1、信息論與編碼-最優(yōu)譯碼和最大似然譯碼,最優(yōu)譯碼和最大似然譯碼 信道的輸入是一個二（或q）進(jìn)制序列，而譯碼器的輸出時一個信息序列M的估值序列 。如下圖所示。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,信道,糾錯編碼器,糾錯譯碼器,干擾源,信源編碼器輸出,至信宿,分組碼數(shù)字通信模型,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,最優(yōu)譯碼和最大似然譯碼 信道的輸入是一個二（或q）進(jìn)制序列，而譯碼器的輸出時一個信息序列M的估值序列 。如下圖所示。 譯碼器的基本任務(wù)就是根據(jù)一套譯碼規(guī)則，由接收序列R給出與發(fā)送的信息序列最接近（最好是相同）的估值序列,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,由于M與碼字C之間存在一一對

2、應(yīng)關(guān)系，所以這等價于譯碼器根據(jù)R產(chǎn)生一個C的估值序列,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,由于M與碼字C之間存在一一對應(yīng)關(guān)系，所以這等價于譯碼器根據(jù)R產(chǎn)生一個C的估值序列 ，顯然，當(dāng)且僅當(dāng) 時， 。這時譯碼器正確譯碼。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,由于M與碼字C之間存在一一對應(yīng)關(guān)系，所以這等價于譯碼器根據(jù)R產(chǎn)生一個C的估值序列 ，顯然，當(dāng)且僅當(dāng) 時， 。這時譯碼器正確譯碼。 如果 ，則譯碼器產(chǎn)生錯誤譯碼。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,由于M與碼字C之間存在一一對應(yīng)關(guān)系，所以這等價于譯碼器根據(jù)R產(chǎn)生一個C的估值序列 ，顯然，當(dāng)且僅當(dāng) 時， 。這時譯碼器正確譯碼。 如果 ，則

3、譯碼器產(chǎn)生錯誤譯碼。當(dāng)給定接收序列R時，譯碼器的條件譯碼錯誤概率定義為,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,所以譯碼器的錯誤譯碼概率為,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,所以譯碼器的錯誤譯碼概率為 其中， 是接收R的概率，與譯碼方法無關(guān)，,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,所以譯碼器的錯誤譯碼概率為 其中， 是接收R的概率，與譯碼方法無關(guān)，所以譯碼錯誤概率最小的最佳譯碼規(guī)則是使 最小，即,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,所以譯碼器的錯誤譯碼概率為 其中， 是接收R的概率，與譯碼方法無關(guān)，所以譯碼錯誤概率最小的最佳譯碼規(guī)則是使 最小，即 而,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,

4、因此，如果譯碼器對輸入的R，能在 個碼字中選擇一個使 最大的碼字 作為C的估值序列 ，即,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,因此，如果譯碼器對輸入的R，能在 個碼字中選擇一個使 最大的碼字 作為C的估值序列 ，即 則這種譯碼規(guī)則一定能使譯碼器輸出錯誤概率最小,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,因此，如果譯碼器對輸入的R，能在 個碼字中選擇一個使 最大的碼字 作為C的估值序列 ，即 則這種譯碼規(guī)則一定能使譯碼器輸出錯誤概率最小，稱這種譯碼規(guī)則為最大后驗概率譯碼MAP (maximum aposteriori),信息論與編碼-最優(yōu)譯碼和最大似然譯碼,因此，如果譯碼器對輸入的R，能在 個碼字

5、中選擇一個使 最大的碼字 作為C的估值序列 ，即 則這種譯碼規(guī)則一定能使譯碼器輸出錯誤概率最小，稱這種譯碼規(guī)則為最大后驗概率譯碼MAP (maximum aposteriori),也叫做最佳譯碼。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,由貝葉斯公式 可知，如果發(fā)送端發(fā)送每一個碼字的概率 均相同,且由于p(R)與譯碼方法無關(guān)，,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,由貝葉斯公式 可知，如果發(fā)送端發(fā)送每一個碼字的概率 均相同,且由于p(R)與譯碼方法無關(guān)，所以,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,一個譯碼器如果能選擇 即在已知r的情況下使先驗概率最大，則這種譯碼規(guī)則稱為最大似然譯碼,信息論與編碼

