We study reliable communication over finite-state channels (FSCs) using Reed--Muller (RM) codes. Building on recent symmetry-based analyses for memoryless channels, we show that a sequence of binary RM codes (with some random scrambling) can achieve the symmetric capacity (or uniform-input information rate) of a binary-input indecomposable FSC. Our approach has three components. First, we establish a capacity-via-symmetry theorem for doubly-transitive group codes on discrete memoryless channels (DMCs) with non-binary inputs, under some symmetry and puncturing conditions. Then, we reduce a binary-input FSC to an almost memoryless non-binary channel by grouping adjacent input bits into blocks and interleaving non-binary codes onto the channel. Finally, we show that the interleaved non-binary codes can be constructed from a single binary RM code.

Pre-trained transformers exhibit the capability of adapting to new tasks through in-context learning (ICL), where they efficiently utilize a limited set of prompts without explicit model optimization. The canonical communication problem of estimating transmitted symbols from received observations can be modeled as an in-context learning problem: Received observations are a noisy function of transmitted symbols, and this function can be represented by an unknown parameter whose statistics depend on an unknown latent context. This problem, which we term in-context estimation (ICE), has significantly greater complexity than the extensively studied linear regression problem. The optimal solution to the ICE problem is a non-linear function of the underlying context. In this paper, we prove that, for a subclass of such problems, a single-layer softmax attention transformer (SAT) computes the optimal solution of the above estimation problem in the limit of large prompt length. We also prove that the optimal configuration of such a transformer is indeed the minimizer of the corresponding training loss. Further, we empirically demonstrate the proficiency of multi-layer transformers in efficiently solving broader in-context estimation problems. Through extensive simulations, we show that solving ICE problems using transformers significantly outperforms standard approaches. Moreover, just with a few context examples, it achieves the same performance as an estimator with perfect knowledge of the latent context.

The A-channel is a noiseless multiple access channel in which users simultaneously transmitQ−ary symbols and the receiver observes the union of all input symbols. An A-channel is said to be unsourced if additionally, all users’ transmissions are encoded across time using a common codebook and decoding is performed without regard to the identities of the active users. Whereas the A-channel employs a traditional set union, the B-channel employs a multiset union so that the receiver observes the set of input symbols together with their respective multiplicities. In this paper, we consider the task of coding for the unsourced A- and B-channels in the presence of i.i.d. erasures and we propose a novel tail-biting code called the linked loop code (LLC) for these channels. The LLC is shown to outperform contemporary codes in part due to its resilience to lost sections. The performance of the LLC code is investigated theoretically and bounds on the error performance are provided.

This article introduces a novel concatenated coding scheme called sparse regression LDPC (SR-LDPC) codes. An SR-LDPC code consists of an outer non-binary LDPC code and an inner sparse regression code (SPARC), whose respective field size and section sizes are equal. For such codes, an efficient decoding algorithm is proposed based on approximate message passing (AMP) that dynamically shares soft information between inner and outer decoders. This dynamic exchange of information is facilitated by a denoiser that runs belief propagation (BP) on the factor graph of the outer LDPC code within each AMP iteration. It is shown that this BP denoiser falls within the framework of non-separable denoising functions and subsequently, that state evolution holds for the proposed AMP-BP algorithm. Leveraging the rich structure of SR-LDPC codes, this article proposes an efficient low-dimensional approximate state evolution recursion that can be used for efficient hyperparameter tuning, thus paving the way for future work on optimal code design. Finally, numerical simulations demonstrate that SR-LDPC codes outperform contemporary codes over the AWGN channel for parameters of practical interest. SR-LDPC codes are shown to be viable means for obtaining shaping gains over the AWGN channel.

In [1], the linked loop code (LLC) is presented as a promising code for the unsourced A-channel with erasures (UACE). The UACE is an unsourced multiple access channel in which active users’ transmitted symbols are erased with a given probability and the channel output is obtained as the union of the non-erased symbols. In this paper, we extend the UACE channel model to the unsourced B-channel with erasures (UBCE). The UBCE differs from the UACE in that the channel output is the multiset union – or bag union– of the non-erased input symbols. In other words, the UBCE preserves the symbol multiplicity of the channel output while the UACE does not. Both the UACE and UBCE find applications in modeling aspects of unsourced random access. The LLC from [1] is enhanced and shown to outperform the tree code over the UBCE. Findings are supported by numerical simulations.

Novel sparse regression LDPC (SR-LDPC) codes exhibit excellent performance over additive white Gaussian noise (AWGN) channels in part due to their natural provision of shaping gains. Though SR-LDPC-like codes have been considered within the context of single-user error correction and massive random access, they are yet to be examined as candidates for coordinated multi-user communication scenarios. This article explores this gap in the literature and demonstrates that SR-LDPC codes, when combined with coded demixing techniques, offer a new framework for efficient non-orthogonal multiple access (NOMA) in the context of coordinated multi-user communication channels. The ensuing communication scheme is referred to as MU-SR-LDPC coding. Empirical evidence suggests that MU-SR-LDPC coding can increase the sum-rate for a fixed Eb/N0 when compared to orthogonal multiple access (OMA) techniques such as time division multiple access (TDMA) or frequency division multiple access (FDMA). Importantly, MU-SR-LDPC coding enables a pragmatic solution path for user-centric cell-free communication systems with (local) joint decoding. Results are supported by numerical simulations.

Iterative decoding of graph-based codes and sparse recovery through approximate message passing (AMP) are two research areas that have seen monumental progress in recent decades. Inspired by these advances, this article introduces sparse regression LDPC codes (SR-LDPC codes) and their decoding. Sparse regression codes (SPARCs) are a class of error correcting codes that build on ideas from compressed sensing and can be decoded using AMP. In certain settings, SPARCs are known to achieve capacity; yet, their performance suffers at finite block lengths. Likewise, low-density parity-check (LDPC) codes can be decoded efficiently using belief propagation and can also be capacity achieving. This article introduces a novel concatenated coding structure that combines an LDPC outer code with a SPARC-inspired inner code. Efficient decoding for such a code can be achieved using AMP with a denoiser that performs belief propagation on the factor graph of the outer LDPC code. The proposed framework exhibits performance improvements over SPARCs and standard LDPC codes for finite block lengths and results in a steep waterfall in error performance, a phenomenon not observed in uncoded SPARCs.

