差錯控制基本方法和編碼要求課件

1、差錯控制基本方法和編碼要求為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼（1）差錯產生的原因數據通信系統(tǒng)的基本任務是高效率而無差錯地傳送數據。數據信號在通信線路中傳輸時，難免受到來自信道內部和外部的干擾，從而引起信號的失真，導致數據傳輸錯誤。傳輸出錯的原因：一是信道的加性噪聲；二是由于傳輸總特性（包括收、發(fā)濾波器和信道的特性）不理想引起的碼間串擾。噪聲是影響數據傳輸質量的主要因素。根據產生的原因可以將噪聲分為四類：熱噪聲、交調噪聲、串音和脈沖噪聲四類。（2）噪聲的類型熱噪聲是由帶電粒子在導電介質中的布朗運動引起的，它存在于任何工作在絕對零度以上的電路

2、或系統(tǒng)中。熱噪聲屬于高斯白噪聲，其概率密度函數滿足正態(tài)分布統(tǒng)計特性，同時它的功率譜密度函數是均勻分布的（常數）。熱噪聲的特點是：時刻存在、不可排除、幅度較小、強度與頻率無關，但頻譜很寬，是一類隨機的噪聲。噪聲的類型交調噪聲是一種附加的頻率干擾。由于通信系統(tǒng)的非線性，將導致進入通信系統(tǒng)的不同頻率的信號在系統(tǒng)的輸出端產生這些頻率之間的差頻信號或倍頻信號及其組合，這就是交調噪聲。對于交調噪聲可以通過適當的調制技術，人為地校正系統(tǒng)的非線性部分得到補償。噪聲的類型串音是一個通路的信號在相鄰的另一個通路引起的干擾現象。這是由于信號線路之間的電磁感應引起的有害耦合。為了消除線路之間的有害耦合，可以將每一對線

3、擰成一定扭絞節(jié)距的線纜。噪聲的類型脈沖噪聲是由于電火花或其他原因造成的突發(fā)振幅很大、持續(xù)時間比間隔時間短得多的離散脈沖耦合到信號通路中的干擾。脈沖噪聲也稱為沖擊噪聲，它將引起一連串的數據比特出錯，它是數據傳輸差錯的主要根源。脈沖噪聲產生的干擾很難消除，只能采用差錯控制的方法來實現可靠傳輸。（3）差錯的類型隨機差錯指數據單元中的單比特差錯。它通常由傳輸信道的熱噪聲引起。突發(fā)差錯指數據單元中的兩個或兩個以上的比特發(fā)生成串密集性的差錯，第一個錯誤比特到最后一個錯誤比特之間的位數稱為突發(fā)長度。沖擊噪聲持續(xù)的時間通常大于數據傳輸中每比特的發(fā)送時間，因而會引起相鄰的多個數據位出錯，從而導致突發(fā)差錯。有差錯

4、的信道類型按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道：恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現是隨機的，而且錯誤之間是統(tǒng)計獨立的。突發(fā)信道：具有脈沖干擾的信道，是典型的突發(fā)信道。錯誤是成串成群出現的，即在短時間內出現大量錯誤?；旌闲诺溃憾滩ㄐ诺篮蛯α鲗由⑸湫诺朗腔旌闲诺赖牡湫屠?，隨機差錯和成串的突發(fā)差錯都占有相當比例。（4）如何解決傳輸差錯問題提高物理信道的質量，盡量避免和減少差錯：采用電纜屏蔽措施和適當的調制解調方法設置中繼設備對信號進行整理再生和放大加大發(fā)射功率，降低接收設備本身的噪聲，以提高信噪比提高數據的健壯性，有效地進行檢錯和糾錯：采用信道編碼技術，為數據信息增

5、加冗余編碼，形成抗干擾編碼，使接收方能進行檢錯或糾錯配合適當的差錯控制方法進行檢錯或糾錯。第十章 差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼差錯控制的基本工作方式自動反饋重發(fā)方式ARQ發(fā)端發(fā)送檢錯碼，收端收到信碼后能夠檢查出錯誤。前向糾錯方式FEC發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。混合糾錯方式HEC是FEC和ARQ方式的結合。信息反饋方式IF是不用編碼的差錯控制方式。（1）自動反饋重發(fā)ARQ 自動反饋重發(fā)記作ARQ (Automatic Repeat Request )，又稱自動請求重傳方式。發(fā)方按照一定的編