6、-最優(yōu)譯碼和最大似然譯碼,一個譯碼器如果能選擇 即在已知r的情況下使先驗概率最大，則這種譯碼規(guī)則稱為最大似然譯碼（MLD：Maximum Likelihood),信息論與編碼-最優(yōu)譯碼和最大似然譯碼,一個譯碼器如果能選擇 即在已知r的情況下使先驗概率最大，則這種譯碼規(guī)則稱為最大似然譯碼（MLD：Maximum Likelihood)， 稱為似然函數(shù)。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,一個譯碼器如果能選擇 即在已知r的情況下使先驗概率最大，則這種譯碼規(guī)則稱為最大似然譯碼（MLD：Maximum Likelihood)， 稱為似然函數(shù)。相應(yīng)的譯碼器稱為最大似然譯碼器。,信息論與編碼-最優(yōu)譯碼

7、和最大似然譯碼,由于logx與x是單調(diào)關(guān)系，因此最大似然規(guī)則也可以寫成,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,由于logx與x是單調(diào)關(guān)系，因此最大似然規(guī)則也可以寫成 稱logp(R/C)為對數(shù)似然函數(shù)。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,對于DMC信道，如果發(fā)送端發(fā)送每一個碼字的概率 相等，則MLD就是譯碼錯誤概率最小的一種最佳譯碼規(guī)則。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,對于DMC信道，如果發(fā)送端發(fā)送每一個碼字的概率 相等，則MLD就是譯碼錯誤概率最小的一種最佳譯碼規(guī)則。 由于最佳譯碼要求知道后驗概率p(R/C)，這在很多時候是很困難的，所以經(jīng)常使用的是最大似然譯碼，在很多情況下，可

8、以認(rèn)為最大似然譯碼就是最佳譯碼。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,對于BSC信道，在譯碼的時候，如果我們逐比特地比較發(fā)碼和收碼，就只有兩種可能性：相同或者不同，其概率分別是：,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,如果R中有d個碼元與 不同，我們稱R和 之間的距離為d，這樣定義的距離稱為漢明距離。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,如果R中有d個碼元與 不同，我們稱R和 之間的距離為d，這樣定義的距離稱為漢明距離。接收碼字R和發(fā)送碼字 之間的漢明距離，就是二者模2加后的重量,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,如果R中有d個碼元與 不同，我們稱R和 之間的距離為d，這樣定義的距離稱

9、為漢明距離。接收碼字R和發(fā)送碼字 之間的漢明距離，就是二者模2加后的重量，即,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,此時的似然函數(shù)是,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,此時的似然函數(shù)是 因為上述似然函數(shù)中 是常數(shù)， 可以看出，d越大，則似然函數(shù)越小,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,此時的似然函數(shù)是 因為上述似然函數(shù)中 是常數(shù)， 可以看出，d越大，則似然函數(shù)越小，因此，求最大似然函數(shù)問題就變成了求最小漢明距離問題。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,漢明距離譯碼是一種硬判決譯碼。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,漢明距離譯碼是一種硬判決譯碼。只要在接收端將接收碼R與所有可能的

10、發(fā)碼逐比特進(jìn)行比較，選擇其中漢明距離最小的碼字作為譯碼結(jié)果就可以了。,信息論與編碼-最優(yōu)譯碼和最大似然譯碼,漢明距離譯碼是一種硬判決譯碼。只要在接收端將接收碼R與所有可能的發(fā)碼逐比特進(jìn)行比較，選擇其中漢明距離最小的碼字作為譯碼結(jié)果就可以了。當(dāng)發(fā)送的碼字互相統(tǒng)計獨(dú)立且等概時，漢明距離譯碼就是最佳譯碼。,信息論與編碼-碼距與檢錯、糾錯能力,碼距與檢錯、糾錯能力的關(guān)系 碼距：在隨機(jī)編碼中，我們曾說過，一個碼字可以看作是N維矢量空間的一個點(diǎn)，全部碼字所對應(yīng)的點(diǎn)集合構(gòu)成矢量空間的一個子集。子集的任意兩點(diǎn)之間都存在一定的距離，這個距離叫做碼字之間的碼距。子集任意兩點(diǎn)之間的碼距的最小值記為 。 歐氏距、漢明

