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 !
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 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)
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!
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.
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 🙂
@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
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.
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 >_
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?
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!
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 😌
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
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.
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.
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.
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
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!
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.
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!
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!
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.
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.
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.
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?
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?
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.
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.
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.
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 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.
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'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 🤞
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.
But it's not really a Canada joke. Excessive use of "eh?" was an Ontario thing, centered around the Ottawa region as I recall. Then Bob and Doug made a think out of it, along with hockey and six-packs, and toques and hosers. "Sorry" is a Canadian thing.
@afterthesmash as a Canadian, I'm aware of the memes and origins of our sayings. I do use eh occasionally, not in the way of this video though. Still, it's not very conductive to argue about this, eh? Sorry.
Consider the set {0, 1}, and define ⊕ : {0, 1}^2 -> {0, 1} by 0 ⊕ X = X ⊕ 0 = X and 1 ⊕ 1 = 0, and define • : {0, 1}^2 -> {0, 1} by 1 • X = X • 1 = X and 0 • 0 = 0. ({0, 1}, ⊕, •) is a field, and it is the Galois field of order 2, also called the Boolean field, which is denoted F(2). Now, let n be a natural number, expresed as a set. Let C(n) be some nonempty set of functions f : n -> {0, 1}, and define + : C(n)^2 -> C(n) such that for all m in n, (f + g)(m) = f(m) ⊕ g(m), and · : {0, 1}×C(n) -> C(n) such that for all m in n, (k·f)(m) = k•f(m). (C(n), +, ·) is a vector space over the field F(2), and this vector space is the definition of a binary linear code. The functions in C(n) are the words of the code, and n is the length of all the words. This vector space can be equipped with the L1 norm, the taxicab norm, with w : C(n) -> [0, ∞), such that w(f) = Σ{|f|}. This norm is called the weight of a word. Thus, binary linear code is defined as Boolean normed space.
Assuming that the Data bits and the parity bits are going to be sent through the same channel, how can we know that the parity bit won't contain errors? Also you really look like Icelandic singer Björk.
It can correct three errors regardless of the position (whether they are data bits or parity bits doesn't matter). And I guess I'll take that as a compliment..?
