Xref: utzoo sci.electronics:18423 comp.dsp:1391
Path: utzoo!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!samsung!uunet!pilchuck!seahcx!phred!jefft
From: jefft@phred.UUCP (Jeff Taylor)
Newsgroups: sci.electronics,comp.dsp
Subject: Re: A question about the Nyquist theorm
Message-ID: <3354@phred.UUCP>
Date: 13 Mar 91 01:35:17 GMT
References: <20408@shlump.nac.dec.com> <625@ctycal.UUCP>
Reply-To: jefft@phred.UUCP (Jeff Taylor)
Organization: <625@ctycal.UUCP>o
Lines: 178

In article <625@ctycal.UUCP> ingoldsb@ctycal.UUCP (Terry Ingoldsby) writes:
>Pursuing the discussion of the Nyquist theorem, I have a question
>about practical sampling applications.  If you have a sine wave at
>frequency f, which you sample at just over 2f samples per second then
>the Nyquist theorem is satisfied.  I know that by performing a Fourier
>transform it is possible to recover all of the signal, i.e. deduce that
>the original wave was at frequency f.
>
>Note that this is different than just playing connect the dots with the
>samples.  Most of the algorithms I've heard of used with CD players
>perform a variety of interpolation, oversampling, etc., but these all
>seem to be elaborate versions of connect the dots.  I'm not aware that
>the digital signal processing customarily done will restore the wave to
>anything resembling its original.
>
>I suspect that there is something I am missing here.  Can anyone clarify
>the situation?


I wrote this about 5 years ago, and have posted it a couple of times in the
past.  Nyquest and Oversampling/zero filling seems to be on of those things
that most people know about, but don't really understand.  I've gotten enough
mail back saying this clears up some of the same sorts of questions that are
appearing again - that I'll post it again. 

jt


---- OVERSAMPLING AND ZERO FILLING ----------------------------------
What follows is a hand waiving (no math) justification on why this is logical
(although it defies common sense).

Back up to the basics about sampling (talk about the signals, and leave
out A/D's for the moment).  Everyone *knows* that the
sampling must be done at twice the bandwidth of the signal.  This is because

	1) The fourier transform of a periodic impulse (time domain) is
	a periodic impulse train (freq domain).

	2) The Multiplication of two signals in the time domain is
	equivalant to convolution in the frequency domain.

                time                            freq

	|   **         **                 |   *
	|  *   *      *   *               |**
Signal	|  *    *     *    *              |    *
	|-*-------*--*-------*            |     *
	*          *          *           |     *
	|*          *                     |--------------------


Sample  |                                 |
impulse ^   ^   ^   ^   ^   ^             ^               ^             ^
train   |   |   |   |   |   |             |               |             |
        +---------------------            +-------------------------------
        |<T>|                             |<---- 1/T ---->|

If we multiply the two time domain signals together (sample the signal) we
get:

	|                                 |   *       *       *      *
	|   ^           ^                 |**           *****          *****
	|   |           |                 |    *     *         *    *
	|   |   ^       |   ^             |     *   *           *  * 
	+----------------------           |     *   *           *  *
	v           |                     +---------------------------------
	|           v                             ^
                                                  |
						 1/2T

Looking at the freq plot, if we filter everything to the right of 1/2T,
we get the original signal back.  Therefore this impulse train (time domain)
contains all the information in the original signal.

A couple of important points about this time domain signal. 1) it is a
different signal then the original 'analog' signal, but contains all
the information that the original signal had.  2) It is a periodic sequence
of impulses, and *zero* everywhere else (the definitive digital signal,
only two values, 0 and infinity :-)). 3) It can be completely described
with a finite number of terms (the area under the impulses) so it is 
well suited for digital systems.

The disadvantage of this signal is that it is hard to realize (infinite
bandwidth, infinite amplitude).  However it is easy to get the weighting of
(area under) the impulses.  The area under each impulse is the value of the
original waveform at the instant it is sampled.  (Sample/Hold -> A/D).

[Key point coming up]

If you think of the 'digital' signal as completely describing the impulse
train signal, instead of an approximation of the original analog signal, it
is easy to accept zero filling as not introducing any errors.


	|                                 |   *       *       *      *
	|   ^           ^                 |**           *****          *****
	|   |           |                 |    *     *         *    *
	|   |   ^       |   ^             |     *   *           *  * 
	+-o---o---o---o---o---o           |     *   *           *  *
	v           |                     +---------------------------------
	|           v                                     ^
                                                          |
						         1/2T

By adding redundant information (the "o"'s above) of impulses with zero
area, we have not changed the spectrum of the signal, or it's ability
to represent the original analog signal.  Granted, this signal will not
look much like the original analog signal if plotted. So what. [try
sampling a 99 hz sine wave (which we know is bandlimited < 100hz) at
200 samples/sec.  It won't look like a sine wave either].  Two other
approaches, linear interpolation and sample duplication change the
impulse train, and the spectrum.  [ sin(f)/f ** 2  *I think*  and sin(f)/f ]


[Draw out a couple of cycles of 99hz and sample it at 200 S/sec, then
upsample to 400 by 1) zero filling, 2) linear interpolation 3) sample
duplication. None of them will be very accurate representation of the
original signal (if they are, change the phase 90 deg)]

Why bother oversampling?  Twice the sample rate, twice the processing
required (or more (or less)).  In the case of CD's which have a signal
BW of 20Khz, and a sample rate of ~44 khz, that means any signal at
20khz gets mirrored at 24khz.  To get rid of it you either need a
*very* sharp analog filter (with phase distortion/ringing), or lower
the BW of the filter (and lose some of the high freq).  If you
oversample by zero filling, it is possible to remove the
aliased signal with a digital filter.

A digital FIR filter has some good properties for removing the aliased
signal.  It is easy to make mulit-stage (90+) filters.  They are
noncausal (for proper reconstruction in the time domain, each of the
'zero' samples should be influenced by next impulse (not easily achieved
in an analog design :-) )).

		IMPULSE RESPONSE FIR INTERPOLATION FILTER

                                 |
                                _-_
                               - | -
                      _-_     _  |  _     _-_
                -*---*---*---*-------*---*---*---*
                   -      -_-         -_-      -


An important thing to notice about this filter is, it is zero at every
other sample (original sample rate), so running the oversampled signal
through this filter does not change any of the original samples (also
hard to do with an analog filter :-) ).  Adding more stages to the
filter moves the added zeros closer to the values of the original
waveform (by removing the aliased frequencies).  If the filter was
perfect, and the analog signal was bandlimited, they would become
identical to what would have been sampled at 88Khz.

The signal, and it's spectrum after running through this filter is:


	|                                 |   *                      *
	|   ^           ^                 |**                          *****
	|   | ^         | ^               |    *                    *
	|   | | ^       | | ^             |     *                  * 
	+----------------------           |     *                  *
	v           |                     +---------------------------------
	|           v                                     ^
                                                          |
						         1/2T

This is then fed to a D/A converter (at the 88 Khz rate), and the analog
output filter has a much simpler job. The signal at 20Khz is aliased at
68khz.

[side note on this FIR filter - half of the coefficents are zero,  half
of the signal samples are zero,  and the coefficents that are left are
duplicated.  But IIR filters have the reputation of being more efficent?
(but then I often use IIR filters when I want less ripple disortion,  and the
traditional rational for FIR filters is low disortion due to linear
phase delay).  Such is dsp, it often doesn't make sense, until you remember
the reason for your prejudice.]