Skip to Navigation
Auburn University Homepage
A-Z Index | Map | People Finder
Auburn University Logo
Electronic Theses and Dissertations
Skip to Main Content
Main Navigation 
  • AUETD Home
  • Graduate School
JavaScript is disabled for your browser. Some features of this site may not work without it.
View Item 
  •   AUETD Home
  • View Item
  •   AUETD Home
  • View Item

Hierarchical Fault Collapsing for Logic Circuits

View/Open
Extracted text (125.5Kb)
SANDIREDDY_RAJA-KIRAN-KUMAR_48.pdf (428.3Kb)
Date
2005-05-15
Author
Sandireddy, Raja-Kiran-Kumar
Type of Degree
Thesis
Department
Electrical and Computer Engineering
Metadata
Show full item record
Abstract
The process of grouping stuck-at faults into equivalence or dominance classes and then selecting one representative for each class is known as fault collapsing. There have been several techniques to collapse the faults structurally and functionally. We present a new method that determines all functional dominances between the faults of a circuit using redundancy identification and then collapses faults. This procedure produces the smallest possible equivalence and dominance collapsed sets. Our method is more efficient than other functional collapsing algorithms, but is still expensive in CPU time. Therefore, we recommend its application only to smaller sub-circuits that may be embedded in larger circuits. Another contribution of this research is a thorough examination of the fault equivalence and dominance relations for multiple output circuits. The conventional definition for equivalence says that “two faults are equivalent if and only if the corresponding faulty circuits have identical output functions.” This definition is extended for multiple output circuits as “two faults of a Boolean circuit are called diagnostically equivalent if and only if the functions of the two faulty circuits are identical at each output.” Alternatively, “if all tests that detect a fault also detect another fault, not necessarily at the same output, then the two faults are called detection equivalent.” The definitions for fault dominance follow on similar lines. A program implements our novel algorithm based on redundancy identification to find the complete equivalence and dominance collapsed sets using diagnostic and detection collapsing definitions. When applied to a 4-bit ALU it collapses the total fault set of 502 faults to 253 and 155, respectively, according to diagnostic equivalence and dominance. The collapsed sets have 234 and 92 faults, respectively, for detection equivalence and dominance. In comparison, the conventional structural equivalence and dominance collapsing results in 301 and 248 faults, respectively. Functional fault collapsing, using the proposed algorithm, is done for standard cells and other logic blocks and the collapse data is saved as library information. Using the redundancy-based fault collapsing for a full adder library cell, we hierarchically collapse faults in a 64-bit adder to sets of 1538 equivalence and 768 dominance collapsed faults. In comparison, a flattened 64-bit adder circuit collapses into 2306 and 1794 equivalence and dominance collapsed sets, respectively. It is also shown that hierarchical collapsing results in an order of magnitude reduction in the CPU time for very large circuits. A flattened 1024-bit adder requires 39.9 seconds for structural collapsing while the same circuit, if described hierarchically as an interconnect of 1024 full adders, takes only 3.60 seconds. The 1024-bit adder can also be hierarchically built using four 256-bit adders, which are built using four 64-bit adder, and so on and this circuit takes only 2.31 seconds to collapse faults. In conclusion, hierarchical collapsing saves CPU time and potentially provides more collapsing.
Files
Name:
SANDIREDDY_RAJA-KIRAN-KUMAR_48.pdf.txt  
Size:
125.5Kb
Name:
SANDIREDDY_RAJA-KIRAN-KUMAR_48.pdf  
Size:
428.3Kb
URI
http://hdl.handle.net/10415/929

Browse

All of AUETDBy Issue DateAuthor / AdvisorTitlesDepartments

My Account

Login

Auburn University Libraries | 231 Mell Street | Auburn, Alabama 36849 | (334) 844-4500 or (800) 446-0387 |

 

Auburn University |Auburn, Alabama 36849 |(334) 844-4000 |

Website Feedback |Privacy |Copyright ©