通信原理樊昌信版第11章差錯控制編碼1

通信原理樊昌信版第11章差錯控制編碼1第一頁，共63頁。11.1概述數(shù)字信號在傳輸過程中受到干擾的影響，使信號波形變壞，發(fā)生誤碼，可以采用一些方法解決。有效性——信源編碼可靠性——信道編碼第二頁，共63頁。0、復(fù)習(xí)模擬信源：在無線廣播中，信源一般是一個語音源（話音或音樂）；在電視廣播中，信源主要是活動圖像的視頻信號源。這些信源的輸出都是模擬信號，所以稱之為模擬信源。信源編碼：將模擬信息源的輸出轉(zhuǎn)化為數(shù)字信號，即A/D轉(zhuǎn)換。信源編碼目的：提高通信有效性，減少原消息的冗余度。第三頁，共63頁。差錯出現(xiàn)原因外界噪聲傳輸中碼間串?dāng)_解決方法合理地設(shè)計基帶信號、調(diào)制/解調(diào)方式、采用均衡技術(shù)、發(fā)送功率等因素，使誤比特率降低。差錯控制措施。第四頁，共63頁。差錯控制編碼屬信道編碼，要求在滿足有效性前提下，盡可能提高數(shù)字通信的可靠性。

差錯控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強(qiáng)的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號。例如奇偶校驗。差錯控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，或進(jìn)而糾正錯誤。第五頁，共63頁。

按功能分：檢錯碼和糾錯碼按監(jiān)督碼元與信息碼元關(guān)系分：線性碼與非線性碼按信息碼元與監(jiān)督碼元之間的約束關(guān)系分：分組碼與卷積碼按糾正差錯的類型分：糾正隨機(jī)錯誤的碼與糾正突發(fā)錯誤的碼1、差錯控制編碼分類第六頁，共63頁。2、誤碼類型隨機(jī)誤碼、突發(fā)誤碼

