TW200915095A - Fast Fourier Transform (FFT) and inverse FFT (IFFT) device and method - Google Patents

Abstract

Fast Fourier Transform (FFT) and inverse FFT (IFFT) device and its method tare disclosed. By incorporating a retrenched 8-point FFT (R8-FFT) unit and a multiplication-after-write (MAW) scheme, the chip area can be reduced and computation speed is increased, so as to fulfill the needs of a multi-input multi-output (MIMO) orthogonal frequency-division multiplexing (OFDM) wireless communication system.

Description

200915095 l IX. Description of the invention: [Technical field to which the invention pertains] The present invention relates to a Fourier transform and its inverse conversion, and more particularly to a fast Fourier transform and its inverse conversion apparatus and method. [Prior Art] Fast Fourier Transform is a technique for analyzing time-varying signals. Simply put, Fast Fourier Transform (FFT) maps time domain signals to their frequency domain replicas, and inverse fast Fourier transform (IFFT) uses frequency domain signals. Maps to its time domain copy, which are mutually reversible. For an orthogonal frequency division multiplexing (OFDM), the IFFT/FFT module is an indispensable tool for processing modulation/demodulation to achieve efficient multicarrier transmission, such as wireless zones. The wireless local area network (802.11a) standard requires an IFFT/FFT module with high speed and instant processing capability, and which can combine high-data processing efficiency with a simple method. In addition, in some specific wireless communication systems, such as asymmetric digital subscriber line (ADSL), ultra-high-speed digital subscriber loop (VDSL) or digital audio and video broadcasting system (DAB/DVB-T), etc., by using IFFT/ The FFT module increases the bandwidth of the transmission or increases the efficiency of the transmission. The butterfly module is a commonly used method for implementing FFT/IFFT. It uses the method of multi-layer crossover operation to obtain the result of FFT/IFFT. The conventional butterfly module has the same number of inputs and outputs. As shown in Fig. 1, the FFT/IFFT butterfly module 1〇〇200915095 with base 8 has two multiplication units n〇 and 12〇, eight inputs χ[(1) to x[7] and eight rounds. γ[0] to γ[7] are used to calculate the Fourier transform matrix formed by the input to χ[7] by the disassembly method of the odd and even numbers to simultaneously generate eight corresponding outputs Υ[0] to Υ [7]. The Republic of China Patent No. 265503 proposes a "two-dimensional inverse = cosine transform | set" using a 矩阵-type matrix architecture and a pipeline-type multiplier architecture to reduce the wafer area by matrix disassembly, but still needs a quarter of a length The complex multiplication and the read-only memory storing the parameters, thus consuming a larger 曰a >} area' requires a longer computational bottleneck time, and can only be used on the inverse discrete cosine transform device. The Republic of China Patent No. 409212 proposes a "power sum: fast Fourier transform processor with a =," using a matrix of more than 4 points, and a core, and applying a parallel single delay feedback path (SDF) The structure, such as the parallel R22SDF, R23SDF and R24SDF architecture, only the complexity of the complex multiplication of the processor is high, so it requires a long calculation bottle, and in addition, using a complex multiplier with a read-only memory architecture requires p The larger the wafer area, and the processing rate (ρΓ〇_ίηέ her) is only, can not meet the needs of multiple input and multiple output systems. ~. The Republic of China Patent No. 418362 proposes a "fast Fourier transform device with a flat structure", which uses a parallel-type modified two-cosine transform (MDCT) and a modified discrete sine transform (MDST) function = the same method, wherein A MDCT/MDST module column is implemented in a time-returned architecture, which requires a large wafer area. The Republic of China Patent No. 522315 proposes a "discrete double-inverted conversion of 512 points by using the dispersion of the Hartley transform from 200915095 to calculate the discrete Fourier transform and its inverse transform." The processing rate is only R, which cannot meet the requirements of multiple rounds of the war. The Republic of China Patent No. 1224263 proposes an "Easy FFT/iyFT Processor", which uses a matrix architecture and a pipeline type multiplier to 16 The R2 SDF-type enhanced architecture is the basis for development to achieve fast, Fourier transforms of 32, 64, 128, and 256 points. However, the complexity of complex multiplication is high, and the processing rate is only 4 R, which cannot meet the requirements of multiple input systems. The Republic of China Patent Publication No. 200534121 proposes a "fast Fourier, conversion architecture and method" that uses a butterfly matrix type, thus consuming a large area of the slice on the memory and requiring a long computational bottleneck time' Its processing rate is only R, which cannot meet the needs of multi-input and multi-output systems. The Republic of China Patent Publication No. 20060107 proposes a "fast Fourier transform processor and its dynamic adjustment method and a fast Fourier transform algorithm for base number-8", which uses an 8-point matrix butterfly module architecture to repeat the same operation. The large wafer area requires a long computational bottleneck time and its processing rate is only R, which cannot meet the requirements of multiple input and multiple output systems. The Republic of China Patent Publication No. 200602902 proposes a "fast Fourier transform method" which still requires a long operation time and the processing rate is only R, which cannot meet the requirements of the MIMO system.

