This paper presents an arithmetic module generator based on an arithmetic description language called ARITH. The use of ARITH makes it possible to describe a wide variety of arithmetic algorithms in a unified manner. The ARITH descriptions are formally verified in the generator even if the arithmetic algorithms include unconventional number systems for operands or internal variables. The proposed generator also optimizes arithmetic algorithms by using performance profiles derived from the previous generation. From these features, we can obtain high-performance arithmetic modules whose functions are completely verified at the algorithm level. In this paper, we demonstrate that the optimal prefix adders improved the performance of generated arithmetic modules such as multipliers in comparison with the standard prefix adders.

This paper introduces a systematic approach to designing high-performance parallel adders based on Counter Tree Diagrams (CTDs). By using CTDs, we can describe addition algorithms at various levels of abstraction. A high-level CTD represents a network of coarse-grained components associated with word-level operands, whereas a low-level CTD represents a network of primitive components that can be directly mapped onto physical devices. The level of abstraction in circuit representation can be changed by decomposition of CTDs. We can derive possible variations of adder structures by decomposing a high-level CTD into low-level CTDs in a formal manner. In this paper, we focus on an application of CTDs to the design of redundant arithmetic adders with limited carry propagation. For any redundant number representation, we can obtain the optimal adder structure by trying every possible CTD decomposition and CTD-variable encoding. The potential of the proposed approach is demonstrated through an experimental synthesis of Redundant-Binary (RB) adders with CMOS standard cell libraries. We can successfully obtain RB adders that achieve an about 30-40% improvement in terms of power-delay product compared with conventional designs.

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 where the conventional techniques failed.

A major approach for palmprint recognition today is to extract feature vectors corresponding to individual palmprint images and to perform palmprint matching based on some distance metrics. One of the difficult problems in feature-based recognition is that the matching performance is significantly influenced by many parameters in feature extraction process, which may vary depending on environmental factors of image acquisition. This paper presents a palmprint recognition algorithm using phase-based image matching. The use of phase components in 2D (two-dimensional) discrete Fourier transforms of palmprint images makes possible to achieve highly robust palmprint recognition. Experimental evaluation using a palmprint image database clearly demonstrates an efficient matching performance of the proposed algorithm.

A major approach for fingerprint recognition today is to extract minutiae from fingerprint images and to perform fingerprint matching based on the number of corresponding minutiae pairings. One of the most difficult problems in fingerprint recognition has been that the recognition performance is significantly influenced by fingertip surface condition, which may vary depending on environmental or personal causes. Addressing this problem, this paper presents a fingerprint recognition algorithm using phase-based image matching. The use of phase components in 2D (two-dimensional) discrete Fourier transforms of fingerprint images makes possible to achieve highly robust fingerprint recognition for low-quality fingerprints. Experimental evaluation using a set of fingerprint images captured from fingertips with difficult conditions (e.g., dry fingertips, rough fingertips, allergic-skin fingertips) demonstrates an efficient recognition performance of the proposed algorithm compared with a typical minutiae-based algorithm.

This paper presents a generic objected-oriented framework of evolutionary graph generation (EGG) for automated circuit synthesis. The EGG system can be systematically implemented for different design problems by inheriting the framework class templates. The potential capability of EGG framework is demonstrated through experimental synthesis of both digital and analogue circuits. Design examples discussed in this paper are: (i) bit-serial multipliers using bit-level arithmetic components; and (ii) current mirrors using transistor-level components.

This paper presents a graph-based evolutionary optimization technique, called evolutionary graph generation (EGG), to synthesize arithmetic circuits. The potential capability of EGG has been investigated through an experiment of synthesizing fast constant-coefficient multipliers.

This paper proposed an efficient human motion segmentation algorithm with pixel-wise accuracy. Our aim is to solve the problem of separating human image as object of interest from the background image. In our approach, every pixel of a video sequence frame is considered to be a 5-dimensional vector, consisting of pixel position coordinate components (x,y coordinates) plus pixel color information in HSV (Hue, Saturation, and Value). First, the human assistant is employed to create the reference frame of desired human object of interest. This step is done only at the first frame of video sequence. The Kohonen Learning Vector Quantization (LVQ) is then used to give optimal class region decision between the human object class and background class by training its codebook vectors, supervised by reference frame. The segmentation result is generated by doing vector quantization of LVQ codebook vectors to all pixels of image frame. Finally, for adapting the human object class movement in succeeding frames, LVQ codebook vectors are updated periodically by feeding back the result of the last segmentation into the training step. This paper also presents proposed segmentation algorithm performance to some MPEG-4 video test.

