CN105718424B - A kind of parallel Fast Fourier Transform processing method - Google Patents

Abstract

The present invention provides a parallel Fast Fourier Transform processing method, which divides the data sequence x(n) whose number of points is N=r ^S into vr secondary data blocks, and then calculates each secondary data by using radix r FFT in the block The FFT result of data, wherein: v=r ^Z , r and S are arbitrary integers, Z=0, 1, ... or S 2, so the number of data points N of the present invention has more values, can be selected in these Select the scheme with the least zero padding in the value, thereby reducing the occupation of storage space and calculation time; and the present invention adopts multi-butterfly parallel computing, and the number of parallel butterfly computing units v=r ^Z , so the present invention can be based on hardware The degree of parallelism can be selected according to the allocation of resources, which has greater flexibility.

Description

A Parallel Fast Fourier Transform Processing Method

technical field

The invention relates to the technical field of FFT processor design, in particular to a parallel fast Fourier transform processing method.

Background technique

Fast Fourier transform is a key component of digital signal processing in communication and radar systems, and it is used to realize the transformation of digital signals between time domain and frequency domain. It can realize functions such as spectrum analysis, digital filtering, and correlation processing in practical applications.

At present, the multi-butterfly parallel computing fast Fourier transform is basically implemented using the radix-2 and radix-4 structures under in-situ storage, which mainly includes steps such as memory access address generation, conflict-free data exchange, and butterfly calculation. In the process of conflict-free data exchange, if the method of adding an additional cache is adopted, the cache usage will increase with the increase of the number of points, and at the same time, a large number of cache read and write operations will increase the entire calculation time. At present, in the fast Fourier transform of multi-butterfly parallel computing, the memory non-conflict access address generation module is mostly used, thereby offsetting the conflicts generated during the data access process before butterfly computing, and performing multi-butterfly parallelism under the condition of conflict-free access to memory calculate.

The CN101504638 patent of Beijing Institute of Technology discloses a variable-point pipeline FFT processor, which is a variable-point pipeline FFT processor, including a first 1024-point variable FFT processing module, a twiddle factor processing module, and a second 1024 Point-variable FFT processing module, selection and control module. The above four modules and the intermediate data storage module outside the processor jointly complete the two-dimensional processing of the large-point FFT. Zhongxing Communications Co., Ltd. CN101847986A patent discloses a circuit and method for realizing FFT/IFFT transformation. The method is as follows: determine the number of iterations, the depth of the first and second RAMs, and the depth of the ROM memory; The first and second halves are respectively stored in the second and first RAMs; iterative butterfly operation is performed: in the first iteration, when reading the first and second RAMs, the inverted order is used to read, and even times of butterfly operation results are written In the first RAM, the results of the odd number of butterfly operations are written to the second RAM; in other iterations, the first and second RAMs are read using the normal bit order, and the way to write back to the RAM is the same as the first time; the last iteration uses the normal sequential access to memory.

The above method mainly has the following problems:

(1) The singleness of the base affects the selection of Fourier transform points in practical applications

In the fast Fourier transform in the prior art, when the number of points corresponding to base 2 and base 4 is selected, at most double zeros are required to meet the condition that the length is a power of 2. This doubles the storage space and more than doubles the computing time in the calculation process.

(2) The singleness of the base affects the selection of the parallelism of the butterfly computing unit in practical applications

In the prior art, since the base number is a power of 2, the parallelism of the butterfly computing unit must also be a power of 2 to achieve the highest calculation efficiency. However, in practical applications, hardware resources may not meet such requirements. In this case, reducing the degree of parallelism to meet the design requirements will significantly reduce the performance of system computing.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies of the prior art, to provide a parallel fast Fourier transform processor and processing method, which can be realized.

Above-mentioned purpose of the present invention is achieved through the following scheme:

A parallel fast Fourier transform processing method, comprising the steps of:

(1), performing first-level data grouping on the received data sequence x(n), that is, dividing N data into v first-level data blocks, and each of the first-level data blocks includes data; wherein, the n _1th data in the n _2th primary data block is x′(n ₁ ,n ₂ )=x(n ₁ v+n ₂ ), n2=0, 1,..., v-1; N=r ^S , v=r ^Z , Z=0, 1,... or S-2, S and r are integers;

