Three-valued Logic

List of accomplishments

• Basic ternary logic gates: T_NOT, T_OR, T_AND, T_NAND, T_NOR, T_XOR and more
• Synthesis, Minimization and Realization for Ternary Functions
• Ternary half adder, Ternary full adder, Ternary ripple carry adder
• Ternary full subtractor, comparator, multiplier, multiplexer/demultiplexer
• Ternary flip flap flops and latches
• A primitive Ternary Arithmetic and Logical Unit (ALU)

Conventions and used technologies

• Unbalanced Ternary (0, 1, 2) was used in implementation
• 1 Trit is expressed by 2 Bits: 0 ~ 00, 1 ~ 01, 2 ~10 (11 is undefined)
• ModelSim, Quartus prime, Logisim

Introduction

As first-year students of Innopolis University, we had the opportunity to realize projects throughout our computer architecture course. Our group was particularly interested in the ternary system and its functioning, so we decided to implement a simple ternary system with basic components (gates).

In logic, a three-valued logic (also trinary logic, trivalent, ternary) is one of several many-valued logic systems in which there are three truth values indicating true, false and some indeterminate third value.

Ternary logic is MVL (Multi-valued logic) compliant. However, only three logic states are used, ‘0‘,’1‘ and ‘2‘. The optimum radix (r) of a fractional number is found to be the natural logarithm (e). Ternary logic uses number representation with r=3, compared to binary logic which uses r=2, hence the most economical integer radix which is the closest to the natural logarithm e, is base 3. This special property of base 3 inspired the early computer designers to build a ternary computer.

The first working ternary computer was built in Russia at the Moscow State University in 1958. The computer was designed by Nikolay Brusentsov and his colleagues. They named it Setun, like the river that flows near the university campus.

Ternary Logic

A ternary logic function is a mapping F: {0,1,2}ⁿ -> {0,1,2}. We will discuss the advantages and disadvantages of ternary logic over binary logic.

Where Boolean logic has 2² = 4 unary operators, the addition of a third value in ternary logic leads to a total of 3³ = 27 distinct operators on a single input value. Similarly, where Boolean logic has 2²² = 16 distinct binary operators (operators with 2 inputs), ternary logic has 3³²= 19,683 such operators. Where we can easily name a significant fraction of the Boolean operators (not, and, or, nand, nor, exclusive or, equivalence, implication), it is unreasonable to attempt to name all but a small fraction of the possible ternary operators.

Advantages of Ternary Logic

A ternary logic representation enables a more compact and efficient information encoding than the equivalent binary logic representation. The argument stated is as follows: if we assume that a digital circuit has N possible input combinations, then a binary circuit requires log₂N input lines and a ternary circuit requires log₃N input lines.

Therefore, a ternary encoded realization of a given binary logic function should require 0.63 times the input lines than the corresponding binary realization.

Disadvantages of Ternary Logic

Although ternary logic circuits should require fewer input lines than the equivalent binary logic circuits, ternary logic circuits are currently not a practical choice. The reasons are

1. Ternary hardware implementation technology is still in the theoretical, simulation, and laboratory test levels
2. Representing three ternary logic levels (0, 1, and 2) using voltage levels of existing technology is not yet effectively defined
3. No computational model and programming language is developed. However, simulating results of ternary circuit implementation using complementary metal oxide semiconductor (CMOS), resonant tunneling diode (RTD), and carbon nano-tube technologies, demonstrating that ternary logic may be a choice for future computing.

Various possible representations for the ternary system

• Ternary numeral system (Unbalanced ternary), each digit is a trit (trinary digit) having a value of: 0, 1, or 2
• Balanced ternary, each digit has one of 3 values: −1, 0, or +1; these values may also be simplified to −, 0, +, respectively (most commonly used)
• Redundant binary representation, each digit can have a value of −1, 0, 0/1 (the value 0/1 has two different representations)
• Skew binary number system, only most-significant non-zero digit has a value 2, and the remaining digits have a value of 0 or 1

More about the balanced Ternary Numbering System

Today, mostly all hardware is designed for binary computing. If we had a stable electronic component with three stable states, the world perhaps would have turned to ternary computing. However, this is not the truth today. The balanced ternary radix notation has some beneficial properties:

