Search

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction $\tau \ge 1/4$ vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with $n$ transmissions that achieves a positive rate for any fraction of errors $\tau < 1$ and $n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes. [ABSTRACT FROM AUTHOR]

This paper studies a memoryless state-dependent multiple access channel (MAC) where two transmitters wish to convey a message to a receiver under the assumption of causal and imperfect channel state information at transmitters (CSIT) and imperfect channel state information at receiver (CSIR). In order to emphasize the limitation of transmitter cooperation between physically distributed nodes, we focus on the so-called distributed CSIT assumption, i.e., where each transmitter has its individual channel knowledge, while the message can be assumed to be partially or entirely shared a priori between transmitters by exploiting some on-board memory. Under this setup, the first part of the paper characterizes the common message capacity of the channel at hand for arbitrary CSIT and CSIR structure. The optimal scheme builds on Shannon strategies, i.e., optimal codes are constructed by letting the channel inputs be a function of current CSIT only. For a special case when CSIT is a deterministic function of CSIR, the considered scheme also achieves the capacity region of a common message and two private messages. The second part addresses an important instance of the previous general result in a context of a cooperative multi-antenna Gaussian channel under i.i.d. fading operating in frequency-division duplex mode, such that CSIT is acquired via an explicit feedback of perfect CSIR. The capacity of the channel at hand is achieved by distributed linear precoding applied to Gaussian codes. Surprisingly, we demonstrate that it is suboptimal to send a number of data streams bounded by the number of transmit antennas as typically considered in a centralized CSIT setup. Finally, numerical examples are provided to evaluate the sum capacity of the binary MAC with binary states as well as the Gaussian MAC with i.i.d. fading. [ABSTRACT FROM AUTHOR]

It is well known that for Gaussian channels, a nearest neighbor decoding rule, which seeks the minimum Euclidean distance between a codeword and the received channel output vector, is the maximum likelihood solution and hence capacity-achieving. Nearest neighbor decoding remains a convenient and yet mismatched solution for general channels, and the key message of this paper is that the performance of nearest neighbor decoding can be improved by generalizing its decoding metric to incorporate channel state dependent output processing and codeword scaling. Using generalized mutual information, which is a lower bound to the mismatched capacity under independent and identically distributed codebook ensemble, as the performance measure, this paper establishes the optimal generalized nearest neighbor decoding rule, under Gaussian channel input. Several restricted forms of the generalized nearest neighbor decoding rule are also derived and compared with existing solutions. The results are illustrated through several case studies for fading channels with imperfect receiver channel state information and for channels with quantization effects. [ABSTRACT FROM AUTHOR]

Barcoding photons, atoms, and any quantum states can provide a host of functionalities that could benefit future quantum communication systems and networks beyond today’s imagination. As a significant application of barcoding photons, we introduce code division multiple-access (CDMA) communication systems for various applications. In this context, we introduce and discuss the fundamental principles of a novel quantum CDMA (QCDMA) technique based on spectrally encoding and decoding of continuous-mode quantum light pulses. In particular, we present the mathematical models of various QCDMA modules that are fundamental in describing an ideal and typical QCDMA system, such as quantum signal sources, quantum spectral encoding phase operators, M × M quantum broadcasting star-coupler, quantum spectral phase decoding operators, and the quantum receivers. Following the above discussions, we then elaborate on a QCDMA system with M users. In describing a QCDMA system, this paper considers a unified approach where the input continuous-mode quantum light pulses can take on any form of pure states such as quantum coherent (Glauber) states and quantum number (Fock) states. The mathematical presentation is independent of the form of the input pure quantum states. We show that the spectrally encoded quantum states of the light at the quantum star-coupler output are not, in general, factorized states, except for input Glauber states. For input number states, one can observe features like entanglement and quantum interference. Moreover and interestingly, as a consequence of Heisenberg’s uncertainty principle, the quantum signals sent by photon number states obtain complete phase uncertainty at the time of measurement. Therefore, at the receiver output, the multiaccess inter-signal interference vanishes. Due to Heisenberg’s uncertainty principle, the received signal intensity at the photodetector’s output, right at the time of measurement, changes from coherent detection scheme for input Glauber states to incoherent detection scheme for input number states. We also would like to highlight that the mathematical models and tools developed in this paper, in the context of QCDMA, become very useful for developing and analyzing other quantum multiple-access techniques based on wavelength, space and time domain. Furthermore, our mathematical model is valuable in signal design and data modulations of point-to-point quantum communications, quantum pulse shaping, and quantum radar signals and systems where the inputs are continuous mode quantum signals. QCDMA may open up novel possibilities for various quantum technologies such as data privacy, distributed quantum computation, quantum internet, and anti-jamming quantum communication systems. [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]

