It is said that the lower bound of the number of iterations of Miller's algorithm for pairing calculation is log 2r/(k), where () is the Euler's function, r is the group order, and k is the embedding degree. Ate pairing reduced the number of the loops of Miller's algorithm of Tate pairing from ⌊log 2r⌋ to ⌊ log 2(t-1)⌋, where t is the Frobenius trace. Recently, it is known to systematically prepare a pairing-friendly elliptic curve whose parameters are given by a polynomial of integer variable "χ." For such a curve, this paper gives integer variable χ-based Ate (Xate) pairing that achieves the lower bound. In the case of the well-known Barreto-Naehrig pairing-friendly curve, it reduces the number of loops to ⌊log 2χ⌋. Then, this paper optimizes Xate pairing for Barreto-Naehrig curve and shows its efficiency based on some simulation results.

In this letter we give a lower bound on the worst-case time complexity of Dijkstra's three-state mutual exclusion algorithm by specifying a concrete behavior of the algorithm. We also show that our result is more accurate than the known best bound.

Weighted graph matching is computationally challenging due to the combinatorial nature of the set of permutations. In this paper, a new relaxation approach to weighted graph matching is proposed, by which a new matching algorithm, named alternate iteration algorithm, is designed. It is proved that the algorithm proposed is locally convergent. Experiments are presented to show the effectiveness of the proposed algorithm.

In this paper, we present a low complexity, yet accurate adaptive algorithm for the tracking of two-dimensional (2-D) direction of arrival (DOAs) based on a uniform rectangular array (URA). The new algorithm is a novel hybrid of tracking and beamforming processes by making use of three stages of one-dimensional (1-D) DOA tracking algorithms -- in a hierarchical tree structure -- to determine the two DOA components iteratively in a coarse-fine manner. In between every other 1-D DOA tracking algorithm, a complementary orthogonal beamforming process is invoked to partition the incoming signals into appropriate groups to enhance the tracking accuracy. Since the new algorithm only involves the 1-D subspace-based DOA tracking algorithm, the overall complexity is substantially less than the direct two-dimensional (2-D) extension of the existing 1-D DOA tracking algorithms, which requires an update of higher-dimensional vectors followed by a higher-dimensional eigendecomposition or a 2-D search. Furthermore, with the tree-structured DOA tracking scheme, the tracked 2-D DOA components are automatically paired without extra computational overhead. Furnished simulations show that the new algorithm can provide satisfactory tracking performance in various scenarios.

A direct short proof of Horiguchi's formula for error values in alternant codes is provided. Horiguchi's formula employs only output polynomials of Berlekamp-Massey algorithm, which has less computational complexity than extended Euclidean algorithm for decoding alternant codes. As an application of our proof, we provide an explicit formula for the generator and parity check matrices of alternant codes and their singly- and doubly-extended codes.

In this paper, an ER (Error-Reduction) algorithm-based method for removal of adherent water drops from images obtained by a rear view camera mounted on a vehicle in rainy conditions is proposed. Since Fourier-domain and object-domain constraints are needed for any ER algorithm-based method, the proposed method introduces the following two novel constraints for the removal of adherent water drops. The first one is the Fourier-domain constraint that utilizes the Fourier transform magnitude of the previous frame in the obtained images as that of the target frame. Noting that images obtained by the rear view camera have the unique characteristics of objects moving like ripples because the rear view camera is generally composed of a fish-eye lens for a wide view angle, the proposed method assumes that the Fourier transform magnitudes of the target frame and the previous frame are the same in the polar coordinate system. The second constraint is the object-domain constraint that utilizes intensities in an area of the target frame to which water drops have adhered. Specifically, the proposed method models a deterioration process of intensities that are corrupted by the water drop adhering to the rear view camera lens. By utilizing these novel constraints, the proposed ER algorithm can remove adherent water drops from images obtained by the rear view camera. Experimental results that verify the performance of the proposed method are represented.

The line-based method has been one of the most commonly-used methods of hardware implementation of two-dimensional (2D) discrete wavelet transform (DWT). However, data buffer is required between the row DWT processor and the column DWT processor to solve the data flow mismatch, which increases the on-chip memory size and the output latency. Since the incompatible data flow is induced from the intrinsic property of adopted lifting-based algorithm, a decomposed lifting algorithm (DLA) is presented by rearranging the data path of lifting steps to ensure that image data is processed in raster scan manner in row processor and column processor. Theoretical analysis indicates that the precision issue of DLA outperforms other lifting-based algorithms in terms of round-off noise and internal word-length. A memory-efficient and high-performance line-based architecture is proposed based on DLA without the implementation of data buffer. For an N M image, only 2N internal memory is required for 5/3 filter and 4N of that is required for 9/7 filter to perform 2D DWT, where N and M indicate the width and height of an image. Compared with related 2D DWT architectures, the size of on-chip memory is reduced significantly under the same arithmetic cost, memory bandwidth and timing constraint. This design was implemented in SMIC 0.18 µm CMOS logic fabrication with 32 kbits dual-port RAM and 20 K equivalent 2-input NAND gates in a 1.00 mm 1.00 mm die, which can process 512 512 image under 100 MHz.

