第10章信道編碼和差錯(cuò)控制教材

1第十章信道編碼和差錯(cuò)控制信源發(fā)送端接收端信道編碼調(diào)制信道壓縮編碼解調(diào)信宿保密解碼信道解碼壓縮解碼保密編碼噪聲同步信源編碼信源解碼2第十章信道編碼和差錯(cuò)控制10.1概述信道編碼：目的：提高信號傳輸?shù)目煽啃浴７椒ǎ涸黾佣嘤啾忍?，以發(fā)現(xiàn)或糾正錯(cuò)誤。差錯(cuò)控制：包括信道編碼在內(nèi)的一切糾正錯(cuò)誤手段。產(chǎn)生錯(cuò)碼的原因：乘性干擾引起的碼間串?dāng)_加性干擾引起的信噪比降低信道分類：按照加性干擾造成錯(cuò)碼的統(tǒng)計(jì)特性不同劃分隨機(jī)信道：錯(cuò)碼隨機(jī)出現(xiàn)，例如由白噪聲引起的錯(cuò)碼突發(fā)信道：錯(cuò)碼相對集中出現(xiàn)，例如由脈沖干擾引起的錯(cuò)碼?；旌闲诺?差錯(cuò)控制技術(shù)的種類：檢錯(cuò)重發(fā)：能發(fā)現(xiàn)錯(cuò)碼，但是不能確定錯(cuò)碼的位置。通信系統(tǒng)需要有雙向信道。前向糾錯(cuò)(FEC)：利用加入的差錯(cuò)控制碼元，不但能夠發(fā)現(xiàn)錯(cuò)碼，還能糾正錯(cuò)碼。反饋校驗(yàn)：將收到的碼元轉(zhuǎn)發(fā)回發(fā)送端，將它和原發(fā)送碼元比較。缺點(diǎn)：需要雙向信道，傳輸效率也較低。檢錯(cuò)刪除：在接收端發(fā)現(xiàn)錯(cuò)碼后，立即將其刪除。適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)用之處。4編碼序列的參數(shù)n－編碼序列中總碼元數(shù)量k－編碼序列中信息碼元數(shù)量r

－編碼序列中差錯(cuò)控制碼元數(shù)量 （差錯(cuò)控制碼元，以后稱為監(jiān)督碼元或監(jiān)督位）k/n－碼率(n-k)/k=r/k－冗余度5自動(dòng)要求重發(fā)(ARQ)系統(tǒng)停止等待ARQ系統(tǒng)拉后ARQ系統(tǒng)

停止等待ARQ系統(tǒng)接收數(shù)據(jù)ACKACKNAKACKACKNAKACK1233455t發(fā)送數(shù)據(jù)12334556t有錯(cuò)碼組有錯(cuò)碼組拉后ARQ系統(tǒng)214365798接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組91011101112576ACK1NAK5NAK9ACK55769521436798發(fā)送數(shù)據(jù)1011101112重發(fā)碼組重發(fā)碼組6選擇重發(fā)ARQ系統(tǒng)ARQ和前向糾錯(cuò)比較：優(yōu)點(diǎn)監(jiān)督碼元較少，即碼率較高檢錯(cuò)的計(jì)算復(fù)雜度較低能適應(yīng)不同特性的信道缺點(diǎn)需要雙向信道。不適用于一點(diǎn)到多點(diǎn)的通信系統(tǒng)或廣播系統(tǒng)。傳輸效率降低，可能因反復(fù)重發(fā)而造成事實(shí)上的通信中斷。選擇重發(fā)ARQ系統(tǒng)9接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組21436575981011131412發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK9710.2糾錯(cuò)編碼的基本原理分組碼舉例設(shè)：有一種由3個(gè)二進(jìn)制碼元構(gòu)成的編碼，它共有23=8種 不同的可能碼組：

000–晴001–云010–陰011–雨

