CN102144256B - 用于针对矢量量化器的快速最近邻搜索的方法和设备 - Google Patents

Abstract

一种方法，包括从具有一个或多个码矢量的码书C中标识码矢量的分量k，该分量k针对输入矢量引入最高方差；允许在码书C中对码矢量进行排序；以及使用经排序的码矢量搜索输入矢量的最佳匹配矢量。

Description

用于针对矢量量化器的快速最近邻搜索的方法和设备

技术领域

本发明涉及音频数据的编码和解码。特别地，本发明涉及针对矢量量化器的最近邻快速搜索。

背景技术

本部分旨在为权利要求书中陈述的本发明提供背景或上下文。在此的描述可能包括可以探究的概念，但不一定是那些之前已经想到或者探究的概念。因此，除非在此指出，否则在本部分中描述的内容对于本申请的说明书和权利要求书而言不是现有技术，并且并不因为包括在本部分中就被认为是现有技术。

量化是有损信号压缩的主要工具之一。量化过程包括针对给定输入数据找到接近的表示，该表示将使得利用较少的比特对数据进行存储和传输。可以将量化函数写作f：D＞C，其中D是输入空间并且C是表示集合或码书。对于来自于D的给定输入，从C选择表示或码书，从而在整个码书上最小化了输入和表示之间的给定失真测量值。找到最小化失真测量值的码书的过程通常称作最近邻搜索。

如果输入空间以及码书是一维的，则量化称作标量量化；否则其被称作矢量量化。在矢量量化的情况中，表示也称作码矢量。

码书Cc的基数小于输入空间的基数，这允许以较少的比特表示输入数据。在码书中，最近邻码字的索引可以表示为log₂Cc比特。如果利用同样数量的比特来表示所有码字，则量化率是R＝每个采样log₂Cc/K比特，其中K是数据维度。

通常，最近邻搜索包括针对每个码字的失真测量值的评估，尤其对于矢量量化情况而言，从计算的观点来看这可能是非常昂贵的。已经提出了各种快速最近邻算法，它们基于停止评估的一个或多个条件而减少了失真评估的数量。

矢量量化是信号处理应用中广泛使用的工具，其中应用例如是采用话音/音频、图像或视频编码的应用。

发明内容

在本发明的一个方面中，一种方法包括：从具有一个或多个码矢量的码书C中标识码矢量的分量k；以及允许基于分量k来对所述码书C中的码矢量进行排序，从而促进使用经排序的码矢量来搜索输入矢量的最佳匹配矢量。

在一个实施方式中，将所述分量k标识为针对输入矢量引入最高方差。

在一个实施方式中，允许对码矢量进行排序包括根据分量k对所述码书C中的码矢量进行排序。在另一实施方式中，允许对码矢量进行排序包括提供映射函数以形成所述码书C的码矢量索引。

在另一方面中，一种方法包括使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量，其中基于所述码矢量的分量k来对所述码矢量进行排序，其中所述搜索包括在执行考虑所述输入矢量的分量k的二分搜索；以及执行考虑全码矢量的修改的部分失真搜索。可以以升序对所述码矢量进行排序并且执行所述二分搜索可以找到满足以下条件的具有最小索引j的矢量：

X_k＜C_j，k，

其中X是所述输入矢量并且C’是所述经排序的码矢量。

在一个实施方式中，执行所述修改的部分失真搜索包括执行开始于索引j-1的向下搜索；以及执行开始于索引j的向上搜索。可以在找到以下码矢量时终止所述向下搜索，所述码矢量导致比提供所述最佳匹配的当时(then-current)码矢量更大的分量k的失真。可以在找到以下码矢量时终止所述向上搜索，所述码矢量导致比提供所述最佳匹配的当时码矢量更大的分量k的失真。

在一个实施方式中，所述方法还包括在终止所述向上搜索和所述向下搜索两者时选择码矢量作为搜索最佳匹配的输出。

在本发明的另一方面中，一种装置，包括解码器，被配置用于从具有一个或多个码矢量的码书C中标识码矢量的分量k，所述分量k引入输入矢量的最高方差；以及允许基于分量k来对所述码书C中的码矢量进行排序，从而促进使用经排序的码矢量来搜索输入矢量的最佳匹配矢量。

