最大似然譯碼

1、分組碼I定義：將信源的信息序列按照獨(dú)立的分組進(jìn)行處理和編碼，稱為分組 碼。編碼時將每k個信息位分為一組進(jìn)行獨(dú)立處理，變換成長度為n （nk）的二 進(jìn)制碼組。簡單實用編碼包括奇偶監(jiān)督碼、二維奇偶監(jiān)督碼、恒比碼、正反碼，其中奇偶監(jiān)督 碼和分組碼又同屬于代數(shù)碼。分組碼一般用符號（n，k）表示，其中n是碼組的總 位數(shù)，又成為碼組的長度（碼長），k是碼組中信息碼元的數(shù)目，n- k= r為 碼組中 的監(jiān)督碼元數(shù)目。在分組碼中，把碼組中“的個數(shù)目稱為碼組的重量，簡稱碼 重。把兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。碼距又稱 漢明距離。最大似然譯碼前面我們介紹了信道編碼的基本概念，下面將詳細(xì)

2、分析有尖譯碼的一些理論依據(jù)。M = (mk-i mi m。)C = ( Ck-i Ci Co )輸入II輸出圖5-6信道編碼器結(jié)構(gòu)框圖已知信道編碼器的框圖如圖56所示，設(shè)任一個信息序列M是一個k位碼元的序列，通過編碼器按一 定的規(guī)律（編碼規(guī)則）產(chǎn)生若干監(jiān)督元，形成一個長度為n的序列（n重數(shù)組）即碼字（一種按特定規(guī)則 排列并具有唯一含義的碼序列I），每一個信息序列將形成不同的碼字與之對應(yīng)，在二進(jìn)制下，k長序列共 有種組合，因此編碼輸出的碼字集合共有個碼字，而二進(jìn)制下的n重共有卽種，顯然編碼輸出的碼字僅是所有二進(jìn)制n重中的一部分，編碼實際上就是從這N種不同的n重數(shù)組中按一定規(guī)律（編碼規(guī)則）選出郭個

3、n重代表個不同的信源原始信息。經(jīng)編碼后產(chǎn)生的（n,k）碼送信道傳輸，由于信道干擾的影響將不可避免地發(fā)生錯誤，這種錯誤有兩種 趨勢： 許用碼字變成禁用碼組，這種錯誤一旦出現(xiàn)，由于接收到的碼組不在編碼器輸出的碼字集合中，譯 碼時可以發(fā)現(xiàn)，所以這種錯誤模型是可檢出的。 許用碼字變成許用碼字，即發(fā)端發(fā)生某一碼字G經(jīng)傳輸后錯成碼集中的另一碼字Cj，這時收端無法確認(rèn)是否出錯，因此這是一種不可檢出的錯誤模型。可見，一個n重二進(jìn)制碼字C在傳輸中由于信道干擾的影響，到接收端可能變成創(chuàng)種n重中的任一個，為了能在接收端確認(rèn)發(fā)送的是何消息，就需要建立一定的判決規(guī)則以獲得最佳譯碼。一般來說，譯碼器要完成比編碼器更為復(fù)雜

