The ubiquitous time-delay estimation (TDE) problem becomes nontrivial when sensors are non-co-located and communication between them is limited. Building on the recently proposed "extremum encoding" compression-estimation scheme, we address the critical extension to complex-valued signals, suitable for radio-frequency (RF) baseband processing. This extension introduces new challenges, e.g., due to unknown phase of the signal of interest and random phase of the noise, rendering a naïve application of the original scheme inapplicable and irrelevant. In the face of these challenges, we propose a judiciously adapted, though natural, extension of the scheme, paving its way to RF applications. While our extension leads to a different statistical analysis, including extremes of non-Gaussian distributions, we show that, ultimately, its asymptotic behavior is akin to the original scheme. We derive an exponentially tight upper bound on its error probability, corroborate our results via simulation experiments, and demonstrate the superior performance compared to two benchmark approaches.

Consider the problem of distributed binary hypothesis testing with two terminals, where the decision is made at one of them (the “receiver”). We study the exponent of the error probability of the second type. Previously, an achievable exponent was derived by Shimokawa, Han, and Amari using a “quantization and binning” scheme. We propose a simple modification on the receiver’s decision rule in this scheme to attain a better exponent.

Motivated by the proliferation of mobile devices, we consider a basic form of the ubiquitous problem of time-delay estimation (TDE), but with communication constraints between two non co-located sensors. In this setting, when joint processing of the received signals is not possible, a compression technique that is tailored to TDE is desirable. For our basic TDE formulation, we develop such a joint compression-estimation strategy based on the notion of what we term "extremum encoding", whereby we send the index of the maximum of a finite-length time-series from one sensor to another. Subsequent joint processing of the encoded message with locally observed data gives rise to our proposed time-delay "maximum-index"-based estimator. We derive an exponentially tight upper bound on its error probability, establishing its consistency with respect to the number of transmitted bits. We further validate our analysis via simulations, and comment on potential extensions and generalizations of the basic methodology.

We consider a line network of nodes connected by additive white Gaussian noise channels and equipped with local feedback. We study the velocity at which information spreads over this network. For the transmission of a data packet, we derive an explicit positive lower bound on the velocity for any packet size. Furthermore, we consider streaming, that is, transmission of data packets that is generated at a given average arrival rate. We show that a positive velocity exists as long as the arrival rate is below the individual Gaussian channel capacity and provide an explicit lower bound. Our analysis involves applying pulse-amplitude modulation to the data (successively in the streaming case) and using linear mean-squared error estimation at the network nodes. Due to the analog-linear nature of the scheme, the results extend to any additive noise. For general noise, we derive exponential error-probability bounds. Moreover, for (sub-)Gaussian noise, we show doubly-exponential behavior, which reduces to the celebrated Schalkwijk-Kailath scheme when considering a single node. By viewing the constellation as an “analog source”, we also provide bounds on the exponential decay of the mean-squared error of source transmission over the network.

We consider the Stein exponent of distributed hypothesis testing (in the side-information setting). Decades since the problem was first formulated, the exponent is still an open problem, except for some special cases. Rahman and Wagner have derived an upper bound, by providing the decoder with side information that creates conditional independence, where single-letterization is possible. We propose a new technique, inspired by their work, which provides side information in a more gradual manner. For the special case of testing for Gaussian correlations, we show that our technique strictly improves upon the known bounds, and in particular it gives a finite upper bound for parameters where no such non-trivial bound existed.

We consider the problem of discrimination between two pure quantum states. It is well known that the optimal measurement under both the error-probability and log-loss criteria is a projection, while under an “erasure-distortion” criterion it is a three-outcome positive operator-valued measure (POVM). These results were derived separately. We present a unified approach which finds the optimal measurement under any distortion measure that satisfies a convexity relation with respect to the Bhattacharyya distance. Namely, whenever the measure is relatively convex (resp. concave), the measurement is the projection (resp. three-outcome POVM) above. The three above-mentioned results are obtained as special cases of this simple derivation. As for further measures for which our result applies, we prove that Rényi entropies of order 1 and above (resp. 1/2 and below) are relatively convex (resp. concave). A special setting of great practical interest, is the discrimination between two coherent-light waveforms. In a remarkable work by Dolinar it was shown that a simple detector consisting of a photon counter and a feedback-controlled local oscillator obtains the quantum-optimal error probability. Later it was shown that the same detector (with the same local signal) is also optimal in the log-loss sense. By applying a similar convexity approach, we obtain in a unified manner the optimal signal for a variety of criteria.

The classical binary hypothesis testing problem is revisited. We notice that when one of the hypotheses is composite, there is an inherent difficulty in defining an optimality criterion that is both informative and well-justified. For testing in the simple normal location problem (that is, testing for the mean of multivariate Gaussians), we overcome the difficulty as follows. In this problem there exists a natural “hardness” order between parameters as for different parameters the error-probabilities curves (when the parameter is known) are either identical, or one dominates the other. We can thus define minimax performance as the worst-case among parameters which are below some hardness level. Fortunately, there exists a universal minimax test, in the sense that it is minimax for all hardness levels simultaneously. Under this criterion we also find the optimal test for composite hypothesis testing with training data. THIS criterion extends to the wide class of local asymptotic normal models, in an asymptotic sense where the approximation of the error probabilities is additive. Since we have the asymptotically optimal tests for composite hypothesis testing with and without training data, we quantify the loss of universality and gain of training data for these models.

