KR20130047202A - High-speed low-complexity radix-2 to the fifth fast fourier transform apparatus and method - Google Patents

Abstract

Radix 2 quadratic fast Fourier transform apparatus and method are disclosed.
The fast Fourier transform apparatus includes: a plurality of fast Fourier transform units configured to perform fast Fourier transform by calculating single-path delay feedback (SDF) on input data received through a parallel data path; A first butterfly operation unit performing a butterfly operation on the fast Fourier transformed input data; And a second butterfly calculator configured to butterfly arithmetic operations of the first butterfly calculator.

Description

HIGH SPEED LOW-COMPLEXITY RADIX-2 TO THE FIFTH FAST FOURIER TRANSFORM APPARATUS AND METHOD}

The present invention relates to an apparatus and method for a quadratic fast Fourier transform of Radix 2. More particularly, the present invention relates to a pipeline fast Fourier transform device and method for increasing data throughput by performing a parallel operation on a part of a higher stage in the fast Fourier transform method. will be.

Orthogonal Frequency Division Multiplexing (OFDM) divides a single carrier into several orthogonal subcarriers in a communication system, loads, modulates, and transmits a data stream, thereby providing a single carrier communication system without having to parallel structure the communication system. This is a high speed data transfer that is close to parallel structure.

In this case, orthogonal frequency division multiplexing is implemented using a Discrete Fourier Transform (DFT) scheme. However, when the discrete Fourier transform is implemented in hardware, the fast Fourier transform is used because the complex add, subtract, and multiply operations increase exponentially with the increase in the number of points, the input length.

Korean Patent Publication No. 10-2008-0062003 (published Jul. 03, 2008) discloses a fast Fourier transform apparatus using a pipeline structure. The fast Fourier transform apparatus using the conventional pipeline structure uses the Radix-2 ² algorithm, but the Radix-2 ² algorithm requires a multiplier when performing the fast Fourier transform operation with a high input length. There was a problem of this being high.

Therefore, there is a need for an apparatus and method that can be implemented in a lower area than a conventional fast Fourier transform processor and can be processed at a high speed.

The present invention provides a pipeline fast Fourier transform apparatus and method that can increase the data throughput by performing parallel operations on some of the higher stages.

In addition, the present invention is a Canonical Signed Digit (CSD) method using a common sub-expression sharing (CSS) technique having a simple structure for most of the complex booth multiplier having a complex structure By replacing with a plural constant multiplier, there is provided a fast Fourier transform device and method with low complexity.

A fast Fourier transform device according to an embodiment of the present invention includes a plurality of fast Fourier transform unit for performing a fast Fourier transform by calculating a single-path delay feedback (SDF) input data received through a parallel data path; A first butterfly operation unit performing a butterfly operation on the fast Fourier transformed input data; And a second butterfly calculator configured to butterfly arithmetic operations of the first butterfly calculator.

A fast Fourier transform unit of the fast Fourier transform device according to an embodiment of the present invention, the first step of performing a butterfly operation through a second butterfly calculation unit connected to the 32-FIFO memory; A second step of performing a butterfly operation on the operation result of the first step through a first butterfly operation unit connected to a 16-FIFO memory; A third step of performing a butterfly operation on the operation result of the second step through a first butterfly operation unit connected to an 8-FIFO memory; A fourth step of performing a butterfly operation on the operation result of the third step through a second butterfly operation unit connected to a 4-FIFO memory; A fifth step of performing a butterfly operation on the operation result of the fourth step through a first butterfly operation unit connected to a 2-FIFO memory; And a sixth step of performing a butterfly operation on the operation result of the fifth step through a second butterfly operation unit connected to the 1-FIFO memory to perform a single-path delay feedback (SDF) operation. have.

The fast Fourier transform unit of the fast Fourier transform device according to an embodiment of the present invention may perform a rotation factor multiplication operation on the calculation result of the second step and the operation result of the third step by using a complex constant multiplier.

The complex constant multiplier of the fast Fourier transform apparatus according to an embodiment of the present invention may be a multiple constant multiplier of a canonical code number (CSD) method using a common subexpression sharing (CSS) technique.

A fast Fourier transform method according to an embodiment of the present invention comprises the steps of performing a fast Fourier transform in parallel by calculating a single-path delay feedback (SDF) input data received through the parallel data path; Performing a butterfly operation on the fast Fourier transformed input data using the first butterfly calculator; And performing a butterfly operation on a calculation result of the first butterfly calculator using a second butterfly calculator.

