Communications Fundamentals FAQ / Chapter 3

3.8.9 What Is Entropy Coding?

1. What Is Entropy Coding?
2. Why Is Entropy Coding Important?
3. What Is Information Content?
4. What Is Entropy?
5. Why Do Common Symbols Require Fewer Bits?
6. What Is a Variable-Length Code?
7. What Is a Prefix Code?
8. What Is Huffman Coding?
9. How Does Huffman Coding Work?
10. What Is Arithmetic Coding?
11. Why Is Arithmetic Coding More Efficient?
12. What Is Adaptive Entropy Coding?
13. Is Entropy Coding Lossless?
14. Where Is Entropy Coding Used?
15. How Does Entropy Coding Relate to Source Coding?
16. Can Entropy Coding Reach the Entropy Limit?

One of the central objectives of source coding is to represent information as efficiently as possible. Whenever information is transmitted or stored, engineers seek to reduce the number of bits required while preserving the original content. This objective becomes increasingly important as communications systems carry larger volumes of voice, video, images, and data.

One of the most powerful techniques for achieving efficient representation is entropy coding. Unlike many compression techniques that exploit characteristics of specific signal types, entropy coding relies on a fundamental observation: some symbols occur more frequently than others. By assigning shorter codewords to common symbols and longer codewords to rare symbols, entropy coding can reduce the average number of bits required to represent information.

Entropy coding forms the foundation of many modern compression systems and appears in applications ranging from ZIP files and image compression to digital television and streaming media. It is also closely linked to one of the most important concepts in communications theory: entropy, introduced by Claude Shannon as a measure of information content.

What Is Entropy Coding?

Entropy coding is a form of lossless compression that represents information using variable-length codewords.

The basic idea is simple. Suppose a source generates several different symbols. If some symbols occur much more frequently than others, it is inefficient to assign every symbol the same number of bits. Instead:

• Frequently occurring symbols receive short codewords.
• Rare symbols receive longer codewords.

Because common symbols occur most often, the average number of bits required per symbol is reduced.

The original information can still be recovered exactly, making entropy coding a lossless compression technique.

Why Is Entropy Coding Important?

Many sources generate symbols with unequal probabilities.

For example, in English text:

• The letter E occurs much more frequently than Z.
• Spaces occur more frequently than many letters.
• Common words occur far more often than rare words.

If every symbol were assigned a fixed-length code, many bits would be wasted. Entropy coding exploits these probability differences to reduce average bit rate. The result is:

• Reduced storage requirements.
• Reduced transmission bandwidth.
• Increased network capacity.
• Improved compression efficiency.

Consequently, entropy coding plays an important role in many communications systems.

What Is Information Content?

To understand entropy coding, it is useful to examine the concept of information.

In information theory, an unlikely event conveys more information than a highly predictable event. For example:

• Seeing the sun rise tomorrow conveys little new information because it is highly expected.
• Learning that a lottery ticket has won first prize conveys much more information because it is unlikely.

In general:

• Rare events contain more information.
• Common events contain less information.

This observation forms the basis of entropy coding.

What Is Entropy?

Entropy is a measure of the average information content of a source.

It was introduced by Claude Shannon in 1948 as part of the foundation of modern information theory. For a source producing symbols with certain probabilities, the information content of a symbol is defined as:

$\begin{array}{c}I={\log }_2\frac{1}{p}\left(\text{bits}\right)\end{array}$

where p is the probability of occurrence of the symbol. A less probable symbol conveys more information than one that occurs frequently.

The total information, I_t, contained in a set of M symbol is the sum of the information in the individual symbols. That is:

$\begin{array}{c}{I}_t={\sum }_{i=1}^M{p}_{i}M{\log }_2\frac{1}{p_i}\left(\text{bits}\right)\end{array}$

The average information content per symbol is the entropy, E, which is defined as:

$\begin{array}{c}E=\frac{I_t}{M}={\sum }_{i=1}^M{p}_i{\log }_2\frac{1}{p_i}\left(\text{bits per }\text{symbol}\right)\end{array}$

Entropy represents the theoretical minimum average number of bits required to represent the source without losing information.

No lossless coding system can achieve a lower average bit rate than the source entropy.

For this reason, entropy is often described as the ultimate compression limit.

Why Do Common Symbols Require Fewer Bits?

Consider a source producing only four symbols:

A fixed-length code would require 2 bits per symbol because four symbols require four unique binary combinations. However, A occurs half of the time.

Assigning a shorter codeword can reduce the average bit rate substantially. For example:

The average number of bits per symbol becomes: [0.5(1)+0.25(2)+0.15(3)+0.10(3) = 1.75 bits}, which is significantly lower than the fixed-length value of 2 bits.

What Is a Variable-Length Code?

A variable-length code uses codewords of differing lengths.

Examples include:

• Common symbols → short codewords.
• Rare symbols → long codewords.

Variable-length coding is the defining feature of entropy coding. The challenge is to design the code so that the receiver can uniquely determine where one codeword ends and the next begins.

Fortunately, techniques exist that guarantee unambiguous decoding.

What Is a Prefix Code?

