Re-programmable finite state machine

• US 20040054848A1
• Filed: 09/16/2002
• Published: 03/18/2004
• Est. Priority Date: 09/16/2002
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Emulex Design & Manufacturing Corp. (Broadcom, Inc.)
• Inventors: Folsom, Brian Robert
• Granted Patent: US 7,173,452 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G05B 19/045 using logic state machines, consisting only of a memory or a programmable logic device containing the logic for the controlled machine and in which the state of its outputs is dependent on the state of its inputs or part of its own output states, e.g. binary decision controllers, finite state controllers
• CPC Class Codes: G05B 2219/23289 State logic control, finite state, tasks, machine, fsm

Abstract

A re-programmable finite state machine comprising a content-addressable memory (“CAM”) and a read/write memory output array (“OA”). In operation, the CAM receives and periodically latches a status vector, and generates a match vector as a function of the status vector and a set of stored compare vectors. In response, the OA selects for output one of a set of a control vector as a function of the match vector. A state vector portion of the selected control vector is forwarded to the CAM as a portion of the status vector. An output vector portion of the selected control vector controls the operation of external components. Both the set of stored compare vectors and the set of control vectors are fully re-programmable.

Claims

1. A re-programmable finite state machine (“

RFSM”

) comprising;

a content addressable memory (“

CAM”

) comprising;

a compare register adapted to store a status vector to be matched; and

a compare array adapted to store a plurality of compare vectors, and to generate as an output a match vector as a function of respective bits of said status vector and said compare vectors; and

an output array adapted to store a plurality of control vectors, and to select for output one of said control vectors as a function of said match vector, a first portion of said selected control vector comprising a portion of said status vector and a second portion of said selected control vector comprising an output vector.

2. The RFSM of claim 1 wherein the compare register is comprised of a plurality of edge-triggered flip-flops, each adapted to store, in synchronization with a clock signal, respective bits of said status vector.

3. The RFSM of claim 2 wherein said status vector comprises a state vector portion and an input vector portion.

4. The RFSM of claim 1 wherein the compare array is comprised of a plurality of match elements, each comprising:

a compare latch, comprised of a plurality of RWM cells, adapted to store a selected one of said compare vectors, and

compare logic which generates as an output a respective bit of said match vector as a function of respective bits of the status vector and the stored compare vector.

5. The RFSM of claim 4 wherein each of said compare vectors is comprised of a state compare portion and an input compare portion.

6. The RFSM of claim 1 wherein the CAM is further characterized as a ternary CAM.

7. A re-programmable finite state machine (“

RFSM”

) comprising;

a content addressable memory (“

CAM”

) comprising;

a compare register adapted to store a status vector to be matched;

a status mask adapted to store a status mask, and to generate a masked status vector as a function of the status vector and the status mask;

a compare array adapted to store a plurality of compare vectors, and to generate as an output a match vector as a function of respective bits of said masked status vector and said compare vectors;

a match mask adapted to store a match mask, and to generate a masked match vector as a function of the match vector and the match mask; and

an output array adapted to store a plurality of control vectors, and to select for output one of said control vectors as a function of said masked match vector, a first portion of said selected control vector comprising a portion of said status vector and a second portion of said selected control vector comprising an output vector.

8. The RFSM of claim 7 wherein the compare register is comprised of a plurality of edge-triggered flip-flops, each adapted to store, in synchronization with a clock signal, respective bits of said status vector.

9. The RFSM of claim 8 wherein said status vector comprises a state vector portion and an input vector portion.

10. The RFSM of claim 7 wherein the compare array is comprised of a plurality of match elements, each comprising:

a compare latch, comprised of a plurality of RWM cells, adapted to store a selected one of said compare vectors, and

compare logic which generates as an output a respective bit of said match vector as a function of respective bits of the masked status vector and the stored compare vector.

11. The RFSM of claim 10 wherein each of said compare vectors is comprised of a state compare portion and an input compare portion.

12. The RFSM of claim 7 wherein the CAM is further characterized as a ternary CAM.

13. A re-programmable finite state machine (“

RFSM”

) comprising;

a content addressable memory (“

CAM”

) comprising;

a compare register adapted to store a status vector to be matched;

a status mask adapted to store a status mask, and to generate a masked status vector as a function of the status vector and the status mask;

a compare array adapted to store a plurality of compare vectors, and to generate as an output a match vector as a function of respective bits of said masked status vector and said compare vectors;

a match mask adapted to store a match mask, and to generate a masked match vector as a function of the match vector and the match mask; and

an encoder adapted to generate an address as a function of the masked match vector; and

an output array adapted to store a plurality of control vectors, and to select for output one of said control vectors as a function of said address, a first portion of said selected control vector comprising a portion of said status vector and a second portion of said selected control vector comprising an output vector.

14. The RFSM of claim 13 wherein the compare register is comprised of a plurality of edge-triggered flip-flops, each adapted to store, in synchronization with a clock signal, respective bits of said status vector.

15. The RFSM of claim 14 wherein said status vector comprises a state vector portion and an input vector portion.

16. The RFSM of claim 13 wherein the compare array is comprised of a plurality of match elements, each comprising:

a compare latch, comprised of a plurality of RWM cells, adapted to store a selected one of said compare vectors, and

compare logic which generates as an output a respective bit of said match vector as a function of respective bits of the masked status vector and the stored compare vector.

17. The RFSM of claim 16 wherein each of said compare vectors is comprised of a state compare portion and an input compare portion.

18. The RFSM of claim 13 wherein the CAM is further characterized as a ternary CAM.