JPH06105458B2 - Vector calculator - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Object of the Invention] (Field of Industrial Application) The present invention relates to a vector computer used in a fast Fourier transform (hereinafter referred to as FFT) device.

(Prior Art) When the FFT is executed by a vector computer, the conventional arithmetic method has a problem in that, in the butterfly operation, the vector length becomes shorter each time the stage advances, so that the processing performance deteriorates. This will be described with reference to FIG. 6. The vector computer uses the input data X ₀ (m) (m = 0) having the data length n = 8.
~ N), in the first stage, A butterfly operation with a vector length of 4 is performed. In addition,
Here, at ^{Wk = e} -2πk ^{/ _n,} is _{W k = -W k + n /} 2. In addition, the vector calculator is different from the result obtained in stage 1 in stage 2, The butterfly operation of vector length 2 represented by is performed, and in stage 3, X ₃ (0) = X ₂ (0) + W ₀ · X ₂ (1) X ₃ (1) = X ₂ (0) + W ₄ · X ₂ (1) X ₃ (2) = X ₂ (2) + W ₂ · X ₂ (3) X ₃ (3) = X ₂ (2) + W ₆ · X ₂ (3) X ₃ (4) = X ₂ ( 4) + W ₁ · X ₂ (5) X ₃ (5) = X ₂ (4) + W ₅ · X ₂ (5) X ₃ (6) = X ₂ (6) + W ₃ · X ₂ (7) X ₃ (7) = X ₂ (6) + W ₇ · X ₂ The butterfly operation of vector length 1 represented by (7) is performed.

As described above, in the conventional apparatus that executes the FFT by the vector computer, the vector length that influences the performance of the vector computer becomes shorter as the number of stages increases. Normally, a vector computer can process data with a long vector length at a high speed, but when the vector length is short, the proportion of the setup processing time becomes larger than the calculation processing time. However, there is a problem that high speed processing cannot be achieved. Therefore, the conventional vector computer has a problem that its performance cannot be sufficiently exhibited.

(Problems to be Solved by the Invention) As described above, in the conventional vector computer, the vector length becomes shorter each time the stages are overlapped during the FFT calculation, and the advantage of high-speed processing cannot be fully exerted. There was a problem.

In view of the above points, an object of the present invention is to provide a vector computer capable of executing FFT at high speed by fully utilizing the advantage of high-speed processing of the vector computer.

[Structure of the Invention] (Means for Solving Problems) In the present invention, vector data consisting of n (= 2 ^r ) elements is converted into a first data vector consisting of n / 2 elements and a second data vector , And a butterfly operation is performed using both of these data vectors and a coefficient vector consisting of n / 2 elements, and every other n elements of the obtained operation result vector are arranged. The re-processing is repeated by r stages, and as a coefficient vector used in the i-th stage by this means, a series of values from 0 to 2 ^i-1 -1 is repeated 2 ^r-i times. On the other hand, there is provided means for providing a coefficient vector in which a numerical sequence in which the bit order of each numerical value is reversed is used as an element number sequence.

(Operation) According to the present invention, the first and second data vectors composed of n / 2 elements and the coefficient vector composed of n / 2 elements are obtained by dividing the vector data composed of n elements. A process of performing a butterfly operation and rearranging every other n elements of the obtained operation result vector is performed for each stage. When such replacement is performed, when the vector after replacement is divided into two for every n / 2 consecutive elements, the coefficient data to be multiplied by both vectors after the division has a relation of just +-. Therefore, also in the next stage, the butterfly calculation using one coefficient vector for both vectors becomes possible. Therefore, the vector length does not change at all stages.

In the present invention, in order to enable such an operation, coefficient data in consideration of replacement of operation result data is given as coefficient data. That is, a series of values from 0 to 2 ^i-1 -1 is set as 2 as the coefficient vector of the i-th stage.
^For a numerical sequence that is repeated ^r-i times, a coefficient vector whose element number sequence is a numerical sequence in which the bit order of each numerical value is reversed is generated and given, so the vector length does not change at each stage. After all, it is possible to provide a vector arithmetic machine capable of high-speed processing, which maximizes the advantages of the vector arithmetic machine.

(Example) Hereinafter, the present invention will be described based on illustrated examples.

FIG. 3 is a diagram showing the overall flow of the FFT. n (=
Input data that is vector data of 2 ^r ) elements,
The coefficient vector consisting of n / 2 elements generated by the coefficient vector generation unit 10 is guided to the butterfly operation unit 11, where the butterfly operation of the vector consisting of n / 2 elements and the data replacement are performed. Be seen. When this process is performed for r stages, the obtained vector of n elements is bit-inverted in the data order restoration unit 12 and output as converted data.

Of the above processing, the processing in the butterfly computing unit 11
The case where n = 8 will be described.

The butterfly operation performed here is, as shown in FIG. 1, a first data vector a and
The butterfly operation is performed using the second data vector b and the coefficient vector K, and the data obtained by arranging every other element of the operation result vector becomes the input data of the next stage. Here, since it is n = 8 = 2 ^3, this process is performed on the stage of the three stages. Finally, bit inversion is performed to obtain the Fourier transform result. For details on bit inversion, see E.ORAN BRIGHAM, Hiroshi Miyagawa
Translated by Hideki Imai, "Fast Fourier Transform" (Science and Technology Publishing Company, 1
978).

