ldpc коды определение проверочной матрицы

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

Также называют кодом Галлагера, по имени автора первой работы на тему LDPC-кодов.

Содержание

Предпосылки

При передаче информации её поток разбивается на блоки определённой (чаще всего) длины, которые преобразуются кодером (кодируются) в блоки, называемыми ключевыми словами. Ключевые слова передаются по каналу, возможно с искажениями. На принимающей стороне декодер преобразует ключевые слова в поток информации, исправляя (по возможности) ошибки передачи.

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

Первой работой на эту тему стала работа Роберта Галлагера «Low-Density Parity-Check Codes» 1963 года [2] (основы которой были заложены в его докторской диссертации 1960 года). В работе учёный описал требования к таким кодам, описал возможные способы построения и способы их оценки. Поэтому часто LDPC-коды называют кодами Галлагера. В русской научной литературе коды также называют низкоплотностными кодами или кодами с малой плотностью проверок на чётность.

LDPC-коды

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

Обычно рассматриваются матрицы больших размеров. Например, в работе Галлагера в разделе экспериментальных результатов используются «малые» количества строк n=124, 252, 504 и 1008 строк (число столбцов проверочной матрицы немного больше). На практике применяются матрицы с большим количеством элементов — от 10 до 100 тысяч строк. Однако количество единиц в строке или в столбце остаётся достаточно малым, обычно меньшим 10. Замечено, что коды с тем же количеством элементов на строку или столбец, но с большим размером, обладают лучшими характеристиками.

Важной характеристикой матрицы LDPC-кода является отсутствие циклов определённого размера. Под циклом длины 4 понимают образование в проверочной матрице прямоугольника, в углах которого стоят единицы. Отсутствие цикла длины 4 можно также определить через скалярное произведение столбцов (или строк) матрицы. Если каждое попарное скалярное произведение всех столбцов (или строк) матрицы не более 1, это говорит об отсутствии цикла длины 4. Циклы большей длины (6, 8, 10 и т. д.) можно определить, если в проверочной матрице построить граф, вершинами которого являются единицы, а рёбра — все возможные соединения вершин, параллельные сторонам матрицы (то есть вертикальные или горизонтальные линии). Минимальный цикл в этом графе и будет минимальным циклом в проверочной матрице LDPC-кода. Очевидно, что цикл будет иметь длину как минимум 4, а не 3, так как рёбра графа должны быть параллельны сторонам матрицы. Вообще, любой цикл в этом графе будет иметь чётную длину, минимальный размер 4, а максимальный размер обычно не играет роли (хотя, очевидно, он не более, чем количество узлов в графе, то есть n×k).

Описание LPDC-кода возможно несколькими способами:

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

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

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

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

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

При использовании специальных процедур построения кода могут использоваться и свои способы представления, хранения и обработки (кодирования и декодирования).

Построение кода

В настоящее время используются два принципа построения проверочной матрицы кода. Первый основан на генерации начальной проверочной матрицы с помощью псевдослучайного генератора. Коды, полученные таким способом называют случайными (англ. random-like codes ). Второй — использование специальных методов, основанных, например, на группах и конечных полях. Коды, полученные этими способами называют структурированными. Лучшие результаты по исправлению ошибок показывают именно случайные коды, однако структурированные коды позволяют использовать методы оптимизации процедур хранения, кодирования и декодирования, а также получать коды с более предсказуемыми характеристиками.

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

В 2007 году в журнале «IEEE Transactions on Information Threory» была опубликована статья об использовании конечных полей для построения квази-цикличных LDPC-кодов для каналов с аддитивным белым Гауссовым шумом и двоичных каналов со стиранием.

Декодирование

Как и для любого другого линейного кода, для декодирования используется свойство ортогональности порождающей и транспонированной проверочной матриц:

где — порождающая матрица, и — проверочная. Тогда для каждого принятого без ошибок кодового слова выполняется отношение

,

а для принятого кодового слова с ошибкой:

,

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

Данные значения используются воссоздания вектора x. Если полученный вектор удовлетворяет , то алгоритм на этом прерывается, иначе повторяются горизонтальный и вертикальные шаги. Если же алгоритм продолжается до некоторого шага (например, 100), то он прерывается и блок объявляется принятым с ошибкой.

Источник

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

Также называют кодом Галлагера, по имени автора первой работы на тему LDPC-кодов.

Содержание

Предпосылки

При передаче информации её поток разбивается на блоки определённой (чаще всего) длины, которые преобразуются кодером (кодируются) в блоки, называемыми ключевыми словами. Ключевые слова передаются по каналу, возможно с искажениями. На принимающей стороне декодер преобразует ключевые слова в поток информации, исправляя (по возможности) ошибки передачи.

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

