費諾編碼課程設計(共18頁)

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

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

3、方法。在編N進制碼時首先將信源消息符號按其出現(xiàn)的概率依次由小到大排列開來，并將排列好的信源符號按概率值分N大組，使N組的概率之和近似相同，并對各組賦予一個N進制碼元0、1N-1。之后再針對每一大組內(nèi)的信源符號做如上的處理，即再分為概率和相同的N組，賦予N進制碼元。如此重復，直至每組只剩下一個信源符號為止。此時每個信源符號所對應的碼字即為費諾碼。針對同一信源，費諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率大，編碼效率高。 一個有8個符號的信源X，各個符號出現(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進行費諾編碼，并計算平均(pngjn)碼長、編碼效率、冗余度。費諾編碼(bin m)2.1設計(shj)原理編碼與信源編碼在學過信息論與編碼以后，對這方面內(nèi)容已有了基礎的了解。為了進行更深入的了解，我查閱了很多資料，我認為通信的根本問題是如何將信源輸出的信息在接收端的信宿精確地或近似地復制出來，而這最重要的一步就是信源的編碼，一個好的開端才能為以后的傳輸及接受、解碼提供有利得條件。而我也對各種信源編碼方式產(chǎn)生了濃厚的興趣。1.1首先要了解什么是信源編碼為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸

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

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

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

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

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

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

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

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

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

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

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

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

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

18、元碼符號.依次下去,直至每一個小組只剩下一個信源符號為止.這樣,信源符號所對應的碼符號序列則為編得的碼字。 根據(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運行(ynxng)結(jié)果及分析 圖3 運行(ynxng)結(jié)果圖 第4章 總結(jié)(zngji) 本學期的課程設計結(jié)束了，通過本次設計的經(jīng)歷我認識到了許多專業(yè)知識上的不足之處，對于老師課堂上的理論知識進一步的進行了鞏固，在以后的學習(xux)中還應該繼續(xù)努力。 仿真時，我學習鞏固了仿真軟件MATLAB，學習到了仿真軟件

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