信息論與編碼第二講

信息論與編碼第二講第一頁，共八十四頁，編輯于2023年，星期六主要內(nèi)容1234信道編碼定理線性分組碼的編譯碼碼的檢、糾錯(cuò)能力信道編碼概念第二頁，共八十四頁，編輯于2023年，星期六一、信道編碼概念第三頁，共八十四頁，編輯于2023年，星期六1.1通信系統(tǒng)模型第四頁，共八十四頁，編輯于2023年，星期六信源編碼器

把消息轉(zhuǎn)換成為二進(jìn)制形式的信息序列，并且為了使傳輸有效，去掉了與傳輸信息無關(guān)的多余度。糾錯(cuò)編碼器

為了抗擊傳輸過程中各種干擾，要人為地增加一些多余度，使其具有自動(dòng)檢錯(cuò)或糾錯(cuò)能力。糾錯(cuò)碼譯碼器由于信道干擾，該信息序列中可能有錯(cuò)誤，經(jīng)過糾錯(cuò)碼譯碼器，對錯(cuò)誤進(jìn)行糾正。第五頁，共八十四頁，編輯于2023年，星期六信源指原來的信源和信源編碼器，其輸出是二(多)進(jìn)制信息序列。

信道包括發(fā)射機(jī)、實(shí)際信道（或稱傳輸媒質(zhì)）和接收機(jī)在內(nèi)的廣義信道，它的輸入是二（多）進(jìn)制數(shù)字序列，輸出是二（多）進(jìn)制數(shù)字序列。

1.2編碼信道第六頁，共八十四頁，編輯于2023年，星期六第七頁，共八十四頁，編輯于2023年，星期六二、信道編碼定理第八頁，共八十四頁，編輯于2023年，星期六2.1信道編碼理論

每個(gè)信道具有確定的信道容量C，對任何小于C的碼率Rs，存在有速率為Rs、碼長為n的編碼方法，若用最大似然譯碼，則隨著碼長的n增加其譯碼錯(cuò)誤概率Pe可任意小，即：第九頁，共八十四頁，編輯于2023年，星期六式中，E(RS)為正實(shí)函數(shù)，稱為誤差指數(shù)，它與RS、C的關(guān)系如下圖所示。圖中，C1、C2為信道容量，且C1＞C2。第十頁，共八十四頁，編輯于2023年，星期六2.2信道編碼基本思想

第十一頁，共八十四頁，編輯于2023年，星期六第十二頁，共八十四頁，編輯于2023年，星期六第十三頁，共八十四頁，編輯于2023年，星期六第十四頁，共八十四頁，編輯于2023年，星期六第十五頁，共八十四頁，編輯于2023年，星期六2.3譯碼平均錯(cuò)誤概率

第十六頁，共八十四頁，編輯于2023年，星期六第十七頁，共八十四頁，編輯于2023年，星期六第十八頁，共八十四頁，編輯于2023年，星期六2.4譯碼規(guī)則

