# Function Synthesis Algorithm of RTD-Based Universal Threshold Logic Gate

Authors: Maoqun Yao; Kai Yang; Congyuan Xu; Jizhong Shen
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

The resonant tunneling device (RTD) has attracted much attention because of its unique negative differential resistance characteristic and its functional versatility and is more suitable for implementing the threshold logic gate. The universal logic gate has become an important unit circuit of digital circuit design because of its powerful logic function, while the threshold logic gate is a suitable unit to design the universal logic gate, but the function synthesis algorithm for then-variable logical function implemented by the RTD-based universal logic gate (UTLG) is relatively deficient. In this paper, three-variable threshold functions are divided into four categories; based on the Reed-Muller expansion, two categories of these are analyzed, and a new decomposition algorithm of the three-variable nonthreshold functions is proposed. The proposed algorithm is simple and the decomposition results can be obtained by looking up the decomposition table. Then, based on the Reed-Muller algebraic system, the arbitrary n-variable function can be decomposed into three-variable functions, and a function synthesis algorithm for the n-variable logical function implemented by UTLG and XOR2 is proposed, which is a simple programmable implementation.


---

## Body

## 1. Introduction

With the improvement in integrated circuit integration, the complementary metal oxide semiconductor (CMOS) technology is gradually approaching its physical limitations. The resonant tunneling device (RTD) has better performance and features, such as negative differential resistance characteristic, self-latching, high speed, and functional versatility [1, 2]. The universal logic gate, which has a powerful logic function, has become an important unit to implement n-variable logical functions [3], and the RTD is more suitable for implementing the universal logic gate because of its negative differential resistance characteristic [4–6]. So, the RTD will probably become the main electronic device in the next generation of integrated circuits [7, 8].Though the circuit of ann-variable logical function implemented by the universal logic gate will be simpler, a different universal logic gate requires its corresponding synthesis algorithm to implement a function. Some function synthesis algorithms have been proposed in the literature [9–12], but these algorithms are not suitable for implementing an arbitrary n-variable function by the RTD-based universal threshold logic gate (UTLG) [13]. And the algorithm [14] which can implement a three-variable nonthreshold function by UTLGs is relatively complicated, and the implemented circuit structure is also complicated.In this paper, based on the Reed-Muller expansion, the three-variable nonthreshold functions are classified. Two categories of these are analyzed, and a new decomposition algorithm of the three-variable nonthreshold functions is proposed. Then a function synthesis algorithm which can implement an arbitraryn-variable logical function by UTLGs is proposed. The proposed function synthesis algorithm provides a new scheme for designing integrated circuits by RTD devices.


## 2. Background

### 2.1. Threshold Logic

A threshold logic gate is defined as a logic gate withn binary input variables and a single binary output. Its internal parameters are as follows: n binary input variables, x
i  i
=
1,2
,
…
,
n, a set of integer weights, w
i  i
=
1,2
,
…
,
n, and a threshold T and an output f, such that its input-output relationship can be expressed as [15](1)
f
=
1
,
if
∑
i
=
1
n
w
i
x
i
≥
T
0
,
otherwise.Formula (1) can also be presented as f
=
w
1
x
1
+
⋯
+
w
n
x
n
T. If a logic function can be implemented with a single threshold logic gate, the function is called a threshold function; otherwise, it is called a nonthreshold function [15].


### 2.2. Spectral Technique

Spectral technique is a mathematical transformation method. It can convert binary data from the Boolean domain into the spectral domain by matrix transformations, and the information will not be lost [16]. In the spectral domain {
-
1
,
+
1
}, for an n-variable logical function f
(
x
1
,
…
,
x
n
), its input and output have 2
n kinds of states, and the truth vector is(2)
Y
=
f
+
1
,
+
1
,
…
,
+
1
·
f
+
1
,
+
1
,
…
,
-
1
⋯
f
-
1
,
-
1
,
…
,
-
1
T
.The spectral-coefficient vectorR is given by(3)
R
=
r
0
r
1
⋯
r
n
r
12
⋯
r
1
,
…
,
n
T
=
T
n
·
Y
,where T
n is a 2
n
×
n Rademacher-Walsh matrix.As for a three-variable function, the spectral-coefficient vector isR
=
r
0
r
3
r
2
r
23
r
1
r
13
r
12
r
123
T, where r
0 is a zero-order spectral-coefficient, and r
i, r
i
j, and r
i
j
k are one-order, two-order, and three-order spectral coefficients, respectively.


