Go to nordpass.com/anotherroof to get EXCLUSIVE access to NordPass’ best offer. It’s risk-free with a 30-day money-back guarantee! Or use my promo code anotherroof at checkout. Ask your questions for the Q&A here: www.reddit.com/r/anotherroof/comments/158a5he/31623_subscriber_qa_ask_your_questions_here/ CLARIFICATIONS & COMMON QUESTIONS: 1. At 0:02 I misspelt the name -- should be Elwyn. Mortified about this one, apologies.
Oh my gosh, I realized just now (after all of the videos) that these stones with axioms and definitions and proof results are actually our foundations! Nice touch!
@12:32 lol the Vsauce is on point! Congrats on getting big enough to attract some sponser money! Come a good way in not too short a time, you deserve every bit of success for the consistent quality every time, nailed it from your first 'real' video. Always looking forward to whatever new rabbit hole you'll guide us down next!
working on my graduation oral presentation, you just saved my life your lesson is so clear and you helped me understand multiple principles i was going to talk about without really knowing what i was yapping about Thank you very much and keep going you teach so well !
Wow i dont think i ever truly had the dots connect between linear codes and linear algebra / bases... in my defense the proper look into linear algebra in uni was after the course which featured coding theory (which also included many other things like circuits, hazards and capacitance). Once you started getting at the bases my lightbulb went white and everything clicked into place revealing the magnificent possibilities
@@AnotherRoof Theyre one of the best experience when learning! I really enjoy that you build up a proper foundation for every video topic, and i watch it even when i think i have the foundation already because quite often i still learn something new. (and knowing which of the multiple definitions are used for certain terms also helps to avoid confusion)
this did NOT feel like nearly an hour, your presentation style and visual aids make this so easy to sit all the way through in one go without feeling burnt out. I don't know how you keep up this consistent quality but keep doing what you're doing you've made yet another hit :)
Gooooosh I am immediately gets excited when you bring back linear algebra. Unusual vector spaces are so fun! It's just satisfying to see many lin alg theorems works outside of those real or complex matrices that we usually do.
I remember first learning about hamming codes, which there are al sorts of great videos about, then finding out there are even better methods...only to be told that they are so much more complicated I'll basically never understand it lol. There needs to be more educational content about more complex topics like this, it is so amazingly helpful for understanding. Thank you ❤
Wow, these videos are so good - they answer so many questions that I found difficult to figure out myself. And all the connections you show to the different areas of mathematics are mindblowing. Thank you so much for sharing your insights and making these videos. They are truly enlightening!
Q: does the construction or labeling of your icosohedron arise naturally? (do the actual labels matter? can I use different letterings and still create a valid golay code?) are there instructions to label the icosohedron? (a pdf? especially if the labels matter) Where can one find a good pdf of the original one page paper, the diagram of the S(5,8,24), and other such items...your videos are amazingly thought out, and I'd just like time to digest the original information. Thanks!
Great question regarding the labelling, I wish I'd clarified that in the video. The answer is that the labelling doesn't matter. I chose mine deliberately to generate the nice looking basis on the Wikipedia page for binary Golay code. Choose a different labelling and you'll get a different basis but it will still be a valid Golay code! References are in the description but might be blocked behind pay walls / institutional access unfortunately. If you do some googling of "miracle octad generator" you'll find a copy of the MOG. I'm actually contemplating making a poster for people to buy... Hope this helps and thanks for watching 🙂
I f*ckin love your channel. Number theory was already cool but your move to coding theory, which is dear to my heart, is just awesome. You've filled in so many of the blanks in my knowledge. Thanks man.
Love these videos! I'm not a mathematician, and I'm interested in necklace/bracelet combinatorics and it seems like you touched on it here finding all the ways to choose 3 vertices on the icosohedron where all that matters is the shape. For instance, there are only 43 uniquely shaped ways to pick 4 notes on a 12 note keyboard. Is there an easy way to calculate 43 outright?
The best way is to do it separately by symmetry group. With C4 (=shift by 3) symmetry there are 3, or 1 (C, Eb, Gb, A) up to symmetry. With C2 (=shift by 6) symmetry there are (6 choose 2)=15, but 3 of these have C4 symmetry so that leaves 12, which is 2 up to symmetry. Now (12 choose 4)=495 but 3 have C4 and 12 have C2 (and not C4) leaving 480, which is 40 up to symmetry. 40+2+1=43. I didn't need to account for C3 or C6 in this case. The term to search for is "inclusion-exclusion formula".
@AnotherRoof Since you're talking about coding theory now, can you also make a video on the McEliece cipher? I find it a fascinating story of how one can turn an _error correction_ algorithm into a _public key cryptography_ algorithm, even though those two tasks are seemingly unconnected.
the formula for the weight of a sum looks super familiar. w(b1+b2)=w(b1)+w(b2)-2w(b1 b2) now let u and v be vectors in an inner product space. then: |u-v|^2=|u|^2+|v|^2-2(u•v) this makes sense. boolean addition (addition mod 2) is identical to subtraction mod 2: 0-0=0=0+0 0-1=-1=1=0+1 1-0=1=1+0 1-1=0=1+1 in addition, if you take the square of the euclidean norm of a code it's equal to its weight: |00011011|^2=0^2+0^2+0^2+1^2+1^2+0^2+1^2+1^2=1+1+1+1=4 and as he mentioned, the weight of the boolean product can also be thought of as a dot product, so substituting w(x)=|x|^2 and w(xy)=x•y into the weight of sum formula, replacing b1+b2 with b1-b2 since they're equivalent: w(b1+b2)=w(b1-b2)=|b1-b2|^2=w(b1)+w(b2)-2w(b1 b2)=|b1|^2+|b2|^2-2(b1•b2) unrelated side note: every n dimensional (perhaps also infinite dimensional?) vector space has an extension to a geometric algebra G^(n,0,0). i wonder what insights could be gained by looking at the geometric algebra extensions of the vector space in this video
30:39 for even product of w(c1, c2), think back to how we found the correcting bits at the end on the shape and realize that intersecting bands must always intersect on 2 vertices - helped me 😌
oh my ! I'll have to book one hour of my time to completely watch and digest this video that really really talks to me, just at the evocation of a Golay code 7,3. I'll be back with my whole attention !!!
I've had a few lectures by one of the inventors of the compact disc when studying computer science. Could not follow the mathematics. Now here's me hoping my poor brain can grasp your explanation over 25 years later.
That's a very good visualization of this. Especially if you think that the RGB system used everywhere is treated as a 3D vector for computer representation.
Yes, this is correct. RGB systems are actually operating on 3-dimensional spaces similar to a vector space, and the basis vectors are provided by the encodings of the colors red, blue, and green.
around 18:00 I was thinking "why can't you just represent each basis' on/off state as a binary digit and then have the same message in 4 bits instead of 7?" and then I immediately realized that would get rid of the redundancy >_
A little. To elaborate much would require a series of videos in and of itself (which I would love to do in the future) but this planned 4-part series will conclude differently!
Love your videos! I always struggle to find applications of group theory, even just recreational. And I found that books are very academic rigorous, but never getting enough into the application. Any suggestion for a book that dous that?
I find it interesting that the basis code words are analagous to basis vectors, and some of the other terminology is shared. That makes me think about applications of category theory and what the implications are of viewing codes as vectors and vectors as codes; i.e. are there proofs, etc. from either field of study that are applicable to the other? -- That is, you could think of a code as a vector space over the field B (for "boolean"), where B has the values { 0, 1 } and has the outlined properties for addition and multiplication.
Extremely cool! Seeing error correction meeting platonic solids is one of the "how CAN these two things be related" mathematical miracles I long to see
My mistake. It turns out you already done this in your earlier videos. I haven't watched them fully, yet. However, they seem very cool, and I plan on watching them in their entirety soon. Thank you for your awesome videos 👍 Maybe you could try making a short video on how to represent the axioms using symbols?
37:19 I would use a different approach to list all 3|1 cases: your three codes are vertices of a triangle. The edges can be of lentgh 1, 2 or 3. You don't need to look at the icosahedron to list all possibilities and to me it feels more obvious that all possibilities are covered.
Unlike VPNs, password managers actually are a useful tool for improved security. Good to see the VPN trend going away. Everyone deserves to protect their stuff with a good password, regardless of how poor their memory is!
Around 41:30 couldn't you have just concluded u+x+y=z was impossible because the members of the basis are linearly independent by definition? I like the argument you gave with the weight of 5 or 9 and so it can't equal the weight of z which has to be 7. But it seemed unnecessarily complicated given linear independence. Or have I missed something that is preventing us from making the linear independence argument?
Ah but remember here we are saying that u, x, y, z are the right halves of four basis codewords so linear independence doesn't necessarily rule that out!
Criminally under-subscribed. Subbed, liked, set a bell and will be sharing. Your videos is the kinda stuff I come to youtube for. If you need some ideas, I would love to see a video on asymmetric encryption and quantum algorithms.
So the extended Golay Code has an added extra bit and is way cooler... and to tell us about it you've added an extra bit about why that is to the extended Golay video on your way cooler patreon? :3
I don't know if it was intentional, but saying sorry after making that horrible joke about us saying "eh" at the end of sentences was incredibly Canadian.
just to think about how crazy good the golay code is: you have 12 bits of information and 12 bits for error correction. that's enough to send the information twice. but, if you do the naive thing and send the information twice, you could only detect errors, not correct them (you don't know which copy is correct, it might even neither of them!) the golay code uses the same amount of information and error correction, and is able to correct up to 3 bit errors!
31:39 I'm confused - the codes have weight 8? But I can count the ones in the rightmost block - they have 7 ones - 12 vertices on the icosahedron - 5 vertices on the pentagon = 7 ones. I'm clearly misunderstanding, but I've rewound a couple of times..? Is each row of the two blocks together a code word? Ah... 32:50. Ok.
Why is the icosahedron the way to construct this code? Is it at all related to how Hamiltonian paths on n-dimension cubes generate Gray codes? I know Hamming distance shows up there, too.
While I don't know the answer to this particular question, ISBN10 has another nice feature: Flipping two digits (so two errors in the Hamming distance) is also detectable. For ISBN13 that works only if one digit is in an odd position and the other one is in an even position, for example if they're adjacent. I find that neat, because flipping digits seems like a typical human error.
G'day Alex. At 14:40 were you supposed to write 0000 in the 3rd row? {Edit: never mind. I missed that we omit the non-information bits during checkdigit addition. Carry on} {Edit2: why wasn't the 3rd row simply 0000 with 000 as it's checksum?}
No, but I agree that my explanation is a little misleading here! Keep watching and you'll see what I'm getting at, especially at 14:55. The point is that *any* four-digit codeword can be formed from 1000, 0100, 0010, 0001. I was just using 1101 as a guiding example, not what we were adding all four of them together. Hope that helps!
There seems to be some really weird high pitch noises in the audio track around 38:30. Perhaps some high notes from the otherwise background music ending up weirdly loud?
When you reason about the adjacency of the vertices of the icosahedron, I wonder if there is a way to reason about the bands around the vertices instead, to generate fewer cases. The two vertex case only generates two cases, because there are only two kinds of adjacencies for bands. But in the five minutes I've thought about this, I haven't found a way to make the three vertices case easier by reasoning about the bands.
Thanks for watching and thinking about this -- I did think about the number of cases for a long while because I didn't like how clunky that section was. But in the end I couldn't reduce things in an intuitive way -- let me know if you think of anything!
@@AnotherRoof I need to correct myself, there are 3 kinds of adjacencies for 2 bands. But the important part is that they overlap in either 0 or 2 vertices, which is all we care about.
I think you could do that icosahedron construction with the neighborhoods of any graph, so what's special about the icosahedron that it would give rise to an exceptional object like this?
Flatland is a very strange book. It's not really long enough to be a novel, or detailed enough to be hard sci fi, but it's still usually categorized as a hard sci fi novel. It describes itself as a "romance," but there is no romance. And as you say, although it is a satire of English society, it's not a particularly poignant one. What I did like about the book, and I think what most people like, is the playful yet semiserious consideration of how a two-dimensional world could work, such as how people could work out details if everything just looks like a line.
Tbh it's been a while since I've read it. Broadly agree with all points (though I've never heard it being described as hard sci-fi, and you're right it definitely isn't). But I think the observations and consequences of 2D life are interesting.
"Romance", in that time and context, does not mean the same thing as it does today. Originally, it just meant a story written in everyday language (as opposed to ecclesiastical Latin), essentially a non-religious, mundane story. It came to be associated with chivalry and adventure, and from there it took on the connotation of courtly love. All of these senses existed at the time Flatland was written, but in the time since the "adventure" meaning has been lost and only the "love" meaning remains. At least, that's my understanding of the etymology. IANAL (i am not a linguist). See for example "The Romance of the Three Kingdoms", which is what I always think of when I think of "romance" in that old sense of the word, which is a story mostly about warfare and politics in ancient China. anyway i thought flatland sucked tbh
I'd consider it a parable, though I can't put into words precisely how that differs from an allegory. I found it to be very insightful into the general concept of accepting ideas beyond your understanding, with a fun exploration of the concept of dimensions alongside.
Hard disagree, flatland is one of my favorite books. I think its themes of "not knowing what you cant see" by using dimensionality as a metaphor IS very poignant.
I personally prefer ~35 minutes length videos so that I can watch while eating lunch or before go to bed. If the video takes more than 40 minutes or nearly one hour to watch, I have to set up a schedule for that. For these reasons, I suspect making nearly one hour videos may significantly narrow down potential audiences. You can divide videos into 2 or 3 pieces if sub 30 minutes are not enough.
I spend a lot of time wrestling with this, as I discussed on my recent poll. I care more that each video is a self-contained "story" -- here I'd have to cut the video off after establishing a bunch of theory without viewers getting the punchline, which would be unsatisfying. I hope you can watch it over two lunchtimes or something!
If you skipped over the Hamming distance and some other elementary rehash, and you speed up the playback a bit, it wasn't much more than 30 minutes in its present form. Also, you can easily skip over the bit about enumerating distinct sets of three vertices on the icosahedron. You can do that in your mind's eye while brushing your teeth if you've got any choppers at all. I happen to own all the fascicles of Knuth's volume on combinatorics, so maybe that's just me. But no, your first instinct is to change the format globally, because your daily routine is universal. For nearly ten years I listened to a weekly economics podcast with episodes from 60 to 70 minutes (rarely 75). It was never difficult to find an evening where I spent that long in the kitchen cleaning up or preparing dinner at least once.
This is not a great suggestion. He already has to cut off explanations about a topic into multiple parts anyway. If every video was sub-30 minutes, then it would take forever to actually get through the topic.
If the error is in the check digit, then only one of the circles is odd. Which tells the correction algorithm to correct the check digit of that circle. If the error is in d4, then (as shown) all circles are odd. Which means d4 has to be corrected. And if one of d1 through d3 is wrong, then two circles are odd. Which means the digit where those two circles intersect has to be corrected.
8:06-8:11 actually not that bad. You didn't overdo the rhotic "r" like Michael Palin's attempt at a western Pennsylvania dialect in The Meaning of Life. Like, it's not Standard American English, but like RP, no one uses that in daily life except in broadcasting
Oh god, you are totally right >_< I can't believe this! I can't tell you how many times I checked the spelling of the *surname* only to get the first name wrong!
Well spotted! Can't go into all the details here but because it is symmetric on the leading diagonal, it is equal to its own transpose, which means the check bits form an orthogonal matrix, which means it's a self-dual code. I'll leave you to read up on it if you're interested!
I don't fully understand why the 23-bit code is rarely used in comparison to its 24-bit extension. Since the 23-bit code is perfect, it can't really be compressed, which means the best possible compression of the 24-bit code is the 23-bit code. It's less than 5% savings, so maybe that just doesn't turn out to be relevant, but 5% isn't nothing. Why isn't the 23-bit code sent and then expanded at the terminus when necessary?
@@chaoster111 Modern CPUs actually operate on 64-bit words. But that's not really relevant for internet communication anyway. I don't see why transmitting 12 bits in a 24-bit codeword is better than in a 23-bit codeword, especially when virtually all traffic is compressed.
The perfect code has distance 7 not 8 and uses 23 bits not 24. Same dimension of 12. So going to the extended code you pay ~ 4% in storage/transmission but you get back ~ 14% in distance.
@@ipudisciple With a distance of 7 or 8, you can only correct 3 errors either way. If there are 4 errors in a message encoded with a code with Hamming distance 8, there will be at least two valid codewords that you could correct to, each a distance 4 away.
@@EebstertheGreat Yes. I'm not selling the extended code, just describing it, but the ability to detect (not correct) 4 errors means that with high probability you can detect that things are going wrong before they cause too much harm.
Hm... how can these 24-bit/3-byte codes be expressed as a text string... Base-64 is a pretty good text encoding for binary data, so how many base-64 digits would be needed to encode a single codeword...? 2^24 = 16 777 216, which is the number of possible Goley codewords, and 64^4 = 16 777 216... Well, that was easy. So it's possible to write any Goley codeword as 4 characters, each of which is an upper or lower case letter, a decimal digit, or one of 2 symbols. (Most implementations seem to use '+' and '/', but ',', '-', and '_' also seem to be used in some cases.) There's probably a more fitting error correction code for text. In general, I'm curious how possible it is to have a text-based error correction code such that someone can write down a short identitifier in messy handwriting and then have the code successfully correct for various ambiguities in reading said identifier to enter it in.
I'm not sure this is the right place to ask, but I'm gonna a do so anyway - I've almost got my head around the Miller-Rabin Probabilistic Prime algorithm, and all the videos and articles I've found so far don't quite make it as clear and accessible as I'd like. I'm hoping that Another Roof covers it 🤞
Go to nordpass.com/anotherroof to get EXCLUSIVE access to NordPass’ best offer. It’s risk-free with a 30-day money-back guarantee! Or use my promo code anotherroof at checkout.
Ask your questions for the Q&A here: www.reddit.com/r/anotherroof/comments/158a5he/31623_subscriber_qa_ask_your_questions_here/
CLARIFICATIONS & COMMON QUESTIONS:
1. At 0:02 I misspelt the name -- should be Elwyn. Mortified about this one, apologies.
Can't see a single word on your board
Obligatory comment where I don't correct ny typo because there should be a code correcting it
Error correcting codes unfortunately only work if the input starts correct! Garbage in, garbage out :D
so given the correct input, the error correcting codes can always produce a correct output? awesome!
I see what you did theyre
dang bro lets hope the code corrects his new york typo
Correction !equal loss prevention
Oh my gosh, I realized just now (after all of the videos) that these stones with axioms and definitions and proof results are actually our foundations! Nice touch!
@12:32 lol the Vsauce is on point!
Congrats on getting big enough to attract some sponser money! Come a good way in not too short a time, you deserve every bit of success for the consistent quality every time, nailed it from your first 'real' video. Always looking forward to whatever new rabbit hole you'll guide us down next!
I actually hallucinated the vsauce music as soon as he did that.
@@anglaismoyenit actually plays the vsauce music quietly
working on my graduation oral presentation, you just saved my life your lesson is so clear and you helped me understand multiple principles i was going to talk about without really knowing what i was yapping about
Thank you very much and keep going you teach so well !
Wow i dont think i ever truly had the dots connect between linear codes and linear algebra / bases... in my defense the proper look into linear algebra in uni was after the course which featured coding theory (which also included many other things like circuits, hazards and capacitance). Once you started getting at the bases my lightbulb went white and everything clicked into place revealing the magnificent possibilities
That's awesome, thanks sharing! All teachers live for that "lightbulb" moment so great to see it happening even through video 😄
@@AnotherRoof Theyre one of the best experience when learning! I really enjoy that you build up a proper foundation for every video topic, and i watch it even when i think i have the foundation already because quite often i still learn something new. (and knowing which of the multiple definitions are used for certain terms also helps to avoid confusion)
You have me on the edge of my seat with these videos. This is so interesting, I can't wait for the next one, what a cliffhanger!
this did NOT feel like nearly an hour, your presentation style and visual aids make this so easy to sit all the way through in one go without feeling burnt out. I don't know how you keep up this consistent quality but keep doing what you're doing you've made yet another hit :)
Gooooosh I am immediately gets excited when you bring back linear algebra. Unusual vector spaces are so fun! It's just satisfying to see many lin alg theorems works outside of those real or complex matrices that we usually do.
I remember first learning about hamming codes, which there are al sorts of great videos about, then finding out there are even better methods...only to be told that they are so much more complicated I'll basically never understand it lol. There needs to be more educational content about more complex topics like this, it is so amazingly helpful for understanding. Thank you ❤
Wow, these videos are so good - they answer so many questions that I found difficult to figure out myself. And all the connections you show to the different areas of mathematics are mindblowing. Thank you so much for sharing your insights and making these videos. They are truly enlightening!
Comments like this make my day, thank you! Can't wait to share the next videos in the series :D
27:08 Limited bandwidth is as important a consideration in code use for transmission as is limited memory.
This is a great. Such a clear and quick explanation. Thank you for entertaining me for an hour.
ahhh, that's the good stuff. That's what I was waiting for after your steiner system video.
Finally. A cool icosahedron that doesn't constantly roll off my table or makes me fail at an action I should not be failing at all the goddamn time.
As DM: One of my upcoming dungeon puzzles will feature a Golay code application. Can't resist.
Q: does the construction or labeling of your icosohedron arise naturally? (do the actual labels matter? can I use different letterings and still create a valid golay code?) are there instructions to label the icosohedron? (a pdf? especially if the labels matter) Where can one find a good pdf of the original one page paper, the diagram of the S(5,8,24), and other such items...your videos are amazingly thought out, and I'd just like time to digest the original information. Thanks!
Great question regarding the labelling, I wish I'd clarified that in the video. The answer is that the labelling doesn't matter. I chose mine deliberately to generate the nice looking basis on the Wikipedia page for binary Golay code. Choose a different labelling and you'll get a different basis but it will still be a valid Golay code!
References are in the description but might be blocked behind pay walls / institutional access unfortunately. If you do some googling of "miracle octad generator" you'll find a copy of the MOG. I'm actually contemplating making a poster for people to buy...
Hope this helps and thanks for watching 🙂
I f*ckin love your channel. Number theory was already cool but your move to coding theory, which is dear to my heart, is just awesome. You've filled in so many of the blanks in my knowledge. Thanks man.
Love these videos! I'm not a mathematician, and I'm interested in necklace/bracelet combinatorics and it seems like you touched on it here finding all the ways to choose 3 vertices on the icosohedron where all that matters is the shape. For instance, there are only 43 uniquely shaped ways to pick 4 notes on a 12 note keyboard. Is there an easy way to calculate 43 outright?
The best way is to do it separately by symmetry group. With C4 (=shift by 3) symmetry there are 3, or 1 (C, Eb, Gb, A) up to symmetry. With C2 (=shift by 6) symmetry there are (6 choose 2)=15, but 3 of these have C4 symmetry so that leaves 12, which is 2 up to symmetry. Now (12 choose 4)=495 but 3 have C4 and 12 have C2 (and not C4) leaving 480, which is 40 up to symmetry. 40+2+1=43. I didn't need to account for C3 or C6 in this case. The term to search for is "inclusion-exclusion formula".
@AnotherRoof
Since you're talking about coding theory now, can you also make a video on the McEliece cipher? I find it a fascinating story of how one can turn an _error correction_ algorithm into a _public key cryptography_ algorithm, even though those two tasks are seemingly unconnected.
Daaaaamn that would be awesome indeed !!!
Boolean product, also known as the AND operation...
the formula for the weight of a sum looks super familiar.
w(b1+b2)=w(b1)+w(b2)-2w(b1 b2)
now let u and v be vectors in an inner product space. then:
|u-v|^2=|u|^2+|v|^2-2(u•v)
this makes sense. boolean addition (addition mod 2) is identical to subtraction mod 2:
0-0=0=0+0
0-1=-1=1=0+1
1-0=1=1+0
1-1=0=1+1
in addition, if you take the square of the euclidean norm of a code it's equal to its weight:
|00011011|^2=0^2+0^2+0^2+1^2+1^2+0^2+1^2+1^2=1+1+1+1=4
and as he mentioned, the weight of the boolean product can also be thought of as a dot product, so substituting w(x)=|x|^2 and w(xy)=x•y into the weight of sum formula, replacing b1+b2 with b1-b2 since they're equivalent:
w(b1+b2)=w(b1-b2)=|b1-b2|^2=w(b1)+w(b2)-2w(b1 b2)=|b1|^2+|b2|^2-2(b1•b2)
unrelated side note: every n dimensional (perhaps also infinite dimensional?) vector space has an extension to a geometric algebra G^(n,0,0). i wonder what insights could be gained by looking at the geometric algebra extensions of the vector space in this video
This is a rather unnatural way to look at it. The natural way to define the weight of a code word is by using the L1 norm.
It's also the law of cosines, c^2 = a^2 + b^2 - 2 a b cos (theta)
30:39 for even product of w(c1, c2), think back to how we found the correcting bits at the end on the shape and realize that intersecting bands must always intersect on 2 vertices - helped me 😌
of the not, then flip it
It seems clear you like the Extended Golay Code much more than the Perfect Golay Code. Would you say that the Extended Golay Code is more perfect?
oh my ! I'll have to book one hour of my time to completely watch and digest this video that really really talks to me, just at the evocation of a Golay code 7,3. I'll be back with my whole attention !!!
So different style of presentation from 3B1B, but equally good!
Amazing, truly blessed to have such incredibly high quality learning on such otherwise unobtainable concepts. Thankyou Another Roof!
I've had a few lectures by one of the inventors of the compact disc when studying computer science. Could not follow the mathematics. Now here's me hoping my poor brain can grasp your explanation over 25 years later.
16:47 I haven’t ever heard of “Linear Independence”, but the first analogy that came to mind was primary colors
That's a very good visualization of this. Especially if you think that the RGB system used everywhere is treated as a 3D vector for computer representation.
Yes, this is correct. RGB systems are actually operating on 3-dimensional spaces similar to a vector space, and the basis vectors are provided by the encodings of the colors red, blue, and green.
ah! that icosahedron is very nice! i love having shapes as diagrams, and its so cool to have 3d shape as a diagram! i love it! =D
around 18:00 I was thinking "why can't you just represent each basis' on/off state as a binary digit and then have the same message in 4 bits instead of 7?" and then I immediately realized that would get rid of the redundancy >_
will you also elaborate on the connection to the monster in the next part?
A little. To elaborate much would require a series of videos in and of itself (which I would love to do in the future) but this planned 4-part series will conclude differently!
@@AnotherRoof wow i didnt know a fourth part was planned. looking forward to it
Love your videos! I always struggle to find applications of group theory, even just recreational. And I found that books are very academic rigorous, but never getting enough into the application. Any suggestion for a book that dous that?
31, 623 subs eh? Yes that IS a deficient number! ....there will be many more!
I find it interesting that the basis code words are analagous to basis vectors, and some of the other terminology is shared. That makes me think about applications of category theory and what the implications are of viewing codes as vectors and vectors as codes; i.e. are there proofs, etc. from either field of study that are applicable to the other? -- That is, you could think of a code as a vector space over the field B (for "boolean"), where B has the values { 0, 1 } and has the outlined properties for addition and multiplication.
they are called linear codes
4:13 I do love A Series of Unfortunate Events
Thumbs up earned at 6:13 when you state the year 2007 in words as 'twenty-oh-seven'.
nga the delivery in "weight and distance in linear codes" had me weak
I can't help but imagine that the end at 49:01 is how your irl classrooms end up looking like at the end of a lecture.
Extremely cool! Seeing error correction meeting platonic solids is one of the "how CAN these two things be related" mathematical miracles I long to see
Just love your presentation style. The bricks of information are really nice!
My mistake. It turns out you already done this in your earlier videos. I haven't watched them fully, yet. However, they seem very cool, and I plan on watching them in their entirety soon. Thank you for your awesome videos 👍
Maybe you could try making a short video on how to represent the axioms using symbols?
37:19 I would use a different approach to list all 3|1 cases: your three codes are vertices of a triangle. The edges can be of lentgh 1, 2 or 3. You don't need to look at the icosahedron to list all possibilities and to me it feels more obvious that all possibilities are covered.
I like this! I think it might have been simpler than my approach. Thanks for watching!
Subscribed for reference to
sqrt( 1 B ) without ceremony.
Great explanation of the Hamming code. Haven't seen it before.
Unlike VPNs, password managers actually are a useful tool for improved security. Good to see the VPN trend going away.
Everyone deserves to protect their stuff with a good password, regardless of how poor their memory is!
Same! It bugged me to no end how predatory the VPN ads were when, in fact, the justification of "bypass geo restriction" is plenty for most users
Casually pulling out Flatland kinda made my day. :D
Does the "choose 3" operation you're doing around 38:50 have a name when generalised to a graph? Great video!
Around 41:30 couldn't you have just concluded u+x+y=z was impossible because the members of the basis are linearly independent by definition? I like the argument you gave with the weight of 5 or 9 and so it can't equal the weight of z which has to be 7. But it seemed unnecessarily complicated given linear independence. Or have I missed something that is preventing us from making the linear independence argument?
Ah but remember here we are saying that u, x, y, z are the right halves of four basis codewords so linear independence doesn't necessarily rule that out!
Criminally under-subscribed. Subbed, liked, set a bell and will be sharing. Your videos is the kinda stuff I come to youtube for.
If you need some ideas, I would love to see a video on asymmetric encryption and quantum algorithms.
Welcome to the channel!
So the extended Golay Code has an added extra bit and is way cooler... and to tell us about it you've added an extra bit about why that is to the extended Golay video on your way cooler patreon? :3
Golay code! Thank you!
I don't know if it was intentional, but saying sorry after making that horrible joke about us saying "eh" at the end of sentences was incredibly Canadian.
just to think about how crazy good the golay code is:
you have 12 bits of information and 12 bits for error correction. that's enough to send the information twice. but, if you do the naive thing and send the information twice, you could only detect errors, not correct them (you don't know which copy is correct, it might even neither of them!)
the golay code uses the same amount of information and error correction, and is able to correct up to 3 bit errors!
36:14 As a chemist, I'd call them ortho, meta and para :D
31:39 I'm confused - the codes have weight 8? But I can count the ones in the rightmost block - they have 7 ones - 12 vertices on the icosahedron - 5 vertices on the pentagon = 7 ones. I'm clearly misunderstanding, but I've rewound a couple of times..? Is each row of the two blocks together a code word? Ah... 32:50. Ok.
Why is the icosahedron the way to construct this code? Is it at all related to how Hamiltonian paths on n-dimension cubes generate Gray codes? I know Hamming distance shows up there, too.
Hint: how many vertices does an icosahedron have?
Would any adjacency matrix of the icosahedron work? Or does the way the vertices are numbered matter?
damn thats a nice d20
That's the goal, eh? Go lay that pun down in storage and never bring it out again!
If your book has ISBN10 and ISBN13 is that enough to correct two errors?
Wow, this is a great question. I've typed out then subsequently deleted several responses because I keep changing my mind! Let me get back to you!
While I don't know the answer to this particular question, ISBN10 has another nice feature: Flipping two digits (so two errors in the Hamming distance) is also detectable. For ISBN13 that works only if one digit is in an odd position and the other one is in an even position, for example if they're adjacent. I find that neat, because flipping digits seems like a typical human error.
In this topic 10:35 are you saying you can change the values in p1,p2,p3?
If the error is in one of the check digits then yes :)
In practice, when receiving a transmission, how do you do the error correction?
G'day Alex. At 14:40 were you supposed to write 0000 in the 3rd row?
{Edit: never mind. I missed that we omit the non-information bits during checkdigit addition. Carry on}
{Edit2: why wasn't the 3rd row simply 0000 with 000 as it's checksum?}
No, but I agree that my explanation is a little misleading here! Keep watching and you'll see what I'm getting at, especially at 14:55. The point is that *any* four-digit codeword can be formed from 1000, 0100, 0010, 0001. I was just using 1101 as a guiding example, not what we were adding all four of them together. Hope that helps!
There seems to be some really weird high pitch noises in the audio track around 38:30. Perhaps some high notes from the otherwise background music ending up weirdly loud?
It is wonderful how the Levenshtein distance between "Marcel Golay" and "Marcel Golay" is zero.
Q: What is your favourite sequence, and why is it the Catalan Numbers?
When you reason about the adjacency of the vertices of the icosahedron, I wonder if there is a way to reason about the bands around the vertices instead, to generate fewer cases. The two vertex case only generates two cases, because there are only two kinds of adjacencies for bands. But in the five minutes I've thought about this, I haven't found a way to make the three vertices case easier by reasoning about the bands.
Thanks for watching and thinking about this -- I did think about the number of cases for a long while because I didn't like how clunky that section was. But in the end I couldn't reduce things in an intuitive way -- let me know if you think of anything!
@@AnotherRoof I need to correct myself, there are 3 kinds of adjacencies for 2 bands. But the important part is that they overlap in either 0 or 2 vertices, which is all we care about.
See reference 2 in Wikipedia article "Binary Golay code" for Golay's paper
wow, this is really great and helpful!
How about the encoding of the 23 aminoacids by 3 base pairs with 4 letters? Does it have favourable error correcting properties?
I think you could do that icosahedron construction with the neighborhoods of any graph, so what's special about the icosahedron that it would give rise to an exceptional object like this?
Flatland is a very strange book. It's not really long enough to be a novel, or detailed enough to be hard sci fi, but it's still usually categorized as a hard sci fi novel. It describes itself as a "romance," but there is no romance. And as you say, although it is a satire of English society, it's not a particularly poignant one. What I did like about the book, and I think what most people like, is the playful yet semiserious consideration of how a two-dimensional world could work, such as how people could work out details if everything just looks like a line.
Tbh it's been a while since I've read it. Broadly agree with all points (though I've never heard it being described as hard sci-fi, and you're right it definitely isn't). But I think the observations and consequences of 2D life are interesting.
"Romance", in that time and context, does not mean the same thing as it does today. Originally, it just meant a story written in everyday language (as opposed to ecclesiastical Latin), essentially a non-religious, mundane story. It came to be associated with chivalry and adventure, and from there it took on the connotation of courtly love. All of these senses existed at the time Flatland was written, but in the time since the "adventure" meaning has been lost and only the "love" meaning remains.
At least, that's my understanding of the etymology. IANAL (i am not a linguist).
See for example "The Romance of the Three Kingdoms", which is what I always think of when I think of "romance" in that old sense of the word, which is a story mostly about warfare and politics in ancient China.
anyway i thought flatland sucked tbh
I'd consider it a parable, though I can't put into words precisely how that differs from an allegory. I found it to be very insightful into the general concept of accepting ideas beyond your understanding, with a fun exploration of the concept of dimensions alongside.
A term already exists: “light novel”
Hard disagree, flatland is one of my favorite books. I think its themes of "not knowing what you cant see" by using dimensionality as a metaphor IS very poignant.
Thank You
missed opportunity to have a 32,767 sub special :D
Aah yes my favorite youtube channel Aoothar rorf
I personally prefer ~35 minutes length videos so that I can watch while eating lunch or before go to bed.
If the video takes more than 40 minutes or nearly one hour to watch, I have to set up a schedule for that.
For these reasons, I suspect making nearly one hour videos may significantly narrow down potential audiences.
You can divide videos into 2 or 3 pieces if sub 30 minutes are not enough.
I spend a lot of time wrestling with this, as I discussed on my recent poll. I care more that each video is a self-contained "story" -- here I'd have to cut the video off after establishing a bunch of theory without viewers getting the punchline, which would be unsatisfying. I hope you can watch it over two lunchtimes or something!
If you skipped over the Hamming distance and some other elementary rehash, and you speed up the playback a bit, it wasn't much more than 30 minutes in its present form. Also, you can easily skip over the bit about enumerating distinct sets of three vertices on the icosahedron. You can do that in your mind's eye while brushing your teeth if you've got any choppers at all. I happen to own all the fascicles of Knuth's volume on combinatorics, so maybe that's just me.
But no, your first instinct is to change the format globally, because your daily routine is universal.
For nearly ten years I listened to a weekly economics podcast with episodes from 60 to 70 minutes (rarely 75). It was never difficult to find an evening where I spent that long in the kitchen cleaning up or preparing dinner at least once.
I’ve gotten to the point where I don’t care at all about length. If the video is engaging, I’ll stick through it (usually at 2x speed)
This is not a great suggestion. He already has to cut off explanations about a topic into multiple parts anyway. If every video was sub-30 minutes, then it would take forever to actually get through the topic.
I’m usually pretty good on transatlantic/Oceania differences, but how else is Ω pronounced outside UK?
oh-MAY-gah, rather than OH-meh-gah
Can you give an example of how Golay works in practice. Like decode a noisy signal
What I didn’t quite understand from the Hamming Code example is how it can error correct if the error is in the check digit?
If the error is in the check digit, then only one of the circles is odd. Which tells the correction algorithm to correct the check digit of that circle.
If the error is in d4, then (as shown) all circles are odd. Which means d4 has to be corrected.
And if one of d1 through d3 is wrong, then two circles are odd. Which means the digit where those two circles intersect has to be corrected.
8:06-8:11 actually not that bad. You didn't overdo the rhotic "r" like Michael Palin's attempt at a western Pennsylvania dialect in The Meaning of Life. Like, it's not Standard American English, but like RP, no one uses that in daily life except in broadcasting
0:02 The correct spelling is Elwyn Berlekamp.
Oh god, you are totally right >_< I can't believe this! I can't tell you how many times I checked the spelling of the *surname* only to get the first name wrong!
I notice that the matrix of check-bits is symmetric along the diagonal. Is there any significance to that?
Well spotted! Can't go into all the details here but because it is symmetric on the leading diagonal, it is equal to its own transpose, which means the check bits form an orthogonal matrix, which means it's a self-dual code. I'll leave you to read up on it if you're interested!
Excellent video!
12:37 I'm making an alt account to subscribe again
Flatland. Good choice.
This will have serious consequences for the Super Mario 64 speed-running community
Excelente.
Nice
I don't fully understand why the 23-bit code is rarely used in comparison to its 24-bit extension. Since the 23-bit code is perfect, it can't really be compressed, which means the best possible compression of the 24-bit code is the 23-bit code. It's less than 5% savings, so maybe that just doesn't turn out to be relevant, but 5% isn't nothing. Why isn't the 23-bit code sent and then expanded at the terminus when necessary?
CPUs generally operate in 8 bit chunks and 24-bit is a nice multiple of 8.
@@chaoster111 Modern CPUs actually operate on 64-bit words. But that's not really relevant for internet communication anyway. I don't see why transmitting 12 bits in a 24-bit codeword is better than in a 23-bit codeword, especially when virtually all traffic is compressed.
The perfect code has distance 7 not 8 and uses 23 bits not 24. Same dimension of 12. So going to the extended code you pay ~ 4% in storage/transmission but you get back ~ 14% in distance.
@@ipudisciple With a distance of 7 or 8, you can only correct 3 errors either way. If there are 4 errors in a message encoded with a code with Hamming distance 8, there will be at least two valid codewords that you could correct to, each a distance 4 away.
@@EebstertheGreat Yes. I'm not selling the extended code, just describing it, but the ability to detect (not correct) 4 errors means that with high probability you can detect that things are going wrong before they cause too much harm.
Hm... how can these 24-bit/3-byte codes be expressed as a text string... Base-64 is a pretty good text encoding for binary data, so how many base-64 digits would be needed to encode a single codeword...? 2^24 = 16 777 216, which is the number of possible Goley codewords, and 64^4 = 16 777 216... Well, that was easy. So it's possible to write any Goley codeword as 4 characters, each of which is an upper or lower case letter, a decimal digit, or one of 2 symbols. (Most implementations seem to use '+' and '/', but ',', '-', and '_' also seem to be used in some cases.)
There's probably a more fitting error correction code for text. In general, I'm curious how possible it is to have a text-based error correction code such that someone can write down a short identitifier in messy handwriting and then have the code successfully correct for various ambiguities in reading said identifier to enter it in.
cool
I'm not sure this is the right place to ask, but I'm gonna a do so anyway - I've almost got my head around the Miller-Rabin Probabilistic Prime algorithm, and all the videos and articles I've found so far don't quite make it as clear and accessible as I'd like.
I'm hoping that Another Roof covers it 🤞
That's not an Icosahedron, that's a Great Dodecahedron :P
Absolutely! I considered making a model of a great dodecahedron but deemed it too difficult and settled for this kind of labelling!
Well made video. Wow.
This implementation in AI will make people think Computers are sentient. I think people should start speaking as sober as possible
listening to this in the background while i pretend to understand what you're talking about
If you keep all your passwords with NordPass you’re still just one data breach away from losing everything..
when will THE INVESTIGATION... into numbertheory continue
his ikosahedron looks like made out of printed paper on cardboard, where can i get this printout?
Unfortunately I made it by hand!
ouchie, brain. but awesome video