Ron N. wrote:
The mixed radix algorithm is simply an algorithm for computing a DFT
using two smaller DFTs. For example an N point DFT from an M point and
K point DFT where M*K=N. Basically, the N input samples are entered into
an M row by K column matrix, filling in row-major order. Then M-point
transforms are computed down each of the K columns. The results are
phase rotated by a angle that depends on the position in the matrix, and
the results are put back into the matrix in natural order going down the
columns. A second pass then computes the K point transform along each
row, again returning the result into the matrix along the row in natural
order. Finally, the result is read out of the matrix reading down the
columns (column major order) to obtain the FFT result in natural order.
If M and K are relative primes, the phase rotation is not necessary,
which simplifies the computation (although the underlying DFTs are not
as efficient as power of 2 FFTs since at least one does not have a power
of two length).
Reply by Ron N.●September 29, 20072007-09-29
On Sep 28, 5:42 pm, Necronomicon <radio...@aol.com> wrote:
> So it seems the idea is to choose a bin frequency resolution
> that will be a sub-integer multiple of the main frequency of interest,
> like: Fo= 100Hz, then pick freq. resolution = 0.5 Hz.
>
> The problem situation might be, if you were sampling a signal
> that had
> two or more non-harmonically related frequencies, right?
If they are rationally related to each other and to the
sampling frequency, then one solution to the problem is
left as an exercise for the student.
> Can you give your angle on the "Mixed Radix"?
A term sometimes used to describe an FFT of a length
such that all its factors are not just 2 (possibly
also implying having at least two different factors
as well). Gives a lot more flexibility in choosing
the length of your FFT.
IMHO. YMMV.
Reply by Jerry Avins●September 28, 20072007-09-28
Necronomicon wrote:
...
> Can you give your angle on the "Mixed Radix"?
Mixed radius is an implementation detail that affects the efficiency,
not the result, of computation.
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by Necronomicon●September 28, 20072007-09-28
Ron N. wrote:
> On Sep 27, 4:24 pm, Necronomicon <radio...@aol.com> wrote:
> > Sorry if these are newbie questions, but can anyone give me
> > good descriptions of these?
> >
> > The bin splitting is obviously related to the samples per
> > second, the sampling time, and the frequency resolution. It
> > seems related to the number of samples that you fit into
> > the sampling period, but the concept is not totally clear to me.
>
> The term "resolution" may mean different things to different
> people in different contexts. Under some assumptions, one
> can get arbitrarily accurate resolution with only 3 samples.
> Other assumptions may require a lot more samples for a lot
> less resolution.
>
> If you take the DFT of some sufficiently bandlimited signal,
> any sinusoids which are exact integer multiples of Fs / N are
> orthogonal and will appear in exactly one complex DFT bin.
> Sinusoids of *any* other frequencies will appear in potentially
> *all* of the DFT bins, not just the closest bin (which appears
> to be some sort of common misconception), and in the shape of
> the transform of the window (a Sinc function for a rectangular
> window). Even if a good windowing function is used, a large
> portion of a sinusoid may appear in 3 or 4 bins; so even is
> this case, calling it a split between just 2 bins seems to
> be a bit of a misnomer.
>
Understood. Even a Hanning window with a long sampling
period would have sidebands.
> If, at the same sampling rate Fs, the number of samples N
> used in your DFT increases, there will be more potential exact
> frequencies which will be orthogonal to all other DFT bins, and
> the central lobe of the Sinc function will get skinnier, making
> it a bit easier to tell certain pairs of frequencies apart.
>
> If you expect certain frequency sinusoids and their harmonics
> to appear, and are sampling at some fixed rate, it may be
> possible to choose N (other than a power of 2) such that your
> frequencies of interest directly hit the orthogonal bins
> instead of getting spread out among all of them.
>
After reading this:
http://en.wikipedia.org/wiki/Window_function
.....it's all clearer. Although they seem to call the
increase in
the noise floor as "scalloping loss".
So it seems the idea is to choose a bin frequency resolution
that will be a sub-integer multiple of the main frequency of interest,
like: Fo= 100Hz, then pick freq. resolution = 0.5 Hz.
The problem situation might be, if you were sampling a signal
that had
two or more non-harmonically related frequencies, right?
Can you give your angle on the "Mixed Radix"?
Thanks.....
Reply by Ron N.●September 28, 20072007-09-28
On Sep 27, 4:24 pm, Necronomicon <radio...@aol.com> wrote:
> Sorry if these are newbie questions, but can anyone give me
> good descriptions of these?
>
> The bin splitting is obviously related to the samples per
> second, the sampling time, and the frequency resolution. It
> seems related to the number of samples that you fit into
> the sampling period, but the concept is not totally clear to me.
The term "resolution" may mean different things to different
people in different contexts. Under some assumptions, one
can get arbitrarily accurate resolution with only 3 samples.
Other assumptions may require a lot more samples for a lot
less resolution.
If you take the DFT of some sufficiently bandlimited signal,
any sinusoids which are exact integer multiples of Fs / N are
orthogonal and will appear in exactly one complex DFT bin.
Sinusoids of *any* other frequencies will appear in potentially
*all* of the DFT bins, not just the closest bin (which appears
to be some sort of common misconception), and in the shape of
the transform of the window (a Sinc function for a rectangular
window). Even if a good windowing function is used, a large
portion of a sinusoid may appear in 3 or 4 bins; so even is
this case, calling it a split between just 2 bins seems to
be a bit of a misnomer.
If, at the same sampling rate Fs, the number of samples N
used in your DFT increases, there will be more potential exact
frequencies which will be orthogonal to all other DFT bins, and
the central lobe of the Sinc function will get skinnier, making
it a bit easier to tell certain pairs of frequencies apart.
If you expect certain frequency sinusoids and their harmonics
to appear, and are sampling at some fixed rate, it may be
possible to choose N (other than a power of 2) such that your
frequencies of interest directly hit the orthogonal bins
instead of getting spread out among all of them.
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-m
Reply by Necronomicon●September 27, 20072007-09-27
Sorry if these are newbie questions, but can anyone give me
good descriptions of these?
The bin splitting is obviously related to the samples per
second, the sampling time, and the frequency resolution. It
seems related to the number of samples that you fit into
the sampling period, but the concept is not totally clear to me.
Thanks for any advice.