Protecting data compression: arithmetic coding

Data-compression implementations are particularly sensitive to internal fau lts because most inherent redundancy in the input data is minimised by the source-coding process. Fault-tolerance techniques are presented for protect ing a lossless compression algorithm, arithmetic coding, that is vulnerable to temporary hardware failures. The fundamental arithmetic operations are protected by low-cost residue codes, employing new fault-tolerance methods for multiplications and additions, as recently reported. However, additiona l fault-tolerant design techniques are developed to protect critical steps such as normalisation and rounding, bit stuffing and index selection. These approaches integrate well with residue codes. Normalisation and rounding a fter multiplication are protected by efficiently modifying the multiplier t o produce residue segments. The decoding step that selects the next symbol is checked by comparing local values with estimates already calculated in o ther parts of the decoding structure, whereas bit stuffing, a procedure for limiting very long carry propagations, is checked by modified residue valu es. Overhead complexity issues are discussed as rough estimates.