µδ code

Look at these new logs:

https://hackaday.io/project/24834-3rgb-image-lossless-compression-format/log/60063-colorspace
https://hackaday.io/project/7385-recursive-range-reduction-3r-hwsw-codec/log/60068-breakthrough

The have some similarities with µδ but they differ in critical ways:

• µδ works with median and difference while the new transform creates a sum (σ) and one of the operands (let's call it α). The new transform shall then called σα.
• µδ works inside a ring (a closed set with wrap-around) but σα "escapes" this (the output is not constrained inside the original boundaries), which allows actual compression for some combinations of values.
• actually σα has an initial value range that is a ring, however each operand can have its own original ring, they both are combined and the boundaries remain as auxiliary data in the background.
• σα is used with VLC (variable length codes) while µδ uses fixed-length words.

σα already has a fantastic application in the color decomposition of RGB pictures and will make 3R a truly entropy coder... Follow the developments there !

Before we start, let's just remember and examine one of the fundamental rules of arithmetics. If you take 2 non-negative numbers and add them, the sum is equal or greater than any of the addends. This is the rule that makes the #Recursive Range Reduction (3R) HW&SW CODEC work.

In a more general way, if you have two numbers of N bits, you need N+1 bits to uniquely represent the sum. Since X+X=2X, 2^N + 2^N = 2^(N+1). This +1 is the carry bit and is required to restore the original addends if you ever want to subtract it back from the other.

Same goes for the subtraction : the difference requires a "borrow" bit. You can't avoid this, even though there are some cases where you can work modulo 2^N.

We are used to dealing with the carry and borrow bits but things can quickly get out of hand! Imagine you want to compute a 1024-tap integer FFT: each result will be the sum of 2^10 numbers, adding 10 bits to the original sample size. If you're dealing with CD quality, 16+10=26 bits so it fits in the 32-bits registers of common CPUs or DSPs.

Now if you want to use 24-bits samples, you're screwed. 34 bits don't easily fit in 32-bits registers. Will you resort to slower 32-bits floating points ? 40-bits integers ? 64-bits integers ?

Take the classical 8×8 DCT square now. The original 8-bits samples of a picture get fatter during each of the 3+3=6 passes, resulting in 14 bits for the results. The integer units have almost doubled the precision of the source data and this considerably increases gate count, latency, power consumption...

Now you start to see where I'm getting to : the classical filters and time-frequency transforms have a fundamental problem of size.

OpenSilicium#19 is out !

I'll publish the code soon.