الترميز (نظرية-)

أ ب ت ث ج ح خ د ذ ر ز س ش ص ض ط ظ ع غ ف ق ك ل م ن هـ و ي

الترميز (نظرية-)

ترميز (نظريه)

Coding theory -

الترميز

أسس ترميز المصدر	الترميز الكتلي
نظرية ترميز المصدر	الترميز الدوري cyclic code
الترميز المتراص compact coding	ترميز طلب الإعادة الآلي Automatic-Repeat-Request (ARQ)
أسس ترميز القناة	الترميز التلفيفي convolutional code
قواعد كشف الترميز	الترميز التوربيني turbo code
نظرية ترميز القناة	ترميز فحص الندّية ذو الكثافة المنخفضة Low Density Parity Check Codes (LDPC)
أنواع الترميز

تُعنى نظرية الترميز coding theory عناية خاصة بترميز الاتصالات في حال استخدام قنوات اتصال غير موثوقة؛ ممّا يؤدي إلى احتمال حدوث أخطاء في نقل الرسائل، وهذا ما يتطلب اللجوء إلى الترميز لتقليل تلك الأخطاء وتسهيل كشفها وتصحيحها. ثمة نوعان من الترميز هما: ترميز المصدر source coding وترميز القناة channel coding؛ فالغاية من ترميز المصدر هي ضغط المعطيات data compression بهدف إرسالها أو تخزينها. والهدف من الإرسال هو إرسال المعطيات بأقل وقت ممكن وعلى نحو مستقل عن معدل الإرسال؛ أي استثمار مصدر الزمن استثماراً فعّالاً. أما التخزين فيهدف إلى تخزين المعطيات بأقل حجم ممكن (بأقل ذاكرة)، أي استثمار الذاكرة بأفضل ما يمكن. ويمكن تحقيق الأهداف السابقة بالتخلص من الحشو redundancy في المعطيات باستخدام خوارزميات معينة.

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

أسس ترميز المصدر

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

حيث هي الاحتمال، وتعطى: ، وعناصر أبجدية محددة ، وD سعة الأبجدية وأخذ أساس اللوغاريتم 2 للحصول على وحدة القياس البت.

ولتوضيح هذه المفاهيم: ليكن هناك مصدر عديم الذاكرة يُصدر مجموعة من رموز الأبجدية بالاحتمالات ، تسمى عناصر w بكلمات المصدر source words . وعندئذٍ يمكن طرح السؤال التالي: إذا وجدت الأبجدية ذات رمزاً، فكيف يمكن ترميز كلمات المصدر wi باستخدام رموز من الأبجدية بحيث يكون الترميز ( ترميز المصدر) اقتصادياً قدر الإمكان؟ أي يكون متوسط طول الكلمة المرمزة أقصر ما يمكن، حيث (المعادلة 2):

فعلى سبيل المثال إذا كان المصدر يُصدر الكلمات و و و بالاحتمالات
و و

وبالمقارنة بين الترميزين التاليين:

واضح أن متوسط طول الكلمة المرمزة الأول هو ، 2 bit في حين أن الترميز الثاني ، وهكذا فإن الترميز الأول أكثر اقتصادية من الترميز الثاني، أي ، وعموماً يمكن عدّ الترميز تطبيقاً C من W الى. حيث هي مجموعة من صفوف strings مُحددة من رموز الأبجدية، والرسالة m) message) هي صف واحد محدد من كلمات الترميز، أي المعادلة (3):

وإذا طبق الترميز C على الرسالة m يُحصل على المعادلة (4):

حيث هي كلمات الترميز؛ فعلى سبيل المثال إذا كانت:

و فإن .

عموماً يمكن تصنيف ترميز المصدر إلى أربعة أصناف:

1- شاذ singular .

2- غير شاذnon-singular .

3- وحيد فك الترميز uniquely decodable.

4- لحظي instantaneous .

فالترميز الشاذ ترميز تافه ليس له أي قواعد. أما الترميز غير الشاذ فيحقق المعادلة (5):

ولفك الترميز المعطى بالعلاقة (5) يلزم دوماً وجود فواصل بين الكلمات المرمزة، مثال ذلك ترميز الفاصلة التالي:

يلاحظ هنا وجود الفاصلة (0) في نهاية كل كلمة مرمزة، ولهذا فإنه غير فعّال.

في الترميز الوحيد الفك يمكن الانتقال دوماً من الترميز المعطى بالعلاقة (4) إلى الرسالة المعطاة بالعلاقة (3) باستخدام الخوارزمية المناسبة. مثال ذلك الترميز التالي:

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

