On 8/9/15 5:07 PM, Sampo Syreeni wrote:
On 2015-07-18, robert bristow-johnson wrote:
even so, Shannon information theory is sorta static. it does not deal
with the kind of redundancy of a repeated symbol or string.
In fact it does so fully,
really? like run-length encoding?
and i've always thunk that the data reduction that you get with LPC (to
reduce the word size) that depends on the spectrum of the data was a
different thing that Shannon information theory was looking at that
might lead to Huffman coding.
and I believe Peter's problem is about not figuring out how it does
this. (Sorry about arriving at this this late and reviving a heated
thread.)
The basic Shannonian framework works on top of a single, structureless
probability space.
yes, and you can model dependent probabilities, i s'pose. so you can
put together compound messages that have less information needed to
represent them than you might have if they're separate.
Any message sent is a *single* word from that space with a given a
priori probability, and the information it conveys is inversely
related to the probability of the symbol. Thus, the basic framework is
that we're computing the probabilities and the resulting information
based on *entire* signals being the symbols that we send.
Shannon entropy is then revolutionary because under certain conditions
it allows us to decompose the space into smaller parts. If the entire
signal can be broken down into Cartesian product of separate,
*independent* part signals, the whole information content of the
signal can be calculated from the partwise surprisals. That's how the
uniqueness of the entropy measure is proven: if you want the
information in the parts to sum to the information of the whole, and
each part's information content is obviously related to the number of
combinations of values they can take, then the only measure can be a
logarithm of probabilities. At the bottom that's a simple homomorphism
argument: there is no homomorphism from products to sums other than
the logarithm.
But notice that there was an independence assumption there. If you
plan to decompose your signal into smaller parts, Shannon's formula of
additive entropy only holds if the parts don't affect each other. With
periodic signals this assumption is violated maximally, by assumption:
every period is the same, so that a single period correspond to the
entire signal. For the purposes of talking about the entire signal and
its entropy, you only ever need one period, and the underlying
probability it varies within.
one thing that makes this encoding thing difficult is deciding how to
communicate to the receiver the data that the signal is close to
periodic and what the period is. and when that changes, how to
communicate something different. it's the issue of how to define your
codebook and whether the receiver knows about it in advance or not. you
could have a variety of different codebooks established in advance, and
then send a single short word to tell the receiver which codebook to
use. maybe for non-white signals, the LPC coefs for that neighborhood
of audio.
More generally, if there are any statistical correlations between the
decomposed parts of any entire signal, they'll in a certain
probabilistic sense mean that the entire symbol space is more limited
than it would at first seem, and/or that its probability distribution
clumps further away from being the flat, maximum entropy distribution
Shannon's machinery first expects. The surprisal of the whole thing is
lowered.
In limine you could have *any* signal *at all*, but always sent with
100% certainty: when you saw it, its surprisal would be precisely
zero. That's the trivial case of the underlying probability space for
the entire signal being composed of a single message with probability
1, *whatever* that one signal might be.
Peter's problem then seems to be that he doesn't specify that
underlying probability space nor state his assumptions fully. He
calculates on signals as though their successive part-symbols or
periods were independent, as if Shannon's decomposition worked. But
between the line he assumes that signals coming from an entirely
different kind of, far more correlated-between-his-chosen-partition
were an equal option.
Obviously that leads to teeth grinding and misery, because it isn't
even mathematically coherent.
just with the probability of occurrence (which is measured from the
relative frequency of occurrence) of messages. run-length coding
isn't in there. maybe there is something in Shannon information
theory about information measure with conditional probability (that
might obviate what LPC can do to compress data).
In fact LPC and every other DSP transformation we use in codecs are
well within Shannon's framework.
i didn't know that. it appears to me to be different, almost orthogonal
to the Shannon thing.
There, the basic message is the whole continuous time signal. If you
really push it, you can model pretty much anything with any kind of
noise and serial correlation (corresponding directly to any LTI DSP
process in continuous time) with (huge) multivariate distributions as
well. Of course now modulo a number of measure theoretical
quirks...but you can.
It's just that we don't want to. Instead we take the back alley and
model the salient psychoacoustical correlations we see using well
understood LTI math, and the sampling theorem which lets us go to a
numerable base which retains much of the properties of the continuous
domain (mainly shift invariance; that's another neat homomorphism,
basically). Combined with the noisy channel coding theorem, we're set
to do some real calculation of the MP3 kind.
And really, this ain't rocket science when you get it. It's just that
you have to delve into the structure behind it before it gets easy.
Peter doesn't seem to have done quite that, but instead jumped
straight into formulae and simulations. That sort of thing of course
sidetracks you from really getting the wider picture...and as in here,
particularly the edge cases like periodicity and such. :)
--
r b-j r...@audioimagination.com
"Imagination is more important than knowledge."
_______________________________________________
music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp
