---
_id: '6665'
abstract:
- lang: eng
text: 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).
author:
- first_name: Arman
full_name: Fazeli, Arman
last_name: Fazeli
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Alexander
full_name: Vardy, Alexander
last_name: Vardy
citation:
ama: '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'
apa: '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'
chicago: '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.'
ieee: '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.'
ista: '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.'
mla: '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.'
short: A. Fazeli, H. Hassani, M. Mondelli, A. Vardy, in:, 2018 IEEE Information
Theory Workshop, IEEE, 2018, pp. 1–5.
conference:
end_date: 2018-11-29
location: Guangzhou, China
name: 'ITW: Information Theory Workshop'
start_date: 2018-11-25
date_created: 2019-07-23T11:01:42Z
date_published: 2018-11-01T00:00:00Z
date_updated: 2024-03-07T12:18:50Z
day: '01'
doi: 10.1109/itw.2018.8613428
extern: '1'
external_id:
arxiv:
- '1711.01339'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1711.01339
month: '11'
oa: 1
oa_version: Preprint
page: 1-5
publication: 2018 IEEE Information Theory Workshop
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '9002'
relation: later_version
status: public
status: public
title: 'Binary linear codes with optimal scaling: Polar codes with large kernels'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...