Parity-check density versus performance of binary linear block codes over memoryless symmetric channels
Parity-check density versus performance of binary linear block codes over memoryless symmetric channels
复制标题
无记忆对称通道上的奇偶校验密度与二进制线性块码的性能
DOI：
--
复制
发表时间：
2003
影响因子：
2.5
通讯作者：
R. Urbanke
中科院分区：
文献类型：
--
作者：
I. Sason;R. Urbanke
我们推导了用于无记忆二进制输入输出对称(MBIOS)信道的二进制线性码的奇偶校验矩阵密度的下界。根据可实现可靠通信的这些码的速率与信道容量之间的间隔来表示界限；如果存在平均误码概率为零的译码算法，则它们对于每个二进制线性分组码序列都有效。对于每个MBIOS信道，我们构造了一系列规则的低密度奇偶校验(LDPC)码，使得它们的奇偶校验矩阵的渐近密度的上界与下界的比例类似。通过分析Shokroll lahi提出的能够达到二进制纠错信道容量的右正则LDPC码集序列，证明了二进制纠删信道下界的紧密性。在迭代消息传递译码下，我们证明了这个系综序列是渐近最优的(在本文定义的意义下)，加强了Shokroll lahi的一个结果。最后，我们推导了用二部图表示的二元线性分组码的误比特率和容量差的下界，并研究了它们在MBIOS信道上的性能限制。后一个界限为代表良好纠错码的二部图的圈数提供了一个定量的度量。
We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.