In this paper, we present a new signal frequency estimation method based on the sinusoidal additive synthesis model. In the proposed method, frequencies in both the signal and noise are estimated with several delay times by using an expanded linear prediction (LP) method, and assuming that the signal is stationary and noise is unstationary in short record length. Frequencies in the signal are extracted according to their dependence on different delays. The frequency estimation can be accomplished with short record length even in the case where the number of frequency components in the signal is unknown. And it is capable of estimating the frequencies of a signal in the presence of noise. Furthermore, the proposed method estimates the parameters with less computation and high estimation accuracy. Simulation results are provided to confirm the effectiveness of the proposed method. The comparison of estimation accuracy between the proposed method and the analysis by synthesis (ABS) method is shown with the corresponding Cramer-Rao lower bound. And the frequency resolution of this method is also shown.

Today software piracy is a major concern to electronic commerce since a digitized product such as software is vulnerable to redistribution and unauthorized use. This paper presents an enhanced electronic software distribution and software protection model. Authentication scheme of the proposed model is based on zero-knowledge (ZK) proof which requires limited computation. The proposed model considers post installation security using authentication agent. It prevents software piracy and illegal copy. It also provides secure and efficient software live-update mechanism based on traitor tracing scheme. Even if software or personal key is copied illegally, a merchant can trace back to its original owner from the electronic license and personal key. The proposed model provides security and reasonable performance and safety.

We present a simple cell scheduling algorithm for an input buffered switch. The suggested algorithm is based on iSLIP and consists of request, grant and accept steps. The pointer update scheme of iSLIP is simplified in the suggested algorithm. By virtue of the new update scheme, the performance of the suggested algorithm is better than that of iSLIP with one iteration. Using computer simulations under a uniform traffic, we show the suggested algorithm is more appropriate than iSLIP for scheduling of an input buffered switch with multiple service classes.

External pins for tests are precious hardware resources because this number is strongly restricted. Cores are tested via test access mechanisms (TAMs) such as a test bus architecture. When cores are tested via test buses which have constant bit widths, test stimuli and test responses for a particular core have to be transported over these test buses. The core might require more widths for input and output than test buses, and hence, for some part of the test, the TAMs are idle; this is a wasteful usage of the TAMs. In this paper, an optimization method of test accesses with a combined BIST and external test (CBET) scheme is proposed for eliminating the wasteful usage of test buses. This method can minimize the test time and eliminate the wasteful usage of external pins by considering the trade-off between test time and the number of external pins. Our idea consists of two parts. One is to determine the optimum groups, each of which consists of cores, to simultaneously share mechanisms for the external test. The other is to determine the optimum bandwidth of the external input and output for the external test. Our idea is basically formulated for the purpose of eliminating the wasteful external pin usage. We make the external test part to be under the full bandwidth of external pins by considering the trade-off between the test time and the number of external pins. This is achieved only with the CBET scheme because it permits test sets for both the BIST and the external test to be elastic. Taking test bus architecture as an example, a formulation for test access optimization and experimental results are shown. Experimental results reveal that our optimization can achieve a 51.9% reduction in the test time of conventional test scheduling and our proposals are confirmed to be effective in reducing the test time of system-on-a-chip.

A workflow is a flow of work carried out by workers, and workflow management is to automate the flow of work. In workflow management, an actual work is carried out based on the workflow, which is called case. In order to effectively meet various requirements, it is necessary to change current workflow dynamically, which is called dynamic workflow change. When the dynamic change is required, there exist cases in the workflow. In order to handle these cases and further to keep the queuing order, the dynamic change takes period of time (called transient time) until the changed workflow becomes steady state again. During the transient time, workers are forced to do irregular work, and therefore it is important to clarify if a change type takes shorter transient time. In this paper, we do the performance evaluation on transient time of dynamic workflow changes. To do so, we first give a definition of transient time, and then propose methods of computing transient time of three change types proposed by Ellis et al. Finally, we do the performance evaluation for 90 dynamic changes by computing the transient times.

The legal firing sequence problem of Petri nets (LFS) is one of fundamental problems in the analysis of Petri nets, because it appears as a subproblem of various basic problems. Since LFS is shown to be NP-hard, various heuristics has been proposed to solve the problem of practical size in a reasonable time. In this paper, we propose a new algorithm for this problem. It is based on the partial order verification technique, and reduces redundant branches in the search tree. Moreover, the proposed algorithm can be combined with various types of heuristics.

