【正文】 有效性。算術(shù)編碼 是一種能夠趨近于熵極限的最佳編碼方式對出現(xiàn)概率較大的符號使用短碼，對概率較小的符號使用長碼。既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對信源輸出符號序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預(yù)測、域變換和數(shù)據(jù)壓縮等。采用的一般方法是壓縮每個(gè)信源符號的平均比特?cái)?shù)或信源的碼率，同樣多的信息用較少的碼率來傳輸，使單位時(shí)間內(nèi)傳送的平均信息來量增加，從而提高通信的有效性。編碼可分為信源編碼和信道編碼。 信源編碼的基本途徑有兩個(gè)：使序列中的各個(gè)符號盡可能地相互獨(dú)立，即解除相關(guān)性；使編碼中各個(gè)符號出現(xiàn)的概率盡可能地相等，即概率均勻化。 原因是信源符號之間存在概率分布不均勻和相關(guān)性。 即用較少的碼字傳送較多的信息，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。記 ‖ U‖ =K。類似地 ,記 ‖ V‖ ＝ L。這與編碼的基本目標(biāo)是直接相矛盾的。反之 ,若這個(gè)條件不滿足，就不可能實(shí)現(xiàn)無失真的編碼。實(shí)質(zhì)上，定長編碼方法 提高信息載荷能力的關(guān)鍵是利用了漸近等分性 ,通過選擇足夠大的 M,把本來各個(gè)符號概率不等［因而 H(U)＜ logK］的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列 ， 式中 A＝｛ ɑk|k=1,? ,K｝ ,符號熵為 H(U)，對 U進(jìn)行 唯一可譯的變長編碼，編碼字母表 B 的符號數(shù)為 L,即 B=｛ bl|l=1,? ,L｝ ,那么必定存在一種編碼方法，使編出的碼字 Vi＝ (vi1,? ,viNi)， (i=1,? ,‖ V‖ )，具有平均長度嚻： MH(U)/logL≤ 嚻＜MH(U)/logL+1 若 L=K，則當(dāng) H(U)＜ logK＝ logL 時(shí) ,必有嚻＜ M； H(U)離 logK 越遠(yuǎn)，則嚻越小于 M。 霍夫曼編碼方法的具體過程是：首先把信源的各個(gè)輸出符號序列按概率遞降的順序排列起來，求其中概率最小的兩個(gè)序列的概率之和，并把這個(gè)概率之和看作是一個(gè)符號序列的概率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個(gè)序列不再出現(xiàn)在新的排列之中），然后，對參與概率求和的兩個(gè)符號序列分別賦予二進(jìn)制數(shù)字 0 和 1。 表 11 由表中可以看出，在碼字序列中碼元 0 和 1 的概率分別為 10/21 和 11/21，二者近乎相等，實(shí)現(xiàn)了概率的均勻化。 針對信源輸出符號序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。 一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個(gè)： 一是使序列中的各個(gè)符號盡可能地互相獨(dú)立； 二是使序列中各個(gè)符號的出現(xiàn)概率盡可能地相等。所謂對這個(gè)信源的輸出進(jìn)行編碼，就是用一個(gè)新的符號表 B 的符號序列集合 V 來表示信源輸出的符號序列集合 U。為了使信源的每個(gè)輸出符號序列都能分配到一個(gè)獨(dú)特的碼字與之對應(yīng)，至少應(yīng)滿足關(guān)系 ‖ V‖＝ L≥‖ U‖＝ K，或者 N/M≥ logK/logL； 假若編碼符號表 B 的符號數(shù) L與信源符號表 A的符號數(shù) K 相等，則編碼后的碼字序列的長度 N必須大于或等于信源輸出 符號序列的長度 M；反之，若有 N＝ M，則必須有 L≥ K。下面的幾個(gè)編碼定理，提供了解決這個(gè)矛盾的方法。式中 H(U)是信源輸出序列的符號熵。實(shí)質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性 ,通過選擇足夠大的 M,把本 來各個(gè)符號概率不等［因而 H(U)＜ logK］的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列為 ， 式中 A＝｛ ɑk|k=1,? ,K｝ ,符號熵為 H(U)，對 U進(jìn) 行唯一可譯的變長編碼，編碼字母表B 的符號數(shù)為 L,即 B=｛ bl|l=1,? ,L｝ ,那么必定存在一種編碼方法，使編出的碼字 Vi＝(vi1,? ,viNi)， (i=1,? ,‖ V‖ )，具有平均長度嚻： MH(U)/logL≤嚻＜ MH(U)/logL+1； 若 L=K，則當(dāng) H(U)＜ logK＝ logL 時(shí) ,必有嚻＜ M； H(U)離 logK 越遠(yuǎn)，則嚻越小于 M。 編碼的逆過程，利用不同編碼方法實(shí)現(xiàn)的生成的碼字通過其相應(yīng)方法實(shí)現(xiàn)對碼字的譯碼，還原出從信源輸入的信息。 這樣信源發(fā)出的不同符號序列將與各子區(qū)間一一對應(yīng) ， 因此每個(gè)子區(qū)間內(nèi)的任意個(gè)實(shí)數(shù)都可以用來表示對應(yīng)的符號序列，這個(gè)數(shù)就是該符號序列所對應(yīng)的碼字。本課程設(shè)計(jì)中以靜態(tài)算術(shù)編碼算法進(jìn)行仿真。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率， 所能做的最有效的方法是在編碼過程中估算概率。 （ 2）算術(shù)編碼器對整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔 [0, 1)中的一個(gè)實(shí)數(shù)， 因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。為了解決這些難點(diǎn)，針對不同的應(yīng)用方向，人們對傳統(tǒng)的算術(shù)編碼方法進(jìn)行了改進(jìn)，在保證足夠精度的前提下，提高了編碼速度。編碼過程中的間隔決定了符號壓縮后的輸出。靜態(tài)型算術(shù)編碼的編碼值是變化的然后找所對應(yīng)的區(qū)間；自適應(yīng)型算術(shù)編碼的編碼值是不變的，只需改變概率區(qū)間，然后用此 9 編碼值找到所對應(yīng)的區(qū)間，從而譯出碼字。因?yàn)?t 的 range low=,range high=,則下一個(gè) low,high 分別為 Low=+＝ High=+＝ Range= t 將 [,） =[,） 同理得到下面各字符 e,＿ ,s,t,r,e,e 編碼所得到的范圍分別為 [,)，[,),[,),[,),[,），[,） ,[,） 。 由于 11 落在 [,）之間，因此可解得第一個(gè)符號是 s。 設(shè)某信源可能發(fā)出三種符號 a， b， c，對符號序列 bccb 進(jìn)行自適應(yīng)算術(shù)編碼： 初始時(shí)刻，我們對 a， b， c，三者出現(xiàn)的概率一無所知（即采用自適應(yīng)模型），認(rèn)為三者出現(xiàn)的概率相等，暫時(shí)都為 1/3，頻率都為 1，則累積頻率為 3。此時(shí) c 的頻率又增加了 1 變?yōu)?3，累積頻率也又增加了 1 變?yōu)?6；概率分布更新為： 最后輸入字符 b，鎖定區(qū)間 [,)，然后在這個(gè)區(qū)間內(nèi)任意選擇 一個(gè)實(shí)數(shù)，例如 ，再將其轉(zhuǎn)化為二進(jìn)制數(shù) l 位（連續(xù)乘以 2 取整）。 a. 11011011B=，落入?yún)^(qū)間 [,)，所以譯碼器譯為 b，概率分布更新為： 13 b. 落入?yún)^(qū)間 [,)，譯為 c，概率分布更新為： c. 落入?yún)^(qū)間 [,)，譯為 c，概率分布更新為： d. 落入?yún)^(qū)間 [,)，譯為 b。本章主要舉例說明了算術(shù)編碼的基本原理，讓讀者能夠理解算術(shù)編碼的基本應(yīng)用方法。這些工具方便用戶使用 MATLAB 的函數(shù)和文件，其中許多工具采用的是圖形用戶界面。簡單的編程環(huán)境提供了比較完備的調(diào)試系統(tǒng)，程序不必經(jīng)過編譯就可以直接運(yùn)行，而且能夠及時(shí)地報(bào)告出現(xiàn)的錯(cuò)誤及進(jìn)行出錯(cuò)原因分析。在計(jì)算要求相同的情況下，使用 MATLAB 的編程工作量會大大減少。譯碼的時(shí)候，讀取編碼的輸出結(jié)果，找到所在的區(qū)間，依次譯出編碼前輸入的字符信息。 圖 算術(shù)編碼設(shè)計(jì)流程圖 上圖是算術(shù)編碼設(shè)計(jì)流程圖，無論是靜態(tài)型還是自適應(yīng)型算術(shù)編碼在編碼前都要初始化概率空間，但二者在編碼時(shí)的概率空間卻不一樣，前者固定不變，后者概率隨輸入字符變化而變化。 39。 39。39。%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%39。由于在轉(zhuǎn)化為二進(jìn)制時(shí)受限于字長，因此輸入的字符串長度要適宜。 a2=0+pa。 a2=pa+pb。 a2=pa+pb+pc。 a2=pa+pb+pc+pd。 a2=pa+pb+pc+pd+pe。 a2=1。(i=k) %在第一個(gè)字符已編碼的基礎(chǔ)上為后續(xù)字符編 碼 switch 1 case string_s(i)==39。 a1=aa。 aa=a1+l*pa。 case string_s(i)==39。 a1=aa。 aa=a1+l*(pa+pb+pc)。 case string_s(i)==39。 a1=aa。 aa=a1+l*(pa+pb+pc+pd+pe)。 end l=a2a1。 disp(a1) %顯示編碼區(qū)間的起始值 disp(39。本程序選擇區(qū)間中點(diǎn)做為編碼是： 39。)。i=k %譯碼對字符的確認(rèn) switch 1 case ym==1 bm0=(bm00)/pa。 case ym==3 bm0=(bm0papb)/pc。 case ym==5 bm0=(bm0papbpcpd)/pe。 end i=