基于直方图获取有效HMM的预剪枝方案

摘要

本发明的实施方式包含声学处理设备、用于声信号处理的方法以及语音识别系统。语音处理设备可包含处理单元、直方图剪枝单元和预剪枝单元。处理单元被配置成计算一个或多个隐马尔可夫模型(HMM)剪枝门限。直方图剪枝单元被配置成剪枝一个或多个HMM状态，以便产生一个或多个有效HMM状态。剪枝基于一个或多个剪枝门限。预剪枝单元被配置成基于可调节预剪枝门限来剪枝一个或多个有效HMM状态。而且，可调节预剪枝门限基于一个或多个剪枝门限。

说明书

背景

领域

本发明的实施方式大体上涉及到数据模式识别。更具体地，本发明的实施方式涉及到用于数据模式识别的音素分数加速器。

背景

越来越多地使用实时数据模式识别来分析电子系统中的数据流。例如，在具有超过数以万计的词的词汇表上，语音识别系统取得了更好的准确度，使其成为电子系统的吸引人的特性。在诸如移动设备、服务器、汽车和PC市场的以数据模式识别应用为目标的消费者市场中，语音识别系统变得越来越普遍。

尽管在语音识别系统中的准确度有所提高，但是，大量的计算资源却被用于语音识别处理，继而将大量负荷施加在诸如多用户/多编程环境的计算机系统上。多编程计算系统同时处理来自各种应用的数据，因此，由语音识别处理施加在这些计算系统的负荷将影响计算系统能够处理输入的声音信号和来自其他应用的数据的速度。而且，对于通常包含有限存储器资源(如与台式计算系统相比而言)的手持式设备，语音识别应用不仅将大量负荷施加在手持设备的计算资源上，而且还消耗手持设备的存储器资源的很大一部分。实时或本质上接近实时地处理输入的声音信号的需求进一步加重了上述语音识别系统的处理负载量、速度和存储资源中的问题。

内容

因此，具有对语音识别系统施加在计算系统的处理负载量、速度和存储资源上的负荷进行改善的需要。

本发明的实施方式包含语音处理设备。语音处理设备可包含处理单元、直方图剪枝单元和预剪枝单元。处理单元被配置成计算一个或多个隐马尔可夫模型(HMM)剪枝门限。直方图剪枝单元被配置成剪枝一个或多个HMM状态，以便产生一个或多个有效HMM状态。剪枝基于一个或多个剪枝门限。预剪枝单元被配置成基于可调节预剪枝门限来剪枝一个或多个有效HMM状态。而且，可调节预剪枝门限基于一个或多个剪枝门限。

本发明的另一个实施方式包含用于声信号处理的方法。方法可包含以下操作：基于一个或多个剪枝门限来剪枝一个或多个隐马尔可夫模型(HMM)状态，以产生一个或多个有效HMM状态，并基于可调节预剪枝门限来预剪枝一个或多个有效HMM状态。可调节预剪枝门限基于一个或多个剪枝门限。

本发明的另一个实施方式包含语音识别系统。语音识别系统可包含具有系统存储器的中央处理单元(CPU)和连接至CPU的声学处理设备。声学处理设备可包含处理单元、直方图剪枝单元和预剪枝单元。处理单元被配置成计算一个或多个隐马尔可夫模型(HMM)剪枝门限。直方图剪枝单元被配置成基于HMM剪枝门限来剪枝一个或多个HMM状态，以便产生一个或多个有效HMM状态。预剪枝单元被配置成基于可调节预剪枝门限来剪枝一个或多个有效HMM状态。而且，可调节预剪枝门限基于一个或多个剪枝门限。

下面参考附图详细描述本发明的其他特性和优点、以及本发明的各种实施例的结构和操作。应注意，本发明不限制于本文所描述的特定实施方式。只出于说明的目的在本文中提出这些实施方式。基于本文中包含的指导，其他的实施方式对于相关领域的技术人员将变得明显。

附图简述

被并入本文且形成说明书的一部分的附图阐述本发明的实施方式，并连同描述进一步地用来解释本发明的原理，并使得相关领域的技术人员能够制造并使用本发明。

图1是根据本发明的实施方式的语音识别过程的示例性流程图的图例。

图2是传统的语音识别系统的图例。

图3是传统的语音识别系统的图例，其具有由单个处理单元实施的语音识别处理。

图4是由声协同处理器(ACP)和中央处理单元(CPU)实施的语音识别处理的实施方式的图例。

图5是声协同处理器(ACP)的实施方式的图例。

图6是声协同处理器(ACP)中的存储器模块的实施方式的图例。

图7是声协同处理器(ACP)中的隐马尔可夫模型(HMM)模块的实施方式的图例。

图8是用于声信号处理的方法的实施方式的图例。

图9是哈希表的实施方式的图例。

图10是哈希表搜索过程的实施方式的图例。

图11是哈希表插入过程的实施方式的图例。

图12是哈希表剩余有效处理的实施方式的图例。

图13是示例计算机系统的图例，本发明的实施方式或其一部分可在该示例计算机系统中被实现为计算机可读代码。

详细说明

以下详细说明涉及到附图，附图阐明与本发明一致的示例性实施方式。其他实施方式是可能的，并且可在本发明的精神和范围之内对实施方式进行修改。因此，详细说明并不旨在限制本发明的范围。相反，本发明的范围由所附权利要求定义。

对于相关领域的技术人员明显的是，如下文中所描述地，可在软件、硬件、固件和/或图中所示实体的很多不同实施方式中实现本发明。因此，以一种理解描述本发明的实施方式的操作性的行为，这种理解是，根据本文给出的具体描述的程度，对实施方式的修改和改变是可能的。

该说明书公开了包含本发明的特性的一个或多个实施方式。所公开的实施方式仅仅举例证明本发明。本发明的范围不限制于所公开的实施方式。本发明由随附的权利要求限定。

所描述的实施方式和说明书中参考的“一个实施方式”、“实施方式”、“示例实施方式”等表示所描述的实施方式可包含特定特性、结构或特征，但不是所有的实施方式必须包含特定特性、结构或特征。而且，这些短语并不一定指的是同一个实施方式。另外，当将特定特性、结构或特征与实施方式相联系进行描述时，应理解的是，本领域的技术人员掌握将这些特性、结构或特征与其他实施方式相结合进行实现的知识，而不管其是否被具体描述。

1.语音识别过程

图1是根据本发明的实施方式的语音识别过程100的示例性流程图的图例。语音识别过程100包含信号处理级110、声学建模级120、音素评估级130和词语/语言/语法建模级140。

在信号处理级110中，可对输入的模拟信号形式的声音信号105进行滤波，以便去除信号中位于人耳能听到的频率范围之外的高频成分。然后使用相关领域的技术人员熟知的采样和量化技术使经滤波的信号数字化。可使用诸如线性预测编码和快速傅立叶变换等技术从数字化波形中提取一个或多个参数化的数字表示(在本文中还被称为“特征矢量115”)。这种提取能够以例如大约10ms的定期的时间区间或帧发生。

在声学建模级120，将来自信号处理级110的特征矢量115与在存储器中存储的一个或多个多变量高斯概率分布(在本文中还被称为“高斯概率分布”)进行比较。在存储器中存储的该一个或多个高斯概率分布可以是声库的一部分，其中高斯概率分布的混合物表示聚类状态(senone)。聚类状态指的是用于感兴趣的语言的子语音单元，如相关领域的技术人员理解的。单个聚类状态可由例如8个部分组成，其中每个部分可表示39维的高斯概率分布。

