We define the Reallocation Problem to determine whether we can move products from their current store-houses to target storehouses in a number of moves which is less than or equal to a given number. This problem is defined simply and can be applied to many practical problems. We give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose liner time algorithms, when the volume of the products is restricted to 1. Moreover, we show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.

This letter proposes ALPEN, a simple, flexible and cost effective ATM-WAN architecture that emulates multiple ATM-layer protocols at the edge nodes. Any new ATM-layer protocol can be easily implemented by modifying only the edge nodes. The transit network is simple and independent of the protocols emulated, and ALPEN has a short response time. It is very suitable for implementing multimedia ATM networks.

We present a new method for the self-tuning control (STC) of nonminimum phase continuous-time systems based on the pole-zero placement. The long division method is used to decompose a polynomial into a stable and unstable polynomials. It is also shown that the effect of unstable zeros on the magnitude of the desired output can be cancelled. Finally, the results of computer simulation are presented to illustrate the effectiveness of the proposed method.

A new superresolution technique is proposed for high-resolution estimation of the scattering analysis. For complicated multipath propagation environment, it is not enough to estimate only the delay-times of the signals. Some other information should be required to identify the signal path. The proposed method can estimate the frequency characteristic of each signal in addition to its delay-time. One method called modified (Root) MUSIC algorithm is known as a technique that can treat both of the parameters (frequency characteristic and delay-time). However, the method is based on some approximations in the signal decorrelation, that sometimes make problems. Therefore, further modification should be needed to apply the method to the complicated scattering analysis. In this paper, we propose to apply a time-domain null filtering scheme to reduce some of the dominant signal components. It can be shown by a simple experiment that the new technique can enhance estimation accuracy of the frequency characteristic in the Root-MUSIC algorithm.

G/D/1 is a theoretic model for ATM network queueing based on processing cells. We investigate the G/D/1 system by discrete time modeling. Takacs' combinatorial methods are applied to analyze the system performance. An approximation for the survivor function P[Q > q], which is the probability that the queue length Q in the stationary state exceeds q, is obtained. The obtained formula requires only very small computational complexity and gives good approximation for the true value of P[Q > q].

Air interfaces of the future mobile communication are widely spreading, because of the multimedia service demands, technology trends and radio propagation conditions. Radio-Highway Networks are expected to realize the universal, seamless and multi-air-interface capability for mobile access networks, and play an important role in the future multimedia radio communications. For the radio-highway networks, this paper newly proposes natural bandpass sampling - asynchronous time division multiple access (NBS-ATDMA) method, where radio signals are natural bandpass sampled at the radio base station and are asynchronously multiplexed on the optic fiber bus link and intelligently transmitted to its desired radio control station. We theoretically analyze the loss probability of the radio signal due to collision in the network and the carrier-to-noise power ratio of received radio signals at the radio control station. Moreover, in order to reduce the loss probability, two access control methods, carrier sense and pulse width control, are proposed, and it is clarified that these improve the number of base station connected to radio highway networks.

Multiple TDMA bursts assignment between a base station and a personal terminal will be required for multimedia communications that offers high speed signal transmission such as voice and data simultaneous transmission. This paper proposes a reliable packet transmission method for TDMA based wireless multimedia communications. The proposed method employs an adaptive transmission rate control according to the packet length and a burst diversity technique is applied to improve the frame error rate of a packet. The frame error rate performance has been approximated theoretically by using fade- and infade-duration statistics of a Rayleigh fading channel and a computer simulation has been carried out for two control channels, FACCH/SACCH (Fast/Slow Associated Control CHannel) in the PHS as well as GSM. Both results indicate that the frame error rate is dramatically improved, about one order, when two bursts have different frequency and improved by about 25% when the two bursts have the same frequency.

Wet cleaning in actual LSI process is difficult to remove contamination perfectly, because the cleaning condition must be moderate to maintain device characteristics and device texture and because wet cleaning is not so effective for the particles generated during processes such as etching, photo lithography and film formation. Particle reduction depends on particle characteristics, i.e. the sticking force and the chemical structure of the particles. Metallic contamination on wafers, depending on the kind of solutions and the metal concentration in cleaning solutions, degrades TDDB characteristics and recom-bination lifetime. Although the lifetime degradation by the metallic contamination is appreciable, it is much smaller than those caused by damage in etching and in ion implantation.

