計(jì)算機(jī)組成原理中的三種校驗(yàn)方式

計(jì)算機(jī)組成原理中的三種校驗(yàn)方式目前一頁\總數(shù)三十二頁\編于十八點(diǎn)幾個(gè)名詞概念：碼字：由若干代碼組成的一個(gè)字。如8421碼中6（0110），7（0111）碼距：一種碼制中任意兩個(gè)碼字間的最小距離。距離：兩個(gè)碼字之間不同的代碼個(gè)數(shù)。8421碼中，最小的碼字間的距離為1，如0000和0001、0010和0011等；最大碼字間的距離為4，如0111和1000。所以8421碼制的碼距為1。碼距為1碼制，即不能查錯(cuò)也不能糾錯(cuò)。碼距越大的碼制，查錯(cuò)、糾錯(cuò)能力越強(qiáng)。目前二頁\總數(shù)三十二頁\編于十八點(diǎn)1奇偶校驗(yàn)法

奇偶校驗(yàn)法是計(jì)算機(jī)中廣泛采用的檢查傳輸數(shù)據(jù)準(zhǔn)確性的方法。奇偶校驗(yàn)法的原理是：在每組數(shù)據(jù)信息上附加一個(gè)校驗(yàn)位，校驗(yàn)位的取值（0或1）取決于這組信息中‘1’的個(gè)數(shù)和校驗(yàn)方式（奇或偶校驗(yàn)）。如果采用奇校驗(yàn)，則這組數(shù)據(jù)加上校驗(yàn)碼位后數(shù)據(jù)中‘1’的個(gè)數(shù)應(yīng)為奇數(shù)個(gè)。奇校驗(yàn)位形成公式:C=X0⊕X1⊕…⊕Xn-1如果采用偶校驗(yàn)，則這組數(shù)據(jù)加上校驗(yàn)碼位后數(shù)據(jù)中‘1’的個(gè)數(shù)應(yīng)為偶數(shù)個(gè)。偶校驗(yàn)位形成公式:C=X0⊕X1⊕…⊕Xn-1目前三頁\總數(shù)三十二頁\編于十八點(diǎn)在接收端校驗(yàn)檢測：偶校驗(yàn)：P=C⊕

X0⊕X1⊕…⊕Xn-1奇校驗(yàn)：P=C⊕

X0⊕X1⊕…⊕Xn-1若P=0則無錯(cuò)或有偶數(shù)位錯(cuò)，若P=1則有奇數(shù)位錯(cuò)目前四頁\總數(shù)三十二頁\編于十八點(diǎn)例如：八位信息‘10101011’中共有5個(gè)‘1’，附加校驗(yàn)位后變?yōu)榫盼?。若采用奇校?yàn)，則附加的校驗(yàn)位應(yīng)取‘0’值，保證1的個(gè)數(shù)為奇數(shù)個(gè)即010101011；若采用偶校驗(yàn)則附加的校驗(yàn)位應(yīng)取‘1’值即

110101011。

奇偶校驗(yàn)的特點(diǎn)：1、奇偶校驗(yàn)法可檢出數(shù)據(jù)傳送過程中奇數(shù)個(gè)數(shù)位出錯(cuò)的情況；2、實(shí)際中兩位同時(shí)出錯(cuò)的概率極低，奇偶校驗(yàn)法簡便可靠易行，但它只能發(fā)現(xiàn)錯(cuò)誤，卻不知錯(cuò)在何處，因而不能自動(dòng)糾正。目前五頁\總數(shù)三十二頁\編于十八點(diǎn)碼能力碼距

檢錯(cuò)糾錯(cuò)

1

0

0

2

1

0

3

2或1

4

2加1

5

2加2

6

3加2

7

3加3

為了使一個(gè)系統(tǒng)能檢查和糾正一個(gè)差錯(cuò)，碼間最小距離必須至少是“3”。最小距離為3時(shí)，或能糾正一個(gè)錯(cuò)，或能檢二個(gè)錯(cuò)，但不能同時(shí)糾一個(gè)錯(cuò)和檢二個(gè)錯(cuò)。編碼信息糾錯(cuò)和檢錯(cuò)能力的進(jìn)一步提高需要進(jìn)一步增加碼字間的最小距離。

