تحدي ترميز / تصحيح الخطأ

Question

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

إذا كان المرء يستخدم تصحيح خطأ ريد سليمان مع 4 بايت "التكافؤ" تم نقله إلى نهاية بايت "البيانات" الأربعة ، مثل DDDDPPPP ، وينتهي بك الأمر بـ DDDEPPP (حيث تم إسقاط E خطأ) وتم إسقاط بايت تكافؤ ، لا أعتقد أن هناك طريقة لإعادة بناء الرسالة الأولية (على الرغم من تصحيحني إذا كنت مخطئًا) ...

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

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

أنا أبحث عن أي أفكار مجنونة قد يكون لدى أي شخص ... أي أفكار هناك؟

تعديل:

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

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

نأمل أن يوفر ذلك بعض التوضيح حول ما أبحث عنه ...

Answer 1

في غياب البنية الجبرية "اللطيفة" ، أظن أنه سيكون من الصعب العثور على مخطط موجز يحصل على 10 ** 4 فندات ، لأن المعلومات النظرية ، لا يوجد الكثير من الركود. (يمكن للموضوع أدناه استخدام GF (5) لمدة 5 ** 5 = 3125.) لحسن الحظ ، فإن المشكلة صغيرة بما يكفي بحيث يمكنك تجربة طريقة بناء الكود الجشع لشانون (ابحث أضفها إلى المجموعة).

---

قم بتشفير ما يصل إلى 35 بت باعتباره متعدد الحدود الرباعي F على GF (128). قم بتقييم الحدود في ثماني نقاط محددة مسبقًا x0 ، ... ، x7 و encode as 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (x7) ، حيث يتم تخزين الأصفار المتناوبة والأفراد في MSB.

عند فك التشفير ، انظر أولاً إلى MSBs. إذا كان MSB لا يتطابق مع INDEX MOD 2 ، فسيكون هذا البايت فاسدًا و/أو تم تحويله إلى اليسار بواسطة حذف. افترض أنه جيد وقم بتحويله إلى اليمين (ربما يتراكم العديد من القيم المحتملة المختلفة في مرحلة ما). الآن لدينا ما لا يقل عن سبعة تقييمات من متعدد الحدود f في النقاط المعروفة ، منها على الأكثر فاسدة. يمكننا الآن تجربة جميع الاحتمالات للفساد.

تحرير: قام BMM6O بتطوير الادعاء بأن الجزء الثاني من الحل غير صحيح. أنا أعترض.

دعنا نراجع إمكانيات الحالة التي تكون فيها MSBs 0101101. لنفترض أن x هي مجموعة من البايتات المرسلة و y هي مجموعة من البايتات المستلمة. من ناحية ، y [0] ، y [1] ، y [2] ، y [3] لها MSBs صحيحة ويفترض أن تكون x [0] ، x [1] ، x [2] ، x [3] . من ناحية أخرى ، y [4] ، y [5] ، y [6] لها MSBs غير صحيحة ويفترض أن تكون x [5] ، x [6] ، x [7].

إذا تم إسقاط x [4] ، فلدينا سبعة تقييمات صحيحة لـ f.

إذا تم إسقاط x [3] و x [4] تالفة ، فلدينا تقييم غير صحيح في 3 ، وستة تقييمات صحيحة.

إذا تم إسقاط x [5] و x [4] تالفة ، فلدينا تقييم غير صحيح في 5 ، وستة تقييمات صحيحة.

هناك المزيد من الاحتمالات إلى جانب هذه ، ولكن ليس لدينا أقل من ستة تقييمات صحيحة ، وهو ما يكفي لاستعادة و.

Answer 2

أعتقد أنك ستحتاج إلى دراسة ماذا رموز محو قد تقدم لك. لا أعرف أي حدود بنفسي ، ولكن ربما يحقق نوع من رمز MDS ذلك.

تحرير: بعد بحث سريع وجدته rscode المكتبة وفي مثال هذا ما تقوله

In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.

لذا ، يبدو أن رمز Reed-Solomon هو في الواقع الإجابة وقد تحصل فعليًا على الاسترداد من محو واحد وخطأ واحد في رمز 8،4.

Answer 3

تعمل رموز التكافؤ طالما لا تتأثر بايتات بيانات مختلفة بالخطأ أو الخسارة وطالما أن الخطأ لا يساوي أي بايت بيانات أثناء فقد بايت التكافؤ ، IMHO.

Answer 4

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

لست متأكدًا من ما هو موقفك حيث يمكنك أن تفقد قيمة واحدة ، ولا يزال بإمكانك أن تكون واثقًا من أن القيم المتبقية يتم تسليمها بالترتيب الصحيح ، لكنها ليست موقفًا من نظرية الترميز الكلاسيكية.

