信息論-第7章抗干擾信道編碼

1、1信道編碼是以信息在信道上的正確傳輸為目標(biāo)的編碼，可分為兩個層次上的問題： 如何正確接收載有信息的信號線路編碼 如何避免少量差錯信號對信息內(nèi)容的影響糾錯編碼第第7 7章章 抗干擾信道編碼抗干擾信道編碼2 從功能角度：檢錯碼 、糾錯碼 對信息序列的處理方法：分組碼、卷積碼 碼元與原始信息位的關(guān)系：線性碼、非線性碼 差錯類型：糾隨機(jī)差錯碼、糾突發(fā)差錯碼、介于中間的糾隨機(jī)/突發(fā)差錯碼。 構(gòu)碼理論：代數(shù)碼、幾何碼、算術(shù)碼、組合碼等 糾錯碼分類 3差錯控制系統(tǒng)分類 前向糾錯（FEC）：發(fā)端信息經(jīng)糾錯編碼后傳送，收端通過糾錯譯碼自動糾正傳遞過程中的差錯 反饋重發(fā)（ARQ）：收端通過檢測接收碼是否符合編碼規(guī)

2、律來判斷，如判定碼組有錯，則通過反向信道通知發(fā)端重發(fā)該碼 混合糾錯（HEC）：前向糾錯和反饋重發(fā)的結(jié)合，發(fā)端發(fā)送的碼兼有檢錯和糾錯兩種能力 4第第7 7章章 抗干擾信道編碼抗干擾信道編碼 通信的有效性問題：通信的有效性問題：即如何通過對即如何通過對信源信源進(jìn)行進(jìn)行編碼編碼，壓縮信源的多余度，提高傳輸?shù)男?。壓縮信源的多余度，提高傳輸?shù)男省?通信的可靠性問題：通信的可靠性問題：即消息通過即消息通過信道信道傳輸時如何傳輸時如何選擇選擇編碼編碼方案以減少差錯。方案以減少差錯。 通信的可靠性顯然與通信的可靠性顯然與信道的統(tǒng)計特性信道的統(tǒng)計特性有關(guān)，因為有關(guān)，因為雜噪干擾是造成錯誤的主要因素。其次，雜

3、噪干擾是造成錯誤的主要因素。其次，編碼方編碼方法和譯碼方法法和譯碼方法也將影響信息傳輸?shù)目煽啃?。也將影響信息傳輸?shù)目煽啃浴?信道是通信系統(tǒng)中的重要組成部分，信道的任務(wù)是以信信道是通信系統(tǒng)中的重要組成部分，信道的任務(wù)是以信號方式傳輸信息。號方式傳輸信息。信道的輸入端和輸出端連接著編碼器和譯碼器，形成了信道的輸入端和輸出端連接著編碼器和譯碼器，形成了一個新的信道，即一個新的信道，即編碼信道。編碼信道。信道的特征是由信道傳遞概率信道的特征是由信道傳遞概率p(y|x)來描述的。由此可來描述的。由此可以算出它的信道容量以算出它的信道容量C，只要在信道中實際傳送的信息，只要在信道中實際傳送的信息率率RC，

4、在接收端就應(yīng)當(dāng)能夠無差錯地譯出發(fā)端所輸，在接收端就應(yīng)當(dāng)能夠無差錯地譯出發(fā)端所輸送的信息。送的信息。第第7 7章章 抗干擾信道編碼抗干擾信道編碼6 通過信道編碼實現(xiàn)信源與信道相匹配。通過信道編碼實現(xiàn)信源與信道相匹配。 信道編碼的編碼對象是信源編碼器輸出的數(shù)字序信道編碼的編碼對象是信源編碼器輸出的數(shù)字序列列M，又稱為信息序列。通常是由二元符號，又稱為信息序列。通常是由二元符號0,1構(gòu)構(gòu)成的序列，而且成的序列，而且0和和1是獨(dú)立等概的。是獨(dú)立等概的。 信道編碼是按一定的規(guī)則給數(shù)字序列信道編碼是按一定的規(guī)則給數(shù)字序列M增加一些增加一些多余的碼元，使不具有規(guī)律性的信息序列多余的碼元，使不具有規(guī)律性的信息

5、序列M變換變換為為具有某種規(guī)律性具有某種規(guī)律性的數(shù)字序列的數(shù)字序列C，又稱為碼序列。，又稱為碼序列。 碼序列中信息序列的諸碼元與碼序列中信息序列的諸碼元與多余碼元多余碼元之間是相之間是相關(guān)的。關(guān)的。第第7 7章章 抗干擾信道編碼抗干擾信道編碼7 在接收端，信道譯碼器利用這種在接收端，信道譯碼器利用這種預(yù)知的編碼規(guī)預(yù)知的編碼規(guī)則則來譯碼，或者說檢驗接收到的數(shù)字序列來譯碼，或者說檢驗接收到的數(shù)字序列R中中 是否有錯，或者糾正其中的差錯。是否有錯，或者糾正其中的差錯。 信道編碼的基本思想是根據(jù)相關(guān)性來檢測和糾信道編碼的基本思想是根據(jù)相關(guān)性來檢測和糾正傳輸過程中產(chǎn)生的差錯。正傳輸過程中產(chǎn)生的差錯。 在

6、有噪信道中傳輸消息是會發(fā)生錯誤的，在有噪信道中傳輸消息是會發(fā)生錯誤的，錯誤錯誤概率和信道的統(tǒng)計特性、譯碼過程及譯碼規(guī)則概率和信道的統(tǒng)計特性、譯碼過程及譯碼規(guī)則有關(guān)。有關(guān)。第第7 7章章 抗干擾信道編碼抗干擾信道編碼8第第7 7章章 抗干擾信道編碼抗干擾信道編碼9第第7 7章章 抗干擾信道編碼抗干擾信道編碼內(nèi)容提要內(nèi)容提要 7.1 .1 譯碼規(guī)則譯碼規(guī)則 7.2 7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則 7.3 7.3 信道編碼的編碼原則信道編碼的編碼原則 7.4 7.4 抗干擾信道編碼定理抗干擾信道編碼定理 7.5 7.5 分組碼及其檢糾能力分組碼及其檢糾能力 7.7 7.7 線性分組碼及

