J4 ›› 2009, Vol. 36 ›› Issue (3): 541-546.

• Original Articles • Previous Articles     Next Articles

Effective algorithm of parallel twiddle factor generation for programmable FFT processing and its implementation

LIU Hong-xia;YANG Liang;HUANG Jin;HUANG Shi-tan   

  1. (Xi'an Microelectronics Technology Institute, Xi'an  710075, China)
  • Received:2008-06-30 Revised:2008-10-23 Online:2009-06-20 Published:2009-07-04
  • Contact: LIU Hong-xia E-mail:liuhongxia@mail.xjtu.edu.cn

Abstract:

In order to resolve the problem of high complexity and high area consumption in designing a twiddle factor address generator that generates three addresses in every clock cycle, this paper presents a new storage and access strategy of twiddle factors based on the Multi-bank memory structure. The strategy guarantees that the three twiddle factors needed by a butterfly computation of mixed-radix 4/2 FFT algorithm can be accessed simultaneously without conflict. This twiddle factor generating algorithm based on one lookup table for an arbitrary size FFT is dependent only on its maximum size that can be processed. At the same time, the transition from one stage to another can be implemented with a shift addend register. Therefore, this algorithm can be implemented with less complexity and area consumption than any other existing design. In addition, the number of accesses to one of those banks and its size are reduced by at least 50 percent.

Key words: fast Fourier transform(FFT), twiddle factors, mixed radix-4/2, address generating unit, FFT processor

CLC Number: 

  • TP303