Information Theory and Coding

9/17/2014

Information Theory and Coding

ECE533

Overview
Source Coding Techniques
Huffman Coding
Source Coding

jaj
Run Length
Lempel-ziv
Arithmetic
Shannon-Fano
Nikesh Bajaj
[email protected] JPEG: Image Compression
Asst. Prof., ECE Dept.
Digital Signal Processing
Lovely Professional University 2 By Nikesh Bajaj

Source Coding
Source Coding
Aim ??
Ba

Huffman Coding
David A. Huffman
August 9, 1925 October 7, 1999
Ohio State University, MIT
sh
X xi
1952 paper "A Method for the Construction of
Minimum-Redundancy Codes"
Minimum number of bits that completely
represent the symbol.

3 By Nikesh Bajaj 4 By Nikesh Bajaj

ke

Huffman Coding Huffman Coding

Ni

Algorithm

5 By Nikesh Bajaj 6 By Nikesh Bajaj

1
Information Theory and Coding
9/17/2014

Huffman Algorithm Huffman Coding

Observed Parameters
Entropy H

jaj
Average Length R
Efficiency of the code

7 By Nikesh Bajaj 8 By Nikesh Bajaj

Source coding: Classification

Classification of Source coding
Majorly there are two
Fixed Length and Variable Length Coding
Ba Examples
Symbol

x1
x2
x3
Probability

0.37
0.33
0.16
Self-Information

1.4344
1.5995
2.6439
Code word

0
10
110
Lossless and Lossy Compression
sh
x4 0.07 3.8365 1110
Other x5 0.04 4.6439 11110
x6 0.02 5.6439 111110
Prefix Code or Instantaneous Codes
x7 0.01 6.6439 111111

H(X)=2.1152
R=2.1700
N=H/R=2.1152/2.1700=0.9747

9 By Nikesh Bajaj 10 By Nikesh Bajaj

ke

Huffman Coding Problems

Ni

VLC DAP for Huffman algorithm.

Code is not unique Take a page of english charactors and
Efficiency near to 1 compress it using Huffman algorithm then
Prefix Code check all the quantitive parameters i.e. H, R,
efficiency.
Loss less Coding

11 By Nikesh Bajaj 12 By Nikesh Bajaj

2
Information Theory and Coding
9/17/2014

Problem: Combining two symbols Huffman Coding: Variant

Symbol Probability Self-Information Codeword n-ary Huffman coding
x1 0.5 1 1
x2 0.3 1.737 00
Huffman coding for not binary but for ternary,
or n-ary techniques

jaj
x3 0.2 2.3219 01
For ternary
H(X)=1.4855, R =0.9903, =0.9903 Combine 3 least probabilities rather than 2
Group two symbols and calculate same Assign 3 symbols at 3 nodes as 0, 1, 2 rather than 2
symbols as 1, 0
Conclude whether combining increase the
Use log with base 3 rather than 2
efficiency or not
Similarly Huffman can be extended to n-ary
13 By Nikesh Bajaj 14 By Nikesh Bajaj

Huffman Coding: Variant

Adaptive Huffman

Home work to get to know the details
All students are advised to go through detail of
Ba Run Length Coding
It is used when long sequence of Ones and Zeros
comes in the signal
Example
Adaptive Huffman 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1
sh
(7) (0) (3) (1) (6) (0) (0)
Or
11111111111111100000000000000000001111
(15,1), (19,0), (4,1)
(01111,1) , (10011,0), (00100,1)
15 By Nikesh Bajaj 16 By Nikesh Bajaj
ke

Runlength Run length Coding

Case -1 FLC
Ni

Long runs of 0s

Loss less Coding
Case -2
Long runs of 1s
Good for certain applications only
Case -3 Applications
Long runs of 0s and 1s Binary images
Speech coding silence coding in speech communication
Runlength for non-binary source


Video transmission
M=aaaaabbbabaaabbbbbbaabbbbabcbbbbcbad FAX

M=abababababababbababababaabababababa
17 By Nikesh Bajaj 18 By Nikesh Bajaj

3
Information Theory and Coding
9/17/2014

Lemple-Ziv Algorithm (LZW) 1977 Lemple-Ziv Algorithm (LZW) 1977

No need of symbol probability Lets consider Dict. Dict. FL-
Location Content Codeword
Huffman is good for DMS, not for source with memory 101011011010101011 000 -

j
No statistics require, 001 1 0001
010 0 0000
011 10 0010

aja
100 11 0011
101 01 0101
110 101 0111
111 010 1010
Abraham Lempel Jacob Ziv Terry A. Welch
- 1011 1101

19 By Nikesh Bajaj 20 By Nikesh Bajaj

Lemple-Ziv Algorithm B Fundamental of Image

Image : is a matrix of unsigned integer

Black & White image binary image (1 bit/pixel)
Gray scale Image 8bits/pixel
Color Image 24bits/pixel
sh

21 By Nikesh Bajaj 22 By Nikesh Bajaj

ke

BW- Binary image

Image Compression
Ni

Image: dpi 4x4 image

Redundancy?
Gray scale image Spatial Correlation
Spectral Correlation
Temporal Correlation

Color image

