رمز تصحيح الأخطاء المتسلسل

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

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

تُظهر نظرية شانون لترميز القنوات أنه على العديد من القنوات المشتركة، توجد أنظمة ترميز قنوات قادرة على نقل البيانات بشكل موثوق بجميع المعدلات${\displaystyle R}$أقل من عتبة معينة${\displaystyle C}$يُطلق على هذا اسم سعة القناة المحددة. في الواقع، يمكن جعل احتمال خطأ فك التشفير يتناقص أُسّيًا مع طول الكتلة.${\displaystyle N}$تتزايد تعقيدات نظام التشفير إلى ما لا نهاية. ومع ذلك، فإن تعقيد نظام فك التشفير الأمثل البسيط الذي يحسب ببساطة احتمالية كل كلمة مشفرة مُرسلة ممكنة يزداد بشكل أُسّي مع${\displaystyle N}$لذلك، يصبح مثل هذا الجهاز الأمثل لفك التشفير غير عملي بسرعة.

أظهر ديف فورني في أطروحته للدكتوراه أنه يمكن استخدام الرموز المتسلسلة لتحقيق احتمالات خطأ متناقصة بشكل أسي عند جميع معدلات البيانات الأقل من السعة، مع تعقيد فك التشفير الذي يزداد فقط بشكل متعدد الحدود مع طول كتلة الرمز.

ليكن C _رمزًا من النوع [ n , k , d ]، أي رمز كتلة بطول n ، وبُعد k ، وأدنى مسافة هامينغ d ، ومعدل r = k / n ، على أبجدية A :

${\displaystyle C_{in}:A^{k}\rightarrow A^{n}}$

ليكن C _رمزًا [ N , K , D ] على أبجدية B مع | B | = | A | ^k رمزًا:

${\displaystyle C_{out}:B^{K}\rightarrow B^{N}}$

تأخذ الشفرة الداخلية C _{_in} أحد المدخلات الممكنة | A | ^{^k} = | B |، وتُشفّرها في مجموعة n- tuple على A ، ثم تُرسلها، وتُفكّ شفرتها إلى أحد المخرجات الممكنة | B |. نعتبر هذه قناة (فائقة) يمكنها إرسال رمز واحد من الأبجدية B. نستخدم هذه القناة N مرة لإرسال كل رمز من الرموز N في كلمة الشفرة C _{_out} . يُرمز إلى دمج C _{_out} (كشفرة خارجية) مع C _{_in} (كشفرة داخلية) بـ C _{_out} .${\displaystyle \circ }$وبالتالي فإن C _في ، هو رمز بطول Nn على الأبجدية A : ^{[ 1 ]}

${\displaystyle C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}}$

يقوم هذا النظام بربط كل رسالة إدخال m = ( m ₁ , m ₂ , ..., m _K ) بكلمة رمزية ( C _in ( m ' ₁ ), C _in ( m ' ₂ ), ..., C _in ( m ' _N )), حيث ( m ' ₁ , m ' ₂ , ..., m ' _N ) = C _out ( m ₁ , m ₂ , ..., m _K ).

تكمن الفكرة الأساسية في هذا النهج في أنه إذا تم فك تشفير C _{_in} باستخدام أسلوب الاحتمال الأقصى (مما يُظهر انخفاضًا أُسّيًا في احتمال الخطأ مع زيادة الطول)، وكان C _{_out} رمزًا بطول N = 2 ^{^nr} يمكن فك تشفيره في زمن متعدد الحدود لـ N ، فإن الرمز المُدمج يمكن فك تشفيره في زمن متعدد الحدود لطوله المُدمج n ² = O ( N ⋅ log( N )) ويُظهر انخفاضًا أُسّيًا في احتمال الخطأ، حتى لو كان تعقيد فك تشفير C _{_in أُسّيًا.} ^{[ 1 ]} يُناقش هذا بمزيد من التفصيل في قسم " فك تشفير الرموز المُدمجة" .

في تعميم لعملية الربط المذكورة أعلاه، يوجد N رمزًا داخليًا ممكنًا C _{_in} ، حيث يُرسل الرمز i _في كلمة رمزية C_out عبر القناة الداخلية باستخدام _الرمز الداخلي i _. تُعد رموز جوستيسن أمثلة على الرموز المُرتبطة المُعممة، حيث يكون الرمز الخارجي رمز ريد-سولومون .

1. مسافة الكود المتسلسل C _خارج${\displaystyle \circ }$C _in is least dD , Én, it is a [ nN , kK , D ' ] code with D ' ≥ dD .

البرهان: لنفترض ^وجود رسالتين مختلفتين m1 ≠ m2 ∈ BK . ولنرمز ^{بـ Δ} إلى المسافة بين كلمتي التشفير. عندئذٍ

${\displaystyle \Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D.}$

وبالتالي، يوجد على الأقل D موضعًا تختلف فيها سلسلة الرموز N للكلمتين المشفرتين C _out ( m ¹ ) و C _out ( m ² ). بالنسبة لهذه المواضع، المشار إليها بـ i ، لدينا

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})_{i}),C_{in}(C_{out}(m^{2})_{i}))\geq d.}$

وبالتالي، يوجد على الأقل d ⋅ D موضعًا في تسلسل n ⋅ N رمزًا مأخوذة من الأبجدية A تختلف فيها الكلمتان الرمزيتان، ومن ثم

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})),C_{in}(C_{out}(m^{2})))\geq dD.}$

2. إذا كانت C _out و C _in عبارة عن رموز كتلية خطية ، فإن C _out${\displaystyle \circ }$_لغة C هي أيضًا عبارة عن كود خطي.

يمكن إثبات هذه الخاصية بسهولة بناءً على فكرة تعريف مصفوفة مولدة للرمز المتسلسل من حيث مصفوفات المولد لـ C _out و C _in .

