信息論與編碼-第15講-信道編碼-線性分組碼

第1頁2024/4/14

第8章線性分組碼8.1線性分組碼概念8.2線性分組碼的監(jiān)督矩陣和生成矩陣8.3線性分組碼的編碼8.4線性分組碼的最小距離、檢錯和糾錯能力8.5線性分組碼的譯碼ElectronicsEngineeringDepartment,XXXXXxxXxxx第2頁2024/4/148.1線性分組碼概念(1)線性分組碼的編碼：編碼過程分為兩步：把信息序列按一定長度分成若干信息碼組,每組由k位組成;編碼器按照預定的線性規(guī)則（可由線性方程組規(guī)定），把信息碼組變換成n重（n>k）碼字，其中(n－k)個附加碼元是由信息碼元的線性運算產(chǎn)生的。(2)線性分組碼的碼字數(shù)：信息碼組長k位，有2k個不同的信息碼組，有2k個碼字與它們一一對應。第3頁2024/4/148.1線性分組碼概念(3)術語線性分組碼：通過預定的線性運算將長為k位的信息碼組變換成n重的碼字(n>k)。由2k個信息碼組所編成的2k個碼字集合，稱為線性分組碼。碼矢：一個n重的碼字可以用矢量來表示：C=(cn－1,cn－1,…,c1,c0)(n,k)線性碼：信息位長為k，碼長為n的線性碼。編碼效率/編碼速率/碼率/傳信率：R=k/n。它說明了信道的利用效率，R是衡量碼性能的一個重要參數(shù)。第4頁2024/4/148.2線性分組碼的監(jiān)督矩陣和生成矩陣8.2.1線性分組碼的監(jiān)督矩陣8.2.2線性分組碼的生成矩陣第5頁2024/4/148.2.1線性分組碼的監(jiān)督矩陣(1)一致監(jiān)督方程(2)一致監(jiān)督矩陣(3)一致監(jiān)督矩陣特性8.2線性分組碼的監(jiān)督矩陣和生成矩陣第6頁2024/4/148.2.1線性分組碼的監(jiān)督矩陣(1)一致監(jiān)督方程

構成碼字的方法：編碼是給已知信息碼組按預定規(guī)則添加監(jiān)督碼元，構成碼字。在k個信息碼元之后附加r（r=n－k）個監(jiān)督碼元，使每個監(jiān)督元是其中某些信息元的模2和。8.2線性分組碼的監(jiān)督矩陣和生成矩陣第7頁2024/4/148.2.1線性分組碼的監(jiān)督矩陣(1)一致監(jiān)督方程

舉例：k=3,r=4，構成(7,3)線性分組碼。設碼字為：(c6,c5,c4,c3,c2,c1,c0)c6,c5,c4為信息元，c3,c2,c1,c0為監(jiān)督元，每個碼元取“0”或“1”

監(jiān)督元按下面方程組計算：8.2線性分組碼的監(jiān)督矩陣和生成矩陣第8頁2024/4/148.2.1線性分組碼的監(jiān)督矩陣(1)一致監(jiān)督方程一致監(jiān)督方程/一致校驗方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗方程。為什么叫線性分組碼？由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運算關系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。8.2線性分組碼的監(jiān)督矩陣和生成矩陣第9頁2024/4/14

8.2.1線性分組碼的監(jiān)督矩陣(1)一致監(jiān)督方程信息碼組(101)，即c6=1,c5=0,c4=1代入(8-1)得：c3=0,c2=0,c1=1,c0=1由信息碼組(101)編出的碼字為(1010011)。其它7個碼字如表8.2.1。8.2線性分組碼的監(jiān)督矩陣和生成矩陣第10頁2024/4/14

8.2.1線性分組碼的監(jiān)督矩陣將式(8-2)可寫成：

H

·CT=0T

或

C·HT=0CT、HT、0T分別表示C、H、0的轉(zhuǎn)置矩陣。(2)一致監(jiān)督矩陣為了運算方便，將式(8-1)監(jiān)督方程寫成矩陣形式，得：8.2線性分組碼的監(jiān)督矩陣和生成矩陣第11頁2024/4/148.2.1線性分組碼的監(jiān)督矩陣(2)一致監(jiān)督矩陣系數(shù)矩陣H

