I wonder how it is possible to compress music files to 2/3 of the original file. I mean if I take a *.wav file and use WinRar for compression, it won't do much. As far as I know about the WinRar algorithm, it finds strings that are used many times, puts it on an index, and finally replaces these long strings with shorter ones that refer to the original string in the index. However, this seems to work fine for files like uncompressed pictures, programs or other files except for uncompressed music. So how is FLAC or WMA Lossless doing it then?

Thanks

http://www.monkeysaudio.com/theory.html

they use magik I think

the magic word is "Prediction"

http://flac.sourceforge.net/format.html#prediction
http://www.monkeysaudio.com/theory.html
http://www.stanford.edu/~mbax/ee392c/node5.html

It is mathematiclly impossible to create a single technique for compressing all possible data streams. However, most useful data has redundancy. In theory, an stream of data that contains any redundant information can be compressed, though often that redundancy is present in a way that requires a special purpose algorithm. One example of redundant data in audio is correlation between left and right channels.

The basic theory behind flac and a some other lossless compressors) is the concept of a "predictor".

For each input block, a predictor is chosen for that block. A predictor is a formula that "guesses" at the next value by doing some math on the previous few values. The guess probably won't be exactly right, but it will be close. For example, a simple linear predictor might be:
p = 2*v1 - v2
or to make it more readable:
p = v1 + (v1 - v2)

Where v1 is the previous value, and v2 is the value before that. This particular predictor assumes that if the last coule values were "moving" in one direction, the current value will probably be a similar distance in the same direction. This probably won't exactly be true, but it may be close. When encoding, the difference between the actual value and the predicted value (p) is stored as in a stream of data called the residual.

The goal is to make the numbers in the residual as small as possible. The predictor chosen for the block is stored in the block header (it only takes a couple bytes). The residual, which ideally consists of much smaller numbers than the original signal, is compressed losslessly in a way you're probably more familiar with. FLAC uses rice codes (which to my understanding is basically a special case of huffman coding). More common numbers are given shorter codes, less common ones are given longer codes.

When decoding, the decoder takes the last few decoded values, runs them through the predictor formula for that block, then add the residual for that sample.

FLAC does some other things to reduce size. Notably, it can adaptively switch between mid/side channel encoding and L/R channel encoding to try to improve the predictability of a block.

For a very detailed explanation of how FLAC works, please read:
http://flac.sourceforge.net/format.html

Also, while FLAC doesn't use huffman coding, I recommend doing a google for it, because it's a very interesting topic if you're interested in how compression works, and rice coding is similar.

Wow! Thanks for all the links and stuff to read. I find this topic extremely interesting though, it sort of fascinates me. I haven't read anything yet, but I'll go through all this stuff later. One questions just popped up in my head...is it true that it'll be hard to make lossless encoding even more efficient? I found that wma lossless does a slightly better job than FLAC does in terms of the file size but it is pretty much about the same. Wma lossless also seemed to be a little faster though. However, can lossless even be improved? At the time, we are talking about saving about 1/3, but will it be possible to save something like close to 50%? Another thing, why don't we have hardware players that play FLAC or Wma lossless? I mean this way we could fit even more songs on a CD without any disadvantages...

Yeah ... it'll be hard to make lossless encoding even more efficient. It's already big
problems with lossless coders. Most of them as you know are symmetric and some
of them works very slow even on high-end machines. So it's quite possible to create a very efficient algorythm but it will be slow as hell. But who knows ?
Have you heard about NetopSystems FEAD Optimizer ? It is unique compression
technology (not audio related) which consists of about 80 different sub-algorythms.
Maybe someday somebody will make a very efficient lossless coder ...

There are several hardware lossless players.

The reason why WinRar's compression does not work well for music (and pictures, in fact) in noise. "General purposes" compression schemes expect "noiseless" information. This makes the probability of finding (exact) repeated strings reasonably high. In music, on the other hand, it very low. But the probability of finding "something similar" is higher. So, we need to store the error (the noise).

WinRar couldn't do anything without special music-related preprocessing.

-Eugene

For those of you that are interested in the possibilities of lossless encoding, I have written (together with a friend of mine) a program that allows you to experiment with all kinds of different encoding schemes by creating configuration files that specify how the sounds should be compressed. At the moment you'll have to download it from CVS and it hasn't had any work done on it for some months, but it's quite stable and it's already quite interesting to play with.

You can choose from several prediction methods (polynome, wavelets and some strange adaptive polynome algorithms, as well as different methods of averaging) and you can use start-step-stop codes to emulate Rice (and other encodings), which also includes some different adaptive sss encoders. Then there are some other miscellaneous components. And all these components can be plugged into eachother and stacked in all sorts of ways (basically every component has some outputs which can be connected to other components).

The compression isn't as good as Monkey's or FLAC's, but we have had a configuration that on average beat Shorten (which isn't too bad considering most things aren't optimised that much). Also it is possible to relatively easily expand the program to have more components that can be used (anybody interested in writing some?).

As for documentation, we made it as a school project and as such there is our report in Dutch, which has quite a comprehensive explanation of the entire program as well as testresults.

The SF project is at:
http://sourceforge.net/projects/pws-sces/

Warning: Please do NOT use this program for archival purposes! This program is developed exclusively for the purpose of experimenting with compression and as such is not designed to guarantee perfect reproduction under all circumstances (in particular the method used to compress the file can be stored inside the file, but when linking to other files these will not be included, and sometimes you will loose some bytes at the end of the file - although it will usually add some). Also there is absolutely no guarantee of backwards compatibility at all (especially for the audio files, the configuration files are much less likely to change much).

edited: Added the warning message.

Well as I understand it, most lossy codecs like mp3 are frame based and contain all the information for a given portion of music (say 1/10 second) within one frame. Lossless codecs based on prediction need to read many 'frames' to reconstruct a piece of music and this has higher requirements for free memory and/or processor speed. As hardware players tend to be lower spec compared to modern PCs this would make it difficult to produce a player that played these files with all the niceties a consumer player needs, such as smooth FF/REW.

Well that's not exactly correct, FLAC compresses audio in blocks, Monkey's Audio compresses each sample separately. I also don't think it should be that much more difficult (slower) to encode or decode audio losslessly, it just depends on the codec. What is true is that a lot of lossless encoders are symmetrical in the sense that the decoding step is essentially the same as the encoding step, only the other way around, which usually means that decoding is relatively slow. But FLAC for example is asymmetrical, and I think I've heard hardware FLAC support mentioned, but I don't know wether there are any actual devices for sale yet that support it.

Do you have a link or some specific players in mind? I actually wondered why our CD-Players aren't able to play FLAC files. That way we could fit even more songs on a CD without having the issue of loosing any quality.

Why not looking on the FLAC Homepage?

-Eugene

To answer this question properly you need to dive into information theory. Try starting with the comp.compression FAQ.


There are FLAC players, mainly because the decoding complexity is low enough to be done in software and the reference decoder is plain old C. WMA lossless cannot be done in S/W on most (current) players, so I think MS usually has to develop a custom hardware decoder or HW/SW combo for each OEM. This is less than ideal. For an example of this you can peruse the Audiotron forums/lists for how this is playing out.

Josh