Subject: Re: [rohc] W-LSB encoding problem

From: "Wang Haiguang" <[email-masked]>
Date: Mon, 3 Jun 2002 13:07:55 +0800

Hi, Stefan.

Based on my understanding.

In my view, half of the range as the upper boundary of window width is not
safe.

For example, in a range of [0, 65535], assume you have following numbers in
your

window [29000, 60000, 50000], assume v = 19000.

60000 - 29000 = 31000 < 32767

In such case, k = 15.

If the decompressor using 50000 as reference, it will get 51768 instead of
19000.

I think the upper boundary of the window width should be 8192 in such a
case.

That means, when your window width is greater than 8192, you may got a wrong
value.

Welcome for the comments.

Best regards.

Haiguang

----- Original Message -----
From: "Stefan Hendrata" <[email-masked]>
To: <[email-masked]>
Sent: Saturday, June 01, 2002 2:02 AM
Subject: Re: [rohc] W-LSB encoding problem

> Hello,
>
> your analysis looks correct.
>
> Actually, I also got some other responses telling me to use uncompressed
> IP-ID transmission in such a case. In fact I wasn't using fully randomized
> sequences but sequences that contain a random change after a number of
> uniform increments and I was thinking that the W-LSB compression would be
> "robust" enough to deal with such random changes.
>
> After discussing this issue with a colleague and thinking about it, I came
to
> the following conclusion:
>
> Remember that the sliding window contains all reference values that the
> decompressor could possibly use, and the compressor is looking for the
> reference value yielding the greatest number k of bits. Thus, using v_min
and
> v_max of a sliding window to determine the greatest number k of bits
needed
> to be transmitted works only if v_min and v_max have the minimum and
maximum
> distances to v compared with all values in the sliding window.
>
> Taking wrap-around arithmetic into account, this is only true as long as
> v_max - v_min remains smaller than the half of the range of values. If
v_max
> - v_min becomes larger, it is no longer assured that v_min and v_max have
the
> minimum and maximum distances to v (as can be seen in the example given in
my
> first posting),
>
> Thus, a simple and effective solution to my problem was:
> - If the width of the sliding window is smaller than the half of the range
of
> values, use the algorithm as described in the RFC to determine the number
k
> of bits.
> - If the width of the sliding window is equal or larger than the half of
the
> range of values, transmit all bits.
>
> This one-line-workaround made our W-LSB encoder "robust" to deal with
random
> changes.
>
> I understand that the RFC contains statements regarding the limitation of
the
> maximum width of the sliding window for U- and O-mode. So this issue may
be
> of no practical relevance but it is theoretically interesting though.
>
> Stefan Hendrata
>
>
>
> On Wednesday 29 May 2002 07:25, you wrote:
> > Hi.
> >
> > Following is based on my understanding.
> > I think the main reason is because the interpretation interval function
in
> > ROHC didn't consider the random change in numbers.
> >
> > Let's assume rule d) proposed in rfc3095 page 26 is used by both
compressor
> > and decompressor. That is:
> > f(v_ref, k) = [v_ref - 2^(k-2) + 1, v_ref + 2^(k-2) *3].
> > We also assume the maximum number is 65535 (two bytes integer)
> >
> > For your case, the window has three values (100, 60000, 50000), thus the
> > v_min = 100,
> > v_max = 60000, v = 2000.
> >
> > k1 = g(v_min, v) = g(100, 2000) = 12.
> > k2 = g(v_max, v) = g(60000, 2000) = 14;
> >
> > Thus k = max(k1, k2) = 14.
> >
> > The bits carried in header will be 00 0111 1101 0000.
> > The decompressor interprates the value by replace the lower 14 bits of
> > 50000 (1100 0011 0101 0000) by the above bits string and get 1100 0111
1101
> > 0000 = 51152.
> >
> > The reason is becuause the 50000 jumps back too much in the current rule
d)
> > and cause the value 2000 out of the intersection of the interpretation
> > interval of the 50000 and 60000.
> > Interpretation interval for 50000 : [45905, 62288]
> > Interpretation interval for 60000 : [55905, 6752]
> >
> > The lower boundry you can jump back is 55248, that means if the third
value
> > in the window is less than 55248, you may get 51152. If it is greater
than
> > or equal 55248, you will get the
> > right value, 2000.
> >
> > So, if you want to send random values, you'd better send all the bits
> > instead of using W-LSB, for example, the IP_ID filed in the IPV4 header,
> > when rnd is on, it is send without
> > compression.
> >
> > If anything wrong in my analysis, please point it out. Let's understand
it
> > together.
> >
> > Best regards.
> >
> > Haiguang
> >
> >
> > ----- Original Message -----
> > From: "Stefan Hendrata" <[email-masked]>
> > To: <[email-masked]>
> > Sent: Tuesday, May 28, 2002 10:27 PM
> > Subject: [rohc] W-LSB encoding problem
> >
> > > Hello,
> > >
> > > My company is also working on a ROHC implementation and I've come
across
> > > a problem with the W-LSB encoding scheme for which I don't have an
> >
> > explanation
> >
> > > yet:
> > >
> > > I have feeded our W-LSB encoder/decoder with sequences of numbers
> >
> > containing
> >
> > > both uniform increments and random changes for testing. This brought
me
> > > to
> >
> > a
> >
> > > problem of incorrect encoding and decoding, and I don't know if the
error
> > > lies within our understanding of W-LSB encoding/decoding or if it's
> > > within the scheme itself.
> > >
> > > To come straight to the problem, please look at the following sample
> >
> > sequence:
> > > 100
> > > 60000
> > > 50000
> > > 2000
> > >
> > > After encoding and decoding the first three numbers, the W-LSB encoder
> > > has
> >
> > a
> >
> > > v_min of 100 and a v_max of 60000. v_ref of the W-LSB decoder has the
> >
> > value
> >
> > > 50000. Now, for encoding and decoding the fourth value v=2000, the
> > > encoder takes v_min and v_max to calculate the number k of bits
needed.
> > > If the decoder gets these k bits and decodes them, it yields a value
of
> > > 51152
> >
> > which
> >
> > > is of course unequal to 2000. Apparently, the number of bits k is not
> > > high enough, but k results from v_min and v_max which are closer to
the
> > > wrongly decoded value (wrap-around view) than the decoder's v_ref.
> > >
> > > So, the simple question is: What's wrong here?
> > >
> > >
> > > Thank you,
> > > Stefan Hendrata
> > > acticom GmbH, Germany
> > >
> > >
> > > _______________________________________________
> > > Rohc mailing list
> > > [email-masked]
> > > https://www1.ietf.org/mailman/listinfo/rohc
> >
> > _______________________________________________
> > Rohc mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/rohc
>
> -------------------------------------------------------
>
> _______________________________________________
> Rohc mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/rohc
>

