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.

The encoding/decoding process of JPEG2000 requires much more computation power than that of conventional JPEG mainly due to the complexity of the entropy encoding/decoding. Thus usually multiple entropy codec hardware modules are implemented in parallel to process the entropy encoding/decoding. This module, however, requests many small-size memories to store intermediate data, and when multiple modules are implemented on a chip, employment of the large number of SRAMs increases difficulty of whole chip layout. In this paper, an efficient memory organization framework for the entropy encoding/decoding module is proposed, in which not only existing memory organizations but also our proposed novel memory organization methods are attempted to expand the design space to be explored. As a result, the efficient memory organization for a target process technology can be explored.

Distributed Video Coding (DVC) is an emerging video coding approach, particularly attractive due to its flexibility to implement low complex encoders. This feature could be very effectively utilized in a number of video sensor based application scenarios. However, DVC is still in the process of development and currently available codec implementations are based on a number of hypothetical models and assumptions. In DVC, the effects of noise and fading on the compressed payload (parity bit stream) in real video communications and the resultant modified channel model scenario have not been discussed in literature. In this paper, a solution to the above problem in turbo coding based DVC is discussed incorporating a novel dual channel model for the maximum a-posteriori (MAP) algorithm for turbo decoding. The simulations for AWGN and wireless channels at different group of picture (GOP) sizes show that the proposed algorithm improves the rate distortion performance compared to the existing decoding algorithm. It also outperforms the H.264/AVC I-P-I-P codec (v10.1/baseline profile); particularly at low Signal to Noise Ratio (SNR) levels of the channel, thus enabling DVC as a viable and efficient option for video communications.

In this paper, an idea for improvement of suffix array construction using lazy evaluation is presented. Evaluation of the suffix array is based on the searching queries; only the necessary part of the suffix array is built when unevaluated part of the suffix array is referred during the searching process. This is less time consuming than constructing complete suffix array. We propose lazy evaluation of Schürmann-Stoye algorithm. Experimental results show that lazy Schürmann-Stoye algorithm runs faster than Maniscalco, which is well-recognized as the fastest suffix sorting algorithm, under the constraint of small LCP (longest common prefix) and a limited number of searching queries.

This study analyzes the absolute stability in P and PD type fuzzy logic control systems with both certain and uncertain linear plants. Stability analysis includes the reference input, actuator gain and interval plant parameters. For certain linear plants, the stability (i.e. the stable equilibriums of error) in P and PD types is analyzed with the Popov or linearization methods under various reference inputs and actuator gains. The steady state errors of fuzzy control systems are also addressed in the parameter plane. The parametric robust Popov criterion for parametric absolute stability based on Lur'e systems is also applied to the stability analysis of P type fuzzy control systems with uncertain plants. The PD type fuzzy logic controller in our approach is a single-input fuzzy logic controller and is transformed into the P type for analysis. In our work, the absolute stability analysis of fuzzy control systems is given with respect to a non-zero reference input and an uncertain linear plant with the parametric robust Popov criterion unlike previous works. Moreover, a fuzzy current controlled RC circuit is designed with PSPICE models. Both numerical and PSPICE simulations are provided to verify the analytical results. Furthermore, the oscillation mechanism in fuzzy control systems is specified with various equilibrium points of view in the simulation example. Finally, the comparisons are also given to show the effectiveness of the analysis method.

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

This paper proposes novel algorithms for computing double-size modular multiplications with few modulus-dependent precomputations. Low-end devices such as smartcards are usually equipped with hardware Montgomery multipliers. However, due to progresses of mathematical attacks, security institutions such as NIST have steadily demanded longer bit-lengths for public-key cryptography, making the multipliers quickly obsolete. In an attempt to extend the lifespan of such multipliers, double-size techniques compute modular multiplications with twice the bit-length of the multipliers. Techniques are known for extending the bit-length of classical Euclidean multipliers, of Montgomery multipliers and the combination thereof, namely bipartite multipliers. However, unlike classical and bipartite multiplications, Montgomery multiplications involve modulus-dependent precomputations, which amount to a large part of an RSA encryption or signature verification. The proposed double-size technique simulates double-size multiplications based on single-size Montgomery multipliers, and yet precomputations are essentially free: in an 2048-bit RSA encryption or signature verification with public exponent e=216+1, the proposal with a 1024-bit Montgomery multiplier is at least 1.5 times faster than previous double-size Montgomery multiplications.