第十九頁，共八十四頁，編輯于2023年，星期六2.4.1最大后驗(yàn)概率譯碼準(zhǔn)則第二十頁，共八十四頁，編輯于2023年，星期六例題第二十一頁，共八十四頁，編輯于2023年，星期六第二十二頁，共八十四頁，編輯于2023年，星期六2.4.2極大似然譯碼準(zhǔn)則第二十三頁，共八十四頁，編輯于2023年，星期六例題第二十四頁，共八十四頁，編輯于2023年，星期六第二十五頁，共八十四頁，編輯于2023年，星期六兩種譯碼準(zhǔn)則比較第二十六頁，共八十四頁，編輯于2023年，星期六2.4.3最小碼距譯碼準(zhǔn)則第二十七頁，共八十四頁，編輯于2023年，星期六第二十八頁，共八十四頁，編輯于2023年，星期六最小碼距第二十九頁，共八十四頁，編輯于2023年，星期六最小碼距對錯(cuò)誤概率的影響第三十頁，共八十四頁，編輯于2023年，星期六最小距離譯碼準(zhǔn)則第三十一頁，共八十四頁，編輯于2023年，星期六最小距離準(zhǔn)則與最大似然準(zhǔn)則關(guān)系第三十二頁，共八十四頁，編輯于2023年，星期六例：重復(fù)碼早期的檢錯(cuò)碼為重復(fù)碼。該碼用000代表信息“0”，用111代表信息“1”。顯然所增加的2個(gè)碼元并不增多信息，是多余的,使傳信率降低。此外，除去傳送信息的000和111這2種組合外,還有001,010,011,100,101,110等6種組合沒采用。當(dāng)信道上信噪比足夠大時(shí),可認(rèn)為000和111中產(chǎn)生的錯(cuò)誤一般不會(huì)多于一個(gè)碼元。如接收到001,010,100,在接收端怎么譯碼呢？根據(jù)最小碼距譯碼準(zhǔn)則，可判定實(shí)際上是000,即信息為0；同理,如接收到011,110,101,在接收端也可判定111,即信息為1?？梢?多余碼元可檢出并糾正一個(gè)錯(cuò)誤，這樣就提高了傳信的可靠性。

第三十三頁，共八十四頁，編輯于2023年，星期六三、線性分組碼第三十四頁，共八十四頁，編輯于2023年，星期六第三十五頁，共八十四頁，編輯于2023年，星期六m2m1m0C5C4C3C0C1C23.1生成矩陣第三十六頁，共八十四頁，編輯于2023年，星期六[m2m1m0]100111010110001011=[c5c4c3c2c1c0]mG=C100111010110001011張成碼空間的三個(gè)基，本身也是碼字。第三十七頁，共八十四頁，編輯于2023年，星期六第三十八頁，共八十四頁，編輯于2023年，星期六信息空間到碼空間的線性映射信息組(m2m1m0) 碼字(c5c4c3c2c1c0) 000 000000 001 001011 010 010110 011 011101 100 100111 101 101100 110 110001 111111010

k維k重

k維n重

信息空間

碼字空間第三十九頁，共八十四頁，編輯于2023年，星期六

gk-1G== ? g1 g0c

=m

G=[mk-1,……m1

m0][gk-1

…g1g0]T

=mk-1

gk-1+…+m1

g1+m0

g0

第四十頁，共八十四頁，編輯于2023年，星期六生成矩陣G是由k個(gè)行矢量組成的，其中的每個(gè)行矢量gi既是一個(gè)基底，也是一個(gè)碼字。任何碼字都是生成矩陣G的k個(gè)行矢量的線性組合。只要這k個(gè)行矢量線性無關(guān)，就可以作為k個(gè)基底張成一個(gè)k維n重空間，它是n維n重空間的一個(gè)子空間，子空間的所有2k個(gè)矢量構(gòu)成碼集C。第四十一頁，共八十四頁，編輯于2023年，星期六不同的生成矩陣產(chǎn)生不同的碼，生成矩陣的特點(diǎn)決定了碼的特點(diǎn)。由于構(gòu)成同一空間的基底不是唯一的，所以不同的基底或生成矩陣可能生成同一碼集。碼集相同，編碼不一定相同，因?yàn)榫幋a涉及碼集和映射兩個(gè)因素，碼集一樣而映射方法不同不能說是同樣的編碼。第四十二頁，共八十四頁，編輯于2023年，星期六由于基底不是唯一的，因此允許將基底線性組合后挑出其中k個(gè)線性無關(guān)的矢量作為新的基底，依然可以張成同一個(gè)碼空間。對應(yīng)到生成矩陣，等效于允許通過行運(yùn)算（行交換、行的線性組合）改變生成矩陣的行而不改變碼集，只要保證矩陣的秩仍是k（k行線性無關(guān))。所以，任何生成矩陣可通過行運(yùn)算轉(zhuǎn)化成“系統(tǒng)碼”形式。第四十三頁，共八十四頁，編輯于2023年，星期六3.2系統(tǒng)碼把信息組原封不動(dòng)搬到碼字前k位的(n,k)碼，其碼字具有如下形式：c=(cn-1,…cn-k

,cn-k-1,…,c0)=(mk-1,…m1,m0,cn-k-1,…c0)其生成矩陣具有如下形式：G=[IkP]=