We explore a scheme that enables the training of a deep neural network in a Federated Learning configuration over an additive white Gaussian noise channel. The goal is to create a low complexity, linear compression strategy, called PolarAir, that reduces the size of the gradient at the user side to lower the number of channel uses needed to transmit it. The suggested approach belongs to the family of compressed sensing techniques, yet it constructs the sensing matrix and the recovery procedure using multiple access techniques. Simulations show that it can reduce the number of channel uses by ∼30% when compared to conveying the gradient without compression. The main advantage of the proposed scheme over other schemes in the literature is its low time complexity. We also investigate the behavior of gradient updates and the performance of PolarAir throughout the training process to obtain insight on how best to construct this compression scheme based on compressed sensing.

Unsourced random access emerged as a novel wireless paradigm enabling massive device connectivity on the uplink. We consider quasi-static Rayleigh fading wherein the access point has multiple receive antennas and every mobile device a single transmit antenna. The objective is to construct a coding scheme that minimizes the energy-per-bit subject to a maximum probability of error given a fixed message length and a prescribed number of channel uses. Every message is partitioned into two parts: the first determines pilot values and spreading sequences; the remaining bits are encoded using a polar code. The transmitted signal contains two distinct sections. The first features pilots and the second is composed of spread modulated symbols. The receiver has three modules: an energy detector, tasked with recovering the set of active pilot sequences; a bank of Minimum Mean Square Error (MMSE) estimators acting on measurements at the receiver; and a polar list-decoder, which seeks to retrieve the coded information bits. A successive cancellation step is applied to subtract recovered codewords, before the residual signal is fed back to the decoder. Empirical evidence suggests that an appropriate combination of these ideas can outperform state-of-the-art coding techniques when the number of active users exceeds one hundred.

Safe reinforcement learning is extremely challenging--not only must the agent explore an unknown environment, it must do so while ensuring no safety constraint violations. We formulate this safe reinforcement learning (RL) problem using the framework of a finite-horizon Constrained Markov Decision Process (CMDP) with an unknown transition probability function, where we model the safety requirements as constraints on the expected cumulative costs that must be satisfied during all episodes of learning. We propose a model-based safe RL algorithm that we call Doubly Optimistic and Pessimistic Exploration (DOPE), and show that it achieves an objective regret $\tilde{O}(|\mathcal{S}|\sqrt{|\mathcal{A}| K})$ without violating the safety constraints during learning, where $|\mathcal{S}|$ is the number of states, $|\mathcal{A}|$ is the number of actions, and $K$ is the number of learning episodes. Our key idea is to combine a reward bonus for exploration (optimism) with a conservative constraint (pessimism), in addition to the standard optimistic model-based exploration. DOPE is not only able to improve the objective regret bound, but also shows a significant empirical performance improvement as compared to earlier optimism-pessimism approaches.

This article introduces a novel communication paradigm for the unsourced, uncoordinated Gaussian multiple access problem. The major components of the envisioned framework are as follows. The encoded bits of every message are partitioned into two groups. The first portion is transmitted using a compressive sensing scheme, whereas the second set of bits is conveyed using a multi-user coding scheme. The compressive sensing portion is key in sidestepping some of the challenges posed by the unsourced aspect of the problem. The information afforded by the compressive sensing is employed to create a sparse random multi-access graph conducive to joint decoding. This construction leverages the lessons learned from traditional IDMA into creating low-complexity schemes for the unsourced setting, while also accounting for inherent randomness. Under joint message-passing decoding, the proposed scheme offers good performance at a low computational complexity. Findings are supported by numerical simulations, and results are compared to existing alternatives.

Sparse regression codes with approximate message passing (AMP) decoding have gained much attention in recent times. The concepts underlying this coding scheme extend to unsourced random access with coded compressed sensing (CCS), as first demonstrated by Fengler, Jung, and Caire. Specifically, their approach employs a concatenated coding framework with an inner AMP decoder followed by an outer tree decoder. In their original implementation, these two components work independently of each other, with the tree decoder acting on the static output of the AMP decoder. This article introduces a novel framework where the inner AMP decoder and the outer decoder operate in tandem, dynamically passing information back and forth to take full advantage of the underlying CCS structure. This scheme necessitates the redesign of the outer code as to enable belief propagation in a computationally tractable manner. The enhanced architecture exhibits significant performance benefits over a range of system parameters. The error performance of the proposed scheme can be accurately predicted through a set of equations known as state evolution of AMP. These findings are supported both analytically and through numerical methods.

Crucial performance metrics of a caching algorithm include its ability to quickly and accurately learn a popularity distribution of requests. However, a majority of work on analytical performance analysis focuses on hit probability after an asymptotically large time has elapsed. We consider an online learning viewpoint, and characterize the “regret” in terms of the finite time difference between the hits achieved by a candidate caching algorithm with respect to a genie-aided scheme that places the most popular items in the cache. We first consider the Full Observation regime wherein all requests are seen by the cache. We show that the Least Frequently Used (LFU) algorithm is able to achieve order optimal regret, which is matched by an efficient counting algorithm design that we call LFU-Lite. We then consider the Partial Observation regime wherein only requests for items currently cached are seen by the cache, making it similar to an online learning problem related to the multi-armed bandit problem. We show how approaching this “caching bandit” using traditional approaches yields either high complexity or regret, but a simple algorithm design that exploits the structure of the distribution can ensure order optimal regret. We conclude by illustrating our insights using numerical simulations.

This article seeks to advance coded compressed sensing (CCS) as a practical scheme for unsourced random access. The CCS algorithm features a concatenated structure where an inner code is tasked with support recovery and an outer code conducts message disambiguation. Recently, the CCS scheme was improved through the use of approximate message passing (AMP) with a dynamic denoiser that shares soft information between the inner and outer decoders. This significantly improves performance at the cost of additional complexity. This work shows how the spatial coupling generated by the outer code is sufficiently strong to justify relaxing certain constraints on the inner code. It is shown that a block diagonal sensing matrix with the aforementioned dynamic denoiser forms an effective means to get good performance at reduced complexity. This novel architecture can be used to scale CCS to dimensions that were previously impractical. Findings are supported by numerical simulations.

