Multiplication-accumulation is the basic computation required for image filtering operations. For real-time image filtering, very high throughput computation is essential. This work proposes a hardware algorithm for an application-specific VLSI architecture which realizes an area-efficient high throughput multiplier-accumulator. The proposed algorithm utilizes a priori knowledge of filter mask coefficients and optimizes number of basic hardware components (e.g., full adders, pipeline latches, etc.). This results in the minimum area VLSI architecture under certain input/output constraints.

This paper describes a noise resistant algorithm for recovering the three-dimensional motion of a rigid object from optical flow. First, it is shown that in the absence of noise three-demensional motion can be obtained exactly by a linear algorithm except in the special case in which the surface of the object is on a general quadratic surface passing through the viewpoint, and the normal vector of the surface at the viewpoint is perpendicular to the translation velocity vector. In the presence of noise, an evaluation function is introduced based on the least squares method. It is shown, however, that the solution which minimizes the evaluation function is not always optimal due to statistical bias. To deal with this problem, a method to eliminate the statistical bias in the evaluation function is proposed for zero mean white noise. Once the statistical bias is eliminated, the solution of the linear algorithm coincides with the correct solution by means of expectation. In this linear algorithm, only the eigenvector corresponding to the zero eigenvalue of a 33 matrix is necessary to find the translational velocity. Once the translational velocity is obtained, the rotational velocity can be computed directly. This method is also shown to be noise resistant by computer simulation.

To derive blood flow dynamics from cineangiograms (CAG), we have developed an image processing algorithm to estimate a two-dimensional blood fiow velocity map projected on CAG. Each image area of CAG is diveded into blocks, and it is assumed that the movement of the contrast medium between two serial frames is restricted only to adjacent blocks. By this assumption, a fundamental equation" and the maximum flow constraints" are derived. The equation and constraints state the relationship between the volume of contrast medium in each block and the flow components" that are the volumes of contrast medium flowing from/to its adjacent blocks. The initial guess" that is a set of approximately obtained flow components is corrected using these relationships. The corrected flow components are then transformed into blood flow velocities, which are illustrated in the form of a needle diagram. In numerical experiments, the estimation error between the real flow velocity generated artificially and the flow velocity estimated with our algorithm was evaluated under one of the worst conditions. Although the maximum error was fairly large, the estimated flow velocity map was still acceptable for visual inspection of flow velocity pattern. We then applied our algorithm to an abdominal CAG (clinical data). The results showed flow stagnation and reverse flow in the abdominal aneurysm, which are consistent with the presence of a thrombus in the aneurysm. This algorithm may be a useful diagnostic tool in the assessment of vascular disease.

Monopulse technique is widely used for tracking radars. For tracking at a low elevation angle, a narrow beam is required in the elevation plane to reduce multipath signals such as gound reflections. In this case, an elliptical aperture is desired. We have developed an antenna with a high tracking accuracy and a high aperture efficiency which is composed of a monopulse feed and an elliptical aperture. In this paper we discuss a design of the feed through lens array with an elliptical aperture and a new monopulse feed. Evaluation test results of a production model proved validity of our design and showed good performance.

This paper proposes a scheme that offers robust extraction of target images in standard view from input facial images, in order to realize accurate and automatic identification of human faces. A standard view for target images is defined using internal facial features, i.e., the two eyes and the mouth, as steady reference points of the human face. Because reliable detection of such facial features is not an easy task in practice, the proposed scheme is characterized by a combination of two steps: first, all possible regions of facial features are extracted using a color image segmentation algorithm, then the target image is selected from among the candidates defined by tentative combination of the three reference points, through applying the classification framework using the sub-space method. Preliminary experiments on the scheme's flexibility based on subjective assessment indicate a stability of nearly 100% in consistent extraction of target images in the standard view, not only for familiar faces but also for unfamiliar faces, when the input face image roughly matches the front view. By combining this scheme for normalizing images into the standard view with an image matching technique for identification, an experimental system for identifying faces among a limited number of subjects was implemented on a commercial engineering workstation. High success rates achieved in the identification of front view face images obtained under uncontrolled conditions have objectively confirmed the potential of the scheme for accurate extraction of target images.

We are concerned with a subclass of deterministic pushdown automata (dpda) called very simple dpda's, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these dpda's. As usual, we take the maximal thickness (i.e., the length of the shortest input strings that make each stack symbol go to empry) of all stack symbols into account as one parameter of the given dpda's. Then the worst-case time complexity of our algorithm is polynomial with respect to these parameters. Without considering the thickness, the complexity is single exponential in the description length of the given dpda's. As far as we are concerned with very simple dpda's, our algorithm is very simple and direct, and is faster and much better than the previously given algorithms for the inclusion problem of dpda's.

