ﻻ يوجد ملخص باللغة العربية
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 $2times 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 $elltimesell$ 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(nlog n)$.
Polar codes with memory (PCM) are proposed in this paper: a pair of consecutive code blocks containing a controlled number of mutual information bits. The shared mutual information bits of the succeeded block can help the failed block to recover. The
In this paper, we show some applications of algebraic curves to the construction of kernels of polar codes over a discrete memoryless channel which is symmetric w.r.t the field operations. We will also study the minimum distance of the polar codes pr
As an important coding scheme in modern distributed storage systems, locally repairable codes (LRCs) have attracted a lot of attentions from perspectives of both practical applications and theoretical research. As a major topic in the research of LRC
Polar codes are the first class of constructive channel codes achieving the symmetric capacity of the binary-input discrete memoryless channels. But the corresponding code length is limited to the power of two. In this paper, we establish a systemati
We obtain a characterization on self-orthogonality for a given binary linear code in terms of the number of column vectors in its generator matrix, which extends the result of Bouyukliev et al. (2006). As an application, we give an algorithmic method