Circuit simulators are used to verify circuit functionality and to obtain detailed timing information before the expensive fabrication process takes place. They have become an essential CAD tool in an era of sub-micron technology. We have developed a new event-driven MOS circuit simulator to replace a direct method circuit simulator. In our simulator, partitioned subcircuits are analyzed by a direct method matrix solver, and these are controlled by an event-driven scheme to maintain accuracy. The key of this approach is how to manage events for circuit simulation. We introduced two types of events: self-control events for a subcircuit and prediction correcting events between subcircuits. They control simulation accuracy, and bring simulation efficiency through multi-rate behavior of a large scale circuit. The event-driven scheme also brings some useful functions which are not available from a direct method circuit simulator, such as a selected block simulation function and a batch simulation function for load variation. We simulated logic modules (buffer, adder, and counter) with about 1000 MOSFETs with our event-driven MOS circuit simulator. Our simulator was 5-7 times faster than a SPICE-like circuit simulator, while maintaining the less than 1% error accuracy. The selected block simulation function enables to shorten simulation time without losing any accuracy by selecting valid blocks in a circuit to simulate specified node waveforms. Using this function, the logic modules were simulated 13-28 times faster than the SPICE-like circuit simulator while maintaining the same accuracy.

A new line simulator, SEMALIS has been developed. This simulator can handle complicated lot processings to maintain processing quality and efficient line operations to improve line performance. The current manufacturing line consists of five resource models: lot, process sequence, equipment, lot processing, and line operations. The parameters of these models are defined so as to accurately reflect the state of the line operations. From our simulation results, we confirmed that SEMALIS accurately identifies bottlenecks or starvations where equipment can be added or reduced to optimize equipment utilization through resource planning, and that SEMALIS can also be used to evaluate the long-term effects of line operating methods on the line performance of ASIC manufacturing lines.

In this study, we discuss a discrete-time cellular neural network (DTCNN) and its applications including convergence property and stability. Two theorems about the convergence condition of nonreciprocal non-uniform DTCNNs are described, which cover those of reciprocal one as a special case. Thus, it can be applied to wide classes of image processings, such as associative memories, multiple visual patterns recognition and others. Our DTCNN realized by the software simulation can largely reduce the computational time compared to the continuous-time CNN.

In this paper, we formulate and solve a discrete-time queueing problem that has two potential applications: ATM multiplexers and DQDB networks. We first consider the modeling of an ATM multiplexer. The object of the analysis is a periodic traffic stream (CBR traffic), which is one of the inputs to the multiplexer. As in previous works of the subject, we consider a memoryless background traffic input. Here, in addition to this background traffic, we take into account the influence of a high-priority traffic, which is time-correlated and requires expedited service. We analyze the influence of these two types of traffic on the statistics of the interdeparture time (jitter process) and the delay of the periodic traffic stream. We obtain their distributions in a form of z-transforms, and from these we derive closed form expressions for the average delay and the variance of the interdeparture time. Our results show that the delay and jitter are very sensitive to the burstiness of the high priority traffic arrival process. We next apply our analytical modeling to a DQDB network when some of its stations are driven by CBR sources. We can obtain interesting results concerning the influence of the physical location of a DQDB station on the jitter.

A design of current-mode continuous-time filters for low voltage and high frequency applications using complementary bipolar current mirror pairs is presented. The proposed current-mode filters consist of simple bipolar current mirrors and capacitors and are quite suitable for monolithic integration. Since the filters are based on the integrator type of realization, the proposed method can be used for a wide range of applications. The frequency of the filters can easily be changed by the DC controlling current. A fifth-order Butterworth and a thirdorder leapfrog filter with tunable cutoff frequencies from 20 MHz to 100 MHz are designed as examples and simulated by SPICE using standard bipolar parameters.

In ITU-T Recommendation I.371, the Generic Cell Rate Algorithm (GCRA) is used to define Peak Cell Rate for the ATM network. It is further applied by the ATM Forum '93 to define Sustainable Cell Rate and Burst Tolerance so as to facilitate Usage Parameter Control and Network Parameter Control. To judge the validity of a cell according to declared GCRA parameters, the enforcer must read the clock time when the cell arrives. However, the clock of the enforcer would roll over frequently and accordingly the judgment would be incorrect. On the other hand, for a shaper in a customer premise node to dispatch cells conforming to the declared GCRA parameters, the clock would also roll over and the cell would not be dispatched correctly. To overcome the problems induced by clock roll-over, based on "time difference" concept, we propose two modified GCRA's for the enforcer and shaper, respectively. According to the proposed algorithms, we design a feasible architecture for a multi-connection shaper and simplify it for an enforcer. They are proven to perform well in spite of the inherent clock roll-over characteristics. By simulation, we evaluate the delay in the shaper and the loss in the enforcer. The features of the architectures are also discussed.

