رمز توربو

في نظرية المعلومات ، تُعدّ رموز التوربو فئةً من رموز تصحيح الأخطاء الأمامية عالية الأداء ، طُوّرت في الفترة ما بين عامي 1990 و1991، ونُشرت لأول مرة عام 1993. وكانت هذه الرموز أول رموز عملية تقترب من الحد الأقصى لسعة القناة، أو حد شانون ، وهو الحد الأقصى النظري لمعدل الترميز الذي يضمن استمرار الاتصال الموثوق به عند مستوى ضوضاء محدد. تُستخدم رموز التوربو في اتصالات الجيل الثالث والرابع ( مثل UMTS و LTE ) وفي اتصالات الأقمار الصناعية (في الفضاء السحيق )، بالإضافة إلى تطبيقات أخرى يسعى فيها المصممون إلى تحقيق نقل معلومات موثوق عبر روابط اتصال محدودة النطاق الترددي أو زمن الاستجابة في وجود ضوضاء تُشوّه البيانات. تتنافس رموز التوربو مع رموز التحقق من التكافؤ منخفضة الكثافة (LDPC)، التي تُقدّم أداءً مماثلاً. وحتى انتهاء صلاحية براءة اختراع رموز التوربو، ^{[ 1 ]} كان وضع رموز LDPC غير الخاضعة لبراءة اختراع عاملاً مهماً في استمرار أهميتها. ^{[ 2 ]}

نشأ مصطلح "الرمز التوربيني" من حلقة التغذية الراجعة المستخدمة أثناء فك تشفير الرمز التوربيني العادي، والتي شُبّهت بتغذية العادم الراجعة المستخدمة في شحن المحرك التوربيني . وقد جادل هاغناور بأن مصطلح "الرمز التوربيني" تسمية خاطئة، إذ لا توجد تغذية راجعة في عملية التشفير. ^{[ 3 ]}

تم تقديم طلب براءة الاختراع الأساسي لرموز التوربو في 23 أبريل 1991. ويذكر طلب براءة الاختراع أن كلود بيرو هو المخترع الوحيد لرموز التوربو. وقد أسفر تقديم طلب براءة الاختراع عن عدة براءات اختراع، من بينها براءة الاختراع الأمريكية رقم 5,446,747 ، التي انتهت صلاحيتها في 29 أغسطس 2013.

كانت أول ورقة بحثية منشورة حول رموز التوربو بعنوان " الترميز وفك الترميز التصحيحي للأخطاء بالقرب من حد شانون: رموز التوربو ". ^{[ 4 ]} نُشرت هذه الورقة عام 1993 في وقائع مؤتمر الاتصالات الدولي التابع لمعهد مهندسي الكهرباء والإلكترونيات (IEEE). وقد جُمعت هذه الورقة من ثلاث أوراق بحثية منفصلة بسبب ضيق المساحة. ونتيجةً لذلك، أُدرجت ثلاثة مؤلفين في الورقة: بيرو، وجلافيو ، وثيتيماجيشيما (من معهد IMT Atlantique، ومعهد ENST Bretagne سابقًا ، فرنسا). ومع ذلك، يتضح من طلب براءة الاختراع الأصلي أن بيرو هو المخترع الوحيد لرموز التوربو، وأن المؤلفين الآخرين ساهموا بمواد أخرى غير المفاهيم الأساسية.

كانت رموز التوربو ثورية للغاية عند ظهورها لدرجة أن العديد من الخبراء في مجال الترميز لم يصدقوا النتائج المُعلنة. وعندما تم تأكيد الأداء، حدثت ثورة صغيرة في عالم الترميز أدت إلى البحث في أنواع أخرى كثيرة من معالجة الإشارات التكرارية. ^{[ 5 ]}

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

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

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

