Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-07-20
2002-03-05
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06353842
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to linear finite state machines and, more particularly, to the synthesis of such machines.
BACKGROUND
Linear finite state machines (LFSMs) such as linear feedback shift registers (LFSRs) and cellular automata (CA) are often used generating for pseudo-random sequences. Such devices are well known in the art and are amply described in a number of references such as V. N. Yarmolik and S. N. Demidenko,
Generation and Application of Pseudorandom Sequences for Random Testing
, J. Wiley and Sons, New York, 1988. An LFSR includes memory elements such as flip-flops and linear logic gates such as XOR or XNOR gates connected as shown in FIG.
1
. An LFSR of length n can be represented mathematically by its characteristic polynomial h
n
x
n
+h
n-1
x
n-1
+. . . +h
0
, where the term h
i
x
i
refers to the ith flip-flop of the register, such that, if h
i
=1, then there is a feedback tap taken from this flip-flop. Also, h
0
=1. When the proper tap connections are established in accordance with the given polynomial, the combined (added modulo
2
) output of each stage is fed back to the first stage of the LFSR. Such an implementation is called a type I LFSR or Fibonacci generator. To initiate the operation of the LFSR, a nonzero n-bit vector (frequently called a seed) is loaded into the register, and a clock is pulsed at the appropriate rate. An LFSR initialized as described above can cycle through a number of states before coming back to the initial state. If an n-bit LFSR can cycle through all possible
2
n
−1 nonzero states, then its characteristic polynomial is called a primitive characteristic polynomial. Such an LFSR is often referred to as a maximum-length LFSR, and the resultant output sequence is termed a maximum-length sequence or m-sequence. M-sequences have a number of unique properties, as described in P. H. Bardell, W. H. McAnney, and J. Savir,
Built
-
In Test for VLSI. Pseudorandom Techniques
, John Wiley & Sons, 1987.
An alternative LFSR implementation is shown in FIG.
2
. It is called a type II LFSR or Galois true divisor. A distinct feature of this implementation is that the output of the last stage of the LFSR is fed back to prior stages as indicated by the characteristic polynomial employed. As with a type I LFSR, a type II LFSR constructed in accordance with a primitive characteristic polynomial and loaded with a nonzero n-bit vector will produce all
2
n
−1 nonzero states.
When the output is taken from the last stage of a type I or type II LFSR constructed in accordance with the same primitive characteristic polynomial, then the resulting m-sequences are different. The same m-sequences can be obtained, however, if a given primitive characteristic polynomial and its reciprocal are use to implement the type I and type II LFSRs, respectively, and both registers are properly initialized.
LFSMs such as the LFSRs described above are employed in a vast variety of applications, including error detection and correction, data transmission, mobile telephony, cryptography, testing of very large scale integrated circuits, data compression, and hardware white noise generation. For high-performance applications, the required data generation and compression can only be achieved by high-performance circuits. The highest operating speeds of conventional LFSR-based generators, encoders, decoders or compactors are limited by the performance of their respective elements. For a type I LFSR, performance is limited by the depth (i.e., number of levels) of the combinational logic in its feedback path. For a type II LFSR, performance is limited by buffers in the feedback path needed to compensate for internal fan-out on the output of the last stage. In addition, the buffers slow the circuit's operation. In both types of LFSRs, the limitations are especially pronounced for LFSRs having a characteristic polynomial with a large number of terms.
Attempts have been made to improve the performance of conventional LFSRs. Several are described in P. H. Bardell, “Design Considerations for Parallel Pseudorandom Pattern Generators,”
Journal of Electronic Testing: Theory and Applications
, No. 1, pp. 73-87, 1990. Others are described in various U.S. patents. For example, a linear pseudo-random test pattern generator that is aimed at generating all
2
n
vectors using an LFSR enhanced by means of external circuitry is disclosed in the U.S. Pat. No. 4,974,184. The scheme employs a switching circuit added to the feedback network of the register to produce and insert into a suitable position the so-called “stuck-state” which cannot be obtained by means of the conventional linear finite state machines. Typically, the stuck-state consists of an all-Os pattern that can be conveniently employed in several testing approaches (e.g., a memory test).
U.S. Pat. No. 5,268,949 describes a pseudo-random test pattern generator having a higher operating speed than the conventional LFSRs. The speed of any LFSR is determined by the performance of the respective elements comprising the generator. In particular, an XOR feedback network may introduce significant delays if an LFSR features a large number of feedback taps. The patent proposes the use of a number of LFSRs connected in parallel fashion and operated at lower clock speed, wherein the actual output signals are produced on the multiplex basis. However, this architecture has much larger area overhead than typical LFSRs and its performance is still limited by multiplexers in the output function. U.S. Pat. No. 5,412,665 describes another parallel-operation high-speed test pattern generation and test response compaction implemented by means of low-speed components. It utilizes a number of flip-flops and connected combinational logic networks. Each network provides a pseudo-random pattern which is output in parallel, thereby creating a high-speed data flow with an increased area of the circuitry.
U.S. Pat. No. 5,466,683 describes a programmable LFSR that produces pseudo-random patterns having a variable characteristic polynomial. Its sequence generator is driven by applying appropriate control signals in such a way that a given control signal has a value of 1 if the corresponding term of the characteristic polynomial has a coefficient of 1. Consequently, the proposed scheme places an XOR gate and associated two-way multiplexer in the front of each LFSR stage, thus incurring significant area overhead. A similar architecture of a programmable LFSR with a provision for an initialization circuitry is given in U.S. Pat. No. 5,090,035.
U.S. Pat. No. 5,790,626 describes a bidirectional LFSR employing latches having dual (forward and reverse) inputs. This LFSR can generate both state trajectories: the forward sequence of patterns, and the reverse one corresponding to an original feedback polynomial and its reciprocal counterpart, respectively. The register features two different linear feedback networks that operate exclusively at a time, but can intermix forward and reverse steps, thus allowing the vector generation process to follow the native sequence of the LFSR in both directions at any time. A similar concept is also disclosed in the U.S. Pat. No. 5,719,913, where the XOR gates in the feedback network are driven by multiplicity of two-way multiplexers.
None of these prior attempts, however, provides an optimal solution to the performance limitations noted above and found in presents LFSMs.
SUMMARY
In one aspect of the invention, a method for synthesizing a linear feedback shift register (LFSR) includes the following steps. An original linear finite state machine circuit is obtained, the circuit including a plurality of memory elements and linear logic gates and capable of generating an output sequence. Feedback connections in the original circuit are determined, a feedback connection spanning a number of memory elements and including a source tap and destination tap connected by an associated feedback connection line. The source and destination taps of one or more of the feedback
Kassab Mark
Mukherjee Nilanjan
Rajski Janusz
Tyszer Jerzy
Klarquist & Sparkman, LLP
Malzahn David H.
LandOfFree
Method for synthesizing linear finite state machines does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for synthesizing linear finite state machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for synthesizing linear finite state machines will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2869772