在另一方面中，一种装置包括解码器，被配置用于使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量，其中基于所述码矢量的分量k来对所述码矢量进行排序，其中所述解码器被配置用于通过以下操作进行搜索：执行仅考虑所述输入矢量的分量k的二分搜索；以及执行考虑全码矢量的修改的部分失真搜索。

在另一方面中，一种装置包括处理器和通信地连接至所述处理器的存储器单元。所述存储器单元包括用于从具有一个或多个码矢量的码书C中标识码矢量的分量k的计算机代码，所述分量k引入输入矢量的最高方差；以及用于允许基于分量k来对所述码书C中的码矢量进行排序从而促进使用经排序的码矢量来搜索输入矢量的最佳匹配矢量的计算机代码。

在另一方面中，一种装置包括处理器和通信地连接至所述处理器的存储器单元。所述存储器单元包括用于使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量的计算机代码，其中基于所述码矢量的分量k来对所述码矢量进行排序，其中用于搜索的计算机代码包括用于执行仅考虑所述输入矢量的分量k的二分搜索的计算机代码；以及用于执行考虑全码矢量的修改的部分失真搜索的计算机代码。

在另一方面中，本发明涉及一种包含在计算机可读介质上的计算机程序产品。所述计算机程序产品包括用于从具有一个或多个码矢量的码书C中标识码矢量的分量k的计算机代码，所述分量k引入输入矢量的最高方差；以及用于允许基于分量k来对所述码书C中的码矢量进行排序从而促进使用经排序的码矢量来搜索输入矢量的最佳匹配矢量的计算机代码。

在另一方面中，本发明涉及一种包含在计算机可读介质上的计算机程序产品。所述计算机程序产品包括用于使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量的计算机代码，其中基于所述码矢量的分量k来对所述码矢量进行排序，其中用于搜索的计算机代码包括用于执行仅考虑所述输入矢量的分量k的二分搜索的计算机代码；以及用于执行考虑全码矢量的修改的部分失真搜索的计算机代码。

在另一方面中，本发明涉及一种用于处理音频数据的设备，包括：用于使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量的装置，其中基于所述码矢量的分量k来对所述码矢量进行排序，其中用于搜索的装置包括：用于执行仅考虑所述输入矢量的分量k的二分搜索的装置；以及用于执行考虑全码矢量的修改的部分失真搜索的装置。

在结合附图时，根据以下的详细描述，本发明各种实施方式的这些和其他优点与特征，连同其组织和操作方式都将变得明显。

附图说明

通过参考附图来描述本发明的示例实施方式，在附图中：

图1是示出了根据本发明实施方式的示例码字搜索方法的流程图；

图2是示出了根据本发明实施方式的、用于针对图1的码字搜索方法搜索最佳匹配的示例方法的流程图；

图3是可以在其中实现本发明各种实施方式的系统的概览图；

图4示出了根据本发明各种实施方式的、可以利用的示例电子设备的透视图；

图5是可以包括在图4的电子设备中的电路的示意图；以及

图6是可以在其中实现各种实施方式的通用多媒体通信系统的图示。

具体实施方式

在以下描述中，出于解释而非限制的目的，记载了细节和描述，从而提供对本发明的透彻理解。然而，本领域的技术人员应该理解，本发明可以在偏离这些细节和描述的其他实施方式中实现。

即使在失真率方面可以将非约束矢量量化器的性能视为是良好的，但如果复杂度要求受限则编码复杂度也可以禁止其使用。本发明的实施方式提供了一种降低矢量量化编码复杂度而不增加任何存储器或编码失真的方法。

在文献中已经广泛研究了快速最近邻搜索的问题。存在针对矢量量化器的若干类型的快速最近邻搜索，例如将它们称作(a)部分失真方法、(b)三角不等式方法以及(c)投影方法。还存在使用对码书的不同排序的各种方法。

本发明的实施方式提供用于一般性矢量码书中的最近邻搜索的低复杂度方法。与传统解决方案相反，本发明的实施方式不需要补充存储器存储来用于辅助变量。根据本发明实施方式的快速搜索在以下意义上是最佳的，即其保证获得输入的最近邻居。对于增益值和频率分量幅度的量化的示例性应用而言，其中增益值和频率分量幅度从例如ITU-T G.718和G.729.1编解码器的超宽带扩展的上下文中的音频输入数据段中提取，根据本发明实施方式的方法相对于全搜索可以将复杂度降低到八分之一并且相对于部分失真方法可以将复杂度降低到三分之一。本发明的实施方式利用根据所选矢量分量的值排序的码书，例如所选矢量分量在码书的码矢量的分量中具有最高方差。给定输入矢量，针对已排序的分量来执行二分搜索，并且开始于码书中的终局点(resulting point)，将修改的部分失真方法用于在初始点邻居中的搜索。使用码矢量分量之一使得初始二分搜索能够直接针对标量值，而不像现有技术的方法需要任何附加的存储器。由于相对于一个分量的失真仅同样进入矢量失真测量中，所以可以将其传统地用作搜索停止指示符，而不再检查码书的所有码矢量。

