In this paper, we introduce a Shared Multiple Rooted XOR-based Decomposition Diagram (XORDD) to represent functions with multiple outputs. Based on the XORDD representation, we develop a synthesis algorithm for general Exclusive Sum-of-Product forms (ESOP). By iteratively applying transformations and reductions, we obtain a compact XORDD which gives a minimized ESOP. Our method can synthesize larger circuits than previously possible. The compact ESOP representation provides a form that is easier to synthesize for XOR heavy multi-level circuits, such as arithmetic functions. We have applied our synthesis techniques to a large set of benchmark circuits in both PLA and combinational formats. Results of the minimized ESOP forms obtained from our synthesis algorithm are also compared to the SOP forms generated by ESPRESSO. Among the 74 circuits we have experimented with, the minimized ESOP's have fewer product terms than those of SOP's in 39 circuits.

We present here the Controlling Value Boolean Matching based on fault analysis. The problem is to match a Boolean function with don't cares on library cells under arbitrary input permutations and/or input-output phase assignments. Most of the library cells can be represented by tree structure circuits. The approach presented here is suitable for these structures and computes the Boolean matching better than the structural matching used in SIS. It can handle library cells with a general topology and reconvergent paths. The benchmark test shows that the Controlling Value Boolean Matching can be as facter as the structural matching used in SIS.

The analysis of an architecture may provide statistic information on the use of the resources and on the execution time. Some of these information need just a static analysis. Others, such as the execution time, may need dynamic analysis. Moreover as the computation time of behavioral descriptions (control step time unit) and RTL ones (cycle based) may differ a lot, unexpected architectures may be generated by behavioral synthesis. Therefore means to debug the results of behavioral synthesis are required. This paper introduces a new approach to integrate an interactive simulator within a behavioral synthesis tool, thereby allowing concurrent synthesis and simulation. The simulator and the behavioral synthesis are based on the same model. This model allows to link the behavioral description and the architecture produced by synthesis. This paper also discusses an implementation of this concept resulting in a simulator, called AMIS. This tool assists the designer for understanding the results of behavioral synthesis and for architecture exploration. It may also be used to debug the behavioral specification.

In this paper, we propose an efficient solution for the Multiple Constant Multiplication (MCM) problem. The method uses hierarchical clustering to exploit common subexpressions among constants and reduces the number of shifts, additions, and subtractions. The algorithm defines appropriate weights, which indicate operation priority, and selects common subexpressions, resulting in a minimum number of local operations. It can also be extended to various high-level synthesis tasks such as arbitrary linear transforms. Experimental results for several error-correcting codes, digital filters and Discrete Cosine Transforms (DCTs) have shown the effectiveness of our method.

Minato has proposed canonical representation for polynomial functions using zero-suppressed binary decision diagrams (ZBDDs). In this paper, we extend binary moment diagrams (BMDs) proposed by Bryant and Chen to handle variables with degrees higher than l. The experimental results show that this approach is much more efficient than the previous ZBDDs' approach. The proposed approach is expected to be useful for various problems, in particular, for computer algebra.

This paper proposes "path mapping," a method of delay estimation for technology independent combinational circuits. Path mapping provides fast and accurate delay estimation using common ideas with the tree covering based technology mapping. First, path mapping does technology mapping for all paths in the circuit with minimum mapped delay. Then, it finds the largest mapped delay among all the paths in the circuit, and answers it as an estimated circuit delay. Experimental results show path mapping estimates more accurate circuit delay than unit delay, and runs much faster than the technology mapping.

We propose a propagation delay model for SRAM-based FPGAs. It is a simplified Elmore delay model with a linear fan-out function. Therefore, the computational complexity is small. In order to ensure calculation accuracy, the model parameters are extracted from real layout data. The average model error is 4% compared to actual delays. The model is applicable for delay estimation in a router and as a tool for static calculation of critical path delay.

