Abstract: In this study, a novel design of ternary multiplier and adder based on carbon nanotube field effect transistors is proposed to implement Galois field. Ternary logic is implemented utilizing the dependency of threshold voltage to diameter of carbon nanotube. Regarding the importance of multiplier and adder circuits in computer systems, the design of these circuits by field effect transistors with carbon nanotube channel will pave the way for production of more complex circuits and achieving computer systems in nano scales. The number of transistors and resistors in the proposed design is reduced compared to the design which uses multiple-valued logic basic operators.
INTRODUCTION
With the progress of CMOS circuits scaling, transistor dimension has been reducing more and more. This has led to more integrated circuits with higher complexity and efficiency (Raychowdhury et al., 2006). Due to the limitations of silicon based Field Effect Transistors (FETs), finding a proper substitute has become one of the main interests of researchers.
Carbon Nano Tube (CNT) studies carried out since 1991 revealed the unique morphologies and special characteristics of CNT such as: the relatively small dimensions, high mobility of electrons (Keshavarzian and Navi, 2007; Dwyer et al., 2004) and ballistic transport (Paul et al., 2006). Thus CNT has been suggested as an appropriate substitute for silicon.
As the manufacturing technology of very large scale integrated circuits meliorates, the number of transistors that chips embed and the number of functions that chips implement increases. Hence, more input and output pins are required. To reduce the interconnections caused by implementing VLSI circuits in binary logic, Multiple-Valued Logic (MVL) is suggested. The number of lines needed for data transfer in MVL is less than in binary logic (Damarla and Hossain, 1991).
Multiple-valued logic is capable of reducing the area consumption and solving the complexity of interconnection problem. Moreover, by using MVL fewer operations will be needed to implement a mathematical function (Raychowdhury and Roy, 2004). Multiple-valued logic has been employed by different approaches such as: current mode, voltage mode and hybrid mode.
This study introduces a novel design for two CNT circuits which can be the important building blocks of any computing system. Voltage mode is used to implement ternary radix Galois field. It is shown that number of transistors and resistors in the new design is considerably reduced and hence it can have many applications in nano circuits.
CARBON NANO TUBE FIELD EFFECT TRANSISTORS (CNTFETs)
Graphite is a major isotope of carbon which can be formed in the nano-scale as one of the following forms:
| • | Carbon Nano Ball (Bucky Ball) |
| • | Carbon Nano Coil (CNC) |
| • | Carbon Nano Tube (CNT) |
Carbon Nano Tubes are sheets of graphite that are rolled into the form of a tube. These cylindrical sheets are made of one or several layers of carbon atoms which are arranged in a honeycomb form. Single layer CNT can be either semi-conducting characteristics or metallic characteristics, depending on the arrangement of atoms. The conductivity and sturdiness of metallic CNT can be put to use in interconnections. In the other hand, semi-conducting feature of CNT is used in making field effect transistors. In 1998 the first carbon nanotube field effect transistors were demonstrated at Delft and at IBM (O’Connell, 2006). CNT transistors can be categorized into two types: The first is the ballistic CNTFET in which the channel exists inherently and the source and drain regions are doped. In the second type source and drain regions are metallic and transmission within the channel is controlled by electron tunneling through the Shottky barrier at the source-channel junction. In this study, we use ballistic carbon nano tube FETs due to the fact that they have higher on current (Raychowdhury et al., 2003).
CNTFETs can effectively change the voltage into current (Hashempour and Lombardi, 2007). High on current and on-off ratio are the other excellent electrical features of them (Keshavarzian and Navi, 2007; Hashempour and Lombardi, 2007). The smaller molecular structure makes it possible to do more scaling than what is practicable with the current lithographical techniques. Ballistic transmission reduces the CNTFETs power consumption and this makes them ideal for high speed computation.
Characteristics of carbon nano tube FETs are qualitatively similar to those of silicon FETs (Raychowdhury and Roy, 2004). Furthermore, carbon nano tube FETs have lower power consumption and higher speed in comparison to silicon FETs (Al-Rabadi, 2007).
BASIC OPERATORS OF MULTIPLE-VALUED LOGIC (MVL)
Let f(X) be an n-variable r-valued function where, X = {x1, x2,…,
xn} and each variable xi can take up values from R = {0,
1, 2,…, r-1}. This makes the function f(X) a mapping f : Rn→R
and hence
Definition: A min (minimum) operator is defined as:
min(a1, a2,…, an)
= a1•a2•…an |
where a1, a2,…, an belong to the set R.
Definition: A max (maximum) operator is defined as:
max(a1, a2,…, an)
= a1+a2 +…an |
where, a1, a2,…, an belong to the set R.
Definition: A tsum (truncated sum) operator is defined as:
| tsum(a1, a2,…, an) | = a1⊕ a2 ⊕…an |
| = min (a1+a2 +…an, r-1) |
where, a1, a2,…, an belong to the set R.
Definition: A logical complement operator is defined as:
|
ā = (r-l)-a |
where, a belongs to the set R.
Definition: A literal operator is a unary operator and is defined as:
Definition: A modsum operator is defined as:
modsum(a1, a2,…, an)
= (a1+a2 +…an) mod r |
where, a1, a2,…, an belongs to the set R.
By using basic operators of MVL different circuits can be implemented. min, tsum and not operators used in this study, are implemented by CNTFETs by Raychowdhury and Roy (2004). min and tsum operators have 6 transistors and 5 resistors. not operator has 2 transistors and 2 resistors.
Gate-Source and Gate-Drain capacitance and also Drain-Source current is calculated by the equations below (Raychowdhury and Roy, 2004):
(1) |
(2) |
(3) |
(4) |
(5) |
where, L is the length of nano tube and α, A and B are physical fitting parameters. N0 and εs/d are obtained from the equations below:
(6) |
(7) |
VΠ is the C-C (carbon-carbon) bonding energy (=3 ev), b is the C-C bonding distance (=0.142 nm) and Δ1 is given by the equation below:
(8) |
where, Ψs is the source potential and μs and μd are the source and the drain Fermi-Levels, respectively.
GALOIS FIELD
A field is a set with two operations that are closed with respect to that set. These operations are multiplication and addition. A Galois field is a field with finite number of elements equal to a prime number or some power of it (Zilic and Vranesic, 1993). The usual notation for Galois fields is GF(Pn), where P is a prime number and n is an integer number. Binary Galois field, GF(2), is implemented by XOR and AND gates. Which correspond to addition and multiplication operations, respectively. In this study we’ve implemented ternary radix Galois field. Figure 1 represents the multiplication and addition truth table of GF (3). It can be seen that in every row of the addition table in Fig. 1, elements are all different. These elements are repeated in every raw in a cyclic order. Moreover, if the zero elements (shaded in the table) are removed from the multiplication table, then the remaining elements will have the same cyclic repeating order (Kalay et al., 1999; Zilic and Vranesic, 1993).
Due to the cyclic group property of the multiplication and addition operators, Galois field circuits are highly testable and any single fault changing the input value will lead to the output value alteration as well. Hence, this characteristic is very useful in fault detection (Kalay et al., 1999).
In MVL, there have been many ways suggested to represent the logical functions in canonical form and to simplify them. Every multiple-valued logic function can be expressed as sum of minterms or product of maxterms. Minterm is obtained by use of min operator on literals and a constant (Dueck, 1999). Three operators min, max and literal makes a functionally complete set and accordingly every multiple-valued function can be represented using them (Tang et al., 1998). This approach suggested by Allen-Givone is a powerful method however, in case of functions with noncontiguous minterms where simplification is not possible it leads to more terms (Damarla and Hossain, 1991). min, literal and tsum operators can also be employed for multiple-valued function representation (Yildirim et al., 1993). Another approach is proposed by Dueck (1999) which utilizes the min and modsum operators (Damarla and Hossain, 1991). Thanks to the cyclic property of modsum operator, testability of this approach is enhanced compared to the preceding ones.
Reed-Muller transform is an approach in which the Galois field has a key role in circuit design (Zilic and Vranesic, 1995). This transform consists of polynomial representation of logical functions over finite fields. Using this approach in binary logic, GF(2) is implemented by AND and XOR gates.
| Fig. 1: | GF(3) multiplication and addition truth table |
By changing field radix, Reed-Muller transform can be utilized in Galois fields with different radices and multiple-valued functions can be implemented by means of multiplication and addition.
High testability of GF multiplication and addition operators makes it suitable for function representation since it introduces superior testability than the approach which applies modsum and AND (Kalay et al., 1999).
Furthermore, Galois field is employed in a wide variety of applications such as: error correction coding, cryptography and polynomial function implementation (Zilic and Vranesic, 1995; Al-Rabadi, 2007). Taking into account the high applicability of Galois field and its importance in multiple-valued functions representation and simplification, we aim to implement Galois field in this study.
A NOVEL GALOIS FIELD DESIGN
Here, we specify the proposed design of GF(3) multiplication and addition operators using CNTFETs. In this implementation supply voltage has been chosen to be 1.5 V (VDD) which ensures sufficient static noise margin. Voltage values less than 0.5 V are taken as logic 0, voltage values between 0.5 V and 1 V are interpreted as logic 1 and voltage values between 1 V and 1.5 V are regarded as logic 2. This implementation consists of CNTFET transistors with two different diameters, 1.4 and 0.5 nm. These nanotube transistors have the corresponding threshold voltages Vth1 = 300 mV and Vth2 = 840 mV, respectively.
Multiplication circuit: Figure 2 shows the circuit realization of multiplication operation. In this circuit, output is set to logic 0 using a pull up network. In the pull down network, circuit is divided into two separate sections; the one with the resistor set the circuit output to logic 1 by voltage division and the other section set the output to logic 2. Here, we have used two variables a and b and their complements as input. The compliment consist of two 100 KΩ resistors and two transistors (Raychowdhury and Roy, 2004).
In multiplication operation if any of the inputs is zero then the circuit output will equal zero. Thus, in the pull down network transistors are arranged in a way in which there is no path available and all transistors are off.
| Fig. 2: | GF(3) multiplication circuit using CNTFETs. The diameter of transistors
T1, T2, T3, T4, T7, T8, T10 and T11 is 1.4 nm and the diameter of the other
transistors (T5, T6, T9 and T12) is 0.5 nm |
Let us consider some examples to verify the circuit operation. Consider the case in which the inputs a and b are 0 and 1, respectively. Since, the pull down network path is off, the output outz is set to 1.5 V by pull up network path and hence circuit output goes to logic 0.
Now lets examine the case in which the inputs a and b both get the value of logic 1 or logic 2. Here, the output outz will go to
by one of the paths in the resistor section of the pull down network. When the inputs are both logic 1, the compliment will be the same as input. As a result transistors T1, T2, T3 and T4 that have the threshold voltages Vth1 = 300 mV go on and consequently the circuit output goes to logic 1. When the inputs are both logic 2, transistors T5 and T6 threshold voltages Vth2 = 840 mV go on.
Now, consider the case in which one of the inputs a and b is 1 and the other is 2. In this case, resistor path transistors all go off. Transistors T7 and T8 with threshold voltages equal to 300 mV and T9 with threshold voltage equals to 840 mV go on and the output outz gets the logic 0.
As it is explicitly shown in Fig. 2, the multiplication circuit has 2 resistors and 12 carbon nanotube field effect transistors.
| Fig. 3: | GF(3) addition circuit using CNTFETs. The diameter of transistors T1,
T2, T3, T8, T13, T14, T15 and T16 is 0.5 nm and the diameter of the other
transistors (T4, T5, T6, T7, T9, T10, T11 and T12) is 1.4 nm |
The not gate
also adds 2 more resistors and transistors. Moreover, the complement of inputs,
ā and
Addition Circuit: GF(3) addition circuit using CNTFETs is provided in Fig. 3. The circuit inputs are a, b and their complements. Resistors used are all of 100 KΩ. In case that inputs a and b are, respectively 0 and 0 or 1 and 2 or 2 and 1, all transistors of the pull down network go off and the circuit output equals logic 0.
Consider the case in which the inputs a and b are 0 and 1, respectively. T6, T7 and T8 transistors which have the corresponding threshold voltages 300, 300 and 840 mV, respectively, go on. The output outz goes to
by the path in resistor section on the pull down network and hence it equals logic 1.
Now, if the input values of a and b swaps, a = 1 and b = 0, transistors T3, T4 and T5 with threshold voltages 840, 300 and 300 mV, respectively, go on and output circuit equals 1.
In case that both inputs a and b are 2, then the T1 and T2 transistors both with threshold voltages equal to 840 mV go on and the circuit output is logic 1.
| Table 1: | Number of transistors and resistors required for multiplication and addition circuits implementation in ternary logic |
Consider the case where, a and b are both 1.Then the transistors T9, T10, T11 and T12 all with the threshold voltage 300 mV will go on and the circuit output will be 2 by the path in the non-resistor section of the pull down network. If a = 2 and b = 0 then T15 and T16 transistors with threshold voltage 840 mV will go on and circuit output will be 2. Now, if it is vice versa and a = 0 and b = 2, the transistors T13 and T14 go on and output outz is 0.
Figure 3 depicts 2 resistors and 16 carbon nanotube transistors. Similar to the multiplication circuit, by taking into account the not gates, the total number of resistors and carbon nanotube field effect transistors in the proposed addition circuit will be 8 and 22, respectively.
RESULTS
Ternary Galois field implemented with min, tsum and literal operators will have the canonical form represented below:
axb = 1●2a2●2b2⊕2●2a2●1b1⊕2●1a1●2b2⊕1●1a1●1b1 |
(9) |
|
a+b = 1●0a0●1b1⊕2●0a0●2b2⊕1●1a1●0b0⊕2●1a1●1b1⊕2●2a2●0b0 ⊕1●2a2●2b2 |
(10) |
According to the Eq. 9 and 10, number of min operators needed to implement multiplication and addition is 8 and 12, respectively. Also number of required tsum operators is 3 and 5. Furthermore, 4 literal operators are essential for multiplication and 6 for addition. In case that operator set is chosen to be min, max and literal, the number of min and literal operators required won’t differ and the number of max operators will be 3 and 5 for the multiplication and addition, respectively.
As it is shown in Table 1 even if the literal operators are disregarded, number of transistors and resistors used in this proposed approach is far less than these approaches.
CONCLUSION
High testability of Galois field along with its great applicability in mathematical and logical function representation makes the implementation of multiple-valued circuits using multiplication and addition operators to be very efficient. In this study a novel design for ternary multiplication and addition circuits in voltage mode has been proposed as the basic circuits. The proposed multiplication circuit reduces the number of transistors by at least 72.73% and the number of resistors by at least 85.45%. Moreover, number of transistors and resistors in the proposed addition circuit is reduced by at least 78.43 and 90.59%, respectively.
According to the promising advantages of this new design in reducing the number of circuit elements and very unique characteristics of carbon nanotube field effect transistors and also due to the high testability of Galois field, using the proposed circuits as the building blocks in designing ternary valued logical circuits and implementing mathematical functions will lead to a major reduction in size and power consumption and will bring a certain improvement in testability.