Most practical entropy coders employ prefix codes. A prefix code has the property that no codeword forms the beginning of any other codeword.

For example:

This is a prefix code because:

• 0 is not the prefix of any other codeword.
• 10 is not the prefix of another codeword.
• 110 is not the prefix of another codeword.

Prefix codes allow symbols to be decoded immediately without ambiguity.

What Is Huffman Coding?

The most famous entropy-coding technique is Huffman coding.

Developed by David Huffman in 1952, Huffman coding produces an optimal prefix code for a known set of symbol probabilities. The procedure involves:

1. Listing symbols and probabilities.
2. Combining the least probable symbols.
3. Constructing a binary tree.
4. Assigning binary digits to branches.
5. Reading codewords from the completed tree.

The resulting code minimizes the average codeword length among all prefix codes.

Because of its simplicity and effectiveness, Huffman coding remains widely used today.

How Does Huffman Coding Work?

Suppose we have four symbols:

The two least probable symbols are combined first. A binary tree is then constructed progressively until a single root node remains. Traversing the tree produces codewords such as:

The most probable symbol receives the shortest codeword. Less probable symbols receive longer codewords.

The average code length approaches the entropy of the source.

What Is Arithmetic Coding?

Although Huffman coding is extremely effective, it has limitations.

In particular, codeword lengths must be whole numbers of bits. Arithmetic coding overcomes this restriction. Instead of assigning codewords to individual symbols, arithmetic coding represents an entire message as a single fractional number between 0 and 1.

As symbols are processed, the range associated with the message becomes progressively smaller. The final fractional value uniquely identifies the entire message.

Arithmetic coding often achieves compression closer to the theoretical entropy limit than Huffman coding.

Why Is Arithmetic Coding More Efficient?

Consider a symbol whose ideal code length is 1.4 bits. Huffman coding cannot assign a fractional number of bits. It must use either 1 bit, or 2 bits.

Arithmetic coding effectively allows fractional average code lengths. As a result, its performance can approach the entropy limit more closely.

For highly compressed multimedia systems, this advantage can be significant.

What Is Adaptive Entropy Coding?

Many practical systems do not know symbol probabilities in advance.

Adaptive entropy coding addresses this problem by continuously updating probability estimates as data is processed. Advantages include:

• No prior statistical knowledge required.
• Automatic adaptation to changing data characteristics.
• Improved performance for diverse data sources.

Many modern compression systems employ adaptive techniques.

Is Entropy Coding Lossless?

Yes.

Entropy coding does not discard information. Every symbol can be reconstructed exactly. This distinguishes entropy coding from lossy compression methods such as:

• JPEG images.
• MP3 audio.
• MPEG video.

Entropy coding is therefore widely used when exact reconstruction is required.

Where Is Entropy Coding Used?

Entropy coding appears in numerous applications.

• File compression. ZIP and similar utilities rely heavily on entropy coding.
• Image compression. JPEG employs entropy coding after other compression stages.
• Video compression. MPEG, H.264, H.265, and related standards use entropy coding extensively.
• Data communications. Many communications systems incorporate entropy coding to reduce transmission rates.
• Storage systems. Entropy coding helps reduce storage requirements in databases and archives.

In many modern systems, entropy coding is the final stage of the compression process.

How Does Entropy Coding Relate to Source Coding?

Entropy coding is one of the most important categories of source coding.

Its objective is to remove statistical redundancy by exploiting unequal symbol probabilities.

Other source-coding methods may:

• Predict future samples.
• Transform signals into another domain.
• Model source behavior.

Entropy coding is often combined with these techniques to achieve even greater compression.

For example, modern image and video coders typically:

• Remove spatial or temporal redundancy.
• Quantize the resulting data.
• Apply entropy coding.

The entropy coder extracts the remaining statistical redundancy.

Can Entropy Coding Reach the Entropy Limit?

It can approach the limit but never surpass it.

Shannon's source-coding theorem states that the entropy of a source represents the theoretical minimum average number of bits required for lossless representation. A practical entropy coder may approach this limit very closely. However:

• It cannot do better than entropy.
• No lossless coding technique can represent information using fewer bits on average than the entropy allows.

This result is one of the most important principles in communications theory.

Why Is Entropy Coding Important?

Entropy coding provides a direct link between information theory and practical communications systems.

It demonstrates how knowledge of source statistics can be used to reduce transmission rates and storage requirements while preserving information exactly.

By assigning short codewords to common symbols and long codewords to rare symbols, entropy coding achieves compression that approaches the theoretical limits established by Shannon's information theory.

For this reason, entropy coding remains one of the most powerful and widely used techniques in modern digital communications.

Summary

Entropy coding is a lossless source-coding technique that reduces average bit rate by assigning short codewords to frequently occurring symbols and longer codewords to rare symbols. It is based on the information-theoretic concept of entropy, which defines the theoretical minimum average number of bits required to represent a source.

Techniques such as Huffman coding and arithmetic coding are widely used in communications, multimedia, and data-storage systems. By exploiting differences in symbol probabilities, entropy coding approaches the fundamental compression limits established by information theory and forms an essential component of many modern compression systems.

Return to Chapter 3 FAQ 3.8.9