100–雪101–霜110–霧111–雹 這時(shí)，若一個(gè)碼組中發(fā)生錯(cuò)碼，則將收到錯(cuò)誤信息。若在此8種碼組中僅允許使用4種來傳送天氣，例如：令

000–晴011–云101–陰110–雨 為許用碼組，其他4種不允許使用，稱為禁用碼組。 這時(shí)，接收端有可能發(fā)現(xiàn)（檢測到）碼組中的一個(gè)錯(cuò)碼。這種編碼只能檢測錯(cuò)碼，不能糾正錯(cuò)碼。若規(guī)定只許用兩個(gè)碼組：例如

000–晴111–雨 就能檢測兩個(gè)以下錯(cuò)碼，或糾正一個(gè)錯(cuò)碼。 8分組碼概念分組碼＝信息位＋監(jiān)督位分組碼符號：(n,k)

其中，n－碼組總長度，

k－信息碼元數(shù)目。

r=n–k

－監(jiān)督碼元數(shù)目。 右表中的碼組為(3,2)碼。分組碼的一般結(jié)構(gòu)：分組碼的參數(shù)：碼重：碼組內(nèi)“1”的個(gè)數(shù)碼距：兩碼組中對應(yīng)位取值不同的位數(shù)，又稱漢明距離最小碼距(d0)：各碼組間的最小距離信息位監(jiān)督位晴000云011陰101雨110k個(gè)信息位r個(gè)監(jiān)督位an-1an-2...arar-1an-2...a0t碼長n=k+r分組碼的結(jié)構(gòu)9碼距的幾何意義：以n=3的編碼為例一般而言，碼距是n維空間中單位正多面體頂點(diǎn)之間的漢明距離。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a110一種編碼的糾檢錯(cuò)能力：決定于最小碼距d0的值。為了能檢測e個(gè)錯(cuò)碼，要求最小碼距為了能糾正t個(gè)錯(cuò)碼，要求最小碼距0123BA漢明距離ed0碼距等于3的兩個(gè)碼組BtA漢明距離012345td0碼距等于5的兩個(gè)碼組11為了能糾正t個(gè)錯(cuò)碼，同時(shí)檢測e個(gè)錯(cuò)碼，要求最小碼距 糾檢結(jié)合工作方式：當(dāng)錯(cuò)碼數(shù)量少時(shí)，系統(tǒng)按前向糾錯(cuò)方式工作，以節(jié)省重發(fā)時(shí)間，提高傳輸效率；當(dāng)錯(cuò)碼數(shù)量多時(shí)，系統(tǒng)按反饋重發(fā)的糾錯(cuò)方式工作，以降低系統(tǒng)的總誤碼率。AB1tt漢明距離e碼距等于(e+t+1)的兩個(gè)碼組1210.3糾錯(cuò)編碼系統(tǒng)的性能10.3.1誤碼率性能和帶寬的關(guān)系 采用編碼降低誤碼率 所付出的代價(jià)是帶寬的增大。10-610-510-410-310-210-1編碼后Eb/n0(dB)編碼和誤碼率關(guān)系Pe

CDE

A

B2PSK1310.3.2功率和帶寬的關(guān)系 采用編碼以節(jié)省功率，并保持誤碼率不變，付出的代價(jià)也是帶寬增大。10-610-510-410-310-210-1編碼后Eb/n0(dB)編碼和誤碼率關(guān)系Pe

CDE

A

B2PSK14

10.3.3傳輸速率和帶寬的關(guān)系 對于給定的傳輸系統(tǒng)，其傳輸速率和Eb/n0的關(guān)系： 式中，RB

－碼元速率。 提高傳輸速率，采用編 碼以保持誤碼率不變；付出 的代價(jià)仍是帶寬增大。10-610-510-410-310-210-1編碼后Eb/n0(dB)編碼和誤碼率關(guān)系Pe

CDE

A

B2PSK1510.3.4編碼增益 定義：在保持誤碼率恒定條件下，采用糾錯(cuò)編碼所節(jié)省的信 噪比Eb/n0稱為編碼增益： 式中，(Eb/n0)u

