Scaling exponent of sparse random linear codes over binary erasure channels
Scaling exponent of sparse random linear codes over binary erasure channels
复制标题
二进制擦除通道上稀疏随机线性码的缩放指数
DOI：
10.1109/isit.2017.8006616
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Hessam Mahdavifar
中科院分区：
文献类型：
--
作者：
Hessam Mahdavifar
考虑了分析稀疏随机线性码的有限长度缩放行为的问题。具有随机生成矩阵的随机线性码，其元素根据参数\(q = o(1)\)的独立同分布伯努利分布选取，被称为稀疏的。参数\(q\)被称为随机线性码的稀疏度。我们开发了一种方法来证明均匀随机线性码（即\(q = 1/2\)）的缩放指数以高概率是最优的。然后将结果扩展到稀疏度\(q = Θ(n^{−1/2})\)的稀疏随机线性码，其中\(n\)是码块长度。这种稀疏随机线性码的编码复杂度从均匀随机线性码中的\(O(n^2)\)降低到\(O(n^{3/2})\)。还推测\(q = \log n / n\)是具有最优缩放指数的随机线性码的最低稀疏度。还讨论了这些结果与关于寻找具有最优缩放指数的二进制极化码的一个开放问题的联系。特别是，我们指出随着极化核的大小增加，它可以用作具有最优缩放指数的码的生成矩阵，而无需进一步极化。
The problem of analyzing the finite-length scaling behavior of sparse random linear codes is considered. Random linear codes with random generator matrices whose entries are picked according to i.i.d. Bernoulli distribution with parameter q = o(1) are called sparse. The parameter q is referred to as the sparsity of the random linear code. We develop a methodology to show the optimality of the scaling exponent of uniform random linear codes, i.e., q = 1/2, with high probability. The results are then extended to sparse random linear codes with sparsity q = Θ(n−1/2), where n is the code block length. The encoding complexity of such sparse random linear codes is reduced from O(n2), in uniform random linear codes, to O(n 3/2). It is also conjectured that q = log n/n is the lowest sparsity of random linear codes with optimal scaling exponent. The connection of these results to an open problem regarding finding binary polar codes with optimal scaling exponent are also discussed. In particular, we point out that as the size of the polarization kernel increases it can be used as the generator matrix for a code with optimal scaling exponent, without the need to do further polarization.