This paper describes a design scheme of generalized minimum variance controllers (GMVC) using a group method of data handling (GMDH) network for nonlinear systems. Concretely, the predictive value of the output required in the GMVC is obtained by using the GMDH which is a kind of multilayered networks. Since the predictive value of the output in GMVC is calculated by a nonlinear model which is generated by the GMDH network, one can expect to obtain the better control performance than that by the conventional scheme. The behavior of the newly proposed control scheme is evaluated on numerical examples.

Topological sorting is, given with a directed acyclic graph G=(V,E), to find a total ordering of the vertices such that if (u,v)E then u is ordered before v. Instead of topological sorting, we are interested in how many total orderings exist in a given directed acyclic graph. We call such a total ordering as legal sequence and the problem of finding total number of legal sequences as legal sequence number problem. In this paper, we firstly give necessary definitions and known results obtained in our previous research. Then we give a method how to obtain legal sequence number for a class of directed acyclic graphs, extended 2-b-SPGs. Finally we discuss the complexity of legal sequence number problem for extended 2-b-SPGs.

Spatiotemporal chaos in a multidomain regime in a Gunn-effect device is numerically investigated as an example of collective domain oscillations under global constraints. The dynamics of carrier densities are computed using a set of model partial differential equations. Numerical results reveal some distinctive and chaotic clustering features caused by the global coupling and boundary effects. The chaotic regime is then characterized in terms of a Lyapunov spectrum and Lyapunov dimension, the latter increasing with the size of the system.

Agent technology is widely recognized as a new paradigm for the design of concurrent software and systems. The aim of this paper is to give a mathematical foundation for the design and the analysis of multi-agent systems by means of a Petri-net-based model. The proposed model, called PN2, is based on place/transition nets (P/T nets), which is one of the simplest classes of Petri nets. The main difference of PN2's from P/T nets is that each token, representing an agent, is also a P/T net. PN2's are sufficiently simple for the mathematical analysis, such as invariant analysis, but have enough modeling power.

In this paper, we propose a unified high-radix division algorithm for high-speed signal and data processing applications, and present the design and evaluation of high-radix parallel dividers based on the proposed algorithm. By prescaling the input operands and converting some significant digits of a partial remainder into non-redundant representation, the quotient digit can be obtained directly from the partial remainder without using quotient digit selection tables. Performance evaluation shows that the proposed radix-4 and radix-8 divider architectures achieve faster computation with the same level of hardware complexity than the binary counterparts. We also show an experimental fabrication of a radix-4 divider chip in 0.35 µm CMOS technology.

This paper presents a new framework for synthesizing look-up table (LUT) networks. Some of the existing LUT network synthesis methods are based on one or two functional (Boolean) decompositions. Our method also uses functional decompositions, but we try to use various decomposition methods, which include algebraic decompositions. Therefore, this method can be thought of as a general framework for synthesizing LUT networks by integrating various decomposition methods. We use a cost database file which is a unique characteristic in our method. We also present comparisons between our method and some well-known LUT network synthesis methods, and evaluate the final results after placement and routing. Although our method is rather heuristic in nature, the experimental results are encouraging.

This letter proposes a hardware/software partitioning algorithm for digital signal processor cores with two register files. Given a compiled assembly code and a timing constraint of execution time, the proposed algorithm generates a processor core configuration with a new assembly code running on the generated processor core. The proposed algorithm considers two register files and determines the number of registers in each of register files. Moreover the algorithm considers two or more types of functional units for each arithmetic or logical operation and assigns functional units with small area to a processor core without causing performance penalty. A generated processor core will have small area compared with processor cores which have a single register file or those which consider only one type of functional units for each operation. The experimental results demonstrate the effectiveness and efficiency of the proposed algorithm.

Layout design for analog circuits has historically been a time consuming, error-prone, manual task. Its complexity results not so much from the number of devices, as from the complex interactions among devices or with the operating environment, and also from continuous-valued performance specifications. This paper addresses the problem of device-level placement for analog layout in a non-traditional way. Different from the classic approaches--exploring a huge search space with a combinatorial optimization technique, where the cells are represented by means of absolute coordinates, being allowed to illegally overlap during their moves in the chip plane--this paper advocates the use of non-slicing topological representations, like (symmetric-feasible) sequence-pairs, ordered- and binary- trees. Extensive tests, processing industrial analog designs, have shown that using skillfully the symmetry constraints (very typical to analog circuits) to remodel the solution space of the encoding systems, the topological representation techniques can achieve a better computation speed than the traditional approaches, while obtaining a similar high quality of the designs.