في ورقة بحثية لاحقة، أشاد بيرو بحدس "جي. باتيل، وج. هاجيناور، وب. هوهر، الذين سلطوا الضوء في أواخر الثمانينيات على أهمية المعالجة الاحتمالية". وأضاف أن " آر. جالاجر وإم. تانر كانا قد تخيلا بالفعل تقنيات التشفير وفك التشفير التي ترتبط مبادئها العامة ارتباطًا وثيقًا"، على الرغم من أن الحسابات اللازمة كانت غير عملية في ذلك الوقت. ^{[ 6 ]}

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

يرسل هذا النظام المُشفّر ثلاث كتل فرعية من البتات. الكتلة الفرعية الأولى هي كتلة بيانات الحمولة المكونة من m بت. الكتلة الفرعية الثانية هي n/2 بتات التكافؤ لبيانات الحمولة، محسوبة باستخدام رمز التفافي منهجي متكرر (رمز RSC). الكتلة الفرعية الثالثة هي n/2 بتات التكافؤ لتبديل معروف لبيانات الحمولة، محسوبة أيضًا باستخدام رمز RSC. بالتالي، يتم إرسال كتلتين فرعيتين زائدتين ولكن مختلفتين من بتات التكافؤ مع الحمولة. تحتوي الكتلة الكاملة على m + n بت من البيانات بمعدل ترميز m / ( m + n ) . يتم تنفيذ تبديل بيانات الحمولة بواسطة جهاز يُسمى المُشَبِّط .

من الناحية المادية، يتكون مشفر رمز التوربو هذا من اثنين من مشفرات RSC المتطابقة، C ₁ و C ₂ ، كما هو موضح في الشكل، والتي يتم توصيلها ببعضها البعض باستخدام مخطط تسلسل يسمى التسلسل المتوازي :

في الشكل، M هو سجل ذاكرة. يُجبر خط التأخير والمُشَبِّط بتات الإدخال dk _على الظهور في تسلسلات مختلفة. في التكرار الأول، يظهر تسلسل الإدخال dk عند كلا مخرجي المُشفِّر، xk و _y1k أو y2k _، نظرًا _لطبيعة المُشفِّر النظامية. إذا استُخدم المُشفِّران C1 و C2 في _n1 و _{n2 تكرارًا على} التوالي ، _فإن معدلاتهما تساوي

${\displaystyle {\begin{aligned}~R_{1}&={\frac {n_{1}+n_{2}}{2n_{1}+n_{2}}}\\~R_{2}&={\frac {n_{1}+n_{2}}{n_{1}+2n_{2}}}\end{aligned}}}$

