Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2004-11-19
2010-11-30
Kik, Phallaka (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C703S016000
Reexamination Certificate
active
07844924
ABSTRACT:
A device for logic synthesis that can be used to synthesize LUT logic circuit having intermediate outputs for multiple-output logic functions. The device includes means to store node table8storing Binary Decision Diagram for Characteristic Function (BDD_for_CF) of the characteristic function χ(X, Y) of the multiple-output logic function f(X), means to store LUTs16, means to reduce by shorting11partitioning BDD_for_CF into the subgraphs B0and B1at the partition line in the height lev of the partition and executing shorten-processing, means to measure the width W of BDDs12calculating the width W at the partition line, means to compute the intermediate variables13calculating the number of the intermediate variables u according to the width W, means to generate an LUT14generating the LUT for the sub-graph B0, and means to reconstruct BDDs15generating a binary tree that has the same number of control inputs as that of the intermediate variables u, replacing the sub-graph B0with the binary tree and reconstructing the BDD_for_CF.
REFERENCES:
patent: 4811237 (1989-03-01), Putatunda et al.
patent: 5602753 (1997-02-01), Fukui
patent: 5625630 (1997-04-01), Abramovici et al.
patent: 6212669 (2001-04-01), Jain
patent: 6421815 (2002-07-01), Seawright
patent: 6560758 (2003-05-01), Jain
patent: 7003738 (2006-02-01), Bhattacharya et al.
patent: 7028278 (2006-04-01), Jain
patent: 7039882 (2006-05-01), Rana et al.
patent: 7673263 (2010-03-01), Jain
patent: 2002/0023256 (2002-02-01), Seawright
patent: 2002/0053063 (2002-05-01), Bhattacharya et al.
patent: 2003/0233628 (2003-12-01), Rana et al.
patent: 2004/0015799 (2004-01-01), Jain
patent: 2006/0129953 (2006-06-01), Jain
T. Sasao et al., “A Cascade Realization of Multiple-Output Function for Reconfigurable Hardware,” International Workshop on Logic and Synthesis (IWLS01), Lake Tahoe, CA, Jun. 12-15, 2001. pp. 225-230 and three sheets of cover page and TOC.
T. Sasao et al., “DECOMPOS: An Integrated System for Functional Decomposition”, reprinted from1998 International Workshop on Logic Synthesis, Lake Tahoe, Jun. 1998, pp. 1-7.
Y-T. Lai et al., “BDD Based Decomposition of Logic Functions with Application to FPGA Synthesis”, 30th ACM/IEEE Design Automation Conference, Jun. 1993, pp. 642-647.
T. Sasao, “FPGA Design by Generalized Functional Decomposition”, In Logic Synthesis and Optimization, Sasao ed., Kluwer Academic Publisher, 1993, pp. 233-258 and eight sheets of cover page and TOC.
C. Scholl et al., “Communication Based FPGA Synthesis for Multi-Output Boolean Functions”, reprinted from Asia and South Pacific Design Automation Conference, Aug. 1995, 9 sheets (numbered as pp. 279-287 in original).
B. Wurth et al., “Functional Multiple-Output Decomposition: Theory and Implicit Algorithm”, Design Automation Conf., Jun. 1995, 6 sheets (numbered as pp. 54-59 in original).
H. Sawada et al., “Logic Synthesis for Look-Up table based FPGAs using Functional Decomposition and Support Minimization”, reprinted from ICCAD, Nov. 1995, 6 sheets (numbered as pp. 353-358 in original).
J.-H.R.Jian et al., “Compatible Class Encoding in Hyper-Function Decomposition for FPGA Synthesis”, Design Automation Conference, Jun. 1998, 6 sheets (numbered as pp. 712-717 in original).
P. Ashar et al., “Fast Functional Simulation Using Branching Programs”, reprinted from Proc. International Conference on Computer Aided Design, Nov. 1995, 5 sheets (numbered as pp. 408-412 in original).
C. Scholl et al., “Functional Simulation using Binary Decision Diagram”, reprinted from ICCAD'97, Nov. 1997, 5 sheets (numbered as pp. 8-12 in original).
A. Mishchenko et al., “Logic Synthesis of LUT Cascades with Limited Rails”, IEICE Technical Report, VLD2002-99, Lake Biwa (Nov. 2002), pp. 103-108 and two sheets of TOC.
M. R. Garey et al., “Computers and Intractability: A Guide to the Theory of NP-Completeness”, W. H. Freeman & Co., New York, 1979, p. 194 and six sheets of cover page and TOC.
Y. Iguchi et al., “Realization of Multiple-Output Functions by Reconfigurable Cascades”, reprinted from Proceedings of 2001 International Conference on Computer Design, Sep. 23, 2001, Austin TX USA, pp. 388-393.
Iguchi Yukihiro
Sasao Tsutomu
Edwards Angell Palmer & & Dodge LLP
Kik Phallaka
Kitakyushu Foundation for the Advancement of Industry, Science a
LandOfFree
Device for reducing the width of graph and a method to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device for reducing the width of graph and a method to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device for reducing the width of graph and a method to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4206982