JPH08320858A - Unit and method for fourier transformation arithmetic operation - Google Patents

Abstract

PURPOSE: To lower the cost and reduce the size by simplifying the constitution of a butterfly computing element. CONSTITUTION: Data which are inputted are divided by a distribution switch 21-2 into former-half data and latter-half data in symbol units. The former-half data are supplied to a delay circuit 22A-1 and delayed by N/2. The data delayed by the delay circuit 22A-1 are supplied to the delay circuit 22A-1 again. Further, the latter-half data are supplied to a delay circuit 22B-1 and delayed by N/2. The delayed data are supplied to the delay circuit 22B-1 again and delayed. Thus, the former-half data and latter-half data are inputted twice to input terminals of the butterfly computing element 24-1. The butterfly computing element 24-1 performs one (addition) of butterfly operations for the 1st input and the 2nd operation (subtraction) of the butterfly operations for the 2nd input. Namely, the butterfly computing element 24-l performs the butterfly operations on a time division basis.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Fourier transform computing device and method, and more particularly to a Fourier transform computing device and method capable of simplifying the configuration of a butterfly computing unit.

[0002]

2. Description of the Related Art Conventionally, a fast Fourier transform is performed by software using a digital signal processor (DSP). However, since the method using software takes time, an IC chip (dedicated hardware) for performing a fast Fourier transform calculation process has recently been used.

In this hardware, one butterfly operation circuit is repeatedly used, or a plurality of butterfly operation circuits are provided in parallel.

However, if the operation is performed by one butterfly operation circuit, a memory (RAM) for accumulating the next input data and a multiplication clock for performing the operation processing at high speed are required.

When using a plurality of butterfly operation circuits, a plurality of RAMs are required to store the intermediate operation result.

As a result, when the number of points N of the Fourier transform becomes large, the circuit scale also becomes large, an external IC chip is required, and a high-speed multiplication clock is also required, making it difficult to realize one chip. .

Therefore, for example, as shown in FIG. 11, pipeline processing of data can be considered. In the example of FIG. 11, the input data is the data of the first half of one symbol (data supplied earlier in time) and the data of the latter half (time) by the distribution switch 1 of the processing circuit of the first stage. Data that is supplied after being delayed).
The data in the first half is supplied to the delay circuit 2 that delays the data by N / 2 (N is the number of data (the number of points) of one symbol), and after being delayed by N / 2, the butterfly computing unit 4
It is supplied to one (first) input terminal (upper input terminal in the figure).

The latter half of the data divided by the allocating switch 1 is supplied to a rotor multiplier 3 which performs rotor multiplication, and after the rotor multiplication is performed, the other of the butterfly computing units 4 ( It is supplied to the second) input terminal (the lower input terminal in the figure). The butterfly computing unit 4 performs a butterfly computation on two inputs, and outputs the computation result to the processing circuit at the subsequent stage (second stage).

In the second stage processing circuit, the data output from one (first) output terminal (upper output terminal in the figure) of the butterfly arithmetic unit 4 of the first stage is replaced by the exchange switch 6-. 1 is supplied to one (first) input terminal (upper input terminal in the figure) of the butterfly computing unit 4
The data output from the other (second) output terminal (the lower output terminal in the drawing) of the above is delayed by N / 4 by the delay circuit 5-1 and then the other (second) of the exchange switch 6-1.
Input terminal (the lower input terminal in the figure).
The interchange switch 6-1 appropriately exchanges the data input from the two input terminals and then outputs the data from the two output terminals.

The data output from one (first) output terminal of the exchange switch 6-1 is delayed by N / 4 by the delay circuit 7-1 and then one (first) of the butterfly computing units 9-1. ) Is supplied to the input terminal. In addition, the data output from the other (second) output terminal of the exchange switch 6-1 is subjected to rotator multiplication in the rotator multiplier 8-1, and then the data is output from the butterfly computing unit 9-1. It is supplied to the other (second) input terminal. The butterfly computing unit 9-1 performs a butterfly computation on the data input from the two input terminals and outputs the data from the two output terminals.

Hereinafter, the processing circuits of the third and subsequent stages are also
It is configured similarly to the processing circuit of the second stage. However,
The delay time of each of the delay circuits 5-i and 7-i in the processing circuit of each stage is shorter by half than the delay time of the processing circuit of the preceding stage.

Then, in the processing circuit of the stage next to the stage where the delay time in the delay circuits 5-k and 7-k is 1, one of the butterfly computing units 9-k (first) of the processing circuit of the previous stage. The data output from the output terminal of the switching switch 11 is directly supplied to one (first) input terminal of the changeover switch 11, and the data output from the other (second) output terminal is N / 2 by the delay circuit 10A. After being delayed by only that, it is supplied to the other input terminal of the changeover switch 11. The changeover switch 11 is configured to restore the data input from the two input terminals to the original serial data and output the data. The output of the changeover switch 11 is rearranged by the rearrangement circuit 12.

In practice, the butterfly operation is realized, for example, in the first stage processing circuit only when both the processing of the butterfly computing unit 4 and the processing of the rotor multiplier 3 are performed. However, in this specification, for convenience of description, the processing not including the rotor multiplication is referred to as a butterfly operation (butterfly operation in a narrow sense).

Next, the operation will be described. The distribution switch 1 divides the data input in symbol units into the first half of the data (half of the data input earlier in time) and the latter half of the data (half of the data input later in time). Then, the first half data is supplied to the delay circuit 2, and the second half data is supplied to the rotor multiplier 3. The delay circuit 2 delays the input first half data by N / 2 (that is, delays by half the data of one symbol), and supplies it to one input terminal of the butterfly computing unit 4.

At this time, to the other input terminal of the butterfly computing unit 4, the latter half data output from the distribution switch 1 and subjected to the rotor multiplication by the rotor multiplier 3 is input ( Although the multiplication time of the rotor multiplier 3 is neglected, when this time cannot be neglected, the delay time of the delay circuit 2 is set in consideration of this time as well. Is also the same). That is,
The delay circuit 2 allows the first half data and the second half data of the same symbol to be synchronized in timing with the butterfly computing unit 4
At the same time (however, one data at a time starting from the first data). The butterfly computing unit 4 performs a radix-2 butterfly computation on corresponding data of two inputs.

FIG. 12 shows the principle of a radix-2 butterfly operation. Note that in FIG. 12, the number of data N for one symbol is 16.

That is, the butterfly computing unit 4 is shown in FIG.
Of the 16 pieces of data represented by the numbers 0 to 15 of the symbol g, the first number 0 data of the first half data of the number 0 to number 7 and the first half data of the second half of the numbers 8 to 15 The number 8 data is added and subtracted. Then, the added value is the data of number 0 in the p column in FIG. 12, and the subtracted value is the data of number 8.

Next, the second number 1 in the first half of the symbol g
And the second half of the second number 9 data and the difference are calculated, and the sum is set as the number 1 data of the p column, and the difference is set as the number 9 data. Thereafter, similar processing is performed to obtain 16 pieces of data of numbers 0 to 15 shown in the p column. The eight pieces of data indicated by numbers 0 to 7 in the first half of the p column and the eight pieces of data in the latter half indicated by numbers 8 to 15 are
Each one is sequentially supplied in parallel to the subsequent processing circuits.

