Search

We consider the problem of communicating over a channel that randomly “tears” the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\mathrm{ Geometric}}(p_{n})$ , we characterize the capacity as $C = e^{-\alpha }$ , where $\alpha = \lim _{n\to \infty } p_{n} \log n$. Our results show that the case of ${\mathrm{ Geometric}}(p_{n})$ -length fragments and the case of deterministic length- $(1/p_{n})$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity. [ABSTRACT FROM AUTHOR]

This paper considers a real-time status update system in which an energy harvesting (EH)-powered transmitter node observes some physical process, and sends its sensed measurements in the form of status updates to a destination node. The status update and harvested energy packets are assumed to arrive at the transmitter according to independent Poisson processes, and the service time of each status update is assumed to be exponentially distributed. We quantify the freshness of status updates when they reach the destination using the concept of Age of Information (AoI). Unlike most of the existing analyses of AoI focusing on the evaluation of its average value when the transmitter is not subject to energy constraints, our analysis is focused on understanding the distributional properties of AoI through the characterization of its moment generating function (MGF). In particular, we use the stochastic hybrid systems (SHS) framework to derive closed-form expressions of the MGF of AoI under several queueing disciplines at the transmitter, including non-preemptive and preemptive in service/waiting strategies. Using these MGF results, we further obtain closed-form expressions for the first and second moments of AoI in each queueing discipline. We demonstrate the generality of this analysis by recovering several existing results for the corresponding system with no energy constraints as special cases of the new results. Our numerical results verify the analytical findings, and demonstrate the necessity of incorporating the higher moments of AoI in the implementation/optimization of real-time status update systems rather than just relying on its average value. [ABSTRACT FROM AUTHOR]

This paper considers a caching system of a single server and multiple users. We aim to characterize the memory-rate tradeoff for caching with uncoded cache placement, under nonuniform file popularity. Focusing on the modified coded caching scheme (MCCS) recently proposed by Yu, etal., we formulate the cache placement optimization problem for the MCCS to minimize the average delivery rate under nonuniform file popularity, restricting to a class of popularity-first placements. We then present two information-theoretic lower bounds on the average rate for caching with uncoded placement, one for general cache placements and the other restricted to the popularity-first placements. By comparing the average rate of the optimized MCCS with the lower bounds, we prove that the optimized MCCS attains the general lower bound for the two-user case, providing the exact memory-rate tradeoff. Furthermore, it attains the popularity-first-based lower bound for the case of general $K$ users with distinct file requests. In these two cases, our results also reveal that the popularity-first placement is optimal for the MCCS, and zero-padding used in coded delivery incurs no loss of optimality. For the case of $K$ users with redundant file requests, our analysis shows that there may exist a gap between the optimized MCCS and the lower bounds due to zero-padding. We next fully characterize the optimal popularity-first cache placement for the MCCS, which is shown to possess a simple file-grouping structure and can be computed via an efficient algorithm using closed-form expressions. Finally, we extend our study to accommodate nonuniformity in both file popularity and size, where we show that the optimized MCCS attains the lower bound for the two-user case, providing the exact memory-rate tradeoff. Numerical results show that, for general settings, the gap between the optimized MCCS and the lower bound only exists in limited cases and is very small. [ABSTRACT FROM AUTHOR]

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $P $ and $N $ respectively, the list decoding capacity is equal to $\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity. [ABSTRACT FROM AUTHOR]

The topological interference management (TIM) problem refers to the study of the $K$ -user partially connected interference networks with no channel state information at the transmitters (CSIT), except for the knowledge of network topology. In this paper, we study the TIM problem with confidential messages (TIM-CM), where message confidentiality must be satisfied in addition to reliability constraints. In particular, each transmitted message must be decodable at its intended receiver and remain confidential at the remaining $(K-1)$ receivers. Our main contribution is to present a comprehensive set of results for the TIM-CM problem by studying the symmetric secure degrees of freedom (SDoF). To this end, we first characterize necessary and sufficient conditions for feasibility of positive symmetric SDoF for any arbitrary topology. We next present two achievable schemes for the TIM-CM problem: For the first scheme, we use the concept of secure partition and, for the second one, we use the concept of secure independent sets. We also present outer bounds on symmetric SDoF for any arbitrary network topology. Using these bounds, we characterize the optimal symmetric SDoF of all $K=2$ -user and $K=3$ -user network topologies. [ABSTRACT FROM AUTHOR]

