信息論與編碼-第六章

信道編碼-有擾離散信道的編碼定理信道編碼的初步認(rèn)識編碼，譯碼碼C={C1,C2,…,CM},M為碼字個(gè)數(shù)；碼字

C=(c0,c1,…,cn-1);碼元其中ci

(i=0,1,2,…,n-1)稱碼元，對于二進(jìn)制有ci

∈{0，1}誤碼率，差錯(cuò)符號誤比特率，差錯(cuò)比特信道編碼-有擾離散信道的編碼定理差錯(cuò)圖樣E=(e0,e1,…,en-1)E=收碼R-發(fā)碼C mod

M對于二進(jìn)制E=C

⊕R=C+R或C=R+E差錯(cuò)圖樣的類型:隨機(jī)錯(cuò)誤圖樣突發(fā)錯(cuò)誤圖樣信道編碼-有擾離散信道的編碼定理差錯(cuò)控制方式前向糾錯(cuò)（FEC）、檢錯(cuò)重發(fā)（ARQ）和混合糾錯(cuò)（HEC）是常用的三種差錯(cuò)控制方式。圖是這三種方式構(gòu)成的差錯(cuò)控制系統(tǒng)原理框圖。信道編信道譯信息碼信息碼發(fā)送端

接收端信道編信道譯信息碼信息碼發(fā)送端接收端信道編信道譯信息碼信息碼發(fā)送端接收端應(yīng)答信號能夠發(fā)現(xiàn)并可糾正錯(cuò)誤的碼應(yīng)答信號能夠發(fā)現(xiàn)錯(cuò)誤的碼可糾正錯(cuò)誤的碼(a)檢錯(cuò)重發(fā)(ARQ)示意圖(b)前向糾錯(cuò)(FEC)示意圖(c)混合糾錯(cuò)(HEC)示意圖圖三種差錯(cuò)控制方式示意圖信道編碼-有擾離散信道的編碼定理

向糾錯(cuò)(FEC)系統(tǒng)中，發(fā)信端將信息碼經(jīng)信道編碼后變成能夠糾正錯(cuò)誤的碼，然后通過信道發(fā)送出去；收信端收到這些碼組后，根據(jù)與發(fā)信端約定好的編碼規(guī)則，通過譯碼能自動(dòng)發(fā)現(xiàn)并糾正因傳輸帶來的數(shù)據(jù)錯(cuò)誤。前向糾錯(cuò)方式只要求單向信道，因此特別適合于只能提供單向信道的場合，同時(shí)也適合一點(diǎn)發(fā)送多點(diǎn)接收的廣播方式。因?yàn)椴恍枰獙Πl(fā)信端反饋信息，所以接收信號的延時(shí)小、實(shí)時(shí)性好。這種糾錯(cuò)系統(tǒng)的缺點(diǎn)是設(shè)備復(fù)雜、成本高，且糾錯(cuò)能力愈強(qiáng)，編譯碼設(shè)備就愈復(fù)雜。檢錯(cuò)重發(fā)(ARQ)系統(tǒng)的發(fā)信端將信息碼編成能夠檢錯(cuò)的碼組發(fā)送到信道，收信端收到一個(gè)碼組后進(jìn)行檢驗(yàn)，將檢驗(yàn)結(jié)果（有誤碼或者無誤碼）通過反向信道反饋給發(fā)信端作為對發(fā)信端的一個(gè)應(yīng)答信號。發(fā)信端根據(jù)收到的應(yīng)答信號做出是繼續(xù)發(fā)送新的數(shù)據(jù)還是把出錯(cuò)的數(shù)據(jù)重發(fā)的判斷。檢錯(cuò)重發(fā)系統(tǒng)根據(jù)工作方式又可分為三種，即停發(fā)等候重發(fā)系統(tǒng)、返回重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)，如圖8―3所示。在圖8―3（a）中，發(fā)信端在t=0時(shí)刻將碼組1發(fā)給收信端，然后停止發(fā)送，等待收信端的應(yīng)答信號。收信端收到該碼組并檢驗(yàn)后，將應(yīng)答信號ACK發(fā)回發(fā)信端，發(fā)信端確認(rèn)碼組1無錯(cuò)，就將碼組2發(fā)送出來；收信端對碼組2進(jìn)行檢驗(yàn)后，收信端判斷該碼組有錯(cuò)并以NAK信號告知發(fā)信端，發(fā)信端將碼組2重新發(fā)送一次，收信端第二次收到碼組2經(jīng)檢驗(yàn)后無錯(cuò)，即可通過ACK信號告訴發(fā)信端無錯(cuò)，發(fā)信端接著發(fā)送碼組3……從上述過程中可見，發(fā)信端由于要等收信端的應(yīng)答信號，發(fā)送過程是間歇式的，因此數(shù)據(jù)傳輸效率不高。但由于該系統(tǒng)原理簡單，在計(jì)算機(jī)通信中仍然得到應(yīng)用。圖8―3