In the processing circuit of the second stage, the eight pieces of data in the first half of numbers 0 to 7 of the p-column output from the butterfly computing unit 4 of the processing circuit of the first stage are replaced by the exchange switch 6-1. No. 8 is directly supplied to one of the input terminals.
The data in the latter half of the eight data of Nos. 15 to 15 are the delay circuits 5-1.
To the other input terminal of the exchange switch 6-1 after being delayed by N / 4 (that is, by 1/4 symbol).

The exchange switch 6-1 executes a process of appropriately exchanging the data input to the two input terminals shown in the upper and lower parts of the figure.

That is, as shown in FIG. 12, of the data of Nos. 0 to 7 in the p-column supplied from the upper input terminal in the figure, the four data of Nos. 0 to 3 in the first half are delayed by the delay circuit. Supply to 7-1. The four pieces of data of Nos. 4 to 7 in the latter half of the p column are output to the rotor multiplier 8-1. Further, when the four data of the numbers 4 to 7 in the latter half of the p-column are input to the upper input terminal of the exchange switch 6-1, the numbers 8 to 8 of the p-column are simultaneously supplied to the lower input terminal. The four data of 11 are the delay circuit 7-1.
Is supplied to. The four pieces of data of Nos. 12 to 15 in the p-column that are input thereafter are supplied to the rotor multiplier 8-1.

That is, the first of the exchange switches 6-1
No. 0 to 3, No. 8 to No. 11 data in the p-th column are sequentially output from the output terminal of No. 4, and No. 4 from the second output terminal.
7 to 12 and 15 to 15 are sequentially output.

The delay circuit 7-1 delays the inputted four pieces of data of the columns 0 to 3 of the p column by N / 4 and then inputs them to one input terminal of the butterfly computing unit 9-1. . At this time, to the other input of the butterfly computing unit 9-1, the four pieces of data indicated by the numbers 4 to 7 subjected to the rotor multiplication by the rotor multiplier 8-1 are input. That is, the delay circuit 7-1 inputs the data of No. 0 to No. 3 and the data of No. 4 to No. 7 to the butterfly computing unit 9-1 at the same time at the same timing.

The butterfly computing unit 9-1 has a p-column number 0.
And the difference between the data of No. 4 and the data of No. 4 are calculated, and the sum is q
The number 0 data in the column is used, and the difference is number 4 data.
Further, the sum and difference of the data of number 1 and the data of number 5 in the p column are calculated, the sum is set as the data of number 1 in the q column, and the difference is number 5
Data. Thereafter, similar processing is performed, and eight pieces of data indicated by numbers 0 to 7 in the q-th column are obtained from the data indicated by numbers 0 to 7 in the p-th column.

The delay circuit 7-1 includes four numbers 0 to 3
After delaying N pieces of data by N / 4, four pieces of data of Nos. 8 to 11 that are subsequently input are delayed by N / 4 and input to one input terminal of the butterfly computing unit 9-1. . At this time, four pieces of data No. 12 to No. 15 are input to the other input terminal of the butterfly computing unit 9-1 after being multiplied by the rotor by the rotor multiplier 8-1. It That is, the two input terminals of the butterfly computing unit 9-1 have four pieces of data of numbers 8 to 11 and
The four pieces of data of numbers 12 to 15 are simultaneously input at the same timing.

The butterfly computing unit 9-1 has a p-column number 8
And the difference between the data of No. 12 and the data of No. 12 are calculated, the sum is set as the data of No. 8 in the q column, and the difference is set as the data of No. Further, the sum and difference between the data of number 9 and the data of number 13 in the p column are calculated, the sum is set as the data of number 9 in the q column, and the difference is set as the data of number 13.

Thereafter, the same processing is performed, and the p column number 8
From the eight data of No. 15 to No. 15, eight data of No. 8 to No. 15 of the q-th column are obtained.

The data of Nos. 0 to 7 and the data of Nos. 8 to 15 in the q-th column output from the butterfly computing unit 9-1 at the second stage are respectively parallel to the processing circuit at the third stage. Is entered.

Thereafter, similar processing is sequentially performed in the processing circuits of each stage.

Of the data processed by the butterfly computing unit 9-k of the processing circuit of the stage including the delay circuits 5-k and 7-k for delaying the data by one, the upper part of the data in the figure is used. The data output from the output terminal is supplied to the upper input terminal of the changeover switch 11, and the data output from the lower output terminal thereof is set to N by the delay circuit 10A.
After being delayed by / 2, it is input to the input terminal below the changeover switch 11.

The changeover switch 11 has the numbers 0, 2, 4, 6, 8, and 8 in the G column of FIG. 12 input to the upper input terminals.
The data of 10, 12, and 14 are first selected and output, and then the numbers of G columns 1, 3, and 3 input from the delay circuit 10A.
Data of 5, 7, 9, 11, 13, 15 are selected and output. The rearrangement circuit 12 converts this data into 0, 1, 2, ...
.., 14 and 15 are rearranged in this order and output.

This operation is sequentially repeated. As a result, the data serially input to the distribution switch 1 is
After pipeline processing in parallel in each stage, the data is converted back to serial data by the changeover switch 11 and output as serial data having the same clock rate as the serial data input to the distribution switch 1.

The distribution switch 1 of each stage, the replacement switches 6-1 to 6-k, and the changeover switch 11
Is controlled at a predetermined timing by a timing control circuit (not shown).

The number of delay circuits required in this example is 2 (N-1).

In the example of FIG. 11, in each stage, the rotor multiplier 8-i (rotor multiplier 3) is replaced by a replacement switch 6-i (distribution switch 1) as shown in FIG. ) Lower output terminal and butterfly calculator 9-
It is arranged to be inserted between the lower input terminal of i (butterfly computing unit 4), but may be connected to the lower output terminal of the butterfly computing unit 9-i as shown in FIG. Is.

Alternatively, as shown in FIG. 15, a rotor multiplier 8-i can be inserted between the delay circuit 5-i and the input terminal below the interchange switch 6-i. In any case, the same calculation result as in the case of FIG. 13 can be obtained. However, the value of the multiplication value of the rotor multiplication differs depending on the insertion position.

FIG. 16 shows an example in which a radix-4 butterfly operation corresponding to the radix-2 butterfly operation in FIG. 11 is performed. That is, in this example, the first
The distribution switch 1 in the second stage divides the data of each input symbol into four and outputs them. The first quarter data is delayed by the delay circuits 2A, 2B and 2C.
Each is delayed by N / 4, and after being delayed by a total of 3N / 4, the signals are input to the first input terminal of the butterfly computing unit 4. The second quarter data is the delay circuits 2D, 2
It is delayed by N / 4 by E, and delayed by a total of N / 2, and is input to the rotor multiplier 3A. The rotor multiplier 3A performs rotor multiplication on the input data and then inputs the multiplication result to the second input terminal of the butterfly computing unit 4.

The third 1/4 data output from the distribution switch 1 is delayed by N / 4 by the delay circuit 2F and then input to the rotor multiplier 3B. The rotator multiplier 3B performs rotator multiplication on the input data and then outputs the multiplication result to the third value of the butterfly computing unit 4.
Input to the input terminal of. The fourth 1/4 data output from the distribution switch 1 is input to the fourth input terminal of the butterfly computing unit 4 after being subjected to rotor multiplication by the rotor multiplier 3C. .

The butterfly computing unit 4 performs butterfly computation on the data input from the four input terminals, and then sequentially outputs the data as four parallel data to the second stage processing circuit.

