Search

We present an interpretation of Deepcode, a learned feedback code that showcases higher-order error correction relative to an earlier interpretable model. By interpretation, we mean succinct analytical encoder and decoder expressions (albeit with learned parameters) in which the role of feedback in achieving error correction is easy to understand. By higher-order, we mean that longer sequences of large noise values are acted upon by the encoder (which has access to these through the feedback) and used in error correction at the decoder in a two-stage decoding process., Comment: accepted to 60th Annual Allerton Conference

A Physically Unclonable Function (PUF) is a hardware security primitive used for authentication and key generation. It takes an input bit-vector challenge and produces a single-bit response, resulting in a challenge-response pair (CRP). The truth table of all challenge-response pairs of each manufactured PUF should look different due to inherent manufacturing randomness, forming a digital fingerprint. A PUF's entropy (the entropy of all the responses, taken over the manufacturing randomness and uniformly selected challenges) has been studied before and is a challenging problem. Here we explore a related notion -- the response entropy, which is the entropy of an arbitrary response given knowledge of one (and two) other responses. This allows us to explore how knowledge of some CRP(s) impacts the ability to guess another response. The Arbiter PUF (APUF) is a well-known PUF architecture based on accumulated delay differences between two paths. In this paper, we obtain in closed form the probability mass function of any arbitrary response given knowledge of one or two other arbitrary CRPs for the APUF architecture. This allows us to obtain the conditional response entropy and then to define and obtain the size of the entropy bins (challenge sets with the same conditional response entropy) given knowledge of one or two CRPs. All of these results depend on the probability that two different challenge vectors yield the same response, termed the response similarity of those challenges. We obtain an explicit closed form expression for this. This probability depends on the statistical correlations induced by the PUF architecture together with the specific known and to-be-guessed challenges. As a by-product, we also obtain the optimal (minimizing probability of error) predictor of an unknown challenge given access to one (or two) challenges and the associated predictability.

Deep learning methods have recently been used to construct non-linear codes for the additive white Gaussian noise (AWGN) channel with feedback. However, there is limited understanding of how these black-box-like codes with many learned parameters use feedback. This study aims to uncover the fundamental principles underlying the first deep-learned feedback code, known as Deepcode, which is based on an RNN architecture. Our interpretable model based on Deepcode is built by analyzing the influence length of inputs and approximating the non-linear dynamics of the original black-box RNN encoder. Numerical experiments demonstrate that our interpretable model -- which includes both an encoder and a decoder -- achieves comparable performance to Deepcode while offering an interpretation of how it employs feedback for error correction., Comment: Accepted to the 2024 ISIT conference

Modeling attacks, in which an adversary uses machine learning techniques to model a hardware-based Physically Unclonable Function (PUF) pose a great threat to the viability of these hardware security primitives. In most modeling attacks, a random subset of challenge-response-pairs (CRPs) are used as the labeled data for the machine learning algorithm. Here, for the arbiter-PUF, a delay based PUF which may be viewed as a linear threshold function with random weights (due to manufacturing imperfections), we investigate the role of active learning in Support Vector Machine (SVM) learning. We focus on challenge selection to help SVM algorithm learn ``fast'' and learn ``slow''. Our methods construct challenges rather than relying on a sample pool of challenges as in prior work. Using active learning to learn ``fast'' (less CRPs revealed, higher accuracies) may help manufacturers learn the manufactured PUFs more efficiently, or may form a more powerful attack when the attacker may query the PUF for CRPs at will. Using active learning to select challenges from which learning is ``slow'' (low accuracy despite a large number of revealed CRPs) may provide a basis for slowing down attackers who are limited to overhearing CRPs.

This paper considers the single antenna, static Gaussian broadcast channel in the finite blocklength regime. Second order achievable and converse rate regions are presented. Both a global reliability requirement and per-user reliability requirements are considered. The two-user case is analyzed in detail, and generalizations to the $K$-user case are also discussed. The largest second order achievable region presented here requires both superposition and rate splitting in the code construction, as opposed to the (infinite blocklength, first order) capacity region which does not require rate splitting. Indeed, the finite blocklength penalty causes superposition alone to under-perform other coding techniques in some parts of the region. In the two-user case with per-user reliability requirements, the capacity achieving superposition coding order (with the codeword of the user with the smallest SNR as cloud center) does not necessarily gives the largest second order region. Instead, the message of the user with the smallest point-to-point second order capacity should be encoded in the cloud center in order to obtain the largest second order region for the proposed scheme.