ويقال عن الترميز إنه لحظي أو ترميز البادئة prefix إن لم توجد و، بحيث تكون بادئة. أي إذا كان فإن بادئة لـ إذا وجد حيث . واضح أن الترميز اللحظي هو ترميز وحيد فك الترميز، حيث يمكن فكه والوصول إلى الرسالة (3) من الترميز (4) آنياً من دون النظر إلى اللاحق، وهذه خاصية عملية مهمة.

تعتمد نظرية ترميز المصدر على الأسس التالية: متراجحة كرافت Kraft، ومتراجحة ماكميلان Macmillan، ونظرية ترميز المصدر لشانون Shannon.

متراجحة كرافت: إذا كانت أبجدية ذات سعة وW تحوي N كلمة ترميز فإن الشرط اللازم والكافي لوجود ترميز لحظي ذي طول الكلمات هو المعادلة (6):

أو

حيث عدد أطول ذات الطول j

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

متراجحة ماكميلان: إذا كانت أبجدية ذات سعة D وW تحوي N كلمة ترميز فإن الشرط اللازم لوجود ترميز مصدر وحيد الفك طول كلماته هو تحقق المتراجحة (6).

إن فكرة برهان الشرط اللازم هي التحقق من أن كل الرسائل التي تتألف من r كلمة ترميز (أي عدد صحيح موجب)، وطول كل منها j رمزاً وعددها ؛ هي رسائل مختلفة

مثال ذلك: يوجد الترميزان التاليان:

يلاحظ أن الترميز الأول يحقق المتراجحة (6) وهو ترميز لحظي، أي لا توجد أي كلمة ترميز بادئة لكلمة ترميز أخرى، وكل الرسائل في حالة مختلفة؛ في حين الترميز الثاني لا يحقق المتراجحة (6) وهو ترميز غير لحظي حيث هي بادئة لـ، وهناك رسائل متشابهة في حالة ومنها:

تجدر الملاحظة أن متراجحة كرافت تبين في حال تحققها وجود ترميز لحظي؛ ولكن ليس كل ترميز يحقق هذه المتراجحة هو ترميز لحظي، ومثال ذلك الترميز:

نظرية ترميز المصدر

إذا كان هناك مصدر عديم الذاكرة وله الأنتروبية H؛ فإن أي ترميز له وحيد فك الترميز يكون متراصاً compact (متوسط طول كلمة الترميز L أقصر ما يمكن) إذا حقق المتراجحة (7):

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

الترميز المتراص compact coding

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

النقطة الأولى: الترميز المتراص لمصدر بكلمتين و هو:

النقطة الثانية: إذا كان هناك ترميز لحظي ومتراص و فيجب أن يكون طول الكلمة أطول من طول الكلمة أو يساويها أي .

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

اعتماداً على ما سبق اقترح هُفمان Huffman الخوارزمية التالية لترميز المصدر:

1- تُرتب كلمات المصدر بحيث تكون احتمالاتها متناقصة.

2- يجمع آخر احتمالين موافقين لآخر كلمتين.

3- إذا كان عدد الكلمات الباقية يساوي 2 يجري الانتقال إلى الخطوة التالية وإلا العودة إلى الخطوة الثانية.

4- ترميز الكلمتين الباقيتين بـ 0 و1.

5- إضافة 0 و1 وبالترتيب نفسه ( كما هو في الخطوة السابقة) بالنسبة إلى كل جمع احتمالين وباتجاه تناقص الاحتمالات حتى الوصول إلى آخر جمع (أو جموع ).

يمكن إيضاح خوارزمية هُفمان بالمثال التالي: مطلوب ترميز كلمات المصدر التالية: ذات الاحتمالات و على التوالي. يوضح الجدول (1) استخدام الخوارزمية، ففي البداية ترتب الاحتمالات على نحو متناقص (الخطوة1 ). ومن ثم يُجمع أصغر احتمالين ؛ ويجمع الناتج مع ؛ حيث يتم الحصول على ¼، ويجمع الناتج أيضاً مع فيحصل على ، وفي النهاية يُجمع الناتج مع 1/2 فيتم الحصول على 1 (الخطوتان 2 و3).

الجدول ( 1) إجراءات تمييز هُفمان.

تُرمّز الآن الفرعة العليا بـ "0" والسفلى بـ "1" الموافقة للعقدة ، ويستمر الترتيب نفسه حتى الوصول إلى الفرعة ( الخطوتان 4 و5).

