Redundancy removal using quasi-algebraic methods

Details Redundancy removal using quasi-algebraic methods Redundancy removal using quasi-algebraic methods

1991-06-28

1996-06-04

Trans, Vincent N.

Boots, shoes, and leggings

364488, G06F 1750

Patent

active

055240828

ABSTRACT:
A method is provided to remove redundancies in multi-level logic networks caused by reconverging signals at Boolean sum and product nodes. Generally, sum and product nodes which have potential redundancies are first identified. For each reconvergent signal at each of the nodes, it is determined whether it introduces redundancies using nondestructive Boolean analysis. No two-level expansion is made of the logic network. Moreover, for each confirmed redundancy, a redundant term is identified using Boolean analysis. Finally, the redundancy is removed, if desirable.

REFERENCES:
patent: 4503537 (1985-03-01), McAnney
patent: 4591993 (1986-05-01), Griffin et al.
patent: 4703435 (1987-10-01), Darringer et al.
patent: 4726023 (1988-02-01), Carter et al.
patent: 4816999 (1989-03-01), Berman et al.
patent: 4862399 (1989-08-01), Freeman
patent: 4916627 (1990-04-01), Hathaway
patent: 5029102 (1991-07-01), Drumm et al.
patent: 5140526 (1992-08-01), McDermeth et al.
"Improved Cutting Algorithm" by J. Savir, IBM Journal of Research& Development, vol. 34, No. 2/3 Mar./May 1990, pp. 381-388.
"Cellular Automata Circuits for Built-In Self-Test" by P. D. Hortensius et al, IBM Journal of Research&Development, vol. 34, No. 2/3 Mar./May 1990, pp. 389-405.
"Built-In Self-Test Support in the IBM Engineering Design System" by B. L. Keller et al, IBM Journal of Research & Development, vol. 34, No. 2/3 Mar./May 1990, pp. 406-415.
"Self-Testing the 16 Mbps Adapter Chip for the IBM Token-Ring Local Area Network" by S. F. Oakland et al, IBM Journal of Research & Development, vol. 34, No. 2/3 Mar./May 1990, pp. 416-427.
J. C. Sutton, III and J. G. Bredeson, "Minimal Redundant Logic for High Reliability and Irredundant Testability," IEEE Transactions on Computers, vol. c-29, No. 7, pp. 648-656, Jul., 1980.
J. A. Darringer, W. H. Joyner, Jr., C. L. Berman and L. Trevillyan, "Logic Synthesis Through Local Transformations," IBM J. Res. Develop., vol. 25, No. 4, pp. 272-280, Jul., 1981.
R. K. Brayton, "Factoring logic functions," IBM J. Res. Development, vol. 31, No. 2, pp. 187-190, Mar., 1987.
K. A. Bartlett, et al., "Multilevel Logic Minimization Using Implicit Don't Cares," IEEE Transactions On Computer-Aided Design, vol. 7, No. 6, pp. 723-740, Jun., 1988.
D. Brand, "Redundancy and Don't Cares in Logic Synthesis," IEEE Transactions On Computers, vol. c-32, No. 10, pp. 947-952, Oct., 1983.
L. Trevillyan, W. Joyner and L. Berman, "Global Flow Analysis in Automatic Logic Design," IEEE Transactions on Computers, vol. c-35, No. 1, pp. 77-81, Jan., 1986.
R. Dandapani and S. M. Reddy, "On the Design of Logic Networks with Redundancy and Testability Considerations," IEEE Transactions on Computers, vol. c-23, No. 11, pp. 1139-1149, Nov., 1974.
J. P. Roth, "Minimization by the D Algorithm," IEEE Transactions On Computers, vol. c-35, No. 5, pp. 476-478, May, 1986.
T. F. Schwab and S. S. Yau, "An Algebraic Model of Fault-Masking Logic Circuits," IEEE Transactions on Computers, vol. c-32, No. 9, pp. 809-825, Sep., 1983.
R. K. Brayton, et al., "MIS: A Multiple-Level Logic Optimization System," IEEE Transactions on Computer-Aided Design, vol. CAD-6, No. 6, pp. 1062-1080, Nov., 1987.
C. C. Chao, "AC Test Pattern Generation For Sequential Logic," IBM Technical Disclosure Bulletin, vol. 16, No. 8, pp. 2439-2441, Jan., 1974.
D. Brand, "Detecting Redundancy And Don't Cares In Logic Circuit Design," IBM Technical Disclosure Bulletin, vol. 26, No. 7A, pp. 3456-3463, Dec., 1983.
R. K. Brayton, C. L. Chen and J. Yamour, "Method For Optimizing Logic For Single-Ended Domino Logic Circuits," IBM Technical Disclosure Bulletin, vol. 27, No. 7B, pp. 4398-4401, Dec., 1984.
D. E. Popp, "Method For Removing Redundancies From Programmable Logic Arrays," IBM Technical Disclosure Bulletin, vol. 28, No. 10, pp. 4677-4682, Mar., 1986.
W. B. Perlowitz, "Detection Of Multiplexer Structures In Logic," IBM Technical Disclosure Bulletin, vol. 30, No. 7, pp. 36-38, Dec., 1987.
J. L. Gilkinson and R. C. Itskin, "Iterative Consensus And Absorption," vol. 30, No. 9, pp. 379-380, Feb., 1988.
D. O. Forlenza, et al., "Test Generation Of AC Faults Using Weighted Random Patterns," IBM Technical Disclosure Bulletin, vol. 32, No. 3A, pp. 4-6, Aug., 1989.
"A Rule-Based System for Optimizing Combinational Logic" by de Geus et al., IEEE Design & Test, 1985, pp. 22-32.

Affiliated with

Also associated with

Rating

Redundancy removal using quasi-algebraic methods does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Redundancy removal using quasi-algebraic methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Redundancy removal using quasi-algebraic methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-390484