一、Huffman编码方法及例题

Huffman编码方法：

①设信源的消息个数为K，对其进行D元编码，第一次要合并的消息个数为R，则R的值为：

其中第一项表示K-2除D-1的余数。
②将信源S的n个符号{s1,s2,…sn}按概率从大到小排列；
③第一次给概率最小的R个符号分别分配“0”、“1”、…、“R-1”码元，然后其概率相加，合成一个节点，作为一个新的符号，重新与其它符号按概率大小排列；
④第二次则给概率最小的D个符号分别分配“0”、“1”、…、“D-1”码元，然后其概率相加，合成一个节点，作为一个新的符号，重新与其它符号按概率大小排列；
⑤重复上一步，一直处理到D个符号概率相加之和为1为止

Huffman码不唯一（不仅是码字可以不同，尤其是码长分布不唯一）
例：
对U进行二元Huffman编码

第一种：

码长分布及平均码长为：

第二种：

码长分布及平均码长为：

Huffman编码例题：

例1.对下面的信源进行二元Huffman编码：

S	s1	s2	s3	s4	s5
P(S)	0.4	0.3	0.2	0.05	0.05

解：

编码结果为：

s1	s2	s3	s4	s5
1	01	000	0010	0011

例2.对其进行3元Huffman编码

a1	a2	a3	a4	a5	a6	a7
0.2	0.19	0.18	0.17	0.15	0.10	0.01

解：

因此第一次合并3个元素，合并结果及过程如下图所示：

例3.对其进行3元Huffman编码

a1	a2	a3	a4	a5	a6
0.2	0.19	0.18	0.17	0.15	0.11

解：

因此第一次合并2个元素，合并结果及过程如下图所示：

例4.对其进行2元Huffman编码

000	001	010	100	011	101	110	111
0.729	0.081	0.081	0.081	0.009	0.009	0.009	0.001

解：

二、LZ编码方法及例题

LZ编码方法：

设有消息序列：x0,x1,x2,…,xm。把序列分成不同的段。
分段规则：
尽可能取最少个连着的符号，并能保证各段都不相同。
开始取一个符号作为一段，以后有同样的符号时，就再取后面1个符号合起来作为一段，以与前面的段不同。
有了许多段后，再分段时应查看前面所有的段，如有重复就添加符号再查看，直至与前面所有的段不同为止。
可见，每一段都是前面某一段加一个符号。

LZ编码例题：

设二元信源的字母概率为P(0)=1/4,P(1)=3/4。若信源输出序列为1011011110110111，试对其进行LZ编码。

解：
首先对其进行分段：1 0 11 01 111 011 0111，然后对其进行编码，编码词典如下所示：

段号	短语	编码
1	1	0001
2	0	0000
3	11	0011
4	01	0101
5	111	0111
6	011	1001
7	0111	1101

解析：
因为段号有7种，所以前面是[log 7]（对log7上取整），即3bit。
因为只有0,1两种消息，所以后面是log 2,即只有1bit。
所以每个符号编码为4位。
第一个短语为1，由于前面没出现过，故前3位的编码为000.最后一位和短语的最后一位一样.因此编码为0001。
第二个短语为0，由于前面没出现过，故前3位的编码为000.最后一位和短语的最后一位一样.因此编码为0000。
第三个短语为11，去掉该短语的最后一个符号1，剩余的符号为1，由前面可以看出1的段号是1，故前3位的编码为001.最后一位和短语的最后一位一样.因此编码为0011。
第四个短语为01，去掉该短语的最后一个符号1，剩余的符号为0，由前面可以看出0的段号是2，故前3位的编码为010.最后一位和短语的最后一位一样.因此编码为0101。
第五个短语为111，去掉该短语的最后一个符号1，剩余的符号为11，由前面可以看出11的段号是3，故前3位的编码为011.最后一位和短语的最后一位一样.因此编码为0111。
第六个短语为011，去掉该短语的最后一个符号1，剩余的符号为01，由前面可以看出01的段号是4，故前3位的编码为100.最后一位和短语的最后一位一样.因此编码为1001。
第七个短语为0111，去掉该短语的最后一个符号1，剩余的符号为011，由前面可以看出011的段号是6，4前3位的编码为110.最后一位和短语的最后一位一样.因此编码为1101。

三、算术编码方法及例题

算术编码方法：

①针对u计算出对应P(u)；
②计算码长N=[log(1/P(u))]；（对log(1/P(u))上取整）
③根据递推关系计算各信源符号所在的区间；
④在最后得到的区间中任取一点，以其二进制表示作为编码的结果；
⑤从上一步得到的二进制小数中截止N位，如果后面还有尾数则进位，得到最终的编码结果

算术编码例题：

设离散无记忆信源U={𝑎_1,𝑎_2,𝑎_3,𝑎_4},其概率分布为𝑃(𝑎_1 )=0.5，𝑃(𝑎_2 )=0.25，𝑃(𝑎_3 )=0.125，𝑃(𝑎_4 )=0.125，试对序列 𝒖= 𝑎_2 𝑎_1 𝑎_1 𝑎_3 𝑎_4进行算术编码。

解：

四、Shannon-Fano编码方法及例题

通过一个例题来讲解Shannon-Fano编码

Shannon-Fano编码例题：

例1.对其进行Shannon-Fano编码

U	a1	a2	a3	a4	a5	a6	a7	a8	a9
P(u)	1/3	1/9	1/9	1/9	1/9	1/9	1/27	1/27	1/27

则其编码如下：

所以a1对应的码字是0,码长为1; a2对应的码字是10,码长为2; a3对应的码字是11，码长为2; a4对应的码字是02,码长为2; a5 对应的码字是20,码长为2; a6对应的码字是21,码长为2; a7对应的码字是220,码长为3; a8对应的码字是221,码长为3; a9对应的码字是222,码长为3。
解析：