This paper provides algorithms in order to solve an interval implicit function of the Poincare map generated by a continuous piece-wise linear (CPWL) vector field, with the use of interval arithmetic. The algorithms are implemented with the use of MATLAB and INTLAB. We present an application to verification of canards in two-dimensional CPWL vector field appearing in nonlinear piecewise linear circuits frequently, and confirm that the algorithms are effective.

Programmable Logic Controller (PLC) has been widely used in the industrial control. Inherently, the PLC-based system is a class of Hybrid Dynamical System (HDS) in which continuous state of the plant is controlled by the discrete logic-based controller. This paper firstly presents the formal algebraic model of the PLC-based control systems which enable the designer to formulate the various kinds of optimization problem. Secondly, the optimization problem of the 'sensor parameters,' such as the location of the limit switch in the material handling system, the threshold temperature of the thermostat in the temperature control system, is addressed. Finally, we formulate this problem as Mixed Logical Dynamical Systems (MLDS) form which enables us to optimize the sensor parameters by applying the Mixed Integer Programming.

Path following circuits (PFC's) are circuits for solving nonlinear problems on the circuit simulator SPICE. In the method of PFC's, formulas of numerical methods are described by circuits, which are solved by SPICE. Using PFC's, numerical analysis without programming is possible, and various techniques implemented in SPICE will make the numerical analysis very efficient. In this paper, we apply the PFC's of the homotopy method to various nonlinear problems (excluding circuit analysis) where the homotopy method is proven to be globally convergent; namely, we apply the method to fixed-point problems, linear programming problems, and nonlinear programming problems. This approach may give a new possibility to the fields of applied mathematics and operations research. Moreover, this approach makes SPICE applicable to a broader class of scientific problems.

In this paper, rail-to-rail OTA utilizing linear V-I conversion circuit whose input stage is composed of single channel MOSFETs, is proposed. The proposed conversion circuit is realized with two circuit blocks. One of them consists of a single MOSFET operating in plural regions and the other a pair of MOSFETs in saturation region and cut-off region. Combination of the circuit blocks achieves a linear voltage-current conversion for a rail-to-rail input signal. Rail-to-rail OTA is proposed using the proposed conversion circuit. HSPICE simulations are performed to verify the validity of the proposed V-I converter and rail-to-rail OTA. Simulation results indicate good performances. As an application example, 2nd-order LPF is realized using the proposed OTAs.

A novel unified phase compiler framework for embedded VLIWs and DSPs is shown. In this compiler, a given program is represented in 3-D representation space, which enables quantitatively estimating required resources and elapsed time. Transformation of a 3-D representation graph that corresponds to a code optimization method for a specific processor architecture is also proposed. The proposal compiler and the code optimization methods are compared with an ordinary compiler in terms of their generated codes. The results demonstrate their effectiveness.

A memory address allocation method for digital signal processors of indirect addressing with indexed auto-modification is proposed. At first, address auto-modification amounts for a given program are analyzed. And then, address allocation of program variables are moved and shifted so that both indexed and simple auto-modifications are effectively exploited. For further reduction in overhead codes, a memory address allocation method coupled with computational reordering is proposed. The proposed methods are applied to the existing compiler, and generated codes prove their effectiveness.

A noise reduction technique that uses the linear prediction to remove noise components in speech signals has been proposed previously. The noise reduction works well for additive white noise signals, because the coefficients of the linear predictor converge such that the prediction error becomes white. In this method, the linear predictor is updated by a gradient-based algorithm with a fixed step-size. However, the optimal value of the step-size changes with the values of the prediction coefficients. In this paper, we propose a noise reduction system using the linear predictor with a variable step-size. The optimal value of the step-size depends also on the variance of the white noise, however the variance is unknown. We therefore introduce a speech/non-speech detector, and estimate the variance in non-speech segments where the observed signal includes only noise components. The simulation results show that the noise reduction capability of the proposed system is better than that of the conventional one with a fixed step-size.

As the transistor feature sizes and threshold voltages reduce, leakage energy consumption has become an inevitable issue for high-performance microprocessor designs. Since on-chip caches are major contributors of the leakage, a number of researchers have proposed efficient leakage reduction techniques. However, it is still not clear that 1) what kind of algorithm can be considered and 2) how much they have impact on energy and performance. To answer these questions, we explore run-time cache management algorithm, and evaluate the energy-performance efficiency for several alternatives.

