Adaptive Battery Conservation Management (ABCM), an effective form of power conservation for mobile terminals in an always-connected environment, was proposed and evaluated in a previous published work. The ABCM method employs three states: active, dormant, and the Battery Saving Mode (BSM). The BSM is defined as a battery-saving state; in the BSM, the mobile terminal saves power by intermittently receiving paging notifications via a paging channel between the packet bursts of a session. Two control parameters, the sleep-timer and paging interval, are set up according to packet class and are the keys to the performance of a system with this method. In real-time communications, a long sleep-timer and short paging interval are selected to minimize buffering delay. In non-real-time communications, on the other hand, a short sleep-timer and long paging interval are chosen to reduce power consumption by the mobile terminal. Our previous evaluation showed that the method is effective as a means for power conservation in non-real-time communications. In real-time communications, on the other hand, the ABCM method provides shorter buffering delays and the same battery-conservation performance as the conventional method. To further improve the ABCM method's performance, we now propose an enhanced ABCM method that employs multiple BSM sub-modes, each of which has a different paging interval. As dormant periods become longer, the mobile terminal makes transition to successive sub-modes, each of which has a longer interval than the previous one. In this paper, we evaluate the battery conservation effect of the ABCM method through theoretical analysis and computer simulation. Numerical evaluation indicates that the ABCM method will be suitable for the broadband multimedia packet-radio systems of the future.

This paper describes the design of a 2.7 V operational, 200 MS/s, 14-bit CMOS D/A converter (DAC). The DAC consists of 63 current cells in matrix form for an upper 6-bit sub-DAC, and 8 current cells and R-2R ladder resistors for a lower 8-bit sub-DAC. A source degeneration resistor, for which a transistor in the triode operational region is used, is connected to the source of a MOS current source transistor in a current cell in order to reduce the influence of threshold voltage (Vth) variation and to satisfy the differential nonlinearity error specification as a 14-bit DAC. In conventional high-speed and high-resolution DACs that have the same design specifications described here, spurious-free dynamic range (SFDR) characteristics commonly deteriorate drastically as the frequency of the reconstructed waveform increases. The causes of this deterioration were carefully examined in the present study, finding that the deterioration is caused in part by the input-data-dependent time-constant change at the output terminal. Unexpected current flow in parasitic capacitors associated with current sources causes the change in the output current depending on the input data, resulting in time-constant change. In order to solve this problem, we propose a new output circuit to fix the voltage at the node where the outputs of the current sources are combined. SPICE circuit simulation demonstrates that 63 dB of SFDR characteristics for the 90 MHz reconstructed waveform at the output can be realizable when the supply voltage is 2.7 V, the clock rate is 200 MS/s, and the power dissipation is estimated to be 300 mW.

Mathematical analysis of the average behavior of the AVL balanced tree insertion algorithm has not ever been done completely. As the first step toward this analysis, we have proposed an approximate analysis based on the assumption that all AVL balanced trees with a given number of nodes and height are constructed with equal probability. In this paper, we propose a new analysis of the AVL balanced tree insertion algorithm in conformity with that all n! permutations of n keys occur with equal probability. First we derive the formulae to enumerate the number of permutations constructing the AVL balanced trees with a given number of nodes and height. Then, we propose the formulae to evaluate the average behavior of the AVL balanced tree insertion algorithm and show some results from the proposed formulae.

Micali and Rivest have proposed a transitive signature scheme for an undirected graph, which is suitable for signing data with undirected graph structure. The problem of finding a transitive signature scheme for a directed graph has remained an open problem. In this paper, we propose a transitive signature scheme for a directed tree. Since the directed tree is a special case of the directed graph, the proposed scheme is a partial solution for the open problem. We also show that a transitive signature scheme for the undirected graph can be constructed from a bundling homomorphism. This means that the transitive signature scheme for the undirected graph is closely related with a fail-stop signature scheme.

Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence Nn-1,Nn,...,Nm is #P-complete (see e.g.,[3]), where Ni denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence Nn-1,Nn,...,Nm, we show an interesting and stronger property that the sequence γn-1,γn,...,γm, where γi denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence Nn-1,Nn,...,Nm.

In 1991 Girault proposed a key agreement protocol based on his new idea of self-certified public key. Later Rueppel and Oorschot showed variants of the Girault scheme. All of these key agreement protocols inherit positive features of self-certified public key so that they can provide higher security and smaller communication overhead than key agreement protocols not based on self-certified public key. Even with such novel features, rigorous security of these protocols has not been made clear yet. In this paper, we give rigorous security analysis of the original and variants of Girault key agreement protocol under several kinds of active attacker models. In particular we show that protocols are either insecure or proven as secure as the Diffie-Hellman problem over Zn with respect to the reduction among functions of computing them. Analyzed protocols include a new variant of 1-pass protocol. As opposed to the original 1-pass protocol, the new variant provides mutual implicit key authentication without increasing the number of passes.

Decreased power dissipation and transient voltage drops in CMOS power distribution networks are important for high-speed deep submicrometer CMOS integrated circuits. In this paper, three CMOS buffers based on the charge-transfer, split-path and bootstrapped techniques to reduce the power dissipation and transient voltage drop in power supply are proposed. First, the inverted-delay-unit is used in the low-power inverted-delay-unit (LPID) CMOS buffer to eliminate the short-circuit current of the output stage. Second, the low-swing bootstrapped feedback-controlled split-path (LBFS) CMOS buffer is proposed to eliminate the short-circuit current of the output stage by using the feedback-controlled split-path method. The dynamic power dissipation of the LBFS CMOS buffer can be reduced by limiting the gate voltage swing of the output stage. Moreover, the propagation delay of the LBFS CMOS buffer is also reduced by non-full-swing gate voltage of the output stage. Third, the charge-recovery scheme is used in the charge-transfer feedback-controlled 4-split-path (CRFS) CMOS buffer to recovery and pull up the gate voltage of the output stage for reducing power-delay product and power line noise. Based on HSPICE simulation results, the power-delay product and the transient voltage drop in power supply of the proposed three CMOS buffers can be reduced by 20% to 40% as compared to conventional CMOS tapered buffer under various capacitive load.

Obtaining a linearizing feedback and a coordinate transformation map is very difficult, even though the system is feedback linearizable. It is known that finding a desired transformation map and feedback is equivalent to finding an integrating factor for an annihilating one-form for single input nonlinear systems. It is also known that such an integrating factor can be approximated using the simple C.I.R method and tensor product splines. In this paper, it is shown that m integrating factors can always be approximated whenever a nonlinear system with m inputs is feedback linearizable. Next, m zero-forms can be constructed by utilizing these m integrating factors and the same methodology in the single input case. Hence, the coordinate transformation map is obtained.

In this paper, the problem of output feedback passification for nonlinear systems is considered. Contrary to the conventional methodologies, our approach does not require the normal form representation of the system. Consequent advantages include that the system need not have a well-defined relative degree. In particular, we present a necessary and sufficient condition for output feedback passification without relying on the normal form. The proposed condition finally leads to an extension for a recent result when the system does have a normal form.

In this paper we study traffic engineering in Multiprotocol Label Switching (MPLS) networks. We consider off-line computation of disjoint working and restoration paths where path rerouting is used as the restoration scheme. We first compute maximum number of paths for each demand such that paths satisfy diversity requirements. Using the generated path set we study four different approaches for selecting working and restoration paths, and formulate each method as an Integer Linear Programming (ILP) problem. The first two methods treat working and restoration path design problems separately. We propose two new path design methods that jointly optimize the working and restoration paths. A traffic uncertainty model is developed in order to evaluate performances of these four approaches based on their robustness with respect to changing traffic patterns. We compare these design approaches based on the number of additional demands carried and the distribution of residual capacity over the network. It is shown through simulations that the weighted load balancing method proposed in this paper outperforms the other three methods in handling traffic demand uncertainty.

We propose a new scheme of indoor optical wireless LAN based on a special CMOS image sensor (CIS), which realizes a low-power compact communication module with large uplink capacity due to space division multiple access. In our scheme, all nodes and a hub utilize the CIS as a photoreceiver as well as a position-sensing device for finding the positions of the communication modules, while a single large photodiode is used in the conventional systems. Although conventional image sensors cannot detect modulated signals because they integrate photocurrents, our CIS has a high-speed readout function for receiving optical data from the specific pixels receiving optical signals. The advantages of the proposed scheme are 1) compact embodiment of the communication module due to no need of the bulky mechanical components for searching the other modules, 2) space division multiple access, which leads to 3) large capacity of uplink, and 4) applicability of simple modulation and coding schemes for optical signals. In our scheme, diffusive and narrow beam lights are complementally used for position detection and communication, respectively, which leads to the advantage 5) low power consumption of both light emitter and receiver circuits. To demonstrate two basic functional modes of our CIS: an IS (image sensor) mode and a COM (communication) mode, we fabricate an 88-pixel CIS by use of a 0.8µm BiCMOS technology. In the experiments, the image of a light source is successfully captured in the IS mode for integration time of 29.6msec and optical power of 1.1nW. After the functional mode of the pixel receiving the light is changed to the COM mode, the eye pattern of the modulated light is obtained from the pixel at frequency of 1MHz. We also fabricate a test pixel circuit with in-pixel amplifier, with which operation speed is improved to 100MHz.

Bidirected graphs which are generalizations of undirected graphs, have three types of edges: (+,+)-edges, (-,-)-edges and (+,-)-edges. Undirected graphs are regarded as bidirected graphs whose edges are all of type (+,+). The notion of perfection of undirected graphs can be naturally extended to bidirected graphs in terms of polytopes. The fact that a bidirected graph is perfect if and only if the undirected graph obtained by replacing all edges to (+,+) is perfect was independently proved by several researchers. This paper gives a polyhedral proof of the fact and introduces some new knowledge on perfect bidirected graphs.

Seeding substrates with diamond nanocrystals has been considered to be a promising nondestructive pretreatment method for growth of diamond films. However, its application is strongly impeded by the segregation of diamond nanocrystals on substrates. In the present study, we suggest a very simple but effective seeding way ("sandwich" (SW) seeding way) to prevent nanocrystals from segregation. By the SW seeding way, the diamond nanocrystals can be nearly uniformly dispersed on Si substrates with the areal density of the order of 108cm-2. On the nano-seeded Si substrates the continuous and homogeneous diamond films can be successfully fabricated using a microwave plasma enhanced chemical-vapor-deposition (MPECVD) equipment. The cross-sectional transmission electron microscopy (TEM) images reveal that compare with the diamond films grown on the Si substrates pretreated by the conventional scratching method, the films deposited on the nano-seeded Si substrates present a much flatter interfacial structure, suggesting that the SW seeding way can effectively reduce the interface coarseness.

In this paper, we propose a novel pulse-coupled neural network (PCNN) simulator using a programmable gate array (PGA) technique. The simulator is composed of modified phase-locked loops (PLLs) and a programmable gate array (PGA). The PLL, which is modified by the addition of multiple inputs and multiple feedbacks, works as a neuron. The PGA, which controls the network connection, works as nodes of dendritic trees. This simulator, which has 16 neurons and 32 32 network connections, is designed on a chip (4.73mm 4.73mm), and its basic operations such as synchronization, an oscillatory associative memory, and FM interactions are confirmed using circuit simulator SPICE.

Our work introduces a speech enhancement algorithm that modifies on-line the spectral representation of degraded speech to approximate the spectral coefficients of high quality speech. The proposed framework is based on the application of Discrete Fourier Transform (DFT) to a large ensemble of clean speech frames and the estimation of parametric, heavy-tail non-Gaussian probability distributions for the spectral magnitude. Each clean spectral band possesses a unique pdf. This is selected according to the smallest Kullback-Leibler divergence between each candidate heavy-tail pdf and the non-parametric pdf of the magnitude of each spectral band of the clean ensemble. The parameters of the distributions are derived by Maximum Likelihood Estimation (MLE). A maximum a-posteriori (MAP) formulation of the degraded spectral bands leads to soft threshold functions, optimally derived from the statistics of each spectral band and effectively reducing white and slowly varying coloured Gaussian noise. We evaluate the new algorithm on the task of improving the quality of speech perception as well as Automatic Speech Recognition (ASR) and demonstrate its robustness at SNRs as low as 0 dB.

A dual greedy polyhedron is defined by a system of linear inequalities, where the right-hand sides are given by a submodular function and the coefficients matrix is given by the incidence vectors of antichains of a rooted forest. Faigle and Kern introduced this concept and showed that a dual greedy algorithm works for the linear program over dual greedy polyhedra. In this paper, we show that a dual greedy polyhedron is the isomorphic image of an ordinary submodular polyhedron under the Mobius function of the underlying rooted forest. This observation enables us to reduce linear optimization problems over dual greedy polyhedra to those over ordinary submodular polyhedra. We show a new max-min theorem for intersection of two dual greedy polyhedra as well.

Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using (Δ1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using (n 1-3/(k+1)) colors. This improved Wigderson's algorithm, which uses O(n1-1/(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses (Δ 1-x/k) colors for 2

The problem of constructing the suffix tree of a tree is a generalization of the problem of constructing the suffix tree of a string. It has many applications, such as in minimizing the size of sequential transducers and in tree pattern matching. The best-known algorithm for this problem is Breslauer's O(nlog |Σ|) time algorithm where n is the size of the CS-tree and |Σ| is the alphabet size, which requires O(nlog n) time if |Σ| is large. We improve this bound by giving an optimal linear time algorithm for integer alphabets. We also describe a new data structure, the Bsuffix tree, which enables efficient query for patterns of completely balanced k-ary trees from a k-ary tree or forest. We also propose an optimal O(n) algorithm for constructing the Bsuffix tree for integer alphabets.

Some of the recent digital systems have a serious clock skew problem due to huge hardware implementation and high-speed operation in VLSI's. To overcome this problem, clock distribution techniques and, more notably, asynchronous system design methodologies have been investigated. Since the latest asynchronous digital systems use two-rail logic with two-phase data transfer manner, more than two-fold hardware is required in comparison with the synchronous system. In this article, we present a design of asynchronous digital system which is based on B-ternary logic that can process binary data. The system which is based on speed-independent mode consists of data-path and its controller. Then we provide B-ternary two-phase binary data processing in the data-path and its control procedure with hand-shake protocol. To implement the system some functional elements are presented, that is, a ternary-in/binary-out register with request/acknowledge circuits and a control unit. These functional elements are fabricated with ternary NOR, NAND, INV gates and ternary-in/binary-out D-FF (D-elements). The B-ternary based asynchronous circuit has less interconnections, achives race-free operations and makes use of conventional binary powerful design tools. Particularly, we extend the speed-independent delay model to relativity delays in order to reduce hardware overhead of checking memory stability in the system. As a concrete example, a carry-completion type asynchronous adder system is demonstrated under extended speed-independent mode to show the validity of the extension.

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.