Method for synthesizing linear finite state machines
US6353842B1 · kind B1 · utility
Inventors
Key dates
| Filing date | Jul 20, 2000 |
| Grant date | Mar 5, 2002 |
| Priority date | — |
| Expiry date | Jul 20, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2207/583
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.