Compression - Compress a subset of bits form

Author

Compress a subset of bits form

Ulf Reiman

2006-07-03, 3:55 am

Hi!
What is the best algorithm to compress the information, where a want to
point out a subset of 16 bits from 128 bits. a give one example where a
only use a subset of only 4 bits from the 128, we say we have a packet
of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how
can a describe these places with a less bits as possibly? a do not want
to use 7 * 4 bits

/Ulf

Willem

2006-07-03, 3:55 am

Ulf wrote:
) Hi!
) What is the best algorithm to compress the information, where a want to
) point out a subset of 16 bits from 128 bits. a give one example where a
) only use a subset of only 4 bits from the 128, we say we have a packet
) of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how
) can a describe these places with a less bits as possibly? a do not want
) to use 7 * 4 bits

Using combinatorics, find out that there are N possible ways to point out
such a subset. Also using combinatorics, find an ordering of those subsets
(an ordering is a 1-1 mapping from the natural numbers to those subsets)
Encode the natural number a certain subset maps to in log2(N) bits.

This is assuming 'best' means 'highest compression'.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Jani Huhtanen

2006-07-03, 3:55 am

Willem wrote:

> Ulf wrote:
> ) Hi!
> ) What is the best algorithm to compress the information, where a want to
> ) point out a subset of 16 bits from 128 bits. a give one example where a
> ) only use a subset of only 4 bits from the 128, we say we have a packet
> ) of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how
> ) can a describe these places with a less bits as possibly? a do not want
> ) to use 7 * 4 bits
>
> Using combinatorics, find out that there are N possible ways to point out
> such a subset. Also using combinatorics, find an ordering of those
> subsets (an ordering is a 1-1 mapping from the natural numbers to those
> subsets) Encode the natural number a certain subset maps to in log2(N)
> bits.
>
> This is assuming 'best' means 'highest compression'.
>
>
> SaSW, Willem

If I did not do any mistakes combinatorics can express the subsets as
follows:

4 bit subset -> ~23.34 bits/subset
(compare to 7*4 = 28 bits/subset)

16 bit subset -> ~66.33 bits/subset
(compare to 7*16 = 112 bits/subset)

Thus advantage of using plain combinatorics grows when the size of the
subset grows. One can gain even more by taking advantage of the
probabilities of different subsets.

Another possibility is to use an arithmetic coder. Use 128 bit word to mark
the subset, where 1 denotes that the corresponding bit belongs to the set
and 0 denotes that the corresponding bit does not belong to the set. A
simple 0th order coder should easily achieve ~70 bits/subset for 16 bit
subset (probability of a 1 bit is 1/8).

Higher order models are easy to employ in this case. A simple one would just
count the number of 1 bits encountered and update the model such that the
probability of 1 is

p = (S-c)/T,

where S is the size of the subset (e.g., 16) and T is the total number of
bits (e.g. 128) and c is the number of encountered 1 bits.

--
Jani Huhtanen
Tampere University of Technology, Pori

Ulf Reiman

2006-07-03, 7:55 am

There is (128! / (128 - 16)! 16!), diffrent ways to find a subset
of 16 bits from 128, so you mean give evey subset a number, but do you
mean by "Encode the natural number a certain subset maps to in log2(N)
bits"
/Ulf

Willem skrev:

> Ulf wrote:
> ) Hi!
> ) What is the best algorithm to compress the information, where a want to
> ) point out a subset of 16 bits from 128 bits. a give one example where a
> ) only use a subset of only 4 bits from the 128, we say we have a packet
> ) of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how
> ) can a describe these places with a less bits as possibly? a do not want
> ) to use 7 * 4 bits
>
> Using combinatorics, find out that there are N possible ways to point out
> such a subset. Also using combinatorics, find an ordering of those subsets
> (an ordering is a 1-1 mapping from the natural numbers to those subsets)
> Encode the natural number a certain subset maps to in log2(N) bits.
>
> This is assuming 'best' means 'highest compression'.
>
>
> SaSW, Willem
> --
> Disclaimer: I am in no way responsible for any of the statements
> made in the above text. For all I know I might be
> drugged or something..
> No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT

Ulf Reiman

2006-07-03, 7:55 am

Hi!

Where can I find more info about this, what do you will be most
suitably to describe 16 of 128 bits, there can be any of the subset. So
there is uniformly distribution, so all outcomes are equal. How did you
get your numbers below?

