Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2507 > unrolled thread

Need Uniquely Decodable Codes with special properties

Back to article view | Back to comp.compression

Contents

  Need Uniquely Decodable Codes with special properties Fibonacci Code <anglikai@gmail.com> - 2014-08-05 06:00 -0700
    Re: Need Uniquely Decodable Codes with special properties jdallen2000@yahoo.com - 2014-08-05 08:19 -0700
      Re: Need Uniquely Decodable Codes with special properties Fibonacci Code <anglikai@gmail.com> - 2014-08-06 07:33 -0700
        Re: Need Uniquely Decodable Codes with special properties glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-08-06 17:28 +0000
          Re: Need Uniquely Decodable Codes with special properties Fibonacci Code <anglikai@gmail.com> - 2014-08-08 18:10 -0700
            Re: Need Uniquely Decodable Codes with special properties glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-08-09 02:04 +0000
    Re: Need Uniquely Decodable Codes with special properties Thomas Richter <thor@math.tu-berlin.de> - 2014-08-06 18:53 +0200
    Re: Need Uniquely Decodable Codes with special properties Fibonacci Code <anglikai@gmail.com> - 2014-08-08 20:08 -0700
      Re: Need Uniquely Decodable Codes with special properties glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-08-09 03:31 +0000
        Re: Need Uniquely Decodable Codes with special properties Fibonacci Code <anglikai@gmail.com> - 2014-08-10 02:59 -0700
    Re: Need Uniquely Decodable Codes with special properties Ernst <ernst_berg@sbcglobal.net> - 2014-08-13 19:36 -0700

#2507 — Need Uniquely Decodable Codes with special properties

I need Uniquely Decodable Codes for N bits where first bit will always 1 For example.
   
   Codes    N
----------------
   10       1
   110      2
   1110     3
   11110    4
   111110   5

Is there any other Uniquely Decodable Codes that have such properties for a group of N but doesn't expand 1 bit like the codes above ?


Regards,

Fibonacci.

[toc] | [next] | [standalone]

#2509

On Tuesday, August 5, 2014 8:00:39 PM UTC+7, Fibonacci Code wrote:
> I need Uniquely Decodable Codes for N bits where first bit will always 1

> 
> Is there any other Uniquely Decodable Codes that have such properties for a group of N but doesn't expand 1 bit like the codes above ?

The class of codes you seek is simply
Uniquely Decodable Codes with a '1' prepended.
Golomb (Rice) codes are in common use, as
is another such code I'm sure you're
familiar with.  :-)

Without the requested '1' prepended:
11 - 1
011 - 2
0011 - 3
1011 - 4
00011 - 5
10011 - 6
01011 - 7
000011 - 8
100011 - 9
010011 - 10
001011 - 11
101011 - 12
0000011 - 13

James Dow Allen

[toc] | [prev] | [next] | [standalone]

#2510

On Tuesday, 5 August 2014 23:19:38 UTC+8, jdall...@yahoo.com  wrote:
> On Tuesday, August 5, 2014 8:00:39 PM UTC+7, Fibonacci Code wrote:
> 
> > I need Uniquely Decodable Codes for N bits where first bit will always 1
> 
> 
> 
> > 
> 
> > Is there any other Uniquely Decodable Codes that have such properties for a group of N but doesn't expand 1 bit like the codes above ?
> 
> 
> 
> The class of codes you seek is simply
> 
> Uniquely Decodable Codes with a '1' prepended.
> 
> Golomb (Rice) codes are in common use, as
> 
> is another such code I'm sure you're
> 
> familiar with.  :-)
> 
> 
> 
> Without the requested '1' prepended:
> 
> 11 - 1
> 
> 011 - 2
> 
> 0011 - 3
> 
> 1011 - 4
> 
> 00011 - 5
> 
> 10011 - 6
> 
> 01011 - 7
> 
> 000011 - 8
> 
> 100011 - 9
> 
> 010011 - 10
> 
> 001011 - 11
> 
> 101011 - 12
> 
> 0000011 - 13
> 
> 
> 
> James Dow Allen

Hi James, 

        Thanks a lot for the sequence. But I need the sequence to support

encoding for a group of number of N. Where N>=1.

