1
$\begingroup$

Let $y:\left(-\frac T2,\frac T2\right)\to\mathbb{C}$ be a square integrable function. The Fourier coefficients of $y$ are $$\underline{Y}(k):=\frac 1T\int_{-T/2}^{T/2}y(t)e^{-i\omega_kt}\;dt\;\;\;\text{with }\omega_k:=k\frac{2\pi}T$$ for $k\in\mathbb{Z}$. The Fourier polynom of degree $n\in\mathbb{N}$ of $y$ is $$\mathcal{F}^{-1}_n[y](t):=\sum_{k=-n}^n\underline{Y}(k)e^{i\omega_kt}$$ and $$\mathcal{F}^{-1}[y]:=\lim_{n\to\infty}\mathcal{F}_n^{-1}[x]$$ is called inverse Fourier transformation of $y$. Now, I've got two questions:

  1. What is meant by sampling (in terms of the sampling theorem)? From my understanding, if we know the period $T$ all we need to "store" are the values $\underline{Y}(k)$. We cannot store all values, so we need to choose a "huge enough" $n$ and store only the values $\underline{Y}(-n),\cdots,\underline{Y}(n)$. So, where does "sampling" come into play? The only thing I could imagine is numerical integration: We consider an equidistant grid $$x_j=\left(\frac jN-1\right)\frac T2\;\;\;\text{for }j=0,\ldots,2N$$ and apprximate $\underline{Y}(k)$ using the composite trapezoidal rule, i.e. $$\underline{Y}(k)\approx\frac{1}{2N}\sum_{j=0}^{2N-1}y\left(x_j\right)e^{-i\omega_kx_j}$$ By doing so, we didn't take the whole "signal" $y$, but only the "sample points"$\left(x_j,y\left(x_j\right)\right)$ into account. Is this meant by "sampling"?
  2. Does the sampling theorem make a statement about $n$ or $N$ or something else?
$\endgroup$
  • $\begingroup$ badf00d, i am working on this with a slightly different notational convention. like my $N$ will be the same as your $2N$. and i am not using "$x$" to depict "time", like $t$. note that my "$T_\text{s}$" is the same as your $\frac{T}{2N}$ or my $\frac{T}{N}$. and i am not dealing with any "composite trapezoidal rule". integrating in the continuous-time domain ($\int x(t) \ dt$) will be equivalent to summing in the discrete-time domain ($\sum x[n]$) due to the nature of the mathematics in this bandlimited and sampled situation. $\endgroup$ – robert bristow-johnson Feb 15 '15 at 21:36
5
$\begingroup$

I think, with respect to sampled function, that i disagree a bit with MBaz. perhaps i misunderstand what he/she says regarding needing an infinite number of coefficients or samples for this special case of sampled periodic functions. we had a little discussion about this at comp.dsp, and i'm gonna make use of $\LaTeX$ to spell out the same points.

of course, whether $x(t)$ is periodic or not, if $x(t)$ is real and is sufficiently bandlimited (there are no frequency components as high or higher than $\frac{f_\text{s}}{2} = \frac{1}{2T_\text{s}}$), then the samples:

$$ x[n] \triangleq x(n T_\text{s}) $$

are sufficient to completely represent the continuous-time $x(t)$. if $x(t)$ never repeats, than an infinite number of discrete $x[n]$ are necessary to represent $x(t)$ for all $t$.

but if $x(t)$ is periodic,

$$ x[n+N]=x[n] \quad\quad \forall n,N \in \mathbb{Z} $$ and $$ x(t+T)=x(t) \quad\quad \forall t $$

then samples existing over the span of one period are sufficient to represent $x[n]$ and $x(t)$. in order for the $x[n]$ to be periodic in the sampled domain:

$$ \begin{align} x[n+N] & = x\left((n+N)T_\text{s} \right) \\ & = x\left(nT_\text{s}+NT_\text{s} \right) \\ & = x\left(nT_\text{s}+T \right) \\ \end{align} $$ because $ x(t+T) = x(t) $.

which means the obvious, your function period $T$ has to be the same as $N$ times your sampling period $T_\text{s}$.

$$ T = N T_\text{s} $$

now, what we know about this sampled periodic function is that $N$ samples of $x[n]$ are sufficient to tell us all about $x[n]$, and since $x(t)$ is bandlimited, $x[n]$ and the $N$ samples that fully define it, are sufficient to fully describe $x(t)$.

if $x(t)$ is sufficiently bandlimited (as above), then

