信道編碼,糾錯(cuò)碼基礎(chǔ)

第6章信道編碼本章內(nèi)容：有擾離散信道的編碼定理糾錯(cuò)編譯碼的基本原理與分析方法線性分組碼卷積碼1第六講信道編碼

PartI--有噪信道編碼信道編碼的意義譯碼規(guī)則信源編碼提高數(shù)字信號有效性將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號 降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮)信道編碼提高數(shù)字通信可靠性

數(shù)字信號在信道的傳輸過程中,由于實(shí)際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產(chǎn)生誤碼。3編碼有噪信道編碼定理（香農(nóng)第二定理）離散、無記憶、平穩(wěn)信道，信道容量為C，只要待傳送的信息率R<C，就一定能找到一種信道編碼方法，使得碼長N足夠大時(shí)，平均差錯(cuò)率Pe任意接近于零。香農(nóng)第二定理是存在性定理，它指出在R<C時(shí)，肯定存在一種好的信道編碼方法，使Pe逼近零。但并沒有給出編碼的具體方法。

有噪信道編碼逆定理離散、無記憶、平穩(wěn)信道，信道容量為C，如果信息率R>C，則肯定找不到一種信道編碼方法，使得碼長N足夠大時(shí)，平均差錯(cuò)率任意接近于零。1、香農(nóng)信息論對信道編碼的指導(dǎo)意義信道編碼定理：每一個(gè)信道具有確定的信道容量C，對于任何小于C的信息傳輸率R，總存在一個(gè)碼長為n，碼率等于R的分組碼，若采用最大似然譯碼，則其譯碼錯(cuò)誤概率PE滿足

PEAe-nE(R)

其中：A是常數(shù)，E（R)為誤差函數(shù)錯(cuò)誤概率PE越小，傳輸可靠性越高。增大碼長n也可提高傳輸可靠性有噪信道編碼定理（香農(nóng)第二定理）

如一個(gè)離散無記憶信道，信道容量為C。當(dāng)信息傳輸率R≤C時(shí)，只要碼長足夠長，總可以在輸入符號集中找到M個(gè)碼字組成的一組碼和相應(yīng)的譯碼準(zhǔn)則，使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。有噪信道編碼逆定理

如一個(gè)離散無記憶信道，信道容量為C。當(dāng)信息傳輸率R>C時(shí)，則無論碼長n多長，總找不到一種編碼使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。信道編碼的理論依據(jù)：當(dāng)取信道容量C以下的信息傳輸率時(shí)，以指數(shù)趨進(jìn)于0；當(dāng)取分界點(diǎn)以下的信息傳輸率時(shí)，以指數(shù)趨進(jìn)于1；因此在任何信道中，信道容量都是可達(dá)的、最大的可靠信息傳輸率。存在定理，它沒有給出一個(gè)具體可構(gòu)造的編碼方法，但有助于指導(dǎo)各種通信系統(tǒng)的設(shè)計(jì)，有助于評價(jià)各種系統(tǒng)及編碼的效率。差錯(cuò)符號、差錯(cuò)比特差錯(cuò)符號：由符號發(fā)生差錯(cuò)引起，也叫信號差錯(cuò)，信號差錯(cuò)概率用誤碼元率表示；差錯(cuò)比特：由信息比特發(fā)生差錯(cuò)引起，也叫信息差錯(cuò)，信息差錯(cuò)概率用誤比特率表示；對于二進(jìn)制傳輸系統(tǒng)，符號差錯(cuò)等效于比特差錯(cuò)；對于多進(jìn)制系統(tǒng)，一個(gè)符號差錯(cuò)到底對應(yīng)多少比特差錯(cuò)卻難以確定。因?yàn)橐粋€(gè)符號由多個(gè)比特組成。10誤碼率/差錯(cuò)率根據(jù)不同的應(yīng)用場合對差錯(cuò)率有不同的要求:在電報(bào)傳送時(shí),允許的比特差錯(cuò)率約為:10－4～10－5；計(jì)算機(jī)數(shù)據(jù)傳輸,一般要求比特差錯(cuò)率小于:10－8～10－9；在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯(cuò)率11通常，降低誤碼率可采取兩方面的措施：一是降低信道本身引起的誤碼率。二是采用差錯(cuò)控制、糾錯(cuò)編碼技術(shù)。差錯(cuò)圖樣（errorpattern）為了定量地描述信號的差錯(cuò)，定義收、發(fā)碼之“差”為： 差錯(cuò)圖樣E＝發(fā)碼C－收碼R