碼距越大，糾錯(cuò)能力越強(qiáng)，但數(shù)據(jù)冗余也越大，即編碼效率低了。所以，選擇碼距要取決于特定系統(tǒng)的參數(shù)。目前六頁\總數(shù)三十二頁\編于十八點(diǎn)2海明碼校驗(yàn)方法

海明碼是一種比較常用的糾錯(cuò)碼，它實(shí)際上是一種多重奇偶校驗(yàn)碼。其基本思想是將被檢驗(yàn)碼分成多個(gè)組，每組配備一個(gè)奇偶校驗(yàn)位完成該組的奇偶校驗(yàn)位的功能。當(dāng)被校驗(yàn)碼中某一位出錯(cuò)時(shí)，將會(huì)有相關(guān)的多個(gè)小組出現(xiàn)奇偶校驗(yàn)錯(cuò)，根據(jù)這些組的出錯(cuò)情況便可將錯(cuò)誤定位到某一位上從而即可糾正過來。

目前七頁\總數(shù)三十二頁\編于十八點(diǎn)強(qiáng)調(diào)指出：海明碼校驗(yàn)方法以奇偶校驗(yàn)法為基礎(chǔ)，其校驗(yàn)位不是一個(gè)而是一組。海明碼校驗(yàn)方法能夠檢測出具體錯(cuò)誤并糾正。海明碼的最低目標(biāo)是能糾正一位錯(cuò)，因此要求海明碼的碼距大于或等于3。目前八頁\總數(shù)三十二頁\編于十八點(diǎn)海明校驗(yàn)碼是RichardHamming于1950年提出的，目前仍廣泛使用的一種編碼方法。1、原理（1）特點(diǎn)：能檢測出兩位同時(shí)出錯(cuò)、亦能檢測出一位出錯(cuò)并能自動(dòng)糾錯(cuò)。（2）實(shí)現(xiàn)原理：在k個(gè)數(shù)據(jù)位之外加上r個(gè)校驗(yàn)位，從而形成一個(gè)k十r位的新碼字，當(dāng)某一位出錯(cuò)后，就會(huì)引起相關(guān)的幾個(gè)校驗(yàn)位的值發(fā)生變化，從而達(dá)到檢錯(cuò)、糾錯(cuò)的目的。目前九頁\總數(shù)三十二頁\編于十八點(diǎn)kr(最小)122~435~11412~26527~5762r≥k+r+1(3.18)(一位出錯(cuò)并糾錯(cuò))數(shù)據(jù)位k與校驗(yàn)位r的對(duì)應(yīng)關(guān)系：

目前十頁\總數(shù)三十二頁\編于十八點(diǎn)2r-1≥k+r(3.19)(一位出錯(cuò)并糾錯(cuò)并發(fā)現(xiàn)兩位錯(cuò))碼距為4由3.19式計(jì)算可得目前十一頁\總數(shù)三十二頁\編于十八點(diǎn)2、編碼規(guī)則

若海明碼的最高位號(hào)為m，最低位號(hào)為1，即：HmHm-1…H2H1，則此海明碼的編碼規(guī)律：(1)校驗(yàn)位與數(shù)據(jù)位之和為m，每個(gè)校驗(yàn)位Pi在海明碼中被分在位號(hào)2i-1的位置，其余各位為數(shù)據(jù)位，并按從低向高逐位依次排列的關(guān)系分配各數(shù)據(jù)位。(2)海明碼的每一位碼Hi(包括數(shù)據(jù)位和校驗(yàn)位本身)由多個(gè)校驗(yàn)位校驗(yàn)，其關(guān)系是被校驗(yàn)的每一位位號(hào)要等于校驗(yàn)它的各校驗(yàn)位的位號(hào)之和。這樣安排的目的,是希望校驗(yàn)的結(jié)果能正確反映出出錯(cuò)位的位號(hào)。

