1. Введение: два повседневных и одновременно невероятных чуда восстановления информации

Как в глубинах межзвездного пространства, так и в камере вашего смартфона современная цифровая инженерия ежедневно совершает то, что кажется нарушением физической интуиции: 100%-ное побитовое восстановление цифровых данных из сигналов или носителей, серьезно поврежденных тепловым шумом, царапинами или физическим разрушением.

Чудо 1: «Вояджер-1» и «Вояджер-2» вещают с 24 миллиардов километров при мощности \(10^{-16}\text{ Вт}\)

Запущенные в 1977 году зонды Voyager 1 и Voyager 2 передали детальные снимки Юпитера, Сатурна, Урана и Нептуна и сегодня находятся в межзвездном пространстве на расстоянии более 24 миллиардов километров от Земли. Мощность радиопередатчика «Вояджера» составляет всего \(23\text{ Вт}\) — меньше, чем у лампочки в бытовом холодильнике. Когда эта электромагнитная волна достигает 70-метровых антенн Сети дальней космической связи НАСА (DSN) на Земле, принимаемая мощность падает до \(10^{-16}\text{ Вт}\) (\(0,1\text{ аттоватта}\)), полностью утопая в тепловом шуме (шуме Джонсона — Найквиста). Тем не менее «Вояджер» передал кристально четкие цветные фотографии Большого красного пятна Юпитера и атмосферы Нептуна с нулевым числом неисправимых битовых ошибок.

Чудо 2: QR-код, на \(30\,\%\) закрытый пятном кофе или логотипом компании

А теперь взгляните на QR-код, угол которого залит кофе или центральные \(30\,\%\) площади которого намеренно перекрыты логотипом бренда. Менее чем за \(10\text{ миллисекунд}\) камера смартфона восстанавливает точный URL или платежный токен с нулем ошибочных битов (Zero Bit Errors).

  flowchart TD
    subgraph Voyager["Дальняя космическая связь (Вояджер-1 и 2)"]
        V1["Данные изображения планеты (k бит)"] --> V2["Каскадное кодирование (внешний код РС + внутренний сверточный/LDPC)"]
        V2 --> V3["Передатчик 23 Вт через миллиарды км (прием 10⁻¹⁶ Вт)"]
        V3 --> V4["Аддитивный белый гауссовский шум (AWGN) и инверсии битов"]
        V4 --> V5["Мягкое декодирование Витерби / распространение доверия + РС"]
        V5 --> V6["Четкий портрет планеты (Ноль битовых ошибок)"]
    end
    subgraph QR["Мгновенное сканирование QR-кода"]
        Q1["URL / Полезные данные (k байт)"] --> Q2["Кодирование Рида — Соломона над GF(2⁸) (n байт)"]
        Q2 --> Q3["Пятно кофе или логотип уничтожает 30% модулей"]
        Q3 --> Q4["Вычисление синдромов + Алгоритм Берлекэмпа — Месси"]
        Q4 --> Q5["Поиск Ченя + Формула Форни (10 мс)"]
        Q5 --> Q6["100% точное восстановление исходных байтов"]
    end

Как это возможно математически? Ответ кроется в теории информации Клода Шеннона (1948) и алгебре кодов, исправляющих ошибки (Error-Correcting Codes, ECC).

2. Революция Клода Шеннона (1948) и теорема о кодировании для канала с шумом

2.1 Почему наивный код с повторением (\(0 \to 00000\)) терпит крах

При \(n \to \infty\) величина \(P_e^{(n)} \to 0\), но одновременно кодовая скорость обрушивается в ноль: \(R = k/n = 1/n \to 0\).

2.2 Теорема Шеннона и фундаментальный предел Шеннона (\(-1,59\,\text{дБ}\))

В 1948 году Клод Шеннон опубликовал работу «Математическая теория связи» и доказал обратное:

Теорема (Теорема Шеннона о кодировании для канала с шумом, 1948): Каждый канал без памяти обладает строго положительной пропускной способностью канала \(C > 0\):

• Для двоичного симметричного канала (BSC) с двоичной функцией энтропии \(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{бит / использование}]\)
• Для канала с АБГШ (AWGN) ширины полосы \(B\), мощности сигнала \(S\) и мощности шума \(N = N_0 B\) (теорема Шеннона — Хартли): \(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{бит / с}]\)

Для любой скорости передачи \(R < C\) существуют блоковые коды длины \(n \to \infty\), обеспечивающие сколь угодно малую вероятность ошибки декодирования (\(P_e \to 0\))!

3. Геометрический прорыв Ричарда Хэмминга (1950): расстояние Хэмминга и код \([7, 4, 3]\)

3.1 Расстояние Хэмминга \(d_H(\mathbf{u}, \mathbf{v})\) и граница сферической упаковки

