对模拟量的信源的编码(和译码)一般称为量化,它同时也是波形信源编译码的中间层(模拟序列 → 符号序列,符号序列 → 模拟序列)。

对于离散信源,可以把输入看成随机符号序列,对于量化器,则把输入看成是连续随机变量构成的序列U_1, U_2, ...,假设U_1, U_2, ...独立同分布,概率密度函数为f_U(u)。量化器需要把输入序列U_1, U_2, ...映射为离散随机变量V_1, V_2, ...,并要求每个V_m能以最小的失真表现出U_m,将模拟随机变量U量化为离散变量V后,用均方失真E[(U - V)^2]来定义失真。均方失真可以简单地把序列的失真转换为波形的失真。

标量量化

这种量化方式将实数集R划分成M个子集R_1, R_2, ..., R_M,每个子集是一个量化域。假设每个量化域是一个区间,每个域用一个代表点表示。对于信源产生的实数u \in R_j,将被量化成a_j。因此可将标量量化器看成一个函数\{v(u): R \rightarrow R\},对于某个随机变量U_k,量化输出的V_k是字符集为\{a_1, a_2, ... , a_M\}的离散随机变量。现在符号的问题搞清楚了,就要开始解决两个关键问题。

1. 给定带标点\{a_j\},如何设计区间\{R_j\}

2. 给定区间\{R_j\},如何选择带标点\{a_j\}

问题1,不妨考虑点u, a_j < u < a_{j+1},此时需要把u映射到距离u更近的那个点。因此,对于两个相邻域R_j, R_(j+1),它们的分界点b_j应该设定为两代表点a_j, a_{j+1}的中点。这里对均方失真的最小化与U_1, U_2, ...的概率模型无关。

问题2, 均方失真( Mean-Squared Error, MSE)可以表示为:

MSE = E[(U - V(U))^2] = \int_{-\infty}^{+\infty}f_U(u - v(u))^2du = \sum_{j = 1}^M\int_{R_j}f_U(u)(u - a_j)^2du

使得该式最小的a_j是随机变量在概率密度函数f_j(u)下的平均值。

由上述两个问题,可得结论,使MSE最小的端点\{b_j\}和代表点\{a_j\}满足:每个b_j必须是a_ja_{j+1}的中点,每个a_j必须是随机变量U_j在概率密度函数f_j(u)下的平均值。

Lloyd-Max算法

该算法可用于求解满足上述结论中条件的端点\{b_j\}和代表点\{a_j\},假定给定量化级数M,概率密度函数f_U(u),则算法流程为:

(1)任取一组代表点a_1 < a_2 < ... < a_M

(2)对每个j, 1 \le j \le M - 1,取b_j = (a_j + a_{j+1}) / 2

(3)对每个j, 1 \le j \le M - 1,取a_jU在条件U \in (b_{j-1}, b_j]下的条件均值,其中b_0 = - \infty, b_M = + \infty

(4)重复(2)和(3),直至MSE收敛

上述算法交替对端点\{b_j\}和代表点\{a_j\}进行优化,MSE非负,优化的过程又会使得MSE的值更优,因此算法是收敛的。但是该算法有可能达到的只是局部最优解(想想为什么)。借鉴模拟退火的思想,在随机种子足够多的情况下才有可能达到全局最优。

矢量优化

相较于标量优化,矢量优化说的是同时对n个信源变量进行优化,相当于在n维向量空间对信源变量优化。书中以二维作为例子,答案竟然是Voronoi图。之前做计算几何的时候学过,很神奇的一个东西。