Several information-theoretic studies on channels with output quantization have identified the capacity-achieving input distributions for different fading channels with 1-bit in-phase and quadrature (I/Q) output quantization. However, an exact characterization of the capacity-achieving input distribution for channels with multi-bit phase quantization has not been provided. In this paper, we consider four different channel models with multi-bit phase quantization at the output and identify the optimal input distribution for each channel model. We first consider a complex Gaussian channel with $b$ -bit phase-quantized output and prove that the capacity-achieving distribution is a rotated $2^{b}$ -phase shift keying (PSK). The analysis is then extended to multiple fading scenarios. We show that the optimality of rotated $2^{b}$ -PSK continues to hold under noncoherent fast fading Rician channels with $b$ -bit phase quantization when line-of-sight (LoS) is present. When channel state information (CSI) is available at the receiver, we identify $\frac {2\pi }{2^{b}}$ -symmetry and constant amplitude as the necessary and sufficient conditions for the ergodic capacity-achieving input distribution; which a $2^{b}$ -PSK satisfies. Finally, an optimum power control scheme is presented which achieves ergodic capacity when CSI is also available at the transmitter. [ABSTRACT FROM AUTHOR]

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 $\frac {1}2\frac {\log {n}}{n}+{O} \left ({\frac {1}{n}}\right)$ bits per channel use. The result $\vphantom {\sum ^{R}}$ 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. [ABSTRACT FROM AUTHOR]

With the prevalence of orthogonal frequency-division multiplexing (OFDM) in many standards, e.g., IEEE 802.11, IEEE 802.16, DVB-T, and DVB-T2, a number of variant modulation schemes based on OFDM have been proposed, which resort to signal sparsity to further enhance spectral efficiency and mitigate the high peak-to-average ratio (PAPR) problem. Among these variants, OFDM with subcarrier number modulation (OFDM-SNM) has been proven to be efficient for simple communication systems with low constellation modulation orders and limited decoding capability. To rigorously verify the performance advantages of OFDM-SNM, we present the study of OFDM-SNM in this paper from the information-theoretic perspective. In particular, we determine an upper bound on the mutual information of OFDM-SNM in closed form by using the log sum inequality. Also, we analyze the optimal pattern utilization probabilities (PUPs) for OFDM-SNM by channel-dependent coding and propose an easy-to-implement iterative algorithm to approach the optimal PUPs. Moreover, considering the practical achievability, we propose a Huffman coding based achievable PUP vector construction scheme to obtain the achievable PUPs and the corresponding achievable rate. We carry out numerical simulations to verify the effectiveness of this study and illustrate the efficiency of the obtained PUPs in comparison with several benchmarks. [ABSTRACT FROM AUTHOR]

It is well known that the capacity region of an average transmit power constrained Gaussian Broadcast Channel (GBC) with independent noise realizations at the receivers is enlarged by the presence of causal noiseless feedback. When the noise variances at the receivers are identical, even passive feedback via independent memoryless Gaussian links can lead to a capacity region enlargement. The last fact remains true even when the feedback noise variance is very high, and available only from one of the receivers. While such capacity enlargements are feasible for several other feedback models in the Gaussian BC setting, it is also known that feedback does not change the capacity region for physically degraded broadcast channels. In this paper, we consider a two user GBC with independent noise realizations at the receivers, where the feedback links from the receivers are corrupted by independent additive Gaussian noise processes. We investigate the set of four noise variances, two forward and two feedback, for which no capacity enlargement is possible. A sharp characterization of this region is derived, i.e., any quadruple outside the presented region will lead to a capacity enlargement, whereas quadruples inside will leave the capacity region unchanged. Our results lead to the conclusion that when the forward noise variances are different, too noisy a feedback from one of the receivers alone is not always beneficial for enlarging the capacity region, be it from the stronger user or the weaker one, in sharp contrast to the case of equal forward noise variances. [ABSTRACT FROM AUTHOR]

