Reed Solomon Encoding - Computerphile

A high level look at Reed Solomon - Professor Brailsford explains the basics of this complicated encoding technique.
Multi Dimension Error Correction: • Multiple Dimension Err...
Teeny Extra Bit: • EXTRA BITS: Reed Solom...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@BuysDB]

Now I still don't know how it works :'(

[@Izzy88izzy]

"Checksum from hell" is the sickest math-rock band name out there

[@grn1]

All of their music would be Rockstar programs (look up Rockstar programming language).

[@kayakMike1000]

Implemented In Hardware...

[@cybercat1531]

I learned about Reed Solomon Encoding a long time ago at University and used it several times since then in some code. But really Professor Brailsford's explanation so far is one of the best, he truly has a unique way of explaining things. Even better when it's put together with those graphics. I particularly appreciate the historical context he gives, really sells the story.

[@cybercat1531]

Also neat Moiré pattern from the shirt.

[@wimjongman]

Thank you. Very interesting.

[@trifalgarh]

Could you share your code if possible? Would be super helpful ^.^

[@Mefistofy]

This is an absolute fun introduction into RS codes. Had to learn it for a course at my university and I had to grin at some of his explanations.

[@kayakMike1000]

I learned the basics of Galois finite field arithmetic from the Rijndael algorithm.

[@MrDaanjanssen]

5:56 "Yes, but..." *dramatic zoom in*

[@MathematicsOptimization]

**vsauce pops into the image from down bellow**

[@DrGreenGiant]

@@MathematicsOptimization not watched him in years!!! So true though. That's tonight's viewing sorted lol

[@dmsanct]

"so how can CD's continue to work afterr they've been scratched?" me: oh boy, you're in for a treat. So it was late 50's and there was this guy called Richard Hamming

[@sabyasachichoudhury2920]

Who was annoyed at the punch code machine not working

[@bborkzilla]

Good old Évariste Galois. Came up with all his amazing mathematical theories by the age of 20, at which point he got himself killed in a duel.

[@willsi]

Man's a treasure. Always enjoy it, Professor.

[@joshuagarrett4879]

I would enjoy listening to him even if he was reading children's books.

[@kayakMike1000]

Indeed. I am glad he's immortalized on the web. Imagine if we had more stuff from Feynman or so.

[@mishasawangwan6652]

this guy and his encoding videos, as well as that one dude who does all the encryption videos (sorry name escapes me at the moment) are the best types of computerphile vids, hands down

[@DrGreenGiant]

Yet another awesome video from David and produced so well. Great job again computerphile. I can see this leading sweetly onto 2D barcodes!

[@LucasHartmann]

DVDisaster is a piece of software that auguments empty DVD-iso space with error correction codes. I tested it working by intentionally scratching a disk, and it saved me quite a few times later. Awesome extra protection for backup disks.

[@ZeroUltimax]

When starting my degree in CS, I got interested in QR codes and their uses of Reed Solomon Encoding. It was the first time I went "Nope" so hard. This bring back nightmares.

[@davidmcgill1000]

Gah that's where I recognize that name from. Thanks. Was bugging me when I saw the video title.

[@Dawwwg]

When i studied CS back in the late 90s, they actually lectured it...

[@mastodans]

Thank you, professor Brailsford. This is wonderful storytelling.

[@dannyboy42223]

Was waiting for this video after the previous error correction video. Thanks for this!

[@ArumesYT]

In the 60's MIT was already deeply involved in computer tech, as was Berkeley. I think CalTech was only a couple of years behind those two as well. And Silicon Valley (although not known by that name yet) was already becoming a distinct high-tech area. Remember one of SV's most legendary companies, Fairchild Semiconductor, was already founded in 1957. So no, certainly not everybody was at Bell Labs anymore by then.

[@skilletpan5674]

Transistors etc date back along way as well. World war 2 both advanced and stopped development of Computers. (The Japanese invented the transistor just before the war (I can't find an article on this. I maybe incorrect. It may have been the Germans and Americans in about 1947 and 1948) but it was shelved and not further researched/found again until after/later due to budget and economic reasons due to the war). Electronic calculators where obviously worth developing further as IBM and various government departments (not just directly military) put lots of time and money into developing them during and after the 2nd world war. Alan turning and the other code breakers showed the development of computers would be inevitable and invaluable for governments and large companies. This stuff was a forgone conclusion by the 50s. There was just too many applications that electronic computers where helping with at universities. Professors and universities love "new fields" as well. It's nice to have justification for jobs and research grants.

[@johnfrancisdoe1563]

skillet pan The FET transistor (later evolved into MOSFET etc.) was theoretically invented in the 1930s, but no one could get it to work until much later. In the mean time, some of the people trying invented the bipolar transistor (PNP and NPN), which thus became commercially available first. While FET transistors can be readily substituted into circuits designed around vacuum tubes, bipolar transistors required new and different designs.

[@Earthcomputer]

Main thing I learnt from this is the definition of "syndrome" lol

[@PyPylia]

I am both surprised and not surprised that you are here.

[@zohnannor]

hello, seed founder

[@PyPylia]

@@zohnannor *finder

[@zohnannor]

@@PyPylia yeah, typo

[@iabervon]

Yay! It's the video I was asking for! 4-bit symbols aren't too bad, because your times table is only 256 symbols, with a 15-symbol 1/n table. The thing you didn't mention is that the long division is long division of polynomials, although that's kind of a weird math hack, because you never evaluate the polynomial for a value of x, so it's effectively just multi-digit numbers where the digits don't overflow or carry into each other. I like to say that GF(2^n) is arithmetic for people who can't count to 10, but can multiply by 2 repeatedly to 10.

[@BoydWaters]

This seriously helps me, even after 35 years I have been arguing with computers. "Checksum from Hell" :-)

[@danijones1797]

How have I never seen your videos before?. I love your explanations, what a wonderful teacher

[@CoolJosh3k]

I recognise Reed-Solomon due to my use of that for archival recovery records. I also notice how long it takes for a few GBs on an i7 8086k.

[@vjeraturk]

Please enable auto-generated English subtitles on your videos. It is easier for me ( non-native English speaker) to follow what someone is saying if I see it written on screen, even if it is just an approximation. Your channel is the best!

[@ct92404]

Professor Brailsford! Yay!!

[@SpringDivers]

The No. 1 ESS Program Store and Central Control used hardware hamming and parity to check and correct single errors. This was preformed on every program store read. I believe other ESS variants using magnetic card technology used similar techniques. Thanks for the video.

[@theharbingerofconflation]

For reference, you're talking about the Electronic Switching System from Bell Systems, the first large scale automated telephone control system?

[@lawrencedoliveiro9104]

5:19 Isn’t this also where the “CIRC” (“Cross-Interleave Redundancy Checking”) comes in? The bits are arranged in a pseudorandom scrambled pattern (which is unscrambled as part of the decoding process), so that any contiguous run of errors on the disc is spread across a larger area after unscrambling and affects a smaller proportion of bits within that area.

[@DaveFlash]

yes, it is indeed, also, no mention to the simultaneous 8to14 modulation that also happens in those clever little Dutch Audio CD's. bit sad at that...

[@theslimeylimey]

Fascinating and very well presented for us non-computer science people.

[@Crazytesseract]

It is pure mathematics.

[@sonicthehedgehog5088]

Finally, I was waiting for this video, but it's too bad Brailsford didn't give an actual encoding example. The encoding part of Reed-Solomon isn't that difficult once you know how Galois field arithmetic works, decoding however, is *much* more difficult.

[@profdaveb6384]

Your requested "actual encoding example" will be coming in future video(s)

[@lawrencedoliveiro9104]

@@profdaveb6384 Just don’t go taking part in any duels until then. ;)

[@MyTBrain]

Great talk about Reed-Solomon! Now I see its linear nature. What about non-linear error correction? Has that started getting any traction?

[@rayredondo8160]

How about another collaboration with 3b1b? He's been covering error correction a lot lately, and it'd be cool for him to feature again.

[@slpk]

I've never heard of such hardware but I'm sure they're everywhere. Therefore, another video!

[@Shlooomth]

“We’ve tried to prepare you for this” 😂 😂 I know right😂 ❤️

[@SardarNL]

All videos of Computerphile are brilliant. However, this one has a misleading title. There is literally almost no information on Reed Solomon encoding, only emotional opinion on how complicated it is. A little example would help. Or a title like "Before your consider implementing Reed Solomon encoding...".

[@31dariant]

well, to be fair the title doesn't say "Reed Solomon encoding EXPLAINED" or something, for all we know, the title only implies this video is ABOUT Reed Solomon encoding, which it is. so i wouldn't say it's misleading per se. it is, maybe, below your (and maybe many more) expectation. as in another computerphile video, they always explained the subject and even give some clear example. so you expect nothing less for this video. but as the prof. said, it will be complicated to explain and even give example for Reed Solomon encoding in this (relatively) short video format. i'm sure there are someone out there who (not only) "discuss" ReedSolomon Encoding but also explain in depth about how its work and a precise example of that. but i'm sure it wouldn't be 11ish minute long

[@bradburyrobinson]

Brailsford, Bagley, Pound...I'm watching.

[@chaoslab]

Such a lovely chap!

[@NeilRoy]

[@ahmidahmid9303]

even i don't understand the subject i like your videos Prof

[@adamcunningham8248]

This is brilliant!

[@coolcat23]

Boy, oh boy. What an astonishing amount of hand waving. I know about Hamming and BCH codes and was none the wiser after listening to this stream of diffuse metaphors.

[@chrish9506]

This is a nice find!

[@AntonioBarba_TheKaneB]

just a few minutes ago I downloaded a paper about Reed Solomon encoding in JT65. Now I saw a new video on the subject on Computerphile.... creepy coincidence :O

[@0707andy]

Could we maybe get a video on numerical methods?

[@cgraider]

great, i wish for more details ...

[@erwinmulder1338]

*sees Professor Brailsford, presses play* Yes, I'm a simple man.

[@monolyth421]

I'm a computer engineer, I love shift registers.

[@user-vn7ce5ig1z]

11:00 Yup. Gotta love those ASICs. 👍 7:11 Guillain-Barré /gee-on bar-ay/ is a (still mysterious) autoimmune disorder where the immune system attacks the peripheral nervous system. A common result is demyelination which (like stripping insulation from wires), which causes "short-circuits" (leading to spasms, seizures, etc.), as well signal attenuation (nerve impulses don't reach their destinations). (Most people these days probably know it best as one of the go-to diagnoses, along with Lupus, that they would guess on _House MD_ .)

[@slpk]

I don't think he' is talking about ASICs. Is he?

[@KnakuanaRka]

Funny, I could swear people said it as geeahn-barr.

[@GrayBlood1331]

3:48 will this be included on "The Very Best of Professor Brailsford"? ;)

[@RocketLR]

amazing.

For some reason I got the feeling that RAID technologies may be coming up while watching this. 🙂 Also, I would have loved to see some more equations. You don't have to talk about them, but show them at least so those of us who do have a relevant background can get a better grip of things.

[@johnfrancisdoe1563]

Mikkel Højbak RAID1 is simply a second copy, then using read errors to decide when to use that other copy. RAID4 and RAID5 is adding a single XOR parity bit and again using read errors to decide when to reconstruct a block by XORing the blocks from the other disks. RAID6 uses a 2 bit Hamming code while still using read errors to decide which blocks need to be reconstructed from the others. I don't think any of the practical RAID levels use RS codes.

[@StevePinkham]

@@johnfrancisdoe1563 Linux uses Reed Solomon for RAID 6, and ZFS uses it for RAID Z2 and RAID Z3. Not familiar with other implementions, but that's two pretty important projects using it anyway.

[@rcgldr]

@@StevePinkham - RAID 6 implementations vary. Some use XOR for one of the parities, and BCH view Reed Solomon syndromes (as opposed to parities) for the other parity. This approach simplifies recovery.

[@Richardincancale]

LDPC next please!

[@lasersimonjohnson]

You had me at...Prof Brailsford..

[@rcgldr]

The symbols appended to a messages are called "parities". Syndromes are not part of an encoded message, but instead calculated based on a message with appended parities, and used to detect and/or correct errors. To correct errors, instead of matrix inversion, Berlekamp-Massey (1969) or Sugiyama's extended Euclid algorithm (1975) are more efficient, and used by CD's, tape drives, hard drives, ... .

[@vidblogger12]

Brace for this getting recommend after 3blue1brown's video on the topic.

[@dlahouss]

That's why I'm here

[@ogle777]

Sounded like he was going to mention CRC in the end since it also is based on long division, but I guess that's different?

[@Hauketal]

CRC is much simpler. It can only detect, not correct, errors. CRC needs very little resources in either hard- or software. It is at similar complexity much better at detecting real-world errors like truncation or transposing than checksums.

[@sam5992]

I really wish the professor went into the shifting registers earlier on instead of just focusing on the super duper tough mathematical concept behind it. I was onto him the moment he said each symbol should have a value of 0 and a frame shift in the register would give wildly different results. Just bitshift until you get the symbols to all match zero, and then you got your data back... It's interesting he talks about the "hardware guys" doing super duper cool hardware stuff, but it's not really that hard to just explain or visualize the logic gates in the microchip specifically designed to do these calculations.

[@GoddamnAxl]

Funny that reed soloman code is now used in all the places that could use some extensions in the domain of a function.

[@russdill]

OMG, do BCH next. Your viewers haven't seen anything yet.

[@ZanderMander]

I would love this. I had to implement BCH encoding once and I'm still not even entirely sure how it works.

[@rudolfstepan2651]

I am a sw engineer and playing for fun with real-time audio processing and error correction.

[@1Eagler]

The original definition is something that goes the same road with you: συν + δρόμος = plus+road. So it’s not an illness or a wound that will go away i.e change road.

[@zombieinjeans]

Have you done a video on Turbo Codes since this?

[@isbestlizard]

Prepping for 3blue1brown's second part on ecc! :D

[@isbestlizard]

Ok.. half way in and have learned absolutely nothing aside from it works with 'symbols' and not bits..

[@isbestlizard]

This was unenlightening :/

[@kuroexmachina]

How is this so entertaining :o

[@warlockpaladin2261]

I want to see how to create the ECC values using the input data... and how to verify/correct the received signal.

[@trevise684]

This does not explain really anything about reed solomon, other than it’s diificult

[@dreammfyre]

Shouldn't we be able to use something similar to one of those neural-network picture algorithms(like the ones that takes a low-res image and scales it almost perfectly into high-res) and apply it to music or code itself at this point? (And, in this example, use it to fill in the missing data from a media that's been damaged, like a CD...)

