range coder

hi all!

i'm fiddling around to implement a range coder as a backend to an acb
style modeller (for education purposes). somehow i reinvented "acb" :D

the range coders i've seen so far look like a low precision arithmetic
(mentioned in some paper, by moffat, i think, can't remember it) coder
with normalization in octets.

my problem is, when i use 32 bit arithmetic for calculations, i lose
too much precision to enable decoding. for example during normalisation
m. schindler's implementation saves the first 8 bits starting at bit 23
of the low register (he uses bit 31 to handle the underflow digit
detection), so we got 8 more bits, which are shifted in to gain
precision. i wanted my implementation to act more like the "classic"
describtion of arithmetic coding: if the first digit (when i say digit,
i mean an octet) doesn't match and the second one in high and low are
looking like an underflow occuring, discard the second significant
digit and use a counter to keep track of the underflow digits. but this
approce doesn't work!
an example:

high = 20 00 10 00
low = 1F FF FF FF

so range is:

range = 10 01

basically range is a 16 bit number, so if i store the cumulative
probabilities as 14 bit integers, the result of

range = range / totals

is a 2 bit integer, which seems to be too less to achieve enough
precision for decoding. but i wanted my frequencies to be represented
by more than 14 bits...
some papers about rangecoders say, we can use more bits for frequencie
counts, is this really true, looking at the example above.
and something, which was always a thorn in my side: why does a range
coder reserve extra code space for the last symbol of the cumulative
probabilieties?!

did i got anything wrong about range coding?

any suggestions would be helpful.

a link to the original paper about rangecoding and the paper about low
precision arithmetic encodng would also be nice.

by the way, cr88192, if you read this, are u german?

greets

.

Relevant Pages

  • Re: Rounding errors
    ... Take for example 10 random single digit numbers. ... if you take a set of large precision random numbers between ... The rounding to 2 digits will restore the full count 500,500. ... But it is not the _roundeing_ that is wrong, it is the truncation to ...
    (comp.lang.cobol)
  • Re: Another question about big floating point
    ... I've been programming that bignum floating point thing I've talked ... We just lose a whole 32-bit dword "digit" from the number's ... effectively only 32 bits of precision)? ... annoyances of the hex float historically used by S/ ...
    (comp.programming)
  • =?Utf-8?Q?Re:_I_don=C2=B4t_view_the_value_right?= =?Utf-8?Q?_after_six_decimal_place_in_Exce
    ... accuracy--probably IEEE quadruple precision, which is far more than the IEEE ... The 16th digit in 2179,0089519999972104171 is a 7, which rounds up to give ... "David Biddulph" wrote: ...
    (microsoft.public.excel.misc)
  • Re: long double in gcc implementations
    ... some of Mr. Navia's built-in math functions, ... char Pause; ... the full 100 digit precision claimed by qfloat. ...
    (comp.lang.c)