FIG. 2 shows the state of vector calculation at the i-th stage in the butterfly calculation. The vectors to be used are a first data vector a (i) and a second data vector b (i) having a vector length of 4, which are divided into upper and lower parts in the figure of the i-th stage,
It is a coefficient vector K (i) generated by the coefficient vector generation unit 10 by a method described later. Then, by vector operation, p = a (i) + K (i) * b (i) q = a (i) -K (i) * b (i) is calculated.

Next, the data vectors a (i + 1) and b (i + 1) of the i + 1th stage are obtained by arranging every other element of the obtained n-element vector connecting p and q.

Next, the coefficient vector K will be described. Coefficient vector K
As shown in FIG. 1, vector in the first stage was repeated four times W _0, the vector in the second stage was repeated W _0, W ₂ 2 times, in the third stage W _0, W _2, W It is a vector consisting of ₁ and W ₃ . That is, the coefficient vector K of the i-th stage
(I) is a series of values from 0 to 2 ^i-1 -1
It is a vector in which a numerical sequence obtained by performing bit inversion (changing the order of bits) on a numerical sequence repeated ^r-i times is used as a subscript of W.

This coefficient vector can be obtained by a circuit as shown in FIG. 4, for example. The coefficient table 100 is a table in which each element W of the coefficient data K is stored in the bit reverse order. The counter (RA) 110 is incremented every time one element of the coefficient vector K is read from the coefficient table 100. The first register (RB) 120 has 2 ⁱ⁻¹ − in the ^i- th stage.
Set to 1. In this example, 00 is set in the first stage, 01 in the second stage, and 11 in the third stage. The second register (A) 130 stores the start address (0 in this example) of the coefficient table 100. And
Output of the counter (RA) 110 and the first register (RB) 1
The output of 20 is ANDed with AND gate 140, so that all 0s in the first stage and 1s in RA in the second stage.
The bit is enabled, and all bits of RA are enabled in the third stage. Then, the output of the AND gate 140 and the start address of the coefficient table stored in the register (A) 130 are added in the adder 150, and the addition result is given as the address of the coefficient table 110. If such a circuit is used, the coefficient of each stage described above can be obtained.

Now, returning to FIG. 1 and following the calculation results in each stage, first, in the first stage, A butterfly operation with a vector length of 4 is performed. After placing every other result, in the second stage, A butterfly operation with a vector length of 4 is performed. Furthermore, after arranging every other result, in the third stage, A butterfly operation with a vector length of 4 is performed. Here, the obtained results are arranged every other one, and W _k = −W
_{Considering that k + n / 2} , it can be seen that the same result as the conventional result described above was obtained. Further, according to this vector computer, all the butterfly operations from the first stage to the third stage are performed by the vector operation of the vector length 4, so that the performance of the vector computer can be sufficiently exhibited.

Note that in the above embodiment, the fourth
Although the circuit shown in the figure is used, as shown in FIG. 5, for example, each element W of the coefficient vector K is stored in the coefficient table 200 in the normal order, and the output of the adder 150 is stored in the bit inversion unit 2.
The coefficient table 200 may be accessed using the value obtained by bit inversion by 10 as an address.

Further, in the above embodiment, the case of n = 8 has been described, but it goes without saying that other numbers can be applied without departing from the scope of the present invention.

[Effects of the Invention] As described above, according to the present invention, every other butterfly operation result is rearranged and coefficient data corresponding to the butterfly calculation result is rearranged. Vector operations can be performed while keeping the vector length long. Therefore, according to the present invention, it is possible to perform higher-speed processing in the FFT.

[Brief description of drawings]

FIG. 1 is a diagram for explaining a flow of butterfly calculation processing in a vector computer according to an embodiment of the present invention, FIG. 2 is a diagram for explaining processing of an i-th stage in the butterfly processing, and FIG. FFT processing flow chart, FIG. 4 is a circuit diagram showing a detailed configuration of the coefficient vector generation unit in this embodiment, FIG. 5 is a circuit diagram showing another configuration example of the coefficient vector, and FIG. 6 is a conventional butterfly operation. It is a figure for explaining. 10 …… Coefficient vector generator, 11 …… Butterfly calculator,
12 …… Data order restoration unit, 100,200 …… Coefficient table, 1
10 ... Counter, 120 ... First register, 130 ... Second
Register, 140 …… and gate, 150 …… adder, 21
0 …… Bit inversion part.

Claims (2)

[Claims] 1. A vector data composed of n (= 2 ^r ) elements is divided into a first data vector and a second data vector composed of n / 2 elements, and A process of performing a butterfly operation using a coefficient vector composed of n / 2 elements and rearranging every n elements of the obtained operation result vector by r
The stage repeat means and the means for generating the coefficient vector used for each stage by this means are provided, and the means for generating the coefficient vector are 0 to 2 ⁱ⁻¹ as the coefficient vector of the i-th stage. A numerical value sequence in which a series of values up to -1 is repeated 2 ^r-i times is given to give a coefficient vector whose element number sequence is a numerical sequence in which the bit order of each numerical value is reversed. Vector calculator to do. 2. The means for generating the coefficient vector counts up every time one coefficient element is read from the coefficient table in which each element of the coefficient vector is stored in the bit-reverse order of the element number. A counter, a first register set to 2 ⁱ⁻¹ −1 in the ^i- th stage, a second register storing the start address of the coefficient table, an output of the counter and the first register
2. The arithmetic unit for adding the value of the second register to the logical product of the output of the register and the output of the coefficient data as the address of the coefficient data. Vector calculator.