An automated analog circuit synthesis based on reuse of topological features of 'prototype circuits' is proposed. The prototype circuits are designed by humans and suggested to the synthesis system as hints of configurations of new analog circuits to be synthesized by the system. The connections of elements in analog circuits are not generally systematic, but they would have some similarities to a circuit which has similar behaviors or functionalities. In the proposed process, the information on circuit connections is stored as sub-circuits extracted from the prototype circuits. And then, genetic algorithm is used to search for an optimum combination of the sub-circuits that achieves the desired electronic specifications. The combinations of sub-circuits are performed with a novel technique where the terminals of the sub-circuits are shared. The capabilities of the proposed method are demonstrated through an example of the synthesis.

We propose a transistor sizing method that downsizes MOSFETs inside a cell to eliminate redundancy of cell-based circuits as much as possible. Our method reduces power dissipation of detail-routed circuits while preserving interconnects. The effectiveness of our method is experimentally evaluated using 3 circuits. The power dissipation is reduced by 75% maximum and 60% on average without delay increase. Compared with discrete cell sizing, the proposed method reduces power dissipation furthermore by 30% on average.

In this paper, we present a new algorithm for statistical static timing analysis of a CMOS combinatorial circuit, which takes correlations into account to improve accuracy of the distribution of the maximum delay of the circuit. The correlations treated in the algorithm are not only the one between distributions of arrival times of input signals to a logic gate but also correlation between switching delays of a logic gate and correlation between interconnect delays of a net. We model each delay by a normal distribution, and use a normal distribution of two stochastic variables with a coefficient of correlation for computing the maximum of two delays. Since the algorithm takes the correlation into account, the time complexity is O(m2) in the worst-case, where m is the number of edges of the graph representing a given circuit. But, for real combinatorial circuits, the complexity is expected to be less than this.

In this paper we present two contributions for a set of local transformations (a selection set) to improve a performance of a very large circuit. The first contribution is an idea of "padding node" and "multi-separator-set. " We have proven that combination of padding node and multi-separator-set provides the optimum selection set. The second contribution is our heuristic method to find a semi-optimum multi-separator-set, which uses a network flow algorithm. Our method is robust for very large circuits, because its memory usage and calculation time are linear and polynomial order with the size of the circuit. We have compared our method with Singh's selection function method, which provides the optimum selection set and is the best method in literature to date. Our method has successfully optimized delays of all circuits, while Singh's selection function method has aborted with three large circuits because of memory overflow. The results also has shown our method has a comparable capability in delay optimization to Singh's method, although our method is heuristic.

In this paper, we propose a new clock tree synthesis method for semi-synchronous circuits. A clock tree obtained by the proposed method is a multi-level multi-way clock tree such that a clock-input timing of each register is a multiple of a predefined unit delay and the wire length from a clock buffer to an element driven by it is bounded. The clock trees are constructed for several practical circuits. The size of constructed clock tree is comparable to a zero skew clock tree. In order to assure the practical quality of the clock trees, they are examined under the five delay conditions, which cover various environmental and manufacturing conditions. As a result, they are proved stable under each condition and improve the clock speed up to 17.3% against the zero skew clock trees.

Reversible variable length codes (RVLCs), which make instantaneous decoding possible in both forward and backward directions, are exploited to code data stream in noisy enviroments. Because there is no redundancy in code words of RVLCs, RVLCs are suitable for very low bit-rate video coding. Golomb-Rice code, one of variable length code for infinite number of symbols, is widely used to encode exponentially distributed non-negative integers. We propose a reversible variable length code by modifying Golomb-Rice code, which is called parity check reversible Golomb-Rice code and abbreviated to P-RGR code. P-RGR code has the same code length distribution as GR code but can detect one-bit error in any arbitrary position of the code stream. The sets of P-RGR code words in both directions are identical so that they can be constructed by nearly the same algorithm. Furthermore, this paper also gives a general construction method for all instantaneously decodable RGR codes.