JP2000040080A - Fast Fourier transform circuit - Google Patents

Abstract

(57) [Summary] [Problem] To set F at 1/2 or 1/4 of the normal number of samples
When performing the FT processing, the working memory is used in parallel for data input and arithmetic processing to improve processing efficiency. SOLUTION: While complex number input data II, IQ are input to segments 42a, 43a of working memories 42, 43 via a multiplexer 41, a segment 42
The data in b and 43b are connected to data paths 70A and 70B via multiplexers 44 and 41 and subjected to FFT operation processing, and the operation results are output as output data OI and OQ via registers 91 and 92. Segment 4
When the arithmetic processing of the data in 2b and 43b is completed, the multiplexers 41 and 44 are switched, and the segment 42 is switched.
The arithmetic processing of the input data II and IQ input to the input terminals a and 43a is performed. On the other hand, the input data II and IQ of the next cycle are input to the segments 42b and 43b.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a fast Fourier transform (hereinafter referred to as "FFT") circuit for converting into a frequency component by utilizing the periodicity of a discrete time series signal given periodically, and more particularly, to a sample of an input signal. FFT circuit with variable score,
Alternatively, the present invention relates to an inverse conversion circuit that converts a discrete frequency component into a time-series signal.

[0002]

2. Description of the Related Art FIG. 2 is a block diagram showing an example of a conventional FFT circuit. This FFT circuit has registers 11 and 12 for temporarily holding complex number input data II and IQ given in time series, respectively. Register 1
The outputs of 1, 1 and 12 are connected to the first inputs of selectors 13 and 14, respectively. Output sides of the selectors 13 and 14 are connected to a data input terminal of the working memory 15. The working memory 15 stores input data II, IQ
And for temporarily storing intermediate results during the operation. The data output terminal of the working memory 15 is FFT
It is connected to the input side of data paths 16 and 17 for performing arithmetic processing. The data paths 16 and 17 have a coefficient memory 1 in which coefficients used in the FFT operation processing are stored in advance.
8 are connected.

The data paths 16 and 17 are connected to the working memory 1
5 and the data given from the coefficient memory 18
This is calculated according to the T algorithm. Output sides of the data paths 16 and 17 are connected to selectors 13 and 14, respectively.
Of the register 19,
20 are connected to the input side. Registers 19 and 20
Are held to output the complex number output data OI and OQ finally obtained by the repetitive operation by the data paths 16 and 17.

Further, the FFT circuit includes a clock generation unit 21 for generating a clock signal serving as a reference for operation, a sequence control unit 22 for controlling an operation sequence of each unit based on the clock signal, and an address generation unit 23. Have. The address generation unit 23 generates a read / write address for the working memory 15 and a read address for the coefficient memory 18 in accordance with the operation sequence. In such an FFT circuit, for example, FFT
When processing is performed with the number of sample points in one cycle of the processing set to 1024, first, the first input sides of the selectors 13 and 14 are selected. Then, the complex number input data II and IQ discretely inputted via the registers 11 and 12 are sequentially stored in the working memory 15 by the number of sample points (that is, 1024 points). After 1024 points of complex number input data II and IQ are stored in the working memory 15, the selectors 13 and 14
Is switched to the second input side.

Next, data stored at a predetermined address based on the FFT algorithm is read out from the working memory 15 and the coefficient memory 18, and the data path 16,
17 inputs. As a result, data path 1
Intermediate results corresponding to the read data are output to output sides 6 and 17. Intermediate results output from the data paths 16 and 17 are written again to the same address in the working memory 15 via the selectors 13 and 14. The addresses of the working memory 15 and the coefficient memory 18 are sequentially shifted, and the data in the working memory 15 and the coefficient memory 18 are operated by the data paths 16 and 17 to perform the FFT processing. Intermediate results of the FFT processing by the data paths 16 and 17 are sequentially updated and written to the working memory 15. Then, when the final calculation result is obtained, the output data of the data paths 16 and 17 is
The complex output data O stored in the registers 19 and 20
Output as I, OQ.

