矢量量化技术课件.pptx

1、 第七章 矢量量化技术 (vector quantization VQ)(vector quantization VQ)7.1 概述 7.2 矢量量化的基本原理7.3 矢量量化的失真测度7.4 矢量量化的最佳码本设计7.1 概述一、矢量量化的应用二、标量量化和矢量量化的区别 矢量量化技术技术是一种数据压缩和编码技术，矢量量化技术技术是一种数据压缩和编码技术，矢量量化压缩技术的应用领域非常广阔，如军事部门矢量量化压缩技术的应用领域非常广阔，如军事部门和气象部门的卫星和气象部门的卫星( (或航天飞机或航天飞机) )遥感照片的压缩编码遥感照片的压缩编码和实时传输、雷达图像和军用地图的存储与传输、数和

2、实时传输、雷达图像和军用地图的存储与传输、数字电视和字电视和DVDDVD的视频压缩、医学图像的压缩与存储、的视频压缩、医学图像的压缩与存储、网络化测试数据的压缩和传输、语音编码、图像识别网络化测试数据的压缩和传输、语音编码、图像识别和语音识别等等和语音识别等等 。一、矢量量化的应用 整个动态范围被分成若干个小区间，每个小区间整个动态范围被分成若干个小区间，每个小区间有一个代表值，量化时落入小区间的信号值就用这个有一个代表值，量化时落入小区间的信号值就用这个代表值代替，或者叫被量化为这个代表值。这时的信代表值代替，或者叫被量化为这个代表值。这时的信号量是一维的，所以称为标量量化。号量是一维的，所

3、以称为标量量化。二、标量量化和矢量量化的区别采样采样量化量化x xa a(t)(t)x xa a(nT)(nT)x(n)x(n)x xa1a1x x1 1x xk kx xakakx xak+1ak+1x xk+1k+1x xL Lx xaLaLx xaL+1aL+1x(n)=Qxx(n)=Qxa a(nT)(nT)。 1.标量量化：2 2 - - -2-2 2 2 标量量化标量量化1-dimensional VQ is shown below: 2. 矢量量化： 若干个标量数据组成一个矢量，若干个标量数据组成一个矢量，矢量量化是矢量量化是对矢量进行量化，和标量量化一样，它把矢量空间对矢量进行

4、量化，和标量量化一样，它把矢量空间分成若干个小区域，每个小区域寻找一个代表矢量，分成若干个小区域，每个小区域寻找一个代表矢量，量化时落入小区域的矢量就用这个代表矢量代替，量化时落入小区域的矢量就用这个代表矢量代替，或者叫着被量化为这个代表矢量。例如，所有可能或者叫着被量化为这个代表矢量。例如，所有可能的二维矢量就构成了一个平面，将平面分成的二维矢量就构成了一个平面，将平面分成7 7个小个小区域。区域。Y Y1 1Y Y2 2Y Y3 3Y Y4 4Y Y5 5Y Y6 6Y Y7 7x1x2Y Yi i（x x1i 1i ,x,x2i2i） 假设声道滤波器传输函数用假设声道滤波器传输函数用4

5、4个系数来描述，个系数来描述，而且，又假设声道只能为而且，又假设声道只能为4 4个可能的形状之一。这个可能的形状之一。这意味着只存在意味着只存在4 4组可能的声道滤波器传输函数。组可能的声道滤波器传输函数。 现在考虑对每一个滤波器系数单独进行标量量现在考虑对每一个滤波器系数单独进行标量量化，需要化，需要2bit2bit，每一分析帧需要，每一分析帧需要8 8个比特来进行编个比特来进行编码。码。3、举例说明标量量化与矢量量化的区别、举例说明标量量化与矢量量化的区别 如果我们知道只有如果我们知道只有4 4种可能的声道形状，与种可能的声道形状，与4 4个可能的声道滤波器系数组成的矢量相对应，个可能的声

6、道滤波器系数组成的矢量相对应，若某一个滤波器系数知道了，其它系数就知道若某一个滤波器系数知道了，其它系数就知道了，也就是矢量中的标量值之间是高度相关的，了，也就是矢量中的标量值之间是高度相关的，在这种情况下，一个分析帧，只需要一个在这种情况下，一个分析帧，只需要一个2bits2bits对对4 4个滤波器系数进行编码，这样降低了个滤波器系数进行编码，这样降低了所需的比特数。矢量量化就是利用数据之间的所需的比特数。矢量量化就是利用数据之间的相关性来降低所需的比特率。相关性来降低所需的比特率。4.2 矢量量化的基本原理一、矢量量化的基本原理二、矢量量化在语音通信中的应用三、矢量量化在语音识别中的应用