Dolinar's receiver is an architecture for distinguishing between two possible coherent states, using a photon detector and a local signal which may depend on past detector measurements. The optimal local signal satisfies very favorable properties: it is independent of the time horizon, and the resulting error probability is independent of the measurements. It was also shown that the same signal is optimal in the sense of maximizing the mutual information between the identity of the state and the measurements. In this work we show that the same signal is optimal for the optimization of the expected value of a wide class of objective functions. Our proof is based entirely on convex optimization and functional analysis, without resorting to any "quantum" arguments.

This work addresses distributed binary hypothesis testing, where observations at two terminals are jointly Gaussian, each one standard, with two possible correlation coefficients. We assume that one of the terminals is colocated with the decision center, and focus on a single (Stein) error exponent. Rather than the traditional exponent that is defined with respect to the source blocklength, we assume the source data to be unlimited, and consider the error exponent as a function of the communication message length. We examine two different approaches, one by quantization and the other by sending the index of the maximum, and find them to yield the same exponent. We further find that binning improves upon both approaches in the same way. Finally we compare the obtained exponents to two upper bounds and determine the optimal exponent in some very special cases.

We consider the classic joint source-channel coding problem of transmitting a memoryless source over a memoryless channel. The focus of this work is on the rate of convergence of the smallest attainable expected distortion to its asymptotic value, as a function of blocklength n. Our main result is that in general the convergence rate is not faster than n-1/2. In particular, we show that for the problem of transmitting i.i.d uniform bits over a binary symmetric channels with Hamming distortion, the smallest attainable distortion (bit error rate) is at least Ω(n-1/2) above the asymptotic value, if the "bandwidth expansion ratio" is above 1.

The distributed hypothesis testing (DHT) problem is considered, in which the joint distribution of a pair of sequences present at separated terminals, is governed by one of two possible hypotheses. The decision needs to be made by one of the terminals (the "decoder"). The other terminal (the "encoder") uses a noisy channel in order to help the decoder with the decision. This problem can be seen as a generalization of the side-information variant of the DHT problem, where the rate-limited link is replaced by a noisy channel. A recent work by Salehkalaibar and Wigger has derived an achievable Stein exponent for this problem, by employing concepts from the DHT scheme of Shimokawa et al., and from unequal error protection coding for a single special message. In this work we extend the view to a trade-off between the two error exponents, additionally building on multiple codebooks and two special messages with unequal error protection. As a by product, we also present an achievable exponent trade-off for a rate-limited link, which generalizes Shimokawa et al..

Two problems, namely multiple-description source coding and joint source-channel broadcasting of a common source, are addressed. For the multiple-description problem, we revisit Ozarow's technique for establishing impossibility results, and extend it to general sources and distortion measures. For the problem of sending a source over a broadcast channel, we revisit the bounding technique of Reznik, Feder and Zamir, and extend it to general sources, distortion measures and broadcast channels. Although the obtained bounds do not improve over existing results in the literature, they are relatively easy to evaluate, and their derivation reveals the similarities between the two bounding techniques.

The distributed hypothesis testing problem with full side-information is studied. The trade-off (reliability function) between the two types of error exponents under limited rate is studied in the following way. First, the problem is reduced to the problem of determining the reliability function of channel codes designed for detection (in analogy to a similar result which connects the reliability function of distributed lossless compression and ordinary channel codes). Second, a single-letter random-coding bound based on a hierarchical ensemble, as well as a single-letter expurgated bound, are derived for the reliability of channel-detection codes. Both bounds are derived for a system which employs the optimal detection rule. We conjecture that the resulting random-coding bound is ensemble-tight, and consequently optimal within the class of quantization-and-binning schemes.

Upper bounds on the error probability of channel coding are derived for codebooks drawn from random codebook ensembles with various independence and symmetry assumptions. For regular decoding (without an erasure option), the random coding union bound of Polyanskiy et al. is improved by carefully taking ties (equal likelihood scores) into account. It is shown that the improved bound is always better than threshold-decoding based bounds. The framework is extended to the case of decoding with an erasure option, deriving several achievability bounds in the same spirit. In order to exemplify the merits of the approach, the bounds are evaluated for the case of pairwise-independent uniformly-distributed ensembles (e.g., shifted random linear codes).

