Полярные коды: от теории к практике

Полярные коды

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

Фактически, такой подход задает некоторый метод кодирования данных (полярное кодирование). Э. Ариканом было показано, что полярные коды достигают пропускной способности широкого класса каналов передачи информации, обладая при этом простыми процедурами построения, кодирования и декодирования. Такой результат был получен впервые с 1948 года, когда К. Шеннон показал принципиальную возможность создания таких методов кодирования.  Несмотря на то, что кодовые конструкции, достигающие пропускной способности различных каналов были известны и ранее, они не нашли практического применения из-за высокой сложности своей реализации. Полярные коды ввиду своей простоты имеют значительный потенциал использования в системах передачи и хранения информации.

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

Полярные подкоды (полярные коды с динамически замороженными символами)

П.В. Трифоновым, В.Д. Милославской и Г.А, Трофимюком было предложено обобщение конструкции полярных кодов. Вместо того, чтобы передавать 0 по некоторым синтетическим подканалам, как в классической конструкции Арикана, было предложено передавать взвешенную сумму некоторых символов, передаваемых по другим подканалам. Конкретные весовые коэффициенты выбираются так, чтобы получаемый код имел хорошие дистантные свойства. Построенные таким образом коды демонстрируют значительно большую корректирующую способность по сравнению с известными LDPC и турбо-кодами.

В.Д. Милославской был предложен метод укорочения полярных (под)кодов, который позволяет получить коды произвольной длины, что невозможно в рамках классической конструкции Арикана.

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

Последовательное декодирование полярных кодов

В.Д. Милославской и П.В. Трифоновым был предложен алгоритм последовательного декодирования полярных кодов. В отличие от предложенных другими исследователями алгоритмов списочного декодирования, предложенный подход исключает выполнение значительной доли бесполезных вычислений.  За счет этого сложность декодирования оказывается меньше, а корректирующая способность - лучше, чем у LDPC и турбо-кодов с сопоставимыми параметрами. Данный подход допускает обобщение на случай полярных кодов с произвольными ядрами, а также коротких кодов Рида-Соломона. Методы дальнейшего снижения сложности данного метода декодирования были разработаны Г. Трофимюком и Н. Якубой.

 

 

Вероятность ошибки на кодовое слово для кодов с размерностью 1024
Сложность декодирования кодов с размерностью 1024
Отношение сигнал/шум, требуемое для достижения вероятности ошибки 1E-2 на кодовое слово
 

Публикации