檢錯(cuò)重發(fā)的三種工作方式12*23傳輸

ACK傳輸

ACKNAK傳輸

ACK傳輸

tt端12234碼組

發(fā)送

接收端發(fā)送

接收端端12345623456789101112*345623456789傳輸

NAK傳輸

發(fā)送

接收端端123456278910111213141512*3456278910111213傳輸

NAK傳輸

tttt(a)停發(fā)等候重發(fā)示意圖(b)返回重發(fā)示意圖(c)選擇重發(fā)示意圖返回重發(fā)系統(tǒng)的工作原理如圖8―3（b）所示，在這種系統(tǒng)中發(fā)信端不停頓地發(fā)送信息碼組，

不再等候ACK信號，如果收信端發(fā)現(xiàn)錯(cuò)誤并發(fā)

回NAK信號，則發(fā)信端從下一個(gè)碼組開始重發(fā)前一段N個(gè)碼組，N的大小取決于信號傳輸和處理所造成的延時(shí)，也就是發(fā)信端從發(fā)錯(cuò)誤碼組開始，到收到NAK信號為止所發(fā)出的碼組個(gè)數(shù)，圖中N=5。收信端收到碼組2有錯(cuò)。發(fā)信端在碼組6后重發(fā)碼組2、3、4、5、6，收信端重新接收，圖中碼組4連續(xù)兩次出錯(cuò)，發(fā)信端重發(fā)兩次。這種返回重發(fā)系統(tǒng)的傳輸效率比停發(fā)等候系統(tǒng)有很大改進(jìn)，在很多數(shù)據(jù)傳輸系統(tǒng)中得到應(yīng)用。圖8―3（c）描述選擇重發(fā)系統(tǒng)的工作過程：這種重發(fā)系統(tǒng)也是連續(xù)不斷地發(fā)送碼組，收信端檢測到錯(cuò)誤后發(fā)回NAK信號，但是發(fā)信端不是重發(fā)前N個(gè)碼組，而是只重發(fā)有錯(cuò)誤的那一組。圖中顯示發(fā)信端只重發(fā)收信端檢出有錯(cuò)的碼組2，對其它碼組不再重發(fā)。

收信端對已認(rèn)可的碼組，從緩沖 器讀出時(shí)重新排序，恢復(fù)出正常的碼組序列。顯然，選擇重發(fā)系統(tǒng)傳輸效率最高，但價(jià)格也最貴，因?yàn)樗筝^為復(fù)雜的控制，在收、發(fā)兩端都要求有數(shù)據(jù)緩存器。

混合糾錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合。如圖8―2（c）所示。其內(nèi)層采用FEC方式，糾正部分差錯(cuò)；外層采用