بإجراء حسابات بسيطة يُلاحظ أن الترميز السابق يُحقق نظرية ترميز المصدر (العلاقة 7). كما يمكن البرهان بسهولة على أن ترميز "هفمان" ترميز أمثلي ومن مساوئه:

(أ) كلمات الترميز ليست بالطول نفسه.

(ب) يحتاج إلى توزع احتمالي لكلمات المصدر.

(جـ) إن حدوث خطأ في أي بت من كلمات الترميز، سواء في الإرسال أم التخزين، يسبب انتشار الخطأ.

لتفادي مساوئ ترميز "هفمان" اقترح الباحثان لمبل Lempel وزيف Ziv ترميز المصدر الذي يتميز بالطول الثابت وسهولة عملية الترميز وفك الترميز. وللتبسيط سوف يقتصر على المصدر الثنائي (0،1). ويمكن تلخيص خوارزمية " "لمبل – زيف" بالإجرائيات التالية:

1- تتم في البداية عملية تحليل parsing السلسلة المراد ترميزها؛ أي تقسيمها إلى جمل أو عبارات phrases بدءاً من أصغر عبارة (رمز واحد) حتى أكبر جملة ممكنة، وكل جملة تختلف عن الجملة السابقة بآخر رمز.

2- يُخصص موقع لكل جملة بشكل متسلسل كما هو واضح في الجدول (1).

3- تتكّون كلمة الترميز من قسمين؛ الأول هو الرمز (البت) الأخير في الجملة المعنية الذي يميز الجملة من جملة سابقة. أما القسم الثاني فهو موقع الجملة الناتجة بعد حذف الرمز (البت) الأخير.

يلخص الجدول (2) عملية الترميز؛ حيث أخذ عدد المواقع 15 لكون عدد الجمل 15. أما عملية فك الترميز فيمكن استنتاجها ببساطة من الجدول (1).

الجدول (2)

موقع الجُمل		الجُمل	كلمات الترميز
1-	0001	0	0	000
2-	0010	1	1	0000
3-	0011	00	0	0001
4-	0100	001	1	0011
5-	0101	10	0	0010
6-	0110	000	0	0011
7-	0111	101	1	0101
8-	1000	0000	0	0110
9-	1001	01	1	0001
10-	1010	010	0	1001
11-	1011	00001	1	1000
12-	1100	100	0	0101
13-	1101	0001	1	0110
15-	1110	0100	0	1010
15-	1111	0010	0	0100

طُرح ترميز هُفمان عام 1952 وله العديد من الإصدارات، وتستخدم إصداراته المختلفة في ضغط الصورة في تقنية مجموعة خبراء التصوير المشتركة Joint Photographic Experts Group (JPEG)، ذات الإصدارات JPEG 2000 وJPEG++. وكذلك في ضغط الصوت والفيديو في تقنية مجموعة خبراء الأفلام Motion Picture Experts Group (MPEG)، ذات الإصدارات MPEG 1 وMPEG2 وMPEG3 وMPEG4. أما ترميز "لمبل – زيف" فيستخدم أساساً في ضغط الملفات النصية، وأهم إصداراته LZ77 و LZSS وLZ78 و LZW.

أسس ترميز القناة

يوضح الشكل (1) وصلة اتصالات رقمية (نموذج) مناسبة لمعالجة موضوع ترميز القناة؛ حيث يرمز الحرف U إلى كلمة ترميز المصدر، وv إلى الكلمة المرمزة، وn إلى شعاع الضجيج الجمعي الغاوصي gaussian بسبب القناة، وr إلى الشعاع المستقبل، و إلى كلمة المصدر المقدرة.

الشكل (1) نموذج لوصلة اتصالات رقمية.

فعلى فرض أن القناة عديمة الذاكرة، أي خرجها مستقل وتوزعها منتظم؛ عند ذلك يمكن توصيف القناة بالاحتمال الشرطي . ويكون التعامل هنا مع أبسط أنواع القنوات العديمة الذاكرة، وهي القناة الاثنانية المتناظرة (BSC) Binary Symmetric Channel المبينة بالشكل (2). يرمز عادة إلى عدد بتات (خانات) كلمة المصدر بـ وإلى عدد بتات كلمة الترميز بـ ، أي إن عدد بتات الحشو هو n-k. تُسمى النسبة بمعدل الترميز code rate.

الشكل (2) نموذج القناة الاثنانية المتناظرة.

أما أبسط أنواع تراميز القناة فهي:

