信息論與編碼 第6章(2)(糾錯(cuò))

2023/2/51第六章信道編碼2023/2/52問題的提出愿望：信息傳輸多快好省?，F(xiàn)實(shí)：（1）速度：受信道容量的限制，不可能無限大；（2）質(zhì)量：受信道噪聲的干擾，傳輸錯(cuò)誤不可避免。衡量信息傳輸可靠性的指標(biāo)：平均差錯(cuò)率Pe。Pe與信道的統(tǒng)計(jì)特性有關(guān)，不可能為零，有時(shí)甚至很大。降低Pe的方法：先對消息進(jìn)行編碼再送入信道傳送，這種為降低平均差錯(cuò)率而進(jìn)行的編碼稱為信道編碼；在信道輸出端加信道譯碼器進(jìn)行信息還原。香農(nóng)第二編碼定理所給出的結(jié)論：只要信道編碼和譯碼的方法得當(dāng)，就可使平均差錯(cuò)率趨于零。

編碼信道信道編碼器f信道信道譯碼器F2023/2/536.1

有擾離散信道的編碼理論6.2

糾錯(cuò)編譯碼的基本原理與分析方法6.3線性分組碼6.4卷積碼6.5

其它信道編碼內(nèi)容2023/2/546.1有擾離散信道的編碼定理6.1.1差錯(cuò)和差錯(cuò)控制系統(tǒng)分類

6.1.2矢量空間與碼空間

6.1.3隨機(jī)編碼與信道編碼定理2023/2/556.1.1差錯(cuò)和差錯(cuò)控制系統(tǒng)分類差錯(cuò)率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。碼元差錯(cuò)率/符號(hào)差錯(cuò)率指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯(cuò)的碼元數(shù)所占的比例(平均值),簡稱誤碼率(Errorsymbolrate)。是指信號(hào)差錯(cuò)概率比特差錯(cuò)率/比特誤碼率(Errorbitrate)：在傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯(cuò)的比特?cái)?shù)所占比例是指信息差錯(cuò)概率對二進(jìn)制傳輸系統(tǒng),符號(hào)差錯(cuò)等效于比特差錯(cuò);對多進(jìn)制系統(tǒng),一個(gè)符號(hào)差錯(cuò)對應(yīng)多少比特差錯(cuò)卻難以確定2023/2/56為定量地描述信號(hào)的差錯(cuò),定義差錯(cuò)圖樣E:

E=C－R(模M)最常用的二進(jìn)制碼可當(dāng)作特例來研究,其差錯(cuò)圖樣等于收碼與發(fā)碼的模2加,即E=C⊕R

或C=R⊕E設(shè)發(fā)送的碼字C1111111111

接收的碼字R1001001111

差錯(cuò)的圖樣E

0110110000差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。差錯(cuò)圖樣類型隨機(jī)差錯(cuò),突發(fā)差錯(cuò)：差錯(cuò)圖樣2023/2/57糾錯(cuò)碼分類從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼按照對信息序列的處理方法,有分組碼和卷積碼按照碼元與原始信息位的關(guān)系,分為線性碼和非線性碼按照適用的差錯(cuò)類型,分成:糾隨機(jī)差錯(cuò)碼和糾突發(fā)差錯(cuò)碼按照構(gòu)造碼的理論：代數(shù)碼、幾何碼、算術(shù)碼和組合碼。2023/2/58信道編碼的基本思想信道編碼按一定規(guī)則給數(shù)字序列m增加一些多余的碼元,使不具有規(guī)律性的信息序列m變換為具有某種規(guī)律性的數(shù)碼序列C；碼序列中的信息序列碼元與多余碼元之間是相關(guān)的；信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗(yàn)接收到的數(shù)字序列R是否符合既定的