目前十二頁\總數(shù)三十二頁\編于十八點(diǎn)1、糾查一位錯(cuò)的編碼方法

（以四個(gè)校驗(yàn)位進(jìn)行說明）四個(gè)校驗(yàn)位最多可以校驗(yàn)11位數(shù)據(jù)。設(shè)：

D10D9D8D7D6D5D4D3D2D1D0為11個(gè)數(shù)據(jù)位，

P4P3P2P1分別為四個(gè)校驗(yàn)碼，則編碼規(guī)則是：海明碼的總位數(shù)H等于數(shù)據(jù)位與校驗(yàn)位之和；每個(gè)校驗(yàn)位Pi排放在2i-1的位置，如P4排放在第24-1=8位，其余數(shù)據(jù)位依序排列。目前十三頁\總數(shù)三十二頁\編于十八點(diǎn)即：

H15H14H13H12H11H10H9H8H7H6H5H4H3H2H1D10D9D8D7D6D5D4P4

D3D2D1P3

D0

P2P1海明碼的每一位用多個(gè)校驗(yàn)位一起進(jìn)行校驗(yàn)，被校驗(yàn)的位號(hào)等于校驗(yàn)它的各校驗(yàn)位位號(hào)和；各校驗(yàn)位的值為它參與校驗(yàn)的數(shù)據(jù)位的異或。目前十四頁\總數(shù)三十二頁\編于十八點(diǎn)

海明碼校驗(yàn)表P4,P3,P28,4,2(14=8+4+2)H14D9P4,P3,P18,4,1(13=8+4+1)H13D8P4,P38,4(12=8+4)H12D7P4,P2,P18,2,1(11=8+2+1)H11D6P4,P28,2(10=8+2)H10D5P4,P18,1(8=8+1)H9D4P48H8P44,2,1(7=4+2+1)P3,P2,P1H7D3P3,P24,2(6=4+2)H6D2P3,P14,1(5=4+1)H5D1P4,P3,P2,P18,4,2,1(15=8+4+2+1)H15D10P34H4P3P2P12,1(3=2+1)H3D0P22H2P2P11H1P1參與的校驗(yàn)位參與校驗(yàn)的校驗(yàn)位位號(hào)海明碼位號(hào)目前十五頁\總數(shù)三十二頁\編于十八點(diǎn)

各校驗(yàn)位形成公式：P1=D0⊕D1⊕D3⊕D4⊕D6⊕D8⊕D10(1)

P2=D0⊕D2⊕D3⊕D5⊕D6⊕D9⊕D10(2)P3=D1⊕D2⊕D3⊕D7⊕D8⊕D9⊕D10(3)P4=D4⊕D5⊕D6⊕D7⊕D8⊕D9⊕D10(4)按上述方式Pi的取值是采用偶校驗(yàn)時(shí)的取值，當(dāng)采用奇校驗(yàn)時(shí)，Pi則取反。這樣Pi連同數(shù)據(jù)位一起形成了海明碼的各位。

用海名位號(hào)改寫P4～P1：P1=H3⊕H5⊕H7⊕H9⊕H11

⊕H13

⊕H15P2=H3⊕H6⊕H7⊕H10⊕H11

⊕H14

⊕H15P3=H5⊕H6⊕H7⊕H12⊕H13⊕H14⊕H15P4=H9⊕H10⊕H11⊕H12⊕H13⊕H14⊕H15目前十六頁\總數(shù)三十二頁\編于十八點(diǎn)2、檢查糾錯(cuò)（以四個(gè)校驗(yàn)位進(jìn)行說明）

海明碼數(shù)據(jù)傳送到接收方后，再將各校驗(yàn)位的值與它所參與校驗(yàn)的數(shù)據(jù)位的異或結(jié)果進(jìn)行異或運(yùn)算。運(yùn)算結(jié)果稱為校驗(yàn)和。校驗(yàn)和共有四個(gè)。對(duì)偶校驗(yàn)來說，如果校驗(yàn)和不為零則傳輸過程中間有錯(cuò)誤。而錯(cuò)誤的具體位置則由四個(gè)校驗(yàn)和依序排列后直接指明。如果四個(gè)校驗(yàn)和S4S3S2S1

