US5228040A — Testable implementations of finite state machines…

Claim 1

Independent Claim 130 words

Apparatus which implements a given finite state machine, the given finite state machine requiring a set of m memory elements, m≧1, and the apparatus comprising: first means for implementing the given finite state machine, the first means including the set of m memory elements; and second means for implementing a test finite state machine, the second means being able to set and/or read the memory elements in the set of m memory elements, the first means and the second means being produced from a merged finite state machine which is obtained by merging the given finite state machine with the test finite state machine, whereby operation of the apparatus may be tested by employing the second means to set and/or read memory elements in the set of m memory elements.

Claim 2

Dependent Claim 130 words

Apparatus which implements a given finite state machine, the given finite state machine requiring a set of m memory elements, m≧1, and the apparatus comprising: first means for implementing the given finite state machine, the first means including the set of m memory elements; and second means for implementing a test finite state machine, the second means being able to set and/or read the memory elements in the set of m memory elements, the first means and the second means being produced from a merged finite state machine which is obtained by merging the given finite state machine with the test finite state machine, whereby operation of the apparatus may be tested by employing the second means to set and/or read memory elements in the set of m memory elements.

Claim 3

Dependent Claim 54 words

The apparatus set forth in claim 1 wherein: the test finite state machine has one or more states and can be set to each of the states and each of the states of the test finite state machine can be observed at an output by applying one of a plurality of predetermined input sequences.

Claim 4

Dependent Claim 45 words

The apparatus set forth in claim 2 wherein: the test finite state machine has N=2 m states, each state may be reached in response to one of the predetermined input sequences, and reaching the state produces an output sequence which is unique for the state.

Claim 5

Dependent Claim 31 words

The apparatus set forth in claim 3 wherein: none of the predetermined input sequences has a length greater than log k N, where k is a design parameter such that 2≦k≦N.

Claim 6

Dependent Claim 19 words

The apparatus set forth in claim 4 wherein: k is chosen from the lower portion of the range 2≦k≦N.

Claim 7

Dependent Claim 138 words

The apparatus set forth in claim 4 wherein: the test finite state machine has k distinctly different inputs p1, p2, . . . pk and k distinctly different outputs q1, q2, . . . qk where log k N is an integer; the N states are divided into k equal groups G1, G2, . . . Gk; each state has k outgoing edges, one of the outgoing edges in each state going to one of the states in each of the groups G1, G2, . . . Gk, and k incoming edges, one of the incoming edges in each state coming from one of the states in each of the groups G1, G2, . . . Gk; and each edge represents a state transition which has a distinctly different combination of an input pi and an output qj.

Claim 8

Dependent Claim 31 words

The apparatus set forth in claim 1 wherein: the first means includes a component other than the set of m memory elements; and the second means also includes the other component.

Claim 9

Dependent Claim 17 words

The apparatus set forth in claim 7 wherein: the other component is an input or an output.

Claim 10

Dependent Claim 112 words

The apparatus which implements the given finite state machine set forth in claim 1, 7, 8, 2, 3, 4, 5, or 6, wherein the second implementation is merged with the first implementation by performing the steps of: producing a first state graph specifying first state transitions for the given finite state machine; producing a second state graph specifying second state transitions for the test finite state machine; producing a third state graph by adding new transitions to the first state graph such that all of the first state transitions and all of the second state transitions are present in the third state graph; and producing the apparatus from the third state graph.

Claim 11

Dependent Claim 43 words

The apparatus set forth in claim 9 wherein: the step of producing the third state graph includes the step of determining a minimal number of the new transitions and adding only the minimal number of the new transitions to the first state graph.

Claim 12

Independent Claim 171 words

A method for producing apparatus which implements a given finite state machine which requires a first set of m memory elements, m≧1, the method comprising the steps of: defining a test finite state machine, the test finite state machine requiring a second set of m memory elements and being capable of setting and/or reading the m memory elements in the second set; defining a testable finite state machine by merging the test finite state machine and the given finite state machine such that the testable finite state machine has a third set of m memory elements which serves as both the first set and the second set; and producing the apparatus from the definition of the testable finite state machine, the apparatus including an implementation of the third set, whereby the test finite state machine implemented in the testable implementation may be employed to set and/or read the m memory elements in the implementation of the third set and thereby to test the given finite state machine implemented in the apparatus.

Claim 13

Independent Claim 171 words

A method for producing apparatus which implements a given finite state machine which requires a first set of m memory elements, m≧1, the method comprising the steps of: defining a test finite state machine, the test finite state machine requiring a second set of m memory elements and being capable of setting and/or reading the m memory elements in the second set; defining a testable finite state machine by merging the test finite state machine and the given finite state machine such that the testable finite state machine has a third set of m memory elements which serves as both the first set and the second set; and producing the apparatus from the definition of the testable finite state machine, the apparatus including an implementation of the third set, whereby the test finite state machine implemented in the testable implementation may be employed to set and/or read the m memory elements in the implementation of the third set and thereby to test the given finite state machine implemented in the apparatus.

