1、數(shù)字通信中的信源編碼和信道編碼摘要：如今社會(huì)已經(jīng)步入信息時(shí)代，在各種信息技術(shù)中，信息的傳輸及通信起著支撐作用。而對(duì)于信息的傳輸，數(shù)字通信已經(jīng)成為重要的手段。本論文根據(jù)當(dāng)今現(xiàn)代通信技術(shù)的發(fā)展，對(duì)信源編碼和信道編碼進(jìn)行了概述性的介紹.關(guān)鍵詞：數(shù)字通信；通信系統(tǒng)；信源編碼；信道編碼Abstract：Now it is an information society. In the all of information technologies, transmission and communication of information take an important effect. For the

2、 transmission of information, Digital communication has been an important means. In this thesis we will present an overview of source coding and channel coding depending on the development of todays communication technologies.Key Words：digital communication; communication system; source coding; chan

3、nel coding1. 前言 通常所謂的“編碼”包括信源編碼和信道編碼。編碼是數(shù)字通信的必要手段。使用數(shù)字信號(hào)進(jìn)行傳輸有許多優(yōu)點(diǎn), 如不易受噪聲干擾, 容易進(jìn)行各種復(fù)雜處理, 便于存貯, 易集成化等。編碼的目的就是為了優(yōu)化通信系統(tǒng)。一般通信系統(tǒng)的性能指標(biāo)主要是有效性和可靠性。所謂優(yōu)化，就是使這些指標(biāo)達(dá)到最佳。除了經(jīng)濟(jì)性外，這些指標(biāo)正是信息論研究的對(duì)象。按照不同的編碼目的，編碼可主要分為信源編碼和信道編碼。在本文中對(duì)此做一個(gè)簡(jiǎn)單的介紹。2. 數(shù)字通信系統(tǒng)通信的任務(wù)是由一整套技術(shù)設(shè)備和傳輸媒介所構(gòu)成的總體通信系統(tǒng)來完成的。電子通信根據(jù)信道上傳輸信號(hào)的種類可分為模擬通信和數(shù)字通信。最簡(jiǎn)單的數(shù)字通信

4、系統(tǒng)模型由信源、信道和信宿三個(gè)基本部分組成。實(shí)際的數(shù)字通信系統(tǒng)模型要比簡(jiǎn)單的數(shù)字通信系統(tǒng)模型復(fù)雜得多。數(shù)字通信系統(tǒng)設(shè)備多種多樣，綜合各種數(shù)字通信系統(tǒng)，其構(gòu)成如圖2-l所示。圖2-1 數(shù)字通信系統(tǒng)模型信源編碼是以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。信道，通俗地說是指以傳輸媒質(zhì)為基礎(chǔ)的信號(hào)通路。具體地說，信道是指由有線或無線電線路提供的信號(hào)通路。信道的作用是傳輸信號(hào)，它提供一段頻帶讓信號(hào)通過，同時(shí)又給信號(hào)加以限制和損害。信道編碼是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通常通過增加信源的冗余度來實(shí)現(xiàn)。采用的一般方法是增大

5、碼率或帶寬。與信源編碼正好相反。在計(jì)算機(jī)科學(xué)領(lǐng)域，信道編碼（channel code）被廣泛用作表示編碼錯(cuò)誤監(jiān)測(cè)和糾正的術(shù)語，有時(shí)候也可以在通信和存儲(chǔ)領(lǐng)域用作表示數(shù)字調(diào)制方式。信道編碼用來在數(shù)據(jù)傳輸?shù)臅r(shí)候保護(hù)數(shù)據(jù)，還可以在出現(xiàn)錯(cuò)誤的時(shí)候來恢復(fù)數(shù)據(jù)。3. 信源編碼一般情況下，信源編碼可分為離散信源編碼、連續(xù)信源編碼和相關(guān)信源編碼。離散信源編碼可做到無失真編碼；而連續(xù)信源編碼則只能做到限失真編碼。3.1 信源編碼的一般模型圖3-1 信源編碼的一般模型如圖3-1所示。如果將編碼器看作是一個(gè)網(wǎng)絡(luò)，則它有2個(gè)輸入和1個(gè)輸出，分別是消息集合X、信道基本符號(hào)集合A和代碼集合C。 設(shè)消息集合共有N個(gè)元素，信道