Wei-Hsin Chang and Truong Nguyen on IEEE Trans· on 7 200915095

"An OFDM-specified lossless FFT architecture" published in Circuit and System I, which implements a 64-point fast Fourier transform with the R22SDF architecture. It simplifies the bit hierarchy to obtain the minimum chip area design, but the complexity of complex multiplication is high. And the processing rate is only R, which cannot meet the requirements of multi-input and multi-output systems.

Chiu C., Wing Hui, Tion JD and McCanny JV, "A 64-point Fourier transform chip for video motion compensation using phase correlation", published in IEEE Journal of Solid-State Circuits, proposes a multi-delay rectification architecture with a base number of 4. (R4MDC), it makes the utilization of each component have a good performance in the 4x4 multi-input multi-output application, but it consumes a large wafer area, and the complexity of complex multiplication is high.

Haining Jiang, Hanwen Luo, Jifeng Tian and Wentao Song, "Design of an efficient FFT processor for OFDM systems" published in IEEE Trans, on Consumer Electronics, proposes a radix-4 multi-delay rectification architecture, due to the architecture will handle The parallel arrangement of cores leads to an increase in the required wafer area, while the system operating frequency is greater than the input data sampling frequency, which does not meet the low energy requirements.

Yunho Jung, Hongil Yoon and Jaeseok Kim, "New efficient FFT algorithm and pipeline implementation results for OFDM/DMT applications" published in IEEE Trans, on Consumer Electronics, proposes a base-four multi-delay rectification architecture by changing the architecture. The internal constant multiplication area is reduced, but the system operation 200915095 frequency is greater than the input data sampling frequency and does not meet the low energy requirements. K. Maharatna, E. Grass and U. Jagdhold, "A 64-point Fourier transform chip for high-speed wireless LAN application using OFDM", published in IEEE Journal of Solid-State Circuits, proposes a constant parallel multiplier architecture. The base--8 fast Fourier converter has a processing speed of 4.33R, but consumes a large wafer area, and the utilization of each module in 2x2 and 4x4 multiple input multi-output orthogonal multi-frequency system applications Lower. L. Jia, Y. Gao, J. Isoaho and H. Tenhunen, Proc. Eleventh Annu. IEEE Int. ASIC Conf., "A new VLSI-oriented FFT algorithm and implementation", proposes a traditional separation factor - 2/8 theory, but no implementation of the hardware architecture, if the equation is directly implemented in the hardware architecture, each butterfly architecture has a constant multiplication unit, which consumes a large wafer area.