ARQ方式，重傳那些雖已檢出但未糾正的差錯(cuò)?；旌霞m錯(cuò)方式在實(shí)時(shí)性和譯碼復(fù)雜性方面是前向糾錯(cuò)和檢錯(cuò)重發(fā)方式的折衷，較適合于環(huán)路延遲大的高速數(shù)據(jù)傳輸系統(tǒng)。信道編碼-有擾離散信道的編碼定理差錯(cuò)控制編碼分類根據(jù)編碼方式和不同的衡量標(biāo)準(zhǔn)，差錯(cuò)控制編碼有多種形式和類別。下面簡單地介紹幾種主要分類。(1)根據(jù)編碼功能可分為檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼三種類型，只能完成檢錯(cuò)功能的叫檢錯(cuò)碼；具有糾錯(cuò)能力的叫糾錯(cuò)碼；而糾刪碼既可檢錯(cuò)也可糾錯(cuò)。(2)按照信息碼元和附加的監(jiān)督碼元之間的檢驗(yàn)關(guān)系可以分為線性碼和非線性碼。若信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系，即監(jiān)督碼元是信息碼元的線性組合，則稱為線性碼。反之，若兩者不存性關(guān)系，則稱為非線性碼。如果所字可以組成一個(gè)線性空間，就稱為線性碼，否則，為非線性碼。(3)按照信息碼元和監(jiān)督碼元之間的約束方式

可分為分組碼和卷積碼。在分組碼中，編碼前先把信息序列分為k位一組，然后用一定規(guī)則附加m位監(jiān)督碼元，形成n=k+m位的碼組。監(jiān)督碼元僅與本碼組的信息碼元有關(guān)，而與其它碼組的信息碼元無關(guān)。但在卷積碼中，碼組中的監(jiān)督碼元不但與本組信息碼元有關(guān)，而且與前面碼組的信息碼元也有約束關(guān)系，就像鏈條那樣一環(huán)扣—環(huán)；所以卷積碼又稱連環(huán)碼或鏈碼。系統(tǒng)碼與非系統(tǒng)碼。性分組碼中所有碼組的k位信息碼元在編碼前后保持原來形式的碼叫系統(tǒng)碼，反之就是非系統(tǒng)碼。系統(tǒng)碼與非系統(tǒng)碼在性能上大致相同，而且系統(tǒng)碼的編、譯碼都相對比較簡單，因此得到廣泛應(yīng)用。糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。顧名思義，前者用于糾正因信道中出現(xiàn)的隨機(jī)獨(dú)立干擾引起的誤碼，后者主要對付信道中出現(xiàn)的突發(fā)錯(cuò)誤。信道編碼-有擾離散信道的編碼定理從上述分類中可以看到，一種編碼可以具有多樣性，本章主要介紹糾正隨機(jī)錯(cuò)誤的二進(jìn)制線性分組碼。信道編碼-有擾離散信道的編碼定理碼空間信息空間2k碼空間2kn-維n-重矢量空間2n編碼，在n-維n-重矢量空間選取2k個(gè)碼字矢量的方法。（一種 ，不同的 方法，構(gòu)成不同的編碼。）信道編碼-有擾離散信道的編碼定理有擾離散信道的編碼定理隨機(jī)編碼考慮一個(gè)DMC信道，其輸入符號集為輸出符號集為即輸入為q元，輸出為Q元。,

xq-

1},

yQ

-

1}{x0

,

x1,Y

=

{y

0

,

y1

,轉(zhuǎn)移概率矩陣為{p(yj

/

xi

)}信道編碼-有擾離散信道的編碼定理對其輸入進(jìn)行分組編碼，編碼方式是每K個(gè)輸入信源符號一組，編成N個(gè)符號的碼，叫做（N，K）分組編(N,K)分組編DMC信道消息組m(m0

,

m1, ,

mK

-1

)。碼字

c

=

(c0

,c1

,C

X

Nx0

,

x1

,,

xq-

1}ic

X,

yQ

-

1}ri

?

Y{y

0

,

y1

,0

1N

-1,

r

)

?

Y

N。,cN

-1

)收碼r

