Finite-state machine embeddings for nonconcurrent error detection and identification

Abstract

In digital sequential systems that operate over several time steps, a state-transition fault at any time step during the operation of the system can corrupt its state and render its future functionality useless. Such state-transition faults are usually handled by embedding the given sequential system into a larger one, in a way that preserves the state evolution and properties of the original system while enabling an external mechanism to perform checks to detect, identify and correct errors in the encoded state of this redundant system. Checking is typically performed concurrently (i.e., at the end of each time step) and can potentially cause high power consumption or an overall slowdown in the system; more importantly, concurrent checking imposes significant reliability requirements on the error-detection/identification mechanism. In this paper, we develop a methodology for systematically constructing embeddings of finite-state machines so that the external mechanism can capture transient state-transition faults via checks that are performed in a nonconcurrent manner (e.g., periodically instead of every time step). More specifically, by characterizing nonconcurrent error-detecting/identifying capabilities in terms of state encoding constraints and redundant dynamics, the proposed approach can be used to construct a redundant version of the given finite-state machine (FSM) that allows the external mechanism to detect and identify errors due to past state-transition faults based on an analysis of the current, possibly corrupted FSM state. As a result, the checker in such designs can operate at a slower speed than the rest of the system which relaxes the stringent requirements on its reliability. © 2005 IEEE.