Multiple access networks over finite fields : optimality of separation, randomness and linearity

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.Includes bibliographical references (leaves 93-95).This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.We consider a time-slotted multiple access noisy as well as noise-free channel in which the received, transmit and noise alphabets belong to a finite field. We show that source-channel separation holds when the additive noise is independent of inputs. However, for input-dependent noise, separation may not hold. For channels over the binary field, we derive the expression for the probability of source-channel separation failing. We compute this probability to be 1/4 when the noise parameters are picked independently and uniformly. For binary channels, we derive an upper bound of 0.0776 bit for the maximum loss in sum rate due to separate source-channel coding when separation fails. We prove that the bound is very tight by showing that it is accurate to the second decimal place. We derive the capacity region and the maximum code rate for the noisy as well as noise-free channel where, code rate is defined as the ratio of the information symbols recovered at the receiver to the symbols sent by the transmitters in a slot duration. Code rate measures the overhead in transmitting in a slot under multiple access interference. We show for both noisy and noise-free channels that capacity grows logarithmically with the size of the field but the code rate is invariant with field size. For the noise-free channel, codes achieve maximum code rate if and only if they achieve capacity and add no redundancy to the shorter of the two information codewords. For the noise-free multiple access channel, we consider the cases when both transmitters always transmit in a slot, as well as when each transmitter transmits in a bursty fashion according to a Bernoulli process. For the case when both transmitters always transmit, we propose a systematic code construction and show that it achieves the maximum code rate and capacity. We also propose a systematic random code construction and show that it achieves the maximum code rate and capacity with probability tending to 1 exponentially with codeword length and field size. This is a strong coding theorem for this channel. For the case when transmitters transmit according to a Bernoulli process, we propose a coding scheme to maximize the expected code rate. We show that maximum code rate is achieved by adding redundancy at the less bursty transmitter and not adding any redundancy at the more bursty transmitter. For the noisy channel, we obtain the error exponents and hence, the expression for average probability of error when a random code is used for communicating over the channel.by Siddharth Ray.S.M