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 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 a secure partially blind signature scheme, the signer assures that the blind signatures issued by him contains the information he desires. The techniques make it possible to minimize the unlimited growth of the bank's database which storing all spent electronic cash in an anonymous electronic cash system. In this paper we propose an efficient partially blind signature scheme for electronic cash. In our scheme, only several modular additions and modular multiplications are required for a signature requester to obtain and verify a signature. It turns out that the proposed scheme is suitable for mobile clients and smart-card applications because no time-consuming computations are required, such as modular exponentiation and inverse computations. Comparing with the existing blind signature schemes proposed in the literatures, our method reduces the amount of computations for signature requesters by almost 98%.

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.

We propose a new approach to the exact performance analysis of a shared buffer ATM multiplexer, which is loaded with mixed correlated and uncorrelated traffic sources. We obtain the joint steady-state probabilities of both states of the input process and the buffer using a one-dimensional Markov chain. From these probabilities we calculate the loss probabilities and the average delays of the correlated and the uncorrelated traffic sources.

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.

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.

A VLSI architecture of a motion estimator is described dedicatedly for the H. 263 low bitrate video coding. Adopting an efficient hierarchical search algorithm, a new motion estimator yields high quality vectors with small area occupancy and at a low operation frequency. A one-dimensional PE (Processing Element) array is devised to be tuned to the H. 263 encoding, which treats both the advanced prediction mode and the PB-frame mode. The proposed motion estimation core is integrated in 1. 55 mm2 by using 0. 35 µm CMOS 3LM technology, which operates at 15 MHz, and hence enables the realtime motion estimation of QCIF pictures.

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 introduce a concept of regularization into Genetic Algorithms (GAs). Conventional GAs include no explicit regularizing operations. However, the regularization is very effective in solving ill-posed problems. So, we propose a method of regularization to apply GAs to ill-posed problems. This regularization is a kind of consensus operation among neighboring individuals in GAs, and plays the role of `smoothing the solution. ' Our method is based on the evaluation of macroscopic fitness, which is a new fitness criterion. Conventional fitness of an individual in GAs is defined only from the phenotype of the individual, whereas the macroscopic fitness of an individual is evaluated from the phenotypes of the individual and its neighbors. We tested our regularizing operation by means of experiments with an elastic image mapping problem, and showed the effectiveness of the regularization.

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.

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.

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 two attacks against blind decryption (decode) based on the commutative random-self reducibility and RSA systems utilizing the transformability of digital signatures proposed in [2]. The transformable digital signature was introduced in [2],[8] for defeating an oracle attack, where the decrypter could be abused as an oracle to release useful information for an attacker acting as a requester of blind decryption. It was believed in [2],[8] that the correctness of a query to an oracle was ensured by the transformable signature derived from an original signature issued by the decrypter in advance, and a malicious query to an oracle could be detected before the blind decryption by the decrypter or would lead to release no useful information to an attacker. The first attack can decrypt all encrypted data with one access to an oracle. The second one generates a valid signature for an arbitrary message selected by an attacker abusing the validation check procedure.

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.

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.

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.

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.

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.

The classical max-min policy has been suggested by the ATM Forum to support the available bit rate (ABR) service class. However, there are several drawbacks in adopting the max-min rate allocation policy. In particular, the max-min policy is not able to support the minimum cell rate (MCR) requirement and the peak cell rate (PCR) constraint for each ABR connection. Furthermore, the max-min policy does not offer flexible options for network providers wishing to establish a usage-based pricing criterion. In this paper, we present a generic weight-based rate allocation policy, which generalizes the classical max-min policy by supporting the MCR/PCR for each connection. Our rate allocation policy offers a flexible usage-based pricing strategy to network providers. A centralized algorithm is presented to compute network-wide bandwidth allocation to achieve this policy. Furthermore, a simple switch algorithm using ABR flow control protocol is developed with the aim of achieving our rate allocation policy in a distributed networking environment. The effectiveness of our distributed algorithm in a local area environment is substantiated by simulation results based on the benchmark network configurations suggested by the ATM Forum.