第四十四頁，共八十四頁，編輯于2023年，星期六3.3校驗(yàn)矩陣對于k×n矩陣G，存在一個(gè)(n-k)×n矩陣H，使得G的行空間和H正交。基底數(shù)k的碼空間C是n維n重空間的子空間，若能找出全部n個(gè)基底的另外n-k個(gè)基底，也就找到了對偶空間D。將D空間的n-k個(gè)基底排列起來可構(gòu)成一個(gè)(n-k)×n矩陣，稱為是碼空間C的校驗(yàn)矩陣H，它與所有碼字正交。既然用k個(gè)基底能產(chǎn)生一個(gè)(n,k)線性碼，那么也能用其余n-k個(gè)基底產(chǎn)生一個(gè)(n,n-k)線性碼，稱（n,n-k）線性碼是(n,k)線性碼的對偶碼。C和D的對偶是相互的，G是C的生成矩陣又是D的校驗(yàn)矩陣，而H是D的生成矩陣又是C的校驗(yàn)矩陣。第四十五頁，共八十四頁，編輯于2023年，星期六

n維n重空間R k維k重k維n重 n-k維n重信息組碼空間C

對偶空間D

空間m

G

H

圖3-1碼空間與映射第四十六頁，共八十四頁，編輯于2023年，星期六c是G空間的一個(gè)碼字，那么由正交性得到：

c

HT=0 0代表零陣，它是[1×n]×[n×(n-k)]=1×(n-k)矢量。上式可以用來檢驗(yàn)一個(gè)n重矢量是否為碼字：若等式成立，該n重是碼字，否則不是碼字。由于生成矩陣的每行都是一個(gè)碼字，因此有：

GHT=0 這里0代表一個(gè)[k×n]×[n×(n-k)]=k×(n-k)的零矩陣。第四十七頁，共八十四頁，編輯于2023年，星期六對于系統(tǒng)碼，其校驗(yàn)矩陣也是規(guī)則的，必為：

H＝[PT┆In-k]

因?yàn)椋?/p>

GHT=[Ik┆P][PT┆In-k]T

=[IkP]+[P

In-k]

=[P]+[P]

=0

第四十八頁，共八十四頁，編輯于2023年，星期六例3.1考慮一個(gè)(7，4)碼，其生成矩陣是：

G= =[I4

P]

①對于信息組m=(1011),編出的碼字是什么？②畫一個(gè)（7，4）分組碼編碼器原理圖。 ③若接收到一個(gè)7位碼r=(1001101),檢驗(yàn)它是否碼字？

第四十九頁，共八十四頁，編輯于2023年，星期六3.3伴隨式與譯碼線性分組碼C=(cn-1,……c1,c0)，接收碼R=(rn-1,……r1,r0)，

差錯(cuò)圖案:E=(en－1,…，e1,e0)=R–C 對于二進(jìn)制碼，有E=R＋C及 R=C＋E RHT=(C＋E)HT=CHT＋EHT=0＋EHT=EHT如收碼無誤，必有R=C即RHT=0,如信道差錯(cuò)E0，必有RHT=EHT0。定義伴隨式S：S=(sn-k-1,…，s1,s0)=RHT=EHT S僅與E有關(guān)，而與C無關(guān)。

第五十頁，共八十四頁，編輯于2023年，星期六從物理意義看，伴隨式S并不反映發(fā)送的碼字是什么，而只反映信道對碼字造成了怎樣的干擾。伴隨式S是一個(gè)(n-k)重矢量，只有2n-k種可能的組合；而差錯(cuò)圖案E是n重矢量，共有2n個(gè)可能的組合。因此，同一伴隨式可能對應(yīng)若干個(gè)不同的差錯(cuò)圖案。在接收端我們并不知道發(fā)碼C究竟是什么，但可以知道HT和接收碼是R什么，從而算出S是什么。譯碼最重要的任務(wù)：從伴隨式S找出C的估值。第五十一頁，共八十四頁，編輯于2023年，星期六