7、其生成矩陣線性分組碼及其生成矩陣 7.8 7.8 一致檢驗矩陣與伴隨式一致檢驗矩陣與伴隨式 7.9 7.9 標(biāo)準(zhǔn)陣列與譯碼表標(biāo)準(zhǔn)陣列與譯碼表 7.10 7.10 檢糾能力與一致檢驗矩陣的關(guān)系檢糾能力與一致檢驗矩陣的關(guān)系 7.11 7.11 完備碼完備碼 7.12 7.12 漢明碼與擴(kuò)展?jié)h明碼漢明碼與擴(kuò)展?jié)h明碼 107.1 譯碼規(guī)則譯碼規(guī)則 錯誤概率與信道統(tǒng)計特征有關(guān)。例如在二錯誤概率與信道統(tǒng)計特征有關(guān)。例如在二元對稱信道中元對稱信道中 單個符號的單個符號的錯誤傳遞概率是錯誤傳遞概率是p 單個符號的單個符號的正確傳遞概率是正確傳遞概率是1-p 錯誤概率與譯碼過程和譯碼規(guī)則的關(guān)系也錯誤概率與譯碼過

8、程和譯碼規(guī)則的關(guān)系也很大。很大。117.1 譯碼規(guī)則譯碼規(guī)則 例例7.1 設(shè)有一個二元對稱信道，如下圖所示，其輸入符號為設(shè)有一個二元對稱信道，如下圖所示，其輸入符號為等概分布。等概分布。 1-p=0.1 1-p p=0.9 p X a1=0 0 a2=1 1=b2 Y 0=b1 結(jié)論：錯誤概率既與信道的統(tǒng)計特性有關(guān)，也與譯碼規(guī)則有關(guān)。結(jié)論：錯誤概率既與信道的統(tǒng)計特性有關(guān)，也與譯碼規(guī)則有關(guān)。在信道輸出端，如果規(guī)定：在信道輸出端，如果規(guī)定：接收到符號接收到符號0時，譯碼器把它譯成時，譯碼器把它譯成0；接收到符號接收到符號1時，譯碼器把它譯成時，譯碼器把它譯成1；譯碼錯誤概率譯碼錯誤概率PE=0.9

9、。反之，如果：反之，如果：接收到符號接收到符號0時，譯碼器把它譯成時，譯碼器把它譯成1；接收到符號接收到符號1時，譯碼器把它譯成時，譯碼器把它譯成0；譯碼錯誤概率譯碼錯誤概率PE=0.1。12 定義定義7.1 設(shè)信道輸入符號集為設(shè)信道輸入符號集為X=(xi，i=1,2 ,r)，輸出符號集為輸出符號集為Y=(yj，j=l,2,s)，若對每一個輸出，若對每一個輸出符號符號yj都有一個確定的函數(shù)都有一個確定的函數(shù)F(yj)，使，使yj對應(yīng)于唯一的對應(yīng)于唯一的一個輸入符號一個輸入符號xi，則稱這樣的函數(shù)為譯碼規(guī)則，即，則稱這樣的函數(shù)為譯碼規(guī)則，即 F(yj)=xi i=1,2 ,r和和 jl,2,s

10、顯然，對于有顯然，對于有r個輸入、個輸入、s個輸出的信道而言，按個輸出的信道而言，按上述定義得到的譯碼規(guī)則共有上述定義得到的譯碼規(guī)則共有rs 種。種。7.1 譯碼規(guī)則譯碼規(guī)則13 7.1 譯碼規(guī)則譯碼規(guī)則例例 7.2 設(shè)有一信道，其信道矩陣為設(shè)有一信道，其信道矩陣為 由于由于r3，s3，s個輸出符號中的每一個個輸出符號中的每一個都可以譯成都可以譯成 r 個輸入符號中的任何一個，個輸入符號中的任何一個，故按此倍道矩陣總共可設(shè)計出故按此倍道矩陣總共可設(shè)計出3 3=27種譯碼種譯碼規(guī)則。規(guī)則。 在所有的譯碼規(guī)則中，不是每一種譯碼規(guī)在所有的譯碼規(guī)則中，不是每一種譯碼規(guī)則部是合理的，因此我們要討論則部是

11、合理的，因此我們要討論選擇選擇譯碼譯碼規(guī)則的準(zhǔn)則規(guī)則的準(zhǔn)則。141、錯誤概率錯誤概率在確定譯碼規(guī)則在確定譯碼規(guī)則 F(yj)xi， i=1,2 ,r , j=l,2,s 之后，之后，若信道輸出端接收到的符號為若信道輸出端接收到的符號為yj，則一定譯成則一定譯成xi。如果發(fā)送端發(fā)送的就是如果發(fā)送端發(fā)送的就是xi，即為正確譯碼；，即為正確譯碼；反之，若發(fā)送端發(fā)送的反之，若發(fā)送端發(fā)送的xk，且，且k i，即為，即為錯誤譯碼。錯誤譯碼。經(jīng)過譯碼后經(jīng)過譯碼后條件正確概率為條件正確概率為條件錯誤概率為條件錯誤概率為 平均錯誤概率平均錯誤概率pE為為平均錯誤概率平均錯誤概率pE的含義是經(jīng)過譯碼后，平均接收到

