信息論第九章

信息論第九章第一頁，共六十三頁，2022年，8月28日前向糾錯(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。接收端信道譯碼器對接收碼字進行譯碼，若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時，譯碼器對差錯進行定位并加以糾正。自動請求重發(fā)(ARQ)：用于檢測的糾錯碼在譯碼器輸出端只給出當前碼字傳輸是否可能出錯的指示，當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字全部或部分。9.1差錯控制的基本方式第二頁，共六十三頁，2022年，8月28日混合糾錯(HEC)：是FEC與ARQ方式的結合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組，收端收到碼組后，檢查差錯情況，如果差錯在碼的糾錯能力以內(nèi)，則自動進行糾正。如果信道干擾很嚴重，錯誤很多，超過了碼的糾錯能力，但能檢測出來，則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。9.1差錯控制的基本方式第三頁，共六十三頁，2022年，8月28日分組碼：編碼的規(guī)則僅局限于本碼組之內(nèi)，本碼組的監(jiān)督元僅和本碼組的信息元相關。信息碼組由k個二進制碼元組成，共有2k個不同的信息碼組；附加n－k個碼元，每個監(jiān)督元取值與該信息碼組的k個碼元有關；編碼器輸出長度n；這2k

個碼字的集合稱為(n,k)分組碼；卷積碼：本碼組的監(jiān)督元不僅和本碼組的信息元相關，而且還與本碼組相鄰的前n－1個碼組的信息元相關。9.2糾錯碼分類第四頁，共六十三頁，2022年，8月28日是否可用線性方程組來表示線性碼：編碼規(guī)則可以用線性方程表示；非線性碼：編碼規(guī)則不能用線性方程表示；按碼字的結構分系統(tǒng)碼：前k

個碼元與信息碼組一致；非系統(tǒng)碼：沒有系統(tǒng)碼的特性。按糾正差錯的類型可分為糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼；按碼字中每個碼元的取值可分為二進制碼和多進制碼。9.2糾錯碼分類第五頁，共六十三頁，2022年，8月28日漢明距離/距離：在(n,k)線性碼中，兩個碼字U、V之間對應碼元位上符號取值不同的個數(shù)，稱為碼字U、V之間的漢明距離。線性分組碼的一個碼字對應于n維線性空間中的一點，碼字間的距離即為空間中兩對應點的距離。碼距與糾檢錯能力第六頁，共六十三頁，2022年，8月28日漢明重量/碼字重量/W：碼字中非0碼元符號的個數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中含“1”的個數(shù)。最小距離與最小重量的關系：線性分組碼的最小距離等于它的非零碼字的最小重量。

第七頁，共六十三頁，2022年，8月28日一般地說，線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。最小距離與檢、糾錯能力最小距離與糾錯能力：(n,k)線性碼能糾t個錯誤的充要條件是碼的最小距離為

第八頁，共六十三頁，2022年，8月28日

幾何意義：第九頁，共六十三頁，2022年，8月28日最小距離與檢錯能力：(n,k)線性碼能夠發(fā)現(xiàn)l個錯誤的充要條件是碼的最小距離為dmin=l+1或l=dmin－1第十頁，共六十三頁，2022年，8月28日線性空間的概念定理：（n,k）線性分組碼是n維n重線性空間的一個k維線性子空間。線性空間相關概念：（1）n維線性空間：由n個線性無關的矢量組成基底，它們的全部線性組合所構成的空間。若矢量長度也為n，則稱n維n重線性空間S。第十一頁，共六十三頁，2022年，8月28日（2）線性子空間：從n個基底中選出一組k（k<n）個基底，它們的全部線性組合也構成一個集合，這個集合是S的一個k維子集，稱為k維n重子空間，記作。（3）n維空間的n個基底不是唯一的。第十二頁，共六十三頁，2022年，8月28日（4）矢量正交：兩矢量內(nèi)積為零。矢量空間正交：一空間中的任一矢量都和另一空間的任一矢量正交。（5）對偶空間：以互相正交的基底組張成的兩個線性空間一定正交，這兩個空間稱為對偶空間，其中一個空間是另一個空間的零空間。第十三頁，共六十三頁，2022年，8月28日（6）碼空間與校驗空間：把n維n重線性空間中互相正交的n個基底分成兩組：一組k個基底，另一組（n-k）個基底，則它們分別張成k維n重和（n-k）維n重兩個正交的對偶空間，將k維n重空間用作碼空間C，將（n-k）維n重空間用作校驗空間H。第十四頁，共六十三頁，2022年，8月28日將H空間的（n-k）個基底排列起來可構成一個（n-k）×n矩陣，稱為線性碼C的一致校驗（或監(jiān)督）矩陣，簡稱為校驗（或監(jiān)督）矩陣H。H是（n，n-k）對偶碼的生成矩陣，它的每一行是一個基底，也是一個碼字。第十五頁，共六十三頁，2022年，8月28日第2節(jié)線性分組碼第十六頁，共六十三頁，2022年，8月28日在由(n,k)線性碼構成的碼空間C中，一定存在k個線性獨立的碼字：g1,g2,…,gk,。碼集

中其它任何碼字C都可以表為這k個碼字的一種線性組合，即線性分組碼的生成矩陣第十七頁，共六十三頁，2022年，8月28日第十八頁，共六十三頁，2022年，8月28日G中每一行gi=(gi1,gi2,…,gin)都是一個碼字；對每一個信息組m，由矩陣G都可以求得(n,k)線性碼對應的碼字。(n,k)線性碼的每一個碼字都是生成矩陣G的行矢量的線性組合，所以它的2k個碼字構成了由G的行張成的n維空間的一個k維子空間。第十九頁，共六十三頁，2022年，8月28日通過行初等變換，將G化為前k

列是單位子陣的標準形式

線性系統(tǒng)分組碼第二十頁，共六十三頁，2022年，8月28日舉例已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為第2節(jié)線性分組碼第二十一頁，共六十三頁，2022年，8月28日定理(n,k)線性分組碼最小距離等于dmin的充要條件是：校驗矩陣H的列矢量中至少要有dmin個才能線性相關,而任意（dmin-1)列線性無關。定理

