Arithmetic Coding — Why Frame 500 Decodes Wrong

from fractions import Fraction

def arithmetic_encode(message: str, probs: dict) -> Fraction:
    """Encode message as a fraction in [0,1)."""
    # Build cumulative probability table
    symbols = sorted(probs)
    cum = {}
    total = Fraction(0)
    for s in symbols:
        cum[s] = total
        total += Fraction(probs[s]).limit_denominator(1000)
    low, high = Fraction(0), Fraction(1)
    for symbol in message:
        range_size = high - low
        high = low + range_size * (cum[symbol] + Fraction(probs[symbol]).limit_denominator(1000))
        low  = low + range_size * cum[symbol]
    return (low + high) / 2  # midpoint of final interval

def arithmetic_decode(code: Fraction, probs: dict, length: int) -> str:
    symbols = sorted(probs)
    cum = {}
    total = Fraction(0)
    for s in symbols:
        cum[s] = total
        total += Fraction(probs[s]).limit_denominator(1000)
    message = ''
    for _ in range(length):
        for s in reversed(symbols):
            if code >= cum[s]:
                message += s
                p = Fraction(probs[s]).limit_denominator(1000)
                code = (code - cum[s]) / p
                break
    return message

probs = {'a': 0.5, 'b': 0.25, 'c': 0.25}
msg = 'aab'
code = arithmetic_encode(msg, probs)
print(f'Encoded {msg!r} → {float(code):.6f}')
print(f'Decoded → {arithmetic_decode(code, probs, len(msg))!r}')

import math
import heapq
from fractions import Fraction

# Huffman simulation (code length calculation)
def huffman_expected_length(probs):
    heap = [(p, []) for p in probs if p > 0]
    heapq.heapify(heap)
    while len(heap) > 1:
        p1, c1 = heapq.heappop(heap)
        p2, c2 = heapq.heappop(heap)
        for code in c1:
            code.append('0')
        for code in c2:
            code.append('1')
        heapq.heappush(heap, (p1 + p2, c1 + c2))
    codes = heap[0][1]
    code_lengths = [len(code) for code in codes]
    return sum(p * l for p, l in zip(probs, code_lengths))

# Entropy calculation
def entropy(probs):
    return -sum(p * math.log2(p) for p in probs if p > 0)

probabilities = [0.99, 0.01]
huff_len = huffman_expected_length(probabilities)
ent = entropy(probabilities)
print(f"Huffman expected length: {huff_len:.3f} bits/symbol")
print(f"Entropy: {ent:.3f} bits/symbol")
print(f"Redundancy: {huff_len - ent:.3f} bits/symbol")
print(f"For 1000 symbols: Huffman {1000 * huff_len} bits, optimal {1000*ent:.0f} bits")
print(f"Arithmetic coding (theoretically) can get within 0.001 bits/symbol of entropy")

# Multiple symbols scenario
probs_multi = [0.4, 0.3, 0.2, 0.1]
huff_multi = huffman_expected_length(probs_multi)
ent_multi = entropy(probs_multi)
print(f"\n4 symbols (0.4,0.3,0.2,0.1): Huffman {huff_multi:.2f}, Entropy {ent_multi:.2f}")
print(f"Waste: {huff_multi - ent_multi:.2f} bits/symbol, {1000 * (huff_multi - ent_multi):.0f} bits per KB")

// Simplified CABAC-style renormalization in integer arithmetic
// From H.264 standard: range is in [2^8, 2^9) after renormalization

#include <stdint.h>

// Encoder state (as in CABAC)
typedef struct {
    uint32_t low;      // current interval low point (scaled integer)
    uint32_t range;    // current interval range (>= 256 << 16)
    uint8_t  pending;  // number of pending bits (for carry)
} CabacEncoder;

// Renormalisation: called when range < 256 << 16
void cabac_renorm(CabacEncoder *enc, void (*output)(uint8_t byte)) {
    while (enc->range < (256 << 16)) {
        if (enc->low < (1 << 24)) {  // No carry to propagate
            output(enc->low >> 24);   // Output highest byte
            for (int i = 0; i < enc->pending; i++) output(0xFF); // Emit pending 0xFFs
            enc->pending = 0;
        } else if (enc->low >= (3 << 24)) { // 3<<24 = 50331648
            output(((enc->low >> 24) + 1) & 0xFF); // Propagate carry
            for (int i = 0; i < enc->pending; i++) output(0x00); // Emit 0x00 for pending
            enc->pending = 0;
        } else {  // Pending carry case: low in [1<<24, 3<<24)
            enc->pending++;
            enc->low -= (1 << 24);
        }
        enc->low <<= 8;
        enc->range <<= 8;
    }
}

// Probability update (LPS = less probable symbol, MPS = more probable symbol)
typedef struct {
    uint16_t probLPS;  // Probability of LPS (0..32767, scaled to 2^15)
    uint8_t  mps;      // More probable symbol value (0 or 1)
} CabacContext;

// Update probability after encoding a symbol
void cabac_update(CabacContext *ctx, uint8_t encoded_symbol) {
    if (encoded_symbol == ctx->mps) {
        // Increase MPS probability: probLPS *= (1 - alpha) where alpha ~ 0.05
        ctx->probLPS -= ((ctx->probLPS) >> 5);  // multiply by 31/32
    } else {
        // LPS occurred: increase probLPS, swap MPS if necessary
        ctx->probLPS += ((32768 - ctx->probLPS) >> 5);  // increase toward 0.5
        if (ctx->probLPS > 16384) {  // > 0.5
            ctx->mps ^= 1;  // swap MPS/LPS
            ctx->probLPS = 32768 - ctx->probLPS;
        }
    }
}