Soal 5: Kompresi Data, Huffman Code & Kapasitas Kanal Shannon
Jawaban
Bagian A: Kompresi Data & Huffman Coding
1. Entropy Sumber Data
Langkah pertama, kita hitung entropy sumber sebagai batas teoritis kompresi:
$$H = -\sum P(x_i) \cdot \log_2 P(x_i)$$ $$H = -[0.5 \cdot \log_2(0.5) + 0.25 \cdot \log_2(0.25) + 0.125 \cdot \log_2(0.125) + 0.125 \cdot \log_2(0.125)]$$ $$H = -[0.5 \cdot (-1) + 0.25 \cdot (-2) + 0.125 \cdot (-3) + 0.125 \cdot (-3)]$$ $$H = -[-0.5 - 0.5 - 0.375 - 0.375]$$ $$H = 1.75 \text{ bits/simbol}$$
Entropy-nya 1.75 bits — ini batas bawah ya, rata-rata kode ga boleh lebih kecil dari ini.
2. Bikin Pohon Huffman
Huffman coding ngebangun pohon biner dari bawah ke atas, gabungin dua simbol yang probabilitasnya paling kecil:
-
Langkah 1: Urutkan probabilitas
A=0.5, B=0.25, C=0.125, D=0.125 (urut dari yang paling gede)
-
Langkah 2: Gabung dua terkecil (C=0.125 + D=0.125)
Node baru CD = 0.25. Sekarang list-nya: A=0.5, B=0.25, CD=0.25
-
Langkah 3: Gabung dua terkecil (B=0.25 + CD=0.25)
Node baru BCD = 0.5. Sekarang list-nya: A=0.5, BCD=0.5
-
Langkah 4: Gabung sisa (A=0.5 + BCD=0.5)
Root ABCD = 1.0 — pohon beres.
-
Langkah 5: Assign kode (0 = kiri, 1 = kanan)
Tinggal telusuri dari root ke setiap daun.
3. Hasil Kode Huffman
| Simbol | Probabilitas | Kode Huffman | Panjang Kode \(l_i\) |
|---|---|---|---|
| A | 0.5 | 0 | 1 bit |
| B | 0.25 | 10 | 2 bits |
| C | 0.125 | 110 | 3 bits |
| D | 0.125 | 111 | 3 bits |
4. Rata-rata Panjang Kode
$$\bar{L} = \sum_{i=1}^{n} P(x_i) \cdot l_i$$ $$\bar{L} = (0.5 \times 1) + (0.25 \times 2) + (0.125 \times 3) + (0.125 \times 3)$$ $$\bar{L} = 0.5 + 0.5 + 0.375 + 0.375$$ $$\bar{L} = 1.75 \text{ bits/simbol}$$
5. Efisiensi Kode
$$\eta = \frac{H}{\bar{L}} \times 100\%$$ $$\eta = \frac{1.75}{1.75} \times 100\% = \mathbf{100\%}$$
Bagian B: Kapasitas Kanal Shannon
1. Batasan Kanal
Kanal komunikasi ada batasan fisiknya:
- Bandwidth (B): 3000 Hz — rentang frekuensi yang tersedia buat transmisi.
- Noise (SNR): 15 — signal-to-noise ratio, ngukur kualitas sinyal relatif terhadap noise.
- Konsekuensinya: Ga semua data bisa dikirim secepet-cepetnya — ada batas atas yang namanya kapasitas kanal.
2. Shannon-Hartley Theorem
$$C = B \cdot \log_2(1 + \text{SNR})$$
Dimana C = kapasitas kanal (bps), B = bandwidth (Hz), SNR = signal-to-noise ratio (dalam linear ya, bukan dB).
3. Ngitung Kapasitas Kanal
CATET: SNR = 15 ini dalam bentuk rasio linear ya (bukan dB). Kalo SNR-nya dB, konversi dulu: \(\text{SNR}_{\text{linear}} = 10^{\text{SNR}_{\text{dB}}/10}\).
$$C = 3000 \cdot \log_2(1 + 15)$$ $$C = 3000 \cdot \log_2(16)$$ $$C = 3000 \cdot 4$$ $$C = \mathbf{12{,}000 \text{ bps}}$$
Catatan: Kalo SNR = 15 dB
Kalo SNR-nya 15 dB (nilai yang umum di telekomunikasi), itungannya:
\(\text{SNR}_{\text{linear}} = 10^{15/10} = 10^{1.5} \approx 31.62\)
\(C = 3000 \cdot \log_2(1 + 31.62) = 3000 \cdot \log_2(32.62) \approx 3000 \cdot 5.028 \approx \mathbf{15{,}084 \text{ bps}}\)
4. Maksudnya & Efisiensi Sistem
| Parameter | Nilai | Keterangan |
|---|---|---|
| Entropy Sumber (H) | 1.75 bits/simbol | Rata-rata informasi per simbol |
| Huffman Avg Length (L̄) | 1.75 bits/simbol | Rata-rata bit setelah kompresi |
| Code Efficiency (η) | 100% | Optimal — tidak bisa dikompresi lagi |
| Shannon Capacity (C) | 12,000 bps | Batas atas teoritis transmisi |
| Max Symbols/sec | 12,000 ÷ 1.75 ≈ 6,857 | Maksimum simbol yang bisa dikirim per detik |
5. Batasan Kanal
Kanal dengan B=3000Hz dan SNR=15 kapasitasnya 12,000 bps. Artinya:
- Kalo sumber data ngasilin > 6,857 simbol/detik → kanal ga cukup, butuh kompresi tambahan atau naikin bandwidth.
- Kalo sumber data ngasilin ≤ 6,857 simbol/detik → kanal cukup, transmisi real-time bisa.
- Error-correcting codes mungkin dibutuhin karena noise cukup signifikan di kanal praktis.