Data scheduling register tree for radix-2 FFT architecture

Abstract

The present invention discloses a data scheduling register tree structure for radix-2 FFT architecture. The operation method of the proposed invention, there is no need for the Random Access Memory (RAM) to store the data; instead, shift registers with some multiplexers are enough to perform the memory operation with less hardware. There are three steps in the FFT computation such as input storage, data processing and output retrieval. The data processing step is further configured in four different operations. The number of operation mainly depends upon the size of the FFT, which is equal to log.sub.2N modes. During each operation, the DSRT changes its structure and these structures are basically MDC (Multi-path Delay Commutator) structures.

Claims

1. A data scheduling register tree (DSRT) structure for Radix-2 Fast Fourier Transform (FFT) architecture comprising of: a plurality of shift registers (R.sub.1 to R.sub.16); and a plurality of multiplexers (mi, mx.sub.1-mx.sub.4, mu.sub.1-mu.sub.3) in place of Random Access Memory to store the data in the 16 point FFT architecture, wherein the memory operation is performed by the data scheduling Register tree (DSRT), which can be substituted with any radix-2 FFT size for the architecture to obtain the corresponding size.

2. The data scheduling Register tree (DSRT) structure for 16-point Radix-2 as claimed in claim 1, wherein the total number of the multiplexers required for design N-point Radix-2 FFT is 2 log.sub.2N and R1(R.sub.1) has 1D register, R2(R.sub.2) has 1D register, R3(R.sub.4-3) has 2D registers, R4(R.sub.8-5) has 4D registers and so on up to Rn(R.sub.N/2−(N/4+1)) has (N/4)D registers, wherein N is the number of registers required, which can be substituted with any radix-2 FFT size for the architecture to obtain the corresponding architecture.

3. The data scheduling Register tree (DSRT) structure for Radix-2 as claimed in claim 1, wherein the 16-point FFT having four configurations (I to IV) and N-point FFT has log.sub.2N configurations (1 to log2N), wherein N is the number of registers required.

4. The data scheduling Register tree (DSRT) structure for 16-point Radix-2 as claimed in claim 3, wherein the N-point Radix-2 FFT architecture is characterized by the following configurations: (a) during configuration-I, the control signal to multiplexers (mx.sub.n) is 1 and all other control signals of multiplexers (mx and mu) are zero; (b) during configuration-II, the control signals of multiplexers (mx.sub.n-1 and mu.sub.n-1) are 1 and all other control signals of multiplexers (mx and mu) are zero and the control signal of SW toggles for every N/4 clock cycles; (c) during configuration-III, the control signals of multiplexers (mx.sub.n-2 and mu.sub.n-2) are 1 and all other control signals of multiplexers (mx and mu) are zero and the control signal of SW toggles for every N/8 clock cycles; (d) during configuration-IV, the control signals of multiplexers (mx.sub.n-3 and mu.sub.n-3) are 1 and all other control signals of multiplexers (mx and mu) are zero and the control signal of SW toggles for every N/16 clock cycles; (e) wherein N-point Radix-2 FFT architecture goes up to configuration-n during which the control signals of mx.sub.1 and mu.sub.1 are 1 and all other control signals of mx and mu are zero and the control signal of SW toggles for everyone clock cycle, wherein n=log.sub.2N.

5. The data scheduling Register tree (DSRT) structure for Radix-2 as claimed in claim 1, wherein the operation of the 16-point FFT architecture is further comprises the following steps: (a) input storage step comprises of the control signal of m.sub.i, mx.sub.4 is set to “1”, the control signals of mx.sub.3, mx.sub.2, mx.sub.1 are set to “0” and the switch position is set as Swap, wherein the input data are fed from Ip.sub.1 to the architecture through the multiplexer (mi) and the input data (x.sub.0, x.sub.1, x.sub.2, . . . x.sub.15) are stored in the shift registers (D, D, 2D, 4D and 8D); (b) data processing step comprises of retrieving of the data stored in the registers (DSRT) and processed by the processing element and stored the output data back into the shift registers, characterized by the switch (SW) position is toggling between normal and swap mode depending upon the operation and control signals (Ctrl) of multiplexer (m.sub.i, mx.sub.4, mx.sub.3, mx.sub.2, mx.sub.1, mu.sub.3, mu.sub.2, mu.sub.1) are also set depending upon the operation; (c) data retrieval step comprises of the control signals to the multiplexer are set same as the input storage mode, wherein the output are stored in the sixteen registers, R.sub.1 to R.sub.16 and further the output data are retrieved while the output data of the current set are retrieved, the next set of input data are stored into the registers, wherein, the next set of input data stored into the register once the output data of the current set are retrieved.

