Arithmetic Coding

Arithmetic coding is an advanced data compression technique that encodes messages with exceptional efficiency. Unlike simpler encoding methods that assign fixed codes to individual symbols, arithmetic coding represents an entire message as a single number within a specific range. The example using “INDIA” provides an excellent step-by-step illustration of how this technique works.

What is Arithmetic Coding?

Arithmetic coding is a form of entropy encoding that represents data by a fractional number between 0 and 1. The technique works by progressively narrowing down the range in which the f inal coded number will fall, based on the probabilities of each symbol in the message. For the “INDIA” example, we first establish the probability and cumulative frequency distribution:

These cumulative frequencies define the proportional sub-intervals for each symbol.

Core Formulas with Cumulative Frequencies

For encoding each symbol:

1. Range Calculation: range = high — low
2. New High: high_new = low + range × cumulative_frequency_end(symbol)
3. New Low: low_new = low + range × cumulative_frequency_start(symbol) Where:

• cumulative_frequency_start(symbol) is the starting point of the symbol’s range
• cumulative_frequency_end(symbol) is the ending point of the symbol’s range

Step-by-Step Implementation with Cumulative Frequencies

Initial State:

• low = 0.0
• high = 1.0
• range = 1.0

Step 1: Encoding “I”

Cumulative frequency for “I” is [0.0, 0.4)

• range = high — low = 1.0–0.0 = 1.0
• new_high = low + range × cumulative_frequency_end(“I”) = 0.0 + 1.0 × 0.4 = 0.4
• new_low = low + range × cumulative_frequency_start(“I”) = 0.0 + 1.0 × 0.0 = 0.0

Sub-interval calculation:

• step_value = (high — low) / number_of_symbols = (1.0–0.0) / 5 = 0.2
• Symbol “I” interval: [0.0, 0.4)
• Symbol “N” interval: [0.4, 0.6)
• Symbol “D” interval: [0.6, 0.8)
• Symbol “A” interval: [0.8, 1.0)

Updated state:

• low = 0.0
• high = 0.4
• range = 0.4

Step 2: Encoding “N”

Cumulative frequency for “N” is [0.4, 0.6)

• range = high — low = 0.4–0.0 = 0.4
• new_high = low + range × cumulative_frequency_end(“N”) = 0.0 + 0.4 × 0.6 = 0.24
• new_low = low + range × cumulative_frequency_start(“N”) = 0.0 + 0.4 × 0.4 = 0.16

Sub-interval calculation:

• step_value = (high — low) / number_of_symbols = (0.4–0.0) / 5 = 0.08
• Symbol “I” interval: [0.0, 0.16)
• Symbol “N” interval: [0.16, 0.24)
• Symbol “D” interval: [0.24, 0.32)
• Symbol “A” interval: [0.32, 0.4)

Updated state:

• low = 0.16
• high = 0.24
• range = 0.08

Step 3: Encoding “D”

Cumulative frequency for “D” is [0.6, 0.8)

• range = high — low = 0.24–0.16 = 0.08
• new_high = low + range × cumulative_frequency_end(“D”) = 0.16 + 0.08 × 0.8 = 0.224
• new_low = low + range × cumulative_frequency_start(“D”) = 0.16 + 0.08 × 0.6 = 0.208

Sub-interval calculation:

• step_value = (high — low) / number_of_symbols = (0.24–0.16) / 5 = 0.016
• Symbol “I” interval: [0.16, 0.192)
• Symbol “N” interval: [0.192, 0.208)
• Symbol “D” interval: [0.208, 0.224)
• Symbol “A” interval: [0.224, 0.24)

Updated state:

• low = 0.208
• high = 0.224
• range = 0.016

Step 4: Encoding “I”

Cumulative frequency for “I” is [0.0, 0.4)

• range = high — low = 0.224–0.208 = 0.016
• new_high = low + range × cumulative_frequency_end(“I”) = 0.208 + 0.016 × 0.4 = 0.2144
• new_low = low + range × cumulative_frequency_start(“I”) = 0.208 + 0.016 × 0.0 = 0.208

Sub-interval calculation:

• step_value = (high — low) / number_of_symbols = (0.224–0.208) / 5 = 0.0032
• Symbol “I” interval: [0.208, 0.2144)
• Symbol “N” interval: [0.2144, 0.2176)
• Symbol “D” interval: [0.2176, 0.2208)
• Symbol “A” interval: [0.2208, 0.224)

Updated state:

• low = 0.208
• high = 0.2144
• range = 0.0064

Step 5: Encoding “A”

