JP5414434B2 - Fast Fourier transform arithmetic unit - Google Patents

Description

  The present invention relates to a fast Fourier transform computing device that performs butterfly computation by fixed-point computation and continuously executes FFT (fast Fourier transform) computation or IFFT (inverse fast Fourier transform) computation.

  In general, the fixed point has an advantage that the arithmetic circuit is simpler than the floating point and the circuit scale can be reduced, but the dynamic range of the number that can be handled is narrow. Such an arithmetic device often deals with a problem in which the tendency of input data is similar (rarely changes rapidly).

In order to improve the problem that the dynamic range is narrow as described above, a calculation method and a calculation apparatus that perform bit shift only by a specific butterfly calculation have been conventionally proposed (for example, see Patent Document 1).
However, in the above-mentioned patent document 1, the overflow in the butterfly calculation is not monitored, and the position where the bit shift is performed is fixed.

JP 10-49516 A

  As described in Patent Document 1, the conventional fast Fourier transform arithmetic apparatus has a problem that even if overflow occurs in the butterfly calculation, this cannot be avoided.

  The present invention has been made to solve the above-described problems. When overflow occurs, the bit shift amount is updated, thereby generating overflow in the subsequent data calculation process. An object of the present invention is to obtain a fast Fourier transform arithmetic unit capable of suppressing the above.

Fast Fourier transform arithmetic unit according to the present invention, the input data, a fast Fourier transform operation unit having a plurality of butterfly operation unit for performing fast Fourier transform by a fixed point arithmetic fixed bit length, said input data an input line for capturing the plurality of butterfly operation sections of the at least one bit shift unit that performs bit shift with respect to operation data, and is connected to the bit shifter most provided downstream of said bit shift unit an output line for outputting an operation result, and a shift amount control unit for controlling the bit shift amount in the bit shift unit, an input buffer for storing the input data is inserted downstream of the input line, said output line inserted upstream side and an output buffer for storing said operation result, at least one of the plurality of butterfly operation unit Has a function of detecting its own overflow, the shift amount control unit, when overflow in any of the plurality of butterfly operation unit is detected, thereby adjusting the bit shift amount, the The input data stored in the input buffer is introduced into the most upstream butterfly computation unit among the plurality of butterfly computation units, and the computation process is re-executed .

  According to the present invention, by controlling the bit shift amount (bit shift position) according to the presence or absence of a digit overflow, even if a digit overflow occurs, the bit shift control is corrected in the subsequent data processing, The occurrence of overflow can be suppressed.

It is a block block diagram which shows the fast Fourier transform arithmetic unit which concerns on Embodiment 1 of this invention. It is a block block diagram which shows the fast Fourier transform arithmetic unit which concerns on Embodiment 3 of this invention. It is a block block diagram which shows the fast Fourier transform arithmetic unit which concerns on Embodiment 4 of this invention. It is a block block diagram which shows the fast Fourier transform arithmetic unit which concerns on Embodiment 6 of this invention. It is explanatory drawing which shows the arithmetic processing by Embodiment 6 of this invention.

Embodiment 1 FIG.
Embodiment 1 of the present invention will be described below with reference to the drawings.
FIG. 1 is a block configuration diagram showing a fast Fourier transform calculation apparatus according to Embodiment 1 of the present invention, showing a configuration capable of executing FFT (or IFFT) calculation of 2 ¹⁴ (= 16384) points at maximum. Yes.

  In FIG. 1, a fast Fourier transform calculation device includes an input line 1 that takes in input data to be subjected to fast Fourier transform, a fast Fourier transform unit 2 that performs fast Fourier transform operation on the input data, and a fast Fourier transform unit 2. The shift amount control unit 3 for controlling the bit shift amount of the first and second output lines 4 for outputting the result (output data) of the fast Fourier transform.