This paper focuses on the Layered Packet Erasure Broadcast Channel (LPE-BC) with Channel Output Feedback (COF) available at the transmitter. The LPE-BC is a high-SNR approximation of the fading Gaussian BC recently proposed by Tse and Yates, who characterized the capacity region for any number of users and any number of layers when there is no COF. This paper provides a comparative overview of this channel model along the following lines: First, inner and outer bounds to the capacity region (set of achievable rates with backlogged arrivals) are presented: a) a new outer bound based on the idea of the physically degraded broadcast channel, and b) an inner bound of the LPE-BC with COF for the case of two users and any number of layers. Next, an inner bound on the stability region (set of exogenous arrival rates for which packet arrival queues are stable) for the same model is derived. The capacity region inner bound generalizes past results for the two-user erasure BC, which is a special case of the LPE-BC with COF with only one layer. The novelty lies in the use of inter-user and inter-layer network coding retransmissions (for those packets that have only been received by the unintended user), where each random linear combination may involve packets intended for any user originally sent on any of the layers. For the case of $K = 2$ users and $Q \geq 1$ layers, the inner bounds to the capacity region and the stability region coincide; both strategically employ the novel retransmission protocol. For the case of $Q = 2$ layers, sufficient conditions are derived by Fourier-Motzkin elimination for the inner bound on the stability region to coincide with the capacity outer bound, thus showing that in those cases the capacity and stability regions coincide.

This paper considers the problem of code design for a channel where communications and radar systems coexist, modeled as having both Additive White Gaussian Noise (AWGN) and Additive Radar Interference (ARI). The issue of how to adapt or re-design convolutional codes (decoded by the Viterbi algorithm) and LDPC codes (decoded by the sum-product algorithm and optimized by using the EXIT chart method) to effectively handle the overall non-Gaussian ARI noise is investigated. A decoding metric is derived from the non-Gaussian ARI channel transition probability as a function of the Signal-to-Noise Ratio (SNR) and Interference-to-Noise Ratio (INR). Two design methodologies are benchmarked against a baseline "unaltered legacy system", where a code designed for AWGN-only noise, but used on the non-Gaussian ARI channel, is decoded by using the AWGN-only metric (i.e., as if INR is zero). The methodologies are: M1) codes designed for AWGN-only noise, but decoded with the new metric that accounts for both SNR and INR; and M2) codes optimized for the overall non-Gaussian ARI channel. Both methodologies give better average Bit Error Rate (BER) in the high INR regime compared to the baseline. In the low INR regime, both methodologies perform as the baseline since in this case the radar interference is weak. Interestingly, the performance improvement of M2 over M1 is minimal. In practice, this implies that specifications in terms of channel error correcting codes for commercially available wireless systems need not be changed, and that it suffices to use an appropriate INR-based decoding metric in order to effectively cope with the ARI.

Achievable error exponents for the one-way with noisy feedback and two-way AWGN channels are derived for the transmission of a finite number of messages $M$ using fixed block length $n$, under the almost sure (AS) and the expected block (EXP) power constraints. In the one-way setting under noisy AWGN feedback, it is shown that under the AS constraint and when the feedback link is much stronger than the direct link, active feedback leads to a larger gain over the non-feedback error exponent than passive feedback. Under the EXP constraint, a previously known error exponent for the transmission of two messages is generalized to any arbitrary but finite number of messages $M$. In the two-way setting, where each user has its own message to send in addition to (possibly) aiding in the transmission of feedback for the opposite direction, error exponent regions are defined and derived for the first time for the AWGN two-way channel under both AS and EXP power constraints. It is shown that feedback or interaction may lead to error exponent gains in one direction, possibly at the expense of a decrease in the error exponents attained in the other direction. The relationship between $M$ and $n$ supported by our achievability strategies is explored., Comment: 46 pages, 18 figures, Submitted to IEEE Transactions on Information Theory