4、的運(yùn)算，譯碼器性能的好壞、速度的快慢往往決定了整個差錯控制系統(tǒng)的性能和成本。譯碼正確與否的概率主要取決于所使用的碼、信道特征及譯 碼算法。對特定碼類如何尋找譯碼錯誤概率小碼速度快、設(shè)備簡單匚譯碼算法，是糾錯編碼理論中一個重要 而實際的課題。下面我們討論當(dāng)碼類和信道給定時，由圖5-2可知，信道輸出的R是一個二(或q)進(jìn)制序列，而譯碼器的輸出是一個信息序列M的估值序 列M?。譯碼器的基本任務(wù)就是根據(jù)接收序列R和信道特征，按照一套譯碼規(guī)則，由接收序列R給出與發(fā)送的信息序列M最接近的估值序列M?。由于M與碼字C之間存在一一對應(yīng)尖系，所以這等價于 譯碼器根據(jù)R產(chǎn)生一個C的估值序列(？。顯然，當(dāng)且僅當(dāng)C?

5、=C時，M = M ,這時譯碼器正確譯碼。如果譯碼器輸出的C?乳，則譯碼器產(chǎn)生了錯誤譯碼。之所以產(chǎn)生錯誤譯碼是由于：首先，信道干擾很 嚴(yán)重，超過了碼本身的糾錯能力；其次，由于譯碼設(shè)備的故障(這點(diǎn)本書不予討論)。當(dāng)給定接收序列R時，譯碼器的條件譯碼錯誤概率定義為P(E | R)= P(C? MC| R)所以譯碼器的錯誤譯碼概率Pe=、P(E|R)P(R)RP(R)是接收序列R的概率，與譯碼方法無尖，所以譯碼錯誤概率最小的最佳譯碼規(guī)則是使min Pe 二 min P(E R)二 min P(? -C R)RR(5-1)min P(? -C R)= maxP(?=C R)因此，如果譯碼器對輸入的R,

6、能在2k個碼字中選擇一個使P(C?i=C|R) (i = 1,2，2k)最大的 碼字Ci作為C的估值序列C?，則這種譯碼規(guī)則一定使譯碼器輸出錯誤概率最小，稱這種譯碼規(guī)則為最大后 驗概率譯碼。P(C|R)二由貝葉斯公式P(R)可知，若發(fā)端發(fā)送每個碼字的概率P(Ci)均相同，且由于P(R)與譯碼方法無尖，所以maxP(Ci | R) jAP(RQ) (52、i =,2.,2k)對DMC而言P(R|Ci)=i【P(rj|Cij) (5_3)p這里碼了 Ci = ( Ci1 , G2Cin) i = 1 , 2,5 2 k-個譯碼器的譯碼規(guī)則若能在2k個碼字C中選擇某一個C i并使式(52)成為最大，

7、則這種譯碼規(guī)則稱為最大似然譯碼(MLD ), P(R|C)稱為似然函數(shù)，相應(yīng)的譯碼器稱為最大似然譯碼器。由于logbX與x是單調(diào)尖系，因此式(52)與式(53)可寫成i max2k logbP(RQ) =)max2A logbP( |q)(54)仁厶*：二，厶，2j稱logbP(R|C)為對數(shù)似然函數(shù)或似然函數(shù)。對于DMC信道，MLD是使譯碼錯誤概率最小的一種最佳譯碼方法但此時要求發(fā)端發(fā)送每一碼字的概率P(Ci) (i = 1 , 2,，)均相等，否則MLD不是最佳的。在以后的討論中，都認(rèn)為P(G)均近似相等，因而MLD算法是一種最佳的譯碼算法。例5.1 一個碼由00000，00111 111

8、00與11011四個碼字組成。每個碼字可用來表示 四種可能的信息之一?？梢运愠鲈摯a的最小距離d o = 3，由定理5.3可知，它可糾正在任何位上出現(xiàn)的單個誤碼。同時我們注意到，碼長為5的二進(jìn)制碼組共有2 5=32種可能的序列，除了上述4個許用碼組外，其余28個為禁用碼組。為了對該碼進(jìn)行糾錯處理，需將28種禁用碼組的每一個與4種許用碼字作“最鄰近性”的比較。這種處理意味著要建立一個“譯碼表”，所以譯碼的本質(zhì)就是對碼組進(jìn)行分類，即先將所有與每個許用碼字有一位差錯的各個可能接收序列列 在該碼字的下面，這樣，就得到表5-1中以虛線圍起的部分。除了這一部分之外，我們應(yīng)注意到尚有8個序列未被列入。這8個序

9、列與每個碼字至少差二位。但是，它們與上述序列 不同，沒有惟一的方法可把它們安排到表內(nèi)。例如，既可將序列10001放在第4列，也可將它放在第I列。在譯碼過程中使用此表時，可將所接收序列與表內(nèi)各列對照，當(dāng)查到該序列時， 將該列第一行的碼字作為譯碼器的輸出。表四個碼字的譯碼表0000011100001111101110000011001011101011010001010001111100110010011000000111111100010111100010111001000011110100110110101000101101101100101010010011101010101001用這種方式建立的表具有很大的優(yōu)點(diǎn)。設(shè)信道誤比特率為Pe,出現(xiàn)任何一種具有i個差錯特定模式的概率是冃卩昇。當(dāng)Pe Pe(1 - Pe) Pe _(1 Pe) 即不出錯概率大于出錯概率；一個特定的單個差錯模式要比一個特定的兩個(或多個)差錯模式更容易出現(xiàn)。因此，譯碼器將所收到的一個特定碼組譯為在漢明距離上最鄰近的一個碼字時，實際上是選擇了最可能發(fā)送的那個碼字(設(shè)各個碼字的發(fā)送機(jī)會相同)。這就是MLD的具體應(yīng)用，它實際上就是根據(jù)接收序列R,在仝個碼字集中，尋找與R的漢明距離最小的碼字Ci,作為譯碼輸出，因為它最可能是發(fā)送的碼字。這種譯碼方法又稱為最小漢明距離譯碼，執(zhí)行這