This paper proposes a novel algorithm, which can be used to model and analyze mesh tree hybrid power/ground distribution networks with multiple voltage supply in time domain. Not only this algorithm enhances common method's ability on analysis of power/ground network with irregular topology, but also very high accuracy it keeps. The accuracy and stability of this algorithm is proved using strict math method in this paper. Also, the usage of both precondition technique based on Incomplete Choleskey Decomposition and fast variable elimination technique has improved the algorithm's efficiency a lot. Experimental results show that it can finish the analysis of power/ground network with enormous size within very short time. Also, this algorithm can be applied to analyze the clock network, bus network, and signal network without buffer under high working frequency because of the independence of the topology.

Crosstalk noise is one of the emerging issues in deep sub-micrometer technology which causes many undesired effects on the circuit performance. In this paper, a Crosstalk-Aware Routing Resource Assignment (CARRA) algorithm is proposed, which integrates the routing layers and tracks to address the crosstalk noise issue during the track/layer assignment stage. The CARRA problem is formulated as a weighted bipartite matching problem and solved using the linear assignment algorithm. The crosstalk risks between nets are represented by an undirected graph and the maximum number of the concurrent crosstalk risking nets is computed as the max clique of the graph. Then the nets in each max clique are assigned to disadjacent tracks. Thus the crosstalk noise can be avoided based on the clique concept. The algorithm is tested on IBM benchmarks and the experimental results show that it can improve the final routing layout a lot with little loss of the completion rate.

A new CMOS quaternary D flip-flop is implemented employing a multiple-valued clock. Pspice simulation shows that the proposed flip-flop has correct operation. Compared with traditional multiple-valued flip-flops, the proposed multiple-valued CMOS flip-flop is characterized by improved storage capacity, flexible logic structure and reduced power dissipation.

The Godson project is the first attempt to design high performance general-purpose microprocessors in China. This paper introduces the microarchitecture of the Godson-2 processor which is a 64-bit, 4-issue, out-of-order execution RISC processor that implements the 64-bit MIPS-like instruction set. The adoption of the aggressive out-of-order execution techniques (such as register mapping, branch prediction, and dynamic scheduling) and cache techniques (such as non-blocking cache, load speculation, dynamic memory disambiguation) helps the Godson-2 processor to achieve high performance even at not so high frequency. The Godson-2 processor has been physically implemented on a 6-metal 0.18μm CMOS technology based on the automatic placing and routing flow with the help of some crafted library cells and macros. The area of the chip is 6,700 micrometers by 6,200 micrometers and the clock cycle at typical corner is 2.3ns.

Recent software system contain many functions to provide various services. According to this tendency, it is difficult to ensure software quality and to eliminate crucial faults by conventional software testing methods. So taking the effect of test engineer's skill on test item generation into consideration, we propose a new test item generation method, which supports the generation of test items for illegal behavior of the system. The proposed method can generate test items based on use-case analysis, deviation analysis for legal behavior, and faults tree analysis for system fault situations. From the results of the experimental applications of our method, we confirmed that test items for illegal behavior of a system were effectively generated, and also the proposed method could effectively assist test item generation by an engineer with low-level skill.

Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a cooperative environment, where two parties need to solve a geometric problem based on their joint data, but neither wants to disclose its private data to the other party. These problems are the distance between two private points, the relation between a private point and a circle area, the relation between a private point and an ellipse area and the shortest distance between two point sets. The paper gives solutions to these specific geometric problems, and in doing so a building block is developed, the protocol for the distance between two private points, that is also useful in the solutions to other geometric problems and combinatorial problems.

Tate pairings over elliptic curves are important in cryptography since they can be used to construct efficient identity-based cryptosystems, and their implementation dominantly determines the efficiencies of the cryptosystems. In this paper, the implementation of a cryptosystem is provided based on the Tate pairing over a supersingular elliptic curve of MOV degree 3. The implementation is primarily designed to re-use low-level codes developed in implementation of usual elliptic curve cryptosystems. The paper studies how to construct the underlying ground field and its extension to accelerate the finite field arithmetic, and presents a technique to speedup the time-consuming powering in the Tate pairing algorithm.

Abe et al. proposed the methodology of ring signature (RS) design in 2002 and showed how to construct RS with a mixture of public keys based on factorization and/or discrete logarithms. Their methodology cannot be applied to knowledge signatures (KS) using the Fiat-Shamir heuristic and cut-and-choose techniques, for instance, the Goldreich KS. This paper presents a more general construction of RS from various public keys if there exists a secure signature using such a public key and an efficient algorithm to forge the relation to be checked if the challenges in such a signature are known in advance. The paper shows how to construct RS based on the graph isomorphism problem (GIP). Although it is unknown whether or not GIP is NP-Complete, there are no known arguments that it can be solved even in the quantum computation model. Hence, the scheme has a better security basis and it is plausibly secure against quantum adversaries.

The Probability Distribution of Slot Selection (PDoSS) of IEEE 802.11 DCF is extremely uneven, which makes the packet collision probability very high. In this paper, the authors explore how to make the stations select the slots uniformly, and give an RWBO(Pd, w) algorithm for 802.11 DCF to make the PDoSS even and decrease the packet collision probability. A Markov model is given to analyze the PDoSS of RWBO(Pd, w). The performance of RWBO(Pd, w) is evaluated by simulation in terms of saturation throughput and packet collision probability. The simulation results indicate that RWBO(Pd, w) can decrease the packet contention probability to a large extent, and utilize the channel more efficiently as compared to the 802.11 DCF. Moreover, the relation between saturation throughput and walking probability (Pd, w), the relation between saturation throughput and contention windows (w), the relation between packet collision probability and walking probability (Pd, w), and the relation between packet collision probability and contention windows (w) are analyzed. The analysis indicates that RWBO(Pd, w) has some remarkable features: its saturation throughout keeps high and packet collision probability keeps very low (under 0.1) in a large range of Pd and w, which allow users to configure Pd and w more flexibly.