隨機(jī)誤碼錯碼出現(xiàn)是隨機(jī)的、錯碼之間統(tǒng)計獨立由隨機(jī)噪聲引起存在隨機(jī)誤碼的信道稱為隨機(jī)信道／無記憶信道第七頁，共63頁。突發(fā)誤碼差錯在短時間成串出現(xiàn)，而在其間又存在較長的無差錯區(qū)間，且差錯之間相關(guān)。例如：脈沖噪聲；存儲系統(tǒng)中磁帶的缺陷或讀寫頭接觸不良引起的；用手機(jī)過涵洞。存在這種差錯的信道稱為突發(fā)信道/有記憶信道。第八頁，共63頁。3、信道類型隨機(jī)信道：錯碼的出現(xiàn)是隨機(jī)的突發(fā)信道：錯碼是成串集中出現(xiàn)的混合信道：既存在隨機(jī)錯碼又存在突發(fā)錯碼第九頁，共63頁。4、差錯控制方法檢錯重發(fā)前向糾錯反饋校驗檢錯刪除第十頁，共63頁。（1）檢錯重發(fā)ErrorDetectionretransmission收端在接收到的信碼中發(fā)現(xiàn)錯碼時，就通知發(fā)端重發(fā)，直到正確接收為止。如奇偶校驗。檢錯重發(fā)方式只用于檢測誤碼，能夠在接收單元中發(fā)現(xiàn)錯誤，但不一定知道該錯誤碼的具體位置。需具備雙向信道。發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答信號第十一頁，共63頁。（2）前向糾錯（FEC）ForwardErrorCorrection發(fā)收能夠糾正錯誤的碼發(fā)送端將信息序列編碼成能夠糾正錯誤的碼，接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果有錯自動糾正。第十二頁，共63頁。不需要反饋信道，特別適合只能提供單向信道場合。自動糾錯，不要求檢錯重發(fā)，延時小，實時性好。若糾錯較多，則編、譯碼設(shè)備復(fù)雜，傳輸效率低。（2）前向糾錯（FEC）ForwardErrorCorrection發(fā)收能夠糾正錯誤的碼第十三頁，共63頁。（3）反饋(feedback)校驗(checkout)接收端將接收到的信碼原封不動地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信碼相比較，若發(fā)現(xiàn)錯誤，發(fā)端再重發(fā)。數(shù)據(jù)信息發(fā)收數(shù)據(jù)信息第十四頁，共63頁。不需要糾錯、檢錯的編、譯碼器，設(shè)備簡單。需要反向信道，實時性差。發(fā)端需要一定容量的存儲器以存儲發(fā)送碼組。僅適應(yīng)于傳輸速率較低，信道差錯率較低，具有雙向傳輸線路及控制簡單的系統(tǒng)。（3）反饋(feedback)校驗(checkout)數(shù)據(jù)信息發(fā)收數(shù)據(jù)信息第十五頁，共63頁。（4）檢錯刪除發(fā)現(xiàn)錯誤后，刪除，不需重發(fā)。適合少數(shù)特定系統(tǒng)中，發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)用。核心問題：發(fā)現(xiàn)錯誤、糾正錯誤第十六頁，共63頁。5、差錯控制編碼常稱為糾錯編碼(Error-CorrectingCoding)監(jiān)督碼元：前述除第3種外，都是在接收端識別有無錯碼。所以在發(fā)送端需要在信息碼元序列中增加一些差錯控制碼元，稱為監(jiān)督碼元。不同的編碼方法，有不同的檢錯或糾錯能力。第十七頁，共63頁。編碼效率(簡稱碼率)：設(shè)編碼序列中信息碼元數(shù)量為k，總碼元數(shù)量為n，則比值k/n就是碼率。冗余度：監(jiān)督碼元數(shù)(n-k)和信息碼元數(shù)k之比。理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。第十八頁，共63頁。6、自動要求重發(fā)(ARQ)系統(tǒng)AutomaticRepeatreQuest發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答信號信源編碼器和緩沖存儲器重發(fā)控制雙向信道解碼器指令產(chǎn)生器輸出緩沖存儲器收信者正確時輸出錯誤時刪除第十九頁，共63頁。①停止等待ARQ系統(tǒng)2發(fā)送端：接收端：133123ACKACKNAK發(fā)現(xiàn)錯誤TITw停頓時間6、自動要求重發(fā)(ARQ)系統(tǒng)第二十頁，共63頁。發(fā)端在Tw時間內(nèi)送出一個碼組；收端收到后檢查。如果未發(fā)現(xiàn)錯誤，則發(fā)回一個認(rèn)可信號(ACK)給發(fā)送端，發(fā)送端收到ACK信號再發(fā)下一個碼組若檢測到錯誤，則發(fā)回一個否認(rèn)信號(NAK)，發(fā)送端收到NAK信號后重發(fā)前一碼組，并再次等候ACK信號或NAK信號發(fā)送兩個碼組之間有停頓時間TI，影響了傳輸效率。半雙工狀態(tài)。第二十一頁，共63頁。②拉后ARQ系統(tǒng)其發(fā)送端不停地送出一個個連續(xù)碼組，不再等候收端返回的ACK信號一旦收端發(fā)現(xiàn)錯誤并返回NAK信號，則發(fā)端從下一碼組開始重發(fā)前面的N個碼組N的大小取決于信號傳遞及處理所帶來的延時6、自動要求重發(fā)(ARQ)系統(tǒng)接收數(shù)據(jù)有錯碼組有錯碼組91011101112214365798576ACK1NAK5NAK9ACK5發(fā)送數(shù)據(jù)57695214367981011101112重發(fā)碼組重發(fā)碼組第二十二頁，共63頁。③選擇重發(fā)ARQ系統(tǒng)也是連續(xù)不斷地發(fā)送碼組，收端檢測到錯誤后發(fā)回NAK信號。發(fā)端并不重發(fā)錯誤碼組后的所有碼組，而只重發(fā)有錯的那個碼組。6、自動要求重發(fā)(ARQ)系統(tǒng)接收數(shù)據(jù)有錯碼組有錯碼組921436575981011131412發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK9第二十三頁，共63頁。ARQ的主要優(yōu)點：和前向糾錯方法相比監(jiān)督碼元較少即能使誤碼率降到很低，即碼率較高；檢錯的計算復(fù)雜度較低；檢錯用的編碼方法和加性干擾的統(tǒng)計特性基本無關(guān)，能適應(yīng)不同特性的信道。6、自動要求重發(fā)(ARQ)系統(tǒng)第二十四頁，共63頁。ARQ的主要缺點：需要雙向信道來重發(fā)，不能用于單向信道，也不能用于一點到多點的通信系統(tǒng)。因為重發(fā)而使ARQ系統(tǒng)的傳輸效率降低。在信道干擾嚴(yán)重時，可能發(fā)生因不斷反復(fù)重發(fā)而造成事實上的通信中斷。在要求實時通信的場合，例如電話通信，往往不允許使用ARQ法。6、自動要求重發(fā)(ARQ)系統(tǒng)第二十五頁，共63頁。11.2糾錯編碼的基本原理