من المفاهيم الأساسية لخوارزمية فك تشفير الرموز المتسلسلة، فك تشفير الرمز الداخلي أولًا ثم الرمز الخارجي. ولضمان فعالية الخوارزمية، يجب أن يكون زمن تشغيلها متعدد الحدود بالنسبة لطول الكتلة النهائية. لنفترض وجود خوارزمية فك تشفير فريدة للرمز الخارجي بزمن متعدد الحدود. الآن، علينا إيجاد خوارزمية فك تشفير للرمز الداخلي بزمن متعدد الحدود. من المفهوم أن زمن التشغيل متعدد الحدود هنا يعني أن زمن التشغيل متعدد الحدود بالنسبة لطول الكتلة النهائية. الفكرة الرئيسية هي أنه إذا تم اختيار طول الكتلة الداخلية ليكون لوغاريتميًا بالنسبة لحجم الرمز الخارجي، فإن خوارزمية فك تشفير الرمز الداخلي قد تعمل بزمن أسي بالنسبة لطول الكتلة الداخلية، وبالتالي يمكننا استخدام مُفكِّك احتمالية قصوى (MLD) أمثل بزمن أسي للرمز الداخلي.

بالتفصيل، لنفترض أن مدخلات وحدة فك التشفير هي المتجه y = ( y ₁ , ..., y _N ) ∈ ( A ⁿ ) ^N . عندئذٍ، تكون خوارزمية فك التشفير عملية من خطوتين:

1. استخدم MLD للرمز الداخلي C _لإعادة بناء مجموعة من كلمات الرمز الداخلي y ' = ( y ' ₁ , ..., y ' _N ), مع y ' _i = MLD _{C in} ( y _i ), 1 ≤ i ≤ N .
2. قم بتشغيل خوارزمية فك التشفير الفريدة لـ C _على y ' .

الآن، التعقيد الزمني للخطوة الأولى هو O ( N ⋅exp( n ))، حيث n = O (log( N )) هو طول الكتلة الداخلية. بعبارة أخرى، هو O ⁽¹⁾ (أي، زمن متعدد الحدود) بدلالة طول الكتلة الخارجية N. وبما أن خوارزمية فك التشفير الخارجية في الخطوة الثانية يفترض أنها تعمل في زمن متعدد الحدود ^، فإن تعقيد خوارزمية فك التشفير الكلية هو أيضًا زمن متعدد الحدود.

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

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

استُخدمت لأول مرة في المركبة الفضائية فوياجر 2 تركيبةٌ تجمع بين شفرة فيتربي الالتفافية الداخلية وشفرة ريد-سولومون الخارجية (المعروفة بشفرة RSV) ، ^{[ 5 ] [ 8 ]} وسرعان ما أصبحت هذه التركيبة شائعة الاستخدام داخل قطاع الفضاء وخارجه. ولا تزال تُستخدم على نطاق واسع حتى اليوم في اتصالات الأقمار الصناعية ، مثل معيار البث التلفزيوني الرقمي DVB-S . ^{[ 9 ]}

بمعنى أوسع، يمكن الإشارة إلى أي تركيبة (متسلسلة) من رمزين أو أكثر باسم رمز مُدمج. على سبيل المثال، في معيار DVB-S2 ، يتم دمج رمز LDPC عالي الكفاءة مع رمز خارجي جبري لإزالة أي أخطاء متبقية من رمز LDPC الداخلي بسبب حد الخطأ الأساسي المتأصل فيه . ^{[ 10 ]}

كما يتم استخدام مخطط تسلسل بسيط على القرص المضغوط (CD)، حيث تعمل طبقة التداخل بين رمزي ريد-سولومون بأحجام مختلفة على نشر الأخطاء عبر كتل مختلفة.

يُقدّم الوصف أعلاه لما يُعرف الآن بالترميز التسلسلي المتسلسل. وقد طبّقت رموز التوربو ، كما وُصفت لأول مرة عام ١٩٩٣، تسلسلاً متوازياً لترميزين التفافيين، مع مُبدِّل بين الترميزين ومُفكِّك ترميز تكراري ينقل المعلومات ذهاباً وإياباً بينهما. ^{[ ٦ ]} يتميز هذا التصميم بأداء أفضل من أي ترميز متسلسل تم ابتكاره سابقاً.

مع ذلك، يتمثل أحد الجوانب الرئيسية لرموز التوربو في أسلوب فك التشفير التكراري. ويُطبَّق فك التشفير التكراري الآن أيضًا على التسلسلات المتسلسلة لتحقيق مكاسب تشفيرية أعلى، كما هو الحال في رموز الالتفاف المتسلسلة المتسلسلة (SCCCs). وقد طُبِّق شكل مبكر من فك التشفير التكراري باستخدام ما بين دورتين إلى خمس دورات في "رمز غاليليو" الخاص بمسبار غاليليو الفضائي . ^{[ 5 ]}

• متجه جيلبرت-فارشاموف
• رمز جاستيسن
• متجهة إلى سينغلتون
• متجه إلى زيابلوف

• شو لين؛ دانيال ج. كوستيلو الابن (1983). ترميز التحكم في الأخطاء: الأساسيات والتطبيقات . برنتيس هول . الصفحات 278-280 . ISBN  978-0-13-283796-5.
• إف جيه ماك ويليامز ؛ إن جيه إيه سلون (1977). نظرية رموز تصحيح الأخطاء . نورث هولاند. الصفحات 307-316 . ISBN  978-0-444-85193-2.

• ديف فورني (محرر). "الرموز المتسلسلة" . سكولاربيديا .
• ملاحظات محاضرة جامعة بافالو حول نظرية الترميز - د. أتري رودرا