Abstract:
We consider problems of detecting errors in combinational circuits and algorithms for the decoding of linear codes. We show that a totally self-checking combinatorial circuit for the decoding of a binary Hamming $[n,k]$ code can be constructed if and only if $n=2^r-1$, $r=n-k$. We introduce the notion of a totally self-checking combinational circuit detecting error clusters of size at most $\mu$; for shortened Hamming $[n,k]$ codes, we construct totally self-checking decoding combinational circuits detecting error clusters of size at most $\mu$, $2\leq\mu<n-k$. We describe single-error protected and self-checking algorithms: the extended Euclidean algorithm and decoding algorithms for binary BCH codes and Reed–Solomon codes over $GF(2^m)$.