Data Compression


Criteria

Survey Formats

Basics

Basic Terms

Variable Length Codes

Interpretation

Prefix Codes

Distribution of Code Lengths

Code Trees

Compression Methods

Data Formats


Glossary

Index


Download


www.BinaryEssence.com

Prefix Codes (Prefix Property)


Prefix Property:
No code word is the prefix
of any other code word.

Coding schemes constructed according to the prefix property are unambiguously decodable at any time. Such a code will be called a prefix code.


Example:

   a  -  0
   b  -  10
   c  -  110
   d  -  111

No one of the shorter sequences '0' and '10' are used as the leading part of any other code. If a decoder will find such a sequence in a data stream, the code can unambiguously be assigned to the particular symbol.


Any code representable by a code tree has the prefix property provided that the codes are assigned to the leaf nodes. Moreover a variety of other coding schemes exist that are also unambiguously decodable but not belonging to the class of prefix codes.


Example:

    a   -   1
    b   -   10
    c   -   100
    d   -   1000

 <   ^   > 

 Code Trees 

Variable Length Codes Interpretation Distribution of Code Lengths