A fast Fourier transform apparatus according to an embodiment of the present invention is a fast Fourier transform according to a modified Radix-2 ⁵ algorithm that reconstructs an equation by applying a common factorization algorithm to a Radix-2 ⁵ algorithm derived by 6-dimensional index decomposition. Can be performed.

A fast Fourier transform apparatus according to an embodiment of the present invention is a fast Fourier transform according to a modified Radix-2 ⁵ algorithm using a parallel structure and a pipeline method based on a plurality of Radix-2 ⁵ algorithms derived by 6-dimensional index decomposition. You can perform the conversion.

According to an embodiment of the present invention, the data throughput may be increased by performing a parallel operation on a part of an upper stage in a pipeline fast Fourier transform apparatus having a plurality of parallel data paths.

In addition, according to an embodiment of the present invention, a majority of the complex booth multiplier having a complicated structure is a plural constant multiplier of a canonical code number (CSD) method using a common subexpression sharing (CSS) technique having a simple structure. By replacing, the complexity of the fast Fourier transform device can be reduced.

1 is a schematic signal flow diagram of a fast Fourier transform method using a method 1 of deploying a 64-point Radix-2 ⁵ algorithm.
FIG. 2 is a schematic signal flow diagram of a fast Fourier transform method using a deployment method 2 of a 64-point Radix-2 ⁵ algorithm.
3 is a block diagram illustrating a fast Fourier transform device according to an embodiment of the present invention.
4 is a block diagram illustrating a fast Fourier transform unit according to an embodiment of the present invention.
5 is a diagram illustrating a configuration of a first butterfly calculator included in a fast Fourier transform unit according to an embodiment of the present invention.
6 is a diagram illustrating a configuration of a second butterfly calculator included in a fast Fourier transform unit according to an exemplary embodiment of the present invention.
7 is a diagram illustrating a configuration of a CSD constant multiplier according to an embodiment of the present invention.
8 shows for rotation factor W ₃₂ A diagram illustrating a configuration of a complex constant multiplier according to an embodiment of the present invention.
9 is a diagram illustrating a configuration of a first butterfly calculation unit included in a post-processing unit according to an embodiment of the present invention.
10 is a diagram illustrating a configuration of a second butterfly calculating unit included in a post-processing unit according to an embodiment of the present invention.
11 is a flowchart illustrating a fast Fourier transform method according to an embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. The fast Fourier transform method according to an embodiment of the present invention may be performed by a fast Fourier transform device.

The present invention is a fast Fourier transform method using the Radix-2 ⁵ algorithm.

The 64-point Radix-2 ⁵ algorithm in the fast Fourier transform method may use a signal flow diagram as shown in FIG. 1 or 2 according to a method of applying a common factorization algorithm. At this time, the Dorado signal flow according to a first signal stream Dora, and deployment of the Radix-2 algorithm of the Fig. ⁵ 2 2 64-point method according to the development method 1, the Radix-2 algorithm ⁵ of 64 points.

In this case, the discrete Fourier transform of length N may be defined as in Equation 1.

In this case, W _N may be a rotation factor, n may be a time index, and k may be a frequency index.

In this case, Equation 2 may be generated by applying a six-dimensional linear index map to a Discrete Fourier Transform, such as Equation 1, to derive the Radix-2 ⁵ algorithm.

Next, when the common factor algorithm (CFA) is applied to Equation 2, Equation 3 may be generated.

At this time, if the rotation factor of Equation 3 is arranged, Equation 4 may be generated.

In this case, Equation 4 may represent the order and structure of the butterfly operation and the rotation factor multiplication operation of each stage according to the deployment method 1 of the Radix-2 ⁵ algorithm of 64 points as shown in FIG. 1.

In this case, the rotation factor multiplication 110 of the first stage and the rotation factor multiplication 120 of the fourth stage may be constituted by simple multiplication that does not require a multiplier. In addition, the number of rotation factors of the W ₈ rotation factor complex multiplication 130 may be one, and the number of rotation factors of the W ₃₂ rotation factor complex multiplication 140 may be seven. In this case, the W ₈ rotation factor complex multiplication 130 and the W ₃₂ rotation factor complex multiplication 140 may be performed using a CSD special constant multiplier. At this time, 64P BU2 may be a 64 point second butterfly operation, and 32P BU1 may be a 32 point first butterfly operation. In addition, 16P BU1 may be a 16 point first butterfly operation, and 8P BU2 may be an 8 point second butterfly operation.