1. Ternary inversion is easy, just exchange −1 with 1 and vice versa. If we use an example, 24 is represented as 1T0, and -24 as T10 in balanced ternary notation (T is simply a notation for -1). This is simpler than the rule for the two’s complement in binary logic.
2. The sign of a number is given by its most significant nonzero ’trit’
3. The operation of rounding to the nearest integer is identical to truncation.
4. Addition and subtraction are essentially the same operation (I.e. you merely add the digits using the rules for addition of digits)

Examples:
21₁₀ = 1T10₃; 296₁₀ = 11T00T₃;
-24₁₀ = T10₃; -137₁₀ = T110T1₃

Ternary Arithmetics

Ternary arithmetic can offer a more compact notation than binary arithmetic, and would have been an obvious choice if the hardware manufacturers would have found a ternary switch.

Balanced Ternary Addition and Multiplication

Examples:

Ternary combinational circuits (Ternary gates)

A combinational circuit consists of input variables, ternary logic gates and output variables. The output of the circuit depends only upon the present input. Logic gates accept signals from the input variables and generate output signals. This process transforms ternary information from
the given input data to the required ternary output data.

As mentioned above we can easily name a significant fraction of the Boolean operators (not, and, or, nand, nor, exclusive or, equivalence, implication), however, it is unreasonable to attempt to name all but a small fraction of the possible ternary operators. We will consider the following ternary circuits:

And (Min): It is natural to extend the Boolean and function to a ternary function by declaring that the result is true only if both inputs are true, false if any input is false, and unknown otherwise.

Or (Max): It is also natural to extend the Boolean or function to ternary by declaring that the result is true if any input is true, false only if both inputs are false, and unknown otherwise.

Consensus: In Boolean logic, the inverse of exclusive or is true when the two inputs are the same, and false when they are different. There are several natural extensions of this idea to ternary logic. One of them is the logical consensus of a set of variables, which is true if all are true, false if all are false, and otherwise unknown

Any: Where consensus requires that both inputs agree before it asserts anything but unknown, the accept anything operator declares an unknown conclusion only if both inputs are unknown or actively disagree. Otherwise, it jumps to a conclusion from any non-unknown input available to it.

Increment and Decrement: In Boolean logic, the inverter may be thought of as incrementing or decrementing its argument modulo 2. In ternary logic, the modulo 3 increment and decrement functions are quite distinct from inversion.

Synthesis, Minimization and Realization for Ternary Functions

Relationships interrelated in the ternary logic system

A ternary logic function can be represented as a Max-Min expression. Ternary Max-Min expressions are defined as follows:
Variable: Any symbol that takes value from the set T ∈ {0,1,2} is a ternary variable.
Literal: Literals are transformed forms of a variable. They are used to form Max-Min expressions.

In the literature two types of literals are commonly used: 1-reduced Post literals and 2-reduced post literals. A 1-reduced Post literal of a variable x is represented as x_i, where i ∈ {0,1,2}. When x = i, then x_i = 1, otherwise x_i = 0. The 1-reduced Post literals of a variable is shown below.

A 2-reduced Post literal of a variable x is represented as x_i, where i ∈ {0,1,2}. When x = i, then x_i = 2, otherwise x_i = 0. The 2-reduced Post literals of a variable is shown below. This example makes use of different sets of literals to form Max-Min expressions as discussed previously.

Minterm: When literals of variables of a function are combined using the Min operation, then the term is called a minterm. For example, for a 3-variable ternary logic function F(x,y,z), xyz and xz are two examples of minterms.

Max-Min Expression: When two or more minterms are combined using Max operations, then the expression is called a Max of minterms (Max-Min) expression. For example, for a 3-variable ternary logic function F(x,y,z) = xy + yz + xyz is an example of a Max-Min expression.

Any function F(x,y,z) can always be represented as

Three basic methods to minimize ternary functions are:

1. Manipulation of algebra expression as in Boolean algebra.
2. The tabular method.
3. Ternary K. map method.
   For the implementation of ternary circuits it is necessary to convert ternary variable into unary variable (using the 2-Reduced Post Literals table).

Ternary half adder

A circuit for the addition two 1 trit numbers is referred to as a half adder. the circuit does not consider a carry generated in the previous addition. The addition process in ternary logic system is shown below. Here A and B are two inputs and sum(S) and carry (CARRY)
are two outputs.