The problem of sending a secret message over the Gaussian multiple-input multiple-output (MIMO) wiretap channel is studied. While the capacity of this channel is known, it is not clear how to construct optimal coding schemes that achieve this capacity. In this paper, we use linear operations along with successive interference cancellation to attain effective parallel single-antenna wiretap channels. By using independent scalar Gaussian wiretap codebooks over the resulting parallel channels, the capacity of the MIMO wiretap channel is achieved. The derivation of the schemes is based upon joint triangularization of the channel matrices. We find that the same technique can be used to rederive capacity expressions for the MIMO wiretap channel in a way that is simple and closely connected to a transmission scheme. This technique allows to extend the previously proven strong security for scalar Gaussian channels to the MIMO case. We further consider the problem of transmitting confidential messages over a two-user broadcast MIMO channel. For that problem, we find that derivation of both the capacity and a transmission scheme is a direct corollary of the proposed analysis for the MIMO wiretap channel.

Ozarow's test channel for the quadratic Gaussian (QG) multiple description (MD) problem consists of two correlated AWGN channels. It is known that simply replacing the AWGN channels by quantizers with equivalent statistical properties as the channels, will generally not lead to a rate-distortion optimal realization of the MD rate-distortion function. We have previously proposed a symmetric two-channel model for the QG MD problem for the case, where the two noise terms have equal variances. We show in this paper, that by replacing the AWGN channels of this model by quantizers that are statistical equivalent to the channels, will under high-resolution assumption be rate-distortion optimal. We furthermore extend this symmetric two-channel model to the asymmetric case, and provide a simple suboptimal implementation of the channel based on scalar quantizers. Simulations are provided to show the performance of the proposed implementation.

In this paper, we obtain an improved lower bound on the error exponent of the memoryless multiple-access channel via the use of linear codes, thus demonstrating that structure can be beneficial even when capacity may be achieved via random codes. We show that if the multiple-access channel is additive over a finite field, then any error probability, and hence any error exponent, achievable by a linear code for the associated single-user channel, is also achievable for the multiple-access channel. In particular, linear codes allow to attain joint expurgation, and hence, attain the single-user expurgated exponent of the single-user channel, whenever the latter is achieved by a uniform distribution. Thus, for additive channels, at low rates, where expurgation is needed, our approach strictly improves performance over previous results, where expurgation was used for at most one of the users. Even when the multiple-access channel is not additive, it may be transformed into such a channel. While the transformation is information-lossy, we show that the distributed structure gain in some “nearly additive” cases outweighs the loss. Finally, we apply a similar approach to the Gaussian multiple-access channel. While we believe that due to the power constraints, it is impossible to attain the singleuser error exponent, we do obtain an improvement over the best known achievable error exponent, given by Gallager, for certain parameters. This is accomplished using a nested lattice triplet with judiciously chosen parameters.

In the scalar dirty multiple-access channel, in addition to Gaussian noise, two additive interference signals are present, each known non-causally to a single transmitter. It was shown by Philosof et al. that for strong interferences, an independent identically distributed ensemble of codes does not achieve the capacity region. Rather, a structured-codes approach was presented that was shown to be optimal in the limit of high signal-to-noise ratios, where the sum capacity is dictated by the minimal (“bottleneck”) channel gain. In this paper, we consider the multiple-input multiple-output (MIMO) variant of this setting. In order to incorporate structured codes in this case, one can utilize matrix decompositions that transform the channel into effective parallel scalar dirty multiple-access channels. This approach, however, suffers from a “bottleneck” effect for each effective scalar channel and, therefore, the achievable rates strongly depend on the chosen decomposition. It is shown that a recently proposed decomposition, where the diagonals of the effective channel matrices are equal up to a scaling factor, is optimal at high signal-to-noise ratios, under an equal rank assumption. This approach is then extended to any number of transmitters. Finally, an application to physical-layer network coding for the MIMO two-way relay channel is presented.

Multiple-input multiple-output (MIMO) radar systems have been shown to offer superior performance in direction of arrival (DOA) estimation applications compared to their phased array counterparts. The performance of these systems has been studied under various probing field-target interaction mechanisms. However, to the best of our knowledge, these have been restricted to linearized models. Motivated by various nonlinear imaging modalities we study DOA estimation in far field MIMO radar systems in conjunction with a power-law nonlinear probing field-target interaction mechanism and show that the nonlinearity increases the number of identifiable targets with a given number of antenna array elements.

In the scalar dirty multiple-access channel, in addition to Gaussian noise, two additive interference signals are present, each known non-causally to a single transmitter. It was shown by Philosof et al. that for strong interferences, an i.i.d. ensemble of codes does not achieve the capacity region. Rather, a structured-codes approach was presented, which was shown to be optimal in the limit of high signal-to-noise ratios (SNRs), where the sum-capacity is dictated by the minimal (“bottleneck”) channel gain. In the present work, we consider the multiple-input multiple-output (MIMO) variant of this setting. In order to incorporate structured codes in this case, one can utilize matrix decompositions, which transform the channel into effective parallel scalar dirty multiple-access channels. This approach however suffers from a “bottleneck” effect for each effective scalar channel and therefore the achievable rates strongly depend on the chosen decomposition. It is shown that a recently proposed decomposition, where the diagonals of the effective channel matrices are equal up to a scaling factor, is optimal at high SNRs, under an equal rank assumption.