1- ترميز فحص الندّية ببت واحد single parity check code. حيث؛ و و. تجدر الملاحظة هنا أن كل الحسابات تتم في نظام العد الاثناني binary ما لم يذكر خلاف ذلك. وكمثال على هذا الترميز عند k=2 و n=3 هو:

2- ترميز التكرار repetition: يتألف هذا الترميز من كلمتين؛ فالمحرف "0" يوافق الكلمة والواحد"1" يوافق الكلمة .

فإذا كانت أيُّ تركيبة جمع من كلمات الترميز تطابق كلمة ترميز أخرى؛ يسمى هذا الترميز الترميز الخطي، ويرمز إليه بـ . واضح أن الترميزين السابقين ترميزان خطّيان. وسوف يتم التعامل هنا فقط مع الترميز الخطي؛ لكونه واسع الانتشار، ولاسيما في التطبيقات العملية لأدائه الجيد وسهولة إنجازه.

يسمى عدد العناصر (الخانات) غير الصفرية في كلمة الترميز (أي كلمة ترميز) v بوزن "هامينغ" Hamming weight، أي المعادلة (8):

(8)

إذا كان للشعاعين ، b عدد الخانات (البتات) نفسه؛ فإن عدد مواقع الخلاف بين الشعاعين يسمى بمسافة "هامينغ" Hamming distance أي (المعادلة 9):

من أهم معاملات الترميز الخطي هو المسافة الصغرى للترميز، والتي تعرف بالعلاقة (10):

حيث: ترميز خطي.

ليكن هناك الترميز C، وبفرض أنه تمَّ إرسال كلمة الترميز واستقبال الشعاع حيث e شعاع الخطأ بسبب القناة (ضجيج القناة، التداخل، التشويش.....)، يمكن عندئذٍ تصحيح الخطأ في الكلمة المستقبلة r، إذا كانت المسافة بينها وبين أي كلمة ترميز في C تحقق العلاقة (11):

فعلى سبيل المثال يبين الشكل (3) كلمتي ترميز أو b، والمسافة الصغرى بينهما هي و؛ فإذا كان ؛ فإنه يمكن تصحيح الخطأ في كلا الترميزين، أما إذا كانت فإنه يمكن كشف الخطأ في الترميز ذي ، وارتكاب خطأ في كشف الترميز ذي . مما سبق يلاحظ أن الترميز ذا المسافة الصغرى d يستطيع تصحيح الأخطاء ( أكبر عدد صحيح أقل أو يساوي ).

الشكل (3) مسافات هامينغ.

قواعد كشف الترميز

المهام الأساسية في استخدام ترميز القناة؛ هي أن يكون احتمال الخطأ في كشف كلمة الترميز أصغر ما يمكن. بفرض تمَّ إرسال كلمة الترميز وتمَّ استقبال الشعاع r، وعلى أساسه تمَّ تقدير الكلمة المرسلة بـ ؛ فإن احتمال الخطأ يكون كما في المعادلة (12):

وللحصول يجب أن يكون لكون P(r)مستقلاً عن قاعدة الكشف، وهذا يكافئ أن يكون اختيار الكلمة التي تحقق أعظمية أي على كل قيم r. تسمى هذه القاعدة احتمال اللاحق الأعظمي Maximum A Posteriori Probability (MAP)؛ غير أنه يلزم لاستخدام القاعدة السابقة معرفة التوزع الاحتمالي السابق a priori لـ، وهذا يبرر استخدام القاعدة التالية لكشف الترميز، وتسمى قاعدة الأرجحية العظمى Maximum Likelihood (ML)، أي المعادلة (13):

ومعلوم أن:

وعند استخدام أي فإن تكون عُظمى عندما تكون d صغرى (أي مسافة هامينغ صغرى).

في كشف ترميز القناة يوجد معياران لاتخاذ القرار؛ الأول اتخاذ القرار الصلد hard والثاني القرار المرن soft. ولتوضيح ذلك؛ لتكن هناك الأبجدية وقناة يؤثر فيها ضجيج أبيض غاوصي؛ عند ذلك فإن للقيمة المستقبلة ri التوزع الاحتمالي الشرطي التالي (المعادلة 14):

يعتمد اتخاذ القرار الصلد على تحديد العتبة الواقعة عند تقاطع التوزعين التاليين: و أما اتخاذ القرار المرن فيعتمد على لوغارتم الأرجحية العظمى maximum Likelihood Ratio (LLR) (المعادلة 15):

وكذلك على sn(LLR)، القيمة LLR تسمى معلومات الوثوقية.

