計算機網(wǎng)絡通信原理概論課件

第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制1（1）差錯產(chǎn)生的原因數(shù)據(jù)通信系統(tǒng)的基本任務是高效率而無差錯地傳送數(shù)據(jù)。數(shù)據(jù)信號在通信線路中傳輸時，難免受到來自信道內部和外部的干擾，從而引起信號的失真，導致數(shù)據(jù)傳輸錯誤。傳輸出錯的原因：一是信道的加性噪聲；二是由于傳輸總特性（包括收、發(fā)濾波器和信道的特性）不理想引起的碼間串擾。噪聲是影響數(shù)據(jù)傳輸質量的主要因素。根據(jù)產(chǎn)生的原因可以將噪聲分為四類：熱噪聲、交調噪聲、串音和脈沖噪聲四類。（1）差錯產(chǎn)生的原因數(shù)據(jù)通信系統(tǒng)的基本任務是高效率而無差錯地2（2）噪聲的類型熱噪聲是由帶電粒子在導電介質中的布朗運動引起的，它存在于任何工作在絕對零度以上的電路或系統(tǒng)中。熱噪聲屬于高斯白噪聲，其概率密度函數(shù)滿足正態(tài)分布統(tǒng)計特性，同時它的功率譜密度函數(shù)是均勻分布的（常數(shù)）。熱噪聲的特點是：時刻存在、不可排除、幅度較小、強度與頻率無關，但頻譜很寬，是一類隨機的噪聲。（2）噪聲的類型熱噪聲3噪聲的類型交調噪聲是一種附加的頻率干擾。由于通信系統(tǒng)的非線性，將導致進入通信系統(tǒng)的不同頻率的信號在系統(tǒng)的輸出端產(chǎn)生這些頻率之間的差頻信號或倍頻信號及其組合，這就是交調噪聲。對于交調噪聲可以通過適當?shù)恼{制技術，人為地校正系統(tǒng)的非線性部分得到補償。噪聲的類型交調噪聲4噪聲的類型串音是一個通路的信號在相鄰的另一個通路引起的干擾現(xiàn)象。這是由于信號線路之間的電磁感應引起的有害耦合。為了消除線路之間的有害耦合，可以將每一對線擰成一定扭絞節(jié)距的線纜。噪聲的類型串音5噪聲的類型脈沖噪聲是由于電火花或其他原因造成的突發(fā)振幅很大、持續(xù)時間比間隔時間短得多的離散脈沖耦合到信號通路中的干擾。脈沖噪聲也稱為沖擊噪聲，它將引起一連串的數(shù)據(jù)比特出錯，它是數(shù)據(jù)傳輸差錯的主要根源。脈沖噪聲產(chǎn)生的干擾很難消除，只能采用差錯控制的方法來實現(xiàn)可靠傳輸。噪聲的類型脈沖噪聲6（3）差錯的類型隨機差錯指數(shù)據(jù)單元中的單比特差錯。它通常由傳輸信道的熱噪聲引起。突發(fā)差錯指數(shù)據(jù)單元中的兩個或兩個以上的比特發(fā)生成串密集性的差錯，第一個錯誤比特到最后一個錯誤比特之間的位數(shù)稱為突發(fā)長度。沖擊噪聲持續(xù)的時間通常大于數(shù)據(jù)傳輸中每比特的發(fā)送時間，因而會引起相鄰的多個數(shù)據(jù)位出錯，從而導致突發(fā)差錯。（3）差錯的類型隨機差錯7有差錯的信道類型按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道：

恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。突發(fā)信道：

具有脈沖干擾的信道，是典型的突發(fā)信道。錯誤是成串成群出現(xiàn)的，即在短時間內出現(xiàn)大量錯誤?；旌闲诺溃?/p>

短波信道和對流層散射信道是混合信道的典型例子，隨機差錯和成串的突發(fā)差錯都占有相當比例。有差錯的信道類型按照噪聲或干擾的變化規(guī)律，可把信道分為三類：8（4）如何解決傳輸差錯問題提高物理信道的質量，盡量避免和減少差錯：采用電纜屏蔽措施和適當?shù)恼{制解調方法設置中繼設備對信號進行整理再生和放大加大發(fā)射功率，降低接收設備本身的噪聲，以提高信噪比提高數(shù)據(jù)的健壯性，有效地進行檢錯和糾錯：采用信道編碼技術，為數(shù)據(jù)信息增加冗余編碼，形成抗干擾編碼，使接收方能進行檢錯或糾錯配合適當?shù)牟铄e控制方法進行檢錯或糾錯。（4）如何解決傳輸差錯問題提高物理信道的質量，盡量避免和減少9第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制10差錯控制的基本工作方式自動反饋重發(fā)方式ARQ發(fā)端發(fā)送檢錯碼，收端收到信碼后能夠檢查出錯誤。前向糾錯方式FEC發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤?；旌霞m錯方式HEC是FEC和ARQ方式的結合。信息反饋方式IF是不用編碼的差錯控制方式。差錯控制的基本工作方式自動反饋重發(fā)方式ARQ11（1）自動反饋重發(fā)ARQ