根据本发明的某些实施方式，采用针对矢量分量k的值排序的N歌码矢量的K维码书。分量k可以是在码书C的码矢量内引入最大方差的矢量分量。

在某些实施方式中，可以以不同的方式选择用作对码书C的码矢量进行排序的基础的分量k的选择。在一个实施方式中，可以在码矢量的分量中随机地选择分量k。此外，例如在一个实施方式中，利用码书搜索中的经加权失真测量，可以将具有最大权重的分量选作将用作排序基础的分量k。在又一实施方式中，分量的方差和加权可以在选择矢量分量k时考虑。在其他实施方式中，可以将对失真具有最大敏感度的矢量分量选作将用作排序码书的基础的分量k。

在一个实施方式中，给定来自于R^K空间的输入矢量X，即每个矢量K个元素的实值矢量的集合，在根据渐增的分量k的值排序的码书C中执行考虑分量k的值的二分搜索。获取具有分量k的最大值的矢量的索引I，其中分量k的最大值仍旧小于或等于输入矢量X的相应分量，从而

C_I，k≤X_k＜C_I+1，k

其中C_I，k表示具有索引I的码矢量的分量k。应该指出，在另一示例实施方式中，可以根据分量k的降序对码书C进行排序。在该情况中，将二分搜索用于找到具有分量k的最小值的码书矢量的索引，其中分量k的最小值仍旧大于输入矢量X的相应分量，即：

C_I，k＞X_k≥C_I+1，k。

部分失真方法的原理是：如果针对矢量分量的子集(例如，针对一定数量的码矢量的第一分量)计算的失真已经大于当前最小失真，则停止对给定码矢量的失真的评估。如上所述，如果仅针对矢量分量k计算的部分失真大于当前最小失真，则通过完全停止搜索并且选择导致当前最小失真的码矢量作为输出矢量来修改部分失真方法。这是可能的，因为在一个实施方式中，根据分量k的值的升序对码书进行排序，这暗示了C_n，k＜＝C_n +1，k对所有0＜n＜N的值都成立。因此，在考虑具有开始于I+1的索引值的码矢量的向上搜索中，一旦第一矢量m_u的分量k引入高于当前最小失真的失真就停止向上，因为对码书的排序确保了具有I＞m_u的索引值的所有码矢量将在仅考虑分量k时引入甚至更高的失真。以类似的方式，在考虑开始于索引I的码矢量的向下搜索中，一旦第一矢量m_d的分量k引入高于当前最小失真的失真就可以停止向下，因为根据分量k的值的升序排序的码书确保了具有I＜m_d的索引值的码矢量将在仅考虑分量k时引入甚至更高的失真。

向上搜索和向下搜索过程以及停止条件在以下示例实施方式中也是类似的，该示例实施方式采用具有根据分量k的值的降序进行排序的码矢量的码书。

在采用根据分量k的值的升序排序的码书的实施方式中，如果X_K大于任何码矢量中的分量k，则修改的部分失真搜索从最后的码矢量向下执行。因此，在该情况中，仅执行向下搜索。如果X_K小于任何码矢量中的分量k，则从第一码矢量向上执行修改的部分失真搜索。因此，仅执行向上搜索。如果码书包含这两种码矢量，一种具有其值小于X_K的分量k以及一种具有其值大于X_K的分量k，则修改的部分失真搜索在向上和向下二者中均执行。

在采用根据分量k的值的降序排序的码书的实施方式中，在任何码矢量中大于分量k的X_K导致仅执行向上搜索。以类似的方式，在任何码矢量中小于分量k的X_K导致仅执行向下搜索。