The fast Fourier transform unit 2 includes 14 (a, b,..., M, n) butterfly computation units 5a to 5n that perform butterfly computation, and bit shift units 6a to 6n that perform bit shift. .
The butterfly operation units 5a to 5n and the bit shift units 6a to 6n are alternately and sequentially arranged, and are connected to the shift amount control unit 3, respectively.

  That is, bit shift units 6a to 6n are individually connected to data output terminals of butterfly operation units 5a to 5n, and butterfly operation units 5a to 5n are sequentially connected in series via bit shift units 6a to 6m. The output line 4 is connected to the bit shift unit 6n at the final stage.

The butterfly calculation units 5a to 5n individually input the calculation data to the lower bit shift units 6a to 6n and to the shift amount control unit 3, respectively.
The bit shift units 6a to 6n perform bit shift on the input data under the control of the shift amount control unit 3, and the bit shift units 6a to 6m sequentially bit-shift the lower stage butterfly calculation units 5b to 5n. The last bit shift unit 6n outputs the output data via the output line 4.

The function and operation of each part of the fast Fourier transform arithmetic unit according to Embodiment 1 of the present invention shown in FIG. 1 will be described below.
(1) First, data from the input line 1 is input to the uppermost butterfly computation unit 5 a in the fast Fourier transform unit 2.
(2) The fast Fourier transform unit 2 sequentially performs FFT (or IFFT) operation on the input data in accordance with an instruction from the shift amount control unit 3.
(3) The fast Fourier transform unit 2 outputs the final FFT (or IFFT) calculation result from the bit shift unit 6n via the output line 2.

(4) At this time, the shift amount control unit 3 takes in the “overflow situation (or maximum value)” from each of the butterfly calculation units 5 a to 5 n in the fast Fourier transform unit 2, and Instruction contents for the bit shift units 6a to 6n are updated.
(5) Hereinafter, the fast Fourier transform unit 2 and the shift amount control unit 3 execute the processes (1) to (4) for the next input data (subsequent data).

Next, the operation inside the fast Fourier transform unit 2 will be described in more detail.
(6) First, the butterfly computation unit 5a on the uppermost stage always performs the butterfly computation on the input data and outputs the computation data to the lower stage.
(7) The butterfly calculation unit 5 a reports information on the presence or absence of “digit overflow” during the butterfly calculation to the shift amount control unit 3.
(8) Hereinafter, the butterfly computing units 5b to 5n on the lower stage sequentially execute the above processing operations in the same manner as the butterfly computing unit 5a.

(9) On the other hand, the bit shift unit 6a connected to the butterfly operation unit 5a always performs a bit shift on the input data and outputs the data after the bit shift. At this time, the bit shift amount by the bit shift unit 6 a is determined according to an instruction from the shift amount control unit 3.
(10) Hereinafter, the lower bit shift units 6b to 6n execute the processing operation (9) in the same manner as the bit shift unit 6a. At this time, the shift amount control unit 3 instructs the bit shift amounts individually for the bit shifts 5a to 5n.

With the above processing operations (1) to (10), the fast Fourier transform arithmetic unit can continue to perform the fast Fourier transform.
The butterfly computing units 5a to 5n have an internal memory (not shown), and simultaneously perform data exchange processing when performing the butterfly computation.
In addition, the Fast Fourier Transform arithmetic unit shown in FIG. 1 passes the information on the presence / absence of overflow and the bit shift amount to the post-stage process when necessary in the post-process (not shown) of the output line 4. It shall be comprised so that it can do.

Here, the operation example of the shift amount control unit 3 will be supplementarily described.
The shift amount control unit 3 determines an initial value of the shift amount for the bit shift units 6a to 6n based on a simulation result or a prior observation result. Thereby, each bit shift part 6a-6n performs the bit shift of the shift amount designated to each.

At this time, the initial value of the shift amount for each of the bit shift units 6a to 6n is set to the following value, for example.
The shift amounts for the odd-numbered bit shift units 6a, 6c, 6e, 6g, 6i, 6k, and 6m are set to “1”.
The shift amounts for the even-numbered bit shift units 6b, 6d, 6f, 6h, 6j, 6l, and 6n are set to “0”.

  The shift amount control unit 3 shifts the bit shift unit connected to the upper stage of the butterfly calculation unit that has reported “digit overflow” when any of the butterfly calculation units 5b to 5n reports “digit overflow”. Change the amount.

