This paper proposes a decomposition method for symmetric multiple-valued functions. It decomposes a given symmetric multiple-valued function into three parts. By using suitable decision diagrams for the three parts, we can represent symmetric multiple-valued functions compactly. By deriving theorems on sizes of the decision diagrams, this paper shows that space complexity of the proposed representation is low. This paper also presents algorithms to construct the decision diagrams for symmetric multiple-valued functions with low time complexity. Experimental results show that the proposed method represents randomly generated symmetric multiple-valued functions more compactly than the conventional representation method using standard multiple-valued decision diagrams. Symmetric multiple-valued functions are a basic class of functions, and thus, their compact representation benefits many applications where they appear.

A systolic array is an ideal for ASICs because of its massive parallelism with a minimum communication overhead, regularity and modularity. Most of commercial FPGAs cannot handle systolic structure with fast sampling rate for their general-purpose architecture nature. This paper presents a new PLD architecture targeting a super-systolic array for application-specific arithmetic operations such as MAC. This architecture combines the high performance of ASICs with the flexibility of PLDs and it offers a significant alternative view on the programmable logic devices. The super-systolic array is ideal for a newly proposed PLD architecture when it comes to area-efficiency, P&R and clock speed.

Obradovic and Parberry showed that any n-input k-ary function can be computed by a depth 4 unit-weight k-ary threshold circuit of size O(nkn). They also showed that any n-input k-ary symmetric function can be computed by a depth 6 unit-weight k-ary threshold circuit of size O(nk+1). In this paper, we improve upon and expand their results. The k-ary threshold circuits of nonunit weight and unit weight are considered. We show that any n-input k-ary function can be computed by a depth 2 k-ary threshold circuit of size O(kn-1). This means that depth 2 is optimal for computing some k-ary functions (e.g., a PARITY function). We also show that any n-input k-ary function can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(kn). Next, we show that any n-input k-ary symmetric function can be computed by a depth 3 k-ary threshold circuit of size O(nk-1), and can be computed by a depth 3 unit-weight k-ary threshold circuit of size O(knk-1). Finally, we show that if the weights of the circuit are polynomially bounded, some k-ary symmetric functions cannot be computed by any depth 2 k-ary threshold circuit of polynomial-size.

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.

This paper presents an optimization method for pseudo-Kronecker expressions of p-valued input two-valued output functions by using multi-place decision diagrams for p2 and p4. A conventional method using extended truth tables requires memory of O (3n) to simplify an n-variable expression, and is only practical for functions of up to n14 variables when p2. The method presented here utilizes multi-place decision diagrams, and can optimize considerably larger problems. Experimental results for up to n39 variables are shown.