Huffman Encoding: Wheel of Fortune Style

Information Theory (Winter 2020)

by Katherine Kowalski, Calvin Lin and Yasmeen Jassim

Introduction & Motivation

From sending text messages to searching for recipes on the internet, millions of devices connect and communicate information every minute. But how is this information communicated? This quarter, we set out to teach Ravenswood Middle School students how information is communicated through encoding and decoding. Through our interactive game, “Huffman’s Wheel of Encoding”, we hoped to teach the students the basics of encoding and decoding through our version of Wheel of Fortune.

Huffman’s Wheel of Fortune

Prior to making our game, we thought about the most important concepts we wanted to teach the students. We identified several outcomes that would allow them to engage with encoding/decoding in an effective way and help them understand that communication processes aren’t always smooth. Slots on the wheel each represent different outcomes which manipulate the player’s bitstream.

We created a multi-player program that allows players to input their letter (in the form of a codeword) as well as the number of points their guess is worth. Our program keeps track of each player’s total points and declares a winner at the end of the game. We also made an “Encoding Wheel” mimicked after Wheel of Fortune and constructed the Huffman encoding for the English alphabet based on the probabilities of each letter being in a word (included in the cheat sheet, figure 1.1).

How To Play

Like in the game show, a category to the phrase or word is given. Until a player wants to guess the word, the entire game is communicated in bits that constitute a codebook for the alphabet. Each contestant is given a decoder sheet (figure 1.1) and they must communicate which letter they are guessing by searching for its codeword and entering this codeword into our program. Before each contestant makes a guess, they must spin the wheel (figure 1.2). As mentioned, the wheel has various slots that represent positive or negative consequences. Depending on the consequence they receive, they must guess a letter with that consequence in mind.

Figure 1.2: Wheel of Encoding

Possible Outcomes

Negative Consequences manipulate your bitstream (input you give the program):

Bit flip: One bit in a symbol sequence has a X% chance of being the wrong bit. Randomize which bit is flipped.

Truncate 2: The last 2 bits of all coming letters are truncated – last 2 bits are lost. This could hurt especially if the codes are prefix coded.

Bankruptcy: Lose all points and don’t get to guess a letter.

Lose Turn: Player loses their turn.

Positive Consequences take the form of bonus points or a chance me card:

Bonus Points (+500, +200 etc): Point values that you get if you correctly guess the letter.

Increased Bit Rate (bonus card): Can guess 2 consonants instead of 1 without penalty (increase the number of bits you send in a row).

Bit Repetition: If a given code word has suffered a negative consequence, can use this card to send over the bit stream again with each bit repeated x times.

Error Correcting Code: If transmitted code is incorrect, the student can tell us the bit to correct.

Figure 1.3: Playing the game!

Overall, we tried to combine an important topic in Information Theory with a popular game show we all know and love. We hope the students are Ravenswood get a chance to play our game in the future!

Want to play the game yourself? Grab a friend, make your own wheel (if you’re ambitious enough) and check out our program here! Check out our video for a more in depth explanation of key concepts and a demonstration of how to play the game!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s