В 1992 году первый GSM-звонок прошёл по цифровому каналу с BER около 10⁻³ — и всё равно был разборчивым. Сейчас 5G держит BER ниже 10⁻⁵ при вдвое меньшей энергии. За 30 лет не изменились ни физика канала, ни формула Шеннона — изменились коды.

Каждое поколение сотовой связи — это смена схемы помехоустойчивого кодирования:

1G (1981): аналог, никакого канального кодирования 2G GSM (1992): свёрточный код R=1/2, K=5 + декодер Витерби 2G IS-95 / CDMA (1995): свёрточный R=1/2, K=9, полиномы [753 561] 3G UMTS (2001): турбо-коды (PCCC, R=1/3) — прыжок BER на 3–4 дБ 4G LTE (2009): турбо + хвостово-скусанные свёрточные для управляющих каналов 5G NR (2019): LDPC для данных (eMBB), полярные коды для управления

Статья идёт по этой цепочке. К каждому коду — числовой пример, рабочий MATLAB-скрипт и BER-кривая, а в финале — всё на одном графике.

Модель канала: BSC и BPSK+AWGN

Прежде чем говорить о кодах, нужно договориться о том, что мы моделируем. «Канал с помехами» — понятие широкое. В теории кодирования используют две главные модели, и они устроены принципиально по-разному.

Двоичный симметричный канал (BSC)

Самая простая модель: каждый бит независимо с вероятностью p переворачивается (0→1 или 1→0). Параметр p — вероятность ошибки на бит.

BSC удобен для теоретических расчётов и простых симуляций, но он слишком грубый: в реальном эфире биты не переворачиваются случайно и независимо — сигнал тонет в шуме, и решение «0 это или 1» принимает приёмник.

% Генерация ошибок в BSC с вероятностью p
p = 0.01;
bits     = randi([0 1], 1, 1000);
errors   = rand(1, 1000) < p;
received = xor(bits, errors);

BPSK + AWGN

Более реалистичная модель — BPSK в канале с белым гауссовым шумом. Здесь мы уже моделируем физический уровень передачи.

Бит 0 передаётся как −1, бит 1 — как +1. По эфиру летит аналоговый сигнал. Шум добавляет случайное смещение к каждому отсчёту, и если смещение достаточно большое — приёмник принимает неверное решение. Это принципиально отличается от BSC: там ошибки «случаются» с заданной вероятностью, здесь они возникают из физики сигнала.

Eb/N0 — отношение энергии бита к спектральной плотности мощности шума. По смыслу: насколько сигнал «громче» шума. Чем выше Eb/N0 — тем меньше ошибок. Это универсальная ось X для всех BER-кривых в статье.

Почему именно Eb/N0, а не просто SNR? Потому что Eb/N0 позволяет сравнивать системы с разной скоростью кодирования честно. Код с R=1/2 тратит вдвое больше энергии на передачу одного информационного бита — и Eb/N0 это учитывает автоматически.

BER (Bit Error Rate) — доля ошибочно принятых бит. При BPSK без кодирования:

где Q(x) — функция хвоста нормального распределения. При Eb/N0 = 6 дБ получаем BER ≈ 10⁻³. При 10 дБ — уже 10⁻⁵. Это и есть базовая линия, с которой мы будем сравнивать все коды.

EbN0_dB = 0:1:10;
EbN0    = 10.^(EbN0_dB/10);
BER_ref = qfunc(sqrt(2*EbN0));

figure;
semilogy(EbN0_dB, BER_ref, 'k--', 'LineWidth', 2);
grid on;
xlabel('Eb/N0, дБ'); ylabel('BER');
title('BPSK без кодирования');

Дальше накладываем на эту кривую результаты кодированных систем — смотрим, на сколько дБ каждый код сдвигает её влево. Сдвиг влево на X дБ означает: «при той же вероятности ошибки нам нужно в X дБ меньше мощности передатчика» — или, что то же самое, «при той же мощности мы получаем на порядки меньше ошибок».

Код Хэмминга (7,4): с чего всё начинается

Хэмминг — не сотовый код. Но именно с него начинается понимание всего остального.

В 1950 году Ричард Хэмминг работал в Bell Labs и каждый раз, когда в его программе была ошибка, машина останавливалась и нужно было перезапускать с начала. Он придумал код, который не просто обнаруживает ошибку, но и исправляет её на лету. Этот принцип — синдромное декодирование — живёт сегодня внутри BCH, свёрточных и LDPC-кодов в разных обличьях.