－未編碼時(shí)的信噪比(dB)；

(Eb/n0)c

－編碼后所需的信噪比(dB)。1610.4奇偶監(jiān)督碼

10.4.1一維奇偶監(jiān)督碼奇偶監(jiān)督碼－分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩類。在奇偶監(jiān)督碼中，監(jiān)督位只有1位，故碼率等于k/(k+1)。偶數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個(gè)數(shù)為偶數(shù)： 式中，a0為監(jiān)督位，其他位為信息位。奇數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個(gè)數(shù)為奇數(shù)：檢錯(cuò)能力－能夠檢測奇數(shù)個(gè)錯(cuò)碼。1710.4.2二維奇偶監(jiān)督碼碼率等于有可能檢測偶數(shù)個(gè)錯(cuò)碼適合檢測突發(fā)錯(cuò)碼能夠糾正部分錯(cuò)碼………………………1810.5線性分組碼基本概念代數(shù)碼－利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼線性分組碼－代數(shù)碼的一種，其 監(jiān)督位和信息位的關(guān)系由線性代數(shù)方程決定漢明碼－一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼校正子： 在偶數(shù)監(jiān)督碼中，計(jì)算 實(shí)際上就是計(jì)算 并檢驗(yàn)S是否等于0。

S稱為校正子。監(jiān)督關(guān)系式：19糾錯(cuò)基本原理中，S只有兩種取值，故只能表示有錯(cuò)和無錯(cuò)，而不能進(jìn)一步指明錯(cuò)碼的位置。若此碼組長度增加一位，則能增加一個(gè)監(jiān)督關(guān)系式。這樣，就能得到兩個(gè)校正子。兩個(gè)校正子的可能取值有4種組合，即00，01，10，11，故能表示4種不同的信息。若用其中一種組合表示無錯(cuò)碼，則還有其他3種組合可以用于指明一個(gè)錯(cuò)碼的3種不同位置。從而可以有糾錯(cuò)能力。一般而言，若有r個(gè)監(jiān)督關(guān)系式，則r個(gè)校正子可以指明一個(gè)錯(cuò)碼的(2r–1)個(gè)不同位置。當(dāng)校正子可以指明的錯(cuò)碼位置數(shù)目等于或大于碼組長度n時(shí)，才能夠糾正碼組中任何一個(gè)位置上的錯(cuò)碼，即要求20漢明碼例：要求設(shè)計(jì)一個(gè)能夠糾正1個(gè)錯(cuò)碼的分組碼(n,k)，給定的碼組中有4個(gè)信息位，即k=4。由 這時(shí)要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7。現(xiàn)在用a6

a5

a4

a3

a2

a1

a0表示這7個(gè)碼元，用S1S2

S3表示校正子，則這3個(gè)校正子恰好能夠指明23–1=7個(gè)錯(cuò)碼的位置。若規(guī)定校正子和錯(cuò)碼位置的關(guān)系如下表，則僅當(dāng)在a6

a5

a4

a2位置上有錯(cuò)碼時(shí)，校正子S1的值才等于1；否則S1的值為零。這就意味著a6

a5

a4

a2四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：同理，有S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無錯(cuò)碼21在編碼時(shí)，信息位a6

a5

a4

a3的值決定于輸入信號，它們是隨機(jī)的。監(jiān)督位a2

a1

a0是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列3式中的校正子等于0，即有 給定信息位后，為了 計(jì)算監(jiān)督位，上式可 以改寫為 按照上式計(jì)算結(jié)果為信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111122在接收端解碼時(shí)，對于每個(gè)接收碼組，先按式 計(jì)算出校正子S1，S2和S3，然后按照表 判斷錯(cuò)碼的位置。 例：若接收碼組為0000011，則按上三式計(jì)算得到：S1=0，S2=1，S3=1。這樣，由上表可知，錯(cuò)碼位置在a3。S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無錯(cuò)碼23上例中的漢明碼是(7,4)碼，其最小碼距d0=3。由式可知，此碼能夠檢測2個(gè)錯(cuò)碼，或糾正1個(gè)錯(cuò)碼。漢明碼的碼率：