6. The data scheduling Register tree (DSRT) structure for Radix-2 as claimed in claim 5, wherein the control signal of the multiplexer (mi) is set to “1” during the data storage step and in the data retrieval step and set to “0” during the data processing step.

Description

BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS

(1) The drawings described herein are for illustrative purposes only of selected embodiments and not all possible implementations and are not intended to limit the scope of the present disclosure. The invention itself, however, both as to organization and method of operation, may best be understood by reference to the detailed description which follows taken in conjunction with the accompanying drawings in which:

(2) FIG. 1 is the representation of the N-point radix-2 FFT architecture with the data scheduling register tree unit of the system.

(3) FIG. 2 is a block diagram of the system illustrating the 16-point FFT architecture with data scheduling register tree unit according to the preferred embodiment of the present invention;

(4) FIG. 3 is a block diagram of the configuration of Data Scheduling Register Tree.

DETAILED DESCRIPTION OF THE INVENTION

(5) The preferred embodiments will now be described more fully with reference to the accompanying drawings. The embodiments are provided so that this disclosure will be thorough, and will fully convey the scope to those who are skilled in the art. Numerous specific details are set forth as specific components, devices, and methods, to provide a thorough understanding of preferred embodiments of the present disclosure. It will be apparent to those skilled in the art that specific details need not be employed, that preferred embodiments may be embodied in many different forms and that neither should be construed to limit the scope of the disclosure. In some example embodiments, well-known processes, well-known device structures, and well-known technologies are not described in detail.

Definitions of the Used Terms

(6) The following definitions should be interpreted in consideration of the disclosure and for a better understanding of the present invention to a person skilled in the art. In the complete disclosure of the present invention, certain scientific and biotechnological terms appropriately used, having the same meaning as practically and theoretically understood by an ordinary person skilled in the art.

(7) Fast Fourier transform (FFT):—The term “Fast Fourier transform” used herein refers to an algorithm that calculates the discrete Fourier transform (DFT) of some sequence and also reduces the number of computations needed for N points from 2N.sup.2 to 2N lg N, where lg is the base-2 logarithm.

(8) Random-access memory (RAM):—The term “Random-access memory” used herein refers to a hardware device that allows information to be stored and retrieved on a computer.

(9) Multipath Delay Commutator (MDC):—The term “Multipath Delay Commutator” used herein refers to an architecture that is the most straightforward approach to implement the radix-2 FFT algorithm using pipeline architecture.

(10) Register:—The term “Register” used herein refers to a storage space for units of memory that are used to transfer data for immediate use by the CPU (Central Processing Unit) for data processing.

(11) Shift Registers:—The term “Shift Registers” used herein refers to the digital memory circuitry found in devices such as calculators, computers, and data processing systems.

(12) Multiplexer (or mux):—The term “Multiplexer” used herein refers to a way of selecting one out of many digital signals. It is a combinational circuit that has a maximum of 2n data inputs, ‘n’ selection lines and a single output line.

Abbreviations

(13) FFT:—Fast Fourier transform

(14) DSRT—Data Scheduling Register Tree

(15) DIF:—Decimation in Frequency

(16) MDC:—Multipath Delay Commutator

(17) In describing the preferred embodiments of the present invention, reference will be made herein to FIGS. 1, 2, and 3 of the drawings in which like numerals refer to like features of the invention.

