Abstract
Parallel prefix circuits are circuits that generate the prefix computation of a given input. The prefix computation is used extensively in hardware circuits. Prefix computation has its wide applications in cryptography, fast adders, etc. Any hardware circuit that have adders as one of its components could benefit from such computation. Prefix circuits proposed in literature differ in their performance, cost and size. Usually most circuits use operation nodes with fan-in/fan-out of 2. One classification of prefix circuits is dependent on the width of the circuit: circuits with width equal to the input, and circuits with width less than the input. In this paper, we first perform an analysis of two important classes of parallel prefix circuits. The first class performs well when the input size is of the same width as the circuit. The second class performs well when the width of the circuit is greater than the circuit width. We analyze the two classes in case of existence of faulty nodes. We estimate the time penalty and the number of idle nodes when a node in a certain location in the circuit goes faulty. Then based on the analysis, we propose new designs that can better handle faulty nodes. Finally, we simulate the circuits on FPGAs to assess their performance with faulty nodes.