Compaction-based concurrent error detection for digital circuits

We present a non-intrusive concurrent error detection (CED) method for combinational and sequential digital circuits. We analyze the optimal solution model and point out the limitations that prevent logic synthesis from yielding a minimal-cost monolithic CED implementation. We then propose a compaction-based alternative approach for restricted error models. The proposed method alleviates these limitations by decomposing the CED functionality into: compaction of the circuit outputs, prediction of the compacted responses, and comparison. We model the fault-free and erroneous responses as connected vertices in a graph and perform graph coloring in order to derive the compacted responses. The proposed method is first discussed within the context of combinational circuits, with zero detection latency, and subsequently extended to Finite State Machines (FSMs), with a constant detection latency of one clock cycle. Experimental results demonstrate that the proposed method achieves significant hardware reduction over duplication-based CED, while detecting all possible errors.