JPH0230062B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to an FFT calculation device that performs fast Fourier transform (hereinafter abbreviated as FFT). Traditionally, general-purpose pipelined array processors (Array Processor, abbreviated as AP)
In this case, there is usually a time delay in data memory access, which increases the time delay in completing additions, subtractions, and multiplications. There is a delay in reading (or writing) input (or output) data for calculations from storage memory,
Furthermore, in FFT calculations that require continuous reading or writing of large amounts of data, the calculation (processing) capability is limited by the speed of memory and data exchange. For example, the time required to read and write two points of complex data is 4 cycles for reading and 4 cycles for writing, because each point is represented by two data, a real part and an imaginary part. A total of 8 cycles are required. In this case, even if the start of 4 multiplications and the start of 6 additions can be executed in 6 cycles by parallel processing of multiplication and addition, the number of memory accesses of 8 cycles determines the speed of the FFT operation. i.e.
There was a problem that the FFT calculation speed was limited by the number of memory accesses. In view of these points, the present invention aims to provide two minimum-capacity, high-speed access memories in addition to a low-speed, large-capacity memory for storing FFT input/output data. An object of the present invention is to provide an FFT device that can shorten the time required for calculation by skillfully controlling input and output memory addresses. The present invention will be explained in detail below using the drawings. First, the algorithm of the method of the present invention will be explained. This is a diagram showing the signal flow of the method of the present invention in FIG. 1, in which the number of data is 16, the DIT method, the in-place method,
The calculation method and data flow in the example of normal input order are shown in Figure 2.
The details of the signal flow are shown in examples of ND, DIT method, in-place method, and normal input order. The basics of the FFT algorithm in the method of the present invention are as follows. This FFT is
BaSe2FFT, number of complex data N, in-
These are the cases of the place method, the input data normal order, and the DIT method, and the calculation procedure is divided into the cases of N=2 ² 〓 and N=2 ² 〓 ⁺¹ as follows. (a) In the case of N=2 ² 〓 (1) Let N=2 ² 〓, ND=N/2, l=1. (2) Let K=0 and M=0. (3) k=K, K+1, K+2,..., K+ND-
1, perform the following calculation.

[Table] (4) M=M+2, K=K+2・ND, K<
If N, return to (3). (5) ND=ND/4, l=l+1, l≦γ
Then return to (2). (6) For k=0, 1,...,N-1 (output data array normalization) q=Bit Reverse {k} If q>k then G=C _l (q) C _l (q)= C _l (k)} (6) C _l (k)=G (b) In the case of N=2 ² 〓 ⁺¹ (1) Set N=2 ² 〓 ⁺¹ , ND=N/2, l=1 . (2) Let K=0 and M=0. (3) k=K, K+1, K+2,..., K+ND-
1, perform the following calculation.

【table】

