費諾編碼課程設計

//吉林建筑大學電氣與電子信息工程學院信息理論與編碼課程設計報告設計題目： 費諾編碼專業(yè)班級學生姓名： 學號： 指導教師： 設計時間：2014.11.24－2014.12.5/// / v第1章概述設計的作用、目的《信息論與編碼》是一門理論與實踐密切結合的課程,課程設計是其實踐性教學環(huán)節(jié)之一，同時也是對課堂所學理論知識的鞏固和補充。其主要目的是加深對理論知識的理解，掌握查閱有關資料的技能，提高實踐技能，培養(yǎng)獨立分析問題、解決問題及實際應用的能力。通過完成具體編碼算法的程序設計和調試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過程，增強邏輯思維能力，培養(yǎng)和提高自學能力以及綜合運用所學理論知識去分析解決實際問題的能力，逐步熟悉開展科學實踐的程序和方法。設計任務及要求1．理解無失真信源編碼的理論基礎，掌握無失真信源編碼的基本方法；2．根據(jù)費諾編碼算法，考慮一個有多種可能符號（各種符號發(fā)生的概率不同）的信源，得到費諾編碼；3．掌握費諾編碼的優(yōu)缺點；4能夠使用MATLAB或其他語言進行編程，編寫的函數(shù)要有通用性，要理解每個函數(shù)的具體意義和適用范圍，對主要函數(shù)的功能和參數(shù)做詳細說明。1.3設計內容費諾編碼屬于概率匹配編碼，但不是最佳的編碼方法。在編N進制碼時首先將信源消息符號按其出現(xiàn)的概率依次由小到大排列開來，并將排列好的信源符

