Automate hardware design using recursion in non-power of two fast fourier transform (FFT) hardware algorithms

A method comprising:

• receiving, at a compiler that implements a non-power of two Fast Fourier Transform (FFT) algorithm using a recursive function, input specifying a sequence of indexes and a bit width of a fixed-point digital signal processor (DSP), wherein instructions for the compiler are stored in a memory device;
• performing, by a processor communicatively coupled with the memory device and configured to execute the instructions, a process that splits the sequence using a recursive loop, wherein the recursive loop determines a number of multiplications in a hardware design of a plurality of compute blocks of the fixed-point DSP, determines a number of FFT points, identifies operations for serialization at a first rate that is greater than a channel rate of the fixed-point DSP, and identifies operations for math optimizations, and generates a trace graph of the non-power of two FFT algorithm corresponding to an addressing scheme of the hardware design, wherein the process uses the recursive function and ends when the recursive loop decrements to a value corresponding to a Radix-3 or Radix-2;
• and
• outputting data comprising at least the number of multiplications in the hardware design, the number of FFT points, and the trace graph.

A non-transitory computer-readable storage medium, the computer-readable storage medium including instructions of a compiler that implements a non-power of two Fast Fourier Transform (FFT) algorithm using a recursive function that, when executed by a processing device, cause the processing device to:

• receive input specifying a sequence of indexes and a bit width of a fixed-point digital signal processor (DSP);
• perform a process that splits the sequence using a recursive loop, wherein the recursive loop determines a number of multiplications in a hardware design of a plurality of compute blocks of the fixed-point DSP, determines a number of FFT points, identifies operations for serialization at a first rate that is greater than a channel rate of the fixed-point DSP, and identifies operations for math optimizations, and generates a trace graph of the non-power of two FFT algorithm corresponding to an addressing scheme of a hardware design of a plurality of compute blocks of the fixed-point DSP, wherein the process uses the recursive function and ends when the recursive loop decrements to a value corresponding to a Radix-3 or Radix-2;
• and
• output data comprising at least the number of multiplications in the hardware design, the number of FFT points, and the trace graph.