Fast fourier transform circuit

A fast Fourier transform circuit comprising:

• a multiplexer which receives a plurality of data streams transmitted in parallel on a time axis and which outputs partial data of each data stream every unit time in determined data stream order;
• a plurality of delay sections which delay and output input data;
• butterfly computation sections which correspond to the plurality of delay sections in number, each of which receives output data from a corresponding delay section as first input data, each of which computes a sum of and a difference between the first input data and second input data, and each of which outputs one computation result or the second input data to the corresponding delay section;
• and
• multiplication sections each of which multiplies an other computation result obtained by each of the butterfly computation sections or output data from the corresponding delay section and a twiddle factor together and each of which outputs a multiplication result as the second input data for a butterfly computation section at a next stage,
• wherein:
• the butterfly computation section at a first stage receives as the second input data the partial data outputted from the multiplexer;
• and
• a delay section, of the plurality of delay sections, corresponding to the butterfly computation section at the first stage receives in the data stream order the partial data outputted from the multiplexer, delays the partial data, and outputs the partial data as the first input data for the butterfly computation section at the first stage.