JP3950466B2 - Fourier transform device - Google Patents

Description

  The present invention relates to a Fourier transform apparatus.

Conventionally, there is a technique called DFT (Discrete Fourier Transform) as one of the techniques for converting a time component signal into a frequency component signal. A general formula of DFT for frequency conversion of a signal at N points (indicating that the period is N) is as follows, where S _i is a time component signal value and S _k is a frequency component signal value: It can be expressed as 1).

In order to perform the calculation of (Equation 1), it is necessary to perform multiplication 4N ² times and addition / subtraction 2N ² + 2N (N−1) times. That is, as can be seen from (Equation 1), since the DFT performs complex operations, the rotation operation represented by the following (Equation 2) is actually performed for each value of the arguments k and i.

In (Equation 2), in order to obtain the frequency component signal values S _k [real] (real part) and S _k [imag] (imaginary part), the time component signal values S _i [real], cos θ, The multiplication of the value S _i [real] and sin θ, the signal value S _i [imag] and sin θ, and the signal value S _i [imag] and cos θ is performed N times for i, and further N times for k. Therefore, a total of 4N ² multiplications are required.

Furthermore, subtraction of the signal value S _i [real] cosθ and the signal value S _i [imag] sinθ obtained by multiplying the above, the addition of the signal value S _i [real] sinθ and the signal value S _i [imag] cosθ Since i is calculated N times for i and N times for k, and a double loop, a total of 2N ² + 2N (N−1) times is required. For example, Patent Documents 1 and 2 propose conventional examples of apparatuses that perform Fourier transform as described above.

Japanese Unexamined Patent Publication No. 07-006160 Japanese Patent Laid-Open No. 02-101574

  As described above, in the conventional DFT, it is necessary to perform many multiplications and additions / subtractions. For this reason, there has been a problem that the processing takes an enormous amount of time. Therefore, conventionally, a technique called FFT (Fast Fourier Transform) has been developed and used in the field of digital signal processing in order to make the DFT processing time as short as possible.

  In this FFT, a basic calculation called butterfly calculation is repeatedly performed over several stages so that the calculation amount of the DFT can be reduced. That is, when performing Fourier transform of period N in FFT, frequency analysis is performed by dividing the period N into several stages for each predetermined radix and performing butterfly computation for each radix.

  In this FFT, it is possible to perform several stages of butterfly operations in parallel by pipeline processing. In that case, an intermediate buffer memory is required to temporarily store the results calculated over several stages. However, the conventional FFT has a problem that the total memory capacity of each intermediate buffer memory becomes very large.

  In other words, because of the nature of each butterfly computation that constitutes the FFT, only a relatively small number of radixes can be selected, resulting in an increase in the number of butterfly computation stages. For this reason, the number of intermediate buffer memories for temporarily storing the results of each butterfly operation increases, and the capacity of each intermediate buffer memory also increases, resulting in a very large total memory capacity. I was sorry. Furthermore, by repeatedly performing basic operations over several stages, access to the intermediate buffer memory having a large capacity increases. When accessing a large-capacity intermediate buffer memory, it takes a long access time. Therefore, if the number of accesses increases, the access time becomes enormous and the processing speed for performing the Fourier transform decreases. there were.

  The present invention has been made to solve such a problem, and makes it possible to shorten the processing time for performing Fourier transform in digital signal processing and to be used for the processing. It is an object to reduce the capacity of the intermediate buffer memory.

The Fourier transform apparatus according to the present invention applies a time component signal of a period N (= n ₁ × n ₂ ) arranged in a two-dimensional manner with a period n _{1 in} the horizontal direction and a period n _{2 in} the vertical direction. M n ₂ long Fourier transform means for performing a Fourier transform of period n ₂ with respect to m, m intermediate buffer memories for temporarily storing the transformation results of the m n ₂ long Fourier transform means, and the m pieces Rotation calculation means for performing rotation calculation on the data stored in the intermediate buffer memory, and m n ₁ long Fouriers for performing Fourier transform of the period n _{1 in} the horizontal direction on the calculation result by the rotation calculation means conversion means, together with the data determined to not to allow the product to be stored in the same intermediate buffer memory by the same n ₂ length Fourier transform means over a plurality of cycles, it is used by the same n ₁ length Fourier transform means That data is not to allow the product to be stored in the same intermediate buffer memory, the m data obtained respectively by the m-number of n ₂ length Fourier transform means one by one to the m-number of intermediate buffer memories and a data distributing means to be distributed and stored, performs n ₁ times n ₂ length Fourier transform processing by using the m-number of n ₂ length Fourier transform means in parallel, the m-number of n ₁ N ₂ times of n ₁ long Fourier transform processing is performed in parallel using the long Fourier transform means, and the same n ₁ long Fourier transform means is applied to m data distributed in the same cycle by the data distribution means. The n ₁ long Fourier transform process is performed in cycles different from each other.