（模M）例：8進(jìn)制(M=8)碼元， 若發(fā)碼 C=（0,2,5,4,7,5,2） 收碼變?yōu)?R=（0,1,5,4,7,5,4） 差錯(cuò)圖樣 E=C－R=（0,1,0,0,0,0,6）（模8）12差錯(cuò)圖樣（errorpattern）二進(jìn)制碼：E=CR或

C=RE

，差錯(cuò)圖樣中的“１”既是符號差錯(cuò)也是比特差錯(cuò)，差錯(cuò)的個(gè)數(shù)叫漢明距離。13設(shè)發(fā)送的碼字C1111111111

接收的碼字R1001001111

差錯(cuò)的圖樣E0110110000差錯(cuò)圖樣中的“1”既是符號差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。0:傳輸中無錯(cuò)1:傳輸中有錯(cuò)

差錯(cuò)類型隨機(jī)差錯(cuò)：差錯(cuò)是相互獨(dú)立的,不相關(guān)，以相等的概率獨(dú)立發(fā)生于各碼字、各碼元、各比特存在這種差錯(cuò)的信道是無記憶信道或隨機(jī)信道----(較多恒參信道)突發(fā)差錯(cuò)：指成串出現(xiàn)的錯(cuò)誤,錯(cuò)誤間有相關(guān)性,一個(gè)差錯(cuò)往往要影響到后面一串字----(隨參信道)差錯(cuò)碼元開頭、以差錯(cuò)碼元結(jié)尾，之間并不是每個(gè)碼元都錯(cuò)，而是碼元差錯(cuò)概率超過了某個(gè)額定值E:001001000000

10011100000

