الشفرة الالتفافية

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

تُعدّ القدرة على إجراء فك تشفير اقتصادي باستخدام طريقة القرار المرن ذي الاحتمالية القصوى إحدى المزايا الرئيسية للرموز الالتفافية. وهذا على عكس رموز الكتل التقليدية، التي تُمثَّل عادةً بشبكة متغيرة مع الزمن، وبالتالي يتم فك تشفيرها عادةً باستخدام طريقة القرار الصارم. غالبًا ما تتميز الرموز الالتفافية بمعدل الترميز الأساسي وعمق (أو ذاكرة) المُشفِّر.${\displaystyle [n,k,K]}$يُعطى معدل الترميز الأساسي عادةً على النحو التالي:${\displaystyle k/n}$حيث k هو معدل بيانات الإدخال الخام، و n هو معدل بيانات دفق الإخراج المشفر بواسطة القناة. يكون k أقل من n لأن ترميز القناة يُدخل تكرارًا في بتات الإدخال. يُطلق على الذاكرة غالبًا اسم "طول القيد" K ، حيث يكون الإخراج دالةً للإدخال الحالي بالإضافة إلى الإدخال السابق.${\displaystyle K-1}$المدخلات. ^{[ 1 ]} يمكن أيضًا تحديد العمق على أنه عدد عناصر الذاكرة v في متعدد الحدود أو الحد الأقصى لعدد حالات المشفر (عادةً:${\displaystyle 2^{v}}$).

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

يتم تعديل معدل ترميز الشفرة الالتفافية عادةً عن طريق تثقيب الرموز . على سبيل المثال، شفرة التفافية ذات معدل ترميز "أم".${\displaystyle n/k=1/2}$قد تتعرض للثقب بمعدل أعلى، على سبيل المثال،${\displaystyle 7/8}$ببساطة عن طريق عدم إرسال جزء من رموز التشفير. يتحسن أداء التشفير التلافيفي المثقوب عمومًا مع زيادة كمية بيانات التكافؤ المرسلة. إن القدرة على إجراء فك تشفير اقتصادي باستخدام قرارات مرنة على التشفير التلافيفي، بالإضافة إلى مرونة طول الكتلة ومعدل التشفير، تجعله شائعًا جدًا في الاتصالات الرقمية.

طُرحت رموز الالتفاف في عام 1955 على يد بيتر إلياس . كان يُعتقد آنذاك بإمكانية فك تشفير هذه الرموز بجودة عالية، ولكن على حساب زيادة الحساب والتأخير. في عام 1967، أثبت أندرو فيتربي إمكانية فك تشفير رموز الالتفاف باستخدام خوارزمية فيتربي ، وهي خوارزمية فك تشفير تعتمد على الشبكة الثابتة زمنيًا، وذلك باستخدام طريقة الاحتمال الأقصى مع تعقيد معقول . لاحقًا، طُوّرت خوارزميات أخرى لفك التشفير تعتمد على الشبكة، بما في ذلك خوارزمية BCJR .

تم اختراع رموز الالتفاف المنهجية المتكررة بواسطة كلود بيرو حوالي عام 1991. وقد أثبتت هذه الرموز فائدتها بشكل خاص للمعالجة التكرارية بما في ذلك معالجة الرموز المتسلسلة مثل رموز التوربو . ^{[ 2 ]}

باستخدام مصطلحات "الالتفاف"، يمكن اعتبار رمز الالتفاف الكلاسيكي مرشح استجابة نبضية محدودة (FIR)، بينما يمكن اعتبار رمز الالتفاف المتكرر مرشح استجابة نبضية لا نهائية (IIR).

تُستخدم رموز الالتفاف على نطاق واسع لتحقيق نقل بيانات موثوق في العديد من التطبيقات، مثل الفيديو الرقمي ، والراديو، والاتصالات المتنقلة (على سبيل المثال، في شبكات GSM وGPRS وEDGE و3G (حتى الإصدار 7 من 3GPP) ^{[ 4 ] [ 5 ]} )، والاتصالات عبر الأقمار الصناعية . ^{[ 6 ]} غالبًا ما تُنفذ هذه الرموز بالتزامن مع رمز القرار الحاسم، وخاصةً رمز ريد-سولومون . قبل ظهور رموز التوربو، كانت هذه التركيبات هي الأكثر كفاءة، حيث كانت الأقرب إلى حد شانون .

