Home > Archive > Compression > November 2005 > What is the shortest bit sequence covering all 256 byte values?
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 |
What is the shortest bit sequence covering all 256 byte values?
|
|
| Claudio Grondi 2005-11-14, 6:55 pm |
| Let's imagine a bit sequence like e.g.
000000001000000011111111
Let's move a 8 bit wide 'window' from the left to the right over it. This
will give here following byte sequence:
00000000 h00
00000001 h01
00000010 h02
00000100 h04
and so on.
The requirement:
let's require, that the bit sequence should 'contain' all of the 256
possible byte values (where some or even all of the values can occure
multiple times).
The minimum length of such bit sequence not contradicting the obvious rule,
that it is not possible to store all 8 bit values using less than 8 bit is
256 + 7 = 263 bit, but it seems to me, that there is no 263 bit long bit
pattern which satisfies the requirement.
If there is no 263 bit long bit pattern which satisfies the requirement,
how long is/are the shortest bit sequence/s covering all 256 byte values
and what pattern does/do it/they have?
If someone asks himself what has this kind of question to do with
compression:
A sequence of 256 bytes requires 256 byte of storage space
A sequence of 263 bits requires 33 byte of storage space which gives 87%
compression ratio
I don't think, that this is something new, so if there is a compression
scheme which uses this kind of approach, how is it called?
Claudio
| |
| Willem 2005-11-14, 6:55 pm |
| Claudio wrote:
) ...
) The requirement:
) let's require, that the bit sequence should 'contain' all of the 256
) possible byte values (where some or even all of the values can occure
) multiple times).
) ...
) If someone asks himself what has this kind of question to do with
) compression:
) A sequence of 256 bytes requires 256 byte of storage space
) A sequence of 263 bits requires 33 byte of storage space which gives 87%
) compression ratio
)
) I don't think, that this is something new, so if there is a compression
) scheme which uses this kind of approach, how is it called?
There is no compression scheme that uses this kind of approach, because
you can't use it for compression. You could only store a sequence where
each byte happens to match the previous byte, shifted one place.
How do you envision compression using such a bit sequence ?
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
| |
| Claudio Grondi 2005-11-14, 6:55 pm |
| > How do you envision compression using such a bit sequence ?
This approach came to my mind while thinking about the very basics of what
compression is and what are the data patterns behind the electronic chips
used in a computer, so I have no idea how to use such approach in
compression which is useful in practice - the only thing I know about it is,
that it can be very effective on special data patterns. I can imagine, that
it can be used also in case the string does not fit into the scheme of
shifting bits, but this starts to be complicated, so considering that there
is no knowledge about the properties of real world data behind it from my
side, it is probably interesting only in its own special context.
By the way, are there any another comparable easy to understand, intuitive
and simple ways of generating larger strings from shorter ones as moving a
multiple bit 'window' over a bit sequence and as RLE?
Claudio
"Willem" <willem@stack.nl> schrieb im Newsbeitrag
news:slrndnh7nb.8vp.willem@toad.stack.nl...
> Claudio wrote:
> ) ...
> ) The requirement:
> ) let's require, that the bit sequence should 'contain' all of the 256
> ) possible byte values (where some or even all of the values can occure
> ) multiple times).
> ) ...
> ) If someone asks himself what has this kind of question to do with
> ) compression:
> ) A sequence of 256 bytes requires 256 byte of storage space
> ) A sequence of 263 bits requires 33 byte of storage space which gives
87%
> ) compression ratio
> )
> ) I don't think, that this is something new, so if there is a compression
> ) scheme which uses this kind of approach, how is it called?
>
> There is no compression scheme that uses this kind of approach, because
> you can't use it for compression. You could only store a sequence where
> each byte happens to match the previous byte, shifted one place.
>
> How do you envision compression using such a bit sequence ?
>
>
> 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
| |
| John_H 2005-11-14, 6:55 pm |
| One example is
1011000111101000011111111001000010100111
1101010101110000011000101011001100101111
1101111001101110111001010100101000100101
1010001100111001111000110110000100010111
0101111011011111000011010011010110110101
0000010011101100100100110000001110100100
011100010000000
0,1011000
where I included the comma to show where the first 7 bits of the sequence
are appended to the end.
The google phrase is "maximal length sequence" with the additional info that
the sequence for 8 bits would only give 255 unique values where the 8-bit
all-0 or all-1 sequence is missing. I just added an extra zero to the 7-bit
0 sequence to make it all 256.
Not that this information will help you.
"Claudio Grondi" <claudio.grondi@freenet.de> wrote in message
news:3trke5Fu42t0U1@individual.net...
> Let's imagine a bit sequence like e.g.
>
> 000000001000000011111111
>
> Let's move a 8 bit wide 'window' from the left to the right over it. This
> will give here following byte sequence:
>
> 00000000 h00
> 00000001 h01
> 00000010 h02
> 00000100 h04
> and so on.
>
> The requirement:
> let's require, that the bit sequence should 'contain' all of the 256
> possible byte values (where some or even all of the values can occure
> multiple times).
>
> The minimum length of such bit sequence not contradicting the obvious
> rule,
> that it is not possible to store all 8 bit values using less than 8 bit is
> 256 + 7 = 263 bit, but it seems to me, that there is no 263 bit long bit
> pattern which satisfies the requirement.
>
> If there is no 263 bit long bit pattern which satisfies the requirement,
> how long is/are the shortest bit sequence/s covering all 256 byte values
> and what pattern does/do it/they have?
>
> If someone asks himself what has this kind of question to do with
> compression:
> A sequence of 256 bytes requires 256 byte of storage space
> A sequence of 263 bits requires 33 byte of storage space which gives 87%
> compression ratio
>
> I don't think, that this is something new, so if there is a compression
> scheme which uses this kind of approach, how is it called?
>
> Claudio
| |
| Claudio Grondi 2005-11-14, 6:55 pm |
|
Thank you very much.
The information in your reply was exactly what I was looking for.
Claudio
"John_H" <johnhandwork@mail.com> schrieb im Newsbeitrag
news:e44ef.4$As2.88@news-west.eli.net...
> One example is
>
1011000111101000011111111001000010100111
110101010111000001100010101100110010
1111110111100110111011100101010010100010
010110100011001110011110001101100001
0001011101011110110111110000110100110101
101101010000010011101100100100110000
0011101001000111000100000000,1011000[col
or=darkred]
>
> where I included the comma to show where the first 7 bits of the sequence
> are appended to the end.
>
>
>
> The google phrase is "maximal length sequence" with the additional info[/color]
that
> the sequence for 8 bits would only give 255 unique values where the 8-bit
> all-0 or all-1 sequence is missing. I just added an extra zero to the
7-bit
> 0 sequence to make it all 256.
>
>
>
> Not that this information will help you.
>
>
>
>
>
> "Claudio Grondi" <claudio.grondi@freenet.de> wrote in message
> news:3trke5Fu42t0U1@individual.net...
This[color=darkred]
is[color=darkred]
values[color=darkred]
87%[color=darkred]
>
>
| |
| Ben Rudiak-Gould 2005-11-15, 7:55 am |
| Claudio Grondi wrote:
> Knowledge about the existance of a 263 bit long sequence has whetted my
> appetite for more and now I am wondering if it is possible to get it down to
> a 256 bit long sequence when allowing the bit 'window' to go around i.e. to
> close the chain of bits into a bit circle in which the 'window' runs its
> lap.
The example that John_H posted had this form. He even included a comma to
show where it wraps around.
> The only approach for the search for such a 256 bit long sequence(s) coming
> to my mind is by brute force, but this seems to exceed the computation power
> of any available computer...
Such sequences can be generated using a linear feedback shift register
(which google).
But your dream of exploiting this for compression is doomed to failure.
-- Ben
|
|
|
|
|