A low-cost and low-power via-programmable structured ASIC architecture named “VPEX3” and a VPEX3-specific CAD system are developed. In the VPEX3 architecture, which is an improved version of the old VPEX and VPEX2 architectures, an arbitrary logic function including sequential logic can be programmed by three via layers. The logic elements (LEs) of VPEX3 are 60% smaller than those of the previous VPEX2, which can be programmed by two via layers. In this paper, we describe a global architecture named Logic Array Block (LAB) composed of LE matrices. The clock lines are buffered in the buffering region on the left and right sides of LAB. Next, a VPEX3-specific CAD system utilizing an academic placement tool named “CAPO” and the “FGR” global router is developed. Since these tools are originally designed for ASICs, we developed CAD tools for supporting a structured ASIC architecture. In particular, we developed a detailed router that assigns via positions on the via-programmable routing fabric. Our CAD system successfully converts the HDL design to GDS-II data format including via-1, 2, 3 layouts, and the successful verification of LVS and DRC on GDSII is achieved. The performance of the VPEX3 architecture and the CAD system is evaluated using ISCAS benchmark circuits. The developed CAD system is used to successfully design a test chip composed of 130110 LEs.

Clocked cascade voltage switch logic (C2VSL) circuits with gated feedback were newly designed for synchronous systems. In order to investigate single event transient (SET) effects on the C2VSL circuits, SET effects on C2VSL EX-OR circuits were analyzed using SPICE. Simulation results have indicated that the C2VSL have increased tolerance to SET.

This paper presents a novel technique to realize Karnin et al.'s (k,n)-threshold schemes over binary field extensions as a software. Our realization uses the matrix representation of finite fields and matrix-vector multiplications, and enables rapid operations in software implementation. The theoretical evaluation and computer simulation reveal that our realization of Karnin et al.'s scheme achieves much faster processing time than the ordinary symbol oriented realization of the scheme. Further, we show that our realization has comparable performance to the existing exclusive-OR-based fast schemes of Fujii et al. and Kurihara et al.

Single event transient (SET) effects on original static cascade voltage switch logic (CVSL) exclusive-OR (EX-OR) circuits have been investigated using SPICE. SET simulation results have confirmed that the static CVSL EX-OR circuits have increased tolerance to SET. The static CVSL EX-OR circuit is more than 200 times harder than the conventional CMOS circuit.

Shamir's (k,n)-threshold secret sharing scheme (threshold scheme) has two problems: a heavy computational cost is required to make shares and recover the secret, and a large storage capacity is needed to retain all the shares. As a solution to the heavy computational cost problem, several fast threshold schemes have been proposed. On the other hand, threshold ramp secret sharing schemes (ramp scheme) have been proposed in order to reduce each bit-size of shares in Shamir's scheme. However, there is no fast ramp scheme which has both low computational cost and low storage requirements. This paper proposes a new (k,L,n)-threshold ramp secret sharing scheme which uses just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret at a low computational cost. Moreover, by proving that the fast (k,n)-threshold scheme in conjunction with a method to reduce the number of random numbers is an ideal secret sharing scheme, we show that our fast ramp scheme is able to reduce each bit-size of shares by allowing some degradation of security similar to the existing ramp schemes based on Shamir's threshold scheme.

In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme)[1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR(XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.

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.

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.

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.