In addition, when the common factorization algorithm applied to Equations 1 and 2 is applied in a manner different from that of Equation 3, Equation 5 may be generated.

At this time, by arranging the rotation factors of Equation 5, Equation 6 may be generated.

In this case, Equation 6 may represent the order and structure of the butterfly operation and the rotation factor multiplication operation of each stage according to the deployment method 2 of the Radix-2 ⁵ algorithm of 64 points as shown in FIG. 2.

In this case, the rotation factor multiplication 210 of the first stage and the rotation factor multiplication 220 of the third stage may be constituted by simple multiplication that does not require a multiplier. In addition, the two can be computed by forming the number of twiddle factors three, CSD W ₁₆ rotation factor complex multiplication 230 of the second stage by using a special constant multiplier in a W ₁₆ rotation factor complex multiplication (230) of the second stage have. If the input length of the fast Fourier transform is less than 512, the rotation factor multiplication 240 of the fifth stage may be configured with a maximum of seven rotation factors. Can be calculated.

The Radix-2 ⁵ algorithm according to the present invention operates from the first stage to the upper fifth stage by applying the expansion method 1 according to Equation 3 and Equation 4, and from the sixth stage to the last stage. Up to 2 may be calculated by applying the expansion method 2 according to Equations 5 and 6 below.

In addition, the Radix-2 ⁵ algorithm according to the present invention can reduce the design cost and power consumption of hardware by calculating a multiple constant multiplication using a complex constant multiplier using CSS and CSD instead of the programmable complex multiplier. In this case, the complex constant multiplier according to the present invention can simplify the calculation process to minimize the number of non-zero bits through the CSD method and to share the common operation unit through the CSS method.

3 is a block diagram illustrating a fast Fourier transform device according to an embodiment of the present invention.

The fast Fourier transform device according to an embodiment of the present invention is a pipelined Fast Fourier transform device having eight parallel data paths as shown in FIG. 3, and includes a fast Fourier transform unit 310 and a post processor 320. It may include.

The fast Fourier transform unit 310 may perform fast Fourier transform by calculating 64-point single-path delay feedback (SDF) on input data received through eight parallel data paths. In this case, the fast Fourier transform unit 310 may independently perform parallel operation on input data input through the parallel data path using the first fast Fourier transform unit 311 to the eighth fast Fourier transform unit 312.

In addition, the fast Fourier transform unit 310 may perform upper six stages corresponding to the first to sixth steps of the fast Fourier transform method according to an embodiment of the present invention.

The detailed configuration of the fast Fourier transform unit 310 and the performing stages will be described in detail with reference to FIG. 4.

The post processor 320 performs the lower three stages by the first butterfly operator, the second butterfly operator, and the complex constant multiplier 322 for multiplying the rotation factor of W ₁₆ to perform the first fast Fourier transform units 311 to 3rd. 8 The output of the fast Fourier transform unit 312 can be post-processed.