的后四列組成一個(4×4)階單位子陣，用

I4表示，H

的其余部分用P表示：8.2線性分組碼的監(jiān)督矩陣和生成矩陣第12頁2024/4/14

8.2.1線性分組碼的監(jiān)督矩陣(2)一致監(jiān)督矩陣推廣到一般情況：對(n,k)線性分組碼，每個碼字中的r（r=n－k）個監(jiān)督元與信息元之間的關系可由下面的線性方程組確定：8.2線性分組碼的監(jiān)督矩陣和生成矩陣第13頁2024/4/14

8.2.1線性分組碼的監(jiān)督矩陣(2)一致監(jiān)督矩陣令上式的系數(shù)矩陣為H，碼字行陣列為C：8.2線性分組碼的監(jiān)督矩陣和生成矩陣(3)一致監(jiān)督矩陣特性對H

各行實行初等變換，將后面r列化為單位子陣，得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣H

的標準形式：后面r列是一單位子陣的監(jiān)督矩陣H。第14頁2024/4/148.2.1線性分組碼的監(jiān)督矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第15頁2024/4/148.2.2線性分組碼的生成矩陣(1)線性碼的一些性質(zhì)(2)線性分組碼的生成矩陣(3)生成矩陣與一致監(jiān)督矩陣的關系(4)對偶碼8.2線性分組碼的監(jiān)督矩陣和生成矩陣第16頁2024/4/14(1)線性碼的一些性質(zhì)

線性碼的封閉性：線性碼任意兩個碼字之和仍是一個碼字。定理8-1：設二元線性分組碼CI(CI表示碼字集合)是由監(jiān)督矩陣H

所定義的，若U

和V

為其中的任意兩個碼字，則U

+V

也是

CI中的一個碼字。8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第17頁2024/4/14(2)線性分組碼的生成矩陣生成矩陣的來由：在由(n,k)線性碼構成的線性空間Vn的

k

維子空間中，一定存在k

個線性獨立的碼字：g1,g2,…,gk。碼

CI中其它任何碼字C都可以表為這k

個碼字的一種線性組合，即：8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第18頁2024/4/14(2)線性分組碼的生成矩陣生成矩陣定義：由于矩陣G生成了(n,k)線性碼，稱矩陣G為

(n,k)線性碼的生成矩陣。8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第19頁2024/4/14(2)線性分組碼的生成矩陣

線性系統(tǒng)分組碼

線性系統(tǒng)分組碼的構成：通過行初等變換，將G化為前k列是單位子陣的標準形式。8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第20頁2024/4/14(2)線性分組碼的生成矩陣

線性系統(tǒng)分組碼

線性系統(tǒng)分組碼定義：用標準生成矩陣Gk×n

編成的碼字，前面k位為信息位，后面r=n－k位為監(jiān)督位，這種信息位在前監(jiān)督位在后的線性分組碼稱為線性系統(tǒng)分組碼。當生成矩陣G

確定之后，(n,k)線性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問題也同樣被解決了。8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第21頁2024/4/14(2)線性分組碼的生成矩陣舉例：(7,4)線性碼的生成矩陣為：8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第22頁2024/4/14(3)生成矩陣與一致監(jiān)督矩陣的關系由于生成矩陣G的每一行都是一個碼字，所以G的每行都滿足：

Hr×n(C1×n)T=(01×r)T，則有：

Hr×n(Gk×n)T=(0k×r)T

或

Gk×n(Hr×n)T=0k×r線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接互換8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第23頁2024/4/14(3)生成矩陣與一致監(jiān)督矩陣的關系舉例：已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為：8.2.2線性分組碼的生成矩陣QQT8.2線性分組碼的監(jiān)督矩陣和生成矩陣第24頁2024/4/14(4)對偶碼

對偶碼：對一個(n,k)線性碼CI，由于

