纠错码
| 此條目可参照英語維基百科相應條目来扩充。 (2019年8月29日) |
在计算机，电信，信息理论和编码理论中，纠错码（ECC，error correction/correcting code）是信息传输中错误检测与纠正的工具。它通常用在不可靠或嘈杂的信道中。[1][2]数据发送方利用纠错码中的冗余信息，使得接收方能够检测消息传输中发生的错误，而且通常可以纠正这些错误而无需重新传输。美国数学家理查德·汉明（Richard Hamming）在1940年代开创了这一领域，并在1950年发明了第一个纠错码：汉明（7,4）代码。[2]
相比错误检测，纠错码不仅能够检测到错误，而且可以将其更正。它的优点是在出现错误时不需要反向信道来请求重发数据，缺点是消息中增加了固定开销，因此需要更高的前向信道带宽。因此，纠错码用于重传成本高昂或无法实现的情况，例如单向通信链路，时延较长的链接，以及以多播方式发送给多个接收者的链接。比如，绕天王星运行的卫星，由于传输错误而造成的重发会造成5个小时的延迟。纠错码信息通常添加到大容量存储设备中，以恢复损坏的数据，并广泛用于调制解调器、固态硬盘，以及主存为 ECC 内存的系统中。
接收机中的纠错码处理可以应用于数字比特流，也可以应用于数字调制载波的解调。对于后者，纠错码是接收器中類比數位轉換器的组成部分。维特比（Viterbi）解码器采用软判决算法，以从被噪声破坏的模拟信号中解调数字数据。许多纠错码编码器/解码器还可以生成比特误码率（BER）信号，该信号可用作反馈以微调模拟接收电子设备。
纠错码能够纠正的错误位/丢失位的最大数量取决于它的的设计，因此，不同的纠错码适用于不同的环境。一般来说，能够纠正大量错误的代码中有着更多的冗余信息，所以会需要更多带宽进行传输，从而降低了有效比特率，且同时提高了接收到的有效信噪比。克劳德·香农（Claude Shannon）的有噪信道编码定理回答了以下问题：若使用最有效的代码将解码错误概率变为零，数据通信还剩下多少带宽？对于具有基本噪声水平的信道，该定理给出了理论上的最大信息传输速率。但是，该证明不具建设性，也就是说它并不能用来构建实现最大速率的代码。经过多年的研究，如今[何时？]一些先进的纠错码系统，其速率已非常接近理论最大值。
工作原理 编辑
纠错码的编码方法如下：发信方利用算法，向要传输的信息添加冗余位。这些冗余位通常是将原始输入位由复杂的函数转换而成。原始信息不一定原样出现在输出的编码中；包含原始信息的代码称为系统代码，反之称为非系统代码。
下面是一个简单纠错码的例子：将每个数据位发送3次。这种编码称为（3,1）重复码。 通过嘈杂的频道，接收器可能会收到8个不同版本的输出，参见下表：
| 接收信号 | 解码 |
|---|---|
| 000 | 0 (无错) |
| 001 | 0 |
| 010 | 0 |
| 100 | 0 |
| 111 | 1 (无错) |
| 110 | 1 |
| 101 | 1 |
| 011 | 1 |
若收到的信息非3个重复的数位，则以重复次数较多的数位为准。该纠错码最多纠正一位错误位，或两位丢失位。虽然这种纠错码实施方便且应用广泛，但这种三重模塊冗餘的形式是效率较低的。更好的纠错码通常会检查先前接收到的几十位，或几百位，由此判断如何解码当前的几位（通常以2到8位为一组）。
利用噪声的“平均化”来减少错误 编辑
纠错码的使用对信息噪声产生的破坏有“平均化”的作用。由于每一个原始数据位生成了多于一个的传输符，尽管某些传输符可能遭到噪声的破坏，接收方通常能够依赖其它未损坏的，由相同原始位生成的接收符来获取原本数据。由于这种效应，使用纠错码的数字通信系统往往能够在信噪比远高于最小信噪比的情况下运转。在运转过程中，系统的信噪比永远不会低于最小信噪比。当使用更强的，接近香农极限的代码时，这种懸崖效應将变得更加明显。有时，信道错误通常是突發型的。在这种情况下，可以使用交错的纠错码来将数据编码，这样能够降低所传输纠错码的悬崖效应。但是，这种方法也有局限性，它比较适用于窄带数据。
大多数电信系统使用固定的信道代码，这样的信道代码通常可以容忍预期的最坏误码率；如果误码率高于该值，则系统根本无法运转。但是，有些系统能够适应特定的信道错误条件：在一些混合式自動重送請求的实例中，错误率较低时系统使用固定的纠错码，而在错误率过高时切换到自动重传请求。 自適應調變和編碼能够应对多种错误率：当通道中的错误率较高时，在每个数据包中添加更多的纠错位，而在不需要它们时将其删除。
纠错码的种类 编辑
分组码适用于一连串固定长度的数据包，而每一种分组码只能用于特定长度的数据包。实际用途中的分组码一般使用硬解码方式，所需时间为每一个数据包长度的多项式时间。分组码有许多不同的类型，值得关注的有里德-所罗门码，它被广泛的应用于光盘，DVD和硬盘驱动器中。经典分组码的其他例子有格雷码，BCH码，多维奇偶校验码和汉明码。
卷积码适用于任意长度的位元流/符号流。接收方通常使用维特比算法将其软解码，但有时也会用其他算法。随着卷积码约束条件的长度增加，维特比解码的解码效率渐近最优；但作为代价，计算时间将以对数式增长。长度有限的卷积码也可以看作一种“分组码”，因为输入数据是成组的；但是卷积码的每一“组”长度不一，而分组码的长度是固定的，且由其特定的代数性质而定。 卷积码有几种不同的终止方式，如“咬尾巴（tail-biting）”和“位元刷新（bit-flushing）”。
汉明纠错码一般用来纠正NAND闪存错误[3]。它可以矫正一位错误或检测两位错误。汉明码仅适用于相对可靠的单层单元NAND，较稠密的多层单元NAND需要能够校正更多位的纠错码，例如BCH或里德-所罗门码[4][5] 。NOR闪存通常不需要任何错误校正。[4]
分组码通常使用硬决策算法解码[6]，在这种决策方式下，每个输入和输出信号都非1即0。而卷积码则相反，使用如维特比，MAP或BCJR算法之类的软决策算法进行解码，该算法用于离散化的模拟信号，并且比硬判决解码具有更高的纠错性能。
几乎所有的经典分组码都利用了有限域的代数性质。因此，经典分组码也称为代数码。
经典分组码的检错或纠错能力通常是事先预定的，而许多现代的分组码（例如低密度奇偶檢查碼）并没有这方面的保证；它们的能力是由误码率来评估的。
大多数前向纠错码仅纠正翻转位，而不能纠正插入位或丢失位。在这种情况下，计算误码率时应使用汉明距离。一些前向纠错码可以纠正插入位和丢失位，例如标记码和水印码。若使用此类代码，测量比特误码率时使用莱文斯坦距离更加合适。 [7]
可靠性和编码率的权衡利弊 编辑
纠错码的基本原理是以添加冗余位的方法，来帮助解码器寻回编码前的原本消息。纠错码系统的编码率指的是通信包中，信息位数与总位数（总位数=信息+冗余位数）之间的比率。接近零的低码率表示代码的纠错能力强，反之，若纠错码有着接近1的大码率，则意味着代码的纠错能力较弱。
传输这些冗余位时，必须消耗有限的通信资源，这导致了可靠性和数据速率之间的相互冲突[8]。在极端情况下，具有低传输效率的强代码会导致接收器信噪比的大幅增加，这样降低了误码率，但同时也降低了有效数据的速率。另一方面，不使用任何纠错码（此时码率=1）将整个信道用于信息传输目的，这样效率极高但没有任何纠错能力。
具有极低错误率的纠错码，能够达到怎样的信息传输效率？克劳德·香农的第二定理给出了答案，根据该定理，若错误率趋于零，纠错码的速率最大可以达到信道容量[9] 。他的证明使用了高斯随机编码，并不适用于实际应用。香农给出了一个速率的上限，而学界为了设计出达到速率上限的纠错码，踏上了漫长的旅途。如今，有些纠错码几乎可以达到香农极限，但是通常实施起来极其复杂。
常见的几种纠错码必须在纠错性能和计算复杂度之间取得平衡。通常，它们的参数可以适用特定区间以内的编码率，可以根据不同的情况自动选择较优的编码率。这样可以降低冗余位对数据速率的影响，同时减少错误。优化编码率的另一个准则是在低误码率的情况下尽量减少重传次数，以降低通信的能源成本。[10]
如上文中的许多例子所示，“不定式”一词并不表明它的极限不存在。在许多情况下，我们可以使用洛必达法则，代数方程求解，或其他方法计算极限。
纠错码列表 编辑
| Distance | Code |
|---|---|
| 2 （单错误检测） | 奇偶性 |
| 3 （单错误检测） | 三重模塊冗餘 |
| 3 （单错误检测） | perfect Hamming such as Hamming(7,4) |
| 4 （SECDED） | Extended Hamming |
| 5 （双重错误校正） | |
| 6 （双重错误校正/三重错误检测) | |
| 7 （三错误校正） | perfect binary Golay code |
| 8 （TECFED） | extended binary Golay code |
- 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
- 里德-所罗门码
- Reed–Muller code
- Repeat-accumulate code
- Repetition code
- 脊柱代码，一种基于伪随机哈希函数的无速率非线性代码。[11]
- Tornado code
- 涡轮码
- Walsh–Hadamard code
- 循環冗餘校驗
另见 编辑
参考文献 编辑
- ^ Glover, Neal; Dudley, Trent. Practical Error Correction Design For Engineers Revision 1.1, 2nd. CO, USA: Cirrus Logic. 1990. ISBN 0-927239-00-0. ISBN 978-0-927239-00-4.
- ^ 2.0 2.1 Hamming, R. W. Error Detecting and Error Correcting Codes. Bell System Technical Journal (USA: AT&T). April 1950, 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x.
- ^ "Hamming codes for NAND flash memory devices" （页面存档备份，存于互联网档案馆）. EE Times-Asia. Apparently based on "Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices" （页面存档备份，存于互联网档案馆）. 2005. Both say: "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications."
- ^ 4.0 4.1 What Types of ECC Should Be Used on Flash Memory? (Application note). Spansion. 2011 [2020-06-26]. （原始内容 (PDF)于2016-03-04）.
Both Reed-Solomon algorithm and BCH algorithm are common ECC choices for MLC NAND flash. ... Hamming based block codes are the most commonly used ECC for SLC.... both Reed-Solomon and BCH are able to handle multiple errors and are widely used on MLC flash.
|url-status=和|dead-url=只需其一 (帮助) - ^ Jim Cooke. The Inconvenient Truths of NAND Flash Memory (PDF): 28. August 2007 [2020-06-26]. （原始内容 (PDF)于2020-11-12）.
For SLC, a code with a correction threshold of 1 is sufficient. t=4 required ... for MLC.
- ^ Baldi, M.; Chiaraluce, F. A Simple Scheme for Belief Propagation Decoding of BCH and RS Codes in Multimedia Transmissions. International Journal of Digital Multimedia Broadcasting. 2008, 2008: 1–12 [2020-06-26]. doi:10.1155/2008/957846 . （原始内容于2019-12-18）.
- ^ Shah, Gaurav; Molina, Andres; Blaze, Matt. Keyboards and covert channels. USENIX. 2006 [20 December 2018]. （原始内容于2021-03-08）.
- ^ Tse, David; Viswanath, Pramod, Fundamentals of Wireless Communication, Cambridge University Press, UK, 2005
- ^ Shannon, C. E. A mathematical theory of communication (PDF). Bell System Technical Journal. 1948, 27 (3–4): 379–423 & 623–656 [2021-07-20]. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2 . （原始内容 (PDF)于2022-02-12）.
- ^ Rosas, F.; Brante, G.; Souza, R. D.; Oberli, C. Optimizing the code rate for achieving energy-efficient wireless communications. Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC). 2014 [2021-07-20]. （原始内容于2021-07-20）.
- ^ Perry, Jonathan; Balakrishnan, Hari; Shah, Devavrat. Rateless Spinal Codes. Proceedings of the 10th ACM Workshop on Hot Topics in Networks. 2011. doi:10.1145/2070562.2070568.