We consider the problem of distributed binary hypothesis testing of two sequences that are generated by a doubly binary symmetric source. Each sequence is observed by a different terminal. The two hypotheses correspond to different levels of correlation between the two source components, i.e., the i.i.d. probability of the difference between the two sequences. The terminals communicate with a decision function via equal-rate noiseless links. We analyze the tradeoff between the exponential decay of the error probabilities of the hypothesis test and the communication rate. As Körner-Marton coding is known to minimize the rate in the corresponding distributed compression problem of conveying the difference sequence, it constitutes a natural candidate for the present setting. Indeed, using this scheme we derive achievable error exponents. Interestingly, these coincide with part of the optimal tradeoff without communication constraints, even when the rate is below the Körner-Marton rate for one of the hypotheses.

The problem of finite-blocklength lossy compression is considered. Motivated by troubling behavior of the rate expressions under an excess-distortion probability constraint, we define the mean excess distortion criterion. We evaluate the asymptotic performance of various settings under this criterion, and show that sharp and insightful rate bounds can be derived.

A framework is developed for decode-and-forward-based relaying using standard coding and decoding that are good for the single-input single-output (SISO) additive white Gaussian noise channel. The framework is applicable to various scenarios and is demonstrated for several important cases. Each of these scenarios is transformed into an equivalent Gaussian multiple-input multiple-output (MIMO) common-message broadcast problem, which proves useful even when all links are SISO ones. Over the effective MIMO broadcast channel, a recently developed Gaussian MIMO common-message broadcast scheme is applied. This scheme transforms the MIMO links into a set of parallel SISO channels with no loss of mutual information, using linear pre- and post-processing combined with successive decoding. Over these resulting SISO channels, off-the-shelf scalar codes may be used.

It is well known that Shannon's rate-distortion function (RDF) in the colored quadratic Gaussian (QG) case can be parametrized via a single Lagrangian variable (the water level in the reverse water filling solution). In this paper, we show that the symmetric colored QG multiple description (MD) RDF in the case of two descriptions can be parametrized in the spectral domain via two Lagrangian variables, which control the tradeoff between the side distortion, the central distortion, and the coding rate. This spectral-domain analysis is complemented by a time-domain scheme-design approach: we show that the symmetric colored QG MD RDF can be achieved by combining ideas of delta-sigma modulation and differential pulse-code modulation. In particular, two source prediction loops, one for each description, are embedded within a common noise-shaping loop, whose parameters are explicitly found from the spectral-domain characterization.

We consider the problem of transmitting confidential messages over a two-user broadcast multiple-input multiple-output (MIMO) channel. Surprisingly, the capacity region of this setting under a covariance matrix constraint was shown by Liu et al. to be rectangular. That is, there is no tension, and both users can attain their respective MIMO wiretap capacities, simultaneously. In this work, we provide a new derivation of this result by proposing an alternative achievability scheme for the corner point of the capacity region. This derivation, in addition to being considerably shorter and simpler than the original, also provides a practical transmission scheme, in the sense that the codes used are scalar (single-antenna) ones. We use two main ingredients. The first is the explicit optimal input covariance matrix of Bustin et al. for the MIMO wiretap channel under a covariance matrix constraint, which we also re-derive in a simple manner. The second is a dirty-paper variant of a recently proposed optimal scheme for the MIMO wiretap channel, which uses scalar codes. The proposed treatment demonstrates the connection between the confidential broadcast problem and the MIMO wiretap one: the former almost reduces to the latter, except for the use of dirty-paper coding which is not mandatory in MIMO wiretap; the work sheds light on the reason for this difference.

We investigate the fundamental limits of communication over optical on-off-keying channels with crosstalk, where a light pulse may span over multiple time slots or spatial pixels, and the receiver is equipped with single-photon detectors. First, we analyze achievable rates of communication over such channels, and observe that increasing transmission power (expected number of photons emitted per slot or pixel) does not necessarily lead to higher rates. Under simple but reasonable models, the highest rates are often achieved in a low-photon regime, with an average of 3 to 7 photons received in each slot or pixel. We further characterize the tradeoff between information rate and photon efficiency (in terms of the expected number of bits transmitted per photon) in the presence of crosstalk. Finally, we develop guidelines for slot length and pixel size selection for different application scenarios. Our analysis reveals that optimum optical-communication systems do not minimize the level of crosstalk.

The problem of sending a secret message over the multiple-input multiple-output (MIMO) wiretap Gaussian channel is studied. While the capacity of this channel is known, it is not clear how to construct optimal coding schemes that achieve this capacity. In this work we show how to use linear operations along with successive interference cancellation in order to reduce the problem to that of designing optimal codes for the single-antenna additive-noise Gaussian wiretap channel. Much like popular communication techniques in the absence of an eavesdropper, the data is carried over parallel streams. The design approach is flexible enough to allow for using the same scalar wiretap code over all streams, or alternatively to use different scalar wiretap codes over parallel sub-channels without successive interference cancellation. This approach is applicable to more involved secrecy settings, by adjusting the linear operations performed by the encoder, and by jointly processing several channel uses.

