分组码
- 将信源消息分成若干组，用符号序列$\mathbf {x_i}=(x_{i_1},x_{i_2},\cdots,x_{i_l},\cdots,x_{i_L})$表示，序列中每个符号都取自于符号集$A$，$x_{i_L}\in A=\{a_1,a_2,\cdots,a_i,\cdots,a_n\}$，每个$x_i$依照固定的码表映射成一个码字$y_i$
  - 按照码表映射编码的码称为分组码，有时也叫做块码，只有分组码才有对应的码表，非分组码不存在码表
码字
- 每个码符号序列称为码字，如编码后的${0001,0010,1100}$
$D$元码
- 由$D$个符号组成的码字集合，如${0,1}$对应二源码，${0,1,2}$对应三元码

理解

根据编码方式的不同，同一个信源符号可以有不同的码符号序列
将信源符号变换成由码元符号组成的码符号序列的过程就是信源编码的过程

码树

形状
- 倒立的树，树根在上，树枝在下
概念
- 树枝：码树中的线段，表示编码路径，用码字符号标注
- 节点：结点，树枝的端点
- 树根：最顶端的节点，编码的起始段，码字起点
- $r$级节点：从树根开始经过第$r$个分支节点所到达的节点
- $m$进码树：一个节点最多能伸出$m$个树枝的码树，表示$m$进制
- 终端节点：码树的最底层节点，不再伸出树枝，表示编码结束
- 节数：码长
- 满树：每个分支都延伸到最后一级节点的码树，共有$m$的$r$次方个等长码
码树与编码的关系
- $m$进码树表示对应的编码为$m$进制编码
- 码字为树根到每个终端节点树枝的标号序列，是即时码
- $r$级终端符号对应的一个码字最多有$r$个码字符号组成
- $n$个终端节点则对应n个不同的码字

讨论

唯一可译码存在的充要条件：各码字的长度$K_i$符合克劳夫特不等式，式中$m$为进制数，$n$为信源符号数
$$ \sum_{i=1}^nm^{-K_i}\leqslant1 $$
以上判断方式并没有涉及具体的编码结果，所以只能判断某种编码方式是否存在唯一可译码，并不能给出具体的结果，也不是所有满足上述编码方式的编码结果都是唯一可译码

无失真信源编码定理

编码的数学模型

拟进行编码的信源符号序列长度为$L\geqslant 1$，以传输$11$个符号$information$为例，则可将信源序列描述为
$$ \mathbf X=(i,n,f,o,r,m,a,t,i,o,n),X_l\in\{a,b,\cdots,z\},L=11 $$
码表为26个字母$a,b,c,\cdots,z$依次编码成$00000, 00001,\cdots,11001$，变换成由$K_L$个符号组成的码序列，编码后的输出序列可写作
$$ \mathbf Y=(01000,01101,00101,01110,10001,01100,00000,10011,01000,01110,01101),Y_k\in\{0,1\} $$
编码变换的基本要求是能够无差错地从$Y$恢复到$X$，能够正确地进行反变换（译码），同时希望传送$Y$的信息率最小，因此延伸出几个概念
- 编码输出序列含有的最大信息量为（$K_L$长的输出符号序列，含有$K_L$个码元，二进制情况下每个码元所携带的信息量为$\log2$）
  $$ K_L\log_2m=55\log_22 $$
  - 而该输出码字表示了本身长为$L=11$的信源发出序列（即原始信源序列里有$11$个符号），则每发送一个信源符号所需要的信息率平均值为（$m$为进制数，不同进制下要对应将$m$的值做出改变）
  $$ \begin {align} \overline{K}&=\frac {K_L} L \log m=\frac 1 L\log m^{K_L}=\frac 1 L \log M\\ &=\frac {55} {11}\log_22=5\log_22=5=\frac 1 {11}\log_22^{55} \end {align} $$
  - $M=m^{K_L}=2^{55}$表示输出序列能够编码的码字个数（所有可能的情况数量）
为了让信息率最小，也就意味着要找到一种编码方式，使得符号平均信息率K拔值最小，由此引出无失真信源编码定理（包括定长、边长编码）

定长编码定理

讨论
- 研究对象：离散无记忆信源
- 成立条件
  - $K=K_L$，各码字的序列长度相等
  - 编码是唯一可译码
  - 对于$m$元码，最多有$m^{K_L}$个码字
- 目的
  - 寻找最小的$K$值
  - 实现无失真传输，满足条件：信源符号和码字是一一对应的且由码字组成的码符号序列的逆变换也是唯一的
