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?

Improve this question
$\endgroup$
3
  • 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
    Commented May 24, 2017 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
    Commented May 24, 2017 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
    Commented May 26, 2017 at 20:07

5 Answers 5

Reset to default
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?

Improve this answer
$\endgroup$
1
  • 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.
    Commented May 26, 2017 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

Improve this answer
$\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?

Improve this answer
$\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).

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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