量化

无损压缩算法大致由两个步骤组成：改变信号的表示以减少样本的熵（Entropy），以及熵编码（Entropic Coding）。有损压缩算法在表示变换和编码之间插入了一个量化（Quantification）步骤。它在信号表示中引入了误差，但同时也能更大程度地减少熵，这比无损情况下的效果更明显。

均匀量化

连续信号通常具有无限多的可能值，例如一个音频信号的幅度可能是任意的实数。然而，数字系统只能处理有限的值集合，例如整数或固定的小数位数。因此，在数字化过程中，需要对信号的幅度进行近似，使其符合离散值集合的要求。这个近似过程就是量化。

最简单的量化方法是均匀量化器$Q_\Delta$:

$Q_{\Delta}(x)=\Delta R(x / \Delta)$

其中$R$表示四舍五入，$\Delta$是量化步长。

例如对区间$[-1,1]$以步长$\Delta = 0.5$进行量化后，有：

$Q_\Delta(-1) = 0.5R(-1/0.5) = -1$
$Q_\Delta(-0.74) = 0.5R(-0.74/0.5) = -0.5$
$Q_\Delta(-0.4) = 0.5R(-0.4/0.5) = 0$
$Q_\Delta(0.5) = 0.5R(0.5/0.5) = 0.5$
…