### 2.3. Reed-Muller Expansion

A Reed-Muller expansion is a standard expansion in the AND/XOR algebraic system. A given function can be expressed as the XOR of basic entry; its coefficient is called the RM expansion coefficient [17]. Given an n-variable function f
(
x
1
,
…
,
x
n
), its RM expansion coefficient vector B (0-polarity; in this paper we only use 0-polarity expansion coefficient) is(4)
B
=
T
⊗
n
·
F
,where [
T
]
⊗
n
=
T
⊗
T
⊗
⋯
⊗
[
T
]
︸
n, [
T
]
=
1
0
1
1, ⊗ is the Kronecker product, and F is the truth vector of the function in the Boolean domain. As for a three-variable function f
(
x
1
,
x
2
,
x
3
), its RM expansion is(5)
f
x
1
,
x
2
,
x
3
=
b
0
⊕
b
1
x
3
⊕
b
2
x
2
⊕
b
3
x
2
x
3
⊕
b
4
x
1
⊕
b
5
x
1
x
3
⊕
b
6
x
1
x
2
⊕
b
7
x
1
x
2
x
3
.


## 2.1. Threshold Logic

A threshold logic gate is defined as a logic gate withn binary input variables and a single binary output. Its internal parameters are as follows: n binary input variables, x
i  i
=
1,2
,
…
,
n, a set of integer weights, w
i  i
=
1,2
,
…
,
n, and a threshold T and an output f, such that its input-output relationship can be expressed as [15](1)
f
=
1
,
if
∑
i
=
1
n
w
i
x
i
≥
T
0
,
otherwise.Formula (1) can also be presented as f
=
w
1
x
1
+
⋯
+
w
n
x
n
T. If a logic function can be implemented with a single threshold logic gate, the function is called a threshold function; otherwise, it is called a nonthreshold function [15].


## 2.2. Spectral Technique

Spectral technique is a mathematical transformation method. It can convert binary data from the Boolean domain into the spectral domain by matrix transformations, and the information will not be lost [16]. In the spectral domain {
-
1
,
+
1
}, for an n-variable logical function f
(
x
1
,
…
,
x
n
), its input and output have 2
n kinds of states, and the truth vector is(2)
Y
=
f
+
1
,
+
1
,
…
,
+
1
·
f
+
1
,
+
1
,
…
,
-
1
⋯
f
-
1
,
-
1
,
…
,
-
1
T
.The spectral-coefficient vectorR is given by(3)
R
=
r
0
r
1
⋯
r
n
r
12
⋯
r
1
,
…
,
n
T
=
T
n
·
Y
,where T
n is a 2
n
×
n Rademacher-Walsh matrix.As for a three-variable function, the spectral-coefficient vector isR
=
r
0
r
3
r
2
r
23
r
1
r
13
r
12
r
123
T, where r
0 is a zero-order spectral-coefficient, and r
i, r
i
j, and r
i
j
k are one-order, two-order, and three-order spectral coefficients, respectively.


## 2.3. Reed-Muller Expansion

A Reed-Muller expansion is a standard expansion in the AND/XOR algebraic system. A given function can be expressed as the XOR of basic entry; its coefficient is called the RM expansion coefficient [17]. Given an n-variable function f
(
x
1
,
…
,
x
n
), its RM expansion coefficient vector B (0-polarity; in this paper we only use 0-polarity expansion coefficient) is(4)
B
=
T
⊗
n
·
F
,where [
T
]
⊗
n
=
T
⊗
T
⊗
⋯
⊗
[
T
]
︸
n, [
T
]
=
1
0
1
1, ⊗ is the Kronecker product, and F is the truth vector of the function in the Boolean domain. As for a three-variable function f
(
x
1
,
x
2
,
x
3
), its RM expansion is(5)
f
x
1
,
x
2
,
x
3
=
b
0
⊕
b
1
x
3
⊕
b
2
x
2
⊕
b
3
x
2
x
3
⊕
b
4
x
1
⊕
b
5
x
1
x
3
⊕
b
6
x
1
x
2
⊕
b
7
x
1
x
2
x
3
.


## 3. Decomposition Algorithm of Three-Variable Nonthreshold Functions