We present an efficient graph-based evolutionary optimization technique, called evolutionary graph generation (EGG), and the proposed approach is applied to the design of combinational and sequential arithmetic circuits based on parallel counter-tree architecture. The fundamental idea of EGG is to employ general circuit graphs as individuals and manipulate the circuit graphs directly using new evolutionary graph operations without encoding the graphs into other indirect representations, such as the bit strings used in genetic algorithm (GA) proposed by Holland (1992) and trees used in genetic programming (GP) proposed by Koza et al. (1997). In this paper, the EGG system is applied to the design of constant-coefficient multipliers and the design of bit-serial data-parallel adders. The results demonstrate the potential capability of EGG to solve the practical design problems for arithmetic circuits with limited knowledge of computer arithmetic algorithms. The proposed EGG system can help to simplify and speed up the process of designing arithmetic circuits and can produce better solutions to the given problem.

The paper presents a hardware algorithm for a real/complex reconfigurable arithmetic unit, which can change its structure for three different arithmetic modes in real time. The three modes realize: (i) a single precision complex number multiplication; (ii) a double precision real number multiplication; and (iii) a pair of single precision real number four operand multiply-add operations, respectively. We discuss the reconfiguration of hardware structure on the basis of the transformation of the number system used in each arithmetic mode. The designed arithmetic unit can perform high speed real/complex arithmetic computations based on binary tree addition scheme, and also exhibits highly regular structure suited for VLSI implementation.

This paper presents a GA-based design method for multiplierless 2-D state-space digital filters (SSDFs) with very small roundoff noise. All coefficients of the designed 2-D SSDFs are expressed as the sum of two powers-of-two terms. Consequently, the multiplierless 2-D SSDFs are attractive for the high-speed operation and simplification of hardware, since the signal in the filters can be processed by fewer shifting operations and additions instead of multiplications. The proposed method can design multiplierless 2-D SSDFs without significantly increasing the roundoff noise power gain and with smaller approximation error than those of the other methods which use transfer functions in a continuous coefficient space. The effectiveness of the proposed method is demonstrated with a design example.

The nearest-neighbor multilayer perceptron (NN-MLP) is a single-hidden-layer network suitable for pattern recognition. To design an NN-MLP efficiently, this paper proposes a new evolutionary algorithm consisting of four basic operations: recognition, remembrance, reduction, and review. Experimental results show that this algorithm can produce the smallest or nearly smallest networks from random initial ones.

This paper presents a new design method of 2-D state-space digital filters (2D-SSDFs) with powers-of-two coefficients based on a genetic algorithm (GA). The design problem is formulated in a state-space model. All coefficients of 2D-SSDF are then encoded to binary strings in order to apply the GA to the design problem. In addition, a stability test routine is embedded in the GA procedure to ensure the stability of the resulting 2D-SSDFs. The proposed method can obtain 2D-SSDFs with small approximation error in a nonuniform discrete space such as powers-of-two coefficients, which means that the designed 2D-SSDFs are attractive for high-speed operation and simple hardware architecture. The effectiveness of the proposed method is demonstrated by a design example.

The paper proposes an optimal design method of separable-denominator (SD) two-dimensional digital filters (2DDFs) based on a simple genetic algorithm (SGA) for frequency-domain specifications. Parameters of the transfer function of a SD-2DDF are encoded to bit strings in order to apply a SGA to the design. Stability of a 2DDF is easily checked because of the separability of the denominator of the transfer function. The proposed method has flexibility for change of specifications of 2DDFs, and enables one to use arbitrary error functions. The usefulness of the proposed method is demonstrated by design examples.>

Iterated transformation theory-based coding (ITTBC) suffers from very high computational complexity in the encoding phase. This is due to its exhaustive search. This paper proposes a multiresolution tree search ITTBC (MTS-ITTBC) to reduce the encoding complexity. MTS-ITTBC searches the ITT-code using a multiresolution search-tree. The computational load of MTS-ITTBC is O(NlogN), while that of full search ITTBC is O(N/sup 2/), where N is the number of range blocks or domain blocks in an image. Numerical examples show that the encoding time of MTS-ITTBC can be reduced to 14% of that of the full search ITTBC, while the loss in quality relative to the full search ITTBC is about 0.5 dB in p-pSNR, which is visually negligible.>

Presents a very-large-scale-integration (VLSI)-oriented high-speed multiplier design method based on carry-propagation-free addition trees and a circuit technique, so-called multiple-valued current-mode (MVCM) circuits. The carry-propagation-free addition method uses a redundant digit set such as /spl lcub/0,1,2,3/spl rcub/ and /spl lcub/0,1,2,3,4/spl rcub/. The number representations using such redundant digit sets are called redundant positive-digit number representations. The carry-propagation-free addition is written by three steps, and the adder can be designed directly and efficiently from the algorithm using MVCM circuits. The designed multiplier internally using the MVCM parallel adder with the digit set /spl lcub/0,1,2,3/spl rcub/ in radix 2 has attractive features on speed, regularity of the structure, and reduced complexities of active elements and interconnections. A prototype CMOS integrated circuit of the MVCM parallel adder has been implemented, and its stable operation has been confirmed. Other possible schemes of multipliers with redundant digit sets using MVCM technology are discussed.>

