Shortest Message Encoding

Overview

Students will create a system to encode a specific message using the fewest number of bits possible. Then students will encode that message in a chain of paper rings.

There are many ways to encode messages, our goal with this lesson is to encode a message with the fewest number of bits.

Purpose

The purpose of this lesson is to have students explore alternate ways of encoding information. The goal is to write a message in the fewest number of bits in a way that it can be decoded by someone else.

Objectives

Students will be able to:

• Create a system to encode messages
• Encode a message using their own system
• Decode a message using a system developed by another group
• Compare efficiencies of the various systems.

Preparation

• Create several messages for students to encode.
• Messages should have 8 or fewer distinct letters for best results.
• Print the Shortest Message Challenge - 1 per group
• Print the Shortest Message Legend sheets
• Cut strips of paper. Each group will need 120 strips of two colors (60 of each color)
• Tape - 1 per group

Links

• For the Teacher
  • Huffman Coding - https://en.wikipedia.org/wiki/Huffman_coding
• For the Students

Vocabulary

Huffman Encoding - A technique for creating encoding where frequently used letters have shorter encoding.

Teaching Guide

Getting Started

Introduce the idea of encoding a message using fewer bits. Every letter in ASCII takes 1 byte or 8 bits, if we tailor the code to the message, could we improve that and make our message shorter?

Activity

Break the class into groups of 3. As a group they will have a unique message and will be tasked with making an encoding that uses the fewest number of bits.

Once they have generated their encoding, they will use the strips of paper to create interlocking rings that are the encoded message.

Finally, once groups have their encoding, they can swap legends and rings with another group and try to decode the other message.

Wrap-up

Discussion:

1. What advantages does this system have in comparison to ASCII?
2. What disadvantages does it have?
3. In what kinds of situations might the two types of systems be appropriate?

Show Huffman Encoding and describe how it is used.

• https://www.youtube.com/watch?v=dM6us854Jk0

Assessment Questions

• Given that Huffman encoding is more efficient, why is it not used more frequently?
• What types of messages would suffer under the Huffman encoding scheme?

Extended Learning

Standards Alignment

License

Cyber Security Curriculum is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.