[0006]

However, the conventional FFT circuit has the following problems. For example, F
When the number of sample points in one cycle of the FT process is set to 512, which is の of 1024, only half of the working memory 15 is used, and the other half is unused. Not planned. For this reason, the storage areas for the complex input data II and IQ and the storage area for the intermediate result alternately use the same area.
When performing FT processing continuously over a plurality of cycles, data input and arithmetic processing cannot be performed in parallel,
There is a problem that it is difficult to improve the processing efficiency. The present invention solves the problem of the prior art, and can improve processing efficiency by performing parallel processing of data input and arithmetic processing when the number of sample points is reduced to half or the like. It provides a simple FFT circuit.

[0007]

According to a first aspect of the present invention, there is provided an input means for inputting discrete input data sampled at a constant period, and comprising: Working storage means having a storage capacity for processing the input data for N (where N is a power of 2) samples sequentially input, and a frequency component of the input data input from the input means And a storage means for the coefficient in which a torsion coefficient for calculating the torsion coefficient is stored in advance, and an intermediate result is calculated based on the torsion coefficient and the input data stored in the work storage means, and re-stored in the work storage means. In the FFT circuit including the frequency analysis means for calculating the frequency component of the input data by repeating the arithmetic processing to be performed in accordance with a predetermined procedure, the working storage means
Each segment is composed of two segments each having a storage area for processing the input data for N / 2 samples.

An input process for storing the input data from the input means,
An input control unit and an output control unit for sequentially and concurrently using a calculation process of calculating and outputting a frequency component by the frequency analysis unit based on the input data stored in the segment by the input process. Provided. According to the first aspect, since the FFT circuit is configured as described above, the following operation is performed. When input data for N / 2 samples is input to one segment of the working storage means from the input means, the input data input to this segment is output to the frequency analysis means together with the torsion coefficient stored in the coefficient storage means. To calculate the frequency component. While this segment calculation process is being performed, N / 2 for other segments is performed in parallel.
Input processing of input data for a sample is performed.

[0009] The second invention is the same as the FFT of the first invention.
In the circuit, the working storage means comprises four segments each having a storage area for processing the input data for N / 4 samples. Further, an input process for storing the input data from the input unit for each of the four segments, and a calculation for calculating a frequency component by the frequency analysis unit based on the input data stored in the segment by the input process processing,
Further, an input control unit and an output control unit for sequentially and in parallel use are provided for an output process for outputting a calculation result by the calculation process. According to the second aspect, the following operation is performed. Input data for N / 4 samples is sequentially input from the input means to the four segments of the working storage means. The input data of the segment for which the input processing has been completed is provided to the frequency analysis means together with the torsion coefficient stored in the coefficient storage means, and the frequency component is calculated. Further, the calculation results stored in the segments for which the calculation processing has been completed are sequentially read out and output. These input processing, calculation processing, and output processing in the four segments are sequentially performed in parallel under the control of the input control unit and the output control unit.

[0010] A third invention is the FF of the first and second inventions.
In the T circuit, block floating point processing means is provided for each arithmetic processing in the frequency analyzing means, which gives a common index of data used in the arithmetic processing to the frequency analyzing means. According to the third aspect, the following operation is performed. Each input data input from the input means is supplied to the frequency analysis means in the arithmetic processing by the block floating point processing means, with the index of the data used in the arithmetic processing being shared.

