Sound Compression Algorithms

This is more of a theoretical/hypothetical question, but appreciate it if someone could give me a better idea / point me in the right direction.

Sound compression algorithms remove certain frequencies from audio files, reducing the quality of the sound, but saving space (take 128 kpbs vs. 320 kbps for example).

Is it possible to do the reverse? Say, up-convert from 128kbps to 320kbps or higher? Essentially write a "smart" algorithm that predicts which frequencies that need to be put back?


Thanks.

I am no expert but here is my question. The information contained in the 128kbps file represented in the frequency domain has a limited bandwidth due to the sampling rate. The 320 kbps file has more than double the bandwidth when compared to the 128Kbps file, but we do not know what information (frequency components) should be included.

There is no way to retrieve this information once it is removed. There are "intelligent" algorithms out there that do improve perceived sound quality and help fill in those missing frequencies on the high and low end, but they certainly are not reproducing anything close to the original music.

Most of them work by filling in missing high and low frequencies with harmonies of the of the music in the middle bandwidths(where more information is kept). I do not know the technical or commercial names for this technique, but it is widely implemented on media players already on the market.

That is interesting... It sounds kind of like up-converting DVD.

Hi, sorry but the simple answer to your question is "no".

If you want to go more in depth, you have to consider the sampling rate and the bits per sample. When you digitally sample a sound, the information between samples is thrown away. There is no way to get it back. The best you can do is draw a line from one sample point to the next.

As others have said, there are algorithms out there that guess what the data between points should be, but as implied, it's simply guess work.

So, no, you cannot get upconvert 128kpbs to 320kbps in the same way that upconveting a DVD from 480p to 720p or 1080p is useless.

You might consider reading about Nyquist Rate, Sampling Frequency and Aliasing: http://en.wikipedia.org/wiki/Nyquist_rate http://en.wikipedia.org/wiki/Sampling_frequency http://en.wikipedia.org/wiki/Aliasing

When most people think about sound compression, they tend to think about lossy compression algorithms like .mp3. If you are thinking about comparing 128kpbs to 320kpbs, what you are really comparing in the resolution of the data. More bits, means you can have a finer resolution and be more accurate to finer scales.

As Andrew and others have pointed out, once data has been removed (or lost) there is no way to retrieve it. Lossy algorithms will always throw away not only redundant data, but also data that the algorithm perceives as being 'unnecessary'. There are certainly algorithms out there, (and you could also try to create one yourself) that interpolate or predict what data would look like on the finer scales, but these will never be as good as data that was encoded using a lossless scheme. An interesting approach I once saw was to treat the lost data and being corrupted by noise, and then to use a Weiner Filter to try to reconstruct the original lossless signal. Lossless encoding (sometimes referred to as entropy coding in the information theory world) will only remove redundant data, and assuming you obey the all power Nyquist Theorem, it will be possible to decode and retrieve the entire original signal.

> There is no way to get it back. The best
> you can do is draw a line from one sample
> point to the next.

While I agree with what I think you are trying to say (once data is lost it's lost, get over it), there are better ways to interpret the existing data than to draw a line between samples.

Drawing a line between successive data points is essentially a piecewise linear interpolation. Note that the slope changes abruptly at each sample point, meaning there are steps in the second derivative, which should be a clue that high frequencies are introduced.

The same Nyquist theorum that tells us you can only faithfully capture frequencies up to half the sample rate also tells us how to reconstruct those frequencies *exactly* from the resulting samples. This is done with a filter that passes frequencies up to half the sample rate, then none above that.

For anyone looking for more information on this, the topic is called "reconstruction filters".

Just when you thought you knew everything about a topic, something new comes along to upset the apple cart. There are new techniques for sampling that violate the tenets of Nyquist. These new sensing techniques use random sampling of the signal, and the principle of sparsity.

Sparsity implies that while a signal may have sections or areas that require higher sampling, other areas of the signal do not. Most applications of these new techniques appear to be directed at imaging, where a scene may have complex areas and simple areas (sky, lake). Conventional wisdom would sample the image at a high rate to insure that the most complex portions of the scene would be captured with adequate resolution.

Now, getting back to the question about sound. A sound waveform may have sections with higher frequency components, and may also have sections without them. Using these new techniques it would theoretically be possible to sample at what would be an equivalent "128kbps" rate, but capture much higher resolution of the actual signal.

I have been trying (intentionally) to build the anticipation of just what I"m talking about. The techniques I am referring to are called "Compressive Sensing". They are quite new, I believe they have been developed in the past decade. They are based on statistical probability, not the basic "sample high enough to get everything" techniques of Nyquist, and therefore they have the ability to turn all of that conventional wisdom on it's head.

The technique was first developed at Rice university, and their website has as a wealth of information on the topic:
http://dsp.rice.edu/cs

Hopefully my brief comments are accurate, I am no expert on the subject, but I have read some papers on it. Compressive Sensing (CS) does not actually provide the solution that Anand was asking about, but I felt it was worth mentioning here as new students in electrical engineering will be hearing about these new techniques that go beyond Nyquist.

This is an interesting post - and took me by suprise - not because of the principles of using non-linear 'decisions' to compress the detailed bits - but more my shock that this is not already common practice in audio. Is it really not?

Similar methods of phase space measurements and a whole host of non-linear decision algorithms are the core of many video processing and compression algorithms.

Whether it is 'beyond Nyquist' is a moot point - as one can always look and analyse data from either a frequency or temporal domain - but it does make it clear that careful compression might not leave as much out as expected.

As for regenerating 'lost data' - hmmmm...

... I marvel at the episodes of CSI when someone takes a few dozen blurred pixel and recreates a clear image - all that is necessary is some cunning algorithm and a powerful computer. I look forward to the episode where the sample is only a few pixels!!!