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

لأن كود متغير الطول مفيد، يجب على المستقبل الترميز بلا شك. يلخص هامينغ ذلك بکد 4-رمز يفشل في هذا الاختبار، ثم يُدخل الحل: الكودات بدون قواعد مسبقة.

الشروط الكودية بدون قواعد مسبقة

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

مثال على الكود بدون قواعد مسبقة ل {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 بتات/رمز

و يتم تحقيق L = 1.75 = H تمامًا بواسطة كود هوفمان {0, 10, 110, 111}.

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

حدا أدنى للنظير الصوتية ليس مجرد معادلة - يعبّر عن شيء عميق حول المعلومات: لا يمكنك الضغط على ما هو بالفعل غير قابل للتنبؤ.

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

عندما يكون أحرف واحد رئيسية (قولة p(A) = 0.99، p(B) = 0.01)، يكون H صغيرًا - قريب من 0. يمكن أن تخص كود طويل متغير A قصيرًا، مما يؤدي إلى كودة الكائن بشكل فعال.

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