一．香農-范諾編碼
香農-范諾（Shannon-Fano）編碼的目的是產生具有最小冗餘的碼詞（code word）。其基本思想是產生編碼長度可變的碼詞。碼詞長度可變指的是，被編碼的一些訊息的符號可以用比較短的碼詞來表示。估計碼詞長度的準則是符號出現的機率。符號出現的機率越大，其碼詞的長度越短。
香農-范諾編碼算法需要用到下面兩個基本概念：
（1）熵（Entropy）
某個事件的信息量（又稱自信息）用
Ii ＝ -log2 pi
表示，其中pi為第i個事件的機率，0< pi ≤ 1。
信息量Ii的機率平均值叫做信息熵，或簡稱熵。
熵是信息量的度量方法，它表示某一事件出現的訊息越多，事件發生的可能性就越小，數學上就是機率越小。
（2）信源的熵
按照香農的理論，信源S的熵定義為
其中pi是符號Si在S中出現的機率；log2(1/pi)表示包含在Si中的信息量，也就是編碼Si所需要的位數。
按照香農的理論，熵是平穩信源的無損壓縮效率的極限。例如，一幅用256級灰度表示的圖像，如果每一個像素點灰度的機率均為 pi=1/256，編碼每一個像素點就需要8位（比特，bit）。
香農-范諾編碼算法步驟：
（1）按照符號出現的機率減少的順序將待編碼的符號排成序列。
（2）將符號分成兩組，使這兩組符號機率和相等或幾乎相等。
（3）將第一組賦值為0，第二組賦值為1。
（4）對每一組，重複步驟2的操作。
下面我們用一個例子說明。假定有下述內容：
"EXAMPLE OF SHANNON FANO"
首先，我們計算文本中每個符號出現的機率，見表3-03。
然後，按照按照符號機率排成序列：
'N ' ，' ' ，' O' ，' A' ，' E' ，' F' ，' X' ，' M' ，' P' ，' L' ，' S' ，' H'
將' N' ，' ' ，' O' ，' A' 編為一組，賦值為0；其餘的為另一組，賦值為1。遞歸下去，如圖03-02-1所示。
表03-02-1 符號在文本中出現的機率
| 符號 | 機率 |
| E | 2月23日 |
| X | 1月23日 |
| A | 3月23日 |
| M | 1月23日 |
| P | 1月23日 |
| L | 1月23日 |
| O | 3月23日 |
| F | 2月23日 |
| S | 1月23日 |
| H | 1月23日 |
| N | 4月23日 |
| 空格 | 3月23日 |
在我們的例子中有23個字元的文本中共有12個符號。用4個比特才能表示12個符號，編碼這個文本需要4x23=92個比特。按照香農理論，這個文本的熵為
H(S) = (2/23)log2(23/2)+(1/23)log2(23/1)+…+(3/23)log2(23/3)
= 2.196
這就是說每個符號用2.196比特表示可以，23個字元需用87.84比特。
圖03-02-1 香農-范諾算法編碼例
由於上述理論是香農（Claude Shannon，1948年）和范諾（Robert Fano，1949年）各自獨立發現的，因此被稱為香農-范諾算法。香農-范諾的理論雖然指出了平穩信源的無損壓縮的極限，實際的問題在於，為了達到這個極限，通常需要建立一種對於n字信源的編碼，當n很 大時，這樣的編碼不但很複雜，而且會導致一般系統無法容忍的延時。實際上，人們通常不採用壓縮到熵率的無損編碼。他們寧願採用準最佳化的壓縮方式以求可操作 性和低延時。3類和4類傳真標準就是例子，它們在實際無損壓縮過程中犧牲了一點壓縮效率以提高可實現性和靈活性。霍夫曼編碼則是另一個改進的例子。