一般的譯碼思路RHT

=S

E

C=R＋E

E

m

編碼C

R S= no計(jì)算輸出?

mGRHT=0？

ER+Eyes

輸出R

圖3-3譯碼過程框圖第五十二頁，共八十四頁，編輯于2023年，星期六S=(sn-k-1,…，s1,s0)=EHT=(en－1,…e1,e0) (3-18)展開成線性方程組形式，為：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h00方程組中有n個(gè)未知數(shù)en－1,…e1,e0，卻只有n-k個(gè)方程。第五十三頁，共八十四頁，編輯于2023年，星期六在二元域中，少一個(gè)方程導(dǎo)致兩個(gè)解，少兩個(gè)方程導(dǎo)致四個(gè)解…少n-(n-k)=k個(gè)方程導(dǎo)致有2k個(gè)解。在E的2k個(gè)解中選一，最合理的方法是概率譯碼，它把所有2k個(gè)解的重量(差錯(cuò)圖案E中1的個(gè)數(shù))作比較，選擇其中最輕者作為E的估值。該算法的理論根據(jù)就是最小漢明距離譯碼。

第五十四頁，共八十四頁，編輯于2023年，星期六3.4標(biāo)準(zhǔn)陣列第五十五頁，共八十四頁，編輯于2023年，星期六某一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣：G=碼集：{00000,10111,01101,11010}S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第五十六頁，共八十四頁，編輯于2023年，星期六E2n-k+C2kE2n-k+CiE2n-k-1+C1E2n-k+C0=E2n-kEj+C2k－1Ej+CiEj+C1Ej+C0=EjE1+C2k－1E1+CiE1+C1E1+C0=E1E0+C2k－1=C2k－1E0+Ci=CiE0+C1=C1E0+C0=0+0=0表3-2標(biāo)準(zhǔn)陣列譯碼表第五十七頁，共八十四頁，編輯于2023年，星期六對于(6,3)碼的8個(gè)碼矢：v1=(000000),v2=(001110),v3=(010101),v4=(100011),v5=(011011),v6=(101101),v7=(110110),v8=(111000)。其標(biāo)準(zhǔn)陣列：第五十八頁，共八十四頁，編輯于2023年，星期六例：某一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣是G=，設(shè)收碼是R=(10101),請先構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表，然后譯出發(fā)碼的估值?。分析：H=[PTI3]=，由S=(E+C)HT=EHT得：

s2=e4+e3+e2

s1=e4+e15個(gè)未知數(shù)，3個(gè)方程

s0=e4+e3+e0

必有4組解令S0=000,并分別令e4e3=00、01、10、11,解得E0的4組解是(00000)(01101)(10111)(11010)，取E0=(00000)再依次令S=001,010,011…每次有4組解，取最輕者為“解”。其中有的組最輕解是唯一的，有的卻不是，比如伴隨式S=(011)的4個(gè)解是(00011)、(10100)、(01110)、(11001)，其中(00011)和(10100)并列最小重量，任取其中一個(gè)？第五十九頁，共八十四頁，編輯于2023年，星期六S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第六十頁，共八十四頁，編輯于2023年，星期六第六十一頁，共八十四頁，編輯于2023年，星期六查表譯碼方法[1]計(jì)算R的伴隨式S=RHT；[2]找出伴隨式S等于RHT的陪集首el；[3]碼矢v=R+el就是發(fā)送碼矢。第六十二頁，共八十四頁，編輯于2023年，星期六例3.3對于(6,3)碼，校驗(yàn)矩陣為：S=EHT第六十三頁，共八十四頁，編輯于2023年，星期六如果發(fā)送的碼矢為v=(111000)，接收的矢量r=(111001)，怎樣來譯碼？第六十四頁，共八十四頁，編輯于2023年，星期六四、碼的糾、檢錯(cuò)能力第六十五頁，共八十四頁，編輯于2023年，星期六4.1計(jì)算最小距離的方法[1]直接計(jì)算。含2k個(gè)碼字的碼集需計(jì)算2k(2k-1)/2個(gè)距離后才能找出dmin。[2]利用群碼封閉性——兩碼字之和仍是碼字：