We present a recursive algorithm for constructing linear discrete-time systems which interpolate the desired 1st-and 2nd-order information. The recursive algorithm constructs a new system and connects it to the previous system in the cascade form every time new information is added. These procedures yield a practical realization of all the interpolants.

In 1980, Hellman presented "time-memory trade-off cryptanalysis" for block ciphers, which requires precomputation equivalent to time complexity of exhaustive search, but can drastically reduce both time complexity on intercepted ciphertexts of exhaustive search and space complexity of table lookup. This paper extends his cryptanalysis and optimizes a relation among the breaking cost, time, and success probability. The power of the optimized cryptanalytic method can be demonstrated by the estimates as of January 1995 in the following. For breaking DES in one hour with success probability of 50% or more, the estimated cost of a simple and a highly parallel machine is respectively about 0.26[million dollars] and 0.06[million dollars]. Also it takes about six and two years respectively until each machine costs for breaking FEAL-32 on the same condition decreases to 1[million dollars]. Moreover, it takes about 22.5 and 19[years] respectively until each costs for breaking Skipjack similarly decreases to 1[million dollars], but time complexity of precomputation is huge in case of the former. The cost-time product for this precomputation will decrease to 20[million dollarsyears] in about 30[years].

This paper proposes a photonic integrated beam forming and steering network (BFN) that uses switched true-time-delay (TTD) silica-based waveguide circuits for phased array antennas. The TTD-BFN has thermooptic switches and variable time delay lines. This TTD-BFN controls four array elements, and can form and steer a beam. An RF test was carried out in the 2.5 GHz microwave frequency range. The experimental results show a peak-to-peak phase error of 6.0 degrees and peak-to-peak amplitude error of 2.0 dB. Array factors obtained from the measured results agree well with the designed ones. This silica-based beam former will be a key element in phased array antennas.

This paper presents a new internal image representation, in which the scene is encoded into a three-intensity-level image. This representation is generated by Laplacian-Gaussian filtering followed by dual-thresholding. We refer to this imege as three-level broad-edge representation. It supresses the high frequency noise and shading in the image and encodes the sign of relative intensity of a pixel compared with surrounding region. Image model search based on cross correlation using this representation is as reliable as the one based on gray normalized correlation, while it reduces the computational cost by 50 times. We examined the reliability and realtime performance of this method when it is applied to an industrial object recognition task. Our prototype system achieves 3232 image model search from the 128128 pixel area in 2 milli-seconds with a 9 MHz pixel clock image processor. This speed is fast enough for searching and tracking a single object at video frame rate.

This paper presents efficient algorithms for updating moving octrees with real-time performance. The first algorithm works for octrees undergoing both translation and rotation motion; it works efficiently by compacting source octrees into a smaller set of cubes (not necessarily standard octree cubes) as a precomputation step, and by using a fast, exact cube/cube intersection test between source octree cubas and target octree cubes. A parallel version of the algorithm is also described. Finally, the paper presents an efficient algorithm for the more limited case of octree translation only. Experimental results are given to show the efficiency of the algorithms in comparison to competing algorithms. In addition to being fast, the algorithms presented are also space efficient in that they can produce target octrees in the linear octree representation.

This paper describes a statistical integration algorithm for color, motion and stereo disparity, and introduces a real-time stereo system that can tell us where and what objects are moving. Regarding the integration algorithm, motion estimation and depth estimation are simultaneously performed by a clustering process based on motion, stereo disparity, color, and pixel position. As a result of the clustering, an image is decomposed into region fragments. Eath fragment is characterized by distribution parameters of spatiotemporal intensity gradients, stereo difference, color and pixel positions. Motion vectors and stereo disparities for each fragment are obtained from those distribution parameters. The real-time stereo system can view the objects with the distribution parameters over frames. The implementation and experiments show that we can utilize the proposed algorithm in real-time applications such as surveillance and human-computer interaction.