We investigate covert communication under a sequential change-point detection (SCPD) framework, where a transmitter, Alice, attempts to communicate reliably with a receiver, Bob, over an additive white Gaussian noise channel, while simultaneously ensuring covertness (low probability of detection) with respect to an adversary, Willie. Different from the binary hypothesis test based detection framework considered in prior works where Willie collects all signal samples together and makes a decision in a batch manner, we view Willie’s detection process as an SCPD process that works in a real-time manner. We establish a new criterion to evaluate the covertness of the communication between Alice and Bob, and investigate the performance of covert communication accordingly. Subject to the proposed constraint on covertness, we investigate the feasible transmit power and transmission duration under three SCPD algorithms, namely, the Shewhart test, the finite moving average chart (FMAC), and the cumulative sum (CUSUM) test, and characterize how the covert communication throughput scales with the average run length to false alarm (ARL2FA) of Willie’s detector as the ARL2FA increases without bound. Our theoretical results can be viewed as upper bounds on the covert communication throughput that can be achieved, and we show that compared with the case where Willie performs the CUSUM test, Alice and Bob achieve a higher covert communication throughput if Willie performs the Shewhart test or the FMAC. [ABSTRACT FROM AUTHOR]

In applications of remote sensing, estimation, and control, timely communication is critical but not always ensured by high-rate communication. This work proposes decentralized age-efficient transmission policies for random access channels with $M$ transmitters. We propose the notion of age-gain of a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which transmitters act in a decentralized manner based on the age-gain of their available packets. In particular, each transmitter sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. Both methods improve age of information significantly compared to the state of the art. In the limit of large $M$ , we prove that when the arrival rate is small (below $\frac {1}{eM}$), slotted ALOHA-type algorithms are order optimal. As the arrival rate increases beyond $\frac {1}{eM}$ , while age increases under slotted ALOHA, it decreases significantly under the proposed age-based policies. For arrival rates $\theta $ , $\theta =\frac {1}{o(M)}$ , the proposed algorithms provide a multiplicative gain of at least two compared to the minimum age under slotted ALOHA (minimum over all arrival rates). We conclude that it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain. This is surprising and contrary to common practice where the arrival rate is optimized to attain the minimum AoI. We further extend our results to other random access technologies such as Carrier-sense multiple access (CSMA). [ABSTRACT FROM AUTHOR]

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2\log (n)$ bits in one sub-regime, and at most $\Omega ({n})$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping. [ABSTRACT FROM AUTHOR]

We consider the problem of covert communication over a state-dependent channel when the Channel State Information (CSI) is available either non-causally, causally, or strictly causally, either at the transmitter alone, or at both transmitter and receiver. Covert communication with respect to an adversary, called “warden,” is one in which, despite communication over the channel, the warden’s observation remains indistinguishable from an output induced by innocent channel-input symbols. Covert communication involves fooling an adversary in part by a proliferation of codebooks; for reliable decoding at the legitimate receiver, the codebook uncertainty is typically removed via a shared secret key that is unavailable to the warden. In contrast to previous work, we do not assume the availability of a large shared key at the transmitter and legitimate receiver. Instead, we only require a secret key with negligible rate to bootstrap the communication and our scheme extracts shared randomness from the CSI in a manner that keeps it secret from the warden, despite the influence of the CSI on the warden’s output. When CSI is available at the transmitter and receiver, we derive the covert capacity region. When CSI is only available at the transmitter, we derive inner and outer bounds on the covert capacity. We also provide examples for which the covert capacity is positive with knowledge of CSI but is zero without it. [ABSTRACT FROM AUTHOR]

Aligned-Images Sum-set Inequalities are used in this work to study the Generalized Degrees of Freedom (GDoF) of the symmetric layered multi-hop interference channel under the robust assumption that the channel state information at the transmitters (CSIT) is limited to finite precision. First, the sum-GDoF value is characterized for the $2\times 2\times 2$ setting that is comprised of 2 sources, 2 relays, and 2 destinations. It is shown that the sum-GDoF does not improve even if perfect CSIT is allowed in the first hop, as long as the CSIT in the second hop is limited to finite precision. The sum GDoF characterization is then generalized to the $2\times 2\times \cdots \times 2$ setting that is comprised of $L$ hops. Remarkably, for large $L$ , the sum-GDoF value approaches that of the one-hop broadcast channel that is obtained by full cooperation among the two transmitters of the last hop, with finite precision CSIT. Previous studies of multi-hop interference networks either identified sophisticated GDoF optimal schemes under perfect CSIT, such as aligned interference neutralization and network diagonalization, that are powerful in theory but too fragile to be practical, or studied robust achievable schemes like classical amplify/decode/compress-and-forward without claims of information-theoretic optimality. In contrast, under finite precision CSIT, we show that the benefits of fragile schemes are lost, while a combination of classical random coding schemes that are simpler and much more robust, namely a rate-splitting between decode-and-forward and amplify-and-forward, is shown to be GDoF optimal. As such, this work represents another step towards bridging the gap between theory (optimality) and practice (robustness) with the aid of Aligned-Images Sum-set Inequalities. [ABSTRACT FROM AUTHOR]

