How to Construct Polar Codes

By Ido Tal, Alexander Vardy. IEEE Transactions on Information Theory, 2011

851 citations recorded by the source corpus.

A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with the code length. Thus, the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which “sandwich” the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed ε > 0 and all sufficiently large code lengths n, polar codes whose rate is within ε of channel capacity can be constructed in time and space that are both linear in n.

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/1905f42cd7a3175972919d7fa988d8c495d3b55c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Efficient Design and Decoding of Polar Codes (2012, background): “An implementation of density evolution with complexity O(nμ(2) logμ) was proposed in [4], where n is the length of the polar code to be constructed, and μ is the number of quantization levels, which has to be selected sufficiently high to achieve the required accuracy.”
Fast Polar Decoders: Algorithm and Implementation (2013, background): “While some throughput improvement is possible via some code modifications, the resulting polar code diverges from t he optimal one constructed according to [9].”
Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes (2010, methodology): “For example, to establish the results reported in (99), we have run the algorithm of [38] with a precision of 300 bits (which is necessary to provide meaningful guarantees of security down to ).”
CRC-Aided Decoding of Polar Codes (2012, methodology): “For polar codes, the information set A is selected using the method in [8].”
Twelve Scientific Challenges for 6G: Rethinking the Foundations of Communications Theory (2022, background): “Since the early development of wireless generations, 2G, 3G, and up to 5G networks, channel coding has always been an essential component in the transmission process, and therefore, several efforts were devoted for developing resilient channel coding mechanisms, spanning from the basic algebraic cod”
List decoding of polar codes (2011, methodology): “Code construction was carried out via the method proposed in [4].”
Simultaneous Wireless Information and Power Transfer (SWIPT): Recent Advances and Future Challenges (2018, methodology): “A method for efficiently constructing polar codes has been presented and analysed in [180], and it has been applied in cooperative communications.”
Systematic Polar Coding (2011, methodology): “The set A for polar coding was optimized for operation at Eb/N0 = 1 (0 dB) using the Tal-Vardy method [9].”