We investigate a privacy-signaling game problem in which a sender with privacy concerns observes a pair of correlated random vectors which are modeled as jointly Gaussian. The sender aims to hide one of these random vectors and convey the other one whereas the objective of the receiver is to accurately estimate both of the random vectors. We analyze these conflicting objectives in a game theoretic framework with quadratic costs where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg (Bayesian persuasion) equilibria. We show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. We formulate the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the random variables is observed at the sender. We show that this MMSE Gaussian Information Bottleneck Problem admits a linear solution which is explicitly characterized in the paper. We provide explicit conditions on when the optimal solutions, or equilibrium solutions in the Nash setup, are informative or noninformative. [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]

Previous works on age of information and erasure channels have dealt with specific models and computed the average age or average peak age for certain settings. In this paper, given a source that produces a letter every $T_{s}$ seconds and an erasure channel that can be used every $T_{c}$ seconds, we ask what is the coding strategy that minimizes the time-average “age of information” that an observer of the channel output incurs. We first analyze the case where the source alphabet and the channel-input alphabet have the same size. We show that a trivial coding strategy is optimal and a closed form expression for the age can be derived. We then analyze the case where the alphabets have different sizes. We use a random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age of linear block codes as the source alphabet becomes large. [ABSTRACT FROM AUTHOR]

In this paper, a general framework is formalised to characterise the value of information (VoI) in hidden Markov models. Specifically, the VoI is defined as the mutual information between the current, unobserved status at the source and a sequence of observed measurements at the receiver, which can be interpreted as the reduction in the uncertainty of the current status given that we have noisy past observations of a hidden Markov process. We explore the VoI in the context of the noisy Ornstein-Uhlenbeck process and derive its closed-form expressions. Moreover, we investigate the effect of different sampling policies on VoI, deriving simplified expressions in different noise regimes and analysing statistical properties of the VoI in the worst case. We also study the optimal sampling policy to maximise the average information value under the sampling rate constraint. In simulations, the validity of theoretical results is verified, and the performance of VoI in Markov and hidden Markov models is also analysed. Numerical results further illustrate that the proposed VoI framework can support timely transmission in status update systems, and it can also capture the correlation properties of the underlying random process and the noise in the transmission environment. [ABSTRACT FROM AUTHOR]

The Langberg-Médard multiple unicast conjecture claims that for a strongly reachable $k$ -pair network, there exists a feasible multi-flow with rate $(1,1, {\dots },1)$. In this paper, we confirm the conjecture for $k=3$. [ABSTRACT FROM AUTHOR]

This paper presents explicit solutions for two related non-convex information extremization problems due to Gray and Wyner in the Gaussian case. The first problem is the Gray-Wyner network subject to a sum-rate constraint on the two private links. Here, our argument establishes the optimality of Gaussian codebooks and hence, a closed-form formula for the optimal rate region. The second problem is Wyner’s common information and a generalization thereof, where conditional independence is generalized to a limit on the conditional mutual information. We present full explicit solutions for the scalar as well as the vector case. [ABSTRACT FROM AUTHOR]

This paper employs auxiliary receivers as a mathematical tool to identify Gallager-type auxiliary random variables and write outer bounds for some basic multiuser settings. This approach is then applied to the relay, interference, and broadcast channel settings, yielding new outer bounds that improve on existing outer bounds and strictly outperform classical outer bounds. For instance, we strictly improve on: the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channel. [ABSTRACT FROM AUTHOR]

