Apparatus and methods for analyzing transitions in finite state machines

• US 4,829,575 A
• Filed: 11/12/1986
• Issued: 05/09/1989
• Est. Priority Date: 11/12/1985
• Status: Expired due to Fees

• Current Assignee: National Research Development Corporation
• Original Assignee: National Research Development Corporation
• Inventors: Lloyd, Alexander H.
• Primary Examiner(s): Salce, Patrick R.
• Assistant Examiner(s): VOELTZ, EMANUEL T
• Application Number:
  US06/929,474
• Time in Patent Office: 909 Days
• Field of Search: 381/41-50, 382/1, 364/513.5
• US Class Current: 704/238
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G10L 15/14 using statistical models, e.g. Hidden Markov Models [HMMs] G10L15/18 takes precedence

Abstract

In speech recognition words to be recognized may be represented by finite state machines and recognition is based on analyzing transitions through the machines as an utterance occurs. One value which is then required for each state of each machine in a timescale which is compatible with continuous speech recognition is minimum cumulative distance; that is the smallest of values dependent on reaching one of the states from a starting position, considering all possible paths. In the present invention a specially constructed Viterbi engine is provided for calculating cumulative distances at high speed. Latch circuits holding pointers allow a RAM to be read to provide, for a current machine state, both stored cumulative distances of states with transitions to that state and stored penalties corresponding to the transitions. A logic circuit comprising an ALU finds the cumulative distance for each path as far as the current state, selectes the minimum and adds another penalty dependent on the current state. Thus a minimum cumulative distance is provided for storage and for a speech recognition decision making circuit. The process is repeatedly carried out for each state of each machine. The total number of iterations of the engine in reaching each minimum cumulative distance is also held in the RAM and updated by the logic circuit.

Claims

1. Apparatus for finding minimum cumulative distances in a finite state machine, comprising:

indicator circuit means for indicating positions in an external store of minimum cumulative distance of all originating states, which are states having transitions to a current state whose minimum cumulative distance is to be found, and for indicating the positions in the external store of corresponding transition penalties, corresponding to these transitions,

logic circuit means for determining, for each transition to the current state, a value dependent on the minimum cumulative distance for each originating state and the corresponding transition penalty, for determining a minimum said value for the current state and for determining a minimum cumulative distance for the current state from said minimum said value and a state penalty for the current state; and

control circuit means for controlling an operation of the indicator mean to supply minimum cumulative distances and penalties to the logic means, for controlling the logic means, on receipt of a command signal, to determine the minimum cumulative distances of all states.

2. Apparatus according to claim 1 wherein

the indicator means comprising first, second and third storage means for storing a cumulative distance pointer, an offset pointer, and a transition penalty pointer, for indicating locations in the external store of the cumulative distance of the current state, an incremental address of a cumulative distance of a selected originating state from the location of a cumulative address of the current state and a location of the transition penalty corresponding to the tramsition between the selected originating state and the current, respectively, and

the control circuit means is also for obtaining a currently required minimum cumulative distance of an originating state from the location in the external store whose address is obtained by using the logic circuit mean to add the offset at the location indicated by the offset pointer to the address of the location indicated by the cumulative distance pointer.

3. Apparatus according to claim 1 for finding minimum cumulative distances in a number of finite state machines where transitions may occur between the said machines,

including storage means forming the said external store, and wherein

the control circuit means is arranged to cause the logic circuit means to determine the minimum cumulative distance of each state of each machine,

the storage means is arranged to store score values dependent on minimum cumulative distances and transition penalties relating to two categories of additioned states;

that is a start state and an end state for each machine, the end state having transitions from all states which may transit to other finite state machines, and the start state having transitions to all states which may be reached from other finite state machines, and

the logic means is arranged to determine each said machine a value representing the minimum cumulative distance to the end state, and for storing a score value dependent on the smallest of the minimum cumulative distances of the end states as the score values of the start states of selected ones of the finite state machines, the logic means storing relatively high values for the other start states.

4. Apparatus for use in speech recognition according to claim 3, wherein

a part of the storage means is arranged to store quantities dependent on analysis of sound received at successive instants, and

the logic means is arranged to obtain the said state penalties by using an index to interrogate the said part of the storage means.

5. Apparatus for finding minimum cumulative distances in a predetermined number of finite state machines, all having the same number of states and the same pattern of transitions, comprising:

storage means for storing minimum cumulative distances, and a number of address offsets, one for, and corresponding to, each transition to each state,

