編碼演算法T

① 哈夫曼編碼碼長怎麼算

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼編碼是變長編碼，思路：對概率大的編的碼字短，概率小的編的碼字長，這樣一來所編的總碼長就小，這樣編碼效率就高。上面那樣求是不對的，除非你這6個碼字是等概率的，各佔1/6。應該用對應的概率*其對應得碼長，再求和。

實際應用中

除採用定時清洗以消除誤差擴散和採用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。

按照CCITT標准，需要統計2×1728種遊程（長度），這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。

② 語音編解碼的723.1(雙速率語音編碼演算法)

類型：Audio
制定衡埋者：ITU-T
所需頻寬：5.3Kbps(22.9)
特性：能夠對音樂和其他音頻信號進行壓縮和解壓縮，但它對語音信號來說是最優的。G.723.1採用了執咐敏螞行不連續傳輸的靜音壓縮，這就意味著在靜音期間的比特流中加入了人為的雜訊。除了預留帶寬之外，這種技術使發信機的數據機保持連續工作，並且避免了載波信號的時通時斷。
優點：避免了載波信號的時通時斷。
缺點：語音質量一般
應用領域：voip
版稅方式：Free
備註：G.723.1演算法是 ITU-T建議的應用於低速率多媒體服務中語音或其它音頻信號的壓縮演算法，其目標應用系統包括H.323、H.324等多媒體通信系統 。該演算法已成為IP電話系統中的必選演算法拿告之一。

③ 哈夫曼的編碼

哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。） 而衫譽跡且哈夫曼編碼是按照子樹到父親，而其讀碼則是完全相反的。 因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的或並編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼虛拿使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。
哈夫曼樹的構造演算法。
const maxvalue= 10000; {定義最大權值}
maxleat=30; {定義哈夫曼樹中葉子結點個數}
maxnode=maxleaf*2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0..maxnode] of HnodeType;
var ……
procere CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構造演算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {輸入葉子結點個數}
for i:=0 to 2*n-1 do {數組HuffNode[ ]初始化}
begin
HuffNode.weight=0;
HuffNode.parent=-1;
HuffNode.lchild=-1;
HuffNode.rchild=-1;
end;
for i:=0 to n-1 do read(HuffNode.weight); {輸入n個葉子結點的權值}
for i:=0 to n-1 do {構造哈夫曼樹}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n+i-1 do
if (HuffNode[j].weight<m1) and (HuffNode[j].parent=-1) then
begin m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
end
else if (HuffNode[j].weight<m2) and (HuffNode[j].parent=-1) then
begin m2:=HuffNode[j].weight; x2:=j; end;
{將找出的兩棵子樹合並為一棵子樹}
HuffNode[x1].parent:=n+i; HuffNode[x2].parent:=n+i;
HuffNode[n+i].weight:= HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild:=x1; HuffNode[n+i].rchild:=x2;
end;
end;

④ 哈夫曼編碼

編碼方案

． 編碼和解碼 數據壓縮過程稱為編碼 即將文件中的每個字元均轉換為一個惟一的二進制位串 數據解壓過程稱為解碼 即將二進制位串轉換為對應的字元

． 等長編碼方案和變長編碼方案 給定的字元集C 可能存在多種編碼方案 （ ） 等長編碼方案 等長編碼方案將給定字元集C中每個字元的碼長定為[lg|C|] |C|表示字元集的大小 【例】設待壓縮的數據文件共有 個字元 這些字元均取自字元集C={a b c d e f} 等長編碼需要三位二進制數字來表示六個字元 因此 整個文件的編碼長度為 位

（ ）變長編碼方案 變長編碼方案將頻度高的字元編碼設置短 將頻度低的字元編碼設置較長 【例】設待壓縮的數據文件共有 個字元 這些字元均取自字元集C={a b c d e f} 其中每個字元在文件中出現的次數(簡稱頻度)見表 表 字元編碼問題 字元 a b c d e f 頻度（單位 千次） 定長編碼 變長編碼 根據計算公式 ( * + * + * + * + * + )* = 整個文件被編碼為 位 比定長編碼方式節約了約 ％的存儲空間 注意 變長編碼可能使解碼產生二義性 產生該問題的原因是某些字元的編碼可能與其他字元的編碼開始部分(稱為前綴)相同 【例】設E T W分別編碼為 則解碼時無法確定信息串 是ET還是W

