Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1209.4444 · Wiley eBooks

Construction of Polar Codes

Mohammad Rowshan, Emanuele Viterbo

Published Oct 27, 2025• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1002/9781119911760.ch6

Related papers

Properties of Polar Codes

Mohammad Rowshan, Emanuele Viterbo

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.

Wiley eBooks•Oct 27, 2025•0 citations

Convolutional Decoding of Polar Codes

Arman Fazeli, Alexander Vardy, Hanwen Yao

Polar coding has found its way into many realms in communications and information theory. In most implementation setups, they are accompanied with the list successive cancellation (LSC) decoding algorithm which is shown to provide a superior error performance compared to the original successive cancellation (SC) decoding method. While the SC decoding is fairly well-studied, the exact math behind LSC's superior performance still remains to be of mystery. Multiple techniques have been proposed to further improve the LSC's error performance or to reduce its computational complexity, which are usually motivated by heuristic reasons and shown through numerical simulations. Most notable example is the CRC-aided LSC, which drastically improves the LSC's performance by concatenating the polar code with some high-rate cyclic redundancy check (CRC) codes.In this paper, we present polar codes that are concatenated with an underlying high-rate convolutional code, which are shown to have superior performances over CRC-aided LSC. We also present a computationally-efficient decoding algorithm for these codes which resembles the techniques used in the Viterbi algorithm, and hence is called the convolutional decoding algorithm. To do this, we revisit the error analysis of the original SC decoding along with the concept of Arıkan's helper genie. We address some shortcomings of the CRC-aided LSC and discuss how to turn around them by emulating a convolutional code instead of a CRC code. Contrary to CRC codes, most of the convolutional codes are not a proper choice for concatenation with polar codes. We introduce the bucketing algorithm to construct suitable punctured convolutional codes for this purpose. The proposed framework can accommodate any such underlying convolutional code, which allows one to search for the optimal convolutional code based on their design parameters.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•8 citations

Performance Analysis of a CRC-aided BP Decoder in an AWGN Channel

Hamizan Suhaimi, Roslina Mohamad, Ezmin Abdullah +1 more

Polar codes have emerged as a powerful error correction technique for reliable data transmission in various communication systems. The addition of cyclic redundancy check (CRC) can significantly enhance the reliability of polar codes by providing an additional layer of error detection and correction. Without CRC, a system will lack a mechanism that detects and corrects decoding errors. By appending CRC bits to the polar-encoded data, the receiver with a belief propagation (BP) decoder can perform CRC to verify the correctness of the received information, enabling error detection beyond the capabilities of polar codes alone. This paper mainly focuses on incorporating CRC codes into polar codes and evaluating performance after the codes were transmitted into an additive white Gaussian channel. The CRC-aided BP decoder was simulated using MATLAB. The block length, N, was set to 256 and 1024 bits, and CRC varied between 12 and 16 bits for each N. The decoder system was tested with different numbers of iterations (50, 100, 200, and 500) to verify the performance in terms of bit error rate and frame error rate. Overall, this research provides a comprehensive analysis of the utilization of CRC for polar codes, considering different CRC sizes, numbers of iterations for BP decoding, and various block lengths. The average number of iterations of 200 and increasing CRC shows the lowest error rate readings throughout an increase in noise. The use of 12 and 16 bits of CRC further enhances the decoder’s error detection and correction capability.

IEEE Symposium on Computers & Informatics (ISCI)•Oct 14, 2023•1 citation

On the comparison of different serial concatenated schemes based on polar and LDPC codes

Fedor I. Ivanov, Aleksey Kuvshinov

Nowadays concatenated codes are actively developed for different applications of error-correcting theory. In this paper we propose a new method for constructing concatenated codes consisting of some outer error-correcting code and a particular designed inner low-density parity-check (LDPC) code. We consider polarization-adjusted convolutional (PAC) code and LDPC code as outer code of suggested construction. A specialized optimization algorithm was developed to generate inner code with particular error-reducing properties. By using the woven codes decoder with this design, the complexity of the decoding procedure is reduced compared to traditional polar and LDPC codes decoders, while still providing error-correcting characteristics. Additionally, we enhance the performance of our system by puncturing the encoded symbols. The resulting concatenated constructions outperform low-rate LDPC code from the 5G standard and polar code. Furthermore, we demonstrate the performance of code with a special paritycheck matrix which consists of parity-check matrices of inner and outer codes from our proposed construction.

