在计算机，电信，信息理论和编码理论中，纠错码（ECC，）是信息传输中错误检测与纠正的工具。它通常用在不可靠或嘈杂的信道中。数据发送方利用纠错码中的冗余信息，使得接收方能够检测消息传输中发生的错误，而且通常可以纠正这些错误而无需重新传输。美国数学家理查德·汉明（Richard Hamming）在1940年代开创了这一领域，并在1950年发明了第一个纠错码：汉明（7,4）代码。。它可以矫正一位错误或检测两位错误。汉明码仅适用于相对可靠的单层单元NAND，较稠密的多层单元NAND需要能够校正更多位的纠错码，例如BCH或里德-所罗门码 。NOR闪存通常不需要任何错误校正。，在这种决策方式下，每个输入和输出信号都非1即0。而卷积码则相反，使用如维特比，MAP或算法之类的软决策算法进行解码，该算法用于离散化的模拟信号，并且比硬判决解码具有更高的纠错性能。
几乎所有的经典分组码都利用了有限域的代数性质。因此，经典分组码也称为代数码。
经典分组码的检错或纠错能力通常是事先预定的，而许多现代的分组码（例如低密度奇偶檢查碼）并没有这方面的保证；它们的能力是由误码率来评估的。
大多数前向纠错码仅纠正翻转位，而不能纠正插入位或丢失位。在这种情况下，计算误码率时应使用汉明距离。一些前向纠错码可以纠正插入位和丢失位，例如标记码和水印码。若使用此类代码，测量比特误码率时使用莱文斯坦距离更加合适。
可靠性和编码率的权衡利弊
纠错码的基本原理是以添加冗余位的方法，来帮助解码器寻回编码前的原本消息。纠错码系统的编码率指的是通信包中，信息位数与总位数（总位数=信息+冗余位数）之间的比率。接近零的低码率表示代码的纠错能力强，反之，若纠错码有着接近1的大码率，则意味着代码的纠错能力较弱。
传输这些冗余位时，必须消耗有限的通信资，这导致了可靠性和数据速率之间的相互冲突。在极端情况下，具有低传输效率的强代码会导致接收器信噪比的大幅增加，这样降低了误码率，但同时也降低了有效数据的速率。另一方面，不使用任何纠错码（此时码率=1）将整个信道用于信息传输目的，这样效率极高但没有任何纠错能力。
具有极低错误率的纠错码，能够达到怎样的信息传输效率？克劳德·香农的第二定理给出了答案，根据该定理，若错误率趋于零，纠错码的速率最大可以达到信道容量 。他的证明使用了高斯随机编码，并不适用于实际应用。香农给出了一个速率的上限，而学界为了设计出达到速率上限的纠错码，踏上了漫长的旅途。如今，有些纠错码几乎可以达到香农极限，但是通常实施起来极其复杂。
常见的几种纠错码必须在纠错性能和计算复杂度之间取得平衡。通常，它们的参数可以适用特定区间以内的编码率，可以根据不同的情况自动选择较优的编码率。这样可以降低冗余位对数据速率的影响，同时减少错误。优化编码率的另一个准则是在低误码率的情况下尽量减少重传次数，以降低通信的能源成本。
如上文中的许多例子所示，“不定式”一词并不表明它的极限不存在。在许多情况下，我们可以使用洛必达法则，代数方程求解，或其他方法计算极限。
纠错码列表
- AN codes
- BCH码，可以设计为更正每个代码块中任意数量的错误。
*
- Constant-weight code
- 卷积码
- Expander code
- Group code
- Golay code
- Goppa code, used in the McEliece cryptosystem
- Hadamard code
- Hagelbarger code
- 汉明码
- 基于拉丁方陣的代码
- Lexicographic code
- Long code
- 低密度奇偶檢查碼
- 盧比變換碼
- m of n codes
- Online code
- 極化碼
- Raptor code
- 里德-所罗门码
*
- Repeat-accumulate code
- Repetition code
- 脊柱代码，一种基于伪随机哈希函数的无速率非线性代码。
- Tornado code
- 涡轮码
- Walsh–Hadamard code
- 循環冗餘校驗
另见
- 编码率
- 抹除碼
- 错误检测与纠正
参考文献
评论 (0)