Multi-dimensional FFT computation pipelined hardware architecture using Radix-3 and Radix-22 butterflies

A system comprising:

• a system data input configured to receive data samples;
• a system data output configured to output a system processed result;
• a plurality of Radix-22 butterfly stages, each including a first Radix-22 butterfly circuit and a second Radix-22 butterfly circuit, in which the first Radix-22 butterfly circuit of a first Radix-22 butterfly stage includes a data input coupled to the system data input, and one of the first Radix-22 butterfly circuit and the second Radix-22 butterfly circuit of a last Radix-22 butterfly stage includes a data output coupled to the system data output;
• a Radix-3 butterfly circuit including a data input coupled to the system data input and a data output selectively couplable to a data input of one of the first or second Radix-22 butterfly circuits of a second or later Radix-22 butterfly stage based on a particular point transform to be performed by the system;
• a first memory coupled to the first Radix-22 butterfly circuit of the first Radix-22 butterfly stage and to the Radix-3 butterfly circuit;
• and
• a second memory coupled to the second Radix-22 butterfly circuit of the first Radix-22 butterfly stage and to the Radix-3 butterfly circuit.

A method comprising:

• receiving, by a Radix-3 butterfly stage, a new data sample, a first feedback data sample, and a second feedback data sample;
• performing, by the Radix-3 butterfly stage, a first aspect of a 3×2N transform operation to generate a first data output sample, a first memory data sample, and a second memory data sample;
• storing the first and second memory data samples in first and second memories, respectively, the first and second memories shared between the Radix-3 butterfly stage and multiple Radix-22 butterfly circuits, the multiple Radix-22 butterfly circuits unused during performance of the method;
• providing, by the Radix-3 butterfly stage, the first data output sample to a select one of a Radix-22 butterfly stage of a plurality Radix-22 butterfly stages based on a value of N;
• performing, by the select Radix-22 butterfly stage, a second aspect of the 3×2N transform operation to generate a second data output sample;
• and
• providing, by the select Radix-22 butterfly stage, the second data output sample to a next Radix-22 butterfly stage of the plurality Radix-22 butterfly stages.