Method for accelerating fast Fourier transform based on field programmable gate array
A method for accelerating fast Fourier transform (FFT) based on field programmable gate array is provided. A sequence requiring N-point FFT is decomposed equally into 4 subsequences. The 4 subsequences are processed through 4 parallel FFT intellectual property (IP) cores. Finally, an arithmetic operation is performed on the processed data and twiddle factor data pre-stored in a memory to obtain a result of the N-point FFT of an original sequence. An FFT decomposition module, a twiddle factor storage module, and an operation processing module are provided. Through the processing method, a time delay consumed by an N-point FFT operation can be reduced, and excellent application value can be achieved in a high-speed digital signal processing system.
1 . A method for accelerating fast Fourier transform based on field-programmable gate array (FPGA), wherein the FPGA is internally provided with a fast Fourier transform (FFT) decomposition module, a twiddle factor storage module, and an operation processing module; and the method comprises:
step S1: decomposing, by the FFT decomposition module, an input sequence having a length of N into 4 subsequences having a length of N/4, and synchronously performing N/4-point FFT;
step S2: outputting, by the twiddle factor storage module, pre-stored twiddle factor data by determining an external input signal for performing arithmetic operation; and
step S3: processing, by the operation processing module, data output by the FFT decomposition module and the twiddle factor storage module to obtain a result of N-point FFT of an original sequence;
wherein the FFT decomposition module comprises a sequence decomposition module and four parallel N/4-point FFT submodules, wherein the N/4-point FFT submodules are FFT intellectual property (IP) cores provided by the FPGA, with an output mode of sequential output;
the twiddle factor storage module comprises two control units respectively marked as ctr1 and ctr2, and three independent single-port block random access memories (BRAMs) respectively configured to store three different types of twiddle factor data; the three independent single-port BRAMs respectively have a depth of N/4 and are respectively marked as BRAM1, BRAM2, and BRAM3; and corresponding twiddle factor data stored in the three independent single-port BRAMs are as follows:
WN
1
=
e
-
j
2
π
N
k
k
=
0
,
1
…
,
N
4
-
1
;
(
1
)
WN
2
=
e
-
j
2
π
N
k
k
=
N
4
,
N
4
+
1
,
…
,
N
2
-
1
;
(
2
)
and
WN
3
=
e
-
j
2
π
N
/
2
k
k
=
0
,
1
…
N
4
-
1
;
(
3
)
wherein the step S1 comprises:
substep S11: upon determining that a signal fft_valid==1, decomposing the input sequence x(n) having the length of N into the 4 subsequences, x(m), x(m+2), x(m+1), and x(m+3), each having the length of N/4, wherein n=0, 1, . . . , N−1, and m=0, 1, . . . , N/4−1;
substep S12: transforming the 4 subsequences x(m), x(m+2), x(m+1), and x(m+3) through four parallel N/4-point FFT IP cores respectively, to obtain 4 output sequences z 1 (m), z 2 (m), z 3 (m), and z 4 (m), wherein m=0, 1, . . . , N/4−1; z 1 (m) corresponds to an output of x(m), z 2 (m) corresponds to an output of x(m+2), z 3 (m) corresponds to an output of x(m+1), and z 4 (m) corresponds to an output of x(m+3); and
substep S13: outputting synchronously a data valid signal data1_valid to the twiddle factor storage module while outputting the sequences z 1 (m), z 2 (m), z 3 (m), and z 4 (m).
2 . The method for accelerating the fast Fourier transform based on the FPGA according to claim 1 , wherein the step S2 further comprises:
substep S21: sequentially storing corresponding twiddle factors into three independent memory cells BRAM1, BRAM2, and BRAM3 in a binary form according to an increasing order of k values;
substep S22: when the control unit ctr1 determines that the signal data1_valid==1, generating a read enable signal rd1 and a read address counter addr1 of BRAM3, sequentially acquiring the twiddle factor data of WN3, and transmitting the twiddle factor data of WN3 to the operation processing module; and
substep S23: when the control unit ctr2 determines that a signal data2_valid==1, generating a read enable signal rd2 and a read address counter addr2 of BRAM1 and BRAM2, sequentially acquiring the twiddle factor data of WN1 and WN2, and transmitting the twiddle factor data of WN1 and WN2 to the operation processing module.
3 . The method for accelerating the fast Fourier transform based on the FPGA according to claim 1 , wherein step S3 further comprises:
substep S31: performing a delay beating on the sequences z 2 (m) and z 4 (m) to wait for the twiddle factor data of WN3; and multiplying the sequences z 2 (m) and z 4 (m) by the twiddle factor data of WN3 in sequence in a pipeline architecture to obtain sequences z 21 (m) and z 41 (m) having a length of N/4, wherein m=0, 1, . . . , N/4−1;
substep S32: performing the delay beating on the sequences z 1 (m) and z 3 (m) to wait for z 21 (m) and z 41 (m); adding z 1 (m) and z 21 (m) in sequence in the pipeline architecture to obtain a sequence Z 1 (m) having a length of N/4, wherein m=0, 1, . . . , N/4−1; performing a subtraction operation on z 1 (m) and z 21 (m) in sequence in the pipeline architecture, by subtracting z 21 (m) from z 1 (m) to obtain a sequence Z 2 (m) having a length of N/4, wherein m=0, 1, . . . , N/4−1; adding z 3 (m) and z 41 (m) in sequence in the pipeline architecture to obtain a sequence z 3 (m) having a length of N/4, wherein m=0, 1, . . . , N/4−1; and performing a subtraction operation on z 3 (m) and z 41 (m) in sequence in the pipeline architecture, by subtracting z 41 (m) from z 3 (m) to obtain a sequence Z 4 (m) having a length of N/4, wherein m=0, 1, . . . , N/4−1;
substep S33: outputting synchronously a data valid signal data2_valid to the twiddle factor storage module while obtaining Z 3 (m) and Z 4 (m);
substep S34: performing the delay beating on the sequences Z 3 (m) and Z 4 (m) to wait for the twiddle factor data of WN1 and the twiddle factor data of WN2; multiplying the sequence Z 3 (m) and the twiddle factor data of WN1 in sequence in the pipeline architecture to obtain a sequence Z 31 (m) having a length of N/4, wherein m=0, 1, . . . , N/4−1; and multiplying the sequence Z 4 (m) and the twiddle factor data of WN2 in sequence in the pipeline architecture to obtain a sequence Z 41 (m) having a length of N/4, wherein m=0, 1, . . . , N/4−1;
substep S35: performing the delay beating on the sequences Z 1 (m) and Z 2 (m) to wait for Z 31 (m) and Z 41 (m); adding the sequences Z 1 (m) and Z 31 (m) in sequence in the pipeline architecture to obtain a sequence y 1 (n) having a length of N/4, wherein n=0, 1, . . . , N/4−1; adding the sequences Z 2 (m) and Z 41 (m) in sequence in the pipeline architecture to obtain a sequence y 2 (n) having a length of N/4, wherein n=0, 1, . . . , N/4−1; performing a subtraction operation on the sequences Z 1 (m) and Z 31 (m) in sequence in the pipeline architecture, by subtracting Z 31 (m) from Z 1 (m) to obtain a sequence y 3 (n) having a length of N/4, wherein n=0, 1, . . . , N/4−1; and performing a subtraction operation on the sequences Z 2 (m) and Z 41 (m) in sequence in the pipeline architecture, by subtracting Z 41 (m) from Z 2 (m) to obtain a sequence y 4 (n) having a length of N/4, wherein n=0, 1, . . . , N/4−1; and
substep S36: outputting synchronously a data valid signal dout_valid while outputting y 1 (m), y 2 (m), y 3 (m), and y 4 (m).