Shannon Bilgiyi Ne Anladı
Shannon, bilgiyi şaşırtmayı ölçerek tanımladı. P(0) = p olan bir mesaj taşıyabilir:
I = −log₂(p) bayt
Bir olay (p = 1) 0 bayt taşır - şaşırtıcı değil, bilgi yok. Bir nadir olay (p = 1/1024) 10 bayt taşır.
Hamming, hemen sorunu işaret ediyor: bu, bir kavramı tanımlamaya yönelik bir formül değil, bir miktarı ölçmek için bir formül. Bu, makineli şaşırtmayı, insan anlamını ölçmez. Bir sorunun cevabını zaten bilen bir öğrenci, cevaptan 0 bayt alır - diğer insanlar için ne kadar önemli olursa olsun.
Formül, telefon sistemleri, radyo, bilgisayarlar için iyi uygulanır. İnsan iletişim kuramı, biyoloji veya anlam için iyi uygulanmaz. Hamming'in tercih ettiği ad: 'İletişim Kuramı' değil, 'Bilgi Kuramı.'
Entropi
q sembolden oluşan bir alfabe ile p₁, p₂, ..., p_q olasılıkları, her sembolün ortalaması bilgi miktarı entropi olarak hesaplanır:
H = −Σᵢ pᵢ log₂(pᵢ)
H, olasılıklar eşit olduğunda en yüksek değer alır: H_max = log₂(q) bayt. Herhangi bir düzensiz dağılım daha düşük entropi sağlar.
Entropi Hesaplama
İkili entropi: iki sembolden oluşan bir kaynağa P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 p = 0 veya p = 1 (tamamen öngörülebilir). H(p) = 1 bayt p = 0.5 (tamamen öngörülmez).
Gibbs' Eşitsizliği & Sesiz Kodlama
Gibbs' eşitsizliği: herhangi iki olasılık dağılımı p = {pᵢ} ve q = {qᵢ} için:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
eşitlik sadece p = q olduğunda gerçekleşir. Bu, x > 0 için ln(x) ≤ x − 1 elementer gerçeğine dayanır ve eşitlik x = 1'de gerçekleşir.
Sonuç: entropi H(p) en yüksek değeri eşit olasılıklı sembollerde görülür. q sembolleri için: H_max = log₂(q).
Sesiz kodlama teoremi: bir tek başına çözülebilir kod verildiğinde, Kraft eşitsizliği gerektirir: Σ 2^(−lᵢ) ≤ 1, burada lᵢ sembol i için kodun uzunluğudur. Gibbs' eşitsizliği ile, ortalama kod uzunluğu L = Σ pᵢ lᵢ için:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Ortalama olarak entropiden daha iyi bir şey yapamazsınız. Huffman kodlaması L < H + 1'i gerçekleştirir.
Kanal Kapasitesi
Bir dik basamaklı kanal (BSC) hata olasılığı Q = 1 − P ile her bitin bağımsız olarak tersine edildiği bir kanaldir. Dik basamaklı kanalın kapasitesi - en yüksek güvenilir bilgi hızı - şu şekildedir:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
burada H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) hata oranının ikili entropisidir.
Q = 0 (hiç hata): C = 1 bit/transmission (mükemmel kanal). Q = 0.5 (random tersineleme): C = 0 (kanal bilgi taşıyamaz). Q = 1 (hepsi tersinele): C = 1 (şu an ne gönderen ne de alıcı bilgisayarlar bilmiyor, sadece tersineleyin).
C, maksimum hata olasılıklı küçük hata olasılığı ile güvenilir bir şekilde iletebileceğiniz veri hızını ölçer. Eğer R < C ise böyle kodlar mevcuttur. Eğer R > C ise bu kodlar yoktur - hiçbir kod kapasiteyi aşamaz.
Kanal Kapasitesini Hesaplama
Eğer P = 0.9 (10% hata oranı, Q = 0.1):
C = 1 + 0.9 log₂(0.9) + 0.1 log₂(0.1)
log₂(0.9) ≈ −0.152, log₂(0.1) ≈ −3.322
C ≈ 1 + 0.9×(−0.152) + 0.1×(−3.322) = 1 − 0.137 − 0.332 ≈ 0.531 bit/transmisyon
Teoremin Ne Şeyleri Gösterdi
Shannon'ın temel teoremi: R < C için, n (n → ∞) blok uzunluğundaki kodlar var ve hata olasılığı P_E → 0.
Bu, şaşırtıcı bir argüman kullanır: random kodlar. Belirli bir kod oluşturmak yerine, Shannon tüm olası rastgele kod kitapçıkları üzerinde (parçalarla kodlama) bir ortalama hata yaptı. Tüm kod kitapçıklarının ortalaması küçük ise, en azından küçük hata yapan bir kod mevcut demektir.
Sferik analiz: gönderici, mesajı aᵢ'ye sferik bir alan seçer (aᵢ'ye n(Q + ε₂) yarıçaplı sfer). Büyük n için, alınan kelime bⱼ, bu sfer içinde yüksek olasılıkla yer alır. Alıcı, bⱼ'yi içeren kod sözcüğüne dönüştürür.
Dört durum hata olasılığı P_E'yi belirler:
``
aᵢ sphere içinde mi? other aⱼ sphere içinde mi? sonuç
evet hayır doğru (hata yok)
yeş evet belirsiz → hata
hayır evet yanlış kodlama → hata
hayır hayır tüm sphereler dışında → hata
``
P_E'ye yönelik sınır şu şekilde çalışır: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) uygun olarak seçilen d ve ε₂ ile. ε₂'yi H(Q+ε₂) < C olarak seçerek ekseni negatif hale getirin. Büyük n için, ikinci terim 0'a yaklaşır.
Teoremin Varoluşsal Tabiatı
Hamming, teoremin ne sağladığını ve ne sağlamadığını kesin bir dille belirtti.
Ne kanıtlar: R < C olan güvenilir iletişim, yeterince büyük n için teoride mümkün.
Ne sağlamadığını: açık kod yapısı. Uzunluğu n'e ulaştığında kapasiteye yaklaşan bir rastgele kodun kod kitabı boyutu M × n bit, hem M hem de n astronomik ölçüde büyük. Bu boyutlarda depolayamaz veya hesaplayamazsınız.
Hata düzeltme kodları vs. Shannon: Hata düzeltme kodları (Hamming, Reed-Solomon, turbo, LDPC) açık, hesaplanabilir yapılar sağlar. Kapasiteye yakın olmaları için bazı mesafeyi feda ederler. n büyüdükçe ve her blokta düzeltilen hatalar arttıkça, uygulamalı kodlar hızla kapasiteye yaklaşabilir.
Uzaktaki uydu örneği: Voyager ve Pioneer, 5-20 watt güçle milyarlarca mil uzaklıkta iletişim kurarak güçlü hata düzeltme kodları kullandı. Uzun blok uzunlukları, büyük bir gürültüye rağmen uzaklığı olan gürültüden daha fazla hata düzelme olanağı sağladı.
Eleştirel Değerlendirme
Hamming, 13. bölümü bilgi teorisi adının yüzeysel olduğunu ve Shannon'ın bilgi formülünün insan anlamını değil, makinelerin şaşırtıcı olduğunu ölçtiğini eleştirdi. Bilgi Teorisi, gerçek dünyadaki sınırları oluşturan araçların sınırlarını öngörmeye aldatıcı. Balıkçı analoji: büyük ağırlık ağının meshi olan bir balıkçı, küçükten daha küçük balıklar olduğunu belirten balıkları yakalar. Araçların sınırları, dünyanın görünüşte kısıtlamaları haline gelir.
Tanımlarla Problemler
Hamming, bilgi teorisi kullanarak daha büyük bir metodolojik nokta oluşturdu: başlangıçtaki tanımlar, genellikle düşünülenden daha fazla şey bulmanıza yardımcı olur.
Shannon, 'bilgi'yi şaşırtma olarak seçti. Bu tanım, iletişim mühendisliği için üretken oldu. Ama 'bilgi' kelimesinin evrensel bir uygulamaya sahip olduğu düşünülen bir alan içeriği taşıdı.
Balıkçılık alegorisi: 6 inçlik bir ağı ile sadece büyük balıklar yakalar. Balıkçı: en minimum balık boyutu 6 inçtir. Sonuç, aletin dünyayı yansıtmaz.
Zeka skoru paraleli: zeka ölçmek için tasarlanmış bir test, normal dağılım üretmeye uygun hale getirildi ve sonra zeka olarak tanımlandı. Araç, kavramı şekillendiriyor.
Hamming'in önerisi: her zaman bir tanımla karşılaştığınızda, (1) tanımla önceki intuisyonunuzla ne kadar uyumlu olduğunu? (2) ne kadar saptırdığını? (3) ne tür koşullar altında yapıldığını? (4) şimdi farklı koşullar altında uygulanıyor mu?