Polar codes: from theory to practice

Performance of codes with dimension 1024
Average decoding complexity of codes with dimension 1024
Signal-to-noise ratio required for achieving codeword error probability 1E-2

Polar codes

Channel polarization phenomenon was discovered by E. Arikan in 2008. Essentially, by employing very simple operations one can transform a data transmission channel into a number almost noiseless and almost pure-noise synthetic subchannels. Then one can transmit the payload data over almost  noiseless subchannels with very high reliability. Some deterministic symbols (normally, 0) should be trasmitted over almost pure-noise synthetic suchannels.  

This approach defines a forward error correction method (polar coding). E. Arikan has shown that polar codes achieve Shannon capacity of a wide class of communication channels, having very simple construction, encoding and decoding algorithms. This is the first result of such kind since  1948, when C. Shannon shown the theoretical possibility of creation of such coding methods.  Although code constructions achieving the capacity  of some channels have been previously known, they did not find practical applications due to high implementation complexity. Owing to their simplicity, polar codes have great potential for finding their way into communication and storage systems.

However, it appears that the performance of Arikan polar codes with practically important parameters is substantially inferior compared to similar  LDPC and turbo codes. Furthermore, the complexity and latency of classical decoding methods for polar codes significantly exceeds that of  LDPC codes. Since 2011, Coding Theory Lab of SPbPU is working on overcoming these problems and development of code constructions and decoding algorithms with better performance and lower complexity compared to the existing techniques.

Polar subcodes (Polar codes with dynamic frozen symbols)

P. V. Trifonov and V. D. Miloslavskaya have suggested a generalization of the polar code construction. Instead of transmitting 0 over some synthetic bit subchannels, as in the classical Arikan construction, it was suggested to transmit some weighted sum of the symbols transmitted over the other subchannels (dynamic frozen symbols). The particular weighting coefficients are selected in such way, so that the obtained code is a subcode of an extended BCH code. This enables one to obtain codes with substantially higher minimum distance compared to classical polar codes. The codes constructed in this way provide much better performance compared to known  LDPC and turbo codes.

V.D. Miloslavskaya has suggested a method for shortening polar (sub)codes, which enables one to obtain codes of arbitrary length, which is not possible in the framework of the classical Arikan construction.

This page presents a database of  some polar subcodes. These codes can be decoded using the same techniques as Arikan polar codes.

Sequential decoding of polar codes

V.D. Miloslavskaya and P. V. Trifonov have suggested a sequential decoding algorithm for polar codes. As opposed to the list decoding algorithms suggested by some researchers, the proposed approach avoids a large fraction of useless computation.  As a result, the decoding complexity appears to be less, and the performance is better compared to the case of LDPC and turbo codes with similar parameters. This approach can be extended to the case of polar codes with arbitrary kernel, as well as short Reed-Solomon codes. Further complexity reduction techniques for this approach were developed by G. Trofimiuk and N. Iakuba.

 

 

References

References
38.
Moskovskaya, Elizaveta; Trifonov, Peter
Design of BCH Polarization Kernels with Reduced Processing Complexity
IEEE Communications Letters,
2020

Keywords: polar

37.
Karakchieva, L,; Trifonov, P.
An Approximate Method for Construction of Polar codes with Kernels over F2t
IEEE Communications Letters,
2020
accepted

Keywords: polar

36.
Trifonov, Peter
Recursive Trellis Decoding Techniques of Polar Codes
Proceedings of IEEE International Symposium on Information Theory
2020

Keywords: polar

35.
Morozov, Ruslan; Trifonov, Peter
On Distance Properties of Convolutional Polar Codes
IEEE Transactions on Communications, 67(7):4585 - 4592
July 2019
ISSN: 1558-0857

Keywords: convolutional polar, b-MERA

34.
Morozov, Ruslan; Trifonov, Peter
Successive and Two-Stage Systematic Encoding of Polar Subcodes
IEEE Wireless Communications Letters, 8(3):877 - 880
June 2019
ISSN: 2162-2345

Keywords: polar

33.
Морозов, Руслан; Трифонов, Пётр
Компактная спецификация полярных кодов
Информационно-Управляющие Системы, 98(1):40-47
2019
ISSN: 2541-8610

Keywords: polar

32.
Ivanov, K.; Trifonov, P.
Polar Subcodes for Encoding and Blind Decoding of Variable-Sized Data Blocks
12th International ITG Conference on Systems, Communications and Coding
2019

Keywords: polar

31.
Trifonov, Peter
On Construction of Polar Subcodes with Large Kernels
Proceedings of IEEE International Symposium on Information Theory
2019

Keywords: polar

30.
Trofimiuk, Grigorii; Trifonov, Peter
Reduced complexity window processing of binary polarization kernels
Proceedings of IEEE International Symposium on Information Theory
2019

Keywords: polar

29.
Morozov, Ruslan; Trifonov, Peter
A Lower Bound on Minimum Distance of Convolutional Polar Codes
Proceedings of IEEE International Symposium on Information Theory
2019

Keywords: polar

28.
Trifonov, Peter
Trellis-based Decoding Techniques for Polar Codes with Large Kernels
Proceedings of IEEE Information Theory Workshop
2019

Keywords: polar

27.
Trofimiuk, Grigorii; Trifonov, Peter
Construction of binary polarization kernels for low complexity window processing
Proceedings of IEEE Information Theory Workshop
2019

Keywords: polar

26.
Trifonov, P.
Randomized Chained Polar Subcodes
Proceedings of Wireless Communications and Networking Conference Workshops , page 25-30.
2018

Keywords: polar

25.
Trifonov, Peter
Chained Successive Cancellation Decoding of the Extended Golay Code
Proceedings of Iran Workshop on Communication and Information Theory
2018

Keywords: polar

24.
Trifonov, Peter
A score function for sequential decoding of polar codes
Proceedings of IEEE International Symposium on Information Theory
2018

Keywords: polar

23.
Trifonov, Peter
Algebraic matching techniques for fast decoding of polar codes with Reed-Solomon kernel
Proceedings of IEEE International Symposium on Information Theory
2018

Keywords: polar

22.
Morozov, Ruslan; Trifonov, Peter
Efficient SC Decoding of Convolutional Polar Codes
Proceedings of International Symposium on Information Theory and Applications
2018

Keywords: convolutional polar, b-MERA

21.
Trofimiuk, G.; Trifonov, P.
Efficient decoding of polar codes with some 16 x 16 kernels
Proceedings of IEEE Information Theory Workshop
2018

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

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