依序排列后等于(1001)2=(9)10時(shí)，就表明海明碼的第九位也就是D4發(fā)生了錯(cuò)誤，此時(shí)只要將D4取反，也就糾正了錯(cuò)誤。目前十七頁\總數(shù)三十二頁\編于十八點(diǎn)

校驗(yàn)和Si的表達(dá)式：S1=D0⊕D1⊕D3⊕D4⊕D6⊕D8⊕D10⊕P1

S2=D0⊕D2⊕D3⊕D5⊕D6⊕D9⊕D10⊕P2S3=D1⊕D2⊕D3⊕D7⊕D8⊕D9⊕D10⊕P3S4=D4⊕D5⊕D6⊕D7⊕D8⊕D9⊕D10⊕P4

用海名位號(hào)改寫S4～S1：S1=H1⊕H3⊕H5⊕H7⊕H9⊕H11

S2=H2⊕H3⊕H6⊕H7⊕H10⊕H11

S3=H4⊕H5⊕H6⊕H7⊕H12S4=H8⊕H9⊕H10⊕H11⊕H12目前十八頁\總數(shù)三十二頁\編于十八點(diǎn)當(dāng)采用偶校驗(yàn)方式其傳送數(shù)據(jù)正確時(shí)，校驗(yàn)和S1~S4的值分別都為0；當(dāng)采用奇校驗(yàn)方式其傳送數(shù)據(jù)正確時(shí)，校驗(yàn)和S1~S4的值分別都為1。當(dāng)不為上述值時(shí)，傳送就發(fā)生了錯(cuò)誤。目前十九頁\總數(shù)三十二頁\編于十八點(diǎn)解：已知D10D9D8D7D6D5D4D3D2D1D0

由于被校驗(yàn)位的位號(hào)等于校驗(yàn)它的各校驗(yàn)位位號(hào)之和以及各校驗(yàn)位的取值等于它參與校驗(yàn)的數(shù)據(jù)位取值的異或。所以校驗(yàn)位的取值以及所求海明碼為：P1=D0D1

D3

D4

D6

D8

D10=1P2=D0

D2

D3

D5

D6

D9

D10=1P3=D1

D2

D3

D7

D8

D9

D10=1P4=D4

D5

D6

D7

D8

D9

D10=0D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1=傳送正確時(shí)校驗(yàn)和的值為0，如果不等于0，則是幾就是第幾位出錯(cuò)，是7則是第7位D3出錯(cuò)，此時(shí)將其取反即可糾正錯(cuò)誤。例題：采用4位校驗(yàn)位、偶校驗(yàn)方式，目前二十頁\總數(shù)三十二頁\編于十八點(diǎn)例4.5按配奇原則配置1100101的漢明碼。解：根據(jù)1100101，得n=7。根據(jù)2k≥n+k+1，可求出需增添k=4位檢測位，各位的安排如下：二進(jìn)制序號(hào)1234567891011海明碼C1C21C4100C8101按配奇原則配置，則C1=3⊕5⊕7⊕9⊕11=1C2=3⊕6⊕7⊕10⊕11=1C4=5⊕6⊕7=0C8=9⊕10⊕11=1目前二十一頁\總數(shù)三十二頁\編于十八點(diǎn)例4.4已知接收到的海明碼為0110101（按配偶原則配置），試問欲傳送的信息是什么？解：由于要求出欲傳送的信息，必須是正確的信息，因此不能簡單地從接收到的7位海明碼中去掉C1、C2、C4三位檢測位來求得。首先應(yīng)該判斷收到的信息是否出錯(cuò)。糾錯(cuò)過程如下：s1=1⊕3⊕5⊕7=1s2=2⊕3⊕6⊕7=1s3=4⊕5⊕6⊕7=0所以，s3s2s1=011，第3位出錯(cuò)，可糾正為0100101，故欲傳送的信息為0101。目前二十二頁\總數(shù)三十二頁\編于十八點(diǎn)C1C2…...CK