[0011]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS First Embodiment FIG. 1 is a block diagram of an FFT circuit showing a first embodiment of the present invention. The FFT circuit includes input means (for example, a register) for temporarily holding time-series complex number input data II and IQ each composed of a real part and an imaginary part.
31 and 32, and a working storage unit (for example, a data storage unit) 40 for storing an intermediate result of the operation and the like. The data storage unit 40 includes an input-side input control unit (for example, a multiplexer) 41, two working memories 42,
And an output control unit (for example, a multiplexer) 44 on the output side. The output sides of the registers 31 and 32 are connected to the input side of the multiplexer 41.
The working memory 4 is connected to the output side of the multiplexer 41.
2, 43 data input terminals are connected. The multiplexer 41 converts the input data provided from the registers 31 and 32 and the intermediate result of the operation into a predetermined working memory 42,
It has a function of switching and connecting in order to write to 43. The working memories 42 and 43 have storage areas corresponding to the number N of sample points in one cycle (for example, N = 1024 = 2 ¹⁰ ).
It is for temporarily storing IQ and the real part and imaginary part of complex number data in the middle of calculation. Working memory 4
The data output terminals 2 and 43 are connected to the input side of the multiplexer 44.

The multiplexer 44 is provided with the working memory 4.
It has a function of switching and connecting the data read from the devices 2 and 43 for FFT operation processing or final result output. The FFT circuit includes a coefficient storage unit (for example, a memory for coefficients) 50 and a block floating point processing unit (for example, a block floating point processing unit) 60.
have. The coefficient memory 50 includes a torsion coefficient W1i, based on a sine function and a cosine function used in the FFT operation processing.
W2i, W3i, W4i (where i = 1 to 256)
This is a read-only memory stored in advance. The block floating-point processing unit 60 detects an exponent common to each input data. That is, each time data is input, the values are compared with each other, and when a value larger than the value already stored in the working memories 42 and 43 is input, it is rewritten to a newer value. Has become. When a numerical value smaller than the value stored in the working memories 42 and 43 is input, the maximum value is finally obtained by leaving the value as it is. Then, the shift data S at the time of the calculation processing is set as the index of the maximum value as the index common to the group.
It is used as ET.

A multiplexer 44, a coefficient memory 50,
The output side of the floating point processing unit 60 is connected to the input side of frequency analysis means (for example, a data path) 70A, 70B. The data paths 70A and 70B are provided with the torsional coefficient W given from the data storage unit 40 and the coefficient memory 50.
A frequency component of input data is calculated by repeatedly performing an arithmetic operation according to the FFT algorithm using 1i to W4i and the shift data SFT provided from the floating point processing unit 60. Data path 70A, 7
0B is connected to the multiplexer 4 of the data storage unit 40.
1 is connected to the input side. The output side of the multiplexer 44 further outputs the complex number output data O finally obtained by the repetition operation by the data paths 70A and 70B.
Registers 91 and 92 held for outputting I and OQ
Is connected. The FFT circuit includes a clock generation unit 93 that generates a clock signal CLK as a reference for operation, a sequence control unit 94 that controls an operation sequence of each unit based on the clock signal CLK, An address generation unit 95 that generates a read / write address for the storage unit 40 and the block floating point processing unit 60 and a read address for the coefficient memory 50 is provided.

FIG. 3 is a configuration diagram of the data storage unit 40 in FIG. The multiplexer 41 of the data storage unit 40
Is composed of four selectors 41a, 41b, 41c, 41d. The working memories 42 and 43 include segments 42a and 42b corresponding to the number of sample points N / 2 (= 512) divided into two, and a segment 43, respectively.
a, 43b. The multiplexer 44 is composed of two selectors 44a and 44b. The first input side of the selector 41a and the selector 4
1b, the data I from the register 31
Ik (where k = 1 to 512) is provided. Similarly, data IQk from the register 32 is supplied to a first input side of the selector 41c and a second input side of the selector 41d.

