信息論與編碼原理-第8章-線性分組碼

1、信息論與編碼原理（第八章）線性分組碼8/10/20221Department of Electronics and Information, NCUT Song Peng 第8章 線性分組碼8.1 一般概念8.2 一致監(jiān)督方程和一致監(jiān)督矩陣8.3 線性分組碼的生成矩陣8.4 線性分組碼的編碼8.5 線性分組碼的最小距離、檢錯和糾錯能力8.6 線性分組碼的譯碼8.7 線性分組碼的性能8.8 漢明碼8.9 由已知碼構(gòu)造新碼的方法8.10 GSM 的信道編碼總體方案8.11 線性分組碼的碼限8/10/20222Department of Electronics and Information, NC

2、UT Song Peng 8.1 一般概念(1) 線性分組碼的編碼：編碼過程分為兩步：把信息序列按一定長度分成若干信息碼組, 每組由 k 位組成;編碼器按照預(yù)定的線性規(guī)則（可由線性方程組規(guī)定），把信息碼組變換成 n 重（nk）碼字，其中 (nk) 個附加碼元是由信息碼元的線性運(yùn)算產(chǎn)生的。(2) 線性分組碼的碼字?jǐn)?shù)：信息碼組長 k 位，有 2k 個不同的信息碼組，有 2k 個碼字與它們一一對應(yīng)。8/10/20223Department of Electronics and Information, NCUT Song Peng 8.1 一般概念(3) 術(shù)語線性分組碼：通過預(yù)定的線性運(yùn)算將長為 k

3、 位的信息碼組變換成 n 重的碼字 (nk)。由 2k 個信息碼組所編成的 2k個碼字集合，稱為線性分組碼。碼矢：一個 n 重的碼字可以用矢量來表示：C=(cn1,cn1,c1,c0 )(n,k) 線性碼：信息位長為 k，碼長為 n 的線性碼。編碼效率/編碼速率/碼率/傳信率：R=k /n。它說明了信道的利用效率，R 是衡量碼性能的一個重要參數(shù)。返回目錄8/10/20224Department of Electronics and Information, NCUT Song Peng8.2 一致監(jiān)督方程和一致監(jiān)督矩陣(1) 一致監(jiān)督方程(2) 舉 例(3) 一致監(jiān)督矩陣(4) 一致監(jiān)督矩陣特

4、性8/10/20225Department of Electronics and Information, NCUT Song Peng 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣(1) 一致監(jiān)督方程構(gòu)成碼字的方法：編碼是給已知信息碼組按預(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)督元按下面方程組計(jì)算：8/10/20226Dep

5、artment of Electronics and Information, NCUT Song Peng 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣(1) 一致監(jiān)督方程一致監(jiān)督方程/一致校驗(yàn)方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗(yàn)方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗(yàn)方程。為什么叫線性分組碼？由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運(yùn)算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。返回目錄8/10/20227Department of Electronics and Information, NCUT Song Peng 8.2 一致監(jiān)

6、督方程和一致監(jiān)督矩陣(2) 舉例信息碼組 (101)，即c6=1, c5=0, c4=1代入 (7.2.1) 得： c3=0, c2=0, c1=1, c0=1由信息碼組 (101) 編出的碼字為 (1010011)。其它 7 個碼字如表8.2.1。返回目錄8/10/20228Department of Electronics and Information, NCUT Song Peng 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣(3) 一致監(jiān)督矩陣為了運(yùn)算方便，將式(7.2.1)監(jiān)督方程寫成矩陣形式，得：將式(8.2.2)可寫成： H CT=0T 或 C HT=0 CT、HT、0T 分別表示 C、

7、H、0 的轉(zhuǎn)置矩陣。8/10/20229Department of Electronics and Information, NCUT Song Peng 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣(3) 一致監(jiān)督矩陣系數(shù)矩陣 H 的后四列組成一個 (44) 階單位子陣，用 I4 表示，H 的其余部分用 P 表示：8/10/202210Department of Electronics and Information, NCUT Song Peng 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣(3) 一致監(jiān)督矩陣推廣到一般情況：對 (n,k) 線性分組碼，每個碼字中的 r(r=nk) 個監(jiān)督元與信息元之間的關(guān)系

8、可由下面的線性方程組確定：返回8/10/202211Department of Electronics and Information, NCUT Song Peng 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣(3) 一致監(jiān)督矩陣令上式的系數(shù)矩陣為 H，碼字行陣列為 C ：返回目錄8/10/202212Department of Electronics and Information, NCUT Song Peng(4) 一致監(jiān)督矩陣特性對 H 各行實(shí)行初等變換，將后面 r 列化為單位子陣，得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣 H 的標(biāo)準(zhǔn)形式：后面 r 列是一單位子陣的監(jiān)督矩陣 H。

