信息論 第六章 信道編碼(2)

第六章信道編碼

思維世界的發(fā)展，在某種意義上說(shuō)，就是對(duì)驚奇的不斷擺脫。

-愛(ài)因斯坦（美國(guó)）

第六章信道編碼6.2.16.2.26.2.36.2.46.2.56.2.66.2.76.2.86.2.96.2.10一般概念一致監(jiān)督方程和一致監(jiān)督矩陣線(xiàn)性分組碼的生成矩陣線(xiàn)性分組碼的編碼線(xiàn)性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力線(xiàn)性分組碼的譯碼線(xiàn)性分組碼的性能漢明碼由已知碼構(gòu)造新碼的方法線(xiàn)性分組碼的碼限6.2線(xiàn)性分組碼

第六章信道編碼線(xiàn)性分組碼的編碼：線(xiàn)性分組碼的編碼過(guò)程分為兩步：把信息序列按一定長(zhǎng)度分成若干信息碼組，每組由k位組成；編碼器按照預(yù)定的線(xiàn)性規(guī)則(可由線(xiàn)性方程組規(guī)定)，把信息碼組變換成n重(n>k)碼字，其中(n－k)個(gè)附加碼元是由信息碼元的線(xiàn)性運(yùn)算產(chǎn)生的。信息碼組長(zhǎng)k位，有2k

個(gè)不同的信息碼組，則有2k

個(gè)碼字與它們一一對(duì)應(yīng)。6.2.1一般概念6.2線(xiàn)性分組碼

第六章信道編碼名詞解釋線(xiàn)性分組碼：通過(guò)預(yù)定的線(xiàn)性運(yùn)算將長(zhǎng)為k位的信息碼組變換成n重的碼字(n>k)。由2k

個(gè)信息碼組所編成的2k個(gè)碼字集合，稱(chēng)為線(xiàn)性分組碼。

碼矢：一個(gè)n重的碼字可以用矢量來(lái)表示

C=(Cn－1,Cn－2,…,C1,C0)所以碼字又稱(chēng)為碼矢。(n,k)線(xiàn)性碼：信息位長(zhǎng)為k，碼長(zhǎng)為n的線(xiàn)性碼。編碼效率/編碼速率/碼率/傳信率：R=k/n。它說(shuō)明了信道的利用效率，R是衡量碼性能的一個(gè)重要參數(shù)。6.2.1一般概念6.2線(xiàn)性分組碼

第六章信道編碼(1)一致監(jiān)督方程編碼就是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，以構(gòu)成碼字。在k個(gè)信息碼元之后附加r(r=n－k)個(gè)監(jiān)督碼元，使每個(gè)監(jiān)督元是其中某些信息元的模2和。舉例：k=3,r=4，構(gòu)成(7,3)線(xiàn)性分組碼。設(shè)碼字為

(C6,C5,C4,C3,C2,C1,C0)

C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)督元，每個(gè)碼元取“0”或“1”監(jiān)督元可按下面方程組計(jì)算6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣6.2線(xiàn)性分組碼(6.2.1)

第六章信道編碼一致監(jiān)督方程/一致校驗(yàn)方程：確定由信息元得到監(jiān)督元規(guī)則的一組方程稱(chēng)為監(jiān)督方程/校驗(yàn)方程。由于所有碼字都按同一規(guī)則確定，又稱(chēng)為一致監(jiān)督方程/一致校驗(yàn)方程。由于一致監(jiān)督方程是線(xiàn)性的，即監(jiān)督元和新信源之間是線(xiàn)性運(yùn)算關(guān)系，所以由線(xiàn)性監(jiān)督方程所確定的分組碼是線(xiàn)性分組碼。6.2線(xiàn)性分組碼6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣信息組對(duì)應(yīng)碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100

第六章信道編碼(2)舉例

信息碼組(101)，即C6=1,C5=0,C4=1

代入(6.2.1)得：C3=0,C2=0,C1=1,C0=1

由信息碼組(101)編出的碼字為

(1010011)。其它7個(gè)碼字如表6.2.1。表6.2.1(7,3)分組碼編碼表6.2線(xiàn)性分組碼6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣(6.2.1)

第六章信道編碼(3)一致監(jiān)督矩陣

為了運(yùn)算方便，將式

