Telefonaktiebolaget Lm Ericsson (Publ)

Anders Orling

Antoni Fertner

Mattias Hyll

The present invention significantly reduces the number of complex computations that must be performed to compute a DFT or IDFT when a pattern is identified in an original input data sequence and is used to modify the data sequence in order to reduce the size of the sequence to be transformed. A DFT (IDFT) is performed on the modified input data sequence to generate a transformed sequence. The transformed data sequence is then manipulated to generate an output sequence that corresponds to the DFT (IDFT) of the original input data sequence without having actually calculated the DFT (IDFT) of the entire, original input data sequence. Three symmetrical patterns are used in the invention to simplify and render more efficient DFT and IDFT computations: Hermite symmetry, index-reversed, complex-conjugate symmetry, and mirror symmetry. As a result, the number of complex multiplications required to perform the DFT (or IDFT) is considerably less than the number of complex multiplications required to calculate the DFT (or IDFT) of the original input data sequence. The computational reduction increases signal processing speed and decreases power consumption, both attributes are highly desirable in virtually every DFT/IDFT application.

Computationally efficient analysis and synthesis of real signals using discrete fourier transforms and inverse discrete fourier transforms

The present invention significantly reduces the number of complex computations that must be performed in computing the discrete Fourier transform (DFT) and inverse DFT (IDFT) operations. In particular, the DFT and IDFT operations are computed using the same computing device. The computation operations are substantially identical for both operations with the exception that for the IDFT operation, the data are complex conjugated before and after processing. Using the same computing device/operations, both DFT and IDFT computations are optimized for maximum efficiency. A common transform process is selectively connected to first and second data processing paths. A DFT operation is performed on an N-point sequence on the first data processing path, and an IDFT operation is performed on an N-point sequence on the second data processing path using the same N-point fast Fourier transform (FFT).

Growing community of inventors

Stockholm, Sweden

Anders Orling