Multiplier-less real-valued FFT-like transformation (ML-RFFT) and related real-valued transformations

Abstract

This paper proposes a new multiplier-less Fast Fourier Transform-like (ML-RFFT) transformation for real-valued sequence. Like the ML-FFT, it parameterizes the twiddle factors in the conventional radix-2n or split-radix real-valued FFT algorithm as certain rotation-like matrices and approximates the associated parameters inside these matrices by the sum-of-power-of-two (SOPOT) or canonical signed digits (CSD) representations. Because of the symmetry in the algorithm, it only requires about half the number of additions as required by the ML-FFT. Moreover, using the mappings between the DFT and the DCTs and DWTs, new ML-FFT-based transformation called ML-DCTs and ML-DWTs are derived. Design examples of the new transformations are given to demonstrate the proposed approach.