In this section, the three-variable nonthreshold functions are classified, and a new decomposition algorithm of the three-variable nonthreshold functions is proposed.


### 3.1. Determine the Three-Variable Threshold Function

The zero-order and one-order spectral-coefficient can determine whether a function is a threshold function [16]. The spectral-coefficient classification table of all the three-variable threshold functions is given in Table 1, and some conclusions as follows [16].Table 1
Spectral-coefficientr
i classification of all the three-variable threshold functions.
n
r
i
a
i
n
=
3
8
0
0
0
1
0
0
0
6
2
2
2
2
1
1
1
4
4
4
0
1
1
1
0(1) The zero-order and one-order spectral-coefficients of the given function are calculated and arranged in numerically descending magnitude order, and this is ther
i of the function; if the r
i appear in Table 1, the function is a threshold function. The threshold value of a threshold function and weights can be obtained by a
i in Table 1. The relationship between the w
i and listed a
i value is (6)
w
i
=
a
i
i
=
1,2
,
3
.The sign ofw
i is the same as r
i. The threshold T can be calculated as(7)
T
=
1
2
∑
i
=
0
3
a
i
+
1
.(2) If the function is not a threshold function, the derived numberr
i will not appear in Table 1.


### 3.2. New Decomposition Algorithm of Three-Variable Nonthreshold Functions

According to the properties of the spectral coefficient, the three-variable nonthreshold function can be decomposed into three-variable threshold functions by a series of conversions [14], but for some three-variable nonthreshold functions, this algorithm [14] is relatively complex. So, we will propose a simpler algorithm which can decompose those three-variable nonthreshold functions into three-variable threshold functions.For all the three-variable functions, there are 104 threshold functions and 152 nonthreshold functions [16].First, according to Table1, the 104 threshold functions are divided into three categories [16].(1)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there is one number equal to 8 and three numbers equal to 0.
(2)
Among the absolute values of all the zero- and one-order spectral-coefficients, there is one number equal to 6 and three numbers equal to 2.
(3)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there is one number equal to 0 and three numbers equal to 4.Then, the 152 nonthreshold functions can be divided into four categories.(1)
Among the absolute values of all the spectral coefficients, the maximum number is from the two-order spectral coefficient.
(2)
Among the absolute values of all the spectral coefficients, the maximum number is from the three-order spectral coefficient.
(3)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there is one number equal to 4.
(4)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there are two numbers equal to 4.The numbers of these four categories of three-variable nonthreshold functions are 54, 18, 33, and 47, respectively. If the function belongs to the second and third categories of the three-variable nonthreshold functions, the algorithm [14] which decomposes the function will be relatively complex. A nonthreshold function is decomposed into the threshold function by the conversion of f
x
⊕
x
i and x
i
↔
x
i
⊕
x
j, so we propose a new decomposition algorithm of the three-variable nonthreshold functions based on the Reed-Muller algebraic system, and the decomposition process is as follows.(1)
The RM expansion coefficient vectors of all the three-variable threshold functions are calculated as a reference table.
(2)
The RM expansion coefficient vector of the given function is calculated.
(3)
Search the reference table and find two threshold functions in which the XOR result of their RM expansion coefficient vectors just equals the calculated RM expansion coefficient vector in step 2.
(4)
The three-variable nonthreshold function can be expressed as the XOR of the found threshold functions of step 3.After applying the process to the second and third categories of the three-variable nonthreshold functions, except two special functions,f
=
x
1
⊕
x
2
⊕
x
3 and f
=
x
1
⊕
x
2
⊕
x
3
¯, the others can be presented by the XOR of two threshold functions; that is, f
(
x
1
,
x
2
,
x
3
)
=
f
1
(
x
1
,
x
2
,
x
3
)
⊕
f
2
(
x
1
,
x
2
,
x
3
), where f
1 and f
2 are threshold functions. The decomposition results of the second and third categories of the three-variable nonthreshold functions are shown in Tables 2 and 3. In the tables, each vector of the columns is the output of the three-variable function for an 8-input combination from 000 to 111. Taking the first column of the first vector (
0
0
0
1
0
1
1
0
) as an example in Table 2, it expresses the three-variable function f
=
∑
m
i  (
i
=
3,4
), where m
i is the minterm of the function, and f can be expressed as f
=
f
1
⊕
f
2, where f
1
=
∑
m
i  (
i
=
3,4
,
5,6
,
7
) and f
2
=
∑
m
i  (
i
=
5,6
,
7
), and they are the three-variable threshold functions denoted by the second and third columns of the first row in Table 2.Table 2
The second category of the three-variable nonthreshold functions.
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
0
1
0
1
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
1
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
1
1
1
0
1
0
0
0Table 3
The third category of the three-variable nonthreshold functions.
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
0
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
0
1
0
0
1
1
0
1
1
0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
0
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
0
1
0
0
0
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
1
0
0
1
0
1
0
0
1
1
0
1
0
1
0
1
0
0
1
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
1
1
1
0
0
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
1
0
1
1
0
0
0
0
1
0
1
1
1
0
1
0
1
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
1
0
1
0
1
0
1
1
1
0
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
1
1
0
0
0
1
1
1
1
1
0
0
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0