The problem of sending a secret message over the Gaussian multiple-input multiple-output wiretap channel is studied. In a recent work, we have proposed a layered coding scheme where a scalar wiretap code is used in each layer, and successive interference cancellation (SIC) is carried at the legitimate receiver. By a proper rate allocation across the layers, we showed that this scheme satisfies the secrecy constraint at the eavesdropper and achieves the secrecy capacity. However, the existence of the scalar codes was based upon a random coding argument. In this work we take a further step and show how the scheme can be based upon any codes that are good for the ordinary (non-secrecy) additive white Gaussian noise channel. As any stage of the SIC process is equivalent to achieving a corner point of a Gaussian multiple-access channel (MAC) capacity region, the class of codes used needs to be good for the MAC under SIC. Since in the secrecy analysis of our layered scheme, it suffices at each stage to consider a genie-aided eavesdropper that performs SIC, the coding task reduces to guaranteeing secrecy for corner points of induced MACs to the eavesdropper. Structured generation of such codes from ordinary ones is discussed.

The Gaussian parallel relay network, introduced by Schein and Gallager, consists of a concatenation of a Gaussian additive broadcast channel from a single encoder to a layer of relays followed by a Gaussian multiple-access channel from the relays to the final destination (decoder), where all noises are independent. This setup exhibits an inherent conflict between digital and analog relaying; while analog relaying [known as amplify-and-forward (A&F)] suffers from noise accumulation, digital relaying (known as decode-and-forward) looses the potential coherence gain in combining the relay noises at the decoder. For a large number of relays, the coherence gain is large, and thus analog relaying has better performance; however, it is limited to white channels of equal bandwidth. In this paper, we present a generalization of the analog approach to the case of bandwidth mismatch. Our strategy, coined rematch and forward (R&F), is based upon applying joint source-channel coding techniques that belong to a certain class of maximally analog schemes. Using such techniques, R&F converts the bandwidth of the broadcast section to that of the multiple-access section, creating an equivalent matched-bandwidth network over which A&F is applied. It is shown that this strategy exploits the full bandwidth of the individual channels, without sacrificing the coherence gain offered by A&F. Specifically, for given individual-link capacities, R&F remains within a constant gap from the network capacity for any number of relays and any bandwidth ratio between the sections. Finally, the approach is extended to the case of colored channels.

This paper considers the distribution of a secret key over an optical (bosonic) channel in the regime of high photon efficiency, i.e., when the number of secret key bits generated per detected photon is high. While, in principle, the photon efficiency is unbounded, there is an inherent tradeoff between this efficiency and the key generation rate (with respect to the channel bandwidth). We derive asymptotic expressions for the optimal generation rates in the photon-efficient limit, and propose schemes that approach these limits up to certain approximations. The schemes are practical, in the sense that they use coherent or temporally entangled optical states and direct photodetection, all of which are reasonably easy to realize in practice, in conjunction with off-the-shelf classical codes.

In the above-referenced paper, typesetting errors caused mismatch between labels of schemes and subscripts in equations. Schemes S-3, S-4, and S-5 should be relabeled S-1, S-2, and S-3, respectively.

An efficient sparse antenna array architecture is developed for coherent imaging of sparse but otherwise unknown scenes. In this architecture, the array elements form a periodic nonuniform pattern. Using analysis that explicitly takes into account the presence of noise, we develop an efficient pattern design procedure based on co-arrays, describe an efficient scene support recovery algorithm as part of image reconstruction in the form of a modification to the MUSIC algorithm, and discuss a failure detection technique based on evaluating “back-projection” error. Since our development exploits a close connection to multi-coset sampling of bandlimited waveforms, our results may in turn may also be useful in the design of those systems.

Upper bounds on the error probability in channel coding are considered, improving the RCU bound by taking into account events, where the likelihood of the correct codeword is tied with that of some competitors. This bound is compared to various previous results, both qualitatively and quantitatively; it is shown to be the tightest bound with respect to previous bounds with the same computational complexity. With respect to maximal error probability of linear codes, it is observed that when the channel is additive, the derivation of bounds, as well as the assumptions on the admissible encoder and decoder, simplify considerably.

We consider the error exponent of the memoryless multiple-access (MAC) channel. We show that if the MAC channel is modulo-additive, then any error probability, and hence any error exponent, achievable by a linear code for the corresponding single-user channel, is also achievable for the MAC channel. Specifically, for an alphabet of prime cardinality, where linear codes achieve the best known exponents in the single-user setting (and the optimal exponent above the critical rate), this performance carries over to the MAC setting. At least at low rates, where expurgation is needed, our approach strictly improves performance over previous results, where expurgation was used at most for one of the users. Even when the MAC channel is not additive, it may be transformed into such a channel. While the transformation is lossy, we show that the distributed structure gain in some “nearly additive” cases outweighs the loss, and thus we can improve upon the best known exponent for these cases as well. This approach is related to that previously proposed for the Gaussian MAC channel, and is based on “distributed structure”.