在某些实施方式中，可以从概念上将码书划分为两个或更多子码书，并且根据分量k的排序针对子码书中的每个来独立执行。在搜索阶段中，如果向上搜索和向下搜索适用于给定的输入矢量，则涉及向上搜索和向下搜索两者的过程针对子码书中的每个来独立执行，并且针对子码书中的每个来选择中间输出矢量。最终输出矢量是在子码书的中间输出矢量中提供最小失真的那个。

在采用使用两个或更多概念上的子码书的排序和搜索过程的又一实施方式中，排序和搜索可以基于不同矢量分量来执行。例如，矢量分量k₁可以用于对第一子码书进行排序，并且矢量分量k₂可以用于对第二子码书进行排序。

在某些实施方式中，可以在排序和/或搜索中仅考虑全码书的一部分。

现在参考图1，图1示出了根据本发明实施方式的用于码字搜索的示例过程200。在框202，过程200找到在码书C’内引入最高方差的码矢量的分量k。分量k继而用于对码书C’中的矢量进行排序(框204)。接下来，根据本发明的实施方式，允许对码书中的码矢量进行排序。根据图1示出的示例性实施方式，这通过将矢量排序为例如矢量分量k的值的升序或降序以形成码书C来实现。然后，将经排序的码书C用于搜索输入矢量X的最佳匹配(框206)。

在另一实施方式中，码书C’无需排序。反之，对码书中的码矢量排序可以通过映射函数以形成码书C’的码矢量索引来实现，这创建了C中的码矢量的顺序。因此，可以将具有映射函数的现有码书用于支持使用根据本发明的实施方式的搜索方法。

在图2中示出了用于搜索框206的最佳匹配的示例性方法。当从经排序的码书C搜索输入矢量X的最佳匹配时，在框208，首先，仅考虑输入矢量的分量k和码书来执行二分搜索，以找到具有大于矢量分量k的X_K的值的第一码矢量C_j。因此，找到了满足条件X_k＜C_j，k的具有最小索引j的码矢量。

在框210，考虑开始于上面找到的索引j的全码矢量来执行修改的部分失真搜索：向下搜索考虑具有索引j-1、j-2、j-3的码矢量，依次类推。以类似的方式，向上搜索考虑具有索引j、j+1、j+2的码矢量，依次类推。在向下搜索中(框212)，一旦遇到具有以下分量k的第一码矢量就终止向下搜索并且开始向上搜索，其中该分量k引入大于在全矢量上计算的当前最小失真的失真。在向上搜索中(框214)，一旦遇到具有以下分量k的第一码矢量就完成了搜索并且将提供最小失真的码矢量选作搜索的输出，其中该分量k引入大于在全矢量上计算的当前最小失真的失真。

以下C代码表示提供所述方法的实施方式的实现。在该示例中，针对第一分量对码书进行排序。

可以将经加权的每秒百万操作(WMOPS)方面的复杂度与部分失真方法和全搜索方法进行比较。针对使用相同输入数据的所有非结构化矢量量化器在每帧值中估计该复杂度。

全搜索	部分失真	本发明的实施方式
			5.89WMOPS	2.61WMOPS	0.79WMOPS

因此，本发明的实施方式提供了大量降低的计算复杂度而没有引入附加的存储器需求。

图3示出了本发明可以在其中使用的系统10，包括可以通过一个或多个网络进行通信的多个通信设备。系统10可以包括有线或无线网络的任意组合，其中这些网络包括但不限于移动电话网络、无线局域网(LAN)、蓝牙个域网、以太网LAN、令牌环LAN、广域网、因特网等。系统10可以包括有线通信设备和无线通信设备两者。

例如，图3中所示系统10包括移动电话网络11和因特网28。通往因特网28的连接可以包括但不限于远程无线连接、短程无线连接，以及各种有线连接，有线连接包括但不限于电话线、电缆线路、电力线等。

系统10的示例性通信设备可以包括但不限于移动电话、组合式个人数字助理(PDA)形式的电子设备12、以及移动电话14、PDA16、集成消息传递设备(IMD)18、台式计算机20，笔记本计算机22等。通信设备可以是固定的或者在由行进中的人携带时是移动的。通信设备还可以处于交通模式中，包括但不限于汽车、卡车、出租车、公共汽车、火车、船、飞机、自行车、摩托车等。通信设备的一些或全部可以通过通往基站24的无线连接25发送和接收呼叫和消息，并且通过通往基站24的无线连接25与服务提供商进行通信。基站24可以连接至网络服务器26，该服务器26允许移动电话网络11和因特网28之间的通信。系统10可以包括附加的通信设备和不同类型的通信设备。

