The virtual memory functions in real-time operating systems have been used in embedded systems. Recent RISC processors provide virtual memory supports through software-managed Translation Lookaside Buffer (TLB) in software. In real-time aspects of the embedded systems, managing TLB entries is the most important because overhead at TLB miss time gives a great effect to overall performance of the system. In this paper, we propose several TLB management algorithms in MIPS processors. In the algorithms, a replaced TLB entry is randomly chosen or managed. We analyze the algorithms by comparing overheads at task switching times and TLB miss times.
Chik-How TAN Xun YI Chee-Kheong SIEW
In this paper, we construct a new signature scheme which is provably secure against adaptive chosen message attack in the standard model under the strong RSA assumption. The proposed scheme is different from Cramer-Shoup scheme and Camenisch-Lysyanskaya scheme and is more efficient than them. The tradeoff of the proposed scheme is a slight increase of the secret key.
Pitak THUMWARIN Takenobu MATSUURA
In this paper, we propose an on-line writer recognition method for Thai numeral. A handwriting process is characterized by a change of numeral's shape, which is represented by two features, a displacement of pen-point position and an area of triangle determined from the two adjacent points of pen-point position and the origin. First, the above two features are expanded into Fourier series. Secondly, in order to describe feature of handwriting, FIR (Finite impulse response) system having the above Fourier coefficients as input and output of the system is introduced. The impulse response of the FIR system is used as the feature of handwriting. Furthermore, K-L expansion of the obtained impulse response is used to recognize writer. Writer recognition experiments are performed by using 3,770 data collected by 54 Thai writers for one year. The average of Type I (false rejection) error rate and Type II (false acceptance) error rate were 2.16% and 1.12%, respectively.
The history of the development of the High Electron Mobility Transistor (HEMT) is an outstanding illustration of how a new device can be successfully marketed. In this paper we discuss a key to successful commercialization of new devices.
Hiroki FUJIO Hiroyuki OKAMURA Tadashi DOHI
The software rejuvenation is a proactive fault management technique for operational software systems which age due to the error conditions that accrue with time and/or load, and is important for high assurance systems design. In this paper, fine-grained shock models are developed to determine the optimal rejuvenation policies which maximize the system availability. We introduce three kinds of rejuvenation schemes and calculate the optimal software rejuvenation schedules maximizing the system availability for respective schemes. The stochastic models with three rejuvenation policies are extentions of Bobbio et al. (1998, 2001) and represent the failure phenomenon due to the exhaustion of the software resources caused by the memory leak, the fragmentation, etc. Numerical examples are devoted to compare three control schemes quantitatively.
Juichi TAKAHASHI Yoshiaki KAKUDA
Software and its systems are more complicated than a decade ago, and the systems are used for mission critical business, flight control and so on which often require high assurance systems. In this circumstance, we often use black-box testing. The question now arises that black-box testing does not generate numerical value of testing result but empirical. Thus, in this research, we develop and enhance FSM (Finite State Machine) testing method which can produce code coverage rate as numerical value. Our developed FSM testing by code coverage focuses on not only software system behavior but also data. We found higher code coverage rate, which indicates quality of system, by this method than existing black box testing method.
We propose and describe a free-space optical interconnection device with a photorefractive semi-linear resonator. The hologram in the photorefractive crystal is, in general, volatile and the erasing of it coincides with the diffraction of the signal beam. Therefore we have to reform the hologram again after several transmissions of the data or use some fixing techniques such as thermal fixing and electrical fixing. In our interconnection device, the hologram is enhanced by the feedback beam that is a part of the input signal divided by the beam splitter within semi-linear resonator, therefore the sustentation time of the connection can be extended. We explain the sustentation mechanism and investigate the optimum reflectivity of the beam splitters, which determine the feedback rate of the input signal, within feedback circuit for the high output conversion efficiency. We also analyze the coupling strength threshold for sustentation of the connection. We give a basic experiment on 33 interconnection by using BaTiO3 crystal and Ar+ laser whose wavelength is 514 [nm]. We show that the connections are held for long time without the continuous illumination of the control beam.
Mi-Jeong KIM Kyung-Geun LEE Hyoung-Kyu SONG
Recently, there has been increasing interest in providing high quality and efficient broadband services over wireless and mobile links. Space-time code is designed to exploit multiple-input multiple-output antenna systems and by doing so an enormous increase in the capacity of wireless systems can be achieved. In this letter, a synchronization technique is proposed to improve the performance of multiple-input multiple-output system. The interpolation method is employed to estimate the coarse and fine frequency offset at the same time without additional complexity.
Yoshifumi KAWAKAMI Naohiro KUZE Jin-Ping AO Yasuo OHNO
DC and RF performances of AlGaN/GaN HEMTs are simulated using a two-dimensional device simulator with the material parameters of GaN and AlGaN. The cut-off frequency is estimated as 205 GHz at the gate length of 0.05 µm and the drain breakdown voltage at this gate length is over 10 V. The values are satisfactory for millimeter wavelength power applications. The use of thin AlGaN layers has key importance to alleviate gate parasitic capacitance effects at this gate length.
Hideo TAKEUCHI Yoshitsugu YAMAMOTO Ryo HATTORI Takahide ISHIKAWA Masaaki NAKAYAMA
We propose an analysis method for Franz-Keldysh (FK) oscillations appearing in photoreflectance (PR) spectra of heterojunction device structures, which enables precise and simultaneous evaluation of the built-in electric field strength and band-gap energy. Samples for PR measurements were n+-GaAs/n-Al0.3 Ga0.7 As/i-GaAs heterostructures with different Al0.3Ga0.7As-layer thickness. We have found that the phase of the FK oscillations originating from the i-GaAs buffer layer depends on the Al0.3 Ga0.7 As-layer thickness. We have derived a calculation model for FK oscillations that includes the interference of probe light. From the comparison of the calculated spectra with the measured spectra, we conclude that mixing of the real and imaginary parts of a modulated dielectric function, which is caused by the probe-light interference, gives rise to the phase shift of the FK oscillations. Our FK-oscillation analysis method reduces ambiguity in the estimation of band-gap energy that is considerable in a conventional analysis.
Ting-Chao HOU Chien-Min WU Ming-Chieh CHAN
There has been a growing interest in multihop wireless ad hoc networks in recent years. Previous studies have shown that, in a wireless multihop network using the slotted ALOHA as the medium access control mechanism, the maximum throughput can be achieved if the number of neighbors is six to eight. We show that, when using the IEEE 802.11 DCF protocol in a wireless ad hoc network, the maximum end-to-end goodput is achieved when all nodes are within transmission range of each other. The main reason is that the channel spatial reuse factor gained from the multihop network does not match the increase in additional transmission hops that a packet needs to travel in a multihop network. For a multihop network, its MAC frame delivery capacity is approximately fixed at a value dependent on its spatial reuse factor. If the offered load increases, less capacity will be spent on delivering packets that eventually reach their destinations and hence resulting in lower end-to-end goodput.
Hans VANDIERENDONCK Koen De BOSSCHERE
Embedded processors are used in numerous devices executing dedicated applications. This setting makes it worthwhile to optimize the processor to the application it executes, in order to increase its power-efficiency. This paper proposes to enhance direct mapped data caches with automatically tuned randomized set index functions to achieve that goal. We show how randomization functions can be automatically generated and compare them to traditional set-associative caches in terms of performance and energy consumption. A 16 kB randomized direct mapped cache consumes 22% less energy than a 2-way set-associative cache, while it is less than 3% slower. When the randomization function is made configurable (i.e., it can be adapted to the program), the additional reduction of conflicts outweighs the added complexity of the hardware, provided there is a sufficient amount of conflict misses.
Rachaporn KEINPRASIT Prabhas CHONGSTITVATANA
In this paper an algorithm based on Ant Colony Optimization techniques called Ants on a Tree (AOT) is introduced. This algorithm can integrate many algorithms together to solve a single problem. The strength of AOT is demonstrated by solving a High-Level Synthesis problem. A High-Level Synthesis problem consists of many design steps and many algorithms to solve each of them. AOT can easily integrate these algorithms to limit the search space and use them as heuristic weights to guide the search. During the search, AOT generates a dynamic decision tree. A boosting technique similar to branch and bound algorithms is applied to guide the search in the decision tree. The storage explosion problem is eliminated by the evaporation of pheromone trail generated by ants, the inherent property of our search algorithm.
Ranking fuzzy numbers is one of very important research topics in fuzzy set theory because it is a base of decision-making in applications. However, fuzzy numbers may not be easily ordered into one sequence according to their magnitudes because they represent uncertain values. When two fuzzy numbers overlap with each other, a fuzzy number may not be considered absolutely larger than the other. That is, even when a fuzzy number may be considered larger than the other, it may also be considered smaller than the other. It means that for a given set of fuzzy numbers, several ranking sequences possibly exist. However, most of the existing ranking methods produce only one ranking sequence. They ignore other possible sequences due to the overlap between fuzzy numbers. We propose a ranking method which generates possible ranking sequences of given fuzzy numbers. Our method takes a viewpoint from users, and uses it for evaluation of fuzzy numbers. Fuzzy numbers will be ranked based on the evaluations and a fuzzy set of sequences of fuzzy numbers will be produced as a ranking results. Numeric examples and comparisons with other methods are also presented.
Huiqin JIANG Takashi YAHAGI Jianming LU
Automatic image inspector inspects the quality of printed circuit boards using image-processing technology. In this study, we change an automatic inspection problem into a problem for detecting the signal singularities. Based on the wavelet theory that the wavelet transform can focus on localized signal structures with a zooming procedure, a novel singularity detection and measurement algorithm is proposed. Singularity positions are detected with the local wavelet transform modulus maximum (WTMM) line, and the Lipschitz exponent is estimated at each singularity from the decay of the wavelet transform amplitude along the WTMM line. According to the theoretical analysis and computer simulation results, the proposed algorithm is shown to be successful for solving the automatic inspection problem and calculating the Lipschitz exponents of signals. These Lipschitz exponents successfully characterize singular behavior of signals at singularities.
Masahiro YOSHIDA Takeshi KAMIO Hideki ASAI
This report describes face image recognition by 2-dimensional discrete Walsh transform and multi-layer neural networks. Neural network (NN) is one of the powerful tools for pattern recognition. In the previous researches of face image recognition by NN, the gray levels on each pixel of the face image have been used for input data to NN. However, because the face image has usually too many pixels, a variety of approaches have been required to reduce the number of the input data. In this research, 2-dimensional discrete Walsh transform is used for reduction of input data and the recognition is done by multi-layer neural networks. Finally, the validity of our method is varified.
Yuichi IGARASHI Hidenori KUWAKADO Hatsukazu TANAKA
Relative time-stamping schemes prove the chronological sequence of digital documents and their integrity. Since the chronological sequence is verified by tracing the link between two timestamps, it is desirable that the length of the verification path is short. Buldas, Laud, Lipmaa, and Villemson have proposed the relative time-stamping scheme based on the binary link. In this paper, we extend the binary link to the ternary link, and apply it to the relative time-stamping scheme. We show that the maximum length of the verification path of the proposed scheme is shorter than that of the previous scheme. Moreover, we show that the average length of the proposed scheme is shorter than that of the previous scheme. Thus, the proposed time-stamping schemes is more efficient than the previous scheme.
This paper presents two different algorithms for random number generation. One algorithm generates a random sequence with an arbitrary distribution from a sequence of pure random numbers, i.e. a sequence with uniform distribution. The other algorithm generates a sequence of pure random numbers from a sequence of a given i.i.d. source. Both algorithms can be regarded as an implementation of the interval algorithm by using the integer arithmetic with limited precision. We analyze the approximation error measured by the variational distance between probability distributions of the desired random sequence and the output sequence generated by the algorithms. Further, we give bounds on the expected length of input sequence per one output symbol, and compare it with that of the original interval algorithm.
Masayuki GOTO Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
Nishiara and Morita defined an i.i.d. word-valued source which is defined as a pair of an i.i.d. source with a countable alphabet and a function which transforms each symbol into a word over finite alphabet. They showed the asymptotic equipartition property (AEP) of the i.i.d. word-valued source and discussed the relation with source coding algorithm based on a string parsing approach. However, their model is restricted in the i.i.d. case and any universal code for a class of word-valued sources isn't discussed. In this paper, we generalize the i.i.d. word-valued source to the ergodic word-valued source which is defined by an ergodic source with a countable alphabet and a function from each symbol to a word. We show existence of entropy rate of the ergodic word-valued source and its formula. Moreover, we show the recurrence time theorem for the ergodic word-valued source with a finite alphabet. This result clarifies that Ziv-Lempel code (ZL77 code) is universal for the ergodic word-valued source.
A Time Hopping Pulse Spacing Modulation (TH-PSM) system, which combines the pulse position modulation system with code shift keying, is proposed. The following performances are analyzed; (1) data transmission rate, (2) error rate in a single-user case, (3) error rate in a multi-user case, and (4) spectral efficiency. Consequently, the data transmission rate of the proposed system is higher than that of the conventional Spread Spectrum Pulse Position Modulation (SS-PPM) system. The proposed system can improve the probability of block error by increasing the number of information bits per spreading code. Moreover, the spectral efficiency of the proposed system is higher than that of the conventional system. The proposed system is more attractive than the conventional SS-PPM system for optical communications, power-line communications, and UWB communications.