The present invention comprises the above technical means, and the time component signal of period N is not frequency-transformed at once by the Fourier transform of period N, but the Fourier transform of periods n ₁ and n ₂ smaller than the period N is performed. Since the frequency conversion is performed by the combination, the amount of calculation performed by the Fourier transform of the small periods n ₁ and n ₂ is larger than the amount of calculation performed by the Fourier transform of the period N because of the nature of the Fourier transform operation. Even if the amount of calculation performed by the Fourier transform of the small cycles n ₁ and n _{2 and} the amount of calculation performed by the rotation calculation are summed, the frequency conversion is performed at once by the Fourier transform of the cycle N. The amount of calculation is smaller than the amount of calculation of a conventional DFT designed to perform the above. Further, the Fourier transform of the small cycles n ₁ and n ₂ is performed in parallel using m n ₂ long Fourier transform means and n ₁ long Fourier transform means, and the same number of intermediate buffer memories are prepared. Thus, the data obtained by the same n ₂ long Fourier transform means is prevented from being stored in the same intermediate buffer memory over a plurality of cycles, and the data used by the same n ₁ long Fourier transform means is In order not to be stored in the same intermediate buffer memory, m data respectively obtained by the m n ₂ long Fourier transform means are distributed and stored one by one in the m intermediate buffer memories. to make it, the relative further said data distribution unit m data distributed by the same cycle by the same n ₁ length Fourier transform means Since to carry out the n ₁ length Fourier transform processing at different cycles have, with the number of operation cycles is reduced, access to the intermediate buffer memory also becomes possible to efficiently parallelize, is shortened to remarkably access time It becomes possible.

According to the present invention, the frequency analysis of the signal of the time component of the cycle N (= n ₁ × n ₂ ) is performed by the Fourier transform of the cycle n _{1 in} the horizontal direction which is a cycle smaller than the cycle N and the cycle n in the vertical direction. be performed by a combination of _two of the Fourier transform, performs in parallel with the small period n _1, m pieces of n ₂ length Fourier transform means Fourier transform of n ₂ and n ₁ length Fourier transform unit, the same A plurality of intermediate buffer memories are prepared so that data obtained by the same n ₂ long Fourier transform means is not stored in the same intermediate buffer memory over a plurality of cycles, and the same n ₁ long Fourier as never data used by the conversion means is stored in the same intermediate buffer memory, it is respectively determined by the m-number of n ₂ length Fourier transform means m data to be stored are distributed one by one to the m-number of intermediate buffer memory, further for m pieces of data sorted in the same cycle by the data distributing means, the same n ₁ length Fourier transform means Since the n ₁ long Fourier transform processing is performed in different cycles using the above, the amount of computation is made smaller than the amount of computation of the conventional DFT in which frequency transformation is performed at once by the Fourier transform of the period N. be able to. In addition, the number of operation cycles can be reduced, and access to the intermediate buffer memory can be efficiently parallelized to shorten the access time. Thereby, the capacity of the intermediate buffer memory as a whole can be remarkably reduced, and the processing speed of the Fourier transform can be increased.

  Hereinafter, an embodiment of the present invention will be described with reference to the drawings. Conventionally, processing for converting a time component signal into a frequency component signal with a period N, that is, N-point DFT processing, is performed at once by N-length Fourier transform as shown in FIG. On the other hand, in the Fourier transform apparatus of the present embodiment, the process is divided into the first to fifth phases as shown in FIGS.

That is, in the first phase, as shown in FIG. 2A, the input one-dimensional N digital signals are rearranged into a two-dimensional arrangement of n ₁ horizontal × n ₂ vertical. In the second phase, as shown in FIG. 2 (b), the side by side in the two-dimensional data arrangement for changing the number of n ₂ length DFT processing in the transverse direction relative to the longitudinal direction using the n ₂ pieces of data n Do only _one .

Next, in the third phase, as shown in FIG. 2C, rotation calculation is performed on the result obtained by the n ₂ long DFT process. In the fourth phase, as shown in FIG. 2 (d), the result of the rotation operation, performs n ₁ length DFT processing the number n ₂ of the vertical direction using the n ₁ pieces of data in the lateral direction . Finally, in the fifth phase, as shown in FIG. 2E, the results obtained by the n ₁ length DFT processing are rearranged into a one-dimensional data arrangement.

  FIG. 1 is a diagram showing a configuration of a Fourier transform apparatus according to the present embodiment, and is a diagram showing a configuration for performing the processing of the five phases shown in FIG. In FIG. 1, reference numeral 1 denotes a first rearrangement unit, which performs the first phase process. The first rearranging means 1 can be easily configured by a memory and an addressing device, for example. This rearrangement process is expressed by the following equation (3).

Reference numeral 2 denotes n ₂ long Fourier transform means, which performs the second phase process according to the following (Equation 4). That is, in the two-dimensional data arrangement rearranged by the first rearranging means 1, n ₂ length DFT processing in the vertical direction is performed n ₁ times.

Reference numeral 3 denotes rotation calculation means, which performs the third phase process according to the following (Equation 5). That is, the rotation calculation is performed on the data obtained as a result of the calculation process by the n ₂ long Fourier transform means 2.

