Fast Fourier Transform in my opinion is one of the most important algorithms in computing. It is because I personally like this algorithm that I've decided to discuss it. The basis behind fourier transform is in mathematics. Fourier transform is the discovery that a signal in one form can be turned into another form without losing any information. A signal in the time and space domain can be transformed into a signal in the frequency domain. This concept is powerful in a similar way to the ability to use a directed graph to visualize a social network. For clarity the time domain, minutes, seconds, mili-seconds, and so on.
The Utility of Fourier Transform
Fourier transform's power becomes apparently when you understand the nature of the electromagnetic spectrum. Information traverses the electromagnetic spectrum as "waves". Fourier transform allows for analysis of this spectrum to be possible. Spectral analysis is made possible and all it's applications by way of Fourier transform.
Signal processing is also a very common element in computer programing. We use signal processing for example to do image processing. We also use signal processing when we are dealing with audio processing. People who like music, who like games, will understand the value of digital signal processors.
Programing and FFT
Fast Fourier Transform is an efficiency enhancement for the process of Fourier transform.
Below is the code to show you how simple it is to apply FFT in practice
from numpy.fft import fft
from numpy import array
a = array([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])
print( ' '.join("%5.3f" % abs(f) for f in fft(a)) )
4.000 2.613 0.000 1.082 0.000 1.082 0.000 2.613
Now let's discuss the code. If you don't know Python, the "from" command is how you select a module. So "from numpy.fft import fft"
This imports the FFT module from numpy. What is numpy? Numpy is a package which you can leverage in your programming to do scientific computing. FFT is imported by the import command in Python so that Fast Fourier Transform can be used in your app.
The next step is to import an array. From the Numpy manual:
NumPy’s main object is the homogeneous multidimensional array. It is a table of elements (usually numbers), all of the same type, indexed by a tuple of positive integers. In NumPy dimensions are called axes.
We can also see from the manual how to compute different types of FFT using Numpy:
fft(a[, n, axis, norm]) Compute the one-dimensional discrete Fourier Transform.
ifft(a[, n, axis, norm]) Compute the one-dimensional inverse discrete Fourier Transform.
fft2(a[, s, axes, norm]) Compute the 2-dimensional discrete Fourier Transform
ifft2(a[, s, axes, norm]) Compute the 2-dimensional inverse discrete Fourier Transform.
fftn(a[, s, axes, norm]) Compute the N-dimensional discrete Fourier Transform.
ifftn(a[, s, axes, norm]) Compute the N-dimensional inverse discrete Fourier Transform.
https://docs.scipy.org/doc/numpy/reference/routines.fft.html#standard-ffts
As you can see it is trivially easy to write this code. I chose Python because it's the easiest language to explain for a newbie programmer. Fourier transform is immensely useful. In fact, the concept of heart rate variability which is used with heart rate monitors is calculated by Fast Fourier Transform. The pattern of beats is translated into the frequency domain. It is also possible to use FFT in combination with neural networks (NN) to diagnose by EKG heart related problems. This shows the versatility and life saving potential of FFT.
References
Clifford, G. D. (2002). Signal processing methods for heart rate variability (Doctoral dissertation, University of Oxford).
Gothwal, H., Kedawat, S., & Kumar, R. (2011). Cardiac arrhythmias detection in an ECG beat signal using fast fourier transform and artificial neural network. Journal of Biomedical Science and Engineering, 4(04), 289.
You are not reading my mind, I hope? ;)
Because I came across FFT mself yesterday, but with another use case.
Thanks for introducing this one to us.
FFT has many many use cases. One of the most important algorithms I've come across. No I'm not a psychic but maybe my life would be much easier if I had such powers.
You can wrap your code in "```" for readability:
import numpy as np a = np.array([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]) print( ' '.join("%5.3f" % abs(f) for f in np.fft.fft(a)) )I read it several times ... but maybe because I'm not a programmer, I see it as if it were the Nasa, hahaha. It looks interesting.
Have a nice day!
Take it slowly. First learn the basics of programming, then learn a bit about Numpy, then learn the math behind FFT, then learn how to implement FFT using Numpy.
I want to be a web designer and i guess i will come across the web design of a stuff later in the future
Congratulations @dana-edwards! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :
Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word
STOPOH YES!
FFTs... without it radio astronomy and Large Base Interferometry wouldn't exist at all.
Cheers, and very nice post :) Was delighted to see some old Fourier!