規(guī)則,從而發(fā)現(xiàn)R中是否有錯(cuò),或者糾正其中的差錯(cuò)；根據(jù)相關(guān)性來檢測/發(fā)現(xiàn)和糾正傳輸過程中產(chǎn)生的差錯(cuò)就是信道編碼的基本思想。2023/2/59差錯(cuò)控制系統(tǒng)分類前向糾錯(cuò)(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯(cuò)能力的碼。自動(dòng)請求重發(fā)(ARQ)：發(fā)端發(fā)送檢錯(cuò)碼,如CRC(循環(huán)冗余校驗(yàn)碼)混合糾錯(cuò)(HEC)：是FEC與ARQ方式的結(jié)合。信息反饋(IRQ)：2023/2/5106.1.2矢量空間與碼空間分組碼的一個(gè)碼字可以看作一個(gè)n重矢量，所以可以用矢量空間來分析和理解分組碼。F表示碼元所在的數(shù)域，對于二進(jìn)制碼，F(xiàn)代表二元域{0,1}。設(shè)n重有序元素的集合V={Vi

},

則稱集合V是數(shù)域F上的n維矢量空間，或稱n維線性空間，n維矢量又稱n重(n-tuples)。線性空間的基底、自然基底、子空間、矢量正交、矢量空間正交、對偶空間“重?cái)?shù)”：構(gòu)成矢量的有序元素的個(gè)數(shù)；“維數(shù)”：張成矢量空間基底的個(gè)數(shù)；維數(shù)不可能大于重?cái)?shù)，而當(dāng)維數(shù)小于重?cái)?shù)時(shí)說明這是個(gè)子空間。2023/2/511碼空間和分組編碼的任務(wù)

消息k長 (n,k)碼字n長

qk

種分組編碼器qn種

k維k重矢量n維n重矢量

通常qn>>qk，分組編碼的任務(wù)是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個(gè)構(gòu)成一個(gè)碼空間，其元素就是許用碼的碼集。選擇一個(gè)ｋ維n重子空間作為碼空間。確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構(gòu)成了不同的分組碼。2023/2/5126.1.3隨機(jī)編碼與信道編碼定理

如果不考慮編碼的具體方法，而是運(yùn)用概率統(tǒng)計(jì)的方法在特定信道條件下對編碼信號(hào)的性能作出統(tǒng)計(jì)分析，求出差錯(cuò)概率的上，下限邊界，其中最優(yōu)碼所能達(dá)到的差錯(cuò)概率上界稱為隨機(jī)碼界。隨機(jī)編碼的含義2023/2/513錯(cuò)誤概率的上界對于離散無記憶信道（DMC）。錯(cuò)誤平均概率的上界為：E(R)為可靠性函數(shù)，也叫誤差指數(shù)碼率：R=(lbM)

/N

M是可能的信息組合數(shù)，M=qKN是每碼字的碼元數(shù)，R表示每碼元攜帶的信息量，單位是每符號(hào)比特（bit/symbol）是全部碼集的平均差錯(cuò)概率2023/2/514正定理：只要傳信率R小于信道容量C，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯(cuò)概率實(shí)現(xiàn)可靠的通信。逆定理：信道容量C是可靠通信系統(tǒng)傳信率R的上邊界，如果R>C，就不可能有任何一種編碼能使差錯(cuò)概率任意小。上述兩定理統(tǒng)稱為有擾或噪聲信道的信道編碼定理信道編碼定理2023/2/5156.2糾錯(cuò)編譯碼的基本原理與分析方法6.2.1糾錯(cuò)編碼的基本原理6.2.2譯碼方法---最優(yōu)譯碼和最大似然譯碼2023/2/5166.2.1糾錯(cuò)編碼的基本原理6.2.1糾錯(cuò)編碼的基本思想一、從編碼定理出發(fā)討論糾錯(cuò)碼的基本原理：從上面的公式可以看出：要減小Pe：（1）增大N;（2）增大Er(R)；1增大信道容量C（1）擴(kuò)展帶寬。（2）加大功率。（3）減小噪聲功率。2減小碼率R(=KlbQ/N)增大碼長NC,R,K/N不變2023/2/517二、從冗余度和噪聲均化討論糾錯(cuò)碼的基本原理：冗余度：就是在信息流中插入冗余比特，插入的冗余比特與信息比特存在著特定的相關(guān)性。這樣如果在傳輸過程中有個(gè)別信息比特受損，也可以從冗余比特中恢復(fù)或發(fā)現(xiàn)受損比特。從而保證了信息傳輸?shù)目煽啃浴鬏斎哂啾忍乇厝灰獎(jiǎng)佑萌哂嗟馁Y源:

時(shí)間,頻帶,功率,設(shè)備復(fù)雜度噪聲均勻化：就是讓差錯(cuò)隨機(jī)化，以便符合編碼定理的條件從而得到符合編碼定理結(jié)果。其基本思想是設(shè)法將危害較大的，較為集中的噪聲干擾分?jǐn)傞_來，使不可恢復(fù)的信息損傷最小。（1）增加碼長。（2）卷積。（3）交織。2023/2/518譯碼算法的已知條件是要求已知：（1）實(shí)際接收到的碼字序列{r},r=(r1,r2,…..rN)。（2）發(fā)送端所采用的編碼算法和該算法產(chǎn)生的碼集XN,滿足（3）信道模型及信道參數(shù)。消息組m(N,K)編碼器信道最佳/最大似然譯碼消息還原6.2.2譯碼方法---最優(yōu)譯碼和最大似然譯碼2023/2/519

譯碼規(guī)則與錯(cuò)誤概率信道編碼是一個(gè)一一對應(yīng)的變換或函數(shù)，稱為編碼函數(shù)f；信道譯碼也是一個(gè)函數(shù)，稱為譯碼函數(shù)F。編碼信道信道編碼器f信道信道譯碼器F

由于

是一一對應(yīng)變換，其反變換

唯一確定。因此，討論譯碼函數(shù)時(shí)，只考慮從中還原出就可以了。平均差錯(cuò)率Pe與譯碼規(guī)則F有關(guān)。2023/2/520兩種典型的譯碼規(guī)則兩種典型的譯碼規(guī)則：最佳譯碼規(guī)則、極大似然譯碼規(guī)則

1、最佳譯碼規(guī)則：平均差錯(cuò)率最小的譯碼規(guī)則。DMC信道譯碼F

按“后驗(yàn)概率最大”原則定出，又稱最大后驗(yàn)概率譯碼規(guī)則

按“聯(lián)合概率最大”原則定出，又稱最大聯(lián)合概率譯碼規(guī)則

2023/2/5212、極大似然譯碼規(guī)則

按“轉(zhuǎn)移概率最大”原則定出，稱為極大似然譯碼規(guī)則。實(shí)際應(yīng)用中，經(jīng)常只知道信道的統(tǒng)計(jì)特性(轉(zhuǎn)移概率)，而不知道信源的統(tǒng)計(jì)特性(輸入概率)，這時(shí)求不出聯(lián)合概率和后驗(yàn)概率，因此無法確定最佳譯碼規(guī)則。既然只知道轉(zhuǎn)移概率，就只能按轉(zhuǎn)移概率的某種約束條件制訂譯碼規(guī)則。按最大轉(zhuǎn)移概率條件來確定的譯碼規(guī)則，稱為極大似然譯碼規(guī)則。2023/2/522極大似然譯碼規(guī)則與最佳譯碼規(guī)則等價(jià)的條件極大似然譯碼規(guī)則最佳譯碼規(guī)則結(jié)論：信道輸入等概時(shí)，極大似然譯碼規(guī)則與最佳譯碼規(guī)則等價(jià)。證明：

輸入等概（1）信道輸入是近似等概的：因?yàn)樾诺狼凹?jí)有信源編碼器存在。（2）極大似然譯碼規(guī)則近似最佳，可以放心使用。

注：2023/2/523最佳譯碼，也叫最大后驗(yàn)概率譯碼(MAP)最大似然譯碼(MLD)

消息組mi

碼字ci

接收碼r

估值

消息信道消息還原編碼器譯碼2023/2/524碼字的似然函數(shù)為了方便計(jì)算，可以利用對數(shù)運(yùn)算將乘法運(yùn)算轉(zhuǎn)化為加法運(yùn)算。即：2023/2/525BSC信道2023/2/526漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對稱的，只要發(fā)送的碼字獨(dú)立、等概，漢明距離譯碼也就是最佳譯碼。最大似然譯碼等效于最小漢明距離譯碼。2023/2/5276.3線性分組碼6.3.1線性分組碼的生成矩陣和校驗(yàn)矩陣6.3.2伴隨式與標(biāo)準(zhǔn)陣列譯碼6.3.3碼距,糾錯(cuò)能力,MDC碼等6.3.4完備碼,循環(huán)碼,BCH和RS碼6.3.5分組碼的擴(kuò)展,縮短和CRC2023/2/5286.3線性分組碼(n,k)分組碼是把信息流分割成一串前后獨(dú)立的k比特信息組，再將每組信息元映射成n個(gè)碼元組成的碼字。如下圖：m0m1m2……mk-1m0m1m2…..mk-1m0m1m2……mk-1….