Reference numeral 4 denotes an intermediate buffer memory which temporarily stores data subjected to Fourier transform by the n ₂ long Fourier transform means 2. The above rotation calculation means 3 performs a rotation calculation on the data stored in the intermediate buffer memory 4 and supplies the calculation result to the n ₁ long Fourier transform means 5.

The n ₁ long Fourier transform means 5 uses the data obtained as a result of the rotation calculation by the rotation calculation means 3 to perform the fourth phase process according to the following (Equation 6). That is, in the rearranged two-dimensional data arrangement, n ₁ -length DFT processing in the horizontal direction is performed n ₂ times.

Reference numeral 6 denotes a second rearranging unit, which performs the process of the fifth phase. That is, the frequency component signal _Sk is obtained by rearranging the data obtained by the n ₁ long Fourier transform means 5 again in a one-dimensional manner according to the following (Equation 7). The second rearranging means 6 can be composed of a memory and an addressing device, like the first rearranging means 1.

The DFT processing of the present embodiment performed by dividing into the five phases shown in the above (Formula 3) to (Formula 7) is equivalent to the conventional DFT process performed in (Formula 1), and the same calculation result (Signal S _k having the same frequency component) can be obtained. On the other hand, the amount of calculation until the calculation result is obtained is smaller in the present embodiment than in the prior art. This will be described below.

  Since the first and fifth phase processes in the DFT process of this embodiment are merely data rearrangement processes (memory addressing processes), no computation is performed. Therefore, the total calculation amount in this embodiment is the sum of the calculation amounts of the respective processes in the second to fourth phases. Table 1 below shows the amount of calculation.

As is apparent from Table 1, the number of multiplications performed in the DFT processing of this embodiment is 4n ₁ n ₂ (n ₁ + n ₂ +1), and the number of additions / subtractions is 2n ₁ n ₂ (2n ₁ + 2n ₂ +1) times. On the other hand, as described in the conventional example, the number of multiplications performed in the conventional DFT processing is 4N ² = 4n ₁ ² n ₂ ² times. The number of additions / subtractions is 2N ² + 2N (N−1) = 4n ₁ ² n ₂ ² −2n ₁ n ₂ , and 2n ₁ n ₂ can be considered to be negligibly small. ₁ ² n ₂ ² times.

As can be seen by comparing the number of multiplications and the number of additions / subtractions between this embodiment and the prior art, if the values of n ₁ and n ₂ are both 3 or more, the calculation in the DFT processing of this embodiment is performed. The amount can be surely reduced as compared with the calculation amount in the conventional DFT processing.

  Next, comparing the DFT processing of this embodiment with the conventional FFT processing, it can be said that the conventional FFT is a special example of the DFT of this embodiment. That is, in the DFT of the present embodiment, the actual calculation is performed in three stages of the second to fourth phases. On the other hand, in the conventional FFT, the second phase and the third phase or the third phase and the fourth phase are grouped together to rearrange the flow of operations, and are performed in a form of butterfly computation. Is.

  For this reason, from the viewpoint of the amount of calculation, it can be said that there is no difference between the DFT of the present embodiment and the conventional FFT. However, from the viewpoint of the capacity of the intermediate buffer memory that is required when the processing of each phase is pipelined and performed in parallel, the DFT of the present embodiment has an advantage that a memory capacity much smaller than that of the conventional FFT is required. is there.

That is, in this embodiment, the memory capacity required for the intermediate buffer memory 4 is n ₁ × n ₂ words. Furthermore, if the cycle n ₁ of the n ₁ long DFT processing in the second phase is further divided into the horizontal direction n ₁₁ and the vertical direction n ₁₂ (n ₁ = n ₁₁ × n ₁₂ ), A memory for n ₁₁ × n ₁₂ words is required in the middle part. Further, if the cycle n ₂ of the n ₂ long DFT processing in the fourth phase is further finely separated and processed as the horizontal direction n ₂₁ and the vertical direction n ₂₂ (n ₂ = n ₂₁ × n ₂₂ ), A memory for n ₂₁ × n ₂₂ words is required in the middle part.

In the same manner, if the period is further finely divided and the vertical DFT processing and the horizontal DFT processing are performed, for example, when performing frequency analysis of N = 2 ¹⁶ points, it is necessary for each intermediate buffer memory. The memory capacity is as shown by the numbers in each square in FIG. Therefore, the total memory capacity of the intermediate buffer memory is 66176 words, which is the total memory capacity of the intermediate buffer memories.

  Of course, as shown in FIG. 3A, it is not always necessary to subdivide the period until the period becomes the smallest, and the memory capacity required in that case is smaller than the above 66176 words.

  On the other hand, in the conventional FFT, frequency analysis is performed by butterfly calculations in several stages. However, as described above, the radix of each butterfly calculation can take only a small value. Therefore, the memory capacity required for each intermediate buffer memory when the radix is 2 is shown in FIG. FIG. 3B shows that the total memory capacity required for the intermediate buffer memory is 131102 words.

  As is clear from comparison between FIG. 3A and FIG. 3B, according to the DFT processing of this embodiment, the memory capacity of the intermediate buffer memory required when the processing of each phase is operated in parallel. Can be made smaller than the memory capacity required for parallel operation of each butterfly operation in the conventional FFT.

  As described above, according to the Fourier transform device of the present embodiment, the amount of calculation required for a series of Fourier transform processes can be reduced, and the intermediate buffer memory used when each phase is operated in parallel. It is also possible to reduce the total memory capacity.

  In the above embodiment, the device including the first rearranging means 1 and the second rearranging means 6 is treated as one Fourier transform device, but means for rearranging such data. Are not necessarily provided in the Fourier transform apparatus.

  Using the Fourier transform apparatus of the present embodiment as described above, several application examples described below can be realized.

  In the first example, a Fourier transform device having a larger period is configured by providing two Fourier transform devices having a certain small period in series and adding a small-scale rotation arithmetic unit therebetween. .