=(r

,r

,信道編碼-有擾離散信道的編碼定理?點(diǎn)中，選擇M，可能會得到不所謂編碼，就是要在Z個(gè)N個(gè)作為碼字，不同的同的誤碼率。碼字(c0

,c1,,cN

1

)可看成是一個(gè)N重矢量，設(shè)想

有一個(gè)N維的矢量空間X

N，每一個(gè)碼字可以認(rèn)

為是該矢量空間的一個(gè)點(diǎn)。由于每維有q個(gè)取值，故該矢量空間中總的點(diǎn)數(shù)為Z

qN而碼字由K個(gè)q進(jìn)制符號組成，故碼字總數(shù)為M

qK信道編碼-有擾離散信道的編碼定理隨機(jī)編碼的誤碼率已經(jīng)

，所謂編碼就是要在Z個(gè)N

點(diǎn)中選取M個(gè)作為碼字。如果不要求一一對應(yīng)，則共有ZM種不同的 ，在這些中，有的方法選取的結(jié)果會使得誤碼率比較低，有的可能比較高。那么，誤碼率的上界是多少呢？由于共有ZM種不同的，故每一種選取方法的出現(xiàn)概率為1/ZM，即信道編碼-有擾離散信道的編碼定理mZ

M

q

NM1p({C

})

其中，{Cm}為某種選擇方法得到的碼集。設(shè)與這種選擇相對應(yīng)的誤碼率為Pe

({Cm})，則全部碼集的平均誤碼率為NMq

NM

q

NMP

m1e

m1Pe

({Cm})Pe

({Cm})

p({Cm})

q信道編碼-有擾離散信道的編碼定理那么，Pe

的上界是多少呢？設(shè)有某一個(gè)碼字

Ck

(ck

0

,

ck1,,

ck

(

N

1)

)

，經(jīng)DMC信道傳輸后，在輸出端變成接收碼字r

(r0

,r1,,rN

1)，則譯碼后的誤碼率是Pe

(ck

)

p(r

/

ck

)Ik

(r）rY

N其中，1,(a)(b)I

(r)

0,ki

k,有p(r

/ck

)

p(r

/ci

)對所有的i

k,總有至少一個(gè)i使p(r

/ck

)

p(r

/ci

)信道編碼-有擾離散信道的編碼定理這就意味著，當(dāng)發(fā)碼字ck

而收到r的概率大于發(fā)任何其他碼字

ci

而收到r的概率時(shí)，則令

Ik

(r)

0,因?yàn)榇藭r(shí)通過最優(yōu)譯碼可以做到正確譯碼；反之，則令I(lǐng)k

(r)

1,因?yàn)榇藭r(shí)不能正確譯碼。而Ik

(r)一定滿足不等式

1

1

)1

k

ik

