1. Pendahuluan: Dua Keajaiban Rekonstruksi Informasi dalam Kehidupan Sehari-hari

Baik di ruang antarbintang maupun di layar kamera ponsel Anda, rekayasa digital modern setiap hari melakukan sesuatu yang tampak menentang intuisi fisika: merekonstruksi informasi digital secara 100% akurat bit demi bit dari sinyal atau media yang telah rusak parah akibat derau termal, goresan, atau kerusakan fisik.

Keajaiban 1: Voyager 1 & 2 Mengirim Gambar melintasi 24 Miliar Kilometer pada Daya $10^{-16}\text{ Watt}$

Diluncurkan pada tahun 1977, wahana antariksa Voyager 1 dan Voyager 2 memotret Jupiter, Saturnus, Uranus, dan Neptunus sebelum memasuki ruang antarbintang yang berjarak lebih dari 24 miliar kilometer dari Bumi. Pemancar radio Voyager hanya beroperasi pada daya $23\text{ watt}$ — lebih kecil dari bohlam lampu kulkas. Ketika gelombang elektromagnetik tersebut mencapai antena parabola 70 meter milik Deep Space Network (DSN) NASA di Bumi, daya sinyal yang diterima telah melemah hingga sekitar $10^{-16}\text{ watt}$ ($0,1\text{ attowatt}$), tenggelam di dalam derau termal (thermal noise). Namun Voyager berhasil mengirimkan foto berwarna beresolusi tajam dengan nol kesalahan bit.

Keajaiban 2: Kode QR yang $30\%$ Modulnya Tertutup Noda Kopi atau Logo Perusahaan

Demikian pula, ketika Anda memindai Kode QR (Quick Response Code) yang terkena noda kopi atau memiliki logo perusahaan yang menutupi hingga $30\%$ area tengahnya, kamera ponsel Anda memulihkan URL atau data pembayaran secara utuh dalam waktu kurang dari $10\text{ milidetik}$ dengan nol kesalahan bit (Zero Bit Errors).

  flowchart TD
    subgraph Voyager["Telemetri Antariksa Dalam (Voyager 1 & 2)"]
        V1["Data Citra Planet (k bit)"] --> V2["Pengkodean Berantai (RS Luar + Konvolusional/LDPC Dalam)"]
        V2 --> V3["Pemancar 23 W melintasi Miliaran km (10⁻¹⁶ W Diterima)"]
        V3 --> V4["Derau Putih Gaussian (AWGN) & Pembalikan Bit"]
        V4 --> V5["Soft-Decision Viterbi / Belief Propagation + Dekode RS"]
        V5 --> V6["Citra Planet Tajam (Nol Kesalahan Bit)"]
    end
    subgraph QR["Pemindaian Kode QR Harian"]
        Q1["URL / Data Payload (k byte)"] --> Q2["Pengkodean Reed-Solomon GF(2⁸) (n byte)"]
        Q2 --> Q3["Noda Kopi atau Logo Merusak 30% Modul"]
        Q3 --> Q4["Perhitungan Sindrom + Algoritma Berlekamp-Massey"]
        Q4 --> Q5["Pencarian Chien + Rumus Forney (10 ms)"]
        Q5 --> Q6["Rekonstruksi Data 100% Akurat"]
    end

Bagaimana hal ini mungkin secara matematis? Jawabannya terletak pada Teori Informasi Claude Shannon (1948) dan aljabar Kode Koreksi Kesalahan (Error-Correcting Codes, ECC).

2. Revolusi Claude Shannon (1948) dan Teorema Pengkodean Kanal Berderau

2.1 Mengapa Kode Pengulangan Naif ($0 \to 00000$) Gagal

Saat $n \to \infty$, memang $P_e^{(n)} \to 0$, tetapi secara bersamaan laju kode runtuh menjadi nol: $R = k/n = 1/n \to 0$.

2.2 Teorema Shannon dan Batas Mutlak Shannon ($-1,59\,\text{dB}$)

Pada tahun 1948, Claude E. Shannon membuktikan dalam “A Mathematical Theory of Communication” Teorema Pengkodean Kanal Berderau:

Teorema (Pengkodean Kanal Berderau Shannon, 1948): Setiap kanal tanpa memori memiliki Kapasitas Kanal $C > 0$ yang positif:

• Untuk Kanal Simetris Biner (BSC) dengan fungsi entropi biner $H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$: $$C_{\text{BSC}}(p) = 1 - H_2(p) = 1 + p\log_2 p + (1-p)\log_2(1-p) \quad [\text{bit / penggunaan kanal}]$$
• Untuk kanal AWGN dengan lebar pita $B$, daya sinyal $S$, dan derau $N = N_0 B$ (Teorema Shannon-Hartley): $$C_{\text{AWGN}} = B \log_2\!\left(1 + \frac{S}{N}\right) = B \log_2\!\left(1 + \frac{S}{N_0 B}\right) \quad [\text{bit / s}]$$

