🔢 Arithmetic Coding

🔢 Arithmetic Coding

Data Compression

📚 1. Introduction to Arithmetic Coding

Arithmetic Coding is a lossless data compression technique used in information theory and data compression. Unlike fixed-length or variable-length coding techniques such as ASCII, Huffman coding and Shannon-Fano coding, arithmetic coding does not assign a separate binary codeword to every symbol.

Instead, the complete message is represented by a single real number between 0 and 1. The interval containing this number becomes smaller as more symbols of the message are processed.

Core idea: Arithmetic coding represents an entire sequence of symbols by one fractional number lying inside the final interval generated from the probability model.

⌨️ 2. Interactive Arithmetic Encoder

Enter Message

Example Messages

Try: ABACA, ABCAB, BACAB, ABBAC

📊 3. Probability and Cumulative Interval

🔎 4. Step-by-Step Encoding

Enter a message and click Encode Message.

🎯 5. Final Arithmetic Code

The final arithmetic code will appear here.

📖 6. Detailed Theory for B.Sc. Computer Science Honours

6.1 Basic Principle

Suppose a source produces symbols from an alphabet S = {A, B, C}. Each symbol has an associated probability. The probability distribution determines a range within the interval [0,1).

For example, if:

P(A) = 0.5    P(B) = 0.3    P(C) = 0.2

then the cumulative ranges can be:

A → [0.0, 0.5) B → [0.5, 0.8) C → [0.8, 1.0)

Every subsequent symbol causes the current interval to become smaller.

6.2 Initial Interval

The encoder initially considers the entire unit interval:

L = 0
H = 1

where L represents the lower bound and H represents the upper bound.

6.3 Interval Updating Formula

For every symbol, the current interval is divided according to the probability distribution.

Let:

Range = H - L

For a symbol having cumulative lower probability C_low and cumulative upper probability C_high:

New Lower = L + Range × C_low

New Upper = L + Range × C_high

These equations are the central mathematical operations used in arithmetic encoding.

6.4 Encoding Algorithm

1. Determine the frequency of every symbol.
2. Calculate the probability of every symbol.
3. Construct cumulative probability intervals.
4. Initialize the interval to [0,1).
5. Read the message symbol by symbol.
6. Calculate the current interval width.
7. Update the lower and upper bounds.
8. Repeat until all symbols are processed.
9. Select any number inside the final interval as the arithmetic code.

6.5 Worked Mathematical Example

Consider the alphabet:

A = 0.5
B = 0.3
C = 0.2

Therefore:

A → [0.0, 0.5)
B → [0.5, 0.8)
C → [0.8, 1.0)

Suppose the message begins with A. The initial interval [0,1) becomes:

[0 + 1×0.0, 0 + 1×0.5)
= [0,0.5)

If the next symbol is B:

Range = 0.5 - 0 = 0.5

New Lower = 0 + 0.5×0.5 = 0.25
New Upper = 0 + 0.5×0.8 = 0.40

Thus the new interval becomes:

[0.25, 0.40)

The same process continues for every subsequent symbol.

6.6 Arithmetic Coding and Probability

The compression efficiency of arithmetic coding depends strongly on the accuracy of the probability model.

If a symbol occurs frequently, it should receive a larger probability interval. If a symbol is rare, its interval should be smaller.

A good probability model generally produces a narrower final interval, which can be represented efficiently using fewer bits.

6.7 Arithmetic Coding vs Huffman Coding

Feature	Arithmetic Coding	Huffman Coding
Basic representation	One fractional interval/code	Binary codeword for each symbol
Code assignment	Based on cumulative intervals	Based on binary tree
Probability handling	Can represent probabilities very precisely	Generally uses discrete code lengths
Compression efficiency	Can approach the entropy limit closely	Can be less efficient for some probability distributions
Implementation	Requires interval/range arithmetic	Requires a binary tree or equivalent structure

6.8 Entropy and Arithmetic Coding

In information theory, the entropy of a discrete source is:

H(X) = - Σ P(x) log₂ P(x)

Entropy represents the theoretical lower bound on the average number of bits required to represent symbols from a source under the given probability model.

Arithmetic coding can approach this theoretical limit more closely than many traditional symbol-by-symbol coding methods when an appropriate probability model is used.

6.9 Arithmetic Decoding

Decoding is the reverse operation of encoding. The decoder receives the arithmetic code and uses the same probability model to determine which symbol corresponds to the current value.

1. Start with the same probability intervals used by the encoder.
2. Locate the encoded value in the appropriate interval.
3. Identify the corresponding symbol.
4. Reduce the interval using that symbol.
5. Repeat until the complete message is reconstructed.

Important: The encoder and decoder must use the same probability model. If their models differ, correct decoding is generally not possible.

6.10 Advantages

• Excellent compression efficiency.
• Can closely approach the source entropy.
• Works well with probability models containing fractional probabilities.
• Does not require a separate complete binary codeword for every symbol.
• Can be combined with adaptive probability models.
• Useful for statistical data compression.

6.11 Limitations

• More mathematically complex than simple fixed-length coding.
• Requires careful numerical/range management in practical implementations.
• Encoder and decoder must maintain compatible probability models.
• Finite-precision arithmetic requires special implementation techniques.
• Very long messages can cause interval precision problems in naive implementations.

6.12 Applications

• Lossless data compression
• Image compression
• Text compression
• Multimedia compression systems
• Statistical coding
• Entropy coding stages of compression algorithms
• Adaptive data compression systems

6.13 Important Examination Points

• Arithmetic coding is a lossless compression technique.
• The complete message is represented by a number in an interval.
• The initial interval is normally [0,1).
• Symbol probabilities determine interval sizes.
• The interval becomes smaller after processing each symbol.
• The final code is a number lying inside the final interval.
• The decoder requires the same probability model.
• Arithmetic coding is closely related to entropy coding.
• Its theoretical performance can approach the entropy of the source.

🧠 7. Concept Summary

Symbol → Probability → Cumulative Range → Interval Update → Smaller Interval → Final Code

Arithmetic coding therefore converts an entire sequence of symbols into a progressively refined numerical interval. The final fractional value acts as the compressed representation of the message.

CREATED BY BIJAN KRISHNA PAUL B.Sc. Computer Science Honours • Data Compression • Information Theory