Apparatus for generating memory addresses for accessing and storing data in an FFT (Fast Fourier Transform) computation is provided. The FFT computation is typically performed by computing a plurality of FFT butterflies belonging to a plurality of ranks. The apparatus includes a butterfly counter for determining the current FFT butterfly being computed. The butterfly counter produces a plurality of butterfly carries. A rank counter for determining the rank of said current FFT butterfly being computed produces a rank number. Coupled to the rank and butterfly counters is incremental curcuitry, which generates an incremental number in response to the rank number and the butterfly carries. An adder circuitry coupled to the incremental circuitry adds the incremental number and a plurality of memory addresses to produce the FFT data memory addresses.
A Fast Fourier Transform (FFT) apparatus for selectively performing Fast Hadamard transform (FHT), and a complementary code keying (CCK) modulation/demodulation apparatus using the same. An OFDM module and CCK module are integrated as one module having lower complexity compared to conventional scheme by embodying the CCK modulation using FFT structure in the OFDM module, and embodying the suboptimal and the optimized CCK modulations using FFT structure in OFDM module. CDMA, OFDM, CCK modules may be integrated as single module.
A hardware arrangement for a fast Fourier Transform includes, an arithmetic unit for executing said fast Fourier Transform, a data memory for storing data to be executed and storing results thereof, and an address generator for generating addresses to be applied to said data memory. The hardware arrangement further is provided with a bit rotation circuit coupled to receive each of said addresses. The circuit rotates a predetermined number of lower bits of each of said addresses such as to locate the least significant bit at the upper bit position of said predetermined number of lower bits and shift the remaining bits towards the least significant bit by one.
An address generator for use in conjunction with a fast Fourier transform processor includes an efficient architecture for computing the memory addresses of input data points, output data points and twiddle coefficients. In particular, multiplication operation in the calculation of memory addresses is minimized. Instead, a cascaded series of adders is used, in which the output of one adder is input to the next adder. At each stage of the cascaded adders, the same input variable is successively added. The cascaded adder structure is used in the writing address generator, the reading address generator and the twiddle coefficient address generator. In addition, a plurality of modulo N circuits is used in series with the cascaded series of adders to generate the twiddle coefficient addresses.
For each input block of N data bits received as an input to a stage for computing a Fourier transform, only three quarters of the data bits of the input block are stored in a main storage. A Fourier transform computation is performed on the basis of the stored data and of the other data of the block. Only half of the data bits received are stored in an auxiliary storage. All the data bits of the input block are reconstructed from the contents of the main and auxiliary storage to obtain a reconstructed data block, which is temporally delayed with respect to the input block.
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.
