信息論第九章

1、信息論第九章第1頁，共63頁，2022年，5月20日，1點21分，星期一前向糾錯(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。接收端信道譯碼器對接收碼字進行譯碼，若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時，譯碼器對差錯進行定位并加以糾正。自動請求重發(fā)(ARQ)：用于檢測的糾錯碼在譯碼器輸出端只給出當前碼字傳輸是否可能出錯的指示，當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字全部或部分。9.1 差錯控制的基本方式第2頁，共63頁，2022年，5月20日，1點21分，星期一混合糾錯(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組，收

2、端收到碼組后，檢查差錯情況，如果差錯在碼的糾錯能力以內(nèi)，則自動進行糾正。如果信道干擾很嚴重，錯誤很多，超過了碼的糾錯能力，但能檢測出來，則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。9.1 差錯控制的基本方式第3頁，共63頁，2022年，5月20日，1點21分，星期一分組碼：編碼的規(guī)則僅局限于本碼組之內(nèi)，本碼組的監(jiān)督元僅和本碼組的信息元相關(guān)。 信息碼組由 k 個二進制碼元組成，共有 2k 個不同的信息碼組； 附加nk個碼元，每個監(jiān)督元取值與該信息碼組的k個碼元有關(guān)； 編碼器輸出長度 n； 這2k 個碼字的集合稱為 (n,k) 分組碼；卷積碼：本碼組的監(jiān)督元不僅和本碼組的信息元相關(guān)，而且還與本碼組相鄰的前

3、n1 個碼組的信息元相關(guān)。9.2 糾錯碼分類第4頁，共63頁，2022年，5月20日，1點21分，星期一是否可用線性方程組來表示線性碼：編碼規(guī)則可以用線性方程表示；非線性碼：編碼規(guī)則不能用線性方程表示；按碼字的結(jié)構(gòu)分系統(tǒng)碼：前 k 個碼元與信息碼組一致；非系統(tǒng)碼：沒有系統(tǒng)碼的特性。按糾正差錯的類型可分為糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼；按碼字中每個碼元的取值可分為二進制碼和多進制碼。9.2 糾錯碼分類第5頁，共63頁，2022年，5月20日，1點21分，星期一漢明距離/距離：在 (n,k)線性碼中，兩個碼字 U、V 之間對應碼元位上符號取值不同的個數(shù)，稱為碼字 U、V 之間的漢明距離。線性分

4、組碼的一個碼字對應于 n 維線性空間中的一點，碼字間的距離即為空間中兩對應點的距離。碼距與糾檢錯能力第6頁，共63頁，2022年，5月20日，1點21分，星期一漢明重量/碼字重量/W：碼字中非0碼元符號的個數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中含“1”的個數(shù)。最小距離與最小重量的關(guān)系：線性分組碼的最小距離等于它的非零碼字的最小重量。 第7頁，共63頁，2022年，5月20日，1點21分，星期一一般地說，線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。最小距離與檢、糾錯能力最小距離與糾錯能力：(n,k) 線性碼能糾 t 個錯誤的充要條件是碼的最小距

5、離為 第8頁，共63頁，2022年，5月20日，1點21分，星期一 幾何意義：第9頁，共63頁，2022年，5月20日，1點21分，星期一最小距離與檢錯能力：(n,k) 線性碼能夠發(fā)現(xiàn) l 個錯誤的充要條件是碼的最小距離為dmin=l+1 或 l=dmin1第10頁，共63頁，2022年，5月20日，1點21分，星期一線性空間的概念定理：（n,k）線性分組碼是n維n重線性空間的一個k維線性子空間。線性空間相關(guān)概念：（1）n維線性空間：由n個線性無關(guān)的矢量組成基底，它們的全部線性組合所構(gòu)成的空間。若矢量長度也為n，則稱n維n重線性空間S。第11頁，共63頁，2022年，5月20日，1點21分，星

6、期一（2）線性子空間：從n個基底中選出一組k（kn）個基底，它們的全部線性組合也構(gòu)成一個集合，這個集合是S的一個k維子集，稱為k維n重子空間，記作 。（3）n維空間的n個基底不是唯一的。第12頁，共63頁，2022年，5月20日，1點21分，星期一（4）矢量正交：兩矢量內(nèi)積為零。矢量空間正交：一空間中的任一矢量都和另一空間的任一矢量正交。（5）對偶空間：以互相正交的基底組張成的兩個線性空間一定正交，這兩個空間稱為對偶空間，其中一個空間是另一個空間的零空間。第13頁，共63頁，2022年，5月20日，1點21分，星期一（6）碼空間與校驗空間：把n維n重線性空間中互相正交的n個基底分成兩組：一組k

7、個基底，另一組（n-k）個基底，則它們分別張成k維n重和（n-k）維n重兩個正交的對偶空間，將k維n重空間用作碼空間C，將（n-k）維n重空間用作校驗空間H。第14頁，共63頁，2022年，5月20日，1點21分，星期一 將H空間的（n-k）個基底排列起來可構(gòu)成一個（n-k）n矩陣，稱為線性碼C的一致校驗（或監(jiān)督）矩陣，簡稱為校驗（或監(jiān)督）矩陣H。H是（n，n-k）對偶碼的生成矩陣，它的每一行是一個基底，也是一個碼字。第15頁，共63頁，2022年，5月20日，1點21分，星期一第2節(jié) 線性分組碼第16頁，共63頁，2022年，5月20日，1點21分，星期一在由 (n,k) 線性碼構(gòu)成的碼空間

8、C中，一定存在 k 個線性獨立的碼字：g1,g2, gk,。碼 集 中其它任何碼字C都可以表為這 k 個碼字的一種線性組合，即線性分組碼的生成矩陣第17頁，共63頁，2022年，5月20日，1點21分，星期一第18頁，共63頁，2022年，5月20日，1點21分，星期一G中每一行 gi=(gi1,gi2, gin ) 都是一個碼字；對每一個信息組m，由矩陣G都可以求得 (n,k) 線性碼對應的碼字。(n,k) 線性碼的每一個碼字都是生成矩陣 G 的行矢量的線性組合，所以它的 2k 個碼字構(gòu)成了由 G 的行張成的 n 維空間的一個 k 維子空間 。第19頁，共63頁，2022年，5月20日，1點

9、21分，星期一通過行初等變換，將 G 化為前 k 列是單位子陣的標準形式 線性系統(tǒng)分組碼第20頁，共63頁，2022年，5月20日，1點21分，星期一舉例 已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為第2節(jié) 線性分組碼第21頁，共63頁，2022年，5月20日，1點21分，星期一定理 (n,k) 線性分組碼最小距離等于dmin的充要條件是：校驗矩陣H的列矢量中至少要有dmin個才能線性相關(guān),而任意（dmin-1)列線性無關(guān)。定理 (n,k) 線性分組碼的最小距離必定小于等于 (n-k+1)dmin (n-k+1) 第22頁，共63頁，2022年，5月20日，1點21分，星期一例： H (7，4)線性碼

10、 各列都不相同，任意2列之和不等于0，2列線性無關(guān)；某3列線性相關(guān)。所以該碼的最小距離為3，小于n-k +14。第23頁，共63頁，2022年，5月20日，1點21分，星期一（n,k）線性碼最小距離dmin的上邊界是n-k +1。如果我們設計的（n,k）線性碼的dmin達到了n-k +1，就是達到了設計性能的極點。因此，dmin n-k +1的碼稱為極大最小距離碼 (MDC Maximized minimum Distance Code)。生成矩陣和校驗矩陣第24頁，共63頁，2022年，5月20日，1點21分，星期一伴隨式與譯碼 m C=(c1,cn) R=(r1,rn) (n,k) 信道定

11、義差錯圖案E E(e1,en) RC (r1c1,rncn) 二進制碼中模2加與模2減是等同的，因此有E = R C 及R = C E 第25頁，共63頁，2022年，5月20日，1點21分，星期一伴隨式S的定義因為CHT = 0 所以RHT(CE)HTCHTEHT= EHT如果收碼無誤：必有RC即E0， 則EHT= 0 RHT = 0。如果收碼有誤：即E 0， 則RHT = EHT 0。 在HT固定的前提下，RHT僅僅與差錯圖案E有關(guān)，而與發(fā)送碼C無關(guān)。定義伴隨式S: S = (s1, s2 ,sn-k) = RHT = EHT 第26頁，共63頁，2022年，5月20日，1點21分，星期一

12、從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。差錯圖案E是n重矢量，共有2n個可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個可能的組合，因此不同的差錯圖案可能有相同的伴隨式。接收端收到R后，因為已知HT，可求出 SRHT；如果能知道對應的E，則通過C = RE而求得C。 RHT = S ? C = RE R S E C 只要E正確，譯出的碼也就是正確的。 伴隨式S的意義第27頁，共63頁，2022年，5月20日，1點21分，星期一差錯圖案E的求解(1) 可以通過解線性方程求解E：S = (s1, s2 ,sn-k) = EHT = (e1, e

13、2 , , en)得到線性方程組：sn-k=e1h(n-k)(1)+enh(n-k)ns1 = e1h11 + + en h1n第28頁，共63頁，2022年，5月20日，1點21分，星期一上述方程組中有n個未知數(shù)e1, e2 , , en ，卻只有n-k個方程，可知方程組有多解。在有理數(shù)或?qū)崝?shù)域中，少一個方程就可能導致無限多個解，而在二元域中，少一個方程導致兩個解，少兩個方程四個解，以此類推，少n-( n-k) = k個方程導致每個未知數(shù)有2k個解。因此，由上述方程組解出的E可以有2k個解。到底取哪一個作為附加在收碼R上的差錯圖案E的估值呢？概率譯碼：把所有2k個解的重量(差錯圖案E中1的個

14、數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計算效率不高。第29頁，共63頁，2022年，5月20日，1點21分，星期一依據(jù)：若BSC信道的差錯概率是p，則長度n的碼中錯誤概率 ： 0個錯 1個錯 2個錯 n個錯 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于p 出錯越少的情況，發(fā)生概率越大，E的重量越輕，所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準則，即最大似然譯碼。第30頁，共63頁，2022年，5月20日，1點21分，星期一標準陣列譯碼表 上述的概率譯碼，如每接收一個碼R就要解一次線性方程，那就太麻煩了。好在伴隨式S的數(shù)目是有限的2n-k個，如果n-k不太

15、大，我們可以預先把不同S下的方程組解出來，把各種情況下的最大概率譯碼輸出列成一個碼表。這樣，在實時譯碼時就不必再去解方程，而只要象查字典那樣查一下碼表就可以了。這樣構(gòu)造的表格叫做標準陣列譯碼表。 第31頁，共63頁，2022年，5月20日，1點21分，星期一表中所列碼字是接收到的碼字R 。將沒有任何差錯時的收碼R放在第一行，收碼等于發(fā)碼R=C(CCi,i =0,1,2k-1), 差錯圖案為全零E0=(0,00)，伴隨式為全零S0=(0,00)。由于有2k個碼字，碼表有2k列。在第2到第n+1的n行中差錯圖案的所有重量為1 (共n個)。如果(1+ n)2n-k，再在下面行寫出全部帶有2個差錯的圖

16、案 (共 個)。如果總行數(shù)(1+n + )仍然小于2n-k，再列出帶有3個差錯的圖案，以此類推，直到放滿2n-k行，每行一個Ej, 對應一個不同的伴隨式Sj。這樣，表的行數(shù)2n-k正好等于伴隨式的數(shù)目。標準陣列譯碼表的構(gòu)成 第32頁，共63頁，2022年，5月20日，1點21分，星期一S0 E0S1 E1 Sj Ej E0+C0= 0+0= 0E0+C1= C1E0+Ci= CiE1+C0= E1E1+CiEj+C0= EjEj+C1Ej+Ci 標準陣列譯碼表 E1+C1 第33頁，共63頁，2022年，5月20日，1點21分，星期一陪集和子集譯碼表中有2n-k行，每行是一個陪集，每陪集的第一

17、個元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素對應共同的一個伴隨式。第一行陪集的陪集首是全零伴隨式S0所對應的全零差錯圖案E0(無差錯)，而第j行陪集的陪集首是伴隨式Sj所對應的重量最小的差錯圖案Ej (C0=0, Rj=Ej)。定理：在標準陣列中，一個陪集的所有 2k 個 n 重有相同的伴隨式，不同的陪集伴隨式互不相同。第34頁，共63頁，2022年，5月20日，1點21分，星期一譯碼表中有2k列，每列是一個子集，每子集的第一個元素(位于第一行)叫子集頭。同一子集（同一列）中的所有元素對應同一個碼字，第一列子集的子集頭是全零碼字C0，而第i列子集的子集頭是碼字Ci (E0=0,

18、 Ri=Ci) 。第35頁，共63頁，2022年，5月20日，1點21分，星期一例 一個(5,2)系統(tǒng)線性碼的生成矩陣是G = 設收碼R = (10101)，構(gòu)造標準陣列譯碼表，譯出發(fā)碼的估值解：(1)構(gòu)造標準陣列譯碼表。分別以信息組m= (00)、(01) 、(10)、(11)及已知的G求得4個許用碼字為C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校驗矩陣： H = PT I3 = 列出方程組：S = (s1, s2 , s3) = (e1, e2 , , e5) 第36頁，共63頁，2022年，5月20日，1點21分，星期一伴

19、隨式有2n-k238種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有 種，已有6種。代表兩個差錯的圖案有 種。只需挑選其中的兩個，挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對應的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對應的差錯圖案是2k個即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式(

20、110)所對應的最輕差錯圖案之一是(00110)。 譯碼表的構(gòu)成第37頁，共63頁，2022年，5月20日，1點21分，星期一S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=0011010001010

21、1111100標準陣列譯碼表第38頁，共63頁，2022年，5月20日，1點21分，星期一將接收碼R10101譯碼 可選以下三種方法之一譯碼：直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。先求伴隨式RHT = (10101) HT = (010) = S4，確定S4所在行，再沿著行對碼表作一維搜索找到(10101), 最后順著所在列向上找出碼字(10111)。先求出伴隨式RHT = (010) = S4并確定S4所對應的陪集首（差錯圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C= R+ E4= (10101)+ (00010)= (

22、10111)。 上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。第39頁，共63頁，2022年，5月20日，1點21分，星期一 對上例作進一步分析，還可以看到，該(5,2)碼的dmin=3, 糾錯能力是t = INT(3-1)/2 = 1。因此，譯碼陣列中只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準則，而第7、8行的差錯圖案(00011)和(00110)中包含兩個“1”，已超出了t= 1的糾錯能力，譯碼已不可靠。比如，當收碼R(10100)時，根據(jù)碼表譯出的碼字是(10111)，與收碼R的漢明距離是2，然而收碼R與全零碼字(00000)的漢明距離也

23、是2，為什么不能譯成(00000)呢？事實上，碼表的第7、8行本身就不是唯一的。注意在碼表計算過程中，伴隨式(011)所對應的4個差錯圖案中有兩個并列重量最輕，如果當時選的不是(00011)而是(10100)，那么碼表第7行就不是現(xiàn)在這樣了。 對本例 題的分析第40頁，共63頁，2022年，5月20日，1點21分，星期一任何一個二元(n,k)線性分組碼都有2n-k個伴隨式，假如該碼的糾錯能力是t，則對于任何一個重量小于等于t的差錯圖案，都應有一個伴隨式與之對應，也就是說，伴隨式的數(shù)目滿足條件 上式稱作漢明限，任何一個糾t碼都應滿足上述條件。 完備碼(Perfect code) 第41頁，共63

24、頁，2022年，5月20日，1點21分，星期一完備碼 某二元(n,k)線性分組碼能使等式 成立，即該碼的伴隨式數(shù)目不多不少恰好和不大于t個差錯的圖案數(shù)目相等，相當于在標準譯碼陣列中能將所有重量不大于t的差錯圖案選作陪集首，而沒有一個陪集首的重量大于t，這時的校驗位得到最充分的利用。這樣的二元(n,k)線性分組碼稱為完備碼。 第42頁，共63頁，2022年，5月20日，1點21分，星期一漢明碼(Hamming Code) 漢明碼不是指一個碼，而是代表一類碼。漢明碼的糾錯能力t = 1，既有二進制的，也有非二進制的。二進制時，漢明碼碼長n和信息位k服從以下規(guī)律： (n,k)=(2m-1, 2m-1

25、-m) 其中m= n-k，是正整數(shù)。當m3、4、5、6、7、8時，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)。漢明碼是完備碼，因為它滿足上述等式。第43頁，共63頁，2022年，5月20日，1點21分，星期一漢明碼校驗矩陣的構(gòu)成 漢明碼的校驗矩陣H具有特殊的性質(zhì)，能使構(gòu)造方法簡化。一個(n,k)碼的校驗矩陣有nk行和n列，二進制時n-k個碼元所能組成的列矢量總數(shù)是2n-k-1, 恰好和校驗矩陣的列數(shù)n =2m-1相等。只要排列所有列，通過列置換將矩陣H轉(zhuǎn)換成系統(tǒng)形式，就可以進一步得到相應的生成矩陣G。 第44頁，共63頁，2022

26、年，5月20日，1點21分，星期一例 構(gòu)造一個m=3的二元(7，4)漢明碼。解：先利用漢明碼的特性構(gòu)造一個(7，4)漢明碼的校驗矩陣H，再通過列置換將它變?yōu)橄到y(tǒng)形式： 0 0 0 1 1 1 1 列置換 1 1 1 0 1 0 0 H = 0 1 1 0 0 1 1 0 1 1 1 0 1 0 = PT I3 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩陣G為 1 0 0 0 1 0 1 G = I4 P = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 第45頁，共63頁，2022年，5月20日，1點21分，星期一1 、循環(huán)碼的多項式

27、描述2 、循環(huán)碼的生成多項式3 、系統(tǒng)循環(huán)碼4 、多項式運算電路5 、循環(huán)碼的編碼電路6 、循環(huán)碼的譯碼7 、循環(huán)漢明碼8 、縮短循環(huán)碼第4節(jié)循環(huán)碼第46頁，共63頁，2022年，5月20日，1點21分，星期一(1) 循環(huán)碼的性質(zhì)循環(huán)碼是線性分組碼的一個重要子類；由于循環(huán)碼具有優(yōu)良的代數(shù)結(jié)構(gòu)，使得可用簡單的反饋移位寄存器實現(xiàn)編碼和伴隨式計算，并可使用多種簡單而有效的譯碼方法；循環(huán)碼是研究最深入、理論最成熟、應用最廣泛的一類線性分組碼。第4節(jié)循環(huán)碼第47頁，共63頁，2022年，5月20日，1點21分，星期一(2) 循環(huán)碼的定義循環(huán)碼：如果 (n,k) 線性分組碼的任意碼矢C=(Cn1,Cn2,

28、C0) 的 i 次循環(huán)移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni) 仍是一個碼矢，則稱此線性碼為 (n,k) 循環(huán)碼。第4節(jié)循環(huán)碼第48頁，共63頁，2022年，5月20日，1點21分，星期一(3) 碼多項式碼多項式：為了運算的方便，將碼矢的各分量作為多項式的系數(shù)，把碼矢表示成多項式，稱為碼多項式。其一般表示式為C(x)=Cn1xn1+Cn2xn2+C0)碼多項式 i 次循環(huán)移位的表示方法 記碼多項式C(x)的一次左移循環(huán)為 C(1)(x) ，i 次左移循環(huán)為 C(i)(x)第4節(jié)循環(huán)碼第49頁，共63頁，2022年，5月20日，1點21分，星期一碼多項式的模 (xn+

29、1) 運算0和1兩個元素模2運算下構(gòu)成域。第4節(jié)循環(huán)碼第50頁，共63頁，2022年，5月20日，1點21分，星期一碼矢 C 循環(huán) i 次所得碼矢的碼多項式 C(x) 乘以 x，再除以 (xn+1)，得第4節(jié)循環(huán)碼第51頁，共63頁，2022年，5月20日，1點21分，星期一上式表明：碼矢循環(huán)一次的碼多項式 C(1)(x) 是原碼多項式 C(x)乘以 x 除以 (xn+1) 的余式。寫作因此， C(x) 的 i 次循環(huán)移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即結(jié)論：循環(huán)碼的碼矢的 i 次循環(huán)移位等效于將碼多項式乘 xi 后再模 (xn+1)。第4節(jié)循環(huán)碼第5