通信设备可以使用各种传输技术进行通信，包括但不限于，码分多址(CDMA)、全球移动通信系统(GSM)、通用移动通信系统(UMTS)、时分多址(TDMA)、频分多址(FDMA)、传输控制协议/因特网协议(TCP/IP)、短消息传递服务(SMS)、多媒体消息传递服务(MMS)、电子邮件、即时消息传递服务(IMS)、蓝牙、IEEE 802.11等。实现本发明各种实施方式中所涉及的通信设备可以使用各种介质进行通信，包括但不限于无线电、红外、激光、线缆连接等。

图4和图5示出了可以用作根据本发明各种实施方式的网络节点的典型电子设备28。然而，应当理解，本发明的范围不旨在限于一种特定类型的设备。图4和图5的电子设备28包括外壳30、液晶显示器形式的显示器32、小键盘34、麦克风36、耳机38、电池40、红外端口42、天线44、根据一个实施方式的UICC形式的智能卡46、读卡器48、无线电接口电路52、编解码器电路54、控制器56以及存储器58。根据本发明的各种实施方式，上述组件使得电子设备28能够向/从可以驻留在网络中的其他设备发送/接收各种消息。单独的电路和元件可以是本领域公知的所有类型，例如Nokia范围内的移动电话系列。

图6是可以在其中实现本发明的通用多媒体通信系统的图示。如图6所示，数据源100以模拟、未压缩数字式、或压缩数字格式或这些格式的任意组合提供源信号。编码器110将源信号编码成已编码媒体比特流。应该理解，可以从位于实际任何类型网络内的远程设备直接或间接地接收将解码的比特流。此外，比特流可以从本地硬件或软件接收。编码器110能够对多于一个的媒体类型(诸如，音频和视频)进行编码，或者可能需要多于一个的编码器110以对源信号的不同媒体类型进行编码。编码器110还可以得到合成产生的输入，诸如图形和文本，或者其能够产生合成媒体的已编码比特流。在下文中，仅考虑对一个媒体类型的一个已编码媒体比特流进行处理，以便简化描述。然而，应当注意的是，通常实时广播服务包括若干流(通常，至少一个音频、视频和文本字幕流)。还应当注意的是，系统可以包括很多编码器，但是在图6中，不失一般性地，仅考虑一个编码器110，以简化描述。还应该理解，尽管此处包含的文本和示例可以具体地描述编码过程，但是本领域的技术人员应该理解相同的概念和原理也应用于相应的解码过程，并且反之亦然。

已编码媒体比特流传输至存储设备120。存储设备120可以包括任何类型的海量存储器，以存储已编码的媒体比特流。存储设备120中已编码媒体比特流的格式可以是基本自包含(elementaryself-contained)比特流格式，或者一个或多个已编码比特流可以封装至容器文件中。某些系统“直播”操作，即，省略存储设备，而直接将已编码媒体比特流直接从编码器110传输至发送器130。已编码媒体比特流随后传输至发送器130，根据需要，也称为服务器。在传输中使用的格式可以是基本自包含的比特流格式、分组流格式，或者一个或多个已编码媒体比特流可以封装至容器文件中。编码器110、存储设备120和服务器130可以位于同一物理设备中，或者它们可以包括在单独的设备中。编码器110和服务器130可以利用直播实时内容进行操作，在该情况下，已编码媒体比特流通常不会永久存储，而是在内容编码器110和/或服务器130中缓冲一小段时间，以平滑处理延迟、传输延迟和已编码媒体比特速率的变化。

服务器130使用通信协议栈来发送已编码媒体比特流。栈可以包括但不限于实时传输协议(RTP)、用户数据报协议(UDP)和因特网协议(IP)。当通信协议栈是面向分组的时候，服务器130将已编码媒体比特流封装至分组中。例如，当使用RTP时，服务器130根据RTP净荷格式将已编码媒体比特流封装至RTP分组中。通常，每个媒体类型具有专用RTP净荷格式。再次需要注意，系统可以包含多于一个的服务器130，但是为了简化，以下描述仅考虑一个服务器130。