In this paper, we propose a new approximate algorithm for the model predictive control (MPC) problem with a time-varying reference of hybrid systems. The proposed algorithm consists of an offline computation and an online computation. In the offline computation, candidates of mode sequences are derived. In the online computation, after the mode sequence is uniquely decided among candidates, the finite-time optimal control problem, i.e., the quadratic programming problem, is solved. So by applying the proposed algorithm, the computational amount of the online computation is decreased. First, the MPC problem with a time-varying reference is formulated. Next, the proposed algorithm is explained, and the accuracy of the obtained approximate solution is discussed. Finally, the effectiveness of the proposed method is shown by a numerical example.

In this letter the complexity of factoring an α-LSBS modulus is analyzed. This gives an improvement on the lower bound of the previous results.

In this paper, we consider a problem of assigning n independent tasks onto m identical processors in such a way that the overall execution time of the tasks will be minimized. Unlike conventional task assignment problem, we assume that the execution time of each task is not fixed in advance, and merely upper and lower bounds of the execution time are given at the compile time. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal off-line scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case performance ratio of 1 + 1/f(n) where f(n) = O(n2/3) for any fixed m, which approaches to one by increasing n to the infinity. We then propose a new scheme that achieves better worst case ratio of 1 + 1/g(n) where g(n) = Θ (n/log n) for any fixed m, which approaches to one more quickly than previous schemes.

This paper proposes a new sieving algorithm that employs a bucket sort as a part of a factoring algorithm such as the number field sieve. The sieving step requires an enormous number of memory updates; however, these updates usually cause cache hit misses. The proposed algorithm significantly reduces the number of cache hit misses when the size of the sieving region is roughly less than the square of the cache size, and the memory updates are several times faster than the straightforward implementation according to the PC experiments.

Let G(s)=C(sI - A)-1B+D be a given system where entries of A,B,C,D are polynomials in a parameter k. Then H∞ norm || G(s) ||∞ of G(s) is a function of k, and [9] presents an algorithm to express 1/(||G(s) ||∞)2 as a root of a bivariate polynomial, assuming feedthrough term D to be zero. This paper extends the algorithm in two ways: The first extension is the form of the function to be expressed. The extended algorithm can treat, not only H∞ norm, but also functions that appear in the celebrated KYP Lemma. The other extension is the range of the frequency. While H∞ norm considers the supremum of the maximum singular value of G(i ω) for the infinite range 0 ≤ω ≤ ∞ of ω, the extended algorithm treats the norm for the finite frequency range ω ≤ ω ≤ ω- (ω, ω- ∈ R ∪ ∞). Those two extensions allow the algorithm to be applied to wider area of control problems. We give illustrative numerical examples where we apply the extended algorithm to the computation of the frequency-restricted norm, i.e., the supremum of the maximum singular value of G(i ω) (ω- ≤ ω ≤ ω-).

Recently, it has become important to rapidly detect human subjects buried under collapsed houses, rubble and soil due to earthquakes and avalanches to reduce the casualties in a disaster. Such detection systems have already been developed as one kind of microwave displacement sensors that are based on phase difference generated by the motion of the subject's breast. Because almost all the systems consist of single transmitter and receiver pair, it is difficult to rapidly scan a wide area. In this paper, we propose a single-frequency multistatic radar system to detect breathing human subjects which exist in the area surrounded by the transmitting and receiving array. The vibrating targets can be localized by the MUSIC algorithm with the complex amplitude in the Doppler frequency. This algorithm is validated by the simulated signals synthesized with a rigorous solution of a dielectric spherical target model. We show experimental 3D localization results using a developed multistatic Doppler radar system around 250 MHz.

A task that suspends itself to wait for an I/O completion or to wait for an event from another node in distributed environments is called an I/O blocking task. Conventional hard real-time scheduling theories use framework of rate monotonic analysis (RMA) to schedule such I/O blocking tasks. However, most of them are pessimistic. In this paper, we propose effective algorithms that can schedule a task set which has I/O blocking tasks under dynamic priority assignment. We present a new critical instant theorem for the multi-frame task set under dynamic priority assignment. The schedulability is analyzed under the new critical instant theorem. For the schedulability analysis, this paper presents saturation summation which is used to calculate the maximum interference function (MIF). With saturation summation, the schedulability of a task set having I/O blocking tasks can be analyzed more accurately. We propose an algorithm which is called Frame Laxity Monotonic Scheduling (FLMS). A genetic algorithm (GA) is also applied. From our experiments, we can conclude that FLMS can significantly reduce the calculation time, and GA can improve task schedulability ratio more than is possible with FLMS.

