Encoding trees enable flexible variable-length prefix coding for arbitrary symbol sets
Encoding Trees: A Method for Producing a Variable-Length Prefix Code From Sets of Arbitrary Size
Information Theory
Summary
When sending messages, it helps to convert symbols into bits that don’t get mixed up, even if the symbols come from many different groups. The authors describe a new way to build special trees, called encoding trees, that can turn these symbols into unique sequences of bits. These trees can be trimmed and labeled in clever ways to make sure the code works both for turning symbols into bits and bits back into symbols. They prove that their method always produces codes that are easy to decode and can handle any length or combination of symbols from those groups.
What this means in practice
- •For data compression engineers: Design prefix codes for data streams with symbols drawn from complex, arbitrary sets using encoding trees.
- •For digital communication designers: Develop coding schemes that reliably encode and decode variable-length binary strings from arbitrary input symbol sets of varying sizes.
A theory result. No direct application yet.
Authors
Bryony H. Laporte, Karen Rudie
Abstract
In this work we formalize a new class of binary trees called encoding trees. We extend this structure in two ways, through labelling to create the class of labelled encoding trees, and pruning to create the class of pruned encoding trees. We discuss how these two extensions can be combined to create the the class of pruned labelled encoding trees. Using the supplementary results that we prove about these classes of trees, we construct a code that uses pruned labelled encoding trees to convert a string of symbols from a sequence of non-empty sets to a binary string. We prove that this code is a variable-length prefix code that can process any valid string of symbols from the given sequence of non-empty sets. Furthermore, we construct a code from the class of pruned labelled encoding trees that goes in the opposite direction, from binary strings to a string of symbols from a sequence of non-empty sets of arbitrary symbols. We prove that this code is also a variable-length prefix code that can process any binary string of any length, provided that the sequence of non-empty sets is sufficiently long. We provide an equation that establishes the minimum sequence length to encode any binary string of a given length, based on that length.