Hi!

As U know one step of the hole MP3 encoding process is the 'Hoffman encoding'
that works something like the (Win)Zip compression.
Does anyone know how strong it is able to compess the remaning audio data?


Input => 'Hoffman encoding' => Output

Let's say the 'input' is 100% (unrespected what has happend before).
Now - after the Hoffman encoding - how big is the 'output' in general?
Approximately 50%? - More? - Less?


Thx 4 your answers,
384kbps

Friendly reminder:
Other than that, it's "huffman" not "hoffman".

Ha ha ha, that's more of a funny reminder in this case.

Dear Mr. Huffman,

Please forgive me, it was never my intension annoying You
with a wrong written name.

I'm very glad now to know how to write Your name the right way!
Nevertheless i still wonder how efficient Your algorithm woks.
However, it does a great job at all!


Yours sincerely,
384kbps

What Peter means by his quoting of the TOS #10, is that you shouldn't use abbreviations such as "U" instead of "you" or "Thx 4" instead of "Thanks for". Speak properly if you want to be taken seriously. How much time did you save by using those abbreviations?
I know, it isn't obvious. TOS #10 isn't explicit on this regard. I have proposed an extension of the explanation in order to address this issue specifically.

In fact, huffman encoding is only the second part of the deflate algorithm (used in *zip). Used by itself (both static and dynamic variants) it gives a weak performance (make a search in any data compression tutorial; it gives about 50% and more for text files IIRC).
The problem is, it not obvious how to apply it directly to music. If you take sample values as input the performance will be really pour, because most values have the same 0-order probability.

-Eugene

I am sorry to inform you that Mr D. Huffman is not directly able to answer you, mainly because he passed by about 2 years ago.


Back on your question, in mp3 the Huffman compressed data is about 80% of the original size.

Hi - Thank You both for your immediate responses!

Indeed I like to know how good that lossless encoding step works
to be able to estimate how 'cruel' all the lossy steps before are.


384kbps

Sorry, my fault.
Often i simply try to write as short as possible at the expense of the readability...

I will try to prevent this bad taste in future.

384kbps

It took some time to find my abacus...

So 80% would mean that in a (fully channel separated) stereo MP3 (frame)
encoded with 128kbit/s, the MP3 encoding process generates out of 8 tones
(originally taken from CD) only 1 tones to put it in this MP3 !?

As joint-stereo MP3 (where left and right channel divert by 50% for example)
i guess it is about 6(CD):1(128kbps-mp3) - but even this is quite rough.

... and it still sounds anything like music!


Is there anything more to respect in this 'calculation'?
384kbps

Sorry - I just couldn't resist: Of all the places in the world, a requirement to speak/write proper English would be the one place you would expect to find proper English

Anyway, AFAIK "SPAM" is a trademark and it denotes the canned "meat" sold in the UK, and "spam" is the correct way to refer to unwanted e-mails.

Um, shouldn't it be 125 successive tones in the space of 100? (To twist your analogy a little, that is.) How did you get "only one tone in the space of eight?"

It means that 100kb of data before Huffman will be about 80kb after Huffman processing.
Huffman coding is just a tool to further reduce bitrate, but it is not the source of the main data reduction.

Thanks for helping me on this task.

Why 8:1? - I have tried to find a simple ratio to convince
MP3-far-standing people to make better MP3s. - It's only 'mathematical':

a) 128kbps is 80% (huffman compressed), so 100% (expanded) is 160kbps
b) CD quality is about 1380kbps.
c) 1380kbps:160kbps is the a ratio between 8:1 or 9:1
d) So you have only 1 tone 'made' of 8 (or 9) in a 128kbps stereo MP3.


Now often MP3 are using the joint-stereo mode to safe further space.
(it gets problematic now... As You know, the amount of safed space is different
on every single track, depending on its original channel separation).

f) So let us suppose the Mid-channel would be in this example 2x as big
as the Side-channel
g) Such a joint-stereo MP3 safes 25% space
h) In other words, on the given space the encoder has no need to take
8 or 9 tones to process, because the space consuption is more effective
on a joint-stereo MP3. If you calculate it, it is only about 6:1.



I hope i have nothing forgotten aud that MP3 allows such abstract calculations.
However i have made letters so You can easily invent if You disagree.

384kbps

What are you trying to say? Do you mean that you don't understand why MP3 compresses 8:1 even though Huffman only gives around 1:1.25?

Menno

b) CD audio is 44.1kHz 16bit stereo PCM. For PCM, the bitrate is sampling rate times sample size times the number of channels, so a CD's audio bitrate is 44100 x 16 x 2 == 1411200 bits per second.

