Name: Checksums and Hamming distance
Uploaded: 2020-03-27T17:08:58.000Z
Duration: 28 min 21 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Parody could be used to detect any single bit error that occurs when transmitting from one system to another

And we can inject an error here too to sort of demonstrate that but the limitation of parity is if there's more than one error

That occurs in your message, then it may not detect it. And actually in this case that seems to be what has happened here

So, for example, we have a comma in our you know

Over here no comma so there was definitely an error and of course

injected an error you saw that but I received parity is is even which

Indicates that we did not detect a parity error

Even though there was an error and that's just a limitation of parity is if there's one bit error

But if there's more than one depending on how many errors there are you basically have a 50/50 chance of catching them

And then at the end of the last video I showed you some potential ways to work around this by potentially adding more parity bits

So if we have our message here hello world when we can convert that to binary

we've got the the binary representation of what we're sending and

You know, just four four basic parity. We have a single parity bit

and in this case if we count up all the ones in this message, there are like 49 ones and

In order to send this with even parity. We want to send either 48 or 50

We want to send an even number of ones so we have 49 ones

We need to add another one so that we send an even number of ones

But if we change any two bits in here, for example, we just change any any two ones to zero

So instead of having 50 ones we'll have forty-eight ones that's still an even number and so we won't detect a parity error

So one way to work around that is to add more parity bits

So instead of having a single parity bit for the entire message

We can have a separate parity bit for each byte

And of course the trade-off is if we're sending a parity bit for each byte then we're sending more data overall

Because we're essentially adding 12 percent overhead to our entire transmission and maybe that's worth it because you want to catch errors

But even here you still may not catch every error because if you have multiple errors in a single byte

Then you may not catch that with the parity bit

And so you could keep going you could say well send a parity bit for every four bits or a parity bit for every two

Bits or even a parity bit for every bit which essentially just means you're sending the entire message twice

But all of that just adds more overhead and so it seems like there's this trade-off, right?

I want to talk about some ways to sort of do better than this too to get a better air detection

But lower over that's sort of our goal here

And one thing to keep in mind is just the types of errors that we might that we might expect

So it's actually not true that it's equally likely for every bit to just randomly flip errors tend to happen in certain patterns

So for example the error that we had here where you know

We were supposed to be receiving hello comma world but we received hello and then and then two spaces

That error happened because of two bit flips. So if we look at the difference between a comma and a space

In both cases and then it's either 1 1 0 0 or 0 0 0 0

and so what happened while we were transmitting this is I just hit this button to

Drop those two bits and that that's what injected the error and because it was 2 bits that flipped

We didn't catch it with the parity, but we wouldn't catch you here either, right?

Then this parity bits still gonna be a 1 right because we'd go from 3 ones in here to just one one in

Here and that's still an odd number. So we'd still have a 1 out here as our parity bit

So we still wouldn't catch it with even this scheme

and in fact this this type of error where you have multiple bit errors in a row is called a burst error and it's quite

Common because you might imagine some sort of thing interfering with your with your signal

Maybe it's not a button like this. But but some sort of interference that happens

It's gonna happen, you know over or maybe some short period of time and corrupt a couple different bits in a row

So one thing we could do with parity. That's actually much better at catching

Burst errors is instead of using a parity bit to protect a sequence of bits in a row have the parity bit protect an interleaved

Sequence of bits so one way to do that is something like this where we have the same data here

But instead of computing a parity bit for each byte is essentially compute a parity bit for each column here

Which is sort of each each bit position within the byte

So for example, if we look at the first bit of every byte, well this case they're all zeros

And we just do that for every bit position at the end here. We're gonna have

Another another essentially another byte of 8 parity bits

and so we send our message and then we send these eight parity bits and this is

if we change both of these bits here like we did in our message where we lost our comma we would detect that because both

Of these parity bits down here would be invalid now

This still has limitations, of course, so just like here if we change two bits in a row

If you change two bits in a column, you wouldn't detect that and so there's this trade-off between you know

Parity bits per row versus parity bits per column and which one you might choose depends on the types of errors

in most communication systems burst errors are actually pretty common and so something like a a

Parity bit per column here might be a better choice

But know that you you may not catch multiple bit flips in a column

So that's the trade-off that you're making but maybe we don't need to make that trade-off

you know a few of you suggested in the comments on the last video using a checksum and

The term checksum can can technically refer to any additional little bit of information that you attach to your message to validate that it's correct

So if we take the the characters in our message and get their ASCII numerical equivalent

We just add those up and in the case of hello world

We get 11 61. And so what if we just send our message and we send this number 11 61

Well, then you'd think well if anything in here changes, well, then the sums probably going to change. So is that better or

As good or worse than these parity things we've been looking at well to figure that out

it actually helps to look at this addition in binary because you know

We can do the addition in decimal like we did here we could do the same addition in binary

And in fact, you know, this answer we get here is 11 61 in in binary

But if we look at the way this addition works, there are actually a lot of similarities to parity going on here

and so we we can actually sort of compare what's going on here to what's going on with

Parity scenario where we were taking a parity bit for every column

Well, it turns out that actually for this first column here on the right

Because if we just count up how many ones there are which I guess is the same as adding them

We got 1 2 3 4 5 and so the sum there would be 5 of course. There is no 5 in binary

You would put a 1 down here. And then we carry a 1 0 over into these next columns

So the 5 here is 1 0 1 we actually look at this one that we're putting down here at the bottom

Subtitles ListPlay Video

Checksums and Hamming distance

sort

entire

essentially

susceptible