差錯(cuò)檢驗(yàn)與校正解讀課件

1、差錯(cuò)檢驗(yàn)與校正2.4差錯(cuò)檢驗(yàn)與校正第2章 數(shù)據(jù)通信基礎(chǔ)第1頁(yè)，共23頁(yè)。 計(jì)算機(jī)網(wǎng)絡(luò)的基本要求是高速而且無(wú)差錯(cuò)的傳輸數(shù)據(jù)信息，而通信系統(tǒng)主要由一個(gè)個(gè)物理實(shí)體組成。一個(gè)物理實(shí)體從制造、裝配等都無(wú)法達(dá)到理想的理論值，而且通信系統(tǒng)在運(yùn)作中，也會(huì)受到周圍環(huán)境的影響。因此數(shù)據(jù)在傳輸數(shù)據(jù)過(guò)程中發(fā)生差錯(cuò)是不可避免的，解決這個(gè)問(wèn)題的技術(shù)稱為差錯(cuò)控制技術(shù) ，即把差錯(cuò)控制在允許的范圍內(nèi)。通常差錯(cuò)控制技術(shù)包括兩個(gè)主要內(nèi)容：差錯(cuò)的檢驗(yàn)差錯(cuò)的校正第2頁(yè)，共23頁(yè)。1、差錯(cuò)出現(xiàn)的可能原因 數(shù)據(jù)傳輸中出現(xiàn)差錯(cuò)有多種原因，一般分為內(nèi)部因素和外部因素。 內(nèi)部因素有噪聲脈沖、脈動(dòng)噪聲、衰減、延遲、失真等。機(jī)器設(shè)備本身的不理想、技

2、術(shù)不成熟 外部因素有電磁干擾、太陽(yáng)噪聲、工業(yè)噪聲等。對(duì)信號(hào)影響較大。 噪聲脈沖：通信中出現(xiàn)的離散型噪聲的統(tǒng)稱。它由時(shí)間上無(wú)規(guī)則出現(xiàn)的突發(fā)性干擾組成。第3頁(yè)，共23頁(yè)。 一般來(lái)說(shuō)，傳輸中的差錯(cuò)都是由噪聲引起的。噪聲有兩大類：隨機(jī)熱噪聲和沖擊噪聲。隨機(jī)差錯(cuò)：隨機(jī)熱噪聲 信道所固有的，持續(xù)存在的，隨機(jī)錯(cuò)通常 較少。 突發(fā)差錯(cuò)：沖擊噪聲 由于外界特定的短暫原因所造成的沖擊噪聲，沖擊噪聲的幅度可以相當(dāng)大 ，它是傳輸中產(chǎn)生差錯(cuò)的重要原因 。第4頁(yè)，共23頁(yè)。2、兩種差錯(cuò)控制技術(shù)檢錯(cuò)法糾錯(cuò)法在發(fā)送方的數(shù)據(jù)中增加一些用于檢查差錯(cuò)的附加位。用于有反饋的傳輸機(jī)制中。實(shí)現(xiàn)方法簡(jiǎn)單，速度快。在待發(fā)送數(shù)據(jù)中增加足夠多的

3、附加位，從而使得接收方能夠準(zhǔn)確地檢測(cè)到差錯(cuò)，并且可以自動(dòng)地糾正差錯(cuò)。用于無(wú)反饋信息的傳輸機(jī)制中，如漢明碼。第5頁(yè)，共23頁(yè)。 3、奇偶校驗(yàn) 奇偶校驗(yàn)(Parity Check)是一種校驗(yàn)代碼傳輸正確性的方法，是一種最簡(jiǎn)單的檢錯(cuò)方法。根據(jù)被傳輸?shù)囊唤M二進(jìn)制代碼的數(shù)位中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)來(lái)進(jìn)行校驗(yàn)。采用何種校驗(yàn)是事先規(guī)定好的。采用奇數(shù)的稱為奇校驗(yàn)，反之，稱為偶校驗(yàn)。通常專門設(shè)置一個(gè)奇偶校驗(yàn)位，用它使這組代碼中“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)。若用奇校驗(yàn)，則當(dāng)接收端收到這組代碼時(shí)，校驗(yàn)“1”的個(gè)數(shù)是否為奇數(shù)，從而確定傳輸代碼的正確性。 第6頁(yè)，共23頁(yè)。 例如，在傳輸ASCII字符時(shí)，每個(gè)ASCII字

4、符用7為表示，最后加上一個(gè)奇偶校驗(yàn)位總共成為8位。對(duì)于奇校驗(yàn)來(lái)說(shuō)，最后加上的奇偶位校驗(yàn)使整個(gè)8位中1個(gè)數(shù)為奇數(shù)。 如發(fā)送1110001，采用奇校驗(yàn)時(shí)，奇偶位校驗(yàn)為1，即傳輸11100011。接收器檢查接收到的數(shù)據(jù)的1的個(gè)數(shù)為奇數(shù)，就認(rèn)為 無(wú)錯(cuò)誤發(fā)生。若采用偶校驗(yàn)時(shí)，發(fā)送的二進(jìn)制碼是？第7頁(yè)，共23頁(yè)。已知字符T的ASCII碼值的十進(jìn)制表示為84，如果將最高位設(shè)置為奇校驗(yàn)位，則字符M的ASCII碼值設(shè)置奇校驗(yàn)位后，它的二進(jìn)制表示為（ ） A.01001101 B.11001101 C.01101011 D.10111101 解答：M的ASCII碼77，二進(jìn)制表示為01001101，里面有4個(gè)1所

