Re: question about QI coder
- From: "nightlight" <nightlight@xxxxxxxxxxxxxx>
- Date: 20 Feb 2006 01:52:34 -0800
let's imagine we have to compress 1024 bits ; 506 bits are zeroes
and 518 bits are ones. for several decades it is well known we
can compress this by the number of zeroes and a combination ( Cn,p ) .
what's the difference between this old algorithm and the new QI coder ?
You can use QI source & QI.exe (at [QIC]) to see what you would get.
Using command line:
QI.exe n1k k518 ci10
runs QI on this input with k=518 ones and n=1024 bits (for 10
iterations). The QI index (produced by qiEnc()) has length of 1018.5726
bits. That is 1.18e-7 bits above the log(C(n,k)) of the exact
combination C(n,k), which is a mathematical lower bound on average
index size (a smaller avg. index would not be uniquely decodable).
Note that the length of the QI index is defined (upper bound) by the
length of the quantized binomial Q(n,k), which in this case is:
Q(1024,518) = 0xBE5B299D * 2^987
Index Size = log(0xBE5B299D) + 987 = 1018.5726 bits
hence its mantissa is M=0xBE5B299D and the shift s is s=987). The top
32 bits of the index, which are always smaller than M, can be coded to
exact log(M) bits using mixed radix code (if there are other items to
ship). If only the index is shipped (hence one has to round the output
to the whole number of bits) one can use tapered Huffman code to encode
the upper 32 bits of index in 31 or 32 bits, which will result in the
average excess of 0.0826 bits above the mixed radix output (the avg.
excess of tapered Huffman is always smaller than 0.08607... =
1+log(log(e))-log(e) bits). The mixed radix coding of bit fractions is
explained in an earlier post [M1].
how many bits does the QI coder "win" compared to the old algorithm ?
QI produces 1.18e-7 bits _more_ than the size of exact index
log(C(n,k)). But for any 1024 bit string S1024 with 506 zeros, QI index
I(S1024) is computed using only 506 adds of 32 bit numbers into the
output index (see eqs. (7) p. 13, (21) p. 27 in [T1]):
I(S1024) = Q(N1,1) + Q(N2,2) + ... + Q(N506,506)
where N1, N2,..., N506 are offsets (zero based) of less frequent bits
(here zeros) in the S1024 and the numbers Q(n,k) are quantized
binomials obtained from the table (see [QIC], function qiEnc() in
EncDec.c ).
In contrast, the exact enumeration would have to compute exact
binomials C(Nj,j) for j=1..506 (see eq. (7) p. 13 in [T1]) , which
would be integers ranging from 32 bits to 1024 bits (1019 bits if
you're adding in bits). Hence the advantage of QI vs the exact
enumeration is not in output size but in speed and binomial table size.
That was the precise point of the QI advance (see also A1-A4 in [M2]):
for the price of mere 1.18e-7 bits in excess output, QI reduces the
arithmetic complexity and table sizes of exact enumeration by a factor
n/g (where g=32 bits is the QI mantissa width and n is the number of
input bits). The QI coding excess over the exact enumeration is always
below DQ=2*log(e)/2^g bits per symbol (see [T4 and p.8, [T3]). This
value DQ is mathematically the lowest excess any coder using g bit
addends (codewords) can obtain and still produce decodable output (see
Kraft inequality constraint, eq. (20), p. 8 [T3]). The maximum
quantization excess for arithmetic coder is 4 times larger than DQ (see
[M1]) for binary alphabet (and A*2 for general alphabet size A).
I should add here that in addition to the four fundamental advantages
A1-A4 over arithmetic coding described in [M2], there is one more
principal QI advantage relevant for the multiprocessor environments:
A5) -- PARALLELIZATION OF CODING --
With QI the index computation for each block (which normally takes the
bulk of coding time) can be done by a separate processor for each
block. This is another consequence of the QI's better division of labor
between coder and modeler and within coder itself: with QI the
cumulative statistics of the entire input affects only the encoding of
the 'counts of ones' which is a separate and independent component of
coding process from the index computation. The coding of index for each
block only uses the count of ones in that block, while the encoding of
counts of ones (produced by individual block coding) K1, K2,.. Km for m
blocks occurs in a separate stage after the index computations. The
cumulative statistics of the m blocks affects only this last component,
coding of K1,K2,..Km, while the rest can go in parallel if multiple
processors are available.
In contrast, with arithmetic coding (AC) the index computation is
inextricably intertwined with the statistics of the entire processed
input, since its coding probabilities which are needed to encode the
current bit, depend on statistics of _all_ previous bits. To achieve
the parallelism in index computation, AC would need a separate pass
over entire data to collect the statistics for each block in advance,
so that it could hand the subsequent index computations for different
blocks to different processors. Hence, the AC computation logistics is
wrong footed regarding the parallelism: the information AC needs to
encode index for each block depends on content of previous blocks. With
QI the index computations occur first -- they are independent from
block to block and the statistics they collect is handed to the coder
for K1,K2,..Km numbers, which doesn't need to revisit the input data
again.
Hence QI needs only one pass over the entire data to achieve the coding
parallelism, while arithmetic and Huffman coders, both having wrong
footed coding logistics for the parallelism, need two passes. The QI
logistics is thus natural for the parallel computations.
--- References ( http://www.1stworks.com/ref/RefLib.htm )
QIC. QI C source code research kit:
http://www.1stworks.com/ref/qi.htm
M1. -- Mixed radix coding of bit fractions:
http://groups.google.com/group/comp.compression/msg/1e015f38d228969e
T1. R.V. Tomic "Fast, optimal entropy coder" 1stWorks
TR04-0815, 52p, Aug 2004
http://www.1stworks.com/ref/TR/tr04-0815b.pdf
M2. -- Summary of QI algorithmic advances (A1)-(A4)
http://groups.google.com/group/comp.compression/msg/27c6f329038a1bdc
T3. R.V. Tomic "Quantized Indexing: Beyond Arithmetic Coding"
arXiv cs.IT/0511057, 10p, Nov 2005
http://arxiv.org/abs/cs.IT/0511057
T4. One page summary and guide to [T3]
http://www.1stworks.com/ref/TR/DCC2006.pdf
.
- Follow-Ups:
- Re: question about QI coder
- From: David A. Scott
- Re: question about QI coder
- From: cp
- Re: question about QI coder
- References:
- question about QI coder
- From: cp
- question about QI coder
- Prev by Date: Re: Computational Estimation for EBCOT
- Next by Date: Re: freeware Arithmetic Compressor
- Previous by thread: question about QI coder
- Next by thread: Re: question about QI coder
- Index(es):
Relevant Pages
|
|