The third input side of the selector 41a, the second input side of the selector 41b, the third input side of the selector 41c, and the third input side of the selector 41d are provided with data from the data path 70A. ai, ci (where i = 1 to
128). Data bi and di from the data path 70B are given to the second input side of the selector 41a, the first input side of the selector 41b, the second input side of the selector 41c, and the first input side of the selector 41d. It is supposed to be. Then, the selectors 41a, 41
The output side of b is the segment 42a of the working memory 42,
42b are respectively connected to the data input terminals. The data output terminals of the segments 42a and 42b of the working memory 42 are respectively connected to the first and second input sides of a selector 44a, and the output side of the selector 44a outputs the real parts of the complex data Ai to Di. It has become. On the other hand, the output sides of the selectors 41c and 41d are connected to the data input terminals of the segments 43a and 43b of the working memory 43, respectively. Data output terminals of the segments 43a and 43b of the working memory 43 are respectively connected to first and second input sides of a selector 44b, and complex number data Ai to Di are output from the output side of the selector 44b.
The imaginary part of is output.

FIG. 4 shows data paths 70A and 70A in FIG.
FIG. The data path 70A has a register 71 that temporarily holds the data Ai to Di output from the data storage unit 40 for the operation. A shifter 72 is connected to the output side of the register 71. Shifter 72
Is for shifting the data Ai to Di held in the register 71 by the designated number of digits based on the shift data SFT given from the block floating point processing unit 60. The output side of the shifter 72 is connected to the adder 73A and the first input side of the selector 74. Adder 73A
Is connected to the second input side of the selector 74,
The output side of the selector 74 is connected to the input side of the register 75. The output side of the register 75 is connected to the input side of the adder / subtractor 76, and the output side of the adder / subtractor 76 is connected to the input sides of the registers 77 and 78.

The data path 70A is used to calculate the torsional coefficients W1i and W3i given from the coefficient memory 50,
Each has registers 79 and 80 for temporarily holding them. The outputs of the registers 77 and 79 are connected to the input of a multiplier 81, and the output of the multiplier 81 is connected to a register. The registers 78 and 8
The output side of 0 is connected to the input side of the multiplier 83, and the output side of the multiplier 83 is connected to the register 84. The outputs of the registers 82 and 84 are connected to an adder / subtractor 85, and the output of the adder / subtractor 85 is connected to a register 86. Then, the operation result once stored in the register 86 is output as data ai, ci. The configuration of data path 70B is substantially the same as data path 70A. However, a subtractor 73B is provided instead of the adder 73A in the data path 70A. The other configuration is the same as that of the data path 70A, and the operation result once stored in the register 86 is output as data bi and di.

Such data paths 70A, 70B are:
By switching the selector 74, a function capable of performing FFT operation processing on the radix 4 and the radix 2 is provided. That is, when performing radix-4 FFT operation processing, the data storage unit 40 is stored in the register 71 of the data paths 70A and 70B.
And the complex number data Ai to Di read from.
The selector 74 of the data path 70A adds the adder 73.
The output side of A is selected by the selector 74 of the data path 70B from the output side of the subtractor 73B. Further, the registers 79 and 80 of the data path 70A include the coefficient memory 50.
The torsional coefficients W1i and W3i read from are stored, respectively. On the other hand, registers 79 and 80 of data path 70B
Includes the torsion coefficient W2 read from the coefficient memory 50.
i and W4i are stored.

Thus, the output signals ai, ci and the output signals bi, di calculated according to the following equations (1) to (4) are output to the output sides of the data paths 70A, 70B, respectively. It has become. ai = {(Ai + Ci) + (Bi + Di)} × W1i (1) ci = {(Ai + Ci) − (Bi + Di)} × W3i (2) bi = ｛(Ai−Ci) −j (Bi) −Di)｝ × W2i (3) di = {(Ai−Ci) + j (Bi−Di)} × W4i (4) On the other hand, when performing a radix-2 FFT operation, data The data storage unit 4 is stored in the register 71 of the paths 70A and 70B.
0, and stores the complex number data Ai to Di read from the adder 7 by the selector 74 of the data path 70A.
The input side of 3A is selected by the selector 74 of the data path 70B from the input side of the subtractor 73B. And data path 7
In the 0A registers 79 and 80, the torsional coefficients W1i and W3i read from the coefficient memory 50 alternately store the torsional coefficients W0 (= 1 + j0) corresponding to the phase 0 °.
On the other hand, the torsional coefficients W2 and W4 read from the coefficient memory 50 are stored in the registers 79 and 80 of the data path 70B.
Similarly stores the torsional coefficient W0 alternately.

