Finite state-machine employing a content-addressable memory

• US 5,125,098 A
• Filed: 10/06/1989
• Issued: 06/23/1992
• Est. Priority Date: 10/06/1989
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Sanders Associates, INC. (BAE Systems Plc)
• Inventors: Burrows, James L.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Pollack, Caleb
• Application Number:
  US07/418,412
• Time in Patent Office: 991 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/800
• US Class Current: 711/108
• CPC Class Codes: G11C 8/00 Arrangements for selecting an address in a digital store for stores using transistors G11C11/407, G11C11/413

Abstract

A finite-state machine (30), which receives its input on INPUT lines (32) and generates its output on OUTPUT lines (34), is implemented with a content-addressable memory (46), whose output is the address of the location containing the data word presented to the content-addressable memory as its input. The content-addressable memory'"'"'s input data word is the concatenation of the finite-state-machine input and the content-addressable-memory output, while the content-addressable-memory output is the output of the finite-state machine.

Claims

1. A finite-state machine, operable in cycles, comprising:

A. a content-addressable memory, including a key-word port comprising a feedback port and machine input port, at least one output port, and a plurality of storage locations having respective output words associated therewith, for (i) operating in one mode to receive key-word and location-identification signals and to store the key words represented by the key-word signals in the locations identified by the location-identification signals and (ii) operating in another mode to generate at its output port, in response to reception at its key-word port of an input representing a key word, a memory output representing the output word associated with the storage location that contains the key word represented by the input signals at the key-word port;

B. feedback means for applying to the feedback port during a current cycle a feedback signal determined by the memory output of the previous cycle; and

C. output means for generating a machine output determined by the memory output,

whereby the finite-state machine generates a machine output determined by the previous memory output and a machine input received at the machine input port.

2. A finite-state machine as defined in claim 1 wherein the feedback means includes:

A. a random-access memory, including a data port, an address port connected to receive at least part of the memory output of the content-addressable memory, and a plurality of RAM locations containing data contents and having unique addresses associated therewith, for generating at its data port data signals representative of the contents of the RAM location associated with the address represented by the signals received at its address input port; and

B. means for applying at least part of the data signals of the previous cycle to the feedback port as the feedback signal of the current cycle.

3. A finite-state machine as defined in claim 2 wherein the output means includes the random-access memory and means for providing at least part of the data signals as the machine output.

4. A finite-state machine as defined in claim 2 wherein:

A. each storage location of the content-addressable memory is associated with a unique address; and

B. the memory output is a decoded representation of the address associated with the storage location that contains the key word represented by signals at the key-word port.

5. A finite-state machine as defined in claim 2 wherein:

A. each storage location of the content-addressable memory is associated with a unique address; and

B. the memory output is an encoded representation of the address associated with the storage location that contains the key word represented by signals at the key-word port.

6. A finite-state machine as defined in claim 1 wherein the output means includes:

A. a random-access memory, including a data port, an address port connected to receive at least part of the memory output of the content-addressable memory, and a plurality of RAM locations containing data contents and having unique addresses associated therewith, for generating at its data port data signals representative of the contents of the RAM location associated with the address represented by the signals received at its address input port; and

B. means for providing at least part of the data signals as the machine output.

7. A finite-state machine as defined in claim 6 wherein the feedback means comprises means for applying at least part of the memory output of the previous cycle to the feedback port as the feedback signal of the current cycle.

8. A finite-state machine as defined in claim 6 wherein:

A. each storage location of the content-addressable memory is associated with a unique address; and

B. the memory output is a decoded representation of the address associated with the storage location that contains the key word represented by signals at the key-word port.

9. A finite-state machine as defined in claim 6 wherein:

A. each storage location of the content-addressable memory is associated with a unique address; and

B. the memory output is an encoded representation of the address associated with the storage location that contains the key word represented by signals at the key-word port.

10. A finite-state machine as defined in claim 1 wherein the output word associated with each storage location is a unique address thereof.