In layout design of transport-processing FPGAs, it is required that not only routing congestion is kept small but also circuits implemented on them operate with higher operation frequency. This paper extends the proposed simultaneous placement and global routing algorithm for transport-processing FPGAs whose objective is to minimize routing congestion and proposes a new algorithm in which the length of each critical signal path (path length) is limited within a specified upper bound imposed on it (path length constraint). The algorithm is based on hierarchical bipartitioning of layout regions and LUT (Look Up Table) sets to be placed. In each bipartitioning, the algorithm first searches the paths with tighter path length constraints by estimating their path lengths. Second the algorithm proceeds the bipartitioning so that the path lengths of critical paths can be reduced. The algorithm is applied to transport-processing circuits and compared with conventional approaches. The results demonstrate that the algorithm satisfies the path length constraints for 11 out of 13 circuits, though it increases routing congestion by an average of 20%. After detailed routing, it achieves 100% routing for all the circuits and decreases a circuit delay by an average of 23%.

The FPGA logic synthesis consists of logic minimization step and technology mapping step. These two steps are usually performed separately to reduce the complexity of the problem. Conventional logic minimization methods try to minimize the number of literals of a given Boolean network, while FPGA technology mapping techniques attempt to minimize the number of basic blocks. However, minimizing the number of literals, which is target architecture-independent feature, does not always lead to minimization of basic block count, which is a FPGA architecture specific feature. Therefore, most of the existing technology mapping systems take into account reorganization of its input circuits to get better mapping results. Such a loosely coupled logic synthesis paradigm may cause difficulties in finding the optimal solution. In this paper, we propose a new logic synthesis approach where logic minimization and technology mapping steps are performed tightly coupled. Our system takes into account FPGA specific features in logic minimization step and thus our technology mapping step does not need to resynthesize the Boolean network. We formulate the technology mapping problem as a graph covering problem. Such formulation provides more global view to optimality and supports versatile cost functions. in addition, a fast and exact library management technique is devised for efficient FPGA cell matching which is one of the most frequently used operations in the FPGA logic synthesis.

