語音識別系統中跟蹤矩陣存儲器的方法

2023-05-05 11:33:56 1

專利名稱：語音識別系統中跟蹤矩陣存儲器的方法
技術領域：
本發明涉及語音識別，尤其是涉及存儲用於語音識別系統的格子跟蹤信息的方法。
背景技術：
在依賴於講話者的語音識別系統中，當使用該系統時，用戶必須註冊他們想要的詞彙表字(vocabulary word)。詞彙表的「字」可以是說出的單個字或者短語，且詞彙表的字的選擇依賴於特定的應用。例如，用於可攜式無線電話的語音識別裝置可能要求用戶提供經常呼叫的人們的姓名和位置(例如，「弗瑞德的辦公室」)，或者通常使用的特徵的指令提供在用戶的接口(例如，「蓄電池安時計」，「消息」，或「電話鎖」)。
在註冊程序過程中，語音識別系統響應用戶的輸入以導出用於每一個詞彙表字的代表性模板。在一些系統中，此模板由包括一系列狀態的隱式馬爾科夫模式(HMM)表示。每一個狀態代表語音表達(speechutterance)的有限的部分；在此使用的表達稱為「詞彙表字」，其可包括一個或多個字。使用由用戶說出的特定的詞彙表字的一個或多個註冊語音樣本字來計算每一個HMM的狀態的統計表示。這通過幀對狀態分配來完成。
這種狀態分配被用於訓練和工作的語音識別模式。具體地說，已分配的狀態被用來創建在訓練模式中的模型，其被用來作為在語音識別模式期間的比較參考。可使用在工作的語音識別模式中的輸入表達的分配來產生分數信息，並且將輸入表達與已存儲的參考模型進行比較。
諸如維特比算法的對準算法(alignment algorithm)被用於表達的幀對狀態分配。提供了將語音表達與模型進行最好匹配的對準算法被用來將詞彙表字表達的每一幀分配給模型的各個狀態。使用這種分配，可以精煉用於每一個狀態的統計表式。
在幀對準期間，通過找出表達幀與在模型中的狀態的最佳匹配來定義「路徑」。為了進行這一步，需要對在每一幀中的HMM的每一狀態進行評估。假設觀察到的語音總計為幀t，其中的進入給定的狀態的狀態在幀t-1最好，確定了該估計的一部分。對於完全連接的HMM，任意的一個狀態可以轉變為任意的其它狀態。因此，可能有到達每一個狀態的N個路徑，其中N為狀態數。
使用這種技術，在對準算法期間，需要跟蹤哪一個語音幀被映射到在模型中的每一個狀態。使用常規的技術，這要求很大的存儲器。現有技術的方法使用稱為跟蹤矩陣的陣列來存儲每一幀的信息，詳細地給出到每一個狀態的最好路徑。通常，這需要N×T的陣列，其中N為模型中的狀態數，T為表達中的最大幀數。由於通常N等於20，T等於30，這樣的表示需要6000字的存儲量。
為了在可攜式設備上完成依賴於講話者的訓練算法，在提供非常小的隨機存儲器(RAM)的無線通信設備中，用於存儲格子跟蹤信息的技術需要使所要求的存儲空間最小。因此，需要一種方法，用於存儲需要用來訓練HMM的格子跟蹤信息，其減小所要求的存儲空間量。


