Circular fast fourier transform

US7685220B2 · kind B2 · utility

Assignee

• Telefonaktiebolaget LM Ericsson (Publ) · SE

Inventors

• Anders Berkeman · Lund, SE
• Leif Wilhelmsson · Lund, SE
• Jim Svensson · Lund, SE

Key dates

• Filing date: Dec 14, 2005
• Grant date: Mar 23, 2010
• Expiry date: Dec 24, 2028

Classification

• Technology area (CPC H): Electricity
• CPC primary: H04L27/2662
• WIPO field: Digital communication
• WIPO sector: Electrical engineering

Abstract

A Decimation In Frequency (DIF) Fast Fourier Transform (FFT) stage is used in an N bin FFT, wherein N is an even integer. The DIF FFT stage includes swap logic that receives a first input sample, x(v), and a second input sample, x(v+N/2), and selectively supplies either the first and second input samples at respective first and second swap logic output ports or alternatively the second and first input samples at the respective first and second swap logic output ports, wherein 0≦v<N/2. The DIF FFT stage further includes a summing unit for adding values supplied by the first and second swap logic output ports; a differencing unit for subtracting values supplied by the first and second swap logic output ports; and twiddle factor logic that multiplies a value supplied by the differencing unit by a twiddle factor, WN(v+s)mod(N/2), where s is an integer representing an amount of circular shift of N input samples.