Reed Solomon Encoding - Computerphile

we're going to talk about going from Galois fields to reed-solomon codes we must be mad sure really I mean so many of you have said just do reed-solomon you know you've done Hamming codes they can't be that much more complex oh yes they can the stuff we have done earlier done a fair bit on Hamming codes which if you remember a basically going to correct a single 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 one one for sunny or something like that but in order to protect those bits against a one bit damage i had to add no fewer than three extra bits i had to mean into a 5-bit code but it was okay because checking up whether it had been damaged was easy it was a simple parity check it was vector lee saying look here's the three 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 one another one says zero but this bit I don't know but it's got to be even parity overall so I only got a single one and A zero I need another one 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 fifties early sixties the next phase of this or this big jump forward would want to do by read and Solomon was 10 years later it was late sixties early seventies oh and big surprise were read and Solomon at Bell Labs know for a change everybody else seemed to be at Bell Labs read and Solomon where I think MIT 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 where a code word because string of bits and some of those are information bits and interleaved with them or parked at the right and then 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 has not been a single bit but a column of bits let's say it's an 8 bit column if you're doing something like reach Holloman correction on in a CD context you know how big is the bucket size of these columns I think it's something like 40 otter bits but then even that couldn't cope they had like two layers of reed-solomon encoding what 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 okay 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 that every symbol is composing 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 why depart 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 in music now if they've 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 bit errors within the symbol but just the symbol itself something's wrong with it right you then might stand the chance if you've got again parity check symbols at the far right-hand end not 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 checks symbols at the end are nonzero you're getting three five twelve fifteen what does that mean well the answer is you lots and lots of detective work by the way those symbols that you put on the far right hand end revel in the name syndrome which i think is a wonderful word and my first thought was what on earth of pure mathematicians or communications engineers do with syndromes their medical on there 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 something I think we Ambar syndrome is ER I don't know what it is but I'm no doubt it'll 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 calls multiple bytes whatever but right at the end is now a checksum from how you have got a syndrome a set of remained as 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 ego his and the answer is by using Gao our 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 how 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 love this because your beloved two comes into the real world because were you say four and I say don't think of it as two times two think of it as two to the power of two 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 two and say you want to use my methods here's rule number one everything must be done modulo two not modulo your big number like 256 that's different modulo 2 so for addition what do we know about addition modulo 2 from Bletchley Park Shawn what the mathematical mathematical magicians call addition modulo 2 this is exclusive or 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 division 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 1 that's a lot of equation solving for those of you into these things it's like solving lots of simultaneous equations saying the only logical solution to this damage is it absolutely must be column 3 and column 17 that's where the damage has come does that syndrome always work back to getting your precisely one answer yes it's just a 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 similar types of questions so 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 Shawn and I were in the early eighties thinking this error correction 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 to solve your syndrome Asians nope what's the answer you shaky head anything 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 Riesling schemes lenses are very nicely indeed two things that computer engineers love like shift registers and all sorts of Hardware specials with all the possible three bit combinations but I carefully arranged so that the three zeros which I'm now using for at three ones as knack I put them at the diametrically opposite corners of the queue and what is magic about doing that

Channel: Computerphile

Views: 128,348

Keywords: computers, computerphile, computer, science, Computer Science, University of Nottingham, Professor Brailsford, Reed, Solomon, Reed Solomon

Id: fBRMaEAFLE0

Length: 11min 56sec (716 seconds)

Published: Wed Feb 20 2019