． 前綴碼方案 對字元集進行編碼時 要求做舉字元集中任一字元的編碼都不是其它字元的編碼的前綴 這種編碼稱為前綴(編)碼 注意 等長編碼是前綴碼

．最優前綴碼 平均碼長或文件總長最小的前綴編碼稱為最優的前綴碼 最優的前綴碼對文件的壓縮效果亦最佳

其中 pi為第i個字元得概率 li為碼長【例】若將表 所示的文件作為統計的樣本 則a至f六個字元的概率分別為 對變長編碼求得的平均碼長為 優於定長編碼(平均碼長為 )

根據最優二叉樹構造哈夫曼編碼

利用哈夫曼樹很容易求出給定字元集及其概率(或頻度)分布的最優前綴碼 哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術 該技術一般可將數據文件壓縮掉 ％至 ％ 其壓縮效率取決於被壓縮文件的特徵

． 具體做法 （ ）用字元ci作為葉子 pi或fi做為葉子ci的權 構造一棵哈夫曼樹 並將樹中左分支和右分支分別標記為 和 （ ）將從根到葉子的路徑上的標號依次相連 作為該葉子所表示字元的編碼 該編碼即為最優前綴碼（也稱哈夫曼編碼）

． 哈夫曼編碼為最優前綴碼 由哈夫曼樹求得編碼為最優前綴碼的原段胡肆因 ① 每個葉子字元ci的碼長恰為從根到該葉子的路徑長度li 平均碼長(或文件總長)又是二叉樹的帶權路徑長度WPL 而哈夫曼樹是WPL最小的二叉樹 因此編碼的平均碼長(或文件總長)亦最小 ② 樹中沒有一片葉子是另一葉子的祖先 每片葉子對應的編碼就不可能是其它葉子編碼的前綴 即上述編碼是二進制的前綴碼

． 求哈夫曼編碼的演算法 （ ）思想方法 給定字元集的哈夫曼樹生成後 求哈夫曼編碼的具體實現過程是 依次以葉子T[i]( ≤i≤n )為出發點 向上回溯至根為止 上溯時走左分支則生成代碼 走右分支則生成代碼 注意握轎 ① 由於生成的編碼與要求的編碼反序 將生成的代碼先從後往前依次存放在一個臨時向量中 並設一個指針start指示編碼在該向量中的起始位置（start初始時指示向量的結束位置） ② 當某字元編碼完成時 從臨時向量的start處將編碼復制到該字元相應的位串bits中即可 ③ 因為字元集大小為n 故變長編碼的長度不會超過n 加上一個結束符 bits的大小應為n+