Как это работает

Код Хэмминга (7,4) берёт 4 информационных бита и добавляет 3 проверочных — итого 7. Код исправляет одну ошибку в блоке из 7 бит.

Ключевая идея: проверочные биты расставляются так, что по их значениям на приёмнике можно не просто понять «ошибка есть», но и узнать точный номер позиции, где она случилась.

Проверочные биты стоят на позициях 1, 2, 4 (степени двойки). Каждый «отвечает» за определённое подмножество позиций:

p1 (позиция 1) проверяет позиции: 1, 3, 5, 7 p2 (позиция 2) проверяет позиции: 2, 3, 6, 7 p4 (позиция 4) проверяет позиции: 4, 5, 6, 7

Информационные биты — позиции 3, 5, 6, 7.

Выбор подмножеств не случаен: если посмотреть на двоичные записи номеров позиций, то p1 отвечает за позиции с единицей в первом бите, p2 — с единицей во втором бите, p4 — с единицей в третьем. Именно поэтому синдром из трёх проверок напрямую даёт двоичный номер ошибочной позиции.

Числовой пример

Кодируем d = [1 0 1 1] (биты d1…d4).

Расстановка: [_,_ ,_ 1,_ , 0, 1, 1] (позиции 1, 2, 4 пустые).

Проверочные биты (XOR): p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0 p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1 p4 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0

Кодовое слово: [0, 1, 1, 0, 0, 1, 1].

Ошибка в позиции 5: [0, 1, 1, 0, 1, 1, 1]. На приёмнике считаем синдром: s1 = r1 ⊕ r3 ⊕ r5 ⊕ r7 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1 s2 = r2 ⊕ r3 ⊕ r6 ⊕ r7 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 s4 = r4 ⊕ r5 ⊕ r6 ⊕ r7 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1

Синдром [s1, s2, s4] = [1, 0, 1] → число 5 в двоичной записи. Ошибка на позиции 5. Инвертируем бит — готово.

Заметьте: нам не нужно перебирать все возможные ошибки. Синдром — это трёхбитный «адрес» ошибки, вычисленный за одну операцию.

MATLAB-симуляция BER:

% hamming_ber.m — BER-симуляция кода Хэмминга (7,4)
clear; clc;

EbN0_dB  = 0:1:10;
n_bits   = 100000;
rate     = 4/7;

BER_hamming = zeros(1, length(EbN0_dB));
BER_uncoded = zeros(1, length(EbN0_dB));

H = [1 0 1 0 1 0 1;
     0 1 1 0 0 1 1;
     0 0 0 1 1 1 1];

syndrome_table = zeros(1, 8);
for i = 1:7
    e = zeros(7,1); e(i) = 1;
    s = mod(H * e, 2);
    syndrome_table(s(1)*4 + s(2)*2 + s(3) + 1) = i;
end

for k = 1:length(EbN0_dB)
    EbN0  = 10^(EbN0_dB(k)/10);
    sigma = sqrt(1 / (2 * rate * EbN0));
    n_blocks = floor(n_bits / 4);
    err_coded = 0; err_unc = 0;

    for b = 1:n_blocks
        d = randi([0 1], 4, 1);
        cw = zeros(7, 1); cw([3 5 6 7]) = d;
        cw(1) = mod(cw(3)+cw(5)+cw(7), 2);
        cw(2) = mod(cw(3)+cw(6)+cw(7), 2);
        cw(4) = mod(cw(5)+cw(6)+cw(7), 2);

        rx = 2*cw - 1 + sigma*randn(7,1);
        rb = double(rx > 0);

        s = mod(H*rb, 2);
        si = s(1)*4 + s(2)*2 + s(3) + 1;
        if si > 1 && syndrome_table(si) > 0
            rb(syndrome_table(si)) = 1 - rb(syndrome_table(si));
        end
        err_coded = err_coded + sum(rb([3 5 6 7]) ~= d);

        sigma0 = sqrt(1/(2*EbN0));
        err_unc = err_unc + sum((2*d-1 + sigma0*randn(4,1) > 0) ~= d);
    end

    BER_hamming(k) = err_coded / (n_blocks * 4);
    BER_uncoded(k) = err_unc   / (n_blocks * 4);