6、基本符號(hào)共有2種，代碼組集合的元素個(gè)數(shù)為N，則 X=x1，x2，xN A=0，1 C=c1，c2，cN 由信源編碼器的數(shù)學(xué)模型可將信源編碼器的作用歸納為 (1)用信道的基本符號(hào)按照規(guī)定的編碼方法把信源發(fā)出的消息變換成相應(yīng)的代碼組； (2)建立消息集合X與代碼組集合C之間的一一對(duì)應(yīng)關(guān)系。 通常稱具有上述映射規(guī)則的信源編碼器為正規(guī)編碼器，編出來的碼稱為非奇異碼。 由于正規(guī)編碼器一一對(duì)應(yīng)的規(guī)則確保了編碼過程不會(huì)造成信息量的損失，故等效信源的熵必定與初始信源的熵相等。3.2 最佳編碼 通常稱具有最短的代碼組平均長(zhǎng)度或編碼效率接近于1的信源編碼為最佳信源編碼，亦簡(jiǎn)稱為最佳編碼。最佳編碼的目的是提高信道傳

7、輸消息的有效性。 最佳編碼的實(shí)質(zhì)：減小每個(gè)符號(hào)所占用的時(shí)間長(zhǎng)度，即讓每個(gè)碼元所攜帶的信息量最大。最佳編碼的原則：把信源符號(hào)集合中出現(xiàn)概率大的符號(hào)編成長(zhǎng)度較短的代碼組，而把出現(xiàn)概率小的符號(hào)編成長(zhǎng)度較長(zhǎng)的代碼組；信源編碼器輸出的代碼組為單義可譯碼組，即序列中不必使用間隔就能把序列逐個(gè)分成代碼組（因?yàn)殚g隔不攜帶信息量，使用了間隔自然降低了編碼效率）3.3 常見信源編碼3.3.1 香農(nóng)編碼在信源編碼方面，1951年香農(nóng)證明，當(dāng)信源輸出有冗余的消息時(shí)可通過編碼改變信源的輸出，使信息傳輸速率接近信道容量。1948年香農(nóng)就提出能使信源與信道匹配的香農(nóng)編碼。香農(nóng)編碼編碼步驟如下：(1) 將符號(hào)序列ai i=1

8、,2,Nn按概率降序排列;(2) 確定第i個(gè)碼字的碼長(zhǎng) i=1,2,Nn ；(3) 令P(a0)=0，計(jì)算第i-1個(gè)符號(hào)序列的累加概率 i= i=1,2,Nn；(4) 將Pa(ai)用二進(jìn)制表示，取小數(shù)點(diǎn)后li位作為符號(hào)序列ai的碼字ci i=1,2,Nn；香農(nóng)編碼方法特點(diǎn)：由于bi總是進(jìn)一取整，香農(nóng)編碼方法不一定是最佳的；由于第一個(gè)消息符號(hào)的累加概率總是為0，故它對(duì)應(yīng)的碼字總是0、00、000、00的式樣；碼字集合是唯一的，且為即時(shí)碼；先有碼長(zhǎng)再有碼字；對(duì)于一些信源，編碼效率不高，多余度稍大，因此其實(shí)用性受到較大限制。3.3.2 費(fèi)諾編碼費(fèi)諾編碼是一種基于一組符號(hào)及及其或然率（估量或測(cè)量所得

9、），從而構(gòu)建前綴碼的技術(shù)。在理想意義上， 它與哈夫曼編碼一樣，并未實(shí)現(xiàn)碼詞（code word）長(zhǎng)度的最低預(yù)期。然而，與哈夫曼編碼不同的是，它確保了所有的碼詞長(zhǎng)度在一個(gè)理想的理論范圍之內(nèi)。這項(xiàng)技術(shù)是香農(nóng)于1948年，在他介紹信息理論的文章“通信數(shù)學(xué)理論”中被提出的。這個(gè)方法歸功于范諾，他在不久以后以技術(shù)報(bào)告發(fā)布了它。費(fèi)諾編碼不應(yīng)該與香農(nóng)編碼混淆，后者的編碼方法用于證明Shannons noiseless coding theorem，或與ShannonFanoElias coding（又被稱作Elias coding）一起，被看做算術(shù)編碼的先驅(qū)。費(fèi)諾編碼也是一種常見的信源編碼方法。其步驟：(1

10、) 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列，即p(x1) p(x2) p(xn )；(2) 將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和接近于相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和“1”；(3) 將每一大組的信源符號(hào)進(jìn)一步再分成兩個(gè)組，使分解后的兩個(gè)組的概率之和接近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號(hào)“0”和“1”；(4) 如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止； 信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾編碼。費(fèi)諾編碼特點(diǎn)為：概率大，則分解的次數(shù)小；概率小，則分解的次數(shù)多。這符合最佳編碼原則。碼字集合是唯一的。分解完了，碼字出來了，碼長(zhǎng)也有了。因此，費(fèi)諾編碼方法又稱為子集分解法。3.

