Recursive implementation of prime radix and composite radix Fourier transforms

The discrete Fourier transform (DFT) is a fundamental operation in digital signal processing. The transform techniques outlined in the paper have been developed to implement high performance processors in gate array technologies available from commercial foundries in the UK, particularly those with a mixed analogue/digital capability. The practical constraints involved in developing this type of processor differ significantly from those met in full custom VLSI designs. In particular, the overall complexity of the implementation must be minimised so that processors can be realised on simple gate arrays. The paper outlines the development of two such algorithms