Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

This paper presents the analysis of integrated voice and data cellular networks with channel borrowing. Our considered system gives higher priority to handoff calls over new calls from users' point of view and reflects each characteristics of voice and data traffic types. Data handoff calls can wait in a queue while they are in handoff areas if there are no channels available. Voice handoff calls can borrow at most l channels from data calls if there are no idle channels upon their arrivals. We mathematically model this system by applying queueing theory. Then, we analyze its performance to derive the forced termination probability of data handoff calls, the blocking probabilities of the new and handoff calls of voice and data, and the Laplace Stieltjes transform for the distribution of waiting time in a queue. In numerical results, the analytical results for the mean waiting time of data handoff calls are compared with the simulation results to validate our analytical approach. Our system is also compared with the system where channel borrowing cannot be allowed (nonborrowing system) with respect to the blocking probabilities of the new and handoff calls of voice and data, the forced termination probability of data handoff calls, the mean and the coefficient of variation of the waiting time of data handoff calls.

In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.

This paper considers combining receptions with multiple receive antennas for space time coded MPSK signals over correlated Rayleigh fading channels. For the system with dual-antenna at receiver, a new transform is proposed, which can convert the correlated fading signals into uncorrelated ones. With the results obtained by using the proposed transform, the equivalent selective combining (SC) reception and maximum likelihood (ML) reception are presented. Theoretical analysis shows that ML reception has better performance than SC reception in terms of bit error rate. For the system with triple antenna at receiver, the simulation results are presented by using Monte Carlo method. All the results show that compared to using a receive antenna, a considerable signal to noise ratio gain can be obtained by using multiple receive antennas when the correlation coefficients among the receive antennas is not too high.

A uniform raised-salicide technology has been investigated using both uniform selective-epitaxial-growth (SEG) silicon and salicide films, to reduce a junction leakage current of shallow source/drain (S/D) regions for high-performance CMOS devices. The uniform SEG-Si film without pits is formed by using a wet process, which is a carbon-free oxide removal only using a dilute hydrofluoric acid (DHF) dipping, prior to the Si-SEG process. After a titanium-salicide formation using a conventional two-step salicide process, this uniform SEG-Si film achieves good S/D junction characteristics. The uniform titanium-salicide film without bowing into a silicon is formed by a smaller Ti/SEG-Si thickness ratio, which results in a low sheet resistance of 5 Ω/sq. without a narrow-line effect. Furthermore, the drive current is maximized by this raised-salicide film using a Ti/SEG-Si thickness ratio of 1.0.

In this paper, we propose a new approach to the adaptive MLSE receiver, which is based on the delay estimation of the paths in the fading channel. The path delays are estimated by using the known training sequence, and based on this estimation the proposed MLSE tracks not the T-spaced equivalent channel but the variations of each path in the frequency-selective channel directly. It will be shown through computer simulations that the proposed MLSE can improve the performance of the conventional MLSE receivers, when the number of paths is small.

We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing and H(k) for polymatroid covering, where k is the largest rank of an element in a polymatroid, and H(k)=Σi=1k 1/i is the kth Harmonic number. The main contribution of this note is to improve these bounds by slightly extending the greedy heuristics. Specifically, it will be shown how to obtain approximation factors of 2/(k+1) for packing and H(k)-1/6 for covering, generalizing some existing results on k-set packing, matroid matching, and k-set cover problems.

We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.

We propose a subchannel power control scheme in the OFDM system, which transmits data with a variable power level for each subchannel based on the received SNR. The OFDM system, employing the D-QPSK modulation and the proposed subchannel power control with a grouping coefficient equal to 3, gives about 2.3 dB gain in Eb/N0 comparing with the conventional OFDM system, under the two-ray multipath channel with the mean value of the second-ray's attenuation coefficient equal to 0.25, for the required BER equal to 10-5.

A lithium-ion (Li-ion) battery protection IC with an average current of 0.99 µA (at a battery voltage of 3.6 V) and a standby current (after detecting over-discharge) less than 0.01 µA is presented. This low power performance is achieved via a power-on duty-cycle technique. The protection circuit samples the voltage of the battery periodically and powers down during the rest of time. This Li-ion battery protector provides over-charge, over-discharge, excess-current and short circuits protection. This protection IC was implemented in a 0.6-µm CMOS technology and the active area is 880 µm 780 µm.

This letter proposes a design methodology of a capacitor for a switched capacitor filter. The capacitor design method makes the capacitor accurate to the capacitance ratio and insensitive to the process deviation. The SCF designed is used for the PCM CODEC filter and the deviation of the frequency characteristic is below 0.05 dB for a process deviation 0.5 µm in 5 µm CMOS process.

This paper presents effective methods to calculate dual frame of the short-time Fourier expansion (STFE) in l2(Z). Based on a relationship between the prototype window used for generating a frame and the dual prototype window used for generating a dual frame in the STFE, two useful numerical methods with a finite frame operator are proposed to obtain finite support dual frames in time domain formulation. The methods can be used to construct the multiple STFE (MSTFE) suitable for a time-frequency analysis, synthesis and coding of discrete-time nonstationary signals. Numerical simulation results are given to verify the effectiveness of the calculation of dual frame.

A radio network is a distributed system with no central shared resource, consisting of n stations each equipped with a radio transceiver. One of the most important parameters to evaluate protocols in the radio networks is the number of awake time slots in which each individual station sends/receives a data packet. We are interested in devising energy-efficient initialization protocols in the single-hop radio network (RN, for short) that assign unique IDs in the range [1,n] to the n stations using few awake time slots. It is known that the RN can be initialized in O(log log n) awake time slots, with high probability, if every station knows the number n of stations in the RN. Also, it has been shown that the RN can be initialized in O(log n) awake time slots even if no station knows n. However, it has been open whether the initialization can be performed in O(log log n) awake time slots when no station knows n. Our main contribution is to provide the breakthrough: we show that even if no station knows n, the RN can be initialized by our protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log log n) time slots. We then go on to design an initialization protocol for the k-channel RN that terminates, with high probability, in O(n/k + (log n)2) time slots with no station being awake for more than O(log log n) time slots.

Practical image restoration filters usually include a parameter that controls regularizability, trade-off between fidelity of a restored image and smoothness of it, and so on. Many criteria for choosing such a parameter have been proposed. However, the relation between these criteria and the squared error of a restored image, which is usually used to evaluate the restoration performance, has not been theoretically substantiated. Sugiyama and Ogawa proposed the subspace information criterion (SIC) for model selection of supervised learning problems and showed that the SIC is an unbiased estimator of the expected squared error between the unknown model function and an estimated one. They also applied it to restoration of images. However, we need an unbiased estimator of the unknown original image to construct the criterion, so it can not be used for general situations. In this paper, we present a modified version of the SIC as a new criterion for choosing a parameter of image restoration filters. Some numerical examples are also shown to verify the efficacy of the proposed criterion.

In this letter, we propose high-speed binary to residue converters for moduli 2n, 2n 1 without using look-up table. For integration of residue arithmetic circuit using a signed-digit (SD) number representation with ordinary binary system, the proposed circuits carry out the efficient conversion. Using SD adders instead of ordinary adders that are used in conventional binary to residue converter, the high-speed conversion without the carry propagation can be achieved. Thus, the proposed converter is independent of the size of modulus and can speed up the binary to residue conversion. On the simulation, the conversion delay times are 1.78 ns for modulus 210-1 and 1.73 ns for modulus 210+1 under the condition of 0.6 µm CMOS technology, respectively. The active area of the proposed converter for moduli 210 1 is 335 µm325 µm.

A novel power spectral density accumulation (PSDA) method for estimating the bandwidth of the clutter spectra is proposed, based on a priori knowledge of the shape of the clutter spectra. The comparison of the complexity and the performance between the PSDA method and the general ones is presented. It is shown that the PSDA method is effective for the short-time clutter data in the practical application.

Precise interconnect analysis is strongly required for giga-scale integration the operation frequency of which is excess 10 GHz. In this study, detailed and accurate analyses of a coaxial interconnect and an actual rectangular interconnect have been performed by the direct evaluation of Maxwell's equations and the finite element method, respectively. It has been revealed that there are two propagation modes for LSI interconnects: skin depth limited propagation mode and interconnect induced slow wave mode. In a miniaturized interconnect, the propagation mode is the interconnect induced slow wave mode; therefore, we cannot obtain the light-speed propagation due to such an interconnect-induced effect. In order to overcome this speed limitation or to improve signal integrity, it is essential to introduce a short interconnect for a miniaturized structure, and a much larger interconnect than the skin depth. We propose a gas-isolated interconnect as a candidate for an ultimately low-k structure in order to increase the signal-propagation speed. By the introduction of such structures, the performance of miniaturized devices in the deep submicron region will be effectively enhanced.

For ubiquitous computing and communication, a mobile node needs to change upon movements its network- and link-layer points of attachment to the Internet. Conventionally, the network-layer protocol is unaware of the link-layer changes, so IP datagrams to and from a moving node could be lost. Considerable system performance degradation might therefore result. This paper presents a scheme to integrate the handoff procedures of the two layers in the context of Mobile IP with route optimization. Experiment results show that our scheme is promising and can reduce packet loss due to host migrations substantially.

This paper describes the concept of an adaptive network, that is, a network environment that can rapidly and autonomously adapt its behavior according to network conditions and traffic status. The user interface of the adaptive network can access any resource in the network as a memory-mapped I/O device, as if it were attached to the local bus of the user's PC. This network concept has several benefits. From the application development viewpoint, no network related programming is required, and applications do not have to be modified even if the network topologies and protocols are changed. Network maintenance and upgrading can be done anytime without having to worry about the application users, because the network itself is concealed from the applications. In addition, the reconfigurable hardware technology functions as an autonomous network control through the use of a lower-layer protocol. We developed a testbed that makes heterogeneous resources available to users and used it to demonstrate the feasibility of our concept by implementing and running some applications over it.

This paper presents a new decoupling circuit for suppressing radiated emissions due to power plane resonance in multilayer printed circuit boards (PCBs). This circuit is based on transmission line theory, and consists of two decoupling capacitors and one power trace. The two capacitors, one mounted on the power pin of an IC and the other mounted on the common power distribution bus in a board, are connected through the power trace. The characteristic impedance of the trace is much higher than the impedance of the capacitors. In addition, the length of the trace between the capacitors is less than 1/4 the effective wavelength for high frequency (e.g., 1 GHz). Tests we performed on simple PCBs confirm that our decoupling circuit suppresses radiated emissions due to power plane resonance.