Automatic generation of prime length FFT programs

摘要: Describes a set of programs for circular convolution and prime length fast Fourier transforms (FFTs) that are relatively short, possess great structure, share many computational procedures, cover large variety lengths. The make clear the structure algorithms clearly enumerate independent branches can be performed in parallel. Moreover, each these operations is made up sequence suboperations implemented as vector/parallel operations. This contrast with previously existing FFTs: They consist straight line code, no code shared between them, they cannot easily adapted implementations. authors have also developed program automatically generates FTTs. code-generating requires information only about modules computing cyclotomic convolutions.