Wen_Chang Yeh and Chein-Wei Jen, "High-speed and low-power split-radix FFT" published in IEEE Trans, on Signal Processing, proposes a traditional hardware architecture design based on the separation base-2/8 theory. However, there is one constant multiplication unit in each butterfly structure, which consumes a large wafer area, and because the processing rate is only R, it cannot meet the requirements of the multi-input and multi-output system, and the utilization rate of each component is also slightly lower. S. Bouguezel, MO Ahmad and Μ. NS Swamy's "A New Radix-2/8 FFT Algorithm for Length-q x 2m DFTs" published in IEEE Trans, on Circuits and Systems I, presents a 200915095 traditional separation The base-2/8 theory, but no implementation of the hardware architecture, if the equation is directly implemented in the hardware architecture, each butterfly architecture will have a constant multiplication unit, which consumes a larger wafer area. CT Lin, YC Yu and LD Van at the IEEE ISCAS2006 Conference, "A Low Power 64-Point FFT/IFFT Design for IEEE 802.11a wireless LAN Application", proposes a traditional separation base-2/8 theory, but The processing rate is only R, which can only be applied to a single input single output quadrature multi-frequency (SISO-OFDM) environment with low processing speed, and cannot be applied to applications of multiple input and multiple output systems. Li Jiansong's Master's thesis at the Datong Institute of Technology (2006) "Design and implementation of variable-length fast gourier transform processor", while revealing various FFT/IFFT conversion architectures, such as a single delayed feedback path (SDF), a single delay rectification path ( SDC) and Multi-Delay Rectifier Path (MDC) architectures, but these architectures are not capable of meeting both low die area, high efficiency, and multi-input multi-output system applications. Due to the traditional R22SDF and R23SDF architecture 64-point fast Fourier converter, the wireless communication system used in single input and single output, such as wireless local area network, is designed for streamlined and high efficiency, but it is energy-intensive and complex multiplication. High complexity, not suitable for multi-input and multi-output systems, while split-radix and high-radix fast Fourier transform theory can solve the complex multiplication problem, but high-order The number of multipliers in the base-type architecture has increased significantly, resulting in higher cost for the wafers' and the separation-based architecture does not currently have a highly utilized pipeline rack 200915095, making it compatible with multi-input, multi-round and profit-domain networks. ..., line-pass λ system, such as wireless zone, therefore, a fast Fourier transfer rate for multiple rounds of low wafer area.茱 conversion and its inverse conversion device and method are the content of the invention. The object of the invention is to have a high efficiency and a low : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : The fast Fourier transform of the slice area and the inverse of the H-type fast Fourier transform and the element, the _ input data generates a plurality of 第t茱 conversion modules according to the plurality of data containing-output data, each of the plural a first output multiplication unit, a number information, a multiplication module having a plurality of multiplicative μ (four) number information from the second output data having the position information, to: store the second _, its *= matrix The formula (4) body complex number έ < 固第-output data contains conflicting output data, the material, and after: the location information stores the conflict output resource according to the present invention: the multiplication module performs the operation. (4) Performing the first-L penalty speed Fourier transform and its inverse conversion method, the dust-blown butterfly operation to generate 200915095 multiple pieces of position information and number information based on the plurality of input data - the number of the first output data is not rushed ^, the round of the data '(C) according to the location information hall, and the plurality of first wheel data without the first multiplication operation, the first plurality of first outputs of the first multiplication operation The non-conflict person performs the second multiplication of the numbered information == the number of the third output data with the position information (four) and the fourth (four) second multiplication operation of the plurality of rounds of the poor material '(f) Step eggs) and (4) until

