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

Groups > comp.compression > #2512

Re: Need Uniquely Decodable Codes with special properties

Show all headers | View raw

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

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web