4
$\begingroup$

I have recently been involved in a discussion with someone who doesn't accept that lossless compression is possible, even in principle. This person considers himself to be technically literate, and an expert in his field of audio engineering.

I and several others have patiently tried to explain how lossless compression is possible, using simple examples such as run-length encoding and delta encoding, but he refuses to believe that it's possible for a lossless audio codec such as FLAC, for example, to exactly reproduce the input bitstream from the raw PCM data.

His response is always along the lines of:

it's getting smaller, so it must be losing data

"lossless" is just a buzzword used by software companies to sell their software, it doesn't actually mean lossless

Are there any other examples I can use to demonstrate conclusively that lossless compression is actually possible?

$\endgroup$
  • 4
    $\begingroup$ Text compression works. The point is that both text and audio are predictable. But this is beside the point. FLAC is lossless, and it works. No need for any further proof. To demonstrate that it's lossless, you can compress, decompress, and compare. $\endgroup$ – Yuval Filmus May 24 '17 at 20:53
  • 4
    $\begingroup$ Also, it's not the case that "it's getting smaller" in all cases. If it's lossless, then by pigeonhole principle sometimes it'll have to get bigger. $\endgroup$ – mhum May 24 '17 at 21:55
  • $\begingroup$ Not really a CS answer, so just commenting here: You could simply demonstrate that a .wav file is literally identical before compression and after decompression. But i think the CS answer you are looking for is an intuitive explanation for the theory behind lossless audio compression? $\endgroup$ – Tom Lubitz May 26 '17 at 20:07
12
$\begingroup$

Tell him to write out the integers between 1 and 100, inclusive. Ask him how it can be that your instruction was so much shorter than the list of numbers he wrote out. Did that brevity cause him to write out the wrong thing?

$\endgroup$
  • 3
    $\begingroup$ This is great. I might follow by saying that, to be lossless, it doesn't have to have all of the data. It just has to have a way to describe how to regenerate the exact data. If we can regenerate exactly the same data as the original, then we have not actually lost any information. Hence, "lossless". $\endgroup$ – Ben I. May 26 '17 at 3:51
2
$\begingroup$

You're explaining the wrong way - explain the opposite way. Take the original data, and write each bit twice, i.e. 0101 --> 00110011. Now the output is twice the size but still carries the exact same amount of information. Yes, n bits can represent 2^n unique values. But a specific value can be encoded in an infinite number of ways, some smaller than others. Maybe try referring him to capacity and to Kolmogorov complexity

$\endgroup$
1
$\begingroup$

Ask him to write a large matrix of floating point data into a text file with as many digits as there is precision. Then ask him to store the same data in a binary file format. Make note of the difference in file sizes.

Finally, ask him how it is possible to store the same matrix data in two files with drastically different storage footprints?

$\endgroup$
1
$\begingroup$

It's true that we're encoding a bit string $Y$ with some shorter bit string $X$, but we are not losing any information, because we're going to encode $X$ with some possibly longer bit string $Z$. On the average we won't gain anything, but our procedure works so that the bit strings that we typically see in practice get shorter during compression, and those that we do not see in practice get longer (but nobody cares about them).

$\endgroup$
0
$\begingroup$

A CD stores sounds as volume levels from -32768 to 32767. You need 16 bits for each volume level.

Instead of the volume level, store the difference from one sample to the next. Take a 440 Hz sound. The differences from one sample to the next are much smaller than the original levels and can be stored in less space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.