Each of the n materials undergoes the first or second multiplication operation, and (8) the H (d) the second and third data are used to generate the fast Fourier transform data of the plurality of input assets or the inverse conversion data thereof. The invention improves the hardware utilization by the simplified 8-point fast Fourier transform module, and utilizes the multiplication_after_write (MAW) machine rhyme operation _, and adopts the matrix type to construct the feedback path with the module. The forward rectification path architecture increases the processing rate to achieve the goal of the multi-output orthogonal multi-frequency wireless communication system with a minimum crystal = area. [Embodiment] The "Established 8-point fast Fourier transform module (R8_FFT) to reduce the complexity of complex multiplication" takes the N-point fast Fourier transform as an example. The conversion sequence can be expressed as 200915095 Z[k]= YiX[n]-Wjr Equation 1 where X[n] is the input data 'Z[k] is the round-off data, ^, and %, according to the theory of base 8, formula j can be rewritten as N is the %-turn factor Z[ s + Tt]= ^ /=0 τ~\ ^MT ' X{l-\- Mm\ Wfm Equation 2 ' T,8,s, detachable into two of them, k=s+Tt,n=1 +Mm, where N is equal to 64, t, l, and m are integers from 〇 to 7, so the fast Fourier expression of the 8th point is rewritten as ">〇y, y6 Λ w° w2 h ys

w'

Equation 3 puts Equation 3 to 18〇. Simplify with the excess of 9〇 to get 200915095 >〇' 1 0 0 y. 0 0 1 y. 0 0 ys 0 0 1 y2 0 0 η 0 0 0 γ6 0 1 0 Λ. 0 0 0 οΚο -旳~y%'ο (^〇+ χ4) + (χ2 + χ6)- (尤0+尤4)-(Χ2 +义6) (^0-Χ4)_ jXX2^X6) ^Χ0~Χ4) + Λχ2 -Χ6) (尤1 +A) + (X3 + Jf7) u'+a)-(x3 + a) {x' ~χ5)~ ΛΧ,-^ι) -(Λ,1 ~^s) + 7 (^3-^7). & 4 Then the upper half and the lower half are removed from the 4th ship. The formula is: formula >0/1 h/3 where = gKFft)+Hkfft), G2( FFT) + ^2(FFT) >>6 /7 G\(FFT)= ^Χ〇+Χ^ + (Χ2+Χ6) L('〇"Ά)-·/(义2 _尤6 )_G2(FFT) (Xq +X4)-(X2 +^e) ^0-^4) + 7(^2-^6), ^ΐ(«τ) = [ι rg1]· "2( Print r) = - household [l ej_ '^\(FFT) - H^FFTy -^2(FFT) ~H2(FFT) Equation 5a Equation 5a (Xl +X5)-(X^+X7) _(Χ{ -Χ5)+ΛΧ3~Χ7)_

According to formulas 6a to 6d, R8-FJFT can be obtained. Equation 6a Equation 6b Equation 6c Equation 6d In this nose-feeding process, the above-mentioned 14 200915095 half and bottom half dismantling methods replace the conventional odd-numbers disassembly method decomposition formula 4 The matrix shown to simplify the single multiplication number required. ^ Figure 2 is a R8-FFT based on the output reordering separation base _2 / 8 theory of the B butterfly module 200, which has a multiplication unit 21 〇, eight inputs and four outputs to calculate 8 input data乂[〇]至χ[7] For example, 'To enter the data X[〇g Χ[7] full input requires eight clock cycles, the L-Butterfly module 200 operates in two clock cycles, To generate the output Υ[2], γ [6], γ[3] and Υ[7], and the Υ[0], γ [4], respectively, corresponding to the rounded data Χ[〇] to Χ[7], γ(1) and γ[5], the utilization rate of the L-shaped butterfly module 200 is two-eighth. In contrast, the butterfly module shown in Fig. i is operated in one clock cycle by two multiplication units Π0 and 120. In order to simultaneously generate the output data γ[0] to Υ[7] of the corresponding input data X[〇] to X[7], the utilization rate of the butterfly module 1〇〇 is one eighth, so the l-type butterfly module The 200 is at least twice as efficient as the conventional butterfly module 100. In addition, the number of multiplying units in the 'L-type butterfly module 200 is only half that of the conventional butterfly module 1' effectively reduces the required wafer area. 3 is a first embodiment of the FFT/IFFT device of the present invention, a discrete block 2/8 multi-delay feedback path using a serial blockwise architecture (redix-2/8 multiple-path delay) The feedback module (R28MDF) 300 includes an input module 310 having input groups 318 and 319. The input groups 318 and 319 respectively include a plurality of input units 312 for receiving a plurality of input data, and an R8-FFT 320 generates a device according to the input data. The output structure including the location information and the number information, the specific structure of the R8-FFT 320 is the L-shaped butterfly module of FIG. 2 2 0 0 ' -~~ control module 15 200915095

The 350 is used to control the operation order of the R8-FFT 320. The multiplication module 330 has a plurality of multiplication units for multiplying the output data of the R8-FFT 320, and a matrix memory module 340 stores the information according to the location information. As a result of the operation of the multiplication module 330, the matrix memory module 340 adopts a feedback path architecture for feeding back the stored data to the R8-FFT 320 to generate an FFT corresponding to the input data. IFFT data output. In the present embodiment, the schematic diagrams of the input unit 312 and the multiplication module 330 are as shown in Figs. 4 and 5, respectively. Referring to FIG. 4, the input unit 312 includes an AND gate 316 that generates a shift signal Ss according to a gate control signal and a clock, and a register 314 that shifts the input data according to the displacement signal. Referring to FIG. 5 and FIG. 3, the multiplication module 330 includes a multiplexer 334, a plurality of multiplication units 332, and a demultiplexer 336. The multiplexer 334 passes the r8_fft 32〇 output data to the corresponding multiplication according to the number information. The unit 332 performs a corresponding multiplication operation, and the result of the multiplication=element 332 operation is output from the Y0 to Y4 by the demultiplexer 336, and is stored in the matrix memory module 340 according to the position information. In an embodiment, The multiplication unit 332 includes an addition shifter, and uses a fixed displacement line with addition = to achieve multiplication, thereby reducing the complexity of the multiplication operation, and without adding another-read only memory, further reducing the required Wafer area. -a,6 is the operation timing diagram of Figure 3. The operation time of 64 feet and the foot of the pull point (4) requires 64 clocks, including two = phase and MS2 and two output periods (10) and (10): respectively It is a timing chart of the multiplication period and the output period in Fig. 6. ... Figure 7 and Figure 3, the input module 31A includes two maps 16 200915095 319 'Input groups 318 and 319 contain 64 input units 312, and 64 input units 312 form an 8x8 matrix from χ〇〇 to χ 77 The 64-point data χ[〇] to Χ[63] are sequentially input to χ〇〇 to Xu. In the first clock cycle, the data Χ[56] is input to χ7〇, and the R8_FFT 320 is based on the input data. • For example, the data X[0] to X[7] that have been input to Xoo to X〇7 are subjected to the L-shaped butterfly operation to produce the output data γ〇〇(0), γ1〇(0), 丫4〇(〇 And γ5〇(〇), wherein ab in Yab(c) represents position information (a, b) and e represents number information, and then the multiplication module 330 selects a corresponding multiplication unit pair R8-FFT 320 according to the number information. The output data is subjected to a corresponding multiplication operation, and the difference result is stored in the corresponding position in the matrix memory module 34A according to the position information. In the second clock cycle, data χ[57] is input to X7i, and r8_fft 320 performs L-shaped butterfly operation based on the input data, such as data χ[〇] to xm that has been input to χ(10) to χ〇7. , generating an output signal γ2. (9), Υ3〇(〇), 丫6〇(0), and Υ^Ο), multiplied by the multiplication unit selected by the numbering information== after the multiplication module 33, and the result is stored in the matrix memory according to the position information. The body module 34 wipes. Similarly, in the 3rd to Μ = clock cycle, 'note that according to the input to the input module training, in the 6th clock cycle, the deer arrives: output bead material ¥22 (4) And the number information of Y62(4) conflicts with each other, and the c multiplication unit, for example, the fourth multiplication unit, forms a collision 2 gas (4)'. At this time, in the 6th clock cycle, the following:: The conflicting output data Y2: i and the conflict rounding data (10) according to the bit, the corresponding position 17 200915095 (6, 2) in the sub-array redundancy module 340 so that the fourth multiplication unit is not used subsequently In the clock cycle, the large output bead γ62(4) is supplied to the fourth multiplication unit for multiplication, for example, the conflict output data is supplied to the fourth multiplication unit in the eighth β cycle, and (4) is multiplied. At this time, it is represented by R64 (4), and will be, , and . If it is back to the matrix memory module (10) according to the location information (6, 2). Similarly, 'the conflicting output data in the ninth clock cycle\ (the sentence is multiplied in the 12th clock cycle, and the conflict output data Υ64(8) and Υ74_ in the 1st () clock cycle are respectively The η and f 13 clock cycles are multiplied, so the first to the 16th clock cycles form the multiplication period _ in Fig. 6. Referring to Fig. 8 and Fig. 3, in the first clock cycle '# The material X[8] is input to Χι., and the _ attached 32 () is based on the data of the information retrieved from the moment memory module 340. [The butterfly generates the data of 2°°, 21, 24, and 250 output. In the 18th clock cycle, the data χ[9] is input to &, R8_FFT32(), based on the data of the data fed back from the matrix memory module 340, the L-type FFT is generated. The IFFT data Ζ〇ι, &, B 41 and & output, in the 19th to 32th clock cycles, the FT32G is based on the moment: the data retrieved from the group 340 is used to perform the L-shaped butterfly. In the calculation, the output time/month OS1, similarly, the 33rd to 48th and 49th to 64th clock cycles respectively form the 2nd MS2 of the graph and the output period 0S2. In this embodiment, the method module 33 adopts a parallel feedback loop, which includes nine multiplication units respectively corresponding to the numbering signal ~8, and each of the current 18 18150150 law units corresponds to different multiplication operations, five The input end respectively receives the output data of the R8_FFT 320 and the conflicting output data stored in the matrix memory module 340 and the five output terminals Y0 to Υ4 respectively output the results of the multiplication by the multiplication unit, and store the result according to the location information. The multiplication unit of the matrix memory module /, corresponding to the description ϊ 0, represents X1, and the direct output does not cause a collision. This first write and multiplication mechanism can reduce the delay time of the operation, thereby increasing the processing rate. The module 310 has two input groups 318 and 319, and includes two multiplication periods MSI and MS2 and two output periods OS1 and 〇S2 'display R28MDF 300 processing rate up to 2R' in 64 clock cycles. 2x2 multi-input multi-output orthogonal multi-frequency wireless local area network. In addition, 'R8-FFT 320 and matrix are used regardless of the multiplication period or output period r8_fft 320 and matrix memory module 340 are used. The utilization rate of the memory module 340 is up to 1〇〇〇/., effectively improving the utilization rate of each module. Fig. 9 is a second embodiment of the FFT/IFFT device of the present invention, and the separation using the serial module architecture The radix-2/8 multiple delay rectification path (RXMDC) 400 includes an input floor group 410 having input groups 460 to 466. The input groups 460 to 466 respectively include a plurality of input units 412 for Receiving a plurality of input data, and a switching unit 414 is configured to switch the plurality of input data, and an R8_pFT 4 2 0 generates output data including location information and number information according to the input data outputted after switching by the switching unit, The multiplication module 430 has a plurality of multiplying units 432 for performing 19 200915095 multiplication operations on the output data of the R8-FFT 420, and a matrix memory module 44 is subjected to the operation of the multiplication module according to the position information, and _ R8_FFT 45G generates (4) the FFT/IFFT data output of the data according to (10) stored in the matrix memory module 440, wherein the specific structure of the R8 FFT 42〇 and 45〇 is as shown in FIG. · L-shaped butterfly module. In this embodiment, the multiplication module 430 uses a parallel feedback path to receive the data provided by the matrix memory module 440 or store the data in the matrix memory module 440, and the input unit 412 and the multiplication mode The architecture of group 43() is the same as that shown in Figures 4 and 5. In an embodiment, the multiplication single S 432 includes a = method shifter 'utilizing a fixed displacement line with an adder to achieve a multiplication operation, thereby reducing the complexity of multiplication, and without adding another read only memory' further Reduce the required wafer area. FIG. 10 is a timing chart of the operation of FIG. 9. Referring to FIG. 9 and FIG. 1 , taking the 64-point FFT/IFFT as an example, a 64-point fft/ifft operation time requires 64 clocks, including four multiplication periods, Service, Lake and Li, and four output periods (10), 〇S2, 〇s3, and 〇S4, the timing diagrams of the multiplication period and the output period, and the operations between the modules are as shown in Fig. 7 and Fig. 8 respectively. The difference of the third is that the matrix memory 44 〇 uses the forward rectification path (four) to construct its data directly to the R8-FFT 450 without feeding back to the R8_FFT 42G. In the 16-cycle period of the first group, the R8-FFT42〇 and the multiplication template 43〇 switch the 4 L-type butterfly operation and the multiplication operation according to the switching unit 414, and store the operation result in the matrix memory model. In group 440, a multiplication period MS1 is formed. In the first set of 16 clock cycles 472, R8_FFT 45〇 according to the matrix 20 200915095

The data remaining in the memory module 440 is subjected to L FF:/IFF7 material rounding 'simultaneous_·and multiplication=step, and then the input data is calculated to form an output time period, similarly The third group and the fourth group of 16 = and the formation of the round-out period (10) and the multiplication time #_ = the out-of-time period (10) and the multiplication period Cong, and the output _qS4 is formed in the subsequent i6 clock cycles 478. In this implementation, the multiply touch 43〇 uses a parallel-type feedback circuit, so that the multiplication module gamma has a mechanism of first writing and then multiplying to improve the processing speed. Since the input module 41〇 has four input groups 46〇 to 466, and includes four multiplication periods in the 64 clock cycles to Cong and four output periods OS1 to OS4 'display R28MDC 4〇〇 processing rate can be Up to 4R' is suitable for 4x4 multi-wheeled multi-output quadrature multi-frequency wireless local area network. In addition, R8-FFT 420 and 450, multiplication module 43〇, and matrix memory are used regardless of the multiplication period or output period R8_FFT42〇 and 45〇, multiplication module 430, and matrix memory module 44〇. The utilization rate of the module 44〇 is 100%, which effectively improves the utilization rate of each module. Furthermore, the R28MDC architecture 400 uses a high-speed pipeline processor architecture, and performs multiplication and output periods simultaneously in the FFT/IFFT migration process, so the processing power per unit time is doubled to achieve high utilization. OBJECTIVE FIG. 11 is a comparison table of the 64-point FFT/IFFT conversion performance of the R28MDF of the present invention and a conventional technique applied in a 2x2 multiple-input multiple-output orthogonal multi-frequency system, wherein the conventional R2MDC has only theoretically no practical. Frame 21 200915095 structure, if directly based on its theory to achieve the architecture, then four read-only memory is required. As can be seen from Figure 11, the R28MDF of the present invention considers the complexity of the multiplication module, the system operating frequency, the wafer area, After the butterfly module utilization rate and processing speed, the architecture with the highest efficiency and area efficiency is adopted. 12 is a comparison table of 64-point FFT/IFFT conversion performance of the R28MDC of the present invention and a conventional technique applied in a 4×4 multiple-input multiple-output orthogonal multi-frequency system. As shown in FIG. 12, the R28MDC module utilization rate of the present invention is shown in FIG. The architecture with the highest and smallest wafer area. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a schematic view of a conventional butterfly module; FIG. 2 is a schematic view of an L-shaped butterfly module of the present invention; FIG. 3 is a schematic view of a first embodiment of an FFT/IFFT device of the present invention; 4 is a schematic diagram of the input unit in FIG. 3; FIG. 5 is a schematic diagram of the multiplication module in FIG. 3; FIG. 6 is an operation timing diagram of FIG. 3; FIG. 7 is a timing chart of the multiplication period in FIG. FIG. 9 is a schematic diagram of a second embodiment of the FFT/IFFT apparatus of the present invention, FIG. 10 is an operation timing diagram of FIG. 9; FIG. 11 is a R28MDF of the present invention and a conventional technique applied to 2×2 multiple inputs. In a multi-output orthogonal multi-frequency system, 64 points; FFT/IFFT conversion performance ratio 22 200915095; and FIG. 12 is a R28MDC of the present invention and a conventional technique applied in a 4x4 multiple input multiple output orthogonal multi-frequency system, 64 Point FFT/IFFT conversion performance comparison table. [Main component symbol description] 100 Butterfly module 110 Multiplication unit 120 Multiplication unit 200 L-type butterfly module 210 Multiplication unit 300 Separation base-2/8 multi-delay feedback path 310 Input module 312 Input unit 314 Register 316 and Gate 318 Input Group 319 Input Group

320 R8-FFT 330 Multiplication Module 332 Multiplication Unit 334 Multiplexer 336 Demultiplexer 340 Matrix Memory Module 23 200915095 350 Control Module 400 Separation Base-2/8 Multi-Delay Rectifier Path 410 Input Module 412 Input Unit 414 Switching Unit 420 R8-FFT 430 Multiplication Module 432 Multiplication Unit 440 Matrix Memory Module 450 R8-FFT 460-466 Input Group 470-478 16 Clock Cycles 24

Claims (1)

200915095 X. The scope of application for patents·· ^Transfer type ^Four Fourier transform and its inverse conversion device, including: Input data; ] Early 70' to receive a plurality of streamlined 8-point fast Fourier transform modules into the data to generate complex numbers The first-output data, each!;::: one: the data contains a position, the message and the 'number of assets t, the second group, the group' has a plurality of multiplication units, according to the number information of the plurality of materials from the plural The multiplication unit 3' ς 彳 运 运 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生 产生In the cycle, if the plurality of first conflicting outputs are output, the translation method outputs data, and the multiplication module is provided in the subsequent clock cycle to perform the operation. 2 as requested! The fast Fourier transform and its control module are used to control and set the order of operations. The fast Fourier transform and its inverse conversion device in the 8-bit fast Fourier transform single, the array memory 2: having a feedback path structure to feedback the moment Fourier transform two::: second output The data is sent to the reduced 8-point fast conversion, and the fast Fourier 25 200915095 leaf conversion data or its inverse conversion data corresponding to the plurality of input data is generated. Including the fast Fourier transform of item 1 and its inverse conversion device, the memory-mode continuous 8-point fast Fourier transform module switches the fast Fourier transform of the item 4 in the matrix and its inverse conversion device, and the complex rib formation The structure of the front rectification path to provide the fast output of the second output data to the second streamlined 8-point fast-transfer leaf transfer group or its inverse conversion of several rounds including the fast Fourier of the item 1. The conversion and its reverse conversion device, in which the soap element is replaced in the input module, is used for data to the reduced 8-point fast Fourier transform unit.... Each element 1 speed Fourier transform and its inverse conversion The device, according to a closed-loop control signal and a time-shift signal, shifts the plurality of input data according to the 5 green shift signal. The fast Fourier transform and the inverse conversion device of the axe/, item 1 Group / / month ο · point fast Fourier transform module includes an L-shaped butterfly speed Fourier transform and its inverse conversion split in an L-shaped butterfly mode, the upper half and the lower main 1 input and four outputs ' Take The matrix operation after the +4 disassembly. 10. The fast Fourier transform and inverse conversion device of the item 1 is 26, 200915095 2== The group has a parallel feedback path structure to access the matrix. === leaf transformation and its inverse conversion device, steps: (4) Fourier transform and its inverse conversion method, including the following: 亍 L-shaped butterfly operation, according to the plurality of position information and number information, the first number = birth, the plural The first multiplication operation of the number information=person number information in the first output data to generate a plurality of second output data having 5 hai position information; the location # storing the second output data and not The plurality of first-output data of the multiplication operation; ()=the non-Hai-multiplication operation of the plurality of first-output data, the number information does not conflict, and the second=-method corresponding to the number information generates a plurality of The third output asset (4) of the location information stores the third output f material and the plurality of first rounds of data not subjected to the second multiplication according to the location information; (0 repeating steps (d) and (4) until the plurality of An output data is subjected to the first or second multiplication operation; and (g) performing a second L-type butterfly operation 'generating the fast Fourier transform data of the plurality of input data according to the second and third data or inverse conversion data thereof ' 27 200915095 13. The fast method of claim 12 further includes the feedback of the second and third indirect conversion and its inverse conversion butterfly operation. · As requested in item 12, the fast Fourier transform method and the inverse Fourier transform and its inverse conversion L-shaped butterfly operation. Output the material to perform the second 15. The fast method of claim 12, including switching The plurality of input data/input and/or inverse conversion operations. Into the first L-type butterfly 16. As the fast method of the item 12, the current 笫-_ ν, the transformation and the inverse conversion of the square part of the I matrix operation t-butter operation including the upper half And the second half of the second method of the 1i conversion and its inverse conversion and the first multiplication method including the displacement addition operation. 28