Methods and systems for complexity reduction in discrete Fourier transform computations
AssigneeApple Inc.
InventorsChris C. Lee, Ali Sazegari
Life of this patent
Estimating the term…
Abstract
In one embodiment, a computer-implemented method of discrete Fourier transform (DPT), FFT, or DCT computations on a system comprising a processor is described herein. In one example, the method includes receiving, with the processor, input complex samples from memory of the system, determining input vectors based on the received input complex samples, determining a DFT radix p of p macro blocks based on the input vectors, determining p independent DFT-L vectors based on the p macro blocks with L being based on p, and generating p DFT-N output vectors without reordering or shuffling output data based on the p independent DFT-L vectors.
Claims23
A computer-implemented method of discrete Fourier transform (DFT) computations on a system comprising a hardware processor, the method comprising:
- receiving, with the hardware processor, input complex samples from memory of the system;
- determining input vectors based on the received input complex samples;
- determining a DFT radix p of p macro blocks based on the input vectors;
- determining, with the hardware processor, p independent DFT-L vectors to reduce complexity of DFT computations to reduce processing cycles of the hardware processor based on the p macro blocks with L being based on p, wherein N is based on p2 and L;
- and
- generating p DFT-N output vectors to be stored in the memory in-place without reordering or shuffling output data based on the p independent DFT-L vectors.
A non-transitory computer-readable medium having executable instructions stored thereon, that when executed by a processing system comprising at least one hardware processor coupled to a memory perform operations, the operations comprising:
- receiving, with the hardware processor, input complex samples from memory of the system;
- determining input vectors based on the received input complex samples;
- determining a DFT radix p of p macro blocks based on the input vectors;
- determining, with the hardware processor, p independent DFT-L vectors to reduce complexity of DFT computations to reduce processing cycles of the hardware processor based on the p macro blocks with L being based on p, wherein N is based on p2 and L;
- and
- generating p DFT-N output vectors to be stored in the memory in-place without reordering or shuffling output data based on the p independent DFT-L vectors.
A processing system comprising:
- memory programmed with instructions;
- and
- at least one hardware processor coupled to the memory, the at least one hardware processor to execute the instructions to receive input complex samples from memory of the system, to determine input vectors based on the received input complex samples, to determine a DFT radix p of p macro blocks based on the input vectors with p being a prime number, to determine p independent DFT-L vectors to reduce complexity of DFT computations to reduce processing cycles of the at least one hardware processor based on the p macro blocks with L being based on p, wherein N is based on p2 and L, and to generate p DFT-N output vectors to be stored in the memory in-place without reordering or shuffling output data based on the p independent DFT-L vectors.
A computer-implemented method of discrete Fourier transform (DFT) computations on a system comprising a hardware processor, the method comprising:
- receiving, with the hardware processor, input complex samples from memory of the system;
- determining input vectors based on the received input complex samples;
- determining a DFT of macro blocks based on the input vectors;
- determining, with the hardware processor, independent DFT-L vectors to reduce complexity of DFT computations to reduce processing cycles of the hardware processor based on the macro blocks;
- and
- generating DFT-N output vectors to be stored in the memory in-place without reordering or shuffling output data based on the independent DFT-L vectors, wherein N is a multiple of 16 and L=N/16.
A non-transitory computer-readable medium having executable instructions stored thereon, that when executed by a processing system comprising at least one hardware processor coupled to a memory perform operations, the operations comprising:
- receiving, with the hardware processor, input complex samples from memory of the system;
- determining input vectors based on the received input complex samples;
- determining a DFT of macro blocks based on the input vectors;
- determining, with the hardware processor, independent DFT-L vectors to reduce complexity of DFT computations to reduce processing cycles of the hardware processor based on the macro blocks;
- and
- generating DFT-N output vectors to be stored in the memory in-place without reordering or shuffling output data based on the independent DFT-L vectors, wherein N is a multiple of 16 and L=N/16.
Dependencies are inferred from the claim text.