Consider a target moving at a constant velocity on a unit-circumference circle, starting at an arbitrary location. To acquire the target, any region of the circle can be probed to obtain a noisy measurement of the target’s presence, where the noise level increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity and a given reliability, we provide an asymptotical characterization of the optimal tradeoff between time and resolution. Considering an asymptotically diminishing error probability, we derive the maximal targeting rate, and show that in contrast to the well-studied case of constant measurement noise, measurement dependent noise incurs a multiplicative gap in the maximal targeting rate between adaptive and non-adaptive search strategies. Moreover, for all rates below this maximal rate, our adaptive strategy attains the optimal rate-reliability tradeoff. We further show that accounting for a target moving at an unknown fixed velocity, the optimal non-adaptive search strategy incurs a factor of at least two in the maximal targeting rate.

In this paper, we study linear encoding for a pair of correlated Gaussian sources transmitted over a two-user Gaussian broadcast channel in the presence of unit-delay noiseless feedback, abbreviated as the GBCF. Each pair of source samples is transmitted using a linear transmission scheme in a finite number of channel uses. We investigate three linear transmission schemes: A scheme based on the Ozarow-Leung (OL) code, a scheme based on the linear quadratic Gaussian (LQG) code of Ardestanizadeh et al., and a novel scheme derived in this paper using a dynamic programming (DP) approach. For the OL and LQG schemes we present lower and upper bounds on the minimal number of channel uses needed to achieve a target mean-square error (MSE) pair. For the LQG scheme in the symmetric setting, we identify the optimal scaling of the sources, which results in a significant improvement of its finite horizon performance, and, in addition, characterize the (exact) minimal number of channel uses required to achieve a target MSE. Finally, for the symmetric setting, we show that for any fixed and finite number of channel uses, the DP scheme achieves an MSE lower than the MSE achieved by either the LQG or the OL schemes.

This work focuses on the minimum transmission energy required for communicating a pair of correlated Gaussian sources over a two-user Gaussian broadcast channel with noiseless and causal channel output feedback (GBCF). We study the fundamental limit on the required transmission energy for broadcasting a pair of source samples, such that each source can be reconstructed at its respective receiver to within a target distortion, when the source-channel bandwidth ratio is not restricted. We derive a lower bound and three distinct upper bounds on the minimum required energy. For the upper bounds we analyze three transmission schemes: Two schemes are based on separate source-channel coding, and apply coding over multiple samples of source pairs. The third scheme is based on joint source-channel coding obtained by extending the Ozarow-Leung (OL) transmission scheme, which applies uncoded linear transmission. Numerical simulations show that despite its simplicity, the energy-distortion tradeoff of the OL-based scheme is close to that of the better separation-based scheme, which indicates that the OL scheme is attractive for energy-efficient source transmission over GBCFs.

We consider a search problem in which multiple targets are uniformly placed on the unit interval. An agent, who might not know the number of targets in advance, is interested in acquiring all targets to within some resolution δ as quickly as possible. To that end, at each time unit, the agent can probe any region of the unit interval for the presence of targets but the associated measurement noise increases with the size of the probed region. We characterize the maximal targeting rate, the optimal tradeoff between resolution and expected search time, with adaptive and non-adaptive search strategies, highlighting the advantage of adaptive strategies. We show that even when the number of targets is known, in contrast to the case of constant measurement noise, there is a multiplicative gap between the performance of adaptive and non-adaptive search. This gap, however, diminishes as the number of targets grow.

We consider the estimation of a standard Gaussian random variable under an observation attack where an adversary may add a zero mean Gaussian noise with variance in a bounded, closed interval to an otherwise noiseless observation. A straightforward approach would entail either ignoring the attack and simply using an optimal estimator under normal operation or taking the worst-case attack into account and using a minimax estimator that minimizes the cost under the worst-case attack. In contrast, we seek to characterize the optimal tradeoff between the MSE under normal operation and the MSE under the worst-case attack. Equivalently, we seek a minimax estimator for any fixed prior probability of attack. Our main result shows that a unique minimax estimator exists for every fixed probability of attack and is given by the Bayesian estimator for a least-favorable prior on the set of possible variances. Furthermore, the least-favorable prior is unique and has a finite support. While the minimax estimator is linear when the probability of attack is 0 or 1, our numerical results show that the minimax linear estimator is far from optimal for all other probabilities of attack and a simple nonlinear estimator does much better.

We study the uncoded transmission of a bivariate Gaussian source over a two-user symmetric Gaussian broadcast channel with a unit-delay noiseless feedback (GBCF), assuming that each (uncoded) source sample is transmitted using a finite number of channel uses, and that the transmission scheme is linear. We consider three transmission schemes: The scheme of Ardestanizadeh et al., which is based on linear quadratic Gaussian (LQG) control theory, the scheme of Ozarow and Leung (OL), and a novel scheme derived in this work designed using a dynamic programing (DP) approach. For the LQG scheme we characterize the minimal number of channel uses needed to achieve a specified mean-square error (MSE). For the OL scheme we present lower and upper bounds on the minimal number of channel uses needed to achieve a specified MSE, which become tight when the signal-to-noise ratio approaches zero. Finally, we show that for any fixed and finite number of channel uses, the proposed DP scheme achieves MSE lower than the MSE achieved by either the LQG or the OL schemes.

