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

Convolutional Polar Codes on Channels with Memory using Tensor Networks

Benjamin Bourassa, Tremblay, Maxime, David Poulin

Published May 23, 2018• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1805.09378

Related papers

Convolutional Polar Codes

Andrew J. Ferris, Christoph Hirche, David Poulin

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.

arXiv:1704.00715•Apr 3, 2017•23 citations

Convolutional Polar Codes: LLR-based Successive Cancellation Decoder and List Decoding Performance

Hamid Saber, Yiqun Ge, Ran Zhang +2 more

Recently convolutional polar (cpolar) codes have been proposed. A tensor-network-based successive cancellation (SC) decoding was proposed for them under which cpolar codes were shown to outperform polar codes. In this paper we present the notion of m-bit-channels for cpolar codes and give the recursive construction of m-bit-channels for m=3. Then a log likelihood ratio(LLR)-based SC decoding of complexity order O(Nlog(N)) for cpolar codes is presented. We also present the numerical results for performance evaluation of cpolar codes under SC list (SCL) decoding. Our simulation results show that cpolar codes can achieve the performance of polar codes with a list size reduced by a factor of 4.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•12 citations

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•18 citations

Polar List Decoding for Large Polarization Kernels

Bhaskar Gupta, Hanwen Yao, Arman Fazeli +1 more

Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2021•7 citations

On Distance Properties of Convolutional Polar Codes

Ruslan Morozov, Peter Trifonov

A lower bound on the minimum distance of convolutional polar codes is provided. The bound is obtained from the minimum weight of the generalized cosets of the codes generated by the bottom rows of the polarizing matrix. Moreover, a construction of convolutional polar subcodes is proposed, which provides improved performance under successive cancellation list decoding. For sufficiently large list size, the decoding complexity of convolutional polar subcodes appears to be lower compared with Arikan polar subcodes with the same performance. The error probability of successive cancellation list decoding of convolutional polar subcodes is lower than that of Arikan polar subcodes with the same list size.

arXiv:1901.06341•IEEE Transactions on Communications•Apr 4, 2019•9 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
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.
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.
Recently convolutional polar (cpolar) codes have been proposed. A tensor-network-based successive cancellation (SC) decoding was proposed for them under which cpolar codes were shown to outperform polar codes. In this paper we present the notion of m-bit-channels for cpolar codes and give the recursive construction of m-bit-channels for m=3. Then a log likelihood ratio(LLR)-based SC decoding of complexity order O(Nlog(N)) for cpolar codes is presented. We also present the numerical results for performance evaluation of cpolar codes under SC list (SCL) decoding. Our simulation results show that cpolar codes can achieve the performance of polar codes with a list size reduced by a factor of 4.
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.
Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.
A lower bound on the minimum distance of convolutional polar codes is provided. The bound is obtained from the minimum weight of the generalized cosets of the codes generated by the bottom rows of the polarizing matrix. Moreover, a construction of convolutional polar subcodes is proposed, which provides improved performance under successive cancellation list decoding. For sufficiently large list size, the decoding complexity of convolutional polar subcodes appears to be lower compared with Arikan polar subcodes with the same performance. The error probability of successive cancellation list decoding of convolutional polar subcodes is lower than that of Arikan polar subcodes with the same list size.
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.