CN1181151A - 快速语音编码的代数码书深度优先搜索 - Google Patents

Abstract

在声音编码时要进行码书搜索。码书由40个位置的码矢量的一个集合组成,每一码矢量由分至其预置有效位置的N个幅度非零的脉冲组成。为减少搜索复杂度,使用了涉及从1到M排序的树结构的深度优先搜索。每级执行路径建立操作,依照给定的脉冲顺序规则和选择准则,选出预置数目的新脉冲,并为这些新脉冲选定有效位置,以延伸来自上一级的一条候选路径。

Description

快速语音编码的代数码书深度优先搜索

本文是关于于1995年3月10日提交的美国专利申请No.08/401,785“快速语音编码的代数码书深度优先搜索”的部分继续申请。

本发明涉及一种考虑到声音信号的传输与合成而对声音信号进行数字编码的改进技术。尤其涉及语音信号，但不排除适用于其他声音信号。

语音通过卫星陆地移动台，数字广播，分组网络的传输，语音存储，语音应答，以及无线电话等应用对能够提供良好主观质量与比特率折衷的高效的数字语音编码技术提出了日益增加的需求。

码激励线性预测(CELP)是现有技术中所采用的能够获得良好质量与比特率折衷的最好的技术方案之一。根据该技术，语音信号经过抽样，以L个样点(即矢量)组成的连续块的形式处理，其中L是某个预置数。CELP技术使用了一个码书。

在CELP中，码书就是称作L维码矢量的L个样点所组成的序列的一个有序集。码书包括一个从1到M变化的下标(index)k，M表示了码书的大小，有时M用比特数b表示。

    M＝2^b

码书可以存储在物理内存中(如一个查寻表)，或者借助一机制把下标与相应的码矢量联系起来(如一个公式)。

在CELP中，码书中恰当的码矢量经过依据语音信号谱特征建模的时变滤波器滤波，可以实现对样点组成的每一数据块的语音合成。在编码器端，计算码书中所有的码矢量或其子集的合成输出，根据一感觉加权失真测度保留能够产生与原始语音最接近的合成输出的码矢量。

第一类码书叫做“随机”码书。此类码书的一个缺点是它经常要使用大量的物理存储空间。它们是随机的，随机意谓着从下标到相应码矢量的路径涉及一查找表，而该查找表是在大量的语音训练集上应用随机数产生或统计技术得到的。随机码书的大小由于存储空间及/或搜索的复杂度而受到限制。

第二类码书是代数码书。与随机码书相比，代数码书不具有随机性，不需要大量的存储单元。代数码书是一个码矢量有序集，其中第k个码矢量的脉冲幅度和相位可以根据一个规则由相应的下标k推出。代数码书不需或只需极少的物理存储单元，因此其大小不受存储空间的限制。代数码书还可以进行快速搜索。

本发明的目的是提供一种适用于多种类型码书并且能够在声音编码时极大地降低码书搜索复杂度的方法和装置。

根据本发明，尤其提供了一种进行声音信号编码时执行码书深度优先搜索的方法：

码书由码矢量A_K的一个集合组成，定义了多个不同位置p并包括N个幅度非零的脉冲，每个脉冲可分配至码矢量的预置有效位置；

深度优先搜索涉及一M级/层(level)有序的树结构，每一级m与N_m个幅度非零的脉冲相关联，N_m为一预置数，N_m＞＝1，涉及所有M级的各级预置数的和与组成码矢量的幅度非零的脉冲数目N相等。树结构的每一级m进一步涉及一路径建立操作，一给定脉冲顺序规则，和选择准则；

码书深度优先搜索操作包括以下步骤：---在树结构的第一层相关的路径建立操作包括：

根据相应的脉冲顺序规则，在N个幅度非零的脉冲中选择N₁个脉冲；

根据相应的选择准则，在N₁个幅度非零的脉冲的P个有效位置中至少选择一个有效位置，从而定义至少一条第一层候选路径；---在树结构的m级，相应的路径建立操作通过扩展(m-1)级的一条候选路径迭代定义了一条m级候选路径，步骤如下：

根据相应的脉冲顺序规则，选择在建立m-1级路径时没有选择的幅度非零的N_m个脉冲；

根据相应的选择准则，在这N_m个幅度非零的脉冲中至少选择一个有效位置p，从而定义至少一条m级候选路径；

其中源于一条第1级候选路径并在树结构的后续级路径建立中扩展的一条M级候选路径确定了码矢量中N个幅度非零的脉冲的各个的位置P，由此定义了一个候选码矢量A_K。

根据本发明也提供一种声音编码的码书深度优先搜索的方法，其中，

码书由一个码矢量A_K的集合组成，每个码矢量定义了多个不同位置p并且包括N个幅度非零的脉冲组成，其中每个脉冲都分配至码矢量的预置有效位置P；

深度优先搜索涉及(a)将N个幅度非零的脉冲划分至M个子集，每一子集至少包括一个幅度非零的脉冲，(b)一树结构，其每一节点代表了N个幅度非零脉冲的有效位置p，该树结构定义了多个搜索级，每一搜索级与M个子集中的一个相关联，并有给定的脉冲顺序规则和选择准则；

码书深度优先搜索操作包括以下步骤：---在树结构的第一搜索级，

根据相应的脉冲顺序规则，在N个幅度非零的脉冲中至少选择一个以形成相应子集；

根据相应的选择准则，在上述至少一个幅度非零脉冲的有效位置p中至少选择一个有效位置，以定义至少一条通过树节点的路径；---在树结构的每一后续搜索级

根据相应的脉冲顺序规则，至少选择一个先前未选择的上述幅度非零的脉冲，以形成相应子集；

根据相应的选择准则，在上述至少含有一个幅度非零脉冲的有效位置p的相应子集中至少选择一个有效位置，以延伸至少一条通过树节点的上述路径；

其中在第一搜索级定义并在后续搜索级延伸的每条路径确定了码矢量A_K的N个幅度非零的脉冲的各个位置p，从而在声音编码时构成了一个候选码矢量。

本发明还涉及一声音信号编码时执行码书深度优先搜索操作的装置，其中，

码书由一个码矢量A_K的集合组成，每个定义了多个不同位置p并且包括N个幅度非零的脉冲组成，其中每个脉冲都分配至码矢量的预置有效位置P

深度优先搜索涉及(a)将N个幅度非零的脉冲划分至M个子集，每一子集至少包括一个幅度非零的脉冲，(b)一树结构，每一节点代表了N个幅度非零脉冲的有效位置p，该树结构定义了多个搜索级，每一搜索级与M个子集中的一个相关联，并有自己的脉冲顺序规则和选择准则；

码书深度优先搜索装置包括：

对于树结构的第一搜索级，

第一装置，根据相应的脉冲顺序规则，在N个幅度非零的脉冲中至少选择一个以形成相应子集；

第一装置，根据相应的选择准则，在上述至少一个幅度非零的脉冲的有效位置p中选择至少一个有效位置以定义至少一条通过树节点的路径；

对于树结构的每一后续搜索级，

第二装置，根据相应的脉冲顺序规则，选择至少一个先前未选择的上述幅度非零的脉冲，以形成相应子集；

第二装置，后续搜索级根据相应的选择准则，在上述至少含有一个幅度非零脉冲的有效位置p的相应子集中选择至少一个有效位置，以延伸至少一条通过树节点的上述路径；

其中在第一搜索级定义并在后续搜索级延伸的每条路径确定了码矢量A_K的N个幅度非零的脉冲的各个位置p，从而在声音编码时构成了一个候选码矢量。

本发明进一步涉及服务于分为若干蜂窝的大片地理区域的蜂窝通信系统，它包括：

移动发射/接收单元；

位于各蜂窝的蜂窝基站；

蜂窝基站间进行通信控制的设备；

在小区中的每个移动单元和小区蜂窝基站间进行双向无线通信的子系统，该双向无线通信的子系统的移动单元和基站均具有：(a)包括对语音信号进行编码的装置及传输编码的语音信号的装置的发射机，(b)包括接收编码后的信号及解码装置的接收机；

其中的语音信号编码装置包括在对语音信号进行编码时进行码书深度优先搜索的模块，其中：

码书由一个码矢量A_K的集合组成，定义了多个不同位置p的并且包括N个幅度非零的脉冲，其中每个脉冲都分配至码矢量的预定有效位置P；

深度优先搜索涉及(a)将N个幅度非零的脉冲划分至M个子集，每一子集至少包括一个幅度非零的脉冲，(b)一树结构，每一节点代表了N个幅度非零的脉冲的有效位置p，该树结构定义了多个搜索级，每一搜索级与M个子集中的一个相关联，并有自己的脉冲顺序规则和选择准则；

码书深度优先搜索装置包括：---对于树结构的第一搜索级，

第一装置，根据相应的脉冲顺序规则，在N个幅度非零的脉冲中至少选择一个以形成相应子集；

第一装置，根据相应的选择准则，在上述至少一个幅度非零的脉冲的有效位置p中选择至少一个有效位置以定义至少一条通过树节点的路径；---对于树结构的每一后续搜索级

第二装置，根据相应的脉冲顺序规则，选择至少一个先前未被选择的上述幅度非零的脉冲，以形成相应子集；

第二装置，后续搜索级根据相应的选择准则，在上述至少含有一个幅度非零脉冲的有效位置p的相应子集中选择至少一个有效位置，以延伸至少一条通过树节点的上述路径；其中在第一搜索级定义并在后续搜索级延伸的每条路径决定了码矢量A_K的N个幅度非零的脉冲的各个位置p，从而在声音编码时构成了一个候选码矢量。

通过对带有附图的实施例的非严格描述，本发明的目的、优点和其它特征会有更明显的体现。

图1为根据本发明的一种编码系统实施例的原理框图，系统包括一脉冲位置似然估计器和一优化控制器；

图2为与图1所示编码系统对应的解码系统原理框图；

图3为图1中编码系统的优化控制器为计算最优码矢量使用的若干嵌套循环的图解表示；

图4a的树结构作为一个例子来说明图3中的“嵌套循环搜索”技术的一些特色；

图4b是在较低层处理的性能值超过某一给定门限的条件时图4a的树结构；这是一种仅仅把注意力集中最可能的树区域的快速树搜索方法；

图5显示了深度优先搜索技术是如何通过树结构进行脉冲位置组合的；本例是根据交织单脉冲排列设计的一个40位置的码矢量的10脉冲码书；

图6是图1中的脉冲位置似然估计器和优化控制器的操作流程图；

图7是典型蜂窝通信系统的结构框图。

虽然在本说明中，码书深度优先搜索算法及相应装置应用于蜂窝通信系统是作为一个无限制使用范围的例子而公开的，但需指出，本算法及装置可用于许多其它需要语言编码的通信系统，并且可以获得同样的效果。

在蜂窝通信系统1(图7)中，大片地理区域划分为若干小区以提供通信业务。每一小区有一蜂窝基站2，提供无线信令信道(radio signallingchannels)及音频与数据信道。

在蜂窝基站所能覆盖的范围内(小区)，无线信令信道用于寻呼移动无线电话(移动发射机/接收机单元)如3，播叫本小区或其它小区内的其它无线电话3，或者拨入其它网络，如公用电话交换网(PSTN)4。

一旦无线电话3成功地拨叫或接收到一个电话，无线电话3所在小区的基站2就建立起一条语音或数据信道，基站2、无线电话3通过该语音或数据信道进行通信。在通话期间，无线电话3通过信令信道接收控制和定时信息。

如果在通话期间，无线电话3由一个小区进入另一个小区，那么无线电话将把通话切换到给新小区的一个可用的语音或数据信道上。与之类似，如果在漫游时没有通话，则在信令信道上传送一控制信息，使无线电话3注册在新小区的基站2上。这种方式使得在广大地理区域上进行移动通信成为可能。

蜂窝通信系统1还包括一控制基站2与公用电话交换网4之间通信，例如在无线电话3与公用电话交换网(PSTN)4之间的通信或者第一小区内的无线电话3与第二小区内的无线电话3之间的通信的终端设备5。

当然要建立某一小区内的每一无线电话3与该小区基站2之间的通信，双向无线通信子系统是必不可少的。双向无线通信子系统通常在无线电话3和蜂窝基站2上包括(a)进行语音编码以及通过如天线6或7发射编码的发射机，(b)通过同样的天线6或7接收传输的编码语音信号及解码装置的接收机。一般技术人员所共知，为了压缩通过双向无线通信系统，即无线电话3与基站2之间，传送话音所需的带宽，语音编码必不可少的。

本发明的目的是提供一种高效的数字语音编码技术，在例如蜂窝基站2和无线电话3通过语音或数据通道进行双向语音传送时，能够获得良好主观品质/比特率的折衷。图1是一适于采用本技术的数字语音编码装置的结构框图。

图1的语音编码系统与U.S父专利申请No.07/927,528图1中所示的编码装置完全相同，在父申请的图1中已加入了根据本发明的脉冲位置估计器112。父美国专利申请No.07/927,528是关于发明“基于代数码的有效语音编码的动态码书”的专利申请，于1992年9月10日提交。

输入的模拟语音信号经过采样以数据块(bloC_K)的形式处理。需指出本发明并不限于语音信号，也可考虑用于其它类型声音的编码。

在图示例子中，输入的采样语音数据决S(图1)由L个连续采样点组成。在CELP中，L定义为子帧长(subframe length)，通常在20～80之间取值，L个样点组成的块定义为L维矢量。在编码过程中，产生不同的L维矢量。以下给出图1和图2中有关矢量及传输参数的列表：