_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: "West, Mark (ITN)" <[email-masked]>
Date: Tue, 04 Jun 2002 00:11:41 +0100

I'm doubtless missing something blindingly obvious, but...

 > window [29000, 60000, 50000], assume v = 19000.

[I'll also point out that you aren't quoting a value for 'p' in this 
case, so we can't be sure what the interpretation interval is.  But I'll 
assume that p = 0, for now...]

The possible values of v_ref are 29000, 60000 and 50000.  With modular 
arithmetic, the difference between a v of 19000 and a v_ref of 29000 is 
55536, which (with p = 0) is going to lead to k being the full 16 bits, 
isn't it?

Cheers,

Mark.

-- 
Mark A. West, Consultant Engineer
Roke Manor Research Ltd., Romsey, Hants.  SO51 0ZN
Phone +44 (0)1794 833311   Fax  +44 (0)1794 833433

(Yes, I do know that my disclaimer is in an attachment.  And, no, I 
didn't ask for it to be that way)

---

From: Wang Hai Guang <[email-masked]>
Date: Tue, 4 Jun 2002 09:38:19 +0800 (SGT)

I assume p = 2^(k-2) - 1.

 Because the number may change randomly, so I didn't add the

65536 when wraparound happens. I think I should add it.

Thanks Mark for the comments.

Best regards.

Haiguang