第二讲 码制
※ 检错码和纠错码 ※
《数字电子技术基础》
第二讲 码制
█ 误差检验码(Error-detecting Codes)
由于存在干扰，二进制信息在传输过程中会出现 错误。为发现并纠正错误，提高数字设备的抗干扰能 力，必须使代码具有发现错误并纠正的能力，这种代 码称为误差检验码（ Error-detecting Codes ）。 最常用的误差检验码为奇偶校验码。它的编码方 法是在信息码组外增加一位监督码元，增加监督码元 后，使得整个码组中“1”码元的数目为奇数或为偶数。 若为奇数，称为奇校验码(Odd parity)；若为偶数， 称为偶校验码(Even parity)。
《数字电子技术基础》
第二讲 码制
表1
8421BCD码奇偶校验码示例
奇校验码 1 0000 0 0001 0 0010 1 0011 0 0100 1 0101 1 0110 0 0111 0 1000 1 1001 偶校验码 0 0000 1 0001 1 0010 0 0011 1 0100 0 0101 0 0110 1 0111 1 1000 0 1001 《数字电子技术基础》
信息码 0 1 2 3 4 5 6 7 8 9 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001
第二讲 码制
◆ 奇/偶校验码工程示例：
数据发送端 数据接收端
偶校验
01001 00101 10111…
01001 00100 10111… Error!
《数字电子技术基础》
图1 奇偶校验码工程示例
第二讲 码制
◆ 奇偶校验码的特点：
★ 奇偶校验码可以检测单向单错。
★ 奇偶校验码中，信息码和校验码是可以分 离的，故称为可分离码。 ★ 无需任何附加电路可以从收到的奇偶校验码 中取得信息码，从而简化了译码过程。
《数字电子技术基础》
第二讲 码制
█ 误差纠错码(Error-correcting Codes)
汉明距离（ HammingDistance Distance ）—— 汉明距离（ Hamming ）—— 汉明距离是指两个等长字符串对应位置的字符不同的 个数，即将一个字符串变换成另外一个字符所需要替换的 字符个数。 汉明码（ HammingCode Code ）—— 汉明码（ Hamming ）—— 汉明码是一个在原有数据中插入若干校验码来进行错 误检查和纠正的编码技术。
《数字电子技术基础》
第二讲 码制
◆ 考察8421BCD码
各代码间的最小Hamming距离为1，这种编码没有 检错功能。 例： ‘1001’?’0001’
◆ 考察表1所示8421BCD码奇偶校验码
各代码间的最小Hamming距离为2，这种编码具有 检测单向单错的功能。 例： ‘11001’?’10001’
《数字电子技术基础》
第二讲 码制
◆ 考察表2所示编码表
表2中各代码间的最小Hamming距离为3，这种编码不 但能检测到错误，而且在一定条件下可以获得纠错功能。 例： ‘00111’?’10111’ 表2 一种纠错码示例 信息码 00 01 10 11 校验码 111 010 001 100 由此可见：增加各合法代码 间的Hamming距离，将可以 提高检错能力，而且可以获 得纠错功能。建立在这一基 础上的纠错码叫做Hamming 纠错码。
《数字电子技术基础》
最小码距和检错纠错能力关系 一、码距？ 码距就是两个码字C1与C2之间不同的比特数。如：1100与1010的码距为2;1111与0000的码距为4。 一个编码系统的码距就是整个编码系统中任意(所有)两个码字的最小距离。若一个编码系统有四种编码分别为：0000，0011，1100，1111，此编码系统中0000与1111的码距为4;0000与0011的码距为2，是此编码系统的最小码距。因此该编码系统的码距为2。 二、码距和检错纠错有何关联? 首先大家要了解以下两个概念： 1.在一个码组内为了检测e个误码，要求最小码距应该满足：d>=e+1 2.在一个码组内为了纠正t个误码，要求最小码距应该满足：d>=2t+1 现在举个例子来说明这个问题： 假如我们现在要对A，B两个字母进行编码。我们可以选用不同长度的编码，以产生不同码距的编码，分析它们的检错纠错能力。 ||-- 若用1位长度的二进制编码。若A=1，B=0。这样A，B之间的最小码距为1。 合法码：{0,1｝;非法码：{0,1｝; 根据上面的规则可知此编码的检错纠错能力均为0，即无检错纠错能力。其实道理很简单，这种编码无论由1错为0，或由0错为1，接收端都无法判断是否有错，因为1，0都是合法的编码。 ||-- 若用2位长度的二进制编码，可选用11，00作为合法编码，也可以选用01，10作为合法编码。若以A=11，B=00为例，A、B之间的最小码距为2。 合法码：{11,00｝;非法码：{01,10｝; 根据上面的规则可知此编码的检错位数为1位，无法纠错。因为无论A(11)或B(00)，如果发生一位错码，必将变成01或10，这都禁用码组(非法码)，故接收端可以判断为误码，却不能纠正其错误。因为无法判断误码(01或10)是A(00)错误还是B(11)错误造成，即无法判断原信息是A或B，或说A与B形成误码(01
3.2差错控制 3.2.2常用的检错码- 奇偶校验码 奇偶校验码是一种简单的检错码，奇偶校验码分为奇校验码和偶校验码，两者原理相同。它通过增加冗余位来使得码字中“1”的个数保持奇数或偶数。 ?无论是奇校验码还是偶校验码，其监督位只有一位； ?假设信息为为I1, I2, …, I n，对于偶校验码，校验位R可以表示为： R =I 1 ⊕I 2 ⊕Λ⊕I n ?假设信息为为I1, I2, …, I n，对于奇校验码，校验位R可以表示为： R =I 1 ⊕I 2 ⊕Λ⊕I n ⊕1 ?无论是奇校验码还是偶校验码，都只能检测出奇数个错码，而 不能检测偶数个错码。 4 4
讨论： 从检错能力、编码效率和代价等方面来评价垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验 3.2 差错控制 3.2.2 常用的检错码 - 奇偶校验码 奇偶校验在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。 5
3.2.2常用的检错码–定比码 所谓定比码，即每个码字中“1”的个数与“0”的个数之比保持恒定， 故又名等比码或恒比码。 ?当码字长一定，每个码字所含“1”的数目都相同，“0”的数目也 都相同。 ?由于若n位码字中“1”的个数恒定为m，还可称为“n中取m”码 定比码（n中取m）的编码效率为： log C m R = ?2 n n 定比码能检测出全部奇数位错以及部分偶数位错。实际上，除了码 字中“1”变成“0”和“0”变成“1”成对出现的差错外，所有其它差 错都能被检测出来 6 4
代码“1011011”对应的多项式为x 6 + x 4 + x 3 +1 多项式“x 5 + x 4 + x 2 + x”所对应的代码为“110110” 3.2.2 常用的检错码 – 循环冗余检验 循环冗余码（Cyclic Redundancy Code ，简称CRC ）是无线通信中用得最广泛的检错码，又被称为多项式码。 二进制序列多项式：任何一个由m 个二进制位组成的代码序列都可以和一个只含有0和1两个系数的m-1阶多项式建立一一对应的关系。 CRC 有关的多项式： ? 信息位多项式、冗余位多项式、码字多项式、和生成多项式 信息位1010001：K (x ) = x 6 + x 4 + 1 冗余位1101：R (x ) = x 3 + x 2 + 1； 码字10100011101： T (x ) = x 10 + x 8 + x 4 + x 3 + x 2 + 1 7
计算机网络检错码与纠错码 在通信系统中广泛应用的差错控制技术是差错控制编码技术。而差错控制编码包括检错码和纠错码两种，其中检错码是为传输的数据信号增加冗余码，以便发现数据信号中的错码，但不能纠正错码；纠错码是为传输的数据信号增加冗余码，以便发现数据信号中的错码，并自动纠正这些错码。下面介绍几种检错码和纠错码的校验方法。 1．奇偶校验码 奇偶校验码是一种最简单的无纠错能力的检错码，其编码规则是先将数据代码分组，例如，将ASCⅡ码中的一个字符或若干个字符分为一组。在各组数据后面附加一位校验位，使该数据连校验位在内的码元中1的个数恒为偶数则为偶校验，恒为奇数则为奇校验。奇偶校验无纠错能力，它只能检测出码元中的任意奇数个错误，若有偶数个错误必定漏检。由于奇偶校验码容易实现，所以当信道干扰较弱，并且数据码长较短时，使用奇偶校验码效果很好，在计算机网络的数据传输中经常使用该检错码。 根据数据代码的分组方法，奇偶校验码可以分为水平奇偶校验、垂直奇偶校验和垂直水平奇偶校验。 ●水平奇偶校验 如表3-1所示，在水平奇偶校验中，把数据先以适当的长度划分成小组，并把码元按表中所示的顺序一列一列地排列起来，然后对水平方向的码元进行奇偶校验，得到一列校验位，附加在其他各列之后，最后按行的顺序进行传输。水平奇偶校验能查出水平方向上奇数个错误和不大于数据代码长度的突发错误，无纠错能力，但产生校验码及校验逻辑相对复杂。 表3-1 水平奇偶校验 ●垂直奇偶校验 如表3-2所示，在垂直奇偶校验中，把数据先以适当的长度划分成小组，并把码元按表中所示的顺序一列一列地排列起来，然后对垂直方向的码元进行奇偶校验，得到一行校验位，附加在其他各行之后，然后按列的顺序进行传输。垂直奇偶校验能够查出列上的奇数个错误，只能查处50%的突发错误，无纠错能力，但产生校验码及校验逻辑相对简单。 表3-2 垂直奇偶校验
一、常用检错码 (1) 寄偶校验码 寄偶校验码是一种最简单的校验码，其编码规则：先将所要要传送的数据码元分组，并在每组的数据后面附加一位冗余位即校验位，使该组包括冗余位在内的数据码元中“1”的个数保持为奇数（奇校验）或偶数（偶校验）。在接收端按照同样的规则检查，如发现不符，说明有错误发生；只有“1”的个数仍然符合原定的规律时，认为传输正确。实际数据传输中所采用的寄偶校验码分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验三种。 垂直奇偶校验是一字符为单位的校验方法。例如，传输数据信息为“1010001”，采用偶校验时，附加位为“1”，则发送信息变为“10100011”；采用奇校验时，附加位为“0”，发送信息变为“10100010”； (2) 循环冗余校验码（CRC） 循环冗余校验码CRC（Cyclic Redundancy Code）采用一种多项式的编码方法。把要发送的数据位串看成是系数只能为“1”或为“0”的多项式。一个k位的数据块可以看成Xk-1到X0的k项多项式的系数序列。例如，“110001”有6位，表示多项式是“X5 + X4+ 1”。多项式的运算是模2运算。 采用CRC码时，发方和收方必须事先约定一个生成多项式G（X），并且G（X）的最高位和最低必须是1。要计算m位数据块的M（X）的校验和，生成多项式必须比该多项式短。其基本思想是：将校验和附加在该数据块的末尾，使这个带校验和的多项式能被G（X）除尽。当接收方收到带校验和的数据块时，用G（X）去除它，如果有余数，则传输有错误。 二、纠错码 纠错码与检错码相比其功能更强，它不但能检错还能纠错。海明码就是一种能够纠正一位错误的检错码。海明码是海明(H.W.Hamming)于1950年提出的一种码制。在发送数据之前将数据按照海明码制形成海明码，然后发送海明码，到达对方后根据接收到的海明码进行解释分析、判错、纠错。 (1) 海明码的形成 ①海明码的组合规则 海明码是由数据与校验位组合而成的。其组合规则为：将数据与校验码（寄偶校验）自左至右进行编码，其中编号为2的幂的位均为校验位，其余为数据位。 ②校验位值的确定 将每一数据位的编号展开成2的幂的和（每一项不可重复），则每一项所对应的位均为该数据位的校验位。据此，按照寄偶校验规则确定各校验位的值。 例：要传送的数据为“11001100” 则相应的海明码为：AB1C100D1100 其中A、B、C、D是加入的校验位。 将每一数据位的编号展开成2的幂的和： 3=2+1 9=8+1
第二节 纠错编码原理 一、纠错编码的原理 一般来讲，信源发出的消息均可用二进制信号来表示。例如，要传送的消息为A 和B ，则我们可以用1表示A ，0表示B 。在信道传输后产生了误码，0错为1，或1错为0，但接收端却无法判断这种错误，因此这种码没有任何抗干扰能力。如果在0或1的后面加上一位监督位（也称校验位），如以00表示A ，11表示B 。长度为2的二进制序列共有种组合，即00、01、10、11。00和11是从这四种组合中选出来的，称其为许用码组，01、10为禁用码。当干扰只使其中一位发生错误，例如00变成了01或10，接收端的译码器就认为是错码，但这时接收端不能判断是哪一位发生了错误，因为信息码11也可能变为01或10，因而不能自动纠错。如果在传输中两位码发生了错误，例如由00变成了11，译码器会将它判为B ，造成差错，所以这种1位信息位，一位监督位的编码方式，只能发现一位错误码。 224=按照这种思路，使码的长度再增加，用000表示A ，111表示B ，这样势必会增强码的抗干扰能力。长度为3的二进制序列，共有8中组合：000、001、010、011、100、101、110、111。这8种组合中有三种编码方案：第一种是把8种组合都作为码字，可以表示8种不同的信息，显然，这种编码在传输中若发生一位或多位错误时，都使一个许用码组变成另一个许用码组，因而接收端无法发现错误，这种编码方案没有抗干扰能力；第二种方案是只选四种组合作为信息码字来传送信息，例如：000、011、101、110，其他4种组合作为禁用码，虽然只能传送4种不同的信息，但接收端有可能发现码组中的一位错误。例如，若000中错了一位，变为100，或001或010，而这3种码为禁用码组。接收端收到禁用码组时，就认为发现了错码，但不能确定错码的位置，若想能纠正错误就还要增加码的长度。第三种方案中规定许用码组为000和111两个，这时能检测两位以下的错误，或能纠正一位错码。例如，在收到禁用码组100时，若当作仅有一位错码，则可判断出该错码发生在“1”的位置，从而纠正为000，即这种编码可以纠正一位差错。但若假定错码数不超出两位，则存在两种可能性，000错一位及111错两位都可能变为100，因而只能检错而不能纠错。 从上面的例子可以得到关于“分组码”的一般概念。如果不要求检错或纠错，为了传输两种不同的信息，只用1位码就够了，我们把代表所传信息的这位码称为信息位。若使用了2位码或3位码，多增加的码位数称为监督位。我们把每组信息码附加若干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。 图8-2分组码的结构 分组码一般用符号(表示， 其中k 是每组码中信息码元的数目，n 是码组的总位数，又称为码组的长度（码长），为每码组中的监督码元数目，或称为监督位数目。通常将分组码规定为如图8-2所示的结构，图中前面位为信息位，后面附 )n n a a ??,n k n k r ?=k 12(,,...,)r a
上 海 理 工 大 学
计 算 机 工 程 学 院
实 验 报 告
实验名称 课程名称 数据链路层－检错与 纠错 计算机网络
学号 992A328B 地点 计算机信息中心 教师 陈家琪
姓名 朱文贵 日期 2002.11.5 成绩
备注：
第1页 共5页
上海理工大学计算机工程学院
实验报告
第2页 共5页
1.实验目的
⑴ 通过《海明编码》演示软件，验证纠错与检错功能和性能，掌握其工作原理； ⑵ 编写海明编码程序和 CRC 编码程序；
2.实验环境（软件、硬件及条件）
⑴ Windws9x/NT/2000/XP ⑵ TCP/IP 协议 （编程工具：Visual C++ 6.0，C++ Builder 或 其它）
3.实验方法
运行《CRC 编码》演示软件 ⑴ 验证纠错能力； ⑵ 验证检错能力； ⑶ 若数据＝10011001，海明编码＝？，校验位=? ⑷ 若接收端收到的信息＝101010101001（海明编码） ，数据＝？ ⑸ 尝试编写海明编码的程序。
4.实验分析
参考
5.实验结论
通过实验表明海明码是一种可纠正一位错的编码方法。 用 r 个校验位构造出 r 个校验关系式来指示一位错码的 n(=m+r)种 可能位置及表示无差错。 码字排列：从最左边位开始依次编号（1，2，….，n） ； k r 个校验位：在 2 的位置（1，2，4，8…..） ； m 个数据位：在其余位（3，5，6，7…..） 。 r 的确定：r2-r>=m+1； 如果海明距 d>=2t+1,则该编码可纠正任何 t 个（或 t 个以下）的错 误。 如果 d>=e+1,则该编码可检测出任何 e 个（或 e 个以下）的错误。
-2-
奇偶校验码 2.5.2 奇偶校验码 奇偶校验码是一种通过增加冗余位使得码字中"1"的个数恒为奇数或偶数的编码方法,它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。 1.垂直奇偶校验 垂直奇偶校验又称为纵向奇偶校验,它是将要发送的整个信息块分为定长p位的若干段(比如说q段),每段后面按"1"的个数为奇数或偶数的规律加上一位奇偶位,如图2.19所示。问位信息(I11,I21,…,Ipl,I12,…,Ipq) 中,每p位构成一段(即图中的一列),共有q段(即共有q列〉。每段加上一位奇偶校验冗余位,即图中的rio编码规则为 注意:此间的"+"指的是模二加,也即异或运算。 图中箭头给出了串行发送的顺序,即逐位先后次序为 I11,I21,…,Ip1,r1,I12,…,Ipa,r2,…,儿,…,I间,rq。在编码和校验过程中,用 硬件方法或软件方法很容易实现上述连续半加运算,而且可以边发送边产生冗余位;同样,在接收端也可边接收边进行校验后去掉校验位。 垂直奇偶校验方法的编码效率为R=p/(p+1)。通常,取一个字符的代码为一个 信息段,这种垂直奇偶校验有时也称为字符奇偶校验。例如,在8位字符代码(即用8位二进制数位表示一个字符)中,p=8,编码效率便为8/9。 垂直奇偶校验方法能检测出每列中的所有奇数位错,但检测不出偶数位的错。对于突发错误来说,奇数位错与偶数位错的发生概率接近于相等,因而对差错的漏检率接近于1/20。 2.水平奇偶校验 为了降低对突发错误的漏检率,可以采用水平奇偶校验方法。水平奇偶校验又称为横向奇偶校验,它是对各个信息段的相应位横向进行编码,产生一个奇偶校验冗余位,如图2.20所示,编码规则为 若每个信息段就是一个字符的话,这里的q就是发送的信息块中的字符数。 水平奇偶校验的编码效率为R=q/(q+1)。 水平奇偶校验不但可以检测出各段同一位上的奇数位错,而且还能检测出突发长度
第八章线性分组码 8.1 什么是检错码？什么是纠错码？两者有什么不同？ 答：能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。 8.2 试述分组码的概念，并说明分组码的码率r的意义。 答：分组码是把信息序列以每k个码元分组，即每k个码元组成一个信息组。n表示码长,k 表示信息位的数目，码率r=k/n，它说明在一个码字中信息为所占的比重。 8.3 什么是码的生成矩阵和校验矩阵？一个（n，k）线性分组码的生产矩阵和校验矩阵各是几行几列的矩阵？ 答：线性分组码的2个码字将组成n维向量空间的一个k维子空间，而线性空间可由其基底张成，因此线性分组码的个码字完全可由k个独立的向量组成的基底张成。设k个向量为 （7.3-2） 将它们写成矩阵形式： （7.3-3） （n,k）码中的任何码字，均可由这组基底的线性组合生成。即 C=MG=(mk-1,mk-2,m0)G 式中 M=(mk-1,mk-2,m0)是k个信息元组成的信息组。这就是说，每给定一个信息组，通过式（7.3-3）便可求得其相应的码字。故称这个由k 个线性无关矢量组成的基底所构成的k×n阶矩阵G为码的生成矩阵（Generator Matrix）。
校验矩阵H 的每一行代表求某一个校验位的线性方程的系数(n-k)线性分组码有r=n-k 个校验元，故须有r 个独立的线性方程，因此H 矩阵必由线性无关的r 行组成，是一个(n-k)×n 阶矩阵，一般形式为 一个（n,k ）线性分组码生成矩阵有k 行n 列校验矩阵有(n-k)行n 列。 8.4 什么样的码成为系统码？系统码的生成矩阵和校验矩阵在形式上有何特点？ 答：若信息组为不变的形式，称在码字的任意k 位中出现的码为系统码；一个系统码的生成矩阵G ，其左边k 行k 列是一个k 阶单位方阵，系统码的校验矩阵H ，其右边r 行r 列组成一个r 阶单位方阵。 8.5 什么是对偶码？试举例说明之。 答：若把（n,k ）码的H 矩阵看成是(n,r)码的生成矩阵Gd,而（n,k ）码的G 矩阵就是（n,r ），码的校验矩阵Hd,则称这两种码为互为对偶码。例如课本列举的（7，3）码 8.6 试述码的距离和重量的概念。线性分组码的最小距离有何实际意义？ 答：两个码字之间，对应位取值不同的个数，称为它们之间的汉明距离，简称距离用d(c1,c2)表示。码字中非零码元的个数，称为该码子的汉明重量，简称重量，用w(c)表示。一个线性分组码的最小距离是衡量码抗干扰能力的重要参数。码的最小距离愈大，其抗干扰能力愈强。 8.7 如果要构造一个能纠2个错的线性分组码，则其H 矩阵中至少应保证多少列线性无关？ 答：4列 根据定理8.2检测e 个错，则要求码的最小距离d 大于等于e+1 纠正t 个错，则要求码的最小距离d 大于等于2t+1 纠正t 个错误同时检测e 个错误，则要求d 大于等于t+e+1 而根据定理8.3 （n,k ）线性分组码有最小距离为d 的重要条件是H 矩阵中任意d-1列线性无关 所以是4列 8.8 什么是接收序列y 的伴随式s ？为什么伴随式s 只由错误图样e 决定？ 答：令 ? ? ??? ?? ?????---------0,2 ,1 ,0,22,21,20,12,11,1..................,...k n n k n n k n n n n n h h h h h h h h h ????? ???????11 01000 011010011100101010001Gd=H= T T eH yH s ==
数据加密与校验纠错码相结合的一点尝试 陈晓蕾 （单位：苏州市工业园区娄葑学校 215001） 摘要：数据加密及校验纠错方法很多，但往往都是独立处理的。针对此问题，本文阐述了一种数据加密与校验纠错相结合进行数据加工的方法。 一、引言 随着因特网的日益普及，网络信息在人类社会生产实践中扮演着越来越重要的角色，越来越多地影响着人们生活的各个方面，网络信息安全问题自然上升到一个前所未有的高度，引起了所有人的关注。任何信息发生意料之外的泄露，都将引起一连串的烦恼与错误。小至个人隐私的名誉受损，大至商业机密的恶意窃取，都使得数据的传输在方便、快捷之余增添了无穷无尽的担忧与忐忑。因此，数据加密成为必不可少的一道关卡。 数据加密给数据加工增加了许多负担，然而，为使重要数据得到更为稳妥的处置，加密解密工作将更加繁杂。如何使加密、解密工作以最小的消耗来获得最佳的效果，成为很多人孜孜以求的目标。本文在简介密码学的一般常用方法后，重点阐述笔者关于加密与校验相结合的一点思考，旨在对数据加密的同时尽量简化一些并非必要的工作，使总工作量得以减少。 二、密码学常用加密方法 众所周知，加密是在与窃密的斗争中反复改进，不断成长的。一方面是越来越高的加密要求，而另一方面则是紧随其后的窃密破坏，迫使加密的手段也日趋专业化、系统化，以应付越来越刁钻的窃密手法。 最初的加密简单而直接，经历了替代和换位两个阶段。 1、替代密码 替代密码通过对原文经过一系列替代处理后形成新的码文，以达到加密的要求。接受方再经过相应的反处理即可恢复成原文。 举例来说，要传输一个商定的会晤日期20020212，可以通过逐位加1乘2再加3的步骤获得密文95595979。密文的接收方则可在受到密文后，用事先商定好的减3除2再减1的方法来获取原文。 这种方法过于简单，极易泄密。窃密者在观察截获的密文时不难发现，前四位年份呈对称性，有可能的不是2002就是1991，则密文可翻译成200202？2或
浅析信道编码检错纠错的原理及方法 【摘要】信道编码在信息码元中插入一些冗余码元（监督码元），使得整体码元具有一定规律。当出现传输错误时，可以通过规律，对错误进行检测乃至纠正。 【关键词】信道编码；检错纠错；信息码元 在数字通信中，噪声的存在使得最终恢复出的基带信号出现误码。在数字通信中可以依据这样一类方法来减少数据错误：将发送的数字信号码元序列按照某种规则进行编码，使得新的码元序列具有一定的规律。这样接收方能够根据编码的规则，对收到的信号码元组进行检测，从而发现或者纠正数据传输中出现的误码。这便是信道编码，又叫差错控制编码、纠错编码、抗干扰编码或可靠性编码等。这些名称分别体现了信道编码某一方面的特点：编码是为了增强信号在信道中传输的可靠性，也是为了控制码元差错，可以对干扰造成的误码进行检错和纠错。 1 信道编码的概述 信道编码检错和纠错的基本思路是按某种规则在传输的码元序列之中，附加一些冗余的码元。这些冗余码元的取值与原来包含初始信息的码元取值有关。由于插入了冗余码元，原本只是单纯传输信息的码元序列便具有了特定的规律，而这些冗余码元也就对信号起到了监督作用。当数据传输中出现错误时，误码可能会破坏信道编码的规律，这样接收方就能发现错误，即检错；有些情况下，还能根据传输到的错误码组和编码规律，推断出原正确码元组，即纠错。因此，这些冗余码元又被称为“监督码元”。 2 信道编码的分类 按照不同功能分为检错码、纠错码和纠删码。检错码只具备检查码组错误的功能；纠错码还能对部分错误进行纠正。纠删码对超出纠错范围的误码能将其删除。 按照纠正错误的类型不同，分为纠正随机错误的码和纠正突发错误的码。随机错误的误码从统计上是彼此独立的，同一个码组内发生若干个码元错误的概率远远低于只有一两个码元错误的概率。这意味着信道编码哪怕只纠正每个码组内一两个码元错误，也可使得整个系统的误码率大幅度下降。但有时信道中出现强度大，持续时间长的脉冲噪声，使连串的码元受到干扰，称为突发错误。例如连续若干位的0变成1。这时必须用专门针对突发错误信道编码方式。 按照信息码元和监督码元之间的制约规则不同，分为分组码和卷积码。分组码是指在每一组码元（k位信息码元和r位附加监督码元）中，所有的监督码元取值，仅仅与这一组的k位信息码元有关，而与其他组的信息码元无关。分组码
毕业论文任务书 注：一式三份，系、指导教师、学生各一份，由指导教师填写。
对论文“数据检错和纠错的主流方法（Main methods for data error detection and correction）”的指导意见 ◆要求：撰写一万字左右的论文，论述数据检错纠错技术的主流方法。 ◆主要内容： 数据存储和数据通信中的检错和纠错方法很多，其中奇偶校验、hamming校验和循环冗余校验(CRC)是主流。论文的内容是叙述和分析各种校验的原理，比较各自的优缺点。各自应用的场合。 ◆论文撰写步骤（仅为建议，供参考）： 1、在已有知识基础上，参阅文献，深入理解纠错检错方法。你应认识的知识是：a.奇偶校 验原理。该校验简单易行、廉价。但只可以检错，不能判断错位及纠错，所以用在简单场合，如慢速串行通信，要求不高的存储器等；b. hamming校验原理。该校验为什么检错能力强且可纠错。该校验编码和解码程序简单，纠错方便，但存储资源消耗较大，适合在存储校验如磁盘阵列RAID II存储系统；c. CRC校验原理：搞懂一个二进制数为何可表为一个以2为底的多项式，如1011011 = 1X6+0X5+1X4+1X3+0X2+1X1+1X0；搞懂生成多项式；模二加、模二除等运算。该校验特点是信息字段和校验字段的由人选定，检错和纠错功能很强，可以使用硬件纠错。CRC多用于磁表面存储和数据通信。这方面的知识网上很多（可供参考但不可作文献引用）。 2、草稿：a.罗列你可以搜罗到的各种数据检错纠错方法；b.指明在计算机领域主流检错纠 错方法是奇偶校验、hamming校验、循环冗余校验(CRC)；c.分别叙述它们的原理、校验方法。文中必须有必要的图、表；d. 比较它们的优缺点，指出在什么场合实用；e.你的论文结论，即为什么在某种场合下最适合用某一种方法。你也可以有自己的看法，例如你可某种检错纠错法有更可观的前景。等等。 3、论文的整理，定稿。中外文摘要。 （注意以上仅为提要，论文详细内容你要仔细充实） ◆可供查阅的参考文献：（仅为建议，可更多或更少不限） [1] 罗克露、单立平等：计算机组成原理. 北京：电子工业出版社 2005 [2]毛爱华. 计算机组成原理.北京:冶金工业出版社,2005 [3](美)William Stallings，张昆藏译. 计算机组织与结构（新版）电子工业出版社 [4]俸远禛、王正智等：计算机组成原理与汇编语言程序设计电子工业出版社 1997 [5]王爱英.计算机组织与结构.北京:清华大学出版社,2005 [6]章鸿献. 微软计算机辞典（英汉双解）.北京:清华大学出版社,2003 [9]数据通信或通信原理方面的书籍和期刊
1. 检错纠错的有关概念和实现思路 数据在计算机系统内加工、存取和传送的过程中可能产生错误。为减少和避免这类错误，一方面是精心选择各种电路，改进生产工艺与测试手段，尽量提高计算机硬件本身的可靠性；另一方面是在数据编码上找出路，即采用带有某种特征能力的编码方法，通过少量的附加电路，使之能发现某些错误,甚至能准确地确定出错位置,进而提供自动纠正错误的能力。 数据校验码就是一种常用的带有发现某些错误、甚至带有一定自动改错能力的数据编码方法。它的实现原理，是在合法的数据编码之间，加进一些不允许出现的(非法的)编码，使合法数据编码出现某些错误时，就成为非法编码。这样,则可以通过检查编码的合法性来达到发现错误的目的。合理地设计编码规则，安排合法、不合法的编码数量，就可以得到发现错误的能力，甚至达到自动改正错误的目的。这里用到一个码距（最小码距）的概念。码距是指任意两个合法码之间至少有几个二进制位不相同，仅有一位不同，称其（最小码距）为1，例如用四位二进制表示16种状态，则16种编码都用到了，此时码距为1，就是说，任何一个编码状态的四位码中的一位或几位出错，都会变成另一个合法码，此时无检错能力。若用四个二进制位表示8种合法状态，就可以只用其中的8个编码来表示之，而把另8种编码作为非法编码，此时可使合法码的码距为2。一般说来，合理地增大编码的码距,就能提高发现错误的能力，但表示一定数量的合法码所使用的二进制位数要变多，增加了电子线路的复杂性和数据存储、数据传送的数量。在确定与使用数据校验码的时候，通常要考虑在不过多增加硬件开销的情况下，尽可能地发现较多的错误，甚至能自动改正某些最常出现的错误。常用的数据校验码是奇偶校验码、海明校验码、循环冗余校验码等。纠错编码是对检错编码的更进一步的发展和应用。 计算机内经常遇到的错误有两大类，随机错误和突发错误。前者指孤立出现的一个错误，后者指连续产生的一批（彼此之间可能有关联）错误。对它们处理的难度和复杂度会有很大不同，在我们的课程中基本不涉及对突发错误的检查与纠正问题，有兴趣者请自行查阅有关资料。对纠错编码的分类方案给在图2.1。 图2.1 纠错码的分类
最近在实习期间需要用到数据的校验，所选为CRC16，那么就在此总结一番吧。 现在此说明下什么是CRC：循环冗余码校验英文名称为Cyclical Redundancy Check，简称CRC，它是利用除法及余数的原理来作错误侦测（Error Detecting）的。实际应用时，发送装置计算出CRC值并随数据一同发送给接收装置，接收装置对收到的数据重新计算CRC并与收到的CRC相比较，若两个CRC值不同，则说明数据通讯出现错误 那么其实CRC有比较多种，比如CRC16、CRC32 ，为什么叫16、32呢。在这里并非与位有和关系。而是由所确定的多项式最高次幂确定的。如下所示。理论上讲幂次越高校验效果越好。 CRC(12位) =X12+X11+X3+X2+X+1 CRC(16位) = X16+X15+X2+1 CRC(CCITT) = X16+X12 +X5+1 CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1 循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2R，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。 几个基本概念 1、多项式与二进制数码 多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。 多项式包括生成多项式G(x)和信息多项式C(x)。 如生成多项式为G(x)=x4+x3+x+1，可转换为二进制数码11011。 而发送信息位1111，可转换为数据多项式为C(x)=x3+x2+x+1。 2、生成多项式 是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。 在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。 应满足以下条件： a、生成多项式的最高位和最低位必须为1。 b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做模2除，应使余数循环。 将这些要求反映为数学关系是比较复杂的。但可以从有关资料查到常用的对应于不同码制的生成多项式如图9所示： N K 码距d G(x)多项式G(x) 7 4 3 x3+x+1 1011 7 4 3 x3+x2+1 1101 7 3 4 x4+x3+x2+1 11101
一、海明码检错/纠错基本思想 海明码（Hamming Code）是一个可以有多个校验位，具有检测并纠正一位错误代码的纠错码，所以也仅用于信道特性比较好的环境中，如以太局域网。它的检错、纠错基本思想如下： （1）将有效信息按某种规律分成若干组，每组安排一个校验位通过异或运算进行校验，得出具体的校验码 （2）在接收端同样通过异或运算看各组校验结果是否正确，并观察出错的校校组，或者多个出错的校验组的共同校验位，得出具体的出错比特位 （3）对错误位取反来将其纠正 二、海明码计算 海明码计算要按以下步骤来进行：计算校验码位数→确定校验码位置→确定校验码 1. 计算校验码位数 假设用N表示添加了校验码位后整个传输信息的二进制位数，用K代表其中有效信息位数，r表示添加的校验码位数，它们之间的关系应满足：N=K＋r≤2r－1（是为了确保r位校验码能校验全部的数据位，因为r位校验码所能表示的最大十进制数为2r-1，同时也确保各位码本身不被其他校验码校验） 信息码位数12~45~1112~2627~5758~120121~247 校验码位数2 3 4 5 6 7 8 2. 确定校验码位置 海明码的校验码的位置必须是在2n次方位置（n从0 开始，分别代表从左边数起分别是第1、2、4、8、16……），信息码也就是在非2n次方位置 3. 确定校验码 校验位置选择原则：第i位校验码从当前校验码位开始，每次连续校验i位后再跳过i位，然后再连续校验i位，再跳过i位，以此类推。确定每个校验码所校验的比特位： P1校验码位校验的码字位为：第1位（也就是P1本身）、第3位、第5位、第7位、第9位、第11位、第13位、第15位，……。 P2校验码位校验的码字位为：第2位（也就是P2本身）、第3位，第6位、第7位，第10位、第11位，第14位、第15位，……。 P3校验码位校验的码字位为：第4位（也就是P4本身）、第5位、第6位、第7位，第12位、第13位、第14位、第15位，第20位、第21位、第22位、第23位，……。 Pn校验码位校验的码字位为：第2n-1位（也就是Pn本身）、第2n-1+1位、第2n-1+2位、第2n-1+3位、……、第2n-1位，第3×2n-1位、第3×2n-1+1、……、第2×2n-1位，第5×2n-1位、第5×2n-1+1位、第3×2n-1位，……、第7×2n-1位、第7×2n-1+1位、……、第4×2n-1位，……，第(2m-1) 2n-1位、……第m×2n-1位 最后每组通过异或逻辑运算（与偶校验原理一样），使每组的运算结果为0，即可得出第i位校验码的值 4. 实现校验和纠错
计算机网络应用 检错码 检错码（error-detecting code ）是指为传输的数据信号增加冗余码，以便发现数据信号中的错误码，但不能纠正错误码的一种方法。 检错码一般是奇偶校验码（Parity Check Code ）、循环冗余校验码（Cyclic Redundancy Code ，CRC ），其主要用于在高度可靠的信道上，如光纤，当偶尔有错误发生时，只需重传整个数据块即可。 1．奇偶校验码 奇偶校验码是一种最简单的无纠错能力的检错码，其编码规则是先将数据代码分组，例如，将ASC Ⅱ码中的一个字符或若干个字符分为一组。在各组数据后面附加一位校验位，使该数据连校验位在内的码元中1的个数恒为奇数或偶数的编码方法。如果恒为偶数则称为偶校验，若恒为奇数则称为奇校验。 奇偶校验无纠错能力，它只能检测出码元中的任意奇数个错误，若有偶数个错误必定漏检。由于奇偶校验码容易实现，所以当信道干扰较弱，并且数据码长较短时，使用奇偶校验码效果很好，在计算机网络的数据传输中经常使用该种类型的检错码。 根据数据代码的分组方法，奇偶校验码可以分为水平奇偶校验、垂直奇偶校验和垂直水平奇偶校验三种方法。 水平奇偶校验 在水平奇偶校验方法中，将数据先以适当的长度划分成小组，并把码元按顺序一列一列地排列起来，然后对水平方向的码元进行奇偶校验，得到一列校验位，附加在其他各列之后，最后按行的顺序进行传输，如表2-1所示。 表2-1 水平奇偶校验 在水平奇偶校验编码的数据传输中，数据发送顺序及格式如图2-35所示。其中，P 为码字的特定长度，q 为码字的个数，其编码效率为q/（q+1）。 I 11 I 12 I 13 ……… I 1q r 1 I 21 I 22 I 23 ……… I 2q r 2 I p1 I p2 I p3 ……… I pq r p ……… ……… ……… 冗余位 图2-35 水平奇偶校验编码数据发送顺序及格式
第二讲 码制
※ 检错码和纠错码 ※
《数字电子技术基础》
第二讲 码制
█ 误差检验码(Error-detecting Codes)
由于存在干扰，二进制信息在传输过程中会出现 错误。为发现并纠正错误，提高数字设备的抗干扰能 力，必须使代码具有发现错误并纠正的能力，这种代 码称为误差检验码（ Error-detecting Codes ）。 最常用的误差检验码为奇偶校验码。它的编码方 法是在信息码组外增加一位监督码元，增加监督码元 后，使得整个码组中“1”码元的数目为奇数或为偶数。 若为奇数，称为奇校验码(Odd parity)；若为偶数， 称为偶校验码(Even parity)。
《数字电子技术基础》
第二讲 码制
表1
8421BCD码奇偶校验码示例
奇校验码 1 0000 0 0001 0 0010 1 0011 0 0100 1 0101 1 0110 0 0111 0 1000 1 1001 偶校验码 0 0000 1 0001 1 0010 0 0011 1 0100 0 0101 0 0110 1 0111 1 1000 0 1001 《数字电子技术基础》
信息码 0 1 2 3 4 5 6 7 8 9 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001
第二讲 码制
◆ 奇/偶校验码工程示例：
数据发送端 数据接收端
偶校验
01001 00101 10111…
01001 00100 10111… Error!
《数字电子技术基础》
图1 奇偶校验码工程示例
杰林信道检错纠错编码介绍 一、理论来源： 通过十多年的研究，王杰林先生发现了泛过程随机过程概率模型，基于这套概率模型，团队发明了众多算法，其中包括等熵无损压缩算法，数字信息加密算法，信道查错纠错编码算法，人工智能和数字信息分析算法等，自测发现均优于当前主流同类算法。目前基础的核心算法已经申请的多项发明专利，部分算法已经在相关领域实现应用。 本文介绍的泛过程信道检错和纠错编码方法是一种基于泛过程概率模型的全新信道纠错编码算法，本算法共分为两个版本，分别是检错V1.0.0和纠错V1.4.0。 二、检错V1.0.0性能介绍 检错V1.0.0算法，是一种按位线性检错算法，当前版本是在 1/1.5849625码率和1/2码率的情况下实现检错重发。编码后的二进制流以32比特为检错窗口，即每次验证32比特窗口中误比特情况。根据论文理论计算，此时的检错概率为： 0.999999999996055，于是误判概率为：0.000000000003945，也就是说几乎能100%检错，当检错窗口越长，则检错概率就趋近于1。本算法检错过程发现错误比特后，仅需从误比特窗口32比特最后1比特开始回溯，重传13个字节即可。由于是线性编译码，所以仅需传输27个字节即可开始译码。本算法具有各种码率下的子版本
功能和性能均不一样，如1/1.0413645818码率，1/1.025*******码率。 检错V2.0.0将通过增加纠错判据（高阶泛过程模型）提高查错能力。 检错V3.0.0将同时拥有压缩、查错能力的算法，当符号1和符号0的概率均等时，只有检错能力；当符号1和符号0的概率不均等时，具有无损压缩和纠错能力。 纠错V4.0.0将开发同时拥有压缩、加密、查错能力的算法。 三、纠错V1.4.0性能介绍 纠错V1.4.0，是同时有查错和纠错能力的算法，也是一种按位线性检错算法，是基于概率的纠错编译码方法，可达到纠错编码的理论值。自测实验模拟了随机干扰下的BSC、BEC和AWGN信道，使得编码后的伪随机文件发生误比特率。本算法在第29个字节开始译码，29个字节内同时出现错误比特小于5个比特，且误比特率小于10?3情况下，可在1/1.5849625码率和1/2码率实现一次性100%纠正并译码。29个字节内同时出现错误比特大于等于5个比特情形（能100%检错，但目前1.4.0版本无法纠错（将在后续版本中解决），需从出错位置开始回溯，重传13个字节即可；从实验上也可达到香农极限（待贵公司进行实用环境检测）。编译码速度极快，纠错率高，纠错结果可知可控，并可实现高并行处理。目前普通PC （Intel(R) Core(TM) i5-6500@3.20GHz (4 CPUs)，DDR4 8192MB
奇偶校验码 奇偶校验码是一种通过增加冗余位使得码字中“１”的个数为奇数或偶数的编码方法，它是一种检错码。 1.垂直奇偶校验的特点及编码规则 发送顺序↑ │ │ │ │ I 11 I 12 ... I 1q┐ │ │ │ ┘ 信 息 位I 21 I 22 ... I 2q ...... I p1 I p2 ... I pq r 1 r 2 ... r q冗余位 1)编码规则： 偶校验：r i=I1i+I2i+...+I pi(i=1,2,...,q) 奇校验：r i=I1i+I2i+...+I pi+1(i=1,2,...,q) 式中 p为码字的定长位数 q为码字的个数 垂直奇偶校验的编码效率为R=p/(p+1)。 2)特点：垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错。因而对差错的漏检率接近1/2。
2.水平奇偶校验的特点及编码规则1)编码规则： 发送顺序↑ │ │ │ │ I 11 I 12 ... I 1q r1 r 2 .... r p I 21 I 22 ... I 2q ...... I p1 I p2 ... I pq └──────┘↑ 信息位冗余位 偶校验：r i=I i1+I i2+...+I iq(i=1,2,...,p) 奇校验：r i=I i1+I i2+...+I iq+1(i=1,2,...,p) 式中 p为码字的定长位数 q为码字的个数 水平奇偶校验的编码效率为R=q/(q+1)。 2)特点：水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=p的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。
三、习题及思考题 1 、简述异步传输和同步传输的差别。 异步传输：数据以字符为传输单位，字符发送时间是异步的，即后一字符的发送时间与前一字符的发送时间无关。时序或同步仅在每个字符的范围内是必须的，接收机可以在每个新字符开始是抓住再同步的机会。同步传输：以比特块为单位进行传输，发送器与接收机之间通过专门的时钟线路或把同步信号嵌入数字信号进行同步。异步传输需要至少 20% 以上的开销，同步传输效率远远比异步传输高。 2 、检错码和纠错码有何不同？试比较在网络通信中使用时各自的优缺点。 检错码：只具有检错功能，但不能确定错误位置，也不能纠正错误。纠错码：具有纠错功能，将无效码字恢复成距离它最近的有效码字，但不是 100% 正确。要检测或纠正同样比特的错误，纠错码比检错码要求更大的海明距离，而且还不是 100% 正确，所以在大多数情况下只采用检错码，当检测出错后要求重发数据即可。 3 、假设采用异步传输，一个起始位，两个终止位，一个寄偶校验位，每一信号码元两位，对于下述信号（波特）率，试推出相应的信息传输速率（ b/s) ； (1)300 (2)600 (3)1200 (4)4800 。 1)300*12=3600b/s 2)600*12=7200b/s 3)1200*12=14400b/s 4)4800*12=57600b/s 4 、通信接口标准包括哪四方面的内容？为什么要作出这些规定？ 数据终端设备 DTE 和数据线路端接设备 DCE 之间的接口标准特性：机械的、电气的、功能性、过程性。机械特性规定了 DCE 与 DTE 的实际物理连接细节。电气特性规定了 DTE 和 DCE 必须使用的编码，必须用相同的电压来描述相同的状态，必须使用相同宽度的信号比特，这些特征决定能够达到的数据传输速率和距离。功能特性指定每条交换电路须完成的功能。根据接口的功能特性，过程特性指定传送数据的事件序列。 从一方面看， DCE 负责在传输介质或网络上收发比特，一次一个比特。在另一方面看， DCE 必须与 DTE 相互交互。一般来说，这要求对数据和控制信息进行交换，这是通过一套交换电路的线路完成的。为了运行这套机制，在传输线或网络上交换信号的两个 DCE 必须相互理解。另外，每个 DTE-DCE 对都必须设计成能合作并相互作用。为了使数据处理装备制造商和用户的重担变得轻松，因此作出通信接口标准的规定。 5 、比较 RS-232-C 与 ISDN 接口的电气特征。 RS-232-C 接口用于 DTE 设备与语音级调制解调器的连接，以利用公众模拟远程通信系统传输数据。使用25 线进行全双工数据传输。信号地线作为全部数据线路的公共回线，因此这种传输是不平衡的。 ISDN 接口：使用 8 线平衡传输方式。平衡方式比不平衡方式能容忍更高的噪声 , 而产生的噪声却更少。最为理想的是，对称传输线上的干扰将同等地围绕着两个导体，而不会影响到电压差异。因为不平衡传输不拥有