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 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.
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.
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 β <; ½.
The min-sum approximation is widely used in the decoding of polar codes. Although it is a numerical approximation, hardly any penalties are incurred in practice. We give a theoretical justification for this. We consider the common case of a binary-input, memoryless, and symmetric channel, decoded using successive cancellation and the min-sum approximation. Under mild assumptions, we show the following. For the finite length case, we show how to exactly calculate the error probabilities of all synthetic (bit) channels in time
O(N1.585), where
Nis the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denoted
RL=RL(λ)and
RU=RU(λ), where
λ(⋅)is the labeler of the channel outputs (essentially, a quantizer). For any
0<β<21and any code rate
R<RL, there exists a family of polar codes with growing lengths such that their rates are at least
Rand their error probabilities are at most
2−Nβ. That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceeding
RU, the error probability approaches 1 as the code-length increases, irrespective of which bits are frozen. We show that
0<RL≤RU≤C, where
Cis the channel capacity. The last inequality is often strict, in which case the ramification of using the min-sum approximation is that we can no longer achieve capacity.
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.
Consider a binary-input memoryless output-symmetric channel
W. Such a channel has a capacity, call it
I(W), and for any
R<I(W) and strictly positive constant
Pe we know that we can construct a coding scheme that allows transmission at rate
R with an error probability not exceeding
Pe. Assume now that we let the rate
R tend to
I(W) and we ask how we have to "scale" the blocklength
N in order to keep the error probability fixed to
Pe. We refer to this as the "finite-length scaling" behavior. This question was addressed by Strassen as well as Polyanskiy, Poor and Verdu, and the result is that
N must grow at least as the square of the reciprocal of
I(W)−R. Polar codes are optimal in the sense that they achieve capacity. In this paper, we are asking to what degree they are also optimal in terms of their finite-length behavior. Our approach is based on analyzing the dynamics of the un-polarized channels. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of sub-channels chosen (by the polar coding scheme) to transmit information. If we require this sum to be smaller than a given value
Pe>0, then the required block-length
N scales in terms of the rate
R<I(W) as
N≥(I(W)−R)μα, where
α is a positive constant that depends on
Pe and
I(W), and
μ=3.579. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate like
N≤(I(W)−R)μβ, where
β is a constant that depends on
Pe and
I(W), and
μ=6.