نظرية ترميز القناة

لكل عدد حقيقي ولكل مُعدل ترميز أصغر من سعة القناة C؛ يوجد ترميز طوله n و احتمال خطأ كلمة الترميز فيه بعد الكشف أقل من بشرط أن يكون طول الترميز n كبيراً بما فيه الكفاية.

حيث: سعة القناة هي القيمة العظمى للمعلومات المتبادلة بين دخل القناة وخرجها وتساوي (المعادلة 16):

أنتروبية X وتقيس الغموض فيها، و هي الغموض في X بعد معرفة Y، أي (المعادلة 17):

واحتمال الخطأ في كلمة الترميز (المعادلة 18)

حيث e عدد الأخطاء الممكن تصحيحها.

تبين النظرية السابقة وجود ترميز موثوق، ولكنها لا تعطي الطريقة للحصول على ذلك الترميز، ومن ثمّ فهي نظرية وجود existence.

أنواع الترميز

يمكن تقسيم أنواع التراميز (تراميز القناة) بحسب ظهورها الزمني بحسب ما يلي: الترميز الكتلي block codes، والترميز التلفيفي convolutional، ترميز الكشف العودي iteratively decoded codes، الترميز الفضائي الزمني space time coding. وللتبسيط سوف يكون التعامل هنا مع التراميز في حقل غالواGalois Field GF(2).

الترميز الكتلي

تقسم سلسلة المعلومات في الترميز الكتلي إلى كتل رسائل، طول كل منها k بتاً، ويُرمز إلى كل رسالة بالحرف u. يقوم المرمز encoder بإضافة رموز حشو، بهدف رفع وثوقية الإرسال لكل رسالة u للحصول على كلمة الترميز ذات الطول . تشكل مجموعة كلمات الترميز الترميز الكتلي حيث لكل رسالة كلمة ترميز. وهكذا يوجد رسالة يقابلها كلمة ترميز. يمكن عدّ كلمات الترميز فضاءً جزئياً بـ بُعداً من الفضاء الشعاعي ذي بُعداً؛ أي يلزم إيجاد كلمة ترميز مستقلة خطياً حيث كل كلمة ترميز هي تركيبة خطية من تلك الكلمات، أي (المعادلة 19):

حيث:

وللتبسيط يمكن وضع كلمات الترميز المستقلة في المصفوفة ، أي:

فإذا كانت الكلمة المراد ترميزها فإن كلمة الترميز الموافقة تكون . وهكذا يمكن ببساطة توليد الترميز ، ولهذا السبب سُميت المصفوفة بمصفوفة التوليد generator matrix. وللتفريق (فصل) بين رموز المعلومات ورموز الحشو يمكن وضع المصفوفة بالشكل التالي حيث مصفوفة واحدية .

عُلم من جبر المصفوفات أنه لأي مصفوفة ذات سطراً مستقلاً توجد مصفوفة ذات سطراً مستقلاً خطياً؛ حيث أيُّ شعاع من فضاء الأسطر للمصفوفة G يكون متعامداً مع أسطر المصفوفة H، وأيُّ شعاع مُعامد لأسطر المصفوفة H يكون من فضاء أسطر المصفوفة G. هذا يعني (المعادلة 20)

عند إرسال الشعاع عبر القناة فإن خرج القناة يكون الشعاع حيث هو شعاع الخطأ المرافق للرسالة. وباستخدام المعادلة (20) تكون (المعادلة 21):

يسمى العارض أو المتلازمة syndrome ويرمز إليه بالحرف S. واضح من (21) أنه إذا كان هناك فإنه لا يوجد أيُّ خطأ في الإرسال، أما إذا كان فيوجد خطأ، أي هناك وجود خطأ في الإرسال. أما تصحيح الخطأ فيتم باستخدام قاعدة المسافة الصغرى "لهامينغ" والمكافئة لقاعدة الأرجحية العظمى ML وذلك للقناة BSC. ويمكن تقليل التعقيد لدرجة كبيرة باستخدام المتلازمة S.

عند تصميم الترميز الكتلي يجب أن يؤخذ بالحسبان ما يلي: أن تكون أسطر المصفوفة G مستقلة خطياً، وأن تكون الأسطر المستقلة في G تحقّق مسافة هامينغ الأمثلية؛ أي يجب أن تكون المسافة الصغرى أعظمية. من أهم التراميز الكتلية هو ترميز هامينغ الذي تكون فيه المصفوفتان G وH على النحو التالي:

