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

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

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

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

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

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

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

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

Данная конструкция положена в основу процедуры канального кодирования стандарта 5G.

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

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

Полярные коды с большими ядрами

Полярные коды с большими ядрами обеспечивают намного лучшее масштабирование корректирующей способности в зависимости от длины кода по сравнению с классическими полярными кодами с ядром Арикана. Однако до недавнего времени отсутствовали простые алгоритмы декодирования таких кодов. Г.А. Трофимюком и П.В. Трифоновым был предложен оконный алгоритм, обеспечивающий быстрое декодирование полярных кодов с ядрами размерности 2^m, а также семейство ядер, для которых этот алгоритм оказывается особо эффективным. В результате при списочном декодировании полярные подкоды с большими ядрами демонстрируют лучшую корректирующую способность по сравнению с аналогичными кодами с ядром Арикана с той же сложностью декодирования. В некоторых случаях обеспечивается одновременно меньшая сложность и лучшая корректирующая способность по сравнению с кодами, основанными на ядре Арикана.

IEEE Communications Society Best Readings in Polar Coding

Следующие статьи нашей группы включены в список IEEE Communications Society Best Readings in Polar Coding:

• P. Trifonov, “Efficient Design and Decoding of Polar Codes,” IEEE Transactions on Communications, vol. 60, no. 11, pp. 3221-3227, November 2012.
• P. Trifonov and V. Miloslavskaya, “Polar Subcodes,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 2, pp. 254-266, February 2016.
• P. Trifonov, “A Score Function for Sequential Decoding of Polar Codes,” in Proc. IEEE International Symposium on Information Theory (ISIT), Vail, USA, June 2018.
• G. Trofimiuk and P. Trifonov, “Efficient Decoding of Polar Codes with Some 16×16 Kernels,” in Proc. IEEE Inf. Theory Workshop (ITW), Guangzhou, China, November 2018.