我們深信具有新穎性的本發明的特徵被具體地闡述於所附權利要求中。通過參考下面的說明書，結合所附附圖可以更好地理解本發明及其進一步的目的和優點，其中，相同的附圖標記代表相同的元件，其中
圖1為以方框圖形式表示的根據本發明的存儲格子跟蹤信息的無線電話的電路示意圖；圖2為以方框圖形式表示的說明用於根據圖1中的無線電話中的語音識別電路的輸入電路的電路示意圖；圖3為說明具有被分段為幀的兩個相關的語音表達的左-右隱式馬爾科夫模型(left-right Hidden Markov Model)；圖4為一種模型的狀態轉移圖，其中，允許有自身環、單個步驟和單個跳變轉移；圖5為與在圖4的狀態轉移圖中的狀態之間的每一個允許的路徑相關的跟蹤格子；圖6為根據本發明的存儲狀態時延計數(state dwell counts)的跟蹤陣列；圖7為根據本發明的陣列更新過程的示意框圖，所述陣列更新過程用於使用存儲位置來更新存儲在時延計數的跟蹤陣列中的格子跟蹤信息；圖8為根據本發明的存儲狀態時延計數的各行的存儲陣列的示意框圖；圖9和圖10為對應於根據本發明的用於使用存儲位置來更新存儲在時延計數的跟蹤陣列中的跟蹤信息的方法的流程圖；圖11為說明用於產生線性陣列的過程的流程圖，該過程對應於本發明，被用來根據圖9和10的陣列更新過程的結果來存儲為每一個幀的幀分配；圖12為使用圖11的產生過程生成的線性陣列的示意框圖；圖13為根據本發明的另一個實施例的使用數字編碼碼元來存儲狀態時延計數的陣列的示意框圖；圖14為根據本發明的用於使用數字編碼來更新跟蹤信息的陣列更新過程的示意框圖；圖15為根據本發明的使用數字編碼來更新存儲作為時延計數的跟蹤陣列的格子跟蹤信息的方法的流程圖；圖16為根據本發明的用於產生線性陣列的過程的流程圖，其被用於根據圖15的陣列更新過程的結果來存儲用於每一個幀的幀分配。
具體實施例方式
本文公開了一種用於語音識別的跟蹤矩陣更新和存儲方法。在依賴於講話者的註冊過程中，用戶提供一個或多個重複的語音表達以被註冊。使用一幀分配過程來將每一個此類表達與現有的隱式馬爾科夫模型進行匹配。通過產生具有多行和一列或者多列的跟蹤幀列來存儲和更新用於語音識別系統的格子跟蹤信息，多行中的每一行對應於跟蹤路徑終止的多個狀態中的一個，並且每一列包含一個或多個用於在跟蹤路徑中的狀態的時延計數。進入多個狀態中的給定的狀態的最佳的狀態轉移路徑被確定，並且響應所述已確定的最佳的狀態轉移路徑，更新所述已產生的跟蹤陣列。當執行該過程時，通過存儲用於每一個狀態的狀態時延計數集來影響記錄在表達的短時間分析幀與所述模型的狀態之間的相關性(association)的有效的方法。
本發明可以有利地採用的設備100示於圖1中。為了說明，在此將設備100描述為可攜式無線電話，但是其可以是計算機、個人數字助理、或者可以有利地採用語音識別的任意其它的設備，特別是可以利用有效的存儲語音識別系統的設備。所示的無線電話包括發射器102和連接到天線106的接收器104。發射器102和接收器104連接到執行呼叫處理功能的呼叫處理器108。可以使用數位訊號處理器(DSP)、微處理器、微控制器、可編程邏輯電路、兩個或多個上述器件的組合或者任何其它合適的數字電路來實現呼叫處理器108。
呼叫處理器108連接到存儲器110。存儲器110包括RAM、電可擦可編程只讀存儲器(EEPROM)、只讀存儲器(ROM)、閃爍ROM等、或者兩個或多個這些存儲器類型的組合。存儲器110支持呼叫處理器108的工作，改工作包括語音識別工作，並且必須包括電可改變的存儲器以支持在下文詳細地介紹的狀態轉移路徑存儲器。可以提供ROM以存儲運行程序的設備。
音頻電路112將數位訊號從話筒114提供給呼叫處理器108。音頻電路112驅動揚聲器116響應來自呼叫處理器108的數位訊號。
呼叫處理器108連接到顯示處理器120。如果另外的處理器支持是設備100所希望的，則顯示處理器是可選的。具體而言，顯示處理器120提供顯示控制信號到顯示器126，並從鍵盤124接收輸入。可以使用微處理器、微控制器、數位訊號處理器、可編程邏輯電路及其組合等來實現顯示處理器120。存儲器122連接到現實處理器以支持數字邏輯。可以使用RAM、EEPROM、ROM、閃爍ROM等等，或者兩個或多個這些存儲器類型的組合來實現存儲器122。
參考圖2，在音頻電路112的模數轉換器202中將話筒114接收到音頻信號轉換為數位訊號。本領域的普通技術人員將認識到，音頻電路112提供另外的信號處理，諸如在此為了簡短而沒有介紹的濾波處理。呼叫處理器108在由話筒114輸出的模擬信號的已處理的數位訊號表示上執行特徵抽取204，並且產生代表用戶表達的特徵向量集。為每一個短時間分析窗口產生一個特徵向量。短時間分析窗口為一幀，其中在此示例中為20ms。因此，每一幀有一個特徵向量。處理器108使用用於語音識別206或訓練207的特徵。
在訓練中，使用表達的特徵向量來已被存儲在存儲器208中的和HMM的形式產生模板。在語音識別中，將表示輸入表達的特徵向量於存儲在存儲器208中的詞彙表字的模板進行表較以確定用戶說的是什麼。系統可輸出最好的匹配，最好的匹配集，或者可選地，沒有匹配。存儲器208優選地可以是存儲器110的非易失性存儲部分(圖1)，並且可以是，例如EEPROM或閃爍ROM。正如在此使用的一樣，「字」可以是不只一個字，諸如「約翰多爾」，或者是諸如「呼叫」單字。
如上面的簡短介紹一樣，在訓練模式中產生在存儲器208中的已存儲的詞彙表字。例如，已存儲的詞彙表字被從兩個訓練信號即表達U1和U2(圖3)中初始導出，分別由特徵向量組成。表達U1代表講話者在訓練期間說的特定的字的第一時間時存儲的信號。表達U2代表講話者在訓練期間說的特定的字的第二時間時存儲的信號。在說明的例子中，表達U1和表達U2的長度不同。本領域普通技術人員將認識到，可以使用更多的或更少的表達。
由於幀具有相同的長度，而表達U1和U2具有不同的長度，當用幀表示每一表達時，具有不同長度的表達U1和U2將同樣地具有不同的幀數。多個幀Ft組成了一表達。一般而言，儘管將表達標識為Ft，其中t為從1到T，在圖3的符號中，表達幀由符號Fab標識，其中a為表達號，而b為幀號。具體而言，表達U1具有10幀即F11，F12，F13，F14，F15，F16，F17，F18，F19，和F110。表達U2具有12幀，即F21，F22，F23，F24，F25，F26，F27，F28，F29，F210，F211，和F212。在示例中，每一幀包括代表20毫秒聲音的特徵。
可以使用任何常規的方式產生特徵向量。例如，特徵向量可以包括從A/D轉換器202(圖2)的輸出產生的導頻(eepstral)和Δ-導頻特徵。
參見圖3，開始時，從表達U1的幀F11和F12和表達U2的F21和F22形成狀態1(S1)。這些幀值被用來初始地計算包括狀態1的統計表示的一些或所有的參數。在優選實施例中，統計表示為表達U1和表達U2的幀的均值。因此，開始時將狀態1設為表達U1的幀F11和F12和表達U2的F21和F22的幀的均值。本領域普通技術人員將認識到，狀態也可包括方差。也產生其它狀態的統計表示。第二狀態S2為表達U1的幀F13和F14和表達U2的幀F23和F24的均值。類似地，第三狀態S3為表達U1的幀F15和F16和表達U2的幀F25和F26的均值。狀態S4為表達U1的幀F17和F18和表達U2的幀F27，F28和F29的均值。
如上述例子，在表達U2中的外面的幀被分配給最後的兩個狀態。如果第二表達僅僅具有一個外面的幀，只有最後的狀態獲得外面的幀。如果第二表達具有三個外面的幀，最後三個狀態中的每一個被分配一個外面的幀。類似地，如果第一表達具有外面的幀，如四個外面的幀，最後四個狀態中的每一個將具有一外面的幀。如果一個表達具有的幀多於其它表達的幀達5個幀，則每一個狀態從具有更多幀的表達接收三個幀，並從具有較少幀的表達接收兩個幀。
上述的幀分配被提供來作為一個例子，說明可以如何初始化地來將幀分配給狀態，和如何形成狀態的統計表示。然而，本領域普通技術人員將認識到，現有的其它多種方法可以用來初始地分配狀態，並且統計地表示狀態，因此，本發明不限於上述情形。
在例子中，使用5個狀態而不管表達的長度。本領域普通技術人員將認識到，可以使用任意數目的狀態，並且可以預料到，可以為每一個表達採用多於10個的狀態。此外，狀態數可以是固定的而不需要考慮表達的長度，或者狀態數依賴於表達的長度。下面的討論將針對任意的表達使用5個狀態的系統進行介紹，而不考慮長度。
一旦從表達U1和U2的幀的統計生成狀態S1至S5，就生成了隱式馬爾科夫模型(HMM)。呼叫處理器108採用對準算法來通過生成的HMM的狀態運行每一個表達。然後，可以使用對準來重新估計狀態的統計表示。具體而言，對準算法運行以根據每一個考慮的路徑的分數來確定從任何的點的最佳的路徑反饋。根據本發明的用於存儲和更新此信息的方法通常稱為格子跟蹤信息，將參考圖6和7對其進行介紹。
圖4為一種模型的狀態轉移框圖，其中，允許有自身環、單步、和單跳轉移。儘管在圖4的狀態轉移框圖中僅示出狀態1-6，應當理解，可以包括任意數目的狀態，將狀態數限制為6個狀態僅僅是為了簡化介紹。
為了使模型序列化、在語音表達的聲音事件中的規則特徵更好，通常限制在模型中的從狀態到狀態或者狀態轉移的可能路徑。例如，在一種最普通的隱式馬爾科夫模型結構和被證明對於多種語音識別任務是有效的結構中，將允許的狀態轉移限制為自身環、單步、或單跳。通常，實質上將HMM狀態轉移限制為左到右，如圖4所示，其中進入特地狀態Sn的允許的轉移路徑來自該狀態Sn，或者來自前兩個狀態S(n-1)或S(n-2)中的一個。來自狀態Sn進入到狀態Sn的狀態轉移路徑被稱為自身環，通常表示為ann，來自前一個狀態S(n-1)的進入特定狀態Sn的狀態轉移路徑被稱為單步，通常表示為a(n-1)n，來自前二個狀態S(n-2)的進入特定狀態Sn的狀態轉移路徑被稱為單跳，通常表示為a(n-1)n。
具體而言，如圖4所示，例如，進入第五狀態300的允許的狀態轉移路徑或者來自自身環a55，其中前一幀狀態與當前幀狀態相同，或者來自單步轉移a45，其中前一狀態為第四狀態302，或者來自單跳轉移a35，其中前一幀狀態為第三狀態304。類似地，進入第四狀態302的允許的狀態轉移路徑或者來自本身環a44，其中前一幀狀態與當前幀狀態相同，或者來自單步轉移a34，其中前一幀狀態為第三狀態304，或者來自單跳轉移a24，其中前一幀狀態為第二狀態306。
圖5為與在圖4的狀態轉移框圖中的狀態之間每一個允許的路徑相關的跟蹤格子。如圖5所示，格子310中的每一點308對應于格子31中的幀和狀態位置。路徑延伸通過該點，狀態之間的每一個允許的路徑為三種狀態轉移類型即自身環、單步或者單跳狀態轉移中的一個。例如，在時間t＝5處進入如圖4所示的第五狀態300的三個允許的狀態轉移路徑a55，a44和a55中的每一個由進入格子310中的點A的路徑指定。進入點A的自身環狀態轉移路徑a55由源於點B的路徑312指定，點B位於在時間t＝4時如點A即縱軸上的狀態5一樣的相同的狀態。進入點A的單步狀態轉移路徑a45由源於點C的路徑314指定，點C位於在時間t＝4時點A的狀態前的狀態即縱軸上的狀態4。最後，進入點A的單跳狀態轉移路徑a35由源於點D的路徑316指定，點D位於在時間t＝4時點A的狀態前兩個狀態即縱軸上的狀態3。
從圖4和5可看出，在任意給定的狀態之前僅有三個狀態。儘管對允許的轉移的此類限制固存於此類HMM結構中，傳統的跟蹤矩陣存儲技術沒有使用這種性質。本發明使用這種限制狀態轉移的知識，並且進一步提供對跟蹤矩陣的改進，其中顯著地減小了需要記錄跟蹤路徑的存儲量。
具體而言，根據本發明，使用狀態時延計數的陣列來維持跟蹤矩陣，在所述狀態時延計數的陣列中記錄經過模型的路徑。給定當前狀態，向後通過格子的路徑被記錄作為在該狀態所用的幀數(即用於該狀態的時延計數)和在每一前面狀態使用的幀數。根據本發明，用於存儲狀態時延計數的跟蹤存儲陣列示於圖6中，其中狀態數N等於5(例如)。本發明的跟蹤陣列可以顯示為三角形，其中每一行對應於跟蹤路徑終止的5個狀態1-5中的一個，在每一列中，為跟蹤路徑中的每一狀態記錄時延計數。
因此，根據本發明，通過更新n個時延計數集，列舉有多少幀或者時間分段信號被用在狀態1至n中的每一個狀態來更新從5個狀態的每一個狀態n的路徑返回(path back)(n＝1，2，...，5，對應於行1-5)。例如，如圖6所示，行320對應於結束於狀態5的狀態轉移路徑，存儲在列322和行322的信息指出用於該路徑的狀態5中的幀數，存儲在列324和行320的信息指出用於該路徑的狀態4中的幀數，存儲在列326和行320的信息指出用於該路徑的狀態3中的幀數，存儲在列328和行320的信息指出用於該路徑的狀態2中的幀數，存儲在列330和行320的信息指出用於該路徑的狀態1中的幀數。類似地，行332對應於結束於狀態4的狀態轉移路徑，存儲在列324和行332的信息指出用於該路徑的狀態4中的幀數，存儲在列326和行332的信息指出用於該路徑的狀態3中的幀數，存儲在列328和行332的信息指出用於該路徑的狀態2中的幀數，存儲在列330和行332的信息指出用於該路徑的狀態1中的幀數，行334-338依此類推。
儘管圖6的跟蹤陣列包括5個狀態，應當理解，本發明不限於使用5個狀態，而是可以使用任意的狀態數。
在具有N個狀態的HMM中使用根據本發明的跟蹤陣列的模型，要求大小為 的陣列。因為N可以多達小於在表達T中的最大的幀數數量級，與傳統技術所要求的NxT大小的陣列相比，本發明的跟蹤矩陣顯現出顯著地節約所要求的存儲量。
利用根據本發明的存儲位置來更新在時延計數的跟蹤陣列中存儲的跟蹤信息的陣列更新過程示於圖7中。儘管可以理解可以包括任意數目的狀態，並且將狀態數限制為4個狀態僅僅是為了簡化介紹，圖7的例子說明了狀態數N＝4的一種情況。根據本發明，更新過程可用於由格子340和跟蹤陣列342和360指定的自身環狀態轉移路徑，可用於由格子344和跟蹤陣列346和364指定的單步狀態轉移路徑，可用於由格子348和跟蹤陣列350和368指定的單跳狀態轉移路徑，可用於由格子352和跟蹤陣列354和372指定的雙跳狀態轉移路徑，依次類推，可以擴展到N個狀態跳躍狀態轉移路徑。
格子中的每一點對應於該格子中的幀和狀態位置，水平軸對應於幀，縱軸對應於狀態。
如圖7所示，用於在幀4處的每一路徑結束狀態的最佳路徑由陣列342(等價於陣列346，350，354)的時延計數行來指示。從下面的從幀4向後的路徑可以看出記錄在陣列中的跟蹤路徑格子340用於狀態4，格子344用於狀態3，格子348用於狀態2，格子352用於狀態1。例如，結束於(幀4，狀態4)的跟蹤路徑為狀態4的一個幀，在狀態3的一個幀，在狀態2的一幀，和在狀態1的一幀。結束於(幀4，狀態3)的跟蹤路徑為狀態3的一個幀，在狀態2的兩個幀，在狀態1的一幀。結束於(幀4，狀態2)的跟蹤路徑為狀態2的3個幀，在狀態1的一個幀。最後，結束於(幀4，狀態1)的跟蹤路徑為狀態1的4個計數。
儘管結束於4個狀態中的一個處的每一路徑對應於用於該狀態的最佳路徑，也就是，結束於狀態4跟蹤路徑為用於狀態4的最佳路徑，結束於狀態3的跟蹤路徑為用於狀態3的最佳路徑等等，這些最佳路徑不必重疊。因此，對於每一個狀態，有一個相應的、可能是唯一的、最佳的路徑，如格子340、344、348和352所示。根據本發明，用跟蹤信息的陣列的行單獨地記錄每一狀態的跟蹤路徑。
根據本發明，根據被確定為最佳的狀態轉移路徑，應用了一些確定的更新過程。使用對準算法如維特比對準算法來確定最佳的路徑，並且更新存儲在跟蹤陣列中的路徑信息以反映使用本發明更新過程的選擇的路徑。每一次接收到新幀時，例如，在圖7的說明中考慮幀5時，運行對準算法，並且更新路徑信息。
為了為新接收到的幀更新路徑信息，要考慮每一狀態。例如，考慮狀態4、幀5，其中考慮從幀4到幀5可能的路徑。如果進入一狀態的最佳路徑為自身環狀態轉移路徑，如在圖7的格子340中從幀4到幀5，也就是進入在幀5的狀態4的狀態轉移來自在第一列356和行358的對應於在狀態4中用的幀數(時間分段信號)的狀態4，其增加1。結果，更新後的陣列360指出結束於狀態4的最佳跟蹤路徑包括在狀態4的兩個幀，在狀態3的一個幀，在狀態2的一個幀，和在狀態1的一個幀。
如果進入一狀態的最佳路徑為單步狀態轉移路徑，如圖7的格子344中的從幀4至幀5，也就是進入在幀5的狀態4的狀態轉移來自狀態3，對應於第一在前狀態的行362，也就是狀態3被複製進入行358，並且行358的第一列入口被重設為1。結果，更新後的陣列364指出結束於狀態4的最佳跟蹤路徑包括在狀態4的一個幀，在狀態3的一個幀，在狀態2的兩個幀，和在狀態1的一個幀。
如果進入一狀態的最佳路徑為單跳狀態轉移路徑，如圖7的格子348中的從幀4至幀5，也就是進入在幀5的狀態4的狀態轉移來自狀態2，對應於第二在前狀態的行366，也就是狀態2被複製進入行358，並且行358的第一列的入口被重設為1。由於已跳過狀態3，並且行366不包括用於狀態3的時延計數，用於狀態3的時延計數在行358中被設為0。在這個例子中，已更新的陣列368指出結束於狀態4的最佳的跟蹤路徑包括在狀態4的一個幀，在狀態3的0幀，在狀態2的3個幀，和在狀態1的一個幀。
與進入一狀態的最佳路徑是單跳狀態轉移路徑的情形相似，如果進入一狀態的最佳路徑為雙跳狀態轉移路徑，如圖7的格子352中的從幀4至幀5，也就是進入在幀5的狀態4的狀態轉移來自狀態1，對應於第三在前狀態的行370也就是狀態1被複製進入行358，並且行358的第一列的入口被重設為1。由於已跳過狀態3和狀態2，並且行370不包括用於狀態3和狀態2的時延計數，用於狀態2和狀態3的時延計數在行358中被設為0。在這個例子中，已更新的陣列372指出結束於狀態4的最佳的跟蹤路徑包括在狀態4的一個幀，在狀態3的0幀，在狀態2的0個幀，和在狀態1的4個幀。
將相似的更新過程應用於三跳狀態轉移路徑，依此類推，使得根據本發明的更新過程可被擴展至N個狀態跳躍。通過仔細的考慮，可觀察到單步、單跳、雙跳、和多達N個狀態跳躍的所有的跳躍均採用相同的通用的更新過程。即，通常通過將在第一列的當前的狀態時延計數重設為1，並且複製對應於相關的在前狀態的時延計數的行，並且將所有跳過的狀態時延計數設為0(如果有的話)來處理所有的更新。而且，通過首先在每一幀處執行估計最後的狀態，並且向第一狀態向下工作，可能就地執行跟蹤陣列更新，因此，在對準過程中要求最小的工作存儲量。因此，儘管參考包括了4個狀態的圖7介紹了更新過程，應當理解，可以將本發明的更新過程應用於任意的狀態數。
根據本發明的用於存儲狀態時延計數的行的存儲陣列342(等價於346，350和354)一般地示於圖8中。存儲陣列342包括多個狀態時延計數存儲位置343，每一個存儲位置343一般由Ln[i]標識，使得在位於每一個存儲位置343中的值對應於在從狀態n向後跟蹤的路徑中分配給狀態i的多個幀。例如，對應於L4[3]存儲位置為在存儲陣列342中的位置，對於從狀態4向後跟蹤的路徑，指出被分配給狀態3的幀數，而對於從狀態2向後跟蹤的路徑，對應於L2[2]的存儲位置指出被分配給狀態2的幀數，等等。
在所概述的用於根據狀態時延計數來更新跟蹤信息的過程中，例如圖7中，進行對陣列的「行」和「列」的參考說明。對於熟知所述狀態技術領域的技術人員來說，很顯然，通常不是以此類三角形或者矩形格式組織諸如動態RAM和其他存儲介質的存儲器。通常，以線性的方式用指向存儲字的單個參考指針來訪問存儲器。因此，為了展開本發明的跟蹤陣列，需要進行運算以將用於狀態時延計數的「行」和「列」號轉換為線性存儲字指針。根據如何將三角陣列映射到線性組織的存儲設備，此類算法運算有一些變化，因此，不將這些內容作為一部分包括在本說明書中，這些內容被認為是對於軟體開發的本領於技術人員來說是顯而易見的。
圖9和圖10為對應於根據本發明的用於使用存儲位置來更新存儲在時延計數的跟蹤陣列中的跟蹤信息的方法的流程圖。如圖8和9所示，首先，在步驟400，通過將L1[1]的時延計數設為1、將在該陣列的剩餘位置中的時延計數設為0、並且將幀計數器設為下一幀，t＝2來初始化存儲陣列。然後，在步驟402，確定是否已評估所有的幀，也就是如果t＞T？如果確定已經評估了所有的幀，則結束更新過程，步驟404。然而，如果確定沒有評估完所有的幀，將當前狀態n設為總的狀態數N(步驟408)，使得首先評估最高的或者最後的狀態。例如，如圖7所示，根據本發明，當前狀態n被設為4，示的評估開始於對應於幀2、狀態4的格子340(等價于格子344，348，352)的點處。
然後在步驟410，確定是否已經評估完所有狀態，也就是如果n＜1。如果已經評估完所有的狀態，則增加幀計數器，也就是幀t＝3(步驟412)，並且評估返回步驟402。然而，如果確定在步驟410沒有評估完所有狀態，在步驟414，使用維特比搜索方法執行對進入在幀t處的當前狀態n的最佳路徑的搜索。如果確定進入在幀t處的當前狀態n的最佳路徑位來自當前狀態n(也就是自身環)，在步驟418增加對應於當前狀態n的狀態時延計數存儲位置Ln[n]，在步驟420減當前狀態n，並且然後流程返回步驟410。從圖7可看出，對應於圖9的序列步驟410和414-416的流程對應於跟蹤信息更新過程，該跟蹤信息更新過程用於上面所介紹的當狀態轉移為自身環時將陣列342更新為已更新的陣列360。
如果在步驟416確定進入狀態n的最佳路徑不是來自狀態n(也就是除了自身環狀態轉移的一些狀態轉移)，則流程繼續步驟A(如圖10所示)。如圖10所示，由於最佳路徑不是自身環狀態轉移，最佳路徑必定是來自於前面的狀態m而不是狀態n。結果，根據本發明，在步驟422，將狀態時延計數存儲位置Ln[n]設為1，流程繼續步驟424，至前面的狀態時延計數存儲位置Ln[i]，其中狀態i等於在狀態n前的狀態，或者i＝n-1。然後在步驟426確定是否已經評估完跳過的狀態，也就是如果i小於或等於m。
如果確定沒有評估完所有跳過的狀態，在步驟436清除狀態時延計數存儲位置Ln[i]，使得狀態時延計數存儲位置Ln[i]為0，在步驟438，減狀態i，然後流程返回步驟426。如果在步驟426確定已經評估完所有跳過的狀態，或者等價地沒有狀態被跳過，在步驟428確定是否已經評估完所有的狀態，也就是如果i＜1。
如果確定已經評估完所有的狀態，則在步驟430，流程繼續圖9的步驟420。然而，如果在步驟428確定沒有評估完所有的狀態，在步驟432，將對應於前面狀態m的狀態時延計數存儲位置Lm[i]複製到前一狀態時延計數存儲位置Ln[i]，在步驟434，減狀態i，並且流程回到步驟428。
從圖7可看出，對應於圖10的序列步驟426-434的流程對應於跟蹤信息更新過程，所述跟蹤信息更新過程用於對應於在上面介紹的狀態轉移為單步時將陣列346更新為已更新的陣列364。同樣，從圖7可看出，對應於圖10的序列步驟426、436、438、428、432和434的流程對應於跟蹤信息更新過程，所述跟蹤信息更新過程用於對應於當上面介紹的狀態轉移為單跳或雙跳步驟時分別將陣列350和354更新為已更新的陣列368和372。
圖11為說明對應於本發明的產生線性陣列A[t]的流程圖，用來根據上面介紹的圖9和10的陣列更新過程的結果來存儲用於每一幀的幀分配。根據本發明，圖8的三角形存儲陣列342被展開為線性陣列A[t]，該線性陣列A[t]具有對應於在被對準的表達中的幀T的總數的長度。例如，如在圖7的更新陣列360所示，如果本發明的更新過程結果指出在從狀態4向後跟蹤的路徑中，分配給狀態4的幀數L4[4]等於2，則相應地，L4[3]等於1，L4[2]等於1，和L4[1]等於1，幀總數等於5。
使用用於每一狀態向後跟蹤的路徑的已知幀數，根據本發明的線性陣列A[t]的產生被使用圖11的過程來執行，得到一般地示於圖12中的線性陣列。如圖12所示，產生的線性440包括對應於5個狀態即f＝1至f＝5中的每一個的存儲位置，用於存儲對應於幀所相關的狀態數的值。例如，幀4和5與狀態4相關。
在圖9的步驟404中，一旦已經確定已經評估完所有的幀，已經完成更新狀態時延計數的陣列，根據本發明的用於產生線性陣列A[t]以存儲用於每一幀的幀分配的流程被初始化。如上所述，如果狀態時延計數的更新陣列指出L4[4]＝2，L4[3]＝1，L4[2]＝1，和L4[1]＝1，有對應於從狀態4向後跟蹤的路徑的總計4個狀態和總計5個幀。結果，當前幀t被初始化為等於總的幀數，並且當前狀態n被設為等於總狀態數，步驟422。應當理解，本發明應用於任意的狀態數，並應用於從LN[1]至LN[N]的任意可能的值，已經選擇的用於狀態數和用於L4[1]-L4[4]的值僅僅是為了支持說明本發明。
在步驟444，通過設定計數器k等於LN[n]來設定計數器k，其對應於分配給在從狀態N向後跟蹤的路徑中的幀數，其從狀態時延計數的已更新陣列中獲得。由於在上述的狀態時延計數的已更新陣列的例子中，L4[4]＝2，當前值k等於2。在步驟450，確定是否已經對當前狀態n的所有的狀態分配進行計數(account for)，也就是當前值小於1。如果沒有對所有的狀態計完數，在步驟446記錄用於線性陣列的幀分配，然後在步驟448，減幀t和計數器k，並且流程返回步驟450。然而，如果在步驟450確定已經對所有的狀態分配進行完計數，在步驟452減當前狀態n，並且在步驟454確定是否已經評估完所有的狀態，也就是如果n＜1。如果已經評估了所有狀態，則流程結束(步驟456)，並且在上述的例子中，產生線性陣列A[t]。然而，如果沒有評估完所有狀態，流程返回步驟444。
根據本發明的另一個實施例，是使用數字編碼而不是存儲位置來執行跟蹤和幀分配過程。例如，圖13為根據本發明的使用基數-B數字編碼碼元來存儲狀態時延計數的陣列的框圖。狀態時延計數的陣列457包括狀態時延計數存儲位置L1-L4，通常以Ln表示。每一個狀態時延計數存儲位置Ln包含從狀態n向後的已編碼的路徑信息，對應於用於在從狀態n向後的路徑中每一狀態的狀態時延計數，其被使用根據本發明的陣列更新過程來進行更新，並將參考圖14在下面進行介紹。狀態時延計數457的陣列使用基數-B數字值，使得在任意狀態中的時延時間不能超過B幀。在本發明的優選實施例中，基數B被選擇為2的乘冪(例如，2，4，8，16，32等等)以便於在通常的計算設備上進行計算，然而，應當理解，可選擇任意值的基數B。在本發明的另一個實施例中，基數B被選擇為10，該值用在圖14所時的例子中，並且相應的說明將在下面介紹。
使用根據本發明的另一個實施例的數字編碼來更新存儲在時延計數的跟蹤陣列中的跟蹤信息的陣列更新過程被示於圖14中。與上面的對圖7的討論相似，圖14的更新例子說明了一種情形，其中狀態數N等於4，儘管應當理解，可以包括任意的狀態數，選擇該狀態數為4個狀態僅僅是為了簡化說明。
根據本發明的另一個實施例，更新過程可用於由格子458和跟蹤陣列460，462指定的自身環狀態轉移路徑，可用於由格子464和跟蹤陣列460，466指定的單步狀態轉移路徑，可用於由格子468和跟蹤陣列460，470指定的單跳狀態轉移路徑，可用於有格子472和跟蹤陣列460，474指定的雙跳狀態轉移路徑，依此類推，可以擴展到N-狀態跳躍的狀態轉移路徑。
根據本發明，根據被確定為最佳的狀態轉移路徑，應用特定的更新過程。使用諸如維特比對準算法的對準算法來確定最佳的路徑，並且使用根據本發明的另一個實施例的更新過程來更新存儲在跟蹤陣列中的路徑信息以反映選擇的路徑。每一次收到新的幀時，例如當在圖14的說明中為考慮的幀5時，運行對準算法，並且更新路徑信息。
為了更新用於新接收到的幀的路徑信息，要考慮每一個狀態。如果考慮的狀態為狀態n，並且進入狀態n的最佳路徑被確定為來自狀態m(這裡m小於或等於n)，則記錄來自狀態n的跟蹤路徑的已更新的編碼基數-B值由Ln＝Lm+B(n-1)給出。例如，考慮狀態n＝4，幀5，其中考慮來自幀4至幀5的可能的路徑。如果進入一狀態的最佳路徑為自身環狀態轉移路徑，正如所示的在圖14的格子458中的從幀4至幀5一樣，根據本發明，通過獲得B(n-1)與狀態時延基數的和來更新跟蹤陣列460，所述狀態時延基數用於對應於來自跟蹤陣列460的狀態時延計數位置Ln的當前狀態n。
例如，由於用於在當前跟蹤陣列460中的狀態時延計數位置L4的時延計數為狀態4中的一個時延計數、狀態3中的一個時延計數、狀態2中的一個時延計數和在狀態1中的一個時延計數，並且當前狀態n等於4，通過獲得狀態時延計數位置L4與B4-1的和來更新當前的跟蹤陣列460。因此，使用本發明的更新過程，用於狀態時延計數位置L4的更新的時延計數等於2111，如在更新的跟蹤陣列462所示一樣。
如果進入一狀態的最佳路徑為單步狀態轉移路徑，如所示的圖14的格子464中的從幀4至幀5一樣，根據本發明，通過獲得Bn-1與在對應於來自跟蹤陣列460的前面狀態的狀態時延計數位置中的狀態時延計數的值的和來更新跟蹤陣列460。例如，由於跟蹤陣列460的狀態時延計數位置L3的時延計數為在狀態3中的一個時延計數、在狀態2中的兩個時延計數、和在狀態1中的一個時延計數，並且當前狀態n等於4，通過獲得狀態時延計數位置L3與B4-1的和來更新跟蹤陣列460，結果，狀態時延計數位置L4的已更新的時延計數等於1121，如在更新的跟蹤陣列466中所示。
類似地，如果進入一狀態的最佳路徑為單跳狀態轉移路徑，如所示的圖14的格子468中的從幀4至幀5一樣，根據本發明，通過獲得Bn-1與狀態時延計數的值的和來更新跟蹤陣列460，所述狀態時延計數的值來自於跟蹤陣列460並且在對應於在當前狀態n前面的前兩個狀態的在前狀態的狀態時延計數中。例如，由於跟蹤陣列460的狀態時延計數位置L2的時延計數為在狀態2中的三個時延計數、在狀態1中的一個時延計數，並且當前狀態n等於4，通過獲得狀態時延計數位置L2與B4-1的和來更新跟蹤陣列460，結果，狀態時延計數位置L4的已更新的時延計數等於1031，如在更新的跟蹤陣列470中所示。
最後，如果進入一狀態的最佳路徑為雙跳狀態轉移路徑，如所示的圖14的格子472中的從幀4至幀5一樣，根據本發明，通過獲得Bn-1與狀態時延計數的值的和來更新跟蹤陣列460，所述狀態時延計數的值來自於跟蹤陣列460並且在對應於在當前狀態n前面的前三個狀態的在前狀態的狀態時延計數中。例如，由於跟蹤陣列460的狀態時延計數位置L1的時延計數為在狀態1中的四個時延計數，並且當前狀態n等於4，通過獲得狀態時延計數位置L1與B4-1的和來更新跟蹤陣列460，結果，狀態時延計數位置L1的已更新的時延計數等於1004，如在更新的跟蹤陣列470中所示。對於本領域的普通技術人員來說，很顯然，計算Ln＝Lm+B(n-1)的更新過程通常應用於從狀態n到狀態m的任意的轉移，其中m小於或等於n。
在所概述的用於根據數字編碼來更新跟蹤信息的過程中，例如圖14中，進行對各個數字編碼的基數-B值的參考說明。對於熟知本領域的狀態技術領域的技術人員來說，很顯然，通常在諸如動態RAM和其他存儲介質的存儲設備中的存儲字具有固定的存儲字大小。在將基數B用於編碼和在模型中的狀態數N足夠大的情況下，需要用來存儲編碼值Ln的位數可超過存儲字大小。在這種情況下，可能需要確定的算法運算來執行跟蹤信息更新過程以提供用來擴展至多個存儲字的一編碼值。根據存儲字的大小和用來執行運算的設備的功能，此類算法運算有一些變化，因此，不將這些內容作為一部分包括在本說明書中，這些內容被認為是對於軟體開發的本領於技術人員來說是顯而易見的。
圖15為根據本發明的另一個實施例使用數字編碼來更新存儲作為時延計數的跟蹤陣列的格子跟蹤信息的方法的流程圖。如圖13和15所示，首先，在步驟500，通過將L1[1]的時延計數設為1、將在該陣列的剩餘位置中的時延計數設為0、並且將幀計數器設為下一幀，t＝2來初始化狀態時延計數的陣列457。然後，在步驟502，確定是否已評估所有的幀。如果確定已經評估了所有的幀，則結束更新過程(步驟504)。然而，如果確定沒有評估完所有的幀，將當前狀態n設為總的狀態數N(步驟508)來使流程開始於最後的狀態，使得首先評估最高的或者最後的狀態。例如，如圖14所示，根據本發明的另一個實施例，狀態n被設為4，使得評估開始於對應於幀2、狀態4的格子458(等價于格子464，468，472)的點處。
然後在步驟510，確定是否已經評估完所有狀態，也就是如果n＜1。如果已經評估完所有的狀態，則增加幀計數器，也就是幀t＝3(步驟512)，並且評估返回步驟502。然而，如果在步驟510沒有評估完所有狀態，在步驟514，使用維特比搜索方法執行對進入在幀t處的當前狀態n的最佳路徑的搜索。
正如在圖9和15中看到的一樣，根據本發明的另一個實施例的、用於使用數字編碼來更新存儲作為時延計數的跟蹤陣列的跟蹤信息的更新過程的步驟500-514與上面介紹的根據本發明的用於使用存儲位置來更新作為時延計數的跟蹤陣列的跟蹤信息的更新過程的步驟400-414相同。然而，根據本發明的另一個實施例，在用於利用圖15的數字編碼來更新存儲作為時延基數的跟蹤陣列的跟蹤信息的更新過程中，一旦在步驟514完成搜索最佳的路徑，結果被用來識別進入當前狀態n的最佳路徑是來自狀態m，步驟516。然後，在步驟518，用於當前狀態n的狀態時延計數被設為對應於前面狀態m對應的狀態時延計數位置Lm與B(n-1)的和的狀態時延計數。流程繼續前面的狀態n＝n-1，步驟520，然後，返回步驟510。
圖16為根據本發明的用於產生線性陣列的過程的流程圖，其被用於根據圖15的陣列更新過程的結果來存儲用於每一個幀的幀分配。根據本發明的另一個實施例，圖13的狀態時延計數陣列457被展開為線性陣列A[t]，該陣列具有對應於在被對準的表達中的幀總數的長度，類似於上面介紹的圖12的產生的線性陣列440。
一旦在步驟502確定已經評估所有的幀，並且結束了更新過程(圖15的步驟504)，根據本發明的另一個實施例，通過將當前幀t設為幀總數T、將當前狀態n設為狀態總數N來在圖16的步驟600初始化基於圖15的陣列更新過程的結果的、用於產生線性陣列的流程。如果(例如)從圖14的已更新的跟蹤陣列462產生線性陣列，狀態總數為4，並且幀總數等於在狀態時延計數位置L4中的各個基數-B數字的和。
由於對應於在狀態時延計數位置L4中的時延計數的數字已編碼的跟蹤信息為在狀態4中的兩個幀、和分別在每一狀態1、2和3中的一個幀，在狀態時延計數位置L4中的已編碼值為2111。在表達中的幀總數T等於5(2+1+1+1＝5)。可以理解，本發明的另一個實施例可以應用任意的狀態數和幀數，選定的用於狀態數和幀數的值僅僅是為了支持說明本發明的另一個實施例。
在初始化步驟600後，在步驟602，對應於當前狀態時延計數位置LN的數字已編碼跟蹤信息被複製，並且在步驟604確定已複製的跟蹤信息L是否大於或等於B(n-1)。如上所述，儘管在本發明的優選實施例中，B等於10，可以理解，可以使用任意的值B。然而，根據本發明的另一個實施例，在任意的狀態中的時延時間不能超過B個幀。
如果在步驟604確定了已複製的數字編碼的跟蹤信息L大於或等於B(n-1)，在步驟606中記錄用於線性陣列A[t]的相應的幀分配，在步驟608減當前幀t，在步驟610，已複製的跟蹤信息L被減掉對應於狀態n的基數-B的值B(n-1)，並且流程返回步驟604。
如果在步驟604確定了已複製的數字編碼的跟蹤信息L不大於或等於B(n-1)，在步驟612將當前狀態n減到前一狀態n-1，並且在步驟614確定是否已經評估所有的狀態。如果在步驟614確定已經評估所有的狀態，則流程使用前一狀態n-1來繼續步驟604，在步驟616結束線性陣列產生流程，得到圖12的線性陣列440。
儘管已經示出和介紹了本發明的特定的實施例，可以進行修改。因此，所附權利要求希望覆蓋落在本發明的精神和範圍內的所有的此類改變和修改。
權利要求
1.一種用於存儲和更新在語音識別系統中的格子跟蹤信息的方法，其包括步驟產生具有多行和一列或多列的跟蹤陣列，所述多行中的每一行對應於跟蹤路徑結束的多個狀態中的一個，並且所述一列或多列中的每一列包含用於在所述跟蹤路徑中的狀態的時延計數；確定進入所述多個狀態中的給定狀態的最佳的狀態轉移路徑；和響應所述已確定的最佳狀態轉移路徑，更新所述已產生的跟蹤陣列。
2.根據權利要求1的方法，進一步包括步驟響應於所述確定的最佳狀態轉移路徑為自身環狀態轉移路徑，增加包含在具有對應於所述給定狀態的行的第一列中的時延計數。
3.根據權利要求2的方法，進一步包括步驟將對應於在所述給定狀態前的第一在前狀態的行複製到對應於所述給定狀態的行中；和響應於所述已確定的最佳狀態轉移路徑為單步狀態轉移路徑，重設包含在具有對應於所述給定狀態的行的第一列中的時延計數為1。
4.根據權利要求3的方法，進一步包括步驟將對應於在所述給定狀態前的第二在前狀態的行複製到對應於所述給定狀態的行中；重設包含在具有對應於所述給定狀態的行的第一列中的時延計數為1；和響應於所述已確定的最佳狀態轉移路徑為單跳狀態轉移路徑，重設包含在對應於所述給定狀態的行中、不包括在所述已複製的行中的剩餘的時延計數為0。
5.根據權利要求4的方法，進一步包括步驟將對應於在所述給定狀態前的第三在前狀態的行複製到對應於所述給定狀態的行中；重設包含在具有對應於所述給定狀態的行的第一列中的時延計數為1；和響應於所述已確定的最佳狀態轉移路徑為雙跳狀態轉移路徑，重設包含在對應於所述給定狀態的行中、不包括在所述已複製的行中的剩餘的時延計數為0。
6.根據權利要求3的方法，進一步包括步驟將對應於在所述給定狀態前的n個狀態的一狀態的行複製到對應於所述給定狀態的行中；重設包含在具有對應於所述給定狀態的行的第一列中的時延計數為1；和響應於所述已確定的最佳狀態轉移路徑為n-1跳躍狀態轉移路徑，重設包含在對應於所述給定狀態的行中、不包括在所述已複製的行中的剩餘的時延計數為0。
7.根據權利要求6的方法，進一步包括步驟確定進入所述多個狀態中的每一個狀態的最佳狀態轉移路徑，開始於模型的所述最後狀態。
8.根據權利要求7的方法，進一步包括步驟對於每一個新的幀f，確定進入所述多個狀態中的每一個幀的最佳狀態轉移路徑。
9.根據權利要求8的方法，進一步包括步驟確定是否已經評估所有的幀；響應於確定已經評估所有幀，將當前幀t設等於幀總數T，並且將當前狀態n設為等於狀態總數N；將對應於具有被分配給在從狀態N向後跟蹤的路徑中的狀態n的幀數的當前計數器k設為等於狀態時延計數存儲位置LN[n]；確定是否已經對用於所述當前狀態n的所有狀態分配進行了計數；響應於沒有對所有的狀態分配進行了計數，記錄幀分配，減所述當前幀t和所述計數器k，並且返回到確定是否已經對用於所述當前狀態n的所有狀態分配進行了計數的步驟；響應於對用於所述當前狀態n的所有狀態分配進行了計數，確定所述當前狀態n；和確定是否已經評估所有的狀態，並且響應於沒有評估所有的狀態，返回到所述設定計數器k的步驟。
10.根據權利要求1的方法，進一步包括步驟設定當前狀態n為等於所述給定狀態；確定進入所述當前狀態n的最佳狀態轉移路徑位來自狀態m，其中m小於或等於n；和將對應於所述當前狀態、存儲作為基數-B的數字編碼值的狀態時延計數存儲位置設為等於對應於狀態m的狀態時延計數存儲位置與基數-B的值B(n-1)的和。
11.根據權利要求10的方法，進一步包括步驟確定進入所述多個狀態的每一個狀態的最佳狀態路徑，開始模型的所述最後步驟。
12.根據權利要求11的方法，進一步包括步驟對於每一個新的幀f，確定進入所述多個狀態的每一個狀態的最佳狀態轉移路徑。
13.根據權利要求12的方法，進一步包括步驟(i)將當前幀t設等於幀總數T，並且將當前狀態n設為等於狀態總數N；(ii)將來自對應於所述狀態總數N的狀態時延計數存儲位置的基數-B的數字編碼值的跟蹤信息進行複製；(iii)確定所述已複製的跟蹤信息是否大於或等於B(n-1)；(iv)記錄幀分配，減所述當前幀t，將所述已複製的跟蹤信息減掉對應於所述當前狀態的基數-B的值B(n-1)，並且響應於所述已複製的跟蹤信息大於或等於B(n-1)，返回到步驟(iii)；和(v)減所述當前狀態n，並且響應於所述已複製的跟蹤信息不大於或等於B(n-1)，確定是否已經評估了所有狀態；和(vi)響應於沒有評估完所有狀態，返回步驟(iii)。
14.根據權利要求13的方法，其中所述B等於10。
15.根據權利要求13的方法，其中所述B等於2的乘冪。
16.一種更新存儲作為時延計數的跟蹤陣列的跟蹤信息的方法，該方法包括步驟(i)確定是否已經評估所有幀；(ii)響應於沒有評估完所有幀，將當前狀態n設為等於狀態總數N；(iii)確定是否已經評估所有狀態；(iv)響應於評估完所有狀態，轉向下一幀，並且返回步驟(i)；(v)響應於沒有評估完所有狀態，執行對進入在幀t的所述當前狀態n的最佳路徑的搜索；和(vi)響應於搜索到所述最佳路徑，更新所述跟蹤陣列。
17.根據權利要求16所述的方法，進一步包括步驟(vii)確定所述最佳路徑是否來自當前狀態n；(viii)響應於所述最佳路徑來自所述當前狀態n，增加對應於所述當前狀態n的狀態時延計數存儲位置Ln[n]，減所述當前狀態n，並且返回到步驟(iii)；(ix)響應於在步驟(vii)確定所述最佳路徑不是來自當前狀態n，將所述最佳路徑設為來自前面的狀態m而不是來自所述當前狀態n，將對應於所述當前狀態n的所述狀態時延計數存儲位置Ln[n]設為等於1，並且前進到對應於所述當前狀態前n的狀態i的狀態時延計數存儲位置Ln[i]；(x)確定是否已經評估所有已跳過的狀態；(xi)響應於在步驟(x)確定沒有評估完所有已跳過的狀態，將狀態時延計數存儲位置Ln[i]設為等於0，減前一狀態i，並且返回步驟(x)；(xii)響應於在步驟(xi)確定已經評估所有已跳過的狀態，確定是否已經評估完所有狀態；(xiii)響應於在步驟(xii)確定沒有評估完所有狀態，減所述當前狀態n，並且返回步驟(iii)；和(xiv)響應於在步驟(xii)已經評估完所有狀態，將對應於所述在前狀態m的狀態時延計數存儲位置Lm[i]複製到狀態時延計數存儲位置Ln[i]，減狀態i，並且返回步驟(xii)。
18.根據權利要求17所述的方法，進一步包括步驟確定是否已經評估完所有幀；響應於已經評估完所有幀，將當前幀t設為等於幀總數T，並將當前狀態n設為等於狀態總數N；將對應於被分配給在來自狀態向後跟蹤N的路徑的狀態n的幀數的計數器k設為等於狀態時延計數存儲位置LN[n]；確定是否已經對用於所述當前狀態n的所有狀態分配進行了計數；響應於沒有對用於所述當前狀態n的所有狀態分配進行了計數，記錄幀分配，減所述當前幀t和所述計數器k，並且返回到確定是否已經對用於所述當前狀態n的所有狀態分配進行了計數的步驟；響應於已經對用於所述當前狀態n的所有狀態分配進行了計數，減所述當前狀態n；和響應於沒有評估完所有狀態，確定是否已經評估了所有狀態，並且返回到設置計數器k的步驟。
19.根據權利要求16的方法，進一步包括步驟(vii)將進入狀態n的所述最佳路徑設為來自狀態m，其中m小於或等於n；和(viii)將存儲作為基數-B數字編碼值的用於狀態n的狀態時延基數設為等於對應於狀態m的狀態時延計數位置與基數-B的值B(n-1)，減所述當前狀態n，並且返回步驟(iii)。
20.根據權利要求19的方法，進一步包括步驟(ix)將當前幀t設為等於幀總數T，並將當前狀態n設為等於狀態總數N；(x)複製來自對應於所述狀態總數N的狀態時延計數位置的基數-B數字編碼跟蹤信息；(xi)確定是否所述已複製的跟蹤信息大於或等於B(n-1)；(xii)響應於所述已複製的跟蹤信息大於或等於B(n-1)，記錄相應的幀分配，減所述當前幀t，將所述已複製的跟蹤信息減掉對應於所述當前狀態的基數-B的值B(n-1)，並且返回步驟(xi)；(xiii)響應於所述已複製的跟蹤信息不大於或等於B(n-1)，減所述當前狀態n，並且確定是否已經評估完所有狀態；和(xiv)響應於沒有評估完所有狀態，返回步驟(xi)。
21.根據權利要求20的方法，其中所述B等於10。
22.根據權利要求20的方法，其中所述B等於2的乘冪。
23.一種無線通信設備，其包括話筒；和連接到所述話筒以接收信號並且負責提供語音識別的處理器，所述處理器產生具有多行和一列或多列的跟蹤陣列，所述多行中的每一行對應於跟蹤路徑結束的多個狀態中的一個，且一列或多列中的每一列包含用於在所述跟蹤路徑中的狀態的時延計數，並且響應於進入所述多個狀態中的給定狀態的最佳狀態轉移路徑，所述處理器更新已產生的跟蹤陣列。
24.根據權利要求23的通信設備，其中所述處理器響應於所述最佳狀態轉移路徑為自身環狀態轉移路徑，增加包含在具有對應於所述給定狀態的行的第一列中的時延計數，響應於所述最佳狀態轉移路徑為單步狀態轉移路徑，將對應於在所述給定狀態前的第一在前狀態的行複製到對應於所述給定狀態的行中，並且將包含在具有對應於所述給定狀態的行的第一列中的時延計數重設為等於1，和響應於所述已確定的最佳狀態轉移路徑為n-1個跳躍狀態轉移路徑，將對應於在所述給定狀態前的n個狀態的狀態的行複製到對應於所述給定狀態的行，將包含在具有對應於所述給定狀態的行的第一列中的時延計數重設為等於1，並且將包含在對應於所述給定狀態的行中、不包括在所述已複製的行中的剩餘的時延計數重設為等於0。
25.根據權利要求23的通信設備，其中所述處理器將當前狀態n設為等於所述給定狀態，確定進入所述當前狀態的所述最佳狀態轉移路徑為來自狀態m，其中m小於或等於n，並且將被存儲作為基數-B的數字編碼值的、對應於所述當前狀態的狀態時延基數存儲位置設為等於對應於狀態m與基數-B的值B(n-1)的狀態時延基數存儲位置的和。
26.根據權利要求25的通信設備，其中所述B等於10。
27.根據權利要求25的通信設備，其中所述B等於2的乘冪。
全文摘要
包括語音識別系統(204，206，207，208)的設備(100)產生表示語音表達的信號。所述表達被劃分為表示所述表達的幀(Ft)。使用對準算法將幀分配給狀態(S1－S5)。使用識別對每一個狀態的狀態轉移的狀態轉移信息來將代表幀到狀態分配的路徑存儲在存儲器(110)中。通過產生具有多行和一列或多列的跟蹤陣列來存儲和更新用於語音識別系統的格子跟蹤信息，多行中的每一行對應於跟蹤路徑結束的多個狀態中的一個，並且每一列包含用於在跟蹤路徑中的一個或多個時延計數。進入多個狀態中的一個給定的狀態的最佳的狀態轉移路徑被確定，並且響應於所述已確定的最佳的狀態轉移路徑，更新已產生的跟蹤陣列。
文檔編號G10L15/08GK1524259SQ01808981
公開日2004年8月25日 申請日期2001年4月12日 優先權日2000年5月4日
發明者傑弗裡·梅烏涅爾, 丹尼爾·波佩特, 波佩特, 傑弗裡 梅烏涅爾 申請人:摩託羅拉公司