The deterministic identification (DI) capacity is developed in multiple settings of channels with power constraints. A full characterization is established for the DI capacity of the discrete memoryless channel (DMC) with and without input constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness at the encoder, resulting in a double exponential number of messages in the block length $n$. In the deterministic setup, the number of messages scales exponentially, as in Shannon’s transmission paradigm, but the achievable identification rates are higher. An explicit proof was not provided for the deterministic setting. In this paper, a detailed proof is presented for the DMC. Furthermore, Gaussian channels with fast and slow fading are considered, when channel side information is available at the decoder. A new phenomenon is observed as we establish that the number of messages scales as $2^{n\log (n)R}$ by deriving lower and upper bounds on the DI capacity on this scale. Consequently, the DI capacity of the Gaussian channel is infinite in the exponential scale and zero in the double exponential scale, regardless of the channel noise. [ABSTRACT FROM AUTHOR]

Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes and assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication with end-to-end encryption for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that information-theoretic secrecy can be achieved asymptotically if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose a practical scheme that achieves a good balance of network and channel rates with information-theoretic secrecy guarantee. This work has a wide range of potential applications for which strong secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks. [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]

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]

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size $\exp (\exp (\Theta (\sqrt {\text {n}})))$ can be transmitted over n channel uses. We then characterize the exact pre-constant in the $\Theta (\cdot)$ notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints. [ABSTRACT FROM AUTHOR]

The correspondence cited in the above article derived ergodic capacity of the coherent multiple-input multiple-output (MIMO) channel in independent and identically distributed (IID) Rayleigh fading. While the theoretical results are correct, several plots in the paper are incorrect. In this correspondence, we correct the plots. More importantly, the corrected plots present an interesting and compelling contrast between performances of the coherent MIMO systems with and without channel state information at the transmitter; whereas this view is somewhat limited in the above article because of flaws in the capacity curves. [ABSTRACT FROM AUTHOR]

We derive universal classical-quantum superposition coding and universal classical-quantum multiple access channel coding by using generalized packing lemmas for the type method. Using our classical-quantum universal superposition code, we establish the capacity region of a classical-quantum compound broadcast channel with degraded message sets. Our universal classical-quantum multiple access channel codes have two types of codes. One is a code with joint decoding and the other is a code with separate decoding. It is not so easy to construct a former code that universally achieves general points of the capacity region beyond corner points. First, we construct the latter code that universally achieves general points of the capacity region. Then, converting the latter code to the former coder, we construct the above desired code with the former type. [ABSTRACT FROM AUTHOR]

The original coded caching scenario assumes a content library that is of interest to all receiving users. In a realistic scenario though, the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, 40% of the users and each user has potential interest in 40% of the library? In this work, we investigate the so- called symmetrically selfish coded caching scenario, where each user only makes requests from a subset of the library that defines its own file demand set (FDS), each user caches selfishly only contents from its own FDS, and where the different FDSs symmetrically overlap to some extent. In the context of various traditional prefetching scenarios (prior to the emergence of coded caching), selfish approaches were known to be potentially very effective. On the other hand — with the exception of some notable works — little is known about selfish coded caching. We here present a new information-theoretic converse that proves, in a general setting of symmetric FDS structures, that selfish coded caching, despite enjoying a much larger local caching gain and a much smaller set of possible demands, introduces an unbounded load increase compared to the unselfish case. In particular, in the $K$ -user broadcast channel where each user stores a fraction $\gamma $ of the library, where each file (class) is of interest to $\alpha $ users, and where any one specific file is of interest to a fraction $\delta $ of users, the optimal coding gain of symmetrically selfish caching is at least $(K - \alpha)\gamma + 1$ times smaller than in the unselfish scenario. This allows us to draw the powerful conclusion that the optimal selfish coding gain is upper bounded by $1/(1 - \delta)$ , and thus does not scale with $K$. These derived limits are shown to be exact for different types of demands. In the end, this work provides, in a unified manner, the strong conclusion that selfish caching can cause unbounded performance deterioration in coded caching systems. [ABSTRACT FROM AUTHOR]

Minimum energy required to achieve a distortion-noise profile, i.e., a function indicating the maximum allowed distortion value for each channel noise level, is studied for transmission of Gaussian sources over Gaussian channels. A general coding scheme is proposed to upper bound the minimum energy needed for any distortion-noise profile. Conversely, utilizing a family of lower bounds originally derived for broadcast channels with power constraints, the minimum required energy is lower bounded for any profile. As examples, linear, exponential, square-law, and staircase profiles are studied. It is shown that for the linear profile, as well as for any concave profile, uncoded transmission is optimal. As a negative result, it is shown that exponential profiles are not achievable with finite energy. For square-law and staircase profiles, upper bounds and lower bounds are derived and the gaps between them are studied. [ABSTRACT FROM AUTHOR]

