A high-speed triangular-modulated spread-spectrum clock generator using a fractional phase-locked loop is presented. The fractional division is implemented by a nested fractional topology, which is constructed from a dual-modulus divide-by-(N-1/16)/N divider to divide the VCO outputs as a first division period and a fractional control circuit to establish a second division period to cause the overall fractional division. The dual-modulus divider introduces a delay-locked-loop network to achieve phase compensation. Operating at the frequency of 3.2 GHz, the measured peak power reduction is around 16 dB for a deviation of 0.37% and a frequency modulation of 33 kHz. The circuit occupies 1.41.4 mm2 in a 0.18-µm CMOS process and consumes 52 mW.

A new subfamily of sequences with optimal correlation properties is constructed for the generalized Kasami set. A lower bound on the linear span is established. It is proved that with suitable choices of parameters, this subfamily has exponentially larger linear spans than either No sequences or TN sequences. A class of sequences with ideal autocorrelation is also proved to have large linear span.

Consider an undirected multigraph G=(V,E) with n vertices and m edges, and let Ni denote the number of connected spanning subgraphs with i(min) edges in G. Recently, we showed in [3] the validity of (m-i+1)Ni-1>Ni for a simple graph and each i(min). Note that, from this inequality, 2 is easily derived. In this paper, for a multigraph G and all i(min), we prove (m-i+1)Ni-1(i-n+2)Ni, and give a necessary and sufficient condition by which (m-i+1)Ni-1=(i-n+2)Ni. In particular, this means that (m-i+1)Ni-1>Ni is not valid for all multigraphs, in general. Furthermore, we prove 2, which is not straightforwardly derived from (m-i+1)Ni-1(i-n+2)Ni, and also introduce a necessary and sufficent condition by which =2. Moreover, we show a sufficient condition for a multigraph to have Nn2>Nn-1Nn+1. As special cases of the sufficient condition, we show that if G contains at least +1 multiple edges between some pair of vertices, or if its underlying simple graph has no cycle with length more than 4, then Nn2>Nn-1Nn+1.

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. If the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set ej ⊆ V of items and assigns valuation w(ej) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.

Effect of the post-growth annealing on the morphology of a Ge mesa selectively grown on Si was studied from the viewpoint of near-infrared photodiode applications. By ultrahigh-vacuum chemical vapor deposition, Ge mesas were selectively grown at 600 on Si (001) substrates partially covered with SiO2 masks. The as-grown Ge mesas showed trapezoidal cross-sections having a top (001) surface and {311} sidewall facets, as similar to previous reports. However, after the subsequent post-growth annealing at ~800 in the ultrahigh-vacuum chamber, the mesas were deformed into rounded shapes having a depression at the center and mounds near the edges. Such a deformation cannot be observed for the samples annealed once after cooled and exposed to the air. The residual hydrogen atoms on the Ge surface from the germane (GeH4) decomposition is regarded as a trigger to the observed morphological instability, while the final mesa shape is determined in order to minimize a sum of the surface and/or strain energies.

Multi-carrier code division multiple access (MC-CDMA) has been considered as one of the promising techniques for the next generation of mobile communication systems because of its efficient bandwidth usage, robustness to the multi-path fading and simple channel-sharing scheme. However, MC-CDMA cannot be employed in the uplink communication where the transmitted signal from each user propagates through the different multi-path fading channel, and the received signals are no longer orthogonal at the base station. As a result, bit error rate (BER) performance in the uplink MC-CDMA communication would be strongly degraded due to the occurrence of multi-user interference (MUI). To solve the MUI problem in the uplink MC-CDMA, the pre-equalization method was proposed in which the uplink signal is pre-equalized at the user terminal by using the channel response estimated from the downlink. Although the pre-equalization method is very effective for the stationary uplink channel with fixed users, it is hard to be employed in the time varying fading channel with mobile users, because there is a big difference in the channel responses between downlink and uplink. For the efficient MUI compensation, each user terminal would be required to predict the future channel conditions based on the current observation. This paper proposes a method for model based uplink channel response prediction by employing the spectral decomposition of the downlink channel impulse response. Computer simulation results show that the proposed method can achieve the accurate prediction of channel response for mobile users during the uplink transmission and allows the effective MUI compensation.

Due to the proliferation of mobile devices connected to the Internet, implementing a secure and practical Mobile IP has become an important goal. A mobile IP can not work properly without authentication between the mobile node (MN), the home agent (HA) and the foreign agent (FA). In this paper, we propose a practical Mobile IP authentication protocol that uses public key cryptography only during the initial authentication. The proposed scheme is compatible with the conventional Mobile IP protocol and provides scalability against the number of MN's. We also show that the proposed protocol offers secure operation.

