An Application of Domain Theory to Logical Design of VLSI Circuits
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This paper is to suggest that traditional 2-valued Boolean algebra is not sufficient for representation of VLSI circuits at logic gate level, although it is the case for combinational circuits. Instead of using the Register-and-Transfer technique at RT level to represent sequential circuits, an alternative is sought and found. That is, all uncertain voltages such as oscillations and floating voltages are identified by the same value, denoted as ⊥ (called bottom). The two certain voltages are, as usual,ground and power; they are denoted by 0 and 1 respectively. An invertor, a nor-gate and a nand-gate are defined according to the physics of VLSI circuits instead of the Boolean algebra. As a result, a logic is obtained which coincides with Kleene 3-valued logic provided that Kleene's u=⊥. As it is well known, Kleene 3-valued logic is functionally incomplete. This means that not every function (or gate) can be constructed from invertors, nor-gates and nand-gates. However, by introducing a partial order  into the logic, by using general fixed-point operators instead of the least fixpoint operator to deal with feedbacks in VLSI circuits, and by applying CPO (complete partial order) domain theory to the derived 3-valued logic system, the result obtained means that this system is functionally monotonic complete. Also, the canonical normal forms for this Kleene 3-valued logic are obtained. Although the present results are mainly semantic, it is very interesting in pursuing the research further by investigating the syntactical derivability. Such research would derive more secure circuits close to reality, which is to make the work compatible with VHDL, Verilog HDL and/or EDIF. Incidentally, Mukaidono has obtained similar results, although his approach is not as coherent as the one presented in this paper.

    Reference
    Related
    Cited by
Get Citation

孙踊,胡易.论域理论在超大规模集成电路逻辑设计上的运用.软件学报,2000,11(5):569-583

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 01,1998
  • Revised:December 24,1998
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063