自動反饋重發(fā)記作ARQ(AutomaticRepeatRequest)，又稱自動請求重傳方式。發(fā)方按照一定的編碼規(guī)則處理待發(fā)信息，構成具有檢錯能力的編碼，發(fā)往傳輸信道；收方判決傳輸中無錯誤產(chǎn)生，并通過反向信道把判決結果反饋給發(fā)方；發(fā)方根據(jù)反饋的結果決定是否執(zhí)行重傳動作，如果接收方未正確接收，則重傳信息(出錯重傳)在規(guī)定的時間內，發(fā)方若未能收到應答信號(稱為超時)，則可以認為傳輸出現(xiàn)差錯，進而執(zhí)行重傳動作(超時重傳)。（1）自動反饋重發(fā)ARQ自動反饋重發(fā)記作ARQ(Auto12主要的反饋重傳方式

反饋重傳方式的特點是譯碼設備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效；但實時性差，主要在計算機數(shù)據(jù)通信系統(tǒng)中得到應用。常用的反饋重傳方式有：發(fā)送-等待ARQ（?！葏f(xié)議）連續(xù)發(fā)送ARQ（滑動窗口協(xié)議）選擇重傳ARQ發(fā)送方接收方抗干擾編碼應答信號主要的反饋重傳方式反饋重傳方式的特點是譯碼設備簡單，對突發(fā)13（2）前向糾錯法FEC前向糾錯方式記作FEC(ForwordErrorCorrection)。發(fā)送方按照一定的編碼規(guī)則處理待發(fā)信息，構成具有糾正錯誤能力的代碼(糾錯碼)發(fā)往傳輸信道；接收方根據(jù)編碼規(guī)則，檢查傳輸差錯，并自動加以糾正。其特點是單向傳輸，實時性好，但譯碼設備較復雜。（2）前向糾錯法FEC前向糾錯方式記作FEC(Forword14（3）混合糾錯法混合糾錯方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結合。發(fā)方發(fā)送具有一定糾錯能力同時又具有檢錯能力的編碼。收方收到編碼后，檢查差錯情況，如果錯誤在編碼的糾錯能力范圍以內，則自動糾錯，否則經(jīng)過反饋信道請求發(fā)方重發(fā)。（3）混合糾錯法混合糾錯方式記作HEC(HybridErr15（4）信息反饋法信息反饋法記作IRQ(InformationRepeatRequest)接收方把收到的信息代碼全部送回發(fā)送方，由發(fā)送方進行差錯檢驗。發(fā)送方若發(fā)現(xiàn)傳輸差錯，則重發(fā)信息代碼，直至不再發(fā)現(xiàn)差錯為止。（4）信息反饋法信息反饋法記作IRQ(Informatio16幾種差錯控制方法比較自動反饋重傳法：

使用的編/解碼設施比較簡單，如果信道的質量差或干擾嚴重，則可能經(jīng)常進入重發(fā)狀態(tài)而影響通信效率。前向糾錯法：編/解碼相對復雜，且編碼的效率很低，但是無需專門的反饋信道。主要應用于沒有反饋信道的場合，或用于線路傳播時間很長、要求重發(fā)在經(jīng)濟上不切實際的的場合。由于形成糾錯碼要求較多的冗余信息，當信道質量較好時，也影響了傳輸?shù)男??；旌霞m錯法：編/解碼相當復雜、且編碼的效率很低，很少被采用。信息反饋法：反饋信息量太大，傳輸效率很低，很少被采用。幾種差錯控制方法比較自動反饋重傳法：17第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制18差錯控制編碼的基本原理差錯控制的核心技術是信道編碼技術，即采用適當?shù)牟铄e控制編碼來傳輸信息。差錯控制編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關系加以校驗，以檢測和糾正錯誤，增加的冗余碼元就稱為監(jiān)督碼元（校驗碼元）。差錯控制編碼的基本原理差錯控制的核心技術是信道編碼技術，即采19信道編碼技術對于n位的二進制碼有N=2n種組合。如果這N種組合都用來傳輸信息，這樣構成的編碼并不具備抗干擾能力。因為不管哪一位發(fā)生錯誤，都會使傳輸信息出錯。但是，若這N種組合并未完全使用，情況將會怎樣呢？信道編碼技術對于n位的二進制碼有N=2n種組合。20差錯控制編碼的抗干擾機理【例】考慮n=3的情形，3位二進制碼有8種組合：

000、001、010、011、100、101、110、111若只用以下四個碼組表示四個字母，其余的作為禁用碼組：

000——A 011——B 101——C 110——D則只要發(fā)生一位錯誤，準用碼組就將變成禁用碼組，接收端就能知道出錯，但是不能糾錯。若只用兩個碼組作為有用碼組000——A、111——B，并將8個碼組分為兩個子集：{000、001、010、100}和{011、101、110、111}，前者對應碼組000，后者對應碼組111。則接收端可以檢測兩位及以下的差錯，或糾正一位的差錯。【結論】增加監(jiān)督碼元的個數(shù)可提高糾檢錯能力。差錯控制編碼的抗干擾機理【例】考慮n=3的情形，3位二進制碼21抗干擾編碼的理論依據(jù)香農定理在有噪聲干擾的信道中，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入信道編碼器的二進制碼元速率），則一定存在一種編碼方式，使數(shù)據(jù)的誤碼率隨著碼長n的增長將按指數(shù)下降到任一值。結論如碼長及發(fā)送速率一定，可以通過增大信道容量，使誤碼率下降。如信道容量及發(fā)送信息速率一定，可以通過增加碼長，使誤碼率下降。抗干擾編碼的理論依據(jù)香農定理22碼長、碼重、碼距編碼碼組中的碼元總位數(shù)稱為碼組的長度，簡稱碼長。一個碼組中，“1”碼元的數(shù)目稱為碼組的重量，簡稱碼重。兩個等長碼組之間對應碼位上碼元不同的數(shù)目稱為這兩個碼組的海明(Hamming)距離，簡稱碼距。一個碼組集中任意兩個碼組之間距離的最小值稱為碼的最小距離。最小碼距是抗干擾編碼的一個重要參數(shù)，它是衡量編碼檢錯、糾錯能力的依據(jù)?！纠吭谇笆隼又?，碼組集{000、011、101、110}的最小碼距為2，而碼組集{000、111}的最小碼距為3。碼長、碼重、碼距編碼碼組中的碼元總位數(shù)稱為碼組的長度，簡稱碼23編碼的檢錯和糾錯能力理論證明，編碼的抗干擾能力與最小碼距密切相關：為檢查出e個錯誤，要求最小碼距為dmin≥e+1為糾正t個錯誤，要求最小碼距為dmin≥2t+1為糾正e個錯誤，同時檢查出t個錯誤，要求最小碼距為dmin≥e+t+1 (e>t)編碼的檢錯和糾錯能力理論證明，編碼的抗干擾能力與最小碼距密切24編碼效率用差錯控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價換來的。定義編碼效率R來衡量有效性：R=d/(d+r)其中，d是信息碼元的個數(shù)，r為校驗碼元個數(shù)

。校驗碼元越長，編碼的檢錯能力越強，編碼/解碼越復雜；附加的冗余信息在整個編碼中所占的比例越大，傳輸?shù)挠行С煞衷降?，傳輸?shù)男氏陆?。編碼效率用差錯控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性25對糾、檢錯碼的基本要求對糾、檢錯碼的基本要求是:檢錯和糾錯能力盡量強、編碼效率盡量高、編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，保證有一定的糾、檢錯能力和編碼效率，并且易于實現(xiàn)。對糾、檢錯碼的基本要求26差錯控制編碼的分類按照信息碼元和監(jiān)督碼元之間的函數(shù)關系分為：線性碼和非線性碼。前者碼元之間能滿足一組線性方程組，后者則不然。按照對信息元的處理方式分為：分組碼和卷積碼。前者的各碼元僅與本組的信息元有關；后者的碼元不僅與本組的信息元有關，而且還與前面若干組的信息元有關。按照差錯控制編碼的用途分為：檢錯碼和糾錯碼。前者以檢錯為目的，不一定能糾錯；而后者以糾錯為目的，一定能檢錯。按照碼組中信息碼元在編碼前后是否相同分為：系統(tǒng)碼和非系統(tǒng)碼。差錯控制編碼的分類按照信息碼元和監(jiān)督碼元之間的函數(shù)關系分為：27分組碼分組碼一般用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成碼長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼字未被選用，稱為禁用碼組。分組碼=k個信息碼元+r個監(jiān)督碼元（校驗碼元）分組碼分組碼一般用(n,k)表示。其中，k是每組二進制信息碼28線性分組碼線性分組碼是指信息碼元與監(jiān)督碼元之間的關系可以用一組線性方程來表示的分組碼。在(n,k)分組碼中，每一個監(jiān)督碼元都是碼組中某些信息碼元按模2和而得到的，線性分組碼是一類重要的檢/糾錯碼，應用很廣。本章介紹的差錯控制編碼均為線性分組碼。線性分組碼線性分組碼是指信息碼元與監(jiān)督碼元之間的關系可以用一29第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制30常用的簡單編碼奇偶校驗碼水平奇偶校驗（行校驗）垂直奇偶校驗（列校驗）水平垂直奇偶校驗（方陣碼）定比碼（恒比碼）常用的簡單編碼奇偶校驗碼31奇偶校驗碼

