Z) { bit := MPS; A := Z; } deal with MPS G-3 else { bit := kPS; A := A + 1 - Z; C := C + 1 - Z; } deal with kPS G-4 while (A _> 1/2 ) { A := 2(n- 1/2); C := 2(C- 1/2); } renormalize Why Golomb coding is easy. When considered in these terms, Golomb coding is easy for three reasons. First, all the MPS-objects are forced to be the same size, the slot size, and that size is a divisor of the bin size, so no MPS-object ever straddles a bin boundary. Hence cm(k) and cm(kq- 1) are always in the same segment of the piecewise linear function defined by Equation (1). During the coding of a single symbol, the low point A never moves along two different slopes of the bin-count-to-codeword curve of Figure 1, so no special non-linear processing is needed to handle this case. Second, because i - Z is always a multiple of a power of 2, we do not have to deal with arithmetic carries when doing the upward shift of A and C by i - Z; fixed-point > S size Z-la if (Z > 1/2 ) { Z := Z/2 + 1/4;} adjust for bin overlap z-2 if (C > Z) { bit := MrS; A := Z; } deal with MrS z-3 else{bit:=krS;A:=A+l-Z;C':=C'+l-Z;} deal withkrS z-4 while (A _> 1/2 ) { A := 2(A- 1/2); C' := 2(C'- 1/2); } renormalize This method of dealing with bin overlap is essentially the same as the "over-half processing" presented by Ono et al. [4] in the Arithmetic Melcode. It is a much more accurate and more principled approximation of proportional interval division than It is possible to use a different Golomb parameter after each renormalization, that is, after each code bit, but this is not frequent enough for maximum compression efficiency. It is also possible to interleave Golomb codes with different parameters in the same code stream, as in Block Melcode [4], but this increases encoding latency and coder complexity. > 1/2 ) { z := z/2 + 1/4; } ir (c > z) { bit := MI S; A := Z; } else { bit := L?S; A := A+ 1 - Z; C := C+ 1 - Z; while (A _ 1/2 ) { A := 2(A- 1/2); C := 2(C- 1/2); F :---- rain(C, 1/2); } increment based on MPS size fast MP$ path adjust for bin overlap deal with MPS deal with renormalize new fence The variables will all be treated as fixed-point numbers stored in fixed-length registers. Further optimizations are possible, such as unrolling code to reveal de- terministic comparisons, replacing multiplications and divisions by shifts, and never storing the value of Z into main memory. Encoding. The code for the encoder is similar to that of the decoder; it includes carry control by counting as in [7]: Encoder for Z-Coder ZE-1 Z := A + A; ZE-2 if (bit = MI>S) { ZE-3 if (Z < 1/2 ) ZE-4 else A := ZE-5 else ZE-6 if (Z ZE-7 C := C + 1 - Z; A := C+ 1 - Z; ZE-8 while (A > 1/2 ) ZE-9 emit ZE-10 A := increment based on slot size deal with MI>S fast path M I>S adjust for bin overlap deal with LI>S adjust for bin overlap shift to top of unit interval bit; output bit (includes carry control by counting) 2(A- 1/2); C :: 2(C- 1/2); } renormalize 3 Probability estimation Coding a binary event is always conditioned on a state in the model of the data, called the context of the event. For each context we maintain three pieces of information about the probabilities of the two possible symbols: the value of the LI>S (0 or 1), the probability pLPs of the LI>S, and the confidence that we have in our estimate. (We obviously could use MI>S values instead of LI>S values if it were convenient to do so.) > C I A + A < 1/2 ) + Prob(A + A > 1/2 ) Prob(Z > C IA + A > 1/2 ). We find that p,.s = zx - (zx + 1/2 ) log(zx + 1/2 ) - (zx - 1/2 ) log 1/2, implicitly defining A as a function of PL,s. Decoding a random sequence of independent equiprobable bits produces a random sequence of independent symbols distributed as derived above. Conversely, encod- ing such a random sequence of symbols under the same assumptions will produce a random sequence of equiprobable bits. Thus A is the optimal increment when the probability of the LPS is PLPS. We have confirmed this formula by experiments seeking the optimum increment for chosen symbol probabilities. Encoding a random symbol string with this optimal increment produces about 0.5% more code bits than predicted by the entropy. This appears to be the cost of the additive approximation to the computation of Z. >

The Z-Coder Adaptive Binary Coder In Proceedings of IEEE Data Compression Conference DCC'98, pages 13-22, Snowbird, March 1998