SENG1050 Chap.10 Encoding, Error Checking and Compression
Encoding, Error Checking and Compression
This chapter follows the Week 10 lecture, whose lab marks Huffman coding and the cyclic redundancy check as certain exam content. It covers binary encoding, ASCII and Unicode, parity and its limits, and the CRC by modulo-2 division.
It then compares lossless and lossy compression, run-length encoding and prefix codes, and works a full Huffman encoding with the compression amount, before surveying dictionary compression and audio, image and video formats.
Every number in the worked examples here is original and recomputed, so you can check each step of your own working against them, from the appended zeros of a CRC to the final bit count of a Huffman message.
What this chapter covers
- 01
Encoding, ASCII and Unicode
- 02
Even and odd parity
- 03
CRC by modulo-2 division
- 04
Lossless versus lossy compression
- 05
Run-length encoding
- 06
Prefix codes and Huffman trees
- 07
Compression amount and exact ratio
- 08
Dictionary compression and media formats
Worked example · free
Compute a CRC by modulo-2 division and check it
- 1Write the generator as 1001. It has four bits, so append three zeros to the message: 110101000.
- 1XOR the generator under each leftmost 1 in turn. The running results are 010001000, 000011000, 000001010 and 000000011.
- 1The remainder is the last three bits, 011, so the sender transmits the message followed by 011: 110101011.
- 1The receiver divides 110101011 by 1001 and gets remainder 000, so no error is detected.
Key terms
- Parity bit
- A parity bit is an extra bit that makes the total number of ones even or odd so single-bit errors can be detected.
- Cyclic redundancy check
- A cyclic redundancy check appends the remainder of a modulo-2 division by a shared generator so the receiver can detect errors.
- Generator polynomial
- A generator polynomial is the divisor shared by sender and receiver in a CRC, written as its binary coefficients.
- Lossless compression
- Lossless compression reduces size so that decompression returns exactly the original data.
- Lossy compression
- Lossy compression discards detail people cannot perceive, returning data close to but not identical to the original.
- Prefix code
- A prefix code is a set of codes in which no code is the beginning of another, so decoding is unambiguous.
- Huffman coding
- Huffman coding builds a binary tree from symbol frequencies so frequent symbols get shorter codes.
- Run-length encoding
- Run-length encoding writes each run of repeated symbols as a count followed by the symbol.
- Modulo-2 division
- Modulo-2 division is binary long division that uses XOR in place of subtraction, with no carries or borrows.
Encoding, Error Checking and Compression FAQ
How is the compression amount calculated for a Huffman question?
Assume each character normally takes 8 bits, so the original size is the number of characters times 8. The compression amount is 1 minus the compressed bits divided by the original bits, which you can give as a fraction and a percentage. State which way round you write any ratio.
Does it matter which way I break ties when building a Huffman tree?
Different tie choices can give different trees and codes, but the total number of bits for the message is always the same. State the rule you used, keep left as 0 and right as 1 throughout, and check the total by multiplying each frequency by its code length.
Why can parity miss an error?
Parity only tracks whether the count of ones is even or odd. If two bits flip, the count keeps its parity, so the corrupted byte passes the check. Stronger methods such as the cyclic redundancy check catch many errors that parity misses.
How many zeros do I append before a CRC division?
Append one fewer zero than the number of bits in the generator, which is the same as the highest power in the generator polynomial. A generator of 1011, from x^3 + x + 1, has four bits, so append three zeros and expect a three-bit remainder.
Which compression topics are marked as exam content?
The Week 10 lab marks the Huffman encoding and CRC calculation tasks as certain exam content and marks the gzip exercise as optional and not in exams. Lossless versus lossy compression, run-length encoding and the audio and image formats remain lecture content for theory questions.
Exam move
Rehearse the two certain exam methods until they are mechanical. For Huffman, take a short word, count letters, build the tree, write the code table, encode, count the bits and compute the compression amount, then decode your own answer. For the CRC, divide one new message each day and check it at the receiver. Learn the JPEG steps and the lossless and lossy contrast as short lists.
Time yourself on one full Huffman question and aim to finish it, with the ratio, inside fifteen minutes.
Working through Encoding, Error Checking and Compression in SENG1050? Sia is AskSia’s AI Computer Science tutor — ask any SENG1050 Encoding, Error Checking and Compression question and get a clear, step-by-step explanation grounded in how SENG1050 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
