CN102339272A - Split base-2/8 fast Fourier transform device and method - Google Patents

Abstract

The invention relates to an SR-2/8FFT device, which comprises a memory, an SRFFT processor and a control unit. The control unit comprises an input control block, an SRFFT control block and an output control block. The input control block determines a first sequence and loads the input data into the corresponding memory banks according to the first sequence, so that the SRFFT processor can simultaneously retrieve the data from the memory banks in a single clock cycle. The SRFFT control block determines a decomposition structure of the 2M-point FFT and controls the SRFFT processor to repeatedly execute butterfly computation along the decomposition structure. The input data order of each butterfly calculation conforms to the first order. The SRFFT control block controls the output result after each butterfly calculation to be written back to the memory bank corresponding to the input data. The output control block determines a second sequence and controls the output result to be output as output data according to the second sequence.

Description

Division radix-2/8 fast fourier transform device and method

Technical field

The relevant a kind of division radix of the present invention (split-radix, SR)-2/8 fast fourier transform (Fast FourierTransform, FFT) device and method, and particularly relevant a kind of simple and effective SR-2/8FFT device and method.

Background technology

(Fast Fourier Transform FFT) is common in the real-time application of digital signal processing fast fourier transform.According to European digital audio-video broadcast standard (DVB-T/DAB); Orthodoxy Frequency Division Multiplex (OrthogonalFrequency Division Multiplexer; OFDM) system is widely used, and exclusive FFT/IFFT processing unit is suitable for reaching the target of high frequency range especially for ofdm system and digital communication.

As everyone knows, in fft algorithm, compared to radix (radix)-4FFT, the division radix (split-radix, SR)-2/8FFT can save about multiplying more than 1/3.SR-2/8FFT is shown in the expression formula of following even number item FFT and odd term FFT, and please with reference to Fig. 6 and Fig. 7, Fig. 6 illustrates the synoptic diagram that time SR-8 butterfly computing falls in frequency, and Fig. 7 illustrates the time and falls the synoptic diagram of time SR-8 butterfly computing.

$X\left(2k\right)=\underset{n=0}{\overset{N/2-1}{\mathrm{\Σ}}}(x\left(n\right)+x(n+\frac{N}{2}))W_{N/2}^{\mathrm{nk}}$

$\begin{array}{c}\mathrm{where}{W}_{N/2}=e^{-\mathrm{<figure-callout\; id="2"\; label="j"\; filenames="HSA00000204710700012.png,HSA00000204710700021.png"\; state="\{\{state\}\}">j</figure-callout>}\frac{2\pi }{N?2}}\mathrm{andk}=\mathrm{0,1,2},...,(N/2)-1\\ \mathrm{And}\end{array}$ (even items FFT)

$X(8k+l)=\underset{n=0}{\overset{N/8-1}{\mathrm{\&Sigma;}}}\left((x\left(n\right)+x(n+\frac{2N}{8})W_4^l+x(n+\frac{4N}{8})W_4^{21}+x(n+\frac{6N}{8})W_4^{-l})\right)$

$+(x(n+\frac{N}{8})+x(n+\frac{3N}{8})W_4^l+x(n+\frac{5N}{8})W_4^{21}+x(n+\frac{7N}{8})W_4^{-l})W_8^{-l})W_N^{\mathrm{nl}}{W}_{N/8}^{\mathrm{nk}}$

where? k = 0,1,2, ..., (N / 8)-1andl = 1,3,5,7 (odd items FFT)

Therefore, SR-2/8FFT can more effectively utilize resource or time.Yet the irregular decomposition framework of SR-2/8FFT makes it be difficult to realize with hardware, is suitable for realizing with software and be regarded as.

Lift the SR-2/4FFT algorithm is that example is done explanation at present.The butterfly of SR-2/4FFT and radix-4FFF (butterfly) processor has 4 inputs and 4 outputs.Corresponding to a fixing input clock pulse and a limited hardware resource, the data access between storer and butterfly processor must be fast as much as possible.Four inputs reading and write the butterfly processor of SR-2/4FFT simultaneously can obtain the fastest FFT speed, i.e. each butterfly computing only expends the 1 clock pulse cycle (clock cycle).

