Patent US4977598A successfully refreshed from Google Patents.
US4977598A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient pruning algorithm for hidden markov model speech recognition
Assignee: Texas Instruments Inc
•
Filing: 1989-04-13
•
Granted: 1990-12-11
•
Expires: 2009-04-13
Abstract
Abstract An efficient pruning method reduces central processing unit (CPU) loading during real time speech recognition by instructing the CPU to compare a current state's previously calculated probability score against a predetermined threshold value and to discard hypothesis containing states with probability scores below such threshold. After determining that the current state should be kept, the CPU is directed to locate an available slot in the scoring buffer where information about the current state is then stored. The CPU locates an available slot by comparing the current time-index with the time-index associated with each scoring buffer slot. When they are equal, the slot is considered not available; when the current time-index is greater, the slot is considered available. After the information about the current state is stored, the CPU then sets the current state's backpointer to point at the start state of the current best path if the current states represents a completed model. Regardless of the current state's status, the CPU then associates the current time-index with the time-indices of all the slots along the best path to the current state. The CPU then proceeds to calculate the probability score of the next current state and the method repeats until all states have been completed.
Inventors
- 👤 George R. Doddington
- 👤 Basavaraj I. Pawate
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:51
CPC Classifications
G; G10; G10L; G10L15/00; G10L15/08; G10L15/14
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
186 words
A method for reducing loading of a central processing unit during speech recognition involving hierarchical layers of grammar and wherein models of those hierarchical layers employ a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising: (a) computing a score for the information-bearing current state; (b) comparing said score against a predetermined threshold value to determine whether said information-bearing current state should be retained; (c) locating an available slot in a scoring buffer having at least one slot; (d) storing information regarding said current state in said available slot; (e) setting a scoring buffer slot backpointer; (f) assigning a last-time field value in said available slot equal to a current time-index of the central processing unit; (g) propagating a time value equal to said current time-index back to all scoring buffer slots along a best path leading to said available slot containing information about said current state; (h) parsing a next current state; and (i) repeating steps (a) through (h) until all states have been completed.
Claim 2
Independent Claim
186 words
A method for reducing loading of a central processing unit during speech recognition involving hierarchical layers of grammar and wherein models of those hierarchical layers employ a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising: (a) computing a score for the information-bearing current state; (b) comparing said score against a predetermined threshold value to determine whether said information-bearing current state should be retained; (c) locating an available slot in a scoring buffer having at least one slot; (d) storing information regarding said current state in said available slot; (e) setting a scoring buffer slot backpointer; (f) assigning a last-time field value in said available slot equal to a current time-index of the central processing unit; (g) propagating a time value equal to said current time-index back to all scoring buffer slots along a best path leading to said available slot containing information about said current state; (h) parsing a next current state; and (i) repeating steps (a) through (h) until all states have been completed.
Claim 3
Dependent Claim
88 words
The method for reducing central processing unit loading of claim 1, said step (c) for locating an available slot further comprising: (j) reading a slot's last-time field value; (k) comparing said available slot's last-time field with said (l) indicating the slot is available if said current time-index minus one is less than said last-time field; (m) passing over the slot if said current time-index minus one is greater than or equal to said last-time field; and (n) repeating steps (j) through (m) until an available slot is located.
Claim 4
Dependent Claim
78 words
The method for reducing central processing unit loading of claim 1, said step (b) for comparing said score against a predetermined threshold value, further comprising: (o) if said score is greater than or equal to said predetermined threshold value, continuing on to step (c) of locating an available slot; and (p) if said score is less than said predetermined threshold, discarding said state and then returning to step (a) of computing a score for an information-bearing current state.
Claim 5
Dependent Claim
74 words
The method for reducing central processing unit loading of claim 1, said step (e) for setting a scoring buffer slot backpointer further comprising: (q) if said current state is from the top layer of a grammar, setting said backpointer to indicate a directly previous current state's scoring buffer slot address; and (r) if said current state is not from said top layer of a grammar, setting said backpointer to indicate said model's start state.
Claim 6
Dependent Claim
68 words
The method for reducing central processing unit loading of claim 1, said step (g) for propagating a time value equal to said current time-index back to all scoring buffer slots along the best path leading to said available slot containing information about said current state, wherein the location of said all scoring buffer slots along the best path leading to said available slot are indicated by said backpointer.
Claim 7
Independent Claim
212 words
A method for efficient pruning during speech recognition, wherein said speech recognition involves using hierarchical layers of grammar and wherein models of those hierarchical layers involve a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising: (s) computing the current state's score; (t) comparing said score against a predetermined threshold value, wherein if said score is greater than or equal to said predetermined threshold value, continuing on to step (u) and if said score is less than said predetermined threshold, discarding said state and returning to step (s); (u) locating an available scoring buffer slot; (v) storing information regarding said current state in said available slot; (w) setting a scoring buffer slot backpointer; (x) assigning a last-time field value in said available slot equal to a current time-index; (y) propagating a time value equal to said current time-index back to all scoring buffer slots along the best path leading to said available slot containing information about said current state, wherein the location of said all scoring buffer slots are indicated by said backpointer; (z) parsing a next current state; and (aa) repeating steps (s) through (z) until all states have been completed.
Claim 8
Independent Claim
212 words
A method for efficient pruning during speech recognition, wherein said speech recognition involves using hierarchical layers of grammar and wherein models of those hierarchical layers involve a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising: (s) computing the current state's score; (t) comparing said score against a predetermined threshold value, wherein if said score is greater than or equal to said predetermined threshold value, continuing on to step (u) and if said score is less than said predetermined threshold, discarding said state and returning to step (s); (u) locating an available scoring buffer slot; (v) storing information regarding said current state in said available slot; (w) setting a scoring buffer slot backpointer; (x) assigning a last-time field value in said available slot equal to a current time-index; (y) propagating a time value equal to said current time-index back to all scoring buffer slots along the best path leading to said available slot containing information about said current state, wherein the location of said all scoring buffer slots are indicated by said backpointer; (z) parsing a next current state; and (aa) repeating steps (s) through (z) until all states have been completed.
Claim 9
Dependent Claim
71 words
The method for efficient pruning of claim 6, said step (w) for setting a scoring buffer slot backpointer further comprising: (bb) if said current state is from the top layer of a grammar, setting said backpointer to indicate a directly previous current state's scoring buffer slot address; and (cc) if said current state is not from said top layer of a grammar, setting said backpointer to indicate said model's start state.
Claim 10
Independent Claim
258 words
A method for improved speech recognition, said speech recognition using hierarchical layers of grammar and models of those hierarchical layers of grammar employ a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising: (dd) computing said current state's score; (ee) comparing said score against a predetermined threshold value, wherein if said score is greater than or equal to said predetermined threshold value, continuing on to step (ff) and if said score is less than said predetermined threshold, discarding said state and returning to step (dd); (ff) locating an available scoring buffer slot; (gg) storing information regarding said current state in said available slot; (hh) setting a scoring buffer slot backpointer to indicate a directly previous current state's scoring buffer slot address if said current state is from the top layer of a grammar; (ii) setting a scoring buffer slot backpointer to indicate said model's start state if said current state is not from said top layer of said grammar; (jj) assigning a last-time field value in said available slot equal to a current time-index; (kk) propagating a time value equal to said current time-index back to all scoring buffer slots along the best path leading to said available slot containing information about said current state, wherein the location of said all scoring buffer slots are indicated by said backpointer; (ll) parsing the next current state; and (mm) repeating steps (dd) through (ll) until all states have been completed.
Claim 11
Independent Claim
258 words
A method for improved speech recognition, said speech recognition using hierarchical layers of grammar and models of those hierarchical layers of grammar employ a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising: (dd) computing said current state's score; (ee) comparing said score against a predetermined threshold value, wherein if said score is greater than or equal to said predetermined threshold value, continuing on to step (ff) and if said score is less than said predetermined threshold, discarding said state and returning to step (dd); (ff) locating an available scoring buffer slot; (gg) storing information regarding said current state in said available slot; (hh) setting a scoring buffer slot backpointer to indicate a directly previous current state's scoring buffer slot address if said current state is from the top layer of a grammar; (ii) setting a scoring buffer slot backpointer to indicate said model's start state if said current state is not from said top layer of said grammar; (jj) assigning a last-time field value in said available slot equal to a current time-index; (kk) propagating a time value equal to said current time-index back to all scoring buffer slots along the best path leading to said available slot containing information about said current state, wherein the location of said all scoring buffer slots are indicated by said backpointer; (ll) parsing the next current state; and (mm) repeating steps (dd) through (ll) until all states have been completed.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-12-10 | 1994-06-11 | 1994-12-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-12-10 | 1998-06-11 | 1998-12-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-12-10 | 2002-06-11 | 2002-12-11 | $7700.00 | Window Closed / Lapsed |