nu MOS-based sorter for arithmetic applications

VLSI DESIGN 2000, Vol. 11, No. 2, pp. 129-136 Reprints available directly from the publisher Photocopying permitted by license only (C) 2000 OPA (Overseas Publishers Association) N.V. Published by license under the Gordon and Breach Science Publishers imprint. Printed in Malaysia. vMOS-based Sorter for Arithmetic Applications* E. RODRGUEZ-VILLEGAS, M. J. AVEDILLO, J. M. QUINTANA t, G. HUERTAS and A. RUEDA Instituto de Microelectr6nica de Sevilla, Centro Nacional de Microelectr6nica, Edif. CICA, Avda. Reina Mercedes s/n, 41012-Sevilla, Spain (Received 1 June 1999; In final form 22 November 1999) The capabilities of the conceptual link between threshold gates and sorting networks are explored by implementing some arithmetic demonstrators. In particular, both an (8 8)-multiplier and a (15, 4) counter which use a sorter as the main building block have been implemented. Traditional disadvantages of binary sorters such as their hardware intensive nature are avoided by using uMOS circuits. It allows both an improving of previous results for multipliers based on a similar architecture, and to obtain a new type of counter which shows a reduced delay when compared to a conventional implementation. Keywords: uMOS circuits, threshold logic, sorter circuits, arithmetic circuits I. INTRODUCTION Circuits whose outputs depend on the number of l’s in the inputs are widely used in logic design. This kind of circuits can be described very advantageously by using the concept of threshold functions. A threshold function T, has n twovalued inputs x l, x2,..., xn and a single two-valued output. The input-output relation is defined as T if iL1 xi m, rn= 1,2,...,n, and 0 otherwise. Sum is the conventional, rather than the logical, operation. Circuits such as multipliers, counters or checkers for m-out-of-n codes and Berger codes are well described using the set of n inputs threshold functions (T’, T’,..., T), represented by T n. This set of functions corresponds to the output of an n-input binary sorting network (SN). An n-input SN is a switching network with n outputs that generates an output which is a sorted (non increasing order) permutation of inputs. A first mention to the conceptual link between threshold functions and sorting networks was done by Lamagna [1] who stated that T and the sorting function are equivalent, as shown in Figure 1. In spite of this early identification, the relation between sorting networks and threshold logic has not been exploited to date by researchers perhaps due to the hardware intensive nature of * This effort was partially supported by the spanish CICYT under Project TIC97-0648. Address for correspondence: Instituto de Microelectr6nica de Sevilla, IMSE-CNM, Universidad de Sevilla. Edif. CICA, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. Tel.: + 34-955056666, Fax: + 34-955056692, e-mail: [email protected] 129 130 E. RODRGUEZ-VILLEGAS et al. binary n-tuple with k l’s xl I T1 k first x2 T2 outputs to Sorting Networkl’ Tk Xn-l T,n-| n_k following x, T’,’, outputs to 0 FIGURE Sorting network with k binary signal inputs equal to 1. the traditional solution for SNs [2]. The objective of this paper is to demonstrate the viability and capabilities of the link between SNs and threshold functions by implementing two arithmetic circuits: a serial/parallel multiplier and a counter which use as main building block an efficiently implemented sorter circuit. This efficiency has been achieved by resorting to the uMOS principle. The obtained results for these application examples pave the way to consider the implementation of more complex circuits which use sorting networks as basic building blocks. The paper is organized as follows. Section II is mainly devoted to the description of the proposed uMOS sorter. The design and experimental results for two arithmetic applications which use the new circuit as basic building block are given in Section III, and finally, some conclusions are discussed in Section IV. sum which controls the current in the transistor channel. A schematic of this transistor is shown in Figure 2a. There is a floating gate and a number of input gates Xl, X2,... ,xn. Weights for every input are proportional to the ratio of the corresponding input capacitance, Ci, between the floating gate and each of the input gates, to the total capacitance, including the transistor channel capacitance, Cchan, between the floating gate and the substrate. The most simple uMOS-based threshold gate is the complementary inverter using both pand ntype uMOS devices. A schematic of this TG is shown in Figure 2b. There is a floating gate, which is common to both the PMOS and NMOS transistors, and a number of input gates connected to Vxi xiVoo, where VDD is the power supply and XzE {0, 1} correspond to the TG logical inputs, xl, xz,...,xn. Additionally, there are some extra inputs (indicated by Vc in the figure) for threshold adjustment. When all the threshold functions to be implemented have the same weight (C; C, 1,... ,n), the voltage in the floating gate, VFa, is given by VFG-- (Xi) (1) II. THE BINARY SORTER A lot of attention has been for many years devoted to the problem of efficient SN design [3]. An ninput sorting network can be directly realized as a set of n threshold gates implementing the n threshold functions (Tf, T,..., T), according to the previous definition. Physical implementation of these threshold gates can be efficiently achieved by resorting to the high-functional uMOS transistors which can perform weighted summation of multiple input signals at the gate level [4]. uMOS transistors have a buried floating polysilicon gate and a number of input polysilicon gates that couple capacitively to the floating gate. The voltage of the floating gate becomes a weighted sum of the voltages in the input gates, and hence, it is this in in 2 in in (a) vMOS V xj---- V x,,--- Vc --- (b) f FIGURE 2 (a) Schematic of the uMOS transistor. (b) Schematic of the uMOS TG. uMOS-BASED SORTER FOR ARITHMETIC APPLICATIONS 131 without using the extra control inputs and assuming zero the change in the floating gate, where Ctot-- Cchan n tFt. C. As VFG becomes higher than the threshold voltage of the first stage inverter, the output switches to logic 1. Clearly, the capacitive network in the uMOS devices implements the summation in the logical definition. Extra control inputs are required for extreme values of logical threshold m. Practical design requires considering second order effects not included for simplicity in the above expressions. The TG-based solution to the n-input sorter requires n TGs and it suffers the implicit problem of interconnecting n input lines to n TGs of n inputs each. A clever solution for the problem of building binary sorting networks which substitutes these n TGs by only one high functional uMOS circuit has been recently reported [5]. This circuit is based on the fact that an n-input sorter can be seen as a cascaded two-block circuit. The first block provides an output which depends linearly on the number of l’s in the applied inputs. The second block takes this output signal and compares it with a set of n fixed values by means of a battery of comparators, thus providing the set of n output functions of an n-input sorter. Figure 3 shows the two-stage schematic diagram of the n-input sorter proposed in [5]. The implementation of the first block resorts to the uMOS principle and to current mirroring to provide an analog output voltage, V1, which mmmmmmmmmmmmmmmmmm Xn M R first stage oHE T n r’L? ’-b.--’P, - 2 102 --i0 -- Tn second stage FIGURE 3 Two-stage schematic of the proposed n-input sorter. increases proportionally, in a staircase shape, to the number of binary inputs equal to 1. This operation is performed by transistor M1-M4 in their saturation regions. Transistors Me and M4 are equally sized n-channel uMOS transistors. M1 and M3 are equal PMOS transistors. The sorter inputs are the M2 input gates capacitively coupled to its floating gate with identical coupling capacitances, C,, which produces a floating gate voltage, VFG, linearly dependent of the sum of the inputs. However, with this circuit several input combinations with different number of l’s can give floating gate voltages below the threshold voltage of the NMOS transistor, so not being distinguished. This offset is avoided injecting an initial charge in the M2 floating gate. For this purpose, inverter I1 has been included as well as two additional inputs to transistor m2 with coupling capacitances C,/2 and Co. With R (initialization mode) switches controlled by this phase short circuit the Me floating gate and the output and input of I1, and the input terminals xl, x2,..., xn are connected to ground (input switches not shown in Fig. 3). After initialization, when qR=0, (processing mode), the voltage in the floating gate is C (Cu/2) v .EZto + v;*, Cto--Zi=1 where V]I is the threshold voltage of inverter Cto (Ft n L 1/2)C, @ Cchan -tCo. Capacitance Co is introduced by the extra grounded input in order to maintain M2 saturated, even when the n inputs of the sorter are at logical 1. This VFG controls the current through M1 and M3. Since M4 is made equal to M2, this circuit produces a voltage at the M4 drain terminal, V1 VF. The purpose of using this scheme to obtain the analog output voltage is twofold. First, to make operation insensitive to the parasitic charges in the floating gate, thus avoiding the need of post fabrication UV erasure. The mismatch between M2 and M4 will be smaller if both are uMOS transistors since if only M2 is a uMOS transistor, the charge stored in the floating 132 E. RODRGUEZ-VILLEGAS et al. gate would be equivalent to a shift in the threshold voltage, so causing a difference between the thresholds of M2 and M4 that could be important and could bring about the scheme fails. Then it would be necessary a post fabrication UV erasure. If two uMOS transistors are used the difference between the thresholds would depend on the different charges stored in M2 and M4. This quantity will be much more smaller than the previous one. Secondly, to make the resulting staircase shape voltage robust concerning process parameter variations. With this scheme, variations in the voltage at V will depend only on differences between the thresholds and betas of equal sized transistors. These ones will be smaller than the variations in the nominal values of the technology, and will have no effect on the design if a good layout if done. The second block is constituted by the set of comparators which have been implemented as inverters. Each inverter is sized so that its threshold voltage is between two given consecutive steps of the staircase mentioned above. For example, the output Tf must be a logical one if there is at least an input at logical one and so the threshold voltage of inverter lol is fixed to (V(0)+ V(1))/2, where V(0) stands for the voltage at node V when the all zero input vector is applied and V(1) corresponds to the voltage at node V when an input vector with only one is applied. III. ARITHMETIC APPLICATIONS III.1. The (8 8) Multiplier Recently, a compact architecture for serial/parallel multipliers, shown in Figure 4, has been proposed [6]. The main component of it, apart from peripheral circuitry necessary for data scheduling, is a combinational functional block (F_Block) with 16 inputs and nine outputs. Eight of the outputs correspond to threshold functions T216, T416, T616, T 6, To 6, T2 6, T4 6 and T6 6. The ninth is the parity function. The F_Block circuit is realized by using a two level network of capacitive threshold gates [7] (17 gates). The F_Block we have realized uses the uMOS sorter circuit as the key component. Figure 5 shows the logic diagram we have implemented. It consists only of a 16-input sorter, T 16 and a threshold gate, T 6 realized based on the ideas sketched in the previous section. The output of the threshold gate Serial Data Parallel Data T ___K TI T Register T lll T16 Serifil Data Output FIGURE 4 Serial/Parallel multiplier architecture. As mentioned at the beginning of this paper, the threshold functions produced at the outputs of the sorter circuits are involved in many arithmetic-like operations. To illustrate this, we describe two examples of application different from the binary sorting function pointed out above. The first one refers to the implementation of an (8 x 8)-multiplier. The second one is the implementation of a (15, 4) counter which is used in the summation of the partial products in a parallel multiplier. 16 input sorter (T 16) TI T T T T T 166 parity FIGURE 5 Logic diagram for the F_Block. uMOS-BASED SORTER FOR ARITHMETIC APPLICATIONS 133 implements the parity function following the Muroga’s method [8] as: parityTt 6T 6 q-- T316 Tt4 6 -}- Tt5 6 Tt6 6 (3) The F_Block circuit using the uMOS sorter has been designed and laid out in a 0.8lam double poly CMOS process. Figure 6 plots the simulated waveforms for the parity output of the extracted F_Block. The inputs correspond to a sequence of input patterns with an increasing number of ones" (xl, X2,..., X16)--- {(0, 0,..., 0), (0,0,..., 1),...,(1, 1,..., 1)} starting at time 60 ns. A new pattern is applied each 7.5 ns. Clearly, the parity of the 16 input signals is correctly evaluated. Correct operation under process and ambient parameter variations has been validated through extensive Monte Carlo HSPICE simulations of the extracted circuit. Time characteristics and average power have been measured on post-layout simulation results using typical device parameters at a supply voltage of 5V. The power has been measured using a random generated input sequence with 100 vectors. The worst case delay time is 4.5ns and the power consumption is 13 mW at 100 MHz. However, the intrinsic nature of the uMOS approach makes this consumption be very independent of the frequency. In order to validate the proposed circuit a comparison to others solutions is in order. Simulation results for the threshold-gate-based implementation of the architecture in Figure 4 provide a Do. Ao v(outs) 45 35 25 1.5 500m 60n 70n 80n 90n 100n 110n 120n 130n 140n 150n 160n 170n 180n Time (lin) (TIME) FIGURE 6 HSPICE simulation results for the parity output of F_Block. 134 E. RODR[GUEZ-VILLEGAS et al. clock frequency around 30 MHz for the multiplier when implemented in a 1.2 lam technology [6]. A multiplier incorporating our circuit as the required functional unit could work at frequencies in excess of 175 MHz since the clock frequency is mainly limited by the signal propagation through the F_Block. It allows us to conclude that the proposed new implementation is faster even taking into account the extrapolation to 0.8 gm of the design in [6]. For the purpose of comparison, we have designed and laid out also the F_Block following a conventional approach (NOR and NAND gates are used) and the same technological process. The worst case delay for this conventional design is over 11 ns and the power consumption at 66 MHz is 13 mW. Additionally, it occupies an area between one and two orders of magnitude higher than the new one. 111.2. The (15, 4) Counter The second application considered is the implementation of a (15,4) counter. A counter is a combinational circuit with a number of output lines representing the binary number equal to the number of input lines that are asserted to logical one. The summation of partial product in a parallel multiplier has been traditionally done by using a full adder tree (full adders are a particular case of counters, the (3, 2) counter). However, the routing may be complicated and high-order counters are used. High-order counters are usually implemented from (3,2) counters because of the disadvantages of a direct implementation [9]. The approach we have developed allows us to construct the counter directly from its logic equations. Let (Xo, Xl,... ,x14) be the fifteen numbers to add in a (15, 4) counter, and (Y3, y2, yl, y0) be the counter output. Signals y3, y2, yl and y0 are symmetric functions and a set of two-level logic equations using the sorter outputs as input variables are: 15 input sorter 15 (T) 15 TI4 15 TI5 Y0 72 Y3 FIGURE 7 Logic diagram implementing the (15, 4) counter. uMOS-BASED SORTER FOR ARITHMETIC APPLICATIONS 135 The implementation of these expressions can be improved by implicit computations, using arithmetic operators: which can be implemented in only one level of threshold logic, as shown in Figure 7. Outputs Y0, Yl and Y2 have been implemented through functions Ts 5, T47, and T23, realized as threshold gates. A (15, 4) counter using the uMOS sorter circuit and uMOS TGs, and another one following a conventional approach have been designed and laid out in the same technological process. Correct operation under process and ambient parameter variations of the uMOS circuits have been validated through extensive Monte Carlo HSPICE simulations of the extracted circuit. Time characteristics and average power have been measured in a similar way to the above described multiplier. The worst case delay time for the uMOS solution is 8 ns and the power consumption is 12 mW at 66MHz, very independent of the frequency. The worst case delay for conventional design is 11.25 ns, being the power consumption the same at 66 MHz. The sorter circuit design we propose does not exhibit the prohibitively hardware cost of the traditional approach. This eliminates the practical limitation for the implementation of digital functions using the sorter concept, as it has been shown with the case designs described herein. The new sorter exploits the high functionality of the uMOS transistor. So this circuit is another example of the potential that this kind of transistor has for digital design. References [1] Lamagna, E. A., "The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting and Merging", IEEE Trans. on Computers, C-28, 773-782, October, 1979. [2] Batcher, K. E. (1968). "Sorting Networks and their Applications", In: Proc. 1968 SICC, AFIPS, 32, 307-314. [3] Piestrak, S. J., "The Minimal Test Set for Multioutput Threshold Circuits Implemented as Sorting Networks", IEEE Trans. on Computers, 42, 700712, June, 1993. [4] Shibata, T. and Ohmi, T. (1990). "A Functional MOS Transistor Featuring Gate Level Weighted Sum and Threshold Operations", IEEE Trans. on Electron Devices, 39(6), 1444-1455. [5] Rodriguez, E., Quintana, J. M., Avedillo, M. J. and Rueda, A., "Sorting Networks Implemented as uMOS Circuits", Electronics Lett..ers, 34(23), 2237-2238, November, 1998. [6] Leblebici, Y., Ozdemir, H., Kepkep, A. and (ilingiroglu, U., "A Compact (88)-Bit Serial/Parallel Multiplier Based on Capacitive Threshold Logic", Proc. of the E..CCTD’95, pp. 55-58. [7] Ozdemir, H., Kepkep, A., Pamir, B., Leblebici, Y. and (ilingiroglu, U., "A Capacitive Threshold-Logic Gate", IEEE Trans. on Solid-State Circuits, 31(8), 1141-1150, August, 1996. [8] Muroga, S., Threshold Logic and its Applications, John Wiley & Sons, 1971. [9] Song, P. J. and De Micheli, G., "Circuit and architecture trade-off for high-speed multiplication", IEEE Trans. on Solid-State Circuits, 26(9), 1184-1198, September, 1991. IV. CONCLUSIONS Both an (8 x 8) serial/parallel multiplier and a (15,4) counter based on uMOS sorter circuits have been presented. The first one compares favorably in terms of speed, power and area to both conventional and capacitive threshold-gate-based implementations of the same architecture. The counter has a reduced delay when compared to a conventional approach. Authors’ Biographies Esther Rodriguez-Villegas received the B.S. degree in Electronics from the University of Sevilla, Spain in 1996. Since 1997 she is in the Institute of Microelectronics at Seville (IMSE) where is currently working toward the Ph.D. degree. Her main research interests is the design of Floating-Gate circuits for both digital and analog applications. 136 E. RODRGUEZ-VILLEGAS et al. Maria J. Avedillo joined the Department of Electronics and Electromagnetism at the University of Seville in 1988 as Assistant Professor, and obtained the Ph.D. degree in 1992. Since 1995 she is Associate Professor in that Department. In 1989 she became researcher at the Department of Analog Design of the National Microelectronics Center (CNM), now Institute of Microelectronics at Seville (IMSE). She has participated in several research projects financed by the Spanish CICYT and in ESPRIT Projects. She has published several technical papers in main international journals and conferences, and she won the KELVIN Premium of "The Council of the Institution of Electrical Engineers" for two articles published in 1994. Her current research interests include design of threshold logic circuits, development of CAD tools for FSM synthesis and design for testability. Jos M. Quintana joined the Department of Electronics and Electromagnetism at the University of Seville in 1983 as Assistant Professor, and obtained the Ph.D. degree in 1987. Since 1990 he is Associate Professor in that Department. In 1989 he became researcher at the Department of Analog Design of the National Microelectronics Center (CNM), now Institute of Microelectronics at Seville (IMSE). He has participated in several research projects financed by the Spanish CICYT and in the ESPRIT Projects ADCIS and AD-2000. He has published several technical papers in main international journals and conferences, and he won the KELVIN Premium of "The Council of the Institution of Electrical Engineers" for two articles published in 1994. His current research interests include design of threshold logic circuits, computer arithmetic and development of CAD tools for FSM synthesis. Gloria Huertas received the B.S. degree in Electronics from the University of Sevilla, Spain in 1997. Since 1998 she is in the Institute of Microelectronics at Seville (IMSE) where is currently working toward the Ph.D. degree. Her main research interests is the design of Floating-Gate circuits for both digital and analog applications. Adoraei6n Rueda joined the Department of Electronics and Electromagnetism at the University of Seville in 1976 as Assistant Professor, and obtained the Ph.D. degree in 1982. From 1984 to 1996 she was Associate Professor in that Department, where now holds the position of Professor in Electronics. In 1989 she became researcher at the Department of Analog Design of the National Microelectronics Center (CNM), now Institute of Microelectronics at Seville (IMSE). She has participated in several research projects financed by the Spanish CICYT, in the AFMIS Project included in the COMETT Program of the European Community, and in the ESPRIT Projects: ADCIS, AD-2000, AMATIST, ASTERIS and MICROCARD. She has also published several technical papers in main international journals and conferences, and she won the Best Paper Award of the 10th IEEE VLSI Test Symposium in 1992. Her current research interests are design and test of analog and mixed analog/digital circuits, and development of CAD tools. She is member of the Institute of Electrical and Electronic Engineers. Submit your manuscripts at http://www.hindawi.com Control Science and Engineering Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 International Journal of Rotating Machinery Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Part I Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Distributed Sensor Networks International Journal of ISRN Signal Processing Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Mechanical Engineering Advances in Modelling & Simulation in Engineering Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Advances in OptoElectronics Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 ISRN Sensor Networks Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 VLSI Design Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 The Scientific World Journal ISRN Robotics Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 International Journal of Antennas and Propagation Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 ISRN Electronics Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Journal of Sensors Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Active and Passive Electronic Components Chemical Engineering International Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Electrical and Computer Engineering Journal of ISRN Civil Engineering Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Advances in Acoustics & Vibration Hindawi Publishing Corporation http://www.hindawi.com Volume 2013