We propose a novel approach for designing a low power datapath in wireless communication systems. Especially, we focus on the digital FIR filter. Our proposed approach can reduce the power consumption and the circuit area of the digital FIR filter by optimizing the bitwidth of the each filter coefficient with keeping the filter calculation accuracy. At first, we formulate the constraints about keeping accuracy of the filter calculations. We define the problem to find the optimized bitwidth of each filter coefficient. Our defined problem can be solved by using the commercial optimization tool. We evaluate the effects of consuming power reduction by comparing the digital FIR filters designed in the same bitwidth of all coefficients. We confirm that our approach is effective for a low power digital FIR filter.

A b-bit SIMD functional unit has n k-bit sub-functional units in itself, where b = k n. It can execute n-parallel k-bit operations. However, all the b-bit functional units in a processor core do not necessarily execute n-parallel operations. Depending on an application program, some of them just execute n/2-parallel operations or even n/4-parallel operations. This means that we can modify a b-bit SIMD functional unit so that it has n/2 k-bit sub-functional units or n/4 k-bit sub-functional units. The number of k-bit sub-functional units in a SIMD functional unit is called sub-operation parallelism. We incorporate a sub-operation parallelism optimization algorithm into SIMD functional unit optimization. Our proposed algorithm gradually reduces sub-operation parallelism of a SIMD functional unit while the timing constraint of execution time satisfied. Thereby, we can finally find a processor core with small area under the given timing constraint. We expect that we can obtain processor core configurations of smaller area in the same timing constraint rather than a conventional system. The promising experimental results are also shown.

This paper discusses performance limitation of on-chip interconnects. On-chip global interconnects are considered to be a bottleneck of high-performance LSIs. To overcome this issue, high-speed signaling and large throughput interconnection using electrical wires have been studied. However the limitation of on-chip interconnects has not been examined sufficiently. This paper reveals the maximum performance of on-chip global interconnects based on derived analytic expressions and detailed circuit simulation. We derive trade-off curves among bit rate, interconnect length, and eye opening both for single-end and for differential signaling. The results show that differential signaling improves signaling performance several times compared with conventional single-end signaling, and demonstrate that 80 Gbps differential signaling on 10 mm interconnects is promising.

Under the assumption that clock can be inputted to each register at an arbitrary timing, the minimum feasible clock period can be determined if delays between registers are given. This minimum feasible clock period might be reduced if delays between some registers are increased by delay insertion. In this paper, we propose a delay insertion algorithm to reduce the minimum clock period. First, the proposed algorithm determines a clock schedule ignoring some constraints. Second, the algorithm inserts delays to recover ignored constraints according to the delay-slack and delay-demand of the obtained clock schedule. We show that the proposed algorithm achieves the minimum clock period by delay insertion if the delay of each element in the circuit is unique. Experiments show that the amount of inserting delay and computational time are smaller than the conventional algorithm.

VLSI architecture of IEEE802.11i cipher algorithms is devised dedicatedly for embedded implementation of IEEE802.11a/g wireless communication systems. The proposed architecture consists mainly of RC4 unit for WEP/TKIP and AES unit. The RC4 unit successfully adopts packed memory accessing architecture. As for the AES unit, overlapped pipeline scheme of CBC-MAC and Counter-Mode is exploited in order to conceal processing latency. The cipher core has been implemented with 18 Kgates in 0.18 µm CMOS technology, which achieves the maximum transmission rate of IEEE802.11a/g at 60 MHz clock frequency while consuming 14.5 mW of power.

This paper presents an approach of logic mapping into LUT-Array-Based PLD where Boolean functions in the form of the sum of generalized complex terms (SGCTs) can be mapped directly. While previous mapping approach requires predetermined variable ordering, our approach performs mapping and variable reordering simultaneously. For the purpose, we propose a directed acyclic graph based on the multiple-valued decision diagram (MDD) and an algorithm to construct the graph. Our algorithm generates candidates of SGCT expressions for each node in a bottom-up manner and selects the variables in the current level by evaluating the sizes of SGCT expressions directly. Experimental results show that our approach reduces the number of terms maximum to 71 percent for the MCNC benchmark circuits.

This paper describes a formal verification for a shared-memory-style communication system. We first describe two versions (i.e. abstract and concrete) of the communication system based on an I/O-automaton, which is a formal system for distributed algorithms. Then, we prove the concrete version can perform all the external operations of the abstract version. This result, together with a former result, leads to the equivalence of the two versions. The proof is done by Larch theorem prover, and is the ever largest case study using I/O-automata.