为了计算这种量化引入的误差，我们假设需要量化的数据由一个已知概率密度 $p(x)$ 的随机变量 $X$ 生成，并且这种概率密度在量化间隔 $[(n-1 / 2) \Delta,(n+1 / 2) \Delta[$ 上（近似）为常数（高分辨率量化假设）。
在这种情况下，通过基础计算可以得到量化误差：

$d=\mathbb{E}\left((X-Q(X))^2\right)=\frac{\Delta^2}{12}$

$d=\mathbb{E}\left((X-Q(X))^2\right) = \frac{1}{\Delta}\int{(n-1/2)\Delta}^{(n+1/2)\Delta}(x-n\Delta)^2dx = \frac{1}{\Delta}\left|\frac{(x-n\Delta)^3}{3}\right|{(n-1/2)\Delta}^{(n+1/2)\Delta} = \frac{\Delta^2}{12}$

通过将数据用二进制表示，可以观察到增加一个比特相当于将 $\Delta$ 减半（相当于量化级从$2^n$增加到$2^{n+1}$），从而量化噪声的功率减少 $6.04 dB$ 。

熵约束下的标量量化

我们现在研究更通用的量化器，它由一组区间 $\left[a_{k-1}, a_k\left[\right.\right.$ 和值 $b_k$ 描述，这些区间将实数轴划分开。量化器定义为：

$Q(x)=b_k, \quad x \in\left[a_{k-1}, a_k[\right.$

记:

$\Delta_k=a_k-a_{k-1}, \quad \tilde{X}=Q(X)$

在高分辨率假设下，有:

$p_k=\Delta_k p(x), \quad pour \ x \in\left[a_{k-1}, a_k[\right.$

可以近似认为在每一个区间中，量化器与前一章提及的量化器相同。根据先前的计算，此时的误差为：

$d=\frac{1}{12} \sum_{k \in \mathbb{Z}} p_k \Delta_k^2$

微分熵

定义具有概率密度$p$的随机变量$X$的微分熵为：

$H_d(X)=-\int_{-\infty}^{+\infty} p(x) \log _2 p(x) d x$

定理

在高分辨率假设下有：

$H(\tilde{X}) \geq H_d(X)-\frac{1}{2} \log _2(12 d)$

证明：

$\begin{aligned}H(\tilde{X})&=-\sum_{k \in \mathbb{Z}} p_k \log _2 p_k =-\sum_{k \in \mathbb{Z}} \frac{1}{\Delta_k} \int_{a_{k-1}}^{a_k} \Delta_k p(x) \log _2\left(\Delta_k p(x)\right) d x\\&=-\sum_{k \in \mathbb{Z}} \int_{a_{k-1}}^{a_k} p(x) \log _2 p(x) d x-\sum_{k \in \mathbb{Z}} p_k \log _2 \Delta_k\\&=H_d(X)-\frac{1}{2} \sum_{k \in \mathbb{Z}} p_k \log _2 \Delta_k^2\end{aligned}$

由于$-log_2$的凸性，有：

$\sum_{k \in \mathbb{Z}} p_k\left(-\log _2 \Delta_k^2\right) \geq-\log _2\left(\sum_{k \in \mathbb{Z}} p_k \Delta_k^2\right) = -\log_2(12d)$

即可证明。

推论

对于给定量化误差 $d$ ，熵在量化步长 $\Delta_k=\Delta$ 恒定时达到最小值。
要保证给定量化跨差 $d$ ，所需的比特率为:

$R=H_d(X)-\frac{1}{2} \log _2(12 d)$

代入步长的关系：

$R=H_d(X)-\log _2 \Delta$

反过来，根据比特率计算误差:

$d=\frac{1}{12} 2^{2 H_d-2 R}$

矢量数据的量化

通过在正交基 $\left(\phi_n\right)_n$ 上分解矢量数据（选择一个正交基可以保证信号误差与系数误差一致），对每个系数 $X_n=\left\langle\phi_n, X\right\rangle$ 单独进行编码。

目标是找到应用于每个系数的量化步长 $\Delta_n$ ，在固定比特率的条件下最小化误差。

$d=\sum_{n=1}^N d_n$

展开后：

$d=\frac{1}{12} \sum_{n=1}^N 2^{2 H_{d, n}-2 R_n}$

总的比特率为：

$R=\sum_{n=1}^N R_n$

定理
在高分辨率假设下，当量化步长为 $\Delta_n=\Delta$ 时，可以在固定失真条件下实现最小比特率。对应的失真 (误差) 为:

$d=\frac{N}{12} 2^{2 \bar{H}_d-2 \bar{R}}$

其中:

$\bar{H}_d$ 是平均微分熵。
$\bar{R}=R / N$ 是平均比特率。

分解基的选择

我们最终确定用于信号分解的最优基。这里假设被分解的信号是高斯信号。很容易证明，方差为 $\sigma^2$ 的正态分布变量的熵为:

$H_d=\log _2(\sigma \sqrt{2 \pi e})$

使用上一节中失真的表达式，可以得到:

$d=\frac{N \pi e}{6} \rho^2 2^{-2 \bar{R}}$

其中:

$\rho^2=\left(\prod_{n=1}^N \sigma_n^2\right)^{1 / N}$

$\rho^2$ 是每个系数方差的几何平均值。

定理

当信号按照协方差矩阵的特征向量（称为 Karhunen-Loève 基）进行分解时，$\rho^2$达到最小值。

我们将信号分解到一个正交基$\left(\phi_n\right)$上，有：$\sigma_n^2=\phi_n^T \Sigma \phi_n$，因此对上式取对数：

$\log _2 \rho^2=\frac{1}{N} \sum_{n=1}^N \log _2\left(\phi_n^T \Sigma \phi_n\right)$

在协方差矩阵特征向量基中分解：

$\phi_n^T \Sigma \phi_n=\sum_{m=1}^N\left|\left\langle\phi_n, \psi_m\right\rangle\right|^2 \psi_m^T \Sigma \psi_m$

根据$log_2$是一个凹函数，有：

$\log _2\left(\phi_n^T \Sigma \phi_n\right) \geq \sum_{m=1}^N\left|\left\langle\phi_n, \psi_m\right\rangle\right|^2 \log _2\left(\psi_m^T \Sigma \psi_m\right)$

又因为$\sum_{m=1}^N\left|\left\langle\phi_n, \psi_m\right\rangle\right|^2=1$，有：

$\sum_{n=1}^N \sum_{m=1}^N\left|\left\langle\phi_n, \psi_m\right\rangle\right|^2 \log _2\left(\psi_m^T \Sigma \psi_m\right)=\sum_{m=1}^N \log _2\left(\psi_m^T \Sigma \psi_m\right) \sum_{n=1}^N\left|\left\langle\phi_n, \psi_m\right\rangle\right|^2=\sum_{m=1}^N \log _2\left(\psi_m^T \Sigma \psi_m\right)$

因此有：

$\log _2 \rho^2 \geq \frac{1}{N} \sum_{m=1}^N \log _2\left(\psi_m^T \Sigma \psi_m\right)$

不同分布的熵

正态分布

对于正态分布 $X \sim \mathcal{N}(\mu, \sigma^2)$，概率密度函数为：

$p(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$

微分熵的计算公式为：

$H_d(X) = -\int_{-\infty}^{+\infty} p(x) \log_2 p(x) dx$

将 $p(x)$ 代入公式：

$H_d(X) = \int_{-\infty}^{+\infty} p(x) \left[\log_2\sqrt{2\pi\sigma^2} + \frac{(x-\mu)^2}{2\sigma^2}\log_2 e\right] dx$

最终结果为：

$H_d(X) = \frac{1}{2} \log_2(2\pi e \sigma^2)$

拉普拉斯分布

对于中心化的拉普拉斯分布 $X \sim \text{Laplace}(\mu, b)$，概率密度函数为：

$p(x) = \frac{1}{2b} \exp\left(-\frac{|x-\mu|}{b}\right)$

经过计算，其微分熵为：

$H_d(X) = \log_2(2b e)$

均匀分布

对于均匀分布 $X \sim \mathcal{U}(a, b)$，概率密度函数为：

$p(x) = \frac{1}{b-a}, \quad x \in [a, b]$

其微分熵为：

$H_d(X) = \log_2(b-a)$

等方差下的熵比较

各分布的方差为：

正态分布：$\sigma^2$
拉普拉斯分布：$2b^2 = \sigma^2 \implies b = \sqrt{\frac{\sigma^2}{2}}$
均匀分布：$\frac{(b-a)^2}{12} = \sigma^2 \implies b-a = 2\sqrt{3\sigma^2}$

代入后得到的熵为：

正态分布：$\frac{1}{2} \log_2(2\pi e \sigma^2)$
拉普拉斯分布：$\log_2\left(2\sqrt{\frac{\sigma^2}{2}} e\right)$
均匀分布：$\log_2\left(2\sqrt{3\sigma^2}\right)$

按熵值从大到小排序：

正态分布（$H_d \propto \log_2(\sigma)$）
均匀分布（$H_d \propto \log_2(\sigma)$，但小于正态分布）
拉普拉斯分布（$H_d \propto \log_2(\sigma)$，最小）

在方差相等的情况下，正态分布具有最大的微分熵，其次是均匀分布，最后是拉普拉斯分布。