JPS6237776A - Fast Fourier transform device - Google Patents

Abstract

PURPOSE:To attain an FFT (fast Flurier transformation) calculation at a high speed by reversing the address of a memory for each bit without rearranging data and therefore giving highly orderly accesses to data at a high speed together with a simple access given to a wait table. CONSTITUTION:An address counter 1 and a 1-bit reversing circuit 2 are controlled by a control/arithmetic circuit 6 of an FFT arithmetic unit. Then both the lowest and highest bits of the address of the data stored in time series into a memory 3 are reversed. The data are read out of the memory 3 and sent to a wait counter 4 and the circuit 6 performs a butterfly calculation to store the result of this operation in the memory 3. Furthermore the circuit 6 performs a butterfly calculation to store the result of this operation in the memory 3. Furthermore the circuit 6 performs an FFT calculation and stores data in a memory 8 when all bits of the data address are reversed. Both control/ arithmetic circuits 6 and 9 are connected with each other in a butterfly form by a data bus via the 1st and 2nd memories 3 and 8. Then the circuit 9 performs the next processing based on the data of the memory 8. Thus an FFT calculation can be carried out at a high speed.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention is directed to fast Fourier transform (Fast Fourier transform).
rTransform (hereinafter abbreviated as FFT) device.

[Conventional technology]

A conventional FFT device reverses all bits of the memory address where the data is stored and rearranges the order of the data, and then accesses the data bear of the butterfly operation using the address generated by the address generator according to a predetermined algorithm. As a result, the FFT calculation results are arranged in good order.

Here, the butterfly operation is given by the following equation as shown in FIG.

X(i)=Work(i)+w-"・χ0) X(i), Y(j): two-weight vector for complex number W- Figure 4(a) is an example of the algorithm of a conventional FFT device (
Figure 4 (b) shows the case where the number of data N = 23 = 8)
is its weight hector W′1. W6゜W-“・,w”
, w'j, w"7 , W", WO, -Wo.

In the vector diagram of -W4, -W'7, -W'3, the numbers within 0 yen indicate the data completion.

After reversing all bits of the memory address and rearranging the data order as 0.4, 2.6, 1.5.3.7, step 1.11. According to III and the algorithm, when the butterfly calculation data is accessed using the address generated by the address generator and the calculation proceeds, the final order is 0.1, 2.3°, 4.5, 6.7. F well lined up
FT calculation results are obtained.

(Problem to be solved by the invention) In the above-mentioned conventional FFT device, it takes a long time to rearrange data by 1-oversing all bits of the data address, generate data addresses and wait addresses by the address generator in the calculation process, and access. Moreover, there is a problem that the circuit becomes sloppy.

An object of the present invention is to provide an FF that is fast and suitable for real-time processing.
The purpose of this invention is to provide a T device.

[Means for solving problems]

The FFT torpedo of the present invention includes a first device that reverses the least significant bit and the most significant bit of an address of a first memory in which data is stored in time series, accesses the data, and performs a butterfly operation; Is it the calculation result of the first memory?
A second memory is provided in which all bits of the address are reversed and stored in accordance with the number of pieces of data, and the second memory is connected to the first device via the first and second memories in a pipeline manner. It has a second device that performs the next process of the butterfly operation based on the data in the memory.

[Effect]

By performing one-bit reversal in this way, the circuit configuration becomes simpler than when performing all-bit reversal as in the past, and data access and therefore calculations become faster. A first device that performs IFFT, absolute value/phase calculation, spectrum calculation, etc. is divided into a first device that performs IFFT, absolute value/phase calculation, spectrum calculation, etc., and these devices are connected in a pipeline manner (referring to multiplexing of processing). As a result, each device can process the data from the pre-processing after completing its own processing and passing the data to the other device, thereby realizing real-time processing.

〔Example〕

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 shows an example of FFT snow treatment of the present invention (number of data N=
8), and FIG. 2 is a diagram showing the calculation process of the butterfly calculation.

Address counter 1 (3 dots AO, AI, A2) is a first-stage octal counter that is incremented every time data is accessed (to read/line two pieces of complex data in one butterfly operation) and an octal counter. The memory 3 consists of a binary counter (to read/write data separately for the real part and imaginary part) that is incremented by a carry of .Data: 1:(i)(l・0...
...27) Or, the weight table 5 contains weight vectors w-3, w-2, W-1°Wo, WI,
VJ2 and W3 are stored respectively. The 1-bit reverse circuit 2 performs bit conversion of the output of the address counter 1 (bits AO and A2 in step E, bits AO and AI in step 11).

