Patent ID: 7849123
Filing Date: 2010-12-07
Classification: G06F

Abstract:
1. A pipeline-based reconfigurable mixed-radix fast Fourier transform (FFT) processor, comprising: a first commutator that receives incoming data; a first multiplexer connected to the first commutator; a first general radix-8 butterfly performing an 8-point discrete Fourier transform (DFT) operation and connected to the first multiplexer; a multiplier connected to the first general butterfly; a memory unit connected to the multiplier; a first register bank connected to the multiplier and to the first multiplexer and storing and switching internal data and wherein the first multiplexer multiplexes the first commutator and the first register bank to the first general butterfly; a first Block Floating Point (BFP) unit connected to the first register bank wherein data is partitioned into non-overlapping blocks and wherein the blocks are normalized and a fixed-point computation is performed where execution of a given block is not started until execution of a supplying block is finished; a second register bank connected to the multiplier and storing and switching internal data; a third register bank connected to the multiplier and storing and switching internal data; a second BFP unit connected to the second register bank and to the third register bank wherein data is partitioned into non-overlapping blocks and wherein the blocks are normalized and a fixed-point computation is performed where execution of a given block is not started until execution of a supplying block is finished; a second multiplexer connected to and multiplexing the second register bank and the third register bank; a third multiplexer connected to and multiplexing the first commutator and the second multiplexer; a second general radix-8 butterfly performing an 8-point DFT operation and connected to the third multiplexer; a coefficient multiplier connected to the second general butterfly; a fourth register bank connected to the coefficient multiplier and storing and switching internal data; a fifth register bank connected to the coefficient multiplier and storing and switching internal data; a third BFP unit connected to the fourth register bank and to the fifth register bank wherein data is partitioned into non-overlapping blocks and wherein the blocks are normalized and a fixed-point computation is performed where execution of a given block is not started until execution of a supplying block is finished; a fourth multiplexer connected to and multiplexing the fourth register bank and the fifth register bank; a reconfigurable butterfly configurable as a radix-2, a radix-4, or a radix-8 butterfly and connected to the fourth multiplexer; and a second commutator connected to the reconfigurable butterfly and outputting an N-point mixed radix FFT of the incoming data wherein the processor decomposes the N-point FFT into four or fewer sub-FFTs having points, wherein a number of the points is a power of 2 and wherein N is the multiplication product of the number of the points and wherein parts having a higher radix are executed earlier than parts having a lower radix.