信息论与编码（七）| 无失真变长编码定理与编码效率

编码效率与信源长度

为了衡量编码效果, 定义编码效率:

$\eta=\frac{H(X)}{H(X)+\varepsilon}, \varepsilon>0,$

对等长编码,若要实现几乎无失真编码,则信源长度必须满足:

$L \geq \frac{\sigma^{2}(X)}{\varepsilon^{2} \delta}$

其中: $\sigma^{2}(X)=E\left\{\left[I\left(x_{i}\right)-H(X)\right]^{2}\right\}$ , 为信源序列的自信息方差

例 2 :设离散无记忆信源概率空间

$\left[\begin{array}{l} X \\ P \end{array}\right]=\left[\begin{array}{cccccccc} a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & a_{6} & a_{7} & a_{8} \\ 0.4 & 0.18 & 0.1 & 0.1 & 0.07 & 0.06 & 0.05 & 0.04 \end{array}\right]$

• 信息熵: $H(X)=-\sum_{i} p\left(x_{i}\right) \log p\left(x_{i}\right)=2.55 \mathrm{bit} / 符号$

• 方差: $\sigma^{2}(X)=\sum_{i=1}^{8} p_{i}\left(\log p_{i}\right)^{2}-[H(X)]^{2}=7.82 b i t^{2}$

• 若取差错率 $\delta \leq 10^{-6}$ , 编码效率为 $90 \%$ , 则 L 应满足

  $\begin{array}{l} \varepsilon=\frac{1-\eta}{\eta} H(X) \approx 0.28 \quad L \geq \frac{\sigma^{2}(X)}{\varepsilon^{2} \delta}=\frac{7.82}{0.28^{2} \times 10^{-6}} \\ =9.8 \times 10^{7} \end{array}$

在差错率和编码效率要求并不十分苛刻的条件下,就需要 $L=10^{8}$ 个信源符号进行联合编码, 这显然是很难实现的。

无失真变长编码定理

变长编码定理

• 在变长编码中码长K是变化 的。
• 我们可根据信源各个符号的统计特性如概率大的符号用短码，概率小的用较长的码，这样在大量信源符号编成码后平均每个信源符号所需的输出符号数就可以降低，从而提高编码效率。

平均码长

对于等长码, 平均码长就是每个码字的位数, 如 例 1 的码 0 , 其平均码长为 $2 \mathrm{bit}$ ; 对于变长码, 平均码长为码字的码长的数学期, 即

$\overline{\mathrm{K}}=\sum_{i=1}^{L} p_{i} l_{i} \text { bit }$

其中 $l_{i}$ 为信源符号 $a_{i}$ 对应的码字的位数。

单个符号变长编码定理

若一离散无记忆信源的符号熵为 $H(X)$ , 每个信源符号用 m 进制码元进行变长编码,一定存在一种无失真编码方法, 其 码字平均长度 $\bar{K}$ 满足下列不等式:

$\frac{H(X)}{\log m} \leq \bar{K}<\frac{H(X)}{\log m}+1$

离散平稳无记忆序列变长编码定理

对于平均符号熵为 $H(\mathrm{X})$ 的离散平稳无记忆信源,必存在 一种无失真编码方法,使平均信息率 $\overline{\boldsymbol{K}}$ 满足不等式

$H(\mathbf{X}) \leq \overline{\mathbf{K}}<H(\mathbf{X})+\varepsilon$

其中 $\varepsilon$ 为任意小正数,
平均信息速率为: $\overline{\boldsymbol{K}}=\frac{\bar{K}}{L} \log m$ , 表示单个符号的平均 码长

用变长编码来达到相当高的编码效率,一般所要求 的符号长度 L 可以比定长编码小得多。
编码效率的下界:

$\eta=\frac{H(\mathbf{X})}{\overline{\mathbf{K}}}>\frac{H(\mathbf{X})}{H(\mathbf{X})+\frac{\log m}{L}}$

信息率与编码效率

• 信息率

$R=\frac{K}{L} \log m$

• 编码效率

$\eta=\frac{H(\mathbf{X})}{R}$