Jason O. HALLSTROM William M. LEAL Anish ARORA
The demand for highly available software systems has increased dramatically over the past several years. Such systems must be developed using a discipline that supports unanticipated runtime evolution. We characterize the desiderata of a programming model that provides such support, and describe the design and implementation of an architecture satisfying these criteria. The Dynamic Reconfiguration Subsystem (DRSS) is an interceptor-based open container architecture that supports the development of highly available systems by enabling the scalable, dynamic deployment of cross-cutting software modifications. We have implemented a prototype of DRSS using Microsoft's .NET Framework.
Kouji ISHII Giuseppe ABREU Ryuji KOHNO
Beam-space time coding methods are being extensively investigated, since they provide levels of performance appropriate for the next and future generations of wireless communication systems. In this paper, we focus on beam-domain space-time coding, especially considering the case when transmit beams have inter-beam interference (IBI). A new beam-space time coding scheme that takes into account the overlap amount among beams is proposed. We observe that the overlap of beams introduces an amount of correlation to the channels in a similar way to the well-known Partial Response (PR) channel in magnetic recording. Based on that observation, the proposed system can make use of IBI to encode and decode the signals. We evaluate the proposed system both via theoretical upper bound and via computer simulations. The Bit Error Rate (BER) performance of the proposed system using IBI is better than that of the system with no-IBI because the proposed system delivers more coding gain. However, the overlap of beams decreases the diversity gain. The tradeoff relationship between diversity gain and coding gain is investigated.
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.
Hidenori KOBAYASHI Nobuyuki YAMASAKI
The imprecise computation model is one of the flexible computation models used to construct real-time systems. It is especially useful when the worst case execution times are difficult to estimate or the execution times vary widely. Although there are several ways to implement this model, they have not attained much attentions of real-world application programmers to date due to their unrealistic assumptions and high dependency on the execution environment. In this paper, we present an integrated approach for implementing the imprecise computation model. In particular, our research covers three aspects. First, we present a new imprecise computation model which consists of a mandatory part, an optional part, and another mandatory part called wind-up part. This wind-up part allows application programmers to explicitly incorporate into their programs the exact operations needed for safe degradation of performance when there is a shortage in resources. Second, we describe a scheduling algorithm called Mandatory-First with Wind-up Part (M-FWP) which is based on the Earliest Deadline First strategy. This algorithm, unlike scheduling algorithms developed for the classical imprecise computation model, is capable of scheduling a mandatory portion after an optional portion. Third, we present a dynamic priority server method for an efficient implementation of the M-FWP algorithm. We also show that the number of the proposed server at most needed per node is one. In order to estimate the performance of the proposed approach, we have implemented a real-time operating system called RT-Frontier. The experimental analyses have proven its ability to implement tasks based on the imprecise computation model without requiring any knowledge on the execution time of the optional part. Moreover, it also showed performance gain over the traditional checkpointing technique.
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.
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.
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.
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.
In this paper, a high-performance pipelining architecture for 2-D inverse discrete wavelet transform (IDWT) is proposed. We use a tree-block pipeline-scheduling scheme to increase computation performance and reduce temporary buffers. The scheme divides the input subbands into several wavelet blocks and processes these blocks one by one, so the size of buffers for storing temporal subbands is greatly reduced. After scheduling the data flow, we fold the computations of all wavelet blocks into the same low-pass and high-pass filters to achieve higher hardware utilization and minimize hardware cost, and pipeline these two filters efficiently to reach higher throughput rate. For the computations of N N-sample 2-D IDWT with filter length of size K, our architecture takes at most (2/3)N2 cycles and requires 2N(K-2) registers. In addition, each filter is designed regularly and modularly, so it is easily scalable for different filter lengths and different levels. Because of its small storage, regularity, and high performance, the architecture can be applied to time-critical image decompression.
Tadashi DOHI Kazuki IWAMOTO Hiroyuki OKAMURA Naoto KAIO
Software rejuvenation is a proactive fault management technique that has been extensively studied in the recent literature. In this paper, we focus on an example for a telecommunication billing application considered in Huang et al. (1995) and develop the discrete-time stochastic models to estimate the optimal software rejuvenation schedule. More precisely, two software availability models with rejuvenation are formulated via the discrete semi-Markov processes, and the optimal software rejuvenation schedules which maximize the steady-state availabilities are derived analytically. Further, we develop statistically non-parametric algorithms to estimate the optimal software rejuvenation schedules, provided that the complete sample data of failure times are given. Then, a new statistical device, called the discrete total time on test statistics, is introduced. Finally, we examine asymptotic properties for the statistical estimation algorithms proposed in this paper through a simulation experiment.
Hisashi FUTAKI Tomoaki OHTSUKI
Space-time transmit diversity (STTD) and space-time block coding (STBC) are attractive techniques for high bit-rate and high capacity transmission. The concatenation scheme of turbo codes and STBC (Turbo-STBC) was proposed and it has been shown that the Turbo-STBC can achieve the good error rate performance. Recently, low-density parity-check (LDPC) codes have attracted much attention as the good error correcting codes achieving the near Shannon limit performance like turbo codes. The decoding algorithm of LDPC codes has less complexity than that of turbo codes. Furthermore, when the block length is large, the error rate performance of the LDPC codes is better than that of the turbo codes with almost identical code rate and block length. In this letter, we propose a concatenation scheme of LDPC codes and STBC. We refer to it as the LDPC-STBC. We evaluate the error rate performance of the LDPC-STBC by the computer simulation and show that the error rate performance of the LDPC-STBC is almost identical to or better than that of the Turbo-STBC in a flat Rayleigh fading channel.
Hongku KANG Yeyun KHO Kanghee KIM Kiseon KIM
In this letter, we propose a robust IFDD scheme employing an interference canceller, which is used for mitigating interferences from the transmitting signal instead of complex filter bank to reduce the complexity, for the OFDM system using feedback information. According to simulation results, the proposed IFDD OFDM system does not show significant performance degradation but maintains the robustness against the fast time-varying multipath channel, while the TDD OFDM system estimating feedback information from receiving block makes serious performance degradation.
Kazuo MORI Tomotaka NAGAOSA Hideo KOBAYASHI
A shared-TDD scheme has been proposed for accommodation of asymmetric communications between uplink and downlink traffic. The application of shared-TDD scheme to CDMA cellular systems causes inter-link interference because CDMA cellular systems use the same frequency band for all cells. This paper proposes a transmission control scheme for uplink packets to relieve the effect of inter-link interference in CDMA/shared-TDD cellular packet systems. In the proposed scheme, mobile stations select transmission slots based on their location and the status of slot allocations in own and the adjacent cells. Computer simulations show that the proposed scheme relieves the effect of inter-link interference, and thus improves the downlink transmission efficiency.
In this letter, we present a normalized least-mean-square algorithm of blind estimator for carrier frequency offset estimation of orthogonal frequency division multiplexing systems. In conjunction with the closed-loop estimate structure, the proposed efficient algorithm eliminates the inter-carrier interference for time varying carrier frequency offset. The proposed algorithm offers faster convergence speed and more accuracy to the carrier frequency offset estimate. Several computer simulation examples are presented for illustrating and effectiveness of the proposed algorithm.
Md. Mostafizur Rahman KHAN Noboru TANIZUKA
The radio wave intensity time series of the quasar is observed with the radio wave interferometer on the earth. External noise may superimpose with the radio wave on the path of wave propagation over the cosmological distance. In this paper, the effects of the superimposed noise on the radio wave intensity time series are discussed assuming nonlinear dynamics to apply on the time series. A convolution method is applied to the original observed radio wave intensity time series. Both the original and the convolution time series are analyzed by the Grassberger-Procaccia (GP) method with correlation integration and compared the results to estimate the presence and the effects of superimposed subtle noise. In addition, surrogate and Judd methods are applied to the radio wave intensity time series to increase the credibility of the results of the GP method. The effects of added random noise in Lorenz model are also analyzed with the GP method to estimate the above results.
Hyunseok SHIN Euntai KIM Mignon PARK
In this paper, we present an output feedback controller using a fuzzy controller and observer for nonlinear systems with unknown time-delay. Recently, Cao et al. proposed a stabilization method for the nonlinear time-delay systems using a fuzzy controller when the time-delay is known. In general, however, it is impossible to know or measure this time-varying delay. The proposed method requires only the upper bound of the derivative of the time-delay. We represent the nonlinear system with the unknown time-delay by Takagi-Sugeno (T-S) fuzzy model and design the fuzzy controller and observer for the systems using the parallel distributed compensation (PDC) scheme. In addition, we derive the sufficient condition for the asymptotic stability of the equilibrium point by applying Lyapunov-Krasovskii theorem to the closed-loop system and solve the condition in the formulation of LMI. Finally, computer simulations are included to demonstrate the effectiveness of the suggested method.
Jiman HONG Sangsu KIM Yookun CHO
Forked checkpointing scheme is proposed to achieve low checkpoint overhead. When a process wants to take a checkpoint in the forked checkpointing scheme, it creates a child process and continues its normal computation. Two recovery models can be used for forked checkpointing when the parent process fails before the child process establishes the checkpoint. One is the pessimistic recovery model where the recovery process rolls back to the previous checkpoint state. The other is the optimistic recovery model where a recovery process waits for the checkpoint to be established by the child process. In this paper, we present the recovery models for forked checkpointing by deriving the expected execution time of a process with and without checkpointing and also show that the expected recovery time of the optimistic recovery model is smaller than that of the pessimistic recovery model.
In this paper, a novel algorithm is presented for blind estimation of the symbol timing and frequency offset for OFDM systems. Time-varying frequency-selective Rayleigh fading multipath channel is considered, which is characterized by the power delay profile and time-varying scattering function and has high reliability for real-world mobile environment. The estimators exploit the intrinsic structures of OFDM signals and rely on the second-order moment rather than the probability distribution function of the received signals. They are totally optimum in sense of minimum mean-square-error and can be implemented easily. In addition, we have presented an improved approach which not only preserves the merits of previously proposed method, but also makes the estimation range of the frequency offset cover the entire subcarrier spacing of OFDM signals and the timing estimator be independent of the frequency offset.
Ohmin KWON Sangchul WON Dong YUE
In this paper, we propose a delayed feedback guaranteed cost controller design method for uncertain linear systems with delays in states. Based on the Lyapunov method, an LMI optimization problem is formulated to design a delayed feedback controller which minimizes the upper bound of a given quadratic cost function. Numerical examples show the effectiveness of the proposed method.
Hanseok KO Ilkwang LEE Jihyo LEE David HAN
In this paper, we develop an image-based tracking algorithm of multiple vehicles performing effective detection and tracking of moving objects under adverse environmental conditions. In particular, we employ low cost commercial off-the-shelf IR or CCD image sensor for generating continuous images of multiple moving vehicles. The motion in image sequences is first detected by adaptive background estimation and then tracked by Kalman filtering with the attribute information being updated by data association. Upon applying a modified Retinex procedure as preprocessing to reduce the illumination effects, we proceed with a two-step tracking algorithm. The first step achieves blob grouping and then judicially selects the true targets for tracking using data association through information registration. In the second stage, all blobs detected go through a validation for screening as well as for occlusion reasoning, and those found pertinent to the real object survive to become the 'Object' state for stable tracking. The results of representative tests confirm its effectiveness in vehicle tracking under both daylight and nighttime conditions while resolving occlusions.