Method for synthesizing linear finite state machines

• US 20070294327A1
• Filed: 08/20/2007
• Published: 12/20/2007
• Est. Priority Date: 11/23/1999
• Status: Active Grant

• Current Assignee: Siemens Industry Software Limited (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Mukherjee, Nilanjan, Tyszer, Jerzy, Rajski, Janusz, Kassab, Mark
• Granted Patent: US 8,024,387 B2
• Time in Patent Office: Days
• 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-19. -19. (canceled)

20. A computer-readable medium storing computer-executable instructions for performing the following:

obtaining a first layout of a linear finite state machine, the first layout of the linear finite state machine including a plurality of serially coupled memory elements and one or more feedback connections, each of the one or more feedback connections coupling an output of a respective one of the memory elements to inputs of one or more respective other ones of the memory elements; and

performing one or more transformations of the one or more feedback connections to transform the first layout of the linear finite state machine into a second layout of the linear finite state machine, the combined length of the feedback connections in the second layout of the linear finite state machine being less than the combined length of the feedback connections in the first layout of the linear finite state machine, the second layout of the linear finite state machine further being capable of providing a same output sequence as the first layout of the linear finite state machine.

21. The computer-readable medium of claim 20, wherein one of the one or more transformations performed involves shifting a source tap and a destination tap of a respective feedback connection in a same direction.

22. The computer-readable medium of claim 20, wherein one of the one or more transformations performed involves adding a new feedback connection.

23. The computer-readable medium of claim 20, wherein the linear finite state machine is a type I linear feedback shift register, type II linear feedback shift register, or cellular automata.

24. The computer-readable medium of claim 20, wherein the act of performing the one or more transformations reduces the internal fan-out in the linear finite state machine.

25. The computer-readable medium of claim 20, wherein the one or more feedback connections couple the output of a respective one of the memory elements to the inputs of the one or more respective other ones of the memory elements via logic gates.

26. The computer-readable medium of claim 25, wherein the act of performing the one or more transformations reduces the levels of the logic gates in the linear finite state machine.

27. The computer-readable medium of claim 20, wherein the act of obtaining the first layout of the linear finite state machine comprises obtaining the first layout of the linear finite state machine from secondary storage or memory.

28. A linear finite state machine synthesized by the method of claim 20.

29. A computer-readable medium storing computer-executable instructions for performing the following:

obtaining a first layout of a linear finite state machine, the first layout of the linear finite state machine including a plurality of serially coupled memory elements and at least one feedback connection coupling an output of a source memory element in the linear finite state machine to respective inputs of two or more destination memory elements in the linear finite state machine; and

transforming the first layout of the linear finite state machine into a second layout of the linear finite state machine by performing one or more transformations to the at least one feedback connection, the one or more transformations reducing the fan-out of the at least one feedback connection by replacing an original connection between the output of the source memory element and the input of one of the destination memory elements with a shifted version of the original connection.

30. The computer-readable medium of claim 29, wherein the source memory element and the destination memory element of the shifted version of the original connection are a same number of memory elements away from the source memory element and the destination memory element of the original connection.

31. The computer-readable medium of claim 29, wherein the linear finite state machine is a type I linear feedback shift register, type II linear feedback shift register, or cellular automata.

32. The computer-readable medium of claim 29, wherein the length of the shifted version of the original connection is less than the length of the original connection.

33. The computer-readable medium of claim 29, wherein the act of transforming the first layout of the linear finite state machine into a second layout of the linear finite state machine comprises reducing the number of linear logic gates in the at least one feedback connection.

34. The computer-readable medium of claim 29, wherein the act of transforming the first layout of the linear finite state machine into a second layout of the linear finite state machine comprises reducing the number of linear logic gates in the at least one feedback connection to one.

35. The computer-readable medium of claim 29, wherein the second layout of the linear finite state machine is capable of generating a same output sequence as the first layout of the linear finite state machine.

36. The computer-readable medium of claim 29, wherein the act of obtaining the first layout of the linear finite state machine comprises obtaining the first layout of the linear finite state machine from secondary storage or memory.

37. A linear finite state machine synthesized by the method of claim 29.

38. A system, comprising:

means for obtaining a first layout of a linear finite state machine, the first layout of the linear finite state machine including a plurality of serially coupled memory elements and one or more feedback connections, each of the one or more feedback connections coupling an output of a respective one of the memory elements to inputs of one or more respective other ones of the memory elements; and

means for performing one or more transformations of the one or more feedback connections to transform the first layout of the linear finite state machine into a second layout of the linear finite state machine, the combined length of the feedback connections in the second layout of the linear finite state machine being less than the combined length of the feedback connections in the first layout of the linear finite state machine, the second layout of the linear finite state machine further being capable of providing a same output sequence as the first layout of the linear finite state machine.

39. The system of claim 38, wherein the means for performing the one or more transformations reduces the levels of logic gates in the linear finite state machine.