This article presents a novel enhancement to the random spreading based coding scheme developed by Pradhan et al. for the unsourced multiple access channel. The original coding scheme features a polar outer code in conjunction with a successive cancellation list decoder (SCLD) and a hard-input soft-output MMSE estimator. In contrast, the proposed scheme employs a soft-input soft-output MMSE estimator for multi-user detection. This is accomplished by replacing the SCLD based polar code with an LDPC code amenable to belief propagation decoding. This novel framework is leveraged to successfully pass pertinent soft information between the MMSE estimator and the outer code. LDPC codes are carefully designed using density evolution techniques to match the iterative process. This enhanced architecture exhibits significant performance improvements and represents the state-of-the-art over a wide range of system parameters.

Unsourced random access (URA) is a recently proposed communication paradigm attuned to machine-driven data transfers. In the original URA formulation, all the active devices share the same number of bits per packet. The scenario where several classes of devices transmit concurrently has so far received little attention. An initial solution to this problem takes the form of group successive interference cancellation, where codewords from a class of devices with more resources are recovered first, followed by the decoding of the remaining messages. This article introduces a joint iterative decoding approach rooted in approximate message passing. This framework has a concatenated coding structure borrowed from the single-class coded compressed sensing and admits a solution that offers performance improvement at little added computational complexity. Our findings point to new connections between multiclass URA and compressive demixing. The performance of the envisioned algorithm is validated through numerical simulations.

We consider the approximate support recovery (ASR) task of inferring the support of a$K$-sparse vector$\mathrm{x}\in \mathbb{R}^{n}$from$m$noisy measurements. We examine the case where$n$is large, which precludes the application of standard compressed sensing solvers, thereby necessitating solutions with lower complexity. We design a scheme for ASR by leveraging techniques developed for unsourced multiple access. We present two decoding algorithms with computational complexities$\mathcal{O}(K^{2}\log n+ K\log n\log\log n)$and$\mathcal{O}(K^{3}+K^{2}\log n+K\log n\log \log n)$per iteration, respectively. When$K\ll n$, this is much lower than the complexity of approximate message passing with a minimum mean squared error denoiser, which requires$\mathcal{O}(mn)$operations per iteration. This gain comes at a slight performance cost. Our findings suggest that notions from multiple access can play an important role in the design of measurement schemes for ASR.

Coded compressed sensing is an algorithmic framework tailored to sparse recovery in very large dimensional spaces. This framework is originally envisioned for the unsourced multiple access channel, a wireless paradigm attuned to machine-type communications. Coded compressed sensing uses a divide-and-conquer approach to break the sparse recovery task into sub-components whose dimensions are amenable to conventional compressed sensing solvers. The recovered fragments are then stitched together using a low complexity decoder. This article introduces an enhanced decoding algorithm for coded compressed sensing where fragment recovery and the stitching process are executed in tandem, passing information between them. This novel scheme leads to gains in performance and a significant reduction in computational complexity. This algorithmic opportunity stems from the realization that the parity structure inherent to coded compressed sensing can be used to dynamically restrict the search space of the subsequent recovery algorithm.

This article presents a novel transmission scheme for the unsourced, uncoordinated Gaussian multiple access problem. The proposed scheme leverages notions from single-user coding, random spreading, minimum-mean squared error (MMSE) estimation, and successive interference cancellation. Specifically, every message is split into two parts: the first fragment serves as the argument to an injective function that determines which spreading sequence should be employed, whereas the second component of the message is encoded using a polar code. The latter coded bits are then spread using the sequence determined during the first step. The ensuing signal is transmitted through a Gaussian multiple-access channel (GMAC). On the receiver side, active sequences are detected using a correlation-based energy detector, thereby simultaneously recovering individual signature sequences and their generating information bits in the form of preimages of the sequence selection function. Using the set of detected active spreading sequences, an MMSE estimator is employed to produce log-likelihood ratios (LLRs) for the second part of the messages corresponding to these detected users. The LLRs associated with each detected user are then passed to a list decoder of the polar code, which performs single-user decoding to decode the second portion of the message. This decoding operation proceeds iteratively by subtracting the interference due to the successfully decoded messages from the received signal, and repeating the above steps on the residual signal. At this stage, the proposed algorithm outperforms alternate existing low-complexity schemes when the number of active uses is below 225.

Sparse regression codes with approximate message passing (AMP) decoding have gained much attention in recent times. The concepts underlying this coding scheme extend to unsourced access with coded compressed sensing (CCS), as first pointed out by Fengler, Jung, and Caire. More specifically, their approach uses a concatenated coding framework with an inner AMP decoder followed by an outer tree decoder. In the original implementation, these two components work independently of each other, with the tree decoder acting on the static output of the AMP decoder. This article introduces a novel framework where the inner AMP decoder and the outer tree decoder operate in tandem, dynamically passing information back and forth to take full advantage of the underlying CCS structure. The enhanced architecture exhibits significant performance benefit over a range of system parameters.

Real-time decision making relies on the availability of accurate data and, therefore, delivering status updates in a timely fashion is of paramount importance. The topic of real-time status updates has received much attention in recent years. This article contributes new results to this research area by studying the interplay between average timeliness and design decisions made at the physical layer, for unreliable communication channels. Specifically, this study explores the tension between the fact that more reliable transmissions with lower probabilities of decoding failure tend to improve timely delivery, unless these improvements come at the expense of significantly longer codewords. The average timeliness is adopted as an evaluation criterion, and a framework to efficiently compute the performance of various transmission schemes for the binary erasure channel is developed. We show that the average timeliness decreases as we increase the feedback rate in a hybrid ARQ scheme for a range of codeword lengths. This article also provides design guidelines for the codeword length selection for an hybrid ARQ scheme to improve the average information timeliness. Numerical examples are included to further illustrate the applicability of our findings.

