Saed SAMADI Akinori NISHIHARA Nobuo FUJII
In practical applications of digital filters it is more realistic to treat multiplier coefficients as finite intervals than restricting them to infinite or very long word-length representations. However, this can not be done it the frequency response performance under interval assumption is difficult to analyze. In this paper, it is proved that stable lattice allpass filters possess bounded continuous phase response when lattice parameters vary in bounded intervals. It is shown that sharp bounds on the interval phase response can be computed easily at an arbitrary frequency using a simple recursive procedure. Application of this property to the problem of finite word-length lattice allpass filter design is also discussed. By formulating this problem as an interval design it is possible to solve it efficiently independent of the number system used to represent multiplier coefficients.
Recently, a flexible image database retrieval system where image keywords can be captured automatically is strongly required, in order to manage a practical number of image data successfully. However, image recognition/understanding technology level is not generally sufficient enough to achieve this requirement. In order to overcome this problem, a new type of image database framework is proposed in this paper. In the proposed system, image keywords are extracted in fully-automated fashion by the flexible and generalized image recognition system. Image keywords employed in this system are a collection of recognized objects in the image, where achieved recognition levels are allowed to be intermediate or imperfect. The concept of recognition thesaurus" has been introduced to manage these various abstraction level of kerwords successfully. As an embodiment of this concept, an experimental image database with various types of sports scenes has been implemented and various retrieval evaluations have been performed. Experimental results reveal the effectiveness of the proposed method.
Mario G. FROMOW RANGEL Akira NOGUCHI
The inverse problem we consider in this paper seeks, based on the equivalent source method, to determine the shape of perfectly conducting cylinders from the scattered farfield data obtained by using several incident waves. When incident waves of different frequencies are used, the shape of the scatterer can be reconstructed by employing only a few number of observation points. In the reconstruction problem, to determine the shape of the scatterer, the conjugate gradients method is applied. The general approach is applicable to cylindrical scatterers of arbitrary shape. Results of numerical simulations are presented to support the suggested approach.
Mitsuo WAKATSUKI Etsuji TOMITA
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.
Hiroaki YAMAMOTO Takashi MIYAZAKI
There have been several studies related to a reduction of the amount of computational resources used by Turing machines. As consequences, linear speed-up theorem" tape compression theorem", and reversal reduction theorem" have been obtained. In this paper, we consider reversal- and leaf-bounded alternating Turing machines, and then show that the number of leaves can be reduced by a constant factor without increasing the number of reversals. Thus our results say that a constant factor on the leaf complexity does not affect the power of reversal- and leaf-bounded alternating Turing machines
As a new method to generate a homogeneous, random, binary image with a rational power spectrum, this paper proposes a discrete-valued auto-regressive equation, of which random coefficients and white noise excitation are all discrete-valued. The average and spectrum of the binary image are explicitly obtained in terms of the random coefficients. Some computer results are illustrated in figures.
Tomohiko OHTSUKA Nobuyuki KUROSAWA Hiroaki KUNIEDA
The paper presents the improvement of out new approach to optimize the process parameter variation, device heat and wire parasitics for analog LSI design by explicitly incorporating various performance estimations into objective functions for placement and routing. To minimize these objective functions, the placement by the simulated annealing method, and maze routing are effectively modified with the perfomance estimation. The improvement results in the excellent performance driven layout for the large size of analog LSIs.
Mototaka KURIBAYASHI Masaaki YAMADA Takashi MITSUHASHI Nobuyuki GOTO
A fast and efficient heuristic hierarchical global router for Sea-of-Gates(SOG) with embedded macro-blocks is described. The key point in the method is carry out a new optimal domain decomposition scheduling at every hierarchical level. This scheduling is intended to avoid macro-block-through wirings and to reduce wiring congestion near macro-blocks which may occur at lower levels. The new global router yielded superior results compared with previous hierarchical routers and a non-hierarchical maze router by evaluating with several actual SOG circuits including a 300K gate master chip and benchmark data supplied from MCNC. Overflows were reduced to one-half or one-quarter for macro-block embedded data compared with previous hierarchical routers. Concerning the running time, the router remarkably outperformed the non-hierarchical maze router, which took more than 390 times longer time for the tested large data.
Ikuo ARAI Kazuma MOTOMURA Tsutomu SUZUKI
A method to measure the displacement from the phase rotation of the Doppler signal including the displacement information of the moving body is proposed, where the displacement resolution can be improved 4 times by making the phase rotation faster. Furthermore, this test system is applied in clinical use. The test system is built up by using a two-phase microwave Doppler sensor covering a 10GHz band, where the Doppler frequency is multiplied 4 times by signal processing. Thus, the resolution is improved from a conventional 12.6mm (in case of 11.9GHz) to 3.15mm, and practical utilization has been attained. The microwave Doppler radar system described in this paper is adequate for the displacement measurement for a relatively fast moving body. As a medical sensor for clinical use, measurement examples of head movement in a vestibule examination (vestibule oculomotor reflexive inspection) and finger movement in a cerebellum function test are given. Furthermore by using two sets of this Doppler radar system, a 2-dimensional measurement of head movement is possible.
Hoyong CHOI Hironori MAEDA Takashi KOHARA Nagisa ISHIURA Isao SHIRAKAWA Akira MOTOHARA
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.
Weibull-distributed clutter are reviewed. Most of the clutter received by L, S, C, X and Ku band radars obey Weibull distribution. Clutter suppression techniques for Weibull clutter are also reviewed. Especially, the generalized Weibull CFAR detector is emphasized. The approch is to estimate the shape and scale parameters of the Weibull clutter using order statistics and then use them in the detector. The generalized CFAR detector transforms the Weibull clutter distribution into a normalized exponential distribution. When a target is present, the transformation produces a large error that can be used to detect the target. Actual data taken by a Ku band radar are used to compare the proposed method with another method to estimate the Weibull parameters and with the Weibull CFAR detector. Order statistics estimation requires a small number of samples and can be used to find the local value of Weibull clutter parameters and, thus, the proposed method requires less computational time to find the Weibull parameters.
Tomohiro MURATA Kenzou KURIHARA Ayako ASHIDA
Reactive systems respond to internal or external stimuli and act in an event-driven manner. It is generally difficult to specify a complex reactive systems' behavior using conventional state machine formalism. One reason is that actual reactive systems are usually formed by combining plural state-machince that behave concurretly. This paper presents the State Diagram Matrix (SDM) which is a visual and hierarchical formalism of such a reactive system's behavior. SDM has two concepts. The first is matrix plane description on which 3-dimensional state space is projected. The second is state abstraction for hierarchical state-machine definition. Understandability and reliability of control software was improved as a consequence of adopting SDM for specifying disk-subsystem control requirements. The development support functions of SDM using a workstation are also described.
Yasuharu JIN Yuichiro GOTO Yoshiro NISHIMOTO Hiroyuki NAITO Akio IWAKE
As in other fields, the automatization of railway maintenance work is a firm requirement. The authors have developed a system detecting obstacles around a railway for practical railway inspection. The system is based on an original laser-sectioning method and characterized by high accuracy with wide view and in-motion operation. It was confirmed that a static calibration was performed at an accuracy of within 5 mm. Furthermore, a theoretical estimation predicted that dynamic errors can be eliminated within a resolution of 4 mm by means of rail movement detection. In field tests on the Chuo Line, facilities were successfully inspected at speeds up to 40km/h.
Yoichi SHIRAISHI Jun'ya SAKEMI Kazuyuki FUKUDA
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.
Saburo ADACHI Toru UNO Tsutomu NAKAKI
This paper discusses methods and numerical simulations of one and two dimensional profilings for an arbitrary convex conducting target using the electromagnetic backscattering. The inversions for profile reconstructions are based upon the modified extended physical optics method (EPO). The modified EPO method assumes the modified physical optics current properly over the entire surface of conducting scatterers. First, the cross sectional area along a line of sight is reconstructed by performing iteratively the Fourier transform of the backscattering field in the frequency domain. Second, the two dimensional profile is reconstructed by synthesizing the above one dimensional results for several incident angles. Numerical simulation results of the target profiling are shown for spheroids and cone-spheroid.
Toshio WAKAYAMA Toru SATO Iwane KIMURA
Radar imaging technique is one of the most powerful tool for underground detection. However, performance of conventional methods is not sufficiently high when the observational direction or the aperture size is restricted. In the present paper, an image reconstruction method based on a model fitting with nonlinear least-squares has been developed, which is applicable to arbitrarily arranged arrays. Reconstruction is executed on the assumption that targets consist of discrete point scatterers embedded in a homogeneous medium. Model fitting is iterated as the number of point target in the assumed model is increased, until the residual in fitting becomes unchanged or small enough. A penalty function is used in nonlinear least-squares to make the algorithm stable. Fundamental characteristics of the method revealed with computer simulation are described. This method focuses a much sharper image than that obtained by the conventional aperture synthesis technique.
Shinichiro OHNUKI Tsuneki YAMASAKI Takashi HINATA
The transient scattering of a half sine pulse wave by a conducting rectangular cylinder with an open sidewall is rigorously analyzed by using the point matching method (taking into account the edge condition exactly) combined with the fast inversion of Laplace transform. Numerical results are presented for back scattered and forward scattered responses of the far fields when a half sine pulse is incident on the open side and the closed side of the cylinder. The physical meaning of the transient responses is discussed in detail. The comparison of the responses with those by a perfect conducting rectangular cylinder is presented.
This letter presents a new method for adaptive control of nonminimum phase discrete-time systems with disturbances based on the technique of pole-zero placement. The long division method is used to decompose apolynomial into a stable polynomial and an unstable one. Finally, the results of computer simulation are presented to illustrate the effectiveness of the proposed method.
Mitsuru TANAKA Atsushi KUSUNOKI
Scattering characteristics of a stratified chiral slab, which is composed of dielectric chiral layers of different material properties and thicknesses, are extensively explored. Design considerations for optical filters are also presented for both the cases of normal and oblique incidence. In the analysis, the incident field is assumed to be a plane monochromatic wave of any arbitrary polarization. The transmitted and reflected electric fields are obtained by noting the fact that the electric field inside a chiral medium is expressed as a sum of the left- and right-circularly polarized plane waves of different phase velocities. Then one can describe the power densities and the Stokes parameters of the transmitted and reflected waves in terms of their field components. As is well known,the Stokes parameters characterize every possible state of polarization of a plane wave. Numerical examples are presented to show the effects of chirality on polarization conversion properties of the stratified chiral slab. The cross- and co-polarized powers and the Stokes parameters of the transmitted and reflected waves are computed for the incident wave of perpendicular polarization. The numerical results demonstrate novel depolarization properties of the slab with application to the design of efficient filters active at the optical region. It is seen from the results that the stratified chiral slab acts as a polarization-conversion transmission filter that passes only a cross-polarized component of the transmitted wave at some frequency band. Furthermore, the slab may be utilized as an antireflection filter for both the cross- and co-po1arized components of the reflected wave at the band region.