2013/09/02 by Debesh K. Das, Debabani Chowdhury, Das, Debesh K. +5
Computer Science · Engineering · #FOS: Computer and information sciences #Formal Methods in Verification #Low-power high-performance VLSI design #Other Computer Science (cs.OH) #VLSI and Analog Circuit Testing
paper · pdf · doi:10.48550/arxiv.1309.3993
openalex publication_date 2013/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many underlying structural and functional factors that determine the fault behavior of a combinational network, are not yet fully understood. In this paper, we show that there exists a large class of Boolean functions, called root functions, which can never appear as faulty response in irredundant two-level circuits even when any arbitrary multiple stuck-at faults are injected. Conversely, we show that any other Boolean function can appear as a faulty response from an irredundant realization of some root function under certain stuck-at faults. We characterize this new class of functions and show that for n variables, their number is exactly equal to the number of independent dominating sets (Harary and Livingston, Appl. Math. Lett., 1993) in a Boolean n-cube. We report some bounds and enumerate the total number of root functions up to 6 variables. Finally, we point out several open problems and possible applications of root functions in logic design and testing.