In the processing circuit of the second stage, the data output from the first output terminal of the butterfly computing unit 4 of the first stage is directly input to the first input terminal of the exchange switch 6-1. It The data output from the second output terminal of the butterfly computing unit 4 is transferred to N by the delay circuit 5F-1.
After being delayed by / 16, it is input to the second input terminal of the exchange switch 6-1. The third of the butterfly computing unit 4
The data output from the output terminal of the delay circuit 5D-
1,5E-1 delays each N / 16,
After being delayed by a total of N / 8, the replacement switch 6-1
Is input to the third input terminal of. The data output from the fourth output terminal of the butterfly computing unit 4 is delayed by the delay circuit 5A.
The signals are delayed by N / 16 by -1, 5B-1 and 5C-1, respectively, and after being delayed by a total of 3N / 16, they are input to the fourth input terminal of the exchange switch 6-1.

The exchange switch 6-1 appropriately selects the data input from the four input terminals and outputs the data from the four output terminals.

The data output from the first output terminal of the exchange switch 6-1 is the delay circuits 7A-1 and 7B-.
1,7C-1 delays each N / 16,
After being delayed by a total of 3N / 16, the butterfly computing unit 9
-1 is input to the first input terminal. The data output from the second output terminal of the exchange switch 6-1 is delayed by N / 16 by the delay circuits 7D-1 and 7E-1, respectively, and after being delayed by a total of N / 8, the data is output to the rotor. It is input to the multiplier 8A-1. The rotor multiplier 8A-1 is
After the input data is multiplied by the rotor, it is input to the second input terminal of the butterfly computing unit 9-1.

The data output from the third output terminal of the exchange switch 6-1 is transferred to N / N by the delay circuit 7F-1.
After being delayed by 16, it is input to the rotor multiplier 8B-1. The rotator multiplier 8B-1 performs rotator multiplication on the input data, and then inputs the data to the third input terminal of the butterfly computing unit 9-1. The data output from the fourth output terminal of the exchange switch 6-1 is subjected to rotator multiplication by the rotator multiplier 8C-1, and then the fourth input terminal of the butterfly computing unit 9-1. Entered in.

Hereinafter, similar processing is sequentially performed in each subsequent stage. In the example of FIG. 11, the delay time of the delay circuit in each stage is 1/2
The length is shortened by 1/4, but in this example, it is shortened by 1/4.

The data output from the first to fourth output terminals of the butterfly computing unit 9-k at the stage where the delay time in the delay circuit is one data is the same as it is, or the delay circuit 10F, the delay circuit. The signals are delayed by N / 4 by the delay circuits 10D and 10E and the delay circuits 10A to 10C, respectively, and then input to the first to fourth input terminals of the changeover switch 11. The changeover switch 11 appropriately selects data input in parallel from the first to fourth input terminals and outputs it as serial data. The sorting circuit 12 is
The output of the changeover switch 11 is rearranged and output.

Next, the operation will be described. The distribution switch 1 uses the data input in symbol units for 4
It is divided into two and is output from the first to fourth output terminals.
For example, as shown in FIG. 17, when one symbol is composed of 16 pieces of data, 4 pieces of data of the symbols g, numbered 0 to 3, are output from the first output terminal and numbered 4 4 to 7 are outputted from the second output terminal, 4 data shown from 8 to 11 are outputted from the third output terminal, and 12 to 15 are outputted.
The four data indicated by are output from the fourth output terminal.

The most preceding numbers 0 to 3 in terms of time
The four pieces of data of 4 are obtained by the delay circuits 2A, 2B and 2C.
Delayed by a total of 3N / 4, the first of the butterfly computing unit 4
Input to the input terminal of. The four pieces of data indicated by the numbers 4 to 7 are delayed by a total of N / 2 by the delay circuits 2D and 2E, and then are multiplied by the rotor by the rotor multiplier 3A. Is input to the second input terminal of.

The four pieces of data Nos. 8 to 11 are delayed by N / 4 by the delay circuit 2F, and then input to the rotor multiplier 3B, subjected to the rotor multiplication, and subjected to the butterfly operation. It is input to the third input terminal of the container 4. Then, the four pieces of data indicated by numbers 12 to 15 are input to the fourth input terminal of the butterfly computing unit 4 after being subjected to the rotor multiplication by the rotor multiplier 3C. In this way, four pieces of data are sequentially input simultaneously to the four input terminals of the butterfly computing unit 4 at the same timing.

The butterfly computing unit 4, as shown in FIG. 17, performs butterfly computation on the data of No. 0, No. 4, No. 8 and No. 12 respectively inputted from four input terminals. Then, the calculation result is set as the data of number 0, number 4, number 8 and number 12 in the p column shown in FIG.

Next, the data of the numbers 1, 5, 9 and 13 of the symbol g are subjected to butterfly operation to obtain the data of numbers 1, 5, 9 and 13 of the p column.

In the same manner, 16 pieces of data in the p column are calculated from the 16 pieces of data of the symbol g. Then, these calculation results are output to the second stage processing circuit.

In the second processing circuit, the data in the p-column of the numbers 0 to 3 are input to the first input terminal of the exchange switch 6-1 and the data in the numbers 4 to 7 are input to the delay circuit 5F-. After being delayed by N / 16 by 1, it is input to the second input terminal. The data of the numbers 8 to 11 are delayed by a total of N / 8 by the delay circuits 5D-1 and 5E-1, and then input to the third input terminal, and the data of the number 12 are input.
The data of Nos. 15 to 15 are delay circuits 5A-1, 5B-1,
After being delayed by a total of 3N / 16 by 5C-1, the fourth
Input to the input terminal of.

The exchange switch 6-1 selects the data of the number 0 in the p column output from the first output terminal of the butterfly computing unit 4 which is input from the first input terminal first,
This data is output from the first output terminal. The number 0 output from the first output terminal of the exchange switch 6-1
Data is delayed by 3N / 16 by the delay circuits 7A-1, 7B-1, and 7C-1, and the butterfly calculator 9-
1 is input to the first input terminal.

At the next timing, the data of the numbers 1 and 4 are input to the first input terminal and the second input terminal of the exchange switch 6-1. The data of number 1 is output from the second output terminal, and the data of number 4 is output from the first output terminal.

Similarly, the next timing number 2,
The data of 5, 8 are output from the third, second or first output terminals, and the data of numbers 3, 6, 9, 12 are the fourth,
Output from the third, second or first output terminal, the data of numbers 7, 10, and 13 are output from the fourth, third, and second output terminals, and the data of numbers 11 and 14 are the fourth, Third
And the data of number 15 is output from the fourth output terminal.

The data of the numbers 0, 4, 8 and 12 on the p-th column output from the first output terminal are the delay circuits 7A-1 and 7B.
After being delayed by a total of 3N / 16 by -1, 7C-1, they are input to the first input terminal of the butterfly computing unit 9-1.

The data of the numbers 1, 5, 9 and 13 in the p-th column output from the second output terminal are the delay circuits 7D-1 and 7E.
After being delayed by N / 8 by -1, the rotor multiplier 8A-1 further performs rotor multiplication, and the result is input to the second input terminal of the butterfly computing unit 9-1.

The data of the numbers 2, 6, 10, and 14 in the p-th column output from the third output terminal are delayed by N / 16 by the delay circuit 7F-1, and further the rotor multiplier 8B.
The multiplication for the rotor is performed by -1, and is input to the third input terminal of the butterfly computing unit 9-1. Then, the numbers 3, 7, 11, 15 of the p-th column output from the fourth output terminal
Data is subjected to rotator multiplication by the rotator multiplier 8C-1 and then input to the fourth input terminal of the butterfly computing unit 9-1.

