Boundary Constraints of VLSI floorplanning require a set of blocks to be placed along the boundaries of the chip. Thus, this set of blocks can be adjacent to I/O pads for external communication. Furthermore, these blocks are kept away from the central area so that they do not form blockage for internal routing. In the paper, we devise an algorithm of VLSI floorplanning with boundary constraints using a Corner Block List (CBL) representation. We identify the necessary and sufficient conditions of the CBL representation for the boundary constraints. We design a linear time approach to scan the conditions and formulate a penalty function to punish the constraint violation. A simulated annealing process is adopted to optimize the floorplan. Experiments on MCNC benchmarks show promising results.

An advanced spare-connection scheme for K-out-of-N redundancy is proposed for constructing fault-tolerant ring- or toroidal mesh-connected processing-node arrays able to enhance emulation of binary hypercubes by using bypass networks. With this scheme, a component redundancy configuration for a base array with a fixed number of primary nodes, such as that for 8-node ring or 32-node toroidal mesh, can be constructed by using bypass links with a segmented bus structure to selectively connect the primary nodes to a spare node in parallel. These bypass links are allocated to the primary nodes by graph-node coloring with a minimum inter-node distance of three in order to use the bypass links as the hypercube connections as well as to attain strong fault tolerance for reconfiguring the base array with the primary network topology. An extended redundancy configuration for a large fault-tolerant array can be constructed by connecting the component configurations by using external switches of a hub type provided at the bus nodes of the bypass links. This configuration has a network topology of the parallel star-connections of sub-hypercubes whose diameter is smaller than that of the regular hypercube.

As LSIs are two-dimensional structures, the number of external pins increases at a lower rate than the corresponding increase in the number of gates on the LSI. Therefore, the number of flip-flops on a scan path increases as the density of gates on LSIs rises, resulting in longer test application times. In this paper, three novel DFT strategies aimed at reducing test application time are proposed. DFT strategy 1 is a full scan design method with test point insertion, DFT strategy 2 is a partial scan design method, and DFT strategy 3 is a partial scan design method with test point insertion. Experimental results show that these DFT strategies reduced the test application times by 45% to 82% compared with conventional full scan design methods.

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 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.

This paper proposes the Vector Evaluated GA-ICT (VEGA-ICT), a novel design method that employs the Genetic Algorithm (GA) to obtain the optimum antenna design. GA-ICT incorporates an arbitrary wire-grid model antenna to derive the optimum solution without any basic structure or limitation on the number of elements by merely optimizing an objective function. GA-ICT comprises the GA and an analysis method, the Improved Circuit Theory (ICT), with the following characteristics. (1) To achieve optimization of an arbitrary wire-grid model antenna without a basic antenna structure, the unknowns of the ICT are directly assigned to variables of the GA in the GA-ICT. (2) To achieve a variable number of elements, duplicate elements generated by using the same feasible region are deleted in the ICT. (3) To satisfy all complex design conditions, the GA-ICT generates an objective function using a weighting function generated based on electrical characteristics, antenna configuration, and size. (4) To overcome the difficulty of convergence caused by the nonlinearity of each term in the objective function, GA-ICT adopts a vector evaluation method. In this paper, the novel GA-ICT method is applied to downsize sector antennas. The calculation region in GA-ICT is reduced by adopting cylindrical coordinates and a periodic imaging structure. The GA-ICT achieves a 30% reduction in size compared to the previously reported small sector antenna, MS-MPYA, while retaining almost the same characteristics.

A quality-of-service based link control scheme to counteract correlated channel errors for wireless multimedia communications is proposed in this paper. Both the medium access (MAC) and data link control (DLC) layers are treated. The performance of the proposed scheme is evaluated using both analysis and simulation. The delay and jitter behaviors are examined for both the constant bit rate (CBR) traffic and variable bit rate (VBR) traffic. The throughput performance is also obtained for the available bit rate (ABR) traffic. Through numerical experiments, the proposed scheme is demonstrated to be not only robust against channel impairments but also capable of providing the desired QoS for wireless multimedia communications.