In this case, the post-processing unit 320 may output the outputs of the first fast Fourier transform units 311 to 8th fast Fourier transform unit 312 by using four first butterfly calculators 321 in the seventh stage. Can fly operation. In this case, since the rotation factor multiplication operation of the seventh stage requires three types of rotation factors, the post-processing unit 320 uses the complex butterfly multiplier 322 for multiplying the rotation factor of W ₁₆ to generate the first butterfly operator ( A rotation factor multiplication operation may be performed on the output of 321. In this case, the complex constant multiplier 322 for multiplying the rotation factor of W ₁₆ may be a plural constant multiplier of Canonical Signed Digit (CSD) using a common sub-expression sharing (CSS) technique. have.

In addition, the post processor 320 may perform a four point butterfly operation on the result of the seventh stage using the eighth stage and four second butterfly calculators 323.

The post-processing unit 320 may output a result for 64 clocks by performing a two-point butterfly operation on the eighth stage result using the four first butterfly calculators 324 in the ninth stage.

Detailed configurations and operations of the first butterfly calculating unit and the second butterfly calculating unit of the post-processing unit 320 will be described in detail with reference to FIGS. 9 and 10. In addition, the configuration of the complex constant multiplier 322 will be described in detail with reference to FIG.

4 is a block diagram illustrating a fast Fourier transform unit according to an embodiment of the present invention.

The fast Fourier transform unit 310 according to an embodiment of the present invention includes six butterfly calculators 410, 420, 430, 440, 450, 460 and W for performing six stages as shown in FIG. 4. Complex constant multiplier 422 for multiplying rotation factors of ₈ , complex constant multiplier 432 for multiplying rotation factors of W ₃₂ , and FIFO memories 411, 421, 431, 441, 451, corresponding to respective butterfly operations. 461). In this case, the complex constant multiplier 422 for multiplying the rotation factor of W ₈ and the complex constant multiplier 432 for multiplying the rotation factor of W ₃₂ are provided by a canonical code number (CSD) method using a common subexpression sharing (CSS) technique. It may be a multiple constant multiplier. In this case, the detailed configuration and operation of the first butterfly calculation unit and the second butterfly calculation unit of the fast Fourier transform unit 310 will be described in detail with reference to FIGS. 5 and 6.

The fast Fourier transform unit 310 according to an embodiment of the present invention may receive one complex value per clock from one of eight pipelines as input data.

In this case, the fast Fourier transform unit 310 may perform a first stage of performing 64-point butterfly operation on the input data through the second butterfly operator 410 connected to the 32-FIFO memory 411.

In detail, the second butterfly calculator 410 may store input data in the 32-FIFO memory 411 from one clock to 32 clocks. Next, the second butterfly operator 410 may perform a butterfly operation with values stored in the 32-FIFO memory 411 for input data of 32 clocks to 64 clocks. In this case, the result of performing the complex addition among the butterfly operation results may be output for the second stage operation. In addition, the result of performing the complex subtraction among the butterfly operation results may be stored in the 32-FIFO memory 411. In this case, the complex subtraction result of the butterfly operation according to the characteristics of the 32-FIFO memory 411 may be output after 32 clocks have elapsed.

Next, the fast Fourier transform unit 310 may perform a second stage of performing 32 point butterfly operation on the input data through the first butterfly operator 420 connected to the 16-FIFO memory 421. In this case, the fast Fourier transform unit 310 may perform a third stage of performing 16 point butterfly operation on the input data through the first butterfly operation unit 430 connected to the 8-FIFO memory 431.

Next, the fast Fourier transform unit 310 may perform a fourth stage of 8-point butterfly operation on the input data through the second butterfly operator 440 connected to the 4-FIFO memory 441. In this case, the fast Fourier transform unit 310 may perform a fifth stage of performing four point butterfly operation on the input data through the first butterfly operator 450 connected to the 2-FIFO memory 451.

Finally, the fast Fourier transform unit 310 may perform a sixth stage of performing two point butterfly operation on the input data through the second butterfly operator 460 connected to the 1-FIFO memory 461.

In this case, the second butterfly calculator is configured to add a simple multiplication operation that multiplies a complex number (-j) by the same operation result as the first butterfly calculator. Thus, the second stage, the third stage, and the fifth stage without using the second butterfly operator may require a multiplier for rotation factor multiplication.

In this case, the second stage and the third stage may have fewer kinds of rotation factors for multiplication. Therefore, the fast Fourier transform unit 310 uses a complex constant multiplier 422 for multiplication of the rotation factor of W ₈ . A rotation factor multiplication operation may be performed on the result of the third stage, and a rotation factor multiplication operation may be performed on the result of operation of the third stage by using a complex constant multiplier 432 for multiplying the rotation factor of W ₃₂ .

In addition, the fast Fourier transform unit 310 may use the rotation factor complex booth multiplier 452 of W ₃₂ to perform rotation factor multiplication of the fifth stage. In this case, the complex booth multiplier 452 may perform a rotation factor multiplication operation using the rotation factor values pre-stored in the ROM memory.

The fast Fourier transform 310 according to the present invention computes a 64-point fast Fourier transform with the same control signal by calculating up to the sixth stage by using a single path delay feedback structure as shown in FIG. 4 for each parallel data path. can do.

5 is a diagram illustrating a configuration of a first butterfly calculator included in a fast Fourier transform unit according to an embodiment of the present invention.

