信息论与编码（六）| 无失真定长编码定理

无失真信源编码

定义: 在无失真信源编码中, 编译码过程是可逆的, 即信源符号可以通过编码序列无差错的恢复 ，该编码方式适用于离散信源的编码。

实现无失真的信源编码,要求:
a. 信源符号 $\mathrm{X}_{1} \mathrm{X}_{2} \ldots \mathrm{X}_{l} \ldots \mathrm{X}_{L}$是一一对应于码字 $\mathrm{Y}_{1} \mathbf{Y}_{2} \ldots \mathbf{Y}_{k} \ldots \mathbf{Y}_{\mathbf{K}}$ ;
b. 能够无失真或无差错地从 $\mathbf{Y}$ 恢复 $\mathbf{X}$ , 也就是能正确地 进行反变换或译码;
c. 传送 $\mathbf{Y}$ 时所需要的信息率最小。

• 信源编码器输入的消息序列: $\mathbf{X}=\left(\mathrm{X}_{1} \mathrm{X}_{2} \ldots \mathrm{X}_{l} \ldots \mathrm{X}_{L}\right) , \mathbf{X}_{l} \in\left\{a_{1}, \ldots a_{\mathrm{n}}\right\}$ ,
  输入的消息总共有 $n^{L}$ 种可能的组合
• 输出的码字为: $\mathrm{Y}=\left(\mathrm{Y}_{1} \mathrm{Y}_{2} \ldots \mathrm{Y}_{k} \ldots \mathrm{Y}_{K}\right) , \mathbf{Y}_{k} \in\left\{\mathbf{b}_{1}, \ldots \mathbf{b}_{\mathrm{m}}\right\}$
  输出的码字总共有 $m^{K}$ 种可能的组合。
• 信息率最小就是找到一种编码方式使 $\bar{K}=\frac{K}{L} \log m$ 最小

无失真定长编码定理

在定长编码中,输出码字的长度 $\mathbf{K}$ 是定值。
我们的目的是寻找最小K值。
编码器输入 $\mathrm{X}=\left(\mathrm{X}_{1} \mathrm{X}_{2} \ldots \mathrm{X}_{l} \ldots \mathrm{X}_{L}\right), \mathrm{X}_{l} \in\left\{a_{1}, \ldots a_{\mathrm{n}}\right\}$ , 输入的消息总共有 $n^{\mathrm{L}}$ 种可 能的组合
输出 的码字 $\mathrm{Y}=\left(\mathrm{Y}_{1} \mathbf{Y}_{2} \ldots \mathrm{Y}_{k} \ldots \mathrm{Y}_{\mathrm{K}}\right), \mathrm{Y}_{k} \in\left\{\mathrm{b}_{1}, \ldots \mathrm{b}_{\mathrm{m}}\right\}$ , 输出的码字总共有 $m^{\mathrm{K}}$ 种可能的组合。
若对信源进行等长编码, 必须满足: $n^{\mathrm{L}} \leq m^{\mathrm{K}}$

等长编码

• 若对信源进行等长编码,必须满足: $n^{L} \leq m^{K}$ 或 $\frac{K}{L} \geq \frac{\log n}{\log m}$
• 只有当 K 长的码符号序列数 $m^{K}$ 大于或等于信源的符号数 $n^{L}$ 时,才可能存在等长非奇异码。

例如英文电报有 27 个符号, $\mathrm{n}=27, \mathrm{~L}=1, \mathrm{~m}=2$( 二元编码 )

$K \geq L \frac{\log _{2} n}{\log _{2} m}=\log _{2} 27 \approx 5$

• 实际英文电报符号信源,在考虑了符号出现的概率以及符号之间的依赖性后,平均每个英文电报符号所提供的信息量约等于1.4比特,大大小于5比特。
• 编码后5个二元符号只携带约1.4比特信息量。
• 等长编码的信息传输效率极低。

等长编码定理

由 L 个符号组成的、每个符号的熵为 $\mathrm{H}(\mathbf{X})$ 的无记忆平稳信源符号序列 $\mathrm{X}_{1} \ldots \mathrm{X}_{l} \ldots \mathrm{X}_{\mathrm{L}}$ , 可用 K 个符号 $\mathbf{Y}_{1} \ldots \mathrm{Y}_{k} \ldots \mathbf{Y}_{\mathrm{K}}$ (每个符号有 $\mathrm{m}$ 种可能值)进行等长编码。

对任意 $\varepsilon>0, \delta>0$ , 只要 $\frac{K}{L} \log m \geq H(\mathrm{X})+\varepsilon$, 则当 L 足够大时, 必可使译码差错小于 $\delta$ ;

反之, 当 $\frac{K}{L} \log m \leq H(X)-2 \varepsilon$时, 译码差错一定是有限值, 而当 L 足够大时, 译码几乎必定出错.

(1)当编码器容许的输出信息率, 也就是当每个信源符号所必须输出的码长是

$\overline{\boldsymbol{K}}=\frac{\mathrm{K}}{\mathrm{L}} \operatorname{logm}$

时,只要 $\bar{K}>H(X)$ , 这种编码器一定可以做到几乎无失真, 也就是收端的译码差错概率接近于零, 条件是 所取的符号数 L 足够大。

(2)将定理的条件改写成

$K \log m>L H(X)=H(\mathbf{X})$

其中：左边： K 长码字所能携带的最大信息, 右边: L 长信源序列携带的信息量。上述定理表明：

• 只要码字所能携带的信息量大于信源序列输出的信息量, 则可以使传 输几乎无失真, 当然条件是 L 足够大。
• 反之, 当 $\bar{K}<H(X)$ 时, 不可能构成无失真的编码, 也就是不可能做一 种编码器, 能使收端译码时差错概率趋于零。
• $\bar{K}=H(X)$ 时, 则为临界状态, 可能无失真, 也可能有失真。