Well, today is hardcore Coding Theory, relatively speaking. It's still "64 shades
of Grey" for those of you looking for the sequel. And remember, the sequel is always
better than the original thing! >> Sean: Is this "50 shades Darker then? "64 Shades Darker ?" >> DFB: Yeah! "64 Shades Darker!"
To send pictures back from Mariner 9 a Reed-Muller code was used and Irving
Reed is a very famous coding theorist. And this worked incredibly well; they [JPL]
were ever so pleased about the results they got from this. The nice thing about
it from the theory point of view is that if you want to go all mathematical and say:
"It's a multi-variable polynomial blah blah... y' know ..." You can do that. Because it is. But I
can disguise that for you with Reed-Muller and I can say: "Look everyone, trust
me. It's just an exercise in recursion that we're all familiar with". And you've
got to be prepared to do concatenation of bit strings which I think in North
America and Canada is called bit fiddling, but here in the UK we call it
bit twiddling. Bit twiddling? Fiddling? We don't mind which. Recursion and bit
twiddling is all we need to understand how those pictures were sent. But because
it's a recursive procedure it takes us almost on a sort of magical mystery tour
of everything we've ever done about codes. Because as you build up to
something usable - in terms of lots of error correction - you meet lots of other,
almost familiar, friends on the way. The [n, k, d] notation is what we're going to use.
This comes from a previous video where we qualitatively took a look at pictures
from Mars and how they were sent. But, of course, we're now getting down to
hard-core details involving recursion and bit twiddling. But, just for revision, the
total number of bits in what you're sending. including payload bits [i.e. message
bits] and the parity check bits, that's 'n'. Within that, how many bits are devoted to
the message itself, 'k'. What's your distance? And the bigger that number is the more
errors you can correct. So the correctable errors is your distance,
here minus 1, divided by 2, and take the "floor of" The thing that we are headed for at the end
of our recursion is 32 bits total, 6 bits of message. 16 is the distance. This
magic code, when we've got there, will actually correct up to 7 wrong bits
in 32. And, I mean, some of you will be saying: "Why couldn't you do this earlier?!" The answer
is: "It's a trade-off". The trade-off is [that] we've only got six payload bits, whereas
with things like Hamming codes it would have been more like 26. You pay your
money and you make your choice! OK, well how do we do this recursion then? How does it
develop? Every recursion has to have a sort of bottom point where it finishes.
You know, factorial(0) is 1. That sort of thing. Well, here we're going to develop
the ... [what are] known in some textbooks as the H_n codes. And the reason for that is that
they are actually derived from things called Hadamard matrices. There's lots
of ways of getting at these Reed-Muller codes. But the fact that there is a
Hadamard matrix method of getting at it is good news for us. Because what
it means is you can do it recursively and, as computer scientists, we're all
totally and completely happy with recursion, I know we are. The zeroth one of
these codes, the very simplest, is just so simple it's laughable, just the single
bit "1". But every good recursion has got to have an algorithm for how you get
from this one, to the previous one, to the next one and so on. The rule for
constructing - shall we call it H_n - is at every stage you take 2^(n-1) 0s
and 2^(n-1) 1s So, in other words, you get a bunch of
zeros and a bunch of ones - joined together by concatenation. Plus, at every stage of the
recursion, you do 2-fold repetitions of previous
patterns, from the previous version of the recursion. It's one of these things
where it's actually ... let's start doing it and then I'll keep cross-referring here and
you'll get the hang. H_0 is 1. That's god-given, you can't contest that. That's
the bottom. OK then, so what about H_1 ? Well, what this is saying is that for H_1
our 'n' value is 1. So we're going to have to put in a pattern, here, that is
2^(n-1) 0s. Well 'n' is 1. That's 2 ^ (1 - 1).
2 ^ 0. But anything to the power 0 is 1. So you start off with one 0 and one 1 [i.e. 01]
OK but the rule says ... and as well as that your working set - this is called
your *basis set* of things you're building up - your working set must also include a
two-fold repetition of the things you had previously. Well the only thing I had
previously was a 1. So what's a two-fold repetition of 1? [It's] 11. It's all to do
with *concatenation*. We're not, at the moment, doing any arithmetic or XORs.
We're just joining bit patterns together. So here we are then, it's 11. Now a rule
here - which is a quite general thing in developing these codes - is you can always
introduce a 0 vector, as it's called. If I keep calling these things *vectors* don't
worry. It's a very "in" phrase - you can bandy it around in the pub. But all it
really means is 'bit strings'. You can always introduce a zero vector of order 'n'.
What that means is - absolutely for free and from nowhere - I can add to this 00.
OK? And if I was working with bit strings, as we will eventually be, that are
4 bits long, I can just bring in four 0s. It's bound to be there. The zero vector, at
whatever length, is always part of your set of codewords. That's fine. So you can
look at this now and say "You know, you've almost got a valid code there, haven't you, in 2 bits?"
Look you've got 01, 11. And you say that absolutely for
free i can have 00? Do you know if you just added 10 in there, you'd have a complete
set of 4-bit possibilities wouldn't you? Yes and here is a lovely way to
introduce you to what I blather on about from some time- it's called a *linear code*.
It means, if you add these things together with XOR they'll
deliver something else in the same family. Well, look, there's only one thing
we're missing in this family of 4-bit possibilities. So if I do 01 - and I'll
indicate my XOR, "binary addition without carry", with that + [within a circle], what happens
if you add 01 to 11? Well 1 + 0 is 1, because they differ, 1 + 1 is 0 because
they're the same. Hurrah! that has delivered me my final possibility of 10. So what
we're saying is: at every level of this recursion you take what's called your
basis vectors, that come from this recursive algorithm, lots of zeros, lots
of ones, plus double-ups of what you had last time. You do all of those but then
you add together what you've got in all possible combinations. And you know that
they'll form a closed family. You'll get to a stage where they won't deliver
anything different. They just rattle around within themselves. Now look at
this fabulous code, Sean! It's so familiar to us isn't it? But it's not very
exciting because in [n, k, d] terms what are we saying that this is? It's got a
2-bit code but the payload is 2 bits long. There is no space for any error
correction, and if there's no space for any error correction whatsoever, then
they must be distance 1 apart. They all differ by one bit as you go from zero
through to 4. >> Sean: I have to confess to being completely lost at this moment!
I understood what you said but I don't see how it has a bearing on where we're going.
>> DFB: It will! Next time around, believe me, this will have such a bearing as you can't imagine.
What I'm saying is, in the trivial case this doesn't give us an
error-correcting code at all so it's useless. But we recur one more time!
I might need your help here. H_2. Oh crumbs! You need 2 ^ (n - 1) 0s
and 2^(n-1) 1s. So that's always the new thing - introduced every time, yeah?
It's 2 ^ 1, which is 2. So you need two 0s and two 1s, plus two-fold
repetitions ... now I did derive that, but that wasn't part of the basis set.
Two-fold repetitions of what you had last time. Well, 0101 and 1111.
Don't worry about the zeros. You can always add those in at this stage. If we want to add
in a four 0s vector we can do so at whatever stage we want. >> Sean: So that's just
like you can have a code of nothing? >> DFB: Yeah, it's a bit like, you know, when
you're doing arithmetic systems you find zeros are useful. But it really is like
saying 5 + 0 = 5. all right? But, of course, with XOR systems it's
handy to have it because if you accidentally XOR something with
itself, because they're identical, it will yield a bunch of zeros for you. So it's handy
to have that there, as a kind of check that it didn't just arise from outer
space. It could have arisen from adding two things together that were absolutely
identical. These are what's called *basis vectors* for the vector space and
they're 4 bits long. But from these you can generate all of the 4-bit
possibilities you're after by simply adding - either taking them as they come or
adding them together with XOR. And I'll show this now on this sheet
which I'll carefully introduce over here. I've introduced a 4-bit 0 vector which
sometimes is called 'bold 0'. That is the 0 vector of whatever length you need.
Remember the x_1 we got? Two 0s and two 1s? Fine. x_2: 0101 ; x_3: 1111. Those are the three we
started with. Now add them together in all possible combinations until you
don't get anything new. And I mean XOR of course. x_1 + x_2 = 0110
x_1 + x_ 3 = 1100. How about x_2 + x_3? 1010. And finally the final
possible combination is all three of them. And of course you
know it doesn't matter what order you do these XORs in: x_1 + x_2 + x_3
is the same as x_3 + x_1 + x_2. You do all that one and you get 1001.
Now when you look here, look, [counting] 1, 2, 3, 4, 5, 6, 7, 8.
You've generated 8 possibilities out of all the 16
possibilities in 4 bits. What I'm saying to you is, you take any two of
those now, and add them together again. You won't get anything new. If I take 1010 [+]
1100. Do an XOR on those. I'll get 0110. There it is look, just above.
Try it with any of those and you won't get anything new. The other thing I'd
point out to you, here, is what is the minimum distance of this code? Well, look
0011 how distant is that from 0000? Two. Yeah, the only exception is if
you take the zero vector with the vector that's all 1s. you will get a much
bigger distance - you'll get 4. But you're not worried about the maximum [distance] one.
You're worried about the [minimum distance] one. So this thing, then, it's not exactly
award-winning but it's a step on the way. We've now got something - let me use my
crib-sheet and write down for you. H_2 is a [4, 3, 2] code. And you look at that and
you say: "Well, that's a bit better than last time where we didn't do any error correction"t
But we all know, from previous videos, if the thing's only got a distance of 2 you
can't correct an error, you can only detect it. And when you look back at
this set of possible codewords, we've seen that it's actually carrying a
3-bit payload with one parity check bit at the end of it. And overall it's always
even parity. Yes, but we're on our way! We can now fast forward and say: "What about H_3?"
What we're going to develop from here is basically a set of 16 8-bit
possibilities and if you sort of say "Well this is H_3, what is its [n, k, d] rating?
It's an [8, 4, 4] code. We're coming on!
We're getting a bit of error correction at last! Now. In this recursive build up. Aren't we?r
4 - 1 Sean? 3. 3 / 2 = 1.5 round down to 1 It can correct one error. It's getting up
to Hamming code standards this is! We're up to [8, 4, 4] for this H_3 code.
But probably the most equivalent Hamming code I could pluck out for you is [7, 4, 3].
A perfect illustration of trade-off. Look, that will only correct one error but it's got a
payload of four bits. That's [also] got a payload of four bits and this is pretty comparable.
>> Sean: How far do you have to go with this before you get ... >> DFB: well we've done H_3
and you've got to get to H_5. We will draw a veil over H_4 completely. I will leave
you to read the handout and work out the basis vectors and do it all for yourself.
Or, if you can't be bothered to, you can use my 'awk' program which has got an option
in to generate it. Let me just say H_4 has a [n, k, d] rating of [16, 5, 8] and that's very nice
Look at that: 8 - 1 = 7; 7/2 = 3.5; Round it down. It could correct
three errors in a 16-bit codeword. This is looking good. But those clever engineers
at JPL, and elsewhere, said: "Oh!! if we went one stage further we could do even
better". H_5, this is our target. [32, 6, 16]. Notice what's happening is that at every
stage of these Hadamard / Reed-Muller codes the size - the length of them.
It's exponential; it's doubling. It's gone 2, 4, 8, 16, 32 The next one will be 64. So they are expanding at
a heck of a rate. And as some sardonic person has once said, in the Comments on these:
"The trouble with extending these codes is [that] it only gives the cosmic rays more
chance to damage them" And that's quite true, So this is a fabulous compromise as
you can see now. I hope you've all by now seen the
previous video, with the pictures from Mars. If not you can always go and
consult it but this was just about perfect - you get a 6-bit payload packed
inside 32. And with a lot of hard work, at the Jet Propulsion Laboratory, you can
deterministically decode every one of these vectors to get its shade of grey
out of it - so long as it's not being hit by more than 7 errors. You might have
a big decoding effort to do this quickly enough because it can very easily mount up,
but that's solved the problem for you. Mission Accomplished, really, I think, this.
It solves all our error correcting desires for this particular level of
technology that happened in the Mariner 9. It was always counted a great success
Of course, things have moved on from there a lot, since that date.
[Trailer for EXTRA BITS] We've used secure shell [ssh] to bridge across to something I'm more familiar with: Open
SuSse Linux. And i think I can't remember in the previous ....