信息论与编码 第五章信源编码

问题:在不失真或允许一定的失真条件下,如何提高信息传输速率(如何用尽可能少的符号来传送信源消息)。

信源编码的基本途径:①编码后使序列中的各个符号之间尽可能地相互独立,解除相关性——预测编码和变换编码等;②使编码后各个符号出现的概率尽可能相等,即均匀化分布——统计编码等。

信源编码的目的:提高传输有效性,即用尽可能短的码符号序列来代表信源符号。 ### 5.1 编码器和相关概念

5.1.1 码的分类

由码符号 xi 组成的输出序列 Wi 称为码字,其长度 li 称为码字长度或码长,全体码字 Wi 的集合 C 称为码或码书

信源符号的概率已知——概率匹配编码;信源符号的概率未知——通用编码。

  1. 二元码和 r 元码

    若码符号集 X 共有 r 个元素,则所得的码称为 r 元码。

  2. 等长码

    若一组码中所有码字 Wi 的长度都相同,则称为等长码。

  3. 变长码

    若一组码中所有码字 Wi 的码长各不相同,则称为变长码。

  4. 分组码

    若每个信源符号 si 按照固定的码表映射成一个码字 Wi,则称为分组码,否则是非分组码。

    • 非奇异码和奇异码

      所有码字 Wi 都不相同,则称为非奇异码;反之,则为奇异码。

    • 同价码

      若每个码字的传输时间都相同,则所得的码为同价码。

    • 码的 N 次扩展码

      信源符号 si 一一映射成码字 Wi 后,则 C 的 N 此扩展码就是所有 N 个码字组成的码序列内容。

    • 唯一(单义)可译码

      任意一串有限长的码符号序列只能被唯一地译成对应的信源符号序列。

      • 即时码

        又称“非延长码”,如果接收端在收到一个完整的码字过后,立刻执行。

      • 非即时码

        如果接收端在收到一个完整的码字过后,还需等待下一个码字(或码符号)接收后才能判断是否可以译码。

      • 逗号码

        用一个特定的码符号表示所有码字的结尾。

      • 异前置码

        等价即时码,一个码中无任何码字是其他码字的前置。

变长码 定长码
非奇异且异前置,就唯一可译 只要非奇异,就唯一可译
速率变化->设置缓冲器 速率恒定->不需缓冲器
受误码影响大,逗号码除外 码长已知->容易同步
容易产生差错传播 无差错传播

5.1.2 码树

在码树中,R 点是根节点,从树根伸出 r 个树枝,构成 r 元码树。树枝的尽头是节点,一般中间节点会伸出树枝,不伸出树枝的节点为终端节点,编码时尽量在终端节点安排码字。

若码树的各个分支都延伸到最后一级端点,此时共有 rn 个码字,这样的码树称为整树,否则为非整树。 等长码不一定对应整树。

按树图法构成的码若中间节点不安排码字,则一定满足唯一可译码(非延长码)的充要条件。

####5.1.3 Kraft 不等式

利用克拉夫特(Kraft)不等式,直接根据各码字的长度来判断唯一可译码是否存在,即各码字的长度应符合克拉夫特不等式:

\(\sum_{i=1}^qr^{-l_i}≤1\),r 为码符号个数,q 为信源符号数,\(l_i\) 是编码长度。

Kraft 不等式是唯一可译码存在的充要条件。满足 Kraft 不等式的码不一定是唯一可译码。

5.2 变长编码

变长码往往在码长的平均值不很大时,编出效率很高且无失真的码,其平均码长受香农第一定理所限定。要做到无失真的信源编码,平均每个信源符号所需要的最少 r 元码元数为信源的熵 Hr(S),即 Hr(S) 是无失真信源压缩的极限值。

无失真信源编码的实质:对离散信源进行适当的变换,使变换后形成新的码符号信源(信道的输入信源)尽可能等概率分布,以使新信源的每个码符号平均所携带的信息量达到最大,是信道的信息传输率 R 达到信道容量 C,实现信源与信道的统计匹配。这实际上也是香农第一定理的物理意义。

变长码的编码效率:\(\eta=\frac{H_r(S)}{\overline{L}}\),没有单位。

码的剩余度:\(1- \eta=1-\frac{H_r(S)}{\overline{L}}\)

信息传输率:\(R=\frac{H(S)}{\overline{L}}=\eta\),单位:比特/码符号。

对于某一信源和某一符号来说,满足 Kraft 不等式的唯一可译码可以有很多种,在这些唯一可译码中,如果有一种(或几种)码,其平均编码长度小于所有其他唯一可译码的平均编码长度,则该码称为最佳码(紧致码)。

5.2.1 香农码

香农码满足克拉夫特不等式,所以一定存在对应码字的长度的唯一可译码。编码步骤如下:

  1. 将信源发出的 M 个消息,按其概率递减顺序进行排列;

    \[q(x_1)≥q(x_2)≥q(x_3)≥…≥q(x_M)\]

  2. 计算出各消息的 \(-log q(x_m)\) 值,m=1,2,…,M;
  3. 求不小于 \(-log q(x_m)\) 的最小整数,代表每个消息的二进制代码的长度 \(l_m\)
  4. 计算出第 m 个消息的累加概率 \(p_i=\sum_{m=1}^{i-1}q(x_m)\),再将 pi 变换成二进制小数,取小数点后面 \(l_m\) 位作为第 m 个消息得代码组。

一般情况下,香农码得平均码长不是最短的,也不是紧致码。只有当信源符号得概率分布使不等式左边的等号成立时,编码效率才达到最高。

5.2.2 费诺编码法

  1. 信源发出的 M 个消息,按其概率递减顺序进行排列,把消息集 \(\{x_1,x_2,x_3,…x_M\}\) 按其概率大小分解为两个子集,使两个子集的概率之和尽可能接近相等,把第一个子集编码为“0”,第二个子集编码为“1”,作为代码组的第一个码元;
  2. 对子集做第二次分解,同样分解成两个子集,并使两个自己的概率尽可能接近相等,再把第一个子集编码为“0”,第二个子集编码为“1”,作为代码组的第二个码元;
  3. 如此一直进行下去,直到各子集仅含一个消息为之;
  4. 将主次分解过程当中得到的码元排列起来就是各消息的代码。

费诺码是即时码,不一定是最佳码。

r 元费诺码,每次分组时将符号分成概率分布接近的 r 个组。

5.2.3 霍夫曼码

  1. 将信源发出的 M 个消息,按其概率递减顺序进行排列;
  2. 将概率最小的两个消息分别编码为“1”和“0”,再对这两个消息求概率之和;
  3. 将上述概率之和作为一条新消息的概率,与余下的消息一起组成一新的信源,再按概率递减顺序重新排列。
  4. 如此一直进行下去,直到两个合并消息的概率之和为 1;
  5. 从最后一级缩减信源开始,向前返回,沿信源缩减过程的反方向取出所编的码元,得出各信源符号所对应的码符号序列,即为对应信源符号的码字。

注:若概率之和与原信源的某个概率相等,把概率之和排在上面。

霍夫曼码是一种分组码、唯一可解的码、即时码。

对于给定信源,用霍夫曼编码方法得到的码并非是唯一,但平均码长不变。

r 元霍夫曼编码:每次把概率最小的 r 个符号合并成一个新的信源符号。为使平均码长最短,最后一步的缩减信源有 r 个信源符号。因此对于 r 元编码,信源 S 的符号个数 q 满足 q = n(r-1) + r。当 q 不足时,填充概率为 0 的虚拟信源,使等式成立。

香农编码方法得出的二进制码组集合是唯一的,其余两个不是(信源等概率时,排序任意)。香农编码和诺曼编码是次最佳编码,霍夫曼编码是最佳编码方法(码平均长度最小)。

差错扩散:变长编码通过信道传送时,一个码字中有一个码元发生变化,会影响后面一系列的码字译码错误。

5.2.4 马氏源的编码

