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

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

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

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

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

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

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

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

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

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

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

 

 

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

Публикации

References
21.
Trifonov, P.
Randomized Chained Polar Subcodes
Proceedings of Wireless Communications and Networking Conference Workshops
2018
accepted

Keywords: polar

20.
Trifonov, P.
Chained polar subcodes
Proceedings of 11th International ITG Conference on Systems, Communications and Coding
2017

Keywords: polar

19.
Trifonov, P.
Star polar subcodes
Proceedings of IEEE Wireless Communications and Networking Conference Workshops
2017

Keywords: polar

18.
Trifonov, P.; Trofimiuk, G.
A Randomized Construction of Polar Subcodes
Proceedings of IEEE International Symposium on Information Theory , page 1863-1867.
2017

Keywords: polar

17.
Trifonov, Peter, Miloslavskaya, Vera, Chen, Chen; Wang, Yuangang
Fast Encoding of Polar Codes with Reed-Solomon Kernel
IEEE Transactions on Communications, 64(7):2746-2753
July 2016

Keywords: polar

16.
Trifonov, P.; Miloslavskaya, V.
Polar subcodes
IEEE Journal on Selected Areas in Communications, 34(2):254-266
February 2016

Keywords: polar

15.
Ivanov, K.; Trifonov, P.
Hybrid Decoding of Interlinked Generalized Concatenated Codes
Proceedings of 9th International Symposium on Turbo Codes and Iterative Information Processing
2016

Keywords: polar

14.
Morozov, Ruslan; Trifonov, Peter
Directed Search Decoding of Polar Codes with Reed-Solomon kernel
Proceedings of XV International Symposium "Problems of Redundancy in Information and Control Systems"
2016
accepted

Keywords: polar

13.
Miloslavskaya, Vera
Shortened Polar Codes
IEEE Transactions on Information Theory, 61(9):4852-4865
September 2015
ISSN: 0018-9448

Keywords: polar

12.
Trifonov, P.
Design of Polar Codes for Rayleigh Fading Channel
Proceedings of The International Symposium on Wireless Communication Systems
2015

Keywords: polar

11.
Trofimiuk, G.; Trifonov, P.
Block Sequential Decoding of Polar Codes
Proceedings of International Symposium on Wireless Communication Systems
2015

Keywords: polar

10.
Iakuba, N.; Trifonov, P.
Multilevel Buckets for Sequential Decoding of Polar Codes
Proceedings of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications
2015

Keywords: polar

9.
Miloslavskaya, Vera; Trifonov, Peter
Sequential Decoding of Polar Codes
IEEE Communications Letters, 18(7):1127 - 1130
July 2014

Keywords: polar

8.
Trifonov, P.
Successive Cancellation Decoding of Reed–Solomon Codes
Problems of Information Transmission, 50(4)
2014

Keywords: polar

7.
Trifonov, P.
Binary Successive Cancellation Decoding of Polar Codes with Reed-Solomon Kernel
Proceedings of IEEE International Symposium on Information Theory , page 2972 - 2976.
2014

Keywords: polar

6.
Miloslavskaya, V.; Trifonov, P.
Sequential Decoding of Reed-Solomon Codes
Proceedings of International Symposium on Information Theory and its Applications , page 466-470.
2014

Keywords: polar

5.
Trifonov, P.; Miloslavskaya, V.
Twisted polar codes
Proceedings of International Symposium on Information Theory and Its Applications , page 456-460.
2014

Keywords: polar

4.
Trifonov, P.
Successive Cancellation Permutation Decoding of Reed-Solomon Codes
Proceedings of IEEE Information Theory Workshop , page 386 - 390.
2014

Keywords: polar

3.
Miloslavskaya, V.; Trifonov, P.
Sequential Decoding of Polar Codes with Arbitrary Binary Kernel
Proceedings of IEEE Information Theory Workshop , page 376 - 380.
2014

Keywords: polar

2.
Trifonov, Peter; Miloslavskaya, Vera
Polar Codes with Dynamic Frozen Symbols and Their Decoding by Directed Search
Proceedings of IEEE Information Theory Workshop , page 1-5.
2013

Keywords: polar

1.
Trifonov, Peter
Efficient Design and Decoding of Polar Codes
IEEE Transactions on Communications, 60(11):3221 - 3227
November 2012

Keywords: polar

Export as:
BibTeX, XML