c) 1411.2/160 gives you 8.82

d) That's not how lossy compression works. If you could hear 8 tones in the original, then you should be able to hear all those tones in the MP3.

edit: minor clarifications.

a - Yes - This basically means that, thanks to Huffman coding a 128kbps frame holds about 160kbps of encoded data on average.

h - Wrong. The encoder takes everything (below the lowpass) into account, not just 6 or 8 tones. Also the unimportant "tones" are not removed - they are just encoded with less precision.

I mean it relative. - Indeed, i forgot the lowpass filtering.

I wasn't looking for an absolute number. I have tried to find a ratio,
how hard the lossy part of the MP3 encoding must work.

That's what i have meant with 8:1 - in context of my mad encoding idea:
- lowpass-filtering (thanks!)
- lossy compression, in the case of a 128kbps stereo MP3 with ratio 8:1
- lossless huffman compression


Well, it would be great if anyone could provide some notes or web links
how something can be encodec with more or less precision.
(I hope this won't be too difficult because i only have a rough imagine
about noise shaping and masking procedures.)

Thanks again,
384kbps

http://www.mp3-tech.org/content/?MP3

It's hard to catch a problem 'at the border of my knowledge'
with the right words...

So thanks for the link with all the information!
It will take some hours (=>days!) to understand all.

But i will return.
384kbps

Doesn't the efficiency of Huffman coding depend on the total entropy of the signal? Isn't one function of a lossy compression scheme to decrease this entropy by nullifying some data? At least in some models?

By the way, if I'm totally misguided I would really appreciate any corrections. I'm writing a thesis on this

Hi,

You can also suppress data by cutting the lower significant bits in a coefficient.

Yeah, in a way, you are right.. The efficiency of Huffman coding depends on the data statistics.. In some cases, huffman coding can actually consume more bits than the uncoded data if the development of the huffman codes does not correspond with the new data statistics.

In the case of mp3, I think the Huffman codes can be freely chosen - so this case would only happen if the mp3 encoder is buggy.

No, the Huffman codes can't be chosen freely. MP3 uses a set of fixed Huffman tables which are defined in the MPEG standard. The encoders can optimize the bitstreams only by choosing the "best" Huffman tables, i.e. the ones that result in the fewest bits.

Just a thought: Could it be possible to compress MP3 files even more by first decompressing the huffman encoded data and then recompress it with a more efficient compression algorithm? It's a common point of view that huffman isn't as efficient as defalte (for example) is.

So let's say if the Huffman part in the MP3 standardization was replaced by deflate or bzip2's compression scheme... wouldn't it result in significantly smaller "MP3s"? (I know, this term is wrong as MP3 is a standard and doesn't allow compression algorithms other than Huffman encoding to be used)

EDIT: By the way - I guess that I'm wrong but the above is probably what you can call a straightforward chain of thoughts regarding to compression efficiency. I think Huffman is to be used when it's about compressing a bunch of values which can be classified through their appeareance amount only and when it's NOT about compressing a regular octet stream with multiple appeareances of equal or similar value arrays.

Deflate and bzip2 use Huffman coding for the entropy encoding too. It just uses a different context model.

Menno

Isn't huffman coding technique the most efficient lossless coding method that ever existed? ..provided that the signal statistics of the data matches the particular huffman codes..

IIRC huffman is most effective if every input value is represented by an output value with a integer number of bits. Arithmetic coding doesn't have this limit and is better for this reason.

edit:
Somewhere here there's a good explanation by NumLock.

Are there any sites where you could read how MP3 compression works (every step is explained) and how psychoacustic models work? Also a site for digital music in general would be interesting.

There are two ways of doing that, and both were rejected in MPEG:

1. Use some other entropy coding algorithm, say arithmetic coding

While it might work better than Huffman, under certain circumstances (sometimes not), it has drawbacks that are serious when frame-by-frame audio encoding is a target. Drop-in (random seeking) and error protection are some of the things that are hard to do with arithmetic coding in MP3/AAC/...

2. Use adaptive Huffman codebooks, which are calculated from the signal statistic of the source material

This might improve performance by ~1% over current fixed codebooks, but unfortunately it is a heavy burden for decoder complexity, as additional memory would be required for storage of the custom codebooks and it would break some optimization possibilities - in addition, codebooks must be sent every time which complicates "drop in" streaming and encoder design as well.


It has been proven that fixed set of Huffman codebooks is a best solution for MP3/AAC taking into account all mainstream applications where these formats are used.