متتالية دي بروين: كل ثلاث خانات في حلقة من ثمانية رموز

الخلاصة السريعة

اقرأ ثلاث خانات متجاورة من كل موضع، مع الرجوع إلى البداية عند تجاوز نهاية الحلقة. [1]

• النموذج يستخدم الرمزين 0 و1. يجب أن تظهر الأنماط الثمانية ذات الطول 3 مرة واحدة لكل نمط، بما فيها 000. [1]
• اخترنا 00011101؛ نقرأ من اليسار إلى اليمين، ونرقم مواضع البداية من 1 إلى 8.
• من الموضع 7 نقرأ 010، ومن الموضع 8 نقرأ 100، لأن النافذة تستكمل خاناتها من البداية.
• للعرض على سطر دون التفاف، أضف أول خانتين: 0001110100. طوله 10، وفيه ثماني نوافذ؛ السطر الأقصر لا يستوعب ثمانية أنماط مختلفة.
• وجود أربعة أصفار وأربعة آحاد لا يكفي: 00001111 يكرر 000 و111، ويفقد 010 و101.
• في جدولنا، 101 يبدأ عند الموضع 6. تحديد الموضع يفترض الحلقة نفسها واتجاه القراءة والترقيم المتفق عليه؛ لا يمثل ضمانًا لكشف خطأ القراءة.

حدد ما الذي ستعده

النافذة ثلاث خانات متجاورة، وليست ثلاثة رموز تختارها من أماكن متباعدة. والقراءة دورية: بعد آخر رمز نتابع من الأول. هذه الخاصية الدورية أساسية في تعريف متتالية دي بروين. [1]

قائمة الأنماط المطلوبة في فحصنا هي: 000، 001، 010، 011، 100، 101، 110، 111. احتفظ بالأصفار الأولى؛ نحن نقارن نصوصًا ثابتة الطول. كتابة 1 بدل 001 تخفي الخانتين اللتين نحتاج إلى تتبعهما.

تحقق من الحلقة موضعًا بموضع

اكتب 00011101 من اليسار إلى اليمين، وضع الأرقام 1 إلى 8 تحت رموزه بهذا الترتيب. في كل صف من الجدول، ابدأ عند الموضع المحدد، واقرأ ثلاث خانات في الاتجاه نفسه. لا تغير الحلقة أثناء الفحص.

رتب نتائج الجدول ذهنيًا وفق قائمة الأنماط المطلوبة: ستجد كل نمط مرة واحدة. وجود ثمانية صفوف وحده ليس دليلًا؛ فقد تحتوي الصفوف على تكرار. هنا قارنّا المحتوى أيضًا، فوجدنا ثمانية أنماط مختلفة.

اقرأ عبر حد الحلقة

عند الموضع 7، الخانات هي رمز الموضع 7 ثم 8 ثم 1: 0 ثم 1 ثم 0، فتقرأ 010. وعند الموضع 8، تستخدم المواضع 8 ثم 1 ثم 2: 1 ثم 0 ثم 0، فتقرأ 100. لا تتوقف لأن الرسم الخطي انتهى.

الصورة الداخلية تميز الخانات الأصلية والخانتين المضافتين عند عرض الحلقة على سطر. الخانتان المضافتان ليستا موضعين جديدين داخل الحلقة، بل نسخة من أول خانتين لإكمال نافذتي البداية 7 و8.

لماذا يحتاج السطر إلى عشرة رموز؟

العرض الخطي لنموذجنا هو 0001110100. نقرأ فيه النوافذ من المواضع 1 إلى 8 فقط، دون التفاف إضافي. تعطي هذه النوافذ نتائج الجدول نفسها. إذا اعتبرت الرموز العشرة حلقة جديدة، فستغير المسألة وتضيف مواضع قراءة غير مقصودة.

في سطر طوله 10، تستطيع نافذة من ثلاث خانات أن تبدأ عند ثمانية مواضع: لا تبدأ في آخر موضعين لأن الخانات لا تكفي. وبالمثل، سطر من 9 رموز يعطي سبع نوافذ فقط، مهما غيرت محتواه. لذلك يحتاج سطر يحتوي الأنماط الثمانية إلى 10 رموز على الأقل؛ ونموذجنا يحقق هذا الحد.

أما الحلقة ذات ثمانية مواضع فتعطي ثماني نوافذ، لأن القراءة تستمر عبر حدها. حلقة أقصر تعطي مواضع بداية أقل من ثمانية؛ فلا يمكن أن تعرض الأنماط الثمانية المختلفة مرة واحدة. هذا برهان عد بسيط لهذا النموذج، وليس طريقة عامة لتوليد متتاليات أكبر.

اختبر نموذجًا يبدو متوازنًا لكنه يفشل

في 00001111 توجد أربعة أصفار وأربعة آحاد، مثل نموذجنا الصحيح. لكن نوافذه الدورية بالترتيب هي: 000، 000، 001، 011، 111، 111، 110، 100. تكرر نمطان، وغاب 010 و101. توازن عدد الرموز لا يضمن ترتيب النوافذ المطلوب.

للمراجعة، اكتب قائمة النتائج كاملة ثم احسب مرات ظهور كل نمط. ابحث عن التكرار والغياب معًا. لا تقبل سلسلة لمجرد أن طولها ثمانية، ولا تصلح الخطأ بحذف صف من جدول النتائج؛ فالصف يمثل موضعًا موجودًا في الحلقة.

استخدم الجدول لتحديد موضع بداية

إذا قرأت 101 في نموذجنا، تجدها في صف الموضع 6 وحده. لكن قراءة 10 لا تكفي: تبدأ عند الموضعين 6 و8. نحتاج الخانة الثالثة لتمييز هذين الموضعين وفق الجدول.

إذا بدأت ترقيم الحلقة من رمز آخر، تغيرت أرقام المواضع ولو بقيت النوافذ نفسها. وإذا عكست اتجاه القراءة، وجب إعادة بناء الجدول. سجل السلسلة واتجاه القراءة وبداية الترقيم قبل استخدامه.

لو كان المقصود 101 وقرأت الخانة الأخيرة خطأً فصارت 100، فستجد جوابًا صالحًا في الجدول، لكنه يشير إلى الموضع 8. إذن ظهور النمط في الجدول لا يثبت صحة قراءتك. هذا فحص حسابي مكتوب، ولم نجرب حساسًا أو جهازًا فعليًا.