الكود التلافيفي

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Convolutional code" – news · newspapers · books · scholar · JSTOR (May 2015) (Learn how and when to remove this message)

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

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

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

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

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

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

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

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

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

الشكل أدناه هو مُشفِّر بمعدل 1 ⁄ 3 ( م ⁄ ن ) بطول قيد ( ك ) يساوي 3. حدود المولد هي G ₁ = (1,1,1)، و G ₂ = (0,1,1) ، و G ₃ = (1,0,1) . لذلك، يتم حساب بتات الإخراج (modulo 2) على النحو التالي:

ن ₁ = م ₁ + م ₀ + م ₋₁

ن ₂ = م ₀ + م ₋₁

ن ₃ = م ₁ + م ₋₁ .

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

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

تعد أكواد الالتفاف غير المنهجية أكثر شيوعًا بسبب مناعتها الأفضل للضوضاء. ويرتبط ذلك بالمسافة الحرة للكود الالتفافي. ^[6]

• 
  رسم توضيحي قصير للكود التلافيفي غير المنهجي.
• 
  صورة توضيحية قصيرة للكود التلافيفي المنهجي.

إن المشفر الموجود في الصورة أعلاه هو مشفر غير متكرر . وفيما يلي مثال على مشفر متكرر وبالتالي فهو يسمح ببنية ردود الفعل:

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

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

إن المشفر المثال في الشكل 2 هو مشفر مكون من 8 حالات لأن السجلات الثلاثة ستنشئ 8 حالات مشفر ممكنة (2 ³ ). وعادةً ما تستخدم شبكة فك التشفير المقابلة 8 حالات أيضًا.

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

تتضمن أكواد RSC الأخرى وتطبيقات المثال ما يلي:

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

مفيد لـ SCCC وأكواد التوربو متعددة الأبعاد.

مفيد ككود مكون في أكواد توربو منخفضة معدل الخطأ لتطبيقات مثل روابط الأقمار الصناعية. مناسب أيضًا للكود الخارجي SCCC.

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

${\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}=(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.\,}$

تعريف م بواسطة

${\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)\,}$، ويتم تعريف طول القيد على أنه . على سبيل المثال، في المثال الأول، طول القيد هو 3، وفي المثال الثاني، طول القيد هو 4. ${\displaystyle K=m+1\,}$

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

تخيل أن المشفر (كما هو موضح في الشكل 1 أعلاه) يحتوي على "1" في خلية الذاكرة اليسرى ( m ₀ )، و"0" في الخلية اليمنى ( m ₋₁ ). ( m ₁ ليست خلية ذاكرة حقًا لأنها تمثل قيمة حالية). سنحدد هذه الحالة على أنها "10". وفقًا لبت الإدخال، يمكن للمشفر في الدورة التالية التحويل إما إلى الحالة "01" أو الحالة "11". يمكن للمرء أن يرى أنه ليس كل التحولات ممكنة (على سبيل المثال، لا يمكن للمشفر التحويل من الحالة "10" إلى "00" أو حتى البقاء في الحالة "10").

يمكن إظهار جميع التحولات الممكنة على النحو التالي:

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

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

المسافة الحرة ^[7] ( د ) هي الحد الأدنى لمسافة هامينج بين تسلسلات مشفرة مختلفة. قدرة التصحيح ( ت ) للرمز التلافيفي هي عدد الأخطاء التي يمكن تصحيحها بواسطة الرمز. ويمكن حسابها على النحو التالي

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

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

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

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

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

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

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

يحتوي كود التفافي مفكك بواسطة فيتربي شائع الاستخدام على الأقل منذ برنامج فوييجر على طول قيد K يساوي 7 ومعدل r يساوي 1/2. ^[12]

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

يتم استخدام الكود التلافيفي بطول قيد 2 ومعدل 1/2 في GSM كتقنية لتصحيح الأخطاء. ^[13]

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

معدل الكود	مصفوفة الثقب	المسافة الحرة (للكود التلافيفي القياسي لوكالة ناسا K=7)
1/2 (بدون ثقب)	1 1	10
2/3	1 0 1 1	6
3/4	1 0 1 1 1 0	5
5/6	1 0 1 0 1 1 1 0 1 0	4
7/8	1 0 0 0 1 0 1 1 1 1 1 0 1 0	3

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

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

تُسمى أيضًا الأكواد التلافيفية المثقوبة بـ "المثقبة".

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

• الكود التلافيفي الكمي

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

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