This paper proposes an iterative parallel genetic algorithm with biased initial population to solve large-scale combinatorial optimization problems. The proposed scheme employs a master-slave collaboration in which the master node manages searched space of slave nodes and assigns seeds to generate initial population to slaves for their restarting of evolution process. Our approach allows us as widely as possible to search by all the slave nodes in the beginning period of the searching and then focused searching by multiple slaves on a certain spaces that seems to include good quality solutions. Computer experiment shows the effectiveness of our proposed scheme.

In this paper we give a simple algorithm to generate all partitions of {1,2,,n} into k non-empty subsets. The number of such partitions is known as the Stirling number of the second kind. The algorithm generates each partition in constant time without repetition. By choosing k = 1,2,,n we can also generate all partitions of {1,2,,n} into subsets. The number of such partitions is known as the Bell number.

This paper proves that for every positive integers n,k and any positive number ε, we can explicitly construct a DAG G with n+O(k^1+ε) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n,k and any positive number ε, we can explicitly construct a graph H with n+O(k^2+ε) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.

Hypersequential programming is a new method of concurrent-program development in which the original concurrent program is first serialized, then tested and debugged as a set of sequential programs (scenarios), and finally restored into the target concurrent program by parallelization. Both high productivity and reliability are achieved by hypersequential programming because testing and debugging are done for the serialized versions and the correctness of the serialized programs is preserved during the subsequent parallelization. This paper proposes scenario-based hypersequential programming for reactive multitasking systems that have not only concurrency and nondeterminacy, but also interruption and priority. Petri nets with priority are used to model reactive systems featuring interruption and priority-based scheduling. How reactive systems are made highly reliable by this approach is explained and the effectiveness of the approach is demonstrated through the example of a telephone terminal control program.

One of the remaining issues of Mobile IP is a mobile host (MH) needs to update its location each time it moves from one subnet to another, even when it is in dormant mode while roaming. This practice is apparently not efficient in terms of location update cost and power consumption. Recent research works have attempted to address that problem by extending Mobile IP with a layer 3 paging mechanism so-called IP paging. Particularly, IP Individual Paging schemes, which are customized to each MH, have attracted considerable interest of researchers. The employment of adaptability in some manner to MH parameters in order to enhance the efficiency of IP paging schemes is probably a promising approach. In this paper, we present an analysis on the effects of both host-adaptability and time-adaptability to MH parameters in Individual Paging schemes by comparing the signaling cost of an adaptive Individual Paging scheme to that of a non-adaptive counterpart. From our analysis, specifying the optimal paging area (PA) is critical in saving signaling cost of IP paging. Thus, our investigation is focused on the adaptability of PA to maintain its optimality.

The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V,E) and an upper bound a(v;G) Z⁺{} on vertex-degree increase for each v V, find a smallest set E′ of edges such that (V,E E′) has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each v V by the addition of E′ to G is at most a(v;G), where Z⁺ is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(|V|+|E|) time.

A siphon-trap(ST) of a Petri net N = (P,T,E,α,β) is defined as a set S of places such that, for any transition t, there is an edge from t to a place of S if and only if there is an edge from a place of S to t. A P-invariant is a |P|-dimensional vector Y with Y^tA = for the place-transition incidence matrix A of N. The Fourier-Motzkin method is well-known for computing all such invariants. This method, however, has a critical deficiency such that, even if a given Perti net N has any invariant, it is likely that no invariants are output because of memory overflow in storing intermediary vectors as candidates for invariants. In this paper, we propose an algorithm STFM_N for computing minimal-support nonnegative integer invariants: it tries to decrease the number of such candidate vectors in order to overcome this deficiency, by restricting computation of invariants to siphon-traps. It is shown, through experimental results, that STFM_N has high possibility of finding, if any, more minimal-support nonnegative integer invariants than any existing algorithm.

In this paper, an adaptive microphone array system with a two-stage adaptation mode controller (AMC) is proposed for high-quality speech acquisition in real environments. The proposed system includes an adaptive array algorithm, a time-delay estimator and a newly proposed AMC. To ensure proper adaptation of the adaptive array algorithm, the proposed AMC uses not only temporal information, but also spatial information. The proposed AMC is constructed with two processing stages: an initialization stage and a running stage. In the initialization stage, a sound source localization technique is adopted, and a signal correlation characteristic is used in the running stage. For the adaptive array algorithm, a generalized sidelobe canceller with an adaptive blocking matrix is used. The proposed algorithm is implemented as a real-time man-machine interface module of a home-agent robot. Simulation results show 13 dB SINR improvement with the speaker sitting 2 m distance from the home-agent robot. The speech recognition rate is also enhanced by 32% when compared to the single channel acquisition system.

