一般概念一致監(jiān)督方程和一致監(jiān)督矩陣線性分組碼ppt課件

1、5.1 普通概念5.2 一致監(jiān)視方程和一致監(jiān)視矩陣5.3 線性分組碼的生成矩陣5.4 線性分組碼的編碼5.5 線性分組碼的最小間隔、檢錯和糾錯才干5.6 線性分組碼的譯碼5.7 線性分組碼的性能5.8 漢明碼5.9 由知碼構(gòu)造新碼的方法5.10 線性分組碼的碼限第5章 線性分組碼l線性分組碼的編碼：線性分組碼的編碼過程分為兩步：線性分組碼的編碼：線性分組碼的編碼過程分為兩步：l把信息序列按一定長度分成假設(shè)干信息碼組，每組由把信息序列按一定長度分成假設(shè)干信息碼組，每組由 k 位組位組成；成；l編碼器按照預(yù)定的線性規(guī)那么編碼器按照預(yù)定的線性規(guī)那么(可由線性方程組規(guī)定可由線性方程組規(guī)定)，把信，把信

2、息碼組變換成息碼組變換成 n 重重 (nk) 碼字，其中碼字，其中 (nk) 個附加碼元是由個附加碼元是由信息碼元的線性運算產(chǎn)生的。信息碼元的線性運算產(chǎn)生的。l信息碼組長信息碼組長 k 位，有位，有 2k 個不同的信息碼組，那么有個不同的信息碼組，那么有 2k 個碼個碼字與它們一一對應(yīng)。字與它們一一對應(yīng)。5.1 普通概念l名詞解釋l線性分組碼：經(jīng)過預(yù)定的線性運算將長為 k 位的信息碼組變換成 n 重的碼字 (nk)。由 2k 個信息碼組所編成的 2k個碼字集合，稱為線性分組碼。l碼矢：一個 n 重的碼字可以用矢量來表示lC=(Cn1,Cn1,C1,C0 )l 所以碼字又稱為碼矢。l(n,k)

3、線性碼：信息位長為 k，碼長為 n 的線性碼。l編碼效率/編碼速率/碼率/傳信率：R=k /n。它闡明了信道的利用效率，R是衡量碼性能的一個重要參數(shù)。5.1 普通概念(1) 一致監(jiān)視方程編碼就是給知信息碼組按預(yù)定規(guī)那么添加監(jiān)視碼元，以構(gòu)成碼字。在 k 個信息碼元之后附加 r(r=nk) 個監(jiān)視碼元，使每個監(jiān)視元是其中某些信息元的模2和。舉例：k=3, r=4，構(gòu)成 (7,3) 線性分組碼。設(shè)碼字為(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)視元，每個碼元取“0或“1監(jiān)視元可按下面方程組計算5.2 一致監(jiān)視方程和一致監(jiān)視矩陣) 1 . 5(45

4、05614562463CCCCCCCCCCCCCl一致監(jiān)視方程一致監(jiān)視方程/一致校驗方程：確定信息元得到監(jiān)視元一致校驗方程：確定信息元得到監(jiān)視元規(guī)那么的一組方程稱為監(jiān)視方程規(guī)那么的一組方程稱為監(jiān)視方程/校驗方程。由于一切校驗方程。由于一切碼字都按同一規(guī)那么確定，又稱為一致監(jiān)視方程碼字都按同一規(guī)那么確定，又稱為一致監(jiān)視方程/一致一致校驗方程。校驗方程。l由于一致監(jiān)視方程是線性的，即監(jiān)視元和信息元之間是由于一致監(jiān)視方程是線性的，即監(jiān)視元和信息元之間是線性運算關(guān)系，所以由線性監(jiān)視方程所確定的分組碼是線性運算關(guān)系，所以由線性監(jiān)視方程所確定的分組碼是線性分組碼。線性分組碼。5.2 一致監(jiān)視方程和一致監(jiān)視

5、矩陣(2) 舉例信息碼組 (101)，即C6=1, C5=0, C4=1代入 (5.1) 得： C3=0, C2=0, C1=1, C0=1由信息碼組 (101) 編出的碼字為 (1010011)。其它7個碼字如表5.1。6.2 一致監(jiān)視方程和一致監(jiān)視矩陣) 1 . 5(4505614562463CCCCCCCCCCCCC00000000000000000000451562456346CCCCCCCCCCCCC(3) 一致監(jiān)視矩陣為了運算方便，將式(5.1)監(jiān)視方程寫成矩陣方式，得式(5.2)可寫成 H CT=0T或 C HT=0 CT、HT、0T分別表示C、H、0的轉(zhuǎn)置矩陣。)3 . 5(1

6、000110010001100101110001101H00000C)2 . 5(0000100011001000110010111000110101234560123456CCCCCCCCCCCCCC令5.2 一致監(jiān)視方程和一致監(jiān)視矩陣l系數(shù)矩陣 H 的后四列組成一個 (44) 階單位子陣，用 I4 表示，H 的其他部分用 P 表示)5 . 5(IPH1000010000100001I110011111101P43437434),(所以5.2 一致監(jiān)視方程和一致監(jiān)視矩陣l推行到普通情況：對 (n,k) 線性分組碼，每個碼字中的 r(r=nk) 個監(jiān)視元與信息元之間的關(guān)系可由下面的線性方程組確

7、定5.2 一致監(jiān)視方程和一致監(jiān)視矩陣)6 . 5(000022110222212101212111ChChChChChChChChChrnnrnrnnnnnnl令上式的系數(shù)矩陣為 H，碼字行陣列為 C5.2 一致監(jiān)視方程和一致監(jiān)視矩陣矩陣，簡稱監(jiān)督矩陣。線性分組碼的一致監(jiān)督為稱或可寫成式),(H)8 . 5(0HC0CH)6 . 5(C)7 . 5(H11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnr(4) 一致監(jiān)視矩陣特性對H 各行實行初等變換，將后面 r 列化為單位子陣，于是得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)視矩陣