7、四、矢量量化的关键之处1.1.基础知识一、矢量量化的基本原理 若干个标量数据组成一个矢量，标量的个数就为若干个标量数据组成一个矢量，标量的个数就为矢量的维数。如语音信号某一帧中提取的声道参数，矢量的维数。如语音信号某一帧中提取的声道参数，共共P P个个,X,Xi i=a=ai1i1,a,ai2i2, ,a,aiPiP 。则。则X Xi i是一个是一个P P维矢量。设维矢量。设共有共有N N个个P P维矢量维矢量X=XX=X1 1,X,X2 2, ,X,XN N,其中第其中第i i个矢量为个矢量为X Xi i，i=1,2,i=1,2,N N。类比过来，。类比过来，N N个语音帧，每帧中共有个语音

8、帧，每帧中共有P P个个声道参数，共组成声道参数，共组成N N个个P P维矢量。维矢量。a a1111,a,a1212, ,a,a1K1Ka aN1N1,a,aN2N2, ,a,aNKNK第第1 1帧帧第第N N帧帧X X1 1=a=a1111,a,a1212, ,a,a1P1PX X2 2=a=a2121,a,a2222, ,.,a.,a2P2PX XN N=a=aN1N1,a,aN2N2, ,.,a.,aNPNPN个矢量，每个矢量的维数为个矢量，每个矢量的维数为P第一帧第一帧第二帧第二帧第第N帧帧 将一个将一个P维随机矢量映射成另一个离散取值的实维随机矢量映射成另一个离散取值的实P维矢量的

9、过程。维矢量的过程。()q XY 所有所有P P维矢量构成了一个空间为维矢量构成了一个空间为R RP P，无遗漏地划，无遗漏地划分成分成J J个互不相交的子空间个互不相交的子空间R R1 1,R,R2 2R RJ J , ,将将R Rj j称为胞腔。称为胞腔。在每一个子空间在每一个子空间R Rj j找一代表矢量找一代表矢量Y Yj j，则，则J J个代表矢量个代表矢量可以组成矢量集为：可以组成矢量集为： Y=YY=Y1 1,Y,Y2 2, ,Y,YJ J 构成了一个矢量量化器，构成了一个矢量量化器，Y Y叫着叫着码本，码本，J J称为码本长度称为码本长度, Y, Yj j称为码字，有：称为码字

10、，有：Y Yj j=y=yj1j1,y,yj2j2, ,y,yjPjP ，j=1,2,j=1,2,J J。2.2.矢量空间的划分举例 以以P=2P=2为例来说明。当为例来说明。当P=2P=2时，所得到的是二维时，所得到的是二维矢量。所有可能的二维矢量就构成了一个平面。第矢量。所有可能的二维矢量就构成了一个平面。第i i个二维矢量记为：个二维矢量记为： X Xi i=x=xi1i1,x,xi2i2 。先把这个平面。先把这个平面划分成划分成J J块互不相交的子区域，从每个子区域中找块互不相交的子区域，从每个子区域中找出一个代表矢量。如出一个代表矢量。如J=7J=7。Y Y1 1Y Y2 2Y Y3

11、 3Y Y4 4Y Y5 5Y Y6 6Y Y7 7x1x2码本码本 Y=YY=Y1 1,Y,Y2 2, ,Y,YJ J 码本长度码本长度 J=7J=7码字码字 Y Yj j=x=xj1j1,x,xj2j2 ，j=1,2,j=1,2,J J 维数为维数为P P，码本长度为，码本长度为J J的矢量量化器的矢量量化器Q Q定义：定义：为从为从P P维欧几里德空间维欧几里德空间R RP P到一包含到一包含J J个输出个输出( (重构重构) )点的有限集合点的有限集合C C的映射，的映射， Q Q：R RP PCC，其中，其中C=yC=y1 1 ,y ,y2 2 , , ,y ,yJ J y yi i