14突發(fā)長度=4突發(fā)長度=6糾錯(cuò)碼分類15從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò)糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò)糾錯(cuò)碼與檢錯(cuò)碼在理論上沒有本質(zhì)區(qū)別,只是應(yīng)用場合不同,而側(cè)重的性能參數(shù)也不同。糾錯(cuò)碼分類對信息序列的處理方法：分組碼、卷積碼碼元與原始信息位的關(guān)系：線性碼、非線性碼差錯(cuò)類型：糾隨機(jī)差錯(cuò)碼、糾突發(fā)差錯(cuò)碼、介于中間的糾隨機(jī)/突發(fā)差錯(cuò)碼。構(gòu)碼理論：代數(shù)碼、幾何碼、算術(shù)碼、組合碼等16檢錯(cuò)與糾錯(cuò)舉例0:晴,1:雨若1→0,0→1。收端無法發(fā)現(xiàn)錯(cuò)誤1700晴1001110011雨能發(fā)現(xiàn)一個(gè)錯(cuò)誤禁用碼組插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。檢錯(cuò)與糾錯(cuò)舉例18000晴010001111000111雨晴在只有1位錯(cuò)碼的情況下,可以判決哪位是錯(cuò)碼并予以糾正,可以檢出2位或2位以下的錯(cuò)碼，但糾錯(cuò)能力有限，比如111000。100011101110雨擇多譯碼糾錯(cuò)編碼的基本思路糾錯(cuò)能力的獲取歸結(jié)為兩條：一條是利用冗余度，另一條是噪聲均化（隨機(jī)化、概率化）19冗余度就是在信息流中插入冗余比特。例：3bit表示4種意義。1、增加碼長N例：設(shè)某BSC信道誤碼率Pe=0.01，假如編碼后的糾錯(cuò)能力是10%。先設(shè)碼長N=10，碼字中多于1位誤碼時(shí)就會產(chǎn)生譯碼差錯(cuò)，差錯(cuò)概率為：糾錯(cuò)編碼的基本思路2、噪聲均化就是讓差錯(cuò)隨機(jī)化，就是設(shè)法將危害較大的、較為集中的噪聲干擾分?jǐn)傞_來。卷積：卷積碼在一定約束長度內(nèi)的若干碼字之間加進(jìn)了相關(guān)性，譯碼時(shí)不是根據(jù)單個(gè)碼字，而是一串碼字，這樣就可以將噪聲分?jǐn)偟酱a字序列而不是一個(gè)碼字上。交錯(cuò)：交錯(cuò)是對付突發(fā)差錯(cuò)的有效措施。如果保持碼率不變，將碼長增加到N=40，那么當(dāng)碼字中多于4位誤碼時(shí)，會產(chǎn)生譯碼差錯(cuò)，差錯(cuò)的概率為信道編碼（糾錯(cuò)編碼）在被傳輸信息中附加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關(guān)系加以校驗(yàn),以檢測和糾正錯(cuò)誤。信源編碼減少了冗余度冗余度是隨機(jī)的、無規(guī)律的信道（糾錯(cuò)）編碼增加了冗余度冗余度是特定的、有規(guī)律的,故可利用其在接收端進(jìn)行檢錯(cuò)和糾錯(cuò)。21傳輸冗余比特必然要占用更多的資源。時(shí)間：比如一個(gè)比特重復(fù)發(fā)幾次,或一段消息重復(fù)發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。頻帶：插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號傳遞速率(波特率),結(jié)果就占用了更大的帶寬。功率：采用多進(jìn)制符號,用8進(jìn)制ASK符號代替4進(jìn)制ASK符號來傳送2比特信息,可騰出位置另傳1冗余比特。8進(jìn)制ASK符號的平均功率肯定比4進(jìn)制時(shí)要大,這就是動(dòng)用冗余的功率資源來傳輸冗余比特。設(shè)備復(fù)雜度：加大碼長,采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實(shí)施糾錯(cuò)編碼的有效方法,代價(jià)是算法復(fù)雜度的提高,需動(dòng)用設(shè)備資源。22差錯(cuò)控制系統(tǒng)分類前向糾錯(cuò)（FEC）：發(fā)端信息經(jīng)糾錯(cuò)編碼后傳送，收端通過糾錯(cuò)譯碼自動(dòng)糾正傳遞過程中的差錯(cuò)反饋重發(fā)（ARQ）：收端通過檢測接收碼是否符合編碼規(guī)律來判斷，如判定碼組有錯(cuò)，則通過反向信道通知發(fā)端重發(fā)該碼混合糾錯(cuò)（HEC）：前向糾錯(cuò)和反饋重發(fā)的結(jié)合，發(fā)端發(fā)送的碼兼有檢錯(cuò)和糾錯(cuò)兩種能力231.前向糾錯(cuò)方式前向糾錯(cuò)方式：FEC(ForwardError-Correction)。利用糾錯(cuò)碼自動(dòng)糾正收端檢出的錯(cuò)誤。

FEC方式的優(yōu)點(diǎn)是：無需反饋信道，傳信率恒定，譯碼延時(shí)恒定，有利于實(shí)時(shí)處理和同步。

FEC方式的缺點(diǎn)是：如果糾大量的錯(cuò)誤，必須插入較多的監(jiān)督碼元，編碼效率低，需增加相應(yīng)的信道容量，或使用高效碼，對于高可靠性通信，選擇適用的糾錯(cuò)碼及其譯碼算法往往比較困難。自動(dòng)請求重傳系統(tǒng)有三種：停發(fā)等侯重發(fā)返回重發(fā)選擇重發(fā)停發(fā)等候重發(fā)

停發(fā)等候重發(fā)方式在兩個(gè)碼組之間有停頓時(shí)間（T1），使傳輸效率受到影響，但由于工作原理簡單，在計(jì)算機(jī)數(shù)據(jù)通信中仍得到應(yīng)用過程演示即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TW發(fā)送端在TW時(shí)間內(nèi)送出一個(gè)碼組給接收端接收端進(jìn)行檢驗(yàn)即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TWACKT1接收端未發(fā)現(xiàn)錯(cuò)誤，則發(fā)回一個(gè)認(rèn)可信號（ACK）給發(fā)送端兩碼組之間有停頓時(shí)間T1即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TW發(fā)送端收到信號ACK后再發(fā)出下一個(gè)碼組ACKT12233即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TWACKT1223如果接收端檢測出錯(cuò)誤，則發(fā)回一個(gè)否認(rèn)信號NAK發(fā)現(xiàn)錯(cuò)誤3NAK發(fā)送端收到信號后重發(fā)前一個(gè)碼組即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TWACKT12233發(fā)現(xiàn)錯(cuò)誤NAK3返回返回重發(fā)