马氏源可采用按状态编码和多个符号合并编码。

按状态编码

  1. 给定一个初始状态 s0
  2. 对每个状态 s,根据转移概率 \(p(a_i|s=j),i=0,1,…,q-1\) 进行最优编码,例如 Huffman 编码。
  3. 设 Cj(j=0,1,…,J-1) 为对应的码表,其中规定信源符号 ai 和码字 yi(j) 的对应关系,记为 Cj(ai, yi(j))。

按平稳分布编码

  1. 求出平稳状态下概率分布;
  2. 对此概率分布进行最优编码,例如 Huffman 编码。

5.3 限失真信源编码

略。

5.4 实用信源编码方法

游程编码对相关信源编码更有效,考虑了连续重复出现符号串的长度。

香农编码、费诺编码、霍夫曼编码、游程编码都属于无失真信源编码

5.4.1 游程编码

游程 (Run-Length,RL) 指符号序列中各个符号连续重复出现而形成符号串的长度,有称游程长度或游长。游程编码 (Run-Length Coding,RLC) 就是将这种符号序列映射成游程长度对应符号序列的位置的标志序列

对二元相关信源,输出序列只有 “0” 和 “1”。

  • 连续出现的 0 符号称为 0 游程,其长度为 “0”游程长度 L(0);
  • 连续出现的 1 符号称为 1 游程,其长度为 “1”游程长度 L(1);

游程变换减弱了原序列符号间的相关性。将二元序列变换成了多元序列,这样就能适用其他编码方法(以游程长度为元素,构造新信源再编码)。

对 r 元序列也存在相应的游程:连续出现的 ai 符号称为 i 游程,其长度为 “i” 游程长度 L(i)。用 L(i) 也可以构建游程序列,但必须再加一些标志信源符号取值的符号,才能使编码后的又称序列与原来的 r 元序列一一对应。所以,编码效率通常不高。

游程编码是变长码,有着变长码固有缺点:

  • 需要大量的缓冲和优质的通信信道。
  • 游程长度可从 1 到无穷大,码字的选择和码表的简历有困难。

MH 编码

游程编码已在图文传真、图像传输等取得应用。MH 编码是一维编码方案,对一行一行的数据进行编码,将游程编码和霍夫曼码相结合,是一种改进的霍夫曼码。

5.4.2 算术编码

非分组码。不同于霍夫曼编码。利用累计概率概念,主要编码方法:计算输入信源符号徐丽额所对应的区间。基本思路:

  • 从整个符号序列出发,将符号序列的概率序列映射到 [0,1) 区间上,使每个符号序列对应于区间内的一点,也就是一个二进制小数。
  • 这些点把 [0,1) 区间分成许多小段,每段的长度等于某一信源序列的概率。
  • 在段内取一个二进制小数,其长度可与该序列的概率匹配,达到高效率编码的目的。

每个符号序列中随着符号数量的增加,用于代表符号序列概率的区间将随之减少:

二元信源的累计概率 G 和对应区间 A 的递推公式:

\[A(\vec{\alpha}r)=A(\vec{\alpha})p(r)=p(\vec{\alpha})p(r)=p(\vec{\alpha}r), r=0,1\\G(0)=0,G(1)=p(0)\\G(\vec{\alpha}r)=G(\vec{\alpha})+p(\vec{\alpha})G(r),r=0,1\]

\(G(\vec{\alpha})\) 为信源符号的累计概率,\(p(\vec{\alpha})\) 为信源符号的联合概率。我们可去小区间内任意一点来代表这个符号序列,通常取小区间的下界值。

常用编码方法,将信源符号序列的累计概率值 G 写成二进制小数,取小数点后 L 位(算术码字长度),若后面有尾数,就进位到第 L 位,L 是不小于 \(-log(p(\vec{\alpha}))\) 的最小整数。

算术编码优点:

  • 所需参数少、编码效率高、编译码简单、不需要大码表。
  • 自适应实现。

应用:JPEG。

5.3.3 预测编码

略。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×