🔢 mathematics

Asymmetric Encoding-Decoding Schemes for Lossless Data Compression

This paper proposes the Asymmetric Encoding-Decoding Scheme (AEDS), a generalized lossless compression method that encodes data backward and decodes it forward, demonstrating that it can outperform Huffman coding for specific probability distributions and converges to source entropy at a rate of $O(1/N)$ as the number of states increases.

Original authors: Hirosuke Yamamoto, Ken-ichi Iwata

Published 2026-01-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hirosuke Yamamoto, Ken-ichi Iwata

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to pack a suitcase full of clothes for a trip. The goal of lossless data compression is to fit as much as possible into the smallest space without losing a single item.

For decades, the two most famous "packing methods" were Huffman coding and Arithmetic coding.

Huffman coding is like a smart organizer who assigns short tags to common items and long tags to rare ones. It's fast and reliable.
Arithmetic coding is like a master mathematician who squeezes items into a tiny, continuous space. It's incredibly efficient but requires heavy mental math to do the squeezing.

Recently, a method called tANS (tabled Asymmetric Numeral Systems) came along. It's a hybrid: it uses the heavy math of Arithmetic coding but stores the answers in a lookup table (like a cheat sheet) so it doesn't have to do the math every time. It's fast and very efficient.

The Problem: Even tANS has a limit. It's built on a specific set of rules, like a suitcase with a fixed number of compartments. Sometimes, the "clothes" (data) you are packing don't fit perfectly into those pre-made compartments, leaving a little bit of wasted space.

The Solution: AEDS (Asymmetric Encoding-Decoding Scheme)
This paper introduces a new, more flexible packing method called AEDS. Think of AEDS as a "super-suitcase" that generalizes tANS. It keeps the best features of the old methods but removes the rigid rules, allowing for a much broader variety of packing strategies.

Here is how it works, using simple analogies:

1. The "Backwards Packing, Forwards Unpacking" Trick

Most packing methods work in order: you pack item 1, then item 2, then item 3.

AEDS (and tANS) do something weird: They pack the suitcase backwards (Item 3, then 2, then 1) but unpack it forwards (Item 1, then 2, then 3).
Why? Imagine you are building a tower of blocks. If you build it from the top down, you can use a single, simple number to keep track of the whole tower's height. If you build from the bottom up, you need complex calculations to know how much space is left. By packing backwards, AEDS can use a single "counter" to manage the whole sequence, making it incredibly efficient.

2. The "State Machine" (The Switchboard)

In the old methods, the "rules" for packing are fixed. In AEDS, the rules change based on a state.

Imagine a switchboard with many different lights (states).
When you pack an item, you look at which light is currently on. That light tells you exactly how to tag the item and which light to switch to next.
Because AEDS allows for any pattern of lights and switches (not just the specific ones tANS allows), it can find a "perfect fit" for data that tANS would struggle with.

3. When Does AEDS Win?

The paper proves that AEDS is a "super-charger" for compression in specific scenarios:

The "Dominant Item" Scenario: Imagine your suitcase is mostly filled with one type of item (e.g., 62% of your clothes are t-shirts).
- Standard Huffman coding is good, but it leaves a little gap.
- AEDS can rearrange the packing rules to squeeze that dominant item in even tighter. The paper shows that if one item makes up more than 61.8% of your data, a simple 2-state AEDS beats Huffman. If you use 5 states, it beats Huffman even if that item is only 57% of the data.
The "Uniform" Scenario: Imagine you have an equal number of every type of item (like a deck of cards).
- Standard methods have a tiny bit of "wasted space" (redundancy) because they can't divide the space perfectly.
- AEDS can construct a custom "switchboard" specifically for this uniform mix, reducing that wasted space significantly, sometimes almost eliminating it.

4. The "Speed vs. Smarts" Balance

The paper highlights a crucial trade-off:

Huffman is fast but not the smallest.
Arithmetic is the smallest but slow (too much math).
AEDS aims for the "Goldilocks" zone: It is as fast as Huffman (because it uses simple look-up tables and no heavy math) but can be as small as the best theoretical limits.

The Bottom Line

The authors of this paper have built a new "packing algorithm" (AEDS) that is a more flexible version of the popular tANS.

It's backward-compatible: It can do everything tANS does.
It's smarter: It can find better packing arrangements for data where one item is very common or when items are evenly distributed.
It's scalable: As you give the system more "states" (more switches on the switchboard), it gets closer and closer to the theoretical perfect size, eventually reaching the absolute limit of how small data can be compressed.

In short, AEDS is a new way to organize data that uses a clever "backwards" trick and flexible rules to squeeze information into a smaller space than ever before, without slowing down the computer.

Technical Summary: Asymmetric Encoding-Decoding Schemes for Lossless Data Compression

Problem Statement