end

figure;
semilogy(EbN0_dB, BER_uncoded, 'k--', 'LineWidth', 2); hold on;
semilogy(EbN0_dB, BER_hamming, 'b-o', 'LineWidth', 2);
grid on; ylim([1e-5 1]);
legend('Без кодирования', 'Хэмминг (7,4)', 'Location', 'southwest');
xlabel('Eb/N0, дБ'); ylabel('BER');
title('BER: Хэмминг (7,4)');

Хэмминг (7,4) исправляет ровно одну ошибку на блок. Две ошибки — декодер укажет на неправильную позицию и сделает хуже, чем если бы не исправлял вовсе. Это принципиальное ограничение однократно-исправляющих кодов: при высоком уровне шума они перестают помогать. Для GSM, где замирание канала может портить подряд несколько бит, нужно что-то другое.

BCH-коды и GSM: когда ошибок больше одной

Хэмминг хорош для ECC-памяти, где ошибки редки и одиночны. Радиоканал устроен иначе — там ошибки приходят пачками. Нужен код, который держит t ошибок, а не одну. BCH-коды — обобщение Хэмминга именно для этого случая.

Принцип:

BCH (Боуз — Чоудхури — Хоквингем, 1959–1960) строятся над конечными полями GF(2^m). Вместо того чтобы придумывать проверочные биты интуитивно, как Хэмминг, BCH используют алгебраический аппарат: проверочная матрица конструируется так, что её строки охватывают все комбинации до t ошибок.

Проверочная часть длиной не более m·t бит гарантирует исправление t ошибок в блоке длиной до 2^m − 1. Пример: BCH(15,7) при m=4 исправляет t=2 ошибки. Кодовая скорость 7/15 ≈ 0.47 — вдвое «тяжелее» Хэмминга, зато держит две одиночные ошибки в блоке.

На декодере вместо таблицы синдромов работает алгоритм Берлекэмпа–Месси: он находит полином локаторов ошибок — многочлен, корни которого — позиции ошибок в кодовом слове. По сложности это уже не «посмотрели в таблицу», а итерационный алгоритм, но всё ещё без итераций над графом, как в LDPC.

Роль в GSM

В GSM управляющие каналы (SCH, BCCH) защищены FIRE-кодом — частным случаем BCH(23,12). Он исправляет один пакет ошибок длиной до 11 бит в блоке.

Почему именно пакет, а не одиночные ошибки? Потому что управляющий канал передаётся в одном бёрсте длиной 148 бит. Замирание — это физическое явление: сигнал на долю миллисекунды «пропадает», и в этот момент теряется кусок бёрста целиком. Несколько бит подряд, не по одному. FIRE-код создан именно под это.

Речевые каналы (TCH) защищены по-другому: там свёрточный код плюс перемежение по нескольким бёрстам. Об этом — в следующем разделе.

MATLAB-симуляция BER:

% bch_ber.m — BER-симуляция BCH(15,7)
clear; clc;

n = 15; k = 7;
EbN0_dB = 0:1:10;
n_bits  = 140000;
rate    = k/n;

enc = comm.BCHEncoder(n, k);
dec = comm.BCHDecoder(n, k);

BER_bch = zeros(1, length(EbN0_dB));
BER_unc = zeros(1, length(EbN0_dB));

for idx = 1:length(EbN0_dB)
    EbN0  = 10^(EbN0_dB(idx)/10);
    sigma = sqrt(1 / (2*rate*EbN0));
    n_blocks = floor(n_bits / k);
    err_coded = 0; err_unc = 0;

    for b = 1:n_blocks
        d  = randi([0 1], k, 1);
        cw = enc(d);

        rx      = 2*cw - 1 + sigma*randn(n, 1);
        dec_out = dec(double(rx > 0));
        err_coded = err_coded + sum(dec_out ~= d);

        sigma0  = sqrt(1/(2*EbN0));
        err_unc = err_unc + sum((2*d-1 + sigma0*randn(k,1) > 0) ~= d);
    end

    BER_bch(idx) = err_coded / (n_blocks * k);
    BER_unc(idx) = err_unc   / (n_blocks * k);
end