(n,k)線性分組碼的最小距離必定小于等于

(n-k+1) dmin

(n-k+1) 第二十二頁，共六十三頁，2022年，8月28日例：

H＝(7，4)線性碼各列都不相同，任意2列之和不等于0，2列線性無關；某3列線性相關。所以該碼的最小距離為3，小于n-k+1＝4。第二十三頁，共六十三頁，2022年，8月28日（n,k）線性碼最小距離dmin的上邊界是n-k+1。如果我們設計的（n,k）線性碼的dmin達到了n-k+1，就是達到了設計性能的極點。因此，dmin＝n-k+1的碼稱為極大最小距離碼

(MDC–MaximizedminimumDistanceCode)。生成矩陣和校驗矩陣第二十四頁，共六十三頁，2022年，8月28日伴隨式與譯碼

mC=(c1,…,cn)R=(r1,…,rn)

(n,k)信道定義差錯圖案E

E＝(e1,…,en)＝R－C

＝(r1－c1,…,rn－cn)二進制碼中模2加與模2減是等同的，因此有 E=R＋C及 R=C＋E

第二十五頁，共六十三頁，2022年，8月28日伴隨式S的定義因為CHT=0所以RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收碼無誤：必有R＝C即E＝0，則EHT=0RHT=0。如果收碼有誤：即E0，則RHT=EHT0。在HT固定的前提下，RHT僅僅與差錯圖案E有關，而與發(fā)送碼C無關。定義伴隨式S:S=(s1,s2,…,sn-k)=RHT=EHT

