Ağaç Olarak Kod
Önek-serbest bir kod ikili bir ağaca eşlenir: kök kod çözmenin başını temsil eder, sol dallar bit 0'ı temsil eder, sağ dallar bit 1'i temsil eder & yapraklar tam codeword'leri temsil eder.
Geometrik kısıtlama: her yaprak kök-yaprak yolunu sonlandırır. Hiçbir yaprak soyundan gelen bir şeye sahip olamaz (eğer olsaydı, codeword'ü soyundan gelen bir şeyin codeword'ünün ön eki olurdu, önek-serbest özelliğe aykırı).
Bu, Kraft eşitsizliğine geometrik bir yorum verir:
Derinlik d'deki her yaprak toplam ağaç kapasitesinin 2^(−d) fraksiyonunu 'işgal eder'. Derinlik D'deki tam bir ikili ağacın toplam kapasitesi 1'dir. Önek-serbest bir kod çeşitli derinliklerde yapraklar kullanır; Kraft toplamı toplam işgali ölçer.
Kraft toplamı = 1: tam kod (her yol bir yaprakta biter — mükemmel paketleme).
Kraft toplamı < 1: eksik kod (bazı ağaç kapasitesi kullanılmamış — daha fazla sembol eklenebilir).
Kraft toplamı > 1: önek-serbest kodlar için imkansız (bazı yollar bir yaprakı paylaşmak zorunda kalacaktı).
Daha Derin Yapraklar = Daha Uzun Kodlar = Daha Az Kapasite
Derinlik 1'deki bir yaprak ağaç kapasitesinin yarısını kullanır (2^(−1) = 0,5).
Derinlik 3'teki bir yaprak sekizde birini kullanır (2^(−3) = 0,125).
Ağaçta yüksek konuma kısa bir codeword yerleştirmek tüm soyundan gelenlerin kullanılmasını engeller — kısa bir kodu birçok potansiyel daha uzun kod için değiştirirsiniz.
Önek-Serbest Ağaç İnşa Etmek
l = {1, 2, 3, 3, 3} uzunluğuna sahip 5 sembolü düşünün. Kraft toplamı = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Bu 1'i aşıyor: bu uzunluklar önek-serbest bir kodla uyumlu değil. En az bir uzunluk artmalı.
Düzeltme: l_1'i 1'den 2'ye değiştirin. Yeni uzunluklar {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Geçerli ama eksik.
Düzeltme: kalan kapasiteyi kullanmak için uzunlukları ayarlayın. Kraft = 0,875; kalan = 0,125 = 2^(−3): bir daha derinlik-3 yaprak için yer.
Entropi Neden Kod Uzunluğunu Sınırlar
Kraft eşitsizliği kod yapısını kısıtlar (uzunluklar ağaçta sığmalı). Shannon entropisi kod verimliliğini kısıtlar (ortalama uzunluk teorik bir tabanı yeneamez).
Optimal kod uzunlukları. Olasılık p_i olan bir sembol için ideal kod uzunluğu log₂(1/p_i)'dir. Nadir semboller uzun kodlar hak eder; sık semboller kısa kodlar hak eder. Bu, Kraft eşitliğini yansıtır: 2^(−l_i) = p_i ne zaman l_i = log₂(1/p_i).
Ama log₂(1/p_i) nadiren bir tamsayıdır. ⌈log₂(1/p_i)⌉'ye yuvarlamak Huffman uzunluğunu verir, bu da H ≤ L < H + 1'i sağlar.
Geometrik okuma. Her sembolü derinlik l_i'de ikili ağaçta bir nokta olarak çizin. Kraft toplamı toplam yaprak kapsamını ölçer. Entropi ağırlıklı ortalama derinliği ölçer, olasılık tarafından ağırlıklandırılmış. Shannon teoremi: olasılık-ağırlıklı ortalama derinlik ≥ olasılık-ağırlıklı bilgi içeriği.
Entropi Sınırı Doğrulaması
Çalışılmış örnek: {A, B, C, D} sembolleri için p = [1/2, 1/4, 1/8, 1/8].
Optimal uzunluklar: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Bunlar hepsi tamsayılar — mükemmel bir eşleşme. Huffman kodu: A=0, B=10, C=110, D=111.
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 0,5 + 0,5 + 0,375 + 0,375 = 1,75.
H = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75. L = H tam olarak: optimal kod.
Tam Çalışılmış Bir Örnek
Tam boru hattı: verilen olasılıklar, entropisi hesapla, bir kodun sınırı karşıladığını doğrula.
Kaynak: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 bit (yukarıda hesaplandı).
Saf bir blok kodu: 4 sembol → her biri 2 bit → L = 2,0. Entropi üzerinde ek yük: 2,0 − 1,75 = 0,25 bit/sembol = %12,5 atık.
Değişken uzunluklu kod, sabit uzunluklu ile karşılaştırıldığında %12,5 tasarruf sağlar. Büyük mesajlar için bu önemlidir.
İngilizcenin Entropi Hızı. Shannon, yazılı İngilizcenin entropisi 5 bitlik ASCII kodları kullanmasına rağmen karakter başına yaklaşık 1,0 ila 1,3 bit olarak tahmin etti. Bu 4:1 oranı doğal dildeki muazzam yedekliliği yansıtır — yaygın harfler kümelenir, sözcükler tekrar eder, gramer dizileri kısıtlar.
Sıkıştırma Entropiyi Yeneamez
Sıkıştırma oranı: H / (blok kod uzunluğu). Örneğimiz için: 1,75/2,0 = 0,875 — %87,5 verimlilik.
Daha da sıkıştırabilir misiniz? Sadece bağlam kullanarak: eğer sembol çiftlerini veya üçlülerini birlikte kodlarsanız, joint entropi H(X,Y) istatistiksel bağımlılıklar nedeniyle 2·H(X)'ten daha az olabilir. Bu, gürültüsüz kodlama teoreminin n-gramlara uzantısıdır.