Back to results
US 2008/0288569 A1Published application
Pipelined fft processor with memory address interleaving
AssigneeCygnus Communications Canada Co.
InventorsSean G. Gibb, Peter J.W. Graumann
Life of this patent
Estimating the term…
Abstract
An interleaver for use with transform processors provides an address generator allowing for implementation using a reduced memory foot print, and permitting interleaving of an input sequence while minimizing latency.
Claims25
A fast Fourier transform (FFT) processor for performing an FFT on a series of input samples organized as pairs, the processor comprising:
- a first butterfly unit for receiving the series of input samples, for performing a first butterfly operation on each received pair of the series of input samples to provide a serial output;
- an interleaver for receiving the serial output of the first butterfly unit, for permuting samples in the serial output to provide an output sequence organized as a pairwise series of samples, the interleaver comprising
- a plurality of memory elements, each element having a write storage address for storing a sample from the serial output, wherein the number of memory elements is less than the number of samples in the serial output, and
- an interleaver controller for receiving a sample from the serial output, determining the write storage address of one of the plurality of memory elements for storing the sample, writing the sample to the memory element associated with the determined write storage address, determining a read storage address associated with a memory element, and reading out the sample stored in the memory element associated with the determined read storage address to provide a sample of an output sequence, wherein the samples from the serial output are interleaved in accordance with a non-repeating pattern;
- and
- a second butterfly unit for serially receiving the output sequence from the interleaver, for performing a second butterfly operation on each pair of samples in the pairwise series of samples of the output sequence to obtain an output series of samples corresponding to an FFT of the series of input samples.
3 more elements
A single path delay fast Fourier transform (FFT) processor for performing an FFT on a series of input samples organized as pairs, the processor comprising:
- a plurality of butterfly modules connected in series each having a memory for receiving the series of input samples and an associated butterfly unit for performing butterfly operations on the series of input samples in the memory, the first butterfly module in the plurality for receiving and storing the series of input samples in memory, the final butterfly module in the plurality for providing a butterfly operation output as a series of samples corresponding to an FFT of the series of input samples;
- and
- at least one of the plurality of butterfly modules having an interleaving memory for receiving and storing a serial output resulting from performing a butterfly process on the series of input samples received by the at least one of the plurality of butterfly modules having an interleaving memory, and for permuting the series of samples in the serial output to obtain an output sequence organized as a pairwise series of samples, and for serially providing an associated butterfly unit with the output sequence, the interleaving memory comprising
- a plurality of memory elements, each element having a write storage address for storing a sample in the serial output, wherein the number of memory elements is less than the number of samples in the serial output, and
- an interleaver controller for receiving a sample from the serial output, determining the write storage address of one of the plurality of memory elements for storing the sample, writing the sample to the memory element associated with the determined write storage address, determining a read storage address associated with a memory element, and reading out the sample stored in the memory element associated with the determined read storage address to provide a sample of an output sequence, wherein the samples from the serial output are interleaved in accordance with a non-repeating pattern.
2 more elements
Dependencies are inferred from the claim text.