主要L维矢量列表：S：输入语音矢量R：基音去除的残余矢量X：目标矢量D：后向滤波目标矢量A_K：代数码书中下标为k的码矢量C_K：更新矢量(滤波后的码矢量)

传输参数列表：k：码矢量下标(代数码书的输入)g：增益STP：短时预测参数(定义为A(z))及LTP：长时预测参数(定义基音增益b，基音延迟T)

解码原则

首先描述图2的语音解码装置。图2显示了数字输入(信号隔离器205的输入)和语音采样输出(合成滤波器204的输出)之间执行的不同操作的步骤。

信号隔离器205接收数字输入信道上的二进制信息，从中提取出下标k，增益g，短时预测参数STP，长时预测参数LTP。语音信号的当前L维矢量在这4个参数的基础上合成，解释如下。

图2的语音解码装置由一动态码书208构成，码书包括一代数码书发生器201，一自适应前置滤波器202，一放大器206，一加法器207，一长时预测器203，和一合成滤波器204。

第一步，代数码书根据下标k产生码矢量A_K。

第二步，码矢量A_K经过输入有短时预测参数STP的自适应前置滤波器202处理，产生输出更新矢量C_K。自适应前置滤波器202动态地控制输出更新矢量C_K的频率成分以提高语音质量，即减少干扰人耳的频率造成的听觉失真。通常，自适应前置滤波器202的转移函数如下式： $F_a\left(z\right)=\frac{A(z/{\mathrm{\γ}}_1)}{A(z/{\mathrm{\γ}}_2)}$ $F_b\left(z\right)=\frac{1}{(1-b_0{z}^T)}$

f_a(z)是共振峰前置滤波器，γ₁、γ₂是常数，0＜γ₁＜γ₂＜1。该前置滤波器能增加共振峰区域，在码率低于5bit/s时，工作非常有效。

F_b(z)是基音前置滤波器，T是时变基音延迟，b₀是常数或等于当前或先前子帧的长时基音预测参数的量化值。F_b(z)可在任何码率有效地增强基音谐波频率(Pitch harmonic frequencies)。因此F(z)通常包括一基音前置滤波器，有时附加一共振峰前置滤波器，即F(z)＝F_a(z)f_b(z)。当然也可使用其它类型的前置滤波器。

