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.