Patent Publication Number: US-10771947-B2

Title: Methods and apparatus for twiddle factor generation for use with a programmable mixed-radix DFT/IDFT processor

Description:
PRIORITY 
     This patent application is a continuation patent application of a co-pending U.S. patent application having a U.S. patent application Ser. No. 15/347,663, filed on Nov. 9, 2016 in the name of the same inventor and entitled “Methods and Apparatus for Twiddle Factor Generation for Use with a Programmable Mixed-Radix DFT/IDFT Processor,” which is a CIP U.S. patent application having an application Ser. No. 15/292,015 filed on Oct. 12, 2016, now issued as U.S. Pat. No. 10,311,018 on Jun. 4, 2019, entitled “Methods and Apparatus for a Vector Memory Subsystem for Use with a Programmable Mixed-Radix DFT/IDFT Processor,” which further claims the benefit of priority based upon U.S. Provisional Patent Application having an Application No. 62/279,345, filed on Jan. 15, 2016, and entitled “M ETHOD AND  A PPARATUS FOR  P ROVIDING  P ROGRAMMABLE  M IXED -R ADIX  DFT/IDFT P ROCESSOR  U SING  V ECTOR  M EMORY  S UBSYSTEM ,” and U.S. Provisional Patent Application having an Application No. 62/274,686, filed on Jan. 4, 2016, and entitled “M ETHOD AND  A PPARATUS FOR  D YNAMICALLY  G ENERATING  M IXED -R ADIX  T WIDDLE  C OEFFICIENT  V ECTORS ,” and U.S. Provisional Patent Application having Application No. 62/274,062, filed on Dec. 31, 2015, and entitled “M ETHOD AND  A PPARATUS FOR  P ROVIDING  P ROGRAMMABLE  M IXED  R ADIX  DFT P ROCESSOR  U SING  V ECTOR  E NGINES ,” all of which are hereby incorporated herein by reference in their entirety. 
    
    
     FIELD 
     The exemplary embodiments of the present invention relate to the design and operation of telecommunications networks. More specifically, the exemplary embodiments of the present invention relate to receiving and processing data streams in a wireless communication network. 
     BACKGROUND 
     There is a rapidly growing trend for mobile and remote data access over high-speed communication networks, such as 3G or 4G cellular networks. However, accurately delivering and deciphering data streams over these networks has become increasingly challenging and difficult. High-speed communication networks which are capable of delivering information include, but are not limited to, wireless networks, cellular networks, wireless personal area networks (“WPAN”), wireless local area networks (“WLAN”), wireless metropolitan area networks (“MAN”), or the like. While WPAN can be Bluetooth or ZigBee, WLAN may be a Wi-Fi network in accordance with IEEE 802.11 WLAN standards. 
     To communicate high speed data over a communication network, such as a long-term evolution (LTE) communication network, the network needs to support many configurations and process data utilizing different FFT sizes. A variety of architectures have been proposed for pipelined FFT processing that are capable of processing an uninterrupted stream of input data samples while producing a stream of output data samples at a matching rate. However, these architectures typically utilize multiple stages of FFT radix processors organized in a pipelined mode. The data is streamed into a first stage to complete a first radix operation and then the data is stream to subsequent stages for subsequent radix operations. 
     Thus, conventional pipelined architectures utilize multiple physical radix processors laid out in series to create the pipeline for streaming in/out data. The number of stages utilized is determined by the largest FFT size to be supported. However, this design becomes more complex when processing a variety of FFT sizes that require mixed-radix (2, 3, 4, 5, and 6) processing typically used in cellular (e.g., LTE) transceivers. As a result, the drawbacks of conventional systems are not only the amount of hardware resources utilized, but also the difficulty to configure such a system with the many different FFT sizes and mixed-radix factorization schemes utilized in an LTE transceiver. 
     Therefore, it is desirable to have a pipelined FFT architecture that is faster and consumes fewer resources than conventional systems. The architecture should have a higher performance to power/area ratio than the conventional architectures, and achieve much higher scalability and programmability for all possible mix-radix operations. 
     SUMMARY 
     The following summary illustrates simplified versions of one or more aspects of present invention. The purpose of this summary is to present some concepts in a simplified description as more detailed descriptions are provided below. 
     A programmable vector processor (“PVP”) capable of calculating discrete Fourier transform (“DFT”) values is disclosed. The PVP includes a ping-pong vector memory bank, a twiddle factor generator, and a programmable vector mixed radix engine that communicate data through a vector pipeline. The ping-pong vector memory bank is able to store input data and feedback data with optimal storage contention. The twiddle factor generator generates various twiddle values for DFT calculations. The programmable vector mixed radix engine is configured to provide one of multiple DFT radix results. For example, the programmable vector mixed radix engine can be programmed to perform radix3, radix4, radix 5 and radix6 DFT calculations. In one embodiment, the PVP also includes a vector memory address generator for producing storage addresses, and a vector dynamic scaling factor calculator capable of determining scaling values. 
     In an exemplary embodiment, an apparatus includes a vector memory bank and a vector data path pipeline coupled to the vector memory bank. The apparatus also includes a configurable mixed radix engine coupled to the vector data path pipeline. The configurable mixed radix engine is configurable to perform a selected radix computation selected from a plurality of radix computations. The configurable mixed radix engine performs the selected radix computation on data received from the vector memory bank through the vector pipeline to generate a radix result. The apparatus also includes a controller that controls how many radix computation iterations will be performed to compute an N-point DFT based on a radix factorization. 
     In an exemplary embodiment, a method for performing an N-point DFT is disclosed. The method includes determining a radix factorization to compute the N-point DFT, the radix factorization determines one or more stages of radix calculations to be performed. The method also includes performing an iteration for each radix calculation. Each iteration includes reading data from a vector memory bank into a vector data path pipeline, configuring a configurable mixed radix engine to perform a selected radix calculation, performing the selected radix calculation on the data in the vector data path pipeline, storing a radix result of the selected radix calculation back into the vector memory bank, if the current iteration is not the last iteration, and outputting the radix result of the selected radix calculation as the N-point DFT result, if the current iteration is the last iteration. 
     In an exemplary embodiment, an apparatus includes a vector memory bank and a vector memory system (VMS) that generates input memory addresses that are used to store input data into the vector memory bank. The VMS also generates output memory addresses that are used to unload vector data from the memory banks. The input memory addresses are used to shuffle the input data in the memory bank based on a radix factorization associated with an N-point DFT, and the output memory addresses are used to unload the vector data from the memory bank to compute radix factors of the radix factorization. 
     In an exemplary embodiment, a method includes generating input memory addresses that are used to store input data into a vector memory bank. The input memory addresses are used to shuffle the data in the memory bank based on a radix factorization associated with an N-point DFT. The method also includes generating output memory addresses that are used to unload vector data from the vector memory bank to compute radix factors of the radix factorization. 
     In an exemplary embodiment, an apparatus includes look-up table logic that receives twiddle control factors and outputs a selected twiddle factor scaler value (TFSV), a base vector generator that generates a base vector values based on the selected TFSV, and a twiddle column generator that generates a twiddle vector from the base vector. 
     Additional features and benefits of the exemplary embodiments of the present invention will become apparent from the detailed description, figures and claims set forth below. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The exemplary aspects of the present invention will be understood more fully from the detailed description given below and from the accompanying drawings of various embodiments of the invention, which, however, should not be taken to limit the invention to the specific embodiments, but are for explanation and understanding only. 
         FIG. 1  is a block diagram illustrating a computing network configured to transmit data streams using a programmable vector processor in accordance with exemplary embodiments of the present invention; 
         FIG. 2  is a block diagram illustrating logic flows of data streams traveling through a transceiver that includes a programmable vector processor in accordance with the exemplary embodiments of the present invention; 
         FIG. 3  is a table showing DFT/IDFT sizes with respect to index and resource block (“RB”) allocations in accordance with exemplary embodiments of the present invention; 
         FIG. 4  is a block diagram illustrating an exemplary embodiment of a programmable vector processor in accordance with exemplary embodiments of the present invention; 
         FIG. 5  is a block diagram illustrating a detailed exemplary embodiment of a programmable vector mixed-radix processor in accordance with exemplary embodiments of the present invention; 
         FIG. 6  is a block diagram of a radix3 configuration for use with the programmable vector mixed-radix processor in accordance with exemplary embodiments of the present invention; 
         FIG. 7  is a block diagram of a radix4 configuration for use with the programmable vector mixed-radix processor in accordance with exemplary embodiments of the present invention; 
         FIG. 8  is a block diagram of a radix5 configuration for use with the programmable vector mixed-radix processor in accordance with exemplary embodiments of the present invention; 
         FIG. 9  is a block diagram of a radix6 configuration for use with the programmable vector mixed-radix processor in accordance with exemplary embodiments of the present invention; 
         FIG. 10  is a block diagram illustrating a configurable vector mixed-radix engine in accordance with one embodiment of the present invention; 
         FIG. 11  illustrates an exemplary digital computing system that comprises a programmable vector processor having a configurable vector mixed-radix engine with iterative pipeline in accordance with embodiments of the invention; 
         FIG. 12  illustrates an exemplary method for operating a programmable vector processor having a configurable vector mixed-radix engine with iterative pipeline in accordance with embodiments of the invention; 
         FIG. 13  illustrates an exemplary embodiment of a 1080-point DFT configuration with radix factorization having five stages as in RV=[5,3,3,6,4] in accordance with embodiments of the invention; 
         FIG. 14  illustrates an exemplary embodiment of a memory configuration for a 1080-point DFT that utilizes a virtual folded memory with iterative DFT process in accordance with the exemplary embodiments of the invention; 
         FIG. 15  illustrates exemplary embodiments of memory organizations in accordance with embodiments of the invention; 
         FIGS. 16A-C  illustrate an exemplary embodiment of a memory input data pattern for a 1200-point DFT having one section based on a radix factorization where the last two stage of the radix factorization include {x, x, x, 3, 4}; 
         FIGS. 17A-D  illustrate an exemplary embodiment of a memory input data pattern for a 1080-point DFT having two sections based on a radix factorization where the last two stage of the radix factorization include {x, x, x, 6, 4}; 
         FIG. 18  illustrates an exemplary embodiment of a method for address generation for stages before the last two stages in accordance with the present invention; 
         FIG. 19  illustrates exemplary block diagrams of data output patterns for the output to get in-order addresses and SIMD4 throughput in accordance with exemplary embodiments of the present invention; 
         FIGS. 20-21  illustrates exemplary block diagrams of address patterns for the last stage of VMS in accordance with one embodiment of the present invention; 
         FIG. 22  shows an exemplary detailed embodiment of the dynamic twiddle factor generator (DTF) shown in  FIG. 4 ; 
         FIG. 23  shows an exemplary embodiment of an AGU for use in a look-up logic of the DTF shown in  FIG. 22 ; and 
         FIG. 24  illustrates an exemplary method for operating a twiddle factor generator in a programmable vector processor with iterative pipeline in accordance with embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     Aspects of the present invention are described herein the context of a methods and/or apparatus for processing control information relating to wireless data. 
     The purpose of the following detailed description is to provide an understanding of one or more embodiments of the present invention. Those of ordinary skills in the art will realize that the following detailed description is illustrative only and is not intended to be in any way limiting. Other embodiments will readily suggest themselves to such skilled persons having the benefit of this disclosure and/or description. 
     In the interest of clarity, not all of the routine features of the implementations described herein are shown and described. It will, of course, be understood that in the development of any such actual implementation, numerous implementation-specific decisions may be made in order to achieve the developer&#39;s specific goals, such as compliance with application- and business-related constraints, and that these specific goals will vary from one implementation to another and from one developer to another. Moreover, it will be understood that such a development effort might be complex and time-consuming, but would nevertheless be a routine undertaking of engineering for those of ordinary skills in the art having the benefit of embodiment(s) of this disclosure. 
     Various embodiments of the present invention illustrated in the drawings may not be drawn to scale. Rather, the dimensions of the various features may be expanded or reduced for clarity. In addition, some of the drawings may be simplified for clarity. Thus, the drawings may not depict all of the components of a given apparatus (e.g., device) or method. The same reference indicators will be used throughout the drawings and the following detailed description to refer to the same or like parts. 
     The term “system” or “device” is used generically herein to describe any number of components, elements, sub-systems, devices, packet switch elements, packet switches, access switches, routers, networks, modems, base stations, eNB (eNodeB), computer and/or communication devices or mechanisms, or combinations of components thereof. The term “computer” includes a processor, memory, and buses capable of executing instruction wherein the computer refers to one or a cluster of computers, personal computers, workstations, mainframes, or combinations of computers thereof. 
     IP communication network, IP network, or communication network means any type of network having an access network that is able to transmit data in a form of packets or cells, such as ATM (Asynchronous Transfer Mode) type, on a transport medium, for example, the TCP/IP or UDP/IP type. ATM cells are the result of decomposition (or segmentation) of packets of data, IP type, and those packets (here IP packets) comprise an IP header, a header specific to the transport medium (for example UDP or TCP) and payload data. The IP network may also include a satellite e network, a DVB-RCS (Digital Video Broadcasting-Return Channel System) network, providing Internet access via satellite, or an SDMB (Satellite Digital Multimedia Broadcast) network, a terrestrial network, a cable (xDSL) network or a mobile or cellular network (GPRS/EDGE, or UMTS (where applicable of the MBMS (Multimedia Broadcast/Multicast Services) type, or the evolution of the UMTS known as LTE (Long Term Evolution), or DVB-H (Digital Video Broadcasting-Handhelds)), or a hybrid (satellite and terrestrial) network. 
       FIG. 1  is a diagram illustrating a computing network  100  configured to transmit data streams using a programmable vector processor in accordance with exemplary embodiments of the present invention. The computer network  100  includes packet data network gateway (“P-GW”)  120 , two serving gateways (“S-GWs”)  121 - 122 , two base stations (or cell sites)  102 - 104 , server  124 , and Internet  150 . P-GW  120  includes various components  140  such as billing module  142 , subscribing module  144 , tracking module  146 , and the like to facilitate routing activities between sources and destinations. It should be noted that the underlying concepts of the exemplary embodiments of the present invention would not change if one or more blocks (or devices) were added or removed from computer network  100 . 
     The configuration of the computer network  100  may be referred to as a third generation (“3G”), 4G, LTE, 5G, or combination of 3G and 4G cellular network configuration. MME  126 , in one aspect, is coupled to base stations (or cell site) and S-GWs capable of facilitating data transfer between 3G and LTE (long term evolution) or between 2G and LTE. MME  126  performs various controlling/managing functions, network securities, and resource allocations. 
     S-GW  121  or  122 , in one example, coupled to P-GW  120 , MME  126 , and base stations  102  or  104 , is capable of routing data packets from base station  102 , or eNodeB, to P-GW  120  and/or MME  126 . A function of S-GW  121  or  122  is to perform an anchoring function for mobility between 3G and 4G equipment. S-GW  122  is also able to perform various network management functions, such as terminating paths, paging idle UEs, storing data, routing information, generating replica, and the like. 
     P-GW  120 , coupled to S-GWs  121 - 122  and Internet  150 , is able to provide network communication between user equipment (“UE”) and IP based networks such as Internet  150 . P-GW  120  is used for connectivity, packet filtering, inspection, data usage, billing, or PCRF (policy and charging rules function) enforcement, et cetera. P-GW  120  also provides an anchoring function for mobility between 3G and 4G (or LTE) packet core networks. 
     Sectors or blocks  102 - 104  are coupled to a base station or FEAB  128  which may also be known as a cell site, node B, or eNodeB. Sectors  102 - 104  include one or more radio towers  110  or  112 . Radio tower  110  or  112  is further coupled to various UEs, such as a cellular phone  106 , a handheld device  108 , tablets and/or iPad®  107  via wireless communications or channels  137 - 139 . Devices  106 - 108  can be portable devices or mobile devices, such as iPhone®, BlackBerry®, Android®, and so on. Base station  102  facilitates network communication between mobile devices such as UEs  106 - 107  with S-GW  121  via radio towers  110 . It should be noted that base station or cell site can include additional radio towers as well as other land switching circuitry. 
     Server  124  is coupled to P-GW  120  and base stations  102 - 104  via S-GW  121  or  122 . In one embodiment, server  124  which contains a soft decoding scheme is able to distribute and/or manage soft decoding and/or hard decoding based on predefined user selections. In one exemplary instance, upon detecting a downstream push data  130  addressing to mobile device  106  which is located in a busy traffic area or noisy location, base station  102  can elect to decode the downstream using the soft decoding scheme distributed by server  124 . One advantage of using the soft decoding scheme is that it provides more accurate data decoding, whereby overall data integrity may be enhanced. 
     When receiving bit-streams via one or more wireless or cellular channels, a decoder can optionally receive or decipher bit-streams with hard decision or soft decision. A hard decision is either 1 or 0 which means any analog value greater than 0.5 is a logic value one (1) and any analog value less than 0.5 is a logic value zero (0). Alternatively, a soft decision or soft information can provide a range of value from 0, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, and the like. For example, soft information of 0.8 would be deciphered as a highly likelihood one (1) whereas soft information of 0.4 would be interpreted as a weak zero (0) and maybe one (1). 
     A base station, in one aspect, includes one or more FEABs  128 . For example, FEAB  128  can be a transceiver of a base station or eNodeB. In one aspect, mobile devices such tables or iPad®  107  uses a first type of RF signals to communicate with radio tower  110  at sector  102  and portable device  108  uses a second type of RF signals to communicate with radio tower  112  at sector  104 . In an exemplary embodiment, the FEAB  128  comprises an exemplary embodiment of a PVP  152 . After receiving RF samples, FEAB  128  is able to process samples using the PVP  152  in accordance with the exemplary embodiments. An advantage of using the PVP  152  is to improve throughput as well as resource conservation. 
       FIG. 2  is a block diagram  200  illustrating logic flows of data streams traveling through a transceiver that includes a programmable mixed-radix processor in accordance with the exemplary embodiments of the present invention. Diagram  200  includes user equipment (“UE”)  216 , uplink front end (“ULFE”)  212 , transceiver processing hardware (“TPH”)  220 , and base station  112 . Base station  112  is capable of transmitting and receiving wireless signals  224  to and from TPH  220  via an antenna  222 . It should be noted that the underlying concept of the exemplary embodiments of the present invention would not change if one or more devices (or base stations) were added or removed from diagram  200 . 
     The TPH  220 , in one example, includes MMSE  202 , DFT/IDFT  204 , and demapper  206 , and is able to process and/or handle information between antenna  222  and a decoder. The information includes data and control signals wherein the control signals are used to facilitate information transmission over a wireless communication network. While MMSE may include an estimator able to provide an estimation based on prior parameters and values associated with bit streams, DFT/IDFT  204  converts symbols or samples between time and frequency domains. After conversion, DFT/IDFT  204  may store the symbols or samples in a storage matrix. 
     In one embodiment, DFT/IDFT  204  includes one or more programmable vector processors that determine DFT/IDFT values. Depending on the applications, DFT/IDFT  204  can transmit determined symbols to the next logic block such as demapper  208 . In an exemplary embodiment, the storage matrix is a local storage memory which can reside in DFT/IDFT  204 , demapper  206 , or an independent storage location. 
     The MMSE  202 , in one example, includes an equalizer with serial interference cancellation (“SIC”) capability and provides possible processing paths between TPH and SIC path. MMSE  202 , which can be incorporated in TPH  220 , generates estimated value using a function of mean-square-error or equalization of received signals or bit stream(s) during the signal processing phase. MMSE  202  also provides functionalities to equalize multiple streams of data received simultaneously over the air. For instance, the number of bit streams such as one (1) to eight (8) streams can arrive at antenna  222  simultaneously. MMSE  202  also supports frequency hopping and multi-cluster resource block (“RB”) allocations. Note that the frequency offset may be used to compensate channel estimates before performing time interpolation. Time interpolation across multiple symbols may be performed in multiple modes. 
     The Demapper  206 , in one aspect, includes a first minimum function component (“MFC”), a second MFC, a special treatment component (“STC”), a subtractor, and/or an LLR generator. A function of demapper  206  is to demap or ascertain soft bit information associated to received symbol(s) or bit stream(s). For example, demapper  206  employs soft demapping principle which is based on computing the log-likelihood ratio (LLR) of a bit that quantifies the level of certainty as to whether it is a logical zero or one. To reduce noise and interference, demapper  206  is also capable of discarding one or more unused constellation points relating to the frequency of the bit stream from the constellation map. 
     In an exemplary embodiment, the DFT/IDFT  204  converts signals between the frequency domain and the time domain using a discrete Fourier transform (“DFT”) and an inverse DFT (“IDFT”). The DFT and IDFT can be defined as; 
     
       
         
           
             
               DFT 
               ⁢ 
               
                 : 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 X 
                 ⁡ 
                 
                   [ 
                   k 
                   ] 
                 
               
             
             = 
             
               
                 ∑ 
                 
                   n 
                   = 
                   0 
                 
                 
                   N 
                   - 
                   1 
                 
               
               ⁢ 
               
                 
                   x 
                   ⁡ 
                   
                     [ 
                     n 
                     ] 
                   
                 
                 ⁢ 
                 
                   W 
                   N 
                   kn 
                 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               IDFT 
               ⁢ 
               
                 : 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 x 
                 ⁡ 
                 
                   [ 
                   n 
                   ] 
                 
               
             
             = 
             
               
                 1 
                 
                   N 
                 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     k 
                     = 
                     0 
                   
                   
                     N 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                   
                     X 
                     ⁡ 
                     
                       [ 
                       k 
                       ] 
                     
                   
                   ⁢ 
                   
                     W 
                     N 
                     
                       - 
                       kn 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               where 
               ⁢ 
               
                   
               
               ⁢ 
               
                 W 
                 N 
               
             
             = 
             
               
                 e 
                 
                   
                     - 
                     2 
                   
                   ⁢ 
                   π 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     j 
                     / 
                     N 
                   
                 
               
               . 
             
           
         
       
     
     In the above expressions, the output is properly scaled after all radix states so that the average power of DFT/IDFT output is the same as the input. 
       FIG. 3  is a table  300  showing DFT/IDFT sizes with respect to index and resource block (“RB”) allocations in accordance with exemplary embodiments of the present invention. In one embodiment, LTE networks are generally required to support many different configurations using different DFT sizes with mixed radix computations. For example, an N-point DFT can be determine from the following radix factorization.
 
 N= 2 α 3 β 5 γ 
 
     Thus, for a DFT of size N, a factorization can be determined that identifies the radix2, radix3 and radix5 computations to be performed to compute the DFT result. In various exemplary embodiments, the PVP operates to use a vector pipeline and associated vector feedback path to perform an iterative process to compute various radix factorizations when determining DFT/IDFT values. 
       FIG. 4  is a block diagram illustrating an exemplary embodiment of a PVP  400  in accordance with the present invention. In one embodiment, the PVP  400  comprise one single programmable vector mixed-radix engine  414  that is a common logic block reused for all the different radix sizes calculations. Thus, the vector engine  414  is reused iteratively as the ALU (Arithmetic Logic Unit) of the PVP  400 . Complex control logic and memory sub-systems are used as described herein to load/store data in a multiple-stage radix computation by iteratively feeding data to the single vector mixed-radix engine  414 . In another exemplary embodiment, multiple vector engines  414  are utilized. 
     Exemplary embodiments of the PVP  400  satisfy the desire for low power consumption and reduced hardware resources by iteratively reusing a single pipelined common vector data-path for all possible combinations of mixed-radix computations, yet still achieving streaming in/output data throughput of multiple samples/cycle with much less logic utilization. Besides its much higher performance to power/area ratio over conventional architectures, exemplary embodiments of the PVP  400  achieve much higher scalability and programmability for all possible mix-radix operations. 
     In an exemplary embodiment, the PVP  400  also comprises vector input shuffling controller  402 , ping-pong memory bank  404 , vector load unit  406 , vector dynamic scaling unit  408 , vector input staging buffer  410 , vector data twiddle multiplier  412 , vector output staging buffer  416 , vector dynamic scaling factor calculator  418 , vector store unit  420 , dynamic twiddle factor generator  422 , vector memory address generator  424 , finite state machine controller  426 , configuration list  428  output interface streamer  430  and in-order output vector ping-pong buffer  432 . In an exemplary embodiment, the vector load unit  406 , vector dynamic scaling unit  408 , vector input staging buffer  410 , and vector data twiddle multiplier  412  form a vector data-path pipeline  448  that carries vector data from the memory  404  to the vector mixed-radix engine  414 . The vector output staging buffer  416 , vector dynamic scaling factor calculator  418 , and vector store unit  420  for a vector feedback data-path  484  that carries vector data from the vector mixed-radix engine  414  to the memory  404 . 
     In an exemplary embodiment, the finite state machine controller  426  receives an index value  450  from another entity in the system, such as a central processor of the DFT/IDFT  204 . Using the index value, the state machine  426  accesses the configuration information  428  to determine the size (N) of the DFT/IDFT to be performed. For example, the configuration information  428  includes the table  300  that cross-references index values with size (N) values. Once the DFT/IDFT size is determined, the state machine  426  accesses the configuration information  428  to determine a factorization that identifies the number and type of radix computations that need to be performed to complete the DFT/IDFT operation. 
     Once the radix factorization is determined, the state machine  426  provides input shuffling control signals  452  to the vector input shuffling controller  402  that indicate how input data  434  is to be written into the memory  404  to allow efficient readout into the vector pipeline  448 . The state machine  426  also provides address control signals  454  to the vector memory address generator  424  that indicate how memory addresses are to be generated to read-out, store, move and otherwise process data throughout the PVP  400 . The state machine  426  also generated twiddle factor control (TFC) signals  456  that are input to twiddle factor generator  422  to indicate how twiddle factor are to be generated for use by the twiddle multiplier  412 . The state machine  426  also generates scaling control signals  458  that are input to the scaling unit  408  to indicate how pipeline vector data is to be scaled. The state machine  426  also generates radix engine control signals  460  that indicate how the mixed radix engine is to perform the DFT/IDFT calculations based on the radix factorization. 
     In an exemplary embodiment, the vector input shuffling controller  402  receives streaming input data  434  at the draining throughput of the previous module in the system with a rate of up to 12 samples/cycle. However, this is exemplary and other rates are possible. The shuffling controller  402  uses a vector store operation to write the input data  434  into the ping-pong vector memory bank  404 . For example, the shuffling controller  402  receives the control signals  452  from the state machine  426  and address information  462  from the address generator  424  and uses this information to shuffling and/or organize the input data  434  so that it can be written into the memory bank  404 . For example, parallel data path  436  carries parallel input data to be written to the ping-pong memory bank  404 . After the shuffling operation, all the data are stored in a matrix pattern in the ping-pong vector memory bank  404  to allow efficient data read-out to facilitate the selected multi-stage radix-operation with in-order write-back. In an exemplary embodiment, the ping-pong memory bank  404  includes “ping” and “pong” memory banks that may be selectively written to or read from to facilitate efficient data flow. 
     In an exemplary embodiment, the vector load unit  406  reads the data in parallel for the multiple radix-operations from either the ping or pong memory banks  404  to feed the down-stream operations. For example, the vector load unit  406  receives address information  464  from the address generator  424  which indicates how data is to be read from the memory bank  404 . For example, parallel data path  438  carries parallel data read from the ping-pong memory banks  404  to the vector load unit  406 . The vector load unit  406  can generate full throughput (e.g., 12 samples/cycle) at the output of vector load unit  406  with no interruption. For example, parallel data path  440  carries parallel data output from the vector load unit  406  to the scaling unit  408 . 
     In an exemplary embodiment, the vector dynamic scaling unit  408  scales all the parallel samples within one cycle to keep the signal amplitude within the bit-width of the main data-path after each stage of radix computation. A scaling factor  466  is calculated by the vector dynamic scaling factor calculator  418  without stalling the pipeline for each iteration. The scaling factor  466  and the scaling control signals  458  are used by the vector dynamic scaling unit  408  to perform the scaling operation. For example, parallel data path  442  carries scaled parallel data output from the vector dynamic scaling unit  408  after the scaling operation is performed. 
     In an exemplary embodiment, the vector input staging buffer  410  comprises an array of vector registers that are organized in a matrix pattern. The scaled vector-loaded data originating from the main ping-pong memory bank  404  and carried on data path  442  is written column-wise into the array of vector staging registers. The registers are then read out row-wise to form the parallel data input to the vector data twiddle multiplier  412 . For example, the data path  444  carries parallel data output from the vector input staging buffer  410  to the vector data twiddle multiplier  412 . 
     In an exemplary embodiment, vector data twiddle multiplier  412  multiplies the scaled and staged samples with twiddle factors received by the dynamic twiddle factor generator  422  over signal path  466 . The dynamic twiddle factor generator  422  receives the TFC  456  and generates twiddle factors to be multiplied with the scaled data. The vector data twiddle multiplier  412  generates 12 samples/cycle of input for radixes (2,3,4,6) scenarios or 10-samples for the radix-5 scenario to feed into the programmable vector mix-radix engine  414  using signal path  446 . 
     The mixed-radix engine  414  uses a pipelined data-path to implement multiple vector radix operations for all the different radix-factorization schemes. It is controlled by a radix-mode program controller  482  within the engine for each iteration stage. The engine data-path reuses the same logic for all the different combinations of radix operations. As an example, it can reuse the common functional logic to compute multiple radix3, radix4, radix5 and radix6 computations with no pipeline stall. For example, in an exemplary embodiment, the engine  414  can be reconfigured to compute four (4) radix3, three (3) radix4, two (2) radix5, or two (2) radix6 computations with no pipeline stall. A more detailed description of the mixed radix engine  414  is provided below. 
     The vector memory address generator  424  operates to provide memory address and control information to the vector input shuffling controller  402 , vector load unit  406 , vector store unit  420  (see A), vector output staging buffer  416  (see B), and the output interface streamer  430 . The addresses coordinate the flow of data into the memory bank  404  and through the pipeline  448  to the mixed radix engine  414 . Processed data is output from the engine  414  and input to the vector output staging buffer  416  on the vector feedback data path  484  that leads back to the ping-pong memory  404 . For example, after the data passes through the vector dynamic scaling factor calculator  418 , it flows to the vector store unit  420 , which uses the address information (A) it receives to store the data back into the ping-pong memory  404 . 
     In an exemplary embodiment, the PVP  400  determines a DFT/IDFT conversion by performing multiple iterations where in each iteration, a particular radix calculation is performed. Thus, in an exemplary embodiment, after performing intermediate radix computations, the intermediate results are stored back into the memory  404 . For example, the intermediate radix results are output to the vector output staging buffer  416  using the vector data path  468 . The vector output staging buffer  416  uses address and control information (B) received from the address generator  424  to receive the intermediate radix results and output the results in an appropriate order the vector dynamic scaling factor calculator  418  using vector data path  470 . 
     The vector dynamic scaling factor calculator  418  calculates scaling factors from the received radix results and outputs the scaling factors  466  to the dynamic scaling factor unit  408 . The radix results are then forward to the vector store unit  420  using vector data path  472 . The vector store unit  420  receive address and control information (A) from the address generator  424  and stored the received vector data in the ping-pong memory bank  404  according to the received control and address information. In an exemplary embodiment, the intermediate vector radix results are stored in-place corresponding to the data that was used to generate the radix results. In an exemplary embodiment, the staging buffer  416 , scaling factor calculator  418  and vector store unit  420  form a vector feedback data path  484  to allow results from the mixed radix engine  414  to be stored into the memory  404 . 
     In an exemplary embodiment, a final iteration is performed where the mixed radix engine  414  computes a resulting DFT/IDFT. The results are output from the output staging buffer  416  to the output interface streamer  430  using vector data path  476 . The output interface streamer  430  receive processed data from the mixed radix engine  414  and outputs this data to the in-order output vector ping-pong buffer  432  using the vector data path  478 . The in-order output vector ping-pong buffer  432  outputs the DFT/IDFT data  480  to downstream entities in the correct order. 
     Computational Iterations 
     In an exemplary embodiment, the PVP  400  operates to compute a desired DFT/IDFT using multiple iterations where in each iteration a particular radix calculation is performed. For example, the PVP  400  initially computes a radix factorization to determine the radix computations to be made to compute the DFT/IDFT for the given point size N. Data is stored in the memory  404  and read out into the vector pipeline  448  where it is scaled, staged, and multiplied by twiddle factors. The results are input to the mixed radix engine  414  that is configured to perform a first radix computation. The intermediate radix result is written back to the memory bank  404  using the vector feedback path  484 . A next iteration is performed to compute the next radix factor. The radix engine  414  is reconfigured to compute this next radix factor. The iterations continue until the complete DFT/IDFT is computed. The radix engine  414  then outputs the final result through the output staging buffer  416  to the output interface streamer  430  using path  476 . Thus, to determine an N-point DFT/IDFT, a radix factorization is determined that is used to perform a selected number of iterations to calculate each radix factor. For each iteration the radix engine  414  is reconfigured to compute the desired radix computation. As a result, the PVP  400  uses a pipeline architecture to compute DFT/IDFT values with high speed and efficiency, while the reconfigurable radix engine  414  utilizes fewer resources. 
       FIG. 5  is a block diagram illustrating a detailed exemplary embodiment of a programmable vector mixed-radix processor  500  in accordance with exemplary embodiments of the present invention. For example, the processor  500  is suitable for use as the programmable vector mixed-radix engine  414  shown in  FIG. 4 . The processor  500  includes multiple stages (S 0 -S 5 ) that include complex ALU (Arithmetic Logic Unit) Arrays (e.g., shown at  508 ,  510 , and  512 ) and connecting multiplexers (e.g., shown at  502 ,  504  and  506 ). The multiplexers and the ALUs of the stages (S 0 -S 5 ) are configurable to allow the processor  500  to perform R2, R3, R4, R5, and R6 radix computations. 
     In an exemplary embodiment, the radix-mode program controller  482  comprises the data-path programmer  514  and the LUT  516 . The data-path programmer  514  comprises at least one of logic, a processor, CPU, state machine, memory, discrete hardware and/or other circuitry that operates to allow the programmer  514  to reconfigure the ALU arrays and multiplexers based on the received radix engine control signals  460 . A small LUT (Look Up-Table)  516  holds a set of constant scaling values for the radix equations. 
     In an exemplary embodiment, vector input data (IN D 0 -D 11 ) is received at the mux  502 . The vector input data is received from the twiddle multiplier  412  such that the generated twiddle factors have already been applied to the data. The mux  502  is configured by the programmer  514  based on the received radix engine control signals  460  to connect the input data to the ALU  508  in a particular connection pattern. The ALU  508  is configured by the programmer  514  to perform arithmetic operations (such as add the data and/or constants together) based on the received radix engine control signals  460 . The results of the arithmetic operations of the ALU  508  (S 0  D 0 -D 11 ) are input to the mux  504  of stage S 1 . 
     In an exemplary embodiment, the stage S 1  operates similarly to the stage S 0 . The mux  504  receives the data (S 0  D 0 -D 11 ) output from the stage S 0  and connects this input data to the ALU  510  in a particular connection pattern. The mux  504  is configured by the programmer  514  based on the received radix engine control signals  460 . The ALU  510  is configured by the programmer  514  to perform arithmetic operations (such as add and/or multiply the data and/or constants together) based on the received radix engine control signals  460 . The results of the arithmetic operations of the ALU  510  (S 1  D 0 -D 11 ) are input to the mux of stage S 2  (not shown). 
     In an exemplary embodiment, the stages S 2 -S 4  operates similarly to the stage S 1 . The stage S 4  outputs data (S 4  D 0 -D 11 ) that has been processed by these stages configured by the programmer  514  according to the received radix control signals  460 . The mux  506  of the stage S 5  receives the data processed by the stage S 4  and connects this input data to the ALU  512  in a particular connection pattern. The mux  506  is configured by the programmer  514  based on the received radix engine control signals  460 . The ALU  512  is configured by the programmer  514  to perform arithmetic operations (such as add and/or multiply the data and/or constants together) based on the received radix engine control signals  460 . The results of the arithmetic operations of the ALU  512  (OUT D 0 -D 11 ) are output from the processor  500 . Thus, the processor  500  is re-configurable to perform a variety of radix computations on data received from the twiddle multiplier  412  of the pipeline  448 . The radix computations include radix3, radix4, radix5 and radix6 DFT computations. 
       FIG. 6  is a block diagram of a radix3 configuration  600  for use with the programmable vector mixed-radix processor  500  in accordance with exemplary embodiments of the present invention. For example, the stages (S 0 -S 5 ) of the processor  500  can be configured to perform a radix3 computation using the configuration  600 . In an exemplary embodiment, three data bits (d 0 -d 2 ) are input to the configuration  600 . The input data is added and a multiplication block  602  and a shift block  604  are utilized to generate three output bits (v 0 -v 2 ) that represent the radix3 computation. 
       FIG. 7  is a block diagram of a radix4 configuration  700  for use with the programmable vector mixed-radix processor  500  in accordance with exemplary embodiments of the present invention. For example, the stages (S 0 -S 5 ) of the processor  500  can be configured to perform a radix4 computation using the configuration  700 . In an exemplary embodiment, four data bits (d 0 -d 3 ) are input to the configuration  700 . The input data is added and a multiplication block  704  is utilized to generate four output bits (v 0 -v 3 ) that represent the radix4 computation. 
       FIG. 8  is a block diagram of a radix5 configuration  800  for use with the programmable vector mixed-radix processor  500  in accordance with exemplary embodiments of the present invention. For example, the stages (S 0 -S 5 ) of the processor  500  can be configured to perform a radix5 computation using the configuration  800 . Five data bits (d 0 -d 4 ) are input to the configuration  800 . Addition blocks (e.g.,  802 ), multiplication blocks (e.g.,  804 ), and shift block  806  are utilized to generate five output bits (v 0 -v 4 ). 
       FIG. 9  is a block diagram of a radix6 configuration  900  for use with the programmable vector mixed-radix processor  500  in accordance with exemplary embodiments of the present invention. For example, the stages (S 0 -S 5 ) of the processor  500  can be configured to perform a radix6 computation using the configuration  900 . Six data bits (d 0 -d 5 ) are input to the configuration  900 . The data bits are input to two blocks  902  and  904  that are configured for radix3 operation as shown in block  600 . The outputs of the block  902  and  904  are combined to generate six output bits (v 0 -v 5 ). 
       FIG. 10  is a block diagram illustrating a configurable vector mixed-radix engine  1000  in accordance with one embodiment of the present invention. For example, the engine  1000  is suitable for use as the engine  500  shown in  FIG. 5 . The engine  1000  comprises a radix-operator data-path that is configured to compute selected radix modes. In an exemplary embodiment, the radix-mode can be four parallel radix3 computations (4vR3 as shown in block  1002 ), or three parallel radix4 computations (3vR4 as shown in block  1004 ), or two parallel radix5 computations (2 vR5 in block  1006 ), or two parallel radix6 computations (2vR6 in block  1008 ). After each configuration is selected, data can be pipelined into each run-time data-path with no stall within the iteration stage. The input and output of 12-samples are selected according to the radix-mode and stage index based on the DFT/IDFT algorithm. 
       FIG. 11  illustrates an exemplary digital computing system  1100  that comprises a programmable vector processor having a configurable vector mixed-radix engine with iterative pipeline in accordance with embodiments of the invention. It will be apparent to those of ordinary skill in the art that the programmable mixed-radix processor with iterative pipelined vector engine is suitable for use with other alternative computer system architectures. 
     Computer system  1100  includes a processing unit  1101 , an interface bus  1112 , and an input/output (“IO”) unit  1120 . Processing unit  1101  includes a processor  1102 , main memory  1104 , system bus  1111 , static memory device  1106 , bus control unit  1105 , and mass storage memory  1107 . Bus  1111  is used to transmit information between various components and processor  1102  for data processing. Processor  1102  may be any of a wide variety of general-purpose processors, embedded processors, or microprocessors such as ARM® embedded processors, Intel® Core™2 Duo, Core™2 Quad, Xeon®, Pentium™ microprocessor, AMD® family processors, MIPS® embedded processors, or Power PC™ microprocessor. 
     Main memory  1104 , which may include multiple levels of cache memories, stores frequently used data and instructions. Main memory  1104  may be RAM (random access memory), MRAM (magnetic RAM), or flash memory. Static memory  1106  may be a ROM (read-only memory), which is coupled to bus  1111 , for storing static information and/or instructions. Bus control unit  1105  is coupled to buses  1111 - 1112  and controls which component, such as main memory  1104  or processor  1102 , can use the bus. Mass storage memory  1107  may be a magnetic disk, solid-state drive (“SSD”), optical disk, hard disk drive, floppy disk, CD-ROM, and/or flash memories for storing large amounts of data. 
     I/O unit  1120 , in one example, includes a display  1121 , keyboard  1122 , cursor control device  1123 , decoder  1124 , and communication device  1125 . Display device  1121  may be a liquid crystal device, flat panel monitor, cathode ray tube (“CRT”), touch-screen display, or other suitable display device. Display device  1121  projects or displays graphical images or windows. Keyboard  1122  can be a conventional alphanumeric input device for communicating information between computer system  1100  and computer operator(s). Another type of user input device is cursor control device  1123 , such as a mouse, touch mouse, trackball, or other type of cursor for communicating information between system  1100  and user(s). 
     Communication device  1125  is coupled to bus  1111  for accessing information from remote computers or servers through wide-area network. Communication device  1125  may include a modem, a router, or a network interface device, or other similar devices that facilitate communication between computer  1100  and the network. In one aspect, communication device  1125  is configured to perform wireless functions. 
     In one embodiment, DFT/IDFT component  1130  is coupled to bus  1111  and is configured to provide a high-speed programmable vector processor having a configurable vector mixed-radix engine with iterative pipeline in accordance with embodiments of the invention. For example, DFT/IDFT  1130  can be configured to include the PVP  400  shown in  FIG. 4 . The DFT/IDFT component  1130  can be hardware, hardware executing software, firmware, or a combination of hardware and firmware. For example, the component  1130  operates to receive streaming data and compute a desired N-point DFT that is output from the component  1130 . Accordingly, the component  1130  may also operate to compute a desired IDFT. 
       FIG. 12  illustrates an exemplary method  1200  for operating a programmable vector processor having a configurable vector mixed-radix engine with iterative pipeline in accordance with embodiments of the invention. For example, the method  1200  is suitable for use with the PVP  400  shown in  FIG. 4 . 
     At block  1202 , a radix factorization is determined. For example, a radix factorization is determined to compute an N-point DFT associated with a particular index value. For example, the index value  450  for the N-point DFT to be computed is received at the state machine controller  426 , which accesses the configuration information  428  to determine a radix factorization which can be used to compute the DFT. 
     At block  1204 , memory accesses and pipeline components are configured based on the radix factorization. For example, based on the determined radix factorization, the state machine controller  426  determines how many iterations and radix computations it will take to compute the desired DFT. The state machine  426  outputs control signals  452  to the shuffling controller  402  to control how input data is stored in the memory  404 . The state machine  426  outputs control signals  454  to control how memory addresses and control signals are generated by the address generator  424 . These addresses and control signals are used control how data is transmitted through the vector pipeline  448  and the vector feedback path  484  for each iteration of the DFT computation. 
     At block  1206 , the configurable vector mixed-radix engine is configured to perform a first radix computation. For example, the state machine  426  outputs radix control signals  460  to the program controller  448  and the programmer  514  uses these signals to configure the stages (S 0 -S 5 ) (e.g., vector engines) of the mixed-radix engine  500  to perform the selected radix computation, such as a radix3, radix4, radix5, or radix 6 computation. For example, the stages are configured to one of the configurations shown in  FIG. 10  to perform the selected radix computation. 
     At block  1208 , vector data is read from the memory into the vector pipeline. For example, input data stored in the memory  404  is read out and input to the pipeline  448 . In an exemplary embodiment, the vector data is input to the pipeline  448  at a rate of 12 samples per cycle. In an exemplary embodiment, the data is stored in the memory in a shuffled fashion according to the radix factorization and then read out from the memory in sequential fashion. 
     At block  1210 , vector scaling, staging, and twiddle factor multiplication of the vector data is performed. For example, the vector data is scaled by the scaling unit  408 , staged by the staging buffer  410 , and multiplied by twiddle factors at the twiddle multiplier  412 . 
     At block  1212 , the selected radix computation is performed. For example, the mixed-radix engine  500  performs the selected radix computation, such as a radix3, radix4, radix5, or radix 6 computation) as configured by the programmer  514 . 
     At block  1214 , a determination is made as to whether additional radix computations are required to complete the computation of the desired DFT. If additional radix computations are required, the result is output on the vector feedback path  484  to the staging buffer  416  and the method proceeds to block  1216 . If no additional computations are required and the computation of the DFT is complete, the method proceeds to block  1222 . 
     At block  1216 , a scaling factor is updated. For example, the results of the radix computation flow to the scaling factor calculator  418 , which calculates a new scaling factor and outputs this scaling factor  466  to the scaling unit  408 . 
     At block  1218 , the result of the radix computation is stored in memory. For example, the results of the radix computation a stored in the memory  404  by the vector store unit  420 . In an exemplary embodiment, the radix result is stored (in-place) at the same memory locations as the initial data used to compute the result. 
     At block  1220 , the mixed-radix engine  500  is reconfigured to perform the next radix calculation. For example, the state machine  426  outputs radix control signals  460  to the program controller  448  and the programmer  514  uses these signals to configure the stages (S 0 -S 5 ) (e.g., vector engines) of the mixed-radix engine  500  to perform the next radix computation, such as a radix3, radix4, radix5, or radix 6 computation. For example, the stages are configured to one of the configurations shown in  FIG. 10  to perform the selected radix computation. The method then proceeds to block  1208  to perform the next iteration. 
     At block  1222 , the N-point DFT is output. For example, the mixed radix engine  414  outputs the DFT result through the output staging buffer  416  to the output interface streamer  430 , which is turn streams the result to the buffer  432 . The buffer  432  then outputs the DFT result to a downstream entity. 
     Thus, the method  1200  illustrates a method for operating a programmable vector processor having a configurable vector mixed-radix engine with iterative pipeline in accordance with embodiments of the invention. In an exemplary embodiment, the method is computes an N-point DFT as described above. In another exemplary embodiment, the method computes an N-point IDFT. For example, to compute the IDFT, at block  1210 , the twiddle factors are adjusted (e.g., sign change) such that the result is an IDFT. Accordingly, the method  1200  operates to compute either a DFT or an IDFT in accordance with the exemplary embodiments. 
     Vector Memory Subsystem 
     Memory organization and addressing procedure provide an important role in achieving high Data-Level-Parallelism (“DLP”) for high throughput DFT/IDFT engine design with efficient logic resource utilization. In exemplary embodiments, the vector memory subsystem (“VMS”) as shown in  FIG. 4  is formed by the vector input shuffling controller  402 , ping-pong vector memory bank  404 , vector memory address generator  424 , finite state machine controller  426  and the configuration LUT  428 . The VMS generates memory addresses for each stage of the pipelined DFT/IDFT operation. It should be noted that although VMS illustrated in  FIG. 4  is directed to the framework of DFT architecture, it is applicable in other architecture contexts. 
     In one aspect, the VMS discloses a method and apparatus for efficient layout and organization of the ping-pong vector memory banks  404 , which are reused in different configurations for radix-operations in various DFT sizes and configurable radix-factorizations. The VMS, in one embodiment, also includes the vector memory address generator (“VMAG”)  424 . VMAG  424  is able to provide a multi-sector/multi-bank memory organization mechanism to allow a high level of Data-Level Parallelism (“DLP”) and a vector shuffling operation with write (WR) address generation based on various configurable parameters (e.g., radix-factorization vector, DFT_index and current stage etc.) to store the initial input data into multi-section vector memory. VMAG  424  is also configured to provide a vector load method and procedure with read (RD) address generation to feed the vector DFT engine. The VMAG  424  also provides a vector store method and procedure with write-back address generation to write-back intermediate results to the ping-pong memory bank  404 . VMAG  424  also provides an efficient write-out method and procedure to stream out the vector results at the last-stage through interface streamer  430 . Note that VMS using the VMAG  424  allows up to 12 samples/cycle vector store/load, and is the key to achieving greater than 2 samples/cycle throughput in the DFT/IDFT implementation. 
     It should be noted that even for different architectures, computation of the DFT/IDFT involves the same multi-stage computations. The address generation is closely related to the iterative computation process of the DFT/IDFT algorithm. In an exemplary embodiment, the DFT/IDFT is calculated in an iterative procedure following the “divide &amp; conquer” principle as follows.
     A. A large data block is divided into smaller equal-sized blocks and then processed with smaller sized-DFT on divided sub-blocks.   B. For example, in DIT (Decimation-In-Time) the dividing process is in the backward direction from output to input;   C. For a stage of Radix-r, r sub-blocks of size n are merged into r*n sized parent sub block.   

     The iterative algorithm works in multiple stages to generate the final result of an N-point DFT/IDFT. For example, if the last stage is a radix-r, it is generated from r sub-blocks of n=N/r point FFT. For example, assuming data stored in a data matrix from the previous stage output as: 
                 D     r   ×   n       =       [           d     0   ,   0             d     0   ,   1             d     0   ,   2           …         d     0   ,     n   -   1                   d     1   ,   0             d     1   ,   1             d     1   ,   2           …         d     1   ,     n   -   1                   d     2   ,   0             d     2   ,   1             d     2   ,   2           …         d     2   ,     n   -   1                 …                                                             d       r   -   1     ,   0             d       r   -   1     ,   1             d     0   ,   2           …         d       r   -   1     ,     n   -   1               ]       r   ×   n         ,         