返回重發(fā)系統(tǒng)比停發(fā)等候重發(fā)系統(tǒng)有很大改進(jìn)，在許多數(shù)據(jù)傳輸系統(tǒng)中得到應(yīng)用過程演示1發(fā)送端接收端發(fā)送端無停頓地送出一個(gè)又一個(gè)碼組給接收端不再等候ACK信號123411發(fā)送端接收端234發(fā)現(xiàn)錯(cuò)誤一旦接收端發(fā)現(xiàn)錯(cuò)誤便發(fā)回NAK信號34253NAK6TW11發(fā)送端接收端2234發(fā)現(xiàn)錯(cuò)誤34NAK34562TW發(fā)送端重發(fā)下一個(gè)碼組時(shí)先重發(fā)前N段碼組11接收端2234發(fā)現(xiàn)錯(cuò)誤34NAK34562TW2345645623789101145678從碼組2開始重發(fā)發(fā)送端返回11發(fā)送端接收端2234發(fā)現(xiàn)錯(cuò)誤34NAK34562TW2345645623789101145678從碼組2開始重發(fā)N=5選擇重發(fā)

選擇重發(fā)系統(tǒng)傳輸效率最高，但另一方面價(jià)格也最貴，應(yīng)為它要求較為復(fù)雜的控制,在發(fā)送、接收端都要求數(shù)據(jù)緩存器。

此外，重發(fā)系統(tǒng)和返回重發(fā)系統(tǒng)都需要全雙工的鏈路，而停發(fā)等後系統(tǒng)只要求半雙工的鏈路。過程演示1發(fā)送端接收端發(fā)送端無停頓的送出一個(gè)又一個(gè)碼組給接收端不再等候ACK信號123411發(fā)送端接收端234發(fā)現(xiàn)錯(cuò)誤一旦接收端發(fā)現(xiàn)錯(cuò)誤便發(fā)回NAK信號。這幾步和返回重發(fā)是一樣的。34253NAK6TW11發(fā)送端接收端234發(fā)現(xiàn)錯(cuò)誤34253NAK6TW發(fā)送端重發(fā)有錯(cuò)誤的一組。（而返回重發(fā)要重發(fā)前面所有的碼組）4211接收端2234發(fā)現(xiàn)錯(cuò)誤34NAK34562TW27891045627111213141589101112只重發(fā)碼組2發(fā)送端返回43混合糾錯(cuò)(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測能力的碼組,收端收到碼組后,檢查差錯(cuò)情況,如果差錯(cuò)在碼的糾錯(cuò)能力以內(nèi),則自動(dòng)進(jìn)行糾正。如果信道干擾很嚴(yán)重,錯(cuò)誤很多,超過了碼的糾錯(cuò)能力,但能檢測出來,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。信息反饋(IRQ)：收端把收到的數(shù)據(jù),原封不動(dòng)地通過反饋信道送回到發(fā)端,發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù),從而發(fā)現(xiàn)錯(cuò)誤,并且把錯(cuò)誤的消息再次傳送,直到發(fā)端沒有發(fā)現(xiàn)錯(cuò)誤為止。有噪信道編碼的譯碼準(zhǔn)則實(shí)際的信道傳輸過程中，差錯(cuò)的發(fā)生往往不可避免；錯(cuò)誤概率和信道統(tǒng)計(jì)特性等相關(guān)；選擇合適的譯碼規(guī)則能降低差錯(cuò)。

[例]錯(cuò)誤概率與譯碼規(guī)則有關(guān)01XY01二元對稱信道錯(cuò)誤概率不僅與信道的統(tǒng)計(jì)特征有關(guān)，而且也與譯碼規(guī)則有關(guān)。信道編碼以及譯碼將信道用圖5-1所示的模型表示。信道編碼器信道信道譯碼器uxy信道模型

信源輸出序列u，經(jīng)信道編碼器編成碼字x=f(u)并輸入信道，由于干擾，信道輸出y，信道譯碼器對y估值得

=F(y)

。