By: Nikesh Bajaj

23 By Nikesh Bajaj 24

4
Information Theory and Coding
9/17/2014

RGB to YCrCb RGB image

jaj
25 By: Nikesh Bajaj

Transform Coding Ba

JPEG:
Still Image Compression Standard
JPEG: Joint Photographic Experts Group
Formally: ISO/IEC JTC1/SC29/WG1

International
Working Group 1
(JBIG,JPEG)
sh
organization for
Standardization Joint ISO/IEC
Technical Sub-committee 29
International Committee (Coding of Audio,
Electro-technical (Information Picture, Multimedia
Commission Technology) and Hypermedia
information
Work commenced in mid-1980s.
Draft international standard 1991.
Widely used for image exchange, WWW, and digital photography.
ke

Image Compression Standard JPEG:Encoder and Decoder

Ni

By: Nikesh Bajaj

29

5
Information Theory and Coding
9/17/2014

JPEG: Image Partitioning JPEG:Basic Algorithm

jaj
JPEG: Quantization Table Ba JPEG: Differential coding of DC
sh
ke

Entropy Coding for AC Comp. Image Compression

Run Length Introduction to image compression
Ni

Huffman DCT Transform
N 1 M 1
k l
y (k , l ) 4 I (i, j ) cos (2i 1) cos (2 j 1)
i 0 j 0 2N 2M
JPEG standard
For Lossless Compression
For Lossy Compression

35 By Nikesh Bajaj 36 By Nikesh Bajaj

6
Information Theory and Coding
9/17/2014

DCT of an Image DCT -Problem

Compute DCT of
x = [1 1 2 1]

j
x= [ 1123 12]

aja
37 By: Nikesh Bajaj 38 By: Nikesh Bajaj

DCT of an Image

DCT
50

100
B 250

200

150
JPEG: Example

100
sh
150

50

200

39 By: Nikesh Bajaj

ke

JPEG: Example JPEG: Example

Ni

7
Information Theory and Coding
9/17/2014

JPEG: Decoding
JPEG: Example
The DC coefficient is DPCM coded (difference
between the DC coefficient of the previous block
and current block)

jaj
The AC coefficients are mapped to run-length
pairs: (run,value)
(0,5),(0, -3),(0, -1),(0,- 2),(0, -3),(0,1),
(0,1),(0, -1),(0, -1),(2,1),(0,2),(0,3),(0, -2),
(0,1),(0,1),(6,1),(0,1),(1,1), EOB
These are then Huffman coded (codes are
specified in the JPEG scheme)

JPEG: Decoding Ba JPEG: Original Vs reconstructed

Image
sh
ke

JPEG:
Example Image Compression
Ni

By: Nikesh Bajaj

48

8
Information Theory and Coding
9/17/2014

JPEG ITU T.81 Standard JPEG -Conclusion

Different coding All the Steps of JPEG
8x8 block Why Level offset?

jaj
artifacts Why zig-zag scanning?
Why differential Coding?
Why DCT transform?

By: Nikesh Bajaj

49 50 By Nikesh Bajaj

Arithmetic Coding Ba Arithmetic Coding

+
P(A) = 0.5 P(B) = P(C) = 0.25
Msg = BACA
sh
51 By Nikesh Bajaj 52 By Nikesh Bajaj
ke

Problems: Encoding Problem: Decoding

P(1) = P(0) = P(A) =0.5 P(B) =0.2 P(C) =0.3
Ni

Msg = 110101011010101 Code =0.21625

53 By Nikesh Bajaj 54 By Nikesh Bajaj

9
Information Theory and Coding
9/17/2014

Problem Shannon Fano-Elias Coding

Consider a message Pdf
M = ababbaaaabbbccccbbaaabbccccd Cdf
Compress the message M using Huffman, Runlength and

jaj

Lempel ziv algorithm show the compressed message

55 By Nikesh Bajaj 56 By Nikesh Bajaj

Sym
Shannon Fano-Elias Coding

Prob F(x) F(x) F(x)bin l(x) codeword

Ba Shannon Fano-Elias Coding

Sym Prob F(x) F(x) F(x)bin l(x) codeword
sh

x1 x1 0.5 0.25 0.01 2 01
x2 ^2 x2 ^2 0.75 0.625 0.101 3 101
x3 ^3 x3 ^3 0.875 0.8125 0.1101 4 1101
x4 ^ 3 x4 ^ 3 1 0.9375 0.1111 4 1111

57 By Nikesh Bajaj 58 By Nikesh Bajaj

ke

Compression Problems Compression Problems

Consider an 4x4 image M
Consider a message
Ni

6 7 8 8
M = ababbaaaabbbccccbbaaabbccccd 6 6 8 8

Compress message M by following algorithm and show M= 6 3 3 3

3 3 2 1
the compressed message
Huffman Compress message M by following algorithm and show
Arithematic the compressed message
Runlength Huffman, Arithmetic, Runlength
Lempel-Ziv Lempel-Ziv, Shannon Fano
Shannon Fano Compare all the out put by computing compression
Compare all the out put by computing compression ratio of each
ratio of each Compute entropy of message M
59 By Nikesh Bajaj 60 By Nikesh Bajaj

10