178 Structural constructions of computer engineering elements in k-valued logic © Volodymyr Yartsev 1 and © Dmitry Gololobov 2 1 State University of Telecommunications, Kyiv, Ukraine 2 National Aviation University, Kyiv, Ukraine jvp57@ukr.net, gololobov.dma@meta.ua Abstract. Methods are proposed for implementing the logical functions of digital devices without memory and with memory using three-valued logic obtained us- ing direct and inverse multiplexer circuits as a logical basis. This simplifies the development of digital logic circuits with a large number of input arguments, reduces the number of tiers of the tree structure of the circuit implementation. Using a multiplexer to perform operations in three-valued logic allows reducing the number of logical elements in the structure of a digital device, reducing the delay time when generating a control signal, and using existing microcircuits with transistor-transistor logic. As an example, structural synthesis of a finite state machine recognizing a given combination is given. Keywords: digital devices, logical basis, finite-state machine, logic function, multiplexer, ternary adder, ternary trigger. 1 Introduction In modern discrete mathematics and the theory of building digital technology, an im- portant place is occupied by the problem of building state machine based on the con- version of Boolean functions. Various digital devices on which artificial intelligence systems, control systems are built, solve complex computational problems based on elementary binary operations. But today, the physical and technological parameters of binary logic microchips have reached the practical limit in both size and speed. Further growth of these indicators is associated with the use of calculators that work in multi- valued alphabets [1]. The complexity of the tasks that digital devices perform is constantly growing. This requires an increase in the operating frequency, the number of logic elements in the circuits, and at the same time, a reduction in the cost of power consumption. The use of multi-valued logic is one way to resolve these problems. The multi-valued logic pro- vides more opportunities for the development of various information processing algo- rithms, which allows to reduce the computational complexity, the number of elements and connections in various signal conditioning devices, increase the density of ele- ments, increase the speed and volume of processed data [2]. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 179 Professor of Stanford University D. Knut in his book "The Art of Programming" emphasized that ternary logic is more elegant and more efficient than binary, and in the future, humanity will again return to its development [3]. The multi-valued logic has been widely used to solve the problems of data transmission and storage, the formation of a visual display of graphic information and the processing of complex digital signals [4]. The following conclusions can be drawn from the analysis of literary sources. Most of the technical solutions of the sets of logic and operating devices use a symmetric triple system with a set of signals corresponding to the values of ‒1, 0, +1, which are technically implemented on the threshold elements of three-valued logic in integrated electronics [5- 6]. 2 Problem Formulation In this paper, the theoretical and practical problems of the implementation of digital devices, in particular, the finite state machine, in ternary number system are considered. Digital devices in this number system are the simplest in technical implementation com- pared to other positional number systems with a base of more than two [7]. In addition, ternary computers are considered promising for the creation of artificial intelligence, since ternary logic is the most natural way of thinking from the point of view of human thinking, and the cognition process, along with the categories "yes" and "no" to describe the state of uncertainty, the meaning of "unknown" or "may be". Note that three-valued logic is considered as a possible replacement for binary logic in the development of quantum computers [8–9]. To construct structural schemes in any multi-valued logic, it is necessary to have a functionally complete logical basis and a memory element with a functionally complete system of transitions, states, and outputs. [10] The study of these issues is focused on in this paper. 3 Choosing a logical basis The total number of N logic functions in three-valued r logic is: N  33 where r is the argument of a logical function. The properties of many logical functions of multi-valued logics are still not well understood, but at the moment, among the many logical functions of each k-valued logic, two can be distinguished, which, together with the constants 0, 1, 2, ..., k-1, create two universal logical bases. These logical functions, as well as the devices that implement them (logic elements), are called forward and reverse multiplexers. The forward multiplexer (Помилка! Джерело посилання не знайдено., left) function has the form: 180  x1 if x0  0   x if x0  1 M xk0 ( x1 , x2 ,..., xk )   2 ..........................  xk if x0  k -1 The reverse multiplexer (Fig. 1, right) function  xk isifwritten x0  as0 follows:  k x if x0  1 M x0 ( xk , xk 1 ,..., x1 )   k 1  ..........................  x1 if x0  k -1 Fig. 1. Forward and reverse multiplexers. A multiplexer with one control signal will be called an elementary multiplexer. Mul-  k -1areifcalled tiplexers with two or more control signals x complex. 0 In addition to this logical  x 1  k - 2 -ifinversion: basis, we introduce another logical function X  ........................ 0 if x  k -1 The corresponding logical element is shown in Fig. 2. 181 Fig. 2. Multi-valued inverter The functional completeness of the basis can be brought indirectly by obtaining struc- tural diagrams for arbitrary logical functions of the three-valued logic. The table of functioning of the three-valued logical function of one argument is given in Table 1. Table 1. Three-valued logical function of one argument x 0 1 2 f(x) 0 2 1 The rule of functioning of the three-valued logical function of two arguments is pre- sented in Table 2. Table 2. Three-valued logical function of two arguments x0 0 1 2 0 1 2 0 1 2 x1 0 0 0 1 1 1 2 2 2 f(x0,x1) 2 1 0 0 1 2 1 0 2 Structural diagrams of the three-valued logical function of one and two arguments are shown in Fig. 3, left and right, respectively. Fig. 3. Three-valued logical function of one and two arguments 182 Similarly, block diagrams using a reverse multiplexer can be obtained. Thus, any log- ical function of multi-valued logic can be represented by a multi-tiered tree structure in which the basic element is an elementary k-valued multiplexer. k The following equalities holdMfor x (0, 0,..., any 0)  0 multi-valued logic and can be used to simplify structural diagrams: M (1,1,...,1)  1 k x ............................ M xk (0,1, 2,..., k  1)  x M xk (k  1, k  2,...,1, 0)  x Consider an example of the synthesis of the structural diagram of the three-valued adder, the rule of operation of which is given in Table 3 and obtained on the basis of obvious three-valued expressions: 0+0=0 0+1=1 0+2=2 1+1=2 1 + 2 = 10 2 + 2 = 11 0 + 1 + 2 = 10 1 +1 + 1 = 10 0 + 2 + 2 = 11 1 + 2 + 2 = 12 2 + 2 + 2 = 20 Table 3. The table of functioning of the three-valued adder bi 012 012 012 012 012 012 012 012 012 ai 000 111 222 000 111 222 000 111 222 Pi-1 000 000 000 111 111 111 222 222 222 Si 012 120 201 120 201 012 201 012 120 Pi 000 001 011 001 011 111 011 111 112 where ai, bi are the symbols that make up i-th digit of the three-valued numbers; Pi-1 is transfer from the previous digit; Si is the sum of numbers of the i-th digit; Pi is transfer to the next (senior) digit. Table 3 allows you to get a block diagram of the full three-valued adder on elementary multiplexers, consisting of a node for realizing the sum of Si (Fig. 4) and the transfer signal Pi (Fig. 5). As for the case of binary logic, complex multiplexers with several control signals can be used to construct the structural diagrams of the logical functions of multi-valued logic. It is easy to show that complex multiplexers also have functional completeness. They can be used to reduce the number of levels in the structural diagram of a device designed to form a model for presenting information on various indicators. 183 Fig. 4. Node for realizing the sum of the full three-valued adder on elementary multiplexers Fig. 5. Node for realizing the transfer signal of the full three-valued adder on elementary multi- plexers 4 Implementation of logic elements with memory in a multiplexer basis By a memory element is meant an elementary storage element that is capable of stor- ing one bit of a multi-valued code. For k-valued logic, such an element must remember one of the values 0, 1, 2, ..., k-1. Such elements are a trigger circuit of a static or dynamic 184 type. In modern calculators, the static storage mechanism is most often used. A trigger as a memory element must have a certain minimum set of properties that allow it to obtain its functioning table and block diagram [5]. These properties are: storage of the previously set value of the input signal, setting the value 0, setting the value 1, setting the value k-1. For example, a ternary trigger must have the following properties: storage of the previously set value of the input signal, setting value 0, setting value 1, setting value 2. In any multi-valued logic, such properties have a one-bit shift register [5]. The transition table (or graph) is easy to obtain using "window"-technology. For this, the register is conventionally represented as a single “window” through which in the gen- eral case a random sequence of k-digit signals alternately passes. The signal value in the "window" determines the state of the register. The number of states is N=k corre- sponds to the number of values of the used logical function. At each next moment of time, the next signal of the sequence enters the window and replaces (displaces) the previous signal, thereby changing the state of the "window". If the same signal arrives that was in the “window”, the state of the “window” does not change. For three-valued logic, the transition graph has the form shown in Fig. 6 (left - if there is a clock signal; right - in the absence of a clock signal). A circuit that implements the transition graph will perform the function of a D-trigger. Using the same principle, you can get a k-valued register graph. Given that the transi- tions of the register triggers occur in the presence of a synchronizing signal C the table of the D-trigger functioning will take the form shown in Table 4. Table 4. The functioning table of the three-valued D-trigger Q 012 012 012 012 012 012 012 012 012 D 000 111 222 000 111 222 000 111 222 C 000 000 000 111 111 111 222 222 222 Q 012 012 012 000 111 222 --- --- --- ¬Q 210 210 210 222 111 000 --- --- --- In Table 4, the symbol “-” indicates values that can be arbitrarily selected. According to the Table 4 block diagram of the three-valued D-trigger will look as shown in Fig. 7. All structural schemes are based on a universal logic element, which is a multiplexer. The table shows that all the necessary properties of the trigger as a memory element are satisfied. To build block diagrams in k-valued logic, you can now apply the classical technique developed for binary logic. As an example, we show the implementation of the structural diagram of the Mealy machine in three-valued logic, which, from the sequence of input signals X = 0, 1, 2, detects a combination of 1220 and sends the output signal y = 1. Otherwise, the machine sends a signal to the output y = 0. The graph of such a finite state machine is shown in Fig. 8, and Table 5 contains a table of its transitions. If the input of the machine, which is in the 3rd state, receives the next input signal equal to 0, then it returns to its original zero state. To implement the structural diagram of this finite state machine, two D- 185 triggers are required, the states of which are denoted by Q1 and Q2. We encode the state of the machine in the form given in Table 6. Fig. 6. Transition graph of a three-valued shift register Fig. 7. Structural diagram of the three-valued D-trigger Fig. 8. The graph of a state machine that recognizes a combination of 1220 Table 5. Transition table of a state machine that recognizes a combination of 1220 input state 0 1 2 3 0 0 0 0 0 1 1 1 1 1 2 0 2 3 0 186 Table 6. Table of the machine state encoding state of the machine 0 1 2 3 trigger Q1 0 0 0 1 state Q2 1 1 1 1 With the selected option of encoding states, we obtain an encoded table of transitions and outputs presented in Table 7. Table 7. Encoded transition table of a state machine that recognizes a combination of 1220 Q'2 012 012 012 012 012 012 012 012 012 Q'1 000 111 222 000 111 222 000 111 222 x 000 000 000 111 111 111 222 222 222 Q1 000 0-- --- 000 0-- --- 001 0-- --- Q2 000 0-- --- 111 1-- --- 020 0-- --- y 000 0-- --- 000 0-- --- 000 1-- --- Q1 000 0-- --- 000 0-- --- 001 0-- --- Q2 000 0-- --- 111 1-- --- 020 0-- --- The table corresponds to the structural diagram of a given machine, which consists of three parts: to determine the value of the first digit (Fig. 9), the second (Fig. 10, left) and the third (Fig. 10, right) digit of the state code. Fig. 9. Structural scheme of the machine for determining the value of the first digit Fig. 10. Structural scheme of the machine for determining the values of the second and third digits 187 Conclusions The possibility of using direct and reverse multiplexer circuits as a logical basis for constructing in three-valued logic structural diagrams of digital devices without memory and with memory of any complexity is shown. As an example of using a mul- tiplexer to implement 3-valued logic, a structural synthesis of a finite state machine is given, which, from a sequence of input signals, detects a given combination and gener- ates an output control signal. Using the proposed method for constructing block dia- grams of digital devices based on k-valued logic, it will be possible to create control signal conditioners for constructing various models of discrete-analog representation of data on semiconductor indicators. This will increase the capacity, processing speed and display of large amounts of information while reducing hardware and energy costs for their technical implementation. References 1. Vladimirova, Yu.: Introduction to Ternary Computer Science. Moscow, Argamak-media (2015). 2. Wakerly, J.: Digital Design: Principles and Practices. 6rd ed. Hoboken, Pearson Education Inc (2018). 3. Knut, D.: The Art of Programming, 3rd edn. vol. 2. Boston, Addison-Wesley (1997). 4. Vladmirova, Yu., Alvarez, R.: On the occasion of the 60th anniversary of the Setun com- puter. In: X International Scientific Conference named after A. I. Kitov “Information Tech- nologies and Mathematical Methods in Economics and Management” (IT&MM-2019), pp. 144-150. Moscow (2019). 5. Drobik, O., Lobanov, L., Yaskevich, V.: Building digital diagram on multiplexers. Komp'yuterno-intehrovani tekhnolohiyi: osvita, nauka, vyrobnytstvo 8, 16-21. (2012). 6. Ivanko, M., Gasovich, A.: Trinity computers: historical and educational aspects of the study of computer architecture. In: Vestnik MGUP Ivana Fyodorova 1, pp. 42-45. Moscow (2016). 7. Das, S., Sain, J., Dasgupta, P., Sensarma S. Arithmetic Algorithms for Ternary Number System. Procedia Technology 4, 278-285, Elsevier (2012). 8. Lin, S., Kim, Y., Lombardi, B.: CNTFET-Based Design of Ternary Logic Gates and Arith- metic Circuits. IEEE Transactions on Nanotechnology 10(2). 217-225 (2011). 9. Tabrizchi, S., Azimi, N., Navi, K.: A novel ternary half adder and multiplier based on carbon nanotube field effect transistors. Information Technology & Electronic Engineering 18. 423–433 (2017). 10. Mendelson, E.: Introduction to Mathematical Logic. 6th edn. Chapman and Hall (2015).