服务器130可以或可以不通过通信网络连接至网关140。网关140可以执行不同类型的功能，诸如将根据一个通信协议栈的分组流转译成另一通信协议栈、合并以及分流数据流，以及根据下行链路和/或接收器的能力操纵数据流，诸如控制根据流行的下行链路网络条件控制转发的比特流的比特速率。网关140的示例包括MCU、电路交换和分组交换视频电话之间的网关、一键通话(PoC)服务器、手持数字视频广播(DVB-H)系统的IP封装器，或者将本地广播传输转发到家庭无线网络的机顶盒。当使用RTP时，网关140被称为RTP混合器或RTP转译器，并且通常作为RTP连接的端点。

系统包括一个或多个接收器150，它们一般能够对传输的信号进行接收、解调并且将其解封装成编码媒体比特流。编码媒体比特流被传送到记录存储设备155。记录存储设备155可以包括存储编码媒体比特流的任意类型的大容量存储器。作为替换或另外地，记录存储设备155可以包括诸如随机访问存储器之类的计算存储器。记录存储设备155中的编码媒体比特流的格式可以是基本的自包含比特流的格式，或者一个或多个编码媒体比特流可以被封装到一个容器文件中。如果存在多个编码媒体比特流，比如相互关联的音频流和视频流，则一般使用容器文件并且接收器150包括或连结到容器文件生成器，该容器文件生成器从输入流中产生容器文件。一些系统“直播”操作，即省略记录存储设备155，直接从接收器150向解码器160传送编码媒体比特流。在一些系统中，记录存储设备155中只保存被记录流的最近的部分，例如被记录流的最近10分钟摘录，而任何更早的记录数据从记录存储设备155中被丢弃。

编码媒体比特流从记录存储设备155传送到解码器160。如果存在许多编码媒体比特流，比如相互关联且被封装到容器文件中的音频流和视频流，则文件解析器(图中未示出)被用来从容器文件中解封装每一个编码媒体比特流。记录存储设备155或解码器160可以包括文件解析器，或者该文件解析器附接到记录存储设备155或解码器160。

一般来说，编码媒体比特流被解码器160进一步处理，解码器160的输出是一个或多个未压缩的媒体流。最后，呈现器170例如可以用扬声器或显示器来再现该未压缩的媒体流。接收器150、记录存储设备155、解码器160和呈现器170可以驻留在同一物理设备中，或者它们可以被包含在单独的设备中。

根据各种实施方式的发送器130可以被配置用于为了多个原因而选择若干传输层，比如用以响应接收器150的请求或者在其上传播比特流的网络的普遍条件。例如，来自接收器的请求可以是显示层的改变请求，或者与之前设备相比具有不同能力的呈现设备的改变请求。

这里描述的各个实施方式是在通用的方法步骤或处理的上下文中描述的，并且在一个实施方式中，所述步骤或处理可以由计算机程序产品来实施，其中，所述计算机程序产品包含在接收器可读介质中，并且包含了诸如程序代码之类的由联网环境中的计算机执行的指令。计算机可读介质可以包括可移动或不可移动的存储设备，包括但不限于只读存储器(ROM)、随机访问存储器(RAM)、紧凑磁盘(CD)、数字万用磁盘(DVD)等等。通常，程序模块可以包括用于执行特定任务或是实施特定抽象数据类型的例程、程序、对象、组件、数据结构等等。计算机可执行指令、相关联的数据结构以及程序模块代表用于执行这里公开的方法步骤的程序代码的示例。这些可执行指令或相关联的数据结构的特定序列代表的是用于实施在此类步骤或处理中描述的功能的相应动作的示例。

本发明的实施方式可以在软件、硬件、应用逻辑或软件、硬件和应用逻辑的结合中来实施。软件、应用逻辑和/或硬件例如可以驻留在芯片组、移动设备、台式计算机、膝上型计算机或服务器上。各种实施方式的软件和Web实施可以用标准编程技术来完成，这些编程技术具有用以实现各种数据库搜索步骤或处理、相关步骤或处理、比较步骤或处理和判决步骤或处理的其他逻辑以及基于规则的逻辑。各种实施方式也可以全部或部分地在网络元件或模块之内实施。应当注意，在这里和下述权利要求中使用的字眼“组件”和“模块”旨在涵盖使用一行或多行软件码的实施、和/或硬件实施、和/或用于接收人工输入的设备。

已经出于图示和描述的目的而呈现若干实施方式的前文描述。前文描述本意并非在于穷举本发明的实施方式或是将本发明的实施方式限于所公开的精确形式，并且修改和变化根据上述教导是可能的或者可以从各个实施方式的实践中得以获悉。选择和描述在此论述的实施方式以便解释各个实施方式的原理和本质及其实际应用，从而使本领域技术人员能够在各种实施方式中并且以与设想的实际应用适应的各种修改来利用本发明。在此描述的各个实施方式的特征可以结合在方法、装置、模块、系统和计算机程序产品的所有可能组合中。

Claims (18)

1.一种用于处理音频数据的方法，包括：

使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量，其中基于所述码矢量的分量k来以升序对所述码矢量进行排序，其中所述搜索包括：

执行仅考虑所述输入矢量的分量k的二分搜索；以及

执行考虑全码矢量的修改的部分失真搜索。

2.根据权利要求1所述的方法，其中执行所述二分搜索找到满足以下条件的具有最小索引j的矢量：

X_k＜C_j，k，

其中X是所述输入矢量并且C是所述经排序的码矢量。

3.根据权利要求2所述的方法，其中执行所述修改的部分失真搜索包括：

执行开始于索引j-1的向下搜索；以及

执行开始于索引j的向上搜索。

4.根据权利要求3所述的方法，其中在找到以下码矢量时终止所述向下搜索，所述码矢量导致比提供所述最佳匹配的当时码矢量更大的分量k的失真。

5.根据权利要求3所述的方法，其中在找到以下码矢量时终止所述向上搜索，所述码矢量导致比提供所述最佳匹配的当时码矢量更大的分量k的失真。

6.根据权利要求3所述的方法，还包括：

在终止所述向上搜索和所述向下搜索两者时选择码矢量作为所述最佳匹配矢量。

7.一种用于处理音频数据的装置，包括：

编码器，被配置用于：

使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量，其中基于所述码矢量的分量k来以升序对所述码矢量进行排序，其中所述编码器被配置用于通过以下操作进行搜索：

执行仅考虑所述输入矢量的分量k的二分搜索；以及

执行考虑全码矢量的修改的部分失真搜索。

8.根据权利要求7所述的装置，其中执行所述二分搜索找到满足以下条件的具有最小索引j的矢量：

X_k＜C_j，k，

其中X是所述输入矢量并且C是所述经排序的码矢量。

9.根据权利要求8所述的装置，其中执行所述修改的部分失真搜索包括：

执行开始于索引j-1的向下搜索；以及

执行开始于索引j的向上搜索。

10.根据权利要求9所述的装置，其中在找到以下码矢量时终止所述向下搜索，所述码矢量导致比提供所述最佳匹配的当时码矢量更大的分量k的失真。

11.根据权利要求9所述的装置，其中在找到以下码矢量时终止所述向上搜索，所述码矢量导致比提供所述最佳匹配的当时码矢量更大的分量k的失真。

12.根据权利要求9所述的装置，其中所述编码器还被配置用于：

在终止所述向上搜索和所述向下搜索两者时选择码矢量作为所述最佳匹配矢量。

13.一种用于处理音频数据的设备，包括：

用于使用码书C中经排序的码矢量来搜索输入矢量的最佳匹配矢量的装置，其中基于所述码矢量的分量k来以升序对所述码矢量进行排序，其中用于搜索的装置包括：

用于执行仅考虑所述输入矢量的分量k的二分搜索的装置；以及

用于执行考虑全码矢量的修改的部分失真搜索的装置。

14.根据权利要求13所述的设备，其中用于执行所述二分搜索的所述装置被配置用于找到满足以下条件的具有最小索引j的矢量：

X_k＜C_j，k，

其中X是所述输入矢量并且C是所述经排序的码矢量。

15.根据权利要求14所述的设备，其中用于执行所述修改的部分失真搜索的所述装置包括：

用于执行开始于索引j-1的向下搜索的装置；以及

用于执行开始于索引j的向上搜索的装置。

16.根据权利要求15所述的设备，其中用于执行向下搜索的装置被配置用于在找到以下码矢量时终止所述向下搜索，所述码矢量导致比提供所述最佳匹配的当时码矢量更大的分量k的失真。

17.根据权利要求15所述的设备，其中用于执行向上搜索的装置被配置用于在找到以下码矢量时终止所述向上搜索，所述码矢量导致比提供所述最佳匹配的当时码矢量更大的分量k的失真。

18.根据权利要求15所述的设备，还包括：

用于在终止所述向上搜索和所述向下搜索两者时选择码矢量作为所述最佳匹配矢量的装置。

Images