C0C1C3………...Cn-1C0C1C3……....Cn-1C0C1C3………....Cn-1K個(gè)信息元可以寫成矢量(mk-1,….m1,m0)或者矩陣的形式[mk-1,….m1,m0]。同樣碼字可以表示為(Cn-1,….C1,C0)或者[Cn-1,….C1,C0].(碼矢,碼字,碼組)2023/2/529線性分組碼中，必須考慮的問題：（1）碼集C能否構(gòu)成n維n重矢量空間的一個(gè)k維n重子空間。（2）如何尋找最佳的碼空間。（3）qk個(gè)信息元組以怎樣的算法一一映射到碼空間。碼率對于二元分組碼(n,k),其碼率定義為：RC=k/n對于q元分組碼(n,k),其碼率定義為：RC=klbq/n

消息m (n,k)碼字c

m=(mk-1,…,m1,m0)分組編碼器c=(cn-1,…,c1,c0)

qk<qn2023/2/5306.3.1 生成矩陣和校驗(yàn)矩陣

線性分組碼的碼空間C

是由k

個(gè)線性無關(guān)的基底

gk-1,，．．．g1，g0

張成的k維n重子空間，所有碼字都可寫成k個(gè)基底的線性組合，即 c=

mk-1

gk-1+…+

m1

g1+m0g02023/2/531生成矩陣

當(dāng)信息元確定后，碼字僅由G矩陣決定，因此我們稱這k×n

矩陣G為該(n,k)線性分組碼的生成矩陣。如果已知線性分組碼的生成矩陣，則任何一個(gè)k位信息組對應(yīng)的碼字都可以由mG運(yùn)算得到。

2023/2/532生成矩陣G(k×n)的特點(diǎn)想要保證(n,k)線性分組碼能夠構(gòu)成k維n重子空間，G的k個(gè)行矢量gk-1,…,g1,g0必須是線性無關(guān)的，只有這樣才符合作為基底的條件。由于k個(gè)基底即G的k個(gè)行矢量線性無關(guān)，矩陣G的秩一定等于k。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個(gè)因素，碼集一樣而映射方法不同也不能說是同樣的碼。2023/2/533例如2023/2/534系統(tǒng)形式的生成矩陣(n,k)碼的任何生成矩陣都可以通過行運(yùn)算（不改變碼集，只改變映射規(guī)則）簡化成“系統(tǒng)形式”。G=[Ik

P]=Ik是k×k單位矩陣，P是k×(n-k)矩陣。2023/2/535復(fù)習(xí)：定義

下面三種變換稱為矩陣的初等行變換：1．

互換兩行；2．

以數(shù)k

乘以某一行；3．

把某一行的k倍加到另一行上。若將定義中的“行”換成“列”，則稱之為初等列變換，初等行變換和初等列變換統(tǒng)稱為初等變換。2023/2/536系統(tǒng)碼前k位由單位矩陣Ik決定，等于把信息組m原封不動(dòng)搬到碼字的前k位；

mG=m[Ik

P]=[mIk

mP]=[mmP]其余的n-k位叫冗余位或一致校驗(yàn)位，是前k個(gè)信息位的線性組合。這樣生成的（n,k）碼叫做系統(tǒng)碼。若生成矩陣G不具備系統(tǒng)形式，則生成的碼叫做非系統(tǒng)碼。系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。2023/2/537由上面的生成矩陣生成的碼字的特點(diǎn)：特點(diǎn)：碼字的前面k位就是信息組中的k位，而后面的校驗(yàn)位為信息組的線性組合。2023/2/538空間構(gòu)成n維n重空間有相互正交的n個(gè)基底選擇k個(gè)基底構(gòu)成碼空間C選擇另外的(n-k)個(gè)基底構(gòu)成空間DC和D是對偶的

n維n重空間V

k維k重k維n重n-k維信息組碼空間n重D

空間m

C

H

