Low-Density Parity-Check Codes
Low-Density Parity-Check Codes
复制标题
DOI：
10.1007/978-3-540-69457-1_3
复制
发表时间：
2009-01-01
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
大约60年前，香农的开创性论文奠定了信息论的基础。特别是，它将信道编码描述为实现所谓信道容量的一种手段，即利用信道的全部信息传输潜力。从那时起，用于点对点通信的理论和技术一直在发展，直到现在，对于几个简单信道存在实际上接近信道容量的差距的技术。这已经通过诸如turbo码和低密度奇偶校验（LDPC）码的强大编码方法的发明而成为可能。Turbo码的思想最早发表在1993年的一篇会议论文中，作者使用了强大的级联码和迭代方案，使得有效地（尽管次优）执行解码成为可能。自Turbo码提出以来，科学界的大量资源都转移到迭代检测和译码技术的研究上。这最终导致了LDPC码在1995年的重新发现。事实上，LDPC码最早是由Robert Gallager在60年代初提出和分析的。当时，有限的计算能力使得LDPC码的使用不切实际，并阻止了科学家充分了解其潜力。在90年代后期引入非规则LDPC码和实用性能分析工具之后，LDPC码成为最强大的纠错码，使得能够以接近多个无记忆信道的信道容量的速率进行可靠传输。LDPC码最初是为二进制输入无记忆信道设计的。虽然二进制输入假设并不是真正的限制-LDPC码实际上可以很容易地推广到非二进制输入符号-摆脱无记忆假设是一个微妙的任务。事实上，尽管用于二进制输入无记忆信道的LDPC码允许对于增加码字长度渐近最优的解码算法-除了在少数情况下对于有限码字长度是最优的之外-但不存在实现容量的编码方案，也不存在实用的最优解码算法
About sixty years ago, Shannon’s seminal paper laid the foundations of information theory. In particular, it characterized channel coding as a means for achieving the so-called channel capacity, ie, to exploit the full information transfer potential of the channel. Since then, both theory and techniques for point-to-point communications have been constantly developed, up to the point that, nowadays, techniques for practically closing the gap to channel capacity exist for several simple channels. This has been made possible by the invention of powerful coding methods, such as turbo codes and low-density parity-check (LDPC) codes. The idea of turbo codes was first published in a conference paper in 1993, where the authors used powerful concatenated codes and an iterative scheme which made possible to effectively—although suboptimally—perform decoding. Since the introduction of turbo codes, a huge amount of resources in the scientific community moved to the investigation of iterative detection and decoding techniques. This eventually led to the rediscovery of LDPC codes in 1995. In fact, LDPC codes were first introduces and analyzed by Robert Gallager in the early Sixties. At that time, the limited available computational power made the use of LDPC codes impractical and prevented scientists from fully understanding their potential. After the introduction of irregular LDPC codes and of practical performance analysis tools in the late Nineties, LDPC codes became the most powerful error correcting codes, enabling reliable transmissions at rates close to the channel capacity for a number of memoryless channels. LDPC codes were originally designed for binary input memoryless channels. Although the binary input assumption is not really restrictive—LDPC codes can in fact be easily generalized to non-binary input symbols—getting rid of the memoryless assumption is a subtle task. In fact, despite LDPC codes for binary-input memoryless channels admit a decoding algorithm which is asymptotically optimum for increasing codeword lengths—besides being optimum, in a few cases, also for finite codeword lengths—there exists no capacity-achieving coding scheme nor practical optimum decoding algorithm