Apa yang Disebut Shannon sebagai Informasi
Shannon mendefinisikan informasi dengan mengukur kejutan. Pesan dengan probabilitas p membawa:
I = −log₂(p) bit
Peristiwa yang pasti (p = 1) membawa 0 bit — tidak ada kejutan, tidak ada informasi. Peristiwa yang langka (p = 1/1024) membawa 10 bit.
Hamming segera menunjukkan masalahnya: ini adalah rumus untuk mengukur suatu kuantitas, bukan definisi konsep. Ini mengukur kejutan seperti mesin, bukan makna manusia. Siswa yang sudah tahu jawaban atas pertanyaan menerima 0 bit dari jawaban — terlepas dari seberapa penting jawaban itu bagi orang lain.
Rumusnya berlaku baik untuk sistem telepon, radio, & komputer. Ini berlaku buruk untuk komunikasi manusia, biologi, atau makna. Nama pilihan Hamming: 'Teori Komunikasi', bukan 'Teori Informasi'.
Entropi
Untuk abjad dari q simbol dengan probabilitas p₁, p₂, ..., p_q, informasi rata-rata per simbol adalah entropi:
H = −Σᵢ pᵢ log₂(pᵢ)
H mencapai maksimumnya ketika semua probabilitas sama: H_max = log₂(q) bit. Distribusi yang tidak seragam memiliki entropi lebih rendah.
Menghitung Entropi
Entropi biner: sumber dengan dua simbol, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 pada p = 0 atau p = 1 (sepenuhnya dapat diprediksi). H(p) = 1 bit pada p = 0,5 (sepenuhnya tidak dapat diprediksi).
Ketidaksetaraan Gibbs & Pengkodean Tanpa Gangguan
Ketidaksetaraan Gibbs: untuk dua distribusi probabilitas p = {pᵢ} & q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
dengan kesetaraan hanya ketika p = q. Ini bergantung pada fakta dasar bahwa ln(x) ≤ x − 1 untuk semua x > 0, dengan kesetaraan pada x = 1.
Konsekuensi: entropi H(p) dimaksimalkan ketika semua simbol memiliki probabilitas yang sama. Untuk q simbol: H_max = log₂(q).
Teorema pengkodean tanpa gangguan: diberikan kode yang dapat didekodekan secara unik, ketidaksetaraan Kraft memerlukan Σ 2^(−lᵢ) ≤ 1 di mana lᵢ adalah panjang kode untuk simbol i. Berdasarkan ketidaksetaraan Gibbs, panjang kode rata-rata L = Σ pᵢ lᵢ memenuhi:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Anda tidak dapat melakukan yang lebih baik daripada entropi rata-rata. Pengkodean Huffman mencapai L < H + 1.
Kapasitas Saluran
Saluran simetris biner (BSC) membalik setiap bit secara independen dengan probabilitas kesalahan Q = 1 − P. Kapasitas BSC — laju informasi yang dapat diandalkan maksimal — adalah:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
di mana H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) adalah entropi biner dari laju kesalahan.
Pada Q = 0 (tidak ada kesalahan): C = 1 bit/transmisi (saluran sempurna). Pada Q = 0,5 (pembalikan acak): C = 0 (saluran tidak membawa informasi). Pada Q = 1 (semua bit terbalik): C = 1 (Anda tahu persis apa yang dikirim pengirim, tinggal balikkan semuanya kembali).
C mengukur laju maksimal R di mana Anda dapat mengirim dengan probabilitas kesalahan yang dapat diabaikan. Jika R < C, kode seperti itu ada. Jika R > C, tidak ada — tidak ada kode yang dapat mengalahkan kapasitas.
Menghitung Kapasitas Saluran
Dengan P = 0,9 (laju kesalahan 10%, 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/transmisi
Apa yang Dibuktikan Teoremanya
Teorema fundamental Shannon: untuk laju apa pun R < C, ada kode dengan panjang blok n (dengan n → ∞) yang mencapai probabilitas kesalahan P_E → 0.
Bukti menggunakan argumen yang mengejutkan: kode acak. Alih-alih membangun kode spesifik, Shannon mencari rata-rata semua buku kode acak yang mungkin (pengkodean lemparan koin). Dia menunjukkan rata-rata kesalahan di semua buku kode kecil. Jika rata-ratanya kecil, setidaknya satu kode mencapai kesalahan kecil.
Analisis berbasis bola: pengirim memilih pesan aᵢ → bola dengan radius n(Q + ε₂) di sekitar aᵢ dalam ruang biner berdimensi n. Untuk n besar, kata yang diterima bⱼ berada dalam bola ini dengan probabilitas tinggi. Penerima mendekodekan ke codeword yang bolanya berisi bⱼ.
Empat kasus menentukan probabilitas kesalahan P_E:
``
aᵢ dalam bola aⱼ lain dalam bola hasil
iya tidak benar (tanpa kesalahan)
iya iya ambigu → kesalahan
tidak iya dekode salah → kesalahan
tidak tidak di luar semua bola → kesalahan
``
Batas pada P_E ternyata: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) untuk d & ε₂ yang dipilih dengan tepat. Memilih ε₂ sehingga H(Q+ε₂) < C membuat eksponennya negatif. Untuk n besar, suku kedua → 0.
Sifat Eksistensial dari Teoremanya
Hamming sangat tepat tentang apa yang dibuktikan teorema & apa yang tidak.
Apa yang dibuktikannya: komunikasi yang dapat diandalkan pada laju R < C dimungkinkan, pada prinsipnya, untuk n yang cukup besar.
Apa yang tidak diberikannya: konstruksi kode eksplisit. Kode acak dengan panjang n yang cukup besar untuk mendekati kapasitas memiliki buku kode berukuran M × n bit, di mana baik M maupun n sangat besar. Anda tidak dapat menyimpannya atau menghitungnya.
Kode koreksi kesalahan vs. Shannon: kode koreksi kesalahan (Hamming, Reed-Solomon, turbo, LDPC) menyediakan konstruksi yang eksplisit & dapat dihitung. Mereka mengorbankan beberapa jarak dari kapasitas sebagai gantinya untuk encoder & decoder praktis. Saat n tumbuh & lebih banyak kesalahan dikoreksi per blok, kode praktis dapat mendekati kapasitas dengan dekat.
Contoh satelit luar angkasa: Voyager & Pioneer menggunakan kode koreksi kesalahan yang kuat untuk berkomunikasi di seluruh miliaran mil dengan daya 5–20 watt. Panjang blok yang panjang memungkinkan lebih banyak kesalahan per blok untuk dikoreksi, mendorong dekat dengan kapasitas meskipun bising luar biasa dari jarak.
Penilaian Kritis
Hamming menutup Bab 13 dengan kritik yang lebih luas tentang definisi dalam sains. Rumus informasi Shannon mengukur kejutan mesin, bukan makna manusia. Nama 'Teori Informasi' berjanji terlalu banyak. Analogi jaring ikan: nelayan yang hanya menangkap ikan yang lebih besar dari mata jaringnya menyimpulkan tidak ada ikan yang lebih kecil. Keterbatasan alat menjadi batasan aparatur dunia.
Masalah dengan Definisi
Hamming menggunakan teori informasi untuk membuat titik metodologis yang lebih besar: definisi awal menentukan apa yang Anda temukan, lebih dari yang disadari sebagian besar orang.
Shannon memilih untuk mendefinisikan 'informasi' sebagai kejutan. Definisi itu produktif untuk teknik komunikasi. Tetapi mengimpor lingkup spesifik — sistem seperti mesin — ke dalam kata ('informasi') yang menyarankan penerapan universal.
Analogi jaring ikan: jaring dengan mata 6 inci menangkap hanya ikan besar. Nelayan menyimpulkan: ukuran ikan minimum 6 inci. Kesimpulannya mencerminkan alat, bukan dunia.
IQ sebagai paralel: tes yang dirancang untuk mengukur 'intelijen', dikalibrasi untuk menghasilkan distribusi normal, kemudian digunakan untuk mendefinisikan intelijen. Alat membentuk konsep.
Rekomendasi Hamming: setiap kali Anda menemui definisi, tanyakan (1) seberapa jauh itu sepakat dengan intuisi sebelumnya Anda? (2) seberapa jauh itu mendistorsi? (3) di bawah kondisi apa itu dibingkai? (4) apakah itu diterapkan sekarang di bawah kondisi yang berbeda?