12、一個符號的含義是經(jīng)過譯碼后，平均接收到一個符號所產(chǎn)生錯誤概率的大小。所產(chǎn)生錯誤概率的大小。)|(| )(jijjyxpyyFp | )(1)|(1)|(jjjijyyFpyxpyep sjjjjEyepypyepEp1)|()()|(7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則152、譯碼規(guī)則譯碼規(guī)則 使平均錯誤概率使平均錯誤概率pE最小為最小為選擇譯碼規(guī)則的選擇譯碼規(guī)則的準(zhǔn)則準(zhǔn)則(1) 定義定義7. 2.1 最大后驗概率譯碼規(guī)則最大后驗概率譯碼規(guī)則理想觀測者規(guī)則理想觀測者規(guī)則 選擇譯碼函數(shù)選擇譯碼函數(shù)F(yj)x*，使之滿足條件，使之滿足條件iyxpyxpjij 對對 )|()|(* 它是選

13、擇這樣一種譯碼函數(shù)，對于每一個輸出符號它是選擇這樣一種譯碼函數(shù)，對于每一個輸出符號yj，j1、2，s 均譯成具有最大后驗概率的那個輸均譯成具有最大后驗概率的那個輸入符號入符號x*，則信道譯碼錯誤概率會最小。但一般說來，則信道譯碼錯誤概率會最小。但一般說來，后驗概率應(yīng)用起來并不方便，這時我們引入極大似然譯后驗概率應(yīng)用起來并不方便，這時我們引入極大似然譯碼規(guī)則。碼規(guī)則。7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則16(2) 定義定義7.2.2 極大似然譯碼規(guī)則極大似然譯碼規(guī)則 選擇譯碼函數(shù)選擇譯碼函數(shù)F(yj)x*，使之滿足條件，使之滿足條件 7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則ixpxy

14、pxpxypiijj 對對 )()|()()|(*ixypxypijj 對對 )|()|(* 當(dāng)信道輸入符號為等概分布時，應(yīng)用極大似然譯碼規(guī)則當(dāng)信道輸入符號為等概分布時，應(yīng)用極大似然譯碼規(guī)則是最方便的。所用的條件概率為信道矩陣中的元素。是最方便的。所用的條件概率為信道矩陣中的元素。當(dāng)信道輸入符號為等概分布時，可以寫成當(dāng)信道輸入符號為等概分布時，可以寫成17(3) 最大后驗概率譯碼規(guī)則和極大似然譯碼規(guī)則是等價的最大后驗概率譯碼規(guī)則和極大似然譯碼規(guī)則是等價的 最大后驗概率譯碼規(guī)則可以很容易推出極大似然譯碼最大后驗概率譯碼規(guī)則可以很容易推出極大似然譯碼規(guī)則。由貝葉斯公式，最大后驗概率公式可寫為規(guī)則。

15、由貝葉斯公式，最大后驗概率公式可寫為iypxpxypypxpxypjiijjj 對對 )( )()|()()()|(*當(dāng)輸入為等概分布，當(dāng)輸入為等概分布， 則有則有)()(*ixpxp ixypxypijj 對對 )|()|(*7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則183、平均錯誤概率、平均錯誤概率 *xY,XxY,XYXYYXYYjjYjjjYjYjjjsjjjEp(y|x)p(x)p(xy)x*ypxypF(y),ypxypyyFpyp|yyFpypyp|yyFpe|ypypp)()()(),(1)()()()()(1)()(17.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則193、平均

16、錯誤概率、平均錯誤概率若輸入為等慨分布，則若輸入為等慨分布，則 *,)|(1xXYExyprp(*)式式( (* *) )意味著，在輸入為等概分布的條件下，意味著，在輸入為等概分布的條件下，譯碼錯誤概率譯碼錯誤概率P PE可用信道矩陣中的元素來表示。可用信道矩陣中的元素來表示。這種求和是除去信道矩陣中每列中對應(yīng)于這種求和是除去信道矩陣中每列中對應(yīng)于F(yj)x*的那一項后，求矩陣中其余元素之和。的那一項后，求矩陣中其余元素之和。7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則注：注：改變信道的傳遞特性，降低平均錯誤概率。改變信道的傳遞特性，降低平均錯誤概率。20 4、費(fèi)諾不等式費(fèi)諾不等式 譯碼時發(fā)

17、生錯誤是由信道中噪聲引起的，因此平均譯碼時發(fā)生錯誤是由信道中噪聲引起的，因此平均錯誤概率錯誤概率pE與信道疑義度與信道疑義度H(X|Y)有關(guān)。表述這種關(guān)系有有關(guān)。表述這種關(guān)系有下述引理：費(fèi)諾不等式下述引理：費(fèi)諾不等式引理引理7.2.1 錯誤概率錯誤概率pE與信道疑義度與信道疑義度H(X|Y)之間的關(guān)系之間的關(guān)系 H(X|Y)H(pE)十十pElog(r1)這個不等式稱為費(fèi)諾不等式。這個不等式稱為費(fèi)諾不等式。 雖然雖然PE與譯碼規(guī)則有關(guān)，但不管采用什么譯碼規(guī)則與譯碼規(guī)則有關(guān)，但不管采用什么譯碼規(guī)則該不等式均成立。對于給定的信源、信道及編碼、譯碼規(guī)該不等式均成立。對于給定的信源、信道及編碼、譯碼規(guī)

18、則，信道疑義度則，信道疑義度H(X|Y)=H(X)I(X;Y)就可以被確定，它就可以被確定，它是信源熵超過是信源熵超過I(X;Y)的部分。這個值給定了譯碼錯誤的下的部分。這個值給定了譯碼錯誤的下限。限。7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則214、費(fèi)諾不等式、費(fèi)諾不等式 以以H(X|Y)為縱坐標(biāo)，為縱坐標(biāo)， pE為橫坐標(biāo)，函數(shù)為橫坐標(biāo)，函數(shù)H(pE)十十pElog(r1)隨隨pE變化的曲線如下圖所示。變化的曲線如下圖所示。7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則22 4、費(fèi)諾不等式費(fèi)諾不等式 費(fèi)諾不等式費(fèi)諾不等式 H(X|Y)H(pE)十十pElog(r1) 從費(fèi)諾不等式可以看出，當(dāng)

19、作了一次譯碼判決后所保留的從費(fèi)諾不等式可以看出，當(dāng)作了一次譯碼判決后所保留的關(guān)于信源的不確定性可以分成兩部分：關(guān)于信源的不確定性可以分成兩部分： 第一部分是接收到第一部分是接收到Y(jié)后，判決是否發(fā)生錯誤的不確定性后，判決是否發(fā)生錯誤的不確定性H(PE, 1-PE)， 第二部分是當(dāng)判決是錯誤的，其錯誤概率為第二部分是當(dāng)判決是錯誤的，其錯誤概率為PE確定由確定由r-1個個輸人符號中哪一個引起錯誤的不確定性，它是輸人符號中哪一個引起錯誤的不確定性，它是(r-1 )個符號個符號不確定性的最大值不確定性的最大值log(r-1 )與與PE的乘積。的乘積。7.2 譯碼規(guī)則的選擇準(zhǔn)則譯碼規(guī)則的選擇準(zhǔn)則237.3

20、 信道編碼的編碼原則信道編碼的編碼原則 選擇最佳譯碼規(guī)則只能使錯誤概率選擇最佳譯碼規(guī)則只能使錯誤概率pE有限地減小，有限地減小，無法使無法使pE任意地小任意地小 必須優(yōu)選信道編碼方法來進(jìn)一步減小錯誤概率必須優(yōu)選信道編碼方法來進(jìn)一步減小錯誤概率 編碼方法介紹編碼方法介紹 簡單重復(fù)編碼簡單重復(fù)編碼 247.3.1 簡單重復(fù)編碼簡單重復(fù)編碼 99. 001. 001. 099. 0P其信道矩陣為其信道矩陣為2,1001. 001. 021)|(1,* xXYExyprp平均錯誤概率平均錯誤概率件下件下輸入分布為等概分布條輸入分布為等概分布條 2211)()(:xyFxyFA最最佳佳譯譯碼碼規(guī)規(guī)則則

21、設(shè)有二元對稱信道如圖所示。設(shè)有二元對稱信道如圖所示。257.3.1 簡單重復(fù)編碼簡單重復(fù)編碼簡單重復(fù)編碼：簡單重復(fù)編碼：規(guī)定信源符號為規(guī)定信源符號為“0 0( (或或“1 1”) )時，則重復(fù)發(fā)時，則重復(fù)發(fā)送三個送三個“0 0”( (或或“1 1”) )，此時構(gòu)成的新信道可，此時構(gòu)成的新信道可以看成是二元對稱信道的三次擴(kuò)展信道。以看成是二元對稱信道的三次擴(kuò)展信道。 87654321110101100011010001 aaaaaaaa的碼字的碼字沒有使用沒有使用111 000 消消息息的的碼碼字字發(fā)發(fā)送送端端用用作作11111010110001101000100087654321 接收序列接收

22、序列接收端接收端267.3.1 簡單重復(fù)編碼簡單重復(fù)編碼設(shè)輸入符號為等概分布，采用極大似然譯碼規(guī)則設(shè)輸入符號為等概分布，采用極大似然譯碼規(guī)則（即大數(shù)邏輯譯碼）（即大數(shù)邏輯譯碼）3222222332222223 pp pp pppp pppppppppppp pppp pp ppP15131211)()()()( FFFF88878684)()()()( FFFF42332222223,1033)(21)|(1)()|(* ppppppppppppppppppMpppxXYijixXYijE 輸入為等概條件下，相應(yīng)的平均錯誤概率為輸入為等概條件下，相應(yīng)的平均錯誤概率為277.3.1 簡單重復(fù)編碼

23、簡單重復(fù)編碼 采用簡單重復(fù)編碼方法，如果進(jìn)一步增大重復(fù)次數(shù)采用簡單重復(fù)編碼方法，如果進(jìn)一步增大重復(fù)次數(shù)n，則，則會繼續(xù)降低平均錯誤概率會繼續(xù)降低平均錯誤概率pE ，不難算出，不難算出 n=5 pE = 10-5 n=7 pE410-5 n=9 pE10-8 n=11 pE510-10 在這種情況下，采用在這種情況下，采用“擇多譯碼擇多譯碼”的譯碼規(guī)則，即根據(jù)的譯碼規(guī)則，即根據(jù)信道輸出端接收序列中信道輸出端接收序列中“0”多還是多還是“1”多。多。 如果是如果是“0”多譯碼器就判決為多譯碼器就判決為“0”， 如果是如果是“1”多譯碼器就判決為多譯碼器就判決為“1”。得到的平均錯誤概率與極大譯碼規(guī)

24、則是一致的。得到的平均錯誤概率與極大譯碼規(guī)則是一致的。287.3.2 漢明距離漢明距離 1、漢明距離漢明距離 設(shè)設(shè)X(x1 , x2 , xn)，Y(y1 , y2 , yn)為兩個為兩個n長的二長的二元碼字，則碼字元碼字，則碼字X和和Y之間的漢明距離定義為之間的漢明距離定義為 2、物理含義：兩個碼字之間的漢明距離是它們在相同位、物理含義：兩個碼字之間的漢明距離是它們在相同位上不同碼符號的數(shù)目的總和。上不同碼符號的數(shù)目的總和。3、性質(zhì)、性質(zhì) 漢明距離滿足距離公理漢明距離滿足距離公理 (1)非負(fù)性非負(fù)性 (2)對稱性對稱性 (3)三角不等式三角不等式 nikkyxYXD1,表表示示模模二二和和運(yùn)

25、運(yùn)算算其其中中 29 4、 碼碼C的最小距離的最小距離 在二元碼在二元碼C中，任意兩個碼字的漢明距離的最中，任意兩個碼字的漢明距離的最小值，稱為碼小值，稱為碼C的最小距離，即的最小距離，即 5、舉例、舉例 7.3.2 漢明距離漢明距離CCCCCCCDDjijiji, ,minmin且1 2 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 3minminmin432121 DDDaaaaCCn的的兩兩組組碼碼設(shè)設(shè)有有307.3.2 漢明距離漢明距離 很明顯，最小碼間距離很明顯，最小碼間距離Dmin越大，則平均錯誤概越大，則平均錯誤概率率pE越小。在

26、輸入消息符號個數(shù)越小。在輸入消息符號個數(shù)M相同的情況相同的情況下，同樣地下，同樣地Dmin越大，越大， pE越小。越小。 碼組中最小距離越大，受干擾后，越不容易把碼組中最小距離越大，受干擾后，越不容易把一個碼字錯譯成另一個碼字，因而平均錯誤概一個碼字錯譯成另一個碼字，因而平均錯誤概率率pE小。如果最小碼間距離小。如果最小碼間距離Dmin小，受干擾后小，受干擾后 很容易把一個碼字譯成另一個碼，因而平均錯很容易把一個碼字譯成另一個碼，因而平均錯誤概率大。這意味著，在選擇編碼規(guī)則時，應(yīng)誤概率大。這意味著，在選擇編碼規(guī)則時，應(yīng)使碼字之間的距離越大越好。使碼字之間的距離越大越好。316 6、基于漢明距離

27、的最小近鄰譯碼規(guī)則、基于漢明距離的最小近鄰譯碼規(guī)則消息數(shù)固定為消息數(shù)固定為M M，碼字長度固定為，碼字長度固定為N N，離散無記憶，離散無記憶信道的信道的N N次擴(kuò)展信道次擴(kuò)展信道7.3.2 漢明距離漢明距離),(),(22112121)()()()()(jijiyxDNyxDiNjNijijiNiijNjjijppppppppxypxypxypxxxyyypxyp 32M個消息先驗等概條件下，采用最大似然準(zhǔn)則個消息先驗等概條件下，采用最大似然準(zhǔn)則若有若有則選擇譯碼函數(shù)則選擇譯碼函數(shù)7.3.2 漢明距離漢明距離), 2 , 1)()(*Mixypxypijj ),(),(),(),(*jiji

28、jjyxDNyxDyxDNyxDpppp ppp 且當(dāng)21),(),(*jijyxDyxD ), 2 , 1(Mi )2 , 2 , 1(,)(21*NMjjxxxxyF 337.3.2 漢明距離漢明距離6 6、基于漢明距離的最小近鄰譯碼規(guī)則、基于漢明距離的最小近鄰譯碼規(guī)則將與將與yj漢明距離最近的漢明距離最近的xi譯作譯作yj原碼，即選擇譯原碼，即選擇譯碼函數(shù)碼函數(shù)),(),()(min*jijjyxDyxDxyF 對于等概輸入，當(dāng)誤碼率較低時（小于對于等概輸入，當(dāng)誤碼率較低時（小于1/21/2），），基于漢明距離的最小近鄰譯碼規(guī)則基于漢明距離的最小近鄰譯碼規(guī)則等價于等價于極大似然譯碼規(guī)則。

29、極大似然譯碼規(guī)則。347.3.2 漢明距離漢明距離 在有噪信道中，傳輸?shù)钠骄e誤概率在有噪信道中，傳輸?shù)钠骄e誤概率pE和和各種編、譯碼方法有關(guān)。各種編、譯碼方法有關(guān)。 可采用使碼的最小距離盡可能增大的編碼可采用使碼的最小距離盡可能增大的編碼方法，又采用將接收序列方法，又采用將接收序列yj譯成與之距離譯成與之距離最短的碼字最短的碼字x*的譯碼方法，則只要的譯碼方法，則只要n足夠足夠長時，適當(dāng)選擇輸入符號個數(shù)長時，適當(dāng)選擇輸入符號個數(shù)M，就可以，就可以使平均錯誤概率很小，而信息傳輸率又能使平均錯誤概率很小，而信息傳輸率又能保持一定。保持一定。357.4 抗干擾信道編碼定理抗干擾信道編碼定理定理定