(18) One embodiment of the proposed invention includes an FFT architecture having a register tree instead of RAM and a hybrid that is in between in-placed and MDC (multi-path delay commutator) pipelined FFT architectures. The memory module is designed, based on the shift registers and multiplexers, which is a Data Scheduling Register Tree structure. The same memory operation can be performed using the DSRT (Data Scheduling Register Tree) structure but with less hardware. The DSRT does not require address decoder and complex addressing schemes to overcome memory conflict issues. Therefore, the convention RAM-based approach required 50% more area than the proposed DSRT approach.

(19) In another embodiment of the present invention, an N-point FFT architecture is illustrated in FIG. 1. N can be substituted with any radix-2 FFT size and the architecture for the corresponding size can be obtained. The total number of multiplexer required for the design is 2 log.sub.2 N and N number of registers are required. R1(R1) has 1D register, R2(R2) has 1D register, R3(R4-3) has 2D registers, R4(R8-5) has 4D registers and finally, Rn(RN/2−(N/4+1)) has (N/4)D registers. Similarly, Rr(RN−(N/2+1)) has (N/2)D registers.

(20) In the N-point FFT, there are log.sub.2 N configurations and log.sub.2 N is equal to n. The control signal of mi is set to“1” during data storage step and retrieval step and “0” while data processing step.

(21) Yet another embodiment of the present invention, FIG. 2 is showing an example of proposed DIF FFT architecture. In FIG. 2, there are two main units Processing Element (PE) and DSRT (Data Scheduling Register Tree). The Processing Element includes adder, subtractor and multiplier to perform the FFT butterfly operation. The Data Scheduling Register Tree has Shift Registers and multiplexers, which provides the data to PE in an appropriate order. The SW unit is a switch that has two modes of operations namely normal mode and swap mode. During the normal mode, the data at the lower input is passed to the lower output and the data at the upper input is passed to the upper output. During the swap mode, the data at the lower input is passed to the upper output and the data at the upper input is passed to the lower output.

(22) The working of the architecture is followed by the three steps in the FFT Commutation operation such as input storage, data processing, and output retrieval.

(23) Input storage:—In the input storage step the Ctrl (control signal) of mi, mx4 are set to “1”, the control signals of the multiplexer (mx3, mx2, mx1) are set to “0” and the switch position is set as Swap. In the same step, the input data are fed from I p1 to the architecture through the multiplexer (mi) and the sixteen input data (x0, x1, x2, . . . x15) are stored in the shift registers D, D, 2D, 4D and 8D.

(24) Data processing:—In the data processing step, the data stored in the registers (DSRT) are retrieved, processed by the PE and stored the output data back into the registers. This process is repeated to compute the output of every stage of the FFT. In total, this process repeated four times because it is a 16-point (24-point) FFT and has four stages. The SW position toggles between normal and swap mode depending upon the operation and control signals (Ctrl) of the multiplexer (mi, mx4, mx3, mx2, mx1, mu3, mu2, mu1) are also set depending upon the operation.

(25) Output retrieval:—In the data retrieval step, the control signals to the multiplexer are set the same as that of input storage mode. Once the output is stored in the sixteen registers, R1 to R16, they are retrieved from the ra1 line which is connected to pa1. While the output data of the current set are retrieved, the next set of input data is stored into the registers.

(26) According to an embodiment of the invention, the inputs x15 to x0 are first stored in the registers R16 to R1 respectively. The next step is the data processing and it has four different operations. The number of operations depends upon the size of the FFT, which is equal to log 2 N modes. Since the size of the proposed FFT is 16-point, it has four different operations. During each operation, the DSRT changes its structure and these structures are basically MDC (Multi-path Delay Commutator) structures.

(27) According to the present invention, there are four different configurations of DSRT are illustrated in FIG. 3. The data processing step has four different configurations for the operation of the FFT computation. In all of the configurations, there are two inputs and two outputs designated as fba and fbb because input and output are forming a closed path.

(28) Configuration-I