第二十六頁，共六十三頁，2022年，8月28日從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。差錯圖案E是n重矢量，共有2n個可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個可能的組合，因此不同的差錯圖案可能有相同的伴隨式。接收端收到R后，因為已知HT，可求出S＝RHT；如果能知道對應的E，則通過C=R＋E而求得C。

RHT=S ?C=R＋ERSEC

只要E正確，譯出的碼也就是正確的。伴隨式S的意義第二十七頁，共六十三頁，2022年，8月28日差錯圖案E的求解(1)

可以通過解線性方程求解E：

S=(s1,s2,…,sn-k)=EHT

=(e1,e2,…,en)得到線性方程組：

sn-k=e1h(n-k)(1)+…+enh(n-k)n

s1=e1h11+…+enh1n

第二十八頁，共六十三頁，2022年，8月28日上述方程組中有n個未知數(shù)e1,e2,…,en

，卻只有n-k個方程，可知方程組有多解。在有理數(shù)或實數(shù)域中，少一個方程就可能導致無限多個解，而在二元域中，少一個方程導致兩個解，少兩個方程四個解，以此類推，少n-(n-k)=k個方程導致每個未知數(shù)有2k個解。因此，由上述方程組解出的E可以有2k個解。到底取哪一個作為附加在收碼R上的差錯圖案E的估值呢？概率譯碼：把所有2k個解的重量(差錯圖案E中1的個數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計算效率不高。第二十九頁，共六十三頁，2022年，8月28日依據(jù)：若BSC信道的差錯概率是p，則長度n的碼中錯誤概率：

0個錯1個錯2個錯…n個錯

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

由于p<<1,>>>>>>…>>

出錯越少的情況，發(fā)生概率越大，E的重量越輕，所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準則，即最大似然譯碼。第三十頁，共六十三頁，2022年，8月28日標準陣列譯碼表

上述的概率譯碼，如每接收一個碼R就要解一次線性方程，那就太麻煩了。好在伴隨式S的數(shù)目是有限的2n-k個，如果n-k不太大，我們可以預先把不同S下的方程組解出來，把各種情況下的最大概率譯碼輸出列成一個碼表。這樣，在實時譯碼時就不必再去解方程，而只要象查字典那樣查一下碼表就可以了。這樣構造的表格叫做標準陣列譯碼表。第三十一頁，共六十三頁，2022年，8月28日表中所列碼字是接收到的碼字R。將沒有任何差錯時的收碼R放在第一行，收碼等于發(fā)碼R=C(CCi,i=0,1,…2k-1),差錯圖案為全零E0=(0,0…0)，伴隨式為全零S0=(0,0…0)。由于有2k個碼字，碼表有2k列。在第2到第n+1的n行中差錯圖案的所有重量為1(共n個)。如果(1+n)<2n-k，再在下面行寫出全部帶有2個差錯的圖案

(共個)。如果總行數(shù)(1+n+)仍然小于2n-k，再列出帶有3個差錯的圖案，以此類推，直到放滿2n-k行，每行一個Ej,對應一個不同的伴隨式Sj。這樣，表的行數(shù)2n-k正好等于伴隨式的數(shù)目。標準陣列譯碼表的構成

第三十二頁，共六十三頁，2022年，8月28日S0E0S1E1

SjEj

E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

標準陣列譯碼表E1+C1

第三十三頁，共六十三頁，2022年，8月28日陪集和子集譯碼表中有2n-k行，每行是一個陪集，每陪集的第一個元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素對應共同的一個伴隨式。第一行陪集的陪集首是全零伴隨式S0所對應的全零差錯圖案E0(無差錯)，而第j行陪集的陪集首是伴隨式Sj所對應的重量最小的差錯圖案Ej(C0=0,Rj=Ej)。定理：在標準陣列中，一個陪集的所有2k個n重有相同的伴隨式，不同的陪集伴隨式互不相同。第三十四頁，共六十三頁，2022年，8月28日譯碼表中有2k列，每列是一個子集，每子集的第一個元素(位于第一行)叫子集頭。同一子集（同一列）中的所有元素對應同一個碼字，第一列子集的子集頭是全零碼字C0，而第i列子集的子集頭是碼字Ci(E0=0,Ri=Ci)。第三十五頁，共六十三頁，2022年，8月28日例

一個(5,2)系統(tǒng)線性碼的生成矩陣是G=設收碼R=(10101)，構造標準陣列譯碼表，譯出發(fā)碼的估值解：(1)構造標準陣列譯碼表。分別以信息組m=(00)、(01)、(10)、(11)及已知的G求得4個許用碼字為C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校驗矩陣：

H=[PTI3]=列出方程組：S=(s1,s2,s3)=

(e1,e2,…,e5)

第三十六頁，共六十三頁，2022年，8月28日伴隨式有2n-k＝23＝8種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有種，已有6種。代表兩個差錯的圖案有種。只需挑選其中的兩個，挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對應的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對應的差錯圖案是2k個即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式(110)所對應的最輕差錯圖案之一是(00110)。譯碼表的構成第三十七頁，共六十三頁，2022年，8月28日S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100標準陣列譯碼表第三十八頁，共六十三頁，2022年，8月28日將接收碼R＝10101譯碼

可選以下三種方法之一譯碼：直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。先求伴隨式RHT=(10101)HT=(010)=S4，確定S4所在行，再沿著行對碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。先求出伴隨式RHT=(010)=S4并確定S4所對應的陪集首（差錯圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。第三十九頁，共六十三頁，2022年，8月28日

對上例作進一步分析，還可以看到，該(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)的漢明距離也是2，為什么不能譯成(00000)呢？事實上，碼表的第7、8行本身就不是唯一的。注意在碼表計算過程中，伴隨式(011)所對應的4個差錯圖案中有兩個并列重量最輕，如果當時選的不是(00011)而是(10100)，那么碼表第7行就不是現(xiàn)在這樣了。對本例題的分析第四十頁，共六十三頁，2022年，8月28日任何一個二元(n,k)線性分組碼都有2n-k個伴隨式，假如該碼的糾錯能力是t，則對于任何一個重量小于等于t的差錯圖案，都應有一個伴隨式與之對應，也就是說，伴隨式的數(shù)目滿足條件上式稱作漢明限，任何一個糾t碼都應滿足上述條件。

完備碼(Perfectcode)第四十一頁，共六十三頁，2022年，8月28日

完備碼

某二元(n,k)線性分組碼能使等式

成立，即該碼的伴隨式數(shù)目不多不少恰好和不大于t個差錯的圖案數(shù)目相等，相當于在標準譯碼陣列中能將所有重量不大于t的差錯圖案選作陪集首，而沒有一個陪集首的重量大于t，這時的校驗位得到最充分的利用。這樣的二元(n,k)線性分組碼稱為完備碼。

第四十二頁，共六十三頁，2022年，8月28日漢明碼(HammingCode)漢明碼不是指一個碼，而是代表一類碼。漢明碼的糾錯能力t=1，既有二進制的，也有非二進制的。二進制時，漢明碼碼長n和信息位k服從以下規(guī)律：

(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整數(shù)。當m＝3、4、5、6、7、8…時，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。漢明碼是完備碼，因為它滿足上述等式。第四十三頁，共六十三頁，2022年，8月28日漢明碼校驗矩陣的構成

漢明碼的校驗矩陣H具有特殊的性質，能使構造方法簡化。一個(n,k)碼的校驗矩陣有n－k行和n列，二進制時n-k個碼元所能組成的列矢量總數(shù)是2n-k-1,恰好和校驗矩陣的列數(shù)n=2m-1相等。只要排列所有列，通過列置換將矩陣H轉換成系統(tǒng)形式，就可以進一步得到相應的生成矩陣G。

第四十四頁，共六十三頁，2022年，8月28日例

構造一個m=3的二元(7，4)漢明碼。解：先利用漢明碼的特性構造一個(7，4)漢明碼的校驗矩陣H，再通過列置換將它變?yōu)橄到y(tǒng)形式：

0001111列置換1110100 H= 0110011 0111010=[PT

I3] 1010101 1101001再得生成矩陣G為

1000101

G=[I4

P]=0100111 0010110 0001011

第四十五頁，共六十三頁，2022年，8月28日1、循環(huán)碼的多項式描述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)碼第四十六頁，共六十三頁，2022年，8月28日(1)循環(huán)碼的性質循環(huán)碼是線性分組碼的一個重要子類；由于循環(huán)碼具有優(yōu)良的代數(shù)結構，使得可用簡單的反饋移位寄存器實現(xiàn)編碼和伴隨式計算，并可使用多種簡單而有效的譯碼方法；循環(huán)碼是研究最深入、理論最成熟、應用最廣泛的一類線性分組碼。第4節(jié)循環(huán)碼第四十七頁，共六十三頁，2022年，8月28日(2)循環(huán)碼的定義循環(huán)碼：如果(n,k)線性分組碼的任意碼矢C=(Cn－1,Cn－2,…,C0)