Hr×n(Gk×n)T=(0k×r)T，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構造另一個碼CId，CId是一個

(n,n－k)線性碼，稱碼CId為原碼的對偶碼。

例如：(7,4)線性碼的對偶碼是(7,3)碼：

(7,3)碼的生成矩陣G(7,3)是(7,4)碼監(jiān)督矩陣H(7,4)

8.2.2線性分組碼的生成矩陣8.2線性分組碼的監(jiān)督矩陣和生成矩陣第25頁2024/4/14

(n,k)線性碼的編碼：根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將長為k的信息組變換成長為n(n>k)的碼字。利用監(jiān)督矩陣構造(7,3)線性分組碼的編碼電路

設碼字為：C=(c6c5c4c3c2c1c0)

碼的監(jiān)督矩陣為：8.3線性分組碼的編碼第26頁2024/4/14

利用監(jiān)督矩陣構造(7,3)線性分組碼的編碼電路：根據(jù)上面方程組可直接畫出(7,3)碼的并行編碼和串行編碼電路:8.3線性分組碼的編碼第27頁2024/4/148.4線性分組碼的最小距離、檢錯和糾錯能力(1)漢明距離、漢明重量(2)最小距離與檢、糾錯能力第28頁2024/4/14(1)漢明距離和漢明重量

漢明距離（距離）：在(n,k)線性碼中，兩個碼字U、V

之間對應碼元位上符號取值不同的個數(shù)，稱為碼字U、V

之間的漢明距離。8.4線性分組碼的最小距離、檢錯和糾錯能力第29頁2024/4/14(1)漢明距離和漢明重量

最小距離dmin：在(n,k)線性碼的碼字集合中，任意兩個碼字間距離最小值，叫做碼的最小距離。若C(i)和C(j)

是任意兩個碼字，則碼的最小距離表示為：

碼的最小距離是衡量碼的抗干擾能力（檢、糾錯能力）的重要參數(shù)。碼的最小距離越大，碼的抗干擾能力就越強。8.4線性分組碼的最小距離、檢錯和糾錯能力第30頁2024/4/14(1)漢明距離和漢明重量漢明重量（碼字重量）W：碼字中非0

碼元符號的個數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中含“1”的個數(shù)。最小重量Wmin

：線性分組碼CI中，非0

碼字重量最小值，叫做碼CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}8.4線性分組碼的最小距離、檢錯和糾錯能力第31頁2024/4/14(1)漢明距離和漢明重量

最小距離與最小重量的關系：線性分組碼的最小距離等于它的最小重量。8.4線性分組碼的最小距離、檢錯和糾錯能力第32頁2024/4/14(2)最小距離與檢、糾錯能力檢錯能力：如果一個線性碼能檢出長度≤l個碼元的任何錯誤圖樣，稱碼的檢錯能力為l。糾錯能力：如果線性碼能糾正長度≤t個碼元的任意錯誤圖樣，稱碼的糾錯能力為t。最小距離與檢糾錯能力的關系：線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。8.4線性分組碼的最小距離、檢錯和糾錯能力第33頁2024/4/14(2)最小距離與檢、糾錯能力最小距離與糾錯能力：(n,k)線性碼能糾t個錯誤的充要條件是碼的最小距離為：dmin≥2t+1最小距離與檢錯能力：(n,k)線性碼能夠發(fā)現(xiàn)l個錯誤的充要條件是碼的最小距離為：dmin≥l+1最小距離與檢、糾錯能力：(n,k)線性碼能糾t個錯誤，并能發(fā)現(xiàn)l個錯誤(l>t)的充要條件是碼的最小距離為：dmin≥

t+l+18.4線性分組碼的最小距離、檢錯和糾錯能力第34頁2024/4/148.5線性分組碼的譯碼8.5.1伴隨式和錯誤檢測8.5.2糾錯譯碼第35頁2024/4/148.5.1伴隨式和錯誤檢測(1)如何譯碼？(2)伴隨式(3)伴隨式的計算(4)伴隨式的特性(5)舉例(6)伴隨式計算電路8.5線性分組碼的譯碼第36頁2024/4/148.5.1伴隨式和錯誤檢測(1)如何譯碼？