Первой работой на эту тему стала работа Роберта Галлагера «Low-Density Parity-Check Codes» 1963 года [2] (основы которой были заложены в его докторской диссертации 1960 года). В работе учёный описал требования к таким кодам, описал возможные способы построения и способы их оценки. Поэтому часто LDPC-коды назвают кодами Галлагера. В русской научной литературе коды также называют низкоплотностными кодами или кодами с малой плотностью проверок на чётность.

LDPC-коды

LDPC-коды описываются низкоплотностой проверочной матрицей, содержащей в основном нули и относительно малое количество единиц. По определению, если каждая строка матрицы содержит ровно k и каждый столбец ровно j единиц, то код называют регулярным (в противном случае — нерегулярным). В общем случае количество единиц в матрице имеет порядок , то есть растёт линейно с увеличением длины кодового блока (количества столбцов проверочной матрицы).

Обычно рассматриваются матрицы больших размеров. Например, в работе Галлагера в разделе экспериментальных результатов используются «малые» количества строк n=124, 252, 504 и 1008 строк (число столбцов проверочной матрицы немного больше). На практике применяются матрицы с большим количеством элементов — от 10 до 100 тысяч строк. Однако количество единиц в строке или в столбце остаётся достаточно малым, обычно меньшим 10. Замечено, что коды с тем же количество элементов на строку или столбец, но с большим размером, обладают лучшими характеристиками.

Важной характеристикой матрицы LDPC-кода является отсутсвие циклов определённого размера. Под циклом длины 4 понимают образование в проверочной матрице прямоугольника, в углах которого стоят единицы. Отсутствие цикла длины 4 можно также определить через скалярное произведение столбцов (или строк) матрицы. Если каждое попарное скалярное произведение всех столбцов (или строк) матрицы не более 1, это говорит об отсутствии цикла длины 4. Циклы большей длины (6, 8, 10 и т. д.) можно определить, если в проверочной матрице построить граф, вершинами которого являются единицы, а рёбра — все возможные соединения вершин, параллельные сторонам матрицы (то есть вертикальные или горизонтальные линии). Минимальный цикл в этом графе и будет минимальным циклом в проверочной матрице LDPC-кода. Очевидно, что цикл будет иметь длину как минимум 4, а не 3, так как рёбра графа должны быть параллельны стронами матрицы. Вообще, любой цикл в этом графе будет иметь чётную длину, минимальный размер 4, а максимальный размер обычно не играет роли (хотя, очевидно, он не более, чем количество узлов в графе, то есть n×k).

Описание LPDC-кода возможно несколькими способами:

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

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

Распространённым графическим способом является представление кода в виде двудольного графа. Сопоставим все k строк матрицы k нижним вершинам графа, а n столбцов — верхним, и соединим верхние и нижние вершины графа, если на пересечении соответствующих строк и столбцов стоят единицы.

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

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

При использовании специальных процедур построения кода могут использоваться и свои способы представления, хранения и обработки (кодирования и декодирования).

Построение кода

В настоящее время используются два принципа построения проверочной матрицы кода. Первый основан на генерации начальной проверочной матрицы с помощью псевдослучайного генератора. Коды, полученные таким способом называют случайными (англ. random-like codes ). Второй — использование специальных методов, основанных, например, на группах и конечных полях. Коды, полученные этими способами называют структурированными. Лучшие результаты по исправлению ошибок показывают именно случайные коды, однако структурированные коды позволяют использовать методы оптимизации процедур хранения, кодирования и декодирования, а также получать коды с более предсказуемыми характеристиками.

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

В 2007 году в журнале «IEEE Transactions on Information Threory» была опубликована статья об использовании конечных полей для построения квази-цикличных LDPC-кодов для каналов с аддитивным белым Гауссовым шумом и двоичных каналов со стиранием.

Декодирование

Как и для любого другого линейного кода, для декодирования используется свойство ортогональности порождающей и транспонированной проверочной матриц:

где G — порождающая матрица, и H — проверочная. Тогда для каждого принятого без ошибок кодового слова выполняется отношение

,

а для принятого кодового слова с ошибкой:

,

Данные значения используются воссоздания вектора x. Если полученный вектор удовлетворяет , то алгоритм на этом прерывается, иначе повторяются горизонтальный и вертикальные шаги. Если же алгоритм продолжаеся до некоторого шага (например, 100), то он прерывается и блок объявлявляется принятым с ошибкой.

Источник

Содержание

История

Приложения

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

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

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

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

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

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

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

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

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

Битовая строка «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, при низких скоростях кода, или, по крайней мере, конструкция хорошо работающих кодов с низкой скоростью проще для турбо-кодов.

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

Расшифровка

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

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

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

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

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

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

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

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

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

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

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

Обновление информации об узле

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

Построение кода

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

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

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

Коды LDPC против турбокодов

Источник