定义
- 设由$L$个符号组成的，每个符号熵为$H_L(\mathbf X)$的无记忆平稳信源符号序列$X_1,X_2,...,X_L$可以用$K_L$个符号$Y_1,Y_2,\cdots,Y_k,\cdots,Y_{K_L}$进行定长编码（其中每个符号有$m$种可能的取值）
  - 正定理：对于任意$\epsilon>0,\delta>0$,只要$\frac {K_L} L\log m\geqslant H_L(\mathbf X)+\epsilon$那么当$L$足够大时，必可使译码差错小于$\delta$
  - 逆定理：反之，当$\frac {K_L} L\log m\leqslant H_L(\mathbf X)-2\epsilon$时，译码差错一定是有限值，且当$L$足够大时，译码几乎必定出错
  - 类似极限的定义，有着相同的思路
  - $\overline K=\frac {K_L} L \log m$是编码后发送一个信源符号所需要的平均信息量
分析
- 正定理说明
  - 当编码和信源满足关系$\overline K=\frac {K_L} L \log m>H_L(\mathbf X)$或$K_L\log m>LH_L(\mathbf X)=H(\mathbf X)$，即编码发送一个消息符号所需平均信息量大于信源平均每符号的信息量时，近乎无失真编码存在
  - 当$L$足够大时，译码误差可以控制在小于$\delta$内，而这个$\delta$值是任取的
  - 换一种形式来说，假设$L$足够大，当$K_L$长的码字所能够携带的最大信息量大于信源序列输出的信息量时，则可以使得传输几乎无失真
- 逆定理说明
  - 当编码和信源满足关系$\overline K=\frac {K_L} L \log m <H_L(\mathbf X)$或$K_L\log m<LH_L(\mathbf X)=H(\mathbf X)$，即编码发送一个消息符号所需平均信息量小于信源平均每符号的信息量时，必定存在编码失真
  - 当$L$足够大时，译码几乎必定出错
  - 此时不可能做成一种编码器可以使得接收端译码时的差错概率趋于$0$，译码误差必然存在，且为一个有限值$\delta>0$
- 临界情况下
  - 即满足关系$\overline K=\frac {K_L} L \log m =H_L(\mathbf X)或K_L\log m=LH_L(\mathbf X)=H(\mathbf X)$时
  - 此时可能有失真，也可能无失真，要进一步讨论
  - 通过例题发现，当处于临界状态时，若信源等概率分布，则可以实现无失真编码，反之不可能实现无失真，必然存在编码误差
差错概率测度与控制
- 假设信源序列长度为$L$，由文献可知$P_e\leqslant\frac {\sigma^2(\mathbf X)} {L\epsilon^2}$
- 其中$\sigma^2(\mathbf X)=E\{[I(\mathbf x_i)-H(\mathbf X)]^2\}$为信源序列的自信息方差
- 当$\sigma^2(\mathbf X)$和$\epsilon$为定值时，只要$L$足够大，差错概率便可小于任意一个数$\delta$，即当$L$序列长度满足$L\geqslant\frac {\sigma^2(\mathbf X)}{\epsilon^2\delta}$时，编码可以满足用户定义的差错概率$\delta$，该值一般很小，如$10^{-9}$等
连续信源限失真编码原理
- 由前面所学知识可知，连续信源的信息量趋于无穷，不能用离散符号序列进行无失真编码，只能进行限失真编码
  $$ H(\mathbf X)=-\int_a^bp_X(x_i)\log p_X(x_i)\mathrm d x=\lim_{\Delta x\to0}\log \Delta x $$
- 定义采用平均码长$K_L$编码所得到的编码效率为
  $$ \eta=\frac {H_L(\mathbf X)} {\overline K} $$
- 最佳编码效率可定义为（当$L$趋近于无穷大时，可实现编码效率趋近于1，但在实际中无法实现，最佳编码可看作平均码长最接近于熵的无损编码）
  $$ \eta = \frac {H_L(\mathbf X)} {H_L(\mathbf X)+\epsilon},\epsilon >0,\lim_{\epsilon \to 0}\eta =1 $$

变长编码定理

讨论
- 变长编码的特点：用不同长度的码序列实现信源符号的编码
- 编码方法：根据信源符号的不同统计特性采用不同长度的码字编码，如用短码表示大概率符号，长码表示小概率符号，提高编码效率
单个符号的变长编码定理
- 若离散无记忆信源的符号熵为$H(X)$，每个信源符号用$m$进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足不等式
  $$ \frac {H(\mathbf X)}{\log m}\leqslant\overline K<\frac {H(\mathbf X)}{\log m}+1 $$
