Код проверки на четность с низкой плотностью

В теории информации код с низкой плотностью проверки на четность ( LDPC ) - это код с линейной коррекцией ошибок , метод передачи сообщения по каналу передачи с шумом . ^{[1] [2]} LDPC строится с использованием разреженного графа Таннера (подкласс двудольного графа ). ^[3] Коды LDPC - это коды, приближающиеся к емкости , что означает, что существуют практические конструкции, которые позволяют устанавливать порог шума очень близко к теоретическому максимуму ( предел Шеннона) для симметричного канала без памяти. Порог шума определяет верхнюю границу шума канала, до которой вероятность потери информации может быть минимальной по желанию. Используя методы итеративного распространения уверенности , коды LDPC могут быть декодированы во времени, линейном по отношению к длине их блока.

Коды LDPC находят все более широкое применение в приложениях, требующих надежной и высокоэффективной передачи информации по линиям с ограниченной полосой пропускания или обратным каналом в присутствии искажающего шума. Реализация кодов LDPC отставала от других кодов, особенно турбокодов . Срок действия фундаментального патента на турбокоды истек 29 августа 2013 г. ^{[4] [5]}

Коды LDPC также известны как коды Галлагера в честь Роберта Г. Галлагера , который разработал концепцию LDPC в своей докторской диссертации в Массачусетском технологическом институте в 1960 году ^{[6] [7].}

История [ править ]

Непрактично реализовывать, когда впервые разработал Галлагер в 1963 году ^[8] коды LDPC были забыты до тех пор, пока его работа не была повторно открыта в 1996 году. ^[9] Турбокоды , еще один класс кодов , приближающихся к емкости, открытый в 1993 году, стали схемой кодирования выбора в в конце 1990-х использовался для таких приложений, как сеть дальнего космоса и спутниковая связь . Однако достижения в кодах проверки на четность с низкой плотностью показали, что они превосходят турбокоды с точки зрения минимального уровня ошибок и производительности в диапазоне более высоких кодовых скоростей , в результате чего турбокоды лучше подходят только для более низких кодовых скоростей. ^[10]

Приложения [ править ]

В 2003 году код LDPC в стиле нерегулярного повторения (IRA) превзошел шесть турбокодов и стал кодом с исправлением ошибок в новом стандарте DVB-S2 для спутниковой передачи цифрового телевидения . ^[11] Отборочная комиссия DVB-S2 сделала оценки сложности декодера для предложений Турбо Кода, используя гораздо менее эффективную архитектуру последовательного декодера, чем архитектуру параллельного декодера. Это вынудило предложения Turbo Code использовать размеры кадра порядка половины размера кадра предложений LDPC.

В 2008 годе LDPC бить сверточные турбокоды как прямая коррекция ошибок системы (ПИО) для МСЭ-Т G.hn стандарта. ^[12] G.hn предпочел коды LDPC турбокодам из-за их меньшей сложности декодирования (особенно при работе со скоростями передачи данных, близких к 1,0 Гбит / с), а также из-за того, что предложенные турбокоды демонстрируют значительный минимальный уровень ошибок в желаемом диапазоне работы. ^[13]

Коды LDPC также используются для 10GBASE-T Ethernet, который передает данные со скоростью 10 гигабит в секунду по кабелям витой пары. С 2009 года коды LDPC также являются частью стандарта Wi-Fi 802.11 в качестве дополнительной части 802.11n и 802.11ac в спецификации PHY с высокой пропускной способностью (HT). ^[14]

Некоторые системы OFDM добавляют дополнительную внешнюю коррекцию ошибок, которая исправляет случайные ошибки («минимальный уровень ошибок»), которые преодолевают внутренний код коррекции LDPC даже при низкой частоте ошибок по битам . Например: код Рида-Соломона с кодированной модуляцией LDPC (RS-LCM) использует внешний код Рида-Соломона. ^[15] Все стандарты DVB-S2, DVB-T2 и DVB-C2 используют внешний код кода BCH для устранения остаточных ошибок после декодирования LDPC. ^[16]

Оперативное использование [ править ]

