Patent Publication Number: US-9846678-B2

Title: Fast Fourier Transform (FFT) custom address generator

Description:
PRIORITY CLAIM 
     The present application claims benefit of priority to provisional application No. 62/235,356 titled “FAST FOURIER TRANSFORM (FFT) CUSTOM ADDRESS GENERATOR” and filed on Sep. 30, 2015, the entire contents of which is incorporated by reference in its entirety as though fully and completely set forth herein. 
    
    
     BACKGROUND 
     Technical Field 
     Embodiments described herein are related to the field of integrated circuit implementation, and more particularly to the address generation for memory access. 
     Description of the Related Art 
     Computing systems may include one or more processors for executing program instructions (commonly referred to as “software,” “firmware,” or “microcode). Such program instructions may be stored in a memory within a computing system. Alternatively, or additionally, program instructions may be stored in other mass storage devices, such as, hard disk drives, compact discs (CDs), and the like. 
     In addition to processors and memories, computing systems may include dedicated collections of circuits (commonly referred to as “Intellectual Property (IP) blocks” or simply “blocks”) that are dedicated to specific tasks. Such tasks may include formatting graphics or video data for display, sending and receiving data via a wired or wireless network, processing input from external sensors, microphones, and the like. 
     Data received from such external sensors may be processed according to a desired algorithm. In some cases, such as with audio data, for example, received data may be converted to the frequency domain using a Fast Fourier Transform (FFT) in order to perform additional analysis of the data. 
     SUMMARY OF THE EMBODIMENTS 
     Various embodiments of a processor are disclosed. Broadly speaking, a system, an apparatus, and a method are contemplated in which the apparatus includes a plurality of registers and circuitry coupled to the plurality of registers. The circuitry may be configured to set a count value to an initial value, and format the count value of the counter to generate first and second output values. The first and second output values may correspond to addresses used to access memory locations in a pattern according to execution of a Fast Fourier Transform (FFT) algorithm. The circuitry may be further configured to increment the count value of the counter circuit by an increment value to generate a next count value. In response to a determination that a processing stage of an FFT operation has completed, the circuitry may be further configured to re-set the count value to the initial value, and modify the increment value. 
     In another embodiment, increment value may be stored in a corresponding register of the plurality of registers. 
     In a further embodiment, to modify the increment value, the circuitry may be further configured to perform a shift left operation in the corresponding register of the plurality of registers. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The following detailed description makes reference to the accompanying drawings, which are now briefly described. 
         FIG. 1  illustrates a block diagram of an embodiment of a computing system. 
         FIG. 2  illustrates a block diagram of a signal processing unit. 
         FIG. 3  illustrates address generation for FFT memory access. 
         FIG. 4  illustrates address generation of FFT twiddle factor access. 
         FIG. 5  illustrates a flow diagram of an embodiment of a method for generating addresses for memory access while performing an FFT operation. 
         FIG. 6  illustrates a flow diagram of an embodiment of a method for calculating indicies to be used in memory access using a count value. 
         FIG. 7  illustrates a flow diagram of an embodiment of a method for generating addresses to access twiddle factors while performing an FFT operation. 
         FIG. 8  illustrates a flow diagram of an embodiment of a particular bit of a count value is changing during the calculation of addresses to access twiddle factors. 
         FIG. 9  illustrates a block diagram of a address generator circuit. 
         FIG. 10  illustrates a block diagram of a format circuit included in an address generator circuit. 
     
    
    
     While the disclosure is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the disclosure to the particular form illustrated, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present disclosure as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to. 
     Various units, circuits, or other components may be described as “configured to” perform a task or tasks. In such contexts, “configured to” is a broad recitation of structure generally meaning “having circuitry that” performs the task or tasks during operation. As such, the unit/circuit/component can be configured to perform the task even when the unit/circuit/component is not currently on. In general, the circuitry that forms the structure corresponding to “configured to” may include hardware circuits. Similarly, various units/circuits/components may be described as performing a task or tasks, for convenience in the description. Such descriptions should be interpreted as including the phrase “configured to.” Reciting a unit/circuit/component that is configured to perform one or more tasks is expressly intended not to invoke 35 U.S.C. §112, paragraph (f) interpretation for that unit/circuit/component. More generally, the recitation of any element is expressly intended not to invoke 35 U.S.C. §112, paragraph (f) interpretation for that element unless the language “means for” or “step for” is specifically recited. 
     DETAILED DESCRIPTION OF EMBODIMENTS 
     In a computer system, processors, processor cores, or other blocks may access memory to retrieve program instructions and data, or store recently modified data for retrieval at a later time. In some cases, the locations in memory that are being accessed are not random, but follow a distinct pattern, and the addresses corresponding to the desired locations in memory may be algorithmically calculated. Address generators may be used to perform the necessary calculations. Such generators may allow for high levels of execution parallelism using few encoded instruction bits, as well as increased efficiency and greater throughput. Additionally, address generators may be designed to provide common access patterns such as, e.g., Fast Fourier Transform (FFT) bit-reversed access, and base stride access. For each memory, or port in a multi-ported memory, a separate address generator may be employed or address generators may be shared between multiple ports. 
     A common case for accessing a memory is base-stride addressing. Each address may be calculated by f(i)=base+i·stride, where base is initial starting address, i is a positive integer, and stride is the step from one address to the next. Such an algorithm may be implemented in microcode instructions, however, it may require multiple instructions which would lead to increased area for the microcode memory, as well as added power consumption. The embodiments illustrated in the drawings and described below may provide techniques for generating addresses for memory access, while limiting area and power impact on the microcode memory. 
     For the purpose of clarity of explanation, in the algorithms disclosed herein, only index calculations are specified. In various embodiments, the indices may be used directly to access memory locations, while in other embodiments, the indices may be transformed into addresses using a base-stride or other suitable method. 
     Programs executed on computer systems, often refer to memory locations using indices. For example, individual elements of an array may be accessed using a corresponding index, such as, e.g., i, which may correspond to a particular location in memory of the computer system. Such indices may be converted to actual addresses to access the memory explicitly by a programmer, or automatically by compiler software. As described below, in more detail, the conversion from index to address may include adding a base address to the product of the index and an element and/or stride size. In some embodiments, the base address may be zero and the stride may be 1, resulting in a case where the index and the address are the same. 
     A block diagram illustrating an embodiment of computing system is illustrated in  FIG. 1 . Computer system  100  includes processor  101 , memory  103 , mass-storage device  105 , and signal processing unit  110 . It is noted that although specific components are shown and described in computer system  100 , in alternative embodiments different components and numbers of components may be present in computer system  100 . For example, computer system  100  may not include some of the memory hierarchy (e.g., memory  103  and/or mass-storage device  105 ). In addition, computer system  100  may include graphics processors, video cards, video-capture devices, user-interface devices, network cards, optical drives, and/or other peripheral devices that are coupled to processor  101  using a bus, a network, or another suitable communication channel (all not shown for simplicity). 
     In various embodiments, processor  101  may be representative of a general-purpose processor that performs computational operations. For example, processor  101  may be a central processing unit (CPU) such as a microprocessor, a microcontroller, a digital signal processor, an application-specific integrated circuit (ASIC), or a field-programmable gate array (FPGA). Although one processor  101  is illustrated, some embodiments of system  100  may include more than one processor  101 . In various embodiments, processor  101  may implement any suitable instruction set architecture (ISA), such as, e.g., ARM™, C6000™, Blackfin® or x86 ISAs, or combination thereof. 
     The memory  103  and mass-storage device  105  are storage devices that collectively form a memory hierarchy that stores data and instructions for processor  101 . More particularly, the mass-storage device  105  may be a high-capacity, non-volatile memory, such as a disk drive or a large flash memory unit with a long access time, while memory  103  may be smaller, with shorter access times. Memory  103  may store copies of frequently used data. Memory  103  may be representative of a memory device in the dynamic random access memory (DRAM) family of memory devices. In some embodiments, memory  103  and mass-storage device  105  are shared between one or more processors in computer system  100 . 
     Signal processing unit  110  may, in various embodiments, be configured to execute one or more digital signal processing algorithms on data received by computer system  100  through an external sensor (not shown) or other data source. Such processing algorithms may include Fast Fourier Transform (FFT), Infinite Impluse Response (IIR) filtering, and the like. 
     In some embodiments, signal processing unit  110  may be configured to process audio data received from a microphone or other audio source. Signal processing unit  110  may process the audio data to detect specific words or phrases within the audio data. 
     It is also noted that the system illustrated in  FIG. 1  is merely an example. In other embodiments, different functional blocks and different configurations of functional blocks may be possible dependent upon the specific application for which the system is intended. 
     Turning to  FIG. 2 , a block diagram of a signal processing unit is illustrated. In various embodiments, signal processing unit  200  may correspond to signal processing unit  110  as depicted in the embodiment illustrated in  FIG. 1 . In the illustrated embodiment, signal processing unit  200  includes sequencer  201 , operand router  202 , function units  203 , write address generator  204 , read address generator  205 , and memory  206 . In various embodiments, signal processing unit  200  may be configured to operate on complex numbers. For example, a 64-bit data word may include both real and imaginary floating point numbers. 
     Sequencer  201  may include a microcode memory configured to store program instructions as well to perform instruction fetch, decode, hazard detection, stall, control functions, and the like. Sequencer  201  may also include logic circuits specifically configured to perform the stored program instructions such as instruction fetch, decode, hazard detection, stall, control functions and the like. Logic circuits external to sequencer  201  (not shown) may select an entry address for the start of execution of a portion of the program instructions stored in the microcode memory and then signal sequencer  201  to begin execution at the selected entry address. In response to execution of program instructions by sequencer  201 , data may be read from memory  206 , routed into function units  203 . Once function units  203  have operated upon the data, results may then be re-written back into memory  206 . 
     Function units  203  may, in some embodiments, be organized into real and imaginary sides to operate on the complex numbers. In various embodiments, function units  203  may include Arithmetic Logic Units (ALUs), as well as circuits dedicated to performing square root and logarithmic calculations. In some embodiments, sub-units included in function units  203 , may be organized in a pipelined fashion, allowing different stages to perform different operations at different times. 
     Read operand router  202  may be configured to selectively route data from memory  206  into function units  203 . Write operand router  207  may be configured to selectively route data from function units  203  to memory  206 . In various embodiments, read operand router  202  may individually route real or imaginary portions of a complex number into a port of function units  203 . Additionally, write operand router  207  may individually route real or imaginary portions of a complex number into a port of memory  206 . 
     Memory  206  may be configured to store parameters set by system software, intermediate data used during calculations, and the like. In some embodiments, so-called “twiddle factors” used in FFT, which refer to multiplicative constants used in the transform, may also be stored in memory  206 . Although memory  206  is depicted as a single memory, in other embodiments, any suitable number of memories may be employed. In cases where multiple memories are employed, each memory may be configured to store different data, such as the aforementioned intermediate data. Each memory may be read independently of the others, allowing multiple read accesses to be performed simultaneously. 
     In the course of executing an FFT algorithm, the data stored in memory  206  may need to be accessed according to a predetermined sequence. As described below in regard to  FIGS. 3 and 4 , the sequence for accessing the intermediate data may be different than the sequence for accessing the twiddle factors. In some embodiments, different address generators may be employed for memory access versus twiddle factor access while, in other embodiments, a single address generator may be capable of producing addresses used in both types of accesses. 
     Memory  206  may incorporate multiple instances of memory circuits, such as, e.g., Static Random Access Memory (SRAM), or a Read Only Memory (ROM), or any suitable combination thereof. 
     To access memory  206  at the desired locations, address generators are employed to create the desired addresses for accessing memory  206 . As described above, addresses may be generated from indices. As used and described herein, the terms indices and addresses are used interchangeably with the understanding that, in some embodiments, indices may be transformed into addresses. In the illustrated embodiment, separate read and write address generators are employed. In some embodiments, multiple read address generators may be used to allow for parallel read access to different memories included in memory  206 . 
     As will be described below in more detail, read address generator  205  and write address generator  204  may generate addresses in accordance with a predetermined FFT algorithm. In cases where multiple read address generators are employed, each read address generator may create addresses using different respective algorithms. For example, a particular read address generator may implement a base-stride addressing algorithm, while other read address generators may implement any suitable addressing algorithm. By implementing address generation, both read and write, as specialized hardware circuits, program instructions for calculating the addresses may be omitted from the microcode memory in sequencer  201 , thereby saving area and power, in some embodiments. The omission of address calculation instructions reduces a number of executed instructions in the program leading to faster execution especially inside of loops. In some embodiments, faster execution may allow for logic circuits to quickly be placed in a low power state following signal processing, thereby reducing power consumption. 
     It is noted that the embodiment of signal processing unit  200  as illustrated in  FIG. 2  is merely an example. Some blocks included within signal processing unit  200 , and some connections between the blocks have been omitted for the sake of clarity. In other embodiments, different blocks and different configurations of blocks are possible and contemplated. 
     As previously mentioned, during complex FFT operations, memory locations may be addressed in accordance with a predefined algorithm. One such algorithm is illustrated in Example 1, shown below. In Example 1, the two inner for-loops, one for j and the other for even_index, together result in the same number of inner loop body executions independent of the current value of stage in the outer for-loop. For example, for a 256-point complex FFT, the number of innermost loop body executions is 128 regardless of the current value of stage in the outer loop. Although the processing order varies from iteration to iteration, the aforementioned inner for-loops touch every element exactly once. It is noted that the last odd_index processed by the two inner for-loops is always  255 . In various embodiments, the detection of the value of 255 for the odd_index may assist in the determination that the address generator has reached the end of the inner for-loops and needs to be re-initialized. The outer for-loop may then also be advanced by shifting the value of SN by one bit and resetting the count to zero, to continue processing the next stage of the FFT. 
     Each stage the step size, by which the counter counts, varies to allow for the creation of desired indices. The value from the counter may be split into high and low bits, which may, in some embodiments, be combined using a bitwise OR operation to obtain even_index. At a particular stage of the FFT operation, s+1, there are log 2 (s) zeros at the least significant end of the counter since the counter increases by a power of 2. These bits may be set to the value of j, which, in this implementation, is the same of the value of the high bits of the counter. Odd_index may be generated by combining even_index with SN_by_2 using a bitwise OR operation. 
     While performing an FFT operation, in addition to memory accesses, predetermined multiplicative constants (commonly referred to as “twiddle factors”) may be read from storage and used in the calculations for each stage of the FFT. Such twiddle factors may be accessed in a predetermined sequence and, as such, the addresses to read the twiddle factors from memory may be generated algorithmically. The generation of the addresses to retrieve the twiddle factors is also presented in Example 1. For each pass through the j inner for-loop, a new twiddle factor needs to be retrieved from storage. Additionally, each time the algorithm moves to the next stage, the twiddle factors need to be reset. While the innermost loop is executed, the twiddle factor remains the same. It is noted that during the first stage, only one twiddle factor is used, so the algorithm returns the same value 128 times. In contrast, during the final stage, the twiddle factor changes each time. The stride value is a power of 2, and may change with each stage. For example, in the first stage, the stride is 128, in the second stage, the stride is 64, and so forth. During the final stage, the stride value is 1. 
     It is noted that Example 1 is merely one representative algorithm. In other embodiments, differences in the execution of the for-loops is possible and contemplated. It is further noted that since the generation of addresses to access the memory, as well as retrieve twiddle factors, both rely on a determination of when the loop index j changes and when the stage changes, dedicated circuits to generate the aforementioned addresses may share portions of the their respective designs. 
     Example 1: FFT Algorithm 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 for stage in range(1,nstage+1): 
               
            
           
           
               
               
            
               
                   
                 SN = 1 &lt;&lt; stage 
               
               
                   
                 SN_by_2 = SN/2• 
               
               
                   
                 SW = twiddle_v[stage] 
               
               
                   
                 twiddle = 1+0j• 
               
               
                   
                 for j in range(SN_by_2): 
               
            
           
           
               
               
            
               
                   
                 for even_index in range(j,N,SN): 
               
            
           
           
               
               
            
               
                   
                 odd_index = even_index + SN_by_2 
               
               
                   
                 x_e = x_v[even_index] 
               
               
                   
                 x_o = x_v[odd_index] 
               
               
                   
                 t = x_o * twiddle 
               
               
                   
                 x_v[even_index] = x_e + t 
               
               
                   
                 x_v[odd_index] = x_e − t 
               
            
           
           
               
               
            
               
                   
                 twiddle *= SW 
               
            
           
           
               
               
            
               
                   
                 return x_v 
               
               
                   
                   
               
            
           
         
       
     
     An embodiment of an algorithm for generating Complex FFT addresses is illustrated in Example 2. A state machine may, in some embodiments, be configured to implement the algorithm. In various embodiments, the _init_( ) function may include configuration steps performed by system software to setup the associated hardware. During execution, the start ( ) function includes both initialization and re-initialization steps that may be performed at the start of operation or during a stage change. 
     The value of even_index may be returned by evoking get_index (0), and the value of odd_index may be returned by evoking get_index (1). Once the indices corresponding to a given iteration have been consumed, the next ( ) function is executed. In various embodiments, the next ( ) function may increment the count value as well as adjust the step size. 
     It is noted that in the embodiment of Example 2, is directed towards address generation for Complex FFT operations, i.e., FFT operations that can be used with complex numbers. In some embodiments, a Complex FFT may be used as a building block for implementing an optimized real valued FFT. Some actual implementations may employ a Complex FFT as part of a real number valued FFT. 
     Example 2: Complex FFT Address Generator Algorithm 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 class ComplexFFTAddressGenerator(object): 
               
            
           
           
               
               
            
               
                   
                 def  —— init —— (self, N): 
               
            
           
           
               
               
            
               
                   
                 self.N = N 
               
               
                   
                 self.nbits = int(ceil(log2(N))) 
               
            
           
           
               
               
            
               
                   
                 def start(self): 
               
            
           
           
               
               
            
               
                   
                 self.count = 0 
               
               
                   
                 self.SN = 2 
               
               
                   
                 self.SN_by_2 = 1 
               
            
           
           
               
               
            
               
                   
                 def get_index(self, which): 
               
            
           
           
               
               
            
               
                   
                 even_index = self.get_even_index( ) 
               
               
                   
                 if which: 
               
            
           
           
               
               
            
               
                   
                 return even_index | self.SN_by_2 
               
            
           
           
               
               
            
               
                   
                 return even_index 
               
            
           
           
               
               
            
               
                   
                 def get_even_index(self): 
               
            
           
           
               
               
            
               
                   
                 high_bits = self.count &gt;&gt; self.nbits 
               
               
                   
                 low_bits = self.count &amp; (self.N−1) 
               
               
                   
                 even_index = low_bits | high_bits 
               
               
                   
                 return even_index 
               
            
           
           
               
               
            
               
                   
                 def next(self): 
               
            
           
           
               
               
            
               
                   
                 even_index = self.get_even_index( ) 
               
               
                   
                 odd_index = even_index | self.SN_by_2 
               
               
                   
                 if odd_index == self.N−1: 
               
            
           
           
               
               
            
               
                   
                 self.count = 0 
               
               
                   
                 self.SN &lt;&lt;= 1 
               
               
                   
                 self.SN_by_2 &lt;&lt;= 1 
               
            
           
           
               
               
            
               
                   
                 else: 
               
            
           
           
               
               
            
               
                   
                 self.count += self.SN 
               
               
                   
                   
               
            
           
         
       
     
     An embodiment of an algorithm for generating twiddle addresses is illustrated in Example 3. As with the embodiment depicted in Example 2, the _init_( ) function may include configuration steps performed by system software to setup the associated hardware. During execution, the start ( ) function includes both initialization and re-initialization steps that may be performed at the start of operation or during a stage change. In the present example, the initialization and re-initialization steps may include setting an initial value for the index, as well as, setting initial values for the variables count, stride, and SN. 
     After initialization or re-initialization, the next ( ) function generates the next state of the address generator. The algorithm may determine if the nth bit of the count value is changing. As described below in more detail, the nth bit is a function of the size of the FFT. If the nth bit of the count value changes from the current count value to the next count value, the index value is incremented by the stride value. Additionally, when the index value reaches a last value indicating that the final twiddle factor for the current stage has been passed, the stage indicator SN is advanced to the next stage, the stride value in incremented, and the count and index values are re-initialized. 
     Example 3: Twiddle Address Generator Algorithm 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 class TwiddleAddressGenerator(object): 
               
            
           
           
               
               
            
               
                   
                 def  —— init —— (self, N): 
               
            
           
           
               
               
            
               
                   
                 self.last = N/2 
               
               
                   
                 self.first = 0 
               
               
                   
                 self.nbits = int(ceil(log2(N))) 
               
            
           
           
               
               
            
               
                   
                 def start(self): 
               
            
           
           
               
               
            
               
                   
                 self.index = self.first 
               
               
                   
                 self.stride = 1 &lt;&lt; (self.nbits−1) 
               
               
                   
                 self.count = 0 
               
               
                   
                 self.SN = 2 
               
            
           
           
               
               
            
               
                   
                 def get_index(self): 
               
            
           
           
               
               
            
               
                   
                 return self.index 
               
            
           
           
               
               
            
               
                   
                 def next(self): 
               
            
           
           
               
               
            
               
                   
                 // if n-th bit of count is changing, then 
               
            
           
           
               
               
            
               
                   
                 update the index 
               
            
           
           
               
               
            
               
                   
                 prev_bit = self.count &amp; (1 &lt;&lt; self.nbits) 
               
               
                   
                 self.count += self.SN 
               
               
                   
                 cur_bit = self.count &amp; (1 &lt;&lt; self.nbits) 
               
               
                   
                 bit = prev_bit {circumflex over ( )} cur_bit 
               
               
                   
                 if bit: 
               
            
           
           
               
               
            
               
                   
                 self.index += self.stride 
               
               
                   
                 // if the final twiddle factor has been passed, 
               
            
           
           
               
               
            
               
                   
                 advance to next stage and re-init 
               
            
           
           
               
               
            
               
                   
                 if self.index == self.last: 
               
            
           
           
               
               
            
               
                   
                 self.count = 0 
               
               
                   
                 self.SN &lt;&lt;= 1 
               
               
                   
                 self.index = self.first 
               
               
                   
                 self.stride = self.stride &gt;&gt; 1 
               
               
                   
                   
               
            
           
         
       
     
     The algorithms illustrated in Examples 1-3 are presented for illustrative purposes. In other embodiments, the calculations included in each of the algorithms may be modified to be suitable with logic circuit design. It is noted that the algorithms depicted in Examples 1, 2, and 3 are intended to operate on unsigned integers. In other embodiments, different operations may be employed to account for signed bits. In cases where the description included herein deviates from the embodiments of Examples 1-3, it is noted that embodiments described in Examples 1-3 are preferred. 
     Turning to  FIG. 3 , an example of a memory address sequence used during a 512 point complex FFT operation is illustrated based on the algorithm described above in regard to Example 1 and Example 2. In the illustrated embodiment, addresses for the first three of eight stages of the FFT operation are depicted. Additionally, settings for variables used in the generation of the address sequences are shown for each stage. It is noted, that the three depicted stages are merely for the purposes of illustration, and that actual implementations may employ any suitable number of stages. It is further noted that the aforementioned method of address generation may be generalized to an FFT of any size that is a power of two or to sizes that are not powers of two by zero padding or other modifications to the FFT algorithm. 
     In stage 0, Count is initialized to zero, Step is initialized to two, and Step/2 is set to one. As described below in more detail in regard to  FIG. 5 , the aforementioned variable values are used to generate the odd and even indices. As indicated, the Odd Index includes odd numbers from 1 to 255 (the last or maximum index value for this particular addressing scheme). The Even Index includes even numbers between 0 and 254. 
     When stage 0 has completed, the values of Count, Step, and Step/2 are re-initialized. In the present embodiment, count is reset to zero, while step is set to four and Step/2 is initialized to two. Using the new values for the variables, the odd and even indices take on different values. During stage 1, the Odd Index includes values starting at two and counts by four to a value of 254, at which point, the sequence continues starting at three and counts by four to a value of 255 (the maximum value). The Even Index starts at zero and proceeds by four to a value of 252, at which point, the sequence continues from one and counts by four to a value of 253. 
     At the start of Stage 2, the variables are again re-initialized. In this case, Count is reset to zero, step is set to 8, and Step/2 is set to four. The re-initialized values are then used to generate new values for the odd and even indices. The Odd Index begins at 4 and increases by 8 until a value of 252 is reached. At that point, the Odd Index value changes to 5 and continues, incrementing by 8, until the value of 253 is achieved. Finally, the Odd Index value changes to 7 and increments by 8 until the value of 255 is reached. 
     In a similar fashion, the Even Index begins at zero, and increments by 8 until the value of 248 is reached. At that point, the Even Index value transitions to 1 and increments by 8 until the value of 249 is achieved. The Even Index value then changes to 2, and proceeds, counting by 8, until the value 250 is achieved. Finally, the Even Index value transitions to 3, and increments by 8 until the final value of 251 is reached. 
     It is noted that the embodiment illustrated in  FIG. 3  is merely an example. In other embodiments, different sequences of addresses that support other signal processing operations may be possible. 
     Turning to  FIG. 4 , a diagram depicting address generation for accessing a sequence of twiddle factors during a FFT operation is illustrated. In the present embodiment, the twiddle factors, or any suitable portion thereof, may be stored in any suitable location. For example, the twiddle factors may be stored sequentially in memory addresses 0 through 127 as described above in regard to Example 1 and Example 3. Twiddle factors may be stored at any other memory address using a transformation similar to base-stride as described above. As above, the data for only a few stages of the FFT operation is shown. In actual implementations, addresses for accessing twiddle factors may be generated for each stage of the FFT operation. 
     During the initial stage, i.e., Stage 0, the variables Stride, Index, Count and Step are initialized. The value of Index, which will contain the addresses to be used for accessing the twiddle factors, is set to a base value, which may be dependent upon a particular embodiment. The value of Count is set to zero, the value of Stride is set to 128, and the value of Step is set to 2. During stage 0, 128 addresses, each of which will have a value of zero, will be generated. Once the last index has been reached, the next stage of the FFT operation may begin. 
     At the start of Stage 1, Count and Index are re-initialized to zero and base, respectively. The value of Stride is initialized to 64 and the value of Step is set to four. By setting Step and Stride to these particular values, a different set of addresses may then be generated for accessing twiddle factors during stage 1. In the present stage, the sequence of generated addresses, i.e., the value of Index, includes zero repeated 64 times, followed by 64 repeated 64 times. 
     The process of re-initializing the variables and generating addresses may then continue for each remaining stage. For example, in Stage 6, a sequence of even numbers, each one of which is repeated twice is generated. In the final stage, the generated addresses start at zero, and proceed to 127, incrementing by one. 
     It is noted that address scheme depicted in  FIG. 4  is merely an example. In other embodiments, different initialization values and different sequences of addresses may be employed. 
     As described above in regard to  FIG. 3 , during a FFT operation, a sequence of addresses may be generated to access memory for each stage of the FFT operation. Each stage may require a different sequence addresses in order to properly implement the FFT operation. Moving to  FIG. 5 , a flow diagram depicting an embodiment of a method for generating addresses to access a memory during a FFT operation is illustrated. The method begins in block  501 . A count value and a step may then be initialized (block  502 ). In various embodiments, a counter may be reset to a value of all logical-0s and a register may be loaded with a initial step size. 
     Address indices may then be calculated dependent upon a value of the counter (block  503 ). As described above in regard to  FIG. 3 , the indices may include both an even and an odd index that may correspond to addresses used in the sequential addressing scheme of a FFT algorithm. As described below in more detail in regard to  FIG. 4 , the value of the counter may be formatted to generate the even index. The even index may then be combined with additional information to generate the odd index. By processing the count value in such a manner, two indices that comply with the FFT memory access scheme may be generated from a single count value. 
     The method may then depend on the value of the odd index (block  504 ). In various embodiments, if the odd index has not yet reached a maximum value, such as, e.g., a value consisting of all logical-1s, then the count value may be incremented (block  505 ). The count value may, in some embodiments, be incremented by the step size stored in the register. In various embodiments, the step size value may be added to the count value, and the resultant sum may then be stored in the in counter to be used in further calculations. The method may then proceed from block  503  as described above. 
     If, however, the odd index has reached the maximum value, then the operation is dependent on the stage of the FFT operation (block  506 ). If the last stage has been reached, then the method may conclude in block  507 . 
     Alternatively, if the last stage has not yet been reached, then the count value may be re-initialized and the step size value may be modified (block  508 ). In various embodiments, the count value may be reset to zero, or any other suitable value. The step size value may, in some embodiments, be incremented by a factor of two. In certain embodiments, a shift operation may be performed on the register, in which the step size value is stored, thereby generating a new step size value that is twice the old step size value. The method may then proceed from block  503  as described above. 
     It is noted that the embodiment of the method depicted in the flow diagram illustrated in  FIG. 5  is merely an example. In other embodiments, different operations, and different orders of operations may be employed. 
     As described above, multiple indices may be generated from a single count value. A flow diagram depicting an embodiment of a method for generating two indices used in FFT memory access from a single count value is illustrated in  FIG. 6 . In various embodiments, the method depicted in the flow diagram of  FIG. 6 , may correspond to the operation described in block  503  of the flow diagram illustrated in  FIG. 5 . The method begins in block  601 . 
     The count value may then be split into two parts (block  602 ). In some embodiments, to generate a data word containing the low order bits, a bitwise AND operation may be performed on the count value and a data word containing the maximum value of the FFT indices. The high order bits may be, in various embodiments, generated by shifting the count value by maximum number of stages of the FFT of given size. 
     A bitwise OR operation may then be performed on the data words containing the high and low order bits in order to generate an even index, such as those described above in regard to  FIG. 3  (block  603 ). 
     Another bitwise OR operation may then be performed on using the even index and a data word containing half of the step value to generate an odd index, such as those described in regard to  FIG. 3  (block  604 ). As with the previous bitwise OR operation, multiple OR gates may be employed. With the generation of the even and the odd indices, the operation may conclude in block  605 . 
     The operations included in the flow diagram illustrated in  FIG. 6  are depicted as being performed in a serial fashion. In other embodiments, one or more of the operations may be performed in parallel. 
     During an FFT operation, in addition to memory accesses, predetermined twiddle factors may be read from a separate memory and used in the calculations for each stage of the FFT. Such twiddle factors may be accessed in a predetermined sequence and, as such, the addresses to read the twiddle factors from memory may be generated algorithmically. An embodiment of a method for generating the addresses to read the twiddle factors for a FFT operation is depicted in the flow diagram illustrated in  FIG. 7 . The method begins in block  701 . 
     A count value, an index value, a stride value, and a step value may then be initialized (block  702 ). It is noted that the index, stride and step values may be stored in respective registers, and that the count value may be stored in a counter or other suitable sequential logic circuit. In various embodiments, the count value may be initialized to zero, and the index value, which will be used to access the twiddle factors, may be initialized to a base value. In some embodiments, the stride value may be set to 128, and the step value may be set to 2. 
     A determination may then be made if the nth bit position of the count value is changing (block  703 ). The nth bit position may, in various embodiments, dependent on the size of the FFT. For example, in some embodiments, the nth bit position may be determined using equation 1 (below), wherein N is the size of FFT. As a specific example, when the size of the FFT is 512, the nth bit position is determined to be 9. As described below in more detail in regard to  FIG. 8 , a next count value may be generated, and the nth bit value of the previous count value and the newly generated next count value may be compared. The method may then depend on the result of the determination (block  704 ).
 
 n=int ( ceil (log 2 ( N )))  (1)
 
     If the nth bit of the count value is changing, then the index value may be incremented (block  705 ). In various embodiments, the stride value may be added to the index value, and the index value used to access the memory, in which the twiddle factors are stored. Alternatively, if it is determined that the nth bit of the count value is not changing, then the method may proceed from block  706  as described below. 
     The method may then depend on the current stage of the FFT operation (block  706 ). If the last stage of the FFT operation has been reached, then the method may conclude in block  707 . If, however, the last stage has not yet been reached, then the method may depend on the value of the index (block  708 ). If the last index has not yet been reached, then the method may proceed from block  703  as described above. Alternatively, if the index has reached a final value, then the count and index values may be reset, and the stride and step values may be modified (block  709 ). In some embodiments, the count value may be reset to zero, and the index value may be reset to the base value. Additionally, the step value may be incremented by two, while the stride value may be divided by two. In various embodiments, a shift operation on the register storing the stride value may be performed, dividing the stored stride value by two. The operation may then proceed from block  703  as described above. 
     It is noted that the embodiment illustrated in the flow diagram of  FIG. 7  is merely an example. In other embodiments, different increment/decrement values for the stride and step values may be employed, in order to generate addresses compatible with other twiddle factor access algorithms. 
     The method described above in regard to  FIG. 7 , employs checking if the nth bit of the count value changes from one count value to the next. It is noted that there are numerous methods for determining if the nth bit has changed value, but that a particular method is depicted in the flow diagram illustrated in  FIG. 8 . It is further noted that the embodiment of the method depicted in the flow diagram of  FIG. 8  may correspond to the operation described in relation to block  703  of the flow diagram illustrated in  FIG. 7 . The method begins in block  801 . 
     The nth bit of the current count value may then be determined (block  802 ). In various embodiments, a bitwise AND operation may be performed on the current count value and a logical 1 value that has been shifted left by the value of n, which may be calculated in accordance with equation 1, as described above. 
     The count value may then be incremented (block  804 ). In various embodiments, the step value may be added to the current count value to generate a next count value. The next count value may then be stored in the counter. 
     In a similar fashion to the procedure described above, the nth bit of the next count value may then be determined (block  804 ). An exclusive OR operation may then be performed on the two nth bit values (block  805 ) to determine if the values are identical. The resultant information may then be used as described in block  704  of the flow diagram illustrated in  FIG. 7 . The method may then conclude in block  806 . 
     It is noted that the method illustrated in  FIG. 8  is merely an example. In other embodiments, different operations and different orders of operations are possible and contemplated. 
     Moving to  FIG. 9 , a block diagram of an address generator circuit  900  is illustrated. Address generator circuit  900  may, in various embodiments, correspond to either of Read Address Generator  205  or Write Address Generator  204  as illustrated in the embodiment depicted in  FIG. 2 , and may be configured to implement one or more of the algorithms depicted in  FIG. 3  through  FIG. 8 . By implementing the aforementioned algorithms using address generator circuit  900 , power and area associated with a software implementation of an address generation algorithm may be saved. In the illustrated embodiment, address generator circuit  900  includes Control and Next State Logic  901 , Format Circuit  904 , and Current State Registers  903 . The count value as well as half step value are communicated via  906 . Additionally, the count value, increment updates, etc., are communicated via  909 . 
     Control and Next State Logic  901  may be associated with multiple registers holding state, such as, e.g., the current value of count and increment, as well as other parameters used in address generation. Any suitable arrangement of the multiple registers may be updated in isolation, or together, either sequentially or in parallel. 
     Current State Registers  903  may, in various embodiments, may include multiple registers, each of which may be configured to store values related to FFT and twiddle factor address calculations. Each of the multiple registers may include multiple storage elements, each storage element configured to store a respective data bit of a particular value, such as, e.g., a step value, a base value, a stride value, or any other suitable values used in the generation of the access addresses. Such values may, in some embodiments, be configurable via system software. 
     In other embodiments, values stored in Current State Registers  903  may be updated or modified during operation. For example, circuitry may increase the step value using a one bit shift left operation, and update the relevant bits in the Current State Registers  903 . 
     As described below, in more detail, in regard to  FIG. 10 , Format Circuit  904  may generate the even and odd indices for accessing the memory or twiddle factors during FFT operations. Dependent on whether address generator is being employed to generate memory access addresses, or twiddle factor access address, Format Circuit  904  may be configured to perform different format operations. 
     During the generation of access addresses for twiddle factors, an index value may be generated to be used as an address. In response to a determination that a particular bit of the count value is changing as Control and Next State Logic  901  increments, the index value may be incremented by the stride value. In various embodiments, the index value may be initialized or re-initialized to the base value or other suitable initial value. 
     In some embodiments, Format Circuit  904  may combine count value  906  with other values to generate Even Index  907  and Odd Index  908 . In various embodiments, even index  907  and Odd Index  908  may correspond to the even and odd indices described in regard to  FIG. 3 . In some cases, such as the generation of twiddle factor addresses, Format Circuit  904  may be omitted from address generator circuit  900 . 
     Control and next state logic  901  may, in various embodiments, compare count value  906  to a predetermined value. For example, in some embodiments, control and next state logic  901  may compare counter value  906  to a data word consisting of all logical-1 values. Additionally, Control and next state logic  901  may determine when all the stages of an FFT operation have completed. 
     During the generation of access addresses for twiddle factors, Control and next state logic  901  may be configured to determine if a particular bit of the count value is changing from a particular count value to a next count value. The particular bit of the count value may, in some embodiments, be a constant bit of the count value, or any other suitable data bit included in the count value. Control and next state logic  901  may determine the value of the particular bit for a current count value and then, in response to the count value being incremented, determine the value of the particular bit for the newly updated count value. In various embodiments, Control and next state logic  901  may then perform an exclusive OR operation on the two values of the particular bit. 
     It is noted that the embodiment illustrated in  FIG. 9  is merely an example. In other embodiments, various versions of format circuit  904  may be employed that allow the generation of both memory access addresses and twiddle factor access addresses using a single address generator circuit. 
     Turning now to  FIG. 10 , a block diagram of a format circuit that may be used in the generation of memory access addresses for a FFT operation is illustrated. In some embodiments, Format circuit  1000  may correspond to Format circuit  904  as depicted in the embodiment illustrated in  FIG. 9 . In the illustrated embodiment, Format circuit  1000  includes OR gates  1004  and  1007 . 
     During operation, count value  1001 , which may correspond to count value  906  as illustrated in  FIG. 9 , may be split into high bits  1002  and low bits  1003 . Each of high bits  1002  and low bits  1003  are coupled to the inputs of OR gates  1004 . OR gates  1004  may include multiple OR gates each or which performed a bitwise OR of corresponding bits from high bits  1002  and low bits  1003 . The result of the bitwise OR operation performed by OR gates  1004  generates even index  1005 . In various embodiments, even index  1005  may correspond to the even indices depicted in  FIG. 3  and  FIG. 4 . 
     As described above in regard to  FIG. 3 ,  FIG. 4 , and  FIG. 5 , a single count value may be used to generate multiple indices, such as, even index  907  and odd index  908  as illustrated in  FIG. 9 , for example. In the present embodiment, odd index  1008  is generated using even index  1005  and half step value  1006 . It is noted that half step value  1006  may be the step value by which the count value was increment divided by two. In a similar fashion to OR gates  1004 , OR gates  1007  may be configured to perform a bitwise OR operation on the two aforementioned values to generate odd index  1008 . 
     It is noted that the method illustrated in  FIG. 10  is merely an example embodiment. The generation of even index  1005  and odd index  1008  as depicted in  FIG. 10  represents only one type of index generation. In other embodiments, different combinations of data bits including the count values, step value, and the like, may be combined in different ways, using different logic functions, to achieve different address sequences. 
     Although specific embodiments have been described above, these embodiments are not intended to limit the scope of the present disclosure, even where only a single embodiment is described with respect to a particular feature. Examples of features provided in the disclosure are intended to be illustrative rather than restrictive unless stated otherwise. The above description is intended to cover such alternatives, modifications, and equivalents as would be apparent to a person skilled in the art having the benefit of this disclosure. 
     The scope of the present disclosure includes any feature or combination of features disclosed herein (either explicitly or implicitly), or any generalization thereof, whether or not it mitigates any or all of the problems addressed herein. Accordingly, new claims may be formulated during prosecution of this application (or an application claiming priority thereto) to any such combination of features. In particular, with reference to the appended claims, features from dependent claims may be combined with those of the independent claims and features from respective independent claims may be combined in any appropriate manner and not merely in the specific combinations enumerated in the appended claims.