(2), each first-level data block that step (1) is divided carries out second-level data grouping, is about to divide each first-level data block into r secondary data blocks, and each described second-level data block includes data; wherein, the n' _1th data x"(n' ₁ ,n' ₂ ,n _{2 )} =x' ₍ n' ₁ r+n' ₂ ,n ₂ ), n' ₂ =0, 1, ..., r-1, n ₂ =0, 1, ..., v-1;

(3), for each secondary data block data Point FFT calculation; wherein the n'th ₂ secondary data blocks divided by n' ₂ primary data blocks The FFT calculation result of each data is in, n' ₂ =0, 1, ..., r-1, n ₂ =0, 1, ..., v-1,

(4), the FFT calculation results of r secondary data blocks in each primary data block are merged to obtain the FFT calculation results of each primary data block; wherein, in the n ₂ primary data blocks The FFT calculation result of the data is in, n ₂ =0, 1, . . . , v-1,

(5) Merge the FFT calculation results of v first-level data blocks to obtain the N-point FFT calculation results of the data sequence x(n) Wherein, _k =0, 1, ..., N-1, W _N =e ^-j2π/N .

The above-mentioned parallel fast Fourier transform processing method, in step (2), adopts vr The dual-port memory of point stores the data of vr secondary data blocks; the vr dual-port memory is divided into v memory groups, corresponding to v primary data blocks; each of the memory groups includes r dual-port Memory, corresponding to r secondary data blocks in one primary data block; wherein an S-bit r-ary counter is used to obtain the storage address of each data in the sequence x(n), that is, to determine the The nth data is stored in the storage address serial number Add_ID (n) in the Ram_Id (n) memory in the Group_Id (n) memory group, n=0, 1, ..., N-1, and the specific implementation method is as follows:

The r-ary value of the count value n of the counter is (a _S-1 a _S-2 ...a _Z+1 a _Z a _Z-1 ...a ₁ a ₀ ) _r , where a ₀ to a _S-1 are The r-ary value of the 1st to S-th digits of the r-ary value ranges from 0 to r-1, and the r-ary value of the memory group serial number Group_Id(n) is (a _Z-1 … a ₁ a ₀ ) _r , the r-ary value of the memory serial number Ram_Id(n) is (a _Z ) _r , the r-ary value of the storage address serial number Add_ID(n) is (a _S-1 a _S-2 …a _{Z +1} ) _r .

In the above-mentioned parallel fast Fourier transform processing method, in step (3), the radix r FFT calculation is used to obtain the FFT results of data; in step (4), adopt radix r FFT calculation to merge the FFT calculation results of r secondary data blocks in each primary data block; use radix v FFT calculation in step (5) Merge the FFT calculation results of the v first-level data blocks.

In the above-mentioned parallel fast Fourier transform processing method, in step (3), v base r butterfly units are used to perform base r FFT calculations on vr secondary data blocks, and r secondary data blocks in each primary data block The block shares a base-r butterfly computing unit through a time-division multiplexing system; A control unit and r parallel-to-serial conversion modules, wherein:

r serial-to-parallel conversion modules: one-to-one correspondence with r secondary data blocks in a primary data block; read data from the memories of r secondary data blocks respectively to obtain r channels of serial data, wherein each channel Serial data includes data points; then each serial-to-parallel conversion module performs serial-to-parallel conversion on the corresponding serial data, and converts the serial data points are converted into r parallel data, and each parallel data includes data points;

The first-level gating control unit: performs gating operation on the parallel data output by r serial-to-parallel conversion modules, selects the r-way parallel data output by one of the serial-to-parallel conversion modules each time, and then transfers the r-way parallel data output to the base r butterfly computing unit;

Base-r butterfly calculation unit: receive r-channel parallel data to perform base-r FFT calculation, and output r-channel parallel calculation results to the second-stage channel gating control unit;

The second-level gating control unit: gating among r parallel-to-serial conversion modules, outputting the received r parallel FFT calculation results to one of the parallel-to-serial conversion modules, and the sequence number of the selected parallel-to-serial conversion module is the same as The serial numbers of the serial-to-parallel conversion modules gated by the first-level strobe control unit are the same;