figure;
semilogy(EbN0_dB, BER_unc, 'k--', 'LineWidth', 2); hold on;
semilogy(EbN0_dB, BER_bch, 'r-s', 'LineWidth', 2);
grid on; ylim([1e-5 1]);
legend('Без кодирования', 'BCH(15,7)', 'Location', 'southwest');
xlabel('Eb/N0, дБ'); ylabel('BER');
title('BER: BCH(15,7)');

Это лучше Хэмминга, но прирост всё равно скромный — и причина понятна: BCH декодирует по жёсткому решению. Приёмник сначала говорит «это 0 или 1», и только потом декодер смотрит на биты. Аналоговая уверенность («очень похоже на 0» против «еле-еле 0») выброшена. Следующий шаг в эволюции кодов — научить декодер работать с сырым аналоговым сигналом. Свёрточный код с декодером Витерби — первый, кто это умеет по-настоящему.

Свёрточный код: основа 2G

Память и решётка

Хэмминг и BCH — блоковые коды: берём блок бит, добавляем проверочные, передаём. Следующий блок обрабатывается независимо.

Свёрточный код устроен иначе: у него есть память. Кодер — конечный автомат с несколькими регистрами сдвига. Каждый входной бит сдвигает содержимое регистров, и выходные биты — XOR разных комбинаций регистров. Текущий выход зависит от текущего входа и от нескольких предыдущих.

Параметр K — «длина ограничения» (constraint length): кодер «помнит» K−1 предыдущих бит. При K=7, как в наших симуляциях, кодер хранит состояние из 6 бит — итого 2⁶ = 64 возможных состояния.

Граф переходов между состояниями кодера называется решёткой (trellis). Решётка разворачивается во времени: каждый столбец — момент прихода нового бита, каждый узел — состояние кодера, каждое ребро — переход при 0 или 1. Метка на ребре — пара выходных бит.

Почему это лучше блокового кода? Потому что избыточность «размазана» по времени: один кодовый бит содержит информацию о нескольких входных. Декодер видит длинную последовательность и ищет самый правдоподобный путь по решётке — он использует контекст, а не обрабатывает биты изолированно.

Декодер Витерби

Алгоритм Витерби (1967) — ключ к практическому использованию свёрточных кодов. Задача: по принятой последовательности найти путь по решётке с минимальным расстоянием до неё.

Наивный перебор всех путей — 2^N вариантов для N битов, нереально. Витерби использует динамическое программирование: на каждом шаге для каждого состояния хранится только один «выживший» путь — тот, что ближе всего к принятому сигналу. Остальные отбрасываются. Сложность — O(N · 2^K), линейная по времени.

Два режима работы декодера:

Жёсткое решение (hard decision): приёмник сначала квантует сигнал в 0 или 1. Декодер Витерби считает расстояние Хэмминга — число несовпадающих позиций между принятой и предсказанной последовательностью. Аналоговая уверенность потеряна: бит «0.9» и бит «0.1» для декодера одинаковы.

Мягкое решение (soft decision, ‘unquant’): декодер получает сырые аналоговые отсчёты с приёмника — без квантования. Витерби считает евклидово расстояние: отсчёт +0.9 и +0.1 — оба говорят «бит 0», но первый гораздо убедительнее. Эта разница и даёт около 2 дБ выигрыша при одинаковом кодере — просто потому что декодер получает больше информации о канале.

В MATLAB опция ‘unquant’ у vitdec означает именно мягкое решение: положительный отсчёт интерпретируется как бит 0, отрицательный — как бит 1. Важен знак: наш BPSK кодирует бит 0 как −1 (передаём 2·cw−1), поэтому декодеру передаём −rx, чтобы привести знаки в соответствие.

GSM TCH/FS: 260 бит каждые 20 мс

GSM-кодек RPE-LTP выдаёт 260 бит на один речевой фрейм (20 мс). Это не однородный поток — биты имеют разный вес для качества речи:

Class Ia (50 бит) — наиболее значимые: CRC(3) + свёрточный R=1/2, K=5 Class Ib (132 бита) — тот же кодер без CRC Class II (78 бит) — без защиты (LSB вокодера; их ошибки на слух почти не заметны)

Итого на выходе кодера: (50 + 3 + 132) × 2 + 78 = 456 бит. Затем они перемежаются по 8 бёрстам.

