**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Universal Polar Codes

Abstract

Polar codes, invented by Arikan in 2009, are known to achieve the capacity of any binary-input memoryless outputsymmetric channel. Further, both the encoding and the decoding can be accomplished in O(N log(N)) real operations, where N is the blocklength. One of the few drawbacks of the original polar code construction is that it is not universal. This means that the code has to be tailored to the channel if we want to transmit close to capacity. We present two "polar-like" schemes that are capable of achieving the compound capacity of the whole class of binary-input memoryless symmetric channels with low complexity. Roughly speaking, for the first scheme we stack up N polar blocks of length N on top of each other but shift them with respect to each other so that they form a "staircase." Then by coding across the columns of this staircase with a standard ReedSolomon code, we can achieve the compound capacity using a standard successive decoder to process the rows (the polar codes) and in addition a standard Reed-Solomon erasure decoder to process the columns. Compared to standard polar codes this scheme has essentially the same complexity per bit but a block length which is larger by a factor O(N log(2)(N)/epsilon). Here N is the required blocklength for a standard polar code to achieve an acceptable block error probability for a single channel at a distance of at most ! from capacity. For the second scheme we first show how to construct a true polar code which achieves the compound capacity for a finite number of channels. We achieve this by introducing special " polarization" steps which " align" the good indices for the various channels. We then show how to exploit the compactness of the space of binary-input memoryless output-symmetric channels to reduce the compound capacity problem for this class to a compound capacity problem for a finite set of channels. This scheme is similar in spirit to standard polar codes, but the price for universality is a considerably larger blocklength.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related concepts (10)

Code

In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for c

Polar code (coding theory)

In information theory, a polar code is a linear block error-correcting code. The code construction is based on a multiple recursive concatenation of a short kernel code which transforms the physical

Low-density parity-check code

In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed usi

Related publications (8)

Loading

Loading

Loading

Mohammad Karzand, Emre Telatar

Polar coding is a recent channel coding technique invented by Arikan to achieve the 'symmetric capacity' of binary-input memoryless channels. Subsequently it was observed by Korada and Urbanke that such codes are also good for lossy channel coding, achieving the 'symmetric rate distortion' bound, when the representation alphabet is binary. In this note we extend this result to the case when the representation alphabet is q-ary, for q a prime number.

Shannon, in his landmark 1948 paper, developed a framework for characterizing the fundamental limits of information transmission. Among other results, he showed that reliable communication over a channel is possible at any rate below its capacity. In 2008, Arikan discovered polar codes; the only class of explicitly constructed low-complexity codes that achieve the capacity of any binary-input memoryless symmetric-output channel. Arikan's polar transform turns independent copies of a noisy channel into a collection of synthetic almost-noiseless and almost-useless channels. Polar codes are realized by sending data bits over the almost-noiseless channels and recovering them by using a low-complexity successive-cancellation (SC) decoder, at the receiver. In the first part of this thesis, we study polar codes for communications. When the underlying channel is an erasure channel, we show that almost all correlation coefficients between the erasure events of the synthetic channels decay rapidly. Hence, the sum of the erasure probabilities of the information-carrying channels is a tight estimate of the block-error probability of polar codes when used for communication over the erasure channel. We study SC list (SCL) decoding, a method for boosting the performance of short polar codes. We prove that the method has a numerically stable formulation in log-likelihood ratios. In hardware, this formulation increases the decoding throughput by 53% and reduces the decoder's size about 33%. We present empirical results on the trade-off between the length of the CRC and the performance gains in a CRC-aided version of the list decoder. We also make numerical comparisons of the performance of long polar codes under SC decoding with that of short polar codes under SCL decoding. Shannon's framework also quantifies the secrecy of communications. Wyner, in 1975, proposed a model for communications in the presence of an eavesdropper. It was shown that, at rates below the secrecy capacity, there exist reliable communication schemes in which the amount of information leaked to the eavesdropper decays exponentially in the block-length of the code. In the second part of this thesis, we study the rate of this decay. We derive the exact exponential decay rate of the ensemble-average of the information leaked to the eavesdropper in Wyner's model when a randomly constructed code is used for secure communications. For codes sampled from the ensemble of i.i.d. random codes, we show that the previously known lower bound to the exponent is exact. Our ensemble-optimal exponent for random constant-composition codes improves the lower bound extant in the literature. Finally, we show that random linear codes have the same secrecy power as i.i.d. random codes. The key to securing messages against an eavesdropper is to exploit the randomness of her communication channel so that the statistics of her observation resembles that of a pure noise process for any sent message. We study the effect of feedback on this approximation and show that it does not reduce the minimum entropy rate required to approximate a given process. However, we give examples where variable-length schemes achieve much larger exponents in this approximation in the presence of feedback than the exponents in systems without feedback. Upper-bounding the best exponent that block codes attain, we conclude that variable-length coding is necessary for achieving the improved exponents.

Polar coding is a recently invented technique for communication over binary-input memoryless channels. This technique allows one to transmit data at rates close to the symmetric-capacity of such channels with arbitrarily high reliability, using low-complexity encoding and decoding algorithms. As such, polar coding is the only explicit low-complexity method known to achieve the capacity of symmetric binary-input memoryless channels. The principle underlying polar coding is channel polarization: recursively combining several copies of a mediocre binary-input channel to create noiseless and useless channels. The same principle can also be used to obtain optimal low-complexity compression schemes for memoryless binary sources. In this dissertation, the generality of the polarization principle is investigated. It is first shown that polarization with recursive procedures is not limited to binary channels and sources. A family of low-complexity methods that polarize all discrete memoryless processes is introduced. In both data transmission and data compression, codes based on such methods achieve optimal rates, i.e., channel capacity and source entropy, respectively. The error probability behavior of such codes is as in the binary case. Next, it is shown that a large class of recursive constructions polarize memoryless processes, establishing the original polar codes as an instance of a large class of codes based on polarization methods. A formula to compute the error probability dependence of generalized constructions on the coding length is derived. Evaluating this formula reveals that substantial error probability improvements over the original polar codes can be achieved at large coding lengths by using generalized constructions, particularly over channels and sources with non-binary alphabets. Polarizing capabilities of recursive methods are shown to extend beyond memoryless processes: Any construction that polarizes memoryless processes will also polarize a large class of processes with memory. The principles developed are applied to settings with multiple memoryless processes. It is shown that separately applying polarization constructions to two correlated processes polarizes both the processes themselves as well as the correlations between them. These observations lead to polar coding theorems for multiple-access channels and separate compression of correlated sources. The proposed coding schemes achieve optimal sum rates in both problems.