Lossless and near-lossless source coding for multiple access networks

A multiple access source code (MASC) is a source code designed for the following network configuration: a pair of correlated information sequences {X_i}_i=1^∞ and {Y_i}_i=1^∞ is drawn independent and identically distributed (i.i.d.) according to joint probability mass function (p.m.f.) p(x,y); the encoder for each source operates without knowledge of the other source; the decoder jointly decodes the encoded bit streams from both sources. The work of Slepian and Wolf describes all rates achievable by MASCs of infinite coding dimension (n→∞) and asymptotically negligible error probabilities (P_e⁽ⁿ⁾→0). In this paper, we consider the properties of optimal instantaneous MASCs with finite coding dimension (n<∞) and both lossless (P_e⁽ⁿ⁾=0) and nearlossless (P_e⁽ⁿ⁾→0) performance. The interest in near-lossless codes is inspired by the discontinuity in the limiting rate region at P_e⁽ⁿ⁾=0 and the resulting performance benefits achievable by using near-lossless MASCs as entropy codes within lossy MASCs. Our central results include generalizations of Huffman and arithmetic codes to the MASC framework for arbitrary p(x,y), n, and P_e⁽ⁿ⁾ and polynomial-time design algorithms that approximate these optimal solutions.