## 3.1. Determine the Three-Variable Threshold Function

The zero-order and one-order spectral-coefficient can determine whether a function is a threshold function [16]. The spectral-coefficient classification table of all the three-variable threshold functions is given in Table 1, and some conclusions as follows [16].Table 1
Spectral-coefficientr
i classification of all the three-variable threshold functions.
n
r
i
a
i
n
=
3
8
0
0
0
1
0
0
0
6
2
2
2
2
1
1
1
4
4
4
0
1
1
1
0(1) The zero-order and one-order spectral-coefficients of the given function are calculated and arranged in numerically descending magnitude order, and this is ther
i of the function; if the r
i appear in Table 1, the function is a threshold function. The threshold value of a threshold function and weights can be obtained by a
i in Table 1. The relationship between the w
i and listed a
i value is (6)
w
i
=
a
i
i
=
1,2
,
3
.The sign ofw
i is the same as r
i. The threshold T can be calculated as(7)
T
=
1
2
∑
i
=
0
3
a
i
+
1
.(2) If the function is not a threshold function, the derived numberr
i will not appear in Table 1.


## 3.2. New Decomposition Algorithm of Three-Variable Nonthreshold Functions

According to the properties of the spectral coefficient, the three-variable nonthreshold function can be decomposed into three-variable threshold functions by a series of conversions [14], but for some three-variable nonthreshold functions, this algorithm [14] is relatively complex. So, we will propose a simpler algorithm which can decompose those three-variable nonthreshold functions into three-variable threshold functions.For all the three-variable functions, there are 104 threshold functions and 152 nonthreshold functions [16].First, according to Table1, the 104 threshold functions are divided into three categories [16].(1)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there is one number equal to 8 and three numbers equal to 0.
(2)
Among the absolute values of all the zero- and one-order spectral-coefficients, there is one number equal to 6 and three numbers equal to 2.
(3)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there is one number equal to 0 and three numbers equal to 4.Then, the 152 nonthreshold functions can be divided into four categories.(1)
Among the absolute values of all the spectral coefficients, the maximum number is from the two-order spectral coefficient.
(2)
Among the absolute values of all the spectral coefficients, the maximum number is from the three-order spectral coefficient.
(3)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there is one number equal to 4.
(4)
Among the absolute values of all the zero-order and one-order spectral-coefficients, there are two numbers equal to 4.The numbers of these four categories of three-variable nonthreshold functions are 54, 18, 33, and 47, respectively. If the function belongs to the second and third categories of the three-variable nonthreshold functions, the algorithm [14] which decomposes the function will be relatively complex. A nonthreshold function is decomposed into the threshold function by the conversion of f
x
⊕
x
i and x
i
↔
x
i
⊕
x
j, so we propose a new decomposition algorithm of the three-variable nonthreshold functions based on the Reed-Muller algebraic system, and the decomposition process is as follows.(1)
The RM expansion coefficient vectors of all the three-variable threshold functions are calculated as a reference table.
(2)
The RM expansion coefficient vector of the given function is calculated.
(3)
Search the reference table and find two threshold functions in which the XOR result of their RM expansion coefficient vectors just equals the calculated RM expansion coefficient vector in step 2.
(4)
The three-variable nonthreshold function can be expressed as the XOR of the found threshold functions of step 3.After applying the process to the second and third categories of the three-variable nonthreshold functions, except two special functions,f
=
x
1
⊕
x
2
⊕
x
3 and f
=
x
1
⊕
x
2
⊕
x
3
¯, the others can be presented by the XOR of two threshold functions; that is, f
(
x
1
,
x
2
,
x
3
)
=
f
1
(
x
1
,
x
2
,
x
3
)
⊕
f
2
(
x
1
,
x
2
,
x
3
), where f
1 and f
2 are threshold functions. The decomposition results of the second and third categories of the three-variable nonthreshold functions are shown in Tables 2 and 3. In the tables, each vector of the columns is the output of the three-variable function for an 8-input combination from 000 to 111. Taking the first column of the first vector (
0
0
0
1
0
1
1
0
) as an example in Table 2, it expresses the three-variable function f
=
∑
m
i  (
i
=
3,4
), where m
i is the minterm of the function, and f can be expressed as f
=
f
1
⊕
f
2, where f
1
=
∑
m
i  (
i
=
3,4
,
5,6
,
7
) and f
2
=
∑
m
i  (
i
=
5,6
,
7
), and they are the three-variable threshold functions denoted by the second and third columns of the first row in Table 2.Table 2
The second category of the three-variable nonthreshold functions.
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
0
1
0
1
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
1
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
1
1
1
1
0
1
0
0
0Table 3
The third category of the three-variable nonthreshold functions.
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
f
=
∑
m
i
f
1
=
∑
m
i
f
2
=
∑
m
i
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
0
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
0
1
0
0
1
1
0
1
1
0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
0
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
0
1
0
0
0
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
1
0
0
1
0
1
0
0
1
1
0
1
0
1
0
1
0
0
1
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
1
1
1
0
0
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
1
0
1
1
0
0
0
0
1
0
1
1
1
0
1
0
1
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
1
0
1
0
1
0
1
1
1
0
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
1
1
0
0
0
1
1
1
1
1
0
0
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0