Specifically, the shift amount changing process at this time is executed as follows, for example.
The value of the bit shift unit on the upper side of the butterfly operation unit that detects “overflow” and closest to the butterfly operation unit that detects “overflow” is increased by “1”.
When “overflow” is reported from the butterfly calculation unit 5a, it is considered as a temporary one and no particular countermeasure (shift amount changing process) is performed.

  As described above, the fast Fourier transform operation apparatus according to Embodiment 1 (FIG. 1) of the present invention performs a plurality of butterfly operation units 5a that perform fast Fourier transform on input data by fixed-point length fixed-point operations. A fast Fourier transform operation device having ˜5n, an input line 1 for taking in input data, and bit shift units 6a-6n for performing bit shift on at least one operation data of the plurality of butterfly operation units 5a-5n, The output line 4 that is connected to the last bit shift unit 6n of the bit shift units 6a to 6n and outputs the operation result, and the shift amount control unit 3 that controls the bit shift amount in the bit shift units 6a to 6n, It has.

At least one of the plurality of butterfly calculation units 5a to 5n has a function of detecting its own overflow, and the shift amount control unit 3 has "digit overflow" in any of the plurality of butterfly calculation units 5a to 5n. When it is detected, the bit shift amount of at least one of the bit shift units 6a to 6n is adjusted (changed).
By this shift amount changing process, it is possible to suppress the occurrence of “overflow” when performing FFT (or IFFT) operation on subsequent data having the same tendency.

  In the above description, the case where “overflow” is reported from the butterfly operation unit 5a is not dealt with, but a control line (not shown) from the shift amount control unit 3 to the preceding stage processing unit of the input line 1 When a “overflow” is reported from the butterfly operation unit 5a, a request for lowering the level value of the input data is output from the shift amount control unit 3 to the preceding process of the butterfly operation unit 5a. Also good. Thereby, “overflow” in the butterfly calculation unit 5a can also be suppressed.

Further, in order to suppress “digit overflow” in the butterfly operation unit 5a, a bit shift unit (not shown) is added on the upper side of the butterfly operation unit 5a, and a shift amount control unit is added to the added bit shift unit. The shift amount “1” may be specified from 3.
As a result, when performing the FFT (or IFFT) operation on the subsequent data having the same tendency, even if the occurrence of “digit overflow” in the butterfly calculation unit 5a does not become transient, “digit overflow” "Can be suppressed.

Embodiment 2. FIG.
In the first embodiment (FIG. 1), the butterfly operation units 5a to 5n and the bit shift units 6a to 6n constitute 14 pairs, and the shift amounts of the bit shift units 6a to 6n are arbitrarily set. However, the even-numbered bit shift units 6b, 6d, 6f, 6h, 6j, 6l, and 6n may be reduced so that one bit shift process is performed for two butterfly computation processes. Good.

Further, instead of reducing the bit shift units as described above, the maximum shift amount that can be designated by each of the bit shift units 6a to 6n may be set to “1” without changing the configuration of FIG.
Hereinafter, the operation of the shift amount control unit 3 when the shift amount is set to “1” at the maximum will be supplementarily described.

In this case, the shift amount control unit 3 shifts the bit shift unit that satisfies all of the following conditions (a) to (c) when “overflow” is reported from any of the butterfly calculation units 5b to 5n. Change the amount to "1".
(A) It is located on the upper side of the butterfly calculation unit that detects “overflow”.
(B) The shift amount is “0”.
(C) Among the bit shift units satisfying both (a) and (b), it is located on the lowermost side.

In the shift amount changing process, the shift amount is updated by only one of the 14 bit shift units 6a to 6n, but is more than the bit shift unit having the updated shift amount. The shift amounts of all the bit shift units on the lower side may be changed.
For example, when the bit shift unit that satisfies the above-described conditions (a) to (c) is only the bit shift unit 6d, the shift amount (“0”) of the bit shift unit 6d and the lower-stage bit shift units 6e to 6n. Or “1”) will be inverted.