奇偶校驗碼是在原信息碼元后面附加一個監(jiān)督碼元，使得碼組中“1”的個數(shù)為奇數(shù)或偶數(shù)。因此，奇偶校驗碼是含一個監(jiān)督碼元，碼重為奇數(shù)或偶數(shù)的（n,n-1）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。奇偶校驗碼奇偶校驗碼是在原信息碼元后面附加一個監(jiān)督碼元，使32奇偶校驗碼的特點

設有n-1位信息碼元為Cn-1，Cn-2，……，C1，校驗碼為C0對于偶校驗，有 對于奇校驗，有奇偶校驗碼只能檢測出代碼序列中的奇數(shù)個錯誤。沒有糾錯能力最小碼距為dmin=2編碼效率為R=（n-1）/n33奇偶校驗碼的特點設有n-1位信息碼元為Cn-1，Cn-2，行、列監(jiān)督碼奇偶校驗碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況，引入行、列監(jiān)督碼。這類編碼不僅對水平(行)方向的碼元，而且對垂直(列)方向的碼元實施奇偶校驗。既可以逐行傳輸，也可以逐列傳輸。這類編碼具有較強的檢測能力，適于檢測突發(fā)錯誤，還有一定的糾錯能力。行、列監(jiān)督碼奇偶校驗碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況，34水平奇偶校驗（HRC）

屬于水平方向冗余校驗：把要傳輸?shù)臄?shù)據(jù)以適當?shù)拈L度劃分成若干個小組，每個小組由若干個碼字組成。把碼字按順序一列一列地排列起來，然后對水平方向的碼元進行奇偶校驗，得到一列校驗碼字，附加在其它各列之后，最后按列的順序進行傳輸。水平奇偶校驗（HRC）屬于水平方向冗余校驗：35水平奇偶校驗之例

字符位ABCDEFGHI偶校驗位11010101011201100110003000111100040000000110500000000006000000000071111111111水平奇偶校驗能發(fā)現(xiàn)水平方向奇數(shù)個錯誤，以及所有突發(fā)長度<=n（n為碼字長度）的突發(fā)性錯誤。水平奇偶校驗之例字符ABCDEFGHI偶校驗位36垂直奇偶校驗（VRC）

屬于垂直方向冗余校驗碼：把要傳輸?shù)臄?shù)據(jù)以適當?shù)拈L度劃分成若干個小組，每個小組由若干個碼字組成。把碼字按順序一列一列地排列起來。然后對垂直方向的碼元進行奇偶校驗，得到一行校驗位字，附加在其它各列之后，最后按列的順序進行傳輸。垂直奇偶校驗（VRC）屬于垂直方向冗余校驗碼：37垂直奇偶校驗之例

垂直奇偶校驗能發(fā)現(xiàn)垂直方向奇數(shù)個錯誤，以及50%的突發(fā)性錯誤。字符位ABCDEFGHI1101010101201100110030001111004000000011500000000060000000007111111111奇校驗位110100110垂直奇偶校驗之例垂直奇偶校驗能發(fā)現(xiàn)垂直方向奇數(shù)個錯誤，以及38水平垂直奇偶校驗（LRC）

水平垂直奇偶校驗碼，也稱為方陣校驗碼。它不僅對行進行奇偶校驗，而且也對列進行奇偶校驗。這種方法按列傳輸時能發(fā)現(xiàn)所有長度<=n+1（n為碼字長度）的突發(fā)性錯誤和其它錯誤；按行傳輸時能發(fā)現(xiàn)所有長度<=m+1（m為碼字個數(shù)）的突發(fā)性錯誤和其它錯誤；并且具有一定的糾錯能力。水平垂直奇偶校驗（LRC）水平垂直奇偶校驗碼，也稱為方陣校39水平垂直奇偶校驗之例

字符位ABCDEFGHI偶校驗位11010101011201100110003000111100040000000110500000000006000000000071111111111奇校驗位1101001101水平垂直奇偶校驗之例字符ABCDEFGHI偶校40定比碼定比碼的碼字中1的數(shù)目與0的數(shù)目保持恒定比例，也稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的數(shù)目是否正確，就可判斷有無差錯。

定比碼定比碼的碼字中1的數(shù)目與0的數(shù)目保持恒定比例，也稱為恒41定比碼應用舉例我國電傳通信中普遍采用3∶2碼，又稱“5中取3”的定比碼，即每個碼組的長度為5，其中3個“1”。這時可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個許用碼組恰好可表示10個阿拉伯數(shù)字。而每個漢字又是以四位十進制數(shù)來代表的。國際通用的ARQ電報通信系統(tǒng)采用“7中取3”的定比碼?！?中取3”碼可以檢出所有的單比特差錯和奇數(shù)個差錯，但只能檢出部分偶數(shù)位差錯。定比碼應用舉例我國電傳通信中普遍采用3∶2碼，又稱“5中取342第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制43循環(huán)冗余碼（CRC）循環(huán)碼是一類重要的線性分組碼，它除了具有線性碼的一般性質外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。循環(huán)冗余碼（CRC碼）是數(shù)據(jù)通信領域中最常用的一種差錯檢驗碼，其特征是信息碼元和校驗碼元的長度可以任意選定。循環(huán)冗余碼（CRC）循環(huán)碼是一類重要的線性分組碼，它除了具有44CRC碼的原理假定我們構成(n=7,k=3)這樣的線性分組碼，若已知三個信息碼元為C6、C5和C4，而校驗碼元C3、C2、C1和C0是未知的。校驗碼元與信息碼元間的關系是根據(jù)以下四個線性關系式確立的。 CRC碼的原理假定我們構成(n=7,k=3)這樣的線性分組碼45CRC碼的原理按上頁編出的線性碼為：信息碼元碼組C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100當我們從表中任意挑選出兩個碼組時，將對應比特按模2相加，所得到的新碼組仍然是表中的某一碼組。這說明由8個碼字組成的線性碼具有封閉性。封閉性是線性碼的一個重要特性。CRC碼的原理按上頁編出的線性碼為：信息碼元碼組C646循環(huán)冗余碼的基本思想把要傳輸?shù)臄?shù)據(jù)信息當作一個報文碼多項式f(x)的系數(shù)，發(fā)送時用一個標準的生成多項式G(x)來除f(x)，將所除得余式R(x)的系數(shù)附加在報文碼之后發(fā)出；接收時用同一生成多項式G(x)來除收到的碼字多項式，能除盡說明傳輸正確，否則說明有錯。實現(xiàn)：用簡單的移位寄存器電路即可。循環(huán)冗余碼的基本思想把要傳輸?shù)臄?shù)據(jù)信息當作一個報文碼多項式47碼多項式