12、 R RP P，i i1,1,J,J 集合集合C C称作称作码本或码书码本或码书，码本长度码本长度为为J J 。 码本的码本的J J个元素称作个元素称作码字码字或码矢量，它们均或码矢量，它们均为为R RP P中的矢量，中的矢量，P P维矢量。维矢量。 矢量量化器定义：矢量量化器定义：An example of a 2-dimensional VQ is shown below: 当给矢量量化器输入一个任意矢量当给矢量量化器输入一个任意矢量X Xi i进行矢量进行矢量量化时，矢量量化器首先判断它属于那个子空间，量化时，矢量量化器首先判断它属于那个子空间，然后输出该子空间的代表矢量然后输出该子空间

13、的代表矢量Y Yj j。矢量量化过程就。矢量量化过程就是用是用Y Yj j代替代替X Xi i的过程。的过程。 Y Yj jQ(XQ(Xi i) 1) 1 j j J 1J 1 i i N N3.3.矢量量化的过程矢量矢量量化器量化器X Xi iY Yj j 当给矢量量化器输入一个任意矢量当给矢量量化器输入一个任意矢量X Xi i进行矢进行矢量量化时，矢量量化器首先判断它属于那个子空量量化时，矢量量化器首先判断它属于那个子空间，如何判断就是要依据一定的规则，选择一个间，如何判断就是要依据一定的规则，选择一个合适的失真测度，分别计算每个码字代替合适的失真测度，分别计算每个码字代替X Xi i所带

14、所带来的失真，当确定产生最小失真的那个码字来的失真，当确定产生最小失真的那个码字Y Yj j时，时，就将就将X Xi i量化成量化成Y Yj j， Y Yj j就是就是X Xi i的重构矢量（和恢复的重构矢量（和恢复矢量）。矢量）。4.判断规则X Xi i=a=ai1i1,a,ai2i2, ,a,aiPiP Y Y2 2Y Y1 1= y y1111,y,y1212, ,y,y1P1P Y Y2 2= y y2121,y,y2222, ,y,y2P2P Y YJ J= y yJ1J1,y,yJ2J2, ,y,yJPJP 矢量量化器矢量量化器（码本）（码本）最小失真最小失真计算失真计算失真x4矢

