This paper proposes a top-down co-verification approach in the design of embedded systems composed of both hardware and software, for multimedia applications. In order to realize the optimized embedded system in cost, performance, power consumption and flexibility, hardware/software co-design becomes to be essential. In this top-down co-design flow, a target design is verified at three different levels: (1) algorithmic, (2) implementation, and (3) experimental. We have developed a methodology of top-down co-verification, which consists of the system level simulation at the algorithmic level, two type of co-simulations at the implementation level and the co-emulation at the experimental level. We have realized an environment optimized for verification performance by employing verification models appropriate to each verification stage and an efficient top-down environment by introducing the component logical bus architecture as the interface between hardware and software. Through actual application to a image compression and expansion system, the possibility of efficient co-verification was demonstrated.

In live multimedia applications with multiple videos, it is necessary to develop an efficient mechanism of multiplexing several MPEG video streams into a single stream and transmitting it over network without wasting excessive bandwidth. In this paper, we present an efficient multiplexing and traffic smoothing scheme for multiple variable bit rate (VBR) MPEG video streams in live video applications with finite buffer sizes. First, we describe the constraints imposed by the allowable delay bound for each elementary stream and by the multiplexer/receiver buffer sizes. Based on these constraints, a new multiplexing and traffic smoothing scheme is designed in such a way as to smooth maximally the multiplexed transmission rate by exploiting temporal and spatial averaging effects, while avoiding the buffer overflow and underflow. Through computer experiments based on an MPEG-coded video trace of Star-wars, it is shown that the proposed scheme significantly reduces the peak rate, coefficient of variation, and effective bandwidth of the multiplexed transmission rate.

In this paper, we propose a new structure of the frequency domain adaptive filter (FDAF). The proposed structure is based on the modified DFT pair which consists of the FIR filters, so that un-delayed output signal can be obtained with stable convergence and without accumulated error which are problems for the conventional FDAFs. The convergence performance of the proposed FDAF is examined through the computer simulations in the adaptive line enhancer (ALE) comparing with the conventional FDAF and the DCT domain adaptive filter. Furthermore, in order to improve the error performance of the FDAF, we propose a composite algorithm which consists of the normalized step size algorithm for fast convergence and the variable step size one for small estimation error. The advantage of the proposed algorithm is also confirmed through simulations in the ALE. Finally, we propose a reduction method of the computational complexity of the proposed FDAF. The proposed method is to utilize a part of the FFT flow-graph, so that the computational complexity is reduced to O(N log N).

In this paper, we give a new approach to the computation of primary decomposition and associated prime components of a zero-dimensional polynomial ideal (f1,f2,. . . ,fn), where fi are multivariate polynomials on Z (the ring of integer). Over the past several years, a considerable number of studies have been made on the computation of primary decomposition of a zero-dimensional polynomial ideal. Many algorithms to compute primary decomposition are proposed. Most of the algorithms recently proposed are based on Groebner basis. However, the computation of Groebner basis can be very expensive to perform. Some computations are even impossible because of the physical limitation of memory in a computer. On the other hand, recent advance in numerical methods such as homotopy method made access to the zeros of a polynomial system relatively easy. Hence, instead of Groebner basis, we use the zeros of a given ideal to compute primary decomposition and associated prime components. More specifically, given a zero-dimensional ideal, we use LLL reduction algorithm by Lenstra et al. to determine the integer coefficients of irreducible polynomials in the ideal. It is shown that primary decomposition and associated prime components of the ideal can be computed, provided the zeros of the ideal are computed with enough accuracy. A numerical experiment is given to show effectiveness of our algorithm.

Basic structural characteristics, which are useful in modular synthesis based on strongly connected state machines, of SMA/LBFC nets are discussed in this paper. A more convincing and direct proof of the equivalence of two structural characterization of the class of Petri nets is given. This proof will give clearer view of the structural characteristics of LBFC/SMA nets. On the other hand, however, the structural characteristics are not practically amenable in application to modular synthesis of SMA nets from a given set of SCSM's since all possible SCSM's should be examined for the verification of the given conditions. The later half of this paper is devoted into strengthening the results, i. e. , in composition of an SMA net from a given set of SCSM's the condition is also satisfied in any SCSM generated by composition.

A formal necessary and sufficient condition on the general Petri net reachability problem is presented by eliminating all spurious solutions among known nonnegative integer solutions of state equation and unifying all the causes of those spurious solutions into a maximal-strongly-connected and siphon-and-trap subnet Nw. This result is based on the decomposition of a given net (N, Mo) with Md and the concepts of "no immature siphon at the reduced initial marking Mwo" and "no immature trap at the reduced end marking Mwd" on Nw which are both extended from "no token-free siphon at the initial marking Mo" and "no token-free trap at the end marking Md" on N, respectively, which have been both effectively, explicitly or implicitly, used in the well-known fundamental and simple subclasses.