This paper addresses the estimation of time delay between two spatially separated noisy signals by system identification modeling with the input and output corrupted by additive white Gaussian noise. The proposed method is based on a modified adaptive Butler-Cantoni equalizer that decouples noise variance estimation from channel estimation. The bias in time delay estimates that is induced by input noise is reduced by an IIR whitening filter whose coefficients are found by the Burg algorithm. For step time-variant delays, a dual mode operation scheme is adopted in which we define a normal operating (tracking) mode and an interrupt operating (optimization) mode. In the tracking mode, only a few coefficients of the impulse response vector are monitored through L₁-normed finite forward differences tracking, while in the optimization mode, the time delay optimized. Simulation results confirm the superiority of the proposed approach at low signal-to-noise ratios.

This paper discusses the least-squares linear filtering and fixed-lag smoothing problems of discrete-time signals from uncertain observations when the random interruptions in the observation process are modelled by a sequence of not necessarily independent Bernoulli variables. It is assumed that the observations are perturbed by white noise and the autocovariance function of the signal is factorizable. Using an innovation approach we obtain the filtering and fixed-lag smoothing recursive algorithms, which do not require the knowledge of the state-space model generating the signal. Besides the observed values, they use only the matrix functions defining the factorizable autocovariance function of the signal, the noise autocovariance function, the marginal probabilities and the (2,2)-element of the conditional probability matrices of the Bernoulli variables. The algorithms are applied to estimate a scalar signal which may be transmitted through one of two channels.

A new Successive-Approximation ADC (Analog-to-Digital Converter) was designed which not only consumes little power, but also requires a small chip area. To achieve those goals, both comparator and internal DAC (Digital-to-Analog Converter) have been improved. The ADC was designed in a 1.2 µm CMOS double-poly double-metal n-well process. It performs 10-bit conversion with 67 dB SFDR. Power consumption and die area are 0.6 mW and 0.95 mm², respectively. ADC was extensively simulated using Hspice to verify the desired performance.

This study proposes a novel adaptive fuzzy control methodology to remove disadvantages of traditional fuzzy approximation based control. Meanwhile, the highly uncertain robot manipulator is taken as an application with either guaranteed robust tracking performances or asymptotic stability in a global sense. First, the design concept, namely, feedforward fuzzy approximation based control, is introduced for a simple uncertain system. Here the desired commands are utilized as the inputs of the Takagi-Sugeno (T-S) fuzzy system to closely compensate the unknown feedforward term required during steady state. Different to traditional works, the assumption on bounded fuzzy approximation error is not needed, while this scheme allows easier implementation architecture. Next, the concept is extended to controlling manipulators and achieves global robust tracking performances. Note that a linear matrix inequality (LMI) technique is applied and provides an easier gain design. Finally, numerical simulations are carried out on a two-link robot to illustrate the expected performances.

In this paper two algorithms for the synthesis and minimization of a CA (cellular array architecture) are proposed. Starting from a completely specified single-output switching function, our methods produce rectangularly shaped arrays of cells, interconnected in chains, with an effort to minimize the number of the produced chains (cascades). This kind of cellular topology is known throughout the bibliography as Maitra cellular arrays. The significance of those algorithms is underlined by the fact that this particular type of cellular architecture can be mapped to reversible circuits and gates (generalized Toffoli gates), which are the type of logic used in quantum circuits. The proposed methodologies include use of ETDDs (EXOR ternary decision diagrams), and switching function decompositions (including new types of boolean expansions).

A diagnosis technique is presented to locate at least one fault in a scan chain with multiple timing faults. This diagnosis technique applies Single Excitation (SE) patterns of which only one bit can be flipped even in the presence of multiple faults. By applying the SE patterns, the problem of simulations with unknown values is eliminated. The diagnosis result is therefore deterministic, not probabilistic. Experiments on the ISCAS benchmark circuits show that the average diagnosis resolution is less than ten scan cells.

This paper presents a new asynchronous FIFO design to reduce forward latency in a linear structure. The operation mode for each cell can be reconfigured dynamically as either of the two schemes, wave pipelining or handshaking, according to the data flow in the FIFO. The adoption of wave pipelining to the conventional self-timed FIFO can reduce the overhead of the handshaking as well as latching control in each stage. Initial pre-layout simulations indicate about two times of improvement on latency performance over a state-of-art asynchronous FIFO, while retaining its throughput.