Analysis

A karnaugh map (K-map) is used to represent the sum and carry output. K-maps are useful for minimization and optimization of logic circuits. Here a K-map of 2 inputs is used. Since no grouping of 2’s and 1’is possible, the output equation is as below.

Implementation

module half_adder (     input [1:0] A, [1:0] B,     output [1:0] sum, [1:0] carry  );  wire [1:0] temp = 2'b01; wire [1:0] a0, a1, a2, b0, b1, b2; wire [1:0] i0, i1, i2, i3, i4, i5; wire [1:0] o0, o1, o2, o3, o4; wire [1:0] c0, c1, c2, c3;  mask msk_1(A, a0, a1, a2); mask msk_2(B, b0, b1, b2);  andgate and_1(a2,b0,i0); andgate and_2(a1,b1,i1); andgate and_3(a0,b2,i2); // partial products  orgate or_1(i0, i1, o0); orgate or_2(o0, i2, o1); // f1  andgate and_4(a1,b0,i3); andgate and_5(a0,b1,i4); andgate and_6(a2,b2,i5); // partial products  orgate or_3(i3, i4, o2); orgate or_4(o2, i5, o3); // f2 andgate and_7(o3,temp,o4); // 1.f2  andgate andc_0(a2,b1,c0); andgate andc_1(a1,b2,c1); orgate orc_0(c0,c1,c2); orgate orc_1(c2,i5,c3); andgate andc_2(c3,temp,carry); // carry orgate or_5(o1, o4, sum); // sum endmodule

Ternary full adder

As with half adders, one stage of a ternary full adder can be described by a numerical table giving the sum SUM and carry out CARRY as a function of the three inputs A, B, along with the carry in C:

Analysis

A karnaugh map (K-map) is used to represent the sum and carry output. K-maps are useful for minimization and optimization of logic circuits. Here a K-map of 3 inputs is used.

Implementation