In this paper, we propose a transformation technique for the multiplications of one variable with multiple constants, which are frequently seen in the various applications of signal processing, image processing, and so forth. The method is based on the exploration of common subexpressions among constants and reduces the number of shifts, additions, and subtractions to implement linear computations with hardware. Our method searches for regularity among elements of a linear transform using matrix decomposition and generates a reduced data-flow graph which preserves the full regularity. We show experimental results obtained using Discrete Cosine Transform (DCT) and Fast Fourier Transform (FFT) and illustrate the effectiveness of the method.

FIR digital filters composed of parallel multiple subfilters are proposed. A binary expression of an input signal is decomposed into multiple shorter words, which drive the subfilters having different length. The output error is evaluated by mean squared and maximum spectra. A fast algorithm is also proposed to determine optimal filter lengths and coefficients of subfilters. Many examples confirm that the proposed filters generate smaller output errors than conventional filters under the condition of specified number of multiplications and additions in filter operations. Further, multiplier and adder structures (MAS) to perform the operations of the proposed filters are also presented. The number of gates used in the proposed MAS and its critical path are estimated. The effectiveness of the proposed MAS is confirmed.

We describe an algorithm for efficiently compositing partial images generated during parallel volume rendering on a distributed memory parallel computer. In this object space partitioning algorithm, each PE is assigned to several subvolumes where each subvolume has a corresponding local frame buffer. After volume rendering is performed independently for each subvolume, the partial images stored in the local frame buffers are combined to generate a complete image. During this compositing process, the communication of partial image data between the PEs is kept minimal by assigning PEs to subvolumes in an interleaved manner. This assignment makes possible a reduction in communication in the axis direction in which there is the most communication. Experimental results indicate that a 9% to 35% reduction in the total rendering time can be attained with no additional data structures and no memory overhead.

This paper proposes a design method of feature spaces in a two-stage image recognition method that improves the recognition accuracy and efficiency in statistical image recognition. The two stages are (1) image screening and (2) image recognition. Statistical image recognition methods require a lot of calculations for spatially matching between subimages and reference patterns of the specified objects to be detected in input images. Our image screening method is effective in lowering the calculation load and improving recognition accuracy. This method selects a candidate set of subimages similar to those in the object class by using a lower dimensional feature vector, while rejecting the rest. Since a set of selected subimages is recognized by using a higher dimensional feature vector, overall recognition efficiency is improved. The classifier for recognition is designed from the selected subimages and also improves recognition accuracy, since the selected subimages are less contaminated than the originals. Even when conventional recognition methods based on linear transformation algorithms, i. e. principal component analysis (PCA) and projection pursuit (PP), are applied to the recognition stage in our method, recognition accuracy and efficiency may be improved. A new criterion, called a screening criterion, for measuring overall efficiency and accuracy of image recognition is introduced to efficiently design the feature spaces of image screening and recognition. The feature space for image screening are empirically designed subject to taking the lower number of dimensions for the feature space referred to as LS and the larger value of the screening criterion. Then, the recognition feature space which number of dimensions is referred to as LR is designed under the condition LSLR. The two detection tasks were conducted in order to examine the performance of image screening. One task is to detect the eye- and-mouth-areas in a face image and the other is to detect the text-area in a document image. The experimental results demonstrate that image screening for these two tasks improves both recognition accuracy and throughput when compared to the conventional one-stage recognition method.

This paper proposes a time-interval data model in which all temporal representation and operations can be expressed with time intervals. The model expresses not only real time intervals, in which an event exists, but also null time intervals, in which an event is suspended. We model the history of a real-world event as a composite time interval, which is defined in this paper. Operations on the composite time intervals are also defined, and it is shown how these operations can be used to express temporal constraints with time intervals.

We investigate an importance sampling (IS) simulation of MMPP/D/1 queueing to obtain an estimate for the survivor function P(Q > q) of the queue length Q in the steady state. In Ref.[11], we studied the IS simulation of 2-state MMPP/D/1 queueing and obtained the optimal simulation distribution, but the mathematical fundation of the theory was not enough. In this paper, we construct a discrete time Markov chain model of the n-state MMPP/D/1 queueing and extend the results of Ref.[11] to the n-state MMPP/D/1. Based on the Markov chain model, we determine the optimal IS simulation distribution fo the n-state MMPP/D/1 queueing by applying the large deviations theory, especially, the sample path large deviations theory. Then, we carry out IS simulation with the obtained optimal simulation distribution. Finally, we compare the simulation results of the IS simulation with the ordinary Monte Carlo (MC) simulation. We show that, in a typical case, the ratio of the computation time of the IS simulation to that of the MC simulation is about 10-7, and the 95% confidence interval of the IS is slightly improved compared with the MC.

Irreducible components of canonical graphs for second order spectral null constraints at a rational submultiple of the symbol frequency fsk/n are studied where fs is the symbol frequency. We show that if n is prime then a canonical graph consists of disjoint irreducible components. We also show that the number of irreducible components of a canonical graphs is finite if n is prime. For the case n = 2 and p O mod n, all aperiodic irreducible components are identified explicitly where p is a parameter of a canonical graph.

