Error Correcting Codes 1: Introduction + Hamming (7,4) Code

No video

Error Correcting Codes 1: Introduction + Hamming (7,4) Code

Рет қаралды 58,589

eigenchris

Күн бұрын

Пікірлер: 68

@jonasdaverio9369 5 жыл бұрын

I'm so happy. I came for your tensor calculus series and now I'm addicted

@blazingsniper1239 3 жыл бұрын

Thank you so much for explaining the reasoning behind the equations I was taught this in way that was basically forcing me to memorize . I truly believe that the best way to learn is by understanding the reasoning behind what your doing as it makes it easier to memorize and more enjoyable

@prajwolgyawali6770 4 жыл бұрын

Repetition Code - 2:30 Hamming Code - 6:55 Syndromes - 17:03 Check-bit states and Error States - 17:10

@PC-wi1tk 5 жыл бұрын

Glad to see you back. Code theory has very interesting ties with field theory and algebraic geometry, and it's not easy to find instructional videos about it. Keep up the great work!

@TORGIXGaming 3 жыл бұрын

I study media engineering in Germany. Since there are no good videos in my language about this topic, you are my hero. Thank you! :D

@alibaba888 4 жыл бұрын

Thank you very much for explaining clearly and not including too many unnecessary and complex words!

@NoNameAtAll2 2 жыл бұрын

interesring to compare this explanation of Hamming code with 3blue1brown's one I guess I like 3b1b's version more, because it shows "set intersection" aspect visually, but pure "make equations do the work" approach deserves respect and I guess that "one can mix what error states correspond to which error bits" idea is eye-opening, but probably just corresponds to taking different bits in 3b1b rectangle...

@JgM-ie5jy 5 жыл бұрын

Absolutely amazing ! I was eagerly awaiting the upcoming series on GR which I thought would be the end of your production. But instead, a totally unexpected series on error correction coding, which I also am very interested in. So excited, I wrote this comment even before I began watching the lecture. The first screen seems to relate linear algebra to error correction ... How is the tip jar coming along ? I hope I don't have to use an intermediary to process a credit card transaction.

@beagle1008 5 жыл бұрын

good to see you back!

@user-zu4ft8yw9e 4 ай бұрын

Error Correcting Codes 1: Introduction + Hamming (7,4) Code Decoding Problems Stages In the field of data transmission and storage, error-correcting codes play a crucial role in ensuring the reliable transfer of information. The Hamming (7,4) code is a specific example of an error-correcting code that can detect and correct errors in a data transmission. Let's break down the stages involved in understanding and solving problems related to this code. 1. Introduction to Error Correcting Codes: Error-correcting codes are mathematical algorithms that encode digital data in a way that allows the receiver to detect and, in some cases, correct errors that may occur during transmission. These codes work by adding redundant information to the original data, which helps the receiver identify and correct errors without the need for retransmission. 2. Understanding Hamming (7,4) Code: The Hamming (7,4) code is a popular example of an error-correcting code. It is a linear code that can correct a single error in the transmitted data. The code is named after its inventor, Richard Hamming. This code uses 7-bit blocks to encode 4-bit information, with the remaining 3 bits serving as parity checks for error detection and correction. 3. Decoding Problems: Decoding problems in error-correcting codes involve determining the original data from the received data, which may contain errors. In the case of the Hamming (7,4) code, the decoding process involves the following steps: a. Syndrome Calculation: The receiver calculates the syndrome, which is the sum of the product of the received bits and a set of fixed coefficients. This syndrome helps determine the location and type of error(s) in the received data. b. Error Location: Using the syndrome, the receiver identifies the location(s) of the error(s) in the received data. c. Error Correction: Once the location of the error(s) is known, the receiver can correct the error(s) by flipping the bit(s) at the identified location(s). 4. Stages in Solving Decoding Problems: To solve decoding problems related to the Hamming (7,4) code, you can follow these stages: a. Understand the code structure and its ability to correct errors. b. Learn how to calculate the syndrome for a given set of received data. c. Develop strategies to identify the location of errors based on the syndrome. d. Implement methods to correct the errors by flipping the appropriate bits in the received data. By mastering these stages, you will be well-equipped to understand and solve problems related to the Hamming (7,4) code and other error-correcting codes.

@neomuks 4 жыл бұрын

it's a vary good video so easily explained, good work.

@user-fc2yp9ne8h Жыл бұрын

Your videos seem to be the best ones to understand ECC by far. Its a shame the series isn't finished but I was wondering if you have made any notes on the rest of the topic that I could buy?

@swalscha 5 жыл бұрын

New serie 🙌🏼😃

@eleazaralmazan4089 4 жыл бұрын

Great video! I already love this channel!

@Sharikkhursheed 5 жыл бұрын

Hello eigen why dont you upload video on tensor analysis.. We are waiting to go for General theory of Relativity

@eigenchris 5 жыл бұрын

I'm preparing the final 3 videos I have planned for that series on Torsion, the Riemann Tensor, and the Ricci Tensor. I'm still learning about them, and I'll be uploading ECC videos in the meantime until my understanding of the tensor calc stuff is better.

