This paper presents an efficient graph-based evolutionary optimization technique called Evolutionary Graph Generation (EGG) and its extension to a parallel version. A new version of parallel EGG system is based on a coarse-grained model of parallel processing and can synthesize heterogeneous networks of various different components efficiently. The potential capability of parallel EGG system is demonstrated through the design of current-mode logic circuits.

A novel multiple-valued transfer gate (T-gate) consisting of multiple-junction surface tunnel transistors (MJSTTs) and hetero-junction FETs (HJFETs) was developed and its operation was confirmed by both simulation and experiment. The number of the devices required to form the T-gate can be drastically reduced because of the high functionality of the MJSTT; namely only three MJSTTs and three HJFETs are required to fabricate the three-valued T-gate. This number of transistors is less than half that of a conventional circuit. The fabricated circuit exhibited a basic T-gate operation with various logic functions. Furthermore, only one T-gate is needed to form a multiple-valued D-flip-flop (D-FF) circuit.

This letter presents an efficient graph-based evolutionary optimization technique, and its application to the transistor-level design of multiple-valued arithmetic circuits. The key idea is to introduce "circuit graphs with colored terminals" for modeling heterogeneous networks of various components. The potential of the proposed approach is demonstrated through experimental synthesis of a radix-4 signed-digit (SD) full adder circuit.

In this paper, we propose a method to minimize multiple-valued decision diagrams (MDDs) for multiple-output functions. We consider the following: (1) a heuristic for encoding the 2-valued inputs; and (2) a heuristic for ordering the multiple-valued input variables based on sampling, where each sample is a group of outputs. We first generate a 4-valued input 2-valued multiple-output function from the given 2-valued input 2-valued functions. Then, we construct an MDD for each sample and find a good variable ordering. Finally, we generate a variable ordering from the orderings of MDDs representing the samples, and minimize the entire MDDs. Experimental results show that the proposed method is much faster, and for many benchmark functions, it produces MDDs with fewer nodes than sifting. Especially, the proposed method generates much smaller MDDs in a short time for benchmark functions when several 2-valued input variables are grouped to form multiple-valued variables.

In this paper, we focus on regularity and set-valued functions. Regularity was first introduced by S. C. Kleene in the propositional operations of his ternary logic. Then, M. Mukaidono investigated some properties of ternary functions, which can be represented by regular operations. He called such ternary functions "regular ternary logic functions". Regular ternary logic functions are useful for representing and analyzing ambiguities such as transient states or initial states in binary logic circuits that Boolean functions cannot cope with. Furthermore, they are also applied to studies of fail-safe systems for binary logic circuits. In this paper, we will discuss an extension of regular ternary logic functions into r-valued set-valued functions, which are defined as mappings on a set of nonempty subsets of the r-valued set {0, 1, . . . , r-1}. First, the paper will show a method by which operations on the r-valued set {0, 1, . . . , r-1} can be expanded into operations on the set of nonempty subsets of {0, 1, . . . , r-1}. These operations will be called regular since this method is identical with the way that Kleene expanded operations of binary logic into his ternary logic. Finally, explicit expressions of set-valued functions monotonic in subset will be presented.

We developd a method of implementing a multiple-valued Hopfield network on electronic circuits by using single-electron circuit technology. The single-electron circuit shows quantized behavior in its operation because of the discrete tunnel transport of electrons. It can therefore be successfully used for implementing neuron operation of the multiple-valued Hopfield network. The authors developed a single-electron neuron circuit that can produce the staircase transfer function required for the multiple-valued neuron. A method for constructing a multiple-valued Hopfield network by combining the neuron circuits was also developed. A sample network was designed that solves an example of the quadratic integer-programming problem. And a computer simulation demonstrated that the sample network can converge to its optimal state that represents the correct solution to the problem.

This paper describes the benefit of utilizing the unary function generators in a multiple-valued Programmable Logic Array (PLA). We will clarify the most suitable PLA structure in terms of the array size. The multiple-valued PLA considered here has a structure with two types of function generators (literal and unary function generators), a first-level array and a second-level array. On investigating the effectiveness to reduce the array size, we can pick up four form PLAs: MAX-of-TPRODUCT form, MIN-of-TSUM form, TSUM-of-TPRODUCT form and TPRODUCT-of-TSUM form PLAs among possible eight form PLAs constructing from the MAX, MIN, TSUM and TPRODUCT operators. The upper bound of the array sizes with v UGs is derived as (log2ppv + p(n-v) + 1) pn-1 to realize any n-variable p-valued function. Next, experiments to derive the smallest array sizes are done for 10000 randomly generated functions and 21 arithmetic functions. These results conclude that MAX-of-TPRODUCT form PLA is the most useful in reducing the array size among the four form PLAs.

