رمز الوزن الثابت

في نظرية الترميز ، يُعرف الترميز ذو الوزن الثابت ، أو ما يُسمى أيضًا بترميز m من n ، بأنه ترميز لاكتشاف الأخطاء وتصحيحها، حيث تشترك جميع الكلمات المشفرة في نفس وزن هامينغ . ويُعد الترميز الأحادي الساخن والترميز المتوازن نوعين شائعين من الترميز ذي الوزن الثابت.

ترتبط هذه النظرية ارتباطًا وثيقًا بنظرية التصميمات (مثل تصميمات t وأنظمة شتاينر ). ويركز معظم العمل في هذا المجال من الرياضيات المتقطعة على الشفرات الثنائية ذات الوزن الثابت.

تُستخدم رموز الوزن الثابت الثنائية في تطبيقات عديدة، منها تقنية القفز الترددي في شبكات GSM . ^{[ 1 ]} تستخدم معظم الرموز الشريطية رمز الوزن الثابت الثنائي لتبسيط عملية ضبط عتبة السطوع التي تميز بين الخطوط السوداء والبيضاء تلقائيًا. وتستخدم معظم رموز الخطوط إما رمز الوزن الثابت أو رمز التباين المزدوج ذي الوزن شبه الثابت . بالإضافة إلى استخدامها كرموز لتصحيح الأخطاء، يمكن أيضًا استغلال المسافة الكبيرة بين كلمات الرمز في تصميم الدوائر غير المتزامنة ، مثل الدوائر غير الحساسة للتأخير .

يمكن للرموز ذات الوزن الثابت، مثل رموز بيرغر ، اكتشاف جميع الأخطاء أحادية الاتجاه.

تتمثل المشكلة الأساسية المتعلقة برموز الوزن الثابت فيما يلي: ما هو الحد الأقصى لعدد الكلمات المشفرة في رمز ثنائي ذي وزن ثابت بطول${\displaystyle n}$مسافة هامينغ${\displaystyle d}$والوزن${\displaystyle w}$يُطلق على هذا الرقم اسم${\displaystyle A(n,d,w)}$.

باستثناء بعض الملاحظات البسيطة، يستحيل عمومًا حساب هذه الأرقام بطريقة مباشرة. تُحدد الحدود العليا بواسطة العديد من النظريات المهمة، مثل حدي جونسون الأول والثاني ^{[ 2 ]} ، ويمكن أحيانًا إيجاد حدود عليا أفضل بطرق أخرى. أما الحدود الدنيا، فتُحدد غالبًا من خلال عرض رموز محددة، إما باستخدام مجموعة متنوعة من أساليب الرياضيات المتقطعة، أو من خلال بحث حاسوبي مكثف. نُشر جدول كبير لهذه الرموز القياسية في عام 1990 ^{[ 3 ]،} وتم توسيعه ليشمل رموزًا أطول (ولكن فقط لتلك القيم من${\displaystyle d}$و${\displaystyle w}$(وهي ذات صلة بتطبيق GSM) تم نشرها في عام 2006. ^{[ 1 ]}

تُعد رموز "واحد من بين N" حالة خاصة من رموز الوزن الثابت ، والتي تقوم بتشفير${\displaystyle \log _{2}N}$بتات في كلمة رمزية من${\displaystyle N}$البتات. يستخدم رمز واحد من اثنين الكلمتين الرمزيتين 01 و10 لترميز البتات '0' و'1'. يمكن لرمز واحد من أربعة استخدام الكلمات 0001 و0010 و0100 و1000 لترميز بتتين 00 و01 و10 و11. ومن الأمثلة على ذلك ترميز السكة المزدوجة ، ووصلة السلسلة ^{[ 4 ]} المستخدمة في الدوائر غير الحساسة للتأخير. بالنسبة لهذه الرموز،${\displaystyle n=N,~d=2,~w=1}$و${\displaystyle A(n,d,w)=n}$.

تتضمن بعض الاستخدامات البارزة للرموز أحادية الطور ما يلي: يستخدم رمز العلامة ثنائي الطور رمز 1 من 2؛ يستخدم تعديل موضع النبضة رمز 1 من n ؛ وحدة فك تشفير العنوان ، إلخ.

في نظرية الترميز ، يُعرف الترميز المتوازن بأنه ترميز ثنائي لتصحيح الأخطاء الأمامية، حيث تحتوي كل كلمة منه على عدد متساوٍ من بتات الصفر والواحد. وقد طوّر دونالد كنوث الترميزات المتوازنة ؛ ^{[ 5 ]} وهي مجموعة فرعية من ما يُسمى بالترميزات غير المرتبة، وهي ترميزات تتميز بأن مواقع الواحدات في كلمة ما لا تُشكّل أبدًا مجموعة فرعية من مواقع الواحدات في كلمة أخرى. ومثل جميع الترميزات غير المرتبة، تُناسب الترميزات المتوازنة اكتشاف جميع الأخطاء أحادية الاتجاه في الرسالة المُرمّزة. وتتيح الترميزات المتوازنة فك تشفير فعال للغاية، يُمكن تنفيذه بالتوازي. ^{[ 5 ] [ 6 ] [ 7 ]}

تتضمن بعض الاستخدامات البارزة لرموز الوزن المتوازن ما يلي: يستخدم رمز العلامة ثنائي الطور رمز 1 من 2؛ ويستخدم ترميز 6b/8b رمز 4 من 8؛ ورمز هادامارد هو${\displaystyle 2^{k-1}}$ل${\displaystyle 2^{k}}$الرمز (باستثناء كلمة الرمز الصفرية)، رمز الثلاثة من ستة ؛ إلخ.

يمكن اعتبار ترميز المسار ثلاثي الأسلاك المستخدم في MIPI C-PHY تعميمًا لترميز الوزن الثابت إلى الترميز الثلاثي - حيث ينقل كل سلك إشارة ثلاثية ، وفي أي لحظة، ينقل أحد الأسلاك الثلاثة إشارة منخفضة، وينقل آخر إشارة متوسطة، وينقل الثالث إشارة عالية. ^{[ 8 ]}

رمز m من n هو رمز قابل للفصل لكشف الأخطاء ، طول كلمته n بت، حيث تحتوي كل كلمة على m من الرقم "واحد". يؤدي خطأ بت واحد إلى احتواء الكلمة على m + 1 أو m - 1 من الرقم "واحد". مثال على رمز m من n هو رمز 2 من 5 الذي تستخدمه خدمة البريد الأمريكية .

أبسط طريقة للتنفيذ هي إضافة سلسلة من الآحاد إلى البيانات الأصلية حتى تحتوي على m من الآحاد، ثم إضافة الأصفار لإنشاء رمز بطول n .

مثال:

تتضمن بعض الاستخدامات البارزة لرموز الوزن الثابت، بخلاف رموز الوزن المتوازن والرمز الواحد الساخن المذكورة أعلاه، ما يلي: يستخدم الرمز 39 رمز 3 من 9؛ ويستخدم الرمز العشري المشفر ثنائي الخماسي رمز 2 من 7، ورمز 2 من 5 ، وما إلى ذلك.

• جدول الحدود الدنيا لـ${\displaystyle A(n,d,w)}$تمت الصيانة بواسطة أندرياس بروير
• جدول الحدود العليا لـ${\displaystyle A(n,d,w)}$يتولى إريك أغريل صيانة الموقع.