[@johnfrancisdoe1563]

re hash Too weak. AI neural networks are inherently unpredictable. Error correction needs to guarantee correct results up to almost the theoretical limit of impossibility.

[@myleslos9658]

Tom Scott in 40 years be like.

[@jasondmyterko5780]

from newman on down you can't download WHY?

[@kuroexmachina]

SICK

You know stuff gets really complicated when the only people who are able to explain it are retired professors.

[@CarterColeisInfamous]

just blew my mind because i realized cds have error correction :facepalm:

[@MelvinKoopmans]

Not only CD's. I just figured out from Wikipedia that it is also used for _QR codes, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, and storage systems such as RAID 6._ Google, for instance, uses it in their massive distributed storage system, Colossus, to recover from disk failures.

[@3zrv]

Watching the video , while holding the modulation scheme , feels like being in a trap called Computer Science >>> Edit : Nice topic by the way , i like it

[@hiqwertyhi]

3:48 is great out of context

[@martin128]

I had my runin with reed-solomon when i tried to make data matrix barcode.

[@MrOvergryph]

Wow

[@ZomB1986]

I commented on the previous video that I'd like a Reed-Solomon video (with the implication of the same kind of content). I'm disappointed as after watching this video, I still can't implement R-S from scratch in software, and that's my goal. Yes I know how difficult the math is, but I can't change the fact that I just need to know how it works, rather than just grabbing a library and calling it a day.