Get Nit’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Cumulative frequency for “A” is [0.8, 1.0)

• range = high — low = 0.2144–0.208 = 0.0064
• new_high = low + range × cumulative_frequency_end(“A”) = 0.208 + 0.0064 × 1.0 = 0.2144
• new_low = low + range × cumulative_frequency_start(“A”) = 0.208 + 0.0064 × 0.8 = 0.21312

Sub-interval calculation:

• step_value = (high — low) / number_of_symbols = (0.2144–0.208) / 5 = 0.00128
• Symbol “I” interval: [0.208, 0.21056)
• Symbol “N” interval: [0.21056, 0.21184)
• Symbol “D” interval: [0.21184, 0.21312)
• Symbol “A” interval: [0.21312, 0.2144)

Final state:

• low = 0.21312
• high = 0.2144
• range = 0.00128

Final Codeword Calculation

The final range [0.21312, 0.2144) contains all numbers that uniquely decode to “INDIA”. Any number in this range will work, but typically we choose the simplest representation for efficiency.

The value 0.21313 is selected because:

1. It falls within our valid range [0.21312, 0.2144)
2. It has a relatively simple binary representation
3. It satisfies: 0.21312 < 0.21313 < 0.2144

Recalculation of Cumulative Frequencies at Each Step

One key aspect of arithmetic coding is how the cumulative frequencies are recalculated for each step within the newly restricted range:

1. For each new range [low, high), the symbols are allocated proportionally according to their original probabilities.
2. The formula to locate a symbol’s sub-interval within the current range is:

• sub_interval_start = low + range × cumulative_frequency_start(symbol)
• sub_interval_end = low + range × cumulative_frequency_end(symbol)

3. At each step, the entire probability space [0,1) is effectively rescaled to fit within the current range [low, high).

Evaluation Parameters:

1. BPP (Bits Per Pixel/Symbol) Calculation:

BPP is a measure of how many bits are used on average to represent each symbol in the compressed message:

BPP Formula:

BPP = Size of Compressed Message in Bits / Total Number of Characters

For the “INDIA” example: •

• Total characters = 5
• To represent 0.21313 precisely requires about 32 bits (using single precision float)
• BPP = 32 bits / 5 characters = 6.4 bits per character

2. Compression Ratio Calculation

The compression ratio measures how much the data has been reduced in size:

Compression Ratio Formula:

Compression Ratio = ((Original Size — Compressed Size) / Original Size) × 100%

For the “INDIA” example:

• Original size = 5 bytes × 8 bits = 40 bits (assuming 8-bit ASCII)
• Compressed size = 32 bits (for the number 0.21313)
• Compression Ratio = ((40–32) / 40) × 100% = 20%

Decoding Process with Cumulative Frequencies

To decode the arithmetic code 0.21313:

1. Start with the full symbol range [0,1)
2. Locate which symbol’s interval contains 0.21313:

• 0.21313 falls in [0.0, 0.4), so output “I”

3. For next symbol, rescale the code value:

• code_value = (code_value — low) / range = (0.21313–0.0) / 0.4 = 0.532825
• 0.532825 falls in [0.4, 0.6), so output “N”

4. Continue rescaling and mapping to intervals:

• After “N”: code_value = (0.532825–0.4) / 0.2 = 0.664125
• 0.664125 falls in [0.6, 0.8), so output “D”
• After “D”: code_value = (0.664125–0.6) / 0.2 = 0.320625
• 0.320625 falls in [0.0, 0.4), so output “I”
• After “I”: code_value = (0.320625–0.0) / 0.4 = 0.8015625
• 0.8015625 falls in [0.8, 1.0), so output “A”

This process recovers the original message “INDIA”.

Advantages of Arithmetic Coding

1. Efficiency: Arithmetic coding can achieve compression rates very close to the theoretical entropy limit.
2. Flexibility: It works well with adaptive models where probabilities change during encoding.
3. Symbol Integration: The entire message is encoded as one number, eliminating the need for symbol-by-symbol encoding.

Practical Applications

Arithmetic coding is used in:

• Advanced image compression formats (JPEG2000)
• Video compression standards
• Audio compression
• Text compression algorithms

Limitations

1. Computational Complexity: More computationally intensive than simpler methods like Huffman coding.
2. Precision Requirements: Requires high-precision arithmetic to avoid rounding errors.
3. Sequential Nature: Inherently sequential, making parallelization challenging.

This detailed implementation demonstrates how arithmetic coding uses cumulative frequencies to progressively narrow the encoding range, achieving compression efficiency that approaches the theoretical entropy limit.