(6.2.1)監(jiān)督方程寫(xiě)成 矩陣形式，得 式(6.2.2)可寫(xiě)成

H.CT=0T或

C.HT=0

CT、HT、0T分別表 示C、H、0的轉(zhuǎn)置 矩陣。6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣6.2線(xiàn)性分組碼I4=

第六章信道編碼系數(shù)矩陣H的后四列組成一個(gè)(4×4)階單位子陣，用I4表示，H的其余部分用P表示(6.2.5)P4×3H(7,3)=[P4×3I4]所以6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣6.2線(xiàn)性分組碼

第六章信道編碼推廣到一般情況：對(duì)(n,k)線(xiàn)性分組碼，每個(gè)碼字中的r(r=n－k)個(gè)監(jiān)督元與信息元之間的關(guān)系可由下面的線(xiàn)性方程組確定6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣6.2線(xiàn)性分組碼(6.2.6)=

第六章信道編碼令上式的系數(shù)矩陣為H，碼字行陣列為C6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣6.2線(xiàn)性分組碼或(6.2.8)式(6.2.6)可寫(xiě)成(6.2.7)C0]稱(chēng)H為(n,k)線(xiàn)性分組碼的一致監(jiān)督矩陣，簡(jiǎn)稱(chēng)監(jiān)督矩陣。Hr×nC1×n=[Cn?1Cn?2=

第六章信道編碼(4)一致監(jiān)督矩陣特性對(duì)H各行實(shí)行初等變換，將后面r列化為單位子陣，于是得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣H的標(biāo)準(zhǔn)形式：后面r列是一單位子陣的監(jiān)督矩陣H。H陣的每一行都代表一個(gè)監(jiān)督方程，它表示與該行中“1”相對(duì)應(yīng)的碼元的模2和為0。6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣6.2線(xiàn)性分組碼(6.2.9)Hr×n

第六章信道編碼H的標(biāo)準(zhǔn)形式還說(shuō)明了相應(yīng)的監(jiān)督元是由哪些信息元決定的。例如(7,3)碼的H陣的第一行為(1011000)，說(shuō)明此碼的第一個(gè)監(jiān)督元等于第一個(gè)和第三個(gè)信息元的模2和，依此類(lèi)推。H陣的r行代表了r個(gè)監(jiān)督方程，也表示由H所確定的碼字有r個(gè)監(jiān)督元。為了得到確定的碼，r個(gè)監(jiān)督方程（或H陣的r行）必須是線(xiàn)性獨(dú)立的，這要求H陣的秩為r。若把H陣化成標(biāo)準(zhǔn)形式，只要檢查單位子陣的秩，就能方便地確定H陣本身的秩。6.2線(xiàn)性分組碼6.2.2一致監(jiān)督方程和一致監(jiān)督矩陣

第六章信道編碼(1)線(xiàn)性碼的封閉性線(xiàn)性碼的封閉性：線(xiàn)性碼任意兩個(gè)碼字之和仍是一個(gè)碼字。定理6.2.1：設(shè)二元線(xiàn)性分組碼CI(CI表示碼字集合)是由監(jiān)督矩陣H所定義的，若U和V為其中的任意兩個(gè)碼字，則U+V也是CI中的一個(gè)碼字。

[證明]：由于U和V是碼CI中的兩個(gè)碼字，故有

HUT=0T，HVT=0T

那么H(U+V)T=H(UT+VT)=HUT+HVT=0T

即U+V滿(mǎn)足監(jiān)督方程，所以U+V一定是一個(gè)碼字。 一個(gè)長(zhǎng)為n的二元序列可以看作是GF(2)(二元域)上的n維線(xiàn) 性空間中的一點(diǎn)。長(zhǎng)為n的所有2n

個(gè)矢量集合構(gòu)成了GF(2)

上的n維線(xiàn)性空間Vn。把線(xiàn)性碼放入線(xiàn)性空間中進(jìn)行研究，將使許多問(wèn)題簡(jiǎn)化而比較容易解決。(n,k)線(xiàn)性碼是n維線(xiàn)性空間Vn中的一個(gè)k維子空間Vk。6.2.3線(xiàn)性分組碼的生成矩陣6.2線(xiàn)性分組碼

第六章信道編碼(2)線(xiàn)性分組碼的生成矩陣在由(n,k)線(xiàn)性碼構(gòu)成的線(xiàn)性空間Vn

的k維子空間中，一定存在k個(gè)線(xiàn)性獨(dú)立的碼字：g1,g2,…,gk,。碼CI中其它任何碼字C都可以表示為這k個(gè)碼字的一種6.2.3線(xiàn)性分組碼的生成矩陣6.2線(xiàn)性分組碼G是一個(gè)k×n階矩陣。線(xiàn)性組合，即

C=mk-1g1

+mk-2

g2

+…+m0

gk

mi∈GF(2),i=0,1,k?1。寫(xiě)成矩陣形式得

m=[mk-1mk-2

…

m0

]是待編碼的信息組（6.2.10）

(6.2.11)

第六章信道編碼G中每一行g(shù)i=(gi1,gi2,…,gin)都是一個(gè)碼字；對(duì)每一個(gè)信息組m，由矩陣G都可以求得(n,k)線(xiàn)性碼對(duì)應(yīng)的碼字。生成矩陣：由于矩陣G生成了(n,k)線(xiàn)性碼，稱(chēng)矩陣G為(n,k)線(xiàn)性碼的生成矩陣。(n,k)線(xiàn)性碼的每一個(gè)碼字都是生成矩陣G的行矢量的線(xiàn)性組合，所以它的2k

個(gè)碼字構(gòu)成了由G的行張成的n維空間的一個(gè)k維子空間Vk。6.2.3線(xiàn)性分組碼的生成矩陣6.2線(xiàn)性分組碼(6.2.11)=

第六章信道編碼線(xiàn)性系統(tǒng)分組碼 通過(guò)行初等變換，將G化為前k列是單位子陣的標(biāo)準(zhǔn)形式6.2.3線(xiàn)性分組碼的生成矩陣6.2線(xiàn)性分組碼(6.2.13)(6.2.12)j=1,2,,n?ki=1,2,…,k,…,C0)=(mk-1

,mk-2

,

…,m0

)Gk×n,得將上式代入C1×n=(Cn

?1,Cn

?2=[IkQk×r]Gk×n…

第六章信道編碼線(xiàn)性系統(tǒng)分組碼：用標(biāo)準(zhǔn)生成矩陣Gk×n

編成的碼字，前面k位為信息數(shù)字，后面r=n－k位為校驗(yàn)字，這種信息數(shù)字在前校驗(yàn)數(shù)字在后的線(xiàn)性分組碼稱(chēng)為線(xiàn)性系統(tǒng)分組碼。當(dāng)生成矩陣G確定之后，(n,k)線(xiàn)性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問(wèn)題也同樣被解決了。6.2線(xiàn)性分組碼6.2.3線(xiàn)性分組碼的生成矩陣

第六章信道編碼(3)舉例6.2.3線(xiàn)性分組碼的生成矩陣6.2線(xiàn)性分組碼=(1010011)

C1×7=m1×4G4×7(7,4)線(xiàn)性碼的生成矩陣為

G4×7=若m1×4=(1010)，則由于生成矩陣G的每一行都是一個(gè)碼字，所以G的每行都滿(mǎn)足Hr×nCTn×1=0Tr×1，則有Hr×nGTn×k=0Tr×k

或Gk×nHTn×r=0k×r線(xiàn)性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接互換。(4)生成矩陣與一致監(jiān)督矩陣的關(guān)系6.2.3線(xiàn)性分組碼的生成矩陣?yán)?

