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:1704.00715

Convolutional Polar Codes

Andrew J. Ferris, Christoph Hirche, David Poulin

Published Apr 3, 2017• 17 citations
arXivHTMLPDF

Abstract

Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite block-length performance, while keeping the bloc-structured kernel. Recently, two of us introduced a new family of efficiently decodable error-correction codes based on a recently discovered efficiently-contractible tensor network family in quantum many-body physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a non-trivial way by substituting the bloc-structured kernel by a convolutional structure. Here, we perform an in-depth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite block-size numerical simulations which display improved error-correcting capability with only a minor impact on decoding complexity.

DOI
10.48550/arxiv.1704.00715

Related papers

Branching MERA codes: a natural extension of polar codes

Andrew J. Ferris, David Poulin

We introduce a new class of circuits for constructing efficiently decodable error-correction codes, based on a recently discovered contractible tensor network. We perform an in-depth study of a particular example that can be thought of as an extension to Arikan's polar code. Notably, our numerical simulation show that this code polarizes the logical channels more strongly while retaining the log-linear decoding complexity using the successive cancellation decoder. These codes also display improved error-correcting capability with only a minor impact on decoding complexity. Efficient decoding is realized using powerful graphical calculus tools developed in the field of quantum many-body physics. In a companion paper, we generalize our construction to the quantum setting and describe more in-depth the relation between classical and quantum error correction and the graphical calculus of tensor networks.

arXiv:1312.4575•Dec 16, 2013•9 citations

Branching MERA codes: A natural extension of classical and quantum polar codes

Andrew J. Ferris, David Poulin

We introduce a new class of circuits for constructing efficiently decodable quantum and classical error-correction codes, based on a recently discovered contractible tensor network known as branching multi-scale entanglement renormalization ansatz [1]. We perform an in-depth study of a particular example that can be thought of as an extension to Arikan's polar code [2]-[4]. Notably, our numerical simulation show that these codes polarize the logical channels more strongly while retaining the log-linear decoding complexity using the successive cancellation decoder. These codes also display improved error-correcting capability with only a minor impact on decoding complexity. Efficient decoding is realized using powerful graphical calculus tools developed in the field of quantum many-body physics.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•15 citations

Convolutional Polar Codes on Channels with Memory using Tensor Networks

Benjamin Bourassa, Tremblay, Maxime, David Poulin

Arikan's recursive code construction is designed to polarize a collection of memoryless channels into a set of good and a set of bad channels, and it can be efficiently decoded using successive cancellation. It was recently shown that the same construction also polarizes channels with memory, and a generalization of successive cancellation decoder was proposed with a complexity that scales like the third power of the channel's memory size. In another line of work, the polar code construction was extended by replacing the block polarization kernel by a convoluted kernel. Here, we present an efficient decoding algorithm for finite-state memory channels that can be applied to polar codes and convolutional polar codes. This generalization is most effectively described using the tensor network formalism, and the manuscript presents a self-contained description of the required basic concepts. We use numerical simulations to study the performance of these algorithms for practically relevant code sizes and find that the convolutional structure outperforms the standard polar codes on a variety of channels with memory.

arXiv:1805.09378•May 23, 2018•0 citations

From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family ${\mathcal C}_{\rm inter} = \{C_α : α\in [0, 1]\}$, where $C_α \big |_{α= 1}$ is the original polar code, and $C_α \big |_{α= 0}$ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of $α$. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family ${\mathcal C}_{\rm inter}$ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

arXiv:1401.3127•Jan 14, 2014•0 citations

Polar Codes: Finite Length Implementation, Error Correlations and Multilevel Modulation

Mani Bastani Parizi

Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.

•Jan 1, 2012•4 citations

From polar to Reed-Muller codes: A technique to improve the finite-length performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1]}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cintereven under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•14 citations
Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite block-length performance, while keeping the bloc-structured kernel. Recently, two of us introduced a new family of efficiently decodable error-correction codes based on a recently discovered efficiently-contractible tensor network family in quantum many-body physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a non-trivial way by substituting the bloc-structured kernel by a convolutional structure. Here, we perform an in-depth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite block-size numerical simulations which display improved error-correcting capability with only a minor impact on decoding complexity.
We introduce a new class of circuits for constructing efficiently decodable error-correction codes, based on a recently discovered contractible tensor network. We perform an in-depth study of a particular example that can be thought of as an extension to Arikan's polar code. Notably, our numerical simulation show that this code polarizes the logical channels more strongly while retaining the log-linear decoding complexity using the successive cancellation decoder. These codes also display improved error-correcting capability with only a minor impact on decoding complexity. Efficient decoding is realized using powerful graphical calculus tools developed in the field of quantum many-body physics. In a companion paper, we generalize our construction to the quantum setting and describe more in-depth the relation between classical and quantum error correction and the graphical calculus of tensor networks.
We introduce a new class of circuits for constructing efficiently decodable quantum and classical error-correction codes, based on a recently discovered contractible tensor network known as branching multi-scale entanglement renormalization ansatz [1]. We perform an in-depth study of a particular example that can be thought of as an extension to Arikan's polar code [2]-[4]. Notably, our numerical simulation show that these codes polarize the logical channels more strongly while retaining the log-linear decoding complexity using the successive cancellation decoder. These codes also display improved error-correcting capability with only a minor impact on decoding complexity. Efficient decoding is realized using powerful graphical calculus tools developed in the field of quantum many-body physics.
Arikan's recursive code construction is designed to polarize a collection of memoryless channels into a set of good and a set of bad channels, and it can be efficiently decoded using successive cancellation. It was recently shown that the same construction also polarizes channels with memory, and a generalization of successive cancellation decoder was proposed with a complexity that scales like the third power of the channel's memory size. In another line of work, the polar code construction was extended by replacing the block polarization kernel by a convoluted kernel. Here, we present an efficient decoding algorithm for finite-state memory channels that can be applied to polar codes and convolutional polar codes. This generalization is most effectively described using the tensor network formalism, and the manuscript presents a self-contained description of the required basic concepts. We use numerical simulations to study the performance of these algorithms for practically relevant code sizes and find that the convolutional structure outperforms the standard polar codes on a variety of channels with memory.
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family Cinter={Cα:α∈[0,1]}{\mathcal C}_{\rm inter} = \{C_α : α\in [0, 1]\}Cinter​={Cα​:α∈[0,1]}, where Cα∣α=1C_α \big |_{α= 1}Cα​​α=1​ is the original polar code, and Cα∣α=0C_α \big |_{α= 0}Cα​​α=0​ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of ααα. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter{\mathcal C}_{\rm inter}Cinter​ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1]}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cintereven under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.