We must be mad, Sean. Really, I mean, so many of you have said: "Just do Reed-Solomon,

y' know. You've done Hamming codes. They [Reed-Solomon] can't be that much more complex?" Oh yes they can!

The stuff we have done earlier - and we've done a fair bit on Hamming codes, which if you

remember are basically going to correct a ... put right a single error. That all

happened in the 1960s. And in two of the videos out there, which we'll put the

links out for you, I did a thing called Multi-Dimensional Error Correction where

I had two bits of information (which was a San Francisco state of weather). So

there was two bits for the state of the weather, like I think it was '11' for "sunny",

or something like that. But in order to protect those bits against a

1-bit damage, I had to add no fewer than 3 extra bits. I had to make it into

a 5-bit code. But it was OK, because checking up whether it had been damaged

was easy. It was a simple parity check. It was effectively saying : "Look, here's the

3 parity-check bits at the end". I've made the rule that overall it must be

even parity. I know that one of them says '1' Another one says '0' but this [third] bit I

don't know. But it's got to be even parity overall so if I've only got a single

'1'and a '0', I need another '1' to make that grouping be even parity.

Now that's the easy error correction. How did it advance from that? What changed?

Well, we're talking about 10 years hence. I mean Richard Hamming was very definitely

late '50s / early '60s. The next phase of this or, this "big jump forward"

thst we would want to do, was by Reed and Solomon [and] was 10 years later. It was late '60s / early '70s.

O!h and big surprise: Were Reed and

Solomon at Bell Labs ?! No! For a change. Everybody else seemed to be at Bell Labs

[but] Reed and Solomon were, I think, at MIT's Lincoln Laboratory. But there

was a realization that if you wanted more powerful error correction there

were several things you could do but, the more they looked into it, the more they

found themselves having to learn about Pure Mathematics concepts called Galois

Fields. And this is finite field arithmetic where you've got to be able

to find a multiplicative and an additive inverse. We've tried to prepare you for

this by doing ISBN book codes, which is a very simple manifestation of those two

things. We thought in our early things [i.e. videos] where a code word became a string of bits.

And some of those are information bits. And interleaved with them, or parked at

the right-hand end very often, were parity check bits. What we're now going

to try and do is instead of just having one great long string of bits, linearly,

we're going to try and make it be almost two-dimensional. Think of every one of

these positions in your code-word now as not being a single bit but a column

of bits. Let's say it's an 8 bit column. If you're doing something like Reed-Solomon

correction in a CD context, y'know, how big is the bucket size of

these columns? I think it's something like 40-odd bits but then even that

couldn't cope. They had, like, two layers of Reed-Solomon encoding - one backing up

the other. So, if you like, the filling up of these things, instead of linearly

going like that - and then at the very far end you put a few parity check bits - what

we now do is we declare that every one of these positions isn't a *bit* position

it's a *symbol* position but a symbol can be multiple bits, OK? For the sake of

argument let's say it's an 8-bit symbol, a byte. The way they get filled up is the

bit stream comes in and it fills up a column of 8, and then it fills up a next

column 8 and a next column of 8. So it's almost like we've got a 2-dimensional

array of bits - and symbols in that direction-

but every symbol is composed of 'n' bits, as it goes along. What's the advantage of

doing that? Well, you can see one advantage, when you think about it,

straight away. Hamming codes, for example, the old way, tended to presume you've got

the occasional error, now and then, wide apart. What this is anticipating - if you

can fill up symbol positions - is you might get 'burst errors'. Yeah, you might

get - here we go - bits coming off a CD, trying to play your music.

It's encoded music. Now, if they're filling up a bucket in a column,

in some sense, and then moving on to the next one

there is just a chance that a localized scratch will get all its 'bit-clobbering'

over and done with, within two symbols shall we say. So, we know that we can

devise codes that will can detect and potentially correct a certain number of

errors but if we can make it so that those errors are not [only] bit errors within

the symbol but just the symbol itself ... something's wrong with it! Right?

You then might stand a chance if you've got, again, parity-check *symbols* at

the far right-hand end - not [just] parity-check bits, if they've got enough information