[@randall172]

do video on ROP

[@legendgames128]

What about columns of bits that are 1 tall?

[@rcgldr]

In that case, BCH code is normally used. For the BCH like version of Reed Solomon, let n = number of bits per column, then maximum number of symbols, including the parity symbols, that can be corrected using Reed Solomon is 2^n - 1.

[@jellyfishjelly1941]

Please no more tokens! I've had a fever dream with tens of Dr Bagleys passing tokens.

[@Monothefox]

how about Bose-Chaudhuri-Hocquenghem?

[@azertyQ]

Now do turbo codes

[@kayakMike1000]

Reed-Solomon error correction is a mechanism to improve data integrity by encoding redundant information that can be used to correct errors in the sequential bit reads. It's useful in any mechanism where data integrity is required on bit streams. Compact discs are the classical example, but it's also used in QR codes and data transmissions.

[@joebloggsgogglebox]

He really goes round the houses with his explanations doesn't he? If I wasn't a native English speaker I think I would probably find this video very confusing.

[@abhijeet800]

Galois theory - 7:48 if you were finding.

[@yfs9035]

TLDR; CD Players are a damn miracle

[@dexter97_66]

Im a simple man I see Professor Brailsford, I click!

[@shemmo]

it reminds me prof.Farkas from Pan European University

