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.

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.

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.

Evolution programs have been shown to be very useful in a variety of search and optimization problems, however, until now, there has been little attempt to apply evolution programs to channel routing problem. In this paper, we present an exolution program and identify the key points which are essential to successfully applying evolution programs to channel routing problem. We also indicate how integrating heuristic information related to the problem under consideration helps in convergence on final solutions and illustrate the validity of out approach by providing experimental results obtained for the benchmark tests. compared with the optimal solutions.

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.

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.

As RAMs become dense, their reliability reduces because of complex interactions between memory cells and soft errors due to alpha particle radiations. In order to rectify this problem, RAM manufacturers have started incorporating on-chip (built-in) ECC. In order to minimize the area overhead of on-chip ECC, the same technology is used for implementing the check bits and the information bits. Thus the check bits are exposed to the same failure modes as the information bits. Furthermore, faults in the check bits will manifest as uncorrectable multiple errors when a soft error occurs. Therefore it is important to test the check bits for all failure modes expected of other cells. In this paper, we formulate the problem of testing RAMs with on-chip ECC capability. We than derive necessary and sufficient conditions for testing the check bits for arbitrary and adjacent neighborhood pattern sensitive faults. We also provide an efficient solution to test a memory array of N bits (including check bits) for 5-cell neighborhood pattern sensitive faults in O (N) reads and writes, with the check bits also tested for the same fault classes as the information bits.

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.

This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.

We present an extension of the previously proposed 3-layer feedforward network called a cascaded network. Cascaded networks are trained to realize category classification employing binary input vectors and locally represented binary target output vectors. To realize a nonlinearly separable task the extended cascaded network presented here is consreucted by introducing high order cross producted inputs at the input layer. In the construction of the cascaded network, two 2-layer networks are first trained independently by delta rule and then cascaded. After cascading, the intermediate layer can be understood as a hidden layer which is trained to attain preassigned saturated outputs in response to the training set. In a cascaded network trained to categorize binary image patterns, saturation of hidden outputs reduces the effect of corrupted disturbances presented in the input. We demonstrated that the extended cascaded network was able to realize a nonlinearly separable task and yielded better generalization ability than the Backpropagation network.

A hardware accelerator for a raster-based design-rule checking called BITDRC for a bit-mapping CAD system is described. BITDRC is a special-purpose hardware accelerator which performs design-rule checking for the Manhattan layout style VLSI circuis, much faster than the software checking which belonged to the bit-mapping CAD system before. The bit-mapping CAD system had effectively been developed for both of educational and VLSI design purposes, and just needs only a personal computer as a compact working environment. The proposed hardware architecture is rather simply and characterized by the bit-mapping CAD system where it works on. The hardware architecture and checking algorithm have been confirmed by implementing a bread-board prototype using discrete components. As a result, the processing time of BITDRC is speeded up as much as 500 times faster than the original software and takes only 4 seconds for checking every rule on a(15001500) grids layout pattern. BITDRC performs the error checking together with the data scanning that makes it can be as an on-line design-rule checker for the bit-mapping CAD system. Finally, the physical layout of BITDRC has been designed using a conventional CMOS technology.

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.

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 coherent communication system using squeezed light is one of candidates for a realization of super-reliable systems. In order to design such a system, it is essential to understand and to analyze modulators mathematically. However, quantum noise of squeezed light has a colored spectrum which changes with respect to phase of a local laser. Therefore the optimization of the relationship between signal and quantum noise spectrums is required at a modulator to obtain the ultimate performance of the communication system. In this paper, some ideas of modulators for squeezed light are proposed and their spectrum transformations are given. After the brief summary of squeezed quantum noise, a new concept which originates from the restriction of the local laser phase is applied to it. This concept makes a problem originated from a colored quantum noise spectrum more serious. It results in the optimization problem for the relationship between the quantum noise spectrum and signal power spectrum. The solution of this problem is also given under the restriction of local laser phase. As a result, a general design theory for coherent communication system using the squeezed light is given.

Since the time required for testing logic circuits is proportional to the number of test vectors, the size of test sets as well as test generation time is one of the most important factors to be considered in test generation. The size of test sets becomes an essential issue, especially for scan designed circuits, because of the need to shift a test vector serially into the scan path. In this paper, we propose new methods of generating compact test sets to detect al the irredundant single stuck-at faults in combinational circuits. The proposed algorithms calculate a test function for each fault which corresponds to the set of all test vectors for the fault and generate a compact test set by analyzing the test functions. The analysis is based on finding a test vector which detects the largest number of remaining faults. Since our methods select a test vector among all the test vectors, represented by a test function, for a target fault, smaller test sets can be generated, in general, than that by conventional test set compaction methods. The experimental results show that the size of test sets generated by our method is about one-third as large as that without compaction.

Fiber-optic microcellular system has been studied actively as an excellent system for solving the equipment cost problems in microcellular systems. However, the occurrence of intermodulation distortion (IMD) arising from the nonlinearity of the laser diode used for E/O conversion which degrades the transmission quality is a serious problem in this system. In this paper, we propose a new frequency switching/IM3 reduction method, which dynamically reassigns the carrier frequencies to minimize the carrier to IMD power ratio under the hostile environment with time-varying received carrier strength, and analyze the performance improvements by the proposed method. The improvements obtained both for the worst value of the overall CNR and for the overall CNR in a specific user are numerically made clear. It is also shown that if the interval between frequency reassignings is set less than one second, a sufficient improvement in the overall CNR is achievable.

Reducing communication complexity is a viable approach to multilevel logic synthesis. A communication complexity based approach was proposed previously. In the previous works, only disjoint input decomposition was considered. However, for certain types of circuits, the circuit size can be reduced by using overlapped decomposition. In this paper, we consider overlapped decompositions. Some design issues for overlapped decompositions such as detecting globals" and deriving subfunctions are addressed. Moreover, the Decomposition Don't Cares (DDC) is considered for improving the decomposed results. By using these techniques together, the area and delay of circuits can be further minimized.

In this paper, a new method of synthesizing multi-level logic circuits directly from binary decision diagrams (BDDs) is proposed. In the simple multiplexer implementation, the depth of the synthesized circuit was always O (n), where n is the number of input variables. The new synthesis method attempts to reduce the depth of circuits. The depth of the synthesized circuits is O (log n log w) where w is the maximum width of given BDDs. The synthesized circuits are 2-rail-input 2-rail-output logic circuits. The circuits have good testability; it is proved that the circuits are robustly path-delay fault testable and also totally self-checking for single stuck-at faults.

Acceleration techniques have been incorporated into the generalized method of characteristics (GMC) to perform transient analysis of uniform transmission lines, for the special case when the transmission lines are driven by digital signals. These techinques have been proved to improve the simulation speed to a great extent when the analysis is carried out using iterative waveform relaxation method. It has been identified that the load impedance connected to the transmission line has a bearing on the efficiency of one of these acceleration techniques. Examples of an RLCG line terminated with linear loads as well as nonlinear loads are given to illustrate the advantage of incorporating these acceleration techniques.