Re: The variable bit cpu

> Your format allows arbitrary-length fields, but it requires 2*n bits to
> store n bits of data. A fixed and predefined layout would only require n
> bits to store n bits of data. Can you think of a good compromise between
> those two extremes?

First alternative would be static huffman compression and seperating the
data and meta bits into bytes.

Actually with static huffman compression there are 9 possibilities:

meta bits: compressed encoding:

1: 0000 0000 0000
2: 0000 0001 0001
3: 0000 0010 0010
4: 0000 0100 0011
5: 0000 1000 0100
6: 0001 0000 0101
7: 0010 0000 0110
8: 0100 0000 0111
9: 1000 0000 1000

So only 4 bits are required for the meta bits by using static huffman
compression:

So that's "only" 1.5 as much bits needed ;)

Second alternative would be only applieing the meta bits to a length prefix
field.

The length prefix field indicates the length of the next field which is the
data.

Bitstream: 1100011010101001110011100010101000
Metadata: 0001 001 0001

This would mean:

length data length length
data
12 - 6
5 -
Bitstream: 1100#011010101001#110#011100#0101#01000
Metadata: 0001# #001# #0001#

The meta data bits could be grouped together into a seperate bitstream

or

The meta data bits could be interleaved with the length data

one bit of meta data, one bit of length data, one bit of meta data, one bit
of length data, etc.

This last option would be good for communication protocols where otherwise
packets might go lost and important length data might go lost ;)

The final interleaved bit stream would look like:

Interleaved Bitstream: 10100001#011010101001#101001#011100#00100011#01000

45 bits in total.

11 bits for length data
11 bits for meta data
23 bits for data

Let' see how many bits are required for say value 2 million

255 - 8 bits

512
1 k
2 k
4 k
8 k
16 k
32 k
64 k another 8 bits

128 k
256 k
512 k
1 m
2 m another 5 bits

That's indeed 21 bits... ;) every 10 bits is 1000 decimal ;)

To store length value 21 bits

1 6 bits are needed
2
4
8
16
32

So using this scheme another 6 bits for meta data is a total of 12 overhead
bits.

So 12 overhead bits vs 21 data bits.

There is a clear saviour/reduction there ;) :)

With huffman about 12 overhead bits would be needed as well. 4 bits for each
byte.

Now let's take a bigggggg data type.

Let's say 1 megabit. 1 miljoen bits of data.

20 bits for a length field with another 20 bits for a meta data field.

Now only 40 bits are required for a data field which is 1 miljoen bits long.

Huffman would require half which is 0.5 milion overhead bits
My original idea would require 1 milion overhead bits.

This new encoding

prefix length + prefix length marker + data would only require 40 overhead
bits ;)

And is still as flexible as any encoding ;) :)

Bye,
Skybuck.


.