As described above, the butterfly computing unit 9-
The data of Nos. 0 to 3 in the p-th column are simultaneously input to the first to fourth input terminals of No. 1 at the same timing. The butterfly computing unit 9-1 performs a butterfly computation on these four pieces of data to obtain data of numbers 0 to 3 in the G column.

Similarly, when the data of the numbers 4 to 7 are input, the four pieces of data of the numbers 4 to 7 in the G column are output from the butterfly computing unit 9-1. Further, when the data of the numbers 8 to 11 or the data of the numbers 12 to 15 are input, the numbers 8 to 8 in the G column of FIG. 17 are output from the first to fourth output terminals of the butterfly computing unit 9-1. The data of number 11 or the data of numbers 12 to 15 are obtained.

When the number of data of 1 symbol is 16, the operation by the butterfly computing unit is completed as described above. However, when the number of data of 1 symbol is more than 16, in the processing circuit of the subsequent stage. , Similar processing is performed.

Then, of the four pieces of data of numbers 0 to 3 in the G column for which the butterfly calculation has been completed, the data of number 0 is not delayed and the data of number 1 is delayed by N / 4 by the delay circuit 10F. , The data of No. 2 is the delay circuit 1
The data of No. 3 is delayed by N / 2 by 0D and 10E, and delayed by 3N / 4 by the delay circuits 10A, 10B, and 10C, and the first to fourth of the switching circuit 11 respectively.
Input to the input terminal of.

The changeover switch 11 has the numbers 0, 4, and 4 input from the first input terminal during the first N / 4 period.
8 and 12 data are selected, and in the next N / 4 period, the second
The data of numbers 1, 5, 9 and 13 input from the input terminals of No. 2 and No. 3, 6, 10 and 14 or the data of number 3, input from the third and fourth input terminals are selected. The data of 7, 11, and 15 are selected and output.

By repeating such an operation, the data of each number is sequentially output in series, and is further rearranged in the rearrangement circuit 12 in the order of the numbers 0 to 15.

Although the number of delay circuits when the radix shown in FIG. 11 is 2 is 2 (N-1), the radix in FIG. 16 is 4
In this case, the number of delay circuits is 4 (N-1) (when the radix is R, the number is R (N-1)).

In any of the examples, the position of the rotor multiplier is not restricted, and there is no restriction on the radix when performing the fast Fourier transform. Further, there is no regulation on how to make the delay amount. Further, in the above example, the input / output of the data string in each stage is parallel data.

[0067]

As described above, in the conventional Fourier transform computing device, the butterfly computing unit
Since a plurality of calculations are performed at one time, the configuration of the butterfly calculator becomes complicated, resulting in an increase in the size of the entire apparatus and a problem of high cost.

The present invention has been made in view of such a situation, and it is possible to simplify the structure of the butterfly computing unit and to reduce the size and cost.

[0069]

According to another aspect of the present invention, there is provided a Fourier transform calculation device, wherein first data inputted first in time and second data inputted second in time. And a timing adjusting means for outputting the first data and the second data divided by the dividing means a plurality of times at the same timing, and a timing adjusting means for adjusting the timing. 1st data and 2nd data are butterfly-operated in time division
And a second arithmetic means for performing a rotor arithmetic operation on a predetermined one of the data input to the first arithmetic means or the data output from the first arithmetic means. And

In the Fourier transform calculation method according to the fourth aspect, the inputted data is converted into the first inputted first in time.
Data and second data input later in time, and the divided first data and second data are output a plurality of times at the same timing, and the first timing is adjusted. The data and the second data are subjected to butterfly operation in a time division manner, and the operation for the rotor is performed on a predetermined data of the data after the butterfly operation or the data before the butterfly operation.

[0071]

In the Fourier transform computing device according to the present invention, the dividing means divides the inputted data into the first data inputted earlier in time and the second data inputted later in time.
And the timing adjusting means outputs the first data and the second data divided by the dividing means a plurality of times at the same timing, and the first computing means performs timing by the timing adjusting means. The first data and the second data adjusted by are subjected to butterfly computation in time division,
The second arithmetic means performs a rotor arithmetic operation on predetermined data input to the first arithmetic means or data output from the first arithmetic means.

In the Fourier transform operation method according to the fourth aspect, the input data is divided into the first data input earlier in time and the second data input later in time. The first data and the second data that are divided are output at a plurality of times at the same timing, and the first data and the second data whose timings have been adjusted are subjected to a butterfly operation in a time division manner to make a butterfly operation. The calculation for the rotor is performed on the predetermined data after the calculation or the data before the butterfly calculation.

[0073]

EXAMPLES Examples of the present invention will be described below. In order to clarify the correspondence between each means of the invention described in the claims and the following examples, parentheses after each means The features of the present invention will be described below by adding a corresponding embodiment (however, one example).

In the Fourier transform operation device according to the first aspect of the present invention, the inputted data is converted into the first data inputted first in time.
Of data and the second data input later in time (for example, the distribution switch 21 in FIG. 1).
-1 to 21-k) and the first divided by the dividing means.
Data and second data are output a plurality of times at the same timing (for example, the changeover switches 26A-1 to 26B-k in FIG. 1, the delay circuit 22A-1).
22B-k) and the first and second data whose timings have been adjusted by the timing adjusting means, are subjected to a butterfly operation in a time division manner (for example, butterfly arithmetic unit 24-1 to 24-1 in FIG. 1). 24-k) and the second arithmetic means (for example, in FIG. 1) that performs the arithmetic operation for the rotor on a predetermined one of the data input to the first arithmetic means or the data output from the first arithmetic means. Rotor multiplier 23-
1 to 23-k).

In the Fourier transform operation device according to the second aspect, the timing adjusting means delays the first data by the first delay means (for example, the delay circuits 22A-1 to 22A of FIG. 1).
2A-k) and the data input to the first delay means are selected, and the first data delayed by the first delay means is supplied again to the first delay means to delay the first data. Selection means (for example, changeover switches 26A-1 to 26A-k in FIG. 1) and second delay means for delaying the second data (for example, delay circuits 22B-1 to 22B-k in FIG. 1)
And selecting the data input to the second delay means,
Second data to be supplied to the second delay means for delaying
Selection means (for example, the changeover switch 26B-1 in FIG. 1)
To 26B-k).

In the Fourier transform operation device according to the third aspect, the dividing means has a plurality of delay means for sequentially delaying the input data by a predetermined time (for example, the delay circuit 2 in FIG. 5).
2A-1 to 22B-k), and the timing adjusting means selects the first data delayed by the first time by the delay means and the second data not delayed, and delays by the first time. Selecting means for selecting data obtained by further delaying the first data obtained by delaying the first data and data obtained by delaying the second data by the first time (for example, changeover switches 26A-1 to 26B-k in FIG. 5). ) Is provided.

However, this description does not mean that each means is limited to the above.

FIG. 1 is a block diagram showing an example of the configuration of an embodiment of the Fourier transform computing device of the present invention. In this embodiment, the distribution switch 21- of the first-stage processing circuit is
The data input with 1 is divided into the first half data that precedes in time and the second half data that follows in time, and the first half data is delayed via the second input terminal of the changeover switch 26A-1. It is supplied to the circuit 22A-1. Data is N /
The output of the delay circuit 22A-1 that delays by 2 (N is the number of data of 1 symbol) is input to the delay circuit 22A-1 again via the first input terminal of the changeover switch 26A-1. Has been done.

