Binary erasure multiple descriptions: Worst-case distortion

We consider a binary erasure version of the n-channel multiple descriptions problem with no excess rate and no distortion for every k out of n descriptions, i.e., any subset of k messages has a total rate of one and allows for perfect reconstruction of the source. Using a worst-case distortion criterion, we present an explicit coding scheme based on Reed-Solomon codes and, for any n and k, characterize its achievable distortion region when m < k messages are received at the decoder. We prove that this scheme is Pareto optimal in the achievable distortions for all n and k for any number of received messages at the decoder, and is optimal for all n and k when a single message is received. We also provide optimality results for a certain range of values of n and k.