（ ）字元集編碼的存儲結構及其演算法描述 typedef struct { char ch //存儲字元 char bits[n+ ] //存放編碼位串 }CodeNode typedef CodeNode HuffmanCode[n] void CharSetHuffmanEncoding(HuffmanTree T HuffmanCode H) {//根據哈夫曼樹T求哈夫曼編碼表H int c p i;//c和p分別指示T中孩子和雙親的位置 char cd[n+ ] //臨時存放編碼 int start //指示編碼在cd中的起始位置 cd[n]= //編碼結束符 for(i= i<n i++){ //依次求葉子T[i]的編碼 H[i] ch=getchar() //讀入葉子T[i]對應的字元 start=n //編碼起始位置的初值 c=i //從葉子T[i]開始上溯 while((p=T[c] parent)>= ){//直至上溯到T[c]是樹根為止 //若T[c]是T[p]的左孩子 則生成代碼 否則生成代碼 cd[ start]=(T[p) child==C)? c=p //繼續上溯 } strcpy(H[i] bits &cd[start]) //復制編碼位串 }//endfor }//CharSetHuffmanEncoding文件的編碼和解碼有了字元集的哈夫曼編碼表之後 對數據文件的編碼過程是 依次讀人文件中的字元c 在哈夫曼編碼表H中找到此字元 若H[i] ch=c 則將字元c轉換為H[i] bits中存放的編碼串 對壓縮後的數據文件進行解碼則必須藉助於哈夫曼樹T 其過程是 依次讀人文件的二進制碼 從哈夫曼樹的根結點(即T[m ])出發 若當前讀人 則走向左孩子 否則走向右孩子 一旦到達某一葉子T[i]時便譯出相應的字元H[i] ch 然後重新從根出發繼續解碼 直至文件結束 文件的編碼和解碼演算法【參見練習】

lishixin/Article/program/sjjg/201311/22941

⑤ G.711編碼原理

本文目的：
1、熟悉G711a/u兩種格式的基本原理
2、熟悉兩種壓縮演算法的友悔實現步驟及提供源碼實現

G.711是國際電信聯盟ITU-T定製出來的一套語音壓縮標准，它代表了對數PCM（logarithmic pulse-code molation）抽樣標准，是主流的波形聲音編解碼標准，主要用於電話。

G.711 標准下主要有兩種壓縮演算法。

G.711將14bit(uLaw)或者13bit(aLaw)采樣的PCM數據編碼成8bit的數據流，播放的時候在將此8bit的數據還原成14bit或者13bit進行播放，不同於MPEG這種對於整體或者一段數據進行考慮再進行編解碼的做法，G711是波形編解碼演算法，就是一個sample對應一個編碼，所以壓縮比固定為：

G.711是將語音模擬信號進行一種非線性量化， 詳細的資料可以在ITU 上下到相關的spec 。下面主要列出一些性能參數：
G.711（PCM方式）

演算法原理：
A-law的公式如下，一般採用A=87.6

畫出圖來則是如下圖，用x表示輸入的采樣值，F(x)表示通過A-law變換後的采樣值，y是對F(x)進行量化後的采樣值。

由此可見

對應反量化公式(即上面函數的反函數)：

G.711A輸入的是13位（S16的高13位），這種格式是經過特別設計昌拍的，便於數字設備進行快速運算。

A-law如下表計算。

示例：

輸入pcm數據為1234，二進制對應為（0000 0100 1101 0010）
二進制變換下排列組合方式（0 00001 0011 010010）
1、獲取符號位最高位為0，取反，s=1
2、獲取強度位00001，查表，編碼制應該是eee=011
3、獲取高位樣本wxyz=0011
4、組合為10110011，逢偶數為取反為11100110，得到E6

使用在北美和日本，輸入的是14位，編碼演算法就是查表，計算出：基礎值+平均偏移值

μ-law的公式如下，μ取值一般為255

相應的μ-law的計算方法如下表

示例：
輸入pcm數據為1234
1、取得范圍值，查表得 +2014 to +991 in 16 intervals of 64
2、得到基礎值為0xA0
3、得到間隔數為64
4、得到區間基本值2014
5、當前值1234和區間基本值差異2014-1234=780
6、偏移值=780/間隔數=780/64，取整得到12
7、輸出為0xA0+12=0xAC

A-law和u-law畫在同一個坐標軸中就能發現A-law在低強度信號下，精度要稍微高一些。

實際應用中，我們確實可以用浮點數計算的方式把F(x)結果計算出來，然後進行量化，但是這樣一來計算量會比較大耐告羨，實際上對於A-law（A=87.6時），是採用13折線近似的方式來計算的，而μ-law（μ=255時）則是15段折線近似的方式。

G711盡管是一種非常古老的話音編碼演算法，原理和計算也比較簡單，但是其中用到的一些基本原理同樣在其他編碼演算法中得到了應用，對其進行深入的了解有助於更好的理解其他的演算法。

⑥ 遺傳演算法的編碼方法有幾種

常用的編碼介紹
1、二進制編碼：
（1）定義：二進制編碼方法是使用二值符號集{0,1}，它所構成的個體基因型是一個二進制編碼符號串。二進制編碼符號串的長度與問題所要求的求解精度有關。
（2）舉例：0≤x≤1023,精度為1,m表示二進制編碼的長度。則有建議性說法：使 2m-1≤1000（跟精度有關）≤2m-1。取m=10
則X:0010101111就可以表示一個個體，它所對應的問題空間的值是x=175。
（3）優缺點
優點：符合最小字元集原則，便於用模式定理分析；
缺點：連續函數離散化時的映射誤差。
2、格雷碼編碼
（1）定義：格雷碼編碼是其連續的兩個整數所對應的編碼之間只有一個碼位是不同的，其餘碼位完全相同。它是二進制編碼方法的一種變形。
十進制數0—15之間的二進制碼和相應的格雷碼分別編碼如下。
二進制編碼為：0000，0001，0010，001 1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷碼編碼為：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）舉例：對於區間[0。1023]中兩個鄰近的整數X1=175和X2=176，若用長度為10位的二進制編碼，可表示為X11：0010101111和X12 0010110000，而使用同樣長度的格雷碼，它們可分別表示為X21：0010101111和X22：0010101000。
（3）優點：增強了遺傳演算法的局部搜索能力，便於連續函數的局部控制項搜索。
3、浮點數(實數)編碼
（1）定義：浮點數編碼是指個體的每個基因值用某一范圍內的一個浮點數來表示，而個體的編碼長度等於其決策變數的個數。因為這種編碼方法使用的決策變數的真實值，也稱之為真值編碼方法。
（2）舉例：
（3）優點：實數編碼是遺傳演算法中在解決連續參數優化問題時普遍使用的一種編碼方式，具有較高的精度，在表示連續漸變問題方面具有優勢。
4、排列編碼
排列編碼也叫序列編碼，是針對一些特殊問題的特定編碼方式。排序編碼使問題簡潔，易於理解。該編碼方式將有限集合內的元素進行排列。若集合內包含m個元素，則存在m!種排列方法，當m不大時，m!也不會太大，窮舉法就可以解決問題。當m比較大時，m!就會變得非常大，窮舉法失效，遺傳演算法在解決這類問題上具有優勢。如解決TSP問題時，用排列編碼自然、合理。
5、其它編碼方式
多參數級聯編碼等

⑦ IP視頻通信中視頻壓縮編碼方法介紹【詳解】

和一般的業務不同，視頻是流特性業務，數據量很大。例如，數字電視圖像中的SIF格式、NTSC制式、彩色、4∶4∶4采樣，每幀的數據量為2028Kb，每秒的數據流量可達60.8Mb;CCIR格式、PAL制式、4∶4∶4采樣的彩色視頻的數據流量可達148.8Mbps。實驗表明，176& TI mes;144的YUV原始視頻在10Mbps的LAN上傳送速率是3幀/秒左右。可見，未壓縮的視頻在Internet上傳輸的效果是無法容忍的，而且會很容易地將Internet資源吞沒，造成網路擁塞甚至崩潰。因此，IP視頻通信的第一步就是視頻壓縮。

視頻壓縮編碼的理論基礎是資訊理論。壓縮就是從時域、空域兩方面去除冗餘信息，即將可推知的確定信息去掉。編碼方法大致可分為三類：

1.考慮到圖像信源的統計特性採用的預測編碼方法、變換編碼方法、液謹矢量量化編碼方法、子帶-小波編碼方法及神經網路編碼方法等;

2.考慮到視覺特性採用的基於方向濾波的圖像編碼方法、基於圖像輪廓/紋理的編碼方法;

3.考慮到圖像傳遞的景物特徵，採用的分形編碼、基於模塊的編碼方法。

在IP視頻通信應用中，編碼方法的選擇不但要考慮到壓縮比、信噪比，還要考慮到演算法的復雜性。太復雜的編碼演算法可能會產生較高的壓縮比，但也會帶來較大的計算開銷，軟體實現時會影響通信的實時性。目前，在眾多視頻編碼演算法中，影響最大並被廣泛應用的演算法是MPEG和H.26x。

MPEG編碼

MPEG是國際標准化組織ISO/IEC下的一個制定動態 視頻壓縮 編碼標準的組織，它為視頻壓縮編碼技術的標准化、實用化做出了巨大貢獻。如針對CD-ROM的1.5Mbps傳輸率的MPEG-1、針對HDTV的6Mbps以上傳輸速率的MPEG-2都已成功地得到應州橘用，並創造了巨大的商業價值。MPEG-4是針對視頻會議、可視電話的甚低速率編碼標准，它鬧跡基融入了基於內容的檢索與編碼，可對壓縮數據內容直接訪問;即將於2001年制定完畢的MPEG-7標准被稱為"多媒體內容描述介面"，這種標准化的描述可以加到任何類型的媒體信息上。不管視頻信息的表達形式或壓縮形式如何，具有這種標准化描述的多媒體數據均可被檢索。因此，MPEG-7的應用領域主要是數字化圖書館和廣播式媒體。

H.263編碼

H.261編碼是一種幀間預測減少時域冗餘、變換編碼減少空域冗餘的混合編碼方法，具有壓縮比高、演算法復雜度低等優點，得到較為廣泛的應用。Mbone的重要應用工具之一IVS的視頻編碼採用的就是H.261編碼演算法。在H.261的基礎上，1996年ITU-T推出了H.263編碼標准。H.263在許多方面對H.261進行了改進和擴充，如在編碼演算法復雜度增加很少的基礎上，H.263能提供更好的圖像質量、更低的速率，十分適合於IP視頻會議、可視電話應用。目前，H.263編碼是IP視頻通信採用最多的一種編碼方法，並已被許多多媒體通信終端標准所吸收, 如：ITU-TH.310(B-ISDN)、H.320(ISDN)、H.324(PSTN)、H.323(LAN、 WAN、Internet)。

隨著計算機性能的快速提高，對於可視電話和視頻會議等應用(一般使用QCIF圖像)，純軟體編碼器(codec)即可以滿足應用要求。我們實現的H.263純軟體編碼器在主頻為166MHz的主機上編碼幀率可達60幀/秒以上，平均圖像質量(用信噪比表示)大於38dB。

1998年ITU-T推出的H.263+是H.263建議的第二版，它提供了12個新的可協商模式和其他特徵，進一步提高了壓縮編碼性能。如H.263隻有5種視頻源格式，H.263+允許使用更多的源格式，圖像形狀和時鍾頻率也有多種選擇，拓寬了應用范圍;另一重要的改進是可擴展性，它允許多顯示率、多速率及多解析度，增強了視頻信息在易誤碼、易丟包異構網路環境下的傳輸。另外，H.263+的圖像分段依賴性也可以是受限的，以減少差錯傳播。H.263+對H.263中的不受限運動矢量模式進行了改進，加上12個新增的可選模式，不僅提高了編碼性能，而且增強了應用的靈活性。

⑧ 哈夫曼編碼（貪心演算法）

參考： 哈夫曼編碼

哈夫曼編碼是一種十分有效的編碼方法，廣泛應用於 數據壓縮 中
通過採用 不等長 的編碼方式，根據 字元頻率的不同 ，選擇 不差派拿同長度的編碼 ，對頻率 越高 的字元採用 越短 的編碼實現數據的高度壓縮。
這種對頻率越高的字元採用越短的編碼來編碼的方式應用的就是貪心演算法的思想。

下面看一個例子：
假如我們有虛搭一個包含1000個字元的文件，每個字元佔1個byte(1byte=8bits)，則存儲這100個字元一共需要8000bits。這還是有一些大的
那我們統計一下這1000個字元中總共有多少種字元，原來需要8bit來表示一個字元，如果使用更少的位數來表示這些字元，則可以減少存儲空間。
假設這1000個字元中總共有a、b、c、d、e、f共6種字元，使用使用3個二進制位來表示的話，存儲這1000個字元就只需要3000bits，比原來更節省存儲空間。

或許還可以再壓縮一下：
根據字元出現的 頻率 給與字元 不等長 的編碼，頻率越高的字元編碼越短，頻率越低的字元編碼越長。
它不能像等長編碼一樣直接按固定長度去讀取二進制位，翻譯成字元，為了能夠准確讀取翻譯字元，它要求一個字元的編碼不能是另外一個字元的前綴。

假設a、b、c、d、e、f這6個字元出現的頻率依次降低，則我們可以給與他們這樣的編碼

假如字元的出現頻率如圖所示，按照這樣的編碼表示的話，總位數如圖，一共2100bits，更加節省空間了

貪心策略：頻率小的字元，優先入隊。

步驟：
1.將每一個字元作為節點，以出現頻率大小作為權重，將其都放入 優先隊列 中（一個最小堆）；
2.每次出隊兩個節點並創建一個父節點，使其權值為剛剛出隊的節點的權值和，並且為兩個節點的父節點（合並）。然後將這個樹入隊。
3.重復操作2，直到隊列中只有一個元素（此時這個元素表示形式應該為一個樹）時，完成創建。

創建好了樹，該怎麼編碼呢？
我們對一個哈夫曼樹，從父節點開始的所有節點，往左邊標0，右邊標1。那麼到達葉子節點的順次編碼就可以找到了。

C：字元集合
Q：優先隊列
EXTRACT-MIN：傳入一羨山個隊列，出隊最小的元素
INSERT：將z插入到Q中

當for循環結束之後，此時隊列中只有一個元素，就是我們需要的哈夫曼樹，最後返回此樹即可。

假設T樹已經是一個最優的樹，假設x、y的頻率小於等於最低處的a、b，然後交換x、a，y、b。

計算代價是否發生變化。
比如這里比較 T 變成 T 』 後代價是否變化，發現代價變小或不變。

同理T』到T』』，又因為T本來假設就是最優的，所以只能相等
所以T』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的

⑨ 哈夫曼編碼碼長怎麼算

假設用於通信的電文由字元集{a,b,c,d,e,f,g,h}中的字母構成，這8個字母在電文中出現的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。

哈夫曼編碼 根據上面可得編碼表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000

用三位二進行數進行的等長編碼平均長度為3，而根據哈夫曼樹編碼的平均碼長為：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均碼長是等長碼的87%，所以平均壓縮率為13%。

因為定長編碼已經用相同的位數這個條件保證了任一個字元的編碼都不會成為其它編碼的前綴,所以這種情況只會出現在變長編碼當中，要想避免這種情況，

就必須用一個條件來制約定長編碼，這個條件就是要想成為壓縮編碼，變長編碼就必須是前綴編碼，所謂的前綴編碼就是任何一個字元的編碼都不能是另一個字元編碼的前綴。

(9)編碼演算法T擴展閱讀：

實際應用中，除採用定時清洗以消除誤差擴散和採用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，

例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。按照CCITT標准，需要統計2×1728種遊程（長度），

這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時，不小於64的遊程長度由主碼和基碼組成。而當l為64的整數倍時，只用主碼的代碼，已不存在基碼的代碼。

⑩ 哈夫曼編碼原理

赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆毀亮余。

哈夫曼編碼，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman於1952年提出一種編碼方法，纖滾該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼。

(10)編碼演算法T擴展閱讀

赫夫曼編碼的具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率
和剩餘的概率重新排隊，再把最鍵孫小的兩個概率相加，再重新排隊，直到最後變成1。

每次相
加時都將「0」和「1」賦與相加的兩個概率，讀出時由該符號開始一直走到最後的「1」，
將路線上所遇到的「0」和「1」按最低位到最高位的順序排好，就是該符號的赫夫曼編碼。

例如a7從左至右，由U至U″″，其碼字為1000；

a6按路線將所遇到的「0」和「1」按最低位到最高位的順序排好，其碼字為1001…

用赫夫曼編碼所得的平均比特率為：Σ碼長×出現概率

上例為：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵為2.61bit，二者已經是很接近了。