KR20100138639A - Method and apparatus for tweed factor index generation in fast Fourier transform system - Google Patents

Abstract

The present invention relates to a method and apparatus for generating a tween factor index in a fast Fourier transform system, comprising: a stage number counter for determining and outputting a number (s) of a stage into which data is input, and sequentially counting an index of the input data And a data index counter for outputting the counted data index in r-decimal number, a selector for selecting and outputting a digit corresponding to r ^s digits as a first factor among the digits constituting the data index in r-number, A shifter for selecting a digit higher than the r ^s digit among the digits constituting the data index, a bit inverter for bit inverting the digit selected by the shifter and outputting it as a second factor, scaling according to the determined stage number A scaler for generating a third factor for and the first factor And a multiplier for multiplying the second factor and the third factor to generate the tween factor index.

Description

METHODE AND APPARATUS FOR GENERATING TWIDDLE FACTOR INDEX IN FAST FOURIER TRANSFORM SYSTEM}

The present invention relates to a method and apparatus for generating a tween factor index in a fast Fourier transform system. More specifically, the present invention relates to a method and apparatus for generating a tween factor index required for performing a Fast Fourier Transform of an n-square method of Radix-r on a data string input in a bit reverse order.

Orthogonal Frequency Division Multiplexing (OFDM) technology is used in wireless communication systems such as Institute of Electrical and Electronics Engineers (IEEE) 802.16, IEEE 802.111, and digital broadcasting such as digital multimedia broadcasting (DMB). . At this time, one of the most important components of the OFDM is a FAST FOURIER TRANSFORM (FFT) processor. The FFT is an algorithm for computing the Discrete Fourier Transform (DFT) at high speed, and the equation for the DFT is defined as in Equation 1 below.

[Equation 1]

Where X (K) is the result of the Fourier transform, x (n) is the input data string of the FFT, W _N is the Twiddle Factor, and all of these values have a complex form. Here, the tweet factor is a periodic function used for converting a time signal into a frequency signal.

In implementing the FFT, the Radix-4 method, which is one of the widely used methods, is superior in terms of multiplication efficiency to the Radix-2 method. On the other hand, the Radix-2 method has the advantage that the butterfly structure is easier to use because it is simpler than the Radix-4. Here, Radix-4 method and system which combines the advantages of only Radix-2 scheme (the same ^{Radix-2. 2,} below) the square of the Radix-2 by 'Shousheng He' DIF FFT is designed.

However, the quadratic DIF FFT of Radix 2 receives a data sequence in a natural order, performs an FFT operation, and outputs the data sequence in an inverted order. On the other hand, modern modem modem receivers use (I) FFT not only for demodulation of received OFDM signals but also for equalizers and channel estimation. In this case, in implementing the (I) FFT in the FFT for demodulation and the equalizer to be performed later, when the conventional Radix 2 power DIF FFT algorithm is applied in the same way, the data outputted in the reversed order will be In order for the (I) FFT operation to be performed, the process must be rearranged in order. This realignment operation requires a memory corresponding to the FFT size, and there is a problem that a time delay occurs for symbols.

The present invention has been made to solve the above problems, and an object of the present invention is to propose a method for generating a tween factor required for performing a Fast Fourier Transform of a Radix-r method on a data sequence inputted in an inverted order.

In order to solve the above problems, a tweed factor index generating device of the Radix-r n-type fast Fourier transform processor according to the present invention includes a stage number counter for determining and outputting a number s of a stage into which data is input; A first index corresponding to r ^s digits of a data index counter that sequentially counts the indexes of the input data and outputs the counted data indexes in r numbers, and digits constituting the r data indexes; A selector for selecting and outputting a digit, a shifter for selecting a digit corresponding to a higher digit than the r ^s digits among the digits constituting the data index of the r-number, and outputting the bit selected by the shifter as a second factor. A bit inverter, generating a third factor for scaling according to the determined stage number Multiplied by a scalar, and the third factor and the second factor from the first factor to each other characterized in that it comprises a multiplier for generating the twiddle factor index.

In addition, in order to solve the above problems, a method of generating a tween factor index of the n-th order fast Fourier transform processor of the Radix-r of the present invention includes determining and outputting a number s of a stage into which data is input; Sequentially counting the indices of the input data and outputting the counted data indexes in r numbers; selecting a digit corresponding to r ^s digits among the digits constituting the r data index as the first factor Selecting a digit corresponding to a higher digit than the r ^s digit among the digits constituting the data index of the r base, outputting the selected digit by the bit shifter as a second factor, Generating a third factor for scaling according to the determined stage number and the first factor and the second factor And multiplying a factor by the third factor to generate the tweet factor index.

The present invention proposes a method of generating a tween factor required for performing a Fast Fourier Transform of the n-th power method of Radix-r on a data sequence inputted in bit inverted order. Accordingly, in configuring an equalizer in an OFDM modem modem receiver, after the FFT for demodulation, (I) FFT for channel equalization may be performed without a separate reordering process. Therefore, the memory and time increase required by the reordering process can be prevented.

The gist of the present invention described below will be described as an example of Radix-2 quadratic fast Fourier transform, but may be applied when performing Radix-r fast Fourier transform of n-square.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. Note that, in the drawings, the same components are denoted by the same reference symbols as possible. Further, the detailed description of well-known functions and constructions that may obscure the gist of the present invention will be omitted.

FIG. 1 is a diagram illustrating a signal flow graph (SFG) of a Radix-2 quadratic DIF FFT for N = 64.

The Radix-2 quadratic DIF FFT combines only the advantages of the Radix-4 and Radix-2 schemes, and includes various pipeline schemes such as Multi-Path Delay Commutator (MDC) and Single-path Delay Feedback (SDF). Can be applied to the FFT structure.

The SDF FFT processor implemented using the Radix-2 quadratic DIF FFT algorithm shown in FIG. 1 is shown in FIG. 2. The FFT processor shown in FIG. 2 is widely used as an optimal FFT implementation method because of maintaining the simple butterfly structure of Radix-2 and the number of multiplications of Radix-4, because of the efficiency of functions and the ease of implementation.

As shown in FIG. 2, the FFT processor includes a plurality of stages, and the tween factor 'W (n)' is multiplied by the output data string of each stage. The input data string x (n) having passed through all stages is output as X (K).

And the detailed structure of any stage shown in FIG. 2 is shown in FIG. As shown in FIG. 3, any stage of the Radix-2 quadratic DIF FFT processor may include a first buffer 310, a second buffer 320, a first Radix-2 butterfly operator 330, and a first stage. 2 Radix-2 butterfly operator 340, I / Q exchanger 350, tweed factor multiplier 360, and tweed factor generator 370.

The first buffer 310 and the second buffer 320 having different sizes according to stages operate as first-in first-out (FIFO) and perform a function of sorting input and output of a butterfly operator.

Data input to the butterfly unit is stored in the first buffer 310 in order. Data input from the initial or previous stage and data output from the first buffer 310 are output from the time point at which the first stored data is output from the first buffer 310 to the last data stored. To perform the first Radix-2 butterfly operation. Here, the Radix-2 butterfly operation is a technical matter apparent to those skilled in the art and is an operation for performing addition and subtraction on two data.

The addition result of the output of the first Radix-2 butterfly operator 330 is directly input to the I / Q exchanger 350. On the other hand, the result of the subtraction of the output of the first Radix-2 butterfly operator 330 is stored in the first buffer 310 and then input to the I / Q exchanger 350 after a delay of the buffer size.

The I / Q exchanger 350 is also a block that substantially multiplies the tweed factor. Trial multiplication with a value of '-j' or '1' only according to the quadratic decomposition of Radiz-2. This is simplified by changing the sign of I and then swapping the I / Q data with each other.

After passing through the I / Q exchanger 350, the data is stored in the second buffer 320, and then, as in the first buffer 310, the second Radix-2 butterfly operation is performed from the time when the first input data is output. do. The output is then input to the tween factor multiplier 360 in order by the second Radix-2 butterfly operator 340.