This article introduces a novel scheme, termed coded compressed sensing, for unsourced multiple-access communication. The proposed divide-and-conquer approach leverages recent advances in compressed sensing and forward error correction to produce a novel uncoordinated access paradigm, along with a computationally efficient decoding algorithm. Within this framework, every active device partitions its data into several sub-blocks and, subsequently, adds redundancy using a systematic linear block code. Compressed sensing techniques are then employed to recover sub-blocks up to a permutation of their order, and the original messages are obtained by stitching fragments together using a tree-based algorithm. The error probability and computational complexity of this access paradigm are characterized. An optimization framework, which exploits the tradeoff between performance and computational complexity, is developed to assign parity-check bits to each sub-block. In addition, two emblematic parity bit allocation strategies are examined and their performances are analyzed in the limit as the number of active users and their corresponding payloads tend to infinity. The number of channel uses needed and the computational complexity associated with these allocation strategies are established for various scaling regimes. Numerical results demonstrate that coded compressed sensing outperforms other existing practical access strategies over a range of operational scenarios.

This article introduces a novel communication paradigm for the unsourced, uncoordinated Gaussian multiple access problem. The major components of the envisioned framework are as follows. The encoded bits of every message are partitioned into two groups. The first portion is transmitted using a compressive sensing scheme, whereas the second set of bits is conveyed using a multi-user coding scheme. The compressive sensing portion is key in sidestepping some of the challenges posed by the unsourced aspect of the problem. The information afforded by the compressive sensing is employed to create a sparse random multi-access graph conducive to joint decoding. This construction leverages the lessons learned from traditional IDMA into creating low- complexity schemes for the unsourced setting and its inherent randomness. Under joint message- passing decoding, the proposed scheme offers superior performance compared to existing low- complexity alternatives. Findings are supported by numerical simulations.

The neighbor discovery paradigm finds wide application in Internet of Things networks, where the number of active devices is orders of magnitude smaller than the total device population. Designing low-complexity schemes for asynchronous neighbor discovery has recently gained significant attention from the research community. Concurrently, a divide-and-conquer framework, referred to as coupled compressive sensing, has been introduced for the synchronous massive random access channel. This work adapts this novel algorithm to the problem of asynchronous neighbor discovery with unknown transmission delays. Simulation results suggest that the proposed scheme requires much fewer transmissions to achieve a performance level akin to that of state-of-the-art techniques.

This paper focuses on the design and evaluation of pragmatic schemes for delay-sensitive communication. Specifically, this contribution studies the operation of data links that employ incremental redundancy as a means to shield information bits from the degradation associated with unreliable channels. While this inquiry puts forth a general methodology, exposition centers around erasure channels because they are well suited for analysis. Nevertheless, the goal is to identify both structural properties and design guidelines that are broadly applicable. Conceptually, this paper leverages a methodology, termed sequential differential optimization, aimed at identifying near-optimal block sizes for hybrid ARQ. This technique is applied to erasure channels and it is extended to scenarios where throughput is maximized subject to a constraint on the feedback rate. The analysis shows that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when maximizing throughput. Ultimately, block size selection is informed by approximate distributions on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid automatic repeat request and coding, offers a computationally efficient framework to select code rates and blocklengths for incremental redundancy. These findings are supported through numerical results.

This work introduces a novel coding paradigm for the unsourced multiple access channel model. The envisioned framework builds on a select few key components. First, the transmission period is partitioned into a sequence of sub-blocks, thereby yielding a slotted structure. Second, messages are split into two parts. A portion of the data is encoded using spreading sequences or codewords that are designed to be recovered by a compressed sensing type decoder. In addition to being an integral part of the data, the information bits associated with this first part also determine the parameters of the low-density parity check code employed during the subsequent stages of the communication process. The other portion of the message is encoded using the aforementioned low-density parity check code. The data embedded in this latter stage is decoded using a joint message passing algorithm designed for the T-user binary input real adder channel. Finally, devices repeat their codeword in multiple sub-blocks, with the transmission pattern being a deterministic function of message content independent of the identity of the device. When combined with successive interference cancellation, the ensuing communication infrastructure offers significant performance improvement compared to coding schemes recently published in the literature for unsourced random access.

Modern communication and computation systems often consist of large networks of unreliable nodes. Still, it is well known that such systems can provide aggregate reliability via redundancy. While duplication may increase the load on a system, it can lead to significant performance improvement when combined with the judicious management of extra system resources. Prime examples of this abstract paradigm include multi-path routing across communication networks, content access from multiple caches in delivery networks, and master/slave computations on compute clusters. Several recent contributions in the area establish bounds on the performance of redundant systems, characterizing the latency-redundancy tradeoff under specific load profiles. Following a similar line of research, this paper introduces new analytical bounds and approximation techniques for the latency-redundancy tradeoff for a range of system loads and a class of symmetric redundancy schemes, under the assumption of Poisson arrivals, exponential service-rates, and fork-join scheduling policy. The proposed approach can be employed to efficiently approximate the latency distribution of a queueing system at equilibrium. Various metrics can subsequently be derived for this system, including the mean and variance of the sojourn time, and the tail decay rate of the stationary distribution. This paper also establishes the stability region in terms of arrival rates for redundant systems with certain symmetries. Finally, it offers selection guidelines for design parameters to provide latency guarantees based on the proposed approximations. Findings are substantiated by numerical results.

Variable-length (VL) coding sends an initial codeword followed by subsequent transmissions of incremental redundancy (IR) sent when the decoder indicates through feedback that it has not yet identified a reliable codeword. VL coding is a staple of modern communication to handle fading, and recent theoretical analysis and applications have demonstrated its value on non-fading channels for applications that require short blocklengths. To maximize throughput in a VL setting, the length of each IR transmission should be optimized. Sequential differential optimization (SDO) computes transmission lengths that optimize throughput by minimizing average blocklength. SDO produces a family of solutions that each maximize throughput for a specified maximum number of transmissions. This paper considers the average number of feedback transmissions per message as an alternative metric for the cost of the feedback resource. A Lagrangian approach provides a new SDO solution that jointly minimizes both the average blocklength and the average number of feedback transmissions associated with a message. The mapping of real-valued SDO solutions to the necessarily integer transmission lengths is also addressed.