In this paper, we present the condition for the effective wire addition in Look-Up-Table-based (LUT-based) field programmable gate array (FPGA) circuits, and an optimization procedure utilizing the effective wire addition. Each wire has different characteristics, such as delay and power dissipation. Therefore, the replacement of one critical wire for the circuit performance with many non-critical ones, i.e., many-addition-for-one-removal (m-for-1) is sufficiently useful. However, the conventional logic optimization methods based on sets of pairs of functions to be distinguished (SPFDs) for LUT-based FPGA circuits do not make use of the m-for-1 manipulation, and perform only simple replacement and removal, i.e., the one-addition-for-one-removal (1-for-1) manipulation and the no-addition-for-one-removal (0-for-1) manipulation, respectively. Since each LUT can realize an arbitrary internal function with respect to a specified number of input variables, there is no sufficient condition at the logic design level for simple wire addition. Moreover, in general, simple addition of a wire has no effects for removal of another wire, and it is important to derive the condition for non-simple and effective wire addition. We found the SPFD-based condition that wire addition is likely to make another wire redundant or replaceable, and developed an optimization procedure utilizing this effective wire addition. According to the experimental results, when we focused on the delay reduction of LUT-based FPGA circuits, our method reduced the delay by 24.2% from the initial circuits, while the conventional SPFD-based logic optimization and the enhanced global rewiring reduced it by 14.2% and 18.0%, respectively. Thus, our method presented in this paper is sufficiently practical, and is expected to improve the circuit performance.

In this paper, we present a model for evaluating the effectiveness of (2, 1, m) convolutional-code-based packet-level FEC, under the condition of a limited buffer size in which the number of available packets is restricted for recovery. We analytically derive the post-reconstruction receiving rate, i.e., the probability that a lost packet is received or recovered before the buffer limit is reached. We show numerical examples of the analytical results and demonstrate that the buffer size at the same level as m gives sufficient recovery performance.

We propose a new type of revocation scheme for efficient public-key black-box traitor tracing. Our revocation scheme is flexible and efficient in the sense that (i) any number of subscribers can be revoked in each distribution under an assumption that the number of revoked subscribers who collude in one coalition is limited to a threshold and (ii) both each subscriber's storage and the transmission overhead are independent of n, while (i) the maximum number of revoked ones cannot be changed or (ii) they depend on n in previous schemes, where n is the total number of subscribers. The flexibility in revocation is significant since flexible revocation can be integrated with efficient black-box tracing and this integration can be achieved without a substantial increase in the transmission overhead over the previous schemes. In this paper, we present a concrete construction of an efficient public-key black-box traceable and revocable scheme by combining flexible revocation with a known black-box tracing algorithm which works under the same attack model as assumed in the previous schemes. Our scheme achieves that (i) the transmission overhead remains efficient, especially linear only in k in case of bulk revocation and (ii) the tracing algorithm runs in O(log n) time, while the previous ones cannot satisfy both of these properties, where k is the maximum number of traitors in a coalition.

We propose source coding algorithms that use the randomness of a past sequence. The proposed algorithms solve the problems of multi-terminal source coding, rate-distortion source coding, and source coding with partial side information at the decoder. We analyze the encoding rate and the decoding error rate in terms of almost-sure convergence.

A novel CMOS LC oscillator architecture combining an LC tuned oscillator and a ring structure is presented as a new design topology to deliver improved phase noise for multiphase applications. The relative enhancement in the phase noise is estimated using a linear noise modeling approach. A three-stage LC-ring oscillator fabricated in a 0.6 mm CMOS technology achieves measured phase noise of -132 dBc/Hz at 600 kHz offset from a 900 MHz carrier and dissipates 20 mW with a 2.5 V power supply.

This note considers a problem of minimum length scheduling for a set of messages subject to precedence constraints for switching and communication networks, and shows some improvements upon previous results on the problem.

In this paper, we analyse the signcryption scheme proposed by Libert and Quisquater in 2004 and show that their scheme does not meet the requirements as claimed in their paper in PKC'2004, such as, semantically secure against adaptive chosen ciphtertext attack, ciphertext anonymity and key invisibility.

In this letter, we introduce the concept of k-error lattice structure to describe the stability of lattice structure for pseudorandom number sequences, give some of its properties, and make a study of the relationship between the k-error lattice structure and the k-error linear complexity. These properties and the relationship create an elementary framework to study the stability of the lattice structure of pseudorandom number sequences.