[Table] (4) M=M+2, K=K+2・ND, K<
If N, return to (3). (5) ND=ND/4, l=l+1, l≦γ
Then return to (2). (6) Perform the following calculation for k=0, 1, 2,..., N/2-1. C _l (2k)=C _l (2k) +C _l (2k+1)・W(2k) (5-1) C _l (2k+1)=C _l (2k) −C _l (2k+1)・W(2k) (5 -2) (7) For k=0, 1, 2,..., N-1 (data array normalization) q=Bit Reverse {k} If q>k then G=C _l (q) C _l ( q) = C _l (k) C _l (k) = G In addition, the method of the present invention extracts one point of data from each small block obtained by dividing each block into four.
It is configured to process two loops of normal FFT on this four-point data at one time, reducing the number of large-capacity memory accesses by half. Figures 3 and 4 are diagrams showing the relationship between loops, blocks, and small blocks. The case where the data consisting of is continuous is shown. FIG. 5 shows an example of an FFT setup for implementing the algorithm described above. In FIG. 5, RF1 and RF2 are register files consisting of a plurality of registers, which store read addresses and write addresses of the large capacity memory MS.
Both RI1 and RI2 are registers that provide changes in the read address and changes in the storage address. SEL1 and SEL2 are selectors that select either input a ₁ or a ₂ , and AD1 and AD2 are adders that add addresses. RF1 in AD1
Adds both outputs of SEL1 and SEL1, and sends the result to MS address register MA via selector SEL3.
give to The output of AD1 is fed back to the corresponding register of RF1 and becomes the next address data.
AD2 adds both RF2 and SEL2 outputs,
Give the results to MA via SEL3. The output of AD2 is stored in the corresponding register of RF2 and becomes the next address data. register file RF
1, RF2, register RI1, RI2, selector
SEL1, SEL2, SEL3, adders AD1, AD2,
An address register MA etc. constitutes means for controlling the address group. HSM1 and HMS2 are high-speed, small-capacity memories.
It is used to store read data from the MS, to store intermediate results of FFT calculations, and to store FFT calculation results. HSMs 1 and 2 are capable of simultaneous data read/write operations in the minimum cycle time (read addresses and write addresses do not necessarily match). TBM is a constant of FFT operation (W(M)
data memory (RAM, etc.)
is used). ADD is an adder that can add two inputs A1 and A2, and give the result to each input of HSM1, HSM2, and A2 of ADD. For the A1 input of ADD,
One of the outputs of HSM1, HSM2, and MUL is selected. A2 input of ADD has HSM1, HSM
2. One of the outputs of ADD itself is selected.
MUL is a multiplier that multiplies two inputs M1 and M2 and can give the result to each input of A1 of HSM1, HSM2, and ADD. The M1 input of MUL has
The output of TBM is given. Either of the outputs of HSM1 and HSM2 is selected for the M2 input of MUL. IF is an interface section with external devices (CPU, data collection device, etc.). Data, address information, control signals, etc. are exchanged. Data transfer with the outside is performed between the MS and the external device. CS is a memory that stores microprograms for FFT calculations, and CTL is a part that centrally controls the organic operations of each device based on the microprograms. MS read and write operations are serial, but ADD, MUL, HSM1/HSM
The read and write operations of 2, the TBM read operations, etc. can be performed in parallel. The operation of the present invention in such a configuration will be described next. (1) Preparation for each loop processing Store the FFT input data in the MS.
RF1 and RF2 are register files each consisting of 8 registers, and the initial value RF of each register is
1(j), RF2(j) (j=0, 1, . . . , 7) are set as follows (RF1 is for reading and RF2 is for writing). RBA: First application address of real number data IBA: Imaginary number data 〃 ND: Half the number of data in the block Also, set the initial values of RI1 and RI2 as follows (example when real number data and imaginary number data are separated) ). RI1=1 (9-1) RI2=3/2ND+1 (9-2) W(M)=W(o)=1 (10) (2) To HSM1 (RBA, IBA); (RBA+ND/2, IBA+ND/ 2); Write 4 complex number data corresponding to (MS→
HSM1). (3) Write the next 4 complex number data from MS to HSM2 (MS→HSM2). At the same time, perform FFT calculation on HSM1 (HSM
1 → HSM1; Section (3) of algorithm (a)). (4) Process the following operations in parallel. (i) Store the 4complex data of HSM1 in the address RF2(j) + RI2 if it is the first data of the block, or RF2(j) + RI1 if it is not the first data of the block (HSM1 → MS), and then store it at the address RF2(j)+RI1 if it is the first data of the block. If it is data, read 4complex data of RF1(j) + RI2 into HSM1 if it is other than the first data of the block (MS
→HSM1). (ii) Perform FFT operation on 4complex data of HSM2 (HSM2→HSM2; Algorithm (a) (3)
section). (5) Process the following operations in parallel. (i) Store the 4complex data of HSM2 in the address RF2(j) + RI2 if it is the first data of the block, or RF2(j) + RI1 if it is not the first data of the block (HSM2 → MS), and then store it at the address RF2(j)+RI1 if it is the first data of the block. If it is data, read 4complex data of RF1(j) + RI2, otherwise read 4complex data of RF1(j) + RI1 to HSM2 (MS
→HSM2). (ii) Perform FFT operation on 4complex data of HSM1 (HSM1→HSM1; Algorithm (a) (3)
section). (6) The above (4) until the end of all FFT calculations for one block.
Repeat (5), and after completing this calculation process, M=M+
2, and if the processing of all blocks in this loop is not completed, the operation returns to step (5) again. (7) Store 4Complex data of HSM2 in MS. After completing one loop of processing, set ND=ND/4,
If all loop processing is not completed, return to (1). The above (1) to (7) are examples of algorithms for realizing high-speed FFT operations exceeding the memory access limit using the apparatus shown in FIG. Control of data processing times (1 block ND times),
Control of the number of loops, etc. is performed by CTL using the CS microprogram. Register files RF1 and RF2 have 4 points and 8
It stores the Read Address of Write Address of the data and updates the contents of the register to the next reference address after referencing it. RI2 is used when calculating the address of the first data of the block (Read
Add./Write Add.), RI1 is for other data.
It is controlled to be used when calculating an address. Note that the present invention is not limited to the above-described embodiments, and can be expanded and modified as listed below. (1) Divide one block into 8 parts (16, 32, ... divisions),
Expansion and modification of algorithms for FFT calculation devices, etc. using 3-loop (4, 5, ... loop) batch processing algorithms (2) Unification or separation of lines and buses for control signals, data, addresses, etc., and separate separation between devices Connection, bonding, wiring. (3) When multiple adders (addition/subtraction units) are used (such as those with Butterfly arithmetic units) or when multiple multipliers are used to speed up processing (4) Sharing or substitution of equipment (i) AD1 and AD2 (SEL3 is not required) (ii) TBM is shared with HSM1 or HSM2 (iii) When CTL is substituted without CS (5) Combining and combining devices (i) (SEL3,) MA is included in MS ((SEL3,)
Case in which MA is apparently absent) (ii) SEL1 is included in AD1 (iii) SEL2 is included in AD2 (iv) Combination of RI1 and RI2 (SEL1 and SEL2 unnecessary) (v) Combination of RF1 and RF2 (6) Others ● When there are two each of RI1 and RI2 ●When RI1 and RI2 are ROM (multiple) ●When there are multiple RI1 and RI2 ●When TBM is ROM ●The number of registers for RF1 and RF2 is not limited to 8 As described above, according to the present invention, it is possible to reduce memory access to a large-capacity memory, and to perform both arithmetic operations on a data group and transfer of a data group in succession, thereby reducing the number of memory accesses to a large-capacity memory. High-speed FFT operations exceeding memory access limits can be achieved. Furthermore, it is possible to realize a simple and highly applicable FFT in a general-purpose array processor device without using expensive devices such as a butterfly arithmetic unit or a large-capacity high-speed memory.

[Brief explanation of drawings]

Figures 1 and 2 are diagrams showing the signal flow of the present invention, Figures 3 and 4 are diagrams showing the relationship between loops, blocks, and small blocks, and Figure 5 is an illustration of the FFT calculation device of the present invention. FIG. 2 is a main part configuration diagram showing an example. RF1, RF2...Register file, RI1,
RI2...Register, SEL1, SEL2, SEL3...
...Selector, AD1, AD2...Adder, MA...
...Address register, MS...Large capacity memory, HSM1, HSM2...High speed small capacity memory,
TBM...Data memory, ADD...Adder,
MUL...multiplier, IF...interface.

Claims (1)

[Claims] 1 A means for controlling an input data address group and an output data address group in a large-capacity memory, and a plurality of high-speed memories used as buffers, dividing the input data block in the large-capacity memory, and further Divide the block into small blocks,
This is a fast Fourier transform calculation device that performs FFT operations between data groups retrieved from each small block group to high-speed memory, and controls input data address groups and output data address groups of small blocks in large capacity memory. However, one high-speed memory is used to perform multiple loops of FFT calculations between the current data group, and the previous FFT calculation results are stored from another high-speed memory to large-capacity memory, and the next data group is processed faster than the large-capacity memory. A fast Fourier transform calculation device that uses the FFT calculation method to perform read operations to memory in parallel.