Коды LDPC функционально определяются разреженной матрицей проверки на четность . Эта разреженная матрица часто генерируется случайным образом с учетом ограничений разреженности - конструкция кода LDPC обсуждается позже . Эти коды были впервые разработаны Робертом Галлагером в 1960 году ^[7].

Ниже приведен фрагмент графика примера кода LDPC с использованием обозначения графа факторов Форни . В этом графе n узлов переменных в верхней части графа соединены с ( n - k ) узлами ограничений в нижней части графа.

Это популярный способ графического представления кода ( n ,  k ) LDPC. Биты действительного сообщения, помещенные в буквы T в верхней части графика, удовлетворяют графическим ограничениям. В частности, все линии, соединяющиеся с узлом переменной (прямоугольник со знаком '='), имеют одинаковое значение, и все значения, соединяющиеся с узлом фактора (прямоугольник со знаком '+'), должны суммироваться по модулю два до нуля (в другими словами, они должны быть суммированы до четного числа; или должно быть четное число нечетных значений).

Игнорируя любые строки, выходящие за пределы изображения, существует восемь возможных шестибитных строк, соответствующих допустимым кодовым словам: (т.е. 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). Этот фрагмент кода LDPC представляет собой трехбитовое сообщение, закодированное как шесть битов. Здесь используется избыточность для увеличения шансов восстановления после ошибок канала. Это (6, 3) линейный код с n  = 6 и k  = 3.

Снова игнорируя строки, выходящие за пределы изображения, матрица проверки на четность, представляющая этот фрагмент графа, имеет вид

${\ displaystyle \ mathbf {H} = {\ begin {pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\\ end {pmatrix}}.}$

В этой матрице каждая строка представляет одно из трех ограничений проверки на четность, а каждый столбец представляет один из шести битов принятого кодового слова.

В этом примере восемь кодовых слов можно получить, поместив матрицу проверки на четность H в эту форму с помощью основных операций со строками в GF (2) :${\ displaystyle {\ begin {bmatrix} -P ^ {T} | I_ {nk} \ end {bmatrix}}}$

${\displaystyle \mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}_{1}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\0&1&1&0&1&0\\\end{pmatrix}}_{2}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\0&0&1&1&0&1\\\end{pmatrix}}_{3}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\\\end{pmatrix}}_{4}.}$

Шаг 1: H.

Шаг 2: Ряд 1 добавлен к ряду 3.

Шаг 3: меняются местами строки 2 и 3.

Шаг 4: Ряд 1 добавляем к ряду 3.

Из этого порождающая матрица G может быть получена как (с учетом того, что в частном случае это двоичный код ), или, в частности:${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}$${\displaystyle P=-P}$

${\displaystyle \mathbf {G} ={\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}.}$

Наконец, умножая все восемь возможных 3-битных строк на G , получаются все восемь действительных кодовых слов. Например, кодовое слово для битовой строки «101» получается следующим образом:

${\displaystyle {\begin{pmatrix}1&0&1\\\end{pmatrix}}\odot {\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}={\begin{pmatrix}1&0&1&0&1&1\\\end{pmatrix}}}$,

где - символ умножения по модулю 2.${\displaystyle \odot }$

Для проверки, пространство строк G ортогонально H такое, что${\displaystyle G\odot H^{T}=0}$

Битовая строка «101» находится как первые 3 бита кодового слова «101011».

Пример кодировщика [ править ]

На рисунке 1 показаны функциональные компоненты большинства кодеров LDPC.

Во время кодирования кадра биты входных данных (D) повторяются и распределяются по набору составляющих кодеров. Составляющие кодеры обычно являются накопителями, и каждый накопитель используется для генерации символа четности. Одна копия исходных данных (S _{0, K-1} ) передается с битами четности (P), чтобы составить кодовые символы. S битов от каждого составляющего кодера отбрасываются.

Бит четности может использоваться в другом составляющем коде.

В примере с использованием кода DVB-S2 со скоростью 2/3 размер кодированного блока составляет 64800 символов (N = 64800) с 43200 битами данных (K = 43200) и 21600 битами четности (M = 21600). Каждый составляющий код (контрольный узел) кодирует 16 битов данных, за исключением первого бита четности, который кодирует 8 битов данных. Первые 4680 битов данных повторяются 13 раз (используются в 13 кодах четности), а оставшиеся биты данных используются в 3 кодах четности (нерегулярный код LDPC).