- 注意：上式是一个左闭右开的不等式，且这里的$\overline K$和前面的定长编码中的定义不同，这里指的是码字的平均长度
  $$ \overline K=\sum_{i}p_iK_{L_i} $$
- 当$m=2$时，即码元符号是二进制时，此时码字平均长度和码字平均符号信息量相等，意味着码字平均符号信息量和信息熵相差$1bit$以内
  $$ H(\mathbf X)\leqslant \overline {K_1}<H(\mathbf X)+1 $$
离散平稳无记忆序列变长编码定理
- 对于平均符号熵为$H_L(X)$的离散平稳无记忆信源，必然存在一种无失真编码方法，使得平均信息率（码字平均符号信息量）满足不等式（其中$\epsilon$为任意小正数）
  $$ H_L(\mathbf X)\leqslant\overline K<H_L(\mathbf X)+\epsilon $$
变长编码的编码效率
- 变长编码一般可以达到较高的编码效率，其下界可以根据上述定理得知
  $$ \eta = \frac {H_L(\mathbf X)}{\overline K}>\frac {H_L(\mathbf X)}{H_L(\mathbf X)+\frac {\log m}{L}} $$
剩余度
- 认为编码效率趋近于1的编码为最佳编码，为了衡量各种编码方法和最佳编码之间的差距，定义编码的剩余度为$\gamma$，实际中剩余度可以无限接近于$\gamma$，但却无法达到
  $$ \gamma=1-\eta=1-\frac {H_L(\mathbf X)}{\overline K}=1-\frac {H_L(\mathbf X)}{\frac {\overline {K_l}}{L}\log m} $$
最佳编码
- 特征
  - 能载荷一定的信息量
  - 码字的平均长度最短
  - 可分离的变长码的码字组合
- 方法
  - 概率大的信息符号编以短码字，概率小的编长码字，使得平均码长最短
- 常见方法
  - Shannon Coding 香农编码
  - Fano Coding 费诺编码
  - Huffman Coding 哈夫曼编码
香农编码
- 香农第一定理：如果编码后的信源序列信息传输率不小于信源的熵，则可实现无失真编码，反之不存在无失真编码
- 编码过程
  - 1.将信源消息符号按照其出现概率大小依次排列得到
    $$ p(x_1)\geqslant p(x_2)\geqslant \cdots \geqslant p(x_n) $$
  - 2.按照以下关系确定整数码长$K_i$
    $$ -\log p(x_i)\leqslant K_i\leqslant-\log p(x_i)+1 $$
  - 3.为了变成唯一可译码，计算消息的累加概率
    $$ P_i=\sum_{k=1}^{i-1}p(a_k) $$
  - 4.将累加概率$P_i$变成二进制数（小数点后不断乘2，出现进位则记为1，反之记为0）
  - 5.将$P_i$二进制数小数点后$K_i$位作为该消息符号的二进制码字
- 讨论
  - 香农编码方法的多余度较大，编码效率低，实用性不强
  - 但其给出了香农第一定理，给出了最佳编码方法（概率小码长，概率大码短），也提出了累加概率的概念
费诺编码
- 特点
  - 属于概率匹配编码
  - 有代表性，但不是最佳编码
- 编码过程
  - 1.将信源消息符号按照出现的概率大小依次排列得到
    $$ p(x_1)\geqslant p(x_2) \geqslant \cdots \geqslant p(x_n) $$
  - 2.将依次排列好的信源符号按照概率值分为$m$组（几进制就分几组），使得各组的概率之和趋近于相同，并对各组依次赋$m$进码元
  - 3.将每一大足的信源符号进一步分成$m$个组，使得划分后的$m$组的概率之和趋近相同，再依次给各组赋$m$进码元
  - 4.重复以上步骤，直到每组只剩下一个信源符号位置
  - 5.将信源符号的码字从左到右读出，即费诺码

常用信源编码方法

讨论

变长编码
- 优点：无损编码，相对于定长编码有着较高的编码效率
- 缺点：具有分组码具有的缺点
常见编码方法
- 信源统计特性已知/未知编码
- 无失真/限失真编码
- 无记忆/有记忆编码
- 分组/非分组码
- 等长/变长码
- 最常见的是已知统计特性，离散、平稳且无失真的信源编码

哈夫曼编码