例如，声学建模级120可处理超过1000个聚类状态。因此，特征矢量115和一个或多个高斯概率分布的比较可能是计算上和存储上密集的任务，因为例如每个时间区间或帧(例如，10ms)可能将成千上万个高斯概率分布与特征矢量115进行比较。用于声库中表示的每一个聚类状态的一组分数(本文中还被称为“聚类状态分数”)是由将特征矢量115中的每一个与一个或多个高斯概率分布中的每一个进行比较产生的。声学建模级120向音素评估级130提供聚类状态分数125。

在音素评估级130，隐马尔可夫模型(HMM)可被使用于将音素表示为状态集合和每一个状态之间的转移概率的先验集合，其中状态与聚类状态有关。对于聚类状态的特定的观察序列，对应的HMM中具有最可能的状态序列。可将这个对应HMM与所观察的音素相联系。维特比算法可被用于找出每个HMM对应音素的可能性。

维特比算法进行一种计算，该计算始于第一帧，且然后以时间同步的方式一次一帧地继续进行至后续的帧。针对正被考虑的HMM中的每个聚类状态计算概率分数。因此，当维特比算法分析连续帧时，可为每一个可能的聚类状态序列相继计算累计概率分数。与由声学建模级120进行的聚类状态分数计算相似，概率分数的累计计算可能是计算上和存储上密集的任务。音素评估级130向词语/语言/语法建模级140提供语音可能性或概率135(在本文中还被称为“音素分数”)。

在词语/语言/语法建模级140中，使用搜索技术来随时间确定最可能的音素串和最终的词语。诸如树形算法等的搜索技术可被使用于确定最可能的音素串。如相关领域的技术人员将理解的，音素评估级还可被用于计算可变长度的HMM的分数，例如，其表示音素序列、完整的词语或有限状态转换器的弧(arc)。

2.传统的语音识别系统

图2是传统的语音识别系统200的图例。语音识别系统200包含输入设备210、处理单元220、存储设备230和数据总线240，这些全部为单独的物理组件。例如，存储设备230可以是动态随机访问存储器(DRAM)设备，其在处理单元220的外部，并通过数据总线240与处理单元220进行通信。输入设备210也通过数据总线240与处理单元220进行通信。数据总线240具有例如为8至32比特的典型的总线宽度。

输入设备210被配置成接收输入的声音信号(例如，图1中的输入的声音信号105)，并将与输入的声音信号有关的声震动转换为模拟信号。使用模数转换器(图2中未示出)将模拟信号数字化，并将产生的数字信号在数据总线240上传输至处理单元220。例如，输入设备210可以是麦克风。

处理单元220被配置成根据结合图1在上文中描述的信号处理级110、声学建模级120、音素评估级130和词语/语言/语法建模级140的顺序来处理数字输入信号。图3是语音识别系统200的图例，其具有由处理单元220实施的语音识别模块。处理单元220包含信号处理模块310、声学建模模块320、音素评估模块330和词语/语言/语法建模模块340，其分别以与图1中的信号处理级110、声学建模级120、音素评估级130和词语/语言/语法建模级140相似的方式运行。

参考图3，信号处理模块310可将输入的声音信号305(例如，来自输入设备210)的数字输入信号表示转换为一个或多个特征矢量315。声学建模模块320将一个或多个特征矢量315与在存储设备230的声库中存储的一个或多个高斯概率分布进行比较。即，对于一个或多个特征矢量315和一个或多个高斯概率分布的比较中的每一个比较，处理单元220通过数据总线240访问存储设备230。对于具有成千上万个聚类状态的声库(其中每个聚类状态都由多个高斯概率分布组成)而言，不仅是由声学建模模块320实施的比较在计算上密集，而且声学建模模块320通过数据总线240对存储设备230的成千上万个访问也是存储上密集的并耗时的。此外，音素评估模块330为了概率分数的累计计算也要访问存储设备230。数据总线240的总线宽度(例如，通常8至32个比特)进一步恶化对存储设备230的成千上万个访问，其中声学建模模块320、音素评估模块330可能需要对存储设备230的多个访问。另外，与数据总线240有关的互连寄生可能使存储设备230和声学建模模块320之间以及存储设备230和音素评估模块330之间的数据传输恶化。

音素评估模块330从声学建模模块320接收聚类状态分数325。如在上文中关于图1的语音识别过程100所讨论的，HMM可被用于将音素表示为状态集合和每一个状态之间的转移概率的先验集合，其中，状态包含一系列聚类状态。可将由音素评估模块330使用的状态集合和转移概率的先验集合存储在存储设备230中。音素评估模块330向词语/语言/语法建模模块340提供音素分数335。

词语/语言/语法建模模块340使用诸如树形算法等的搜索技术来随时间确定最可能的音素串(例如，最可能的音素335)以及最终的词语。

图3的传统的语音识别系统300的许多问题中的一个问题是由于声学建模和音素评估过程引起的在处理单元220上的大量负荷。例如，对于一个或多个特征矢量315和在存储设备230中存储的一个或多个高斯概率分布的比较中的每一个，处理单元220都访问存储设备230。相似地，在音素评估过程中，处理单元220访问存储设备230，以便取回用于概率分数的累计计算的状态和先验转移概率信息。因此，大量的计算和存储资源致力于声学建模和音素评估过程，从而在处理单元220和存储单元230上施加大量负荷。

由声学建模和音素评估过程施加在处理单元220上的负荷影响处理单元220能够处理来自输入设备210的数字信号和来自其他应用的数据(例如，其中处理单元220可以同时处理来自多个应用的数据的多用户/多编程的环境中工作)的速度。另外，对于具有有限存储资源的计算系统(例如，手持式设备)，声学建模和音素评估过程不止在处理单元220上施加大量负荷，而且还消耗存储设备230和数据总线240的带宽的很大一部分。在许多应用中实时或本质上接近实时地处理输入的声音信号的需求进一步加重了处理负载量、速度和存储资源中的这些问题以及其他问题。

3.具有音素分数加速器的语音识别系统

本发明的实施方式解决在上文中分别关于图2和3的传统的语音识别系统200和300讨论的问题。在一个实施方式中，声学建模过程由专用的处理单元(在本文中还被称为“声协作处理器”或“ACP”)实施。ACP连同图3的处理单元220(本文中还被称为“中央处理单元”或“CPU”)工作。例如，ACP从CPU接收一个或多个特征矢量(例如，图3的特征矢量315)，基于一个或多个高斯概率分布计算聚类状态分数(例如，图3的聚类状态分数325)，基于聚类状态分数计算音素分数，并向CPU输出音素分数。

在一个实施方式中，可将一个或多个高斯概率分布和HMM信息(例如，HMM词典、HMM状态信息和先验转移概率信息)存储在ACP中的存储设备位置中。在另一个实施方式中，可将一个或多个高斯概率分布和HMM信息存储在ACP之外的专用的存储设备中，其中ACP从外部存储设备接收一个或多个高斯概率分布和HMM信息。根据本发明的一个实施方式，专用的存储设备是与系统存储器(例如，图3的存储设备230)分离的，其中的系统存储器与CPU关联。在又一种选择中，可将一个或多个高斯概率分布或者HMM信息存储在ACP之外的专用的存储设备中，其中ACP从外部存储设备接收一个或多个高斯概率分布或HMM信息。基于ACP的结构，可获得聚类状态分数和音素分数的加速计算。

本公开关注基于一个或多个聚类状态分数的音素分数的加速计算。例如，可在2012年6月6日提交的(代理案号3186.0050000)、标题为《声学处理单元(AcousticProcessingUnit)》的美国专利申请第13/489,799号(其全部内容作为参考并入本文)中找到关于聚类状态分数的加速计算的细节。

尽管在语音识别系统的环境中描述了本公开的各个部分，相关领域的技术人员将意识到本文所述的实施方式可用于基于本文说明的任何数据模式识别应用中。这些其他的数据模式识别应用包括但不限于图像处理、音频处理和手写识别。这些其他的数据模式识别应用在本文公开的实施方式的精神和范围之内。

图4是由ACP和CPU实施的语音识别过程400的实施方式的图例。在一个实施方式中，CPU实施信号处理过程410和词语建模过程440。ACP实施声学建模过程420和音素评估过程430。信号处理过程410、声学建模过程420、音素评估过程430和词语/语言/语法建模过程440分别以与图1的信号处理级110、声学建模级120、音素评估级130和词语/语言/语法建模级140相似的方式运行，除非在本文中另外进行了说明。

参考图4的实施方式，反馈450是语音识别过程400的可选特性，其中根据本发明的实施方式，音素评估过程430可向声学建模过程420提供有效的聚类状态列表。声学建模过程420可将一个或多个特征矢量与在有效聚类状态列表中指示的一个或多个聚类状态进行比较。

在另一个实施方式中，声学建模过程420可将一个或多个特征矢量与跟声库有关的所有聚类状态进行比较。在这种情况下，不需要反馈450，因为音素评估过程430从声学建模过程420接收一整组聚类状态分数(例如，“给所有打分”功能)，以供进一步的处理。可在2012年6月6日提交的美国专利申请第13/489,799号中找到关于“给所有打分”功能的额外信息。

4.声协作处理器结构

图5是ACP500的实施方式的图例。在一个实施方式中，ACP500是集成芯片，其包含接口模块510、隐马尔可夫模型(HMM)模块520、聚类状态打分单元(SSU)530和存储模块540。在另一个实施方式中，接口模块510、HMM模型520、SSU530和存储模块540中的每一个都可集成到单独的芯片上或以任何组合的形式集成到共同的芯片上。例如，但非限制性地，接口模块510和HMM模块520可被集成在同一个芯片上，而SSU530和存储模块540可被集成到它们自己各自的芯片上。可选择地，接口模块510、HMM模块520和SSU530可被集成到同一个芯片上，而存储模块540可被集成到其自己的芯片上。

ACP500如同CPU(未在图5中示出)一样被集成到单独的芯片上，并经由输入/输出(I/O)总线505与CPU进行通信，其中ACP500被配置成实施根据本发明的实施方式实施声学建模过程(例如，图4的声学建模过程420)和音素评估过程(例如，图4的音素评估过程430)。在一个实施方式中，I/O总线505可通过API定义，其中I/O总线505可被用于促进用于ACP500的特征矢量信息、音素分数信息和其他I/O控制信号的数据传输。根据本发明的实施方式，ACP500可被配置成经由I/O总线505从CPU接收一个或多个特征矢量(由CPU计算)并经由I/O总线505向CPU发送音素分数，以供进一步的处理(例如，图4的词语建模过程440)。在一个实施方式中，例如，I/O总线505可被实现成SPI总线、PCI总线、AXI总线、AHB总线、APB总线、存储器总线或任何其他类型的总线，以便提供在ACP500和CPU之间的通信路径(参见，例如，图5-7和2012年6月6日提交的美国专利申请第13/489,799号的相关描述)。

参考图5，接口模块510被配置成控制ACP500和外部CPU之间的数据传输。在一个实施方式中，接口模块510可以控制一个或多个特征矢量的接收和来自外部CPU的一个或多个HMM打分要求以及从ACP500到CPU的一个或多个音素分数(例如，HMM状态分数)的传输。在一个实施方式中，接口模块510被配置成经由总线515从CPU向SSU模块530传输一个或多个特征矢量，以供进一步的处理，以及从CPU向HMM模块520传输一个或多个HMM打分要求，以供进一步的处理。虽然SSU模块530计算用于数据帧的一个或多个聚类状态分数且HMM模块520遍历HMM(下文中将详细描述)，但是，根据本发明的实施方式，CPU还搜索另外的HMM，以便进行评估并向接口模块510发送另外的HMM打分要求。如在下文中描述的，HMM模块520接收补充列表形式的HMM打分要求。

根据本发明的实施方式，一旦计算聚类状态分数，就将聚类状态分数从SSU模块530传输到存储器模块540。在另一个实施方式中，将聚类状态分数存储在SSU模块530中的存储设备中(图5中未示出)。例如，可在2012年6月6日提交的美国专利申请第13/489,799号中(例如，参见图14的SSU1430和相关说明)找到关于由SSU模块530进行聚类状态分数的计算的详细信息。在一个实施方式中，SSU模块530计算用于数据帧(例如，10ms的时间区间或帧)的一个或多个聚类状态分数，而CPU计算同一个数据帧的补充列表(下文中更详细描述)，并经由接口模块510将补充列表传输至HMM模块520。

图6是存储模块540的实施方式的图例。存储模块540包含存储控制器610和存储设备620。在一个实施方式中，存储控制器610被配置成控制在接口模块510和存储设备620之间经由总线545的数据传输，在HMM模块520和存储设备620之间经由总线537的数据传输，以及在SSU模块530和存储设备620之间经由总线535的数据传输。根据本发明的实施方式，存储设备620可以是易失性存储设备，例如但不限于，动态随机存取存储器(DRAM)设备。根据本发明的实施方式，存储设备620可被用于存储声库(例如，一个或多个高斯概率分布)，其中在计算聚类状态分数期间SSU模块530经由总线535访问存储设备620。在一个实施方式中，存储设备620还可被用于存储聚类状态分数和HMM信息(例如，HMM词典、HMM状态信息和先验转移概率信息)，其中HMM模块520经由总线537访问存储设备620。根据本发明的实施方式，存储设备620还可被用于存储由ACP500从CPU接收到的控制信息，其中可经由总线545将控制信息传输至存储设备620。

图7是HMM模块520的实施方式的图例，HMM模块520被配置成遍历隐马尔可夫模型。HMM模块520包含HMM产生器710、直方图剪枝模块720、HMM打分模块730、直方图产生器740、预剪枝模块750、弧产生器760、存储设备770和缓存780。根据描述，相关领域的普通技术人员将意识到HMM模块520的组件能够以流水线的方式遍历HMM。

HMM产生器710被配置成从缓存780中存储的补充列表接收弧数据。在一个实施方式中，弧数据包含ACP500经由图5中的I/O总线505从CPU接收到的HMMID和初始HMM状态分数。根据本发明的实施方式，处理弧数据之前，HMM产生器710验证图6的存储设备620中是否存在弧数据。在存储模块620中存储的弧数据(例如，HHMID和HMM状态分数)在本文中还被称为位于ACP500的“有效列表”中。存储设备770在存储设备620中存储对应于数据状态的一个或多个状态比特，并可以是具有快于图6的存储设备620的访问时间的存储设备，例如而非限制性的，静态随机存取存储器(SRAM)设备。