where each row is a sub-block of size n, the output of an n-point FFT. Let the twiddle factors also be stored in a matrix format as:
 
                 T     r   ×   n       =       [         1       1       1       …       1           1         W   1           W   2                       W     (     n   -   1     )               1         W   2           W   4                       W     2   ⁢     (     n   -   1     )                 ⋮                                                           1         W     (     r   -   1     )             W     2   ⁢     (     r   -   1     )                           W       (     r   -   1     )     ⁢     (     n   -   1     )               ]       r   ×   n         ,     W   =       e       -   j     ⁢       2   ⁢   π       r   ×   n           .             
where {tilde over (D)} r×n =D r×n ∘T r×n  is the Hadamard product of the data matrix and the twiddle factor matrix. Then each column of {tilde over (D)} r×n  will be the input of the radix-r operator.
 
       FIG. 13  illustrates an exemplary embodiment of a 1080-point DFT configuration  1300  with radix factorization having five stages as in RV=[5,3,3,6,4] in accordance with the exemplary embodiments of the invention. The configuration  1300  shows the multiple stage computation procedure from r smaller DFT size n to form multiple larger DFT of size r×n. In each stage, the memory is organized as a single serial memory that only allows one read/write access per clock cycle. Thus, the processing throughput is quite limited. 
       FIG. 14  illustrates an exemplary embodiment of a memory configuration  1400  for a 1080-point DFT that utilizes a virtual folded memory with iterative DFT process in accordance with the exemplary embodiments of the invention. In the configuration  1400 , the radix factorization includes the five stages as in RV=[5,3,3,6,4]. In an exemplary embodiment, the VMS organizes the memory to support Single-Instruction Multiple-Data (SIMD) to output 12 samples per cycle (e.g., single access). The VMS sets up an iterative DFT process with three virtual memory banks (shown at  1402 ,  1404 , and  1406 ) of SIMD width of 4 (SIMD4), or 1 bank of SIMD width of 12 (SIMD12), by utilizing the data level parallelism of the independent smaller size DFT computations in the stages before the last two stages. 
     The following parameters are defined for the multi-stage iterative address generation:
     A. Ns: Number of stages;   B. N_DFT: the length of the DFT data;   C. RV[Ns]: the radix vector factorization;   D. CurRadix: r in the above equations, the radix size for current stage;   E. SBSizeIn: n in the above equations, the DFT size of previous stage, i.e., input sub-block size for current stage;   F. N_SBlks: The number of independent r×n sub block DFTs for a length N_DFT data.   G. NFFT_CurStage: The DFT size of the current stage, which is =r×n.   

     The features of the vector memory design, in one embodiment, include the virtual folded parallel memory with iterative procedure of SIMD12 using the single-port ping-pong memory buffer  404  to achieve the data-level parallelism for all the DFT-sizes in LTE applications. The radix vector for all the 35 different N_DFTs is arranged to have radix-4 in the last stage (e.g., the (Ns−1) th  stage) and either radix-3 or radix-6 for the stage before the last stage (e.g., (Ns−2) th  stage). The memory is first folded to support parallel radix-4 operation for the last stage by having a SIMD of multiple of 4. By fixing RV[Ns−1]=4, the SIMD12 memory is divided to 1 or 2 sections depending on the radix factorization vector for the last two stages. 
       FIG. 15  illustrates exemplary embodiments of memory organizations in accordance with the exemplary embodiments of the invention. As shown in  FIG. 15 , in one embodiment, the memory of the memory bank  404  is organized as one section  1502  for the cases of radix vectors {3, 4} in the last two stages of the radix factorization or in two sections  1504  for the case of radix vectors {6,4} in the last two stages of the radix factorization. If (RV[Ns−2]=3) then the 128-entry memory is treated as a single section  1502 . If (RV[Ns−2]=6) then the 128-entry memory is treated as two sections  1504 . Examples of such radix factorizations include, but are not limited to: {5,3,3,6,4}, {6,6,6,4}, {6,5,6,4}, {5,5,6,4}, {6,4,6,4}. 
     In an exemplary embodiment, a method to compute the multi-stage DFT/IDFT iteratively in a single common vector radix-engine is summarized as follows:
     Phase 1: Input data to the memory bank  404  before the computation is started. Data is written into the memory  404  in a shuffled pattern in this phase. In an exemplary embodiment, the pattern is determined from an InputDataFFT( ) procedure as shown below.   Phase 2: If the number of radix factorization stages is &gt;2, then an iterative process is called for the first (Ns−2) stages as shown in the exemplary procedure DFT_MidStages_Proc( ) shown below.   Phase 3: The procedure for the (Ns−2) th  stage is called to do either radix-3, or radix-6 operation.   Phase 4: The last stage procedure is called to do a radix-4 operation. The data is written directly to the output vector buffer after the radix operation.   

     In an exemplary embodiment, the Vector Memory Address Generation (VMAG) includes address generation for the vector memory including address generation for the following components:
     A. Address Generation for the Input Shuffling and Vector Store Stage.   B. Address Generation for the vector load/store of stages before the last two stages.   C. Address Generation for the Stage Before Last.   D. Address Generation for the Last Stage.   

     An address generation procedure is used for input shuffling and vector store to store data into the vector memory bank  404 . In an exemplary embodiment, the address generation in this phase is performed by pseudo-code as shown in the in Table 1. After this phase, the data has been shuffled in the memory  404  into a pattern for independent sub-block DFT computation from smaller size DFTs to the final full size DFT. In an exemplary embodiment, address patterns for two scenarios are demonstrated as shown in the following two examples.
     A. 1200-point DFT with a radix factorization of {5,5,4,3,4}. The memory is treated as a single section because the fourth stage has a radix-3 operation.   B. 1080-point DFT with a radix factorization of {5,3,3,6,4}. The memory is treated as two sections (due to radix 6 in fourth stage) to hold the radix-6 data in an SIMD-12 vector memory with a last stage of radix-4.   

     
       
         
           
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 Pseudo-code for the Input Shuffling and Vector Store Phase 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                 #define MAX_NDFT 1536 
                   
               
               
                 #define MAX_NS 6 
                 // Max number of stages in the radix factorization. 
               
            
           
           
               
            
               
                 #define MAX_NS_M2 MAX_NS −2 
               
            
           
           
               
               
            
               
                 #define MB_DEPTH 128 
                 // The depth of the memory bank. 
               
               
                 #define SIMD_WIDTH 12 
                 // The SIMD width of the memory bank. 
               
            
           
           
               
            
               
                 void InputDataFFT(short NFFT, short Radix_Vect[MAX_NS], short NStages, int In[MAX_NDFT], int 
               
               
                 MEMBK[MB_DEPTH][SIMD_WIDTH]) 
               
               
                 { 
               
               
                   Short InAddr = 0; 
               
               
                   int wdIndx, i0, i1, i2, i3; 
               
               
                   int Offi0, Offi1, Offi2; 
               
               
                   int BK_AOff, BK_AOff_P2;   //Memory Bank Address Offset. 
               
               
                   short STEPS[MAX_NS] = {0,}; 
               
               
                   short RVectMAX[MAX_NS] = {1,1,1,1,1,1};   // Radix factorization vector. 
               
               
                   for (i0 =0; i0&lt;NStages−2; i0++){ 
               
               
                     RVectMAX[i0] = Radix_Vect[i0]; 
               
               
                   } 
               
               
                   STEPS[MAX_NS_M2−2] = Radix_Vect[0]; 
               
               
                   for (int SIndx = MAX_NS_M2−2; SIndx &gt;= 1; SIndx −−){ //Stage index. 
               
               
                       STEPS[SIndx −1] = STEPS[SIndx] * Radix_Vect[MAX_NS_M2 − SIndx−1];} 
               
               
                   for (i3 = 0; i3&lt;RVectMAX[0]; i3++){ 
               
               
                     Offi2 = 0; 
               
               
                     for (i2 = 0; i2&lt;RVectMAX[1]; i2++){ 
               
               
                       Offi1 = 0; 
               
               
                       for (i1 = 0; i1&lt;RVectMAX[2]; i1++){ 
               
               
                         Offi0 = 0; 
               
               
                         for (i0=0; i0 &lt;RVectMAX[3]; i0++){ 
               
               
                           BK_AOff = i3 + Offi2 + Offi1 + Offi0; 
               
               
                           for (wdIndx = 0; wdIndx &lt; SIMD_WIDTH; wdIndx++){ 
               
               
                             MEMBK[BK_AOff][wdIndx] = In[InAddr]; InAddr ++; 
               
               
                           } 
               
               
                           if ((Radix_Vect[NStages − 2] == 6)) 
               
               
                           { 
               
               
                             BK_AOff_P2 = BK_AOff + 64; 
               
               
                             for (wdIndx = 0;wdIndx &lt; SIMD_WIDTH; wdIndx++){ 
               
               
                                MEMBK[BK_AOff_P2][wdIndx] = In[InAddr]; InAddr ++; 
               
               
                             } 
               
               
                           } 
               
               
                           Offi0 = Offi0 + STEPS[0]; 
               
               
                         } 
               
               
                         Offi1 = Offi1 + STEPS[1]; 
               
               
                       } 
               
               
                       Offi2 = Offi2 + STEPS[2]; 
               
               
                     } 
               
               
                   } 
               
               
                 } 
               
               
                   
               
            
           
         
       
     
     During the write-in process, the data is written into the SIMD12 vector memory bank  404  continuously. The generated address points to the offset address within the memory bank. The offset address will be traced by starting from the last two stages. For example, 12 incoming samples are written continuously into one entry of the SIMD12 memory  404  given by the address (BK_AOff=i3+Offi2+Offi1+Offi0). If there are two memory sections use (e.g., for the case of radix-6 in the (Ns−2) th  stage), then after writing the first section, data storage will jump to the same offset address in section 2 as (BK_AOff_P2=BK_AOff+64). Then the AddrOffset addresses are generated iteratively as shown above for the first several stages. 
     Address Generation for Last Two Stages of DFT Computation 
       FIGS. 16A-C  illustrate an exemplary embodiment of a memory input data pattern for a 1200-point DFT having one section based on a radix factorization where the last two stage of the radix factorization include {x, x, x, 3, 4}. For example, the radix factorization as shown above is {5, 5, 4, 3, 4}. After the shuffling, the data is written into the addresses that allow independent radix-operations across the 12-SIMDs for the first stages. For the example of a 1200-point DFT, the first group of 12-samples are written to addresses with offset of BK_AOff=0 as shown at  1602 . The method then continues to write to BK_AOff=25 (shown at  1604 ), and then to BK_AOff=50 (shown at  1606 ) and to BK_AOff=75 (shown at  1608 ) based on the steps generated in the above procedure. The block data from addresses [0-4] is then the radix input to the first stage radix-5 operator. For stage 2, the radix-5 input data will then be picked from a stepped address corresponding to the sub-block as: [0, 5, 10, 15, 20]+i, where i=[0,4] entries. For stage-3, the radix-4 input data will be picked from [0, 25, 50, 75]+j, where j=[ 0 , 24 ]. For stage-4, the radix-3 input data will then be picked from the [W0, W4, W8]+k, where k=[0,3]. For stage-5, the radix-4 input data will then be picked from [W0, W1, W2, W3]+4*l, where l=[0,2]. The detailed procedure for the address generation for each stage is shown later. 
       FIGS. 17A-D  illustrate an exemplary embodiment of a memory input data pattern for a 1080-point DFT having two sections based on a radix factorization where the last two stage of the radix factorization include {x, x, x, 6, 4}. For example, the radix factorization is {5, 3, 3, 6, 4}. For this 1080-point DFT, the memory is partitioned into two sections because the last two stages are radix [6, 4] computations. The first group of 12-samples are written to the first section (Section 1) at addresses with offset BK_AOff=0, as shown at  1702 . The data writing continues with the next group written to the second section (Section 2) at addresses with offset BK_AOff_P2=64, as shown at  1704 . For both sections, the BK_AOff continues to jump to [30, 45]. The block data from addresses [0-4] is then the radix input to the first stage radix-5 operator. For stage 2, the radix-3 input data will be picked from a stepped address corresponding to the sub-block as: [0, 5, 10]+i, where i=[0,4] entries. And then, for stage-3, the radix-3 input data will be picked from [0, 15, 30]+j, where j=[0,14]. For stage-4, the radix-3 input data will then be picked from the [W0, W4, W8]+k from both sections, where k=[0,3]. For stage-5, the radix-4 input data will then be picked from [W0, W1, W2, W3]+4*l, where l=[0,2] from both sections separately. The detailed procedure for the address generation for each stage is shown later. 
     Address Generation for Stages Before the Last Two Stages 
     With the input data already shuffled in the pattern as above, parallel processing of multiple radices can be done by loading the data into the input staging buffer matrix  410  of size DVectREGs[6][12]. The VMS reads the vector data from the memory  404  and into the pipeline  448 . The vector data then flows the input staging buffer matrix  410 . The address generation is then done iteratively from the radix-vector and the parameters including the number of sectors, number of sub-block size, the current radix size r, and the input sub-block size n. The detailed procedure is shown in the following logic flow. 
     The address generation is then a nested loop that first goes through the number of sectors, and then the OffsetAddress within one sector, and then the number of independent sub-blocks. This process is repeated for the stages with update to the loop counters and NFFT_CurStage based on the radix vector.
 