Similarly, the latter half data distributed by the distribution switch 21-1 is changed over to the changeover switch 26.
It is input to the delay circuit 22B-1 via the first input terminal of B-1. The data output from the delay circuit 22B-1 that delays the data by N / 2 is input again to the delay circuit 22B-1 via the second input terminal of the changeover switch 26B-1. There is.

The butterfly computing unit 24-1 includes the delay circuit 2
The data output from 2A-1 and the data output from the changeover switch 26B-1 are fetched, subjected to a butterfly operation, and output to the rotor multiplier 23-1. The rotator multiplier 23-1 is configured to perform rotator multiplication on the input data and output the data to a processing circuit at a subsequent stage.

The processing circuits in the second and subsequent stages are also constructed similarly to the processing circuits in the first stage. However, the delay time of the delay circuit is gradually shortened by 1/2.

Next, the operation will be described with reference to FIG. The distribution switch 21-1 separates the input data (FIG. 2A) into the first half data and the second half data in symbol units, and the first half data is input to the second input terminal of the changeover switch 26A-1. Supply (Fig. 2
(B)), the second half data changeover switch 26B-1
Is supplied to the first input terminal of (FIG. 2 (C)).

The data input to the second input terminal of the changeover switch 26A-1 is supplied to the delay circuit 22A-1 and written therein. For example, as shown in FIG.
The first half data f ₀ of the symbol f is written in the delay circuit 22A-1. Then, when the delay time of N / 2 elapses, the data f ₀ is read from the delay circuit 22A-1 and input to the first input terminal of the butterfly computing unit 24-1.

At the same timing, the latter half data f distributed by the distribution switch 21-1.
₁ is fetched from the first input terminal of the changeover switch 26B-1 and input to the second input terminal of the butterfly computing unit 24-1. The butterfly computing unit 24-1 uses _one of the necessary butterfly computations, for example, addition (f ₀ + f), with respect to the first half data f ₀ and the second half data f ₁ that are simultaneously input to the two input terminals. _{Perform 1} ) and output (Fig. 2 (F)).

On the other hand, when the butterfly computing unit 24-1 is sequentially computing the first half data f ₀ , the delay circuit 2
The first half data f ₀ read from 2A-1 is written again in the delay circuit 22A-1 via the first input terminal of the changeover switch 26A-1 (FIG. 2 (D)).
Similarly, the latter half data f ₁ output from the changeover switch 26B-1 is written in the delay circuit 22B-1 during the calculation by the butterfly calculator 24-1 (FIG. 2 (E)). ). As a result, the butterfly computing unit 2
When 4-1 completes the addition operation of the _first half data f ₀ and the latter half data f ₁ , the delay circuit 22A-1 outputs the first half data f ₀ again, and the delay circuit 22B-1 outputs the latter half data. f ₁ is read out and the changeover switch 26B-
It is output via 1. Therefore, the butterfly computing unit 24
The same data is input again to -1.

The butterfly computing unit 24-1 performs, on the re-input first-half data f ₀ and second-half data f ₁ , operations not previously performed by the butterfly computing unit, such as subtraction (f ₀ -f _1). ) And output.

When the delay circuit 22A-1 is reading the first half data f ₀ for the second time, the changeover switch 26A
-1 distribution switch 21- via the second input terminal
The data g ₀ of the first half of the next symbol g is supplied from 1
Written. As a result, it is possible to perform butterfly computation on the data of each input symbol without interruption.

The result of the butterfly operation performed by the butterfly operation unit 24-1 is input to the rotor multiplier 23-1, where the rotor multiplication is performed and the result is output to the subsequent processing circuit.

Hereinafter, the same processing as in the case of the first stage is performed in each processing circuit of the second and subsequent stages.

As described above, in this embodiment, the butterfly computing unit 24-1 performs butterfly computation in a time division manner. Butterfly calculator 24-1 is 1
You only have to perform one operation (addition or subtraction) each time,
The circuit scale can be reduced compared to the case where two operations (both addition and subtraction) are performed at once. The number of delay circuits in this embodiment is 2 (N-1).

The embodiment shown in FIG. 3 represents a configuration example of an embodiment for performing a radix-4 operation corresponding to the embodiment for performing a radix-2 operation in FIG. In this embodiment, the distribution switch 21A-1 divides the input data into four,
Through the fourth output terminal. The data output from the first output terminal needs to be delayed by a total of 3N / 4 and supplied to the first input terminal of the butterfly computing unit 24-1. Further, the data output from the second output terminal needs to be delayed by N / 2 and input to the second input terminal. Furthermore, the data output from the third output terminal needs to be delayed by N / 4 and input to the third input terminal. Further, the data output from the fourth output terminal needs to be input to the fourth input terminal without delay.

Therefore, the data output from the first output terminal of the distribution switch 21A-1 of the first-stage processing circuit is transmitted through the first output terminal or the second output terminal of the distribution switch 21B-1. Changeover switch 26A-
2nd input terminal of 1 or changeover switch 26B-
It is adapted to be input to the second input terminal of No. 1.

The changeover switch 26A-1 selects either the output of the delay circuit 22A-1 for delaying the data by N / 4 or the output of the first output terminal of the distribution switch 21B-1, and the delay circuit 22A-1. -1 is supplied. The changeover switch 26B-1 selects either the output of the delay circuit 22B-1 for delaying the data by N / 4 or the output from the second output terminal of the distribution switch 21B-1, and the delay circuit 22B-1 is selected. It is designed to output to. Changeover switch 26F-1
Selects one of the outputs of the delay circuit 22A-1 or 22B-1 and supplies it to the first input terminal of the butterfly computing unit 24-1.

The changeover switch 26C-1 is a delay circuit 2 for delaying the data output from the second output terminal of the distribution switch 21A-1 or the data by N / 4.
One of the outputs of 2C-1 is selected and output to the delay circuit 22C-1. The delay circuit 22E-1 is
The output of the delay circuit 22C-1 is delayed by N / 4 and is input to the second input terminal of the butterfly computing unit 24-1.

The changeover switch 26D-1 is a delay circuit 2 for delaying the data output from the third output terminal of the distribution switch 21A-1 or the data by N / 4.
One of the data output from 2D-1 is selected and output to the delay circuit 22D-1. The output of the delay circuit 22D-1 is the third output of the butterfly computing unit 24-1.
It is designed to be input to the input terminal of.

The changeover switch 26E-1 is a delay circuit 2 for delaying the data output from the fourth output terminal of the distribution switch 21A-1 or the data by N / 4.
One of the data output from 2F-1 is selected and output to the delay circuit 22F-1, and the butterfly computing unit 24
-1 is inputted to the fourth input terminal.

One output of the butterfly computing unit 24-1 is input to the rotator multiplier 23-1, subjected to rotator multiplication, and then output to the subsequent processing circuit. .

The processing circuits at the second and subsequent stages are similarly configured. However, the delay time of the delay circuit of the processing circuit of each stage is shortened by 1/4.

Next, the operation will be described with reference to FIG. The distribution switch 21A-1 at the first stage divides the input data (FIG. 4A) into four data in symbol units. For example, the symbol f is divided into the first quarter data f ₀ , the next quarter data f ₁ , the third quarter data f ₂ , and the last quarter data f _3. It Then, these data are output from the first output terminal to the fourth output terminal, respectively (FIGS. 4B to 4E).