Untuk setiap laju kode $R < C$, terdapat kode blok dengan panjang $n \to \infty$ yang menghasilkan probabilitas kesalahan dekode sekecil apa pun ($P_e \to 0$)!

3. Terobosan Geometris Richard Hamming (1950): Jarak Hamming dan Kode Sempurna $[7, 4, 3]$

3.1 Jarak Hamming $d_H(\mathbf{u}, \mathbf{v})$ dan Batas Pengepakan Bola

Untuk kode $\mathcal{C} \subset \mathbb{F}_q^n$ dengan jarak minimum $d_{\min} = \min_{\mathbf{u}\neq\mathbf{v}} d_H(\mathbf{u},\mathbf{v})$, geometri bola-bola Hamming berjari-jari $t$ yang saling lepas membuktikan bahwa kode tersebut mampu:

• Mendeteksi $d_{\min} - 1$ kesalahan;
• Memulihkan $e = d_{\min} - 1$ penghapusan (erasures) pada posisi yang diketahui;
• Mengoreksi $t = \lfloor(d_{\min} - 1)/2\rfloor$ kesalahan acak pada posisi yang tidak diketahui: $$\mathbf{d_{\min} \ge 2t + e + 1}, \qquad |\mathcal{C}| \cdot \sum_{i=0}^{t} \binom{n}{i} (q-1)^i \le q^n \quad \text{(Batas Hamming)}$$

3.2 Kode Sempurna Hamming $(7,4)$ dan Dekode Sindrom

Vektor sindrom 3-bit $\mathbf{s} = \mathbf{H}\mathbf{y}^T = \mathbf{H}(\mathbf{c} + \mathbf{e})^T = \mathbf{H}\mathbf{e}^T \pmod 2$ langsung mengekstrak kolom matriks $\mathbf{H}$ yang bersesuaian dengan posisi bit yang terbalik: jika kolom diurutkan secara biner dari $1$ hingga $7$, sindrom $\mathbf{s}$ langsung menghasilkan indeks biner $(1 \dots 7)$ dari bit yang rusak, melindungi seluruh memori server ECC DRAM (SECDED) saat ini.

4. Mahakarya Reed dan Solomon (1960): Kode Reed-Solomon di atas Medan Galois $\mathbb{F}_{2^m}$

4.1 Medan Galois $\text{GF}(2^8)$ dan Kekebalan terhadap Burst Errors

Untuk mengatasi kesalahan beruntun (goresan cakram optik, noda pada Kode QR), Irving Reed dan Gustave Solomon (1960) mengelompokkan setiap byte ($m=8$ bit) sebagai satu simbol di dalam medan hingga $\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$. Bahkan jika seluruh 8 bit dalam satu byte hancur, di dalam $\text{GF}(2^8)$ itu hanyalah satu kesalahan simbol tunggal!

4.2 Interpolasi Polinomial dan Batas Singleton MDS $d_{\min} = n - k + 1$

Dengan demikian, $n - k$ byte paritas mampu memulihkan hingga $e = n - k$ penghapusan (RAID-6, penyimpanan cloud) atau mengoreksi hingga $t = \lfloor(n-k)/2\rfloor$ kesalahan simbol pada posisi tak diketahui (Kode QR hingga 30% kerusakan pada Level H; kode $[255, 223]$ pada Voyager) melalui polinomial generator siklik $g(x) = \prod_{i=1}^{2t}(x - \alpha^i)$, algoritma Berlekamp-Massey / Euclidean ($\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$), pencarian Chien, dan rumus Forney.

5. Mendekati Batas Shannon: Kode LDPC (1962), Turbo (1993), dan Polar (2009)

1. Kode LDPC Robert Gallager (1962): menggunakan matriks paritas jarang $\mathbf{H}$ dan graf bipartit Tanner. Melalui pertukaran iteratif rasio log-likelihood lunak $L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}$ dengan Belief Propagation (Sum-Product), kode LDPC beroperasi hanya $0,0045\,\text{dB}$ dari batas Shannon (kanal data 5G NR, Wi-Fi 6/7, dan SSD 3D NAND).
2. Polar Codes Erdal Arıkan (2009): menerapkan transformasi Kronecker $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$ secara rekursif untuk menciptakan polarisasi kanal — saat $N \to \infty$, proporsi $C = I(W)$ subkanal sintetis menuju kapasitas $1$ (bebas derau, membawa bit informasi) dan proporsi $1 - C$ menuju kapasitas $0$ (bit beku / Frozen Bits $= 0$), menjadikannya kode berkecepatan $O(N \log N)$ pertama yang secara matematis terbukti mencapai kapasitas Shannon (kanal kontrol 5G NR).

  flowchart TD
    subgraph CapID["Kode Modern Pencapai Kapasitas Shannon"]
        L1["Kode LDPC (Graf Bipartit Jarang Tanner)"] --> L2["Pertukaran Iteratif Pesan LLR Lunak"]
        L2 --> L3["Belief Propagation Sum-Product (0,0045 dB dari Batas Shannon)"]
        P1["Polar Codes (Transformasi Kronecker G_N = B_N F^{⊗m})"] --> P2["Polarisasi Kanal menjadi W⁻ (memburuk) dan W⁺ (membaik)"]
        P2 --> P3["Proporsi C → Kapasitas 1 (Bit Data), Proporsi 1-C → Kapasitas 0 (Frozen Bits)"]
    end