如果有效列表中存在来自补充列表的弧数据，那么可将来自补充列表的弧数据与其对应的有效列表中的弧数据合并。在一个实施方式中，当与来自补充列表的弧数据有关的HMM状态分数高于与有效列表中的现有弧数据有关的HMM状态分数时(例如，来自补充列表的弧数据具有与当前数据帧匹配的更高概率)，则将有效列表中的现有弧数据的左上下文(leftcontext)替换为来自补充列表的弧数据。HMM状态的每一个都包含状态索引(K)和左上下文(K-1)，其中(K-1)指的是在状态索引(K)之前的或其左边的状态索引。如果在有效列表中不存在来自补充列表的弧数据，那么将来自补充列表的弧数据插入到有效列表中，其中将来自补充列表的弧数据提供给有效列表中的新的弧条目的左上下文(例如，(K-1))。而且，根据本发明的实施方式，可从存储设备620读取与新的弧条目(其当前位于有效列表中)有关的HMMID(例如，从存储设备620中存储的HMM词典)。

下文在部分5中更详细地描述了确定在有效列表中是否存在来自补充列表的弧数据的过程和将来自补充列表的数据合并和插入到有效列表的过程。另外，在下文中针对HMM打分模块730更详细地描述了将弧数据应用于左上下文的细节。

参考图7，在一个实施方式中，HMM产生器710将来自补充列表的弧数据重新格式化为单独的HMM状态，并将单独的HMM状态输出到直方图剪枝模块720。除单独的HMM状态之外，直方图剪枝模块720还接收剪枝门限(图7中未示出)。根据本发明的实施方式，直方图剪枝模块720被配置成对单独的HMM状态使用束剪枝(beampruning)算法，以协助减少ACP500中的有效数据的量。如果单独的HMM状态的分数低于剪枝门限，那么将单独的HMM状态标记为“无效”(例如，将HMM状态的有效/无效标志位设置为“低”或“无效”)。否则，如果单独的HMM状态的分数高于剪枝门限，那么将单独的HMM状态标记为“有效”。在一个实施方式中，基于来自先前时间区间或时间帧(例如，10ms)和预定束宽度的数据的直方图分布来计算剪枝门限。

参考图7，HMM打分模块730从图6的存储设备620接收具有高于剪枝门限的分数的HMM状态和一个或多个聚类状态分数，其中剪枝门限是由直方图剪枝模块720设置的。如上文中讨论的，一个或多个聚类状态分数由图5的SSU模块530计算，并可被存储在图6的存储设备620中。图7中未示出存储设备620和HMM打分模块730之间的总线。可选择地，在另一个实施方式中，可将一个或多个聚类状态分数存储在其他地方，例如但非限制性地，可存储在SSU模块530中。此处，SSU模块530可将一个或多个聚类状态分数经由总线525传输到HMM打分模块730。根据本发明的实施方式，在HMM打分模块730计算HMM状态分数之前，SSU模块530计算一个或多个聚类状态分数。

在一个实施方式中，HMM打分模块730使用以下公式来计算在剪枝门限之上的每一个HMM状态的HMM状态分数：

分数_K,T＝MAX(分数_K,T-1,分数_K-1,T-1)+分数_{聚类状态,T}(K),

其中K是给定弧(ARC)的HMM状态索引，T是时间帧或时间区间(例如，10ms的时间帧或时间区间)。在一个实施方式中，HMM打分模块730连续地接收在剪枝门限之上的给定ARC的HMM状态(即K-2,K-1,K,K+1,K+2,...)。而且，在一个实施方式中，左上下文HMM状态(K-1)的分数在计算当前HMM状态(K)的分数期间是可用的，其中将分数_K,T-1和分数_K-1,T-1之间的最大分数增加到对应于状态索引(K)的聚类状态分数。

根据本发明的实施方式，在计算用于当前状态索引(K)的HMM状态分数之前，将与无效的HMM状态有关的HMM状态分数(例如，与低于剪枝门限的分数有关的HMM状态，其中剪枝门限是由直方图剪枝模块720设置的)设置为最小的概率值，例如但非限制性地，设置为与特定数据格式有关的最低值等。例如，如果将HMM状态分数以16比特数据格式存储，那么与此格式有关的最低值为0。根据本发明的实施方式，如果用于当前状态索引(K)的HMM状态分数高于最小的概率值(例如，0)，那么将HMM状态标记为“有效”。否则，HMM状态保持其“无效”状态。

参考图7，直方图产生器740被配置成产生HMM状态分数的分布，以被用于计算用于下一个时间区间或时间帧的剪枝门限。在一个实施方式中，直方图产生器740接收来自HMM打分模块740的具有“无效”状态的HMM状态、来自先前数据帧的HMM状态分数(例如，来自先前数据帧的最大HMM状态分数)以及箱宽(binwidth)信息。箱宽信息可包含箱子的数量和每个箱子的宽度，其中无效HMM状态被分布到箱子中。在一个实施方式中，箱子的数量和每一个箱子的宽度是预定的，并由CPU向ACP500提供。

根据本发明的实施方式，在装箱过程之前，通过从每一个有效HMM状态分数减去先前帧的最佳HMM状态分数来更新有效HMM状态的分数。在一个实施方式中，将具有低于零的被更新的分数的HMM状态放置在第一箱中，将具有高于零的被更新的分数的HMM状态放置在第二箱中。在将所有的有效HMM状态装箱之后，将有效HMM状态的分布发送给CPU，以供在直方图剪枝模块720中用于下一个剪枝门限的计算。在另一个实施方式中，直方图产生器740被用于计算在直方图剪枝模块720中使用的下一个剪枝门限。相关领域的普通技术人员熟知剪枝门限的计算。

参考图7，剪枝模块750被配置成从HMM打分模块730和预剪枝门限接收具有“有效”状态的HMM状态。在一个实施方式中，预剪枝门限由CPU计算并被传输至图5的ACP500，其中预剪枝门限是来自一个或多个先前的数据帧的预剪枝门限的函数。在另一个实施方式中，预剪枝模块750可产生预剪枝门限。如果与有效HMM状态有关的分数低于预剪枝门限，那么将HMM状态的状态从“有效”改为“无效”。下面在部分6中描述了关于预剪枝门限的计算的其他的细节。

弧产生器760被配置成从预剪枝模块750接收具有“有效”状态的HMM状态，即接收具有高于预剪枝门限的分数的HMM状态。在一个实施方式中，弧产生器760被配置成确定当前HMM状态是否为HMM的最后的状态，其中HMM具有数目为N的状态(例如，N＝3)。根据本发明的实施方式，如果当前HMM状态是HMM的最后的状态并具有“有效”状态，那么将HMM状态写入缓存780中。将HMM状态信息从缓存780经由图5的接口模块510传输到CPU，以供进一步处理。如果当前HMM状态不是HMM的最终状态并具有“有效”状态，那么将HMM状态信息哈希并插入有效列表中(例如，将数据散列并存储到图6的存储设备620中，其中将状态信息存储到图7的存储设备770中)。与图2和图3中的各个传统的语音识别系统200和300不同，专用存储设备(图6的存储设备620和图7的存储设备770)被用于存储有效列表，从而使得专用HMM打分模块(例如，图5的HMM模块520)被用于计算HMM状态分数，而不是使用系统存储器(例如，图2的存储设备230)和CPU(例如，处理单元220)，从而减轻在CPU和系统存储器上施加的负荷。因此，CPU可处理来自其他应用的数字信号，其中CPU可在可同时处理来自多个应用的数据的多用户/多编程环境中运行。

图8是用于声信号处理的方法800的图例。例如，可使用图5的ACP500实施方法800的步骤。

