Lecture 4 运算器-数据校验码

1、问题问题n在数据储存、传输过程中，难免由于故障或干扰导致数据在数据储存、传输过程中，难免由于故障或干扰导致数据出错。如何有效地检测并纠正这种错误？出错。如何有效地检测并纠正这种错误？n1 0 1 1= ？ ； 1 0 1 0= ？课程结构计算机系计算机系统统计统统计硬件硬件运算器运算器数据表示数据表示数据数据数据数据定点定点原码原码反码反码补码补码移码移码浮点浮点一般表示一般表示规格化规格化IEEE754非数值数非数值数据据字符字符汉字汉字BCD码码校验码校验码奇偶校验奇偶校验海明校验海明校验循环冗余循环冗余校验校验运算方法运算方法运算器运算器存储器存储器控制器控制器总线总线输入输出输入输出软

2、硬件接软硬件接口口软件软件主要内容n校验码校验码n奇偶校验奇偶校验n海明校验海明校验n循环冗余校验循环冗余校验校验码校验码 为了提高计算机的为了提高计算机的可靠性可靠性，除了采取选用，除了采取选用更高可靠性的器件，更好的生产工艺等措施之更高可靠性的器件，更好的生产工艺等措施之外，还可以从数据编码上想一些办法，即采用外，还可以从数据编码上想一些办法，即采用一点一点冗余冗余的线路，在原有数据位之外再的线路，在原有数据位之外再增加增加一到几位校验位一到几位校验位，使新得到的码字带上某种特使新得到的码字带上某种特性性，之后则通过，之后则通过检查该码字是否仍保持有这一检查该码字是否仍保持有这一特性特性，

3、来，来发现发现是否出现了错误，甚至于定位错是否出现了错误，甚至于定位错误后，误后，自动改正自动改正这一错误，这就是我们这里说这一错误，这就是我们这里说的的检错纠错编码技术检错纠错编码技术。校验码校验码三种常用的检错纠错码：三种常用的检错纠错码：奇偶检错码奇偶检错码 用于用于并行并行数据传送中数据传送中海明检错与纠错码海明检错与纠错码 用于用于并行并行数据传送中数据传送中循环冗余码循环冗余码 用于用于串行串行数据传送中数据传送中编码过程编码过程译码过程译码过程传送传送原始数据原始数据码字码字结果数据结果数据形成校验位的值，形成校验位的值，加进特征加进特征检查接送的码字，检查接送的码字，发现发现

4、/ 改正错误改正错误主要内容n校验码校验码n奇偶校验奇偶校验n海明校验海明校验n循环冗余校验循环冗余校验校验码校验码奇偶校验码奇偶校验码n奇偶校验码：用于并行码奇偶校验码：用于并行码检错检错原理：在原理：在 k 位数据码之外增加位数据码之外增加 1 位校验位，位校验位，使使 K+1 位码字中取值为位码字中取值为 1 的位数的位数总保持总保持为为 偶数偶数（偶偶校验校验）或）或 奇数奇数（奇校验奇校验）。）。例如：例如： 偶校验偶校验奇校验奇校验校验位校验位0 0 0 10 0 0 10 1 0 10 1 0 10 1 0 10 0 0 11001 原有数字位原有数字位 两个新的码字两个新的码字

