This paper proposes new architecture LSIs based on wave-parallel computing to provide an essential solution to the interconnection problems in massively parallel processing. The basic concept is ferquency multiplexing of digital information, which enables us to utilize the parallelism of electrical (or optical) waves for parallel processing. This wave-parallel computing concept is capable of performing several independent binary funtions in parallel with a single module. In this paper, we discuss the design of wave-parallel image processing LSI to demonstrate the feasibility of reducing the number of interconnections among modules.

Robust-fault tolerance is a property that a computational result becomes nearly equal to the correct one at the occurrence of faults in digital system. There are many cases where the safety of digital control systems can be maintained if the property is satisfied. In this paper, robust-fault-tolerant three-valued arithmetic modules such as an adder and a multiplier are proposed. The positive and negative integers are represented by the number of 1's and 1's, respectively. The design concept of the arithmetic modules is that a fault makes linearly additive effect with a small value to the final result. Each arithmetic module consists of identical submodules linearly connected, so that multi-stage structure is formed to generate the final output from the last submodule. Between the input and output digits in the submodule some simple functional relation is satisfied with respect to the number of 1's and 1's. Moreover, the output digit value depends on very small portion of the submodules including the input digits. These properties make the linearly additive effect with a small value to the final result in the arithmetic modules even if multiple faults are occurred at the input and output of any gates in the submodules. Not only direct three-valued representation but also the use of three-valued logic circuits is inherently suitable for efficient implementation of the arithmetic VLSI system. The evaluation of the robust-fault-tolerant three-valued arithmetic modules is done with regard to the chip size and the speed using the standard CMOS design rule. As a result, it is made clear that the chip size can be greatly reduced.

Rapid advances in integrated circuit technology based on binary logic have made possible the fabrication of digital circuits or digital VLSI systems with not only a very large number of devices on a single chip or wafer, but also high-speed processing capability. However, the advance of processing speeds and improvement in cost/performance ratio based on conventional binary logic will not always continue unabated in submicron geometry. Submicron integrated circuits can handle multiple-valued signals at high speed rather than binary signals, especially at data communication level because of the reduced interconnections. The use of nonbinary logic or discrete-analog signal processing will not be out of the question if the multiple-valued hardware algorithms are developed for fast parallel operations. Moreover, in VLSI or ULSI processors the delay time due to global communications between functional modules or chips instead of each functional module itself is the most important factors to determine the total performance. Locally computable hardware implementation and new parallel hardware algorithms natural to multiple-valued data representation and circuit technologies are the key properties to develop VLSI processors in submicron geometry. As a result, multiple-valued VLSI processors make it possible to improve the effective chip density together with the processing speed significantly. In this paper, we summarize several potential advantages of multiple-valued VLSI processors in submicron geometry due to great reduction of interconnection and due to the suitability to locally computable hardware implementation, and demonstrate that some examples of special-purpose multiple-valued VLSI processors, which are a signed-digit arithmetic VLSI processor, a residue arithmetic VLSI processor and a matching VLSI processor can achieve higher performance for real-world computing system.

The demand for high-speed image processing is obvious in many real-world computations such as robot vision. Not only high throughput but also small latency becomes an important factor of the performance, because of the requirement of frequent visual feedback. In this paper, a high-performance VLSI image processor based on the multiple-valued residue arithmetic circuit is proposed for such applications. Parallelism is hierarchically used to realize the high-performance VLSI image processor. First, spatially parallel architecture that is different from pipeline architecture is considered to reduce the latency. Secondly, residue number arithmetic is introduced. In the residue number arithmetic, data communication between the mod mi arithmetic units is not necessary, so that multiple mod mi arithmetic units can be completely separated to different chips. Therefore, a number of mod mi multiply adders can be implemented on a single VLSI chip based on the modulus-slice concept. Finally, each mod mi arithmetic unit can be effectively implemented in parallel structure using the concept of a pseudoprimitive root and the multiple-valued current-mode circuit technology. Thus, it is made clear that the throughout use of parallelism makes the latency 1/3 in comparison with the ordinary binary implementation.

It is well known that the multiple-valued signed-digit (SD) arithmetic circuits have the attractive features of compactness and high-speed operation. However, both of these features have yet to be utilized fully. In this paper, we consider the application of a parallel-structure-based VLSI processor. A high-performance parallel-structure-based multiple-valued VLSI processor using the radix-2 SD number system is proposed. Its compactness makes the parallelism high under chip size limitations in comparison with the ordinary binary arithmetic circuits. Moreover, the speed of the single arithmetic module is very high in the SD arithmetic circuits, so that we can take advantage of the high-speed operation in the parallel-structure-based VLSI processor chip. The multiple-valued bidirectional current-mode technology is used not only in high-speed small sized arithmetic circuits, but also in reducing the number of connections in the parallel-structure-based VLSI processor. The proposed processor is specially developed for real-time digital control, where the performance is evaluated by delay time. Performance estimation using SPICE simulators shows that the delay time of proposed processor for matrix operations such as matrix multiplication is greatly reduced in comparison with a conventional binary processor.

