Noisy Channel Compression

[tbird]

Hi, 1st time poster here.

I am interested in whether noisy channel is ever a consideration in the creation of compression algorithms, and if so then in what applications?

For example this recent paper at ICML considers a machine learning based compressor for the task of compressing data which will be stored in a noisy format - a binary symmetric channel (BSD).

Obviously a BSD is not that realistic, but they show that learning a compressor to handle both the compression and such a BSD is maybe better than using some standard compression like WebP and then LDPC (or some other error correcting code).

I doubt their method is that practical (neural nets have a high computational footprint), but I thought it was interesting nonetheless.

[Shelwien]

Well, it can be important for any kind of analog channel or storage (TLC+ SSD), since its common to use both compression and ECC there.
But I think normally compression and ECC are separate layers.

Also, any full-precision arithmetic coder can be combined with ECC easily enough (AC decoding can be used to produce data fitting to any given model),
so there's little point to consider higher-level compression algorithms, since error correction can be solved at the level of entropy coder.
But some formats (jpeg, mp3) do in fact provide an option to re-sync after data error.

Then, there're some compression algorithms based on steganography, which is kinda related.

[tbird]

Also, any full-precision arithmetic coder can be combined with ECC easily enough (AC decoding can be used to produce data fitting to any given model),
so there's little point to consider higher-level compression algorithms, since error correction can be solved at the level of entropy coder.

To make sure I understand this point - are you saying that if you had knowledge of the (possibly approximate) data-generating distribution and also knowledge of the ECC you wish to use, then you can simply combine these two to get a distribution you can encode the data according to (with an entropy coder like AC)?

Interesting. Although surely it could be better to incorporate some kind of error correcting process into the approximation of the data-generating distribution itself? Assuming we don't have access to the true data-generating distribution.

[Shelwien]

> then you can simply combine these two to get a distribution
> you can encode the data according to (with an entropy coder like AC)?

Yes. Or just encode compressor's output to add redundancy.
Here's an example that uses this approach to re-encode data
to specified alphabet: http://nishi.dreamhosters.com/u/marc_v1.rar
(like base64, but any alphabet).

So in case of ECC, for example, we can generate an alphabet containing
only codes with hamming distance >N, and thus detect N-bit errors.

> Interesting. Although surely it could be better to incorporate some kind of
> error correcting process into the approximation of the data-generating
> distribution itself?

It would be much more limited (and redundant) because of precision issues.
Also its not too easy to design good codecs even without ECC considerations,
so solutions like taking an existing codec (eg. lzma) and tweaking its entropy model
seem much more practical.

[tbird]

What do you mean by precision issues?

[Shelwien]

I presumed that we're taking an existing compression algorithm (like lzma or ppmd) and transparently replacing the entropy coder there.
In which case entropy coder would still be called to encode/decode individual symbols (bits or at most bytes)
without an option for combining them into composite symbols, because that'd require a totally different compression algorithm -
normally its only possible to start decoding the next symbol once current one is already known.
Which means error correction on the level of individual symbols, while having an extra AC layer would let us
automatically combine them.