當(dāng)r(或n)很大時(shí)，上式趨近于1。所以漢明碼是一種高效編碼。24分組碼的一般原理線性分組碼的監(jiān)督位和信息位的關(guān)系 可以改寫為 上式中，已經(jīng)將“

”簡寫成“+”。25監(jiān)督矩陣 上式可以寫成矩陣形式：

（模2）

將上式簡寫為

HAT=0T

或AHT=026

HAT=0T

式中， －稱為監(jiān)督矩陣監(jiān)督矩陣的性質(zhì)監(jiān)督矩陣H確定碼組中的信息位和監(jiān)督位的關(guān)系。H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù)r

。H的每行中“1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。

H可以分成兩部分，例如 －典型監(jiān)督矩陣式中，P為r

k階矩陣，Ir為r

r階單位方陣。

A=[a6

a5

a4

a3

a2

a1

a0]

0=[000]27H矩陣的各行應(yīng)該是線性無關(guān)的，否則將得不到r個(gè)線性無關(guān)的監(jiān)督關(guān)系式。若一個(gè)矩陣能寫成典型陣形式[PIr]，則其各行一定是線性無關(guān)的。生成矩陣?yán)? 可以寫為 上式兩端分別轉(zhuǎn)置后，可以變成式中，Q為k

r階矩陣，是P的轉(zhuǎn)置，即 Q=PT

28

將Q的左邊加上一個(gè)k階單位方陣，稱為生成矩陣： －生成矩陣

G稱為生成矩陣，因?yàn)榭梢杂盟a(chǎn)生整個(gè)碼組A，即有生成矩陣的性質(zhì)具有[IkQ]形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼組稱為系統(tǒng)碼。矩陣G的各行也必須是線性無關(guān)的。如果已有k個(gè)線性無關(guān)的碼組，則可以將其用來作為生成矩陣G，并由它生成其余碼組。29錯(cuò)誤圖樣 設(shè)：發(fā)送碼組A是一個(gè)n列的行矩陣： 接收碼組是一個(gè)n列的行矩陣B： 令接收碼組和發(fā)送碼組之差為

E就是錯(cuò)碼的行矩陣 －稱為錯(cuò)誤圖樣 式中，

(i=0,1,…,n-1)

若ei

=0，表示該碼元未錯(cuò)；若ei=1，表示該碼元為錯(cuò)碼。B–A=E(模2)30校正子矩陣

B–A=E可以改寫成B=A+E上式表示發(fā)送碼組A與錯(cuò)碼矩陣E之和等于接收碼組B。例如，若發(fā)送碼組A=[1000111]， 錯(cuò)碼矩陣E=[0000100]，則 接收碼組B=[1000011]。在接收端解碼時(shí)，將接收碼組B代入式

AHT=0

中A的位置進(jìn)行計(jì)算。若接收碼組中無錯(cuò)碼，則B=A。代入后，該式仍成立，即有

BHT=0

只有當(dāng)錯(cuò)碼未超出檢測能力時(shí)，上式才不成立。

3110.6循環(huán)碼

10.6.1循環(huán)碼的概念： 循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個(gè)碼組。

例：一種(7,3)循環(huán)碼的全部碼組如下 表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位A6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001032一般情況 若(an-1

an-2…a0)是循環(huán)碼的一個(gè)碼組，則循環(huán)移位后的碼組： (an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)

仍然是該編碼中的碼組。多項(xiàng)式表示法 一個(gè)長度為n的碼組(an-1

an-2…a0)可以表示成

上式中x的值沒有任何意義，僅用它的冪代表碼元的位置。 例：碼組1100101可以表示為3310.6.2循環(huán)碼的運(yùn)算整數(shù)的按模運(yùn)算 在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有

