All, (with thanks to Eric)
My code is working, and the results of the DFT and the FFT on the same data
return essentially the same results (small floating point differences in
the LSB not withstanding). My understanding of what these algorithms do is
*greatly* expanded and a number of things that I have heard, I now
understand more completely. The particularly interesting bit was one that
Mike calls out in one of his lectures, which is that these algorithms talk
about frequency but they don't really "know" anything about the signal
frequency. Rather, they correlate the sample data across the bins, as
related to bins. As a result, things like the 'nyquist frequency' which to
me had me thinking about what frequency I thought I was generating in my
sample data, has nothing to do with that. Instead it has to do with the
fact that the algorithm can only detect the frequency component when there
is change, and fastest "visible" change will be when it is occurring on
every other bin.
The other part that through me off was that bugs in my DFT code that had
gone un-recognized because I wasn't exactly sure what the DFT "should" look
like, initially threw me off since I didn't know which was correct, the DFT
plot or the FFT plot. And as Eric pointed out, the FFT output going from 0
.. +nyquist -nquist .. 0 is the correct output. And given *that* and going
back and figuring out what that was the case, it let me fix the bugs in my
DFT code which then produced the same output as my FFT code. And now that I
understand what it is doing, I can go back and clean up all the
misunderstandings and comments in the code which were associated with that
misunderstanding.
--Chuck
On Fri, May 12, 2017 at 4:30 PM, Chuck McManis <chuck.mcmanis@xxxxxxxxx>
wrote:
Hi Eric,
Thanks for the response. Fooling around if I "strech" the first 32 bins
(which is plot them so that the X axis is the same as the X axis for the
DFT plot, they essentially match (caveat resolution). So the peaks appear
under each other.
Which tells me (given your description) that the nyquist frequency
represented in my computed FFT is about 32x the frequency of the DFT plot.
And in answer to that question, yes I'm still working through understand
exactly how much spectrum the bins represent given the way I understand
unity roots.
(explanation here to communicate how I understand it, not to educate
anyone else)
I am writing my own FFT function (and I wrote my own DFT function). The
principle being that if I can code it then I can understand it, and if I
understand it, then I can code it. But if I don't actually understand it, I
can't code it :-). The same reason I would do the home work problems,
solving from first principles gets me a deeper understanding.
The FFT being 'cool' in that for a power of two, given the DFT of a signal
with one bin, is just the value of that bin, the FFT converts two 'single
bin' DFTs into a 2 bin DFT by computing multiplying the second bin by
e^(w/2), and adding that value to the first bin, and subtracting it from
the second bin. Then converting two 2 bin DFTs into a 4 bin DFT means
multiply bin 3 by e^(w/4), and setting bin 1 to that plus bin1 and bin3 get
gets bin1 minus that value. Then bin 2 computes bin4 times e^(2/w) and bin3
gets bin3 + that and bin 4 gets bin3 minus that. Leaving you with a 4 bin
DFT. Two 4 bin DFTs are combined into an 8 bin, then up the chain until I
convert two 256 bin DFTs into a single 512 bin DFT.
The bit reversal sort at the beginning, pre-orders the samples so that the
first two that are next to each other were originally bin/2 apart, The
first group of 4 are were bin/4 apart. etc. After converting all of the
DFTs from x1, x2, x4, .. xBin the values have essentially been unsorted
back to their original order.
So the revelation I came to here, is that to get the peaks to 'line up'
and the number I had to divide by, I realized I could "explain" it if the
FFT was plotting 0 - 8192hz rather than 0 to 512hz and 8192 is 16 times
larger than 512. And the "sample rate" that I picked, kind of out of thin
air, was 8192 hz.
To test my understanding of that, I generated my sample data with a
'sample rate' of 1024hz, and I computed the FFT on 1024 bins, but only
plotted the first half (the 'positive' frequencies). That gives me two
sharp peaks exactly under the two peaks I see from my DFT calculation. But
there aren't any side lobes like there are in the DFT calc.
I think I've made a small step forward in my understanding, will continue
on this road.
Thanks!
--Chuck
On Fri, May 12, 2017 at 3:56 PM, Eric Schneider <erictschneider@xxxxxxxxx>
wrote:
Chuck, to me the FFT looks correct and the DFT not so much. The FFT
looks like it starts at 0 Hz, goes to +nyquist, then -nyquist toward
zero, that is pretty typical of FFTs. If you want 0 to be in the center
you just take the right half and move it to the left side. "fftshift"
is a typical name of a function that would do that for you. (So I
concur with the other person)
Why are you bit-reversing? Did you write your own FFT? You are not
doing that for the DFT are you?
When you say you are using correlation for the DFT, do you mean summing
the product of the input sequence with a sinusoid at the bin frequency?
(aka the standard DFT definition)
Why 1024 samples and 512 DFT/FFT? Is it safe to assume that you are only
using the first 512 samples of the 1024 length array?
In your DFT are you ignoring negative frequencies? E.g. Not correlating
for negative frequencies, so only 256 outputs?
DFT or FFT, you can only get 256 positive frequencies from 512 samples.
Hopefully this helps somehow.
--Eric
On 05/12/2017 03:37 PM, Chuck McManis wrote:
Hi All,
Being inspired by Mike's videos and my current job is deep into SDRs I
have embarked on internalizing a crap ton of analog stuff I just
'memorized, regurgitated, and forgot' in college. Specifically the
analysis of signals using transforms. I'm writing this email in part
to "explain to someone else" what I'm trying to do in order to develop
insights in where I may be going wrong, and if you happen to know the
answer that is good too :-)
To that end I've been reading papers, and general descriptions, of the
theory and practice of fourier transforms. I subsequently wrote,
debugged, and re-wrote a discrete fourier transform routine that used
correlation to transform my (artificially) generated signal from the
time domain to the frequency domain.
My generated signal is stored in an array of 1024 samples with a
nominal 'sampling rate' of 8192 hz. And I fill the array with the
output of a cos function set for 300 hz and an amplitude of 1.0 (so
+/- 1.0 values into an array of floats).
When I run my DFT over 512 bins, and plot the magnitude of the 512
complex numbers that DFT produces, I get pretty much exactly what I
expected, a large peak centered around bin 300 falling off
exponentially to two much smaller peaks on either side, then two much
smaller peaks on either side of those down to a slightly wavy line
along 0. I've plotted the output on a nice display on a microprocessor
and took a picture of it here: https://goo.gl/photos/rcxFHCeQ18bdR7766
I then take the exact same data and apply my Fast Fourier Transform
code to it. And what I get is in that same picture (the lower half).
Two peaks, very far apart. Still 512 bins, same data. Clearly it is
"different" than the DFT result and I'm struggling to figure out why.
One person suggested "Oh that is the positive and negative versions of
the frequency." And yes when i do my bit reversal sort to take in my
signal I have the imaginary part set to zero (the signal (an array of
floats) gets translated into a an array of complex where the imaginary
component is zero. But even with that "explanation" Neither "half" of
that display looks like the DFT display.
I also tried doing 1024 bins and looking at the magnitude of the first
512 and last 512 bins, they both are very different.
It is really confusing the heck out of me.
--Chuck