This thesis deals with the Shannon-theoretic fundamental limits of channel coding for single-user channels with memory and feedback and for multi-user channels with side information. We first consider the feedback capacity of a class of symmetric channels with memory modelled as nite-state Markov channels. The symmetry yields the existence of a hidden Markov noise process that facilitates the channel description as a function of input and noise, where the function satisfies a desirable invertibility property. We show that feedback does not increase capacity for such class of finite-state channels and that both their non-feedback and feedback capacities are achieved by an independent and uniformly distributed input. As a result, the capacity is given as a difference of output and noise entropy rates, where the output is also a hidden Markov process; hence, capacity can be approximated via well known algorithms. We then consider the memoryless state-dependent multiple-access channel (MAC) where the encoders and the decoder are provided with various degrees of asymmetric noisy channel state information (CSI). For the case where the encoders observe causal, asymmetric noisy CSI and the decoder observes complete CSI, inner and outer bounds to the capacity region, which are tight for the sum-rate capacity, are provided. Next, single-letter characterizations for the channel capacity regions under each of the following settings are established: (a) the CSI at the encoders are non-causal and asymmetric deterministic functions of the CSI at the decoder (b) the encoders observe asymmetric noisy CSI with asymmetric delays and the decoder observes complete CSI; (c) a degraded message set scenario with asymmetric noisy CSI at the encoders and complete and/or noisy CSI at the decoder. Finally, we consider the above state-dependent MAC model and identify what is required to be provided to the receiver in order to get a tight converse for the sum-rate capacity. Inspired by the coding schemes of the lossless CEO problem as well as of a recently proposed achievable region, we provide an inner bound which demonstrates the rate required to transmit this information to the receiver. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2013-07-12 13:48:59.849

This thesis contributes toward understanding fundamental limits of multi-user fading channels and random wireless networks. Specifically, considering different samples of channel gains corresponding to different users/nodes in a multi-user wireless system, the maximum number of channel gains supporting a minimum rate is asymptotically obtained. First, the user capacity of fading multi-user channels with minimum rates is analyzed. Three commonly used fading models, namely, Rayleigh, Rician and Nakagami are considered. For broadcast channels, a power allocation scheme is proposed to maximize the number of active receivers, for each of which, a minimum rate Rmin>0 can be achieved. Under the assumption of independent Rayleigh fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be arbitrarily close to ln(P.ln(n))/Rmin with probability approaching one, where P is the total transmit power. The results obtained for Rayleigh fading are extended to the cases of Rician and Nakagami fading models. Under the assumption of independent Rician fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be equal to ln(2P.ln(n))/Rmin with probability approaching one. For broadcast channels with Nakagami fading, the maximum number of active receivers is shown to be equal to ln(ω/μ.P.ln(n))/Rmin with probability approaching one, where ω and μ are the Nakagami distribution parameters. A by-product of the results is to also provide a power allocation strategy that maximizes the total throughput subject to the rate constraints. In multiple-access channels, the maximum number of simultaneous active transmitters (i.e. user capacity) is obtained in the many user case in which a minimum rate must be maintained for all active users. The results are presented in the form of scaling laws as the number of transmitters increases. It is shown that for all three fading distributions, the user capacity scales double logarithmically in the number of users and differs only by constants depending on the distributions. We also show that a scheduling policy that maximizes the number of simultaneous active transmitters can be implemented in a distributed fashion. Second, the maximum number of active links supporting a minimum rate is asymptotically obtained in a wireless network with an arbitrary topology. It is assumed that each source-destination pair communicates through a fading channel and destinations receive interference from all other active sources. Two scenarios are considered: 1) Small networks with multi-path fading, 2) Large Random networks with multi-path fading and path loss. In the first case, under the assumption of independent Rayleigh fading channels for different source-destination pairs, it is shown that the optimal number of active links is of the order log(N) with probability approaching one as the total number of nodes, N, tends to infinity. The achievable total throughput also scales logarithmically with the total number of links/nodes in the network. In the second case, a two-dimensional large wireless network is considered and it is assumed that nodes are Poisson distributed with a finite intensity. Under the assumption of independent multi-path fading for different source-destination pairs, it is shown that the optimal number of active links is of the order N with probability approaching one. As a result, the achievable per-node throughput obtained by multi-hop routing scales with Θ(1/√N).

This thesis contributes toward understanding fundamental limits of multi-user fading channels and random wireless networks. Specifically, considering different samples of channel gains corresponding to different users/nodes in a multi-user wireless system, the maximum number of channel gains supporting a minimum rate is asymptotically obtained. First, the user capacity of fading multi-user channels with minimum rates is analyzed. Three commonly used fading models, namely, Rayleigh, Rician and Nakagami are considered. For broadcast channels, a power allocation scheme is proposed to maximize the number of active receivers, for each of which, a minimum rate Rmin>0 can be achieved. Under the assumption of independent Rayleigh fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be arbitrarily close to ln(P.ln(n))/Rmin with probability approaching one, where P is the total transmit power. The results obtained for Rayleigh fading are extended to the cases of Rician and Nakagami fading models. Under the assumption of independent Rician fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be equal to ln(2P.ln(n))/Rmin with probability approaching one. For broadcast channels with Nakagami fading, the maximum number of active receivers is shown to be equal to ln(ω/μ.P.ln(n))/Rmin with probability approaching one, where ω and μ are the Nakagami distribution parameters. A by-product of the results is to also provide a power allocation strategy that maximizes the total throughput subject to the rate constraints. In multiple-access channels, the maximum number of simultaneous active transmitters (i.e. user capacity) is obtained in the many user case in which a minimum rate must be maintained for all active users. The results are presented in the form of scaling laws as the number of transmitters increases. It is shown that for all three fading distributions, the user capacity scales double logarithmically in the number of users and differs only by constants depending on the distributions. We also show that a scheduling policy that maximizes the number of simultaneous active transmitters can be implemented in a distributed fashion. Second, the maximum number of active links supporting a minimum rate is asymptotically obtained in a wireless network with an arbitrary topology. It is assumed that each source-destination pair communicates through a fading channel and destinations receive interference from all other active sources. Two scenarios are considered: 1) Small networks with multi-path fading, 2) Large Random networks with multi-path fading and path loss. In the first case, under the assumption of independent Rayleigh fading channels for different source-destination pairs, it is shown that the optimal number of active links is of the order log(N) with probability approaching one as the total number of nodes, N, tends to infinity. The achievable total throughput also scales logarithmically with the total number of links/nodes in the network. In the second case, a two-dimensional large wireless network is considered and it is assumed that nodes are Poisson distributed with a finite intensity. Under the assumption of independent multi-path fading for different source-destination pairs, it is shown that the optimal number of active links is of the order N with probability approaching one. As a result, the achievable per-node throughput obtained by multi-hop routing scales with Θ(1/√N).