kp(r

/

c

p(r

/

ci

)1

I

(r)

信道編碼-有擾離散信道的編碼定理上式可以根據(jù)

Ik

(r)

0和Ik

(r)

1兩種情況分別加以驗(yàn)證。將上式代入誤碼率公式，于是有rY

N

ikikrY

Nk

ik

ke

k

1

1

1

1

p(r

/

c

)1

p(r

/

c

)1

p(r

/

c

)1

p(r

/

ci

)1

p(r

/

c

)P

(c

)

式中

為人為加入的一個(gè)修正因子，

0

1信道編碼-有擾離散信道的編碼定理這個(gè)不等式叫做Gallager界，它了碼字的誤碼上界，是Gallager在1965年推導(dǎo)出來的。如果該誤碼上界等于零或者足夠小，則可以說，總有一些編碼方法，能夠使誤碼足夠小。這就是第二定理。信道編碼-有擾離散信道的編碼定理（二）有擾信道編碼定理上面分析了在輸入端發(fā)送一個(gè)碼字ck

時(shí)，誤碼率的上界，即Gallager界。由于輸入端發(fā)送的碼字有多種可能，則由Gallager界，對所字取平均，可以推導(dǎo)出其平均誤碼率的上界，為Pe

eNE(R)其中，N是碼字長度，E(R)是叫做DMC信道的可靠性函數(shù)信道編碼-有擾離散信道的編碼定理而E(R)

定義為E(R)

max

max[R

E0

(,

Px

)]

Px當(dāng)最優(yōu)的及Px

選定以后，E(R)就只是R的函數(shù)，R

ln

M

/

N是信道的碼率，M

qK是可能的信息組合數(shù)，N是每碼字的碼元數(shù)，R表示每碼元攜帶的信息量，所以稱作碼率（或傳信率）。信道編碼-有擾離散信道的編碼定理從E(R)的定義式可以看出，E(R)越大，Pe

就越小，即可靠性就越高，這也是E(R)稱為可靠性函數(shù)的原因，也叫做誤差指數(shù)。其中的Eo

(,Px

)定義為1Q1

q1E0

(,

Px

)

ln

[

p(xi

)

p(

y

j

/

xi

)1

]1

j

0

i0也就是說，Eo

(,

Px

)

是以修正因子

及輸入符號概分布矢量

Px

為自變量的一個(gè)函數(shù)信道編碼-有擾離散信道的編碼定理由于E(R)是

R

E0

(,

Px

)

對

取極大值，所以一定有[R

E0

(,

Px

)]

R

E0

(,

Px

)

0

即R

E0

(,

Px

)信道編碼-有擾離散信道的編碼定理E0

(,Px

)

與

的關(guān)系曲線如下面左圖所示，因此可得到R與

的關(guān)系曲線，如下面右圖所示。01

E0

(,

Px

)1RR0C信道編碼-有擾離散信道的編碼定理E(R)與R的關(guān)系，由E(R)的定義式，可得E(R)

，如下圖R即E(R)和R之間的關(guān)系曲線的斜率為E(R)RCR00信道編碼-有擾離散信道的編碼定理R從0~

R0

的一段，由于此時(shí)

恒為1，所以是一條直線，而在R從R0

~C這一段，由于

從1逐漸減小至0，所以變成了一條曲線，各點(diǎn)處的斜率對應(yīng)于該點(diǎn)處的

，當(dāng)R=C時(shí)，

0

，所以此時(shí)的E(R)=0。信道編碼-有擾離散信道的編碼定理由此可以得到有擾離散信道的信道編碼定理：設(shè)離散無 信道為[X,P(y/x),Y]，其信道容量為C。當(dāng)信息傳輸率R<C時(shí)，只要碼長N足夠大，就一定存在一種編碼方法，使譯碼的錯(cuò)誤概率任意?。?/p>

Pe

0

）。信道編碼-有擾離散信道的編碼定理這是因?yàn)槠骄`碼率上界為Pe

eNE(R)也就是說，一定有一些編碼方法，其譯碼誤碼率滿足Pe

eNE(R)由于當(dāng)R<C時(shí)，E(R)>0，所以只要N足夠大，則Pe可以足夠小。信道編碼-有擾離散信道的編碼定理有擾離散信道的信道編碼逆定理：設(shè)離散無 信道為[X,P(y/x),Y]，其信道容量為C。當(dāng)信息傳輸率R>C時(shí)，無論碼長N多長，總也找不到一種編碼方法，使譯碼的錯(cuò)誤概率任意小。這兩個(gè)定理常常被寫在一起，統(tǒng)稱為有擾信道或噪聲信道的信道編碼定理。信道編碼-有擾離散信道的編碼定理第二定理也只是一個(gè)存在定理，它只說明錯(cuò)誤概率趨于零的好碼是存在的。但并沒有給出具體的編碼方法。因此，在1948年文章后，科學(xué)家們致力于各種編碼方法的實(shí)現(xiàn)，出現(xiàn)了代數(shù)編碼、卷積碼、循環(huán)碼等等。下面在分析差錯(cuò)控制的基本原理之后，來介紹這些編碼方法。信道編碼-有擾離散信道的編碼定理差錯(cuò)控制與信道編譯碼的基本原理（一）差錯(cuò)控制的途徑下面 從前面 推導(dǎo)的誤碼率公式以及信。息論的基本理論兩個(gè)方面來1.從公式分析由誤碼率的上界公式Pe

eNE(R)信道編碼-有擾離散信道的編碼定理E(R)~R關(guān)系曲線?？梢钥闯觯谕瑯拥男畔⒙?/p>

R的情況下，C大則E(R)也大?？梢钥闯?，要減小誤碼率，可以增加碼長N或者增加可靠性函數(shù)E(R)。增加E(R)的途徑主要有:（1）增加信道容量C右圖是不同信道容量下，E(R)C2C1RR1

R2R1<R2C1<C2信道編碼-有擾離散信道的編碼定理根據(jù) 公式，對于帶限波形信道，有因此，想增加信道容量C，可以采用的方法有：（i）增加帶寬W。有線：明線 對稱電纜

同軸電纜光纖無線：中波 短波

超短波 毫米波 微米波 光波)WN0PavC

W

log(1信道編碼-有擾離散信道的編碼定理、提高天線加大信號功率：提高增益、全向天線改定向天線等。降低噪聲功率：采用低噪聲器件、濾波等。（2）減小碼率R：對于（N，K）分組碼，碼率R=Klogq/N，要減小碼率R，方法有：（i）q、N不變，減小K。相當(dāng)于信道速率不變的情況下，減小信息傳輸率。信道編碼-有擾離散信道的編碼定理q、K不變，增大N。因此會提高信道速率，會占用更大的帶寬。K、N不變，減小q。即減小輸入輸出符號集中符號的個(gè)數(shù)，如果發(fā)送功率不變，則信號間隔增大，可靠性提高。（3）增加碼長N。如果要求R不變，則增加碼長N，相應(yīng)地也要增加K，以保持K/N不變。信道編碼-有擾離散信道的編碼定理2.從概念分析從信息論和概率論的角度，增加傳輸系統(tǒng)的可靠性，降低差錯(cuò)率，就是要增加冗余度，和進(jìn)行隨機(jī)化。（1）增加冗余度在第二章就反復(fù)強(qiáng)調(diào)過，增加冗余度可以提高能力。但是，增加冗余度，并不是隨便增加的，那樣效率會很低。在信道編碼中，要使得信息流中的冗余比特與信息比特有特定信道編碼-有擾離散信道的編碼定理的關(guān)系，這樣當(dāng)信息比特由于受到干擾而受損時(shí)，可以通過冗余比特來進(jìn)行檢測或恢復(fù)。至于冗余度增加多少、如何設(shè)計(jì)信息比特與冗余比特之間的關(guān)系等等，是糾錯(cuò)編碼理論要 的主要問題。常用的冗余資源有：時(shí)間。如ARQ系統(tǒng)的重復(fù)發(fā)送，就要占用

的時(shí)間。頻帶。由于增加了冗余度，使得信息傳輸率下降，如果想保持有用信息的傳輸速率不變，就要提高信

道的波特率，也就是要占用更大的帶寬。信道編碼-有擾離散信道的編碼定理（iii）功率。根據(jù)頻帶和信噪比的互換原則，也可以不增加信道帶寬，但提高發(fā)送功率，來達(dá)到同樣的目的。（iV）設(shè)備復(fù)雜度。增加碼長N可以減小差錯(cuò)率，但編 設(shè)備等的復(fù)雜度相應(yīng)有所增加。信道編碼-有擾離散信道的編碼定理（2）噪聲均化（隨機(jī)化）噪聲干擾的危害大小，不僅與噪聲的大小和總量

有關(guān)，還與噪聲的分布有關(guān)。同樣的噪聲總量，如果噪聲分布非常密集在一個(gè)時(shí)段，就會使該時(shí)段的信息受到很大的損傷，變得不可恢復(fù)。如果噪聲分布比較均勻，則雖然也會使信息收到損傷，但由于損傷不嚴(yán)重，可能會在編碼的可糾錯(cuò)范圍內(nèi)，從而得到正確的譯碼結(jié)果。所以，集中的噪聲干擾的危害要大于分散的噪聲干擾。噪聲均化就是要把噪聲盡可能地均勻分布到各個(gè)碼字。信道編碼-有擾離散信道的編碼定理噪聲均化的方法主要有：（i）增加碼長N。例如：設(shè)BSC信道的誤碼概率為

Pe

0.01

，設(shè)編碼的糾錯(cuò)能力為10%，即碼字中如果錯(cuò)誤的碼元數(shù)小于等于碼長N的10%，就可以通過譯碼加以糾正。如果碼字長度N=10，則當(dāng)碼字中有多于1個(gè)的碼元發(fā)生誤嗎時(shí)，就會產(chǎn)生譯碼差錯(cuò)。所以差錯(cuò)概率為110

4.27

1010m

3emem0(1

P

)P

m

P

1信道編碼-有擾離散信道的編碼定理可見，僅僅是將碼