In the case of this shift amount changing process, the effect of suppressing “overflow” is weaker than when only one shift amount of the bit shift units 6a to 6n is changed to “1”. 3 can perform a more gradual adjustment for “overflow”.
As a result, it is possible to realize a fast Fourier transform operation device with a smaller circuit scale while suppressing the occurrence of “overflow”.

  In the above description, the shift amount control unit 3 has been described as an example where it is possible to detect where “overflow” has occurred in the butterfly calculation units 5a to 5n. As long as it is possible to detect the presence or absence, it is possible to take the same action as described above even if it is impossible to detect where the butterfly computing units 5a to 5n occur.

For example, if the occurrence location of “overflow” is indistinguishable, the above-mentioned measures can be taken by setting the occurrence location of “overflow” in one of the following criteria (A) or (B) become.
(A) It is considered that it occurred in the butterfly calculation unit 5n at the final stage.
(B) Among the bit shift units having a shift amount of “0”, it is considered that the signal is generated in the butterfly operation unit immediately after the bit shift unit located on the uppermost side.
Which of the above criteria (A) and (B) is adopted can be arbitrarily selected according to the purpose of use of the fast Fourier transform arithmetic unit.

  As described above, according to the second embodiment of the present invention, since the configuration is simplified as compared with the first embodiment described above, a fast Fourier transform arithmetic apparatus can be realized with a smaller circuit scale.

Embodiment 3 FIG.
In the first embodiment (FIG. 1), the bit shift unit 6n at the final stage is connected to the output line 4, but the maximum value is detected between the bit shift unit 6n and the output line 4 as shown in FIG. Part 7 may be inserted.

FIG. 2 is a block diagram showing a fast Fourier transform arithmetic unit according to Embodiment 3 of the present invention. Components similar to those described above (see FIG. 1) are denoted by the same reference numerals as those described above, or Is followed by “A” and detailed description is omitted.
In this case, the only difference from FIG. 1 is that a maximum value detector 7 is added in the fast Fourier transform unit 2A.

The operation according to the third embodiment of the present invention shown in FIG. 2 will be described below.
In FIG. 2, the maximum value detection unit 7 detects the maximum value of the absolute value for each block of the FFT (or IFFT) calculation result based on the output data from the bit shift unit 6n, and shifts the maximum value to the shift amount. Report to the control unit 3A and output to the outside via the output line 4.

When the maximum value received from the maximum value detection unit 7 is smaller than a predetermined value, the shift amount control unit 3A reduces the shift amount instructed to the bit shift units 6a to 6n.
For example, when the bit width of each data is “16 bits” but the received maximum value is less than 2 ¹³ (= 8192), even if the output data value is quadrupled, the 16-bit representation Since it is clear that it falls within the range, among the bit shift units 6a to 6n, the shift amount is “1” or more, and the shift amount of the bit shift unit located on the lowest side is reduced by “1”.

  As a result, “digit overflow” can be suppressed, and at the same time, the size of the output data value can be prevented from being fixed to a small level.

  In the configuration shown in FIG. 1 (not including the maximum value detection unit 7), by selecting the following operations (A1) and (A2) of the shift amount control unit 3, “digit” At the same time as suppressing “overflow”, it is possible to prevent the output data value from being fixed to a small level.

(A1) When the period during which “digit overflow” does not occur exceeds the set value, the shift amount is returned to the initial value.
(A2) The shift amount change history is retained, and each time the period during which “digit overflow” does not occur exceeds the set value, the change history is reversed to sequentially reverse the changes.

  As described above, according to the fast Fourier transform arithmetic unit according to Embodiment 3 (FIG. 2) of the present invention, the maximum value detector 7 inserted on the upper stage side of the output line 4 is provided, and the shift amount controller 3A. Since the bit shift amount is adjusted according to the detection result of the maximum value detection unit 7, even in the configuration (without the maximum value detection unit 7) of FIG. It is possible to prevent the output data value from being fixed at a small level.