11、距,信息論與編碼-碼距與檢錯、糾錯能力,檢錯能力：如果信道傳輸無誤，接收到的N重矢量一定是碼字，在矢量空間中一定對應(yīng)到碼字子集中的一個點(diǎn)上。,信息論與編碼-碼距與檢錯、糾錯能力,檢錯能力：如果信道傳輸無誤，接收到的N重矢量一定是碼字，在矢量空間中一定對應(yīng)到碼字子集中的一個點(diǎn)上。當(dāng)傳輸有誤時，可能會發(fā)生兩種情況：,信息論與編碼-碼距與檢錯、糾錯能力,檢錯能力：如果信道傳輸無誤，接收到的N重矢量一定是碼字，在矢量空間中一定對應(yīng)到碼字子集中的一個點(diǎn)上。當(dāng)傳輸有誤時，可能會發(fā)生兩種情況：一是不再對應(yīng)碼子字集上的一點(diǎn)，而是對應(yīng)到碼字子集點(diǎn)相鄰的的另一個空間點(diǎn)上；,信息論與編碼-碼距與檢錯、糾錯能力,檢錯

12、能力：如果信道傳輸無誤，接收到的N重矢量一定是碼字，在矢量空間中一定對應(yīng)到碼字子集中的一個點(diǎn)上。當(dāng)傳輸有誤時，可能會發(fā)生兩種情況：一是不再對應(yīng)碼子字集上的一點(diǎn)，而是對應(yīng)到碼字子集點(diǎn)相鄰的的另一個空間點(diǎn)上；第二種可能是仍然對應(yīng)到碼子字集中的一個點(diǎn)上，但卻是一個錯誤的點(diǎn)上。,信息論與編碼-碼距與檢錯、糾錯能力,檢錯能力：如果信道傳輸無誤，接收到的N重矢量一定是碼字，在矢量空間中一定對應(yīng)到碼字子集中的一個點(diǎn)上。當(dāng)傳輸有誤時，可能會發(fā)生兩種情況：一是不再對應(yīng)碼子字集上的一點(diǎn)，而是對應(yīng)到碼字子集點(diǎn)相鄰的的另一個空間點(diǎn)上；第二種可能是仍然對應(yīng)到碼子字集中的一個點(diǎn)上，但卻是一個錯誤的點(diǎn)上。第一種情況下，譯碼

13、的時候一定可以判斷出發(fā)生了誤碼；,信息論與編碼-碼距與檢錯、糾錯能力,檢錯能力：如果信道傳輸無誤，接收到的N重矢量一定是碼字，在矢量空間中一定對應(yīng)到碼字子集中的一個點(diǎn)上。當(dāng)傳輸有誤時，可能會發(fā)生兩種情況：一是不再對應(yīng)碼子字集上的一點(diǎn)，而是對應(yīng)到碼字子集點(diǎn)相鄰的的另一個空間點(diǎn)上；第二種可能是仍然對應(yīng)到碼子字集中的一個點(diǎn)上，但卻是一個錯誤的點(diǎn)上。第一種情況下，譯碼的時候一定可以判斷出發(fā)生了誤碼；而第二種情況卻不能判斷出發(fā)生了誤碼。,信息論與編碼-碼距與檢錯、糾錯能力,對于一個最小碼距為 的碼字子集，如果傳輸中發(fā)生誤碼后使得空間點(diǎn)的位置偏移小于 ，則一定可以判斷出發(fā)生了誤碼，,信息論與編碼-碼距與檢

14、錯、糾錯能力,對于一個最小碼距為 的碼字子集，如果傳輸中發(fā)生誤碼后使得空間點(diǎn)的位置偏移小于 ，則一定可以判斷出發(fā)生了誤碼，因為這時候由于誤碼不可能從一個空間點(diǎn)偏移到另一個空間點(diǎn)。,信息論與編碼-碼距與檢錯、糾錯能力,對于一個最小碼距為 的碼字子集，如果傳輸中發(fā)生誤碼后使得空間點(diǎn)的位置偏移小于 ，則一定可以判斷出發(fā)生了誤碼，因為這時候由于誤碼不可能從一個空間點(diǎn)偏移到另一個空間點(diǎn)。換句話說，可以檢測到錯誤。,信息論與編碼-碼距與檢錯、糾錯能力,對于一個最小碼距為 的碼字子集，如果傳輸中發(fā)生誤碼后使得空間點(diǎn)的位置偏移小于 ，則一定可以判斷出發(fā)生了誤碼，因為這時候由于誤碼不可能從一個空間點(diǎn)偏移到另一個