6、碼規(guī)則處理待發(fā)信息，構成具有檢錯能力的編碼，發(fā)往傳輸信道；收方判決傳輸中無錯誤產生，并通過反向信道把判決結果反饋給發(fā)方；發(fā)方根據反饋的結果決定是否執(zhí)行重傳動作，如果接收方未正確接收，則重傳信息(出錯重傳)在規(guī)定的時間內，發(fā)方若未能收到應答信號(稱為超時)，則可以認為傳輸出現差錯，進而執(zhí)行重傳動作(超時重傳)。主要的反饋重傳方式 反饋重傳方式的特點是譯碼設備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效；但實時性差，主要在計算機數據通信系統(tǒng)中得到應用。 常用的反饋重傳方式有：發(fā)送-等待ARQ（停等協議）連續(xù)發(fā)送ARQ（滑動窗口協議）選擇重傳ARQ發(fā)送方接收方抗干擾編碼應答信號（2）前向糾錯法FEC前向糾

7、錯方式記作FEC(Forword Error Correction)。發(fā)送方按照一定的編碼規(guī)則處理待發(fā)信息，構成具有糾正錯誤能力的代碼(糾錯碼)發(fā)往傳輸信道；接收方根據編碼規(guī)則，檢查傳輸差錯，并自動加以糾正。其特點是單向傳輸，實時性好，但譯碼設備較復雜。 （3）混合糾錯法混合糾錯方式記作HEC(Hybrid Error Correction)是FEC和ARQ方式的結合。發(fā)方發(fā)送具有一定糾錯能力同時又具有檢錯能力的編碼。收方收到編碼后，檢查差錯情況，如果錯誤在編碼的糾錯能力范圍以內，則自動糾錯，否則經過反饋信道請求發(fā)方重發(fā)。（4）信息反饋法信息反饋法記作IRQ (Information Repe

8、at Request )接收方把收到的信息代碼全部送回發(fā)送方，由發(fā)送方進行差錯檢驗。發(fā)送方若發(fā)現傳輸差錯，則重發(fā)信息代碼，直至不再發(fā)現差錯為止。幾種差錯控制方法比較自動反饋重傳法： 使用的編/解碼設施比較簡單，如果信道的質量差或干擾嚴重，則可能經常進入重發(fā)狀態(tài)而影響通信效率。 前向糾錯法：編/解碼相對復雜，且編碼的效率很低，但是無需專門的反饋信道。主要應用于沒有反饋信道的場合，或用于線路傳播時間很長、要求重發(fā)在經濟上不切實際的的場合。由于形成糾錯碼要求較多的冗余信息，當信道質量較好時，也影響了傳輸的效率?；旌霞m錯法：編/解碼相當復雜、且編碼的效率很低，很少被采用。信息反饋法：反饋信息量太大，傳

9、輸效率很低，很少被采用。第十章 差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼差錯控制編碼的基本原理差錯控制的核心技術是信道編碼技術，即采用適當的差錯控制編碼來傳輸信息。差錯控制編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關系加以校驗，以檢測和糾正錯誤，增加的冗余碼元就稱為監(jiān)督碼元（校驗碼元）。信道編碼技術對于n位的二進制碼有N=2n種組合。如果這N種組合都用來傳輸信息，這樣構成的編碼并不具備抗干擾能力。因為不管哪一位發(fā)生錯誤，都會使傳輸信息出錯。但是，若這N種組合并未完全使用，情況將會怎樣呢？差錯控制編碼的

10、抗干擾機理【例】考慮n=3的情形，3位二進制碼有8種組合：000、001、010、011、100、101、110、111若只用以下四個碼組表示四個字母，其余的作為禁用碼組：000 A011B101C110D則只要發(fā)生一位錯誤，準用碼組就將變成禁用碼組，接收端就能知道出錯，但是不能糾錯。若只用兩個碼組作為有用碼組000 A、111B，并將8個碼組分為兩個子集：000、001、010、100和011、101、110、111，前者對應碼組000，后者對應碼組111。則接收端可以檢測兩位及以下的差錯，或糾正一位的差錯?！窘Y論】增加監(jiān)督碼元的個數可提高糾檢錯能力。抗干擾編碼的理論依據香農定理在有噪聲干擾