For example, as shown in FIG. 4, an n ₂ -length DFT device 11 and an n ₁ -length DFT device 14 are provided in series, and a rotation arithmetic device 12 and an intermediate having a capacity of (n ₁ × n ₂ ) words therebetween. By adding the buffer memory 13, a DFT device having a large period of N = n ₁ × n ₂ is formed. Then, N point frequency analysis is performed by pipelining the n ₂ length DFT and the n ₁ length DFT.

As described above, performing a frequency analysis of a large period N at a time with one DFT apparatus has a very large calculation load, whereas a frequency analysis is performed with a combination of small periods n ₁ and n _2. The calculation load is small. Therefore, according to this apparatus, there is an advantage that the overall processing speed can be increased.

The second example is n ₂ length DFT process in the second phase and the n ₁ length DFT process in the fourth phase by utilizing the higher respectively independent, performing the n ₂ length DFT processor And a plurality of devices for performing the n ₁ long DFT processing are provided to constitute one Fourier transform device.

For example, as shown in FIG. 5, m ₁ (word / s) n ₂ length DFT unit 21a having the computing power of, 21b, ..., 21c to be provided _one l with composing the n ₂ length DFT unit group 21 , m ₂ (word / sec) n ₁ length DFT unit 24a having the computing power of, 24b, ..., 24c to constitute the n ₁ length DFT unit group 24 provided _two l.

Then, between the n ₂ long DFT device group 21 and the n ₁ long DFT device group 24, there is a rotation computing device 22 having a computing capacity of m ₃ (words / second) and (n ₁ × n ₂ ) words worth. By providing the intermediate buffer memory 23 having a capacity, one Fourier transform device is configured.

As already described, in the second phase, it is necessary to perform n ₂ length DFT processing n ₁ times. Therefore, n ₂ length DFT unit 21a constituting the n ₂ length DFT unit group 21, 21b, ..., ₁ or n and 21c, or by providing only appropriate number divided by the number, n ₁ times n ₂ length DFT Perform processing in parallel. As a result, the n ₂ long DFT process can be performed in a shorter time.

For example, the case of n ₁ = 4, as in the example of Figure 4 shown above, than performing one in the n _2-length DFT unit 11 n ₁ times n ₂ length DFT process it takes 4 cycles On the other hand, if _two n ₂ long DFT devices are provided, it can be performed in two cycles. If four n ₂ long DFT devices are provided, it can be performed in one cycle.

Similarly, in the fourth phase, n ₁ long DFT devices 24a, 24b,..., 24c constituting the n ₁ long DFT device group 24 are provided by n ₂ or a number obtained by dividing by an appropriate number. , N ₂ times of the n ₁ length DFT processing can be reduced. Thereby, a faster Fourier transform apparatus can be obtained.

The overall computing capability of the n ₂ long DFT device group 21 is l ₁ × m ₁ (words / second), and the computing capability of the n ₁ long DFT device group 24 as a whole is l ₂ × m _2. (Words / second). Here, when m ₃ ≦ l ₁ × m ₁ or m ₃ ≦ l ₂ × m ₂ is satisfied, the n ₂ -length DFT device group 21 and the n ₁ -length DFT device group 24 have m ₃ (words / second). Limited to computing power.

  In the third example, a plurality of Fourier transform devices having a certain small period are used, and they are connected by being stacked via a rotation operation device (the image has the tree structure shown in FIG. 3A). In this way, a Fourier transform device having a larger period is configured.

  For example, consider a case where a 4096-point Fourier transform apparatus having a larger period is configured using a plurality of 4-point Fourier transform apparatuses. In this case, as shown in FIG. 6, the 4096-point Fourier transform device is roughly divided into a 16-point Fourier transform device 31, a 4096-point rotation calculation device 32, a 4096-point buffer memory 33 having a capacity of 4096 words, And a 256-point Fourier transform device 34.

  The 16-point Fourier transform device 31 includes two 4-point Fourier transform devices 31a and 31d, a 16-point rotation calculation device 31b, and a 16-point buffer memory 31c having a capacity of 16 words. The 256-point Fourier transform unit 34 includes two 16-point Fourier transform units 34a and 34d, a 256-point rotation calculation unit 34b, and a 256-point buffer memory 34c having a capacity of 256 words.