G2023/2/539校驗(yàn)矩陣將D空間的n-k個(gè)基底排列起來可構(gòu)成一個(gè)(n-k)×n矩陣，稱為校驗(yàn)矩陣H，也稱監(jiān)督矩陣。用來校驗(yàn)接收到的碼字是否是正確的；即：若c為碼空間C中的任意碼字，則若不滿足此等式，則c必定不是碼空間C中的碼字。2023/2/5402023/2/5412023/2/5422023/2/543校驗(yàn)矩陣G是(n,k)碼的生成矩陣，H是它的校驗(yàn)矩陣；H是(n,n-k)對偶碼的生成矩陣，它的每一行是對偶碼的一個(gè)碼字。G則是它的校驗(yàn)矩陣。GHT=0，H＝[－

PTIn-k]，二進(jìn)制時(shí)，負(fù)號(hào)可省略。2023/2/544校驗(yàn)矩陣與生成矩陣的關(guān)系如果系統(tǒng)碼的生成矩陣為G=[IK|P],則其對應(yīng)的校驗(yàn)矩陣為H=[-PT|In-k]GHT=0或者HGT=02023/2/545例6-2

某線性分組碼，其生成矩陣是

G=求：(1)計(jì)算碼集，列出信息組與碼字的映射關(guān)系。(2)將該碼系統(tǒng)化處理后，計(jì)算系統(tǒng)碼碼集并列出映射關(guān)系。(3)計(jì)算系統(tǒng)碼的校驗(yàn)矩陣H。若收碼r=[100110],檢驗(yàn)它是否碼字？

(4)根據(jù)系統(tǒng)碼生成矩陣畫出編碼器電原理圖。

111010①110001②011101③2023/2/546例6-2碼集與映射關(guān)系信息碼字系統(tǒng)碼字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010做初等行變換2023/2/547例6-2二元(6,3)線性分組碼編碼器m0

m1

m2

輸入 輸出

c0

c1

c22023/2/548下面是某線性二元碼的全部碼字：

。⑴求n,k的值；⑵構(gòu)造這碼的生成矩陣G；(找3個(gè)線性無關(guān)的碼字構(gòu)成G,并化為系統(tǒng)形式)⑶構(gòu)成這碼的一致校驗(yàn)矩陣H。

2023/2/5496.3.2伴隨式與標(biāo)準(zhǔn)陣列譯碼mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)

(n,k)信道定義差錯(cuò)圖案EE＝(en－1,…,e1,e0)＝R－C

＝(rn-1－cn-1,…,r1－c1,r0－c0)二進(jìn)制碼中模2加與模2減是等同的，因此有 E=R＋C及 R=C＋E 2023/2/550伴隨式S的定義因?yàn)镃HT=0所以RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收碼無誤：必有R＝C即E＝0，則EHT=0RHT=0。如果收碼有誤：即E0，則RHT=EHT0。在HT固定的前提下，RHT僅僅與差錯(cuò)圖案E有關(guān)，而與發(fā)送碼C無關(guān)。定義伴隨式SS=(sn-k-1,…,s1,s0)=RHT=EHT

2023/2/551從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。差錯(cuò)圖案E是n重矢量，共有2n個(gè)可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個(gè)可能的組合，因此不同的差錯(cuò)圖案可能有相同的伴隨式。接收端收到R后，因?yàn)橐阎狧T，可求出S＝RHT；如果能知道對應(yīng)的E，則通過C=R＋E而求得C。

RHT=S ?C=R＋ERSEC

只要E正確，譯出的碼也就是正確的。伴隨式S的意義2023/2/552譯碼過程框圖

(R=B)2023/2/553例

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

H=[PTI3]=2023/2/554列出方程組：由RHT確定S后，對應(yīng)的E可以有2k(22=4)個(gè)解，究竟取哪一個(gè)作為差錯(cuò)圖樣E的解?最簡單明了的處理方法是概率譯碼，即對所有2k個(gè)解的重量(差錯(cuò)圖樣E中1的個(gè)數(shù))進(jìn)行比較，選擇重量最小的作為E的估值。由于E=R+C，E重量最小，就是R和C的漢明距離最小。2023/2/555依據(jù)：若BSC信道的差錯(cuò)概率是p，則長度n的碼中錯(cuò)誤概率

0個(gè)錯(cuò)1個(gè)錯(cuò)2個(gè)錯(cuò)…n個(gè)錯(cuò)概率

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

由于p<<1,則(1-p)n>>p(1-p)n-1>>p2(1-p)n-2>>…>>

pn

