---
res:
bibo_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).@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Arman
foaf_name: Fazeli, Arman
foaf_surname: Fazeli
- foaf_Person:
foaf_givenName: Hamed
foaf_name: Hassani, Hamed
foaf_surname: Hassani
- foaf_Person:
foaf_givenName: Marco
foaf_name: Mondelli, Marco
foaf_surname: Mondelli
foaf_workInfoHomepage: http://www.librecat.org/personId=27EB676C-8706-11E9-9510-7717E6697425
orcid: 0000-0002-3242-7020
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Vardy, Alexander
foaf_surname: Vardy
bibo_doi: 10.1109/TIT.2020.3038806
bibo_issue: '9'
bibo_volume: 67
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0018-9448
- http://id.crossref.org/issn/1557-9654
dct_language: eng
dct_publisher: IEEE@
dct_title: 'Binary linear codes with optimal scaling: Polar codes with large kernels@'
...