The capacity of low-density parity-check codes under message-passing decoding
The capacity of low-density parity-check codes under message-passing decoding
复制标题
DOI：
10.1109/18.910577
复制
发表时间：
2001-02-01
影响因子：
2.5
通讯作者：
Urbanke, RL
中科院分区：
文献类型：
--
作者：
Richardson, TJ;Urbanke, RL
本文提出了一种在消息传递译码下确定低密度奇偶校验(LDPC)码容量的一般方法。当在任何具有离散或连续输出字母表的二进制输入无记忆信道上，以低于该容量的速率传输时，给定系综中随机选择的元素将获得任意小的目标差错概率，其概率在码长上接近于1。(通过与适当的外部码级联，可以获得在码长上以指数速度接近于零的差错概率，而在速率上损失任意小。)相反，以高于该容量的速率传输时，差错概率通过与代码长度和执行的迭代次数无关的严格的正常数来限定为零。我们的结果是基于Luby等人观察到的解码器的性能集中在其平均性能周围的观察结果。[1]在二进制对称信道和二进制消息传递算法是一种普遍现象的情况下，对于信任传播译码这一特别重要的情况，我们提供了一种有效的算法来确定相应的容量，以达到任何期望的精度，本文提出的思想具有广泛的适用性，并概述了一般方法对大字母表上的低密度奇偶校验码、Turbo码和其他级联编码方案的扩展。
In this paper, we present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets, Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. [1] in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon, For the particularly important case of belief-propagation decoders, we provide an effective algorithm to deter-mine the corresponding capacity to any desired degree of accuracy, The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.