لترميز البيانات باستخدام الالتفاف، ابدأ بـ k من سجلات الذاكرة ، يحتوي كل منها على بت إدخال واحد. ما لم يُذكر خلاف ذلك، تبدأ جميع سجلات الذاكرة بقيمة 0. يحتوي المُشفِّر على n من جامعات modulo-2 (يمكن تنفيذ جامع modulo-2 باستخدام بوابة XOR منطقية واحدة ، حيث تكون العملية المنطقية كالتالي: 0+0 = 0 ، 0+1 = 1 ، 1+0 = 1 ، 1+1 = 0 )، و n من كثيرات الحدود المولدة - واحدة لكل جامع (انظر الشكل أدناه). يتم إدخال بت الإدخال _m1 إلى السجل الأيسر. باستخدام كثيرات الحدود المولدة والقيم الموجودة في السجلات المتبقية، يُخرج المُشفِّر n من الرموز. يمكن إرسال هذه الرموز أو حذفها حسب معدل الترميز المطلوب. الآن، قم بإزاحة جميع _قيم السجلات إلى اليمين ( ينتقل m1 إلى _{m0 ،} وينتقل m0 إلى m - 1 ₎ وانتظر بت الإدخال التالي. إذا لم تكن هناك بتات إدخال متبقية، فإن المشفر يستمر في الإزاحة حتى تعود جميع السجلات إلى حالة الصفر (إنهاء بت المسح).        

الشكل أدناه يُمثل مُشفِّرًا بمعدل 1/3 ( m / n ) وطول قيد ( k ) يساوي 3. كثيرات الحدود المُولِّدة هي G1 = (1,1,1)، _و G2 = (0,1,1) _، و G3 = (1,0,1) _. لذلك، تُحسب بتات الخرج (بالمقياس 2) كما يلي :

n ₁ = m ₁ + m ₀ + m ₋₁

n ₂ = m ₀ + m ₋₁

n ₃ = m ₁ + m ₋₁ .

يمكن أن تكون رموز الالتفاف منهجية وغير منهجية:

• يكرر بشكل منهجي بنية الرسالة قبل التشفير
• تغييرات غير منهجية في البنية الأولية

تُعدّ رموز الالتفاف غير المنتظمة أكثر شيوعًا نظرًا لمقاومتها الأفضل للضوضاء. ويرتبط ذلك بالمسافة الحرة لرمز الالتفاف. ^{[ 7 ]}

• 
  مثال توضيحي قصير لرمز الالتفاف غير المنهجي.
• 
  مثال توضيحي موجز لرمز الالتفاف المنهجي.

المُشفِّر في الصورة أعلاه هو مُشفِّر غير تكراري . إليك مثال على مُشفِّر تكراري، ولذلك فهو يدعم بنية التغذية الراجعة:

يُعدّ المُشفّر المُشار إليه في المثال مُنظّمًا لأنّ بيانات الإدخال تُستخدم أيضًا في رموز الإخراج (الإخراج 2). أما الرموز التي لا تتضمن بيانات الإدخال في رموز الإخراج فتُسمى غير مُنظّمة.

تتسم الشفرات التكرارية عادةً بالمنهجية، وعلى النقيض، تتسم الشفرات غير التكرارية عادةً باللامنهجية. ليس هذا شرطًا أساسيًا، ولكنه ممارسة شائعة.

يُعدّ المُشفّر الموضح في الصورة 2 مثالاً على مُشفّر ثماني الحالات، لأنّ السجلات الثلاثة تُتيح ثماني حالات مُمكنة للمُشفّر (2 ³ ). وعادةً ما يستخدم مُفكّك الشفرة المُقابل ثماني حالات أيضاً.

أصبحت رموز الالتفاف المنهجي المتكرر (RSC) أكثر شيوعًا نظرًا لاستخدامها في رموز Turbo. وتُعرف هذه الرموز أيضًا باسم الرموز شبه المنهجية.

تتضمن رموز RSC الأخرى والتطبيقات النموذجية ما يلي:

مفيد لتنفيذ كود LDPC وككود مكون داخلي لرموز الالتفاف المتسلسلة المتسلسلة (SCCC).

مفيد لبرامج SCCC ورموز التوربو متعددة الأبعاد.

يُعدّ هذا الكود مفيدًا كجزء أساسي في أكواد التوربو ذات معدل الخطأ المنخفض لتطبيقات مثل وصلات الأقمار الصناعية. كما أنه مناسب ككود خارجي لـ SCCC.

يُطلق على المشفر التلافيفي هذا الاسم لأنه يقوم بعملية التفاف بين دفق الإدخال واستجابات النبضات الخاصة بالمشفر :

${\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty}h_{k}^{j}x_{ik}=(x*h^{j})[i],}$

