Введение
Линейный код, исправляющий ошибки
В теории информации код проверки чётности с низкой плотностью (LDPC) — это линейный код, исправляющий ошибки, метод передачи сообщения по зашумлённому каналу связи. Код LDPC строится с использованием разреженного графа Таннера (подкласс двудольного графа). Коды LDPC – это коды, приближающиеся к пропускной способности, что означает, что существуют практические реализации, позволяющие установить пороговое значение шума очень близко к теоретическому максимуму (пределу Шеннона) для симметричного канала без памяти. Пороговое значение шума определяет верхнюю границу уровня шума в канале, до которой вероятность потери информации может быть сделана сколь угодно малой. Используя итеративные методы распространения сообщений, коды LDPC могут быть декодированы за время, линейно зависящее от длины блока. Коды LDPC также известны как коды Галлагера, в честь Роберта Г. Галлагера, который разработал концепцию LDPC в своей докторской диссертации в Массачусетском технологическом институте в 1960 году. Однако коды LDPC требуют вычислительно сложных итеративных алгоритмов декодирования, поэтому они не использовались в течение десятилетий. В 1993 году вновь изобретённые турбокоды продемонстрировали, что коды с итеративным декодированием могут значительно превосходить другие коды, использовавшиеся в то время, но турбокоды были запатентованы и требовали лицензионных отчислений за использование. Это возродило интерес к кодам LDPC, которые показали сравнимую производительность, но были намного старше и не имели патентных ограничений. Теперь, когда основной патент на турбокоды истек (29 августа 2013 года), коды LDPC по-прежнему используются благодаря своим техническим достоинствам. Коды LDPC обладают идеальными комбинаторными свойствами. В своей диссертации Галлагер показал, что коды LDPC достигают границы Гилберта — Варшамова для линейных кодов над бинарными полями с высокой вероятностью. В 2020 году было показано, что коды LDPC Галлагера достигают пропускной способности декодирования списка и также достигают границы Гилберта — Варшамова для линейных кодов над общими полями.
История
Коды LDPC были непрактичны для реализации при первоначальной разработке Галлагером в 1963 году и были забыты до повторного открытия его работы в 1996 году. Коды турбо, другой класс кодов, приближающихся к теоретическому пределу пропускной способности, открытые в 1993 году, стали предпочтительной схемой кодирования в конце 1990-х годов и использовались в таких приложениях, как сеть дальней космической связи и спутниковая связь. Затем коды LDPC вновь привлекли внимание как альтернатива без лицензионных отчислений с сопоставимой производительностью.
Обновление информации о узле
В последние годы также проводилась большая работа по изучению влияния альтернативных графиков обновления переменных узлов и узлов ограничений. Изначальная техника, использовавшаяся для декодирования кодов LDPC, была известна как метод "затопления" (flooding). Этот тип обновления требовал, чтобы перед обновлением переменного узла были обновлены все узлы ограничений, и наоборот. В более поздних работах Вила Касадо и др. изучались альтернативные методы обновления, при которых переменные узлы обновляются с использованием самой новой доступной информации от узлов ограничений. Логика этих алгоритмов заключается в том, что переменные узлы, значения которых меняются сильнее всего, нуждаются в обновлении в первую очередь. Высоконадёжные узлы, величина отношения правдоподобия (LLR) которых велика и не меняется существенно от одной итерации к другой, не требуют обновлений с той же частотой, что и другие узлы, знак и величина которых более сильно колеблются. Эти алгоритмы планирования демонстрируют более высокую скорость сходимости и более низкий уровень ошибок, чем те, которые используют метод затопления. Эти более низкие уровни ошибок достигаются благодаря возможности информированного динамического планирования (IDS).
При использовании алгоритмов планирования, отличных от метода затопления, используется альтернативное определение итерации. Для LDPC-кода (n, k) со скоростью k/n полная итерация происходит, когда обновлены n переменных узлов и n − k узлов ограничений, независимо от порядка их обновления.
По сравнению с кодами турбо
Коды LDPC можно сравнить с другими мощными схемами кодирования, например, с турбокодами. С одной стороны, производительность по битовой ошибке (BER) турбокодов ограничена свойствами кодов с низкой кодовой скоростью. Коды LDPC не имеют ограничений, связанных с минимальным расстоянием, что косвенно означает, что они могут быть более эффективными при относительно высоких кодовых скоростях (например, 3/4, 5/6, 7/8), чем турбокоды. Однако коды LDPC не являются полной заменой турбокодам: турбокоды остаются оптимальным решением при низких кодовых скоростях (например, 1/6, 1/3, 1/2).