已知(7,4)線(xiàn)性系統(tǒng)碼的監(jiān)督矩陣為對(duì)偶碼：一個(gè)(n,k)線(xiàn)性碼CI，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構(gòu)造另一個(gè)(n,n－k)線(xiàn)性碼CId

，稱(chēng)碼CId為原碼的對(duì)偶碼。(7,3)碼的監(jiān)督矩陣H(7,3)是(7,4)碼的生成矩陣G(7,4)

(7,4)碼的監(jiān)督矩陣H(7,4)是(7,3)碼的生成矩陣G(7,3)(n,k)線(xiàn)性碼的編碼就是根據(jù)線(xiàn)性碼的監(jiān)督矩陣或生成矩陣將長(zhǎng)為k的信息組變換成長(zhǎng)為n(n>k)的碼字。利用監(jiān)督矩陣構(gòu)造(7,3)線(xiàn)性分組碼的編碼電路：設(shè)碼字矢量為C=(C6C5C4C3C2C1C0)碼的監(jiān)督矩陣為線(xiàn)性分組碼的編碼根據(jù)方程組可直接畫(huà)出(7,3)碼的并行和串行編碼電路。漢明距離、漢明重量和漢明球漢明距離：在(n,k)線(xiàn)性碼中，兩個(gè)碼字U、V之間對(duì)應(yīng)碼元位上符號(hào)取值不同的個(gè)數(shù)，稱(chēng)為碼字U、V的漢明距離。例：(7,3)碼的兩個(gè)碼字U=0011101,V=0100111之間第2、3、4和6位不同。因此，碼字U和V的距離為4。線(xiàn)性分組碼的一個(gè)碼字對(duì)應(yīng)于n維線(xiàn)性空間中的一點(diǎn)，碼字間的距離即為空間中兩對(duì)應(yīng)點(diǎn)的距離。因此，碼字間的距離滿(mǎn)足一般距離公理：線(xiàn)性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力最小距離dmin：在(n,k)線(xiàn)性碼的碼字集合中，任意兩個(gè)碼字間距離的最小值，叫做碼的最小距離。若C(i)和C(j)

