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.

Frequency-domain equalization (FDE) based on the minimum mean square error (MMSE) criterion can increase the downlink bit error rate (BER) performance of DS-CDMA beyond that possible with conventional rake combining in a frequency-selective fading channel. FDE requires accurate channel estimation. Recently, we proposed a pilot-assisted channel estimation (CE) based on the MMSE criterion. Using MMSE-CE, the channel estimation accuracy is almost insensitive to the pilot chip sequence, and a good BER performance is achieved. In this paper, we propose a channel estimation scheme using one-tap recursive least square (RLS) algorithm, where the forgetting factor is adapted to the changing channel condition by the least mean square (LMS) algorithm, for DS-CDMA with FDE. We evaluate the BER performance using RLS-CE with adaptive forgetting factor in a frequency-selective fast Rayleigh fading channel by computer simulation.

Current collapse phenomenon is a well known obstacle in the AlGaN/GaN HEMTs. In order to improve the surface stability of HEMTs, we have investigated the SiN passivation film deposited by T-CVD, and we found that it improves both gate leakage current and current collapse phenomenon [1]. Moreover, we compared the T-CVD and PE-CVD passivation films, on high electric field DC and RF characteristics. We found that T-CVD SiN passivation film improves BVds-off by 30% because of the reduction of gate leakage current. It also improved ηd in the output power characteristics by load-pull measurement, which indicates the decrease of the current collapse phenomenon. Also we fabricated a multi-fingered 50 W-class AlGaN/GaN HEMT with T-CVD SiN passivation film and achieved 61.2% of high drain efficiency at frequency of 2.14 GHz, which was 3.6 points higher than that with PE-CVD SiN passivation film.

Quantum circuits for elementary arithmetic operations are important not only for implementing Shor's factoring algorithm on a quantum computer but also for understanding the computational power of small quantum circuits, such as linear-size or logarithmic-depth quantum circuits. This paper surveys some recent approaches to constructing efficient quantum circuits for elementary arithmetic operations and their applications to Shor's factoring algorithm. It covers addition, comparison, and the quantum Fourier transform used for addition.

Quantum computations have so far proved to be more powerful than classical computations, but quantum computers still have not been put into practical use due to several technical issues. One of the most serious problems for realizing quantum computers is decoherence that occurs inevitably since our apparatus are surrounded with environment and open systems. In this paper, we give some surveys on a variety of effects of decoherence in quantum algorithms such as Grover's database search and quantum walks, and we show how quantum algorithms work under decoherence, how sensitive they are against decoherence, and how to implement a robust quantum circuit.

Testing and diagnosis techniques play a key role in the advance of semiconductor memory technology. The challenge of failure detection has created intensive investigation on efficient testing and diagnosis algorithm for better fault coverage and diagnostic resolution. At present, March test algorithm is used to detect and diagnose all faults related to Random Access Memories. However, the test and diagnosis process are mainly done manually. Due to this, a systematic approach for developing and evaluating memory test algorithm is required. This work is focused on incorporating the March based test algorithm using a software simulator tool for implementing a fast and systematic memory testing algorithm. The simulator allows a user through a GUI to select a March based test algorithm depending on the desired fault coverage and diagnostic resolution. Experimental results show that using the simulator for testing is more efficient than that of the traditional testing algorithm. This new simulator makes it possible for a detailed list of stuck-at faults, transition faults and coupling faults covered by each algorithm and its percentage to be displayed after a set of test algorithms has been chosen. The percentage of diagnostic resolution is also displayed. This proves that the simulator reduces the trade-off between test time, fault coverage and diagnostic resolution. Moreover, the chosen algorithm can be applied to incorporate with memory built-in self-test and diagnosis, to have a better fault coverage and diagnostic resolution. Universities and industry involved in memory Built-in-Self test, Built-in-Self repair and Built-in-Self diagnose will benefit by saving a few years on researching an efficient algorithm to be implemented in their designs.

Ant colony optimization (ACO) algorithms are a recently developed, population-based approach which has been successfully applied to optimization problems. However, in the ACO algorithms it is difficult to adjust the balance between intensification and diversification and thus the performance is not always very well. In this work, we propose an improved ACO algorithm in which some of ants can evolve by performing genetic operation, and the balance between intensification and diversification can be adjusted by numbers of ants which perform genetic operation. The proposed algorithm is tested by simulating the Traveling Salesman Problem (TSP). Experimental studies show that the proposed ACO algorithm with genetic operation has superior performance when compared to other existing ACO algorithms.

