( Sign up ) Sign In
`
`V
`
`Open in app ,71
`
`e,, Q Search Medium
`
`•
`
`Published in Analytics Vidhya
`
`Shah Mahdi Hasan ( Follow)
`Apr 15, 2020 · 7 min read · 0 Listen
`
`W- Save W O
`
`Im
`
`<9
`
`Breaking down confusions over Fast Fourier
`Transform (FFT)
`
`Fourier Transform is undoubtedly one of the most valuable weapons you can have in
`your arsenal to attack a wide range of problems. FFT is literally the bread and butter
`for many signal processing engineers. At the same time, there are examples of
`application of FFT in data science realm. For example, time-series data with dense
`interval (for example: instead of monthly sales data, you might be dealing with hourly
`sales data) exhibits complex seasonality. Fourier Transform is a handy tool to analyze
`the seasonalities of those kinds. Unfortunately, in an inexperienced hand, it can lead to
`disastrous and frustrating conclusions sometimes.
`
`I was surfing through hundreds of discussions and Q&A in stack-exchange, Mathworks
`and other forums. What I have learned is: people who intend to use Fourier Transform
`do know why they want to use it. But the common confusion is: What's next? How to
`"post-process" the sequence in hand and get a meaningful and accurate insight? To be
`more specific, there are mainly following questions:
`
`1. What is Single Side Band (SSB)? Why do we care?
`
`2. What is the relationship between my FFT sequences and physical frequencies?
`How these two can be correctly aligned?
`3. What is FFT bins? How does it s'" ~ -~~- __ __ ?_ _ ~ ... of FFT?
`
`MZ Audio, Ex. 2010, Page 1 of 9
`
`
`
`V
`
`Open in app ,71
`
`e,, Q Search Medium
`
`•
`
`Published in Analytics Vidhya
`
`Shah Mahdi Hasan ( Follow)
`Apr 15, 2020 · 7 min read · 0 Listen
`
`W- Save W O
`
`Im
`
`<9
`
`Breaking down confusions over Fast Fourier
`Transform (FFT)
`
`Fourier Transform is undoubtedly one of the most valuable weapons you can have in
`your arsenal to attack a wide range of problems. FFT is literally the bread and butter
`for many signal processing engineers. At the same time, there are examples of
`application of FFT in data science realm. For example, time-series data with dense
`interval (for example: instead of monthly sales data, you might be dealing with hourly
`sales data) exhibits complex seasonality. Fourier Transform is a handy tool to analyze
`the seasonalities of those kinds. Unfortunately, in an inexperienced hand, it can lead to
`disastrous and frustrating conclusions sometimes.
`
`I was surfing through hundreds of discussions and Q&A in stack-exchange, Mathworks
`and other forums. What I have learned is: people who intend to use Fourier Transform
`do know why they want to use it. But the common confusion is: What's next? How to
`"post-process" the sequence in hand and get a meaningful and accurate insight? To be
`more specific, there are mainly following questions:
`
`1. What is Single Side Band (SSB)? Why do we care?
`
`2. What is the relationship between my FFT sequences and physical frequencies?
`How these two can be correctly aligned?
`3. What is FFT bins? How does it s'" ~ -~~- __ __ ?_ _ ~ ... of FFT?
`
`MZ Audio, Ex. 2010, Page 1 of 9
`
`
`
`4. Why there is a normalization factor?
`
`The source of confusions are buried beneath the mathematical fundamentals which
`built the foundation of Fourier Transform. In this article, I will try to breakdown
`several common confusions which arise while working with Fourier Transform. I will
`try to explain the reasoning using as little mathematics as possible. Hopefully this will
`help you to work with this amazing tool without going through the trouble of picking
`up the mathematics behind it.
`
`For explanation, I will be using an example code for Fast Fourier Transform (FFT). FFT
`is essentially a super fast algorithm that computes Discrete Fourier Transform (DFT).
`The example code is written in MATLAB (or OCTAVE) and it is a quite well known
`example to the people who are trying to understand Fourier Transform. Similar
`example can be found in here.
`
`MZ Audio, Ex. 2010, Page 2 of 9
`
`
`
`1
`2
`3
`4
`
`clear;
`clc;
`Fs = 1000;
`T
`1/ Fs;
`
`%sampling rate
`%sampling interval
`%Number of time points
`500;
`L
`5
`0 :T: (L - l )*T;
`t
`6
`%time vector
`%FFT points
`1024;
`7 N
`8 % Define frequencies
`9
`20 ;
`10
`220;
`
`fl
`
`f2
`
`11
`
`f3
`
`138;
`
`12 % Create the signal
`13
`x = 5 + 12*sin( 2*pi *fl *t -0.3 ) + 5*sin( 2*pi *f2*t -0.5 ) + 4*sin( 2*pi *f3 *t - 1.5 );
`14
`figure( l )
`15
`plot(t *1000,x)
`16
`xlabel('time (in ms)')
`17
`ylabel('Amplitude')
`18
`title('Original Signal')
`19 % Add some noise
`20
`figure( 2)
`21
`x = awgn(x, 5, 'measured')
`22
`plot(t *1000,x)
`23
`xlabel('time (in ms)')
`24
`ylabel('Amplitude')
`25
`title('Noisy Signal')
`26
`27 % FFT
`28 X = fft(x,N);
`29
`figure( 3)
`
`30
`31
`32
`
`plot(abs(X))
`SSB = X( l : N/ 2);
`SSB( 2:end ) = 2*SSB( 2 :end );
`
`f = (0 : N/ 2- l )*(Fs / N);
`33
`34 % Amplitude
`35
`figure( 4)
`
`36
`37
`
`38
`39
`
`plot(f,abs(SSB/ L))
`xlabel('f (in Hz)')
`
`ylabel('IX(f)I')
`title('Corrected Frequency Spectrum')
`
`fft_sample.m hosted with • by GitHub
`
`view raw
`
`MZ Audio, Ex. 2010, Page 3 of 9
`
`
`
`In what follows next, we will be taking parts from this code and analyze it. First, let us
`set up the context. We have a sampler which can sample 1000 samples in a second. We
`have gathered 500 time points using that sampler.
`
`Fs = 1000;
`T = 1/Fs;
`L = 500;
`t = 0:T:(L-l)*T;
`
`%sampling rate
`%sampling interval
`%Number of time points
`96time vector
`
`Next, let us create a signal with 3 frequencies and a DC component (component with 0
`Hz) which will be sampled. Let us add some noise as well. If you want, you can plot
`your signal for an initial visual inspection. That's a good practice.
`
`96 Define frequencies
`fl= 20;
`f2 = 220;
`f3 = 138;
`96 Create the signal
`x = 5 + 12*sin(2*pi*fl*t-0.3) + 5*sin(2*pi*f2*t-0.5) +
`4*sin(2*pi*f3*t - 1.5);
`x = awgn(x,5, 'measured') 96noise with 5 dB Signal to Noise ratio
`
`Now, we are all set for performing FFT. We have a real world signal in our hand which
`is a mixture of sinusoids corrupted by additive noise. Let us take the FFT and plot it.
`Bummer. Oh yes, FFT sequences are complex sequences. Why? Because they contain
`information about amplitude and phase for a given frequency component and complex
`numbers are the best way to describe it. Let us take the absolute value (magnitude) of
`those sequences then. What do we get?
`
`MZ Audio, Ex. 2010, Page 4 of 9
`
`
`
`2500
`
`2000
`
`1500
`
`1000
`
`500
`
`0
`
`100
`
`200
`
`300
`
`400
`
`The magnitude of the FFT sequences FFT(x)
`
`This do not make much sense at all. First of all, there are 7 peaks (including the one at
`zero). But we were expecting 4 peaks, (3 for frequencies fl,f2,f3 and 1 for the DC
`component). Secondly, what has happened to the amplitude? It looks too high! The
`peaks are in wrong place as well. It is pretty evident that to work with this thing, we
`have works to do.
`
`Let us break the first confusion: why there are more peaks than we were expecting?
`This is where Single Side Band (SSB) spectrum comes to play. If you look closely, one
`side of the plot above is the mirror reflection of another side, dropping the peak at 0.
`This is because, for real signals, the coefficients of positive and negative frequencies
`become complex conjugates. That means, we do not need both sides of spectrum to
`represent the signal, a single side will do. This is known as Single Side Band (SSB)
`spectrum. To get the SSB spectrum, we need to our time domain signal into the
`analytic signal which is Xa = x + iH(x). H(x) is the well known Hilbert Transform. But,
`the good news is- we do not need to learn a new transform for that. It turns out, if you
`take the spectrum associated with positive frequencies only and multiply it by 2, you
`will get the SSB spectrum without explicitly applying Hilbert Transform on converted
`
`MZ Audio, Ex. 2010, Page 5 of 9
`
`
`
`analytic signal. This can be done simply writing the two lines of additional code as
`shown in the following snippet:
`
`X = fft(x,N);
`SSB = X(l:L/2);
`SSB(2:end) = 2*SSB(2:end);
`
`Note that, we excluded the first element while multiplying by 2. This is because, in
`MATLAB, the FFT function returns a vector where the first element is the DC
`component (associated with O frequency). A DC component is associated with 0
`frequency, which is neither positive nor negative. In reality, this coefficient is real.
`
`Next, we need to fix an appropriate x-axis for the FFT spectrum. In our case, we need
`to put the physical frequencies in the x-axis so that we know we are getting peaks at the
`correct frequencies. This is an extremely crucial step. To do that, we need to
`understand how FFT creates "bins". For N point FFT, the number of bins created is N/2.
`
`FFT is just an implementation of Discrete Fourier Transform (DFT). To discretize the
`continuum of frequencies, the frequency axis is evenly segmented into finite number
`of parts which are known an bins. Bins can be considered as spectrum samples. In our
`example, the sampling frequency Fs = 1000 samples/second. According to Nyquist law,
`the highest physical frequency which can be represented by its samples without
`aliasing is simply Fs/2 = 500 Hz. So, essentially the frequency spectrum is being
`segmented into strips of (Fs/2)/(N/2) or Fs/Nbins. This is big. We can now create
`appropriate frequency axis as shown in the snippet below.
`
`f = (0:N/2-l)*(Fs/N);
`
`Moreover, bins give us the idea about the underlying frequency resolution of FFT. In a
`simpler word- to which extent we will be able to separate two closely placed
`frequencies in the spectrum. In our example, our frequency resolution is Fs/N =
`1000/1024 or 0.9765 Hz/bin. We won't be able to separate frequencies as distinct peaks
`if they have a spearation less than 0.9765 Hz.
`
`MZ Audio, Ex. 2010, Page 6 of 9
`
`
`
`We are almost there. We have extracted the Single Side Band spectrum. We also have
`established the axis of the spectrum. Now, we want to simply look at the spectrum and
`spell out the amplitudes of each sinusoids. Before doing that, let me rephrase DFT a
`little bit. Remeber the definition of DFT?
`
`N-1
`
`X (k) = L x(n)e-i2rrkn/ N
`
`n= O
`
`DFT can be seen as a correlation
`
`If you look closely, you will notice that, computing DFT ressembles correlation a lot.
`That's right. In fact, I think this is a great intuitive way of thinking about how DFT
`works. So, essentially for each bin, we compute the cross-correlation between our time
`domain signal x and a complex sinusoid associated with that bin. A further
`investigation reveals that, something is indeed missing which we usually see along
`with a correlation operation. A normalization factor. To be specific, a normalization
`factor of signal length. That's what we will do, we will normalize the spectrum with
`signal length. Now, let us put all of these understandings together and let us see what
`happens.
`
`figure(4)
`plot(f,abs(SSB/L)) %Normalizing with signal length
`xlabel('f (in Hz)')
`ylabel(' IX(f) I')
`title('Corrected Frequency Spectrum')
`
`MZ Audio, Ex. 2010, Page 7 of 9
`
`
`
`Corrected Frequency Spectrum
`12 ..------------r----~------r-----r----r--------.-------r------.---------,
`X: 19.53
`Y: 10.52
`■
`
`10
`
`8
`
`£ 6
`
`X
`
`I X: 0
`Y: 5.15
`
`4
`
`2
`
`X: 21 g_7
`Y: 5.135
`
`■
`
`+-
`
`X: 13 7.7
`Y: 3.914
`■
`
`o ~~~~~~--~-~--~--~~~-~~--~-~
`50
`150
`200
`250
`300
`350
`450
`500
`400
`0
`100
`f (in Hz)
`
`Voila! We have successfully retrieved our frequencies from deep beneath the noise. I
`suggest you to play with the code attached and see what happens at different signal
`length, FFT points and frequencies. I would like to remind you that, for given settings
`in the code, aliasing will happen if you chose a frequency above Fs/2. Frequencies
`higher than Fs/2 will appear as a low frequency component in the spectrum because of
`aliasing. That is why, a low-pass filtering is suggested before applying FFT, especially if
`you do not have any knowledge about the potential frequency components of your
`signal.
`
`I hope this story will equip you with some basic understanding about handling FFT
`operations. For the ease of explanation, many of mathematical perspectives are
`oversimplified since I am trying to cater a broad class of readers. See you next time!
`
`Digital Signal Processing
`
`Data Science
`
`Mathematics
`
`Fourier Transform
`
`Linear Algebra
`
`MZ Audio, Ex. 2010, Page 8 of 9
`
`
`
`Sign up for Analytics Vidhya News Bytes
`By Analytics Vidhya
`
`Latest news from Analytics Vidhya on our Hackathons and some of our best articles! Take a look.
`
`Your email
`
`S Get this newsletter
`
`By signing up, you will create a Medium account if you don't already have one. Review our PrivacY. PolicY. for more information about our privacy
`practices .
`
`..=..1.::>c:>..__.L
`
`t----ile,, ■~
`
`1 e,, ■ m,g.
`
`..-. •...,,.a,_c:,Y'
`
`- - - - - - - -
`
`11111.... GETITON
`,..... Google Play
`
`MZ Audio, Ex. 2010, Page 9 of 9
`
`
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