8、H 的規(guī)范方式：后面 r 列是一單位子陣的監(jiān)視矩陣H。H 陣的每一行都代表一個監(jiān)視方程，它表示與該行中“1相對應(yīng)的碼元的模2和為0。5.2 一致監(jiān)視方程和一致監(jiān)視矩陣)9 . 5(100010001H212222111211rnrrkknrppppppppplH 的規(guī)范方式還闡明了相應(yīng)的監(jiān)視元是由哪些信息元決議的。例如 (7,3) 碼的H 陣的第一行為 (1011000)，闡明此碼的第一個監(jiān)視元等于第一個和第三個信息元的模2和，依此類推。 lH 陣的 r 行代表了 r 個監(jiān)視方程，也表示由H 所確定的碼字有 r 個監(jiān)視元。l為了得到確定的碼，r 個監(jiān)視方程或H 陣的r 行必需是線性獨立的，這要

9、求H 陣的秩為 r。l假設(shè)把H 陣化成規(guī)范方式，只需檢查單位子陣的秩，就能方便地確定H 陣本身的秩。5.2 一致監(jiān)視方程和一致監(jiān)視矩陣(1) 線性碼的封鎖性線性碼的封鎖性：線性碼恣意兩個碼字之和仍是一個碼字。定理5.1：設(shè)二元線性分組碼 CI (CI表示碼字集合) 是由監(jiān)視矩陣H所定義的，假設(shè) U 和 V 為其中的恣意兩個碼字，那么 U+V 也是 CI中的一個碼字。證明：由于 U 和 V 是碼 CI 中的兩個碼字，故有HUT=0T，HVT=0T 那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T 即 U+V 滿足監(jiān)視方程，所以 U+V 一定是一個碼字。一個長為 n 的二元序列可以看作

10、是GF(2)(二元域)上的 n 維線性空間中的一點。長為 n 的一切 2n 個矢量集合構(gòu)成了GF(2)上的 n 維線性空間Vn。把線性碼放入線性空間中進(jìn)展研討，將使許多問題簡化而比較容易處理。(n,k) 線性碼是 n 維線性空間Vn中的一個 k 維子空間 Vk。5.3 線性分組碼的生成矩陣(2) 線性分組碼的生成矩陣在由 (n,k) 線性碼構(gòu)成的線性空間 Vn 的 k 維子空間中，一定存在 k 個線性獨立的碼字：g1,g2, gk,。碼 CI 中其它任何碼字C都可以表為這 k 個碼字的一種線性組合，即5.3 線性分組碼的生成矩陣階矩陣。是一個是待編碼的信息組。寫成矩陣形式得）（nkmmmmmm

11、kimmmmkknkkkkknikkkGm)11. 5(GmgggC1, 1 , 0),2(GF10. 5gggC021121021102211G中每一行 gi=(gi1,gi2, gin ) 都是一個碼字；對每一個信息組m，由矩陣G都可以求得 (n,k) 線性碼對應(yīng)的碼字。生成矩陣：由于矩陣 G 生成了 (n,k) 線性碼，稱矩陣 G 為 (n,k) 線性碼的生成矩陣。(n,k) 線性碼的每一個碼字都是生成矩陣 G 的行矢量的線性組合，所以它的 2k 個碼字構(gòu)成了由 G 的行張成的 n 維空間的一個 k 維子空間 Vk。5.3 線性分組碼的生成矩陣)11. 5(gggG21222211121

12、121knkknnknkgggggggggl線性系統(tǒng)分組碼l 經(jīng)過行初等變換，將 G 化為前 k 列是單位子陣的規(guī)范方式l 5.3 線性分組碼的生成矩陣)13. 5(, 2 , 1, 2 , 1G),(),(C)12. 5(QI100010001G02211)(0210211)(21)(22221)(11211knjqmqmqmCkimC,mmmCCCqqqqqqqqqkjjkjkjknikinnkkknnnrkkknkkkknknnk得將上式代入l線性系統(tǒng)分組碼：用規(guī)范生成矩陣 Gkn 編成的碼字，前面 k 位為信息數(shù)字，后面 r=nk 位為校驗字，這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼稱

13、為線性系統(tǒng)分組碼。l當(dāng)生成矩陣 G 確定之后，(n,k) 線性碼也就完全被確定了，只需找到碼的生成矩陣，編碼問題也同樣被處理了。5.3 線性分組碼的生成矩陣(3) 舉例 (7,4) 線性碼的生成矩陣為5.3 線性分組碼的生成矩陣)1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174GmCmG，則若(4) 生成矩陣與一致監(jiān)視矩陣的關(guān)系由于生成矩陣G的每一行都是一個碼字，所以G 的每行都滿足HrnCTn1=0Tr1，那么有HrnGTnk=0Trk 或 GknHTnr=0kr線性系統(tǒng)碼