15、空間點(diǎn)。換句話說，可以檢測到錯誤。而當(dāng)由于誤碼使空間偏移大于 時，則有可能偏移到另外的碼字點(diǎn)上，也就有可能檢不出該錯誤來。,信息論與編碼-碼距與檢錯、糾錯能力,對于一個最小碼距為 的碼字子集，如果傳輸中發(fā)生誤碼后使得空間點(diǎn)的位置偏移小于 ，則一定可以判斷出發(fā)生了誤碼，因為這時候由于誤碼不可能從一個空間點(diǎn)偏移到另一個空間點(diǎn)。換句話說，可以檢測到錯誤。而當(dāng)由于誤碼使空間偏移大于 時，則有可能偏移到另外的碼字點(diǎn)上，也就有可能檢不出該錯誤來。因此，對于最小碼距為 的碼子字集，其檢錯能力為 。,信息論與編碼-碼距與檢錯、糾錯能力,糾錯能力：如果我們采用最佳譯碼或最大似然譯碼，那么當(dāng)接收到的碼字偏離其在N

16、維空間中原來的位置時，只要偏離得不太遠(yuǎn)，就可以根據(jù)最大似然譯碼規(guī)則（或最佳譯碼規(guī)則）經(jīng)過譯碼得到正確的結(jié)果。,信息論與編碼-碼距與檢錯、糾錯能力,糾錯能力：如果我們采用最佳譯碼或最大似然譯碼，那么當(dāng)接收到的碼字偏離其在N維空間中原來的位置時，只要偏離得不太遠(yuǎn)，就可以根據(jù)最大似然譯碼規(guī)則（或最佳譯碼規(guī)則）經(jīng)過譯碼得到正確的結(jié)果。但如果偏離得太遠(yuǎn)，以至于離另外一個碼字的空間點(diǎn)更近一些，則經(jīng)過最大似然譯碼，就會譯成另一個碼字，也就是不能糾正誤碼，或者說超出了該種編碼的最大糾錯范圍。,信息論與編碼-碼距與檢錯、糾錯能力,糾錯能力：如果我們采用最佳譯碼或最大似然譯碼，那么當(dāng)接收到的碼字偏離其在N維空間中

17、原來的位置時，只要偏離得不太遠(yuǎn)，就可以根據(jù)最大似然譯碼規(guī)則（或最佳譯碼規(guī)則）經(jīng)過譯碼得到正確的結(jié)果。但如果偏離得太遠(yuǎn)，以至于離另外一個碼字的空間點(diǎn)更近一些，則經(jīng)過最大似然譯碼，就會譯成另一個碼字，也就是不能糾正誤碼，或者說超出了該種編碼的最大糾錯范圍。那么糾錯范圍是多大呢？,信息論與編碼-碼距與檢錯、糾錯能力,我們可以設(shè)想以 個碼字空間點(diǎn)為球心，分別做一個超維的球體，且各個球體互不相交,信息論與編碼-碼距與檢錯、糾錯能力,我們可以設(shè)想以 個碼字空間點(diǎn)為球心，分別做一個超維的球體，且各個球體互不相交，那么，如果由于誤碼使空間點(diǎn)的偏移沒有超出所對應(yīng)的球體，則可以由最大似然譯碼糾正其錯誤，也就是可以

18、糾錯。,信息論與編碼-碼距與檢錯、糾錯能力,我們可以設(shè)想以 個碼字空間點(diǎn)為球心，分別做一個超維的球體，且各個球體互不相交，那么，如果由于誤碼使空間點(diǎn)的偏移沒有超出所對應(yīng)的球體，則可以由最大似然譯碼糾正其錯誤，也就是可以糾錯。對于最小碼距為 的碼子字集，球體半徑的最小值為 ，考慮到糾錯能力為整數(shù)位，所以糾錯能力應(yīng)該寫為 。,信息論與編碼-碼距與檢錯、糾錯能力,聯(lián)合檢錯、糾錯能力：,信息論與編碼-碼距與檢錯、糾錯能力,聯(lián)合檢錯、糾錯能力：對于最小碼距為 的碼字，其單獨(dú)的檢錯能力為 ，,信息論與編碼-碼距與檢錯、糾錯能力,聯(lián)合檢錯、糾錯能力：對于最小碼距為 的碼字，其單獨(dú)的檢錯能力為 ，單獨(dú)的糾錯能