AbsBaseAddr=SECTOR_BASE+BaseAddr+OffSetInSBlk
 
     For the 1200-point DFT example with RV=[5,5,4,3,4], the addresses for reading the memory  404  and loading the pipeline  448  for the first three stages are given as follows: 
     Stage 0: n=1, r=5, NFFT_CurStage=n*r=5, N_SBlks=(5*4*3*4)/12=20 is the number of SIMD-12 sub-blocks for the radix-5 computation. All the radix-5 operations are independent for the 12-SIMD data and there is no need to do twiddle factor multiplication and twiddle factor regeneration. The operation basically produces 20*12 independent 5-point DFTs. For example, a process called: 
     vLoadDataMBS(CurRadix,AbsBaseAddr,SBSizeIn,DVectREGS) 
     will load a matrix of data to into the staging buffer ( 410 ) DVectREGs[5][12] from the following addresses in the vector memory bank  404 : 
     [0,1,2,3,4][0˜11], 
     [5, 6,7,8,9][0˜11], 
     [10,11,12,13,14][0˜11], 
     . . . 
     [95, 96, 97, 98, 99][0˜11]. 
     The radix-5 operation is thus straightforward for the data DVectREGs[5][12]. After the radix operation is performed by the radix engine  414 , the resulting data will be written back to the same addresses in the memory  404  for each sub-block as in above order. For example, the vector memory address generator  424  generates the appropriate control and address parameters (A) that are provided to the vector store unit  420  to write the results of the radix computations back into the memory  404  at the same addresses. 
     Stage 1: n=5, r=5, NFFT_CurStage=n*r=25, N_SBlks=N_SBlks/r=4. Thus, the data will be loaded into the staging buffer  410  from the following memory addresses of the memory bank  404  in the following order for the 1 st  sub-block: 
     [0, 5, 10, 15, 20][0˜11], 
     [1, 6, 11, 16, 21][0˜11], 
     [2, 7, 12, 17, 22][0˜11], 
     [3, 8, 13, 18, 23][0˜11], 
     [4, 9, 14, 19, 24][0˜11]. 
     Similarly, the other four sub-blocks are computed as the following order. 
     [25, 30, 35, 40, 45][0˜11], 
     [26, 31, 36, 41, 46][0˜11], 
     . . . . 
     Stage 2: n=25, r=4, NFFT_CurStage=n*r=100, N_SBlks=N_SBlks/r=1. Thus, the data will be loaded into the staging buffer  410  from the following memory addresses of the memory bank  404  in the following order: 
     [0, 25, 50, 75][0˜11], 
     [1, 26, 51, 76][0˜11] 
     [2, 27, 52, 77][0˜11] 
     . . . 
     [24, 49, 74, 99][0˜11] 
       FIG. 18  illustrates an exemplary embodiment of a method  1800  for address generation for stages before the last two stages in accordance with one embodiment of the present invention. In an exemplary embodiment, the operations shown below are performed by the VMS described above. 
     At block  1802 , the DFT procedure begins. 
     At block  1804 , values are initialized. For example, values corresponding to the radix factorization, number of sectors per block, current radix value and others as described above are initialized. 
     At block  1806 , a loop on stage index begins. 
     At block  1808 , an update to stage parameters is performed. 
     At block  1810 , a procedure to look up base radix Vect_T(CurRadix, SBSizeIn) is performed. 
     At block  1812 , a variable called curRS_bits is set. 
     At block  1814 , a loop on stage block index begins. 
     At block  1816 , a variable called T_CurVect is set to a unity vector. 
     At block  1818 , a loop on Offset Input stage block begins. 
     At block  1820 , a sector base is set to zero. 
     At block  1822 , a loop on sector index begins. 
     At block  1824 , a base address is computed. 
     At block  1826 , vector data is loaded from the memory to a staging buffer. For example, the vector data passes from the memory  404  through the pipeline  448  to the input staging buffer  410 . 
     At block  1828 , a twiddle multiplication is performed on the data and a vector radix operation is performed. For example, the twiddle multiplier  412  performed the twiddle multiplication on the SIMD12 data and the radix engine  414  performs the radix calculation as described above. 
     At block  1830 , the result of the radix calculation is written to the output staging buffer  416 . 
     At block  1832 , the result in the output staging buffer is stored in the memory  404 . For example, the vector store unit  420  receives the result from the output staging buffer over the feedback path  472  and stores the result into the memory  404  at the same address locations from which the data originated. 
     At block  1834 , the sector base address is updated. 
     At block  1836 , new twiddle factors are generated for the next column of a twiddle matrix. For example, the twiddle factor generator  422  operates to generate new twiddle factors. The new twiddle factors are input to the twiddle multiplier  412 . 
     At block  1838 , the base address for the next SBlk is updated. 
     At block  1840 , the MaxValueAbs and Total RE_Bits are updated for the current stage. 
     Thus, the method  1800  provides for address generation for stages before the last two stages in accordance with one embodiment of the present invention. 
     Address Generation for Stage before the Last Stage 
     The address generation for the last two stages is different from the previous stages because of the use of SIMD12 to allow parallel processing of the last two stages. There are two scenarios for the stage before the last, radix-6 or radix-3 while the last stage is always radix-4. The memory  404  will be accessed by a SECTOR_BASE={0,64} for radix-3 and radix-6, respectively, plus the OffSetInSBlk as shown in the following equation.
 
