Greyscale pictures from interplanetary space were actually sent back from Mars
to Earth from the mid 60s onwards and yeah, I mean, we call these
black-and-white pictures. As you all know by now they're not; they're really
greyscale pictures. The scale used at the time was one of 64 shades, and if I put that
there, black was shade 63 actually, and over here, probably just off the page, is
shade 0 which is white. Interplanetary space - and you're transmitting radio
signals with the shades of grey on - it's a very noisy place! There's X-rays,
gamma rays, cosmic rays generally. There's solar sunspots, flares, everything. The
amount of radio noise is quite considerable. And what this means is that
typically up to 25% of your shade-of-grey pixels, in your photos,
can get corrupted in flight. If you look at these two pictures - that one there is
actually very fuzzy. And then you look at the sky you might think: "Ooh! there's lots
and lots of quasars and tiny stars there!" No - no it's not - it's noise. And if you
compare it with the other one, that's being cleaned up, you can see the contours on
Mars are sharper, the sky is much blacker. So that's the idea then. You've got noisy
photos and noisy greyscale pictures being sent back. How do you correct them
and get them to look really, really good? The early Mariners just did a flyby of
the planets. I think Mariner 3 - unbelievable this - did a flyby and then
transmitted the results back at 8 bits per second, for a 200 x 200 pixel
array. It "only" took 8 hours! Part of the problem, of space being so noisy, is
that you cannot start having [bit rates of] Megabits per second between the planets. In fact
Dr. Bagley, Dr. Steve, was talking to me about this yesterday and saying: "What
bit-rate did they get on Mariner 9 ?" And the answer is 16 kilobits per second.
Also don't forget that, at the time that the Mariner 9 venture took place, roughly
speaking, it took radio signals 9 minutes to get from Earth to Mars. Now
you realize, this is a moveable feast. Because it depends where Earth and Mars
are, relative to one another, in their orbits. I think - I looked up - it can be
anything between 6 minutes and 23 minutes and at Mariner 9 time it was 9 minutes. So the
other thing to say is - to those of you sceptics who say: "Oh! we got a corrupted
picture. Why not send back a signal and ask it to transmit again". Are you joking ?!
you're gonna spend ... y'know, it took 9 minutes to get [it]. You've got 9 minutes to get
a NOT ACKNOWLEDGE signal back to Mars. And then wait another 9 minutes to
hopefully get a better one that doesn't get corrupted? 27 minutes! No, I mean you
can forget any idea of tight interaction with planetary spacecraft. You cannot do
that and this I think does bring it home to those of you say: "Well, if in doubt, just
send it again". No, you can't do that. Here is the real case where you've got to
pack enough check-bits around the message that you can clean it up without
asking for a retransmit. Even when you've got the pictures back and you see all
this corruption you think: "Oh heck! how clever can I be? How am I going to clean
these up?" And let me just remind you, once again, about how you measure payload
vs. correction-bits, and so on, and then I'll reveal to you what ratios
between those were actually used in Mariner 9. [n, k, d] notation. That is total
number of bits per codeword. The codeword is basically saying: "Here is the
package. It's got the message bits in it, packed around with
parity-checking bits, to make sure it gets through OK" And the idea of
this game is to keep the code words as far 'distant' as possible. And by 'distance'
what we're saying is: Take a codeword, take another codeword. Look at how many
places in the bit-patterns are different and that is your 'distance'. And the bigger
you can keep that distance apart the more chance you have that the corruption,
and damage, won't mislead you. >> Sean: It's like you want to send a parcel of eggs somewhere.
It's how much packing you put in isn't it? >> DFB: Yes it is! >> Sean: And physically how far the eggs ...
>> DFB Yes, how far apart are they? Exactly so! And of course the further
apart you put your eggs the bigger the package gets, with lots of fluffy, woolly
stuff in, keeping them apart from one another. Yes, it's it's quite right!
That's exactly what it is. OK, so total bits per codeword is 'n'. 'k' is the [number of] message bits
the payload, the ones that really count. These are the things that are going to
communicate which of your 64 shades of grey that pixel is, And just remember,
because it's sobering, every one of these great long [bit] strings we send is giving you
the colour of one pixel. At Mariner 6 time it was a 200 x 200 grid; by Mariner 9
- you see you make a rod for your own back - it had gone up to 700 x 832.
Not, perhaps, quite as good as modern video screens. But, you know, we're getting there.
So, back to this then: 'd' is that distance I was telling you about. The people at Jet
Propulsion Laboratory (JPL) have got a lot of really, really good communications
engineers who are also coding theorists. And what they came up with [was] a code to
answer all of these conflicting claims, was one where the overall message length
is 32 bits. Packed inside that is a 6-bit message, carefully hidden and carefully
protected. And the 'distance' is amazing It's 16. For those of you still
with us, who aren't computer scientists, the reason we've got 6 here is that 2 to the
power 6: 2 x 2 x 2 x 2 - 6 times over, is the magic 64. Which we number from 0 to
63 because we're computer scientists and everything starts at zero. This distance
will give you a figure [for] "number of correctable errors." Remember this is 'd' and
here's my little bit of mathematical notation "floor ( d -1 ) / 2".
What does 'floor' mean? I'll tell you in a minute. But let's work out the
little formula in the middle. My 'd' value is 16. OK, so on this occasion I'm
finding the floor of 15/2. 15 / 2 = 7.5. 'floor of' means if you've got a decimal
part to your number in there, then round everything down. It doesn't matter even
if it's 7.8, it would round down. So 'floor' means 'round down'; 'ceiling' is forcibly
rounding up. What we're doing [is] 'floor' here. floor(7.5) is 7. So this is [an] amazing
performance actually. What it's saying is that in these 32-bit packages you can
have up to 7 bits go wrong. There you are, you see its 25%.
The reason they chose this was they knew that, roughly speaking, you could get up
to 25% errors [in a codeword] depending on whether it was a good day or a bad day
for cosmic rays. at the moment, you know! But this really worked well, 32 bits!
We're in the 1960s. Older viewers will know- heaven sent - that fits into an IBM
mainframe word. Because powerful computers in those days - really expensive
ones and even the newly emerging DEC [VAX] mini-mainframes had 32 bits. I mean it's old
hat now. Everything 32-bits being phased out in favour of 64 [bits]. But this fitted so
well. You'd got a 32-bit package six of those hidden bits in there carrying the
message - up to 7 correctable errors inside here. And this particular code is
very famous because it had been proposed way, way back before the Mariner
program, in the 1950s, as a good way of getting lots of error-correction going
inside a transmitted packet. Oh! and by the way, even on Mariners, you know, the
camera could gather information faster than it could ever be transmitted. So the
Mariners had a little tape recorder on board and they tape recorded the scan of
the picture and then trickled it out, overnight, at 16 kilobits per sec. Well,
"overnight"- "over earth night" presumably. So it's been a story that's gone on now for
the best part of 50 more years. And I think this is a good place to stop but some
of you, I know, will want to follow up saying: "Show me how the Reed-Muller code
words because I want to do it for myself. [trailer for next video] 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!