The tween factor factor multiplied at this time is generated by the tween factor generator 370, and is derived as shown in Equation 2 below according to the quadratic decomposition process of Radix-2.

[Equation 2]

Here, N is the size of the FFT, n ₃ is [0 ~ N / 4-1], k1 = (0,1), k2 = (0,1).

n ₃ is a counter value that increases every clock with the data input, and (k2, k1) changes to (0,0), (1,0), (0,1), (1,1) in N / 4 periods. Value.

4 is a diagram illustrating the index of the tween factor generated for N = 16.

FIG. 4 illustrates a tween factor index calculated according to n ₃ , k ₂ , and k 1 values corresponding to an input data string when N = 16. The tween factor value thus generated is complex-multiplied to the butterfly unit of the next stage. Since the Radix-2 quadratic SDF type FFT processor operates in a pipelined manner, the butterfly units are connected by the number of stages determined according to the FFT size and each stage is controlled.

However, the quadratic DIF FFT of Radix 2 receives a data sequence in a natural order, performs an FFT operation, and outputs the data sequence in an inverted order. On the other hand, modern modem modem receivers use (I) FFT not only for demodulation of received OFDM signals but also for equalizers and channel estimation. In this case, in implementing the (I) FFT in the FFT for demodulation and the equalizer to be performed later, when the conventional Radix 2 power DIF FFT algorithm is applied in the same way, the data outputted in the reversed order will be In order for the (I) FFT operation to be performed, the process must be rearranged in order. This realignment operation requires a memory corresponding to the FFT size, and there is a problem that a time delay occurs for symbols.

Accordingly, it is necessary to generate a tween factor necessary for performing a Fast Fourier Transform of the Radix-2 quadratic method on the data strings input in the inverted order.

In the present invention for achieving the above object, in order to apply the Radix-2 quadratic FFT algorithm to the data input in the inverted order, the tweed factor index (i = n ₃ (k1 +) used in each stage 2k2)) Reorder. To this end, in the present invention, in consideration of the fact that the input data string is bit inverted, n ₃ is bit inverted and the order of the tweed factor is reversed by changing the operation periods of k1 and k2. A detailed method for implementing this will be described below.

5 is a block diagram illustrating an internal structure of an FFT processor according to an embodiment of the present invention. The FFT processor of the present invention includes a first buffer 510, a second buffer 520, a first Radix-2 butterfly operator 530, a second Radix-2 butterfly operator 540, and an I / Q exchanger 550. ), A tweed factor multiplier 560, and a tweed factor generator 570.

The functions of the first Radix-2 butterfly operator 530, the second Radix-2 butterfly operator 540, and the tweed factor multiplier 560 illustrated in FIG. 5 have been described above with reference to FIG. 3. It will be omitted.

The first buffer 310 and the second buffer 320 having different sizes according to stages operate as first-in first-out (FIFO) and perform a function of sorting input and output of a butterfly operator. Meanwhile, referring to FIG. 8, which is a two-signal Signal Flow Graph of Radix-2 inputted in an inverted order, according to an embodiment of the present invention, two inputs used for the second Radix-2 butterfly calculation of each stage are described. You can see that the distance between the data is twice as long as the distance between the two data used in the first Radix-2 butterfly operation. A two-fold long distance between two data sets means that it takes twice as long to enter the next data after one of the two inputs of the Radix-2 buffer fly operator. Since the function of the first buffer and the second buffer is to input the two data simultaneously with the Radix-2 butterfly operator by matching the time difference occurring between the two input data, conventionally, the size of the first buffer is twice the size of the second buffer. On the contrary, in the present invention, the second buffer has a size twice the size of the first buffer.

The I / Q exchanger 550 exchanges the data of I and Q after changing the sign of I, which is the same operation as multiplying (-j) when the switch of the I / Q exchanger is 'ON'. If it is 'OFF', it is output as is. The operation period of this switch varies depending on the stage. When the input data is in the inverted order as in the present invention, it is the same as in the case that [OFF: ON] is in the form of [3: 1], but the switching cycle and ON This maintained interval follows the rule of four times longer than the previous stage. The switching operation timing of the I / Q exchange when N = 64 is illustrated in FIG. In the first stage, four data cycles in one cycle, keeping OFF for three data intervals and turning ON in one data interval. In the second stage, 16 data four times longer are held in one cycle, and then OFF is maintained for 12 data sections and repeated four times in the form of being turned on in four data sections. The last stage operates in the same manner as before, with 64 data being held at one cycle, which is OFF for 48 data intervals and ON for 16 data intervals.

