Sumber → Saluran: Encoding Dua Tahap
Bab 10 Hamming dibuka dengan model komunikasi Shannon yang berlaku pada setiap sistem yang menggerakkan informasi: telepon, radio, hard drive, replikasi DNA, memori komputer.
Arsitektur Dua Tahap
Tahap 1: Encoding sumber (kompresi). Ubah pesan sumber menjadi representasi yang padat. Tujuan: hapus keanekaragaman yang berasal dari sumber. Contoh: kode Morse melakukan ini: huruf yang sering mendapatkan kode pendek, sedangkan huruf yang jarang mendapatkan kode panjang.
Tahap 2: Encoding saluran (perlindungan error). Tambahkan keanekaragaman yang dikendalikan sesuai karakteristik kebisingan saluran. Saluran telepon yang bising membutuhkan lebih banyak keanekaragaman daripada kabel fiber optik. Kedua tahap memisahkan antara: optimalisasikan masing-masing terpisah untuk tugasnya sendiri.
Antarmuka umum antara dua tahap — aliran bit standar — berarti setiap sumber dapat berpasangan dengan setiap saluran. Kebersamaan ini adalah insiatif arsitektur utama Shannon.
Penyimpanan sebagai komunikasi. Hamming mencatat bahwa mengirimkan pesan melalui ruang (transmisi) dan mengirimkannya melalui waktu (penyimpanan) menggunakan model yang sama. Drive cadangan adalah saluran bising dalam waktu.
Peran Kebisingan
Model Shannon membuat asumsi radikal: kebisingan tidak dapat dihindari. Setiap saluran, setiap media penyimpanan, setiap sirkuit switching memperkenalkan beberapa kemungkinan kesalahan. Pertanyaannya bukan 'bagaimana kita menghilangkan kebisingan?' tapi 'bagaimana kita mengambil kembali pesan asli meskipun ada kebisingan?'
Ini berbeda dengan fisika klasik, di mana kebisingan dimasukkan sebagai tambahan (prinsip ketidaktertentuan). Shannon memperlakukan kebisingan sebagai kondisi dasar — semua teori dibangun dari itu.
Untuk saat ini, Bab 10 mengfokuskan pada kasus tanpa kebisingan: encoding sumber tanpa kesalahan. Masalah channel coding (korosi error) menunggu bab berikutnya.
Kapan Anda Dapat Mencocokkan Unik?
Untuk kode panjang variabel yang bermanfaat, penerima harus mencocokkan aliran bit secara unik. Hamming mengilustrasikan dengan kode 4-symbol yang gagal tes ini, kemudian memperkenalkan solusi: kode prefix bebas.
Syarat Prefix Bebas
Sebuah kode adalah bebas awalan (atau segera) jika tidak ada kode kata yang merupakan awalan dari kode kata lainnya. Diberikan aliran bit yang diterima, Anda tahu simbol tersebut telah selesai pada saat Anda mencapai daun dalam pohon pencocokan — tidak diperlukan pandangan maju.
Contoh kode prefix bebas untuk {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Verifikasi: 0 bukan awalan dari 10, 110, atau 111. 10 bukan awalan dari 110 atau 111 (10 diikuti oleh lebih banyak bit memberikan 100... atau 101..., tidak salah satu dari yang dimulai dengan 110 atau 111). Kode memenuhi syarat.
Prosedur pencocokan: ikuti pohon, cabang pada setiap bit yang masuk, keluarkan simbol saat Anda menabrak daun, kembali ke akar.
Ketidaksetaraan Kraft
Untuk kode biner bebas awalan dengan panjang kata l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Kesamaan terjadi saat kode adalah komplit (daun menutupi pohon biner penuh dengan tidak ada celah). Ini adalah syarat yang diperlukan: kode prefix bebas tidak dapat melanggar ini. Sebaliknya, untuk setiap pengaturan panjang yang memenuhi ketidaksetaraan Kraft, kode prefix bebas ada.
Penggunaan Ketidaksetaraan Kraft
Diberikan panjang kode, verifikasi Kraft: Σ 2^(−l_i) ≤ 1.
Untuk {s1=0, s2=10, s3=110, s4=111}: panjangnya adalah 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Entropi Shannon
Panjang rata-rata kode dari sebuah kode panjang variabel: L = Σ p_i · l_i, di mana p_i adalah probabilitas simbol s_i dan l_i adalah panjang kode-nya.
Berapa pendek L bisa? Jawaban Shannon: tidak di bawah entropi sumber.
Entropi Shannon: H = −Σ p_i · log₂(p_i) (satuan: bit/simbol)
Entropi mengukur informasi rata-rata per simbol. Entropi tinggi berarti simbol-simbol tersebut hampir sama kemungkinannya (kemaximalan ketidaktentuan). Entropi rendah berarti beberapa simbol mendominasi (ketidaktentuan yang tinggi, lebih mudah di kompres).
Teorema Kode Tanpa Bising
Untuk setiap kode bebas awalan, H(source) ≤ L ≤ H(source) + 1.
Tidak ada kode yang bisa mengalahkan entropi. Kode Huffman (bab berikutnya) mencapai batas atas: L < H + 1. Untuk kode blok atas n simbol, batas tersebut menjadi lebih ketat: H ≤ L/n < H + 1/n.
Entropi juga adalah batas kompresi teoritis: Anda tidak bisa mengkompres sumber di bawah H bit per simbol tanpa kehilangan informasi.
Menghitung Entropi
Contoh: 4 simbol dengan probabilitas p = [1/2, 1/4, 1/8, 1/8].
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/simbol
Dan kode Huffman {0, 10, 110, 111} mencapai L = 1,75 = H tepat.
Mengapa Entropi adalah Batas Bawah
Teorema pencodiran tanpa noise batas bawahnya bukan hanya suatu rumus - itu mencerminkan sesuatu yang dalam tentang informasi: Anda tidak dapat mengompresi apa yang sudah tidak dapat diprediksi secara maksimal.
Ketika semua simbol sama kemungkinan (distribusi uniform), entropi H = log₂(n) untuk n simbol. Kode blok panjang log₂(n) bit mencapai H secara tepat. Tidak ada kode yang bisa lebih baik.
Ketika satu simbol mendominasi (misalnya, p(A) = 0,99, p(B) = 0,01), H kecil - dekat dengan 0. Kode panjang variabel dapat mengasosiasikan A dengan kode yang sangat pendek, mengenkripsi aliran sangat efisien.
Pengambilan kesimpulan praktis: kesepakatan kompresi besar hanya ada ketika kemungkinan simbol berbeda secara signifikan. Jika sumber sudah 'uniform' (acak), Huffman coding tidak mendapatkan apa-apa.