On the basis of the controllability gramians, the observability gramians and the second order modes, this paper shows that optimal realizations (filter structures having minimum roundoff noises) of quarter-plane-causal, recursive and separable in denominator 2-D digital filters (CRSD filters for short) are scaled and rotated balanced realizations. Two applications of this relation are given. The first one gives a simple proof of the absence of overflow oscillations in optimal realizations. The second one, which is the main result of this paper, gives a direct design method of CRSD filters in the spatial domain. This method simplifies traditional two-step design (approximation and synthesis) into a one-step design with much less computational complexity. Resulting filters of this direct design method can approximate given 2-D impulse responses closely. In addition, they are always guaranteed to be stable, nearly optimal with respect to roundoff noise and free of overflow oscillations. The efficiency of the direct design method is shown by numerical examples.

This paper studies the design problem of causal, recursive and separable denominator (CRSD) 3-D state-space digital filters. First, a balanced approximation method and a synthesis method of optimal realizations of CRSD 3-D digital filters are proposed by introducing the concept of characteristic filters. Then, a simple equivalent relation between balanced realizations and optimal realizations of CRSD 3-D digital filters is revealed. Using this relation and the balanced approximation method proposed, this paper proposes a spatial-domain direct design method of CRSD 3-D digital filters. This direct design method can perform approximation and synthesis of CRSD 3-D digital filters simultaneously. Further, it can result in stable state-space digital filters which are nealy optimal with respect to roundoff noise, and free of overflow oscillations. Effciency of direct design method is shown by a numerical example.

The average coefficient sensitivity is defined for 2-D systems described by Roesser's local state space model. The sensitivity can be computed by using the 2-D observability Gramian and the 2-D controllability Gramian, which are also called the 2-D noise matrix and the 2-D covariance matrix if the 2-D systems are considered to be 2-D digital filters. Minimization of sensitivity via 2-D equivalent transforms is studied in cases of having no constraint and having a scaling constraint on the state vector. In the first case, the minimum sensitivity realizations are equivalent to the 2-D balanced realizations modulo a block orthogonal transform. In the second case, the 2-D systems are considered to be 2-D digital filters and the minimization of sensitivity is equivalent to the minimization of roundoff noise under l2-norm scaling constraint. An example is given to show method of analysing and minimizing the sensitivity of 2-D systems.

This paper designs and evaluates highly parallel VLSI processors for real time 2-D state-space digital filters using hierarchical behavioral description language and synthesizer. The architecture of the 2-D state-space digital filtering system is a linear systolic array of homogeneous VLSI processors, each of which consists of eight processing elements (PEs) executing 1-D state-space digital filtering with multi-input and multi-output. Hierarchical behavioral description language and synthesizer are adopted to design and evaluate PE's and the VLSI processors. One 16 bit fixed-point PE executing a (4, 4)-th order 2-D state-space digital filtering is described on the basis of distributed arithmetic in about 1,200 steps by the description language and is composed of 15 K gates in terms of 2 input NAND gate. One VLSI processor which is a cascade connection of eight PEs is composed of 129 K gates and can be integrated into one 1515 [mm2] VLSI chip using 1 µm CMOS standard cell. The 2-D state-space digital filtering system composed of 128 VLSI processors at 25 MHz clock can execute a 1,0241,024 image in 1.47 [msec] and thus can be applied to real-time conventional video signal processing.

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.

This paper explores the potential of multiwave interconnectionsoptical interconnections that employ wavelength components as multiplexable information carriersfor constructing next-generation multiprocessor systems using MCM technology. A hypercube-based multiprocessor network called the multiwave hypercube (MWHC) is proposed, where multiwave interconnections provide highly-flexible dynamic communication channels among processing elements. A performance analysis shows that the use of multiwavelength optics makes possible the reduction of network complexity on an MCM substrate, while supporting low-latency message routing.

