Capacity achieving linear codes with random binary sparse generating matrices over the Binary Symmetric Channel
Capacity achieving linear codes with random binary sparse generating matrices over the Binary Symmetric Channel
复制标题
在二进制对称信道上使用随机二进制稀疏生成矩阵实现线性码的能力
DOI：
10.1109/isit.2012.6284267
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Kasra Alishahi
中科院分区：
文献类型：
--
作者：
A. M. Kakhaki;H. K. Abadi;P. Pad;H. Saeedi;F. Marvasti;Kasra Alishahi
在本文中，我们证明了在二进制对称信道（BSC）上使用随机二进制稀疏生成矩阵实现线性码的能力的存在。文献中关于实现线性码的能力存在性的结果仅限于等概率生成矩阵元素和稀疏奇偶校验矩阵的随机二进制码。此外，文献中报道的具有稀疏生成矩阵的码并未被证明能够实现除二进制擦除信道之外的信道的容量。与文献中基于最优最大后验解码器的现有结果相反，所提出的方法基于不同的解码器，因此不是最优的。我们还展示了生成矩阵的稀疏性和误差指数（一个常数，决定当块长度趋于无穷大时误差概率以指数方式衰减的速度）之间的有趣权衡。基于我们的结果，我们还提出了在给定块长度和错误概率下线性码可实现的信道编码率。此外，我们证明了在生成矩阵的行上具有给定（任意低）密度的线性码的存在能力。除了证明容量实现稀疏码的存在性之外，本文的一个重要结论是证明任意选择的稀疏生成矩阵序列都是高概率容量实现的。
In this paper, we prove the existence of capacity achieving linear codes with random binary sparse generating matrices over the Binary Symmetric Channel (BSC). The results on the existence of capacity achieving linear codes in the literature are limited to the random binary codes with equal probability generating matrix elements and sparse parity-check matrices. Moreover, the codes with sparse generating matrices reported in the literature are not proved to be capacity achieving for channels other than Binary Erasure Channel. As opposed to the existing results in the literature, which are based on optimal maximum a posteriori decoders, the proposed approach is based on a different decoder and consequently is suboptimal. We also demonstrate an interesting trade-off between the sparsity of the generating matrix and the error exponent (a constant which determines how exponentially fast the probability of error decays as block length tends to infinity). Based on our results, we also propose a channel coding rate achievable by linear codes at a given block length and error probability. Moreover, we prove the existence of capacity achieving linear codes with a given (arbitrarily low) density of ones on rows of the generating matrix. In addition to proving the existence of capacity achieving sparse codes, an important conclusion of our paper is to prove that any arbitrarily selected sequence of sparse generating matrices is capacity achieving with high probability.