부산대학교 도서관

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 $\varepsilon > 0$ of capacity, the code length $n$ often scales as $O(1/\varepsilon ^{\mu })$ , where the constant $\mu $ is called the scaling exponent . It is known that the optimal scaling exponent is $\mu =2$ , and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the $2\times 2$ kernel) on the BEC is $\mu =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 $\ell \times \ell $ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent $\mu (\ell)$ that tends to the optimal value of 2 as $\ell $ grows. We furthermore characterize precisely how large $\ell $ needs to be as a function of the gap between $\mu (\ell)$ 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(n\log n)$ .