Suppose that storer comprises 4 thesauruss (memory bank), then the time of radix-4FFT processor when handling 16 input data falls time that (decimation in time, DIT) the data list entries that calculates of radix-4 butterfly is as shown in table 1.

Table 1

In table 1, before stage 1 beginning, data 0～data 3 are placed in thesaurus 0, and data 8～data 11 are placed in thesaurus 1, and data 4～data 7 are placed in thesaurus 2, and data 12～data 15 are placed in thesaurus 3.Therefore, in the stage 1,4 inputs of radix-4 butterfly processor can be in while in single clock pulse cycle reading of data, for example (0,8,4,12).Yet in the stage 2, radix-4 butterfly processor 4 clock pulse cycles of needs could be from memory read data, for example (0,2,1,3).Therefore, the arithmetic speed of whole FFT reduces, and causes the efficient of total system not good.

Summary of the invention

The purpose of this invention is to provide a kind of division radix-2/8 fast fourier transform device and method; Utilize memory management to make division radix fast fourier transform processor to capture/to write many data to storer simultaneously in the single clock pulse cycle; And utilize regular decomposition framework, make division radix fast fourier transform processor can use low-cost hardware to realize.

According to a first aspect of the invention, propose a kind of division radix (SR)-2/8 fast fourier transform (FFT) device, comprise a storer, division radix fast fourier transform (SRFFT) processor and a control module.Storer comprises a plurality of thesauruss, and in order to receive 2 ^MPen input data, each data has an original address, and M is a positive integer.The SRFFT processor falls time (DIT) SR butterfly in order to the time of carrying out and calculates.Control module comprises an input control block, SRFFT control block and an output control block.Input control block is in order to determine one first order according to the number of these thesauruss and the reverse address, position of these original addresss; And in order to control store according in first order the thesaurus that these input data load are corresponding, make the SRFFT processor can single clock pulse in the cycle from these thesauruss acquisition data simultaneously.SRFFT control block in order to determine corresponding this 2 ^M1 of pen input data ^MThe decomposition framework of point FFT, and control SRFFT processor repeats butterfly calculating along decomposing framework.Wherein the input data sequence of butterfly calculating each time meets first order.SRFFT control block is also write and is fed back into the pairing thesaurus of data in order to control output result after butterfly is calculated each time.Output control block is in order to after calculating completion when DIT SR butterfly, according to the number and 2 of these thesauruss ^MThe original address of output data determines one second order, and and said these output result of writing back and be stored in said these thesauruss in order to control be output as 2 according to second order ^MOutput data, 2 ^MCorresponding in regular turn 2 of first order that meets of the output result that output data comprises ^MPen input data.

According to a second aspect of the invention; A kind of division radix (SR)-2/8 fast fourier transform (FFT) method is proposed; Be applied to a SR-2/8FFT device, the SR-2/8FFT device comprises a storer, division radix fast fourier transform (SRFFT) processor and a control module.Storer comprises a plurality of thesauruss.The SRFFT processor falls time (DIT) SR butterfly in order to the time of carrying out and calculates.Control module comprises an input control block, SRFFT control block and an output control block.This SR-2/8FFT method comprises the following steps.Storer receives 2 ^MPen input data, each data has an original address, and M is a positive integer.Input control block determines one first order according to the number of these thesauruss and the reverse address, position of these original addresss.This storer of input control block control is according in first order these thesauruss that these input data load are corresponding, make the SRFFT processor can single clock pulse in the cycle from these thesauruss acquisition data simultaneously.SRFFT control block determining corresponding this 2 ^M1 of pen input data ^MThe decomposition framework of point FFT, and control SRFFT processor repeats butterfly and calculate along decomposing framework, wherein the input data sequence calculated of butterfly meets first order each time.SRFFT control block is controlled output result after butterfly is calculated each time and is write and be fed back into the pairing thesaurus of data.After DIT SR butterfly was calculated completion, output control block was according to the number and 2 of these thesauruss ^MThe original address of output data determines one second order, and and these output result of writing back and be stored in these thesauruss in order to control be output as 2 according to second order ^MOutput data, 2 ^MCorresponding in regular turn 2 of first order that meets of the output result that output data comprises ^MPen input data.

