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

Polar codes for q-ary channels, q=2^r

Woomyoung Park, Alexander Barg

Published Jul 25, 2011• 0 citations
arXivHTMLPDF

Abstract

We study polarization for nonbinary channels with input alphabet of size q=2^r,r=2,3,... Using Arikan's polarizing kernel H_2, we prove that the virtual channels that arise in the process of polarization converge to q-ary channels with capacity 1,2,...,r bits, and that the total transmission rate approaches the symmetric capacity of the channel. This leads to an explicit transmission scheme for q-ary channels. The error probability of decoding using successive cancellation behaves as exp(-N^α), where N is the code length and α is any constant less than 0.5.

DOI
10.48550/arxiv.1107.4965

Related papers

Polar codes for q-ary channels, q =2r

Woomyoung Park, Alexander Barg

We study polarization for nonbinary channels with input alphabet of size q = 2r, r = 2,3,.... Using Arikan's polarizing kernel H2, we prove that virtual channels that arise in the process of polarization converge to q-ary channels with capacity 1,2,..., r bits, and that the total transmission rate approaches the symmetric capacity of the channel. This leads to an explicit transmission scheme for q-ary channels. The error probability of decoding using successive cancellation behaves as exp(-Nα), where N is the code length and α is any constant less than 0.5.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•3 citations

Polar codes for arbitrary classical-quantum channels and arbitrary cq-MACs

Rajai Nasser, Joseph M. Renes

We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation and an Arikan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple access channels (cq-MAC). The encoder can be implemented in O(N log N) operations, where N is the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2-Nβfor any β <; ½.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•3 citations

Polar Codes for Classical-Quantum Channels

Mark M. Wilde, Saikat Guha

Holevo, Schumacher, and Westmoreland's coding theorem guarantees the existence of codes that are capacity-achieving for the task of sending classical data over a channel with classical inputs and quantum outputs. Although they demonstrated the existence of such codes, their proof does not provide an explicit construction of codes for this task. The aim of this paper is to fill this gap by constructing near-explicit “polar” codes that are capacity-achieving. The codes exploit the channel polarization phenomenon observed by Arikan for the case of classical channels. Channel polarization is an effect in which one can synthesize a set of channels, by “channel combining” and “channel splitting,” in which a fraction of the synthesized channels are perfect for data transmission, while the other channels are completely useless for data transmission, with the good fraction equal to the capacity of the channel. The channel polarization effect then leads to a simple scheme for data transmission: send the information bits through the perfect channels and “frozen” bits through the useless ones. The main technical contributions of this paper are threefold. First, we leverage several known results from the quantum information literature to demonstrate that the channel polarization effect occurs for channels with classical inputs and quantum outputs. We then construct linear polar codes based on this effect, and the encoding complexity isO(NlogN), whereNis the blocklength of the code. We also demonstrate that a quantum successive cancellation decoder works well, in the sense that the word error rate decays exponentially with the blocklength of the code. For this last result, we exploit Sen's recent “noncommutative union bound” that holds for a sequence of projectors applied to a quantum state.

arXiv:1109.2591•IEEE Transactions on Information Theory•Sep 14, 2012•115 citations

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•17 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

Polar Codes: Characterization of Exponent, Bounds, and Constructions

Satish Babu Korada, Eren Şaşoğlu, Rudiger L. Urbanke

Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the $2 \times 2$ matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of $\frac12$, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding $\frac12$. We first show that any $\ell \times \ell$ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding $\frac12$. Further, we give a general construction based on BCH codes which for large $n$ achieves exponents arbitrarily close to 1 and which exceeds $\frac12$ for size 16.

arXiv:0901.0536•Jan 5, 2009•30 citations
We study polarization for nonbinary channels with input alphabet of size q=2^r,r=2,3,... Using Arikan's polarizing kernel H_2, we prove that the virtual channels that arise in the process of polarization converge to q-ary channels with capacity 1,2,...,r bits, and that the total transmission rate approaches the symmetric capacity of the channel. This leads to an explicit transmission scheme for q-ary channels. The error probability of decoding using successive cancellation behaves as exp(-N^α), where N is the code length and α is any constant less than 0.5.
We study polarization for nonbinary channels with input alphabet of size q = 2r, r = 2,3,.... Using Arikan's polarizing kernel H2, we prove that virtual channels that arise in the process of polarization converge to q-ary channels with capacity 1,2,..., r bits, and that the total transmission rate approaches the symmetric capacity of the channel. This leads to an explicit transmission scheme for q-ary channels. The error probability of decoding using successive cancellation behaves as exp(-Nα), where N is the code length and α is any constant less than 0.5.
We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation and an Arikan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple access channels (cq-MAC). The encoder can be implemented in O(N log N) operations, where N is the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2-Nβfor any β <; ½.
Holevo, Schumacher, and Westmoreland's coding theorem guarantees the existence of codes that are capacity-achieving for the task of sending classical data over a channel with classical inputs and quantum outputs. Although they demonstrated the existence of such codes, their proof does not provide an explicit construction of codes for this task. The aim of this paper is to fill this gap by constructing near-explicit “polar” codes that are capacity-achieving. The codes exploit the channel polarization phenomenon observed by Arikan for the case of classical channels. Channel polarization is an effect in which one can synthesize a set of channels, by “channel combining” and “channel splitting,” in which a fraction of the synthesized channels are perfect for data transmission, while the other channels are completely useless for data transmission, with the good fraction equal to the capacity of the channel. The channel polarization effect then leads to a simple scheme for data transmission: send the information bits through the perfect channels and “frozen” bits through the useless ones. The main technical contributions of this paper are threefold. First, we leverage several known results from the quantum information literature to demonstrate that the channel polarization effect occurs for channels with classical inputs and quantum outputs. We then construct linear polar codes based on this effect, and the encoding complexity isO(NlogN), whereNis the blocklength of the code. We also demonstrate that a quantum successive cancellation decoder works well, in the sense that the word error rate decays exponentially with the blocklength of the code. For this last result, we exploit Sen's recent “noncommutative union bound” that holds for a sequence of projectors applied to a quantum state.
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.
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.
Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the 2×22 \times 22×2 matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of 12\frac1221​, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding 12\frac1221​. We first show that any ℓ×ℓ\ell \times \ellℓ×ℓ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding 12\frac1221​. Further, we give a general construction based on BCH codes which for large nnn achieves exponents arbitrarily close to 1 and which exceeds 12\frac1221​ for size 16.