A Continuity Theory for Lossless Source Coding over Networks

Abstract

A continuity theory of lossless source coding over networks is established and its implications are investigated. In the given model, source and side-information random variables X and Y have finite alphabets, and the input sequences are drawn i.i.d. according to a generic distribution P_(X,Y) on (X,Y). We consider traditional source coding, where all demands equal source random variables. We define a family of lossless source coding problems that includes prior example network source coding problems as special cases. We show that the lossless rate region R_L(P_(X,Y)) is inner semi-continuous in P_(X,Y). We further show that for a special type of networks called super-source networks, where there is a super source node v* that has access to (X,Y) and any other node with access to some source random variable X_i is directly connected to v*, R_L(P_(X,Y)) is also outer semi-continuous in P_(X,Y). Based on the continuity of super-source networks with respect to P_(X,Y), we conjecture that R_L(P_(X,Y)) is also outer semi-continuous and therefore continuous in P_(X,Y) for general networks.

Files

Additional details