Facta universitatis - series Electronics and Energetics•Jan 1, 2024•1 citation

Low-Density Parity-Check Codes: Construction and Implementation

Gabofetswe Malema

Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. \nThis thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. \nRow-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. \nQuasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. \nDecoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing \nthe starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. \nTechniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques.

•Jan 1, 2007•24 citations

Practical Decoding for Deep Polar Codes

Donghwa Han, Min Jang, Donghun Lee +2 more

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.

IEEE Globecom Workshops (GC Wkshps)•Dec 8, 2024•1 citation
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.
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.
Polar coding has found its way into many realms in communications and information theory. In most implementation setups, they are accompanied with the list successive cancellation (LSC) decoding algorithm which is shown to provide a superior error performance compared to the original successive cancellation (SC) decoding method. While the SC decoding is fairly well-studied, the exact math behind LSC's superior performance still remains to be of mystery. Multiple techniques have been proposed to further improve the LSC's error performance or to reduce its computational complexity, which are usually motivated by heuristic reasons and shown through numerical simulations. Most notable example is the CRC-aided LSC, which drastically improves the LSC's performance by concatenating the polar code with some high-rate cyclic redundancy check (CRC) codes.In this paper, we present polar codes that are concatenated with an underlying high-rate convolutional code, which are shown to have superior performances over CRC-aided LSC. We also present a computationally-efficient decoding algorithm for these codes which resembles the techniques used in the Viterbi algorithm, and hence is called the convolutional decoding algorithm. To do this, we revisit the error analysis of the original SC decoding along with the concept of Arıkan's helper genie. We address some shortcomings of the CRC-aided LSC and discuss how to turn around them by emulating a convolutional code instead of a CRC code. Contrary to CRC codes, most of the convolutional codes are not a proper choice for concatenation with polar codes. We introduce the bucketing algorithm to construct suitable punctured convolutional codes for this purpose. The proposed framework can accommodate any such underlying convolutional code, which allows one to search for the optimal convolutional code based on their design parameters.
Polar codes have emerged as a powerful error correction technique for reliable data transmission in various communication systems. The addition of cyclic redundancy check (CRC) can significantly enhance the reliability of polar codes by providing an additional layer of error detection and correction. Without CRC, a system will lack a mechanism that detects and corrects decoding errors. By appending CRC bits to the polar-encoded data, the receiver with a belief propagation (BP) decoder can perform CRC to verify the correctness of the received information, enabling error detection beyond the capabilities of polar codes alone. This paper mainly focuses on incorporating CRC codes into polar codes and evaluating performance after the codes were transmitted into an additive white Gaussian channel. The CRC-aided BP decoder was simulated using MATLAB. The block length, N, was set to 256 and 1024 bits, and CRC varied between 12 and 16 bits for each N. The decoder system was tested with different numbers of iterations (50, 100, 200, and 500) to verify the performance in terms of bit error rate and frame error rate. Overall, this research provides a comprehensive analysis of the utilization of CRC for polar codes, considering different CRC sizes, numbers of iterations for BP decoding, and various block lengths. The average number of iterations of 200 and increasing CRC shows the lowest error rate readings throughout an increase in noise. The use of 12 and 16 bits of CRC further enhances the decoder’s error detection and correction capability.
Nowadays concatenated codes are actively developed for different applications of error-correcting theory. In this paper we propose a new method for constructing concatenated codes consisting of some outer error-correcting code and a particular designed inner low-density parity-check (LDPC) code. We consider polarization-adjusted convolutional (PAC) code and LDPC code as outer code of suggested construction. A specialized optimization algorithm was developed to generate inner code with particular error-reducing properties. By using the woven codes decoder with this design, the complexity of the decoding procedure is reduced compared to traditional polar and LDPC codes decoders, while still providing error-correcting characteristics. Additionally, we enhance the performance of our system by puncturing the encoded symbols. The resulting concatenated constructions outperform low-rate LDPC code from the 5G standard and polar code. Furthermore, we demonstrate the performance of code with a special paritycheck matrix which consists of parity-check matrices of inner and outer codes from our proposed construction.
Low-density parity-check (LDPC) codes have been shown to have good error correcting performance approaching Shannon’s limit. Good error correcting performance enables efficient and reliable communication. However, a LDPC code decoding algorithm needs to be executed efficiently to meet cost, time, power and bandwidth requirements of target applications. The constructed codes should also meet error rate performance requirements of those applications. Since their rediscovery, there has been much research work on LDPC code construction and implementation. LDPC codes can be designed over a wide space with parameters such as girth, rate and length. There is no unique method of constructing LDPC codes. Existing construction methods are limited in some way in producing good error correcting performing and easily implementable codes for a given rate and length. There is a need to develop methods of constructing codes over a wide range of rates and lengths with good performance and ease of hardware implementability. LDPC code hardware design and implementation depend on the structure of target LDPC code and is also as varied as LDPC matrix designs and constructions. There are several factors to be considered including decoding algorithm computations,processing nodes interconnection network, number of processing nodes, amount of memory, number of quantization bits and decoding delay. All of these issues can be handled in several different ways. \nThis thesis is about construction of LDPC codes and their hardware implementation. LDPC code construction and implementation issues mentioned above are too many to be addressed in one thesis. The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. We introduce two main methods for constructing structured codes. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. Cycles of length four are avoided by observing the row-column constraint. \nRow-column connections observing this condition are searched sequentially or randomly. Although the girth conditions are not sufficient beyond six, larger girths codes were easily obtained especially at low rates. The advantage of this algorithm compared to other methods is its flexibility. It could be used to construct codes for a given rate and length with girths of at least six for any sub-matrix configuration or rearrangement. The code size is also easily varied by increasing or decreasing sub-matrix size. Codes obtained using a sequential search criteria show poor performance at low girths (6 and 8) while random searches result in good performing codes. \nQuasi-cyclic codes could be implemented in a variety of decoder architectures. One of the many options is the choice of processing nodes interconnect. We show how quasi-cyclic codes processing could be scheduled through a multistage network. Although these net-works have more delay than other modes of communication, they offer more flexibility at a reasonable cost. Banyan and Benes networks are suggested as the most suitable networks. \nDecoding delay is also one of several issues considered in decoder design and implementation. In this thesis, we overlap check and variable node computations to reduce decoding time. Three techniques are discussed, two of which are introduced in this thesis. The techniques are code matrix permutation, matrix space restriction and sub-matrix row-column scheduling. Matrix permutation rearranges the parity-check matrix such that rows and columns that do not have connections in common are separated. This techniques can be applied to any matrix. Its effectiveness largely depends on the structure of the code. We show that its success also depends on the size of row and column weights. Matrix space restriction is another technique that can be applied to any code and has fixed reduction in time or amount of overlap. Its success depends on the amount of restriction and may be traded with performance loss. The third technique already suggested in literature relies on the internal cyclic structure of sub-matrices to achieve overlapping. The technique is limited to LDPC code matrices in which the number of sub-matrices is equal to row and column weights. We show that it can be applied to other codes with a lager number of sub-matrices than code weights. However, in this case maximum overlap is not guaranteed. We calculate the lower bound on the amount of overlapping. Overlapping could be applied to any sub-matrix configuration of quasi-cyclic codes by arbitrarily choosing \nthe starting rows for processing. Overlapping decoding time depends on inter-iteration waiting times. We show that there are upper bounds on waiting times which depend on the code weights. Waiting times could be further reduced by restricting shifts in identity sub-matrices or using smaller sub-matrices. This overlapping technique can reduce the decoding time by up to 50% compared to conventional message and computation scheduling. \nTechniques of matrix permutation and space restriction results in decoder architectures that are flexible in LDPC code design in terms of code weights and size. This is due to the fact that with these techniques, rows and columns are processed in sequential order to achieve overlapping. However, in the existing technique, all sub-matrices have to be processed in parallel to achieve overlapping. Parallel processing of all code sub-matrices requires the architecture to have the number of processing units at least equal to the number sub-matrices. Processing units and memory space should therefore be distributed among the sub-matrices according to the sub-matrices arrangement. This leads to high complexity or inflexibility in the decoder architecture. We propose a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques.
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.