從數(shù)學角度來看，所有的X進制數(shù)都可以用一個以X為基的多項式來表示。對于二進制數(shù)，基X=2，多項式的系數(shù)只取0、1。對于長度為n的任一二進制碼字，可以用一個x的n-1次多項式來表示。碼字中每個碼元的值就是該多項式中的相應的系數(shù)。此多項式就成為碼多項式。如：

Cn-1Cn-2……C1

C0的碼多項式為：

Cn-1

xn-1+

Cn-2xn-2+……+

C1x1+

C0x0又如：碼字1010111對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應的碼字為101111。碼多項式從數(shù)學角度來看，所有的X進制數(shù)都可以用一個以X為基48循環(huán)冗余碼（CRC）

設：

k個信息碼元Cn-1，Cn-2，……，Cn-k對應的碼多項式為f(x)；r次的生成多項式為G(x)

（n=k+r）；用G(x)去除f(x)（模2運算）所得余式為R(x)；f(x)=Cn-1

xk-1+

Cn-2xk-2+……+

Cn-k

x0R(x)=Cr-1

xr-1+

Cr-2

xr-2+……+

C0x0Cn-1，Cn-2，……，Cn-k，Cr-1，……，C0循環(huán)冗余碼（CRC）設：

k個信息碼元Cn-1，Cn-2，49循環(huán)冗余編碼工作原理

發(fā)送方接收方發(fā)送數(shù)據(jù)f(x)生成多項式G(x)f(x)xr.G(x)=Q(x)+R(x)G(x)實際發(fā)送:f(x)xr.+R(x)信息字段校驗字段f(x)xr.R(x)接收數(shù)據(jù)f(x)+R(x)生成多項式G(x)R'(x)=R(x)接收正確R'(x)≠R(x)接收出錯發(fā)送f(x)xr.G(x)=Q(x)+R'(x)G(x)循環(huán)冗余編碼工作原理發(fā)送方接收方發(fā)送數(shù)據(jù)f(x)生成多項50CRC校驗碼軟件生成方法設：信息代碼M為1011001，生成多項式為G(x)=x4+x3+1，則：k=7，r=4，CRC碼字長度為n=11對應f(x)=x6+x4+x3+1，G(x)的代碼為1011001x4f(x)=x10+x8+x7+x4對應的代碼記為：10110010000；采用多項式除法，得余數(shù)為1010

(即校驗字段為1010)發(fā)送方發(fā)出的傳輸編碼為:

1011001

1010

信息字段

校驗字段接收方使用相同的生成碼進行校驗，將接收到的字段除以生成碼（二進制除法），如果能夠除盡，則正確，否則出錯。CRC校驗碼軟件生成方法設：信息代碼M為1011001，生成51簡化算法

11111101√1010000

1110110010

1110111110

1110111將信息碼字左移n-k位，后面補上n-k個0；用所得的碼字除以生成多項式G(x)的系數(shù)；將所得的n-k位余數(shù)接在信息碼字之后，即可得到CRC編碼。例：設(7,3)碼的信息碼字為101，生成多項式為：G(x)=x4+x3+x2+1求CRC編碼的碼字的過程如右圖所示。余數(shù)為0011，CRC編碼為1010011。簡化算法將信息碼字左移n-k位，后面補上n-k個0；52例1設信息代碼M=1010001101，r=5,G=110101。模2運算的結果是：商Q=1101010110，余數(shù)R=01110。將余數(shù)R作為冗余碼添加在信息M的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或2rM+R。例1設信息代碼M=1010001101，r=5,G53例1的計算過程

1101010110

←

Q

商

除數(shù)

P→

110101101000110100000

←

2rM被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余數(shù)例1的計算過程54

1100111001110011100111001110010100001110011000011001G(x)1100110000110011001R(x)100001Q(x)f(x).xr例2110011發(fā)送數(shù)據(jù)比特序列CRC校驗碼比特序列1001帶CRC校驗碼的發(fā)送數(shù)據(jù)比特序列11001110011100155例3原始數(shù)據(jù)M=1101011011G(x)=x4+x+1的系數(shù)=1001111010110110000100111001110011100111011010011101001001111101100001010余數(shù)傳輸碼元

=原始數(shù)據(jù)（左移位后）+余數(shù)

11010110111110例3原始數(shù)據(jù)M=11010110111101011056標準CRC生成多項式G(x)CRC-12：G（x）=x12+x11+x3+x2+x+1CRC-16：G（x）=x16+x15+x2+1CRC-CCITT：G（x）=x16+x12+x5+1CRC-32：G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+

x7+x5+x4+

x2+x+1標準CRC生成多項式G(x)CRC-12：57循環(huán)碼的檢錯能力

理論證明，CRC碼能查出：全部的單個比特錯誤；所有的離散的雙位錯（不相鄰）；全部≤n-k（冗余位數(shù)）的突發(fā)性錯誤；對于n-k+1位的突發(fā)性錯誤；檢出率為1-2-(n-k-1)；對于多于n-k+1位的突發(fā)性錯誤；檢出率為1-2-(n-k)；實驗表明，如果使用16位冗余碼可以檢出所有奇數(shù)位的差錯及所有雙位錯，和長度小于16位的突發(fā)錯誤，還能查出99.997%的17位和99.998%18位或更長位的突發(fā)性錯誤。傳輸速率為9600bps時，傳輸3000年才會有一個錯誤。循環(huán)碼的檢錯能力理論證明，CRC碼能查出：58海明碼Hamming于1950年在美國貝爾實驗室提出了海明碼，是第一個用來糾錯的線性分組碼，被廣泛地應用在數(shù)據(jù)通信和數(shù)據(jù)存儲系統(tǒng)的差錯控制中。所謂海明校驗實質上是奇偶校驗，是分組奇偶校驗。它可以糾正一位差錯。設海明碼長為n，監(jiān)督碼元的個數(shù)為r，海明碼它利用r個監(jiān)督關系式產(chǎn)生的r個校正因子來區(qū)分無錯和在碼字中的n個不同位置的一位錯。海明碼Hamming于1950年在美國貝爾實驗室提出了海明碼59海明碼的特點設碼長為n，信息位為k位，監(jiān)督碼元的個數(shù)為r=n-k，海明碼長滿足n=2r-1，r≥2且為正整數(shù)。給定r之后，即可確定n和k。無論碼長n為多少，海明碼的最小碼距為dmin=3。因此它只能糾正1位錯碼，通常用于前向糾錯FEC的系統(tǒng)中海明碼的編碼效率為R=k/n=1-r/n，因此編碼效率將隨著碼長增加而提高。

