So in this video.
We're going to consider Shannon's crowning
result.
That it called this in 1948.
The so called, Noisy Channel Coding
Theorem.
What this theorem states, that it is
possible to communicate through a digital
channel that introduces errors.
So that the error correcting code can
correct all the errors.
Not just the single bit errors but all the
errors.
And we'll be very interested in the
conditions under which you can do that.
This is going to lead us to find the
capacity of a channel which is the magic
number that summarizes the error behavior
of the channel.
And once we understand that result, this
will lead us to understand why is
everything digital.
There's no longer really much left anymore
that's analog.
And we'll see why that is in just a
second.
So let's review the Digital Communication
Model.
We have a digital source.
And it goes through the compression stage.
And It then goes through the channel coder
which introducues the erorr corerecting
cods.
It gets sent through a channel that has a
probability of Pe of flipping a bit.
And we've already seen there are error
correcting codes such that the decoder can
correct those errors as long as there
aren't too many of them.
We worry about the single bit error
correcting code.
And once you correct those errors, you
have now the, the same you can get out the
bits that you were sent which allows you
to reconstruct the signal and, and you are
very happy.
However this only mitigates the channel
errors.
If there happens to be two bits an error.
Set of one, there's nothing that, that
code we talked about can do.
It will totally foul up.
So we can reduce the errors with those
error, a single bit error correcting
schemes but we can't make it go to zero.
Well Shannon asked, can we remove all
channel induced errors?
Is there such a powerful error corrupting
code that we can use it and not worry
about any kind of errors that the channel
may be introducing.
And clearly the answer was yes you can but
let's see what the statement or the result
is.
So the noisy channel coding theorem.
Says, says let e be the efficiency of the
code.
So if you recall, we have an NK where N is
the length of the codeword that's used to
represent K bits.
K data bits.
If that efficiency is less than the
capacity C of the channel, then there is
an error correcting code that has the
probability.
That, as the length of the, the code word
goes to infinity, the probability that
you, that you can decode without the,
that, the decoding will incur an error.
Let me get this straight.
So if the decoding will incur in error is
0.
In other words, you can get the data
through without error.
And that's so long as the efficiency of
the code is less than the capacity and
I'll show you in the next line what the
capacity is.
I want to point out some things though
first, and that is this limit here means
that the code word length is going to
infinity.
Since we're keeping the efficiency at
constant that means that more and more
data bits are being used in the error
correcting code.
So this code word is going to get very,
very long but if you do that despite what
we may have been seeing there exists an
error correcting code out there.
So its that you can make the probability
of an error occurring in the recovering
data block, 0.
He then proved a result which makes this
capacity a very special number.
If the code efficiency is greater than C
then all error correcting codes.
We'll always incur decoding errors.
In other words, again, as the block then
goes to infinity, a probability that
there's an error anywhere in the data
block is going to be one.
So you better have a code, use a code, use
efficiency less than the capacity.
If you try to use one that's was a bit
weaker.
Doesn't add as much error corerection.
You will never be able to correct the
errors.
So, what is the capacity?
So, if our little channel, the digital
channel we've been talking about.
The capacity is given by this formula.
And if you seems, say that looks a little
bit familiar.
It does look like it's the entropy formula
applied to Pe and 1 minus Pe.
In fact 1 minus, it's 1 minus an entropy
formula involved in those quantities.
So here's a plot of capacity.
So let's focus on the extremes here first.
Let's look at Pe equals zero, the capacity
is 1.
And since E of, the efficiency of the code
has been less than C N.
Needs to be less than c.
That means that we can have efficiency
code of, efficiency of 1, when Pe is 0.
Well, efficiency of 1 means there is no
coding.
That all thee, all this in and code words
are data bits, and certainly if there are
no errors in the channel will just send
the data through, if that's your problem.
On the other hand, on the other extreme,
Pe is half, that means that the channel is
randomly flipping the bits.
And, it's total chaos, basically coming
out of the channel and there is no error
correcting code, because you cannot send
times through the efficiency has 0.
And why bother?
So at some intermediate Pe, you cannot use
a code that's greater than this capacity
if you have any hope of getting the
message through without error.
If you try to use something that has a
greater efficiency, greater than capacity,
you're going to have errors.
You just can't do it.
What's interesting about this plot is that
you can plot it for Pe greater than a
half.
There's no reason you can't, and it kind
of falls in on the map that indicates
where Pe is 1.
That means if the channel is flipping
reliably every bit changing a 0 to a 1,
changing a 1 to a 0.
And if the efficiency is 1, you might as
well just send all the data because all
the channel decoder has to do, it just
flip the bits back.
So, automatically, that result is taken
into account.
So a really bad pe, turns out to be
equivalent to a really good one.
So Channel's result is symmetric in that
way.
So let's talk about a few issues with the
Noisy Channel Coding Theorem.
Which are pretty important.
And the first is this phrase that keeps
coming up, there exists an
error-correcting code.
Well, to this day, we don't know what that
code is.
There are two candidates out there that
are being studied today.
And they come very close to the so called
capacity limit but no ones proven that
they can satisfy the noisy channel coding
theorem.
Shannon's proof with the noisey shany,
noisy channel coding theorem is fine.
There's nothing wrong with it.
It's just that it's not what we call
constructive.
It doesn't give you an example.
Proof of it did not use an example code.
It was proven a different way.
We still don't know what the code is.
But there is a more practical problem
which has to do with this limit, as N goes
to infinity.
So this means the code word length has to
go to infinity which means you're also
taking in more and more data bits and
encoding them all at once, sending them
through the channel and then decoding
them.
So this incurs what we call a coding
delay.
And you also have to wait for all the data
to come in before you can run your channel
code.
Now, that isn't very nice and the capacity
that obeys this result is sometimes called
the C infinity capacity, which means you
need an infinite length code word.
And what we'd like to talk about is what
is the capacity for a finite length code
word.
It's certainly, if it exists is going to
be less than C infinity capacity.
But we don't know there are a noisy
channel coding theorem for such a thing.
It's not clear that you can correct all
codes with a finite length block.
But people are certainly working on that,
so we can have practical codes.
Well, Shannon also derived a capacity.
When we take into account the fact that
underneath our digital channel, there's
really an analog channel.
So as we always abstracted the analog
channel, channel it's adding noise, the
signal set choice and everything and just
call it a digital channel.
But, if you go back down and you talk
about a white noise channel having a
bandwidth of W.
And having to have figured out what the
signals sets are.
Then Shannon's results says yes.
If the datarate of the source is less than
the capacity, then you can have what are
called, we call reliable communication, no
errors you can't, will occur.
If you have the right error correcting
code.
So if the rate is less than capacity, you
can send information through a channel
without error, somehow.
And here's the formula for capacity.
So, W is the bandwith of the channel in
hertz.
The signal to noise ratio is the
signal-to-noise ratio in the channel.
And this result is in bps because of the
law of this too.
And just as before, if you try to send it
at a data rate greater than capacity, it's
impossible to have reliable communication.
You're always going to incur error.
So, nowadays when you try to design a
digital communication system, one of the
things you do is calculate the capacity to
make sure.
And make sure that the data rate your
trying to sent to that channel satisfy
this bound.
If they don't, you're going to have
errors.
If you use a data rate less than capacity
then there's hope that you can, there is a
signal set and error correcting code
that'd do the job, but like I said, we
don't know what they are yet.
But no one tries to send at a data rate
greater than capacity because there's no
hope.
So I'm going to go through our little
example that we've done before and if you
recall we were trying to send an analog
signal through a channel here.
Th, and the analog signal had a bandwidth
of 4 kHz.
So, we're going to send it an A to D
converter and sample it.
Now, thing to note is that the anolog
signal, incurred a quantization error.
And once we, when it's in that A to D
convertor, and you sample it with a finite
number of bits, here four.
There is an unrecoverable error.
We cannot get the original signal back.
So what I want to ask is can we mitigate
the communication errors?
Can you get rid of them?
Simply only have the quantization error of
the A to D converter.
So, for this example the sampling rate is,
of course, 8 kHz.
Twice the bandwidth of the signal.
And I'm using a band, or a number of bits
of 4 and the A to D converter in this
example.
So we have a data rate of 32 kilobits.
So we want to know, for what channels, is
the capacity greater than 32 kilobits.
And I have here a color plot.
That chose of how that works.
So, the large area in color here.
All I'm doing is plotting the capacity as
a function of SNR.
And channeled down with in hertz.
So in the 32 bit kilobit plane is shown.
And so this boundary here forms, shows us
which channels can support the data rate
of 32 kilobits, So that you can get the
information through without error, at
least in theory.
So, we can see that, as the.
The we have approaches, about 4 kHz.
You're going to need a very high quality
channel, because the SNR you're going to
need is very, very high.
Furthermore, if the SNR gets low, it turns
out the bandwidth is going up and up and
up.
And, that's kind of standard.
So if you're anywhere in this region, it's
impossible.
You're in big trouble.
So you want to be in the region that's
inside this boundary.
You want to be in there somewhere.
In order to communicate this signal you
have a hope whether it's sending the
signal through, with the, the help there.
I want to compare this result with the
plot we had for the signal-to-noise ratio.
So if you remember this plot, I was
comparing analog communication, which is
the resulting message signal-to-noise
ratio was given via that.
Y is a function of the channels that
signal is shown, with 4 bits and 8 bits.
And, I'm only going to do the 4 bit
example again.
So, turning things around a little bit, if
you, you want to know what signal ratio
would work?
And the data rate, of course, is the
sampling rate, times the number of bits in
the de-converter.
And when you work that all out, you get
this.
Well, for the case that we were, worrying
about.
We were worrying about an 8 kHz, y
channel.
Which so that you could use the same
bandwidth as the analog signal requires,
modulated analog communication required 8
kHz bandwidth channel.
Suppose you made the digital channel live
with eight kilo hertz?
What signal noise ration are you going to
need?
Well you can do that in this calculation.
Wc and Fs are the same quantity, so you
just get 2 to the B minus 1.
So the answer, answer is 15 which in dB
turns about to be about 11.
So what results is I can send my
information through my channel, my channel
somehow.
Yet if the SNR is bigger than this number
then I will incur a no communication
error.
The only thing I'm left with is the
quantization error, that's this plateau.
But once I drop below this magic number,
it turns out to the signal-to-noise ratio
goes to basically 0 and I can't get
anything through.
And this is the capacity wall, its called.
And once you get, you transmit enough
signal-to-noise ratio so which your above
magic threshold, things are fine.
But if you fall below it, things are not
very good at all.
You're going to be in big trouble.
And as you can see from this plot, you're
better off not using any channel coding at
all.
And this is what happens when you use BPSK
and don't do any channel coding.
In that situation, in this regime, you're
better off not trying to do channel coding
at all, but you're always incurring error,
and that's the sad result.
But there is a region with which you can
get through and live only with the
quantification there.
Very, very nice.
So.
Why is everything digital?
So.
Sources can be compressed, first of all.
And that's either lossy or lossless,
depending on whichever you're going with.
If it's lossy and you could consider
running an analog signal through and A to
D converter as being a lossy compression
scheme.
It's representing signal bits but you
cannot recover it.
Same thing is compressing music with an
MP3 compre- compressor as lossy
compression.
Be then as it may, you can convert
basically in its any source into a
sequence of letters which can be
compressed in the source coders.
Somehow, we can find a error cracking code
that's very good.
As long as it obeys the noisy channel
coding theorem, we know we can actually
decode without error.
So, that means once you are wiling to
incur the error in digitizing analog
signals converting it to bits.
Turns out that means now.
Digitized signals and inherently digital
signals, like text, can now be transmitted
over a common communication scheme without
error, and that is really interesting.
So, once you have bits, you got a chance.
You can send the bits through a channel
with no error.
There is no similar result for analog
channels.
Once you have error and noise introduced
in an analog channel you have to live with
the errors if you stay analog.
But if you go digital, or if you have a
digital source, you can correct those
errors if they channel.
Well you could do this if the situation is
correct.
In other words, if the data rates is less
than the capacity.
Well, this ability to send any kind of
signal once its bit.
That leads to repute computer networks.
Well computer networks can carry any kind
of signals.
Be it SMS.
Be it your voice.
Be it an image.
Be it a video.
We all can put all those different kind of
sick messages into a common communication
scheme.
And the reason for that is Shannon's Noisy
Channel Coding Theorem.