The embedded Markov processes associated with Markovian queueing systems are closely related, and their relationships are important for establishing an analytical basis for performance evaluation techniques. As a first step, we analyze the embedded processes associated with a general M/M/1 queueing system. Linear transformations between the infinitesimal generators and the transition probability matrices of embedded processes at arrival and departure times are explicitly derived. Based upon these linear transformations, the equilibrium distributions of the system states at arrival and departure times are obtained and expressed in terms of the equilibrium distribution at arbitrary times. The approach presented here uncovers an underlying algebraic structure of M/M/1 queueing systems, and establishes an algebraic methodology for analyzing the equilibrium probabilities of the system states at arrival and departure times for more general Markovian queueing systems.
Keiji KONISHI Yoshiaki SHIRAO Hiroaki KAWABATA Masaya HIRATA Toshikuni NAGAHARA Yoshio INAGAKI
One model of a laser is a set of differential equations called the Maxwell-Bloch equations. Actually, in a physical system, causing a chaotic behavior is very difficult. However the chaotic behavior can be observed easily in the system which has a mirror to feedback the delayed output.
Hideaki WAKABAYASHI Masanobu KOMINAMI Shinnosuke SAWA Hiroshi NAKASHIMA
Frequency Selective Screens (FSS) with conductor or complementary aperture array are investigated. The electric current distribution on conductor or the magnetic current distribution on aperture is determined by the moment method in the spectral domain. In addition, the power reflection coefficients are calculated and the scattering properties are considered.
Masahito SHOYAMA Koosuke HARADA
This paper presents a new type of zero-voltage-switched (ZVS) push-pull dc-dc converter with two synchronous rectifiers in the secondary circuit. ZVS is realized using the magnetizing current of the transformer as a constant current source during the commutation. The output voltage is controlled by PWM with a constant switching frequency. The circuit operation is described using equivalent circuits. The steady-state and dynamic characteristics are analyzed and confirmed experimentally.
Masashi HASHIMOTO Yukio FUKUDA Shigeki ISHIBASHI Ken-ichi KITAYAMA
The newly developed GaAs-pin/SLM, that is structured with a GaAs-pin diode photodetector and a ferroelectric liquid crystal as the light phase modulator, shows the accumulative thresholding characteristic against the optical energy of the write-in pulse train. We experimentally investigate this characteristic and discuss its applications to optical parallel processings.
This paper presents an efficient algorithm for computing the capacity of discrete memoryless channels. The algorithm uses Newton's method which is known to be quadratically convergent. First, a system of nonlinear equations termed Kuhn-Tucker equations is formulated, which has the capacity as a solution. Then Newton's method is applied to the Kuhn-Tucker equations. Since Newton's method does not guarantee global convergence, a continuation method is also introduced. It is shown that the continuation method works well and the convergence of the Newton algorithm is guaranteed. By numerical examples, effectiveness of the algorithm is verified. Since the proposed algorithm has local quadratic convergence, it is advantageous when we want to obtain a numerical solution with high accuracy.
Bernd FREISLEBEN Hans-Henning KOCH Oliver THEEL
In this paper we present and analyze multi-level quorum schemes for maintaining the consistency of replicated data in the presence of concurrency and failures in a large distributed environment. The multi-level quorum method operates on a logical hierarchy of the nodes in the network and applies well known flat voting algorithms for replicated data concurrency control in a layered fashion. We show how the number of hierarchy levels, the number of logical entities per level and the voting algorithms used on each level affect the costs and the degree of availability associated with a wide range of multi-level quorum schemes. The results of the analysis are used to provide guidelines for designing the most suitable multi-level quorum strategy for a given application scenario. Comparative performance measurements in a simulated network are presented to illustrate the properties of multi-level approaches when some of the assumptions of the analytical investigation do not hold.
A new indexing technique for rapid evaluation of nested query on composite object is propoced, reducing the overall cost for retrieval and update. An extended B+ tree is introduced in which object identifier (OID) to be searched and path information usud for update of index record are stored in leaf node and subleaf node, respectively. In this method, the retrieval oeration is applied only for OIDs in the leaf node. The index records of both leaf and subleaf nodes are updated in such a way that the path information in the subleaf node and OIDs in the leaf node are reorganized by deleting and inserting the OIDs. The techniaue presented offers advantages over currently related indexing techniques in data reorganization and index allocation. In the proposed index record, the OIDs to be reorganized are always consecutively provided, and thus only the record directory is updated when an entire page should be removed. In addition, the proposed index can be allocate to a path with the length greater than 3 without splitting the path. Comparisons under a variety of conditions are given with current indexing techniques, showing improved performance in cost, i.e., the total number of pages accessed for retrieval and update.
Marco A. Amaral HENRIQUES Takashi YAHAGI
In most of the methods proposed so far to design approximately linear phase IIR digital filters (IIR DFs), the design takes place only in the time or in the frequency domain. However, when both magnitude and phase responses are considered, IIR DFs with better frequency responses can be obtained if their characteristics in both domains are taken into account. This paper proposes a design method for approximately linear phase IIR DFs, which is based on parameter estimation techniques in the time domain followed by a nonlinear optimization algorithm in the frequency domain. Several examples are presented, illustrating the proposed method.
Yoichi NAGAO Hideaki OHTA Hironobu URABE Sadatoshi KUMAGAI
This paper describes a programming system, K-NET for the development of control software for flexible manufacturing systems composed of robots, numerically-controlled machines, transfer machines and automatic storage/retrieval systems. K-NET is based on a high-level Petri net which makes it simple to express operational functions such as synchronization, interlock and concurrence in sequence control. Petri net in K-NET is colored one in which tokens have attributes, and timed one which can provide a notion of stochastic time. K-NET provides many kinds of boxes having specific functions, and gates specified the firing condition and the token flow control with IF-THEN rules. On the other hand, procedural language can be also used for information processing. K-NET can support all development stages including general design, detailed design, programming and testing. K-NET has an editor to input control specifications expressed with Petri net; a simulator to verify edited specifications; a generator to convert the net to C source programs for a computer or to ladder diagrams for a programmable controller; a reporter to print control specifications; and a monitor to display controller status in real-time. K-NET has been used in the development of control software for an automated guided vehicle system, and results show a 2/3rds cost-saving over development with conventional methods in which only procedural language is used.
Yoshiki YAMAUCHI Osaake NAKAJIMA Koichi NAGATA Hiroshi ITO Tadao ISHIBASHI
A one-by-four static frequency divider using AlGaAs/GaAs heterojunction bipolar transistors (HBTs) was designed to operate at a bias condition that gave a maximum cutoff frequency fT and a maximum oscillation freqency fmax. The fT and fmax applied to the divider were 68 GHz and 56 GHz, respectively. As a result of the tests, the circuit operated up to 34.8 GHz at a power supply voltage of 9 V and power dissipation of 495 mW. A low minimum input signal power level of 0 dBm was also achieved.
This paper describes a reduction algorithm for SW method which generates test sequences for communication systems. SW method is based upon the Finite State Machine (FSM). SW method uses a set of characterizing sequences and a state transition checking approach. This paper concentrates the characteristics of the SW sequences, and proposes the new derivation algorithm of characterizing sequences. Furthermore, Chinese Postman Tour and Extended Chinese Postman Tour is proposed to reduce redundancy of the SW sequences. This paper also presents an evaluation of this method in terms of an upper bound of the sequence length and generated test sequence length. The evaluation shows that the algorithm dramatically reduces the sequence length of the original method.
Yoshimi ASADA Yasuhiro NAKASHA Norio HIDAKA Takashi MIMURA Masayuki ABE
We developed a 32-bit pseudorandom number generator (RNG) operating at liquid nitrogen temperature based on HEMT ICs. It generates maximum-length-sequence codes whose primitive polynomial is X47+X42+1 with the period of 247-1 clock cycle. We designed and fabricated three kinds of cryogenic HEMT IC for this system: A 1306-gate controller IC, a 3319-gate pseudorandom number generator (RNG) IC, and a buffer IC containing a 4-kb RAM and 514 gates. We used 0.6-µm gate-length Se-doped GaAlAs/GaAs HEMTs. Interconnects were Al for the first layer and Au/Pt/Ti for the second layer with a SiON insulator between them. The HEMT ICs have direct-coupled FET logic (DCFL) gates internally and emitter-coupled logic (ECL) compatible input-putput buffers. The unloaded basic delay of the DCFL gate was 17 ps/gate with a power consumption of 1.4 mW/gate at liquid nitrogen temperature. We used an automatic cryogenic wafer probe we developed and an IC tester for function tests, and used a high-speed performance measuring system we also developed with a bandwidth of more than 20 GHz for high-speed performance tests. Power dissipations were 3.8 W for the controller IC, 4.5 W for the RNG IC, and 3.0 W for the buffer IC. The RNG IC, the largest of the three HEMT ICs, had a maximum operating clock rate of 1.6 GHz at liquid nitrogen temperature. We submerged a specially developed zirconium ceramic printed circuit board carrying the HEMT ICs in a closed-cycle cooling system. The HEMT ICs were flip-chip-packaged on the board with bumps containing indium as the principal component. We confirmed that the RNG system operates at liquid nitrogen temperature and measured a minimum system clock period of 1.49 ns.
Boolean unification is an algorithm to obtain the general solution of a given Boolean equation. Since a general solution provides a way to represent a complete don't care set, Boolean unification can be a powerful technique when applied to logic synthesis. In this paper we present various applications of Boolean unification to combinational logic synthesis. Three topics of combinational logic synthesis: redesign, multi-level logic minimization and minimization of Boolean relations are discussed. All these problems can be uniformly formalized as Boolean equations. Experimental results are also reported.
Masahiro HIGUCHI Hiroyuki SEKI Tadao KASAMI
Many practical communication protocols provide priority service as well as ordinary service. In such a protocol, the protocol machines can initiate a priority service at most of the states. This characteristic leads an extreme increment of the number of state transitions on the protocol machines and causes state space explosion in verification of safety property of the protocol. This paper describes a method of constructing a communication protocol from composition of a subprotocol for ordinary service and that for priority service. This paper also presents a sufficient condition for a composed protocol to inherit safety property from the subprotocols. By using the composition method and the sufficient condition, the decision problem for safety property of the composed protocol can be reduced to those of the subprotocols. An experimental result of verification of a part of OSI session protocol is also described. The result shows that the method can reduce the computation time for verifying safety property to about 3% against the naive way.
Kiyoharu HAMAGUCHI Hiromi HIRAISHI Shuzo YAJIMA
Recently, Burch et al. proposed symbolic model checking method to verify sequential machines formally. The method, which is based on logic function manipulation using binary decision diagram, can handle large sequential machines that cannot be handled by the conventional techniques. The expressive power of Computational Tree Logic (CTL), which was used by Burch et al., is not very powerful, for example, CTL cannot describe repetition of events. This papers shows an extension of the symbolic model checking algorithm to Branching time regular temporal logic (BRTL), which has been proposed by the authors as an improvement of CTL in terms of expressive power. The implemented verifier based on the proposed algorithm could verify behaviors of a microprocessor composed of approximately 1,600 gates and 68 flipflops.
Takeshi AGUI Haruo KITAGAWA Tomoharu NAGAO
A process of mixing viscous fluids, such as oil-based paints is applied to generate marble patterns. It is difficult to get the exact flow function of the viscous fluid, then we express the flow in terms of velocity vectors derived from simplified flow phenomena, in which the viscous liquid is supposed to be a collection of finite liquid elements. The position change of each element is calculated as the function of time and several examples of the obtained marble patterns are illustrated.
This paper describes the integration of a qualitative method and a quantitative method by Bottleneck Diagnosis/Improvement Expert Systems for Synchronized queueing network (BDES-S and BIES-S). On the basis of qualitative reasoning, BDES-S can carry out parameter tuning in order to diagnose and improve bottlenecks of synchronized queueing networks. BDES-S can produce several alternative qualitative improvement plans for one bottleneck server. BIES-S can produce quantitative improvement equations for each qualitative improvement plan. Our method using BDES-S and BIES-S can integrate both quantitative and qualitative methods for parameter tuning on complicated queueing synchronized networks.
Shigenori KINJO Hiroshi OCHI Yoshitatsu TAKARA
In case of the system identification problem, such as an echo canceller, estimated impulse response obtained by the frequency-domain adaptive filter based on the circular convolution has estimation error because the unknown system is based on the linear convolution in the time domain. In this correspondence, we consider a sufficient condition to reduce the estimation error.
Akira MATSUSHIMA Tokuya ITAKURA
An accurate numerical solution is presented for the electromagnetic scattering from infinite strip gratings attached to both sides of a dielectric slab. This structure is a model of polarization discriminating devices. The period of the strips is common to both planes, but the widths and the axes may be different. The direction of propagation and the polarization of an incident plane wave are arbitray. We derive a set of singular integral equations and solve it by the moment method, where the Chebyshev polynomials are successfully used as the basis and the testing functions. This method is accurate and effective owing to the incorporation of the edge condition and the decomposition of the kernel functions into the singular and the regular parts. Numerical calculations are carried out for the purpose of designing polarization discriminators, and it is shown that the band width is widened by decreasing the permittivity of the slab. The cross-polarization characteristics at skew incidence are also discussed.