This chapter delves into the key properties of polar codes, offering insights into their mathematical foundations and practical implications. It examines the polar transform and its connection to linear algebra, highlighting the role of permutation matrices and the construction of generator and parity-check matrices, which are essential for encoding and decoding processes. The chapter also explores the concept of systematic polar codes. It addresses the error correction performance of polar codes through an analysis of their minimum distance and the construction and enumeration of minimum weight codewords. It further extends the discussion to polar codes with large kernels and mixed/multi-kernel constructions, which aim to enhance polarization and improve performance. The chapter introduces the exponent of the polarizing matrix as a measure of the efficiency of these alternative kernels in polarizing sub-channels. It explores the practical aspects of decoding in depth, with a particular focus on the properties of SC decoding.
The construction of polar codes is critical in determining their error correction performance, computational complexity, and suitability for diverse applications. This chapter explores various methods for constructing polar codes, focusing on their trade-offs in terms of computational complexity, accuracy, and error correction performance. It explores both channel-dependent approaches, such as density evolution and Gaussian approximation, and channel-independent methods, including partial orders and polarization weights. The chapter discusses the construction of concatenated codes, such as cyclic redundancy check-polar codes and polarization-adjusted convolutional codes, which have demonstrated enhanced performance in practical scenarios. It focuses on practical and low-complexity construction techniques suitable for real-world applications. By understanding the differences between the presented techniques, the readers will be equipped to select and implement the most suitable construction method for their specific decoders and application needs.
Multi-kernel polar codes are constructed from the Kronecker product. For ordinary multi-kernels, constituent polarizing matrices of the same stage are identical. However, in a stage, applying different constituent matrices based on channel property can further improve performance. This family of polar codes is defined as hybrid multi-kernel polar codes. Exponents of hybrid multi-kernels are analyzed. The matrix of a hybrid multi-kernel is generated by a Kronecker-like product operation, and so are partial distances. All exponents of hybrid multi-kernels take values between the maximum and the minimum exponents among all constituent matrices. Exponents are related to the error probability of the original channel and exhibit a trend of convergence as block-length increases. The convergence rate is also related to the original error probability.
Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.
In the field of channel coding theory, there are two main branches. The first is related to the design and construction of codes capable of facilitating identification of errors at the receiver despite potential alterations during transmission; this is known as the encoding operation. The second branch focuses on developing mechanisms for correcting errors caused by the transmission channel, by devising valid and suitable algorithms; this is known as the decoding operation. The authors have delved into both aspects. In the first part, a novel method for constructing good linear codes is studied. It is based on the Hadamard matrix, which shares the same structure as the kernel of polar codes, and on the generator matrix of several existing linear codes. In the second part, a new decoding algorithm is proposed. This involves adapting the SSCL polar code decoder to decode the codes designed in the first part, as well as some of the most well-known block codes.
Pre-transformed polar codes constitute a broad class of codes constructed through the serial concatenation of outer codes and polar codes, enhancing the performance of standalone polar codes either by improving the weight distribution or by increasing the error-decay rate. Deep polar codes, a novel variant within this class, are constructed through a pre-transformation that involves a series of nested polar codes with increasing dimensions across layers. The proposed successive cancellation list with backpropagation parity check (SCL-BPC) decoder exploits the parity equations naturally arising from this nested encoding structure. In certain scenarios, deep polar codes with SCL-BPC decoding demonstrate superior performance compared to other pre-transformed polar codes. However, the SCL-BPC algorithm incurs additional decoding complexity and results in uneven decoding times. To address these issues, we investigate the matrix representation of the pre-transformation in deep polar codes and develop efficient implementation solutions for SCL-BPC decoding. Additionally, we introduce a low-complexity approach to SCL-BPC, which exhibits only a marginal reduction in performance.
Multi-kernel polar codes, which are constructed by different sizes of kernels make the traditional polar codes have more flexible code length. In this paper, we extend the multi-kernel polar codes to
5×5 kernels including kernel design, code design, and fast decoding. First, we construct a new
5×5 kernel, which has the maximum polarization rate. The first row of this kernel is all-one vector, which enable us to seek the relation between node modification and distance property of multi-kernel polar codes. Second, we modify the repetition (REP) nodes to this kernel, which can increase the distance property of the constructed polar codes, improve the decoding performance and reduce memory requirements during the fast decoding. In addition, we find this REP node modification can be generalized when multi-kernel polar codes constructed by kernels, which the first row is all-one vector. Third, we prove the four kinds of basic nodes (Rate-1 node, Rate-0 nodes, Repetition (REP) nodes, and Single-Parity check (SPC) nodes) of fast decoding are suitable for this kernel. Moreover, we generalize the Generalized Parity-Check (G-PC) nodes and the Generalized Repetition (GREP) nodes, which are suitable for multi-kernel polar codes constructed by any size of kernels and any order of kernels. The G-PC and G-REP nodes can further accelerate the decoding speed. By simulations, we show that our modification improves the error-rate performance of the fast decoding. Meanwhile, the fast decoding of our multi-kernel polar codes has at least 68. 4% reduced latency compared with the traditional SC decoder in all cases considered where frame lengths are (
80,135,400,675). Index Terms-Multi-kernel polar codes, node modification, fast decoding,
5×5 kernel matrix