Multi-level Source Coding

A set of information sources (e.g., bitstreams) are jointly encoded by K encoders. There are N decoders, each of which has access to a non-empty subset of the encoded streams. Each decoder is assigned with a (ordered) level, which depends on the subset of compressed streams it has access to. The decoder at level m is interested in recovering a subset of the original information sources including streams labeled by 1,2,...,m. The goal is find admissible rate region, the minimum number of bits each encoder needs for compression such that the decoders can use the compressed streams for decoding. 

This is motivated by asymmetric (unequal) reliabilities of the disks in distributed disk storage application. Moreover, packet erasure applications, such as Internet, in which the erasure probabilities for the sub-packets may be unequal because the paths over which they are sent may have different reliabilities, is a special case of this  problem. 

We obtain a single letter characterization of the complete achievable rate region for the 3-description problem. In doing so, we show that it is necessary to jointly encode independent sources (i.e., similar to network coding), and that linear codes are optimal for this problem.

Multi-level Source Coding