最大似然譯碼

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

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

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

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

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

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

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

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

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