《差錯(cuò)控制原》PPT課件.ppt

第7章 差錯(cuò)控制原理,石高濤 天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2,差錯(cuò)產(chǎn)生的原因,信號(hào)在傳輸過程中會(huì)收到例如脈沖干擾、隨機(jī)噪聲干擾等使信號(hào)波形失真，從而使接收解調(diào)后的信號(hào)產(chǎn)生差錯(cuò)。 誤比特率是指二進(jìn)制比特在數(shù)據(jù)傳輸系統(tǒng)中被傳錯(cuò)的概率，它在數(shù)值上近似等于： Pe = Ne/N 其中，N為傳輸?shù)亩M(jìn)制比特總數(shù)，Ne為被傳錯(cuò)的比特?cái)?shù),信源,通信信道,信宿,數(shù)據(jù),噪聲,數(shù)據(jù)+噪聲,3,差錯(cuò)產(chǎn)生的原因,兩類噪聲： 隨機(jī)噪聲：時(shí)時(shí)處處存在、幅度小、頻帶寬，導(dǎo)致產(chǎn)生的噪聲隨機(jī)、離散，前后差錯(cuò)之間無關(guān)聯(lián)。 脈沖噪聲：強(qiáng)度大、持續(xù)時(shí)間與數(shù)據(jù)傳輸中每比特的時(shí)間相比較長(zhǎng)，因而造成錯(cuò)誤成串出現(xiàn)。,信源,通信信道,信宿,數(shù)據(jù),噪聲,數(shù)據(jù)+噪聲,4,主要內(nèi)容,差錯(cuò)控制基本原理 漢明距與檢錯(cuò)糾錯(cuò) 差錯(cuò)控制編碼 差錯(cuò)控制方法,5,主要內(nèi)容,差錯(cuò)控制基本原理 漢明距與檢錯(cuò)糾錯(cuò) 差錯(cuò)控制編碼 差錯(cuò)控制方法,6,信源編碼與信道編碼,在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號(hào)傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。 信源編碼：模擬信號(hào)如果想利用數(shù)字通信系統(tǒng)進(jìn)行傳輸，就需要將模擬信息源的輸出轉(zhuǎn)化為數(shù)字信號(hào)，而這個(gè)轉(zhuǎn)化構(gòu)成就稱為信源編碼。脈沖編碼調(diào)制(PCM)、差分脈沖編碼調(diào)制(DPCM) 、增量調(diào)制(DM). 信道編碼：又稱差錯(cuò)控制編碼，是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強(qiáng)的原始數(shù)字信號(hào)變?yōu)橛幸?guī)律的數(shù)字信號(hào)；差錯(cuò)控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯(cuò)誤，或進(jìn)而糾正錯(cuò)誤。,7,差錯(cuò)控制基本原理,原始數(shù)字信號(hào)是分組傳輸?shù)?，例如每k個(gè)二進(jìn)制碼元為一組（稱為信息組）， 經(jīng)信道編碼后轉(zhuǎn)換為每n個(gè)碼元一組的碼字(碼組)，這里nk，分組碼通常表示為(n，k)，其中n=k+r, r是碼組中監(jiān)督碼位的長(zhǎng)度,n是編碼碼組的總長(zhǎng)度。 信道編碼是用增加數(shù)碼，利用“冗余”來提高抗干擾能力的，也就是以降低信息傳輸速率為代價(jià)來減少錯(cuò)誤的，或者說是用削弱有效性來增強(qiáng)可靠性的。,8,增加冗余碼的原因,原始數(shù)據(jù)碼本身隨機(jī)變化，無任何規(guī)律，通過增加冗余信息使其呈現(xiàn)某種規(guī)律性，從而可以在接收端進(jìn)行錯(cuò)誤檢測(cè)。 考察3位二進(jìn)制碼，其中的八個(gè)組合可表示八種不同信息，如果只傳輸這三位，則任意一個(gè)組合出錯(cuò)都回變成另一組碼，接受端無法發(fā)現(xiàn)錯(cuò)誤。,許用碼 000 011 101 110,禁用碼 001 010 100 111,其中任一個(gè)碼一位出錯(cuò)，都會(huì)變成禁用碼。從而接收端能夠且只能夠檢測(cè)出錯(cuò)誤。 相當(dāng)于用3位二進(jìn)制表示4個(gè)信息，從而存在一位冗余。,9,增加冗余碼的原因,為了能糾正錯(cuò)誤，還需要增加冗余碼元。如下表所示，若許用碼只有000,111，其余均為禁用碼組。 這相當(dāng)于使用三位二進(jìn)制碼來代表兩種不同的信息，有兩位碼是冗余的。 接收端可檢測(cè)出2位以下的錯(cuò)誤或者糾正1位錯(cuò)誤,許用碼 000 111,禁用碼 001 010 011 100 101 111,當(dāng)收到禁用碼組時(shí)100時(shí)，可以認(rèn)為只有一位出錯(cuò)，則原始信息為000，因?yàn)?11任何一位出錯(cuò)都不會(huì)變成100，此時(shí)即檢錯(cuò)1位又能糾錯(cuò)1位。 若認(rèn)為錯(cuò)碼不超過2位，則存在兩種可能：000錯(cuò)1位或者111錯(cuò)2位。,10,檢錯(cuò)碼和糾錯(cuò)碼,按照信道編碼的不同功能，可以將它分為檢錯(cuò)碼和糾錯(cuò)碼。 檢錯(cuò)碼僅能檢測(cè)誤碼，例如，在計(jì)算機(jī)串口通信中常用到的奇偶校驗(yàn)碼等； 糾錯(cuò)碼可以糾正誤碼，當(dāng)然同時(shí)具有檢錯(cuò)的能力，當(dāng)發(fā)現(xiàn)不可糾正的錯(cuò)誤時(shí)可以發(fā)出出錯(cuò)指示。,11,主要內(nèi)容,差錯(cuò)控制基本原理 漢明距與檢錯(cuò)糾錯(cuò) 差錯(cuò)控制編碼 差錯(cuò)控制方法,12,漢明距離,漢明距離又稱碼距，它是指兩個(gè)等長(zhǎng)二進(jìn)制碼組之間對(duì)應(yīng)位不同的個(gè)數(shù)，用來描述碼組之間的不同程度。,其中aji,aki分別為第j個(gè)碼組和第k個(gè)碼組的第i為碼元;n為碼組長(zhǎng)度 一個(gè)碼組集合中，任何兩個(gè)碼組間的漢明距離的最小值稱為最小碼距。 最小碼距越大，差錯(cuò)控制能力越強(qiáng)。,13,漢明距離,漢明距離又稱碼距，它是指兩個(gè)等長(zhǎng)二進(jìn)制碼組之間對(duì)應(yīng)位不同的個(gè)數(shù)，用來描述碼組之間的不同程度。,許用碼 000 011 101 110,許用碼 000 111,最小碼距為2，接收端能夠檢測(cè)出1位錯(cuò)誤。,最小碼距為3，接收端能夠檢測(cè)出2位錯(cuò)誤。,14,漢明距和檢錯(cuò)糾錯(cuò)的關(guān)系,當(dāng)碼字用于檢測(cè)錯(cuò)誤時(shí)，如果要檢測(cè)e個(gè)錯(cuò)誤，則分組碼最小漢明距離d0和e之間的關(guān)系： 在圖中用A和B分別表示兩個(gè)碼距為d0的碼字，若A發(fā)生e個(gè)錯(cuò)誤，則A就變成以A為球心，e為半徑的球面上的碼字，為了能將這些碼字分辯出來，它們必須距離其最近的碼字B至少有一位的差別,A,B,e,d0,15,漢明距和檢錯(cuò)糾錯(cuò)的關(guān)系,當(dāng)碼字用于糾正錯(cuò)誤時(shí)，如果要糾正t個(gè)錯(cuò)誤，則 在圖中用A和B分別表示兩個(gè)碼距為d0的碼字，若A發(fā)生t個(gè)錯(cuò)誤，則A就變成以A為球心，t為半徑的球面上的碼字；B發(fā)生t個(gè)錯(cuò)誤，則B就變成以B為球心，t為半徑的球面上的碼字。為了在出現(xiàn)t個(gè)錯(cuò)誤之后，仍能夠分辯出A和B來，那么，A和B之間距離應(yīng)大于2t，最小距離也應(yīng)當(dāng)使兩球體表面相距為1。,A,B,t,d0,t,1,16,主要內(nèi)容,差錯(cuò)控制基本原理 漢明距與檢錯(cuò)糾錯(cuò) 差錯(cuò)控制編碼 差錯(cuò)控制方法,17,差錯(cuò)控制編碼,奇偶校驗(yàn)碼：奇偶校驗(yàn)碼是奇校驗(yàn)碼和偶校驗(yàn)碼的統(tǒng)稱，是一種最基本的檢錯(cuò)碼。它是由n-1位信息元和1位校驗(yàn)元組成，可以表示成為（n，n-1）。 如果是奇校驗(yàn)碼，在附加上一個(gè)監(jiān)督元以后，碼長(zhǎng)為n的碼字中“1”的個(gè)數(shù)為奇數(shù)個(gè)； 如果是偶校驗(yàn)碼，在附加上一個(gè)監(jiān)督元以后，碼長(zhǎng)為n的碼字中“1”的個(gè)數(shù)為偶數(shù)個(gè)。,18,奇偶校驗(yàn)碼是最常見的檢錯(cuò)碼方式，它可以構(gòu)成垂直奇偶校驗(yàn)、水平奇偶校驗(yàn)和垂直水平奇偶校驗(yàn)。 垂直奇偶校驗(yàn)：也稱為字符奇偶校驗(yàn)。對(duì)于單元字符代碼，在字符代碼最后一位加上一個(gè)奇偶校驗(yàn)位b7，使碼組中的1的個(gè)數(shù)為奇數(shù)或者偶數(shù)。 接收端可以通過校驗(yàn)接收字符碼組中的1的個(gè)數(shù)為偶數(shù)(或奇數(shù))來判斷傳輸是否有差錯(cuò)。,差錯(cuò)控制編碼,19,垂直水平奇偶校驗(yàn),又叫二維奇偶校驗(yàn)或方陣校驗(yàn)。它不僅對(duì)水平（行）方向的碼元，而且還對(duì)垂直（列）方向的碼元實(shí)施奇偶監(jiān)督。 將信息碼組排列成矩陣，每一個(gè)碼組寫成一行，然后根據(jù)奇偶校驗(yàn)原理在垂直和水平兩個(gè)方向進(jìn)行校驗(yàn)。 發(fā)送時(shí)需要將校驗(yàn)位和校驗(yàn)碼發(fā)送到接收端。,20,恒比碼,恒比碼中的1和0的個(gè)數(shù)保持恒定比例。,若碼長(zhǎng)為n，碼重為w，則此碼的碼字個(gè)數(shù)為 ，禁用碼字?jǐn)?shù)為 。 該碼的檢錯(cuò)能力較強(qiáng)，除對(duì)換差錯(cuò)（1和0成對(duì)的產(chǎn)生錯(cuò)誤）不能發(fā)現(xiàn)外，其它各種錯(cuò)誤均能發(fā)現(xiàn)。 國(guó)際上通用的電報(bào)通信系統(tǒng)中，采用7中取3碼，實(shí)踐證明，應(yīng)用這種碼，使國(guó)際電報(bào)通信的誤碼率保持在以 10-6 下。,21,正反碼,校驗(yàn)碼取決于信息碼中1的數(shù)目，或者與信息碼元相同(正碼)，或者與信息碼元相反(反碼)。 博多碼：當(dāng)信息碼組中有奇數(shù)個(gè)1時(shí)，校驗(yàn)碼與信息碼相同，當(dāng)信息碼中有歐數(shù)個(gè)1時(shí)，校驗(yàn)碼是信息碼的反碼。如：11001校驗(yàn)碼為11001，而11101校驗(yàn)碼為00010。 接收端將接收的碼組中的信息碼與校驗(yàn)碼模2加，得到一個(gè)5單位合成碼組作為校驗(yàn)碼。如果信息碼奇數(shù)個(gè)1，合成碼就是校驗(yàn)碼；如果信息碼是歐數(shù)個(gè)，則合成碼的反碼為校驗(yàn)碼。 對(duì)根據(jù)校驗(yàn)碼中1的個(gè)數(shù)依據(jù)下表進(jìn)行判決：,22,正反碼譯碼判決表,信息碼 校驗(yàn)碼,信息碼有奇數(shù)個(gè)1,判決校驗(yàn)碼,判決校驗(yàn)碼,信息碼有歐數(shù)個(gè)1取反,01101 01101 01010 10111,00000,11101,00000,00010,23,循環(huán)冗余校驗(yàn)編碼,又稱CRC碼，糾錯(cuò)能力強(qiáng)，采用多項(xiàng)式編碼的方法。目前廣泛應(yīng)用的一種糾錯(cuò)編碼。 二進(jìn)制可使用多項(xiàng)式來表示：如10111可表示為：x4+x2+x+1,多項(xiàng)式的系數(shù)就代表二進(jìn)制10111. 對(duì)長(zhǎng)度為n的二進(jìn)制序列，存在一個(gè)以x為基的n-1次多項(xiàng)式。,24,在發(fā)送端，將要發(fā)送的數(shù)據(jù)比特序列作為一個(gè)多項(xiàng)式T(x)的系數(shù)，并選定一個(gè)k次冪的生成多項(xiàng)式G(x)。對(duì)于二進(jìn)制乘法,該步意味著數(shù)據(jù)比特序列左移k位.,CRC基本原理,CRC生成多項(xiàng)式G(x)標(biāo)準(zhǔn)：使用時(shí)從中選擇：,CRC-12 G(x)=x12+x11+x3+x2+1,CRC-16 G(x)=x16+x15+x2+1,T(x),T(x) xk k位,T(x) xk R(x),G(x),將T(x)xk除以生成多項(xiàng)式G(x) 其中Q(x)為商，R(x)為余數(shù)。 將T(x)xk+R(x)所對(duì)應(yīng)的比特序列作為一個(gè)整體發(fā)送。,25,校驗(yàn)過程 (接收端),在接收端，對(duì)接收序列所對(duì)應(yīng)的多項(xiàng)式T(x)xk進(jìn)行與發(fā)送端同樣的運(yùn)算，即： 比較R(x)和R(x)，如果R(x)=R(x)，認(rèn)為傳輸正確，否則認(rèn)為傳輸錯(cuò)誤。,T(x) xk R(x),26,CRC例子,假設(shè)發(fā)送數(shù)據(jù)為110011;生成多項(xiàng)式為 x4+x3+1，k=4，所對(duì)應(yīng)的序列為11001； 將發(fā)送數(shù)據(jù)序列左移4位，新的序列為：1100110000; 按模2算法，將生成的新序列用多項(xiàng)式序列去除，,Q(x),T(x)xk,R(x),發(fā)送新序列為：110011 1001,如果沒有發(fā)送失敗那么接收端收到的比特序列一定能被同一個(gè)多項(xiàng)式整除。,27,CRC的性能,CRC生成的多項(xiàng)式結(jié)構(gòu)與檢錯(cuò)效果已經(jīng)過嚴(yán)格的數(shù)學(xué)分析。 能檢錯(cuò)出全部單個(gè)錯(cuò)誤、能檢測(cè)出全部隨機(jī)的2位錯(cuò)誤 能檢測(cè)出全部奇數(shù)個(gè)錯(cuò)誤。 能檢測(cè)出全部長(zhǎng)度小于等于k位的突發(fā)錯(cuò)誤 能以1-(1/2)k-1的概率檢測(cè)出長(zhǎng)度為k+1位突發(fā)錯(cuò)誤。,28,發(fā)送方將數(shù)據(jù)單元分成k段，每段n比特；將各段相加求和；對(duì)和取反得到校驗(yàn)和；將校驗(yàn)和字段附加到數(shù)據(jù)序列末尾與數(shù)據(jù)一起發(fā)送。,校驗(yàn)和編碼,接收端將接收到的數(shù)據(jù)單元分成長(zhǎng)度為n比特的段；將所有分段相加求和；對(duì)和求反；如果結(jié)果為0，表示傳輸正確。,n n n n,n n n n,29,校驗(yàn)和例子,例：假定要發(fā)送16位數(shù)據(jù)1010100100111001,采用8位校驗(yàn)和，則發(fā)送比特為： 10101001 00111001 00011101,10101001,00111001,+,11100010,00011101,取反,發(fā)送端,10101001,00111001,+,00011101,00000000,取反,接收端,11111111,能檢測(cè)所有奇數(shù)個(gè)錯(cuò)誤及大多數(shù)偶數(shù)個(gè)錯(cuò)誤，但如果某一段中的一個(gè)或多個(gè)比特?fù)p壞，下一個(gè)分段中具有相反值的對(duì)應(yīng)位也被破壞，這些列的和保持不變，從而無法檢測(cè)出錯(cuò)。,00101001,10111001,+,00011101,00000000,取反,11111111,出錯(cuò)情況,00101001,00111001,+,00011101,10000000,取反,01111111,30,主要內(nèi)容,差錯(cuò)控制基本原理 漢明距與檢錯(cuò)糾錯(cuò) 差錯(cuò)控制編碼 差錯(cuò)控制方法,31,差錯(cuò)控制方法,發(fā)送端對(duì)信源數(shù)據(jù)進(jìn)行糾錯(cuò)編碼，然后送信道傳輸。 接收端對(duì)信號(hào)譯碼，如果檢測(cè)傳輸中的錯(cuò)誤則自動(dòng)糾正。 優(yōu)點(diǎn)：不需要反向信道，能用于單工通信，也可用于一點(diǎn)對(duì)多點(diǎn)通信。 缺點(diǎn)：譯碼設(shè)備復(fù)雜，為糾正錯(cuò)誤需要附加較多的冗余碼元，傳輸效率低。,向前糾錯(cuò)FEC：又稱自動(dòng)糾錯(cuò)，其數(shù)學(xué)模型如下圖：,信源,FEC編碼,信道,FEC譯碼,信宿,32,差錯(cuò)控制方法,自動(dòng)請(qǐng)求重發(fā)(ARQ):用于檢錯(cuò)編碼，接收端通過譯碼能夠發(fā)現(xiàn)傳輸錯(cuò)誤，但是無法糾正，因此采用自動(dòng)請(qǐng)求重發(fā)的工作方式。,發(fā)送端在將數(shù)據(jù)發(fā)向信道的同時(shí)還進(jìn)行緩存，以備重發(fā)使用。如果接到重發(fā)請(qǐng)求，則將該數(shù)據(jù)放入緩存器重新編碼發(fā)送。 接收端通過判決器檢測(cè)，如果正確接收則發(fā)送ACK；在檢測(cè)到錯(cuò)誤時(shí)發(fā)送NACK，要求重發(fā)。,信源,編碼器,正向信道,譯碼器,信宿,緩存器,重發(fā)控制器,反向信道,重發(fā)判決器,33,自動(dòng)請(qǐng)求重發(fā)的實(shí)現(xiàn)方式,停止-等待方式：每發(fā)送一個(gè)數(shù)據(jù)分組后就停止等待接收端的應(yīng)答信號(hào)。如果發(fā)送端收到確認(rèn)信號(hào)就發(fā)送下一組數(shù)據(jù)，如果收到否認(rèn)信號(hào)就重發(fā)。,34,連續(xù)重發(fā)方式,發(fā)送端可以連續(xù)向接收端發(fā)送數(shù)據(jù)，接收端對(duì)接收到的數(shù)據(jù)進(jìn)行校驗(yàn)，根據(jù)結(jié)果向發(fā)送端發(fā)送應(yīng)答信號(hào)。 當(dāng)發(fā)送端接收到否認(rèn)信號(hào)就退回到有錯(cuò)的數(shù)據(jù)分組，并重發(fā)此分組及以后的分組。 接收端丟棄有錯(cuò)誤的分組及該分組之后的分組，直到有錯(cuò)誤的分組被正確接收到為止。,0 1 2 3 4 5 2 3 4 5 6,0 1 2 3 4 5 2 3 4 5 6,丟棄,35,選擇重發(fā)方式,選擇重發(fā)方式與連續(xù)重發(fā)方式的不同在于：發(fā)送端僅重傳接收出