Improved fast convolution algorithm with reduced complexity and increased flexibility

摘要

A modified fast convolution algorithm may be enhanced in order to increase the flexibility of the algorithm. In an exemplary embodiment of the present invention, a folding unit is introduced as a pre-processing stage prior to the Inverse Discrete Fourier Transform (IDFT) in the receiver. The folding unit adds outer frequency components onto inner frequency components in the frequency domain in order to produce a reduced set of frequency components. In an alternative embodiment, an unfolding unit is introduced as a post-processing stage after the Discrete Fourier Transform (DFT) in the transmitter. The unfolding unit expands the set of the set of frequency components by adding translated original components outside the original set. The folding and unfolding processes increase the flexibility of the modified fast convolution algorithm by reducing the number of operations per second that have to be performed for the channel-specific parts of the algorithm. Moreover, since the number of operations per channel decreases, more channels can be treated by a single chip.