JPH08137832A - Butterfly arithmetic circuit and fast Fourier transform device using the same circuit - Google Patents

Abstract

(57) [Summary] [Object] The present invention relates to a butterfly operation circuit required when performing an operation using an FFT, and an FFT device configured by using the circuit. The Y side can be arbitrarily switched with a simple structure, and FF
An object of the present invention is to reliably obtain a frequency component on the desired side as a T output and to reliably perform correlation processing on FFT results at multiple points. [Structure] Butterfly operation circuit 1 constituting an FFT device
A multiplication circuit 2 for multiplying the input data y by the twiddle factor W ^k
And a pair of addition / subtraction circuits 3A and 3B for performing either one of addition processing and subtraction processing on the multiplication result W ^k · y and the input data x, and the pair of addition / subtraction circuit 3
A switching circuit 4 that can selectively switch between A and 3B that performs addition processing and one that performs subtraction processing is configured.

Description

Detailed Description of the Invention

(Table of Contents) Industrial Application Field of the Prior Art (FIGS. 24 to 29) Problems to be Solved by the Invention (FIGS. 24, 25, 2)
9) Means for Solving the Problem (FIG. 1) Operation (FIG. 1) Embodiment (a) Description of First Embodiment (FIGS. 2 to 4) (b) Description of Second Embodiment (FIGS. 5 and 5) 6) (c) Description of the third embodiment (FIG. 7) (d) Description of the fourth embodiment (FIGS. 8 and 9) (e) Description of the fifth embodiment (FIGS. 10 to 23)

[0002]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a butterfly operation circuit necessary for performing an operation using a fast Fourier transform [hereinafter referred to as FFT (Fast Fourier Transform)],
Also, the present invention relates to a fast Fourier transform device configured using the butterfly operation circuit. According to this type of device,
The amount of calculation can be greatly reduced as compared with a device in which a normal discrete Fourier transform algorithm is adopted, and therefore, it is possible to significantly speed up the processing in a signal processing system, a data analysis system, a linear system, etc. .

[0003]

2. Description of the Related Art FFT is originally a mathematically improved technique for reducing the number of enormous multiplications and additions and subtractions required for a discrete Fourier transform (DFT) and its inverse transform (IDFT). In recent years, digital computers (DS
P) has become faster and microprocessors have become widespread, and various techniques and devices have been proposed for performing FFT, which is the mainstream of digital signal analysis, in the field of analysis processing of voice, image, radio waves, and the like.

Generally, FFT can be performed by repeatedly performing the butterfly operation as a basic operation. As hardware for realizing this FFT, one basic stage composed of a butterfly operation circuit and a data rearrangement circuit is used, and the basic stages are connected in series by an appropriate number of stages in a predetermined relation. (Pipeline) type (described later in FIGS. 24 to 27)
Also known is a structure in which the series type front stage part and the parallel type rear stage part are combined (described later in FIGS. 28 and 29).

As a serial type FFT device, for example, an FFT with a radix r = 2 and the number of sampled data (the number of FFT points)
An example of the case where N = 8 is shown in FIG. In this case, as shown in FIG. 24, three basic stages (basic circuits) 1
6-1, 16-2, 16-3 are connected in series.
Here, the basic stage number M is given as M = log _r N = log ₂ 8 = 3 based on the radix r and the FFT score N.

Each basic stage 16-1, 16-2, 16
-3, as shown in FIG. 25, includes a data rearrangement circuit 10 and a butterfly operation circuit 11. The data rearrangement circuit 10 rearranges the data input from the outside according to the order according to the operation, and then the butterfly operation circuit 11
Is output in units of two. The butterfly operation circuit 11 is composed of a twist coefficient multiplication unit 12, an addition circuit 13, and a subtraction circuit 14. Twist coefficient multiplication unit 1
Reference numeral 2 is for multiplying one of the data from the data rearrangement circuit 10 by a twist coefficient (twiddle factor) W ^k. Twist coefficient memory 1 for storing W ^k
2b and.

Then, for example, a continuous time signal as shown in FIG. 26 is sampled at a predetermined sampling interval, and its data A0, A1, A2, ... Are sent to the first basic stage 16-1 as a single stream data string. input.
At this time, the number of data to be sampled is 8 (N = 8).
In the point FFT, there are eight points A0 to A7. 27 is the same as FIG.
4, for explaining the FFT algorithm by the 8-point FFT device shown in FIG. 25. As shown in FIG. 27, in the first basic stage 16-1, A0
2 data sets (A0, A4) among 8 data sets from A7 to A7,
(A1, A5), (A2, A6), (A3, A7) are rearranged by the data rearrangement circuit 10 and input to the butterfly operation circuit 11 as (x, y).

The butterfly operation circuit 11 performs a butterfly operation (crossing operation) on the input data (x, y). That is, the data y by the multiplication unit 12
An appropriate twist coefficient (twiddle factor) W ^k is multiplied for each time, and the result of adding the multiplication result W ^k · y from the multiplication unit 12 to the input data x by the adder circuit 13 is data X (= x + W ^k · y).
In addition, the subtraction circuit 14 subtracts the multiplication result W ^k · y from the multiplication unit 12 from the input data x and outputs the result as data Y (= x−W ^k · y).

The first-stage basic scan calculated in this way
Calculation result A from tage 16-1₁0 (= A0 + W^k・ A
4), A₁1 (= A1 + W^k・ A5), ..., A₁4 (= A0
-W ^k・ A4), A₁5 (= A1-W^k・ A5), ..., A
₁7 (= A3-W^k・ A7) is the second basic stage 1
Input to 6-2. This second basic stage 16-
In 2, A₁0 ~ A₁2 of 7 data sets (A
₁0, A₁2), (A₁1, A₁3), (A₁4, A₁6), (A
₁5, A₁7) is rearranged by the data rearrangement circuit 10.
The same butterfly as above is input to the butterfly operation circuit 11.
The fly operation is performed and the operation result A₂0 ~ A₂7 is the third
It is input to the basic stage 16-3 of the stage.

Furthermore, in the basic stage 16-3 of the third stage, the two data sets of the _{A 2 0~A 2 7 (A 2} 0,
_{A 2 1), (A 2} 2, A 2 3), (A 2 4, A 2 5), (A 2 6, A
₂ 7) are inputted sorted by the data shuffle play circuit 10 to the butterfly operation circuit 11, similar to the butterfly operation described above is performed, the operation result A ₃ 0 to A ₃ 7 is output as the FFT result. It should be noted that the numbers 1 to 3 attached to the lower right of the code "A" indicating the data indicate from which basic stage the data is output.

That is, each data set has a basic stage 16
-1, 16-2, 16-3 in this order N / 2, N / 2 ² , N
Data that are separated by ^2/3 are selected as a pair. Since the example described above is an 8-point FFT, the number of basic stages is three, but if the number of FFT points N is 2 ^m , butterfly operation is performed until data separated by one is selected as a data set. That is, by performing the butterfly operation of m (= log ₂ 2 ^m ) stages, the N-point FFT result is obtained.

Next, an example of an FFT device in which a series type front stage part and a parallel type rear stage part are combined will be described with reference to FIG. The FFT device shown in FIG.
It is composed of a T circuit 51A and a post-stage parallel type FFT circuit 51B, and performs FFT with a radix r = 2 and an FFT score N = 32. Then, the serial FFT circuit 51A is
Similar to FIG. 24, three basic stages 16-1 to 16-3
4 series circuits 52-1 to 52-4 connected in series are arranged in parallel. That is, each of the series circuits 52-1 to 52-4 is configured to perform FFT with the radix r = 2 and the FFT score N = 8, similarly to the FFT device shown in FIG. In addition, each of the basic stages 16-1 to 16-1
6-3 has the same configuration as that described above with reference to FIG.

In the parallel type FFT circuit 51B, two sets of parallel circuits 53A and 53B are arranged in parallel, and
It is configured to include four selectors (data selection units) 56-1 to 56-4. The parallel circuit 53A is a serial type F
The X output from each of the series circuits 52-1 to 52-4 of the FT circuit 51A is input and the radix r = 2 and the FFT score N = 4 F
For performing FT, four butterfly operation circuits 5 having the same configuration as the butterfly operation circuit 11 described above with reference to FIG.
4-1, 54-2, 55-1 and 55-2 are arranged in the form of 2 rows and 2 columns. The X output and the Y output from the butterfly operation circuit 54-1 of the fourth stage are input to the two butterfly operation circuits 55-1 and 55-2 of the fifth stage, respectively, and the butterfly operation circuit 54- of the fourth stage 54- Two
The X output and the Y output from are also input to the two butterfly operation circuits 55-1 and 55-2 in the fifth stage, respectively.

The parallel circuit 53B is a serial FFT circuit 51.
The Y output from each of the A series circuits 52-1 to 52-4 is input to perform the FFT with the radix r = 2 and the FFT score N = 4, and four butterfly operation circuits 54-3 and 54-
4, 55-3, 55-4 are arranged in the form of 2 rows and 2 columns. These butterfly operation circuits 54-
3, 54-4, 55-3, 55-4 are also butterfly operation circuits 54-1, 54-2, 5 of the parallel circuit 53A described above.
It is connected in the same manner as 5-1 and 55-2.

Then, the fifth stage butterfly operation circuit 55
Any one of the X output or the Y output from -1 to 55-4 is a selector (data selection unit) 56-1 to 56-4.
And is output as the FFT result. When performing FFT on the data A00, A01, ..., A31 of 32 points of a single stream by the FFT device having such a configuration, first, these data are grouped into four 8-point data groups A00, A04, A08, … 、
A28; A01, A05, A09, ..., A29; A02, A06, A1
0, ..., A30; A03, A07, A11, ..., A31, and for each data group, the serial type FFT of the preceding stage, respectively.
Eight-point FFT is performed by each series circuit 52-1 to 52-4 (three basic stages 16-1 to 16-3) of the circuit 51A.

[0016] After this, X output group from the basic stage 16-3 in the series circuit _{52-1 A 3 00, A 3 08} , A 3 16, A 3 24
And X output group A ₃ 02 from the base stage 16-3 of the series circuit 52-3, and _{A 3 10, A 3 18,} A 3 26 is a parallel circuit 53
X output group input to the butterfly operation circuit 54-1 of A and from the basic stage 16-3 of the series circuit 52-2
X output groups A ₃ 03, A ₃ 11, A ₃ 19, from A ₃ 01, A ₃ 09, A ₃ 17, A ₃ 25 and basic stage 16-3 of series circuit 52-4.
And A ₃ 27 is, the butterfly operation circuit of the parallel circuit 53A 5 4-
Entered in 2.

[0017] Similarly, Y output group A ₃ 04 from the base stage 16-3 of the series circuit _{52-1, A 3 12, A 3} 20, A 3 28
And the Y output group _{A 3 06, A 3 14,} A 3 22, A 3 30 from the base stage 16-3 of the series circuit 52-3, the parallel circuit 53
B output from the basic stage 16-3 of the series circuit 52-2, which is input to the B butterfly calculation circuit 54-3.
A ₃ 05, A ₃ 13, A ₃ 21, A ₃ 29 and Y output groups from the basic stage 16-3 of the series circuit 52-4 A ₃ 07, A ₃ 15, A ₃ 23,
A ₃ 31 is the butterfly operation circuit 54- of the parallel circuit 53B.
4 is input.

And, these parallel circuits 53A, 53B
FFT of 4 points is performed by the selectors 56-1 to 56-
-4, for example, the fifth stage butterfly operation circuit 55
By selecting the X output of -1 to 55-4, the lower half side of the FFT output (0 to N / 2-1 at the frequency index), that is, A ₅
00, A ₅ 08, A ₅ 16, A ₅ 24; A ₅ 02, A ₅ 10, A ₅ 18, A ₅ 26; A ₅ 0
_{4, A 5 12, A 5} 20, A 5 28; A 5 06, A 5 14, A 5 22, A 5 30 is output as a final FFT results. Here, the numbers 3, 5 and the like attached to the lower right of the code A indicating the data indicate the output of the data (basic stage or butterfly operation circuit). Further, the number attached to the lower right subscript of the symbol A is a sequential number indicating the data sampling order.

As described above, by combining the serial type FFT circuit 51A and the parallel type FFT circuit 1B, it becomes possible to flexibly determine the parallel degree of the Fourier transform in the relation between the number N of input data and the processing speed. , Therefore,
It is possible to reduce the scale of the hardware required for the processing while ensuring high-speed processing. In addition, in the above-mentioned example, the case of single stream 32-point data has been described, but the multi-stream mode (2, 4,
FFT can be similarly performed on 32 points of data in 8 and 16 stream modes. In that case,
Assuming that the number of streams is I, [5-log ₂ I] basic stages 16-1 to 16-3, a butterfly operation circuit 54-
The FFT is performed using 1 to 54-4 and 55-1 to 55-4, and the circuit on the subsequent stage side bypasses the data and outputs the FFT result.

For example, FIG. 2 shows the case of the 8-stream mode.
9 shows. In this case, [5-log ₂ 8] = 2, so
The FFT is the first two stages, that is, each series circuit 52-1 to 5-5.
2-4 using the basic stages 16-1 and 16-2, and the subsequent basic stages 16-3 and butterfly operation circuits 54-1 to 54-4, 55-1 to 55-
In 4, the data is passed without performing the FFT. Figure 2
9, it is confirmed that “====” described in the blocks of the basic stage 16-3 and the butterfly operation circuits 54-1 to 54-4, 55-1 to 55-4 is in the through operation state. Shows.

As a result, 4-point FFT is applied to each stream for 32-point data in the 8-stream mode. In order to realize such a function, each of the basic stages 16-1 to 16-3 and the butterfly operation circuit 54
Each of -1 to 54-4 and 55-1 to 55-4 usually has a function of bypassing data. Here, in the example shown in FIG. 29, two streams of data A are stored.
0 to A3; E0 to E3 are input to the series circuit 52-1,
Two streams of data B0 to B3; F0 to F3 are input to the serial circuit 52-2, and two streams of data C0 are input.
~ C3; G0 to G3 are input to the series circuit 52-3, and 2
Stream data D0 to D3; H0 to H3 are input to the serial circuit 52-4. It should be noted that data indicated by the same alphabet indicates that the data is in the same stream, and the numbers after each alphabet indicate the data order in the same stream.

Then, by the first two basic stages 16-1 and 16-2 of each series circuit 52-1 to 52-4,
Four-point FFT is performed for each stream. The output from the basic stage _{16-2 A 2 0~A 2 3; E} 2 0~E 2 3; B 2 0~B
_{2 3; F 2 0~F 2 3} ; C 2 0~C 2 3; G 2 0~G 2 3; D 2 0~D
₂ 3; H _{2 0~H 2} 3 as the FFT result, subsequent basic stages 16-3 and the butterfly operation circuit 54-1 to 54
-4, 55-1 to 55-4, selector 56-1
Is output from ~ 56-4.

In FIG. 29, selectors 56-1 and 56-2 are provided.
Selects the X output of the butterfly operation circuits 55-1 and 55-2, so that for the stream data indicated by the symbols "A", "E", "C", and "G", the lower half side of the FFT output ( in frequency index 0 to N / 2-1) that is A ₂ 0, A
₂ 2; E ₂ 0, E ₂ 2; C ₂ 0, C ₂ 2; G ₂ 0, G ₂ 2 are output as final FFT results.

Further, the selectors 56-3 and 56-4 select the Y outputs of the butterfly operation circuits 55-3 and 55-4 so that the symbols "B", "F", "D" and "H" are used. for stream data shown, the upper half side of the FFT output (at frequency index N / 2 ~N-1) that is _{B 2 1, B 2 3;} F
₂ 1, F ₂ 3; D ₂ 1, D ₂ 3; H ₂ 1, H ₂ 3 are the final FFT
It is output as a result.

Here, the numeral 2 attached to the lower right of each code A to H indicating data indicates that the data is output from the second basic stage 16-2. The numbers attached to the lower right subscripts of the respective symbols A to H are sequential numbers indicating the data sampling order.

[0026]

By the way, when a radio telescope is used to observe the same celestial body (radio wave source) from a plurality of locations on the earth, after FFT the signals sampled by the receivers of the radio telescopes, Observation results at multiple locations (FF
(T result) is subjected to correlation processing to clarify information on the radio wave source to be observed. At this time, it is necessary that the frequencies of the counterparts to be correlated should match each other.

Further, in general, when the FFT is constructed as a serial type (pipeline type) as shown in FIG. 24, F output from the X output and Y output from the final stage of the FFT, respectively.
Lower half side of FT output (0-N / 2- in frequency index)
1) or the upper half side (frequency index from N / 2 to N-
Each frequency component is extracted in the state separated into 1). However, even in the data obtained by observing the same radio wave source, each frequency of the local oscillation of the receiver of each radio telescope and the anti-aliasing filter (anti-aliasing filter)
Of the frequency components of the FFT output depends on whether the lower half side is effective or the upper half side is effective.

In order to perform the correlation processing after performing the FFT on these data, it is necessary to select the frequency component on the effective side from the lower half side or the upper half side of the FFT outputs and perform the correlation processing. . Therefore, when the FFT device is constructed in a pipeline type using the conventional butterfly operation circuit shown in FIG. 25, it is necessary to additionally provide a data selection circuit after the FFT.

Further, as shown in FIG. 29, the conventional butterfly operation circuit is used, and the serial FFT circuit 51 of the preceding stage is used.
When an FFT device is composed of A and the parallel type FFT circuit 1B in the subsequent stage and multi-stream format data is handled as an input, each butterfly operation circuit 55-1 to 55-1 in the final stage is used.
From the X output and the Y output of 55-4, the same frequency side (if the X output is the lower half side (even number in the index value shown in FIG. 29), the Y output is also the lower half side) is output. .

Thus, for example, when the lower half side of both FFT outputs is required for the streams A and B, the selector 56-1 can output only one side,
The FFT result for one stream cannot be obtained. In order to solve this, after the FFT (between the final stage butterfly operation circuits 55-1 to 55-4 and each selector 56-1 to 56-4), a data selection unit having a complicated hardware configuration is provided. There was a need.

Note that the same processing as the correlation processing for the radio telescope as described above is also used for determining the position of underground buried objects (oil, mineral veins, fossils, etc.) by multipoint observation of blast shock waves. is there. The present invention was devised in view of such problems, and X of butterfly calculation output is used.
The side and the Y side can be arbitrarily switched with a simple configuration, and even if it is a serial type configuration or a configuration in which a front stage serial type and a rear stage parallel type are combined, It is an object of the present invention to provide a butterfly operation circuit and a fast Fourier transform device using the butterfly operation circuit, which is extremely effective when performing correlation processing on FFT results at multiple points by easily obtaining frequency components.

[0032]

FIG. 1 is a block diagram of the principle of the present invention. In FIG. 1, reference numeral 1 is a butterfly operation circuit according to the first invention. This butterfly operation circuit 1 comprises a multiplication circuit 2 and a pair of addition and subtraction circuits. It is composed of circuits 3A and 3B and a switching circuit 4. Here, the multiplication circuit 2 multiplies one of the two pieces of input data y by the twiddle factor W ^k , and the pair of addition / subtraction circuits 3A and 3B generate multiplication results W ^k · y and 2 from the multiplication circuit 2. One of the addition process and the subtraction process is performed on the other x of the individual pieces of input data, and output as output data X and Y, respectively. The switching circuit 4 is for selectively switching between the addition processing and the subtraction processing of the pair of addition / subtraction circuits 3A and 3B (claim 1).

At this time, a storage circuit for storing a control flag for instructing the switching operation of the switching circuit 4 is provided, the control flag is read from the storage circuit for each processing cycle, and the switching circuit 4 switches in accordance with the control flag. It may be configured to perform an operation (claim 2). The fast Fourier transform device of the present invention (the second to fifth inventions) is configured by using the above-mentioned butterfly computing circuit 1.

That is, the fast Fourier transform device of the second invention rearranges the input data appropriately in the order according to the operation so as to perform the radix-2 fast Fourier transform on the input data. A basic stage composed of a circuit and a butterfly operation circuit that performs butterfly operation on two input data from the data rearrangement circuit is connected in series by the number of stages set according to the number of input data, The butterfly operation circuit of at least the final basic stage is configured as the butterfly operation circuit 1 described above with reference to FIG. 1 (claim 3).

Further, the fast Fourier transform device of the third invention is inputted with a plurality of multiplexed data strings as input data, and in order to perform the radix-2 fast Fourier transform for each data string, the input data is subjected to arithmetic operations. A data rearrangement circuit for rearranging the data in units of two, a butterfly operation circuit for performing a butterfly operation on two input data from the data rearrangement circuit, and the data rearrangement circuit and butterfly operation circuit The basic stage consisting of a bypass circuit capable of bypassing the input data and outputting the input data as it is, is connected in series by the number of stages set according to the number of input data, and is configured for fast Fourier transform for multiple data strings. In the basic stages other than the basic stage for butterfly calculation, the bypass circuit is operated and at least the maximum The butterfly operation circuit of the basic stage for performing butterfly computation, and constitutes a butterfly operation circuit 1 described above in the FIG. 1 (claim 4).

Further, in the fast Fourier transform device of the fourth invention, a plurality of series circuits in which the same basic stages as those of the second invention are connected in series by a predetermined number of stages in order to perform the radix-2 fast Fourier transform on the input data. A series-type fast Fourier transform circuit arranged in parallel and a parallel circuit in which a plurality of butterfly operation circuits are arranged and connected in matrix form are provided in parallel, and two output data of each series circuit are input to each pair of parallel circuits. And a parallel fast Fourier transform circuit, and at least the final stage butterfly operation circuit in the parallel fast Fourier transform circuit is configured as the butterfly operation circuit 1 described above with reference to FIG. 1 (claim 5).

Further, the fast Fourier transform device of the fifth invention is the same as the third invention in order to perform a radix-2 fast Fourier transform for each data string which is input with a plurality of multiplexed data strings as input data. A series type fast Fourier transform circuit in which a plurality of series circuits in which a predetermined number of similar basic stages are connected in series are arranged in parallel, and a parallel circuit in which a plurality of butterfly operation circuits having a bypass function are arranged and connected in a matrix form in parallel And a parallel type fast Fourier transform circuit for inputting two output data of each series circuit to a pair of parallel circuits respectively, and a basic stage other than the basic stage in the series type fast Fourier transform circuit for performing butterfly operation. In the parallel type fast Fourier transform circuit, which operates the bypass circuit and performs butterfly computation, The butterfly operation circuit other than the fly operation circuit operates the bypass function, and at least the basic stage butterfly operation circuit in the serial fast Fourier transform circuit that performs the final butterfly operation, or the parallel fast Fourier transform that performs the final butterfly operation. The butterfly operation circuit in the circuit is configured as the butterfly operation circuit 1 described above with reference to FIG. 1 (claim 6).

When the final stage of each butterfly operation circuit is provided with a data selector for selecting and outputting any one of the two output data from the butterfly operation circuit, a plurality of data strings are provided. Corresponding to, the output data to be selected by the data selection unit may be set in advance (claim 7). In each of the fast Fourier transform devices described above, a storage circuit that stores a control flag for instructing the switching operation of the switching circuit 4 of each butterfly operation circuit 1 is provided, and the control flag is read from the storage circuit for each processing cycle. The switching circuit 4 may be configured to perform a switching operation according to the control flag (claim 8).

[0039]

In the butterfly operation circuit of the first invention described above,
The multiplication circuit 2 multiplies the input data y by the twiddle factor W ^k , and outputs the intermediate result W ^k · y.
3B performs either addition processing or subtraction processing on the multiplication result W ^k · y from the multiplication circuit 2 and the input data x, and outputs the respective processing results as output data X and Y, respectively.

At this time, when the switching circuit 4 switches the addition / subtraction circuit 3A to perform addition processing and the addition / subtraction circuit 3B to perform subtraction processing, output data X = x + W ^k · y from the addition / subtraction circuit 3A. , The output data from the adder / subtractor circuit 3B is Y = x−W ^k · y, while the switching circuit 4 switches the subtraction process in the adder / subtractor circuit 3A and the addition process in the adder / subtractor circuit 3B , Output data X = x−W ^k · y from the adder / subtractor circuit 3A, and output data Y = x + W ^k · y from the adder / subtractor circuit 3B.

That is, according to the switching operation by the switching circuit 4, the X output and the Y output from the butterfly operation circuit 1 can be arbitrarily switched to either x + W ^k · y or x−W ^k · y. (Claim 1). At this time, a control flag for instructing the switching operation of the switching circuit 4 is stored in advance in the storage circuit, the control flags are sequentially taken out from the storage circuit for each processing cycle, and the switching operation according to the control flag is performed by the switching circuit 4. By performing the above, it is possible to dynamically switch the operations performed by the adder / subtractor circuits 3A and 3B (claim 2).

In the above-described fast Fourier transform device of the second aspect of the invention, the basic stages consisting of the data rearrangement circuit and the butterfly operation circuit are connected in series by a predetermined number of stages, and these basic stages are used for the fast Fourier transform of the radix 2 with respect to the input data. The conversion is applied. At this time, since the X output and the Y output from the butterfly operation circuit 1 of the final basic stage can be arbitrarily switched as described above, the frequency component of the result of the fast Fourier transform is changed from the X output and the Y output. The desired side [0 at frequency index
.About.N / 2-1 or N / 2.about.N-1 (N is the number of data of the power of 2)] can be extracted (claim 3).

In the above-described fast Fourier transform device of the third invention, when a plurality of multiplexed data strings (multistream format data) are handled as input data, the data rearrangement circuit, the butterfly operation circuit and the bypass circuit are used. The following basic stages are connected in series for a prescribed number of stages, and these basic stages perform butterfly computation for a prescribed number of stages according to the number of multiplexed data strings, and operate the bypass circuit in the basic stages that do not need to perform butterfly computation. By allowing the input data to pass as it is, the radix-2 fast Fourier transform is performed for each data string. At this time, the X output and the Y output from the butterfly operation circuit 1 of the basic stage that performs the final butterfly operation can be arbitrarily switched as described above, so that the result of the fast Fourier transform is obtained from the X output and the Y output. It is possible to take out the frequency component on the desired side (frequency index 0 to N / 2-1 or N / 2 to N-1) of the frequency components (claim 4).

In the above fast Fourier transform device of the fourth invention, the radix-2 fast Fourier transform is applied to the input data by the serial fast Fourier transform circuit at the front stage and the parallel fast Fourier transform circuit at the rear stage. At this time, since the X output and the Y output from the butterfly operation circuit 1 of the final basic stage can be arbitrarily switched as described above, the frequency component of the result of the fast Fourier transform is changed from the X output and the Y output. Of these, frequency components on the desired side (frequency index 0 to N / 2-1 or N / 2 to N-1) can be extracted (claim 5).

In the above-described fast Fourier transform device of the fifth aspect of the invention, in the case of handling a plurality of multiplexed data strings (multi-stream format data) as input data, the preceding stage serial fast Fourier transform circuit having a bypass function. And the parallel type fast Fourier transform circuit in the subsequent stage performs a predetermined number of butterfly operations according to the number of multiplexed data strings, and operates the bypass function in the basic stage and butterfly operation circuit that do not require butterfly operation. By passing the data as it is, the radix-2 fast Fourier transform is performed for each data sequence. At this time, the X output and the Y output from the butterfly operation circuit 1 of the basic stage in the serial fast Fourier transform circuit that performs the final butterfly operation, or the butterfly operation circuit 1 in the parallel fast Fourier transform circuit that performs the final butterfly operation Can be arbitrarily switched as described above, so that from the X output and the Y output, the desired side (frequency index 0 to N / 2-1 or N / 2 in the frequency component of the result of the fast Fourier transform) can be obtained.
(N-1) frequency components can be taken out (Claim 6).

When a data selector is provided at the rear stage of each butterfly operation circuit at the final stage, output data (X output or Y output) to be selected by the data selector is preset corresponding to a plurality of data strings. By doing so, the frequency component on the desired side (frequency index 0 to N / 2-1 or N / 2 to N-1) can be extracted from each data string (stream) (claim 7). ..

Also in each of the above-described fast Fourier transform devices, the control flag is sequentially taken out from the memory circuit for each processing cycle, and the switching circuit 4 performs the switching operation according to the control flag so that the final stage is operated. The frequency component of the output data can be dynamically switched to the desired side (claim 8).

[0048]

Embodiments of the present invention will be described below with reference to the drawings. (A) Description of First Embodiment First, the configuration of a butterfly operation circuit used in a fast Fourier transform device of each embodiment of the present invention described later will be described with reference to FIG.

In FIG. 2, reference numeral 21 denotes a butterfly operation circuit of this embodiment, which is composed of a multiplication circuit 22, a pair of CLA (Carry Lookahead Adder) 23A, 23B and a switching circuit 24. ing. Here, the multiplication circuit 22 multiplies one of two pieces of input data x and y by a twiddle factor (twisting coefficient) W ^k , and the twiddle factor W ^k is a memory (not shown) (for example, FIG. 2).
5, the input data y is appropriately multiplied by the twiddle factor W ^k corresponding to the input data y.

In addition, the pair of CLAs 23A and 23B, together with the function of the switching circuit 24 which will be described later, perform addition processing on the multiplication result W ^k · y from the multiplication circuit 22 and the other x of the two input data x and y. Alternatively, either one of the subtraction processes is performed and output as output data X and Y, respectively. The switching circuit 24 selectively switches between the pair of CLAs 23A and 23B that performs addition processing and the one that performs subtraction processing according to a butterfly mode switching signal (1-bit signal) BM supplied from the outside. And an inverter circuit 25 and a pair of exclusive OR circuits (EOR) 26A and 26B.

The inverter circuit 25 is provided on the carry-in terminal Cin of the CLA 23B and the input line to the exclusive OR circuit 26B, and is provided with a switching signal B from the outside.
M is directly input to the carry-in terminal Cin of the CLA 23A, inverted by the inverter circuit 25, and then input to the carry-in terminal Cin of the CLA 23B.

The exclusive OR circuit 26A calculates the exclusive OR of the switching signal BM from the outside and the multiplication result W ^k · y (multi-bit signal) from the multiplication circuit 22 to obtain CLA2.
The exclusive OR circuit 26B outputs the signal to the data input terminal B of 3A, and the multiplication result W ^k from the multiplication circuit 22 and the switching signal BM inverted by the inverter circuit 25.
The exclusive OR with y (multi-bit signal) is calculated, and C
The data is output to the data input terminal B of the LA 23B.

The input data x is directly input to the data input terminal A of each CLA 23A, 23B. Further, in FIG. 2, 27 is a storage circuit for setting and storing a plurality of control flags BF for instructing the switching operation of the switching circuit 24, 28 is a control flag BF sequentially fetched from the storage circuit 27 and used as the switching signal BM. Arithmetic circuit 2
This multiplexer 2 outputs to 1
According to FIG. 8, during the butterfly operation, the control flag BF is sequentially taken out from the memory circuit 27 for each processing cycle and is given to each butterfly operation circuit 21 as the switching signal BM, whereby the operation performed by the CLA 23A, 23B can be dynamically switched. It is possible. The functions of the storage circuit 27 and the multiplexer 28 are effective in the multi-stream mode described later.

The operation of the butterfly operation circuit 21 configured as described above will be described in more detail. When the switching signal BM = 0, "0" is input to the carry-in terminal Cin of the CLA 23A and the exclusive OR circuit 26A. Since it is input, the multiplication circuit 2 is fed from the exclusive OR circuit 26A.
The multiplication result W ^k · y by 2 is output to the CLA 23A as it is. Then, in the CLA 23A, the data x input from the data input terminal A and the data W ^k · y input from the data input terminal B are added, and the addition result x + W ^k · y is output as the output data X. .

When the switching signal BM = 0, the switching signal BM is inverted by the inverter circuit 25 and C
Since “1” is input to the carry-in terminal Cin of the LA 23B and the exclusive OR circuit 26B, the multiplication result W ^k · y by the multiplication circuit 22 is input from the exclusive OR circuit 26B.
Is inverted, and the two's complement of this multiplication result W ^k · y is output to the CLA 23B. Then, in the CLA 23B, "1" input to the carry-in terminal Cin,
Data x that is input from the data input terminal A, by adding the 2's complement of with data W ^k · y input from the data input terminal B, the data from the data x W ^k ·
Subtraction processing for subtracting y is performed, and the subtraction result x−W
^k · y is output as output data Y.

On the contrary, when the switching signal BM = 1, CL
Since "1" is input to the carry-in terminal Cin of A23A and the exclusive OR circuit 26A, the multiplication result W ^k · y by the multiplication circuit 22 is inverted from the exclusive OR circuit 26A, and this multiplication result W ^k The two's complement for y is C
It is output to LA23A. Then, in the CLA 23A, “1” input to the carry-in terminal Cin, the data x input from the data input terminal A, and the two's complement number of the data W ^k · y input from the data input terminal B are input. By adding, a subtraction process of subtracting the data W ^k · y from the data x is performed, and the subtraction result x−W ^k · y.
y is output as the output data X.

When the switching signal BM = 1, the switching signal BM is inverted by the inverter circuit 25 and C
Since “0” is input to the carry-in terminal Cin of the LA 23B and the exclusive OR circuit 26B, the multiplication result W ^k · y by the multiplication circuit 22 is input from the exclusive OR circuit 26B.
Is output as it is to the CLA 23B. And CLA
23B, the data x input from the data input terminal A and the data W ^k input from the data input terminal B
y and y are added, and the addition result x + W ^k · y is output as output data Y.

Thus, the butterfly mode switching signal B
By setting M to “0”, the CLA 23A functions as an adder and the CLA 23B functions as a subtractor, while by setting the butterfly mode switching signal BM to “1”, the CLA 23A functions as a subtractor and the CLA 23B. Can function as an adder, and depending on the setting of the switching signal BM, a pair of CLA 23
It is possible to selectively switch between A and 23B that performs addition processing and that that performs subtraction processing.

FIG. 3 is a block diagram showing a fast Fourier transform device as a first embodiment of the present invention. In this first embodiment, the FFT device is a serial type, and the radix r = 2,
A case will be described in which the FFT is performed on the data in the single stream format in which the number of sample value data (the number of FFT points) N = 2 ^M. In this case, as shown in FIG. 3, M basic stages 30-1, 30-2, ..., 30-M are connected in series. Here, the basic stage number M is M = log _r N = log ₂ based on the radix r and the FFT score N.
Given as 2 ^M = M.

As shown in FIG. 4, each of the basic stages 30-1 to 30-M comprises a data rearrangement circuit 31 and the butterfly operation circuit 21 described above with reference to FIG. The data rearrangement circuit 31 appropriately rearranges the data x and y input from the outside according to the order according to the operation, as in the conventional circuit shown in FIG.
1 is output in units of two.

With the above configuration, each basic stage 30-
1 to 30-M, the butterfly operation is performed by the butterfly operation circuit 21 while rearranging the data by the data rearrangement circuit 31 as in the conventional case.
The radix-2 FFT is applied to (= 2 ^M ) pieces of input data. At this time, in the present embodiment, the X output and the Y output from the butterfly operation circuit 21 of the final basic stage 30-M can be switched according to the setting of the butterfly mode switching signal BM. That is, if the switching signal BM is set to "0", the butterfly operation circuit 21 at the final stage
Although the X output and the Y output from the same are conventional, when the switching signal BM is set to "1", the X output and the Y output from the butterfly operation circuit 21 at the final stage are opposite to the conventional ones.

Therefore, in the serial type FFT device, from the X output and the Y output of the butterfly operation circuit 21 at the final stage, the desired side (0 to N / 2-1 or N at the frequency index) of the frequency components of the FFT result is obtained. / 2 to N-1) frequency components can be easily extracted, so FFT at multiple points
Correlation processing for the result can be performed reliably and effectively.