11、3.3 赫夫曼編碼香農(nóng)編碼算法并非總能得到最優(yōu)編碼。1952年, David A. Huffman提出了一個(gè)不同的算法，這個(gè)算法可以為任何的可能性提供出一個(gè)理想的樹。香農(nóng)編碼是從樹的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)所進(jìn)行的的編碼，赫夫曼編碼算法卻是從相反的方向，即從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的方向編碼的。編碼步驟如下：(1) 將符號(hào)序列ai i=1,2,Nn按概率降序排列；(2) 為概率最小的兩個(gè)符號(hào)序列各自分配一個(gè)二進(jìn)制碼元；(3) 將概率最小的兩個(gè)符號(hào)序列合并成一個(gè)新的符號(hào)序列，用兩者概率之和作為新符號(hào)序列的概率；重復(fù)（1）（2）（3）步驟，直到合并出一個(gè)以1為概率的新符號(hào)序列。分配給符號(hào)序列ai的全部碼元作為該符

12、號(hào)序列的碼字ci i=1,2,Nn。赫夫曼碼的特點(diǎn)：編碼過程中先確定碼字，后確定碼長(zhǎng)；用局部累加概率代替累加概率，多次重新排列合并累加的過程是優(yōu)化過程；每次合并伴之分配碼元保證大概率符號(hào)序列編為短碼，小概率符號(hào)序列編為長(zhǎng)碼；不具有唯一性，但不同赫夫曼碼的編碼效率相同；碼率不超過熵率1/n個(gè)比特，n越大碼率越接近熵率。盡管對(duì)同一信源存在著多種結(jié)果的赫夫曼編碼，但它們的平均碼長(zhǎng)幾乎都是相等的，因?yàn)槊恳环N路徑選擇都是使用最小概率相加的方法，其實(shí)質(zhì)都是遵循最佳編碼的原則，因此赫夫曼編碼是最佳編碼。赫夫曼編碼是一種最佳編碼，實(shí)現(xiàn)也不困難，因此到目前為止它仍是應(yīng)用最為廣泛無失真信源編碼之一。3.3.4 通

13、用編碼對(duì)于統(tǒng)計(jì)特性已知的平穩(wěn)信源，有Huffman碼和算術(shù)碼等高效編碼方法。但是，它們存在以下共同問題：在編碼時(shí)必須知道信源的概率分布，這在許多情況下是不可能的；它們對(duì)無記憶信源較為合適，而實(shí)際應(yīng)用中的信源一般都具有記憶性。因此如何利用信源的記憶性提高它的壓縮率是信源編碼所必需考慮的問題。因而在此簡(jiǎn)單介紹一下通用編碼。通用編碼是指在信源概率分布不知時(shí)，對(duì)其編碼并使編碼效率很高的一種碼。他的基本原理是利用出現(xiàn)數(shù)據(jù)序列前后的相關(guān)性進(jìn)行壓縮。下面簡(jiǎn)單介紹一下通用碼中的一種LZ碼：1965年蘇聯(lián)數(shù)學(xué)家Kolmogolov提出利用信源序列的結(jié)構(gòu)特性來編碼。而兩位以色列研究者J.Ziv和A.Lempel獨(dú)

14、辟蹊徑，完全脫離Huffman及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的通用壓縮算法。將這些算法統(tǒng)稱為L(zhǎng)Z系列算法。LZ碼的基本算法：(1) 將長(zhǎng)度不同的符號(hào)串編成一個(gè)個(gè)新的短語(單詞)，形成短語詞典的索引表；(2) 它是一種分段編碼，其短語詞典是由前面已見到的文本分段來定義的.LZ碼的編碼步驟為：(1) 取第一個(gè)符號(hào)x作為第一段（單詞），記為（0，x）；(2) 從第二個(gè)符號(hào)y起，分段時(shí)先查看是否與前面的短語相同（匹配）：若沒有匹配的，記為（0，y）；若有匹配的符號(hào)，就找從該符號(hào)開始與之匹配的最大長(zhǎng)度L，并使得匹配開始的距離最近，記為（1，L，）；4.

