Yasuyuki HATAKAWA Noriaki MIYAZAKI Toshinori SUZUKI
This paper proposes Twin Turbo (T2) MIMO-OFDM (Multiple Input Multiple Output-Orthogonal Frequency Division Multiplexing). The advanced iterative decoder, called the T2 decoder, decreases the transmission error rate compared to conventional turbo decoders because it uses the correlation information among the bits mapped on an identical symbol of multi-level modulation and updates the channel reliability. When T2 is applied to a MIMO-OFDM, the required symbol energy to noise power density ratio (Es/N0) can be reduced more effectively than when T2 is applied to SISO (Single Input Single Output). This is because T2 can use the correlation among the bits not only mapped on an identical symbol but also transmitted from different antennas. Moreover, T2 achieves good performance in a correlated MIMO channel because the average minimum squared Euclidean distances between symbol replica candidates consisting of signals transmitted from multiple transmitter antennas are reduced. Computer simulations verify that the required Es/N0 of T2 MIMO-OFDM using 16QAM is 1.9 dB lower than that of a conventional turbo decoder when the correlation coefficients of transmitter and receiver antennas are 0.8. A computational complexity analysis clarifies the relation between the increase in computational complexity and the reduction in the required Es/N0.
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.
Yasuyuki NOGAMI Yumi SAKEMI Takumi OKIMOTO Kenta NEKADO Masataka AKANE Yoshitaka MORIKAWA
For ID-based cryptography, not only pairing but also scalar multiplication must be efficiently computable. In this paper, we propose a scalar multiplication method on the circumstances that we work at Ate pairing with Barreto-Naehrig (BN) curve. Note that the parameters of BN curve are given by a certain integer, namely mother parameter. Adhering the authors' previous policy that we execute scalar multiplication on subfield-twisted curve
Ali OZEN Ismail KAYA Birol SOYSAL
Because of the fact that mobile communication channel changes by time, it is necessary to employ adaptive channel equalizers in order to combat the distorting effects of the channel. Least Mean Squares (LMS) algorithm is one of the most popular channel equalization algorithms and is preferred over other algorithms such as the Recursive Least Squares (RLS) and Maximum Likelihood Sequence Estimation (MLSE) when simplicity is the dominant decision factor. However, LMS algorithm suffers from poor performance and convergence speed within the training period specified by most of the standards. The aim of this study is to improve the convergence speed and performance of the LMS algorithm by adjusting the step size using fuzzy logic. The proposed method is compared with the Channel Matched Filter-Decision Feedback Equalizer (CMF-DFE) [1] which provides multi path propagation diversity by collecting the energy in the channel, Minimum Mean Square Error-Decision Feedback Equalizer (MMSE-DFE) [2] which is one of the most successful equalizers for the data packet transmission, normalized LMS-DFE (N-LMS-DFE) [3] , variable step size (VSS) LMS-DFE [4] , fuzzy LMS-DFE [5],[6] and RLS-DFE [7] . The obtained simulation results using HIPERLAN/1 standards have demonstrated that the proposed LMS-DFE algorithm based on fuzzy logic has considerably better performance than others.
Rie HAYASHI Eiji OKI Kohei SHIOMOTO
This paper evaluates three inter-domain redundancy path computation methods based on PCE (Path Computation Element). Some inter-domain paths carry traffic that must be assured of high quality and high reliability transfer such as telephony over IP and premium virtual private networks (VPNs). It is, therefore, important to set inter-domain redundancy paths, i.e. primary and secondary paths. The first scheme utilizes an existing protocol and the basic PCE implementation. It does not need any extension or modification. In the second scheme, PCEs make a virtual shortest path tree (VSPT) considering the candidates of primary paths that have corresponding secondary paths. The goal is to reduce blocking probability; corresponding secondary paths may be found more often after a primary path is decided; no protocol extension is necessary. In the third scheme, PCEs make a VSPT considering all candidates of primary and secondary paths. Blocking probability is further decreased since all possible candidates are located, and the sum of primary and secondary path cost is reduced by choosing the pair with minimum cost among all path pairs. Numerical evaluations show that the second and third schemes offer only a few percent reduction in blocking probability and path pair total cost, while the overheads imposed by protocol revision and increase of the amount of calculation and information to be exchanged are large. This suggests that the first scheme, the most basic and simple one, is the best choice.
Alexander TIKHONRAVOV Michael TRUBETSKOV Ichiro KASAHARA
A new paradigm in the design of optical coatings connected with an outstanding computational efficiency of modern design techniques is discussed. Several other topics including pre-production error analysis, monitoring of coating production, and computational manufacturing of optical coatings are considered.
Chuzo IWAMOTO Harumasa YONEDA Kenichi MORITA Katsunobu IMAI
We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n+1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.
Ji Hun PARK Jae Sam YOON Hong Kook KIM
In this paper, we propose a new mask estimation method for the computational auditory scene analysis (CASA) of speech using two microphones. The proposed method is based on a hidden Markov model (HMM) in order to incorporate an observation that the mask information should be correlated over contiguous analysis frames. In other words, HMM is used to estimate the mask information represented as the interaural time difference (ITD) and the interaural level difference (ILD) of two channel signals, and the estimated mask information is finally employed in the separation of desired speech from noisy speech. To show the effectiveness of the proposed mask estimation, we then compare the performance of the proposed method with that of a Gaussian kernel-based estimation method in terms of the performance of speech recognition. As a result, the proposed HMM-based mask estimation method provided an average word error rate reduction of 61.4% when compared with the Gaussian kernel-based mask estimation method.
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.
HyongSoon KIM PyungSoo KIM SangKeun LEE
In this letter, a new estimation filtering is proposed when a delay between signal generation and signal estimation exists. The estimation filter is developed under a maximum likelihood criterion using only the finite observations on the delay interval. The proposed estimation filter is represented in both matrix form and iterative form. It is shown that the filtered estimate has good inherent properties such as time-invariance, unbiasedness and deadbeat. Via numerical simulations, the performance of the proposed estimation filtering is evaluated by the comparison with that of the existing fixed-lag smoothing, which shows that the proposed approach could be appropriate for fast estimation of signals that vary relatively quickly. Moreover, the on-line computational complexity of the proposed estimation filter is shown to be maintained at a lower level than the existing one.
Takuya KITAMOTO Tetsu YAMAGUCHI
Let M(y) be a matrix whose entries are polynomial in y, λ(y) and v(y) be a set of eigenvalue and eigenvector of M(y). Then, λ(y) and v(y) are algebraic functions of y, and λ(y) and v(y) have their power series expansionsλ(y) = β0 + β1 y + + βk yk + (βj C),(1) v(y) = γ0 + γ1 y + + γk yk + (γj Cn), (2)provided that y=0 is not a singular point of λ(y) or v(y). Several algorithms are already proposed to compute the above power series expansions using Newton's method (the algorithm in [4]) or the Hensel construction (the algorithm in[5],[12]). The algorithms proposed so far compute high degree coefficients βk and γk, using lower degree coefficients βj and γj (j=0,1,,k-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index k increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients βk and γk, and we need to check the accuracy. In this paper, we assume that given matrix M(y) does not have multiple eigenvalues at y=0 (this implies that y=0 is not singular point of λ(y) or v(y)), and presents an algorithm to estimate the accuracy of the computed power series βi,γj in (1) and (2). The estimation process employs the idea in [9] which computes a coefficient of a power series with Cauchy's integral formula and numerical integrations. We present an efficient implementation of the algorithm that utilizes Newton's method. We also present a modification of Newton's method to speed up the procedure, introducing tuning parameter p. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 1216%, choosing the optimal tuning parameter p.
ShanXue CHEN FangWei LI WeiLe ZHU TianQi ZHANG
A simple and successful design of initial codebook of vector quantization (VQ) is presented. For existing initial codebook algorithms, such as random method, the initial codebook is strongly influenced by selection of initial codewords and difficult to match with the features of the training vectors. In the proposed method, training vectors are sorted according to the norm of training vectors. Then, the ordered vectors are partitioned into N groups where N is the size of codebook. The initial codewords are obtained from calculating the centroid of each group. This initializtion method has a robust performance and can be combined with the VQ algorithm to further improve the quality of codebook.
Zhiqiang BIAN Hirotake ISHII Hiroshi SHIMODA Masanori IZUMI
Augmented reality tasks require a high-reliability tracking method. Large tracking error causes many problems during AR applications. Tracking error estimation should be integrated with them to improve the reliability of tracking methods. Although some tracking error estimation methods have been developed, they are not feasible to be integrated because of computational speed and accuracy. For this study, a tracking error estimation algorithm with screen error estimation based on the characteristic of linecode marker was applied. It can rapidly estimate tracking error. An evaluation experiment was conducted to compare the estimated tracking error and the actual measured tracking error. Results show that the algorithm is reliable and sufficiently fast to be used for real-time tracking error warning or tracking accuracy improvement methods.
ShanXue CHEN FangWei LI WeiLe ZHU TianQi ZHANG
A fast algorithm to speed up the search process of vector quantization encoding is presented. Using the sum and the partial norms of a vector, some eliminating inequalities are constructeded. First the inequality based on the sum is used for determining the bounds of searching candidate codeword. Then, using an inequality based on subvector norm and another inequality combining the partial distance with subvector norm, more unnecessary codewords are eliminated without the full distance calculation. The proposed algorithm can reject a lot of codewords, while introducing no extra distortion compared to the conventional full search algorithm. Experimental results show that the proposed algorithm outperforms the existing state-of-the-art search algorithms in reducing the computational complexity and the number of distortion calculation.
Yuki YAI Shigeki MIYABE Hiroshi SARUWATARI Kiyohiro SHIKANO Yosuke TATEKURA
In this paper, we propose a computationally efficient method of compensating temperature for the transaural stereo. The conventional method can be used to estimate the change in impulse responses caused by the fluctuation of temperature with high accuracy. However, the large amount of computation required makes real-time implementation difficult. Focusing on the fact that the amount of compensation depends on the length of the impulse response, we reduce the computation required by segmenting the impulse response. We segment the impulse responses in the time domain and estimate the effect of temperature fluctuation for each of the segments. By joining the processed segments, we obtain the compensated impulse response of the whole length. Experimental results show that the proposed method can reduce the computation required by a factor of nine without degradation of the accuracy.
This paper considers numerical methods for stability analyses of periodic solutions of ordinary differential equations. Stability of a periodic solution can be determined by the corresponding monodromy matrix and its eigenvalues. Some commonly used numerical methods can produce inaccurate results of them in some cases, for example, near bifurcation points or when one of the eigenvalues is very large or very small. This work proposes a numerical method using a periodic boundary condition for vector fields, which preserves a critical property of the monodromy matrix. Numerical examples demonstrate effectiveness and a drawback of this method.
This paper presents a novel high-speed low-complexity pipelined degree-computationless modified Euclidean (pDCME) algorithm architecture for high-speed RS decoders. The pDCME algorithm allows elimination of the degree-computation so as to reduce hardware complexity and obtain high-speed processing. A high-speed RS decoder based on the pDCME algorithm has been designed and implemented with 0.13-µm CMOS standard cell technology in a supply voltage of 1.1 V. The proposed RS decoder operates at a clock frequency of 660 MHz and has a throughput of 5.3 Gb/s. The proposed architecture requires approximately 15% fewer gate counts and a simpler control logic than architectures based on the popular modified Euclidean algorithm.
Kuo-Tsung TSENG Chang-Biau YANG Kuo-Si HUANG Yung-Hsing PENG
The optimal alignment of two given biosequences is mathematically optimal, but it may not be a biologically optimal one. To investigate more possible alignments with biological meaning, one can relax the scoring functions to get near-optimal alignments. Though the near optimal alignments increase the possibility of finding the correct alignment, they may confuse the biologists because the size of candidates is large. In this paper, we present the filter scheme for the near-optimal alignments. An easy method for tracing the near-optimal alignments and an algorithm for filtering those alignments are proposed. The time complexity of our algorithm is O(dmn) in the worst case, where d is the maximum distance between the near-optimal alignments and the optimal alignment, and m and n are the lengths of the input sequences, respectively.
Masatsugu HIGASHINAKA Katsuyuki MOTOYOSHI Akihiro OKAZAKI Takayuki NAGAYASU Hiroshi KUBO Akihiro SHIBUYA
This paper proposes a likelihood estimation method for reduced-complexity maximum-likelihood (ML) detectors in a multiple-input multiple-output (MIMO) spatial-multiplexing (SM) system. Reduced-complexity ML detectors, e.g., Sphere Decoder (SD) and QR decomposition (QRD)-M algorithm, are very promising as MIMO detectors because they can estimate the ML or a quasi-ML symbol with very low computational complexity. However, they may lose likelihood information about signal vectors having the opposite bit to the hard decision and bit error rate performance of the reduced-complexity ML detectors are inferior to that of the ML detector when soft-decision decoding is employed. This paper proposes a simple estimation method of the lost likelihood information suitable for the reduced-complexity ML detectors. The proposed likelihood estimation method is applicable to any reduced-complexity ML detectors and produces accurate soft-decision bits. Computer simulation confirms that the proposed method provides excellent decoding performance, keeping the advantage of low computational cost of the reduced-complexity ML detectors.
Mototsugu NISHIOKA Naohisa KOMATSU
Canetti et al. [5] showed that there exist signature and encryption schemes that are secure in the random oracle (RO) model, but for which any implementation of the RO (by a single function or a function ensemble) results in insecure schemes. Their result greatly motivates the design of cryptographic schemes that are secure in the standard computational model. This paper gives some new results on the RO methodology. First, we give the necessary and sufficient condition for the existence of a signature scheme that is secure in the RO model but where, for any implementation of the RO, the resulting scheme is insecure. Next, we show that this condition induces a signature scheme that is insecure in the RO model, but that there is an implementation of the RO that makes the scheme secure.