Multimedia and Text Compression
First part of the deck Multimedia Basics (up to PNG): what multimedia is, its application areas and industries, then lossless text compression with Huffman coding, LZ77 and LZSS, with fully worked examples.
Course mapSearch on YouTube
The course has five units. This page and the next two cover Unit 1.
| Unit | Theme | What it deals with |
|---|---|---|
| 1 | Multimedia | Evolution of multimedia, encoding and compression techniques |
| 2 | Multimedia | QoS and the operating system |
| 3 | Security | Security principles for multimedia; methods to ensure CIA |
| 4 | Forensics | Digital forensics fundamentals, standards, best practices, evidence handling |
| 5 | Forensics | Source identification techniques |
The syllabus topics per unit:
- Introduction: application areas, interdisciplinary aspects, multimedia data encoding, data compression.
- QoS and operating system: requirements and constraints, QoS concept, resource management, media server architecture, storage management, services, protocols, layers.
- Security in multimedia applications: security attacks, multimedia encryption, steganography, digital image watermarking, multimedia authentication.
- Multimedia evidence handling: forensic labs in operation, standards and best practices, evidence extraction, multimedia file carving.
- Device and source forensics: camera model identification, printer and scanner forensics, microphone forensics, content forensics.
| Component | Item | Weight (%) |
|---|---|---|
| Theory | Mid semester | 25 |
| Theory | Continuous assessment (quiz 20 + assignment 10) | 30 |
| Theory | End semester | 45 |
| Lab | Mini project | 20 |
| Lab | Continuous assessment | 10 |
What is multimediaSearch on YouTube
The deck opens with a quiz. Which of these is multimedia: an interactive e-book, a high-resolution image, a silent video, an animation, a text document, an infographic? The answer slide marks the interactive e-book and the infographic. Each of them combines several media types. A single image, a silent video or a plain text file uses one medium only.
Multimedia is the integration of various forms of media, such as text, images, audio, video and animations, to convey information or entertainment in a digital format. The elements work together synergistically and improve the user experience.
"Multimedia is the seamless integration of various forms of digital media, including text, images, audio, video, and animations, to convey information or entertainment in a digital format."
Components of multimediaSearch on YouTube
| Component | Meaning on the slide |
|---|---|
| Text | Written words that convey information |
| Audio | Sound or music that enriches the auditory experience |
| Animation | Dynamic, interactive visual elements that add a layer of engagement |
| Video | Moving images and sequences that convey a narrative |
| Image | Visual representations: photographs, graphics and illustrations |
Tired Ants Always Visit India: Text, Audio, Animation, Video, Image.
The five components of multimedia, in the order the slide draws them.
Application areasSearch on YouTube
| Area | How multimedia is used |
|---|---|
| Computing | Software and user interfaces with videos, animations and audio |
| Telecommunications | Video conferencing and virtual reality meetings; better remote interaction |
| Publishing | Interactive e-books and digital magazines with video, animation and sound |
| Television / broadcasting | High-quality graphics, animations and interactive segments |
| Entertainment and fine arts | Digital art installations, video games, interactive exhibits |
| Education | E-learning through interactive lessons, educational videos, virtual simulations |
| Engineering | Visualising complex designs with 3D modelling and virtual prototyping |
| Mathematical and scientific research | Data visualisation and simulation of complex data |
| Medicine | Medical training and patient education with 3D models, videos and VR |
| Social media | Sharing of images, videos, live streams and interactive stories |
Interdisciplinary aspectsSearch on YouTube
Four industries drive multimedia.
| Industry | Slide point |
|---|---|
| Telecommunication | Originally focused on telephony; now relies heavily on digital networks |
| Consumer electronics | Known for "brown ware"; has reduced the cost of video technology |
| TV and radio broadcasting | Leads in professional audio-video technology |
| Publishing companies | Offer publications in electronic form; now content in multiple forms |
Key observationsSearch on YouTube
Hardware to software shift:
- Most computer components are modified or extended to support multimedia applications.
- Processor performance keeps increasing.
- Storage becomes a concern for high-quality media.
Fault tolerance and speed:
- Fault tolerance is critical in real-time multimedia systems.
- Conventional data processing must be completed as fast as possible.
- Components of a multimedia system are not independent. The slide shows a sports broadcast chain: capturing the sport (camera, microphone), on-site production (mixing, switching, graphics, replays), encoding and compression, signal transmission (satellite, cables), broadcasting. A fault in one stage breaks the chain.
Why compress textSearch on YouTube
Uncompressed text uses a fixed number of bits per character. Compression removes redundancy so the same message takes fewer bits.
Message size of "Mississippi" (11 characters)
Step 1. ASCII uses 8 bits per character: bits.
Step 2. The message has only 4 distinct characters (m, i, s, p). A fixed-length code needs bits per character: bits.
Step 3. Huffman coding (below) needs 21 bits. It beats the fixed-length code because frequent letters get shorter codes.
Huffman codingSearch on YouTube
Huffman coding is a lossless compression algorithm. It assigns variable-length codes to input characters. The length of each code depends on the frequency of the character:
- Higher-frequency characters get fewer bits.
- Lower-frequency characters get more bits.
No code is a prefix of another code, so the decoder can split the bitstream without separators.
StepsSearch on YouTube
- Build the frequency table. Arrange the characters in ascending order of frequency.
- Select the two nodes with the least frequency.
- Combine them into a new node whose frequency is the sum.
- Repeat steps 1 to 3 until a single tree remains.
- Label every left edge 0 and every right edge 1. The code of a character is the path from the root to its leaf.
Huffman code for "Mississippi"
Step 1. Frequencies: m = 1, p = 2, s = 4, i = 4. Sorted: 1m, 2p, 4s, 4i.
Step 2. Combine the two smallest, 2p and 1m, into a node of weight 3. List: 3, 4s, 4i.
Step 3. Combine 4s and 3 into a node of weight 7. List: 4i, 7.
Step 4. Combine 4i and 7 into the root, weight 11.
Step 5. Label edges (left 0, right 1) and read the codes.
| Character | Frequency | Code | Code length |
|---|---|---|---|
| m | 1 | 111 | 3 |
| p | 2 | 110 | 3 |
| s | 4 | 10 | 2 |
| i | 4 | 0 | 1 |
Step 6. Total bits: bits.
Step 7. Average bits per character: .
When two nodes have equal weight, the tree shape can differ between solutions. The code lengths and the total bit count stay the same. Examiners accept any valid tree, so state your tie rule and stay consistent.
Practice questions from the deckSearch on YouTube
Question 1: bits saved. A message has a = 5, b = 9, c = 12, d = 13, e = 16, f = 45 (100 characters, 1 byte each). How many bits does Huffman coding save?
Step 1. Merge: 5 + 9 = 14; 12 + 13 = 25; 14 + 16 = 30; 25 + 30 = 55; 45 + 55 = 100.
Step 2. Code lengths: f = 1, c = 3, d = 3, e = 3, a = 4, b = 4.
Step 3. Huffman bits: bits.
Step 4. Original: bits. Saved: bits.
Question 2: build the tree for A = 50, B = 10, C = 30, D = 5, E = 3, F = 2.
Step 1. Merge F + E = 5; then (5) + D = 10; then 10 + B = 20; then 20 + C = 50; then 50 + A = 100.
Step 2. Code lengths: A = 1, C = 2, B = 3, D = 4, E = 5, F = 5.
Step 3. Total for 100 symbols: bits, or 1.85 bits per symbol.
Question 3: decode with Fibonacci frequencies. a = 1, b = 1, c = 2, d = 3, e = 5, f = 8, g = 13, h = 21. Decode 110111100111010.
Step 1. Each merge adds the next Fibonacci number, so the tree is a "ladder". Codes: h = 0, g = 10, f = 110, e = 1110, d = 11110, c = 111110, a and b = 1111110 / 1111111.
Step 2. Split the bits: 110 11110 0 1110 10.
Step 3. Read: f, d, h, e, g. The message is fdheg.
GATE CSE 2017 (Set 2, Q50). Alphabet P, Q, R, S, T with probabilities 0.22, 0.34, 0.17, 0.19, 0.08. Expected length of a 100-character message?
Step 1. Merge T + R = 0.25; S + P = 0.41; 0.25 + Q = 0.59; 0.41 + 0.59 = 1.
Step 2. Code lengths: P = 2, Q = 2, S = 2, R = 3, T = 3.
Step 3. Average: bits per character.
Step 4. For 100 characters: bits.
LZ77 (LZ1) encodingSearch on YouTube
LZ77 is a lossless, dictionary-based method. It uses a sliding window to find and encode repeated patterns in a data stream. The window has two parts:
- Search buffer: the text already encoded. It acts as the dictionary.
- Look-ahead buffer: the text still to be encoded.
The encoder looks for the longest string in the search buffer that matches the start of the look-ahead buffer. It outputs a triplet (offset, length, next symbol):
- Offset: distance counted back from the dividing line between the search buffer and the look-ahead buffer.
- Length: number of characters matched.
- Next symbol: the first character after the match.
If nothing matches, the output is (0, 0, c) where c is the current character.
LZ77 says "go back offset characters and copy length characters, then add this new character". The match may run past the dividing line into the look-ahead buffer. The decoder copies one character at a time, so overlapping copies still work.
Encode cabracadabrarrarrad, window 13, look-ahead 6 (search buffer ).
| # | Already encoded (search side) | Look-ahead starts | Match | Token |
|---|---|---|---|---|
| 1 | (empty) | cabrac | none | (0, 0, c) |
| 2 | c | abraca | none | (0, 0, a) |
| 3 | ca | bracad | none | (0, 0, b) |
| 4 | cab | racada | none | (0, 0, r) |
| 5 | cabr | acadab | "a" 3 back | (3, 1, c) |
| 6 | cabrac | adabra | "a" 2 back | (2, 1, d) |
| 7 | abracad (last 7) | abrarr | "abra" 7 back | (7, 4, r) |
| 8 | adabrar (last 7) | rarrad | "rarra" 3 back, overlapping | (3, 5, d) |
Step 1. Rows 1 to 4: no earlier occurrence, so each is a literal triplet.
Step 2. Row 5: "a" occurs 3 positions back. The next text "c" does not extend the match, so (3, 1, c).
Step 3. Row 7: "abra" starts 7 back, at the far end of the search buffer. The next character is "r", so (7, 4, r).
Step 4. Row 8: "rar" starts 3 back and the copy continues into the look-ahead: r, a, r, r, a. Length 5, next "d".
Output: (0,0,c) (0,0,a) (0,0,b) (0,0,r) (3,1,c) (2,1,d) (7,4,r) (3,5,d). Eight tokens for 19 characters.
Exercise: repetitive_repeat, search buffer 11, look-ahead 4.
| # | Covers | Token | Reason |
|---|---|---|---|
| 1 | r | (0, 0, r) | new |
| 2 | e | (0, 0, e) | new |
| 3 | p | (0, 0, p) | new |
| 4 | e t | (2, 1, t) | "e" is 2 back |
| 5 | i | (0, 0, i) | new |
| 6 | t i v | (2, 2, v) | "ti" is 2 back |
| 7 | e _ | (6, 1, _) | "e" is 6 back |
| 8 | r e p e a | (11, 4, a) | "repe" is 11 back |
| 9 | t | (10, 1, EOF) | "t" is 10 back; nothing follows |
Nine tokens for 17 characters. The slide writes the end-of-input marker as a dollar sign.
LZ77 decodingSearch on YouTube
The decoder keeps the output so far. For each triplet it goes back offset characters, copies length characters one at a time, then appends the next symbol.
Decode (0,0,c) (0,0,a) (0,0,b) (0,0,r) (3,1,c) (2,1,d) (7,4,r) (3,5,d)
Step 1. First four tokens give cabr.
Step 2. (3,1,c): 3 back is "a"; copy it, add c: cabrac.
Step 3. (2,1,d): 2 back is "a"; add d: cabracad.
Step 4. (7,4,r): 7 back starts "abra"; add r: cabracadabrar.
Step 5. (3,5,d): 3 back is "r". Copy r, a, r, r, a one by one (each copied character becomes available). Add d: cabracadabrarrarrad.
LZSS encoding and decodingSearch on YouTube
LZSS is an improvement of LZ77. LZ77 wastes space: every unmatched character costs a full triplet (0, 0, c). LZSS outputs two kinds of token:
- a literal: the character itself, when there is no match;
- a pointer
(offset, length): when a match is found. There is no "next symbol" field.
A flag bit tells the decoder which kind comes next. The lab used the form (0, character) for a literal and (1, distance, length) for a reference.
LZSS on repetitive repeat, window 15 (search 11, look-ahead 4).
Step 1. r, e, p have no match: three literals.
Step 2. e occurs 2 back: pointer (2, 1).
Step 3. t, i: literals. Then ti occurs 2 back: pointer (2, 2).
Step 4. v: literal. e occurs 6 back: pointer (6, 1). The space: literal.
Step 5. repe starts 11 back: pointer (11, 4). Then a: literal. The last t is 10 back: pointer (10, 1).
Encoded: r e p (2,1) t i (2,2) v (6,1) ␣ (11,4) a (10,1). That is 7 literals and 6 pointers, 13 tokens against 9 triplets for LZ77, and each token is smaller.
Decoding reads left to right. A literal is written out. A pointer copies length characters from offset back. The output grows as r, re, rep, repe, repet, repeti, repetiti, ..., repetitive repeat.
The deck uses a pointer even for a one-character match. In a real LZSS coder a pointer costs more bits than a literal. The coder then sends a pointer only when the match is long enough to save space (the break-even length). State which rule you use in the exam.
ComparisonSearch on YouTube
| Property | Huffman | LZ77 | LZSS |
|---|---|---|---|
| Type | Statistical (entropy) coder | Dictionary, sliding window | Dictionary, sliding window |
| Exploits | Unequal symbol frequencies | Repeated strings | Repeated strings |
| Output | Variable-length bit code per symbol | Triplet (offset, length, next) | Literal or pointer (offset, length) plus flag bit |
| Needs code table? | Yes, the tree must be known to the decoder | No | No |
| Weak case | Uniform frequencies | Short or non-repetitive text | Very low redundancy |
| Used in | JPEG, PNG (final stage) | Basis of LZSS | PNG (with Huffman, that is DEFLATE) |
Exp 1 and 2: text compression in Python.
- Exp 1 (LZSS): scan the text with a sliding window, find the longest match in the dictionary, emit
(0, character)for a literal and(1, distance, length)for a reference. The decompressor expands references and must rebuild the input exactly. - Exp 2 (Huffman): build the tree from character frequencies, generate prefix codes, encode the text to a bit string and decode it back. The lab result notes that Huffman efficiency depends on the frequency distribution: skewed text compresses well, uniform text barely compresses.
Quick self-testSearch on YouTube
Define multimedia and list its five components.
Multimedia is the seamless integration of various forms of digital media to convey information or entertainment in a digital format. Components: text, audio, animation, video and image.
Which four industries make up the interdisciplinary aspects of multimedia?
Telecommunication, consumer electronics, TV and radio broadcasting, and publishing companies.
Why are fault tolerance and speed key concerns for multimedia systems?
Real-time multimedia must meet timing constraints, so fault tolerance is critical. Processing must finish as fast as possible. The components are not independent, so a fault in one stage (capture, production, encoding, transmission) breaks the whole chain.
"Mississippi": how many bits for ASCII, fixed-length and Huffman coding?
ASCII: bits. Fixed-length (4 symbols, 2 bits): 22 bits. Huffman (i = 0, s = 10, p = 110, m = 111): 21 bits, average 1.909 bits per character.
Why is a Huffman code uniquely decodable without separators?
It is a prefix code. Every symbol is a leaf of the tree, so no codeword is the start of another codeword. The decoder walks the tree and outputs a symbol each time it reaches a leaf.
What do the three fields of an LZ77 token mean?
Offset: distance back from the dividing line between search and look-ahead buffer. Length: number of matched characters. Next symbol: the first character after the match.
Window 13, look-ahead 6. What is the search buffer size?
characters.
How does LZSS improve on LZ77?
LZ77 sends a full triplet even for an unmatched character. LZSS sends either a bare literal or an (offset, length) pointer with no next-symbol field. A flag bit distinguishes the two, so unmatched characters cost far less.
Decode the LZ77 tokens (0,0,a) (0,0,b) (2,4,c).
ab, then go back 2 and copy 4 characters one at a time: a, b, a, b. Add c. Result: abababc.
A file has 4 symbols with equal frequency. Will Huffman coding help?
No. All four codes get length 2, the same as a fixed-length code. Huffman gains only when frequencies are unequal.
- Multimedia integrates text, audio, animation, video and images in digital form.
- Four industries shape it: telecommunication, consumer electronics, broadcasting, publishing.
- Real-time multimedia needs fault tolerance and speed; its components depend on each other.
- Huffman coding gives short codes to frequent symbols; build the tree by merging the two smallest nodes.
- "Mississippi": 88 bits (ASCII), 22 bits (2-bit fixed), 21 bits (Huffman), 1.909 bits per character.
- LZ77 emits (offset, length, next symbol); search buffer = window minus look-ahead.
- LZSS emits a literal or an (offset, length) pointer with a flag bit, so it wastes less on unmatched characters.
- These lossless coders return in JPEG (Huffman) and PNG (LZSS plus Huffman) on the next page.