號按概率值分N大組，使N組的概率之和近似相同，并對各組賦予一前進制碼元0、1……N-1。之后再針對每一大組內的信源符號做如上的處理，即再分為概率和相同的N組，賦予N進制碼元。如此重復，直至每組只剩下一個信源符號為止。此時每個信源符號所對應的碼字即為費諾碼。針對同一信源，費諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率大，編碼效率高。一個有8個符號的信源X,各個符號出現(xiàn)的概率為：TOC\o"1-5"\h\z〃 1rX80.01X X80.01P（X） 0.19, 0.18, 0.17, 0.16, 0.13, 0.10, 0.06,進行費諾編碼，并計算平均碼長、編碼效率、冗余度。第2章費諾編碼2.1設計原理編碼與信源編碼在學過信息論與編碼以后，對這方面內容已有了基礎的了解。為了進行更深入的了解，我查閱了很多資料，我認為通信的根本問題是如何將信源輸出的信息在接收端的信宿精確地或近似地復制出來，而這最重要的一步就是信源的編碼，一個好的開端才能為以后的傳輸及接受、解碼提供有利得條件。而我也對各種信源編碼方式產(chǎn)生了濃厚的興趣。首先要了解什么是信源編碼為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列使，后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復原來的符號序列［8］。既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對信源輸出符號序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預測、域變換和數(shù)據(jù)壓縮等。一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個：①使序列中的各個符號盡可能地互相獨立；②使序列中各個符號的出現(xiàn)概率盡可能地相等。前者稱為解除相關性，后者稱為概率均勻化。在通信過程中，如何在不失真或允許一定失真條件下，用盡可能少的符號來傳送信源信息，提高信息傳輸率；在信道受干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大。這就產(chǎn)生了多種信源編碼方式［2］。為了有效傳播信息，最理想狀態(tài)即為無失真?zhèn)鬏?。在無失真信源編碼中又分為定長編碼、變長編碼機最佳變長編碼。定長編碼在定長編碼中，K是定值，編碼的目的即為找到最小的K值。要實現(xiàn)無失真的信源編碼，不但要求信源符號與碼字是一一對應的，而且還要求有碼字組成的碼符號序列的逆變換也是唯一的。由定長編碼定理可知，當編碼器容許的輸出信息率，也就是當每個信源符號必須輸出的碼長是K=Kl/logm。由定理表明，只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，但是條件是1足夠大。這就為傳輸帶來了很大的麻煩，并且實現(xiàn)起來很困難，并且編碼效率也不高。而要達到編碼效率接近1的理想編碼器雖有存在性，但在實際上時不可能的，因為1非常大，無法實現(xiàn)。由此而產(chǎn)生了變長編碼。變長編碼在變長編碼中，碼長K是變化的，可根據(jù)信源各個符號的統(tǒng)計特性，對概率大的符號用短碼，而對概率小的符號用長碼。這樣大量信源符號編成碼后，平均每個信源符號所需的輸出符號數(shù)就可以降低，從而提高編碼效率。用變長編碼來達到相當高的編碼效率，一般所要求的符號長度L可以比定長編碼小得多的多。很明顯，定長碼需要的信源序列長，這使得碼表很大，且總存在譯碼差錯。而變長碼要求編碼效率達到96%時，只需1=2.因此用變長碼編碼時，L不需要很大就可達到相當高的編碼效率，而且可實現(xiàn)無失真編碼。并且隨著信源序列長度的增加，編碼效率越來越接近于1,編碼后的信息傳輸率口也越來越接近于無噪無損二元對稱信道的信道容量C=1bit/二元碼符號，達到信源與信道匹配，使信道得到充分利用。但變長編碼方式也有優(yōu)劣的區(qū)分，下面就討論幾種不同的變長編碼方式［1］。香農(nóng)編碼方法香農(nóng)第一定理指出了平均碼長與信源之間的關系，同時也指出了可疑通過編碼使平均碼長達到極限值，這是一個很重要的極限定理。香農(nóng)第一定理指出，選擇每個碼字的長度代滿足下式：I(xi)<Ki<I(xi)+1就可以得到這種碼。編碼方式如下：首先將信源消息符號按其出現(xiàn)的概率大小依次從大到小排列，為了編成唯一可譯碼，計算第i個消息的累加概率P=Epe)，并將累加概率Pi變換成二進制數(shù)。最后去Pi二進制數(shù)的小數(shù)點后8位提取出，即為給出符號的二進制碼字。由此可見香農(nóng)編碼法冗余度稍大，實用性不強，但他是依據(jù)編碼定理而來，因此具有重要的理論意義。費諾編碼方法費諾編碼屬于概率匹配編碼，但不是最佳的編碼方法。在編N進制碼時首先將信源消息符號按其出現(xiàn)的概率依次由小到大排列開來，并將排列好的信源符號按概率值分N大組，使N組的概率之和近似相同，并對各組賦予一個N進制碼元0、1……N-1。之后再針對每一大組內的信源符號做如上的處理，即再分為概率和相同的N組，賦予N進制碼元。如此重復，直至每組只剩下一個信源符號為止。此時每個信源符號所對應的碼字即為費諾碼。針對同一信源，費諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率大，編碼效率高。哈夫曼編碼方法編碼方法：也是先將信源符號按其出現(xiàn)的概率大小依次排列，并取概率最小的字母分別配以0和1兩個碼元（先0后1或者先1后0，以后賦值順序固定），再將這兩個概率想家作為一個新字母的概率，與未分配的二進制符號的字母重新排隊。并不斷重復這一過程，直到最后兩個符號配以0和1為止。最后從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即為相應的碼字。哈夫曼編碼方式得到的碼并非唯一的。在對信源縮減時，兩個概率最小的符號合并后的概率與其他信源符號的概率相同時這，兩者在縮減信源中的排序將會導致不同碼字，但不同的排序將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。哈夫曼碼的平均碼長最小，消息傳輸效率最大，編碼效率最高。鑒于以上編碼的特點與我所掌握的知識下面我將著重介紹費諾編碼。費諾編碼的描述費諾編碼是一種信源編碼.信源編碼分為無失真信源編碼和限失真信源編碼。一般稱無失真信源編碼為第一機械定理；限失真信源編碼定理稱為第三極限定理。由于信源符號之間存在分布不均勻和相關性，使得信源存在冗余度，信源編碼的主要任務就是減少冗余，提高編碼效率。具體說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短碼字序列的方法。信源編碼的基本途徑有兩個：使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。信源編碼的基礎是信息論中的兩個編碼定理：無失真編碼定理和限失真編碼定理。其中無失真編碼定理是可逆編碼的基礎?？赡媸侵府斝旁捶栟D換成代碼后，可從代碼無失真地恢復信源符號。當已知信源符號的概率特性時，可計算它的符號熵，這表示每個信源符號所載有的信息量。編碼定理不但證明了必定存在一種編碼方法，可使代碼的平均長度可任意接近但不低于符號熵，而且還闡明達到這目標的途徑，就是使概率與碼長匹配。無失真編碼或可逆編碼只適用于離散信源。對于連續(xù)信源，編成代碼后就無法無失真地恢復原來的連續(xù)值，因為后者的取值可有無限多個。此時只能根據(jù)率失真編碼定理在失真受限制的情況下進行限失真編碼。信源編碼定理出現(xiàn)后，編碼方法就趨于合理化。凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼。能獲得最佳碼的編碼方法主要有：香農(nóng)碼（Shannon）、費諾任2門0）、哈夫曼伸"的20編碼等。費諾編碼步驟1,將信源消息符號按其出現(xiàn)的概率大小依次排列：P1>=P2>=??>=Pn。2．依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近似相同，并對各組賦予一個二進制碼元“0”和“1”。3．使劃分后的兩個組的概率之和近似相同，并對各組賦予一個二進制符號“0”和“1”。4．如此重復，直至每個組只剩下一個信源符號為止。5．信源符號所對應的碼字即為費諾碼。費諾編碼特點費諾編碼，它編碼后的費諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率大，編碼效率高，但它屬于概率匹配編碼它不是最佳的編碼方法［1］。費諾編碼方法屬于概率匹配編碼，具有如下特點：1、概率大，則分解次數(shù)小；概率小則分解次數(shù)多。這符合最佳碼原則。2、碼字集合是唯一的。3、分解完了，碼字出來了，碼長也有了,即先有碼字后有碼長。因此，費諾編碼方法又稱為子集分解法。2設計步驟費諾編碼過程框圖概率大小降序排列按概率值分為兩組，概率

