Error Correction - Computerphile
Вставка
- Опубліковано 9 вер 2024
- What good is knowing you have a problem if you can't fix it? - Professor Brailsford explains Hamming Codes and how errors can not just be detected, but also corrected.
Original Compression film: • Compression - Computer...
Entropy in Compression: • Entropy in Compression...
Error Detection: • Error Detection and Fl...
Home-made Video Arcade: • Homemade Video Arcade ...
BASIC & Sorting: • Programming BASIC and ...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradycha...
I could seriously sit and listen to this guy all day, he's so goddamn interesting.
only issue i have with this channel is the videos that are part of a series of videos are not labeled. Sometimes you give them the "continued.." but that doesn't help if there are more than 2.
Professor Brailsford is video GOLD for education about this field and it's history!
Why use the cube at all? Why over complicate this? If you got two zeroes, it's an ACK. If you got two ones, it's a NAK.
The point is that, minus the perfect 000/111 case, you're tolerating at most one bit of corruption. So 110, 101, 011 = the only possible ways to corrupt one bit of three ones. Likewise, 001, 010, 100 = the only possible ways to corrupt one bit of three zeroes.
Keep It Simple, Smarty.
Definitely my favorite series on computerphile so far!
Would love it if we could venture further into the 'hairy' stuff, even if we'd only scratch the surface in such a short format :)
It'd be great if we could have "Part 1" and so on in the title, I often stumble onto Part 2 from a video that interested me, without knowing it'd been there
Flashbacks to 12 months ago. and my grad course. This is one of the foundation pieces guys! Can't have our lovely wi-fi without it.
Just programmed a hamming encoder/decoder for my programming class! Really cool stuff, I'd like to learn how multiple bit error detection/correction works
You should make a video about creating Hamming codes for larger numbers/multiple errors. You said it was very complicated but I disagree. It is one of the simpler algorithms, it is absolutely beautiful and anyone who ever took algebra should be able to understand it.
this channel ND numberphile i love it..
i am doing my computer engineering and sometimes when i get frustrated of my hectic life schedule and want a productive break these are the two channels i come to...
i hope you guys make more and more videos .. so that it can make my course more interesting and also encourage young minds to perceive career in computer also it would help ordinary people to know how the devices they use so casually work...
guys please make more videos... i love them all and it makes my course really more interesting ...
This is my favorite series in computerphile so far.
Different idea in cd error correction Reed Solomon I believe in 1960s - love to see him demonstrate that correction code. If memory serves a 16x16 grid. Though it's years since I studied theory.
The arrangement of bits in that cube has a very special property that makes the detection possible, notice how every sides in the cube connects two points that differs in exactly one bit. The cube looks a little pointless here because there's only 3-bits, but with larger number of bits, when you're sending n-bits with larger correction distance, you can construct an n-dimensional hypercube to help visualize and correction simply becomes finding the nearest "good neighbors" in the hypercube.
RAID 1 and 10 have error correction in that there's at least one identical copy of everything. RAID 4 and 5 reserve one disk's worth of space to store parity bits (which follow the same rules that Professor Brailsford has been describing), and if one disk fails, you can use those parity bits along with the contents of the surviving disks to figure out what would have been on the disk that failed.
To break down a concept an demonstrate it in basic terms it's always good to go back many generations before modern error correction algorithms for example like the streaming video data in this video.
As he mentioned at the end, modern error correction methods are based on sophisticated versions of this method. This channel is more about the origins and foundations of CS than about teaching cutting edge methods.
I have to say that in general the computerphile videos are not all that interesting to me (a programmer), which suprised me a lot because i liked the idea. But the videos with Professor Brailsford are always really really good and i feel they are explained well even for those that are not that deeply familiar with the things he talks about. Keep it up!
In any case, the point of the ACK and NAK is so that the receiver can say to the transmitter "Got your message, thanks" or "Could you send that again, please?" respectively. So, on decoding that received ACK or NAK the transmitter will know what happened to the original message.
The original message could also implement a similar system to what the Professor describes here for error correction, and so the receiver could attempt to correct errors before giving up and sending a NAK.
First, it actually is possible to have signals with different lengths (look up "variable-length code" for some examples).
Second, a "0" signal is not the absence of power, because then a "1" signal would be indistinguishable from a "01" signal or a "10" signal. A "0" signal would be a low-voltage signal and a "1" signal would be a high-voltage signal (or some other representation of what is technically a 3 character language with "no power" being a "space" or null character).
I'm feeling proud that I know what he was talking at the end.
This man has to be one of the best teachers in the world.
Interesting; 1 Qbit Quantum error correction uses two additional bits as well. The Qbit has the superposition state Y= a|0> + b|1> where the information in the Qbit is contained in the complex numbers "a" and "b". We entangle the state with two addition bits which gives us Y' = a|000> + b|111>. Then no matter which bit gets damaged we can recover the original state /w 100% certainty by applying a set procedure. The bonus is that we can actually lose 2 bits and still recover the original state
I was working on sending small packets of no more than 256 bytes of data over IR using a a NRZ scheme really meant for TV remotes. I wanted good error correction but I think a few braincells upped and left me in the effort. I had to settle for error detection only in the end. Excellent work and thumbs up!
(cont.) say you want to send 32-bit data with correction distance of 4 (i.e. it can correct when up to 4 bits are flipped). Given this requirements, all you need to do is to create a hypercube that can fit 2^32 good points where each good points are at least 9 steps away from all the other good points. How to create the smallest hypercube that satisfies that property and can be easily transformed back and forth from the original 32-bit is more involved, but it's easy to visualize why that works.
Just wanted to say that prof. Brailsford has amazingly soothing voice, it's pure pleasure to listen to. I'd love to see more videos about this other lovely stuff :)
Drawing it as a cube makes me think that it's just a distance calculation from each corner. errors have a distance 1, sqrt (2) or sqrt (3). That seems like it would make large problems easier.
I like this clear step by step explanation. A well done video!
This way of explaining it converts very well into the mathematics behind it.
Lol, everything is understandable and fascinating when your teacher's got a british accent! I just love this channel! ^_^
What you are talking about though is synonymous with geometry. Steps are essentially distance. The reason why he used a cube is because it's a nice analog that works even better when the systems get much more complicated.
CDs use so-called Reed-Solomon codes. With them you are able to restore up to 25% corrupted info. The idea behind it is basically to distribute information, so that if you scratch a surface, then erased bits can still be built up from other parts of CD. Same principle is used in QR-codes.
I'd like to spend a day with this man.
Please more videos about this!!!!!!!
Anyone else love this guy's voice?
It may seem weird, but I am genuinely interested in the way harder stuff.
To be honest, for me personally it was fatiguing that he took like 5 min to explain that there is no way you can get from 000 to 111 with 1 error - although he is an amazingly interesting speaking teacher.
You said you read the comments so I like to leave my feedback :)
I'd really watch maybe 30 min videos which go in depth when it's such an excited teacher. Maybe here or on numberphile.
That was a very complex way of explaining how to correct the errors. Instead of representing it as a cube, you could've just said "if one bit is wrong, then change it so all three bits are the same".
Only if only need to do it a small number of times. Speaking is a very slow method of transferring data; I could spend all day calling places and getting only a few hundred weather reports. But if I need to know the wind speed and visibility around a weather drone every few miliseconds to make sure I don't crash, this method will do better than a phone call.
A parity bit is the easiest form of a checksum. A checksum is any method of changing the data to allow error detection to occur at the receiving end. In this example, he did just use a parity bit, but he wasn't incorrect in calling it a checksum.
You can also use methods like cyclic coding where the information is encoded into more bits. This allows you detect and correct wrong bits at the receiving end.
Let's say : there is 25% chance for one (any) bit in 000 to get distorted. So there is 25% chance to go from 000 to 010,001,100. This doesn't bother us, as we know it was 000 before (with the "cube" error correction).
So there is 1/4 * 1/4 = 1/16 chance (6,25%) chance to distort 2 bits. To get them all wrong we have 1/4 * 1/4 * 1/4 = 1/64 chance (1,5625%).
That all means to interpret the AKN / NAK in a wrong way we have 7,8125% chance.
If you liked the set of integers from 0 to 255, well, Beyonce can tell you how you should have used it for error correction (and also encryption).
It's in the description under "Error Detection".
Man now I want a video on each of the things he mentioned at the end!
Also the CD player hides some smaller errors from the user. So even if some data samples have been lost, the user usually can't detect the difference. Only if the error rate gets too high, there will be audible crackle or a short silence.
Very well explained, thanks! I had wondered about this before, but I'm not a good learner by reading just text. Visual explanations I grasp much quicker.
I think the whole point of doing this is not having to make a call. And when you solve this problem, you can apply it to any other city and have the whole country constantly updated on how the weather is like everywhere.
because that only works for the simplest case where your valid bit patterns are all 0 or all 1. For complex messages you probably have multiple messages with the same bit counts but that are still 3 edges away from each other in your graph.
This chap is epic at explaining stuff
I could be totally wrong, but I feel like he is stepping up a 3-D graph and using it as a proof of theory. Same idea as using the limit definition of a derivative to find the derivative of X^2, or just knowing the 'rule' of making the exponent the coefficient and reducing the exponent by one. Same result, one is a trick, one is the proof.
I made example in other comment. You can count steps needed to reach any expected combination without graphic representation.
2 points!
1: This is quicker
2: This is over-engineered madness and is therefore better!
There is a carrier signal agreed by both (or all) ends of the network. This signal is then manipulated to represent 1 or 0.
not quite, i think you would just be adding faces to the 3 dimensional object. four bits for instance would probably resemble a truncated icosahedron and so on. i would assume the shape of a 8 bit spherical polyhedron would need a single point (00000000) with six other geometric points of interest around the sphere before hitting the far point(11111111). all points of course converging in. essentially it would need eight paths and six or seven points between on each path.
Loved the way he ended it off. Gets me excited to learn more mathematics!
My point is (was), it's just an extremely complicated way of saying 'we send the bit three times and use whatever pops up the most times'. The schematic used, while accurate, over-complicates it, especially with the (UA-cam) audience in mind, as it should be described in as simple and general terms as possible.
It's also portrayed to provide something like flawless accuracy, which it does not (unless it's near-flawless to begin with).
yyyeeeaaaa new computerphile video!!
To expand on QuotePilgrim:
1) Pay your internet company for a fixed IP address
2) Use a domain registration company to register (and possibly pay for) a domain name to be mapped to your fixed IP address - takes a day or so for this information to propagate through the internet
3) Configure your home PC firewall and router to let incoming traffic through
4) Install a web server and a website onto your home PC
5) Your home PC is now a 'sever'
Oversimplified but hopefully informative. ^_^
All these error correcting mechanisms are done in the assumption that getting an error is, to a certain point, highly unlikely. So, when you receive a 010 it is much more likely that the original message was 000 and the middle bit was swapped, than it is that the original message was 111 and both the corner bits were swapped. It is still not 100% reliable, but it's much more reliable and quicker than to send acks and naks back and forth.
You don't have to physically draw the cube. That was just to illustrate a point. However many problems are simpler to solve when taking into account geometry. For example netflix's suggestion system. They compare you to other members and suggest movies that people have rated highly and those people are close to you in Euclidean space i.e. people who rated movies you've rated similarly.
Here are a few great ideas for the next Computerphile videos: Field theory, rings, groups and/or cosets :D
I love this channel so much. Could you do an episode (or several) on file systems and RAID?
I love this old reel feed paper!
The process of correcting something is one thing, but how to know an error occurred in the first place? How to know without a shadow of a doubt where things went wrong? And what is the most likely answer? All of those are answers that the cube solves. Flipping bits, babies can do it, but flipping the right bits and doing something meaningful with that, people have devoted their entire lives to that sort of problems, trust me, at some point in history that cube seemed like pure magic!
A 1 vrs. 2 bit code would be hard to tell apart. Since by default there is no data coming down the line, you could imagine the default 'no signal' message being a trail of 0's. So sending either 01 or 1, it would look like 00001000. (Is it 01, or 1 that was sent?). To solve this, all messages should be the same length and have a start bit to mark the beginning of a message. Now if you get 0000010100000 or 00000100100000, you can tell whether it was 010 or 001 that was sent. I hope that helps. :)
You should do a video on RAID 0,1,5,10 etc and explain how the error correction is done.
You effectively just pick the binary digit that's most often represented in the trio, and assume that's the digit. In 001, there's two 0s, so go with 0. If there'd been five, it could be 00111, and there's more 1s, so go with 1.
usually these things are time-based, so an inserted bit would likely result in further data looking like garbage.
presumably, there would be a mechanism in place for the hardware to re-align with the communication stream, then it reports a bad value or similar?
Maybe Reed Solomon could be a good continuation of this at a later point? Once you start getting into noisy transmission on lines of more bits.
A parity bit is a kind of checksum, just a very simple case.
based on? why not a polyhedron with 4294967296 vertices (eulers polyhedron formula), choose a number of edges and it'll tell you the number of polygons that make up the faces of said polyhedron...
- correcting just 1 bit: then 4294967294 vertices are wrong.
- have 2 rings of 2147483647 vertices each plus the 2 good vertices.
- and a total of 10737418233 edges (imagine a wheel)
- the number of faces of such a polyhedron is: 6442450939
It all depends on how many bits you want to correct.
Professor Brailsford is is WIN!
***** So it works best with any odd number of bits in the original ack or nak signal. On the receiving end (after possible errors), just count up the 1s and 0s. More 0s = ack, more 1s = nak. For instance, let's try it with seven-bit outputs:
ack: 0000000 --> 0101100 // That's fine, four zeros and 3 1s, it's still an ack result.
nak: 1111111 --> 0011101 // That is acceptable as well. Four 1s and three 0s, still a nak. This allows up to 3 bits to be corrupted. If you want to allow for x corrupted bits, you simply need 2x+1 0s for the ack, and 2x+1 1s for the nak. Honestly one of the simplest problems your videos have dealt with.
Cooper Gates simple CRC works with comparing bit sets - more complex corrections use larger blocks and calculate a hash - if the hash fails to comply at the other side - this block is at fault and can be sent again.
but what if electric interference is the cause of the fault ?
What if one changes the frequency on the bus.. and lower the error rate with it ?
when the hole is at a position where there is no data, its no problem. the cd is filled from the inside out. so if the cd is only half full its likely there is no data on the outer parts. but i think the cd player could have some problems with a disc which isnt balanced anymore.
Actually that's not the theory behind, because here you're dealing with 3 bits, but you may have "words" with more bits, most likely a multiple of 8 bits, so changing one bit does not work.
The thing actually is changing as few bits as needed to get to the closest "correct word". And, in case you still wondered, you don't always have only two options, all 0's and all 1's, but some combinations from 0...0 to 1...1 are valid "words" and others aren't.
Yep, I studied this at the University.
More practical is a 3-Dimensional matrix. Just imagine subdividing the 3D cube until you're left with 4294967296 (2 to power 32) vertices. Therefore the distance between the two "Good" transmissions would be 32 (in the cube example it was 3).
I hope there will be video on fields, rings, groups and cosets, either here or on Numberphile.
Perhaps go into explaining the difference between Back Error Correction and Forward Error Correction? I think it could be interesting to hear your explanation of this.
for a distance one correction of any bit length couldn't you just convert the codes to the decimal form and check if the wrong code has a difference of 2^n (1, 2, 4, 8 etc.) compared to the correct codes? That should be only one bit difference
"3-dimensional" only means that each vertex in the graph would be adjacent to three other vertices, just as a two-dimensional "cube" is just every vertex being adjacent to two others. Adding extra bits you could imagine as duplicating the existing k-cube and adding an edge between the "same" vertices.
Adding a bit to {000, 100, 110, 010, 011, 001, 101, 111} would become
{0000, 0100, 0110, 0010, 0011, 0001, 0101, 0111,
1000, 1100, 1110, 1010, 1011, 1001, 1101, 1111}.
See how this is the 4-cube?
Please do a video on ECC RAM vs. non-EEC RAM, and DDR RAM vs. GDDR RAM
That's science :) read my comment again and notice the "why not" near the beginning... thank you for your reply, certainly a specific situation might require a specific solution... my proposal is not universal or a panacea when it comes to error correction schemes... it is just a simplification of the 32 bit problem on a 3 dimensional space...
As i understood it, the cube is needed to describe what would happen if you had say 4 alternatives. That would produce a 2x2x2 grid of cubes. Each option at least 3 spaces away from the other.
But i am tired so don't take my word for it, look it up if that sounds good.
The cube is simply an easy way of visualizing something he didn't specifically name, which is hamming distances.
In Information Theory, there is a rule which says that in order to correct one bit in a bitstream, each code must be at least a hamming distance of 3 away from each other. Any less and you can't do it.
It should be noted that maximum likelihood and nearest neighbor/minimal distance are, in genereal, not the same thing, though they are in this example.
I spent a while trying to understand what (cool) structure you're describing - but it's not right unfortunately...
Eg:
- If you had 32 bits, why would you only use 2 correct codes and with path length 3 between?
- How would you assign numbers to nodes? (so that each edge represents a corruption of 1 bit)
More fundamentally, a 32 bit code has a space consisting of 2^32 different numbers. Each bit would be assigned a dimension, giving a 32D hypercube. (Independent of all the hamming stuff)
It would be easier in this specific case but this is a general solution for all possible codes.
What if the codes you're expecting are 010101 and 101010?
What if you're expecting one of ten codes, not just two?
Computers are amazing D:
And Professor Brailsford is really good at explaining how they work.
More please :V
this guy's a boss at drawing cubes.
What do you mean by "isn't either like 010"? And If the ack/nak is warped then yes the message probably is warped. I thought the whole ack/nack thing was for like single characters, so each letter in the text file would have their own ack/nak test.
Do hamming codes next!
Would it be more beneficial to ACK that it is cloudy outside (101) rather than sending back a Boolean state (111) or (000)? Or even go back to (10) but instead do a double ACK?
A: 01 -> B
B: 01 -> A
A: 01 -> B
B: 01 -> A
It is obvious, but it is also a very simple coding scheme that nobody really uses in practice anymore... it's used for teaching because of its simplicity.
The problem with it is that for every bit of information your sending, you're actually sending 3 bits... so bandwidth becomes more limited as you are using more bits than are necessary to transmit the information.
The difficult thing to do is to find/design a code that approaches the 1 bit per bit of information limit as closely as possible.
Connection errors, broken line, whatever like that. You can still probably distinguish what he is saying,even if some parts got distorted.
Wow, where does this guy get old school computer printout fanfold paper? I haven't seen that stuff since I was writing Fortran 77 code for our CDC Cyber 170 something like 35 years ago.
That's... Kind of obvious. It's just the fact that the more bits you transfer per bit of data you're sending, the more likely the received bit will be correct. If you use five bits, it'll be even more accurate, or 7, or however many.
(With 3 bits compared to 1, the realistic odds of the data bit being wrong have gone from a given probability (a) to 3a^2 - 2a^3. So errors will still happen, just less often.)
"Other lovely stuff like that" == Error Correction with Reed-Solomon, and Golomb rulers.
What happens if the error doesn't change a bit, but instead adds or deletes a bit? (000 becomes 0010, for example)
Just discovered the channel! Loved it!
Fantastic video!
Yes, a 000 could turn into a 111, or 000 into 110, or so on - it's just incredibly unlikely in comparison to just 1 being changed.