Для сравнения, в классических турбокодах обычно используются два составляющих кода, сконфигурированных параллельно, каждый из которых кодирует весь входной блок (K) битов данных. Эти составляющие кодеры представляют собой рекурсивные сверточные коды (RSC) средней глубины (8 или 16 состояний), которые разделены перемежителем кода, который перемежает одну копию кадра.

Код LDPC, напротив, использует параллельно множество составляющих кодов (аккумуляторов) с низкой глубиной, каждый из которых кодирует только небольшую часть входного кадра. Множество составляющих кодов можно рассматривать как множество «сверточных кодов» с низкой глубиной (2 состояния), которые связаны посредством операций повторения и распределения. Операции повтора и распределения выполняют функцию перемежителя в турбо-коде.

Возможность более точно управлять соединениями различных составляющих кодов и уровнем избыточности для каждого входного бита дает большую гибкость в разработке кодов LDPC, что в некоторых случаях может привести к лучшей производительности, чем турбокоды. Турбо-коды по-прежнему работают лучше, чем LDPC, при низких скоростях кода, или, по крайней мере, конструкция хорошо работающих кодов с низкой скоростью проще для турбо-кодов.

На практике оборудование, которое формирует накопители, повторно используется в процессе кодирования. То есть, как только первый набор битов четности сгенерирован и биты четности сохранены, то же самое аппаратное накопительное оборудование используется для генерации следующего набора битов четности.

Расшифровка [ править ]

Этот раздел требует внимания специалиста в области телекоммуникаций . Пожалуйста, добавьте причину или параметр обсуждения в этот шаблон, чтобы объяснить проблему с разделом. WikiProject Telecommunications может помочь нанять эксперта. ( Ноябрь 2008 г. )

Как и в случае с другими кодами, декодирование с максимальной вероятностью кода LDPC в двоичном симметричном канале является NP-полной проблемой. Оптимальное декодирование NP-полного кода любого полезного размера нецелесообразно.

Однако субоптимальные методы, основанные на итеративном декодировании с распространением убеждений, дают отличные результаты и могут быть практически реализованы. Субоптимальные методы декодирования рассматривают каждую проверку четности, которая составляет LDPC, как независимый код одиночной проверки четности (SPC). Каждый код SPC декодируется отдельно с использованием методов soft-in-soft-out (SISO), таких как SOVA , BCJR , MAP.и другие их производные. Информация мягкого решения от каждого декодирования SISO перекрестно проверяется и обновляется с помощью других избыточных декодирований SPC того же информационного бита. Затем каждый код SPC снова декодируется с использованием обновленной информации мягкого решения. Этот процесс повторяется до тех пор, пока не будет получено действительное кодовое слово или не будет исчерпано декодирование. Этот тип декодирования часто называют декодированием суммарного произведения.

Декодирование кодов SPC часто упоминается как обработка «узла проверки», а перекрестная проверка переменных часто упоминается как обработка «узла переменной».

В практической реализации декодера LDPC наборы кодов SPC декодируются параллельно для увеличения пропускной способности.

Напротив, распространение убеждений по каналу двоичного стирания особенно просто, если оно состоит из итеративного удовлетворения ограничений.

Например, предположим, что действительное кодовое слово 101011 из приведенного выше примера передается по двоичному каналу стирания и принимается со стертыми первым и четвертым битами, чтобы получить «01» 11. Поскольку переданное сообщение должно удовлетворять ограничениям кода, сообщение может быть представлено записью полученного сообщения в верхней части графа факторов.

В этом примере первый бит еще не может быть восстановлен, потому что все связанные с ним ограничения имеют более одного неизвестного бита. Чтобы продолжить декодирование сообщения, необходимо определить ограничения, связанные только с одним из стертых битов. В этом примере достаточно только второго ограничения. Рассматривая второе ограничение, четвертый бит должен быть равен нулю, поскольку только ноль в этой позиции будет удовлетворять ограничению.

