費(fèi)諾編碼課程設(shè)計(jì)(共18頁)

1、吉林建筑(jinzh)大學(xué)電氣(dinq)與電子信息工程學(xué)院信息(xnx)理論與編碼課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目： 費(fèi)諾編碼 專業(yè)班級 學(xué)生姓名： 學(xué) 號： 指導(dǎo)教師： 設(shè)計(jì)時(shí)間： 2014.11.242014.12.5 教師評語：成績 評閱教師 日期 第1章 概述(i sh)1.1設(shè)計(jì)的作用(zuyng)、目的信息論與編碼是一門理論與實(shí)踐密切結(jié)合的課程(kchng),課程設(shè)計(jì)是其實(shí)踐性教學(xué)環(huán)節(jié)之一，同時(shí)也是對課堂所學(xué)理論知識的鞏固和補(bǔ)充。其主要目的是加深對理論知識的理解，掌握查閱有關(guān)資料的技能，提高實(shí)踐技能，培養(yǎng)獨(dú)立分析問題、解決問題及實(shí)際應(yīng)用的能力。通過完成具體編碼算法的程序設(shè)計(jì)和調(diào)試工作，提高編

2、程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過程，增強(qiáng)邏輯思維能力，培養(yǎng)和提高自學(xué)能力以及綜合運(yùn)用所學(xué)理論知識去分析解決實(shí)際問題的能力，逐步熟悉開展科學(xué)實(shí)踐的程序和方法。1.2設(shè)計(jì)任務(wù)及要求 1理解無失真信源編碼的理論基礎(chǔ)，掌握無失真信源編碼的基本方法； 2根據(jù)費(fèi)諾編碼算法，考慮一個(gè)有多種可能符號（各種符號發(fā)生的概率不同）的信源，得到費(fèi)諾編碼； 3掌握費(fèi)諾編碼的優(yōu)缺點(diǎn)； 4能夠使用MATLAB或其他語言進(jìn)行編程，編寫的函數(shù)要有通用性，要理解每個(gè)函數(shù)的具體意義和適用范圍，對主要函數(shù)的功能和參數(shù)做詳細(xì)說明。1.3設(shè)計(jì)內(nèi)容 費(fèi)諾編碼屬于概率匹配編碼，但不是最佳的編碼

3、方法。在編N進(jìn)制碼時(shí)首先將信源消息符號按其出現(xiàn)的概率依次由小到大排列開來，并將排列好的信源符號按概率值分N大組，使N組的概率之和近似相同，并對各組賦予一個(gè)N進(jìn)制碼元0、1N-1。之后再針對每一大組內(nèi)的信源符號做如上的處理，即再分為概率和相同的N組，賦予N進(jìn)制碼元。如此重復(fù)，直至每組只剩下一個(gè)信源符號為止。此時(shí)每個(gè)信源符號所對應(yīng)的碼字即為費(fèi)諾碼。針對同一信源，費(fèi)諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率大，編碼效率高。 一個(gè)有8個(gè)符號的信源X，各個(gè)符號出現(xiàn)的概率為：XP（X） X1, X2, X3, X4, X5, X6, X7, X80.19, 0.18, 0.17, 0.16, 0.13, 0

4、.10, 0.06, 0.01進(jìn)行費(fèi)諾編碼，并計(jì)算平均(pngjn)碼長、編碼效率、冗余度。費(fèi)諾編碼(bin m)2.1設(shè)計(jì)(shj)原理編碼與信源編碼在學(xué)過信息論與編碼以后，對這方面內(nèi)容已有了基礎(chǔ)的了解。為了進(jìn)行更深入的了解，我查閱了很多資料，我認(rèn)為通信的根本問題是如何將信源輸出的信息在接收端的信宿精確地或近似地復(fù)制出來，而這最重要的一步就是信源的編碼，一個(gè)好的開端才能為以后的傳輸及接受、解碼提供有利得條件。而我也對各種信源編碼方式產(chǎn)生了濃厚的興趣。1.1首先要了解什么是信源編碼為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸

5、出符號序列的統(tǒng)計(jì)特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時(shí)又能保證無失真地恢復(fù)原來的符號序列8。既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對信源輸出符號序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預(yù)測、域變換和數(shù)據(jù)壓縮等。一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個(gè)：使序列中的各個(gè)符號盡可能地互相獨(dú)立；使序列中各個(gè)符號的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。在通信過程中，如何在不失真或允許一定失真條件下，用盡可能

6、少的符號來傳送信源信息，提高信息傳輸率；在信道受干擾的情況下，如何增加信號的抗干擾能力，同時(shí)又使得信息傳輸率最大。這就產(chǎn)生了多種信源編碼方式2。為了有效傳播信息，最理想狀態(tài)即為無失真?zhèn)鬏?。在無失真信源編碼中又分為(fn wi)定長編碼、變長編碼機(jī)最佳變長編碼。1.1.1定長編碼(bin m)在定長編碼中，K是定值，編碼的目的即為找到最小的K值。要實(shí)現(xiàn)無失真的(zhn de)信源編碼，不但要求信源符號與碼字是一一對應(yīng)的，而且還要求有碼字組成的碼符號序列的逆變換也是唯一的。由定長編碼定理可知，當(dāng)編碼器容許的輸出信息率，也就是當(dāng)每個(gè)信源符號必須輸出的碼長是K=Kl/logm。由定理表明，只要碼字所能

7、攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，但是條件是L足夠大。這就為傳輸帶來了很大的麻煩，并且實(shí)現(xiàn)起來很困難，并且編碼效率也不高。而要達(dá)到編碼效率接近1的理想編碼器雖有存在性，但在實(shí)際上時(shí)不可能的，因?yàn)長非常大，無法實(shí)現(xiàn)。由此而產(chǎn)生了變長編碼。1.1.2變長編碼在變長編碼中，碼長K是變化的，可根據(jù)信源各個(gè)符號的統(tǒng)計(jì)特性，對概率大的符號用短碼，而對概率小的符號用長碼。這樣大量信源符號編成碼后，平均每個(gè)信源符號所需的輸出符號數(shù)就可以降低，從而提高編碼效率。用變長編碼來達(dá)到相當(dāng)高的編碼效率，一般所要求的符號長度L可以比定長編碼小得多的多。很明顯，定長碼需要的信源序列長，這使得碼表

8、很大，且總存在譯碼差錯(cuò)。而變長碼要求編碼效率達(dá)到96%時(shí)，只需L=2.因此用變長碼編碼時(shí)，L不需要很大就可達(dá)到相當(dāng)高的編碼效率，而且可實(shí)現(xiàn)無失真編碼。并且隨著信源序列長度的增加，編碼效率越來越接近于1，編碼后的信息傳輸率R也越來越接近于無噪無損二元對稱信道的信道容量C=1bit/二元碼符號，達(dá)到信源與信道匹配，使信道得到充分利用。但變長編碼方式也有優(yōu)劣的區(qū)分，下面就討論幾種不同的變長編碼方式1。香農(nóng)編碼方法香農(nóng)第一定理指出了平均碼長與信源之間的關(guān)系，同時(shí)也指出了可疑通過編碼使平均碼長達(dá)到極限值，這是一個(gè)很重要的極限定理。香農(nóng)第一定理指出，選擇每個(gè)碼字的長度Ki滿足下式：I（xi）Ki=P2=P

9、n。2依次排列的信源符號按概率值分為兩大組，使兩個(gè)組的概率之和近似相同，并對各組賦予一個(gè)二進(jìn)制碼元“0”和“1”。3使劃分后的兩個(gè)組的概率(gil)之和近似相同，并對各組賦予一個(gè)二進(jìn)制符號“0”和“1”。4如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(fho)為止。5信源符號(fho)所對應(yīng)的碼字即為費(fèi)諾碼。4. 費(fèi)諾編碼特點(diǎn)費(fèi)諾編碼，它編碼后的費(fèi)諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率大，編碼效率高，但它屬于概率匹配編碼它不是最佳的編碼方法1。費(fèi)諾編碼方法屬于概率匹配編碼，具有如下特點(diǎn)：1、概率大，則分解次數(shù)??；概率小則分解次數(shù)多。這符合最佳碼原則。2、碼字集合是唯一的。3、分解完了，碼字出來了，