Embodiment 4 FIG.
In the third embodiment (FIG. 2), only the maximum value detection unit 7 is inserted on the upper side of the output line 4, but the input buffer 8 is inserted on the lower side of the input line 1 as shown in FIG. In addition, an output buffer 9 may be further inserted on the upper side of the output line 4.

FIG. 3 is a block diagram showing a fast Fourier transform arithmetic unit according to Embodiment 4 of the present invention. The same components as those described above (see FIGS. 1 and 2) are denoted by the same reference numerals as those described above. Alternatively, “B” is appended after the reference numerals and the detailed description is omitted.
In this case, the only difference from FIG. 2 is that an input buffer 8 and an output buffer 9 are added in the fast Fourier transform unit 2B.

The input buffer 8 retransmits the accumulated input data under the control of the shift amount control unit 3B when “digit overflow” described later occurs.
The output buffer 9 discards the accumulated output data under the control of the shift amount control unit 3B when “digit overflow” occurs.

Hereinafter, the operation according to the fourth embodiment of the present invention will be described with reference to FIG. 3 while focusing on the difference from the above.
First, data input from the input line 1 is once stored in the input buffer 8 and taken into the fast Fourier transform unit 2B via the input buffer 8.

  Thereafter, the fast Fourier transform unit 2B performs a fast Fourier transform operation on the input data, stores the calculation result in the output buffer 9 via the maximum value detection unit 7, and then outputs the calculation result (output data) from the output line 4. ) Is output.

  At this time, if no “overflow” has occurred in any of the butterfly operation units 5a to 5n, the data only passes through the input buffer 8 and the output buffer 9, and compared with the above, from the output line 4 There is no change in the output data value obtained.

On the other hand, when a “digit overflow” occurs in any of the butterfly computing units 5a to 5n, the following operations (B1) to (B5) can be used.
(B1) The butterfly operation unit in which “overflow” has occurred reports “overflow” to the shift amount control unit 3B.
(B2) All butterfly computation units 5a to 5n once terminate the computation process.
(B3) Even if the output buffer 9 has already received halfway data, it discards it.
(B4) The shift amount control unit 3B updates the shift amounts of the bit shift units 6a to 6n.
(B5) The shift amount control unit 3B instructs the input buffer 8 to retransmit data.

  As described above, the fast Fourier transform arithmetic operation apparatus according to Embodiment 4 (FIG. 3) of the present invention includes the input buffer 8 inserted in the lower stage side of the input line 1 and stores the input data, and the upper stage of the output line 4. And an output buffer 9 for storing calculation results.

The shift amount control unit 3B adjusts the bit shift amount of the bit shift unit when the “digit overflow” occurs in any of the plurality of butterfly calculation units 5a to 5n, and the input data stored in the input buffer 8 Is introduced into the uppermost butterfly computation unit 5a among the plurality of butterfly computation units 5a to 5n, and the computation process is re-executed.
As a result, the operation result of FFT (or IFFT) in which “digit overflow” does not occur can be sent to the lower stage side of the output line 4.

Embodiment 5 FIG.
In the fourth embodiment (FIG. 3), each FFT (or IFFT) operation is handled independently. However, a plurality of times (for example, 8000) are handled as one lump, May perform arithmetic processing with the same shift amount.

However, in the configuration of FIG. 3, if the number of one block is large, redoing may occur many times, and processing time may increase significantly.
Therefore, in order to avoid an increase in processing time, it is desirable to perform the following operation under the control of the shift amount control unit 3B.

In FIG. 3, first, the shift amount control unit 3 </ b> B takes several FFTs (or IFFTs) as samples from the chunk and introduces them into the fast Fourier transform unit 2 </ b> B via the input buffer 8.
Hereinafter, if “digit overflow” occurs in the arithmetic processing by the fast Fourier transform unit 2B, the shift amount is adjusted as described above, and the above is applied to all samples. During this time, the output buffer 9 discards all received data.

  Subsequently, the input buffer 8 introduces all of the data in one block to the fast Fourier transform unit 2B, and the fast Fourier transform unit 2B performs fast Fourier transform. At this time, even if “digit overflow” occurs, the shift amount is not updated and the arithmetic processing is not performed again.