The data output from the first output terminal of the distribution switch 21A-1 is the data of the distribution switch 21B.
-1 and is supplied to the changeover switch 26A-1 or the changeover switch 26B-1. The distribution switch 21B-1 alternately performs this distribution in symbol units. For example, when the data of the symbol f is supplied to the changeover switch 26A-1, the data of the next symbol g is output to the changeover switch 26B-1.
Then, the data of the next symbol h is supplied to the changeover switch 26A-1 again.

For example, the data f ₀ of the first symbol f is
It is supplied to the changeover switch 26A-1. The changeover switch 26A-1 transfers the data f ₀ to the delay circuit 22A.
It is supplied to -1 and written (FIG. 4 (F)). And
The data f ₀ written in the delay circuit 22A-1 is
After being delayed by N / 4, it is read out and input again to the delay circuit 22A-1 via the changeover switch 26A-1. Such an operation is repeated, and the data f
_{When 0} is delayed by a total of 3N / 4, ₀ is input to the first input terminal of the butterfly computing unit 24-1 via the changeover switch 26F-1.

On the other hand, the second switch of the distribution switch 21A-1
Second quarter data f output from the output terminal of
₁ is the delay circuit 2 via the changeover switch 26C-1
2C-1 is input and written (FIG. 4 (H)). The delay circuit 22C-1 delays the input data f ₁ by N / 4 and then outputs it. This output data f
₁ is again input to the delay circuit 22C-1 via the changeover switch 26C-1 and written. Such an operation is repeated.

On the other hand, the delay circuit 22E-1 is the delay circuit 2E
The data delayed by N / 4 by 2C-1 is further delayed by N / 4, and the second data of the butterfly computing unit 24-1 is
Input to the input terminal of (FIG. 4 (J)). Accordingly, at the timing when data f ₀ to a first input terminal of the butterfly operation device 24-1 is input to the second input terminal, data f ₁ is inputted.

On the other hand, the third switch of the distribution switch 21A-1
Third quarter data f output from the output terminal of
₂ is input to and written in the delay circuit 22D-1 via the second input terminal of the changeover switch 26D-1 (FIG. 4 (I)). Then, this data f ₂ is delayed by N / 4 by the delay circuit 22D-1, and then input again to the delay circuit 22D-1 via the first input terminal of the changeover switch 26D-1 and delayed. . Such an operation is repeated.

As a result, the data f ₀ is input to the first input terminal and the second input terminal of the butterfly computing unit 24-1.
And at the timing when f ₁ is input, the third input terminal, data f ₂ is inputted from the delay circuit 22D-1.

Further, the fourth switch of the allocating switch 21A-1
Fourth quarter data f output from the output terminal of
₃ is written in the delay circuit 22F-1 via the first input terminal of the changeover switch 26E-1 (FIG. 4 (K)) and is also input to the fourth input terminal of the butterfly computing unit 24-1. .

As described above, the butterfly computing unit 24
Data f _{0 to} f _{3 obtained} by dividing the symbol f into four are sequentially input simultaneously to the −1 first to fourth input terminals at the same timing. Therefore, the butterfly computing unit 24-1 performs one predetermined butterfly computation among the four butterfly computations to be performed on the four data f _{0 to} f ₃ , and outputs the computation result F ₀ (FIG. 4 (L )).

The butterfly calculator 24-1 calculates the calculation result F _0.
When the output of is completed, at the next timing, the data f ₀ is input again to the first input terminal of the butterfly computing unit 24-1 from the delay circuit 22A-1 via the changeover switch 26F-1 ( FIG. 4 (F)). Similarly, the data f ₁ from the delay circuit 22E-1 is input to the second input terminal.
Is input (FIG. 4 (J)), and the data f ₂ is input from the delay circuit 22D-1 to the third input terminal (FIG. 4 (J)).
(I)), and the data f ₃ is input to the fourth input terminal from the delay circuit 22F-1 via the changeover switch 26E-1 (FIG. 4 (K)).

Therefore, the butterfly computing unit 24-1 is set to 4
Of the two butterfly operations, the second butterfly operation is performed and the operation result F ₁ is output (FIG. 4 (L)).

Similarly, the second calculation result F ₁
When the above is completed, the data f _{0 to} f ₃ are input again to the first to fourth input terminals of the butterfly computing unit 24-1, and the butterfly computing unit 24-1 performs the computation of the third butterfly computing. The result F ₂ is output. When the output of the operation result F ₂ is completed, the data f _{0 to} f ₃ are input again, so the fourth butterfly operation is performed and the operation result F ₃ is output.

On the other hand, when the butterfly computing unit 24-1 completes the output of the first computation result F ₀ of the symbol f, the next symbol is output from the first output terminal to the fourth output terminal of the distribution switch 21A-1. Data g _{0 to} g _{3 obtained} by dividing g into four are sequentially output with a shift of N / 4.

The first data g ₀ cannot be supplied to and written in the delay circuit 22A-1. That is, the delay circuit 22A-1 still needs to hold the data f ₀ and supply it to the butterfly computing unit 24-1. Therefore, the distribution switch 21B-1 supplies this data g ₀ to the delay circuit 22B-1 via the changeover switch 26B-1 and writes it therein (FIG. 4 (G)). Delay circuit 22B-1
Outputs the input data g ₀ after delaying it by N / 4. The delayed data g ₀ is input to the delay circuit 22B-1 again via the changeover switch 26B-1 and delayed. Such an operation is repeatedly executed.

Then, the fourth switch of the distribution switch 21A-1
The last quarter data g ₃ of the symbol g from the output terminal of
Is output and is input to the fourth input terminal of the butterfly computing unit 24-1.
The data g ₀ read from B-1 is transferred to the first of the butterfly computing unit 24-1 via the changeover switch 26F-1.
Input to the input terminal of. Similarly, the data g ₁ and g ₂ output from the second output terminal and the third output terminal of the distribution switch 21A-1 are
It is read from the delay circuit 22E-1 and the delay circuit 22D-1, and is input to the second input terminal and the third input terminal of the butterfly computing unit 24-1.
Input to the input terminal of. Then the butterfly calculator 24
-1 performs the first butterfly operation of the butterfly operations on the input data g _{0 to} g ₃ and outputs the operation result G ₀ (FIG. 4 (L)).

Thereafter, the butterfly operation is similarly performed in a time division manner, and the operation result is output.

The data output from the butterfly computing unit 24-1 is input to the rotator multiplier 23-1, subjected to rotator multiplication, and then output to the subsequent processing circuit.

The same processing as in the case of the first stage is executed in each processing circuit of the second and subsequent stages.

The number of delay circuits in this embodiment is 2
(N-1).

FIG. 5 shows another embodiment for performing a radix-2 fast Fourier transform. In this example, FIG.
In this embodiment, the distribution switch 21-1 is omitted, and instead, the inputs are delay circuits 22A-1 and 22A.
The signal is sequentially delayed by N / 2 by B-1, and then input to the first input terminal of the changeover switch 26A-1. The output of the delay circuit 22A-1 is supplied to the second input terminal of the changeover switch 26A-1.