11、的信道中，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入信道編碼器的二進制碼元速率），則一定存在一種編碼方式，使數據的誤碼率隨著碼長n的增長將按指數下降到任一值。結論如碼長及發(fā)送速率一定，可以通過增大信道容量，使誤碼率下降。如信道容量及發(fā)送信息速率一定，可以通過增加碼長，使誤碼率下降。碼長、碼重、碼距編碼碼組中的碼元總位數稱為碼組的長度，簡稱碼長。一個碼組中，“1”碼元的數目稱為碼組的重量，簡稱碼重。兩個等長碼組之間對應碼位上碼元不同的數目稱為這兩個碼組的海明(Hamming)距離，簡稱碼距。一個碼組集中任意兩個碼組之間距離的最小值稱為碼的最小距離。最小碼距是抗干擾編碼的一個重要

12、參數，它是衡量編碼檢錯、糾錯能力的依據。【例】在前述例子中，碼組集000、011、101、110的最小碼距為2，而碼組集000、111的最小碼距為3。編碼的檢錯和糾錯能力理論證明，編碼的抗干擾能力與最小碼距密切相關：為檢查出e個錯誤，要求最小碼距為dmine+1為糾正t個錯誤，要求最小碼距為dmin2t+1為糾正e個錯誤，同時檢查出t個錯誤，要求最小碼距為dmine+t+1(et)編碼效率用差錯控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價換來的。定義編碼效率R來衡量有效性：R=d/(d+r) 其中，d是信息碼元的個數，r為校驗碼元個數 。校驗碼元越長，編碼的檢錯能力越強，編碼/解碼越復

13、雜；附加的冗余信息在整個編碼中所占的比例越大，傳輸的有效成分越低，傳輸的效率下降。對糾、檢錯碼的基本要求對糾、檢錯碼的基本要求是: 檢錯和糾錯能力盡量強、編碼效率盡量高、編碼規(guī)律盡量簡單。 實際中要根據具體指標要求，保證有一定的糾、檢錯能力和編碼效率，并且易于實現。差錯控制編碼的分類按照信息碼元和監(jiān)督碼元之間的函數關系分為：線性碼和非線性碼。前者碼元之間能滿足一組線性方程組，后者則不然。按照對信息元的處理方式分為：分組碼和卷積碼。前者的各碼元僅與本組的信息元有關；后者的碼元不僅與本組的信息元有關，而且還與前面若干組的信息元有關。按照差錯控制編碼的用途分為：檢錯碼和糾錯碼。前者以檢錯為目的，不一

14、定能糾錯；而后者以糾錯為目的，一定能檢錯。按照碼組中信息碼元在編碼前后是否相同分為：系統(tǒng)碼和非系統(tǒng)碼。分組碼分組碼一般用(n,k)表示。其中，k是每組二進制信息碼元的數目，n是編碼碼組的碼長。n-k=r為每個碼組中的監(jiān)督碼元數目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成碼長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余 2n-2k個碼字未被選用，稱為禁用碼組。分組碼= k個信息碼元+ r個監(jiān)督碼元（校驗碼元）線性分組碼線性分組碼是指信息碼元與監(jiān)督碼元之間的關系可以用一組線性方程來表示的分組碼。在(n,k)分組碼

15、中，每一個監(jiān)督碼元都是碼組中某些信息碼元按模2和而得到的，線性分組碼是一類重要的檢/糾錯碼，應用很廣。本章介紹的差錯控制編碼均為線性分組碼。第十章 差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼常用的簡單編碼奇偶校驗碼水平奇偶校驗（行校驗）垂直奇偶校驗（列校驗）水平垂直奇偶校驗（方陣碼）定比碼（恒比碼）奇偶校驗碼 奇偶校驗碼是在原信息碼元后面附加一個監(jiān)督碼元，使得碼組中“1”的個數為奇數或偶數。因此，奇偶校驗碼是含一個監(jiān)督碼元，碼重為奇數或偶數的（n,n-1）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。奇偶校驗碼的特點 設有n-1位信息碼

16、元為Cn-1，Cn-2，C1， 校驗碼為C0對于偶校驗，有對于奇校驗，有奇偶校驗碼只能檢測出代碼序列中的奇數個錯誤。沒有糾錯能力最小碼距為dmin=2編碼效率為R=（n-1）/n34行、列監(jiān)督碼奇偶校驗碼不能發(fā)現偶數個錯誤。為了改善這種情況，引入行、列監(jiān)督碼。這類編碼不僅對水平(行)方向的碼元，而且對垂直(列)方向的碼元實施奇偶校驗。既可以逐行傳輸，也可以逐列傳輸。這類編碼具有較強的檢測能力，適于檢測突發(fā)錯誤，還有一定的糾錯能力。水平奇偶校驗（HRC） 屬于水平方向冗余校驗：把要傳輸的數據以適當的長度劃分成若干個小組，每個小組由若干個碼字組成。把碼字按順序一列一列地排列起來，然后對水平方向的碼