AbsBaseAddr=SECTOR_BASE+OffSetInSBlk
 
     Each address points to one SIMD12 entry. The 12 words in one single entry are logically partitioned into 3 portions, each with 4-SIMD words (corresponding to the 3-bank counterpart, which can be referred to as 3 virtual banks). For radix-3, the three inputs are taken from each of the three virtual banks as [0,4,8]+j, where j=[0,3]. So each SIMD12 entry will make 4 parallel radix-3 operations. For the case of radix-6, the 6 inputs will be taken from two sectors of the SIMD12 entries, i.e., the [0,4,8]+j from section 0 and [0,4,8]+j from section 1. The two sections are gapped by 64 in the address space as shown above. The details can be demonstrated by the following two examples. 
     For the case of radix-3 in the stage (Ns−2), there will be only one section; n=NFFT_CurStage of the previous stage. In the example of a 1200-point DFT, n=100, r=3, NFFT_CurStage=300 for this stage. The operation will simply loop over all the SIMD12 entries to load the 12-SIMD words, and then pack them into four radix-3 inputs. In an exemplary embodiment, the address pattern can be determined from the following: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 for (OffSetInSBlk = 0 : SBSizeIn−1) 
               
               
                   
                 { 
               
               
                   
                   Load from [OffSetInSBlk][0-11]; 
               
               
                   
                 ... 
               
               
                   
                 } 
               
               
                   
                   
               
            
           
         
       
         
         A. [0][0-11]: radix-3 inputs are composed of [0,4,8]+j, J=[0,3] of the same SIMD12 entry. 
         B. [1][0˜11]: radix-3 inputs are composed of [0,4,8]+j, j=[0,3] of the same SIMD12 entry.
       . . .   
     
         C. [OffSetInSBlk][0˜11]: radix-3 inputs are composed of [0,4,8]+j, J=[0,3] of the same SIMD12 entry.
       . . .   
     
         D. [99][0˜11]: radix-3 inputs are composed of [0,4,8]+j, j=[0,3] of the same SIMD12 entry. 
       
    
     For the case of radix-6 in this stage as in the example of a 1080-point DFT, there will be two sections; n=45, r=6, NFFT_CurStage=270 for this stage. In an exemplary embodiment, the address pattern can be determined from the following: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 for (OffSetInSBlk = 0 : SBSizeIn−1) 
               
               
                   
                 { 
               
               
                   
                   SECTOR_BASE = 0; 
               
               
                   
                   short SECTOR_BASE_DVREGS = 0; 
               
               
                   
                   for (SectorIndx = 0 : 1) 
               
               
                   
                   { 
               
               
                   
                     short AbsBaseAddr = SECTOR_BASE + OffSetInSBlk; 
               
               
                   
                     load from [AbsBaseAddr][0-11]; 
               
               
                   
                     SECTOR_BASE = 64; 
               
               
                   
                   } 
               
               
                   
                 ... 
               
               
                   
                 } 
               
               
                   
                   
               
            
           
         
       
     
     As a result, the 6-inputs for the radix-6 operator is loaded from the following addresses:
     A. [0][0˜11], [64][0˜11]: 6-inputs for the radix-6 is composed from two sectors of [0,4,8]+j, j=[0,3].   B. [1][0˜11], [1+64][0˜11]: same as above, except that the AbsBaseAddr to the memory space is now 1.   C. [2][0-11], [2+64][0-11]
       . . .   
       D. [44][0˜11], [44+64][0˜11]: same as above, except that the AbsBaseAddr to the memory space is now 44.
 
