Shannon'ın Bilgiyi Nasıl Adlandırdığı
Shannon, sürprizliği ölçerek bilgiyi tanımladı. p olasılığına sahip bir mesaj şunu taşır:
I = −log₂(p) bit
Kesin bir olay (p = 1) 0 bit taşır — sürpriz yok, bilgi yok. Nadir bir olay (p = 1/1024) 10 bit taşır.
Hamming hemen sorunu işaret ediyor: bu bir niceliği ölçmek için bir formüldür, kavramın tanımı değildir. Makinesel sürprizi ölçer, insan anlamını değil. Bir sorunun cevabını zaten bilen bir öğrenci, cevapta 0 bit alır — cevabın diğerleri için ne kadar önemli olduğundan bağımsız olarak.
Formül telefon sistemlerine, radyoya, bilgisayarlara iyi uygulanır. İnsan iletişimine, biyolojiye veya anlama kötü uygulanır. Hamming'in tercih ettiği ad: 'İletişim Teorisi', 'Bilgi Teorisi' değil.
Entropi
p₁, p₂, ..., p_q olasılıklarına sahip q sembolün alfabesi için, sembol başına ortalama bilgi entropidir:
H = −Σᵢ pᵢ log₂(pᵢ)
H tüm olasılıklar eşit olduğunda maksimuma ulaşır: H_max = log₂(q) bit. Herhangi bir homojen olmayan dağılım daha düşük entropiye sahiptir.
Entropiyi Hesaplama
İkili entropi: iki sembolü olan bir kaynak, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) p = 0 veya p = 1 konumunda 0'dır (tamamen tahmin edilebilir). H(p) p = 0.5 konumunda 1 bittir (tamamen tahmin edilemez).
Gibbs Eşitsizliği & Gürültüsüz 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 ancak p = q olduğunda geçerlidir. Bu, tüm x > 0 için ln(x) ≤ x − 1 gerçeğine dayanır, eşitlik x = 1 konumundadır.
Sonuç: entropi H(p) tüm semboller eşit olasılıkta olduğunda maksimize edilir. q sembol için: H_max = log₂(q).
Gürültüsüz kodlama teoremi: benzersiz olarak decodlanabilir bir kod verildiğinde, Kraft eşitsizliği Σ 2^(−lᵢ) ≤ 1 gerektirir; burada lᵢ sembol i için kodun uzunluğudur. Gibbs eşitsizliği ile, ortalama kod uzunluğu L = Σ pᵢ lᵢ şunu sağlar:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Entropiye kıyasla daha iyi yapamayız. Huffman kodlaması L < H + 1 elde eder.
Kanal Kapasitesi
İkili simetrik kanal (BSC), her biti bağımsız olarak Q = 1 − P hata olasılığı ile çevirir. BSC'nin kapasitesi — maksimum güvenilir bilgi hızı — şudur:
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 (hata yok) konumunda: C = 1 bit/iletim (mükemmel kanal). Q = 0.5 (rastgele çevirme) konumunda: C = 0 (kanal bilgi taşımaz). Q = 1 (tüm bitler çevrilir) konumunda: C = 1 (gönderenin ne gönderdiğini tam olarak bilirsiniz, sadece her şeyi geri çevirin).
C, R'nin maksimum hızını ölçer; burada keyfi olarak küçük hata olasılığı ile iletebilirsiniz. R < C ise, bu tür kodlar vardır. R > C ise, yoktur — hiçbir kod kapasiteyi yenemez.
Kanal Kapasitesini Hesaplama
P = 0.9 ile (%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/iletim
Teorem Neyi Kanıtlar
Shannon'ın temel teoremi: herhangi bir R < C hızı için, blok uzunluğu n (n → ∞ ile) olan kodlar vardır ve P_E → 0 hata olasılığı elde eder.
Kanıt şaşırtıcı bir argüman kullanır: rastgele kodlar. Belirli bir kod yazmak yerine, Shannon tüm olası rastgele kod kitapları (yazı tura kodlaması) arasında ortalamasını aldı. Tüm kod kitapları arasındaki ortalama hatasının küçük olduğunu gösterdi. Ortalama küçükse, en az biri küçük hata elde eder.
Küre tabanlı analiz: gönderici aᵢ → n-boyutlu ikili uzayda aᵢ etrafında n(Q + ε₂) yarıçaplı küre seçer. Büyük n için, alınan sözcük bⱼ bu küre içinde yüksek olasılıkla yer alır. Alıcı, bⱼ içeren codeword'e kodu çözer.
Dört durum hata olasılığı P_E belirler:
``
aᵢ içinde küre diğer aⱼ küre içinde sonuç
evet hayır doğru (hata yok)
evet evet muğlak → hata
hayır evet yanlış decode → hata
hayır hayır tüm küreler dışında → hata
``
P_E sınırı şu şekilde çalışır: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) uygun d ve ε₂ seçimi için. H(Q+ε₂) < C olarak ε₂ seçmek üssü negatif yapıyor. Büyük n için, ikinci terim → 0.
Teoremin Varoluşsal Doğası
Hamming, teorimin neyi yaptığını ve yapmadığını tam olarak düşündü.
Kanıtladığı şey: güvenilir iletişim R < C oranında prensipte mümkündür, yeterince büyük n için.
Sağlamadığı şey: açık kod yapısı. Kapasiteye yaklaşmaya yeterince büyük n uzunluğundaki rastgele kod, M × n bit boyutunda bir kod kitabına sahiptir; burada hem M hem de n astronomik olarak büyüktür. Bunu saklayamaz veya onunla hesap yapamazsınız.
Hata düzeltme kodları vs. Shannon: hata düzeltme kodları (Hamming, Reed-Solomon, turbo, LDPC) açık, hesaplanabilir yapılar sağlar. Kapasite ile biraz mesafe için kodlayıcı & çözücü hesaplanabilirliği feda ederler. n büyüdükçe ve blok başına daha fazla hata düzeltilirken, pratik kodlar kapasiteye yakından yaklaşabilir.
Uzay uydusu örneği: Voyager ve Pioneer, milyarlarca mil uzaklıkta 5–20 watt gücüyle iletişim kurmak için güçlü hata düzeltme kodları kullanmıştır. Uzun blok uzunlukları, mesafeden gelen muazzam gürültüye rağmen kapasiteye yakın itme yapmasını sağlayan blok başına daha fazla hata düzeltmeyi mümkün kılmıştır.
Eleştirel Değerlendirme
Hamming, Bölüm 13'ü bilimde tanımlar hakkında daha geniş bir eleştiriyle kapattı. Shannon'ın bilgi formülü makinesel sürprizi ölçer, insan anlamını değil. 'Bilgi Teorisi' adı aşırı vaat eder. Balık ağı analojisi: ağ göz boyutundan daha küçük balık tutamayan balıkçı, daha küçük balık olmadığı sonucuna varır. Aracın sınırlamaları, dünyanın görünür kısıtlamaları haline gelir.
Tanımlar ile İlgili Problem
Hamming, bilgi teorisini daha geniş bir metodolojik noktayı yapmak için kullandı: ilk tanımlar, çoğu insanın fark ettiğinden daha çok neyi bulduğunuzu belirler.
Shannon 'bilgiyi' sürpriz olarak tanımlamayı seçti. Bu tanım, iletişim mühendisliği için üretken oldu. Fakat belirli bir kapsam — makinesel sistemler — 'bilgi' sözcüğüne ithal etti, bu evrensel uygulanabilirliği ima eder.
Balık ağı analojisi: 6 inçlik ağ göz boyutlu bir ağ sadece büyük balıkları yakalar. Balıkçı şu sonucu verir: minimum balık boyutu 6 inçtir. Sonuç aracı yansıtır, dünyayı değil.
IQ paralel örneği: 'zekayı' ölçmek için tasarlanan bir test, normal dağılım üretmek için ayarlanmış, sonra zekayı tanımlamak için kullanılan. Araç kavramı şekillendirir.
Hamming'in tavsiyesi: tanımla karşılaştığınız zaman, şunu sorun (1) sizin önceki sezginizle ne kadar anlaşıyor? (2) ne kadar bozuyor? (3) ne koşullar altında çerçevelendi? (4) şimdi farklı koşullar altında uygulanıyor mu?