编码过程
- 1.将$n$个信源符号按其概率大小依次排列得到
  $$ p(x_1)\geqslant p(x_2) \geqslant \cdots \geqslant p(x_n) $$
- 2.取两个概率最小的字母分布依次配以$m$个码元，并将这$m$个概率相加作为一个新字母的概率，与未分配的字母重新排队
- 3.对重排后的$m$个概率最小符号重复第二步
- 4.不断重复以上过程，直到最后$m$个符号分配完成
- 5.从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即对应码字
讨论
- 哈夫曼编码并不是唯一的，其和$m$个符号的放置顺序、相同合并概率的放置位置有关
- 一般将合并后的概率放在最靠上的位置（如当合并后的概率和其他剩余概率值相等时，应放在这些相同概率值的最上面），以减小方差
- 哈夫曼编码的效率高于费诺编码和香农编码
- 随着序列长度$L$的不断增加，平均码长迅速降低，接近信源熵值，效率不断增加
特点
- 短码对应概率大的信源符号，长码对应概率小的信源符号，提高了编码效率
- 缩减信源的最后两个码字总式最后一位不同，保证了哈夫曼编码为即时码
优点
- 哈夫曼编码通过概率匹配的方法提高了编码效率
- 当信源为单个符号或序列长度较小时，哈夫曼编码仍可达到较高的编码效率（相比下高于费诺编码和香农编码）
缺点
- 其码字长度有时比定长编码的码字长，使得送出一个信源符号所需的平均信息量增加
- 当传输码字序列中任意符号出错，就会存在译码断点，从而造成后面一系列译码出错，产生差错扩散，但定长编码不会出现这种情况
- 对单个符号进行变长编码永远不能使得编码效率接近于$1$
- 对于多个符号一起编码，虽然能够提高编码效率，但是也要大幅增加码表长度，增加存储器
- 需要大量存储设备来缓冲码字长度，存储容量不够大时，容易出现短码取空，长码溢出的现象

算数编码

基本思想
- 算术编码属于非分组码，需要将编码的全部数据看成某一长$L$的序列，将所有可能出现的L长序列的概率映射到$[0,1]$区间上，把$[0,1]$区间划分成许多个小段，每段的长度等于某一序列概率，再在段内取一个二进制小数作为码字，长度与序列概率匹配，从而实现高效率编码
编码过程
- 1.获取信源各符号的先验概率，转换为二进制数，将各符号的概率累加，获得符号累加概率（累加概率都用大写$P$表示，普通概率用小写$p$表示）
  $$ P_r=\sum_{i=1}^{r-1}p_i,P_0=0,P_1=p_1,P_2=p_1+p_2,\cdots $$
- 2.计算序列累加概率
  $$ P(S,a_r)=P(S)+p(S)P_r,p(S,a_r)=p(S)p_r $$
- 3.$P(S)$把区间$[0,1]$根据各序列的概率分布分割成若干个小区间，每个小区间的长度为其对应的序列的概率$p(S)$，各个小区间不重叠，选择小区间内任意一点可用来唯一代表该区间，取$P(S)$的小数点后$L$位，得到编码
  $$ L=\left \lceil \log \frac 1 {p(S)} \right \rceil $$
  - 如果小数位数$=L$，则直接取小数后$L$位，即$P(S)=C$
  - 如果小数位数$>L$，则将尾数依次向前进位，即
    $$ P(S)=C-2^{-L}+\sum_{i=L+1}^ma_k2^{-i},k=2,a_k\in\{0,1\} $$
讨论
- $C$的取值满足关系
  $$ P(S)\leqslant C<P(S+1) $$
  这是一个左闭右开的区间，永远不可能取到$P(S+1)$）