Wireless ad hoc networks have fundamentally altered today's battlefield, with applications ranging from unmanned air vehicles to randomly deployed sensor networks. Security and vulnerabilities in wireless ad hoc networks have been considered at different layers, and many attack strategies have been proposed, including denial of service (DoS) through the intelligent jamming of the most critical packet types of flows in a network. This paper investigates the effectiveness of intelligent jamming in wireless ad hoc networks using the Dynamic Source Routing (DSR) and TCP protocols and introduces an intelligent classifier to facilitate the jamming of such networks. Assuming encrypted packet headers and contents, our classifier is based solely on the observable characteristics of size, inter-arrival timing, and direction and classifies packets with up to 99.4% accuracy in our experiments.

This paper proposes an adaptive selection algorithm for the surviving symbol replica candidates (ASESS) based on the maximum reliability in maximum likelihood detection with QR decomposition and the M-algorithm (QRM-MLD) for Orthogonal Frequency Division Multiplexing (OFDM) multiple-input multiple-output (MIMO) multiplexing. In the proposed algorithm, symbol replica candidates newly-added at each stage are ranked for each surviving symbol replica from the previous stage using multiple quadrant detection. Then, branch metrics are calculated only for the minimum number of symbol replica candidates with a high level of reliability using an iterative loop based on symbol ranking results. Computer simulation results show that the computational complexity of the QRM-MLD employing the proposed ASESS algorithm is reduced to approximately 1/4 and 1/1200 compared to that of the original QRM-MLD and that of the conventional MLD with squared Euclidian distance calculations for all symbol replica candidates, respectively, assuming the identical achievable average packet error rate (PER) performance in 4-by-4 MIMO multiplexing with 16QAM data modulation. The results also show that 1-Gbps throughput is achieved at the average received signal energy per bit-to-noise power spectrum density ratio (Eb/N0) per receiver antenna of approximately 9 dB using the ASESS algorithm in QRM-MLD associated with 16QAM modulation and Turbo coding with the coding rate of 8/9 assuming a 100-MHz bandwidth for a 12-path Rayleigh fading channel (root mean square (r.m.s.) delay spread of 0.26 µs and maximum Doppler frequency of 20 Hz).

We propose a polynomial-time algorithm for the scheduling of real-time parallel tasks on multicore processors. The proposed algorithm always finds a feasible schedule using the minimum number of processing cores, where tasks have properties of linear speedup, flexible preemption, arbitrary deadlines and arrivals, and parallelism bound. The time complexity of the proposed algorithm is O(M3log N) for M tasks and N processors in the worst case.

As a flexible, cost effective solution for a large-scale access network to the Internet, we have studied the design optimization of the Wireless Internet-access Mesh NETwork (WIMNET). WIMNET consists of multiple access points (APs) that have wireless links between them mainly on the wireless distribution system (WDS). In WIMNET, the links around the Internet gateway can be bottlenecks because every packet passes through it after multihop link activations. Besides, the link quality may be degraded by obstacles in indoor environments. Thus, the proper allocation of APs is essential in WIMNET, so that the communication quality should be ensured while the installation and management cost be minimized. In this paper, we formulate this AP allocation problem for indoor environments in WIMNET with the proof of the NP-completeness of its decision version. Then, we present its two-stage heuristic algorithm composed of the initial greedy allocation and the iterative improvement. The effectiveness of our proposal is verified through extensive simulations in three indoor environments.

Recently, a promising packet forwarding architecture COPE was proposed to essentially improve the throughput of multihop wireless networks, where each network node can intelligently encode multiple packets together and forward them in a single transmission. However, COPE is still in its infancy and has the following limitations: (1) COPE adopts the FIFO packet scheduling and thus does not provide different priorities for different types of packets. (2) COPE simply classifies all packets destined to the same nexthop into small-size or large-size virtual queues and examines only the head packet of each virtual queue to find coding solutions. Such a queueing structure will lose some potential coding opportunities, because among packets destined to the same nexthop at most two packets (the head packets of small-size and large-size queues) will be examined in the coding process, regardless of the number of flows. (3) The coding algorithm adopted in COPE is fast but cannot always find good solutions. In order to address the above limitations, in this paper we first present a new queueing structure for COPE, which can provide more potential coding opportunities, and then propose a new packet scheduling algorithm for this queueing structure to assign different priorities to different types of packets. Finally, we propose an efficient coding algorithm to find appropriate packets for coding. Simulation results demonstrate that this new COPE architecture can further greatly improve the node transmission efficiency.

