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