Still puzzling over this myself.


Regards,
Fibonacci

[toc] | [prev] | [next] | [standalone]

#2512

Fibonacci Code <anglikai@gmail.com> wrote:
> On Tuesday, 5 August 2014 23:19:38 UTC+8, jdall...@yahoo.com  wrote:
>> On Tuesday, August 5, 2014 8:00:39 PM UTC+7, Fibonacci Code wrote:
 
>> > I need Uniquely Decodable Codes for N bits where first bit will always 1
 
>> > Is there any other Uniquely Decodable Codes that have such 
>> > properties for a group of N but doesn't expand 1 bit like 
>> > the codes above ?

(snip)

>  Thanks a lot for the sequence. But I need the sequence to support
>  encoding for a group of number of N. Where N>=1.

Do you know the distribution (probability) for each value?

As I understand it, I believe from Knuth, the optimal code for
an arbitrary (unlimited) sized positive integer that has an
N bit binary representation is (N-1) zeros, followed by the binary
representation without leading zeros.  That will start with a
zero for every value except one. 

If you need to represent non-negative integers, add one and then
use the above representation. 

For signed integers, put the sign first, then the non-negative
representation.

So, for an optimal representation starting with one, for integers
between M and infinity, subtract (M-2) which gives you a N bit binary
integer between 2 and infinity, so with at least two bits. 
Write out N-1 ones, followed by the ones complement of (M-2), 
without any leading ones.

-- glen

[toc] | [prev] | [next] | [standalone]

#2516

On Thursday, 7 August 2014 01:28:47 UTC+8, glen herrmannsfeldt  wrote:
> Fibonacci Code <anglikai@gmail.com> wrote:
> 
> > On Tuesday, 5 August 2014 23:19:38 UTC+8, jdall...@yahoo.com  wrote:
> 
> >> On Tuesday, August 5, 2014 8:00:39 PM UTC+7, Fibonacci Code wrote:
> 
>  
> 
> >> > I need Uniquely Decodable Codes for N bits where first bit will always 1
> 
>  
> 
> >> > Is there any other Uniquely Decodable Codes that have such 
> 
> >> > properties for a group of N but doesn't expand 1 bit like 
> 
> >> > the codes above ?
> 
> 
> 
> (snip)
> 
> 
> 
> >  Thanks a lot for the sequence. But I need the sequence to support
> 
> >  encoding for a group of number of N. Where N>=1.
> 
> 
> 
> Do you know the distribution (probability) for each value?
> 
> 
> 
> As I understand it, I believe from Knuth, the optimal code for
> 
> an arbitrary (unlimited) sized positive integer that has an
> 
> N bit binary representation is (N-1) zeros, followed by the binary
> 
> representation without leading zeros.  That will start with a
> 
> zero for every value except one. 
> 
> 
> 
> If you need to represent non-negative integers, add one and then
> 
> use the above representation. 
> 
> 
> 
> For signed integers, put the sign first, then the non-negative
> 
> representation.
> 
> 
> 
> So, for an optimal representation starting with one, for integers
> 
> between M and infinity, subtract (M-2) which gives you a N bit binary
> 
> integer between 2 and infinity, so with at least two bits. 
> 
> Write out N-1 ones, followed by the ones complement of (M-2), 
> 
> without any leading ones.
> 
> 
> 
> -- glen

Hi Glen,

          Many thanks, for your code, does it mean a sequence like this ?

            1
           01x
          001xx
         0001xxx 

Where x = bits either 0 or 1 


Regards,
Raymond

[toc] | [prev] | [next] | [standalone]

#2517

Fibonacci Code <anglikai@gmail.com> wrote:
 
 (snip)
 
>> >  Thanks a lot for the sequence. But I need the sequence to support
>> >  encoding for a group of number of N. Where N>=1.

(snip)
>> As I understand it, I believe from Knuth, the optimal code for
>> an arbitrary (unlimited) sized positive integer that has an
>> N bit binary representation is (N-1) zeros, followed by the binary
>> representation without leading zeros.  That will start with a
>> zero for every value except one. 

(snip)

>     Many thanks, for your code, does it mean a sequence like this ?
 
