New fault tolerance techniques are presented for protecting a lossless compression algorithm, arithmetic coding, whose recursive nature makes it vulnerable to temporary hardware failures. The fundamental arithmetic operations are protected by low-cost residue codes, employing fault tolerance in multiplications and additions. Additional fault-tolerant design techniques are developed to protect other critical steps such as normalization and rounding, bit stuffing and index selection. For example, the decoding step that selects the next symbol is checked by comparing local values with estimates already calculated in other parts of the decoding structure. Bit stuffing, a procedure for limiting very long carry propagations, is checked through modified residue values, whereas normalization and rounding after multiplication are protected by efficiently modifying the multiplier to produce residue segments.