Methods for addressing input data values of a Fast Fourier Transform (FFT) calculation
A method for the generation of addresses of successive pairs of input data values of stages of a Fast Fourier Transform calculation stored contiguously in a memory includes initializing at most once per stage a first base address pointer to an address of a first input data value of an initial butterfly calculation of the stage and a second base address pointer to an address of a second input data value of the initial butterfly calculation, and initializing at most once per stage a first constant and a second constant. Pairs of input data values of successive butterfly calculations in the stage are then addressed using the first base address pointer, the second base address pointer, the first constant and the second constant.
1. A processor for digital signal processing comprising: a data address unit including at least:
a first base address register to store an address of a first input data value of an initial butterfly calculation of a particular stage of a Fast Fourier Transform calculation;
a second base address register to store an address of a second input data value of the initial butterfly calculation;
a first step register to store the sum of a data width of an input data value and the value 2 (log 2 N)−1+M , where N is the number of input data values counting from zero and M is an index of the stage counting from zero;
a second step register to store the logical NOT of the value 2 (log 2 N)−1+M ;
a scalar unit to update the contents of an address offset register once per butterfly calculation by adding the contents of the offset address register to the contents of the first step register to produce a first sum and then performing a logical AND operation on the first sum with the contents of the second step register;
an additional register to store the value 2 (log 2 N)−1 for the first stage of the Fast Fourier Transform calculation; and
a shift unit to perform a logical shift right by 1 bit to the additional register at most once per stage of the Fast Fourier Transform calculation, and to perform an arithmetic shift right by 1 bit to the second step register at most once per stage of the Fast Fourier Transform calculation,
wherein once per stage, the scalar unit is to add the contents of the additional register to the data width to produce a result and to store the result in the first step register.
2. The A device for digital signal processing comprising: a data address unit including at least:
a first base address register to store an address of a first input data value of an initial butterfly calculation of a particular stage of a Fast Fourier Transform calculation;
a second base address register to store an address of a second input data value of the initial butterfly calculation;
a first step register to store the sum of a data width of an input data value and the value 2 (log 2 N)−1+M where N is the number of input data values counting from zero and M is an index of the stage counting from zero;
a second step register to store the logical NOT of the value 2 (log 2 N)−1+M;
a scalar unit to update the contents of an address offset register once per butterfly calculation by adding the contents of the offset address register to the contents of the first step register to produce a first sum and then performing a logical AND operation on the first sum with the contents of the second step register;
an additional register to store the value 2 (log 2 N)−1 for the first stage of the Fast Fourier Transform calculation; and
a shift unit to perform a logical shift right by 1 bit to the additional register at most once per stage of the Fast Fourier Transform calculation, and to perform an arithmetic shift right by 1 bit to the second step register at most once per stage of the Fast Fourier Transform calculation,
wherein once per stage, the scalar unit is to add the contents of the additional register to the data width to produce a result and to store the result in the first step register.
3. An apparatus for digital signal processing comprising:
a memory to store contiguously input data values of a Fast Fourier Transform calculation; and
a processor including at least a data address unit, the data address unit including at least:
a first base address register to store an address of a first input data value of an initial butterfly calculation of a particular stage of a Fast Fourier Transform calculation;
a second base address register to store an address of a second input data value of the initial butterfly calculation;
a first step register to store the sum of a data width of an input data value and the value 2 (log 2 N)−1+M , where N is the number of input data values counting from zero and M is an index of the stage counting from zero;
a second step register to store the logical NOT of the value 2 (log 2 N)−1+M ;
a scalar unit to update the contents of an address offset register once per butterfly calculation by adding the contents of the offset address register to the contents of the first step register to produce a first sum and then performing a logical AND operation on the first sum with the contents of the second step register;
an additional register to store the value 2 (log 2 N)−1 for the first stage of the Fast Fourier Transform calculation; and
a shift unit to perform a logical shift right by 1 bit to the additional register at most once per stage of the Fast Fourier Transform calculation, and to perform an arithmetic shift right by 1 bit to the second step register at most once per stage of the Fast Fourier Transform calculation,
wherein once per stage, the scalar unit is to add the contents of the additional register to the data width to produce a result and to store the result in the first step register.