discuss-gnuradio
[Top][All Lists]
Advanced
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Discuss-gnuradio] Frequency discriminator using a frequency to volt

From: Marcus Müller
Subject: Re: [Discuss-gnuradio] Frequency discriminator using a frequency to voltage converter
Date: Mon, 9 Nov 2015 13:48:08 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0
<math mode engaged>
Since it's a bit of a pain to make beautiful in the email itself, see the attached PDF. Here's the text of that:

Claim

The bin-wise average of $M$ DFTs of consecutive, non-overlapping input samples is the same as the DFT of the sample-wise averaged, consecutive, non-overlapping input vectors.

Proof

As mention in the claim, we average over $M$ DFTs. Let the length of the individual DFT be $N$.

Let us consider a complex input signal $x[n]$, with $n$ being the non-negative index, that exists for the whole observation, hence $n\in\{0,1,\ldots,MN\}$.

Lets use the same definition of the discrete Fourier transform as is used in FFTW[1], so that the first DFT $X_1$ would yield in bin $k$:

  $X_{1,k} = \sum_{n=0}^{N-1} {x_n e^{-j2\pi k \frac nN}}$.

Introducing the average DFT $Y$, we see that

$Y_k = \frac 1M \sum_{m=0}^{M-1}X_{m,k}$
  $= \frac 1M \sum_{m=0}^{M-1}\sum_{n=0}^{N-1} {x_{n+Nm} e^{-j2\pi k \frac nN}}$.
With the sums above being finite, we can change their order:
  $= \frac 1M \sum_{n=0}^{N-1}\sum_{m=0}^{M-1} {x_{n+Nm} e^{-j2\pi k \frac nN}}$
The exponential term doesn't depend on $m$, and hence can be extracted from the inner sum.
  $= \sum_{n=0}^{N-1}e^{-j2\pi k \frac nN}\frac 1M \sum_{m=0}^{M-1} {x_{n+Nm} }$
  $= \sum_{n=0}^{N-1}e^{-j2\pi k \frac nN} x_\text{avg}$

Notice that

$x_\text{avg}= \frac 1M \sum_{m=0}^{M-1} {x_{n+Nm} }$

is the sample average over $M$ consecutive, non-overlapping sample vectors of length $N$.

$\blacksquare$

SNR considerations


Let us consider the job of the DFT to find the coefficients that you'd have to write in front of the individual series representing an $N$ long complex oscillation with frequency $\frac 1N k$, i.e. the set of series

  $s_k = \left(e^{-j2\pi k \frac nN}\right)_{n=0,\ldots,N-1}$ .

All the $\frac1{\frac1Nk}=\frac Nk$-periodic oscillations are also $N$-periodic (by definition of periodicity).

Hence, in consecutive vectors of length $N$, if you add up the elements with the same index, and the observed signal is periodic, you simply get the averaging factor $M$ as the factor between the individual vector and the sum of $M$ vectors.

Now, remember that the purpose of averaging the DFTs was to enhance SNR by $M$. That's exactly what happens when you average the input signal, too.

[1]  FFTW, the Fastest Fourier Transform in the West, What FFTW Really Computes: The 1d Discrete Fourier Transform (DFT),
http://www.fftw.org/doc/The-1d-Discrete-Fourier-Transform-_0028DFT_0029.html#The-1d-Discrete-Fourier-Transform-_0028DFT_0029

On 09.11.2015 11:55, Daniele Nicolodi wrote:
On 06/11/15 19:01, madengr wrote:

Marcus Müller-3 wrote

Hi Lou,

that's a pretty good application of the spectrum, I agree. One could
certainly modify the freq_sink to do that, however, as it is now, the
PSD calculation (based on the fft result) is done in a single VOLK
kernel, 32fc_s32f_x2_power_spectral_density_32, which probably has some
performance advantages, so changing that would mean to either abandon
that benefit or introduce a new "processing path" inside the frequency
sink.

I'm a bit confused, though: The DFT is a linear operation. So averaging
k FFT vectors (linear operation) before or after the DFT wouldn't make a
difference, because

$\sum_{n=1}^k \mathrm{DFT}(x_n) = \mathrm{DFT}(\sum_{n=1}^k x_n)$, with
$x_n$ being our DFT length-sized input sample vectors.

You should be able to do $\sum_{n=1}^k x_n$ with a stream to vector->add
block combination in front of the normal frequency sink.

Hmm.. maybe it is.  I have done it in (shudder) LabView and it's nice since
noise reduces at 1/N instead of 1/sqrt(N); N is number of averages.  Maybe
I'll try it tonight with just discrete blocks to compare them side by side. 
Just something that can't be done with a normal spectrum analyzer.

Why does that hold true?

I don't think it is possible, at least in the general case.

Cheers,
Daniele


_______________________________________________
Discuss-gnuradio mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Attachment: linearity_of_DFT.pdf
Description: Adobe PDF document

reply via email to
[Prev in Thread] Current Thread [Next in Thread]