1+1=2

0(模2)， 1+2=3

1(模2)，2

3=6

0(模2)

等等。 一般說來，若一個(gè)整數(shù)m可以表示為 式中，Q為整數(shù)，則在模n運(yùn)算下，有

m

p(模n)

所以，在模n運(yùn)算下，一個(gè)整數(shù)m等于它被n除得的余數(shù)。34碼多項(xiàng)式的按模運(yùn)算 若任意一個(gè)多項(xiàng)式F(x)被一個(gè)n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，即 則在按模N(x)運(yùn)算下，有 這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算。 例1：x3被(x3+1)除，得到余項(xiàng)1，即 例2： 因?yàn)?/p>

x

x3+1x4+x2+1

x4+x

x2+x+1

在模2運(yùn)算中加法和減法一樣。35循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)T(x)是一個(gè)長度為n的碼組，若 則T

(x)也是該編碼中的一個(gè)碼組。

[證]設(shè)一循環(huán)碼為 則有 上式中的T

(x)正是碼組T(x)向左循環(huán)移位i次的結(jié)果。 例：一循環(huán)碼為1100101，即 若給定i=3，則有 上式對應(yīng)的碼組為0101110，它正是T(x)向左移3位的結(jié)果。結(jié)論：一個(gè)長為n的循環(huán)碼必定為按模(xn+1)運(yùn)算的一個(gè)余式。36循環(huán)碼的生成有了生成矩陣G，就可以由k個(gè)信息位得出整個(gè)碼組： 例： 式中， 生成矩陣G的每一行都是一個(gè)碼組。因此，若能找到k個(gè)已知的碼組，就能構(gòu)成矩陣G。如前所述，這k個(gè)已知碼組必須是線性不相關(guān)的。在循環(huán)碼中，一個(gè)(n,k)碼有2k個(gè)不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，xg(x)，x2g(x)，

，xk-1g(x)都是碼組，而且這k個(gè)碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。37在循環(huán)碼中除全“0”碼組外，再?zèng)]有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n-k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n–k)，即連續(xù)“0”的個(gè)數(shù)多于(k–1)。顯然，這是與前面的結(jié)論矛盾的。我們稱這唯一的(n–k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。38因此，循環(huán)碼的生成矩陣G可以寫成例： 上表中的編碼為(7,3)循環(huán)碼，n=7,k=3,n–k=4，其中唯一的一個(gè)(n–k)=4次碼多項(xiàng)式代表的碼組是第二碼組0010111，與它對應(yīng)的碼多項(xiàng)式，即生成多項(xiàng)式，為

g(x)=x4+x2+x+1。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位A6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001039 g(x)=x4+x2+x+1即“10111”

將此g(x)代入上矩陣，得到 或 上式不符合G=[IkQ]形式，所以它不是典型生成矩陣。但它經(jīng)過線性變換后，不難化成典型陣。 此循環(huán)碼組的多項(xiàng)式表示式T(x)： 上式表明，所有碼多項(xiàng)式T(x)都能夠被g(x)整除，而且任意一個(gè)次數(shù)不大于(k–1)的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。4010.6.5截短循環(huán)碼截短目的： 在設(shè)計(jì)時(shí)，通常信息位數(shù)k、碼長n和糾錯(cuò)能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。故采用截短碼長截短，得出滿足要求的編碼。截短方法： 設(shè)給定一個(gè)(n,k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i(0<i<k)個(gè)信息位全為“0”，于是它變成僅有2k-i種碼組。然后從中刪去這i位全“0”的信息位，最終得到一個(gè)(n–i，k–i)的線性碼。將這種碼稱為截短循環(huán)碼。截短循環(huán)碼與截短前的循環(huán)碼至少具有相同的糾錯(cuò)能力，并且截短循環(huán)碼的編解碼方法仍和截短前的方法一樣。例：要求構(gòu)造一個(gè)能夠糾正1位錯(cuò)碼的(13,9)碼。 這時(shí)可以由