30、理7.4.1 香農(nóng)第二定理香農(nóng)第二定理 設(shè)有一離散無記憶平穩(wěn)信道，信道容量為設(shè)有一離散無記憶平穩(wěn)信道，信道容量為C，只要，只要待傳送的信息傳輸率待傳送的信息傳輸率 RC，則存在一種編碼，當(dāng)輸，則存在一種編碼，當(dāng)輸入序列長度入序列長度n足夠大時，使譯碼錯誤概率任意小足夠大時，使譯碼錯誤概率任意小。物理意義：物理意義：(1) 只要只要RC，就可以在有噪信道中以任意小的錯誤概率，就可以在有噪信道中以任意小的錯誤概率(pE )傳傳 輸信息輸信息(2) 當(dāng)輸入序列長度當(dāng)輸入序列長度n足夠大時，可以以任意接近信道容量足夠大時，可以以任意接近信道容量C的信息的信息傳輸率傳遞信息。傳輸率傳遞信息。367.4

31、抗干擾信道編碼定理抗干擾信道編碼定理定理定理 7.5.2 香農(nóng)第二定理的逆定理香農(nóng)第二定理的逆定理 設(shè)有一離散無記憶平穩(wěn)信道，其信道容量為設(shè)有一離散無記憶平穩(wěn)信道，其信道容量為C，對于任，對于任意意 0，若選用碼字總數(shù)，若選用碼字總數(shù)M2n(C+ )，則無論，則無論n取多大也找不取多大也找不到一種編碼，使譯碼錯誤概率到一種編碼，使譯碼錯誤概率pE任意小。任意小。CnCnnMLSHR2log)(log)(香農(nóng)第二定理及其逆定理香農(nóng)第二定理及其逆定理表明表明：耍想使信息傳輸率耍想使信息傳輸率R R大于信道容量大于信道容量C C而又無錯誤的傳輸消息是不而又無錯誤的傳輸消息是不可能的?？赡艿?。在任何信

32、道中，信道容量是進(jìn)行可靠傳輸?shù)淖畲笮畔鬏斅?。在任何信道中，信道容量是進(jìn)行可靠傳輸?shù)淖畲笮畔鬏斅?。?dāng)選擇碼字個數(shù)當(dāng)選擇碼字個數(shù)M2n(C+ )時，信息傳輸率為時，信息傳輸率為37一、分組碼的基本概念一、分組碼的基本概念差錯控制思想：差錯控制思想：在在2k個長度為個長度為k的的0,1消息消息序列中，設(shè)法按一定規(guī)則加入若干序列中，設(shè)法按一定規(guī)則加入若干0,1符號，符號，把長度為把長度為k的的0,1信息序列變?yōu)殚L度為信息序列變?yōu)殚L度為n(nk)的具有一定抗干擾能力的符號序列的具有一定抗干擾能力的符號序列其中其中k+r=n.由由2k個長度為個長度為n的的0,1符號序符號序組成的集合，構(gòu)成一個組成的集