譯碼器的任務(wù)是從受損的信息序列中盡可能正確地恢復(fù)出原信息。兩種常用譯碼規(guī)則信道總不可避免會攙雜噪聲，所以信息在信道傳輸過程中，差錯(cuò)是不可避免的。選擇合適的譯碼規(guī)則可以彌補(bǔ)信道的不足。1．最大后驗(yàn)概率譯碼準(zhǔn)則發(fā)送碼矢xk，其發(fā)送概率為q(xk)，通過信道轉(zhuǎn)移概率為p(y︱xk)的信道傳輸，接收到矢量y，信道譯碼器輸出

通信過程可用圖5－5所示框圖表示。信源信道編碼器信道信道譯碼器信宿干擾{xk}{y}圖5－5通信過程框圖

當(dāng)估值≠xk時(shí)，就產(chǎn)生了誤碼，用（x︱y）表示后驗(yàn)概率，則收到y(tǒng)估錯(cuò)的概率為

（5-2）

通信總希望錯(cuò)誤概率最小，由式(5-2)可看出錯(cuò)誤概率pe

(xk)最小等同于后驗(yàn)概率（xk︱y）最大，這就是最大后驗(yàn)概率譯碼準(zhǔn)則。

根據(jù)概率關(guān)系式

（5-3）

根據(jù)式（5-3）后驗(yàn)概率（x︱y）最的就意味著p（x

y）全概率最大，因此最大后驗(yàn)概率譯碼準(zhǔn)則也稱為最大聯(lián)合概率譯碼準(zhǔn)則?！纠?.5】信源分布，信道轉(zhuǎn)移概率矩陣,信道輸出符號Y={y1,y2,y3}，按最大后驗(yàn)概率準(zhǔn)則譯碼。(1)根據(jù)p(xy)=p(y︱x)q(x)算出全概率，用矩陣表示

(2)根據(jù)，算出[（y）]=[0.380.340.28]

(3)再由算出后驗(yàn)概率，用矩陣表示

(4)按最大后驗(yàn)概率準(zhǔn)則譯碼，在后驗(yàn)概率矩陣中，每列選一最大值（矩陣中帶下劃線的值），譯為

(5)若按最大聯(lián)合概率譯碼準(zhǔn)則譯碼，在全概率矩陣[p(xy)]中每列選一最大值（矩陣中帶下劃線的值），也可譯出

最大后驗(yàn)概率譯碼準(zhǔn)則存在問題：

不易實(shí)現(xiàn),對于信道，可以獲知統(tǒng)計(jì)特性P（y/x）,但難以獲得信源分布p（x），因此無法求得全概率p（xy）；

而獲得后驗(yàn)概率（收發(fā)）也很困難。

在實(shí)際應(yīng)用中，一般按最大信道轉(zhuǎn)移概率來確定估值，即在收到矢量y后，在所有的xm(m=1,2,…,M)中,選一個(gè)轉(zhuǎn)移概率p(y︱xm)最大的xm值，作為對y的估值=xk，這一譯碼規(guī)則稱為極大似然譯碼規(guī)則。2．極大似然譯碼準(zhǔn)則---退而求其次已知接收序列的條件下使先驗(yàn)概率最大的譯碼算法實(shí)際應(yīng)用中，能夠獲知信道的統(tǒng)計(jì)特性p(y/x)，所以可根據(jù)信道轉(zhuǎn)移概率來確定碼字估值。3．平均錯(cuò)誤概率

（5-4）

【例5.6】計(jì)算[例5.5]的平均錯(cuò)誤概率，若信源等概分布，對其譯碼，并求平均錯(cuò)誤概率。