The tween factor index generator 570 generates a tween factor index necessary for performing a Fast Fourier Transform of the Radix-r method on a data string input in a bit inverted order according to an embodiment of the present invention. When the FFT size is referred to as N _FFT , the data index k is represented by r-decimal number (r = 4 in the case of 2 ² ), and the stage number is represented by 's', the tween factor index generator 570 is used. The tween factor index 'i' generated in Equation 3 may be expressed as Equation 3 below.

&Quot; (3) "

Where r = 2 ² and n = log _r N _FFT

Hereinafter, a structure of a tween factor index generator 570 for implementing Equation 3 in real logic will be described.

FIG. 6 is a diagram illustrating a detailed structure of the tween factor index generator 570.

As shown in FIG. 6, the tweed factor generator 570 of the present invention includes a stage number counter 605, a data index counter 610, a shifter 620, a bit inverter 630, a selector 640, A scaler 650 and a multiplier 660 may be provided.

The stage number counter 605 determines the number of the current stage to which the data string is input and outputs the result value. The stage number counter 605 corresponds to a block for calculating the 's' value of Equation 3 above.

The data index counter 610 increases the counter value k by 1 and outputs the r-decimal digit each time data is input to the butterfly unit for each stage. The data index counter 610 operates to initialize the index to zero when all data of the N _FFT is input. According to an embodiment of the present invention, the data index counter 610 may be a 2n bit counter. The data index counter 610 corresponds to a block for calculating a 'k' value of Equation 3 above. For example, when r = 2 ² , the index of the first input data is [000] ₄ , the index of the second input data can be represented by [001] ₄ , and the data index is sequentially increased. .

The shifter 620 calculates a portion corresponding to k / r ^{(s + 1)} of Equation 3, and shifts a quaternary digit of an output value of the data index counter 610. The shifter 620 is a block for right shifting the index of the data represented by the hexadecimal number according to the number of the corresponding stage. Looking at the operation of this block, in the first stage (s = 0), if the data index (000, 001, 002, 003, 010, 011, ..., 330, 331, 332, 333) is inputted (s + 1) ) Digits, that is, one digit, are right-shifted to output (00, 00, 00, 00, 01, 01, ..., 33, 33, 33, 33). Looking at the case of the second stage (s = 1) for the same index, the data index data index (000, 001, 002, 003, 010, 011, ..., 330, 331, 332, 333) is input and two Right-shift the digit to output (0, 0, 0, 0, 0, 0, ..., 3, 3, 3, 3). In summary, the shifter 620 converts one digit (quat number, two bits) into one hexadecimal digit (00, 00, 00, 01, ..., 33) and two hexadecimal numbers according to the stage number. -Digit (00, 00, 00, 00, 01, ..., 33) to right shift (0, 0, 0, 0, 0, ..., 3).

The above process may be described as a process in which the shifter 620 selects a digit corresponding to a higher digit than 4 ^s (r ^s ) digits among the hexadecimal data indexes output from the data index counter 610.

The bit inverter 630 inverts the output value of the shifter 620 in units of bits and converts it to a decimal number to output a second factor for generating a tween factor index. Here, bit inversion refers to reading an arbitrary value from least significant bit (LSB) to most significant bit (MSB). For example, the bit inversion result of '0001' is '1000' and the bit inversion result of '0101' is '1010'.