10、碼長也有了,即先有碼字后有碼長。因此，費(fèi)諾編碼方法又稱為子集分解法。2.2設(shè)計(jì)步驟費(fèi)諾編碼過程框圖概率大小降序排列按概率值分為兩組，概率和近似相同各組賦予二進(jìn)制碼云“0”和“1”兩組概率和近似相同，各組賦予二進(jìn)制碼云“0”和“1”如此反復(fù)，直至每個(gè)組只剩下一個(gè)信源符號為止信源符號所對應(yīng)的碼字即為費(fèi)諾碼 圖1費(fèi)諾碼編碼(bin m)過程圖費(fèi)諾編碼(bin m)過程表消息符號Xi各個(gè)符號概率P(Xi)第一次分組第二次分組第三次分組第四次分組二元碼字碼長X10.1900002X20.18100103X30.1710113X40.1610102X50.13101103X60.101011104X70.

11、06111115X0.01111115 表1費(fèi)諾碼編碼(bin m)過程表計(jì)算(j sun)平均碼長、編碼效率、冗余度。 冗余度在數(shù)據(jù)傳輸中，由于衰減或干擾會(huì)使數(shù)據(jù)代碼發(fā)生突變，此時(shí)就要提高數(shù)據(jù)代碼的抗干擾能力這必須在原二進(jìn)制代碼長度的基礎(chǔ)上增加幾位二進(jìn)制代碼的長度，使相應(yīng)數(shù)據(jù)具有一定(ydng)的冗余度，也稱做富裕度簡單地說，所謂冗余度，就是從安全角度考慮多余的一個(gè)量，這個(gè)量就是為了保障儀器、設(shè)備或某項(xiàng)工作在非正常情況下也能正常運(yùn)轉(zhuǎn)。目前大多現(xiàn)代產(chǎn)品和工程設(shè)計(jì)中都應(yīng)用了冗余度這個(gè)思想和理論。在許多醫(yī)療單位中藥品存量不足，衛(wèi)生材料存量不夠，一遇突發(fā)事件，就會(huì)造成缺貨，造成漲價(jià)風(fēng)波，影響社會(huì)安定

12、。在我們的醫(yī)院中，由于各項(xiàng)費(fèi)用都與經(jīng)濟(jì)效益掛鉤，醫(yī)療設(shè)備等衛(wèi)生裝備冗余度很不夠，基本上只能按平時(shí)的正常運(yùn)轉(zhuǎn)設(shè)置，甚至有的都沒達(dá)到。一遇突發(fā)事件，這點(diǎn)裝備就顯得嚴(yán)重不足。冗余度，通俗(tn s)的講就是數(shù)據(jù)的重復(fù)度。在一個(gè)數(shù)據(jù)集合中重復(fù)的數(shù)據(jù)稱為數(shù)據(jù)冗余 第3章 費(fèi)諾編碼(bin m)的MATLAB實(shí)現(xiàn)3.1 MATLAB簡介(jin ji)Matlab是MathWorks公司于1982年推出的一套高性能的數(shù)值計(jì)算和可視化軟件。它集數(shù)值分析、矩陣運(yùn)算、信號處理和圖形顯示于一體，構(gòu)成了一個(gè)方便、界面良好的用戶環(huán)境。它還包括了Toolbox(工具箱)的各類問題的求解工具，可用來求解特定學(xué)科的問題。其

13、特點(diǎn)是：16，17，18 (1) 可擴(kuò)展性：Matlab最重要的特點(diǎn)是易于擴(kuò)展，它允許用戶自行建立指定功能的M文件。對于一個(gè)從事特定領(lǐng)域的工程師來說，不僅可利用Matlab所提供的函數(shù)及基本工具箱函數(shù)，還可方便地構(gòu)造出專用的函數(shù)。從而大大擴(kuò)展了其應(yīng)用范圍。當(dāng)前支持Matlab的商用Toolbox(工具箱)有數(shù)百種之多。而由個(gè)人開發(fā)的Toolbox則不可計(jì)數(shù)。(2) 易學(xué)易用性：Matlab不需要用戶有高深的數(shù)學(xué)知識和程序設(shè)計(jì)能力，不需要用戶深刻了解算法及編程技巧。(3) 高效性：Matlab語句功能十分強(qiáng)大，一條語句可完成十分復(fù)雜的任務(wù)。如fft語句可完成對指定數(shù)據(jù)的快速傅里葉變換，這相當(dāng)于上