For real time image processing, a readout circuit for an infrared focal plane array (IRFPA) involving a new edge detection technique has been proposed in this letter. A non-uniformity correction unit (NUC), essential in an IRFPA because of bad non-uniformity characteristics of IR sensors is eliminated in this circuit by using a noise tolerant edge detection technique. In addition, real time edge detection can be possible, because of pixel-level integration and parallel processing. The proposed readout circuit shows an approximately three to nine times better edge error rate than other available methods using pixel-level parallel processing.

A linear term tree is defined as an edge-labeled rooted tree pattern with ordered children and internal structured variables whose labels are mutually distinct. A variable can be replaced with arbitrary edge-labeled rooted ordered trees. We consider the polynomial time learnability of finite unions of linear term trees in the exact learning model formalized by Angluin. The language L(t) of a linear term tree t is the set of all trees obtained from t by substituting arbitrary edge-labeled rooted ordered trees for all variables in t. Moreover, for a finite set S of linear term trees, we define L(S)=∪t∈S L(t). A target of learning, denoted by T*, is a finite set of linear term trees, where the number of edge labels is infinite. In this paper, for any set T* of m linear term trees (m ≥ 0), we present a query learning algorithm which exactly identifies T* in polynomial time using at most 2mn2 Restricted Subset queries and at most m+1 Equivalence queries, where n is the maximum size of counterexamples. Finally, we note that finite sets of linear term trees are not learnable in polynomial time using Restricted Equivalence, Membership and Subset queries.

This paper discusses the behavior of the second-order modes (Hankel singular values) of linear continuous-time systems under variable transformations with positive-real functions. That is, given a transfer function H(s) and its second-order modes, we analyze the second-order modes of transformed systems H(F(s)), where 1/F(s) is an arbitrary positive-real function. We first discuss the case of lossless positive-real transformations, and show that the second-order modes are invariant under any lossless positive-real transformation. We next consider the case of general positive-real transformations, and reveal that the values of the second-order modes are decreased under any general positive-real transformation. We achieve the derivation of these results by describing the controllability/observability Gramians of transformed systems, with the help of the lossless positive-real lemma, the positive-real lemma, and state-space formulation of transformed systems.

Though machine vision systems for automatically detecting visual defects, called mura, have been developed for thin flat transistor liquid crystal display (TFT-LCD) panels, they have not yet reached a level of reliability which can replace human inspectors. To establish an objective criterion for identifying real defects, some index functions for quantifying defect levels based on human perception have been recently researched. However, while these functions have been verified in the laboratory, further consideration is needed in order to apply them to real systems in the field. To begin with, we should correct the distortion occurring through the capturing of panels. Distortion can cause the defect level in the observed image to differ from that in the panel. There are several known methods to restore the observed image in general vision systems. However, TFT-LCD panel images have a unique background degradation composed of background non-uniformity and vignetting effect which cannot easily be restored through traditional methods. Therefore, in this paper we present a new method to correct background degradation of TFT-LCD panel images using principal component analysis (PCA). Experimental results show that our method properly restores the given observed images and the transformed shape of muras closely approaches the original undistorted shape.

Modern applications of pattern recognition generate very large amounts of data, which require large computational effort to process. However, the majority of the methods intended for large-scale problems aim to merely adapt standard classification methods without considering if those algorithms are appropriated for large-scale problems. CombNET-II was one of the first methods specifically proposed for such kind of a task. Recently, an extension of this model, named CombNET-III, was proposed. The main modifications over the previous model was the substitution of the expert networks by Support Vectors Machines (SVM) and the development of a general probabilistic framework. Although the previous model's performance and flexibility were improved, the low accuracy of the gating network was still compromising CombNET-III's classification results. In addition, due to the use of SVM based experts, the computational complexity is higher than CombNET-II. This paper proposes a new two-layered gating network structure that reduces the compromise between number of clusters and accuracy, increasing the model's performance with only a small complexity increase. This high-accuracy gating network also enables the removal the low confidence expert networks from the decoding procedure. This, in addition to a new faster strategy for calculating multiclass SVM outputs significantly reduced the computational complexity. Experimental results of problems with large number of categories show that the proposed model outperforms the original CombNET-III, while presenting a computational complexity more than one order of magnitude smaller. Moreover, when applied to a database with a large number of samples, it outperformed all compared methods, confirming the proposed model's flexibility.