海明碼的特點設碼長為n，信息位為k位，監(jiān)督碼元的個數(shù)為r=n60海明碼校驗碼的位權海明碼是分組奇偶校驗碼，每組校驗位P1，P2，P3，…，Pn的位權值為2n-1。即所有2的冪次方的數(shù)據(jù)位就是奇偶校驗位(對應編號為1,2,4,8,16,32,64等的位置)其他數(shù)據(jù)位用于待編碼數(shù)據(jù).(編號為3,5,6,7,9,10,11,12,13,14,15,17等的位置)海明碼校驗碼的位權海明碼是分組奇偶校驗碼，每組校驗位P1，P61海明碼的構建每個奇偶校驗位的值代表了碼字中部分數(shù)據(jù)位的奇偶性，其所在位置決定了要校驗和跳過的比特位順序：位置1：每校驗1位，跳過1位(1,3,5,7,9,11,13,15,…)位置2：每校驗2位，跳過2位(2,3,6,7,10,11,14,15,…)位置4：每校驗4位，跳過4位(4,5,6,7,12,13,14,15,20,21,22,23,…)位置8：每校驗8位，跳過8位(8~15,24~31,40~47,…)……如果全部校驗的位置中有奇數(shù)個1，把該奇偶校驗位置為1；如果全部校驗的位置中有偶數(shù)個1，把該奇偶校驗位置為0.海明碼的構建每個奇偶校驗位的值代表了碼字中部分數(shù)據(jù)位的奇偶性62海明校驗碼的生成示例設發(fā)送信息為1000101，把校驗碼P１，P2，P3，…，順序插入信息碼中，得海明碼P１P21P3000P4101分組：組P1P21P3000P41011√√√√√√2√√√√√√3√√√√4√√√√編碼，設發(fā)送與接收雙方均采用奇校驗，則P1=0，P2=1，P3=1，P4

=1發(fā)送端發(fā)送的比特流為01110001101海明校驗碼的生成示例設發(fā)送信息為1000101，把校驗碼P１63檢錯和糾錯接收端對海明碼檢錯的方法就是逐個驗證每一個校驗位。假如有錯，就累加出錯的檢驗碼元的位權。得到的就是錯誤信息所在的位置。假定實際接收到的數(shù)據(jù)是01110011101，接收方驗證每一個校驗位驗證，可以發(fā)現(xiàn)校驗位P1、P2和P3的數(shù)據(jù)不正確。錯誤校驗位的位權求和1+2+4=7,表明位置7的數(shù)據(jù)出錯。檢錯和糾錯接收端對海明碼檢錯的方法就是逐個驗證每一個校驗位。64示例假定實際接收到的數(shù)據(jù)是01110011101組0P11P2111P30000101P41100111√√√√√√2√√√√√√3√√√√4√√√√示例假定實際接收到的數(shù)據(jù)是01110011101組0111065第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制66（1）差錯產(chǎn)生的原因數(shù)據(jù)通信系統(tǒng)的基本任務是高效率而無差錯地傳送數(shù)據(jù)。數(shù)據(jù)信號在通信線路中傳輸時，難免受到來自信道內部和外部的干擾，從而引起信號的失真，導致數(shù)據(jù)傳輸錯誤。傳輸出錯的原因：一是信道的加性噪聲；二是由于傳輸總特性（包括收、發(fā)濾波器和信道的特性）不理想引起的碼間串擾。噪聲是影響數(shù)據(jù)傳輸質量的主要因素。根據(jù)產(chǎn)生的原因可以將噪聲分為四類：熱噪聲、交調噪聲、串音和脈沖噪聲四類。（1）差錯產(chǎn)生的原因數(shù)據(jù)通信系統(tǒng)的基本任務是高效率而無差錯地67（2）噪聲的類型熱噪聲是由帶電粒子在導電介質中的布朗運動引起的，它存在于任何工作在絕對零度以上的電路或系統(tǒng)中。熱噪聲屬于高斯白噪聲，其概率密度函數(shù)滿足正態(tài)分布統(tǒng)計特性，同時它的功率譜密度函數(shù)是均勻分布的（常數(shù)）。熱噪聲的特點是：時刻存在、不可排除、幅度較小、強度與頻率無關，但頻譜很寬，是一類隨機的噪聲。（2）噪聲的類型熱噪聲68噪聲的類型交調噪聲是一種附加的頻率干擾。由于通信系統(tǒng)的非線性，將導致進入通信系統(tǒng)的不同頻率的信號在系統(tǒng)的輸出端產(chǎn)生這些頻率之間的差頻信號或倍頻信號及其組合，這就是交調噪聲。對于交調噪聲可以通過適當?shù)恼{制技術，人為地校正系統(tǒng)的非線性部分得到補償。噪聲的類型交調噪聲69噪聲的類型串音是一個通路的信號在相鄰的另一個通路引起的干擾現(xiàn)象。這是由于信號線路之間的電磁感應引起的有害耦合。為了消除線路之間的有害耦合，可以將每一對線擰成一定扭絞節(jié)距的線纜。噪聲的類型串音70噪聲的類型脈沖噪聲是由于電火花或其他原因造成的突發(fā)振幅很大、持續(xù)時間比間隔時間短得多的離散脈沖耦合到信號通路中的干擾。脈沖噪聲也稱為沖擊噪聲，它將引起一連串的數(shù)據(jù)比特出錯，它是數(shù)據(jù)傳輸差錯的主要根源。脈沖噪聲產(chǎn)生的干擾很難消除，只能采用差錯控制的方法來實現(xiàn)可靠傳輸。噪聲的類型脈沖噪聲71（3）差錯的類型隨機差錯指數(shù)據(jù)單元中的單比特差錯。它通常由傳輸信道的熱噪聲引起。突發(fā)差錯指數(shù)據(jù)單元中的兩個或兩個以上的比特發(fā)生成串密集性的差錯，第一個錯誤比特到最后一個錯誤比特之間的位數(shù)稱為突發(fā)長度。沖擊噪聲持續(xù)的時間通常大于數(shù)據(jù)傳輸中每比特的發(fā)送時間，因而會引起相鄰的多個數(shù)據(jù)位出錯，從而導致突發(fā)差錯。（3）差錯的類型隨機差錯72有差錯的信道類型按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道：

恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。突發(fā)信道：

具有脈沖干擾的信道，是典型的突發(fā)信道。錯誤是成串成群出現(xiàn)的，即在短時間內出現(xiàn)大量錯誤?；旌闲诺溃?/p>

短波信道和對流層散射信道是混合信道的典型例子，隨機差錯和成串的突發(fā)差錯都占有相當比例。有差錯的信道類型按照噪聲或干擾的變化規(guī)律，可把信道分為三類：73（4）如何解決傳輸差錯問題提高物理信道的質量，盡量避免和減少差錯：采用電纜屏蔽措施和適當?shù)恼{制解調方法設置中繼設備對信號進行整理再生和放大加大發(fā)射功率，降低接收設備本身的噪聲，以提高信噪比提高數(shù)據(jù)的健壯性，有效地進行檢錯和糾錯：采用信道編碼技術，為數(shù)據(jù)信息增加冗余編碼，形成抗干擾編碼，使接收方能進行檢錯或糾錯配合適當?shù)牟铄e控制方法進行檢錯或糾錯。（4）如何解決傳輸差錯問題提高物理信道的質量，盡量避免和減少74第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制75差錯控制的基本工作方式自動反饋重發(fā)方式ARQ發(fā)端發(fā)送檢錯碼，收端收到信碼后能夠檢查出錯誤。前向糾錯方式FEC發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。混合糾錯方式HEC是FEC和ARQ方式的結合。信息反饋方式IF是不用編碼的差錯控制方式。差錯控制的基本工作方式自動反饋重發(fā)方式ARQ76（1）自動反饋重發(fā)ARQ