Previous researches have shown that Distributed Coordination Function (DCF) access mode of IEEE 802.11 has lower performance in heavy contention environment. Based on the in-depth analysis of IEEE 802.11 DCF, NSAD (New Self-adapt DCF-based protocol) has been proposed to improve system saturation throughput in heavy contention condition. The initial contention window tuning algorithm of NSAD is proved effective in error-free environment. However, problems concerning the exchanging of initial contention window occur in error-prone environment. Based on the analysis of NSAD's performance in error-prone environment, RSAD is proposed to further enhance the performance. Simulation in a more real shadowing error-prone environment is done to compare the performance of NSAD and RSAD and results have shown that RSAD can achieve further performance improvement as expected in the error-prone environment than NSAD (I.e., better goodput and fairness index).

With the rapid development of deep submicron (DSM) VLSI circuit designs, many issues such as time closure and power consumption are making the physical designs more and more challenging. In this review paper we provide readers with some recent progress of the VLSI physical designs. The recent developments of floorplanning and placement, interconnect effects, modeling and delay, buffer insertion and wire sizing, circuit order reduction, power grid analysis, parasitic extraction, and clock signal distribution are briefly reviewed.

Increasing IC densities necessitate diagnosis methodologies with enhanced defect locating capabilities. Yet the computational effort expended in extracting diagnostic information and the stringent storage requirements constitute major concerns due to the tremendous number of faults in typical Ics. In this paper, we propose an RT-level diagnosis methodology capable of responding to these challenges. In the proposed scheme, diagnostic information is computed on a grouped fault effect basis, enhancing both the storage and the computational aspects. The fault effect grouping criteria are identified based on a module structure analysis, improving the propagation ability of the diagnostic information through RT modules. Experimental results show that the proposed methodology provides superior speed-ups and significant diagnostic information compression at no sacrifice in diagnostic resolution, compared to the existing gate-level diagnosis approaches.

VLSI testing is being pushed to the high-level based technology. In this paper a Verilog Register transfer level Model (VRM) for integrated circuits is proposed. The model provides a text format file, which is convenient and more practical for developing succeeding Register Transfer Level (RTL) test tools, such as fault simulation, test pattern generation and so forth. Based on the VRM, an RTL concurrent fault simulation approach is presented. After RTL fault models and super faults defined, the concurrent fault simulation algorithm is given. The corresponding RTL concurrent fault simulator, VFSim, was implemented. The initial experiments show that the RTL fault simulator is efficient for VLSI circuits.

A new fault model, called the X-fault model, is proposed for fault diagnosis of physical defects with unknown behaviors by using X symbols. An efficient X-fault simulation method and an efficient X-fault diagnostic reasoning method are presented. Fault diagnosis based on the X-fault model can improve the accuracy of failure analysis for a wide range of physical defects in complex and deep submicron integrated circuits.

Gate Oxide Short (GOS) defects are becoming predominant as technology is scaling down. Boolean and IDDQ testing of this defect has been widely studied but there is no paper dedicated to delay testing of this defect. So, this paper studies the delay behavior of Gate Oxide Short faults due to pinhole in the gate oxide. The objective of this paper is to give a detailed analysis of the behavior of the GOS defect taking into account the random parameter of the defect such as the GOS resistance and the GOS location. Because an accurate analysis is desired, the bi-dimensional array will be used. Because a complete analysis is desired, we derive the dynamic characteristic of the GOS as a function of the GOS resistance and location. It is demonstrated that I) GOS has a significant impact on gate delay, ii) GOS located close to the source of the transistor and with small resistance has very high impact.

This paper presents a test resource partitioning technique based on an efficient response compaction design~called quotient compactor(q-Compactor). Because q-Compactor is a single-output compactor, high compaction ratios can be obtained even for chips with a small number of outputs. Some theorems for the design of q-Compactor are presented~to achieve full diagnostic ability, minimize error cancellation and handle unknown bits in the outputs of the circuit under test (CUT). The q-Compactor can also be moved to the load-board, so as to compact the output response of the CUT even during functional testing. Therefore, the number of tester channels required to test the chip is significantly reduced. The experimental results on the ISCAS '89 benchmark circuits and an MPEG 2 decoder SoC show that the proposed compaction scheme is very efficient.

This paper proposes an effective method for reducing test data volume under multiple scan chain designs. The proposed method is based on reduction of distinct scan vectors using selective don't-care identification. Selective don't-care identification is repeatedly executed under condition that each bit of frequent scan vectors is fixed to binary values (0 or 1). Besides, a code extension technique is adopted for improving compression efficiency with keeping decompressor circuits simple in the manner that the code length for infrequent scan vectors is designed as double of that for frequent ones. The effectiveness of the proposed method is shown through experiments for ISCAS'89 and ITC'99 benchmark circuits.

This paper describes a built-in self-test (BIST) hardware overhead minimization technique used during a BIST synthesis process. The technique inserts a minimal amount of BIST resources into a digital system to make it fully testable. The BIST resource insertion is guided by the results of symbolic testability analysis. It takes into consideration both BIST register cost and wiring overhead in order to obtain the minimal area designs. A Simulated Annealing algorithm is used to solve the overhead minimization problem. Experiments show that considering wiring area during BIST synthesis results in smaller final designs as compared to the cases when the wiring impact is ignored.