WO2009014291A1

WO2009014291A1 - Fast fourier transforming method and processor for 4x4 mimo-ofdm wlan system

Info

Publication number: WO2009014291A1
Application number: PCT/KR2008/000285
Authority: WO
Inventors: Jae-Seok Kim; Sang-Min Lee; Yun-Ho Jung
Original assignee: Industry Academic Cooperation Foundation of Yonsei University
Current assignee: Industry Academic Cooperation Foundation of Yonsei University
Priority date: 2007-07-26
Filing date: 2008-01-17
Publication date: 2009-01-29
Anticipated expiration: 2010-01-26
Also published as: KR20090011398A; KR100929393B1

Abstract

The present invention relates to a fast Fourier transforming method for a 4X4 MIMO-OFDM WLAN system and an apparatus thereof. More particularly, the present invention relates to a fast Fourier transforming method for a 4 4 MIMO-OFDM WLAN system and apparatus thereof, in which an multi-channel MDC (Multi-path Delay Commutator) structure is formed to support multiplex data paths, four fast Fourier transform operations required for a 4x4 MIMO (Multiple Input Multiple Output ) -OFDM (Orthogonal Frequency Division Multiplexing) WLAN system can be processed by one processor, the number of non-trivial multiplications can be reduced as compared with an existing 4- chanle Radix-4 MDC FFT processor using an efficient Radix decomposition based on a mixed Radix scheme, thereby reducing hardware complexity.

Description

[DESCRIPTION]

[Invention Title]

FAST FOURIER TRANSFORMING METHOD AND PROCESSOR FOR 4X4 MIMO-OFDM WLAN SYSTEM

[Technical Field]

The present invention relates to a fast Fourier transforming method for a 4X4 MIMO-OFDM WLAN system and an apparatus thereof. More particularly, the present invention relates to a fast Fourier transforming method for a 4 4 MIMO-OFDM WLAN system and apparatus thereof, in which an multi-channel MDC (Multi-path Delay Commutator) structure is formed to support multiplex data paths, four fast Fourier transform (hereinafter, referred to as "FFT") operations required for 4X4 MIMO (Multiple Input Multiple Output)- OFDM(Orthogonal Frequency Division Multiplexing) WLAN system can be processed by one processor, the number of non-trivial multiplications can be reduced as compared with an existing 4-chanle Radiχ-4 MDC FFT processor using an efficient Radix decomposition based on a mixed Radix scheme, thereby reducing hardware complexity.

[Background Art]

In general, in a digital data communication system, data is transmitted through modulation and demodulation at the time of transmitting and receiving the data. The modulation and demodulation are performed by a modem and the modem has a different structure according to a modulation scheme. A variety of modulation schemes and multiplexing schemes are used in data communication. An orthogonal frequency division multiplexing (hereinafter, referred to as "OFDM") scheme has been suggested for high-speed data transmission through a multi-path channel in a radio communication system.

Meanwhile, a next-generation WLAN system that enables a high channel capacity and high-speed data transmission for use in a multimedia service such as an HDTV using a WLAN has been increasingly required. To do so, an MIMO scheme has been suggested, in which a diversity gain is obtained by increasing the number of transmitting and receiving antennas. The MIMO scheme can effectively overcome an influence due to a frequency selective fading environment when the MIMO scheme and the OFDM scheme are used together. Therefore, the MIMO scheme and the OFDM scheme are researched together. The MIMO-OFDM scheme can improve the throughput due to an increase in the transmission amount and improvement of performance at the same band.

The IEEE 802. Hn standardized system is oriented to a high-speed WLAN system, and is being standardized to support a maximum of 4X4 MIMO system and a maximum of transmission rate of 300/600 Mbps. However, in the MIMO- OFDM system, the high throughput is obtained, but system complexity is high. In the 4X4 MIMO system, if an independent block is used for each data path, four OFDM baseband processors that operate in parallel are required, which results in increasing hardware complexity four times.

FIG. 1 is a block diagram illustrating a 4x4 MIMO system among the IEEE 802.Hn standardized systems. As can be seen from FIG. 1, if the MIMO technology is applied to the OFDM system, multiplex data paths are formed and hardware complexity is increased.

Accordingly, in order to apply the MIMO technology and prevent hardware complexity from increasing, an efficient system block that can process multiplex data paths needs to be developed. In particular, in the WLAN system, an FFT processor occupies about 30% with respect to 100% of hardware complexity of the entire system, complexity of the FFT processor is preferably reduced so as to reduce hardware complexity of the MIMO-OFDM WLAN system.

Further, a non-trivial multiplier occupies a large portion of the FFT processor. In the existing FFT processor, a Radiχ-2 algorithm and a Radiχ-4 algorithm are mainly used. The Radiχ-2 algorithm is efficient for an SISO (Single Input Single Output)-0FDM, but inefficient for the MIMO-OFDM. The Radiχ-4 algorithm requires a large number of non-trivial multipliers, which results in increasing hardware complexity. [Disclosure]

[Technical Problem]

