ACM通信
研究突出了
技术视角:纠错码之美
纠错码是我们用来补偿通信干扰的手段，对数字数据的准确传输和存储至关重要。所有通信机制和存储设备都会受到干扰，通常称为“噪声”，它会破坏通信的消息和存储的数据。因此，为了使通信系统能够忠实地传输数据，它必须在其传输中建立冗余，这样即使传输部分损坏，预期的消息也可以被重建。错误纠正码提供从消息到冗余传输的映射。
例如，消息通常是由0和1组成的字符串。消息的冗余编码可以通过在原始消息中附加一些奇偶校验位来获得，以形成一个码字．的率码的长度是消息长度与码字长度之比，等于冗余的倒数。一种叫做信道的通信媒介可以传输位元，而噪声可以使位元从0变为1或从1变为0。例如，具有交叉概率的二进制对称信道p传输位，并按概率翻转每个位p,独立。在设计纠错码时，要考虑目标通信信道的抽象模型。
给定一个信道模型，应该设计一种代码，使速率最大化，同时最小化错误概率、延迟和编码和解码的计算复杂度的折衷。虽然在通信系统中实现低错误概率的目标基本上是概率的，但该领域的主要进展是通过一种最坏情况的确定性方法取得的。Guruswami和Rudra在这里的论文调查了编码问题的最坏情况方法的发展，并解释了他们自己最近的贡献。它们建立在经典里德-所罗门密码的基础上。
里德-所罗门码采用了一种信号字母表，其中包含的元素不止0和1:每个符号都是有限域的一个元素，比如整数对素数的模。里德-所罗门码的速率R，经典的解码算法可以有效地重构消息，只要最多a (1-R)/2部分传输码字中的符号被损坏。这正是保证问题有唯一解决方案的错误比例:存在一些罕见的模式，其中只包含一个错误，两个码字与损坏的传输相同接近。
解码里德-所罗门密码的一个重大进展来自苏丹4里德-所罗门码列表解码算法。列表解码解码器返回在损坏传输的一定距离内的所有码字的列表。虽然最接近的码字通常是唯一的，但通过返回列表选项简化了算法任务。Guruswami和苏丹的1苏丹的列表解码器的改进有效地返回所有码字的列表，不同于一个损坏的传输最多在一个
符号的分数，并且列表保证是短的。
与以前的解码算法相比，这是一个很大的改进，但在理想的高速率(接近1)下几乎没有区别，其中大致等于(1-R)/ 2。古鲁斯瓦米和楼陀罗的进步利用了帕瓦雷什和瓦尔迪的思想3.将里德-所罗门字母表符号捆绑在一起。这使得信号字母表略大，但大大增加了有效的列表解码所需要的错误比例。他们获得了利率代码R从中可以有效地生成与损坏传输不同的所有码字的列表，这些码字的符号接近1 -R．对于高速率代码，这几乎是以前的方案所能纠正的错误的两倍。此外，我们知道一个人不可能指望做得更好。
虽然这是一个巨大的理论进步，但在这些编码能够用于实际通信系统之前，还需要进行更多的工作。译码算法的运行时间为多项式，但在实际应用中需要提高译码速度。它们还需要加以扩展，以纳入来自通信系统较低层的信息。很少有通信媒体会自然地传输有限场元素，甚至是0和1。这些符号通常被转换成模拟波形。部分损坏波形的接收器可以做的不仅仅是报告哪个有效波形最接近:他们可以返回每个有效波形的可能性。一个不痒的决定译码器将此信息合并到解码过程中。
Koetter和Vardy2找到了如何将这些信息纳入Guruswami-Sudan算法的方法，在我们使用Guruswami-Rudra代码进行通信之前，可能还需要一个类似的发现。
参考文献
1.Guruswami, V.和Sudan, M.里德-所罗门码和代数-几何码的改进解码。IEEE反式。在信息。理论,45(1999), 17571767。
2.里德-所罗门码的代数软判决译码。IEEE反式。在信息。理论49地球物理学报，112(2003)，28092825。
3.Parvaresh, F.和Vardy, A.在多项式时间内纠正Guruswami-Sudan半径以外的误差。在第46届IEEE计算机科学基础研讨会论文集(2005), 285294。
©2009 acm 0001-0782/09/0300 $5.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2009 ACM, Inc.
没有发现记录