Zero-error communication over adder MAC
share
Adder MAC is a simple noiseless multiple-access channel (MAC), where if users send messages X_1,...,X_h∈{0,1}^n, then the receiver receives Y = X_1+...+X_h with addition over Z. Communication over the noiseless adder MAC has been studied for more than fifty years. There are two models of particular interest: uniquely decodable code tuples, and B_h-codes. In spite of the similarities between these two models, lower bounds and upper bounds of the optimal sum rate of uniquely decodable code tuple asymptotically match as number of users goes to infinity, while there is a gap of factor two between lower bounds and upper bounds of the optimal rate of B_h-codes. The best currently known B_h-codes for h> 3 are constructed using random coding. In this work, we study variants of the random coding method and related problems, in hope of achieving B_h-codes with better rate. Our contribution include the following. (1) We prove that changing the underlying distribution used in random coding cannot improve the rate. (2) We determine the rate of a list-decoding version of B_h-codes achieved by the random coding method. (3) We study several related problems about Rényi entropy.
READ FULL TEXT