Non-Asymptotic Analysis of Single-Receiver Channels with Limited Feedback

Citation

Yavas, Recep Can (2023) Non-Asymptotic Analysis of Single-Receiver Channels with Limited Feedback. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/a9e9-he45. https://resolver.caltech.edu/CaltechTHESIS:06012023-003751035

Abstract

Emerging Internet of Things, machine-type communication, and ultra-reliable low-latency communication in 5G demand codes that operate at short blocklengths, have low error probability and low energy consumption, and can handle the random activity of a large number of communicating devices. Since many of the applications have a single central device, e.g., a base station, that resolves the communication and a varying number of users, these requirements on the code design motivate interest in the non-asymptotic analysis of codes in a variety of single-receiver channels. This thesis investigates three channel coding problems with the goals of understanding the fundamental limits of channel coding under stringent requirements on reliability, delay, and power, and proposes novel coding architectures that employ constrained feedback to attain those limits. In the first part, we consider point-to-point channels without feedback, and analyze the non-asymptotic limits in the moderate deviations regime in probability theory. The moderate deviations regime is suitable for accurately approximating the maximum achievable coding rate in the operational regimes of practical interest because it simultaneously considers high rates and low error probabilities. We propose a new quantity, channel skewness, which governs the fundamental limit at short blocklengths and low error probabilities. Our approximation is the tightest among the state-of-the-art approximations for most error probability and latency constraints of interest. In the second part, we investigate rateless channel coding with limited feedback. Here, rateless means that decoding can occur at multiple decoding times. In our code design, feedback is limited both in frequency and content; it is sparse, meaning that it is available only at a few instants throughout the communication epoch; and it is stop-feedback, meaning that the receiver informs the transmitters only about whether decoding has occurred rather than what symbols it has received. Our results demonstrate that sporadically sending a few bits is almost as efficient as sending feedback at every time instant. In the third part, we focus on rateless random access channel codes, where the number of active transmitters is unknown to both the transmitters and the receiver. Our rateless code design that reserves a decoding time for each possible number of active transmitters achieves the same first two terms in the asymptotic expansion of the achievable rate as codes where the transmitter activity is known a priori. This means that, remarkably, the random transmitter activity has almost no effect on achievable rates.

To obtain tight channel coding bounds, we analyze some non-asymptotic and asymptotic state-of-the-art bounds on the probability of the sum of independent and identical random variables, whose applications extend to source coding, hypothesis testing, and many others. In the scenarios where these tools are not directly applicable such as for the Gaussian channel, we propose new techniques to overcome that difficulty.

Thesis Files