1、2022-7-211第第4章章 存储器存储器 补充内容：补充内容：数据校验码数据校验码2022-7-212数据校验码是什么？数据校验码是什么？l数据在传输或存储过程中常因受到某种随机干扰数据在传输或存储过程中常因受到某种随机干扰而发生错误（即误码）：而发生错误（即误码）：1 1 0 0 或或 0 01 1l为了保证数据的正确性，必须及时发现并纠正数为了保证数据的正确性，必须及时发现并纠正数据中的错误。据中的错误。l数据校验码数据校验码：一种具有检错能力或自动改错能：一种具有检错能力或自动改错能力的数据编码方法。力的数据编码方法。2022-7-213“冗余校验冗余校验”思想思想：（以数据传输为例
2、）：（以数据传输为例）（1 1）编码编码：在原始数据（即有效数据位）的基础上：在原始数据（即有效数据位）的基础上增加冗余数据（即校验位），按照某种增加冗余数据（即校验位），按照某种规律规律将有效将有效数据位和校验位一起编码，得到数据位和校验位一起编码，得到数据校验码数据校验码；（2 2）译码译码：按同一约定：按同一约定规律规律对收到的数据校验码进对收到的数据校验码进行分析，并判断约定规律是否被破坏。行分析，并判断约定规律是否被破坏。若未被破坏，则正确，从中取出有效数据即可；若未被破坏，则正确，从中取出有效数据即可；若被破坏，则有错，根据约定规律被破坏后的某若被破坏，则有错，根据约定规律被破坏后
3、的某些特征对出错位进行定位，从而可自动纠正错误。些特征对出错位进行定位，从而可自动纠正错误。2022-7-214l本质本质：加进一些冗余码，使合法加进一些冗余码，使合法编码出现某些错误时，就成为非编码出现某些错误时，就成为非法编码。这样，可通过检测编码法编码。这样，可通过检测编码的合法性来达到发现错误的目的。的合法性来达到发现错误的目的。l举例：假设有效数据用举例：假设有效数据用3 3位二进制位二进制编码，表示某个地区八个城市的编码，表示某个地区八个城市的代号。代号。l码距码距：一个编码系统中任意两个一个编码系统中任意两个合法编码之间对应二进制位状态合法编码之间对应二进制位状态不同的位数，称为
4、这不同的位数，称为这两个编码的两个编码的距离距离。任意两个编码的最小距离。任意两个编码的最小距离就是该编码系统的就是该编码系统的码距码距，通常用，通常用d表示。例子中的表示。例子中的d=？二进制编码二进制编码 D2 D1 D0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 101101001 P2022-7-215l为了使一个编码系统能为了使一个编码系统能发现并纠正一位错，其发现并纠正一位错，其码距至少应为码距至少应为3 3。此时，。此时，或能纠正一位错，或能或能纠正一位错，或能发现二位错。但不能同发现二位错。但不能同时兼有这两种能力。时兼有这两种
5、能力。l为了进一步提高编码系为了进一步提高编码系统的检错和纠错能力，统的检错和纠错能力，必须进一步增加码距。必须进一步增加码距。l码距码距d=码码距距编码系统能力编码系统能力查错查错 纠错纠错10 021 032 或或 142 与与 15 2 与与 26 3 与与 273 与与 3位错。位错，并能纠正偶数：可以发现位错；位错，或纠正奇数：可以发现)12/(2/2/)1(1dddd2022-7-216 结论结论：l增加的校验位越多，增加的校验位越多，码距越大，纠错能力越码距越大，纠错能力越强；但数据冗余也越大，代价越高。强；但数据冗余也越大，代价越高。l数据校验码数据校验码设计原则：设计原则：在
6、不过多增加硬件开销在不过多增加硬件开销的情况下，尽可能多地发现和纠正错误。的情况下，尽可能多地发现和纠正错误。l设计者要综合考虑信息发生差错的概率以综合考虑信息发生差错的概率以及具体应用系统所能容许的最小差错率等及具体应用系统所能容许的最小差错率等因素因素来选择合适的码距。选择合适的码距。2022-7-217一、奇偶校验码一、奇偶校验码l最简单、开销最小最简单、开销最小，广泛应用于存储器读写校验。，广泛应用于存储器读写校验。l编码规律编码规律：l偶校验偶校验：配一个校验位，使整个校验码（包括有效数据位和：配一个校验位，使整个校验码（包括有效数据位和校验位）中校验位）中“1”1”的个数为偶数；的
7、个数为偶数；l奇校验奇校验：配一个校验位，使整个校验码（包括有效数据位和：配一个校验位，使整个校验码（包括有效数据位和校验位）中校验位）中“1”1”的个数为奇数；的个数为奇数；l采用奇校验还是偶校验，应事先约定好。采用奇校验还是偶校验，应事先约定好。2022-7-218以以偶校验偶校验为例介绍其编、译码方法为例介绍其编、译码方法l编码编码：统计有效数据中统计有效数据中“1”的个数的个数，若为奇数（偶，若为奇数（偶数），则令增加的校验位为数），则令增加的校验位为“1”（“0”），由有效数），由有效数据和校验位构成整个校验码。（写入存储器）据和校验位构成整个校验码。（写入存储器）形如形如 D D8
8、 8D D7 7D D6 6D D5 5D D4 4D D3 3D D2 2D D1 1D D校校其中其中 D D校校=D=D8 8 D D7 7 D D6 6 D D5 5 D D4 4 D D3 3 D D2 2 D D1 1例如：例如：有效数据有效数据偶校验码偶校验码10110010101100100101100111011001112022-7-219l译码译码：（从存储器读出）（从存储器读出）统计整个校验码统计整个校验码中中“1”的个数的个数，若仍为偶数，则表明约定，若仍为偶数，则表明约定规律未被破坏，读出的数据是正确的，从规律未被破坏，读出的数据是正确的，从中取出有效数据即可；否则
9、，表明出错。中取出有效数据即可；否则，表明出错。l出错条件可表示为：出错条件可表示为：偶校验错偶校验错=D=D8 8 D D7 7 D D6 6 D D5 5 D D4 4 D D3 3 D D2 2 D D1 1 D D校校l检错纠错能力分析：检错纠错能力分析：l码距码距 d=2d=2；l只能发现只能发现1 1位错，而不能纠正错误；位错，而不能纠正错误；l不能发现偶数个错误。不能发现偶数个错误。因一位出错的几率大，故有实用价值。因一位出错的几率大，故有实用价值。2022-7-2110逻辑实现：逻辑实现：编编码码译译码码2022-7-2111二、二、海明校验码海明校验码 19501950年，年
10、，Richard HammingRichard Hamming提出。目前仍应用广泛。提出。目前仍应用广泛。实质：是一种多重奇偶校验码多重奇偶校验码。实现原理：l按一定规律将有效数据位划分为若干组，分组进行按一定规律将有效数据位划分为若干组，分组进行奇偶校验。奇偶校验。l各组的检错信息构成一个各组的检错信息构成一个指错字指错字，不但可以发现出，不但可以发现出错，还能指出是哪一位出错，为自动纠错提供依据。错，还能指出是哪一位出错，为自动纠错提供依据。2022-7-2112(1)(1)分成几组？增加多少校验位？分成几组？增加多少校验位？设待编信息k位，分为r组，每组增加一个校验位，则r位校验位构成一
11、个r位的指错字。r r位校验位能表示位校验位能表示2 2r r种状态：种状态：用全用全0 0表示表示“没有错误没有错误”；用其余用其余2 2r r-1-1种状态指出错误发生在哪一位。种状态指出错误发生在哪一位。具体实现具体实现2022-7-2113需要满足：需要满足：2r 1 k+r若设若设k=4k=4，则，则r3r3，组成，组成7 7位海明码。位海明码。k1245111226 275758120r2345672022-7-2114(2)分组方法？设有效数据4位：A4 A3 A2 A1，增加3位校验位：P3 P2 P1，构成一个3位的指错字G3 G2 G1。7654321A4A3A2P3A1P
12、2P1 P Pi i在海明码中位序号为在海明码中位序号为2 2i-1i-1的位置上。的位置上。2022-7-21157654321指错字指错字A4A3A2P3A1P2P1第第3 3组组G3第第2 2组组G2第第1 1组组G1“”表示某位海明码参加某组。表示某位海明码参加某组。有效数据位有效数据位Ai分别参加分别参加2组以上，且满组以上，且满足如下关系：其位序号要等于所参与各组足如下关系：其位序号要等于所参与各组的校验位的位序号之和。的校验位的位序号之和。每个校验位每个校验位Pi只参加本组。只参加本组。2022-7-2116(3)编码（以偶校验为例）？第第1 1组：组：P P1 1=A=A1 1
13、 A A2 2 A A4 4 G G1 1=P=P1 1 A A1 1 A A2 2 A A4 4 第第2 2组：组：P P2 2=A=A1 1 A A3 3 A A4 4 G G2 2=P=P2 2 A A1 1 A A3 3 A A4 4 第第3 3组：组：P P3 3=A=A2 2 A A3 3 A A4 4 G G3 3=P=P3 3 A A2 2 A A3 3 A A4 4 (4)查错与纠错若若G G3 3G G2 2G G1 1000000，若若G G3 3G G2 2G G1 1000000，则无错；则无错；则则G G3 3G G2 2G G1 1的值即指明出错位，的值即指明出错
14、位，将该位取反即可纠正。将该位取反即可纠正。2022-7-21177654321指错字指错字G3G2G1A4A3A2P3A1P2P1正确码正确码0101101000出错码出错码0111101G G1 1=P=P1 1 A A1 1 A A2 2 A A4 4=1 1 1 0=1=1 1 1 0=1 G G2 2=P=P2 2 A A1 1 A A3 3 A A4 4=0 1 1 0=0=0 1 1 0=0 G G3 3=P=P3 3 A A2 2 A A3 3 A A4 4=1 1 1 0=1=1 1 1 0=1 1012022-7-2118(5)(5)逻辑实现逻辑实现(译码电路译码电路)20
15、22-7-2119 由于每一个有效数据位至少要由于每一个有效数据位至少要参加两个校验组参加两个校验组的奇偶检测的奇偶检测，因此当两个有效数据只有一位不相，因此当两个有效数据只有一位不相同时，该位至少引起两个校验位的不同！故码距同时，该位至少引起两个校验位的不同！故码距d3。(6)(6)分析分析 d3的码能够检测的码能够检测2位错，或用来检测并纠正位错，或用来检测并纠正 1位错，但两者只能择一。位错，但两者只能择一。如要能检测并纠正如要能检测并纠正1位错，同时能发现位错，同时能发现2位错，位错，此时应增加一个校验位，即应满足：此时应增加一个校验位，即应满足：2r-1k+r2022-7-2120
16、校验规则：让校验码能被某一约定代码除尽。若能除尽，表明代码无错；若除不尽，余数将指明出错位置。三、三、循环冗余校验码（循环冗余校验码（CRC码）码）实现原理：在k位信息位之后拼接r位校验位。问题1：如何从k位信息位简便地得到r位校验位？问题2：如何从k+r位信息码判断是否有错？2022-7-2121 模2运算：以按位模2相加为基础，运算时不考虑进位和借位。模2加减（异或）000 011 101 110 模2乘（用模2加求和）例如：1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 CRC码是基于码是基于模模2运算运算来建立编译码规律的校验码，在计
17、来建立编译码规律的校验码，在计算机外存储器校验和通信等方面应用广泛。算机外存储器校验和通信等方面应用广泛。2022-7-2122 模2除（用模2减求余数）每求1位商使部分余数减少1位。上商原则：部分余数的首位为1，商取1；部分余数的首位为0，商取0。当部分余数位数小于除数位数时，该余数为最后余数。例如：1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 12022-7-2123设：被除数M(x)：k位待编信息 除数G(x)：r+1位？余数R(x)：r位校验位 商Q(x)(1)CRC(1)CRC码的编码方法码的编码方法 具体实现具体实现
18、a.将待编码的k位有效信息位组写成表达式：M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0 (Ci=0或1)b.将信息位组左移r位，变成多项式M(x)Xr；c.用M(x)Xr除以G(x)，所得余数作为校验位。d.有效的CRC码为：M(x)Xr+R(x)=Q(x)G(x)+R(x)+R(x)=Q(x)G(x)。所以：CRC码能够被G(x)除尽。2022-7-2124例如：例如：对对M(x)=1100M(x)=1100，用，用G(x)=1011G(x)=1011，求，求CRCCRC码。码。a.将待编码的k=4位有效信息位组写成表达式：M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+
19、C0=X3+X2=110010110101110101111000003G(X)XM(X)b.将信息位组左移r=3位,M(x)Xr=M(X)X3=1100000c.用M(x)Xr除以G(x)，所得余数作为校验位。d.有效的CRC码此处为(7,4)码为：M(x)Xr+R(x)=1100000+010=1100010。2022-7-2125(2)CRC码的译码与纠错 译码：用收到的CRC码除以G(x)。若码字无误，则余数为0；若有某1位错，则余数不为0且不同位出错时的余数不同。注意：余数与出错位的对应关系不变，它只与码制和生成多项式G(x)有关，而与待测码字无关。2022-7-2126 (7(7，
20、4)4)循环码的出错模式循环码的出错模式(生成多项式生成多项式G(x)=1011)G(x)=1011)A A1 1A A2 2A A3 3A A4 4A A5 5A A6 6A A7 7余数余数出错位出错位正确正确1 11 10 00 00 01 10 00 0 00 0 0无无错误错误1 11 10 00 00 01 11 10 0 10 0 17 71 11 10 00 00 00 00 00 1 00 1 06 61 11 10 00 01 11 10 01 0 01 0 05 51 11 10 01 10 01 10 00 1 10 1 14 41 11 11 10 00 01 10
21、01 1 01 1 03 31 10 00 00 00 01 10 01 1 11 1 12 20 01 10 00 00 01 10 01 0 11 0 11 12022-7-2127 纠错：对于用G(x)作模2除得到的余数R(x)，若补0继续除下去，发现各次的余数按上表的顺序循环。所以，可以采用一种节省硬件的纠错办法：如只设置余数如只设置余数101101的译码输出，对应于第的译码输出，对应于第1 1位位A1出错。出错。在求出余数不为在求出余数不为0 0后，对余数一边补后，对余数一边补0 0一边作模一边作模2 2除，除，同时将被测码字循环左移，当余数为同时将被测码字循环左移，当余数为101101时，出错位时，出错位 移到移到A1A1位置，将它纠正后继续移位，使移位次数满位置，将它纠正后继续移位，使移位次数满 k+rk+r次即可。次即可。2022-7-2128(3)(3)生成多项式生成多项式G(x)G(x)不是任一个(r+1)位多项式都可作生成多项式。生成多项式应能满足下列要求：任何一位发生错误都应使余数不为0。不同位发生错误应当使余数不同。对余数继续作模2除，应使余数循环。生成多项式可以查表得到。