/Ulf
Jani Huhtanen skrev:

> Willem wrote:
>
>
> If I did not do any mistakes combinatorics can express the subsets as
> follows:
>
> 4 bit subset -> ~23.34 bits/subset
> (compare to 7*4 = 28 bits/subset)
>
> 16 bit subset -> ~66.33 bits/subset
> (compare to 7*16 = 112 bits/subset)
>
> Thus advantage of using plain combinatorics grows when the size of the
> subset grows. One can gain even more by taking advantage of the
> probabilities of different subsets.
>
> Another possibility is to use an arithmetic coder. Use 128 bit word to mark
> the subset, where 1 denotes that the corresponding bit belongs to the set
> and 0 denotes that the corresponding bit does not belong to the set. A
> simple 0th order coder should easily achieve ~70 bits/subset for 16 bit
> subset (probability of a 1 bit is 1/8).
>
> Higher order models are easy to employ in this case. A simple one would just
> count the number of 1 bits encountered and update the model such that the
> probability of 1 is
>
> p = (S-c)/T,
>
> where S is the size of the subset (e.g., 16) and T is the total number of
> bits (e.g. 128) and c is the number of encountered 1 bits.
>
> --
> Jani Huhtanen
> Tampere University of Technology, Pori

Ulf Reiman

2006-07-03, 7:55 am

Jani Huhtanen

2006-07-03, 6:55 pm

Ulf Reiman wrote:

> Hi!
>
> Where can I find more info about this

Google entropy coding, arithmetic coding, run-length coding, etc..

> , what do you will be most
> suitably to describe 16 of 128 bits, there can be any of the subset. So
> there is uniformly distribution, so all outcomes are equal.

I cannot comment about combinatorics, but I know that the arithmetic coding
(or similar approach) is moderately easy to setup. What are the
requirements for speed, memory usage, compression ratio, etc?

> How did you
> get your numbers below?
>

See below.
[color=darkred]
> /Ulf
> Jani Huhtanen skrev:
>

log2(binomial(128,4)) = log2(10668000) =~ 23.34
[color=darkred]

log2(binomial(128,16)) =~ 66.33

[color=darkred]

In 128 bit word with 16 one bits, the probability of a 1 bit is 16/128 =
1/8. Thus the probability of the 0 bit is 7/8. Scalar (or 0th order)
entropy of the word is

H = -1/8*log2(1/8) -7/8*log2(7/8) = ~0.544 bits.

That is, coding every bit in the word requires ~0.544 bits. Thus in order to
code 128 bits one has to use

128*H =~ 69.576 bits in total.

IIRC, arithmetic coder can achieve up to one bit this limit posed by
entropy. Thus one could code the word with 71 bits using 0th order
arithmetic coder (not 70 as I stated in my previous post). Conditional
entropy is less than scalar entropy, in general, and especially in this
case. That is, one knows always the exact number of one bits in the word
while coding and this can be easily taken advantage of:
[color=darkred]

--
Jani Huhtanen
Tampere University of Technology, Pori

nightlight

2006-07-03, 9:55 pm

Ulf Reiman wrote:
> Hi!
>
> Where can I find more info about this, what do you will be most
> suitably to describe 16 of 128 bits, there can be any of the subset. So
> there is uniformly distribution, so all outcomes are equal. How did you
> get your numbers below?
>

Below is link to a site with plenty information (online papers) and
usable code on this very method (known as enumertaive coding):

http://www.1stworks.com/ref/qi.htm

