Method for synthesizing linear finite state machines
First Claim
1. A method of transforming an original linear finite state machine circuit including a plurality of memory elements coupled in series and linear logic gates coupled between some of the memory elements, and a feedback connection coupled from a source tap at an output of one of the memory elements to a destination tap coupled to an input of another of the memory elements, comprising:
- shifting the source tap of the feedback connection to the right or left along the series of memory elements; and
shifting the destination tap of the feedback connection in a same direction as the source tap to generate a transformed linear finite state machine.
2 Assignments
0 Petitions
Accused Products
Abstract
Method and apparatus for synthesizing high-performance linear finite state machines (LFSMs) such as linear feedback shift registers (LFSRs) or cellular automata (CA). Given a characteristic polynomial for the circuit, the method obtains an original LFSM circuit such as a type I or type II LFSR. Feedback connections within the original circuit are then determined. Subsequently, a number of transformations that shift the feedback connections can be applied in such a way that properties of the original circuit are preserved in a modified LFSM circuit. In particular, if the original circuit is represented by a primitive characteristic polynomial, the method preserves the maximum-length property of the original circuit in the modified circuit and enables the modified circuit to produce the same m-sequence as the original circuit. Through the various transformations, a modified LFSM circuit can be created that provides higher performance through shorter feedback connection lines, fewer levels of logic, and lower internal fan-out.
-
Citations
19 Claims
-
1. A method of transforming an original linear finite state machine circuit including a plurality of memory elements coupled in series and linear logic gates coupled between some of the memory elements, and a feedback connection coupled from a source tap at an output of one of the memory elements to a destination tap coupled to an input of another of the memory elements, comprising:
-
shifting the source tap of the feedback connection to the right or left along the series of memory elements; and
shifting the destination tap of the feedback connection in a same direction as the source tap to generate a transformed linear finite state machine. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method of transforming an original linear finite state machine, comprising:
-
providing an original linear finite state machine having multiple memory elements coupled in series with one or more linear logic gates coupled between some of the memory elements;
identifying a feedback connection including a source tap at one end of the feedback connection, the source tap being an output of one of the memory elements, and a destination tap at an opposite end of the feedback connection, the destination tap being an input to one of the memory elements; and
shifting the feedback connection across the memory elements to transform the linear finite state machine. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
17. A system of transforming an original linear finite state machine, comprising:
-
means for identifying a feedback connection in the linear finite state machine; and
means for shifting the feedback connection to transform the linear finite state machine. - View Dependent Claims (18, 19)
-
Specification