在步骤810中，从外部计算设备(例如，经由图5的I/O总线505与ACP500进行通信的CPU)接收一个或多个特征矢量和HMM信息。例如，HMM信息可包含HMM词典、HMM状态信息和先验转移概率信息。

在步骤820中，基于一个或多个特征矢量来计算一个或多个聚类状态分数。可使用SSU计算一个或多个聚类状态分数，其中SSU例如为在2012年6月6日提交的美国专利申请第13/489,799号中公开的SSU(例如，参见图14的SSU1430和相关描述)等。在一个实施方式中，当外部计算设备产生用于数据帧的补充列表时，计算用于数据帧的一个或多个聚类状态分数。将补充列表从外部计算设备传输至HMM模块(见下文中的步骤830)。而且，补充列表可包含第一多个HMMID和HMM状态分数，其未被存储在第二多个HMMID和HMM状态分数的有效列表中(例如，参见上文中关于图7的HMM产生器710描述的有效列表)。

在步骤830中，基于一个或多个聚类状态分数来计算一个或多个HMM状态分数。可使用诸如图5的HMM模块520的HMM模块等来计算一个或多个HMM状态分数。在一个实施方式中，在计算一个或多个HMM状态分数之前，计算一个或多个聚类状态分数(参见步骤820)。

在步骤840中，将一个或多个HMM状态分数存储在存储模块中，其中存储模块、SSU和HMM模块被集成在第一芯片上，且外部计算设备被集成在第二芯片上，第一芯片和第二芯片是分开的。例如，存储模块可以是图5的存储模块540。

在步骤850中，将一个或多个HMM状态分数传输到外部计算设备。可使用诸如图5的接口模块510等接口模块来将一个或多个HMM状态分数传输到外部计算设备。

本发明的实施方式提出并解决了在上文中关于图3的传统的语音识别系统200所讨论的问题。概括地说，例如，由图5的ACP500实施音素评估过程。AC与CPU一同工作，其中ACP可以从CPU接收一个或多个特征矢量(例如，图3的特征矢量315)，基于一个或多个高斯概率分布计算聚类状态分数(例如，图3的聚类状态分数325)，基于聚类状态分数计算音素分数，并向CPU输出音素分数。在一个实施方式中，可将一个或多个高斯概率分布和一个或多个HMM存储在位于ACP中的存储设备中。可选择地，在另一个实施方式中，可将一个或多个高斯概率分布和HMM存储在ACP之外的专用的存储设备中，其中ACP从外部存储设备接收一个或多个高斯概率分布和HMM。基于上文描述的ACP架构的实施方式，获得了聚类状态分数和音素分数的加速计算。

5.在有效列表中哈希和插入弧数据

如在上文中在部分4中讨论的，HMM产生器710从在图7的缓存780中存储的补充列表接收弧数据。以下部分描述将来自补充列表的弧数据哈希并插入到存储设备(例如，图7的存储设备770)的有效列表中的实施方式。出于解释的目的，在语音识别应用的环境中描述以下实施方式。然而，基于本文的说明，本领域的普通技术人员将意识到这些实施方式可被应用于其他应用中，例如但非限制性地，可被应用于图像处理、音频处理和手写识别等。这些其他应用在本文公开的实施方式的精神和范围之内。

A.哈希表结构

图9是根据本发明的实施方式的哈希表900的图例。如在下文中更详细的描述的，例如，可在图6的存储设备620和图7的存储设备720中实现哈希表900。哈希表900包含两个存储区：第一区910和第二区960。在本发明的一个实施方式中，相比第一区910，第二区960可具有较小的存储容量。例如，相比第一区910，第二区960可包含较少的存储条目。相比第一区910，第二区960还可包含较少的用于每个条目的状态比特。与此相反，相比第二区960中的每一个条目，第一区910中的每个条目可能需要更大的数据格式(例如，数据比特数量)。例如，第一区910中的每个条目可包含HMM信息，而第二区960的每个条目可包含状态或标志位信息。

鉴于第一区910和第二区960的上述特性，可在数据模式系统中实现这些存储区，以获得例如更快、更便宜、更节省功率的实现。例如，可在分开的存储设备(或芯片)上实现第一区910和第二区960，其中与第一区910的存储设备相比，将第二区960实现在具有更快的访问时间的更小的存储设备上。因此，可通过首先在第二区960中处理信息以在访问第一区910之前确定第一区910的信息是否有效且确定其是否已被处理过来提高系统性能。实现哈希表900的语音识别系统因此可以限制其必须访问第一区910的次数。基于本文的说明，本领域的普通技术人员将意识到可将哈希表900实现在其他系统上。这些其他系统在本发明的范围和精神之内。

在本发明的实施方式中，在DRAM设备中实现第一区910并在SRAM设备中实现第二区960。如本领域的普通技术人员将理解的，SRAM设备具有比DRAM设备更快的访问时间(例如，读取和写入访问时间)。然而，与SRAM设备相比，DRAM设备具有更小的芯片占位面积，以及在以更高的存储密度生产时的更便宜的成本。因此，在SRAM和DRAM设备之间的权衡中，实现哈希表900的系统获取例如以SRAM设备的速度优势来最小化对较慢的DRAM设备的访问次数，同时仍然利用DRAM设备的尺寸小和成本低的优势，以存储系统使用的大多数的数据。

参考图9，根据本发明的实施方式，如虚线915₀-915₇所示，第一区910的每个条目对应第二区960的一个条目。即，与第二区960中的条目有关的索引值具有与第一区910中其对应条目相同的索引，从而使第一区910和第二区960之间具有相对于第一区910中存储的数据的一对一的映射。在一个实施方式中，第一区910中的每个条目都包含数据和关于溢出数据的存储位置的信息。在一个实施方式中，如果将要存储在第一区910的数据太大而无法存储在单个条目中，那么将多出的数据存到溢出段970中。这允许哈希表900保持第二区960和第一区910之间的映射。在另一个实施方式中，溢出段170是可选的并在第一区910中未被分配存储空间。

可用多种方式组织第一区910中的条目。例如，第一区910中的每个条目可包含如在图9中示出的弧数据920、分数930、溢出指针940和溢出长度950。根据本发明的实施方式，数据920可表示被语音识别应用使用的HMM信息，例如，在图5的ACP500中使用的HMM信息等。在一个实施方式中，弧数据920包含HMMID。分数930包含用于HMM的当前状态分数，即，用于当前处理的状态的HMM状态分数。溢出指针940可指向第一区910的溢出段970中的存储位置，其存储不能在第一区910的条目中存储的数据930的任何部分。溢出长度950可被用于标识多少额外的数据被存储到第一区910的特定条目的溢出段970中。

在一个实施方式中，第二区960中的每个哈希条目包含多个状态比特，状态比特指示是否需要访问第一区910的对应条目和在第一区910的对应条目中存储的信息是否需要更进一步的处理。例如，在语音识别的环境中，如图9所示的，对于第二区960中的每一个条目，可以存储两个比特。在一个实施方式中，第一比特(在本文中还被称为“有效比特980”)可指示第一区910中的对应条目是否有效(例如，数据位于用于特定数据帧的哪个存储位置)。根据本发明的实施方式，第二比特(在本文中还被称为“打分比特的比特990”)可指出第一区910中的对应条目是否已经针对特定数据帧被打分(例如，HMM状态分数)。

B.哈希表规程