The first switch of the changeover switch 26B-1
The output of the delay circuit 22A-1 is supplied to the input terminal of, and the data input to the input terminal of the delay circuit 22A-1 is input to the second input terminal thereof. Changeover switch 26A-1 and changeover switch 26B-1
The data selected by the butterfly calculator 24-1
Are supplied to the first input terminal and the second input terminal, respectively. The output of the butterfly computing unit 24-1 is output to the processing circuit in the subsequent stage after the computing for the rotor is performed by the computing unit 23-1 for the rotor.

The processing circuits of the second and subsequent stages are also constructed similarly to the processing circuits of the first stage. However, the delay time of the delay circuit is gradually shortened by 1/2.

Next, the operation will be described with reference to FIG. For example, now the data of the symbol f (see FIG.
(A)) is input, the changeover switch 26
The first half data f ₀ delayed by N / 2 is input to the second input terminal of A-1 by the delay circuit 22A-1 (FIG. 6 (B)). On the other hand, the changeover switch 2
The second half data f ₁ is input to the second input terminal of 6B-1 (FIG. 6A). Therefore, as shown in FIG.
By switching the changeover switches 26A-1 and 26B-1 to the lower side in the drawing, the butterfly computing unit 2
The first half data f ₀ is supplied to the first input terminal 4-1 (FIG. 6 (D)), and the second half data f ₁ is simultaneously input to the second input terminal (FIG. 6 (E)). Butterfly calculator 24
-1 performs the first operation (for example, addition) of the butterfly operations and outputs the added value (f ₀ + f ₁ ) (FIG. 6).
(F)).

Next, the changeover switches 26A-1 and 26A
B-1 is switched to the upper side in the figure. As a result, the changeover switch 26A-1 causes the delay circuit 22A-1 to
And 22B-1 fetch the first half data f ₀ delayed by a total of N (FIG. 6 (C)). Further, the changeover switch 26B-1 causes the delay circuit 22A-1 to fetch the latter half data f ₁ delayed by N / 2 (FIG. 6 (B)). Butterfly operation device 24-1, a second data f ₀ of the first half of that supplied from the changeover switch 26A-1, with respect to the second half of the data f ₁ of the second supplied from the changeover switch 26B-1, the butterfly operation Among them, the calculation (for example, subtraction) not performed previously is performed, and the subtraction value (f ₀ −f ₁ ) is output (FIG. 6).
(F)).

Similar processing is performed in the processing circuits of the second and subsequent stages.

In the embodiment of FIG. 5, for example, as shown in FIG. 8, the number of the changeover switch 26 is one, and the output of the delay circuit 22B-1 is changed to the changeover switch 2
6, the output of the delay circuit 22A-1 is directly supplied to the first input terminal of the butterfly computing unit 24-1, and is supplied to the input terminal of the delay circuit 22A-1. The data may be input to the second input terminal of the changeover switch 26 (the same applies to the processing circuits of other stages).

In this case, the first half data f ₀ of the first time is
At the timing of input from the delay circuit 22A-1 to the first input terminal of the butterfly computing unit 24-1,
The data f _{1 in} the latter half of the second time is input to the second input terminal of the butterfly computing unit 24-1 via the second input terminal of the switch 26. The butterfly computing unit 24-1 performs a predetermined computation (for example, addition (f ₀ + f ₁ )) of the butterfly computations on these data.

Next, at the timing when the second half data f ₁ of the second time is input from the delay circuit 22A-1 to the first input terminal of the butterfly operation unit 24-1, the second operation of the butterfly operation unit 24-1 is performed. The input terminal of the delay circuit 22B
Second half data f delayed by -1
₀ is fetched via the switch 26. The butterfly computing unit 24-1 performs an operation (for example, subtraction (f ₀ −f ₁ )) that has not been performed previously in the butterfly operation on these data input at the same time, and outputs the data.

FIG. 9 shows a configuration example of a radix-4 embodiment corresponding to the radix-2 embodiment shown in FIG. In the first-stage processing circuit of this embodiment, the input data is sequentially delayed by N / 4 by the delay circuits 22A-1 to 22F-1, and is delayed by a total of 3N / 2, and the first data of the changeover switch 26A-1. Is input to the input terminal of. The output of the delay circuit 22E-1 is the output of the changeover switch 2
6A-1 second input terminal and changeover switch 26B-
1 is input to the first input terminal. Delay circuit 22D
The output of -1 is supplied to the third input terminal of the changeover switch 26A-1, the second input terminal of the changeover switch 26B-1, and the first input terminal of the changeover switch 26C-1.
Each is supplied.

The output of the delay circuit 22C-1 is the fourth input terminal of the changeover switch 26A-1, the third input terminal of the changeover switch 26B-1, and the changeover switch 26C.
-1 is input to the second input terminal and the changeover switch 26D-1 is input to the first input terminal.

The output of the delay circuit 22B-1 is the fourth input terminal of the changeover switch 26B-1, the third input terminal of the changeover switch 26C-1, and the changeover switch 26D.
-1 is input to each of the second input terminals.

The output of the delay circuit 22A-1 is input to the fourth input terminal of the changeover switch 26C-1 and the third input terminal of the changeover switch 26D-1.
The data input to the input terminal of the delay circuit 22A-1 is input to the fourth input terminal of the changeover switch 26D-1.

Changeover switches 26A-1 to 26D-
1 is the first of the butterfly computing units 24-1.
Through the fourth input terminal. The output of the butterfly computing unit 24-1 is supplied to the rotor multiplier 23-1. The output of the rotor multiplier 23-1 is
It is input to the subsequent processing circuit.

The processing circuits in the second and subsequent stages are similarly constructed. However, the delay time of the delay circuit is gradually shortened by 1/4.

In this embodiment, the delay circuits 22F-1, 22E-1, 22D-1, and the delay circuits 22F-1, 22E-1, 22D-1 are respectively connected to the first to fourth input terminals of the changeover switch 26A-1.
The 22C-1 inputs data whose timings are shifted by N / 4. Changeover switch 26B
Similarly, in -1, 26C-1 and 26D-1, N / 4 is respectively applied to the first to fourth input terminals,
Data whose timings are sequentially shifted is input.

Then, the changeover switches 26A-1 and 26A-2
The data input to 6B-1, 26C-1, and 26D-1 are further shifted in timing by N / 4. Therefore, for example, the selector switches 26A-1 to 26D-1 all select the data input from the fourth input terminal, so that the data obtained by dividing the same symbol into four can be simultaneously operated by the butterfly computing unit 24-. First of one
Through the fourth input terminal. Butterfly calculator 2
At this time, 4-1 performs the first operation of the butterfly operations.

Next, when the data supplied to the third input terminal of each of the change-over switches 26A-1 to 26D-1 is selected, the same data as the previously selected data is restored in the butterfly computing unit 24-1. It is supplied to the first to fourth input terminals. At this time, the butterfly computing unit 24-1
The second operation of the butterfly operation is performed.

Thereafter, similarly, the changeover switch 26
A-1 to 26D-1 are caused to select the data supplied to the second input terminal and then to select the data input to the first input terminal. In each case, the butterfly computing unit 24-1 performs a different computation among the butterfly computations.

The number of delay circuits in this case is also 2 (N
-1).

With the configuration shown in each of the above embodiments, the fast Fourier transform operation can be performed. Such a Fourier transform operation device can be applied to the device shown in FIG. 10, for example. .