是任意兩個(gè)碼字，則碼的最小距離表示為碼的最小距離是衡量碼的抗干擾能力（檢、糾錯(cuò)能力）的重要參數(shù)。碼的最小距離越大，碼的抗干擾能力就越強(qiáng)。漢明球：以碼字C為中心，半徑為t的漢明球是與C的漢明距離≤t的向量全體集合SC(t)

任意兩個(gè)漢明球不相交最大程度取決于任意兩個(gè)碼字之間的最小漢明距離dmin。

漢明重量W：碼字中非0碼元符號(hào)的個(gè)數(shù)，稱(chēng)為該碼字的漢明重量。在二元線(xiàn)性碼中，碼字重量就是碼字中“1”的個(gè)數(shù)。最小重量Wmin

：線(xiàn)性分組碼CI中，非0碼字重量的最小值，叫做碼CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}最小距離與最小重量的關(guān)系：線(xiàn)性分組碼的最小距離等于它的最小重量。

[證明]：設(shè)線(xiàn)性碼CI，且U∈CI,V∈CI，又設(shè)U－V=Z，由線(xiàn)性碼的封閉性知，Z∈CI

。因此，d(U,V)=W(Z)，由此可推知，線(xiàn)性分組碼的最小距離必等于非0碼字的最小重量。

第六章信道編碼(2)最小距離與檢、糾錯(cuò)能力一般地說(shuō)，線(xiàn)性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯(cuò)能力越強(qiáng)。檢錯(cuò)能力：如果一個(gè)線(xiàn)性碼能檢出長(zhǎng)度≤l個(gè)碼元的任何錯(cuò)誤圖樣，稱(chēng)碼的檢錯(cuò)能力為l。糾錯(cuò)能力：如果線(xiàn)性碼能糾正長(zhǎng)度≤t個(gè)碼元的任意錯(cuò)誤圖樣，稱(chēng)碼的糾錯(cuò)能力為t。6.2線(xiàn)性分組碼6.2.5線(xiàn)性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力最小距離與糾錯(cuò)能力：(n,k)線(xiàn)性碼能糾t個(gè)錯(cuò)誤的充要條件是碼的最小距離為

[證明]：

設(shè)發(fā)送的碼字為V；接收的碼字為R；U為任意其它碼字；則矢量V、R、U間滿(mǎn)足距離的三角不等式，

d(R,V)+d(R,U)≥d(U,V)

又設(shè)信道干擾使碼字中碼元發(fā)生錯(cuò)誤的實(shí)際個(gè)數(shù)為t’，且t’≤td(R,V)＝t’≤t

由于d(U,V)≥dmin=2t+1，代入上式得：

d(R,U)≥d(U,V)－d(R,V)=2t+1－t’>t