In this paper, the capacity region of the Layered Packet Erasure Broadcast Channel (LPE-BC) with Channel Output Feedback (COF) available at the transmitter is investigated. The LPE-BC is a high-SNR approximation of the fading Gaussian BC recently proposed by Tse and Yates, who characterized the capacity region for any number of users and any number of layers when there is no COF. This paper derives capacity inner and outer bounds for the LPE-BC with COF for the case of two users and any number of layers. The inner bounds generalize past results for the two-user erasure BC, which is a special case of the LPE-BC with COF with only one layer. The novelty lies in the use of \emph{inter-user \& inter-layer network coding} retransmissions (for those packets that have only been received by the unintended user), where each random linear combination may involve packets intended for any user originally sent on any of the layers. Analytical and numerical examples show that the proposed outer bound is optimal for some LPE-BCs., Comment: 6 pages, 1 figure, submitted to 2019 IEEE International Conference on Communications (ICC)

This paper considers packet scheduling over a broadcast channel with packet erasures to multiple receivers with different messages (multiple uni-cast) each with possibly different hard deadline constraints. A novel metric is proposed and evaluated: the global deadline outage probability, which gives the probability that the hard communication deadline is not met for at least one of the receivers. The cut-set upper bound is derived and a scheduling policy is proposed to determine which receiver's packets should be sent in each time slot. This policy is shown to be optimal among all scheduling policies, i.e., it achieves all boundary points of cut-set upper bounds when the transmitter knows the erasure patterns for all the receivers ahead of making the scheduling decision. An expression for the global deadline outage probability is obtained for two receivers and is plotted and interpreted for various system parameters. These plots are not Monte-Carlo simulations, and hence the obtained expression may be used in the design of future downlink broadcast networks. Future extensions to per-user deadline outage probabilities as well as to scenarios with causal knowledge of the channel states are briefly discussed.

This paper considers a Strongly Asynchronous and Slotted Massive Access Channel (SAS-MAC) where $K_n:=e^{n\nu}$ different users transmit a randomly selected message among $M_n:=e^{nR}$ ones within a strong asynchronous window of length $A_n:=e^{n\alpha}$ blocks, where each block lasts $n$ channel uses. A global probability of error is enforced, ensuring that all the users' identities and messages are correctly identified and decoded. Achievability bounds are derived for the case that different users have similar channels, the case that users' channels can be chosen from a set which has polynomially many elements in the blocklength $n$, and the case with no restriction on the users' channels. A general converse bound on the capacity region and a converse bound on the maximum growth rate of the number of users are derived., Comment: under submission

Finding the underlying probability distributions of a set of observed sequences under the constraint that each sequence is generated i.i.d by a distinct distribution is considered. The number of distributions, and hence the number of observed sequences, are let to grow with the observation blocklength $n$. Asymptotically matching upper and lower bounds on the probability of error are derived., Comment: Under Submission

The adaptive zero-error capacity of discrete memoryless channels (DMC) with noiseless feedback has been shown to be positive whenever there exists at least one channel output "disprover", i.e. a channel output that cannot be reached from at least one of the inputs. Furthermore, whenever there exists a disprover, the adaptive zero-error capacity attains the Shannon (small-error) capacity. Here, we study the zero-error capacity of a DMC when the channel feedback is noisy rather than perfect. We show that the adaptive zero-error capacity with noisy feedback is lower bounded by the forward channel's zero-undetected error capacity, and show that under certain conditions this is tight.

This paper investigates the capacity of a communications channel that, in addition to additive white Gaussian noise, also suffers from interference caused by a co-existing radar transmission. The radar interference (of short duty-cycle and of much wider bandwidth than the intended communication signal) is modeled as an additive term whose amplitude is known and constant, but whose phase is independent and identically uniformly distributed at each channel use. The capacity achieving input distribution, under the standard average power constraint, is shown to have independent modulo and phase. The phase is uniformly distributed in $[0,2\pi]$. The modulo is discrete with countably infinitly many mass points, but only finitely many in any bounded interval. From numerical evaluations, a proper-complex Gaussian input is seen to perform quite well for weak radar interference. We also show that for very large radar interference, capacity is equal to $1/2\log (1 + S)$ and a proper-complex Gaussian input achieves it. It is concluded that the presence of the radar interference results in a loss of half of the degrees of freedom compared to an AWGN channel without radar interference., Comment: Under submission

