In [1], approximate eigenvalues and eigenvectors are defined and algorithms to compute them are described. However, the algorithms require a certain condition: the eigenvalues of M modulo S are all distinct, where M is a given matrix with polynomial entries and S is a maximal ideal generated by the indeterminate in M. In this paper, we deal with the construction of approximate eigenvalues and eigenvectors when the condition is not satisfied. In this case, powers of approximate eigenvalues and eigenvectors become, in general, fractions. In other words, approximate eigenvalues and eigenvectors are expressed in the form of Puiseux series. We focus on a matrix with univariate polynomial entries and give complete algorithms to compute the approximate eigenvalues and eigenvectors of the matrix.

We introduce a strongly infix code. A code X is a strongly infix code if X is an infix code and any catenation of two words in X has no proper factor in X, which is neither a left factor nor a right factor. We show that the class of strongly infix codes is closed under composition, and, as the dual result, that the property to be strongly infix is inherited by a component of a decomposition.

Huynen has already provided a method to decompose a Mueller matrix in order to retrieve detailed target information in a polarimetric radar system. However, this decomposition sometimes fails in the presence of small error or noise in the elements of a Mueller matrix. This paper attempts to improve Huynen's decomposition method. First, we give the definition of stable decomposition and present an example, showing a problem of Huynen's approach. Then two methods are proposed to carry out stable decompositions, based on the nonlinear least square method and the Newton's method. Stability means the decomposition is not sensitive to noise. The proposed methods overcomes the problems on the unstable decomposition of Mueller matrix, and provides correct information of a target.

The adaptive associative memory proposed by Ma is used to construct a new model of semantic network, referred to as associative semantic memory (ASM). The main novelty is its computational effectiveness which is an important issue in knowledge representation; the ASM can do inference based on large conceptual hierarchies extremely fast-in time that does not increase with the size of conceptual hierarchies. This performance cannot be realized by any existing systems. In addition, ASM has a simple and easily understandable architecture and is flexible in the sense that modifying knowledge can easily be done using one-shot relearning and the generalization of knowledge is a basic system property. Theoretical analyses are given in general case to guarantee that ASM can flawlessly infer via pattern segmentation and recovery which are the two basic functions that the adaptive associative memory has.

Two-dimensional (2-D) adaptive digital filters (ADFs) for 2-D signal processing have become a fascinating area of the adaptive signal processing. However, conventional 2-D FIR ADF's require a lot of computations. For example, the TDLMS requires 2N2 multiplications per pixel. We propose a new 2-D adaptive filter using the FFTs. The proposed adaptive filter carries out the fast convolution using overlap-save method, and has parallel structure. Thus, we can reduce the computational complexity to O(log2N) per pixel.

In this paper, we apply the Semi-markov Memory and Cache coherence Interference (SMCI) model, which we had proposed for invalidating based cache coherent parallel computers, to an updating based protocol. The model proposed here, the SMCI/Dragon model, can predict performance of cache coherent parallel computers with the Dragon protocol as well as the original SMCI model for the Synapse protocol. Conventional analytic models by stochastic processes to describe parallel computers have the problem of numerical explosion in the number of states necessary as the system size increases. We have already shown that the SMCI model achieved both the small number of states to describe parallel computers with the Synapse protocol and the inexpensive computation cost to predict their performance. In this paper, we demonstrate generality of the SMCI model by applying it to the another cache coherence protocol, Dragon, which has opposite characteristics than Synapse. We show the number of states required by constructing the SMCI/Dragon model is only 21 which is as small as SMCI/Synapse, and the computation cost is also the order of microseconds. Using the SMCI/Dragon model, we investigate several comparative experiments with widely known simulation results. We found that there is only a 5. 4% differences between the simulation and the SMCI/Dragon model.

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.

This paper investigates the relations between the computational complexity and the restrictions for several problems that determine whether a given graph with edge costs and edge lengths has a spanning subgraph with such restrictions as the diameter, the connectivity, and the NA-distance and the NA-(edge)-connectivity proposed and investigated in [1]-[5]. The NA-distance and the NA-(edge)-connectivity are the measures for the distance and the connectivity between a vertex and a vertex subset (area). In this paper we prove that the minimum diameter spanning subgraph problem considering the restrictions of the diameter and the sum of edge costs is NP-complete even if the following restrictions are satisfied: all edge costs and all edge lengths are equal to one, and the upper bound of the diameter is restricted to four. Next, we prove that the minimum NA-distance spanning subgraph problem considering the restrictions of the NA-distances and the sum of edge costs is NP-complete even if the following conditions are satisfied: all edge costs and all edge lengths are equal to one, the upper bound of the NA-distance is restricted to four, each area is composed of a vertex, and the number of areas is restricted to two. Finally, we investigate the preserving NA-distance and NA-edge-connectivity spanning subgraph problem considering the preservations of the NA-distances and the NA-edge-connectivity and the restrictions of the sum of edge costs, and prove that a sparse spanning subgraph can be constructed in polynomial time if all edge costs are equal to one.