The first butterfly calculators 420, 430, and 450 included in the fast Fourier transform unit 310 according to the present invention perform two calculation processes based on the N / 2th clock when performing the N point butterfly operation. Can be done.

First, the first butterfly operation units 420, 430, and 450 sequentially store complex values input from the first to N / 2 th clocks in the N / 2-FIFO memory 510, and N / 2-FIFO memories. Complex values previously stored at 510 may be sequentially output to the next stage.

Next, the first butterfly calculator 420, 430, 450 performs a butterfly operation on the complex value input from the N / 2 th clock to the N th clock and the complex value output from the N / 2-FIFO memory 510. can do. In this case, the first butterfly calculators 420, 430, and 450 may sequentially input complex subtraction results to the N / 2-FIFO memory 510 among the butterfly calculation results (520). In this case, the complex subtraction result of the butterfly operation according to the characteristics of the N / 2-FIFO memory 510 output in the input order may be output after the N / 2 clock has elapsed. For example, if N is 32, as a result of performing complex subtraction during the butterfly operation on 16 clocks, the value stored in the 16-FIFO memory may be output to 33 clocks, i.e., a new one clock after 16 clocks have elapsed. have.

In operation 530, the first butterfly calculator 420, 430, or 450 may output a complex addition result from the butterfly calculation result to the next stage.

That is, the first butterfly operation unit performing the N point butterfly operation according to the present invention repeats the above process, and outputs the result of performing the complex subtraction among the butterfly operation results from the first to N / 2th clocks. From the N / 2 th clock to the N th clock, the complex addition result of the butterfly operation result may be output.

6 is a diagram illustrating a configuration of a second butterfly calculator included in a fast Fourier transform unit according to an exemplary embodiment of the present invention.

The second butterfly operators 410, 440, and 460 included in the fast Fourier transform unit 310 according to the present invention add a simple multiplication operation that multiplies a complex number (-j) to the same operation result as the first butterfly operator. Configuration.

Accordingly, when the second butterfly operation units 410, 440, and 460 according to the present invention perform an N point butterfly operation, the second butterfly operation units 410, 440, and 460 generate the N / 2th clock in the same manner as the first butterfly operation units 420, 430, and 450. As a standard, two operations can be performed.

In this case, when the clocks for receiving the input data are 1 to N / 2, the second butterfly calculators 410, 440, and 460 input complex values from the first to N / 2th clocks as in the first butterfly calculator. Are sequentially stored in the N / 2-FIFO memory 610, and complex values previously stored in the N / 2-FIFO memory 610 may be sequentially output to the next stage.

In addition, when the clocks for receiving the input data are N / 2 to N, the second butterfly calculators 410, 440, and 460 input complex values and N / 2-FIFOs that are input from the N / 2 th clock to the N th clock. The butterfly operation may be performed on the complex value output from the memory 610. In this case, the second butterfly calculators 410, 440, and 460 may sequentially input complex subtraction results to the N / 2-FIFO memory 610 among the butterfly calculation results (620).

In operation 630, the second butterfly calculator 410, 440, 460 may output a complex addition result among the butterfly calculation results to the next stage. In this case, the second butterfly operation unit 410, 440, 460 may perform a simple multiplication operation by multiplying a complex number (-j) by a complex addition of the butterfly operation results using the mulberryplexer circuit 640. Can be.

7 is a diagram illustrating a configuration of a CSD constant multiplier according to an embodiment of the present invention.

In the fast Fourier transform apparatus according to an embodiment of the present invention, a canonical code number (CSD) scheme using a common subexpression sharing (CSS) technique for most of the complex multipliers included in the fast Fourier transform apparatus in order to reduce hardware area and power consumption. Can be used as a multiple constant multiplier of.

The rotation factor required for complex multiplication in the fast Fourier transform device may be represented by a decimal number, a 10-bit binary number, and a 10-bit CSD representation as shown in Table 1.

/8), cos(

/8), sin(

/4), sin(

/16), sin(3

/16), sin(5

/16), sin(7

/16)이며 이를 CSD 표현으로 나타내면 최대 5개의 0이 아닌 비트로 표현될 수 있다.In this case, the complex multiplication factor corresponding to the rotation factor is sin (

/ 8), cos (

/ 8), sin (

/ 4), sin (

/ 16), sin (3

/ 16), sin (5

/ 16), sin (7

/ 16), which can be represented by up to five nonzero bits.