Перемежение — отдельный приём борьбы с пакетными ошибками. Логика такая: если бёрст целиком провалился в замирание, все биты из него потеряны. Но если биты одного речевого фрейма были размазаны по 8 бёрстам, то потеря одного бёрста — это всего 1/8 бит от каждого фрейма. Свёрточный декодер с такой плотностью ошибок справляется, а с потерей половины бёрста — нет.

GSM использует K=5. Но в стандарте IS-95 (2G CDMA) и 802.11 прижился K=7 с полиномами [171 133] (октальная запись) — именно их мы используем в симуляции. Constraint length 7 даёт 64 состояния против 32 у K=5 и примерно на 1 дБ лучше при том же R.

Образующие полиномы в двоичной записи: 171₈ = 1111001₂ → v1 = u(t) ⊕ u(t-2) ⊕ u(t-3) ⊕ u(t-5) ⊕ u(t-6) 133₈ = 1011011₂ → v2 = u(t) ⊕ u(t-1) ⊕ u(t-2) ⊕ u(t-3) ⊕ u(t-6)

MATLAB-симуляция BER

% conv_ber.m — BER свёрточного кода R=1/2, K=7, полиномы [171 133]
% Те же параметры, что в IS-95 и 802.11; в лабораторной работе — TbDepth=96
clear; clc;

EbN0_dB = 0:1:10;
n_bits  = 100000;
rate    = 1/2;

% poly2trellis(K, [g1 g2]):
%   K=7    — constraint length, кодер запоминает 6 предыдущих бит
%   171, 133 (окт) = 1111001, 1011011 (бин) — образующие полиномы
trel  = poly2trellis(7, [171 133]);
tblen = 96;  % traceback depth: рекомендуется ~5–10·K, здесь ~14·K

BER_hard = zeros(1, length(EbN0_dB));
BER_soft = zeros(1, length(EbN0_dB));
BER_unc  = zeros(1, length(EbN0_dB));

for idx = 1:length(EbN0_dB)
    EbN0  = 10^(EbN0_dB(idx)/10);
    sigma = sqrt(1 / (2*rate*EbN0));

    d  = randi([0 1], n_bits, 1);
    cw = convenc(d, trel);     % 1 инф. бит → 2 кодовых бита (R=1/2)

    tx = 2*cw - 1;             % BPSK: бит 0 → -1, бит 1 → +1
    rx = tx + sigma * randn(length(cw), 1);

    % Жёсткое: решение до декодера (rx > 0 → бит=1), теряем аналоговую инфо
    dec_hard = vitdec(double(rx > 0), trel, tblen, 'trunc', 'hard');
    BER_hard(idx) = sum(dec_hard ~= d) / n_bits;

    % Мягкое ('unquant'): аналоговые отсчёты прямо в декодер
    % vitdec ждёт: положительный → бит 0, отрицательный → бит 1
    % Но наш BPSK: бит 0 → tx=-1, значит знак обратный → передаём -rx
    dec_soft = vitdec(-rx, trel, tblen, 'trunc', 'unquant');
    BER_soft(idx) = sum(dec_soft ~= d) / n_bits;

    % Без кодирования
    sigma0 = sqrt(1/(2*EbN0));
    BER_unc(idx) = sum((2*d-1 + sigma0*randn(n_bits,1) > 0) ~= d) / n_bits;
end

figure;
semilogy(EbN0_dB, BER_unc,  'k--', 'LineWidth', 2); hold on;
semilogy(EbN0_dB, BER_hard, 'g-d', 'LineWidth', 2);
semilogy(EbN0_dB, BER_soft, 'b-o', 'LineWidth', 2);
grid on; ylim([1e-5 1]);
legend('Без кодирования', 'Свёрточный, жёсткое', 'Свёрточный, мягкое', ...
       'Location', 'southwest');
xlabel('Eb/N0, дБ'); ylabel('BER');
title('BER: свёрточный R=1/2, K=7 [171 133]');

Стоит обратить внимание на одну деталь графика: жёсткое декодирование при Eb/N0 < 2–3 дБ хуже некодированной BPSK. Кривая уходит вверх. Это не артефакт симуляции — это цена скорости: кодер удваивает число передаваемых бит, и при низком SNR этот «долг» не окупается. Мягкое декодирование пересекает некодированную кривую уже около 1 дБ, жёсткое — только после 3 дБ.