We consider the problem of minimizing playback delay in streaming over a packet erasure channel with fixed bandwidth. When packets have to be played in order, the expected delay inherently grows with time. We analyze two cases, namely no feedback and instantaneous feedback. We find that in both cases the delay grows logarithmically with the time elapsed since the start of transmission, and we evaluate the growth constant, i.e. the pre-log term, as a function of the transmission bandwidth (relative to the source bandwidth). The growth constant with feedback is strictly better that the one without, but they have the same asymptotic value in the limit of infinite bandwidth.

This paper introduces the problem of joint source-channel coding in the setup where channel errors are adversarial and the distortion is worst case. Unlike the situation in the case of stochastic source-channel model, the separation principle does not hold in adversarial setup. This surprising observation demonstrates that designing good distortion-correcting codes cannot be done by serially concatenating good covering codes with good error-correcting codes. The problem of the joint code design is addressed and some initial results are offered.

We consider a discrete memoryless joint source-channel setting. In this setting, if a source sequence is reconstructed with distortion below some threshold, we declare a success event. We prove that for any joint source-channel scheme, if this threshold lower (better) than the optimum average distortion, then the success probability approaches zero as the block length increases. Furthermore, we show that the probability has an exponential behavior, and evaluate the optimal exponent. Surprisingly, the best exponential behavior is attainable by a separation-based scheme.

This work considers practical implementation of the decode-and-forward relaying protocol for the full-duplex Gaussian relay channel. Unlike previous works which developed coding techniques tailored to this protocol, it is shown that standard codes which are good for the Gaussian scalar channel of fixed signal-to-noise ratio suffice to approach the theoretical performance promised by this protocol. The proposed technique employs only linear operations and successive interference cancelation in conjunction with fixed signal-to-noise ratio base codes, and the achievable rate is solely dictated by the performance of these base codes. The same approach and results carry over to the multiple-antenna case as well.

This paper continues the investigation of the combinatorial formulation of the joint source-channel coding problem. In particular, the connections are drawn to error-reducing codes, isometric embeddings and list-decodable codes. The optimal performance for the repetition construction is derived and is shown to be achievable by low complexity Markov decoders. The compound variation of the problem is proposed and some initial results are put forward.

This work considers the definition of the excess-distortion exponent, used to measure the asymptotic finite blocklength behavior of joint source-channel coding. We arrive at the conclusion that it is not a meaningful measure for the operational tradeoffs of a scheme. We propose a new definition, which makes a distinction between the processing block of the coding scheme (which implies delay and may be connected to complexity), the fidelity blocklength (reflecting the quality of the reconstruction as required by the application), and the resource blocklength (depending on hardware or shared medium considerations). As an aside, the exponent of uncoded schemes is analyzed. This results in finding the joint source-channel coding excess-distortion exponent in some cases where it was not known previously.

In this work we investigate the behavior of the minimal rate needed in order to guarantee a given probability that the distortion exceeds a prescribed threshold, at some fixed finite quantization block length. We show that the excess coding rate above the rate-distortion function is inversely proportional (to the first order) to the square root of the block length. We give an explicit expression for the proportion constant, which is given by the inverse Q-function of the allowed excess distortion probability, times the square root of a constant, termed the excess distortion dispersion. This result is the dual of a corresponding channel coding result, where the dispersion above is the dual of the channel dispersion. The work treats discrete memoryless sources, as well as the quadratic-Gaussian case.

This work considers the joint source-channel problem of transmitting a Gaussian source over a two-user multiple-input multiple-output (MIMO) broadcast channel. We show the existence of non-trivial channels, where the optimal distortion pair (which for high signal-to-noise ratios equals the point-to-point distortions of the individual users) may be achieved. A condition for existence of a joint triangularization of the MIMO channels which shapes the ratio of the diagonals to a desired form is derived. Whenever possible, all diagonal elements but one are made equal. We then employ a hybrid digital-analog scheme to the source, where the digital part is sent over the equal subchannels and the analog refinement is sent over the remaining one.

Structured codes have been utilized in deriving the best known achievable rate regions in certain network scenarios. In this paper we demonstrate that structure can be also beneficial in terms of error exponents even in cases where there is no capacity gain. We use distributed structure, i.e., different users use codes which satisfy a nesting condition. Specifically, for the scalar Gaussian multiple-access channel we obtain an improvement over the best known achievable exponent, given by Gallager, for certain rate pairs.

The physical-layer network coding (PNC) approach provides improved performance in many scenarios over “traditional” relaying techniques or network coding. This work addresses the generalization of PNC to wireless scenarios where network nodes have multiple antennas. We use a recent matrix decomposition, which allows, by linear pre- and post-processing, to simultaneously transform both channel matrices to triangular forms, where the diagonal entries, corresponding to both channels, are equal. This decomposition, in conjunction with precoding, allows to convert any two-input multiple-access channel (MAC) into parallel MACs, over which single-antenna PNC may be used. The technique is demonstrated using the two-way relay channel with multiple antennas. For this case it is shown that, in the high signal-to-noise regime, the scheme approaches the cut-set bound, thus establishing the asymptotic network capacity.