33、合，構(gòu)成一個(n,k)分組碼，代表分組碼，代表2k個長度為個長度為k的消息序列。的消息序列。7.5 分組碼及其檢糾能力分組碼及其檢糾能力)(2121rkkkkaaaaaa 38 與與 (n,k)分組碼分組碼 對應(yīng)關(guān)系對應(yīng)關(guān)系(n,k)分組碼實質(zhì)：分組碼實質(zhì)：如何從如何從2n個長為個長為n的的0,1序列中選序列中選2k個長為個長為n的的0,1序列序列7.5 分組碼及其檢糾能力分組碼及其檢糾能力)(21kaaa)(21nccc )()()(2121222111knnkkaaafcaaafcaaafc39奇偶校驗碼奇偶校驗碼特點(diǎn)：特點(diǎn)：長度為長度為N；信息位；信息位k=(N-1)，且有，且有表明：表

34、明：碼字中碼字中1的個數(shù)是偶數(shù)，只能發(fā)現(xiàn)奇的個數(shù)是偶數(shù)，只能發(fā)現(xiàn)奇數(shù)個錯誤。數(shù)個錯誤。7.5 分組碼及其檢糾能力分組碼及其檢糾能力) 1, 2 , 1( Niacii 11NiiNac40二、分組碼的檢錯、糾錯能力二、分組碼的檢錯、糾錯能力(n,k)分組碼是一種糾錯碼分組碼是一種糾錯碼.(3,1)分組碼分組碼(N=3次重復(fù)碼次重復(fù)碼)可糾正一位錯，可糾正一位錯，發(fā)現(xiàn)兩位錯發(fā)現(xiàn)兩位錯.7.5 分組碼及其檢糾能力分組碼及其檢糾能力41(n,k)分組碼的檢糾能力與漢明距離的關(guān)系分組碼的檢糾能力與漢明距離的關(guān)系7.5 分組碼及其檢糾能力分組碼及其檢糾能力),(,(1),(),(knwwewwDeknj

35、iji 個錯誤分組碼能發(fā)現(xiàn)),(,(12),(),(jiknwwewwDeknjiji 個錯誤分組碼能糾正),(,(1),()(),(jiknwwfewwDeffeknjiji 個錯誤個錯誤，同時發(fā)現(xiàn)分組碼能糾正注：注：上述結(jié)論可換為最小漢明距離上述結(jié)論可換為最小漢明距離.42重復(fù)碼重復(fù)碼很強(qiáng)檢糾能力，碼率最低很強(qiáng)檢糾能力，碼率最低奇偶校驗碼奇偶校驗碼檢糾能力極低，碼率最高檢糾能力極低，碼率最高7.5 分組碼及其檢糾能力分組碼及其檢糾能力碼符比特NNNMR12loglog11 碼符比特NNNNNMRN1112loglog12 43線性分組碼線性分組碼7.7 線性分組碼及其生成矩陣線性分組碼及其

36、生成矩陣 消息消息m (n , k) 碼字碼字c m=(mk-1,m1,m0) 分組編碼器分組編碼器 c=(cn-1,c1,c0) qk qn 由碼符號集由碼符號集0,1組成的組成的(n,k)線性分組碼，是線性分組碼，是k維子空間維子空間 (n,k)線性分組碼可由線性分組碼可由k個線性獨(dú)立的碼字張成個線性獨(dú)立的碼字張成 qk個信息元組以什么算法一一對應(yīng)映射到碼空間。個信息元組以什么算法一一對應(yīng)映射到碼空間。 碼率編碼效率：碼率編碼效率：Rc =k/n 447.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣生成矩陣 c m G 1n 1k kn 碼字 消息 生成矩陣 Ggk-1g1g0T，有k

37、個(1n)行矢量，如何選擇呢？457.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣線性分組碼的形成線性分組碼的形成 c = mk-1 gk-1+ m1 g1+m0 g0 碼空間的所有元素（即碼字）都可以寫成k個基底的線性組合 由于k個基底即G的k個行矢量線性無關(guān)，矩陣G的秩一定等于k。 當(dāng)信息元確定后，碼字僅由G矩陣決定，因此我們稱這kn 矩陣G為該(n,k)線性分組碼的生成矩陣。 467.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣生成矩陣生成矩陣G(kn)的特點(diǎn)的特點(diǎn) 想要保證 (n,k)線性分組碼能夠構(gòu)成k維n重子空間，G 的k個行矢量gk-1, g1, g0必須是線性無關(guān)的，只

38、有這樣才符合作為基底的條件。 由于基底不是唯一的，所以G也就不是唯一的。 不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個因素，碼集一樣而映射方法不同也不能說是同樣的碼。 477.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣 (n,k)碼的任何生成矩陣都可以通過行運(yùn)算（以及列置換）簡化成“系統(tǒng)形式” 。G = Ik P =Ik是kk單位矩陣，P是kr矩陣(k+r = n)。 (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 系統(tǒng)形式的生成矩陣(1)(1)(1)1(1)01(1)11100(1)01001000

39、100001kn kkkn kn kppppppppp (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp (1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp krkkrrppppppppp21222211121110001000148系統(tǒng)碼構(gòu)造7.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣 krkkrrkppppppppp

40、mmmPMw21222211121121)()()()2()1(21rknknknkCCCmmmw ),12(1)(rjpmCkiijijkn 其中其中49碼字碼字碼字漢明重量碼字漢明重量(n,k)線性分組碼最小重量線性分組碼最小重量7.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣), 2 , 1(1 , 0)(21niCCCCwin 01)(iCwW0,),(min)(min iiiiwWwwWWW結(jié)論結(jié)論)(),(minminWWwwDji 其中其中),(,),(min),(minknwwwwDwwDjijijiji 507.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣 前k位由單

41、位矩陣Ik決定，等于把信息組m原封不動搬到碼字的前k位； 其余的n-k位叫冗余位或一致校驗位一致校驗位，是前k個信息位的線性組合。 這樣生成的（n,k）碼叫做系統(tǒng)碼系統(tǒng)碼。 若生成矩陣G不具備系統(tǒng)形式，則生成的碼叫做非系統(tǒng)碼非系統(tǒng)碼。 系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。 生成的碼字生成的碼字C517.7 線性分組碼及其生成矩陣線性分組碼及其生成矩陣 若通過行運(yùn)算和列置換能將兩個生成矩陣G互等，則稱這兩個G等效。 非系統(tǒng)碼的G可通過運(yùn)算轉(zhuǎn)變?yōu)橄到y(tǒng)碼的G，且不改變原碼的檢糾能力。 等效的兩個G生成的兩個(n,k)線性碼也是等效的。 因此，每個(n,k)線性碼都可以和一個系統(tǒng)的(n,k)線性碼等

42、效。 系統(tǒng)碼52一致校驗矩陣的構(gòu)成一致校驗矩陣的構(gòu)成(n,k)碼生成矩陣G=Ik,P ，則H PT In-k ， 且GHT=0 H的校驗作用的校驗作用7.8 一致檢驗矩陣與伴隨式一致檢驗矩陣與伴隨式TTWHknW0),( 537.8 一致檢驗矩陣與伴隨式一致檢驗矩陣與伴隨式 n維n重空間有相互正交的n個基底 選擇k個基底構(gòu)成碼空間C 選擇另外的(n-k)個基底構(gòu)成空間H C和H是對偶的 CHT0, GHT=0 n維維n重空間重空間V k維維k重重 k維維n重重 n-k維維 信息組信息組 碼空間碼空間 n重重H 空間空間m C空間構(gòu)成空間構(gòu)成547.8 一致檢驗矩陣與伴隨式一致檢驗矩陣與伴隨式

43、將H空間的n-k個基底排列起來可構(gòu)成一個(n-k)n矩陣，稱為校驗矩陣H。用來校驗接收到的碼字是否是正確的； G是(n,k)碼的生成矩陣，H是它的校驗矩陣； H是(n,n-k)對偶碼的生成矩陣，它的每一行是一個基底。 G則是它的校驗矩陣。55 例7.8.1 (6,3)線性分組碼，其生成矩陣是 G= 求：(1)計算碼集，列出信息組與碼字的映射關(guān)系。(2)將該碼系統(tǒng)化處理后，計算系統(tǒng)碼碼集并列出映射關(guān)系。(3)計算系統(tǒng)碼的校驗矩陣H。若收碼r = 100110, 檢驗它是否碼字？ (4)根據(jù)系統(tǒng)碼生成矩陣畫出編碼器電原理圖。 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1

44、56例7.8.1 碼集與映射關(guān)系信息 碼字 系統(tǒng)碼字000 000000 00000000101110100101101011000101011001110110001110110011101010011110110011110110011000101111000111101011011101057例7.8.1 二元(6,3)線性分組碼編碼器 m0m1m2 輸入 輸出 c0c1c258伴隨式伴隨式 m C=(cn-1,c1,c0) R=(rn-1,r1,r0) (n,k) 信道定義差錯圖案E E(en1,e1,e0) RC (rn-1cn-1,r1c1,r0c0) 二進(jìn)制碼中模2加與模2減是等

45、同的，因此有E = R C 及R = C E 59伴隨式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 = (sn-k-1,s1,s0) = RHT = EHT 60 從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。 差錯圖案E是n重矢量，共有2n個可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個可能的組合，因此不同的差錯圖案

46、可能有相同的伴隨式。 接收端收到R后，因為已知HT，可求出 SRHT；如果能知道對應(yīng)的E，則通過C = RE而求得C。 RHT = S ? C = RE R S E C 只要E正確，譯出的碼也就是正確的。 伴隨式S的意義61 上述方程組中有n個未知數(shù)en1, e1,e0 ，卻只有n-k個方程，可知方程組有多解。 在有理數(shù)或?qū)崝?shù)域中，少一個方程就可能導(dǎo)致無限多個解，而在二元域中，少一個方程導(dǎo)致兩個解，少兩個方程四個解，以此類推，少n-( n-k) = k個方程導(dǎo)致每個未知數(shù)有2k個解。 因此，由上述方程組解出的E可以有2k個解。到底取哪一個作為附加在收碼R上的差錯圖案E的估值呢？ 概率譯碼：把所

47、有2k個解的重量(差錯圖案E中1的個數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計算效率不高。差錯圖案差錯圖案E的求解的求解(2) 62依據(jù)：依據(jù)：若若BSC信道的差錯概率是信道的差錯概率是p，則長度，則長度n的碼中錯誤概率的碼中錯誤概率 ： 0個錯個錯 1個錯個錯 2個錯個錯 n個錯個錯 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出錯越少的情況，發(fā)生概率越大，出錯越少的情況，發(fā)生概率越大，E的重量越輕，的重量越輕，所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準(zhǔn)則，所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準(zhǔn)則，即最大似然譯碼。即最大似然譯碼。63(n,k

48、)碼的一般譯碼方法：碼的一般譯碼方法：把把n維線性空間維線性空間Vn中所有中所有2n種不同的種不同的n維矢維矢量，劃分成量，劃分成2k個不交的子集個不交的子集D1,D2, ,D2k，每個子集中只含每個子集中只含(n,k)碼中的一個碼字碼中的一個碼字wi,每每個個Di含有含有2(n-k)個矢量個矢量.Di中任一矢量與中任一矢量與Di中中的碼字的碼字wi之間距離，是與其他子集之間距離，是與其他子集Dj (ij)中所含碼字中所含碼字wj (ij)間距離最小的。每個間距離最小的。每個Di中矢量都譯成中矢量都譯成Di所包含的碼字所包含的碼字wi.注：注：2k個碼字先驗等概時平均錯誤譯碼概率最小個碼字先驗

49、等概時平均錯誤譯碼概率最小7.9 標(biāo)準(zhǔn)陣列與譯碼表標(biāo)準(zhǔn)陣列與譯碼表64 表中所列碼字是接收到的碼字表中所列碼字是接收到的碼字R； 將沒有任何差錯時的收碼將沒有任何差錯時的收碼R放在第一行，收碼等于發(fā)碼放在第一行，收碼等于發(fā)碼R=C(C Ci,i =0,1,2k-1), 差錯圖案為全零差錯圖案為全零E0=(0,00)，伴隨，伴隨式為全零式為全零S0=(0,00)。由于有。由于有2k個碼字，碼表有個碼字，碼表有2k列。列。 在第在第2到第到第n+1的的n行中差錯圖案的所有重量為行中差錯圖案的所有重量為1 (共共n個個)。 如果如果(1+ n)2n-k，再在下面行寫出全部帶有，再在下面行寫出全部帶有

50、2個差錯的圖案個差錯的圖案 (共共 個個)。 如果總行數(shù)如果總行數(shù)(1+n + )仍然小于仍然小于2n-k，再列出帶有，再列出帶有3個差錯的圖個差錯的圖案，以此類推，直到放滿案，以此類推，直到放滿2n-k行，每行一個行，每行一個Ej, 對應(yīng)一個不同的對應(yīng)一個不同的伴隨式伴隨式Sj。這樣，表的行數(shù)。這樣，表的行數(shù)2n-k正好等于伴隨式的數(shù)目。正好等于伴隨式的數(shù)目。標(biāo)準(zhǔn)陣列的構(gòu)成 2n2nC2nC65S0 E0S1 E1 Sj Ej E0+C0= 0+0= 0E0+C1= C1E0+Ci= CiE1+C0= E1 E1+Ci Ej+C0= EjEj+C1Ej+Ci 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 E1+C1 1

51、1022n kn k ECE1122n kn k SE112n k EC12n ki EC1221n kk EC21kjEC121kEC02121kkECC66陪集和子集陪集和子集 譯碼表中有譯碼表中有2n-k行，每行是一個行，每行是一個陪集陪集，每陪集的第一個，每陪集的第一個元素元素(位于第一列位于第一列)叫叫陪集首陪集首。同一陪集（同一行）中的。同一陪集（同一行）中的所有元素對應(yīng)共同的一個伴隨式。第一行陪集的陪集所有元素對應(yīng)共同的一個伴隨式。第一行陪集的陪集首是全零伴隨式首是全零伴隨式S0所對應(yīng)的全零差錯圖案所對應(yīng)的全零差錯圖案E0(無差錯無差錯)，而第而第j行陪集的陪集首是伴隨式行陪集的

52、陪集首是伴隨式Sj所對應(yīng)的重量最小的所對應(yīng)的重量最小的差錯圖案差錯圖案Ej (C0=0, Rj=Ej)。 譯碼表中有譯碼表中有2k列，每列是一個列，每列是一個子集子集，每子集的第一個，每子集的第一個元素元素(位于第一行位于第一行)叫叫子集頭子集頭。同一子集（同一列）中的。同一子集（同一列）中的所有元素對應(yīng)同一個碼字，第一列子集的子集頭是全所有元素對應(yīng)同一個碼字，第一列子集的子集頭是全零碼字零碼字C0，而第，而第i列子集的子集頭是碼字列子集的子集頭是碼字Ci (E0=0, Ri=Ci) 。67例例 7.9.1 一個一個(5,2)系統(tǒng)線性碼的生成矩陣是系統(tǒng)線性碼的生成矩陣是G = 設(shè)收碼設(shè)收碼R

53、= (10101)，構(gòu)造標(biāo)準(zhǔn)陣列譯碼表，譯出發(fā)碼的估值，構(gòu)造標(biāo)準(zhǔn)陣列譯碼表，譯出發(fā)碼的估值解：解：(1)構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組m= (00)、(01) 、(10)、(11)及已知的及已知的G求得求得4個許用碼字為個許用碼字為C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校驗矩陣：求出校驗矩陣： H = PT I3 = 列出方程組：列出方程組：1011011101ic 000102030410111213142021222324100110100100111hhhhhhhhhhhhhhh000

54、011022033044010011112213314412002112222332442hehehehehesheheheheheshehehehehes 68伴隨式有伴隨式有2n-k238種組合，差錯圖案中代表無差錯的有種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有一種，代表一個差錯的圖案有 種，已有種，已有6種。種。代表兩個差錯的圖案有代表兩個差錯的圖案有 種。只需挑選其中的兩個，種。只需挑選其中的兩個，挑選方法可有若干種，不是唯一的。先將挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代

55、入上面的代入上面的線性方程組，解得對應(yīng)的線性方程組，解得對應(yīng)的Sj分別是分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，。剩下的伴隨式中，(011)所對應(yīng)的差所對應(yīng)的差錯圖案是錯圖案是2k個即個即(00011)、(10100)、(01110)、(11001),其中其中(00011)和和(10100)并列重量最輕，任選其中一個如并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式同樣可得伴隨式(110)所對應(yīng)的最輕差錯圖案之一是所對應(yīng)的最輕差錯圖案之一是(00110)。 551 5102 例例 7.9.1 標(biāo)準(zhǔn)陣列的構(gòu)成標(biāo)準(zhǔn)陣列的構(gòu)成515 C

56、1025 C69S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例例 7.9.1 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列70例 7.9.1 將接收碼R10101譯碼 可選以下三種方法

57、之一譯碼：可選以下三種方法之一譯碼： 直接搜索碼表，查得直接搜索碼表，查得(10101)所在列的子集頭是所在列的子集頭是(10111)，因此，因此譯碼輸出取為譯碼輸出取為(10111)。 先求伴隨式先求伴隨式RHT = (10101) HT = (010) = S4，確定，確定S4所在行，再所在行，再沿著行對碼表作一維搜索找到沿著行對碼表作一維搜索找到(10101), 最后順著所在列向上找最后順著所在列向上找出碼字出碼字(10111)。 先求出伴隨式先求出伴隨式RHT = (010) = S4并確定并確定S4所對應(yīng)的陪集首（差錯所對應(yīng)的陪集首（差錯圖案）圖案）E4=(00010)，再將陪集首與

58、收碼相加得到碼字，再將陪集首與收碼相加得到碼字C= R+ E4= (10101)+ (00010)= (10111)。 上述三種方法由上而下，查表的時間下降而所需計算量增大，上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。實際使用時可針對不同情況選用。71 對上例作進(jìn)一步分析，還可以看到，該對上例作進(jìn)一步分析，還可以看到，該(5,2)碼的碼的dmin=3, 糾錯能力是糾錯能力是t = INT(3-1)/2 = 1。因此，譯碼陣列。因此，譯碼陣列中只有前中只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準(zhǔn)則，而第譯碼

59、準(zhǔn)則，而第7、8行的差錯圖案行的差錯圖案(00011)和和(00110)中包含中包含兩個兩個“1”，已超出了，已超出了t= 1的糾錯能力，譯碼已不可靠。比的糾錯能力，譯碼已不可靠。比如，當(dāng)收碼如，當(dāng)收碼R(10100)時，根據(jù)碼表譯出的碼字是時，根據(jù)碼表譯出的碼字是(10111)，與收碼與收碼R的漢明距離是的漢明距離是2，然而收碼，然而收碼R與全零碼字與全零碼字(00000)的的漢明距離也是漢明距離也是2，為什么不能譯成，為什么不能譯成(00000)呢？事實上，碼呢？事實上，碼表的第表的第7、8行本身就不是唯一的。注意在碼表計算過程中，行本身就不是唯一的。注意在碼表計算過程中，伴隨式伴隨式(0

60、11)所對應(yīng)的所對應(yīng)的4個差錯圖案中有兩個并列重量最輕，個差錯圖案中有兩個并列重量最輕，如果當(dāng)時選的不是如果當(dāng)時選的不是(00011)而是而是(10100)，那么碼表第，那么碼表第7行就行就不是現(xiàn)在這樣了。不是現(xiàn)在這樣了。 對例對例 7.9.1的的分析分析72譯碼表的構(gòu)成 由陪集首由陪集首ei和伴隨式和伴隨式Si兩列構(gòu)成兩列構(gòu)成 共有共有2n-k行，按發(fā)生錯誤遞增的順序，排行，按發(fā)生錯誤遞增的順序，排列陪集首，直到排滿列陪集首，直到排滿2n-k行行 計算每個陪集首對應(yīng)的伴隨式計算每個陪集首對應(yīng)的伴隨式Si= eiHT 譯碼過程譯碼過程 計算計算S=RHT S=0,則沒有發(fā)生錯誤，譯為則沒有發(fā)生