出錯(cuò)越少的情況，發(fā)生概率越大，E的重量越輕，所以該譯碼方法實(shí)際上體現(xiàn)了最小距離譯碼準(zhǔn)則，即最大似然譯碼。顯然，在進(jìn)行概率譯碼時(shí)，每接收一個(gè)碼字就要解一次線性方程，非常復(fù)雜麻煩。但如果n－k不太大，我們可以預(yù)先把不同校正子S情況下的所有方程組都預(yù)先解出來，將各種情況下的最大概率譯碼輸出列成一個(gè)標(biāo)準(zhǔn)陣列譯碼表。這樣，在實(shí)際譯碼時(shí)就不必解方程，只要查譯碼表就可以了。2023/2/556伴隨式有2n-k＝23＝8種組合，差錯(cuò)圖案中代表無差錯(cuò)的有一種，代表一個(gè)差錯(cuò)的圖案有種，已有6種。代表兩個(gè)差錯(cuò)的圖案有種。只需挑選其中的兩個(gè)，挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對應(yīng)的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對應(yīng)的差錯(cuò)圖案是2k個(gè)即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個(gè)如(00011)。同樣可得伴隨式(110)所對應(yīng)的最輕差錯(cuò)圖案之一是(00110)。例6-3譯碼表的構(gòu)成2023/2/557S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例6-3標(biāo)準(zhǔn)陣列譯碼表2023/2/558例6-3將接收碼R＝10101譯碼可選以下三種方法之一譯碼：直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。先求伴隨式RHT=(10101)HT=(010)=S4，確定S4所在行，再沿著行對碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。先求出伴隨式RHT=(010)=S4并確定S4所對應(yīng)的陪集首（差錯(cuò)圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。2023/2/559差錯(cuò)圖案E的求解(1)

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

S=(sn-k-1,…,s1,s0)=EHT

=(en-1,…e1,e0)得到線性方程組：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h002023/2/560上述方程組中有n個(gè)未知數(shù)en－1,…e1,e0

，卻只有n-k個(gè)方程，可知方程組有多解。在有理數(shù)或?qū)崝?shù)域中，少一個(gè)方程就可能導(dǎo)致無限多個(gè)解，而在二元域中，少一個(gè)方程導(dǎo)致兩個(gè)解，少兩個(gè)方程四個(gè)解，以此類推，少n-(n-k)=k個(gè)方程導(dǎo)致這組未知數(shù)有2k組解。概率譯碼：把所有2k個(gè)解的重量(差錯(cuò)圖案E中1的個(gè)數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計(jì)算效率不高。差錯(cuò)圖案E的求解(2)

2023/2/561標(biāo)準(zhǔn)陣列譯碼表

在伴隨式S的數(shù)目是有限的2n-k個(gè)，如果n-k不太大，我們可以預(yù)先把不同S下的方程組解出來，把各種情況下的最大概率譯碼輸出列成一個(gè)碼表。這樣，在實(shí)時(shí)譯碼時(shí)就不必再去解方程，而只要象查字典那樣查一下碼表就可以了。這樣構(gòu)造的表格叫做標(biāo)準(zhǔn)陣列譯碼表。表中所列碼字是接收到的碼字R；將沒有任何差錯(cuò)時(shí)的收碼R放在第一行，收碼等于發(fā)碼R=C(CCi,i=0,1,…2k-1),差錯(cuò)圖案為全零E0=(0,0…0)，伴隨式為全零S0=(0,0…0)。由于有2k個(gè)碼字，碼表有2k列。2023/2/562在第2到第n+1的n行中差錯(cuò)圖案的所有重量為1(共n個(gè))。如果(1+n)<2n-k，再在下面行寫出全部帶有2個(gè)差錯(cuò)的圖案(共個(gè))。標(biāo)準(zhǔn)陣列譯碼表的構(gòu)成

如果總行數(shù)(1+n+)仍然小于2n-k，再列出帶有3個(gè)差錯(cuò)的圖案，以此類推，直到放滿2n-k行，每行一個(gè)Ej,對應(yīng)一個(gè)不同的伴隨式Sj。這樣，表的行數(shù)2n-k正好等于伴隨式的數(shù)目。2023/2/563S0E0S1E1

SjEj

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

E1+CiEj+C0=EjEj+C1Ej+Ci

標(biāo)準(zhǔn)陣列譯碼表

E1+C1

2023/2/564

在制定標(biāo)準(zhǔn)陣列譯碼表的過程中，由S決定差錯(cuò)圖案E時(shí)只有前6行真正體現(xiàn)了最大似然譯碼準(zhǔn)則，而第7、8行的差錯(cuò)圖案選擇不是唯一的。比如第7行可有(00011)和(10100)兩個(gè)選擇，如果當(dāng)時(shí)選的不是(00011)而是(10100)，那么碼表第7行就不是現(xiàn)在這樣了。那么在譯碼時(shí)最后的結(jié)果也就不一樣了。為什么會(huì)出現(xiàn)這種情況呢？伴隨式的個(gè)數(shù)2n-k與n、k及糾錯(cuò)能力t

有一定的數(shù)量關(guān)系。對例6-3的分析2023/2/5656.3.3碼距、糾錯(cuò)能力、MDC碼及重量譜

N重碼矢c=(cn-1,cn-2,…c1,c0)可與N維矢量空間XN中的一個(gè)點(diǎn)對應(yīng)，全體碼字所對應(yīng)的點(diǎn)構(gòu)成矢量空間里的一個(gè)子集發(fā)碼一定在這個(gè)子集里，傳輸無誤時(shí)的收碼也一定位于該子集當(dāng)出現(xiàn)差錯(cuò)時(shí)，接收的N重矢量:對應(yīng)到子集外空間某一點(diǎn)

對應(yīng)到該子集，卻對應(yīng)到該子集的另一點(diǎn)上

2023/2/566td=7dmin=3d=5C1C2C3C4C5碼集各碼字間的距離是不同的，碼距最小者決定碼的特性，稱之為最小距離dmin這里dmin=3，糾錯(cuò)能力是1，檢錯(cuò)能力是2碼距2023/2/567定理6.1

任何最小距離dmin的線性分組碼，其檢錯(cuò)能力為（dmin-1）,糾錯(cuò)能力t為最小距離dmin表明碼集中各碼字差異的程度，差異越大越容易區(qū)分，抗干擾能力就越強(qiáng)，是衡量分組碼性能的最重要的指標(biāo)之一。定理6.2

線性分組碼的最小距離等于碼集中非零碼字的最小重量

dmin=min{w(Ci)} CiC及Ci

0 糾錯(cuò)能力2023/2/568定理6.3(n,k)線性分組碼最小距離等于dmin的充要條件是：校驗(yàn)矩陣H中有（dmin-1)列線性無關(guān)。定理6.4(n,k)線性分組碼的最小距離必定小于等于