This paper presents a formal approach to verify arithmetic circuits using symbolic computer algebra. Our method describes arithmetic circuits directly with high-level mathematical objects based on weighted number systems and arithmetic formulae. Such circuit description can be effectively verified by polynomial reduction techniques using Grobner Bases. In this paper, we describe how the symbolic computer algebra can be used to describe and verify arithmetic circuits. The advantageous effects of the proposed approach are demonstrated through experimental verification of some arithmetic circuits such as multiply-accumulator and FIR filter. The result shows that the proposed approach has a definite possibility of verifying practical arithmetic circuits.

This paper presents a model-based study of SET (Single-Electron-Transistor) logic gate family for synthesizing binary, MV (Multiple-Valued) and mixed-mode logic circuits. The use of SETs combined with MOS transistors allows compact realization of basic logic functions that exhibit periodic transfer characteristics. The operation of basic SET logic gates is successfully confirmed through SPICE circuit simulation based on the physical device model of SETs. The proposed SET logic gates are useful for implementing binary logic circuits, MV logic circuits and binary-MV mixed-mode logic circuits in a highly flexible manner. As an example, this paper describes design of various parallel counters for carry-propagation-free arithmetic, where MV signals are effectively used to achieve higher functionality with lower hardware complexity.

This paper studies the model reduction of separable denominator multi-dimensional (SD M-D, M is used as an integer) linear, shift-invariant systems (systems for short). First, it shows that the controllability, observability and stability of an SD M-D system are completely determined by M 1-D multi-input multi-output systems, which are referred to as the characteristic systems in this paper. Then the balanced realizations of SD M-D systems are defined, and a synthesis method of such realizations is given. Finally, a model reduction method based on the balanced realizations is proposed. Validity of this method is illustrated by a numerical example of a 3-D system.

In order to suppress constant input limit cycles in 2-D separable denominator digital filters, bias cancel realizations are proposed by modifying 2-D separable denominator digital filters free of zero imput limit cycles.

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.

This paper proposes an efficient design method of three-dimensional (3-D) recursive digital filters for video signal processing via decomposition of magnitude specifications. A given magnitude specification of a 3-D digital filter is decomposed into specifications of 1-D digital filters with three different (horizontal, vertical, and temporal) directions. This decomposition can reduce design problems of 3-D digital filters to design problems of 1-D digital filters, which can be designed with ease by conventional methods. Consequently, design of 3-D digital filters can be efficiently performed without complicated tests for stability and large amount of computations. In order to process video signal in real time, the 1-D digital filters with temporal direction must be causal, which is not the case in horizontal and vertical directions. Since the proposed method can approximate negative magnitude specifications obtained by the decomposition with causal 1-D R filters, the 1-D digital filters with temporal direction can be causal. Therefore the 3-D digital filters designed by the proposed method is suitable for real time video signal processing. The designed 3-D digital filters have a parallel separable structure having high parallelism, regularity and modularity, and thus is suitable for high-speed VLSI implementation.

A new computer architecture using multiwavelength optoelectronic integrated circuits (OEICs) is proposed to attack the problems caused by interconnection complexity. Multiwavelength-OEIC architecures, where various wavelengths are employed as information carriers, provide the wavelength as an extra dimension of freedom for parallel processing, so that we can perform several independent computations in parallel in a single optical module using the wavelength space. This multiplex computing" enables us to reduce the wiring area required by a network and improve their complexity. In this paper, we discuss the efficient multiplexing of Batcher's bitonic sorting networks, highly parallel computing architectures that require global interconnections inherently. A systematic multiplexing of interconnection topology is presented using a binary representation of the connectivities of interconnection paths. It is shown that the wiring area can be reduced by a factor of 1/r2 using r kinds of wavelength components.

This paper presents a new approach to designing arithmetic circuits by using a graph-based evolutionary optimization technique called Evolutionary Graph Generation (EGG). The key idea of the proposed method is to introduce a higher level of abstraction for arithmetic algorithms, in which arithmetic circuit structures are modeled as data-flow graphs associated with specific number representation systems. The EGG system employs evolutionary operations to transform the structure of graphs directly, which makes it possible to generate the desired circuit structure efficiently. The potential capability of EGG is demonstrated through an experiment of generating constant-coefficient multipliers.

This paper proposes an analysis method of the roundoff error due to finite-wordlength decoding in fractal image coding. The proposed method can be applied to large images such as 256 256 or 512 512 images because it needs no complex matrix computation. The simplified model used here ignores the effect of decimation ratio on the roundoff error because it is negligible. As an analysis result, the proposed method gives the output error variance which consists of grey-tone scaling coefficients and an iteration number. This method is tested on various types of 12 standard images which have 256 256 size or 512 512 size with 256 grey levels. Comparisons of simulation results with analysis results are given. The results show that our analysis method is valid for the fractal image coding.