Hidden markov model processing engine

• US 9,817,881 B2
• Filed: 10/16/2013
• Issued: 11/14/2017
• Est. Priority Date: 10/16/2013
• Status: Active Grant

• Current Assignee: Cypress Semiconductor Corporation (Infineon Technologies AG)
• Original Assignee: Cypress Semiconductor Corporation (Infineon Technologies AG)
• Inventors: Bapat, Ojas A., Fastow, Richard M., Olson, Jens, Kumatani, Kenichi
• Primary Examiner(s): Shah, Paras D
• Assistant Examiner(s): Blankenagel, Bryan
• Application Number:
  US14/054,884
• Publication Number:
  US 20150106405A1
• Time in Patent Office: 1,490 Days
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G10L 15/14 using statistical models, e.g. Hidden Markov Models [HMMs] G10L15/18 takes precedence
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]
• CPC Class Codes: G10L 15/30 Distributed recognition, e.g. in client-server systems, for mobile phones or network applications

Abstract

A method, apparatus, and tangible computer readable medium for processing a Hidden Markov Model (HMM) structure are disclosed herein. For example, the method includes receiving Hidden Markov Model (HMM) information from an external system. The method also includes processing back pointer data and first HMM states scores for one or more NULL states in the HMM information. Second HMM state scores are processed for one or more non-NULL states in the HMM information based on at least one predecessor state. Further, the method includes transferring the second HMM state scores to the external system.

Claims

1. A method comprising:

receiving, at an external processing unit, speech from a user;

processing the speech via an acoustic modeling process and a phoneme evaluation process;

scoring Hidden Markov Models (HMMs) in association with the phoneme evaluation process by the following;

receiving, at a co-processing unit, HMM information from an external processing unit, wherein the HMM information is derived from a plurality of HMMs, each HMM having a different type of data structure, wherein the different structures comprise Ergodic HMM structures, left-to-right structures, and parallel path left-to-right HMM structures;

formatting, with the co-processing unit, the HMM information from each of the plurality of HMMs into a common HMM data structure to access the HMM information based on a priori knowledge of one or more fields and one or more indices in the common HMM data structure, wherein the formatting comprises formatting HMM information from at least one of a plurality of fields of the plurality of HMMs into the common HMM data structure;

processing, with the co-processing unit, back pointer data and first HMM state scores for one or more NULL states in the common HMM data structure, each NULL state being a non-emitting state identified by a state-type flag;

after processing the back pointer data and the first HMM state scores for each of the one or more NULL states in the common HMM data structure, processing, with the co-processing unit, second HMM state scores for one or more non-NULL states in the common HMM data structure based on at least one predecessor state;

transferring the second HMM state scores from the co-processing unit to the external processing unit; and

outputting, via the external processing unit, decoded speech based on the second HMM state scores.

2. The method of claim 1, further comprising:

updating the back pointer data based on the HMM information associated with the one or more non-NULL states; and

transferring the updated back pointer data to the external processing unit.

3. The method of claim 1, wherein the external processing unit comprises a memory device, and the receiving comprises receiving the HMM information via a single read access from the memory device.

4. The method of claim 1, wherein the formatting comprises formatting an HMM identification, a number of states associated with an HMM structure, a best score associated with the HMM structure, a state pointer for each of the one or more NULL and non-NULL states, an observation probability for each of the one or more non-NULL states, a path pointer for each of the one or more plurality of NULL states and one or more non-NULL states, and the state-type flag for each of the one or more plurality of NULL states and one or more non-NULL states, or a combination thereof for each of the plurality of HMMs into the common HMM data structure.

5. The method of claim 1, wherein the processing the back pointer data comprises updating the back pointer data with a back pointer of a predecessor state having the best incoming probability, wherein the best incoming probability is based on a state score and a transition probability associated with one or more predecessor states.

6. The method of claim 1, wherein the processing the second HMM state scores comprises summing a maximum value associated with one or more predecessor states and an observation probability associated with the one or more non-NULL states, wherein the maximum value is based on a state score and a transition probability associated with the one or more predecessor states.

7. The method of claim 1, wherein the processing the first HMM state scores comprises selecting a maximum value associated with one or more predecessor states, wherein the maximum value is based on a state score and a transition probability associated with the one or more predecessor states.

19. The method of claim 1, wherein the formatting further comprises:

accessing the HUM information in the common HMM data structure based on byte index locations for each of the one or more fields in the common HMM data structure.

8. An apparatus comprising:

an interface device configured to;

receive Hidden Markov Model (HMM) information from an external processing unit, wherein the external processing unit is configured to receive speech from a user and further configured to process the speech via an acoustic modeling process and a phoneme evaluation process, wherein the HMM information is derived from a plurality of HMMs, each HMM having a different type of data structure, and wherein the different structures comprise Ergodic HMM structures, left-to-right structures, and parallel path left-to-right HMM structures; and

