In our previous video we talked about how
to evaluate whether a code, an error
correcting code, could correct single bit
errors or not.
What I didn't talk about, though, was
actually how does a code that has that
capability, how does it actually correct
the errors?
That's what we're going to talk about in
this video.
So to review we have the digital
communication model.
And a channel coder is what we're talking
about.
It takes in K bits at once, puts out N
bits.
And the way it does it is through the
matrix equation when c equals g b, and the
g defines the code.
It's called the generator matrix.
And the bits, the N bits that it sends
through goes through the additional
channel.
The channel has a probability, Pe of
flipping a bit, changing the 0 to a 1, or
a 1 to a 0, and it does so randomly.
So, what comes out of the channel, these N
data, N bits that come out of the channel
the received code work could have errors
in it may not.
It's up to the channel decoder to not only
determine if that an error occurred in the
transmission but also to fix it.
Fix those errors so we can produce the
original data discs that were sent and we
know that this error correcting code for
the 7, 4 Hamming code obeys the properties
that we are looking for.
We have to have the minimum distance
between any two any pair of code words has
to be greater than or equal to three.
We know that this G works, but we haven't
actually figured out how the channel
decoder does it's job and that's what
we'll be talking about today.
So, here's our source coder and our G, and
it's worthwhile going over the sizes of
things here.
This is an N.
A tall matrix, and it's Ky.
So, that agrees with the fact it's taking
in K bits, and it's producing N.
And it's also worthwhile to note that the
top K part of this is the identity matrix,
and the bottom N minus K part Is a special
matrix that has the properties we need to
kind of deem N greater than or equal to
three.
Here's what comes out of the channel, what
the channel decoder receives is not C,
which was transmitted by the general coder
that are received c hat.
And we can write express, the occurrence
of errors in this way, where e is a
vector.
It has a 1 in every position where there
was an error in the transmitted codeword.
Error upon reception.
If we remember the properties of exclusive
or addition, when you put a one as one of
the area you're adding together, that
flips the bit of the other, the match,
match, mounts to get flipping.
And so this is a very nice way of
describing the fact that an error was in
transmission.
In this case the third bit occurred in
error.
Of course the channel decoder doesn't know
which one occurred in error, it has to
figure that out.
But this was is going to be very helpful
for us.
Well, how does the decoder work?
And what it does is it forms the following
result.
It has, creates the S vector as given by H
another matrix times C hat.
And the way H is created is as follows,
you first take the lower portion of G.
You stick it in down there.
Remember, this is an n minus k tall bottom
part.
And it's k wide.
You then tack on to this lower portion of
G part, you tack on the identity matrix.
Matrix, well that makes this matrix N
minus K tall or it makes it N wide which
is what we need and so that everything,
all the dimensions agree.
So again, the dimension of S is N minus K.
Well, this seems to come out of thin air.
How does this work and that's what I'm
about to show.
Is that this formula for h, this use of h
will do what we want.
So let's look at what this matrix multiply
does.
We have sin c hat is given by this, we
substitute again.
Use the properties of matrix multiply and
that's the result.
And when I substitute it was c is, what
the channel code is, we get this.
What I'm about to show you is H times Gb
is zero.
This choice for H here is it based on
which G is, is such, is chosen such that
each time G is 0, no matter what b is, and
if its 0 that means that you multiply the
received code word by H is simply e equals
to H times the order of sequence.
If the error sequence is zero.
This result is zero.
There are no errors and we're happy.
If's when e is not zero which gives a
nonzero value for S.
That's when we get we know we have to
correct errors.
That's called the detection process.
We know that there is a, a error that
occurred, and this is not equal to zero.
So we still have to talk about how you
actually correct the errors.
So let me prove to you first that, that
property H time G is 0, is true.
So remember how G was constructed.
Identity up top, G lower at the bottom.
So that when you multiply times the data
block, you get the following result for c,
which can be written this way.
Now H, it is of course formed in the, in
this following way.
G lower is stuck down there and then I is
added on.
Now what happens when you look at H times
c.
Okay.
So that's HG times b and so, let's see.
We have multiplied this times that.
We get G lower times b plus identity times
G lower times b.
Well, whenever you add together, two
binary vectors that have exactly same
components with the exclusive or.
You get 0.
So it doesn't matter what B is because
these two things are the same you get 0
all the time.
So this H, this choice of H always results
in when a code word arrives without error
the result is going to be 0.
And the interesting thing is, is that,
when there is an error.
It's only this H times c property being 0
means that H times c hat.
It depends only on the error sequence.
Not on the transmitted code word.
That's really very cool.
So for each received code word.
We formed H times c hat and we know that's
H times e.
And if it's nonzero, we know that there
was an error.
And what you simply go through is you
write down all of the N possible, N
possible single bit error sequences for E.
You do the matrix multiplying from this
table, and all the decoder has to do is it
says oh I got 111.
That means there was an error.
I look in this table.
I figure out that the second bit was an
error and I correct it by adding it to it
as you see.
Now the entries in this table may seem
kind of mysterious, but what they amount
to are the columns of H.
That's because each of these single bit
error sequences do the multiplying just
picks out a column.
And so, this table may seem kind of random
but it's really just the columns of H.
So, it's pretty easy to figure out.
So, now that the decoder has a good idea
what the error sequence is.
It turns out if you adds that error
sequence to what it received since c hat
is c plus e, you add e again.
Well, if you add 2 vectors, they're the
same.
That's 0, and you get back the original
codeword.
It has corrected the error.
All that you could do now is determine
what the data bits were now that you have
the actual codeword that the channel code
produced.
And for the set four code, the top four
bits, the first four bits correspond to
the data bits.
So that's pretty easy and we have
corrected the error.
So, it's very cool.
All single bit errors can be corrected.
Now there's a little detail here and that
we can correct the errors but we did so at
a, at a small price.
We have to send the data at the same, at
the same rate whether we code or not.
So the time taken to send K bits with no
coding, no error correcting coding has to
be the same as if we instead used seven
bits to send the same data when we add on
the error correction.
Well, that means that we have to cut down
the bit interval by the efficiency of the
code and that means the single bit error
probability PE goes up In the error
collection case.
That's because we were using last time.
So, the question is does that, that's bad
if that P goes up.
So doing N over O.
So Y product here is the combo of the
block of there for two cases, one in I use
simply send four bits as a block.
And in the case where I employ my (7,4)
Code you wish PE is slightly hal higher
given by the formal reply rather than
through these videos.
And what you discover when you find a plot
the resulting combo is a function of the
signal-to-noise ratio in the channel.
That turns out the uncoded case always
results in a bigger probability of error
any of your code.
So we win and in some cases it can be big,
above 10db.
That's almost a factor of 10 better in
terms of overall probability getting it
through.
So error correction wins, we certainly do,
as long as you have an efficient code.
So what you'd like, you'd like the code
efficiency to go up.
Now I should comment that the repitition
code that we've already talked about the
one three one code.
If you look at it and plot the same plot,
it turns out you now get a coded error
that's bigger than if you employed no
code.
So the efficiency of this is way too
small, it's only one third, and that
really hurts.
So efficiency of this code is 4 7th.
That's better but we, you want that
efficiency even better to get more, gain
in the [unknown].
Let me talk about what a 7 4 code is and
what in particular what this hamming code
is .
What constitutes a hamming code and I'll
show you how the efficiency can go up.
So as we've seen in a, in a N K code the
number of single bid errors is equal to
the lenght of the code word which is N
bit.
Okay, now the number of nonzero values for
H times C hat is 2 to the N minus K minus
1.
N minus one is because we exclude the all
zero sequence because that means no errors
occurred.
So, the dimension of S is N minus K and
the number of numbers you can express in N
minus K bits of course is 2 to the N minus
K, tip off the minus 1.
And that's the number of non zero values,
so that's the number of possible values
for S at which it better be greater than
the number of single bit errors.
We couldn't form that table neatly so
that's the result we have to have in order
to correct all single bit errors we have
to have this property.
The question to point is we get a maximum
efficient code when we apply equality.
So what values of N and K work?
So we have this maximum efficient code and
when you have that occur, you have what
are called the Hamming codes.
So, the thing to note is, in this
expression.
That n here, has to be a power of 2 minus
1.
So all I did in, in this table was form,
list the powers of 2 minus 1.
So this is 2 squared minus 1.
2 cubed minus 1, et cetera.
And then search for a value of K that
works.
It turns out 1 always can be found.
And you can see that, as you make the code
word longer, the efficiency goes up and up
and up.
Look at that for any 63 code, the
efficiency is 90%.
So we're only cutting down the, a bit
interval by 10%.
Which is really nice.
Which means we're really going to gain
over using the old coding.
These error correcting coding.
Probably, all those bits are being in
there after decoding is really, really
small.
So, that's great but there's a problem.
And we've seen that the Hamming code,
which is very efficient can correct all
single bit errors.
But, if you make the code longer and
longer, double bit errors may become more
probable than single bit errors.
When a double-bit error occurs in a
Hamming code, it is only designed to
correct single-bit errors, and what it
does, it thinks the double-bit error was
some strange single-bit error and corrects
accordingly, and usually totally fouls up,
and results in a data block is totally
wrong.
So, in some sense, the errors become
catastrophic when a double-bit error
occurs and we have to figure out when
that's more likely.
But if you think about it for a second
some, the longer the code word is, the
more likely it is that a double-bit error
will occur rather than a single-bit error.
And it's like, you flip a coin that has a
probability of a tenth coming up heads in
ten trials.
You sort of expect there to be maybe 1 or
0, but 1 is okay.
If you flipped a million times, what's the
probability in that length In a million
flips, only one flip came up heads.
Very unlikey, it's much more likely to get
many, many more errors.
So that's the situation I'm trying to
analyze here.
So, all we have to do is compare the
probability of a single-bit error with a
double-bit error.
So, on the left hand side, is the
probability of a single bit error's p e,
the probability that all the rest are
correct is p e, 1 minus p e n minus 1.
N possible choices.
Something similar on the right hand side.
On for the double-bit error.
So, we've just simply compare the two and
it's easy to do this compilation, and what
you discover is that double-bit errors are
more likely when pe divided by 1 minus pe
is greater than 2 over N minus 1.
Well lets assume that pe is small, so we
can drop it down makes little bit easier
to see what's going on.
So as long as, when ever pe gets greater
than 2 over N minus 1 double-bit errors
are much more likely.
But you can see as N gets big, really big,
and that can, fall below the[UNKNOWN]
error that you get.
So this means that we, despite the fact we
can have a very efficient single bit error
correcting code where it may not work all
the time.
And certainly even in the 74 code, we
talked about we only have saving database.
It is, it is a nonzero probability that 2
bits can arrive in error.
So it may be a nice code in that it can
correct those single-bit errors, but it
can't correct them all.
Well, how do you correct them all?
Well, it turns out you have to make the
code word longer and longer and longer.
Well, do, do we, can we find a code that
can correct, no matter how many errors
there are?
And that turns out to be our only problem.
So, error correcting codes.
Yet we have seen, the good is, is that,
even though the channel can introduce
errors in the transmission because the
channel flips the bits.
Error correcting codes can repair the
errors as long as there aren't too many of
them.
However, it would seem that no matter what
we do the errors are always going to be
present in digital communication problems.
Well now this is where a somewhat
surprising result comes up.
[unknown] his 1948 paper showed that it is
possible to send bits through a channel
that introduces error and find an error
correcting code that fixes all the errors.
And here's a theory general criterian for
that.
And that's what we're going to talk about
next.