Fine-Grained Redundancy in Adders

Patrick Ndai1,  Shih-Lien Lu2,  Dinesh Somasekhar2
1Purdue University, 2Intel Corporation


Abstract

We present a technique for fault tolerance in prefix-based adders, and show its application by implementing a Kogge-Stone adder. The technique is based on the fact that an n-bit Kogge-Stone adder can be split into two independent n-bit Han-Carlson (HC) adders by augmenting an additional computation stage to the adder. The presence of single faults only affects one of these HC adders, thus we use a multiplexer to select the correct output. Moreover, the adder can correct multiple faults (up to 50% faulty nodes) as long as all the faults are located on one adder. A 64-bit version of this adder is implemented, and both area & power overhead (relative to a standard KS adder) are less 20%. If faults are present, the delay is 16%. If no faults are present, the delay of the adder is 2% relative to a KS adder.