# multiple-valued logic in vlsi challenges and opportunities[精选推荐pdf]

Multiple-Valued Logic in VLSI Challenges and OpportunitiesElena Dubrova Electronic System Design Lab Department of Electronics Royal Institute of Technology Kista, Sweden elenaele.kth.seAbstractInrecentyears, there havebeenmajoradvancesinintegrated circuittechnology which have both made feasible and generated great interest in electronic circuits which employ more than two discrete levels of signal. Such circuits, called multiple-valued logic cir- cuits, offer several potential opportunities for the improvement of present VLSI circuit designs. In this paper, we give an overview of recent developments in multiple-valued logic circuit design, revealing both the opportunities they offer and the challenges they face.1IntroductionWhen people ask me why I am doing research in multiple-valued logic, I often reply that it is like painting a picture having all possible colors available. Once you tried them, you will never return to just black and white. Multiple-valued logic displays us phenomena, we would never see in binary case, where the only two values available are null and unit elements ofBoolean algebra , possessing very specific properties. Reflected back to two-valued scale, these phenomena give us a new, deeper understanding of the matter. Apart from giving us a better insight into binary problems, multiple-valued logic hasmany other useful applications. They can be classified into two groups. The first groupuses multiple-valued logic domain to solve binary problems more efficiently. For example, a well-known approach to represent a multiple-output Boolean function is to convert it to a single-output multiple-valued function, by treating its output part as a single multiple-valuedvariable. Such an approach is used, for instance, in Berkeley’s tool for verification and syn- thesis VIS [1]. The second group targets the design of electronic circuits which employ more than two discrete levels of signals, such as multiple-valued memories, arithmetic circuits, Field Pro- grammable Gate Arrays etc. Multiple-valued logic MVL circuits offer several potential opportunities for the improvement of present VLSI circuit designs. For example, seriousdifficulties with limitations on the number of connections of an integrated circuit with theThe null 0 and unit 1 elements of an algebra over a set A have the properties that, for each, andexternal world pinout problem as well as on the number of connections inside the circuit encountered in some VLSI circuit synthesis could be substantially reduced if signals in the circuit are allowed to assume four or more states rather than only two. In addition, there is a clear mathematical attraction of using multiple-valued number representation in many appli- cations. For example, residue and redundant number systems allow to reduce or eliminate the ripple-through carries which are involved in normal binary addition or subtraction, resulting in high-speed arithmetic operations. In spite of these potential advantages, practicality of MVL design heavily depends on the availability of circuit realizations, which must be compatible or competitive with present-day binary technologies. The purpose of this paper is to give the reader an overview of recent 1995-1999 developments in MVL circuit design, revealing both the opportunities they offer and the challenges they face. The earlier achievements in this area can be found in [3]-[5]. To achieve this goal in a reasonable space, we have had to exclude a number of topics which are of interest, but not central to our purpose. We do not deal with fuzzy logic, nor signal process- ing. Ination about reliability or fault detection is excluded as is a whole range of purely theoretical material. Also, we do not discuss applications of multiple-valued logic to solving binary problems. A recent overview of this area can be found in [6]. Section 2 describes number representations alternative to binary. Section 3 shows possibilities for implementing multiple-valued circuits with integrated circuits technologies. Section 4 summarizes recent achievements in the design of MVL circuits. Section 5 concludes the paper.2Number RepresentationA digital system represents ination with discrete symbols rather than with continuously carrying quantity, as in a analog system. Digital binary systems use just two symbols, 0 and 1, to represent all ination. Leaving aside for the moment the problem of circuit realiza- tion, we may ask whether the binary number representation is an optimum choice. The real world is not binary. It is more intuitive to reason about a system, especially at higher levels of abstractions, in terms of variables with symbolic values. In many practical engineering situa- tions, a device can be not only in ”off” or ”on” state, but also in ”idle” state. When arithmetic operations are involved, computing in a decimal system would match best our experience. In this section we discuss potential advantages of using multiple-valued number representation instead of binary one. There are two major conventions for labeling values in a multiple-valued logic system over a set ofvalues. The most common is, extending binary notation in one direction only. It is called unbalanced or unsigned, or positive. The second one requires an odd. It extends binary notation in both directions as . It is called balanced or signed. A string of digitsover a set ofvalues represents the numberFor example, in the binary case of,. In the ternary case of, for the unbalanced system, andfor the balanced system. One concern in binary number representation is the treatment of negative numbers. There are three common techniques 1 sign-magnitude, where a sign is explicitly attached to the frontofthestringofdigits; 21’s complement,wheretherepresentationforanegativenumberis obtained by subtracting each digit from 1; 3 2’s complement, where the representation fora negative number is obtained as in 2 but with a final addition of 1 to the number. There are disadvantages of all three of these techniques. Both 1 and 2 have two rep- resentations for 0 and, while 3 permits the representation of one more negative number than positive. Alternatively, in a balanced system over a set ofvalues, all the num- bers can be represented without using an explicit sign. The sign of a number is the sign of themostsignificantnon-zerodigit. Furthermore,in a ternarysystem, the negativeofa numbercan be found by interchangingandthroughout, leaving all zeros unchanged. Hence, addi- tion and subtraction can be pered with the same hardware by sign changes of the addend and subtrahend, respectively,as required. One other advantageof a balancedsystem is that the procedure of roundinga number is identical to truncation. In a binary system it is not possible,because there is no way for negative correction being applied by digits of lower significance. Therefore, the correct value of the number must be approached from lower digits. Another concern in binary number representation is that in pering addition or sub- traction, the sum bits depend on the carry lower bits. Two alternative multiple-valued number systems have been extensively studied in order to reduce or eliminate the ripple-through carries. The first one is residue number system, in which there are no carries between bits. In such a representation, operations occur at each digit independently of the other digits, resulting in fast arithmetic operations [7], [8]. A disadvantageis that the size of the digits may vary, and thus different circuit designs might be needed for different digits. Thesecondnumberrepresentationwhichhaspotentialperanceattractionsisanumber system with redundancy. In such a system, all numbers except 0 are not uniquely represented by a string of digits. Instead, two or more representations for a given number are available.The most significant digit does not depend on the least significant bit. The carry into a digit is computed only from at most the next two lower digits, but no other, enabling fast arithmetic operations. Multiple-valued arithmetic in redundant balanced number system [9], [10] as well as in redundant unbalanced number system [11], [12] have been presented. Someothernumberrepresentationswhichhavepotentialadvantagesoverbinaryhavebeen studied, includingoverlapresolutionnumbersystembasedon signedcontinuousvalueddigits, allowing to per arithmetic operations by analog digit manipulation circuitry [13] and redundant complex number system [14], allowing to per addition and multiplication of complex numbers without treating real part and imaginary part separately as well as enabling carry-free addition and binary-tree multiple-operand addition.3Technology ConsiderationsPrevioussectionshowsthatthere isa clearmathematicalattractionin theadoptionof multiple- valued number representation. Its practicality, however, depends on the availability of circuit realizations, which must be compatible or competitive with present-day binary technologies. The attempts to built multiple-valuedintegratedcircuits ICs of multiple-valuedcircuits com- patible with IC technologies can be traced back to 1970, starting from the early works on 3- valued designs. Multiple-valued logic circuits have been implemented in bipolar technology, such as integrated injection logic I L and emitter-coupled logic ECL; in complementary metal oxide semiconductor CMOS technology; in n-type MOS technology; and in charge- coupledeviceCCDtechnology. Ofthetechnologiesapplied,thetwowhichshowthegreatest potential for commercialization are current-mode CMOS and quantum functional devices. Inthis section, we briefly describe pro and contra of design of MVL circuits using these tech- nologies.3.1CMOS current-mode MVL circuitsIn current-mode circuits, currents are usually defined to have logical levels that are integer multiples of a reference current unit. Currents can be copied, scaled, and algebraically sign- changed with a simple current mirror. The frequently used linear sum operation can be per- ed simply by wiring, resulting in a reduced number of active devices in the circuit. Several prototype chips of current-mode CMOS circuits have been fabricated, showing better perance compared to corresponding binary circuits [7], [9], [11], [15], [16]. It is believed that current-mode designs can allow better noise margin than voltage-mode CMOS designs. Regrettably, the unique characteristics of CMOS binary logic, namely that of zero static power dissipation in either stable state, similar output impedance in either state are not carriedovertoMVLCMOScircuits. Instead,suchcircuitsareusuallycharacterizedbyrail-to-rail current flow in one or more static state and higher output impedancein one state compared to other states. Two solutions to these problems have been suggested recently. In [9], current- mode CMOS MVL circuits based on dual-rail source-couple logic have been introduced. The use of a complementary pair and source-coupled logic allows high-speed circuits with low power dissipation. An alternative solution is proposed in [15], where low-voltage and low-power current-mode MVL circuits are designed using a neuron-MOS transistor. Another problem with CMOS MVL circuits is that, unlike binary CMOS circuits, they are not self-restored. A level restorer circuit must be used every certain number of stages to recover the signal. To overcome this problem, a novel self-restored architecture has been recently presented [16]. It uses both current-mode MVL circuits and voltage-mode binary circuits to implement MVL functions and to restore output signal simultaneously. Binary gates are used within the design architecture so that MVL-binary or binary-MVL conversion circuits are not required to interface with binary circuits. The average size of the resulting circuitsis about50smaller thanpreviouslyproposedMVL circuits,while theaverage power dissipation and time delays are comparable.3.2MVL circuit design using quantum functional devicesAn area of a special interest is implementation of MVL circuits using quantum functional devices. Negative-differential-resistance characteristics which appear in these devices have clear multiple threshold characteristics and therefore are very promising for MVL applica- tions [10], [17]-[19]. Several MVL circuits have been constructed using resonant tunneling transistors RTT and resonant tunneling diodes RTD [20]-[24], or using surface tunneling transistors STT [25]. Although not at a mature stage yet, quantum devices may become indispensable for implementation of MVL circuits in the near future.4Design of MVL CircuitsThe most promising applications of MVL are memories and arithmetic circuits, as we shall see in the sections that follow. Among other interesting recent achievements, not covered in this survey, are MVL programmable devices [26]-[29], multiplr [17], A/D converter [21], decoder [30], quantizer [20], and logic-in-memory VLSI structure [31].4.1MemoriesIn memory technology, recent applications of multiple-valued logic include Flash [32]-[37], DRAM [46], [47], CAM [40]-[42], and optical [43] memory designs. In what follows, we will concentrate on advances in Flash and DRAM memories, which seem to have the greatest commercial success. An overview of CMOS-related multiple-valued memory technologies can be found in [44] and of non-volatile multiple-valued memory technologies - in [45].4.1.1Flash memoriesFlash memory is a non-volatile multiple-write EEPROM memory. Data is entered into theflash memory on a bit, byte, word or page boundary through programming. Once data is entered into the device it will remain, regardless of the presence or absence of power. Un-like traditional EEPROM, flash memory is limited in the granularity of the blocks that can be erased. The size of theerased blockscan rangefrom 8Kbit to 1Mbit, dependingon the productdesign. Array core cells of flash are normally arranged as NOR [32] or NAND [33] config- urations. The memory cell consists of a single transistor with the addition of an electricallyisolated polysilicon floating gate capable of storing charge electrons. The single transistor memory cell results in a small cell size, and thus a small amount of silicon area is consumed for the storage of one bit of data, resulting in low cost.The combination of non-volatility, electrical alterability and low cost makes flash memory attractive to small battery-powered systems. Flash memory devices are found in over 90 of PCs, over 90 of cellular phones and over 50 of modems. They are also key components ofthe emerging digital imaging and audio markets where it serves as the digital ”film” or digital ”tape”.Traditionally, cost reduction and density increase for flash memory has been driven by process scaling in the same way as other semiconductor memory devices such as DRAMs and SRAMs. In 1992,Intel begana researcheffortto reducethe