Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I understand that $$X(k) = \sum_{n=0}^{N-1}x_ne^{-i2\pi \frac{k}{N} n}$$ and $$x(n) = \frac{1}{N}\sum_{k=0}^{N-1}X_k e^{i2\pi \frac{k}{N} n}$$ are the discrete Fourier transform and inverse discrete Fourier transform. How do I translate/interpret/apply these formulas in terms of sampling period and frequency. For example, if I sample $11$ times so that $N=11$, and 1.5 seconds is the sampling period. Then from what little I understand, I should be able to write something that resembles sort of like, (ignoring the sine terms), $$y(t)=A_1\cos(2\pi ft) + A_2\cos(2\pi(2f)t)+\ldots$$ where $y(0),y(1.5),y(2*1.5),\ldots, y(10*1.5)$ take on the values of those $11$ sampled values and $t$ is time in seconds, $f$ is some lowest frequency needed in the representation.

Now somehow using the inverse discrete Fourier transform $x(n)$ I'm suppose to be able to get at $y(n)$. However, everything in $X(k)$ and $x(n)$ is based around integers (i.e. $n$ and $k$ are integers). Whereas $y(t)$ deals with values like $t=1.5$ and $f$ that are not integers. Can someone show the baby steps to get from $x(n)$ to $y(t)$.

share|improve this question
1  
In sampling you should take at least two samples from the lowest period of the signal. In other words you shoud sample two times faster than the highest frequency of the signal, $f_s>2f$ to perfectly recunstruct the original continuos time signal. In order to obtain the continuos time signal, you do interpolation. This means your continuos time signal doest have any discrete value. The idea behind the Nyquist sampling is that, if your signal is band limited by say $B$, then interpolation process can not make errors higer than this frequency and your signal will be perfectly recunstructed. –  Seyhmus Güngören Jul 28 '12 at 10:52

1 Answer 1

up vote 1 down vote accepted

The discrete Fourier transform and its inverse do not include any specifications of the continuous-time signal (and its Fourier transform) from which the sample values are obtained. The vector $(x(0), x(1), \ldots, x(N-1))$ can represent sample values spaced $T$ seconds apart for your choice of $T$ and thus the $y(t)$ that you seek cannot be determined until you specify $T$. In your example, you chose $N=11$, $T = 1.5$ seconds and so you know the values of $y(t)$ for $t = 0, 1.5, 3.0, \ldots, 15.0$.

Your signal $y(t)$ is unknown except for its values at $11$ points on the time axis: $y(1.5n) = x(n), 0 \leq n < 11$. Anything more that could be said about $y(t)$ depends on what assumptions you are willing to make. One common assumption is that (for the case when $N$ is odd)

$y(t)$ can be represented on the interval $[0, NT] = [0,16.5]$ by the finite Fourier series $$y(t) = \sum_{k=-(N-1)/2}^{(N-1)/2} Y_k \exp(i 2\pi f_0 kt) $$ where $f_0 = 1/NT$ Hz.

Note that this means that $y(t)$ has no frequencies higher than $((N-1)/2)f_0 < Nf_0/2 = (2T)^{-1}$, that is, half the sampling rate $T^{-1}$. Now, the Fourier coefficients cannot be computed in the usual manner as $Y_k = \frac{1}{16.5}\int_{0}^{16.5}y(t)\exp(-i2\pi kf_0 t) \,\mathrm dt$ because $y(t)$ is not known except at the sample points. But, when $N = 11$, $$\begin{align*} y(nT) &= \sum_{k=-5}^{5} Y_k \exp(i2\pi kf_0 nT) = \sum_{k=-5}^{5} Y_k \exp(i 2\pi kn/11)\\ &= \sum_{k=0}^{5} Y_k \exp(i 2\pi kn/11) + \sum_{k=6}^{10} Y_{k-11} \exp(i 2\pi kn/11)\\ \text{But,}\qquad \qquad y(nT) &= x(n)\\ &= \frac{1}{N} \sum_{k=0}^{11} X_k \exp(i 2\pi kn/11) \end{align*}$$ and so we have that $Y_k = \begin{cases}\frac{1}{N}X_k, & 0 \leq k \leq 5,\\ \frac{1}{N} X_{k+11}, & -5 \leq k < 0.\end{cases}$

So the Fourier coefficients can be determined from the known values of the discrete Fourier transform. Note that I have discussed the case when $N$ is odd. When $N$ is even, a slightly different calculation is used to account for the relationship between $Y_{\pm N/2}$ and $X_{N/2}$.

share|improve this answer
    
So how can I see that with reasonable assumptions that $f_0$ is unique. That the representation fundamentally has this lowest frequency that is unique. –  user782220 Jul 28 '12 at 22:08
    
$f_0 = (NT)^{-1}$ is uniquely determined by the number of samples $N$ and their spacing $T$ because we made the assumption that $y(t)$ is periodic with period $NT$. But there is no way of telling whether the actual signal $y(t), -\infty < t < \infty$ (from which these $N$ samples were drawn) is a periodic signal, and if so, what the period is. Nor is there is no way of knowing whether the actual fundamental frequency has any relationship to $f_0$ as defined above. All we have found is one of the many signals that have the same $N$ sample values. –  Dilip Sarwate Jul 29 '12 at 2:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.