الترميز

الترميز





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









إن المسألة المطروحة في الاتصالات هي مسألة
إعادة توليد رسالة مختارة في نقطة ما ثم توليدها (منبع
الإشارة) على نحو كامل أو تقريبي في نقطة أخرى تفصلها عن النقطة الأولى قناة اتصال
ما. ولتحقيق ذلك يبنى نظام الاتصال الرقمي المؤلف من العناصر الأساسية المبينة في
الشكل 1.


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



ترميز المنبع
source
encoding


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


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



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


وتقسم طرق ترميز المنبع التمثيلي إلى ثلاثة أقسام:


أ ـ ترميز شكل الموجة في المجال الزمني: هو
تمثيل رقمي لعينات الإشارة الزمنية. ومن أنواعه تعديل النبضة المرمز pulse code modulation
أو PCM
المستخدم في الشبكات الهاتفية. ويبين الشكل 2 مراحل الانتقال من خرج منبع تمثيلي
إلى سلسلة ثنائية بطريقة تعديل النبضة المرمز.


ب ـ ترميز شكل الموجة في المجال الترددي: هو
تمثيل رقمي للمواصفات الترددية لامتداد زمني محدود من الإشارة.


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


أما اختيار طرق ترميز المنبع المتقطع:


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


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


ويبين الجدولان 1 و2 مثالين لترميز منبع متقطع
بطريقة هوفمان وكيفية اختيار البتات بمعرفة المواصفات الإحصائية للمنبع.









إن متوسط عدد البتات لكل حرف في المثال الأول
يساوي 2.21 بت/حرف. وفي المثال الثاني يساوي 2.70 بت/حرف. أما متوسط عدد البتات في
حال أُغفلت المواصفات الإحصائية لخرج المنبع واستخدم الترميز العادي في كلا
المثالين فيكون مساوياً 3 بت لكل حرف.


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


ترميز الخط
line coding



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


يبين الشكل 3 بعض طرق ترميز الخط، منها:


أ ـ الترميز وحيد القطب unipolar
NRZ: يقابَل البت 1 بكمون
كهربائي عالي A+ ويقابَل البت 0 بكمون كهربائي
يساوي الصفر.


ب ـ الترميز القطبي polar
NRZ: يقابَل البت 1 بكمون كهربائي عالي A+ ويقابل البت 0 بكمون كهربائي
منخفض يساوي A-.


ج ـ الترميز ثنائي القطبية bipolar NRZ:
يقابل البت 1 بكمون كهربائي بصورة متناوبة عالية A+ مرة ثم منخفض A- في المرة التي تليها وهكذا. ويقابل البت 0
بكمون كهربائي يساوي الصفر دوماً.


د ـ ترميز مانشيستر Manchester
NRZ: يُقابل البت 1 بنبضة موجبة تليها نبضة سالبة وزمن كل منها يساوي نصف زمن البت 0 أما البت 0 فتُقابله نبضة
سالبة تليها نبضة موجبة وبالأزمنة نفسها.


ترميز القناة


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


فعلى سبيل المثال الحل البديهي لترميز سلسلة
المعطيات الثنائية هو تكرار كل بت عدداً من المرات. الحل الآخر الأقل بديهية
والأكثر فعالية هو تقسيم المعلومات إلى مجموعات من K بت تؤلف كل منها كلمة ثم مقابلة كل كلمة من هذه الكلمات بكلمة
أخرى من N
بت حيث N
أكبر من K
ويؤلف الفرق K - N الحشو المضاف على نحو معروف، والكلمات الناتجة هي كلمات الرمز.
تقاس نسبة الحشو في المعلومات المرمّزة في هذه الحالة بالنسبة N/K التي تسمى معدل الترميز.


لترميز القناة أنواع منها:


أ ـ طلب إعادة إرسال آلي (automatic repeat request) ARQ: حين يكتشف المستقبِل وجود خطأ في المعطيات يهمل هذه المعطيات
ويطلب إلى المرسل إعادة إرسالها من جديد. تستخدم هذه الطريقة في حال إمكان انتظار
رسالة المستقبِل لمعرفة ما إذا كان قد نجح في الاستقبال، كأن توجد قناة ثانية
لإرسال مثل هذه المعلومات أو أن تكون نسبة الخطأ منخفضة بحيث تجعل إعادة الإرسال
قليلة التواتر. بوجه عام تستخدم هذه الطريقة في الأنظمة المعلوماتية مثل شبكات
الحواسيب.


ب ـ تصحيح الخطأ الأمامي (forward error correction codes) FEC: يُدخل الحشو بطريقةٍ مراقبة بحيث يستطيع المستقبِل عند اكتشاف
الخطأ، أن يصحح عدداً من الأخطاء لمعرفته بالترميز. يستخدم هذا الترميز في حال
تعذر انتظار رسالة المستقبل المؤكدة لنجاحه في الاستقبال، ويحدث ذلك عندما يكون
زمن النقل طويلاً أو عندما تكون نسبة الخطأ عالية فتتسبب في إعادة إرسال متكرر غير
مقبول.


يقسم الترميز الأمامي المصحح للخطأ إلى قسمين
كبيرين رئيسيين: ترميز الكتلة block coding والترميز التلفيفي convolutional coding.


من أنواع ترميز الكتلة: ترميز هامينغ Hamming، وترميز ريد
سولومون Reed-Solomon، و ترميزغولاي Golay، وترميز ريد مولرReed-Mulle وهي تراميز معروفة بأسماء أصحابها. كمثال على ترميز هامينغ Hamming (7,4):


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






عدد أسطر المصفوفة G هو: n=4، وعدد أعمدتها k=7، وI المصفوفة الواحدية.


إذا كانت الكلمة الأصلية من الرسالة معرفة كما
يأتي:



[X_m=[X_m1X_m2X_m3X_m4


فإن الكلمة المرمزة هي:



[G_m=X_mG=[X_m1X_m2X_m3X_m4G_m5G_m6G_M7


وذلك باستخدام الجبر الخطي الثنائي.


نعرف مصفوفة الفحص H=P^TI_K-n حيث
P^T منقول المصفوفة P:










تُعرّف S=rH^T حيث r الكلمة المستقبلة. إذا كان S = 0 لايوجد خطأ، وإذا كان S
≠ 0. يمكِن تصحيح خطأ وحيد، حيث توافق S عموداً
من H ورقم العمود هو رقم
البت الخاطئ. في حال استقبال 1010010 فإن S = 11 وهو العمود الرابع من H أي أن الخطأ في البت الرابع والكلمة الصحيحة هي 1011010.


مبدأ الترميز التلفيفي


يكون عدد المخارج مساوياً N لكل k دخل جديد ويتعلق الخرج بالدخل الجديد وبـ (L-1) k دخل سابق مما يعني أن للترميز ذاكرة. تستثمرهذه الخاصة جيداً في
الحصول على طريقة فك ترميز مصحح للخطأ ذات فعالية عالية تعرف باسم خوارزمية فيتربي
Viterbi. يبين الشكل 4 مخططاً
صندوقياً لمثل هذا الترميز.