假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。 ① 试为这8个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例,比较两种方案的优缺点。
时间: 2023-05-02 13:01:57 浏览: 136
题目描述:假设用于通信的电文仅包含8个字母组成,字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10。 ① 试为此设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例,比较两种方案的优缺点。
① 赫夫曼编码设计方法如下:
(1)将电文中的8个字母按照出现频率从小到大排序,得到序列CFGEHDBA。
(2)将第1、2个字母C和F合成一个节点CF,权重为0.09,其他节点保持不变,得到序列CFGEHDBA。
(3)将序列中权重最小的节点CF和G合成一个新节点CFG,权重为0.12,得到序列CFGEDHBA。
(4)将序列中权重最小的节点ED和H合成一个新节点EDH,权重为0.09,得到序列CFGEDHBA。
(5)将序列中权重最小的节点CFG和EDH合成一个新节点CFGEDH,权重为0.21,得到序列CFGEDHBA。
(6)将序列中权重最小的节点D和B合成一个新节点DB,权重为0.16,得到序列CFGEDHDBA。
(7)将序列中权重最小的节点CFGEDH和DB合成一个新节点CFGEDHDB,权重为0.37,得到序列CFGEDHDBA。
(8)将序列中权重最小的节点C和F合成一个新节点CF,权重为0.09,得到序列CFGEDHA。
(9)将序列中权重最小的节点E和H合成一个新节点EH,权重为0.12,得到序列CFGEDBACEH。
(10)将序列中权重最小的节点CF和EDBACEH合成一个新节点CFEDBACEH,权重为0.58,赫夫曼编码如下:
| 字母 | 频率 | 编码 | | 字母 | 频率 | 编码 | | 字母 | 频率 | 编码 |
|------|------|------|-----|------|------|------|-----|------|------|------|
| C | 0.07 | 111 | | F | 0.03 | 1001 | | E | 0.19 | 10 |
| G | 0.06 | 1011 | | H | 0.10 | 110 | | D | 0.02 | 10000|
| B | 0.10 | 010 | | A | 0.21 | 00 |
② 设计等长编码方案如下:
由于这8个字母可以用3位二进制数来表示,因此我们可以将每个字母映射到3位二进制数,具体设计如下:
| 字母 | 频率 | 编码 |
|------|------|------|
| C | 0.07 | 000 |
| F | 0.03 | 001 |
| G | 0.06 | 010 |
| E | 0.19 | 011 |
| H | 0.10 | 100 |
| D | 0.02 | 101 |
| B | 0.10 | 110 |
| A | 0.21 | 111 |
③ 两种方案的优缺点如下:
赫夫曼编码的优点是可以利用频率信息设计出尽可能短的编码,从而减小信息传输的时间和带宽。缺点是需要计算赫夫曼树,编码和解码的复杂度较高,且需要将编码表发送给接收方,增加了信息传输的成本。
等长编码的优点是编码和解码的复杂度较低,且编码表不需要发送给接收方。缺点是编码长度固定,不能很好地利用频率信息,导致编码长度较长,增加了信息传输的时间和带宽。
阅读全文