通信原理第10章差錯(cuò)控制編碼解析

第十章差錯(cuò)控制編碼1通信原理第10章差錯(cuò)控制編碼解析引言信源編碼，目的是實(shí)現(xiàn)模擬信號(hào)數(shù)字化信道編碼，目的是提高數(shù)字通信的可靠性差錯(cuò)率是信噪比的函數(shù)信道編碼，差錯(cuò)控制編碼，抗干擾編碼信道編碼過(guò)程：信息碼元序列＋監(jiān)督碼元→編碼碼組信道譯碼過(guò)程：編碼碼組→檢錯(cuò)或糾錯(cuò)→信息碼元序列2通信原理第10章差錯(cuò)控制編碼解析10.1差錯(cuò)控制編碼的基本概念10.1.1?差錯(cuò)控制方式10.1.2?差錯(cuò)控制編碼分類10.1.3?幾種簡(jiǎn)單的檢錯(cuò)碼10.1.4?檢錯(cuò)和糾錯(cuò)的基本原理3通信原理第10章差錯(cuò)控制編碼解析10.1.1差錯(cuò)控制方式常用的差錯(cuò)控制方式有三種：前向糾錯(cuò)（FEC:forwarderrorcorrection）發(fā)送能糾錯(cuò)的碼，在譯碼時(shí)自動(dòng)發(fā)現(xiàn)并糾正傳輸中的錯(cuò)誤只需正向信道，實(shí)時(shí)性好編譯碼設(shè)備復(fù)雜，適合單向信道和一發(fā)多收系統(tǒng)檢錯(cuò)重發(fā)（ARQ:automaticrepeatrequest）發(fā)送端發(fā)出能夠檢錯(cuò)的碼，接收端檢驗(yàn)，接收端發(fā)出反饋應(yīng)答信號(hào)，發(fā)送端重新傳輸直到正確接收為止工作原理簡(jiǎn)單，正向信道+反向信道，傳輸效率低混合糾錯(cuò)（HEC:hybriderrorcorrection）前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合與折衷外層先采用前向糾錯(cuò)，當(dāng)前向糾錯(cuò)不能解決問(wèn)題時(shí)，內(nèi)層再采用檢錯(cuò)重發(fā)。4通信原理第10章差錯(cuò)控制編碼解析

（a）

FEC方式（b）ARQ方式（c）

HEC方式5通信原理第10章差錯(cuò)控制編碼解析

檢錯(cuò)重發(fā)的三種方式

停發(fā)等候重發(fā)返回重發(fā)選擇重發(fā)6通信原理第10章差錯(cuò)控制編碼解析

10.1.2差錯(cuò)控制編碼分類在編碼前先把信息序列分為k位一組（稱為信息碼），然后附加m位監(jiān)督碼，形成n=k+m位的碼組。1、按信息碼和附加監(jiān)督碼間的檢驗(yàn)關(guān)系線性碼：監(jiān)督碼是信息碼的線性組合非線性碼：監(jiān)督碼是信息碼的非線性組合2、按信息碼和監(jiān)督碼間的約束方式分組碼：監(jiān)督碼僅與本碼組的信息碼有關(guān)卷積碼：監(jiān)督碼與之前的若干個(gè)信息碼組的碼元有約束關(guān)系7通信原理第10章差錯(cuò)控制編碼解析10.1.3幾種簡(jiǎn)單的檢錯(cuò)碼1.奇偶監(jiān)督碼編碼方法把信息碼元先分組，在每組最后加一位監(jiān)督碼元，使該碼組中1的數(shù)目為奇數(shù)或偶數(shù)奇數(shù)時(shí)稱為奇校驗(yàn)碼偶數(shù)時(shí)稱為偶校驗(yàn)碼偶校驗(yàn)碼許用碼組為000，011，101，110禁用碼組為001，010，100，111奇校驗(yàn)碼禁用碼組為000，011，101，110許用碼組為001，010，100，1118通信原理第10章差錯(cuò)控制編碼解析

一般情況下：設(shè)碼組長(zhǎng)為n，且為：則偶校驗(yàn)時(shí)有：奇校驗(yàn)時(shí)有：譯碼方法(與編碼方法相對(duì)應(yīng))不滿足校驗(yàn)關(guān)系，傳輸一定錯(cuò)誤！奇偶校驗(yàn)只能發(fā)現(xiàn)奇數(shù)個(gè)(單個(gè))錯(cuò)誤，不能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤。編碼方法簡(jiǎn)單且實(shí)用性強(qiáng)，適用于檢測(cè)隨機(jī)零星錯(cuò)碼滿足校驗(yàn)關(guān)系，傳輸一定準(zhǔn)確嗎？9通信原理第10章差錯(cuò)控制編碼解析2.二維奇偶監(jiān)督碼將奇偶校驗(yàn)碼的若干碼組排列成矩陣每一碼組寫成一行m個(gè)碼組m行m個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位列按列的方向增加第二維校驗(yàn)位n個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位行檢錯(cuò)能力檢出所有行和列中的奇數(shù)個(gè)差錯(cuò)能檢出大多數(shù)偶數(shù)個(gè)差錯(cuò)檢測(cè)突發(fā)錯(cuò)碼也有一定的適應(yīng)能力方陣碼，交織碼10通信原理第10章差錯(cuò)控制編碼解析

