Author: Ratko V Tomic
Date: 05:37:46 01/04/06
Go up one level in this thread
>One question to the implementation of the binary 32-bit Encoder/Decoder - i >think beside the path-index as "main" compressed data also the number of one >bits (if variable) is required. I don't see how "k" is passed from Encoder to >Decoder!? How the count k (or generally, the frequency table) is passed to decoder depends on the larger context of coding task. The simplest way is to send it in the fixed number of bits of ceil(log(n+1)) bits (or tapered huffman code if n+1 is not power of 2). That is also the optimal way for non-probabilistic sources, where the counts can vary arbitrarily from task to task. For the sources where symbol probabilities are fixed (and perhaps unknown), one can code counts using Huffman codes computed for the binomial distribution, P(n,k)= p^k * (1-p)^(n-k) * C(n,k). That method was used for the benchmarks in the table on p.10 in the preprint. For fully optimal encoding, instead of Huffman (which is not very good for counts on very sparse data) one would use multi-alphabet version of QI coder itself to encode counts. This is the hierarchical enumerative coding, which already exists in the conventional EC. See more on this topic in: 23. L. Öktem "Hierarchical Enumerative Coding and Its Applications in Image Compressing", Ph.D. thesis, TUT Finland, 1999 http://www.1stworks.com/ref/oktemThesis.pdf There are also several EC coding methods which encode k within the index, as a part of enumeration (see [11] & [13] on the RefLib page: http://www.1stworks.com/ref/RefLib.htm ). They are elegant formally, although in practice they run quite bit slower, since the don't have as good division of labor as the separate coding methods do. They also don't gain anything on compression ([11] even loses some compression efficiency). > Is there a reason why you initialize K with one in the C-code > of the Encoder - in opposition to the pseudo code? That is to help compiler to better optimize the statements inside the loop, where it gets binomial coefficient I+=bc32(n,k++). Alternative would have been to set k=0 at the top and then use I+=bc32(n,++k), which is potentially slightly slower since compiler is now constrained to increment k somewhere before it pushes it as the arg to bc32() function. So, I think the k++ version allows slighly greater parallelism by having weaker constraints on which instructions have to happen before the next ones in the stream can be performed.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.