## 4. The Synthesis Algorithm ofn-Variable Function Based on UTLG

The literature [13] proposed an RTD-based universal logic gate (UTLG) which can implement an arbitrary three-variable threshold function with a single UTLG. Figure 1 shows the schematic and symbol of UTLG; its input-output relationship can be expressed as(8)
f
=
1
,
2
c
1
+
c
2
+
c
3
-
2
c
4
-
c
5
-
c
6
≥
1
0
,
otherwise.Figure 1
The universal threshold logic gate (UTLG), (a) schematic (b) symbol.
(a)
(b)The first and fourth categories of the three-variable nonthreshold functions can be implemented by 3 UTLGs, and the second and third categories of the three-variable nonthreshold functions can be implemented by 7 UTLGs [13]. In our proposed decomposition algorithm of three-variable nonthreshold functions we introduced a bivariate XOR function, which cannot be implemented by a single UTLG, so according to the structure of MOBILE circuit [18], we design an RTD-based bivariate XOR gate (XOR2). Figure 2 shows the schematic and symbol of XOR2. Thus, the second and third categories of the three-variable nonthreshold functions can be implemented by 2 UTLGs and 1 XOR2, and it simplifies the circuit. Figure 3 shows the simulation results of XOR2 circuit by HSPICE; the parameters of RTD and HFET are the same as UTLG circuit [13], and as observed from Figure 3, the proposed XOR2 has the correct logic functionality.Figure 2
The bivariate XOR gate (XOR2), (a) schematic (b) symbol.
(a)
(b)Figure 3
Transient waveforms of the proposed XOR2.Currently, there is no algorithm which can implement arbitraryn-variable functions by the UTLG. Therefore, we proposed an n-variable function synthesis algorithm based on UTLG.First, we analyze the RM expansion of a four-variable functionf
x
1
,
x
2
,
x
3
,
x
4 [17]; f
=
b
0
⊕
b
1
x
4
⊕
b
2
x
3
⊕
b
3
x
3
x
4
⊕
b
4
x
2
⊕
b
5
x
2
x
4
⊕
b
6
x
2
x
3
⊕
b
7
x
2
x
3
x
4
⊕
b
8
x
1
⊕
b
9
x
1
x
4
⊕
b
10
x
1
x
3
⊕
b
11
x
1
x
3
x
4 ⊕ b
12
x
1
x
2
⊕
b
13
x
1
x
2
x
4
⊕
b
14
x
1
x
2
x
3
⊕
b
15
x
1
x
2
x
3
x
4.By observation, the last eight terms of the RM expansion are equal to the first eight terms of the RM expansion by multiplyingx
1, respectively, and the operations of terms in the RM expansion function are XOR, so the four-variable function can be expressed as f
=
f
11
⊕
x
1
f
12, the variables of f
11 are x
2, x
3 and x
4, and the RM expansion coefficient vector of f
11 is equal to the first eight elements of the RM expansion coefficient vector of f. The variables of f
12 are also x
2, x
3, and x
4, and the RM expansion coefficient vector of f
12 is equal to the last eight elements of the RM expansion coefficient vector of f.For ann-variable function, based on the Reed-Muller algebraic system [17], it can also be expressed as f
=
f
11
⊕
x
1
f
12, so we propose the synthesis algorithm of n-variable functions based on UTLG; its process is as follows.(1)
Calculate the RM expansion coefficient vectorB of the given n-variable function f.
(2)
In the first decomposition,f
=
f
11
⊕
x
1
f
12, the subfunction f
11 is the n
-
1 variable of the function except x
1, and its RM expansion coefficient vector B
1 is equal to the first n
/
2 elements of B; the subfunction f
12 is also the n
-
1 variable of the function except x
1, and its RM expansion coefficient vector B
2 is equal to the last n
/
2 elements of B.
(3)
In the second decomposition,f
11
=
f
21
⊕
x
2
f
22, f
12
=
f
23
⊕
x
2
f
24, the subfunctions f
21, f
22, f
23, and f
24 are the n
-
2 variables of functions except x
1 and x
2, and their RM expansion coefficient vectors are equal to the first n
-
1
/
2 elements of B
1, the last n
-
1
/
2 elements of B
1, the first n
-
1
/
2 elements of B
2, and the last n
-
1
/
2 elements of B
2, respectively.
(4)
Repeat step 3, until the subfunctions are the three-variable functions.
(5)
Judging all the three-variable subfunctions, if the function is a threshold function, it can directly be implemented by 1 UTLG; if the function belongs to the first and fourth categories of the three-variable nonthreshold functions, it can be implemented by 3 UTLGs [14]; if the function belongs to the second and third categories of the three-variable nonthreshold functions, looking up the decomposition results from Tables 2 and 3, it can be implemented by 2 UTLGs and 1 XOR2; if the function is f
=
x
1
⊕
x
2
⊕
x
3 or f
=
x
1
⊕
x
2
⊕
x
3
-, it can be implemented by 1 UTLG and 2 XOR2s.
(6)
Thex
i
+
1
f
(
i
+
1
)
l of each decomposition equation f
i
j
=
f
(
i
+
1
)
k
⊕
x
i
+
1
f
(
i
+
1
)
l can be regarded as the bivariate function, which can be implemented by 1 UTLG. And the bivariate XOR operation of the decomposition equations can be implemented by 1 XOR2.Example 1.
Implement the four-variable function:(9)
f
=
x
1
¯
x
3
¯
x
4
¯
+
x
2
¯
x
3
¯
x
4
¯
+
x
1
¯
x
2
x
3
¯
+
x
1
¯
x
2
x
4
¯
+
x
1
x
2
x
4
+
x
1
¯
x
2
¯
x
3
x
4
.
The RM expansion coefficient vectorB of f is B
=
1
1
1
0
0
1
1
1
0
0
0
1
1
1
0
0, the f can be decomposed as f
=
f
11
⊕
x
1
f
12, f
11 is a three-variable function, and its RM expansion coefficient vector B
1 is equal to the first 8 elements of B; that is, B
1
=
1
1
1
0
0
1
1
1, f
11
=
x
2
x
3
¯
+
x
2
x
4
¯
+
x
3
¯
x
4
¯
+
x
2
¯
x
3
x
4. f
12 is a three-variable function, and its RM expansion coefficient vector B
2 is equal to the last 8 elements of B; that is, B
2
=
0
0
0
1
1
1
0
0, f
12
=
x
2
x
4
¯
+
x
3
x
4.
f
11 belongs to the second category of the three-variable nonthreshold functions; looking up Table 2, f
11
=
f
11
′
⊕
f
12
′, f
11
′
=
x
3
+
x
4
2, f
12
′
=
2
x
2
-
x
3
-
x
4
0. f
12 belongs to the fourth category of the three-variable nonthreshold functions, and it can be decomposed as [14] f
12
=
f
21
′
+
f
22
′, f
21
′
=
x
2
x
4
¯, f
22
′
=
x
3
x
4. Then f can be implemented by 6 UTLGs and 2 XOR2s. Figure 4 shows the UTLG and XOR2 implementation of this function.Figure 4
UTLG and XOR2 implementation of Example1.Example 2.
Implement the five-variable function:(10)
f
=
x
1
x
2
x
3
¯
x
4
¯
x
5
+
x
1
x
2
¯
x
3
¯
x
4
x
5
¯
+
x
1
¯
x
3
¯
x
4
x
5
+
x
1
¯
x
2
x
3
¯
x
4
+
x
1
x
2
x
3
x
4
+
x
1
¯
x
3
x
4
¯
x
5
+
x
2
¯
x
3
x
4
¯
x
5
¯
+
x
1
¯
x
2
¯
x
3
.
The RM expansion coefficient vectorB of f is B
=
0
0
0
1
1
0
0
1
0
0
1
1
1
1
1
0
0
0
1
0
0
1
0
1
0
1
0
1
0
1
0
1, f can be decomposed as f
=
f
11
⊕
x
1
f
12, f
11 is a four-variable function, its RM expansion coefficient vector B
1 is equal to the first 16 elements of B, that is, B
1
=
0
0
0
1
1
0
0
1
0
0
1
1
1
1
1
0, f
12 is a four-variable function, and its RM expansion coefficient vector B
2 is equal to the last 16 elements of B, that is, B
2
=
0
0
1
0
0
1
0
1
0
1
0
1
0
1
0
1.
Continue to decomposef
11. f
11
=
f
21
⊕
x
2
f
22, f
21 is a three-variable function, its RM expansion coefficient vector B
3 is equal to the first 8 elements of B
1, that is, B
3
=
0
0
0
1
1
0
0
1, f
22 is also a three-variable function, and its RM expansion coefficient vector B
4 is equal to the last 8 elements of B
1, that is, B
4
=
0
0
1
1
1
1
1
0.
Continue to decomposef
12. f
12
=
f
23
⊕
x
2
f
24, f
23 is a three-variable function, its RM expansion coefficient vector B
5 is equal to the first 8 elements of B
2, that is, B
5
=
0
0
1
0
0
1
0
1, f
24 is a three-variable function, and its RM expansion coefficient vector B
6 is equal to the last 8 elements of B
2, that is, B
6
=
0
1
0
1
0
1
0
1.
f
21, f
22, f
23, and f
24 are the three-variable threshold functions, and f can be implemented by 7 UTLGs and 3 XOR2s. Figure 5 shows the UTLG and XOR2 implementation of this function.
The proposed synthesis algorithm of then-variable function based on UTLG can decompose the arbitrary n-variable function into three-variable functions, and all the three-variable nonthreshold functions are divided into four categories, and two categories of them can be implemented by UTLG and XOR2. Thus, arbitrary n-variable functions can be implemented by UTLG and XOR2, and if the given function is decomposed into the threshold functions, the circuit structure will be simple.
Up to now, there is no algorithm which can implement arbitraryn-variable function by UTLG. Reference [13] just proposed the algorithm which can implement arbitrary three-variable function. So, we provided new logic units UTLG and XOR2 and a new algorithm to implement RTD-based arbitrary n-variable function.Figure 5
UTLG and XOR2 implementation of Example2.


## 5. Conclusion

In this paper, the 152 three-variable nonthreshold functions are divided into four categories, and a new decomposition algorithm of the three-variable nonthreshold functions is proposed. If the function belongs to the second and third categories of the three-variable nonthreshold functions, it can be implemented by 2 UTLGs and 1 XOR2, and it simplifies the implemented circuit structure. Based on the Reed-Muller algebraic system, the arbitraryn-variable function can be decomposed into three-variable functions, and the function synthesis algorithm for the n-variable function which can be implemented by UTLG and XOR2 is proposed; that is, the arbitrary n-variable function can be implemented by UTLG and XOR2, and if the given function is decomposed into three-variable threshold functions, the circuit structure will be much simpler. The proposed logic units and algorithm present a new method to implement the arbitrary n-variable function by RTD-based devices.



---

*Source: 827572-2015-06-11.xml*