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

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

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

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

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

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

6.1.2矢量空間與碼空間

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

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

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

接收的碼字R1001001111

差錯的圖樣E

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

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

},

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

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

qk

種分組編碼器qn種

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

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

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

/N

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

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

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

由于

是一一對應變換，其反變換

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

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

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

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

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

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

輸入等概（1）信道輸入是近似等概的：因為信道前級有信源編碼器存在。（2）極大似然譯碼規(guī)則近似最佳，可以放心使用。

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

消息組mi

碼字ci

接收碼r

估值

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

C0C1C3………...Cn-1C0C1C3……....Cn-1C0C1C3………....Cn-1K個信息元可以寫成矢量(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重矢量空間的一個k維n重子空間。（2）如何尋找最佳的碼空間。（3）qk個信息元組以怎樣的算法一一映射到碼空間。碼率對于二元分組碼(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 生成矩陣和校驗矩陣

線性分組碼的碼空間C

是由k

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

gk-1,，．．．g1，g0

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

mk-1

gk-1+…+

m1

g1+m0g02023/2/531生成矩陣

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

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

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

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

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

互換兩行；2．

以數(shù)k

乘以某一行；3．

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

mG=m[Ik

P]=[mIk

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

n維n重空間V

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

空間m

C

H

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

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

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

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

(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個線性無關(guān)的碼字構(gòu)成G,并化為系統(tǒng)形式)⑶構(gòu)成這碼的一致校驗矩陣H。

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

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

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

2023/2/551從物理意義上看，伴隨式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的意義2023/2/552譯碼過程框圖

(R=B)2023/2/553例

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

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

0個錯1個錯2個錯…n個錯概率

(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

出錯越少的情況，發(fā)生概率越大，E的重量越輕，所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準則，即最大似然譯碼。顯然，在進行概率譯碼時，每接收一個碼字就要解一次線性方程，非常復雜麻煩。但如果n－k不太大，我們可以預先把不同校正子S情況下的所有方程組都預先解出來，將各種情況下的最大概率譯碼輸出列成一個標準陣列譯碼表。這樣，在實際譯碼時就不必解方程，只要查譯碼表就可以了。2023/2/556伴隨式有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)。例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標準陣列譯碼表2023/2/558例6-3將接收碼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)。2023/2/559差錯圖案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個未知數(shù)en－1,…e1,e0

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

2023/2/561標準陣列譯碼表

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

如果總行數(shù)(1+n+)仍然小于2n-k，再列出帶有3個差錯的圖案，以此類推，直到放滿2n-k行，每行一個Ej,對應一個不同的伴隨式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

標準陣列譯碼表

E1+C1

2023/2/564

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

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

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

對應到該子集，卻對應到該子集的另一點上

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

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

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

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

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

(n-k+1),即

dmin

(n-k+1) 糾錯能力

糾錯能力

定理6.3（應為）：

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

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

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

(MDC–MaximizedminimumDistanceCode)。

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

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