()?=-=Mjkj1)(1yxyfw（1）求平均錯(cuò)誤概率pe根據(jù)式（6-4）得=0.01+0.12+0.07+0.12+0.1+0.02=0.44(2)當(dāng)信源等概分布，按最大似然函數(shù)譯碼準(zhǔn)則譯碼，[例5.5]已給出信道轉(zhuǎn)移概率矩陣在矩陣的每列中選一最大值(矩陣中帶下劃線的值)，譯碼為平均錯(cuò)誤概率最優(yōu)譯碼與最大似然譯碼譯碼器的任務(wù)是從受損的信息序列中盡可能正確地恢復(fù)出原信息。譯碼算法的已知條件是：實(shí)際接收到的碼字序列{r},r=(r1,r2,…,rN)發(fā)端所采用的編碼算法和該算法產(chǎn)生的碼集XN，滿足信道模型及信道參數(shù)。55最優(yōu)譯碼：最大后驗(yàn)概率譯碼準(zhǔn)則最佳譯碼，也叫最大后驗(yàn)概率譯碼(MAP:Maximumaposteriori)已知r的條件下找出可能性最大的發(fā)碼作為譯碼估值,通過經(jīng)驗(yàn)與歸納推測發(fā)碼的方法56

消息組mi

碼字ci

接收碼r

估值

消息編碼器信道譯碼消息還原最大后驗(yàn)概率譯碼準(zhǔn)則等同于最小傳輸錯(cuò)誤概率準(zhǔn)則57

消息組mi

碼字ci

接收碼r

估值

消息編碼器信道譯碼消息還原存在問題：

不易實(shí)現(xiàn),對于信道，可以獲知統(tǒng)計(jì)特性P（y/x）,但難以獲得信源分布p（x），因此無法求得全概率p（xy）；

而獲得后驗(yàn)概率（收發(fā)）也很困難。

已收到碼為條件的條件概率全概率、聯(lián)合概率，也等同于最大聯(lián)合概率譯碼準(zhǔn)則次最優(yōu)：最大似然譯碼準(zhǔn)則最大似然譯碼(MLD:MaximumLikelihoodDecoding)已知r的條件下使先驗(yàn)概率最大的譯碼算法實(shí)際應(yīng)用中，能夠獲知信道的統(tǒng)計(jì)特性p(y/x)，但很難獲得信源分布P(x),無法求得全概率p(xy)所以根據(jù)信道轉(zhuǎn)移概率來確定碼字估值。58最優(yōu)譯碼與最大似然譯碼的關(guān)系如果構(gòu)成碼集的2K個(gè)碼字以相同概率發(fā)送，滿足P(ci)=1/2K

，i=1,2,…,2K

P(r)對于任何r都有相同的值，滿足P(r)=1/2K

則P(ci/r)最大等效于P(r/ci)的最大，在此前提下最佳譯碼等效于最大似然譯碼。59最優(yōu)譯碼與最大似然譯碼對于無記憶信道，

[例]：BSC信道的最大似然譯碼可以簡化為最小漢明距離譯碼。漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對稱的，只要發(fā)送的碼字獨(dú)立、等概率，漢明距離譯碼也就是最佳譯碼。

60[例]已知信道矩陣并設(shè)p(x1)=1/2,p(x2)=p(x3)=1/4,分別用最小錯(cuò)誤概率準(zhǔn)則和最大似然譯碼準(zhǔn)則確定相應(yīng)的譯碼規(guī)則，并計(jì)算平均錯(cuò)誤概率。解：由于輸入符號不是等概率分布，所以對于最小錯(cuò)誤概率準(zhǔn)則必須根據(jù)聯(lián)合概率的大小來選擇。p(x1y1)=1/4,p(x2y1)=1/24,p(x3y1)=1/12p(x1y2)=1/6,p(x2y2)=1/8,p(x3y2)=1/24p(x1y3)=1/12,p(x2y3)=1/12,p(x3y3)=1/8故譯碼規(guī)則是F(y1)=x1,F(y2)=x1,F(y3)=x3對于最大似然譯碼準(zhǔn)則，可以直接從信道矩陣的傳遞概率來選擇，譯碼規(guī)則是F(y1)=x1,F(y2)=x2,F(y3)=x3平均錯(cuò)誤概率為pE=1/24+1/12+1/6+1/24+1/12+1/12=12/24p’E=1/24+1/12+1/8+1/24+1/12+1/12=11/24<pE64選擇最佳譯碼規(guī)則只能使錯(cuò)誤概率pE有限地減小，無法使其任意的小。要想進(jìn)一步減小錯(cuò)誤概率，必須優(yōu)選信道編碼方法。[例]已知信道轉(zhuǎn)移矩陣如下，試確定譯碼規(guī)則。解只知轉(zhuǎn)移概率，無法找出最佳譯碼規(guī)則，只能采用最大似然譯碼規(guī)則。將轉(zhuǎn)移概率矩陣各列最大的值標(biāo)出，重寫轉(zhuǎn)移矩陣如下：

按轉(zhuǎn)移概率最大原則確定最大似然譯碼規(guī)則如下：

盡管一般情況下并不知道這樣譯碼的差錯(cuò)率。但可以證明，當(dāng)信道輸入等概時(shí)，最大似然譯碼規(guī)則也是最佳的。糾錯(cuò)碼的數(shù)學(xué)基礎(chǔ)：

矢量空間與碼空間基本的糾錯(cuò)碼為（n,k）分組碼（塊碼）每塊為k個(gè)符號由n個(gè)碼元組成碼字碼字可視為n重矢量（n個(gè)矢量元素）67矢量空間與碼空間F表示碼元所在的數(shù)域(對于二進(jìn)制碼，F(xiàn)代表二元域{0,1})設(shè)n重有序元素的集合V={Vi

},若滿足條件：V中矢量元素在矢量加運(yùn)算下構(gòu)成加群；V中矢量元素與數(shù)域F元素的標(biāo)乘封閉在V中；分配律、結(jié)合律成立，則稱集合V是數(shù)域F上的n維矢量空間，或稱n維線性空間，n維矢量又稱n重(n-tuples)。68矢量空間中矢量的關(guān)系

對于域F上的若干矢量線性組合：

線性相關(guān)：

其中任一矢量可表示為其它矢量的線性組合線性無關(guān)或線性獨(dú)立：一組矢量中的任意一個(gè)都不可能用其它矢量的線性組合來代替.69矢量空間與基底一組線性無關(guān)的矢量，其線性組合的集合就構(gòu)成了一個(gè)矢量空間V，這組矢量就是這個(gè)矢量空間的基底。n維矢量空間應(yīng)包含n個(gè)基底基底不是唯一的，例：線性無關(guān)的兩個(gè)矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可張成同一個(gè)兩維空間。70二元域GF(2)上三重矢量空間以（100）為基底可張成一維三重子空間V1，含21=2個(gè)元素，即以(010)(001)為基底可張成二維三重子空間V2，含22=4個(gè)元素，即以(100)(010)(001)為基底可張成三維三重空間V,含23=8個(gè)元素，V1和V2都是V的子空間。71概念重?cái)?shù)構(gòu)成矢量的有序元素的個(gè)數(shù)維數(shù)構(gòu)成矢量空間的基底的個(gè)數(shù)72矢量空間每個(gè)矢量空間或子空間中必然包含零矢量兩個(gè)矢量正交：V1V2＝0兩個(gè)矢量空間正交：某矢量空間中的任意元素與另一矢量空間中的任意元素正交正交的兩個(gè)子空間V1、V2互為對偶空間

