A Formal Proof of PG Recurrence Equations of Parallel Adders

Parallel adders are extensively used in high-performance computer design and hardware acceleration for large-scale data processing. In the adder design theory, a key property of the group propagated carry and the group generated carry is based on the two recurrence equations. The property is fundamental to many parallel prefix adders. However, there is no proof of the property in the literature. This article presents a rigorous and complete proof for it. The proof can leverage a solid ground for a formal verification methodology for parallel adder-based chip design.