3.重復(fù)碼重復(fù)碼是在每位信息碼元之后，再簡(jiǎn)單重復(fù)多次的編碼；接收端譯碼時(shí)采用多數(shù)表決法。4.恒比碼從固定碼長(zhǎng)的碼組中選擇那些1和0的比例恒定的碼組作為許用碼組，如五單位保護(hù)電碼等。5.ISBN國(guó)際統(tǒng)一圖書編號(hào)2007年作了修改11通信原理第10章差錯(cuò)控制編碼解析

10.1.4檢錯(cuò)與糾錯(cuò)的基本原理差錯(cuò)編碼的基本思想是在被傳輸?shù)男畔⒅懈郊颖O(jiān)督碼，用信息的冗余度來(lái)實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。例如：000、001、010、011、100、101、110、111用來(lái)傳遞信息，則無(wú)法檢錯(cuò)；000、011、101、110用來(lái)傳遞信息可以檢一位錯(cuò)，但無(wú)法糾錯(cuò)；000、111用來(lái)傳遞信息可以檢一位或兩位錯(cuò)碼，還可以糾一位錯(cuò)碼。可見，碼組間的差異與糾檢錯(cuò)能力十分重要。12通信原理第10章差錯(cuò)控制編碼解析

定義1：碼組中非零碼元的數(shù)目稱為碼組的重量，簡(jiǎn)稱碼重。定義2：兩碼組中對(duì)應(yīng)碼位上具有不同碼元的數(shù)目稱為兩碼組的距離，簡(jiǎn)稱碼距，又叫漢明距。最小漢明距離dmin決定糾檢錯(cuò)能力例8種碼組000、001、010、011、100、101、110、111均為許用碼組時(shí)，最小碼距為1在選4種碼組000、011、101、110為許用碼組情況下，最小碼距為2采用2種許用碼組000、111時(shí)，最小碼距為313通信原理第10章差錯(cuò)控制編碼解析下圖為碼距的幾何解釋三種編碼組合，其漢明距分別為1，2，3。14通信原理第10章差錯(cuò)控制編碼解析

對(duì)于分組碼，一般有如下結(jié)論：

(1)在一個(gè)碼組內(nèi)檢測(cè)e個(gè)誤碼，要求；

(2)在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，要求；

(3)在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，同時(shí)檢測(cè)個(gè)誤碼，要求。差錯(cuò)控制編碼提高了通信系統(tǒng)的可靠性，也降低了有效性。為衡量有效性，定義編碼效率。k是編碼前碼組中的碼元數(shù)，即信息碼元數(shù)；n是編碼后碼組中的碼元數(shù)，它包含了校驗(yàn)碼元。15通信原理第10章差錯(cuò)控制編碼解析

10.2線性分組碼線性碼組中的監(jiān)督碼是信息碼元的線性組合。線性碼具有封閉性，即任意兩個(gè)許用碼組之和（模2加），結(jié)果仍為一許用碼組。設(shè)n位分組碼用表示，k位信息碼用表示，記該碼組為(n,k)碼。將碼組和信息碼組用行矩陣表示出來(lái)，則有：16通信原理第10章差錯(cuò)控制編碼解析

n=k+m，n：編碼以后的位數(shù)k：編碼以前的位數(shù)，即信息碼m=n-k：監(jiān)督位或校驗(yàn)位17通信原理第10章差錯(cuò)控制編碼解析

寫成矩陣形式，有，G為生成矩陣(k*n)，且：

設(shè)則k行k+m=n列18通信原理第10章差錯(cuò)控制編碼解析矩陣P的重要意義①與監(jiān)督位或校驗(yàn)位相對(duì)應(yīng)②編碼的根據(jù)③譯碼的根據(jù)，檢糾錯(cuò)的根據(jù)矩陣P如何選擇？編碼前信息碼組有k位碼元，k位碼元共有種組合編碼后碼組有n位碼元，n位碼元共有種組合，矩陣P可有多種選擇較強(qiáng)的檢錯(cuò)或糾錯(cuò)能力實(shí)現(xiàn)方法盡可能簡(jiǎn)單且編碼效率高在數(shù)學(xué)上已經(jīng)證明線性碼的最小碼距正好等于非零碼的最小碼重為了估算線性碼的差錯(cuò)控制能力應(yīng)首先求出碼組的最小碼距19通信原理第10章差錯(cuò)控制編碼解析