In this paper, we introduce a Shared Multiple Rooted XOR-based Decomposition Diagram (XORDD) to represent functions with multiple outputs. Based on the XORDD representation, we develop a synthesis algorithm for general Exclusive Sum-of-Product forms (ESOP). By iteratively applying transformations and reductions, we obtain a compact XORDD which gives a minimized ESOP. Our method can synthesize larger circuits than previously possible. The compact ESOP representation provides a form that is easier to synthesize for XOR heavy multi-level circuits, such as arithmetic functions. We have applied our synthesis techniques to a large set of benchmark circuits in both PLA and combinational formats. Results of the minimized ESOP forms obtained from our synthesis algorithm are also compared to the SOP forms generated by ESPRESSO. Among the 74 circuits we have experimented with, the minimized ESOP's have fewer product terms than those of SOP's in 39 circuits.

This paper presents a logic synthesis method for look-up table (LUT) based field programmable gate arrays (FPGAs). We determine functions to be mapped to LUTs by functional decomposition for each of single-output functions. To share LUTs among several functions, we use a new Boolean resubstitution technique. Resubstitution is used to determine whether an existing function is useful to realize another function; thus, we can share common functions among two or more functions. The Boolean resubstitution proposed in this paper is customized for an LUT network synthesis because it is based on support minimization for an incompletely specified function. Experimental results show that our synthesis method produces a small size circuit in a practical amount of time.

Field Programmable Gate Arrays (FPGA's) are important devices for rapid system prototyping. Roth-Karp decomposition is one of the most popular decomposition techniques for Look-Up Table (LUT) -based FPGA technology mapping. In this paper, we propose a novel algorithm based on Binary Decision Diagrams (BDD's) for selecting good lambda set variables in Roth-Karp decomposition to minimize the number of consumed configurable logic blocks (CLB's) in FPGA's. The experimental results on a set of benchmarks show that our algorithm can produce much better results than the similar works of the previous approaches.

We propose a top-down approach for cosimulation of hardware/software co-designs for embedded systems and introduce a component logical bus architecture as an interface between software components implemented by processors and hardware components implemented by custom logic circuits. Co-simulation using a component logical bus architecture is possible is the same environment from the stage at which the processor is not yet finalized to the stage at which the processor is modeled in register transfer language. Models based upon a component logical bus architecture can be circulated and reused. We further describe experimental results of our approach.

One of the polarimetric radar applications is classification or identification of targets making use of the scattering matrix. This paper presents a decomposition scheme of a scattering matrix into three elementary scattering matrices in the circular polarization basis. The elementary components are a sphere, a diplane (dihedral corner reflector), and a helix. Since a synthetic aperture FM-CW radar provides scattering matrix through a polarimetric measurement, this decomposition scheme was applied to the actual raw data, although the matrix is resulted from a swept frequency measurement. Radar imaging experiments at the Ku band (14.5-15.5GHz) were carried out to obtain a total of 6464 scattering matrices in an imaging plane, using flat plates, corner reflectors and wires as elementary radar targets for classification. It is shown that the decomposition scheme has been successfully carried out to distinguish these targets and that the determination of rotation angle of line target is possible if the scattering matrix is classified as a wire.

An implementation of photometric stereo is described in which all directions of illumination are close to and rotationally symmetric about the viewing direction. THis has practical value but gives rise to a problem that is numerically ill-conditioned. Ill-conditioning is overcome in two ways. First, many more than the theoretical minimum number of images are acquired. Second, principal components analysis (PCA) is used as a linear preprocessing technique to determine a reduced dimensionality subspace to use as input. The approach is empirical. The ability of a radial basis function (RBF) neural network to do non-parametric functional approximation is exploited. One network maps image irradiance to surface normal. A second network maps surface normal to image irradiance. The two networks are trained using samples from a calibration sphere. Comparison between the actual input and the inversely predicted input is used as a confidence estimate. Results on real data are demonstrated.

Materials for a new reinforcement method using an internal heating technique have been developed experimentally for fusion splices. The method employs a protective package of a carbon-fiber composite and a hot-melt adhesive in a heat-shrinkable tube. The most appropriate heating current and heating time were determined from a consideration of the decomposition temperature of the adhesive (300) and the complete shrinking temperature (115) and the minimum welding temperature of Nylon 12 (about 180). The protective package can be installed in less than 30 seconds at a power of 10 W. Air bubbles which might cause microbending were completely eliminated by using Nylon 12 as the hot-melt adhesive, irradiated polyethylene as the heat-shrinkable tube and a carbon-fiber-composite electrical heating rod which also acted a tension member. The key for preparing the carbon-fiber composite was to remove its impurities. Under the condition of temperature difference larger than 40 deg. between the shrinking temperature of the heat-shrinkable tube and the melting temperature of the hot-melt adhesive. Nylon 12 and irradiated polyethylene were needed for the complete elimination of residual bubbles. By using Nylon 12 as the hot-melt adhesive, a reliable protective package could be achieved for a fusion spliced optical fiber with a low excess loss of less than 0.06 dB/splice between -60 and +70 and a high tensile strength of 3.9 kg.