Useful technique effect of the present invention is: SR-2/8FFT device and method of the present invention; Utilize simple and effective memory management method; In the thesaurus of input data according to the certain order pseudostatic ram; Make the SRFFT processor can single clock pulse in the cycle simultaneously to many data of storer acquisition, so need not adopt than storer (memory) expensive register (register) storage data.In addition, the present invention also utilizes finite state machine to realize the rule of FFT is decomposed framework, makes the SRFFT processor can use low-cost hardware to realize.Therefore, SR-2/8FFT device and method of the present invention has high-level efficiency and advantage cheaply.

Description of drawings

For there is better understanding above-mentioned and other aspect of the present invention, hereinafter is special lifts preferred embodiment, and conjunction with figs. is elaborated, wherein:

Fig. 1 illustrates the SR-2/8FFT schematic representation of apparatus according to preferred embodiment of the present invention.

Fig. 2 illustrates the synoptic diagram according to the partial arithmetic flow process of first order of preferred embodiment of the present invention.

Fig. 3 is the synoptic diagram that decomposes framework according to 16 SR-2/8FFT of preferred embodiment of the present invention.

Fig. 4 A～Fig. 4 F illustrates according to the finite state machine that utilizes of preferred embodiment of the present invention and carries out the process flow diagram that SR-2/8FFT decomposes framework.

Fig. 5 illustrates the synoptic diagram according to the partial arithmetic flow process of second order of preferred embodiment of the present invention.

Fig. 6 illustrates the synoptic diagram that time SR-8 butterfly computing falls in frequency.

Fig. 7 illustrates the time and falls the synoptic diagram of time SR-8 butterfly computing.

Embodiment

The present invention proposes a kind of division radix (split-radix; SR)-2/8 fast fourier transform (Fast FourierTransform; FFT) device and method; Utilize memory management to make division radix fast fourier transform processor to capture/to write many data to storer simultaneously, and utilize the decomposition framework of rule, make division radix fast fourier transform processor can use low-cost hardware to realize at single clock pulse cycle (clock cycle).

Please with reference to Fig. 1, it illustrates the SR-2/8FFT schematic representation of apparatus according to preferred embodiment of the present invention.SR-2/8FFT device 100 comprises a storer 110, a SRFFT processor 120 and a control module 130.Storer 110 comprises a plurality of thesauruss (memory bank), and in order to receive 2 ^MPen input data, each input data has an original address, and M is a positive integer.Consider cost and efficient, the storer 110 in this preferred embodiment comprises 8 thesauruss at the most.SRFFT processor 120 is in order to fall time (decimation in time, DIT) SR butterfly calculating (butterfly computation) from storer 110 reading of data with the time of carrying out.

Control module 130 comprises an input control block 140, SRFFT control block 150 and an output control block 160.The number and 2 of the thesaurus that input control block 140 is comprised according to storer 110 ^MReverse (bit-reversed) address, position of the original address of pen input data determines one first order.Then, input control block 140 control stores 110 are complied with first order with 2 ^MIn a plurality of thesauruss of pen input data load corresponding to first order, make SRFFT processor 120 when the butterfly that carries out each stage is calculated all can single clock pulse in the cycle from thesaurus acquisition data simultaneously.Wherein, each input data is obtained by a round values that reverse address value is got its quotient divided by the thesaurus number of importing data in the address of the thesaurus of correspondence.

Corresponding to 2 ^MPen input data, SRFFT processor 120 will carry out 1 ^MPoint FFT computing, thus SRFFT control block 150 can decision this 2 ^MThe decomposition framework of point FFT.SRFFT control block 150 is with 2 ^MPoint FFT obtains one according to the not homoimerous butterfly calculating decomposition of M stage and decomposes execution order; And control SRFFT processor 120 is carried out butterfly calculating along decomposing execution order; Wherein the not homoimerous butterfly calculating of each stage possibly be repeated to carry out, and input data fit first order of the feed-in of butterfly calculating each time input end.

