信源编码 | 无线通信基础知识

一、信源编码

1. 目的：减少冗余，提高有效性

2. 码的分类：非奇异码、惟一可译码、即时码(前缀码)

3. 码树：如果所有叶子都用了，则有$|\chi |-1$是$D-1$的整数倍，$|\chi |$为消息符号的个数，D为几元字母表，eg:$D=1,2,3,D=3$

4. Kraft不等式(对于即时码)：
   对于D元字母表上的即使码，码字长度$l_1,l_2....l_{|\chi |}$满足以下不等式：
   $$\sum _{i=1}^{|\chi |}{D}^{-l_i}\le 1$$
   反之，若给定以上不等式的一组码字长度，存在相对应的即时码，码字长度是给定的长度。

5. Kraft不等式(对于非奇异码)
   对于D元字母表上的即使码，码字长度$l_1,l_2....l_{|\chi |}$满足以下不等式：
   $$\sum _{i=1}^{|\chi |}{D}^{-l_i}\le 1$$
   怎么一样？？？

6. 最优码
   构建优化问题，目标函数是$L=\sum p_i{l}_i$，限制条件：$\sum D^{-l_I}\le 1$，利用拉格朗日乘子法将带约束的最小化问题转换为求下式得最小化问题：
   $$J=\sum p_i{l}_i+\lambda \sum D^{-l_i}$$
   对码字进行求导等于0：
   $$\frac{\partial J}{\partial l_i}=p_i-\lambda D^{-l_i}lo{g}_{e}D=0$$
   $$D^{-l_i}=\frac{p_i}{\lambda lo{g}_{e}D}⟹\lambda =\frac{1}{lo{g}_{e}D},p_i=D^{-l_i}$$
   则最优码长：
   $$l_i^{\ast }=-lo{g}_D{p}_i$$
   若取码字长度为整数，此时希望的码长：
   $$L^{\ast }=\sum p_i{l}_i=-\sum p_{i}lo{g}_D{p}_i=H_D(X)$$
   引出以下定理：随机变量X的任一D元即时码的期望长度必定大于或等于熵$H_D(X)$，即$L\ge H_D(X)$，当且仅当$p_i=D^{-l_i}$

7. 最优码的边界：
   定理：设$l_1^{\ast },l_2^{\ast }...l_{|\chi |}^{\ast }$是关于信源分布p和D元字母表的一组最优码长，$L^{\ast }$为最优码长期望的长度$L^{\ast }=\sum p_i{l}_i$，则：
   $$H_D(X)\le L^{\ast }<H_D(X)+1$$

note:+1是由于$-lo{g}_D{p}_i$并不总是整数造成的，可通过扩展将多字符进行分组编码缩减每个字符的附加位。

8. 熵率
   定义：当存在如下定义时，随机过程$X_i$的熵率为：$$H(\chi )=\underset{n\to \infty }{\lim }\frac{1}{n}H(X_1,X_2,....,X_n)$$
   若$X_i$是独立同分布i.i.d.则有：
   $$H(\chi )=\underset{n\to \infty }{\lim }\frac{1}{n}nH(X_1)=\underset{n\to \infty }{\lim }H(X_1)$$
   若$X_i$不是独立同分布，则有：
   $$H(\chi )=\underset{n\to \infty }{\lim }\frac{1}{n}\sum _{i=1}^{n}H(X_i)$$

二、shannon第一定理 / 无失真信源编码

定义$L_n$为输入字符期望码字长度，设$l(x_1,x_2,...,x_n)$是与$(x_1,x_2,...,x_n)$相应的二级制码字长度，则有：
$$L_n=\frac{1}{n}\sum p(x_1,x_2,...,x_n)l(x_1,x_2,...,x_n)=\frac{1}{n}E[l(x_1,x_2,...,x_n)]$$
则有最优码的界应用此编码
$$H(x_1,x_2,...,x_n)\le E[l(x_1,x_2,...,x_n)]\le H(x_1,x_2,...,x_n)+1$$
由于$x_1,x_2,...,x_n$是统计独立同分布的i.i.d，则有：
$$H(x_1,x_2,...,x_n)=\sum H(x_i)=nH(X)\Rightarrow H(X)\le L_n<H(X)+\frac{1}{n}$$
如果随机过程是平稳的，则：
$$\frac{H(x_1,x_2,...,x_n)}{n}\le L_n\to H(\chi )$$

$n\to \infty$时，每字符期望长度趋于熵率$H(\chi )$.

三、Shannon码和Huffman码

1. Shnanon码
   码字长度分配$l(x)=\lceil log\frac{1}{q(x)}\rceil$关于p(x)的期望码长，满足
   $$H(p)+D(p||q)\le E_{p}l(x)<H(p)+D(p||q)+1$$
   note：$$D(p||q)=\sum _{x}p(x)log\frac{p(x)}{q(x)}、H(p)=\sum _{x}p(x)log\frac{1}{p(x)}$$
   若真实分布为$p(x)$，编码时使用非真实分布$q(x)$会导致期望长度增加$D(p||q)$
2. Huffman码
   D元码要先验证信源数目是否充足，即$|\chi |-1$是否为D-1的整数倍，要求$\lceil \frac{|\chi |-1}{D-1}\rceil$，若不是整数倍，需要加一个虚拟符号

$\chi$是消息个数，D是D元码。

3. Huffman码的最优性
   满足以下条件，即为最优码：

长度序列与按概率分布排列的次序相反，即若$p_j>p_k$，则$l_j<l_k$
最长的码字有相同的长度
最长的两个码字仅在最后一位上有差别，且对应于两个最小可能发生的字符

4. Shannon码的竞争最优性
   设$l(x)$为Shannon码的相应码字长度，$l^{\prime }(x)$表示其他唯一可译码的相应码字长度，则$$Pr(l(x)\ge l^{\prime }(x)+c)\le \frac{1}{2^{(c-1)}}$$
   eg：$l^{\prime }(x)$比$l(x)$短5bit，或更多的概率不超过$\frac{1}{16}$
5. Shannon码长$L_s$和Huffman码长$L^{\ast }$关系
   $$H(X)\le L^{\ast }\le L_s<H(X)+1$$
   参考文章：通信算法基础知识汇总（6）