The Earth will require sustainable electricity sources equivalent to 3 to 5 times the commercial power presently produced by 2050. Solar Power Satellite (SPS) is one option for meeting the huge future energy demand. SPS can send enormous amounts of power to the Earth as the form of microwave (MW). A highly efficient microwave power transmission (MPT) system is needed for SPS. A critical goal of SPS is to maintain highest Beam Efficiency (BE) because the microwaves from SPS will be converted to utility power unlike the MW from communication satellites. Another critical goal of SPS is to maintain Side Lobe Levels (SLL) as small as possible to reduce interference to other communication systems. One way to decrease SLL and increase BE is the edge tapering of a phased array antenna. However, tapering the excitation requires a technically complicated system. Another way of achieving minimum SLL is with randomly spaced element position but it does not guarantee higher BE and the determination of random element position is also a difficult task. Isosceles Trapezoidal Distribution (ITD) edge tapered antenna was studied for SPS as an optimization between full edge tapering and uniform amplitude distribution. The highest Beam Collection Efficiency (BCE) and lowest SLL (except maximum SLL) are possible to achieve in ITD edge tapering and ITD edge tapered antenna is technically better. The performance of ITD is further improved from the perspective of both Maximum Side Lobe Level (MSLL) and BE by using unequal spacing of the antenna elements. A remarkable reduction in MSLL is achieved with ITD edge tapering with Unequal element spacing (ITDU). BE was also highest in ITDU. Determination of unequal element position for ITDU is very easy. ITDU is a newer concept that is experimented for the first time. The merits of ITDU over ITD and Gaussian edge tapering are discussed.

In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.

In this paper, we propose a method that recovers a smooth high-resolution image from several blurred and roughly quantized low-resolution images. For compensation of the quantization effect we introduce measurements of smoothness, Huber function that is originally used for suppression of block noises in a JPEG compressed image [Schultz & Stevenson '94] and a smoothed version of total variation. With a simple operator that approximates the convex projection onto constraint set defined for each quantized image [Hasegawa et al. '05], we propose a method that minimizes these cost functions, which are smooth convex functions, over the intersection of all constraint sets, i.e. the set of all images satisfying all quantization constraints simultaneously, by using hybrid steepest descent method [Yamada & Ogura '04]. Finally in the numerical example we compare images derived by the proposed method, Projections Onto Convex Sets (POCS) based conventinal method, and generalized proposed method minimizing energy of output of Laplacian.

Meeting the tough linearity and noise required by GSM and UMTS receivers in CMOS technology is challenging. A new IIP2 calibration technique based on canceling the second order nonlinearities of mixer, generated in the input RF transistors, is introduced. By using this technique about 22 dB mixer IIP2 improvement is achieved. The proposed calibration circuit can be used in multi-standard mixer because of high bandwidth of the calibration circuitry. Moreover it can work with voltage supplies as low as 1 V. Using this technique a multi-standard mixer supporting PCS, UMTS and IEEE802.11b-g is developed. The design is done in CMOS 65 nm technology with 1.2 V supply while it consumes about 7 mA current.

In this letter, a computational approach for solving cross-coupled algebraic Riccati equations (CAREs) is investigated. The main purpose of this letter is to propose a new algorithm that combines Newton's method with a gradient-based iterative (GI) algorithm for solving CAREs. In particular, it is noteworthy that both a quadratic convergence under an appropriate initial condition and reduction in dimensions for matrix computation are both achieved. A numerical example is provided to demonstrate the efficiency of this proposed algorithm.

This report describes an application of relaxation technique to the alternating direction implicit finite-difference time-domain (ADI-FDTD) method. The ADI-FDTD method is quite stable even when the CFL condition is not satisfied. However, the ADI-FDTD method is computationally more complicate than the conventional FDTD method and this method requires to solving the tri-diagonal matrix equation. Thus, this method may require more computational cost than the standard FDTD method due to the large scale tri-diagonal matrix solution corresponding to a large number of meshes. In this report, relaxation-based solution technique is discussed for the matrix solution and a simple numerical example is shown. As a result, it is confirmed that ADI-FDTD method with the relaxation technique is useful for the acceleration of the electromagnetic field simulation.

This paper presents an automatic adjustment of the transfer function of phase locked loop (PLL). The time constants and the gain factor of the transfer function are adjusted without opening the loop of PLL. The time constant adjustment is performed using a replica of the 1st order RC low pass filter and the gain factor is adjusted by detecting the open loop gain at the unity gain frequency. These adjustments are automatically carried out using a digitally controlled capacitance array and a digitally controlled charge pump. The proposed calibration can reduce the bandwidth error of 30% to 5% and the gain error of 7 dB to 1 dB.

In this paper, we present a new extension of the butterfly digraph, which is known as one of the topologies used for interconnection networks. The butterfly digraph was previously generalized from binary to d-ary. We define a new digraph by adding a signed label to each vertex of the d-ary butterfly digraph. We call this digraph the dihedral butterfly digraph and study its properties. Furthermore, we show that this digraph can be represented as a Cayley graph. It is well known that a butterfly digraph can be represented as a Cayley graph on the wreath product of two cyclic groups [1]. We prove that a dihedral butterfly digraph can be represented as a Cayley graph in two ways.