[@gloweye]

Ok, but how does it work?

[@Ykulvaarlck]

you didn't even mention berlekamp-massey!

[@mallik10892]

This is how dsl services works

[@kindane4417]

I just want to make my own qr code generator, why is it so hard ((

[@richtourist]

Please plan the video before you start, because this is rather slow and repetitive compared to the other stuff.

[@lukaskusik8034]

I see I click

[@leeamraa]

If I can copy his knowledge and style to all of my teachers from KG PHD.

[@AB-Prince]

please do a video on how a 6502 works

[@johnfrancisdoe1563]

the bronylike superchannel The 6502 was a fairly simple CPU designed by a small team at MOS (later Commodore) in the US. The design team was so small it made Acorn computers in Britain realize they could design their own RISC CPU without owning a chip factory. This became the Acorn Risc Machine or ARM that has since become one of the world's most widely used CPU families.

[@jezzermeii]

Fun fact: I have the same chair as this man!

[@Jirayu.Kaewprateep]

📺💬 Gallion series and error correction in CD, where it is capable of working the hardware performs supercomputing ability. 🥺💬 Yes, and 2 bits modulo for error collection purposes is makes sense that a small device can perform a big computation within 15 seconds of buffer time. 🐑💬 Everything had prepared state and work in real-time when it does require.

[@charlieangkor8649]

In my experience, CDs don't work even when they aren't scratched.

[@FlaSh3ch]

Czech Cymbals

[@fukyougooglification]

it's like he's afraid anyone might understand what he's saying

[@avi12]

Who else is watching this video properly, on a 4K monitor?

[@sgaleta]

May I present you Moiré

[@Pants4096]

I searched the comments specifically for this! ◡̈ His shirt is quite the test for video compression.

[@skullmanji1825]

Guillain-Barre Syndrome = progressive ascending flaccid paralysis. I'm from the medical field, don't know what I'm doing here.

[@RavenLuni]

What it is != how it works. Disappointed.