logic means for determining, for each transition to a current state of a selected finite state machine, a cumulative distance value dependent on an originating state from which said each transitions originates and a stored minimum cumulative distance for the originating state, and for obtaining the stored minimum cumulative distances of the originating states from the address of the stored minimum cumulative distance of the current state by using the address offsets, and

control means for causing the logic means to determine said cumulative distance values for each transition to each state of each machine, and selecting a minimum said cumulative distance value for each state and transferring the minimum said cumulative distance values to the storage means as updated values of the stored minimum cumulative distances.

6. Apparatus according to claim 5 wherein

the storage means is arranged to store transition penalties and state penalties, and

the logic means is arranged to determine each said cumulative distance value by using a process which includes determining the minimum of the sums for each originating state of the stored minimum cumulative distance for that state and the transition penalty from that state to the current state.

7. Apparatus according to claim 6 for use in analysing a plurality of finite state machines, wherein

the storage means is arranged to store values dependent on minimum cumulative distances and transition penalties relating to two categories of additioned states;

that is a start state and an end state for each machine, the end state having transitions from all states which may transit to other finite state machines, and the start state having transitions to all states which may be reached from other finite state machines, and

the logic means is arranged to determine for each said machine a value representing the minimum cumulative distance to the end state, and for storing a score value dependent on the smallest of the minimum cumulative distances of the end states as the score values of the start states of selected ones of the finite state machines, the logic means storing relatively high values for the other start states.

8. Apparatus according to claim 7 wherein the logic means is arranged to select those finite state machines which are to have start states set with a smallest said score value, on the basis of whether one word is likely to follow another.

9. Apparatus according to claim 7 for use in analysing the finite state machines, wherein

the logic means is arranged to determine repeatedly values representative of the said minimum cumulative distances of each state of each word and to determine for each state an indication representative of the number of iterations which have taken place to reach that state from a starting state while accruing the said minimum cumulative distance,

the logic means is arranged to determine the score value of each end state from the minimum cumulative distance of that state and a value dependent on the said indication for that state, and

the storage means is arranged to store at least the current values of the said indications.

10. Apparatus according to claim 9 wherein the logic means is arranged

to subtract the smallest minimum cumulative distance found in the previous iteration of determining minimum cumulative distances for all states of all machines from the minimum cumulative distance found in the current iteration to obtain the minimum cumulative distances stored by the storage means, to cease increasing any of the minimum cumulative distances stored by the storage means which reaches the maximum value which the storage means can hold, and

to cease subtracting the smallest cumulative distance found in the previous iteration from any stored minimum cumulative distance which has reached the said maximum value.

11. A method of finding minimum cumulative distances in a predetermined number of finite state machines all having the same number of states and the same pattern of transitions, comprising the steps of:

storing minimum cumulative distances and a number of address offsets, one for, and corresponding to, each transition to each state,

determining of each transition to a current state of a selected finite machine, a cumulative value dependent on an originating state from which that transition originates and a stored minimum cumulative distance for the originating state, the stored minimum cumulative distances of the originating states being obtained from the address of the stored minimum cumulative distance of the current state by using the address offsets, and

determining said cumulative distance values for each transition to each state of each machine, selecting a minimum of said cumulative distance value for each state and storing minimum values as updated values of the stored minimum cumulative distances.

12. A method according to claim 11 including the further step of

storing transition penalties and state penalties, and obtaining each said cumulative distance value by using a process which includes determining the minimum of sums for each originating state of the stored minimum cumulative distance for that state and a transition penalty from that state to the current state.

13. A method according to claim 12 for use in analysing a plurality of finite state machines wherein transitions may occur between finite state machines, including storing score values dependent on minimum cumulative distances and transition penalties relating to two categories of additional states;

that is a start state and an end state for each machine, the end state having transitions from all states which may transit to another finite state machine and the start state having transitions to all states which may be reached from other finite state machines,

determining, for each said machine, a value representing the minimum cumulative distance to the end state and

storing a score value dependent on the smallest of the minimum cumulative distances of the end states as the score values of the start states of selected ones of the finite state machines, relatively high values being stored for the other start states.

14. A method according to claim 13 including

repeatedly determining values representative of the said minimum cumulative distances of each state of each machine,

determining for each state of each machine an indication of the number of iterations which have taken place to reach that state from a starting state while accruing the said minimum cumulative distance for that state, and

determining the score value for each end state from the minimum cumulative distance of that state and a value dependent on the said indication for that state.