format the HMM information from each of the plurality of HMMs into a common HMM data structure to access the HMM information based on a priori knowledge of one or more fields and one or more indices in the common HMM data structure wherein the formatting comprises formatting HMM information from at least one of a plurality of fields of the plurality of HMMs into the common HMM data structure;

a processing device comprising;

a state type fetch module configured to determine a presence of one or more NULL and non-NULL states in the common HMM data structure, each NULL state being a non-emitting state identified by a state-type flag;

a processing module configured to;

process back pointer data and first HMM state scores for the one or more NULL states;

after back pointer data and first HMM state scores have been processed for each of the one or more NULL states, process second HMM state scores for one or more non-NULL states based on at least one predecessor state;

an output list module configured to transfer the second HMM state scores to the external processing unit, wherein the external processing unit outputs decoded speech based on the second HMM state scores; and

a memory device configured to store the HMM information.

9. The apparatus of claim 8, wherein the processing device comprises:

an input list module configured to provide the HMM information from the interface device to the state type module and the processing module.

10. The apparatus of claim 8, wherein the processing module is configured to:

update the back pointer data based on the HMM information associated with the one or more non-NULL states; and

transfer the updated back pointer data to the output list module.

11. The apparatus of claim 8, wherein the state type fetch module is configured to determine the presence of the NULL and non-NULL states in the HMM information based on the common HMM data structure comprising an HMM identification, a number of states associated with an HMM structure, a best score associated with the HMM structure, a state pointer for each of the NULL and non-NULL states, an observation probability for each of the one or more non-NULL states, a path pointer for each of the NULL and non-NULL states, and the state-type flag for each of the NULL and non-NULL states, or a combination thereof.

12. The apparatus of claim 8, wherein the processing module is configured to update the back pointer data with a back pointer of a predecessor state having the best incoming probability, wherein the best incoming probability is based on a state score and a transition probability associated with one or more predecessor states.

13. The apparatus of claim 8, wherein the processing module is configured to sum a maximum value associated with one or more predecessor states and an observation probability associated with the one or more non-NULL states, wherein the maximum value is based on a state score and a transition probability associated with the one or more predecessor states.

14. The apparatus of claim 8, wherein the processing module is configured to select a maximum value associated with one or more predecessor states, wherein the maximum value is based on a state score and a transition probability associated with the one or more predecessor states.

15. A tangible, non-transitory computer readable medium having stored therein one or more sequences of one or more instructions for execution by one or more processors to perform a method for processing a common Hidden Markov Model (HMM) data structure, the method comprising:

receiving speech from a user;

processing the speech via an acoustic modeling process and a phoneme evaluation process;

scoring Hidden Markov Models (HMM) in association with the phoneme evaluation process by the following;

receiving, at a co-processing unit, HMM information from an external processing unit, wherein the HMM information is derived from a plurality of HMMs, each HMM having a different type of data structure wherein the different structures comprise Ergodic HMM structures, left-to-right structures, and parallel path left-to-right HMM structures;

formatting, with the co-processing unit, the HMM information from each of the plurality of HMMs into a common HMM data structure to access the HMM information based on a priori knowledge of one or more fields and one or more indices in the common HMM data structure, wherein the formatting comprises formatting HMM information from at least one of a plurality of fields of the plurality of HMMs into the common HMM data structure;

processing, with the co-processing unit, back pointer data and first HMM state scores for NULL states in the common HMM data structure, each NULL state being a non-emitting state identified by a state-type flag;

after processing the back pointer data and the first HMM state scores for each of the NULL states, processing, with the co-processing unit, second HMM state scores for one or more non-NULL states in the common HMM data structure based on at least one predecessor state;

transferring the second HMM state scores from the co-processing unit to the external processing unit; and

outputting decoded speech based on the second HMM state scores.

16. The tangible, non-transitory computer readable medium of claim 15, wherein the method further comprises:

updating the back pointer data based on the HMM information associated with the one or more non-NULL states; and

transferring the updated back pointer data to the external processing unit.

17. The tangible, non-transitory computer readable medium of claim 15, wherein the external processing unit comprises a memory device, and the receiving comprises receiving the HMM information via a single read access from the memory device.

18. The tangible, non-transitory computer readable medium of claim 15, wherein the formatting comprises formatting an HMM identification, a number of states associated with an HMM structure, a best score associated with the HMM structure, a state pointer for each of the NULL and non-NULL states, an observation probability for each of the one or more non-NULL states, a path pointer for each of the NULL and non-NULL states, and the state-type flag for each of the NULL and non-NULL states, or a combination thereof for each of the plurality of HMMs into the common HMM data structure.