Binary linear codes with optimal scaling: Polar codes with large kernels

Fazeli A, Hassani H, Mondelli M, Vardy A. 2020. Binary linear codes with optimal scaling: Polar codes with large kernels. IEEE Transactions on Information Theory.

Download
No fulltext has been uploaded. References only!

Journal Article | Epub ahead of print | English

Scopus indexed
Author
Fazeli, Arman; Hassani, Hamed; Mondelli, MarcoIST Austria ; Vardy, Alexander
Department
Abstract
We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε>0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ=2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2×2 kernel) on the BEC is μ=3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist ℓ×ℓ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ(ℓ) that tends to the optimal value of 2 as ℓ grows. We furthermore characterize precisely how large ℓ needs to be as a function of the gap between μ(ℓ) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(nlogn).
Publishing Year
Date Published
2020-11-17
Journal Title
IEEE Transactions on Information Theory
ISSN
eISSN
IST-REx-ID

Cite this

Fazeli A, Hassani H, Mondelli M, Vardy A. Binary linear codes with optimal scaling: Polar codes with large kernels. IEEE Transactions on Information Theory. 2020. doi:10.1109/TIT.2020.3038806
Fazeli, A., Hassani, H., Mondelli, M., & Vardy, A. (2020). Binary linear codes with optimal scaling: Polar codes with large kernels. IEEE Transactions on Information Theory. IEEE. https://doi.org/10.1109/TIT.2020.3038806
Fazeli, Arman, Hamed Hassani, Marco Mondelli, and Alexander Vardy. “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” IEEE Transactions on Information Theory. IEEE, 2020. https://doi.org/10.1109/TIT.2020.3038806.
A. Fazeli, H. Hassani, M. Mondelli, and A. Vardy, “Binary linear codes with optimal scaling: Polar codes with large kernels,” IEEE Transactions on Information Theory. IEEE, 2020.
Fazeli A, Hassani H, Mondelli M, Vardy A. 2020. Binary linear codes with optimal scaling: Polar codes with large kernels. IEEE Transactions on Information Theory.
Fazeli, Arman, et al. “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” IEEE Transactions on Information Theory, IEEE, 2020, doi:10.1109/TIT.2020.3038806.

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1711.01339

Search this title in

Google Scholar