$$ \begin{align} x(t) & = \sum\limits_{n=\infty}^{+\infty} x[n] \operatorname{sinc}\left(\frac{t-nT_\text{s}}{T_\text{s}}\right) \\ & = \sum\limits_{n=\infty}^{+\infty} x[n] \frac{\sin\left(\pi\frac{t-nT_\text{s}}{T_\text{s}}\right)}{\pi\frac{t-nT_\text{s}}{T_\text{s}}} \\ & = \sum\limits_{m=\infty}^{+\infty} \sum\limits_{n=0}^{N-1} x[n+mN] \frac{\sin\left(\pi\frac{t-(n+mN)T_\text{s}}{T_\text{s}}\right)}{\pi\frac{t-(n+mN)T_\text{s}}{T_\text{s}}} \\ & = \sum\limits_{n=0}^{N-1} \sum\limits_{m=\infty}^{+\infty} x[n] \frac{(-1)^{mN}\sin\left(\pi\frac{t-nT_\text{s}}{T_\text{s}}\right)}{\pi\frac{t-(n+mN)T_\text{s}}{T_\text{s}}} \\ & = \sum\limits_{n=0}^{N-1} x[n] \sin\left(\pi\frac{t-nT_\text{s}}{T_\text{s}}\right) \sum\limits_{m=\infty}^{+\infty} \frac{\frac{T_\text{s}}{\pi}(-1)^{mN}}{t-(n+mN)T_\text{s}} \\ \end{align} $$

$$ x(t) = \begin{cases} \sum\limits_{n=0}^{N-1} x[n] \frac{\sin\left(\pi\frac{t-nT_\text{s}}{T_\text{s}}\right)}{N\tan\left(\frac{\pi}{N}\frac{t-nT_\text{s}}{T_\text{s}}\right)}, & \text{if }N\text{ is even} \\ \sum\limits_{n=0}^{N-1} x[n] \frac{\sin\left(\pi\frac{t-nT_\text{s}}{T_\text{s}}\right)}{N\sin\left(\frac{\pi}{N}\frac{t-nT_\text{s}}{T_\text{s}}\right)}, & \text{if }N\text{ is odd} \end{cases} $$

proving the latter takes a little bit. you might recognize the $N$ odd case as the Dirichlet_kernel. the $N$ even case looks a teeny bit different. but both show exactly how the $N$ samples that fully define the sampled and periodic $x(t)$ are combined to get $x(t)$.

now, since $x(t)$ is also periodic with period $T$, then

$$ \begin{align} x(t) & = x\left(t+T \right) \\ & = x\left(t+N T_\text{s} \right) \\ & = \sum\limits_{k=-\infty}^{+\infty} X[k] e^{i 2 \pi \frac{k}{T} t} \\ & = \sum\limits_{k=-\infty}^{+\infty} X[k] e^{i 2 \pi \frac{k}{N T_\text{s}} t} \\ & = \sum\limits_{k=-\lfloor \frac{N}{2} \rfloor}^{+\lfloor \frac{N}{2} \rfloor} X[k] e^{i 2 \pi \frac{k}{N} \frac{t}{T_\text{s}}} \end{align} $$

where $\lfloor\cdot\rfloor$ is the $\operatorname{floor}(\cdot)$ operator and

$$ \begin{align} X[k] & = \frac{1}{N} \sum\limits_{n=0}^{N-1} x[n] e^{-i 2 \pi \frac{nk}{N}} \\ & = \mathcal{DFT}\{x[n]\} \end{align} $$

there's actually something to fudge (a factor of $\frac{1}{2}$) about $X\left[\frac{N}{2}\right]$ for the $N$ even case:

$$ \begin{align} X\left[-\frac{N}{2}\right] = X\left[\frac{N}{2}\right] & = \frac{1}{2} \ \frac{1}{N} \sum\limits_{n=0}^{N-1} x[n] e^{-i 2 \pi n\frac{n(N/2)}{N}} \\ & = \frac{1}{2N} \sum\limits_{n=0}^{N-1} x[n] (-1)^n \\ \end{align} $$

note that:

$$ \begin{align} x[n] = x(n T_\text{s}) & = \sum\limits_{k=-\lfloor \frac{N}{2} \rfloor}^{+\lfloor \frac{N}{2} \rfloor} X[k] e^{i 2 \pi \frac{k}{N} \frac{t}{T_\text{s}}}\bigg|_{t=n T_\text{s}} \\ & = \sum\limits_{k=-\lfloor \frac{N}{2} \rfloor}^{+\lfloor \frac{N}{2} \rfloor} X[k] e^{i 2 \pi \frac{k}{N}n} \\ & = \sum\limits_{k=0}^{N-1} X[k] e^{i 2 \pi \frac{nk}{N}} \\ & = \mathcal{iDFT}\{X[k]\} \end{align} $$

if you deal with that $\frac{1}{2}$ fudging for $X\left[\frac{N}{2}\right]$ for the $N$ even case. this is because $X[k+N]=X[k]$ for all $k$.


a periodic continuous-time function can be described with a countable set of Fourier coefficients. a bandlimited periodic continuous function can be described with a finite set of $N$ Fourier coefficients, just as well as it can be described with a finite set of $N$ samples.