حيث x هي سلسلة إدخال، و y ^j هي سلسلة من المخرج j ، و h ^j هي استجابة نبضية للمخرج j و${\displaystyle {*}}$يشير إلى عملية الالتفاف.

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

دوال النقل للمشفّر الأول (غير التكراري) هي:

• ${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{3}(z)=1+z^{-2}.\,}$

دوال التحويل للمشفّر الثاني (التكراري) هي:

• ${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\,}$
• ${\displaystyle H_{2}(z)=1.\,}$

عرّف m بـ

${\displaystyle m=\max _{i}\operatorname {polydeg} (H_{i}(1/z))\,}$

حيث، لأي دالة كسرية${\displaystyle f(z)=P(z)/Q(z)\,}$،

${\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}$.

إذن ، m هي أعلى درجة من درجات كثيرات الحدود لـ

${\displaystyle H_{i}(1/z)\,}$ويُعرَّف طول القيد على النحو التالي:${\displaystyle K=m+1\,}$على سبيل المثال، في المثال الأول يكون طول القيد 3، وفي المثال الثاني يكون طول القيد 4.

المشفر التلافيفي هو آلة ذات حالات محدودة . المشفر الذي يحتوي على n خلية ثنائية سيكون له 2^ ⁿ حالة.

تخيل أن المُشفِّر (الموضح في الصورة 1 أعلاه) يحتوي على القيمة '1' في خلية الذاكرة اليسرى ( _{m0)، والقيمة '0' في الخلية اليمنى (m-1). (m1 ليست} خلية ذاكرة حقيقية _لأنها تمثل قيمة حالية). سنرمز لهذه الحالة بالرمز "10". وفقًا لبت الإدخال، يمكن للمُشفِّر في الدورة التالية التحويل إما إلى الحالة "01" أو الحالة "11". يتضح أن بعض الانتقالات غير ممكنة (على سبيل المثال، لا يمكن للمُفكِّك التحويل من الحالة "10" إلى "00" أو حتى البقاء في الحالة "10").

يمكن عرض جميع التحولات الممكنة كما يلي:

يمكن تمثيل التسلسل المشفر الفعلي كمسار على هذا الرسم البياني. يظهر أحد المسارات الصحيحة باللون الأحمر كمثال.

يُعطينا هذا الرسم البياني فكرةً عن فك التشفير : إذا لم تتطابق سلسلة مُستلمة مع هذا الرسم البياني، فهذا يعني أنها استُلمت مع وجود أخطاء، وعلينا اختيار أقرب سلسلة صحيحة (متوافقة مع الرسم البياني). وتستغل خوارزميات فك التشفير الحقيقية هذه الفكرة.

المسافة الحرة ^{[ 8 ]} ( d ) هي أقصر مسافة هامينغ بين تسلسلات مشفرة مختلفة. قدرة التصحيح ( t ) لرمز الالتفاف هي عدد الأخطاء التي يمكن تصحيحها بواسطة هذا الرمز. ويمكن حسابها كالتالي:

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}$

بما أن الترميز التلافيفي لا يستخدم كتلًا، بل يعالج تدفقًا مستمرًا من البتات، فإن قيمة t تنطبق على عدد من الأخطاء المتقاربة نسبيًا. أي أنه يمكن عادةً إصلاح مجموعات متعددة من t خطأ عندما تكون متباعدة نسبيًا.

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

توجد عدة خوارزميات لفك تشفير الشفرات الالتفافية. بالنسبة لقيم k الصغيرة نسبيًا ، تُستخدم خوارزمية فيتربي على نطاق واسع نظرًا لأدائها الذي يحقق أقصى احتمالية وقابليتها العالية للتوازي. ولذلك، يسهل تنفيذ مُفكِّكات فيتربي في دوائر VLSI البرمجية وعلى وحدات المعالجة المركزية المزودة بمجموعات تعليمات SIMD .

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