Nonnegative matrix factorization (NMF) and its extensions such as Nonnegative Tensor Factorization (NTF) have become prominent techniques for blind sources separation (BSS), analysis of image databases, data mining and other information retrieval and clustering applications. In this paper we propose a family of efficient algorithms for NMF/NTF, as well as sparse nonnegative coding and representation, that has many potential applications in computational neuroscience, multi-sensory processing, compressed sensing and multidimensional data analysis. We have developed a class of optimized local algorithms which are referred to as Hierarchical Alternating Least Squares (HALS) algorithms. For these purposes, we have performed sequential constrained minimization on a set of squared Euclidean distances. We then extend this approach to robust cost functions using the alpha and beta divergences and derive flexible update rules. Our algorithms are locally stable and work well for NMF-based blind source separation (BSS) not only for the over-determined case but also for an under-determined (over-complete) case (i.e., for a system which has less sensors than sources) if data are sufficiently sparse. The NMF learning rules are extended and generalized for N-th order nonnegative tensor factorization (NTF). Moreover, these algorithms can be tuned to different noise statistics by adjusting a single parameter. Extensive experimental results confirm the accuracy and computational performance of the developed algorithms, especially, with usage of multi-layer hierarchical NMF approach [3].

In this paper, we propose a novel Hidden-terminal and Exposed-terminal Interference aware routing metric (HEI-ETT) for Multi-Radio and Multi-Rate wireless mesh networks in which each stationary mesh node is equipped with multi-radio interfaces that relays traffic to the extend networks by using multi-hop transmissions. We have two main design goals for HEI-ETT. First, we will characterize interferences as Hidden-terminal Interference and Exposed-terminal Interference regardless of inter- or intra-flow interference and should take into account both interference effects while computing the path metric. Second, an efficient transmission rate adaptation should be employed in HEI-ETT to enhance the network throughput. We incorporated our metric in well known Optimized Link State Routing protocol version 2 (OLSRv2) which is one of the two standard routing protocols for MANETs and evaluated the performance of our metric by simulation. The results show that our metric outperforms existing metrics such as ETX, ETT and WCETT.

Multiple Input Multiple Output (MIMO) represents a highly promising technique for 4G communication networks as it uses multiple antennas at the transmitter and receiver to improve the reliability of transmissions and to provide a high data rate. This paper introduces an adjustable scheduling algorithm for multi-user MIMO systems that can provide an advantageous trade-off solution between throughput maximization and fair resource allocation among users. Specifically, our algorithm is proposed as a solution to system requirement issues through the flexible control of fairness factors.

Role-based access control (RBAC) is widely used as an access control mechanism in various computer systems. Since an organization's lines of authority influence the authorized privileges of jobs, roles also form a hierarchical structure. A role graph is a model that represents role hierarchies and is suitable for the runtime phase of RBAC deployment. Since a role graph cannot take various forms for given roles and cannot handle abstraction of roles well, however, it is not suitable for the design phase of RBAC deployment. Hence, an extended role graph, which can take a more flexible form than that of a role graph, is proposed. The extended role graph improves diversity and clarifies abstraction of roles, making it suitable for the design phase. An equivalent transformation algorithm (ETA), for transforming an extended role graph into an equivalent role graph, is also proposed. Using the ETA, system administrators can deploy efficiently RBAC by using an extended role graph in the design phase and a standard role graph in the runtime phase.

The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.

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].

An adaptive zero forcing maximum likelihood soft input soft output (AZFML-SISO) detector for multiple input multiple output (MIMO) wireless systems is presented. Its performance in an iterative MIMO receiver is analyzed. The AZFML-SISO detector calculates the soft outputs, applying the ML approach to the list that contains only those signal vectors limited by a hypersphere around the zero forcing (ZF) solution. The performance of the algorithm is evaluated on a communication system based on the standard for single carrier broadband wireless communication IEEE 802.16, with three transmit and three receive antennas. It is shown by computer simulation that the computational complexity in an average sense of the receiver running the AZFML-SISO algorithm is reduced by 90% at the SNR values of 30 dB and by 50% for SNR values of 15 dB in comparison to the receiver with an ML detector, while the system performance degrades by less than 1 dB.

This paper deals with a strategic issue in the stable marriage model with complete preference lists (i.e., a preference list of an agent is a permutation of all the members of the opposite sex). Given complete preference lists of n men over n women, and a marriage µ, we consider the problem for finding preference lists of n women over n men such that the men-proposing deferred acceptance algorithm (Gale-Shapley algorithm) adopted to the lists produces µ. We show a simple necessary and sufficient condition for the existence of a set of preference lists of women over men. Our condition directly gives an O(n2) time algorithm for finding a set of preference lists, if it exists.