Hiroshi SAKAMOTO Shirou MARUYAMA Takuya KIDA Shinichi SHIMOZONO
A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length n and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n)log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log log n > 1. This ratio is thus regarded to almost O(log n), which is the currently best approximation ratio. While g depends on the string, it is known that g=Ω(log n) and for strings from k-letter alphabet [12].
We present a novel frequency partitioning technique of fractional frequency reuse (FFR) that reduces the effect of co-channel interference and increases the capacity of OFDM systems. The usable sub-channel sets are classified into the common sub-channel sets for all cells and the dedicated sub-channel sets for specific cell types in FFR. The proposed fractional frequency reuse with ordering scheme (FFRO) can decrease the amount of interference in the common sub-channel sets by specially designing the sub-channel sets and the order of sub-channel assignment for specific cell types. Simulation results show that the proposed FFRO yields enhanced performance for both uniform and non-uniform distributions of traffic load.
Eunchul YOON Sun-Yong KIM Suhan CHOI Hichan MOON
The downlink beamforming weights which can suppress interfering signals toward out-of-cell mobile stations for a TDD-based OFDMA system are introduced. First, the downlink beamforming weights are optimally designed based on iteration. Then, the downlink beamforming weights are designed in a sub-optimal way. It is shown that the sub-optimally designed downlink beamforming weights have the same structure as that of the uplink beamforming weights which are derived based on MMSE. The performance of these schemes is compared based on the average receive SINR. The performance of a heuristic scheme which exploits uplink beamforming weights for downlink beamforming weights is also investigated.
We propose a new filter method for feature selection for SELDI-TOF mass spectrum datasets. In the method, a new relevance index was defined to represent the goodness of a feature by considering the distribution of samples based on the counts. The relevance index can be used to obtain the feature sets for classification. Our method can be applied to mass spectrum datasets with extremely high dimensions and process the clinical datasets with practical sizes in acceptable calculation time since it is based on simple counting of samples. The new method was applied to the three public mass spectrum datasets and showed better or comparable results than conventional filter methods.
JiYing WU QiuQi RUAN Gaoyun AN
A novel bimodal method for face recognition under low-level lighting conditions is proposed. It fuses an enhanced gray level image and an illumination-invariant geometric image at the feature-level. To further improve the recognition performance under large variations in attributions such as poses and expressions, discriminant features are extracted from source images using the wavelet transform-based method. Features are adaptively fused to reconstruct the final face sample. Then FLD is used to generate a supervised discriminant space for the classification task. Experiments show that the bimodal method outperforms conventional methods under complex conditions.
Masashi NAITO Shun WATANABE Ryutaroh MATSUMOTO Tomohiko UYEMATSU
We consider the problem of secret key agreement in Gaussian Maurer's Model. In Gaussian Maurer's model, legitimate receivers, Alice and Bob, and a wire-tapper, Eve, receive signals randomly generated by a satellite through three independent memoryless Gaussian channels respectively. Then Alice and Bob generate a common secret key from their received signals. In this model, we propose a protocol for generating a common secret key by using the result of soft-decision of Alice and Bob's received signals. Then, we calculate a lower bound on the secret key rate in our proposed protocol. As a result of comparison with the protocol that only uses hard-decision, we found that the higher rate is obtained by using our protocol.
In this letter, we propose a new scheme for the tag structure of the EPCglobal Class-1 Generation-2 (EPC C1 Gen2) standard equipped with a channel encoding block and the corresponding decoding block in the receiver of the reader system. The channel coded tag is designed to fully accommodate the EPC C1 Gen2 standard. The use of the proposed channel encoding block increases the number of logic gates in the tag by no more than 5%. The proposed reader system is designed to be used in the mixed tag modes as well, where the channel coded tags and existing tags co-exist in the same inventory round. The performances of the proposed tags and the corresponding reader systems are also presented by comparing the number of EPC error frames and the tag identification time with those of the conventional tags and reader systems.
This paper proposes a method providing efficient test compression. The proposed method is for robust testable path delay fault testing with scan design facilitating two-pattern testing. In the proposed method, test data are interleaved before test compression using statistical coding. This paper also presents test architecture for two-pattern testing using the proposed method. The proposed method is experimentally evaluated from several viewpoints such as compression rates, test application time and area overhead. For robust testable path delay fault testing on 11 out of 20 ISCAS89 benchmark circuits, the proposed method provides better compression rates than the existing methods such as Huffman coding, run-length coding, Golomb coding, frequency-directed run-length (FDR) coding and variable-length input Huffman coding (VIHC).
DinhTrieu DUONG Min-Cheol HWANG Byeong-Doo CHOI Jun-Hyung KIM Sung-Jea KO
In low bit-rate video transmission, the payload of a single packet can often contain a whole coded frame due to the high compression ratio in both spatial and temporal domains. Thus, the loss of a single packet can lead to the loss of a whole video frame. In this paper, we propose a novel error concealment algorithm that can effectively reconstruct the lost frame and protect the quality of video streams from the degradation caused by propagation errors. The proposed algorithm employs a bilateral motion estimation scheme where the weighted sum of the received motion vectors (MVs) in the neighboring frames is utilized to construct the MV field for the concealed frame. Unlike the conventional algorithms, the proposed scheme does not produce any overlapped pixel and hole region in the reconstructed frame. The proposed algorithm can be applied not only to the case of single frame loss but also adaptively extended to the case of multiframe loss. Experimental results show that the proposed algorithm outperforms other conventional techniques in terms of both peak signal-to-noise ratio (PSNR) performance and subjective visual quality.
Yasuyuki MATSUYA Takahiro MESUDA
We propose a stereo transmission technique using infrared rays and pulse density modulation (PDM) for digital wireless audio headphone systems. The main feature of the proposed technique is the use of two channels for transmission: the PDM data channel and the synchronized clock channel. This technique improves receiver characteristics to a noise floor of -80 dB and a second distortion of 62 dB and achieves a very low power consumption of 3.5 mW.
Naohiro KAWABATA Hisao KOGA Osamu MUTA Yoshihiko AKAIWA
As a method to realize a high-speed communication in the home network, the power-line communication (PLC) technique is known. A problem of PLC is that leakage radiation interferes with existing systems. When OFDM is used in a PLC system, the leakage radiation is not sufficiently reduced, even if the subcarriers corresponding to the frequency-band of the existing system are never used, because the signal is not strictly band-limited. To solve this problem, each subcarrier must be band-limited. In this paper, we apply the OQAM based multi-carrier transmission (OQAM-MCT) to a high-speed PLC system, where each subcarrier is individually band-limited. We also propose a pilot-symbol sequence suitable for frequency offset estimation, symbol-timing detection and channel estimation in the OQAM-MCT system. In this method, the pilot signal-sequence consists of a repeated series of the same data symbol. With this method, the pilot sequence approximately becomes equivalent to OFDM sequence and therefore existing pilot-assisted methods for OFDM are also applicable to OQAM-MCT system. Computer simulation results show that the OQAM-MCT system achieves both good transmission rate performance and low out-of-band radiation in PLC channels. It is also shown that the proposed pilot-sequence improves frequency offset estimation, symbol-timing detection and channel estimation performance as compared with the case of using pseudo-noise sequence.
Po-Hsun CHENG Sao-Jie CHEN Jin-Shin LAI
This work elucidates the evolution of three generations of the laboratory information system in the National Taiwan University Hospital, which were respectively implemented in an IBM Series/1 minicomputer, a client/server and a plug-and-play HL7 interface engine environment respectively. The experience of using the HL7 healthcare information exchange in the hospital information system, laboratory information system, and automatic medical instruments over the past two decades are illustrated and discussed. The latest design challenge in developing intelligent laboratory information services is to organize effectively distributed and heterogeneous medical instruments through the message gateways. Such experiences had spread to some governmental information systems for different purposes in Taiwan; besides, the healthcare information exchange standard, software reuse mechanism, and application service provider adopted in developing the plug-and-play laboratory information system are also illustrated.
A high-efficiency CMOS rectifier circuit for UHF RFID applications was developed. The rectifier utilizes a self-Vth-cancellation (SVC) scheme in which the threshold voltage of MOSFETs is cancelled by applying gate bias voltage generated from the output voltage of the rectifier itself. A very simple circuit configuration and zero power dissipation characteristics in biasing enable excellent power conversion efficiency (PCE), especially under small RF input power conditions. At higher RF input power conditions, the PCE of the rectifier automatically decreases. This is the built-in self-power-regulation function. The proposed SVC CMOS rectifier was fabricated with a 0.35-µm CMOS process and the measured performance was compared with those of conventional nMOS, pMOS, and CMOS rectifiers and other types of Vth cancellation rectifiers as well. The SVC CMOS rectifier achieves 32% of PCE at the -10 dBm RF input power condition. This PCE is larger than rectifiers reported to date under this condition.
Takehito SUZUKI Jiro HIROKAWA Makoto ANDO
This paper presents the formulation for the evaluation of external coupling in the alternating-phase feed single-layer slotted waveguide array antenna with baffles by using the Spectrum of Two-Dimensional Solutions (S2DS) method. A one-dimensional slot array is extracted from the array by assuming the periodicity in transversal direction and introducing the perfect electric conductors in the external region. The uniform excitation over the finite array is synthesized iteratively to demonstrate the fast and accurate results by S2DS. A unit design model with the baffles is introduced to determine the initial parameters of the slot pair which accelerate the iteration. Experiment at 25.3 GHz demonstrates good uniformity of the aperture field distribution as well as the effects of the baffles. The directivity is 32.7 dB which corresponds to the aperture efficiency 90.5% and the reflection is below -15.0 dB over 1.3 GHz.
Fumihito SASAMORI Yuya ISHIKAWA Shiro HANDA Shinjiro OSHITA
Both adaptive modulation and diversity combining are attractive techniques to combat fading and these two can be applicable to each digital-modulated symbol in OFDM transmission. In this letter, aiming to combat severe fading more effectively than the adaptive modulation, we theoretically analyze the benefit of a frequency diversity scheme within one OFDM symbol, which is a simple kind of coded OFDM (COFDM) based on IEEE 802.16 protocols. A simple closed form equation of bit error rate (BER) is derived, and then the advantages of correlated diversity gain and interference suppression by the diversity scheme are verified by both theoretical analysis and Monte Carlo simulation.
Hidehiro KATO Yasuyuki NOGAMI Tomoki YOSHIDA Yoshitaka MORIKAWA
In this paper, a multiplication algorithm in extension field Fpm is proposed. Different from the previous works, the proposed algorithm can be applied for an arbitrary pair of characteristic p and extension degree m only except for the case when 4p divides m(p-1) and m is an even number. As written in the title, when p>m, 4p does not divide m(p-1). The proposed algorithm is derived by modifying cyclic vector multiplication algorithm (CVMA). We adopt a special class of Gauss period normal bases. At first in this paper, it is formulated as an algorithm and the calculation cost of the modified algorithm is evaluated. Then, compared to those of the previous works, some experimental results are shown. Finally, it is shown that the proposed algorithm is sufficient practical when extension degree m is small.
Koji CHIDA Hiroaki KIKUCHI Keiichi HIROTA Gembu MOROHASHI
We propose a protocol for converting the encryption function of a ciphertext into another encryption function while keeping the corresponding message secret. The proposed protocol allows conversions of the El Gamal and Paillier cryptosystems and has the potential to design an efficient multiparty protocol intended for circuits consisting of arithmetic and logical operations. We clarify the condition of circuits such that the multiparty protocol based on the proposed protocol provides better performance than previous approaches. In addition, we introduce some privacy-preserving statistical computations as an effective application of the proposed protocol.
Seiji HAYASHI Hiroyuki INUKAI Masahiro SUGUIMOTO
The present paper describes quality enhancement of speech corrupted by an additive background noise in a single-channel system. The proposed approach is based on the introduction of a perceptual criterion using a frequency-weighting filter in a subtractive-type enhancement process. Although this subtractive-type method is very attractive because of its simplicity, it produces an unnatural and unpleasant residual noise. Thus, it is difficult to select fixed optimized parameters for all speech and noise conditions. A new and effective algorithm is thus developed based on the masking properties of the human ear. This newly developed algorithm allows for an automatic adaptation in the time and frequency of the enhancement system and determines a suitable noise estimate according to the frequency of the noisy input speech. Experimental results demonstrate that the proposed approach can efficiently remove additive noise related to various kinds of noise corruption.
Yu SASAKI Lei WANG Kazuo OHTA Noboru KUNIHIRO
In this paper, we propose password recovery attacks against challenge-response authentication protocols. Our attacks use a message difference for a MD5 collision attack proposed in IEICE 2008. First, we show how to efficiently find a message pair that collides with the above message difference. Second, we show that a password used in authenticated post office protocol (APOP) can be recovered practically. We also show that the password recovery attack can be applied to a session initiation protocol (SIP) and digest authentication. Our attack can recover up to the first 31 password characters in a short time and up to the first 60 characters faster than the naive search method. We have implemented our attack and confirmed that 31 characters can be successfully recovered.
Kaoru KUROSAWA Kazuhiro SUZUKI
It is known that perfectly secure (1-round, n-channel) message transmission (MT) schemes exist if and only if n ≥ 3t+1, where t is the number of channels that the adversary can corrupt. Then does there exist an almost secure MT scheme for n=2t+1 ? In this paper, we first sum up a number flaws of the previous almost secure MT scheme presented at Crypto 2004. We next show an equivalence between almost secure MT schemes and secret sharing schemes with cheaters. By using our equivalence, we derive a lower bound on the communication complexity of almost secure MT schemes. Finally, we present a near optimum scheme which meets our bound approximately. This is the first construction of provably secure almost secure (1-round, n-channel) MT schemes for n=2t+1.