This paper describes a chip set architecture and its implementation for programmable MPEG2 MP@ML (main profile at main level) video encoder. The chip set features a functional partitioning architecture based on the MPEG2 layer structure. Using this partitioning scheme, an optimized system configuration with double bus structure is proposed. In addition, a hybrid architecture with dual video-oriented on-chip RISC processors and dedicated hardware and a hierarchical pipeline scheme covering all layers are newly introduced to realize flexibility. Also, effective motion estimation is achieved by a scalable solution for high picture quality. Adopting these features, three kinds of VLSI have been developed using 0. 5 micron double metal CMOS technology. The chip set consists of a controller-LSI (C-LSI), a macroblock level pixel processor-LSI (P-LSI) and a motion estimation-LSI (ME-LSI). The chip set combined with synchronous DRAMs (SDRAM) supports all the layer processing including rate-control and realizes real-time encoding for ITU-R-601 resolution video (720480 pixels at 30 frames/s) with glue less logic. The exhaustive motion estimation capability is scalable up to 63. 5 and 15. 5 in the horizontal and vertical directions respectively. This chip set solution realizes a low cost MPEG2 video encoder system with excellent video quality on a single PC extension board. The evaluation system and application development environment is also introduced.

The problem of constructing the proper-path-decomposition of width at most 2 has an application to the efficient graph layout into ladders. In this paper, we give a linear time algorithm which, for a given graph with maximum vertex degree at most 3, determines whether the proper-pathwidth of the graph is at most 2, and if so, constructs a proper-path-decomposition of width at most 2.

In the future, more and more network providers will be established through the introduction of an open telecommunications market. At this time, it is necessary to guarantee the fair competition between these network providers. In this paper, a negotiation protocol for connection establishment is proposed. This negotiation protocol is based on the concept of open, competitive bidding and can guarantee fair competition between the network providers. In this negotiation protocol, each network providers objective is to maximize its profit. Conversely, each users objective is to select a network provider which will supply as much capacity as required. Employing this negotiation protocol, the users and the network providers can select each other based on their objectives. In this paper, adaptation strategies which network providers and users can adopt under the proposed negotiation protocol framework are also discussed. A network provider which adopts this strategy can obtain enough profit even when the number of connection requests is small relative to the idle bandwidth capacity. Moreover, a user who adopts this strategy can be sure to obtain bandwidth even when the idle bandwidth capacity is small relative to the number of connection requests.

Topological Walk is an algorithm that can sweep an arrangement of n lines in O(n2) time and O(n) space. This paper revisits Topological Walk to give its new interpretation in contrast with Topological Sweep. We also survey applications of Topological Walk to make the distinction clearer.

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.

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.

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.

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.

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.

In recent years, the rapid advancements of wireless communication technology and computer down-sizing technology have enabled users to utilize computing resources anywhere in the computer network. New applications constructed on the mobile database system are becoming popular. However, the current database systems do not provide special facilities for specific update operations in a mobile computing environment. Moreover, due to the lack of a common data handling method and a mutual communication mechanism, varieties in implementations may cause applications to be incompatible with each other. In this paper, we take up the issue of data handling, in a mobile computing environment, and propose an active mobile database system (AMDS) to solve this issue. First, we review the difficulties of dynamic update of databases in a mobile computing environment, and provide a basic concept of AMDS as a solution for these difficulties. In order to construct an AMDS, we focus on asynchronous events such as the appearance and disappearance of a mobile computer in a wireless communication cell. Then we provide a facility to specify the behavior of each system in Event-Condition-Action(ECA) rules in the same way as normal active database systems. Moreover, we show the architecture and the design of our implementation of AMDS. And, finally AMDS can be easily implemented as a common database infrastructure and work well on heterogeneous systems through indoor experiments.

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.

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.