A compact residue arithmetic multiplier based on the radix-4 signed-digit arithmetic is presented. Conventional residue arithmetic circuits have been designed using binary number arithmetic system, but the carry propagation arises which limits the speed of arithmetic operations in residue modules. In this paper, two radix-4 signed-digit (SD) number representations, {-2,-1,0,1,2} and {-3,-2,-1,0,1,2,3}, are introduced. The former is used for the input and output, and the later for the inner arithmetic circuit of the presented multiplier. Integers 4p and 4p 1 are used as moduli of residue number system (RNS), where p is a positive integer and both circuits for partial product generation and sum of the partial products can be efficiently constructed by using the multiple-valued current-mode circuits. The modulo m addition, m=4p or m=4p 1, can be performed by an SD adder or an end-around-carry SD adder with the multiple-valued circuits and the addition time is independent of the word length of operands. The modulo m multiplier can be compactly constructed using a binary tree of the multiple-valued modulo m SD adders, and consequently the modulo m multiplication is performed in O(log p) time. The number of MOS transistors required in the presented residue arithmetic multiplier is about 86p2 + 66p.

A multiple-valued logic inverter is proposed that uses single-electron-tunneling (SET) circuits in which the discreteness of the electron charge is utilized. The inverter circuit, which is composed of only two SET transistors, has a memory function as well as an inverter function for multiple-valued logic. A quantizing circuit and a D flip-flop circuit for multiple-valued logic can be compactly constructed by combining two inverters. A threshold device can be compactly constructed by attaching more than one input capacitor to the inverter circuit. A quaternary full adder circuit can be constructed by using two threshold devices. Implementation issues are also discussed.

This paper describes a new model of multiple-valued immune network based on biological immune response network. The model of multiple-valued immune network is formulated based on the analogy with the interaction between B cells and T cells in immune system. The model has a property that resembles immune response quite well. The immunity of the network is simulated and makes several experimentally testable predictions. Simulation results are given to a letter recognition application of the network and compared with binary ones. The simulations show that, beside the advantages of less categories, improved memory pattern and good memory capacity, the multiple-valued immune network produces a stronger noise immunity than binary one.

This paper considers methods to design multiple-output networks based on decision diagrams (DDs). TDM (time-division multiplexing) systems transmit several signals on a single line. These methods reduce: 1) hardware; 2) logic levels; and 3) pins. In the TDM realizations, we consider three types of DDs: shared binary decision digrams (SBDDs), shared multiple-valued decision diagrams (SMDDs), and shared multi-terminal multiple-valued decision diagrams (SMTMDDs). In the network, each non-terminal node of a DD is realized by a multiplexer (MUX). We propose heuristic algorithms to derive SMTMDDs from SBDDs. We compare the number of non-terminal nodes in SBDDs, SMDDs, and SMTMDDs. For nrm n, log n, and for many other benchmark functions, SMTMDD-based realizations are more economical than other ones, where nrm n is a (2n)-input (n1)-output function computing (X2+Y2)+0.5, log n is an n-input n-output function computing (2n1)log(x1)/nlog2, and a denotes the largest integer not greater than a.

We study ultrafast operation of multiple-valued quantizers composed of resonant-tunneling diodes (RTDs) and high electron mobility transistors (HEMTs). The operation principle of these quantizers is based on the monostable-multistable transition logic (MML) of series-connected RTDs. The quantizers are fabricated by monolithically integrating InP-based RTDs and 0.7-µm-gate-length HEMTs with a cutoff frequency of 40 GHz. To perform high-frequency experiments, an output buffer and termination resistors are attached to the quantizers, and the quantizers are designed to accommodate high-frequency input signals. Our experiments show that both ternary and quaternary quantizers can operate at clock frequencies of 10 GHz and at input frequencies of 3 GHz. This demonstrates the potential of applying RTD-based multiple-valued quantizers to high-frequency circuits.

We discuss a new decoder for the multiple-valued signed-digit number, using a current-mode CMOS transistor-oriented circuit structure. In this paper, a new decoding method with the selective summation of a redundantly represented addend "O = [-1 r]" is proposed, where r is the radix and the addend is applied to each digit with a negative value and any consecutively higher digit takes which has a value of O. A newly designed literal linear circuit is realized, which has a current-switch function that makes independently the short path when each digit has a value of O. Through the parallel connections of these current swiches, the same addend signal at the lower digit is transmitted in a higher speed, The decoder circuit is tested by using the general circuit simulation software SPICE and the circuit characteristics of the selective summation of a redundantly represented O addend and the output results of the SD decoding operation were simulated. We also evaluated the decoder circuit in terms of the processing speed and the circuit size.