>            1
>           01x
>          001xx
>         0001xxx 
 
> Where x = bits either 0 or 1 

Yes. Not knowing why you wanted it to start with 1, but if you
don't use the first entry and invert the bits of the rest, then
it will always start with one.

Note that, the length of the representation for value m is,
for large m, proportional to log(m), and that it can code
arbitrarily large values.

-- glen

[toc] | [prev] | [next] | [standalone]

#2511

Am 05.08.2014 15:00, schrieb Fibonacci Code:
> I need Uniquely Decodable Codes for N bits where first bit will always 1 For example.
>
>     Codes    N
> ----------------
>     10       1
>     110      2
>     1110     3
>     11110    4
>     111110   5
>
> Is there any other Uniquely Decodable Codes that have such properties for a group of N but doesn't expand 1 bit like the codes above ?

It's hard to understand what you want. If you have the requirement that 
the first bit is always one, then obviously the only choice you have for 
minimizing the output size is to minimize the average codeword size of 
all remaining bits. If you want a prefix code, the optimal code is 
Huffman. Thus, apparently, the code you need is 1 + Huffman code in that 
case.

Clearly, it *must* expand the size by one bit because you cannot use the 
constraint bit to carry any information - as you say, it is always one, 
so a receiver cannot use it to decode it to anything useful. Thus, this 
bit is always wasted, thus the code is always one bit longer. No way 
around it.

This is quite trivial, so probably you want something different from 
what you are asking for. Question is: What is it?

Greetings,

Thomas

[toc] | [prev] | [next] | [standalone]

#2518

On Tuesday, 5 August 2014 21:00:39 UTC+8, Fibonacci Code  wrote:
> I need Uniquely Decodable Codes for N bits where first bit will always 1 For example.
> 
>    
> 
>    Codes    N
> 
> ----------------
> 
>    10       1
> 
>    110      2
> 
>    1110     3
> 
>    11110    4
> 
>    111110   5
> 
> 
> 
> Is there any other Uniquely Decodable Codes that have such properties for a group of N but doesn't expand 1 bit like the codes above ?
> 
> 
> 
> 
> 
> Regards,
> 
> 
> 
> Fibonacci.

Hi Glen,

        I need it to be 1 but don't want the overhead. I hope there is a 
group of N length encoding method that could assorbed the lost of bit 1
prefix.

Regards,
Fibonacci

[toc] | [prev] | [next] | [standalone]

#2519

Fibonacci Code <anglikai@gmail.com> wrote:

(snip)

>> Is there any other Uniquely Decodable Codes that have such 
> properties for a group of N but doesn't expand 1 bit 
> like the codes above ?

(snip)

>        I need it to be 1 but don't want the overhead. I hope there is a 
> group of N length encoding method that could assorbed the lost of bit 1
> prefix.

You can't absorb the loss, but only move it around. 

It would help if you said why it needs to be a 1.

-- glen

[toc] | [prev] | [next] | [standalone]

#2520

Hi Glen,

     Is it possible to move the 1 to the front, and have such a way to

end the length ?

--Fibonacci

[toc] | [prev] | [next] | [standalone]

#2524

On Tuesday, August 5, 2014 6:00:39 AM UTC-7, Fibonacci Code wrote:
> I need Uniquely Decodable Codes for N bits where first bit will always 1 For example.
> 
>    
> 
>    Codes    N
> 
> ----------------
> 
>    10       1
> 
>    110      2
> 
>    1110     3
> 
>    11110    4
> 
>    111110   5
> 
> 
> 
> Is there any other Uniquely Decodable Codes that have such properties for a group of N but doesn't expand 1 bit like the codes above ?
> 
> 
> 
> 
> 
> Regards,
> 
> 
> 
> Fibonacci.

At the cost of one bit any string can be made into a code where the first or last bit is set depending on the positional notation used.
 Simply export the parity reference and code to a fixed terminus of 1 using dynamic unary.

Example 0000101010 is the code then exporting b0 parity of a reset bit > 0
Encoding then to a fixed terminus right to left standard western positional notation 100011111 + 0 so 1000111110
 
I covered this in the paper Introduction to Dynamic Unary Encoding

Ernst

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web