As a result, the output side of the data path 70A is provided with the above equations (1) and (2) or the following equations (5) and (5).
The output signals ai and bi calculated according to (6) are output alternately. ai = Ai + Bi (5) bi = Ai-Bi (6) Also, on the output side of the data path 70B, the equation (3),
(4) Alternatively, output signals ci and di calculated according to the following equations (7) and (8) are output alternately. ci = Ci + Di (7) di = Ci-Di (8)

FIG. 5 is a diagram showing an operation sequence of the FFT circuit of FIG. Next, the operation of the FFT circuit of FIG. 1 at the number of sample points 512 will be described with reference to FIGS. First, in the period T1 in FIG. 5, the multiplexers 41a to 41d of the data storage unit 40 in FIG. 3 are switched to the first input side. Thereby, the segment 42
In a, the real part II of the complex input data of the first cycle from the outside is written via the register 31. Further, the imaginary part IQ of the complex input data of the first cycle from the outside is written into the segment 43a via the register 32.

Next, in the cycle T2, the multiplexers 41a to 41d are switched to the second and third input sides,
Further, the multiplexers 44a and 44b are switched to the second input side. Thereby, the segments 42b and 43
b includes externally input complex number input data II,
The IQ is written via the registers 31 and 32. On the other hand, the input data of the first cycle stored in the segments 42a and 43a is output via the multiplexers 44a and 44b. The operation results of the data paths 70A and 70B are input to the segments 42a and 43a via the multiplexers 41a and 41c.
The contents of 2a and 43a are sequentially replaced with data during the operation. When all the operations are completed and the data in the middle of the operation is replaced with the final result, the final result is output in synchronization with the clock signal CLK3.

Further, in the period T3, the multiplexers 41a to 41d are again switched to the first input side,
The multiplexers 44a and 44b are also switched to the first input. As a result, the third-period complex number input data II and IQ are externally added to the segments 42a and 43a.
Is written through the registers 31 and 32. On the other hand, the input data of the second cycle stored in the segments 42b and 43b is output via the multiplexers 44a and 44b. Then, the operation results of the data paths 70A and 70B are transmitted to the segment 4 via the multiplexers 41b and 41d.
2b, 43b and these segments 42b,
The contents of 43b are sequentially replaced with data during the operation.

As illustrated in detail in a cycle T3 in FIG. 5, in each cycle, the complex number input data (II1, IQ
1), (II2, IQ2),..., (II512, IQ5)
12) are sequentially input in synchronization with the clock signal CLK1 for data input. The input data II1, II2,..., II512 of the real number part are stored in the segment 42a of the data storage unit 40 as data A1 to D1, A2.
.., D128,..., A128 to D128. Also, the input data IQ1, I of the imaginary part
, IQ512 store data A1 to D1, A2 to D2,..., A1 in the segment 43a of the data storage unit 40.
28 to D128 are sequentially stored as imaginary part data.
On the other hand, the data once stored in the segments 42b and 43b of the data storage unit 40 is used for the operation clock signal CLK.
2 and are subjected to FFT operation processing in the data paths 70A and 70B, and the intermediate result is again stored in the same storage area of the segments 42b and 43b as intermediate data. Further, an FFT operation process according to a predetermined procedure is repeatedly performed on the re-stored intermediate result,
The final result is stored in the same storage area of the segments 42b and 43b. The final result is the output data OI of the real component in synchronization with the output clock signal CLK3.
, OI512, and imaginary component output data OQ1, OQ2,..., OQ512 are output via registers 91, 92, respectively.

