Prefolding in FHT algorithms

A generalised approach to prefolding the input sequence of the FHT algorithms m times for a radix-r case is introduced. The resulting output sequence is found, in the case of a decaying input sequence to have the same spectral shape and resolution as the output sequence obtained with the nearest higher two-power sequence length input using zero padding. By this procedure, a significant reduction in the required amount of arithmetic can be obtained.