Asymptotic analysis for multi-user channels

Abstract

This dissertation studies the asymptotics of two multi-user channel problems. The fingerprinting channel is associated with digital fingerprinting, which is an emerging technology to protect multimedia from unauthorized redistribution. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. The multiple access channel (MAC) is a classical problem in the field of network information theory. Multiple senders cooperate with one another to maximize their rates of communication to a single receiver. We address the problem of asymptotic analysis when the size of the problem goes to infinity.

The fundamental metric of measuring the detection capability of a fingerprinting system is capacity. It has recently been derived as the limit value of a sequence of maximin games with mutual information as their payoff functions. However, these games generally do not admit saddle-point solutions and are very hard to solve. Here under a modified version of the combined digit model proposed by Skoric et al., we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution.

For fingerprinting capacity games with k pirates, we provide capacities along with optimal strategies for both players of the game when k is small. For large k, we show that capacity is asymptotic to A/k^2 where the constant A is specified as the maximin value of a continuous functional game. Saddle-point solutions to the game are obtained using methods of variational calculus.

For multiple access channels we study the maximum achievable rate region for a given blocklength n and a desired error probability epsilon. The inner region for the discrete memoryless MAC is approximated by a single-lettered expression I-(1/sqrt(n))*Q_inv(V,epsilon) where I is associated with the capacity pentagon bounds by Ahlswede and Liao, V is the MAC dispersion matrix, and Q_inv is the inverse complementary multivariate Gaussian cumulative distribution region. For outer regions, we provide general converse bounds for both average error probability and maximal error probability criteria.