ترميز تونستال

في علوم الحاسوب ونظرية المعلومات ، يعتبر ترميز تونستال شكلاً من أشكال ترميز الإنتروبيا المستخدم لضغط البيانات بدون فقدان .

كان ترميز تونستال موضوع أطروحة الدكتوراه التي قدمها برايان باركر تونستال عام 1967، أثناء دراسته في معهد جورجيا للتكنولوجيا. وكان موضوع تلك الأطروحة "توليف رموز الضغط الخالية من الضوضاء" ^{[ 1 ].}

يُعد تصميمها بمثابة مقدمة لتصميم ليمبل-زيف .

على عكس الرموز ذات الطول المتغير ، والتي تشمل ترميز هوفمان وترميز ليمبل-زيف ، فإن ترميز تونستال هو رمز يربط رموز المصدر بعدد ثابت من البتات. ^{[ 2 ]}

تمثل كل من رموز تونستال ورموز ليمبل-زيف الكلمات ذات الطول المتغير بواسطة رموز ذات طول ثابت. ^{[ 3 ]}

على عكس ترميز المجموعة النموذجي ، يقوم ترميز تونستال بتحليل مصدر عشوائي باستخدام كلمات رمزية ذات طول متغير.

يمكن إثبات أنه بالنسبة لقاموس كبير بما فيه الكفاية، يمكن أن يكون عدد البتات لكل حرف مصدر قريبًا بشكل تعسفي من${\displaystyle H(U)}$، إنتروبيا المصدر. ^{[ 4 ]}

تتطلب الخوارزمية كمدخل أبجدية إدخال${\displaystyle {\mathcal {U}}}$بالإضافة إلى توزيع احتمالات لكل كلمة مُدخلة. كما يتطلب الأمر ثابتًا اختياريًا.${\displaystyle C}$وهو الحد الأقصى لحجم القاموس الذي سيتم حسابه. القاموس المعني،${\displaystyle D}$يتم بناء هذه الشبكة على شكل شجرة احتمالات، حيث يرتبط كل ضلع بحرف من الأبجدية المدخلة. وتكون الخوارزمية كالتالي:

D := شجرة من${\displaystyle |{\mathcal {U}}|}$أوراق، واحدة لكل حرف في${\displaystyle {\mathcal {U}}}$. بينما${\displaystyle |D|<C}$: حوّل الورقة الأكثر احتمالاً إلى شجرة باستخدام${\displaystyle |{\mathcal {U}}|}$أوراق.

لنفترض أننا نرغب في ترميز السلسلة "hello, world". ولنفترض أيضًا (بشكل غير واقعي إلى حد ما) أن الأبجدية المدخلة${\displaystyle {\mathcal {U}}}$ تحتوي هذه المجموعة على أحرف من السلسلة النصية "hello, world" فقط، وهي: 'h'، 'e'، 'l'، ','، ' '، 'w'، 'o'، 'r'، 'd'. وبالتالي، يمكننا حساب احتمالية ظهور كل حرف بناءً على ظهوره الإحصائي في السلسلة النصية المدخلة. على سبيل المثال، يظهر الحرف L ثلاث مرات في سلسلة نصية مكونة من 12 حرفًا: احتمالية ظهوره هي${\displaystyle 3 \over 12}$.

نقوم بتهيئة الشجرة، بدءًا بشجرة من${\displaystyle |{\mathcal {U}}|=9}$أوراق الشجر. وبالتالي، ترتبط كل كلمة مباشرةً بحرف من حروف الأبجدية. ويمكن ترميز الكلمات التسع التي نحصل عليها في مخرج ذي حجم ثابت من${\displaystyle \lceil \log _{2}(9)\rceil =4}$أجزاء.

ثم نختار الورقة ذات الاحتمالية الأعلى (هنا،${\displaystyle w_{1}}$)، ثم تحويلها إلى شجرة أخرى من${\displaystyle |{\mathcal {U}}|=9}$نرسم أوراقًا، واحدة لكل حرف. نعيد حساب احتمالات تلك الأوراق. على سبيل المثال، يظهر تسلسل الحرفين L مرة واحدة. إذا علمنا بوجود ثلاث حالات لظهور أحرف متبوعة بالحرف L، فإن الاحتمال الناتج هو${\displaystyle {1 \over 3}\cdot {3 \over 12}={1 \over 12}}$.

نحصل على 17 كلمة، يمكن ترميز كل منها في مخرج ذي حجم ثابت من${\displaystyle \lceil \log _{2}(17)\rceil =5}$أجزاء.

لاحظ أنه يمكننا التكرار أكثر، وزيادة عدد الكلمات بمقدار${\displaystyle |{\mathcal {U}}|-1=8}$في كل مرة.

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

إن اشتراطها لإخراج كتلة ذات طول ثابت يجعلها أقل من Lempel–Ziv ، التي لها تصميم مشابه قائم على القاموس، ولكن مع إخراج كتلة متغيرة الحجم.

هذا مثال على استخدام كود تونستال لقراءة (أو إرسال) أي بيانات مشفرة، مثلاً باستخدام التشفير متعدد الحدود. يساعد هذا المثال تحديدًا في تعديل أساس البيانات من 2 إلى 3 في تدفق البيانات، وبالتالي تجنب إجراءات تعديل الأساس المكلفة. مع تعديل الأساس، نلتزم بشكل خاص بـ "كفاءة" عمليات القراءة، حيث يكون من الناحية المثالية${\textstyle \log _{n}}$تُستخدم البتات بمعدل متوسط ​​لقراءة الشفرة. وهذا يضمن أنه عند استخدام القاعدة الجديدة، والتي من واجبها استخدامها على أفضل وجه${\textstyle \log _{n}}$بما أن عدد البتات لكل رمز لا يؤدي إلى انخفاض في كفاءة الإرسال، وهو ما دفعنا إلى استخدام تعديل الأساس في المقام الأول. وبالتالي، يمكننا استخدام آلية القراءة لتعديل الأساس لنقل البيانات بكفاءة عبر قنوات ذات أساس مختلف. على سبيل المثال، نقل البيانات الثنائية عبر قنوات MLT-3 بكفاءة أعلى مقارنةً برموز التعيين (التي تحتوي على عدد كبير من الرموز غير المستخدمة).

نقرأ في الأساس بيانات ثنائية مشوشة تمامًا، أو ما يُعرف بـ"البيانات الضمنية"، بغرض إرسالها عبر قنوات النظام الثلاثي. انظر إلى العقد الطرفية في شجرة تونستال الثلاثية. كما نلاحظ، ستكون نتيجة القراءة هي أن يكون الرقم الأول هو "B" بنسبة 25%، نظرًا لاحتمالية ضمنية تبلغ 25%، حيث يبلغ طوله 2 عند محاولة القراءة من البيانات الضمنية. لا تُكمل قراءة "B" هذه العملية، ولكن باحتمالية 75%، نقرأ "A" أو "C"، مما يتطلب رمزًا آخر. وبالتالي، فإن كفاءة القراءة هي 2.75 (متوسط ​​طول رمز هوفمان ذي الحجم 7) / 1.75 (متوسط ​​طول رمز تونستال ذي الأساس الثلاثي المكون من رقم واحد أو رقمين).${\textstyle 1.57142857}$وهو ما يتوافق مع المتطلبات، قريب جدًا من${\textstyle \log _{2}3=1.5849625}$وهو ما يُحسب بكفاءة قدرها$99.15$يمكننا بعد ذلك إرسال الرموز باستخدام قنوات الأساس 3 بكفاءة.