用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個字R后，校驗H

RT=0T是否成立：若關系成立，則認為R

是一個碼字；否則判為碼字在傳輸中發(fā)生了錯誤；H

R

T的值是否為0

是校驗碼字出錯與否的依據(jù)。(2)伴隨式/監(jiān)督子/校驗子：S=R

HT

或ST=H

RT8.5線性分組碼的譯碼第37頁2024/4/148.5.1伴隨式和錯誤檢測(3)伴隨式的計算

發(fā)送碼字：C=(cn－1,cn－2,…,c0)

信道錯誤圖樣：E=(en－1,en－2,…,e0)

ei=0，表示第i位無錯；

ei=1，表示第i位有錯。i=n－1,n－2,…,08.5線性分組碼的譯碼第38頁2024/4/148.5.1伴隨式和錯誤檢測(3)伴隨式的計算接收字：R=(rn－1,rn－2,…,r0)=C+E=(cn－1+en－1,cn－2+en－2,…,c0+e0)求接收字的伴隨式（接收字用監(jiān)督矩陣進行檢驗）

ST=H

RT=H

(C+E)T=H

CT+H

ET

(8-32)H

CT=0T，所以ST=H

ET設

H=(h1,h2,…,hn)，（hi表示

H的列）。代入式(8-32)得：

ST=h1en－1+h2en－2+…+hn

e08.5線性分組碼的譯碼第39頁2024/4/148.5.1伴隨式和錯誤檢測(4)伴隨式的特性

伴隨式僅與錯誤圖樣有關，而與發(fā)送的具體碼字無關，即伴隨式僅由錯誤圖樣決定；伴隨式是錯誤的判別式：若S

=0，則判為沒有出錯，接收字是一個碼字；若S≠0，則判為有錯。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的。對二元碼，伴隨式是H

陣中與錯誤碼元對應列之和。8.5線性分組碼的譯碼第40頁2024/4/14(5)舉例：(7,3)碼接收字R的伴隨式計算

若接收字中沒有錯誤：

設發(fā)送碼字C=1010011，接收字

R＝1010011，R與C相同：

但接收端譯碼器并不知道就是發(fā)送的碼字

根據(jù)接收字R

計算伴隨式：ST=HRT=0T

因此，譯碼器判接收字無錯8.5.1伴隨式和錯誤檢測8.5線性分組碼的譯碼第41頁2024/4/14(5)舉例：(7,3)碼接收矢量R的伴隨式計算若接收字中有1位錯誤：

發(fā)送碼字C=1010011，接收字R=1110011，伴隨式為：8.5.1伴隨式和錯誤檢測8.5線性分組碼的譯碼第42頁2024/4/14(5)舉例：(7,3)碼接收矢量R的伴隨式計算若接收字中有1位錯誤：發(fā)送碼字C=1010011，接收字R=1110011

(7,3)碼是糾單個錯誤的碼，且ST

等于H

的第二列，因此判定接收字R

的第二位是錯的。

由于接收字R

中錯誤碼元數(shù)與碼的糾錯能力相符，所以譯碼正確。8.5.1伴隨式和錯誤檢測8.5線性分組碼的譯碼第43頁2024/4/148.5.1伴隨式和錯誤檢測(5)舉例：(7,3)碼接收矢量R的伴隨式計算當碼元錯誤多于1個時：發(fā)送碼字C=1010011，接收字R=0011011，伴隨式為：8.5線性分組碼的譯碼第44頁2024/4/148.5.1伴隨式和錯誤檢測(5)舉例：(7,3)碼接收矢量R的伴隨式計算當碼元錯誤多于1個時：發(fā)送碼字C=1010011，接收字R=0011011

由于ST

是第一列和第四列之和，不等于0；但ST與H

陣中任何一列都不相同無法判定錯誤出在哪些位上，只是發(fā)現(xiàn)有錯。8.5線性分組碼的譯碼第45頁2024/4/148.5.1伴隨式和錯誤檢測(6)伴隨式計算電路伴隨式的計算可用電路來實現(xiàn)。(7,3)碼為例：接收字R