在信息碼序列中加監(jiān)督碼就稱為差錯控制編碼，也叫糾錯編碼。不同的編碼方法，有不同的檢錯和糾錯能力，增加監(jiān)督碼元越多，檢(糾)錯能力越強(qiáng)。差錯控制編碼原則上是降低編碼效率來換取可靠性提高。（即誤碼率更?。?/p>

第二十六頁，共63頁。設(shè)有一種由3位二進(jìn)制數(shù)字構(gòu)成的碼組，它共有8種不同的可能組合。若將其全部用來表示天氣，則可以表示8種不同天氣，如：000（晴）001（云）010（陰）011（雨）100（雪）101（霜）110（霧）111（雹）其中任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發(fā)現(xiàn)錯誤。1、分組碼基本原理：舉例說明第二十七頁，共63頁。若在上述8種碼組中只準(zhǔn)許使用4種來傳送天氣，如：000＝晴011＝云101＝陰110＝雨接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。若000中錯了一位，則接收碼組將變成100或010或001。這3種碼組都是不準(zhǔn)使用的，稱為禁用碼組。接收端在收到禁用碼組時，就認(rèn)為發(fā)現(xiàn)了錯碼。這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產(chǎn)生的是許用碼組。也能檢測3個錯碼，000變成了111。第二十八頁，共63頁。2、檢錯和糾錯000＝晴011＝云101＝陰110＝雨上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當(dāng)接收碼組為禁用碼組100時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成100。要能夠糾正錯誤，還要增加多余度。例如，若規(guī)定許用碼組只有兩個：000(晴)，111(雨)，其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。第二十九頁，共63頁。2、檢錯和糾錯000=晴111=雨例如，當(dāng)收到禁用碼組100時，若當(dāng)作僅有一個錯碼，則可以判斷此錯碼發(fā)生在“1”位，從而糾正為000（晴）。因為111（雨）發(fā)生任何一位錯碼時都不會變成100這種形式。若假定錯碼數(shù)不超過兩個，則存在兩種可能性：000錯1位和111錯2位都可能變成100，因而只能檢測出存在錯碼而無法糾正錯碼。第三十頁，共63頁。信息位監(jiān)督位晴000云011陰101雨1103、分組碼的結(jié)構(gòu)將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。分組碼包括信息位和監(jiān)督位。監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。第三十一頁，共63頁。分組碼的一般結(jié)構(gòu)分組碼的符號：(n,k)n－碼組的總位數(shù)，又稱為碼組的長度(碼長)k－碼組中信息碼元的數(shù)目n–k＝r－碼組中的監(jiān)督碼元數(shù)目編碼效率η:指一個碼組中信息位所占比重第三十二頁，共63頁。碼重：碼組中“1”的個數(shù)目稱為碼組的重量，簡稱碼重。碼距：兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。如：000＝晴011＝云101＝陰110＝雨4個碼組之間，任意兩個的距離均為2。最小碼距：某種編碼中各個碼組之間距離的最小值稱為最小碼距(d0)。如上面的編碼的最小碼距d0=2。4、分組碼的碼重和碼距第三十三頁，共63頁。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a15、碼距的幾何意義每個碼組的3個碼元的值(a1,a2,a3)就是此立方體各頂點的坐標(biāo)。而上述碼距概念在此圖中就對應(yīng)于各頂點之間沿立方體各邊行走的幾何距離。由此圖可以直觀看出，上例中4個準(zhǔn)用碼組之間的距離均為2。第三十四頁，共63頁。6、碼距和檢糾錯能力的關(guān)系0123BA漢明距離ed0一種編碼的最小碼距d0的大小直接關(guān)系著這種編碼的檢錯和糾錯能力。為檢測e個錯碼，要求最小碼距d0