自動反饋重發(fā)記作ARQ(AutomaticRepeatRequest)，又稱自動請求重傳方式。發(fā)方按照一定的編碼規(guī)則處理待發(fā)信息，構成具有檢錯能力的編碼，發(fā)往傳輸信道；收方判決傳輸中無錯誤產(chǎn)生，并通過反向信道把判決結果反饋給發(fā)方；發(fā)方根據(jù)反饋的結果決定是否執(zhí)行重傳動作，如果接收方未正確接收，則重傳信息(出錯重傳)在規(guī)定的時間內，發(fā)方若未能收到應答信號(稱為超時)，則可以認為傳輸出現(xiàn)差錯，進而執(zhí)行重傳動作(超時重傳)。（1）自動反饋重發(fā)ARQ自動反饋重發(fā)記作ARQ(Auto77主要的反饋重傳方式

反饋重傳方式的特點是譯碼設備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效；但實時性差，主要在計算機數(shù)據(jù)通信系統(tǒng)中得到應用。常用的反饋重傳方式有：發(fā)送-等待ARQ（?！葏f(xié)議）連續(xù)發(fā)送ARQ（滑動窗口協(xié)議）選擇重傳ARQ發(fā)送方接收方抗干擾編碼應答信號主要的反饋重傳方式反饋重傳方式的特點是譯碼設備簡單，對突發(fā)78（2）前向糾錯法FEC前向糾錯方式記作FEC(ForwordErrorCorrection)。發(fā)送方按照一定的編碼規(guī)則處理待發(fā)信息，構成具有糾正錯誤能力的代碼(糾錯碼)發(fā)往傳輸信道；接收方根據(jù)編碼規(guī)則，檢查傳輸差錯，并自動加以糾正。其特點是單向傳輸，實時性好，但譯碼設備較復雜。（2）前向糾錯法FEC前向糾錯方式記作FEC(Forword79（3）混合糾錯法混合糾錯方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結合。發(fā)方發(fā)送具有一定糾錯能力同時又具有檢錯能力的編碼。收方收到編碼后，檢查差錯情況，如果錯誤在編碼的糾錯能力范圍以內，則自動糾錯，否則經(jīng)過反饋信道請求發(fā)方重發(fā)。（3）混合糾錯法混合糾錯方式記作HEC(HybridErr80（4）信息反饋法信息反饋法記作IRQ(InformationRepeatRequest)接收方把收到的信息代碼全部送回發(fā)送方，由發(fā)送方進行差錯檢驗。發(fā)送方若發(fā)現(xiàn)傳輸差錯，則重發(fā)信息代碼，直至不再發(fā)現(xiàn)差錯為止。（4）信息反饋法信息反饋法記作IRQ(Informatio81幾種差錯控制方法比較自動反饋重傳法：

使用的編/解碼設施比較簡單，如果信道的質量差或干擾嚴重，則可能經(jīng)常進入重發(fā)狀態(tài)而影響通信效率。前向糾錯法：編/解碼相對復雜，且編碼的效率很低，但是無需專門的反饋信道。主要應用于沒有反饋信道的場合，或用于線路傳播時間很長、要求重發(fā)在經(jīng)濟上不切實際的的場合。由于形成糾錯碼要求較多的冗余信息，當信道質量較好時，也影響了傳輸?shù)男省；旌霞m錯法：編/解碼相當復雜、且編碼的效率很低，很少被采用。信息反饋法：反饋信息量太大，傳輸效率很低，很少被采用。幾種差錯控制方法比較自動反饋重傳法：82第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制83差錯控制編碼的基本原理差錯控制的核心技術是信道編碼技術，即采用適當?shù)牟铄e控制編碼來傳輸信息。差錯控制編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關系加以校驗，以檢測和糾正錯誤，增加的冗余碼元就稱為監(jiān)督碼元（校驗碼元）。差錯控制編碼的基本原理差錯控制的核心技術是信道編碼技術，即采84信道編碼技術對于n位的二進制碼有N=2n種組合。如果這N種組合都用來傳輸信息，這樣構成的編碼并不具備抗干擾能力。因為不管哪一位發(fā)生錯誤，都會使傳輸信息出錯。但是，若這N種組合并未完全使用，情況將會怎樣呢？信道編碼技術對于n位的二進制碼有N=2n種組合。85差錯控制編碼的抗干擾機理【例】考慮n=3的情形，3位二進制碼有8種組合：

000、001、010、011、100、101、110、111若只用以下四個碼組表示四個字母，其余的作為禁用碼組：

000——A 011——B 101——C 110——D則只要發(fā)生一位錯誤，準用碼組就將變成禁用碼組，接收端就能知道出錯，但是不能糾錯。若只用兩個碼組作為有用碼組000——A、111——B，并將8個碼組分為兩個子集：{000、001、010、100}和{011、101、110、111}，前者對應碼組000，后者對應碼組111。則接收端可以檢測兩位及以下的差錯，或糾正一位的差錯。【結論】增加監(jiān)督碼元的個數(shù)可提高糾檢錯能力。差錯控制編碼的抗干擾機理【例】考慮n=3的情形，3位二進制碼86抗干擾編碼的理論依據(jù)香農定理在有噪聲干擾的信道中，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入信道編碼器的二進制碼元速率），則一定存在一種編碼方式，使數(shù)據(jù)的誤碼率隨著碼長n的增長將按指數(shù)下降到任一值。結論如碼長及發(fā)送速率一定，可以通過增大信道容量，使誤碼率下降。如信道容量及發(fā)送信息速率一定，可以通過增加碼長，使誤碼率下降?？垢蓴_編碼的理論依據(jù)香農定理87碼長、碼重、碼距編碼碼組中的碼元總位數(shù)稱為碼組的長度，簡稱碼長。一個碼組中，“1”碼元的數(shù)目稱為碼組的重量，簡稱碼重。兩個等長碼組之間對應碼位上碼元不同的數(shù)目稱為這兩個碼組的海明(Hamming)距離，簡稱碼距。一個碼組集中任意兩個碼組之間距離的最小值稱為碼的最小距離。最小碼距是抗干擾編碼的一個重要參數(shù)，它是衡量編碼檢錯、糾錯能力的依據(jù)?！纠吭谇笆隼又?，碼組集{000、011、101、110}的最小碼距為2，而碼組集{000、111}的最小碼距為3。碼長、碼重、碼距編碼碼組中的碼元總位數(shù)稱為碼組的長度，簡稱碼88編碼的檢錯和糾錯能力理論證明，編碼的抗干擾能力與最小碼距密切相關：為檢查出e個錯誤，要求最小碼距為dmin≥e+1為糾正t個錯誤，要求最小碼距為dmin≥2t+1為糾正e個錯誤，同時檢查出t個錯誤，要求最小碼距為dmin≥e+t+1 (e>t)編碼的檢錯和糾錯能力理論證明，編碼的抗干擾能力與最小碼距密切89編碼效率用差錯控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價換來的。定義編碼效率R來衡量有效性：R=d/(d+r)其中，d是信息碼元的個數(shù)，r為校驗碼元個數(shù)

。校驗碼元越長，編碼的檢錯能力越強，編碼/解碼越復雜；附加的冗余信息在整個編碼中所占的比例越大，傳輸?shù)挠行С煞衷降?，傳輸?shù)男氏陆?。編碼效率用差錯控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性90對糾、檢錯碼的基本要求對糾、檢錯碼的基本要求是:檢錯和糾錯能力盡量強、編碼效率盡量高、編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，保證有一定的糾、檢錯能力和編碼效率，并且易于實現(xiàn)。對糾、檢錯碼的基本要求91差錯控制編碼的分類按照信息碼元和監(jiān)督碼元之間的函數(shù)關系分為：線性碼和非線性碼。前者碼元之間能滿足一組線性方程組，后者則不然。按照對信息元的處理方式分為：分組碼和卷積碼。前者的各碼元僅與本組的信息元有關；后者的碼元不僅與本組的信息元有關，而且還與前面若干組的信息元有關。按照差錯控制編碼的用途分為：檢錯碼和糾錯碼。前者以檢錯為目的，不一定能糾錯；而后者以糾錯為目的，一定能檢錯。按照碼組中信息碼元在編碼前后是否相同分為：系統(tǒng)碼和非系統(tǒng)碼。差錯控制編碼的分類按照信息碼元和監(jiān)督碼元之間的函數(shù)關系分為：92分組碼分組碼一般用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成碼長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼字未被選用，稱為禁用碼組。分組碼=k個信息碼元+r個監(jiān)督碼元（校驗碼元）分組碼分組碼一般用(n,k)表示。其中，k是每組二進制信息碼93線性分組碼線性分組碼是指信息碼元與監(jiān)督碼元之間的關系可以用一組線性方程來表示的分組碼。在(n,k)分組碼中，每一個監(jiān)督碼元都是碼組中某些信息碼元按模2和而得到的，線性分組碼是一類重要的檢/糾錯碼，應用很廣。本章介紹的差錯控制編碼均為線性分組碼。線性分組碼線性分組碼是指信息碼元與監(jiān)督碼元之間的關系可以用一94第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制95常用的簡單編碼奇偶校驗碼水平奇偶校驗（行校驗）垂直奇偶校驗（列校驗）水平垂直奇偶校驗（方陣碼）定比碼（恒比碼）常用的簡單編碼奇偶校驗碼96奇偶校驗碼

