4 September 2026
Huffman Coding can be expressed by making a tree of most-common to least-common values.
Wikipedia has a great illustration of the way one can construct a huffman code set. We take a set of data and physically count the occurrences of each point. For our purposes, it is important to remember that there are two layers of compression we are working with here:
-
We are storing the smaller differences between subband energies instead of their larger absolute values.
-
We are compressing the compressed differences from (1) using Huffman Encoding, representing the most common differences in subband energies as smaller data packets than rarer differences in subband energies.
Huffman Encoding Procedure
One question that arises from this Huffman Encoding Table:
What data was used to determine the commonality of subband energy differences?
There must be a source that was used to determine the huffman code that is then applied to all other audio. The existence of a hard-coded huffman table (see GAIN_HUFFMAN_TREE) suggests there was a primary source to create such a table as they are all unique to each application. Is this perhaps what Segment 2 and Regions 13-24 were used for?
In the above documentation about GAIN_HUFFMAN_TREE we can notice that it is an array of arrays. Each subarray houses only two integers. We can think of each indice of the parent array as nodes on a tree:
GAIN_HUFFMAN_TREE = [node_1, node_2, node_3, ..., node_n]
node_n = [value_when_bit_is_0, value_when_bit_is_1]
If node_n's value (whether 0 -- the first item, or 1 -- the second item) is negative, then we've arrived at the difference we must take from our previous subband's value to get the current subband's value.
To make things more intricate, we can notice that each subband has its own huffman tree split in groups of 23 nodes. We can also notice that the first group is blank with [0,0]s. This means that the real first subband huffman code starts at the 23rd index/node of GAIN_HUFFMAN_TREE. There are 14 subbands or groups represented here. See a1800_huffman.md for chart of each group.
This blank first tree poses a question:
Why is the first tree blank?
If there are 14 Huffman Trees for 14 subbands (as indicated at 16kHz), then the first subband is always blank…
Oh! This is because we hard-code the initial value for subband 0 in the first 5 bits of the bitstream! This makes sense now.
| ⟵ Older | Table of Contents | Newer ⟶ |
|---|