Method for synthesizing linear finite state machines
First Claim
1. A method for synthesizing a linear feedback shift register (LFSR), comprising:
- obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining a feedback connection in the original circuit, the feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line; and
shifting the source and destination taps of the feedback connection across a number of memory elements in the same direction, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
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.
129 Citations
35 Claims
-
1. A method for synthesizing a linear feedback shift register (LFSR), comprising:
-
obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining a feedback connection in the original circuit, the feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line; and
shifting the source and destination taps of the feedback connection across a number of memory elements in the same direction, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A computer-readable medium on which is stored computer-readable instructions for performing the following:
-
obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining a feedback connection in the original circuit, the feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line; and
shifting the source and destination taps of the feedback connection across a number of memory elements in the same direction, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
-
20. A method for synthesizing a linear finite state machine, comprising:
-
obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining a feedback connection in the original circuit, a feedback connection spanning a number of memory elements and including a source tap and a plurality of destination taps that each include a destination linear logic gate, the taps connected by associated feedback connection lines; and
splitting the feedback connection into corresponding separate feedback connections by;
splitting the source tap into at least two source taps; and
shifting one of the source taps and one of the destination taps across a number of memory elements, thereby transforming the original circuit into a modified linear finite state machine circuit having a smaller internal fan-out than the original circuit yet capable of providing the same output sequence as the original circuit. - View Dependent Claims (21, 22)
-
-
23. A method for synthesizing a linear finite state machine, comprising:
-
obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining at least first and second feedback connections in the original circuit, each feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line, the destination tap including a destination linear logic gate;
shifting the source and destination taps of the second feedback connection to the left, the source tap of the second feedback connection crossing the destination linear logic gate of the first feedback connection; and
adding a feedback connection line between the source tap of the first feedback connection and a destination linear logic gate at the shifted destination tap of the second feedback connection, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
-
24. A method for synthesizing a linear finite state machine, comprising:
-
obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining at least first and second feedback connections in the original circuit, each feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line, the destination tap including a destination linear logic gate;
shifting the source and destination taps of the second feedback connection to the right, the source tap of the second feedback connection crossing the destination linear logic gate of the first feedback connection; and
adding a feedback connection line between the source tap of the first feedback connection and a destination linear logic gate at the initial destination tap of the second feedback connection, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of generating the same output sequence as the original circuit.
-
-
25. A method for synthesizing a linear finite state machine, comprising:
-
obtaining an original linear feedback shift register circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining at least first and second feedback connections in the original circuit, each feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line, the destination tap including a destination linear logic gate;
shifting the source and destination taps of the first feedback connection to the left, the destination tap of the first feedback connection crossing the source tap of the second feedback connection; and
adding a feedback connection line between the initial source tap of the first feedback connection and a destination linear logic gate at the destination tap of the second feedback connection, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
-
26. A method for synthesizing a linear finite state machine, comprising:
-
obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining at least first and second feedback connections in the original circuit, each feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line, the destination tap including a destination linear logic gate;
shifting the source and destination taps of the first feedback connection, the destination tap of the first feedback connection crossing the source tap of the second feedback connection; and
adding a feedback connection line between the shifted source tap of the first feedback connection and a destination linear logic gate at the destination tap of the second feedback connection, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
-
27. A method for synthesizing a linear finite state machine, comprising:
-
obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
determining at least first and second feedback connections in the original circuit, each feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line, the destination tap including a destination linear logic gate;
shifting the source and destination taps of the feedback connections relative to one another such that the destination tap of the first feedback and the source tap of the second feedback connection cross; and
adding a feedback connection line between a source tap of the first feedback connection and a destination linear logic gate at a destination tap of the second feedback connection, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit. - View Dependent Claims (28, 29, 30, 31)
-
-
32. An apparatus for synthesizing a linear finite state machine, comprising:
-
means for obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
means for determining a feedback connection in the original circuit, the feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line; and
means for shifting the source and destination taps of the feedback connection across a number of memory elements in the same direction, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
-
33. An apparatus for synthesizing a linear finite state machine, comprising:
-
means for obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
means for determining at least first and second feedback connections in the original circuit, each feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line, the destination tap including a destination linear logic gate;
means for shifting the source and destination taps of the feedback connections relative to one another such that the destination tap of the first feedback and the source tap of the second feedback connection cross; and
means for adding a feedback connection line between a source tap of the first feedback connection and a destination linear logic gate at a destination tap of the second feedback connection, thereby transforming the original circuit to a linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
-
34. A method for synthesizing a linear finite state machine, the method comprising the following steps:
-
a step for obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence;
a step for determining a feedback connection in the original circuit, the feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line; and
a step shifting the source and destination taps of the feedback connection across a number of memory elements in the same direction, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
-
35. A method for synthesizing a linear finite state machine, comprising:
-
a step for obtaining an original linear finite state machine circuit, the circuit including a plurality of memory elements and linear logic gates;
a step for determining at least first and second feedback connections in the original circuit, each feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line, the destination tap including a destination linear logic gate;
a step for shifting the source and destination taps of the feedback connections relative to one another such that the destination tap of the first feedback and the source tap of the second feedback connection cross; and
a step for adding a feedback connection line between a source tap of the first feedback connection and a destination linear logic gate at a destination tap of the second feedback connection, thereby transforming the original circuit to a modified linear finite state machine circuit that is capable of providing the same output sequence as the original circuit.
-
Specification