This letter presents an algorithm named SPM which generates test patterns for single stuck-at faults in synchronous sequential circuits based on a product machine traversal method. The new idea presented in this letter is partitioned image computation combined with a mixed breadth-first/depth-first search. Image computation is carried out in partitioned manner by substituting constant logical values to some input variables. This brings about significant reduction in storage requirement during image computation. A test generator based on SPM achieved 100% fault efficiency for the ISCAS'89 benchmark circuits with not more than 32 flip-flops.

This paper describes a new algorithm for finding the contours of a moving object in an image sequence. A distinctive feature of this algorithm is its complete bottom-up strategy from image data to a consistent contour description. In our algorithm, an input image sequence is immediately converted to a complete set of quasi logical spatio-temporal measures on each pixel, which provide constraints on varying brightness. Then, candidate regions in which to localize the contour are bounded based on consistent grouping among neighboring measures. This reduces drastically the ambiguity of contour location. Finally, Some mid-level constraints on spatial and temporal smoothness of moving boundaries are invoked, and they are combined with these low-level measures in the candidate regions. This is performed efficiently by the regularization over the restricted trajectory of the moving boundary in the candidate regions. Since any quantity is dimensionless, the results are not affected by varying conditions of camera and objects. We examine the efficiency of this algorithm through several experiments on real NTSC motion pictures with dynamic background and natulal textures.

A modern architect can not design high performance computer architecture without thinking all factors of performance from hardware level (logic/layout design) to system level (application programs, operating systems, and compilers). For computer architecture design, there are few practical CAD tools, which support design activities of the architect. In this paper, we propose a CAD tool, called COACH, for computer architecture design. COACH supports architecture design from hardware level to system level. To make a high-performance general purpose computer system, the architect evaluates system performance as well as hardware level performance. To evaluate hardware level performance accurately, logic/layout synthesis tools and simulator are used for evaluation. Logic/layout synthesis tools translate the architecture design into logic circuits and layout pattern and simulator is used to get accurate information on hardware level performance which consists of clock frequency, the number of transistors, power consumption, and so on. To evaluate system level performance, a compiler generator is introducd. The compiler generator generates a compiler of a programming language from the desripition of architecture design. The designed architecture is simulated in the behavior level with programs compiled by the compiler, and the architect can get information on system level performance which consists of program execution steps, etc. From both hardware level performance and system level performance, the architect can evaluate and revise his/her architecture, considering the architecture from hardware level to system level. In this paper, we propose a new design methodology which uses () logic/layout synthesis tools and simulators as tools for architecture design and () a compiler generator for system level evaluation. COACH, a CAD system based on the methodology, is discussed and a prototype of COACH is implemented. Using the design methodology, two processors are designed. The result of the designs shows that the proposed design methodology are effective in architecture design.

The size and weight of marine pulse radar systems must be limited in order to mount them on board boats. However, the azimuthal resolution of a marine radar with a small antenna is degraded by the antenna beam width. It is desirable to use signal processing techniques to increase both the azimuthal resolution and the range resolution of such systems without changing their external configuration. This paper introduces a resolution enhancement method based on deconvolution, which is a kind of inversion. The frequency domain deconvolution method is described first. The effectiveness of the proposed method is shown by simulation. Then, an example of resolution enhancement processing is applied to a pulse radar. The results of practical experiments show that this method is a promising way of upgrading radars by simply processing the received signals.

String grammars (languages) have been extensively studied from 60's. On the other hand, the transformational grammar, proposed by Chomsky, contains the transformation from the set of derivation trees of context-free language to the surface set. And the grammar regarded a tree as an input sentence to some transducer. After that from latter half of 60's, the studies of acceptor, transducer, and so on, whose input is a tree, have been done extensively. In this paper we propose, as a model, a new type of transducer which translates trees into trees and investigate its fundamental properties. The model proposed here is the pushdown tree transducer (for shortly PDTT) that is an extension of the finite state tree transducer discussed by J. W. Thacher, W. C. Rounds, J. Engelfriet, and so on. The main subjects discussed here (we consider only top-down case (t-PDTT)), are as follows: (1) final state t-PDTT translation is equivalent to empty stack t-PDTT translation and vice versa, (2) for any t-PDTT, a single state t-PDTT which is equivalent to it always exists, (3) as a standard form the symmetric stack form t-PDTT is proposed and based on this, it is shown that any single state t-PDTT can be always converted into a linear stack t-PDTT, and so on.

