Search

We study variable-length feedback (VLF) codes with noiseless feedback for discrete memoryless channels. We present a novel non-asymptotic bound, which analyzes the average error probability and average decoding time of our modified Yamamoto--Itoh scheme. We then optimize the parameters of our code in the asymptotic regime where the average error probability $\epsilon$ remains a constant as the average decoding time $N$ approaches infinity. Our second-order achievability bound is an improvement of Polyanskiy et al.'s (2011) achievability bound. We also universalize our code by employing the empirical mutual information in our decoding metric and derive a second-order achievability bound for universal VLF codes. Our results for both VLF and universal VLF codes are extended to the additive white Gaussian noise channel with an average power constraint. The former yields an improvement over Truong and Tan's (2017) achievability bound. The proof of our results for universal VLF codes uses a refined version of the method of types and an asymptotic expansion from the nonlinear renewal theory literature., Comment: Submitted to ISIT 2024, 14 pages

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

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

We study the best-arm identification problem in sparse linear bandits under the fixed-budget setting. In sparse linear bandits, the unknown feature vector $\theta^*$ may be of large dimension $d$, but only a few, say $s \ll d$ of these features have non-zero values. We design a two-phase algorithm, Lasso and Optimal-Design- (Lasso-OD) based linear best-arm identification. The first phase of Lasso-OD leverages the sparsity of the feature vector by applying the thresholded Lasso introduced by Zhou (2009), which estimates the support of $\theta^*$ correctly with high probability using rewards from the selected arms and a judicious choice of the design matrix. The second phase of Lasso-OD applies the OD-LinBAI algorithm by Yang and Tan (2022) on that estimated support. We derive a non-asymptotic upper bound on the error probability of Lasso-OD by carefully choosing hyperparameters (such as Lasso's regularization parameter) and balancing the error probabilities of both phases. For fixed sparsity $s$ and budget $T$, the exponent in the error probability of Lasso-OD depends on $s$ but not on the dimension $d$, yielding a significant performance improvement for sparse and high-dimensional linear bandits. Furthermore, we show that Lasso-OD is almost minimax optimal in the exponent. Finally, we provide numerical examples to demonstrate the significant performance improvement over the existing algorithms for non-sparse linear bandits such as OD-LinBAI, BayesGap, Peace, LinearExploration, and GSE., Comment: 28 pages, Submitted to TMLR

We study variable-length codes for point-to-point discrete memoryless channels with noiseless unlimited-rate feedback that occurs in $L$ bursts. We term such codes variable-length bursty-feedback (VLBF) codes. Unlike classical codes with feedback after each transmitted code symbol, bursty feedback fits better with protocols that employ sparse feedback after a packet is sent and also with half-duplex end devices that cannot transmit and listen to the channel at the same time. We present a novel non-asymptotic achievability bound for VLBF codes with $L$ bursts of feedback over any discrete memoryless channel. We numerically evaluate the bound over the binary symmetric channel (BSC). We perform optimization over the time instances at which feedback occurs for both our own bound and Yavas et al.'s non-asymptotic achievability bound for variable-length stop-feedback (VLSF) codes, where only a single bit is sent at each feedback instance. Our results demonstrate the advantages of richer feedback: VLBF codes significantly outperform VLSF codes at short blocklengths, especially as the error probability $\epsilon$ decreases. Remarkably, for BSC(0.11) and error probability $10^{-10}$, our VLBF code with $L=5$ and expected decoding time $N\leq 400$ outperforms the achievability bound given by Polyanskiy et al. for VLSF codes with $L=\infty$, and our VLBF code with $L=3$., Comment: Presented at ISIT 2023

In this paper, we are interested in the performance of a variable-length stop-feedback (VLSF) code with m optimal decoding times for the binary-input additive white Gaussian noise channel. We first develop tight approximations to the tail probability of length-n cumulative information density. Building on the work of Yavas et al., for a given information density threshold, we formulate the integer program of minimizing the upper bound on average blocklength over all decoding times subject to the average error probability, minimum gap and integer constraints. Eventually, minimization of locally optimal upper bounds over all thresholds yields the globally minimum upper bound and the above method is called the two-step minimization. Relaxing to allow positive real-valued decoding times activates the gap constraint. We develop gap-constrained sequential differential optimization (SDO) procedure to find the optimal, gap-constrained, real-valued decoding times. In the error regime of practical interest, Polyanskiy's scheme of stopping at zero does not help. In this region, the achievability bounds estimated by the two-step minimization and gap-constrained SDO show that Polyanskiy’s achievability bound for VLSF codes can be approached with a small number of decoding times.

This paper focuses on the numerical evaluation of the maximal achievable rate of variable-length stop-feedback (VLSF) codes with m decoding times at a given message size and error probability for binary-input additive white Gaussian noise channel, binary symmetric channel, and binary erasure channel (BEC). Leveraging the Edgeworth and Petrov expansions, we develop tight approximations to the tail probability of length-n cumulative information density that are accurate for any blocklength n. We reduce Yavas et al.'s non-asymptotic achievability bound on VLSF codes with m decoding times to an integer program of minimizing the upper bound on the average blocklength subject to the average error probability, minimum gap, and integer constraints. We develop two distinct methods to solve this program. Numerical evaluations show that Polyanskiy's achievability bound for VLSF codes, which assumes m = ∞, can be approached with a relatively small m in all of the three channels. For BEC, we consider systematic transmission followed by random linear fountain coding. This allows us to obtain a new achievability bound stronger than a previously known bound and new VLSF codes whose rate further outperforms Polyanskiy's bound.

This paper studies the third-order characteristic of nonsingular discrete memoryless channels and the Gaussian channel with a maximal power constraint. The third-order term in our expansions employs a new quantity here called the \emph{channel skewness}, which affects the approximation accuracy more significantly as the error probability decreases. For the Gaussian channel, evaluating Shannon's (1959) random coding and sphere-packing bounds in the central limit theorem (CLT) regime enables exact computation of the channel skewness. For discrete memoryless channels, this work generalizes Moulin's (2017) bounds on the asymptotic expansion of the maximum achievable message set size for nonsingular channels from the CLT regime to include the moderate deviations (MD) regime, thereby refining Altu\u{g} and Wagner's (2014) MD result. For an example binary symmetric channel and most practically important $(n, \epsilon)$ pairs, including $n \in [100, 500]$ and $\epsilon \in [10^{-10}, 10^{-1}]$, an approximation up to the channel skewness is the most accurate among several expansions in the literature. A derivation of the third-order term in the type-II error exponent of binary hypothesis testing in the MD regime is also included; the resulting third-order term is similar to the channel skewness., Comment: Presented at ISIT 2022. Submitted to IT Transactions in January, 2023

In this paper, we are interested in the performance of a variable-length stop-feedback (VLSF) code with $m$ optimal decoding times for the binary-input additive white Gaussian noise channel. We first develop tight approximations on the tail probability of length-$n$ cumulative information density. Building on the work of Yavas \emph{et al.}, for a given information density threshold, we formulate the integer program of minimizing the upper bound on average blocklength over all decoding times subject to the average error probability, minimum gap and integer constraints. Eventually, minimization of locally minimum upper bounds over all thresholds will yield the globally minimum upper bound and this is called the two-step minimization. For the integer program, we present a greedy algorithm that yields possibly suboptimal integer decoding times. By allowing a positive real-valued decoding time, we develop the gap-constrained sequential differential optimization (SDO) procedure that sequentially produces the optimal, real-valued decoding times. We identify the error regime in which Polyanskiy's scheme of stopping at zero does not improve the achievability bound. In this error regime, the two-step minimization with the gap-constrained SDO shows that a finite $m$ suffices to attain Polyanskiy's bound for VLSF codes with $m = \infty$., Comment: 8 pages, 4 figures; fixed some errors in v1 and added some new results; a short version of this preprint was submitted to ISIT 2022

Incremental redundancy with ACK/NACK feedback produces a variable-length stop-feedback (VLSF) code constrained to have $m$ decoding times, with an ACK/NACK feedback to the transmitter at each decoding time. This paper focuses on the numerical evaluation of the maximal achievable rate of random VLSF codes as a function of $m$ for the binary-input additive white Gaussian noise channel, binary symmetric channel, and binary erasure channel (BEC). Leveraging Edgeworth and Petrov expansions, we develop tight approximations to the tail probability of length-$n$ cumulative information density that are accurate for any blocklength $n$. We reduce Yavas et al.'s non-asymptotic achievability bound on VLSF codes with $m$ decoding times to an integer program of minimizing the upper bound on the average blocklength subject to the average error probability, minimum gap, and integer constraints. We develop two distinct methods to solve this program. Numerical evaluations show that Polyanskiy's achievability bound for VLSF codes, which assumes $m = \infty$, can be approached with a small $m$ for all three channels. For BEC, we consider systematic transmission followed by random linear fountain coding. This allows us to obtain a new achievability bound stronger than a previous bound and new VLSF codes whose rate further outperforms Polyanskiy's bound., Comment: 19 pages, 12 figures; submitted to IEEE Transactions on Communications. An earlier version of this work was published at ISIT 2022. Comments are welcome!

This paper investigates variable-length feedback codes for discrete memoryless channels in point-to-point, multiple access, and random access communication. The proposed nested code employs L decoding times n₁,n₂,…,n_L for the point-to-point and multiple access channels and KL decoding times {n_(k,ℓ):1 ≤ k ≤ K,1 ≤ ℓ ≤ L} for the random access channel with at most K active transmitters; in the latter case, decoding times n_(k,ℓ), 1 ≤ ℓ ≤ L are reserved for decoding in the scenario where the decoder believes that the number of active transmitters is k. The code has a nested structure, i.e., codewords used to decode messages from k active transmitters are prefix of codewords used to decode messages from k+1 active transmitters. The code employs single-bit, scheduled feedback from the receiver to the transmitters at each potential decoding time to inform the transmitters whether or not it is able to decode. Transmitters cease transmission, thereby truncating their codewords, when no further transmissions are required by the decoder. The choice of decoding times is optimized to minimize the expected decoding time subject to an error probability constraint, and second order achievability bounds are derived.

This paper investigates variable-length stop-feedback codes for memoryless channels in point-to-point, multiple access, and random access communication scenarios. The proposed codes employ $L$ decoding times $n_1, n_2, \dots, n_L$ for the point-to-point and multiple access channels and $KL + 1$ decoding times for the random access channel with at most $K$ active transmitters. In the point-to-point and multiple access channels, the decoder uses the observed channel outputs to decide whether to decode at each of the allowed decoding times $n_1, \dots, n_L$, at each time telling the encoder whether or not to stop transmitting using a single bit of feedback. In the random access scenario, the decoder estimates the number of active transmitters at time $n_0$ and then chooses among decoding times $n_{k, 1}, \dots, n_{k, L}$ if it believes that there are $k$ active transmitters. In all cases, the choice of allowed decoding times is part of the code design; given fixed value $L$, allowed decoding times are chosen to minimize the expected decoding time for a given codebook size and target average error probability. The number $L$ in each scenario is assumed to be constant even when the blocklength is allowed to grow; the resulting code therefore requires only sparse feedback. The central results are asymptotic approximations of achievable rates as a function of the error probability, the expected decoding time, and the number of decoding times. A converse for variable-length stop-feedback codes with uniformly-spaced decoding times is included for the point-to-point channel., Comment: 29 Pages. Presented at ISIT 2021. Accepted for publication at IEEE Transactions on Information Theory Dec. 2023

This paper presents finite-blocklength achievabil- ity bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter’s rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to ½ log n/n + O(1/n) bits per channel use. The result then extends to a RAC model in which neither the encoders nor the decoder knows which of K possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time n t that depends on the decoder’s estimate t of the number of active transmitters k. Single-bit feedback from the decoder to all encoders at each potential decoding time n_i, i ≤ t, informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation.

This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability., Comment: 14 pages, Accepted by the IEEE Transactions on Information Theory

This paper presents finite-blocklength achievability bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter's rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to $\frac12\frac{\log n}{n}+O \left(\frac 1 n \right)$ bits per channel use. The result then extends to a RAC model in which neither the encoders nor the decoder knows which of $K$ possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time $n_t$ that depends on the decoder's estimate $t$ of the number of active transmitters $k$. Single-bit feedback from the decoder to all encoders at each potential decoding time $n_i$, $i \leq t$, informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation., Comment: 27 pages, IEEE Transactions on Information Theory, ISIT 2020

Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. Inspired by the model recently introduced for the Multiple Access Channel (MAC) with a fixed, known number of transmitters by Polyanskiy, we assume that the channel is invariant to permutations on its inputs, and that all active transmitters employ identical encoders. Unlike Polyanskiy, we consider a scenario in which neither the transmitters nor the receiver know which or how many transmitters are active. We refer to this agnostic communication setup as the Random Access Channel, or RAC. Limited feedback is used to ensure that the collection of active transmitters remains fixed during each epoch. The decoder is tasked with determining from the channel output the number of active transmitters (k) and their messages but not which transmitter sent which message. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require 2^k - 1 simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion.

Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. As in the model recently introduced by Polyanskiy for the Multiple Access Channel (MAC) with a fixed, known number of transmitters, the channel is assumed to be invariant to permutations on its inputs, and all active transmitters employ identical encoders. Unlike the Polyanskiy model, in the proposed scenario, neither the transmitters nor the receiver knows which transmitters are active. We refer to this agnostic communication setup as the Random Access Channel (RAC). Scheduled feedback of a finite number of bits is used to synchronize the transmitters. The decoder is tasked with determining from the channel output the number of active transmitters, $k$, and their messages but not which transmitter sent which message. The decoding procedure occurs at a time $n_t$ depending on the decoder's estimate, $t$, of the number of active transmitters, $k$, thereby achieving a rate that varies with the number of active transmitters. Single-bit feedback at each time $n_i, i \leq t$, enables all transmitters to determine the end of one coding epoch and the start of the next. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require $2^k - 1$ simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion., Comment: Presented at ISIT 2018. IEEE Transactions on Information Theory