As described above, the FF of the first embodiment
The T circuit has two segments 42a, 42b, respectively.
When data from outside is input to one of the working memories 42 and 43 divided into segments 43a and 43b, the data stored in the other segment is read to perform the FFT operation. It has multiplexers 41 and 44 for switching.
Thereby, when performing the FFT processing by reducing the number of sample points to １ ／, the parallel use of the data input and the arithmetic processing can be performed by the effective use of the working memories 42 and 43, and the processing performance is improved. Will be possible.

Second Embodiment FIG. 6 shows a data storage unit 4 according to a second embodiment of the present invention.
It is a block diagram of 0A. This data storage unit 40A
It is provided in place of the data storage unit 40 inside,
Input side input control unit (for example, multiplexer) 45
a, 45b, working memories 46, 47, and an output-side output control unit (for example, a multiplexer) 48a, 48b. The multiplexer 45a has three input sides and four output sides, and connects the input side and the output side according to a control signal (not shown). To the input side of the multiplexer 45a, input data IIk (where k = 1 to 256) of the real part from the register 31 and data ai to di (where i = 1 to 64) from the data paths 70A and 70B are provided. It has become. The working memory 46 includes four segments 46a, 46b, 46c, and 46d each having a storage area corresponding to the input data IIk having 256 sample points. The input side of each of the segments 46a to 46d is connected to the four output sides of the multiplexer 45a. The output side of each of the segments 46a to 46d is connected to the input side of a 4-input 2-output multiplexer 48a. The multiplexer 48a connects the input side and the output side according to a control signal (not shown).

Similarly, the multiplexer 45b has three input sides and four output sides, and connects the input side and the output side according to a control signal (not shown).
At the input side of the multiplexer 45b, input data IQk (where k = 1 to 256) of the imaginary part from the register 32 and data ai to di from the data paths 70A and 70B are provided.
(Where i = 1 to 64). The working memory 47 has 256 sample points each.
Is composed of four segments 47a, 47b, 47c and 47d having storage areas corresponding to the input data IQk. Then, each of these segments 47a to 47d
Are connected to the four outputs of the multiplexer 45b, respectively. The output side of each of the segments 47a to 47d is connected to the input side of a 4-input 2-output multiplexer 48b. Multiplexer 48b
Connects the input side and the output side according to a control signal (not shown).

FIG. 7 is a diagram showing an operation sequence of the data storage section 40A of FIG. Next, referring to FIG.
The number of sample points 256 in the data storage unit 40A of FIG.
Will be described. First, in a cycle T1 of FIG.
The first inputs of the multiplexers 45a and 45b in FIG. 6 are respectively connected to the first outputs. This allows
The segments 46a and 47a store the input data II and IQ of the first cycle, respectively. Next, in the period T2, the first input side of each of the multiplexers 45a and 45b is connected to the second output side, and the second input side is connected to the first output side. Further, multiplexers 48a and 48b
Has a first input connected to a first output. As a result, the input data II and IQ of the second cycle are stored in the segments 46b and 47b, respectively. On the other hand, the input data I of the first cycle stored in the segments 46a and 47a
I and IQ are provided to data paths 70A and 70B, respectively, and are subjected to FFT operation processing and rewritten to final operation results.

In the period T3, each multiplexer 45
a, 45b have a first input connected to a third output,
The second and third inputs are connected to a second output. Furthermore, the first inputs of the multiplexers 48a, 48b are connected to a second output, and the second and third inputs are connected to a first output. Thereby, the segment 46c,
47c stores the input data II and IQ of the third cycle, respectively. On the other hand, the data II and IQ of the second cycle stored in the segments 46b and 47b are provided to the data paths 70A and 70B, respectively, are subjected to FFT operation processing, and are rewritten into final operation results. Further, the input data I of the first cycle stored in the segments 46a and 47a
FFT operation results corresponding to I and IQ are output as output data OI and OQ via registers 91 and 92, respectively.