和近似相同各組賦予二進制

碼云“0”和“1”兩組概率和近似相同，各組賦

予二進制碼云“0”和“1”如此反復，直至每個組只剩下

一個信源符號為止信源符號所對應的碼字即為費

諾碼圖1費諾碼編碼過程圖

分題點為旗組分封如懂f編號?通過求黑闌和諭定分卸矯每羽雁率里加和只可能相近或相等.分題點為旗組分封如懂f編號?通過求黑闌和諭定分卸矯每羽雁率里加和只可能相近或相等.費諾編碼流程圖:/腕人信源部號個數(shù)n,信源/ %丹4斯度對應的概率口/愉叫信海苻辛.丁/率、瑪寧、碼任分組點為新分油的是心一個騙耳，其他編號不變按概率從入到小排列.對應的符號也亞新H：列分組點為新分組的第一個掂號.其他依次 第一用的信源碼字加H.‘；州/”??.字，Ji.?以仆機力為斷點.田斯編號分為兩組費諾編碼過程表消息符號X.i各個符號概率P(Xi)第一次分組第二次分組第三次分組第四次分組二元碼字碼長X10.1900002X20.18100103X30.1710113X40.1610102X50.13101103X60.101011104X70.06111115X0.01111115表1費諾碼編碼過程表計算平均碼長、編碼效率、冗余度。平均碼長:K=￡p(ai)Ki=2.85碼元/符號i=1傳輸速率：R=H(X)=261=0.916bit/碼元K2.85編碼效率：H=0.916冗余度在數(shù)據(jù)傳輸中，由于衰減或干擾會使數(shù)據(jù)代碼發(fā)生突變，此時就要提高數(shù)據(jù)代碼的抗干擾能力,這必須在原二進制代碼長度的基礎上增加幾位二進制代碼的長度，使相應數(shù)據(jù)具有一定的冗余度，也稱做富裕度、簡單地說，所謂冗余度，就是從安全角度考慮多余的一個量，這個量就是為了保障儀器、設備或某項工作在非正常情況下也能正常運轉。目前大多現(xiàn)代產(chǎn)品和工程設計中都應用了冗余度這個思想和理論。在許多醫(yī)療單位中藥品存量不足，衛(wèi)生材料存量不夠，一遇突發(fā)事件，就會造成缺貨，造成漲價風波，影響社會安定。在我們的醫(yī)院中，由于各項費用都與經(jīng)濟效益掛鉤，醫(yī)療設備等衛(wèi)生裝備冗余度很不夠，基本上只能按平時的正常運轉設置甚至有的都沒達到。一遇突發(fā)事件，這點裝備就顯得嚴重不足。冗余度，通俗的講就是數(shù)據(jù)的重復度在一個數(shù)據(jù)集合中重復的數(shù)據(jù)稱為數(shù)據(jù)冗余第3章費諾編碼的MATLAB實現(xiàn)MATLAB簡介Matlab是MathWorks公司于1982年推出的一套高性能的數(shù)值計算和可視化軟件。它集數(shù)值分析、矩陣運算、信號處理和圖形顯示于一體，構成了一個方便、界面良好的用戶環(huán)境。它還包括了Toolbox(工具箱)的各類問題的求解工具，可用來求解特定學科的問題。其特點是：[16，17，18](1)可擴展性：Matlab最重要的特點是易于擴展，它允許用戶自行建立指定功能的M文件。對于一個從事特定領域的工程師來說，不僅可利用Matlab所提供的函數(shù)及基本工具箱函數(shù)，還可方便地構造出專用的函數(shù)。從而大大擴展了其應用范圍。當前支持Matlab的商用Toolbox(工具箱)有數(shù)百種之多。而由個人開發(fā)的Toolbox則不可計數(shù)。(2)易學易用性：Matlab不需要用戶有高深的數(shù)學知識和程序設計能力，不需要用戶深刻了解算法及編程技巧。(3)高效性：Matlab語句功能十分強大，一條語句可完成十分復雜的任務。如fft語句可完成對指定數(shù)據(jù)的快速傅里葉變換，這相當于上百條C語言語句的功能。它大大加快了工程技術人員從事軟件開發(fā)的效率。據(jù)MathWorks公司聲稱，Matlab軟件中所包含的Matlab源代碼相當于70萬行C代碼。MATLAB廣泛應用由于Matlab具有如此之多的特點，在歐美高等院校，Matlab已成為應用于線性代數(shù)、自動控制理論、數(shù)理統(tǒng)計、數(shù)字信號處理、時間序列分析、動態(tài)系統(tǒng)仿真等高級課程的基本教學工具：在研究單位、工業(yè)部門，Matlab也被廣泛用于研究和解決各種工程問題。當前在全世界有超過40萬工程師和科學家使用它來分析和解決問題［14］。Matlab作為科學計算軟件，主要適用于矩陣運算和信息處理領域的分析設計，它使用方便、輸入簡捷，運算高效、內容豐富，并且有大量的函數(shù)庫可提供使用，與Basic,C和Fortran相比，用Matlab編寫程序，其問題的提出和解決只需要以數(shù)學方式表達和描述，不需要大量繁瑣的編程過程。利用Matlab軟件并通過計算機仿真光學空間濾波實驗過程的新方法,其特點是：既可以隨意改變所設計濾波器的參量，又可以對輸入圖像進行振幅、相位或復合濾波，并且可實現(xiàn)傅里葉變換頻譜中相位信息的提取、存儲和利用，因而能夠完成一般光學實驗中往往難以實現(xiàn)的某些操作.并分別給出了網(wǎng)格濾波、低通、高通及相位濾波等仿真實驗結果。這種仿真實驗給光學濾波器的設計和圖象處理帶來很大方便，同時也為相關器件的設計提供了一條新的途徑。MATLAB軟件系統(tǒng)構成