14、的監(jiān)視矩陣 H 和生成矩陣 G 之間可以直接互換。5.3 線性分組碼的生成矩陣)14. 5(I)Q(HQIGP)Q()P(Q0Q)P(I)P(QIIPQIHGIPHQIGrTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrkkTrkrrkkTSSrkrSrkkS或所以，l舉例l 知(7,4)線性系統(tǒng)碼的監(jiān)視矩陣為5.3 線性分組碼的生成矩陣1101000011010011100101010001100101101011100010111)4,7()4,7(GH陣可直接寫出它的生成矩(5) 對偶碼對偶碼：對一個(n,k)線性碼 CI，由于HrnGTnk=0Trk，假設(shè)以G 作監(jiān)視矩陣，

15、而以H 作生成矩陣，可構(gòu)造另一個碼CId，碼CId是一個(n,nk)線性碼，稱碼CId為原碼的對偶碼。例如： (7,4)線性碼的對偶碼是(7,3)碼：(7,3)碼的監(jiān)視矩陣H(7,3)是(7,4)碼生成矩陣G(7,4) 5.3 線性分組碼的生成矩陣10001100100011001011100011011101000011010011100101010001)4,7()3 ,7(化成標(biāo)準(zhǔn)形式GHl(7,3) 碼的生成矩陣 G(7,3) 是 (7,4) 碼監(jiān)視矩陣 H(7,4) 5.3 線性分組碼的生成矩陣101110011100100111001100101101011100010111) 4