In this work, we consider linear-feedback schemes for the two-user Gaussian broadcast channel with noiseless feedback. We extend the transmission scheme of [Ozarow and Leung, 1984] by applying estimators with memory instead of the memoryless estimators used by Ozarow and Leung (OL) in their original work. A recursive formulation of the mean square errors achieved by the proposed estimators is provided, along with a proof for the existence of a fixed point. This enables characterizing the achievable rates of the extended scheme. Finally, via numerical simulations it is shown that the extended scheme can improve upon the original OL scheme in terms of achievable rates, as well as achieve a low probability of error after a finite number of channel uses.

We investigate the combination between causal/zero-delay source coding and information-theoretic secrecy. Two source coding models with secrecy constraints are considered. We start by considering zero-delay perfectly secret lossless transmission of a memoryless source. We derive bounds on the key rate and coding rate needed for perfect zero-delay secrecy. In this setting, we consider two models that differ by the ability of the eavesdropper to parse the bit-stream passing from the encoder to the legitimate decoder into separate messages. We also consider causal source coding with a fidelity criterion and side information at the decoder and the eavesdropper. Unlike the zero-delay setting where variable-length coding is traditionally used but might leak information on the source through the length of the codewords, in this setting, since delay is allowed, block coding is possible. We show that in this setting, a separation of encryption and causal source coding is optimal.

Consider a target moving with a constant velocity on a unit-circumference circle, starting from an arbitrary location. To acquire the target, any region of the circle can be probed for its presence, but the associated measurement noise increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity, we characterize the optimal tradeoff between time and resolution (i.e., maximal rate), and show that in contrast to the case of constant measurement noise, measurement dependent noise incurs a multiplicative gap between adaptive search and non-adaptive search. Moreover, our adaptive scheme attains the optimal rate-reliability tradeoff. We further show that for optimal non-adaptive search, accounting for an unknown velocity incurs a factor of two in rate.

We consider zero-delay, single-user, and multi-user source coding with an average distortion constraint and decoder side information. The zero-delay constraint translates into causal (sequential) encoder and decoder pairs as well as the use of instantaneous codes. For the single-user setting, we show that optimal performance is attained by time sharing at most two scalar encoder-decoder pairs, that use zero-error side information codes. Side information look-ahead is shown to be useless in this setting. Furthermore, we show that even without delay constraints, if either the encoder or decoder are restricted a priori to be scalar, the performance loss cannot be compensated by the other component, which can be scalar as well without further loss. Finally, we show that the multi-terminal source coding problem can be solved in the zero-delay regime and the rate-distortion region is provided.

We consider the zero-delay version of the Wyner-Ziv problem. The zero-delay constraint translates into causal (sequential) encoder and decoder pairs as well as the use of instantaneous codes. We show that optimal performance is attained by time sharing at most two scalar encoder-decoder pairs, that use zero-error side information codes. Side information lookahead is shown to be useless in this setting. We show that the restriction to causal encoding functions is the one that causes the performance degradation, compared to unrestricted systems, and not the sequential decoders or instantaneous codes.

We investigate two source coding problems with secrecy constraints. In the first problem we consider real-time fully secure transmission of a memoryless source. We show that although classical variable-rate coding is not an option since the lengths of the codewords leak information on the source, the key rate can be as low as the average Huffman codeword length of the source. In the second problem we consider causal source coding with a fidelity criterion and side information at the decoder and the eavesdropper. We show that when the eavesdropper has degraded side information, it is optimal to first use a causal rate distortion code and then encrypt its output with a key.

The output of a discrete Markov source is to be encoded instantaneously by a variable-rate encoder and decoded by a finite-state decoder. Our performance measure is a linear combination of the distortion and the instantaneous rate. Structure theorems, pertaining to the encoder and next-state functions, are derived for every given finite-state decoder, which can have access to side information.

We consider a broadcast channel with a degraded message set, in which a single transmitter sends a common message to two receivers and a private message to one of the receivers only. The main goal of this work is to find new lower bounds to the error exponents of the strong user, the one that should decode both messages, and of the weak user, that should decode only the common message. Unlike previous works, where suboptimal decoders were used, the exponents we derive in this work pertain to optimal decoding and depend on both rates. We take two different approaches. The first approach is based, in part, on variations of Gallager-type bounding techniques that were presented in a much earlier work on error exponents for erasure/list decoding. The resulting lower bounds are quite simple to understand and to compute. The second approach is based on a technique that is rooted in statistical physics, and it is exponentially tight from the initial step and onward. This technique is based on analyzing the statistics of certain enumerators. Numerical results show that the bounds obtained by this technique are tighter than those obtained by the first approach and previous results. The derivation, however, is more complex than the first approach and the retrieved exponents are harder to compute.

We extend Witsenhausen's structure theorem for real-time source coding, so as to accommodate both variable-rate coding and causal side information at the decoder.

The analysis of random coding error exponents pertaining to optimal decoding in a degraded broadcast with degraded message sets is revisited. Instead of using Jensens inequality as well as some other inequalities in the derivation, we demonstrate that, after an initial step, an exponentially tight analysis can be carried out by assessing the relevant moments of a certain type class enumerator.

We consider a degraded broadcast channel with maximum likelihood decoders and derive lower bounds on the error exponent of each user. Unlike earlier results, our exponents pertain to optimal decoding and include both rates.