HIDDEN MARKOV MODEL PROCESSING ENGINE

• US 20150106405A1
• Filed: 10/16/2013
• Published: 04/16/2015
• Est. Priority Date: 10/16/2013
• Status: Active Grant

• Current Assignee: Cypress Semiconductor Corporation (Infineon Technologies AG)
• Original Assignee: Spansion LLC (Infineon Technologies AG)
• Inventors: BAPAT, Ojas, Fastow, Richard, Olson, Jens, Kumatani, Kenichi
• Granted Patent: US 9,817,881 B2
• Time in Patent Office: Days
• US Class Current: 707/795
• 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 Hidden Markov Model (HMM) information from an external system;

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

processing second HMM state scores for one or more non-NULL states in the HMM information based on at least one predecessor state; and

transferring the second HMM state scores to the external system.

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 system.

3. The method of claim 1, wherein the external system 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 receiving 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 NULL and non-NULL states, and a state-type flag for each of the one or more NULL and non-NULL states, or a combination thereof in a data format known by an HMM processing engine.

5. The method of claim 1, wherein the receiving comprises receiving HMM information associated with different types of HMM structures.

6. 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.

7. 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.

8. 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.

9. An apparatus comprising:

a state type fetch module configured to determine a presence of one or more NULL and non-NULL states in HMM information;

a processing module configured to;

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

process second HMM state scores for one or more non-NULL states based on at least one predecessor state; and

an output list module configured to transfer the second HMM state scores to an external system.

10. The apparatus of claim 9, further comprising:

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

11. The apparatus of claim 9, 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.

12. The apparatus of claim 9, wherein the state type fetch module is configured to determine the presence of the one or more NULL and non-NULL states in the HMM information based on a predetermined data format 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 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 NULL and non-NULL states, and a state-type flag for each of the one or more NULL and non-NULL states, or a combination thereof.

13. The apparatus of claim 9, 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.

14. The apparatus of claim 9, 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.

15. The apparatus of claim 9, 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.

16. A tangible 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 Hidden Markov Model (HMM) structure, the method comprising:

receiving HMM information from an external system;

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

process second HMM state scores for one or more non-NULL states in the HMM information based on at least one predecessor state; and

transferring the second HMM state scores to the external system.

17. The tangible computer readable medium of claim 16, 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 system.

18. The tangible computer readable medium of claim 16, wherein the external system comprises a memory device, and the receiving comprises receiving the HMM information via a single read access from the memory device.

19. The tangible computer readable medium of claim 16, wherein the receiving 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 NULL and non-NULL states, and a state-type flag for each of the one or more NULL and non-NULL states, or a combination thereof in a data format known by an HMM processing engine.

20. The tangible computer readable medium of claim 16, wherein the receiving comprises receiving HMM information associated with different types of HMM structures.