Scribd
Upload
3 views8 pages

Compression Coding Solved Problems

The document provides examples of various compression coding techniques including Run Length Coding (RLC), Shannon-Fano Coding, and Huffman Coding. It illustrates how to compress sequences of characters and binary data, as well as how these methods are applied in JPEG encoding. Each example includes the input data, the process of encoding, and the final compressed output.

Uploaded by

ahmedala198ggggg
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views8 pages

Compression Coding Solved Problems

The document provides examples of various compression coding techniques including Run Length Coding (RLC), Shannon-Fano Coding, and Huffman Coding. It illustrates how to compress sequences of characters and binary data, as well as how these methods are applied in JPEG encoding. Each example includes the input data, the process of encoding, and the final compressed output.

Uploaded by

ahmedala198ggggg
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Solved Problems on Compression

Coding
Run Length Coding (RLC) - Example 1

Input sequence: A A A A B B C C C C C D D A A A
• Step 1: Count consecutive repetitions.
• A appears 4 times → (A,4)
• B appears 2 times → (B,2)
• C appears 5 times → (C,5)
• D appears 2 times → (D,2)
• A appears 3 times → (A,3)
• Final RLC output: (A,4) (B,2) (C,5) (D,2) (A,3)
Run Length Coding (RLC) - Example 2
Input binary sequence:
111111100000001111000
• Count runs of identical bits.
• 7 ones → (1,7)
• 7 zeros → (0,7)
• 4 ones → (1,4)
• 3 zeros → (0,3)
• Compressed output: (1,7) (0,7) (1,4) (0,3)
Shannon–Fano Coding - Example

• Symbols and probabilities: A=40, B=30, C=20, D=10

• Step 1: Divide symbols into two groups with nearly equal


probabilities.
• Group 1: A(40), B(30) → assign 0
• Group 2: C(20), D(10) → assign 1

• Further divide Group 1:


• A → 00, B → 01
• Further divide Group 2:
• C → 10, D → 11
Shannon–Fano Coding - Final Codes

• Final Shannon–Fano codes are:


• A = 00
• B = 01
• C = 10
• D = 11
• Average code length = 2 bits/symbol
Huffman Coding - Example
• Symbols and probabilities: A=40, B=30, C=20, D=10
• Combine lowest probabilities: D(10)+C(20)=DC (30)
• Combine 30 with B(30) → BDC (60)
• Combine 60 with A(40) → 100

• Assign 0 to lower branch and 1 to higher branch.


• Generated codes:
• A=0
• B = 10
• C = 111
• D = 110

Average code length =1*0.4+2*0.3+3*0.2+3*0.1=1.9 bits/symbol


RLC Used in JPEG - Example 1
• Input vector: [12, 0, 0, 5, 0, 0, 0, -3, 2, 0, 0, 1]
• JPEG RLC stores pairs: (number of preceding zeros,
value)

• 12 → (0,12)
• After two zeros, 5 → (2,5)
• After three zeros, -3 → (3,-3)
• After zero zeros, 2 → (0,2)
• After two zeros, 1 → (2,1)
• Final output: (0,12) (2,5) (3,-3) (0,2) (2,1)
RLC Used in JPEG - Example 2

• Input vector: [7, 0, 0, 0, 4, 0, -2, 0, 0, 6, 0, 0, 0, 0, …..]

• 7 → (0,7)
• Three zeros before 4 → (3,4)
• One zero before -2 → (1,-2)
• Two zeros before 6 → (2,6)
• Final encoded pairs: (0,7) (3,4) (1,-2) (2,6) (0,0)

You might also like