Method and Apparatus of a Fully-Pipelined FFT

摘要

A plurality of three bit units (called triplets) are permuted by a shuffler to shuffle the positions of the triplets into different patterns which are used to specific the read/write operation of a memory. For example, the least significant triplet in a conventional counter can be placed in the most significant position of a permuted three triplet pattern. The count of this permuted counter triplet generates addresses that jump 64 positions each clock cycle. These permutations can then be used to generate read and write control information to read from/write to memory banks conducive for efficient Radix-8 Butterfly operation. In addition, one or more triplets can also determine if a barrel shifter or right circular shift is required to shift data from one data lane to a second data lane. The triplets allow efficient FFT operation in a pipelined structure.

主权项

1. An apparatus for a pipelined fast Fourier transform (FFT) comprising:
a first counter adapted to generate a first triplet and a second triplet; a plurality of memories each configured to be identified by a third triplet: a shuffler adapted to permute said first, second, and third triplets into a first sequence; a plurality of first data lanes providing symbols; a first barrel shifter configured to shift symbols between said plurality of first data lanes if at least one selected triplet of said first sequence changes state; said plurality of memories adapted to store one symbol from each of the first data lanes based on a first address formed by any two of said three triplets in said first sequence; a second counter adapted to generate a fourth triplet and a fifth triplet; said shuffler adapted to permute said fourth, fifth, and third triplets into a second sequence; each of said plurality of memories adapted to transfer stored symbols based on a second address formed by any two of said three triplets in said second sequence to a plurality of second data lanes; a second barrel shifter configured to shift stored symbols between second data lanes if at least one selected triplet of said second sequence changes state; and a first processing element (PE) of said pipelined FFT configured to receive stored symbols from said second data lanes.