9、 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣8/10/202213Department of Electronics and Information, NCUT Song Peng(4) 一致監(jiān)督矩陣特性 H 標(biāo)準(zhǔn)形式的特性 H 陣的每一行都代表一個監(jiān)督方程，它表示與該行中“1”相對應(yīng)的碼元的模 2 和為 0。 H 的標(biāo)準(zhǔn)形式表明了相應(yīng)的監(jiān)督元是由哪些信息元決定的。例如 (7,3) 碼的 H 陣的第一行為 (1011000)，說明第一個監(jiān)督元等于第一個和第三個信息元的模 2 和，依此類推。 H 陣的 r 行代表了 r 個監(jiān)督方程，由 H 所確定的碼字有 r 個監(jiān)督元。 為了得到確定的碼，r 個監(jiān)督方程

10、（或 H 陣的 r 行）必須是線性獨(dú)立的，這要求 H 陣的秩為 r。 若把 H 陣化成標(biāo)準(zhǔn)形式，只要檢查單位子陣的秩，就能方便地確定 H 陣本身的秩。 8.2 一致監(jiān)督方程和一致監(jiān)督矩陣參見方程返回目錄8/10/202214Department of Electronics and Information, NCUT Song Peng 8.3 線性分組碼的生成矩陣 (1) 線性碼的封閉性 (2) 線性分組碼的生成矩陣(3) 生成矩陣與一致監(jiān)督矩陣的關(guān)系 (4) 對偶碼8/10/202215Department of Electronics and Information, NCUT Song

11、 Peng(1) 線性碼的封閉性 線性碼的封閉性：線性碼任意兩個碼字之和仍是一個碼字。 定理7.3.1：設(shè)二元線性分組碼 CI (CI 表示碼字集合) 是由監(jiān)督矩陣H 所定義的，若 U 和 V 為其中的任意兩個碼字，則 U +V 也是 CI 中的一個碼字. 證明：由于 U 和 V 是碼 CI 中的兩個碼字，故有：HU T=0T HV T=0T ，那么 H(U+V)T=H(U T+V T)=HU T+HV T=0T 即 U+V 滿足監(jiān)督方程，所以 U+V 一定是一個碼字。 一個長為 n 的二元序列可以看作是 GF(2) (二元域) 上的 n 維線性空間中的一點(diǎn)。所有 2n 個矢量集合構(gòu)成了GF(

12、2)上的 n 維線性空間 Vn。把線性碼放入線性空間中進(jìn)行研究，將使許多問題簡化而比較容易解決。(n,k) 線性碼是 n 維線性空間 Vn 中的一個 k 維子空間 Vk。8.3 線性分組碼的生成矩陣返回目錄8/10/202216Department of Electronics and Information, NCUT Song Peng(2) 線性分組碼的生成矩陣生成矩陣的來由：在由 (n,k) 線性碼構(gòu)成的線性空間 Vn 的 k 維子空間中，一定存在 k 個線性獨(dú)立的碼字：g1,g2, gk。碼 CI 中其它任何碼字 C 都可以表為這 k 個碼字的一種線性組合，即：8.3 線性分組碼的生

13、成矩陣8/10/202217Department of Electronics and Information, NCUT Song Peng(2) 線性分組碼的生成矩陣生成矩陣定義：由于矩陣 G 生成了 (n,k) 線性碼，稱矩陣 G 為 (n,k) 線性碼的生成矩陣。8.3 線性分組碼的生成矩陣8/10/202218Department of Electronics and Information, NCUT Song Peng(2) 線性分組碼的生成矩陣 生成矩陣G 的特性 G 中每一行 gi=(gi1,gi2, gin ) 都是一個碼字； 對每一個信息組 m，由矩陣 G 都可以求得 (

14、n,k) 線性碼對應(yīng)的碼字。 (n,k) 線性碼的每一個碼字都是生成矩陣 G 的行矢量的線性組合，所以它的 2k 個碼字構(gòu)成了由 G 的行張成的 n 維空間的一個 k 維子空間 Vk。8.3 線性分組碼的生成矩陣8/10/202219Department of Electronics and Information, NCUT Song Peng(2) 線性分組碼的生成矩陣 線性系統(tǒng)分組碼 線性系統(tǒng)分組碼的構(gòu)成：通過行初等變換，將 G 化為前 k 列是單位子陣的標(biāo)準(zhǔn)形式。8.3 線性分組碼的生成矩陣8/10/202220Department of Electronics and Informa