This article introduces a novel paradigm for the unsourced multiple-access communication problem. This divide-and-conquer approach leverages recent advances in compressive sensing and forward error correction to produce a computationally efficient algorithm. Within the proposed framework, every active device first partitions its data into several subblocks, and subsequently adds redundancy using a systematic linear block code. Compressive sensing techniques are then employed to recover sub-blocks, and the original messages are obtained by connecting pieces together using a low-complexity tree-based algorithm. Numerical results suggest that the proposed scheme outperforms other existing practical coding schemes. Measured performance lies approximately 4.3 dB away from the Polyanskiy achievability limit, which is obtained in the absence of complexity constraints.

As sensing and instrumentation play an increasingly important role in systems controlled over wired and wireless networks, the need to better understand delay-sensitive communication becomes a prime issue. Along these lines, this article studies the operation of data links that employ incremental redundancy as a practical means to protect information from the effects of unreliable channels. Specifically, this work extends a powerful methodology termed sequential differential optimization to choose near-optimal block sizes for hybrid ARQ over erasure channels. Furthermore, results show that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when analyzing throughput. Overall, block size selection is motivated by normal approximations on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid ARQ and coding, offers a pragmatic means to select code rates and blocklengths for incremental redundancy.

Modern communication and computation systems consist of large networks of unreliable nodes. Yet, it is well known that such systems can provide aggregate reliability via information redundancy, duplicating paths, or replicating computations. While redundancy may increase the load on a system, it can also lead to major performance improvements through the judicious management of additional system resources. Two important examples of this abstract paradigm are content access from multiple caches in content delivery networks and master/slave computations on compute clusters. Many recent articles in the area have proposed bounds on the latency performance of redundant systems, characterizing the latency-redundancy tradeoff under specific load profiles. Following a similar line of research, this article introduces new analytical bounds and approximation techniques for the latency-redundancy tradeoff for a range of system loads and two popular redundancy schemes. The proposed framework allows for approximating the equilibrium latency distribution, from which various metrics can be derived including mean, variance, and the tail decay of stationary distributions.

We propose a novel coding scheme for the unsourced multiple access channel model introduced by Polyanskiy [1]. This new paradigm is composed of four main ingredients: (i) the transmission period is partitioned into sub-blocks, thereby instituting a slotted framework; (ii) The message (data) is split into two parts and one part chooses an interleaver for a low density parity check (LDPC) type code. This part of the message is encoded using spreading sequences or codewords that are designed to be decoded by a compressed sensing type decoder; (iii) The other part of the message is encoded using a low density parity check (LDPC) type code and decoded using a joint message passing decoding algorithm designed for the T-user binary input real adder channel; (iv) users repeat their codeword in multiple sub-blocks, with the transmission pattern being a deterministic function of message content and independent of the identity of the user. When this coding scheme is combined with serial interference cancellation, the ensuing communication infrastructure can offer significant performance improvements compared to the recently proposed coding scheme in [2] and results in the best performing coding scheme to date.

As sensing, control, and actuation become further integrated into modern communication infrastructures, special consideration must be given to the type of traffic generated by associated devices. Real-time decision making relies on the availability of accurate data and, as such, delivering status updates in a timely fashion is of paramount importance. The topics of real-time status updates and low- delay communications have received much attention in recent years. Within this context, this article presents new results by looking at the interplay between average timeliness and design decisions made at the physical layer for unreliable communication channels. This study focuses on the natural tension between the protection afforded by additional redundancy and the decoding delay associated with longer codewords. The average timeliness is adopted as a performance criterion, and a framework to efficiently compute the performance of various transmission schemes for the binary erasure channel is developed. The problem formulation precludes the use of asymptotically long codewords typical of information theory. Yet, the presence of limited feedback does not seem to boost performance in the present context. Rather, having accurate channel estimates is key in minimizing average timeliness. Numerical examples are included in this article to further illustrate the applicability of the findings.

Future wireless access points may have to support sporadic transmissions from a massive number of unattended machines. Recently, there has been a lot of interest in the design of massive uncoordinated multiple access schemes for such systems based on clever enhancements to slotted ALOHA. A close connection has been established between the design of the multiple access scheme and the design of low density generator matrix codes. Based on this connection, optimal multiple access schemes have been designed based on slotted ALOHA and successive interference cancellation, assuming that the number of users in the network is known at the transmitters. In this paper, we extend this work and consider the design of universal uncoordinated multiple access schemes that are agnostic to the number of users in the network. We design Markov chain based transmission policies and numerical results show that substantial improvement to slotted ALOHA is possible.

Contemporary wireless networks are tasked with supporting different connection profiles, including real-time traffic and delay-sensitive communications. This creates a need to better understand the fundamental limits of forward error correction in non-asymptotic regimes. This paper characterizes the performance of block codes over finite-state channels and evaluates their queueing performance under maximum-likelihood decoding. Classical results from digital communications are revisited in the context of channels with rare transitions, and bounds on the probabilities of decoding failure are derived for random codes. This creates an analysis framework where channel dependencies within and across codewords are preserved. These results are subsequently integrated into a queueing problem formulation.

Reconfigurable antennas (RA) offer an emerging technology that allows wireless devices to alter their antenna states determined by different radiation patterns to maximize received signal strength. In this paper, we consider multiuser orthogonal frequency-division multiple access cognitive heterogeneous networks (HetNets) and we study the potential benefits of employing RA in terms of improving the overall network capacity. In cognitive HetNets, a secondary network is allowed to share the spectrum with the primary network under the condition that the interference level experienced by the primary network is below a predetermined threshold. To satisfy this interference constraint, a secondary user (SU) employs a power control mechanism, which typically limits its transmission power and thus reduces substantially its performance. Moreover, the large number of users expected for next-generation networks brings dense interference to the secondary network and, as such, even efficient interference mitigation and resource allocation techniques can fail in maintaining an acceptable performance level for the network. In this work, we consider utilizing RA technology at SUs to act as an additional resource in terms of selecting antenna radiation patterns that improve received signal strength among SUs. This also limits the mutual interference between the secondary and primary networks. We propose a game theoretical framework for jointly selecting the subcarriers as well as the RA antenna state at each SU that maximizes the overall capacity of the network while meeting the interference target in the primary network. Using potential games that guarantee the existence of a Nash equilibrium, our results show that, by selecting the best RA state and subcarriers for each SU, the capacity of the secondary network increases substantially compared to a scenario with conventional omni-directional antennas.

