We point out that the interval algorithm can be expressed in the form of a shift on the sequence space. Then we clarify that, by using a Bernoulli process, the interval algorithm can generate only a block of Markov chains or a sequence of independent blocks of Markov chains but not a stationary Markov process. By virtue of the finitary coding constructed by Hamachi and Keane, we obtain the procedure, called the finitary interval algorithm, to generate a Markov process by using the interval algorithm. The finitary interval algorithm also gives maps, defined almost everywhere, which transform a Markov measure to a Bernoulli measure.
Takashi IMAMICHI Hiroshi NAGAMOCHI
In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm for spheres based on slab partitioning technique and a plane sweep method. We derive a theoretical upper bound on the time complexity of the algorithm. Our bound tells that if both the dimension and the maximum ratio of radii of two spheres are bounded, then our algorithm runs in O(n log n + K) time with O(n + K) space, where K denotes the number of pairs of colliding spheres.
Masakazu YAGI Takashi HISAKADO Kohshi OKUMURA
Harmonic balance (HB) method is well known principle for analyzing periodic oscillations on nonlinear networks and systems. Because the HB method has a truncation error, approximated solutions have been guaranteed by error bounds. However, its numerical computation is very time-consuming compared with solving the HB equation. This paper proposes an algebraic representation of the error bound using Grobner base. The algebraic representation enables to decrease the computational cost of the error bound considerably. Moreover, using singular points of the algebraic representation, we can obtain accurate break points of the error bound by collisions.
Kang ZHAO Jinian BIAN Sheqin DONG Yang SONG Satoshi GOTO
Programming the multiprocessor system-on-chip (MPSoC) requires partitioning the sequential reference programs onto multiple processors running in parallel. However, designers still need to partition the code manually due to the lack of automated partition techniques. To settle this issue, this paper proposes a partition exploration algorithm based on the search space smoothing techniques, and implements the proposed method using a commercial extensible processor (Xtensa LX2 processor from Tensilica Inc.). We have verified the feasibility of the algorithm by implementing the MPEG2 benchmark on the Xtensa-based two-processor system. The final experimental results indicate a performance improvement of at least 1.6 compared to the single-processor system.
Feng YANG Yu ZHANG Jian SONG Changyong PAN Zhixing YANG
Based on the expectation-maximization (EM) algorithm, an iterative time-domain channel estimation approach capable of using a priori information is proposed for orthogonal frequency division multiplexing (OFDM) systems in this letter: it outperforms its noniterative counterpart in terms of estimation accuracy as well as bit error rate (BER) performance. Numerical simulations demonstrate that an SNR gain of 1 dB at BER=10-4 with only one iteration and estimation mean square error (MSE) which nearly coincides with the Cramer-Rao bound (CRB) in the low SNR region can be obtained, thanks to the efficient use of a priori information.
IEEE 802.16 broadband wireless access (BWA) technology is suitable for providing multimedia applications without accessing the wired networks directly. Although IEEE 802.16 standard well defines the quality of service (QoS) framework, it makes no specific recommendation with regard to the bandwidth allocation. In this paper, we propose an algorithm for allocating bandwidth in response to dynamic changes in the arrival rate such that the total bandwidth is efficiently utilized.
Kostas PSANNIS Yutaka ISHIBASHI
The H.264/AVC standard provides several new error-resilient features to enable the reliable transmission of compressed video signals over lossy packet networks. Flexible Macroblock Ordering (FMO) is one of the most interesting resilient features within the H.264/AVC standard. Unlike former standards, in which slices were constructed out of consecutive raster scan macroblocks, FMO suggests new slices composed of spatially distributed Macroblocks (MBs), and organized in a mixed-up fashion. H.264/AVC specifies seven types of FMO. The standard defines also an explicit FMO type (Type 6), which allows explicitly assignment of each MB within the frame to any available slice groups. Therefore new FMO types can be used and integrated into H264/AVC without violating the standard. In this paper we propose a new Explicit Chessboard-Wipe (ECW) Flexible Macroblocks Ordering (FMO) technique, which outperforms all other FMO types. The new ECW ordering results in effective error scattering which maximizes the number of correctly received macroblocks located around corrupted macroblocks, leading to better error concealment. Performance evaluations demonstrate that the proposed Explicit FMO approach outperforms all the FMO types. Both subjective and objective visual quality comparative study has been also carried out in order to validate the proposed approach.
Todorka ALEXANDROVA Hiroyoshi MORITA
Constructing ideal (t,n) threshold secret sharing schemes leads to some limitations on the maximum number of users, that are able to join the secret sharing scheme. We aim to remove these limitations by reducing the information rate of the constructed threshold secret sharing schemes. In this paper we propose recursive construction algorithms of (t,n) threshold secret sharing schemes, based on the generalized vector space construction. Using these algorithms we are able to construct a (t,n) threshold secret sharing scheme for any arbitrary n.
Shangce GAO Hongwei DAI Jianchen ZHANG Zheng TANG
Based on the clonal selection principle proposed by Burnet, in the immune response process there is no crossover of genetic material between members of the repertoire, i.e., there is no knowledge communication during different elite pools in the previous clonal selection models. As a result, the search performance of these models is ineffective. To solve this problem, inspired by the concept of the idiotypic network theory, an expanded lateral interactive clonal selection algorithm (LICS) is put forward. In LICS, an antibody is matured not only through the somatic hypermutation and the receptor editing from the B cell, but also through the stimuli from other antibodies. The stimuli is realized by memorizing some common gene segment on the idiotypes, based on which a lateral interactive receptor editing operator is also introduced. Then, LICS is applied to several benchmark instances of the traveling salesman problem. Simulation results show the efficiency and robustness of LICS when compared to other traditional algorithms.
Shan DING Hiroyuki TOMIYAMA Hiroaki TAKADA
An advanced communication system, the FlexRay system, has been developed for future automotive applications. It consists of time-triggered clusters, such as drive-by-wire in cars, in order to meet different requirements and constraints between various sensors, processors, and actuators. In this paper, an approach to static scheduling for FlexRay systems is proposed. Our experimental results show that the proposed scheduling method significantly reduces up to 36.3% of the network traffic compared with a past approach.
Seungwu HAN Masaaki FUJIYOSHI Hitoshi KIYA
This paper proposes an image authentication method that detects tamper and localizes tampered areas efficiently. The efficiency of the proposed method is summarized as the following three points. 1) This method offers coarse-to-fine tamper localization by hierarchical data hiding so that further tamper detection is suppressed for blocks labeled as genuine in the uppper layer. 2) Since the image feature description in the top layer is hidden over an image, the proposed method enciphers the data in the top layer rather than enciphers all data in all layers. 3) The proposed method is based on the reversible data hiding scheme that does not use highly-costed compression technique. These three points makes the proposed method superior to the conventional methods using compression techniques and methods using multi-tiered data hiding that requires integrity verification in many blocks even the image is genuine. Simulation results show the effectiveness of the proposed method.
Takuya KITAMOTO Tetsu YAMAGUCHI
H∞ optimal control is one of the most successful achievements in the post modern control theory. In the H∞ optimal control, we design a controller that minimizes the H∞ norm of a given system. Although the algorithms to solve the problem have already been reported, they focus on numerical systems (systems without any unknown parameters) and, can not be applied for parametric systems (systems with unknown parameters). Given a parametric system, this paper presents an algorithm to compute the optimal H∞ norm of the system achieved by an output feedback controller. The optimal H∞ norm is expressed as , where φ(k) denotes a root of a bivariate polynomial. A numerical example is given to show the effectiveness of the algorithm.
Helmut JUNG Herve BLANCK Wolfgang BOSCH Jim MAYOCK
The GaAs industry has been growing immensely during recent years. This is mainly driven by the tremendous growth of the wireless communication market, which is still continuously growing. Additionally, an emerging mmW market with applications in automotive, defense and optoelectronics is further driving the demand for GaAs components. The two largest European GaAs fabrication companies, UMS and Filtronic are very well positioned to address the complete frequency range from 1 GHz up to 100 GHz for commercial, high volume low cost markets, as well as individual niche applications. An overview of the companies' structures, their processes and design capabilities and also their new product developments will be presented in this paper.
Jin-Ping AO Yuya YAMAOKA Masaya OKADA Cheng-Yu HU Yasuo OHNO
The mechanism of current collapse of AlGaN/GaN heterojunction field-effect transistors (HFETs) was investigated by gate bias stress with and without illumination. It is clarified that there are two positions where negative charges accumulate, at the gate edge and in the bulk epi-layer. In the gate-edge mode, the charge comes either through the passivation film or the AlGaN layer, depending on the resistance of the films. Reduction of leakage current in the passivation film will be important to suppress the surface-related collapse.
Sungwook KIM Sungyong PARK Sooyong PARK Sungchun KIM
In this letter, we propose a new energy efficient online routing algorithm for QoS-sensitive sensor networks. An important design principle underlying our algorithm is online decision making based on real time network estimation. This on-line approach gives adaptability and flexibility to solve a wide range of control tasks for efficient network performance. In addition, our distributed control paradigm is practical for real sensor network management. Simulation results indicate the superior performance of our algorithm between energy efficiency and QoS provisioning.
Erin-Ee-Lin LAU Wan-Young CHUNG
A novel RSSI (Received Signal Strength Indication) refinement algorithm is proposed to enhance the resolution for indoor and outdoor real-time location tracking system. The proposed refinement algorithm is implemented in two separate phases. During the first phase, called the pre-processing step, RSSI values at different static locations are collected and processed to build a calibrated model for each reference node. Different measurement campaigns pertinent to each parameter in the model are implemented to analyze the sensitivity of RSSI. The propagation models constructed for each reference nodes are needed by the second phase. During the next phase, called the runtime process, real-time tracking is performed. Smoothing algorithm is proposed to minimize the dynamic fluctuation of radio signal received from each reference node when the mobile target is moving. Filtered RSSI values are converted to distances using formula calibrated in the first phase. Finally, an iterative trilateration algorithm is used for position estimation. Experiments relevant to the optimization algorithm are carried out in both indoor and outdoor environments and the results validated the feasibility of proposed algorithm in reducing the dynamic fluctuation for more accurate position estimation.
Keita MATSUDA Takeshi KAWASAKI Ken NAKATA Takeshi IGARASHI Seiji YAEGASSI
To reduce the gate leakage current of AlGaN/GaN HEMTs, we selected ITO/Ni/Au for Schottky electrodes and Schottky characteristics were compared with those of Ni/Au electrodes. ITO/Ni/Au and Ni/Au electrodes were deposited by vacuum evaporation and annealed at 350 in nitrogen atmosphere. From the I-V evaluation results of ITO/Ni/Au electrodes, forward and reverse leakage currents were reduced. Schottky characteristics of ITO/Ni/Au electrodes were also improved compared to these of Ni/Au electrodes. In addition, substantial decrease of leakage currents was confirmed after the annealing of HEMTs with ITO/Ni/Au electrodes. This may be explained that ITO/AlGaN interface state became lower by the annealing. By the temperature dependence of I-V curves, clear dependence was confirmed for the gates with ITO/Ni/Au electrodes. On the other hand, small dependence was observed for those with Ni/Au electrodes. From these results, tunnel leakage currents were dominant for the gates with Ni/Au electrode. Thermal emission current was dominant for the gates with ITO/Ni/Au electrode. The larger temperature dependence was caused that ITO/AlGaN interface states were smaller than those for Ni/Au electrode. It was suggested that suppressed AlGaN Schottky barrier thinning was caused by the surface defect donors, then tunneling leakage currents were decreased. We evaluated HEMT characteristics with ITO/Ni/Au electrode and Ni/Au electrode. Id max and Gm max were similar characteristics, but Vth with ITO/Ni/Au electrode was shifted +0.4 V than that with Ni/Au electrode due to the higher Schottky barrier. It was confirmed to have a good pinch-off currents and low gate leakage currents by ITO/Ni/Au electrodes.
Jihong GUAN Shuigeng ZHOU Yan CHEN
As GML is becoming the de facto standard for geographic data storage, transmission and exchange, more and more geographic data exists in GML format. In applications, GML documents are usually very large in size because they contain a large number of verbose markup tags and a large amount of spatial coordinate data. In order to speedup data transmission and reduce network cost, it is essential to develop effective and efficient GML compression tools. Although GML is a special case of XML, current XML compressors are not effective if directly applied to GML, because these compressors have been designed for general XML data. In this paper, we propose GPress, a compressor for effectively compressing GML documents. To the best of our knowledge, GPress is the first compressor specifically for GML documents compression. GPress exploits the unique characteristics of GML documents to achieve good performance. Extensive experiments over real-world GML documents show that GPress evidently outperforms XMill (one of the best existing XML compressors) in compression ratio, while its compression efficiency is comparable to the existing XML compressors.
Shengling WANG Yong CUI Rajeev KOODLI Yibin HOU Zhangqin HUANG
Due to the dynamics of topology and resources, Call Admission Control (CAC) plays a significant role for increasing resource utilization ratio and guaranteeing users' QoS requirements in wireless/mobile networks. In this paper, a dynamic multi-threshold CAC scheme is proposed to serve multi-class service in a wireless/mobile network. The thresholds are renewed at the beginning of each time interval to react to the changing mobility rate and network load. To find suitable thresholds, a reward-penalty model is designed, which provides different priorities between different service classes and call types through different reward/penalty policies according to network load and average call arrival rate. To speed up the running time of CAC, an Optimized Genetic Algorithm (OGA) is presented, whose components such as encoding, population initialization, fitness function and mutation etc., are all optimized in terms of the traits of the CAC problem. The simulation demonstrates that the proposed CAC scheme outperforms the similar schemes, which means the optimization is realized. Finally, the simulation shows the efficiency of OGA.
Toshiharu MARUI Shinich HOSHI Masanori ITOH Isao TAMAI Fumihiko TODA Hideyuki OKITA Yoshiaki SANO Shohei SEKI
In AlGaN/GaN high electron mobility transistors (HEMTs), drain current reduction by current collapse phenomenon is a big obstacle for a high efficient operation of power amplifier application. In this study, we investigated the effects of SiN passivation film quality on the electrical characteristics of AlGaN/GaN HEMTs. First, we conducted some experiments to investigate the relationship between electrical characteristics of AlGaN/GaN HEMTs and various conditions of SiN passivation film by plasma enhanced chemical vapor deposition (PE-CVD). We found that both gate current leakage and current collapse were improved simultaneously by SiN passivation film deposited by optimized condition of NH3 and SiH4 gas flow. It is found that the critical parameter in the optimization is a IN-H/ ISi-H ratio measured by Fourier transforms infrared spectroscopy (FT-IR) spectra. Next, a thermal CVD SiN was applied to the passivation film to be investigated from the same point of view, because a thermal CVD SiN is well known to have good quality with low hydrogen content and high IN-H/ISi-H ratio. We confirmed that the thermal CVD SiN passivation could improve much further both of the gate leakage current and the current collapse in AlGaN/GaN-HEMTs. Furthermore, we tried to apply the thermal CVD SiN to the gate insulator in MIS (Metal Insulator Semiconductor) structure of AlGaN/GaN HEMTs. The thermal CVD SiN passivation was more suitable for the gate insulator than PE-CVD SiN passivation in a view of reducing current collapse phenomena. It could be believed that the thermal CVD SiN film is superior to the PE-CVD SiN film to achieve good passivation and gate insulator film for AlGaN/GaN HEMTs due to the low hydrogen content and the high IN-H/ISi-H ratio.