14、百條C語言語句的功能。它大大加快了工程技術(shù)人員從事軟件開發(fā)的效率。據(jù)MathWorks公司聲稱，Matlab軟件中所包含的Matlab源代碼相當(dāng)于70萬行C代碼。3.2 MATLAB廣泛應(yīng)用由于Matlab具有如此之多的特點(diǎn)，在歐美高等院校，Matlab已成為應(yīng)用于線性代數(shù)、自動(dòng)控制理論、數(shù)理統(tǒng)計(jì)、數(shù)字信號處理、時(shí)間序列分析、動(dòng)態(tài)系統(tǒng)仿真等高級課程的基本教學(xué)工具：在研究單位、工業(yè)部門，Matlab也被廣泛用于研究和解決各種工程問題。當(dāng)前在全世界有超過40萬工程師和科學(xué)家使用它來分析和解決問題14。Matlab作為科學(xué)計(jì)算軟件，主要適用于矩陣運(yùn)算和信息處理領(lǐng)域的分析設(shè)計(jì)，它使用(shyng)方便

15、、輸入簡捷，運(yùn)算高效、內(nèi)容豐富，并且有大量的函數(shù)庫可提供使用，與Basic，C和Fortran相比，用Matlab編寫程序，其問題的提出和解決只需要以數(shù)學(xué)方式表達(dá)和描述，不需要大量(dling)繁瑣的編程過程。利用(lyng)Matlab軟件并通過計(jì)算機(jī)仿真光學(xué)空間濾波實(shí)驗(yàn)過程的新方法,其特點(diǎn)是：既可以隨意改變所設(shè)計(jì)濾波器的參量，又可以對輸入圖像進(jìn)行振幅、相位或復(fù)合濾波，并且可實(shí)現(xiàn)傅里葉變換頻譜中相位信息的提取、存儲和利用，因而能夠完成一般光學(xué)實(shí)驗(yàn)中往往難以實(shí)現(xiàn)的某些操作.并分別給出了網(wǎng)格濾波、低通、高通及相位濾波等仿真實(shí)驗(yàn)結(jié)果。這種仿真實(shí)驗(yàn)給光學(xué)濾波器的設(shè)計(jì)和圖象處理帶來很大方便，同時(shí)也為相

16、關(guān)器件的設(shè)計(jì)提供了一條新的途徑。3.3 MATLAB軟件系統(tǒng)構(gòu)成 圖2 MATLAB7.0界面MATLAB軟件主要包括主包、Simulink和工具箱三大部分組成。下圖為MATLAB界面：3.4 MATLAB語言MATLAB可以認(rèn)為是一種解釋性語言，可以直接在MATLAB命令窗口鍵入命令，也可以在編輯器內(nèi)編寫(binxi)應(yīng)用程序，這樣MATLAB軟件對命令或程序中各條語句進(jìn)行翻譯，然后在MATLAB環(huán)境下對它進(jìn)行處理，最后返回運(yùn)算結(jié)果。MATLAB語言的基本語句(yj)結(jié)構(gòu)為：變量名列表(li bio)=表達(dá)式其中等號左邊的變量名列表為MATLAB語句的返回值，等號右邊是表達(dá)式的定義，它可以是

