Method for synthesizing linear finite state machines

• US 6,539,409 B2
• Filed: 09/18/2001
• Issued: 03/25/2003
• Est. Priority Date: 11/23/1999
• Status: Expired due to Term

• Current Assignee: Siemens Industry Software Limited (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Mukherjee, Nilanjan, Tyszer, Jerzy, Rajski, Janusz, Kassab, Mark
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/957,701
• Publication Number:
  US 20020016806A1
• Time in Patent Office: 553 Days
• Field of Search: 708/252, 708/250
• US Class Current: 708/252
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

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.

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.

2. The method of claim 1, wherein the second linear finite state machine is a type I LFSR.

3. The method of claim 1, wherein the second linear finite state machine is a type II LFSR.

4. The method of claim 1, wherein the second linear finite state machine is a cellular automation.

5. The method of claim 1, wherein transforming includes shifting at least one of the feedback connections between different memory elements.

6. The method of claim 1, wherein the feedback includes a feedback connection line having source and destination taps and wherein transforming includes shifting the source and destination taps across a number of memory elements.

7. The method of claim 6, wherein the source tap and destination tap of the feedback connection are shifted across a same number of memory elements.

8. The method of claim 6, wherein shifting the taps of a feedback connection includes reducing the length of the associated feedback connection line.

9. The method of claim 6, wherein shifting the taps of a feedback connection includes reducing the levels of linear logic gates in the original circuit.

10. The method of claim 6, wherein shifting the taps of a feedback connection includes reducing the internal fan-out of the original circuit.

11. The method of claim 1, wherein the original circuit is a maximum-length linear feedback shift register producing a maximum-length output sequence, and the modified circuit is capable of providing the same maximum length sequence as the original circuit.

12. The method of claim 1, wherein the linear logic elements include XOR or XNOR gates.

13. The method of claim 1, wherein the memory elements include flip-flops.

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.

15. The method of claim 14, wherein the first linear finite state machine includes 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.

16. The method of claim 14, wherein the second linear finite state machine is a type I LFSR.

17. The method of claim 14, wherein the second linear finite state machine is a type II LFSR.

18. The method of claim 14, wherein the second linear finite state machine is a cellular automation.