The IEEE 1394 is a standard for the high performance serial bus interface. This standard has the isochronous transfer mode that is suitable for real-time applications and the asynchronous transfer mode for delay-insensitive applications. It can be used to construct a small-size local area network. We propose a queueing model for a network with this standard under some assumptions, and calculate the average waiting time of an asynchronous packet in the buffer in the steady state. We give some numerical results, along with validation by simulation, in order to evaluate its performance.

A multi-grid finite-difference time-domain (FDTD) method was applied for numerical dosimetry analysis in the human head for 5 GHz band portable terminals. By applying fine FDTD grids to the volumes in the human head where the highest electromagnetic (EM) absorption occurs and coarse grids to the remaining volumes of the head, the spatial peak specific absorption rate (SAR) assessment was achieved with a less computation memory and time. The accuracy of applying the multi-grid FDTD method to the spatial peak SAR assessment was checked in comparison with the results obtained from the usual uniform-grid method, and then the spatial peak SARs for three typical situations of a person using a 5.2 GHz band portable terminal were calculated in conjunction with an anatomically based human head model.

In this letter, we propose a grammatical structure of the finite state network (FSN) for the recognition of Korean price sentences. It is implemented by arranging the nodes and the arcs of the FSN. Two kinds of grammatical structure are presented. Both are designed according to the grammar constraints of Korean price sentences. The grammar constraints of Korean price sentences are similar to those of English price sentences; the unit is placed after the digit; several digits form a basic group; the basic group appears recursively followed by meta-units, etc. Speaker-independent recognition experiments were conducted, and the results of the FSN's with proposed grammatical structures were compared with those of the FSN without grammatical structure.

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.

This paper proposes a non-linear adaptive algorithm, the amplitude banded RLS (ABRLS) algorithm, as an adaptation procedure for time variant channel equalizers. In the ABRLS algorithm, a coefficient matrix is updated based on the amplitude level of the received sequence. To enhance the capability of tracking for the ABRLS algorithm, a parallel adaptation scheme is utilized which involves the structures of decision feedback equalizer (DFE). Computer simulations demonstrate that the novel ABRLS based equalizer provides a significant improvement relative to the conventional RLS DFE on a rapidly time variant communication channel.

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.

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.

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.

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.

We consider only P-invariants that are nonnegative integer vectors in this paper. An P-invariant of a Petri net N=(P,T,E,α,β) is a |P|-dimensional vector Y with Yt A = for the place-transition incidence matrix A of N. The support of an invariant is the set of elements having nonzero values in the vector. Since any invariant is expressed as a linear combination of minimal-support invariants (ms-invariants for short) with nonnegative rational coefficients, it is usual to try to obtain either several invariants or the set of all ms-invariants. The Fourier-Motzkin method (FM) is well-known for computing a set of invariants including all ms-invariants. It has, however, critical deficiencies such that, even if invariants exist, none of them may be computed because of memory overflow caused by storing candidate vectors for invariants and such that, even when a set of invariants are produced, many non-ms invariants may be included. We are going to propose the following two methods: (1) FM1_M2 that finds a smallest possible set of invariants including all ms-invariants; (2) STFM that necessarily produces one or more invariants if they exist. Experimental results are given to show their superiority over existing ones.

Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded (extended) free choice net is solved in deterministic polynomial time. This paper treats liveness problem of AC/DC nets. AC/DC net is a subclass of Petri net that exhibits no confusion (mixture of concurrency and conflict). This class properly includes the class of free choice nets. It is shown that every minimal siphon of an AC/DC net is trap if and only if every strongly connected siphon is a trap. This result shows that monotone liveness of bounded AC/DC net is solved in deterministic polynomial time. It is shown that this result is true of bounded time AC/DC net with static fair condition.

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.

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.