When “digit overflow” occurs, the output buffer 9 does not discard the result processed as a sample, and the input buffer 8 limits the data to be introduced into the fast Fourier transform unit 2B to other than the sample. Duplicate processing on the sample may be avoided.
With the above operation, although it is impossible to completely suppress “overflow”, it is possible to obtain a fast Fourier transform arithmetic unit that performs processing without causing a significant increase in processing time.

As described above, according to the fifth embodiment of the present invention, the shift amount control unit 3B sets a plurality of fast Fourier transform arithmetic processing as one block and sets the bit shift amount between one block in common. Then, arithmetic processing is performed as one lump.
The shift amount control unit 3B acquires a sample from one block and determines a bit shift amount for the sample.

Thereby, the processing conditions in one lump can be made the same.
Further, in the processing subsequent to the output line 4, it is possible to perform processing for comparing and referring to the calculation results of different FFT (or IFFT) in the same block.

Embodiment 6 FIG.
In the first to fifth embodiments (FIGS. 1 to 3), the bit shift amount is controlled for a single fast Fourier transform unit. However, as shown in FIG. 4, a plurality of fast Fourier transform units 2a to 2 is used. The bit shift amount may be controlled with respect to 2d.

  FIG. 4 is a block diagram showing a fast Fourier transform arithmetic unit according to Embodiment 6 of the present invention. Components similar to those described above (see FIG. 1) are denoted by the same reference numerals as those described above, or Is followed by "C" and detailed description is omitted.

  In FIG. 4, the fast Fourier transform arithmetic unit includes a plurality of (for example, four) fast Fourier transform units 2a to 2d arranged in series, and memories 11a and 11b that store output data of the fast Fourier transform units 2a and 2c. An intermediate processing unit 12 that is inserted between the fast Fourier transform unit 2b and the fast Fourier transform unit 2c and performs arbitrary processing is provided.

The input line 1 is connected to the uppermost fast Fourier transform unit 2a, and the output line 4 for outputting the operation result is connected to the final fast Fourier transform unit 2d.
The shift amount control unit 3C controls the bit shift amounts of the fast Fourier transform units 2a to 2d.
The fast Fourier transform units 2a to 2d have the same configuration as that shown in any of the first to fifth embodiments.

  Here, as an example of executing the fast Fourier transform operation processing a plurality of times, first, the fast Fourier transform units 2a and 2b perform the two-dimensional FFT operation, the intermediate processing unit 12 performs the intermediate processing, and then the fast Fourier transform processing is performed. The structure in the case of performing two-dimensional IFFT calculation in the conversion parts 2c and 2d is shown.

FIG. 5 is an explanatory diagram showing the arithmetic processing according to the sixth embodiment of the present invention.
In FIG. 5, the two-dimensional FFT is realized by performing both the one-dimensional FFT operation on the horizontal axis and the one-dimensional FFT operation on the vertical axis on the two-dimensional data 100.

Hereinafter, operations (C1) to (C11) according to the sixth embodiment of the present invention will be described with reference to FIGS.
(C1) First, two-dimensional data is input to the fast Fourier transform unit 2a via the input line 1.
(C2) The fast Fourier transform unit 2a performs a one-dimensional FFT operation on the horizontal axis in FIG. 5 in accordance with an instruction from the shift amount control unit 3C.
(C3) The fast Fourier transform unit 2a stores the FFT calculation result in the memory 11a.

(C4) The next-stage fast Fourier transform unit 2b extracts data from the memory 11a in the order in which the one-dimensional FFT operation on the vertical axis in FIG. 5 can be executed.
(C5) The fast Fourier transform unit 2b performs a one-dimensional FFT operation on the vertical axis in FIG. 5 in accordance with an instruction from the shift amount control unit 3C.
(C6) The fast Fourier transform unit 2b sends the FFT calculation result to the intermediate processing unit 12.

