Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-038 | 15th March 2020 04:31

Error Correcting Codes for Uncompressed Messages

RSS-Feed




TR20-038
Authors: Ofer Grossman, Justin Holmgren
Publication: 22nd March 2020 10:59
Downloads: 1454
Keywords: 


Abstract:

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We show that in this setting, it is sub-optimal to use standard error correction. We consider a model where there is a set of “valid messages” which the sender may send that may not be efficiently compressible, but where it is possible for the receiver to recognize valid messages. In this model, we construct a (probabilistic) encoding procedure that achieves better tradeoffs between data rates and error-resilience (compared to just applying a standard error correcting code).

Additionally, our techniques yield improved efficiently decodable (probabilistic) codes for fully compressed messages (the standard setting where the set of valid messages is all binary strings) in the high-rate regime.



ISSN 1433-8092 | Imprint