Home > Archive > Compression > August 2005 > Re: Q: phase in code
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Re: Q: phase in code
|
|
| Steven Pigeon 2005-08-26, 6:55 pm |
| PSP wrote:
> Does anyone know what is phase in coding for encoding string lengths?
>
Phase-in code are not complicated. Let 0...N-1, the range of the
integer to code, and where N= 2^k+b. This decomposition is unique
provided that 0 < b < 2^k.
Let 0 <= x < N be the number to code.
Let B = 2^k-b.
If x < B
emit the code for x on k bits ( x mod 2^k, on k bits,
raw binary )
else
emit the code for B+Floor((x-B)/2) + code, on k bits,
plus one bit, (x-B) mod 2
;
for n=10, you'd get a code like
0 000
1 001
2 010
3 011
4 100
5 1010
6 1011
7 1100
8 1101
9 1110
10 1111
It can be shown (rather easily if not for ascii-art) that
the average length of the code, if the x are drawn uniformely
and iid, does not exceed log_2(N) by more than 0.0860713...
bits (a constant that keeps showing up in coding theory.)
Best,
S.
Steven Pigeon, Ph. D.
steven.pigeon@videotron.ca
| |
| Brian Raiter 2005-08-26, 6:55 pm |
| > for n=10, you'd get a code like
Actually, your example appears to illustrate N-1=10, or N=11.
(Otherwise, a clear explanation.)
b
| |
| Steven Pigeon 2005-08-26, 9:55 pm |
| Brian Raiter wrote:
>
>
> Actually, your example appears to illustrate N-1=10, or N=11.
> (Otherwise, a clear explanation.)
>
> b
Sure, you're absolutely right. Sorry for the typo.
Steven Pigeon, Ph. D.
steven.pigeon@videotron.ca
|
|
|
|
|