Further, one 16-point Fourier transform device 34a in the 256-point Fourier transform device 34 is similar to the 16-point Fourier transform device 31 in that two 4-point Fourier transform devices 34a ₁ and 34a ₄ and 16-point rotation. The arithmetic unit 34a ₂ and a 16-point buffer memory 34a ₃ having a capacity of 16 words are included.

Similarly to the 16-point Fourier transform device 31, the other 16-point Fourier transform device 34 d also has two 4-point Fourier transform devices 34 d ₁ and 34 d ₄ , a 16-point rotation calculation device 34 d _2, and a capacity for 16 words. It constituted by a 16-point buffer memory 34d ₃ with.

  In this way, a 4096-point Fourier transform apparatus with a larger period is configured by using a plurality of small-period 4-point Fourier transform apparatuses and connecting them so as to form a tree structure via a rotation arithmetic unit. . Note that each rotation arithmetic unit used in this apparatus plays a role of multiplication that connects branches of a tree.

  That is, in the apparatus shown in FIG. 6, the frequency analysis of 4096 points is performed by dividing it into 16 vertical points × 256 horizontal points. When performing frequency analysis of 16 vertical points, it is further divided into 4 vertical points × 4 horizontal points. Similarly, when performing frequency analysis of 256 horizontal points, it is divided into four vertical and four horizontal Fourier transforms.

  Performing frequency analysis of 4096 points at one time with a single 4096-point Fourier transform device is very computationally intensive, but performing frequency analysis with a combination of four-point Fourier transform devices with a small period requires a small computational load. Is as described above. Therefore, according to the present apparatus, the processing load as a whole can be reduced and the processing speed can be increased.

  Further, the total memory capacity of the intermediate buffer memory used in this apparatus is 4096 + 16 + 256 + 16 + 16 = 4440 words. On the other hand, when a 4096-point Fourier transform apparatus is configured by conventional FFT, the total memory capacity of the buffer memory is 4096 + 1024 + 256 + 64 + 16 + 4 × 6 = 5480 words even when the radix of each butterfly operation is 4.

  As is apparent from the above, according to the apparatus of FIG. 6, not only can the amount of calculation required for 4096 points of DFT processing be reduced to shorten the processing time to the same level as FFT, but also the calculation process. It is also possible to reduce the memory capacity of the intermediate buffer memory used in FIG.

  The fourth example is an example in which the third example shown in FIG. 6 is applied. That is, a single Fourier transform device is configured using a rotation computation device and a 16-point Fourier transform device that can be used for windowing computation. By using this in time sharing (time division), frequency analysis with a larger period (4096 points) can be performed.

  The Fourier transform is originally performed in an infinitely long cycle in the mathematical story. However, it is impossible as a real problem to actually do this. Therefore, in practice, frequency analysis is performed by considering a fixed interval at a period N and connecting the end points to an infinite length. However, in this case, if there is a discontinuity at the end point, an abnormal frequency component, that is, a frequency leakage component may occur.

