三. 矢量量化(VectorQuantization)一.矢量量化初步基本原理设计码本(LBG)量化二•矢量量化进一步分裂矢量量化(SplittedVQ)多极矢量量化(CascadedVQ)树形矢量量化器其它各种类型矢量量化器几个矢量量化的工程实现问题[2]分级矢量量化中的多路径搜索问题用模拟退火(SimulatedAnnealing)算法训练最佳码本矢量量化的应用矢量量化初步基本原理结论：在信息论中已证明，矢量量化优于标量量化矢量量化是先将K个（K_2）个采样值形成K维空间Rk中的一个矢量，然后将这个矢量一次进行量化它可以大大降低数码率基础是信息论的分支：率失真（畸变）理论对于一定的量化速率R（以每个采样信号平均所用的量化比特数来衡量，bit/采样），量化失真D（以量化信号与原信号之间的误差均方值和原信号均方值之比来衡量）是一定的矢量量化总是优于标量量化的这是因为矢量量化有效地应用了矢量中各分量间的四种相互关联的性质：线性依赖性，非线性依赖性，概率密度函数的形状以及矢量维数定义：1）源：若将M*个信号采样组成的信源序列［中每K个为一组分为M个随机矢量，构成信源空间X=〈X1，X2,…，Xm?（X在K维欧氏空间RK中），其中第j个矢量可记为Xj=［洛，X2,,xj，j=1,2,,M。
K'n2）子空间：把R无遗漏地划分成N=2个互不相交的子空间R1,R2/,Rn，满足：「NUs=rk丿i士RiRj=0,i=j3）码本：在每个子空间Ri中找一个代表矢量Yi，令恢复矢量集为：丫^丫’，丫2,…，Yn二丫也叫输出空间、码本或码书（CodeBook），Yi称为码矢（CodeVector）或码字（CodeWord），丫内矢量的数目n,则叫做码本长度4）码本搜索：当矢量量化器输入任意矢量Xj■RK时，它首先判断Xj属于那个子空间，然后输出该子空间R的代表矢量丫「丫•丫RK,i=1,2,…N几矢量量化过程就是用Yj代表Xj,即Yi=QXj,1乞i乞N,1岂j乞M式中Q为量化函数5）完整系统：VQ编译码的全过程完成一个从K维欧氏空间RK到RK空间中有限子集的映射：Q:RK_：X>Y山飞,，丫n?发端完成映射C:X》I二讣2,,N匚收端完成映射D:I>Y，矢量量化Q则是C和D的结合图1中给出了这种映射关系编码X>I解码ItY图1矢量量化示意图6）矢量量化的比特率：log2NR二K:log2N：每个矢量所需要的编码比特数:K：每个矢量所包含的信号样点数:K=1时,VQ退化成SQ波形量化采样频率为10kHz、振幅量化为16bit的语音信号的传输速率是：16x10000=160,000bit/s（bps）。
•波形特征参数量化对阶数为10、每秒100个特征矢量（如频谱包络参数），如振幅量化也为16bit的话，其传输速率是：16x100x10=16,000bit/s波形特征参数矢量量化：设L=1024（40种语音单位，每个对应25种变形），即为了指定码本中任意码矢需要10bit，则对每秒100个特征矢量的传输需率就为1,000bit/s7）矢量量化的特点：压缩能力强一定产生失真，但失真易控制：X的分类越细，失真越小由于Xj和Yj都是K计算量大：每输入一个Xj,都要和N个Yj逐一比较，搜索出畸变最小的维矢量，故搜索的矢量运算，工作量大VQ是定长码设计码本1）目的：在VQ中，码本的生成是一个关键若设计K维N级码本，则要根据M—L失真最小的准则，分别决定如何对RK进行划分，以得到合适的N个胞腔（Cell）Ci,1乞i乞N；以及求出Ci,1乞i乞N的代表矢量Yi,1乞i乞N最佳量化就要满足使其平均失真dq最小，即DQ=mindX,YF2）原则：最佳多维量化器必须满足K分割条件：对R的分割应满足(Voronoi分割)R—XRK:d(X,YJ岂d(X,Yj):i=j?质心（Centroid）条件：当子空间分割X-巳固定时，Voronoi胞腔的质心就是量化器的码字,即Yj=E取XR1矢量徒是胞腔Ci的质心。
对于最佳胞腔的分割、最佳质心的计算与畸变的度量准则有关对于均方误差准则及加权均方误差准则，胞腔Ci的质心Y:1YPx2XCi表示胞腔Ci中元素的个数，即胞腔Ci中有Ci个X矢量量化由码本丫和划分Ri的条件唯一确定当码本确定后，分割就可以通过最近邻域准则（NNR-NearestNeighborRule）唯一确定最佳量化器q的设计也就是最佳码本Y的设计通常采用迭代类聚的方法3）训练码本的LBG算法Linde,Buzo和Gray将标量最优量化的M—L算法推广到了多维空间LBG算法图2、图3分别给出已知训练序列和已知信源分布特性的算法流程图a）初始化条件：给出-码本长度N-初始码本Yn,&（°）,丫（°】,…，丫（°1}计算停止门限；，01初始平均失真D'—'训练序列Ts—Xn；n=1,2,…,M?MJ（开［甘算停止门限巧覺.―・・■—・・•・・\f弊闔霜鬻翻％JYi.了疋少糾｝r「,■■-1彳卫伫否是（蟻束）图2已知训练序列的算法流程图b）用码本Ynn为已知质心，根据最佳划分原则把训练序列T胞腔，即='Xn；n=1,2,,M划分为N个nSjl=叹d（X,Yj）兰d（X,Yj其中i=j,Y「YjYn,XTs,j=1,2,N。
c）计算平均失真与相对失真rA1K其中dXr，YdXr,k，ym,kKkJ_-平均失真：巾=汰囲严,丫是K维输入矢量xr的量化畸变若6n乞；，则停止计算，当前码本即是设计好的码本Yn，否则进行d）生成新码字-计算这时划分的各胞腔的质心，可由下式计算FSi:集合Si中元素的个数-由这n个新质心匕（2）,丫（^2厂，丫（心门构成新的码本ynD-设置n=n+1-返回2）再进行计算，直到DC*）兰E，得到所要求的码本Yn=Y（n^N为止4）初始码本的生成LBG算法：总失真单调下降的算法要求：避免陷入局部最小点方法：a）随机选取法b）分裂法分裂原则扰乱系数距离最大原则c）综合法（合并法）5）失真测度1）基本定义：失真测度是反映用码字丫代替信源矢量x所付出的代价这种代价的统计平均值描述了矢量量化器的工作特性，即D=EdX,QX12）常用失真测度:平方失真测度:22dX,丫二X_YXi_Yii加权平方失真测度：d(X,Y)=(X-YJW(X-Y)W:正定加权矩阵绝对误差失真测度：dX,Y一丫八Xi-Yi与被量化矢量信号意义相关的失真测度:例如反映语音谱包络的预测(LP)矢量，定义频谱失真为,fl11rd[10log10log]d:1. 打‘°P@)曰(co)式中P(・.)是原始LP能量谱，F?(「)是量化后的LP能量谱似然比失真测度板仓-斋田失真测度矢量量化的量化过程全搜索码本中有N个码字，每个码字为K维矢量,完成一次搜索的计算代价:(欧氏距离)加法：N(2K-1)次乘法:NK次比较:N-1次树形搜索的矢量量化系统图4-5二叉鞫捜索方法二叉树或多叉树优点：降低运算量缺点：增加存储量衰4订三更鞫擡哄与全銀*方玉的性糜比较1「1U.比较唾算・r1'1151i*-—L；.|r『’i最桂栓度「胡L—Hi,全体:二3}a2(/-1)(-14)F_—-———”…仝，UN:水喪中J为科本尺寸。
矢量量化进一步分裂矢量量化（SplittedVQ）!=树搜索矢量量化器分裂矢量量化：首先将一个K维矢量分裂成P（P>1）个子矢量，然后对各个子矢量分别独立进行矢量化对于一个实用的vq系统，例如用20个比特对10个LSF进行量化如果用全搜索方案，码本容量将达到220*10（LSF矢量为10维），无论是从码本的存储容量还是搜索的运算量，在现有的硬件条件下难以实时实现如果采用分裂矢量量化算法，将10维的LSF矢量分裂为两个5维的矢量，分别用10比特进行VQ，这样，码本容量降为2*210*5由此可见分裂矢量量化可以大大降低了码本的存储量和最佳矢量搜索的计算量多极矢量量化（CascadedVQ）1）多级矢量量化器的构造多级矢量量化器可以较大幅度的降低矢量量化器的计算复杂度和存贮量多级矢量量化器由码本大小分别为N,N2，…,Nm,的m个小码本构成图4所示的是m级矢量量化器的编码器原理图图4多级矢量量化器的编码器m级矢量量化器的量化原理：第一级矢量量化器是量化原始输入矢量X，在码本1中找到失真最小的码字Yi，并将其下标i编码送到信道中第二级量化器的输入矢量是：原始输入矢量X与第一级输出矢量Y之差的误差矢量e^X-Y。
e,在码本2中找到失真最小的码字Ej1，并将其下标jl编码送到信道中第三级量化器的输入矢量是：第二级的输入矢量ei与第二级的输出矢量Ej1之差的误差矢量e2=e,-Ej,同样e2在码本3中找到失真最小的码字Ej2，并将其下标j2编码送到信道中依此类推，第m级量化器的输入矢量e(m/)与第(m-1)级的输出矢量Ej(m^｝之差的误差矢量e(m」)=e(m<)-Ej(m』)e(mJ)在码本m中找到失真最小的码字Ej(^1)，并将其下标j(m-1)的编码信号送到信道中这样，信道中传输的将是i,j1,j2,…,jm等下标的编码信号m这m个小码本，等价于一个码本尺寸为N二…Ni的全搜索矢量量化器的码本，并称此全搜索矢i=1量量化器为与此m级矢量量化器相当的量化器2) 多级矢量量化器码本的设计多级矢量量化器各级码本设计仍可采用LBG算法，只是训练序列有所不同下面给出一个m级矢量量化器的码本设计算法a)第一级码本设计设第一级码本大小为N1，训练序列TS的长度为M(即有M个训练矢量)采用LBG算法进行计算，得到第一级码本Yj(i=1,2,…，N1)b)第二及多级码本设计第二级码本仍按LBG算法进行设计。
不过它的训练序列是第一级矢量量化器的误差信号e1长度仍为M同样用LBG算法进行类聚、递归，得到第二级码本的N2个码字Eji(j=1,2,...,N2)余者类推例如设计一个LSF参数的三级矢量量化器：在实际算法中，采用16万帧以上的训练序列TS进行训练，三级矢量量化，分别是7比特，7比特和6比特同样用20比特对LSF矢量进行编码，码本容量降为(27+27+26)*10,相对于分裂矢量量化，存储量降低了60%，相应的搜索计算量也大大减少而合成语音质量与相同比特的分裂矢量量化基本相当多级矢量量化系统无论在减少搜索计算量方面，还是减少码本储存量方面都有可观的改进2. 模糊矢量量化减少码本的量化误差模糊聚类(FuzzyClustering)模糊k均值聚类，隶属度函数其它各种类型矢量量化器全搜索矢量量化器sparsity)o节约计算量(稀疏码本o节约存储量固定预测矢量量化器乘积码矢量量化器o增益/o均值/自适应矢量量化器自适应预测矢量量化器几个矢量量化的工程实现问题分级矢量量化中的多路径搜索问题在分级矢量量化中，每一级量化过程都是在所定义的最小误差意义下最优的但多级量化作为一个整体并不一定是最优的。
然而要用全路径搜索的方法找出全局最优，运算量巨大现阶段的硬件无法满足实时运算的要求所以工程上采用搜索路径数为M的部分路径搜索分级矢量量化例如：1) 在第一级搜索中找到误差测度最小的M个码字，并保留对应的M个误差矢量2) 在第二级搜索中分别以这M个误差矢量为输入矢量，分别进行码本搜索。