图10、11和12是根据本发明的实施方式的哈希表过程的图例。图10是哈希表搜索过程1000的图例。图11是哈希表插入过程1100的图例。图12是哈希表剩余有效过程1200的图例。

i.哈希表搜索规程

例如，可使用图5的ACP500实施哈希表搜索过程1000。哈希表搜索过程1000包含数据接收步骤1002、哈希键产生步骤1004、查看有效比特步骤1006、未找到步骤1008、数据读取步骤1010、比较步骤1012、设置打分比特步骤1014、处理数据步骤1016和增量器步骤1018。

在数据接收步骤1002中，将迭代计数设置为“0”，并接收数据(例如，通过图5的ACP500)。参考图5的ACP500，这个数据可以是表示较大的帧的一部分的声音的一个或多个特征矢量和补充列表中的弧数据。在一个实施方式中，来自补充列表的弧数据包含HMM信息，其中从外部计算设备(例如，经由图5的I/O总线505与ACP500进行通信的CPU)向ACP500提供补充列表。

在哈希键产生步骤1004中，通过在弧数据(来自步骤1002)上执行哈希函数来产生哈希键，其中哈希键提供哈希表索引。在一个实施方式中，哈希表指的是在上文中关于图7的HMM产生器710描述的有效列表。在一个实施方式中，将哈希表(或有效列表)存储在图6的存储设备620中。根据本发明的实施方式，将哈希函数实施在来自补充列表的弧数据上，其中哈希函数的结果提供哈希表索引，通过该索引对应弧数据。

在一个实施方式中，可将哈希函数拆分成两个单独的哈希函数。以下公式中示出包含两个单独的哈希函数的哈希函数的示例：

H(x)＝(H1(x)+i*H2(x))模p

第一哈希函数H1(x)基于来自补充列表的弧数据产生第一临时值。第二哈希函数H2(x)基于弧数据产生第二临时值，其中第二哈希函数H2(x)与计数i相乘。计数i可表示计算过的哈希函数H(X)的次数。根据本发明的实施方式，如上述公式所示，结合了两个哈希函数的结果，以在哈希表中产生索引。

在一个实施方式中，可以如此设计哈希函数，从而当散列数据时(例如，来自补充列表的弧数据)，将结果随机分布在整个哈希表上。这种类型的设计的许多好处中的一个好处是，当将数据存储到哈希表中时的冲突数量的减少，从而提高如下文中讨论的哈希表搜索过程1000和哈希表插入过程1100的速度和效率。例如，第一哈希函数H1(X)可将数据随机地分布在整个哈希表上，从而减少数据被分配到同一个存储索引。这减少存储被散列的数据所需的总时间。第二哈希函数H2(X)可创建用于确定下一个哈希索引的随机步骤，如果发生冲突，减轻连续冲突的影响。这减少在冲突的情况下找到可用的存储索引的时间。

在查看有效比特的步骤1006中，从图9的第二区960读取诸如有效比特980等状态比特。这个状态比特标识在第一区910中的对应条目是否有效。在一个实施方式中，如果在条目中存储了用于当前数据帧的数据，那么第一区910中的条目是有效的；否则，如果没有数据，那么条目是无效的。查看有效比特的步骤1006确定有效比特是否被设置(即，第一区910的对应条目包含用于当前数据帧的数据)或是被清除(即，第一区910中的对应条目不包含用于这个帧的数据)。

在第二区960中存储有效比特(例如，有效比特980)提供至少两个好处，其中有效比特指示第一区910中的对应条目是否有效。首先，当第一区910具有比第二区960慢的访问时间时，第二区960的有效比特提供确定是否需要访问第一区910的快速方式。第二，通过将有效比特单独地存储在具有更快的访问时间的存储设备(例如，SRAM设备)中，存储设备可通过访问包含第二区960的较快的存储设备并清除第二区960中的所有有效比特来快速使两个存储器(例如，图6的存储设备620和图7的存储设备770)中的条目无效。例如，当哈希表需要准备好接收用于新的数据帧的数据的时候，这是有用的。例如，参考图5的ACP500，一旦计算了用于数据帧的HMM状态分数，这允许ACP500快速使整个表无效，以便为新的数据帧做准备。

如果用于这个迭代的索引在第二区960中的有效比特被清除(例如，第一区910中的对应条目不包含数据)，那么过程1000继续进行到未找到步骤1008。在未找到步骤1008中，过程1000指示在哈希表中未找到数据。

参考图10，在检查有效比特步骤1006中，如果用于这个迭代的索引在第二区960中的条目指示该条目是有效的(例如，第一区910的对应条目包含数据)，那么过程1000继续进行到存储数据读取步骤1010。从该索引在第一区910中的对应条目读取存储数据。在一个实施方式中，由于从弧数据创建哈希键的性质，其中具有两种设置有效比特的情况。第一，例如，图5的ACP500可能已接收用于先前帧的弧数据。如果这样，弧数据将产生与先前接收的弧数据相同的哈希键并被存储到相同的哈希条目中。第二，在第一哈希迭代中或在连续迭代中可能接收产生相同哈希键的不同弧数据。处理之前，必须确定当前弧数据是否已被存储到表条目中或不同弧数据是否被存储到表条目中。因此，在比较步骤1012处，将存储弧数据与接收弧数据进行比较。

参考图10，如果存储弧数据与接收弧数据不同，那么过程1000返回到步骤1004，以便执行哈希函数的另一个迭代。在这种情况下，所接收的弧数据与所存储的弧数据不同；然而，当被哈希函数处理时，所接收的弧数据产生与所存储的数据相同的键。为了创建用于接收的弧数据的不同哈希键，过程1000继续进行增量器步骤1018，其中增加迭代计数i。

如果存储的弧数据与接收的弧数据相同，那么过程1000继续进行到设置打分比特步骤1014，其中针对该索引设置第二区960中的打分比特990。过程1000然后继续进行到处理数据步骤1016，在其中处理数据并为其打分。

ii.哈希表插入规程

例如，可使用图5的ACP500实施哈希表插入过程1100。哈希表插入过程1100包含数据接收步骤1102、哈希键产生步骤1104、查看有效比特步骤1106、写入数据步骤1108、设置有效比特步骤1110和增量器步骤1112。

以分别与上文中描述的数据接收步骤1002和哈希产生步骤1004相同的方式，数据接受步骤1102和哈希产生步骤1104接收数据并产生哈希键。

在查看有效比特的步骤1106中，从图9的第二区960读取诸如有效比特980等状态比特。这个状态比特标识在第一区910中的对应条目是否有效。在一个实施方式中，如果在条目中存有用于当前数据帧的数据，那么第一区910中的条目是有效的；否则，如果没有数据，那么条目是无效的。查看有效比特的步骤1106确定有效比特是否被设置(例如，第一区910中的对应条目包含用于当前数据帧的数据)或被清除(例如，第一区910中的对应条目不包含用于这个帧的数据)。

如上所述，有利的是在第二区960中存储有效比特(例如，有效比特980)，其中有效比特指示第一区910中的对应条目是否有效。如上讨论的，在第二区960中存储对应第一区910的条目的有效比特提供至少两个好处。第一，它提供了确定需要访问第一区910中的哪个条目的快速方式，尤其是当访问第二区960快于访问第一区910时。第二，它提供使第一区910和第二区960中的所有条目无效的快速并有效的方式。

如果设置了用于这个迭代的索引在第二区960中的有效比特(例如，第一区910中的对应条目包含数据)，则过程1100执行哈希函数的另一个迭代，以便标识插入数据的不同位置。为了创造用于接收的弧数据的不同哈希键，过程1100继续进行增量器步骤1112，在其中增加迭代计数。