For each two positive integers r, s, let [1DCM(r)-Time(ns)] ([1NCM(r)-Time(ns)]) and [1DCM(r)-Space(ns)] ([1NCM(r)-Space(ns)]) be the classes of languages accepted in time ns and in space ns, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X{D, N}, [1XCM(r)-Time(ns)][1XCM(r+1)-Time(ns)] and [1XCM(r)-Space(ns)][1XCM(r+1)-Space(ns)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.

A multi-beam airborne pulsed-Doppler radar (MBR) system is presented and its clutter rejection performance compared with conventional phased array radar (PAR)'s by PRF tuning is discussed. The pulsed-Doppler radar equations taking account of the multi-beam operation are introduced and some kinds of computer simulations for seeking the conditions to get maximum signal to clutter ratio are carried out. As a results of this, it is cleared that same order of signal to clutter ratio improvement gotten in high PRF operation by conventional PAR can be realized at lower PRF operation by MBR on clutter free area, and higher clutter rejection effect, which is proportional to beam numbers, is obtained under affection of both of mainlobe and sidelobe clutters with order of beam numbers. This also means observable numbers of range bin are increased in MBR operation.

A global routing problem is formulated as a multi-commodity network flow problem. The formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew perfomances by using the goal programming method. An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of procassing time for both problems is about 90 minutes on a mainframe computer.

This article discusses on PDM (Petri net based Development Methodology) which integrates approaches, modeling methods, design methods and analysis methods in a coherent manner. Although various development techniques based on Petri nets have demonstrated advantages over conventional techniques, those techniques are rather ad hoc and lack an overall picture on entire development process. PDM anticipates to provide a refernce process model to develop distributed systems with various Petri net based development methods. Behavioral properties of distrbuted systems can be an appropriate application domain of PDM.

Full scan design of sequential circuits results in greatly reducing the cost of their test generation. However, it introduces the extra expense of many test clocks to control and observe the values of flip-flops because of the need to shift values for the flip-flops into the scan panh. In this paper we propose a new method of generating compact test sequences for scan-based sequential circuits on the assumption that the number of shift clocks is allowed to vary for each test vector. The method is based on Boolean function manipulation using a shared binary decision diagram (SBDD). Although the test generation algorithm is basically for general sequential circuits, the computational cost is much lower for scan-based sequential circuits than for non-scanbased sequential circuits because the length of a test sequence for each fault is limited. Experimental results show that, for all the tested circuits, test sequences generated by the method require much smaller number of test clocks than compact or minimum test sets for combinational logic part of scan-based sequential circuits. The reduction rate was 48% on the average in the experiments.

We derive the eigenvalue constraint for a neural network with three degrees of freedom. The result implies that the neural network needs a neuron with variable output function to generate chaos. It is also shown that the neuron with the special characteristics can be constructed by ordinary neurons.

This paper describes the hierarchical behavioral description language celled SFL and its processing system. This integrated CAD system called PARTHENON is used for designs of the leading ASICs in the NTT Systems Labs. This paper shows, therefore, the effectiveness of PARTHENON as a practical high-lelel synthesis system through real design experience. SFL was developed to aid in the design of the hardware functions and behaviors of ASICs composed solely of clocksynchronized circuits. The main features of SFL are as follows: (1) It is not mixed with connection description, but employs only behavioral description (like procedual description in program language), and it provides hierarchical expression of behavioral description. (2) It permits the description of parallel processing operations by adopting a new hardware task concept. And, (3) it is linked with the behavioral simulator, logic synthesizer, and other components of the processing system. After describing SFL in some detail, a brief explanation of its synthesizer and other processing components is provided, along with its application results in the real design of some leading ASICs at the NTT Systems Laboratories.

This paper shows that coherent optimization strategies for multilevel systhesis should rely on a good link between the factorization, the technology mapping and the netlist optimization. Factorization options are shown to play a key role. The technology mapping should optimize both area and critical path and only netlist structure preserving" optimization techniques (buffer insertion, gate replication) should be applied first to preserve the factorization decision. Only in a last step resynthesis of critical areas based on a local view is applied. The approach has been experimented on a set of large combinational benchmarks.

We introduce automatic procedures for generating and verifying sufficient correctness properties of synchronous processors. The targeted circuits are synchronous array processors designed from localized, highly regular data dependency graphs (DDGs). The specification, in the form of a DDG, is viewed as a maximally parallel circuit. The implementation, on the other hand, is a (partially) serialized circuit. Since these circuits are not equivalent from an automata-theoretic viewpoint, we define the correctness of the implementation against the specification to mean that a certain relation (called the β-relation) holds between the two. We use a compositional approach to decouple the verification of the control circuitry from that of the data path, thereby gaining efficiency. An array processor in isolation may not have a definite flow of control, because control may reside in the data stream. Therefore, for the purpose of verification, we construct an auxiliary machine, which keeps a timing reference and generates control signals abstracted from a typical data stream. Sufficient correctness conditions are expressed as past-tense computation tree logic (CTL) formulae and verified by CTL model-checking procedures. Experimental results of the verification of a matrix multiplication array and a Gaussian elimination array are presented.