Multi-source broadcasting is one of the information dissemination problems on communication networks such that some units disseminate distinct messages to all other units. In this paper, we study multi-source broadcasting on the de Bruijn and Kautz digraphs which are the models of interconnection networks. In [8] and [12], a cycle-rooted tree which has a large root-cycle is constructed by composition of isomorphic factors, and the multi-source broadcasting is executed on the cycle-rooted tree. On the other side, we execute multi-source broadcasting on each isomorphic factors at the same time. We present a method for multi-source broadcasting using isomorphic cycle-rooted trees which factorize these digraphs, and investigate its efficiency.

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.

In the latest video coding frameworks, efficiency of motion vector (MV) coding is becoming increasingly important because of the growing bit rate portion of motion information. However, neither the conventional median predictor, nor the newer schemes such as the minimum bit rate prediction scheme and the hybrid scheme, can effectively eliminate the local redundancy of motion vectors. In this paper, we present the prioritized reference decision scheme for efficient motion vector coding, based on the H.264/AVC framework. This scheme makes use of a boolean indicator to specify whether the median predictor is to be used for the current MV or not. If not, the median prediction is considered not suitable for the current MV, and this information is used for refining the possible space of a group of reference MVs including 4 neighboring MVs and the zero MV. This group of MVs is organized to be a prioritized list so that the reference MV with highest priority is to be selected as the prediction value. Furthermore, the boolean indicators are coded into the modified code words of mb_type and sub_mb_type, so as to reduce the overhead. By applying the proposed scheme, the structure and the applicability problems with the state-of-the-art MBP scheme have been overcome. Experimental result shows that the proposed scheme achieves a considerable reduction of bits for MVDs, compared with the conventional median prediction algorithm. It also achieves a better and much stabler performance than MBP-based MV coding.

Adaptive polarization mode dispersion (PMD) compensation is required for the speed-up and advancement of the present optical communications. The combination of a tunable PMD compensator and its adaptive control method achieves adaptive PMD compensation. In this paper, we report an effective search control algorithm for the feedback control of the PMD compensator. The algorithm is based on the hill-climbing method. However, the step size changes randomly to prevent the convergence from being trapped at a local maximum or a flat, unlike the conventional hill-climbing method. The randomness depends on the Gaussian probability density functions. We conducted transmission simulations at 160 Gb/s and the results show that the proposed method provides more optimal compensator control than the conventional hill-climbing method.

In this letter, we propose a novel frequency-domain equalizer (FDE) for single-carrier systems characterized by severe inter-symbol interference (ISI) channels; it consists of a linear FDE and an iterative block noise-predictor (IBNP). Unlike the FDE with time-domain noise predictor (FDE-NP), the proposed scheme allows the feedback equalizer being an uncausal filter, and performs the noise prediction in an iterative manner. For this reason, FDE-IBNP can remove both precursor and postcursor ISI, and alleviate the impact of error-propagation. Besides, our scheme has lower computational complexity than the present iterative block equalizers.

Ultrawide-band impulse radio (UWB-IR) technology and multiple-input multiple-output (MIMO) systems have attracted interest regarding their use in next-generation high-speed radio communication. We have studied the use of MIMO ultrawide-band (MIMO-UWB) systems to enable higher-speed radio communication. We used frequency-domain equalization based on the minimum mean square error criterion (MMSE-FDE) to reduce intersymbol interference (ISI) and co-channel interference (CCI) in MIMO-UWB systems. Because UWB systems are expected to be used for short-range wireless communication, MIMO-UWB systems will usually operate in line-of-sight (LOS) environments and direct waves will be received at the receiver side. Direct waves have high power and cause high correlations between antennas in such environments. Thus, it is thought that direct waves will adversely affect the performance of spatial filtering and equalization techniques used to enhance signal detection. To examine the feasibility of MIMO-UWB systems, we conducted MIMO-UWB system propagation measurements in LOS environments. From the measurements, we found that the arrival time of direct waves from different transmitting antennas depends on the MIMO configuration. Because we can obtain high power from the direct waves, direct wave reception is critical for maximizing transmission performance. In this paper, we present our measurement results, and propose a way to improve performance using a method of transmit (Tx) and receive (Rx) timing control. We evaluate the bit error rate (BER) performance for this form of timing control using measured channel data.