In the first embodiment described above, the butterfly operation circuit 2 in the basic stages 30-1 to 30-M is used.
1 has the configuration shown in FIG. 2, but at least only the butterfly operation circuit 21 in the final basic stage 30-M has the configuration shown in FIG. 2 and the other basic stages 30-1 to 30-30. The butterfly operation circuit at-(M-1) may have the same configuration as the conventional one shown in FIG. 25, and in this case, the same operational effect as that of the above-described embodiment can be obtained.

(B) Description of Second Embodiment FIG. 5 is a block diagram showing a fast Fourier transform device as a second embodiment of the present invention. In this second embodiment, FF
The T device is a serial type, the radix is r = 2, the sample value data number (FFT point number) N = 2 ^M , and FF for multi-stream format data (multiplexed data strings)
The case of applying T will be described. Here, the number of multistreams (the number of multiplexed data strings) is I (power of 2).

Also in this case, as shown in FIG. 5, as in the first embodiment, the M basic stages 30-1, 30-2,
, 30-M are connected in series. However, in the basic stages 30-1 to 30-M of the second embodiment, as shown in FIG. In addition to the butterfly operation circuit 21 shown in FIG. 2, a pair of bypass circuits 32A and 32B that can bypass the data rearrangement circuit 31 and the butterfly operation circuit 21 and output the input data as they are are provided.

