This paper proposes polling-based real-time software for MPEG2 System protocol LSIs, which is a typical embedded and real-time system on a chip, and demonstrates its performance and usefulness. The polling-based real-time software is designed and optimized by analyzing application specific function requirements and deciding scheduling intervals and the execution cycles of each task. It requires neither hardware for multiple interrupt handling nor software for heavy context switching. The polling-based approach provides sufficient performance without any hardware and software overhead for a real-time application like the MPEG2 System protocol.

In this letter, a design method of linear-phase paraunitary filter banks is proposed for an odd number of channels. In the proposed method, a non-linear unconstrained optimization process is assumed to be applied to a lattice structure which makes the starting guess of design parameters simple. In order to avoid insignificant local minimum solutions, a recursive initialization procedure is proposed. The significance of our proposed method is verified by some design examples.

This paper addresses the optimum routing problem of multipoint connection in large-scale networks. A number of algorithms for routing of multipoint connection have been studied so far, most of them, however, assume the availability of complete network information. Herein, we study the problem under the condition that only partial information is available to routing nodes and that routing decision is carried out in a distributed cooperative manner. We consider the network being partitioned into clusters and propose a cluster-based routing approach for multipoint connection. Some basic principles for network clustering are discussed first. Next, the original multipoint routing problem is defined and is divided into two types of subproblems. The global optimum multicast tree then can be obtained asymptotically by solving the subproblems one after another iteratively. We propose an algorithm and evaluate it with computer simulations. By measuring the running time of the algorithm and the optimality of resultant multicast tree, we show analysis on the convergent property with varying network cluster sizes, multicast group sizes and network sizes. The presented approach has two main characteristics, 1) it can yield asymptotical optimum solutions for the routing of multipoint connection, and 2) the routing decisions can be made in the environment where only partial information is available to routing nodes.

Theoretical calculations of the pulsing operation and the intensity noise under the optical feedback are demonstrated for operation of the self-sustained pulsation lasers. Two alternative models for the optical feedback effect, namely the time delayed injection model and the external cavity model, are applied in a combined manner to analyze the phenomena. The calculation starts by supposing the geometrical structure of the laser and the material parameters, and are ended by evaluating the noise. Characteristics of the feedback induced noise for variations of the operating parameters, such as the injection current, the feedback distance and the feedback ratio, are examined. A comparison to experimental data is also given to ensure accuracy of the calculation.

We have developed and fabricated an LSI called the FMPP-VQ64. The LSI is a memory-based shared-bus SIMD parallel processor containing 64 PEs, intended for low bit-rate image compression using vector quantization. It accelerates the nearest neighbor search (NNS) during vector quantization. The computation time does not depend on the number of code vectors. The FMPP-VQ64 performs 53,000 NNSs per second, while its power dissipation is 20 mW. It can be applied to the mobile telecommunication system.

A multimedia coding standard, MPEG4 has frozen its Committee Draft (CD) as the MPEG4 version 1 CD, last October. It defines Audio-Visual (AV) coding Algorithms and their System Multiplex/Composition formats. Founding on Object-base concept, Video part adopts Shape Coding technology in addition to conventional Texture Coding skills. Audio part consists of voice coding tools (HVXC and CELP core) and audio coding tools (HILN and MPEG2 AAC or Twin VQ). Error resilience technologies and Synthetic and Natural Hybrid Coding (SNHC) technologies are the MPEG4 specific features. System part defines flexible Multiplexing of audio-visual bitstreams and Scene Composition for user-interactive re-construction of the scenes at decoder side. The version 1 standardization will be finalized in 1998, with some possible minute changes. The expected application areas are real-time communication, mobile multimedia, internet/intranet accessing, broadcasting, storage media, surveillance, and so on.

Almost all broadcasting systems and their equipment would be digitalized in the near future. In Japan, investigation of digital broadcasting has been going on for a long time, aiming at a realization of improvement of picture quality, new services, system flexibility, etc. Japanese digital broadcasting systems under development have a lot of technical merits, for example, a high transmission capacity and a hierarchical transmission scheme for satellite, and mobile reception for terrestrial digital broadcasting systems, compared to conventional digital systems.

