Some data are more important than others

This thesis is comprised of two parts. Both parts study informationtheoretic aspects of joint transmission of data of different levels of sensitivity. The more sensitive data is better protected than the less sensitive data. In the first part the data streams have different robustness criteria with respect to variations of the underlying channel model, and in the second part, the data streams have different decoding error requirements. In the first part, we establish the deterministic-code capacity region of a network with one transmitter and two receivers: an “ordinary receiver” and a “robust receiver.” The channel to the ordinary receiver is a given (known) discrete memoryless channel, whereas the channel to the robust receiver is an arbitrarily varying channel. Both receivers are required to decode the “common message” (the more sensitive data), whereas only the ordinary receiver is required to decode the “private message” (the less sensitive data). In the second part, two independent data streams are to be transmitted over a noisy discrete memoryless channel: the “zero-error stream” (the more sensitive data) and the “rare-error stream” (the less sensitive data). Errors are tolerated only in the rare-error stream, provided that their probability tends to zero as the blocklength tends to infinity. If the encoder has access to a noiseless feedback link from the output of the channel, the rate of the zero-error stream cannot, of course, exceed the channel’s zero-error feedback capacity, and nor can the sum of the streams’ rates exceed the channel’s Shannon capacity. Using a suitable feedback coding scheme, these necessary conditions are shown to characterize all the achievable rate pairs and thus the multiplexing capacity region with feedback. Planning for the worst—as is needed to achieve zero-error communication—and planning for the true channel— as is needed to communicate near the Shannon limit—are thus not incompatible. If the encoder has no feedback, computing the multiplexing capacity region is at least as hard as computing the zero-error capacity of a discrete memoryless channel. We present some outer bounds that show that feedback may be beneficial for the multiplexing problem even on channels on which it does not increase the zero-error capacity.