Затем эта процедура повторяется. Новое значение четвертого бита теперь можно использовать вместе с первым ограничением для восстановления первого бита, как показано ниже. Это означает, что первый бит должен быть единицей, чтобы удовлетворить крайнему левому ограничению.

Таким образом, сообщение можно декодировать итеративно. Для других моделей каналов сообщения, передаваемые между переменными узлами и проверочными узлами, являются действительными числами , которые выражают вероятность и вероятность веры.

Этот результат может быть подтвержден путем умножения исправленного кодового слова r на матрицу проверки на четность H :

${\displaystyle \mathbf {z} =\mathbf {H\odot r} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}\odot {\begin{pmatrix}1\\0\\1\\0\\1\\1\\\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\\end{pmatrix}}.}$

Поскольку результатом z ( синдромом ) этой операции является нулевой вектор размером 3 × 1, результирующее кодовое слово r успешно проверяется.

После завершения декодирования исходные биты «101» сообщения могут быть извлечены, просмотрев первые 3 бита кодового слова.

Хотя этот пример стирания является иллюстративным, он не показывает использование декодирования с мягким решением или передачи сообщений с мягким решением, которые используются практически во всех коммерческих декодерах LDPC.

Обновление информации об узле [ править ]

В последние годы также было проведено много работы по изучению эффектов альтернативных расписаний для обновления переменных-узлов и ограничений-узлов. Первоначальный метод, который использовался для декодирования кодов LDPC, был известен как лавинная рассылка . Этот тип обновления требовал, чтобы перед обновлением узла переменной необходимо было обновить все узлы ограничений, и наоборот. В более поздней работе Vila Casado et al. , ^[17] были изучены альтернативные методы обновления, в которых переменные узлы обновляются новейшей доступной информацией о проверочных узлах.

Интуиция, лежащая в основе этих алгоритмов, заключается в том, что узлы переменных, значения которых изменяются больше всего, должны быть обновлены в первую очередь. Высоконадежные узлы, величина логарифмического отношения правдоподобия (LLR) которых велика и существенно не меняется от одного обновления к другому, не требуют обновлений с той же частотой, что и другие узлы, знак и величина которых колеблются более широко. Эти алгоритмы планирования показывают более высокую скорость сходимости и более низкие минимальные уровни ошибок, чем те, которые используют лавинную рассылку. Эти более низкие минимальные уровни ошибок достигаются за счет способности алгоритма информированного динамического планирования (IDS) ^[17] преодолевать захват наборов близких кодовых слов. ^[18]

Когда используются алгоритмы планирования без заводнения, используется альтернативное определение итерации. Для ( n ,  k ) кода LDPC со скоростью k / n полная итерация происходит, когда n переменных и n  -  k узлов ограничений были обновлены, независимо от порядка, в котором они были обновлены.

Построение кода [ править ]

Для больших размеров блоков коды LDPC обычно строятся путем предварительного изучения поведения декодеров. Поскольку размер блока стремится к бесконечности, можно показать, что декодеры LDPC имеют порог шума, ниже которого декодирование выполняется надежно, а выше которого декодирование не достигается, ^{[19] в} просторечии называется эффектом обрыва . Этот порог можно оптимизировать, найдя лучшую пропорцию дуг из контрольных узлов и дуг из переменных узлов. Примерный графический подход к визуализации этого порога - диаграмма ВЫХОДА .

Построение определенного кода LDPC после этой оптимизации делится на два основных типа методов:

• Псевдослучайные подходы
• Комбинаторные подходы

Построение с помощью псевдослучайного подхода основано на теоретических результатах, которые для большого размера блока случайное построение дает хорошие характеристики декодирования. ^[9] В общем, псевдослучайные коды имеют сложные кодеры, но псевдослучайные коды с лучшими декодерами могут иметь простые кодеры. ^[20] Часто применяются различные ограничения, чтобы гарантировать, что желаемые свойства, ожидаемые при теоретическом пределе бесконечного размера блока, возникают при конечном размере блока.

Комбинаторные подходы могут использоваться для оптимизации свойств кодов LDPC небольшого размера или для создания кодов с помощью простых кодировщиков.