Accordingly, the present invention has been made to solve the above- described problem, and it is an object of the present invention to a fast Fourier transforming method for a 4x4 MIMO-OFDM WLAN system and apparatus thereof, in which an multi-channel MDC (Multi-path Delay Commutator) structure is formed to support multiplex data paths, four fast Fourier transform (hereinafter, referred to as "FFT") operations required for 4X4 MIMO (Multiple Input Multiple Output)-OFDM(Orthogonal Frequency Division Multiplexing) WLAN system can be processed by one processor, the number of non-trivial multiplications can be reduced as compared with an existing 4- chanle Radiχ-4 MDC FFT processor using an efficient Radix decomposition based on a mixed Radix scheme, thereby reducing hardware complexity.

[Technical Solution]

In order to achieve the object of the present invention, according to an embodiment of the present invention, there is provided a fast Fourier transform method for a 4X4 MIMO-OFDM WLAN system. The fast Fourier transform method includes (a) a step of selecting an operation mode of a fast Fourier transform (FFT) or an inverse fast Fourier transform (IFFT), when 4- channel data is input; (b) a step of sequentially distributing the 4-channel data during the operation mode selected in the step of (a) and performing delay commutation; (c) a step of using a Radiχ-4 butterfly operation to perform addition and subtraction of the 4-channel data, on which delay commutation is performed through the step of (b); (d) a trivial multiplication step of processing W₈ multiplication independently existing for each data path with respect to the data, on which addition or subtraction are performed through the step of (c); (e) a step of using a Radiχ-2 butterfly operation to perform addition and subtraction of the data, on which trivial multiplication is performed through the step of (d); and (f) a non-trivial multiplication step of processing W₆₄ multiplication independently existing for each data path with respect to the data, on which addition or subtraction are performed through the step of (e).

According to another embodiment of the present invention, there is provided a fast. Fourier transform apparatus for a 4x4 MIMO-OFDM WLAN system. The fast Fourier transform apparatus includes an operation mode selector that selects an operation mode of a fast Fourier transform (FFT) or an inverse fast Fourier transform (IFFT), when 4-channel data is input; a first delay commutator that sequentially distributes the 4-channel data to sequentially perform operations, performs a switching operation having 16, 32, and 48 delay symbols at the second, third, and fourth paths, respectively, and has 48, 32, and 16 delay symbols at the first, second, and third paths, respectively; a Radix-4 butterfly operator that performs addition or subtraction of the data that has passed the first delay commutator; a trivial multiplying unit that processes W₈ multiplication independently existing for each data path with respect to the data, on which the Radix-4 butterfly operation is performed; a Radix-2 butterfly operator that performs addition or subtraction of the data that has passed the trivial multiplying unit; a second delay commutator that arranges the data having passed the trivial multiplying unit according to a data distance required by the Radix-2 butterfly operator, performs a switching operation having 8 delay symbols at each of the second and fourth paths, and has 8 delay symbols at each of the first and third paths; and a non-trivial multiplying unit that processes W₆₄ multiplication independently existing for each data path with respect to the data that has passed the second delay commutator. [Advantageous Effects]

According to the present invention, multi-channel data can be processed by one FFT processor by using only an additional commutator having low complexity. According to the present invention, it is possible to achieve area reduction effects of 25% and 64%, as compared with FFT processors having the

4-channel R4MDC scheme and the four 1-channel R2 SDF scheme.

According to the present invention, the number of non-trivial multiplications that is most important in terms of complexity of an FFT process is reduced through an effective Radix decomposition, thereby reducing hardware complexity.

According to the present invention, a lot of next-generation communication systems, such as IEEE 802.16e Mobile WiMAX and 4G, which are defined in recent years, are based on an MIMO-OFDM. Accordingly, the present invention can be effectively applied to various systems. [Description of Drawings]

FIG. 1 is a block diagram illustrating a 4x4 MIMO system among the IEEE 8.2. Hn standardized systems.

FIG. 2 is a signal flow graph of an FFT signal using an MR algorithm according to the preferred embodiment of the present invention.

FIG. 3 is a block diagram illustrating an FFT apparatus according to the preferred embodiment of the present invention.

FIG.4 is a block diagram illustrating an operation mode selector.

FIG.5 is a block diagram illustrating a first delay commutator.

FIG. 6 is a conceptual diagram illustrating a data arrangement pattern of a first delay commutator.

FIG.7 is a block diagram illustrating a second delay commutator.

FIG. 8 is a conceptual diagram illustrating a data arrangement pattern of a second delay commutator.

FIG.9 is a block diagram illustrating a third delay commutator.

FIG. 10 is a conceptual diagram illustrating a data arrangement pattern of a third delay commutator.

FIG. 11 is a block diagram illustrating a fourth delay commutator.

FIG. 12 is a conceptual diagram illustrating a data arrangement pattern of a fourth delay commutator.

FIG. 13 is a block diagram illustrating an operation structure of an R4BF operator.

FIG. 14 is a block diagram illustrating an operation structure of an R2BF operator.

FIG. 15 is a block diagram illustrating an operation structure of a trivial multiplying unit.

FIG. 16 is a block diagram illustrating an operation structure of a W₈ operator.

FIG. 17 is a block diagram illustrating an operation structure of a scaling factor operation unit.

2

FIG. 18 is a block diagram illustrating an operation structure of a W₈ operator.