Field Programmable Gate Arrays (FPGA's) are important devices for rapid system prototyping. Roth-Karp decomposition is one of the most popular decomposition techniques for Look-Up Table (LUT) -based FPGA technology mapping. In this paper, we propose a novel algorithm based on Binary Decision Diagrams (BDD's) for selecting good lambda set variables in Roth-Karp decomposition to minimize the number of consumed configurable logic blocks (CLB's) in FPGA's. The experimental results on a set of benchmarks show that our algorithm can produce much better results than the similar works of the previous approaches.

In this paper, an efficient approach to the synthesis of CA (Cellular Architecture) -type FPGAs is presented. To exploit the array structure of cells in CA-type FPGAs, logic expressions called Maitra terms which can be mapped directly to the cell arrays are generated by using ETDDs (EXOR Ternary Decision Diagrams). Since a traversal of the ETDD is sufficient to generate a Maitra term which takes O (n) steps where n is the number of nodes in the ETDD, Maitra terms are generated very efficiently. The experiments show that the proposed method generates better results than existing methods.

This paper proposes a new approach that makes it possible for every undergraduate student to perform experiments of developing a <>Ipipelined RISC processor within limited time available for the course. The approach consists of 4 steps. At the first step, every student implements by himself/herself a pipelined RISC processor which is based on a given, very simple model; it has separate buses for instruction and data memory ("Harvard architecture") to avoid structural hazard, while it completely ignores data control hazards to make implementation easy. Although it is such a "defective" processor, we can test its functionality by giving object code containing sufficient amount of NOP instructions to avoid hazards. At the second step, NOP instructions are deleted and behavior of the developed processor is observed carefully to understand data and control hazards. At the third step, benchmark problems are provided, and every student challenges to improve its performance. Finally every student is requested to present how he/she improved the processor. This paper also describes a new educational FPGA board ASAver.1 which is useful for experiments from introductory class to computer architecture/system class. As a feasibility study, a 16-bit pipelined RISC processor "ASAP-O" has been developed which has eight 16-bit general purpose registers, a 16-bit program counter, and a zero flag, with 10 essential instructions.

We propose a top-down approach for cosimulation of hardware/software co-designs for embedded systems and introduce a component logical bus architecture as an interface between software components implemented by processors and hardware components implemented by custom logic circuits. Co-simulation using a component logical bus architecture is possible is the same environment from the stage at which the processor is not yet finalized to the stage at which the processor is modeled in register transfer language. Models based upon a component logical bus architecture can be circulated and reused. We further describe experimental results of our approach.

This paper presents an FPGA architecture for high-speed systems, such as next-generation B-ISDN telecommunications systems. Such a system requires an LSI in which an over-10K-gate circuit can be implemented and that has a clock cycle rate of 80MHz. So far, the FPGA architecture has only been discussed in terms of its circuit structure. In contrast we consider the circuit structure of the FPGA along with the performance of its dedicated CAD system. We evaluate several FPGA logic-element structures with a technology mapping method. From these experiments, a multiplexor-based logic-element is found to be suitable for implementing such a high-speed circuit using the BDD-based technology mapping method. In addition, we examine how to best utilize the characteristics of the selected logic-cell structure in designing the wiring structure. It is found that the multiplexor-based cell can be connected efficiently in a clustered wiring structure.

This paper presents a novel way of evaluating architecture of embedded custom DSPs which helps designers optimizing the datapath configuration and the instruction set. Given a datapath structure, it evaluates the performance in terms of the estimated number of steps to execute the target program on the datapath. A concept of "parallel constraint" is newly introduced, which enables evaluation of the impact of instruction format design on the performance without explicity specifying the instruction format. The number of execution steps is estimated by a combination of static analysis and dynamic analysis. It enables fast and precise estimation of actual performance in the early design stage. We have developed an architecture evaluation system based on the presented method and applied it to some actual design of signal processors. We demonstrate the accuracy of estimation and the usefulness of the method through its applications.

In this paper, we will show some significant results of the routability analysis of bit-serial pipeline datapath designs based on Rent's rule and Donath's observation. Our results show that all of the tested bit-serial benchmarks have Rent exponent of below 0.4, indicating that the average wiring length of the circuit is expected to be independent of the circuit size. This study provides some important implications on the silicon utilization and time-area efficiency of bit-serial pipeline circuits on FPGAs and ASICs.

In this paper we analyze the properties of regular segmentation schemes for 2-D Field Programmable Gate Arrays (FPGAs). Such schemes can be viewed as generalization of the Xilinx-like wire segmentations. We discuss their routing properties and propose a new FPGA design concept of applying architectural coupling to improve chip routability. We give the experimental routing results of such architectures for justification.

In VLSI and printed wiring board design, routing process usually consists of two stages: the global routing and the detailed routing. The routability checking is to decide whether the global wires can be transformed into the detailed ones or not. In this paper, we propose two graphs, the capacity checking graph and the initial flow graph, for efficient routability checking in planar layouts.

We propose a transistor placement algorithm to generate standard cell layout in a two-dimensional placement style. The algorithm optimizes the one-dimensional placement in the first stage, folds the large transistors in the second stage, and optimizes the two-dimensional placement in the final stage. We also propose "cost function" based on wiring length, which closely match the cell optimization. This transistor placement algorithm has been applied to several standard cells, and demonstrated the capability to generate a two-dimensional placement that is comparable to manually designed placement.

After analyzing the limitations of the traditional description of CMOS circuits at the gate level, this paper introduces the notions of switching and signal variables for describing the switching states of MOS transistors and signals in CMOS circuits, respectively. Two connection operations for describing the interaction between MOS transistors and signals and a new description for MOS circuits at the switch level are presented. This new description can be used to express the functional relationship between inputs and the output at the switch level. It can also be used to describe the circuit structure composed of MOS switches. The new description can be effectively used to design both CMOS circuits and nMOS pass transistor circuits.

Signal flow determination of CMOS/VLSI digital circuits is a key issue for switch-level CAD tools such as timing and testability analysers, functional abstractors, ATPGs etc. and even some simulators. Signal flow determination is used to pre-process circuit MOS transistors in order to improve both the accuracy and the running time of these CAD tools. Existing algorithms can be classified into two main categories: the rule-based approach and the algorithm-based approach. However, both of them have several drawbacks. This paper presents an efficient algorithm based on a novel mixed algorithmic and rule based approach. Our algorithm overcomes most of the drawbacks of the pure algorithmic and rule based approaches. It is based on a set of "safe" topological rules rather than ad hoc or technology dependent ones, while the algorithmic aspect of our approach is based on a recursive Depth First Search (DFS). Due to the algorithmic aspect of our approach, some rules consider circuit global effects such as path informations. Our approach provides the advantages of the rule based one (i.e.: the flexibility and the adaptability toward the great variety of CMOS design styles) as well as the advantages of the algorithmic approach (i.e.: the fast processing time and the ability to consider circuits global effects). The result is that the software is very accurate since all the unidirectional and bidirectional transistors are correctly identified in all the pathological benchmarks reported in the literature.

In this paper, we present CB-Power, a hierarchical power analysis and characterization environment of cell-based CMOS circuits. The environment includes two parts, a cell characterization system for timing, input capacitance as well as power and a cell-based power estimation system. The characterization system can characterize basic, complex and transmission gates. During the characterization, input slew rate, output loading, capacitive feedthrough effect and the logic state dependence of nodes in a cell are all taken into account. The characterization methodology separates the power consumption of a cell into three components, e.g., capacitive feedthrough power, short-circuit power and dynamic power. With the characterization data, a cell-based power estimator (CBPE) embedded in Verilog-XL is used for estimating the power consumption of the gates in a circuit. CBPE is also a hierarchical power estimator. Macrocells such as flip-flops and adders are partitioned into primitive gates during power estimation. Experimental results on a set of MCNC benchmark circuits show that the power estimation based on our power modeling and characterization provides within 6% error of SPICE simulation on average while the CPU time consumed is more than two orders of magnitude less.

While estimating glitches or spurious transitions is a challenge due to signal correlations, the random behavior of logic gate delays makes the estimation problem even more difficult. In this paper, we present statistical estimation of signal activity at the internal and output nodes of combinational and sequential CMOS logic circuits considering uncertainty of gate delays. The methodology is based on the stochastic models of logic signals and the probabilistic behavior of gate delays due to process variations, interconnect parasitics, etc. We propose a statistical technique of estimating average-case activity, which is flexible in adopting different delay models and variations and can be integrated with worst-case analysis into statistical logic design process. Experimental results show that the uncertainty of gate delays makes a great impact on activity at individual nodes (more than 100%) and total power dissipation (can be overestimated up to 65%) as well.

This paper presents an effective and robust technique for compacting a large sequence of input vectors into a much smaller input sequence so as to reduce the circuit/gate level simulation time by orders of magnitude and maintain the accuracy of the power estimates. In particular, this paper introduces and characterizes a family of dynamic Markov trees that can model complex spatiotemporal correlations which occur during power estimation both in combinational and sequential circuits. As the results demonstrate, large compaction ratios of 1-2 orders of magnitude can be obtained without significant loss (less than 5% on average) in the accuracy of power estimates.

We have previously proposed a scannable memory configuration which is useful in testing logic blocks around memory arrays. Although the configuration is supposed to be effective in testing the memory array itself by its frequent read/write access during the scan operation, it has not been theoretically shown what types of faults can be detected. In this paper, from a viewpoint of memory testing, we investigate the testability of the scannable memory configuration and propose a memory array test using the scan path. It is shown that we can detect (1) all stuck-at faults in memory cells, (2) all stuck-at faults in address decoders, (3) all stuck-at faults in read/write logic, (4) static, dynamic and 2-coupling faults between memory cells of adjacent words, and (5) static coupling faults between memory cells in the same word. The test can be accomplished simply by comparing scan-in data and scan-out data. The test vector is 20ms bit long, where m is the number of words of the memory array under test and s is the total scan path length.

A CAD-based faulty portion diagnosis technique for CMOS-LSI with single fault using abnormal Iddq has been developed to indicate the presence of physical damage in a circuit. This method of progressively reducing the faulty portion, works by extracting the inner logic state of each block from logic simulation, and by deriving test vector numbers with abnomal Iddq. To easily perform fault diagnosis, the hierarchical circuit structure is divided into primitive blocks including simple logic gates. The diagnosis technique employs the comparative operation of each primitive block to determine whether one and the same inner logic state with abnormal Iddq exists in the inner logic state with normal Iddq or not. The former block is regarded as normal block and the latter block is regarded as faulty block. Faulty portion of the faulty block can be localized easily by using input logic state simulation. Experimental results on real faulty LSI with 100k gates demonstrated rapid diagnosis times of within ten hours and reliable extraction of the faulty portion.

Nonuniform transmission lines are crucial in integrated circuits and printed circuit boards, because these circuits have complex geometries and layout between the multi layers, and most of the transmission lines possess nonuniform characteristics. In this article, an efficient numerical method for analyzing nonuniform transmission lines has been presented by using the Chebyshev expansion method and moment techniques. Efficiency on computational cost is demonstrated by numerical example.

We present theoretical results on the convergence of iterative methods for the solution of linear differential-algebraic equations arising form circuit simulation. The iterative methods considered include the continuous-time and discretetime waveform relaxation methods and the Krylov subspace methods in function space. The waveform generalized minimal residual method for solving linear differential-algebraic equations in function space is developed, which is one of the waveform Krylov subspace methods. Some new criteria for convergence of these iterative methods are derived. Examples are given to verify the convergence conditions.

A non-isothermal device simulation, consisting of solving heat flow equation three-dimensionally together with other semiconductor equations two-dimensionally, is reported for various arrangements of a pluralty of transistors mounted on a single chip. These arrangements are intended to simulate the real situation in an IC chip whereas a three-dimensional solution of the heat flow equation is aimed at accurately determining the thermal interdependence among individual transistors. As a result, the drain current versus drain voltage characteristics of a miniaturized transistor is found to exhibit a heat-induced negative resistance region.

This paper presents a salient method to find an optimal bandwidth for low noise phase-locked loop (PLL) applications by analyzing a discrete-time model of charge-pump PLLs based on ring oscillator VCOs. The analysis shows that the timing jitter of the PLL system depends on the jitter in the ring oscillator and an accumulation factor which is inversely proportional to the bandwidth of the PLL. Further analysis shows that the timing jitter of the PLL system, however, proportionally depends on the bandwidth of the PLL when an external jitter source is applied. The analysis of the PLL timing jitter of both cases gives the clue to the optimal bandwidth design for low noise PLL applications, Simulation results using a C-language PLL model are compared with the theoretical predictions and show good agreement.

Our study investigated the realization of a high-precision MOS current-mode circuit. Simple studies have implied that it is difficult to achieve a high signal-to-noise ratio (S/N) in a current-mode circuit. Since the signal voltage at the internal node is suppressed, the circuit is sensitive to various noise sources. To investigate this, we designed and fabricated a current-mode sample-and-hold circuit with a 3V power supply and a 20MHz clock speed, using a standard CMOS 0.6µm device process. The measured S/N reached 57dB and 59dB in sample mode, and 51dB and 54dB in sample-and-hold mode, with 115µA from a 3V power supply and 220µA from a 5V power supply of input currents and a 10MHz noise bandwidth. The S/N analysis based on an actual circuit was done taking device noise sources and the fold-over phenomena of noise in a sampled system into account. The calculation showed 66.9dB of S/N in sample mode and 59.5dB in sample-and-hold-mode with 115µA of input current. Both the analysis and measurement indicated that 60dB of S/N in sample mode with a 10MHz noise bandwidth is an achievable value for this sample-and-hold circuit. It was clear that the current-mode approach limits the S/N performance because of the voltage suppression method. This point should be further studied and discussed.

A design methodology of the analog currentmode bandwidth programmable integrator for a low voltage (3V) and low power application is developed and the integrator designed by this method is successfully fabricated by a 0.8µm CMOS n-well single poly/double metal process. The integrator ocuppies the active chip area of 0.3mm². The experimental result illustrates a low power dissipation (1.0mW-3.55mW), 65dB of the dynamic range, and bandwidth programmability (10MHz-30MHz) with an external digital 4bit.

A novel CMOS half-wave rectifying transconductor is presented. The proposed circuit utilizes a simple new cascode current subtracter which is obtained from conventional cascode current mirror by a judicious reconfiguration to yield additional subtrahend signal path. The simulated DC transfer characteristics is highly linear with 1.1% linearity error up to 1.5V differential input voltage and the blunt corner at zero-crossing is 20mV. The output resistance is greater than 23MΩ and the total harmonic distortions at 100kHz with 1.5V_p-p in the positive half cycle are better than -46.5dB. The usable operating frequencies are up to 10MHz with maximum peak-to-peak input voltage and 75µW power consumption.

This paper considers a probabilistic model for a database recovery action with checkpoint generations when system failures occur according to a renewal process whose renewal density depends on the cumulative operation period since the last checkpoint. Necessary and sufficient conditions on the existence of the optimal checkpoint interval which maximizes the ergodic availability are analytically derived, and solvable examples are given for the well-known failure time distributions. Further, several methods to be needed for numerical calculations are proposed when the information on system failures is not sufficient. We use four analytical/tractable approximation methods to calculate the optimal checkpoint schedule. Finally, it is shown through numerical comparisons that the gamma approximation method is the best to seek the approximate solution precisely.

This paper presents a new generation method of the periodic orthogonal numerical sequences with small maximum amplitude. In the generation method, complex exponential sequences are used as the generating sequences and such periodic orthogonal numerical sequences are constructed from the discrete Fourier transform of the generating sequences. Until now, there has not been found a generation algorithm to derive such sequences with any period. It is shown that the proposed generation method can derive periodic orthogonal real sequences with the maximum amplitude less than 1.5 for the period 1N200 and periodic orthogonal coplex sequences with all the sbsolute amplitude value of 1 for any period.

The problem of restoring binary (black and white) images degraded by color-dependent flip-flap noises is considered. The real image is modeled by a Markov Random Field (MRF). The Iterated Conditional Modes (ICM) algorithm is adopted. It is shown that under certain conditions the ICM algorithm is insensitive to the MRF image model and noise parameters. Using this property, we propose a parameter-free restoration algorithm which does not require the estimations of the image model and noise parameters and thus can be implemented fully in parallel. The effectiveness of the proposed algorithm is shown through applying the algorithm to degraded hand-drawn and synthetic images.

A modified cryptographic key assignment scheme for the dynamic access control in a group-oriented user hierarchy is presented. In the partially ordered set (poset, for short) user hierarchy (G_jG_i) embedded in a group-oriented (t, n) threshold cryptosystem, the source group G_i has higher security clearance to access the information items held in the target group G_j. If a target group G_j has multipe paths reachable from a source group G_i, we must choose the least cost path to rapidly resolve the dynamic access control problem Furthermore, multiple threshold values are also considered in order to meet the different security requirements.

A novel cryptographic key assignment scheme for dynamic access control in a user hierarchy is presented. Based on Rabin's public key system and Chinese remainder theorem, each security class SC_i is assigned a secret key K_i and some public parameters. In our scheme, a secret key is generated in a bottom-up manner so as to reduce the computation time for key generation and the storage size for public parameters. We also show that our proposed scheme is not only secure but also efficient.

Recently, two new efficient server-aided RSA secret computation protocols were proposed. They are efficient and can guard against some active attacks. In this letter, we propose two multi-round active attacks which can effectively reduce their security level even break them.

The necessary and sufficient conditions for f (x²+x+1) and f (x²+x) to be irreducible, when f (x) is irreducible, are proved. A method that produces polynomials whose roots are linearly independent (therefore form a normal basis for a finite field) is presented.