17、元進行奇偶校驗，得到一列校驗碼字，附加在其它各列之后，最后按列的順序進行傳輸。水平奇偶校驗之例 水平奇偶校驗能發(fā)現水平方向奇數個錯誤，以及所有突發(fā)長度=n（n為碼字長度）的突發(fā)性錯誤。 字符位ABCDEFGHI偶校驗位11010101011201100110003000111100040000000110500000000006000000000071111111111垂直奇偶校驗（VRC） 屬于垂直方向冗余校驗碼：把要傳輸的數據以適當的長度劃分成若干個小組，每個小組由若干個碼字組成。把碼字按順序一列一列地排列起來。然后對垂直方向的碼元進行奇偶校驗，得到一行校驗位字，附加在其它各列之后，最后按

18、列的順序進行傳輸。垂直奇偶校驗之例 垂直奇偶校驗能發(fā)現垂直方向奇數個錯誤，以及50%的突發(fā)性錯誤。 字符位ABCDEFGHI1101010101201100110030001111004000000011500000000060000000007111111111奇校驗位110100110水平垂直奇偶校驗（LRC） 水平垂直奇偶校驗碼，也稱為方陣校驗碼。它不僅對行進行奇偶校驗，而且也對列進行奇偶校驗。這種方法按列傳輸時能發(fā)現所有長度=n+1 （n為碼字長度）的突發(fā)性錯誤和其它錯誤；按行傳輸時能發(fā)現所有長度=m+1（m為碼字個數）的突發(fā)性錯誤和其它錯誤；并且具有一定的糾錯能力。 水平垂直奇偶校驗

19、之例 字符位ABCDEFGHI偶校驗位11010101011201100110003000111100040000000110500000000006000000000071111111111奇校驗位1101001101定比碼定比碼的碼字中1的數目與0的數目保持恒定比例，也稱為恒比碼。由于恒比碼中，每個碼組均含有相同數目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的數目是否正確，就可判斷有無差錯。定比碼應用舉例我國電傳通信中普遍采用32碼，又稱“5中取3”的定比碼，即每個碼組的長度為5，其中3個“1”。這時可能編成的不同碼組數目等于從5中取3的組合數10，這10

20、個許用碼組恰好可表示10個阿拉伯數字。而每個漢字又是以四位十進制數來代表的。國際通用的ARQ電報通信系統(tǒng)采用“7中取3”的定比碼?！?中取3”碼可以檢出所有的單比特差錯和奇數個差錯，但只能檢出部分偶數位差錯。第十章 差錯控制為什么要進行差錯控制差錯控制的基本方法差錯控制編碼的基本概念常用的簡單編碼常用的線性分組碼循環(huán)冗余碼（CRC）循環(huán)碼是一類重要的線性分組碼，它除了具有線性碼的一般性質外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。循環(huán)冗余碼（CRC碼）是數據通信領域中最常用的一種差錯檢驗碼，其特征是信息碼元和校驗碼元的長度可以任意選定。CRC碼的原理假定

21、我們構成(n=7,k=3)這樣的線性分組碼，若已知三個信息碼元為C6、C5和C4，而校驗碼元C3、C2、C1和C0是未知的。校驗碼元與信息碼元間的關系是根據以下四個線性關系式確立的。 CRC碼的原理按上頁編出的線性碼為：信息碼元碼 組C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100當我們從表中任意挑選出兩個碼組時，將對應比特按模2相加，所得到的新碼組仍然是表中的某一碼組。這說明由8個碼字組成的線性碼具有封閉性。封閉性是線性碼的一個重要特性。循環(huán)

