Polar codes were introduced by Erdal Arıkan in 2008. They are the first family of error-correcting codes that attain the capacity of binary-input memoryless and symmetric channels with efficient encoding, decoding, and construction algorithms. Since their introduction, polar codes have been generalized and shown to be capacity achieving in numerous other communications settings.
The original construction of polar codes relies on the recursive application of an invertible linear transformation, which, when combined with a successive-cancellation decoder, effectively splits the original binary-input memoryless and symmetric communication channel into a number of bit subchannels. Increasing the recursion depth causes these bit subchannels to converge either to noiseless or purely noisy channels. Virtually error-free transmission can be achieved by sending the data over noiseless subchannels. While related code constructions had been suggested before (e.g., N. Stolte, I. Dumer and K. Shabunov), Arıkan’s work was the first to prove the polarization phenomenon and thus prove that polar codes are capacity achieving.
Unfortunately, the subchannels converge to these limiting cases relatively slowly, meaning that the error-correcting performance of Arıkan’s polar codes improves more slowly with the blocklength than other widely-used codes, such as Turbo and LDPC codes. However, polar codes have been shown to provide excellent error-correcting performance with low decoding complexity for practical blocklengths when combined with more advanced decoding algorithms. These favorable traits have led to polar codes being used in the 5G wireless standard, which is a testament to their outstanding performance.
In this Best Readings, we summarize several papers on the theoretical foundations of polarization theory, the construction and decoding of practical polar codes, as well as some generalized polar codes, which can help to overcome limitations of classical Arıkan polar codes. We also focus on practical implementation issues because, despite the simple structure of the encoding and decoding algorithms of polar codes, their practical implementation poses numerous challenges.
Issued June 2019
Alexios Balatsoukas-Stimming, EPFL, Switzerland
Ingmar Land, Huawei Technologies, France
Ido Tal, Technion – Israel Institute of Technology, Israel
Peter Trifonov, Peter the Great St. Petersburg Polytechnic University, Russia
Emanuele Viterbo, Monash University, Australia
Matthew C. Valenti
Editor-in-Chief, ComSoc Best Readings
West Virginia University
Morgantown, WV, USA
After introducing some textbooks, overviews & tutorials, special issues, and standards-related articles, we divide the technical papers into the following seven areas:
- Information-theoretic basics
- Construction and encoding
- Improved and low-complexity decoding
- Hardware and software implementation
- Polar coding for general channels
- Generalized polar codes
We note that readers who are mostly interested in the practical aspects of polar coding can focus on topics 1, 3, 4, and 5.
E. Şaşoğlu, Polarization and Polar Codes, Now Publishers Inc, 2012.
This monograph starts with an explanation of channel polarization and how it is used to construct polar codes. The concept of channel polarization is then generalized to non-binary input channels and to polarization kernels of sizes larger than the 2x2 kernel used by Arıkan in his seminal work on channel polarization. Finally, some discussion is provided on the joint polarization of multiple random variables with applications to multi-user channels.
O. Gazi, Polar Codes: A Non-Trivial Approach to Channel Coding, Springer, 2018.
This book explains the philosophy behind the idea of polar encoding from an information-theoretic perspective. It then discusses the successive-cancellation decoding algorithm and associated operations in a tree structure. It also demonstrates the calculation of split channel capacities when polar codes are employed for binary erasure channels, and explains the mathematical formulation of successive-cancellation decoding for polar codes.
P. Giard, C. Thibeault, and W. J. Gross, High-Speed Decoders for Polar Codes, Springer International Publishing, 2017.
This book focuses on the implementation of fast-SSC-based polar decoders. In particular, the authors consider the hardware and software implementation of standard fast-SSC decoding, as well as the hardware implementation of ultra-high-speed unrolled decoders enabled by fast-SSC decoding.
- Overviews and Tutorials
E. Arıkan, “On the Origin of Polar Coding,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 2, pp. 209-223, February 2016.
This paper gives a historical overview of the steps that lead to the discovery of polar codes. Several pre-existing techniques and their relation to polar coding are described in detail, giving readers very useful intuition.
K. Niu, K. Chen, J. Lin, and Q. T. Zhang, “Polar Codes: Primary Concepts and Practical Decoding Algorithms,” IEEE Communications Magazine, vol. 52, no. 7, pp. 60-69, July 2014.
This tutorial paper provides a simple discussion of the main principles behind polar coding. The authors discuss the notion of channel polarization and how it is used in order to construct polar codes. A wide range of decoding algorithms is explained, including successive-cancellation decoding, improved and fast successive-cancellation decoding algorithms, and belief-propagation decoding. Finally, the authors provide a comparison of the error-correcting performance of polar codes with WCDMA and LTE turbo codes, as well as WiMax LDPC codes.
A. Balatsoukas-Stimming, P. Giard, and A. Burg, “Comparison of Polar Decoders with Existing Low-Density Parity-Check and Turbo Decoders,” in Proc. IEEE Wireless Communications and Networking Conference (WCNC) Workshops, San Francisco, USA, March 2017.
This survey paper compares polar codes with the LDPC codes used in the WiGig, Wi-Fi, and 10GE standards, and the Turbo codes used in the LTE standard. The decoder parameters are selected so that the polar codes match the error-correcting performance of the LDPC and turbo codes, and a hardware implementation complexity comparison is performed by scaling the implementation complexity of polar decoders in the literature accordingly.
P. Giard, G. Sarkis, A. Balatsoukas-Stimming, Y. Fan, C.-Y. Tsui, A. Burg, C. Thibeault, and W. J. Gross, “Hardware Decoders for Polar Codes: An Overview,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS), Montreal, Canada, May 2016.
This survey paper provides an overview of hardware implementations of successive-cancellation, successive-cancellation list, and belief-propagation decoders for polar codes. The main techniques employed in the literature for each type of decoder are discussed and implementation results for all decoders are summarized and compared.
S. Shao, P. Hailes, T.-Y. Wang, J.-Y. Wu, R. G. Maunder, B. M. Al-Hashimi, and L. Hanzo, “Survey of Turbo, LDPC and Polar Decoder ASIC Implementations,” IEEE Communications Surveys & Tutorials, early access, January 2019.
This paper is a survey that covers all the codes that were candidates for the 5G standard, including polar codes. The authors first provide a high-level discussion on the requirements of the 5G standard and the main principles behind each coding scheme. Moreover, ASIC decoders for the various coding schemes are compared in terms of several key characteristics, such as throughput, hardware-efficiency, and error-correcting performance. The authors conclude the survey with useful design recommendation as well as some future research directions.
- Special Issues
“Recent Advances in Capacity Approaching Codes,” IEEE Journal On Selected Areas In Communications, vol. 34, no. 2, February 2016.
- Standards-Related Articles
D. Hui, S. Sandberg, Y. Blankenship, M. Andersson, and L. Grosjean, “Channel Coding in 5G New radio: A Tutorial Overview and Performance Comparison with 4G LTE,” IEEE Vehicular Technology Magazine, vol. 13, no. 4, pp. 60-69, December 2018.
This tutorial article describes the specific polar and LDPC codes adopted by the 5G NR standard. The purpose of each key component in these codes and the associated operations are explained, and the performance and implementation advantages of these new codes are compared with those of 4G LTE.
V. Bioglio, C. Condo, and I. Land, “Design of Polar Codes in 5G New Radio,” arXiv:1804.04389v2, January 2019.
This tutorial provides a description of the encoding chain of polar codes, as specified in the 5G NR standard (3GPP 38.212). While the standard specification provides all details, this tutorial aims at assisting the reader’s comprehension by restructuring the presentation, highlighting the underlying polar coding principles, and relating these principles to the literature.
3rd Generation Partnership Project (3GPP), “Multiplexing and Channel Coding,” 3GPP 38.212 V.15.5.0 (2019-03).
This document is the official technical specification produced by the 3rd Generation Partnership Project (3GPP). It provides the full specification of the polar codes for the 5G NR control channels. The document may be updated and new versions may be made available by the TSG.
- Topic: Foundations
E. Arıkan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051-3073, July 2009.
This is the seminal paper in which polar codes were first introduced. The paper introduces the concept of channel polarization for memoryless channels with binary input. It proves that, if the underlying channel is symmetric, then the code rate tends to the channel capacity while the probability of error tends to zero, assuming the use of an efficient successive-cancellation decoder that the paper introduces.
E. Arıkan and E. Telatar, “On the Rate of Channel Polarization," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, South Korea, June 2009.
This paper considers the same channel polarization setting as Arıkan’s seminal paper, but it contains an improved asymptotic analysis of the probability of incorrect decoding. Specifically, it shows that the error probability is approximately 2-√N, where N is the blocklength of the polar code.
E. Arıkan, “Source Polarization,” in Proc. IEEE International Symposium on Information Theory (ISIT), Austin, USA, June 2010.
This paper shows how polar codes can be generalized to a source coding setting in order to losslessly compress a binary independent and identically distributed source with side information. Since the realization of the side information is only needed by the decoder, this scheme can be used in a Slepian-Wolf setting.
- Topic: Information-Theoretic Basics
S. B. Korada and R. Urbanke, "Polar Codes are Optimal for Lossy Source Coding," IEEE Transactions on Information Theory, vol. 56, no. 4, pp. 1751-1768, April 2010.
This paper shows how polar codes can be used for lossy source coding. The coding rate achieved is optimal, provided that the source is symmetric. By incorporating ideas from the fourth paper in this topic, the proposed scheme can also lead to an optimal compression rate for non-symmetric sources.
S. H. Hassani, K. Alishahi, and R. Urbanke, “Finite-Length Scaling of Polar Codes,” IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 5875-5898, October 2014.
This paper was the first to explore the scaling of polar codes, which is the relation between the code rate R and the blocklength N for a fixed probability of error. Specifically, the paper gives upper and lower bounds for N as a function of the code rate R, the channel capacity I(W), and two constants α and β that depend only on the fixed probability of error and on the transmission channel.
D. Goldin and D. Burshtein, “Improved Bounds on the Finite Length Scaling of Polar Codes,” IEEE Transactions on Information Theory, vol. 60, no. 11, pp. 6966-6978, November 2014.
This paper also deals with the scaling of polar codes. In particular, the authors provide an improved bound on the required blocklength N to communicate reliably at a given rate R. The improved results are also extended to the case of lossy source coding.
J. Honda and H. Yamamoto, "Polar Coding without Alphabet Extension for Asymmetric Channels," IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 7829-7838, December 2012.
This paper shows how polar codes can be used to produce an input distribution that is not symmetric. Thus, it shows a polar coding scheme that extends Arıkan’s original scheme and is capacity achieving for memoryless channels that are not symmetric.
V. Guruswami and P. Xia, “Polar Codes: Speed of Polarization and Polynomial Gap to Capacity,” IEEE Transactions on Information Theory, vol. 61, no. 1, pp. 3-16, January 2015.
This paper shows that, for binary-input memoryless symmetric channels, the blocklength N of a polar code grows polynomially in the reciprocal of the difference between the code rate and the channel capacity when imposing a particular constraint on the error probability. Moreover, the paper tracks the polarization of channels without resulting to limiting arguments on martingales.
E. Şaşoğlu and I. Tal, “Polar Coding for Processes with Memory,” IEEE Transactions on Information Theory, vol. 65, no. 4, pp. 1994-2003, April 2019.
This paper extends polar codes to a setting in which either the channel or the input distribution (or both) have memory. Slow polarization is proved for both the low-entropy and high-entropy sets, while fast polarization is proved only for the low-entropy set.
B. Shuval and I. Tal, “Fast Polarization for Processes with Memory,” IEEE Transactions on Information Theory, vol. 65, no. 4, pp. 2004-2020, April 2019.
This paper closes the gap left by the previous paper. Specifically, it shows that if we assume that the input/output process is governed by an underlying regular and hidden Markov process, then we have fast polarization of both the low-entropy and the high-entropy sets. It is also shown that the resulting coding scheme has the same asymptotic probability of error as in the memoryless case, i.e., approximately 2-√N.
- Topic: Construction and Encoding
I. Tal and A. Vardy, “How to Construct Polar Codes,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6562-6582, October 2013.
This paper introduces a method for the construction of polar codes. The bit subchannels induced by Arıkan’s polarizing transformation have an output alphabet whose size grows exponentially with the code length. Channel upgrading and degrading transformations are presented, which allow faithful approximations of a subchannel with an intractably large alphabet by another channel having a manageable alphabet size. This enables the construction of polar codes with complexity growing linearly with the blocklength.
R. Mori and T. Tanaka, “Performance of Polar Codes with the Construction Using Density Evolution,” IEEE Communications Letters, vol. 13, no. 7, pp. 519-521, July 2009.
The authors of this paper were among the first to explicitly state the problem of construction of polar codes. Density evolution was suggested to solve this problem. Furthermore, a partial order is identified on bit subchannels that can be exploited to simplify the construction process.
P. Trifonov, “Efficient Design and Decoding of Polar Codes,” IEEE Transactions on Communications, vol. 60, no. 11, pp. 3221-3227, November 2012.
This paper introduces a method for the construction of polar codes for the AWGN channel. The subchannels induced by Arıkan’s polarizing transformation are approximated with Gaussian ones, and their reliability is characterized by the mean values of the corresponding log-likelihood ratios. An improved decoding algorithm is also presented, which exploits the representation of a polar code as a generalized concatenated code.
S. N. Hong, D. Hui, and I. Marić, “Capacity-Achieving Rate-Compatible Polar Codes,” IEEE Transactions on Information Theory, vol. 63, no. 12, pp. 7620-7632, December 2017.
This work introduces a method of constructing rate-compatible polar codes that are capacity-achieving at multiple code rates, and have low-complexity decoders. The proposed codes consist of a parallel concatenation of multiple polar codes with an information-bit divider at the input of each polar encoder. It is shown that the proposed codes are capacity achieving for an arbitrary sequence of rates and for any class of degraded channels.
G. He, J.-C. Belfiore, I. Land, G. Yang, X. Liu, Y. Chen, R. Li, J. Wang, Y. Ge, R. Zhang, and W. Tong, “Beta-Expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes”, in Proc. IEEE Global Communications Conference (GLOBECOM), Singapore, December 2017.
This paper presents a polarization weight algorithm, which is a simple method for the evaluation of the reliability of polar code subchannels. The authors show that polar codes can be recursively constructed by continuously solving several polynomial equations at each recursive step. The sequences derived from the polarization weight algorithm are shown to satisfy the universal partial order for polar codes.
P. Trifonov and V. Miloslavskaya, “Polar Subcodes,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 2, pp. 254-266, February 2016.
The paper introduces a generalization of polar codes, where some input symbols of a polarizing transformation, called dynamic frozen or parity-check frozen symbols, are set to linear combinations of other symbols instead of fixed values. This enables generic linear block codes to be decoded using the techniques developed for polar codes. A method for the construction of subcodes of extended BCH codes is presented, which outperform polar codes with CRC under successive-cancellation list decoding.
H. Vangala, Y. Hong, and E. Viterbo, “Efficient Algorithms for Systematic Polar Encoding,” IEEE Communications Letters, vol. 20, no. 1, pp. 17-20, January 2016.
This paper presents three systematic encoding algorithms for polar codes. These encoders work for any arbitrary choice of frozen bit indices, and they allow a tradeoff between the number of binary computations and the number of bits of memory required by the encoder. The complexity of the best of these encoders is shown to be exactly equal to that of a non-systematic encoding algorithm.
- Topic: Improved and Low-Complexity Decoding
I. Tal and A. Vardy, “List Decoding of Polar Codes,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213-2226, May 2015.
This paper introduces a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder proposed by Arıkan. Simulations show that the proposed algorithm provides near maximum-likelihood decoding, even for moderate values of the list size. The paper also presents a construction of polar codes with a CRC, which far outperforms classical polar codes under successive-cancellation list decoding.
K. Chen, K. Niu, and J. Lin, “Improved Successive Cancellation Decoding of Polar Codes,” IEEE Transactions on Communications, vol. 61, no. 8, pp. 3100-3107, August 2013.
This paper introduces the successive-cancellation stack decoding algorithm, which enables reduced-complexity decoding of polar codes. Moreover, unified descriptions of the successive-cancellation, successive-cancellation list, and successive-cancellation stack decoding algorithms are given as path-search procedures on the code tree of polar codes.
P. Trifonov, “A Score Function for Sequential Decoding of Polar Codes,” in Proc. IEEE International Symposium on Information Theory (ISIT), Vail, USA, June 2018.
This paper introduces a score function for sequential (stack) decoding of polar codes. A significant reduction of the average decoding complexity is achieved by biasing the path metrics in the min-sum version of the stack successive-cancellation decoding algorithm with its expected value for the correct path. The proposed approach can also be used for near maximum-likelihood decoding of short extended BCH codes.
O. Afisiadis, A. Balatsoukas-Stimming, and A. Burg, “A low-Complexity Improved Successive Cancellation Decoder for Polar Codes,” in Proc. Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, November 2014.
This paper describes successive-cancellation flip decoding, where successive-cancellation decoding failures are detected using a CRC and additional successive-cancellation decoding attempts are made by flipping some bit-decisions. The error-correcting performance of successive-cancellation flip decoding is significantly improved with respect to successive-cancellation decoding with a negligible average complexity overhead, at the cost of a variable running time.
M. Rowshan and E. Viterbo, “Stepped List Decoding for Polar Codes,” in Proc. IEEE International Symposium on Turbo Codes & Iterative Information Processing, Hong Kong, December 2018.
This paper investigates the list decoding process by introducing a new parameter named path metric range. The paper proposes a stepwise adaptation of the list size based on the path metric range. This approach preserves the error-correction performance of conventional successive-cancellation list decoding, while significantly reducing the memory requirements and the computational complexity.
A. Alamdar-Yazdi and F. R. Kschischang, “A Simplified Successive-Cancellation Decoder for Polar Codes,” IEEE Communications Letters, vol. 15, no. 12, pp. 1378-1380, December 2011.
This paper describes a modification on the successive-cancellation decoder for polar codes, in which local decoders for rate-one constituent codes at any depth are simplified. This modification reduces the decoding latency and algorithmic complexity of the conventional SC decoder, while preserving the error-correcting performance.
S. Cammerer, M. Ebada, A. Elkelesh, S. ten Brink, “Sparse Graphs for Belief Propagation Decoding of Polar Codes,” in Proc. IEEE International Symposium on Information Theory (ISIT), Vail, USA, June 2018.
This paper considers belief-propagation decoding of polar codes. The authors show how to interpret a polar code as a low-density parity-check (LDPC)-like code with an underlying sparse decoding graph. As a result, iterative polar decoding can be conducted on a sparse graph using a fully parallel sum-product algorithm. The proposed iterative polar decoder has a negligible performance loss for short-to-intermediate code lengths compared to Arıkan’s original belief-propagation decoder, while having lower complexity.
- Topic: Hardware and Software Implementation
C. Leroux, A. J. Raymond, G. Sarkis, and W. J. Gross, “A Semi-Parallel Successive-Cancellation Decoder for Polar Codes,” IEEE Transactions on Signal Processing, vol. 61, no. 2, pp. 289-299, January 2013.
This paper describes a semi-parallel hardware architecture for successive-cancellation decoding that uses the available hardware resources efficiently. In particular, it is shown how re-using computational logic and memory can significantly reduce the implementation complexity. Most subsequent hardware implementations of decoders based on successive cancellation in the literature use semi-parallel architectures.
Y. Fan and C.-Y. Tsui, “An Efficient Partial-Sum Network Architecture for Semi-Parallel Polar Codes Decoder Implementation,” IEEE Transactions on Signal Processing, vol. 62, no. 12, pp., 3165-3179, June 2014.
This paper describes efficient hardware architectures for the computation of the partial sums in SC-based decoders. The authors explain how a partial sum architecture can be constructed that scales particularly well to large blocklengths, and also how the proposed architecture can be incorporated into a semi-parallel SC decoder. FPGA and ASIC results show significant improvements with respect to previous partial sum architectures.
G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Fast Polar Decoders: Algorithm and Implementation,” IEEE Journal on Selected Areas in Communications, vol. 32, no. 5, pp. 946-957, May 2014.
This paper presents an improved version of simplified successive-cancellation decoding by introducing three new corresponding node types: a single-parity-check-code node, a repetition-code node, and a special node whose left child corresponds to a repetition code and its right to a single-parity-check code. The paper also proposes an algorithm, hardware architecture, and FPGA implementation for the so-called “fast-SSC” decoder.
A. Balatsoukas-Stimming, M. Bastani Parizi, and A. Burg, “LLR-Based Successive Cancellation List Decoding of Polar Codes,” IEEE Transactions on Signal Processing, vol. 63, no. 19, pp. 5165-5179, October 2015.
This work re-formulates successive-cancellation list decoding using log-likelihood ratios (LLRs) by introducing an LLR-based path metric. LLR-based successive-cancellation list decoding is equivalent to the original successive-cancellation list decoding algorithm, but hardware implementation results show that the LLR-based formulation leads to a significant improvement in the area and operating frequency of successive-cancellation list decoders. All subsequent hardware implementations of successive-cancellation list decoding in the literature use LLR-based formulation.
A. Balatsoukas-Stimming, M. Bastani Parizi, and A. Burg, “On Metric Sorting for Successive Cancellation List Decoding of Polar Codes,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS), Lisbon, Portugal, May 2015.
This paper was the first to focus on the critical task of path metric sorting in successive-cancellation list decoding. Some properties of the LLR-based path metric are exploited in order to significantly simplify several well-known sorting architectures. ASIC synthesis results show significant improvements in area and operating frequency with respect to existing sorting architectures.
B. Yuan and K. K. Parhi, “Early Stopping Criteria for Energy-Efficient Low-Latency Belief-Propagation Polar Code Decoders,” IEEE Transactions on Signal Processing, vol. 62, no. 24, pp. 6496-6506, December 2014.
This paper describes several heuristic techniques for early stopping in belief-propagation decoding of polar codes. Each technique works best for a different SNR regime, so an adaptive SNR-dependent early stopping method is also presented. Hardware implementation results show that the early stopping techniques can significantly improve the average throughput and energy-efficiency of belief-propagation decoders.
B. Le Gal, C. Leroux, and C. Jego, “Multi-Gb/s Software Decoding of Polar Codes,” IEEE Transactions on Signal Processing, vol. 63, no. 2, pp. 349-359, January 2015.
This paper shows how the parallelism capabilities of modern CPUs can be used to implement very high-speed SC decoders in software, which are of great interest in software-defined radio applications. It is also explained how existing algorithmic simplifications for hardware SC decoders can be beneficial in software implementations. The implemented software decoders achieve throughputs of more than 1 Gb/s for a wide range of blocklengths and code rates.
- Topic: Polar Coding for General Channels
U. U. Fayyaz and J. R. Barry, “Polar Codes for Partial Response Channels,” in Proc. IEEE International Conference on Communications (ICC), Budapest, Hungary, June 2013.
The paper deals with polar codes for partial-response channels using turbo equalization at the receiver side. The original successive-cancellation decoder for polar codes does not produce soft-outputs for code bits. The authors propose a soft-input soft-output variant of the successive-cancellation decoder, called “soft cancellation (SCAN)” decoder, which is suitable for such turbo receiver architectures and keeps the computational complexity low.
E. Şaşoğlu, E. Telatar, and E. M. Yeh, “Polar Codes for the Two-User Multiple-Access Channel,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6583-6592, October 2013.
This paper extends Arıkan’s polar coding method to two-user multiple-access channels. Using Arıkan’s construction for each of the two users of the channel results in a coding scheme whose sum rate is the one that corresponds to uniform input distributions. The asymptotic encoding and decoding complexities and the error-correcting performance of these codes are shown to be the same as in the single-user case.
N. Goela, E. Abbe, and M. Gastpar, “Polar Codes for Broadcast Channels,” IEEE Transactions on Information Theory, vol. 61, no. 2, pp. 758-782, February 2015.
This paper introduces polar codes for discrete memoryless broadcast channels. For m-user deterministic broadcast channels, the polarization-based codes are shown to achieve rates on the boundary of the private-message capacity region. For two-user noisy broadcast channels, polar implementations are presented for two information-theoretic schemes, namely Cover’s superposition codes and Marton’s codes.
M. Mondelli, S. H. Hassani, I. Sason, and R. Urbanke, “Achieving Marton's Region for Broadcast Channels Using Polar Codes,” IEEE Transactions on Information Theory, vol. 61, no. 2, pp. 783-800, February 2015.
This paper presents polar coding schemes for the two-user discrete memoryless broadcast channel, which achieve Marton’s region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user discrete memoryless broadcast channels whose capacity regions are known.
M. Seidl, A. Schenk, C. Stierstorfer, and J. B. Huber, “Polar-Coded Modulation,” IEEE Transactions on Communications, vol. 61, no. 10, pp. 4108-4119, October 2013.
A framework is proposed that allows for a joint description and optimization of binary polar coding and pulse-amplitude modulation schemes. Multilevel coding and bit-interleaved coded modulation are considered, the conceptual equivalence of polar coding and multilevel coding is detailed, and rules for the optimum choice of the labelling are developed.
D. Zhou, K. Niu, and C. Dong, “Construction of Polar Codes in Rayleigh Fading Channel,” IEEE Communications Letters, vol. 23, no. 3, pp. 402-405, March 2019.
This paper addresses the construction of polar codes for the Rayleigh fading channel. Two algorithms are proposed to determine an AWGN channel that is equivalent to the actual Rayleigh fading channel. For this equivalent AWGN channel, the frozen set is determined using density evolution under a Gaussian approximation.
- Topic: Generalized Polar Codes
S. B. Korada, E. Şaşoğlu, and R. Urbanke, “Polar Codes: Characterization of Exponent, Bounds, and Constructions,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6253-6264, December 2010.
This paper shows that any ℓ × ℓ matrix with the property that none of its column permutations is upper triangular polarizes binary-input memoryless channels. Then, it characterizes the exponent of a given square matrix and provides upper and lower bounds on the achievable exponents. Using these bounds, the authors show that there are no matrices of size smaller than 15×15 with exponents exceeding 1/2. Furthermore, a general construction based on BCH codes which achieves exponents arbitrarily close to 1 for large ℓ is given. Specifically, for size 16×16, this construction yields an exponent greater than 1/2.
R. Mori and T. Tanaka, “Source and Channel Polarization Over Finite Fields and Reed–Solomon Matrices,” IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2720-2736, May 2014.
This paper generalizes Arıkan’s channel polarization for the binary field alphabet to polarization over any finite field, with the field size q being a power of a prime. A necessary and sufficient condition for a matrix over a finite field is shown under which any source and channel are polarized. Additionally, the polarization speed result for binary alphabets is generalized to arbitrary finite fields. This paper also provides an explicit construction of an ℓ×ℓ matrix, based on a Reed-Solomon matrix, with the asymptotically fastest polarization for ℓ ≤ q.
A. Fazeli, H. Hassani, M. Mondelli, and A. Vardy, “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels,” in Proc. IEEE Information Theory Workshop (ITW), Guangzhou, China, November 2018.
This paper shows that for the binary erasure channel, there exist ℓ × ℓ binary kernels with quasi-linear encoding and decoding complexity, such that polar codes constructed from these kernels achieve capacity with a scaling exponent that tends to the optimal value of 2 as ℓ grows.
V. Bioglio, I. Land, F. Gabry, and J.-C. Belfiore, “Flexible Design of Multi-Kernel Polar Codes by Reliability and Distance Properties,” in Proc. International Symposium on Turbo Codes & Iterative Information Processing (ISTC), Hong Kong, December 2018.
This paper proposes a polar code construction for multi-kernel polar codes by taking into account both reliability and distance. The new design provides a framework to optimize the code design for successive-cancellation list decoding, allowing performance to trade against decoding complexity.
N. Presman, O. Shapira, S. Litsyn, T. Etzion, and A. Vardy, “Binary Polarization Kernels from Code Decompositions,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2227–2239, May 2015.
This paper proposes designing binary kernels with a large exponent by using code decompositions. The proposed kernels are generally nonlinear, but they provide a better polarization exponent than the previously known kernels of the same dimensions. In particular, nonlinear kernels of dimensions 14, 15, and 16 are constructed and are shown to have optimal asymptotic error-correcting performance.
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.
This paper presents reduced complexity decoding algorithms for 16×16 polarization kernels with polarization rate 0.51828 and scaling exponents 3.346 and 3.450. It shows that, with these kernels, increasing the list size in the successive-cancellation list decoder provides a significant performance gain compared to the case of Arıkan’s 2×2 kernel. The proposed approach results in lower decoding complexity compared to polar decoding with Arıkan’s kernel at the same performance level.