Claim 14

Dependent Claim 122 words

The method for producing the apparatus which implements the given finite state machine set forth in claim 11 wherein: the given finite state machine further requires a first set of further components; the step of defining a test finite state machine defines the test finite state machine to require a second set of further components; the step of defining a testable finite state machine merges the test finite state machine and the given finite state machine such that a third set of further components serves as both the first set of further components and the second set thereof; and the step of producing the apparatus produces the apparatus such that the apparatus includes an implementation of the third set of further components.

Claim 15

Dependent Claim 42 words

The method for producing apparatus which implements the given finite state machine set forth in claim 12 wherein: the step of producing the apparatus produces the apparatus such that the implementation of the third set of further components includes inputs and/or outputs.

Claim 16

Dependent Claim 73 words

The method for producing apparatus which implements the given finite state machine set forth in claim 11 wherein: the test finite state machine is defined such that the test finite state machine has one or more states and can be set to each of the states and each of the states of the test finite state machine can be observed at an output by applying one of a plurality of predetermined input sequences.

Claim 17

Dependent Claim 64 words

The method of producing apparatus which implements the given finite state machine set forth in claim 14 wherein: the test finite machine is further defined such that the test finite state machine has N=2 m states, each state may be reached in response to one of the predetermined input sequences, and reaching the state produces an output sequence which is unique for the state.

Claim 18

Dependent Claim 51 words

The method for producing apparatus which implements the given finite state machine set forth in claim 15 wherein: the test finite state machine is further defined such that none of the predetermined input sequences has a length greater than log k N, where k is a design parameter such that 2≦k≦N.

Claim 19

Dependent Claim 39 words

The method for producing apparatus which implements the given finite state machine set forth in claim 16 wherein: the test finite state machine is further defined such that k is chosen from the lower porion of the range 2≦k≦N.

Claim 20

Dependent Claim 158 words

The method for producing apparatus which implements the given finite state machine set forth in claim 15 wherein: the test finite state machine is further defined such that the test finite state machine has k distinctly different input p1, p2, . . . pk and k distinctly different outputs q1, q2, . . . qk where log k N is an integer; the N states are divided into k equal groups G1, G2, . . . Gk; each state has k outgoing edges, one of the outgoing edges in each state going to one of the states in each of the groups G1, G2, . . . Gk, and k incoming edges, one of the incoming edges in each state coming from one of the states in each of the groups G1, G2, . . . Gk; and each edge represents a state transition which has a distinctly different combination of an input pi and an output qj.

Claim 21

Dependent Claim 112 words

The method for producing apparatus which implements the given finite state machine set forth in claim 11, 12, 13, 14, 15, 16, 17, or 18, wherein the step of defining the testable finite state machine include the steps of: producing a first state graph specifying first state transitions for the given finite state machine; producing a second state graph specifying second state transitions for the test finite state machine; and producing a third state graph for the testable finite state machine by adding new transitions to the first state graph such that all of the first state transitions and all of the second state transitions are present in the third state graph.

Claim 22

Dependent Claim 41 words

The method of claim 19 wherein: the step of producing the third state graph includes the step of determining a minimal number of the new transitions and adding only the minimal number of the new transitions to the first state graph.

Claim 23

Dependent Claim 168 words

Apparatus which implements a given finite state machine which requires a set of m memory elements, m≧1, the apparatus being produced by performing steps comprising: defining a test finite state machine, the test finite state machine requiring a second set of m memory elements and being capable of setting and/or reading the m memory elements in the second set; defining a testable finite state machine by merging the test finite state machine and the given finite state machine such that the testable finite state machine has a third set of m memory elements which serves as both the first set and the second set; and producing the apparatus from the definition of the testable finite state machine, the apparatus including an implementation of the third set, whereby the test finite state machine implemented in the testable implementation may be employed to set and/or read the m memory elements in the implementation of the third set and thereby to test the given finite state machine implemented in the apparatus.

Claim 24

Dependent Claim 168 words

Apparatus which implements a given finite state machine which requires a set of m memory elements, m≧1, the apparatus being produced by performing steps comprising: defining a test finite state machine, the test finite state machine requiring a second set of m memory elements and being capable of setting and/or reading the m memory elements in the second set; defining a testable finite state machine by merging the test finite state machine and the given finite state machine such that the testable finite state machine has a third set of m memory elements which serves as both the first set and the second set; and producing the apparatus from the definition of the testable finite state machine, the apparatus including an implementation of the third set, whereby the test finite state machine implemented in the testable implementation may be employed to set and/or read the m memory elements in the implementation of the third set and thereby to test the given finite state machine implemented in the apparatus.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1996-07-12	1997-01-11	1997-07-13	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2000-07-12	2001-01-11	2001-07-13	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2004-07-12	2005-01-11	2005-07-13	$7700.00	Window Closed / Lapsed

Testable implementations of finite state machines and methods for producing them

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag