A design method of multilevel logic networks, in single-rail input logic, with MOS cells for parity functions of n variables is presented. The parity functions x1x2xn in a two level network requires 2n-1+1 gates, whereas the number of NOR gates in a multilevel network for this function is proportional to n. Since MOS cells are playing a major role in LSI and can represent more complex functions than a NOR or a NAND gate, it is possible to obtain smaller networks with complex MOS cells than with NOR or NAND gates. However, if MOS cells become excessively complex, the propagation delay time of MOS cells is too large and the normal operation of the whole MOS network cannot be expected. The design procedure given in this paper is systematic and very easy to apply. In the beginning, the formulation of MOS cells and MOS networks has been presented. In this formulation, the number of series and parallel transistors and the number of MOS cells and levels can be defined and enumerated for MOS networks. Without the restrictions the maximum number of series transistors is the number of input variables, n. With the estriction on the number of series transistors to R, the number of parallel transistors is less than or equal to 2R-1. Furthermore, the number of MOS cells and the number of levels of the MOS network are proportional to n and logRn, respectively. Since the designed network is similar to a complete tree, it would also be useful to process a series of combinations of input variable values.

We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.

We propose two lockout-free (starvation-free) mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first algorithm is a modification of the well-known tournament algorithm for the mutual exclusion problem. By the modification we can speed up the original algorithm. The running time of the modified algorithm from the entrance of the trying region to the entrance of the critical region is at most (n-1)c+O(nl), where n is the number of processes, l is an upper bound on the time between successive two steps of each process, and c is is an upper bound on the time that any user spends in the critical region. The second algorithm is a further modification of the first algorithm. It is designed so that some processes have an advantage of access to the resource over other processes.

This paper deals with the size of switching functions in Exclusive-OR sum-of-products expressions (ESOPs). The size is the number of products in ESOP. There are no good algorithms to find an exact minimum ESOP. Since the exact minimization algorithms take a time in double exponential order, it is almost impossible to minimize ESOPs for an arbitrary n-variable functions with n5. Then,it is necessary to study the size of some concrete functions. These concrete functions are useful for testing heuristic minimization algorithms. In this paper we present the lower bounds on size of periodic functions in ESOPs. A symmetric function is said to be periodic when the vector of weights of inputs X such that f(X)1 is periodic. We show that the size of a 2t+1-periodic function with rank r is proportional to n2t+r, where t0 and 0r2t, i.e., in polynomial order,and thet the size of a (2s+1)2t-periodic function with s0 and t0 is greater than or equal to (3/2)n-(2s+1)2t, i.e., in exponential order. The concrete function the size of which is greater than or equal to 32(3/2)n-8 is presented. This function requires the largest size among the concrete functions the sizes of which are known. Some results for non-periodic symmetric functions are also given.

In this paper, we propose a design of reversible adder/subtractor blocks and arithmetic logic units (ALUs). The main concept of our approach is different from that of the existing related studies; we emphasize the function design. Our approach of investigating the reversible functions includes (a) the embedding of irreversible functions into incompletely-specified reversible functions, (b) the operation assignment, and (c) the permutation of function outputs. We give some extensions of these techniques for further improvements in the design of reversible functions. The resulting reversible circuits are smaller than that of the existing design in terms of the number of multiple-control Toffoli gates. To evaluate the quantum cost of the obtained circuits, we convert the circuits to reduced quantum circuits for experiments. The results also show the superiority of our realization of adder/subtractor blocks and ALUs in quantum cost.

A graph G = (V, E) with N nodes is called an N-hyper-ring if V = {0, ..., N-1} and E = {(u, v)(u-v) modulo N is power of 2}. We study embeddings of the 2n-hyper-ring in the n-dimensional hypercube. We first show a greedy embedding with dilation 2 and congestion n+1. We next modify the greedy embedding, and then we obtain an embedding with dilation 4 and congestion 6.

It is known that AND-EXOR two-level networks obtained by AND-EXOR expressions with positive literals are easily testable. They are based on the single-rail-input logic, and require (n+4) tests to detect their single stuck-at faults, where n is the number of the input variables. We present three-level networks obtained from single-rail-input OR-AND-EXOR expressions and propose a more easily testable realization than the AND-EXOR networks. The realization is an OR-AND-EXOR network which limits the fan-in of the AND and OR gates to n/r and r respectively, where r is a constant (1 r n). We show that only (r+n/r) tests are required to detect the single stuck-at faults by adding r extra variables to the network.

Consider a set of parties who do not trust each other but want to compute some agreed function of their inputs in a secure way. This problem is known as multi-party computation. It has various interesting applications including election over the internet, electric contracts, private and secret database, joint signatures, and others. A number of techniques for the problem have been proposed. Secure protocols for multi-paty computation known so far are mainly based on threshold secret sharing, verifiable secret sharing, zero-knowledge proofs, and error-correcting codes. We survey important and interesting results on secure multi-party computation under the existence of various types of adversaries.

This paper deals with minimization of ESOPs (exclusive-or sum-of-products) which represent symmetric functions. Se propose an efficient simplification algorithm for symmetric functions, which guarantees the minimality for some subclass of symmetric functions, and present the minimum ESOPs for all 6-variable symmetric functions.

The Firing Squad Synchronization Problem (FSSP), one of the most well-known problems related to cellular automata, was originally proposed by Myhill in 1957 and became famous through the work of Moore [1]. The first solution to this problem was given by Minsky and McCarthy [2] and a minimal time solution was given by Goto [3]. A significant amount of research has also dealt with variants of this problem. In this paper, from a theoretical interest, we will extend this problem to number patterns on a seven-segment display. Some of these problems can be generalized as the FSSP for some special trees called segment trees. The FSSP for segment trees can be reduced to a FSSP for a one-dimensional array divided evenly by joint cells that we call segment array. We will give algorithms to solve the FSSPs for this segment array and other number patterns, respectively. Moreover, we will clarify the minimal time to solve these problems and show that there exists no such solution.

It has been considered difficult to obtain the minimum AND-EXOR expression of a given function with six variables in a practical computing time. In this paper, a faster algorithm of minimizing AND-EXOR expressions is proposed. We believe that our algorithm can compute the minimum AND-EXOR expressions of any six-variable and some seven-variable functions practically. In this paper, we first present a naive algorithm that searches the space of expansions of a given n-variable function f for a minimum expression of f. The space of expansions are generated by using all combinations of (n-1)-variable product terms. Then, how to prune the branches in the search process and how to restrict the search space to obtain the minimum solutions are discussed as the key point of reduction of the computing time. Finally a faster algorithm is constructed by using the methods discussed. Experimental results to demonstrate the effectiveness of these methods are also presented.