مثال: بفرض تم إرسال واستقبال وشعاع الخطأ فإن

ببساطة تبين أن مشتركة في كلِّ العلاقات ومن ثمَّ الخطأ فيها، فينتج . عموماً عند تصحيح الخطأ بالحالة العامة يجب استخدام مسافة هامينغ الصغرى.

من أهم التراميز الكتلية ترميز ريد- مولر Reed-Muller وترميز غولاي Golay وترميز الجداء product .

الترميز الدوري cyclic code

يسمى الترميز ترميزاً دورياً إذا كانت كلُّ إزاحة لأيِّ شعاع ترميزاً في C هو أيضاً شعاع ترميز في C. أي إذا كان الشعاع ترميزاً دورياً فإن الشعاع
أيضاً ترميز دوري. يستخدم كثير الحدود في تمثيل الشعاع الدوري (كلمة الترميز) أي .

هنا أيضاً سوف يتعامل مع الحقل GF(2). في الترميز الدوري يستخدم كثير حدود التوليد generator polynomial بدلاً من مصفوفة التوليد G، وأهم مواصفات كثير حدود التوليد هي:

- ذو الدرجة الصغرى في الترميز .

- معامل حده الأصغري يساوي الواحد وله الشكل كما في المعادلة (22):

- أيّ كثير حدود ترميز يجب أن يكون من مضاريب .

- درجة كثير الحدود هي .

- كثير حدود التوليد هو أحد عوامل factor .

بفرض الرسالة المراد ترميزها؛ عند ذلك فإن كلمة الترميز تكون

فإذا كان هناكفإنه يمكن اختيار ، وبفرض أن الرسالة هي: أي فإن كلمة الترميز تكون:

عملياً يفضل الفصل بين رموز المعلومات ورموز الحشو؛ لذلك سوف يتم ضرب بـ، ومن ثم التقسيم على ، ومن ثم يُحصل على المعادلة (23):

وهكذا فإن خوارزمية الترميز تكون كما يلي:

- إجراء الجداء .

- الحصول على الباقي (وهي رموز التحكم "الحشو") بتقسيم على .

- جمع مع للحصول على كثير الحدود

مثال ذلك: بفرض و فإن الباقي من

ومنه:

بما أن هو أحد عوامل فإن

حيث

يُسمى كثير الحدود بكثير حدود فحص الندّية parity check. وبتقسيم كثير الحدود المستقبل على يتم الحصول على الباقي، وهو كثير حدود عارض (السندروم)، أي (المعادلة 24):

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

نظراً للبينة الرياضية الجيدة في الترميز الدوري هناك العديد من طرق كشف الخطأ وتصحيحه ومعظمها تعتمد على الطرق الجبرية. من أهم خوارزميات كشف الخطأ وتصحيحه هي: خوارزمية برلكامب - ماسي Berlekamp -Massey وخوارزمية إقليدس وخوارزمية الأكثرية majority. من أهم التراميز الدورية هي ترميز ريد - سولومون Reed- Solomon وترميز BCH.

ترميز طلب الإعادة الآلي Automatic-Repeat-Request (ARQ)

هناك ثلاثة أنواع من هذا الترميز؛ الأول: ARQ وقوف -انتظار stop- and -wait، الثاني: ARQ بالعودة إلى (go- back – N) N، والثالث ARQ إعادة انتقائية selective repeat. في ARQ وقوف - انتظار يُرسل المرسل كلمة الترميز (أو الطرد) إلى المستقبل، وينتظر التوكيد Acknowledgment (ACK) بتسلّمها تسلّم إيجابي أو تسلّم سلبي Negative Acknowledgment (NAK). إذا تم استقبال ACK يقوم المرسل بإرسال الكلمة التالية، أما إذا استقبل NAK (وجود خطأ) فإن المرسل يُعيد إرسال الكلمة السابقة مرة أُخرى. من أهم معاملات نظم ARQ هو فعالية\كفاءة التدفق throughput efficiency أو اختصاراً التدفق الذي يُعرف بالشكل التالي: نسبة متوسط عدد أرقام المعلومات التي تُقبل بنجاح من قِبل المستقبل في وحدة الزمن؛ إلى العدد الكلي للأرقام التي يمكن أن ترسل في وحدة الزمن؛ ففي ARQ وقوف - انتظار فإن التدفق يمكن ببساطة إيجاده، وهو (المعادلة 25):