We consider a transmitter and $K$ receivers, each of which shares a key variable with the transmitter. Through a noiseless broadcast channel, the transmitter wishes to send a common message $W$ securely to $N$ out of the $K$ receivers while the remaining $K-N$ receivers learn no information about $W$. We are interested in the maximum message rate, i.e., the maximum number of bits of $W$ that can be securely groupcast to the legitimate receivers per key block and the minimum broadcast bandwidth, i.e., the minimum number of bits of the broadcast information required to securely groupcast the message bits. We focus on the setting of combinatorial keys, where every subset of the $K$ receivers share an independent key of arbitrary size. Under this combinatorial key setting, the maximum message rate is characterized for the following scenarios - 1) $N=1$ or $N=K-1$ , i.e., secure unicast to 1 receiver with $K-1$ eavesdroppers or secure groupcast to $K-1$ receivers with 1 eavesdropper, 2) $N=2, K=4$ , i.e., secure groupcast to 2 out of 4 receivers, and 3) the symmetric setting where the key size for any subset of the same cardinality is equal for any $N,K$. Further, for the latter two cases, the minimum broadcast bandwidth for the maximum message rate is characterized. [ABSTRACT FROM AUTHOR]

We show that the problem of code construction for multiple access channel (MAC) resolvability can be reduced to the simpler problem of code construction for source resolvability. Specifically, we propose a MAC resolvability code construction that relies on a combination of multiple source resolvability codes, used in a black-box manner, and leverages randomness recycling implemented via distributed hashing and block-Markov coding. Since explicit source resolvability codes are known, our results also yield the first explicit coding schemes that achieve the entire MAC resolvability region for any discrete memoryless multiple-access channel with binary input alphabets. [ABSTRACT FROM AUTHOR]

A new converse bound is presented for the two-user multiple-access channel under the average probability of error constraint. This bound shows that for most channels of interest, the second-order coding rate—that is, the difference between the best achievable rates and the asymptotic capacity region as a function of blocklength $n$ with fixed probability of error—is $O(1/\sqrt {n})$ bits per channel use. The principal tool behind this converse proof is a new measure of dependence between two random variables called wringing dependence, as it is inspired by Ahlswede’s wringing technique. The $O(1/\sqrt {n})$ gap is shown to hold for any channel satisfying certain regularity conditions, which includes all discrete-memoryless channels and the Gaussian multiple-access channel. Exact upper bounds as a function of the probability of error are proved for the coefficient in the $O(1/\sqrt {n})$ term, although for most channels they do not match existing achievable bounds. [ABSTRACT FROM AUTHOR]

We study private classical communication over quantum multiple-access channels. For an arbitrary number of transmitters, we derive a regularized expression of the capacity region. In the case of degradable channels, we establish a single-letter expression for the best achievable sum-rate and prove that this quantity also corresponds to the best achievable sum-rate for quantum communication over degradable quantum multiple-access channels. In our achievability result, we decouple the reliability and privacy constraints, which are handled via source coding with quantum side information and universal hashing, respectively. Hence, we also establish that the multi-user coding problem under consideration can be handled solely via point-to-point coding techniques. As a by-product of independent interest, we derive a distributed leftover hash lemma against quantum side information that ensures privacy in our achievability result. [ABSTRACT FROM AUTHOR]

We present a condition for 1/2 degree of freedom for each user in constant $K$ -user single-antenna interference channels. This condition is sufficient for all and necessary for almost all channel matrices. Moreover, it applies to all channel topologies, i.e., to fully-connected channels as well as channels that have individual links absent, reflected by corresponding zeros in the channel matrix. Moreover, it captures the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference. Finally, we provide codebook constructions achieving 1/2 degree of freedom for each user for all channel matrices satisfying the condition we identified. [ABSTRACT FROM AUTHOR]

