16. Error Detecting and Correcting Codes

Error-correcting coding can be defined as the art of adding redundancy to stored data or messages efficiently so that distortions can be detected and correctly revised. In the context of functional safety of IEC 61508, this can be addressed as method to control statistical hardware failures in case of memory bit flips or bit flips in wire or wireless (telemetry) messages. This includes other bit changes such as bit shifts. However, within classical functional safety approaches, the correction of data in case of detected errors is not recommended. Hence, any wrong corrections need to be controlled. To understand the mechanisms of detection and correction, first, elementary examples are considered in detail: parity bit, Hamming code Hamming(7,4), and cyclic-redundancy check (CRC) checksums. Based on this, an example is given how a safety-critical time is stored using various error-detection and error-correction codes within an embedded highly safety-critical system. It is investigated which error-detection and error-correction scheme is most efficient considering limited resources within a given application case in terms of critical and non-critical corrections. The following schemes are compared for one up to five bit flips: BCD, BCD with XOR, BCD with 2oo3, BCD with Hamming (7,4), Hamming(7,4,1), Hamming(21,16), and Hamming (21,16,1). Inter alia, correct and incorrect corrections are distinguished as well as safety-critical and non-safety-critical corrections. The results confirm that error correction must be very carefully assessed within operational contexts if suitable for safety-critical systems, in particular, in cases if there is no safe default state, e.g., as for scenarios of fast-moving autonomous transport systems. In such cases, it must be shown that the probability of wrong correction within the operational context leads to acceptable system risks.