This article considers the performance of wireless communication systems that utilize reconfigurable or pattern-dynamic antennas. The focus is on finite-state channels with memory and performance is assessed in terms of real-time behavior. In a wireless setting, when a slow fading channel enters a deep fade, the corresponding communication system faces the threat of successive decoding failures at the destination. Under such circumstances, rapidly getting out of deep fades becomes a priority. Recent advances in fast reconfigurable antennas provide new means to alter the statistical profile of fading channels and thereby reduce the probability of prolonged fades. Fast reconfigurable antennas are therefore poised to improve overall performance, especially for delay-sensitive traffic in slow-fading environments. This potential for enhanced performance motivates this study of the temporal behavior of point-to-point communication systems with reconfigurable antennas. Specifically, agile wireless communication schemes over erasure channels are analyzed; situations where using reconfigurable antennas yield substantial performance gains in terms of throughput and average delay are identified. Scenarios where only partial state information is available at the receiver are also examined, naturally leading to partially observable decision processes.

This paper considers the performance of digital communication systems transmitting messages over finite-state erasure channels with memory. Information bits are protected from channel erasures using error-correcting codes; successful receptions of codewords are acknowledged at the source through instantaneous feedback. The primary focus of this research is on delay-sensitive applications, codes with finite block lengths, and, necessarily, nonvanishing probabilities of decoding failure. The contribution of this paper is twofold. A methodology to compute the distribution of the time required to empty a buffer is introduced. Based on this distribution, the mean hitting time to an empty queue and delay-violation probabilities for specific thresholds can be computed explicitly. The proposed techniques apply to situations where the transmit buffer contains a predetermined number of information bits at the onset of the data transfer. Furthermore, as additional performance criteria, large deviation principles are obtained for the empirical mean service time and the average packet-transmission time associated with the communication process. This rigorous framework yields a pragmatic methodology to select code rate and block length for the communication unit as functions of the service requirements. Examples motivated by practical systems are provided to further illustrate the applicability of these techniques.

This paper considers the relationship between code-rate selection and queueing performance for communication systems subject to time-varying channel conditions. While error-correcting codes offer protection against channel uncertainties, there exists a natural tradeoff between the enhanced protection of low-rate codes and the rate penalty imposed by additional redundancy. In the limiting regime where codewords are asymptotically long, this tradeoff is well understood and characterized by the Shannon capacity. However, for delay-sensitive communication systems and finite block lengths, a complete characterization of this tradeoff is not fully developed. This paper offers a new perspective on the queueing performance of communication systems with finite block lengths operating over correlated erasure channels. A rigorous framework that links code rate to overall system performance for random codes is presented. Guidelines for code-rate selection in delay-sensitive systems are identified. These findings are supported by a numerical study.

Quantization is intrinsic to several data acquisition systems. This process is especially important in distributed settings, where observations must first be compressed before they are disseminated. There have been many practical successes in the area of quantization, including the acclaimed Lloyd-Max algorithm. This article adopts a different perspective and it explores quantization at a fundamental level, seeking to identify classes of problems for which efficient quantization is possible. The focus is primarily on positive random variables of unbounded support, where severe degradation may occur. Established properties of Banach spaces are exploited, together with the boundedness of probability measures, to prove that efficient quantization schemes necessarily exist in the fine-quantization regime. The results are algorithmic in nature and provide bounds on the number of bits necessary to achieve a desired level of performance.

This paper considers the queueing performance of a communication system that transmits BCH-coded data over the correlated-error channel first studied by Gilbert and Elliott in the 1960s. For some arrival processes, one can join the queue length and channel state so that the pair forms a Markov chain; this provides a powerful tool to analyze the tail probability of the queue. For Bernoulli packet arrivals, this approach works but does not allow for fair comparisons between different block-length codes. In this paper, a Poisson arrival model is assumed in order to make fair comparisons between codes with arbitrary block length and code rate. This enables one to optimize code parameters for delay-sensitive communication systems over time-varying channels. Finally, the analysis is supported through a Monte Carlo simulation.

The traditional formulation of the total value of information transfer is a multi-commodity flow problem. Each data source is seen as generating a commodity along a fixed route, and the objective is to maximize the total system throughput under some concept of fairness, subject to capacity constraints of the links used. This problem is well studied under the framework of network utility maximization and has led to several different distributed congestion control schemes. However, this view of value does not capture the fact that flows may associate value, not just with throughput, but with link-quality metrics such as packet delay and jitter. In this work, the congestion control problem is redefined to include individual source preferences. It is assumed that degradation in link quality seen by a flow adds up on the links it traverses, and the total utility is maximized in such a way that the end-to-end quality degradation seen by each source is bounded by a value that it declares. Decoupling source-dissatisfaction and link-degradation through an effective capacity variable, a distributed and provably optimal resource allocation algorithm is designed to maximize system utility subject to these quality constraints. The applicability of the controller in different situations is supported by numerical simulations, and a protocol developed using the controller is simulated on ns-2 to illustrate its performance.

The traditional formulation of the total value of information transfer is a multi-commodity flow problem. Here, each data source is seen as generating a commodity along a fixed route, and the objective is to maximize the total system throughput under some concept of fairness, subject to capacity constraints of the links used. This problem is well studied under the framework of network utility maximization and has led to several different distributed congestion control schemes. However, this idea of value does not capture the fact that flows might associate value, not just with throughput, but with link-quality metrics such as packet delay, jitter and so on. The traditional congestion control problem is redefined to include individual source preferences. It is assumed that degradation in link quality seen by a flow adds up on the links it traverses, and the total utility is maximized in such a way that the quality degradation seen by each source is bounded by a value that it declares. Decoupling source-dissatisfaction and link- degradation through an ``effective capacity'' variable, a distributed and provably optimal resource allocation algorithm is designed, to maximize system utility subject to these quality constraints. The applicability of our controller in different situations is illustrated, and results are supported through numerical examples.