15、tion, NCUT Song Peng(2) 線性分組碼的生成矩陣 線性系統(tǒng)分組碼 線性系統(tǒng)分組碼定義：用標(biāo)準(zhǔn)生成矩陣 Gkn 編成的碼字，前面 k 位為信息位，后面 r=nk 位為校驗(yàn)位，這種信息位在前校驗(yàn)位在后的線性分組碼稱為線性系統(tǒng)分組碼。 當(dāng)生成矩陣 G 確定之后，(n,k) 線性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問題也同樣被解決了。8.3 線性分組碼的生成矩陣8/10/202221Department of Electronics and Information, NCUT Song Peng(2) 線性分組碼的生成矩陣舉例：(7,4) 線性碼的生成矩陣為：8.3 線性

16、分組碼的生成矩陣返回目錄8/10/202222Department of Electronics and Information, NCUT Song Peng(3) 生成矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣 G 的每一行都是一個碼字，所以 G 的每行都滿足：Hrn(C1n)T=(01r)T，則有：Hrn(Gkn)T=(0kr)T 或 Gkn(Hrn)T=0kr線性系統(tǒng)碼的監(jiān)督矩陣 H 和生成矩陣 G 之間可以直接互換。8.3 線性分組碼的生成矩陣8/10/202223Department of Electronics and Information, NCUT Song Peng(3) 生成

17、矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣 G 的每一行都是一個碼字，所以 G 的每行都滿足：Hrn(C1n)T=(01r)T，則有：Hrn(Gkn)T=(0kr)T 或 Gkn(Hrn)T=0kr線性系統(tǒng)碼的監(jiān)督矩陣 H 和生成矩陣 G 之間可以直接互換。8.3 線性分組碼的生成矩陣8/10/202224Department of Electronics and Information, NCUT Song Peng(3) 生成矩陣與一致監(jiān)督矩陣的關(guān)系舉例： 已知 (7,4) 線性系統(tǒng)碼的監(jiān)督矩陣為：8.3 線性分組碼的生成矩陣QQT返回目錄8/10/202225Department of Ele

18、ctronics and Information, NCUT Song Peng(4) 對偶碼 對偶碼：對一個 (n,k) 線性碼CI，由于 Hrn(Gkn)T=(0kr)T，如果以G 作監(jiān)督矩陣，而以 H 作生成矩陣，可構(gòu)造另一個碼 CId，CId是一個 (n,nk) 線性碼，稱碼 CId 為原碼的對偶碼. 例如： (7,4) 線性碼的對偶碼是 (7,3) 碼： (7,3) 碼的生成矩陣 G(7,3) 是 (7,4) 碼監(jiān)督矩陣 H(7,4) 8.3 線性分組碼的生成矩陣返回目錄8/10/202226Department of Electronics and Information, NCU

19、T Song Peng (n,k) 線性碼的編碼：根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將長為 k 的信息組變換成長為 n(nk) 的碼字。 利用監(jiān)督矩陣構(gòu)造 (7,3) 線性分組碼的編碼電路 設(shè)碼字為：C=(c6c5c4c3c2c1c0) 碼的監(jiān)督矩陣為：8.4 線性分組碼的編碼8/10/202227Department of Electronics and Information, NCUT Song Peng 利用監(jiān)督矩陣構(gòu)造 (7,3) 線性分組碼的編碼電路： 根據(jù)上面方程組可直接畫出 (7,3) 碼的并行編碼電路和串行編碼電路:8.4 線性分組碼的編碼返回目錄8/10/202228Depar

20、tment of Electronics and Information, NCUT Song Peng8.5 線性分組碼的最小距離、檢錯和糾錯能力(1) 漢明距離、漢明重量和漢明球 (2) 最小距離與檢、糾錯能力 (3) 線性碼的最小距離與監(jiān)督矩陣的關(guān)系8/10/202229Department of Electronics and Information, NCUT Song Peng(1) 漢明距離、漢明重量和漢明球 漢明距離（距離）：在 (n,k) 線性碼中，兩個碼字 U、V 之間對應(yīng)碼元位上符號取值不同的個數(shù)，稱為碼字 U、V 之間的漢明距離。 線性分組碼的一個碼字對應(yīng)于 n 維線性

21、空間中的一點(diǎn)，碼字間的距離即為空間中兩對應(yīng)點(diǎn)的距離。因此，碼字間的距離滿足一般距離公理：8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202230Department of Electronics and Information, NCUT Song Peng(1) 漢明距離、漢明重量和漢明球 最小距離 dmin：在 (n,k) 線性碼的碼字集合中，任意兩個碼字間距離最小值，叫做碼的最小距離。若 C(i) 和 C(j) 是任意兩個碼字，則碼的最小距離表示為： 碼的最小距離是衡量碼的抗干擾能力（檢、糾錯能力）的重要參數(shù)。碼的最小距離越大，碼的抗干擾能力就越強(qiáng)。8.5 線性分組碼的最小距離

