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.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17014 |
| _version_ | 1826191215364669440 |
|---|---|
| author | Ray, Siddharth, 1979- |
| author2 | Muriel Médard and Jinane Abounadi. |
| author_facet | Muriel Médard and Jinane Abounadi. Ray, Siddharth, 1979- |
| author_sort | Ray, Siddharth, 1979- |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. |
| first_indexed | 2024-09-23T08:52:25Z |
| format | Thesis |
| id | mit-1721.1/17014 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:52:25Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/170142019-04-10T12:19:18Z Multiple access networks over finite fields : optimality of separation, randomness and linearity Ray, Siddharth, 1979- Muriel Médard and Jinane Abounadi. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. 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. 2005-05-19T15:39:27Z 2005-05-19T15:39:27Z 2003 2003 Thesis http://hdl.handle.net/1721.1/17014 54456549 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 95 leaves 634632 bytes 634358 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Ray, Siddharth, 1979- Multiple access networks over finite fields : optimality of separation, randomness and linearity |
| title | Multiple access networks over finite fields : optimality of separation, randomness and linearity |
| title_full | Multiple access networks over finite fields : optimality of separation, randomness and linearity |
| title_fullStr | Multiple access networks over finite fields : optimality of separation, randomness and linearity |
| title_full_unstemmed | Multiple access networks over finite fields : optimality of separation, randomness and linearity |
| title_short | Multiple access networks over finite fields : optimality of separation, randomness and linearity |
| title_sort | multiple access networks over finite fields optimality of separation randomness and linearity |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/17014 |
| work_keys_str_mv | AT raysiddharth1979 multipleaccessnetworksoverfinitefieldsoptimalityofseparationrandomnessandlinearity |