This paper considers the queueing performance of a system that transmits coded data over a time-varying erasure channel. In our model, the queue length and channel state together form a Markov chain that depends on the system parameters. This gives a framework that allows a rigorous analysis of the queue as a function of the code rate. Most prior work in this area either ignores block-length (e.g., fluid models) or assumes error-free communication using finite codes. This work enables one to determine when such assumptions provide good, or bad, approximations of true behavior. Moreover, it offers a new approach to optimize parameters and evaluate performance. This can be valuable for delay-sensitive systems that employ short block lengths.

The design of wireless communication schemes tailored to real-time traffic requires an analysis framework that goes beyond the traditional criterion of data throughput. This work considers an approach that relates physical system parameters to the queueing performance of wireless links. The potential benefits of multi-rate techniques such as hybrid-ARQ are assessed in the context of delay-sensitive traffic using large deviations. A continuous-time Markov channel model is employed to partition the instantaneous data-rate received at the destination into a finite number of states, each representing a mode of operation of the hybrid-ARQ scheme. The proposed methodology accounts for the correlation of the wireless channel across time, which is computed in terms of level-crossing rates. The tail asymptote governing buffer overflow probabilities at the transmitter is then used to provide a measure of overall performance. This approach leads to a characterization of the effective capacity of the system which, in turn, is applied to quantify the performance advantages of hybrid-ARQ over traditional schemes.

Network coding has gained significant attention in recent years as a means to improve throughput, especially in multicast scenarios. These capacity gains are achieved by combining packets algebraically at various points in the network, thereby alleviating local congestion at the nodes. The benefits of network coding are greatest when the network is heavily utilized or, equivalently, when the sources are saturated so that there is data to send at every scheduling opportunity. Yet, when a network supports delay-sensitive applications, traffic is often bursty and congestion becomes undesirable. The lighter loads typical of real-time traffic with variable sources tend to reduce the returns of network coding. This work seeks to identify the potential benefits of network coding in the context of delay-sensitive applications. As a secondary objective, this paper also studies the cost of establishing network coding in wireless environments. For a network topology to be suitable for coding, links need to possess a proper structure. The cost of establishing this structure may require excessive radio resources in terms of bandwidth and transmit power. Bursty traffic together with structural cost tend to decrease the potential benefits of network coding. This paper describes how, for real-time applications over wireless networks, there exist network topologies for which it may be best not to establish a network structure tailored to network coding.

The concept of effective capacity offers a novel methodology to investigate the impact that design decisions at the physical layer may have on system performance at the link layer. Assuming a constant flow of incoming data, the effective capacity characterizes the maximum arrival rate that a wireless system can support as a function of its service requirements. Service requirements in this framework are defined in terms of the asymptotic decay-rate of buffer occupancy. This article studies the effective capacity of a class of multiple-antenna wireless systems subject to Rayleigh flat fading. The effective capacity of the multi-antenna Gaussian channel is characterized, and system performance is evaluated in the low signal-to-noise ratio regime. Additional to the power gain of the multiple receive antenna system, we show that there is a statistical gain associated with a multiple transmit antenna system. When the number of transmit and/or receive antennas becomes large, the effective capacity of the system is bounded away from zero, even under very stringent service constraints. This phenomena, which results from channel-hardening, suggests that a multiple-antenna configuration is especially beneficial to delay-sensitive traffic.

Network coding has gained significant attention in recent years as a means to improve throughput, especially in multicast scenarios. These capacity gains are achieved by combining packets algebraically at various points in the network, thereby alleviating local congestion at the nodes. The benefits of network coding are greatest when the network is heavily utilized or, equivalently, when the sources have infinite backlogs. However, if a network supports delay-sensitive applications, traffic is often sparse and congestion becomes undesirable. The lighter loads typical of real-time traffic with variable sources tend to reduce the returns of network coding. This work seeks to identify the potential benefits of network coding in the context of delay-sensitive applications. As a secondary objective, this paper also studies the cost of establishing network coding in wireless environments. For a network topology to be suitable for coding, links need to possess a proper structure. The cost of establishing this structure may require excessive wireless resources in terms of bandwidth and transmit power. Together, these effects decrease the potential benefits of network coding. For real-time applications over wireless networks, it may be best not to combine information at the nodes.

In this paper, a multiuser communication system in which wireless users cooperate to transmit information to a base station is considered. The proposed scheme can significantly enlarge the achievable rate region, provided that the wireless connections between pairs of cooperating users are stronger than the connection from every user to the base station. The gains in transmission rate remain substantial even when the channel phase information is only available at the receivers, not at the transmitters. In the proposed scheme, a transmission period is divided into two time intervals. During the first time interval, wireless users send data to the base station and to the neighboring users simultaneously using a broadcast channel paradigm. During the second time interval, the users cooperate to transmit information to the base station. The achievable rate region corresponding to this paradigm is characterized under a random phase channel model for a two-user system. Results are then generalized to a multiple-user scenario. For fixed system parameters, the achievable rate region is strictly larger than that of the traditional multiple-access channel, thereby allowing a fair distribution of the wireless resources among users. Numerical analysis suggests that cooperating with a single partner is enough to achieve most of the benefits associated with cooperation.

A wireless communication system in which multiple users cooperate to transmit information to a common destination is considered. The traffic generated by the users is subject to a stringent quality of service requirement, which is defined in terms of the asymptotic decay-rate of buffer occupancy. The performance of this communication system is analyzed, and the corresponding achievable rate-region for the two-user scenario is identified. A simple user-cooperation scheme that improves performance is proposed. This cooperative scheme is shown to significantly enlarge the achievable rate-region of the service constrained communication system, provided that the quality of the wireless link between cooperating users is better than the individual connections from the users to the intended destination. Numerical results further indicate that the gains of cooperative strategies can be substantial. This suggests that cooperation allows for a fair distribution of the wireless resources among active users.

Wireless systems offer a unique mixture of connectivity, flexibility, and freedom. It is therefore not surprising that wireless technology is being embraced with increasing vigor. For real-time applications, user satisfaction is closely linked to quantities such as queue length, packet loss probability, and delay. System performance is therefore related to, not only Shannon capacity, but also quality of service (QoS) requirements. This work studies the problem of resource allocation in the context of stringent QoS constraints. The joint impact of spectral bandwidth, power, and code rate is considered. Analytical expressions for the probability of buffer overflow, its associated exponential decay rate, and the effective capacity are obtained. Fundamental performance limits for Markov wireless channel models are identified. It is found that, even with an unlimited power and spectral bandwidth budget, only a finite arrival rate can be supported for a QoS constraint defined in terms of exponential decay rate