In this case, the CSD constant multiplier generates a partial product by right shifting an input value according to a non-zero bit position among multiplication coefficients, and adds all the generated partial products to obtain a result.

In detail, the CSD constant multiplier may include a rotation factor calculator 720 that calculates bits for each rotation factor by the common operator 710 that calculates common bits of the rotation factors W _{32 ,} W _{16 ,} and W ₈ .

In this case, the rotation factors W _{32 ,} W _{16 ,} and W ₈ may be calculated by the W ₈ rotation factor multiplication operation unit 721, the W ₁₆ rotation factor multiplication operation unit 722, and the W ₃₂ rotation factor multiplication operation unit 723.

At this time, the rotation factor W ₃₂ is W ₁₆ Wow Contains all the multiplication factors of W ₈ , and the rotation factor W ₁₆ is Since it includes a multiplication coefficient of W ₈ , the rotation factor calculating unit 720 generates a configuration for calculating the rotation factor W ₃₂ , and the complex constant multiplier according to an embodiment of the present invention uses the multiplication coefficient required in the calculation result, One CSD constant multiplier can compute all rotation factors W _{32 ,} W _{16 ,} and W ₈ .

In addition, W complex constant multiplier (432) for rotation factor multiplication _32, W ₃₂ twiddle factors using the multiplication operation unit 723, and the complex constant multiplier 322 for rotation factor multiplication of the W ₁₆ is W ₁₆ rotation factor multiplication using only the operation unit 722, and the complex constant multiplier 422 for multiplying the rotation factor W ₈ may be simplified in structure by only using the rotation factor W ₈ multiplication operation unit (721).

That is, the CSD constant multiplier according to an embodiment of the present invention may design a binary multiplier for reducing hardware area by expressing a multiplication coefficient expressed in two's complement form by the CSD method. At this time, the CSD method must have a value of one of the elements of {-1, 0, 1}. It cannot consist of more than two consecutive nonzero bits.

8 shows for rotation factor W ₃₂ A diagram illustrating a configuration of a complex constant multiplier according to an embodiment of the present invention.

Rotation factor for W ₃₂ The complex constant multiplier according to an embodiment of the present invention may include two CSD constant multipliers, a multiplexer, and two adders, as shown in FIG. 8.

In this case, the complex constant multiplier according to an embodiment of the present invention may input real and imaginary numbers to two CSD constant multipliers to output a multiplication result for each coefficient of the input data.

In this case, the complex constant multiplier according to an embodiment of the present invention may calculate rotation factor multiplication according to the schedule of Table 2.

Table 2 defines the rotation factor multiplication operation mode for each of the 64 clocks used in the rotation factor W ₃₂ in chronological order, and 15 rotation factor multiplication operation modes may be defined.

In addition, the complex constant multiplier according to an embodiment of the present invention can generate the control signal of the multiplexer as shown in Table 3 using Table 2.

As shown in Table 3, the complex constant multiplier according to an embodiment of the present invention can control the operation of the multiplier by the four multiplexer control signals. At this time, the rotation factor W ₈ And a complex constant multiplier for W ₁₆ may also be simply configured through a control signal as in the case of the rotation factor W ₃₂ .

In this case, the complex constant multiplier 322 for the rotation factor multiplication of W ₁₆ replaces the constant multiplier W ₃₂ with the W ₁₆ rotation factor multiplication operation 722, and the output of the W ₁₆ rotation factor multiplication operation 722 is 3. As a result, mux-sel2's multiplexer can be replaced with 3-to-1 MUX.

Further, the complex constant multiplier 422 for multiplying the rotation factor of W ₈ replaces the constant multiplier W ₃₂ by the W ₈ rotation factor multiplication operation 721, and the output of the W ₈ rotation factor multiplication operation 721 is 1. The mux-sel2 multiplexer can be omitted.

9 is a diagram illustrating a configuration of a first butterfly calculation unit included in a post-processing unit according to an embodiment of the present invention.

The first butterfly calculators 321 and 324 included in the post processor 320 according to the present invention may perform a butterfly operation on the received complex value. At this time, the first butterfly calculating unit 321 multiplies the rotation result of W ₁₆ by using a different output terminal from the result of performing the complex subtraction (910) and the result of the complex addition (920) among the butterfly calculation results. For output to the complex constant multiplier 322 or the second butterfly operator 323 for.

