It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c!n)O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.
Chi-Hui HUANG Shyh-Neng LIN Shiunn-Jang CHERN Jiun-Je JIAN
The convergence speed of the conventional adaptive LMS algorithms for time delay estimation (TDE) is highly dependent on the spectral distribution of the desired random source signals of interest, thus the performance of TDE might be degraded, dramatically. To solve this problem, in this letter, a DCT-transform domain constrained adaptive normalized-LMS filtering scheme, referred to as the adaptive constrained DCT-LMS algorithm, is devised for TDE. Computer simulation results verify that the proposed scheme can be used to achieve desired performance, for input random signals with different spectral distributions; it outperforms the unconstrained DCT-LMS and time-domain constrained adaptive LMS algorithms.
Shigeaki HARADA Eiji TAKIMOTO Akira MARUOKA
We consider the problem of dynamically apportioning resources among a set of options in a worst-case online framework. The model we investigate is a generalization of the well studied online learning model. In particular, we allow the learner to see as additional information how high the risk of each option is. This assumption is natural in many applications like horse-race betting, where gamblers know odds for all options before placing bets. We apply Vovk's Aggregating Algorithm to this problem and give a tight performance bound. The results support our intuition that it is safe to bet more on low-risk options. Surprisingly, the loss bound of the algorithm does not depend on the values of relatively small risks.
Daigo KIKUTA Jin-Ping AO Junya MATSUDA Yasuo OHNO
A model for the enhancement-mode operation of an AlGaN/GaN metal-insulator-semiconductor heterostructure field-effect transistor (MIS-HFET) under DC and AC conditions is proposed. In DC operation at positive gate voltages, the MIS-HFET can be divided into a transistor area and a resistor area due to the diode nature of the insulator/AlGaN interface. The transistor area shrinks with the increases in gate voltage. The intrinsic-transistor gate-length reduction causes a drain current increase. The I-V characteristics based on the gradual channel approximation are derived. The ID hysteresis of the MIS-HFET is investigated by a circuit simulation using SPICE. We have confirmed that the hysteresis was caused by the phase difference between the potential variation of the gate insulator/AlGaN interface and that of the gate electrode due to CR components in the gate structure.
Donghyung KIM Jongho KIM Jechang JEONG
The H.264 standard allows each macroblock to have up to sixteen motion vectors, four reference frames, and a macroblock mode. Exploiting this feature, we present an efficient temporal error concealment algorithm for H.264-coded video. The proposed method turns out to show good performance compared with conventional approaches.
Cheng-Hong YANG Li-Yeh CHUANG Cheng-Huei YANG Ching-Hsing LUO
In this paper, Morse code is selected as a communication adaptive device for persons whose hand coordination and dexterity are impaired by such ailments as amyotrophic lateral sclerosis, multiple sclerosis, muscular dystrophy, and other severe handicaps. Morse code is composed of a series of dots, dashes, and space intervals, and each element is transmitted by sending a signal for a defined length of time. A suitable adaptive automatic recognition method is needed for persons with disabilities due to their difficulty in maintaining a stable typing rate. To overcome this problem, the proposed method combines the support vector machines method with a variable degree variable step size LMS algorithm. The method is divided into five stages: tone recognition, space recognition, training process, adaptive processing, and character recognition. Statistical analyses demonstrated that the proposed method elicited a better recognition rate in comparison to alternative methods from the literature.
Yoshikazu HIROSE Akira HONSHIO Takeshi KAWASHIMA Motoaki IWAYA Satoshi KAMIYAMA Michinobu TSUDA Hiroshi AMANO Isamu AKASAKI
The correlation between ohmic contact resistivity (ρc) and transconductance (gm) in AlGaN/GaN high-electron-mobility transistors (HEMTs) was investigated. To characterize ρc precisely, we fabricated a circular transmission line model (c-TLM) pattern adjoined to a field-effect transistor (FET) pattern on an HEMT. By measuring ohmic contact resistance and sheet resistance using the adjoined c-TLM, intrinsic transconductance (gm0), which is not influenced by the source resistance, can be estimated. The gm0 thus obtained is between 179 and 206 mS/mm. Then, it became possible to calculate the correlation between gm and (ρc. We found that ρc should be below 10-5 Ωcm2 for the improvement of gm in AlGaN/GaN HEMT when Rsh 400 Ω/.
Yong CAI Yugang ZHOU Kei May LAU Kevin J. CHEN
Based on fluoride-based plasma treatment of the gate region in AlGaN/GaN HEMTs and post-gate rapid thermal annealing (RTA), enhancement mode (E-mode) AlGaN/GaN HEMTs with low on-resistance and low knee-voltage were fabricated. The fabricated E-mode AlGaN/GaN HEMT with 1 µm-long gate exhibits a threshold voltage of 0.9 V, a knee-voltage of 2.2 V, a maximum drain current density of 310 mA/mm, a peak gm of 148 mS/mm, a current gain cutoff frequency fT of 10.1 GHz and a maximum oscillation frequency fmax of 34.3 GHz. In addition, the fluoride-based plasma treatment was also found to be effective in lowering the gate leakage current, in both forward and reverse bias. Two orders of magnitude reducation in gate leakage current was observed in the fabricated E-mode HEMTs compared to the conventional D-mode HEMTs without fluoride-based plasma treatment.
Accumulation of non-equilibrium longitudinal optical (LO) phonons (termed hot phonons) is considered as a possible cause for limitation of frequency of operation of GaN-based high-electron-mobility transistors (HEMTs). The experimental data on noise temperature of hot electrons at a microwave frequency as a function of supplied electric power is used to extract information on hot phonons: the hot-phonon lifetime, the equivalent hot-phonon temperature, the effective occupancy of hot-phonon states involved into electron-LO-phonon interaction. The possible ways for controlling the hot-phonon effect on electron drift velocity through variation of electron density, channel composition, and hot-phonon lifetime are discussed. The expected dependence of hot-electron drift velocity on hot-phonon lifetime is confirmed experimentally. A self-consistent explanation of different frequency behaviour of InP-based and GaN-based HEMTs is obtained from a comparative study of hot-phonon effects.
Mehdi EZOJI Karim FAEZ Hamidreza RASHIDY KANAN Saeed MOZAFFARI
Point pattern matching (PPM) arises in areas such as pattern recognition, digital video processing and computer vision. In this study, a novel Genetic Algorithm (GA) based method for matching affine-related point sets is described. Most common techniques for solving the PPM problem, consist in determining the correspondence between points localized spatially within two sets and then find the proper transformation parameters, using a set of equations. In this paper, we use this fact that the correspondence and transformation matrices are two unitary polar factors of Grammian matrices. We estimate one of these factors by the GA's population and then evaluate this estimation by computing an error function using another factor. This approach is an easily implemented one and because of using the GA in it, its computational complexity is lower than other known methods. Simulation results on synthetic and real point patterns with varying amount of noise, confirm that the algorithm is very effective.
Masaya OKADA Ryohei TAKAKI Daigo KIKUTA Jin-Ping AO Yasuo OHNO
This investigation of the temperature and illumination effects on the AlGaN/GaN HFET threshold voltage shows that it shifts about -1 V under incandescent lamp or blue LED illumination, while almost no shift takes place under red LED illumination. The temperature coefficient for the threshold voltage shift is +3.44 mV/deg under the illuminations and +0.28 mV/deg in darkness. The threshold voltage variation can be attributed to a virtual back-gate effect caused by light-generated buffer layer potential variations. The expressions for the potential variation are derived using Shockley-Read-Hall (SRH) statistics and the Maxwell-Boltzmann distribution for the carriers and deep traps in the buffer layer. The expressions indicate that large photoresponses will occur when the electron concentration in the buffer layer is extremely small, that is, highly resistive. In semi-insulating substrates, the substrate potential varies so as to keep the trap occupation function constant. The sign and the magnitude of the threshold voltage variation are explained by the shift of the pinning energy calculated from the Fermi-Dirac distribution function.
Masayuki ABE Hiroyuki NAGASAWA Stefan POTTHAST Jara FERNANDEZ Jorg SCHORMANN Donat Josef AS Klaus LISCHKA
Phase pure cubic (c-) GaN/AlGaN heterostructures on 3C-SiC free standing (001) substrates have successfully been developed. Almost complete (100%) phase pure c-GaN films are achieved with 2-nm surface roughness on 3C-SiC substrate and stoichiometric growth conditions. The polarization effect in c-GaN/AlGaN has been evaluated, based on measuring the transition energy of GaN/AlGaN quantum wells (QWs). It is demonstrated that the polarization electric fields are negligible small in c-GaN/AlGaN/3C-SiC compared with those of hexagonal (h-)GaN/AlGaN, 710 kV/cm for Al content x of 0.15, and 1.4 MV/cm for x of 0.25. A sheet carrier concentration of c-GaN/AlGaN heterojunction interface is estimated to 1.61012 cm-2, one order of magnitude smaller than that of h-GaN/AlGaN. The band diagrams of c-GaN/AlGaN HEMTs have been simulated to demonstrate the normally-off mode operation. The blocking voltage capability of GaN films was demonstrated with C-V measurement of Schottky diode test vehicle, and extrapolated higher than 600 V in c-GaN films at a doping level below 51015 cm-3, to show the possibility for high power electronics applications.
Aloys MVUMA Shotaro NISHIMURA Takao HINAMOTO
In this letter we present steady-state analyses of a gradient algorithm (GA) for second-order adaptive infinite impulse response (IIR) notch filters. A method for deriving more accurate estimation mean square error (MSE) expressions than the recently proposed method is presented. The method is based on the estimation error power spectral density (PSD). Moreover, an expression for the estimation bias for the adaptive IIR notch filter with constrained poles and zeros is shown to be obtained from the estimation MSE expression. Simulations are presented to confirm the validity of the analyses.
Shigeaki KUZUOKA Tomohiko UYEMATSU
This paper investigates some relations among four complexities of sequence over countably infinite alphabet, and shows that two kinds of empirical entropies and the self-entropy rate regarding a Markov source are asymptotically equal and lower bounded by the maximum number of phrases in distinct parsing of the sequence. Some connections with source coding theorems are also investigated.
Shinichi HOSHI Toshiharu MARUI Masanori ITOH Yoshiaki SANO Shouhei SEKI
In AlGaN/GaN high electron mobility transistors (HEMTs), Si3N4 passivation film brings effective improvements in the current collapse phenomenon, however, the suppression of this phenomenon in a high voltage operation can not be achieved in only the Si3N4 deposition process. In order to solve this problem, we have demonstrated an NH3-plasma surface pretreatment in the chamber of plasma enhanced chemical vapor deposition (PE-CVD) just before Si3N4 deposition process. We found that the optimized NH3-plasma pretreatment could improve the current collapse as compared with only the Si3N4 deposition and an excessive pretreatment made it worse adversely in AlGaN/GaN-HEMTs. It was confirmed by Auger electron spectroscopy (AES) analysis that the optimized NH3-plasma pretreatment decreased the carbon contamination such as hydrocarbon on the AlGaN surface and the excessive pretreatment degraded the stoicheiometric composition of AlGaN surface.
Wouter CAARLS Pieter JONKER Henk CORPORAAL
Developing embedded parallel image processing applications is usually a very hardware-dependent process, often using the single instruction multiple data (SIMD) paradigm, and requiring deep knowledge of the processors used. Furthermore, the application is tailored to a specific hardware platform, and if the chosen hardware does not meet the requirements, it must be rewritten for a new platform. We have proposed the use of design space exploration [9] to find the most suitable hardware platform for a certain application. This requires a hardware-independent program, and we use algorithmic skeletons [5] to achieve this, while exploiting the data parallelism inherent to low-level image processing. However, since different operations run best on different kinds of processors, we need to exploit task parallelism as well. This paper describes how we exploit task parallelism using an asynchronous remote procedure call (RPC) system, optimized for low-memory and sparsely connected systems such as smart cameras. It uses a futures [16]-like model to present a normal imperative C-interface to the user in which the skeleton calls are implicitly parallelized and pipelined. Simulation provides the task dependency graph and performance numbers for the mapping, which can be done at run time to facilitate data dependent branching. The result is an easy to program, platform independent framework which shields the user from the parallel implementation and mapping of his application, while efficiently utilizing on-chip memory and interconnect bandwidth.
Chang Wook AHN Rudrapatna S. RAMAKRISHNA
This paper deals with questions concerning the supply of building-blocks (BBs) in the initial population of real-coded genetic algorithms (rGAs). Drawing upon the methodology of existing BB supply studies for finite alphabets, facetwise models for the supply of a single schema as well as for the supply of all the schemata in a partition are proposed. A model for the initial population size necessary to ensure the presence of all the raw BBs with a given supply error has also been developed using the partition success model. Experimental results show the effectiveness of the facetwise models and the initial population sizing model. Finally, an adaptation approach is suggested for practical use of the BB supply.
A hardware algorithm for computing the reciprocal of the Euclidean norm of a 3-dimensional (3-D) vector which appears frequently in 3-D computer graphics is proposed. It is based on a digit-recurrence algorithm for computing the Euclidean norm and an on-line division (on-line reciprocal computation) algorithm. These algorithms are modified, so that the reciprocal of the Euclidean norm is computed by performing on-line division where the divisor is the partial result of Euclidean norm computation. Division, square-rooting, and reciprocal square-root computation, which are important operations in 3-D graphics, can also be performed using a circuit based on the proposed algorithm.
Yuji KASAI Kiyoshi MIYASHITA Hidenori SAKANASHI Eiichi TAKAHASHI Masaya IWATA Masahiro MURAKAWA Kiyoshi WATANABE Yukihiro UEDA Kaoru TAKASUKA Tetsuya HIGUCHI
This paper proposes the combination of adjustable architecture and parameter optimization software, employing a method based on artificial intelligence (AI), to realize an image rejection mixer (IRM) that can enhance its image rejection ratio within a short period of time. The main components of the IRM are 6 Gilbert-cell multipliers. The tail current of each multiplier is adjusted by the optimization software, and the gain and phase characteristics are optimized. This adjustment is conventionally extremely difficult because the 6 tail currents to be adjusted simultaneously are mutually interdependent. In order to execute this adjustment efficiently, we employed a Genetic Algorithm (GA) that is a robust search algorithm that can find optimal parameter settings in a short time. We have successfully developed an IRM chip that has a performance of 71 dB and is suitable for single-chip integration with WCDMA applications.
Young-Ho YOON Hyung-Gyu LIM Jyung-Hyun LEE Hee-Joon PARK Il-Yong PARK Min-Kyu KIM Chul-Ho WON Byung-Seop SONG Jin-Ho CHO
In this paper, the voice signal processing module has been designed using the micro processor for the use of fully implantable middle ear devices (F-IMEHD). The voice signal processing module for F-IMEHD should be designed to compensate for the hearing loss of hearing impaired person and have the flexibility for compensating various hearing threshold level. So, the voice signal processing module has been designed and implemented to present the various frequency characteristics using the low-power micro processor, MSP430F169. The different voice signal path to the inner ear entrance was considered so that two voice signal would be combined in-phase using an all pass filter with a constant time-delay to improve the vibration of the ossicles.