@dippatel1739 5 жыл бұрын

waiting for next video in series.

@letsstarttogather6701 Жыл бұрын

Life saving lecture 🙂

@eatonashton4962 3 жыл бұрын

Thanks a lot. Your lecture is very awesome and helps me understand hamming codes!!!

@SzechSauce 4 жыл бұрын

Excellent video thank you so much for this!

@armannikraftar1977 5 жыл бұрын

I see eigenchris, i click!

@emmanueladebiyi2109 5 жыл бұрын

I would like to know the reason why we have those exact equations for x, y and z. It's it a random selection?

@eigenchris 5 жыл бұрын

I try to explain the proces for getti g the equations in the last 30% or so of this video. It's not totally random, but the 3 variables chosen in each case are arbitrary and can be switched around.

@emmanueladebiyi2109 5 жыл бұрын

@@eigenchris Thanks a lot

@2262sandeep Жыл бұрын

Students are liberated after seeing this !

@phumlanimbabela-thesocialc3285 2 жыл бұрын

Lovely series. Great video.

@malcolmvernon6808 4 жыл бұрын

Hey I googled ricci to know how to pronounce it and saw some of your videos. Good stuff

@Shirani007 3 жыл бұрын

You are one amazing teacher !

@Kelvin.907 4 жыл бұрын

good job chris!

@joelmayer1018 2 жыл бұрын

Really good and informative video

@signorellil 5 жыл бұрын

Hi Chris not wanting to sound like a broken record, and this new series is great... but when will we get the final videos on Tensor Calculus?

@eigenchris 5 жыл бұрын

As I said in another comment, I'm preparing the final 3 videos I have planned for that series on Torsion, the Riemann Tensor, and the Ricci Tensor. I'm still learning about them, and I'll be uploading ECC videos in the meantime until my understanding of the Tensor Calc stuff is better.

@signorellil 5 жыл бұрын

@@eigenchris thanks!

@user-lc1dk1oc1l 5 жыл бұрын

I'm so glad you are still alive

@CrazyAssDrumma 4 жыл бұрын

for the hamming code, what if the any of the 3 bits are wrong? I see how the 3 bits can be used to correct the 4 bits, but how can the 4 bits be used to correct the 3 bits?

@eigenchris 4 жыл бұрын

With 3 parity checkbits, there are 8 possible states it can report. 1 of these is for the "everything is good" case (ooo), 4 are for incorrect data bits (xxo, xox, oxx, xxx), and 3 are for incorrect parity bits (xoo, oxo, oox). If 2 pariry bits are right and 1 is wrong, we know the parity bit has the mistake. 2 or more parity bits being wrong indicates a data bit being wrong. I explain this more in the following videos.

@krissp8712 4 жыл бұрын

eigenchris not OP but thanks, that cleared up things a lot! I didn't quite understand the switch from the 1/0 value of the bits to x/o accuracy of the bits until I read this. At 16:40 I had misunderstood the example comparison. I thought that the 1/0 values somehow corresponded directly to accuracy without realising that the comparison was being made to get the ticks. So yeah, thanks for clearing that up for me!

@ruchikabatz6878 2 ай бұрын

u saved my life thanky ou

@Y747Y 5 жыл бұрын

A bit little rush, but overall well explain!

@harrysvensson2610 5 жыл бұрын

2:02 Will you go through CRC(Cyclic Redundancy Check) as well? Perhaps that's what Polynomial Codes are? If you will go through it then I'd love to hear why one polynomial is better than another polynomial, because I've so far never heard or seen any... reasonable explanation.

@eigenchris 5 жыл бұрын

I haven't studied CRCs directly, but it looks like the theory is very similar to error correcting codes. When you are asking abouy the "polynomial", are you talking about the "generator polynomial"? The one that's used as the multiplier? The anser in general is that you want a polynomial that "spreads" out the valid binary strings as much as possible. This is related to the idea of "minimum distance" which you can google. I know Reed Solomom codes have generator polynomials that are designed to have the highest possible minimum distance for a given string length, so in a sense they are "optimal". I'm not sure I can give a more specific amswer than that yet. Maybe future videos will clear things up.

@harrysvensson2610 5 жыл бұрын

@@eigenchris Well CRC's are very similar to checksums, but yeah when I said "polynomial" I meant "generator polynomial", in this case it's actually division, not multiplication. en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks It's not the same as a generator matrix, for say Hadamard code or Hamming code (I believe). If I'm not incorrect, CRC's are just shift registers where all bits in the register can be inputs and fed from xor gates and then fed back into the input with yet another xor gate. So a fancy checksum, yet not exactly a "sum", it's long division in some sense (according to wiki). I don't understand it 100%, but I'm fairly certain that you can't find out where an error has appeared in a CRC, just that some error has appeared and therefor the receiver can ask for another message. Fun info: CRC has been used multiple times in order for you to read this very text that I've written for you. Imagine losing packets on wi-fi/cable, instead of correcting some packet it just asks for the packet again and says that it has lost a packet. For forward error correcting codes, as you were describing in the video, then yeah I can understand how some generator matrices spread out messages and increase the hamming distances among all codes than other generator matrices. But the CRC polynomial is still... I can read that wiki article several times but it just doesn't go into my head. Or I can read some other wiki article... en.wikipedia.org/wiki/Cyclic_redundancy_check#Designing_polynomials It's still just... I think it's either so ridiculously simple that I'm just overlooking it, or it's so advanced that I can't understand it. So the thing I don't understand regarding CRC in particular is why one polynomial is better than another, or how you would say "this polynomial is better than this one because of ???". But yeah, maybe some future video will mention CRC, or checksums, or maybe not, I love your videos either way ;)