- 各个小区间是不重叠的，可以实现唯一译码
- 满足概率匹配，编码效率高
- $L$较大时，$P(S)$对应较小，使得取整造成的误差较小，平均码长接近于信源熵值
编码算法
- 实际应用中，采用累积概率$P(S)$来表示码字$C(S)$，符号概率$p(S)$来表示状态区间$A(S)$，可得递推关系
  $$ \left \{ \begin {matrix} C(S,r)=C(S)+A(S)P_r\\ A(S,r)=A(S)p_r \end {matrix} \right. $$
- 定义两个存储器，将初始值设置为
  $$ A(\varphi)=1,C(\varphi)=0 $$
- 每输入一个信源符号，两个存储器$A$和$C$就按照递推关系更新一次，输入结束时，$C$就作为编码输出
- 在计算过程中，状态区间$A(S)$会越来越小，由于$C(S)$是递增的，增量$A(S)P_r$会随着序列的增长而减小
举例
- 设有四个符号$a,b,c,d$，其符号概率分别为$0.100,0.010,0.001,0.001$，构成简单序列$\{abda\}$，求其算数编码
- 可得各符号的累积概率依次为$0.000,0.100,0.110,0.111$，设初始状态为空序列$\phi$，定义两个存储器$A(\varphi)=1,C(\varphi)=0$，接着由递推关系依次求解
  $$ \begin {align} &C(\phi,a)=C(\phi)+A(\phi)P_a=0+1\times0=0;\\ &A(\phi,a)=A(\phi)p_a=1\times0.1=0.1;\\ &C(a,b)=C(a)+A(a)P_b=0+0.1\times0.1=0.01;\\ &A(a,b)=A(a)p_b=0.1\times0.01=0.001;\\ &C(a,b,d)=C(a,b)+A(a,b)P_d=0.01+0.001\times0.111=0.010111;\\ &A(a,b,d)=A(a,b)p_d=0.001\times0.001=0.000001;\\ &C(a,b,d,a)=C(a,b,d)+A(a,b,d)P_a=0.010111+0.000001\times0=0.010111;\\ &A(a,b,d,a)=A(a,b,d)p_a=0.1\times0.000001=0.0000001;\\ \end {align} $$
- 接着计算序列码长
  $$ L=\left \lceil \log \frac 1 {p(S)} \right \rceil=\left \lceil \log \frac 1 {A(a,b,d,a)} \right \rceil=7 $$
- 于是得到编码为$C$小数点后$7$位，不够的补$0$，得到$0101110$
- 可同时求得编码效率为
  $$ \eta=\frac {H(\mathbf X)}{\overline K}=\frac {1.75}{\frac 7 4}=100\% $$
拓展
- 算术编码是一种现代编码方法，实际中比哈夫曼编码更加有效
- 算术编码在图像数据压缩标准（如JPEG,JBIG）中扮演了重要角色

限失真信源编码定理

讨论

无失真编码：输入符号与输出符号一一对应，信道的损失熵（疑义度）和噪声熵均为0，通过信道的信息传输率等于信源熵，因此无失真信源编码是保熵的过程，只是对冗余度进行了压缩
有失真编码的中心任务：在允许失真的范围内把编码后的信息量压缩到最小，有失真信源编码的失真范围受限，也称为限失真信源编码，编码后的信息率受到压缩，属于熵压缩编码
信息率失真函数$R(D)$的物理意义：允许失真为$D$时的最小信息率，当信息率大于$R(D)$时可以进行编码，小于时出现信息损失，不可在允许失真范围内编码

引入限失真编码定理的原因

保熵编码并非都是必须的，有时候信宿不需要或者没有能力接受信源发出的全部消息
保熵编码并非总是可能的，如对连续信号进行数字处理时，不可能从根本去除量化误差
降低信息率有利于信息传输和处理，从而有必要进行熵压缩编码

定理阐述

设离散无记忆信源$X$的信息率失真函数为$R(D)$，则当信息率$R>R(D)$，只要信源序列长度$L$足够长，则一定存在一种编码方法，其译码失真小于或等于$D+\epsilon$，$\epsilon$为任意小的正数，反之则无论采用怎样的编码方法，其译码失真必定大于0
二元信源的情况下，对于任意小的$\epsilon>0$，每一个信源符号的平均码长应满足不等式
$$ R(D)\leqslant\overline K\leqslant R(D)+\epsilon $$

理解

该定理适用于离散、连续的信源
在失真限度内使得信息率接近$R(D)$的编码方法存在
要使得信息率小于$R(D)$，平均失真一定会超过失真限度$D$

无失真与限失真编码定理比较

相同之处：都对信息量有一定的要求，给出了编码平均长度的范围
不同之处：限失真编码定理中通过引入允许的一定程度失真，较大幅度地提高了编码效率

信息论基础 | 信源编码

第5章 信源编码

前言

编码方式

信源编码

编码的概念

定义

理解

分类

码树

讨论

无失真信源编码定理

编码的数学模型

定长编码定理

变长编码定理

常用信源编码方法

讨论

哈夫曼编码

算数编码

限失真信源编码定理

讨论

引入限失真编码定理的原因

定理阐述

理解

无失真与限失真编码定理比较

其他编码方法（略）

LZ编码、游程编码、矢量量化编码、预测编码、变换编码

第5章信源编码