Address Generation for the Last Stage
   

     Address generation for the last stage involves the following steps. The loading of the data from the memory  404  to the staging buffer  410  for the last stage first iterates for the number of entries within one section, and then iterates for the number of sections. The SIMD12 samples make the three parallel radix-4 inputs as follows: the samples [0˜3], [4˜7], [8˜11]. Because the input sub-block size n for the last stage is N_DFT/4, to allow the three vector radix processing at the last stage, it is beneficial to prepare three sets of twiddle factor vectors in parallel. In an exemplary embodiment, the twiddle factor is divided in three parts as follows since we have three vector Radix-4s. For each part, two twiddle factors will be generated in parallel incrementally. 
                         
where the decomposition is simply expressed as:
 
               T     r   ×   n       =         [       T     r   ×     n   3         ,       T     r   ×     n   3         ∘       (     T     r   ×   n     base     )       n   3         ,       T     r   ×     n   3         ∘       (     T     r   ×   n     base     )         2   ⁢   n     3           ]       r   ×   n       .           
Thus, the offset address to the SIMD12 will then grow continuously for each section.
 
     For the output to get in-order address and SIMD4 throughput, the DVectREGS[4][12], in one aspect, is used to stage the output buffer  416 . This process is shown for the following examples. 
       FIG. 19  illustrates exemplary block diagrams of data output patterns for the output to get in-order addresses and SIMD4 throughput in accordance with exemplary embodiments of the present invention. For the example of 1200-point DFT, the address grows from 0˜99 for all SIMD12 entries. The in-order output will take the first column of each virtual bank as shown at  1902 . It will then move to the second column. The output of four rows will be stages in the DVectREGS[4][12] (4×3 radix-4 outputs) at the output staging buffer  416  as shown at  1904  and then written directly to the Out_SIMD[300][4] output buffer xxx as shown at  1906 . The DVectREGS[4][12] will be direct mapping of the four rows of the MEM[128][12] as an intermediate output buffer. Thus, the mapping from the DVectREGS[4][12] to Out_SIMD[300][4] will be as gapped by the 25 when the contents are read from DVectREGS[4][12] column-wise but written to the OutSIMD[300][4] row-wise as shown at  1908 . Each row is a SIMD4 entry. This write process to OutSIMD[300][4] is done in the last stage of computation. After the last stage is done, the OutSIMD[300] [4] will be read out in SIMD4 wise and the output throughput to the Out[ 1200 ] will then be 4 samples/cycle. 
       FIGS. 20-21  illustrates exemplary block diagrams of data patterns for the last stage of VMS in accordance with one embodiment of the present invention. For the example of the 1080-point DFT, the last two stages include radix {6,4} computations. Thus, there are two sections as shown in  FIG. 20  at  2002 . The 2 sections of the SIMD12 (6 radix-4) is equivalent to 6 virtual banks. Since the output is buffered at DVectREGS[4][12] as shown in  FIG. 21  at  2102 , the address generation for the radix computation is the same as described above, except that the two sections needed to be iterated. 
     The output to the OutSIMD[288][4] as shown in  FIG. 21  at  2104  is also similar to the above description, except that there will be two extra loop for two sections to go over all 6 virtual banks. Specifically, the MEM[128][12] is partitioned into two sections of 45 entries for each. Three radix-4 operations are carried out in parallel for the 1 st  section first, and then the 2 nd  section, with inputs from [0,1,2,3], [4,5,6,7], [8,9,10,11] for the same offset address of both sections. The results are written into the DVectREGS[4][12] in the same place row-by-row. Once four rows are written into the DVectREGS[4][12], the results are read out column by column and written into the OutSIMD[288][4] row by row. 
     In an exemplary embodiment, a Tail row  2004  exists. It should be noted that 45 is not the multiple of 4, so there is one tail row that will have only one entry instead of four. It will be written into DVectREGS[4][12] for the number of tail rows. The results will be written into the OutSIMD[288][4] disregarding of the number of tail elements. 
     In the output phase by reading from OutSIMD[ ][4], however, the tail needs special handling similar to the write to DVectREGS. Specifically, it will only output the valid elements from the tail entry in OutSIMD and discard the other filler elements. 
     Address Mapping from Staging Buffer to Out_SIMD and the Output Data Stream ( 2106 ) is disclosed for the VMS. Note that for the case of 12-point (radix-{3,4}) and 24-point (radix-{6,4}) DFTs, they can be treated as special cases without using the above procedure to generate the output because there is only one row in each section. The output can be easily packed to the needed format to achieve throughput of 3 samples/cycle or 4 samples/cycle. Otherwise, the tail processing only gives 1 sample/cycle, which does not meet the throughput requirement. Table 2 shows an exemplary embodiment of pseudo-code to achieve the last stage processing and data output as described above. 
     
       
         
           
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 Pseudo-code for the Last Stage Processing and Data Output. 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 SECTOR_BASE = 0; 
               
               
                 NumOutSIMDEntryPerBK = NumEntryPerMB &gt;&gt; 2; 
               
               
                 NumEntryPerMB_Mod4 = NumEntryPerMB % 4; 
               
               
                 if (NumEntryPerMB_Mod4 != 0) 
               
               
                 { 
               
               
                  NumOutSIMDEntryPerBK += 1; 
               
               
                 } 
               
               
                 short OutWR_SECTOR_BASE = 0; 
               
               
                 short BaseDBUF_SIMD; 
               
               
                 unsigned short CurRS_Bits; 
               
               
                 CurRS_Bits = GetCurRS_Bits(DFT_InParas -&gt; MaxValueAbs); 
               
               
                 RS_Bits += CurRS_Bits; 
               
               
                 for (SectorIndx = 0 : NumSectorsPerBK−1) 
               
               
                 { 
               
               
                   short CurSIMDIndx = 0; 
               
               
                   short OutAddrOff = 0; 
               
               
                   for (short OffSetInSBlk = 0 : NumEntryPerMB−1) 
               
               
                   { 
               
               
                     short AbsBaseAddr = SECTOR_BASE + OffSetInSBlk; 
               
               
                 // Step 1: load the data of the same radix from multiple banks and SIMD to the Register files. 
               
               
                     for (j = 0 : CurRadix−1) 
               
               
                       { 
               
               
                       In_MB0[j] = (MEMB0[AbsBaseAddr][j]) &gt;&gt; CurRS_Bits; 
               
               
                       In_MB1[j] = (MEMB0[AbsBaseAddr][j+4]) &gt;&gt; CurRS_Bits; 
               
               
                       In_MB2[j] = (MEMB0[AbsBaseAddr][j+8]) &gt;&gt; CurRS_Bits; 
               
               
                       T_CurFMult[j] = SAT16(T_CurRe[j] &gt;&gt; 2); 
               
               
                       T_CurTmp_MBK1_FMult[j] = SAT16(T_CurReTmp_MBK1[j] &gt;&gt; 2); 
               
               
                       T_CurTmp_MBK2_FMult[j] = SAT16(T_CurReTmp_MBK2[j] &gt;&gt; 2); 
               
               
                     } 
               
               
                     TwiddleMulti(In_MB0, T_CurFMult, CurRadix); 
               
               
                     TwiddleMulti(In_MB1, T_CurTmp_MBK1_FMult, CurRadix); 
               
               
                     TwiddleMulti(In_MB2, T_CurTmp_MBK2_FMult, CurRadix); 
               
               
                 // Step 2: do three vector processing of the Radix operations; 
               
               
                     Radix_OneOperators(CurRadix, In_MB0, Out_MB0); 
               
               
                     Radix_OneOperators(CurRadix, In_MB1, Out_MB1); 
               
               
                     Radix_OneOperators(CurRadix, In_MB2, Out_MB2); 
               
               
                     unsigned int MaxValueB0, MaxValueB1, MaxValueB2; 
               
               
                 // Write back to Buffer Register Files 
               
               
                     for (j = 0 : CurRadix−1) 
               
               
                     { 
               
               
                       DVectREGS_MB0[CurSIMDIndx][j] = Out_MB0[j]; 
               
               
                       DVectREGS_MB1[CurSIMDIndx][j] = Out_MB1[j]; 
               
               
                       DVectREGS_MB2[CurSIMDIndx][j] = Out_MB2[j]; 
               
               
                 // update the MaxAbsValue; 
               
               
                     ... 
               
               
                     } 
               
               
                     Twiddle_Regen(T_Cur, T_BaseRadix,CurRadix);// T = T.*T_BaseRadix; 
               
               
                     Twiddle_Regen(T_CurTmp_MBK1, T_BaseRadix,CurRadix); 
               
               
                     Twiddle_Regen(T_CurTmp_MBK2, T_BaseRadix,CurRadix); 
               
               
                     CurSIMDIndx ++; 
               
               
                     if (CurSIMDIndx == 4) 
               
               
                     { 
               
               
                       CurSIMDIndx = 0; 
               
               
                       BaseDBUF_SIMD = 0; 
               
               
                       for (short j = 0 : CurRadix−1) 
               
               
                       { 
               
               
                         for (short i=0; i&lt;4; i++) 
               
               
                         { 
               
               
                           OutSIMDAddr = BaseDBUF_SIMD + OutWR_SECTOR_BASE + 
               
               
                            OutAddrOff; 
               
               
                           OutSIMD[OutSIMDAddr][i] = SAT16(((DVectREGS_MB0[i][j]) * 
               
               
                            LastST_Scaler) &gt;&gt; RS_LastScalar); 
               
               
                           OutSIMD[OutSIMDAddr + NumOutSIMDEntryPerBK][i] = 
               
               
                             SAT16(((DVectREGS_MB1[i][j]) * LastST_Scaler) &gt;&gt; 
               
               
                             RS_LastScalar); 
               
               
                           OutSIMD[OutSIMDAddr + NumOutSIMDEntryPerBK*2][i] = 
               
               
                             SAT16(((DVectREGS_MB2[i][j]) * LastST_Scaler) &gt;&gt; 
               
               
                             RS_LastScalar); 
               
               
                         }   // for (i) 
               
               
                         BaseDBUF_SIMD += NumOutSIMDEntryPerBK* 3 * NumSectorsPerBK; 
               
               
                       }   // for (short j) 
               
               
                       OutAddrOff ++; 
               
               
                     }   // if (CurSIMDIndx) 
               
               
                   }   // for (OffSetInSBlk) 
               
               
                 // Tail processing 
               
               
                   BaseDBUF_SIMD =0; 
               
               
                   for (short j = 0; j&lt;DFT_InParas-&gt;CurRadix; j++) 
               
               
                   { 
               
               
                     for (short i = 0; i&lt;CurSIMDIndx; i++) 
               
               
                     { 
               
               
                       OutSIMDAddr = BaseDBUF_SIMD + OutWR_SECTOR_BASE + OutAddrOff; 
               
               
                       OutSIMD[OutSIMDAddr][i] = SAT16(((DVectREGS_MB0_I[i][j]) * 
               
               
                        LastST_Scaler) &gt;&gt; RS_LastScalar); 
               
               
                       OutSIMD[OutSIMDAddr + NumOutSIMDEntryPerBK][i] = 
               
               
                        SAT16(((DVectREGS_MB1_I[i][j]) * LastST_Scaler) &gt;&gt;RS_LastScalar); 
               
               
                       OutReSIMD[OutSIMDAddr +NumOutSIMDEntryPerBK*2][i] = 
               
               
                        SAT16(((DVectREGS_MB2_I[i][j]) * LastST_Scaler) &gt;&gt;RS_LastScalar); 
               
               
                     }   // for(i) 
               
               
                     BaseDBUF_SIMD += NumOutSIMDEntryPerBK * 3 * NumSectorsPerBK; 
               
               
                   }   // for (short j) 
               
               
                   SECTOR_BASE = 64; 
               
               
                   OutWR_SECTOR_BASE = NumOutSIMDEntryPerBK * 3; 
               
               
                   for (CurRadixIndx=0:CurRadix−1) 
               
               
                     { 
               
               
                      T_Cur[CurRadixIndx]= (int18)(LUT_STEP_LASTSTAGE_COS[CurRadixIndx]) &gt;&gt; 
               
               
                       RS_BITS_LUT; 
               
               
                     T_CurTmp_MBK1[CurRadixIndx] = T_StepRadix[CurRadixIndx]; 
               
               
                     T_CurTmp_MBK2[CurRadixIndx] = T_StepRadixRe[CurRadixIndx]; 
               
               
                   } 
               
               
                   Twiddle_Regen(T_CurTmp_MBK1, T_Cur, CurRadix); 
               
               
                   Twiddle_Regen(T_CurTmp_MBK2, T_CurTmp_MBK1, CurRadix); 
               
               
                 }   // for (SectorIndx) 
               
               
                   
               
            
           
         
       
     
     With the output data already stored in the SIMD4 output buffer OutSIMD[ ][4], the output phase to the next step computation after DFT is very straightforward, except the special handling needed for the tail SIMD entry, which may not have full SIMD-4 elements to fill that entry. 
     Twiddle Factor Generation 
     It should be noted that the various embodiments of the programmable vector processor can support 35 or more different DFT sizes with mixed base radix of {2, 3, and 5}. To achieve high speed, twiddle coefficients matrices are generated on-the-fly in parallel and flexibly to provide vector processing of all different DFT sizes. Conventional systems may store large size coefficient matrices called twiddle coefficient matrices. However, storing all coefficients in memory and statically loading these coefficients for the required computations is not realistic for power/area efficient VLSI design because of the size of memory required. 
     In various exemplary embodiments, a dynamic twiddle factor generator is provided that generates twiddle factor vectors utilizing a group of very small look up tables (LUTs) that only store base coefficients for each category of radix operations. A unique logic based LUT addressing architecture also is provided to quickly access the LUT entries in a pipelined mode. This not only saves memory resources and cost, but also can achieve high throughput in generating the twiddle factor vectors on-the-fly in parallel for vector processing. 
     As stated above but repeated here for clarity, the DFT algorithm in LTE works iteratively in multiple stages to generate a final result for an N-point DFT/IDFT, where N=2 α 3 β 5 γ . For example, if the last stage is a radix-r, it is generated from r sub-blocks of 
             n   =     N   r           
point FFT. For example, assuming that the data is stored in a data matrix from the previous stage output as;
 
                 D     r   ×   n       =       [           d     0   ,   0             d     0   ,   1             d     0   ,   2           …         d     0   ,     n   -   1                   d     1   ,   0             d     1   ,   1             d     1   ,   2           …         d     1   ,     n   -   1                   d     2   ,   0             d     2   ,   1             d     2   ,   2           …         d     2   ,     n   -   1                 …                                                             d       r   -   1     ,   0             d       r   -   1     ,   1             d     0   ,   2           …         d       r   -   1     ,     n   -   1               ]       r   ×   n         ,         
where each row is a sub-block of size n, the output of an n-point FFT. Further assuming that the twiddle factors also are stored in a matrix format as;
 
                 T     r   ×   n     MATRIX     =       [         1       1       1       …       1           1         W   1           W   2                       W     (     n   -   1     )               1         W   2           W   4                       W     2   ⁢     (     n   -   1     )                 ⋮                                                           1         W     (     r   -   1     )             W     2   ⁢     (     r   -   1     )                           W       (     r   -   1     )     ⁢     (     n   -   1     )               ]       r   ×   n         ,     W   =       e       -   j     ⁢       2   ⁢   π       r   ×   n           .             