15. Apparatus for use in analysing a plurality of finite state machines where transitions may occur between finite state machines, comprising

storage means for storing representations of a plurality of finite state machines wherein three types of states are stored for each said machine:

normal states, a start state and an end state, the normal states being those states required to represent a said machine, the end state having transitions from all normal states which may transit to other finite state machines, and the start state having transitions to all states which may be reached from other finite state machines, and

for determining for each said machine a score value dependent on the minimum cumulative distance to the end state, and for transferring to the storage means the smallest of the score values as the score value of the start states of selected ones of the finite state machines, the logic means transferring to the storage means relatively high values for the other start states.

17. Apparatus according to claim 15 wherein the logic means is arranged to select those finite state machines which are to have start states set with the said smallest score value on the basis of whether one word is likely to follow another.

18. Apparatus according to claim 15 for use in analysing the finite state machines, wherein

the logic means is arranged to determine repeatedly values representative of the said minimum cumulative distances of each state of each word and to determine for each state an indication representative of the number of iterations which have taken place to reach that state from a starting state while accruing the said minimum cumulative distance,

the logic means is arranged to determine the score value of each end state from the minimum cumulative distance of that state and a value dependent on the said indication for that state, and

the storage means is arranged to store at least the current values of the said indications.

19. Apparatus according to claim 18 for analysing finite state machines which are of the type which do not allow transition in one direction, wherein

the logic means is arranged to determine, in each iteration, the minimum cumulative distances in a single pass from the final state to the first, updating the minimum cumulative distances and the corresponding numbers of iterations which have occurred while making the pass.

20. Apparatus according to claim 18 wherein the logic means is arranged

to subtract the smallest minimum cumulative distance found in the previous iteration of determining minimum cumulative distances for all states of all machines from the minimum cumulative distance found in the current iteration to obtain the minimum cumulative distances stored by the storage means,

to cease increasing any of the minimum cumulative distances stored by the storage means which reaches the maximum value which the storage means can hold, and

to cease subtracting the smallest cumulative distance found in the previous iteration from any stored minimum cumulative distance which has reached the said maximum value.

21. Apparatus for use in speech recognition according to claim 15 wherein

the storage means is also for storing transition penalties and state penalties,

the logic means is also for determining each said value by using a process which includes determining the minimum of the sums for each originating state of the stored minimum cumulative distance for that state and the transition penalty from that state to the current state, a part of the storage means being arranged to store quantities dependent on analysis of sound received, and

the logic means is also for obtaining said state penalties by using an index to interrogate said part of the storage means.

16. A method for use in analysing transitions in a plurality of finite state machines where transitions may occur between finite state machines, comprising the steps of

storing representations of a plurality of finite state machines wherein three types of states are stored for each said machine:

normal states, a start state and an end state, the normal states being those states required to represent a said machine, the end state having transitions from all normal states which may transit to another finite state machine and the start state having transitions to all states which may be reached from other finite state machines,

determining, for each said machine, a value representing the minimum cumulative distance to the end state and

storing a score value dependent on the smallest of the minimum cumulative distances of the end states as the score values of the start states of selected ones of the finite state machines, relatively high values being stored for the other start states.

22. Apparatus for finding minimum cumulative distances in a finite state machine, comprising:

indicator circuit means for indicating positions in an external store of minimum cumulative distances of all originating states, which are states having transitions to a current state whose minimum cumulative distances is to be found, and for indicating the positions in the external store of corresponding transition penalties, corresponding to these transitions, the indicator means comprising first, second and third storage means for storing a cumulative distance pointer, an offset pointer, and a transition penalty pointer, for indicating locations in the external store of the cumulative distance of the current state, an incremental address of a cumulative distance of a selected originating state and the current, respectively;

logic circuit means for determining, for each transition to the current state, a value dependent on the minimum cumulative distance for each originating state and the corresponding transition penalty, for determining a minimum said value for the current state and for determining a minimum cumulative distance for the current state from said minimum said value and a state penalty for the current state; and

control circuit means for controlling an operation of the indicator means for supplying minimum cumulative distances and transition penalties to the logic means, for controlling the logic means, on receipt of a command signal, to determine the minimum cumulative distances of all states, and for obtaining a currently required minimum cumulative distances of an originating state from the location in the external store whose address is obtained by using the logic current means to add the offset at the location indicated by the offset pointer to the address of the location indicated by the cumulative distance pointer.