22、、檢錯和糾錯能力8/10/202231Department of Electronics and Information, NCUT Song Peng(1) 漢明距離、漢明重量和漢明球漢明球：以碼字 C 為中心，半徑為 t 的漢明球是與 C 的漢明距離t 的向量全體 SC(t) ：任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最小漢明距離 dmin。8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202232Department of Electronics and Information, NCUT Song Peng(1) 漢明距離、漢明重量和漢明球漢明球：8.5 線性分組碼

23、的最小距離、檢錯和糾錯能力返回8/10/202233Department of Electronics and Information, NCUT Song Peng(1) 漢明距離、漢明重量和漢明球漢明重量（碼字重量）W：碼字中非 0 碼元符號的個數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中含“1”的個數(shù)。最小重量 Wmin ：線性分組碼 CI 中，非 0 碼字重量最小值，叫做碼 CI 的最小重量：Wmin =minW(V),VCI ,V08.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202234Department of Electronics and Inform

24、ation, NCUT Song Peng(1) 漢明距離、漢明重量和漢明球 最小距離 與最小重量 的關(guān)系：線性分組碼的最小距離等于它的最小重量。證明： 設(shè)線性碼 CI，且 UCI, VCI 又設(shè) UV=Z 由線性碼的封閉性知，ZCI 因此，d(U,V)=W(Z) 由此可推知，線性分組碼的最小距離必等于非 0 碼字的最小重量。8.5 線性分組碼的最小距離、檢錯和糾錯能力返回目錄8/10/202235Department of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力檢錯能力：如果一個線性碼能檢出長度l 個碼元的任何錯誤

25、圖樣，稱碼的檢錯能力為 l。糾錯能力：如果線性碼能糾正長度t 個碼元的任意錯誤圖樣，稱碼的糾錯能力為 t。最小距離與檢糾錯能力的關(guān)系：線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強(qiáng)。8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202236Department of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力最小距離與糾錯能力：(n,k) 線性碼能糾 t 個錯誤的充要條件是碼的最小距離為：dmin2t+1 (8.5.1)證明：設(shè)發(fā)送的碼字為 V；接收的碼字為 R；U 為任意其它碼字則矢量

26、V、R、U 間滿足距離的三角不等式： d(R,V)+d(R,U)d(U,V) (8.5.2)設(shè)信道干擾使碼字中碼元發(fā)生錯誤的實(shí)際個數(shù)為 t ，且 t t d(R,V)t t (8.5.3)8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202237Department of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力最小距離與糾錯能力：(n,k) 線性碼能糾 t 個錯誤的充要條件是碼的最小距離為：dmin2t+1 (8.5.1)證明：由于 d(U,V)dmin=2t+1，代入式 (7.5.2) 得： d(R,U)

27、d(U,V)d(R,V)= 2t+1t t (8.5.4) 含義：如果接收字 R 中錯誤個數(shù) t t，接收字 R 和發(fā)送字 V 間距離t ，而與其它任何碼字間距離都大于 t，按最小距離譯碼把 R 譯為 V。此時譯碼正確，碼字中的錯誤被糾正。幾何意義：8.5 線性分組碼的最小距離、檢錯和糾錯能力參見圖示8/10/202238Department of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力最小距離與檢錯能力：(n,k) 線性碼能夠發(fā)現(xiàn) l 個錯誤的充要條件是碼的最小距離為：dminl+1 (8.5.5)證明：設(shè)發(fā)送的碼

28、字為 V；接收的碼字為 R；U 為任意其它碼字則矢量V、R、U 間滿足距離的三角不等式： d(R,V)+d(R,U)d(U,V) (8.5.2)設(shè)信道干擾使碼字中碼元發(fā)生錯誤的實(shí)際個數(shù)為 l ，且 l l d(R,V)l l (8.5.6)8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202239Department of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力最小距離與檢錯能力：(n,k) 線性碼能夠發(fā)現(xiàn) l 個錯誤的充要條件是碼的最小距離為：dminl+1 (8.5.5)證明：由于 d(U,V)dmin=

29、l+1，代入式(7.5.2)得：d(R,U) d(U,V)d(R,V)=l+1l 0 (8.5.7) 含義：由于接收字 R 與其它任何碼字 U 的距離都大于0，說明接收字 R 不會因發(fā)生 l 個錯誤變?yōu)槠渌a字，因而必能發(fā)現(xiàn)錯誤。8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202240Department of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力最小距離與檢錯能力： 幾何意義：8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202241Department of Electronics and I

