متى يمكنك فك التشفير بشكل فريد؟

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

شرط خالي من البادئات

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

مثال رمز خالي من البادئات لـ {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.

تحقق: 0 ليست بادئة لـ 10 أو 110 أو 111. 10 ليست بادئة لـ 110 أو 111 (10 متبوعة بمزيد من البتات تعطي 100... أو 101...، لا يبدأ أي منهما بـ 110 أو 111). الرمز يستوفي المتطلبات.

إجراء فك التشفير: اتبع الشجرة، افرع على كل بتة واردة، أصدر الرمز عند وصولك إلى ورقة، عد إلى الجذر.

عدم مساواة كرافت

لأي رمز ثنائي خالي من البادئات بأطوال كلمات رمزية l_1, l_2, ..., l_n:

Σ 2^(−l_i) ≤ 1

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

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

بالنظر إلى أطوال الرموز، تحقق من كرافت: Σ 2^(−l_i) ≤ 1.

بالنسبة لـ {s1=0, s2=10, s3=110, s4=111}: الأطوال هي 1, 2, 3, 3.

Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓

إنتروبيا شانون

متوسط طول الرمز لرمز الطول المتغير: L = Σ p_i · l_i، حيث p_i هي احتمالية الرمز s_i و l_i هو طول الرمز الخاص به.

كم يمكن أن يصبح L قصيراً؟ إجابة شانون: ليس أقل من إنتروبيا المصدر.

إنتروبيا شانون: H = −Σ p_i · log₂(p_i) (الوحدات: بت/رمز)

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

نظرية الترميز الخالية من الضوضاء

لأي رمز خالي من البادئات، H(source) ≤ L ≤ H(source) + 1.

لا يمكن لأي رمز أن يتغلب على الإنتروبيا. ترميز هوفمان (الفصل التالي) يحقق الحد الأعلى: L < H + 1. لرموز الكتلة على n رموز، يشتد القيد: H ≤ L/n < H + 1/n.

الإنتروبيا هي أيضاً حد الضغط النظري: لا يمكنك ضغط المصدر أقل من H بت لكل رمز بدون فقدان المعلومات.

حساب الإنتروبيا

مثال: 4 رموز بالاحتمالات p = [1/2, 1/4, 1/8, 1/8].

H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)

= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3

= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 بت/رمز

و ترميز هوفمان {0, 10, 110, 111} يحقق L = 1.75 = H بالضبط.

لماذا الإنتروبيا حد أدنى

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

عندما تكون جميع الرموز متساوية الاحتمالية (توزيع موحد)، الإنتروبيا H = log₂(n) لـ n رموز. رمز كتلة بطول log₂(n) بت يحقق H بالضبط. لا يمكن لأي رمز أن يفعل أفضل.

عندما يهيمن رمز واحد (قل، p(A) = 0.99, p(B) = 0.01)، H صغيرة — قريبة من 0. يمكن لرمز الطول المتغير أن يعين A رمزاً قصيراً جداً، ترميز التدفق بكفاءة عالية جداً.

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