Но у свёрточного кода есть ограничение, которое видно на BER-кривой: она убывает плавно, без резкого «обрыва». Чтобы получить BER = 10⁻⁶, нужно ещё несколько децибел. В 3G началась передача видео и данных, где нужны и низкие BER, и высокая скорость — свёрточный код перестаёт быть достаточным. Нужен принципиально другой подход к декодированию.

Турбо-коды: 3G и 4G

В 1993 году Клод Берру и Ален Главьё на конференции ICC представили доклад, который сначала приняли скептически: авторы утверждали, что их код работает в пределах 0.5 дБ от предела Шеннона. Это казалось невозможным — граница Шеннона была теоретической абстракцией, недостижимой практически.

Код назвали турбо — за аналогию с турбонаддувом в двигателях, где выхлоп одной ступени раскручивает другую.

Как устроен турбо-код?

Идея — параллельная конкатенация двух рекурсивных систематических свёрточных кодеров (PCCC):

1. Первый RSC-кодер обрабатывает исходные биты.

2. Перемежитель перемешивает те же биты в другом порядке.

3. Второй RSC-кодер обрабатывает перемешанную последовательность.

На выход идут: исходные биты + проверочные от первого кодера + проверочные от второго. Скорость обычно R=1/3.

Декодирование итеративно. Два BCJR-декодера (вариант Витерби с мягкими выходами) работают поочерёдно. Декодер 1 принимает канальные наблюдения и «мнение» декодера 2 — выдаёт уточнённые оценки. Декодер 2 принимает выход декодера 1 через перемежитель — уточняет ещё раз. Итерации продолжаются до сходимости (обычно 6–8).

Ключевое слово — «мнение»: каждый декодер передаёт не решение (0 или 1), а апостериорную вероятность — насколько уверен, что конкретный бит равен 0 или 1. Такой обмен позволяет двум относительно слабым декодерам вместе «раскачать» правильное решение — эффект, которого нет при однократном декодировании.

3G UMTS (2001) принял турбо-код R=1/3, K=4 как основной для пользовательских данных. Выигрыш над свёрточным K=7 — около 2–3 дБ при BER = 10⁻⁴. LTE унаследовал ту же конструкцию с улучшенным перемежителем QPP (Quadratic Permutation Polynomial).

В MATLAB турбо-код реализован через comm.TurboEncoder/Decoder. Полная симуляция при 6–8 итерациях и блоках >1000 бит занимает минуты — если нужен рабочий скрипт, напишите в комментариях. Главный результат из теории: кривая «турбо-обрыва» круто падает при Eb/N0 ≈ 2–3 дБ, тогда как свёрточный K=7 там держит BER > 10⁻².

LDPC: ядро 5G NR: История, которая не торопилась

LDPC (Low-Density Parity-Check) придумал Роберт Галлагер в 1960 году — в своей PhD-диссертации в MIT. Идея оказалась слишком вычислительно дорогой для тогдашнего железа и на 35 лет ушла в забвение. В конце 1990-х её переоткрыли — и оказалось, что LDPC вплотную подходит к пределу Шеннона, не хуже турбо-кодов, но с меньшей вычислительной сложностью декодера при высоких скоростях.

В 2003 году DVB-S2 (спутниковое телевидение высокой чёткости) выбрал LDPC как основной код — первый массовый стандарт с LDPC. В 2019 году 5G NR выбрал LDPC для пользовательских данных канала eMBB. Именно матрицу DVB-S2 мы применяем в симуляции через dvbs2ldpc(1/2) — та же конструкция, что и в лабораторной работе.

Принцип: разреженный граф вместо матрицы

LDPC — линейный блоковый код с разреженной матрицей проверки чётности H размером (n−k)×n. Каждая строка — одно уравнение: XOR нескольких битов кодового слова должен давать 0. «Разреженная» значит, что в строке не сотни единиц, а 6–8. Это принципиально для декодирования.

Почему разреженность важна? Посмотрим на граф.

Разреженность означает, что большинство пар «бит–уравнение» не связаны напрямую. Это создаёт структуру, похожую на дерево: локально вокруг каждого узла граф почти ацикличен. Именно это позволяет работать алгоритму belief propagation.

Belief propagation: итеративное декодирование

На вход декодера поступают не биты, а логарифмические отношения правдоподобия (LLR):

Для BPSK в канале AWGN с дисперсией σ² это вычисляется просто:S

