This video we're going to talk about Error
Correcting Codes.
How we can get around some of the errors
that channels may introduce.
So we're going to talk about one, as very
simplest one called a repetition code.
And then we're going to go on to a, much
more interesting and much more useful code
actually classic codes called Hamming
codes.
Let's go through and see what I mean by
error correction.
So, here again is the digital
communication model, that we've had
before, but there is a new thing it has
been stuck in here.
So, we've already talked about source
coding.
And how to do compression and represent
the source letters efficiently with bits.
Now what's going to happen the channel
coder, is going to be placed here.
So that it converts the, what we going to
call data bits into more bits.
They have a very special structure, so
that by the time these bits arrive and
goes out of the channel where errors can
be introduced, the channel decoder can
repair those errors.
And hopefully produce something that's the
same as the data bits produced by the
source coder.
So, this may seem like magic.
How can the, we compensate for errors that
the channel introduces after they've
occurred?
And that's the it's actually pretty
straightforward to see how you can do
that.
But generating efficient error correcting
codes is somewhat tricky.
So, can we mitigate channel induced
errors?
Absolutely, and these lead to the error
codes which are commonly know as ECC.
So, the simplest error correcting code is
the repetition code.
It's pretty easy.
So, you take for each bit reduced out of
the source coder, you repeat it.
In this case, 3 times.
So, a 0 data bit becomes 3 data bits in
what we are going to call the codeword.
And if the data bit is a 1, we produce 3
bits that are 111.
We just repeat them, that's why it's
called a repetition code.
So this actually helps and in more detail
about what's going on.
Is that you have this little drawing here.
We have a sequence of data bits that looks
like I've got here a 1, 0 and a 1.
And if we went through our tran, digital
transmitter and worried about a BPSK
baseband signal set.
That might produce something that looks
like that.
Well now if you take that same sequence
and go through the channel coder, it's
going to repeat the bits.
So now we have 111, 000,11 and 1.
One of the ones got chopped off.
And when that goes through the
transmitter, we now have individual bits.
And the correlation receiver knows those
are individual bits.
And is going to try to figure out what
each individual bit is.
So now there is a pe for, for every one of
those new bits.
All right.
So this creates what is called an n1 code.
So we're repeating the, each source bit N
times.
So for every data bit that comes in, we're
producing N bits, so that's what the N
comma 1 means.
One bit in, N capital N bits, out in the
code.
Now the other thing that's important here,
will be important in applications is this,
what has, what's known as a code rate,
which is the same as Re-expression of
this.
It says that for every bit in, I have to
send capital N bits, so it has in the case
of our repetition code it has a rate of a
third which we going to see is a little on
the low side.
But, this code can correct.
All single-bit errors.
And let me show you how that works.
And what we're going to do is code by
majority vote.
So here's the idea.
And this is why the number of bits N in a
repetition code is odd, because we're
going to vote.
So, let's say that the source bit, the
data bit was a zero.
We're sending 3 bits so there are 8
possible received codewords that could
come out of the channel.
All the bits could come out correctly and
no changes and so we say.
It's a 0, because we're going to raise our
hands and vote.
All say 0, all say 1.
Pick the one with the most votes.
So here's a case where one bit got
flipped.
And what it's going to do is still
majority 0, so it corrects the error.
So this is how you can correct errors
after they have occurred.
And that's because you just repeated the
same thing several times.
If you go down this list, you see there
are times it's possible that 2 bits
occurred in there and if the error
correcting code is not going to be able to
correct it.
So, that is why this is a single-bit error
correcting code.
It can correct 1 bit an error but not 2 or
3.
So that turns out to be an accomplishment.
So for all the 8 possibilities of received
codewords, we can correct one, two, three,
four of those codewords and, and
understand and then say that a 0 was
actually send and we get it wrong four
times.
And same thing is going to happen when a 1
is sent, we won't be able to correct the
error for 4 of the codewords and be wrong
for the other four.
So, what's the probability now that the
data bit is decoded wrong?
So that's going to be the sum of the
probabilities for the cases in which an
error still occurs.
And that's just how it goes up and you get
that word expression.
So the question is, do we win?
Is this probability what's called a
decoding error?
We don't get the original data bit back.
Is that probability bigger or smaller than
pe.
In other words the situation in which we
sent only, only one bit which is what we
would do if we had no error correction.
It had better be smaller.
Then it turns out it is.
You can show that if pe is less then a
half, that this quantity is always less
than pe and sometimes much, much less.
Pe is like a 1000th, 10 to the minus 3
notice this square over here, and that's
going to be probably the dominant term and
so, and a 1000th this probability here is
roughly 3 times 10 the minus 6.
So we can really reduce probability of
error by adding error correcting bits.
So lets over where the repetition code is,
its a very simple code, not just repeat
the bits, very easy to do but it has some
downsides.
One, it has a very low coding rate, 1 over
n, and we're going to discover in just a
second an error correcting code that has a
much higher rate and still corrects all
single-bit errors.
Note that as N increases the probability
of just getting 1 bit in error actually
becomes smaller in the probability of
getting 2 bits in error or 3 bits in
error.
And that's just because you keep flipping
coins a lap you going to not just wind up
with just 1 bit in error.
That's all the repetition code can do,
just correct 1 bit in there.
So we definitely need more powerful codes.
Well let's talk about one.
Well first we need to know about what are
called block codes.
And this is a generalization of the
repetition code.
Repetition, repetition code is a special
case of a block code.
So here, what we're going to do is take in
a block of K source bits at once and what
we're going to put through the channel are
N bits derived from those K.
So, in the case of the repetition code we
took in 1 bit and put out N.
More generally we're going to try to take
in more than 1 bit at a time.
Input out again.
And that's an NK code.
And that's why I wrote before that the
repetition code was an N1 code.
Special case.
And here's an example of a 7, 4 code,
which, as you might expect, has some
pretty good properties.
We're going to see that as we go through.
So, here's what it does.
It's trying to put out a codeword of 7
bits.
Here's a list of the bits and here's a, a
mathematical description of how they are
related to the data bits.
The first 4 bits simply repeat the data
bits, so they're exactly the same.
And then, for bits 5, 6, and 7, they are
given by, it turns out, sums of the data
bits, of particular data bits.
Now what that o, o with a circle around
it, plus with the circle around it, means,
it means exclusive or in, it's, it's
usually addition and binary arithmetic
when there's no carats.
So you, 0, exclusive or 0 is 0.
1 exclusive or 1 is 0.
It's only when the 2 bits disagree, do you
get a 1.
And so, you may have 3 bits here.
They get "added together" but the result
is only going to be 1 bit.
And so, no matter what the data bits are,
you just apply these formulas.
And that derives the 3 bits we get you
might say, extra.
We have 4 data bits coming through as they
are.
And we derive three more bits from those.
Turns out these are good bits to derive,
it turns out.
So we gotta figure out the, how do we, can
we think, how can we prove that the code I
just wrote, that 7, 4 code, actually can
correct errors.
So we need to go and, and figure out a
little bit more about error correcting
codes and how to think about them.
And the key to that is something called
the Hamming Distance.
So Hamming Richard Hamming was a Bell Labs
engineer, and developed a whole sequence
of things.
Hamming Distance, and it turns out that 7,
4 code is a special case of the Hamming
code family.
So he worked on this a lot.
So, we're in to find the distance between
two codewords as being the sum, and I
really mean sum here, of c1 exclusive over
c2 so you're going to get N bits out of
this.
The sum, what that's going to be, is the,
it means how many ones are there in that
result.
So you exclusive or these two things
together, and then you tell me how many 1s
there are.
That's what sum means.
Sum means think about them as a real, as
actual 1 and 0, not binary numbers.
So let's take an example.
Suppose I have two codewords and I just
pulled these out of the air.
I want you to note that they differ in
those 2 bits.
Okay?
So I claim these two codewords are a
distance to a part, they differ in 2 bits.
Now, mathematically we can see that if I
add these two together and you can test
this for yourself, and the result is this.
And remember the exclusive or gives you a
one only if the bits disagree.
That's the key.
And of course the number of bits you have
in there is 2.
And so that's, we know the distance
between these codewords is 2.
Now, I want point out something that's
going to be useful later on we have this
relationship here.
If I take this and add it c1, I will give
c2 and I will also find c1 is equal to c2
plus this binary sequence.
This is going to be useful later on.
Okay.
Let's see why this is important.
So distance is a the Hamming distance, it
says how far apart 2 codewords are and how
many bits have to be changed for 1 to
equal to the other.
So, how far apart do two codewords have to
be so that in spite of the fact that
there's a single-bit error, I actually can
figure out what the original codeword was?
How far do they have to be apart?
And another way of saying that is, when
can a single-bit error in one codeword not
be confused as a single-bit error in
another codeword?
That would be a disaster.
If we couldn't figure this out, and if a
single-bit error occurred, we wouldn't
know what the original codeword was, which
means we wouldn't know the original data
sequence.
So they have to be far enough apart that
1, an error in 1 codeword is not confused
with another codeword.
So I have a little geometric picture to
show you, so we can figure this out.
So, sort of abstractly, we have here two
codewords.
We have c1 and c2.
And of course, they're different.
Now suppose I have a single-bit error in
c1.
So I'm using e1 to represent some
particular single-bit error, which means
this e sequence has a bunch of 0s with a 1
in one position.
That's what the error decision names, and
that gives, once I add these two together
it gives me, let's say that.
Well, suppose I had, it was possible that
c2, if I add to it another single-bit
error sequence, give me at the same, same
place.
So these sums the number of 1s in e1 and
e2 is each one.
How far apart are c1 and c2?
Well, because I can get to c2 by taking
c1.
Adding e1 and then if I add in e2, that's
going to get me over here.
That means because these two each have a
bit of bond that when I exclusive or them
together I get 2 bits and the distance
between them is 2.
This would be a disaster in terms of pair
correction.
This is not a codeword, in general and
it's 1 bit away from c1, it's 1 bit away
from c2.
I can't tell if c1 or c2 is the actual
codeword.
I'm in big trouble.
This kind of code, if it does not have a
adding distance of greater than 2, I
cannot correct single-bit errors.
So, what distance is good enough?
I think it's pretty clear that we need to
have a minimum distance between any
possible pair of codewords that's greater
than 3.
If it's greater than 3 that's fine.
But 3s the threshold.
And the idea is that if we have one
codeword here, and another codeword there,
and an error takes us up here.
Well an error might take this up here.
And since these, let's say are at least
the distance one apart.
At least, then they won't be confused, and
I can get back to the original codeword
and correct that single bit error.
So, this is an important criterion for
having a single-bit error correcting code.
And guess what?
The repetition code satisfies that
property.
So there's only 2 codewords, because it
only takes in one bit at a time.
And so, we add together those codewords.
We get 111 and the sum of those means
there's three 1s.
So sure enough, this satisfies our
criterion for a single-bit error
correcting code.
Well, as it stands, I would have to find
the distance between all possible pairs
and an error correcting code and see what
their distance is between them.
Well it turns out, because of the
properties of block codes, there's a very
efficient way of doing it, which actually
provides some insight in what's going on.
But to do so I'm going to have to
re-express these codes in terms of matrix
notation.
So we're going to take a little notational
diversion if you will.
So, we're going to say that the generation
of a codeword from a data block, a bit, a
block of data bits, is given by this
matrix equation c equals Gb.
And G here stands for generator.
This is called the generator matrix.
And in the case of the repetition code
there's only 1 bit, cause it's an n1 code,
there's only 1 bit taken in at a time its,
it, it puts out 3 bits and the G that
looks like that means simply repeat.
If you think about it for a second what
does this mean for the case of something
like this when you have 1.
And it means, just simply give it back.
Well, lets look at our 7, 4 code which is
a bit more complicated.
So here's that code that I wrote before,
same thing.
And so now it's taking in a block of 4
data bits, putting out a block of 7 coded
data bit, coded bits.
And what G do I need to express this?
And I claim it's pretty easy to do.
So because this code just repeats the
original data bits, the upper part of this
matrix is the identity matrix.
I, capital I, because that means just
repeat the bits.
The hard part, if you will, is down here
but that's pretty easy to do.
You simply put a 1 in the generator matrix
for the bits you want in the position of
the bits you want to select in your sum.
So I've got three 1's and then a 0 that
means data bits 1, 2 and 3.
And the next one says, take data bits 2, 3
and 4.
Sure enough that's what it is.
Take data bits 1, 2 and 4, and that's what
that is.
This is a very concise way, this generator
matrix is a very concise way of writing
down what the code is.
How it operates on the data bits.
It's not clear you actually implement it
this way, but it's a nice mathematical way
of doing it as you can see in a second.
And the reason it's important is because
this code has really cool properties.
In fact it's linear.
Really important here.
So, because this is just a matrix
multiplication, this code is linear.
Suppose I add together two data bits,
sequences.
Well that's gotta be some other databit
sequence.
Who knows what it is, but it's something.
Well, you can know this is exclusive or
still obeys the distribution laws.
This is Gb1, exclusive or Gb2.
Well by definition, that's c1 and that's
c2.
So, it obeys the superposition principle.
And that has all kinds of interesting
consequences.
Because, since b1 plus b2 is some other
data bit sequence.
In our 7, 4 code these are each 7, 4 bit
entries.
We exclusive or those 4 bit blocks
together we get some other bit block.
Well that has to be some other data bit
sequences.
That turns out to be c3 which means it's a
codeword.
So adding together two codewords results
in another codeword.
Well, that means, that the distance
between any two codewords has got to be
the same as the number of bits in another
codeword.
So, we only need to examine individual
codewords to figure out the code's error
correcting capability.
We just need to examine how many 1s are
there in every codeword and that tells us
what the Hamming distances are between all
possible pairs.
So, that's why I wanted to go into matrix
notation to prove this linearity property.
It's really important.
So there's my generator matrix for my 7, 4
code I want to point out something.
Suppose I have a 1 bit sequence, data bit
sequence.
What's the resulting codeword for that?
What you should find is that the resulting
codeword for that is the first column of
G.
If you have another simple bit data block
with the 1 in the second position, that
corresponds to the second column etc.
So staring me in the face, in the columns
of G are 4 codewords.
So all I have to do is count up the number
of bits in each column and sure enough,
I'm a happy guy.
They're all greater than 3, well that's
four of the codewords.
Next thing I need to do is add together
two columns to create more codewords.
Well, I want you to note because of the
construction of this code you know that
the upper part is going to have 2 bits.
As long as every row, every pair here
differs in at least 1 bit.
I know that it's going to give me one down
here, I've got two up here, so I have at
least three.
And if you look at the way this bottom
part was constructed, you look at all
pairs they differ in the bottom part in at
least one place.
So, that means all pairs have 3 bits have
the number of bits of 3.
And now if you add three of them together
you can see from the top you're going to
get a 1 in all cases.
So that gives me a link to 3.
It doesn't matter what happens down below.
So this is a single-bit error correcting
code.
And that's because all the codewords have
at least three 1s.
The fact that one of them has 4 really
doesn't help.
It's the minimum of all these distances
that matters for being able to have that
single-bit error correcting code.
So, and I want to point out as opposed to
the repetition code, it's efficiency is
much higher.
Repetition code that we talked about at a,
a code rate of a third, low, 1 bit in 3
bits out.
Now it's 4 bits in 7 bits out.
Much higher efficiency.
And it too can correct single-bit errors
just as well as the repetition code.
So, error-correcting codes.
Even though the channel introduces errors,
the error correcting code can repair some
of the errors.
If more than one bit occur in error our
single bit error correcting codes can't
correct them.
But at least all single bit error errors
can be corrected.
And I showed you with the repetition code
that lowers the probability of the
received bits being an error.
This is very different than in analog
communication.
In that case, once the signal comes out of
the channel, there's nothing you can do
other than remove out of bound noise, but
you cannot remove the out of bound noise
by linear filtering you are stuck with.
You can't do anything with it.
Here, we're removing fixing errors and
lowering the probability.
We're essentially making the channel less
noisy by adding error correcting bits.
Now we must sent bits at a higher rate
than required by the source.
But efficient codes, i.e.
Ones having a, a rate that's close to one
are fairly easily designed.
And we'll see that in a succeeding video.
However, do want to point out that error
correcting code have limited capabilities.
We can't fix double bit errors, in fact
for the case of repetition code and the
Hamming code that I've showed you that if
a double bit error occurs, we're going to
think a single bit error occurred and
we're going to correct it badly.
We're going to make at any mistake, and so
longer codewords double-bit errors occur
more frequently than single-bit errors and
that can be a problem.
So in the next video I'm going to talk
about how you actually do the error
correction for a Hamming code.