Each bypass circuit 32A, 32B is composed of a bypass line 33A, 33B and a multiplexer 34A, 34B, respectively. Here, the bypass lines 33A and 33B are connected to the input data x,
It is for bypassing the data rearrangement circuit 31 and the butterfly operation circuit 21 for y.

Further, the multiplexer 34A receives the X output from the butterfly operation circuit 21 and the input data x from the bypass line 33A, selectively switches either one and outputs the same. 34B receives the Y output from the butterfly operation circuit 21 and the input data y from the bypass line 33B and selectively switches one of them to output. The switching operation by these multiplexers 34A and 34B is It is designed to be controlled by a control signal from the outside.

That is, by selecting and outputting the X output and the Y output from the butterfly operation circuit 21 by the multiplexers 34A and 34B, the normal butterfly operation result is output to the next basic stage, while the input data is input. x,
By selecting and outputting y, the input data x and y are not processed by the data rearrangement circuit 31 and the butterfly operation circuit 21, and are directly input to the respective basic stages 30.
-1 to 30-M will be passed (through operation).

With the above-mentioned configuration, with respect to N-point data in the multi-stream mode (2, 4, 8, 16, ...
FFT is performed. In the case of I multi-stream format,
While the actual butterfly calculation is performed by the basic stages 30-1 to 30- [M-log ₂ I], the latter stage of
basic stage 30-[(M-log ₂ I) + for log ₂ I stages
1] to 30-M, the bypass circuit 32 described above is used.
A and 32B are operated to operate multiplexers 34A and 34B.
By selecting the input data x and y from the bypass lines 33A and 33B, the switching to the through operation state in which the butterfly operation is not performed is performed.

Further, the control flag B for the basic stage 30- [M-log ₂ I] for performing the final butterfly operation.
F is set in the memory circuit 27 in advance for I of the number of streams, and the multiplexer 28 is used during butterfly calculation.
The control flag BF is sequentially taken out as the switching signal BM by the above, and is given to the switching circuit 24 in the butterfly operation circuit 21 of the basic stage 30- [M-log ₂ I].
Similar to the embodiment, the basic stage 30- [M-log
The frequency component of the output data from [ ₂ I] can be dynamically switched to a desired side for each stream (data string).

The X output and Y output from the basic stage 30- [M-log ₂ I] are the same as those of the basic stage 30-[(M-log
₂ I) +1] to 30-M are in the through operation state,
Pass through each stage as it is, the final basic stage 3
It is output as 0-M X output and Y output (FFT result). As described above, according to the second embodiment of the present invention, in the serial type FFT apparatus, the basic stage 30- [M] for performing the final butterfly operation while performing the radix-2 FFT processing on the multi-stream format data. -Log ₂ I]
From the X output and Y output of the butterfly operation circuit 21 of
Of the frequency components of the FFT result for each data string, the frequency component on the desired side (0 to N / 2-1 or N / 2 to N-1 in the frequency index) can be easily extracted, and the FF at multiple points can be obtained.
Correlation processing for the T result can be performed reliably and effectively.

In the second embodiment described above, the case where the FFT processing is performed on the multi-stream format data has been described. However, also in the FFT device of the present embodiment shown in FIG. 5, the bypass circuits 32A and 32B are used. By performing the butterfly operation by all the basic stages 30-1 to 30-M without operating, the FFT for N-point data in the single stream format can be performed in the same manner as in the first embodiment.

In the second embodiment described above, the butterfly operation circuit 2 in the basic stages 30-1 to 30-M is also used.
1 has the configuration shown in FIG. 2, but at least the basic stage 30-which performs the final butterfly operation
Only the butterfly operation circuit 21 in [M-log ₂ I] may have the configuration shown in FIG. 2, and the butterfly operation circuits in the other basic stages may have the same configuration as the conventional one shown in FIG. 25. It is possible to obtain the same effect as that of the above-described embodiment.

Further, in the above-described second embodiment, all the basic stages 30-1 to 30-M have the structure shown in FIG. 6, but at least the basic stage 30-[(M-
log ₂ I) +1] to 30-M, bypass circuits 32A, 32
B, and other basic stages 30-1 to 30- [M-
For the log ₂ I], the bypass circuits 32A and 32B may be omitted, and in this case also, the same effect as the above-described embodiment can be obtained.

(C) Description of Third Embodiment FIG. 7 is a block diagram showing a fast Fourier transform device as a third embodiment of the present invention. In this third embodiment, FF
The T device is a combination of a serial type front stage part and a parallel type rear stage part, and the radix is r = 2, and the FFT is performed on the data in the single stream format with the sample value data number (FFT point number) N = 2 ^M. The case of applying will be described.

As shown in FIG. 7, the FFT apparatus according to the third embodiment has a series type FFT circuit 35 in the front stage and a parallel type FF in the rear stage.
And a T circuit 36. Where serial FF
The T circuit 35 has a configuration in which n sets of series circuits 37-1 to 37-n in which k basic stages 30-1 to 30-k having the same configuration as those shown in FIG. 4 are connected in series are arranged in parallel. It has become. That is, the series circuits 37-1 to 37-n are
The configuration is such that the radix r = 2 and the number of FFT points N = 2 ^k performs FFT. Here, n is the parallel frequency of the butterfly operation of each FFT stage.

Further, the parallel type FFT circuit 36 is constituted by arranging two sets of parallel circuits 38A and 38B in parallel. The parallel circuit 38A receives the X output from each of the series circuits 37-1 to 37-n of the series type FFT circuit 35 and performs the FFT with the radix r = 2 and the FFT score N = 2 ^Mk . The butterfly operation circuit 21 having the same configuration as that described above is arranged in the form of (n / 2) rows (Mk) columns.

The parallel circuit 38B is the serial FFT circuit 35.
The Y output from each of the series circuits 37-1 to 37-n is input to perform the FFT with the radix r = 2 and the number of FFT points N = 2 ^Mk . A butterfly operation circuit 21 having the same configuration (n / 2)
They are arranged in a row (Mk) column format. In these parallel circuits 38A and 38B, data is rearranged in accordance with a hardware configuration in which the butterfly operation circuits 21 are arranged in a matrix and the input ports and the output ports are appropriately connected at each stage.

Then, the butterfly operation circuit 21 at the final stage
X output and Y output from are output as the FFT result. With the configuration described above, in the serial FFT circuit 35 and the parallel FFT circuit 36, the radix-2 FFT processing is performed on N pieces of input data basically in the same manner as the conventional one shown in FIG. .

At this time, also in this embodiment, the n butterfly operation circuits 21 at the final stage in the parallel type FFT circuit 36.
The X output and the Y output can be switched according to the setting of the butterfly mode switching signal BM. In other words, if the switching signal BM is set to "0", the X output and the Y output from each butterfly operation circuit 21 at the final stage will be the same as before, but if the switching signal BM is set to "1", the final stage X output and Y from each butterfly operation circuit 21
The output is the opposite of the conventional one.

Therefore, in the FFT device in which the series type front stage part and the parallel type rear stage part are combined, the FFT is performed from the X output and the Y output of each butterfly operation circuit 21 at the final stage.
Of the resulting frequency components, the frequency component on the desired side (0-N / 2-1 or N / 2-N-1 in the frequency index) can be easily extracted, so correlation processing for FFT results at multiple points is possible. Can be performed reliably and effectively.

In the third embodiment described above, all the butterfly operation circuits 21 constituting the FFT device are all shown in FIG.
However, at least only the butterfly operation circuit 21 at the final stage may be configured as shown in FIG. 2, and the other butterfly operation circuits may have the same structure as the conventional one shown in FIG. In this case as well, it is possible to obtain the same operational effects as the above-described embodiment.

(D) Description of Fourth Embodiment FIG. 8 is a block diagram showing a fast Fourier transform device as a fourth embodiment of the present invention. The FFT device is a combination of a serial type front stage part and a parallel type rear stage part, and the radix is r = 2. Like the second embodiment, the number of sample value data (FFT points) N = 2 ^M , multi A case where FFT is performed on stream format data will be described. Here, the number of multistreams is I.

As shown in FIG. 8, the FFT device of this embodiment has substantially the same structure as that of the third embodiment. As -1 to 30-k, the bypass circuit 32 is the same as that described above with reference to FIG. 6 in the second embodiment.
A type having A and 32B is used, and a parallel type FF
As each butterfly operation circuit 21 forming the T circuit 36, a circuit to which bypass circuits 39A and 39B are added as shown in FIG. 9 is used.

As shown in FIG. 9, each bypass circuit 39
A and 39B are bypass lines 40A and 40B, respectively.
B and multiplexers 41A and 41B. Here, the bypass lines 40A and 40B are used for the butterfly operation circuit 2 for the input data x and y, respectively.
It is for bypassing 1. Further, the multiplexer 41A receives the X output from the butterfly operation circuit 21 and the input data x from the bypass line 40A,
One of them is selectively switched and output. Similarly, the multiplexer 41B receives the Y output from the butterfly operation circuit 21 and the input data y from the bypass line 40B, and selectively selects one of them. Output by switching to the multiplexer 41.
The switching operation by A and 41B is controlled by a control signal from the outside.

That is, by selecting and outputting the X output and the Y output from the butterfly operation circuit 21 by the multiplexers 41A and 41B, the normal butterfly operation result is output to the butterfly operation circuit 21 of the next stage. By selecting and outputting the input data x and y, the input data x and y are not processed by the butterfly operation circuit 21 and bypass each butterfly operation circuit 21 (through operation).

With the above-described configuration, with respect to N-point data in the multi-stream mode (2, 4, 8, 16, ...
FFT is performed. In the case of I multi-stream format,
Butterfly operation is performed using the basic operation stage in the [M-log ₂ I] -stage serial FFT circuit 35 and the butterfly operation circuit 21 in the parallel FFT circuit 36.
In FIG. 8, when the butterfly operation processing of [M-log ₂ I] stage is completed in the serial FFT circuit 35, that is, [M
The case of −log ₂ I] <k will be described.

[0088] In this case, in fact the [M-log ₂ I] The basic stages of stage 30-1～30- [M-log ₂ I] in the series circuits 37-1 to 37-n of the series type FFT circuit 35 While performing the butterfly calculation of
basic stage 30-[(M-log ₂ I) + for log ₂ I stages
1] to 30-k and the butterfly operation circuit 21 in the parallel FFT circuit 36, the bypass circuit 3 described above is used.
2A, 32B and 39A, 39B are operated, and multiplexers 34A, 34B, 41A, 41B select input data x, y from the bypass lines 33A, 33B, 40A, 40B, so that a butterfly operation is not performed. Switch to.

Further, as in the second embodiment, the control flag BF for the basic stage 30- [M-log ₂ I] for performing the final butterfly operation is set to I / n (n is the butterfly of each FFT stage stage). Memory circuit 27 only for the parallel degree of calculation
In the butterfly operation, the multiplexer 28 sequentially takes out the control flag BF as the switching signal BM, and the butterfly operation of the basic stage 30- [M-log ₂ I] in each series circuit 37-1 to 37-n is performed. By applying it to the switching circuit 24 in the circuit 21, as in the first and third embodiments, the basic stage 30- [M-log ₂
The frequency component of the output data from [I] can be dynamically switched to a desired side for each stream (data string).

The X and Y outputs from the basic stage 30- [M-log ₂ I] in each series circuit 37-1 to 37-n are the same as the basic stage 30-[(M
-Log ₂ I) +1] to 30-k and parallel type FFT circuit 3
Since the butterfly operation circuit 21 of 6 is in the through operation state, it passes through each stage as it is, and is output as the X output and Y output (FFT result) of the n butterfly operation circuits 21 at the final stage.

As described above, according to the fourth embodiment of the present invention, in the FFT apparatus in which the serial front stage and the parallel rear stage are combined, the radix-2 FFT process is performed on the multi-stream format data. From the X output and the Y output of the butterfly operation circuit 21 that performs the final butterfly operation while performing the operation, the desired side (0 to N / 2-1 or N / 2 at the frequency index) of the frequency components of the FFT result is obtained for each data string. It is possible to easily extract the frequency components of (~ N-1) and to reliably and effectively perform the correlation processing on the FFT results at multiple points.

In the fourth embodiment described above, the case where the FFT processing is performed on the multi-stream format data has been described. However, also in the FFT device of the present embodiment shown in FIG. 8, the bypass circuits 32A, 32B ,. 39A, 3
By performing the butterfly operation by the butterfly operation circuits 21 of all stages without operating 9B, the FFT for N-point data in the single stream format can be performed as in the third embodiment.

(E) Description of Fifth Embodiment FIG. 10 is a block diagram showing a fast Fourier transform device as a fifth embodiment of the present invention. FFT of this fifth embodiment
As shown in FIG. 10, the device has the same configuration as the FFT device of the fourth embodiment shown in FIG.
A data selection unit 43 including -1 to 42-n is added.

Each of the selectors 42-1 to 42-n forming the data selecting section 43 is arranged at the subsequent stage of each butterfly operation circuit 21 at the final stage, and two output data from each butterfly operation circuit 21 are output. One of X and Y is selected and output, and in this embodiment,
Selectors 42-1 to 42-n corresponding to the respective data strings
The output data to be selected is set in advance, and the frequency component on the desired side can be extracted from each data string (stream).

Next, a more specific operation of the FFT device will be described with reference to FIGS. 11 to 23. First,
The specific configuration of the FFT device will be described with reference to FIG. 11. In the FFT device shown in FIG. It is configured such that four sets of series circuits 37-1 to 37-4 in which 30-3 are connected in series are arranged in parallel. That is, each series circuit 37-1 to 37-4
Is configured to perform FFT with radix r = 2 and FFT score N = 8. In addition, each basic stage 30-1 to 30
-3 has the same configuration as that described above with reference to FIG.

Further, the parallel type FFT circuit 36 has a configuration shown in FIG.
Similar to that shown in FIG. 29, two sets of parallel circuits 38A, 3A
8B are arranged in parallel and four selectors 42
It is configured to include a data selection unit 43 including -1 to 42-4. The parallel circuit 38A is the serial type FFT circuit 3
The X output from each of the serial circuits 37-1 to 37-4 of FIG. Moreover, the bypass circuit 39 described above with reference to FIG.
Four butterfly operation circuits 44- each having A and 39B
1, 44-2, 45-1, 45-2 are arranged in the form of 2 rows and 2 columns. The X output and the Y output from the butterfly operation circuit 44-1 in the fourth stage are 2 in the fifth stage.
The two butterfly operation circuits 45-1 and 45-2 are also input to the two butterfly operation circuits 45-1 and 45-2, and the X output and the Y output from the butterfly operation circuit 44-2 in the fourth stage are also respectively included in the two butterfly operation circuits 45-1 and 45-5 in the fifth stage. -2 is input.

The parallel circuit 38B is the serial FFT circuit 35.
The Y output from each of the series circuits 37-1 to 37-4 is input to perform the FFT with the radix r = 2 and the FFT score N = 4, and four butterfly operation circuits 44-3, 44-4,
45-3 and 45-4 are arranged in the form of 2 rows and 2 columns. These butterfly operation circuits 44-3, 4
4-4, 45-3, and 45-4 also have the same configuration as the butterfly operation circuit 21 described above with reference to FIG. 2 and have the bypass circuits 39A and 39B described above with reference to FIG. 38A butterfly operation circuit 44
It is connected in the same manner as -1, 44-2, 45-1, 45-2.

In the parallel circuits 38A and 38B, the butterfly operation circuits 44-1 to 44-4 and 45-1 to 4 are used.
According to the hardware configuration in which 5-4 are arranged in a matrix and the input ports and output ports are appropriately connected to each stage, data is rearranged and FFT with an FFT score N = 4 is performed. Then, one of the X output and the Y output from the butterfly operation circuits 45-1 to 45-4 of the fifth stage is the selector 42-1 of the data selection unit 43.
˜42-4 are selected and output as the FFT result.

(E1) Description of Operation in 1-Stream Mode When FFT processing is performed on 32-point data data A00, A01, ... This will be described with reference to FIG. In this case,
Similar to the conventional case shown in FIG. 8, first, these data are divided into four 8-point data groups A00, A04, A08, ...,
A28; A01, A05, A09, ..., A29; A02, A06, A1
0, ..., A30; A03, A07, A11, ..., A31, and for each data group, the serial type FFT of the preceding stage, respectively.
Eight-point FFT is performed by each series circuit 37-1 to 37-4 (three basic stages 30-1 to 30-3) of the circuit 35.

[0100] After this, X output group from the basic stage 30-3 in the series circuit _{37-1 A 3 00, A 3 08} , A 3 16, A 3 24
And X output group A ₃ 02 from the base stage 30-3 of the series circuit 37-3, and _{A 3 10, A 3 18,} A 3 26 is a parallel circuit 38
X output group from the basic stage 30-3 of the series circuit 37-2, which is input to the butterfly operation circuit 44-1 of A.
X output groups A ₃ 01, A ₃ 09, A ₃ 17, A ₃ 25 and the basic stage 30-3 of the series circuit 37-4, A ₃ 03, A ₃ 11, A ₃ 19,
And A ₃ 27 is, the butterfly operation circuit of the parallel circuit 38A 44-
Entered in 2.

[0102] Similarly, Y output group A ₃ 04 from the base stage 30-3 of the series circuit _{37-1, A 3 12, A 3} 20, A 3 28
And the Y output group _{A 3 06, A 3 14,} A 3 22, A 3 30 from the base stage 30-3 of the series circuit 37-3 is, the parallel circuit 38
Y output group from the basic stage 30-3 of the series circuit 37-2, which is input to the B butterfly calculation circuit 44-3.
A ₃ 05, A ₃ 13, A ₃ 21, A ₃ 29 and Y output groups from the basic stage 30-3 of the series circuit 37-4 A ₃ 07, A ₃ 15, A ₃ 23,
A ₃ 31 is the butterfly operation circuit 44- of the parallel circuit 53B.
4 is input.

These parallel circuits 38A and 38B enable 4
In the example shown in FIG. 12, since "0" is all given as the butterfly mode switching signal BM to the butterfly operation circuits 45-1 to 45-4 at the final stage, the X output, The Y output is not replaced (reversed), and the data is output as in the conventional case. Then, the selectors 42-1 to 42-4, for example, select the X outputs of the butterfly operation circuits 55-1 to 55-4 at the fifth stage, so that the lower half side of the FFT output (0 to N at the frequency index) is selected. / 2-1) that is _{A 5 00, A 5 08,} A 5 16, A 5 24; A 5 02, A 5 1
_{0, A 5 18, A 5} 26; A 5 04, A 5 12, A 5 20, A 5 28; A 5 06, A 5 1
_{4, A 5 22, A 5} 30 is output as a final FFT results.

Here, the numbers 3, 5 and the like attached to the lower right of the code A indicating the data indicate the output of the data (basic stage or butterfly operation circuit). Further, the number attached to the lower right subscript of the symbol A is a sequential number indicating the data sampling order. The rules for such subscripts are shown in Figure 1.
It is common to the description of the operation in each stream mode according to FIGS.

(E2) Description of Operation in Two-Stream Mode Next, 32-point data data A00, A01, ..., A1 in two-stream mode (data string indicated by symbols A and B, respectively)
5; B00, B01, ..., B15 will be described with reference to FIG. In this case, first, these data are grouped into four 8-point data groups A0.
0, A04, A08, ..., A14; B00, B04, B08, ..., B1
4; A01, A05, A09, ..., A15; B01, B05, B09,
, B15, and for each data group, the series circuits 37-1 to 37-3 of the series-type FFT circuit 35 at the preceding stage, respectively.
Perform 8 point FFT by 7-4.

At this time, since the number of streams is 2,
[5-log ₂ 2] = 4 stages The basic stages of 30-1～30-
3, F using the butterfly operation circuits 44-1 to 44-4
FT is performed, and the butterfly operation circuit 45-1 to 45-2 on the subsequent stage side
In 45-4, the bypass circuits 39A and 39B are operated to bypass the input data (through operation state). In FIG. 13, the butterfly operation circuit 45-1.
“====” described in the block 45-4 indicates that the through operation state is set.

As a result, 16-point FFT is performed for each stream on 32-point data in the 2-stream mode. Then, each series circuit 37-1 to 37-4
First, 8-point FFT is performed for each stream by the three basic stages 30-1 to 30-3. After this, X output group A ₃ 00 from the basic stage 30-3 in the series circuit _{37-1, A 3 04, A 3} 08, X output from the basic stage 30-3 of A ₃ 12 and the series circuit 37-3 Group A ₃ 01, A ₃ 05, A ₃
09, A ₃ 13 and are butterfly operation circuit parallel circuits 38A
4-1 is input to the basic stage 3 of the series circuit 37-2.
X output group B ₃ of from _{0-3 00, B 3 04, B} 3 08, B 3 12 and the X output group B ₃ 01 from the basic stage 30-3 in the series circuit 37-4, B ₃ 05, B ₃ 09, B ₃ 13 and parallel circuit 38A
Is input to the butterfly operation circuit 44-2.

Similarly, Y output groups A ₃ 02, A ₃ 06, A ₃ 10, A ₃ 14 from the basic stage 30-3 of the series circuit 37-1.
And a series circuit Y output group A ₃ 03 from the base stage 30-3 _{37-3, A 3 07, A 3} 11, A 3 15 is a parallel circuit 38
Y output group from the basic stage 30-3 of the series circuit 37-2, which is input to the B butterfly calculation circuit 44-3.
B ₃ 02, B ₃ 06, B ₃ 10, B ₃ 14 and Y output groups B ₃ 03, B ₃ 07, B ₃ 11, from the basic stage 30-3 of the series circuit 37-4,
B ₃ 15 and are parallel circuit 53B butterfly operation circuit 44-
4 is input.

The butterfly operation circuits 44-1 to 44-4 of the first stage (that is, the fourth stage) of the parallel circuits 38A and 38B.
-4 performs two-point FFT, and the X output and Y output from these butterfly operation circuits 44-1 to 44-4 are directly used as the FFT result in the two-stream mode.
It is output after passing through the fifth stage butterfly operation circuits 45-1 to 45-4. However, in the example shown in FIG. 13, the butterfly operation circuit 4 at the fourth stage for performing the final butterfly operation.
Of 4-1 to 44-4, a butterfly operation circuit 44-
1, 44-3 is given a switching signal BM of "0", but the butterfly operation circuits 44-2, 44-4 are given a switching signal BM of "1". Data exchange (reversal) is performed on the X and Y outputs of 44-2 and 44-4. Note that, in FIG. 13, the data output state in the case where the data exchange (reversal) is not performed is indicated by a symbol with ().

Therefore, the butterfly operation circuit 45 of the fifth stage
-1 X output group and Y output group are A ₄₀
0, A ₄ 04, A ₄ 08, A ₄ 12; B ₄ 01, B ₄ 05, B ₄ 09, B ₄ 13 and the X output group and the Y output group of the butterfly operation circuit 45-2 in the fifth stage are A ₄ 01, A ₄ 05, A ₄ 09, A _{4 respectively
13; B 4 00, B 4} 04, B 4 08, B 4 12 , and the 5-stage X output group of the butterfly operation circuit 45-3, Y output group each _{A 4 02, A 4 06,} A 4 12 , A ₄ 14; B ₄ 03, B ₄ 07, B ₄ 1
1, B ₄ 15, and the 5-stage butterfly operation circuit 45-4
X output group and Y output group of A ₄ 03 and A ₄ respectively
_{07, A 4 11, A 4} 15; B 4 02, B 4 06, B 4 10, B 4 has a 14.

In the example shown in FIG. 13, the selector 4
2-1 to 42-4, the butterfly operation circuit 45-
By selecting the X output for 1, 45-3 and the Y output for the butterfly operation circuits 45-2, 45-4, the lower half side of the FFT output (0 to N / 2-1 at the frequency index) is selected. ) That _{A 4 00, A 4 04,} A 4 08, A 4 12; B 4 00, B 4 0
_{4, B 4 08, B 4} 12; A 4 02, A 4 06, A 4 12, A 4 14; B 4 02, B 4 0
6, B ₄ 10 and B ₄ 14 are output as the final FFT result.

(E3) Description of Operation in 4-Stream Mode Next, in 4-stream mode (symbols A, B, C, respectively).
32-point data data A0, A1, (data string indicated by D)
..., A8; B0, B1, ..., B8; C0, C1, ..., C
8; The case of performing FFT processing on D0, D1, ..., D8 will be described with reference to FIG. In this case, first, for each of these eight-point data strings, the series circuits 37-1 to 37-4 of the serial FFT circuit 35 at the preceding stage, respectively.
Performs an 8-point FFT.

At this time, since the number of streams is 4,
[5-log ₂ 4] = 3 stages The basic stages of 30-1～30-
3 is used to perform FFT, and butterfly operation circuits 44-1 to 44-4, 44- of the parallel FFT circuit 36 on the subsequent stage side are performed.
1 to 45-4, bypass circuits 39A and 39B
To bypass the input data (through operation state)
are doing.

As a result, each series circuit 37-1 to 37-
In the three basic stages 30-1 to 30-3 of No. 4, 8-point FFT is performed for each stream on the 32-point data in the four stream mode, and the third basic stage 30-3
The X output and the Y output from the above are output as they are as the FFT result of the 4-stream mode, passing through the butterfly operation circuits 44-1 to 44-4 and 45-1 to 45-4 of the fourth and fifth stages. It

However, in the example shown in FIG. 14, among the butterfly operation circuits 21 of the third basic stage 30-3 for performing the final butterfly operation, the series circuits 37-1 and 37 are included.
-3 for the butterfly operation circuit 21 to the switching signal BM
"0" is given as the serial circuit 37-2, 37-4
Since "1" is given as the switching signal BM to the butterfly operation circuit 21 of FIG.
Data exchange (inversion) for X output and Y output of 1
Is being carried out.

Therefore, the butterfly operation circuit 45 of the fifth stage
-1 X output group and Y output group are A
_{3 0, A 3 2, A} 3 4, A 3 6; B 3 1, B 3 3, B 3 5, B 3 7 , and the 5-stage X output group of the butterfly operation circuit 45-2, Y output group each _{C 3 0, C 3 2,} C 3 4, C 3
_{6; D 3 1, D 3} 3, D 3 5, D 3 7 , and the 5-stage X output group of the butterfly operation circuit 45-3, respectively Y output group _{A 3 1, A 3 3,} A 3 5 _{, A 3 7; B 3 0} , B 3 2, B
₃ 4, B ₃ 6, and the 5-stage butterfly operation circuit 45-
The X output group and Y output group of 4 are C ₃ 1, respectively.
_{C 3 3, C 3 5,} C 3 7; D 3 0, and has a _{D 3 2, D 3 4,} D 3 6.

In the example shown in FIG. 14, the selector 4
2-1 to 42-4, the butterfly operation circuit 45-
1, 45-2 is selected as the X output, and butterfly operation circuits 45-3 and 45-4 are selected as the Y output. Lower half side (frequency index 0-N / 2-
1) That _{A 3 0, A 3 2,} A 3 4, A 3 6; C 3 0, C 3 2, C 3 4,
_{C 3 6; B 3 0,} B 3 2, B 3 4, B 3 6; D 3 0, D 3 2, D 3 4, D 3
6 is output as the final FFT result.

(E4) Description of operation in 8-stream mode Next, 32-point data data A0-A3; B0-B in 8-stream mode (data string indicated by symbols A to H, respectively)
3; C0 to C3; D0 to D3; E0 to E3; F0 to F
3; G0 to G3; H0 to H3 will be described with reference to FIGS.

In both of the examples shown in FIGS. 15 and 16, two streams of data A0 to A3; E0 to E3 are input to the serial circuit 37-1, and two streams of data B0 to B3; F0 to F3. To the serial circuit 37-2, two streams of data C0 to C3; G0 to G3 are input to the serial circuit 37-3, and two streams of data D0 to D3; H0 to H3 are serial circuit 37-4. Is input to each of the four-point data strings and the four-point FFT is performed by each of the series circuits 37-1 to 37-4 of the serial-type FFT circuit 35.

At this time, since the number of streams is 8,
[5-log ₂ 8] = 2-stage basic stage of 30-1,30-
2 is used to perform FFT, and each series circuit 37-1 to 37-37
-4 basic stage 30-3 and parallel FF
Butterfly operation circuits 44-1 to 44-4 of the T circuit 36,
In 44-1 to 45-4, the bypass circuits 32A,
32B, 39A, 39B are operated to bypass the input data (through operation state).

As a result, each series circuit 37-1 to 37-
In the two basic stages 30-1 and 30-2 of No. 4, 4-point FFT is performed for each stream on the 32-point data in the 8-stream mode, and the second basic stage 30-2
The X output and the Y output from the same are directly used as the FFT results of the 8-stream mode, and the third basic stage 30-3 and the fourth and fifth butterfly operation circuits 44-1 to 4-4.
It is output after passing through 4-4, 45-1 to 45-4.

However, in the example shown in FIG. 15, among the butterfly operation circuits 21 of the second basic stage 30-2 for performing the final butterfly operation, the series circuits 37-1 and 37 are included.
-3 for the butterfly operation circuit 21 to the switching signal BM
"0" is given as the serial circuit 37-2, 37-4
Since "1" is given as the switching signal BM to the butterfly operation circuit 21 of FIG.
Data exchange (inversion) for X output and Y output of 1
Is being carried out.

Therefore, the butterfly operation circuit 45 of the fifth stage
-1 X output group and Y output group are A
_{2 0, E 2 0, A} 2 2, E 2 2; B 2 1, F 2 1, B 2 3, F 2 3 , and the 5-stage X output group of the butterfly operation circuit 45-2, Y output group Are C ₂ 0, G ₂ 0, C ₂ 2 and G _{2 respectively
2; D 2 1, H 2} 1, D 2 3, H 2 3 , and the 5-stage X output group of the butterfly operation circuit 45-3, respectively Y output group _{A 2 1, E 2 1,} A 2 3 , E ₂ 3; B ₂ 0, F ₂ 0, B ₂ 2
, F ₂ 2 and butterfly calculation circuit 45-4 in the fifth stage
X output group and Y output group of C ₂ 1 and G ₂ respectively
1, C ₂ 3, G ₂ 3; D ₂ 0, H ₂ 0, D ₂ 2 and H ₂ 2.

In the example shown in FIG. 15, the selector 4
2-1 to 42-4, the butterfly operation circuit 45-
By selecting the X output for 1, 45-2 and the Y output for the butterfly operation circuits 45-3, 45-4, the F output for all the data strings indicated by the symbols A to H is selected.
Lower half side of FT output (0 to N / 2-1 by frequency index)
That is, A ₂ 0, E ₂ 0, A ₂ 2, E ₂ 2; C ₂ 0, G ₂ 0, C ₂ 2 and G ₂
2; B ₂ 0, F ₂ 0, B ₂ 2, F ₂ 2; D ₂ 0, H ₂ 0, D ₂ 2, H ₂ 2
Is output as the final FFT result.

In the example shown in FIG. 15, the data exchange (inversion) is set for each final butterfly operation circuit 21, but the butterfly operation of the second basic stage 30-3 for performing the final butterfly operation is performed. X output, Y in circuit 21
The output data exchange (reversal) may be performed for each data string (stream), and an example in which such control is performed is shown in FIG.

In the example shown in FIG. 16, the data exchange (inversion) of the X output and the Y output is performed by the butterfly operation circuit 21 of the second basic stage 30-3 for performing the final butterfly operation for each data string. I am doing it. That is, for the butterfly operation circuit 21 of the basic stage 30-2 of the series circuit 37-1, the switching signal BM for the data string A is input.
Is set to "0" and the switching signal BM for the data string E is set to "1".
By doing so, the data exchange (inversion) of the X output and Y output of the butterfly operation circuit 21 is performed only for the data string E.

Similarly, for the butterfly operation circuit 21 of the basic stage 30-2 of the series circuit 37-2, the switching signal BM for the data string B is "0" and the switching signal BM for the data string E is "1". By doing so, the data exchange (inversion) of the X output and Y output of the butterfly operation circuit 21 is performed only for the data string F. For the butterfly operation circuit 21 of the basic stage 30-2 of the series circuit 37-3, the switching signal BM for the data string C is set to "1" and the switching signal BM for the data string G is set to "0". , The data output of the butterfly operation circuit 21 is exchanged (inverted) only for the data string C.

Similarly, for the butterfly operation circuit 21 of the basic stage 30-2 of the series circuit 37-4, the switching signal BM for the data string D is set to "1" and the switching signal BM for the data string H is set to "1". ", The output X of the butterfly operation circuit 21 and the output Y of both the data strings D and H
The output data is swapped (reversed). Therefore,
5-stage X output group of the butterfly operation circuit 45-1, respectively Y output group _{A 2 0, E 2 1,} A 2 2, E
_{2 3; B 2 0, F} 2 1, B 2 2, F 2 3 , and the 5-stage X output group of the butterfly operation circuit 45-2, respectively Y output group _{C 2 1, G 2 0,} C 2 3, G ₂ 2; D ₂₁ , H ₂ 1, D ₂
3, H ₂ 3 and the fifth stage butterfly operation circuit 45-3
X output group and Y output group of A ₂ 1 and E ₂ respectively
_{0, A 2 3, E 2} 2; B 2 1, F 2 0, B 2 3, F 2 2 , and the 5-stage X output group of the butterfly operation circuit 45-4, Y
Each output group _{C 2 0, G 2 1,} C 2 2, G 2 3; D
₂ 0, H ₂ 0, has a D _{2 2,} H _{2 2.}

In the example shown in FIG. 15, the selector 4
2-1 to 42-4, the butterfly operation circuit 45-
By selecting the X output for 1, 45-2 and the Y output for the butterfly operation circuits 45-3, 45-4, the FFT for the data string indicated by the symbols A, D, F, G, H is selected. Lower half of output (0 to frequency index)
N / 2-1) and FF for the data string indicated by the symbols B, C, E
The upper half side of the T output (N / 2 to N-1 in the frequency index) is, that is, A ₂ 0, E ₂ 1, A ₂ 2, E ₂ 3; C ₂ 1, G ₂ 0, C
_{2 3, G 2 2; B} 2 1, F 2 0, B 2 3, F 2 2; D 2 0, H 2 0, D 2
2, H ₂ 2 is output as the final FFT result.