The windowing operation described above is performed for the purpose of eliminating this discontinuity at the end points and reducing the frequency leakage component, and is performed by the following equation (Equation 8). In (Equation 8), S _k represents data to be subjected to Fourier analysis, w (k) represents a window function, and S _k ′ represents actual sample data.

  By the way, although this windowing operation is not precise, it can be considered to be almost the same as the rotation operation shown in the following (Equation 9). Therefore, if a coefficient is given well, it is possible to perform windowing calculation using a rotation calculation device. Therefore, in the fourth example, the rotation calculation device can be used for windowing calculation.

  FIG. 7 is a diagram showing a configuration of an apparatus for realizing the fourth example. As shown in FIG. 7, this apparatus includes a windowing / rotation computing device 41 that can also be used for windowing computation, a 16-point Fourier transform device 42, a 4096-point buffer memory 43 having a capacity of 4096 words, A 256-point buffer memory 44 having a capacity of 256 words, a data input unit 45, and a data output unit 46 are included.

  The rotation calculation device 41 includes means for giving an appropriate coefficient when performing windowing calculation. In addition, the 16-point Fourier transform device 42 includes two 4-point Fourier transform devices 42a and 42d, a 16-point rotation calculation device 42b, and a 16-point buffer, like the 16-point Fourier transform devices shown in FIG. And a memory 42c.

  The Fourier transform device configured in this way is a portion indicated by α, β, γ in FIG. 6 (all portions are a 16-point Fourier transform device and a rotation computation device, or a 16-point Fourier transform device and a windowing computation device). Frequency analysis of 4096 points is performed by performing the processing of (including the above) in a time-sharing manner.

  That is, as shown in FIG. 8, first, using the data input via the data input unit 45, an operation corresponding to the portion of α in FIG. 6 is performed. At this time, the windowing / rotation calculation device 41 performs windowing calculation by giving an appropriate coefficient. The calculation result of the portion α is sequentially stored in the 4096-point buffer memory 43 via the data output unit 46.

  When data is accumulated in the 4096-point buffer memory 43, the data is then input via the data input unit 45, and an operation corresponding to β in FIG. 6 is performed. The calculation result of the β part is sequentially stored in the 256-point buffer memory 44 via the data output unit 46. Next, when data is accumulated in the 256-point buffer memory 44, the data is input via the data input unit 45, and an operation corresponding to γ in FIG. 6 is performed.

  As described above, according to the apparatus shown in FIG. 7, the Fourier transform of a large period is performed by a combination of Fourier transforms of a small period. Can do. Furthermore, unlike the device of FIG. 6, the same device is used many times in a time-sharing manner, so that the number of four-point Fourier transform devices and intermediate buffer memories can be reduced compared to the device of FIG. The overall scale can be reduced.

  In the fifth example, when an intermediate buffer memory is configured by using a memory having a high-speed page mode, and the intermediate buffer memory is arranged in the memory having the high-speed page mode, the intermediate buffer memory is not arranged in a stripe pattern, but vertically and horizontally. The memory access time can be shortened by arranging them in the form of blocks.

  In general, an IC memory having a high-speed page mode is manufactured in a two-dimensional matrix. The desired data is obtained by designating the position by the row (column) and the column (row). In this case, in a memory represented by a DRAM, a row address is designated first and a column address is designated next due to the feature of the mechanism.

  In the high-speed page mode, when column addresses are successively specified for the same row address, access can be performed at a higher speed than when column addresses are specified for different row addresses. An example of a memory having such a high-speed page mode is a Hitachi memory (HM511OOOA-6).

  By the way, as described above, in the Fourier transform apparatus of the present embodiment, the DFT process for the vertical direction is performed in the second phase, and the DFT process for the horizontal direction is performed in the fourth phase. For this reason, data is read and written in the vertical direction and the horizontal direction of the intermediate buffer memory formed in two dimensions.

  Here, when the intermediate buffer memory 4 is arranged in a stripe shape in the horizontal direction, since the high-speed page mode in the vertical direction cannot be used, the memory access time in the horizontal direction is fast, but the memory access time in the vertical direction is slow. End up. On the other hand, if the blocks are arranged, the high-speed page mode can be used when reading and writing data in the vertical direction, so that both the access time in the horizontal direction and the access time in the vertical direction can be shortened.

  FIG. 9 is a time chart showing the state of access time of the above-mentioned Hitachi memory. In the example of FIG. 9, a case where two column addresses are successively specified for the same row address is shown.

  That is, normally, the time (cycle time) required to access one word is 120 nsec, while the time required to access two words in the high-speed page mode is 155 (= 60 + 45 + 50) nsec. . That is, it can be seen from FIG. 9 that the access time per word is 77.5 nsec, which is shorter than the normal time.

A specific example when such a Hitachi memory is used as an intermediate buffer memory is shown below. Here, the total memory capacity of the intermediate buffer memory is assumed to be 2 ¹⁸ words (vertical 2 ⁹ words × width 2 ⁹ words).

First, as shown in FIG. 10, consider the case of placing the intermediate buffer memory in stripes in the lateral direction by 2 ⁹ words minutes. In this case, when the data obtained in the second phase is written in the intermediate buffer memory in the vertical direction, the high-speed page mode cannot be used, and therefore it takes 120 nsec per word in the vertical direction.

Further, when data is read from the intermediate buffer memory in the fourth phase, the access time per word in the horizontal direction is (60 + 45 × (2 ⁹ −1) +50) / 2 ⁹ ≈45.13 nsec. It is. Therefore, the upper limit of the data rate related to memory access is 120 + 45.13 = 165.13 nsec / word.