16、 , 7() 3 , 7(化成標(biāo)準(zhǔn)形式HGl(n,k) 線性碼的編碼就是根據(jù)線性碼的監(jiān)視矩陣或生成矩陣將長為 k 的信息組變換生長為 n(nk) 的碼字。l利用監(jiān)視矩陣構(gòu)造 (7,3) 線性分組碼的編碼電路：l設(shè)碼字矢量為C=(C6 C5C4C3C2C1C0)l碼的監(jiān)視矩陣為5.4 線性分組碼的編碼4505614562463)3 ,7(1000110010001100101110001101CCCCCCCCCCCCCTT得由0HCHl根據(jù)方程組可直接畫出 (7,3) 碼的并行編碼電路行串行編碼電路，如圖5.2。5.4 線性分組碼的編碼(1) 漢明間隔、漢明分量和漢明球漢明間隔/間隔：在 (n,

17、k)線性碼中，兩個碼字 U、V 之間對應(yīng)碼元位上符號取值不同的個數(shù)，稱為碼字 U、V 之間的漢明間隔。例如：(7,3) 碼的兩個碼字 U=0011101,V=0100111，它們之間第2、3、4和6位不同。因此，碼字 U 和 V 的間隔為4。線性分組碼的一個碼字對應(yīng)于 n 維線性空間中的一點，碼字間的間隔即為空間中兩對應(yīng)點的間隔。因此，碼字間的間隔滿足普通間隔公理：10)(),(niiivudVU5.5 線性分組碼的最小間隔、檢錯和糾錯才干三角不等式對稱性非負(fù)性),(),(),(),(),(0),(WUWVVUUVVUVUddddddl最小間隔/dmin：在 (n,k) 線性碼的碼字集合中，恣

18、意兩個碼字間間隔最小值，叫做碼的最小間隔。假設(shè)C(i)和C(j) 是恣意兩個碼字，那么碼的最小間隔表示為l碼的最小間隔是衡量碼的抗干擾才干檢、糾錯才干的重要參數(shù)。碼的最小間隔越大，碼的抗干擾才干就越強。l漢明球：以碼字C為中心，半徑為 t 的漢明球是與 C 的漢明間隔 t 的向量全體 SC(t)l 恣意兩個漢明球不相交最大程度取決于恣意兩個碼字之間的最小漢明間隔dmin。12 , 1 , 0,),(min)()(minkjijijiddCC5.5 線性分組碼的最小間隔、檢錯和糾錯才干tdt),()(RCRSC 5.5 線性分組碼的最小間隔、檢錯和糾錯才干l漢明分量/碼字分量/W：碼字中非0碼元

19、符號的個數(shù)，稱為該碼字的漢明分量。l在二元線性碼中，碼字分量就是碼字中含“1的個數(shù)。l最小分量/Wmin ：線性分組碼CI中，非0碼字分量最小值，叫做碼CI的最小分量：lWmin =minW(V),VCI ,V0l最小間隔與最小分量的關(guān)系：線性分組碼的最小間隔等于它的最小分量。l 證明：設(shè)線性碼CI，且UCI, VCI，又設(shè)UV=Z，由線性碼的封鎖性知，ZCI 。因此，d(U,V)=W(Z)，由此可推知，線性分組碼的最小間隔必等于非0碼字的最小分量。5.5 線性分組碼的最小間隔、檢錯和糾錯才干(2) 最小間隔與檢、糾錯才干普通地說，線性碼的最小間隔越大，意味著恣意碼字間的差別越大，那么碼的檢、

20、糾錯才干越強。檢錯才干：假設(shè)一個線性碼能檢出長度l 個碼元的任何錯誤圖樣，稱碼的檢錯才干為 l。糾錯才干：假設(shè)線性碼能糾正長度t 個碼元的恣意錯誤圖樣，稱碼的糾錯才干為 t。5.5 線性分組碼的最小間隔、檢錯和糾錯才干l最小間隔與糾錯才干：(n,k) 線性碼能糾 t 個錯誤的充要條件是碼的最小間隔為l 證明：l 設(shè)：發(fā)送的碼字為V；接納的碼字為R；U為恣意其它碼字；l 那么：矢量V、R、U間滿足間隔的三角不等式， l d(R,V)+d(R,U)d(U,V) (5.16)l 設(shè)：信道干擾使碼字中碼元發(fā)生錯誤的實踐個數(shù)為 t，且ttl d(R,V)tt (5.17)l 由于d(U,V)dmin=2

21、t+1，代入式(5.16)得l d(R,U) d(U,V)d(R,V)= 2t+1tt (5.18)5.5 線性分組碼的最小間隔、檢錯和糾錯才干 47 . 4)15. 5(2112minmin的最大整數(shù)，例表示取實數(shù)其中或XXdttd 上式闡明：假設(shè)接納字 R 中錯誤個數(shù) tt，那么接納字 R 和發(fā)送字 V 間間隔t ，而與其它任何碼字間間隔都大于 t，按最小間隔譯碼把R譯為V。此時譯碼正確，碼字中的錯誤被糾正。 幾何意義：5.5 線性分組碼的最小間隔、檢錯和糾錯才干l最小間隔與檢錯才干：(n,k) 線性碼可以發(fā)現(xiàn) l 個錯誤的充要條件是碼的最小間隔為l dmin=l+1 或 l=dmin1

22、(5.19)l 證明：l 設(shè)：發(fā)送的碼字為 V；接納的碼字為 R；U 為恣意其它碼字；l 那么：矢量V、R、U間滿足間隔的三角不等式， l d(R,V)+d(R,U)d(U,V) (5.20)l 設(shè)：信道干擾使碼字中碼元發(fā)生錯誤的實踐個數(shù)為 l，且lll d(R,V)ll (5.21)l 由于d(U,V)dmin=l+1，代入式(6.2.20)得l d(R,U) d(U,V)d(R,V)=l+1l0 (5.22)5.5 線性分組碼的最小間隔、檢錯和糾錯才干 上式闡明：由于接納字 R 與其它任何碼字 U 的間隔都大于0，那么闡明接納字 R 不會因發(fā)生 l 個錯誤變?yōu)槠渌a字，因此必能發(fā)現(xiàn)錯誤。

