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

A. Fazeli, H. Hassani, M. Mondelli, A. Vardy, in:, 2018 IEEE Information Theory Workshop, IEEE, 2018, pp. 1–5.


Conference Paper | Published | English
Author
; ; ;
Abstract
We prove that, at least for the binary erasure channel, the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but, in fact, 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. Specifically, for any fixed δ > 0, we exhibit binary linear codes that ensure reliable communication at rates within ε > 0 of capacity with block length n = O(1/ε 2+δ ), construction complexity Θ(n), and encoding/decoding complexity Θ(n log n).
Publishing Year
Date Published
2018-11-01
Proceedings Title
2018 IEEE Information Theory Workshop
Page
1-5
Conference
ITW: Information Theory Workshop
Conference Location
Guangzhou, China
Conference Date
2018-11-25 – 2018-11-29
IST-REx-ID

Cite this

Fazeli A, Hassani H, Mondelli M, Vardy A. Binary linear codes with optimal scaling: Polar codes with large kernels. In: 2018 IEEE Information Theory Workshop. IEEE; 2018:1-5. doi:10.1109/itw.2018.8613428
Fazeli, A., Hassani, H., Mondelli, M., & Vardy, A. (2018). Binary linear codes with optimal scaling: Polar codes with large kernels. In 2018 IEEE Information Theory Workshop (pp. 1–5). Guangzhou, China: IEEE. https://doi.org/10.1109/itw.2018.8613428
Fazeli, Arman, Hamed Hassani, Marco Mondelli, and Alexander Vardy. “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” In 2018 IEEE Information Theory Workshop, 1–5. IEEE, 2018. https://doi.org/10.1109/itw.2018.8613428.
A. Fazeli, H. Hassani, M. Mondelli, and A. Vardy, “Binary linear codes with optimal scaling: Polar codes with large kernels,” in 2018 IEEE Information Theory Workshop, Guangzhou, China, 2018, pp. 1–5.
Fazeli A, Hassani H, Mondelli M, Vardy A. 2018. Binary linear codes with optimal scaling: Polar codes with large kernels. 2018 IEEE Information Theory Workshop. ITW: Information Theory Workshop 1–5.
Fazeli, Arman, et al. “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” 2018 IEEE Information Theory Workshop, IEEE, 2018, pp. 1–5, doi:10.1109/itw.2018.8613428.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1711.01339

Search this title in

Google Scholar