Shorter codes for frequent characters

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. In variable-length coding, which character gets the shortest bit code?

A The most frequent character

B The rarest character

2. A message uses 4 different characters. A fixed-length code needs 2 bits per character. How many bits does a 100-character message take?

A 400 bits

B 200 bits

3. Which step comes first when building a variable-length code?

A Count how often each character appears

B Give every character a 1-bit code

4. In the message AAAAAAAB, which code assignment saves more bits?

A A = 0, B = 10

B A = 10, B = 0

5. Message: AAAAAAAB. With A = 0 and B = 10, the total is 9 bits. A fixed 2-bit code would use 16 bits. What does this show?

A Fixed-length coding used fewer bits

B Variable-length coding used fewer bits

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1A=0, B=10, C=11		AThe shortest code (0) was given to B, which is rarer. The most frequent letter A should get the 1-bit code, so A=0 and B=10.
29 letters x 2 bits = 18 bits		BA variable-length code: the most common letter A gets a 1-bit code, and the rarer letters B and C get 2-bit codes.
3Counting character frequencies in AAAAAABBC shows which letter is most common and should get the shortest code.		C6x1 + 2x2 + 1x2 = 12 bits (fixed: 18 bits)
4Comparing total bits shows the variable-length code (A=0, B=10, C=11) uses fewer bits than a 2-bit fixed code for AAAAAABBC.		D12 is less than 18, so the variable-length code is smaller. The fixed-length code is the larger one.
5A=10, B=0, C=11 (A appears 6 times, B twice)		EA:6, B:2, C:1
612 bits vs 18 bits, so the fixed-length code is smaller		FThe total bits for a 9-letter message when a fixed-length code uses 2 bits for every character.

Definitions

variable-length coding

Fill in the Blanks

Complete each line of code by filling in the missing parts.

Message: AAAABBC Count of A = _

Fixed: 7 characters x 2 bits = __ bits

Most common letter gets the ________ code

A: 4 x 1 = 4 B: 2 x 2 = 4 C: 1 x 2 = _

10 bits _ 14 bits, so variable saves space

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A message = AAAAAABBC

B fixed code = 2 bits each

C fixed total = 9 * 2 = 16 bits

Question 2

A message = AABAACAD

B count A = 5

C count B = 2

D count C = 1

Question 3

A A = 00 (most common)

B B = 10

C C = 11 (rare)

Question 4

A A: 5 times, code 0 (1 bit)

B B: 1 time, code 10 (2 bits)

C C: 1 time, code 11 (2 bits)

D total = 5*1 + 1*2 + 1*2 = 8

Question 5

A Fixed: 1 bit for 4 letters

B Message has 10 characters

C Total = 10 * 2 = 20 bits

Answer Key

Shorter codes for frequent characters

Section A: Quick Questions

A — The most frequent character

B — 200 bits

A — Count how often each character appears

A — A = 0, B = 10

B — Variable-length coding used fewer bits

Section B: Match the Pairs

A=0, B=10, C=11 → A variable-length code: the most common letter A gets a 1-bit code, and the rarer letters B and C get 2-bit codes.

9 letters x 2 bits = 18 bits → The total bits for a 9-letter message when a fixed-length code uses 2 bits for every character.

Counting character frequencies in AAAAAABBC shows which letter is most common and should get the shortest code. → A:6, B:2, C:1

Comparing total bits shows the variable-length code (A=0, B=10, C=11) uses fewer bits than a 2-bit fixed code for AAAAAABBC. → 6x1 + 2x2 + 1x2 = 12 bits (fixed: 18 bits)

A=10, B=0, C=11 (A appears 6 times, B twice) → The shortest code (0) was given to B, which is rarer. The most frequent letter A should get the 1-bit code, so A=0 and B=10.

12 bits vs 18 bits, so the fixed-length code is smaller → 12 is less than 18, so the variable-length code is smaller. The fixed-length code is the larger one.

Section C: Definitions

variable-length coding — Gives common characters short bit codes and rare ones longer codes, so a whole message uses fewer bits than if every character used the same fixed number of bits.

Section D: Fill in the Blanks

Message: AAAABBC
Count of A = 4

Fixed: 7 characters x 2 bits = 14 bits

Most common letter gets the shortest code

A: 4 x 1 = 4
B: 2 x 2 = 4
C: 1 x 2 = 2

10 bits < 14 bits, so variable saves space

Section E: Spot the Error

C — The message has 9 characters and each uses 2 bits, so the fixed-length total is 9 * 2 = 18 bits, not 16.

C — B appears only once in AABAACAD, so the count should be 1. Counting frequencies correctly is the first step in giving the common characters shorter codes.

A — The most common character should get the shortest code. A should be 0 (1 bit), not 00 (2 bits), which is no shorter than the codes for the rare characters.

D — Multiply each count by its code length and add: 5 + 2 + 2 = 9 bits, not 8.

A — One bit only gives 2 patterns (0 and 1). To give 4 different letters their own fixed-length code you need 2 bits each, which is what the total of 10 * 2 = 20 uses.