Solved

# what are butterfly's in DSP

Posted on 2004-08-18
1,729 Views

Ive noticed in many DCT and FFT 'C' source codes there are references to
something called butterfly, can someone explain what this is.
Im a self taught programmer, so dont understand math jargon too well,
so if you could explain it's purpose in english that would be great.

thankyou
0
Question by:apakian

LVL 84

Expert Comment

ID: 11836444
0

LVL 84

Expert Comment

ID: 11836448
0

Author Comment

ID: 11836541

In english, assume Im a really dummy please :-)
some pseudo code would help.
0

LVL 18

Expert Comment

ID: 11841658
A butterfly is a simple operation on a complex number.
Part of the process of an FFT is having an network of these butterflies to achieve it's algorithmic aims.
You may notice that the end product of the network of butterflies there is bit reversal, a phenomina of the FFT.
Don't worry if you don't understand it very easily. The FFT is one of mankinds greatest algorithmic achievements and requires a reasonable background in mathematics to understand it. It's just not easy.
0

Author Comment

ID: 11842104

I understand fft,dct and signal processing, as far as how to code them,
but the math jargon i dont understand, so if you can explain butterflies
in the form of C code for something other than DSP, that would
do the trick...
0

LVL 7

Expert Comment

ID: 11849553
apakian, Unless you are hot stuff on the old maths stuff you are not going to understand the subtleties of the FFT and DCT. You do not need complex numbers for the DCT and they really are not required for the FFT but it is a nightmare without them.
0

LVL 27

Accepted Solution

d-glitch earned 100 total points
ID: 11852283
Here is a C language implementation of the Cooley-Tookey FFT algorithm with the butterflies calculations.

http://www.science.uva.nl/pub/computer-systems/ias/groen/aim/aim/fft1.c

Butterflies are just a way of scrambling the inputs in an organized way.
0

## Featured Post

### Suggested Solutions

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …
This tutorial demonstrates a quick way of adding group price to multiple Magento products.