d(C1,C2)=w(C1C2)=w(C3) 可得定理3.1:線性分組碼的最小距離等于碼集中非零碼字的最小重量：

dmin=min{w(Ci)}CiC及Ci0于是最小距離問題轉(zhuǎn)化為尋找最輕碼字問題，含2k個(gè)碼字的碼集僅需計(jì)算2k次。第六十六頁，共八十四頁，編輯于2023年，星期六[3]利用校驗(yàn)矩陣H的秩定理3.4：(n,k)線性分組碼最小距離等于dmin的充要條件是校驗(yàn)矩陣H中有（dmin-1)列線性無關(guān)。換言之，dmin=校驗(yàn)矩陣H的秩+1。第六十七頁，共八十四頁，編輯于2023年，星期六定理3.2:任何最小距離dmin的線性分組碼，其檢測隨機(jī)差錯(cuò)的能力為（dmin－1）。

定理3.3:

任何最小距離等于dmin的線性分組碼，其糾正隨機(jī)差錯(cuò)的能力t為：

t=INT若最小距離為dmin的碼同時(shí)能檢ed個(gè)、糾ec個(gè)差錯(cuò),則 ed＋ec

dmin–1

ec

ed。

抑制糾錯(cuò)能力才能提高檢錯(cuò)能力。第六十八頁，共八十四頁，編輯于2023年，星期六第六十九頁，共八十四頁，編輯于2023年，星期六例：每個(gè)分組碼dmin=7，那么怎么來糾錯(cuò)和檢錯(cuò)？（1）糾錯(cuò)t=3；（2）2重糾錯(cuò)，并且4重錯(cuò)誤檢測

t=2,D=4；（3）6重錯(cuò)誤檢測D=6。第七十頁，共八十四頁，編輯于2023年，星期六定理3.5：(n,k)線性分組碼的最小距離必定小于等于(n-k+1)即

dmin

(n-k+1)

因?yàn)镠是(n-k)n矩陣，該矩陣的秩最大不會(huì)超過(n-k)，即線性無關(guān)的列不會(huì)超過(n-k)。第七十一頁，共八十四頁，編輯于2023年，星期六

4.2完備碼如果某碼的伴隨式組合數(shù)目恰好和不大于t個(gè)差錯(cuò)的圖案數(shù)目相等，相當(dāng)于在標(biāo)準(zhǔn)陣列中能將所有重量不大于t的差錯(cuò)圖案選作陪集首而沒有一個(gè)陪集首的重量大于t，這時(shí)的伴隨式就能和可糾差錯(cuò)圖案實(shí)現(xiàn)一一對應(yīng)，校驗(yàn)位得到最合理的利用。滿足方程：

的二元(n,k)線性分組碼稱為完備碼。t=1的完備碼叫漢明碼。第七十二頁，共八十四頁，編輯于2023年，星期六4.3漢明碼糾錯(cuò)能力t=1的完備碼稱為漢明碼。漢明碼指一類碼，既可以是二進(jìn)制的，也可以是非二進(jìn)制的。二進(jìn)制漢明碼應(yīng)滿足條件：2n-k=1+n。令r=n-k，漢明碼n和k服從以下關(guān)系碼長：n=2r-1

信息位：k=2r-1-r