的i次循環(huán)移位，所得矢量C(i)=(Cn－1－i,Cn－2－i,…,C0,Cn－1,…,Cn－i)

仍是一個碼矢，則稱此線性碼為(n,k)循環(huán)碼。第4節(jié)循環(huán)碼第四十八頁，共六十三頁，2022年，8月28日(3)碼多項式碼多項式：為了運算的方便，將碼矢的各分量作為多項式的系數(shù)，把碼矢表示成多項式，稱為碼多項式。其一般表示式為C(x)=Cn－1xn－1+Cn－2xn－2+…+C0)碼多項式i次循環(huán)移位的表示方法記碼多項式C(x)的一次左移循環(huán)為C(1)(x)

，i次左移循環(huán)為C(i)(x)第4節(jié)循環(huán)碼第四十九頁，共六十三頁，2022年，8月28日碼多項式的模(xn+1)運算0和1兩個元素模2運算下構成域。第4節(jié)循環(huán)碼第五十頁，共六十三頁，2022年，8月28日碼矢C循環(huán)i次所得碼矢的碼多項式

C(x)乘以x，再除以(xn+1)，得第4節(jié)循環(huán)碼第五十一頁，共六十三頁，2022年，8月28日上式表明：碼矢循環(huán)一次的碼多項式C(1)(x)是原碼多項式C(x)乘以x除以(xn+1)的余式。寫作因此，

C(x)的i次循環(huán)移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式，即結論：循環(huán)碼的碼矢的i次循環(huán)移位等效于將碼多項式乘xi后再模(xn+1)。第4節(jié)循環(huán)碼第五十二頁，共六十三頁，2022年，8月28日(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)碼第五十三頁，共六十三頁，2022年，8月28日第4節(jié)循環(huán)碼第五十四頁，共六十三頁，2022年，8月28日循環(huán)碼的生成矩陣在(n,k)循環(huán)碼的2k個碼字中，取前(k－1)位皆為0的碼字g(x)（其次數(shù)r=n－k），再經(jīng)(k－1)次循環(huán)移位，共得到k個碼字:g(x),xg(x),…,xk－1g(x)

這k個碼字顯然是相互獨立的，可作為碼生成矩陣的k行，于是得到循環(huán)碼的生成矩陣G(x)第4節(jié)循環(huán)碼第五十五頁，共六十三頁，2022年，8月28日(2)循環(huán)碼的生成多項式碼的生成矩陣一旦確定，碼就確定了；這就說明：(n,k)循環(huán)碼可由它的一個(n－k)次碼多項式g(x)來確定；所以說g(x)生成了(n,k)循環(huán)碼，因此稱g(x)