Multi-Valued Logic Digital Circuits for Realizing a Complete Computer Architecture

Abstract

The objective of this paper is to lay the foundation for the construction of a computer architecture using entirely multivalue logic (MVL). To achieve this ambitious result, it is necessary to know how to design all the digital components that normally form the basis of a computer's operation. These are combinational circuits dedicated to mathematical computation and sequential circuits in charge of storing information. In the paper, a general methodology is proposed that can be used for the construction of digital circuits capable of working independently of the basis of representation of multivalue logic and the physical quantity used for encoding logical states.

Keywords

• eol>MVL
• Multi-valued logic
• CPU
• Computer architecture
• digital circuit
• adder look ahead

1. Introduction

The subject of multivalue logic as a natural evolution of representation in the binary system is a much debated issue [ 1 ], [ 2 ]. Although various solutions, including technological ones, have been proposed, but at present there is no calculator capable of operating in multivalued logic [ 3 ], [ 4 ], [ 5 ]. However, with the arrival of memresistors [ 6 ] and a multiplicity of multi-state semiconductor components, the scenario is evolving and the theory developed in [ 7 ] could find easy application. The theory we are going to describe is based on the extension of Boolean algebra and the binary numbering system toward an -valued (discrete) numbering system [ 8 ], [ 9 ]. In this paper we will start from the theoretical definition and gradually go on to realize all the digital components that characterize a traditional computer architecture. 2. Method (, 1, ..., − 1) = − 1 − 1 ∑︁ · ∏︁ ()( ) =0 =0 (2) where: • is the value taken at the i-th position in the combination, with ∈ T; • () is the j-th digit of the number , represented in base with ∈ {0, ..., − 1}; • () is the value selector () applied to operand with ∈ {0, ..., − 1} e ∈ {0, ..., − 1}; Thus, to express any MVL function , p+2 basis function are suficient: selection, addition and multiplication functions.

2.1. The selection functions

The proposed method use the teory in [ 10 ]. Assum- The selection functions with ∈ {0, ..., − 1}, that we ing that we have a domain of discrete values T = can call Selectors too, are unary functions. We can define {0, 1, .., − 1}, we can easily show that any function : as many selectors as there are symbols in the domain T. : T × ... × T → T