(C7) The intermediate processing unit 12 performs data processing on the calculation result of the fast Fourier transform unit 2b and inputs the result to the fast Fourier transform unit 2c.
(C8) The fast Fourier transform unit 2c performs a one-dimensional IFFT operation on the vertical axis in FIG. 5 in accordance with an instruction from the shift amount control unit 3C.
(C9) The fast Fourier transform unit 2c stores the FFT calculation result in the memory 11b.

(C10) The fast Fourier transform unit 2d at the final stage extracts data from the memory 11b in the order in which the one-dimensional IFFT on the horizontal axis in FIG. 5 can be executed.
(C11) The fast Fourier transform unit 2d performs a one-dimensional IFFT operation on the horizontal axis in FIG. 5 in accordance with an instruction from the shift amount control unit 3C.

Here, the shift amount control unit 3C sets an individual shift amount for each of the fast Fourier transform units 2a to 2d based on a simulation result or a prior observation result.
Further, the shift amount control unit 3C shifts the plurality of fast Fourier transform units described in the first embodiment, for example, when “overflow” occurs in the uppermost butterfly computation unit in the fast Fourier transform 2b. Quantity control is also performed.

  That is, the shift amount control unit 3C adjusts the shift amount of the bit shift unit at the final stage in the fast Fourier transform 2a when “overflow” occurs in the uppermost butterfly computation unit in the fast Fourier transform 2b. Will do.

  As described above, according to the sixth embodiment (FIG. 4) of the present invention, the shift amount control unit 3C also applies to a plurality of the same fast Fourier transform computation processes among the plurality of fast Fourier transform computation processes. , Each bit shift amount is given, and each bit shift amount is adjusted.

  Thus, when performing a plurality of arithmetic processes using the plurality of fast Fourier transform units 2a to 2d, it is possible to obtain a fast Fourier transform arithmetic apparatus capable of performing an operation based on a shift amount suitable for each fast Fourier transform. it can.

  1 input line, 2, 2A, 2B, 2a to 2d fast Fourier transform unit, 3, 3A, 3B, 3C shift amount control unit, 4 output line, 5a to 5n butterfly operation unit, 6a to 6n bit shift unit, 7 maximum Value detection unit, 8 input buffer, 9 output buffer, 11a, 11b memory, 12 intermediate processing unit.

Claims (5)

A fast Fourier transform operation device having a plurality of butterfly operation units for performing fast Fourier transform on fixed-point operations with a fixed bit length for input data,
An input line for capturing the input data;
A bit shift unit that performs a bit shift on at least one calculation data of the plurality of butterfly calculation units;
An output line connected to a bit shift unit provided on the most downstream side of the bit shift unit and outputting an operation result;
A shift amount control unit for controlling a bit shift amount in the bit shift unit;
An input buffer that is inserted downstream of the input line and stores the input data;
An output buffer that is inserted upstream of the output line and accumulates the operation result ,
At least one of the plurality of butterfly calculation units has a function of detecting its own overflow,
The shift amount control unit adjusts the bit shift amount and detects the input data accumulated in the input buffer when the overflow is detected in any of the plurality of butterfly calculation units. A fast Fourier transform arithmetic apparatus , which is introduced into the most upstream butterfly arithmetic section of the arithmetic sections and re-executes arithmetic processing . A maximum value detector inserted upstream of the output buffer ;
2. The fast Fourier transform arithmetic apparatus according to claim 1, wherein the shift amount control unit adjusts the bit shift amount according to a detection result of the maximum value detection unit. 3. The high speed according to claim 1, wherein the shift amount control unit sets a bit shift amount between the single chunks in common by using a plurality of fast Fourier transform calculation processes as one chunk. 4. Fourier transform arithmetic unit. 4. The fast Fourier transform arithmetic apparatus according to claim 3 , wherein the shift amount control unit acquires a sample from the one block and determines the bit shift amount for the sample. The shift amount control unit, of the plurality of times the fast Fourier transform operation processing, even for a plurality of the same fast Fourier transform processing, given different bit shift amount in each to adjust each bit shift amount The fast Fourier transform arithmetic apparatus according to any one of claims 1 to 4 , wherein the fast Fourier transform arithmetic apparatus is characterized.

Images