module ternary_full_adder (     input [1:0] A, [1:0] B, [1:0] c_in,     output [1:0] sum, [1:0] c_out  ); wire [1:0] temp1 = 2'b01; wire [1:0] temp2 = 2'b00; wire [1:0] a0, a1, a2, b0, b1, b2, a20; wire [1:0] i0, i1, i2, i3, i4; wire [1:0] i5, i6, i7, i8, i9, i10, i11, i12, i13, i14, i15, i16, i17; wire [1:0] o0, o1, o2, o3, o4, o5, o6, o7, o8, o9; wire [1:0] c0, c1, c2; wire [1:0] h0, h1, h2, h3, h4, h5, h6, h7; wire [1:0] t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13, t14, t15, t16; wire [1:0] g0, g1, g2, g3, g4, g5, g6, g7, g8, g9, g10, g11, g12, g13, g14, g15;  mask mk_1(A, a0, a1, a2); mask mk_2(B, b0, b1, b2); mask mk_3(c_in, c0, c1, c2);  andgate3 and3_1(a2,b0,c0, i0); andgate3 and3_2(a1,b0,c1, i1); andgate3 and3_3(a0,b0,c2, i2); andgate3 and3_4(a1,b1,c0, i3); andgate3 and3_5(a0,b1,c1, i4); andgate3 and3_6(a2,b1,c2, i5); andgate3 and3_7(a0,b2,c0, i6); andgate3 and3_8(a2,b2,c1, i7); andgate3 and3_9(a1,b2,c2, i8);  andgate3 and3_10(a1,b0,c0, i9); andgate3 and3_11(a0,b0,c1, i10); orgate or__(a2, a0, a20); andgate3 and3_12(a20,b0,c2, i11); // note a20 andgate3 and3_13(a0,b1,c0, i12); andgate3 and3_14(a2,b1,c1, i13); andgate3 and3_15(a1,B,c2, i14); andgate3 and3_16(a2,b2,c0, i15); andgate3 and3_17(a1,b2,c1, i16); andgate3 and3_18(temp2,b2,c2, i17);  orgate or_1(i9, i10, o0); orgate or_2(o0, i11, o1); orgate or_3(o1, i12, o2); orgate or_4(o2, i13, o3); orgate or_5(o3, i14, o4); orgate or_6(o4, i15, o5); orgate or_7(o5, i16, o6); orgate or_8(o6, i17, o7);  andgate and_1(o7, temp1, o8); // 1.f2 orgate or_9(i0, i1, h0); orgate or_10(h0, i2, h1); orgate or_11(h1, i3, h2); orgate or_12(h2, i4, h3); orgate or_13(h3, i5, h4); orgate or_14(h4, i6, h5); orgate or_15(h5, i7, h6); orgate or_16(h6, i8, h7); orgate or_17_(h7, o8, sum); // sum // carry andgate3 and3_19(a2,b2,c2, t0); // f1 andgate3 and3_20(a0,b1,c2, t1); andgate3 and3_21(a0,b2,c2, t2); andgate3 and3_22(a0,b2,c1, t3); andgate3 and3_23(a1,b2,c0, t4); andgate3 and3_24(a2,b2,c0, t5); andgate3 and3_25(a1,b1,c1, t6); andgate3 and3_26(a1,b2,c1, t7);  andgate3 and3_27(a1,b0,c2, t8); andgate3 and3_28(a1,b1,c2, t9); andgate3 and3_29(a1,b2,c2, t10); andgate3 and3_25_(a2,b0,c2, t11); andgate3 and3_26_(a2,b1,c2, t12);  andgate3 and3_27_(a2,b0,c1, t13); andgate3 and3_28_(a2,b1,c1, t14); andgate3 and3_29_(a2,b2,c1, t15); andgate3 and3_9_(a2,b1,c0, t16); orgate or_17(t1, t2, g0); orgate or_18(g0, t3, g1); orgate or_19(g1, t4, g2); orgate or_20(g2, t5, g3); orgate or_21(g3, t6, g4); orgate or_22(g4, t7, g5); orgate or_23(g5, t8, g6); orgate or_24(g6, t9, g7); orgate or_25(g7, t10, g8); orgate or_21_(g8, t11, g9); orgate or_22_(g9, t12, g10); orgate or_23_(g10, t13, g11); orgate or_24_(g11, t14, g12); orgate or_25_(g12, t15, g13); orgate or_5_(g13, t16, g14); //f2 andgate and_2(g14, temp1, g15); // 1.f2 orgate or_26(g15, t0, c_out); // carry endmodule

Ternary Full Subtractor

Ternary full-Subtractor is a circuit that subtracts two inputs and previous borrow. Truth table for Subtractor is shown below

module full_subtractor(     input [1:0] P, Q, b_in,     output [1:0] diff, b_out );  wire [1:0] temp1 = 2'b01; wire [1:0] temp2 = 2'b10; wire [1:0] a0, a1, a2, b0, b1, b2; wire [1:0] i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i13, i14, i15, i16, i17; wire [1:0] c0, c1, c2, c3; wire [1:0] h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11; wire [1:0] t0, t1, t2, t3, t4, t5, t6, t7, t8, t9;  wire [1:0] p0, p1, p2; wire [1:0] q0, q1, q2;  mask mk_1(P, p0, p1, p2); mask mk_2(Q, q0, q1, q2); mask mk_3(b_in, b0, b1, b2);  andgate and_0(p0, q1, i0); andgate3 and3_0(p2, p1, q2, i1); orgate or_0(i0, i1, i2); andgate and_1(b0, i2, i3); // first expression  andgate and_2(p0, q0, i4); andgate and_3(p1, q1, i5); andgate and_4(p2, q2, i6); orgate or_1(i4, i5, i7); orgate or_2(i7, i6, i8); andgate and_5(i8, b1, i9); // second expression  andgate and_6(p1, q0, i10); andgate and_7(p0, q2, i11); andgate and_8(p2, q1, i12); orgate or_3(i10, i11, i13); orgate or_4(i13, i12, i14); andgate and_9(i14, b2, i15); // third expression  orgate or_5(i3, i9, i16); orgate or_6(i16, i15, c0); //f1  orgate or_7(i10, i12, t0); orgate or_8(t0, i11, t1); andgate and_10(t1, b0, t2); // 1 expression  andgate and_11(p1, q2, i17); orgate or_9(i4, i17, t3); andgate and_12(t3, b1, t4); // 1- expression  orgate or_10(i4, i5, t5); orgate or_11(t5, i6, t6); andgate and_12_(t6, b2, t7); // 1-- expression  orgate or_12(t2, t4, t8); orgate or_13(t8, t7, t9); andgate and_13(t9, temp1, c1);  orgate or_14(c0, c1, diff); // difference  orgate or_15(q1, q2, h0); andgate and_14(h0, temp2, h1); andgate and_15(h1, b2, h3); // 1 b  orgate or_16(i0, i11, h4); andgate and_16(h4, temp2, h5); // 1- b  andgate and_17(i17, temp2, h6); // 1-- b  andgate3 and3_1(p2, q2, b1, h7); // 1--- b andgate3 and3_2(p1, q0, b2, h8); // 1---- b  orgate or_17(h3, h5, h9); orgate or_18(h9, h6, h10); orgate or_19(h10, h7, h11); orgate or_20(h11, h8, b_out); // borrow endmodule

