Encoded finite-state machines for non-concurrent error detection and identification

Abstract

In this paper we develop a methodology for systematically constructing redundant finite-state machines in a way that enables an external mechanism to detect and identify transient state-transition faults by performing checks in a non-concurrent manner (e.g., periodically). More specifically, by characterizing non-concurrent error detection/identification capabilities in terms of state encoding constraints and redundant dynamics, the proposed approach constructs a redundant version of the given FSM that allows the external mechanism to detect and identify errors due to past state-transition faults based on the current, corrupted FSM state. Therefore, the external mechanism can operate at a slower speed than the rest of the system, which relaxes the stringent requirements on its reliability.