The page is about recently invented practical form of this type of
coding (named Quantized Indexing), which doesn't require unlimited
precision to code strings of any length. With conventional enumerative
coding you need arithmetic precision of the size of output, while the
new algorithm, QI, needs only a register size add per input symbol.
It is simultaneously much faster than arithmetic coding and it produces
smaller output (it produces mathematically the smallest output possible
for any given limit on arithmetic precision per input symbol). The
modeling for the new method is quite different than probabilistic
modeling for arithmetic coder. This area is still being developed (few
bits on the new modeling are described in the report TR05-0625, at:
http://www.1stworks.com/ref/TR/tr05-0625a.pdf ).

There are also couple earlier threads in this group discussing the
new method:

http://groups.google.com/group/comp...fc7f7ca84c76378
http://groups.google.com/group/comp...053c23c0d01c81c

Ulf Reiman

2006-07-04, 3:55 am

I will use it in micro controllers with 128k memory, in sensor boards,
so the algorithm cannot be complex. The thing a want to do, I start
with 128 bits, a take out 16 bits from this 128. Now, a need to provide
a description of where these 16 bits is in the 128 bits I had from the
beginning. In addition, do that with as less bits as possibly. If I use
run -length coding, I will use approximately 68 bits in on average.

> Ulf Reiman wrote:
>
>
> Google entropy coding, arithmetic coding, run-length coding, etc..
>
>
> I cannot comment about combinatorics, but I know that the arithmetic coding
> (or similar approach) is moderately easy to setup. What are the
> requirements for speed, memory usage, compression ratio, etc?
>
>
> See below.
>
>
> log2(binomial(128,4)) = log2(10668000) =~ 23.34
>
>
> log2(binomial(128,16)) =~ 66.33
>
>
>
> In 128 bit word with 16 one bits, the probability of a 1 bit is 16/128 =
> 1/8. Thus the probability of the 0 bit is 7/8. Scalar (or 0th order)
> entropy of the word is
>
> H = -1/8*log2(1/8) -7/8*log2(7/8) = ~0.544 bits.
>
> That is, coding every bit in the word requires ~0.544 bits. Thus in order to
> code 128 bits one has to use
>
> 128*H =~ 69.576 bits in total.
>
> IIRC, arithmetic coder can achieve up to one bit this limit posed by
> entropy. Thus one could code the word with 71 bits using 0th order
> arithmetic coder (not 70 as I stated in my previous post). Conditional
> entropy is less than scalar entropy, in general, and especially in this
> case. That is, one knows always the exact number of one bits in the word
> while coding and this can be easily taken advantage of:
>
>
> --
> Jani Huhtanen
> Tampere University of Technology, Pori

Jani Huhtanen

2006-07-04, 3:55 am

Ulf Reiman wrote:

> I will use it in micro controllers with 128k memory, in sensor boards,
> so the algorithm cannot be complex. The thing a want to do, I start
> with 128 bits, a take out 16 bits from this 128. Now, a need to provide
> a description of where these 16 bits is in the 128 bits I had from the
> beginning. In addition, do that with as less bits as possibly. If I use
> run -length coding, I will use approximately 68 bits in on average.
>

I'd say that 68 bits per subset is pretty good. Go with the run-length
coding scheme. Arithmetic coding would probably be too time consuming on
micro controller.

btw. How do you code your run-lengths? Using Golomb-codes?
[color=darkred]

--
----
Jani Huhtanen
Tampere University of Technology, Pori

Ulf Reiman

2006-07-04, 7:55 am

How can i use this enumerative coding to describe which 16 bits from
this 128 i use?
/Ulf

nightlight skrev:

> Ulf Reiman wrote:
>
> Below is link to a site with plenty information (online papers) and
> usable code on this very method (known as enumertaive coding):
>
> http://www.1stworks.com/ref/qi.htm
>
> The page is about recently invented practical form of this type of
> coding (named Quantized Indexing), which doesn't require unlimited
> precision to code strings of any length. With conventional enumerative
> coding you need arithmetic precision of the size of output, while the
> new algorithm, QI, needs only a register size add per input symbol.
> It is simultaneously much faster than arithmetic coding and it produces
> smaller output (it produces mathematically the smallest output possible
> for any given limit on arithmetic precision per input symbol). The
> modeling for the new method is quite different than probabilistic
> modeling for arithmetic coder. This area is still being developed (few
> bits on the new modeling are described in the report TR05-0625, at:
> http://www.1stworks.com/ref/TR/tr05-0625a.pdf ).
>
> There are also couple earlier threads in this group discussing the
> new method:
>
> http://groups.google.com/group/comp...fc7f7ca84c76378
> http://groups.google.com/group/comp...053c23c0d01c81c

Ulf Reiman

2006-07-04, 7:55 am

How can i use this enumerative coding, to describe which 16 bits from
these 128 bits i use? A want to say,a use for example: bit 1, 7, 26,
45... But, in an efficient way?
/Ulf

nightlight skrev:

> Ulf Reiman wrote:
>
> Below is link to a site with plenty information (online papers) and
> usable code on this very method (known as enumertaive coding):
>
> http://www.1stworks.com/ref/qi.htm
>
> The page is about recently invented practical form of this type of
> coding (named Quantized Indexing), which doesn't require unlimited
> precision to code strings of any length. With conventional enumerative
> coding you need arithmetic precision of the size of output, while the
> new algorithm, QI, needs only a register size add per input symbol.
> It is simultaneously much faster than arithmetic coding and it produces
> smaller output (it produces mathematically the smallest output possible
> for any given limit on arithmetic precision per input symbol). The
> modeling for the new method is quite different than probabilistic
> modeling for arithmetic coder. This area is still being developed (few
> bits on the new modeling are described in the report TR05-0625, at:
> http://www.1stworks.com/ref/TR/tr05-0625a.pdf ).
>
> There are also couple earlier threads in this group discussing the
> new method:
>
> http://groups.google.com/group/comp...fc7f7ca84c76378
> http://groups.google.com/group/comp...053c23c0d01c81c

Ulf Reiman

2006-07-04, 7:55 am

nightlight skrev:

> Ulf Reiman wrote:
>
> Below is link to a site with plenty information (online papers) and
> usable code on this very method (known as enumertaive coding):
>
> http://www.1stworks.com/ref/qi.htm
>
> The page is about recently invented practical form of this type of
> coding (named Quantized Indexing), which doesn't require unlimited
> precision to code strings of any length. With conventional enumerative
> coding you need arithmetic precision of the size of output, while the
> new algorithm, QI, needs only a register size add per input symbol.
> It is simultaneously much faster than arithmetic coding and it produces
> smaller output (it produces mathematically the smallest output possible
> for any given limit on arithmetic precision per input symbol). The
> modeling for the new method is quite different than probabilistic
> modeling for arithmetic coder. This area is still being developed (few
> bits on the new modeling are described in the report TR05-0625, at:
> http://www.1stworks.com/ref/TR/tr05-0625a.pdf ).
>
> There are also couple earlier threads in this group discussing the
> new method:
>
> http://groups.google.com/group/comp...fc7f7ca84c76378
> http://groups.google.com/group/comp...053c23c0d01c81c

Ulf Reiman

2006-07-04, 7:55 am

How can i use this enumerative coding, to describe which 16 bits from
these 128 bits i use? A want to say bit 1, 7, 26, 45... However, in an
efficient way?

/Ulf

nightlight skrev:

> Ulf Reiman wrote:
>
> Below is link to a site with plenty information (online papers) and
> usable code on this very method (known as enumertaive coding):
>
> http://www.1stworks.com/ref/qi.htm
>
> The page is about recently invented practical form of this type of
> coding (named Quantized Indexing), which doesn't require unlimited
> precision to code strings of any length. With conventional enumerative
> coding you need arithmetic precision of the size of output, while the
> new algorithm, QI, needs only a register size add per input symbol.
> It is simultaneously much faster than arithmetic coding and it produces
> smaller output (it produces mathematically the smallest output possible
> for any given limit on arithmetic precision per input symbol). The
> modeling for the new method is quite different than probabilistic
> modeling for arithmetic coder. This area is still being developed (few
> bits on the new modeling are described in the report TR05-0625, at:
> http://www.1stworks.com/ref/TR/tr05-0625a.pdf ).
>
> There are also couple earlier threads in this group discussing the
> new method:
>
> http://groups.google.com/group/comp...fc7f7ca84c76378
> http://groups.google.com/group/comp...053c23c0d01c81c

David A. Scott

2006-07-04, 7:55 am

"Ulf Reiman" <ulf.reiman@gmail.com> wrote in
news:1152016569.451570.122770@p79g2000cwp.googlegroups.com:

>
> How can i use this enumerative coding, to describe which 16 bits from
> these 128 bits i use? A want to say,a use for example: bit 1, 7, 26,
> 45... But, in an efficient way?
> /Ulf
>
>

There might be a danger in using this enumerative code first of all I
think it had a patent pending. Second people here did some tests it
was not all that fast and really for what lttle you describe an
arithmetic coder would be simpler and the compressed size would be
as small as possible. You really don't need high precision to take
full advantage of the problem you partial describe here. Is the data
embedded in a stream where you have different data or stand alone
In either case its hard to beat an arithmetic for speed or size in
this case.

David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

David A. Scott

2006-07-04, 6:01 pm

"Ulf Reiman" <ulf.reiman@gmail.com> wrote in
news:1151910348.822701.58810@j8g2000cwa.googlegroups.com:

> Hi!
> What is the best algorithm to compress the information, where a want to
> point out a subset of 16 bits from 128 bits. a give one example where a
> only use a subset of only 4 bits from the 128, we say we have a packet
> of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how
> can a describe these places with a less bits as possibly? a do not want
> to use 7 * 4 bits
>
> /Ulf
>
>

I can see a long thread that may not get any where. But here is
a question for you. Is this information stand alone or what. Example
say you want to 2 bits from 5. Then what you may really want is
to express one of 5!/(2!3!) states that is one of 10 states.
Which would be an exceptable way to you:

Blank for one state
0 or 1 for next two states
00 to 11 for next four states
then your choice of any two 3 bit patterns for last 3 states.
This would gave you the least number of bits possible assuming
you want whole numbers of bits and is stand alone.

Next option would be let
000 to 101 be first six states
and 1100 and 1101 be next two states
and 1110 and 1111 by last two states.
This is best option for whole number embedded
as part of stream. Could easily be done
with huffman or arithmetic coding methods.

Third option if part of a stream use pure arithmetic
where you use roughly 3.22
bits of space in some stream of data In this one
alone can you use fractional bits since the state
of carry and high low registers contain the state
information needed to encode what ever other data
follows.

Any of the above could be done with a low precision arithmetic
quite well. And even here we are assumeing that its a
fixed number of bits from a fixed size. If this is varible
and can change you may have to store this fact with the method
you choose to use in the data itself.

Hope this helps with you homework!

David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

nightlight

2006-07-04, 6:01 pm

David A. Scott wrote:

> There might be a danger in using this enumerative code first
> of all I think it had a patent pending.

Most of the code there, including the exact enumerative coding,
has no patents or patents pending. The parts of the QI algorithm
that represent a significant algorithmic innovation do have a patent
pending, as the brief license included with the source code already
warns about in its third sentence.

Even worse than being superfluous, in the context of the
present-day software patents, where everything from the single
click ordering, xor operator in basic, menus to select choices
and up, including even the most trivial improvements or variants
in compression algorithms, is blanketed in patents, your most
prominent and somber warning about the potential patent "danger"
with QI is about as pertinent as setting yourself up in front of
a five star restaurant, waving a gigantic carboard sign with
a large a skull and crossbones in the center and a grand expose
underneath, all in caps and generously plasterd with exclamation
points, warning visitors to better watch out, since you have
discovered that there may be fat in the main meals and sugar
in the pastries being served there.

In any case, for his 128 bit strings, though, the exact EC is
perfectly fine. There are also numerous papers, theses, books,
including some pretty hard to find papers (even as a hard copy
at most university libraries), which provide all the information
he was asking for, well beyond the vague handwaving he got
prior to the link.

Further, you seem to have entirely forgotten his question being
replied to (which, oddly, you quoted as well, then continued as
if an entirely different question was discussed):

If you know of any site on the rest of the web which has more or
or higher quality info on _that_ question than the site I pointed
him to, you are welcome to provide a link to it.
[color=darkred]
> Second people here did some tests it was not all that fast...

Perhaps you forgot, but what "was not all that fast" in that test
was a bit by bit converter of his MQ model, added as a front end
to the entropy coding. The entropy coder fraction of the execution
time was so negligible in that whole task (which was heavily disk
bound), you could take QI entirely out and not change any of
those speed test results. The thread where that test (mainly of
his MQ model converter and the file i/o timing fluctuations, hence
irrelevant for the question being asked here) was reported is at:

http://groups.google.com/group/comp...d84e1a8334b5fbe

> You really don't need high precision to take full advantage of the
> problem you partial describe here. Is the data embedded in a stream
> where you have different data or stand alone. In either case its hard
> to beat an arithmetic for speed or size in this case.

Whether arithmetic coding is hard to beat here, depends on
what improvement factors you had in mind. If he only needs
to beat arithmetic coding by factors from six to few hundred
in speed, and up to a factor two in output size, then QI will
do fine. If he needs more than that, I am afraid, he may be
out of luck for now. If he is not in any particular hurry, though,
I am sure there will be another advance comparable to the one
from arithmetic coding to QI in the next two to three decades.

QI vs AC test results: http://www.1stworks.com/ref/TR/DCC2006.pdf
QI source code (with high resolution timers for speed measurements):
http://www.1stworks.com/ref/qi.htm

guenther vonKnakspott

2006-07-07, 7:55 am

Ulf Reiman wrote:
> Hi!
> What is the best algorithm to compress the information, where a want to
> point out a subset of 16 bits from 128 bits. a give one example where a
> only use a subset of only 4 bits from the 128, we say we have a packet
> of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how
> can a describe these places with a less bits as possibly? a do not want
> to use 7 * 4 bits
>
> /Ulf

Hi, what you need is Enumerative Source Encoding
http://yreka.stanford.edu/~cover/pa...IT/0073cove.pdf
In my opinion it meets your requirements optimally.

Regards.

nightlight

2006-07-07, 6:55 pm

guenther vonKnakspott wrote:
>
> Hi, what you need is Enumerative Source Encoding
> http://yreka.stanford.edu/~cover/pa...IT/0073cove.pdf
> In my opinion it meets your requirements optimally.
>

Cover's variant of exact Enumerative Coding (EC) isn't the most
practical among the existent variants. It's ok if the question was from
a homework. If he needs to implement it as a part of a real life
programming project, though, much more practical variants were
developed since Cover's 1973 paper. For example, see references
[11]-[16], [23], [26], [35], [36], [46], [47], [60]-[62], [T1]-[T4]
about several more recent EC variants at the link:

--- QI Reference Library:
http://www.1stworks.com/ref/RefLib.htm

guenther vonKnakspott

2006-07-07, 6:55 pm

nightlight wrote:
> guenther vonKnakspott wrote:
>
> Cover's variant of exact Enumerative Coding (EC) isn't the most
> practical among the existent variants. It's ok if the question was from
> a homework. If he needs to implement it as a part of a real life
> programming project, though, much more practical variants were
> developed since Cover's 1973 paper. For example, see references
> [11]-[16], [23], [26], [35], [36], [46], [47], [60]-[62], [T1]-[T4]
> about several more recent EC variants at the link:
>
> --- QI Reference Library:
> http://www.1stworks.com/ref/RefLib.htm
Thank you for the pointers I will look at them.
Regards.

John McCarten

2006-07-08, 3:55 am

Ulf Reiman wrote:
> What is the best algorithm to compress the information, where a want to
> point out a subset of 16 bits from 128 bits. a give one example where a
> only use a subset of only 4 bits from the 128, we say we have a packet
> of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how
> can a describe these places with a less bits as possibly? a do not want
> to use 7 * 4 bits

Arithmetic encoding lends itself very well to encoding permutations,
which is what this is.

Any 16 from 128 can be encoded in a constant 67 bits (66.34) using
simple reductive arithmetic. E.g.

** encoder **
A = 16
B = 128
for i = 1 to 112
if i = ValueToEncode then
Encode(A, B)
if Dec(A) = 0 then
done
else
Encode(B-A, B)
Dec(B)

To decode reverse the above.

I could be wrong, and often am, so I'm happy to stand corrected :), but
I don't think that one could do all possible 16:128 permutations in
less than this.

john.

John McCarten

2006-07-08, 3:55 am

John McCarten wrote in part:

> for i = 1 to 112

This is not strictly correct, but I'll get in right in a while :)

john.

davvid_a_scott@email.com

2006-07-08, 6:55 pm

John McCarten wrote:
> Ulf Reiman wrote:
>
> Arithmetic encoding lends itself very well to encoding permutations,
> which is what this is.

Yes it lends itself very well to exactly this kind of promblem. But
I have faith that nightlight could develope has own version of
arithmetic
that could even make even this easy task look hard for an arithmetic.
I have yet to see real world tests unless you count his especially
modifed moffat that makes QI or its ilk look good.

>
> Any 16 from 128 can be encoded in a constant 67 bits (66.34) using
> simple reductive arithmetic. E.g.
>
> ** encoder **
> A = 16
> B = 128
> for i = 1 to 112
> if i = ValueToEncode then
> Encode(A, B)
> if Dec(A) = 0 then
> done
> else
> Encode(B-A, B)
> Dec(B)
>
> To decode reverse the above.
>
> I could be wrong, and often am, so I'm happy to stand corrected :), but
> I don't think that one could do all possible 16:128 permutations in
> less than this.
>
> john.

You have the basic idea I don't think that nightlight has a clue to
how easy this is with a simple arithmetic. Maybe we can again have a
contest and let the original poster see which is easiest. That is if we
can get the original poster to exactly nail down what he wants.

David Scott

P.S. My machine down so it we be awhile before I get any
more done

John McCarten

2006-07-09, 9:55 pm

davvid_a_scott@email.com wrote in part:
> ...
> I don't think that nightlight has a clue to
> how easy this is with a simple arithmetic.
> ...

I would give nightlight the benefit of doubt. I think he does. Its just
that when one puts a lot of effort into a single idea, a tendency to
mono-track sometimes occurs.

FWIW I think the most intriguing thing to come out of nightlight's work
is the SWI. I can see this forming the basis of a really bignum engine.
The ability to slide values through a window manipulating them in the
process, while also being able to easily track what comes in and what
goes out, suggests that problems like really long division, factorial
and combinatoric calculation, along with a number of other problems
involving really big numbers, would be more manageable with this. The
upper limit on the values being manipulated, restricted only by the
amount of storage space available.

The seed of this engine is already in the code publicly made available
thus far. Should nightlight explore this further and just such an
engine eventuate I believe there would be some considerable academic
and commercial interest.

john.

Phil Carmody

2006-07-10, 3:55 am

"John McCarten" <john.mccarten@hotmail.com> writes:
> davvid_a_scott@email.com wrote in part:
>
> I would give nightlight the benefit of doubt. I think he does. Its just
> that when one puts a lot of effort into a single idea, a tendency to
> mono-track sometimes occurs.
>
> FWIW I think the most intriguing thing to come out of nightlight's work
> is the SWI. I can see this forming the basis of a really bignum engine.
> The ability to slide values through a window manipulating them in the
> process, while also being able to easily track what comes in and what
> goes out, suggests that problems like really long division, factorial
> and combinatoric calculation, along with a number of other problems
> involving really big numbers, would be more manageable with this. The
> upper limit on the values being manipulated, restricted only by the
> amount of storage space available.
>
> The seed of this engine is already in the code publicly made available
> thus far. Should nightlight explore this further and just such an
> engine eventuate I believe there would be some considerable academic
> and commercial interest.

As someone who has coded vast globs of fast bignum arithmetic code,
I see absolutely no use at all in nightlight's code in that context.

I don't doubt it has some use in some context, but not bignum
arithmetic.

Phil
--
The man who is always worrying about whether or not his soul would be
damned generally has a soul that isn't worth a damn.
-- Oliver Wendell Holmes, Sr. (1809-1894), American physician and writer

Ulf Reiman

2006-07-11, 7:55 am

start from a datapacket of 128 bits, but use only 16 bits from this
128, there can be any 16 bits from the 128. how to describe which 16
bits you have taken from this 128, with as less bits as possibly. it
shall be used on a microcontroller, so speed memory is very low.

davvid_a_scott@email.com skrev:

> John McCarten wrote:
>
> Yes it lends itself very well to exactly this kind of promblem. But
> I have faith that nightlight could develope has own version of
> arithmetic
> that could even make even this easy task look hard for an arithmetic.
> I have yet to see real world tests unless you count his especially
> modifed moffat that makes QI or its ilk look good.
>
>
> You have the basic idea I don't think that nightlight has a clue to
> how easy this is with a simple arithmetic. Maybe we can again have a
> contest and let the original poster see which is easiest. That is if we
> can get the original poster to exactly nail down what he wants.
>
> David Scott
>
> P.S. My machine down so it we be awhile before I get any
> more done

guenther vonKnakspott

2006-07-12, 7:55 am

Ulf Reiman wrote:
> start from a datapacket of 128 bits, but use only 16 bits from this
> 128, there can be any 16 bits from the 128. how to describe which 16
> bits you have taken from this 128, with as less bits as possibly. it
> shall be used on a microcontroller, so speed memory is very low.
>
Hi, please don't top post. Did you take a look at
http://yreka.stanford.edu/~cover/pa...IT/0073cove.pdf
?
It contains all the theory that you need solve your problem optimally.
I mean optimally in terms of compression. No other method will compress
better. Wether that paper leads to an implementation suitable to your
needs is another matter, which you can probably judge best. Apparently
nightlight has given some references to more efficient implementations
but I have not had the time to check them out, perhaps you should.

Sponsored Links