第7章差錯控制原理

1、第7章差錯控制原理第7章差錯控制原理2差錯產(chǎn)生的原因 信號在傳輸過程中會收到例如脈沖干擾、隨機噪聲干擾等使信號波形失真，從而使接收解調(diào)后的信號產(chǎn)生差錯。 誤比特率是指二進制比特在數(shù)據(jù)傳輸系統(tǒng)中被傳錯的概率，它在數(shù)值上近似等于： Pe = Ne/N 其中，N為傳輸?shù)亩M制比特總數(shù)，Ne為被傳錯的比特數(shù) 信源信宿數(shù)據(jù)噪聲 數(shù)據(jù)+噪聲第7章差錯控制原理3差錯產(chǎn)生的原因兩類噪聲：隨機噪聲：時時處處存在、幅度小、頻帶寬，導(dǎo)致產(chǎn)生的噪聲隨機、離散，前后差錯之間無關(guān)聯(lián)。脈沖噪聲：強度大、持續(xù)時間與數(shù)據(jù)傳輸中每比特的時間相比較長，因而造成錯誤成串出現(xiàn)。信源 通信信道 信宿數(shù)據(jù)噪聲 數(shù)據(jù)+噪聲第7章差錯控制原理

2、4主要內(nèi)容差錯控制基本原理漢明距與檢錯糾錯差錯控制編碼差錯控制方法第7章差錯控制原理5主要內(nèi)容差錯控制基本原理漢明距與檢錯糾錯差錯控制編碼差錯控制方法第7章差錯控制原理6信源編碼與信道編碼在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。信源編碼：模擬信號如果想利用數(shù)字通信系統(tǒng)進行傳輸，就需要將模擬信息源的輸出轉(zhuǎn)化為數(shù)字信號，而這個轉(zhuǎn)化構(gòu)成就稱為信源編碼。脈沖編碼調(diào)制(PCM)、差分脈沖編碼調(diào)制(DPCM) 、增量調(diào)制(DM).信道編碼：又稱差錯控制編碼，是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的

3、或規(guī)律性不強的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號；差錯控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，或進而糾正錯誤。 第7章差錯控制原理7差錯控制基本原理原始數(shù)字信號是分組傳輸?shù)?，例如每k個二進制碼元為一組（稱為信息組），經(jīng)信道編碼后轉(zhuǎn)換為每n個碼元一組的碼字(碼組)，這里nk，分組碼通常表示為(n，k)，其中n=k+r, r是碼組中監(jiān)督碼位的長度,n是編碼碼組的總長度。信道編碼是用增加數(shù)碼，利用“冗余”來提高抗干擾能力的，也就是以降低信息傳輸速率為代價來減少錯誤的，或者說是用削弱有效性來增強可靠性的。 第7章差錯控制原理8增加冗余碼的原因原始數(shù)據(jù)碼本身隨機變化，無任何規(guī)律，通過增加冗余信

4、息使其呈現(xiàn)某種規(guī)律性，從而可以在接收端進行錯誤檢測?？疾?位二進制碼，其中的八個組合可表示八種不同信息，如果只傳輸這三位，則任意一個組合出錯都回變成另一組碼，接受端無法發(fā)現(xiàn)錯誤。許用碼000011101110禁用碼001010100111 其中任一個碼一位出錯，都會其中任一個碼一位出錯，都會變成禁用碼。從而接收端能夠變成禁用碼。從而接收端能夠且只能夠檢測出錯誤。且只能夠檢測出錯誤。 相當(dāng)于用相當(dāng)于用3位二進制表示位二進制表示4個信個信息，從而存在一位冗余。息，從而存在一位冗余。 第7章差錯控制原理9增加冗余碼的原因為了能糾正錯誤，還需要增加冗余碼元。如下表所示，若許用碼只有000,111，其余

5、均為禁用碼組。這相當(dāng)于使用三位二進制碼來代表兩種不同的信息，有兩位碼是冗余的。接收端可檢測出2位以下的錯誤或者糾正1位錯誤許用碼000111禁用碼001010011100101111 當(dāng)收到禁用碼組時當(dāng)收到禁用碼組時100時，可以認(rèn)為時，可以認(rèn)為只有一位出錯，則原始信息為只有一位出錯，則原始信息為000，因為因為111任何一位出錯都不會變成任何一位出錯都不會變成100，此時即檢錯，此時即檢錯1位又能糾錯位又能糾錯1位。位。 若認(rèn)為錯碼不超過若認(rèn)為錯碼不超過2位，則存在兩種位，則存在兩種可能：可能：000錯錯1位或者位或者111錯錯2位。位。第7章差錯控制原理10檢錯碼和糾錯碼按照信道編碼的不同

