Given a Petri net N=(P, T, E), a siphon is a set S of places such that the set of input transitions to S is included in the set of output transitions from S. Concerning extraction of one or more minimal siphons containing a given specified set Q of places, the paper shows several results on polynomial time solvability and NP-completeness, mainly for the case |Q| 1.

In this paper, an effective method of system modeling and dynamic scheduling to improve operation and control for the Back-End process of semiconductor manufacturing is developed by using Colored Timed Petri-Nets (CTPNs). The simulator of a CTPNs model was utilized to generate a new heuristic scheduling method with genetic algorithm(GA) which enables us to obtain the optimal values of the weighted delay time and standard deviation of lead time.

In a real-time system, it is required to reduce the response time to an interrupt signal, as well as the execution time of a Real-Time Operating System (RTOS). In order to satisfy this requirement, we have proposed a method of implementing some of the functionalities of an RTOS using hardware. Based on this idea, we have implemented a VLSI chip, called STRON (silicon TRON: The Realtime Operating system Nucleus), to enhance the performance of an RTOS, where the STRON chip works as a peripheral unit of any MPU. In this paper we describe the hardware architecture of the STRON chip and the performance evaluation results of the RTOS using the STRON chip. The following results were obtained. (1) The STRON chip is implemented in only about 10,000 gates when the number of each object (task, event flag, semaphore, and interrupt) is 7. (2) The task scheduler can execute within 8 clocks in a fixed period using the hardware algorithm when the number of tasks is 7. (3) Most of the basic µITRON system calls using the STRON chip can be executed in a fixed period of a few microseconds. (4) The execution time of a system call, measured by a multitask application program model, can be reduced to about one-fifth that in the case of the conventional software RTOS. (5) The total performance, including context switching, is about 2.2 times faster than that of the software RTOS. We conclude that the execution time of the part of the system call implemented by the STRON chip can almost be ignored, but the part of the interface software and context switching related to the architecture of a MPU strongly influence the total performance of an RTOS.

In this paper we present a Quality of Service (QoS) management architecture for distributed multimedia applications in heterogeneous communication environments of wired and wireless networks. Gaps in network performance such as bandwidths and error rates between wired and wireless networks, as well as gaps in terminal performance in media handling between desktop computers and handheld computers, bring about heterogeneities. Furthermore, even performance gaps among various desktop computers cause heterogeneities. As a result of these heterogeneities in network and terminal performances and various user preferences, the QoS requirement from each receiver is different. Therefore, mechanisms that adjust and satisfy each QoS requirement are needed. We propose a proxy server called Communication Coordination Server (CCS), which intermediates a video server and a receiver and manages the QoS coordination. The CCS performs QoS admission, adjustment, and allocation mechanisms to satisfy the user's QoS requirement. Then transcoding is used to realize the allocated QoS, and it decodes the input video stream from the video server and encodes it within the CCS. A QoS mapping mechanism that translates application-level QoS into resource-level QoS is needed for the QoS admission. We also propose a new QoS mapping mechanism using spline functions that enables a continuous QoS translation. We have built a CCS prototype in our laboratory testbed, and have verified that the CCS can resolve the heterogeneities between the server and receiver by the QoS adjustment mechanism of the transcoding and the QoS admission.

In this paper, we describe the PS3 load distribution scheme. A target service is a transaction service consisting of multiple processes that communicate with each other. A target system consists of workstations connected by a LAN. PS3 determines the process allocation by estimating response times and throughputs. It allows us to set an upper limit of a response time, and to set lower and upper limits for the throughput of each service. PS3 tries to find a process allocation that provides the minimum response time under conditions set by the user in advance. We measured the response times and throughputs and compared the values with the estimated ones. The results show that PS3 provides an appropriate process allocation, and that calculated results agree well with the measured ones.

This paper presents a new approach to simulation of Dynamically Reconfigurable Logic (DRL) systems, which offers better accuracy of modelling dynamic reconfiguration than previously reported techniques. Our method, named Clock Morphing (CM), is based on modelling dynamic reconfiguration via a reconfigured module clock signal, while using a dedicated signal value to indicate dynamic reconfiguration. We discuss problems associated with the other approaches to DRL simulation and describe the main principles behind the proposed technique. We further demonstrate feasibility of a CM DRL simulation on its example implementation in VHDL.

In the present paper we shall examine the real-time restoration of biomedical signals under additive noises. Biomedical signals measured by instruments such as catheter manometers, ambulatory electrocardiographs and thermo-dilution sensors are susceptible to distortion and noise. Therefore, such signals must be restored to their original states. In the present study, nonstationary biomedical signals are observed and described using a mathematical model, and several restoration filters that are composed of a series of applications of this model are proposed. These filters restored band-limited approximations of the original signals in real-time. In addition, redundancy is introduced into these restoration filters in order to suppress additive noise. Finally, an optimum filter that accounts for restoration error and additive noise is proposed.