In this paper, the trade-off between the number of transmissions (or burstiness) $K_n=e^{n\nu}$ of a user, the asynchronism level $A_n=e^{n\alpha}$ in a slotted strongly asynchronous channel, and the ability to distinguish $M_n=e^{nR}$ messages per transmission with vanishingly error probability is investigated in the asymptotic regime as blocklength $n$ goes to infinity. The receiver must locate and decode, with vanishing error probability in $n$, all of the transmitted messages. Achievability and converse bounds on the trade-off among $(R,\alpha,\nu)$ is derived. For cases where $\nu=0$ and $ R=0$, achievability and converse bounds coincide. A second model for a bursty user with random access in which the user may access and transmit a message in each block with probability $e^{-n\beta}$ in then considered. Achievability and converse bounds on the trade-off between $(R, \alpha, \beta)$ is also characterized. For cases where $\beta =\alpha$ and $R=0$, the achievability and converse bounds match., Comment: Under submission

The problem of estimating an arbitrary random vector from its observation corrupted by additive white Gaussian noise, where the cost function is taken to be the Minimum Mean $p$-th Error (MMPE), is considered. The classical Minimum Mean Square Error (MMSE) is a special case of the MMPE. Several bounds, properties and applications of the MMPE are derived and discussed. The optimal MMPE estimator is found for Gaussian and binary input distributions. Properties of the MMPE as a function of the input distribution, SNR and order $p$ are derived. In particular, it is shown that the MMPE is a continuous function of $p$ and SNR. These results are possible in view of interpolation and change of measure bounds on the MMPE. The `Single-Crossing-Point Property' (SCPP) that bounds the MMSE for all SNR values {\it above} a certain value, at which the MMSE is known, together with the I-MMSE relationship is a powerful tool in deriving converse proofs in information theory. By studying the notion of conditional MMPE, a unifying proof (i.e., for any $p$) of the SCPP is shown. A complementary bound to the SCPP is then shown, which bounds the MMPE for all SNR values {\it below} a certain value, at which the MMPE is known. As a first application of the MMPE, a bound on the conditional differential entropy in terms of the MMPE is provided, which then yields a generalization of the Ozarow-Wyner lower bound on the mutual information achieved by a discrete input on a Gaussian noise channel. As a second application, the MMPE is shown to improve on previous characterizations of the phase transition phenomenon that manifests, in the limit as the length of the capacity achieving code goes to infinity, as a discontinuity of the MMSE as a function of SNR. As a final application, the MMPE is used to show bounds on the second derivative of mutual information, that tighten previously known bounds.

This paper considers a Gaussian channel with one transmitter and two receivers. The goal is to maximize the communication rate at the intended/primary receiver subject to a disturbance constraint at the unintended/secondary receiver. The disturbance is measured in terms of minimum mean square error (MMSE) of the interference that the transmission to the primary receiver inflicts on the secondary receiver. The paper presents a new upper bound for the problem of maximizing the mutual information subject to an MMSE constraint. The new bound holds for vector inputs of any length and recovers a previously known limiting (when the length of vector input tends to infinity) expression from the work of Bustin $\textit{et al.}$ The key technical novelty is a new upper bound on the MMSE. This bound allows one to bound the MMSE for all signal-to-noise ratio (SNR) values $\textit{below}$ a certain SNR at which the MMSE is known (which corresponds to the disturbance constraint). This bound complements the `single-crossing point property' of the MMSE that upper bounds the MMSE for all SNR values $\textit{above}$ a certain value at which the MMSE value is known. The MMSE upper bound provides a refined characterization of the phase-transition phenomenon which manifests, in the limit as the length of the vector input goes to infinity, as a discontinuity of the MMSE for the problem at hand. For vector inputs of size $n=1$, a matching lower bound, to within an additive gap of order $O \left( \log \log \frac{1}{\sf MMSE} \right)$ (where ${\sf MMSE}$ is the disturbance constraint), is shown by means of the mixed inputs technique recently introduced by Dytso $\textit{et al.}$, Comment: Submitted to IEEE Transactions on Information Theory