Thus, the input to the radix-r operator to obtain the N-point (N=r×n) is generated as {tilde over (D)} r×n =D r×n ∘T r×n   MATRIX , which is the Hadamard product of the data matrix and the twiddle factor matrix.
 
     The programmable vector processor is configured to support at least 35 mixed-radix N-point LTE DFT/IDFTs, where N can be factorized to base radix {2, 3, and 5} as shown below in Table 1. This leads to the twiddle coefficient matrix having many different sizes of T r×n , when r and n grows iteratively to construct a larger DFT size from the smaller ones. 
     
       
         
           
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
             
            
               
                   
                 NDFT 
               
            
           
           
               
               
               
               
               
               
               
               
            
               
                   
                 1296 
                 1200 
                 1152 
                 1080 
                 972 
                 960 
                 900 
               
               
                   
               
               
                 Radix-Factors 
                 2{circumflex over ( )}4 * 3{circumflex over ( )}4 
                 2{circumflex over ( )}4 * 3 * 5{circumflex over ( )}2 
                 2{circumflex over ( )}6 * 2 * 3{circumflex over ( )}2 
                 2{circumflex over ( )}3 * 3{circumflex over ( )}3 * 5 
                 2{circumflex over ( )}2 * 3{circumflex over ( )}5 
                 2{circumflex over ( )}6 * 3 * 5 
                 2{circumflex over ( )}2 * 3{circumflex over ( )}2 * 5{circumflex over ( )}2 
               
               
                   
               
            
           
           
               
               
            
               
                   
                 NDFT 
               
            
           
           
               
               
               
               
               
               
               
               
            
               
                   
                 864 
                 768 
                 720 
                 648 
                 600 
                 576 
                 540 
               
               
                   
               
               
                 Radix-Factors 
                 2{circumflex over ( )}5 * 3{circumflex over ( )}3 
                 2{circumflex over ( )}8 * 3 
                 2{circumflex over ( )}4 * 3{circumflex over ( )}2 * 5 
                 2{circumflex over ( )}3 * 3{circumflex over ( )}4 
                 3 * 2{circumflex over ( )}4 * 5{circumflex over ( )}2 
                 2{circumflex over ( )}6 * 3{circumflex over ( )}2 
                 2{circumflex over ( )}2 * 3{circumflex over ( )}3 * 5 
               
               
                   
               
            
           
           
               
               
            
               
                   
                 NDFT 
               
            
           
           
               
               
               
               
               
               
               
               
            
               
                   
                 480 
                 432 
                 384 
                 360 
                 324 
                 300 
                 288 
               
               
                   
               
               
                 Radix-Factors 
                 2{circumflex over ( )}4 * 2 * 3 * 5 
                 2{circumflex over ( )}4 * 3{circumflex over ( )}3 
                 2{circumflex over ( )}7 * 3 
                 2{circumflex over ( )}3 * 3{circumflex over ( )}2 * 5 
                 2{circumflex over ( )}2 * 3{circumflex over ( )}4 
                 2{circumflex over ( )}2 * 3 * 5{circumflex over ( )}2 
                 2{circumflex over ( )}4 * 2 * 3 
               
               
                   
               
            
           
           
               
               
            
               
                   
                 NDFT 
               
            
           
           
               
               
               
               
               
               
               
               
            
               
                   
                 240 
                 216 
                 192 
                 180 
                 144 
                 120 
                 108 
               
               
                   
               
               
                 Radix-Factors 
                 2{circumflex over ( )}4 * 3 * 5 
                 2{circumflex over ( )}3 * 3{circumflex over ( )}3 
                 2{circumflex over ( )}6 * 3 
                 3{circumflex over ( )}2 * 2{circumflex over ( )}2 * 5 
                 3{circumflex over ( )}2 * 2{circumflex over ( )}4 
                 2{circumflex over ( )}3 * 3 * 5 
                 3{circumflex over ( )}3 * 2{circumflex over ( )}2 
               
               
                   
               
            
           
           
               
               
            
               
                   
                 NDFT 
               
            
           
           
               
               
               
               
               
               
               
               
            
               
                   
                 96 
                 72 
                 60 
                 48 
                 36 
                 24 
                 12 
               
               
                   
               
               
                 Radix-Factors 
                 2{circumflex over ( )}5 * 3 
                 2{circumflex over ( )}3 * 3{circumflex over ( )}2 
                 2{circumflex over ( )}2 * 3 * 5 
                 3 * 2{circumflex over ( )}4 
                 3{circumflex over ( )}2 * 2{circumflex over ( )}2 
                 2{circumflex over ( )}3 * 3 
                 2{circumflex over ( )}2 * 3 
               
               
                   
               
            
           
         
       
     
     For example, in the case of a 1200-point DFT as shown in Table 1, the DFT can be factorized into multiple stages of radix operations arranged as {2, 2, 2, 2, 3, 5, 5}. The twiddle coefficient matrix involved in the process of the DFT computation could include the set {T 2×1   MATRIX , T 2×2   MATRIX , T 2×4   MATRIX , T 2×8   MATRIX , T 3×16   MATRIX , T 5×48   MATRIX , T 5×240   MATRIX }, where there is a twiddle matrix for each radix stage. There can be many variations of the radix-orders as well. In another example, if the order of radix operation is arranged as {2, 5, 2, 5, 3, 2, 2}, the twiddle coefficient matrix would include {T 2×1   MATRIX , T 5×2   MATRIX , T 2×10   MATRIX , T 5×20   MATRIX , T 3×10   MATRIX , T 2×300   MATRIX , T 2×600   MATRIX }. In another example of a 900-point DFT, if the radix factorization is arranged as {3,2,2,3,5,5}, the twiddle coefficient matrix can include {T 3×1   MATRIX , T 2×3   MATRIX , T 2×6   MATRIX , T 3×12   MATRIX , T 5×36   MATRIX , T 5×180   MATRIX }. Otherwise, if the radix-factorization becomes {5,5,3,3,2,2}, then the twiddle coefficient matrix can become {T 5×1   MATRIX , T 5×5   MATRIX , T 3×25   MATRIX , T 3×75   MATRIX , T 2×225   MATRIX , T 2×450   MATRIX }, Thus, attempting to store all these twiddle coefficients can lead to very complex memory storage. 
     It should be noted that twiddle factor storage can be in original data matrix format. Intuitively, the twiddle factor coefficients can be stored in the original (r×n) point matrix. All twiddle factors of the same radix size with a fraction of the (r×n) point DFT, 
               e   .   g   .     ,     (     r   ×     n   K       )           
point DFT share the same twiddle factor matrix. The twiddle factors are simply read from every K th  column starting from the first column. For example, the odd columns contain the twiddle factors for the stage of
 
               n   2     ,         
while every 3 rd  column contains the values for a stage with input sub-block size of
 
     
       
         
           
             
               n 
               3 
             
             . 
           
         
       
     
     This option is useful to reuse the twiddle factors in the FFT case, where the NFFT size is relatively regular as two&#39;s power or four&#39;s power. In this case, it is possible to store the twiddle factors of the last stage and read the twiddle factors for the previous stages from the same matrix by jumping the columns. The throughput can be very high without the burden to compute a single twiddle factor but there is redundancy in the twiddle factor matrix. 
                     T     r   ×     n   K       MATRIX     =       ⁢       [         1       1       1       …       1           1           W   ~     1             W   ~     2                                     1           W   ~     2             W   ~     4                                     ⋮                                                           1           W   ~       (     r   -   1     )               W   ~       2   ⁢     (     r   -   1     )                             W   ~         (     r   -   1     )     ⁢     (       n   K     -   1     )               ]       r   ×     n   K                       =       ⁢       [         1       1       1       …       1           1         W   K           W     K   *   2                                       1         W     K   *   2             W     K   *   4                                       ⋮                                                           1         W     K   *     (     r   -   1     )               W     K   *     (     r   -   1     )     *   2                         W       K   ⁡     (     r   -   1     )       ⁢     (       n   K     -   1     )               ]       r   ×     n   K           ,                       W   ~     =       e       -   j     ⁢       2   ⁢   π       r   ×     n   K             =       e       -   j     ⁢       2   ⁢   π   *   K       r   ×   n           =     W   K               
However, this scheme is not realistic for the case of a programmable mix-radix architecture configured to process many radix combinations as provided by the programmable vector processor described herein.
 
     Exemplary embodiments disclosed herein describe incremental vector generation of the twiddle factors. For the case of a DFT with various sizes to support, the memory requirement to store the whole twiddle factor matrix can be high and redundant. A more memory efficient solution is to use the column-wise incremental feature of the twiddle factor matrix. This is shown for the following two scenarios. The first scenario applies to stages before the last stage and the second scenario is last stage vector generation. 
     Twiddle Vector Generation for Stages Prior to Last Stage 
     The first scenario applies to stages before the last one and shows that the twiddle factor matrix for each sub-block can be generated incrementally from column to column, if the computation order is kept the same as follows.
 
 T   r×n   MATRIX =└1, T   r×n   VECT ,[ T   r×n   VECT ] 2 , . . . ,[ T   r×n   VECT ] (n−1) ┘ r×n ,
 
where the second column vector can be expressed as:
 
     
       
         
           
             
               
                 T 
                 
                   r 
                   × 
                   n 
                 
                 VECT 
               
               = 
               
                 
                   [ 
                   
                     1 
                     , 
                     
                       W 
                       
                         r 
                         × 
                         n 
                       
                       1 
                     
                     , 
                     
                       W 
                       
                         r 
                         × 
                         n 
                       
                       2 
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       W 
                       
                         r 
                         × 
                         n 
                       
                       
                         ( 
                         
                           r 
                           - 
                           1 
                         
                         ) 
                       
                     
                   
                   ] 
                 
                 T 
               
             
             , 
             
               
                 W 
                 
                   r 
                   × 
                   n 
                 
               
               = 
               
                 
                   e 
                   
                     
                       - 
                       j 
                     
                     ⁢ 
                     
                       
                         2 
                         ⁢ 
                         π 
                       
                       
                         r 
                         × 
                         n 
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
     Thus, the (k+1) th  column vector can be expressed as the equation below: 
                     T     r   ×   n       VECT   k       =       ⁢       [     1   ⁢       (     W     r   ×   n       )     k     ⁢       (     W     r   ×   n       )       2   ⁢   k       ⁢           ⁢   …   ⁢           ⁢       (     W     r   ×   n       )         (     r   -   1     )     ⁢   k         ]     T                 =       ⁢         [     1   ⁢       (     W     r   ×   n       )       (     k   -   1     )       ⁢       (     W     r   ×   n       )       2   ⁢     (     k   -   1     )         ⁢           ⁢   …   ⁢           ⁢       (     W     r   ×   n       )         (     r   -   1     )     ⁢     (     k   -   1     )           ]     T     ∘                     ⁢       [     1   ⁢         W     r   ×   n       ⁡     (     W     r   ×   n       )       2     ⁢           ⁢   …   ⁢           ⁢       (     W     r   ×   n       )       (     r   -   1     )         ]     T                   =       ⁢       T     r   ×   n       VECT     (     k   -   1     )         ∘     T     r   ×   n     VBase         ,               
and can be generated incrementally by a Hadamard product of k th  column vector T r×n   VECT(k−1) .
 
     Thus, in an exemplary embodiment only the base vector of the twiddle factors are stored for each stage of the computation. This is feasible as the vector computation order grows from the 1 st  column to the n th  column as performed in the vector radix processor engine described above. For example, the computational order from the first column to subsequent columns is shown in the before last stage (BLS) twiddle matrix expression below. 
     
       
         
         
             
             
         
       
     
     Such a twiddle factor generation does not stall the SIMD computation before the last stage since the twiddle factors for all the vector radix operations are identical. Thus, it is possible to save resources by storing only the base vector T r×n   base =[1,W r×n ,W r×n   2 , . . . , W r×n   (r−1) ] T , 
                 W     r   ×   n       =     e       -   j     ⁢       2   ⁢   π       r   ×   n             ,         
instead of the whole data matrix for an (r×n) point DFT. Furthermore, to save storage resources more aggressively, it is possible to store only the base element coefficients
 
               W     r   ×   n     BASE     =     e       -   j     ⁢       2   ⁢   π       r   ×   n                 
for all the different r×n combinations and generate the base vector T r×n   base  in the initialization phase of computing each twiddle vector.
 
Twiddle Vector Generation for Last Stage
 
     The second scenario applies to the last stage vector generation and allows for generation of two vector radices at the last stage, and therefore two sets of twiddle factor vectors are generated in parallel. For example, the twiddle factor can be divided into two parts as follows. For each part, two twiddle factors are generated in parallel incrementally, 
                         
where the decomposition is simply;
 
               T     r   ×   n     MATRIX     =         [       T     r   ×     n   2       MATRIX     ,       T     r   ×     n   2       MATRIX     ∘       (     T     r   ×   n     MBase     )       n   2           ]       r   ×   n       .           
where T r×n   MBase  is a matrix of
 
             r   ×     n   2           
with all column vectors equal to
 
                 (     T     r   ×   n     Base     )       n   2       .         
Thus, it is preferable to store both T r×n   base  and
 
                 (     T     r   ×   n     Base     )       n   2       .         
Since
 
                 (     T     r   ×   n     Base     )       n   2       =     T     r   ×   2     Base           
for all n, there are no extra costs introduced for the various n sizes in the supported DFT size decomposition. Similarly, to allow three vector radix-4 processing at the last stage, the twiddle matrix can be partitioned into three sections, as shown below.
 
                         
where the decomposition and last stage (LS) twiddle matrix expression is simply;
 
                       T     r   ×   n     MATRIX     =       [       T     r   ×     n   3       MATRIX     ,       T     r   ×     n   3       MATRIX     ∘       (     T     r   ×   n     MBase     )       n   3         ,       T     r   ×     n   3       MATRIX     ∘       (     T     r   ×   n     MBase     )         2   ⁢   n     3           ]       r   ×   n         ,           (   LS   )               
and where
 
                 (     T     r   ×   n     MBase     )       n   3       =         T     r   ×   3     MBase     ⁢           ⁢   and   ⁢           ⁢       (     T     r   ×   n     MBase     )         2   ⁢   n     3         =       [     T     r   ×   3     MBase     ]     2             
are constants (or step coefficients) for a given radix base r=4 for the last stage. For example, the step coefficients are stored and provided by LUT  2238  shown in  FIG. 22  to determine the 2 nd  and 3 rd  sections as expressed above in equation (LS).
 
     One embodiment of the present invention discloses method and apparatus for factorizing the mixed-radix coefficients for vector processing. To achieve higher throughput as well as simplify the twiddle coefficient matrix, high-radix vector factorizations for each NDFT point are listed in the Table 2 below that includes radix {3,4,5,6} operations. In factorization scheme selection, the following guidelines are applied wherever possible:
     A. Keep the last stage radix as 4 to utilize the SIMD more efficiently;   B. (NStage-1) th  is either a radix-3 or radix-6 stage to utilize the 3-bank SIMD4 memory structure more efficiently; and   C. Keep the number of stages as few as possible to achieve higher throughput.   

     Exemplary embodiments of radix factorization using the above guidelines are shown in Table 2. The base twiddle factor vectors for each DFT size are listed. It is assumed that there are three banks with SIMDWidth=4 for the DFT engine. In Table 2, the DFT of length NDFT is factorized into NStages of iterative computation, where each stage radix is determined by the Hi-R Factor row. For example, the 1296-point DFT is factorized into five stages of (6,3,6,3,4), meaning that the first stage will be a Radix-6 stage, while the second stage will be a Radix-3 stage, and so on. 
                             TABLE 2                          NDFT                                                 1296   1200   1152   1080   972   960   900               Hi-R   (6, 3, 6, 3, 4)   (5, 5, 4, 3, 4)   (6, 4, 4, 3, 4)   (5, 3, 3, 6, 4)   (3, 3, 3, 3, 3, 4)   (5, 4, 4, 3, 4)   (5, 5, 3, 3, 4)       Factor       NStages   5   5   5   5   6   5   5       T r×n   base     T 3×6   base ,   T 5×5   base     T 4×6   base ,   T 3×5   base ,   T 3×3   base , T 3×9   base ,   T 4×5   base ,   T 5×5   base ,           T 6×18   base ,   T 4×25   base     T 4×24   base ,   T 3×15   base ,   T 3×27   base ,   T 4×20   base ,   T 3×25   base ,           T 3×108   base ,   T 3×100   base     T 3×96   base ,   T 6×45   base ,   T 3×81   base ,   T 3×80   base ,   T 3×75   base ,           T 4×324   base     T 4×300   base ,   T 4×288   base ,   T 4×270   base ,   T 4×243   base ,   T 4×240   base ,   T 4×225   base ,                                 NDFT                                                 864   768   720   648   600   576   540               Hi-R   (6, 6, 6, 4)   (4, 4, 4, 3, 4)   (6, 5, 6, 4)   (3, 3, 3, 6, 4)   (5, 5, 6, 4)   (6, 4, 6, 4)   (5, 3, 3, 3, 4)       Factor       T r×n   base     T 6×6   base ,   T 4×4   base ,   T 5×6   base ,   T 3×3   base ,   T 5×5   base ,   T 4×6   base ,   T 3×5   base ,           T 6×36   base ,   T 4×16   base ,   T 6×30   base ,   T 3×9   base ,   T 6×25   base ,   T 6×24   base ,   T 3×15   base ,           T 4×216   base ,   T 3×64   base ,   T 4×180   base ,   T 6×27   base ,   T 4×150   base     T 4×144   base     T 3×45   base ,               T 4×192   base         T 4×162   base ,           T 4×135   base                                   NDFT                                                 480   432   384   360   324   300   288               Hi-R   (5, 4, 6, 4)   (6, 3, 6, 4)   (4, 4, 6, 4)   (5, 6, 3, 4)   (3, 3, 3, 3, 4)   (5, 5, 3, 4)   (6, 4, 3, 4)       Factor       T r×n   base     T 4×5   base ,   T 3×6   base ,   T 4×4   base ,   T 6×5   base     T 3×3   base ,   T 5×5   base     T 4×6   base ,           T 6×20   base ,   T 6×18   base ,   T 6×16   base ,   T 3×30   base ,   T 3×9   base ,   T 3×25   base     T 3×24   base ,           T 4×120   base     T 4×108   base     T 4×96   base     T 4×90   base     T 3×27   base ,   T 4×75   base     T 4×72   base                             T 4×81   base                                   NDFT                                                 240   216   192   180   144   120   108               Hi-R   (5, 4, 3, 4)   (3, 3, 6, 4)   (4, 4, 3, 4)   (5, 3, 3, 4)   (6, 6, 4)   (5, 6, 4)   (3, 3, 3, 4)       Factor       T r×n   base     T 4×5   base     T 3×3   base     T 4×4   base ,   T 3×5   base ,   T 6×6   base ,   T 6×5   base ,   T 3×3   base ,           T 3×20   base ,   T 6×9   base     T 3×16   base ,   T 3×15   base ,   T 4×36   base ,   T 4×30   base ,   T 3×9   base ,           T 4×60   base ,   T 4×54   base     T 4×48   base ,   T 4×45   base ,           T 4×27   base                                   NDFT                                                 96   72   60   48   36   24   12               Hi-R   (4, 6, 4)   (6, 3, 4)   (5, 3, 4)   (4, 3, 4)   (3, 3, 4)   (6, 4)   (3, 4)       Factor       T r×n   base     T 6×4   base ,   T 3×6   base ,   T 3×5   base ,   T 3×4   base ,   T 3×3   base ,   T 4×6   base ,   T 4×3   base             T 4×24   base ,   T 4×18   base ,   T 4×15   base ,   T 4×12   base ,   T 4×9   base                      