例10-1已知(6,3)碼的生成矩陣為G，試求：(1)編碼碼組和各碼組的碼重；(2)最小碼距及其差錯(cuò)控制能力。解?(1)由3位碼組成的信息碼組矩陣為D：20通信原理第10章差錯(cuò)控制編碼解析

由式，得碼組矩陣為：

信息碼組、編碼碼組及碼重如下表所示：信息碼組編碼碼組碼重W信息碼組編碼碼組碼重W0000000000100100101300100111031011010114010010011311011011040110111014111111000321通信原理第10章差錯(cuò)控制編碼解析

由前表可知，非零碼組的最小碼重為：所以最小碼距為：因此，該碼有糾1錯(cuò)，或檢2錯(cuò)，或糾一錯(cuò)同時(shí)檢一錯(cuò)的能力。

22通信原理第10章差錯(cuò)控制編碼解析

譯碼原理

由可知，或?qū)懗稍O(shè)，則有。任何線性分組碼碼組都應(yīng)該滿足上述關(guān)系信息碼與監(jiān)督碼間的校驗(yàn)關(guān)系完全取決于HH矩陣稱為校驗(yàn)矩陣或監(jiān)督矩陣，是譯碼的關(guān)鍵！23通信原理第10章差錯(cuò)控制編碼解析發(fā)送碼組A在傳輸過(guò)程中可能發(fā)生誤碼，設(shè)接收到的碼組為B=[bn-1bn-2…b0]則B–A=EE=[en-1en-2…e0]錯(cuò)誤圖樣也可寫作B=A+E24通信原理第10章差錯(cuò)控制編碼解析接收端計(jì)算校正子為錯(cuò)誤圖樣與校正子之間有確定的關(guān)系25通信原理第10章差錯(cuò)控制編碼解析例設(shè)且有3

個(gè)接收碼組驗(yàn)證3個(gè)接收碼組是否發(fā)生差錯(cuò)？若在某碼組中有錯(cuò)碼，錯(cuò)碼的校正子是什么？然后再指出發(fā)生錯(cuò)碼的碼字中，哪位有錯(cuò)？26通信原理第10章差錯(cuò)控制編碼解析解：1）若無(wú)錯(cuò)，則錯(cuò)誤圖樣為0，S為0

B1無(wú)錯(cuò)B2錯(cuò)B3錯(cuò)2）∵S2=H第1列∴E=[100000]第1位錯(cuò)同理S3=H第3列∴E=[001000]第3位錯(cuò)27通信原理第10章差錯(cuò)控制編碼解析

10.3循環(huán)碼10.3.1循環(huán)碼的特點(diǎn)及表達(dá)式循環(huán)碼是一種系統(tǒng)分組碼，前k位是信息碼，后r位是監(jiān)督碼。不僅具有封閉性，還具有循環(huán)性，即一許用碼組經(jīng)循環(huán)移位后得到另一個(gè)許用碼組。設(shè)是一個(gè)循環(huán)碼組，則可將之表示為：

上式稱為碼多項(xiàng)式。28通信原理第10章差錯(cuò)控制編碼解析

碼組C移位1次得到的仍是碼組，它可寫成：

不難驗(yàn)證：類似地，碼組C經(jīng)i次移位后，得到的新的碼組是除以的余式。也就是說(shuō)，在模意義下，若c(x)是碼多項(xiàng)式，則都是碼多項(xiàng)式。循環(huán)碼的編碼過(guò)程也可用多項(xiàng)式來(lái)描述。29通信原理第10章差錯(cuò)控制編碼解析循環(huán)冗余編碼CRC在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗(yàn)CRC的檢錯(cuò)技術(shù)。假設(shè)待傳送的數(shù)據(jù)M=1010001101（共kbit）。我們?cè)贛的后面再添加供差錯(cuò)檢測(cè)用的nbit冗余碼一起發(fā)送。冗余碼的計(jì)算用二進(jìn)制的模2運(yùn)算進(jìn)行2n

乘M的運(yùn)算，這相當(dāng)于在M后面添加n個(gè)0。得到的(k+n)bit的數(shù)除以事先選定好的長(zhǎng)度為(n+1)bit的數(shù)P，得出商是Q而余數(shù)是R，余數(shù)R比除數(shù)P至少要少1個(gè)比特。30通信原理第10章差錯(cuò)控制編碼解析31通信原理第10章差錯(cuò)控制編碼解析

冗余碼的計(jì)算舉例

設(shè)

n=5,P=110101，M=1010001101模2運(yùn)算的結(jié)果是：商Q=1101010110，余數(shù)R=01110。將余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或2nM+R。32通信原理第10章差錯(cuò)控制編碼解析循環(huán)冗余檢驗(yàn)的原理說(shuō)明

1101010110

←

Q

商

除數(shù)

P→

1101011000

←

2nM被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101