6、功能，可以將它分為檢錯碼和糾錯碼。檢錯碼僅能檢測誤碼，例如，在計算機串口通信中常用到的奇偶校驗碼等；糾錯碼可以糾正誤碼，當(dāng)然同時具有檢錯的能力，當(dāng)發(fā)現(xiàn)不可糾正的錯誤時可以發(fā)出出錯指示。 第7章差錯控制原理11主要內(nèi)容差錯控制基本原理漢明距與檢錯糾錯差錯控制編碼差錯控制方法第7章差錯控制原理12漢明距離漢明距離又稱碼距，它是指兩個等長二進制碼組之間對應(yīng)位不同的個數(shù)，用來描述碼組之間的不同程度。1()njikiidaa 其中其中aji,aki分別為第分別為第j個碼組和第個碼組和第k個碼組的個碼組的第第i為碼元為碼元;n為碼組長度為碼組長度 一個碼組集合中，任何兩個碼組間的漢明一個碼組集合中，任何兩

7、個碼組間的漢明距離的最小值稱為最小碼距。距離的最小值稱為最小碼距。 最小碼距越大，差錯控制能力越強。最小碼距越大，差錯控制能力越強。第7章差錯控制原理13漢明距離漢明距離又稱碼距，它是指兩個等長二進制碼組之間對應(yīng)位不同的個數(shù)，用來描述碼組之間的不同程度。1()njikiidaa許用碼000011101110許用碼000111 最小碼距為最小碼距為2，接收端能，接收端能夠檢測出夠檢測出1位錯誤。位錯誤。 最小碼距為最小碼距為3，接收端，接收端能夠檢測出能夠檢測出2位錯誤。位錯誤。第7章差錯控制原理14漢明距和檢錯糾錯的關(guān)系當(dāng)碼字用于檢測錯誤時，如果要檢測e個錯誤，則分組碼最小漢明距離d0和e之間

8、的關(guān)系：在圖中用A和B分別表示兩個碼距為d0的碼字，若A發(fā)生e個錯誤，則A就變成以A為球心，e為半徑的球面上的碼字，為了能將這些碼字分辯出來，它們必須距離其最近的碼字B至少有一位的差別01deABed0第7章差錯控制原理15漢明距和檢錯糾錯的關(guān)系當(dāng)碼字用于糾正錯誤時，如果要糾正t個錯誤，則 在圖中用A和B分別表示兩個碼距為d0的碼字，若A發(fā)生t個錯誤，則A就變成以A為球心，t為半徑的球面上的碼字；B發(fā)生t個錯誤，則B就變成以B為球心，t為半徑的球面上的碼字。為了在出現(xiàn)t個錯誤之后，仍能夠分辯出A和B來，那么，A和B之間距離應(yīng)大于2t，最小距離也應(yīng)當(dāng)使兩球體表面相距為1。021dtABtd0t1

9、第7章差錯控制原理16主要內(nèi)容差錯控制基本原理漢明距與檢錯糾錯差錯控制編碼差錯控制方法第7章差錯控制原理17差錯控制編碼奇偶校驗碼：奇偶校驗碼是奇校驗碼和偶校驗碼的統(tǒng)稱，是一種最基本的檢錯碼。它是由n-1位信息元和1位校驗元組成，可以表示成為（n，n-1）。如果是奇校驗碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為奇數(shù)個；如果是偶校驗碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為偶數(shù)個。1230.1nnnaaaa1230.0nnnaaaa第7章差錯控制原理18奇偶校驗碼是最常見的檢錯碼方式，它可以構(gòu)成垂直奇偶校驗、水平奇偶校驗和垂直水平奇偶校驗。垂直奇偶校驗：也稱為字符

10、奇偶校驗。對于單元字符代碼，在字符代碼最后一位加上一個奇偶校驗位b7，使碼組中的1的個數(shù)為奇數(shù)或者偶數(shù)。接收端可以通過校驗接收字符碼組中的1的個數(shù)為偶數(shù)(或奇數(shù))來判斷傳輸是否有差錯。差錯控制編碼第7章差錯控制原理19垂直水平奇偶校驗又叫二維奇偶校驗或方陣校驗。它不僅對水平（行）方向的碼元，而且還對垂直（列）方向的碼元實施奇偶監(jiān)督。 將信息碼組排列成矩陣，每一個碼組寫成一行，然后根據(jù)奇偶校驗原理在垂直和水平兩個方向進行校驗。發(fā)送時需要將校驗位和校驗碼發(fā)送到接收端。1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1

