信息论中相关编码总结

时间：2024-05-22 09:48:28

整理一下下信息论中的几种编码。

不等长编码定理

若一离散无记忆信源的熵为H(U),每个信源符号用D进制码元进行不等长编码,则一定存在一种无失真编码方法,构成唯一可译码，其平均码长满足:
H(U)log⁡(D)≤n‾≤H(U)log⁡(D)+1 \frac {H(U)}{\log(D)} \leq \overline{n} \leq \frac {H(U)}{\log(D)} + 1
对于平均符号熵为HL(U)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均码长满足不等式:
HL(U)log⁡(D)≤n‾≤HL(U)log⁡(D)+1L \frac {H_L(U)}{\log(D)} \leq \overline{n} \leq \frac{H_L(U)}{\log(D)} + \frac {1}{L}

Shannon编码

编码步骤

  1. 对信源符号按概率从大到小排序;
  2. 计算码长;
  3. 计算累加概率;
  4. 写出概率对应的二进制数;
  5. 获得码字(取前k位);

编码示例

信息论中相关编码总结

Fano编码

编码步骤

  1. 对信源符号按概率从大到小排序;
  2. 从这个概率集合中的某个位置将其分为两个子集合，并尽量使两个子集合的概率和近似相等，给前面一个子集合赋值为0，后面一个子集合赋值为1;
  3. 重复步骤(2)，直到各个子集合中只有一个元素为止;
  4. 将每个元素所属的子集合的值依次串起来即可得到码字;

编码示例

信息论中相关编码总结

Huffman编码

编码步骤：

  1. 对信源符号按概率大到小排序，权重为概率；
  2. 取概率最小的字符作为左节点，其次小的符号为右节点，然后这两个(最小)元素相加作为新的元素，权重为概率和，将新元素和剩余元素重新排序;
  3. 重复步骤(2),直到排列的元素只剩一个;
  4. 最后产生的树状图就是Huffman树;
  5. 左节点为0，右节点为1，从根节点到子节点的一条路径即是符号的码字;

编码示例

信息论中相关编码总结

算术编码

编码步骤

  1. 对信源符号按概率大到小排序;
  2. 将[0,1]区间划分为多个子区间，每个子区间代表一个字符，可得每个字符的位置[L,H];
  3. 编码从一个[0,1]区间开始，设置low = 0,high =1;
  4. 不断读入原始数据字符，计算并更新;
    low=low+(high−low)⋅Lhigh=low+(high−low)⋅H low = low+(high−low) \cdot L \\\\ high = low+(high−low) \cdot H
  5. 最后得到的区间[low,high]中任意一个小数以二进制形式输出即可得到码字;

编码示例

注意：将符号序列的累积概率写成二进位小数，取小数点 后L位,若后面有尾数,就进位到第L位。进位！！！
累积概率递推公式: P(S,ar) = P(S) + p(s)Pr
二元序列：S = 011
P(S0->0110) = P(S)
P(S1->0111) = P(S) + p(S)P1

例1：设二元无记忆信源S={0,1},p(0)=1/4,p(1)=3/4。S=11111100，对其做算术编码。
解析:
P0 = 0,P1 = 1/4;P(S0) = P(S) + p(S)P0 = P(S); P(S1) = P(S) + p(S)P1
(此处P1=p(0),补充:二元信源P0 = 0,P1=p(0))
信息论中相关编码总结
例2：设无记忆信源U={a1,a2,a3,a4}，其概率分布依次为0.5,0.25,0.125,0.125，对信源序列做算术编码。
解析：
P1 = 0,P2 = 1/2,P3 = 3/4,P4 = 7/8;P(S,ar) = P(S) + p(s)Pr
信息论中相关编码总结

LZ编码(LZ78码)

设信源符号集A={a1，a2，…，aK}共K个符号，设输入信源符号序列为u=(u1，u2，…，uL)

编码步骤

  1. 取第一个符号作为第一段;
  2. 若下一个符号与已有的分段都不重复,则取其为下一个分段;
  3. 若下一个符号与已有的分段都重复，则再取其下一位符号组成一个分段，直到同前面的所有分段不同;
  4. 重复(2)(3),直至信源序列结束;

编码示例

设U={a1，a2，a3，a4}，信源序列为a1，a3，a2，a3，a2，a4，a3，a2，a1，a4，a3，a2，a1，共13位，字典如表所示：
信息论中相关编码总结

参考链接：

https://baike.baidu.com/item/香农编码/22353186
https://zh.wikipedia.org/wiki/香农-范诺编码
https://blog.****.net/FX677588/article/details/70767446
https://zh.wikipedia.org/wiki/霍夫曼编码
https://segmentfault.com/a/1190000011561822
https://bkso.baidu.com/item/LZ编码

相关文章