5、 字字校验位校验位校验码校验码例例1： 数据数据 0010 0001 0111 0101奇校验码奇校验码0010 0001 1偶校验码偶校验码0010 0001 00111 0101 00111 0101 1例例2：数据：数据 ： 0111 0101奇校验码奇校验码 0111 0101 0发送端发送端（门电路）（门电路）0110 0101 0接收端接收端出错出错奇偶校验只能发现奇数个错误，且不能纠正错误！校验码奇偶校验码奇偶校验码n校验位的产生：校验位的产生：n奇校验：奇校验：C*=0 1 n1n偶校验：偶校验：C=0 1 n1其中其中 代表按位加代表按位加( (异或）异或）n出错检测：出错检

6、测：n奇校验检测：奇校验检测：FC* 0 1 n1n偶校验检测：偶校验检测：FC 0 1 n1F F1 1表示有错，表示有错，F F0 0表示无错表示无错思考：奇偶校验的形成及校验电路？思考：奇偶校验的形成及校验电路？奇偶检验再说明n如果用如果用4位二进制编码位二进制编码16个状态，则一旦其中某一位或几个状态，则一旦其中某一位或几位出错，出错后的的结果依然是合法的状态位出错，出错后的的结果依然是合法的状态n00001111,16个状态都合法个状态都合法n如果用如果用4位二进制编码位二进制编码8个状态，如下，则一但其中一位出个状态，如下，则一但其中一位出了错，得到的编码就是一个非法编码了错，得到

7、的编码就是一个非法编码n0000,0011, 0101,0110, 1001,1010,1100,1111n假定用假定用10位二进制编码位二进制编码4个状态，如下，则其中两位出错个状态，如下，则其中两位出错后，可根据出错后的编码与合法编码的距离进行纠正后，可根据出错后的编码与合法编码的距离进行纠正n00000 00000, 00000 11111, 11111 00000, 11111 11111 n得到的错误编码若是得到的错误编码若是00000 00011，则可将其纠正为，则可将其纠正为00000 00000n这样编码能纠正这样编码能纠正3位错误吗，如得到位错误吗，如得到00000 0011

8、1？奇偶检验奇偶检验码字和码距n什么叫码距？什么叫码距？n由若干位代码组成的一个字叫由若干位代码组成的一个字叫“码字码字” ， 如如0011,01000011,0100n两个码字中具有不同代码的位的个数叫做这两个码字间的两个码字中具有不同代码的位的个数叫做这两个码字间的“距离距离” ，上例，上例 3 3n一种码制各码字间的最小距离称为一种码制各码字间的最小距离称为“码距码距”，它就是这个，它就是这个码制的距离。码制的距离。问题：问题：“84218421”码的码距是几？码的码距是几？ 2 2（00100010）和）和3 3（00110011）间距离为）间距离为1 1，“84218421”码制的码

9、距码制的码距为为1 1。n数据校验中的数据校验中的“码字码字”是指数据位和校验位按某种是指数据位和校验位按某种规律排列得到的代码规律排列得到的代码n码距与检错、纠错能力的关系（当码距与检错、纠错能力的关系（当d4d4） 如果码距如果码距d d为奇数，则能发现为奇数，则能发现d-1d-1位错，位错，或者或者能纠能纠正正( (d-1)/2d-1)/2位错。位错。 如果码距如果码距d d为偶数，则能发现为偶数，则能发现d/2d/2位错，位错，并并能纠正能纠正( (d/2-1)d/2-1)位错。位错。n常用的数据校验码有：常用的数据校验码有：奇偶校验码、海明校验码和循环冗余校验码。奇偶校验码、海明校验

10、码和循环冗余校验码。奇偶校验法的特点n特点：特点：n问题：奇偶校验码的码距是几？为什么？问题：奇偶校验码的码距是几？为什么？n码距码距d=2。在奇偶校验码中，若两个数中有奇数位不同，则。在奇偶校验码中，若两个数中有奇数位不同，则它们相应的校验位就不同；若有偶数位不同，则虽校验位它们相应的校验位就不同；若有偶数位不同，则虽校验位相同，但至少有两位数据位不同。因而任意两个码字之间相同，但至少有两位数据位不同。因而任意两个码字之间至少有两位不同。至少有两位不同。n根据码距和纠根据码距和纠/检错能力的关系，它只能发现奇数位出错，检错能力的关系，它只能发现奇数位出错，不能发现偶数位出错，而且也不能确定发

11、生错误的位置，不能发现偶数位出错，而且也不能确定发生错误的位置，不具有纠错能力。不具有纠错能力。n优点：优点：n开销小；适用于校验一字节长的代码，故常被用于存储器开销小；适用于校验一字节长的代码，故常被用于存储器读写检查或按字节传输过程中的数据校验读写检查或按字节传输过程中的数据校验 因为一字节长的代码发生错误时，因为一字节长的代码发生错误时，1位出错的概率较大，位出错的概率较大，两位以上出错则很少，所以可用奇偶校验。两位以上出错则很少，所以可用奇偶校验。主要内容n校验码校验码n奇偶校验奇偶校验n海明校验海明校验n循环冗余校验循环冗余校验校验码-海明码海明码n由由Richard Hamming

12、于于1950年提出，目前还被广泛使用。年提出，目前还被广泛使用。n主要用于存储器中数据存取校验。主要用于存储器中数据存取校验。n基本思想基本思想：奇偶校验码对整个数据编码生成一位校验位。因此：奇偶校验码对整个数据编码生成一位校验位。因此这种校验码检错能力差，并且没有纠错能力。如果将整个数据这种校验码检错能力差，并且没有纠错能力。如果将整个数据按某种规律分成若干组，对每组进行相应的奇偶检测，使得数按某种规律分成若干组，对每组进行相应的奇偶检测，使得数据位或校验位中某一位出错时，通过对各组检测得到的故障字据位或校验位中某一位出错时，通过对各组检测得到的故障字确定是哪一位数据或检验位出错。确定是哪一

13、位数据或检验位出错。海明校验码实质上就是一种多重奇偶校验码。海明校验码实质上就是一种多重奇偶校验码。校验码-海明码海明码n需要多少位校验码？需要多少位校验码？n假定数据位数为假定数据位数为n，校验码为校验码为k位，则校验位能表示的状态最多是位，则校验位能表示的状态最多是2k，每种状每种状态可用来说明一种出错情况。态可用来说明一种出错情况。n若只有一位错，则可能的结果是：若只有一位错，则可能的结果是：n数据中某一位错数据中某一位错 (n种可能种可能) n校验码中有一位错校验码中有一位错 (k种可能种可能) n无错无错 ( 1 种可能种可能)n结论：结论：要能对最多一位错的所有结果进行正确表示，则

14、要能对最多一位错的所有结果进行正确表示，则n和和k必必须满足下列关系：须满足下列关系： 2k1+n+k， 即：即：2k-1n+kn对于对于8位数据，如果进行一位纠错，需要多少位校验码？位数据，如果进行一位纠错，需要多少位校验码？校验码-海明码海明码n如何分组？如何分组？n基本思想基本思想:数据位和校验位按某种方式排列为一个数据位和校验位按某种方式排列为一个n+k的码字的码字，将该字中每一位的出错位置与故障字的值建立关系，通过故，将该字中每一位的出错位置与故障字的值建立关系，通过故障字的值确定码字中哪一位发生了错误，并将其取反来纠正。障字的值确定码字中哪一位发生了错误，并将其取反来纠正。 根据上

15、述基本思想，按以下规则来解释各故障字的值。根据上述基本思想，按以下规则来解释各故障字的值。 规则规则1： 若故障字每位全部是若故障字每位全部是0，则表示没有发生错误。，则表示没有发生错误。规则规则2：若故障字中有且仅有一位为：若故障字中有且仅有一位为1，则表示校验位中有一，则表示校验位中有一位出错，因而不需纠正。位出错，因而不需纠正。规则规则3：若故障字中多位为：若故障字中多位为1，则表示有一个数据位出错，其，则表示有一个数据位出错，其在码字中的出错位置由故障字的数值来确定。纠正时只要将在码字中的出错位置由故障字的数值来确定。纠正时只要将出错位取反即可。出错位取反即可。121110987654

16、321故障字故障字M8M7M6M5P4M4M3M2P3M1P2P1无无1111100000000S41000011110000S30110011001100S20101010101010S1S S1 1什么情况下为什么情况下为1 1？MM7 7，MM5 5，MM4 4，MM2 2，MM1 1，P P1 1中中 任何任何一位一位出错时出错时! !对比对比奇偶校验：可判断数据传输过程中有一位出错的情况奇偶校验：可判断数据传输过程中有一位出错的情况用用P P1 1作为作为MM7 7，MM5 5，MM4 4，MM2 2，MM1 1的校验位的校验位! !用偶校验：用偶校验： P P1 1= M= M1

17、1MM2 2MM4 4MM5 5MM7 7 ， S S1 1= P= P1 1 M M1 1MM2 2MM4 4MM5 5MM7 7 P：校验位，M：待校验的数据校验码-海明码海明码 以以8位数据进行单个位检错和纠错为例：位数据进行单个位检错和纠错为例： 假定一个假定一个8位数据位数据M= M8M7M6M5M4M3M2M1，其相应的其相应的4位校验位为位校验位为P=P4P3P2P1。根据规则将数据根据规则将数据M和校验位和校验位P按一定的规律排到一个按一定的规律排到一个12位码位码字中。字中。 据规则据规则1，故障字为故障字为0000时，表示无错，因此没有和位置号时，表示无错，因此没有和位置号

18、0000对应的出对应的出错情况，所以位置号从错情况，所以位置号从0001开始。开始。 据规则据规则2，故障字中有且仅有一位为故障字中有且仅有一位为1时，表示校验位中有一位出错，此时，表示校验位中有一位出错，此时，故障字只可能是时，故障字只可能是0001、0010、0100、1000四种情况，我们将这四种状四种情况，我们将这四种状态分别代表校验位中第态分别代表校验位中第P1、P2、P3、P4位发生错误的情况，因此，校验位位发生错误的情况，因此，校验位P1、P2、P3、P4应分别位于码字的第应分别位于码字的第1、2、4、8位。位。 据规则据规则3，将其他多位为将其他多位为1的故障字依次表示数据位的

19、故障字依次表示数据位M1M8发生错误的情发生错误的情况。因此，数据位况。因此，数据位M1M8应分别位于码字的第应分别位于码字的第0011(3)、0101(5)、0110(6)、0111(7)、1001(9)、1010(10)、1011(11)、1100(12)位。即码字的排列为：位。即码字的排列为： M8M7M6M5P4M4M3M2P3M1P2P1 逻辑上的一个顺序，物理上逻辑上的一个顺序，物理上M和和P是分开的是分开的校验码-海明码海明码n如果如果P1出错，希望故障字出错，希望故障字S4S3S2S1=0001; ;如果如果M1出错，希望故障字出错，希望故障字S4S3S2S1=0011;nM1

20、M2M4M5M7被分到第被分到第1组，用组，用P1检验，检验，P1= M1 M2 M4 M5 M7 ,n纠错：纠错：S1= P1 M1 M2 M4 M5 M7 ,海明码举例 假定一个假定一个8位数据位数据M为：为：M8M7M6M5M4M3M2M1= 01101010，根据上述公式求出相应的校验位为：根据上述公式求出相应的校验位为：P1 = M1 M2 M4 M5 M7 =0 1 1 0 1=1P2 = M1 M3 M4 M6 M7 =0 0 1 1 1=1P3 = M2 M3 M4 M8=1 0 1 0=0P4 = M5 M6 M7 M8=0 1 1 0=0假定假定12位码字位码字(M8M7M

21、6M5P4M4M3M2P3M1P2P1)读出后的结果是读出后的结果是: (1) 数据位数据位M=M=01101010，校验位校验位P=P=0011 (2) 数据位数据位M= 01111010，校验位校验位P=P=0011 (3) 数据位数据位M=M=01101010，校验位校验位P= 1011 要求分别考察每种情况的故障字。要求分别考察每种情况的故障字。 (1) 数据位数据位M=M=01101010，校验位校验位P=P=0011，即：所有位都无错。即：所有位都无错。 这种情况下，因为这种情况下，因为M=M，所以所以P= P， 因此因此 S = P P=P P = 0000。S1=P1 M1 M

22、2 M4 M5 M7 =P1 p1类似地S2= P2 P2S=P P(2) 数据位数据位M= 01111010，校验位校验位P=P=0011，即：数据位第即：数据位第5位位(M5)错。错。 这种情况下，对这种情况下，对M生成新的校验位生成新的校验位P为：为： P1 = M1 M2 M4 M5 M7=0 1 1 1 1=0 P2 = M1 M3 M4 M6 M7 =0 0 1 1 1=1 P3 = M2 M3 M4 M8=1 0 1 0=0 P4 = M5 M6 M7 M8=1 1 1 0=1 故障字故障字S为：为： S1= P1 P1= 0 1=1 S2= P2 P2=1 1=0 S3= P3

23、 P3=0 0=0 S4= P4 P4=1 0=1 根据故障字的数值根据故障字的数值1001，可以判断出发生错误的位是在，可以判断出发生错误的位是在12位码字的第位码字的第 1001位位(即：第即：第9位位)，在这一位上排列的是数据位，在这一位上排列的是数据位M5，所以检错正确所以检错正确, 纠错时，只要将码字的第纠错时，只要将码字的第9位（即：第位（即：第5个数据位）取反即可。个数据位）取反即可。海明码举例(3) 数据位数据位M=M=01101010，校验位校验位P= 1011， 即：校验码第即：校验码第4位位(P4)错。错。这种情况下，因为这种情况下，因为M=M，所以所以P= P，因此故障

24、位因此故障位S为：为：S1= P1 P1= 1 1=0S2= P2 P2=1 1=0S3= P3 P3=0 0=0S4= P4 P4=0 1=1 根据故障字的数值根据故障字的数值1000，可以判断出发生错误的位是，可以判断出发生错误的位是在在12位码字的第位码字的第1000位位(即：第即：第8位位)，在这一位上排列，在这一位上排列的是校验位的是校验位P4，所以检错正确，不需纠错。所以检错正确，不需纠错。海明码举例主要内容n校验码校验码n奇偶校验奇偶校验n海明校验海明校验n循环冗余校验循环冗余校验循环冗余码n通过数据运算来建立数据和校验位之间的关系。通过数据运算来建立数据和校验位之间的关系。n设设M(x)为一个为一个n位二进制数的多项式表示，将其左移位二进制数的多项式表示，将其左移k位后，