تم بناء جهاز فك التشفير بطريقة مشابهة لجهاز التشفير المذكور أعلاه. يتم توصيل جهازي فك تشفير أساسيين ببعضهما البعض، ولكن على التوالي وليس على التوازي.${\displaystyle \textstyle DEC_{1}}$يعمل جهاز فك التشفير بسرعة منخفضة (أي،${\displaystyle \textstyle R_{1}}$وبالتالي، فهو مخصص لـ${\displaystyle \textstyle C_{1}}$جهاز التشفير، و${\displaystyle \textstyle DEC_{2}}$هو لـ${\displaystyle \textstyle C_{2}}$وبالمثل.${\displaystyle \textstyle DEC_{1}}$وينتج عنه قرار متساهل يتسبب في${\displaystyle \textstyle L_{1}}$التأخير. وينتج هذا التأخير نفسه عن خط التأخير في جهاز التشفير.${\displaystyle \textstyle DEC_{2}}$تسبب عملية 's${\displaystyle \textstyle L_{2}}$تأخير.

يتم هنا استخدام جهاز تداخل مثبت بين جهازي فك التشفير لتشتيت دفعات الأخطاء القادمة من${\displaystyle \textstyle DEC_{1}}$وحدة الإخراج DI هي وحدة فك تشفير وإدخال. تعمل كمفتاح، حيث تعيد توجيه بتات الإدخال إلى${\displaystyle \textstyle DEC_{1}}$في لحظة واحدة وإلى${\displaystyle \textstyle DEC_{2}}$في حالة أخرى. في حالة الإيقاف، فإنه يغذي كليهما${\displaystyle \textstyle y_{1k}}$و${\displaystyle \textstyle y_{2k}}$المدخلات مع بتات الحشو (الأصفار).

لنفترض وجود قناة AWGN بدون ذاكرة ، ولنفترض أنه في التكرار رقم k ، يتلقى جهاز فك التشفير زوجًا من المتغيرات العشوائية:

${\displaystyle {\begin{aligned}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{k}\end{aligned}}}$

أين${\displaystyle \textstyle a_{k}}$و${\displaystyle \textstyle ب_{ك}}$مكونات ضوضاء مستقلة لها نفس التباين${\displaystyle \textstyle \sigma ^{2}}$.${\displaystyle \textstyle Y_{ك}}$هو البت رقم k من${\displaystyle \textstyle y_{k}}$مخرجات جهاز التشفير.

يتم فصل المعلومات الزائدة وإرسالها عبر DI إلى${\displaystyle \textstyle DEC_{1}}$(متى${\displaystyle \textstyle y_{k}=y_{1k}}$) وإلى${\displaystyle \textstyle DEC_{2}}$(متى${\displaystyle \textstyle y_{k}=y_{2k}}$).

${\displaystyle \textstyle DEC_{1}}$ينتج عنه قرار غير حاسم؛ أي:

${\displaystyle \Lambda (d_{k})=\log {\frac {p(d_{k}=1)}{p(d_{k}=0)}}}$

ويسلمها إلى${\displaystyle \textstyle DEC_{2}}$.${\displaystyle \textstyle \Lambda (d_{k})}$يُطلق عليه اسم لوغاريتم نسبة الاحتمال (LLR).${\displaystyle \textstyle p(d_{k}=i),\,i\in \{0,1\}}$الاحتمال اللاحق (APP) لـ${\displaystyle \textstyle d_{k}}$بت البيانات الذي يوضح احتمالية تفسير البيانات المستلمة${\displaystyle \textstyle d_{k}}$قليلاً مثل${\displaystyle \textstyle i}$مع الأخذ في الاعتبار نسبة المسؤولية القانونية ،${\displaystyle \textstyle DEC_{2}}$ينتج عنه قرار حاسم؛ أي بت تم فك تشفيره.

من المعروف أن خوارزمية فيتربي غير قادرة على حساب APP، وبالتالي لا يمكن استخدامها في${\displaystyle \textstyle DEC_{1}}$بدلاً من ذلك، يتم استخدام خوارزمية BCJR معدلة.${\displaystyle \textstyle DEC_{2}}$، خوارزمية فيتربي هي خوارزمية مناسبة.

إلا أن الهيكل الموضح ليس مثالياً، لأن${\displaystyle \textstyle DEC_{1}}$يستخدم جزءًا مناسبًا فقط من المعلومات الزائدة المتاحة. ولتحسين البنية، تُستخدم حلقة تغذية راجعة (انظر الخط المنقط في الشكل).

تُنتج وحدة فك التشفير عددًا صحيحًا لكل بت في تدفق البيانات. يُمثل هذا العدد الصحيح مقياسًا لاحتمالية أن يكون البت 0 أو 1، ويُسمى أيضًا بالبت اللين . يمكن اختيار هذا العدد الصحيح من النطاق [-127، 127]، حيث:

• -127 تعني "بالتأكيد 0"
• -100 تعني "من المرجح جداً أن تكون النتيجة 0"
• الرقم 0 يعني "يمكن أن يكون إما 0 أو 1"
• 100 تعني "من المرجح جداً أن يكون 1"
• 127 تعني "بالتأكيد 1"

وهذا يُدخل جانبًا احتماليًا إلى تدفق البيانات من الواجهة الأمامية، ولكنه ينقل معلومات أكثر عن كل بت من مجرد 0 أو 1.

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

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

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

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

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

الاتصالات السلكية واللاسلكية:

• تُستخدم رموز Turbo على نطاق واسع في معايير الاتصالات الهاتفية المحمولة من الجيل الثالث والرابع ؛ على سبيل المثال، في HSPA و EV-DO و LTE .
• MediaFLO ، نظام تلفزيوني أرضي متنقل من شركة كوالكوم .
• قناة التفاعل لأنظمة الاتصالات عبر الأقمار الصناعية ، مثل DVB-RCS ^{[ 7 ]} و DVB-RCS2 .
• تستخدم مهمات ناسا الحديثة مثل مركبة استطلاع المريخ المدارية رموز التوربو كبديل لرموز تصحيح الخطأ ريد-سولومون - رموز فك التشفير فيتربي .
• يستخدم معيار IEEE 802.16 ( WiMAX )، وهو معيار شبكة حضرية لاسلكية، ترميز الكتلة التوربيني والترميز التوربيني التلافيفي.

من وجهة نظر الذكاء الاصطناعي ، يمكن اعتبار رموز التوربو مثالاً على انتشار الاعتقاد الحلقي في الشبكات البايزية . ^{[ 8 ]}

• خوارزمية BCJR
• الشفرة الالتفافية
• تصحيح الأخطاء الأمامية
• المتداخل
• رمز التحقق من التكافؤ منخفض الكثافة
• رموز الالتفاف المتسلسلة
• فك تشفير القرار المرن
• معادل توربو
• خوارزمية فيتربي

• غويزو، إريكو (مارس 2004). "الاقتراب من الكود المثالي" . مجلة IEEE Spectrum . 41 (3): 36-42 . doi : 10.1109/MSPEC.2004.1270546 . S2CID 21237188. مؤرشف من الأصل في 11 أكتوبر 2009. 
• "رمز UMTS Turbo وتنفيذ فك تشفير فعال مناسب لأجهزة الراديو المعرفة بالبرمجيات" مؤرشف في 20 أكتوبر 2016 في Wayback Machine ( المجلة الدولية لشبكات المعلومات اللاسلكية )
• ماكنزي، دانا (2005). "انطلق إلى أقصى حد" . مجلة نيو ساينتست . 187 (2507): 38-41 .
• "تجاوز الحدود" ، مقالٌ في مجلة ساينس نيوز يتناول تطور ونشأة رموز التوربو
• ندوة دولية حول رموز التوربو
• مكتبة التعديل المشفر ، مكتبة مفتوحة المصدر لمحاكاة رموز التوربو في برنامج ماتلاب
• "معادلة التوربو: المبادئ والنتائج الجديدة" مؤرشفة في 27 فبراير 2009 في Wayback Machine ، وهي مقالة من IEEE Transactions on Communications حول استخدام الرموز الالتفافية جنبًا إلى جنب مع معادلة القناة.
• الصفحة الرئيسية لـ IT++: IT ++ هي مكتبة C++ قوية تدعم على وجه الخصوص رموز Turbo.
• منشورات رموز توربو من تأليف ديفيد ماكاي
• الصفحة الرئيسية لبرنامج AFF3CT (مجموعة أدوات تصحيح الأخطاء السريعة) لمحاكاة رموز التوربو عالية السرعة في البرامج
• كيرويدان، سيلفي؛ بيرو، كلود (2010). "كود توربو" . سكولاربيديا . 5 (4). Scholarpedia.org: 6496. بيب كود : 2010SchpJ...5.6496K . دوى : 10.4249/scholarpedia.6496 .
• تصميم مرجعي لتقنية 3GPP LTE Turbo .
• تقدير أداء معدل الخطأ في البتات (BER) لرمز Turbo في AWGN مؤرشف في 1 فبراير 2019 في Wayback Machine (MatLab).
• الترميز التلافيفي المتسلسل المتوازي: رموز توربو (ماتلاب سيمولينك)