From: andrey@cco.caltech.edu (Andre T. Yew)
Newsgroups: rec.audio
Subject: Re: CD SOund QUality (really long)
Date: 23 Dec 1992 02:45:46 GMT
Organization: California Institute of Technology, Pasadena
NNTP-Posting-Host: punisher.caltech.edu

	Perhaps this should be an FAQ entry -- the sampling theorem.
I'm going to give my attempt to explain this clearly  (yeah,
right), so maybe someone could write one about bits needed
and dithering.  A warning: my explanation is quite long.

vanz@tragula.equinox.gen.nz (Martin Nieuwelaar) writes:

>I haven't introduced oversampling, as I'm still not too sure what it
>is.  If someone could tell me if what I think is correct, is
>correct I'd be pleased.  What I think happens is that you take
>two of the samples, and do a straight line interpolation between
>the two.  eg, with 4 times oversampling, there will be three extra
>values created between the originals.  If this is so, then I
>would expect the maximum sampling frequency would remain the same,
>which makes sense.

>One result of this (assuming I'm correct) would then be that
>an analog 22 KHz sine wave, could be sampled at 44 Khz.  The result
>would be a square wave.  Oversampling this with linear interpolation
>would result in a triangular wave.  Interesting.

	Well, you're using the wrong kind of interpolation:  for a
point-sampled signal, you want to do sinc interpolation (what
the heck is a sinc?  It's sin(pi*x)/(pi*x)), not linear or
zeroth-order hold (stairsteps).  Why is this?  Let's just
say your sampling method dictates what kind of interpolation
you have to do.

	Let's go through a little proof of why 2 points is enough
(it really isn't -- you can retrieve information that has
just below half of your sampling frequency;  as an example, point-
sample a sine wave at exactly twice its frequency and look
at its Fourier transform).

	Okay, for simplicity's sake, let's look at a point-sampled
signal, that is our samples are just points on the signal we're
sampling.  Now, we need a function called a delta function -- imagine
it as a spike of infinite height at exactly one point and zero
everywhere else.  Usually the spike is centered at zero.
Now, let's say we have a function that's made up of these spikes
placed at regular intervals, say they're placed a distance
exactly equal to our sampling period (this is a function that
depends on time).  Now multiply this delta-function train
by the signal we're trying to sample.  Waving our hands a little,
this is exactly the same as point-sampling our function.
Think of the spikes as giving us our points and the zero
parts between spikes giving us the gaps between the sample
points.

	Now you need a little faith in math.  Fourier transform
the multiplied functions.  What's a Fourier transform?
Think of it as a change in coordinate systems -- kind of
like changing to polar coordinates, except fancier.  Instead
of having straight lines as our coordinate axes, we now have
functions (exp(i*n*w*t), i = sqrt(-1)).  Why are we doing
this?  It makes certain things easier to see -- the t you
see in exp(i*n*w*t) is time, the w frequency, and the n
just says which axis we're looking at.  It's intuitively
believable that this Fourier transform thing changes
things between time and frequency domains, or at least
has something to do with, right?  So, the reason we're
doing this is because we want to look at the frequency
content of our sampled signal.  This is the same idea as
those spectrum analyzers you see on some stereo equipment.

	Now, one requirement of the signal we're sampling is that
it has to have finite bandwidth.  This means that there's no
frequency above some limit we name.  So, on our frequency graph,
the signal we're trying to sample should go to zero before
infinity.  That is, it could start off at some level at zero
frequency, but then goes to zero and stays at zero at and above
say 20 kHz.  Another thing that happens is that our function
looks symmetrical when we Fourier transform it, so it's
mirrored over the origin like so:

      amplitude (well, not really, but linear proportional)
          |
      ----|----
    /     |    \    <---- This will be refered to as the brick
   /      |     \         because, well, it looks like one!
 ------------------ frequency
          0

	Okay here's the faith part.  When you Fourier transform
a multiplication, it becomes something called a convolution.
A convolution is when you take two signals, multiply them,
and integrate them.  Then move one of the functions over a
little bit, and do the same thing.  Now, plot the value of the
integral against the distance you moved the function (x = 
distance, y = integral), and you have a convoluted signal.
You do this all the way from -infinity to +infinity, that
is you move one function over that whole range.

	So now let's look at our Fourier transformed
function.  We have the signal we're trying to sample,
which looks like this thing that goes to zero at some
finite frequency, we have our delta-function train,
which, on faith, stays a delta function train, except
spaced apart a little differently (at multiples of the
sampling frequency, instead of multiples of the sampling
period because of a basic property of delta-functions
when you integrate them over infinity), and they're
multiplied, which becomes a convolution.  It's pretty
easy to convolve a train of delta functions and something
else -- you've just got those spikes to worry about, the
rest are zero.  What you get is the Fourier transform of
the signal we're trying to sample, that brick thing
above, centered on every spike in the delta function
train.  So the upshot of this is that when you point
sample a signal with finite bandwidth and you take
its Fourier transform, you get a bunch of bricks 
spread over regular intervals in frequency.  Each
of these bricks contain all of the original signal,
except they are shifted up to higher frequencies.

	Okay, nice picture, so what?  How do we recover
our original signal?  We multiply our bricks graph
with a box filter that's zero above and below some
limits.  Our box filter wipes out the higher frequency
copies and leaves the one centered at zero intact.
Voila!  We have our original signal.  By the way, the
reason it's called a box filter is because it looks like a
box -- some non-zero value in the center and zero outside
some limits l and -l:

  amplitude
   ___|___
   |  |  |
___|__|__|___ frequency
  -l  0  l

	Now when can't we do this -- multiply by a box
filter?  When we have our bricks overlap.  When do
our bricks overlap?  When either the spikes they're
centered around aren't far enough apart, or the bricks
are too fat.  Put another way, when our sampling
frequency isn't high enough (the spikes are placed
at multiples of our sampling frequency), or the
signal we're trying to sample has frequencies that
are too high (the fatter the bricks, the higher frequencies
they contain).  Now geometrically, we can see what this
relationship between spikes and bricks have to be:
since the spikes are placed at a distance equal to
our sampling frequency apart, the bricks have to be
less than half that distance, or half the sampling
frequency, on one side (remember they're mirrored
around their spikes) not to overlap.  Guess what, 
this is the sampling theorem:  for a signal of 
finite bandwidth B, you need to sample faster than
2B to be able to reproduce it exactly.  Note to
nitpickers:  bandwidth in my book means w >=0.

	Now, just for fun, let's take the inverse Fourier
transform of the multiplication of the box filter and
our series of bricks.  What we get back is the convolution
(works the same going backwards) of the sample points,
the series of bricks, and the inverse Fourier transform
of our box filter.  The inverse Fourier transform of
the box filter is a sinc function.  And interpolation
means convolving these two functions together.  So
there you go -- if anyone hung out til the gory end.

	Here's a piece of party trivia that some might feel
would put a damper on the wonderful sampling theorem:
a bandlimited signal is not timelimited.  And vice-versa.
So, we can't ever produce a signal that satisfies the
sampling theorem.

	A much better explanation of this is found in the
book by Oppenheimer, somebody, and Young, called, I think,
_Signals and Systems_.  It's a red book.

--Andre

-- 
             Andre Yew andrey@cco.caltech.edu (131.215.139.2)
Newsgroups: rec.audio