3

FIG. 19 is a block diagram illustrating an operation structure of a W₈ operator.

FIG. 20 is a block diagram illustrating an operation structure of a non-trivial multiplying unit.

FIG. 21 is a block diagram illustrating an operation structure of W₆₄ among a non-trivial multiplying unit shown in FIG.20.

FIG. 22 is a block diagram illustrating an operation structure of an actual multiplying unit. [Best Mode]

The preferred embodiments of the present invention will now be described in detail with reference to the accompanying drawings. Like reference numerals designate like elements throughout the specification. However, in describing the present invention, when the specific description of the related known structure or function departs from the scope of the present invention, the detailed description thereof will be omitted. Hereinafter, the preferred embodiments of the present invention will be described, but the technical scope of the present invention is not limited thereto, and various modifications and changes can be made by those skilled in the art without departing from the spirit and scope of the present invention.

First, an algorithm of mixed Radix (hereinafter, referred to as "MR") of Radix-4 and Radix-2 according to the present invention will be described.

A discrete Fourier transform (DFT) expression that has N points is as represented by the following Equation 1.

[Equation 1]

In order to represent Equation 1 in a mixed form of Radix-4 and Radix- 2, if n and k for three-dimensional decomposition are substituted for Equation 1, Equation 2 is obtained.

[Equation 2]

In Equation 2, BF₄ is summarized as follows. [Equation 3]

This corresponds to a Radix-4 butterfly operation. A twiddle factor as a coefficient of DFT may be summarized again, as represented by Equation 4. [Equation 4]

If Equation 4 is substituted for Equation, Equation 5 is obtained. [Equation 5]

In this case, H is represented by Equation 6. [Equation 6]

H(n₃, k₁, k₂) means a Radiχ-2 butterfly operation. Since W₈ is trivial multiplication, an operation amount is reduced. If the above decomposition process is applied to the remaining N/8 points, it is possible to obtain a final equation of an MR algorithm where Radix-2 is mixed on the basis of Radix-4.

In the present invention, the above-described MR algorithm is applied to an MDC (Multi-path Delay Commutator) to implement an MRMDC structure. As a result, the number of non-trivial multiplications is reduced, thereby reducing hardware complexity. A compared result of operations of Radix-4 MDC (hereinafter, referred to as "R4MDC") and MRMDC in a 64-point FFT processor is shown in the following Table 1. [Table 1]

An FFT processor of an MRMDC scheme has a four-stage butterfly structure, and performs trivial multiplication two times and non-trivial multiplication once. Meanwhile, an FFT processor of an R4MDC scheme has a three-stage butterfly structure, and performs non-trivial multiplication two times. In the case of the R4MDC scheme, the number of stages is small. However, since a Radix-4 butterfly is equivalent to four Radix-2 butterflies, the number of s;ages is the same in both the MRMDC scheme and the R4MDC scheme. In the case of the R4MDC scheme where non-trivial multiplying units that are more complex than the butterfly operator are large, hardware complexity is high.

FIG. 2 is a signal flow graph illustrating an FFT signal using an MR algorithm according to the preferred embodiment of the present invention.

The FFT method and apparatus according to the preferred embodiment of the present invention have the 64-point structure in relation to the IEEE 802. Hn standardized systems. Since the 64-point structure may be easily applied to both the Radiχ-4 scheme and the Radix-2 scheme, the 64-point structure may be easily applied to a 4X4 MIMO-OFDM system.

In FIG. 2, a 64-point MR FFT algorithm is configured by four stages that include a first stage (Sl), a second stage (S2), a third stage (S3), and a fourth stage (S4). Further, the first stage (Sl), the second stage (S2), and the third stage (S3) include a stage of first trivial multiplication (Ml), a stage of non-trivial multiplication (M2), and a stage of second trivial multiplication (M3), respectively.

The first stage (Sl) is a portion where the Radix-4 butterfly operation is performed. At this time, the Radix-4 butterfly operation is performed by a first Radiχ-4 butterfly operator 300 and a first trivial multiplying unit 400 shown in FIG.3. In the first trivial multiplication (Ml), data on which a butterfly operation is performed is multiplied by W₈₁ , W₈₂ , and W₈₃ to perform trivial multiplication. According to the result that is obtained by performing the first stage (Sl), the length of the data becomes shorter to N/4 = 16.

The second stage (S2) is a portion where the Radix-2 butterfly operation is performed. At this time, the Radix-2 butterfly operation is performed by a first Radix-2 butterfly operator 600 and a non-trivial multiplying unit 700 shown in FIG. 3. In the non-trivial multiplication

(M2), data on which a butterfly operation is performed is multiplied by W₆₄ ⁱ to perform non-trivial multiplication. According to the result that is obtained by performing the second stage (S2), the length of the data becomes shorter to N/8 = 8.

The third stage (S3) is a portion where the Radiχ-4 butterfly operation is performed, similar to the first stage (S1). At this time, the Radix-4 butterfly operation is performed by a second Radix-- butterfly operator 900 and a second trivial multiplying unit 1000 shown in FIG. 3. According to the result that is obtained by performing the third stage (S3), the length of the data becomes shorter to N/32 = 2.