$\endgroup$
  • 1
    $\begingroup$ Even though I haven't checked that final formula, it's obviously true that sampling one period of a periodic band-limited signal suffices. This also leads to the remarkable result that the minimum required sampling rate for sampling a periodic band-limited signal is $f_s=0$. $\endgroup$ – Matt L. Feb 14 '15 at 9:33
  • $\begingroup$ Robert, I will look more closely to your argument later, but let me say this first. It seems to me that you're assuming knowledge about the signal, like its exact period, and its time delay. Given that knowledge, it may well be that you only need a finite number of samples. However, the sampling theorem (which is what the question was about) does not assume any knowledge about the signal except its bandwidth. Of course, the sampling theorem gives sufficient, not necessary conditions; in many cases you can do with much less samples and/or slower sampling rate. $\endgroup$ – MBaz Feb 14 '15 at 17:18
  • $\begingroup$ Robert, yes, assuming you can adjust the sampling frequency to have $T/T_s$ an integer, then the samples are periodic and you only need to keep $N$ of them. $\endgroup$ – MBaz Feb 14 '15 at 18:12
  • 1
    $\begingroup$ i'm starting to crap out on this, guys. so if @MBaz or MattL want to prove that Dirichlet thingie, the way to do it is, first assume without loss of generality that $T_\text{s}=1$, and start with the periodic $x[n+N]=x[n]$ and $x(t+N)=x(t)$ and make this asssumption: $$ x[n] = \begin{cases} 1, & \text{if }n=mN \quad m\in \mathbb{Z} \\ 0, & \text{otherwise} \end{cases}$$ and that $x(t)$ is real. then remember that the frequency components $X[k]$ where $k>\frac{N}{2}$ are reflected to negative frequency. for $k=\frac{N}{2}$, you have to split $X[k]$ in two. for positive and negative $f$. $\endgroup$ – robert bristow-johnson Feb 15 '15 at 21:54
  • 1
    $\begingroup$ @robertbristow-johnson, what Matt is doing (as I understand it) is define an "average $f_s$", which is the number of samples taken divided by the time you spend sampling. Since we take a finite number of samples, but the signal's duration is infinite, then your average sampling rate is zero. $\endgroup$ – MBaz Feb 16 '15 at 23:38
1
$\begingroup$

Sampling and the Fourier series are only indirectly related. Both are orthonormal expansions of a function, but they use different basis.

In the Fourier series, the orthonormal basis are exponential functions. The Fourier coefficents are the magnitude and phase of the exponentials. As you say, having the coefficients is equivalent, in a certain sense, to having the actual function. However:

  • As you have noticed, the Fourier series in general requires an infinite number of coefficients, so it may not be practical. However, the coefficients tend to zero (there is a proof of this), so you can keep a finite number of them and neglect the rest. The difference between the original function and the one re-created from the stored coefficients can be so small as to be ignored.

  • Note that the Fourier transformation is not unique. It is unique if you limit the functions to voltages that can be created in practice.

When sampling, the orthonormal basis are sinc (cardinal sine) functions. The coefficients of the sinc functions are the signal samples (that is, its amplitude at specific instants). The sampling theorem gives sufficient conditions for a function to be expressed in terms of this basis. A nice thing about the proof is that it is constructive; that is, it recreates the function from its samples. Notes:

  • Again, you need an infinite number of coefficients (samples) . If you only keep a finite number, there will be a difference between the original function and its reconstruction.

  • The sampling theorem assumes that the function is band-limited, which implies that it is infinite in duration. So, the theorem requires $n$ to be infinite. It makes no statement on $N$.

In engineering and signal processing, we just design our systems so that the difference between the original signal and that reconstructed from its samples is too small to notice. I don't know of any results that quantify the error in terms of $N$ for general functions.

$\endgroup$
  • $\begingroup$ What exactly do you mean by "the Fourier transform is not unique"? $\endgroup$ – Matt L. Feb 14 '15 at 9:35
  • $\begingroup$ @MattL. The Fourier transform of arbitrary time functions is not unique, in this sense: the FT of functions that differ only at individual time instants is the same. (Mathematecians say that the two function's difference is not Lebesgue-measurable.) The same argument applies to the IFT. An example is a function that is always zero, except at time $t=1$, when its value is 5. Its FT is zero, and its IFT is zero too. Of course, the FT is unique when you consider the subset of functions that can be generated in practice. $\endgroup$ – MBaz Feb 14 '15 at 17:06
  • $\begingroup$ OK, so you're referring to functions that are equal "almost everywhere" having the same FT. That's clear, thanks. $\endgroup$ – Matt L. Feb 14 '15 at 17:17
  • $\begingroup$ Mathematicians say not that the difference is not Lebesgue measureable—non-measureability is a different, and unpleasant, kettle of fish—but rather, as @MattL. says, that the original functions are equal almost everywhere, or that the difference equals 0 almost everywhere. I would prefer to phrase this as saying that the inverse Fourier transform is not unique: there's only one Fourier transform for each function, but there are multiple different functions that have that Fourier transform. $\endgroup$ – LSpice Apr 12 '15 at 23:02
  • $\begingroup$ @LSpice I should have said that their difference has Lebesgue measure zero, instead of being not measureable; thanks for the correction. See definitions 2.5.2 and Theorem 6.2.12 from this book. $\endgroup$ – MBaz Apr 12 '15 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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