Next, as shown in FIG. 11, consider the case of placing on the intermediate buffer memory 2 ⁹ words minutes by blocky (vertical 2 ⁴ × horizontal 2 ^5). In this case, since it is possible to use the high-speed page mode when accessing the memory in the vertical direction, the time required to write the data obtained in the second phase to the intermediate buffer memory is one word per word in the vertical direction. (60 + 45 × 15 + 50) /16≈49.06 nsec.

  Further, when data is read from the intermediate buffer memory in the fourth phase, the access time per word in the horizontal direction is (60 + 45 × 31 + 50) /32≈47.03 nsec. Therefore, the upper limit of the data rate related to memory access is 49.06 + 47.03 = 96.09 nsec / word.

  As is apparent from the above calculation results, the memory access time can be shortened by arranging the intermediate buffer memory in a block shape as compared with the case where the intermediate buffer memory is arranged in a stripe shape. As a result, it is possible not only to reduce the amount of computation when performing the Fourier transform processing as described above, but also to reduce the access time to the intermediate buffer memory used in the process of processing, and as a whole The processing time can be further shortened.

  In the sixth example, when the processing of the second phase and the processing of the fourth phase are operated in parallel, the intermediate buffer memory is devised by devising the addressing operation when data is read from and written to the intermediate buffer memory. Is prepared for only one page.

  Since the data obtained in the second phase is used when the fourth phase process is performed, the fourth phase process cannot be performed unless the second phase process is completed. Therefore, when the processing of the second phase and the processing of the fourth phase are operated in parallel, normally, as shown in FIG. 12, two pages for the second phase and the fourth phase are used. Intermediate buffer memory is required.

  That is, when the second phase and the fourth phase are operated in parallel, as shown in FIG. 12A, the data obtained by the vertical DFT processing in the second phase is sequentially stored in the vertical direction. At the same time, as shown in FIG. 12B, it is necessary to read out already obtained data in the horizontal direction in the fourth phase and sequentially perform the DFT processing in the horizontal direction.

  Accordingly, the intermediate buffer memory includes two pages, a page for sequentially storing data required in the second phase in the vertical direction and a page for reading and using data in the horizontal direction in the fourth phase. I need it. However, if two pages of intermediate buffer memory are prepared in this way, the memory capacity becomes very large.

  Therefore, in the sixth example, the data obtained in the second phase is written in the vertical direction as before, and the data is read in the horizontal direction in the process of the fourth phase. As shown in FIG. 13, in the second and fourth phases performed for the first time, data is read and written in the vertical direction. In the second and fourth phases performed for the second time, the addressing direction is switched alternately between vertical and horizontal, such as reading and writing data in the horizontal direction.

  That is, in FIG. 13A, in the fourth phase process performed for the first time, the data already stored in the intermediate buffer memory (the zeroth process performed before the fourth phase process) is stored. Data obtained in the processing of the second phase) are sequentially read in the vertical direction.

  Then, the data obtained in the first second-phase processing that is performed simultaneously with the fourth-phase processing is sequentially written in the vertical area emptied by the reading. Then, finally, the data obtained by the first second phase process is stored in all the areas of the intermediate buffer memory.

  Next, in FIG. 13B, in the process of the fourth phase performed for the second time, the data stored in the intermediate buffer memory (the data obtained in the process of the second phase of the first time) is changed horizontally. Read sequentially in the direction.

  Then, the data obtained in the second second-phase processing that is performed simultaneously with the fourth-phase processing is sequentially written in the horizontal area emptied by the reading. Then, finally, the data obtained by the second second-phase process is stored in all areas of the intermediate buffer memory. Thereafter, the process shown in FIG. 13A is performed again.

  As described above, when the addressing direction is alternately switched to read / write data, the area that is freed by reading data is effectively used, and one intermediate buffer memory is used for the second phase. And the fourth phase can be shared, and only one page of intermediate buffer memory needs to be prepared.

  The seventh example is an example in which the second example shown in FIG. 5 is applied. As shown in FIG. 5, when the processes are parallelized using a plurality of DFT devices, access to the intermediate buffer memory 23 becomes very large. Therefore, in the seventh example, the intermediate buffer memory 23 is divided into a plurality of memories, and the parallel operability at the time of memory access is improved by using a data distribution device such as a crossbar switch. It is something that can be done.

FIG. 14 is a diagram showing a configuration of an apparatus for realizing the seventh example. The apparatus shown in FIG. 14 is a modification of the apparatus shown in FIG. 5, and sets the values of periods n ₁ and n ₂ shown in FIG. 5 to 4 and performs n ₁ length DFT processing. number l _1, n ₂ length DFT process the number l ₂ of the apparatus for performing the illustrates the case of a four respectively.

  That is, this apparatus includes four four-point Fourier transform devices 51a, 51b, 51c, 51d that perform processing of the second phase, a data distribution device 52, and four intermediate buffer memories 53a, 53b that can operate in parallel. , 53c, 53d and four four-point Fourier transform devices 54a, 54b, 54c, 54d for performing the process of the fourth phase. Here, for the sake of simplification of description, the rotation calculation device is not shown.

