In accordance with Moore's law, recent design issues include shortening of time-to-market and detection of delay faults. Several studies with respect to formal techniques have examined the first issue. Using the equivalence checking, it is possible to identify whether large circuits are equivalent or not in a practical time frame. With respect to the latter issue, it is difficult to achieve 100% fault efficiency even for transition faults in full scan designs. This study involved proposing a redundant transition fault identification method using equivalence checking. The main concept of the proposed algorithm involved combining the following two known techniques, 1. modeling of a transition fault as a stuck-at fault with temporal expansion and 2. detection of a stuck-at fault by using equivalence checking tools. The experimental results indicated that the proposed redundant identification method using a formal approach achieved 100% fault efficiency for all benchmark circuits in a practical time even if a commercial ATPG tool was unable to achieve 100% fault efficiency for several circuits.

The digital logic rewiring technique has been shown to be one of the most powerful logic transformation methods. It has been proven that rewiring is able to further improve some already excellent results on many EDA problems, ranging from logic minimization, partitioning, FPGA technology mappings to final routings. Previous studies have shown that ATPG-based rewiring is one of the most powerful tools for logic perturbation while a graph-based rewiring engine is able to cover nearly one fifth of the target wires with 50 times runtime speedup. For some problems that only require good-enough and very quick solutions, this new rewiring technique may serve as a useful and more practical alternative. In this work, essential elements in graph-based rewiring such as rewiring patterns, pattern size and locality, etc., have been studied to understand their relationship with rewiring performance. A structural analysis on the target-alternative wire pairs discovered by ATPG-based and graph-based engines has also been conducted to analyze the structural characteristics that favor the identification of alternative wires. We have also developed a hybrid rewiring approach that can take the advantages from both ATPG-based and graph-based rewiring. Experimental results suggest that our hybrid engine is able to achieve about 50% of alternative wire coverage when compared with the state-of-the-art ATPG-based rewiring engine with only 4% of the runtime. Through applying our hybrid rewiring approach to the FGPA technology mapping problem, we could achieve similar depth level and look-up table number reductions with much shorter runtime. This shows that the fast runtime of our hybrid approach does not sacrifice the quality of certain rewiring applications.

The logic optimization based on redundancy addition and removal is one of methods which can deal with large-scale logic circuits. In this logic optimization a few redundant elements are added to a logic circuit, and then many other redundant elements which are generated by the redundancy addition are identified and removed. In this paper an optimization method based on redundancy addition and removal using implication relations is proposed. The advantage of the proposed method is to identify removable redundant elements with short time, because the proposed method directly identifies redundant elements using implication relations from two illegal signal assignments which are produced by redundancy addition. The experimental results compared this method with another method show that this method is faster than the another method without declining the optimization ability.