A method using genetic algorithms for path generation have been proposed; however, this method is limited to particular applications, and there are limitations on the types of paths that can be represented. This paper therefore proposes a path generation method that is applicable to more general-purpose applications compared to previous methods based on a new design of the genotype used in the genetic algorithm.

A linear consecutive-k-out-of-n: F system is an ordered sequence of n components. This system fails if, and only if, k or more consecutive components fail. Optimal arrangement is one of the main problems for such kind of system. In this problem, we want to obtain an optimal arrangement of components to maximize system reliability, when all components of the system need not have equal component failure probability and all components are mutually statistically independent. As n becomes large, however, the amount of calculation would be too much to solve within a reasonable computing time even by using a high-performance computer. Hanafusa and Yamamoto proposed applying Genetic Algorithm (GA) to obtain quasi optimal arrangement in a linear consecutive-k-out-of-n: F system. GA is known as a powerful tool for solving many optimization problems. They also proposed ordinal representation, which produces only arrangements satisfying the necessary conditions for optimal arrangements and eliminates redundant arrangements with same system reliabilities produced by reversal of certain arrangements. In this paper, we propose an efficient GA. We have modified the previous work mentioned above to allocate components with low failure probabilities, that is to say reliable components, at equal intervals, because such arrangements seem to have relatively high system reliabilities. Through the numerical experiments, we observed that our proposed GA with interval k provides better solutions than the previous work for the most cases.

This paper presents a high-throughput bit-serial low-density parity-check (LDPC) decoder that uses an asynchronous interleaver. Since consecutive log-likelihood message values on the interleaver are similar, node computations are continuously performed by using the most recently arrived messages without significantly affecting bit-error rate (BER) performance. In the asynchronous interleaver, each message's arrival rate is based on the delay due to the wire length, so that the decoding throughput is not restricted by the worst-case latency, which results in a higher average rate of computation. Moreover, the use of a multiple-valued data representation makes it possible to multiplex control signals and data from mutual nodes, thus minimizing the number of handshaking steps in the asynchronous interleaver and eliminating the clock signal entirely. As a result, the decoding throughput becomes 1.3 times faster than that of a bit-serial synchronous decoder under a 90 nm CMOS technology, at a comparable BER.

In this paper, we analyze the extended real-time Polling Service (ertPS) algorithm in IEEE 802.16e systems, which is designed to support Voice-over-Internet-Protocol (VoIP) services with data packets of various sizes and silence suppression. The analysis uses a two-dimensional Markov Chain, where the grant size and the voice packet state are considered, and an approximation formula for the total throughput in the ertPS algorithm is derived. Next, to improve the performance of the ertPS algorithm, we propose an enhanced uplink resource allocation algorithm, called the e 2rtPS algorithm, for VoIP services in IEEE 802.16e systems. The e 2rtPS algorithm considers the queue status information and tries to alleviate the queue congestion as soon as possible by using remaining network resources. Numerical results are provided to show the accuracy of the approximation analysis for the ertPS algorithm and to verify the effectiveness of the e 2rtPS algorithm.

The All-Pairs Shortest Paths (APSP) problem is a graph problem which can be solved by a three-nested loop program. The Cell Broadband Engine (Cell/B.E.) is a heterogeneous multi-core processor that offers the high single precision floating-point performance. In this paper, a solution of the APSP problem on the Cell/B.E. is presented. To maximize the performance of the Cell/B.E., a blocked algorithm for the APSP problem is used. The blocked algorithm enables reuse of data in registers and utilizes the memory hierarchy. We also describe several optimization techniques for effective implementation of the APSP problem on the Cell/B.E. The Cell/B.E. achieves the performance of 8.45 Gflop/s for the APSP problem by using one SPE and 50.6 Gflop/s by using six SPEs.

This paper analyzes frequency tracking characteristics of a complex-coefficient adaptive infinite impulse response (IIR) notch filter with a simplified gradient-based algorithm. The input signal to the complex notch filter is a complex linear chirp embedded in a complex zero-mean white Gaussian noise. The analysis starts with derivation of a first-order real-coefficient difference equation with respect to steady-state instantaneous frequency tracking error. Closed-form expression for frequency tracking mean square error (MSE) is then derived from the difference equation. Lastly, closed-form expressions for optimum notch bandwidth coefficient and step size constant that minimize the frequency tracking MSE are derived. Computer simulations are presented to validate the analysis.