最小距離dmin=3 當(dāng)r＝3、4、5、6、7、8…時(shí)，有以下漢明碼：(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。第七十三頁，共八十四頁，編輯于2023年，星期六

從n維矢量空間的角度看(n,k)完備碼，假定每個(gè)碼字為中心放置一個(gè)半徑t的球，與該碼漢明距離小于等于t的所有接收矢量均包含在此球內(nèi)，每球包含的矢量點(diǎn)數(shù)是。以碼集2k個(gè)碼字為中心、半徑t(不相重疊)的球共可包含2k

點(diǎn)。由于n重矢量的總數(shù)是2n個(gè)，包含在2k個(gè)球中的點(diǎn)數(shù)不可能多于總點(diǎn)數(shù)，所以下列不等式必定成立：

第七十四頁，共八十四頁，編輯于2023年，星期六如果上式等號(hào)成立，表示全部2n個(gè)接收矢量等分地落在2k個(gè)半徑t的球內(nèi)，而沒有一個(gè)矢量落在球外，這就是完備碼。圍繞完備碼2k個(gè)碼字、漢明距離為t的所有球都是不相交的、不相切的，每一個(gè)接收矢量不是落在這個(gè)球、就是落在那個(gè)球內(nèi)，沒有一點(diǎn)是在球外。這樣，接收矢量離碼字的距離至多為t，所有重量Wt的差錯(cuò)圖案都能通過最小距離譯碼得到糾正，而所有重量Wt+1的差錯(cuò)圖案都不能糾正。第七十五頁，共八十四頁，編輯于2023年，星期六例3.4:構(gòu)造一個(gè)m=3的二元(7，4)漢明碼。

0001111列置換

1110100

H= 0110011 0111010 1010101 1101001那么系統(tǒng)漢明碼的生成矩陣G為：

1000101 G=[I4

P]= 0100111 0010110 0001011 第七十六頁，共八十四頁，編輯于2023年，星期六

4.4高萊碼高萊碼是二進(jìn)制（23，12）線性碼，其最小距離dmin＝7，糾錯(cuò)能力t=3。由于滿足：

223-12=2048=它也是完備碼。在(23,12)碼上添加一位奇偶位即得二進(jìn)制線性(24,12)擴(kuò)展高萊碼，其最小距離dmin＝8。第七十七頁，共八十四頁，編輯于2023年，星期六

4.5擴(kuò)展碼(n,k)分組碼+1位奇偶校驗(yàn)=(n＋1,k)擴(kuò)展碼校驗(yàn)位c校的選擇應(yīng)滿足校驗(yàn)方程

c

n－1

…c1c0

c

校＝0

矩陣H與H擴(kuò)的關(guān)系如下：

0 H 0 k個(gè)0H擴(kuò)＝ ?

0 111…1 1 (n+1)個(gè)1從最小距離角度看，若擴(kuò)展前原碼的最小距離dmin是奇數(shù),則擴(kuò)展后的最小距離變成dmin+1；若原碼的最小距離是偶數(shù)，則偶校驗(yàn)不改變其最小距離。第七十八頁，共八十四頁，編輯于2023年，星期六

4.6縮短碼(n,k)分組碼縮短i位=(n-i,k-i)縮短碼如果縮短1位,可在碼集中去掉所有第1位是0的碼字,剩下的碼組成一個(gè)新的碼集，其最小碼重不變；如果縮短2位,可在碼集中去掉所有前2位是0的碼字,剩下的碼組成一個(gè)新的碼集，其最小碼重仍不變；……以此類推，縮短i位，在碼集中去掉所有前i位是0的碼字，剩下碼集的dmin與縮短前一樣。因此,（n-i,k-i,dmin）縮短碼與原（n,k,dmin）碼具有相同的糾檢錯(cuò)能力。第七十九頁，共八十四頁，編輯于2023年，星期六縮短后的生成矩陣Gs(刪除前i行、前i列）

g(k-1)(n-1)g(k-1)(n-2)……g(k-1)(n-i)g(k-1)(n-i-1)…………g(k-1)0 g(k-2)(n-1)g(k-2)(n-2)……g(k-2)(n-i)g(k-2)(n-i-1)…………g(k-2)0Gs=?