r1r2……ri

3.7.3循環(huán)冗余校驗(yàn)方法(CRC碼)循環(huán)冗余校驗(yàn)方式：通過某種數(shù)學(xué)公式建立信息位和校驗(yàn)位之間的約定關(guān)系——能夠校驗(yàn)傳送信息的對(duì)錯(cuò)，并且能自動(dòng)修正錯(cuò)誤。廣泛用于通信和磁介存儲(chǔ)器中。CRC編碼格式是在k位信息后加r位檢驗(yàn)碼。NN-121

信息位（k位）校驗(yàn)位（r位）目前二十三頁\總數(shù)三十二頁\編于十八點(diǎn)1、CRC碼的編碼方法CRC整個(gè)編碼長度為n=k+r位，故CRC碼又叫（n，k）碼。其編碼方法如下：假設(shè)被傳送的k位二進(jìn)制信息位用C(x)表示,系統(tǒng)選定的生成多項(xiàng)式用G(X)表示，將C(x)左移G(X)的最高次冪(即等于需要添加的校驗(yàn)位的位數(shù)r)，寫作C(x)?2r然后將其C(x)?2r除以生成多項(xiàng)式G(x)，所得商用Q(x)表示，余數(shù)用R(x)表示。則：兩邊同時(shí)乘以G(x)并左移R(x)得到：目前二十四頁\總數(shù)三十二頁\編于十八點(diǎn)故有：上式中，等式左邊即為所求的n位CRC碼，其中余數(shù)表達(dá)式R(x)就是校驗(yàn)位(r位)。且等式兩邊都是G(x)的倍數(shù)。發(fā)送信息時(shí)將等式左邊生成的n位CRC碼送給對(duì)方。當(dāng)接收方接到n位編碼后，同樣除以G(x)，如果傳輸正確則余數(shù)為0，否則則可以根據(jù)余數(shù)的數(shù)值確定是哪位數(shù)據(jù)出錯(cuò)。由于CRC編碼采用的加、減法是按位加減法，即不考慮進(jìn)位與借位，運(yùn)算規(guī)則為：00=0，01=1，10=1，11=0模2加目前二十五頁\總數(shù)三十二頁\編于十八點(diǎn)

例：有一個(gè)（7,4）碼（即CRC碼為7位，信息碼為4位），已確定生成多項(xiàng)式為：

G（X）=X3+X+1=1011

被傳輸?shù)男畔(x)=1001，求C(x)的CRC碼。解：C（x）左移r=n–k=3位即：將上式模2采用除法除以給定的G(x)=1011：1001000/1011=1010+110/1011得到余數(shù)表達(dá)式：R(x)=110所求CRC碼目前二十六頁\總數(shù)三十二頁\編于十八點(diǎn)目前二十七頁\總數(shù)三十二頁\編于十八點(diǎn)2、CRC碼的查錯(cuò)表收到的CRC碼除以約定的生成多項(xiàng)式G(x)，如果余數(shù)為0則傳輸無誤，否則傳輸錯(cuò)誤，根據(jù)所得余數(shù)值就可找出錯(cuò)誤并取反糾正。上表詳細(xì)說明了CRC碼1001110在傳送時(shí)某一位出錯(cuò)后的判斷與糾正方法[C(X)=1001、G(x)=1011]。目前二十八頁\總數(shù)三十二頁\編于十八點(diǎn)3、生成多項(xiàng)式G（x）的確定G(x)是一個(gè)約定的除數(shù)，用來產(chǎn)生校驗(yàn)碼。從檢錯(cuò)和糾錯(cuò)的要求出發(fā)，它并不是隨意選擇的，它應(yīng)滿足下列要求：任何一位發(fā)生錯(cuò)誤都應(yīng)使余數(shù)不為0；不同位發(fā)生錯(cuò)誤應(yīng)使余數(shù)不同；余數(shù)繼續(xù)模2除，應(yīng)使余數(shù)循環(huán)。在