The problem of multicasting common data to several users over multiple-input multiple-output (MIMO) Gaussian channels is studied. A closed-loop setup is considered where the channel matrices are known to the transmitter and respective receivers. An incremental-redundancy (rateless) scenario is considered, where the effective rate is measured by the time that each user needs to stay online until it is able to decode the message. A practical transmission scheme for the two-user case is proposed which, by linear pre - and post-processing combined with successive decoding and interference cancellation, transforms the two MIMO channels into a set of parallel channels with no loss of mutual information, where each user needs to tune in for a duration of time proportional to its individual capacity. This scheme is used for designing a practical transmission scheme for the Gaussian MIMO half-duplex relay channel. We then turn to the related scenario of transmission to a single user over a MIMO channel with unknown but constant signal-to-noise ratio (SNR), for which we develop an optimal low-complexity hybrid ARQ coding scheme, which is optimal for two SNRs and propose a scheme for more SNRs, the loss of which vanishes when the SNRs are high. Finally, we show that even when applied to single-input single-output (“scalar”) channels, the scheme provides a practical solution for cases not covered by previous work.

We consider streaming over a blockage channel with long feedback delay, as arises in, e.g., real-time satellite communication from a comm-on-the-move (COTM) terminal. For this problem, we introduce a definition of delay that captures the real-time nature of the problem, which we show grows at least as fast as O(log(k)) for memoryless channels, where k corresponds to the number of packets in the transmission. Moreover, a tradeoff exists between this delay and a natural notion of throughput we introduce to capture the bandwidth requirements of the communication. We develop and analyze an efficient "multi-burst" transmission (MBT) protocol for achieving good delay-throughput tradeoffs within this framework, which we show to be robust and near-optimal within the class of retransmission protocols with fixed schedules. The MBT protocol can be augmented with coding for additional performance gains. Simulations validate the new protocols, including when peak bandwidth and delay constraints are imposed.

Analog (uncoded) transmission provides a simple and robust scheme for communicating a Gaussian source over a Gaussian channel under the mean-squared-error (MSE) distortion measure. Unfortunately, its performance is usually inferior to the all-digital, separation-based source-channel coding solution, which requires exact knowledge of the channel at the encoder. The loss comes from the fact that except for very special cases, e.g., white source and channel of matching bandwidth (BW), it is impossible to achieve perfect matching of source to channel and channel to source by linear means. We show that by combining prediction and modulo-lattice operations, it is possible to match any colored Gaussian source to any colored Gaussian noise channel (of possibly different BW), hence achieve Shannon's optimum attainable performance R(D)=C. Furthermore, when the source and channel BWs are equal (but otherwise their spectra are arbitrary), this scheme is asymptotically robust in the sense that for high signal-to-noise ratio (SNR) a single encoder (independent of the noise variance) achieves the optimum performance. The derivation is based upon a recent modulo-lattice modulation scheme for transmitting a Wyner-Ziv source over a dirty-paper channel.

We propose a linear predictive quantization system for causally transmitting parallel sources with temporal memory (colored frames) over an erasure channel. By optimizing within this structure, we derive an achievability result in the high-rate limit and compare it to an upper bound on performance. The proposed system subsumes the well-known PCM and DPCM systems as special cases. While typically DPCM performs well without erasures and PCM suffers less with many erasures, we show that the proposed solution improves performance over both under all severities of erasures, with unbounded improvement in some cases.

An achievable excess distortion exponent for compression of a white Gaussian source by dithered lattice quantization is derived. We show that for a required distortion level close enough to the rate-distortion function, and in the high-rate limit, the exponent equals the optimal quadratic-Gaussian excess distortion exponent. Using this approach, no further loss is incurred by the presence of any source interference known at the decoder (“Wyner-Ziv side-information”). The derivation of this achievable exponent involves finding the exponent of the probability that a combination of a spherically-bounded vector and a Gaussian vector leaves the Voronoi cell of a good lattice.

