【正文】 （）其中，r為碼符號(hào)個(gè)數(shù)，為碼長(zhǎng)，q為信源符號(hào)個(gè)數(shù)。 惟一可譯碼判斷準(zhǔn)則在前面的闡述中，雖然給出了判斷惟一可譯碼的方法，但在應(yīng)用中卻十分困難，下面引用一種判別惟一可譯碼的準(zhǔn)則，該準(zhǔn)則是薩得納斯和彼得森設(shè)計(jì)出來(lái)的，內(nèi)容如下：設(shè)為原始碼字的集合，再構(gòu)造一系列集合。若碼字是碼字的前綴，即，則將后綴A列為中的元素，就是由所有具有這種性質(zhì)的A構(gòu)成的集合。若有碼字，且W是的前綴，即U=WA，則取后綴A為中的元素。這樣就可構(gòu)成集合。所以，一種碼是惟一可譯碼的充要條件是中沒(méi)有一個(gè)含有中的碼字。從提高有效性的觀點(diǎn)來(lái)考慮，希望選擇由短的碼符號(hào)組成的 碼字，就是用碼長(zhǎng)作為選擇準(zhǔn)則，為此引進(jìn)碼的平均長(zhǎng)度。定義：若信源的熵給定，編碼后每個(gè)信源符號(hào)平均用個(gè)碼元來(lái)變換。無(wú)失真信源編碼的核心問(wèn)題就是尋找緊致碼。式（），（），（），（）參見(jiàn)文獻(xiàn)[9] 變長(zhǎng)碼的編碼方法常用的變長(zhǎng)碼的編碼方法有如下三種：香農(nóng)（Shannon）編碼法、費(fèi)諾（Fano）編碼法、霍夫曼（Huffman）編碼法。費(fèi)諾編碼法也不是一種最佳編碼法，但用這種方法有時(shí)候也能找到緊致碼。 香農(nóng)編碼香農(nóng)第一定理指出，選擇每個(gè)碼字的長(zhǎng)度，使之滿足式的整數(shù)，就可以得到惟一可譯碼，這種編碼方法稱為香農(nóng)編碼?？梢?jiàn)，香農(nóng)編碼剩余度稍大，實(shí)用性不強(qiáng)，但有重要的理論意義。 將信源發(fā)出的q個(gè)消息符號(hào)按其概率的遞減次序依次排列。 按下式計(jì)算第i個(gè)信源符號(hào)的二進(jìn)制碼字的碼長(zhǎng)，并取整。 為了編成惟一可譯碼，首先計(jì)算第i個(gè)信源符號(hào)的累加概率178。178。 （取整） 費(fèi)諾編碼費(fèi)諾（Fano）編碼方法屬于概率匹配編碼，但它不是最佳的編碼方法。費(fèi)諾碼的編碼過(guò)程如下：178。 將依次排列好的信源符號(hào)按編碼進(jìn)制數(shù)分組，使每組概率和盡可能接近或相等，并給每組各賦予一個(gè)碼元。178。178。信源符號(hào)所對(duì)應(yīng)的碼元序列（從左到右）則為費(fèi)諾碼。其中從編碼效率比較，Huffman編碼方案被認(rèn)為是最佳方案，因?yàn)槠淦骄a長(zhǎng)接近信源熵?；舴蚵℉uffman）提出了一種構(gòu)造緊致碼的方法，它是一種最佳的逐個(gè)符號(hào)的編碼方法，其編碼效率較高。 將信源S發(fā)出的q個(gè)消息符號(hào)按其概率的遞減次序依次排列，即178。178。178。將這最后兩個(gè)信源符號(hào)分別用0和1碼元表示?；舴蚵幋a方法中每一步得到的都是緊致碼，因而信源S的霍夫曼碼一定是緊致碼。造成非惟一的原因如下：178。但它們只是碼字具體形式不同，而其碼長(zhǎng)不變，所以碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)差別。 若當(dāng)縮減信源中縮減合并后的符號(hào)的概率與其他信源符號(hào)概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序時(shí)，其位置放置次序時(shí)可以任意的，故會(huì)得到不同的霍夫曼碼?；舴蚵a具有以下兩個(gè)明顯特點(diǎn)，這兩各特點(diǎn)保證了所得到的霍夫曼碼一定是緊致碼：178。178。參見(jiàn)文獻(xiàn)[9]。通信系統(tǒng)中將各個(gè)部分的躁聲或干擾等效成從信道輸入?？梢詫⑿诺揽醋鍪且粋€(gè)變換器，它將輸入消息x變換成y，以信道轉(zhuǎn)移概率來(lái)描述信道的統(tǒng)計(jì)特性。信道 圖1 離散信道的數(shù)學(xué)模型圖1中輸入和輸出信號(hào)均用隨機(jī)矢量表示，輸入信號(hào)，輸出信號(hào)，其中i=1, 2 N表示時(shí)間或空間的離散值。另外，上圖輸入信號(hào)和輸出信號(hào)之間統(tǒng)計(jì)依賴關(guān)系由條件來(lái)描述，信道噪聲與干擾的影響也包含在之中，反映了信道的統(tǒng)計(jì)特性。它是由于信道噪聲引起的，描述了信道噪聲的特性。有時(shí)把稱為輸入符號(hào)的先驗(yàn)概率，而把對(duì)應(yīng)地把稱為輸入符號(hào)的后驗(yàn)概率。178。178。178。178。根據(jù)統(tǒng)計(jì)特性，即信道轉(zhuǎn)移概率的不同，信道又可分為以下兩種。 無(wú)記憶信道：信道的輸出y只與當(dāng)前時(shí)刻的輸入x有關(guān)。 有記憶信道：信道的輸出y不僅與當(dāng)前時(shí)刻的輸入有關(guān)，還與以前的輸入有統(tǒng)計(jì)關(guān)系。解決這一問(wèn)題，一般采用冗余編碼方法，即按照一定的編碼規(guī)則事先給信碼加上一定的冗余度（檢測(cè)位），賦予信道編碼自身一定的糾錯(cuò)和檢錯(cuò)能力，只要采取適當(dāng)?shù)男诺谰幋a和譯碼措施，就可使信道傳輸?shù)腻e(cuò)誤概率降到允許的范圍之內(nèi)。由此可以計(jì)算出它的信道容量C，只要在信道中實(shí)際傳送的信息率RC，在接收端就應(yīng)當(dāng)能夠無(wú)差錯(cuò)地譯出發(fā)送端所傳送的信息。 信道編碼的編碼對(duì)象是信源編碼器輸出的信息序列N，信道編碼就是按一定的規(guī)則給信息序列N增加一些多余的碼元，使不具有規(guī)律性的信息序列N變換為具有某種規(guī)律性的碼序列X。根據(jù)相關(guān)性來(lái)檢測(cè)和糾正傳輸過(guò)程中產(chǎn)生的差錯(cuò)就是信道編碼的基本思想。其組成由k為信息位的線性組合決定nk個(gè)監(jiān)督位。 可根據(jù)信道特征提出誤差率指標(biāo)，由糾錯(cuò)定理、漢明界限和最小漢明距離，取得加入滿足要求的冗余（監(jiān)督）位r=nk。 設(shè)計(jì)nk=r個(gè)獨(dú)立線性方程，并均由信碼模2加構(gòu)成，然后抽出系數(shù)得到。 由H得到G。 接收伴隨式糾錯(cuò)：（1）在差錯(cuò)控制能力內(nèi)，S必為H中某一列，可自動(dòng)糾錯(cuò)。（3）若超出糾錯(cuò)能力，也可能S仍為H中某列，于是自動(dòng)“糾錯(cuò)”會(huì)糾而更錯(cuò)。在所有的譯碼規(guī)則中，不是每一種譯碼規(guī)則都使合理的。l 最小錯(cuò)誤概率譯碼規(guī)則 譯碼規(guī)則最基本的準(zhǔn)則就是要使錯(cuò)誤概率為最小。在確定譯碼規(guī)則后，若信道輸出端接收到的符號(hào)為，則一定譯成。收到符號(hào)條件下譯碼的條件正確概率為令為條件錯(cuò)誤概率，其中e表示除了以外的所有輸入符號(hào)的集合。它是條件錯(cuò)誤概率對(duì)Y空間求統(tǒng)計(jì)平均值，即 （）下面選擇譯碼函數(shù)： （）使之滿足條件 （）或則稱這個(gè)譯碼規(guī)則為最大后驗(yàn)概率譯碼規(guī)則，或最大聯(lián)合概率譯碼規(guī)則，或最小錯(cuò)誤概率譯碼規(guī)則。l 最大似然譯碼規(guī)則一般情況下，求解后驗(yàn)概率或聯(lián)合概率比較麻煩，應(yīng)用不方便。選擇譯碼函數(shù) （）使?jié)M足 （）于是引入最大似然譯碼規(guī)則。在輸入符號(hào)等概率時(shí)，這兩個(gè)譯碼規(guī)則時(shí)等價(jià)的。最大似然譯碼規(guī)則本身不再依賴于先驗(yàn)概率。根據(jù)譯碼準(zhǔn)則，進(jìn)一步可寫(xiě)出平均錯(cuò)誤概率，即 （）上式中求和號(hào)表示對(duì)輸入符號(hào)集X中除以外的所有元素求和。求和式除去每列對(duì)應(yīng)于的那一項(xiàng)后，求矩陣中其余元素之和。第四章 多信源的信息傳輸前面所涉及的都是只有一個(gè)信源和一個(gè)信宿的單向通信的單用戶通信系統(tǒng)。當(dāng)信息在網(wǎng)絡(luò)通信系統(tǒng)中多用戶和多方向流通時(shí)，如何讓信息有效而可靠地傳輸，這與單信源、單信道時(shí)的情況有很大的不同，需要討論網(wǎng)絡(luò)信息論等問(wèn)題。在實(shí)際通信系統(tǒng)中，常常是某個(gè)信宿收到來(lái)自不同的編碼消息。當(dāng)信源彼此是獨(dú)立時(shí)，就分別處理，多個(gè)信源編碼問(wèn)題就簡(jiǎn)化成幾個(gè)單信源通信情況的信源編碼問(wèn)題；當(dāng)信源彼此相關(guān)時(shí)，由于各個(gè)信源所處的作用位置不同，就出現(xiàn)了各種相關(guān)信源編碼模型，下面介紹兩個(gè)相關(guān)信源編碼。圖2中的信源產(chǎn)生信源序列，信源產(chǎn)生信源序列，分別送入編碼器1和2進(jìn)行編碼，而(i=1,2,j=1,2)是編碼器到譯碼器的信息傳輸率，分別為譯碼器輸出的估計(jì)值。對(duì)上圖中相關(guān)信源如果采用聯(lián)合編碼，則只要聯(lián)合速率（符號(hào)比特率），就能保證譯碼器以任意小的錯(cuò)誤概率恢復(fù)?，F(xiàn)在SlepianWolf證明：對(duì)相關(guān)信源，即使分別單獨(dú)編碼，并在接收端聯(lián)合譯碼，則只要聯(lián)合編碼速率，就能保證以任意小的錯(cuò)誤概率恢復(fù)出 。其中的，分別表示信源與的編碼速率．因此，表示一個(gè)速率對(duì)。若兩個(gè)信源之間統(tǒng)計(jì)相關(guān)，且兩個(gè)信源之間有相互通信聯(lián)絡(luò)。編碼器2對(duì)信源2的輸出進(jìn)行編碼時(shí)可參考信源1送來(lái)的信息，定義信源之間互相提供的信息為邊信息。這里討論單向協(xié)同編碼，例如只有信源1到信源2的信息發(fā)送，而無(wú)反向信息傳遞。接受端利用兩個(gè)編碼器的輸出只恢復(fù)信源1的輸出（而不是兩個(gè)信源的輸出）。收端僅僅由一個(gè)譯碼器譯出不同信源的信息，送給不同的信宿。多源接入信道的各個(gè)信源在地理上是分散的，于是無(wú)論是信源編碼或是信道編碼都必須分散進(jìn)行。 多信源接入信道及其模型多個(gè)不同的信源的信息經(jīng)過(guò)幾個(gè)編碼器后，送入同一信道傳送。從信道上來(lái)看，它是多輸入單輸出信道，如圖所示的離散多址接入信道模型。這類信道最典型的例子就是衛(wèi)星通信的上行線路。因此，為了可靠傳輸，各發(fā)送者不但要考慮克服信道躁聲，而且還要考慮克服各發(fā)送端彼此之間的串?dāng)_。由于網(wǎng)絡(luò)信道有多個(gè)相關(guān)聯(lián)的容量存在，因此，是一個(gè)容量域的問(wèn)題。編碼器2信源編碼器1信源信道譯碼器y圖3 典型的離散無(wú)記憶多址接入信道該信道有兩個(gè)輸入信源的概率空間，分別為，有一個(gè)輸出信源概率空間。多址接入信道可用傳遞概率來(lái)描述。對(duì)含有n個(gè)分量相互獨(dú)立的序列，若分別存在以與比特/符號(hào)的編碼，當(dāng)時(shí)，可使平均譯碼錯(cuò)誤概率，稱此為可達(dá)速率對(duì)，可達(dá)速率對(duì)的集合的閉包定義為多址接入信道的容量區(qū)域。它必定是的概率分布的型凸函數(shù)，可用對(duì)求導(dǎo)的方法求得最大值，這個(gè)最大值與2i有關(guān)。那么，只取 （2i2k） （）就能使達(dá)到最大值，所以在信源