For example, as illustrated in the cycle T4, in each cycle, the complex number input data (II1, IQ1), (I
I2, IQ2), ..., (II256, IQ256)
The data is sequentially input in synchronization with the data input clock signal CLK1. Then, the input data II of the input real number part
.., II256 are stored in the segments 46d of the data storage unit 40, etc., in the data A1 to D1, A2 to D2,
.., Are sequentially stored as real parts of A64 to D64. Also, imaginary part input data IQ1, IQ2,..., IQ25
6 are sequentially stored as imaginary parts of the data A1 to D1, A2 to D2,..., A64 to D64 in the segment 47d or the like of the data storage unit 40. On the other hand, segments 46c, 4
The data once stored in the data path 70A, 7c, etc. is read out in synchronization with the operation clock signal CLK2.
70B, an FFT operation process is performed, and the intermediate result is again calculated as intermediate data, and the segments 46c and 47 are again processed.
The data is stored again in the same storage area such as c. Further, the re-stored intermediate result is repeatedly subjected to an FFT operation according to a predetermined procedure, and the final result is stored in the same storage area such as the segments 46c and 47c.

The final results stored in the segments 46b and 47b are output data OI1, OI2,..., OI2 of the real part in synchronization with the output clock signal CLK3.
56, and output data OQ1, OQ2,.
It is output as Q256 via registers 91 and 92, respectively. As described above, the data storage unit of the second embodiment has four segments 46a to 46
d and working memories 46 and 47 divided into segments 47a to 47d, and when input data from outside is input to one segment, data stored in the previous segment is read out to perform FFT operation processing. And a multiplexer 45a for switching to output the operation result stored in the previous segment.
45b, 48a and 48b. Thereby, when performing the FFT processing by reducing the number of sample points to 1/4,
By effective use of the working memories 46 and 47, parallel processing of data input, arithmetic processing, and data output becomes possible, thereby improving processing performance.

The present invention is not limited to the above embodiment, and various modifications are possible. For example, there are the following modifications (a) to (d). (A) The data storage units 40 and 40A have storage areas corresponding to the maximum number of sample points 1024, but the maximum number of sample points is not limited to 1024 and corresponds to the number of sample points according to the required processing accuracy. Is fine. (B) The configuration of the data paths 70A and 70B is not limited to the configuration shown in FIG. 4, and any configuration can be applied as long as it can perform FFT operation processing. (C) Although the FFT circuit of FIG. 1 includes the block floating point processing unit 60, it may be omitted if simplification of the circuit is more important than arithmetic processing accuracy. (D) In the data storage unit 40A of FIG. 6, four segments are sequentially and periodically allocated in the order of input, operation, output, and unused, but three segments are periodically allocated to input, operation, and output. It is also possible to allocate them in order, and to allocate the remaining one segment to be unused or used for other purposes.

[0033]

As described above in detail, according to the first aspect, the working storage means is divided into two segments for processing N / 2 samples, and these segments are inputted. An input control unit and an output control unit are provided for use in parallel with data input processing and calculation processing for calculating frequency components from input data.
For this reason, when the FFT operation is performed with the normal number of samples of 作業, the working storage unit can be effectively used, and the processing efficiency can be improved.

According to the second invention, the working storage means is set to N
/ 4 samples are divided into four segments for processing, and these segments are input data input processing, calculation processing for calculating frequency components from input data, and output processing for outputting calculation results And an input control unit and an output control unit to be used in parallel. For this reason, when the FFT operation is performed with the normal number of samples of 1/4, the working storage unit can be effectively used, and the processing efficiency can be further improved. According to the third invention, the first and second inventions are provided with block floating point processing means. This allows
The arithmetic processing can be performed by maximizing the number of significant digits of the input data, and in addition to the effects of the first and second inventions, there is an effect that the arithmetic accuracy can be improved.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of an FFT circuit according to a first embodiment of the present invention.