MATLAB軟件主要包括主包、Simulink和工具箱三大部分組成。下圖為乂人丁1人8界面：口降》/*門門正三口GEt+Tny:ShrrlPJ?IdHemto昌*?口降》/*門門正三口GEt+Tny:ShrrlPJ?IdHemto昌*?PI、MfENe^■'Mustbrt(?rnijiat?dk5rtheraatebinisend-tsp</nane>".CoiiLd;a&tpaEaathfiifU.fi!35幻口如廿。6島醵官口口11疝1口011毗11的門-宣1>1^(20>1-9:20>1,2]=1；erd3333BChard]?Er-skas]J.induv[A.EH□<s-rtOLMiriles/scec1.M=]-A；C=?itr￡.2^0flrJ0fll€(195:205,;]=];BZB日的BJldlBg?SJ?gmEb；iKhavl^[D.LJj：IlieTlum-rvt+yp?圖2MATLAB7.0界面MATLAB語言MATLAB可以認為是一種解釋性語言，可以直接在MATLAB命令窗口鍵人命令，也可以在編輯器內編寫應用程序，這樣MATLAB軟件對命令或程序中各條語句進行翻譯，然后在MATLAB環(huán)境下對它進行處理，最后返回運算結果。MATLAB語言的基本語句結構為：變量名列表=表達式其中等號左邊的變量名列表為MATLAB語句的返回值，等號右邊是表達式的定義，它可以是乂人丁1人8允許的矩陣運算，也可以使函數(shù)調用。等號右邊的表達式可以由分號結束，也可以由逗號或回車結束，但他們的含義是不同的，如果用分號結束，則左邊的變量結果將不在屏幕上顯示出來，否則將把結果全部顯示出來。MATLAB語言和C語言有所不同，在調用函數(shù)式MATLAB允許一次返回多個結果，這時等號左邊是用［］括起來的變量列表。MATLAB編程費諾編碼也是一種常見的信源編碼方法。信源符號以概率遞減的次序排列進來,將排列好的信源符號劃分為兩大組,使第組的概率和近于相同,并各賦于一個二元碼符號”0”和”1”.然后,將每一大組的信源符號再分成兩組,使同一組的兩個小組的概率和近于相同,并又分別賦予一個二元碼符號.依次下去,直至每一個小組只剩下一個信源符號為止.這樣,信源符號所對應的碼符號序列則為編得的碼字。根據(jù)其原理所得到的MATLAB程序如下：clc;clear;A=[0.19,0.18,0.17,0.16,0.13,0.10,0.06,0.01];人=￡即卜(50代修));%降序排列[m,n]=size(A);fori=1:n8。,1)=人。);%生成8的第1列end%生成8第2列的元素a=sum(B(:,1))/2;fork=1:n-1ifabs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a)break;endendfor1=1^%生成3第2列的元素ifi<=kB(i,2)=0;elseB(i,2)=1;endend%生成第一次編碼的結果END=B(:,2)';END=sym(END);%生成第3列及以后幾列的各元素j=3;while(j~=0)p=1;while(p<=n)x=B(p,j-1);forq=p:nifx==-1break;elseifB(q,j-1)==xy=1;continue;elsey=0;break;endendendify==1q=q+1;endifq==p|q-p==1B(p,j)=-1;elseifq-p==2B(p,j)=0;END(p)=[char(END(p)),'0'];B(q-1,j)=1;END(q-1)=[char(END(q-1)),'1'];elsea=sum(B(p:q-1,1))/2;fork=p:q-2ifabs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a);break;endendfori=p:q-1ifi<=kB(i,j)=0;END(i)=[char(END(i)),'0'];elseB(i,j)=1;END(i)=[char(END(i)),'1'];endendendendp=q;endC=B(:,j);D=find(C==-1);[e,f]=size(D);ife==nj=0;elsej=j+1;endendBAENDfori=1:n[u,v]=size(char(END(i)));L(i)=v;endavlen=sum(L.*