The paper addresses the limitations of conventional lossless data compression codes, specifically the Huffman code and the arithmetic code. While Huffman codes are simple but often suboptimal in compression rate, and arithmetic codes achieve near-entropy performance, they require complex arithmetic operations. The Asymmetric Numeral Systems (ANS), particularly the tabled variant (tANS), offer a high-speed alternative using a single integer variable and lookup tables, encoding data in backward order and decoding in forward order. However, the theoretical class of codes represented by tANS is relatively narrow. The paper seeks to generalize the tANS framework to create a broader class of codes that can potentially achieve shorter average code lengths than Huffman codes under specific conditions, while maintaining the computational efficiency of table-based methods.

Methodology

The authors propose a new coding framework called the Asymmetric Encoding-Decoding Scheme (AEDS). This scheme generalizes the tANS by relaxing the constraints on state transitions and codeword assignments.

Generalization of tANS:
- AEDS Structure: The AEDS utilizes a finite set of internal states $X$ $X$ . Unlike tANS, which relies on specific arithmetic mappings derived from interval division, AEDS defines encoding and decoding via arbitrary functions:
  - Encoding: Maps a source symbol $s$ and a state $\hat{x}$ to a codeword $\beta$ and a new state $x$ (backward transition).
  - Decoding: Maps a codeword $\beta$ and a state $x$ to a source symbol $s$ and a new state $\hat{x}$ (forward transition).
- Asymmetry: The scheme encodes sequences in backward order ( $s_n \to s_1$ ) and decodes in forward order ( $s_1 \to s_n$ ), similar to ANS, but without requiring arithmetic operations.
- Flexibility: The encoding codeword set does not need to be prefix-free, and the decoding source symbol set does not need to cover all source symbols for every state, allowing for more flexible code tree constructions.
Construction via Code Trees:
The paper demonstrates how to construct AEDSs based on arbitrary prefix-free code trees (e.g., Huffman trees). Two specific types are introduced:
- Type-I AEDS: Constructed with $N$ states based on a code tree $T$ . It utilizes a "phased-in code" (Huffman code for uniform distributions) for specific state transitions to optimize the average code length.
- Type-II AEDS: A 5-state construction designed to improve performance when the probability weight of the root's child in the code tree is lower than the threshold required for Type-I.
State-Divided AEDS (sAEDS):
To facilitate theoretical analysis and establish bounds, the authors define a restricted subclass called sAEDS. In an sAEDS, the state space $X$ is partitioned into disjoint sets $X_s$ corresponding to each source symbol $s$ . This structure ensures that the decoding function $D_x$ for any state $x \in X_s$ always outputs $s$ , simplifying the analysis of stationary probabilities and average code lengths.

Key Contributions and Results

1. Superiority over Huffman Coding

The paper derives conditions under which AEDSs achieve a shorter average code length than the standard Huffman code for i.i.d. sources:

Type-I AEDS (2 states): If a child of the root in the Huffman code tree has a probability weight $P_R > \omega^{(I)} \approx 0.61803$ , the Type-I AEDS with 2 states yields a shorter average code length than the Huffman code.
Type-II AEDS (5 states): If $P_R > \omega^{(II)} \approx 0.56984$ , the Type-II AEDS with 5 states outperforms the Huffman code.
Uniform Sources: For sources with uniform distributions, the paper shows that constructing an AEDS based on a non-Huffman code tree (specifically one that maximizes the probability weight of a subtree) can further reduce the average code length compared to an AEDS based on the Huffman tree.

2. Theoretical Bounds and Convergence

The authors derive upper bounds on the average code length for the sAEDS, which also apply to tANS:

Upper Bounds: The average code length $L$ is bounded by $L \le H(p) + D(p \| q) + \sigma$ , where $H(p)$ is the source entropy, $D(p \| q)$ is the relative entropy between the source distribution and the state distribution, and $\sigma \approx 0.08607$ .
Convergence Rate: For an optimal AEDS (and tANS) with $N$ states, the average code length converges to the source entropy $H(p)$ with a speed of $O(1/N)$ as $N$ increases. This establishes that increasing the number of states systematically reduces redundancy.

3. Worst-Case Redundancy Analysis

The paper analyzes the worst-case redundancy for binary sources and uniform sources. It demonstrates that Type-I and Type-II AEDSs can achieve significantly lower worst-case redundancy compared to the Huffman code, particularly when the source distribution is skewed (e.g., one symbol has a high probability).

Significance and Claims

The paper claims that the AEDS represents a generalization of tANS with a much broader code class. Its primary significance lies in:

Performance Improvement: Proving that simple, state-based schemes (requiring only 2 or 5 states) can theoretically outperform the Huffman code, a long-standing benchmark, under specific probability conditions.
Theoretical Unification: Providing a unified framework (sAEDS) that encompasses tANS and allows for rigorous information-theoretic analysis, including the derivation of convergence rates ( $O(1/N)$ ) to entropy.
Practical Feasibility: Emphasizing that like tANS, AEDSs can be implemented using lookup tables without complex arithmetic operations, making them suitable for high-speed practical systems while offering potential compression gains over Huffman coding.

The authors note that while the construction is theoretically sound and offers compression gains, the complexity of storage (space complexity) may increase with the number of states, though they suggest that for specific constructions (like Type-I and Type-II based on Huffman trees), the complexity can be managed to be comparable to Huffman coding.