Некоторые коды LDPC основаны на кодах Рида – Соломона , например код RS-LDPC, используемый в стандарте 10 Gigabit Ethernet . ^[21] По сравнению со случайно сгенерированными кодами LDPC, структурированные коды LDPC, такие как код LDPC, используемый в стандарте DVB-S2, могут иметь более простое и, следовательно, более дешевое оборудование, в частности, коды, построенные так, что матрица H является циркулянтной. матрица . ^[22]

Еще один способ построения LDPC-кодов - использовать конечную геометрию . Этот метод был предложен Y. Kou et al. в 2001 году. ^[23]

LDPC-коды и турбокоды [ править ]

Коды LDPC можно сравнить с другими мощными схемами кодирования, например с турбокодами. ^[24] С одной стороны, на производительность турбо кодов BER влияют ограничения младших кодов. ^[25] Коды LDPC не имеют ограничений по минимальному расстоянию ^[26], что косвенно означает, что коды LDPC могут быть более эффективными при относительно больших скоростях кода (например, 3/4, 5/6, 7/8), чем турбокоды. Однако коды LDPC не являются полной заменой: турбокоды - лучшее решение при более низких кодовых скоростях (например, 1/6, 1/3, 1/2). ^{[27] [28]}

См. Также [ править ]

Люди [ править ]

• Роберт Г. Галлагер
• Ричард Хэмминг
• Клод Шеннон
• Дэвид Дж. К. Маккей
• Ирвинг С. Рид
• Майкл Луби

Теория [ править ]

• Распространение веры
• Теория графов
• Код Хэмминга
• Линейный код
• Код разреженного графа
• Код расширителя

Приложения [ править ]

• G.hn/G.9960 (стандарт ITU-T для сетей по линиям электропередачи, телефонным линиям и коаксиальному кабелю)
• 802.3an или 10GBASE-T (10 Гбит / с Ethernet по витой паре)
• CMMB (Китайское мультимедийное мобильное вещание)
• DVB-S2 / DVB-T2 / DVB-C2 (цифровое видеовещание, 2-е поколение)
• DMB-T / H (цифровое видеовещание) ^[29]
• WiMAX (стандарт IEEE 802.16e для микроволновой связи)
• IEEE 802.11n-2009 ( стандарт Wi-Fi )
• DOCSIS 3.1

Другие коды приближения к мощности [ править ]

• Турбо коды
• Последовательные каскадные сверточные коды
• Онлайн коды
• Коды фонтанов
• Коды LT
• Коды хищников
• Коды с повторением-накоплением (класс простых турбокодов)
• Коды торнадо ( коды LDPC, предназначенные для декодирования стирания )
• Полярные коды

Ссылки [ править ]

Внешние ссылки [ править ]

• Представляем коды проверки на четность с низкой плотностью (Сара Дж. Джонсон, 2010 г.)
• Коды LDPC - краткое руководство (Бернхард Лейнер, 2005)
• Коды LDPC (TU Wien)
• Он-лайн учебник: Теория информации, логический вывод и алгоритмы обучения , написанный Дэвидом Дж. Маккеем , обсуждает коды LDPC в главе 47.
• Итеративное декодирование кодов проверки на четность с низкой плотностью (Венкатесан Гурусвами, 2006 г.)
• Коды LDPC: Введение (Амин Шокроллахи, 2003)
• Декодирование кодов LDPC с распространением убеждений (Амир Беннатан, Принстонский университет)
• Коды Turbo и LDPC: реализация, моделирование и стандартизация (Университет Западной Вирджинии)
• Теория информации и кодирование (Марко Хеннхёфер, 2011, TU Ilmenau) - обсуждает коды LDPC на страницах 74-78.
• Коды LDPC и результаты производительности
• Канал DVB-S.2, включая кодирование LDPC (MatLab)
• Исходный код для кодирования, декодирования и моделирования кодов LDPC доступен в разных местах:
  • Двоичные коды LDPC в C
  • Двоичные коды LDPC для Python (основной алгоритм на C)
  • LDPC - кодер и LDPC - декодер в MATLAB
  • Набор инструментов Fast Forward Error Correction Toolbox (AFF3CT) в C ++ 11 для быстрого моделирования LDPC