The combination of source coding with decoder side information (the Wyner-Ziv problem) and channel coding with encoder side information (the Gel'fand-Pinsker problem) can be optimally solved using the separation principle. In this work, we show an alternative scheme for the quadratic-Gaussian case, which merges source and channel coding. This scheme achieves the optimal performance by applying a modulo-lattice modulation to the analog source. Thus, it saves the complexity of quantization and channel decoding, and remains with the task of ldquoshapingrdquo only. Furthermore, for high signal-to-noise ratio (SNR), the scheme approaches the optimal performance using an SNR-independent encoder, thus it proves for this special case the feasibility of universal joint source-channel coding.

It was recently shown that the symmetric multiple-description (MD) quadratic rate-distortion function for memoryless Gaussian sources and two descriptions can be achieved by dithered Delta-Sigma quantization combined with memoryless entropy coding. In this paper,we generalize this result to stationary (colored) Gaussian sources by combining noise shaping and source prediction. We first propose a new representation for the test channel that realizes the MD rate-distortion function of a Gaussian source, both in the white and in the colored source case. We then show that this test channel canbe materialized by embedding two source prediction loops, one for each description, within a common noise shaping loop. While the noise shaping loop controls the tradeoff between the side and the central distortions, the role of prediction (like in differential pulse code modulation) is to extract the source innovations from the reconstruction at each of the side decoders, and thus reduce the coding rate. Finally, we show that this scheme achieves the MD rate-distortion function at all resolutions and all side-to-central distortion ratios, in the limit of high dimensional quantization.

The Gaussian parallel relay network problem consists of transmitting a message from a single source node to a single destination node, through a layer of parallel relay nodes. The source is connected to the relays by a Gaussian broadcast channel, while the relays are connected to the destination by a Gaussian multiple access channel. When the channels are all white with the same bandwidth, and the relays cannot decode the message, the best known strategy is "amplify and forward", which achieves the coherence gain of multiple relays. We propose a strategy which achieves this gain even when the noises are colored or the channels have different bandwidths. To that end we use analog modulo-lattice modulation of the codewords in the BC, and then forward the estimated codeword by each of the relays to the MAC. This modulation allows the relays to re-match the signal to the optimal spectrum of the MAC, thus demonstrating how a channel problem can gain from a joint source/channel approach. We show that this strategy is asymptotically optimal in some limiting cases, and that it outperforms the known alternatives in most other cases, where the optimum is unknown. We also demonstrate how to improve the achievable rate in the original white problem, for some signal to noise ratio values.

The ldquowater-fillingrdquo solution for the quadratic rate-distortion function of a stationary Gaussian source is given in terms of its power spectrum. This formula naturally lends itself to a frequency domain ldquotest-channelrdquo realization. We provide an alternative time-domain realization for the rate-distortion function, based on linear prediction. The predictive test channel has some interesting implications, including the optimality at all distortion levels of pre/post filtered vector-quantized differential pulse-code modulation (DPCM), and a duality relationship with decision-feedback equalization (DFE) for intersymbol interference (ISI) channels.

We consider transmission of a colored Gaussian source through a power constrained colored Gaussian broadcast channel subject to a mean-squared error distortion measure. It is well known that separation of source and channel coding cannot achieve the point R(D)=C simultaneously for more than one receiver. We characterize the distortion region achieved by the recently proposed joint source/channel "analog matching" coding scheme. In the special case of equal bandwidth (but arbitrary source and channel spectra) and in the limit of high signal to noise ratio (SNR), we prove that full robustness is asymptotically possible, i.e., the encoder becomes SNR-independent and each decoder approaches the ideal performance R(D)=C. This result extends the well known optimality of analog transmission in the white source / white channel case. Our results are based upon an encoder which employs modulo-lattice arithmetics, i.e. the transmitted signal is the residue of an analog signal with respect to a lattice.

Uncoded transmission provides a simple, delay-less and robust scheme for communicating a Gaussian source over a filter channel under the mean squared error (MSE) distortion measure. Unfortunately, its performance is usually inferior to the all-digital solution, consisting of a rate-distortion code for the source followed by a capacity achieving code for the channel. The performance loss of uncoded transmission comes from the fact that except for very special cases, it is impossible to achieve simultaneous matching of source to channel and channel to source by linear means. We show that by combining prediction and modulo-lattice arithmetic, we can match any stationary Gaussian source to any inter-symbol interference, colored-noise Gaussian channel, hence we achieve Shannon's optimum attainable performance R(D) = C. This scheme is based upon a novel analog modulo-lattice solution to the joint source-channel coding problem for a Gaussian Wyner-Ziv source and a dirty-paper channel

The "water-filling" solution for the quadratic rate-distortion function of a stationary Gaussian source is given in terms of its power spectrum. This formula naturally lends itself to a frequency domain "test-channel" realization. We provide an alternative time-domain realization for the rate-distortion function, based on linear prediction. This solution has some interesting implications, including the optimality at all distortion levels of pre/post filtered vector-quantized differential pulse code modulation (DPCM), and a duality relationship with decision-feedback equalization (DFE) for inter-symbol interference (ISI) channels

We present a new adaptive mechanism for empirical "on-line" design of a vector quantizer codebook. The proposed scheme is based on the principle of "natural type selection" (NTS) (Zamir and Rose, 2001). The NTS principle implies that backward adaptation, i.e., adaptation directed by the past reconstruction rather than by the uncoded source sequence converges to an optimum rate-distortion codebook. We incorporate the NTS iteration step into a parametric encoder. We demonstrate that the codebook converges to an optimum rate-distortion solution within the associated parametric class. This new scheme does not suffer from the severe complexity at high dimensions of nonparametric solutions like the generalized Lloyd algorithm (GLA). Moreover, unlike existing parametric adaptive schemes (e.g., code-excited linear prediction (CELP)), this scheme is optimal even for low coding rates.