The selector 640 is a block for calculating [d _S ] _r of Equation 3. The selector 640 is configured to generate a twiddle factor index from hexadecimal-digits (generally, r-digits, which are generally the same), which is set according to the current stage number among data index values output from the data index counter 610. Select and print as 1 argument. In other words, the selector 640 regards the output of the data index counter 610 as a hexadecimal number, and is a stage 0 during the data indexes (000, 001, 002, 003, 010, ...) expressed in hexadecimal. cases, the ⁴⁰ digits of _{d 0 (0, 1, 2} , 3, 0, ...) for selecting a first factor, and the case of the stage 1, 4 is ^one digit _{d 1 (0, 0, 0} , 0, 1, ...) as the first argument. In general, the selector 640 may select and output a digit corresponding to r ^s digits in the r-index data index value as a first factor for generating a tweed factor index.

For example, when the data index for the second input data is [001] ₄ in stage 0, the selector 640 selects the stage 0 in which the selector of stage ₄ is 4 ⁰ digits of '001 ₄ '. 1 'is selected as the first argument and output. On the other hand, in stage 1, when the data index for the second input data is [001], the selector of stage 1 selects and outputs '0', which is 4 ¹ digits of [001] ₄ , as a first factor.

The scaler 650 receives the stage number s output from the stage number counter 605 and generates a third factor for generating a tweed factor index. According to an embodiment of the present invention, the third factor may be r ^S.

The multiplier 660 multiplies the first factor selected by the selector 640, the second factor output from the bit inverter 630, and the third factor output from the scaler 650, thereby generating and outputting a tween factor index. do.

An example of the tween factor index generated by the tween factor index generator 570 of the present invention is shown in FIG. 7. Assume that N _FFT = 64.

Hereinafter, a case where the data index is 7 will be described in detail with reference to a tween factor index generation process.

First, in the case of stage 0, the stage number counter 605 determines and outputs 0 which is the number of the current stage to which the data string is input. In addition, the data index counter 610 sequentially counts the indexes of the input data strings and outputs them in an r-number (quad). In this example, it is assumed that 7 ([013] ₄ ).

Then, the selector 640 selects and outputs '3', which is a digit corresponding to 4 ⁰ (r ^s ) digits, among the hexadecimal data indexes output from the data index counter 610 as the first factor.

Meanwhile, the shifter 620 selects '01', which is a digit corresponding to a higher digit than 4 ⁰ (r ^s ) digits, among the hexadecimal data indexes output from the data index counter 610, and converts it to a binary number. The output is changed, and the value is '0001'.

The bit inverter 630 receives '0001', which is a value output from the shifter 620, and inverts the bit to generate '1000'. The bit inverter 630 converts the generated '1000' into a decimal number and outputs a second factor '8'.

Meanwhile, the scaler 650 receives the stage number 0 from the stage number counter 605 and outputs '1' (r ^s ) as the third factor.

Then, the multiplier 660 is a first factor ('3'), a second factor ('8'), a third factor (') output from the selector 640, the bit inverter 630, and the scaler 650. 1 '), each of which is multiplied with each other to generate and output a tween factor index' 24 '.

In summary, at stage 0, the tweed factor index for data with data index 7 is 24.

In the case of stage 1, the stage number counter 605 determines and outputs 1, which is the number of the current stage to which the data string is input. In addition, the data index counter 610 sequentially counts the indexes of the input data strings and outputs them in an r-number (quad). In this example, it is assumed that 7 ([013] ₄ ).

Then, the selector 640 selects and outputs '1', which is a digit corresponding to 4 ¹ (r ^s ) digits, among the hexadecimal data indexes output from the data index counter 610 as the first factor.

Meanwhile, the shifter 620 selects '0', which is a digit corresponding to a higher digit than 4 ¹ (r ^s ) digits, among the hexadecimal data indexes output from the data index counter 610, and converts it to a binary number. The output is changed, and the value is '00'.

The bit inverter 630 receives '00', which is a value output from the shifter 620, and inverts the bit to generate '00'. The bit inverter 630 converts the generated '00' into a decimal number and outputs a second factor '0'.

Meanwhile, the scaler 650 receives the stage number 0 from the stage number counter 605 and outputs '4' (r ^s ) as the third factor.

The multiplier 660 then selects the first factor ('1'), the second factor ('0'), and the third factor (the values output from the selector 640, the bit inverter 630, and the scaler 650). '4'), respectively, and multiply them to generate and output a 'tw' factor index '0'.

