Polar codes were recently introduced by Arikan. They achieve the symmetric capacity of arbitrary binary-input discrete memoryless channels under a low complexity successive cancellation decoding ...scheme. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the 2 × 2 matrix 1 0 : 1 1. It was shown by Arikan Telatar that this construction achieves an error exponent of 1/2, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the blocklength. It was already mentioned by Arikan that in principle larger matrices can be used to construct polar codes. In this paper, it is first shown that any ℓ × ℓ matrix none of whose column permutations is upper triangular polarizes binary-input memoryless channels. The exponent of a given square matrix is characterized, upper and lower bounds on achievable exponents are given. Using these bounds it is shown that there are no matrices of size smaller than 15×15 with exponents exceeding 1/2. Further, a general construction based on BCH codes which for large I achieves exponents arbitrarily close to 1 is given. At size 16 × 16, this construction yields an exponent greater than 1/2.
We study polar coding for stochastic processes with memory. For example, a process may be defined by the joint distribution of the input and output of a channel. The memory may be present in the ...channel, the input, or both. We show that the <inline-formula> <tex-math notation="LaTeX">{\psi } </tex-math></inline-formula>-mixing processes polarize under the standard Arıkan transform, under a mild condition. We further show that the rate of polarization of the low-entropy synthetic channels is roughly <inline-formula> <tex-math notation="LaTeX">{O}({2}^{-\sqrt {N}}) </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">{N} </tex-math></inline-formula> is the blocklength. That is, essentially, the same rate as in the memoryless case.
We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise ...structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing block length and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone Boolean functions and the area theorem for extrinsic information transfer functions.
Universal Polarization Sasoglu, Eren; Wang, Lele
IEEE transactions on information theory,
2016-June, 2016-6-00, 20160601, Volume:
62, Issue:
6
Journal Article
Peer reviewed
Open access
A method to polarize channels universally is introduced. The method is based on combining channels of unequal capacities in each polarization step, as opposed to the standard method of combining ...identical channels. The locations of the good and bad channels that emerge upon polarization are only a function of the polar transform chosen, and are otherwise independent of the channel being polarized. This yields a simple method to design universal polar codes for discrete memoryless channels. It is also shown that the less noisy ordering of channels is preserved under polarization, and thus, a good polar code for a given channel will perform well over a less noisy one.
Arikan's polar coding method is extended to two-user multiple-access channels. It is shown that if the two users of the channel use Arikan's construction, the resulting channels will polarize to one ...of five possible extremals, on each of which uncoded transmission is optimal. The sum rate achieved by this coding technique is the one that corresponds to uniform input distributions. The encoding and decoding complexities and the error performance of these codes are as in the single-user case: O(nlogn) for encoding and decoding, and o(2 -n1/2-ε ) for the block error probability, where n is the blocklength.
A low-complexity coding scheme is developed to achieve the rate region of maximum likelihood decoding for interference channels. As in the classical rate-splitting multiple access scheme by Grant, ...Urbanke, and Whiting, the proposed coding scheme uses superposition of multiple codewords with successive cancellation decoding, which can be implemented using standard point-to-point encoders and decoders. Unlike rate-splitting multiple access, which is not rate-optimal for multiple receivers, the proposed coding scheme transmits codewords over multiple blocks in a staggered manner and recovers them successively over sliding decoding windows, achieving the single-stream optimal rate region as well as the more general Han-Kobayashi inner bound for the two-user interference channel. The feasibility of this scheme in practice is verified by implementing it using commercial channel codes over the two-user Gaussian interference channel.
The problem of achieving the secrecy capacity of wiretap channels explicitly and with low complexity has been open since the work of Wyner in 1975. Recently, Mahdavifar and Vardy presented a solution ...to this problem, based on polar codes, for the class of symmetric and degraded wiretap channels. Their polar coding scheme achieves both security and reliability under the weak security criterion, but does not guarantee reliability under the strong security criterion. The main difficulty in providing both strong security and reliability using polar codes is the existence of a small number of bit-channels that are both unreliable and unsecure. In this paper, a multi-block polar coding scheme that resolves this difficulty is presented. It is shown that this coding scheme achieves the secrecy capacity of symmetric degraded wiretap channels while guaranteeing both reliability and strong security.
It is shown that given two copies of a q-ary input channel W, where q is prime, it is possible to create two channels W - and W + whose symmetric capacities satisfy I(W - ) ≤ I(W) ≤ I(W + ), where ...the inequalities are strict except in trivial cases. This leads to a simple proof of channel polarization in the q-ary case.
PDF