Ternary Ripple Carry Adder

Ripple-carry adder(RCA) is a well-known circuit for performing addition of two numbers by cascading ternary full adders. A Ternary RCA is quite similar to its Binary counterpart. A Ternary Half Adder is employed to add the least significant Ternary digits. The rest are summed up by Ternary Full Adders. As mentioned before, Ternary Full Adder adds three Ternary input variables.

Implementation

module ternary_ripple_adder (     input [15:0] input1 ,     input [15:0] input2 ,     output [15:0] out ,     output [1:0] overflow_trit );  wire [15:0] carry ; reg tem;  assign carry[0] = tem; assign carry[1] = tem;  always @(input1, input2) begin     tem <= 1'b0; end  generate   genvar i;   for (i = 0; i <= 12; i=i+2)     begin     full_add af({input1[i+1],input1[i]}, {input2[i+1],input2[i]},          {carry[i+1],carry[i]}, {out[i+1], out[i]}, {carry[i+3],carry[i+2]});     end     full_add af({input1[15],input1[14]}, {input2[15],input2[14]},      {carry[15],carry[14]}, {out[15], out[14]}, overflow_trit); endgenerate endmodule

Ternary Comparators

Ternary comparator circuit camper two inputs X₁, X₂ and accordingly generates output as X₁ = X₂, X₁ > X₂, X₁ < X₂. Truth table for a ternary comparator is shown below

module ternary_comparators (     input [1:0] x1, x2,     output [1:0] f1, f2, f3 ); wire [1:0] t0, t1, t2, t3, t4, t5, t6, t7; wire [1:0] h0, h1, h2, h3, h4, h5; wire [1:0] x10, x11, x12; wire [1:0] x20, x21, x22;  mask mk_1(x1, x10, x11, x12); mask mk_2(x2, x20, x21, x22);  andgate and_0(x10, x20, t0); andgate and_1(x22, x22, t1); orgate or_0(t0, t1, h0); orgate or_1(h0, x11, h1); orgate or_2(h1, x21, f1); // x1 == x2  andgate and_2(x11, x20, t2); andgate and_3(x12, x20, t3); andgate and_4(x12, x21, t4); orgate or_3(t2, t3, h3); orgate or_4(h3, t4, f2); // x1>x2  andgate and_5(x10, x21, t5); andgate and_6(x10, x22, t6); andgate and_7(x11, x22, t7); orgate or_5(t5, t6, h4); orgate or_6(h4, t7, f3); // x1

module ternary_multiplier (     input [1:0] A, [1:0] B,     output [1:0] product, [1:0] carry  );  wire [1:0] temp = 2'b01; wire [1:0] a0, a1, a2, b0, b1, b2; wire [1:0] i0, i1, i2, i3, i4, i5; wire [1:0] o0, o1, o2, o3, o4;  mask msk_1(A, a0, a1, a2); mask msk_2(B, b0, b1, b2);  andgate and_1(a1,b2,i0); andgate and_2(a2,b1,i1); orgate or_1(i0, i1, o0); // f1  andgate and_4(a1,b1,i3); andgate and_5(a2,b2,i4); orgate or_3(i3, i4, o2); andgate and_3(temp,o2,o3); orgate or_4(o3, o0, product); // product  andgate andc_0(a2,b2,o4); andgate andc_1(temp,o4,carry); // carry  endmodule