(E5) Description of operation in 16-stream mode Next, 32-point data data A0, A1; B0, in 16-stream mode (data string indicated by symbols A to P, respectively)
The case of performing FFT processing on B1; C0, C1; ... P0, P1 will be described with reference to FIG. FIG. 17
In the example shown in, the data A0, A1; E for four streams
0, E1; I0, I1; M0, M1 are serial circuits 37-1
Data of four streams B0, B1; F
0, F1; J0, J1; N0, N1 are serial circuits 37-2
Is input to four streams of data C0, C1; G
0, G1; K0, K1; O0, O1 are serial circuits 37-3
Is input to four streams of data D0, D1; H
0, H1; L0, L1; P0, P1 are series circuits 37-4
Is input to each of these two-point data strings, and the series circuits 37-1 to 37- of the serial-type FFT circuit 35 are respectively input.
FFT of 2 points is performed by 4.

At this time, since the number of streams is 16, the FFT is performed using the basic stage 30-1 of [5-log ₂ 16] = 1 stage, and each series circuit 37-1 to 37-4.
2nd and 3rd basic stages 30-2 and 30-3 and the butterfly operation circuit 44- of the parallel type FFT circuit 36
In 1 to 44-4 and 44-1 to 45-4, the bypass circuits 32A, 32B, 39A and 39B are operated to bypass the input data (through operation state).