参考图11，在检查有效比特步骤1106中，如果用于这个迭代的索引在第二区960中的条目指示该条目是无效的(例如，第一区910中的对应条目不包含数据)，那么过程1100继续进行到写入数据步骤1108。将接收数据存储在第一区910中。过程1100继续进行到设置有效比特步骤1110，其中在第二区960中设置对应这个条目的有效比特。这表示现在该条目包含有效数据，以供将来的搜索。

iii.哈希表剩余的有效规程

图12是根据本发明的实施方式的哈希表剩余的有效过程1200的图例。在语音识别的环境中，在处理完来自补充列表的弧数据之后(例如，由图5的HMM模块520处理)，可能存在有效列表中未处理的弧数据(在本文中还被称为“剩余数据”)。过程1200扫描有效列表(例如，在图7的存储设备770中存储的)，以便识别有效(例如，设置了有效比特980)但未打分的HMM。然后从存储器(例如，图5的存储设备540)中取回HMM数据并为其打分。过程1200包含初始化步骤1210、第二区读取步骤1220、第一区读取步骤1250、打分步骤1260、增量器步骤1270、最终步骤1295和三个比较步骤1230、1240和1290。

在初始化步骤1210中，将表索引设置为零。在第二区读取步骤1220中，从图9的第二区960的表索引读取有效比特980和第二比特990。在比较步骤1230中，过程1200确定是否设置或清除有效比特980。

如果已清除有效比特980，这表示未存储用于哈希表的条目的数据。因此，过程1200继续进行到增量器步骤1270，在下文中对其进行讨论。

如果设置了有效比特980，这表示在哈希表中有弧数据，过程1200继续进行到比较步骤1240。在比较步骤1240中，确定是否设置或清除打分比特990。

如果已设置打分比特990，这表示已经存储了弧数据。因此，不需要进一步的处理，且过程1200继续进行到增量器步骤1270，在下文中对其进行讨论。

如果清除了打分比特990，过程1200继续进行到第一区读取步骤1250。在第一区读取步骤1250中，过程1200根据图9的第一区910中的索引读取弧数据。一旦在第一区读取步骤1250中读取了弧数据，过程1200继续进行到打分步骤1260，其中为存储弧数据打分。过程1200然后继续进行到增量器步骤1270。

在增量器步骤1270中，将当前索引的第二区960中的有效比特980和打分比特990清除，然后增加索引。过程1200然后继续进行到比较器步骤1290。

在比较器步骤1290中，将新的索引(例如，增加的索引)与哈希表的尺寸进行比较。如果索引大于或等于哈希表的尺寸，完成过程1200。如果不是，过程1200返回到第二区读取步骤1220，以分析与新的索引相关的信息。

6.预剪枝

如在上文中关于图7所讨论的，预剪枝模块750从接收来自HMM打分模块740的和预门限接收有效HMM状态和预剪枝门限。在一个实施方式中，预剪枝门限被由CPU计算并被传输至图5的ACP500，其中预剪枝门限是来自一个或多个先前的数据帧的预剪枝门限的功能函数。在另一个实施方式中，图7的预剪枝模块750可产生预剪枝门限。

剪枝通过早期检测哪些HMM不太可能表示正被分析的语音提供了降低处理语音所需要的资源的一种方式。这在限定了分配给语音识别过程的处理资源和存储器的情况下是很重要的；尤其是当声模型逐渐变成更精确的模型语言时更是如此。剪枝门限被用于基于HMM表示正被分析的语音的概率来确定保留哪些HMM以供进一步处理。

在一个实施方式中，语音处理系统在不同时刻剪枝HMM状态。首先，系统可以在对HMM状态进行处理并为其打分之后、但在分析下一个数据帧之前预剪枝HMM状态。这个剪枝过程在本文中还被称为“预剪枝”。其次，系统可以在计算HMM状态分数之前剪枝HMM状态。因为剪枝发生在先前帧完成HMM状态处理并为其打分之后，所以可如此选择剪枝门限，从而对于当前数据帧，只分析一定数量的HMM状态(例如，1000)。

以下讨论关注于语音识别系统的预剪枝过程。例如，图7的预剪枝模块750可实施预剪枝过程。预剪枝允许系统在HMM状态被存储到存储器(例如，图6的存储设备620)之前将其移除。通常，语音识别系统的用户为预剪枝门限选择常数值来确定将哪些HMM状态存储在存储器中。因为预剪枝门限是常数并在HMM处理开始之前被选择，所以它必须足够大，从而使足够数量的HMM状态可用于声音质量的波动(在本说明书中，较低的HMM状态分数代表较高的概率)。在用于预剪枝门限的常数值中可考虑这种波动。通常，在低音质环境中，将用于语音识别的预剪枝门限保守地设置为很大的数。用于预剪枝门限的常数值不针对高音质环境中的语音识别进行调整，其通常具有较低的HMM状态分数。

参考图7，如果对应的HMM状态分数差于(例如，小于)预剪枝门限，那么预剪枝模块750将HMM状态标为“无效”。在一个实施方式中，可基于用于先前N个帧的剪枝门限(例如，由图7的直方图剪枝模块720使用的剪枝门限)来调整预剪枝门限，其中N是正整数。通过使用基于一个或多个先前数据帧的剪枝门限的可调节预剪枝门限，可调节预剪枝门限可被校准成剪枝一些但不是所有的独立于音质的HMM状态(例如，低音质环境对高音质环境)。在从处理单元220接收一个或多个先前的剪枝门限之后，可调节预剪枝门限可由图2的处理单元220提供或者可在图7的预剪枝模块750中被计算。图7的预剪枝模块750还可接收来自直方图产生器740(经由HMM打分模块730)的用于一个或多个先前数据帧的HMM状态分数和来自图5的SSU530的聚类状态分数。

在一个实施方式中，可调节预剪枝门限是来自先前数据帧的HMM状态分数和来自先前数据帧的剪枝门限的函数。以下公式可定义可调节预剪枝门限：

P_预，T+1＝分数_{最佳，HMM，T}+Δ_T+1

P_预，T+1＝用于帧T+1的实际的预剪枝门限；

分数_{最佳，HMM，T}＝来自帧T的最佳HMM状态分数；以及

Δ_T+1＝基于一个或多个先前数据帧的剪枝门限的当前计算的预剪枝门限。

总之，根据本发明的实施方式，基于以上公式，可调节预剪枝门限是所处理的HMM状态分数之和，例如来自先前数据帧的最佳HMM分数和来自一个或多个先前数据帧的剪枝门限之和。可基于帧T+1的一个或多个聚类状态分数或通过一个或多个直方图箱回退所计算的预剪枝门限。

在另一个实施方式中，可调节预剪枝门限是来自先前数据帧的一个或多个聚类状态分数、来自当前数据帧的一个或多个聚类状态分数、或一个或多个直方图箱的函数。除了来自先前数据帧的所处理的HMM状态分数和来自一个或多个先前数据帧的剪枝门限之外，还可使用这个。以下公式可定义可调节预剪枝门限：

P_预，T+1＝分数_{最佳，HMM，T}+分数_{最佳，聚类状态}+Δ_T+1

P_预，T+1＝用于帧T+1的实际的预剪枝门限；

分数_{最佳，HMM，T}＝来自帧T的最佳HMM状态分数；

