In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circit is presented. So far several heuristic algorithms for this problem are proposed, but no efficient exact algorithms are known. To solve this exactly, minimum test set problem is formalized as a minimum set covering problem, and then implicit manipulation technique using binary decision diagrams(BDDs) is applied. The algorithm presented in the paper has two contributions. One is utilization of maximal compatible fault set, which can drastically reduce the number of candidates for minimum test set. A new BDD based algorithm for extracting all maximal compatible fault sets is shown. The other is a new implicit manipulation technique handling with huge covering matrix. Actually, the algorithm using this technique can handle minimum set covrering problem with over ten thousand columns in a few minutes. Experiments using ISCAS benchmark circuits show that the algorithm is quite efficient for small(100-300 gates) circuits. A computational complexith of minimum test set problen is much higher than that of ordinary test pattern generation problem, so that practical signifcance of this method is not high. But the algorithm is still useful for evaluation of other heuristic algorithms. furthermore, this implicit manipulation technique can also be applied to other minimumset covering problems.

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.

Recently, there has been a lot of research on solving combinatorial problems using Binary Decision Diagrams (BDDs), which are very efficient representations of Boolean functions. We have already developed a Boolean Expression Manipulator, which calculates and reduces Boolean expressions quickly based on BDD techniques. This greatly aids our works on developing VLSI CAD systems and solving combinatorial problems. Any combinatorial problem can be described in Boolean expressions; however, arithmetic operations, such as addition, subraction, multiplication, equality and inequality, are also used for describing many practical problems. Arithmetic operations provide simple descriptions of problems in many cases. In this paper, we present an arithmetic Boolean expression manipulator (BEM-), based on BDD techniques. BEM- calculates Boolean expressions containing arithmetic operations and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with using 0-1 linear programming. We show the efficient data structure based on BDD representation, algorihms for manipulating Boolean expressions with arithmetic operations, and good formats for displaying the results. Finally we present the specification of BEM- and an example of application to the 8-Queens problem. BEM- is customizable to various applicationa. It has good computation performance in terms of the total time for programming and execution. We expect BEM- to be a helpful tool in research and development on digital systems.

This paper presents a new method to derive the phase difference between n-tuples of an m-sequence over GF(p) of period pn-1. For the binary m-sequence of the characteristic polynomial f(x)=xn+xd+1 with d=1,2c or n-2c, the explicit formulas of the phase difference from the initial n-tuple are efficiently derived by our method for specific n-tuples such as that consisting of all 1's and that cosisting of one 1 and n-1 0's, although the previously known formula exists only for that consisting of all 1's.

The character binarization method MTC is developed for enhancing the recognition of characters in general outdoor images. Such recognition is traditionally difficult because of the influence of illumination changes, especially strong shadow, and also changes in character, such as apparent character sizes. One way to overcome such difficulties is to restrict objects to be processed by using strong hypotheses, such as type of object, object orientation and distance. Several systems for automatic license plate reading are being developed using such strong hypotheses. However. their strong assumptions limit their applications and complicate the extension of the systems. The MTC method assumes the most reasonable hypotheses possible for characters: they occupy plane areas, consist of narrow lines, and external shadow is considerably larger than character lines. The first step is to eliminate the effect of local brightness changes by enhancing feature including characters. This is achieved by applying mathematical morphology by using a logarithmic function. The enhanced gray-scale image is then binarized. Accurate binarization is achieved because local thresholds are determined from the edges detected in the image. The MTC method yields stable binary results under illumination changes, and, consequently, ensures high character reading rates. This is confirmed with a large number of images collected under a wide variety of weather conditions. It is also shown experimentally that MTC permits stable recognition rate even if the characters vary in size.

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.

In this paper, we show that Petri nets can be applied practically to design and analysis of concurrent, parallel and embedded mode systems such as a lift system that is familiar to our daily life. Modeling behavioral characteristics of the lift, we extend a standard Petri net by constant timed transition, faultable transition, stochastic transition and condition transition concepts. Likewise, we prsesnt some results of design and analysis of the system. This method can be applied to design and analysis of another concurrent systems.

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.

The discrete time analysis of logic circuits is usually more efficient than the continuous time analysis, but the preciseness of the discrete time analysis is not guaranteed. The paper shows a method to decide a unit time for a logic circuit under which the analysis result is the same as the result based on the continuous time. The delay time of an element is specified with an interval between the minimum and maximum delay times, and we assume an analysis method which enumerates all possible delay cases under the deisrete time. Our main theorem is as follows: refine the unit time by a factor of 1/2, and if the analysis result with a unit time u and that with a unit time u/2 are the same, then u is the expected unit time.

In this paper, we will clarify the problem of consecutively lost customer due to buffer overflow in an IPP, M/M/l/K queueing system including an M1, M2/M/l/K queueuing system as a special case. We define a length of a consecutive loss as the number of customers consecutively lost due to buffer overflow. And, we obtain individual distributions of the lengths of consecutive losses for the IPP- and Markov-sources. From analytical and numerical results, it is shown that either they are geometrical or they can be approximated by a geometric distribution. Also, from numerical examples, we show some properties of the length of consecutive customer loss.

When orignal signals are contaminated by both additive and signal-dependent noise components, the test statistics of locally optimum detector are obtained for detection of weak composite signals based on the generalized Neyman-Pearson lemma. In order to consider the non-additive noise as well as purely-additive noise, a generalized observation model is used in this paper. The locally optimum detector test statisics are derived for all different cases according to the relative strengths of the known signal, random signal, and signal-dependent noise components. Schematic diagrams of the structures of the locally optimum detector are also included. The finite sample-size performance characteristics of the locally optimum detector are compared with those of other common detectors.

High speed simulation of neural networks can be achieved through parallel implementations capable of exploiting their massive inherent parallelism. In this paper, we show how this inherent parallelism can be effectively exploited on parallel data-driven systems. By using these systems, the asynchronous parallelism of neural networks can be naturally specified by the functional data-driven programs, and maximally exploited by pipelined and scalable data-driven processors. We shall demonstrate the suitability of data-driven systems for the parallel simulation of neural networks through a parallel implementation of the widely used back propagation networks. The implementation is based on the exploitation of the network and training set parallelisms inherent in these networks, and is evaluated using an image data compression network.

One of the most interesting and most analyzed aspects of the CPU design is the instruction set design. How many and which operations to be provided by hardware is one of the most fundamental issues relaing to the instruction set design. This paper describes a novel method that formulates the instruction set design of ASIP (an Application Specific Integrated Processor) using a combinatorial appoach. Starting with the whole set of all possible candidata instructions that represesnt a given application domain, this approach selects a subset that maximizes the performance under the constraints of chip area, power consumption, and functional module sharing relation among operations. This leads to the efficient implementation of the selected instructions. A branch-and-bound algorithm is used to solve this combinatorial optimization problem. This approach selects the most important instructions for a given application as well as optimizing the hardware resources that implement the selected instructions. This approach also enables designers to predict the perfomance of their design before implementing them, which is a quite important feature for producing a quality design in reasonable time.

Since, in a VLSI circuit, the number of transistors and the clock frequency are constantly increasing, it is important to analyze the voltage drop and current density on a full chip's power networks. We propose a new hierarchical power analysis system named XPOWER. A new reduction algorithm for the resistance and current source network is used in this system. The algorithm utilizes the design hierarchy in nature and is independent of network topology. Networks at each level are reduced into small and equivalent networks, and this reduction is performed recursively from the bottom levels of the design hierarchy. At each step of the reduction, the network under consideration consists of two kinds of objects: (1) reduced child networks, and (2) the interconnection between child networks. After all networks have been reduced, circuit equationa are solved recursively from the top. This allows to decrease the size of the matrix to be solved and to reduce the execution time. Experimental results show that the factor of reduction in matrix size is from 1/10 to 1/40 and execution is six times faster than with flat analysis. The power networks of a 16 bit digital signal processor was analyzed within 15 minutes using XPOWER.

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.

This paper proposes a new method for automatic improvement in image quality through adjusting the image sharpness. This method does not need prior knowledge about image blur. To improve image quality, the sharpness must be adjusted to an optimal value. This paper shows a new method to evaluate sharpness without MTF. It is considered that the human visual system judges image sharpness mainly based upon edge area features. Therefore, attention is paid to the high spatial frequency components in the edge area. The value is defined by the average intensity of the high spatial fequency components in the edge area. This is called the image edge sharpness" value. Using several images, edge sharpness values are compared with experimental results for subjective sharpness. According to the experiments, the calculated edge sharpness values show a good linear relation with subjective sharpness. Subjective image sharpness does not have a monotonic relation with subjective image quality. If the edge sharpness value is in a particular range, the image quality is judged to be good. According to the subjective experiments, an optimal edge sharpness value for image quality was obtained. This paper also shows an algorithm to alter an image into one which has another edge sharpness value. By altering the image, which achieves optimal edge sharpness using this algorithm, image sharpness can be optimally adjusted automatically. This new image improving method was applied to several images obtained by scanning photographs. The experimental results were quite good.

This paper describes a new single-unit underground radar for detecting underground buried pipes. The pipe depth can be calculated from the hyperbolic shape in the cross-sectional image of radar echoes. The edge contour of the image is extracted, and the buried depth is judged from the similarity between the extracted hyperbolic curve and the theoretical curve. A suitable amplification rate is estimated by choosing the best image from numerous cross-sectional images formed during one antenna movement repeated at different amplification rates. The best image has few pixels corresponding to weak and saturated signals. The new radar is very compact, so it can be operated by one person. Objects buried up to 2.0m deep can be detected.

An efficient algorithm is presented for finding all solutions of piecewise-linear resistive circuits. In this algorithm, a simple sign test is performed to eliminate many linear regions that do not contain a solution. Therefore, the number of simultaneous linear equations to be solved is substantially decreased. This test, in its original form, requires O(Ln2) additions and comparisons in the worst case, where n is the number of variables and L is the number of linear regions. In this paper, an effective technique is proposed that reduces the computational complexity of the sign test to O(Ln). Some numerical examples are given, and it is shown that all solutions can be computed very efficiently. The proposed algorithm is simple and can be easily programmed by using recursive functions.

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.

A cylindrical active phased array antenna was developed. A primary surveillance radar (PSR) antenna and a secondary surveillance radar (SSR) antenna are integrated conformally. The PSR antenna employs two-dimensional electronic beam scanning. The SSR antenna employs electronic beam scanning in azimuth. Advantages of this antenna, design architecture employed and measured characteristics are described.