Design of Common Sub expression Elimination Algorithm in Fast Fourier Transform

摘要

Common sub expression elimination (CSE) is a critical procedure in many multiplierless implementations of DSP algorithms. The aim of CSE is dual-pronged to reduce the number of logic operators used and to minimize the logic depth (critical path) of the DSP algorithm implemented in VLSI. CSE algorithm combines greedy algorithm and exhaustive search to select the best set of common sub expressions is proposed. Using CSE algorithm, we reduce the additive complexities of cyclotomic fast Fourier transforms (CFFTs) requiring fewer additions.