Для кода \(\mathcal{C} \subset \mathbb{F}_q^n\) с минимальным расстоянием \(d_{\min} = \min_{\mathbf{u}\neq\mathbf{v}} d_H(\mathbf{u},\mathbf{v})\) геометрия непересекающихся сфер Хэмминга радиуса \(t\) доказывает, что код способен:

• Обнаруживать \(d_{\min} - 1\) ошибок;
• Исправлять \(e = d_{\min} - 1\) стираний (erasures) на известных позициях;
• Исправлять \(t = \lfloor(d_{\min} - 1)/2\rfloor\) произвольных ошибок на неизвестных позициях: \(\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{(Граница Хэмминга)}\)

3.2 Совершенный код Хэмминга \((7,4)\) и синдромное декодирование

Трехбитный синдром \(\mathbf{s} = \mathbf{H}\mathbf{y}^T = \mathbf{H}(\mathbf{c} + \mathbf{e})^T = \mathbf{H}\mathbf{e}^T \pmod 2\) выделяет столбец матрицы \(\mathbf{H}\), соответствующий позиции перевернутого бита: при двоичном упорядочении столбцов от \(1\) до \(7\) синдром \(\mathbf{s}\) напрямую выдает двоичный номер \((1 \dots 7)\) поврежденного бита! Эта схема защищает всю серверную память ECC DRAM (SECDED).

4. Шедевр Рида и Соломона (1960): коды Рида — Соломона над полями Галуа \(\mathbb{F}_{2^m}\)

4.1 Поля Галуа \(\text{GF}(2^8)\) и защита от пакетов ошибок (Burst Errors)

Для борьбы с пакетами ошибок (царапины на дисках, пятна на QR-кодах) Ирвинг Рид и Густав Соломон (1960) объединили каждые \(m=8\) бит (1 байт) в единый символ конечного поля Галуа \(\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)\). Даже если все 8 битов внутри одного байта искажены, в поле \(\text{GF}(2^8)\) это всего одна символьная ошибка!

4.2 Полиномиальная интерполяция и граница Синглтона MDS \(d_{\min} = n - k + 1\)

Добавление \(n - k\) проверочных байтов позволяет исправить до \(e = n - k\) стираний (RAID-6, облачные хранилища) или до \(t = \lfloor(n-k)/2\rfloor\) ошибок в неизвестных позициях (QR-коды до 30% площади на уровне H; код \([255, 223]\) на «Вояджере») с помощью порождающего многочлена \(g(x) = \prod_{i=1}^{2t}(x - \alpha^i)\), алгоритма Берлекэмпа — Месси / Евклида (\(\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}\)), поиска Ченя и формулы Форни.

5. Вплотную к пределу Шеннона: LDPC-коды (1962), турбо-коды (1993) и полярные коды (2009)

1. LDPC-коды Роберта Галлагера (1962): задаются разреженной проверочной матрицей \(\mathbf{H}\) и двудольным графом Таннера. Итеративное декодирование методом распространения доверия (Belief Propagation / Sum-Product) с мягкими логарифмическими отношениями правдоподобия \(L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}\) приближается к пределу Шеннона на \(0,0045\,\text{дБ}\) (каналы данных 5G NR, Wi-Fi 6/7, контроллеры 3D NAND SSD).
2. Полярные коды Эрдала Арыкана (Polar Codes, 2009): рекурсивное применение кронекеровой степени \(\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}\) вызывает поляризацию канала — при \(N \to \infty\) доля \(C = I(W)\) синтетических подканалов стремится к пропускной способности \(1\) (без шума, информационные биты), а доля \(1 - C\) — к \(0\) (замороженные биты / Frozen Bits \(= 0\)). Это первые конструктивные коды со сложностью \(O(N \log N)\), математически доказанно достигающие пропускной способности Шеннона (каналы управления 5G NR).

  flowchart TD
    subgraph CapRU["Современные коды, достигающие предела Шеннона"]
        L1["LDPC-коды (Разреженный двудольный граф Таннера)"] --> L2["Итеративный обмен мягкими LLR-сообщениями"]
        L2 --> L3["Belief Propagation Sum-Product (в 0,0045 дБ от предела Шеннона)"]
        P1["Полярные коды (Преобразование Кронекера G_N = B_N F^{⊗m})"] --> P2["Поляризация на подканалы W⁻ (ухудшенные) и W⁺ (улучшенные)"]
        P2 --> P3["Доля C → Емкость 1 (Данные), Доля 1-C → Емкость 0 (Замороженные биты)"]
    end

Сравнительная таблица семейств кодов коррекции ошибок

6. Полная реализация на Python: код Хэмминга \((7,4)\) и Рида — Соломона над \(\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. Заключение

От предела Шеннона \(-1,59\,\text{дБ}\) (1948) до геометрии Хэмминга (1950), интерполяции Рида — Соломона над полями Галуа \(\mathbb{F}_{2^m}\) (1960), графов Таннера LDPC и поляризации каналов Арыкана — теория кодирования демонстрирует триумф чистой математики над тепловым хаосом и физической энтропией Вселенной.