30、2頁，共63頁，2022年，5月20日，1點21分，星期一(4) 舉例：(7,3) 循環(huán)碼可由任一個碼矢，比如 (0011101) 經(jīng)過循環(huán)移位，得到其它6個非0碼矢；也可由相應的碼多項式(x4+x3+x2+1)，乘以xi(i=1,2,6)，再模(x7+1)運算得到其它6個非0碼多項式。移位過程和相應的多項式運算如表所示。第4節(jié)循環(huán)碼第53頁，共63頁，2022年，5月20日，1點21分，星期一第4節(jié)循環(huán)碼第54頁，共63頁，2022年，5月20日，1點21分，星期一循環(huán)碼的生成矩陣 在 (n,k) 循環(huán)碼的 2k 個碼字中，取前 (k1) 位皆為0的碼字 g(x)（其次數(shù)r=nk），再經(jīng) (k1) 次循環(huán)移位，共得到 k 個碼字:g(x),xg(x),xk1 g(x) 這 k 個碼字顯然是相互獨立的，可作為碼生成矩陣的 k 行，于是得到循環(huán)碼的生成矩陣 G(x)第4節(jié)循環(huán)碼第55頁，共63頁，2022年，5月20日，1點21分，星期一(2) 循環(huán)碼的生成多項式碼的生成矩陣一旦確定，碼就確定了；這就說明： (n,k) 循環(huán)碼可由它的一個 (nk) 次碼多項式 g(x) 來確定；所以說 g(x) 生成了 (n,k) 循環(huán)碼，因此稱 g(x)