Questions on the Huffman Tree in Fig.2

[Andy0422]

I am just wondering why there exit no right leaf in this figure? where is the code:1, code:11. etc ? Cheers!

[tonyzhang617]

Thank you for the question!

The right-side leaf nodes are omitted from the figure due to space constraints. In practice, the Huffman tree used in DFloat11 has a maximum depth of 32, and every traversal ends at a valid leaf node, each representing a decoded exponent.

Hope this clarifies things! Let me know if you have any other questions.

[Andy0422]

Very clear. Thanks!

[Andy0422]

BTW，do you have plan to release the encode and decode cuda kernel?

One more question, could you explain how the gap array works? Does it obtain from the encoding part? I am a little bit confused how to build it.

[devloper13]

From what I understand, before calculating the gap array, we must calculate prefix sum of the Huffman encoded string. For example consider a Huffman encoded string 00110 where 0 01 10 are the encoding corresponding to some elements. The prefix sum would be prefix_sum=[0, 1, 3, 5]. We will see later why we need prefix sum.

Now, to decode consider the threads randomly initialised at any point, except the first thread. If we consider our string from above i.e 00110, say thread 1 is at 0th index (pointing at 0), thread 2 is at 2nd index (pointing at 1). Thread 1 is trivial, it will start decoding correctly. Thread 2 on the other hand starts at an undesirable position. Gap array tells us how much we want to move ahead from the initially acquired position to start decoding correctly.

This is where we will utilise the prefix sum array. Each element in prefix sum tells us the length of complete Huffman encoding. For example the prefix_sum[2] which is 3, was calculated using 0 and 01. In an ideal case all thread would initialise at prefix_sum[i] to decode correctly. Taking example of thread 2, it is initialised at index 2 in the example 00110.

We will use the following condition:

Prefix_sum[k] < thread_2_index <= Prefix_sum[k+1]
i.e 1 < 2 <= 3

And so Prefix_sum[k+1] - thread_2_index = 3-2 = 1 will the value in the Gap array. Prefix_sum[k+1] is the length of the a complete Huffman coding. subtracting thread_2_index from it tells us how many indexes to move to start from a correct decoding position.