Tabel Perbandingan Keluarga Kode Koreksi Kesalahan

6. Implementasi Lengkap Python: Hamming $(7,4)$ dan Reed-Solomon di $\text{GF}(2^8)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

from typing import List

def hamming74_demo() -> None:
    G = [[1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1]]
    H = [[1,1,0,1,1,0,0], [1,0,1,1,0,1,0], [0,1,1,1,0,0,1]]
    msg = [1, 0, 1, 1]
    c = [sum(msg[i] * G[i][j] for i in range(4)) % 2 for j in range(7)]
    y = c.copy()
    y[2] ^= 1
    s = [sum(H[r][col] * y[col] for col in range(7)) % 2 for r in range(3)]
    err_idx = next(col for col in range(7) if [H[r][col] for r in range(3)] == s)
    y[err_idx] ^= 1
    print(f"[Hamming (7,4)] Syndrome={s} -> Flipped idx={err_idx}, Recovered={y[:4] == msg}")

class GF256:
    def __init__(self, poly: int = 0x11D) -> None:
        self.exp, self.log = [0] * 512, [0] * 256
        v = 1
        for i in range(255):
            self.exp[i] = self.exp[i + 255] = v
            self.log[v] = i
            v <<= 1
            if v & 0x100:
                v ^= poly

    def mul(self, a: int, b: int) -> int:
        return 0 if (a == 0 or b == 0) else self.exp[self.log[a] + self.log[b]]

    def inv(self, a: int) -> int:
        return self.exp[255 - self.log[a]]

    def power(self, a: int, p: int) -> int:
        return 1 if p == 0 else (0 if a == 0 else self.exp[(self.log[a] * p) % 255])

    def eval_poly(self, coeffs: List[int], x: int) -> int:
        res = 0
        for c in reversed(coeffs):
            res = self.mul(res, x) ^ c
        return res

    def solve(self, A: List[List[int]], b: List[int]) -> List[int]:
        n = len(b)
        M = [row[:] + [b[i]] for i, row in enumerate(A)]
        for col in range(n):
            piv = next(r for r in range(col, n) if M[r][col] != 0)
            M[col], M[piv] = M[piv], M[col]
            inv_p = self.inv(M[col][col])
            for j in range(col, n + 1):
                M[col][j] = self.mul(M[col][j], inv_p)
            for r in range(n):
                if r != col and M[r][col] != 0:
                    f = M[r][col]
                    for j in range(col, n + 1):
                        M[r][j] ^= self.mul(f, M[col][j])
        return [M[i][n] for i in range(n)]

def rs_demo() -> None:
    gf = GF256()
    text = "VOYAGER-1"
    k, t = len(text), 3
    n = k + 2 * t
    pts = [gf.exp[i] for i in range(n)]
    cw = [gf.eval_poly([ord(c) for c in text], x) for x in pts]
    rx = cw.copy()
    rx[1] ^= 0xFF; rx[6] ^= 0xA5; rx[13] ^= 0x3C
    A = [[gf.power(pts[i], d) for d in range(k + t)] + [gf.mul(rx[i], gf.power(pts[i], d)) for d in range(t)] for i in range(n)]
    b = [gf.mul(rx[i], gf.power(pts[i], t)) for i in range(n)]
    sol = gf.solve(A, b)
    E = sol[k + t:] + [1]
    err_pos = [i for i, x in enumerate(pts) if gf.eval_poly(E, x) == 0]
    valid = [(pts[i], rx[i]) for i in range(n) if i not in err_pos][:k]
    rec = gf.solve([[gf.power(x, d) for d in range(k)] for x, _ in valid], [y for _, y in valid])
    print(f"[RS(15,9) over GF(2^8)] Located Errors={err_pos}, Recovered='{''.join(chr(c) for c in rec)}'")

if __name__ == "__main__":
    hamming74_demo()
    rs_demo()

7. Kesimpulan

Dari batas Shannon $-1,59\,\text{dB}$ (1948) hingga geometri Hamming (1950), interpolasi polinomial Reed-Solomon di atas $\mathbb{F}_{2^m}$ (1960), hingga propagasi kepercayaan LDPC dan polarisasi kanal Arıkan — teori pengkodean membuktikan bagaimana matematika murni mampu mengalahkan derau termal dan entropi fisik alam semesta.