1. Introdução: Dois milagres cotidianos de ressurreição da informação

Tanto nas profundezas do espaço interestelar quanto na câmera do seu smartphone, a engenharia digital realiza diariamente uma façanha que parece desafiar a intuição física: reconstruir com 100% de precisão, bit a bit, informações digitais cujo sinal ou mídia física foi severamente mutilado pelo ruído térmico ou destruição parcial.

Milagre 1: Voyager 1 e 2 transmitindo a 24 bilhões de quilômetros com $10^{-16}\text{ watts}$

Lançadas em 1977, as sondas Voyager 1 e Voyager 2 fotografaram Júpiter, Saturno, Urano e Netuno e hoje viajam pelo espaço interestelar a mais de 24 bilhões de quilômetros da Terra. O transmissor de rádio da Voyager opera com apenas $23\text{ watts}$ — menos que a lâmpada de uma geladeira. Quando o sinal alcança as antenas de 70 metros da Deep Space Network (DSN) da NASA na Terra, a potência recebida caiu para cerca de $10^{-16}\text{ watts}$ ($0,1\text{ atowatts}$), submersa no ruído térmico. Ainda assim, a Voyager entregou imagens coloridas perfeitas com zero erros de bit.

Milagre 2: Um código QR com $30\%$ de seus módulos cobertos por café ou um logotipo

Da mesma forma, ao apontar o celular para um código QR manchado de café ou com um logotipo cobrindo até $30\%$ de sua área central, seu smartphone reconstrói a URL exata em menos de $10\text{ milissegundos}$ com zero bits errados.

  flowchart TD
    subgraph Voyager["Telemetria do Espaço Profundo (Voyager 1 e 2)"]
        V1["Imagem planetária (k bits)"] --> V2["Codificação concatenada (RS externo + Convolucional/LDPC interno)"]
        V2 --> V3["Transmissor de 23 W por bilhões de km (10⁻¹⁶ W recebidos)"]
        V3 --> V4["Ruído branco gaussiano (AWGN) e inversão de bits"]
        V4 --> V5["Viterbi suave / Propagação de crenças + Decodificação RS"]
        V5 --> V6["Retrato planetário nítido (Zero erros de bit)"]
    end
    subgraph QR["Leitura diária de Códigos QR"]
        Q1["URL / Dados úteis (k bytes)"] --> Q2["Codificação Reed-Solomon em GF(2⁸) (n bytes)"]
        Q2 --> Q3["Mancha de café ou logotipo destrói 30% dos módulos"]
        Q3 --> Q4["Cálculo de síndromes + Algoritmo de Berlekamp-Massey"]
        Q4 --> Q5["Busca de Chien + Fórmula de Forney (10 ms)"]
        Q5 --> Q6["Reconstrução exata a 100%"]
    end

Como isso é matematicamente possível? Graças à Teoria da Informação de Claude Shannon (1948) e à ciência algébrica dos códigos corretores de erros (ECC).

2. A revolução de Claude Shannon (1948) e o teorema de codificação de canal ruidoso

2.1 Por que a codificação por repetição ingênua ($0 \to 00000$) falha

Quando $n \to \infty$, temos $P_e^{(n)} \to 0$, mas simultaneamente a taxa de código entra em colapso: $R = k/n = 1/n \to 0$.

2.2 O teorema de Shannon e o limite último de Shannon ($-1,59\,\text{dB}$)

Em 1948, Claude E. Shannon provou em “A Mathematical Theory of Communication” seu famoso teorema de codificação de canal ruidoso:

Teorema (Codificação de canal de Shannon, 1948): Todo canal sem memória possui uma capacidade de canal $C > 0$ estritamente positiva:

• Para o canal binário simétrico (BSC) com entropia binária $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{bits / uso do canal}]$$
• Para o canal AWGN de largura de banda $B$, potência de sinal $S$ e ruído $N = N_0 B$ (teorema de 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{bits / s}]$$

Para qualquer taxa $R < C$, existem códigos de bloco de comprimento $n \to \infty$ com probabilidade de erro arbitrariamente pequena ($P_e \to 0$)!

3. O avanço geométrico de Richard Hamming (1950): distância de Hamming e o código $[7, 4, 3]$

3.1 Distância de Hamming $d_H(\mathbf{u}, \mathbf{v})$ e limite de empacotamento de esferas

Para um código $\mathcal{C} \subset \mathbb{F}_q^n$ com distância mínima $d_{\min} = \min_{\mathbf{u}\neq\mathbf{v}} d_H(\mathbf{u},\mathbf{v})$, as esferas de Hamming disjuntas de raio $t$ provam que o código pode:

• Detectar $d_{\min} - 1$ erros;
• Corrigir $e = d_{\min} - 1$ apagamentos (erasures) em posições conhecidas;
• Corrigir $t = \lfloor(d_{\min} - 1)/2\rfloor$ erros arbitrários em posições desconhecidas: $$\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{(Limite de Hamming)}$$

3.2 O código perfeito de Hamming $(7,4)$ e a decodificação por síndrome

A síndrome de 3 bits $\mathbf{s} = \mathbf{H}\mathbf{y}^T = \mathbf{H}(\mathbf{c} + \mathbf{e})^T = \mathbf{H}\mathbf{e}^T \pmod 2$ extrai diretamente a coluna de $\mathbf{H}$ correspondente ao bit invertido: ordenando as colunas em binário de $1$ a $7$, a síndrome $\mathbf{s}$ fornece diretamente o índice binário $(1 \dots 7)$ do bit corrompido, protegendo hoje toda a memória ECC DRAM de servidores.

4. A obra-prima de Reed e Solomon (1960): códigos Reed-Solomon sobre corpos de Galois $\mathbb{F}_{2^m}$

4.1 Corpos de Galois $\text{GF}(2^8)$ e imunidade contra erros em rajada (Burst Errors)

Para vencer erros em rajada (arranhões em discos, manchas em códigos QR), Irving Reed e Gustave Solomon (1960) agruparam cada byte ($m=8$ bits) como um único símbolo do corpo finito $\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$. Mesmo que todos os 8 bits de um byte sejam destruídos, em $\text{GF}(2^8)$ isso representa apenas um único erro de símbolo!

4.2 Interpolação polinomial e o limite de Singleton MDS $d_{\min} = n - k + 1$

Assim, $n - k$ bytes de paridade corrigem até $e = n - k$ apagamentos (RAID-6, armazenamento em nuvem) ou até $t = \lfloor(n-k)/2\rfloor$ erros em posições desconhecidas (códigos QR até 30% no nível H; sonda Voyager $[255, 223]$) via polinômio gerador cíclico $g(x) = \prod_{i=1}^{2t}(x - \alpha^i)$, algoritmo de Berlekamp-Massey / Euclides ($\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$), busca de Chien e fórmula de Forney.

5. Aproximando-se do limite de Shannon: códigos LDPC (1962), Turbo (1993) e Polares (2009)

1. Códigos LDPC de Robert Gallager (1962): utilizam uma matriz de paridade esparsa $\mathbf{H}$ e um grafo bipartido de Tanner. Mediante a troca iterativa de razões de verossimilhança logarítmica suaves $L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}$ com propagação de crenças (Belief Propagation / Sum-Product), os códigos LDPC operam a apenas $0,0045\,\text{dB}$ do limite de Shannon (canais de dados 5G NR, Wi-Fi 6/7 e SSDs 3D NAND).
2. Códigos Polares de Erdal Arıkan (2009): aplicando recursivamente a potência de Kronecker $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$, a polarização de canal faz com que uma fração $C = I(W)$ dos subcanais sintéticos convirja para capacidade $1$ (sem ruído, bits de informação) e uma fração $1 - C$ para capacidade $0$ (bits congelados / Frozen Bits $= 0$), sendo os primeiros códigos com complexidade $O(N \log N)$ que atingem de forma matematicamente comprovada a capacidade de Shannon (canais de controle 5G NR).

  flowchart TD
    subgraph CapPT["Códigos modernos que atingem a capacidade de Shannon"]
        L1["Códigos LDPC (Grafo bipartido esparso de Tanner)"] --> L2["Troca iterativa de mensagens LLR suaves"]
        L2 --> L3["Propagação de crenças Sum-Product (a 0,0045 dB do limite de Shannon)"]
        P1["Códigos Polares (Transformação de Kronecker G_N = B_N F^{⊗m})"] --> P2["Polarização em subcanais W⁻ (degradados) e W⁺ (aprimorados)"]
        P2 --> P3["Fração C → Capacidade 1 (Bits de dados), Fração 1-C → Capacidade 0 (Bits congelados)"]
    end

Tabela comparativa das principais famílias de códigos corretores de erros

6. Implementação completa em Python: Hamming $(7,4)$ e Reed-Solomon em $\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. Conclusão

Do limite de Shannon de $-1,59\,\text{dB}$ (1948) à geometria de Hamming (1950), à interpolação polinomial de Reed-Solomon sobre $\mathbb{F}_{2^m}$ (1960), até a propagação de crenças LDPC e a polarização de canal de Arıkan, a teoria dos códigos corretores mostra como a matemática pura vence o ruído térmico e a entropia do universo.