Положительный LLR — декодер склоняется к нулю, отрицательный — к единице. Чем больше абсолютное значение, тем увереннее решение. LLR — это «мягкое» знание канала, запакованное в одно число.

Декодирование — итерационный обмен сообщениями по рёбрам графа:

1. Инициализация: каждый бит-узел отправляет соседним проверочным свой начальный LLR с канала.

2. Шаг проверочных узлов: каждое уравнение собирает LLR от своих бит-узлов и вычисляет «насколько вероятно, что уравнение выполнено» — отправляет обратно скорректированные оценки.

3. Шаг бит-узлов: каждый бит суммирует все пришедшие поправки со своим начальным LLR — обновляет оценку.

4. Повторяем 30–50 раз, пока все проверки не выполнятся.

Ключевой эффект: информация от «уверенных» бит перетекает к «неуверенным» через общие уравнения. «Уверенный» бит с большим LLR влияет на оценки всех битов, с которыми делит уравнение. За несколько итераций ошибки «вычищаются» почти полностью — если только канал не слишком плох.

Алгоритм сходится, потому что граф локально ацикличен: сообщения, которые бит-узел отправляет в разные проверочные узлы, приходят обратно по разным путям, не «зацикливаясь». В плотном графе это было бы невозможно.

Водопад

Характерная форма LDPC-кривой — «водопад». При низком SNR ошибок слишком много — алгоритм не сходится, BER ≈ 0.1. При переходе через порог ~0.5–1 дБ он начинает сходиться почти для всех блоков — BER падает на 4 порядка примерно за 0.5 дБ. Это резкий «обрыв», которого нет у свёрточного кода.

Почему обрыв такой резкий? Потому что belief propagation — пороговое явление. Выше порога — лавина исправлений: каждая итерация делает LLR более уверенными, что помогает следующей итерации исправить ещё больше ошибок. Ниже порога — лавина работает в обратную сторону.

MATLAB-симуляция BER:

Сравнительный график

Теперь можно поставить все четыре кода рядом. Блок LDPC подгружается из заранее посчитанного файла — симуляция длинная, гонять её внутри compare_all.m неудобно.

% compare_all.m — сравнение BER: Хэмминг, BCH, Conv K=7, LDPC
% LDPC загружается из ldpc_result.mat (запустить ldpc_ber.m заранее)
clear; clc;

EbN0_dB  = 0:0.5:10;
EbN0_lin = 10.^(EbN0_dB/10);
n_iter   = 500000;   % бит на точку; при 50000 хвосты кривых «шумят»

%% Без кодирования (аналитика)
BER_ref = qfunc(sqrt(2*EbN0_lin));

%% Хэмминг (7,4) — ручная реализация через H-матрицу
fprintf('Хэмминг (7,4)...\n');
rate_h = 4/7;
H = [1 0 1 0 1 0 1; 0 1 1 0 0 1 1; 0 0 0 1 1 1 1];
st = zeros(1,8);
for i=1:7
    e=zeros(7,1); e(i)=1; s=mod(H*e,2);
    st(s(1)*4+s(2)*2+s(3)+1)=i;
end
BER_hamming = zeros(1,length(EbN0_dB));
for ki=1:length(EbN0_dB)
    sig=sqrt(1/(2*rate_h*EbN0_lin(ki))); errs=0;
    for b=1:n_iter
        d=randi([0 1],4,1); cw=zeros(7,1); cw([3 5 6 7])=d;
        cw(1)=mod(cw(3)+cw(5)+cw(7),2);
        cw(2)=mod(cw(3)+cw(6)+cw(7),2);
        cw(4)=mod(cw(5)+cw(6)+cw(7),2);
        rb=double(2*cw-1+sig*randn(7,1)>0);
        s=mod(H*rb,2); si=s(1)*4+s(2)*2+s(3)+1;
        if si>1&&st(si)>0, rb(st(si))=1-rb(st(si)); end
        errs=errs+sum(rb([3 5 6 7])~=d);
    end
    BER_hamming(ki)=errs/(n_iter*4);
end

%% BCH(15,7) — Communications Toolbox
fprintf('BCH(15,7)...\n');
enc_bch=comm.BCHEncoder(15,7); dec_bch=comm.BCHDecoder(15,7);
BER_bch=zeros(1,length(EbN0_dB));
for ki=1:length(EbN0_dB)
    sig=sqrt(1/(2*(7/15)*EbN0_lin(ki))); errs=0;
    for b=1:n_iter
        d=randi([0 1],7,1); cw=enc_bch(d);
        rb=double(2*cw-1+sig*randn(15,1)>0);
        errs=errs+sum(dec_bch(rb)~=d);
    end
    BER_bch(ki)=errs/(n_iter*7);