11、 1 0 0 0 01 0 1 0 1 0 1 0 1 0001011 1 0 0 0 1 1 1 1 00第7章差錯控制原理20恒比碼恒比碼中的1和0的個數(shù)保持恒定比例。數(shù)字碼字01234567890 1 1 0 10 1 0 1 11 1 0 0 11 0 1 1 01 1 0 1 00 0 1 1 11 0 1 0 11 1 1 0 00 1 1 1 01 0 0 1 1 若碼長為若碼長為n，碼重為，碼重為w，則此碼的，則此碼的碼字個數(shù)為碼字個數(shù)為 ，禁用碼字?jǐn)?shù)為，禁用碼字?jǐn)?shù)為 。 該碼的檢錯能力較強，除對換差該碼的檢錯能力較強，除對換差錯（錯（1和和0成對的產(chǎn)生錯誤）不能成對的產(chǎn)生錯誤

12、）不能發(fā)現(xiàn)外，其它各種錯誤均能發(fā)現(xiàn)發(fā)現(xiàn)外，其它各種錯誤均能發(fā)現(xiàn)。 國際上通用的電報通信系統(tǒng)中，國際上通用的電報通信系統(tǒng)中，采用采用7中取中取3碼，實踐證明，應(yīng)用碼，實踐證明，應(yīng)用這種碼，使國際電報通信的誤碼這種碼，使國際電報通信的誤碼率保持在以率保持在以 10-6 下。下。 35CwnC2nwnC第7章差錯控制原理21正反碼校驗碼取決于信息碼中1的數(shù)目，或者與信息碼元相同(正碼)，或者與信息碼元相反(反碼)。博多碼：當(dāng)信息碼組中有奇數(shù)個1時，校驗碼與信息碼相同，當(dāng)信息碼中有歐數(shù)個1時，校驗碼是信息碼的反碼。如：11001校驗碼為11001，而11101校驗碼為00010。接收端將接收的碼組中的

13、信息碼與校驗碼模2加，得到一個5單位合成碼組作為校驗碼。如果信息碼奇數(shù)個1，合成碼就是校驗碼；如果信息碼是歐數(shù)個，則合成碼的反碼為校驗碼。對根據(jù)校驗碼中1的個數(shù)依據(jù)下表進行判決：第7章差錯控制原理22正反碼譯碼判決表類型類型校驗碼組形式校驗碼組形式譯碼判決譯碼判決1全全0傳輸正確傳輸正確24個個1，1個個0校驗碼中校驗碼中0對應(yīng)位置的對應(yīng)位置的1位信息碼出錯位信息碼出錯34個個0，1個個1校驗碼中校驗碼中1對應(yīng)的對應(yīng)的1位監(jiān)督碼出錯位監(jiān)督碼出錯4其他其他大于大于1位的傳輸錯誤位的傳輸錯誤 信息碼 校驗碼 信息碼有奇數(shù)個1判決校驗碼判決校驗碼信息碼有歐數(shù)個1取反01101 0110101010

14、1011100000111010000000010第7章差錯控制原理23循環(huán)冗余校驗編碼又稱CRC碼，糾錯能力強，采用多項式編碼的方法。目前廣泛應(yīng)用的一種糾錯編碼。二進制可使用多項式來表示：如10111可表示為：x4+x2+x+1,多項式的系數(shù)就代表二進制10111.對長度為n的二進制序列，存在一個以x為基的n-1次多項式。00000101001x100101111x2x2+1x2+x+1第7章差錯控制原理24在發(fā)送端，將要發(fā)送的數(shù)據(jù)比特序列作為一個多項式T(x)的系數(shù)，并選定一個k次冪的生成多項式G(x)。對于二進制乘法,該步意味著數(shù)據(jù)比特序列左移k位.CRC基本原理 CRC生成多項式生成多

15、項式G(x)標(biāo)準(zhǔn)：使用時從中選擇：標(biāo)準(zhǔn)：使用時從中選擇：CRC-12 G(x)=x12+x11+x3+x2+1CRC-16 G(x)=x16+x15+x2+1T(x)T(x) xk k位T(x) xk R(x)G(x) 將將T(x)xk除以生成多項式除以生成多項式G(x) 其中其中Q(x)為商，為商，R(x)為余數(shù)。為余數(shù)。 將將T(x)xk+R(x)所對應(yīng)的比特序列作為一個整體發(fā)送所對應(yīng)的比特序列作為一個整體發(fā)送。( )( )( )( )( )kT x xR xQ xG xG x第7章差錯控制原理25校驗過程 (接收端)在接收端，對接收序列所對應(yīng)的多項式T(x)xk進行與發(fā)送端同樣的運算，即