30、nformation, NCUT Song Peng(2) 最小距離與檢、糾錯能力最小距離與檢、糾錯能力：(n,k) 線性碼能糾 t 個錯誤，并能發(fā)現(xiàn) l 個錯誤 (lt) 的充要條件是碼的最小距離為：Dmin t+l+1 (8.5.8)證明：因?yàn)閐min2t+1，根據(jù)最小距離與糾錯能力定理，該碼可糾 t 個錯誤。因?yàn)閐minl+1，根據(jù)最小距離與檢錯能力定理, 該碼有檢 l 個錯誤的能力。糾錯和檢錯不會發(fā)生混淆：設(shè)發(fā)送碼字為 V，接收字為 R，實(shí)際錯誤數(shù)為 l ，且 t t (8.5.9) 不會把 R 誤糾為 U。8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202242Depart

31、ment of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力最小距離與檢、糾錯能力： 幾何意義：8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202243Department of Electronics and Information, NCUT Song Peng(2) 最小距離與檢、糾錯能力8.5 線性分組碼的最小距離、檢錯和糾錯能力當(dāng) (n,k) 線性碼的最小距離 dmin 給定后，可按實(shí)際需要靈活安排糾錯的數(shù)目。例如：對 dmin=8 的碼，可用來糾 3 檢 4 錯，或糾 2檢 5 錯，或糾 1 檢 6錯

32、，或者只用于檢 7 個錯誤。返回目錄8/10/202244Department of Electronics and Information, NCUT Song Peng(3) 線性碼的最小距離與監(jiān)督矩陣的關(guān)系定理8.5.1：設(shè) H 為 (n,k) 線性碼的一致監(jiān)督矩陣，若 H 中任意 S 列線性無關(guān)，而 H 中存在 (S+1) 列線性相關(guān)，則碼的最小距離為 (S+1)。定理8.5.2：若碼的最小距離為 (S+1)，則該碼的監(jiān)督矩陣的任意 S 列線性無關(guān)，而必存在有相關(guān)的 (S+1)列。定理8.5.3：在二元線性碼的監(jiān)督矩陣 H 中，如果任一列都不是全“0”，且任兩列都不相等，則該碼能糾一個

33、錯誤。（S=2，dmin=3）8.5 線性分組碼的最小距離、檢錯和糾錯能力8/10/202245Department of Electronics and Information, NCUT Song Peng8.6 線性分組碼的譯碼8.6.1 伴隨式和錯誤檢測8.6.2 糾錯譯碼8/10/202246Department of Electronics and Information, NCUT Song Peng8.6.1 伴隨式和錯誤檢測(1) 如何譯碼？(2) 伴隨式(3) 伴隨式的計(jì)算(4) 伴隨式的特性(5) 舉例(6) 伴隨式計(jì)算電路8.6線性分組碼的譯碼8/10/202247De

34、partment of Electronics and Information, NCUT Song Peng8.6.1 伴隨式和錯誤檢測(1) 如何譯碼？ 用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個字 R 后，校驗(yàn) HR T=0T 是否成立：若關(guān)系成立，則認(rèn)為 R 是一個碼字；否則判為碼字在傳輸中發(fā)生了錯誤；HR T 的值是否為 0 是校驗(yàn)碼字出錯與否的依據(jù)。(2) 伴隨式/監(jiān)督子/校驗(yàn)子：S=RH T 或 S T=HR T返回目錄8.6線性分組碼的譯碼8/10/202248Department of Electronics and Information, NCUT Song Peng8

35、.6.1 伴隨式和錯誤檢測(3) 伴隨式的計(jì)算 發(fā)送碼字：C=(cn1,cn2,c0) 信道錯誤圖樣：E=(en1,en2,e0) ei=0，表示第 i 位無錯； ei=1，表示第 i 位有錯。i=n1,n2,0 接收字：R=(rn1,rn2,r0)=C+E=(cn1+en1,cn2+en2,c0 +e0) 求接收字的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗(yàn)） S T=HR T=H(C+E )T=HC T+HE T (8.6.1) HC T=0T，所以 S T=HE T 設(shè) H=(h1,h2,hn)，（hi 表示 H 的列）。代入式(8.6.1)得：S T=h1 en1+ h2 en2+ + hn e

36、0返回目錄8.6線性分組碼的譯碼8/10/202249Department of Electronics and Information, NCUT Song Peng8.6.1 伴隨式和錯誤檢測(4) 伴隨式的特性 伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯誤圖樣決定； 伴隨式是錯誤的判別式： 若 S=0，則判為沒有出錯，接收字是一個碼字； 若 S0，則判為有錯。 不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對二元碼，伴隨式是 H 陣中與錯誤碼元對應(yīng)列之和。返回目錄8.6線性分組碼的譯碼8/10/202250Department of Electronics and