(DualSpace)，其中一個(gè)空間是另一個(gè)空間的零空間（nullspace，也稱零化空間）。73碼空間

74

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

qk

種分組編碼器qn種

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

通常qn>>qk，分組編碼的任務(wù)是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個(gè)構(gòu)成一個(gè)碼空間，其元素就是許用碼的碼集。分組編碼的任務(wù)選擇一個(gè)ｋ維n重子空間作為碼空間。確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構(gòu)成了不同的分組碼。75隨機(jī)編碼編碼的分析設(shè)計(jì)途徑：1.數(shù)學(xué)解析途徑，即將代數(shù)、幾何、數(shù)論等理論運(yùn)用到編解碼，如分組碼，卷積碼。2.運(yùn)用概率統(tǒng)計(jì)方法在特定信道條件下對編碼信號的性能作出統(tǒng)計(jì)分析，求出差錯(cuò)概率的上下限邊界，其中最優(yōu)碼所能達(dá)到的差錯(cuò)概率上界稱作隨機(jī)碼界。用這種方法不能得知最優(yōu)碼是如何具體編出來的，卻能得知最優(yōu)碼可以好到什么程度，并進(jìn)而推導(dǎo)出有擾離散信道的編碼定理，對指導(dǎo)編碼技術(shù)具有特別重要的理論價(jià)值。76隨機(jī)編碼對于一個(gè)(N,K)分組編碼器對K個(gè)q進(jìn)制組成的消息組m=(m0,m1,…,mk-1)編碼；生成N個(gè)q進(jìn)制符號組成的碼字c=(c0,c1,…cN-1)；在(N,K)分組編碼器中隨機(jī)選定的碼集有qNM種一個(gè)消息組的編碼有qN種選擇（N個(gè)碼元，q進(jìn)制）qK個(gè)消息組共有種選擇令M=qK，可得上式77隨機(jī)編碼在(N,K)分組編碼器中隨機(jī)選定的碼集有