Huet and Levy showed that index reduction is a normalizing strategy for every orthogonal strongly sequential term rewriting system. Toyama extended this result to root balanced joinable strongly sequential systems. In this paper, we present a class including all root balanced joinable strongly sequential systems and show that index reduction is normalizing for this class. We also propose a class of left-linear (possibly overlapping) NV-sequential systems having a normalizing strategy.

This paper presents an efficient bandwidth allocation method for the two-layer video coding of different spatial resolution. We first find a model of distortion-bitrate relationship for the MPEG-2 spatial scalable coding in a fixed total bitrate system. Then we propose an adaptive bitrate allocation method for a constant distortion ratio between two layers with the given total bandwidth. In the proposed method, approximated model parameters are used for simple implementation. The validity of the approximation is proven in terms of the convergence to the desired distortion ratio. It is shown by simulation that the proposed bitrate allocation method can keep almost a constant distortion ratio between two layers in comparison to a fixed bitrate allocation method.

For a given N-vertex graph H, a graph G obtained from H by adding t vertices and some edges is called a t-FT (t-fault-tolerant) graph for H if even after deleting any t vertices from G, the remaining graph contains H as a subgraph. For the n-dimensional cube Q(n) with N vertices, a t-FT graph with an optimal number O(tN+t2) of added edges and maximum degree of O(N+t), and a t-FT graph with O(tNlog N) added edges and maximum degree of O(tlog N) have been known. In this paper, we introduce some t-FT graphs for Q(n) with an optimal number O(tN+t2) of added edges and small maximum degree. In particular, we show a t-FT graph for Q(n) with 2ctN+ct2((logN)/C)C added edges and maximum degree of O(N/(logC/2N))+4ct.

An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.

We consider linearizable implementations of shared FIFO queues and general deterministic objects on a distributed message-passing system which provides a real-time timer. The efficiency of an implementation is measured by the worst-case response time res_time(op) for each operation op of the implemented objects. We show the following results under the assumption that all message delays are in the range [d-u,d] for some constants d and u (0 u d). We first present an implementation of deterministic objects with res_time(opa)=u for any ack-type operation opa and res_time(opv)=2d for any val-type operation opv, where an ack-type operation is an operation which always returns a unique response and a val-type operation is an operation which is not ack-type. We also consider an implementation of FIFO queues, which have two kinds of operations, enq(v) and deq. We show that, for any implementation of FIFO queues, (1) res_time(enq(v)) u(n-1)/n holds for some v where n is the number of processes, and (2) res_time(deq) d+u/2 holds in the case of u (2/3)d.

To further increase the capacity of the DS-CDMA reverse-link, this paper investigates the effectiveness of interference rejection weight control (IRWC) for the pilot symbol-assisted coherent multistage interference canceller (PSA-COMSIC) using recursive channel estimation (RCE). First, a bit error rate (BER) expression of the serial (successive) and parallel type hard decision multistage interference canceller (MSIC) with IRWC using Gaussian approximation for multiple access interference (MAI) are presented for no fading channels. It is theoretically shown that IRWC is effective in mitigating the interference replica generation error in hard decision MSIC. Next, the BER performance of PSA-COMSIC using IRWC in a multipath Rayleigh fading channel when channel coding is applied is evaluated by computer simulations. The BER performance and capacity are evaluated not only for the conventional serial and parallel types but also for serial/parallel (S/P) hybrid type and non-linear/linear (N/L) hybrid type schemes, both of which are effective in significantly reducing the demodulation processing delay. The simulation results demonstrate that, in interference-limited channels where the back ground noise is negligible, the capacity of serial type PSA-COMSIC using IRWC is about 10% higher than that without IRWC. It is also found that if we can accept a slight capacity degradation compared to the serial type PSA-COMSIC, S/P hybrid schemes are effective in reducing the demodulation processing delay.

Let G = (A, B, E) be a bipartite graph with bipartition (A:B) of vertex set and edge set E. For each vertex v, Γ(v) denotes the set of adjacent vertices to v. G is said to be t-convex on the vertex set A if there is a tree and a one-to-one correspondence between vertices in A and edges of the tree such that for each vertex b B the edges of the tree corresponding to vertices in Γ(b) form a path on the tree. G is doubly t-convex if it is convex both on vertex set A and on B. In this paper, we show that, the class of doubly t-convex graphs is exactly the class of bipartite circle graphs.

