Error-Correcting Codes(Like Hamming codes etc) with Combinatorial Games

[InigoMontoya314]

About the authors

More about us in #124

About my mathematics and coding theory background: I did spent considerable effort and have some expertise in the subject of coding theory. I first learnt about it in a summer school, then wrote an award-winning research paper on lexicographic code, which is why I'm making this pitch.

We just want to put our background here to add a bit legitimacy, as although we are high schoolers, we are quite good at the subjects we want to make our videos in.

Quick Summary

Do you know that many famous error-correcting codes, like the Hamming code, can actually be constructed using combinatorial games? The two seemingly unrelated areas actually have an elegant connection! In the 1980s, mathematician J. H. Conway and N. J. Sloane discovered a family of codes called lexicographic code(lexicodes), which are codes created from combinatorial games. For example, Hamming code are known to be lexicographic, and the game associated with it is called turning turtles. I did a research project during summer on it and really loved this. (Should I post this on 3B1B subreddit as a topic suggestion maybe? I feel like he might find this interesting... I heard that's where Grant get his ideas from.)

Target medium

A 3B1B-style video using manim. We are somewhat-okay manim users ourselves, but we'd love to have more professional content creators to help us make the project.

More details

More on Topic 1:

Imagine you have a row of seven turtles in front you, each one of them is either at their head (H) or on its back(T for tail). You are playing a game with your opponent Bob. In each move, you can turn a turtle from T to H, and you can choose to also turn one other turtle that is on the right of that one(doesn't need to be next to), either from H to T or T to H. For example, these are legitimate moves:

HHTHHTH -> HHHHHTH HHTHHTH -> HHTHHHT HHTHHTH -> HHHHHHH

How will you win this game? It turns out, if we denote H as 0 and T as 1, you can force a win as long as in your turn, you always move to the codewords of the [7,4,3] Binary Hamming code!

There are also many other lexicodes that are connected to combinatorial games like this.

A few links:

Wikipeida: although brief, but talks about the greedy generation of lexicodes and its backgrounds.

Section III B Conway and Sloane: the paper that discovered lexicodes and talks more about the games I mentioned in the comments.

The game turning turtle(and other coin turning games) is mentioned in Winning Ways for Your Mathematical Plays, Vol 3, by Berlekamp, Conway and Guy. Though I can't find an online pdf for it, it's quite accessible to see how to win the game(even for me as a high schooler) so I can explain if anyone is interested.

Contact details

Github is fine for now, but if you are interested in making a video with us then we can talk a bit more using email and stuff like that.

Additional context

Check #124 for more about us, and our interests.

(Any additional licensing information? If you do not say anything, this post will be considered CC-BY.)

[3b1b]

That sounds pretty interesting, what are some other examples of error-correcting code and game pairs like this?

[InigoMontoya314]

That sounds pretty interesting, what are some other examples of error-correcting code and game pairs like this?

There are many others. For coin turning games(like turning turtle, except instead of flipping turtles we flip coin to avoid animal cruelty, according to Conway), basically you can modify the games such that instead of only turning at most two turtles, you can turn d-1 turtles (d is the minimal distance of the code) to create other codes. Notable ones include

1. The Extended Hamming Code(connected with the game Mock Turtle)
2. Extended Quadratic Residue Code(connected with Moebius)
3. Extended Golay code(the one used in NASA's Voyager I and II, connected with Mogul). etc.

There is another type of game called Grundy's game that Conway and Sloane used to constructs lexicodes, but it's a different type of construction(and less intuitive in my opinion than coin turning games, so would need a lot more space to explain).

Let me know if anyone needs more info, or papers(if you have background in coding theory) on this topic. See my edits to the original posts for a few links.

[finedesignvideos]

That was a very interesting read about lexicodes. :) What exactly are you looking to convey in the video and what are you looking for in a content producer?

[InigoMontoya314]

That was a very interesting read about lexicodes. :) What exactly are you looking to convey in the video and what are you looking for in a content producer?

Hi! Thank you for your interest! I'm thinking to talk about the turning turtle game first and how to solve the game by doing some analysis to the game, then make a twist and aha moment to unveil its connection with Hamming code. Ultimately, the video should explain both the turning turtle game itself, and how we can use games like this one to construct lexicode. A wider message could to be to show how different seemingly unrelated areas of math can have cool connections.

For content producer, I'm thinking about clean, smooth animations(like Manim which I prefer) and 3b1b-style math explanations. Also I'm not native English speaker, so I would hope if someone can voiceover for me(however I can still do it if you are not native in English either)? I would also appreciate if you can edit video since I'm not experienced in that. However, I can plan the video, write scripts, do the math part, etc. So if that's what you are interested let me know and we can talk a bit more!

[InigoMontoya314]

That sounds pretty interesting, what are some other examples of error-correcting code and game pairs like this?

Also to Grant thanks so much for your interest in this topic and for your work on the SoME in general, because this is really cool! I didn't realise it was you commenting at first glance :)