Locally decodable source coding

Source coding is accomplished via the mapping of consecutive source symbols (blocks) into code blocks of fixed or variable length. The fundamental limits in source coding introduces a tradeoff between the rate of compression and the fidelity of the recovery. However, in practical communication systems many issues such as computational complexity, memory capacity, and memory access requirements must be considered. In conventional source coding, in order to retrieve one coordinate of the source sequence, accessing all the encoded coordinates are required. In other words, querying all of the memory cells is necessary. We study a class of codes for which the decoder is local. We introduce locally decodable source coding (LDSC), in which the decoder need not to read the entire encoded coordinates and only a few queries suffice to retrieve a given source coordinate. Both cases of having a constant number of queries and also a scaling number of queries with the source block length are studied. Also, both lossless and lossy source coding are considered. We show that with constant number of queries, the rate of (almost) lossless source coding is one, meaning that no compression is possible. We also show that with logarithmic number of queries in block length, one can achieve Shannon entropy rate. Moreover, we provide achievability bound on the rate of lossy source coding with both constant and scaling number of queries.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Makhdoumi, Ali (Makhdoumi Kakhaki)

Advisor dc:contributor.advisor

• Muriel Médard and Yury Polyanskiy.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/82403

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/82403