Kaynak → Kanal: İki Aşamalı Kodlama
Hamming'in 10. Bölümü, bilgiyi taşıyan her sisteme uygulanan Shannon'ın haberleşme modeli ile başlar: telefon görüşmeleri, radyo, sabit diskler, DNA replikasyonu, bilgisayar belleği.
İki Aşamalı Mimari
Aşama 1: Kaynak kodlaması (sıkıştırma). Kaynak mesajını kompakt bir gösterime dönüştürün. Amaç: kaynağa özgü fazlalığı kaldırmak. Morse kodu bunu yapar: yaygın harfler kısa kodlar alır, nadir harfler uzun kodlar alır.
Aşama 2: Kanal kodlaması (hata koruması). Kanalın gürültü özelliklerine uyarlanmış kontrollü fazlalık ekleyin. Gürültülü bir telefon hattı, bir fiber optik kabloya göre daha fazla fazlalığa ihtiyaç duyar. İki aşama ayrıştırılır: her birini kendi görevi için bağımsız olarak optimize edin.
İki aşama arasındaki ortak arabirim — standartlaştırılmış bir bit akışı — herhangi bir kaynağın herhangi bir kanalla eşleşebileceği anlamına gelir. Bu modülarite Shannon'ın temel mimari anlayışıdır.
Depolama bir haberleşmedir. Hamming, bir mesajı mekan boyunca göndermek (iletim) ve onu zaman boyunca göndermek (depolama) aynı modeli kullandığını belirtir. Yedek sürücü, zamanda gürültülü bir kanaldır.
Gürültünün Rolü
Shannon'ın modeli radikal bir varsayım yapar: gürültü kaçınılmazdır. Her kanal, her depolama ortamı, her anahtarlama devresi hata olasılığı getirir. Soru 'gürültüyü nasıl ortadan kaldırırız?' değil, 'gürültüye rağmen orijinal mesajı nasıl kurtarırız?'
Bu, gürültünün bir tamamlayıcı olarak girdiği klasik fizikle (belirsizlik ilkesi) çelişir. Shannon, gürültüyü temel koşul olarak ele alır — tüm teori bundan inşa edilir.
Şimdilik, Bölüm 10 sessiz duruma odaklanır: hatasız kaynak kodlaması. Kanal kodlama problemi (hata düzeltme) sonraki bölümleri bekler.
Ne Zaman Benzersiz Şekilde Çözebilirsiniz?
Değişken uzunluklu bir kodun yararlı olması için, alıcı bir bit akışını belirsiz olmadan çözmesi gerekir. Hamming, bu testi başarısız olan 4 simge kodlu ile gösterir, sonra düzeltmeyi sunur: ön ek içermeyen kodlar.
Ön Ek İçermeyen Koşul
Bir kod ön ek içermeyen (veya anlık) ise hiçbir kod kelimesi başka bir kod kelimesinin öneki değildir. Alınan bir bit akışı göz önüne alındığında, çözülme ağacında bir yaprağa ulaştığınız anda bir sembolün bittiğini bilirsiniz — geleceği okuma gerekli değildir.
Örnek ön ek içermeyen kod {s1, s2, s3, s4} için: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Doğrulayın: 0, 10, 110 veya 111'in ön eki değildir. 10, 110 veya 111'in ön eki değildir (10'un ardından daha fazla bit gelmesi 100... veya 101... verir, hiçbiri 110 veya 111 ile başlamaz). Kod nitelendirilebilir.
Çözülme prosedürü: ağacı izleyin, gelen her bite daya açılır, yaprağa çarptığınız zaman sembolü yayınlayın, köke dönün.
Kraft Eşitsizliği
l_1, l_2, ..., l_n kod kelimesi uzunluklarına sahip herhangi bir ön ek içermeyen ikili kod için:
Σ 2^(−l_i) ≤ 1
Eşitlik, kod tam (yapraklar açık olmayan tam ikili ağacı döşer) olduğunda geçerlidir. Bu gerekli bir koşuldur: hiçbir ön ek içermeyen kod bunu ihlal edemez. Tersine, Kraft eşitsizliğini karşılayan herhangi bir uzunluk seti için, ön ek içermeyen bir kod mevcuttur.
Kraft Eşitsizliğini Uygulama
Verilen kod uzunlukları, Kraft'ı doğrulayın: Σ 2^(−l_i) ≤ 1.
{s1=0, s2=10, s3=110, s4=111} için: uzunluklar 1, 2, 3, 3'tür.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Shannon Entropisi
Değişken uzunluklu bir kodun ortalama kod uzunluğu: L = Σ p_i · l_i, burada p_i, s_i sembolünün olasılığı ve l_i kod uzunluğudur.
L ne kadar kısa olabilir? Shannon'ın cevabı: kaynak entropisinin altında değil.
Shannon entropisi: H = −Σ p_i · log₂(p_i) (birim: bit/sembol)
Entropi, sembol başına ortalama bilgiyi ölçer. Yüksek entropi, sembollerin kabaca eşit derecede olası olduğu anlamına gelir (maksimum öngörülemezlik). Düşük entropi, bazı sembollerin hakim olduğu anlamına gelir (yüksek öngörülebilirlik, daha sıkıştırılabilir).
Sessiz Kodlama Teoremi
Herhangi bir ön ek içermeyen kod için, H(kaynak) ≤ L ≤ H(kaynak) + 1.
Hiçbir kod entropiyi yenebilir. Huffman kodlaması (sonraki bölüm) üst sınırı başarır: L < H + 1. n sembol üzerindeki blok kodları için, sınır sıkılaşır: H ≤ L/n < H + 1/n.
Entropi ayrıca teorik sıkıştırma sınırıdır: bilgi kaybetmeden bir kaynağı sembol başına H bitinin altına sıkıştıramazsınız.
Entropiyi Hesaplama
Örnek: p = [1/2, 1/4, 1/8, 1/8] olasılıklı 4 sembol.
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 bit/sembol
Ve Huffman kodu {0, 10, 110, 111}, L = 1.75 = H'yi tam olarak başarır.
Entropi Neden Alt Sınırdır
Sessiz kodlama teoreminin alt sınırı sadece bir formül değildir — bilgi hakkında derin bir şey yansıtır: zaten maksimum derecede öngörülemez olanı sıkıştıramazsınız.
Tüm semboller eşit derecede olası olduğunda (düzgün dağılım), n sembol için entropi H = log₂(n). log₂(n) bit uzunluğundaki bir blok kodu tam olarak H'yi başarır. Hiçbir kod daha iyi yapamaz.
Bir sembol hakim olduğunda (diyelim, p(A) = 0.99, p(B) = 0.01), H küçüktür — 0'a yakın. Değişken uzunluklu bir kod, A'ya çok kısa bir kod atayabilir, akışı çok verimli bir şekilde kodlar.
Pratik sonuç: büyük sıkıştırma kazançları yalnızca sembol olasılıkları önemli ölçüde farklı olduğunda vardır. Kaynak zaten 'üniform' ise (rastgele görünen), Huffman kodlaması hiçbir şey kazanamaz.