15、信道編碼4.1 信道編碼的基本思想和基本方式經(jīng)過信源編碼后并不能將信號(hào)直接送到傳輸通道發(fā)送出去, 因?yàn)閿?shù)字信號(hào)在傳輸中受到衰減、雜波、干擾等所造成的質(zhì)量劣化是突變性的(模擬信號(hào)質(zhì)量的劣化是漸變的), 也就是說,數(shù)字信號(hào)在衰減、雜波或干擾沒有低于某一門限時(shí), 只要接收設(shè)備能判別出0碼和1碼, 信號(hào)質(zhì)量就不會(huì)受到大的影響, 而一旦超過此門限, 接收設(shè)備判別不出0碼和1碼, 信號(hào)就會(huì)丟失。因此, 在數(shù)字信號(hào)傳輸中最重要的是防止誤碼, 也就是要盡量降低誤碼率。1949年香農(nóng)在有噪聲時(shí)的通信一文中提出了信道容量的概念和信道編碼定理，為信道編碼奠定了理論基礎(chǔ)。無噪信道編碼定理（又稱香農(nóng)第一定理）指出，碼字

16、的平均長(zhǎng)度只能大于或等于信源的熵。有噪信道編碼定理（又稱香農(nóng)第二定理）則是編碼存在定理。它指出只要信息傳輸速率小于信道容量，就存在一類編碼，使信息傳輸?shù)腻e(cuò)誤概率可以任意小。隨著計(jì)算技術(shù)和數(shù)字通信的發(fā)展，糾錯(cuò)編碼和密碼學(xué)得到迅速的發(fā)展。信道編碼的基本思想是：在發(fā)端被傳輸?shù)男畔⑿蛄猩细郊右恍┒嘤嗟臋z驗(yàn)碼元，這些監(jiān)督碼元與信息碼元間以某種特定的規(guī)則相互關(guān)聯(lián)。接收端按照既定的規(guī)則檢驗(yàn)信息碼元與監(jiān)督碼元間的關(guān)系，一但傳輸出錯(cuò)，則兩者間的關(guān)系將會(huì)受到破壞，從而可以發(fā)現(xiàn)錯(cuò)誤，乃至糾正錯(cuò)誤。信道編碼的基本方式是：前向糾錯(cuò)（FEC）、檢錯(cuò)重傳（ARQ）、混合差錯(cuò)控制（HEC）和信息反饋（IRQ）。4.2 常用的

17、信道編碼4.2.1 線性分組碼在分組碼中，編碼后的碼元序列每n位為一組，其中k是信息碼元，r（r=n-k）個(gè)是附加的監(jiān)督碼元。如果信息元與監(jiān)督碼元之間呈線性關(guān)系，則為線性分組碼。奇偶校驗(yàn)碼和漢明碼是典型的線性分組碼。循環(huán)碼是線性分組碼，既可糾錯(cuò)又可檢錯(cuò)。特點(diǎn)是任一碼組的每一次循環(huán)移位得到的是碼中的另一碼組。BCH碼是一類糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼。線性分組碼的簡(jiǎn)單編碼過程如下：（1）構(gòu)造秩為m的mn校驗(yàn)矩陣H。Hri=si. 其中ri為第i個(gè)接收碼字，以n列向量表示。si為第i個(gè)接收碼字的誤碼標(biāo)志，以m列向量表示。使校驗(yàn)矩陣H滿足，當(dāng)ri等于ci時(shí)，Hri=Hci=si=0;當(dāng)ri不等于ci時(shí)，

18、Hri=si!=0；（2）構(gòu)造kn生成矩陣G使校驗(yàn)矩陣H與生成矩陣G之間滿足HGT=0；（3）編碼ci=GTxi，其中xi為第i個(gè)碼字的消息，以k列向量表示。4.2.2 卷積碼卷積碼是另一類信道編碼，它也是把k位信息編成n（n大于等于k）位，但k和n都很小，適于串行傳輸。特點(diǎn)是編碼后的n個(gè)碼元不僅與當(dāng)前段的k位信息有關(guān)，而且與前N-1段的信息有關(guān)，編碼過程中相互關(guān)聯(lián)的碼元有Nn個(gè)。糾錯(cuò)能力隨N的增加而增加，而差錯(cuò)率隨N的增加而指數(shù)下降。編碼過程可以看成是輸入信息序列與由移位寄存器和模2加連接所決定的的另一序列的卷積，因此稱為卷積沒碼。N稱為約束長(zhǎng)度，m=N-1稱為編碼存儲(chǔ)。卷積編碼其特點(diǎn)是除能糾正本組的誤碼外, 也糾正其它組的誤碼, 卷積編碼可以采用不同的比率, 在DVB標(biāo)準(zhǔn)中, 規(guī)定5種比率(即1/2、2/3、3/4、5/6、7/8)。5.結(jié)束語信息論理論的建立，提出了信息、信息熵的概念，接著人們提出了編碼定理和編碼方法，但至今尚不完善。近幾年來，第三代移動(dòng)通信系統(tǒng)的熱衷探索，促進(jìn)了各種數(shù)字