In addition, the first butterfly calculator 324 may output a complex subtraction result 910 and a complex addition result 920 among the butterfly operation results for 64 clocks using different output terminals. have.

10 is a diagram illustrating a configuration of a second butterfly calculating unit included in a post-processing unit according to an embodiment of the present invention.

The second butterfly operator 323 included in the post processor 320 according to the present invention is a complex value input from the first butterfly operator 321 or the complex constant multiplier 322 for multiplying the rotation factor of W ₁₆ . Can be computed as a butterfly. At this time, the second butterfly calculator 323 multiplies the complex number (-j) by the result of performing the complex subtraction (1010) and the result of the complex addition (1020) of the butterfly calculation results (1030). ) May be output to the first butterfly calculator 324.

11 is a flowchart illustrating a fast Fourier transform method according to an embodiment of the present invention.

In operation S1110, the eight second butterfly calculators 410 may perform 64-point butterfly operations in parallel on the parallel data paths using the 32-FIFO memory 411.

In operation S1120, the eight first butterfly operation units 420 may perform a 32-point butterfly operation on the operation result of operation S1110 using the 16-FIFO memory 421. In this case, the complex constant multiplier 422 for multiplying the rotation factor of W ₈ may multiply a result of the calculation of the first butterfly operator 420 to the first butterfly operator 430.

In operation S1130, the eight first butterfly operations 430 may perform a 16-point butterfly operation on the operation result of operation S1130 using the 8-FIFO memory 431. In this case, the complex constant multiplier 432 for multiplying the rotation factor of W ₃₂ may perform a rotation factor multiplication operation on the result of the operation of the first butterfly operator 430 to provide the second butterfly operator 440.

In operation S1140, the eight second butterfly operations 440 may perform an eight-point butterfly operation on the operation result of operation S1130 using the 4-FIFO memory 441.

In operation S1150, the eight first butterfly operators 450 may perform a four-point butterfly operation on the operation result of operation S1140 using the 2-FIFO memory 451. In this case, the rotation factor complex booth 452 of W ₅₁₂ may multiply a result of the calculation of the first butterfly operator 450 and provide the result to the first butterfly operator 460.

In operation S1160, the eight second butterfly operation units 460 may perform a two-point butterfly operation on the operation result of operation S1150 using the 1-FIFO memory 461.

In this case, steps S1110 to S1160 may be a single-path delay feedback (SDF) operation that operates independently according to eight parallel data paths.

In operation S1170, the first butterfly operator 321 may perform an eight-point butterfly operation on the operation results of operation S1160. In this case, the complex constant multiplier 322 may perform a rotation factor multiplication operation on the calculation result of the first butterfly operator 321 and provide it to the second butterfly operator 323.

In operation S1180, the second butterfly operation unit 323 may perform a four-point butterfly operation on the operation result of operation S1170.

In operation S1190, the first butterfly operator 324 may output a fast Fourier transform result for 64 clocks by performing a two-point butterfly operation on the operation result of operation S1180.

The present invention can increase data throughput by performing parallel operations on a part of higher stages in a pipeline fast Fourier transform apparatus having a plurality of parallel data paths. In addition, the complexity of the fast Fourier transform apparatus is replaced by replacing a majority of the complex booth multiplier with a complex structure with a plural constant multiplier of the canonical code number (CSD) method using a common subexpression sharing (CSS) technique with a simple structure. Can be lowered.

As described above, the present invention has been described by way of limited embodiments and drawings, but the present invention is not limited to the above embodiments, and those skilled in the art to which the present invention pertains various modifications and variations from such descriptions. This is possible.

Therefore, the scope of the present invention should not be limited to the described embodiments, but should be determined by the equivalents of the claims, as well as the claims.

310: fast Fourier transform unit
321: first butterfly calculation unit
323: second butterfly operation unit

Claims (14)