5、以奇偶校驗(yàn)取值為1，設(shè)置于最高位后就是B了。第8頁(yè)，共23頁(yè)。采用奇偶校驗(yàn)時(shí)，若其中2位同時(shí)發(fā)生錯(cuò)誤，則會(huì)發(fā)生沒(méi)有檢測(cè)錯(cuò)誤的情況。所以奇偶檢驗(yàn)雖然簡(jiǎn)單，但并不是一種安全的差錯(cuò)控制方法。一般，在低速傳輸時(shí)，出錯(cuò)概率較低，效果還可以令人滿意。而當(dāng)傳輸數(shù)據(jù)速率較高或噪聲持續(xù)時(shí)間較長(zhǎng)時(shí)，由于可能發(fā)生多位出錯(cuò)，差錯(cuò)檢驗(yàn)的結(jié)果很可能是錯(cuò)誤的。 第9頁(yè)，共23頁(yè)。ASCII編碼 ASCII（American Standard Code for Information Interchange，美國(guó)標(biāo)準(zhǔn)信息交換代碼）是基于拉丁字母的一套電腦編碼系統(tǒng)，它是現(xiàn)今最通用的單字節(jié)編碼系統(tǒng)。 在計(jì)算機(jī)中，所有的數(shù)據(jù)在存儲(chǔ)

6、和運(yùn)算時(shí)都要使用二進(jìn)制數(shù)表示（因?yàn)橛?jì)算機(jī)用高電平和低電平分別表示1和0），例如，像a、b、c、d這樣的52個(gè)字母（包括大寫）、以及0、1等數(shù)字還有一些常用的符號(hào)（例如*、#、等）在計(jì)算機(jī)中存儲(chǔ)時(shí)都要使用二進(jìn)制數(shù)來(lái)表示，而具體用哪些二進(jìn)制數(shù)字表示哪個(gè)符號(hào)，當(dāng)然每個(gè)人都可以約定自己的一套（這就叫編碼），而大家如果要想互相通信而不造成混亂，那么大家就必須使用相同的編碼規(guī)則，于是美國(guó)有關(guān)的標(biāo)準(zhǔn)化組織就出臺(tái)了ASCII編碼，統(tǒng)一規(guī)定了上述常用符號(hào)用哪些二進(jìn)制數(shù)來(lái)表示。第10頁(yè)，共23頁(yè)。 ASCII 碼使用指定的7 位或8 位二進(jìn)制數(shù)組合來(lái)表示128 或256 種可能的字符。標(biāo)準(zhǔn)ASCII 碼也叫基礎(chǔ)A

7、SCII碼，使用7 位二進(jìn)制數(shù)來(lái)表示所有的大寫和小寫字母，數(shù)字0 到9、標(biāo)點(diǎn)符號(hào)以及在美式英語(yǔ)中使用的特殊控制字符。例如，A的7位ASCII編碼為1000001。下圖為7位ASCII代碼表。第11頁(yè)，共23頁(yè)。d3 d2 d1d0位0 d6 d5d4位0000010100111001011101110000NULDELSP0Pp0001SOHDC1！1AQaq0010STXDC22BRbr0011ETXDC33CScs0100EOTDC44DTdt0101ENQNAK5EUeu0110ACKSYN6FVfv0111BELETB7GWgw1000BSCAN8HXhx1001HTEM9IYiy10

8、10LFSUB：JZjz1011VTESCKk1100FFFS，Ll1101CRGSMm1110SORSNn1111SIHSOoDEL第12頁(yè)，共23頁(yè)。4、循環(huán)冗余碼校驗(yàn) 奇偶校驗(yàn)作為一種檢驗(yàn)碼雖然簡(jiǎn)單，但是漏檢率太高。目前，在計(jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)通信中用得最廣泛的檢錯(cuò)碼是一種漏檢率低得多也便于實(shí)現(xiàn)的循環(huán)冗余碼CRC（Cyclic Redundancy Code）。CRC是一種較復(fù)雜的校驗(yàn)方法，又稱多項(xiàng)式碼，是通過(guò)多項(xiàng)式除法檢測(cè)差錯(cuò)的方法。這種編碼對(duì)隨機(jī)差錯(cuò)和突發(fā)差錯(cuò)均能以較低的冗余度進(jìn)行嚴(yán)格的檢查，有很強(qiáng)的檢錯(cuò)能力。 第13頁(yè)，共23頁(yè)。 CRC碼稱為多項(xiàng)式碼。這是因?yàn)槿魏我粋€(gè)由二進(jìn)制數(shù)位串組

