Capacity Achieving Random Sparse Linear Codes
Capacity Achieving Random Sparse Linear Codes
复制标题
实现随机稀疏线性码的能力
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
F. Marvasti
中科院分区：
文献类型：
--
作者：
A. M. Kakhaki;H. K. Abadi;P. Pad;H. Saeedi;Kasra Alishahi;F. Marvasti
本文证明了存在具有任意稀疏生成矩阵且能达到容量的线性码。特别地，我们证明了存在一些能达到容量的码，其生成矩阵中1的密度可以任意低。文献中关于存在能达到容量的线性码的现有结果仅限于生成矩阵元素以相等概率为0或1的码，这导致生成矩阵是非稀疏的，这将意味着高编码复杂度。还展示了生成矩阵的稀疏性和错误指数值之间一种有趣的权衡。与文献中仅限于具有非稀疏生成矩阵的码的现有结果相比，所提出的方法是新颖且更简洁的。尽管本文重点关注二进制对称信道和二进制删除信道，但这些结果可以很容易地扩展到其他离散无记忆对称信道。
In this paper the existence of capacity achieving linear codes with arbitrarily sparse generator matrices is proved. In particular, we show the existence of capacity achieving codes for which the density of ones in the generator matrix is arbitrarily low. The existing results on the existence of capacity achieving linear codes in the literature are limited to the codes whose generator matrix elements are zero or one with necessarily equal probability, yielding a non-sparse generator matrix. This will imply a high encoding complexity. An interesting trade-off between the sparsity of the generator matrix and the value of the error exponent is also demonstrated. Compared to the existing results in the literature, which are limited to codes with non-sparse generator matrices, the proposed approach is novel and more concise. Although the focus in this paper is on the Binary Symmetric and Binary Erasure Channels, the results can be easily extended to other discrete memory-less symmetric channels.