Когда моделируешь помехоустойчивые коды, декодер обычно остаётся чёрным ящиком: пишешь ldpcDecode(llr, cfg, 30), comm.TurboDecoder или dvbs2ldpc(1/2) — и получаешь красивый «водопад» BER, не заглядывая внутрь. А самое интересное в современных кодах именно там: не в том, как закодировать, а в том, как декодер из зашумлённого сигнала достаёт правильные биты.
Первая часть заканчивалась предложением: «если интересно разобрать итеративное декодирование LDPC/турбо в деталях или полярные коды с последовательным отменением — пишите в комментариях». Написали — так что эта статья и есть ответ на запрос из комментариев. Читать первую часть необязательно: там мы прошли эволюцию кодов в сотовой связи от GSM до 5G по BER-кривым в MATLAB, а всё нужное я напомню по ходу. Здесь — вскрываем сами декодеры.
Эта часть открывает ящик. Разберём три декодера, на которых держится всё современное кодирование:
• belief propagation — итеративный обмен сообщениями по графу, ядро LDPC и всего 5G eMBB;
• BCJR + итеративный обмен мнениями — то, что сделало турбо-коды возможными;
• successive cancellation — последовательное отменение в полярных кодах.
Чтобы видеть каждую строчку, MATLAB-тулбокс не годится — он прячет алгоритм. Поэтому весь разбор идёт по коду небольшой библиотеки, которую я написал специально для этого — fec-cpp: header-only C++17, без единой внешней зависимости, только STL. Её можно прочитать целиком за вечер, и каждый декодер в ней — полсотни строк, которые делают ровно то, что написано в учебнике. Рядом с каждым разбором будет и MATLAB-эквивалент — чтобы видеть контраст: одна строка тулбокса против явного алгоритма. А в конце — большое сравнение: прогоним обе реализации по одинаковым кодам и наложим их BER-кривые на одни графики.
Это учебные реализации. LDPC здесь — случайная регулярная матрица, а не DVB-S2 на 64800 бит; турбо — классический RSC [7,5], а не LTE с QPP; полярный — SC без списочного декодирования. Цель — показать механизм, а не побить рекорд по BER, но все три дают настоящий водопад на реальных числах, которые приведены ниже и воспроизводимы из репозитория.
Общий язык: LLR
Прежде чем лезть в декодеры, договоримся про одно число, на котором говорят все трое, — LLR, логарифмическое отношение правдоподобия:
LLR_j = log( P(бит_j = 0 | принятое) / P(бит_j = 1 | принятое) )
Положительный LLR — склоняемся к нулю, отрицательный — к единице, модуль — это уверенность. Для BPSK в AWGN-канале с дисперсией σ² всё считается одной формулой: LLR = 2y/σ². Именно так устроен канал в библиотеке — AWGNChannel сразу отдаёт не биты, а LLR:
// include/fec/common/channel.hppLLRVec transmit(const BitVec& bits) { LLRVec llr(bits.size()); for(size_t i = 0; i < bits.size(); i++){ float s; if(bits[i] == 0) s = 1.0f; else s = -1.0f; // BPSK: 0 это +1, 1 это -1 float y = s + sigma_ * dist_(rng_); // добавили шум llr[i] = 2.0f * y * inv_sigma2_; // LLR = 2y/sigma^2 } return llr;}
Все три декодера принимают на вход вектор LLR и возвращают биты. Дальше речь только о том, что между этими двумя точками происходит.
LDPC: belief propagation по строкам
Граф, а не матрица
LDPC-код задаётся разреженной матрицей проверок чётности H размером (n−k)×n. Но декодер работает не с матрицей, а с графом Таннера: слева n узлов-переменных (по биту кодового слова), справа n−k проверочных узлов (по уравнению). Ребро соединяет бит с уравнением, если в этой ячейке H стоит единица.
В библиотеке H хранится именно как списки смежности, а не как плотный массив — это и есть «разреженность» в коде:
// include/fec/ldpc/matrix.hppstruct ParityCheckMatrix { int M, N; vector<vector<int>> rows; // проверка -> номера бит vector<vector<int>> cols; // бит -> номера проверок};
Декодер первым делом разворачивает граф в плоский список рёбер — по ребру на каждую единицу матрицы. Все сообщения будут жить на этих рёбрах:
// include/fec/ldpc/decoder.hppvoid build_edge_list(){ check_edges_.resize(H_.M); for(int c=0;c<H_.M;c++) for(int v : H_.rows[c]){ int e = (int)edges_.size(); edges_.push_back({v,c}); // ребро: (бит v, проверка c) check_edges_[c].push_back(e); // у проверки c - список ее ребер }}
Два сорта сообщений
По рёбрам туда-сюда бегают сообщения двух типов:
• Q[e] — от бита к проверке: «вот что я (бит) думаю о себе, не считая мнения этой проверки».
• R[e] — от проверки к биту: «вот что я (уравнение) думаю про этот бит, глядя на всех остальных его соседей».
В начале бит ничего не знает, кроме канала, поэтому все Q инициализируются канальным LLR:
vector<float> Q(E), R(E);for(int e = 0; e < E; e++) Q[e] = llr_ch[edges_[e].var]; // инициализация с канала
Шаг проверочного узла: правило «уверен настолько, насколько уверен слабейший»
Уравнение чётности говорит: XOR его битов равен нулю. Значит, зная мнения всех битов, кроме одного, уравнение может предсказать недостающий: он равен XOR остальных. Но мнения мягкие, поэтому и предсказание мягкое.
Точная формула («tanh rule») в области вероятностей содержит произведение гиперболических тангенсов. Чтобы не перемножать, а складывать, переходим в логарифмическую область через функцию Φ(x) = −log·tanh(x/2). Она замечательна тем, что обратна сама себе, и превращает произведение в сумму:
static float phi(float x){ if(x < 1e - 9f) return 20.0f; // чтоб не делить на 0 по сути return -log(tanh(x * 0.5f));}
Магнитуда исходящего сообщения — это Φ от суммы Φ(|Q|) всех остальных рёбер уравнения, а знак — произведение их знаков. «Все остальные, кроме текущего» — это классический приём префиксных и суффиксных сумм, чтобы не пересчитывать сумму заново для каждого ребра:
for(int c = 0; c < M; c++){ const auto& elist = check_edges_[c]; int ne = (int)elist.size(); vector<float> phi_vals(ne); float sign_prod = 1.0f; for(int i = 0; i < ne; i++){ float q = Q[elist[i]]; phi_vals[i] = phi(fabs(q)); if(q >= 0) sign_prod = 1.0f; else sign_prod = -1.0f; } // префикс / суффикс суммы (чтобы брать всех кроме текущего) vector<float> prefix(ne + 1,0.0f), suffix(ne + 1,0.0f); for(int i = 0; i < ne; i++) prefix[i + 1] = prefix[i] + phi_vals[i]; for(int i = ne - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + phi_vals[i]; for(int i = 0; i < ne; i++){ float phi_sum = prefix[i] + suffix[i + 1]; float qi = Q[elist[i]] float sign_i = sign_prod * ((qi >= 0)? 1.0f:-1.0f); R[elist[i]] = sign_i * phi(phi_sum); }}
Интуиция за Φ: функция резко растёт у нуля и быстро спадает. Поэтому в сумму Φ(|Q|) главный вклад даёт самый неуверенный сосед (его |Q| мало → Φ велико). Уравнение оказывается уверено в бите ровно настолько, насколько уверен его слабейший партнёр. Это и есть механизм, которым уверенность перетекает от «хороших» битов к «плохим».
Шаг бита и ранняя остановка
Бит складывает канальный LLR со всеми пришедшими поправками R — это его полная апостериорная оценка. А исходящее в конкретную проверку сообщение Q — это полная оценка минус вклад этой же проверки (иначе бит вернул бы уравнению его собственное мнение — эхо, которое ломает сходимость):
vector<float> total(N);for(int v = 0; v < N; v++) total[v] = llr_ch[v];for(int e = 0; e < E; e++) total[edges_[e].var] += R[e];for(int e = 0; e < E; e++) Q[e] = total[edges_[e].var] - R[e]; // вычитаем свое ребро
После каждой итерации берём жёсткое решение по знаку total и проверяем синдром. Если все уравнения выполнены — слово корректное, выходим досрочно, не докручивая до лимита итераций:
BitVec hard(N);for(int v = 0; v < N; v++){ if(total[v]<0) hard[v]=1; else hard[v]=0;}BitVec synd = H_.syndrome(hard);bool valid = true;for(Bit s : synd) if(s){ valid=false; break; }if(valid) return hard; // синдром нулевой - все ок, выходим
MATLAB против C++
Вся эта механика в MATLAB из первой части умещалась в одну строку:
dec_bits = ldpcDecode(llr, decCfg, maxIter); % всё BP — внутри
Удобно, но непрозрачно: ни графа, ни сообщений, ни префиксного трюка не видно. C++-версия — это те же 50 строк выше, и в них виден каждый шаг.
Числа
Регулярная матрица (n=200, вес столбца 3, вес строки 6, R=1/2), 50 итераций BP, замер по битам кодового слова:
|
Eb/N0, дБ |
BER |
|
0.0 |
1.2·10⁻¹ |
|
1.0 |
6.0·10⁻² |
|
2.0 |
1.2·10⁻² |
|
3.0 |
1.2·10⁻³ |
|
4.0 |
1.5·10⁻⁴ |
Тот самый водопад: между 2 и 4 дБ BER падает на два порядка. На маленьком блоке n=200 он пологий — у DVB-S2 на 64800 бит обрыв куда круче, но механизм ровно тот же, что в коде выше.
Турбо: BCJR и обмен мнениями
Один компонент: BCJR
Турбо-код — это два рекурсивных свёрточных кодера (RSC), связанных перемежителем. В библиотеке RSC — простейший [7,5] octal на 4 состояния:
// include/fec/turbo/trellis.hppstruct RSCTrellis { static const int NUM_STATES = 4; static const int G0 = 0b111; // 7 - обратная связь static const int G1 = 0b101; // 5 - прямая ветвь // tr[state][input] = {next_state, output=[sys,par]}};
Сердце турбо-декодера — BCJR (он же MAP): в отличие от Витерби, который находит один самый правдоподобный путь, BCJR считает для каждого бита апостериорную вероятность, усредняя по всем путям через решётку. Это и есть «мягкий выход».
Работает он в три прохода. Сначала метрика ветви γ — насколько правдоподобен переход (state, input) при данных LLR систематического бита, паритета и априорной информации:
// include/fec/turbo/decoder.hppauto gamma = [&](int s, int u, int t){ auto& trans = tr.tr[s][u]; int sys = (trans.output >> 1) & 1; int par = trans.output & 1; float la = La[t], ls = llr_sys[t], lp = llr_par[t]; float lsys = (sys?-1.0f:1.0f)*(ls+la); float lpar = (par?-1.0f:1.0f)*lp; return 0.5f*lsys + 0.5f*lpar;};
Затем прямой проход α (накапливает правдоподобие путей слева) и обратный β (справа). Оба складывают вероятности в лог-области через max* — «мягкий максимум», точный логарифм суммы экспонент:
static float lse(float a, float b){ if(a == -1e9f) return b; if(b == -1e9f) return a; float diff = fabs(a - b); return max(a,b) + log1p(exp(-diff));}// прямой проход alphaalpha[0][0] = 0.0f;for(int t = 0; t < K_; t++) for(int s = 0; s < S_; s++){ if(alpha[t][s] == NEG_INF) continue; for(int u = 0; u < 2; u++){ int ns = tr.tr[s][u].next; float g = gamma(s,u,t); alpha[t + 1][ns] = lse(alpha[t + 1][ns], alpha[t][s] + g); } }
Здесь прячется тонкость, которая стоила бы недели отладки в реальном коде. Декодер получает только информационную часть, без терминирующих хвостовых битов, — значит, решётка в конце не приведена в нулевое состояние. Поэтому β инициализируется равномерно, а не «уверенно в состоянии 0»:
// решетка НЕ терминирована, поэтому beta в конце - равномерноfor(int s=0;s<S_;s++) beta[K_][s] = 0.0f;
Наконец, апостериорный LLR бита — это max* по переходам с input=0 минус то же по input=1. А наружу отдаётся не он, а внешняя (extrinsic) информация: из полной оценки вычитается то, что декодер и так знал на входе (канал + априори):
float L_total = L0 - L1;Le[t] = L_total - La[t] - llr_sys[t]; // только добавленное знание
Почему именно extrinsic — и в чём «турбо»
Вот здесь и спрятан весь фокус турбо-кодов. Два BCJR-декодера обмениваются именно extrinsic-сообщениями. Первый смотрит на биты в исходном порядке, второй — в перемешанном перемежителем. Каждый передаёт другому только то, что узнал сам, не возвращая чужое мнение обратно (то же правило «не создавай эхо», что и у бита в LDPC). За несколько итераций два относительно слабых декодера вместе раскачивают правильное решение:
LLRVec La(K_, 0.0f);for(int it=0;it<iters_;it++){ // декодер 1 LLRVec Le1 = bcjr_.decode(llr_sys, llr_par1, La); // перемешиваем для декодера 2 LLRVec Le1_i = il_.interleave_llr(Le1); LLRVec sys_i = il_.interleave_llr(llr_sys); // декодер 2 LLRVec Le2 = bcjr_.decode(sys_i, llr_par2, Le1_i); // обратно перемешиваем -> станет априорной на след итерации La = il_.deinterleave_llr(Le2);}
MATLAB против C++
В MATLAB это:
turboDec = comm.TurboDecoder('InterleaverIndices', idx, 'NumIterations', 8);decoded = turboDec(llr); % два BCJR и весь обмен — внутри
Ни α/β, ни extrinsic, ни обмена не видно. А в C++ виден буквально каждый из восьми проходов туда-обратно.
Числа
K=256, R≈1/3, 8 итераций:
|
Eb/N0, дБ |
BER |
|
0.0 |
9.9·10⁻² |
|
0.5 |
4.7·10⁻² |
|
1.0 |
5.9·10⁻³ |
|
1.5 |
1.8·10⁻³ |
|
2.0 |
6.8·10⁻⁴ |
Характерный для турбо резкий перегиб около 0.5–1 дБ: до него декодер почти не сходится, после — обрушивается. Даже на учебном [7,5] эффект налицо.
Полярные коды: successive cancellation
Поляризация: заморозить бесполезные каналы
Идея Арыкана (2008): если скомбинировать N копий одного канала специальным преобразованием, эффективные «подканалы» поляризуются — часть становится почти идеальными, часть почти бесполезными. По полезным каналам шлём данные, бесполезные замораживаем (фиксируем в нуле, и декодер это знает заранее).
Какие каналы хорошие — оценивается параметром Бхаттачарьи. Каждый уровень преобразования расщепляет канал на «худший» (Z’ = 2Z − Z²) и «лучший» (Z’ = Z²):
// include/fec/polar/polar.hppvector<double> Z(1, 0.5);while((int)Z.size() < N){ int m = (int)Z.size(); vector<double> next(2 * m); for(int i = 0; i < m; i++){ double z = Z[i]; next[2 * i] = 2 * z - z * z; // верхний (хуже) next[2 * i + 1] = z * z; // нижний (лучше) } Z.swap(next);}// K позиций с наименьшим Z - информационные, остальные заморожены
Кодер кладёт информационные биты в незамороженные позиции и прогоняет «бабочку» полярного преобразования:
inline void polar_transform(BitVec& u){ int N = (int)u.size(); for(int step = N / 2; step >= 1; step /= 2) for(int i=0;i<N;i+=2*step) for(int j=0;j<step;j++) u[i+j] ^= u[i+j+step];}
Successive cancellation: бит за битом
Декодер SC идёт по битам последовательно, и каждое решение опирается на все предыдущие. Рекурсия делит блок пополам. Для верхней половины LLR комбинируются функцией f (здесь — min-sum приближение), для нижней — функцией g, которая уже использует частичную сумму из верхней половины как известный бит:
static float f_func(float a, float b){ // f = знак*знак*min(|a|,|b|) float sa = (a >= 0)?1.0f:-1.0f; float sb = (b >= 0)?1.0f:-1.0f; return sa * sb * min(fabs(a), fabs(b));}static float g_func(float a, float b, Bit s){ // s - уже решенный бит сверху return b + (1 - 2 * (int)s) * a;}
Ключевая тонкость реализации — два раздельных буфера. u хранит решения на листьях (это и есть декодированный вектор), а beta — частичные суммы кодовых битов, которые шаг combine перезаписывает. Если их смешать, частичные суммы затрут уже принятые решения до того, как те понадобятся:
void sc_decode(const LLRVec& llr, int offset, int size, const vector<bool>& cur_frozen, BitVec& u, BitVec& beta) const{ if(size == 1){ Bit bit = cur_frozen[0] ? 0 : ((llr[0] < 0)? 1:0); // лист u[offset] = bit; beta[offset] = bit; return; } int half = size / 2; // frozen маски на половины - простой сплит vector<bool> frozen_upper(cur_frozen.begin(), cur_frozen.begin() + half); vector<bool> frozen_lower(cur_frozen.begin() + half, cur_frozen.end()); // верх: f-комбинация, декодим первую половину LLRVec llr_f(half); for(int i = 0; i < half; i++) llr_f[i] = f_func(llr[i], llr[i + half]); sc_decode(llr_f, offset, half, frozen_upper, u, beta); // низ: g-комбинация с частичными суммами верха, декодим вторую половину LLRVec llr_g(half); for(int i = 0; i < half; i++) llr_g[i] = g_func(llr[i], llr[i+half], beta[offset + i]); sc_decode(llr_g, offset+half, half, frozen_lower, u, beta); // combine: частичные суммы наверх (трогаем только beta, не u) for(int i = 0; i < half; i++) beta[offset + i] = beta[offset + i] ^ beta[offset + half + i];}
На листе всё просто: замороженный бит — это известный ноль; информационный — жёсткое решение по знаку LLR. Поскольку замороженные биты декодер знает точно, ошибка в них исключена, и эта определённость через g помогает решать соседние информационные биты.
MATLAB против C++
В 5G-тулбоксе MATLAB:
decoded = nrPolarDecode(llr, K, E); % SC/SCL и frozen set — внутри
Скрыто всё: и конструкция frozen-набора, и рекурсия f/g. В C++ — обе части на виду.
Числа
N=1024, K=512, R=1/2, голый SC:
|
Eb/N0, дБ |
BER |
|
0.0 |
4.2·10⁻¹ |
|
1.0 |
1.9·10⁻¹ |
|
2.0 |
1.0·10⁻² |
|
3.0 |
0 (на 200 блоках) |
Водопад есть, но он сдвинут правее, чем у LDPC при той же R=1/2: голый SC заметно слабее. Это не дефект реализации, а свойство алгоритма — и ровно поэтому 5G использует не чистый SC, а списочный SC-List с CRC-проверкой (декодер ведёт L путей-кандидатов и в конце выбирает тот, чей CRC сошёлся). Это следующий шаг, которого в учебной библиотеке нет, но видно, откуда он растёт.
Большое сравнение с MATLAB: те же коды — два мира
Одностроки тулбокса выше показывают что MATLAB прячет. Но честный вопрос другой: а так же ли хорошо работает библиотека на 60 строках, как промышленный декодер из MATLAB? Проверим напрямую — прогоним оба по одинаковым кодам и наложим BER-кривые на один график.
Методика (без подгонки):
• C++ считает BER через fec-cpp и пишет таблицу в CSV.
• MATLAB читает тот же диапазон Eb/N0, гоняет свой тулбокс и рисует обе кривые.
• Канал у обоих одинаковый: BPSK + AWGN, LLR = 2y/σ².
Весь код сравнения — в репозитории, в каталоге matlab-compare/: cpp_compare.cpp (C++-сторона) и run_compare.m (MATLAB-сторона, она и накладывает обе кривые на график).
LDPC: одна и та же матрица H, два декодера BP
Самый строгий тест — дать обоим декодерам физически одну и ту же матрицу проверок. C++ строит H (N=1024, K=512, бидиагональная паритетная часть, чтобы кодировалось и в MATLAB), экспортирует её в текстовый файл, а MATLAB загружает ту же H в ldpcEncoderConfig/ldpcDecoderConfig. Дальше каждый сам кодирует, шумит и декодирует своим belief propagation.
LDPC: fec-cpp BP против MATLAB ldpcDecode на одной матрице H
Кривые ложатся почти друг на друга. Это и есть проверка: самописный sum-product на префиксных суммах из раздела выше даёт ту же характеристику, что и ldpcDecode из Communications Toolbox. Расхождение в хвосте (после 2.5 дБ) — статистика: 300 блоков на точку, в зоне BER~10⁻⁴ счёт идёт на единицы ошибок.
Турбо: тот же trellis [7,5] и тот же QPP
Здесь тоже добиваемся совпадения кода: в MATLAB задаём comm.TurboDecoder с тем же решётчатым кодом poly2trellis(3,[7 5],7) и теми же индексами QPP-перемежителя для K=256, что и в C++.
Турбо: fec-cpp BCJR против comm.TurboDecoder, один и тот же код
Водопад у обоих начинается в одной зоне (0.5–1 дБ), но дальше пути расходятся, и это поучительно. MATLAB продолжает падать вертикально, а кривая fec-cpp загибается в error floor на уровне ~5·10⁻⁴. Причина — ровно та упрощённая деталь, что разбиралась выше: наш BCJR работает с открытой решёткой (равномерная инициализация β), тогда как comm.TurboDecoder терминирует её честными хвостовыми битами. На пологом склоне это незаметно, но в области низких BER неучтённое финальное состояние оставляет «пол», ниже которого декодер не проваливается. Хороший наглядный урок: упрощение, безобидное в roundtrip-тесте, проявляется именно на хвосте BER-кривой — там, где его и стоит искать.
Polar: плоский SC против 5G NR (SCL + CRC)
А вот тут коды специально разные — и это самое интересное. C++ — голый successive cancellation. MATLAB — полная 5G-цепочка: nrPolarEncode → канал → nrPolarDecode со списочным декодером (SCL, список L=8) и проверкой CRC-11.
Polar: плоский SC против 5G NR SCL+CRC
Разрыв около 1 дБ в пользу MATLAB — это и есть наглядная цена того, что в учебной библиотеке нет SCL+CRC. Список из 8 путей-кандидатов плюс CRC-отбор в конце сдвигают водопад влево ровно на этот зазор. Именно поэтому 5G не использует чистый SC: график показывает, сколько именно даёт списочное декодирование.
Всё вместе
Все три кода: fec-cpp против MATLAB
Сводный график подтверждает картину: LDPC и турбо в fec-cpp практически неотличимы от тулбокса (валидация реализации), а на polar виден честный зазор учебного SC до промышленного SCL.
Собрать и запустить
Весь код из статьи лежит в репозитории fec-cpp под лицензией MIT. Сама библиотека header-only — чтобы пользоваться, достаточно подключить заголовки; сборка нужна только для тестов и примеров. Клонируем и собираем одной командой компилятора (исходники библиотеки — в подкаталоге fec-cpp/):
git clone https://github.com/BessonovT/fec-cpp
cd fec-cpp
# тесты
g++ -std=c++17 -O2 -Ifec-cpp/include fec-cpp/tests/test_all.cpp -o test_all && ./test_all
# → 22/22 passed
# BER-примеры (печатают таблицу BER в stdout)
g++ -std=c++17 -O2 -Ifec-cpp/include fec-cpp/examples/ldpc_ber.cpp -o ldpc_ber && ./ldpc_ber
g++ -std=c++17 -O2 -Ifec-cpp/include fec-cpp/examples/polar_ber.cpp -o polar_ber && ./polar_ber
Любой пример печатает таблицу в stdout, а fec-cpp/scripts/plot_ber.py превращает её в semilog-y график — можно сразу пайпом:
./ldpc_ber | python fec-cpp/scripts/plot_ber.py --title "LDPC, R=1/2" --xlabel "SNR (dB)" -o ldpc.png
Сравнение с MATLAB из предыдущего раздела — в каталоге matlab-compare/; воспроизводится двумя командами (нужен MATLAB с Communications + 5G Toolbox):
cd matlab-compare
# 1. C++: считает BER и экспортирует матрицу H + CSV-таблицы
g++ -std=c++17 -O2 -I../fec-cpp/include cpp_compare.cpp -o cpp_compare && ./cpp_compare
# 2. MATLAB: грузит те же данные, гоняет тулбокс, рисует обе кривые
matlab -batch run_compare
Что ещё в репозитории
Тремя декодерами из этой статьи fec-cpp не ограничивается — он покрывает всю цепочку кодов от 2G до 5G, и каждый код идёт с кодером, декодером и примером BER:
• блоковые — Hamming и Reed–Solomon (Берлекэмп–Месси + Форни);
• свёрточный — решётка и Витерби с мягким входом (основа 2G);
• турбо — RSC [7,5], BCJR, итеративный обмен (3G/4G);
• LDPC — sum-product belief propagation по графу Таннера (5G eMBB);
• полярный — кодер и SC-декодер (5G-управление).
Плюс пресеты под реальные стандарты (gsm.hpp, lte.hpp, nr.hpp), общий AWGN-канал, CRC и перемежители, набор тестов и скрипт для BER-графиков. Всё на голом C++17 без зависимостей — можно бросить в свой проект или просто читать как компактный справочник по FEC.
Итог
Три декодера — три способа распорядиться мягкой информацией. LDPC гоняет её по графу, пока проверки не сойдутся; турбо передаёт между двумя BCJR только то, чего другой ещё не знает; polar заранее отключает слабые подканалы и идёт по битам в один проход. Внутри каждого — десятки строк, которые видно целиком.
Сравнение с MATLAB показало главное: на одинаковом коде самописные BP и BCJR ложатся на промышленный тулбокс, а зазор остаётся там, где у учебной реализации нет нужной добавки, — у polar без списка и CRC. То есть алгоритм из учебника и алгоритм из стандарта различаются не магией, а конкретными механизмами, и каждый из них виден на графике.
Что дальше: SC-List с CRC (тот самый зазор на polar), терминированная решётка для турбо (тот самый error floor) и квазициклические матрицы LDPC из DVB-S2/5G. Это уже на отдельную часть — и она появится, если будет запрос в комментариях.
ссылка на оригинал статьи https://habr.com/ru/articles/1043922/