r parallel-serial conversion modules: one-to-one correspondence with r secondary data blocks in a first-level data block; the parallel-serial conversion module gated by the second-level gating control unit receives r parallel FFT calculation results, Perform parallel-to-serial conversion of one channel of serial data, store the serial data in the memory of the corresponding secondary data block, and the storage location is consistent with the location where the serial-to-parallel conversion module reads the data, that is, realize in-situ storage.

Compared with the prior art, the present invention has the following advantages:

(1), in the prior art, the number of data points N that limits FFT transformation is the power of 2, and the present invention adopts base r fast Fourier transform, carries out the number of data points N=r ^S of FFT transformation, wherein r and S are arbitrary Integer, so the number of data points N of the present invention has more values, and the scheme with the least zero padding can be selected in these values, thereby reducing the occupation of storage space and computing time;

(2), the present invention adopts multi-butterfly parallel computing, and the number of parallel butterfly computing units v=r ^z , wherein z=0, 1, ..., S-2, r and S are arbitrary integers, so the present invention The degree of parallelism can be selected according to the configuration of hardware resources, which has great flexibility;

(3), the present invention uses v=r ^z parallel butterfly computing units to perform calculations when performing N=r ^S -point FFT transformation, and the entire calculation cycle is r ^Sz-1 (Szr)+2r(Sz-1).

Description of drawings

Fig. 1 is the flow chart of parallel fast Fourier transform processing method of the present invention;

Fig. 2 is a schematic diagram of generation of conflict-free access addresses in the present invention;

Fig. 3 is the sequence diagram that base r butterfly computing unit processes data in a single dual-port memory;

Fig. 4 is the time sequence diagram that time division multiplexing base r-butterfly computing unit processes data in a plurality of dual-port memories;

FIG. 5 is a functional block diagram of the time-division multiplexing system of the base-r-butterfly computing unit of the present invention.

Fig. 6a shows that r memories are time-division multiplexed with 1 base r butterfly computing unit in the present invention to perform r groups Schematic diagram of data reading and storage during point FFT calculation;

Fig. 6b shows that r memories are time-division multiplexed with 1 base r butterfly computing unit in the present invention to perform r groups Schematic diagram of data reading and storage when point FFT calculation results are merged;

Fig. 6c shows that in the present invention, v memory groups are time-division multiplexed with 1 basic v-butterfly computing unit to perform v groups Schematic diagram of data reading and storage when point FFT calculation results are merged.

Detailed ways

Below in conjunction with accompanying drawing and specific example the present invention is described in further detail:

(1) Theoretical derivation of parallel FFT calculation

1.1 Decomposition process of N-point FFT

Perform N-point FFT calculation on the received data sequence x(n) to obtain X(k). The calculation formula is as follows:

Wherein, W _N =e ^-j2π/N , k=0, 1, ..., N-1, n = 0, 1, ..., N-1.

Define v as a positive integer divisible by N, then n and k can be decomposed into:

in, n ₂ =0, 1, . . . , v-1, k ₂ =0, 1, . . . , v-1. Equation (2) maps the one-dimensional vector n and k in the interval [0, N-1] to the two-dimensional vector (n ₁ ,n ₂ ) and (k ₁ ,k ₂ ), then formula (1) can be rewritten as:

Wherein, X'(k ₁ ,n ₂ )=FFT[x(n ₁ ,n ₂ ),(N/v)].

Equation (3) shows that an N-point FFT can be decomposed into v-point FFT and N/v-point FFT. Similarly, N/v point FFT can be further decomposed into FFT with smaller points, defining r as a positive integer divisible by N, n ₁ and k ₁ can be decomposed into:

in, n' ₂ =0, 1, ..., r-1, k' ₂ =0, 1, . . . , r−1. Equation (4) will be in The one-dimensional vectors n ₁ and k ₁ in the interval are mapped to [0,r-1]×[0,N/(vr)-1] two-dimensional vectors.

According to the decomposition formula of formula (4), arrange X'(k ₁ ,n ₂ ) as follows:

Wherein, X"(k' ₁ ,n' ₂ ,n ₂ )=FFT[x(n' ₁ ,n' ₂ ,n ₂ ),N/(vr)].

1. Parallel calculation process of 2N-point FFT

According to the decomposition process of the N-point FFT deduced above, the present invention adopts the parallel fast Fourier transform processing method flow process as shown in Figure 1 to carry out N-point FFT calculation to the input data sequence x(n) to obtain X(k):