17、MATLAB允許的矩陣運(yùn)算，也可以使函數(shù)調(diào)用。等號右邊的表達(dá)式可以由分號結(jié)束，也可以由逗號或回車結(jié)束，但他們的含義是不同的，如果用分號結(jié)束，則左邊的變量結(jié)果將不在屏幕上顯示出來，否則將把結(jié)果全部顯示出來。MATLAB語言和C語言有所不同，在調(diào)用函數(shù)式MATLAB允許一次返回多個(gè)結(jié)果，這時(shí)等號左邊是用括起來的變量列表。3.4 MATLAB編程 費(fèi)諾編碼也是一種常見的信源編碼方法。信源符號以概率遞減的次序排列進(jìn)來,將排列好的信源符號劃分為兩大組,使第組的概率和近于相同,并各賦于一個(gè)二元碼符號”0”和”1”.然后,將每一大組的信源符號再分成兩組,使同一組的兩個(gè)小組的概率和近于相同,并又分別賦予一個(gè)二

18、元碼符號.依次下去,直至每一個(gè)小組只剩下一個(gè)信源符號為止.這樣,信源符號所對應(yīng)的碼符號序列則為編得的碼字。 根據(jù)其原理所得到的MATLAB程序如下： clc;clear;A=0.19,0.18,0.17,0.16,0.13,0.10,0.06,0.01;A=fliplr(sort(A);%降序排列m,n=size(A);for i=1:n B(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(B(:,1)/2;for k=1:n-1 if abs(sum(B(1:k,1)-a)=abs(sum(B(1:k+1,1)-a) break; endendfor i=1:n%生

19、成(shn chn)B第2列的元素 if i=k B(i,2)=0; else B(i,2)=1; endend%生成(shn chn)第一次編碼的結(jié)果END=B(:,2);END=sym(END);%生成(shn chn)第3列及以后幾列的各元素j=3;while (j=0) p=1; while(p=n) x=B(p,j-1); for q=p:n if x=-1 break; else if B(q,j-1)=x y=1; continue; else y=0; break; end end end if y=1 q=q+1; end if q=p|q-p=1 B(p,j)=-1; el

20、se if q-p=2 B(p,j)=0; END(p)=char(END(p),0; B(q-1,j)=1; END(q-1)=char(END(q-1),1; else a=sum(B(p:q-1,1)/2; for k=p:q-2 if abs(sum(B(p:k,1)-a)=abs(sum(B(p:k+1,1)-a); break; end end for i=p:q-1 if i=k B(i,j)=0; END(i)=char(END(i),0; else B(i,j)=1; END(i)=char(END(i),1; end end end end p=q; end C=B(:,j

21、); D=find(C=-1); e,f=size(D); if e=n j=0; else j=j+1; endendBAENDfor i=1:n u,v=size(char(END(i); L(i)=v;endavlen=sum(L.*A)encodef=2.61/ avlen3.5運(yùn)行(ynxng)結(jié)果及分析 圖3 運(yùn)行(ynxng)結(jié)果圖 第4章 總結(jié)(zngji) 本學(xué)期的課程設(shè)計(jì)結(jié)束了，通過本次設(shè)計(jì)的經(jīng)歷我認(rèn)識到了許多專業(yè)知識上的不足之處，對于老師課堂上的理論知識進(jìn)一步的進(jìn)行了鞏固，在以后的學(xué)習(xí)(xux)中還應(yīng)該繼續(xù)努力。 仿真時(shí)，我學(xué)習(xí)鞏固了仿真軟件MATLAB，學(xué)習(xí)到了仿真軟件

22、的一些(yxi)作用。和 HYPERLINK /doc/3102369.html Mathematica、Maple并稱為三大 HYPERLINK /doc/5343249.html 數(shù)學(xué)軟件。它在數(shù)學(xué)類科技應(yīng)用軟件中在數(shù)值計(jì)算方面首屈一指。MATLAB可以進(jìn)行 HYPERLINK /doc/5351907.html 矩陣運(yùn)算、繪制函數(shù)和數(shù)據(jù)、實(shí)現(xiàn) HYPERLINK /doc/2758411.html 算法、創(chuàng)建用戶界面、連接其他 HYPERLINK /doc/538266.html 編程語言的程序等，主要應(yīng)用于工程計(jì)算、控制設(shè)計(jì)、信號處理與通訊、 HYPERLINK /doc/838176.html 圖像處理、信號檢測、金融建模設(shè)計(jì)與分析等領(lǐng)域。M