(1) can be expressed as a linear combination of the input variables: : T → B A selector is able to check whether the value of the operand matches a value in the set T: () = {︃1 = 0 ̸= (3) (4) with , ∈ {0, ..., − 1}. Using the selection functions, any combination of the input variables can be identified.

For example, to check if all variables 0, ..., − 1 have the value − 1 except 0 which must be equal to 1, we can use the following function:

= 1(0) · − 1(1) · ... · − 1(− 1) which returns the value 1 exclusively in the case where the input variables meet the requirement:

(0, ..., − 1) = (1, − 1, ..., − 1) 2.2. Sum Let us consider the summation of equation 2, we observe that only one term in the summation will be valued at corresponding to the coding in base of . Indeed, all the terms of the summation are null except the one corresponding to the combination identified by the selection functions:

(, 1, ..., − 1) =

2.3. Multiplication

With reference to the generic term of the summation of the equation 2, it can be expressed by a function : that is equivalent to : thus: : T × B × ... × B → T

: T × B → B · 0 · 1 · ... · − 1 = · (0 · 1 · ... · − 1) = · (10) Indeed, it is suficient to make a function with two operands: one MVL and the other binary. This function returns as output the value of the multivalue input (if the binary value is unity) or zero in the other case: (, ) = {︃0 = 0 = 1 (5) (6) (7) (8) (9) (11)

3. MVL digital circuits

In this section, we will see how it is possible to construct all the circuits that form the basis of a traditional computer architecture [ 11 ], [ 12 ]. Thus, we will start with combinational circuits, those in which the output is a function of the inputs, and then we will consider the smallest memory element, the D Latch. To accomplish this task we will use the same architectural choice made in [ 10 ], and supported by studies in [ 13 ], thus a logic based on 4 values that coincides with the base-4 numbering system. The four logic values will be represented through the voltage levels as reported in table 1.

We also studied the behavior of the proposed circuits by verifying the limits of the adopted components [ 14 ], [ 15 ], [ 16 ]. In particular, the details for the configuration of the components are the following: • AND and OR logic gates: • inverted gates: – Td = 10n – Ref = 0.5 – Trise = 5n – Tfall = 5n – Vhigh = 5 – Td = 5n – Ref = 0.5 – Trise = 5n – Tfall = 5n – Vhigh = 5 with ∈ T and ∈ B.

Recalling that the logical conjunction operation returns 3.1. LTSpice a result that is equivalent to multiplication between bits (the result is one if and only if all the operands are 1), we The electronic circuits that we will describe, were decan conclude that it is possible to use the AND operator signed and validated using the product LTspice® XVII by to compute the value in the binary domain. At this Analog Device Corporation [17], distributed on the develpoint it is possible to use that bit to calculate the MVL oper’s website. This simulator has a graphical interface function (, ). Without loss of generality and with the to build the schematics and allows the user to test the purpose of making the paper easier to read, we will use circuits. The tool also allows new features to be defined the symbol normally used for multiplication to denote the and imported as elements in the various schemes. Therefunction conscious of the fact that it is multiplication fore, we chose to reuse the circuit diagrams proposed in between values pertaining to diferent domains ( B ⊆ T). [ 10 ] regarding the selectors, multiplexer and half-adder to design new ones.

3.2. Combinational Circuits

with , , ∈ T and , +1, , ∈ B MVL look-ahead adder In this section we will study the behavior of the circuit MVL look-ahead adder of 4- Figure 2: Look-ahead full adder blocks scheme digit base-4 words. In [ 7 ] a half-adder consisting of two inputs and two outputs in base 4 has already been presented, and starting from this circuit the authors design as indicated in table 3. a full-adder in [ 10 ]. The most obvious problem with this circuit is the response time, which depends on the prop- Table 3 agation delay of the carryover in the various half-adders. Adding two MVL words of length The time grows as the number of digits of operands and it[sh18un]so,th[1aa9lfef]c-.ateIdndddeberyesdtu,hsieneddaetloloaoycokon-afshtcreiuraccdutiattdhedeleearmdtdehenertcsianprclrrayecoaevsdeesr −−− 111 ......... 000 += in cascade. Consider two MVL words of length : − 1 ... 0 = {− 1, ..., 0} and = {− 1, ..., 0}, if the calculated carryovers are = {, ..., 1} and 0 is the potential carryover of a previous least significant word, we can calculate the sum word = {, ..., 0}

If by the variables and we denote the generated and propagated carryover, respectively, we can build the truth table (table 2) related to the sum of two generic MVL digits. The values of and are given by the a switch driven by a binary signal, can send the value relation 12 for a cirucite in which the signals are in base corresponding to 1 to the second half-adder. The adder n. circuit will use two half-adders to calculate = + + ; the variable will be calculated from the first = {︃01 ++ ≤> −− 11 (12) fhuanlfc-taidodnetrowuhnidleerstawndillwbheectahlecrulate+d usin=g th− e s1el(efigcutrioen 1). This component will be replicated for each couple of {︃0 + = − 1 input in order to build a look-ahead adder as in figure = 1 + ̸= − 1 (13) 2. In figure 3 a look-ahead adder circuit with 4 MVL digits is made. This circuit can be used to perform MLV In the same way, in the case of the MVL, we can determine word sum with lengths multiple of 4: for example, we can in advance the values of the carryovers +1 from the add up 8 MVL digits by cascading two circuits (figure 4). variables and . Using the symbols ∑︀ and ∏︀, for The behavior of the circuit is verified through a concrete logical disjunction (OR) and logical conjunction (AND), example: suppose we add the value = 310200023 respectively, we can write the equation 14. with = 33212131 and that the carryover 0 will be 0. The expected result is the number S=130232220 as can be easily seen from the calculation shown in the table 4.

(14) However, the values of the carryovers (+1), determined in such a way, are in the binary domain, instead we need the value corresponding to the logical level 1 of the table 1. Then a transduction element is needed that, through

Decoder A decoder is a combinational circuit with inputs and outputs. It returns as output the decoded form of a coded word given as input.

Starting with the most basic decoder, which decodes a single digit in the four possible values, we will construct the decoder that decodes two-digit words. Making a single-digit decoder is a simple task because it is suficient to use the selection functions by applying them to the same input (figure 5). Since we have two one-value decoders, it is possible to construct a decoder with = 2 and 42 = 16 outputs (figure 6) using an AND gates array that realizes all possible combinations of pairs relative to the outputs of the two decoders. The figure 6 shows the circuit with the components X2 and X3 representing single-digit decoders. In this case, if the input is the number 134 (1 = 1 and 0 = 3) the only enabled digit in output would be 7 (logic level 1) . Encoder The encoder is a combinational circuit too, that receives as input MVL digits and returns as output {︃1 = MVL digits. It performs the opposite function to the ( ) = 0 ̸= (15) decoder: it receives a decoded representation as input and provides the corresponding encoding as output. The Based on the value of the input IN, it will select the cor- figure 14 shows an encoder with 16 inputs and 2 outputs. responding output (level 1), while all other outputs will Each input passes through a switch that detects be zero (level 0), according to what reported in table 5. the 1 level at the input (equation 16).

To make the circuit simpler, we grouped the selector switch outputs that would determine the same value on the output signals 1 and 2. Note that the output of each enabled switch causes its closure, which brings the output level value. For example, if 7 = 1 the output of selector 8 enables the OR gates that determine 1 = 1 and 0 = 3.

(17) =

0 ℎ

For example, if = 3 there will be 3 = 1.

The output signal from the selectors block 2 enables Demultiplexer The demultiplexer (or simply demux) is a circuit typically used to restore multiplexing produced by a multiplexer in communications. Its treatment 17 · = (41 + 40) · = 41 · + 40 · (18) in MVL can be found in [ 10 ]. It consists of data inputs, selection signals and an output. It takes a value equal Right Shifter The shifter right moves the digits to to the input line corresponding to the decoding of the the right by as many positions as specified in a dedicated data word. The figure 8 shows the simplest MVL demux line. For integers this corresponds to performing a diviwith 4 data lines and selection input SEL of data lines. sion of the number with respect to the base. Since these To make the circuit, we used a selector block (module are components that can be used in series to perform opX2) that contains the 4 basic selectors. The output of the erations on multiple digits, we must provide for receiving block determines which signal of the circuit will and sending these digits to adjacent modules (figure 9). end up in the input. The equation 17 describe the In the following examples, we will use 4-digit words, and behavior of the output. the lines of communication with adjacent modules will be 3. Indeed, the variable indicating the number of {︃ = 1 digits to be moved can take 4 values (including zero).

the corresponding switch by propagating the IN signal to the output 3.

Shifter In this section we will look exclusively at parallel-type shifters, which are normally used to perform mathematical operations (e.g. multiplication and division by base). In general, having a summation and a shifter makes it possible to perform multiplication and division operations for general numbers as long as they are expressed in terms of the base [20]. An example of multiplication between 17 and a generic number , with ∈ N, performed through the use of shifting and addition, is given in the equation 18.

Right Rotate Shifter In this section we wanted to show the simplicity of implementation of a 4-digit word rotation shifter. A selection input determines the number of shifts in the word (figure 11).

Left Shifter Similar to what we described for the right shifter, the left shifter moves the input signals to the left. For integers it corresponds to a multiplication by the base. The figure 12 shows the circuit with 7 data inputs and a selection signal . In this case, each module can expect the arrival of three digits from the one located to its left. Meanwhile, the module under consideration can shift three values of its base word to the left.

In this case if = 0, the most significant outputs are set to 0, enabling the input 0 of the first three multiplexers on the left of the figure ( 8,10, 9). The outputs 6, 5 and 4 are set to level zero. In this case the inputs 1,2,3 do not compete with the outputs. As the value of the signal increases, the inputs will be shifted to the left until 3 moves from the output 3 to 6 ( = 3) and three new signals will be present on 0, 1 and 3.

3.3. Sequential Circuits

A digital circuit is said to be sequential if the output depends on the inputs applied and the state of the circuit. In contrast, in combinational circuits the output is uniquely determined by the values of the inputs. Thus, a sequential circuit has the ability to store information through feedback in the circuits that allows the informative content calculated in the past to be brought back into the input due to the non-instantaneous propagation times in the semiconductors. We will then realize the D latch circuit in MVL logic.

D Latch The schema of the D latch is shown in figure 13, and it consists of two cascaded multiplexers in which the output of the first one determines the selection of the input of the second one. The data signal lands in all data inputs of the first mux except the input 0. Indeed, in 0 comes the output data of the second mux. A clock signal , which intermittently takes on the values 0 and 1, allows selection between the new data present in ( ≥ 1) and the one previously calculated ( = 0).

To verify the operation of the D latch, we used an articulated data signal (table 6) so as to check that the circuit had the desired behavior.

4. Limits and Future Works

New circuits in multivalue logic may be a step toward addressing the computational problems of certain applications such as artificial intelligence and blockchain. The amount of time, energy, and resources to deliver certain services is increasing more and more, and traditional circuits seem unresponsive to current needs [21],[22], [23].

We presented several theoretical solutions, and many of them are aligned with new technological solutions [24], [25], such as mem-resistors [26] or programmable resistor arrays in complex layers [27]. These last components were developed by Massachusetts Institute of Technology (MIT) to create neural networks to support a new area Figure 16: Testing D Latch: outputs of artificial intelligence called analog deep learning.

The lack of integration of models developed with such technologies is one of the limitations that must be over- employ bases that are powers of two; future eofrts will come to make the use of this logic efective. focus on this type of logic.

The first step in achieving the target of usability of such The proposed work has two important advantages over logic within circuits is their integrability within current what has been produced in the literature on MVL syssystems in digital logic. To this end, it is desirable to tems:

5. Conclusion

The idea behind this paper is that it is possible to make MVL circuits capable of performing the same functions available to digital circuits. A multi-valued logic system reduces the significant amount of design efort, reduces power consumption, increases the data rate between devices, and minimizes the cost of signals [ 28, 29, 30, 31 ].

References

[1] E. Dubrova , Multiple-Valued Logic in VLSI: Challenges and Opportunities , Proceedings of NORCHIP'99 ( 1999 ).

[2] D. Etiemble , 45 -year CPU Evolution: one law and two equations , Second Workshop on Pioneering Processor Paradigms, Vienna, ( 2018 ).

[3] R. A. Jaber , B. Owaidat , A. Kassem , A. M. Haidar , A novel low-energy cntfet-based ternary half-adder design using unary operators , in: 2020 International Conference on Innovation and Intelligence for Informatics, Computing and Technologies (3ICT) , 2020 , pp. 1 - 6 . doi: 10 .1109/3ICT51146. 2020 . 9311953 .

[4] R. Zhang , N. Uetake , T. Nakada , Y. Nakashima , Design of programmable analog calculation unit by implementing support vector regression for approximate computing , IEEE Micro 38 ( 2018 ) 73 - 82 . doi: 10 .1109/MM. 2018 . 2873953 .

[5] A. Navidi , R. Sabbaghi-Nadooshan , M. Dousti , Tqcasim: An accurate design and essential simulation tool for ternary logic quantum-dot cellular automata , Scientia Iranica ( 2021 ). URL: http://scientiairanica.sharif.edu/article_22243. html. doi: 10 .24200/sci. 2021 . 53471 .3256.

[6] X. Wang , P. Li , C. Jin , Z. Dong , H. H. C. Iu , General modeling method of threshold-type mul- tional Academy of Sciences 116 ( 2019 ) 7750 - 7759 . tivalued memristor and its application in digital URL: https://www .pnas.org/doi/abs/10.1073/pnas. logic circuits, International Journal of Bifurca- 1820672116. doi:10.1073/pnas.1820672116. tion and Chaos 31 ( 2021 ) 2150248 . URL: https:// [17] Analog Devices , LTspice, 2022 . URL: doi.org/10.1142/S0218127421502485. doi: 10 .1142/ https://www.analog.com/en/design-center/ S0218127421502485. design-tools-and-calculators/ltspice-simulator.

[7] A. Simonetta , M. C. Paoletti , Designing digital html. circuits in multi-valued logic , International [18] S. Raksha , Carry Look-Ahead Adder Journal on Advanced Science , Engineer- - Working , Circuit and Truth Taing and Information Technology 8 ( 2018 ) ble, 2020 . URL: https://technobyte.org/ 1166- 1172 . URL: http://ijaseit.insightsociety. carry -look-ahead-adder-working-circuit-truth-table/ org/index.php?option=com_content&view= (May2022). article&id=9&Itemid=1&article _id= 5966 . [19] WatElectronics , What is Carry Lookahead doi: 10 .18517/ijaseit.8.4.5966. Adder : Block Diagram and Its Working,

[8] W. Alexander , The ternary computer, Electron- 2021 . URL: https://www.watelectronics. com/ ics and Power 10 ( 1964 ) 36 - 39 . doi: 10 .1049/ep. carry -lookahead-adder/(May2022 ). 1964 . 0037 . [20] A. S. Tanenbaum , Structured Computer Organiza-

[9] B. Choi , K. Shukla , Multi-valued logic circuit de- tion, Pearson, 2012 , p. 808 . sign and implementation, International Journal [21] X. Chen , Y. Wardi , S. Yalamanchili , Power reguof Electronics and Electrical Engineering 3 ( 2014 ). lation in high performance multicore processors , doi:10.12720/ijeee.3.4 . 256 - 262 . in: 2017 IEEE 56th Annual Conference on De-

[10] A. Simonetta , M. C. Paoletti , M. Muratore, cision and Control (CDC) , 2017 , pp. 2674 - 2679 . A new approach for designing of computer doi :10.1109/CDC. 2017 . 8264047 . architectures using multi-value logic , Inter- [22] G. C. Cardarilli , L. D. Nunzio , R. Fazzolari , M. Re, national Journal on Advanced Science , Engi- F. Silvestri , S. Spanò , Energy consumption savneering and Information Technology 11 ( 2021 ) ing in embedded microprocessors using hardware 1440-1446 . URL: http://ijaseit.insightsociety. accelerators, TELKOMNIKA (Telecommunication org/index.php?option=com_content&view= Computing Electronics and Control) ( 2018 ). article&id=9&Itemid=1&article _id= 15778 . [23] G. Cardarilli , L. Di Nunzio , R. Fazzolari , M. Re, doi:10.18517/ijaseit.11.4.15778. R. Lee , Butterfly and inverse butterfly nets inte-

[11] "Nagarathna , S. Jamuna , "a brief review on multiple- gration on altera nios-ii embedded processor, in: valued logic-based digital circuits" , in: T. "Sen- Conference Record of the 44th Asilomar Conferjyu , P. N. Mahalle , T. Perumal , A . Joshi (Eds.), "ICT ence on Signals, Systems and Computers, Asilowith Intelligent Applications", "Springer Singapore" , mar 2010 , Conference Record - Asilomar Confer2022. ence on Signals, Systems and Computers , 2010 ,

[12] N. I. Chernov , N. V. Butyrlagin , N. N. Prokopenko , pp. 1279 - 1283 . doi:https://doi.org/10.1109/ V. Y. Yugai, Synthesis and circuitry of multi-valued ACSSC . 2010 . 5757737 , 44th Asilomar Conferdigital current logic elements , in: 2021 Interna- ence on Signals, Systems and Computers , Asilotional Conference on Electrical Engineering and mar 2010 ; Conference date: 07 - 11 -2010 Through Photonics (EExPolytech) , 2021 , pp. 104 - 107 . doi: 10 . 10 - 11 - 2010 . 1109/EExPolytech53083. 2021 . 9614916 . [24] H. Yoo , C.-H. Kim, Multi-valued logic system: new

[13] N. K. Naware , D. S. Khurge , S. U. Bhandari, Re - opportunities from emerging materials and devices, view of quaternary algebra & its logic circuits , 2015 J. Mater. Chem. C 9 ( 2021 ) 4092 - 4104 . URL: http: International Conference on Computing Commu- //dx.doi.org/10.1039/D1TC00148E. doi: 10 .1039/ nication Control and Automation ( 2015 ) 969 - 973 . D1TC00148E .

[14] D. Rene , Random Testing of Digital Circuits: Theory [25] Z. Zhang , A. Xu, H. T. Ren , G. Liu, X. Cheng, Reand Applications, CRC Press, 2020 , p. 496 . configurable multivalued memristor fpga model for

[15] D. Kaufmann , Formal verification of mul- digital recognition, International Journal of Cirtiplier circuits using computer algebra, it cuit Theory and Applications ( 2022 ). URL: https:// - Information Technology ( 2022 ). URL: https:// onlinelibrary.wiley.com/doi/abs/10.1002/cta.3377. doi.org/10.1515/itit-2022-0039. doi:doi:10.1515/ [26] B. Mouttet , Dynamic systems model for ionic memitit-2022-0039. resistors based on harmonic oscillation , arXiv:

[16] D. J. Preston , P. Rothemund , H. J. Jiang , M. P. Ne- Mesoscale and Nanoscale Physics ( 2011 ). mitz, J. Rawson , Z. Suo , G. M. Whitesides , Digi- [27] A. Zewe , New hardware ofers faster computatal logic for soft devices , Proceedings of the Na- tion for artificial intelligence , with much less energy , 2022 . URL: https://news.mit.edu/2022/ [38] G. L. Sciuto , G. Susi, G. Cammarata, G. Capizzi , A analog-deep-learning-ai-computing-0728. spiking neural network-based model for anaerobic

[28] R. A. Jaber , A. Kassem , A. M. El-Hajj , L. A. El - digestion process , in: 2016 International SympoNimri, A. M. Haidar, High-performance and energy- sium on Power Electronics, Electrical Drives, Aueficient cnfet-based designs for ternary logic cir- tomation and Motion (SPEEDAM) , IEEE, 2016 , pp. cuits , IEEE Access 7 ( 2019 ) 93871 - 93886 . doi: 10 . 996 - 1003 . 1109/ACCESS. 2019 . 2928251 .

[29] K. Kobashi , R. Hayakawa , T. Chikyow , Y. Wakayama , Multi-valued logic circuits based on organic anti-ambipolar transistors , Nano Letters ( 2018 ). doi: 10 .1021/acs.nanolett.8b01357.

[30] G. Magistris , C. Rametta , G. Capizzi, C. Napoli , Fpga implementation of a parallel dds for wide-band applications , in: CEUR Workshop Proceedings , volume 3092 , 2021 , pp. 12 - 16 .

[31] M. H. Moaiyeri , Z. M. Taheri , M. R. Khezeli , A. Jalali , Eficient passive shielding of mwcnt interconnects to reduce crosstalk efects in multiple-valued logic circuits , IEEE Transactions on Electromagnetic Compatibility 61 ( 2019 ) 1593 - 1601 . doi: 10 .1109/ TEMC. 2018 . 2863378 .

[32] S. Illari , S. Russo , R. Avanzato , C. Napoli , A cloudoriented architecture for the remote assessment and follow-up of hospitalized patients , in: CEUR Workshop Proceedings , volume 2694 , 2020 , pp. 29 - 35 .

[33] G. Lo Sciuto , S. Russo , C. Napoli , A cloud-based lfexible solution for psychometric tests validation, administration and evaluation , in: CEUR Workshop Proceedings , volume 2468 , 2019 , pp. 16 - 21 .

[34] G. De Magistris , R. Caprari , G. Castro, S. Russo , L. Iocchi , D. Nardi , C. Napoli , Vision-based holistic scene understanding for context-aware humanrobot interaction , Lecture Notes in Computer Science (including subseries Lecture Notes in Artiifcial Intelligence and Lecture Notes in Bioinformatics) 13196 LNAI ( 2022 ) 310 - 325 . doi: 10 .1007/ 978-3- 031 -08421-8_ 21 .

[35] C. Napoli , F. Bonanno , G. Capizzi, Exploiting solar wind time series correlation with magnetospheric response by using an hybrid neuro-wavelet approach , Proceedings of the International astronomical union 6 ( 2010 ) 156 - 158 .

[36] G. Capizzi , G. Lo Sciuto , M. Woźniak , R. Damaševicius , A clustering based system for automated oil spill detection by satellite remote sensing , in: Artificial Intelligence and Soft Computing: 15th International Conference, ICAISC 2016 , Zakopane, Poland, June 12-16, 2016 , Proceedings, Part II 15 , Springer, 2016 , pp. 613 - 623 .

[37] N. Brandizzi , S. Russo , R. Brociek , A. Wajda , First studies to apply the theory of mind theory to green and smart mobility by using gaussian area clustering , in: CEUR Workshop Proceedings , volume 3118 , 2021 , pp. 71 - 76 .