(b1), performing first-level data grouping on the received data sequence x(n), that is, dividing N data into v first-level data blocks, and each first-level data block includes data; wherein, the n _1th data x′(n ₁ ,n ₂ )=x(n ₁ v+n ₂ ) in the n _2th primary data block, n ₂ =0, 1, ..., v-1; N = r ^S , v = r ^Z , Z = 0, 1, ..., S-2, S and r are integers;

(b2), carry out second-level data grouping to each first-level data that step (b1) divides, be about to divide each first-level data block into r second-level data blocks, and each second-level data block includes data; wherein, the n' _1th data x"(n' ₁ ,n' ₂ ,n _{2 )} =x' ₍ n' ₁ r+n' ₂ ,n ₂ ), n' ₂ =0, 1, ..., r-1, n ₂ =0, 1, ..., v-1;

(b3), for each secondary data block data Point FFT calculation; wherein the n'th ₂ secondary data blocks divided by n' ₂ primary data blocks The FFT calculation result of each data is in, n' ₂ =0, 1, ..., r-1, n ₂ =0, 1, ..., v-1,

(b4), the FFT calculation results of r secondary data blocks in each primary data block are merged to obtain the FFT calculation results of each primary data block; wherein, the n ₂ primary data blocks The FFT calculation result of the data is in, n ₂ =0, 1, . . . , v-1,

(b5), merge the FFT calculation results of v first-level data blocks to obtain the N-point FFT calculation results of the data sequence x(n) Wherein, _k =0, 1, ..., N-1, W _N =e ^-j2π/N .

