Polar codes: from theory to practice
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 purenoise 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 purenoise 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 ReedSolomon codes. Further complexity reduction techniques for this approach were developed by G. Trofimiuk and N. Iakuba.
References
20. 
A Randomized Construction of Polar Subcodes
Proceedings of IEEE International Symposium on Information Theory
, page 18631867.
2017

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

18. 
Star polar subcodes
Proceedings of IEEE Wireless Communications and Networking Conference Workshops
2017

17. 
Fast Encoding of Polar Codes with ReedSolomon Kernel
IEEE Transactions on Communications,
64(7):27462753
July
2016

16. 
Polar subcodes
IEEE Journal on Selected Areas in Communications,
34(2):254266
February
2016

15. 
Hybrid Decoding of Interlinked Generalized Concatenated Codes
Proceedings of 9th International Symposium on Turbo Codes and Iterative Information Processing
2016

14. 
Directed Search Decoding of Polar Codes with ReedSolomon kernel
Proceedings of XV International Symposium "Problems of Redundancy in Information and Control Systems"
2016
accepted

13. 
Shortened Polar Codes
IEEE Transactions on Information Theory,
61(9):48524865
September
2015
ISSN: 00189448

12. 
Block Sequential Decoding of Polar Codes
Proceedings of International Symposium on
Wireless Communication Systems
2015

11. 
Design of Polar Codes for Rayleigh Fading Channel
Proceedings of The International Symposium on
Wireless Communication Systems
2015

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

9. 
Sequential Decoding of Polar Codes
IEEE Communications Letters,
18(7):1127  1130
July
2014

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

7. 
Binary Successive Cancellation Decoding of Polar Codes with ReedSolomon Kernel
Proceedings of IEEE International Symposium on Information Theory
, page 2972  2976.
2014

6. 
Sequential Decoding of Polar Codes with Arbitrary Binary Kernel
Proceedings of IEEE Information Theory Workshop
, page 376  380.
2014

5. 
Sequential Decoding of ReedSolomon Codes
Proceedings of International Symposium on Information Theory and its Applications
, page 466470.
2014

4. 
Successive Cancellation Permutation Decoding of ReedSolomon Codes
Proceedings of IEEE Information Theory Workshop
, page 386  390.
2014

3. 
Twisted polar codes
Proceedings of International Symposium on Information Theory and Its Applications
, page 456460.
2014

2. 
Polar Codes with Dynamic Frozen Symbols and Their Decoding by Directed Search
Proceedings of IEEE Information Theory Workshop
, page 15.
2013

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

Contacts
Polytechnicheskaya str., 21, office 103
194021, SaintPetersburg, Russia
Phone: +78122970629
Head of the Coding Theory and Telecommunications Group: Associate Professor Peter V. Trifonov