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
Pewe know that we can construct a coding scheme that allows transmission at rate
Rwith an error probability not exceeding
Pe. Assume now that we let the rate
Rtend to
I(W)and we ask how we have to scale the blocklength
Nin 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
Nmust 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. Since the exact scaling behavior depends on the choice of the channel, our objective is to provide scaling laws that hold universally for all binary-input memoryless output-symmetric channels. Our approach is based on analyzing the dynamics of the un-polarized channels. More precisely, we provide bounds on (the exponent of) the number of subchannels whose Bhattacharyya constant falls in a fixed interval
[a,b]. Mathematically, this can be stated as bounding the sequence
{1/nlogPr(Zn∈[a,b])}n∈N, where
Znis the Bhattacharyya process. We then use these bounds to derive tradeoffs between the rate and the block-length. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of subchannels 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
Nscales in terms of the rate
R<I(W)as
N≥α/(I(W)−R)μ, where
αis a positive constant that depends on
Peand
I(W). We show that
μ=3.579is a valid choice, and we conjecture that indeed the value of
μcan be improved to
μ=3.627, the parameter for the binary erasure channel. 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
Peand
I(W), and
μ=6.
Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.
We consider the problem of determining the trade-off between the rate and the block-length of polar codes for a given block error probability when we use the successive cancellation decoder. We take the sum of the Bhattacharyya parameters as a proxy for the block error probability, and show that there exists a universal parameter
μ such that for any binary memoryless symmetric channel
W with capacity
I(W), reliable communication requires rates that satisfy
R<I(W)−αN−μ1, where
α is a positive constant and
N is the block-length. We provide lower bounds on
μ, namely
μ≥3.553, and we conjecture that indeed
μ=3.627, the parameter for the binary erasure 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.
A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.