As a result, each series circuit 37-1 to 37-
In the first basic stage 30-1 of No. 4, a two-point FFT is performed for each stream on the 32-point data in 16-stream mode, and the X output and Y output from the first basic stage 30-1 , 16 stream mode F as it is
As a result of FT, the second and third basic stages 30-
It is output after passing through the butterfly operation circuits 44-1 to 44-4, 45-1 to 45-4 of the second, 30-3 and fourth and fifth stages.

However, in the example shown in FIG. 17, among the butterfly operation circuits 21 of the first basic stage 30-1 for performing the final butterfly operation, the series circuits 37-1 and 37 are included.
-3 for the butterfly operation circuit 21 to the switching signal BM
"0" is given as the serial circuit 37-2, 37-4
Since "1" is given as the switching signal BM to the butterfly operation circuit 21 of FIG.
Data exchange (inversion) for X output and Y output of 1
Is being carried out.

Therefore, the butterfly operation circuit 45 of the fifth stage
-1 X output group and Y output group are A
_{1 0, E 1 0, I} 1 0, M 1 0; B 1 1, F 1 1, J 1 1, N 1 1 , and the 5-stage X output group of the butterfly operation circuit 45-2, Y output group Are C ₁ 0, G ₁ 0, K ₁ 0 and O _{1 respectively
0; D 1 1, H 1} 1, L 1 1, P 1 1 , and the respective fifth stage X output group of the butterfly operation circuit 45-3, Y output group _{A 1 1, E 1 1,} I 1 1 , M ₁₁ ; B ₁₀ , F ₁₀ , J
₁₀ and N ₁₀ , and the butterfly operation circuit 45- of the fifth stage
4 X output group and Y output group are C ₁ 1 and
Has a _{D 1 0, H 1 0,} L 1 0, P 1 0; G 1 1, K 1 1, O 1 1.