The paper deals with Kleenean functions defined as fuzzy logic functions with constants. Kleenean functions provide a means of handling conditions of indeterminate truth value (ambiguous states) which ordinary classical logic (binary logic) cannot cope with. This paper clarifies a necessary and sufficient condition for a function to be a Kleenean function. The condition is provided with a set of two conditions, and it will be shown that they are independent of each other.

In this paper, we discuss problems in design and fault masking of multiple-valued cellular arrays where basic cells having simple switch functions are arranged iteratively. The stuck-at faults of switch cells are assumed to be fault models. First, we introduce a universal single-level array and derive the ratio of the number of single faults whose influence can be masked to the total number of single faults. Next, we propose a universal two-level array that outputs correct values even if single faults occur in it and derive the ratio of the number of double faults whose influence can be masked compared to the total number of double faults. By evaluating the universal single-level array and the universal two-level array from the viewpoints of design and fault masking, we show that the latter is superior to the former. Finally, we compare our universal two-level array with formerly presented arrays in order to demonstrate the advantages of our universal two-level array.

This paper concerns multiple-valued logical function realized by asynchronous circuit that may have feed-back loops and its completeness problems. The first aim is to give mathematical definition of an asynchronous circuit over multiple-valued logical functions and of the realization of multiple-valued logical function by means of an asynchronous circuit. For asynchronous element, the definition of circuit construction and initialization are very sensitive. A slight modification may have a considerable influence on the completeness. We consider three types of completeness (LF-, GS-, NS-completeness) for a set of multiple-valued logical functions. The LF-completeness means completeness of logical functions realized loop-free cirucit. The GS-completeness means completeness under general initialization assumption. The NS-completeness measn completeness under initialization by input assumption. The second aim is to give a completeness criterion for each type of completeness. This aim is realized for LF-completeness in general case and GS-completeness in ternary case. A completeness criteria for GS-completeness and NS-completeness are given under strong conditions.

This paper describes Kleenean coefficients that are a subset of Kleenean functions for use in representing multiple-valued logic functions. A conventional multiple-valued sum-of-products expression uses product terms that are the MIN of literals and constants. In this paper, a new sum-of-products expression is allowed to sum product terms that also include variables and complements of variables. Since the conventional sum-of-products expression is complete, so also is the augmented one. A minimization method of the new expression is described besed on the binary Quine-McCluskey algorithm. The result of computer simulation shows that a saving of the number of implicants used in minimal expressions by approximately 9% on the average can be obtained for some random functions. A result for some arithmetic functions shows that the minimal solutions of MOD radix SUM, MAX and MIN functions require much fewer implicants than those of the standard sum-of-products expressions. Thus, this paper clarifies that the new expression has an advantage to reduce the number of implicants in minimal sum-of-products expressions.

In order to reduce the ever increasing cost for ULSI manufacturing due to the complexity of integrated circuits, dramatic simplification in the logic LSI architecture as well as the very flexible circuit configuration have been achieved using a highfunctionality device neuron-MOSFET (γMOS).In γMOS logic circuits, however, computations based on the multiple-valued logic is the key for enhancing the functionality. Therefore, much higher accuracy of processing is required. After brief description of the operational principle of γMOS logic, the relationship between the number of multiple logic levels and the functionality enhancement is discussed for further enhancing the functionality of γMOS logic circuits by increasing the number of multiple logic levels, and the accuracy requirements for the manufacturing processes are studied. The order of a few percent accuracy is required for all principal device structural parameters when it is aimed to handle 50-level multiple-valued variable in the γMOS logic circuit.

In this paper, a new encoding/decoding scheme of multiple-valued separable balanced codes is presented. These codes have 2m information digits and m (R - 2) check digits in radices R 4, 2m - 1 information digits and m + 1 check digits in R = 3, where code-length n = Rm. In actual use of code-lengths and radices, it is shown that the presented codes are relatively efficient in comparison with multiple-valued Berger codes which are known as optimal unordered codes. Meanwhile, the optimality of multiple-valued Berger codes is discussed.

The present paper is concerned with an algorithm for the minimization of multiple-valued input, binary-valued output functions. The algorithm is an extension to muitiple-valued logic of an algorithm for the minimization of ordinary single-output Boolean functions. It is based on a local covering approach. Basically, it uses a "divide and conquer" technique, consisting of two steps called expansion and selection. The present algorithm preserves two important features of the original one. First, a lower bound on the number of prime implicants in the minimum cover of the given function is furnished as a by-product of the minimization. Second, all the essential primes of the function are identified and selected during the expansion process. That usually improves efficiency when handling functions with many essential primes. Results of a comparison of the proposed algorithm with the program ESPRESSO-IIC developed at Berkeley are presented.