A VLSI-oriented matrix multiply-addition processor (MMP) is proposed for minimum-delay-time inverse dynamics computation on a linear array structure. It is shown that the delay time of the inverse dynamics computation becomes minimum based on the concept of the odd-even alternative computation. The MMP architecture is systematically designed by using two types of data-dependence graphs of the odd-even alternative computation. It is demonstrated by the layout evaluation that the MMP can be easily implemented in a single chip using the current VLSI technology (e.g. 1 mu m CMOS). The performance with regard to the delay time is higher than for previously reported architectures.>

The authors present an LSI (large-scale integrated) circuit for high-speed inverse kinematics computation. They demonstrate that inverse kinematic solutions can be described by two-dimensional vector rotations and arc tangent operations and that these operations can be efficiently computed by the coordinate rotation digital computer (CORDIC) algorithms. The chip is fabricated using 1.5- mu m CMOS gate array technology, and the design of the arithmetic unit on the chip is based on the CORDIC algorithms. Pipelining is fully used in the processor to enhance the operating ration up to 100%. The resulting compact inverse kinematics processor is composed of the above chip and a few memory chips for program and data. The processor can be used for various kinds of manipulators.>

This paper proposes a newly defined sensitivity called a statistical sensitivity. The statistical sensitivity is minimized, and minimum sensitivity structures are obtained via equivalent transformations. The sensitivity of linear systems can be interpreted by the controllability and observability concepts of the state-space.

This paper studies the roundoff noise and the scaling in 2-D state space digital filters. The noise matrix and the covariance matirx in the 2-D case are derived. They are expressed with infinite sum or double integral. A formulation is given to synthesize minimum roundoff noise 2-D state space digital filters. A numerical example is given to show the methods of analysis and synthesis.

This paper proposes a unified design method of state-space digital filters using system balancing concept. This method is formed by applying a newly discovered relation between the balanced realizations and the optimal realizations of digital filters to the approximation method that results in balanced realizations. It can perform the approximation and the synthesis problems of the filter design simultaneously and efficiently, and can yield suboptimal digital filters which approximate given impulse responses closely and suppress limit cycles.

This paper describes another computational algorithm for the discrete Fourier transform(DFT) via the discrete Walsh transform(DWT). The number of multiplications required by this algorithm is approximately NL/9 where N is the number of data points and L is the number of Fourier coefficients desired. This number shows a 33 % decrease against NL/6 in the previous algorithm published by us. The proposed algorithm can be derived by using conventional sampling points in the DFT. The DFT computation via the DWT is superior to the fast Fourier transform(FFT) approach in applications where L is relatively small compared with N and where the Walsh and Fourier coefficients are both desired.

Arbitrary digital filters are uniquely described by the element equations proposed here in which the outputs of adders and multipliers are defined as variables in addition to state variables. Equations of overflow oscillations in arbitrary digital filters are represented using the simultaneous equations or the DFT. A sufficient condition for absence of overflow oscillations is obtained by means of the element equations and the second method of Liapunov, and is applied to a ladder form as an example.

A directed graph is introduced to treat state transition of digital filters with arbitrary structures. State space of the digital filter defined as a finite subset of lattice group is divided into four subsets from a point of view of the state transition about the limit cycles including overflow oscillations. Based on the concept of the four subsets proposed here, the state distribution is obtained by the aid of a computer. Two algorithms are presented to eliminate the limit cycles of any digital filters using the state distribution computed. An example is represented to show how the algorithms are applied for the elimination of the limit cycles.

The ternary T-gate can be used as a basic building block to construct both combinational and sequential circuits. Since the T-gate is one kind of tree-type universal logic module, any combinational circuit can be built up with modular logic arrays. For constructing ternary memory elements, however, the T-gate is required to be static hazard-free. A theoretical study is done on the necessary conditions for the practical realization of the static-hazard-free T-gate. On the basis of the result obtained, the static-hazard-free T-gate is realized using the ECL technique. The static-hazard-free T-gates obtained here can be used as building blocks to construct memory elements. Various memory elements such as D flip-flap-flop (FFF), D master-slave FFF, B master-slave FFF, and counting FFF is constructed easily. Using these memory elements, three different types of ternary counters can be designed and realized. They are an asynchronous signed ternary counter, a synchronous signed ternary counter, and a counter based on a shift register. Their design methods are discussed. These ternary counters are superior to the binary ones in that the up-down cotnting can easily be carried out by one input signal.

This correspondence presents a theoretical study on the synthesis of multiple-valued logic networks based on tree-type universal logic modules (T-ULM's). The mathematical notation of T-ULM is introduced. On the basis of the mathematical properties, an algorithm for synthesizing an arbitrary logic function of n variables with a smaller number of modules is presented. In this algorithm, only true and constant inputs are allowed at input terminals. The algorithm consists of two parts. The first one is a functional decomposition, and the other one is the proper order of the expansion which is the problem of zinding the most incomplete tree structure. Thus it is established that the systematic and nonexhaustive procedure of the algorithm gives a suboptimal solution for the reduction of the number of T-ULM's.