**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.

Concept# Polar code (coding theory)

Summary

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 channel into virtual outer channels. When the number of recursions becomes large, the virtual channels tend to either have high reliability or low reliability (in other words, they polarize or become sparse), and the data bits are allocated to the most reliable channels. It is the first code with an explicit construction to provably achieve the channel capacity for symmetric binary-input, discrete, memoryless channels (B-DMC) with polynomial dependence on the gap to capacity. Notably, polar codes have modest encoding and decoding complexity O(n log n), which renders them attractive for many applications. Moreover, the encoding and decoding energy complexity of generalized polar codes can reach the fundamental lower bounds for energy consumption of two dimensional circuitry to within an O(n

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 publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related concepts

No results

Related courses (3)

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how they work and sketch how they can be implemented.

COM-622: Topics in information-theoretic cryptography

Information-theoretic methods and their application to secrecy & privacy. Perfect information-theoretic secrecy. Randomness extraction & privacy amplification. Secret key generation from common randomness. Measures of information leakage incl. differential privacy, perfect privacy, & mutual info.

COM-404: Information theory and coding

The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so.

Related people (13)

Related publications (73)

Loading

Loading

Loading

Related units (6)

Related lectures (3)

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.

The year 2016, in which I am writing these words, marks the centenary of Claude Shannon, the father of information theory. In his landmark 1948 paper "A Mathematical Theory of Communication", Shannon established the largest rate at which reliable communication is possible, and he referred to it as the channel capacity. Since then, researchers have focused on the design of practical coding schemes that could approach such a limit. The road to channel capacity has been almost 70 years long and, after many ideas, occasional detours, and some rediscoveries, it has culminated in the description of low-complexity and provably capacity-achieving coding schemes, namely, polar codes and iterative codes based on sparse graphs. However, next-generation communication systems require an unprecedented performance improvement and the number of transmission settings relevant in applications is rapidly increasing. Hence, although Shannon's limit seems finally close at hand, new challenges are just around the corner. In this thesis, we trace a road that goes from polar to Reed-Muller codes and, by doing so, we investigate three main topics: unified scaling, non-standard channels, and capacity via symmetry. First, we consider unified scaling. A coding scheme is capacity-achieving when, for any rate smaller than capacity, the error probability tends to 0 as the block length becomes increasingly larger. However, the practitioner is often interested in more specific questions such as, "How much do we need to increase the block length in order to halve the gap between rate and capacity?". We focus our analysis on polar codes and develop a unified framework to rigorously analyze the scaling of the main parameters, i.e., block length, rate, error probability, and channel quality. Furthermore, in light of the recent success of a list decoding algorithm for polar codes, we provide scaling results on the performance of list decoders. Next, we deal with non-standard channels. When we say that a coding scheme achieves capacity, we typically consider binary memoryless symmetric channels. However, practical transmission scenarios often involve more complicated settings. For example, the downlink of a cellular system is modeled as a broadcast channel, and the communication on fiber links is inherently asymmetric. We propose provably optimal low-complexity solutions for these settings. In particular, we present a polar coding scheme that achieves the best known rate region for the broadcast channel, and we describe three paradigms to achieve the capacity of asymmetric channels. To do so, we develop general coding "primitives", such as the chaining construction that has already proved to be useful in a variety of communication problems. Finally, we show how to achieve capacity via symmetry. In the early days of coding theory, a popular paradigm consisted in exploiting the structure of algebraic codes to devise practical decoding algorithms. However, proving the optimality of such coding schemes remained an elusive goal. In particular, the conjecture that Reed-Muller codes achieve capacity dates back to the 1960s. We solve this open problem by showing that Reed-Muller codes and, in general, codes with sufficient symmetry are capacity-achieving over erasure channels under optimal MAP decoding. As the proof does not rely on the precise structure of the codes, we are able to show that symmetry alone guarantees optimal performance.