This paper presents a fuzzy-based path selection method for improving the security level, in which each cluster chooses paths based on the detection power of false data and energy efficiency.

Localization is one of the fundamental problems in many wireless sensor networks applications, but most of them require the node to equip special range-determining or angle-determining hardware in order to obtain the position related information. In this paper, we propose a concentric beacons localization algorithm which is a range-free approach. Four anchors are set in the four corners of the square target region, and emit localizing beacons at different power levels, with the information of their position and the estimated range of the beacon. The nodes in this region receive these beacons and compute their positions correspondingly. In region of different scale, we propose two alternative schemes. The one for small scale has lower calculation complexity, and the other has better stability on large scale applications. Simulation results show the estimation error is less than 0.4 times the beacon interval.

We present recent progress of high-speed Mach-Zehnder modulator technologies for advanced modulation formats. Multi-level quadrature amplitude modulation signal can be synthesized by using parallel Mach-Zehnder modulators. We can generate complicated multi-level optical signals from binary data streams, where binary modulated signals are vectorially summed in optical circuits. Frequency response of each Mach-Zehnder interferometer is also very important to achieve high-speed signals. We can enhance the bandwidth of the response, with thin substrate. 87 Gbaud modulation was demonstrated with a dual-parallel Mach-Zehnder modulator.

This paper presents an efficient algorithm for large-scale multi-system learning task. The proposed architecture, referred to as the 'RBF×SOM', is based on the SOM2, that is, a'SOM of SOMs'. As is the case in the modular network SOM (mnSOM) with multilayer perceptron modules (MLP-mnSOM), the aim of the RBF×SOM is to organize a continuous map of nonlinear functions representing multi-class input-output relations of the given datasets. By adopting the algorithm for the SOM2, the RBF×SOM generates a map much faster than the original mnSOM, and without the local minima problem. In addition, the RBF×SOM can be applied to more difficult cases, that were not easily dealt with by the MLP-mnSOM. Thus, the RBF×SOM can deal with cases in which the probability density of the inputs is dependent on the classes. This tends to happen more often as the input dimension increases. The RBF×SOM therefore, overcomes many of the problems inherent in the MLP-mnSOM, and this is crucial for application to large scale tasks. Simulation results with artificial datasets and a meteorological dataset confirm the performance of the RBF×SOM.

In communication systems, ZCZ sequences and perfect sequences play important roles in removing multiple-access interference (MAI) and synchronization, respectively. Based on an uncorrelated polyphase base sequence set, a novel construction method, which can produce mutually orthogonal (MO) ZCZ polyphase sequence (PS) sets and perfect PSs, is presented. The obtained ZCZ PSs of each set are of ideal periodic cross-correlation functions (PCCFs), in other words, the PCCFs between such two different sequences vanishes, and the sequences between different sets are orthogonal. On the other hand, the proposed perfect PSs include Frank perfect PSs as a special case and the family size of the former is quite larger than that of the latter.

We show that simultaneous perturbation can be used as an algorithm for on-line learning, and we report our theoretical investigation on generalization performance obtained with a statistical mechanical method. Asymptotic behavior of generalization error using this algorithm is on the order of t to the minus one-third power, where t is the learning time or the number of learning examples. This order is the same as that using well-known perceptron learning.

Kernel methods such as the support vector machine are one of the most successful algorithms in modern machine learning. Their advantage is that linear algorithms are extended to non-linear scenarios in a straightforward way by the use of the kernel trick. However, naive use of kernel methods is computationally expensive since the computational complexity typically scales cubically with respect to the number of training samples. In this article, we review recent advances in the kernel methods, with emphasis on scalability for massive problems.