When SRFFT processor 120 performed butterflies are calculated as the calculating of SR-8 butterfly; SRFFT control block 150 can produce 4 twiddle factors (twiddle factor) and calculate to offer the SR-8 butterfly, and 4 inputs in end that make the SR-8 butterfly calculate are rotated respectively and reach special angle.These 4 twiddle factors for example are W _1/N, W _5/N, W _3/NAnd W _7/N, wherein

Butterfly each time calculate accomplish after, SRFFT control block 150 is controlled output result after butterfly is calculated each time and is write and be fed back into the pairing thesaurus of data.

When SRFFT processor 120 is accomplished after DIT SR butterfly calculates along decomposing execution order, the number and 2 of the thesaurus that output control block 160 is comprised according to storer 110 ^MThe original address of output data determines one second order.Then, 160 controls of output control block write back and are stored in each interior output result of a plurality of thesauruss and are output as 2 according to second order ^MOutput data, these are 2 years old ^MCorresponding in regular turn 2 of first order that meets of the output result that output data comprises ^MPen input data.Wherein, each output result round values of getting its quotient by the original address value of the output data of correspondence divided by the thesaurus number in the address of the thesaurus that writes back and store obtains.

Next lift 16 (M=4) pen input data, and storer 110 to comprise 8 thesauruss be that example is done explanation, yet be not limited to this.Suppose that these 16 input data are x [0]～x [15], it (is A3～A0) that each data comprises original address A [3: 0].Suppose that again these 8 thesauruss are b0～b7, corresponding to 16 input data, each thesaurus comprises 2 address a0～a1 to store the input data.Input control block 140 is according to the thesaurus number 8 of storer 110 and the reverse address decision in position first order as shown in table 2 of 16 original addresss of importing data.Wherein, each input data is obtained by a round values that reverse address value is got its quotient divided by the thesaurus number of importing data in the address of the thesaurus of correspondence.Please cooperate with reference to Fig. 2, it illustrates the synoptic diagram according to the partial arithmetic flow process of first order of preferred embodiment of the present invention.Wherein,, carry out the computing of XOR (XOR) at a distance from 3 reverse positions, again the XOR result is multiplied by 2 power power, and totalling draws the thesaurus that will load so get whenever based on 8 thesauruss.

Table 2