15、量量化矢量量化3 3231322 21343411 134 码书码书码字码字c0码字码字c1码字码字c2码字码字c3索引索引0d(x,c0)=5d(x,c1)=11d(x,c2)=8d(x,c3)=8argmind(x,cj)x412)(),(iiicxCXd图像编码例子：图像编码例子：原图象块（原图象块（4灰度级，矢量维数灰度级，矢量维数 k=44=16） x 0 1 2 3码书码书C y0, y1 , y2, y3 y0 y1 y2 y3码字码字y1最接近输入矢量图象块最接近输入矢量图象块 x，故用索引，故用索引“01”编编码码d(x,y0)=25d(x,y1)=5d(x,y2)=25d(

16、x,y3)=46标量量化是维数为标量量化是维数为1的矢量量化。一般矢量量化均指的矢量量化。一般矢量量化均指大于大于1的多维量化。的多维量化。一个一个P维最佳矢量量化器的性能总是优于维最佳矢量量化器的性能总是优于P个最佳标量个最佳标量量化器。量化器。在相同的编码速率下，矢量量化的失真明显比标量量在相同的编码速率下，矢量量化的失真明显比标量量化的失真小；而在相同的失真条件下，矢量量化所需化的失真小；而在相同的失真条件下，矢量量化所需的码速率比标量量化所需的码速率低得多。的码速率比标量量化所需的码速率低得多。由于矢量量化的复杂度随矢量维数成指数形式增加，由于矢量量化的复杂度随矢量维数成指数形式增加，

17、故矢量量化的复杂度比标量量化的复杂度高故矢量量化的复杂度比标量量化的复杂度高。 标量量化和矢量量化比较标量量化和矢量量化比较二、矢量量化在语音通信中的应用 通信系统中有通信系统中有两个完全相同的码本两个完全相同的码本，一个在，一个在编码编码器（发送端），器（发送端），另一个在另一个在解码器（接收端）解码器（接收端）。每个码。每个码本包含本包含J J个码字个码字Y Yj j, ,每个码字是一个每个码字是一个P P维矢量。维矢量。VQVQ编码器编码器的运行原理是根据输入矢量的运行原理是根据输入矢量X Xi i从编码器码本中选择一从编码器码本中选择一个与之失真误差最小的码字个与之失真误差最小的码字Y

18、 Yj j ，其输出的，其输出的V V就是该码就是该码字的下标，字的下标，V V是一个数字，因而可以通过任何数字信是一个数字，因而可以通过任何数字信道传输或任何数字存储器来存储。如在编码速率为道传输或任何数字存储器来存储。如在编码速率为2.4kbit/s2.4kbit/s的的LPCLPC声码器中，将每帧的声码器中，将每帧的1010个预测系数加个预测系数加以以1010维的矢量量化，编码速率降低到维的矢量量化，编码速率降低到800bit/s800bit/s，而语，而语音质量没有下降。音质量没有下降。特征特征矢量矢量形成形成语音语音信号信号帧帧Xi码本码本Y1Y2YJVQ编码编码器器传输传输或或存储

19、存储VVQ译码译码器器VYj码本码本Y1Y2YJ矢量量化在语音通信中的应用矢量量化在语音通信中的应用信信源源用用LBG(GLA)算算法生成法生成最近邻最近邻搜索搜索信信宿宿查表查表信道信道索引索引索引索引码书码书码书码书输入输入矢量矢量输出输出矢量矢量编码编码器器解码解码器器矢量量化编码与解码结构图：矢量量化编码与解码结构图：XX1 1 , X, X2 2 , , , X , XN N 模板库模板库语语码本码本YY1 1 ,Y,Y2 2 , ,Y,YJ J 学学码本码本音音码本码本文文码本码本wenwen22 , 4, , 4, , 1 , 1N个特征矢量个特征矢量三、矢量量化在语音识别中的应

20、用 先对系统中的每个字，做一个码本作为该字先对系统中的每个字，做一个码本作为该字的参考（标准）模板的参考（标准）模板, ,共有共有M M个字，故共有个字，故共有M M个码个码本，组成一个模板库。本，组成一个模板库。 识别时，对于任意输入的语音识别时，对于任意输入的语音特征矢量序列特征矢量序列X XXX1 1 , X, X2 2 , , , X , XN N ，计算该序列中每一个特，计算该序列中每一个特征矢量对模板库中的每个码本的总平均失真量误征矢量对模板库中的每个码本的总平均失真量误差，找出最小的失真误差对应的码本（代表一个差，找出最小的失真误差对应的码本（代表一个字），将对应的字输出作为识别

21、的结果。字），将对应的字输出作为识别的结果。特征矢量序列特征矢量序列 X XXX1 1 , X, X2 2 , , , X , XN N 模板库模板库 Y Y1 1 , Y, Y2 2 , , , Y , YM M特征矢量特征矢量序列形成序列形成任意任意语音语音X X码本码本Y Y1 1Y Y2 2Y YM M计算计算失真误差失真误差判决判决输出结果输出结果Y Yi i 每一个字做一每一个字做一个码本，共个码本，共M M个字个字模板库模板库XX1 1 , X, X2 2 , , , X , XN N 模板库模板库语语码本码本YY1 1 ,Y,Y2 2 , ,Y,YN N 学学码本码本音音码本码

22、本文文码本码本wenwen四、矢量量化的关键之处 1. 1. 首先设计首先设计一个一个好好码本。关键在于如何划分码本。关键在于如何划分J J个区域边界。这需要大量的输入信号矢量，经个区域边界。这需要大量的输入信号矢量，经过统计实验才能确定，这个过程称为过统计实验才能确定，这个过程称为“训练训练”或或“学习学习”。 应用聚类算法，按照一定的应用聚类算法，按照一定的失真度准则失真度准则（失真测度），对训练的数据进行，对训练的数据进行分类分类，从而把训，从而把训练数据在多维空间中划分成一个以码字为中心的练数据在多维空间中划分成一个以码字为中心的胞腔，常用的是胞腔，常用的是LBGLBG算法来实现。算法

23、来实现。 2. 2. 未知矢量的量化。按照选定的未知矢量的量化。按照选定的失真度准则失真度准则（失真测度），把未知矢量，量化为失真度最，把未知矢量，量化为失真度最小的码字。小的码字。 失真测度就是两矢量之间的失真测度就是两矢量之间的距离距离。7.3 矢量量化的失真测度一、失真测度的定义二、欧氏距离测度三、线性预测失真测度四、识别失真测度一、失真测度的定义 失真测度（距离测度）就是将输入矢量失真测度（距离测度）就是将输入矢量X Xi i用码用码本重构矢量本重构矢量Y Yj j来表征时所产生的来表征时所产生的误差或失真的度量误差或失真的度量方法方法，它可以描述两个或多个模型矢量之间的相，它可以描述

24、两个或多个模型矢量之间的相似程度。常用的失真测度为欧氏距离测度、加权似程度。常用的失真测度为欧氏距离测度、加权欧氏距离测度和识别失真测度。欧氏距离测度和识别失真测度。 K K维语音特征矢量维语音特征矢量X X和码本和码本Y Y的失真测度的失真测度d(X,Y)d(X,Y)需需满足满足下列条件下列条件：（1 1）对称性）对称性 d(X,Y)d(X,Y)d(Y,X) d(Y,X) （2 2）正值性）正值性 d(X,Y)0,d(X,X)=0 d(X,Y)0,d(X,X)=0 （3 3）d(X,Y)=d(X,Z)+d(Z,Y)d(X,Y)=d(X,Z)+d(Z,Y)（4 4）对）对d(X,Y)d(X,Y

25、)有高效率的计算方法有高效率的计算方法二、欧氏距离测度K K维特征矢量：维特征矢量： X Xi ixxi1 i1 , x, xi2 i2 , , , x , xiKiK Y Yj jyyj1 j1 , y, yj2 j2 , , , y , yjKjK KiiiyxKYXd122)(1),(1.1.均方误差欧氏距离均方误差欧氏距离KiiiyxKYXd11|1),(2.2.绝对值平均误差绝对值平均误差3.3.加权欧氏距离测度加权欧氏距离测度KiiiyxiwKYXd12)(1),(三、线性预测失真测度 当语音信号特征矢量使用线性预测方法求出当语音信号特征矢量使用线性预测方法求出的的LPCLPC系数

26、时，系数时，不宜直接用欧氏距离。不宜直接用欧氏距离。应该直接应该直接用预测系数所描述的信号模型的用预测系数所描述的信号模型的功率谱功率谱来进行来进行比较。通过推导，采用对数似然比失真测度和比较。通过推导，采用对数似然比失真测度和模型失真测度。模型失真测度。RaaaRaYXdTTLLR)(ln),(1.1.对数似然比失真测度对数似然比失真测度R R是输入语音信号的是输入语音信号的(p(p1)1)（p+1p+1）自相关矩）自相关矩阵阵,., 121pTaaaa输入语音信号的预输入语音信号的预测系数矢量测系数矢量,., 1)(21pTaaaa码字预测系数矢量码字预测系数矢量)0()2()()2()0

