Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
modern arithmetic coders
71 views
Skip to first unread message
Sebastian
Jan 18, 2012, 9:55:49 AM1/18/12
to
Hi!
Recent posts sparked my interest in efficient implementations of
arithmetic coding again. The "CABA coder" (CABAC = context adaptive
binary arithmetic coding) used in the H.264 video compression standard
seems to be very interesting. It's also table-based and reduces the
approximation errors during interval subdivision by using two high
order bits of the current interval size in addition to the current
"context" as part of the lookup table index for approximating
"A*Pr(LPS)".
What is actually the patent situation for these kinds of things
(including MQ-, QM- coders etc)?
Also, I'm not sure on how to estimate the overhead due to bit
stuffing / byte stuffing. Let's take the arithmetic coder from JBIG2
for example. It outputs octets from the code register every now and
then. My understanding is that overflow is restricted to not propagate
beyond the last extracted octet by inserting a zero bit in case a 0xFF
byte could otherwise overflow. If my intuition is correct this
procedure reduces the coding space by 0.5/256 = 0.2% which should
increase the expected length of the coded stream by about 0.035%. Is
this correct?
Cheers!
SG
Recent posts sparked my interest in efficient implementations of
arithmetic coding again. The "CABA coder" (CABAC = context adaptive
binary arithmetic coding) used in the H.264 video compression standard
seems to be very interesting. It's also table-based and reduces the
approximation errors during interval subdivision by using two high
order bits of the current interval size in addition to the current
"context" as part of the lookup table index for approximating
"A*Pr(LPS)".
What is actually the patent situation for these kinds of things
(including MQ-, QM- coders etc)?
Also, I'm not sure on how to estimate the overhead due to bit
stuffing / byte stuffing. Let's take the arithmetic coder from JBIG2
for example. It outputs octets from the code register every now and
then. My understanding is that overflow is restricted to not propagate
beyond the last extracted octet by inserting a zero bit in case a 0xFF
byte could otherwise overflow. If my intuition is correct this
procedure reduces the coding space by 0.5/256 = 0.2% which should
increase the expected length of the coded stream by about 0.035%. Is
this correct?
Cheers!
SG
Thomas Richter
Jan 18, 2012, 4:23:32 PM1/18/12
to
On 18.01.2012 15:55, Sebastian wrote:
> Hi!
>
> Recent posts sparked my interest in efficient implementations of
> arithmetic coding again. The "CABA coder" (CABAC = context adaptive
> binary arithmetic coding) used in the H.264 video compression standard
> seems to be very interesting. It's also table-based and reduces the
> approximation errors during interval subdivision by using two high
> order bits of the current interval size in addition to the current
> "context" as part of the lookup table index for approximating
> "A*Pr(LPS)".
Indeed, it puts most of the logic in tables where MQ/QM still have
> Hi!
>
> Recent posts sparked my interest in efficient implementations of
> arithmetic coding again. The "CABA coder" (CABAC = context adaptive
> binary arithmetic coding) used in the H.264 video compression standard
> seems to be very interesting. It's also table-based and reduces the
> approximation errors during interval subdivision by using two high
> order bits of the current interval size in addition to the current
> "context" as part of the lookup table index for approximating
> "A*Pr(LPS)".
additions. I wouldn't call it "complex", actually, as it is rather a
state machine that has its cleverness encoded in the state transitions.
> What is actually the patent situation for these kinds of things
> (including MQ-, QM- coders etc)?
free implementations. MQ and QM coder patents run out a couple of years
ago already, there are several actually: On bit-stuffing (MQ coder) and
on the MPS/LPS inversion handling. I always forgot which one was which,
but one of the patents was due to IBM (I believe the interchange) and
the other was from Mitsubishi. None of these should apply anymore to my
very knowledge, its too long ago. Just use them now. [This is not a
legal advice, of course. Patents are a minefield anyhow.]
> Also, I'm not sure on how to estimate the overhead due to bit
> stuffing / byte stuffing. Let's take the arithmetic coder from JBIG2
> for example. It outputs octets from the code register every now and
> then. My understanding is that overflow is restricted to not propagate
> beyond the last extracted octet by inserting a zero bit in case a 0xFF
> byte could otherwise overflow. If my intuition is correct this
> procedure reduces the coding space by 0.5/256 = 0.2% which should
> increase the expected length of the coded stream by about 0.035%. Is
> this correct?
the JPEG 2000 Marcellin book, I can check this out tomorrow. If we
assume that the output of the coder is approximately uniformely iid
(which is sensible of course) then 1/256 of the possible outcomes is
increased by 1 bit, thus I get (8/8 * 255/256 + 9/8 * 1/256)
approximately 0.05% overhead (what I get from this - probably wrong, too
late now). Of course, this is not entirely correct because one purpose
of the stuffed bit is to absorb any carry over, i.e. there are cases
where a carry-over can flow into this bit, and I'm getting too tired to
make a good model for that. Thus, coding space is even used a bit better
than that.
[J2K is here designed smart enough that all the possible overflow cases
do not generate conflicting marker codes, namely 0xff80 through 0xff8f
are reserved. Nice trick.]
Byte-stuffing creates a larger overhead, I get approximately 0.4% by a
similar simple computation. The QM coder does neither use this zero-byte
for carry-over resolution, thus the coding space is truly wasted
entirely and not even used for a faster implementation. Instead, it uses
the old carry-over delayed output approach which may cause very long
propagation delays (i.e. times where the input just accumulates carries
and delays the output until finally a very long stream of zeros and
0xffs - sorry 0xff 0x00 pairs) is generated.
There are a couple of completely different designs of arithmetic coders,
one of them being the ELS coder which operates on logarithmic space
(hence the name (*) e??? Logarithmic Scale) and thus avoids
multiplications in a different way. It wastes more coding space, but it
has a more precise computation of the coding interval size because it
avoids the "addition = multiplication" trick in the Q-coder family.
(*) well, not entirely true. Els Withers is also the nick name of the
inventor which I happen to know. (-; There are a couple of more stories
behind it - the ELS coder was one of the reasons why IBM finally agreed
to provide the MQ coder royality free for standards after Els made his
offer. Old stories...
So long,
Thomas
Sebastian
Jan 19, 2012, 7:31:07 AM1/19/12
to
Thank you Thomas for your comments.
On 18 Jan., 22:23, Thomas Richter wrote:
> I believe there is some discussion of that in either the Pink Book or
> the JPEG 2000 Marcellin book, I can check this out tomorrow. If we
> assume that the output of the coder is approximately uniformely iid
> (which is sensible of course) then 1/256 of the possible outcomes is
> increased by 1 bit, thus I get (8/8 * 255/256 + 9/8 * 1/256)
> approximately 0.05% overhead (what I get from this - probably wrong, too
> late now). Of course, this is not entirely correct because one purpose
> of the stuffed bit is to absorb any carry over, i.e. there are cases
> where a carry-over can flow into this bit, and I'm getting too tired to
> make a good model for that. Thus, coding space is even used a bit better
> than that.
Yes, but I the difference should not really matter. I don't expect a
significant influence on the overhead.
> [J2K is here designed smart enough that all the possible overflow cases
> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
> are reserved. Nice trick.]
Hmm... I would have expected that this bit stuffing makes the sequence
"0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
After all, the purpose of bit stuffing is to avoid overflowing 0xFF
bytes, isn't it? So, by inserting a zero bit you get in the worst case
"0xFF 0x7F" where the 0x7F might be changed to 0x80 later due to a
carry. Maybe I misunderstood the way this bit stuffing works.
I just checked the J2K's final draft and what I found was that the
spec defines markers to be anything between (including) 0xFF 0x01 ...
0xFF 0xFE.
> Byte-stuffing creates a larger overhead, I get approximately 0.4% by a
> similar simple computation.
Makes sense.
> The QM coder does neither use this zero-byte
> for carry-over resolution, thus the coding space is truly wasted
> entirely and not even used for a faster implementation. Instead, it uses
> the old carry-over delayed output approach which may cause very long
> propagation delays (i.e. times where the input just accumulates carries
> and delays the output until finally a very long stream of zeros and
> 0xffs - sorry 0xff 0x00 pairs) is generated.
Ok. AFAIK this is how it's done in H.264 as well. I guess they can
afford it and confine this delay to a single "frame packet" (or
whatever the correct terminology is) via a complete init/flush cycle
of the arithmetic coder.
> There are a couple of completely different designs of arithmetic coders,
> one of them being the ELS coder which operates on logarithmic space
> (hence the name (*) e??? Logarithmic Scale) and thus avoids
Entropy Logarithmic Scale.
> multiplications in a different way. It wastes more coding space, but it
> has a more precise computation of the coding interval size because it
> avoids the "addition = multiplication" trick in the Q-coder family.
Interesting. Thanks for the pointer. I havn't yet read the papers,
though.
Cheers!
SG
On 18 Jan., 22:23, Thomas Richter wrote:
> I believe there is some discussion of that in either the Pink Book or
> the JPEG 2000 Marcellin book, I can check this out tomorrow. If we
> assume that the output of the coder is approximately uniformely iid
> (which is sensible of course) then 1/256 of the possible outcomes is
> increased by 1 bit, thus I get (8/8 * 255/256 + 9/8 * 1/256)
> approximately 0.05% overhead (what I get from this - probably wrong, too
> late now). Of course, this is not entirely correct because one purpose
> of the stuffed bit is to absorb any carry over, i.e. there are cases
> where a carry-over can flow into this bit, and I'm getting too tired to
> make a good model for that. Thus, coding space is even used a bit better
> than that.
significant influence on the overhead.
> [J2K is here designed smart enough that all the possible overflow cases
> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
> are reserved. Nice trick.]
"0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
After all, the purpose of bit stuffing is to avoid overflowing 0xFF
bytes, isn't it? So, by inserting a zero bit you get in the worst case
"0xFF 0x7F" where the 0x7F might be changed to 0x80 later due to a
carry. Maybe I misunderstood the way this bit stuffing works.
I just checked the J2K's final draft and what I found was that the
spec defines markers to be anything between (including) 0xFF 0x01 ...
0xFF 0xFE.
> Byte-stuffing creates a larger overhead, I get approximately 0.4% by a
> similar simple computation.
> The QM coder does neither use this zero-byte
> for carry-over resolution, thus the coding space is truly wasted
> entirely and not even used for a faster implementation. Instead, it uses
> the old carry-over delayed output approach which may cause very long
> propagation delays (i.e. times where the input just accumulates carries
> and delays the output until finally a very long stream of zeros and
> 0xffs - sorry 0xff 0x00 pairs) is generated.
afford it and confine this delay to a single "frame packet" (or
whatever the correct terminology is) via a complete init/flush cycle
of the arithmetic coder.
> There are a couple of completely different designs of arithmetic coders,
> one of them being the ELS coder which operates on logarithmic space
> (hence the name (*) e??? Logarithmic Scale) and thus avoids
> multiplications in a different way. It wastes more coding space, but it
> has a more precise computation of the coding interval size because it
> avoids the "addition = multiplication" trick in the Q-coder family.
though.
Cheers!
SG
Thomas Richter
Jan 19, 2012, 10:24:40 AM1/19/12
to
Am 19.01.2012 13:31, schrieb Sebastian:
>> [J2K is here designed smart enough that all the possible overflow cases
>> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
>> are reserved. Nice trick.]
>
> Hmm... I would have expected that this bit stuffing makes the sequence
> "0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
Yes, it does make 0xff 0x80 possible, but even fifteen additional
>> [J2K is here designed smart enough that all the possible overflow cases
>> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
>> are reserved. Nice trick.]
>
> Hmm... I would have expected that this bit stuffing makes the sequence
> "0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
sequences, namely 0xff 0x81 through 0xff 0x8f.
> After all, the purpose of bit stuffing is to avoid overflowing 0xFF
> bytes, isn't it? So, by inserting a zero bit you get in the worst case
> "0xFF 0x7F" where the 0x7F might be changed to 0x80 later due to a
> carry. Maybe I misunderstood the way this bit stuffing works.
would be indeed the maximum possible. However, it is only an approximate
arithmetic coder, which means that the "coding interval" does not stay
at a constant size of one, but it may grow larger than the unit interval
(due to the replacement of the multiplication by an addition). Thus, the
interval can grow larger, and thus the "overflow" can grow larger.
> I just checked the J2K's final draft and what I found was that the
> spec defines markers to be anything between (including) 0xFF 0x01 ...
> 0xFF 0xFE.
an entropy coded segment are not within this range, i.e. SOT, SOD, EOC,
EPH and SOP are all above the region, and 0xff 0x80 through 0xff 0x8f
are intentionally left undefined because they may appear in the entropy
coded data stream. It is no coincidence that SOT starts at 0xff 0x90 and
that we have marker sequences above 0xff 0x8f and below 0xff 0x80 - two
groups actually. Those that appear in headers, and those that appear in
the entropy coded data.
>> There are a couple of completely different designs of arithmetic coders,
>> one of them being the ELS coder which operates on logarithmic space
>> (hence the name (*) e??? Logarithmic Scale) and thus avoids
>
> Entropy Logarithmic Scale.
>
>> multiplications in a different way. It wastes more coding space, but it
>> has a more precise computation of the coding interval size because it
>> avoids the "addition = multiplication" trick in the Q-coder family.
>
> Interesting. Thanks for the pointer. I havn't yet read the papers,
> though.
Greetings,
Thomas
Sebastian
Jan 19, 2012, 12:40:25 PM1/19/12
to
On 19 Jan., 16:24, Thomas Richter wrote:
> Am 19.01.2012 13:31, schrieb Sebastian:
>
> >> [J2K is here designed smart enough that all the possible overflow cases
> >> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
> >> are reserved. Nice trick.]
>
> > Hmm... I would have expected that this bit stuffing makes the sequence
> > "0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
>
> Yes, it does make 0xff 0x80 possible, but even fifteen additional
> sequences, namely 0xff 0x81 through 0xff 0x8f.
Are you sure?
> Am 19.01.2012 13:31, schrieb Sebastian:
>
> >> [J2K is here designed smart enough that all the possible overflow cases
> >> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
> >> are reserved. Nice trick.]
>
> > Hmm... I would have expected that this bit stuffing makes the sequence
> > "0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
>
> Yes, it does make 0xff 0x80 possible, but even fifteen additional
> sequences, namely 0xff 0x81 through 0xff 0x8f.
> > After all, the purpose of bit stuffing is to avoid overflowing 0xFF
> > bytes, isn't it? So, by inserting a zero bit you get in the worst case
> > "0xFF 0x7F" where the 0x7F might be changed to 0x80 later due to a
> > carry. Maybe I misunderstood the way this bit stuffing works.
>
> No, you didn't. If the MQ coder would be an ideal coder, then 0xff 0x80
> would be indeed the maximum possible. However, it is only an approximate
> arithmetic coder, which means that the "coding interval" does not stay
> at a constant size of one, but it may grow larger than the unit interval
> (due to the replacement of the multiplication by an addition). Thus, the
> interval can grow larger, and thus the "overflow" can grow larger.
of having finite precision during interval subdivision. I also fail to
see what this has to do with anything. Secondly, the MQ decoder
defines three additional buffer bits or "space" bits (s) in the code
registers
MSB LSB
---------------------------------------------------
C-register: 0000 cbbb bbbb bsss xxxx xxxx xxxx xxxx
A-register: 0000 0000 0000 0000 aaaa aaaa aaaa aaaa
between the lowest 16 bits and the upper 9 bits that store 1 carry
bit + 8 "data" bits. And "A" is practically restricted to [0x8000,
0xFFFF] (when normalized, even though 0x8000 "represents" 0.75 in some
mental model). So, after an 0xFF byte with stuffing a zero bit into
the C register the worst case in terms of carry propagation for the
register values would be
MSB LSB
---------------------------------------------------
C-register: 0000 0011 1111 1111 1111 1111 1111 1111
+A-register: 0000 0000 0000 0000 1111 1111 1111 1111
----------------------------------------------------
0100 0000 0000 1111 1111 1111 1110
\________/
0x80
Wouldn't it? -- The sum C+A represents an upper bound of the possible
code which will make it into the stream. I don't see how the byte that
follows 0xFF can be any higher than 0x80. Where is my mistake?
Cheers!
SG
Thomas Richter
Jan 20, 2012, 3:31:29 AM1/20/12
to
Am 19.01.2012 18:40, schrieb Sebastian:
> On 19 Jan., 16:24, Thomas Richter wrote:
>> Am 19.01.2012 13:31, schrieb Sebastian:
>>
>>>> [J2K is here designed smart enough that all the possible overflow cases
>>>> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
>>>> are reserved. Nice trick.]
>>
>>> Hmm... I would have expected that this bit stuffing makes the sequence
>>> "0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
>>
>> Yes, it does make 0xff 0x80 possible, but even fifteen additional
>> sequences, namely 0xff 0x81 through 0xff 0x8f.
>
> Are you sure?
Certainly. Just to give you an example, here is an excerpt from a
> On 19 Jan., 16:24, Thomas Richter wrote:
>> Am 19.01.2012 13:31, schrieb Sebastian:
>>
>>>> [J2K is here designed smart enough that all the possible overflow cases
>>>> do not generate conflicting marker codes, namely 0xff80 through 0xff8f
>>>> are reserved. Nice trick.]
>>
>>> Hmm... I would have expected that this bit stuffing makes the sequence
>>> "0xFF 0x80" still possible due to carry propagation for "0xFF 0x7F".
>>
>> Yes, it does make 0xff 0x80 possible, but even fifteen additional
>> sequences, namely 0xff 0x81 through 0xff 0x8f.
>
> Are you sure?
losslessly compressed version of "boats" in JPEG 2000, in the middle of
the entropy coded segment we have the following (this is not a marker)!
002f4f0 0a04 97ab d40a 4cf3 eb17 ae50 abc3 cc08
002f500 5e65 dbfd f633 84da 719c 08d2 e090 fe50
002f510 7228 49ff 8f36 09fb 439a de79 d884 989c
^^ ^^
002f520 2a6a 6dce f0cf f61a 2587 f62e 925d b249
002f530 3b8e 2f50 01fd 1db0 73c9 3668 7f26 4c04
This is actually not the only place, there are many others were you have
this extreme carry-over.
> First of all, I would define "approximate arithmetic coder" in terms
> of having finite precision during interval subdivision. I also fail to
> see what this has to do with anything.
0x8000 / 0.75 = 0xaaaa
I don't know exactly what the worst case is, but surely it cannot grow
larger than 0xffff = 1.5, i.e. when we add half of the coding interval
(worst case, equal probability) to it. So A can grow larger than it
should, ideally, and thus the carry into the C register can grow larger
than it should. That's my simple-minded explanation.
> Secondly, the MQ decoder
> defines three additional buffer bits or "space" bits (s) in the code
> registers
>
> MSB LSB
> ---------------------------------------------------
> C-register: 0000 cbbb bbbb bsss xxxx xxxx xxxx xxxx
> A-register: 0000 0000 0000 0000 aaaa aaaa aaaa aaaa
>
> between the lowest 16 bits and the upper 9 bits that store 1 carry
> bit + 8 "data" bits. And "A" is practically restricted to [0x8000,
> 0xFFFF] (when normalized, even though 0x8000 "represents" 0.75 in some
> mental model). So, after an 0xFF byte with stuffing a zero bit into
> the C register the worst case in terms of carry propagation for the
> register values would be
>
> MSB LSB
> ---------------------------------------------------
> C-register: 0000 0011 1111 1111 1111 1111 1111 1111
> +A-register: 0000 0000 0000 0000 1111 1111 1111 1111
> ----------------------------------------------------
> 0100 0000 0000 1111 1111 1111 1110
> \________/
> 0x80
>
> Wouldn't it? -- The sum C+A represents an upper bound of the possible
> code which will make it into the stream. I don't see how the byte that
> follows 0xFF can be any higher than 0x80. Where is my mistake?
restricted as said, but C isn't.
Greetings,
Thomas
glen herrmannsfeldt
Jan 20, 2012, 6:15:59 AM1/20/12
to
Thomas Richter <th...@math.tu-berlin.de> wrote:
(snip)
> 002f4f0 0a04 97ab d40a 4cf3 eb17 ae50 abc3 cc08
> 002f500 5e65 dbfd f633 84da 719c 08d2 e090 fe50
> 002f510 7228 49ff 8f36 09fb 439a de79 d884 989c
> ^^ ^^
> 002f520 2a6a 6dce f0cf f61a 2587 f62e 925d b249
> 002f530 3b8e 2f50 01fd 1db0 73c9 3668 7f26 4c04
Is this from a big-endian or little endian machine. Last I knew,
od -x and xd printed 16 bit words in native byte order.
-- glen
(snip)
> 002f4f0 0a04 97ab d40a 4cf3 eb17 ae50 abc3 cc08
> 002f500 5e65 dbfd f633 84da 719c 08d2 e090 fe50
> 002f510 7228 49ff 8f36 09fb 439a de79 d884 989c
> ^^ ^^
> 002f520 2a6a 6dce f0cf f61a 2587 f62e 925d b249
> 002f530 3b8e 2f50 01fd 1db0 73c9 3668 7f26 4c04
od -x and xd printed 16 bit words in native byte order.
-- glen
Thomas Richter
Jan 20, 2012, 6:35:54 AM1/20/12
to
not swap endian-ness:
00161560 da 3a 5b 2c 68 f6 f0 f6 f7 de 22 dd dd f5 57 5c
00161570 3b 73 46 c7 ff 8d a2 6a ee 80 67 21 d6 6c bf 16
^^^^^^
00161580 ae f0 c9 fb de 75 fd ec 1d 51 66 95 4d a0 df 0d
It's not a ff 8f, but a ff 8d, but good enough. Not a marker, either.
Greetings,
Thomas
Sebastian
Jan 21, 2012, 10:23:26 AM1/21/12
to
On 20 Jan., 09:31, Thomas Richter wrote:
> Am 19.01.2012 18:40, schrieb Sebastian:
>
> > Are you sure?
>
> Certainly. [...]
missing an important detail.
> I don't know exactly what the worst case is, but surely it cannot grow
> larger than 0xffff = 1.5, i.e. when we add half of the coding interval
> (worst case, equal probability) to it. So A can grow larger than it
> should, ideally, and thus the carry into the C register can grow larger
> than it should. That's my simple-minded explanation.
This doesn't make sense to me. Why do you say it's possible for A to
_GROW_ beyond 0xFFFF when
(a) it's getting smaller during inverval subdivision and
(b) normalization is done while A<0x8000 which can yield
a final A-value of not more than 0xFFFE
?!
Generally it is not restricted like this, but in this case—after bit
stuffing—it should be, shouldn't it?!
Cheers!
SG
> Am 19.01.2012 18:40, schrieb Sebastian:
>
> > Are you sure?
>
> Certainly. [...]
>
> > First of all, I would define "approximate arithmetic coder" in terms
> > of having finite precision during interval subdivision. I also fail to
> > see what this has to do with anything.
>
> The unit interval can get larger than 1.0, which is represented as
> 0x8000 / 0.75 = 0xaaaa
So? A is still restricted to 0xFFFF isn't it? I guess I'm still
> > First of all, I would define "approximate arithmetic coder" in terms
> > of having finite precision during interval subdivision. I also fail to
> > see what this has to do with anything.
>
> The unit interval can get larger than 1.0, which is represented as
> 0x8000 / 0.75 = 0xaaaa
missing an important detail.
> I don't know exactly what the worst case is, but surely it cannot grow
> larger than 0xffff = 1.5, i.e. when we add half of the coding interval
> (worst case, equal probability) to it. So A can grow larger than it
> should, ideally, and thus the carry into the C register can grow larger
> than it should. That's my simple-minded explanation.
_GROW_ beyond 0xFFFF when
(a) it's getting smaller during inverval subdivision and
(b) normalization is done while A<0x8000 which can yield
a final A-value of not more than 0xFFFE
?!
stuffing—it should be, shouldn't it?!
Cheers!
SG
Thomas Richter
Jan 22, 2012, 4:37:41 PM1/22/12
to
On 21.01.2012 16:23, Sebastian wrote:
> On 20 Jan., 09:31, Thomas Richter wrote:
>> Am 19.01.2012 18:40, schrieb Sebastian:
>>
>>> Are you sure?
>>
>> Certainly. [...]
>>
>>> First of all, I would define "approximate arithmetic coder" in terms
>>> of having finite precision during interval subdivision. I also fail to
>>> see what this has to do with anything.
>>
>> The unit interval can get larger than 1.0, which is represented as
>> 0x8000 / 0.75 = 0xaaaa
>
> So? A is still restricted to 0xFFFF isn't it? I guess I'm still
> missing an important detail.
A is indeed restricted (see below), though 0xffff is not 1.0, but
> On 20 Jan., 09:31, Thomas Richter wrote:
>> Am 19.01.2012 18:40, schrieb Sebastian:
>>
>>> Are you sure?
>>
>> Certainly. [...]
>>
>>> First of all, I would define "approximate arithmetic coder" in terms
>>> of having finite precision during interval subdivision. I also fail to
>>> see what this has to do with anything.
>>
>> The unit interval can get larger than 1.0, which is represented as
>> 0x8000 / 0.75 = 0xaaaa
>
> So? A is still restricted to 0xFFFF isn't it? I guess I'm still
> missing an important detail.
(almost) 1.5.
>> I don't know exactly what the worst case is, but surely it cannot grow
>> larger than 0xffff = 1.5, i.e. when we add half of the coding interval
>> (worst case, equal probability) to it. So A can grow larger than it
>> should, ideally, and thus the carry into the C register can grow larger
>> than it should. That's my simple-minded explanation.
>
> This doesn't make sense to me. Why do you say it's possible for A to
> _GROW_ beyond 0xFFFF when
>
> (a) it's getting smaller during inverval subdivision and
>
> (b) normalization is done while A<0x8000 which can yield
> a final A-value of not more than 0xFFFE
interval. In an ideal implementation, the size of the interval cannot
grow larger than 1. If it is getting smaller than 0.5, it is
renormalized, but it cannot become larger than 1. In the MQ coder, it
can get larger than 1.0 = 0xc000.
i.e. the form
0000 cbbb bbbb bsss xxxx xxxx xxxx xxxx
0x0848 2fc4
Since C run into the carry, the topmost 8 bits are removed, and B
becomes 0x84. The topmost 8 bit are then removed, but only 7 bits are
cleared in the bit-counter.
In every step of the coder, the following is the "worst case": q (the
probability estimate) is added to c, and c is doubled. This happens at
most 8 times. The worst case initial c is 0x7ffff, i.e. if b has been
removed, the b-bits are cleared and all spacer-bits and all x-bits are
one. Now, on every step I get at worst:
c <- 2(c + q)
eight times - eight because the bit counter is at most eight. Summing up
this series, I get for the worst case:
c = 0x7ffff * 2^8 + q * (2^8 + 2^7 + 2^6 +...+ 2) = 0x7ffff * 256 + q * 510.
The worst case value for q is 0x5601 (unless I mistaken) so the largest
value c can get from this would be
0x8ab54fe
so according to this logic, b can be at most 0x8a (and not 0x80). Still,
there is something wrong because in the above we have b = 0x8d. I don't
quite see my error here, but probably you find out. But at least, c can
surely grow larger than it should. This is also because q = 0x5601 is
actually "larger than it should", because this is a value larger than
0.5 = 0x5555, all this because the encoder is not ideal, but the values
are somewhat "tuned" to improve the performance.
Well, maybe you find the reason why I see there a 0x8d because I'm
currently out of ideas (everything else, packet headers etc. use strict
bit-stuffing, so its not up to them), but at least we've seen that 0x80
is certainly not the limit for B.
HTHH,
Thomas
Sebastian
Jan 23, 2012, 11:37:06 AM1/23/12
to
On 22 Jan., 22:37, Thomas Richter wrote:
> [...]
> [...]
MPS/LPS exchange as well as the possibility of two or more
renormalization cycles before further interval subdivisions. So, what
you're computing here seems to be a weak upper bound for C. But a
weak upper bound is of no use if you want to show that B can actually
reach values above 0x80 (with "previous_B==0xFF") in reality.
> 0x8ab54fe
> so according to this logic, b can be at most 0x8a (and not 0x80).
"Can it"? The only conclusion we can draw here (if we ignore the
mistakes) is that the final B value won't be larger than 0x8B.
Of course, to prove that B can actually be as large as 0x8D in this
case, we only need an example (which you found apparently). But I
would prefer to understand the details rather than just looking at
examples.
Cheers!
SG
> [...]
> First, a minor detail: C has in the implementation I use two more bits,
> i.e. the form
>
> 0000 cbbb bbbb bsss xxxx xxxx xxxx xxxx
That looks exactly like the layout I mentioned.
> i.e. the form
>
> 0000 cbbb bbbb bsss xxxx xxxx xxxx xxxx
> [...]
> In every step of the coder, the following is the "worst case": q (the
> probability estimate) is added to c, and c is doubled.
> [...]
> probability estimate) is added to c, and c is doubled.
> The worst case value for q is 0x5601 (unless I mistaken) so the largest
> value c can get from this would be
This does not convince me. It seems that you missed the conditional
> value c can get from this would be
MPS/LPS exchange as well as the possibility of two or more
renormalization cycles before further interval subdivisions. So, what
you're computing here seems to be a weak upper bound for C. But a
weak upper bound is of no use if you want to show that B can actually
reach values above 0x80 (with "previous_B==0xFF") in reality.
> 0x8ab54fe
> so according to this logic, b can be at most 0x8a (and not 0x80).
mistakes) is that the final B value won't be larger than 0x8B.
Of course, to prove that B can actually be as large as 0x8D in this
case, we only need an example (which you found apparently). But I
would prefer to understand the details rather than just looking at
examples.
Cheers!
SG
Thomas Richter
Jan 25, 2012, 4:45:58 AM1/25/12
to
Am 23.01.2012 17:37, schrieb Sebastian:
> On 22 Jan., 22:37, Thomas Richter wrote:
> This does not convince me. It seems that you missed the conditional
> MPS/LPS exchange as well as the possibility of two or more
> renormalization cycles before further interval subdivisions.
Not really. Look, the MPS/LPS exchange is rather irrelevant for the
> On 22 Jan., 22:37, Thomas Richter wrote:
> This does not convince me. It seems that you missed the conditional
> MPS/LPS exchange as well as the possibility of two or more
> renormalization cycles before further interval subdivisions.
argument. You can always arrange the input symbol such that you run into
the case of c + q -> c, whether by conditional exchange or regular coding.
> So, what
> you're computing here seems to be a weak upper bound for C. But a
> weak upper bound is of no use if you want to show that B can actually
> reach values above 0x80 (with "previous_B==0xFF") in reality.
above 0x80 in reality. You know, it doesn't become more real than reality.
The problem is that if you want to see a mathematical proof *other* than
just pointing at a particular symbol sequence and say "here look!", then
it gets soon very complicated because you need to take all the
simplifications of the MQ into consideration - it is not an ideal coder,
so one cannot just argue by interval-subdivision, you need to look at
the particual implementation. One can do a little better
than what I did before, but not much without getting it overhelmingly
complicated. So for example, if we include all the "short MPS" case
in the considerations, the argument may go as follows:
Clearly, C must grow as large as possible, so we need to consider worst
cases. This means: Add the largest possible value to C, renormalize as
little as possible (as this decrements the bit-counter). So you would
need to run into the short-MPS case very often, thus A must be as large
as possible as short MPS only happens if A >= 0x8000. Thus, start with
A=0xffff. Q also needs to be as large as possible. Qmax is 0x5601, which
can be subtracted two times from A without getting under 0x8000, thus c
+ 2*q -> c. At this stage, A is still larger than q, so by arranging the
input sequence apropriately, you can still assume that
you run into the +q case, MPS coding without exchange, or LPS coding
with exchange, doesn't matter. So c + 3*q -> c. At this stage, you
renormalize, so ct - 1 -> ct, 2 c -> c, 2a -> a. By following this logic
until t=0, you get an upper bound for B. It is, however, no longer as
simple as evaluating a geometric series anymore, because q is not always
added three times to c before renormalizing - assuming that provides you
an upper bound for B which is 0xa0. Correct, but one can do better as B
stays below 0x90 as stated.
> Of course, to prove that B can actually be as large as 0x8D in this
> case, we only need an example (which you found apparently). But I
> would prefer to understand the details rather than just looking at
> examples.
have the algorithm in front of you, but if you want it simpler than just
following its flow and considering the worst cases, the bounds become
weaker. I afraid you cannot get both a strong bound *and* a simple proof.
So long,
Thomas
Thomas Richter
Feb 1, 2012, 10:00:07 AM2/1/12
to
Am 25.01.2012 10:45, schrieb Thomas Richter:
> Am 23.01.2012 17:37, schrieb Sebastian:
>> On 22 Jan., 22:37, Thomas Richter wrote:
>
>> This does not convince me. It seems that you missed the conditional
>> MPS/LPS exchange as well as the possibility of two or more
>> renormalization cycles before further interval subdivisions.
>
> Not really. Look, the MPS/LPS exchange is rather irrelevant for the
> argument. You can always arrange the input symbol such that you run into
> the case of c + q -> c, whether by conditional exchange or regular coding.
Here's at least a nice and simple argument why the the output cannot be
> Am 23.01.2012 17:37, schrieb Sebastian:
>> On 22 Jan., 22:37, Thomas Richter wrote:
>
>> This does not convince me. It seems that you missed the conditional
>> MPS/LPS exchange as well as the possibility of two or more
>> renormalization cycles before further interval subdivisions.
>
> Not really. Look, the MPS/LPS exchange is rather irrelevant for the
> argument. You can always arrange the input symbol such that you run into
> the case of c + q -> c, whether by conditional exchange or regular coding.
larger or than a 0xff 0x8f, together with the example that such output
is generated, I believe it completes the argument:
The maximum value of the C register in a non-carry-over case is 2^19-1,
i.e. all bits including the spacer bits are set. In the carry-over case,
one bit even remains in the buffer, and then the maximum value is
2^20-1, however, the bit-counter is in that case set to seven (seven
free bits) rather than eight as in the usual case. The bit-counter is
also set to seven if an 0xff appeared, though the complete top 8 bits
were removed, and this is the only case we talked about.
A is now the size of the coding interval, even though normalized in a
strange way. If you follow the flow-chart of the encoder, I may add Q to
C, but only as long as A remains larger than Q, and Q is subtracted from
A. So the maximum value I may add to C is the value of A in each step,
and the maximum value of A is of course 2^16-1.
Thus, after eight (or seven, in the carry-over-case), the value of C is
at most
2^8 * (2^19 + 2^16) - 1 = 2^27 + 2^24 - 1 in the regular case or
2^7 * (2^20 + 2^16) - 1 = 2^27 + 2^23 - 1 in the carry-over case
2^7 * (2^19 + 2^16) - 1 = 2^26 + 2^23 - 1 in the bit-stuffing case.
If the last output was a 0xff, we are in the last case as only room for
seven bits was allocated. The generated B register is now composed from
the topmost 8 bit, i.e. bit 19 onwards. Thus B can be, in this case, at
most
(2^26 + 2^23) / 2^19 - 1 = 2^7 + 2^4 - 1 = 0x8f
which was claimed.
Sorry, this took longer than necessary, but I had not much spare time....
HTHH,
Thomas
0 new messages