37、 Information, NCUT Song Peng(5) 舉 例：(7,3) 碼接收字 R 的伴隨式計(jì)算 若接收字中沒有錯誤： 設(shè)發(fā)送碼字 C=1010011，接收碼字 R1010011，R 與 C 相同： 但接收端譯碼器并不知道就是發(fā)送的碼字 根據(jù)接收字R 計(jì)算伴隨式：S T= HR T =0T 因此，譯碼器判接收字無錯8.6.1 伴隨式和錯誤檢測8.6線性分組碼的譯碼8/10/202251Department of Electronics and Information, NCUT Song Peng(5) 舉 例：(7,3) 碼接收矢量 R 的伴隨式計(jì)算 若接收字中有 1 位錯誤：

38、 發(fā)送碼字C=1010011，接收碼字R=1110011，伴隨式為： (7,3) 碼是糾單個錯誤的碼，且S T 等于H 的第二列，因此判定接收字R 的第二位是錯的。 由于接收字R 中錯誤碼元數(shù)與碼的糾錯能力相符，所以譯碼正確。8.6.1 伴隨式和錯誤檢測8.6線性分組碼的譯碼8/10/202252Department of Electronics and Information, NCUT Song Peng8.6.1 伴隨式和錯誤檢測(5) 舉 例：(7,3) 碼接收矢量 R 的伴隨式計(jì)算 當(dāng)碼元錯誤多于 1 個時： 發(fā)送碼字C=1010011，接收碼字R=0011011，伴隨式為： 由于S

39、 T 是第一列和第四列之和，不等于0； 但S T 與 H 陣中任何一列都不相同無法判定錯誤出在哪些位上，只是發(fā)現(xiàn)有錯。返回目錄8.6線性分組碼的譯碼8/10/202253Department of Electronics and Information, NCUT Song Peng8.6.1 伴隨式和錯誤檢測(6) 伴隨式計(jì)算電路伴隨式的計(jì)算可用電路來實(shí)現(xiàn)。(7,3) 碼為例：接收字 R =(r6r5r4r3r2r1r0)，伴隨式：8.6線性分組碼的譯碼8/10/202254Department of Electronics and Information, NCUT Song Peng8.

40、6.1 伴隨式和錯誤檢測(6) 伴隨式計(jì)算電路伴隨式計(jì)算電路：返回目錄8.6線性分組碼的譯碼8/10/202255Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(1) 最佳譯碼準(zhǔn)則（最大似然譯碼）(2) 查表譯碼法(3) 標(biāo)準(zhǔn)陣列(4) 舉例(5) 結(jié)論8.6線性分組碼的譯碼8/10/202256Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(1) 最佳譯碼準(zhǔn)則（最大似然譯碼） 通信是一個統(tǒng)計(jì)過程，糾、檢錯能力最終要反映

41、到差錯概率上。 對于 FEC 方式，采用糾錯碼后的碼字差錯概率為 pwe： p(C)：發(fā)送碼字C 的先驗(yàn)概率 p(C/R)：后驗(yàn)概率8.6線性分組碼的譯碼8/10/202257Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(1) 最佳譯碼準(zhǔn)則（最大似然譯碼）若碼字?jǐn)?shù)為 2k，對充分隨機(jī)的消息源有 p(C)=1/ 2k，所以最小化的 pwe等價為最小化 p(C C/R )，又等價為最大化：p(C =C/R)；對于 BSC 信道：最大化的 p(C =C/R ) 等價于最大化的 p(R /C) ，最大化的 p(R

42、 /C) 又等價于最小化 d(R,C)，所以使差錯概率最小的譯碼是使接收向量 R 與輸出碼字 C 距離最小的譯碼。返回目錄8.6線性分組碼的譯碼8/10/202258Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(2) 查表譯碼法 按最小距離譯碼，對有 2k 個碼字的 (n,k) 線性碼，為了找到與接收字 R 有最小距離的碼字，需將 R 分別和 2k 個碼字比較，以求出最小距離。其中利用“標(biāo)準(zhǔn)陣列”譯碼是最典型的方法。返回目錄8.6線性分組碼的譯碼8/10/202259Department of Elect

43、ronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 碼字參數(shù)：發(fā)送碼字：取自于 2k 個碼字集合 C； 接收碼字：可以是 2n 個 n 重中任一個矢量。 譯碼方法把 2n 個 n 重矢量劃分為 2k 個互不相交的子集 ，使得在每個子集中僅含一個碼字；根據(jù)碼字和子集間一一對應(yīng)關(guān)系，若接收矢量 Rl 落在子集 Dl 中，就把 Rl 譯為子集 Dl 含有的碼字 Cl；當(dāng)接收矢量 R 與實(shí)際發(fā)送碼字在同一子集中時，譯碼就是正確的。8.6線性分組碼的譯碼8/10/202260Department of Electronics and Info