Corresponding to 16 input data, SRFFT processor 120 will be carried out one 16 FFT computings, so SRFFT control block 150 can determine the decomposition framework of these 16 FFT.Please with reference to Fig. 3, it shows the synoptic diagram that decomposes framework according to 16 SR-2/8FFT of preferred embodiment of the present invention.SRFFT control block 150 obtains one with 16 FFT according to the not homoimerous butterfly calculating decomposition of 4 stages and decomposes execution order (shown in the arrow among Fig. 3).SRFFT control block 150 control SRFFT processors 120 are carried out butterfly calculating along decomposing execution order.SRFFT control block 150 can constitute by a finite state machine (finite state machine); Finite state machine writes down a plurality of current states; Each current state comprises a plurality of variablees, and for example stage S, the expression butterfly butterfly of block size BS, expression stage S of data number of calculating home position BP, the every phase process of expression of starting position is calculated between the two adjacent input end samples apart from SS, and previous state LS.Wherein, butterfly calculate the input end sample (#0, #1, #2, #3 ..., memory read fetch bit #7) is changed to: will (BP, BP+SS, BP+SS * 2, BP+SS * 3 ..., BP+SS * 7) via first order shown in the table 2 change.Finite state machine can cooperate a case pointer (state pointer) to realize by a temporary file (register file) in fact.Current state of every storage, case pointer adds 1; Previous state of every recovery (restore), case pointer subtracts 1.

Please with reference to Fig. 4 A～Fig. 4 F, it illustrates according to the finite state machine that utilizes of preferred embodiment of the present invention and carries out the process flow diagram that SR-2/8FFT decomposes framework.Based on 16 SR-2/8FFT of present embodiment, in step S402, S=4, BS=16, BP=0, SS=2.In step S404, BS=16 is greater than 8, thus entering step S406, LS=1, and store current state, case pointer becomes 1.Above-mentioned steps is corresponding to the stage among Fig. 34, but the not butterfly calculating of execute phase 4 this moment.In step S408, S=3, BS=8, SS=1.Get back among the step S404, BS=8, thus get into step S406, LS=1, and storing current state, case pointer becomes 2.Above-mentioned steps is corresponding to the 4 entering stages 3 of the stage among Fig. 3, but the also not butterfly of execute phase 3 calculating this moment.

Then, in step S408, S=2, BS=4, SS=1.Get back among the step S404, BS=4 is less than 8, so connecting step G.In step S410, BS=4 so get into step S412, carries out radix-4 butterfly and calculates.Above-mentioned steps is corresponding to the 3 entering stages 2 of the stage among Fig. 3; And a plurality of variablees based on the current state record; SRFFT processor 120 capture simultaneously be stored in thesaurus (b0, a0), (b1, a0), (b2; A0) and (b3, data x a0) [0], x [8], x [4] and x [12] calculate to carry out radix-4 butterfly.The output result that SRFFT control block 150 control radix-4 butterflies are calculated write back thesaurus (b0, a0), (b1, a0), (b2, a0) and (b3 a0) is x [0], x [8], x [4] and x [12].Afterwards, connecting step H.

In step S414, case pointer=2 so get into step S416, are recovered previous state greater than 0, S=3, and BS=8, BP=0, SS=1, LS=1, case pointer becomes 1.In step S418, because LS=1, so connecting step A.In step S420, because BS=8 less than 16, so connecting step E gets into step S422, carries out the SR-8 butterfly and calculates.Above-mentioned steps is got back to the stage 3 corresponding to the stage among Fig. 32, and based on a plurality of variablees of current state record, SRFFT processor 120 captures simultaneously and is stored in thesaurus (b0; A0), (b1, a0), (b2, a0), (b3; A0), (b4, a0), (b5, a0), (b6; A0) and (b7, data x a0) [0], x [8], x [4], x [12], x [2], x [10], x [6] and x [14] calculate to carry out the SR-8 butterfly.The output result that SRFFT control block 150 control SR-8 butterflies are calculated write back thesaurus (b0, a0), (b1, a0), (b2; A0), (b3, a0), (b4, a0), (b5; A0), (b6, a0) and (b7 a0) is x [0], x [8], x [4], x [12], x [2], x [10], x [6] and x [14].Afterwards, connecting step H.

In step S414, case pointer=1 so get into step S416, is recovered previous state greater than 0, S=4, and BS=16, BP=0, SS=2, LS=1, case pointer becomes 0.In step S418, because LS=1, so connecting step A.Because BS=16, so get into step S426 via step S420 and S424, LS=5 stores current state, and case pointer becomes 1.Then, in step S428, S=1, BP=8, BS=2, SS=1.Above-mentioned steps is got back to the stage 4 corresponding to the stage among Fig. 33, but this moment also not the butterfly of execute phase 4 calculate but the entering stage 1.

Get back among the step S404, BS=2 is less than 8, so connecting step G.In step S410, BS=2 so get into step S430, carries out radix-2 butterfly and calculates.Above-mentioned steps is corresponding to the 4 entering stages 1 of the stage among Fig. 3, and based on a plurality of variablees of current state record, SRFFT processor 120 captures simultaneously and is stored in thesaurus (b0; A1) with (b1, a1), (b2, a1) with (b3; A1), (b4, a1) with (b5, a1) and (b6; A1) with (b7, data x a1) [1] and x [9], x [5] and x [13], x [3] and x [11], and x [7] calculates to carry out 4 radix-2 butterflies with x [15].The output result that 4 radix-2 butterflies of SRFFT control block 150 controls are calculated write back thesaurus (b0, a1) with (b1, a1), (b2; A1) with (b3, a1), (b4, a1) with (b5; A1) and (b6; A1) with (b7 a1) is x [1] and x [9], x [5] and x [13], x [3] and x [11], and x [7] and x [15].Afterwards, connecting step H.

In step S414, case pointer=1 so get into step S416, is recovered previous state greater than 0, S=4, and BS=16, BP=0, SS=2, LS=5, case pointer becomes 0.In step S418 and S432～S436, because LS=5 so connecting step E gets into step S422, carries out the SR-8 butterfly and calculates.Above-mentioned steps is got back to the stage 4 corresponding to the stage among Fig. 31, and based on a plurality of variablees of current state record, SRFFT processor 120 captures simultaneously and is stored in thesaurus (b0; A0), (b2, a0), (b4, a0), (b6; A0), (b1, a1), (b3, a1), (b5; A1) and (b7, data x a1) [0], x [4], x [2], x [6], x [1], x [5], x [3] and x [7] calculate to carry out SR-8 butterfly.The output result that SRFFT control block 150 control SR-8 butterflies are calculated write back thesaurus (b0, a0), (b2, a0), (b4; A0), (b6, a0), (b1, a1), (b3; A1), (b5, a1) and (b7 a1) is X [0], X [4], X [2], X [6], X [1], X [5], X [3] and X [7].

In addition, SRFFT processor 120 capture more simultaneously be stored in thesaurus (b1, a0), (b3; A0), (b5, a0), (b7, a0), (b0; A1), (b2; A1), (b4, a1) and (b6, data x a1) [8], x [12], x [10], x [14], x [9], x [13], x [11] and x [15] calculate to carry out another time SR-8 butterfly.Wherein, x [9], x [13], x [11] and x [15] before the SR-8 butterfly is calculated respectively by 4 twiddle factor W _1/N, W _5/N, W _3/NAnd W _7/NRotation reaches special angle.The output result that SRFFT control block 150 control SR-8 butterflies are calculated write back thesaurus (b1, a0), (b3, a0), (b5; A0), (b7, a0), (b0, a1), (b2; A1), (b4, a1) and (b6 a1) is X [8], X [12], X [10], X [14], X [9], X [13], X [11] and X [15].

After accomplishing above-mentioned 2 SR-8 butterflies calculating, case pointer becomes-1, and hereat after step S414, the DIT SR butterfly of SRFFT processor 120 is calculated and finishes.At this moment, be stored in 8 thesauruss 16 outputs as a result X [0]～X [15] be the FFT operation result of input data x [0]～x [15].When SRFFT processor 120 is accomplished along decomposition execution order as shown in Figure 3 after DIT SR butterfly calculates, the number of the thesaurus that output control block 160 is comprised according to storer 110 and original address decision second order as shown in table 3 of 16 output datas.Then, each output result that 160 controls of output control block write back and are stored in a plurality of thesauruss is output as 16 output datas according to second order, corresponding in regular turn 16 the input data that meet first order of the output result that these 16 output datas comprise.Wherein, each output result round values of getting its quotient by the original address value of the output data of correspondence divided by the thesaurus number in the address of the thesaurus that writes back and store obtains.Please cooperate with reference to Fig. 5, it illustrates the synoptic diagram according to the partial arithmetic flow process of second order of preferred embodiment of the present invention.Wherein,, whenever carry out the computing of XOR (XOR), again the XOR result is multiplied by 2 power power, and totalling draws the thesaurus that will load at a distance from 3 positions so get based on 8 thesauruss.

Table 3

Can learn corresponding in regular turn 16 the input data that meet first order of the output result that these 16 output datas comprise by table 3.

In addition, also (Split-Radix, SR)-2/4FFT, and storer 100 must comprise 4 thesauruss and gets final product the FFT computing framework of the above embodiment of the present invention applicable to the division radix.Wherein, When above-mentioned FFT computing framework applications during in SR-2/4FFT; In the partial arithmetic flow process of first order, based on 4 thesauruss, so get whenever at a distance from 2 reverse position row XOR (computings of (XOR); Again the XOR result is multiplied by 2 power power, and totalling draws the thesaurus that the input data will load.

The present invention more proposes a kind of SR-2/8FFT method, is applied to a SR-2/8FFT device, and the SR-2/8FFT device comprises a storer, a SRFF processor and a control module.Storer comprises a plurality of thesauruss.The SRFFT processor calculates in order to carry out a DIT SR butterfly.Control module comprises an input control block, SRFFT control block and an output control block.This SR-2/8FFT method comprises the following steps.Storer receives 2 ^MPen input data, each data has an original address, and M is a positive integer.Input control block determines one first order according to the number of these thesauruss and the reverse address, position of these original addresss.This storer of input control block control is according in first order these thesauruss that these input data load are corresponding, make the SRFFT processor can single clock pulse in the cycle from these thesauruss acquisition data simultaneously.

SRFFT control block determining corresponding this 2 ^M1 of pen input data ^MThe decomposition framework of point FFT, and control SRFFT processor repeats butterfly and calculate along decomposing framework, wherein the input data sequence calculated of butterfly meets first order each time.SRFFT control block is controlled output result after butterfly is calculated each time and is write and be fed back into the pairing thesaurus of data.After DIT SR butterfly was calculated completion, output control block was according to the number and 2 of these thesauruss ^MThe original address of output data determines one second order, and these output result who writes back and be stored in these thesauruss in order to control is output as 2 according to second order ^MOutput data, 2 ^MCorresponding in regular turn 2 of first order that meets of the output result that output data comprises ^MPen input data.

The operation principles of above-mentioned SR-2/8FFT method has been specified in the related content of SR-2/8FFT device 100 and Fig. 1～Fig. 5, so no longer repeat in this.

The SR-2/8FFT device and method that the above embodiment of the present invention disclosed has multiple advantages, below just lists and lifts the explanation of part advantage as follows:

SR-2/8FFT device and method of the present invention; Utilize simple and effective memory management method; In the thesaurus of input data according to the certain order pseudostatic ram; Make the SRFFT processor can single clock pulse in the cycle simultaneously to many data of storer acquisition, so need not adopt than storer (memory) expensive register (register) storage data.In addition, the present invention also utilizes finite state machine to realize the rule of FFT is decomposed framework, makes the SRFFT processor can use low-cost hardware to realize.Therefore, SR-2/8FFT device and method of the present invention has high-level efficiency and advantage cheaply.

In sum, though the present invention with the preferred embodiment exposure as above, yet it is not in order to limit the present invention.Have common knowledge the knowledgeable in the technical field under the present invention, do not breaking away from the spirit and scope of the present invention, when doing various changes that are equal to or replacement.Therefore, protection scope of the present invention is when looking accompanying being as the criterion that the application's claim scope defined.

Claims (12)

1. A split base (SR)-2/8 fast Fourier transform (FFT) device, comprising: A memory, including a plurality of storage banks, and used to receive 2 ^M pieces of input data, each piece of data has an original address, and M is a positive integer; a split radix fast Fourier transform (SRFFT) processor to perform a reduced order in time (DIT) split radix butterfly computation; and a control unit, comprising: An input control block, used to determine a first order according to the number of the memory banks and the bit-reversed addresses of the original addresses, and to control the memory to convert the memory banks according to the first order input data is loaded into said memory banks corresponding to the first order, so that the SRFFT processor can simultaneously fetch data from said memory banks within a single clock cycle; A split radix fast Fourier transform (SRFFT) control block, used to determine the decomposition structure corresponding to a ^2M point FFT of the ^2M input data, and control the SRFFT processor to repeatedly execute the butterfly calculation along the decomposition structure, wherein The input data order of each butterfly calculation conforms to the first order, and the SRFFT control block is also used to control the output result of each butterfly calculation to be written back to the storage bank corresponding to the input data; and An output control block, used to determine a second order according to the number of these memory banks and the original addresses of ^2M output data after the DIT SR butterfly calculation is completed, and used to control write-back and store in the The output results in the storage banks are output as 2 ^M pieces of output data according to the second order, and the output results contained in the 2 ^M pieces of output data correspond to the 2 ^M pieces of input data in accordance with the first order. 2. The SR-2/8FFT device according to claim 1, wherein the address of each input data is divided by the number of storage banks by the bit reverse address value of the input data at the address of the corresponding storage bank Take the integer value of its quotient to get. 3. The SR-2/8FFT device according to claim 1, wherein when the butterfly calculation performed by the SRFFT processor is an SR-8 butterfly calculation, the SRFFT control block is also used to generate 4 rotations Factors are provided to the SR-8 butterfly calculation such that the last 4 inputs of the SR-8 butterfly calculation are each rotated by a specific angle. 4. The SR-2/8FFT device according to claim 1, characterized in that, the SRFFT control block decomposes the 2 ^M -point FFT according to the butterfly calculation of different radixes in M stages to obtain a decomposed execution order, and controls the The SRFFT processor executes the butterfly calculations along the decomposed execution order, wherein the butterfly calculations with different radixes in each stage may be repeatedly executed, and the input data fed to the input terminal for each butterfly calculation conforms to the first order. 5. SR-2/8FFT device according to claim 4, is characterized in that, this SRFFT control block is made up of a finite state machine, and this finite state machine records a plurality of states, and each state comprises a plurality of variables, so These variables include a stage, a base position representing the start position of the butterfly computation, a block size representing the number of data processed in each stage, a sample space representing the distance between the two inputs of the butterfly computation for that stage, and a previous state . 6. SR-2/8FFT device according to claim 1, is characterized in that, the address of each output data at the read storage storehouse is divided by the storage storehouse number by the original address value of this output data Take the integer value of its quotient to get. 7. A split radix (SR)-2/8 fast Fourier transform (FFT) method is applied to an SR-2/8FFT device, and the SR-2/8FFT device includes a memory, a split radix fast Fourier transform (SRFFT ) processor and a control unit, the memory includes a plurality of storage banks, the SRFFT processor is used to perform a time reduction (DIT) SR butterfly calculation, the control unit includes an input control block, a split radix fast Fourier transform ( SRFFT) control block and an output control block, the SR-2/8FFT method includes: The memory receives 2 ^M pieces of input data, each piece of data has an original address, and M is a positive integer; The input control block determines a first order according to the number of the storage banks and the bit-reversed addresses of the original addresses; The input control block controls the memory to load the input data into the storage banks corresponding to the first order in accordance with the first order, so that the SRFFT processor can read from all the memory banks in a single clock cycle. fetch data from these repositories simultaneously; The SRFFT control block determines the decomposition structure of a 2 ^M -point FFT corresponding to the 2 ^M input data, and controls the SRFFT processor to repeatedly execute the butterfly calculation along the decomposition structure, wherein the input data sequence of each butterfly calculation conforms to the first order; The SRFFT control block controls the output result of each butterfly calculation to be written back to the storage bank corresponding to the input data; and After the calculation of the DIT SR butterfly is completed, the output control block determines a second order according to the number of these memory banks and the original address of the ^2M output data, and is used to control write-back and store in these The output results in the storage library are output as 2 ^M pieces of output data according to the second order, and the output results contained in the 2 ^M pieces of output data correspond to the 2 ^M pieces of input data in accordance with the first order. 8. SR-2/8FFT method according to claim 7, is characterized in that, also comprises: The address of the input data in the corresponding storage bank is obtained by dividing the bit-reversed address value of each input data by the number of storage banks and taking the integer value of the quotient. 9. SR-2/8FFT method according to claim 7, is characterized in that, also comprises: When the butterfly calculation performed by the SRFFT processor is an SR-8 butterfly calculation, the SRFFT control block generates 4 twiddle factors to provide to the SR-8 butterfly calculation, so that the last 4 inputs of the SR-8 butterfly calculation are respectively Rotate by a specific angle. 10. SR-2/8FFT method according to claim 7, is characterized in that, also comprises: The SRFFT control block decomposes the 2 ^M -point FFT according to M stages of butterfly calculations with different radixes to obtain a decomposition execution order, and controls the SRFFT processor to execute the butterfly calculations along the decomposition execution order, wherein each stage Butterfly calculations with different radixes can be executed repeatedly, and the input data fed to the input end of each butterfly calculation conforms to the first order. 11. SR-2/8FFT method according to claim 10, is characterized in that, forms this SRFFT control block with a finite state machine, and this finite state machine records a plurality of states, and each state comprises a plurality of variables, These variables include a stage, a base position representing the starting position of the butterfly calculation, a block size representing the number of data processed in each stage, a sample space representing the distance between the two inputs of the butterfly calculation in this stage, and an upper one state. 12. SR-2/8FFT method according to claim 7, is characterized in that, also comprises: The integer value of the quotient obtained by dividing the original address value of each piece of output data by the number of storage banks is used to obtain the address of the output data in the read storage bank.

Images