27、() 1 ()() 1 ()0(nnnnnnnnnRpRpRpRRRpRRRR1)(),(RaaaRaYXdTTM2. 2. 模型失真测度模型失真测度R R是输入语音信号的是输入语音信号的(p+1)(p+1)（p+1p+1）自相关矩阵）自相关矩阵,., 121pTaaaa输入语音信号的预输入语音信号的预测系数矢量测系数矢量,., 1)(21pTaaaa码字预测系数矢量码字预测系数矢量7.4 矢量量化的最佳码本设计一、最佳码本设计的原则二、LBG算法三、码字搜索码本设计码本设计码字搜索码字搜索码字索引分配码字索引分配.x训练集合训练集合XM 训练矢量训练矢量.码本码本Cy1y2yNN 个码字个码

28、字.xd(x,y1)d(x,y0)d(x, yN-1)min d(x,yj)码本码本Cy0y1yN-1 所谓最佳设计，就是从大量信号样本中训所谓最佳设计，就是从大量信号样本中训练出好的码本；从实际效果出发寻找到好的失练出好的码本；从实际效果出发寻找到好的失真测度定义公式；用最少的搜索和计算失真的真测度定义公式；用最少的搜索和计算失真的运算量。运算量。一、最佳码本设计的原则 最佳码本的设计，就是在一定条件下，使得最佳码本的设计，就是在一定条件下，使得d(X,Y)d(X,Y)的统计平均最小。需满足下列条件：的统计平均最小。需满足下列条件： （1 1）最邻）最邻近近准则；根据该条件对信号空间进行最佳

29、准则；根据该条件对信号空间进行最佳划分，得到划分，得到S Sl l称为一个胞腔。称为一个胞腔。（2 2）所有选择码字）所有选择码字Y Yl l的输入矢量的输入矢量X X的集合为的集合为S Sl l， Y Yl l是是S Sl l中所有矢量的质心。根据这两条原则，这个算中所有矢量的质心。根据这两条原则，这个算法就是法就是LBGLBG算法。算法。lSXllXNY1N Nl l为集合中矢量的个数为集合中矢量的个数JiliYXdYXdRXSilKl, 1,);,(),(:xxxxxxxxxxxiSKS),(),(:ikKkYXdYXdRXSkYiYkSXkkXNY1iSXiiXNY1质心的形成质心的形

30、成X1( 220, 400, 430, 390, 300 )X1( 220, 400, 430, 390, 300 )X2( 220, 400, 410, 380, 310 )X2( 220, 400, 410, 380, 310 )X3( 220, 450, 410, 390, 300 )X3( 220, 450, 410, 390, 300 )X4( 220, 450, 420, 370, 290 )X4( 220, 450, 420, 370, 290 ) 所有选择码字所有选择码字Y Y的输入矢量的输入矢量X X的集合为的集合为S S， Y Y是是S S中所有矢量的质心。中所有矢量的质心

31、。300,5.382,425,220XXXX41XXXX41143214321SXXNY LBG LBG算法是一种递推算法，从一个事先选定的算法是一种递推算法，从一个事先选定的初始码本开始迭代。把训练序列按照码本中的元素初始码本开始迭代。把训练序列按照码本中的元素根据最邻近准则分组，对每一分组找质心，得到新根据最邻近准则分组，对每一分组找质心，得到新的码本，又作为初始码本，再进行分组，重复上述的码本，又作为初始码本，再进行分组，重复上述过程，直到系统性能满足要求和不再有明显的改进过程，直到系统性能满足要求和不再有明显的改进为止。为止。二、LBG算法（1 1）初始码本的选择）初始码本的选择 随机

32、选取法：从训练序列中随机选取随机选取法：从训练序列中随机选取J J个矢个矢量作为初始码字，从而构成初始码本。量作为初始码字，从而构成初始码本。.x.训练集合训练集合X . .初始码本初始码本J=2J=2个码字个码字（1 1）求出）求出S S中全体训练序列的质心中全体训练序列的质心（2 2）然后在）然后在S S中找一个与此质心的失真测度最大的中找一个与此质心的失真测度最大的矢量矢量 ，再在再在S S中找一个与中找一个与 的失真测度最大的矢量的失真测度最大的矢量（3 3）以）以 和和 为基准，根据最邻近准则，进行为基准，根据最邻近准则，进行S S的划分，得到两个子集的划分，得到两个子集 和和 ，求

33、其质心；，求其质心；（4 4）对这两个子集分别按同样方法进行处理，可以）对这两个子集分别按同样方法进行处理，可以得到四个子集。依次类推，经过得到四个子集。依次类推，经过r r次分裂，得到次分裂，得到J=2J=2r r 个子集，分别求子集的质心，得到个子集，分别求子集的质心，得到J J个初始码字，构个初始码字，构成初始码本。成初始码本。分裂法分裂法01YiiXYXd),(max01kikXXXd),(maxiXiXkXiSKSxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx质心质心xxxxxxxxxxxiiXYXd),(max01xxxxxxxxxxxki

34、kXXXd),(maxiSKSkSXkXNY111分裂分裂1 1次，得到次，得到2 2个码字个码字J=2 2J=2 2个码字的初始码本构成个码字的初始码本构成),(),(:ikkXXdXXdSXSSiSXiXNY112SXXNY101（2）最佳码本的设计）最佳码本的设计 第一步：初始化。给定全部参考矢量集合第一步：初始化。给定全部参考矢量集合S S，设定，设定失真控制门限失真控制门限 , , 算法最大迭代次数算法最大迭代次数L,L,以及初始码以及初始码本本 ，设置总失真，设置总失真 ，初始迭代，初始迭代次数次数m=1m=1，最大迭代次数为，最大迭代次数为L L。 第二步：迭代。第二步：迭代。（

35、1 1）根据最邻近准则将）根据最邻近准则将S S分成分成J J个子集，个子集，（2 2）计算总失真）计算总失真00201JYYY)0(DmJmmSSS21JlJiliYXdYXdRXSmimlKml, 1;, 1,);,(),(:11 JlSXmlmmlYXdD11),(（3 3）计算新码字：每一个码字为其对应子集的质心。）计算新码字：每一个码字为其对应子集的质心。（4 4）计算相对失真改进量，）计算相对失真改进量， 与与失真控制门限比较，失真控制门限比较， 转入（转入（5 5）；）； 转入（转入（6 6）。）。（5 5）若）若m m大于大于L L，则转入，则转入(6)(6)，否则，否则m+1

36、m+1，转入，转入(1)(1)（6 6）得到最终的码书）得到最终的码书mJmmYYY21mlSXlmlXNY1mmmmDDD|1mmmJmmYYY21xxxxxxxxxxxxxxxxxxxxxSxxxxxxxxxxxxxxxxxxxxx14131211SSSSJ=4,m=104030201YYYY4, 2 , 1,);,(),(:001liliYXdYXdRXSilKl 4101),(lSXlmlYXdDxxxxxxxxxxxxxxxxxxxxx新码字新码字14131211YYYY1101|DDD 1ifm+1=2m+1=2重新开始重新开始24232221SSSS4, 2 , 1,);,(),