We consider a point–to–point communication system, where in addition to the encoder and the decoder, there is a helper that observes non–causally the realization of the noise vector and provides a (lossy) rate– $ {R}_{{ \text { h}}}$ description of it to the encoder ($ {R}_{{ \text { h}}} < \infty $). In continuation to Lapidoth and Marti (2020), who derived the capacity of this model, here our focus is on error exponents. We consider both continuous–alphabet, additive white Gaussian channels and finite–alphabet, modulo–additive channels, and for each one of them, we study the cases of both fixed–rate and variable–rate noise descriptions by the helper. Our main finding is that, as long as the channel–coding rate, R, is below the helper–rate, $ {R}_{{ \text { h}}}$ , the achievable error exponent is unlimited (i.e., it can be made arbitrarily large), and in some of the cases, it is even strictly infinite (i.e., the error probability can be made strictly zero). However, in the range of coding rates $({R}_{{ \text { h}}}, {R}_{{ \text { h}}}+ {C}_{0})$ , C0 being the ordinary channel capacity (without help), the best achievable error exponent is finite and strictly positive, although there is a certain gap between our upper bound (converse bound) and lower bound (achievability) on the highest achievable error exponent. This means that the model of encoder–assisted communication is essentially equivalent to a model, where in addition to the noisy channel between the encoder and decoder, there is also a parallel noiseless bit–pipe of capacity $ {R}_{{ \text { h}}}$. We also extend the scope to the Gaussian multiple access channel (MAC) and characterize the rate sub–region, where the achievable error exponent is unlimited or even infinite. [ABSTRACT FROM AUTHOR]

We study the generalized degrees-of-freedom (GDoF) of cellular networks under finite precision channel state information at the transmitters (CSIT). We consider downlink settings modeled by the interfering broadcast channel (IBC) under no multi-cell cooperation, and the overloaded multiple-input-single-output broadcast channel (MISO-BC) under full multi-cell cooperation. We focus on three regimes of interest: the mc-TIN regime, where a scheme based on treating inter-cell interference as noise (mc-TIN) was shown to be GDoF optimal for the IBC; the mc-CTIN regime, where the GDoF region achievable by mc-TIN is convex without the need for time-sharing; and the mc-SLS regime which extends a previously identified regime, where a simple layered superposition (SLS) scheme is optimal for the 3-transmitter-3-user MISO-BC, to overloaded cellular-type networks with more users than transmitters. We first show that the optimality of mc-TIN for the IBC extends to the entire mc-CTIN regime when CSIT is limited to finite precision. The converse proof of this result relies on a new application of aligned images bounds. We then extend the IBC converse proof to the counterpart overloaded MISO-BC, obtained by enabling full transmitter cooperation. This, in turn, is utilized to show that a multi-cell variant of the SLS scheme is optimal in the mc-SLS regime under full multi-cell cooperation, albeit only for 2-cell networks. The overwhelming combinatorial complexity of the GDoF region stands in the way of extending this result to larger networks. Alternatively, we appeal to extremal network analysis, recently introduced by Chan et al., and study the GDoF gain of multi-cell cooperation over mc-TIN in the three regimes of interest. We show that this extremal GDoF gain is bounded by small constants in the mc-TIN and mc-CTIN regimes, yet scales logarithmically with the number of cells in the mc-SLS regime. [ABSTRACT FROM AUTHOR]

We characterize the capacity region of the two-user broadcast packet erasure channel (PEC) with single-user delayed channel state information (CSI). More precisely, we assume one receiver does not provide its channel state to the other two nodes (the other receiver and the transmitter), while the other receiver reveals its state globally with unit delay. This is a hybrid CSI at the transmitter (CSIT) setting where the transmitter has the delayed CSI of one user but not the other. Previous results developed opportunistic network coding schemes for this setting, which strictly enlarge the achievable rate region compared to the no-CSIT baseline. Characterization of the capacity region with single-user delayed CSI, however, remained open. In this work, we develop an improved achievability strategy and show that the capacity region, surprisingly, matches that of the broadcast PEC with global delayed CSI of both users. The key to such improvement over previous results is a new precoding strategy for the retransmission phase of the opportunistic network coding scheme. It harnesses the single-user delayed CSI in the retransmission phase, so that interference from the feedback receiver can be aligned at the other receiver. Besides the broadcast PEC with two private messages, an extension to a model with an additional common message is also provided and the corresponding capacity region with single-user CSI also matches that with global delayed CSI. Finally, further extensions to three-user cases are also provided. [ABSTRACT FROM AUTHOR]