Finally, the fourth stage (S4) is a portion where the Radiχ-2 butterfly operation is performed, similar to the second stage (S2) . At this time, the Radiχ-2 butterfly operation is performed by a second Radiχ-2 butterfly operator 1200 shown in FIG. 3. According to the result that is obtained by performing the fourth stage (S4), the length of the data becomes shorter to N/64 = 1.

Next, a fast Fourier transform (hereinafter, referred to as "FFT" apparatus according to the preferred embodiment of the present invention where the above-described MR algorithm is applied will be described.

The FFT apparatus according to the preferred embodiment of the present invention is used for an OFDM system and has a pipe-line structure. Since data is sequentially processed because of a characteristic of the OFDM system, the OFDM system is preferably implemented by using the pipe-line structure. Meanwhile, in a single butterfly structure, hardware complexity is lowest. However, since all operations are performed by only one operator, data processing time is long. A parallel structure has a fast processing time, but has high hardware complexity.

Since the FFT apparatus according to the preferred embodiment of the present invention is used for the MIMO-OFDM system, the FFT apparatus has an MDC structure among the pipe-line structure. The MDC scheme is a scheme in which an input data flow is divided into parallel data flows and data is sequentially processed. In the MDC scheme, the amount of data processed is increased, but utilization (time used by an operator) is reduced to half of the original time. Meanwhile, an SDF (Single-path Delay Feedback) structure is suitable for an SISO-OFDM in terms of the operation amount and memory consumption, and an SDC (Single-path Delay Commutator) structure is complex in terms of control . Referring to FIG. 3, the FFT apparatus according to the preferred embodiment of the present invention includes a first operation mode selector 100, a first delay commutator 200, a first Radiχ-4 butterfly operator 300 (hereinafter, referred to as "first R4BF operator"), a first trivial multiplying unit 400, a second delay commutator 500, a first Radiχ-2 butterfly operator 600 (hereinafter, referred to as "first R2BF operator"), a non-trivial multiplying unit 700, a third delay commutator 800, a second Radix-4 butterfly operator 900 (hereinafter, referred to as "secnd R4BF operator"), a second trivial multiplying unit 1000, a fourth delay commutator 1100, a second Radiχ-2 butterfly operator 1200 (hereinafter, referred to as "second R2BF operator"), and a second operation mode selector 1300. In the FFT apparatus, the first operation mode selector 100 and the second operation mode selector 1300 that select FFT/IFFT operations are first provided at the first stage of an input terminal and the last stage of an output terminal, respectively. Then, the first delay commutator 200 and the fourth delay commutator 1100 that distribute 4-channel data are provided at the input/output terminals, respectively. For every stage, the R4BF operators 300 and 900 and the R2BF operators 600 and 1200 are provided to perform a butterfly operation. After the butterfly operation is performed, a multiplier is provided. The multiplier is divided into the trivial multiplying units 400 and 1000 and the non-trivial multiplying unit 700.

FIG. 4 is a block diagram illustrating an operation mode selector. In the following drawings including FIG. 4, IN_reai and IN_imag denote a real part and an imaginary part of input data, respectively, and 0UT_reai and 0UTi_mag denote a real part and an imaginary part of output data, respectively.

The first operation mode selector 100 and the second operation mode selector 1300 are provided at the first stage of the input terminal and the last stage of the output terminal, respectively, and select FFT/IFFT operations. Since the IFFT operation can be expressed as the FFT operation as represented by the following Equation, the FFT apparatus can perform both the FFT operation and the IFFT operation using one hardware. [Equation 7]

Accordingly, IFFT(X(K)) = (1/N)FFT(X^*(K))^* is realized. When the IFFT operation is performed using the FFT operation, if only a 1/ N component is excluded, an input value of the FFT operation may take X (k) that is a complex conjugate number of an input value X(k) in the IFFT operation, and an output value IFFT(X(k)) in the IFFT operation may take FFT(X^*(k))^* that is a complex

_* conjugate number of FFT(X (k)) as an output value of the FFT operation.

In a transmitting scheme in the OFDM system, since the 1/N component is not used, a sign of an imaginary part is changed at the time of inputting data of the FI¹T processor and a sign of an imaginary part is changed at the time of outputting data. As a result, it is not necessary to separately implement an IFFT processor for an OFDM system. Accordingly, the first operation mode selector 100 and the second operation mode selector 1300 are provided at the starting portion and the ending portion of the FFT processor. According to whether the FFT operation is performed or the IFFT operation is performed, a sign shifter (complement) 10 selects whether or not to change a sign of an imaginary part of the data. In this way, the FFT and the IFFT may be implemented by one processor.

That is, in the case of the FFT operation, the first operation mode selector 100 and the second operation mode selector 1300 do not operate the sign shifter 110 and output an imaginary part (IN_imag) of the input data as it is (OUTimag). Meanwhile, in the case of the IFFT operation, the first operation mode selector 100 operates the sign shifter 110 to change a sign of the imaginary part of the input value X(k), such that X (k) is input to the FFT apparatus. Further, the second operation mode selector 1300 operates the sign shifter 110 to change a sign of the imaginary part of the output value

FFT(X^*(k)), such that FFT(X^*(k))^* is output.

FIG. 5 is a block diagram illustrating a first delay commutator and FIG. 6 is a conceptual diagram illustrating a data arrangement pattern of a first delay commutator.

The first delay commutator 200 sequentially distributes 4-channel data and arranges the data, such that the individual operations are sequentially performed. The distance between data, which is needed to perform a 4-channel and 64-point operation, is 64/4 = 16, and thus the number of delay symbols (z

) is determined as a multiple of 16. That is, on the basis of a switching unit 210, the second path of the input terminal has 16 delay symbols, the third path thereof has 32 delay symbols, and the fourth path thereof has 48 delay symbols. In order to adjust the distance between the data after a switching operation is performed by the switching unit 210, the first path of the output terminal has 48 delay symbols, the second path thereof has 32 delay symbols, and the third path thereof has 16 delay symbols.

Referring to FIG. 6, if data having the length of 64 points is simultaneously input for every channel (INPUT), the data is sequentially arranged such that the delay symbols are added at the input terminal of the switching unit 210 and the distance between the data becomes 16 (DELAY). Then, the switching unit 210 performs a switching operation in various patterns. Then, in order to perform a butterfly operation in the first R4BF operator 300, the distance between the data for each path at one channel is preferably adjusted to the distance that is required by the R4BF operation. As a result, the data distance for each channel is adjusted to 64/4 = 16. In contrast as the input terminal of the switching unit 210, at the output terminal thereof, the delay symbols are added and the data is arranged. Accordingly, data, which is arranged in series to have the data distance of 64 for each path at the input terminal of the switching unit 210, is distributed in parallel to have the data distance of 16 for every four paths at the output terminal of the switching unit 210. The data from 0 to 15 is arranged in the first path, the data from 16 to 31 is arranged in the second path, the data from 32 to 47 is arranged in the third path, and the data from 48 to 63 is arranged in the fourth path.

FIG.7 is a block diagram illustrating a second delay commutator. FIG. 8 is a conceptual diagram illustrating a data arrangement pattern of a second delay commutator.

The second delay commutator 500 receives data that has passed the first R4BF operator 300 and rearranges the data according to the data distance required by an R2 butterfly operation before the data is input to the first R2BF operator 600. Referring to FIG. 2, the R2BF operation requires a difference that corresponds to 16/2 = 8 between two paths. In order to maintain a distance difference of 8 between the data, a delay corresponding to 8 is needed in each of the two input paths. That is, on the basis of the switching unit 510, the second path of the input terminal has 8 delay symbols and the fourth path thereof has 8 delay symbols. In order to adjust the distance between the data after a switching operation is performed by the switching unit 510, the first path of the output terminal has 8 delay symbols and the third path has 8 delay symbols.

Referring to FIG. 8, a data arrangement pattern is configured in two types. One is a data arrangement type where input data is output without being changed, and the other is a data arrangement type where data is exchanged between two adjacent paths. If data having the length of 16 points is input for every channel (INPUT), delay symbols are added at the input terminal of the switching unit 510 and data is arranged such that the distance between the data becomes 8 (DELAY). Then, switching is made in various patterns in the switching unit 510. Then, in order to perform a butterfly operation in the first R2BF operator 600, the data distance for each path at one channel is preferably adjusted to the distance that is required by the R2BF operation. As a result, for every channel, the data distance is adjusted to 8. In contrast to the input terminal of the switching unit 510, at the output terminal thereof, the delay symbols are added and the data is arranged. Accordingly, at the output terminal of the switching unit 510, the data is distributed in parallel such that each of the four paths has the data distance of 8. The data of 0 to 7/16 to 23 is arranged in the first path, the data of 8 to 15/24 to 31 is arranged in the second path, the data of 32 to 39/48 to 55 is arranged in the third path, and the data of 40 to 47/56 to 63 is arranged in the fourth path.

FIG. 9 is a block diagram illustrating a third delay commutator, and FIG. 10 is a concept diagram illustrating a data arrangement pattern of a third delay commutator.

The third delay commutator 800 receives data that has passed the first R2BF operator 600 and rearranges the data according to the data distance required by an R4 butterfly operation before the data is input to the second R4BF operator 900. Referring to FIG. 2, the R4BF operation requires a difference that corresponds to 8/4 = 2 between two paths. In order to sequentially arrange 4-channel data, delays corresponding to 2, 4, and 6 are needed in the three input paths, respectively. That is, on the basis of the switching unit 810, the second path of the input terminal has 2 delay symbols, the third path thereof has 4 delay symbols, and the fourth path thereof has 6 delay symbols. In order to adjust the distance between the data after a switching operation is performed by the switching unit 810, the first path of the output terminal has 6 delay symbols, the second path thereof has 4 delay symbols, and the third path thereof has 2 delay symbols.

Since the operation principle of the data arrangement pattern of the third delay commutator 800 is the same as that of the data arrangement pattern of the first delay commutator 200, the detailed description of FIG. 10 will be omitted.

FIG. 11 is a block diagram illustrating a fourth delay commutator, and FIG. 12 is a conceptual diagram illustrating a data arrangement pattern of a fourth delay commutator.

The fourth delay commutator 1100 receives the data that has passed the second R4BF operator 900 and rearranges the data according to the data distance required by an R2 butterfly operation before the data is input to the second R2BF operator 1200 that exists at the last stage. Referring to FIG. 2, the R2BF operation requires a difference that corresponds to 2/2 = 1 between two paths. In order to maintain the distance difference corresponding to 1 between the data, a delay corresponding to 1 is needed for each of the two input paths. That is, on the basis of the switching unit 1210, the second path of the input terminal has a 1 delay symbol and the fourth path thereof has a 1 delay symbol. In order to adjust the distance between the data after a switching operation is performed by the switching unit 1210, the first path of the output terminal has a 1 delay symbol and the third path thereof has a 1 delay symbol.

Since the operation principle of the data arrangement pattern of the fourth delay commutator 1200 is the same as that of the data arrangement pattern of the second delay commutator 500, the detailed description of FIG. 12 will be omitted.

The two R4BF operators are used. One is the first R4BF operator 300 that performs an R4BF operation on data arranged by the first delay commutator 200 and the other is the second R4BF operator 900 that performs an R4BF operation on data arranged by the third delay commutator 800. In the present invention, since the trivial multiplying units 400 and 1000 and the non-trivial multiplying unit 700 that perform multiplication of a twiddle factor (W) are implemented in separated blocks, respectively, the R4BF operators 300 and 900 may perform only the addition and subtraction of data. Referring to FIG. 13, each of the R4BF operators 300 and 900 primarily includes an adder between real parts, a subtracter between the real parts, an adder between imaginary parts, and a subtracter between the imaginary parts. Each of the R4BF operators 300 and 900 secondarily includes an adder and a subtracter that perform an operation between the real part and the imaginary part.

The first R4BF operator 300 reduces the data length from N = 64 to (1/4)N = 16, and the second R4BF operator 900 reduces the data length from N/8 = 8 to (1/4)(N/8) = N/32 = 2.

The four R2BF operators are used. The four R2BF operators include a pair of first R2BF operators 600 that perform an R2BF operation on the data arranged by the second delay commutator 500, and a pair of second R2BF operators 1200 that perform an R2BF operation on data arranged by the fourth delay commutator 1100. Like the above-described R4BF operators 300 and 900, since the function of multiplying the twiddle factor is not included, the R2BF operators 600 and 1200 may perform only addition and subtraction between the data. Meanwαile, as shown in FIG. 14, since the R2BF operators 600 and 1200 independently perform two R2BF operations, the operators are configured as pairs for the four data paths.

The first R2BF operator 600 reduces the data length from N/4 = 16 to (1/2)(N/4) = 8, and the second R2BF operator 1200 reduces the data length from N/32 = 2 to (1/2)(N/32) = 1.

FIG. 15 is a block diagram illustrating an operation structure of a trivial multiplying unit, FIG. 16 is a block diagram illustrating an operation structure of a W₈ operator, and FIG. 17 is a block diagram illustrating an operation structure of a scaling factor operation unit. FIG.

2

18 is a block diagram illustrating an operation structure of a W₈ operator.

3

FIG. 19 is a block diagram illustrating a structure of a W₈ operator.

The trivial multiplying units 400 and 1000 are composed of a first trivial multiplying unit 400 that is located between the first R4BF operator 300 and the second delay commutator 500 and a second trivial multiplying unit 1000 that is located between the second R4BF operator 900 and the fourth delay commutator 1100. The trivial multiplying units 400 and 1000 process W₈

0 1 2 3 multiplication and perform four types of operations of W₈ , W₈ , W₈ , and W₈. k (-j2?8)k (-l/2)k k -1/2 .

In the W₈ = e = 2 (1-j) , 2 is a constant and thus, W₈ multiplication may be defined as trivial multiplication. Accordingly, the trivial multiplying units 400 and 1000 do not require a separate complex

0 1 2 3 multiplier. Referring to FIG. 2, since W₈ , W₈ , W₈ , and W₈ independently exist for the individual paths, a separate selector or distributor is not needed, and only a corresponding operation may be performed for each path. o In the actual operation, since the W₈=I is realized, the operation is not

1 2 performed, and three operators that include a W₈ operator 410, a W₈ operator

3

420, and a W₈ operator 430 are implemented.

Referring to FIG. 16, the W₈ operator 410 includes a real number adder 412, a real number subtracter 414, and a scaling factor operation unit 416.

-1/2

In the description below, l/v2 =2 is called a scaling factor. Since the Ws operation is the same operation as a phase rotation of

-45 degrees on a complex plane, it includes multiplication of a complex number and a scaling factor Accordingly,

multiplication between an arbitrary input value X = X_reai + jXimag and

is

processed as a real number summation operation and a constant multiplication operation, as represented by the following Equation. [Equation 8]

-1/2

Meanwhile, 2 may be approximated and configured as a combination of shift and addition operations. [Equation 9]

Referring to FIG. 17, a scaling factor operation unit 416 includes a 1- bit shifter 416a, a 3-bit shifter 416b, a 4-bit shifter 416c, a 6-bit shifter 416d, and an adder 416e.

Since the operation is the same operation as a phase transition of

- 90 degrees on a complex plane

a sign of a real value of an input is changed to become an imaginary value of an output. The imaginary value of the input becomes a real value of the output. Accordingly, an imaginary part of an input value is output as an imaginary part, and a sign of a real part of the input value is changed and the real part is output as an imaginary part. [Equation 10]

2

Thus, the W₈ operator 420 is composed of only a sign shifter 422. Referring to FIG. 18, a sign of the real value IN_reai of the input is changed through the sign shifter 422 and the real value becomes an imaginary value OUTimag of the output. The imaginary value IN_iniag of the input becomes a real value OUTreai of the output.

3

Referring to FIG. 19, a W₈ operator 430 includes a real number adder

432, a real number subtracter 434, a scaling factor operation unit 436, and a sign shifter 438.

3

The W₈ operation is the same operation as a phase rotation of -135 degrees on a complex plane, and thus it is composed of multiplication of a

3 —i2?/8 —1/2 complex number and a scaling factor (W₈ = e =2 (-1-j)). Accordingly,

3 mul t ipl icat ion between an arbitrary input value X = X_reai + jXi_mag and W₈ i s

-1/2 processed as a real number summation operation and a 2 constant multiplication operation as represented by the following Equation. [Equation 11]

Meanwhile, the scaling factor operation unit 436 has the same structure as the scaling factor operation unit 416 of the W₈ operator 410.

FIG. 20 is a block diagram illustrating an operation structure of a non-trivial multiplying unit, FIG. 21 is a block diagram illustrating an operation structure of W₆₄ among a non-trivial multiplying unit shown in FIG.

20, and FIG. 22 is a block diagram illustrating an operation structure of an actual multiplying unit.

Since the W₆₄ = e ^' = cos(πk/32) - jsin(πk/32) is a complex number, W₆₄ multiplication may be defined as non-trivial multiplication.

The non-trivial multiplying unit 700 is provided between the first R2BF operator 600 and the third delay commutator 800. The non-trivial multiplying unit 700 needs to independently perform multiplication for each path, the total four W₆₄ operators are included. Referring to FIG. 20, the non-trivial i j k multiplying unit 700 includes a W₆₄ operator 710, a W₆₄ operator 720, a W₆₄

operator 730, and a W₆₄' operator 740. The operators 710, 720, 730, and 740 have the same structure, except for the order of indexes generated. Since the data indexes do not overlap, there is no operator that can be shared.

For example, referring to FIG. 21, the W₆₄ operator 710 includes an index generator 712, a trigonometric function generator 714, and an actual multiplying unit 716. The W₆₄ operator 710 that is a non-trivial multiplying unit has a difference value of i according to an index of data that is processed in an MDC structure, and a proper value of i needs to be generated according to each data index. To do so, the index generator 712 is provided. A trigonometric function generator 714 is provided, which generates sin(i) and cos(i) according to the value of i that is generated by the index generator 712. The trigonometric function generator 714 may be implemented by using a ROM table. The trigonometric function generator 714 uses the value of i that receives from the index generator 712 and supplies cos(π i/32) and sin(πi/32) to the actual multiplying unit 716. The actual multiplying unit 716 includes multiplication and addition operations between a cos value, a sin value, a real part input value, and an imaginary part input value, as represented by the following Equation. [Equation 12]

Accordingly, the actual multiplying unit 716 includes four real number multipliers 716a, 716b, 716c, and 716d and two adders 716e and 716f (refer to FIG.22).

The FFT method according to the preferred embodiment of the present invention can be understood by those skilled in the art on the basis of the above description of the FFT apparatus, and thus the detailed description will be omitted.

Hereinafter, the above method and another method are compared on the basis of the hardware design result of the FFT apparatus according to the preferred embodiment of the present invention.

The hardware structure of the suggested FFT processor is designed using a Verilog HDL and the designed result is synthesized using a CMOS cell library of 0.18 μm. The synthesize result is represented by a gate count, which is shown by the following Table 2.

[Table 2]

For comparison with the FFT processor according to the present

3 invention, hardware of R2 SDF and R4MDC schemes are designed and synthesized, and the synthesized result is shown in the following Table 3. [Table 3]

According to the compared result of three types of design results, in the SISO-OFDM system that requires one data channel, R2³ SDF is most efficient.

Meanwhile, in order to implement a 4-chnnel MIMO-OFDM system, R2 SDF needs 4 processors. Accordingly, in terms of the final complexity of the FFT process in order to implement the 4-channel MIMO-OFDM system, the 4-chnnal MRMDC scheme is most preferable. The hardware complexity of the 4-channel MRMDC

3 scheme is reduced to 64% of the hardware complexity of the R2 SDF scheme requiring the four processors, and to 25% of the hardware complexity of the 4-channel R4MDC scheme.

Although the present invention has been described in connection with the exemplary embodiments and the accompanying drawings, the present invention is not limited to the above-described embodiments, and it will be apparent to those skilled in the art that various modifications and changes may be made thereto without departing from the scope and spirit of the invention. Therefore, it should be understood that the above embodiments are not limitative, but illustrative in all aspects. The scope of the present invention is defined by the appended claims rather than by the description preceding them, and all changes and modifications that fall within metes and bounds of the claims, or equivalents of such metes and bounds are therefore intended to be embraced by the claims.

The present invention can be applied to all radio communication systems, such as an IEEE 802. Hn WLAN system, and a 4G radio communication system, which uses a MIMO-OFDM. In recent years, since a radio communication system using an MIMO-OFDM system has been actively developed, it may be widely used.

Claims

[CLAIMS]

[Claim 1]

A fast Fourier transform (FFT) method for a 4X4 MIMO (Multiple Input Multiple Output)-OFDM (Orthogonal Frequency Division Multiplexing) WLAN system, comprising:

(a) a step of selecting an operation mode of a fast Fourier transform (FFT) or an inverse fast Fourier transform (IFFT), when 4-channel data is input;

(b) a step of sequentially distributing the 4-channel data during the operation mode selected in the step of (a) and performing delay commutation;

(c) a step of using a Radiχ-4 butterfly operation to perform addition and subtraction of the 4-channel data, on which delay commutation is performed through the step of (b) ;

(d) a trivial multiplication step of processing We multiplication independently existing for each data path with respect to the data, on which addition or subtraction are performed through the step of (c);

(e) a step of using a Radiχ-2 butterfly operation to perform addition and subtraction of the data, on which trivial multiplication is performed through the step of (d); and

(f) a non-trivial multiplication step of processing W^ multiplication independently existing for each data path with respect to the data, on which addition or subtraction are performed through the step of (e),

-j2?N wherein Ws and W₆4 satisfy N=8 and N=64 in W_N = e , respectively.

[Claim 2]

The fast Fourier transform method of claim 1, wherein the step of (d) includes a step of approximating a scaling factor as represented by the following Equation: 1/V2^ 0.7071 ^ 2 + 2 +

-4 -6

2 + 2 , and configuring the scaling factor as a combination of shift and addition operations.

[Claim 3]

The fast Fourier transform method of claim 1, wherein the step of (f) includes:

(fl) an index generation step of generating a value of i of W₆/ according to a data index;

(f2) a trigonometric function generation step of generating sin(i) and cos(i) according to the value of i; and

(f3) a step of performing actual non-trivial multiplication using a trigonometric function generated through the step of (fl).

[Claim 4]

A fast Fourier transform (FFT) apparatus for a 4X4 MIMO-OFDM WLAN system, comprising: an operation mode selector that selects an operation mode of a fast Fourier transform (FFT) or an inverse fast Fourier transform (IFFT), when A- channel data is input; a first delay commutator that sequentially distributes the 4-channel data to sequentially perform operations, performs a switching operation having 16, 32, and 48 delay symbols at the second, third, and fourth paths, respectively, and has 48, 32, and 16 delay symbols at the first, second, and third paths, respectively; a Radiχ-4 butterfly operator that performs addition or subtraction of the data that has passed the first delay commutator; a trivial multiplying unit that processes W₈ multiplication independently existing for each data path with respect to the data, on which the Radiχ-4 butterfly operation is performed; a Radiχ-2 butterfly operator that performs addition or subtraction of the data that has passed the trivial multiplying unit; a second delay commutator that arranges the data having passed the trivial multiplying unit according to a data distance required by the Radiχ-2 butterfly operator, performs a switching operation having 8 delay symbols at each of the second and fourth paths, and has 8 delay symbols at each of the first and third paths! and a non-trivial multiplying unit that processes W₆₄ multiplication independently existing for each data path with respect to the data that has passed the second delay commutator, wherein Ws and Wβ4 satisfy N=8 and N=64 in W_N = e , respectively.

[Claim 5]

The fast Fourier transform apparatus of claim 4, wherein the two Radiχ-4 butterfly operators and the four Radiχ-2 butterfly operators are provided. [Claim 6]

The fast Fourier transform apparatus of claim 4, further comprising: a third delay commutator that arranges the data having passed the non- trivial multiplying unit according to a data distance required by the Radiχ-4 butterfly operator, performs a switching operation having 2, 4, and 6 delay symbols at the second, third, and fourth paths, respectively, and has 6, 4, and 2 delay symbols at the first, second, and third paths, respectively. [Claim 7]

The fast Fourier transform apparatus of claim 4, wherein the two trivial multiplying units and one non-trivial multiplying unit are provided. [Claim 8]

The fast Fourier transform apparatus of claim 4, wherein the trivial multiplying unit that processes multiplication of

1 2 3

W₈ includes a W₈ multiplying unit, a Ws multiplying unit, and a W₈ multiplying unit , and

1 . . -1/2 the Ws multiplying unit includes two real number adders and two 2 operators. [Claim 9]

The fast Fourier transform apparatus of claim 8,

3 wherein the W₈ multiplying unit includes two real number adders, two 2

1/2 operators, and a sign shifter. [Claim 10]

The fast Fourier transform apparatus of claim 4, wherein the fast Fourier transform apparatus has an MDC (Multi-path Delay Commutator) pipe line structure of 64 points. [Claim 11]

The fast Fourier transform apparatus of claim 4, wherein the non-trivial multiplying unit includes: an index generator that generates a value of i of W^ according to a data index; and a trigonometric function generator that generates sin(i) and cos(i) according to the value of i generated by the index generator.