حيث احتمال الشعاع المستقبل لا يحوي خطأ، احتمال الشعاع المستقبل يحوي خطأ غير قابل للكشف، و الزمن المهمل من نهاية إرسال كلمة ترميز إلى بداية إرسال الكلمة اللاحقة، وr معدل الإرسال.

في نظام ARQ بالعودة إلـى N يقوم المرسل بإرسال كلمة الترميز الى المستقبل باستمرار من دون توقف. والمستقبل يُرسل ACK باستمرار، في حال الاستقبال السليم. وإذا كان الاستقبال غير سليم (وجود خطأ) فإن المستقبل يرسل NAK إلى المرسل الذي يعود إلى كلمة الترميز (رقم N ) التي حصل فيها الخطأ، ومن ثم يعيد إرسالها مع كل كلمات الترميز التي تليها. والتدفق هنا يمكن استنتاجه ببساطة وهو (المعادلة 26):

حيث ، وهو احتمال قبول كلمة الترميز من قِبل المستقبل.

في نظام ARQ ذي الإعادة الانتقائية يقوم المرسل بإرسال كلمات الترميز على نحو مستمر من دون توقف، وعند استقبال NAK يعيد المرسل إرساله للكلمة التي حصل بها الخطأ فقط. والتدفق هنا ببساطة هو .

الترميز التلفيفي convolutional code

يوجد نوعان من الترميز التلفيفي: الأول الترميز اللاعودي وغير المنتظم Nonrecursive Nonsystematic Codes (NNC)، والثاني العودي والمنتظم recursive systematic. الشكل (4) يوضح الترميز الأول.

الشكل (4) الترميز التلفيفي.

من الشكل يُلاحظ أن الخرج هو (المعادلة 27):

والحالة هي (المعادلة 28):

باستخدام التحويل تنتج المعادلة (29)

يكون هناك (المعادلة 30):

وكثيرا حدود التوليد (المعادلة 31)

يوصّف الترميز التلفيفي باستخدام التمثيل التشابكي trellis المبين بالشكل (5). الذي يتألف من الحالات (العلاقة 29) والفرعات ؛ حيث يتم الانتقال من الحالة إلى الحالة خلال دخل بت واحد.

الشكل (5) المخطط التشابكي.

واضح أن معدل الترميز في المرمز (الشكل 4) هو .

مجموعة كلمات الترميز نفسها الصادرة من المرمز (الشكل 4) يمكن الحصول عليها باستخدام الترميز العودي المنتظم Recursive Systematic Codes (RSC)، وذلك بتقسيم كثيري حدود التوليد (العلاقة 32) على ، أي (المعادلة 32):

وهكذا يكون (المعادلة 33):

وبمعالجة بسيطة للعلاقة السابقة يمكن الحصول على الشكل التالي (الشكل6).

الشكل (6) المرمز العودي المنتظم.

يتم كشف الترميز التلفيفي عادة عن طريق خوارزمية فيتربي Viterbi التي تعتمد على البرمجة الديناميكية وقاعدة الأرجحية العظمى؛ أي يجب إيجاد القيمة العظمى لـ، حيث كل من r وu سلسلة بطول رمزاً. بفرض الضجيج "غاوصي" فإن الوصول إلى القيمة العظمى لـ يكافئ الوصول إلى القيمة الصغرى كما في المعادلة (34):

حيث n عدد البتات بالفرعة، في الشكل ( 4) وجد ، وهكذا فإن قياس الفرعة branch metric يكون (المعادلة 35):

وقياس الممر path هو (المعادلة 36):

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

الترميز التوربيني turbo code

يُعد الترميز التوربيني من أهم أنواع التراميز، وهو قريب من حدود شانون (-1,6 dB) بمقدار (0.5 dB)، ويعتمد أساساً على فكرتين:

الأولى: المرمز يعطي ترميزاً ذا خواص قريبة من العشوائية، حيث هذه الخاصة تحسّن أداء الترميز.

والثانية: كاشف الترميز يعتمد على القرار المرن soft وتكرار الإرجاعية iterative، الشكل (7) يوضح المرمز والشكل (8) يوضح كاشف الترميز، وظيفة المشذر interleaver في كلا الشكلين هي كسر الترابط decorrelation.

الشكل (7) المرمز التوربيني.

(-1,6 dB) (-1،6 dB)

الشكل (8) كاشف الترميز التوربيني.

يتألف المرمز التوربيني من مرمزين RSC، مُعدل كل منها 1/2، والمعدل الكلي للمرمز هو 1/3. يُفترض تتابعية المعلومات مستقلة وذات توزع احتمالي متماثل identical ومنتظم، وأن الضجيج هو غاوصي جمعي.Additive White Gaussian Noise (AWGN)

