Sumber → Saluran: Pengodean Dua Tahap
Bab 10 Hamming dibuka dengan model komunikasi Shannon, yang berlaku untuk setiap sistem yang memindahkan informasi: panggilan telepon, radio, hard drive, replikasi DNA, memori komputer.
Arsitektur Dua Tahap
Tahap 1: Pengodean sumber (kompresi). Konversi pesan sumber menjadi representasi yang kompak. Tujuan: menghilangkan redundansi asli dari sumber. Kode Morse melakukan ini: huruf umum mendapat kode pendek, huruf langka mendapat kode panjang.
Tahap 2: Pengodean saluran (proteksi kesalahan). Tambahkan redundansi terkontrol yang disesuaikan dengan karakteristik kebisingan saluran. Saluran telepon yang bising membutuhkan lebih banyak redundansi daripada kabel serat optik. Dua tahap saling lepas: optimalkan masing-masing secara independen untuk tugasnya sendiri.
Antarmuka umum antara dua tahap — aliran bit standar — berarti sumber apa pun dapat berpasangan dengan saluran apa pun. Modularitas ini adalah wawasan arsitektur kunci Shannon.
Penyimpanan sebagai komunikasi. Hamming mencatat bahwa mengirim pesan melalui ruang (transmisi) dan mengirimnya 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 rangkaian penyaklaran memperkenalkan beberapa probabilitas kesalahan. Pertanyaannya bukan 'bagaimana kita menghilangkan kebisingan?' tetapi 'bagaimana kita memulihkan pesan asli meskipun ada kebisingan?'
Ini berbeda dengan fisika klasik, di mana kebisingan memasuki sebagai pemikiran sesudahnya (prinsip ketidakpastian). Shannon memperlakukan kebisingan sebagai kondisi mendasar — semua teori dibangun darinya.
Untuk saat ini, Bab 10 fokus pada kasus tanpa kebisingan: pengodean sumber tanpa kesalahan. Masalah pengodean saluran (koreksi kesalahan) menunggu di bab-bab berikutnya.
Kapan Anda Dapat Menguraikan Kode dengan Unik?
Agar kode panjang variabel berguna, penerima harus menguraikan aliran bit tanpa ambiguitas. Hamming menggambarkan dengan kode 4-simbol yang gagal dalam tes ini, kemudian memperkenalkan perbaikannya: kode bebas prefiks.
Kondisi Bebas Prefiks
Kode bersifat bebas prefiks (atau instan) jika tidak ada codeword yang merupakan prefiks dari codeword lain. Diberikan aliran bit yang diterima, Anda tahu simbol telah berakhir saat Anda mencapai daun di pohon penguraian — tidak diperlukan lookahead.
Contoh kode bebas prefiks untuk {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Verifikasi: 0 bukan prefiks dari 10, 110, atau 111. 10 bukan prefiks dari 110 atau 111 (10 diikuti oleh lebih banyak bit memberikan 100... atau 101..., tidak satupun yang dimulai dengan 110 atau 111). Kode ini memenuhi syarat.
Prosedur penguraian: ikuti pohon, cabang pada setiap bit yang masuk, keluarkan simbol saat Anda mencapai daun, kembali ke akar.
Ketidaksamaan Kraft
Untuk kode biner bebas prefiks apa pun dengan panjang codeword l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Persamaan berlaku ketika kode bersifat lengkap (daun menutupi pohon biner penuh tanpa celah). Ini adalah kondisi yang diperlukan: tidak ada kode bebas prefiks yang dapat melanggarnya. Sebaliknya, untuk setiap set panjang yang memenuhi ketidaksamaan Kraft, kode bebas prefiks ada.
Menerapkan Ketidaksamaan 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 kode rata-rata kode panjang variabel: L = Σ p_i · l_i, di mana p_i adalah probabilitas simbol s_i dan l_i adalah panjang kodnya.
Seberapa pendek L bisa? Jawaban Shannon: tidak di bawah entropi sumber.
Entropi Shannon: H = −Σ p_i · log₂(p_i) (satuan: bits/simbol)
Entropi mengukur informasi rata-rata per simbol. Entropi tinggi berarti simbol kira-kira sama kemungkinannya (ketidakpastian maksimum). Entropi rendah berarti beberapa simbol mendominasi (prediktabilitas tinggi, lebih kompresibel).
Teorema Pengodean Tanpa Kebisingan
Untuk kode bebas prefiks apa pun, H(sumber) ≤ L ≤ H(sumber) + 1.
Tidak ada kode yang dapat mengalahkan entropi. Pengodean Huffman (bab berikutnya) mencapai batas atas: L < H + 1. Untuk kode blok lebih dari n simbol, batas mengencang: H ≤ L/n < H + 1/n.
Entropi juga merupakan batas kompresi teoritis: Anda tidak dapat mengompresi 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 bits/simbol
Dan kode Huffman {0, 10, 110, 111} mencapai L = 1.75 = H persis.
Mengapa Entropi Adalah Batas Bawah
Batas bawah teorema pengodean tanpa kebisingan bukan hanya rumus — itu mencerminkan sesuatu yang mendalam tentang informasi: Anda tidak dapat mengompresi apa yang sudah sangat tidak dapat diprediksi.
Ketika semua simbol sama-sama mungkin (distribusi seragam), entropi H = log₂(n) untuk n simbol. Kode blok dengan panjang log₂(n) bit mencapai tepat H. Tidak ada kode yang bisa lebih baik.
Ketika satu simbol mendominasi (katakanlah, p(A) = 0.99, p(B) = 0.01), H kecil — mendekati 0. Kode panjang variabel dapat menetapkan A kode yang sangat pendek, mengkodikan aliran dengan sangat efisien.
Keuntungan praktis: keuntungan kompresi besar hanya ada ketika probabilitas simbol berbeda secara substansial. Jika sumber sudah 'seragam' (terlihat acak), pengodean Huffman tidak mendapat apa pun.