We consider the task of communicating a generic bivariate function of two classical correlated sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. We first propose a coding scheme based on asymptotically good algebraic structured codes, in particular, nested coset codes, and provide a set of sufficient conditions for the reconstruction of the function of the sources over a CQ-MAC. The proposed technique enables the decoder to recover the desired function without recovering the sources themselves. We further improve this by employing a coding scheme based on a classical superposition of algebraic structured codes and unstructured codes. This coding scheme allows exploiting the symmetric structure common amongst the sources and also leverage the asymmetries. We derive a new set of sufficient conditions that strictly enlarges the largest known set of sources whose function can be reconstructed over any given CQ-MAC, and identify examples demonstrating the same. We provide these conditions in terms of single-letter quantum information-theoretic quantities. [ABSTRACT FROM AUTHOR]

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads $N$ is fixed. Of significance, for the single-deletion channel, using $\log _{2}\log _{2} n +O(1)$ redundant bits, we designed a reconstruction code of length $n$ that reconstructs codewords from two distinct noisy reads (Cai et al., 2021). In this work, we show that $\log _{2}\log _{2} n -O(1)$ redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of the construction. Furthermore, we show that these reconstruction codes can be used in $t$ -deletion channels (with $t \geqslant 2$) to uniquely reconstruct codewords from ${n^{t-1}}/{(t-1)!}+O\left ({n^{t-2}}\right)$ distinct noisy reads. For the two-deletion channel, using higher order VT syndromes and certain runlength constraints, we designed the class of higher order constrained shifted VT code with $2\log _{2} n +o(\log _{2}(n))$ redundancy bits that can reconstruct any codeword from any $N \geqslant 5$ of its length- $(n-2)$ subsequences. [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]

A word is said to be bordered if it contains a non-empty proper prefix that is also a suffix. We can naturally extend this definition to pairs of non-empty words. A pair of words $(u,v)$ is said to be mutually bordered if there exists a word that is a non-empty proper prefix of $u$ and suffix of $v$ , and there exists a word that is a non-empty proper suffix of $u$ and prefix of $v$. In other words, $(u,v)$ is mutually bordered if $u$ overlaps $v$ and $v$ overlaps $u$. We give a recurrence for the number of mutually bordered pairs of words. Furthermore, we show that, asymptotically, there are $c\cdot k^{2n}$ mutually bordered words of length- $n$ over a $k$ -letter alphabet, where $c$ is a constant. Finally, we show that the expected shortest overlap between pairs of words is bounded above by a constant. [ABSTRACT FROM AUTHOR]

This work identifies information-theoretic quantities that are closely related to the required list size on average for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding over general binary memoryless symmetric (BMS) channels. It also provides upper and lower bounds for these quantities that can be computed efficiently for very long codes. For the binary erasure channel (BEC), we provide a simple method to estimate the mean accurately via density evolution. The analysis shows how to modify, e.g., Reed-Muller codes, to improve the performance when practical list sizes, e.g., $L\in {[{8, 1024}]}$ , are adopted. Exemplary constructions with block lengths $N\in \{128,512\}$ outperform polar codes of 5G over the binary-input additive white Gaussian noise channel. It is further shown that there is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths, over discrete-output BMS channels. We provide the probability mass functions (p.m.f.s) of this logarithm, over the BEC, for a sequence of the modified RM codes with an increasing block length via simulations, which illustrate that the p.m.f.s concentrate around the estimated mean. [ABSTRACT FROM AUTHOR]