تُعيد كلٌّ من خوارزميات فيتربي وفك التشفير التسلسلي قراراتٍ حاسمة: وهي البتات التي تُشكّل الكلمة المشفرة الأكثر احتمالاً. يُمكن إضافة مقياس ثقة تقريبي لكل بت باستخدام خوارزمية فيتربي ذات المخرجات الناعمة . يُمكن الحصول على قرارات ناعمة ذات احتمالية قصوى لاحقة (MAP) لكل بت باستخدام خوارزمية BCJR .

في الواقع، تُستخدم في الصناعة هياكل رموز الالتفاف المُحددة مسبقًا والتي تم الحصول عليها خلال الأبحاث العلمية. ويرتبط هذا بإمكانية اختيار رموز الالتفاف الكارثية (التي تُسبب عددًا أكبر من الأخطاء).

يتميز رمز الالتفاف الذي تم فك تشفيره بواسطة Viterbi، والذي يستخدم على الأقل منذ برنامج Voyager ، بطول قيد K يبلغ 7 ومعدل r يبلغ 1/2. ^{[ 13 ]}

تستخدم مركبة مارس باثفايندر ، ومركبة استكشاف المريخ ، ومسبار كاسيني المتجه إلى زحل قيمة K تبلغ 15 ومعدل 1/6؛ ويؤدي هذا الكود أداءً  أفضل بحوالي 2 ديسيبل من الكود الأبسط${\displaystyle K=7}$رمز بتكلفة تزيد 256 ضعفًا في تعقيد فك التشفير (مقارنة برموز مهمة فوياجر).

يُستخدم رمز الالتفاف ذو طول قيد 2 ومعدل 1/2 في نظام GSM كتقنية لتصحيح الأخطاء. ^{[ 14 ]}

يمكن تصميم رمز الالتفاف بأي معدل ترميز بالاعتماد على اختيار متعدد الحدود؛ ^{[ 16 ]} ومع ذلك، عمليًا، تُستخدم غالبًا عملية التثقيب لتحقيق معدل الترميز المطلوب. التثقيب هو أسلوب يُستخدم لإنشاء رمز بمعدل m / n من رمز أساسي منخفض المعدل (مثل 1/ n ). ويتم ذلك عن طريق حذف بعض البتات من خرج المُشفِّر. تُحذف البتات وفقًا لمصفوفة تثقيب . فيما يلي مصفوفات التثقيب الأكثر استخدامًا:

على سبيل المثال، إذا أردنا إنشاء رمز بمعدل 2/3 باستخدام المصفوفة المناسبة من الجدول أعلاه، فيجب علينا أخذ خرج مُشفِّر أساسي وإرسال كل بت من الفرع الأول وكل بت من الفرع الثاني. ويُحدد ترتيب الإرسال المحدد وفقًا لمعيار الاتصال ذي الصلة.

تُستخدم رموز الالتفاف المثقوبة على نطاق واسع في الاتصالات عبر الأقمار الصناعية ، على سبيل المثال، في أنظمة Intelsat والبث الرقمي للفيديو .

تُسمى رموز الالتفاف المثقوبة أيضًا "المثقبة".

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

• شفرة الالتفاف الكمومي

•  تتضمن هذه المقالة موادًا متاحة للعموم من المعيار الفيدرالي 1037C ، إدارة الخدمات العامة . مؤرشفة من الأصل بتاريخ 22 يناير 2022.

• يتناول الكتاب المدرسي الإلكتروني: نظرية المعلومات والاستدلال وخوارزميات التعلم ، من تأليف ديفيد جيه سي ماكاي ، الرموز الالتفافية في الفصل 48.
• صفحة رموز تصحيح الأخطاء (ECC)
• شرح برنامج ماتلاب
• أساسيات أجهزة فك التشفير الالتفافية لتحسين الاتصالات الرقمية
• رموز الالتفاف (معهد ماساتشوستس للتكنولوجيا)
• نظرية المعلومات والترميز (جامعة إلميناو التقنية) مؤرشفة في 30-08-2017 على موقع Wayback Machine ، وتناقش الرموز الالتفافية في الصفحة 48.