A detection problem in sensor networks is considered, where the sensor nodes are placed on a line and receive partial information about their environment. The nodes transmit a summary of their observations over a noisy communication channel to a fusion center for the purpose of detection. The observations at the sensors are samples of a spatial stochastic process, which is one of two possible signals corrupted by Gaussian noise. Two cases are considered: one where the signal is deterministic under each hypothesis, and the other where the signal is a correlated Gaussian process under each hypothesis. The nodes are assumed to be subject to a power density constraint, i.e., the power per unit distance is fixed, so that the power per node decreases linearly with the node density. Under these constraints, the central question that is addressed is: how dense should the sensor array be, i.e., is it better to use a few high-cost, high-power nodes or to have many low-cost, low-power nodes? An answer to this question is obtained by resorting to an asymptotic analysis where the number of nodes is large. In this asymptotic regime, the Gaumlrtner-Ellis theorem and similar large-deviation theory results are used to study the impact of node density on system performance. For the deterministic signal case, it is shown that performance improves monotonically with sensor density. For the stochastic signal case, a finite sensor density is shown to be optimal

A binary decentralized detection problem is studied in which a collection of wireless sensor nodes provides relevant information about their environment to a fusion center. The observations at the nodes are samples of a finite state Markov process under each hypothesis. The nodes transmit their data to a fusion center over a multiple access channel. Upon reception of the information, the fusion center selects one of the two possible hypotheses. It is assumed that the sensor system is constrained by the capacity of the multiple access channel over which the sensor nodes are transmitting. Thus, as the node density increases, the sensor observations get more correlated, and, furthermore, fewer bits can be transmitted by each sensor node. A framework is presented in this paper for deriving design guidelines relating sensor density to system performance under a total communication constraint. The framework is based on large deviation theory applied to the asymptotic regime where the number of sensor nodes is large. This framework is applied to a specific example to compare the gains offered by having a higher node density with the benefits of getting detailed information from each sensor.

We study a binary decentralized detection problem in which a set of sensor nodes provides partial information about the state of nature to a fusion center. Sensor nodes have access to conditionally independent observations, given the state of nature, and they transmit their data over separate wireless channels. The communication link between each node and the fusion center is subject to fading, with certain nodes possibly having much better connections than others. Upon reception of the information, the fusion center attempts to accurately reconstruct the state of nature. Large deviation theory is employed to obtain design guidelines for wireless sensor networks with a large number of nodes. The normalized Chernoff information is shown to be an appropriate performance metric to compare prospective sensor nodes. For the specific example of binary sensor nodes sending data over Rayleigh fading channels, the performance loss due to fading is found to be small.

A binary decentralized detection problem in which sensor nodes provide partial information about their environment to a fusion center is studied. The nodes have access to conditionally independent observations and transmit a summary of their own data over wireless channels. Upon reception of the information, the fusion center attempts to accurately reconstruct the state of nature. The communication link between each node and the fusion center is modeled as a fading channel corrupted by additive noise. Channel state information is available at the fusion center and at the sensor nodes. Large deviation theory is used to show that having identical sensor nodes is asymptotically optimal. Algorithms in which each sensor node selects a signaling/coding schemes based on the quality of its channel are studied.

This paper outlines interesting applications of large-deviation theory and asymptotic analysis to the design of wireless sensor networks. Sensor networks are envisioned to contain a large amount of wireless nodes. As such, asymptotic regimes where the number of nodes becomes large are important tools in identifying good design rules for future sensor systems. Through a simple example, we show how the Gartner-Ellis theorem can be used to study the impact of density on overall performance in resource constrained systems. Specifically, we consider the problem where sensor nodes receive partial information about their environment, and then send a summary of their observations to a fusion center for the purpose of detection. Each node transmits its own data on a noisy communication channel. Observations are assumed to become increasingly correlated as sensor nodes are placed in close proximity. It is found that high node density performs well even when observations from adjacent sensors are highly correlated. Furthermore, the tools presented in this paper can be employed for a more complete analysis of the tradeoff between resource allocation, system complexity, and overall performance in wireless sensor networks.

In this paper, we study a binary decentralized detection problem in which a set of sensor nodes provides partial information about the state of nature to a fusion center. Sensor nodes have access to conditionally independent and identically distributed observations, given the state of nature, and transmit their data over a wireless channel. Upon reception of the information, the fusion center attempts to accurately reconstruct the state of nature. Specifically, we extend existing asymptotic results about large sensor networks to the case where the network is subject to a joint power constraint, and where the communication channel from each sensor node to the fusion center is corrupted by additive noise. Large deviation theory is used to show that having identical sensor nodes, i.e., each node using the same transmission scheme, is asymptotically optimal. Furthermore, a performance metric by which sensor node candidates can be compared is established. We supplement the theory with examples to illustrate how the results derived in this paper apply to the design of practical sensing systems.

The control of transmit power has been recognized as an essential requirement in the design of cellular code-division multiple-access (CDMA) systems. Indeed, power control allows for mobile users to share radio resources equitably and efficiently in a multicell environment. Much of the work on power control for CDMA systems found in the literature assumes a quasi-static channel model, i.e., the channel gains of the users are assumed to be constant over a sufficiently long period of time for the control algorithm to converge. In this paper, the design of dynamic power control algorithms for CDMA systems is considered without the quasi-static channel restriction. The design problem is posed as a tradeoff between the desire for users to maximize their individual quality of service and the need to minimize interference to other users. The dynamic nature of the wireless channel for mobile users is incorporated in the problem definition. Based on a cost minimization framework, an optimal multiuser solution is derived. The multiuser solution is shown to decouple, and effectively converge, to a single-user solution in the large system asymptote, where the number of users and the spreading factor both go to infinity with their ratio kept constant. In a numerical study, the performance of a simple threshold policy is shown to be near that of the optimal single-user policy. This offers support to the threshold decision rules that are employed in current cellular CDMA systems.