In a pipeline fast Fourier transform apparatus having a plurality of parallel data paths,
A plurality of fast Fourier transform units configured to perform fast Fourier transform by calculating single-path delay feedback (SDF) on the input data received through the parallel data path;
A first butterfly operation unit performing a butterfly operation on the fast Fourier transformed input data; And
A second butterfly calculator configured to butterfly arithmetic results of the first butterfly calculator
Fast Fourier transform device comprising a. The method of claim 1,
The fast Fourier transform unit,
A first step of performing a butterfly operation through a second butterfly operator connected to the 32-FIFO memory;
A second step of performing a butterfly operation on the operation result of the first step through a first butterfly operation unit connected to a 16-FIFO memory;
A third step of performing a butterfly operation on the operation result of the second step through a first butterfly operation unit connected to an 8-FIFO memory;
A fourth step of performing a butterfly operation on the operation result of the third step through a second butterfly operation unit connected to a 4-FIFO memory;
A fifth step of performing a butterfly operation on the operation result of the fourth step through a first butterfly operation unit connected to a 2-FIFO memory; And
A sixth step of performing a butterfly operation on the operation result of the fifth step through a first butterfly calculator connected to a 1-FIFO memory;
The fast Fourier transform apparatus for performing a single-path delay feedback (SDF) operation comprising a. The method of claim 2,
The fast Fourier transform unit,
And a rotation factor multiplication operation of the operation result of the second step and the operation result of the third step by using a complex constant multiplier. The method of claim 3,
The complex constant multiplier,
2. A fast Fourier transform apparatus, comprising: a canonical signed digit (CSD) multiple constant multiplier using a common sub-expression sharing (CSS) technique. The method of claim 1,
The fast Fourier transform device,
A Fast Fourier Transform apparatus, which operates according to a modified Radix-2 ⁵ algorithm which reconstructs an equation by applying a common factorization algorithm to a Radix-2 ⁵ algorithm derived by 6-dimensional index decomposition. The method of claim 1,
The fast Fourier transform device,
A fast Fourier transform apparatus, which operates according to a modified Radix-2 ⁵ algorithm using a parallel structure and a pipeline method based on a plurality of Radix-2 ⁵ algorithms derived by 6-dimensional index decomposition. A fast Fourier transform method performed by a pipeline fast Fourier transform apparatus having a plurality of parallel data paths,
Performing fast Fourier transform on the input data received through the parallel data path by performing a single-path delay feedback (SDF) operation in parallel;
Performing a butterfly operation on the fast Fourier transformed input data using the first butterfly calculator; And
Performing a butterfly operation on a calculation result of the first butterfly calculator using a second butterfly calculator
Fast Fourier transform method comprising a. The method of claim 7, wherein
The fast Fourier transform
A first step of performing a butterfly operation on the input data through a second butterfly operator connected to the 32-FIFO memory;
A second step of performing a butterfly operation on the operation result of the first step through a first butterfly operation unit connected to a 16-FIFO memory;
A third step of performing a butterfly operation on the operation result of the second step through a first butterfly operation unit connected to an 8-FIFO memory;
A fourth step of performing a butterfly operation on the operation result of the third step through a second butterfly operation unit connected to a 4-FIFO memory;
A fifth step of performing a butterfly operation on the operation result of the fourth step through a first butterfly operation unit connected to a 2-FIFO memory; And
A sixth step of performing a butterfly operation on the operation result of the fifth step through a first butterfly calculator connected to a 1-FIFO memory;
Fast Fourier transform method comprising a. 9. The method of claim 8,
In the third step,
And performing a butterfly operation on the result of the rotation factor multiplication operation of the operation result of the second step by using a complex constant multiplier. 9. The method of claim 8,
In the fourth step,
And performing a butterfly operation on the result of the rotation factor multiplication operation using the complex constant multiplier. 10. The method of claim 9,
The complex constant multiplier,
A fast Fourier transform method comprising a canonical signed digit (CSD) multi-constant multiplier using a common sub-expression sharing (CSS) technique. The method of claim 7, wherein
Performing a rotation factor multiplication operation on the fast Fourier transformed input data and providing the second butterfly operation unit
Fast Fourier transform method comprising more. A Fast Fourier Transform apparatus that performs Fast Fourier Transform according to the modified Radix-2 ⁵ Algorithm by applying a common factorization algorithm to Radix-2 ⁵ algorithm derived by 6-dimensional index decomposition. A fast Fourier transform apparatus for performing fast Fourier transform according to a modified Radix-2 ⁵ algorithm using a parallel structure and a pipeline method based on a plurality of Radix-2 ⁵ algorithms derived by 6-dimensional index decomposition.

Images