خوارزمية لإنشاء رمز تصحيح الأخطاء في الحجم على بتات n

Question

أرغب في إنشاء رمز على بتات n لـ K مدخلات مختلفة أريد تصنيفها. المطلب الرئيسي لهذا الرمز هو معايير تصحيح الأخطاء: أن الحد الأدنى للمسافة الزوجية بين أي ترميزين من المدخلات المختلفة. لست بحاجة إلى أن تكون دقيقة - الإرادة التقريبية ، وسهولة الاستخدام وسرعة التنفيذ الحسابي هي أولوية أيضًا.

بشكل عام ، سيكون N في المئات ، K في العشرات.

أيضا ، هل هناك ملزمة ضيقة بشكل معقول على الحد الأدنى لمسافة الهلام بين التشفيرات الثنائية N-bit المختلفة؟

Answer 1

مشكلة العثور على أفضل رمز تصحيح الأخطاء الدقيق للمعلمات المعطاة أمر صعب للغاية ، حتى أن أفضل الرموز تقريبًا صعبة. علاوة على ذلك ، فإن بعض الرموز لا تحتوي على أي خوارزميات فك تشفير لائقة ، بينما بالنسبة للآخرين ، فإن مشكلة فك التشفير صعبة للغاية.

ومع ذلك ، فأنت تسأل عن مجموعة معينة من المعلمات حيث n ≫ k ، حيث إذا فهمت بشكل صحيح ، فأنت تريد رمز الطول k. (بحيث يتم ترميز أجزاء K في N بت.) في هذا النطاق ، من المحتمل أن يكون للرمز العشوائي مسافة جيدة جدًا. المشكلة الوحيدة هي أن فك التشفير هو في أي مكان من غير عملي إلى مقبل ، وأن حساب المسافة الدنيا ليس بهذه السهولة.

ثانياً ، إذا كنت تريد رمزًا صريحًا للحالة n ≫ k ، فيمكنك القيام بعمل جيد مع أ رمز BCH مع Q = 2. كما توضح صفحة ويكيبيديا ، هناك خوارزمية فك تشفير جيدة لرموز BCH.

فيما يتعلق بالحدود العليا للمسافة الدنيا للهجوم ، في النطاق n ≫ k يجب أن تبدأ بـ هامينغ ملزمة, ، والمعروفة أيضًا باسم المجلد المقيد أو ملزمة التعبئة المجال. فكرة الإزمة بسيطة وجميلة: إذا كانت المسافة الدنيا هي t ، فيمكن أن يصحح الرمز الأخطاء حتى الأرضية المسافة ((T-1)/2). إذا تمكنت من تصحيح الأخطاء في بعض دائرة نصف قطرها ، فهذا يعني أن كرات الهزلية في نصف القطر لا تتداخل. من ناحية أخرى ، إجمالي عدد الكلمات الممكنة هو 2^ن, ، لذلك إذا قمت بتقسيم ذلك على عدد النقاط في كرة هامينغ واحدة (والتي في الحالة الثنائية هي مجموع معاملات ذات الحدين) ، ستحصل على حد أعلى على عدد كلمات التعليمات البرمجية الخالية من الأخطاء. من الممكن التغلب على هذا الحد ، ولكن بالنسبة للمسافة الدنيا الكبيرة ، ليس الأمر سهلاً. في هذا النظام ، إنه أمر جيد جدًا.