Enumeration of Genaralized Parallel Counters for Multi-Input Adder Synthesis for FPGAs

This paper proposes a method for exhaustive search of efficient FPGA implementations of generalized parallel counters (GPCs) that have not yet been discovered. Multi-input addition is the core operation in multiplier circuits and multiply-accumulate circuits. A known method to construct efficient multiinput adders on FPGAs involves building trees of full adders extended into GPCs. To date, three types of GPCs that can be implemented in a single slice of Xilinx 7 series have been identified. This paper attempts to find other GPCs that can be implemented in a single slice exhaustively. We enumerate possible GPC input-output specifications with output of five bits or less and determine the connections from inputs to LUTs and the truth tables of LUTs if they exist. Running the proposed search method resulted in the discovery of five new GPCs: $(\mathbf{1, 2, 6; 4}),(4,2,5; 5)$, $(1,2,4,4; 5),(1,3,1,6; 5)$, and (1,3,3,4;5). Furthermore, using these GPCs to construct multiplier circuits and multi-input adder circuits resulted in a reduction in the number of slices for two circuits and the number of stages for two other circuits.