下载掌阅APP，畅读海量书库
立即打开
纠错编码（error correcting code，ECC）广泛应用于各种通信系统、存储系统中，用于在不可靠信道中检测和纠正信息传输过程中发生的错误，以保障数据可靠性。1948年，克劳德·香农（Claude E.Shannon）发表了划时代论文《通信的数学原理》（ A Mathematical Theory of Communication ），创立了信息论，开启了信息时代。在经典的信息论通信系统模型（图2-3）中，消息发送方通过信源编码实现数据压缩，通过信道纠错编码实现错误检测和纠正，以抵抗信道中的噪声干扰，从而有效保证通信的可靠性。
·图2-3 通信系统模型
纠错编码的一般思路是在信息比特流中，增加冗余信息位，从而使得接收方能够检测信息传输中发生的错误且在一定范围内纠正这些错误而无须重新传输。纠错编码的应用在日常生活中随处可见，如我国居民身份证码采用18位数字（图2-4），其中最后一位为冗余校验位（X代表数字10）。18位居民身份证号码从左至右记为 a 1 ， a 2 ，…， a 17 ， a 18 ，前6位 a 1 — a 6 为地址码，代表居民首次获得身份证号码时所在县（市、旗、区）的行政区划代码；中间8位 a 7 — a 14 为出生日期码，代表居民出生日期； a 15 — a 17 这3位数字为顺序码，代表同地址码同出生日期码的居民编定的顺序码，其中奇数分配给男性，偶数分配给女性；最后一位 a 18 为校验码，采用ISO 7064：1983.MOD 11-2检验码系统，由前17位数字计算得出。
·图2-4 我国居民身份证号码示意图
具体来说，最后一位校验码 a 18 由以下公式计算得出：
其中mod表示求余运算。以上公式中mod 11意为除以11求余数，因此可理解为什么身份证最后一位数字可能为X，即mod 11得到余数为10。读者可思考：通过这样一位校验码，身份证号是否可检测一位数字错误？是否可检测两位数字错误甚至更多错误呢？为什么？
在香农信息论中，通过有噪信道编码定理可知，如果使用有效的信道纠错编码使得误码率为零，那么在该通信信道上传输信息理论上所能达到的最大信息传输速率，即信道容量。但该信道编码定理无法构造具体的纠错编码，纠错编码研究的核心问题是如何构造算法高效、接近信道容量速率且无错误传输信息的纠错编码。历史上第一个系统的纠错编码构造由理查德·汉明（Richard W. Hamming）提出，称为汉明码。20世纪40年代末，汉明在著名的贝尔实验室用贝尔V型电脑工作，输入端是通过打孔卡读入数据，经常会造成读取错误。在上班时间，当有读取错误发生时，工作人员可手动解决错误，但在下班时间，机器只会简单地将错误转移到下一个任务。为了解决这一问题，汉明于1950年构造了汉明码，可纠正1位错误，开创了纠错编码领域，极大推动了数字通信、存储系统等领域的发展。
下面我们介绍（7，4）汉明码（图2-5），即编码信息比特串长度为4，增加3位冗余比特，编码比特串长度为7。假设4位信息比特串分别记为 x 1 ， x 2 ， x 3 ， x 4 ，3位冗余校验比特串分别记为 p 1 ， p 2 ， p 3 。
·图2-5 （7，4）汉明码冗余校验图示
3个冗余校验位等式分别为：（a） p 1 = x 1 + x 2 + x 4 ，（b） p 2 = x 1 + x 2 + x 3 ，和（c） p 3 = x 2 + x 3 + x 4 ，以上加法为mod 2求余加法，即异或运算。当4位信息比特串为 x 1 x 2 x 3 x 4 时，由上述三个冗余校验位等式，添加3位冗余校验比特串得到长度为7的比特串 x 1 x 2 x 3 x 4 p 1 p 2 p 3 。
下面我们分情况讨论一位比特发生错误将出现的所有情形：
（1）比特位 x 1 发生错误，则（a）（b）校验不通过；
（2）比特位 x 2 发生错误，则（a）（b）（c）校验不通过；
（3）比特位 x 3 发生错误，则（b）（c）校验不通过；
（4）比特位 x 4 发生错误，则（a）（c）校验不通过；
（5）比特位 p 1 发生错误，则（a）校验不通过；
（6）比特位 p 2 发生错误，则（b）校验不通过；
（7）比特位 p 3 发生错误，则（c）校验不通过。
由上述讨论可知，一位比特发生错误的所有7种情形两两互不相同，因此如果1位比特发生错误，可明确定位这个错误位并翻转纠正。事实上可以证明，任意长度为4的信息比特串，通过上述3个冗余校验位等式完成编码得到的长度为7的比特串，两两之间的最小距离为3。如图2-6所示，每个点代表一个码字，皆是长度为7的比特串，共有2 7 =128个；黑点代表所有正确的码字共2 4 =16个；绿点代表发生1位错误得到的所有码字；红点代表发生多于1位错误得到的所有码字。
·图2-6 汉明码纠错图示
理想情况下，信息传递不发生错误，即黑点代表的码字在接收方无错误接收，无须纠错。其他情形如下：
情形（i）：发生较少错误，即1位错误，接收方得到绿色码字，还原成其最接近（汉明距离最小）的黑色码字，此时可正确译码；
情形（ii）：发生多于1位错误，接收方得到红色码字，无法确定如何还原码字，此时可检测出错误，但无法纠正错误；
情形（iii）：发生更多位错误，接收方得到距原码字较远的绿色码字，还原成另外一个黑色码字，此时错误译码；
情形（iv）：接收方得到与原码字不同的黑色码字，此时错误无法检测。
汉明码是一种线性码，即所有码字构成 n 维有限向量空间中的维数为 k 的线性子空间，冗余位数 r = n - k ，汉明码的码长为 n =2 r -1，维数为 k =2 r - r -1，最小距离即任意两码字的最小汉明距离为 d =3。汉明码是一种完备码，它的参数能达到参数相互制约的理论界（汉明界），即在码长相同、最小距离为3的纠错码中能达到最高的码率。线性码通常具有高效的编码与译码算法，因而在实际通信、存储系统中广泛应用，如里德-所罗门（Reed-Solomon）码广泛应用于卫星通信、DVD光盘、磁盘存储等系统中，低密度奇偶校验码（low density parity check code，LDPC）、极化码（polar code）分别是5G通信中数据信道和控制信道的纠错编码标准。汉明码是一种分组纠错码，即编码码字长度是固定的，与之不同的另外一类纠错码是卷积码（convolutional code），它具有信道的记忆性质，通常通过增加存储器阶数来实现低误码率。涡轮码（turbo code）是一种著名的卷积码，由于其高效的Viterbi译码算法而被广泛应用于3G/4G通信、深空卫星通信中。
南方科技大学计算机科学与工程系长聘副教授，博士生导师。2007年于中国科学技术大学信息安全专业获学士学位；2011年于香港科技大学计算机科学与工程系获博士学位；2011—2013年受德国洪堡基金会资助于德国马格德堡大学数学学院做洪堡学者。入选深圳海外高层次人才、南山区“领航人才”。主要研究纠错编码、密码学及应用等，在国际知名期刊和会议发表论文50余篇，主持多项国家级项目。