44、rmation, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列構(gòu)造方法先將 2k 個碼字排成一行，作為標(biāo)準(zhǔn)陣列的第一行，并將全 0 碼字 C1=(000) 放在最左面的位置上；然后在剩下的 (2n2k) 個 n 重中選取一個重量最輕的 n 重 E2 放在全 0 碼字 C1 下面，再將 E2 分別和碼字 相加，放在對應(yīng)碼字下面構(gòu)成陣列第二行；在第二次剩下的 n 重中，選取重量最輕的 n 重 E3，放在 E2 下面，并將 E3 分別加到第一行各碼字上，得到第三行；，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到表 7.6.1 所示的給定 (n,k) 線性碼的標(biāo)準(zhǔn)陣列。

45、8.6線性分組碼的譯碼8/10/202261Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列構(gòu)造方法返回8.6線性分組碼的譯碼8/10/202262Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性定理8.6.1：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且 2n 個 n 重中任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。證明：因?yàn)殛嚵兄腥我恍卸际怯伤x出某一 n 重矢量分別

46、與 2k 個碼字相加構(gòu)成的，而 2k 個碼字互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；在構(gòu)造標(biāo)準(zhǔn)陣列時，是用完全部 n 重為止，因而每個 n 重必出現(xiàn)一次；每個 n 重只能出現(xiàn)一次：8.6線性分組碼的譯碼8/10/202263Department of Electronics and Information, NCUT Song Peng(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性定理8.6.1：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且 2n 個 n 重中任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。證明：8.6.2 糾錯譯碼假定某一 n 重 X 出現(xiàn)在第 l 行第 i 列，那

47、么 X=El+Ci；又假設(shè) X 出現(xiàn)在第 m 行第 j 列，那么 X=Em+Cj，ll) 的第一個元素;按陣列構(gòu)造規(guī)則，后面行的第一個元素是前面行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)則相矛盾。每個 n 重只能出現(xiàn)一次的原因8.6線性分組碼的譯碼8/10/202264Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性定理8.6.2（線性碼糾錯極限定理）：二元 (n,k) 線性碼能糾 2nk 個錯誤圖樣。這 2nk 個可糾的錯誤圖樣，包括 0 矢量在內(nèi)，即把無錯的情況也看成一個可糾的

48、錯誤圖樣。證明：陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個陪集。陪集首：每個陪集的第一個元素叫做陪集首。(n,k) 線性碼的標(biāo)準(zhǔn)陣列有 2k 列（和碼字?jǐn)?shù)量相等），2n/2k= 2nk 行，且任何兩列和兩行都沒有相同的元素。8.6線性分組碼的譯碼8/10/202265Department of Electronics and Information, NCUT Song Peng(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性定理8.6.2（線性碼糾錯極限定理）： 證明：每一列包含 2nk 個元素，最上面的是一個碼字，其它元素是陪集首和該碼字之和，例如第 j 列為：若發(fā)送碼字為 Cj，信道干擾的錯誤圖樣是陪集首，則接

49、收矢量 R 必在 Dj 中；8.6.2 糾錯譯碼見表8.6線性分組碼的譯碼8/10/202266Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性定理7.6.2 (線性碼糾錯極限定理)： 證明：若錯誤圖樣不是陪集首，則接收矢量 R 不在 Dj 中，則譯成其它碼字，造成錯誤譯碼；當(dāng)且僅當(dāng)錯誤圖樣為陪集首時，譯碼才是正確的。可糾正的錯誤圖樣：這 2nk 個陪集首稱為可糾正的錯誤圖樣。見表8.6線性分組碼的譯碼8/10/202267Department of Electronics a

50、nd Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：一個可糾 t 個錯誤的線性碼必須滿足：上式中等式成立時的線性碼稱為完備碼。即：8.6線性分組碼的譯碼8/10/202268Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：證明：糾一個錯誤的 (n,k) 線性碼，必須能糾正 個錯誤圖樣，因此：對糾兩個錯誤的 (n,k) 線性碼，必須能糾 個錯誤圖樣，所以

51、：8.6線性分組碼的譯碼8/10/202269Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：證明：依此類推，一個糾 t 個錯誤的 (n,k) 線性碼必須滿足：對于完備碼，由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤圖樣數(shù)，所以完備碼的 (nk) 個監(jiān)督碼元得到了充分的利用。8.6線性分組碼的譯碼8/10/202270Department of Electronics and Information, NCUT Song Peng8.6.2

52、 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性完備譯碼：(n,k) 線性碼的所有 2nk 個伴隨式，在譯碼過程中都用來糾正所有小于等于 個隨機(jī)錯誤，以及部分大于 t 的錯誤圖樣。限定距離譯碼：任一個 (n,k) 線性碼，能糾正 個隨機(jī)錯誤，如果在譯碼時僅糾正 t t 個錯誤，而當(dāng)錯誤個數(shù)大于 t 時，譯碼器不進(jìn)行糾錯而僅指出發(fā)生了錯誤。8.6線性分組碼的譯碼8/10/202271Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼 假定圍繞每一個碼字 Ci

53、 放置一個半徑為 t 的球，每個球內(nèi)包含了與該碼字漢明距離小于等于 t 的所有接收碼字 R 的集合； 在半徑為 的球內(nèi)的接收碼字?jǐn)?shù)是： 因?yàn)橛?2k 個可能發(fā)送的碼字，也就有 2k 個不相重疊的半徑為 t 的球。包含在 2k 個球中的碼字總數(shù)不會超過 2n 個可能的接收碼字。8.6線性分組碼的譯碼8/10/202272Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼 于是一個糾 t 個差錯的碼必然滿足不等式： 如果上式中等號成立，表示所有的接收碼字

