A new technology mapping algorithm is developed on a general model of FPGA with composite logic block architectures, consisting of different sizes of look-up tables (LUTs) and possibly different logic gates. In additions, the logic blocks may have hard-wired connections and limit accessible fanouts. Xilinx XC4000 is one example containing LUTs of different sizes and AT&T ORCA is another example containing both LUTs and logic gates. We use a multiple-fanout pattern graph library to model the composite logic block and a premapping technique to generate the subject graph dynamically. A new matching algorithm and a new covering algorithm are also developed for the subject graph covering. The experimental results show that our algorithm is an effective technology mapper for FPGAs with composite logic block architectures, especially for larger circuits. Over a set of MCNC benchmarks, our algorithm requires on the average 4.25% fewer CLBs than PPR, 6.79% fewer CLBs than TEMPT, and 2,79% fewer CLBs than ASYL when used as the XC4000 mapper. Over a set of larger benchmarks, our algorithm outperforms PPR by 13.70%. Very encouraging results were obtained when our algorithm is used as an ORCA mapper, while there was no prior published results.

This paper presents a new timing-driven global routing method for standard cell layout. The proposed method can explicitly consider the timing constraint between two registers and minimize the channel density under the given timing constraint. In the proposed method, first, we determine the initial global routes. Next, we improve the global routes to satisfy the timing constraint between two registers as well as to minimize the channel density. Finally, for each cell row, the nets incident to terminals on the cell row are assigned to channels to minimize the channel density using 0-1 integer linear programming. We also show the experimental results of the proposed method implemented on an engineering workstation. Experimental results show that the proposed method is quite promising.

In order to apply formal design verification, it is necessary to describe formally and correctly the specification of the circuit under verification. Especially when we apply conventional OBDD-based logic comparison method for verifying combinational circuits, another correct" logic circuits or Boolean formulae must be given as the specification. It is desired to develop an efficient automatic design verification method which interprets specification that can be described easier. This paper provides a new verification method which is useful for combinational circuits such as arithmetic circuits. The proposed method efficiently verifies whether a designed circuit satisfies a specification given by recurrence equations. This enables us to describe easily an error-free specification for arithmetic circuits. To perform verification efficiently using an ordinary OBDD package, an efficient truth-value rotation algorithm is developed. The truthvalue rotation algorithm efficiently generates an OBDD representing f(x + 1 (mod 2n)) from a given OBDD representing f(x). By experiments on SPARC station 10 model 51, it takes 180 secs to generate an OBDD for designed circuit of 23-bit square function, and additional 60 secs is sufficient to finish verifying that it satisfies the specification given by recurrence equations.

In forthcoming multimedia environments, continuous-media data, such as video and audio data, will be used by a variety of multimedia applications. Multimedia applications require efficient and flexible support from real-time operating systems. This is because the changes in system and network loads require dynamic management of real-time thread behavior. If threads are implemented at the user level, operations on threads can be processed at the user level, and the efficient management of threads becomes possible by avoiding kernel interventions. Thus, we can provide an effective platform for multimedia applications. The goal of our work is to realize high-performance user-level real-time threads which satisfy the above requirements of multimedia systems. In this paper we describe the design and implementation of a user-level real-time threads package, called RTC-Threads, which is being developed on the RT-Mach microkernel. The results of performance evaluations show that our user-level real-time threads outperform real-time kernel-provided threads, which are implemented in the microkernel, in terms of efficiency and accuracy.

In this paper, we discuss problems in design and fault masking of multiple-valued cellular arrays where basic cells having simple switch functions are arranged iteratively. The stuck-at faults of switch cells are assumed to be fault models. First, we introduce a universal single-level array and derive the ratio of the number of single faults whose influence can be masked to the total number of single faults. Next, we propose a universal two-level array that outputs correct values even if single faults occur in it and derive the ratio of the number of double faults whose influence can be masked compared to the total number of double faults. By evaluating the universal single-level array and the universal two-level array from the viewpoints of design and fault masking, we show that the latter is superior to the former. Finally, we compare our universal two-level array with formerly presented arrays in order to demonstrate the advantages of our universal two-level array.

This paper verifies the accuracy of PO as applied to the scattering of dipole waves by a finite size reflector which is composed of strips on a grounded dielectric slab. By using the closed form expressions of reflected waves from the surface, PO calculation can be conducted straightforwardly. The calculated results are compared with the experimental ones for vertical and horizontal dipoles over a circular reflector.

In this paper, an extention for Haddad's method, which is the time-domain stability analysis on scalar nonlinear control systems, to multi-variable nonlinear control systems are proposed, and it is shown that these results are useful for the stability analysis of nonlinear control systems with various types of fuzzy controllers.

This paper treats a new-type power combining system of four oscillators equally coupled to one another through an eight-port hybrid. This system is marked by easy analyzability and adjustability from its symmetrical construction. In addition, a combined power from the four oscillators is distinguishably delivered to an arbitrary port of four output ports, and hence can be switched in four ways. Experimental corroboration is presented also.

This study clarifies the effects of network complexity and network map transformation on the ability of network managers to use graphic network displays. Maps of Japan and the United States with outlines of their respective prefectures or states were displayed on a CRT. Each map displayed a fictitious network of nodes and their interconnections. These networks were two-level hierarchical and non-meshed, meaning that each low-level node was connected to a single high-level node, but not all high-level nodes were linked together. The subjects, task was to identify a path between two low-level nodes. In each trial, two low-level nodes were highlighted, and the subject attempted to find the shortest path between these nodes. This was done by using a mouse to select intermediate nodes. Completing a path required a minimum of 4 node traversals. Three variables were manipulated. First, the number of nodes was defined as the total number of low-level nodes in a network (70, 150, or 200). The second variable was the level of transformation. Very densely populated areas of the maps were systematically transformed to reduce congestion. There were three levels of transformation. The final variable was the country map used, that is, the map of Japan and the map of the United States. Several behavioral measures were used. The most informativ. appeared to be the time required to complete a path (the response time), and how often subjects returned to previous portions of a path (back-ups). For both of these measures, the data pattern was essentially the same. Increasing the number of nodes hurts performance. This was particularly pronounced when the map of Japan was tested. However, as the level of transformation increased, this effect was substantially reduced or completely eliminated. The results are discussed in terms of engineering rules and guidelines for designing graphical network representations.

Unlike the time-consuming contour tracking method of snakes [5] which requires a considerable number of iterated computations before contours are successfully tracked down, we present a faster and accurate model-based landmarks" tracking method where a single iteration of the dynamic programming is sufficient to obtain a local minimum to an integral measure of the elastic and the image energy functionals. The key lies in choosing a relatively small number of salient land-marks", or features of objects, rather than their contours as a target of tracking within the image structure. The landmarks comprising singular points along the model contours are tracked down within the image structure all inside restricted search areas of 41 41 pixels whose respective locations in image structure are dictated by their locations in the model. A Manhattan distance and a template corner detection function of Singh and Shneier [7] are used as elastic energy and image energy respectively in the algorithm. A first approximation to the image contour is obtained in our method by applying the thin-plate spline transformation of Bookstein [2] using these landmarks as fixed points of the transformation which is capable of preserving a global shape information of the model including the relative configuration of landmarks and consequently surrounding contours of the model in the image structure. The actual image contours are further tracked down by applying an active edge tracker using now simplified line search segments so that individual differences persisting between the mapped model contour are substantially eliminated. We have applied our method tentatively to portraits of a class album to demonstrate the effectiveness of the method. Our experiments convincingly show that using only about 11 feature points our method provides not only a much improved computational complexity requiring only 0.94sec. in CPU time by SGI's indigo2 but also more accurate shape representations than those obtained by the snakes methods. The method is powerful in a problem domain where the model-based approach is applicable, possibly allowing real time processing because a most time consuming algorithm of corner template evaluation can be easily implemented by parallel processing firmware.

As IC fabrication technology enters a deepsubmicron region with device feature sizes <0.35µm, interconnect becomes the most dominant factor in design of high-speed Application Specific Integrated Circuits (ASICs). This paper proposes a novel methodology for automated data-path synthesis of such circuits and outlines algorithms to support it. In contrast to other approaches, we formulate interconnect area/delay optimizations as high-level synthesis transformations and use them during the synthesis to minimize the impact of wiring on circuit characteristics. Experiments with FIR filter implementations show that such formulation jointly with on the fly" module generation and performance-driven floorplanning provides more than a 30% reduction in wiring delay for deep sub-micron designs.

This paper presents an improved pragmatic approach to coded modulation design which provides higher coding gains especially for very noisy channels including those with Rayleigh fading. The signal constellation using four equally utilized dimensions implemented with two correlative carrier frequencies is adopted to enhance the performance of the pragmatic approach previously proposed by Viterbi et al.. The proposed scheme is shown to perform much better by analysis of system performance parameters and extensive computer simulation for practical channel conditions. The bandwidth and power efficiencies are also analyzed and discussed to provide more design flexibility for different communications environments.

In this paper, scattering problem of the grating coupler is analyzed by the mode-matching method in the sense of least squares for the gaussian light beam incidence. This coupler has a periodic groove structure of finite extent, which is formed on the surface of the core layer of the symmetric thin-film waveguide. In the present method, the approximate scattered fields of each region of the grating coupler are described by the superpositions of the plane waves with band-limited spectra, respectively. These approximate wave functions are determined by the minimization of the mean-square boundary residual. This method results in the simultaneous Fredholm type integral equations of the second kind for these spectra. The first and second order approximate solutions of the integral equations are derived analytically and the coupling efficiency and scattered fields are analyzed on the basis of those solutions. A qualitative and physical consideration for the scattering problem of the grating coupler is presented with the fundamental data derived from approximate solutions in this paper.

The Yasuura method is effective for calculating scattering problems by bodies of revolution. However dealing with 3-D scattering problems, we need to solve bigger size dense matrix equations. One of the methods to solve 3-D scattering is to use multipole expansion which accelerate the convergence rate of solutions on the Yasuura method. We introduce arrays of multipoles and obtain rapidly converging solutions. Therefore we can calculate scattering properties over a relatively wide frequency range and clarify scattering properties such as frequency dependence, shape dependence, and polarization dependence of 3-D scattering from perfectly conducting scatterer. In these numerical results, we keep at least 2 significant figures.

The scattering problem of a plane wave by an axially slotted conducting elliptic cylinder in homogeneous medium is investigated. We present an accurate analysis using the modified point matching method, which can reduce the order of the simultaneous equations to be solved at least by a half under the condition of the same accuracy as compared with an usual point matching method. The accuracy of our results is checked by evaluating the relative errors. Numerical results are given for scattered field patterns by a conducting elliptic cylinder with a slot aperture of angle width 120 when the angle of incidence θinO.

This paper proposed a fault localization and supervisory (SV) channel implementation for linear-repeaters (L-Reps) employing optical line amplifiers. In order to successfully introduce L-Reps into a Synchronous Digital Hierarchy (SDH)/Synchronous Optical Network (SONET)-based networks in a smooth, orderly fashion, layering of repeater section and supervisory system design must be taken into consideration. There supervisory techniques, such as linking analog-based and digital-based information, a precedence of digital-based information and an upstream precedence, for locating faulty L-Rep sections are proposed taking into consideration the difference in monitoring capabilities between L-Reps and regenerating-type repeaters (R-Reps). Furthermore, a linear repeater supervisory (LSV) channel configuration for L-Reps is also proposed. Finally, an SV system established in a prototype SDH-based 10-Gbit/s optical transmission system is briefly described.

3D model-based coding methods that need 3D reconstruction techniques are proposed for next-generation image coding methods. A method is presented that reconstructs 3D shapes of dynamic objects from image sequences captured using two cameras, thus avoiding the stereo correspondence problem. A coaxial camera system consisting of one moving and one static camera was developed. The optical axes of both cameras are precisely adjusted and have the same orientation using an optical system with true and half mirrors. The moving camera is moved along a straight horizontal line. This method can reconstruct 3D shapes of static objects as well as dynamic objects using motion vectors calculated from the moving camera images and revised using the static camera image. The method was tested successfully on real images by reconstructing a moving human shape.

In this paper, we propose a new design method to construct the highly reliable ATM network based on the virtual path (VP) concept. Through our method, we can guarantee a network survivability, by which we mean that connectivity between every pair of two end nodes is assured even after the failure, and that quality of service (QoS) requirements of each VC connection are still satisfied. For achieving a reliable network, every VP connection between two end nodes is equipped with a secondary VP connection such that routes of primary and secondary VPs are established on completely disjoint physical paths. Our primary objective of the current paper is that the construction cost of the VP-based network with such a survivability is minimized while the QoS requirement of traffic sources in fulfilled. For this purpose, after all the routes of VPs are temporarily established by means of the shortest paths, we try to minimize the network cost through (1) the alternation of VP route and (2) the separation of a single VP into several VPs, and optionally through (3) the introduction of VCX nodes. Through numerical examples, we show how the increased cost for the reliable network can be sustained by using our design method.

In this paper a new type of digital proxy signature is proposed. The proxy signature allows a designated person, called a proxy signer, to sign on behalf of an original signer. Classification of the proxy signatures is shown from the point of view of the degree of delegation, and the necessary conditions of a proxy signature are clarified. The proposed proxy signature scheme is based on either the discrete logarithm problem or the problem of taking the square root modulo of a composite number. Compared to the consecutive execution of the ordinary digital signature schemes, it has a direct from, and a verifier does not need a public key of a user other than the original signer in the verification stage. Moreover, it requires less computational work than the consecutive execution of the signature schemes. Due to this efficiency together with the delegation property, an organization, e.g. a software company, can very efficiently create many signatures of its own by delegating its signing power to multiple employees. Another attractive feature is that the proxy signature based on the discrete logarithm problem is highly applicable to other ordinary signature schemes based on the same problem, For instance, designated confirmer proxy signatures can be constructed. As a stronger form of proxy signature for partial delegation, another type of proxy signature scheme is proposed in which even an original signer cannot create a proxy signature. Furthermore, using a proposed on-line proxy updating protocol, the orignal signer can revoke proxies of dishonest proxy signers.

It is thought that we have generally succeeded in establishing learning algorithms for neural networks, such as the back-propagation algorithm. However two major issues remain to be solved. First, there are possibilities of being trapped at a local minimum in learning. Second, the convergence rate is too slow. Chang and Ghaffar proposed to add a new hidden node, whenever stopping at a local minimum, and restart to train the new net until the error converges to zero. Their method designs newly generated weights so that the new net after introducing a new hidden node has less error than that at the original local minimum. In this paper, we propose a new method that improves their convergence rate. Our proposed method is expected to give a lower system error and a larger error gradient magnitude than their method at a starting point of the new net, which leads to a faster convergence rate. Actually, it is shown through numerical examples that the proposed method gives a much better performance than the conventional Chang and Ghaffar's method.