Multimedia_Lossless Data Compression

Digital information

• Huge amount of data
• Lossy and lossless algorithm

Lossless compression(무손실 압축)

• Less compression ratio < Lossy
• No information or quality loss- good for text compression(Zip), professional audio(FLAC)

Lossy compression(손실 압축)

• Higher compression ratio > Lossless
• JPEG image, MP3 audio, MPEG video

 

무손실 압축 --> Entropy Coding --> Run-Length Encoding(RLE), Shannon-Fano, Huffman 존재 

 

Entropy and Coding Basics

Principle of information theory: 일어날 확률이 낮은 사건은 빈번하게 일어나는 사건보다 정보가 더 많다.

 

'Sunrise in the morning' --> High probability event = Low information

 

'Solar eclipse this morning' --> Low probability event = High information

 

Measure of information(unit- bits)

Entropy

n개의 information을 다 더해서 평균을 구하면 entropy 값이 나온다.

• Average amount of information to the possible outcomes in certain event, Shannon in 1948

• Entropy: data compression 할 때 필요한 최소 bit 수

ex) Transmission of string sequences 'A', 'B', 'C', 'D' over a channel

 

using the entropy formula, entropy=2bits

at least 2 bits in average to encode each character

A='00', B='01', C='10', D='11' (codeword)

 

ex) if P(A)=0.6, P(B)=0.2, P(C)=0.1, P(D)=0.1

 

using the H(X), entropy = 1.57bits

Entropy가 낮을수록 압축률이 늘어난다.(데이터가 편향적일수록 entropy가 낮음)

 

Coding basics(알아야 할 단어)

• Data compression
• Data decompression(압축 된 데이터를 다시 복원하는 것)
• Encoder: HW or SW that does compression
• Decoder: HW or SW that does decompression
• Codec(COderDECoder): 코더와 디코더의 결합 단어
• Codeword: Binary bits assigned to each symbol as a result of encoding or data compression algorithm

Prefix property 

In the process of encoding and decoding, each encoded codeword must provide a unique decoded symbol.

'No codeword is prefix of any other codeword'

Binary Tree

0- left branch, 1- right branch

 

Run-Length Encoding(RLE)

• Simplest. 
• Fax, JPEG

ex) 

14 letter string "ABAAAABCBDDDDD"

 

--> "ABA4BCBD5"

 

If we use 8-bit ASCII code to represent each symbol, 

 

"ABAAAABCBDDDDD" = 14 x 8 = 112 bits

 

"ABA4BCBD5" = 9 x 8 = 72 bits

 

thereby saving 40 bits

 

In this case, the compression ratio can be calculated by

 

Compression ratio = (Original size in bits/ Compressed size in bits): 1

= (112/72):1 

 

Shannon-Fano Coding

ex) 

Information source S. {A, B, C, D, E} with frequency counting {15, 7, 6, 6, 5}.

Compression ratio: 

since the total frequency is 39, original text string size is 39 x 8 bits = 312 bits.

 

Shannon-Fano = 2 x 15 + 2 x 7 + 2 x 6 + 3 x 6 + 3 x 5 = 89 bits

 

= (312/89):1 = 3.5:1 

 

Huffman Coding

Suppose we have a string of symbols 'AAAABBCD'

 

Verifying Huffman encoding results

• Backtrack Huffman tree from the leaf to the top in left to right fashion to list out weight lists
• If the weight list lies in increasing order, correct coding
  • weight list is "D1 C1 2 B2 4 A4 8"
• Finally, check the prefix property

LZ77 coding