in them, you might be able to say: "Something went wrong. I got a burst error

there, as a scratch on that CD. Can I put it right?" Yes, but it's not going to be

simple-minded parity checking; it's gonna be serious hardcore stuff. Because those

check symbols at the end will normally be arranged so that if the information

is correct and nothing's got damaged there'll be zeros. If something gets

damaged, the first thing you know about it is that the parity-check symbols at

the end are nonzero. You're getting [perhaps] 3, 5, 12, 15. What does that mean?

well the answer is using lots and lots of detective work - by the

way those symbols that you put on the far right-hand end - revel in the name of

"syndrome", which i think is a wonderful word. And my first thought was what on

earth are pure mathematicians, or communications engineers, doing with

syndromes? They're medical aren' they?! Well, I looked up in the dictionary and as far

as I can make out it all makes sense. If you have a certain syndrome it means you

are exhibiting symptoms of an underlying problem

So the grouping of symptoms that's caused by an underlying problem is often

called a syndrome. [There's] something like the Guillain-Barre syndrome isn't there? I don't know what

it is but I'm no doubt you'll all put me right on that. But you can see it makes

sense. The signal that something has gone wrong is you get all of these

information bytes or even bigger columns, multiple bytes, whatever. But right at the

end is now a "checksum from hell". You have got a syndrome a set of remainders if

you like, that are not zeros. Given only that information, how can you work

backwards and find out which of these columns got hit and where in the column

it got hit? And the answer is: By using Galois Field theory over finite fields and

doing lots and lots of long divisions and additions. So, the bottom line is that

for this work and particularly if you're using, as we are of course now, powers of

two, Galois said: "I can liberate you from it having to be primes all the time,

I can do powers of primes. And for all of you future computer scientists that I'm

not even aware of, you'll love this because your beloved 2 comes into the real

world because where you say '4' and I say: Don't think of it as 2 x 2

Think of it as 2 ^ 2." And so he said: "Yeah, I can do powers of

any prime, including two, but what he didn't say is: Here are the rules

if you you light on 2 and say you want to use my methods, here's rule number 1.

Everything must be done modulo 2 Not modulo your bigger number - like 256 -

that's different. Modulo 2. So, for addition what do we know

about addition modulo 2, from Bletchley Park Sean? What do the

mathematical logicians call 'addition modulo 2' ? >> Sean: This is exclusive OR

>> DFB: It's Exclusive OR! So, no sweat for computer scientists. All our additions of these

numbers, represented in bytes or whatever, are going to be done

with Exclusive OR. Worse still - as we found out in the ISBN previous example -

you've got to be able to find multiplicative inverses. And that's going

to lead us into doing long divisions modulo 2 in a Galois Finite Field. Now

that is a bit hair-raising but not too terrifying. But if you're prepared in the

end to do all of that work then fine. You can use your 'syndrome' and analyze

it to tell you where the errors went. That's a lot of equation solving. For those of

you into these things it's like solving lots of simultaneous equations saying [for example]:

"The only logical solution to this damage is it absolutely must be column 3 and

column 13. That's where the damage has come. Does that syndrome always work back

to getting your precisely one answer? Yes - it's just magic the way that this

error correction works but it is complex because the brute force way to do it is

to get a set of simultaneous equations and - some of you will know this - get lots

of simultaneous equations to solve you use 'matrix inversion'. That is computationally

a very heavy undertaking. And so you're looking all the time for simplifications

because, if you don't, you're sitting there, like Sean and I were in the early

'80s, thinking: " ... this error correction [for CDs] this is in real time! How is this thing

solving sets of matrix equations in real time to make sure I can listen to this

CD without hearing the scratches? Where's our supercomputer free with every CD - a

Cray XMP [in those days] - to solve your syndrome equations? Nope! what's the answer? You shake

head and think: it's those hardware types! It's custom

hardware! Yes, custom hardware can fairly easily attain supercomputer capabilities

so long as it's in a tightly defined field. And it turns out, thank heavens,

that error correction in Reed-Solomon schemes lends itself very nicely indeed

to things that computer engineers love like "shift registers" [and pipelining] and all sorts of

hardware 'specials'.