16、：比較R(x)和R(x)，如果R(x)=R(x)，認(rèn)為傳輸正確，否則認(rèn)為傳輸錯誤。( )( )( )( )( )kTx xR xQ xG xG xT(x) xk R(x)( )()(kTR xQ xG xxxGx?第7章差錯控制原理26CRC例子假設(shè)發(fā)送數(shù)據(jù)為110011;生成多項式為 x4+x3+1，k=4，所對應(yīng)的序列為11001；將發(fā)送數(shù)據(jù)序列左移4位，新的序列為：1100110000;按模2算法，將生成的新序列用多項式序列去除，10000111001 11001100001100110000110011001Q(x)T(x)xkR(x)發(fā)送新序列為：110011 1001如果沒有發(fā)送失

17、敗那么接收端收到的比特序列一定能被同一個多項式整除。1000011100111100001111001111001第7章差錯控制原理27CRC的性能CRC生成的多項式結(jié)構(gòu)與檢錯效果已經(jīng)過嚴(yán)格的數(shù)學(xué)分析。能檢錯出全部單個錯誤、能檢測出全部隨機的2位錯誤能檢測出全部奇數(shù)個錯誤。能檢測出全部長度小于等于k位的突發(fā)錯誤能以1-(1/2)k-1的概率檢測出長度為k+1位突發(fā)錯誤。第7章差錯控制原理28發(fā)送方將數(shù)據(jù)單元分成k段，每段n比特；將各段相加求和；對和取反得到校驗和；將校驗和字段附加到數(shù)據(jù)序列末尾與數(shù)據(jù)一起發(fā)送。校驗和編碼 接收端將接收到的數(shù)據(jù)單元分成長度為接收端將接收到的數(shù)據(jù)單元分成長度為n比比

18、特的段；將所有分段相加求和；對和求反特的段；將所有分段相加求和；對和求反；如果結(jié)果為；如果結(jié)果為0，表示傳輸正確。，表示傳輸正確。n n n n n n n n 取反取反0 ？第7章差錯控制原理29校驗和例子例：假定要發(fā)送16位數(shù)據(jù)11001,采用8位校驗和，則發(fā)送比特為： 10101001 00111001 +取反發(fā)送端+取反接收端 能檢測所有奇數(shù)個錯誤及大多數(shù)偶數(shù)個錯誤，但能檢測所有奇數(shù)個錯誤及大多數(shù)偶數(shù)個錯誤，但如果某一段中的一個或多個比特損壞，下一個分如果某一段中的一個或多個比特損壞，下一個分段中具有相反值的對應(yīng)位也被破壞，這些列的和段中具有相反值的對應(yīng)位也被破壞，這些列的和保持不變，

19、從而無法檢測出錯。保持不變，從而無法檢測出錯。01+取反出錯情況0+取反第7章差錯控制原理30主要內(nèi)容差錯控制基本原理漢明距與檢錯糾錯差錯控制編碼差錯控制方法第7章差錯控制原理31差錯控制方法發(fā)送端對信源數(shù)據(jù)進行糾錯編碼，然后送信道傳輸。接收端對信號譯碼，如果檢測傳輸中的錯誤則自動糾正。優(yōu)點：不需要反向信道，能用于單工通信，也可用于一點對多點通信。缺點：譯碼設(shè)備復(fù)雜，為糾正錯誤需要附加較多的冗余碼元，傳輸效率低。 向前糾錯向前糾錯FEC：又稱自動糾錯，其數(shù)學(xué)模型如下圖：又稱自動糾錯，其數(shù)學(xué)模型如下圖：信源 FEC編碼信道FEC譯碼信宿第7章差錯控制原理32差錯控制方法自動請求重發(fā)(ARQ):用于檢錯編碼，接收端通過譯碼能夠發(fā)現(xiàn)傳輸錯誤，但是無法糾正，因此采用自動請求重發(fā)的工作方式。 發(fā)送端在將數(shù)據(jù)發(fā)向信道的同時還進行緩存，以備發(fā)送端在將數(shù)據(jù)發(fā)向信道的同時還進行緩存，以備重發(fā)使用。如果接到重發(fā)請求，則將該數(shù)據(jù)放入緩重發(fā)使用。如果接到重發(fā)請求，則將該數(shù)據(jù)放入緩存器重