ما تقترحه الخوارزميات أعلاه هو: إذا كان بإمكانك تقييد نفسك على 7 بتات فقط من المعلومات ، فيمكنك ملء الجزء الثامن من كل بايت مع التناوب 0 و 1 ، مما سيتيح لك معرفة وضع البايت المفقود. وهذا هو ، ضع 0 في الجزء العلوي من البايت 0 ، 2 ، 4 ، 6 و 1 في أجزاء عالية من الآخرين. في الطرف المتلقي ، إذا تلقيت 7 بايت فقط ، فسيتم إسقاط المفقود من بين البايتات التي تطابقها بتات عالية. لسوء الحظ ، هذا ليس صحيحًا تمامًا: إذا كانت المحو والخطأ مجاورين ، فلا يمكنك معرفة أي بايت تم إسقاطه. على سبيل المثال ، يمكن أن تنجم البتات العالية 0101101 عن إسقاط البايت الرابع ، أو من خطأ في البايت الرابع وإسقاط الثالث ، أو من خطأ في البايت الرابع وإسقاط الخامس.

يمكنك استخدام الرمز الخطي:

1 0 0 0  0 1 1 1
0 1 0 0  1 0 1 1
0 0 1 0  1 1 0 1
0 0 0 1  1 1 1 0

(أي سترسل بيانات مثل (A ، B ، C ، D ، B+C+D ، A+C+D ، A+B+D ، A+B+C) (حيث يتم تنفيذ الإضافة مع XOR ، منذ ذلك الحين A ، B ، C ، D هي عناصر GF (128))). إنه رمز خطي مع المسافة 4 ، بحيث يمكنه تصحيح خطأ بايت واحد. يمكنك فك التشفير مع متلازمة فك تشفير, ، وبما أن الكود مزدوج ذاتي ، فإن المصفوفة H ستكون هي نفسها أعلاه.

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

Answer 5

في حالة الأرقام العشرية ، على افتراض أن أحدهم يتنقل مع الرقم الأول ، الرقم الثاني ، حتى الرقم الثالث ODD ، إلخ - مع رقمين ، تحصل مجموعات) - 00 = 101 ، 01 = 103 ، 20 = 181 ، 99 = 789 ، إلخ أظن أن الفحص من نوع ما ... يمكن أن يكون الرقم التالي إلى آخر مؤشر غريب/حتى على كل من الرسائل الأولية الأولية المكونة من رقمين (1 = حتى أول رقمين ، 3 = أول رقمين) و اتبع نمط كونك غريبًا. بعد ذلك ، يمكن أن يكون الرقم الأخير هو مكان واحد من مجموع الأرقام الفردية ، وبهذه الطريقة إذا كان الرقم مفقودًا ، سيكون واضحًا على الفور ويمكن تصحيحه على افتراض أن آخر رقم كان صحيحًا. على الرغم من ذلك ، فإنه سوف يطرد الأشياء إذا تم إسقاط أحد الأرقام الأخيرة ...

Answer 6

يبدو أنه ممكن من الناحية النظرية إذا افترضنا خطأ 1 بت في بايت خاطئ. نحتاج إلى 3 بتات لتحديد البايت المسقط و 3 بتات لتحديد البايت الخاطئ و 3 بتات لتحديد بت خطأ. لدينا 3 أضعاف أن العديد من البتات الإضافية.

ولكن إذا احتجنا إلى تحديد أي عدد من خطأ البتات في بايت خاطئ ، فإنه يصل إلى 30 بت. حتى أن هذا يبدو ممكنًا مع 32 بت ، على الرغم من أن 32 قريبة جدًا من راحتي.

لكني لا أعرف الساخنة للتشفير للحصول على ذلك. جرب Turbocode؟

Answer 7

في الواقع ، كما قال Krystian ، عندما تقوم بتصحيح رمز RS ، سيتم تصحيح كل من الرسالة و "التكافؤ" ، طالما أن لديك V+2E <(NK) حيث V هو عدد المحوسين (أنت تعرف الموضع ) و ه هو عدد الأخطاء. هذا يعني أنه إذا كان لديك أخطاء فقط ، فيمكنك تصحيح أخطاء (NK)/2 ، أو محو (NK-1) (حول عدد الأخطاء) ، أو مزيج من الاثنين (انظر مقالة باهوت: تحويل تقنيات رموز التحكم في الأخطاء و فك تشفير القصب العالمي).

ما هو أجمل هو أنه يمكنك التحقق من أن التصحيح كان ناجحًا: من خلال التحقق من أن متلازمة الحدود فقط تحتوي على معاملات 0 ، فأنت تعلم أن البايتات المتماثلة+تصحيحها صحيحة. يمكنك القيام بذلك من قبل للتحقق مما إذا كانت الرسالة تحتاج إلى أي تصحيح ، ويمكنك أيضًا القيام بالتحقق بعد فك التشفير للتحقق من أنه تم إصلاح كل من الرسالة وبايتات التكافؤ بالكامل.

يعد Bound V+2e <(NK) مثاليًا ، ولا يمكنك القيام بعمل أفضل (ولهذا السبب يطلق على ريد سولومون رمز تصحيح الخطأ الأمثل). في الواقع ، من الممكن تجاوز هذا الحد باستخدام أساليب Bruteforce ، حتى نقطة معينة (يمكنك الحصول على رموز أخرى أو 2 رموز أخرى لكل رموز) باستخدام قائمة فك تشفير, ، لكنها لا تزال مجالًا في مهدها ، لا أعرف أي تطبيق عملي يعمل.