@eigenchris 5 жыл бұрын

So after a bit of reading, I've concluded CRCs are basically equivalent to Cyclic Polynonial Error Correcting Codes. I am working on the video for these right now and it should be out by early May. Although generator polynomials and generator matrices seem different, every generator polynomial can be converted into a generator matrix, so the idea behind them is more or less the same: take raw messages and encode them into a longer string, where the encoded strings are "spread out" as much as possible to maximize error detection. Every generator polynomial/matrix has a number associated wity it called the "minimum distance", usually denoted by the letter d. And if you want to detect/correct more errors, you basically need to choose a generator polynomial/matrix with the highest d possible. While I am not sure how to get d from the generator, I will eventually show how to go the other way around: how to create a generator with a given d. This is ultimately what reed solomon codes and BCH codes allow: we can pick a d of our choice and get most efficient generator with that d. When I say "most efficient", I mean d meets the "singleton bound", which is an inequality you can google that places constraints on the relationship between d and the message length. The following page, in section 7, says that choosing good generator polynomials is a "dark art", and says we generally use "tried and true" polynomials. however I think this might be untrue... the wikipedia page you linked me to mentions BCH codes and this leads me to believe what I said above is correct and that you can design a polynonial which has a given d that you want. I am guessing by the end of this series your question will be answered, but you can always ask me again later if things are unclear. www.ross.net/crc/download/crc_v3.txt

@harrysvensson2610 5 жыл бұрын

@@eigenchris Thanks for that txt file. It really helped. It's fun to know at least someone else has also thought of it as "black arts". But now I see that different polynomials can find different kind of errors (1 bit error, 2 consecutive errors, 2 errors randomly spaced, burst, etc). And I also believe that long division (mod 2) is the same thing as multiplication, with the caveat that the operand slides the opposite way in multiplication vs division. And this is because addition and subtraction is the same. So with CRC I thought it was only long division, but it's also multiplication in some sense. It's weird to even talk about multiplication/division in mod 2 when there's no carries. Oh well. So yeah, looking forward to the next couple of videos ;) Good stuff man!

@Salv-lj8kj 2 жыл бұрын

Excellent. Thank you.

@mateuszkucharczyk2399 Жыл бұрын

Great video! Thank you

@shreyanjha3903 10 ай бұрын

Do errors here neccesarily flip a bit, or do they have a 50 chance of flipping a bit given the error?

@eigenchris 10 ай бұрын

I'm defining an "error" as a "flipped bit" here. Maybe when you're artificially generating errors, you can assign probabilities like that for whether or not they happen.

@muradalm5730 4 жыл бұрын

god bless you.

@zakimuhtadi7194 4 жыл бұрын

You explain really well...should be a teacher.

@gabrijel9129 2 жыл бұрын

Thank you, you've helped a lot.

@fancypants6062 3 ай бұрын

thank you

@raqha4575 3 жыл бұрын

omg, this is gold

@computernetworking3888 3 жыл бұрын

your amazing!

@louaykhammar7268 3 жыл бұрын

thanks

@noobtech8658 3 жыл бұрын

Where I can get the ppt you used here

@user-oi4pg1yo5x 4 жыл бұрын

so cool!!!! thanks a lot

@deepbayes6808 5 жыл бұрын

Ok, so if you made videos on differential geometry and you made videos on information theory, why not cover the marriage of two: "information geometry". This is a topic that can really benefit your style of presentation.

@eigenchris 5 жыл бұрын

I didn't know that information geometry existed until now. :P Unfortunately I know nothing about it and it doesn't really catch my interest much. My main plan for the rest of the year is general relativity videos.

@deepbayes6808 5 жыл бұрын

@@eigenchris yes, I guessed. Information geometry is not very popular, especially if you compare with GR. But information theory is quite deep and general, give it a tiny chance ;)

@CrazyAssDrumma 4 жыл бұрын

does anybody actually call it a "zor"? In my whole professional life in computer science, we refer to this as "ex-or". Great video though

@eigenchris 4 жыл бұрын

I've heard both. I think ex-or is probably better, but it didn't occur to me until after I recorded the audio. I don't talk to people about logic gates out loud much these days.

@CrazyAssDrumma 4 жыл бұрын

@@eigenchris hehe thanks for the reply, makes sense. Great video btw, very well done

@jessg5336 2 жыл бұрын

Why should all the check bits be 0?

@eigenchris 2 жыл бұрын

The check bits validated that all the equations for checking for errors are satisfied. If there's a "1", it means one of the expected check-equations has been violated. Does that make sense or do you need more explanation?