e+1第三十五頁，共63頁。檢e個錯Ae1dminBA、B都為許用碼；A發(fā)生e個錯；B不能靠在球面上，否則收到B無法判斷是否為錯碼；dmin≥e+1若要求檢測e個錯碼，則最小碼距d0至少應(yīng)不小于(e+1)。反之，若一種編碼的最小碼距為d0，則將能檢測(d0-1)個錯碼。第三十六頁，共63頁。BtA漢明距離012345td0為了糾正t個錯碼，要求最小碼距d0

2t+1【證】圖中碼組A和B的距離為5。碼組A或B若發(fā)生不多于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，反之判決為碼組B。這樣，就能夠糾正兩位錯碼。第三十七頁，共63頁。1tABtdmin糾正t個錯碼A、B都為許用碼；A、B都發(fā)生t個錯；dmin≥2t+1為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距:第三十八頁，共63頁。先分析上圖所示的例子。圖中d0=5。按照檢錯能力公式e=d0–1，最多能檢測4個錯碼；按照糾錯能力公式，能糾正2個錯碼。但是，不能同時作到兩者，因為當(dāng)錯碼位數(shù)超過糾錯能力時，該碼組立即進(jìn)入另一碼組的圓內(nèi)而被錯誤地“糾正”了。這就是說，檢錯和糾錯公式不能同時成立或同時運(yùn)用。BtA漢明距離012345td0第三十九頁，共63頁。為了在糾正t個錯碼的同時，能夠檢測e個錯碼，就需要如圖所示，使某一碼組（碼組A）發(fā)生e個錯誤之后所處的位置，與其它碼組（碼組B）的糾錯圓圈至少距離等于1，避免將落在該糾錯圓上從而發(fā)生錯誤地“糾正”。由此圖可以直觀看出，要求最小碼距：ABe1tt漢明距離dmin第四十頁，共63頁。11.3糾錯編碼的性能1、系統(tǒng)帶寬和信噪比的矛盾為減少錯誤碼元數(shù)量，需在信息碼元序列中加入監(jiān)督碼元，使發(fā)送序列增長，冗余度增大。若保持信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起噪聲功率增大，使信噪比下降，又使系統(tǒng)接收端錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。第四十一頁，共63頁。第11章差錯控制編碼2、編碼性能舉例若接收信噪比等于7dB，未采用糾錯編碼時誤碼率約為810-4，(A點)采用糾錯編碼后:誤碼率降至約410-5(B點)不增大發(fā)送功率就能降低誤碼率約一個半數(shù)量級。編碼和誤碼率關(guān)系10-610-510-410-310-210-1編碼后信噪比

(dB)PeCDEAB編碼前2PSK第四十二頁，共63頁。第11章差錯控制編碼2、編碼性能舉例若接收信噪比等于7dB，未采用糾錯編碼時誤碼率約為810-4，(A點)采用糾錯編碼后:誤碼率降至約410-5(B點)不增大發(fā)送功率就能降低誤碼率約一個半數(shù)量級。編碼和誤碼率關(guān)系2PSK10-610-510-410-310-210-1編碼后信噪比