يوضح الشكل (8) كاشف الترميز التوربيني، حيث يستخدم كلا كاشفي الترميز خوارزمية maximum a posteriori (MAP). يستخدم كاشف الترميز الأول (معلومات) و (الحشو) لتوليد خرج مرن soft (يعطي وثوقية البت وليس قيمة البت)، وبعد تشذيره (توريقه) interleaving يستخدم لتحسين تقدير الاحتمالات السابقة p (u)) a priori) لتتابعية المعلومات، وذلك من أجل كاشف الترميز الثاني. كاشف الترميز الثاني يستخدم بعد التشذير و (حشو) لتوليد خرج مرن الذي يستخدم لتحسين تقدير الاحتمالات السابقة لتتابعية المعلومات، وذلك عن دخل المرمز الأول. وهكذا تستمر عمليات العودة لفترة معينة، وكلما كانت الفترة أكبر كان أداء كاشف الترميز أفضل، حيث يصل تكرار العودية إلى عشرات المرات. إضافة إلى ذلك كلما كان حجم المشذر أكبر كان الأداء أفضل، حيث قد يصل حجم المشذر إلى عشرات الآلاف.

ترميز فحص الندّية ذو الكثافة المنخفضة Low Density Parity Check Codes (LDPC)

الـ LDPC هو ترميز كتلي ذو مصفوفة فحص الندية قليلة الوحدان sparse، أي عدد الوحدان في كل سطر وكل عمود قليل مقارنة بأبعاد المصفوفة. وأهم ما يميز هذه المصفوفة هو:

1- عدد الوحدان في كل سطر هو

2- عدد الوحدان في كل عمود هو

3- لا يوجد عمودان يتقاطعان مع أكثر من سطرين يحويان "1" في موقعي السطرين.

4- كل من و صغيرة مقارنة بأبعاد مصفوفة فحص الندية H.

كثافة الترميز هي . إذا كانت كلمة الترميز فإن، أي يوجد معادلة خطية مستقلة، وكل معادلة تحوي من ، وكل تظهر مرة واحدة في المعادلات. وبالأخذ في الخاصية (3) فإن أيّ زوج لا يظهر إلا مرة واحدة في علاقات فحص الندية على الأغلب.

يمكن تمثيل معادلات فحص الندية باستخدام مخطط تنر Tanner الذي يتألف من عقدة متحول variable nodes (n – عدد بتات كلمة الترميز) و عقدة فحص check nodes ( - عدد معادلات فحص الندية). كل عقدة فحص موصولة بعدد من عُقد المتحول الموجودة في معادلة فحص الندية، وكل عقدة فحص تقابل معادلة فحص الندية.

يعتمد كشف الترميز على خوارزمية تكرارية تُسمى تمرير الرسالة message passing، ويمكن تلخيص الخوارزمية بما يلي: تقوم كل عقدة متحول باستقبال خرج القناة المرن (معلومات مرنة عن وثوقية البت). ومن ثم اعتماداً على القيمة المستقبلة تقوم عقدة المتحول بحساب احتمال أن القيمة هي "1"، ومن ثم تقوم كل عقدة بتسليم احتمال الواحد إلى كل عقدة فحص مرتبطة بها. كل عقدة فحص تستقبل الاحتمالات من عقد المتحولات المختلفة المتصلة بها، واعتماداً على تلك الاحتمالات ومعادلات فحص الندية عند تلك العقدة، تقوم العقدة بتقدير الاحتمالات وترسلها إلى عقد المتحولات الموافقة لها.تُحدّث هذه الاحتمالات عند عُقد المتحول (المتحولات)، وهكذا تتم التكرارية حتى اتخاذ القرار النهائي.

يُسمى الترميز السابق بترميز LDPC المنتظم regular. أما الترميز LDPC غير المنتظم irregular فهو الحالة العامة، حيث عدد الوحدان في الأسطر والأعمدة متغير. تجدر الإشارة إلى أن ترميز LDPC قريب من حدود شانون بمقدار 0,3dB في القنوات الغاوصية.

عند استخدام الترميز المناسب فإن ربح الترميز يصل حتى 8dB عند احتمال خطأ البت ، أي المسافة بين منحني الأداء من دون ترميز وبوجود ترميز عند هو 8dB. أكثر أنواع الترميز فعّالة وبالتسلسل المتصاعد هي: الكتلي والتلفيفي والتوربيني والـ LDPC.