(29) In the configuration-,I the Ctrl of mi=0, mx4=1, mx3=0, mx2=0, mx1=0, mu3=0, mu2=0, mu1=0 and the switch is in normal position. The equivalent structure as shown in FIG. 3a, 0D refers to no delay/register. The data x0 to x7 is stored in the upper 8D registers and the data x8 to x15 are stored in the lower 8D registers. This configuration remains for the first eight (1-8) clock cycles during the data processing step and provides the inputs for the butterfly operations of the first stage of the 16-point radix-2 DIF FFT. The outputs of the first stage are stored back to the upper and lower 8D registers via f ba and f bb.

(30) Configuration-II

(31) As per the configuration-II, the Ctrl of mi=0, mx4=0, mx3=1, mx2=0, mx1=0, mu3=1, mu2=0, mu1=0. The equivalent structure is illustrated in FIG. 3b. This configuration remains for the second eight (9-16) clock cycles and provides the inputs (outputs of the first stage) to the PE to perform the butterfly operations of the second stage of FFT DFG. The outputs of the second stage are stored back to the registers via f ba and f bb. The switch is in swap position during 9 to 12 clock cycles and normal position during 13 to 16 clock cycles.

(32) Configuration-III According to the configuration-III, the Ctrl of mi=0, mx4=0, mx3=0, mx2=1, mx1=0, mu3=0, mu2=1, mu1=0. The equivalent structure is illustrated in FIG. 3c. This configuration remains for the third eight (17-24) clock cycles and provides the inputs (outputs of the second stage) to perform the butterfly operations of the third stage. The outputs of the third stage are stored back to the registers via fba and fbb. The switch is in swap position during 17 & 18, 21 & 22, clock cycles and normal position during 19 & 20, 23 & 24 clock cycles.

(33) Configuration-IV

(34) In the configuration-IV, the Ctrl of mi=0, mx4=0, mx3=0, mx2=0, mx1=1, mu3=0, mu2=0, mu1=1. The equivalent structure is shown in FIG. 3d. This configuration remains for the fourth eight (25-32) clock cycles and provides the inputs (outputs of the third stage) to perform the for the butterfly operations of the fourth stage. The outputs of the fourth stage are stored back to the registers via fba and fbb. The switch is in swap position during 25, 27, 29, 31 clock cycles and normal position during 26, 28, 30, 32 clock cycles.

(35) During configuration-I, the control signal to mxn is 1 and all the control signals of mx and mu are zero. During configuration-II, the control signals of mxn-1 and mun-1 are 1 and all the control signals of mx and mu are zero and the control signal of SW toggles for every N/4 clock cycles. During configuration-III, the control signals of mxn-2 and mun-2 are 1 and all the control signals of mx and mu are zero and the control signal of SW toggles for every N/8 clock cycles. During configuration-IV, the control signals of mxn-3 and mun-3 are 1 and all the control signals of mx and mu are zero and the control signal of SW toggles for every N/16 clock cycles. This goes up to configuration-n during which the control signals of mx1 and mu1 are 1 and all the control signals of mx and mu are zero and the control signal of SW toggles for every one clock cycle.

(36) The invented data scheduling register tree structure for radix-2 FFT architecture provides the following practical uses and benefits: (i) The method includes register tree structure for the storage of the data instead of RAM. (ii) The memory module designed based on the shift registers and multiplexers as a result, the same memory operation can be performed using the DSRT (Data Scheduling Register Tree) structure but with less hardware. (iii) Unlike RAM the Data Scheduling Register Tree (DSRT) does not require address decoder and complex addressing schemes to overcome memory conflict issues.

(37) Although a preferred embodiment of the invention has been illustrated and described, it will at once be apparent to those skilled in the art that the invention includes advantages and features over and beyond the specific illustrated construction. Accordingly, it is intended that the scope of the invention be limited solely by the scope of the hereinafter appended claims, and not by the foregoing specification, when interpreted in light of the relevant prior art.

LIST OF REFERENCE NUMERALS

(38) (1) Multiplexers—mi, mx.sub.1, mx.sub.2, mx.sub.3, mx.sub.4, mu.sub.1, -mu.sub.3 (2) Registers—R.sub.1 to R.sub.16 (3) Shift registers—D, D, 2D, 4D and 8D (4) Input data—IP.sub.1