A class of almost-optimal size-independent parallel prefix circuits

• A new class of parallel prefix circuits.
• The circuits perform well when the input size is more than the width of the circuit.
• The proposed circuit is optimal in speed within one time unit.
• The size of the circuits is optimal within one.
• The proposed circuit is faster than any other circuit of the same width and fan-out.

Prefix computation is one of the fundamental problems that can be used in many applications such as fast adders. Most proposed parallel prefix circuits assume that the circuit is of the same width as the input size.In this paper, we present a class of parallel prefix circuits that perform well when the input size, nn, is more than the width of the circuit, mm. That is, the proposed circuit is almost optimal in speed when n>mn>m. Specifically, we derive a lower bound for the depth of the circuit, and prove that the circuit requires one time step more than the optimal number of time steps needed to generate its first output. We also show that the size of the circuit is optimal within one. The input is divided into subsets, each of width m−1m−1, and presented to the circuit in subsequent time steps. The circuit is compared with functionally similar circuits of (Lin, 1999 [9]; Lin and Hung, 2009 [12]) to show its outperforming speed. When n>mn>m, the circuit is shown to be faster than the family of waist-size optimal circuits with waist 1 (WSO-1) of the same width and fan-out.