In summary, in stage 1, the tweet factor index for data with data index 7 is zero.

FIG. 8 is a diagram showing a data flow graph (Signal Flow Graph) to which Equation 3 described above is applied to N _FFT = 64.

9 is a flowchart illustrating a process of generating a tween factor index according to an embodiment of the present invention.

First, in step S910, the stage number counter 605 determines and outputs the number of the current stage to which the data string is input. In operation S920, the data index counter 610 sequentially counts the indexes of the input data strings, and outputs the counted data indexes as an r-number in operation S930.

In operation S940, the selector 640 selects and outputs, as a first factor, a digit corresponding to r ^s digits among the r-index data indexes output from the data index counter 610.

In operation S950, the shifter 620 selects a digit corresponding to a digit higher than the r ^s digits among the r data indexes output from the data index counter 610, and inverts the bit to output the second digit. . Here, the second factor, which is bit inverted, is expressed in decimal.

In operation S960, the scaler receives the stage number from the stage number counter and outputs r ^s as a third factor.

Then, the multiplier 660 receives the first factor, the second factor, and the third factor respectively output from the selector 640, the bit inverter 630, and the scaler 650 in step S970, and multiplies them by multiplying them. Generate and print these factor indices.

The embodiments of the present invention disclosed in the present specification and drawings are merely illustrative of specific embodiments of the present invention and are not intended to limit the scope of the present invention in order to facilitate understanding of the present invention. It will be apparent to those skilled in the art that other modifications based on the technical idea of the present invention can be carried out in addition to the embodiments disclosed herein.

1 shows a signal flow graph (SFG) of a Radix-2 power of two DIF FFTs for a conventional N = 64.

FIG. 2 illustrates an FFT processor structure implemented using Radix-2's quadratic DIF FFT algorithm shown in FIG.

FIG. 3 shows a detailed structure of any stage shown in FIG.

4 illustrates the index of the tween factor generated for N = 16.

5 is a block diagram illustrating an internal structure of an FFT processor according to an embodiment of the present invention.

6 illustrates a detailed structure of the tweed factor index generator 570.

FIG. 7 shows an example of the tween factor index generated by the tween factor index generator 570 of the present invention. FIG.

FIG. 8 is a diagram showing a data flow graph to which Equation 3 described above is applied for N _FFT = 64. FIG.

9 is a flowchart illustrating a process of generating a tween factor index according to an embodiment of the present invention.

10 illustrates a switching period of an I / Q converter in accordance with an embodiment of the present invention.

Claims (4)

In a tween factor index generator of an n-th order fast Fourier transform processor of Radix-r, A stage number counter for determining and outputting a number s of stages into which data is input; A data index counter which sequentially counts the indexes of the input data and outputs the counted data indexes in r numbers; A selector for selecting and outputting a digit corresponding to r ^s digits as a first factor among digits constituting the r-index data index; A shifter for selecting a digit corresponding to a higher digit than the r ^s digit among digits constituting the data index of the r decimal number; A bit inverter for bit inverting the digit selected by the shifter and outputting the second digit as a second factor; A scaler for generating a third factor for scaling according to the determined stage number; And And a multiplier for multiplying the first factor, the second factor, and the third factor to generate the tweet factor index. The method of claim 1, And a fast Fourier transform processor using a Radix 2 ² scheme. In a tween factor index generation method of a n-th order fast Fourier transform processor of Radix-r, Determining and outputting a number s of stages into which data is input; Sequentially counting the indices of the input data and outputting the counted data indices in r numbers; Selecting and outputting a digit corresponding to r ^s digits as a first factor among digits constituting the data index of the r decimal number; Selecting a digit corresponding to a higher digit than the r ^s digit from among digits constituting the r-index data index; Bit-inverting the digit selected by the shifter and outputting the digit as a second factor; Generating a third factor for scaling according to the determined stage number; And And multiplying the first factor, the second factor and the third factor to generate the tweet factor index. The method of claim 3, The fast Fourier transform processor uses a Radix 2 ² scheme.

Images