奇偶校驗碼是在原信息碼元后面附加一個監(jiān)督碼元，使得碼組中“1”的個數(shù)為奇數(shù)或偶數(shù)。因此，奇偶校驗碼是含一個監(jiān)督碼元，碼重為奇數(shù)或偶數(shù)的（n,n-1）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。奇偶校驗碼奇偶校驗碼是在原信息碼元后面附加一個監(jiān)督碼元，使97奇偶校驗碼的特點

設有n-1位信息碼元為Cn-1，Cn-2，……，C1，校驗碼為C0對于偶校驗，有 對于奇校驗，有奇偶校驗碼只能檢測出代碼序列中的奇數(shù)個錯誤。沒有糾錯能力最小碼距為dmin=2編碼效率為R=（n-1）/n98奇偶校驗碼的特點設有n-1位信息碼元為Cn-1，Cn-2，行、列監(jiān)督碼奇偶校驗碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況，引入行、列監(jiān)督碼。這類編碼不僅對水平(行)方向的碼元，而且對垂直(列)方向的碼元實施奇偶校驗。既可以逐行傳輸，也可以逐列傳輸。這類編碼具有較強的檢測能力，適于檢測突發(fā)錯誤，還有一定的糾錯能力。行、列監(jiān)督碼奇偶校驗碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況，99水平奇偶校驗（HRC）

屬于水平方向冗余校驗：把要傳輸?shù)臄?shù)據(jù)以適當?shù)拈L度劃分成若干個小組，每個小組由若干個碼字組成。把碼字按順序一列一列地排列起來，然后對水平方向的碼元進行奇偶校驗，得到一列校驗碼字，附加在其它各列之后，最后按列的順序進行傳輸。水平奇偶校驗（HRC）屬于水平方向冗余校驗：100水平奇偶校驗之例

字符位ABCDEFGHI偶校驗位11010101011201100110003000111100040000000110500000000006000000000071111111111水平奇偶校驗能發(fā)現(xiàn)水平方向奇數(shù)個錯誤，以及所有突發(fā)長度<=n（n為碼字長度）的突發(fā)性錯誤。水平奇偶校驗之例字符ABCDEFGHI偶校驗位101垂直奇偶校驗（VRC）

屬于垂直方向冗余校驗碼：把要傳輸?shù)臄?shù)據(jù)以適當?shù)拈L度劃分成若干個小組，每個小組由若干個碼字組成。把碼字按順序一列一列地排列起來。然后對垂直方向的碼元進行奇偶校驗，得到一行校驗位字，附加在其它各列之后，最后按列的順序進行傳輸。垂直奇偶校驗（VRC）屬于垂直方向冗余校驗碼：102垂直奇偶校驗之例

垂直奇偶校驗能發(fā)現(xiàn)垂直方向奇數(shù)個錯誤，以及50%的突發(fā)性錯誤。字符位ABCDEFGHI1101010101201100110030001111004000000011500000000060000000007111111111奇校驗位110100110垂直奇偶校驗之例垂直奇偶校驗能發(fā)現(xiàn)垂直方向奇數(shù)個錯誤，以及103水平垂直奇偶校驗（LRC）

