Method of generating fft value and electronic device for performing the method

An electronic device, comprising:

• a processor;
• and
• a memory,
• wherein the processor is configured to:
• generate a plurality of sub-input data sets by classifying a plurality of input values, each having an index in a first dimension and an index in a second dimension, based on an even index in the first dimension, an odd index in the first dimension, an even index in the second dimension, and an odd index in the second dimension, wherein the plurality of sub-input data sets comprises
• a first sub-input data set that includes input values of the plurality of input values that have an even index in the first dimension and an even index in the second dimension,
• a second sub-input data set that includes input values of the plurality of input values that have an odd index in the first dimension and an even index in the second dimension,
• a third sub-input data set that includes input values of the plurality of input values that have an even index in the first dimension and an odd index in the second dimension, and
• a fourth sub-input data set that includes input values of the plurality of input values that have an odd index in the first dimension and an odd index in the second dimension;
• calculate a first intermediate value by performing an FFT on the first sub-input data set;
• calculate a second intermediate value by performing an FFT on the second sub-input data set;
• calculate a third intermediate value by performing an FFT on the third sub-input data set;
• calculate a fourth intermediate value by performing an FFT on the fourth sub-input data set;
• calculate a first value, a second value, a third value, and a fourth value for the plurality of input values based on the first intermediate value, the second intermediate value, the third intermediate value, and the fourth intermediate value;
• and
• generate a plurality of FFT value sets for the plurality of input values based on the first value, the second value, the third value, and the fourth value.

A method, performed by an electronic device, of generating fast Fourier transform (FFT) values for a plurality of multi-dimensional input values, the method comprising:

• generating a plurality of sub-input data sets by classifying a plurality of input values, each having an index in a first dimension and an index in a second dimension, based on an even index in the first dimension, an odd index in the first dimension, an even index in the second dimension, and an odd index in the second dimension, wherein the plurality of sub-input data sets comprises a first sub-input data set, a second sub-input data set, a third sub-input data set, and a fourth sub-input data set;
• calculating a first intermediate value by performing an FFT on the first sub-input data set;
• calculating a second intermediate value by performing an FFT on the second sub-input data set;
• calculating a third intermediate value by performing an FFT on the third sub-input data set;
• calculating a fourth intermediate value by performing an FFT on the fourth sub-input data set;
• calculating a first value for the plurality of input values based on the first intermediate value;
• calculating a second value for the plurality of input values based on the second intermediate value;
• calculating a third value for the plurality of input values based on the third intermediate value;
• calculating a fourth value for the plurality of input values based on the fourth intermediate value;
• and
• generating a plurality of FFT value sets for the plurality of input values based on the first value, the second value, the third value, and the fourth value,
• wherein the first intermediate value, the second intermediate value, the third intermediate value, and the fourth intermediate value are calculated through a first pipeline, a second pipeline, a third pipeline, and a fourth pipeline, respectively.