9、成的代碼都可以和一個(gè)只含有0和1兩個(gè)系數(shù)的多項(xiàng)式建立一一對(duì)應(yīng)的關(guān)系。 x的最高冪次對(duì)應(yīng)二進(jìn)制數(shù)的最高位，以下各位對(duì)應(yīng)多項(xiàng)式的各冪次，有此冪次項(xiàng)對(duì)應(yīng)1，無(wú)此冪次項(xiàng)對(duì)應(yīng)0?？梢钥闯觯簒的最高冪次為R，轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)有R+1位。(因?yàn)閺膞的0次冪算起) 代碼1011011對(duì)應(yīng)的多項(xiàng)式為 x6 + x4 + x3 +1 而多項(xiàng)式x5 + x4 + x2 + x對(duì)應(yīng)的代碼為110110 第14頁(yè)，共23頁(yè)。 CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗(yàn)的信息，后部分是校驗(yàn)碼，如果CRC碼共長(zhǎng)N個(gè)bit，信息碼長(zhǎng)K個(gè)bit，就稱為(N,K)碼。對(duì)于一個(gè)給定的（N，K）碼，可以證明存在一個(gè)最高

10、次冪為N-K=R的多項(xiàng)式G(x)，可根據(jù)其生成信息的校驗(yàn)碼，所以G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。 第15頁(yè)，共23頁(yè)。 CRC編碼步驟：（1）給定一個(gè)生成多項(xiàng)式：G(x)=x4+x3+1,則x的最高次冪是R=4，轉(zhuǎn)換為二進(jìn)制數(shù)碼11001（有R+1=5位）（2）將原信息碼1011001(K=7bit)左移R位(K+R=N)（即后邊補(bǔ)k個(gè)0）得到F(x)=10110010000（3）用F(x)模2除以G(x)對(duì)應(yīng)的二進(jìn)制數(shù)碼，得余數(shù)R(x) ，即為校驗(yàn)碼（4）令F(x)+R(x)=T(x)，即將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼，并傳送T(x)（5）接受方用接收到的T(x)

11、模2除以G(x)（6）察看結(jié)果為0則認(rèn)為無(wú)差錯(cuò)，否則就是有差錯(cuò)要求重傳。第16頁(yè)，共23頁(yè)。模2除法 模2除法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。 多位模2除法采用模2減法，不帶借位的二進(jìn)制減法。第17頁(yè)，共23頁(yè)。循環(huán)冗余校驗(yàn)碼由于具有良好的代數(shù)結(jié)構(gòu)，計(jì)算機(jī)中易于實(shí)現(xiàn)，編碼器簡(jiǎn)單，檢錯(cuò)能力強(qiáng)，故在微機(jī)通信中廣泛使用。循環(huán)冗余檢驗(yàn)碼的糾錯(cuò)能力與校驗(yàn)碼的位數(shù)有關(guān)，校驗(yàn)碼位數(shù)多，檢錯(cuò)能力就強(qiáng)。第18頁(yè)，共23頁(yè)。例1.CRC屬于檢錯(cuò)碼還是糾錯(cuò)碼？如果某一數(shù)據(jù)通信系統(tǒng)采用CRC校驗(yàn)方式，生成多項(xiàng)式G(x)為X4+X3+1，目的結(jié)點(diǎn)接收到二進(jìn)制比特序列為1101111

12、01（含CRC校驗(yàn)碼），判斷傳輸過(guò)程中是否出現(xiàn)了錯(cuò)誤？并解釋原因。 答：屬于檢錯(cuò)碼。出現(xiàn)了差錯(cuò)，因?yàn)橛鄶?shù)為110。第19頁(yè)，共23頁(yè)。例2.利用標(biāo)準(zhǔn)CRC方法傳輸位流10011101，生成多項(xiàng)式為x3+1，請(qǐng)給出實(shí)際被傳輸?shù)奈淮?。假設(shè)在傳輸過(guò)程中左邊第三位變反了，請(qǐng)證明這個(gè)錯(cuò)誤可以在接收端被檢測(cè)出來(lái)。 答：（1）模2除，得余數(shù)，即校驗(yàn)碼。（2）可以檢測(cè)出來(lái)，因?yàn)橛鄶?shù)是100.第20頁(yè)，共23頁(yè)。例3.如果某一數(shù)據(jù)通信系統(tǒng)采用CRC校驗(yàn)方式，生成多項(xiàng)式G(x)為X4+X3+1，目的結(jié)點(diǎn)接收到二進(jìn)制比特序列為1101111101（含CRC校驗(yàn)碼）。請(qǐng)回答以下問(wèn)題：（1）該生成多項(xiàng)式對(duì)應(yīng)的二進(jìn)制比特序列是多少？（2）如果接收到的二進(jìn)制比特序列長(zhǎng)度正確，則發(fā)送端原始二進(jìn)制比特序列的長(zhǎng)度是幾位？（3）判斷傳輸過(guò)程中是否出現(xiàn)了差錯(cuò)？為什么？第21頁(yè)，共23頁(yè)。十進(jìn)制 二進(jìn)制（35）D=( )B 用若干個(gè)2n相加方法；除2取余法35用8421編碼方法，轉(zhuǎn)換成的代碼序列：10001100110101第22頁(yè)，