FIG. 2 is a configuration diagram illustrating an example of a conventional FFT circuit.

FIG. 3 is a configuration diagram of a data storage unit 40 in FIG.

FIG. 4 is a configuration diagram of data paths 70A and 70B in FIG. 1;

FIG. 5 is a diagram showing an operation sequence of the FFT circuit of FIG. 1;

FIG. 6 shows a data storage unit 4 according to the second embodiment of the present invention.
It is a block diagram of 0A.

FIG. 7 is a diagram showing an operation sequence of the data storage unit 40A of FIG.

[Explanation of symbols]

40, 40A Data storage units 41, 44, 45a, 45b, 48a, 48b Multiplexers 41a to 41d, 44a, 44b Selectors 42, 43 Working memories 42a, 42b, 43a, 43b, 46a to 46d, 4
7a to 47d Segment 50 Coefficient memory 60 Block floating point processing unit 70A, 70B Data path 93 Clock generation unit 94 Sequence control unit 95 Address generation unit

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Kenichi Tsuchida 1-10-11 Kinuta, Setagaya-ku, Tokyo Inside the Japan Broadcasting Corporation Broadcasting Research Institute (72) Inventor Shigeki Moriyama 1-10-11 Kinuta, Setagaya-ku, Tokyo No. Japan Broadcasting Corporation Broadcasting Technology Research Laboratory (72) Inventor Toru Kuroda 1-10-11 Kinuta, Setagaya-ku, Tokyo Japan Broadcasting Technology Broadcasting Research Laboratory F-term (reference) 5B056 AA00 BB13 CC01 CC03 FF05 FF06 FF07 GG00

Claims (3)

[Claims] 1. An input means for inputting discrete input data sampled at a constant period, and N (where N is a power of 2) samples sequentially input from the input means. Work storage means having a storage capacity for processing, a coefficient storage means for storing in advance a torsion coefficient for calculating a frequency component of input data input from the input means, the torsion coefficient and the work The arithmetic processing of calculating the intermediate result based on the input data stored in the working storage means and restoring the intermediate result in the working storage means is repeated according to a predetermined procedure to calculate the frequency component of the input data. A fast Fourier transform circuit provided with a frequency analysis unit for performing the above operation, wherein the working storage unit is provided with a storage area for processing the input data for N / 2 samples. An input process for storing the input data from the input unit, and the frequency analysis based on the input data stored in the segment by the input process. A fast Fourier transform circuit characterized in that an input control unit and an output control unit for sequentially and concurrently using a calculation process for calculating and outputting a frequency component by means are provided. 2. An input means for inputting discrete input data sampled at a constant period, and N (where N is a power of 2) samples of the input data sequentially inputted from the input means. Work storage means having a storage capacity for processing, a coefficient storage means for storing in advance a torsion coefficient for calculating a frequency component of input data input from the input means, the torsion coefficient and the work The arithmetic processing of calculating the intermediate result based on the input data stored in the working storage means and restoring the intermediate result in the working storage means is repeated according to a predetermined procedure to calculate the frequency component of the input data. A fast Fourier transform circuit provided with a frequency analysis unit that performs the above operation, wherein the working storage unit is provided with a storage area for processing the input data for N / 4 samples. An input process for storing the input data from the input unit, and the frequency analysis unit based on the input data stored in the segment by the input process. A fast Fourier transform circuit comprising: an input control unit and an output control unit for sequentially and concurrently using a calculation process for calculating a frequency component by using the calculation process and an output process for outputting a calculation result by the calculation process. . 3. A block floating point processing means for providing a common index to data used in the calculation processing and giving the index to the frequency analysis means for each calculation processing in the frequency analysis means. 3. The fast Fourier transform circuit according to 1 or 2.