22、冗余碼的基本思想 把要傳輸的數據信息當作一個報文碼多項式f(x)的系數，發(fā)送時用一個標準的生成多項式G(x)來除f(x) ，將所除得余式R(x)的系數附加在報文碼之后發(fā)出；接收時用同一生成多項式G(x)來除收到的碼字多項式，能除盡說明傳輸正確，否則說明有錯。實現：用簡單的移位寄存器電路即可。碼多項式 從數學角度來看，所有的X進制數都可以用一個以X為基的多項式來表示。對于二進制數，基X=2，多項式的系數只取0、1。對于長度為n的任一二進制碼字，可以用一個x的n-1次多項式來表示。碼字中每個碼元的值就是該多項式中的相應的系數。此多項式就成為碼多項式。如： Cn-1Cn-2C1 C0的碼多項式為：

23、Cn-1 xn-1 + Cn-2 xn-2+ C1 x1 + C0 x0 又如：碼字對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應的碼字為101111。循環(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-2 xk-2+ Cn-k x0 R(x)=Cr-1 xr-1 + Cr-2 xr-2+ C0 x0 Cn-1，Cn-2，Cn-k，Cr-1，C0循環(huán)冗余編碼工作原理 發(fā)送方

24、接收方發(fā)送數據 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)接收數據 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)CRC校驗碼軟件生成方法設：信息代碼M為，生成多項式為G(x)=x4+x3+1，則：k=7，r=4，CRC碼字長度為n=11 對應 f(x)=x6+x4+x3+1，G(x)的代碼為x4f(x)=x10+x8+x7+x4 對應的代碼記為：10110010000；采用多項式除

25、法， 得余數為 1010 (即校驗字段為1010)發(fā)送方發(fā)出的傳輸編碼為: 1 0 1 1 0 0 1 1 0 10 信息字段 校驗字段接收方使用相同的生成碼進行校驗，將接收到的字段除以生成碼（二進制除法），如果能夠除盡，則正確，否則出錯。簡化算法 1 1 11 1 1 0 11 0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1將信息碼字左移n-k位，后面補上n-k個0；用所得的碼字除以生成多項式G(x)的系數；將所得的n-k位余數接在信息碼字之后，即可得到CRC編碼。例：設(7,3)碼的信息碼字為101， 生成

26、多項式為： G(x)=x4+x3+x2+1求CRC編碼的碼字的過程如右圖所示。余數為0011， CRC編碼為。例1設信息代碼 M = 1010001101，r = 5,G = 110101。模 2 運算的結果是： 商 Q = 1101010110， 余數R = 01110。將余數 R 作為冗余碼添加在信息 M 的后面發(fā)送出去，即發(fā)送的數據是101000110101110，或 2rM + R。例1的計算過程 1101010110 Q 商 除數 P 110101 101000110100000 2rM 被除數 110101 111011 110101 111010 110101 111110 11

27、0101 101100 110101 110010 110101 01110 R 余數 例21 1 0 0 1 1 1 0 0 11 1 0 0 1 1 1 0 0 11 1 0 0 11 1 0 0 101 0 0 0 0 11 1 0 0 1 1 0 0 0 01 1 0 0 1G(x) 1 1 0 0 11 0 0 0 01 1 0 0 11 0 0 1R(x)1 0 0 0 0 1Q(x)f(x).xr1 1 0 0 1 1發(fā)送數據比特序列CRC校驗碼比特序列1 0 0 1帶CRC校驗碼的發(fā)送數據比特序列例3原始數據M=1101011011G(x)=x4+x+1 的系數=1001111

28、 0 10 11 0 11 0 0 0 010 0 1110 0 111 0 0 111 0 0 111 0 1 101 0 0 111 01 0 01 0 0 1111 1 0 1100001010余數 傳輸碼元=原始數據（左移位后）+余數 11010110111110標準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 + x

29、2+x+1 循環(huán)碼的檢錯能力 理論證明，CRC碼能查出：全部的單個比特錯誤； 所有的離散的雙位錯（不相鄰）； 全部 n-k（冗余位數）的突發(fā)性錯誤；對于n-k+1位的突發(fā)性錯誤；檢出率為1-2-(n-k-1) ；對于多于n-k+1位的突發(fā)性錯誤；檢出率為1-2-(n-k) ；實驗表明，如果使用16位冗余碼可以檢出所有奇數位的差錯及所有雙位錯，和長度小于16位的突發(fā)錯誤，還能查出99.997%的17位和99.998% 18位或更長位的突發(fā)性錯誤。 傳輸速率為9600bps時，傳輸3000年才會有一個錯誤。海明碼Hamming于1950年在美國貝爾實驗室提出了海明碼，是第一個用來糾錯的線性分組碼，被廣泛地應用在數據通信和數據存儲系統(tǒng)的