54、都落在 2k 個球內(nèi)，而球外沒有一個碼，這就是完備碼。8.6線性分組碼的譯碼8/10/202273Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼 完備碼特性：圍繞 2k 個碼字，漢明距離為 t=INT(dmin1)/2 的所有球都是不相交的，每一個接收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離至多為 t，這時所有重量 t 的錯誤圖樣都能用最佳（最小距離）譯碼器得到糾正，而所有重量t+1 的錯誤圖樣都不能糾正。8.6線性分組碼的譯碼8/10/

55、202274Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼 舉例：對糾一個錯誤的 (7,4) 漢明碼：(7,4) 漢明碼是一個完備碼。 所有漢明碼都是完備碼：（滿足2nk = 2r=n+1）。8.6線性分組碼的譯碼8/10/202275Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性 標(biāo)準(zhǔn)陣列譯碼 = 最小距離譯碼 = 最佳譯碼

56、陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯誤圖樣作陪集首； 重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列時是選取重量最輕的 n 重作陪集首； 當(dāng)錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼字間的距離（等于陪集首）最?。?因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最小距離譯碼； 所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。8.6線性分組碼的譯碼8/10/202276Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(3) 標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性定理7.6.3：在

57、標(biāo)準(zhǔn)陣列中，一個陪集的所有 2k 個 n 重有相同的伴隨式，不同的陪集伴隨式互不相同。證明：設(shè) H 為給定 (n,k) 線性碼的監(jiān)督矩陣，在陪集首為 El 的陪集中的任意矢量為：R=El+Ci, i=1,2,2k其伴隨式為：S=RH T=(El+Ci)H T=ElH T+CiH T =ElH T上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨式。即同一陪集中所有伴隨式相同。不同陪集中，由于陪集首不同所以伴隨式不同。返回目錄8.6線性分組碼的譯碼8/10/202277Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯

58、譯碼(4) 舉例： (6,3)碼的標(biāo)準(zhǔn)陣列返回返回目錄8.6線性分組碼的譯碼8/10/202278Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(5) 結(jié)論 任意 n 重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪集首。 標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對應(yīng)的，因而碼的可糾錯誤圖樣和伴隨式是一一對應(yīng)的，應(yīng)用此對應(yīng)關(guān)系可以構(gòu)成比標(biāo)準(zhǔn)陣列簡單得多的譯碼表，從而得到 (n,k) 線性碼的一般譯碼步驟。 (n,k) 線性碼的一般譯碼步驟 計(jì)算接收矢量 R 的伴隨式 S T=HR T ； 根據(jù)伴隨式和錯誤圖樣一一對應(yīng)的關(guān)系

59、，利用伴隨式譯碼表，由伴隨式譯出 R 的錯誤圖樣 E； 將接收字減錯誤圖樣，得發(fā)送碼字的估值：C =RE 。見表8.6線性分組碼的譯碼8/10/202279Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(5) 結(jié)論線性分組碼一般譯碼器（伴隨式譯碼法/查表譯碼法） 譯碼器如下圖。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯誤概率，原則上可用于任何 (n,k) 線性碼。8.6線性分組碼的譯碼8/10/202280Department of Electronics and Information, NCUT S

60、ong Peng8.6.2 糾錯譯碼(5) 結(jié)論 舉例： 求 (7,4) 漢明碼的編碼電路和譯碼電路。 其系統(tǒng)碼形式：8.6線性分組碼的譯碼8/10/202281Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(5) 結(jié)論 舉例： 求 (7,4) 漢明碼的編碼電路和譯碼電路。 編碼電路：8.6線性分組碼的譯碼8/10/202282Department of Electronics and Information, NCUT Song Peng8.6.2 糾錯譯碼(5) 結(jié)論 舉例： 求 (7,4) 漢明碼的編