In the example shown in FIG. 15, the selector 4
2-1 to 42-4, the butterfly operation circuit 45-
By selecting the X output for 1, 45-2 and the Y output for the butterfly operation circuits 45-3, 45-4, the F output for all the data strings indicated by the symbols A to H is selected.
Lower half side of FT output (0 to N / 2-1 by frequency index)
That is, A ₁ 0, E ₁ 0, I ₁ 0, M ₁ 0; C ₁ 0, G ₁ 0, K ₁ 0, O ₁
0; B ₁ 0, F ₁ 0, J ₁ 0, N ₁ 0; D ₁ 0, H ₁ 0, L ₁ 0, P ₁ 0
Is output as the final FFT result.

In the case of the 16 stream mode, as described above with respect to the case of the 8 stream mode in FIG. 16, in the butterfly operation circuit 21 of the first basic stage 30-1, each data string (stream) is generated.
The data may be replaced (reversed) every time. (E6) Description of Specific Example of FFT Data Stream Configuration Next, FIGS. 18 to 23 show specific FFT data in each stream mode described above with reference to FIGS. 12 to 17.
The stream format and the selection state by the selector are shown.
The data string after the FFT processing is called an FFT data stream. This FFT data stream is shown in FIG.
~ It is configured by a combination of each control mode shown in FIG. 17 and the following segment size. The segment size is a unit for performing correlation processing for each stream, that is, FFT.
In terms of points, there are sizes from 32 to 16384 (16K), for example.

18 to 23 are respectively shown in FIGS.
It corresponds to FIG. 17, and in FIG. 18 to FIG. 23, the alphabetical symbols indicate multiplexed data strings (stream names), and the numbers attached to the upper left of each alphabet are segment numbers. The number attached to the lower right of is a sequential number.

18 to 23, the top row is the X output of the butterfly operation circuit 45-1 in the FFT device shown in FIG. 11, and the second row from the top is the butterfly operation circuit 45-1. Y output, and similarly, the third and fourth rows from the top are butterfly operation circuits 45-2, respectively.
The X output and the Y output of the butterfly operation circuit 45-3 are the X output and the Y output of the butterfly operation circuit 45-3. These are the X output and Y output of the butterfly operation circuit 45-4.