This paper provides a survey of the state-of-the-art information theoretic analysis for overlay multi-user (more than two pairs) cognitive networks and reports new capacity results. In an overlay scenario, cognitive / secondary users share the same frequency band with licensed / primary users to efficiently exploit the spectrum. They do so without degrading the performance of the incumbent users, and may possibly even aid in transmitting their messages as cognitive users are assumed to possess the message(s) of primary user(s) and possibly other cognitive user(s). The survey begins with a short overview of the two-user overlay cognitive interference channel. The evolution from two-user to three-user overlay cognitive interference channels is described next, followed by generalizations to multi-user (arbitrary number of users) cognitive networks. The rest of the paper considers K-user cognitive interference channels with different message knowledge structures at the transmitters. Novel capacity inner and outer bounds are proposed. Channel conditions under which the bounds meet, thus characterizing the information theoretic capacity of the channel, for both Linear Deterministic and Gaussian channel models, are derived. The results show that for certain channel conditions distributed cognition, or having a cumulative message knowledge structure at the nodes, may not be worth the overhead as (approximately) the same capacity can be achieved by having only one global cognitive user whose role is to manage all the interference in the network. The paper concludes with future research directions., Comment: 7 figures, 16 pages, 1 table

This paper shows that for the two-user Gaussian Interference Channel (G-IC) Treating Interference as Noise without Time Sharing (TINnoTS) achieves the closure of the capacity region to within either a constant gap, or to within a gap of the order O(logln(min(S,I))) where S is the largest Signal to Noise Ratio (SNR) on the direct links and I is the largest Interference to Noise Ratio (INR) on the cross links. As a consequence, TINnoTS is optimal from a generalized Degrees of Freedom (gDoF) perspective for all channel gains except for a subset of zero measure. TINnoTS with Gaussian inputs is known to be optimal to within 1/2 bit for a subset of the weak interference regime. Surprisingly, this paper shows that TINnoTS is gDoG optimal in all parameter regimes, even in the strong and very strong interference regimes where joint decoding of Gaussian inputs is optimal. For approximate optimality of TINnoTS in all parameter regimes it is critical to use non-Gaussian inputs. This work thus proposes to use mixed inputs as channel inputs where a mixed input is the sum of a discrete and a Gaussian random variable. Interestingly, compared to the Han-Kobayashi inner bound, the discrete part of a mixed input is shown to effectively act as a common message in the sense that, although treated as noise, its effect on the achievable rate region is as if it were jointly decoded together with the desired messages at a non-intended receiver. The practical implication is that a discrete interfering input is a 'friend', while a Gaussian interfering input is in general a 'foe'. Since TINnoTS requires neither joint decoding nor time sharing, the results of this paper are applicable to a variety of oblivions or asynchronous channels, such as the block asynchronous G-IC (which is not an information stable) and the G-IC with partial codebook knowledge at one or more receivers.

The presence of signal outage, due to shadowing and blockage, is expected to be the main bottleneck in millimeter wave (mmWave) networks. Moreover, with the anticipated vision that mmWave networks would have a dense deployment of base stations, interference from strong line-of-sight base stations increases too, thus further increasing the probability of outage. To address the issue of reducing outage, this paper explores the possibility of base station cooperation in the downlink of a mmWave heterogenous network. The main focus of this work is showing that, in a stochastic geometry framework, cooperation from randomly located base stations decreases outage probability. With the presumed vision that less severe fading will be experienced due to highly directional transmissions, one might expect that cooperation would increase the coverage probability; our numerical examples suggest that is in fact the case. Coverage probabilities are derived accounting for: different fading distributions, antenna directionality and blockage. Numerical results suggest that coverage with base station cooperation in dense mmWave systems and with no small scale fading considerably exceeds coverage with no cooperation. In contrast, an insignificant increase is reported when mmWave networks are less dense with a high probability of signal blockage and with Rayleigh fading., Comment: 30 pages, 8 figures