水平垂直奇偶校驗碼，也稱為方陣校驗碼。它不僅對行進行奇偶校驗，而且也對列進行奇偶校驗。這種方法按列傳輸時能發(fā)現(xiàn)所有長度<=n+1（n為碼字長度）的突發(fā)性錯誤和其它錯誤；按行傳輸時能發(fā)現(xiàn)所有長度<=m+1（m為碼字個數(shù)）的突發(fā)性錯誤和其它錯誤；并且具有一定的糾錯能力。水平垂直奇偶校驗（LRC）水平垂直奇偶校驗碼，也稱為方陣校104水平垂直奇偶校驗之例

字符位ABCDEFGHI偶校驗位11010101011201100110003000111100040000000110500000000006000000000071111111111奇校驗位1101001101水平垂直奇偶校驗之例字符ABCDEFGHI偶校105定比碼定比碼的碼字中1的數(shù)目與0的數(shù)目保持恒定比例，也稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的數(shù)目是否正確，就可判斷有無差錯。

定比碼定比碼的碼字中1的數(shù)目與0的數(shù)目保持恒定比例，也稱為恒106定比碼應用舉例我國電傳通信中普遍采用3∶2碼，又稱“5中取3”的定比碼，即每個碼組的長度為5，其中3個“1”。這時可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個許用碼組恰好可表示10個阿拉伯數(shù)字。而每個漢字又是以四位十進制數(shù)來代表的。國際通用的ARQ電報通信系統(tǒng)采用“7中取3”的定比碼?！?中取3”碼可以檢出所有的單比特差錯和奇數(shù)個差錯，但只能檢出部分偶數(shù)位差錯。定比碼應用舉例我國電傳通信中普遍采用3∶2碼，又稱“5中取3107第十章差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼第十章差錯控制為什么要進行差錯控制108循環(huán)冗余碼（CRC）循環(huán)碼是一類重要的線性分組碼，它除了具有線性碼的一般性質外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。循環(huán)冗余碼（CRC碼）是數(shù)據(jù)通信領域中最常用的一種差錯檢驗碼，其特征是信息碼元和校驗碼元的長度可以任意選定。循環(huán)冗余碼（CRC）循環(huán)碼是一類重要的線性分組碼，它除了具有109CRC碼的原理假定我們構成(n=7,k=3)這樣的線性分組碼，若已知三個信息碼元為C6、C5和C4，而校驗碼元C3、C2、C1和C0是未知的。校驗碼元與信息碼元間的關系是根據(jù)以下四個線性關系式確立的。 CRC碼的原理假定我們構成(n=7,k=3)這樣的線性分組碼110CRC碼的原理按上頁編出的線性碼為：信息碼元碼組C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100當我們從表中任意挑選出兩個碼組時，將對應比特按模2相加，所得到的新碼組仍然是表中的某一碼組。這說明由8個碼字組成的線性碼具有封閉性。封閉性是線性碼的一個重要特性。CRC碼的原理按上頁編出的線性碼為：信息碼元碼組C6111循環(huán)冗余碼的基本思想把要傳輸?shù)臄?shù)據(jù)信息當作一個報文碼多項式f(x)的系數(shù)，發(fā)送時用一個標準的生成多項式G(x)來除f(x)，將所除得余式R(x)的系數(shù)附加在報文碼之后發(fā)出；接收時用同一生成多項式G(x)來除收到的碼字多項式，能除盡說明傳輸正確，否則說明有錯。實現(xiàn)：用簡單的移位寄存器電路即可。循環(huán)冗余碼的基本思想把要傳輸?shù)臄?shù)據(jù)信息當作一個報文碼多項式112碼多項式

從數(shù)學角度來看，所有的X進制數(shù)都可以用一個以X為基的多項式來表示。對于二進制數(shù)，基X=2，多項式的系數(shù)只取0、1。對于長度為n的任一二進制碼字，可以用一個x的n-1次多項式來表示。碼字中每個碼元的值就是該多項式中的相應的系數(shù)。此多項式就成為碼多項式。如：

Cn-1Cn-2……C1

C0的碼多項式為：

Cn-1

xn-1+

Cn-2xn-2+……+

C1x1+

C0x0又如：碼字1010111對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應的碼字為101111。碼多項式從數(shù)學角度來看，所有的X進制數(shù)都可以用一個以X為基113循環(huán)冗余碼（CRC）

設：

k個信息碼元Cn-1，Cn-2，……，Cn-k對應的碼多項式為f(x)；r次的生成多項式為G(x)

（n=k+r）；用G(x)去除f(x)（模2運算）所得余式為R(x)；f(x)=Cn-1

xk-1+

Cn-2xk-2+……+

Cn-k

x0R(x)=Cr-1

xr-1+

Cr-2

xr-2+……+

C0x0Cn-1，Cn-2，……，Cn-k，Cr-1，……，C0循環(huán)冗余碼（CRC）設：

k個信息碼元Cn-1，Cn-2，114循環(huán)冗余編碼工作原理

發(fā)送方接收方發(fā)送數(shù)據(jù)f(x)生成多項式G(x)f(x)xr.G(x)=Q(x)+R(x)G(x)實際發(fā)送:f(x)xr.+R(x)信息字段校驗字段f(x)xr.R(x)接收數(shù)據(jù)f(x)+R(x)生成多項式G(x)R'(x)=R(x)接收正確R'(x)≠R(x)接收出錯發(fā)送f(x)xr.G(x)=Q(x)+R'(x)G(x)循環(huán)冗余編碼工作原理發(fā)送方接收方發(fā)送數(shù)據(jù)f(x)生成多項115CRC校驗碼軟件生成方法設：信息代碼M為1011001，生成多項式為G(x)=x4+x3+1，則：k=7，r=4，CRC碼字長度為n=11對應f(x)=x6+x4+x3+1，G(x)的代碼為1011001x4f(x)=x10+x8+x7+x4對應的代碼記為：10110010000；采用多項式除法，得余數(shù)為1010

(即校驗字段為1010)發(fā)送方發(fā)出的傳輸編碼為:

1011001

1010

信息字段

校驗字段接收方使用相同的生成碼進行校驗，將接收到的字段除以生成碼（二進制除法），如果能夠除盡，則正確，否則出錯。CRC校驗碼軟件生成方法設：信息代碼M為1011001，生成116簡化算法

11111101√1010000

1110110010

1110111110

1110111將信息碼字左移n-k位，后面補上n-k個0；用所得的碼字除以生成多項式G(x)的系數(shù)；將所得的n-k位余數(shù)接在信息碼字之后，即可得到CRC編碼。例：設(7,3)碼的信息碼字為101，生成多項式為：G(x)=x4+x3+x2+1求CRC編碼的碼字的過程如右圖所示。余數(shù)為0011，CRC編碼為1010011。簡化算法將信息碼字左移n-k位，后面補上n-k個0；117例1設信息代碼M=1010001101，r=5,G=110101。模2運算的結果是：商Q=1101010110，余數(shù)R=01110。將余數(shù)R作為冗余碼添加在信息M的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或2rM+R。例1設信息代碼M=1010001101，r=5,G118例1的計算過程

1101010110

←

Q

商

除數(shù)

P→

110101101000110100000

←

2rM被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010