19、力為 。,信息論與編碼-碼距與檢錯、糾錯能力,聯(lián)合檢錯、糾錯能力：對于最小碼距為 的碼字，其單獨(dú)的檢錯能力為 ，單獨(dú)的糾錯能力為 。 但如果聯(lián)合考慮檢錯和糾錯，則情況會有所變化,信息論與編碼-碼距與檢錯、糾錯能力,聯(lián)合檢錯、糾錯能力：對于最小碼距為 的碼字，其單獨(dú)的檢錯能力為 ，單獨(dú)的糾錯能力為 。 但如果聯(lián)合考慮檢錯和糾錯，則情況會有所變化，因為如果單獨(dú)考慮檢錯，只要不會偏移到另一個碼字空間點(diǎn)上，都可以檢測出來,信息論與編碼-碼距與檢錯、糾錯能力,聯(lián)合檢錯、糾錯能力：對于最小碼距為 的碼字，其單獨(dú)的檢錯能力為 ，單獨(dú)的糾錯能力為 。 但如果聯(lián)合考慮檢錯和糾錯，則情況會有所變化，因為如果單獨(dú)考

20、慮檢錯，只要不會偏移到另一個碼字空間點(diǎn)上，都可以檢測出來，但當(dāng)加了糾錯以后，如果偏移值過大，以至于偏移后更接近于另一個碼字空間點(diǎn)（即進(jìn)入另一個超球體）,信息論與編碼-碼距與檢錯、糾錯能力,聯(lián)合檢錯、糾錯能力：對于最小碼距為 的碼字，其單獨(dú)的檢錯能力為 ，單獨(dú)的糾錯能力為 。 但如果聯(lián)合考慮檢錯和糾錯，則情況會有所變化，因為如果單獨(dú)考慮檢錯，只要不會偏移到另一個碼字空間點(diǎn)上，都可以檢測出來，但當(dāng)加了糾錯以后，如果偏移值過大，以至于偏移后更接近于另一個碼字空間點(diǎn)（即進(jìn)入另一個超球體），則由于糾錯的原因，就會把它當(dāng)成另一個碼字，從而進(jìn)行錯誤的糾正（糾錯后就認(rèn)為沒有錯誤了），以至于不能檢測出來其錯誤。

21、,信息論與編碼-碼距與檢錯、糾錯能力,對于一個最小碼距為 的碼字子集，一般性的結(jié)論是：,信息論與編碼-碼距與檢錯、糾錯能力,對于一個最小碼距為 的碼字子集，一般性的結(jié)論是： 其中， 是糾錯能力， 是檢錯能力。,信息論與編碼-碼距與檢錯、糾錯能力,例如：最小碼距為7的碼字子集,信息論與編碼-碼距與檢錯、糾錯能力,例如：最小碼距為7的碼字子集，單獨(dú)檢錯可以檢測6個碼元的錯誤,信息論與編碼-碼距與檢錯、糾錯能力,例如：最小碼距為7的碼字子集，單獨(dú)檢錯可以檢測6個碼元的錯誤，單獨(dú)糾錯可以糾正3個碼元的錯誤。,信息論與編碼-碼距與檢錯、糾錯能力,例如：最小碼距為7的碼字子集，單獨(dú)檢錯可以檢測6個碼元的錯誤，單獨(dú)糾錯可以糾正3個碼元的錯誤。但如果想糾正3個碼元的錯誤，其檢錯能力減小為3，因為如果錯誤大于3，就會因為進(jìn)入另一個超球體的范圍而被錯誤地糾錯。,信息論與編碼-碼距與檢錯、糾錯能力,例如：最小碼距為7的碼字子集，單獨(dú)檢錯可以檢測6個碼元的錯誤，單獨(dú)糾錯可以糾正3個碼元的錯誤。但如果想糾正3個碼元的錯誤，其檢錯能力減小為3，因為如果錯誤大于3，就會因為進(jìn)入另一個超球體的范圍而被錯誤地糾錯。如果想檢測4個錯誤，則糾錯能力要降低為2，也就是說，要把糾錯的超球半徑降低為2。,信息論與編碼-碼距與檢錯、糾錯能力,例如：最小碼距為7的碼字子集，單獨(dú)檢錯可以檢測6個碼元的錯誤，單獨(dú)糾錯可以糾正3個