Next, the operation of the apparatus configured as described above will be described with reference to the layout diagram of intermediate data shown in FIG. In this apparatus, the four-point Fourier transform is performed in the vertical direction in the second phase, and the four-point Fourier transform is performed in the horizontal direction in the fourth phase. 16-point frequency analysis is performed.

  At this time, the four 4-point Fourier transform devices 51a, 51b, 51c, and 51d that perform the processing of the second phase described above simultaneously perform the Fourier transform using the data in the vertical direction of FIG. Thereby, in the first cycle, the Fourier-transformed data for the first, second, third and fourth words is obtained at the same time.

  The four data simultaneously obtained in this way are sorted and stored one by one in the four intermediate buffer memories 53a, 53b, 53c, and 53d by the data sorting device 52. Here, the types of the intermediate buffer memories 53a, 53b, 53c, and 53d in which the data of each word are stored are indicated by the symbols A to D, respectively.

  Normally, four cycles are required to write four data to one intermediate buffer memory. In this embodiment, four data are stored in four intermediate buffer memories 53a, 53b, 53c, and 53d. Since writing is performed in a distributed manner, writing can be performed in one cycle.

  Similarly, the data simultaneously Fourier-transformed in each cycle of the second cycle to the fourth cycle is also allocated to the four intermediate buffer memories 53a, 53b, 53c, 53d by the data distribution device 52 and stored. Is done. At this time, sorting is performed so that data converted by the same Fourier transform device is not stored in the same intermediate buffer memory.

  As a result of the write operation as described above, the data of each word is stored in the four intermediate buffer memories 53a, 53b, 53c, and 53d in the relationship shown in FIG. That is, the first intermediate buffer memory 53a stores data of the first, sixth, eleventh, and sixteenth words, and the second intermediate buffer memory 53b stores the fifth, tenth, fifteenth, and fifth data. Four words of data are stored.

  The third intermediate buffer memory 53c stores the ninth, fourteenth, third, and eighth word data, and the fourth intermediate buffer memory 53d stores the thirteenth, second, seventh, and eighth data. 12 words of data are stored.

  Next, when performing the process of the fourth phase, the four four-point Fourier transform devices 54a, 54b, 54c, 54d that perform the process of the fourth phase described above are data for the horizontal direction of FIG. Is used to perform Fourier transform simultaneously. That is, in the first cycle, the four four-point Fourier transform devices 54a, 54b, 54c, and 54d read the data of the first, fifth, ninth, and thirteenth words, respectively, and simultaneously perform the Fourier transform.

  In this case, as is apparent from FIG. 15, four data simultaneously used by the four-point Fourier transform devices 54a, 54b, 54c and 54d are stored in the four intermediate buffer memories 53a, 53b, 53c and 53d. The words are stored in a distributed manner. Therefore, if all the above four data are stored in one intermediate buffer memory, it can be read in one cycle in this embodiment, where four cycles are required for reading.

  As described above, according to the device of the seventh example shown in FIG. 14, when the DFT processing is performed in parallel using a plurality of Fourier transform devices, the access to the intermediate buffer memory is also efficiently performed. Parallelization can be performed, and parallel operability of the entire apparatus can be improved. For reference, FIG. 16 shows the above-described data read / write procedure.

It is a block diagram which shows the structure of the Fourier-transform apparatus which is one Example of this invention. It is a figure for demonstrating the processing content of the 1st-5th phase performed by the Fourier-transform apparatus of FIG. FIG. 6 is a diagram for comparing the capacity of the intermediate buffer memory required when the Fourier transform apparatus of the present embodiment has a tree structure with the capacity of the intermediate buffer memory required when paralleling the FFT butterfly operations. is there. It is a figure which shows the structure of the apparatus by the 1st application example. It is a figure which shows the structure of the apparatus by the 2nd application example. It is a figure which shows the structure of the apparatus by the 3rd application example. It is a figure which shows the structure of the apparatus by the 4th application example. It is a figure for demonstrating the mode of the time division process performed by the apparatus shown in FIG. It is a time chart which shows the mode of the access time of the intermediate | middle buffer memory with a high-speed page mode used by the 5th application example. It is a figure which shows a mode that the intermediate buffer memory has been arrange | positioned at stripe form. It is a figure which shows a mode that the intermediate buffer memory has been arrange | positioned in block shape. It is a figure for demonstrating a mode that data reading / writing is performed using the intermediate buffer memory for 2 pages. It is a figure for demonstrating the mode of reading / writing of the data by the 6th application example, and is a figure for demonstrating a mode of reading / writing data using the intermediate buffer memory for 1 page. It is a figure which shows the structure of the apparatus by the 7th application example. It is a figure for demonstrating the relationship between several intermediate | middle buffer memory and the data memorize | stored in it. It is a figure which shows the procedure of the reading / writing of the data by the 7th application example.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 1st rearrangement means 2 n ₂ length Fourier transform means 3 Rotation calculation means 4 Intermediate buffer memory 5 n ₁ length Fourier transform means 6 2nd rearrangement means

Claims (1)

For a time component signal of period N (= n ₁ × n ₂ ) arranged two-dimensionally with period n _{1 in} the horizontal direction and period n _{2 in} the vertical direction, a Fourier transform with period n _{2 in} the vertical direction is performed. M n ₂ long Fourier transform means to perform;
M intermediate buffer memories for temporarily storing the conversion results by the m n ₂ long Fourier transform means;
Rotation calculation means for performing rotation calculation on the data stored in the m intermediate buffer memories;
M number of n ₁ long Fourier transform means for performing a Fourier transform of period n _{1 in} the lateral direction on the computation result by the rotation computation means;
The data obtained by the same n ₂ long Fourier transform means is prevented from being stored in the same intermediate buffer memory over a plurality of cycles, and the data used by the same n ₁ long Fourier transform means is the same intermediate. In order not to be stored in the buffer memory, the m data respectively obtained by the m n ₂ long Fourier transform means are distributed and stored one by one in the m intermediate buffer memories. Data distribution means to
The m n ₂ long Fourier transform means are used to perform n ₁ times n ₂ long Fourier transform processes in parallel, and the m n ₁ long Fourier transform means are used to perform n ₂ times n ₁ long Fourier transform processes. The conversion processes are performed in parallel, and the n ₁ long Fourier transform processes are performed in different cycles using the same n ₁ long Fourier transform means on the m pieces of data distributed in the same cycle by the data distribution means. A Fourier transform device characterized by the above.

Images