DPCM, ADPCM, u-Law, LPC, compression and redundancy

[Max]

----- Original Message -----
From: "Detlef Morgenstern" <detlef_morgenstern at yahoo.de>
Sent: 11 May 2001 02:23
Subject: Re: DPCM, ADPCM, u-Law, LPC, compression and redundancy


> Hello Max,
>
> I had a short but interesting talk with Prof. Brandenburger, the MP3
> inventor. I wanted to suggest him following up this idea:
>
> Audio compression distilles the essence from a piece of sound. An
> audio compressed sound is less redundant (= more abstract) compared
> to the source sound. Couldn't this be done with information in
> general? Compress it - to get its essence?
>
> Want to know, what he replied?
> "No chance, because a compression like MP3 exploits our knowledge on
> the specifics of the neurobiology of our hearing sense."
>
> But this IS the very chance:
> Get into the specifics of the neurobiology of our mind! How can we
> exploit some 'deficiencies' of our mental neurobiology?
>
>
> Detlef
>
> --- M. Little <ltu98ml at rdg.ac.uk> wrote:
> > Dear Compressionists
> >
...
> > But
> > this algorithm achieves it's effect not by coding for a universal
> > attribute of sound sources, but by exploiting some 'deficiencies'
> > of our neurobiology.
>
...

>I wonder whether the issue here is between *lossless* and *lossy*
>compression?
>
>My understanding of compression techniques is that they all try to extract
>redundancy from information but with 'lossy' techniques, some of the
>non-redundant information is sacrificed too.
>
>With lossless compression it is usually possible to reconstruct the original
>information without any errors. With lossy compression this is never
>possible.
>
>Why should anyone bother with lossy compression? The main reasons are that
>the process of compression (and possibly decompression) can be much faster
>than with lossless compression and the amount of compression can be greater.
>
>Because our nervous systems are not 'perfect' there are certain kinds of
>degradation from lossy compression that we may not notice. Hence "No chance,
>because a compression like MP3 exploits our knowledge on the specifics of
>the neurobiology of our hearing sense."
>
>Gerry

Gerry

>From a pragmatic standpoint, I agree that the issue here and now can be
about lossy versus lossless compression. This is why I wanted to raise the
question: is compression algorithmic complexity inversely proportional to
computational economy? I admit Gerry that I have only studied your ICMAUS
papers with cursory attention to detail and so I hope that I am not merely
grinding metal.

In one sense it seems to be: a simple algorithm with only a few 'production
rules' (I think this is an old AI term) might be a very memory-efficient way
of storing a much larger pattern. But in another sense it is not: if the
rules are few but either deeply recursive or require numerous iterations
then this is uneconomic.

Assume, for simplicity, that there is a unit time per iteration and a unit
memory location per rule, then you can make a score that measures the
'efficiency' of the algorithm: this would be a sum of the number of
iterations required, the number of rules stored divided by compression ratio
that it achieves. For example, given the string:

000011110000111100001111

this can obviously be compressed as

00001111 rep 11

where '<d> rep <n>' obviously is a simple infix functional rule for
repetition, and the numbers <n> and <d> are binary strings. Now, at the very
least according to the assumptions above this scores ((8 + 1 + 2) + (3)) /
12 = 1.1666. Another way is:

0000 rep 01 1111 rep 01 0000 rep 01 1111 rep 01 0000 rep 01 1111 rep 01

this is far worse and scores worse. But there are less trivial and more
contentious possibilities:

1111 inv 110

where '<d> inv <n>' inverts the <d> string wholly, stores it and outputs it,
<n> times. This scores ((4 + 1 + 3) + (6)) / 12 = 1.1666. So this is the
same as the first. Is there a fundamental limit at work here? Can an
algorithm be found that is more efficient for this string?

Finally, does anyone know if mathematical category theory might be able to
shed some light on CASC?

Max
-------------------------
Max Little
miggs at little.tele2.co.uk