Multimedia communications over mobile networks suffer from fluctuating channel degradation. Conventional error handling schemes consist of the first stage error correction decoding in wireless interface and the second stage error correction decoding in multimedia demultiplexer, where the second stage decoding result is not used to improve the first stage decoding performance. To meet the requirements of more powerful error protection, we propose iterative soft-input/soft-output error correction decoding in multimedia communications, where the likelihood output generated by the error correction decoding in multimedia demultiplexer is fed back to the decoding in wireless interface and the decoding procedure is iterated. The performances were evaluated by MPEG-4 video transmission simulation over mobile channels.

This paper proposes a novel MAC scheme over APON based on the cell arrival timing information to provide residential and small business customers with multimedia services. The proposed scheme supports the frame format of ITU-T recommendation G.983 and also provides diverse ATM service classes such as CBR, rtVBR, nrtVBR, ABR, and UBR traffics. Each service is allocated on the basis of priority and cell arrival timing information. Especially, the CBR and rtVBR services, which are sensitive to delay and CDV, are allocated with higher priority and more exact arrival timing resolution which is achieved with specific coding and ranging procedure. For the proposed MAC scheme, we present grant field format, minislot format, and bandwidth allocation algorithm. Computer simulation results show that the performance of the proposed scheme is significantly improved in terms of CDV and delay time in case of CBR and rtVBR services, comparing with the normal FIFO scheme.

Synchronization and continuity are essential for multimedia presentation, but because network resources and available bandwidth are both limited, synchronization quality and continuity quality have to be traded off in response to the fluctuating network conditions. This paper therefore introduces an algorithm for intramedia synchronization with adaptive quality of service (QoS) control handled at different layers of multimedia streams. The work described here is an extension of our earlier proposal of a synchronization algorithm by delay compensation protocol with two resynchronization mechanisms: retrieval offset adjustment and data unit skipping. That algorithm has been extended by the introduction of QoS control mechanisms in the QoS plane of a distributed control platform. The extended approach results not only in better synchronization and continuity, but also integrates the QoS adjustment into the existing architecture. Unexpected QoS variations are coped with by an adaptive QoS control designed to maintain the desired application qualities within the fluctuating environment. Simulations implemented on a UDP/IP network have verified the effectiveness of the proposed scheme.

High-speed collision detection is important to realize a highly-safe intelligent vehicle. In collision detection, high-computational power is required to perform matching operation between discrete points on surfaces of a vehicle and obstacles in real-world environment. To achieve the highest performance, a hierarchical matching scheme is proposed based on two representations: the coarse representation and the fine representation. A vehicle is represented as a set of rectangular solids in the fine representation (fine rectangular solids), and the coarse representation, which is also a set of rectangular solids, is produced by enlarging the fine representation. If collision occurs between an obstacle discrete point and a rectangular solid in the coarse representation (coarse rectangular solid), then it is sufficient to check the only fine rectangular solids contained in the coarse one. Consequently, checks for the other fine rectangular solids can be omitted. To perform the hierarchical matching operation in parallel, a hierarchically-content-addressable memory (HCAM) is proposed. Since there is no need to perform matching operation in parallel with fine rectangular solids contained in different coarse ones, the fine ones are mapped onto a matching unit. As a result, the number of matching units can be reduced without decreasing the performance. Under the condition of the same execution time, the area of the HCAM is reduced to 46.4% in comparison with that of the conventional CAM in which the hierarchical matching scheme is not used.

In this paper, we present the theoretical development to stabilize a class of uncertain time-delay system. The system under consideration is described in state space model containing distributed delay, uncertain parameters and disturbance. The main idea is to transform the system state into an equivalent one, which is easier to analyze its behavior and stability. Then, a computational method of robust controller design is presented in two parts. The first part is based on solving a Riccati equation arising in the optimal control theory. In the second part, the finite dimensional Lyapunov min-max approach is employed to cope with the uncertainties. Finally, we show how the resulting control law ensures asymptotic stability of the overall system.

Wavelet filters used in usual applications are not time-varying filters. In this paper, we present a novel method to design biorthogonal wavelet filters which are orthogonal to the input signals. We call newly designed filters time-varying lifting wavelet filters (TVLWF). Their feature is to vary the wavelet filters adapting to the input signal by tuning free parameters contained in the lifting scheme developed by Sweldens. These filters are almost compact support and perfect reconstruction. By using TVLWF, we demonstrate an application to data compression of electrocardiogram (ECG) which is one of the semi-periodic time-series signals and show that the time-varying system can be constructed easily and the proposed method is very useful for data compression.