分数_{最佳，聚类状态}＝基于帧T+1的一个或多个聚类状态分数、帧T的一个或多个聚类状态分数、或一个或多个直方图箱的可能的回退值；以及，

Δ_T+1＝基于一个或多个先前数据帧的剪枝门限的当前计算的预剪枝门限。

在一个实施方式中，所处理的HMM状态分数可以是用于最佳HMM的分数。根据本发明的实施方式，聚类状态分数可以是来自当前数据帧或来自先前数据帧的聚类状态。在一个实施方式中，聚类状态分数可以是来自先前帧的最佳聚类状态分数或者是来自当前帧的最佳聚类状态分数。在一个实施方式中，聚类状态分数还可被直方图的一个或多个箱的宽度修改。例如，如果在先前帧中剪枝通过了K个箱，那么回退值可被用于在当前帧的预剪枝阶段中通过K+1或K+2个箱。

7.示例性计算机系统

可在软件、固件、硬件或其组合中实现本发明的各个方面。图13是示例计算机系统1300的图例，本发明的实施方式或其一部分可在该示例计算机系统中被实现为计算机可读代码。例如，可在系统1300中实现图8的流程图800示出的方法、图10的流程图1000所示的方法、图11的流程图1100所示的方法和/或图12的流程图1200所示的方法。根据该示例计算机系统1300，描述了本发明的各个实施方式。阅读本说明书之后，将对相关领域的技术人员变得明显的是，如何使用计算机系统和/或计算机架构来实现本发明的实施方式。

应注意，可通过使用计算机可读代码来部分完成本发明的各种实施方式的仿真、合成和/或生产，其中计算机可读代码包含通用编程语言(例如C或C++)；诸如VerilogHDL、VHDL、AlteraHDL(AHDL)的硬件描述语言(HDL)或其他可用的编程和/或原理图捕获工具(例如，电路捕获工具)。所述计算机可读代码可位于任何已知计算机可使用介质中，包括半导体、磁盘、光盘(例如CD-ROM、DVD-ROM)。因此，可将代码在包括互联网的通信网络上传输。应理解，所完成的功能和/或由系统提供的结构和上文描述的技术可在核(例如，ACP核)中表示，核在编程代码中体现并可作为集成电路的生产的一部分被传输至硬件。

计算机系统1300包含诸如处理器1304的一个或多个处理器。处理器1304可以是专用或通用处理器，分别例如为图4的ACP和CPU等。将处理器1304连接至通信基础结构1306(例如，总线或网络)。

计算机系统1300还包含主存储器1308，优选地为随机存取存储器(RAM)，并还可包含副存储器1310。例如，副存储器1310可包含硬盘驱动1312、移动存储驱动1314和/或记忆棒。移动存储驱动1314可包含软盘驱动、磁带驱动和光盘驱动、闪速存储器等等。移动存储驱动1314以众所周知的方式从移动存储单元1318读取和/或向移动存储单元1318写入。移动存储单元1318可包括软盘、磁带、光盘等，其由移动存储驱动1314读取和写入。如相关领域的技术人员将意识到的，移动存储单元1318包含计算机可使用存储介质，在其上存储有计算机软件和/或数据。

计算机系统1300(可选择地)包含显示接口1302(其可包含诸如键盘、鼠标等的输入和输出设备)，显示接口1302传输来自通信基础结构1306(或来自未示出的帧缓存)的图形、文字和其他数据，以供在显示单元1330上显示。

在可选择的实现中，副存储器1310可包含其他相似的设备，以允许将计算机程序或其他指令加载到算机系统1300中。例如，这种设备可包括移动存储单元1322和接口1320。这种设备的示例可包络程序盒式存储器(catridge)和盒式接口(例如，在视频游戏中找到的那些)、移动存储芯片(例如，EPROM或PROM)和相关插座、以及允许将软件和数据从移动存储单元1322传输到计算机系统1300的其他移动存储单元1322和接口1320。

计算机系统1300还可包含通信接口1324。通信接口1324允许将软件和数据在计算机系统1300和外部设备之间传输。通信接口1324可包括调制解调器、网络接口(例如以太网卡)、通信端口、PCMCIA槽和卡等等。经由通信接口1324传输的软件和数据具有信号的形式，其可以使电子的、电磁的、光的或能够被通信接口1324接收到的其他信号。经由通信路径1326将这些信号提供给通信接口1324。通信路径1326携带信号，并可使用电线或电缆、光纤、电话线、移动电话链路、RF链路或其他通信信道将其实现。

在此文件中，术语“计算机程序介质”和“计算机可使用介质”被用于广义地指诸如移动存储单元1318、移动存储单元1322和在硬盘驱动1312上安装的硬盘的介质。计算机程序介质和计算机可使用介质还可指的是诸如主存储器1308和副存储器1310的存储器，其可以是存储器半导体(例如，DRAM等)。这些计算机程序产品向计算机系统1300提供软件。

计算机程序(还称之为计算机控制逻辑)被存储在主存储器1308和/或副存储器1310中。还可经由通信接口1324接收计算机程序。当被执行时，这种计算机程序使得计算机系统1300能够实现如本文中讨论的本发明的实施方式。具体地，当被执行时，计算机程序使得处理器1304能够实现本发明的实施方式的过程，例如，上文中讨论的图8的流程图800示出的方法、图10的流程图1000所示的方法、图11的流程图1100所示的方法和/或图12的流程图1200所示的方法中的步骤可以在系统1300中实现。因此，这种计算机程序表示计算机系统1300的控制器。在使用软件实现本发明的实施方式的地方，可将软件存储在计算机程序产品中并使用移动存储驱动1314、接口1320、硬盘驱动1312或通信接口1324将软件加载到计算机系统1300中。

本发明的实施方式还针对包含在任何计算机可使用介质上存储的软件的计算机程序产品。当在一个或多个数据处理设备上被执行时，这种软件导致数据处理设备如上文中描述地运行。本发明的实施方式采用现在已知或将来会知道的任何计算机可使用或可读介质。计算机可使用介质的示例包括但不限制于主存储设备(例如，任何类型的随机存取存储器)、副存储设备(例如，硬盘驱动、软盘、CDROM、ZIP盘、磁带、磁存储设备、光存储设备、MEMS、纳米技术存储设备等等)和通信介质(例如，有线和无线通信网、局域网、广域网、企业内部网等)。

8.结论

应理解，详细说明部分(不是内容和摘要部分)旨在被使用于解释权利要求。发明内容和摘要部分可能提出一个或多个但并非由发明人所预期的本发明的所有示例性实施方式，因此，并非旨在以任何方式限制本发明及所附权利要求。

上面借助示出特定功能的实现及其关系的功能构造块描述了本发明的实施方式。为了说明的方便，在本文中不严格地定义了这些功能构造块的界限。只要适当地实施特定功能及其关系，就可以定义其他的界限。

特定实施方式的前述说明将如此完全地揭示本发明的一般特性，从而使其他人可以通过应用相关领域的技能范围内的知识，在无过度实验和不脱离本发明的通用概念的情况下，容易地对这种特定实施方式进行修改和/或使其适应于各种应用。因此，基于本文中提出的指导和引导，这种调整和修改旨在落入所公开的实施方式的等价物的意义和范围之内。应理解，本文中的措辞和术语是出于说明的而不是限制的目的，从而使本说明书的措辞或术语将由技术人员根据指导和引导诠释。

本发明的宽度和范围不应限制于任何上述的示例性实施方式，而是应只根据以下权利要求及其等价物来定义。