(dB)PeCDEAB編碼前2PSK第四十三頁，共63頁。若保持誤碼率在10-5，未采用編碼時，約需要信噪比9.5dB(C點)。在采用這種編碼時，約需要信噪比7.5dB(D點)?？梢怨?jié)省功率2dB。通常稱這2dB為編碼增益。上面兩種情況付出的代價是帶寬增大。編碼和誤碼率關(guān)系2PSK10-610-510-410-310-210-1編碼后信噪比

(dB)PeCDEAB編碼前2PSK第四十四頁，共63頁。第11章差錯控制編碼傳輸速率和Eb/n0的關(guān)系提高傳輸速率，采用編碼以保持誤碼率不變；付出的代價仍是帶寬增大。對于給定的傳輸系統(tǒng)2PSK式中，RB為碼元速率。10-610-510-410-310-210-1編碼后信噪比

(dB)PeCDEAB編碼前2PSK第四十五頁，共63頁。奇偶監(jiān)督碼二維奇偶監(jiān)督碼恒比碼正反碼11.4簡單的實用編碼第四十六頁，共63頁。1、奇偶監(jiān)督碼奇偶監(jiān)督碼：在信息碼元后附加一位監(jiān)督位，使得碼組中奇偶監(jiān)督碼“1”的個數(shù)為偶數(shù)或奇數(shù)。偶數(shù)監(jiān)督碼奇數(shù)監(jiān)督碼式中a0為監(jiān)督位，其他位為信息位。第四十七頁，共63頁。只能檢測出奇數(shù)個錯誤，不能糾錯。應(yīng)用：以隨機(jī)錯誤為主的計算機(jī)通信系統(tǒng)，難于對付突發(fā)錯誤。編碼效率=k/n=k/(k+1)偶數(shù)監(jiān)督碼奇數(shù)監(jiān)督碼第四十八頁，共63頁。2、二維奇偶監(jiān)督碼（方陣碼）將奇偶監(jiān)督碼推廣到二維。即在水平監(jiān)督基礎(chǔ)上再對方陣中每一列進(jìn)行奇偶校驗，發(fā)送時按列的順序傳輸。又稱為方陣碼、行列監(jiān)督碼、水平垂直奇偶監(jiān)督碼。接收端將碼元排成發(fā)送時的方陣形式，再分別按行、按列進(jìn)行奇偶校驗。第四十九頁，共63頁。

能夠發(fā)現(xiàn)某行、某列上所有奇數(shù)個錯誤以及突發(fā)長度不大于方陣行數(shù)或列數(shù)的突發(fā)錯誤；有可能檢測出偶數(shù)個錯誤（在行上檢測不出，但有可能在列上檢測出），但當(dāng)偶數(shù)個錯誤剛好構(gòu)成矩形時，則檢測不出。可糾正一些錯誤。第五十頁，共63頁。第五十一頁，共63頁。011例如：當(dāng)碼組中僅在一行有奇數(shù)個錯誤時，能夠確定錯誤位置，并糾正它?！獭獭獭獭獭獭獭獭獭獭獭獭獭痢痢痢恋谖迨?，共63頁。011構(gòu)成矩形的偶數(shù)個誤碼檢測不出?！獭獭獭獭獭獭獭獭獭獭獭獭?0√√√√第五十三頁，共63頁。01有可能檢測出偶數(shù)個誤碼?！獭獭獭獭獭獭獭獭獭獭?0√√1√√××第五十四頁，共63頁。3、恒比碼每個碼組中含“1”和“0”的個數(shù)的比例恒定，又稱等重碼。這種碼在檢測時，只要計算接收碼組中“1”的數(shù)目是否對，就知道有無錯碼。主要優(yōu)點是簡單，適于用來傳輸電傳機(jī)或其他鍵盤設(shè)備產(chǎn)生的字母和符號。第五十五頁，共63頁。表我國五單位保護(hù)電碼表（是一種五中取三碼）數(shù)字電碼數(shù)字電碼001101500111101011610101211001711100310110801110411010910011第五十六頁，共63頁。4、正反碼它是一種簡單的能夠糾正錯碼的編碼。監(jiān)督位數(shù)目與信息位數(shù)目相同，且監(jiān)督碼元