第六章信道編碼上式表明：如果接收字R中錯(cuò)誤個(gè)數(shù)t’≤t，那么接收字R和 發(fā)送字V間距離≤t，而與其它任何碼字間距離都大于t，按最 小距離譯碼把R譯為V。此時(shí)譯碼正確，碼字中的錯(cuò)誤被糾正。幾何意義：6.2.5線(xiàn)性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力6.2線(xiàn)性分組碼t

dmin圖6.2.3dmin=5,碼距和糾錯(cuò)能力關(guān)系示意圖最小距離與檢錯(cuò)能力：(n,k)線(xiàn)性碼能夠發(fā)現(xiàn)l個(gè)錯(cuò)誤的充要條件是碼的最小距離為

dmin=l+1或l=dmin－1

[證明]：設(shè)發(fā)送的碼字為V；接收的碼字為R；U為任意其它碼字；則矢量V、R、U間滿(mǎn)足距離的三角不等式，

d(R,V)+d(R,U)≥d(U,V)

又設(shè)信道干擾使碼字中碼元發(fā)生錯(cuò)誤的實(shí)際個(gè)數(shù)為l’，且l’≤ld(R,V)＝l’≤l

由于d(U,V)≥dmin=l+1，代入上式得：

d(R,U)≥d(U,V)－d(R,V)=l+1－l’>0

第六章信道編碼上式表明：由于接收字R與其它任何碼字U的距離都大于0， 則說(shuō)明接收字R不會(huì)因發(fā)生l’個(gè)錯(cuò)誤變?yōu)槠渌a字，因而必能發(fā) 現(xiàn)錯(cuò)誤。幾何意義：6.2.5線(xiàn)性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力6.2線(xiàn)性分組碼l

dmin圖6.2.4dmin=4,碼距和檢錯(cuò)能力關(guān)系示意圖

第六章信道編碼最小距離與檢、糾錯(cuò)能力：(n,k)線(xiàn)性碼能糾t個(gè)錯(cuò)誤，并能發(fā)現(xiàn)l個(gè)錯(cuò)誤(l>t)的充要條件是碼的最小距離為

dmin=t+l+1或t+l=dmin－1(6.2.23)[證明]：因?yàn)閐min>2t+1，根據(jù)最小距離與糾錯(cuò)能力定理，該碼可 糾t個(gè)錯(cuò)誤。 因?yàn)閐min>l+1，根據(jù)最小距離與檢錯(cuò)能力定理，該碼有檢l個(gè) 錯(cuò)誤的能力。

糾錯(cuò)和檢錯(cuò)不會(huì)發(fā)生混淆：設(shè)發(fā)送碼字為V，接收字為R，實(shí)際錯(cuò)誤數(shù)為l’，且t<l’≤l。這時(shí)R與其它任何碼字U的距離(6.2.24)

d(R,U)≥d(U,V)－d(R,V)=t+l+1－l’>t+1>t因而不會(huì)把R誤糾為U。6.2線(xiàn)性分組碼6.2.5線(xiàn)性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力

幾何意義：當(dāng)(n,k)線(xiàn)性碼的最小距離dmin

給定后，可按實(shí)際需要靈活安排糾錯(cuò)的數(shù)目。例如，對(duì)dmin=8的碼，可用來(lái)糾3檢4錯(cuò)，或糾2檢5錯(cuò)，或糾1檢6錯(cuò)，或者只用于檢7個(gè)錯(cuò)誤。

第六章信道編碼(3)線(xiàn)性碼的最小距離與監(jiān)督矩陣的關(guān)系定理6.2.2：設(shè)H為(n,k)線(xiàn)性碼的一致監(jiān)督矩陣，若H中任意S列線(xiàn)性無(wú)關(guān)，而H中存在(S+1)列線(xiàn)性相關(guān)，則碼的最小距離為(S+1)。（矩陣H的秩為S）定理6.2.3：若碼的最小距離為(S+1)，則該碼的監(jiān)督矩陣的任意S列線(xiàn)性無(wú)關(guān)，而必存在有相關(guān)的(S+1)列。定理6.2.4：在二元線(xiàn)性碼的監(jiān)督矩陣H中，如果任一列都不是全“0”，且任兩列都不相等，則該碼能糾一個(gè)錯(cuò)誤。6.2線(xiàn)性分組碼6.2.5線(xiàn)性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力

第六章信道編碼(1)伴隨式和錯(cuò)誤檢測(cè)①用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：