[数据结构与算法] Uniform Quantizing for Minimum Distortion

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Uniform Quantizing for Minimum Distortion -> 正文阅读

[数据结构与算法]Uniform Quantizing for Minimum Distortion

该文讨论了当量化器的输出电平数固定时，量化器对信号失真最小化的问题。失真被建模为量化器的输入和输出之间的误差函数的期望值。推导了失真最小的量化器参数的方程。我们着重讨论一下均匀分布的情况。

1. 量化背景

在许多数据传输系统中，模拟输入信号首先在发射机上转换为数字形式，然后以数字形式传输，最后在接收机上重构为模拟信号。所产生的输出通常与输入信号相似，但并不完全相同，因为发射机上的量化器对位于有限数量的振幅范围内的所有输入振幅产生相同的数字。假设数字传输无误差，输入信号和输出信号之间的差值是量化误差。由于任何系统的数字传输速率都是有限的，因此必须使用一个量化器来将输入分类为有限数量N的范围。

2. 数学表达

在这里插入图片描述
对于给定的输出区间数量N， $x_k$ 表示为各个区间的边界值， $y_k$ 表示为重建值：
$C_i=\{x\in R:Q(x)=x_i\}$
$\bigcup \limits_{i=0}^{N-1}C_i=R \ with \bigvee_i \neq j:C_i\bigcap C_j=\emptyset$
下图中边界值用的 $u_i$ ，重建值用的 $S_i^{'}$ 。
在这里插入图片描述

3. Minimum Distortion

通常为量化过程定义一个失真度量是合适的，这将是量化误差的一些统计量。 $f (x)$ 为损失定义函数。
$\begin{aligned} D&=E[f(s_{in}-s_{out})] \\ &=\sum \limits_{i=1}^{N} \int_{x_i}^{x_{i+1}}f(x-y_i)p(x)dx \end{aligned}$
对于定义域无限的x来说， $x_{N+1}$ 和 $x_{1}=-\infty$ 。
如果我们希望使固定N的D最小化，我们通过将D分别对于 $x_i$ 和 $y_i$ 求偏导，并将导数设为零来得到必要条件:
$\begin{aligned}\frac{\partial D}{\partial x_i}=f(x_i -y_{i-1})p(x)-f(x_i-y_i)p(x_i)=0 \\i=2,...,N\ \ \ \ \ \ \ (1) \end{aligned}$

$\begin{aligned}\frac{\partial D}{\partial y_i} = -\int_{x_i}^{x_{i+1}} f^{'}(x-y_i)\ p(x)\ dx=0 \\i=1,...,N\ \ \ \ \ \ \ (2)\end{aligned}$

$\begin{aligned}(1)becomes (for\ p(x_i) \neq 0) \\& f(x_i -y_{i-1})=f(x_i-y_i)& &i=2,...,N\ \ \ \ \ \ \ (3) \end{aligned}$
$\begin{aligned}(2)becomes \\ &&&&&&\int_{x_i}^{x_{i+1}} f^{'}(x-y_i)\ p(x)\ dx=0& &i=2,...,N\ \ \ \ \ \ \ (4) \end{aligned}$

在一般情况下最好的解是，如果所有的二阶偏导数的D对 $x_i$ 和 $y_i$ 的存在，那么临界点由条件（3）和（4）是一个最小如果矩阵第 $i$ 行和 $j$ 列元素满足正定：
$\frac{\partial^{2}D}{\partial p_i \partial p_j}|_{critical \ point}$

通常的情况下，我们采取 $f(x)=x^2$ 。
$(3) ? > (j = 2, . . ., N)$
$x_i=(y_i+y_{i+1})/2\ or y_i=2x_i-y_{i-1}$
$(4) ? > (i = 1, . . ., N)$
$\int_{x_i}^{x_{i+1}}(x-y_i)p(x)dx=0$

$y_i$ 是在 $x_i, x_{i+1}$ 之间的质心。

3.1 例子

针对信源分布为 $\sqrt{2}e^{-x^2/2}$ ，其中 $x_{N/2+1}=0 for\ N\ even\ or\ y_{(N+1)/2}=0\ for\ N\ odd$ ，这样会有一个对称的结果。具体为：
在这里插入图片描述
图中是失真与输出水平数的对数-对数图1。

当N很大时，振幅概率密度从单个输入范围的一端到另一端没有明显的变化，除了非常大的振幅，这是非常不可能的，因此它们的影响很小。因此，大多数输出级别都非常接近于对应输入范围的端点的平均值。现在，量化均匀分布的输入信号的最佳方法是均匀地划分输出电平，并将输入范围的端点位于输出电平之间，如图2
在这里插入图片描述
为这个分布产生具有2N输出水平的量化器的最佳方法是将原来的区间分成两半，并将新的输出水平放在这些范围的中点，如图所3

4. Uniform Quantization PCM

商用高速模数转换设备目前仅限于将等量的输入范围转换为介于输入范围两端之间的输出。在许多应用程序中，人们希望知道要使用的最佳间隔长度，即，对于给定数量的输出级别N，产生最小失真的间隔长度。这是一个比第一个问题更容易的问题，因为它只是二维的(对于 $N\ge 2$ )，也就是说，D是间隔的长度r和任何特定输出 $y_k$ 的函数。如果输入具有对称分布，并且需要对称答案，则问题就变成一维问题；此时，我们的重建值为各个区间的中间值。如果p(x)是输入振幅概率密度，f(x)是函数，使得失真D是 $E[f(s_{out}-s_{in})]$ ，那么，对于偶数为2N的输出：
$\begin{aligned} D=2\sum \limits_{i=1}^{N-1}\int_{(i-1)r}^{ir}f(x-[\frac{2i-1}{2}])p(x)dx+2\int_{(N-1)r}^{\infty}f(x-[\frac{2N-1}{2}])p(x)dx \end{aligned}$
我们对r求偏导：
$\begin{aligned} \frac{dD}{dr}=- \sum \limits_{i=1}^{N-1}(2i-1)\int_{(i-1)r}^{ir}f^{'}(x-[\frac{2i-1}{2}])p(x)dx-(2N-1)\int_{(N-1)r}^{\infty}f^{'}(x-[\frac{2N-1}{2}])p(x)dx=0 \end{aligned}$
对于奇数的情况也存在类似的表达式。在这两种情况下，当指定了f(x)、p(x)和N时，这个问题都很容易受到机器计算的影响。
针对信源分布为 $\sqrt{2}e^{-x^2/2}$ ，其中 $x_{N/2+1}=0 for\ N\ even\ or\ y_{(N+1)/2}=0\ for\ N\ odd$ ，N=2 to 36。
在这里插入图片描述
图中显示了等间距的输出水平间距与输出数的对数-对数图4：

最后，在图中可以看到最佳量化器的Distortion比率与最佳等距电平量化器的比值图5

5. 均匀量化与非均匀量化

在这里插入图片描述

5.1 Computation of the Compressor Function

我们根据C()的斜率得到：
$\frac{dx(s)}{ds}|_{s=s_i^{'}}\approx \frac{\Delta}{\Delta_i}$
每区间MSE贡献相等的条件为：(考虑的是用FLC进行标量量化器的高码率近似)
$\sqrt[3]{f(s_i^{'})} \Delta_i \approx \frac{1}{K}\int_{-\infty}^{\infty}\sqrt[3]{f(s_i)}ds$
结合上述两个式子：
$\frac{dx(s)}{ds}|_{s=s_i^{'}}\approx \frac{\Delta}{\Delta_i}=\frac{\Delta \sqrt[3]{f(s_i^{'})}}{\Delta_i \sqrt[3]{f(s_i^{'})}}=\Delta \cdot K\frac{\sqrt[3]{f(s_i^{'})}}{\int_{-\infty}^{\infty}\sqrt[3]{f(x)}dx}$

Compressor function is obtained by integrating over its slope:
$c(s)=\frac{K \Delta}{\int_{-\infty}^{\infty}\sqrt[3]{f(x)}} \cdot \int_{-\infty}^{s}\sqrt[3]{f(x)}dx-\frac{K \Delta}{2}$
在这里插入图片描述