Fully parallel fast fourier transformer

Patent metadata

Field	Value
Publication number	US-9735996-B2
Application number	US-201615348771-A
Country	US
Kind code	B2
Filing date	Nov 10, 2016
Priority date	Nov 25, 2015
Publication date	Aug 15, 2017
Grant date	Aug 15, 2017

Abstract

Provided is a fully parallel fast Fourier transformer of N-point, where N is a natural number, including a bit-reversal arranging block configured to rearrange an order of N input complex number samples, a plurality of first processors configured to perform, in a plurality of group units, a 16-point FFT on the rearranged complex number samples, a twiddle factor multiplier configured to multiply outputs of the plurality of first processors by twiddle factors, a first group rearranging block configured to rearrange outputs of the twiddle factor multiplier in the plurality of group units, a plurality of second processors configured to perform, in the plurality of group units, 16-point FFT on the complex number samples grouped by the first group rearranging block, and a second group rearranging block configured to rearrange outputs of the plurality of second processors to output under a same arrangement criterion as the first group rearranging block.

First claim

What is claimed is:

1. A fully parallel fast Fourier transformer of N-point, where N is a natural number, the fully parallel fast Fourier transformer comprising:
a bit-reversal arranging block configured to rearrange, according to a bit-reversal permutation, an order of N input complex number samples;
a plurality of first processors configured to perform, in a plurality of group units, a 16-point fast Fourier transform (FFT) on the rearranged complex number samples;
a twiddle factor multiplier configured to multiply outputs of the plurality of first processors by respective twiddle factors to produce corresponding twiddled outputs of the plurality of first processors;
a first group rearranging block configured to rearrange the twiddled outputs of the twiddle factor multiplier in the plurality of group units, so that for each twiddled output corresponding to an i th output of a j th first processor, the twiddled output is grouped into a j th element of an i th group unit of an output of the first group rearranging block;
a plurality of second processors configured to perform, in the plurality of group units, 16-point FFT on the complex number samples grouped by the first group rearranging block; and
a second group rearranging block configured to rearrange outputs of the plurality of second processors so that for each output of the plurality of second processors, a k th output of an m th second processor corresponds to an m th output of a k th group unit of the output of the second group rearranging block,
wherein the m th output of a k th group unit of the second group rearranging block corresponds to an output DOUT[n] of the fully parallel fast Fourier transformer, n=(m−1)+16(k−1).

2. The fully parallel fast Fourier transformer of claim 1 , wherein the bit-reversal arranging block allocates an order of the N input complex number samples but rearranges the order in a manner that a bit position of a binary value of the order is switched.

3. The fully parallel fast Fourier transformer of claim 1 , wherein the plurality of first processors and the plurality of second processors comprise radix-16 processors configured to perform an FFT operation on the input complex number samples in the plurality of group units.

4. The fully parallel fast Fourier transformer of claim 3 , wherein the plurality of first processors and the plurality of second processors respectively 16 radix-16 processors.

5. The fully parallel fast Fourier transformer of claim 1 , wherein radix-16 processors included in the plurality of first processors or the plurality of second processors use twiddle factors of W( 1 ), W( 2 ), W( 3 ), W( 4 ), W( 6 ), and W( 9 ) among 16 twiddle factors in complex number multiplication.

6. The fully parallel fast Fourier transformer of claim 5 , wherein the radix-16 processor comprises 9 complex number multipliers configured to perform complex multiplication operations on the twiddle factors of W( 1 ), W( 2 ), W( 3 ), W( 4 ), W( 6 ), and W( 9 ) and the complex number multiplier for the twiddle factor of W( 4 ) is realized through a sign inversion operation.

7. The fully parallel fast Fourier transformer of claim 5 , wherein for a multiplication operation for each of the twiddle factors of W( 1 ), W( 3 ), and W( 9 ), 3 adders and 3 constant multipliers are used.

8. The fully parallel fast Fourier transformer of claim 5 , wherein for a multiplication operation for each of the twiddle factors of W( 2 ) and W( 6 ), 2 adders and 2 constant multipliers are used.

9. The fully parallel fast Fourier transformer of claim 5 , wherein the radix-16 processor comprises 20 constant multipliers configured to perform complex number multiplication of the twiddle factors.

10. The fully parallel fast Fourier transformer of claim 9 , wherein the constant multiplier comprises a canonical signed digit (CSD) multiplier realized with shifters and adders.

11. The fully parallel fast Fourier transformer of claim 1 , wherein at least one of the bit-reversal arranging block, the first group rearranging block, or the second group rearranging block is formed in an interconnection manner without a memory.

12. The fully parallel fast Fourier transformer of claim 1 , wherein the point number N corresponds to any one length of 32 , 64, 128, 256, 512, 1024, and 2048.

Assignees

• Electronics & Telecommunications Res Inst

Inventors

• Kim Jin Kyu

Classifications

• G06F17/142 Primary

  Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm · CPC title

• G06F9/3001

  Arithmetic instructions · CPC title

• G06F17/141

  Discrete Fourier transforms · CPC title

• H04L27/265 Primary

  Fourier transform demodulators, e.g. fast Fourier transform [FFT] or discrete Fourier transform [DFT] demodulators (H04L27/26524 takes precedence) · CPC title