Further, in FIGS. 18 to 23, the selectors 42-1 to 42-4 in the succeeding stages of the butterfly computing circuits 45-1 to 45-4 in the final stage are used to select X of the butterfly computing circuits 45-1 to 45-4. Which of the output and the Y output is selected is indicated by "*" in each figure. The FFT apparatus of the present embodiment described above is used for FFT processing before performing correlation processing on the observation result by the radio telescope (in this case, the stream mode is the observation frequency band or the type of observation data string for each antenna), Positioning of underwater objects by observing underwater reflected sound using a sonar buoy and underground buried objects (oil, oil,
It is also used for FFT processing before performing correlation processing when determining the position of mineral veins, fossils, etc., and it is possible to easily obtain the frequency component on the desired side among the frequency components of the FFT result, so only effective components are Take out and FF with multiple points
Correlation processing with respect to the T result can be reliably performed.

[0139]

As described above in detail, according to the butterfly operation circuit of the present invention, the X output and the Y output can be arbitrarily switched by switching the addition processing and the subtraction processing of the pair of addition / subtraction circuits by the switching circuit. Therefore, it becomes possible to extract a desired frequency component when performing the fast Fourier transform (claims 1 and 2).

Further, according to the fast Fourier transform device using the butterfly operation circuit of the present invention, the X output from the butterfly operation circuit of the final stage and the data of the multi-stream format are both output and Since the Y output can be arbitrarily switched, it is possible to easily obtain the frequency component on the desired side among the frequency components of the result of the fast Fourier transform from the X output and the Y output, and the fast Fourier transform at multiple points There is an effect that the correlation processing for the result can be performed reliably and effectively (claims 3 to 8).

[Brief description of drawings]

FIG. 1 is a principle block diagram of the present invention.

FIG. 2 is a block diagram showing a configuration of a butterfly operation circuit used in the fast Fourier transform device of each embodiment of the present invention.

FIG. 3 is a block diagram showing a fast Fourier transform device as a first embodiment of the present invention.

FIG. 4 is a block diagram showing a configuration of a basic stage of the first embodiment.

FIG. 5 is a block diagram showing a fast Fourier transform device as a second embodiment of the present invention.

FIG. 6 is a block diagram showing a configuration of a basic stage of a second embodiment.

FIG. 7 is a block diagram showing a fast Fourier transform device as a third embodiment of the present invention.

FIG. 8 is a block diagram showing a fast Fourier transform device as a fourth embodiment of the present invention.

FIG. 9 is a block diagram showing a butterfly operation circuit having a bypass function of a fourth embodiment.

FIG. 10 is a block diagram showing a fast Fourier transform device as a fifth embodiment of the present invention.

FIG. 11 is a block diagram showing a specific configuration of a fast Fourier transform device as a fifth embodiment.

FIG. 12 is a block diagram for explaining the operation (flow of FFT data) of the fifth embodiment.

FIG. 13 is a block diagram for explaining the operation of the fifth embodiment (flow of FFT data).

FIG. 14 is a block diagram for explaining an operation (flow of FFT data) of the fifth embodiment.

FIG. 15 is a block diagram for explaining an operation (flow of FFT data) of the fifth embodiment.

FIG. 16 is a block diagram for explaining an operation (flow of FFT data) of the fifth embodiment.

FIG. 17 is a block diagram for explaining an operation (FFT data flow) of the fifth embodiment.

FIG. 18 is a diagram showing an FFT data stream format and a selection state by a selector in the fifth embodiment.

FIG. 19 is a diagram showing an FFT data stream format and a selection state by a selector in the fifth embodiment.

FIG. 20 is a diagram showing an FFT data stream format and a selection state by a selector in the fifth embodiment.

FIG. 21 is a diagram showing an FFT data stream format and a selection state by a selector in the fifth embodiment.

FIG. 22 is a diagram showing an FFT data stream format and a selection state by a selector in the fifth embodiment.

FIG. 23 is a diagram showing an FFT data stream format and a selection state by a selector in the fifth embodiment.

FIG. 24 is a block diagram showing a conventional serial type fast Fourier transform device.

FIG. 25 is a block diagram showing a configuration of a conventional basic stage (basic circuit).

[Fig. 26] Fig. 26 is a diagram for describing a general single stream data string generation operation.

FIG. 27 is a diagram for explaining a general Fast Fourier Transform algorithm.

FIG. 28 is a block diagram showing a conventional fast Fourier transform device in which a series type front stage part and a parallel type rear stage part are combined.

FIG. 29 is a block diagram for explaining the operation of the fast Fourier transform device shown in FIG. 28.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 butterfly operation circuit 2 multiplication circuit 3A, 3B addition / subtraction circuit 4 switching circuit 21 butterfly operation circuit 22 multiplication circuit 23A, 23B CLA (addition / subtraction circuit) 24 switching circuit 25 inverter circuit 26A, 26B exclusive OR circuit (EOR) 27 storage circuit 28 multiplexer 30-1 to 30-M basic stage 31 data rearrangement circuit 32A, 32B bypass circuit 33A, 33B bypass line 34A, 34B multiplexer 35 serial FFT circuit 36 parallel FFT circuit 37-1 to 37-n series circuit 38A , 38B Parallel circuit 39A, 39B Bypass circuit 40A, 40B Bypass line 41A, 41B Multiplexer 42-1 to 42-n Selector 43 Data selection unit 44-1 to 44-4, 45-1 to 45-4 Butterfly operation circuit

Claims (8)

[Claims] 1. A multiplication circuit for multiplying one of two input data by a twiddle factor, and either one of addition processing or subtraction processing for the multiplication result from the multiplication circuit and the other of the two input data. A butterfly operation circuit comprising: a pair of adder / subtractor circuits for performing the above operation; and a switching circuit capable of selectively switching one of the pair of adder / subtractor circuits that performs addition processing and that that performs subtraction processing. 2. A storage circuit, which stores a control flag for instructing a switching operation of the switching circuit, reads the control flag from the storage circuit for each processing cycle, and switches the switching circuit according to the control flag. The butterfly operation circuit according to claim 1, which operates. 3. A data rearrangement circuit that rearranges input data in units of two in order to perform a radix-2 fast Fourier transform on the input data and outputs the rearranged data in units of two. And a butterfly operation circuit that performs a butterfly operation on each input data, the basic stages being connected in series by the number of stages set according to the number of input data, and the butterfly of at least the final basic stage. An arithmetic circuit performs a multiplication circuit for multiplying one of the two input data by a twiddle factor, and one of an addition process or a subtraction process for the multiplication result from the multiplication circuit and the other of the two input data. A pair of addition / subtraction circuits to be performed, and a switching circuit capable of selectively switching between a pair of addition / subtraction circuits that perform addition processing and one that performs subtraction processing Characterized in that provided by being configured to, fast Fourier transform device using a butterfly operation circuit. 4. A plurality of multiplexed data strings are input as input data, and in order to perform a radix-2 fast Fourier transform for each data string, the input data are rearranged as appropriate in accordance with the order of operation 2.
A data rearrangement circuit that outputs the data in units, a butterfly operation circuit that performs a butterfly operation on two input data from the data rearrangement circuit, and an input that bypasses these data rearrangement circuit and butterfly operation circuit A basic stage consisting of a bypass circuit capable of outputting data as it is, is connected in series by the number of stages set according to the number of input data, and butterfly operation for fast Fourier transform is performed on the plurality of data strings. In a basic stage other than the basic stage, the bypass circuit is operated, and at least the butterfly operation circuit of the basic stage that performs the final butterfly operation has a multiplication circuit that multiplies one of the two input data by a twiddle factor, and the multiplication circuit. Addition processing for the multiplication result from the circuit and the other of the two input data, or It is configured to include a pair of addition / subtraction circuits that perform either one of the subtraction processes, and a switching circuit that can selectively switch between the one that performs the addition process and the one that performs the subtraction process among the pair of addition / subtraction circuits. A fast Fourier transform device using a butterfly operation circuit. 5. The input data is rearranged appropriately in accordance with the order of the operation so as to perform a radix-2 fast Fourier transform on the input data.
A plurality of parallel series circuits in each of which a predetermined number of basic stages are connected in series, each of which is composed of a data rearrangement circuit that outputs in units of two and a butterfly operation circuit that performs a butterfly operation on two input data from the data rearrangement circuit And a parallel type circuit in which a plurality of butterfly operation circuits are arranged and connected in a matrix form in parallel, and two output data of each series circuit in the series type fast Fourier transform circuit are provided. And a parallel type fast Fourier transform circuit which is respectively input to the pair of parallel circuits, wherein at least the butterfly operation circuit at the final stage of the parallel type fast Fourier transform circuit has a twiddle factor in one of the two input data. A multiplication circuit for multiplying by, and addition processing or subtraction for the multiplication result from the multiplication circuit and the other of the two input data And a pair of adder / subtractor circuits for performing either one of the processes, and a switching circuit for selectively switching between one of the pair of adder / subtractor circuits that performs addition processing and one that performs subtraction processing. A characteristic fast Fourier transform device using a butterfly arithmetic circuit. 6. A plurality of multiplexed data strings are input as input data, and in order to perform a radix-2 fast Fourier transform for each data string, the input data are appropriately rearranged according to an order according to the operation.
A data rearrangement circuit that outputs the data in units, a butterfly operation circuit that performs a butterfly operation on two input data from the data rearrangement circuit, and an input that bypasses these data rearrangement circuit and butterfly operation circuit A series type fast Fourier transform circuit in which multiple sets of series circuits, each consisting of a basic stage consisting of a bypass circuit that can output data as it is, are connected in parallel and a plurality of butterfly operation circuits with bypass function are arranged in matrix form. And a parallel type fast Fourier transform circuit in which two output data of each series circuit in the series type fast Fourier transform circuit are respectively input to the pair of parallel circuits. And the serial high-speed flux performing butterfly operation for fast Fourier transform on the plurality of data sequences. In the basic stages other than the basic stage in the Rie transform circuit, the bypass circuit is operated, and the butterfly operation other than the butterfly operation circuit in the parallel type fast Fourier transform circuit for performing the butterfly operation for the fast Fourier transform on the plurality of data strings is performed. The circuit operates the bypass function, and at least the butterfly operation circuit of the basic stage in the serial type fast Fourier transform circuit that performs the final butterfly operation, or the parallel operation fast Fourier transform circuit that performs the final butterfly operation. A butterfly operation circuit multiplies one of two input data by a twiddle factor, and one of an addition process and a subtraction process for the multiplication result from the multiplication circuit and the other of the two input data. A pair of adder / subtractor circuits for A fast Fourier transform device using a butterfly operation circuit, comprising a switching circuit capable of selectively switching an addition process and a subtraction process from a pair of addition / subtraction circuits . 7. When the butterfly arithmetic circuit at the final stage is provided with a data selection unit for selecting and outputting any one of the two output data from the butterfly arithmetic circuit, the plurality of data are provided. 7. The fast Fourier transform device using the butterfly operation circuit according to claim 4 or 6, wherein output data to be selected by the data selection unit is set in advance corresponding to a column. 8. A storage circuit for storing a control flag for instructing a switching operation of the switching circuit in the butterfly operation circuit, reading a control flag from the storage circuit for each processing cycle, and controlling the control by the switching circuit. A fast Fourier transform device using a butterfly operation circuit according to any one of claims 3 to 7, characterized by performing a switching operation according to a flag.