We develop a new upper bound on the capacity of the relay channel that is tighter than previously known upper bounds. This upper bound is proved using traditional weak converse techniques involving mutual information inequalities and Gallager-type explicit identification of auxiliary random variables. We show that the new upper bound is strictly tighter than all previous bounds for the Gaussian relay channel with non-zero channel gains. When specialized to the relay channel with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover’s relay channel problem, recovers the recent upper bound for the Gaussian case by Wu et al., and improves upon the recent bounds for the binary symmetric case by Wu et al. and Barnes et al., which were obtained using non-traditional geometric proof techniques. For the special class of a relay channel with orthogonal receiver components, we develop another upper bound on the capacity which utilizes an auxiliary receiver and show that it is strictly tighter than the bound by Tandon and Ulukus. Finally, we show through the Gaussian relay channel with i.i.d. relay output sequence that the bound with the auxiliary receiver can be strictly tighter than our main bound. [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]

Communication over a quantum multiple-access channel (MAC) with cribbing encoders is considered, whereby Transmitter 2 performs a measurement on a system that is entangled with Transmitter 1. Based on the no-cloning theorem, perfect cribbing is impossible. This leads to the introduction of a MAC model with noisy cribbing. In the causal and non-causal cribbing scenarios, Transmitter 2 performs the measurement before the input of Transmitter 1 is sent through the channel. Hence, Transmitter 2’s cribbing may inflict a “state collapse” for Transmitter 1. Achievable regions are derived for each setting. Furthermore, a regularized capacity characterization is established for robust cribbing, i.e. when the cribbing system contains all the information of the channel input. Building on the analogy between the noisy cribbing model and the relay channel, a partial decode-forward region is derived for a quantum MAC with non-robust cribbing. For the classical-quantum MAC with cribbing encoders, the capacity region is determined with perfect cribbing of the classical input, and a cutset region is derived for noisy cribbing. In the special case of a classical-quantum MAC with a deterministic cribbing channel, the inner and outer bounds coincide. [ABSTRACT FROM AUTHOR]

We determine the exact value of the optimal symmetric rate point $(r, r)$ in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity $r = h(1/2-\delta) \approx 0.78974$ , where $h(\cdot)$ is the binary entropy function and $\delta = 1/(2\log _{2}(2 + \sqrt {3}))$. Our motivation is a problem in quantitative group testing. Given a set of $n$ elements two of which are defective, the quantitative group testing problem asks for the identification of these two defectives through a series of tests. Each test gives the number of defectives contained in the tested subset, and the outcomes of previous tests are assumed known at the time of designing the current test. We establish that the minimum number of tests is asymptotic to $(\log _{2} n) / r$ as $n \to \infty $. [ABSTRACT FROM AUTHOR]

We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures that make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this the private index coding problem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where the server has the ability to multicast to any subset of users, and demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required. [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 complex Gaussian wiretap channel with finite-resolution analog-to-digital converters (ADCs) at both the legitimate receiver and the eavesdropper. For this channel, we show that a positive secrecy rate is always achievable as long as the channel gains at the legitimate receiver and at the eavesdropper are different, regardless of the quantization levels of the ADCs. For the achievability, we first consider the case of the one-bit ADCs at the legitimate receiver and apply a binary input distribution where the two input points have the same phase when the channel gain at the legitimate receiver is less than that at the eavesdropper, and otherwise the opposite phase. Then the result is generalized for the case of arbitrary finite-resolution ADCs at the legitimate receiver by translating the input distribution appropriately. We also provide numerical lower bounds on the achievable secrecy rates, and analyze the tendency of the secrecy rates according to the channel difference, the power constraint, and the quantization levels for some cases. For the special case of the real Gaussian wiretap channel with one-bit ADCs at both the legitimate receiver and the eavesdropper, we show that our choice of phase does not lose any optimality for the Wyner code. [ABSTRACT FROM AUTHOR]

The two-user Gaussian interference channel (G-IC) is revisited, with a particular focus on practically amenable discrete input signalling and treating interference as noise (TIN) receivers. The corresponding deterministic interference channel (D-IC) is first investigated and coding schemes that can achieve the entire capacity region of the D-IC under TIN are proposed. These schemes are then systematically translated into multi-layer superposition coding schemes based on purely discrete inputs for the real-valued G-IC. Our analysis shows that the proposed scheme is able to achieve the entire capacity region to within a constant gap for all channel parameters. To the best of our knowledge, this is the first constant-gap result under purely discrete signalling and TIN for the entire capacity region and all the interference regimes. Furthermore, the approach is extended to obtain coding schemes based on discrete inputs for the complex-valued G-IC. For such a scenario, the minimum distance and the achievable rate of the proposed scheme under TIN are analyzed, which takes into account the effects of random phase rotations introduced by the channels. Simulation results show that our scheme is capable of approaching the capacity region of the complex-valued G-IC and significantly outperforms Gaussian signalling with TIN in various interference regimes. [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]

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]

