Parity-preserving transformations in computer arithmetic

Parity checking comprises a low-redundancy method for the design of reliable digital systems. While quite effective for detecting single-bit transmission or storage errors, parity encoding has not been widely used for checking the correctness of arithmetic results because parity is not preserved during arithmetic operations and parity prediction requires fairly complex circuits in most cases. We propose a general strategy for designing parity-checked arithmetic circuits that takes advantage of redundant intermediate representations. Because redundancy is often used for high performance anyway, the incremental cost of our proposed method is quite small. Unlike conventional binary numbers, redundant representations can be encoded and manipulated in such a way that parity is preserved in each step. Additionally, lack of carry propagation ensures that the effect of a fault is localized rather than catastrophic. After establishing the framework for our parity-preserving transformations in computer arithmetic, we illustrate some applications of the proposed strategy to the design of parity-checked adder/subtractors, multipliers, and other arithmetic structures used in signal processing.