Embedded system, communication unit and methods for implementing a fast fourier transform

A communication unit, comprising:

• a processing circuit comprising at least one processor configured to support an implementation of a non-power-of-2 fast Fourier transform (FFT) of length N using a multiplication of at least two smaller FFTs of a respective first length N1 and second length N2, where N, N1, and N2 are whole numbers;
• and
• a memory, operably coupled to the processing circuit and comprising at least input data and other associated data, the input data including an input data complex number sequence;
• wherein the processing circuit is configured to:
• receive the input data complex number sequence from the memory;
• adapt the received input data complex number sequence by inserting at least one zero into every Xth data point that results in an excess number of data points above the length N, where X is a whole number and X=N1, such that the inserted zeroes enables a use of a multiple-of-Q FFT, wherein Q is a number of processing elements that are operated in parallel;
• perform a first decomposed FFT of the respective first length N1 on the adapted input data complex number sequence using the multiple-of-Q FFT to produce a first output complex number sequence;
• restore a number of data points of the first output complex number sequence to the length N after performing the first decomposed FFT;
• and
• perform a second decomposed FFT of the respective second length N2 on the first output complex number sequence to produce a second output complex number sequence.

A method for an embedded system to support an implementation of a non-power-of-2 fast Fourier transform (FFT) of length N, the method comprising:

• receiving an input data complex number sequence;
• adapting the received input data complex number sequence by inserting at least one zero into every Xth data point that results in an excess number of data points above the length N, where N is a whole number and X=N1, such that the inserted zeroes enables a use of a multiple-of-Q FFT;
• performing a first decomposed FFT of a respective first length N1 on the adapted input data complex number sequence using the multiple-of-Q FFT to produce a first output complex number sequence;
• restoring a number of data points of the first output complex number sequence to the length N after performing the first decomposed FFT;
• and
• performing a second decomposed FFT of a respective second length N2 on the first output complex number sequence to produce a second output complex number sequence;
• where N, N1, and N2 are whole numbers and Q is a number of processing elements that are operated in parallel.