依据CELP技术，首先码书208输出的更新矢量C_K在放大器206中由增益因子g进行尺度变换从而获得取样语音信号S输出，然后加法器207将变换后的波形gC_K与输入LTP参数的长时预测器203的输出E(合成滤波器204的信号激励的长时预测分量〕相加。长时预测器和加法器形成反馈环，其转移函数B(z)定义为：

B(z)＝bz^-T，b、T分别是上文定义的基音增益和延时。

预测器203是一个依据上次接收的LTP参数b、T对语音的基音周期建模的转移函数的滤波器。它引入了样值的适当的基音增益b和时延T。复合信号E+gC_K构成了转移函数是1/A(z)的合成滤波器204的激励信号。滤波器204依据上次接收的STP参数形成正确的波谱，更确切地说，滤波器204对语音的共振频率(共振峰)建模。输出块S就是合成的抽样语音信号，使用本领域熟知的抗混迭滤波技术，它可以转化为模拟信号。

有许多设计代数码书208的方法。本发明的代数码书是由N个幅度非零的脉冲(或简称非零脉冲)组成的矢量构成。

以P_i代表第i个幅度非零的脉冲的位置，

代表其幅度。因为第i个脉冲的幅度固定或有某种方法可在搜索前确定出 ，所以假设幅度

为已知量。

轨迹i(track i)用T_i表示，它代表了在1到L间的取值的位置P_i的集合。在L＝40的条件下给出一些典型的轨迹集。第一个例子是在上文中提到的有关“单脉冲交织排列(ISSP)″的U.S专利申请No.927,528中介绍的设计实例。在该设计实例中，40个位置的集合分至5个交织轨迹，每一轨迹有40/5＝8个有效位置，需要3bit确定一脉冲的这8＝2³个有效位置，因此，对于这种特定的代数码书结构，共需5×3＝15个编码位以确定脉冲的位置。

设计1：ISSP(40，5)

i      轨迹(第i个脉冲的有效位置)

1      T1＝{1，6，11，16，21，26，31，36}

2      T2＝{2，7，12，17，22，27，32，37}

3      T3＝{3，8，13，18，23，28，33，38}

4      T4＝{4，9，14，19，24，29，34，39}

5      T5＝{5，10，15，20，25，30，35，40}在这40个位置属于一个且仅属于一个轨迹的意义上，该ISSP是完备的。可以有多种方法从一个或多个ISSP推导出满足特定的脉冲数目或编码位要求的码书结构。例如，在ISSP(40，5)中简单地忽略轨迹5或将轨迹4、5看作一个轨迹，就可得到一4脉冲码书。设计2，3提供了完备的ISSP设计的其它实例。

设计2：ISSP(40，10)

i      轨迹(第i个脉冲的有效位置)

1      T1＝{1，11，21，31}

2      T2＝{2，12，22，32}

3      T3＝{3，13，23，33}

9      T4＝{9，19，29，39}

10     T5＝{10，20，30，40}

设计3：ISSP(48，12)

i      轨迹(第i个脉冲的有效位置)

1      T1＝{1，13，25，37}

2      T2＝{2，14，26，38}

3      T3＝{3，15，27，39}

4      T4＝{4，16，28，40}

5      T5＝{5，17，29，41}

…          ……

11     T11＝{11，23，35，47}

12     T12＝{12，24，36，48}注意在设计3中，轨迹T5至T12的最后一个脉冲的位置落在了子帧长度L＝40之外，此时，最后一个脉冲将被忽略。

设计4：两个ISSP(40，1)的和

i      轨迹(第i个脉冲的有效位置)

1      T1＝{1，2，3，4，5，6，7，…，39，40}

2      T2＝{1，2，3，4，5，6，7，…，39，40}

在设计4中，轨迹T1、T2允许40个有效位置的任何一个位置，两者重叠。当几个脉冲占据了同一位置时，它们的幅度简单相加。

围绕ISSP的设计思想可以建立各种码书。

   编码原则

抽样后的语音信号S以连续块的形式由图1中的编码系统编码。编码系统分为11个模块，102到112。因为大多数模块的功能与U.S父专利申请No.07/1927,328的对应部分相同，所以在下面的叙述中仅简单解释各模块的功能和执行的操作，而将注意力集中在与公开的U.S父专利申请No.07/927,528相比新的部分。

依照先前的技术，每一L个样点组成的语音信号块由一线性预测编码(LPC)谱分析仪102生成线性预测编码(LPC)参数集，LPC参数称为短时预测参数(STP)，确切地说，分析仪对每一L个样点的块S的谱特性建模。

白化滤波器103对L个样点的输入块S白化滤波。基于当前的STP参数的白化滤波器的转移函数如下： $A\left(z\right)=\underset{i=0}{\overset{M}{\mathrm{\Σ}}}{a}_i{z}^{-i}$ a₀＝1，z是Z变换的一般特征变量。如图1所示，白化滤波器103输出残余矢量R。

基音提取器104计算、量化LTP参数基音延时T和基音增益g。提取器104的初始状态值设置为由初始状态提取器110输入的FS值。在U.S父专利申请No.07/927,528中叙述了计算与量化LTP参数的详细过程，相信这也是普通技术人员所熟知的技术，所以在本申请中不再进一步展开叙述。

滤波响应特征器105输入STP和LTP参数，它为下述步骤计算滤波器响应特征FRC。FRC信息由以下三个分量组成，其中n＝1，2，…，Lf(n)F(z)的响应。注意，F(z)通常包括一基音前置滤波器。h(n)1/A(zr^-1)对f(n)的响应，r是感知因子。一般而言，h(n)是对前置滤波器F(z)，感知加权滤波器W(z)，合成滤波器1/A(z)的级联F(z)W(z)/A(z)的脉冲响应。F(z)和1/A(z)与解码器使用的滤波器相同。U(i，j)依据下述表达式的h(n)的自相关： $U(i,j)=\underset{k=1}{\overset{L}{\mathrm{\Σ}}}h(k-i+1)h(k-j+1)$

i＝1，2，…，L    1≤i≤j≤L；当n＜1时，h(n)＝0；

长时预测器106输入上次的激励信号(即前一子帧的E+gC_K)，利用合适的基音延时T和增益b产生一个新的E分量。

感知滤波器107的初始状态设置为由初始状态提取器110输入的值FS。图1的减法器计算基音去除残余矢量R′＝R-E，R′输入至感知滤波器107，在107的输出端得到目标矢量X。如图1所示，滤波器107依据输入的STP参数改变其转移函数。基本上说，X＝R′-P，P代表包括了过去激励的震铃(ringing)的长时预测成分。误差Δ的MSE指标由下述矩阵形式表示： $\underset{k}{\min }{\left|\right|\mathrm{\Δ}\left|\right|}^2=\underset{k}{\min }{\left|\right|S^{\′}-{\hat{S}}^{\′}\left|\right|}^2=\min {\left|\right|S^{\′}-[p-g{A}_k{H}^T]\left|\right|}^2=\underset{k}{\min }{\left|\right|X-g{A}_k{H}^T\left|\right|}^2$ 其中 $\mathrm{\Δ}={\hat{S}}^{\′}-S^{\′},{\hat{S}}^{\′},$ S′分别是 ，S经过具有如下转移函数的感知加权滤波器的输出。

，r＝0.8是一感知常数H是下述的h(n)响应形成的一L×L的下三角Toeplitz矩阵，h(0)占据了矩阵的对角线，h(1)，h(2)，…h(L-1)分别占据了相应的下三角。

图1的滤波器108完成后向滤波。令上文的误差表达式对增益的一阶偏导为0，可求出最佳增益值： $\frac{\∂{\left|\right|\mathrm{\Δ}\left|\right|}^2}{\∂g}=0$ $g=\frac{X{\left(A_k{H}^T\right)}^T}{{\left|\right|A_k{H}^T\left|\right|}^2}$ g为上述值时，最小误差变为： $\underset{k}{\min }{\left|\right|\mathrm{\Δ}\left|\right|}^2=\underset{k}{\min }\{{\left|\right|X\left|\right|}^2-\frac{{\left(X{\left(A_k{H}^T\right)}^T\right)}^2}{{\left|\right|A_k{H}^T\left|\right|}^2}\}$

目的是找出取得最小误差时对应的具体下标k。观察发现‖X‖²是固定值，所以使下面的值取最大值即可求出下标k。 $\underset{k}{\max }\frac{{\left(X{\left(A_k{H}^T\right)}^T\right)}^2}{{\left|\right|A_k{H}^T\left|\right|}^2}=\underset{k}{\max }\frac{{\left(\left(\mathrm{XH}\right){A_k}^T\right)}^2}{{{\mathrm{\α}}_k}^2}=\underset{k}{\max }\frac{{\left(D{A_k}^T\right)}^2}{{{\mathrm{\α}}_k}^2}$

D＝(XH)    α_k ²＝‖A_kH^T‖²

后向滤波器108计算出后向滤波目标矢量D＝(XH)。“后向滤波”一词源于将(XH)解释为X的时间翻转滤波。

优化控制器109的作用是为编码当前L个样点的块在代数码书可用的码矢量中选出最佳码矢量。在一具有N个幅度非零的脉冲的码矢量组成的集合中，最佳码矢量的选择准则是以使一比值取最大值的形式给出的：基本选择准则： $k={\underset{k}{\max }}^{-1}\left[Q_k\left(N\right)\right]$ $Q_k\left(N\right)=\left[\frac{{\left(D{A_k}^T\right)}^2}{{{\mathrm{\α}}_k}^2}\right]$

A_K由N个幅度非零的脉冲组成，上式中的分子是 ${{\mathrm{DA}}_k}^T=\mathrm{\Σ}{D}_{p_i}{S}_{p_i}$ 的平方。D是后向滤波目标矢量，A_K是N个幅度 非零脉冲的代数码矢量。

分母是一能量项，可表示为： ${{\mathrm{\α}}_k}^2=\underset{i=1}{\overset{N}{\mathrm{\Σ}}}{S}_{p_i}U(p_i,p_j)+2\underset{i=1}{\overset{N-1}{\mathrm{\Σ}}}\underset{j=i+1}{\overset{N}{\mathrm{\Σ}}}{S}_{p_i}{S}_{p_j}U(p_i,p_j)$ U(P_i，P_j)是位置在P_i，P_j的两单位脉冲的相关，一个在位置P_i，一个在位置P_j。依据上述等式，矩阵在滤波响应模块105中计算，并包含在图1中的FRC参数集中。

快速计算分母的方法涉及图4的N层嵌套循环。图中S(i)、SS(i，j)用在表示量值 的地方。计算分母是最耗时间的操作。图4中从最外层到最内层的每一层循环计算分母的操作可分别在单独的一行写出。 ${{\mathrm{\α}}_k}^2={S_{p_1}}^{2}U(p_1,p_1)$ $+{S_{p_2}}^{2}U(p_2,p_2)+2S_{p_1}{S}_{p_2}U(p_1,p_2)$ $+{S_{P3}}^{2}U(P_3,P_3)+2[S_{P1}{S}_{P3}U(P_1,P_3)+S_{p2}{S}_{P3}U(P_2,P_3)]$

+.......... ${S_{P_N}}^{2}U(P_N,P_N)+2[S_{p_1}{S}_{p_N}U(p_1,p_N)+S_{p_2}{S}_{p_N}U(p_2,p_N)+.....+S_{p_{n-1}}{S}_{p_N}U(p_{N-1},p_N)]$ P_i是第i个幅度非零的脉冲的位置。

如果优化控制器执行一些预运算，将由滤波器响应特征器105输入的矩阵U(i，j)依照下面的关系变换成U′(i，j)，前面的等式就可简化。

U′(j，k)＝S_jS_kU(j，k)S_k是位置为k的一独立脉冲依照下文中的幅度估计的量化值选择的幅度。为精简等式，在后续描述中，因子2将忽略。

利用新矩阵U′(j，k)，图3中从最外到最内的每层循环计算分母的快速算法按如下形式写在单独一行。α_k ²＝U′(p₁，p₁)

+U′(p₂，p₂)+U′(p₁，p₂)

+U′(P₃，P₃)+U′(P₁，P₃)+U′(P₂，P₃)

+.....  .....  .......

+U′(p_N，p_N)+U′(p₁，p_N)+U′(P₂，P_N)+.......+U′(p_N-1，p_N.)

图4a与4b图示了两个树结构，体现了图3描述的“循环嵌套搜索”的一些特征，从而与本发明相比较。图4a树的底层终结结点图示了对于每一脉冲可位于4个位置的5脉冲例子(N＝5)的所有的脉冲位置组合。穷举“循环嵌套”技术基本是按树节点从左至右的方式进行。它的缺点之一是搜索复杂度是脉冲数目N的增函数。为了能够处理具有大量数目N的脉冲的码书，只能满足于码书的局部搜索。图4b与4a的结构相同，但将注意力集中在了树中最可能的区域，从而实现快速搜索。精确地说，较底层的操作并非是系统的，而是基于性能参数超过某一门限的条件之下的。

   深度优先搜索

现在，我们把注意力转移向另一种更快的技术，即本发明的目的，该技术由图1中的脉冲位置似然估计器112和优化控制器109执行。首先描述其总体特征，然后是该技术的一些具体实施例。

搜索的目的是在假定脉冲幅度固定或搜索前已由某种信号机制，例如在1995年2月6日提交的共同未决的U.S专利申请NO.08/383,968中所描述的那样，确定出了信号幅度的条件下，找出N脉冲位置最佳集的码矢量。基本选择准则是使上文提到的比值Q_K取最大值。

为减少搜索复杂度，一次决定N_m个脉冲的位置。更准确地说，这N个有效脉冲划分至(图6步骤601)M个N_m脉冲组成的非空子集，N₁+N₂+...+N_m…+N_M＝N。对于最前面的J＝N₁+N₂…+N_m-1个脉冲的特定位置选择称为一m级路径或长度为J的路径。在仅考虑这J个相关脉冲时，选择一J脉冲位置路径的基本准则是比值Q_K(J)。

搜索从子集#1开始，依据树结构对后续子集处理，其中在树的m级搜索m子集。

在第一层搜索的目的是研究子集#1的N₁个脉冲及其有效位置以决定出一条或若干长度为N₁的候选路径，构成第一层的树结点。

在m层，研究N_m个新脉冲和其有效位置，将在m-1层的每个终结结点的路径都延伸为m层的长度为N₁+N₂+…+N_m的候选路径，一个或一些候选路径用于构成m层结点。

最佳码矢量就是对所有的M层结点使比值Q_K(N)最大的长度为N的路径。

在上文提到的U.S专利申请NO.927,528中，脉冲(或轨迹)按预定顺序处理，在本发明中，脉冲以不同的顺序处理。事实上，在每次搜索过程特定的情形下，脉冲是按照最有可能的顺序处理的。最终使用了一新顺序下标n(n＝1，2，…，N)，搜索中处理的第n个脉冲的(D)标识号(由“脉冲顺序函数”：i＝i(n)给出。例如对于一5脉冲码书，在某些特定时刻，搜索路径按下述脉冲顺序函数处理：

n＝1  2  3  4  5  顺序号

i＝4  3  1  5  2  脉冲(或轨迹)ID

为了智能地猜测出任一时刻何种脉冲顺序更有可能，本发明引入了基于语音信号的“脉冲位置似然估计矢量”B。估计矢量B的第p个分量B_p表示了一脉冲在寻找的最佳码矢量中占据位置p(p＝1，2，...，L)的可能性。最佳码矢量仍然是未知量，本发明的目的就是公开如何从和语音相关的信号中推导出最佳码矢量的一些特征。

按如下方式使用估计矢量B：

首先，估计矢量B作为决定哪个轨迹i或j更易猜测出脉冲位置的基础，以便先处理最易猜测出脉冲位置的轨迹。这一属性经常用在树结构的第一层选择N_m个脉冲的脉冲顺序规则中。

其次，对一给定轨迹，估计矢量B表明了每一有效位置的相对可能性。因为在前几级只有很少的脉冲在选择有效位置时能提供稳定的性能，所以在树结构的前几级用估计矢量代替基本选择准则Q_K(j)作为选择准则更为有利，

从语音相关的信号中得到脉冲位置的似然估计矢量B的这一优选的方法包括计算归一的后向滤波目标矢量D，和归一的基音去除残余矢量信号R′，

的和，从而计算出脉冲位置的似然估计矢量B $B=(1-\mathrm{\β})\frac{D}{\left|\right|D\left|\right|}+\mathrm{\β}\frac{R^{\′}}{\left|\right|R^{\′}\left|\right|}$ ，β为一固定常数，典型值为1/2(依据代数码中的非零脉冲的百分比，β在0，1间取值)。

这里需指出同样的估计矢量B在1995年2月6日提交的共同未决的U.S专利申请No.08/383,968中用于不同的含义和目的。该专利申请是关于发明“快速语音编码的信号选择脉冲幅度代数码书”的专利申请，它公开了一种选择最优或近似最优的脉冲幅度组合的方法。因为非零脉冲的幅度可以假设为q个值中的一个，q＞1，所以该方法在代数码书设计中非常有用。观察发现为了有效地进行语音编码，从信号自身推出好的估计例如B是非常重要的。事实上，除了作为位置或幅度的估计，B也是码矢量A_K自身的估计。因此，任何综合上述共同未决的U.S专利申请No.08/383,968和本专利申请的搜索方法都明显地属于本方法的原则之列。以下是在本发明范围之列的典型组合技术。在本公开材料中早已指出，当两重叠轨迹中的两个或多个脉冲在一帧中位置相同时，两脉冲幅度相加。这种位置幅度折衷可以由格搜索共同优化。

为方便起见，下面给出已定义的常量变量。

常量列表

常数      例值      名称/含义

L         40        帧长(位置数)

N         10        脉冲数

Li        4         轨迹i中可能的位置数

M         5         层数

N_m       2         m层的脉冲数

S_p       -1        位置p的幅度

P_i       13        第i个脉冲的位置

P_i(n)    19        第n个处理脉冲的位置

变量列表符号    取值范围        标准用法p       1-L             帧内的位置号I       1-N             脉冲号m       1-M             子集号n       1-N             处理顺序号i(n)    1-N             第n个处理的脉冲号P_i(n)    1-L             第n个处理的脉冲位置S_p      {±1}           位置p的幅度S_pi(n)   {±1}           第n个脉冲所在位置的幅度

   深度优先搜索实施例

下面是一些深度优先搜索的典型实施例。

搜索技术#1代数码书L＝40；N＝5ISSP(40，5)(即L1＝L2＝＝L5＝8)搜索过程层数m   脉冲数N_m  候选路径    脉冲顺序规则   选择准则1        1          10         R1，R2         B2        2          2          R2             Q_K(2)3        2          2          R2             Q_K(4)规则R1：

第一层路径建立时，依次考虑5个轨迹，对于每一轨迹依次选择使Bp最大化的两个位置中的一个，选择出第一脉冲位置P_i(1)的10条路径。规则R2：

规则2定义了用于第2，3层的4脉冲脉冲顺序函数，将剩余的4个下标排列在一个圆环上，以顺时针顺序从i(1)脉冲(第一层的节点数目)的右面开始重新编号。

称为搜索技术#2的码书搜索的第二个例子能更明确地说明深度优先原则。

搜索技术#2代数码书L＝40；N＝10ISSP(40，10)(即L₁＝L₂＝…L₁₀＝4)搜索过程层数m  脉冲数N_m 候选路径  脉冲顺序规则   选择准则

1    2        9        R3        B

2    2        1        R4        Q_K(4)

3    2        1        R4        Q_K(6)

4    2        1        R4        Q_K(8)

5    2        1        R4        Q_K(10)规则R3：

选择脉冲i(1)，根据能够使对所有的p使Bp取得最大值的原则选择其位置。对于i(2)，在剩余的9个脉冲中依次选择，选择某i(2)的标准是在轨迹内使Bp取最大值。规则R4：

第一层结束后，将剩余的8个下标排成环，以顺时针顺序从i(2)的右面开始重新编号，由此决定出整个脉冲顺序函数。

图5，6说明了搜索技术#2，图5为依据单脉冲交织排列，对于40位置码矢量的10脉冲码书应用深度优先搜索技术#2的树结构；图6为相应流图。

L＝40个位置划分至10个轨迹，每一轨迹与码矢量中N＝10个幅度非零的脉冲关联，10个轨迹依照N个单脉冲排列进行交织。步骤601

计算前文所述的脉冲位置似然估计矢量B。步骤602

计算绝对值最大的估计Bp的位置p。步骤603(开始第一层路径建立操作)

选择脉冲(即轨迹)i(1)和其有效位置以与步骤602中计算出的位置相符合(图5，501)。步骤604(结束第一层路径建立操作)

对于i(2)依次在剩余的9个脉冲选择，选择标准是在所述i(2)的轨迹中使Bp最大的位置。由此产生了9条不同的候选路径(图5中的502)。这些候选路径中的每一条通过后续级的延伸形成了9个不同的码矢量。很明显，第一层的目的就是在B估计的基础上挑选出9个好的脉冲起始对。正是由于此原因，图5中的第一层的路径建立操作被称为“基于信号的脉冲筛选”。步骤605(规则R4)：

为节省计算时间，后续4级的脉冲顺序是预定的。剩余的8个下标排成环，以顺时针顺序从i(2)的右面开始重新编号，从而决出n＝3，4，.......，10的脉冲顺序函数i(n)。依此顺序选出第二层脉冲i(3)、i(4)，选出第三层i(5)、i(6)，依此类推。步骤606，607，608，609(2至5层)

为了获得有效性，设计成了2至5层，即依据相应的选择准则Q_K(2m)，m＝2，3，4，5为层号，对两个脉冲的4个位置的16种组合进行穷举搜索。

因为2至5层每层的路径建立操作仅产生一条候选路径(即分支因子为1)(图5的504)，搜索的复杂度仅随脉冲总数线性增加，故2至5层执行的操作可看作深度优先搜索。树搜索技术在其结构、标准和所处理问题的领域有很大不同，在人工智能领域，通常对“广度优先搜索”和“深度优先搜索”这两类搜索原则进行比较。步骤610：

9条不同的1级候选路径在604步骤产生，在2至5层延伸(步骤605至609)，构成了9个候选码矢量A_K(图5，505)。

步骤610的目的是比较这9个候选矢量A_K，依据最后一层的选择准则，即Q_K(10)，选出最佳码矢量。

下面以第三个码书深度优先搜索的例子“搜索技术3”说明几个脉冲占据相同位置的情况。

搜索技术#3    不超过10个脉冲代数码书L＝40；N＝10      不同脉冲数≤10两个ISSP(40，5)(即L₁＝L₂＝…L₅＝8；L₆＝L₇＝…L₁₀＝8)搜索过程层数m  脉冲数N_m 候选路径  脉冲顺序规则   选则准则1      2        50          R5           B2      2        2           R6           Q_K(4)3      2        2           R6           Q_K(6)

4    2        1    R6        Q_K(8)

5    2        1    R6        Q_K(10)规则R5：

注意两个脉冲占据了相同的位置，它们幅度相加得到一个幅度加倍的脉冲。规则5决定了选择前两个脉冲的位置的方法以提供第一层候选路径集合，第一层候选路径的节点对应于在5个不同轨迹中选出使Bp最大的一个幅度加倍脉冲，及通过在5个轨迹中选出使Bp最大的两位置从10脉冲集合中选出所有两位置的组合。第一层的候选路径有节点。规则R6：类似规则R4

虽然以上对本发明的推荐实施例进行了详细描述，但是在不背离本发明宗旨、在附属专利要求的范围，可对实施例进行任意修改。本发明可以处理语音信号以外的其它声音信号。这些改变保留了本发明的基本原则，显然仍属于本发明范围之列。

Claims (30)

1.一种对声音信号编码时执行码书深度优先搜索的方法，其中：

所述的码书包括一个码矢量A_K的集合，每个码矢量定义了多个不同位置p并且包括N个幅度非零的脉冲，每个脉冲可分配至码矢量的预置有效位置；

所述的深度优先搜索涉及一M有序的树结构，每一级m与N_m个幅度非零的脉冲相关联，N_m为一预置数，N_m＞＝1与所有所述M层相关的所述预置数的和与组成所述码矢量的幅度非零的脉冲数目N相等，树结构的每一层m还涉及一路径建立操作、一给定脉冲顺序规则、一给定的选择准则；

所述的码书深度优先搜索操作包括以下步骤：---在树结构的第一层相关的路径建立操作包括：

根据相应的脉冲顺序规则，所述N个幅度非零的脉冲中选择N₁个脉冲；

根据相应的选择准则，在N₁个幅度非零的脉冲的P个有效位置中选择至少一个有效位置，从而定义至少一个第一层候选路径；---在树结构的m层，相应的路径建立操作是通过延伸(m-1)层的一条候选路径迭代定义了一条m层候选路径，步骤如下：

根据相应的脉冲顺序规则，选择建立m-1级路径时没有选择的幅度非零的N_m个脉冲；

根据相应的选择准则，在这N_m个幅度非零的脉冲中至少选择一个有效位置P，从而定义至少一个m层候选路径；其中源于一条第一层候选路径并在树结构的后续级路径建立中延伸的一条M层候选路径决定了码矢量中N个幅度非零的脉冲的各个的位置P，由此定义了一个候选码矢量A_K。

2.一种声音编码的码书深度优先搜索的方法，其中：

所述的码书由一个码矢量A_K的集合组成，每个码矢量定义了多个不同位置p并且包括N个幅度非零的脉冲组成，其中每个脉冲都分配至码矢量的预效位置P；

所述的深度优先搜索涉及(a)将N个幅度非零的脉冲划分至M个子集，每一子集至少包括一个幅度非零的脉冲，(b)一树结构，其每一节点代表了N个幅度非零的脉冲的有效位置p，该树结构定义了多个搜索级，每一搜索级对应于M个子集中的一个，并有给定的脉冲顺序规则和选择准则；

所述的码书深度优先搜索操作包括以下步骤：---在树结构的第一搜索级，

根据相应的脉冲顺序规则，在N个幅度非零的脉冲中至少选择一个以形成相应子集；

根据相应的选择准则，在所述至少一个幅度非零的脉冲的有效位置p中至少选择一个有效位置以定义至少一条通过树节点的路径；---在树结构的每一后续搜索级

根据相应的脉冲顺序规则，至少选择一个先前未被选择的所述幅度非零的脉冲，以形成相应子集；

根据相应的选择准则，在所述至少有一个幅度非零脉冲的有效位置p的相应子集中至少选择一个有效位置，以延伸至少一条通过树节点的上述路径；

其中在第一搜索级定义并在后续搜索级延伸的每条路径确定了码矢量A_K的N个幅度非零的脉冲的各个位置p，从而在声音编码时构成了一个候选码矢量。

3.权利要求2描述的码书深度优先搜索执行方法，其中所述的至少一条路径包括若干路径，所述的树结构的搜索级包括一最后搜索级，并且其中所述的方法在树结构的最后搜索级包括声音编码时依照相应的选择准则选择所述路径定义的一候选码矢量A_K的步骤。

4.权利要求2描述的码书深度优先搜索执行方法，进一步包括依照至少一个交错单脉冲排列导出N个幅度非零的脉冲的预置有效位置p的步骤。

5.权利要求2描述的码书深度优先搜索执行方法，其中，在树结构的每一所述后续搜索级，所述选择步骤包括：

对于在前搜索级选出的脉冲位置p定义并且由所述搜索级对应的至少有一个脉冲的子集的每一有效位置p延伸的每条路径，计算一给定的算术比值；

保留使所述比值取最大值的脉冲位置p定义的延伸路径。

6.权利要求2描述的码书深度优先搜索执行方法，其中，在树结构的第一搜索级，选择步骤如下：及

计算声音信号的脉冲位置似然估计矢量；

依照所述的脉冲位置似然估计矢量选择所述相应子集的至少一个幅度非零的脉冲，及其至少一个有效位置p。

7.权利要求6描述的码书深度优先搜索执行方法，其中计算脉冲位置似然估计矢量的步骤包括：

处理声音信号，产生一目标信号X，一后向滤波目标信号D，一基音去除残余信号R’；

计算脉冲位置似然估计矢量以响应至少一个所述目标信号X、后向滤波目标信号D及基音去除残余信号R′中。

8.权利要求7描述的码书深度优先搜索执行方法，其中计算脉冲位置似然估计矢量以响应至少一个所述目标信号X、后向滤波目标信号D、基音去除残余信号R′中的步骤包括：

对后向滤波目标信号D的归一化值 与基音去除残余信号R′的归一化值

求和，得到脉冲位置似然估计矢量B： $B=(1-\mathrm{\β})\frac{D}{\left|\right|D\left|\right|}+\mathrm{\β}\frac{R^{\′}}{\left|\right|R^{\′}\left|\right|},$ β为一固定常数。

9.权利要求8描述的码书深度优先搜索执行方法，其中β是0，1间取值的固定常数。

10.权利要求9描述的码书深度优先搜索执行方法，其中β是值为1/2的固定常数。

11.权利要求2描述的码书深度优先搜索执行方法，其中所述的N个幅度非零的脉冲有各自的下标，并且其中在树结构的所述后续搜索级，依照相应的脉冲顺序规则选出至少一个先前未选出的幅度非零的脉冲的步骤包括：将先前未选出的脉冲的下标排成环状，依照顺时针顺序，从上一级选出的最后一个幅度非零的脉冲的右面开始，选出所述至少一个幅度非零的脉冲。12对声音信号进行编码时执行码书深度优先搜索的装置，其中：

所述码书由一个码矢量A_K的集合组成，每个码矢量定义了多个不同位置p并且包括N个幅度非零的脉冲组成，其中每个脉冲都分配至码矢量的预置有效位置P；

所述深度优先搜索涉及(a)将N个幅度非零的脉冲划分至M个子集，每一子集包括至少一个幅度非零的脉冲，(b)一树结构，每一节点代表了N个幅度非零的脉冲的有效位置p，该树结构定义了多个搜索级，每一搜索级与M个子集中的一个对应，并有自己的脉冲顺序规则和选择准则；

所述码书深度优先搜索装置包括：---对于树结构的第一搜索级，

第一装置，根据相应的脉冲顺序规则，在N个幅度非零的脉冲中至少选择一个以形成相应子集；

第一装置，根据相应的选择准则，在所述至少一个幅度非零的脉冲的有效位置p中选择至少一个有效位置以定义至少一条通过树节点的路径；---对于树结构的每一后续搜索级，

第二装置，根据相应的脉冲顺序规则，选择至少一个先前未被选择的所述幅度非零的脉冲，以形成相应子集；

第二装置，后续搜索级根据相应的选择准则，在所述至少有一个幅度非零脉冲的有效位置p的相应子集中选择至少一个有效位置，延伸至少一条通过树节点的所述路径；其中在第一搜索级定义并在后续搜索级延伸的每条路径确定了码矢量A_K的N个幅度非零的脉冲的各个位置p，从而在声音编码时构成了一个候选码矢量。

13..权利要求12描述的执行码书深度优先搜索的装置，其中所述的至少一条路径包括若干路径，所述的树结构的搜索级包括一最后搜索级，并且所述的装置包括对声音进行编码时在树结构的最后搜索级及依照相应的选择准则选择由所述路径定义的一候选码矢量A_K的装置。

14.权利要求12描述的执行码书深度优先搜索装置，进一步包括依照至少一个交错单脉冲排列导出N个幅度非零的脉冲的预置有效位置p的装置。

15.权利要求12描述的执行码书深度优先搜索装置，其中所述的第二装置包括：

对由前搜索级选出的脉冲位置p所定义的并且由所述搜索级关联的至少有一个脉冲的子集的每一有效位置P所延伸的每条路径计算一给定的算术比值的装置；

保留使所述比值取最大值的脉冲位置p所定义的延伸路径的装置。

16.权利要求12描述的执行码书深度优先搜索方法装置，其中第一挑选装置和第一选择装置包括：

计算声音信号的脉冲位置似然估计矢量的装置；

依照所述的脉冲位置似然估计矢量选择所述相应子集的至少一个幅度非零RN SYP脉冲，及其至少一个有效位置p的装置。

17.权利要求16描述的执行码书深度优先搜索装置，其中所述计算脉冲位置似然估计矢量的装置包括：

处理声音信号，产生目标信号X，后向滤波目标信号D，基音去除残余信号R’的装置；

计算脉冲位置似然估计矢量以响应所述目标信号X、后向滤波目标信号D、基音去除残余信号R′中的至少一个信号的装置。

18.权利要求17描述的执行码书深度优先搜索装置，其中所述计算脉冲位置似然估计矢量以响应所述目标信号X、后向滤波目标信号D、基音去除残余信号R′中的至少一个信号的装置包括：

对后向滤波目标信号D的归一化值

与基音去除残余信号R′的归一化值

求和，得到脉冲位置似然估计矢量B装置； $B=(1-\mathrm{\β})\frac{D}{\left|\right|D\left|\right|}$ $\frac{R^{\′}}{\left|\right|R^{\′}\left|\right|}$ β为一固定常数。

19.权利要求18描述的执行码书深度优先搜索装置，其中β是0，1间取值的固定常数。

20.权利要求19描述的执行码书深度优先搜索装置，其中β是值为1/2的固定常数。

21.权利要求12描述的执行码书深度优先搜索装置，所述的N个幅度非零的脉冲有各自的下标，其中所述第二装置包括：

将先前未选出的脉冲的下标排成环的装置；

依照顺时针顺序，从上一级选出的最后一个幅度非零的脉冲的右面开始，选出至少一个幅度非零的脉冲的装置。

22.服务于已被分为若干蜂窝的大片地理区域的蜂窝通信系统，它包括：

移动发射/接收单元；

位于所述各蜂窝的蜂窝基站；

蜂窝基站间进行通信控制的设备；

蜂窝内的每一移动用户和该区域的基站进行双向无线通信的子系统，在移动单元和蜂窝基站中所述双向无线通信子系统包括：(a)包括进行语音编码的装置和传输编码的语音信号的装置的发射机，(b)包括接收编码后信号及对接收信号解码的装置的接收机；其中的语音信号编码装置包括在对语音信号进行编码时进行码书深度优先搜索的模块，其中：

所述码书由码矢量A_K的一个集合组成，每个定义了多个不同位置p并且包括N个幅度非零的脉冲组成，其中每个脉冲都分配至码矢量的预定有效位置P

所述深度优先搜索涉及(a)将N个幅度非零的脉冲划分至M个子集，每一子集至少包括一个幅度非零的脉冲，(b)一树结构，每一节点代表了N个幅度非零的脉冲的有效位置p，该树结构定义了多个搜索级，每一搜索级与M个子集中的一个对应，还有自己的脉冲顺序规则和选择准则；

所述码书深度优先搜索装置包括：---对于树结构的第一搜索级，

第一装置，根据相应的脉冲顺序规则，在N个幅度非零的脉冲中选择至少一个以形成相应子集；

第一装置，根据相应的选择准则，在所述至少一个幅度非零的脉冲的有效位置p中选择至少一个有效位置以定义至少一条通过树节点的路径；---对于树结构的每一后续搜索级

第二装置，根据相应的脉冲顺序规则，选择至少一个先前未被选择的所述幅度非零的脉冲，以形成相应子集；

第二装置，后续搜索级根据相应的选择准则，在所述至少有一个幅度非零脉冲的有效位置p的相应子集中选择至少一个有效位置，以延伸至少一条通过树节点的所述路径；其中在第一搜索级定义并在后续搜索级延伸的每条路径决定了码矢量A_K的N个幅度非零的脉冲的各个位置p，从而在声音编码时构成了一个候选码矢量。

23..权利要求22描述的蜂窝通信系统，其中所述的至少一条路径包括若干路径，其中所述的树结构的搜索级包括一最后搜索级，并且所述的装置包括对声音进行编码时在树结构的最后搜索级及依照相应的选择准则选择由所述路径定义的一候选码矢量A_K的装置。

24.权利要求22描述的蜂窝通信系统，进一步包括依照至少一个交错单脉冲排列推导出N个幅度非零的脉冲的预置有效位置p的装置。

25.权利要求22描述的蜂窝通信系统，所述的二级选择装置包括：

对由前搜索级选出的脉冲位置p所定义的并且由所述搜索级关联的至少有一个脉冲的子集的每一有效位置P所延伸的每条路径计算一给定的算术比值的装置；

保留使所述比值取最大值的脉冲位置p所定义的延伸路径的装置。

26.权利要求22描述的蜂窝通信系统，其中第一挑选装置和第一选择装置包括：

计算声音信号的脉冲位置似然估计矢量的装置；

依照所述的脉冲位置似然估计矢量选择所述相应子集的至少一个幅度非零的脉冲，及其至少选择一个有效位置p的装置。

27.权利要求26描述的蜂窝通信系统，其中所述计算脉冲位置似然估计矢量的装置包括：

处理声音信号，产生目标信号X，后向滤波目标信号D，基音去除残余信号R’的装置；

计算脉冲位置似然估计矢量以响应所述目标信号X、后向滤波目标信号D、基音去除残余信号R′中的至少一个信号的装置。

28.权利要求27描述的执行码书深度优先搜索装置，其中所述计算脉冲位置似然估计矢量以响应所述目标信号X、后向滤波目标信号D、基音去除残余信号R′中的至少一个信号的装置包括：

对后向滤波目标信号D的归一化值 与基音去除残余信号R′的归一化值

求和，得到脉冲位置似然估计矢量B的装置； $B=(1-\mathrm{\β})\frac{D}{\left|\right|D\left|\right|}+\mathrm{\β}\frac{R^{\′}}{\left|\right|R^{\′}\left|\right|},$ β为一固定常数。

29.权利要求28描述的蜂窝通信系统，其中β是0，1间取值的固定常数。

30.权利要求29描述的蜂窝通信系统，其中β是值为1/2的固定常数。

31.权利要求22描述的执行码书深度优先搜索装置，所述的N个幅度非零的脉冲有各自的下标，所述二级选择装置包括：

将先前未选出的脉冲的下标排成环的装置；

依照顺时针顺序，从上一级选出的最后一个幅度非零的脉冲的右面开始，选出至少一个幅度非零的脉冲的装置。

Images