CN102339272A - SF (split-radix)-2/8 FFT (fast Fourier transform) device and method - Google Patents

Abstract

The invention provides an SF (split-radix)-2/8 FFT (fast Fourier transform) device which comprises a memorizer, an SRFFT (split-radix fast Fourier transform) processor and a control unit, wherein 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 input data to corresponding memory banks in accordance with the first sequence so that the SRFFT processor can capture the data in the memory banks simultaneously in a single clock cycle; the SRFFT control block determines a breakdown structure of 2M-point FFT and controls the SRFFT processor to repeatedly execute butterfly computation along the breakdown structure; the input data sequence of the butterfly computation each time complies with the first sequence; the SRFFT control block controls the result output by the butterfly computation each time to be written back the memory banks corresponding to the input data; and the output control block determines a second sequence and controls the output results to be output as output data in accordance with 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. division radix (SR)-2/8 fast fourier transform (FFT) is installed, and comprising:

One 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;

One division radix fast fourier transform (SRFFT) processor falls time (DIT) division radix butterfly in order to the time of carrying out and calculates; And

One control module comprises:

One input control block; In order to determine one first order according to the number of said these thesauruss and the reverse address, position of said these original addresss; And will be said in these input data load said these thesauruss in order to control this storer corresponding to this first order according to this first order, make this SRFFT processor can single clock pulse in the cycle from said these thesauruss while acquisition datas;

One division radix fast fourier transform (SRFFT) control block, in order to decision to should 2 ^M1 of pen input data ^MThe decomposition framework of point FFT; And control this SRFFT processor and repeat butterfly along this decomposition framework and calculate; Wherein the input data sequence calculated of butterfly meets this first order each time, and this 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; And

One output control block is after calculating completion when this DIT SR butterfly, according to the number and 2 of said these thesauruss ^MThe original address of output data determines one second order, and said these output result who writes back and be stored in said these thesauruss in order to control is output as 2 according to this second order ^MOutput data, these are 2 years old ^MThe output result that output data comprises in regular turn correspondence meet first order this 2 ^MPen input data.

2. SR-2/8FFT device according to claim 1 is characterized in that, the round values that each input data is got its quotient by the reverse address value in the position of these input data divided by the thesaurus number in the address of this thesaurus of correspondence obtains.

3. SR-2/8FFT device according to claim 1; It is characterized in that; When the performed butterfly of this SRFFT processor is calculated as the calculating of SR-8 butterfly; This SRFFT control block also calculates to offer the SR-8 butterfly in order to produce 4 twiddle factors, and 4 inputs in end that make the SR-8 butterfly calculate are rotated respectively and reach special angle.

4. SR-2/8FFT device according to claim 1 is characterized in that,, this SRFFT control block with this 2 ^MPoint FFT obtains one according to the not homoimerous butterfly calculating decomposition of M stage and decomposes execution order; And control this SRFFT processor and carry out said these butterflies calculating along this decomposition execution order; Wherein not homoimerous butterfly is calculated and possibly be repeated to carry out each stage, and each time butterfly calculate the feed-in input end the input data symbols should preface for the first time.

5. SR-2/8FFT device according to claim 4; It is characterized in that; This SRFFT control block constitutes with a finite state machine; This finite state machine writes down a plurality of states, and each state comprises a plurality of variablees, and said these variablees comprise that a stage, expression butterfly calculate the block size of the data number of a home position of starting position, the every phase process of expression, represent that the butterfly in this stage calculates a sample space of two input end spacings, an and laststate.

6. SR-2/8FFT device according to claim 1 is characterized in that, the round values that each output data is got its quotient by the original address value of this output data divided by the thesaurus number in the address of this thesaurus that is read obtains.

7. one kind is divided radix (SR)-2/8 fast fourier transform (FFT) method; Be applied to a SR-2/8FFT device; This SR-2/8FFT device comprises a storer, division radix fast fourier transform (SRFFT) processor and a control module; This storer comprises a plurality of thesauruss; This SRFFT processor falls time (DIT) SR butterfly in order to the time of carrying out and calculates, and this control module comprises an input control block, division radix fast fourier transform (SRFFT) control block and an output control block, and this SR-2/8FFT method comprises:

This storer receives 2 ^MPen input data, each data has an original address, and M is a positive integer;

This input control block determines one first order according to the number of said these thesauruss and the reverse address, position of said these original addresss;

This this storer of input control block control according to this first order will said these input data load said these thesauruss corresponding to this first order in, make this SRFFT processor can single clock pulse in the cycle from said these thesauruss while acquisition datas;

This SRFFT control block determining is to should 2 ^M1 of pen input data ^MThe decomposition framework of point FFT, and control this SRFFT processor and repeat butterfly along this decompositions framework and calculate, wherein the input data sequence of butterfly calculating each time meets this first order;

This 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; And

After this DIT SR butterfly was calculated completion, this output control block was according to the number and 2 of said 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 this second order ^MOutput data, these are 2 years old ^MThe output result that output data comprises is corresponding in regular turn meet first order this 2 ^MPen input data.

8. SR-2/8FFT method according to claim 7 is characterized in that, also comprises:

The round values of getting its quotient divided by the thesaurus number by the reverse address value in the position of each input data obtains the address of these input data at this thesaurus of correspondence.

9. SR-2/8FFT method according to claim 7 is characterized in that, also comprises:

When the performed butterfly of this SRFFT processor was calculated as the calculating of SR-8 butterfly, this SRFFT control block produced 4 twiddle factors and calculates 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.

10. SR-2/8FFT method according to claim 7 is characterized in that, also comprises:

This SRFFT control block with this 2 ^MPoint FFT calculates to decompose according to the not homoimerous butterfly in M section rank and obtains a decomposition execution order; And control this SRFFT processor and carry out said these butterflies calculating along this decomposition execution order; Wherein the not homoimerous butterfly calculating of each stage can be repeated to carry out, and input data fit first order of the feed-in of butterfly calculating each time input end.

11. SR-2/8FFT method according to claim 10; It is characterized in that; Be to constitute this SRFFT control block with a finite state machine; This finite state machine writes down a plurality of states, and each state comprises a plurality of variablees, and said these variablees comprise that a stage, expression butterfly calculate the block size of the data number of a home position of starting position, the every phase process of expression, represent that the butterfly in this stage calculates a sample space of two input end spacings, an and laststate.

12. SR-2/8FFT method according to claim 7 is characterized in that, also comprises:

The round values of getting its quotient divided by the thesaurus number by the original address value of each output data obtains the address of this output data at this thesaurus that is read.

Images