Exemplary Implementation
 
       FIG. 22  shows an exemplary detailed embodiment of the dynamic twiddle factor generator (DTF)  422  shown in  FIG. 4 . In an exemplary embodiment, the DTG  422  comprises look-up table logic  2202 , a base vector address generator  2204 , and twiddle vector generator  2206 . The DTG  422  illustrates an exemplary embodiment of a mixed high-radix twiddle factor generator architecture, which uses multiple relatively small sets of base coefficients to implement dynamic twiddle vector generation. 
     In an exemplary embodiment, the look-up table logic  2202  comprises a radix decoder  2208 , address generation units (AGUs)  2210 ,  2212 , and  2214 . The logic  2202  also comprises a group of look-up tables (“LUTs”)  2216 ,  2218 , and  2220  to generate mixed high-radix twiddle factor values in accordance with the exemplary embodiments of the invention. In one aspect, the look-up table logic  2202  comprises three separate tables for the different radix computations: namely, R3R6-combined LUT  2216  that holds the base values for both radix-3 and radix-6 twiddle coefficients; a R4 LUT  2218  that holds only the base values for all possible radix-4 twiddle coefficients; and a R5 LUT  2220  that holds only the base values of all possible radix-5 twiddle coefficients from the radix-factorization. 
     In one aspect, the AGUs  2210 ,  2212 , and  2214  are used to access the twiddle LUTs  2216 ,  2218 , and  2220 . For example, each AGU receives the current value of n and an enable output from radix decoder  2208 . The radix decoder  2208  decodes the current radix value and activates one of the AGUs using the enable lines, shown generally at  2242 . The activated AGU outputs an address based on the current value of n it receives. For example, the AGU  2210  outputs the address (ADDR3/6), the AGU  2212  outputs the address (ADDR4) and the AGU  2214  outputs the address (ADDR5). 
     The LUTs  2216 ,  2218 , and  2220  output twiddle factor scaler values (TFSV) based on the address they receive. For example, the LUT  2216  outputs either TFSV_R3 or TFSV_R6, the LUT  2218  outputs TFSV_R4, and the LUT  2220  outputs TFSV_R3. A multiplexer  2222 , receives the TFSV outputs from the LUTs and outputs a selected TFSV based on an input from the radix decoder  2208 . The selected TFSV is then passed to the base vector generator  2204 . 
     The possible base twiddle factors are listed below for each radix size. The radix-3 and radix-6 factors can share the same LUT. For example, the T3 and T6 tables can be combined and use the same addressing pattern to access the R3R6 LUT  2216 . Since the T5 LUT  2220  only has two elements, it is easy to access the table with a given n in T r×n   base  as illustrated in Table 3 below. 
     
       
         
           
               
             
               
                 TABLE 3 
               
             
            
               
                   
               
               
                 Complete list of possible T r×n   base   
               
            
           
           
               
               
               
               
            
               
                 Radix r 
                 Value n in T r×n   base   
                 Table Size 
                 Base Elements 
               
               
                   
               
            
           
           
               
               
               
               
            
               
                 T3 
                 3, 4, 5, 6, 9, 15, 16, 18, 
                 22 
                 3, 4, 5, 6, 9, 15, 
               
               
                   
                 20, 24, 25, 27, 30, 45, 
                   
                 16, 18, 20, 24, 25, 
               
               
                   
                 64, 75, 80, 81, 96, 100, 
                   
                 27, 30, 45, 64, 75, 
               
               
                   
                 108 
                   
                 80, 81, 96, 100, 108 
               
               
                 T4 
                 [3  4   5  6 9 12 15  16  18 
                 40 
                 [1 2 3 4 5 6 7 
               
               
                   
                   20 , 24  25  27 30 36, 45 
                   
                 8 9 10 11 12 
               
               
                   
                 48] 
                   
                 13 14 15 16]*3; 
               
               
                   
                 [54 60 72 75 81 90 96 
                   
                 [18 20 21 22 23 24 
               
               
                   
                 108 120 135 144 150 162 
                   
                 25 26 27 28 29 30 31 32 
               
               
                   
                 180 192 216 225 240 
                   
                 33 34 35 36 37 38 39 40 
               
               
                   
                 243 270 288 300 324] 
                   
                 41 42 43 44 45 46 47 48 
               
               
                   
                   
                   
                 49 50 54 60 64 72 75 80 
               
               
                   
                   
                   
                 81 90 96 100 108]*3; 
               
               
                   
                   
                   
                 Not dividable by 3: 
               
               
                   
                   
                   
                 [4, 5, 16, 20, 25] 
               
               
                 T5 
                 5, 6 
                 2 
               
               
                 T6 
                 4, 5, 6, 9, 16, 18, 20, 
                 22 
                 4, 5, 6, 9, 16, 18, 20, 
               
               
                   
                 24, 25, 27, 30, 36, 45 
                   
                 24, 25, 27, 30, 36, 45 
               
               
                   
               
            
           
         
       
     
     During operation, a search mechanism is applied by comparing each entry with the base index n. However, such a mechanism may take many cycles to exhaustively searching all entries, which may not suffice to meet latency requirement(s) in a high speed design. To avoid a complete content search, since the values n are not continuous, a list of all possible values of n can be used to find the unique identifying (ID) logic values from a subset of the bits that exclusively determine which value is being referring to. 
     In an exemplary embodiment, the merged list of possible n in both radix-3 and radix-6 includes the following values: {3, 4, 5, 6, 9, 15, 16, 18, 20, 24, 25, 27, 30, 36, 45, 64, 75, 80, 81, 96, 100, 108}, where the elements in normal type are for both radix-3 and radix-6, while the elements in bold type are only for radix-3 and the elements that are underlined are only for radix-6. Since the radix-3 base value T 3×n   base =(T 6×n   base ) 2 , the logic will only store values of T 6×n   base  for the entries of both radix-3 and radix-6, and store the T 3×n   base  values for the radix-3 only entries, where the T r×n   base  vector is given by the following expression. 
     
       
         
           
             
               
                 T 
                 
                   r 
                   × 
                   n 
                 
                 base 
               
               = 
               
                 
                   [ 
                   
                     1 
                     , 
                     
                       W 
                       
                         r 
                         × 
                         n 
                       
                       1 
                     
                     , 
                     
                       W 
                       
                         r 
                         × 
                         n 
                       
                       2 
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       W 
                       
                         r 
                         × 
                         n 
                       
                       
                         ( 
                         
                           r 
                           - 
                           1 
                         
                         ) 
                       
                     
                   
                   ] 
                 
                 T 
               
             
             , 
             
               
                 W 
                 
                   r 
                   × 
                   n 
                 
               
               = 
               
                 
                   e 
                   
                     
                       - 
                       j 
                     
                     ⁢ 
                     
                       
                         2 
                         ⁢ 
                         π 
                       
                       
                         r 
                         × 
                         n 
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
     For simplicity of addressing, only the R6 single values are stored and can generate the R3 single values for all DFT sizes all from the same computation described above. Table 4 below shows unique ID logic based addressing for T3, T5, and T6. For example, the unique ID logic bit processing maps values of n to LUT content. 
     
       
         
           
               
             
               
                 TABLE 4 
               
             
            
               
                   
               
               
                 Unique ID logic based addressing for T3/T6 and T5 
               
            
           
           
               
               
               
               
               
               
               
            
               
                   
                 Value n in 
                 Unique ID Logic 
                 Addr 
                 LUT 
                 Real 
                 Imaginary 
               
               
                 Value n 
                 7 bits format 
                 Bit processing 
                 Dec(binary) 
                 Content 
                 value 
                 value 
               
               
                   
               
            
           
           
               
            
               
                 T3/T6 Table (22 entries) 
               
            
           
           
               
               
               
               
               
               
               
            
               
                  3 
                 0000011 
                 not(B6|B4|B3|B2) 
                  0(00000) 
                 W 6×3   
                 123167 
                 −44830 
               
               
                  4 
                 
                   0000100 
                 
                 Not(B6|B5|B4|B3|B1|B0) 
                  1(00001) 
                 W 6×4   
                 126605 
                 −33924 
               
               
                  5 
                 0000101 
                 /B6 &amp;/B4 &amp;/B3 
                  2(00010) 
                 W 6×5   
                 128207 
                 −27252 
               
               
                   
                   
                 &amp;/B1 &amp; B0 
               
               
                  6 
                 00 0 0110 
                 /B4&amp;/B3 &amp;B2&amp;B1 
                  3(00011) 
                 W 6×6   
                 129080 
                 −22761 
               
               
                  9 
                 0001001 
                 /B6 &amp;/B4&amp;B3&amp;/B2 
                  4(00100) 
                 W 6×9   
                 130185 
                 −15217 
               
               
                 15 
                 0001111 
                 /B5&amp;/B4&amp;B3&amp;B2 
                  5(00101) 
                 W 6×15   
                 130752 
                 −9144 
               
               
                 16 
                 0010000 
                 /B6&amp;B4&amp;/B3&amp;/B2&amp;/B1 
                  6(00110) 
                 W 6×16   
                 130791 
                 −8573 
               
               
                 18 
                 
                   0010010 
                 
                 B4&amp;/B3&amp;/B2&amp;B1 
                  7(00111) 
                 W 6×18   
                 130850 
                 −7622 
               
               
                 20 
                 
                   0010100 
                 
                 /B5&amp;B4&amp;/B3&amp;B2 
                  8(01000) 
                 W 6×20   
                 130892 
                 −6860 
               
               
                 24 
                 0011000 
                 B4&amp;B3&amp;/B2&amp;/B0 
                  9(01001) 
                 W 6×24   
                 130947 
                 −5718 
               
               
                 25 
                 0011001 
                 /B6&amp;B4&amp;/B1&amp;B0 
                 10(01010) 
                 W 6×25   
                 130957 
                 −5489 
               
               
                 27 
                 0011011 
                 /B6&amp;B3&amp;/B2&amp;B1 
                 11(01011) 
                 W 6×27   
                 130973 
                 −5083 
               
               
                 30 
                 0011110 
                 B4&amp;B3&amp;B2 
                 12(01100) 
                 W 6×30   
                 130992 
                 −4575 
               
               
                 36 
                 0100100 
                 /B6&amp;B5&amp;/B1&amp;/B0 
                 13(01101) 
                 W 6×36   
                 131016 
                 −3813 
               
               
                 45 
                 0101101 
                 /B6&amp;B5&amp;B0 
                 14(01110) 
                 W 6×45   
                 131036 
                 −3050 
               
               
                 64 
                 1000000 
                 B6&amp;/B5&amp;/B4&amp;/B3 
                 15(01111) 
                 W 6×64   
                 131054 
                 −2145 
               
               
                 75 
                 1001011 
                 B6&amp;B1&amp;B0 
                 16(10000) 
                 W 6×75   
                 131059 
                 −1831 
               
               
                 
                   80 
                 
                 1010000 
                 B6&amp;B4&amp;/B0 
                 17(10001) 
                 W 6×80   
                 131060 
                 −1716 
               
               
                 
                   
                     81 
                   
                 
                 1010001 
                 B6&amp;B4&amp;B0 
                 18(10010) 
                 W 6×81   
                 131061 
                 −1695 
               
               
                 
                   96 
                 
                 1100000 
                 B5&amp;/B2 
                 19(10011) 
                 W 6×96   
                 131064 
                 −1430 
               
               
                 
                   100  
                 
                 1100100 
                 B6&amp;/B3&amp;B2 
                 20(10100) 
                 W 6×100   
                 131064 
                 −1373 
               
               
                 
                   108  
                 
                 1101100 
                 B6&amp;B3&amp;B2 
                 21(10101) 
                 W 6×108   
                 131065 
                 −1271 
               
            
           
           
               
            
               
                 T5 Table 
               
            
           
           
               
               
               
               
               
               
               
            
               
                  5 
                 10 1   
                 B0 
                  0(000) 
                 W 5×5   
                 126954 
                 −32597 
               
               
                  6 
                 11 0   
                 /B0 
                  1(001) 
                 W 5×6   
                 128207 
                 −27252 
               
               
                   
               
            
           
         
       
     
     Depending on the applications, at least two options or two addressing schemes for the LUT of twiddle factors for radix-4 can be implemented. While option 1 is to use a single table, option 2 is to break the possible n values into different categories. 
     Option 1, in one embodiment, uses a single table for all the possible base twiddle factor values and continuous addresses to access the table. To avoid content searching, unique ID logic is designed to process the highlighted bits in the Table 5 below. The real and imaginary values of the twiddle factor base values using 18-bit integer format are shown as examples for each n of T 4×n   base  in Table 5. There is a total of 40 ID logic configurations (or decodings) that are designed to access the table based on n. 
     
       
         
           
               
             
               
                 TABLE 5 
               
             
            
               
                   
               
               
                 Addressing Option 1 for “T4” table: continuous unique logic addressing 
               
               
                 T4 Table Option 1 (40 entries) 
               
            
           
           
               
               
               
               
               
               
               
               
               
               
               
               
            
               
                 n 
                 B8 
                 B7 
                 B6 
                 B5 
                 B4 
                 B3 
                 B2 
                 B1 
                 B0 
                 Re 
                 Im 
               
               
                   
               
            
           
           
               
               
               
               
               
               
               
               
               
               
               
               
            
               
                 3 
                 0 
                 0 
                 0 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 113511 
                 −65536 
               
               
                 4 
                 
                   0 
                 
                 0 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 121094 
                 −50160 
               
               
                 5 
                 0 
                 0 
                 0 
                 0 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 124656 
                 −40504 
               
               
                 6 
                 0 
                 
                   0 
                 
                 0 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 126605 
                 −33924 
               
               
                 9 
                 0 
                 0 
                 0 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 129080 
                 −22761 
               
               
                 12 
                 0 
                 0 
                 0 
                 
                   0 
                 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 129950 
                 −17109 
               
               
                 15 
                 0 
                 0 
                 0 
                 0 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 130353 
                 −13701 
               
               
                 16 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 
                   0 
                 
                 1 
                 
                   0 
                 
                 
                   0 
                 
                 
                   0 
                 
                 0 
                 130440 
                 −12848 
               
               
                 18 
                 0 
                 0 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 0 
                 130573 
                 −11424 
               
               
                 20 
                 0 
                 0 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 130667 
                 −10284 
               
               
                 24 
                 0 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 130791 
                 −8573 
               
               
                 25 
                 0 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 130813 
                 −8231 
               
               
                 27 
                 0 
                 0 
                 0 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 130850 
                 −7622 
               
               
                 30 
                 0 
                 0 
                 0 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 130892 
                 −6860 
               
               
                 36 
                 
                   0 
                 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 0 
                 1 
                 0 
                 0 
                 130947 
                 −5718 
               
               
                 45 
                 0 
                 0 
                 0 
                 1 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 130992 
                 −4575 
               
               
                 48 
                 0 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 
                   0 
                 
                 0 
                 0 
                 131001 
                 −4289 
               
               
                 54 
                 0 
                 0 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 131016 
                 −3813 
               
               
                 60 
                 0 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 1 
                 0 
                 0 
                 131027 
                 −3432 
               
               
                 72 
                 
                   0 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 1 
                 0 
                 0 
                 
                   0 
                 
                 131040 
                 −2860 
               
               
                 75 
                 0 
                 0 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 1 
                 0 
                 1 
                 1 
                 131043 
                 −2745 
               
               
                 81 
                 0 
                 0 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 0 
                 0 
                 1 
                 131047 
                 −2542 
               
               
                 90 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 1 
                 0 
                 131052 
                 −2288 
               
               
                 96 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 0 
                 0 
                 0 
                 131054 
                 −2145 
               
               
                 108 
                 0 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 1 
                 0 
                 0 
                 131058 
                 −1907 
               
               
                 120 
                 0 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 0 
                 0 
                 131060 
                 −1716 
               
               
                 135 
                 0 
                 
                   1 
                 
                 0 
                 0 
                 
                   0 
                 
                 0 
                 1 
                 
                   1 
                 
                 
                   1 
                 
                 131063 
                 −1526 
               
               
                 144 
                 0 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 1 
                 0 
                 
                   0 
                 
                 0 
                 0 
                 131064 
                 −1430 
               
               
                 150 
                 0 
                 
                   1 
                 
                 
                   0 
                 
                 0 
                 1 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   0 
                 
                 131064 
                 −1373 
               
               
                 162 
                 0 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   0 
                 
                 0 
                 0 
                 1 
                 0 
                 131065 
                 −1271 
               
               
                 180 
                 0 
                 
                   1 
                 
                 
                   0 
                 
                 
                   1 
                 
                 
                   1 
                 
                 0 
                 1 
                 0 
                 0 
                 131067 
                 −1144 
               
               
                 192 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   0 
                 
                 
                   0 
                 
                 0 
                 0 
                 0 
                 0 
                 131067 
                 −1073 
               
               
                 216 
                 0 
                 
                   1 
                 
                 1 
                 0 
                 1 
                 
                   1 
                 
                 0 
                 0 
                 0 
                 131068 
                 −954 
               
               
                 225 
                 0 
                 
                   1 
                 
                 1 
                 1 
                 
                   0 
                 
                 0 
                 0 
                 
                   0 
                 
                 
                   1 
                 
                 131068 
                 −916 
               
               
                 240 
                 0 
                 
                   1 
                 
                 
                   1 
                 
                 
                   1 
                 
                 1 
                 0 
                 0 
                 0 
                 
                   0 
                 
                 131069 
                 −858 
               
               
                 243 
                 0 
                 
                   1 
                 
                 1 
                 1 
                 
                   1 
                 
                 0 
                 0 
                 1 
                 
                   1 
                 
                 131069 
                 −848 
               
               
                 270 
                 
                   1 
                 
                 0 
                 0 
                 0 
                 0 
                 1 
                 1 
                 
                   1 
                 
                 0 
                 131069 
                 −763 
               
               
                 288 
                 
                   1 
                 
                 0 
                 0 
                 
                   1 
                 
                 0 
                 0 
                 
                   0 
                 
                 0 
                 0 
                 131070 
                 −715 
               
               
                 300 
                 
                   1 
                 
                 0 
                 0 
                 
                   1 
                 
                 0 
                 1 
                 
                   1 
                 
                 0 
                 0 
                 131070 
                 −687 
               
               
                 324 
                 
                   1 
                 
                 0 
                 
                   1 
                 
                 0 
                 0 
                 0 
                 1 
                 0 
                 0 
                 131070 
                 −636 
               
               
                   
               
            
           
         
       
     
     In an exemplary embodiment, the bit processing of the ID logic of the AGU performs the following functions in the 40 configurations to generate an address to access the appropriate LUT as follows: 
     
       
         
           
               
               
               
             
               
                   
               
             
            
               
                 addrR4_3 = 
                 and(and(and(and(not(B4), not(B3)), not(B2)), 
                 0 
               
               
                   
                 B1), B0).′; 
               
               
                 addrR4_4 = 
                 and(and(and(and(and(and(not(B4), not(B3)), 
                 1 
               
               
                   
                 B2), not(B1)), not(B0)), not(B5)), not(B8)).′ 
               
               
                 addrR4_5 = 
                 and(and(and(not(B3), B2), not(B1)), B0).′ 
                 2 
               
               
                 addrR4_6 = 
                 and(and(and(and(not(B7), not(B3)), B2), B1), 
                 3 
               
               
                   
                 not(B4)).′ 
               
               
                 addrR4_9 = 
                 and(and(and(and(not(B4), B3), not(B2)), 
                 4 
               
               
                   
                 not(B1)), B0).′ 
               
               
                 addrR4_12 = 
                 and(and(and(and(not(B5), B3), B2), not(B1)), 
                 5 
               
               
                   
                 not(B0)).′ 
               
               
                 addrR4_15 = 
                 and(and(and(B3, B2), B1), B0).′ 
                 6 
               
               
                 addrR4_16 = 
                 and(and(and(and(and(not(B7), not(B6)), 
                 7 
               
               
                   
                 not(B5)), not(B3)), not(B2)), not(B1)).′ 
               
               
                 addrR4_18 = 
                 and(and(and(and(not(B5), B4), not(B3)), 
                 8 
               
               
                   
                 not(B2)), B1).′ 
               
               
                 addrR4_20 = 
                 and(and(and(and(and(B4, not(B3)), B2), 
                 9 
               
               
                   
                 not(B1)), not(B0)), not(B5)).′ 
               
               
                 addrR4_24 = 
                 and(and(and(and(and(not(B6), not(B5)), B4), 
                 10 
               
               
                   
                 B3), not(B1)), not(B0)).′ 
               
               
                 addrR4_25 = 
                 and(and(and(and(not(B6), not(B5)), B4), 
                 11 
               
               
                   
                 not(B1)), B0).′ 
               
               
                 addrR4_27 = 
                 and(and(and(and(B4, B3), not(B2)), B1), B0).′ 
                 12 
               
               
                 addrR4_30 = 
                 and(and(and(B4, B3), B2), B1).′ 
                 13 
               
               
                 addrR4_36 = 
                 and(not(B7), and(and(and(and(not(B8), 
                 14 
               
               
                   
                 not(B6)), B5), not(B4)), not(B3))).′ 
               
               
                 addrR4_45 = 
                 and(and(and(B3, B2), not(B1)), B0).′ 
                 15 
               
               
                 addrR4_48 = 
                 and(and(and(and(not(B7), not(B6)), B5), B4), 
                 16 
               
               
                   
                 not(B2)).′ 
               
               
                 addrR4_54 = 
                 and(and(and(B5, B4), B2), B1).′ 
                 17 
               
               
                 addrR4_60 = 
                 and(and(and(not(B6), B5), B4), B3).′ 
                 18 
               
               
                 addrR4_72 = 
                 and(and(not(B8), not(B7)), and(and(and(B6, 
                 19 
               
               
                   
                 not(B5)), not(B4)), not(B0))).′ 
               
               
                 addrR4_75 = 
                 and(and(and(B6, not(B5)), not(B4)), B0).′ 
                 20 
               
               
                 addrR4_81 = 
                 and(B4, and(and(B6, not(B5)), not(B3))).′ 
                 21 
               
               
                 addrR4_90 = 
                 and(not(B7), and(B4, and(and(B6, not(B5)), 
                 22 
               
               
                   
                 B3))).′ 
               
               
                 addrR4_96 = 
                 and(not(B7), and(not(B4), and(and(B6, B5), 
                 23 
               
               
                   
                 not(B3)))).′ 
               
               
                 addrR4_108 = 
                 and(B6, and(and(B5, not(B4)), B3)).′ 
                 24 
               
               
                 addrR4_120 = 
                 and(B6, and(and(B5, B4), B3)).′ 
                 25 
               
               
                 addrR4_135 = 
                 and(and(and(B7, not(B4)), B1), B0).′ 
                 26 
               
               
                 addrR4_144 = 
                 and(and(and(B7, not(B6)), not(B5)), not(B2)).′ 
                 27 
               
               
                 addrR4_150 = 
                 and(and(and(and(B7, not(B6)), B2), B1), 
                 28 
               
               
                   
                 not(B0)).′ 
               
               
                 addrR4_162 = 
                 and(and(and(B7, not(B6)), B5), not(B4)).′ 
                 29 
               
               
                 addrR4_180 = 
                 and(and(and(B7, not(B6)), B5), (B4)).′ 
                 30 
               
               
                 addrR4_192 = 
                 and(and(and(B7, B6), not(B5)), not(B4)).′ 
                 31 
               
               
                 addrR4_216 = 
                 and(B7, B3).′ 
                 32 
               
               
                 addrR4_225 = 
                 and(and(and(B7, not(B4)), not(B1)), B0).′ 
                 33 
               
               
                 addrR4_240 = 
                 and(and(and(B7, B6), B5), not(B0)).′ 
                 34 
               
               
                 addrR4_243 = 
                 and(and(B7, B4), B0).′ 
                 35 
               
               
                 addrR4_270 = 
                 and(B8, B1).′ 
                 36 
               
               
                 addrR4_288 = 
                 and(and(B8, B5), not(B2)).′ 
                 37 
               
               
                 addrR4_300 = 
                 and(and(B8, B5), B2).′ 
                 38 
               
               
                 addrR4_324 = 
                 and(B8, B6).′ 
                 39 
               
               
                   
               
            
           
         
       
     
     Option 2, in one aspect, is to break the possible n values into different categories and use continuous addressing by inserting some filler elements in the gaps for some sections of data with only a few number holes. This is shown in Table 6. For section 1, the entries can be divided by 3 and n/3&lt;=16. This gives 12 elements in the address space 0˜15, where address is n/3−1 for that range. Section 2 contains those values that can be divided by 9 and larger than 16. This contains 27 entries with continuous address space given by n/27−2. Section 3 contains those values that can be divided 5*3 for the values n/3&gt;=20. The address is given by n/15−4. Section 4 contains those remaining values n that can be divided by 3 but do not fall into sections 1, 2, and 3. The unique ID logic is designed for this section. Section 5 contains entries whose n cannot be divided by 3. The unique ID logic is designed for this section independently. 
     
       
         
           
               
             
               
                 TABLE 6 
               
             
            
               
                   
               
               
                 Addressing Option 2 for “T4” table: 
               
               
                 continuous unique logic addressing 
               
            
           
           
               
               
               
               
               
            
               
                 Value 
                 Value in 
                 Unique 
                   
                 LUT values W 4×n   
               
            
           
           
               
               
               
               
               
               
            
               
                 n/3 
                 6b format 
                 ID Logic 
                 Addr 
                 RE 
                 IM 
               
               
                   
               
            
           
           
               
               
               
            
               
                 Section 1: T4 Table Incremental Address (12 entries) 
                   
                   
               
            
           
           
               
               
               
               
               
               
            
               
                 [1 2 3 
                 000xxxx + 
                 /B6&amp;/ 
                 Addr = 
                 113511 
                 −65536 
               
               
                 4 5 6 
                 1 
                 B5&amp;/B4 
                 [0~15] = 
                 126605 
                 −33924 
               
               
                   7  8 9 
                   
                   
                 n/3 − 1 
                 129080 
                 −22761 
               
               
                 10  11  12 
                   
                   
                   
                 129950 
                 −17109 
               
               
                   13   14  15 
                   
                   
                   
                 130353 
                 −13701 
               
               
                 16] 
                   
                   
                   
                 130573 
                 −11424 
               
               
                   
                   
                   
                   
                 130704 
                 −9795 
               
               
                   
                   
                   
                   
                 130791 
                 −8573 
               
               
                   
                   
                   
                   
                 130850 
                 −7622 
               
               
                   
                   
                   
                   
                 130892 
                 −6860 
               
               
                   
                   
                   
                   
                 130922 
                 −6237 
               
               
                   
                   
                   
                   
                 130947 
                 −5718 
               
               
                   
                   
                   
                   
                 130964 
                 −5278 
               
               
                   
                   
                   
                   
                 130979 
                 −4901 
               
               
                   
                   
                   
                   
                 130992 
                 −4575 
               
               
                   
                   
                   
                   
                 131001 
                 −4289 
               
            
           
           
               
               
               
            
               
                 Section 2: Dividable by 27 and larger than 16: 
                   
                   
               
               
                 (7 entries) 
               
            
           
           
               
               
               
               
               
               
            
               
                 18, 27, 36, 
                   
                   
                 Addr = 
                 131016 
                 −3813 
               
               
                 45, 54, 63, 
                   
                   
                 [0~7] = 
                 131047 
                 −2542 
               
               
                 72, 81, 
                   
                   
                 n/27 − 2. 
                 131058 
                 −1907 
               
               
                   
                   
                   
                   
                 131063 
                 −1526 
               
               
                   
                   
                   
                   
                 131065 
                 −1271 
               
               
                   
                   
                   
                   
                 131066 
                 −1090 
               
               
                   
                   
                   
                   
                 131068 
                 −954 
               
               
                   
                   
                   
                   
                 131069 
                 −848 
               
               
                   
               
            
           
         
       
     
       FIG. 23  shows an exemplary embodiment of an AGU  2300  for use in the look-up logic  2202 . For example, the AGU  2300  can be configured for use as any one of the AGUs  2210 ,  2212 , or  2214 . The AGU  2300  comprises unique ID logic decoder  2310  and address decoder  2320 . In an exemplary embodiment, the ID logic decoder  2310  comprises a state machine, discrete logic, memory, or other hardware logic to decode received values of n to generate unique logic decoded (ULD) output values  2330 . The decoded values  2330  are input to address encoder  2320  which generates an address to access the appropriate LUT to determine corresponding TFSV values. For example, as illustrated in Tables 5-6 above, values are n are processed by the unique ID logic of the AGU  2300  to determine an appropriate LUT address to obtain corresponding TFSV values. 
     Referring again to  FIG. 22 , in an exemplary embodiment, the base vector generator  2204  comprises an input register  2224 , a cross multiplier  2226 , an output register  2228  and a coefficient  2230 . During operation, the determined TFSV from the logic  2202  is received at the register  2224  and input to the cross multiplier  2226 . The cross multiplier  2226  also receives the coefficient value  2230  and multiplies it with the received TFSV. The output of the cross multiplier  2226  is input to the register  2228 , which may output the value to the register  2232  of the twiddle vector generator  2206  or may perform another iteration of the calculation. Once the correct base value is determined it is input to the twiddle vector generator  2206 . 
     The base values are received at serial to parallel register  2232 , which converts the base values into a base vector. The base vector is input to the vector register  2234 . The vector register  2234  outputs the base vector to a cross multiplier  2236  that performs several multiplication iterations to form a twiddle vector that is input to the vector output register  2240 . The vector output register  2240  outputs the twiddle factor vector to the twiddle multiplier  412 . 
     In an exemplary embodiment, when computing twiddle vectors for stages before the last stage, the cross multiplier  2236  performs several iterations to compute the appropriate twiddle matrix column according to the expression (BLS) above. 
     In an exemplary embodiment, when computing twiddle vectors for the last stage, the cross multiplier  2236  utilizes the step coefficients stored in the LUT  2238  to perform several iterations to compute the appropriate twiddle matrix sections according to the expression (LS) above. 
       FIG. 24  illustrates an exemplary method  2400  for operating a twiddle factor generator in a programmable vector processor with iterative pipeline in accordance with embodiments of the invention. For example, the method  2400  is suitable for use with the twiddle factor generator  422  shown in  FIG. 22 . 
     At block  2402 , current radix and n parameters are received. In an exemplary embodiment, the current radix and n parameters are received at the twiddle factor generator  422  as twiddle control factors (TCF)  456  from the state machine controller  426  as shown in  FIG. 4 . For example, a radix factorization is determined to compute an N-point DFT associated with a particular index value. The current radix and n parameters are received as TCF  456  that are used to generate on-the-fly twiddle vectors. 
     At block  2404 , an address is determined from the current radix and n parameters. For example, the AGU  2210 ,  2212 ,  2214  determine the address from the current radix and n parameters. In an exemplary embodiment, the AGUs operate as describe above and with reference to  FIG. 23  to generate a LUT address that is used to access the LUTs  2216 ,  2218 , and  2220 . 
     At block  2406 , a look-up table is accessed using the address to output a TFSV value. In an exemplary embodiment, the LUTS  2216 ,  2218 ,  2220  are accessed with the address generated by the appropriate AGU to output the appropriate TFSV value. 
     At block  2408 , base address values are generated using the TFSV value. In an exemplary embodiment, the base address generator  2204  operates to receive the TFSV value at the register  2224  and generate base values  2242  as described above. 
     At block  2410 , a determination is made as to whether the twiddle factors to be generated are for a last stage of a radix computation of the N-point DFT. If the twiddle factors that are to be generated are not for the last stage of the radix computation, then the method proceeds to block  2412 . If the twiddle factors are for the last stage, then the method proceeds to blocks  2416 - 2420 . 
     At block  2412 , the base vector  2242  is used to generate the required twiddle column vector. For example, the twiddle vector generator  2206  operates to receive the base vector and generate the appropriate twiddle column vector as described above with regards to generating twiddle vectors for stage before the last stage and as provided by the expression (BLS). 
     At block  2414 , the determined twiddle vector is output. For example, in an exemplary embodiment, the twiddle vectors are output to the twiddle multiplier  412  in the vector data pipeline  448 . The multiplier  412  multiples the twiddles vectors with data received from the pipeline to produce data to be input to the programmable mixed radix engine  414  that performs the current radix calculation. 
     At blocks  2416 - 2420 , twiddle vectors are generated for the three sections as described above with regards to generating twiddle vectors for the last stage. For example, the twiddle vector generator  2206  utilizes the coefficients for the last stage stored in LUT  2238  to generate the twiddle vectors for the three sections as described in expression (LS) above. The computed vectors are passed to block  2414  for output. 
     Thus, the method  2400  illustrates a method for operating a twiddle factor generation in a configurable vector mixed-radix engine with iterative pipeline in accordance with embodiments of the invention. It should be noted that the operations of the method  2400  may be modified, changed, rearranged or otherwise reconfigured within the scope of the exemplary embodiments. 
     While particular embodiments of the present invention have been shown and described, it will be obvious to those skilled in the art that, based upon the teachings herein, changes and modifications may be made without departing from these exemplary embodiments of the present invention and their broader aspects. Therefore, the appended claims are intended to encompass within their scope all such changes and modifications as are within the true spirit and scope of these exemplary embodiments of the present invention.