Method for synthesizing linear finite state machines
First Claim
1. A method to create a linear finite state machine, comprising:
- providing a first linear finite state machine including multiple memory elements coupled in series, wherein at least a portion of the memory elements have linear logic elements coupled therebetween and wherein at least a portion of the memory elements provide feedback to the linear logic elements; and
transforming the first linear finite state machine to a second linear finite state machine having a different circuit structure, but which provides the same output sequence as the first linear finite state machine, wherein the second linear finite state machine has a fan-out no greater than two and a number of linear logic elements between the memory elements that is no greater than one.
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
18 Claims
-
1. A method to create a linear finite state machine, comprising:
-
providing a first linear finite state machine including multiple memory elements coupled in series, wherein at least a portion of the memory elements have linear logic elements coupled therebetween and wherein at least a portion of the memory elements provide feedback to the linear logic elements; and
transforming the first linear finite state machine to a second linear finite state machine having a different circuit structure, but which provides the same output sequence as the first linear finite state machine, wherein the second linear finite state machine has a fan-out no greater than two and a number of linear logic elements between the memory elements that is no greater than one. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method to synthesize a linear finite state machine, comprising:
transforming a first linear finite state machine to a different, second linear finite state machine, which provides the same output sequence as the first linear finite state machine, wherein the second linear finite state machine has a fan-out no greater than two and a number of linear logic elements between memory elements that is no greater than one. - View Dependent Claims (15, 16, 17, 18)
Specification