A floorplan is a partition of a rectangle into subrectangles, each of which is associated with a module. Zero-wasted-area layouts are known to exist when the height and width of modules are constrained only by the area, and several methods have been proposed for deriving such layouts. However, because these methods are global and indirect, they are inherently slow. We propose a new algorithm which simulates the air-pressure mechanics. It begins with a layout, which is not necessarily feasible, and iterates the movement of one wall at a time to the force-balancing position. The key issue is that it is guaranteed that every movement makes a current layout approach a zero-wasted-area layout by the measure of energy which is defined here. Experimental results on the example in several literatures and artificially made complex examples showed very fast convergence. The algorithm is evolved to methods which move all the walls simultaneously, resulting in a further speed enhancement.

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.

The packing problem is to pack given items into given containers as efficiently as possible under various constraints. It is fundamental and significant with variations and applications. The Set-Bin-Packing (SBP) is a class of packing problems: Pack given items into as few bins which have the same capacity where every item is a set and a bin can contain items as long as the number of distinct elements in the union of the items equals to or less than the capacity. One of applications is in FPGA technology mapping, which is our initial motivation. In this paper, the computational complexity of SBP is studied with respect to three parameters α, γ, and δ which are the capacity, the upper bound of the number of elements in an item, and the upper bound of the number of items having an element, respectively. In contrast that the well known Integer-Bin-Packing (IBP) is NP-hard but is proved that even a simplest heuristics First-Fit-Decreasing (FFD) outputs exact solutions as long as α 6, our result reveals that SBP remains NP-hard for a small values of these parameters. The results are summarized on a 3D map of computational complexities with respect to these three parameters.

This paper proposes a new design method of a nonlinear filtering algorithm in continuous-time stochastic systems. The observed value consists of nonlinearly modulated signal and additive white Gaussian observation noise. The filtering algorithm is designed based on the same idea as the extended Kalman filter is obtained from the recursive least-squares Kalman filter in linear continuous-time stochastic systems. The proposed filter necessitates the information of the autocovariance function of the signal, the variance of the observation noise, the nonlinear observation function and its differentiated one with respect to the signal. The proposed filter is compared in estimation accuracy with the MAP filter both theoretically and numerically.

Let H=(V(H),E(H)) be a directed graph with distinguished vertices s and t. An st-path in H is a simple directed path starting from s and ending at t. Let (H) be defined as { SS is the set of vertices on an st-path in H (s and t are excluded)}. For an undirected graph G=(V(G),E(G)) with V(G) V(H)- { s,t }, if the family of maximal independent sets of G coincides with (H), we call H an MIS-diagram for G. In this paper, we provide a necessary and sufficient condition for a directed graph to be an MIS-diagram for an undirected graph. We also show that an undirected graph G has an MIS-diagram iff G is a cocomparability graph. Based on the proof of the latter result, we can construct an efficient algorithm for generating all maximal independent sets of a cocomparability graph.

In this paper, we propose an efficient and powerful crossover operator in the genetic algorithm for solving the traveling salesman problem (TSP). Our proposed crossover is called the complete subtour exchange crossover (CSEX), and inherits as many good subtours as possible because they are worth preserving for descendants. Before generating the descendants, a prerequisite for the CSEX is that it enumerates all common subtours, which consist of the same set in a pair of subtours on the given two tours of n cities. An algorithm to enumerate all common subtours in the CSEX consumes only O(n) time. In a fundamental experiment, we show the experimental number and length of the common subtours for two randomly generated tours with 5 to 500 thousand elements. In addition, we give the practical behavior of the CSEX and compare the CSEX with a hopeful crossover operator using the benchmark instances for the TSP. Moreover, in another experiment of parallel computing, in order to analyze the performance of the CSEX, we compare the CSEX with hopeful crossovers for 25 benchmarks (48 - 2392 city) using a parallel supercomputer, Paragon. From these results, the CSEX shows an extremely bright performance.