That is, in FIG. 10, OFDM (orth
organic frequency division
It represents a multiplex (orthogonal frequency multiplex) transmission / reception system, and basically includes a transmission device 211 and a reception device 231 that receives data transmitted from the transmission device 211 via a transmission path 220.

In the transmitter 211, the input symbol string is the pipeline type inverse FFT as described above.
Arithmetic unit 202 incorporating a (inverse fast Fourier transform) circuit
Is supplied to. When the radix is 2, the inverse FFT is basically realized with the same configuration as the FFT, only by changing the multiplication coefficient in the rotor multiplier to a predetermined value different from that in the FFT. When the radix is greater than 2, the configuration can be easily configured by changing the multiplication coefficient and providing an exchange switch at the input or output of the butterfly computing unit.

Further, the arithmetic unit 202 has a built-in rearrangement circuit 202A for rearranging the outputs of the above-mentioned pipeline type inverse FFT circuit. This rearrangement circuit 20
2A, for example, when data of G0 to G15 are sequentially input, as shown in FIG. 10, G0, G8, G4, G1
2, G2, G10, G6, G14, G1, G9, G5
It outputs in order of G13, G3, G11, G7, G15.

The output order is determined by bit reverse. That is, when the numbers 0 to 15 representing the order of the data G0 to G15 are displayed in binary numbers, 00
It becomes 0,0001,0010, ..., 1111.
When this binary number is displayed (bit-reversed) from the LSB side, not from the MSB side, it is 2
Decimal numbers are in output order.

The arithmetic unit 202 performs inverse FFT processing on the input symbol string. The number of points in this inverse FFT is
It is the same as the number of carriers of the input QPSK-modulated transmission data. Inverse FFT can be viewed as a transform from the frequency domain to the time domain.

The output of the arithmetic unit 202 is input to the D / A conversion circuit 203 and D / A converted. The output of the D / A conversion circuit 203 is input to the low pass filter 204,
A baseband time series signal is extracted. This signal is
It is input to the multiplier 205, multiplied by the carrier wave output from the carrier wave generation circuit 206, and converted into an RF signal of a desired frequency. Then, from this RF signal, the band pass filter 207 extracts only a signal in a predetermined pass band,
It is transmitted to the transmission line 220.

In the receiving device 231, the transmission line 220
The band-pass filter 241 extracts only a signal in a predetermined band from the supplied signal and supplies the signal to the multiplier 242. The multiplier 242 applies an oscillator 24 to the input signal.
A signal of a predetermined frequency output by the signal 3 is multiplied to obtain a baseband signal component. The A / D conversion circuit 244 A / D-converts the output of the multiplier 242 and outputs the output to the arithmetic unit 245 including the pipeline type FFT circuit described above and a rearrangement circuit 245A that rearranges the output.

The arithmetic circuit 245 outputs the input data to the FF.
T process. FFT processing can be viewed as a transformation from the time domain to the frequency domain.

The rearrangement circuits 202A and 245A
Can be provided in the input stage of the pipeline type FFT circuit instead of the output stage. However, in this case, the delay time of the processing circuit in each stage is set to be shortest in the first stage and longer in the subsequent stages.

As described above, it is possible to realize an OFDM transmission / reception system which is strong against multipath interference in which the symbol interval (symbol value) is lengthened to make it less susceptible to the delay time due to reflected waves.

In the above embodiment, the delay circuit and the changeover switch are provided in the preceding stage of the butterfly computing unit,
Although substantially the same data is input to the butterfly computing unit a plurality of times, such a configuration can be realized by a configuration other than that shown in the above embodiment. However, the configuration shown in the above-described embodiment can reduce the number of delay circuits, and correspondingly reduce cost and size.

[0150]

As described above, according to the Fourier transform computing device of the first aspect and the Fourier transform computing method of the fourth aspect, the input data is replaced with the first data which precedes in time. Since it is divided into the second data that follows in time, the first data and the second data are output a plurality of times at the same timing, and the butterfly operation is performed in a time division manner. The configuration can be simplified, and the size and cost can be reduced.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration example of an embodiment of a Fourier transform calculation device of the present invention.

FIG. 2 is a diagram for explaining the operation of the embodiment of FIG.

FIG. 3 is a block diagram showing the configuration of another embodiment of the Fourier transform calculation device of the present invention.

FIG. 4 is a diagram for explaining the operation of the embodiment of FIG.

FIG. 5 is a block diagram showing the configuration of another embodiment of the Fourier transform calculation device of the present invention.

FIG. 6 is a diagram for explaining the operation of the embodiment of FIG.

FIG. 7 is a diagram for explaining the switching operation of the changeover switch in the embodiment of FIG.

FIG. 8 is a diagram showing another configuration example of the changeover switch of the embodiment of FIG.

FIG. 9 is a block diagram showing the configuration of another embodiment of the Fourier transform calculation device of the present invention.

FIG. 10: O to which the Fourier transform calculation device of the present invention is applied
It is a block diagram which shows the structural example of an FDM transmission / reception system.

FIG. 11 is a block diagram showing a configuration of an example of a Fourier transform calculation device.

FIG. 12 is a diagram illustrating an algorithm of a radix-2 fast Fourier transform;

13 is a diagram for explaining an insertion position of the rotor multiplier of the example of FIG.

FIG. 14 is a block diagram showing another example of the insertion position of the rotor multiplier.

FIG. 15 is a block diagram showing still another example of the insertion position of the rotor multiplier.

FIG. 16 is a block diagram showing another configuration example of the Fourier transform calculation device.

FIG. 17 is a diagram illustrating an algorithm of a fast Fourier transform when the radix is 4.

[Explanation of symbols]

 21-1 to 21-k distribution switch 22A-1 to 22B-k delay circuit 23-1 to 23-k rotor multiplier 24-1 to 24-k butterfly computing unit 26A-1 to 26B-k changeover switch 202 Arithmetic device 203 D / A conversion circuit 206 Carrier wave generation circuit 244 A / D conversion circuit 245 Arithmetic device

Claims (4)

[Claims] 1. Dividing means for dividing inputted data into first data inputted earlier in time and second data inputted later in time, and divided by said dividing means. The first data and the second data
Adjusting means for outputting the data of 1. in a plurality of times at the same timing, and a first calculating means for performing a butterfly operation in a time division manner on the first data and the second data whose timings have been adjusted by the timing adjusting means. And the data input to the first computing means or the first
And a second arithmetic means for performing a rotor arithmetic operation on predetermined data output from the arithmetic means. 2. The timing adjusting means selects a first delay means for delaying the first data and data input to the first delay means, and delays the selected data by the first delay means. The first data,
First selecting means for supplying again to the first delay means for delaying, second delay means for delaying the second data, and data for input to the second delay means, The Fourier transform computing device according to claim 1, further comprising: a second selection unit that supplies the second data to the second delay unit to delay the second data. 3. The dividing means converts the input data into
A plurality of delaying means for sequentially delaying by a predetermined time are provided, and the timing adjusting means includes the first data delayed by the delaying means for the first time and the second data not delayed.
Data of which the first data delayed by the first time is further delayed by the first time and data of the second data delayed by the first time are selected. The Fourier transform computing device according to claim 1, further comprising a selecting unit. 4. The input data is divided into first data input earlier in time and second data input later in time, and the first data is divided. The second data is output a plurality of times at the same timing, and the timing-adjusted first data and second data are subjected to butterfly computation in a time division manner, and the data after the butterfly computation or the butterfly is performed. A Fourier transform calculation method, characterized in that a calculation for a rotor is performed on a predetermined data before calculation.