end

%% Свёрточный R=1/2, K=7 — мягкое декодирование Витерби
fprintf('Свёрточный K=7 [171 133]...\n');
trel=poly2trellis(7,[171 133]); tblen=96;
BER_conv=zeros(1,length(EbN0_dB));
for ki=1:length(EbN0_dB)
    sig=sqrt(1/(2*0.5*EbN0_lin(ki)));
    d=randi([0 1],n_iter,1); cw=convenc(d,trel);
    rx=2*cw-1+sig*randn(length(cw),1);
    dec=vitdec(-rx,trel,tblen,'trunc','unquant');
    BER_conv(ki)=sum(dec~=d)/n_iter;
end

%% LDPC — из файла (если есть)
has_ldpc = exist('ldpc_result.mat', 'file');
if has_ldpc
    tmp = load('ldpc_result.mat', 'EbN0_dB', 'BER_ldpc');
    EbN0_ldpc = tmp.EbN0_dB;
    BER_ldpc  = tmp.BER_ldpc;
    fprintf('LDPC загружен из ldpc_result.mat\n');
else
    fprintf('ldpc_result.mat не найден — запустите ldpc_ber.m\n');
end

%% График
figure('Position',[100 100 820 520]);
semilogy(EbN0_dB, BER_ref,     'k--', 'LineWidth', 2.5); hold on;
semilogy(EbN0_dB, BER_hamming, 'b-o', 'LineWidth', 2, 'MarkerSize', 5);
semilogy(EbN0_dB, BER_bch,     'r-s', 'LineWidth', 2, 'MarkerSize', 5);
semilogy(EbN0_dB, BER_conv,    'g-d', 'LineWidth', 2, 'MarkerSize', 5);
if has_ldpc
    semilogy(EbN0_ldpc, max(BER_ldpc,1e-6), 'c-p', 'LineWidth', 2, 'MarkerSize', 6);
end
grid on; ylim([1e-5 1]); xlim([0 10]);

leg = {'Без кодирования (BPSK)', 'Хэмминг (7,4)', 'BCH (15,7)', ...
       'Свёрточный K=7 [171 133]'};
if has_ldpc, leg{end+1} = 'LDPC DVB-S2 R=1/2'; end
legend(leg, 'Location', 'southwest', 'FontSize', 11);
xlabel('Eb/N0, дБ', 'FontSize', 12);
ylabel('BER',        'FontSize', 12);
title('Коды сотовой связи: сравнение BER', 'FontSize', 13);

На графике видна иерархия. Хэмминг и BCH держатся вплотную к некодированной кривой и расходятся заметно лишь после 7–8 дБ. Свёрточный K=7 с мягким Витерби уходит вниз значительно круче: примерно на 4.5 дБ быстрее некодированного при BER=10⁻⁴. LDPC показывает водопад при Eb/N0 ≈ 0.5–1 дБ — кривая обрывается вертикально вниз на 4 порядка за полдецибела.

Итог

Смена поколений в сотовой — это смена кода. 1G передавал аналог без защиты. Каждый переход (2G→3G→4G→5G) давал 2–4 дБ выигрыша при той же энергии — что в масштабе сети означало или больше скорость, или меньше базовых станций.

Если посмотреть на эволюцию декодеров, прослеживается одна линия: жёсткие решения → мягкие выходы → итеративный обмен мягкими выходами. Витерби с мягким вводом — шаг первый. Итеративный декодер турбо-кода — шаг второй. Belief propagation в LDPC — шаг третий. Каждый раз декодер получает больше информации о канале и больше итераций для её переработки.

Турбо-коды и LDPC достигают предела Шеннона в пределах 0.5–1 дБ — предела, который в 1948 году казался теоретической абстракцией. Полярные коды Арыкана (2008) вообще первые, у которых есть доказательство достижения пропускной способности — не просто экспериментальный факт, а теорема.

Если интересно разобрать итеративное декодирование LDPC/турбо в деталях или полярные коды с последовательным отменением — пишите в комментариях.