A nonlinear time series predictor was proposed, in which a nonlinear sub-predictor (NSP) and a linear sub-predictor (LSP) are combined in a cascade form. This model is called "hybrid predictor" here. The nonlinearity analysis method of the input time series was also proposed to estimate the network size. We have considered the nonlinear prediction problem as a pattern mapping one. A multi-layer neural network, which consists of sigmoidal hidden neurons and a single linear output neuron, has been employed as a nonlinear sub-predictor. Since the NSP includes nonlinear functions, it can predict the nonlinearity of the input time series. However, the prediction is not complete in some cases. Therefore, the NSP prediction error is further compensated for by employing a linear sub-predictor after the NSP. In this paper, the prediction mechanism and a role of the NSP and the LSP are theoretically and experimentally analyzed. The role of the NSP is to predict the nonlinear and some part of the linear property of the time series. The LSP works to predict the NSP prediction error. Furthermore, predictability of the hybrid predictor for noisy time series is investigated. The sigmoidal functions used in the NSP can suppress the noise effects by using their saturation regions. Computer simulations, using several kinds of nonlinear time series and other conventional predictor models, are demonstrated. The theoretical analysis of the predictor mechanism is confirmed through these simulations. Furthermore, predictability is improved by slightly expanding or shifting the input potential of the hidden neurons toward the saturation regions in the learning process.

We propose a new bit timing recovery (BTR) scheme, called perturbed sampling BTR (PSBTR), that can operate near the symbol rate in high-bit-rate wireless systems. A peculiar sample clock, the duty factor of which is not 50%, is used in the PSBTR scheme. We call this type of clock a perturbed sample clock and use it for clock recovery. In PSBTR, there is no cycle slip of the sample clock, and the PSBTR circuit is mostly digital. We examine the performance of the PSBTR scheme under additive white Gaussian noise (AWGN) by computer simulation and experiment, and from these results, clarify the relationship between the performance and circuit parameters of the PSBTR circuit. The overall results indicate that the PSBTR scheme performs well and can be employed as a BTR scheme for high-bit-rate wireless systems.

Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems of time Petri nets. In this model, a minimal and a maximal firing delays are assigned to each transition. If a transition is 'enabled' it can fire after minimal delay has passed and must fire before maximal delay has elapsed. Since time Petri net can simulate register machines, it has equivalent modeling power to that of Turing machine. It means, however, that most of the analysis problems of time Petri nets with general net structures are undecidable. In this paper, net structures are restricted to a subclass called partially ordered condition (POC) nets and dissynchronous choice (DC) nets. Firing delays are also restricted to satisfy 'static fair condition' which assures chance to fire for all transitions enabled simultaneously. First, a sufficient condition of liveness of time POC net with the static fair condition is derived. Then it is shown that liveness of time DC net with static fair condition is equivalent to liveness of the underlying nontime net. This means that liveness problem of this class is decidable. Lastly, liveness problem of extended free choice (EFC) net is shown to be decidable.

The problem of transient scattering caused by abrupt extinction of a terminative conducting screen in a waveguide is considered. First, a boundary-value problem is formulated to describe the transient phenomena, the problem in which the boundary condition depends on time. Then, application of the Fourier transformation with respect to time derives a Wiener-Hopf-type equation, which is solved by a commonly known decomposition procedure. The transient fields are obtained through the deformation of the integration path for the inverse transformation and the results are represented in terms of the incomplete Lipschitz-Hankel integrals. Numerical examples showing typical transient phenomena are attached.

We proposed a new model for non-stationary time series analysis based on the IAR (inhomogeneous autoregressive) model, and a method for model parameter estimation when the set of basis is given. In this paper, we further propose a method for parameter estimation including that of basis set: we set a new condition that power of the input sequence is concentrated in low-frequency domain, and developed an iterative estimation method. We firstly select an initial set of basis, from which new sets are created in order to minimize the difference between the model and data. Among new sets of basis, we select a good one that gives minimum standard deviation of estimated frequencies.

Multimedia mobile communication systems with high-speed radio transmission supported by asynchronous transfer mode (ATM) technologies have been intensively studied over the last few years. Smaller radio zones termed microcells and picocells will be used in this kind of mobile communication systems for the purpose of high-speed radio transmission. When the coverage of a radio zone is smaller, the amount of traffic per radio zone is relatively low. It is not possible to use the cable circuits connecting the switch and base stations in an efficient manner because of the lack of the scale effect of traffic. With smaller radio zones, moreover, handoff occurs frequently as a mobile station moves. The switch is required a large capacity to handle the processing of frequent handoffs. This paper proposes a mobile network architecture controlled by the concentrated grouping of base stations. A special feature of this configuration is the ability of the network's switches to efficiently accommodate numerous base stations that control small radio zones. It can also lighten the handoff control load of switches; the effect of handoff frequency reduction is evaluated with computer simulation.

In a personal communication system (PCS), a scheme for reforwarding call-terminating setup messages (SETUP messages) from a network or a cell station is used to guard against their loss. We have developed a method for evaluating the loss probability of a reforwarding scheme in which the network monitors the response messages from a personal station after forwarding a SETUP message to that personal station and reforwards the SETUP message only if a response message is not received. We started with a stochastic model in which messages registered in the paging-channel queue in a cell station are cyclically forwarded to the wireless area. This model corresponds to the finite-capacity M/D/1/N model with vacation time. We then added a method for calculating the "timeout" probability. Next we expanded the model into one in which the SETUP messages are reforwarded when a response message is not received by the network. This model corresponds to the M/D/1/N model with vacation time and retrials. We then added an approximate method for calculating the loss probability. Finally, using the proposed methods, we clarified the traffic characteristics of PCS call-terminating control.