Based on the applications to the wire-tap channel and bounds on the relative generalized Hamming weight, we will introduce optimal codes of type $\mathcal {I}$ and type $\mathcal {II}$. We will give some necessary conditions and the explicit construction for a linear code $\mathcal {C}$ to be optimal of type $\mathcal {I}$ and $\mathcal {II}$ with respect to a subcode $\mathcal {C}_{1}$. We will also present a new bound on two different parameters of the relative generalized Hamming weight. [ABSTRACT FROM AUTHOR]

We consider the fundamental limits of reliable communication over a two-state compound channel when the state of the channel needs to be masked. Our model is closely related to an area of study known as covert communication, a setting in which the transmitter wishes to communicate to legitimate receiver(s) while ensuring that the communication is not detected by an adversary. Our main contribution is the establishment of upper and lower bounds on the throughput-key length region when the constraint that quantifies how much the states are masked is defined to be the total variation distance between the channel output distributions of the two states. When length of the key is sufficiently large, we provide sufficient conditions for the bounds to coincide. Our results follow the so-called square-root law and hence are reminiscent of results in covert communications. Numerical examples, including that of a Gaussian channel, are provided to illustrate our results. [ABSTRACT FROM AUTHOR]

Compute and Forward (CF) is a coding scheme which enables receivers to decode linear combinations of simultaneously transmitted messages while exploiting the linear properties of lattice codes and the additive nature of a shared medium. The scheme was originally designed for relay networks, yet, it was found useful in other communication problems, such as MIMO communication. Works in the current literature assume a fixed number of transmitters and receivers in the system. However, following the increase in communication networks density, it is interesting to investigate the performance of CF when the number of transmitters is large. In this work, we show that as the number of transmitters, L, grows, CF becomes degenerated, in the sense that a relay prefers to decode only one (strongest) user instead of any other linear combination of the transmitted codewords, treating the other users as noise. Moreover, the system’s sum-rate tends to zero as well. This makes scheduling necessary in order to maintain the superior abilities CF provides. We thus examine the problem of scheduling for CF. We start with insights on why good scheduling opportunities can be found. Then, we provide an asymptotically optimal, polynomial-time scheduling algorithm and analyze its performance. We conclude that with proper scheduling, CF is not merely non-degenerated, but, in fact, provides a gain for the system sum-rate, up to the optimal scaling law of O(log log L). [ABSTRACT FROM AUTHOR]

It has long been observed that cooperation between users in a communication network can improve its performance. Unfortunately, in practical ad-hoc networks, cooperation links can be unreliable, and in many cases part of the users in the system cannot be updated about their availability. In such a case we need robust coding schemes that exploit the cooperation links if they are present, but can still operate if cooperation is not possible. In this work we study the general broadcast channel with degraded message sets and cooperation link that may be absent, and derive its capacity region under such uncertainty conditions. A generalization of this model is studied, where the cooperation link capacity is one of k possible values, and its capacity region is derived. We examine the situation where the cooperation link capacity is random and suggest the following performance criterion: maximize the average rate of one user, subject to a constraint on the rate of the other user and the requirement that the system will operate in any realization of the (random) cooperation link. As examples to illustrate our results, the Gaussian broadcast channel is extensively examined, and its capacity is derived for the various cooperation models and assumptions suggested throughout. [ABSTRACT FROM AUTHOR]

We study scalar-linear and vector-linear solutions of the generalized combination network. We derive new upper and lower bounds on the maximum number of nodes in the middle layer, depending on the network parameters and the alphabet size. These bounds improve and extend the parameter range of known bounds. Using these new bounds we present a lower bound and an upper bound on the gap in the alphabet size between optimal scalar-linear and optimal vector-linear network coding solutions. For a fixed network structure, while varying the number of middle-layer nodes r, the asymptotic behavior of the upper and lower bounds shows that the gap is in Θ (log (r)). [ABSTRACT FROM AUTHOR]