Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2007-08-21
2007-08-21
Malzahn, D. H. (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
10781031
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.
REFERENCES:
patent: 3614400 (1971-10-01), Farnett
patent: 3700869 (1972-10-01), Low et al.
patent: 4161041 (1979-07-01), Butler et al.
patent: 4320509 (1982-03-01), Davidson
patent: 4503537 (1985-03-01), McAnney
patent: 4513418 (1985-04-01), Bardell, Jr. et al.
patent: 4536881 (1985-08-01), Kasuya
patent: 4602210 (1986-07-01), Fasang et al.
patent: 4687988 (1987-08-01), Eichelberger et al.
patent: 4754215 (1988-06-01), Kawai
patent: 4785410 (1988-11-01), Hamatsu et al.
patent: 4801870 (1989-01-01), Eichelberger et al.
patent: 4860236 (1989-08-01), McLeod et al.
patent: 4959832 (1990-09-01), Bardell, Jr.
patent: 4974184 (1990-11-01), Avra
patent: 5072178 (1991-12-01), Matsumoto
patent: 5090035 (1992-02-01), Murase
patent: 5138619 (1992-08-01), Fasang et al.
patent: 5167034 (1992-11-01), MacLean, Jr. et al.
patent: 5173906 (1992-12-01), Dreibelbis et al.
patent: 5202889 (1993-04-01), Aharon et al.
patent: 5258986 (1993-11-01), Zerbe
patent: 5268949 (1993-12-01), Watanabe
patent: 5301199 (1994-04-01), Ikenaga et al.
patent: 5325367 (1994-06-01), Dekker et al.
patent: 5349587 (1994-09-01), Nadeau-Dostie et al.
patent: 5369648 (1994-11-01), Nelson
patent: 5394405 (1995-02-01), Savir
patent: 5412665 (1995-05-01), Gruodis et al.
patent: 5414716 (1995-05-01), Bershteyn
patent: 5416783 (1995-05-01), Broseghini et al.
patent: 5446683 (1995-08-01), Mullen et al.
patent: 5450414 (1995-09-01), Lin
patent: 5524114 (1996-06-01), Peng
patent: 5533128 (1996-07-01), Vobach
patent: 5574733 (1996-11-01), Kim
patent: 5586125 (1996-12-01), Warner
patent: 5592493 (1997-01-01), Crouch et al.
patent: 5608870 (1997-03-01), Valiant
patent: 5612963 (1997-03-01), Koenemann et al.
patent: 5614838 (1997-03-01), Jaber et al.
patent: 5617531 (1997-04-01), Crouch et al.
patent: 5631913 (1997-05-01), Maeda
patent: 5642362 (1997-06-01), Savir
patent: 5680543 (1997-10-01), Bhawmik
patent: 5694402 (1997-12-01), Butler et al.
patent: 5701308 (1997-12-01), Attaway et al.
patent: 5717701 (1998-02-01), Angelotti et al.
patent: 5717702 (1998-02-01), Stokes et al.
patent: 5719913 (1998-02-01), Maeno
patent: 5748497 (1998-05-01), Scott et al.
patent: 5790562 (1998-08-01), Murray et al.
patent: 5790626 (1998-08-01), Johnson et al.
patent: 5812561 (1998-09-01), Giles et al.
patent: 5831992 (1998-11-01), Wu
patent: 5848198 (1998-12-01), Penn
patent: 5867507 (1999-02-01), Beebe et al.
patent: 5870476 (1999-02-01), Fischer
patent: 5872793 (1999-02-01), Attaway et al.
patent: 5883906 (1999-03-01), Turnquist et al.
patent: 5899961 (1999-05-01), Sundermann
patent: 5905986 (1999-05-01), Rohrbaugh et al.
patent: 5938784 (1999-08-01), Kim
patent: 5974179 (1999-10-01), Caklovic
patent: 5974433 (1999-10-01), Currie
patent: 5983380 (1999-11-01), Motika et al.
patent: 5991898 (1999-11-01), Rajski et al.
patent: 5991909 (1999-11-01), Rajski et al.
patent: 6006349 (1999-12-01), Fujisaki
patent: 6014763 (2000-01-01), Dhong et al.
patent: 6026508 (2000-02-01), Craft
patent: 6041429 (2000-03-01), Koenemann
patent: 6055658 (2000-04-01), Jaber et al.
patent: 6061818 (2000-05-01), Touba et al.
patent: 6072823 (2000-06-01), Takakusaki
patent: 6122761 (2000-09-01), Park
patent: 6141669 (2000-10-01), Carleton
patent: 6158032 (2000-12-01), Currier et al.
patent: 6178532 (2001-01-01), Pierce et al.
patent: 6181164 (2001-01-01), Miller
patent: 6199182 (2001-03-01), Whetsel
patent: 6240432 (2001-05-01), Chuang et al.
patent: 6256759 (2001-07-01), Bhawmik
patent: 6272653 (2001-08-01), Amstutz
patent: 6286119 (2001-09-01), Wu et al.
patent: 6300885 (2001-10-01), Davenport et al.
patent: 6308291 (2001-10-01), Kock et al.
patent: 6327687 (2001-12-01), Rajski et al.
patent: 6330681 (2001-12-01), Cote et al.
patent: 6353842 (2002-03-01), Rajski et al.
patent: 6385750 (2002-05-01), Kapur et al.
patent: 6467058 (2002-10-01), Chakradhar et al.
patent: 6539409 (2003-03-01), Rajski et al.
patent: 6543020 (2003-04-01), Rajski et al.
patent: 6557129 (2003-04-01), Rajski et al.
patent: 6590929 (2003-07-01), Williams
patent: 6684358 (2004-01-01), Rajski et al.
patent: 6708192 (2004-03-01), Rajski et al.
patent: 6763488 (2004-07-01), Whetsel
patent: 6829740 (2004-12-01), Rajski et al.
patent: 6874109 (2005-03-01), Rajski et al.
patent: 2002/0112199 (2002-08-01), Whetsel
patent: 2002/0124217 (2002-09-01), Hiraide et al.
patent: 2003/0120988 (2003-06-01), Rajski et al.
patent: 2003/0131298 (2003-07-01), Rajski et al.
patent: 2004/0128599 (2004-07-01), Rajski et al.
patent: 2005/0015688 (2005-01-01), Rajski et al.
patent: 2005/0097419 (2005-05-01), Rajski et al.
patent: 0372226 (1990-06-01), None
patent: 0438322 (1991-07-01), None
patent: 0481097 (1992-04-01), None
patent: 0 549 949 (1998-03-01), None
patent: 0887930 (1998-12-01), None
patent: 63-286780 (1988-11-01), None
patent: 01-239486 (1989-09-01), None
patent: 03-002579 (1991-01-01), None
patent: 03-012573 (1991-01-01), None
patent: 4-236378 (1992-08-01), None
patent: 05-215816 (1993-08-01), None
patent: 05-249197 (1993-09-01), None
patent: 07-174822 (1995-07-01), None
patent: 08-015382 (1996-01-01), None
patent: 9-130378 (1997-05-01), None
patent: 11-030646 (1999-02-01), None
patent: 11-153655 (1999-06-01), None
patent: 11-264860 (1999-09-01), None
patent: WO 91/10182 (1991-07-01), None
patent: WO 01/38889 (2001-05-01), None
patent: WO 01/39254 (2001-05-01), None
U.S. Appl. No. 09/713,662, Rajski et al., filed Jul. 20, 2000.
U.S. Appl. No. 09/713,664, Rajski et al., filed Nov. 15, 2000.
Mano, M. Morris, “Computer System Architecture,” 2ndEdition, Prentice-Hall, Inc., New Jersey, 1982, pp. ii and 50-54.
Bershteyn, Michael, “Calculation of Multiple Sets of Weights for Weighted Random Testing,” International Test Conference 1993, Paper 45.3, pp. 1031-1040.
Zacharia, N., “Decompression of Test Data Using Variable-Length Seed LFSRs,” IEEE 1995, 426-432.
P.H. Bardell, “Design Considerations for Parallel Pseudorandom Pattern Generators”, Journal of Electronic Testing: Theory and Applications, pp. 73-87 (1990).
I. Hamzaoglu, J. Patel, “Reducing Test Application Time for Full Scan Embedded Cores,” Center for Reliable & High-Performance Computing, University of Illinois, Urbana, IL., 1999 IEEE, pp. 260-267.
S. Hellebrand, J. Rajski, S. Tarnick, S. Venkataraman, B. Courtois, “Built-in Test for Circuits With Scan Based on Reseeding of Multiple Polynomial Linear Feedback Shift Registers”,IEEE Trans. On Computers, vol. C-44, pp. 223-233, 1995.
S. Hellebrand, B. Reeb, S. Tarnick, H-J Wunderlich, “Pattern Generation for a Deterministic BIST Scheme”, pp. 88-941995 IEEE.
B. Koenemann c/o IBM Corp. , B65/901, “LFSR-Coded Test Patterns for Scan Designs”,Proceedings of European Test Conference, pp. 237-242, 1991.
J. Rajski,J. Tyszer, N. Zacharia, “Decompression of Test Data Using Variable-Length Seed LFSRs”, Microelectronics and Computer Systems Laboratory, McGill University, Montreal, Canada, 1995 IEEE, pp. 426-433.
J. Rajski, J. Tyszer, N. Zacharia, “Test Data Decompression
Kassab Mark
Mukherjee Nilanjan
Rajski Janusz
Tyszer Jerzy
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-3865661