At Sacramento - at your listening station - you hear 010 and you say: "That can't be right!"
What's the simplest thing to do? To try and find out what the weather really is?
Because you know that an error has occurred.
We've talked about the most compact way to transmit this information. There are
four possible patterns. You could have two zeros. You could have 01, 10 and 11.
However, you have got to be careful here because what we've done - and referring back to
what I've said previously about compression methods - what I've done here
is devise a code which has no redundancy at all. We've talked about how
to squeeze redundancy out of text files and pictures - which is what compression
is. It's getting rid of unnecessary information. There's nothing unnecessary
here - every one of those bits is vital And you'd better hope they don't get lost
or distorted on the way. Unfortunately they might get lost or distorted on the
way! So the next thing we have to say is that these codes are beautiful but they rely
on you having clean, noiseless, communication across your telephone wire.
What would go wrong if that wasn't the case? Just occasionally one of these 0
bits that's signified by a short "bloop" for a dot, might get turned into a one
because, part way to Sacramento, suddenly, an electrical storm occurred. And just
hit the telephone wire so what was received at Sacramento was not "doop doop" it was "doop daaang" - like that - a longer
second bit. And the people say: "That's 01, it's sunny in San Francisco!"
No it isn't - it's foggy! So you can see, very quickly, there is no possibility for
recovering from error in these. If you get an error people will receive,
apparently, a good pattern, but it will be for the wrong weather condition. How
could you add something extra to these to give them a bit of protection against
noisy telephone lines? Simplest way - one of the simplest - has been used in
telecommunications - and indeed within computers - for years and years now. You
put in a parity-check bit so here is a code with a check bit. And all I'm going
to do here: I will take every 2-bit code and turn it into a 3-bit code. But
the rule will be that in the overall 3-bit code I must have an even number
of 1 bits. So this is called an "even parity" system. So here we go:
00 there are no 1s in that. So therefore, at the right-hand end here ...
This will add in the parity-check bit and because we're on even parity it's a
0. Viewers of "Numberphile" will have to forgive me - I think there is a video on
the questioning of whether 0 is an even number? I'm sorry, I'm just a computer scientist.
>> Numberphile: People have a delayed reaction people are not sure whether 0 is an even number.
>> DFB: That's even as far as I'm concerned.
OK - how about this one - 01 ?
Well, overall it's got to be even parity which means an even number of 1s. So my
bit I add at the right-hand end is a 1. Equally here for cloudy 1 and 0 there it
is, two of them, 101. Rainy that's easy. There's an even number of 1s already. so I put a 0 at the end.
Now, those codes, with the check bit,
they help a lot in helping to detect whether an error has occurred. Just
suppose that when this 000 was sent it got distorted. Again, an electrical
disturbance just happened to chew up one of the 0 bits, lengthen it, and make it look like
010. If any of these got distorted. A nought turned to a 1, or a 1 turned to a zero, it looks like a valid
different weather state. Here it doesn't. because look at the valid codes: three zeros
011, 101, 110
I sent this and it arrived at the other end as 010. Is this a code that's in this set?
No it isn't. If you try with these, just changing any one of the bits and
flipping it, either a 1 to a 0, or a 0 to a 1 you end up with something that isn't in this
list of good valid codes. You could say "Well, there's bad codes. There's things that don't
correspond to any of these". And of course with three bits: 2 to the power of 3 is 8, so
there's eight possible combinations. What we've done here is split them up into
four good codes, that are meaningful, and four bad ones. But the bad ones give you
a protection against errors in transmission. At your listening station
you hear "010" and you say: "That can't be right!"
What's the simplest thing to do, to try and find out what the weather really is,
because you know that an error has occurred. Well, the simplest thing is to send back
to San Francisco a simple 1-bit message either a nought or a one. You either say
"Acknowledge", in other words "I got it - it's a good code" or "Not Acknowledge". Here I
would send back a "Not Acknowledge" often called a NAK (for "Not Acknowledge")
Send back a 1 bit that says "Not Acknowledge, (it's) garbage" and the sending end
would say: "OK, let's keep it simple, just send it again, 000". And next time you hope it's
going to get through without distortion.
So this is the basis of this system
in that it can detect that a single error has occurred.
The only trouble is that it can't tell you where the error occurred. Just
consider the following: I have got 010 here, by changing the middle 0 into a 1.
But it could have happened that it came from this one via distortion it could
have been that the bit that got distorted was not that one, or that one,
but that one. That trailing 1 bit might have got turned back in into a 0. There's an error but
I don't know whether it came from this one or from this one. So, this kind of code then
can detect one error but it can't correct it. It can tell you where it occurred.
Suppose I had an even noisier line and that in one of these 3-bit codes -- you
hope most of them are going to go through cleanly, you hope that the ones
that aren't clean will have at most one error in them.
What happens if I send 101 and there are two errors in it, not just one? The errors
just so happen that it turns a long blip into a short one, there and there. That
would then give you 000. Two errors.
Oh calamity again! This is received at the receiving station. They say: "Hey!
Fantastic! 000 - it's foggy in San Francisco"
No it isn't! It's cloudy. but it got two errors so it looks like it was foggy.
So, the point here is: it's resilient against one error - they can detect but can't
correct it. But against two errors there isn't resilience. It distorts it into a
good-looking code again.
So for this reason this system is called a "distance 2" code because what it's
saying is: if you flip two bits
it changes into another good code;
if you flip one bit it's discernibly garbage and you can say an error has occurred