In the above process, step (b3) uses radix r FFT calculation to obtain the FFT results of the data. In steps (b4)~(b5), X'(k 1 ,n 2 ) is obtained from X"(k' ₁ ,n' ₂ ,n ₂ ), and X'(k _{1 ,n 2 ) is obtained from X'(k 1 , n 2} ) (k), which includes a level of v Point-based r FFT and one-level N-point basis v FFT, that is to say, in step (b4), the basis r FFT calculation is used to combine the FFT calculation results of r secondary data blocks in each primary data block, and in In step (b5), basal v FFT calculations are used to combine the FFT calculation results of the v primary data blocks.

(2) Parallel FFT calculation structure design

According to the steps (b1) and (b2) described above, the data sequence x(n) whose number of points is N=r ^S (S is an integer) is divided into vr secondary data blocks, which can then be calculated by using radix r FFT in each secondary data block FFT results of the data. Since the aforementioned vr secondary data blocks are independent of each other, parallel FFT calculations are performed on each secondary data block, thereby improving the N=r ^S -point FFT calculation speed of the sequence x(n). And the present invention proposes a kind of basic r butterfly unit time division multiplexing method, can realize the time division multiplexing of r secondary data blocks in 1 primary data block with 1 basic r butterfly unit, realize r secondary data Therefore, the entire system can realize the FFT parallel calculation of vr secondary data blocks by using only v base r butterfly units, and then through the first-level base r and the first-level base v FFT, N=r can be obtained The FFT calculation result of point ^S data.

2.1. Input data storage allocation

The present invention adopts vr The point's dual-port memory stores the vr secondary data blocks divided by steps (b1)-(b2). Wherein, the present invention divides the vr dual-port memories into v memory groups, and these v memory groups correspond to v first-level data blocks; each memory group includes r dual-port memories, and these r dual-port memories correspond to r secondary data blocks in one primary data block.

The present invention adopts an S-bit r-ary counter to obtain the storage address of each data in the sequence x(n), that is, to determine that the nth data x(n) in the sequence is stored in the Ram_Id in the Group_Id(n) memory group (n) storage address sequence number Add_ID(n) in the memory storage, n=0, 1, ..., N-1, the specific implementation method is as follows:

The r-ary value of the count value n of the counter is (a _S-1 a _S-2 ...a _Z+1 a _Z a _Z-1 ...a ₁ a ₀ ) _r , where a ₀ ~ a _S-1 are all The 1st to the Sth digits of the r-ary system value, the value range of the number is 0 to r-1, then: the _r -ary value of the memory group serial number Group_Id(n) is (a _Z-1 ... a ₁ a ₀ ) _r , the r-ary value of the memory serial number Ram_Id(n) is (a _Z ) _r , the r-ary value of the storage address serial number Add_ID(n) is (a _S-1 a _S-2 …a _{Z +1} ) _r .

2.2, r secondary data blocks Point FFT Parallel Computing

According to the above-mentioned input data storage allocation method, each secondary data block is independently stored in a memory, and the Independent FFT calculations are performed on the point data. The method for generating data access addresses in each memory and the method for time-division multiplexing r secondary data blocks into one basic r butterfly unit are given below during parallel FFT calculation.

2.2.1, each memory Point data access address generation method

in each memory point data for independent FFT calculations, which The FFT of a point data sequence x(n') is defined as follows:

The time-domain address identifier n' and the frequency-domain address identifier k' are represented by M-bit r-ary numbers as follows:

Wherein, M=S-z-1. Rewrite formula (6) in r-ary system according to formula (7), then:

It can be seen from formula (8) that the N'-point FFT calculation can be decomposed into M-time iterative calculations, where the m-th iteration formula is:

Among them, m=1,2,...,M, the phase term of the rotation factor It can be seen from formula (9) that during the mth iteration, the data access address is divided into three parts:

in, Addr(m,1)=k _m-1 ,

Define the maximum set of multiple continuous butterfly units with different rotation factors as a butterfly set. From formula (10), it can be known that Addr(m,0) represents the identity of the non-overlapping butterfly set in the mth level, and Addr(m ,1) represents the identity of the operand in each butterfly unit, and Addr(m,2) represents the identity of the butterfly unit contained in each butterfly set. And for the data access address of the mth level, it can be regarded as the shift-add combination of the three, so the present invention adopts an M-bit r-ary counter C=(c _M-1 c _M-2 ... c ₁ c ₀ ) _r , generate data access address by intercepting C.

in each memory When performing FFT calculation on point data, it is necessary to sequentially process the butterfly set in the butterfly computing unit, the butterfly unit in the butterfly set, and the r operands in the butterfly unit respectively. In this way, (c _M-1 c _M-2 ... c _M-m+2 c _M-m+1 ) _r maps the identity Addr(m,0) of the non-overlapping butterfly set in the mth level, (c ₀ ) _r to map the identity of the operand in each butterfly unit Addr(m,1), (c _Mm-1 c _Mm-2 ...c ₁ ) _r maps the identity of the butterfly unit contained in each butterfly set Addr(m, 2), the relationship between the access address of each level and the count value C is shown in formula (11), and the access address of the mth level AcesAddr(m) can be expressed as follows:

The data access address generation process of each level of FFT calculation in each memory is shown in Figure 2.

2.2.2. Calculation process of base-r butterfly computing unit

To perform N'-point FFT calculation on a single dual-port memory, the basic r-butterfly calculation unit needs to complete two operations: one is the process of multiplying the twiddle factor; the other is multiplying the r-point DFT matrix. The former can be completed by sequentially reading data from the memory and passing through the pipeline complex multiplier, and the latter can input the r operands fetched in real-time order in parallel to the butterfly unit through register delay.

The calculation process of the whole basic r-butterfly computing unit is as follows:

(A), According to the data access address deduced in the previous section, the data is fetched from the read bus Data _load of the memory. Each r data represents the r operation data of the butterfly unit, which are marked as Op(i) in turn, and the data is fetched at the same time as The twiddle factors are multiplied, and the result is marked as Op'(i), where i=0,1,...,r-1;

(B), the r input registers of the butterfly unit are Bf_reg _in (i), and the output registers are Bf_reg _out (i). After each r data is taken out from the bus, Bf_reg _in (i)=Op'(i ), and carry out the butterfly calculation. The butterfly unit adopts a parallel pipeline calculation method, and the butterfly unit has r-1 idle time for each calculation, and the calculation result is expressed as Op”(i), so that Bf_reg _out (i)=Op”(i);

(C), sequentially assign r data in Bf_reg _out (i) to the write bus Data _store of the memory, and complete the calculation process of the butterfly unit this time.

The timing diagram of the above process is shown in Figure 3, from which it can be seen that during the calculation process of a single radix r FFT, r-1 butterfly units will be in an idle state every r clock cycles.

2.2.3. The time-division multiplexing base r-butterfly calculation unit completes the FFT calculation of the secondary data block

In the step (b3) of N-point FFT calculation, it is necessary to perform radix-r FFT calculation on vr secondary data blocks. If each secondary data block uses 1 radix-r butterfly unit for FFT calculation, then vr Level data blocks need vr basic r butterfly units to realize parallel computation. However, since the base-r butterfly unit adopts the parallel pipeline computing method, when the base-r butterfly unit calculates a single data block, there will be r-1 in the idle state every r clock cycles, so one butterfly unit can be used for r Perform FFT on N' point data. At this time, the time-division multiplexing of the butterfly unit can be completed only by controlling the start time of each N'-point data fetching. Mark the r operands of the f(f=0,1,...,r-1)th N' point data as Op _f (i)(i=0,1,...,r-1), the memory bus The result after reading and multiplied by the twiddle factor is recorded as Op _f '(i), and the operation data of the r N' point data of the butterfly unit is input in turn, and the calculation result of the butterfly is recorded as Op _f ”(i), and according to The value of f is stored in the corresponding memory, and the processing sequence after adopting the time division multiplexing method is shown in Fig. 4 .

Therefore, in order to improve the resource utilization rate of the system, the present invention uses v radix-r butterfly units to perform radix-r FFT calculations on vr secondary data blocks, wherein r secondary data blocks in each primary data block are time-division multiplexed Use the system to share a base r butterfly computing unit. As shown in Figure 5, the base-r butterfly unit time-division multiplexing system adopted in the present invention includes r serial-to-parallel conversion modules, a first-level gating control unit, a base-r-butterfly calculation unit, a second-level gating control unit, and r parallel-to-serial conversion modules, wherein:

The r serial-to-parallel conversion modules are in one-to-one correspondence with the r secondary data blocks in a primary data block. The r serial-to-parallel conversion modules respectively read data from the memories of the r secondary data blocks to obtain r channels of serial data, wherein each channel of serial data includes data points; then each serial-to-parallel conversion module performs serial-to-parallel conversion on the corresponding serial data, and converts the serial data points are converted into r parallel data, and each parallel data includes data points.

The first-level gating control unit performs a gating operation on the parallel data output by r serial-to-parallel conversion modules, selects the r-way parallel data output by one of the serial-to-parallel conversion modules each time, and then outputs the r-way parallel data to the base r butterfly computing unit.

The radix-r butterfly calculation unit receives the r-channel parallel data gated by the first-stage gating control unit, performs radix-r FFT calculation, and outputs the r-channel parallel calculation results to the second-stage channel gating control unit.

The second-level gating control unit gates among the r parallel-to-serial conversion modules, and outputs the r-way parallel FFT calculation results output by the base r butterfly calculation unit to one of the parallel-to-serial conversion modules, wherein the gating The serial number of the parallel-to-serial conversion module is consistent with the serial number of the serial-to-parallel conversion module gated by the first-level gate control unit.

The r parallel-to-serial conversion modules are in one-to-one correspondence with the r secondary data blocks in one primary data block. The parallel-to-serial conversion module gated by the second-level strobe control unit receives r parallel FFT calculation results, performs parallel-to-serial conversion of 1-way serial data, and stores the serial data in the corresponding secondary data block In the memory, the storage location is consistent with the location where the data is read by the serial-to-parallel conversion module, that is, in-situ storage is realized.

During the above time-division multiplexing calculation process, the data reading and storage methods in each memory are shown in FIG. 6a.

2.2.4. The time-division multiplexing base r-butterfly calculation unit completes the merging of FFT calculation results

In steps (b4)~(b5), X'(k 1 ,n 2 ) is obtained from X"(k' ₁ ,n' ₂ ,n ₂ ), and X'(k _{1 ,n 2 ) is obtained from X'(k 1 , n 2} ) (k), which includes a level of v Point-based r FFT and one-level N-point basis v FFT, that is to say, in step (b4), the basis r FFT calculation is used to combine the FFT calculation results of r secondary data blocks in each primary data block, and in In step (b5), the basic vFFT calculation is used to combine the FFT calculation results of the v primary data blocks. In order to improve calculation efficiency, when combining the above FFT calculation results, a time division multiplexing system as shown in FIG. 5 may also be used.

Among them, in step (b3) for each secondary data block data During point FFT calculation, the processing process of the memory bank is as shown in Figure 6a; in step (b4), when the FFT calculation results of r secondary data blocks in each primary data block are merged by using radix r FFT calculation, The processing process of the memory group is shown in Figure 6b; when the FFT calculation results of r secondary data blocks in each primary data block are combined by using the basic rFFT calculation in step (b5), the processing process of the memory group is as follows Figure 6c shows.

Example:

In this embodiment, four radix-2 butterfly units are used to realize the FFT calculation of 1024 point data, namely: N=1024, r=2, v=4, S=10, Z=2.

According to the processing method of the present invention, the calculation steps are as follows:

(1), input data storage allocation

In this embodiment, eight 128-point dual-port memories are used for input data storage. Wherein, the 8 memories are divided into 4 memory groups, each memory group includes 2 memories, and each memory has 128 storage locations.

Firstly, sequentially address the input 1024-point data, then the binary representation of the address identifier n of the data x(n) is (n ₉ n ₈ …n ₁ n ₀ ) ₂ . Wherein, the nth data is stored in the Ram_Id(n)=(n ₂ )th memory in the Group_Id(n)=(n ₁ n ₀ )th memory group, and the storage address in the memory is (n ₉ n ₈ ... n ₄ n ₃ ) ₂ .

According to the storage allocation method above, the storage situation of 1024 points of data in 8 memories is shown in Table 1.

Table 1 Input data in each memory

(2) Conflict-free address access to realize 8 128-point parallel FFT calculations

After the data is stored in the corresponding memory, the 128-point radix 2FFT processing is started on the data in the 8 memories at the same time. For 128-point base 2FFT, in the 7-level FFT calculation process, the data access address is generated by intercepting the 7-bit binary counter C=(c ₆ c ₅ ...c ₁ c ₀ ) ₂ . Table 2 shows the data access addresses for FFT calculations at all levels.

Using the time-division multiplexing system shown in Figure 5, the data of every two memories shares one radix-2 butterfly computing unit, so that 8 128-point parallel FFT calculations are completed with four radix-2 butterfly computing units, and the entire calculation time It takes 924 clock cycles.

Table 2 The data access address of each memory in FFT calculation at all levels

(3), first-level result synthesis

According to the formula (5), each memory group is calculated with a 256-point radix-2 FFT. Since there are 4 radix-2 butterfly units, and the two operation data of the butterfly are stored in two different memories, so at the same time Can access 8 data simultaneously from 8 memorizers, can finish this calculation with only 128 clock cycles.

(4), second-level result synthesis

Four groups of 256-point data are calculated according to the formula (3) using the first-order basis 4FFT to obtain the FFT result of 1024 points. At this time, the operation data of the butterfly unit belong to different memory banks, so the four operands can be accessed in parallel. Therefore, only 256 clock cycles are required to complete the calculation.

Using the above processing steps, a total of 1308 clock cycles are required for parallel calculation of 1024-point base 2FFT, which can effectively reduce calculation time consumption compared with the prior art.

The above is only a specific embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Any person skilled in the art can easily think of changes or substitutions within the technical scope disclosed in the present invention. All should be covered within the protection scope of the present invention.

The content that is not described in detail in the specification of the present invention belongs to the well-known technology of those skilled in the art.

Claims (3)

1. A parallel fast Fourier transform processing method, characterized in that comprising the steps: (1), carry out first-level data grouping to the received data sequence x(n), n=0, 1, ..., N-1, be about to divide N data into v first-level data blocks, each described Level 1 data blocks include data; wherein, the n _1th data in the n _2th primary data block is x′(n ₁ ,n ₂ )=x(n ₂ v+n ₁ ), n ₂ =0, 1, ..., v-1; N = r ^S , v = r ^Z , Z = 0, 1, ..., S-2, S and r are integers; (2), each first-level data block that step (1) is divided carries out second-level data grouping, is about to divide each first-level data block into r secondary data blocks, and each described second-level data block includes data; wherein, the n' _1th data x"(n' ₁ ,n' ₂ ,n _{2 )} =x' ₍ n' ₂ r+n' ₁ ,n ₂ ), n' ₂ =0, 1, ..., r-1, n ₂ =0, 1, ..., v-1; (3), for each secondary data block data Point FFT calculation; wherein the n'th ₂ secondary data blocks divided by n' ₂ primary data blocks The FFT calculation result of each data is in, n' ₂ =0, 1, ..., r-1, n ₂ =0, 1, ..., v-1, Using v base-r butterfly units to perform base-r FFT calculations on vr secondary data blocks, r secondary data blocks in each first-level data block share one base-r butterfly calculation unit through a time-division multiplexing system; The time-division multiplexing system includes r serial-to-parallel conversion modules, a first-level gating control unit, a base r butterfly calculation unit, a second-level gating control unit, and r parallel-to-serial conversion modules, wherein: r serial-to-parallel conversion modules: one-to-one correspondence with r secondary data blocks in a primary data block; read data from the memories of r secondary data blocks respectively to obtain r channels of serial data, wherein each channel Serial data includes data points; then each serial-to-parallel conversion module performs serial-to-parallel conversion on the corresponding serial data, and converts the serial data points are converted into r parallel data, and each parallel data includes data points; The first-level gating control unit: performs gating operation on the parallel data output by r serial-to-parallel conversion modules, selects the r-way parallel data output by one of the serial-to-parallel conversion modules each time, and then transfers the r-way parallel data output to the base r butterfly computing unit; Base-r butterfly calculation unit: receive r-channel parallel data to perform base-r FFT calculation, and output r-channel parallel calculation results to the second-stage channel gating control unit; The second-level gating control unit: gating among r parallel-to-serial conversion modules, outputting the received r parallel FFT calculation results to one of the parallel-to-serial conversion modules, and the sequence number of the selected parallel-to-serial conversion module is the same as The serial numbers of the serial-to-parallel conversion modules gated by the first-level strobe control unit are the same; r parallel-serial conversion modules: one-to-one correspondence with r secondary data blocks in a first-level data block; the parallel-serial conversion module gated by the second-level gating control unit receives r parallel FFT calculation results, Perform parallel-to-serial conversion of 1-way serial data, store the serial data in the memory of the corresponding secondary data block, the storage location is consistent with the location where the serial-to-parallel conversion module reads the data, that is, realize in-situ storage; (4), the FFT calculation results of r secondary data blocks in each primary data block are merged to obtain the FFT calculation results of each primary data block; wherein, in the n ₂ primary data blocks The FFT calculation result of the data is in, n ₂ =0, 1, . . . , v-1, (5) Merge the FFT calculation results of v first-level data blocks to obtain the N-point FFT calculation results of the data sequence x(n) Wherein, k=0, 1, ..., N-1, W _N =e ^-j2π/N . 2. a kind of parallel fast Fourier transform processing method according to claim 1, is characterized in that: in step (2), adopt vr The dual-port memory of point stores the data of vr secondary data blocks; the vr dual-port memory is divided into v memory groups, corresponding to v primary data blocks; each of the memory groups includes r dual-port Memory, corresponding to r secondary data blocks in one primary data block; wherein an S-bit r-ary counter is used to obtain the storage address of each data in the sequence x(n), that is, to determine the The nth data is stored in the storage address serial number Add_ID (n) in the Ram_Id (n) memory in the Group_Id (n) memory group, n=0, 1, ..., N-1, and the specific implementation method is as follows: The r-ary value of the count value n of the counter is (a _S-1 a _S-2 ...a _Z+1 a _Z a _Z-1 ...a ₁ a ₀ ) _r , where a ₀ to a _S-1 are The r-ary value of the 1st to S-th digits of the r-ary value ranges from 0 to r-1, and the r-ary value of the memory group serial number Group_Id(n) is (a _Z-1 … a ₁ a ₀ ) _r , the r-ary value of the memory serial number Ram_Id(n) is (a _Z ) _r , the r-ary value of the storage address serial number Add_ID(n) is (a _S-1 a _S-2 …a _{Z +1} ) _r . 3. a kind of parallel Fast Fourier Transform processing method according to claim 1, is characterized in that: in step (3), adopt radix r FFT to calculate and obtain in each secondary data block The FFT result of data; Adopt base rFFT calculation in step (4) to merge the FFT calculation results of r secondary data blocks in each primary data block; Adopt base v FFT calculation in step (5) to The FFT calculation results of the v first-level data blocks are combined.