语音信号处理 (31).ppt
16.5 6.5 降低复杂度的矢降低复杂度的矢量量化系统量量化系统2 矢量量化器的复杂度矢量量化器的复杂度 矢矢量量量量化化与与标标量量量量化化相相比比，其其主主要要缺缺点点是是复复杂杂度度随随维维数数的的增增大大而而成成指指数数式式增增加加，这这是是实实现高维数矢量量化的现高维数矢量量化的主要障碍主要障碍。6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统3 在信号处理中，复杂度有两种：在信号处理中，复杂度有两种：时时间间复复杂杂度度单单位位时时间间内内所所需需要要的的计计算算量量，它它包包括括加加（减）法、乘法和比较运算的次数；（减）法、乘法和比较运算的次数；空间复杂度空间复杂度存储容量。存储容量。对降低复杂度的研究，可朝两个方向进行：对降低复杂度的研究，可朝两个方向进行：一：寻找一：寻找好的快速算法好的快速算法；二：使二：使码书结构化码书结构化，以减小搜索量和存储量。，以减小搜索量和存储量。6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统41 1 树搜索原理树搜索原理 下面以二叉树为例说明树搜索原理。下面以二叉树为例说明树搜索原理。树搜索矢量量化器树搜索矢量量化器6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统图图1警察抓小偷警察抓小偷51 1 树搜索原理树搜索原理 下面以下面以二叉树二叉树为例说明树搜索原理。为例说明树搜索原理。二叉树结构图中，以树根二叉树结构图中，以树根第一层第一层为起点，为起点，第二层第二层有有2 2个节点（个节点（Y Y0 0，Y Y1 1）；）；第三层第三层有有4 4个节点（个节点（Y Y0000，Y Y0101，Y Y1010，Y Y1111）；第四层（此树的最后一层）有）；第四层（此树的最后一层）有8 8个节点，这层上的节个节点，这层上的节点又称为树叶。点又称为树叶。树搜索矢量量化器树搜索矢量量化器6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统66.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统图图6.9 6.9 二叉树结构图二叉树结构图1 1 当当下子树下子树的节的节点失真最小时点失真最小时0 0 当当上子树上子树的的节点失真最小时节点失真最小时7 2 2 树结构的设计树结构的设计 树树搜搜索索矢矢量量量量化化器器的的编编码码器器是是由由树树型型码码书书和和相应的搜索算法构成的。下图是它的原理图。相应的搜索算法构成的。下图是它的原理图。6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统8图图6.10 6.10 树搜索矢量量化器原理框图树搜索矢量量化器原理框图6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统思考：树形码书和数组码书相同吗？思考：树形码书和数组码书相同吗？9 设计树结构方法：从设计树结构方法：从树叶树叶开始设计；从开始设计；从树根树根开始设计。开始设计。（1 1）从从树树叶开始叶开始设计设计的的办办法法 四四层层二二叉叉树树矢矢量量量量化化器器维维数数为为K K，第第四四层层有有N N=8=8个个码码字（字（树树叶数）。叶数）。第一步第一步 假假定定第第四四层层的的8 8个个码码字字，已已由由前前面面设设计计码码书书的的方方法法得得到到了了。将将这这些些码码字字，按按码码字字距距离离最最近近配配对对的的原原则则（因因为为是是 二二 叉叉 树树 型型），得得 到到：Y Y000000,Y Y001001,Y Y010010,Y Y011011,Y Y100100,Y Y101101,Y Y110110,Y Y111111,并并把把它它们们放放在在相相应应的的树树叶叶位位置上。置上。6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统10 第第二二步步 求求出出这这些些码码字字对对的的中中心心，如如 Y Y000000，Y Y001001 的的中中心心为为Y Y0000。总总共共得得到到四四个个中中心心：Y Y0000，Y Y0101，Y Y1010，Y Y1111，并并把把它它们放在第三层上。们放在第三层上。第第三三步步 将将第第三三层层上上的的码码字字仍仍按按最最近近距距离离原原则则配配对对，得得到到 Y Y0000，Y Y0101，Y Y1010，Y Y1111。再再求求出出码码字字对对中中心心Y Y0 0与与Y Y1 1并并将它们放在第二层上将它们放在第二层上.这这种种树树形形码码书书总总的的尺尺寸寸为为 N N0 0=8+4+2=14=8+4+2=14，即即共共有有1414个个码字，而译码端的码字大小就是树叶数码字，而译码端的码字大小就是树叶数 N N=8=8。6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统11(2)(2)从树根开始设计的方法从树根开始设计的方法 以四层二叉树为例，具体设计步骤如下：以四层二叉树为例，具体设计步骤如下：6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统第一步第一步 求出整个训练序列的形心，作为初始码书。再用求出整个训练序列的形心，作为初始码书。再用分裂法得到的分裂法得到的Y Y0 0，Y Y1 1便是第二层的码字便是第二层的码字。第二步第二步 分裂法，得到第三层的分裂法，得到第三层的4 4个码字个码字Y Y0000，Y Y0101，Y Y1010，Y Y1111。这样继续下去，一直计算到树叶为止。这样继续下去，一直计算到树叶为止。123 3 树搜索矢量量化器的复杂度树搜索矢量量化器的复杂度 树搜索与全搜索矢量量化器相比：树搜索与全搜索矢量量化器相比：在搜索时间上，二叉树的搜索速度快。在搜索时间上，二叉树的搜索速度快。在存储量上，二叉树多于全搜索。在存储量上，二叉树多于全搜索。在性能上，比全搜索矢量量化器的性能差。在性能上，比全搜索矢量量化器的性能差。通通常常可可以以适适当当选选择择各各层层的的树树叉叉型型数数，在在搜搜索索速速度度、存存储量及质量三者之间得到一种折衷。储量及质量三者之间得到一种折衷。6.5 6.5 降低复杂度的矢量量化系统降低复杂度的矢量量化系统