The wait counter 4 generates the address of the wait table 5 by counting at the rising edge of the bit exchanged with the least significant bit AO of the address counter 1 (A2°AI, 80 order). Note that the least significant bit of the weight counter 4 is connected to the most significant bit of the weight table 5, and the address of the weight table 5 is obtained by reversing the output of the weight counter 4 by all bits. In this way, the required weight vectors are automatically obtained. control/arithmetic circuit 6 is an address counter] and 1
It controls the bit reverse circuit 2, takes out data from the memory 3, performs a butterfly operation, and stores the result in the memory 3. Roughly speaking, after the FFT operation is completed, the control/arithmetic circuit 6 reverses all bits of the data remaining in the memory 3 in the order in which all bits were reversed, rearranges them in the correct order, and transfers them to the memory 8. Control/arithmetic circuit 9
is the multiplexer 7 for the data transferred to the memory 8.
can be accessed via
Processing such as calculation of power (a) is performed.

Next, the operation of this embodiment will be explained. Tables 1, 2, and 3 show address counters 1.
This table shows the output of the 1-bit reverse circuit 2, accessed data, and weight vectors.

Table 1 Table 2 Table 3 In step ■, bits AO and A of address counter 1
2 is reversed (converted) by the 1 pit repart circuit 2,
Data pairs in memory 3 are
) are accessed in order, and at this time, the weight vector W0 of the weight table 5 is accessed by the weight counter 4.
is constantly accessed, a butterfly operation is performed on each data pair in the control/arithmetic circuit 6, and the result is stored in the memory 3.
is stored in

In step II, bits AO and A1 of address counter 1 are reversed by 1 bit reverse circuit 2, and data bits (0) and χ(2), χ(1) and χ of memory 3 are reversed.
(3), x (4) and x (6), χ (5) and χ (7)
are accessed in sequence, and after accessing data (3), the weight counter 4 is incremented and the weight vector W"2 of the weight table 5 is accessed. Butterfly operations are performed on each data pair in the same way as before, and the result is It is stored in memory 3.

In step m, which is the final step, bit reversal is performed and adjacent data pairs t(0) and χ
(1), χ (2) and k (3), x (5) and k (6)
and χ(7) are not accessed in order, while the weight vectors in weight table 5 are first accessed by WO, data x(1)
After accessing W-2, after accessing χ(3), weight counter 4 is incremented, W-1, then W-
A is accessed in order, a butterfly operation is performed on adjacent data pairs, and the results are stored in the memory 3 in the order in which all bits are reversed to 1.

After this, all bits of the memo 1 and 3 (the result of the FFT operation completed) are reversed by the control/arithmetic circuit 6, rearranged in the correct order, and transferred to the memory 8 (memory 8), where they are processed or received by the control/arithmetic circuit 9. The control/arithmetic circuit 9 uses the FFT results stored in the memory 8 as data to perform processing such as IFFT, absolute value/phase calculation, and spectrum calculation.

By the way, when the number of data N (=2L) increases, the bit exchange in the calculation step is 2L in order from the upper bit.
There is one step in the order of -1, 21-2, . . . 20, and each step is completed by performing N/2 butterfly calculations. Furthermore, when data in the memory 3 is transferred to the memory 8, all bits of the data address may be reversed by the control/arithmetic circuit 6.

〔Effect of the invention〕

As explained above, the present invention allows data to be accessed quickly and in an orderly manner by reversing memory addresses by one bit without prior data rearrangement as in the prior art, and at the same time allows easy access to the weight table. U
FFT calculations can be performed at high speed, and the device can be
By decoupling the device that performs the FT operation from the device that performs the next process, and connecting these devices in a pipeline to receive and pass data, it is possible to perform high-speed real-time processing.

[Brief explanation of the drawing]

Fig. 1 is a diagram showing a major embodiment of the fast Fourier transform device of the present invention, Fig. 2 is a diagram showing the process of butterfly calculation in the high speed No. Figure 4 (a) is a diagram showing the process of butterfly operation in a conventional fast Fourier transform device, and Figure 4 (b) is a vector diagram of the weight vector. 1...Address counter, 2...Bit reverse circuit, 3.8...Memory note, 4...Wait counter, 5...Wait table, 6.9...Control. Arithmetic circuit, 7...Multiplexer.

Claims (1)

[Scope of Claims] A first device that accesses the data and performs a butterfly operation by reversing the least significant bit and the most significant bit of an address of a first memory in which data is stored in time series; A second memory is provided in which the calculation result of the memory is stored with the address reversed in all bits according to the number of pieces of data, and is communicated with the first device via the first and second memories in a pipeline manner. A fast Fourier transform device, which is connected to a second memory and has a second device that performs subsequent processing of the butterfly operation using data in a second memory.