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. 67(9), 5693–5710.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | 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
Volume
67
Issue
9
Page
5693-5710
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;67(9):5693-5710. 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, vol. 67, no. 9. IEEE, pp. 5693–5710, 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. 67(9), 5693–5710.
Fazeli, Arman, et al. “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” IEEE Transactions on Information Theory, vol. 67, no. 9, IEEE, 2020, pp. 5693–710, doi:10.1109/TIT.2020.3038806.

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1711.01339

Search this title in

Google Scholar