Fft Using Bruun's Algorithm

FFT using Bruun's Algorithm over Cooley-Turkey Algorithm

J.Elangkumaran

Electrical Engineering, Indian Institiute of Technology, Madras

elangkumaranj@gmail.com

Abstract—In this paper, we address discuss how to do the create the Fast Fourier Transform (FFT) using Bruun's algorithm, as opposed to the common  Cooley–Tukey algorithm. Even though it was developed for powers of 2, it can be extended to other radices as well

Index Terms— FFT, Bruun, polynomial factorisation approach

INTRODUCTION

T

HE most used tool in communications and analysis of signals is the Fourier transform. The Discrete Fourier Transform (DFT) finds a lot of applications. However, directly computing the DFT generally proves costly in terms of computing power and so Fast Fourier Transforms (FFTs) are used, including and especially for large data sets.

The most widely-used algorithm for FFTs is the  Cooley–Tukey algorithm, which uses a divide and conquer approach to recursively compute the DFT. An alternate method was proposed by G. Bruun in the year 1978. It recursively does polynomial factorisation and was initially intended for powers of 2.

DFT Equations

The DFT a discrete time signal[pic 1] is defined as in (I) and the inverse defined as in (ii). Now if we consider as[pic 2] as a  polynomial in z (as per iii) and the root unity defined as in (iv), then the DFT may be expressed as in (v) where polymod denotes the polynomial reminder function

[pic 3]        (i)

[pic 4]        (ii)

[pic 5]        (iii)

[pic 6]        (iv)

[pic 7]        (v)

        We need to compute the remainder effectively to compute

the FFT in a fast manner.

POLYNOMIAL FACTORISATION

Multiplication of all the monomials from[pic 8] which are of the form  ([pic 9]) results in the polynomial[pic 10] .

ALGORITHM

The entire problem of finding the FFT boils down to the efficiently computing the polymod() function in (v).

The Bruun algorithm factorizes[pic 11] using the following two methods:

[pic 12]        (vi)