=(r6r5r4r3r2r1r0)，伴隨式：8.5線性分組碼的譯碼第46頁2024/4/148.5.1伴隨式和錯誤檢測(6)伴隨式計算電路伴隨式計算電路：8.5線性分組碼的譯碼第47頁2024/4/148.5.2糾錯譯碼(1)最佳譯碼準則（最大似然譯碼）(2)查表譯碼法(3)標準陣列(4)舉例(5)結論8.5線性分組碼的譯碼第48頁2024/4/148.5.2糾錯譯碼(1)最佳譯碼準則（最大似然譯碼）

通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。對于FEC方式，采用糾錯碼后的碼字差錯概率為pwe：

p(C)：發(fā)送碼字C的先驗概率

p(C/R)：后驗概率8.5線性分組碼的譯碼第49頁2024/4/148.5.2糾錯譯碼(1)最佳譯碼準則（最大似然譯碼）若碼字數(shù)為2k，對充分隨機的消息源有

p(C)=1/2k，所以最小化的pwe等價為最小化p(C'≠C/R)，又等價為最大化

p(C'

=C/R)；對于BSC信道：最大化的p(C'

=C/R)等價于最大化的p(R/C)，最大化的

p(R/C)又等價于最小化d(R,C)，所以使差錯概率最小的譯碼是使接收向量R與輸出碼字C'距離最小的譯碼。8.5線性分組碼的譯碼第50頁2024/4/148.5.2糾錯譯碼(2)查表譯碼法

按最小距離譯碼，對有2k個碼字的(n,k)線性碼，為了找到與接收字R

有最小距離的碼字，需將R

分別和2k個碼字比較，以求出最小距離。其中利用“標準陣列”譯碼是最典型的方法。8.5線性分組碼的譯碼第51頁2024/4/148.5.2糾錯譯碼(3)標準陣列①碼字參數(shù)：發(fā)送碼字：取自于2k個碼字集合{C}；接收碼字：可以是2n個n重中任一個矢量。②譯碼方法把2n個n重矢量劃分為2k個互不相交的子集，使得在每個子集中僅含一個碼字；根據(jù)碼字和子集間一一對應關系，若接收矢量Rl落在子集Dl中，就把Rl譯為子集Dl含有的碼字Cl；當接收矢量R

與實際發(fā)送碼字在同一子集中時，譯碼就是正確的。8.5線性分組碼的譯碼第52頁2024/4/148.5.2糾錯譯碼(3)標準陣列③標準陣列構造方法先將2k個碼字排成一行，作為標準陣列的第一行，并將全0碼字C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

個n重中選取一個重量最輕的n重

E2放在全0

碼字C1下面，再將

E2分別和碼字相加，放在對應碼字下面構成陣列第二行；在第二次剩下的n重中，選取重量最輕的n重E3，放在

E2下面，并將

E3分別加到第一行各碼字上，得到第三行；…，繼續(xù)這樣做下去，直到全部n重用完為止。得到表8-2所示的給定(n,k)線性碼的標準陣列。8.5線性分組碼的譯碼第53頁2024/4/148.5.2糾錯譯碼(3)標準陣列③標準陣列構造方法8.5線性分組碼的譯碼第54頁2024/4/148.5.2糾錯譯碼(3)標準陣列④標準陣列的特性定理8-9：在標準陣列的同一行中沒有相同的矢量，而且2n個n重中任一個n重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。定理8-10：（線性碼糾錯極限定理）：二元(n,k)線性碼能糾2n－k個錯誤圖樣。這2n－k個可糾的錯誤圖樣，包括0

矢量在內(nèi)，即把無錯的情況也看成一個可糾的錯誤圖樣。這2n－k個陪集首稱為可糾正的錯誤圖樣。8.5線性分組碼的譯碼第55頁2024/4/148.5.2糾錯譯碼(3)標準陣列④標準陣列的特性標準陣列譯碼=最小距離譯碼=最佳譯碼標準陣