(n-k+1),即

dmin

(n-k+1) 糾錯(cuò)能力

糾錯(cuò)能力

定理6.3（應(yīng)為）：

對于(n,k)線性分組碼：校驗(yàn)矩陣H中的任意t列線性無關(guān)而t+1列線性相關(guān)，則碼的最小距離dmin或碼字的最小重量為t+1.反之，若碼字的最小重量或碼的最小距離為t+1則H的任意t列線性無關(guān)而t+1列線性相關(guān)。見《信息論基礎(chǔ)教程》，李亦農(nóng)，李梅編著，北京郵電大學(xué)出版社。P1592023/2/5692023/2/570例：

H＝(7，4)線性碼各列都不相同，任意2列之和不等于0，2列線性無關(guān)；任意2列之和一定等于矩陣中某一列，任意3列線性相關(guān)。所以該碼的最小距離為3，小于n-k+1＝4。糾錯(cuò)能力

2023/2/571(2)為糾正t個(gè)錯(cuò)碼，要求最小碼距(1)為檢測e個(gè)錯(cuò)碼，要求最小碼距最小碼距與檢錯(cuò)能力圖示(3)為糾正t個(gè)錯(cuò)碼，同時(shí)檢測e個(gè)錯(cuò)碼，要求最小碼距(e>t)2023/2/572（n,k）線性碼最小距離dmin的上邊界是n-k+1。如果我們設(shè)計(jì)的（n,k）線性碼的dmin達(dá)到了n-k+1，就是達(dá)到了設(shè)計(jì)性能的極點(diǎn)。因此，dmin＝n-k+1的碼稱為極大最小距離碼

(MDC–MaximizedminimumDistanceCode)。

(1)二進(jìn)制碼中，除了將一位信息重復(fù)n次的（n,1）碼外，不存在其它二進(jìn)制MDC碼；

(2)非二進(jìn)制碼中，MDC碼是存在的，如RS碼（reed-solomon)。MDC碼（MaximizedminimumDistanceCode）2