Lossless and lossy broadcast system source codes: theoretical limits, optimal design, and empirical performance

Broadcast systems are a class of networks where one system node (transmitter) simultaneously sends both common and independent, information to multiple nodes (receivers) in the system. Compressing the messages transmitted in such systems using traditional (single-transmitter, single-receiver) techniques requires use of a collection of independent source codes, one for each message sent through the system. The result of this approach is a system with multiple independent encoders at the transmitter and multiple independent decoders at each receiver. An alternative approach is to design a single joint encoder at the transmitter and a single joint decoder at each receiver. We call the resulting code a "broadcast system source code". This paper treats the theory and practice of optimal lossless and lossy (fixed- and variable-rate) broadcast system source codes. The results given include: theoretical limits for lossless source code performance on broadcast systems; an optimal lossless source code design algorithm; an optimal lossy source code design algorithm that generalizes the generalized Lloyd algorithm to broadcast systems; and experimental results for fixed- and variable-rate code performance in a two-receiver broadcast system.