Why not Compression to cut board cost?

[flf]

The point is to:
A) Compress data without introducing latency
B) Transmit data compressed smaller than original, thus saving bandwidth
C) Decompress data without introducing latency

Not really, because A and C are impossible. The point is to start considering compression when bandwidth is significantly limiting performance, moreso than latency. For a large portion of processing, latency is the larger concern.

I should have written it as "without introducing effective latency." Sure, there may be latencies, but we design our logic to hide those latencies with queued multi-stage processing and caches. Perhaps it would be better to say that the whole time encompassed by A to C needs to be consistently (on average, and bounded by an upper limit) shorter than without compression in place.

Is that stating it a little more correctly?

 

[flf]

flf:
I don't think you'll find many people calling that data compression. Using symbols that can store more than 1 bit might be good in some cases. It might result in smaller chips with the same memory/calculation capacity. But calling it data compression is almost like calling a switch from .15u to .13u data compression.

The basic rules of information theory won't change because you change the basic symbol you work with. You just store N bit in each symbol (where N might not be an integer).

You're assuming that we convert them back to bits at some point. This may not be the case. Also, you're assuming that the data stored is analogous to currently stored structures... and we don't know for certain this is the case, either.

Anyhow, my only point was that compression might have different optimization characteristics on machines that aren't 2-state. How they actually work is conjecture since at this point they've only begun to scratch the surface as to whether such machines are even possible.

That and the fact that I'd be quite surprised if anyone were to develop a lossless binary compression that wasn't simply a small refinement of what we already have. Democoder showed above that "you cannot put a finite smaller set into 1:1 bidirectional correspondence with a larger set," which means that there are some limitations that no amount of processing or mathematical chicanery can overcome... unless we change the foundations of the rules. Of course, whether we can build a machine that uses a different set of rules is the question of the day.

 

[KimB]

I should have written it as "without introducing effective latency." Sure, there may be latencies, but we design our logic to hide those latencies with queued multi-stage processing and caches. Perhaps it would be better to say that the whole time encompassed by A to C needs to be consistently (on average, and bounded by an upper limit) shorter than without compression in place.

Is that stating it a little more correctly?

You could only do that with an assumed data block size. Uncompressed data can be essentially passed in arbitrarily small chunks, so if the data requested is smaller in size than a compressed block, you can't do the above.

I think that typically, you'd need to be very heavily bandwidth-limited for compression to do as you state above. Random data access will probably not fit into that paradigm.

 

[3dilettante]

Democoder showed above that "you cannot put a finite smaller set into 1:1 bidirectional correspondence with a larger set," which means that there are some limitations that no amount of processing or mathematical chicanery can overcome... unless we change the foundations of the rules. Of course, whether we can build a machine that uses a different set of rules is the question of the day.

The rules are basic math, so it's going to get hard to change them.

One way I can see getting around this is pretty kludgy and probably insanely hard to implement with any margin of functionality.

If the memory subsystem was based on a trinary number system with everything else converting to binary, you could store more data per bit. However, you would wind up making memory needs slightly lower at the price of much more complicated hardware and seriously reduced noise margins.

 

[Basic]

flf:
No, I didn't assume any conversion to binary. If you got misled by my use of 'bit' as a unit, then I'm sorry for that, I should have been more clear about it.

In information theory you use the unit 'bit' to measure information, regardless to how it's stored. This unit is equivalent to the amount of information one bit (as you know it) can hold. A N-value symbol can hold log2(N) bit of information. (Note how that coincide with the "obvious" values log2(2)=1, log2(4)=2, log2(8 )=3 ...) So a 3-value symbol can store log2(3)~=1.585 bit

Information theory is rather well researched, and what we're talking about here is just the very basics. And a lot of it is abstracted in a way that the "size" of a symbol can be arbitrary. So changing to N-value symbols is not a change in the foundations of the rules.

If you can find a way to compress random data with a N-value system, then it's fairly easy to map the method back to binary.

Designing a compression scheme isn't so much about what kind of symbols it's stored with, as about knowing the typical redundancy in the input data.

 

[KimB]

To support what Basic just said, consider that a byte holds one of 256 values. A byte is made of 8 bits. What difference would there be, then, in modern computers if there was a storage device with 256 discreet states, or one with 8 times as many storage locations with 2 discreet states each?

 

[DemoCoder]

Well, it is true that you can't design an algorithm that can losslessly compress at a fixed rate (as I showed) for an entire set of inputs. But it's also possible to prove (via Algorithmic Complexity Theory) that you can't ever find the best compression algorithm, *even for a single input*

Consider compressing arbitrary digit strings. Using a standard text compressor, you'll compress some by significant amounts, but others, which are more random will actually expand. But what about a number, say, PI? I could design a special algorithm for that, which, if detected, would switch to a special decompressor that generates PI procedurally.

Now of course, the size of your compressed data is the size of the decompressor that is built into the decompression program. But is this the smallest representation? You can't prove you have the shortest generator for PI and it is impossible to do.

No amount of switching systems and techniques can violate the no-fixed-lossless rule. However, one could find that one's target data is clustered in specific ways and design a lossless compressor that would do very well for that data, but do poorly for everything else. It would not be general purpose, however, and most likely, unusable for realtime 3D anyway.

 

[Bjorn]

Note: i'm giving away this algorithm for free:

000 : 0
001 : 4
010 : 2
011 : 6
100 : 1
101 : 5
110 : 3
111 : 7

How about that ? a 3:1 compression rate, and it's lossless.

 

[flf]

Note: i'm giving away this algorithm for free:

000 : 0
001 : 4
010 : 2
011 : 6
100 : 1
101 : 5
110 : 3
111 : 7

How about that ? a 3:1 compression rate, and it's lossless.

Are we assuming an "8-state bit" theoretical computer that you are encoding for?

Can we assume that if we are talking about compression of a digital signal using today's technology that the only valid signal states are 0 and 1? So, as thus, any "compression" scheme must have inputs and outputs of only strings of 0s and 1s? (Which is why I think your post is about encoding for an 8-state machine. Correct me if I'm wrong.)

But, as objected to above... is this compression? It's tokenization for a differing signal set, but the resultant token string itself is a raw representation of the original with no compression. Is a simple look-up table for encode/decode considered compression?

 

[flf]

flf:
No, I didn't assume any conversion to binary. If you got misled by my use of 'bit' as a unit, then I'm sorry for that, I should have been more clear about it.

In information theory you use the unit 'bit' to measure information, regardless to how it's stored. This unit is equivalent to the amount of information one bit (as you know it) can hold. A N-value symbol can hold log2(N) bit of information. (Note how that coincide with the "obvious" values log2(2)=1, log2(4)=2, log2(8 )=3 ...) So a 3-value symbol can store log2(3)~=1.585 bit

Information theory is rather well researched, and what we're talking about here is just the very basics. And a lot of it is abstracted in a way that the "size" of a symbol can be arbitrary. So changing to N-value symbols is not a change in the foundations of the rules.

If you can find a way to compress random data with a N-value system, then it's fairly easy to map the method back to binary.

Designing a compression scheme isn't so much about what kind of symbols it's stored with, as about knowing the typical redundancy in the input data.

So the conclusion is that future technology does not change either the nature of the data manipulations nor the math underlying those manipulations... thus, future technology cannot deal with the contraints of lossless compression any better than present technology can.

Therefore compression is a mitigating technology that can marginally improve performance (perhaps greatly in specialized cases), but is secondary to the signaling technology itself.

To paraphrase: Put your research money into developing faster/wider signaling methods rather than trying to rely upon developing better compression techniques to improve bandwidth availability, because there is only so much compression can do.

Does this answer Hellbinder's original question about why we don't have a super-compression to solve our bandwidth issues?

 

[KimB]

Note: i'm giving away this algorithm for free:

000 : 0
001 : 4
010 : 2
011 : 6
100 : 1
101 : 5
110 : 3
111 : 7

How about that ? a 3:1 compression rate, and it's lossless.

Hahaha! Man, that gave me a good laugh. Now, should I be worried that I thought it was funny?

 

[3dilettante]

Here's the perfect compression algorithm: http://lzip.sourceforge.net/

edit: Check the FAQ to learn about the Lessis-Moore algorithm.

 

[Simon F]

flf:
I don't think you'll find many people calling that data compression. Using symbols that can store more than 1 bit might be good in some cases. It might result in smaller chips with the same memory/calculation capacity.

Are you refering to the idea that using a 3-value unit (trit) instead of a 2 value unit (bit) would be more efficient because 3 is closer to the theoretically optimum e (=2.7etc)?
I think that would indeed reduce the storage costs but I've read that it would make all the rest of the HW more expensive because instead of needing to make a single comparison to determine {0, 1}, you need 2 tests to classify {0,1,2}.

Thus, AFAICS, if you use this to estimate the HW cost of an N-value scheme, a better choice is to use a system that has 3 comparisons (i.e. closer to to e), in which case you have a 4 value system which, AFAICS, is effectively just back to binary<shrug>

 

[KimB]

How would being closer to e help?

 

[Simon F]

How would being closer to e help?

If you asked me that when I'd just finished Uni then I probably could have answered you immediately, but since it's been nearly 2 decades, I can't

 

[KimB]

On the surface, I don't see any fundamental difference. You'd just need to restructure your basic math structures to trinary (if you were to model the entire system as a three-valued system). You'd still be doing all of the same operations, data would just require fewer symbols to represent.

 

[3dilettante]

I don't see why approaching e has anything to do with the efficacy of a numbering system. Being able to store many values per bit is one of the few cases where more is better (in the abstract).

The big problem comes with implementation, since the noise margins for any memory chips are going to be split up into many smaller bands that are much more vulnerable to transient noise or crosstalk.

 

[KimB]

Noise should only be a problem for signalling, not the storage components. But which storage components are used should determine what symbols are possible.

 

[3dilettante]

If a DRAM were made trinary, it would either have to partially charge capacitors, or double up the number of capacitors per bit, so that there would be a both off, one on/one off, both on states.

The second option seems a little self-defeating capacity-wise, while the first sounds pretty hard to get right consistently.

 

[Simon F]

On the surface, I don't see any fundamental difference. You'd just need to restructure your basic math structures to trinary (if you were to model the entire system as a three-valued system). You'd still be doing all of the same operations, data would just require fewer symbols to represent.

Since no one else seemed to bother to go googling, the answer tom why e is considered the optimal choice is here.

Incidentally, Turing considered that e would be optimal and that's good enough for me.