37、(:112liliYXdYXdRXSilKl 4122),(lSXlmlYXdD新码字新码字24232221YYYY2212|DDD 2ifm+1=3m+1=3重新开始重新开始14131211YYYYxxxxxxxxxxxxxxxxxxxxxJ=4,m=2xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 最佳码本的设计方法之一：遗传算法最佳码本的设计方法之一：遗传算法（Genetic Algorithm,GAGenetic Algorithm,GA）是借鉴生物界自然选）是借鉴生物界自然选择和自然遗传机制的随机化搜索算法。择和自然遗传机制的随机化搜索算法。三、

38、码字搜索三、码字搜索1.1.全搜索全搜索2.2.快速搜索算法（二叉树形搜索）快速搜索算法（二叉树形搜索）1 1、全搜索、全搜索VQVQ时间复杂度时间复杂度: N(2k-1)次加法次加法, kN 次乘法和次乘法和N-1 次比次比较（每个输入矢量）较（每个输入矢量）空间复杂度空间复杂度: kN 个标量个标量如何降低复杂度如何降低复杂度:采用约束结构采用约束结构; 采用快速码字搜索采用快速码字搜索算法算法最近邻最近邻搜索搜索索引索引码书码书输入输入 矢量矢量.y1y2yNxd(x,y2)d(x,y1)码书码书C d(x, yN)min d(x,yj) d(x,yj)=(x1- yj1)2+ (x2-

39、 yj2)2+ +(xk- yjk)2(2k-1)(2k-1)次加法，次加法，k k次乘法次乘法2、二叉树形搜索、二叉树形搜索X先与先与Y0和和Y1比较比较,计算出失真计算出失真d(X, Y0)和和d(X, Y1)，如，如果后者较小，则走下支路，同时送果后者较小，则走下支路，同时送“1”输出；如此类输出；如此类推，最后到达，则送出标号推，最后到达，则送出标号101。输入矢量输入矢量X中间码字中间码字Y1Y0Y00Y01Y10Y11Y000Y001Y010Y011Y100Y101Y110Y111图中各层的码字，用下面的方法得到：图中各层的码字，用下面的方法得到： 如如J=8，已知码本中，已知码本

40、中8个码字，则按最邻近的原则个码字，则按最邻近的原则配对：配对：【 Y000 ， Y001 】；【 Y010 ，Y011 】；【 Y100 ，Y101 】 ；【Y110， Y111 】。求各对的质心，得到求各对的质心，得到【 Y00 ， Y01 】； 【 Y10 ，Y11 】 ，再求这两对的质心，得到，再求这两对的质心，得到Y0和和Y1。比较全搜索和树形搜索的算法量比较全搜索和树形搜索的算法量Y000 Y001 Y010 Y011 Y100Y101 Y110Y111 输入输入矢量矢量X全搜索全搜索全搜索需要全搜索需要8次失真测度计算。次失真测度计算。输入矢量输入矢量X中间码字中间码字Y1Y0Y00Y01Y10Y11Y000Y001Y010Y011Y100Y101Y110Y111树形搜索需要树形搜索需要2log2J=6次失真测度计算。次失真测度计算。根结点根结点(8,10)(4,8)(6,7)(1,3)(9,10)(9,9)(8,9)(9,8)(5,8)(5,9)(4,9)(4,10)(7,7)(6,8)(8,7)(7,8)(2,3)(2,2)(1,2)(2,1)输入矢量输入矢量 (3,5)编码比特位编码比特位 11001110010000011011T THHA ANNKKS S