23、幾何意義：5.5 線性分組碼的最小間隔、檢錯和糾錯才干l最小間隔與檢、糾錯才干：(n,k) 線性碼能糾 t 個錯誤，并能發(fā)現(xiàn) l 個錯誤 (lt) 的充要條件是碼的最小間隔為l dmin=t+l+1 或 t+l=dmin1 (5.23)l 證明：由于dmin2t+1，根據(jù)最小間隔與糾錯才干定理，該碼可糾 t 個錯誤。l 由于dminl+1，根據(jù)最小間隔與檢錯才干定理，該碼有檢 l 個錯誤的才干。l 糾錯和檢錯不會發(fā)生混淆：設(shè)發(fā)送碼字為 V，接納字為 R，實踐錯誤數(shù)為 l，且 tt+1t (5.24)l 因此不會把 R 誤糾為 U。5.5 線性分組碼的最小間隔、檢錯和糾錯才干 幾何意義：5.5

24、線性分組碼的最小間隔、檢錯和糾錯才干5.5 線性分組碼的最小間隔、檢錯和糾錯才干l當(dāng) (n,k) 線性碼的最小間隔 dmin 給定后，可按實踐需求靈敏安排糾錯的數(shù)目。例如，對 dmin=8 的碼，可用來糾3檢4錯，或糾2檢5錯，或糾1檢6錯，或者只用于檢7個錯誤。5.5 線性分組碼的最小間隔、檢錯和糾錯才干(3) 線性碼的最小間隔與監(jiān)視矩陣的關(guān)系定理5.2：設(shè) H 為 (n,k) 線性碼的一致監(jiān)視矩陣，假設(shè) H 中恣意 S 列線性無關(guān)，而 H 中存在 (S+1) 列線性相關(guān)，那么碼的最小間隔為 (S+1)。矩陣 H 的秩為S定理5.3：假設(shè)碼的最小間隔為 (S+1)，那么該碼的監(jiān)視矩陣的恣意

25、S 列線性無關(guān)，而必存在有相關(guān)的 (S+1)列。定理5.4：在二元線性碼的監(jiān)視矩陣 H 中，假設(shè)任一列都不是全“0，且任兩列都不相等，那么該碼能糾一個錯誤。5.5 線性分組碼的最小間隔、檢錯和糾錯才干(1) 伴隨式和錯誤檢測 用監(jiān)視矩陣編碼，也用監(jiān)視矩陣譯碼：接納到一個接納字 R 后，校驗 HRT=0T 能否成立：假設(shè)關(guān)系成立，那么以為 R 是一個碼字；否那么判為碼字在傳輸中發(fā)生了錯誤；HRT的值能否為0是校驗碼字出錯與否的根據(jù)。 伴隨式/監(jiān)視子/校驗子：S=RHT或ST=HRT。 如何糾錯？設(shè)發(fā)送碼矢 C=(Cn1,Cn2,C0)信道錯誤圖樣為 E=(En1,En2,E0) ，其中Ei=0，

26、表示第i位無錯；Ei=1，表示第i位有錯。i=n1,n2,0。5.6 線性分組碼的譯碼l接納字 R 為lR=(Rn1,Rn2,R0)=C+El =(Cn1+En1,Cn2+En2,C0 +E0)l求接納字的伴隨式接納字用監(jiān)視矩陣進(jìn)展檢驗l ST=HRT=H(C+E)T=HCT+HET (5.25)l由于HCT=0T，所以 ST=HETl設(shè)H=(h1,h2,hn)，其中hi表示H的列。代入式(5.25)得到5.6 線性分組碼的譯碼02211EEEnnnThhhS 總結(jié)伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的詳細(xì)碼字無關(guān)，即伴隨式僅由錯誤圖樣決議；伴隨式是錯誤的判別式：假設(shè)S=0，那么判為沒有出錯，接納字是一個碼字；假設(shè)S0，那么判為有錯。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對二元碼，伴隨式是H 陣中與錯誤碼元對應(yīng)列之和。5.6 線性分組碼的譯碼 舉例： (7,3)碼接納矢量 R 的伴隨式計算設(shè)發(fā)送碼矢C=1010011，接納碼字R1010011，R與C一樣。5.6 線性分組碼的譯碼無錯。因此，譯碼器判接收字代入得和計算伴隨式，把根據(jù)接收字道就是發(fā)送的碼字，但接收端譯碼器并不知TTT0HRSRHRH1000110010001100101110001101l假設(shè)接納字中有一位錯