Yoshinori TAKEI Toshinori YOSHIKAWA Xi ZHANG
As pseudorandom number generators for Monte Carlo simulations, inversive linear congruential generators (ICG) have some advantages compared with traditional linear congruential generators. It has been shown that a sequence generated by an ICG has a low discrepancy even if the length of the sequence is far shorter than its period. In this paper, we formulate fractional linear congruential generators (FCG), a generalized concept of the inversive linear congruential generators. It is shown that the sequence generated by an FCG is a geometrical shift of a sequence from an ICG and satisfies the same upper bounds of discrepancy. As an application of the general formulation, we show that under certain condition, "Leap-Frog technique," a way of splitting a random number sequence to parallel sequences, can be applied to the ICG or FCG with no extra cost on discrepancy.
Masataka TAKAMURA Yoshihide IGARASHI
We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.
TCP congestion control is receiving increased attention in recent years due to their usefulness for network stability, robustness use of network buffer and bandwidth resources on an end-to-end per-connection basis. The RED scheme was designed for a network where a single dropped packet is sufficient to signal the presence of congestion to the TCP protocol. This paper applies matrix-analytic approach to analyze both the long-term and the short-term drop behaviors of a queue with RED scheme and uses this model to quantify the benefits brought about by RED. The result shows that the drop probability between RED and Drop-Tail is very close under heavy load conditions. This indicates that RED not only can resolve the synchronization problem but also has the same loss performance with Drop-Tail scheme under the heavy load circumstances. Our findings also show that the rate oscillation behavior of RED is better than Drop-Tail when TCP applies the additive-increase and multiplication-decrease mechanism. As a consequence, it can help reduce the required buffer capacity in the RED router.
Eiju HIROWATARI Kouichi HIRATA Tetsuhiro MIYAHARA Setsuo ARIKAWA
This paper investigates the interaction of mind changes and anomalies for inductive inference of recursive real-valued functions. We show that the criteria for inductive inference of recursive real-valued functions by bounding the number of mind changes and anomalies preserve the same hierarchy as that of recursive functions, if the length of each anomaly as an interval is bounded. However, we also show that, without bounding it, the hierarchy of some criteria collapses. More precisely, while the class of recursive real-valued functions inferable in the limit allowing no more than one anomaly is properly contained in the class allowing just two anomalies, the latter class coincides with the class allowing arbitrary and bounded number of anomalies.
Masatoshi MORITA Katsushi INOUE Akira ITO Yue WANG
This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.
Akiyoshi SHIMADA Hiroshi NARUSE Kiyoshi UZAWA Gaku KIMURA Hideaki MURAYAMA Kazuro KAGEYAMA
This paper describes a method for assessing the structural integrity of International America's Cup Class (IACC) yachts using a fiber optic distributed strain sensor. IACC yachts are made of advanced composite materials designed for high stiffness and lightness, however, a number of critical accidents have occurred during sailing. So we developed a health monitoring system and applied it to two Japanese IACC yachts to measure the distributed strain by using an optical fiber sensor installed in their hulls. We then estimated the three-dimensional distributed strain and compared the results with simulated data obtained by finite element analysis (FEA) to confirm the designed strength of these yachts.
Muneo KUSHIMA Koichi TANNO Okihiko ISHIZUKA
In this paper, a voltage-controlled linear variable resistor (VCLVR) using a floating-gate MOSFET (FG-MOSFET) is proposed. First, the grounded VCLVR realization is discussed. The proposed circuit consists of only an ordinary MOSFET and an FG-MOSFET. The advantages of the proposed VCLVR are low-power and wide-input range and also the power consumption of the proposed VCLVR is the same as an ordinary passive resistor. The performance of the proposed circuits are confirmed by HSPICE simulations with a standard 0.6 µm CMOS process parameters. Simulations of the proposed VCLVR demonstrate a resistance value of 40 kΩ to 338 kΩ and an input range of 4.34 V within THD of less than 1.1%. Next, we proposed a new floating node linear variable resistor using the proposed VCLVR. The performance of the circuit is also evaluated through HSPICE.
Mitsuyoshi KISHIHARA Isao OHTA Tadashi KAWAI Kuniyoshi YAMANE
Directional couplers with flat coupling are designed by using an asymmetrical coupled-HNRD-guide consisting of two HNRD guides of different cross sections arranged closely. First, propagation characteristics of the asymmetrical coupled-HNRD-guide are analyzed by the transverse resonance technique. Next, the whole directional couplers including tapered sections are designed from the S-parameters of the coupled HNRD guides derived from a superposition of the even-like and odd-like modes. Finally, the validity of the design procedure is confirmed by an em-simulator (HFSS).
Hajime SHIBATA Soji MORI Nobuo FUJII
An automated synthesis for analog computational circuits in transistor-level configuration is presented. A cell-based structure is introduced to place moderate constraints on the MOSFET circuit topology. Even though each cell has a simple structure that consists of one current path with four transistors, common analog building blocks can be implemented using combinations of the cells. A genetic algorithm is applied to search circuit topologies and transistor sizes that satisfy given specifications. Synthesis capabilities are demonstrated through examples of three types of computational circuits; absolute value, squaring, and cubing functions by using computer simulations and real hardware.
Xiaotong HU Makoto FUJIMURA Yoko MAEMURA Hideo KURODA
In fractal image coding, for each range block, the best matching domain block is identified, and information from the best matching domains and range blocks are transmitted to the decoder for image reconstruction. In this paper, the similarity between range blocks and domain blocks is evaluated according to their centers of gravity. The number of searched domain blocks are reduced by limiting the candidates for the best matching domain blocks to those domain blocks whose similarity to the range block are high. Using simulation experiments, the number of candidates for the best matching domain blocks were reduced to about 10-23% of the current method. Thus, our proposed method had significantly reduced the number of searched domain blocks below the current method and at the same time it turns out that degradation of the reconstructed image was seldom observed.
Hiroshi TSUNODA Kohei OHTA Nei KATO Yoshiaki NEMOTO
Mobility management is a core issue in IP/LEO satellite network related research. The LEO system consists of wide network of moving satellites providing connectivity to any place on the earth. It implies that the system must support numerous wireless connections under high-mobility conditions. Existing mobility management protocols like Mobile IP suppose that two types of identities, indicating a unique name and position in the network, are dynamically bound in each handover. However, in the IP/LEO system, handovers are mainly caused by fast moving satellites, not moving nodes. As a result, quite a few binding update requests are generated during a short period by the moving satellites; this makes mobility management difficult. In this paper, we propose a new mobility management method that separates binding updates from handovers by using geographical location of the nodes. We evaluate the proposed method and show its effectiveness.
Hiroshi KUBO Masayuki MATSUSHITA Ikuo AWAI
The radiation patterns are synthesized by properly disposing surface variations on dielectric rod waveguides. The genetic algorithm (GA) is applied for searching the optimum disposition of variation sections. A very fast calculation method used in the optimization is presented. The guided waves are related in the form of a 2-port circuit and the radiation field is expressed by superposition of the waves from variation sections. Various conical beams can be synthesized. Short variation sections and combination of several variation sections with different height are used to improve the synthesis performance. The ripple of the mainlobe and the sidelobe levels become small. Spherical sector patterns with a steep fall are synthesized and the agreement with the experimental values is confirmed.
Ikjun YEOM A. L. Narasimha REDDY
Class-based delay differentiation model has been recently proposed as a part of relative differentiated services frameworks, and it is shown that the model can provide delay differentiation without admission control and end-to-end resource reservation. In this paper, however, we observe that there can be inconsistent delay differentiation caused by different size of packets. We propose packet size-based delay differentiation model and show that packet size-based queueing is effective to achieve equal delay within a class and provide consistent delay differentiation between classes through simulations. Simulation results also show that the proposed model improves jitter characteristics of CBR flows.
This letter presents the implementation framework of a video streaming server which uses an optical disk library as a source of media archiving. In order to handle the optical storage subsystem in the framework of disk-based stream service model, we have devised an effective stream scheduling, disk caching, and admission control mechanism. The proposed system has been implemented and its key principles are validated with real experiments.
Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.
One of the most important technical problems in reliable multicast protocol is reducing redundant feedback information, e.g. NAKs, to avoid feedback implosion. A number of feedback suppression mechanisms have been proposed to deal with this problem. In the MBONE, which is a virtual multicast network and makes multi-point communication across the Internet feasible, the source link, the links directly connected to or very close to the source, is reported to contribute high percentile packet loss. When a well-known NAK suppression mechanism is applied, in the case of the source link loss, all receivers suffer the same packet loss and NAK suppression mechanism does not work effectively. In this paper we propose a Reliable Multicast Protocol Applying Local FEC, called Local FEC, where the source link loss is recovered with FEC applied locally only to the source link. To investigate performance of our proposed protocol, it is compared with a popular reliable multicast protocol with NAK suppression mechanism. Our performance analysis results with mathematical analysis and computer simulation show that our proposed protocol outperforms the NAK suppression protocol from the viewpoint of scalability and wasted bandwidth.
Qing-Xin CHU Xiao-Juan HU Kam-Tai CHAN
In the FDTD simulation of microwave circuits, a device in very small size compared with the wavelength is often handled as a lumped element, but it may still occupy more than one cell instead of a wire structure without volume routinely employed in classical extended FDTD algorithms. In this paper, two modified extended FDTD algorithms incorporating a lumped element occupying more than one cell are developed directly from the integral form of Maxwell's equations based on the assumption whether displacement current exists inside the region where a device is present. If the displacement current exists, the modified extended FDTD algorithm can be represented as a Norton equivalent current-source circuit, or otherwise as a Thevenin equivalent voltage-source circuit. These algorithms are applied in the microwave line loaded by a lumped resistor and an active antenna to illustrated the efficiency and difference of the two algorithms.
Takao OGURA Junji SUZUKI Akira CHUGO Masafumi KATOH Tomonori AOYAMA
As use of the Internet continues to spread rapidly, Traffic Engineering (TE) is needed to optimize IP network resource utilization. In particular, load balancing with TE can prevent traffic concentration on a single path between ingress and egress routers. To apply TE, we have constructed an MPLS (Multi-Protocol Label Switching) network with TE capability in the JGN (Japan Gigabit Network), and evaluated dynamic load balancing behavior in it from the viewpoint of control stability. We confirmed that with this method, setting appropriate control parameter values enables traffic to be equally distributed over two or more routes in an actual large-scale network. In addition, we verified the method's effectiveness by using a digital cinema application as input traffic.
Katsutoshi SAEKI Yoshifumi SEKINE
In this paper, we propose the CMOS implementation of neuron models for an artificial auditory neural network. We show that when voltage is added directly to the control terminal of the basic circuit of the hardware neuron model, a change in the output firing is observed. Next, based on this circuit, a circuit that changes with time is added to the control terminal of the basic circuit of the hardware neuron model. As a result, a neuron model is constructed with ON firing, adaptation firing, and repetitive firing using CMOS. Furthermore, an improved circuit of a neuron model with OFF firing using CMOS which has been improved from the previous model is also constructed.
Takeshi ONIZAWA Masato MIZOGUCHI Tetsu SAKATA Masahiro MORIKURA
The adaptive phase tracking scheme for orthogonal frequency division multiplexing (OFDM) signals can provide superior PER performance in channels with varying phase noise power. It is an effective technique for achieving high-rate and high quality wireless transmission. This paper proposes a new simple adaptive phase tracking scheme for OFDM signals in order to realize high-rate wireless local area networks (LANs). The proposed scheme measures the integrated phase rotation in order to appropriately set the properties of the FIR filter in the phase tracking circuits. This scheme uses the fact that the integrated phase rotation is correlated to the phase noise power. Assuming an RMS delay spread of 100 ns, computer simulations show that the proposed scheme offers superior required Eb/N0 performance (with regard to the phase noise power) compared to the conventional fixed-tap scheme, where the phase noise to signal power ratios are below -18 dB. It also offers excellent PER performance at the packet length of 1000 bytes unlike the conventional schemes, which suffer degraded PER performance.