We derive upper and lower bounds on the overall compression ratio of the 1978 Lempel-Ziv (LZ78) algorithm, applied independently tok-blocks of a finite individual sequence. Both bounds are given in terms of normalized empirical entropies of the given sequence. For the bounds to be tight and meaningful, the order of the empirical entropy should be small relative tokin the upper bound, but large relative tokin the lower bound. Several non-trivial conclusions arise from these bounds. One of them is a certain form of a chain rule of the Lempel-Ziv (LZ) complexity, which decomposes the joint LZ complexity of two sequences, say,xandy, into the sum of the LZ complexity ofxand the conditional LZ complexity ofygivenx(up to small terms). The price of this decomposition, however, is in changing the length of the block. Additional conclusions are discussed as well.

We present a family of relatively simple and unified lower bounds on the capacity of the Gaussian channel under a set of pointwise additive input constraints. Specifically, the admissible channel input vectorsx= (x1, . . . ,xn) must satisfykadditive cost constraints of the form ∑ni=1 ∅j(xi) ≤nΓj,j= 1, 2, . . . ,k, which are enforced pointwise for everyx, rather than merely in expectation. More generally, we also consider cost functions that depend on a sliding window of fixed lengthm, namely,∑ni=mϕj(xi,xi−1, . . . ,xi−m+1) ≤nΓj,j= 1, 2, . . . ,k, a formulation that naturally accommodates correlation constraints as well as a broad range of other constraints of practical relevance. We propose two classes of lower bounds, derived by two methodologies that both rely on the exact evaluation of the volume exponent associated with the set of input vectors satisfying the given constraints. This evaluation exploits extensions of the method of types to continuous alphabets, the saddle-point method of integration, and basic tools from large deviations theory. The first class of bounds is obtained via the entropy power inequality (EPI), and therefore applies exclusively to continuous-valued inputs. The second class, by contrast, is more general, and it applies to discrete input alphabets as well. It is based on a direct manipulation of mutual information, and it yields stronger and tighter bounds, though at the cost of greater technical complexity. Numerical examples illustrating both types of bounds are provided, and several extensions and refinements are also discussed.

In continuation of an earlier study, we explore a Neymann-Pearson hypothesis testing scenario where, under the null hypothesis (${\mathcal { H}}_{0}$), the received signal is a white noise process$N_{t}$, which is not Gaussian in general, and under the alternative hypothesis (${\mathcal { H}}_{1}$), the received signal comprises a deterministic transmitted signal$s_{t}$corrupted by additive white noise, the sum of$N_{t}$and another noise process originating from the transmitter, denoted as$Z_{t}$, which is not necessarily Gaussian either. Our approach focuses on detectors that are based on the correlation and energy of the received signal, which are motivated by implementation simplicity. We optimize the detector parameters to achieve the best trade-off between missed-detection and false-alarm error exponents. First, we optimize the detectors for a given signal, resulting in a non-linear relation between the signal and correlator weights to be optimized. Subsequently, we optimize the transmitted signal and the detector parameters jointly, revealing that the optimal signal is a balanced ternary signal and the correlator has at most three different coefficients, thus facilitating a computationally feasible solution.

We establish a coding theorem and a matching converse theorem for separate encodings and joint decoding of individual sequences using finite-state machines. The achievable rate region is characterized in terms of the Lempel-Ziv (LZ) complexities, the conditional LZ complexities and the joint LZ complexity of the two source sequences. An important feature that is needed to this end, which may be interesting on its own right, is a certain asymptotic form of a chain rule for LZ complexities, which we establish in this work. The main emphasis in the achievability scheme is on the universal decoder and its properties. We then show that the achievable rate region is universally attainable by a modified version of Draper’s universal incremental Slepian-Wolf (SW) coding scheme, provided that there exists a low-rate reliable feedback link.

The problem of transmitting a parameter value over an additive white Gaussian noise (AWGN) channel is considered, where, in addition to the transmitter and the receiver, there is a helper that observes the noise non-causally and provides a description of limited rate$R_{\mathrm{h}}$to the transmitter and/or the receiver. We derive upper and lower bounds on the optimal achievable$\alpha-\mathbf{th}$moment of the estimation error and show that they coincide for small values of$\alpha$and for high values of$R_{\mathrm{h}}$. The upper bound relies on a recently proposed channel-coding scheme that effectively conveys$R_{\mathrm{h}}$bits essentially error-free and the rest of the rate—over the same AWGN channel without help, with the error-free bits being allocated to the most significant bits of the quantized parameter.

We consider the problem of parameter estimation, based on noisy chaotic signals, from the viewpoint of twisted modulation for waveform communication. In particular, we study communication systems where the parameter to be estimated is conveyed as the initial condition of a chaotic dynamical system of a certain class and we examine its estimation performance in terms of the expectation of a given convex function of the estimation error at high SNR, under the demand that the probability of anomaly is kept small. We derive a lower bound on the weak-noise estimation error for this class of chaotic modulators, and argue that it can be outperformed by using the itinerary signal associated with the chaotic system instead of the main chaotic output signal.

The problem of transmitting a parameter value over an additive white Gaussian noise (AWGN) channel is considered, where, in addition to the transmitter and the receiver, there is a helper that observes the noise non-causally and provides a description of limited rate$R_{\mathrm {h}}$to the transmitter and/or the receiver. We derive upper and lower bounds on the optimal achievable$\alpha $-th moment of the estimation error and show that they coincide for small values of$\alpha $and for high values of$R_{\mathrm {h}}$. The upper bound relies on a recently proposed channel-coding scheme that effectively conveys$R_{\mathrm {h}}$bits essentially error-free and the rest of the rate—over the same AWGN channel without help, with the error-free bits being allocated to the most significant bits of the quantized parameter. We then concentrate on the setting with a total transmit energy constraint, for which we derive achievability results for both channel coding and parameter modulation for several scenarios: when the helper assists only the transmitter or only the receiver and knows the noise, and when the helper assists the transmitter and/or the receiver and knows both the noise and the message. In particular, for the message-informed helper that assists both the receiver and the transmitter, it is shown that the error probability in the channel-coding task decays doubly exponentially. Finally, we translate these results to those for continuous-time power-limited AWGN channels with unconstrained bandwidth. As a byproduct, we show that the capacity with a message-informed helper that is available only at the transmitter can exceed the sum of the capacity without help and the help rate$R_{\mathrm {h}}$.

The wiretap channel with additive (possibly non-Gaussian) noise and rate-limited help, available at the legitimate receiver (Rx) or/and transmitter (Tx), is studied under various channel configurations (degraded, reversely degraded and non-degraded) and power/amplitude constraints. For all channel configurations, the rate-limited Rx help results in a (weak or strong) secrecy capacity boost equal to the help rate. This holds irrespective of whether the help is secure or not, or whether the helper is aware of the message being transmitted or not; the secrecy of help or helper’s knowledge of the message does not provide any extra capacity boost. The secrecy capacity is positive for the reversely-degraded channel (where the no-help secrecy capacity is zero) and no wiretap coding is needed to achieve it under weak secrecy. The same capacity boost also holds if non-secure help is available to the transmitter (encoder), in addition to or instead of the same Rx help, so that, in the case of the joint Tx/Rx help, one help link can be omitted without affecting the capacity. If Rx/Tx help links are independent of each other, the capacity boost is the sum of help rates and no link can be omitted without loss in the capacity. Non-singular correlation of the receiver and eavesdropper noises does not affect the secrecy capacity and non-causal help does not bring in any capacity increase over the causal one. The choice of the secrecy criterion (weak/strong) affects the complexity of implementation but not the secrecy capacity. Stronger noise at the legitimate receiver can sometimes result in higher secrecy capacity.

We consider the problem of parameter estimation, based on noisy chaotic signals, from the viewpoint of twisted modulation for waveform communication. In particular, we study communication systems where the parameter to be estimated is conveyed as the initial condition of a chaotic dynamical system of a certain class and we examine its estimation performance in terms of the expectation of a given convex function of the estimation error at high SNR, under the demand that the probability of anomaly is kept small. We derive a lower bound on the weak-noise estimation error for this class of chaotic modulators, and argue that it can be outperformed by using the itinerary signal associated with the chaotic system instead of the main chaotic output signal.

The Gaussian wiretap channel (WTC) with rate-limited help, available at the transmitter/encoder (Tx), in addition to or instead of the same help at the legitimate receiver, is studied under various channel configurations. For the degraded or reversely-degraded WTC, rate-limited non-secure Tx help results in a secrecy capacity boost equal to the help rate irrespective of whether the help is causal or not. For the non-degraded WTC, the secrecy capacity boost is lower bounded by the help rate. A capacity-achieving signaling is two-phase time sharing, where wiretap coding without help is used in Phase 1 and help without wiretap coding is used in Phase 2. The secrecy capacity with Tx help is positive for the reversely-degraded channel (where the no-help secrecy capacity is zero) and no Phase 1 is needed to achieve it. Unlike the no-help case, more noise at the legitimate receiver can sometimes result in higher secrecy capacity with Tx help. In the case of the joint Tx/Rx non-secure help, one help link can be omitted without affecting the capacity.

We derive various error exponents for communication channels with random states, which are available non-causally at the encoder only. For both the finite-alphabet Gel’fand-Pinsker channel and its Gaussian counterpart, the dirty-paper channel, we derive random coding exponents, error exponents of the typical random codes (TRCs), and error exponents of expurgated codes. For the two channel models, we analyze some sub-optimal bin-index decoders, which turn out to be asymptotically optimal, at least for the random coding error exponent. For the dirty-paper channel, we show explicitly via a numerical example, that at rates below capacity, the optimal values of the dirty-paper design parameter α in the random coding sense and in the TRC exponent sense are different from one another, and they are both different from the optimal α that is required for attaining the channel capacity. For the Gel’fand-Pinsker channel, we allow for a variable-rate random binning code construction, and prove that the previously proposed maximum penalized mutual information decoder is asymptotically optimal within a given class of decoders, at least for the random coding error exponent.

We prove the existence of codebooks for$d$-semifaithful lossy compression that are simultaneously universal with respect to both the class of finite-alphabet memoryless sources and the class of all bounded additive rational distortion measures. By applying independent random selection of the codewords according to a mixture of all memoryless sources, we achieve redundancy rates that are within$O(\log n/n)$close to the empirical rate-distortion function of every given source vector with respect to every bounded, rational distortion measure.

We consider an ensemble of constant composition codes that are subsets of linear codes: while the encoder uses only the constant-composition subcode, the decoder operates as if the full linear code was used, with the motivation of simultaneously benefiting both from the probabilistic shaping of the channel input (to achieve higher rates) and from the linear structure of the code (to allow for lower complexity practical decoding). We prove that the codebook mismatch can be fully compensated by using a mismatched additive decoding metric that achieves the random coding error exponent of (non-linear) constant composition codes. As the coding rate tends to the mutual information, the optimal mismatched metric approaches the maximum a posteriori probability (MAP) metric, showing that codebook mismatch with MAP metric is capacity-achieving for the optimal input assignment.

We derive various error exponents for communication channels with random states, which are available non-causally at the encoder only. For both the finite-alphabet Gel’fand–Pinsker channel and its Gaussian counterpart, the dirty-paper channel, we derive random coding exponents, error exponents of the typical random codes (TRCs), and error exponents of expurgated codes. For the two channel models, we analyze some sub-optimal bin-index decoders, which turn out to be asymptotically optimal, at least for the random coding error exponent. For the dirty-paper channel, we show explicitly via a numerical example, that both the error exponent of the TRC and the expurgated exponent strictly improve upon the random coding exponent, at relatively low coding rates, which is a known fact for discrete memoryless channels without random states. We also show that at rates below capacity, the optimal values of the dirty-paper design parameter$\alpha $in the random coding sense and in the TRC exponent sense are different from one another, and they are both different from the optimal$\alpha $that is required for attaining the channel capacity. For the Gel’fand–Pinsker channel, we allow for a variable-rate random binning code construction, and prove that the previously proposed maximum penalized mutual information decoder is asymptotically optimal within a given class of decoders, at least for the random coding error exponent.

Consider the problem of guessing a sequence subject to a distortion constraint. Specifically, assume the following game between Alice and Bob: Alice has a sequence x of length n. Bob wishes to guess x, yet he is satisfied with finding any sequence $\hat x$ which is within a given distortion D from x. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses and analyzing its properties has applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering biometrically-secured systems, where the "password" which protects the data is not a single, fixed vector but rather a ball of feature vectors centered at some x, and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in four different setups: memoryless sources, guessing through a noisy channel, sources with memory, and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is five–fold universal, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level.

The Gaussian wiretap channel with rate-limited help available at the legitimate receiver (decoder) is studied under various channel configurations (degraded, reversely degraded and non-degraded). In all considered cases but one, the rate-limited help results in a secrecy capacity boost equal to the help rate. This holds irrespective of whether the help is secure or not, so that secure help does not provide any advantage over non-secure one. The secrecy capacity is positive for the reversely-degraded channel (where the no-help secrecy capacity is zero) and no wiretap coding is needed to achieve it. More noise at the legitimate receiver can sometimes result in higher secrecy capacity. The same secrecy capacity boost also holds if non-secure help is available to the transmitter (encoder), in addition to or instead of the receiver help.

We propose both an improvement and extensions of a reverse Jensen inequality due to Wunder et al. (2021). The new proposed inequalities are fairly tight and reasonably easy to use in a wide variety of situations, as demonstrated in several application examples that are relevant to information theory. Moreover, the main ideas behind the derivations turn out to be applicable to generate bounds to expectations of multivariate convex/concave functions, as well as functions that are not necessarily convex or concave.

We consider the problem of encoding an individual source sequence for the degraded wiretap channel using encoders and decoders that can be implemented as finite–state machines. Our first main result is a converse bound for reliable and secure transmission in terms of the given source sequence, the bandwidth expansion factor, the secrecy capacity, and the numbers of states of the encoder and the decoder. The bound is asymptotically achievable by Lempel–Ziv compression followed by good channel coding for the wiretap channel. Given that the lower bound is saturated, we also derive a lower bound on the minimum necessary rate of purely random bits needed for local randomness at the encoder in order to meet the security constraint. This bound too is achieved by the same achievability scheme. Finally, we extend the main results to the case where the legitimate decoder has access to a side information sequence, which is another individual sequence, and a noisy version of the side information sequence leaks to the wiretapper.

We provide two results concerning the optimality of the stochastic-mutual information (SMI) decoder, which chooses the estimated message according to a posterior probability mass function, which is proportional to the exponentiated empirical mutual information induced by the channel output sequence and the different codewords. First, we prove that the error exponents of the typical random codes under the optimal maximum likelihood (ML) decoder and the SMI decoder are equal. As a corollary to this result, we also show that the error exponents of the expurgated codes under the ML and the SMI decoders are equal. These results strengthen the well-known result due to Csiszár and Körner, according to which, the ML and the maximum-mutual information (MMI) decoders achieve equal random-coding error exponents, since the error exponents of the typical random code and the expurgated code are strictly higher than the random-coding error exponents, at least at low coding rates. The universal optimality of the SMI decoder, in the random-coding error exponent sense, is easily proven by commuting the expectation over the channel noise and the expectation over the ensemble. This commutation can no longer be carried out, when it comes to typical and expurgated exponents. Therefore, the proof of the universal optimality of the SMI decoder must be completely different and it turns out to be highly non-trivial.

We consider the DNA storage channel, in which M Deoxyribonucleic acid (DNA) molecules comprising each codeword, are stored without order, then sampled N times with replacement, and then sequenced over a discrete memoryless channel. For a constant coverage depth, M/N, and molecule length scaling Θ(log M), lower (achievability) and upper (converse) bounds on the capacity of the channel, as well as a lower (achievability) bound on the reliability function of the channel are provided. Both the lower and upper bounds on the capacity generalize a bound which was previously known to hold only for the binary symmetric sequencing channel, and only under certain restrictions on the molecule length scaling and the crossover probability parameters. When specified to binary symmetric sequencing channel, these restrictions are completely removed for the lower bound and are significantly relaxed for the upper bound. The lower bound on the reliability function is achieved under a universal decoder, and reveals that the dominant error event is that of outage – the event in which the capacity of the channel induced by the DNA molecule sampling operation does not support the target rate.

In this paper, we consider the problem of guessing a sequence subject to a distortion constraint. Specifically, we assume the following game between Alice and Bob: Alice has a sequence${x}$of length$n$. Bob wishes to guess${x}$, yet he is satisfied with finding any sequence$\hat {x}$which is within a given distortion$D$from$x$. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses (the guesswork), and analyzing its properties (e.g., its$\rho $–th moment) has several applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering contemporary biometrically–secured systems, where the “password” which protects the data is not a single, fixed vector but rather a ball of feature vectors centered at some${x}$, and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in four different setups: memoryless sources, guessing through a noisy channel, sources with memory and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is five–fold universal, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level.

A source sequence is to be guessed with some fidelity based on a rate-limited description of an observed sequence with which it is correlated. The tension between the description rate and the exponential growth rate of the power mean of the required number of guesses is quantified. This can be viewed as the guessing version of the classical indirect-rate-distortion problem of Dobrushin-Tsybakov’62 and Witsenhausen’80. Judicious choices of the correlated sequence, the description rate, and the fidelity criterion recover a number of recent and classical results on guessing. In the context of security, the paper provides conservative estimates on a password’s remaining security after a number of bits from a correlated database have been leaked.

We study the following semi–deterministic setting of the joint source–channel coding problem: a deterministic source sequence (a.k.a. individual sequence) is transmitted via a memoryless channel, using delay-limited encoder and decoder, which are both implementable by periodically–varying finite-state machines, and the decoder is granted with access to side information, which is a noisy version of the source sequence. We first derive a lower bound on the achievable expected distortion in terms of the empirical statistics of the source sequence, the number of states of the encoder, the number of states of the decoder, their period, and the overall delay. The bound is shown to be asymptotically achievable by universal block codes in the limit of long blocks. We also derive a lower bound to the best achievable excess–distortion probability and discuss situations where it is achievable. Here, of course, source coding and channel coding cannot be completely separated without loss of optimality. Finally, we outline a few extensions of the model considered, such as: (i) incorporating a common reconstruction constraint, (ii) availability of side information at both ends, and (iii) extension to the Shannon channel with causal state information at the encoder. This work both extends and improves on earlier work of the same flavor (Ziv 1980, Merhav 2014), which focused only on the expected distortion, without side information at either end, and without the above mentioned additional ingredients.

We consider the classical Neymann–Pearson hypothesis testing problem of signal detection, where under the null hypothesis (${\mathcal{ H}}_{0}$), the received signal is white Gaussian noise, and under the alternative hypothesis (${\mathcal{ H}}_{1}$), the received signal includes also an additional non–Gaussian random signal, which in turn can be viewed as a deterministic waveform plus zero–mean, non-Gaussian noise. However, instead of the classical likelihood ratio test detector, which might be difficult to implement, in general, we impose a (mismatched) correlation detector, which is relatively easy to implement, and we characterize the optimal correlator weights in the sense of the best trade-off between the false-alarm error exponent and the missed-detection error exponent. Those optimal correlator weights depend (non-linearly, in general) on the underlying deterministic waveform under${\mathcal{ H}}_{1}$. We then assume that the deterministic waveform may also be free to be optimized (subject to a power constraint), jointly with the correlator, and show that both the optimal waveform and the optimal correlator weights may take on values in a small finite set of typically no more than two to four levels, depending on the distribution of the non-Gaussian noise component. Finally, we outline an extension of the scope to a wider class of detectors that are based on linear combinations of the correlation and the energy of the received signal.

We provide two results concerning the optimality of the stochastic-mutual information (SMI) decoder, which chooses the estimated message according to a posterior probability mass function, which is proportional to the exponentiated empirical mutual information induced by the channel output sequence and the different codewords. First, we prove that the error exponents of the typical random codes under the optimal maximum likelihood (ML) decoder and the SMI decoder are equal. As a corollary to this result, we also show that the error exponents of the expurgated codes under the ML and the SMI decoders are equal. These results strengthen the well-known result due to Csiszár and Körner, according to which, the ML and the maximum-mutual information (MMI) decoders achieve equal random-coding error exponents, since the error exponents of the typical random code and the expurgated code are strictly higher than the random-coding error exponents, at least at low coding rates. The universal optimality of the SMI decoder, in the random-coding error exponent sense, is easily proven by commuting the expectation over the channel noise and the expectation over the ensemble. This commutation can no longer be carried out, when it comes to typical and expurgated exponents. Therefore, the proof of the universal optimality of the SMI decoder must be completely different and it turns out to be highly non-trivial.

The DNA storage channel is considered, in which the$M$Deoxyribonucleic acid (DNA) molecules comprising each codeword are stored without order, sampled$N$times with replacement, and then sequenced over a discrete memoryless channel. For a constant coverage depth$M/N$and molecule length scaling$\Theta (\log M)$, lower (achievability) and upper (converse) bounds on the capacity of the channel, as well as a lower (achievability) bound on the reliability function of the channel are provided. Both the lower and upper bounds on the capacity generalize a bound which was previously known to hold only for the binary symmetric sequencing channel, and only under certain restrictions on the molecule length scaling and the crossover probability parameters. When specified to binary symmetric sequencing channel, these restrictions are completely removed for the lower bound and are significantly relaxed for the upper bound in the high-noise regime. The lower bound on the reliability function is achieved under a universal decoder, and reveals that the dominant error event is that ofoutage– the event in which the capacity of the channel induced by the DNA molecule sampling operation does not support the target rate.

Typical random codes (TRC) in a communication scenario of source coding with side information at the decoder is the main subject of this work. We study the semi-deterministic code ensemble, which is a certain variant of the ordinary random binning code ensemble. In this code ensemble, the relatively small type classes of the source are deterministically partitioned into the available bins in a one-to-one manner. As a consequence, the error probability decreases dramatically. The random binning error exponent and the error exponent of the TRC are derived and proved to be equal to one another in a few important special cases. We show that the performance under optimal decoding can be attained also by certain universal decoders, e.g., the stochastic likelihood decoder with an empirical entropy metric. Moreover, we discuss the trade-offs between the error exponent and the excess-rate exponent for the typical random semi-deterministic code and characterize its optimal rate function. We show that for any pair of correlated information sources, both error and excess-rate probabilities are exponentially vanishing.

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

Traditionally, ensembles of Slepian-Wolf (S-W) codes are defined such that every bin of each$n$-vector of each source is randomly drawn under the uniform distribution across the sets$\{0,1,\ldots, 2^{nR_{X}}-1\}$and$\{0,1,\ldots, 2^{nR_{Y}}-1\}$, where$R_{X}$and$R_{Y}$are the coding rates of the two sources,$X$and$Y$, respectively. In a few recent works, where only one source is compressed and the other one serves as side information at the decoder, the scope is extended to variable–rate S-W (VRSW) codes, where the rate may depend on the type class of the source string, but still, the random–binning distribution is assumed uniform within the type–dependent, bin index set. In this expository work, we investigate the role of the uniformity of the random binning distribution from the perspective of the trade-off between the error exponent and the source coding exponent. To this end, we study a much wider class of random–binning distributions, which includes VRSW codes as a special case, but goes considerably beyond. We first show that, except for some pathological cases, the sub-ensemble of VRSW codes is as good as the large ensemble in terms the trade–off between the error exponent and the source coding exponent. Nonetheless, the wider class of ensembles is motivated in two ways. The first is that it outperforms VRSW codes in the above–mentioned pathological cases, and the second is that it allows robustness: in the event of unavailability of the compressed bit–stream from one of the sources, it still allows reconstruction of the other source within some controllable distortion.

Motivated by modern applications of light detection and ranging (LIDAR), we study the model of an optical receiver based on an avalanche photo-diode (APD), followed by electronic circuitry for detection of reflected optical signals and estimation of their delay. This model is complicated as it consists of three types of noise: thermal noise, shot noise, and multiplicative noise (excess noise) that stems from the random gain of the APD. Consequently, the derivation of the optimal likelihood ratio test (LRT) for signal detection is non-trivial. We consider instead simple detectors, that are based on correlating the received signal with a given deterministic waveform, and our purpose is to characterize the waveform that best trades off between the false-alarm (FA) error exponent and the missed-detection (MD) error exponent. We also study the problem of estimating the delay by maximizing the correlation between the received signal and a time-shifted waveform, as a function of this time shift. We characterize the optimal correlator waveform that minimizes the mean square error (MSE) for SNR. The optimal correlator waveforms for detection and for estimation turn out to be different, but their limiting behavior is the same: when the thermal noise is dominant, the optimal correlator waveform becomes proportional to the clean signal, but when the thermal noise is negligible compared to the other noises, then it becomes a logarithmic function of the clean signal, as expected.

The bee identification problem is a problem of properly recognizing a massive amount of data (a numerous amount of bees in a beehive, for example) which have been mixed and corrupted by noise. We derive various error exponents in the bee identification problem under two different decoding rules. Under naïve decoding, which decodes each bee independently of the others, we analyze a general discrete memoryless channel and a relatively wide family of stochastic decoders. Upper and lower bounds to the random coding error exponent are derived and proved to be equal at relatively high coding rates. Then, we propose a lower bound on the error exponent of the typical random code, which improves upon the random coding exponent at low coding rates. We also derive a third bound, which is related to expurgated codes, which turns out to be strictly higher than the other bounds, also at relatively low rates. We show that the universal maximum mutual information decoder is optimal with respect to the typical random code and the expurgated code. Moving further, we derive error exponents under optimal decoding, the relatively wide family of symmetric channels, and the maximum likelihood decoder. We first propose a random coding lower bound, and then, an improved bound which stems from an expurgation process. We show numerically that our second bound strictly improves upon the random coding bound at an intermediate range of coding rates, where a bound derived in a previous work no longer holds.

We address the problem of modulating a parameter onto a power-limited signal, transmitted over a discrete-time Gaussian channel and estimating this parameter at the receiver. Continuing an earlier work, where the optimal trade-off between the weak-noise estimation performance and the outage probability (threshold-effect breakdown) was studied for a scalar parameter, here we extend the derivation of the weak-noise estimation performance to the case of a multi-dimensional vector parameter. This turns out to be a non-trivial extension, that provides a few insights, and has some interesting implications. Several modifications and extensions of the basic setup are also studied and discussed.

We consider the problem of guessing a random, finite-alphabet, secret n-vector, where the guesses are transmitted via a noisy channel. We provide a single-letter formula for the best achievable exponential growth rate of the ρ-th moment of the number of guesses, as a function of n. This formula exhibits a fairly clear insight concerning the penalty due to the noise. We describe two different randomized schemes that achieve the optimal guessing exponent. One of them is fully universal in the sense of being independent of source (that governs the vector to be guessed), the channel (that corrupts the guesses), and the moment power ρ. Interestingly, it turns out that, in general, the optimal guessing exponent function exhibits a phase transition when it is examined either as a function of the channel parameters, or as a function of ρ: as long as the channel is not too distant (in a certain sense to be defined precisely) from the identity channel (i.e., the clean channel), or equivalently, as long ρ is larger than a certain critical value, ρc, there is no penalty at all in the guessing exponent, compared to the case of noiseless guessing.

We explore known integral representations of the logarithmic and power functions, and demonstrate their usefulness for information-theoretic analyses. We obtain compact, easily-computable exact formulas for several source and channel coding problems that involve expectations and higher moments of the logarithm of a positive random variable and the moment of order ρ>0 of a non-negative random variable (or the sum of i.i.d. positive random variables). These integral representations are used in a variety of applications, including the calculation of the degradation in mutual information between the channel input and output as a result of jamming, universal lossless data compression, Shannon and Rényi entropy evaluations, and the ergodic capacity evaluation of the single-input, multiple-output (SIMO) Gaussian channel with random parameters (known to both transmitter and receiver). The integral representation of the logarithmic function and its variants are anticipated to serve as a rigorous alternative to the popular (but non-rigorous) replica method (at least in some situations).

We consider the problem of (almost) lossless source coding of two correlated memoryless sources using separate encoders and a joint decoder, that is, Slepian-Wolf (S-W) coding. In our setting, the encoding and decoding are asynchronous, i.e., there is a certain relative delay between the two sources. Neither the source parameters nor the relative delay are known to the encoders and the decoder. Since we assume that both encoders implement standard random binning, which does not require such knowledge anyway, the focus of this work is on the decoder. Our main contribution is in proposing a universal decoder, that independent of the unknown source parameters and the relative delay, and at the same time, is asymptotically as good as the optimal maximum a posteriori probability (MAP) decoder in the sense of the random coding error exponent achieved. Consequently, the achievable rate region is also the same as if the source parameters and the delay were known to the decoder.

Motivated by earlier results on universal randomized guessing, we consider an individual-sequence approach to the guessing problem: in this setting, the goal is to guess a secret, individual (deterministic) vector xn= (x1, . .. , xn), by using a finite-state machine that sequentially generates randomized guesses from a stream of purely random bits. We define the finite-state guessing exponent as the asymptotic normalized logarithm of the minimum achievable moment of the number of randomized guesses, generated by any finite-state machine, until xn is guessed successfully. We show that the finite-state guessing exponent of any sequence is intimately related to its finite-state compressibility (due to Lempel and Ziv), and it is asymptotically achieved by the decoder of (a certain modified version of) the 1978 Lempel-Ziv data compression algorithm (a.k.a. the LZ78 algorithm), fed by purely random bits. The results are also extended to the case where the guessing machine has access to a side information sequence, yn= (y1, . .. , yn), which is also an individual sequence.

A Lagrange-dual (Gallager-style) lower bound is derived for the error exponent function of the typical random code (TRC) pertaining to the i.i.d. random coding ensemble and mismatched stochastic likelihood decoding. While the original expression, derived from the method of types (the Csiszár-style expression) involves minimization over probability distributions defined on the channel input-output alphabets, the new Lagrange-dual formula involves optimization of five parameters, independently of the alphabet sizes. For both stochastic and deterministic mismatched decoding (including maximum likelihood decoding as a special case), we provide a rather comprehensive discussion on the insight behind the various ingredients of this formula and describe how its behavior varies as the coding rate exhausts the relevant range. Among other things, it is demonstrated that this expression simultaneously generalizes both the expurgated error exponent function (at zero rate) and the classical random coding exponent function at high rates, where it also meets the sphere-packing bound.

We consider the problem of guessing a random, finite-alphabet, secret n-vector, where the guesses are transmitted via a noisy channel. We provide a single-letter formula for the best achievable exponential growth rate of the ρ-th moment of the number of guesses, as a function of n. This formula exhibits a fairly clear insight concerning the penalty due to the noise. We describe two different randomized schemes that achieve the optimal guessing exponent. One of them is fully universal in the sense of being independent of source (that governs the vector to be guessed), the channel (that corrupts the guesses), and the moment power ρ. Interestingly, it turns out that, in general, the optimal guessing exponent function exhibits a phase transition when it is examined either as a function of the channel parameters, or as a function of ρ: as long as the channel is not too distant (in a certain sense to be defined precisely) from the identity channel (i.e., the clean channel), or equivalently, as long ρ is larger than a certain critical value, ρc, there is no penalty at all in the guessing exponent, compared to the case of noiseless guessing.

This work studies the deviations of the error exponent of the constant composition code ensemble around its expectation, known as the error exponent of the typical random code (TRC). In particular, it is shown that the probability of randomly drawing a codebook whose error exponent is smaller than the TRC exponent is exponentially small; upper and lower bounds for this exponent are given, which coincide in some cases. In addition, the probability of randomly drawing a codebook whose error exponent is larger than the TRC exponent is shown to be double-exponentially small; upper and lower bounds to the double-exponential exponent are given. The results suggest that codebooks whose error exponent is larger than the error exponent of the TRC are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables.

This work contains two main contributions concerning the large deviations behavior of randomly chosen fixed composition codes over a discrete memoryless channel (DMC). The first is an exponentially tight expression for the probability of randomly drawing a codebook that performs worse than the typical random coding (TRC) error exponent, which is proved to be exponentially small. The second is lower and upper bounds on the probability of randomly selecting a codebook that outperforms the TRC error exponent, which turn out to be double-exponentially small, suggesting that relatively good codebooks are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables.

Consider the problem of guessing a random vector X by submitting queries (guesses) of the form "Is X equal to x?" until an affirmative answer is obtained. A key figure of merit is the number of queries required until the right vector is guessed, termed the guesswork. The goal is to devise a guessing strategy which minimizes a certain guesswork moment. We study a universal, decentralized scenario where the guesser does not know the distribution of X, and is not allowed to prepare a list of words to be guessed in advance, or to remember its past guesses. Such a scenario is useful, for example, if bots within a Botnet carry out a brute-force attack to guess a password or decrypt a message, yet cannot coordinate the guesses or even know how many bots actually participate in the attack. We devise universal decentralized guessing strategies, first, for memoryless sources, and then generalize them to finite-state sources. For both, we derive the guessing exponent and prove its asymptotic optimality by deriving a matching converse. The strategies are based on randomized guessing using a universal distribution. We also extend the results to guessing with side information (SI). Finally, we design simple algorithms for sampling from the universal distributions.

Biometric authentication systems, based on secret key generation, work as follows. In the enrollment stage, an individual provides a biometric signal that is mapped into a secret key and a helper message, the former being prepared to become available to the system at a later time, and the latter is stored in a public database. When an authorized user signs in with some identity, he/she has to provide a biometric signal again, and then the system retrieves the helper message of the claimed subscriber and estimates the secret key, which is compared to the secret key of that user. In case of a match, the authentication request is approved, otherwise, it is rejected. There is an inherent tension between two conflicting properties of the helper message encoder: on the one hand, the encoding should be informative enough concerning the identity of the real subscriber, in order to approve him/her in the authentication stage, but on the other hand, it should not be too informative, as otherwise, unauthorized imposters could easily fool the system. A good encoder should then trade off two kinds of errors: the false reject (FR) error and the false accept (FA) error. We investigate trade-offs between the random coding FR error exponent and the best achievable FA error exponent. We compare two types of ensembles of codes: fixed-rate codes and variable-rate codes, and we show that the latter class provides considerable improvement compared to the former. In doing this, we characterize ensemble-optimal rate functions for both types of codes. We also examine the effect of privacy leakage constraints for both fixed-rate codes and variable-rate codes.

We consider the problem of modulating a parameter onto a power-limited signal, transmitted over a discrete-time Gaussian channel and estimating this parameter at the receiver. Considering the well-known threshold effect in non-linear modulation systems, our approach is the following: instead of deriving upper and lower bounds on the total estimation error, which weigh both weak-noise errors and anomalous errors beyond the threshold, we separate the two kinds of errors. In particular, we derive upper and lower bounds on the best achievable trade-off between the exponential decay rate of the weak-noise expected error cost and the exponential decay rate of the probability of the anomalous error event, also referred to as the outage event. This outage event is left to be defined as part of the communication system design problem. Our achievability scheme, which is based on lattice codes, meets the lower bound at the high signal-to- noise (SNR) limit and for a certain range of trade-offs between the weak-noise error cost and the outage exponent.

The error exponent of the typical random code is defined as the asymptotic normalized expectation of the logarithm of the probability of error, as opposed to the traditional definition of the random coding exponent as the normalized logarithm of the expectation of the probability of error with respect to a given ensemble of codes. For a certain ensemble of independent codewords, with a given power spectrum, and a generalized stochastic mismatched decoder, we characterize the error exponent the typical random codes (TRC) for the colored Gaussian channel, with emphasis on the range of low rates, where the TRC error exponent differs in value from the ordinary random coding error exponent. The error exponent formula, which is exponentially tight at some range of low rates, is presented as the maximum of a certain function with respect to one parameter only (in the spirit of Gallager's formulas) in the case of matched decoding, and two parameters in the case of mismatched decoding. Several aspects of the main results are discussed.

The error exponent of the typical random code (TRC) in a communication scenario of source-channel coding with side information at the decoder is the main objective of this work. We derive a lower bound, which is at least as large as the random binning-coding exponent due to Merhav (2016), and we show numerically that it may be strictly larger. We deduce the exponents of the TRCs in two special cases: Slepian-Wolf (SW) source coding and joint source-channel coding. Each of these models is further studied in order to provide deeper intuition concerning the behavior of the typical random code. We also propose an alternative expression for the error exponent of typical random binning in SW model, which is given by an optimization over four parameters only, instead of a computationally heavy optimization over probability distributions.

In continuation to an earlier work, where error exponents of typical random codes were studied in the context of general block coding, with no underlying structure, here we carry out a parallel study on typical random, time-varying trellis codes, focusing on a certain range of low rates. By analyzing an upper bound to the error probability of the typical random trellis code, using the method of types, we first derive a Csiszár-style error exponent formula (with respect to the constraint length), which allows to characterize properties of good codes and dominant error events. We also derive a Gallager-style form, which turns out to be related to the expurgated error exponent. The main result is further extended to channels with memory and mismatch.

This paper contains two main contributions concerning the expurgation of hierarchical ensembles for the asymmetric broadcast channel. The first is an analysis of the optimal maximum likelihood (ML) decoders for the weak and strong user. Two different methods of code expurgation will be used, that will provide two competing error exponents. The second is the derivation of expurgated exponents under the generalized stochastic likelihood decoder (GLD). We prove that the expurgated exponents achieved for the hierarchical ensemble under GLD decoding are at least as good as the maximum between the random coding error exponents derived in an earlier work by Averbuch and Merhav (2018) and one of our ML-based expurgated exponents.

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given decoding rule. Specifically, it is assumed that the mismatched decoder has an incorrect assumption on the channel impulse response. The mismatch capacity is the highest achievable rate for a given decoding rule. The existing achievable rates for channels and decoding metrics with memory (as in our model) are currently available only in the form of multi-letter expressions that cannot be calculated. Consequently, they provide little insight on the mismatch problem. In this paper, we derive the computable formulas of achievable rates and discuss some implications of our results. Our achievable rates are based on two ensembles: the ensemble of codewords generated by an autoregressive process and the ensemble of codewords drawn uniformly over a “type class” of real-valued sequences. We provide a few numerical results of our achievable rates, as functions of the mismatched ISI parameters. Finally, we compare our results with universal decoders which are designed outside the true class of channels that we consider in this paper.

Biometric authentication systems, based on secret key generation, work as follows. In the enrollment stage, an individual provides a biometric signal that is mapped into a secret key and a helper message, the former being prepared to become available to the system at a later time (for authentication), and the latter is stored in a public database. When an authorized user requests authentication, claiming his/her identity to be one of those of the subscribers, he/she has to provide a biometric signal again, and then the system, which retrieves also the helper message of the claimed subscriber, produces an estimate of the secret key that is finally compared to the secret key of the claimed user. In the case of a match, the authentication request is approved; otherwise, it is rejected. Evidently, there is an inherent tension between two desired, but conflicting, properties of the helper message encoder; on the one hand, the encoding should be informative enough concerning the identity of the real subscriber, in order to approve him/her in the authentication stage, but on the other hand, it should not be too informative, as otherwise, unauthorized imposters could easily fool the system and gain access. A good encoder should then trade off the two kinds of errors: the false reject (FR) error and the false accept (FA) error. In this paper, we investigate trade-offs between the random coding FR error exponent and the best achievable FA error exponent. We compare two types of ensembles of codes: fixed-rate codes and variable-rate codes, and we show that the latter class of codes offers considerable improvement compared to the former. In doing this, we characterize ensemble-optimal rate functions for both types of codes. We also examine the effect of privacy leakage constraints for both fixed-rate codes and variable-rate codes

We focus on the problem of modulating a parameter onto a power-limited signal transmitted over a discrete-time Gaussian channel and estimating this parameter at the receiver. Considering the well-known threshold effect in the non-linear modulation systems, our approach is the following: instead of deriving upper and lower bounds on the total estimation error, which weighs both weak-noise errors and anomalous errors beyond the threshold, we separate the two kinds of errors. In particular, we derive upper and lower bounds on the best achievable tradeoff between the exponential decay rate of the weak-noise expected error cost and the exponential decay rate of the probability of the anomalous error event, also referred to as the outage event. This outage event is left to be defined as a part of the communication system design problem. Our achievability scheme, which is based on lattice codes, meets the lower bound at the high signal-to-noise limit and for a certain range of tradeoffs between the weak-noise error cost and the outage exponent.

Considering the problem of risk-sensitive parameter estimation, we propose a fairly wide family of lower bounds on the exponential moments of the quadratic error, both in the Bayesian and the non-Bayesian regime. This family of bounds, which is based on a change of measures, offers considerable freedom in the choice of the reference measure, and our efforts are devoted to explore this freedom to a certain extent. Our focus is mostly on signal models that are relevant to communication problems, namely, models of a parameter-dependent signal (modulated signal) corrupted by additive white Gaussian noise, but the methodology proposed is also applicable to other types of parametric families, such as models of linear systems driven by random input signals (white noise, in most cases), and others. In addition to the well-known motivations of the risk-sensitive cost function (i.e., the exponential quadratic cost function), which is most notably, the robustness to model uncertainty, we also view this cost function as a tool for studying fundamental limits concerning the tail behavior of the estimation error. Another interesting aspect that we demonstrate in a certain parametric model is that the risk-sensitive cost function may be subjected to phase transitions, owing to some analogies with statistical mechanics.

We study the ensemble performance of biometric authentication systems, based on secret key generation, which work as follows. In the enrollment stage, an individual provides a biometric signal that is mapped into a secret key and a helper message, the former being prepared to become available to the system at a later time (for authentication), and the latter is stored in a public database. When an authorized user requests authentication, claiming his/her identity as one of the subscribers, s/he has to provide a biometric signal again, and then the system, which retrieves also the helper message of the claimed subscriber, produces an estimate of the secret key, that is finally compared to the secret key of the claimed user. In case of a match, the authentication request is approved, otherwise, it is rejected. Referring to an ensemble of systems based on Slepian-Wolf binning, we provide a detailed analysis of the false-reject and false-accept probabilities, for a wide class of stochastic decoders. We also comment on the security for the typical code in the ensemble.

We define the error exponent of the typical random code as the long-block limit of the negative normalized expectation of the logarithm of the error probability of the random code, as opposed to the traditional random coding error exponent, which is the limit of the negative normalized logarithm of the expectation of the error probability. For the ensemble of uniformly randomly drawn fixed composition codes, we provide exact error exponents of typical random codes for a general discrete memoryless channel (DMC) and a wide class of (stochastic) decoders, collectively referred to as the generalized likelihood decoder (GLD). This ensemble of fixed composition codes is shown to be no worse than any other ensemble of independent codewords that are drawn under a permutation-invariant distribution (e.g., i.i.d. codewords). We also present relationships between the error exponent of the typical random code and the ordinary random coding error exponent, as well as the expurgated exponent for the GLD. Finally, we demonstrate that our analysis technique is applicable also to more general communication scenarios, such as list decoding (for fixed-size lists) as well as decoding with an erasure/list option in Forney's sense. All proofs appear in the full version of this paper, https://arxiv.org/pdf/708.07301.pdf.

This paper contains two main contributions concerning the asymmetric broadcast channel. The first is an analysis of the exact random coding error exponents for both users, and the second is the derivation of universal decoders for both users. These universal decoders are certain variants of the maximum mutual information universal decoder, and they achieve the corresponding random coding exponents of optimal decoding. In addition, we introduce some lower bounds, which involve optimizations over very few parameters, unlike the original, exact exponents, which involve minimizations over auxiliary probability distributions. Numerical results for the binary symmetric broadcast channel show improvements over previously derived error exponents for the same model.

This paper focuses on the problem of separately modulating and jointly estimating two independent continuous-valued parameters sent over a Gaussian multiple-access channel (MAC) under the mean square error (MSE) criterion without bandwidth constraints. To this end, we first improve an existing lower bound on the MSE that is obtained using the parameter modulation-estimation techniques for the single-user additive white Gaussian noise (AWGN) channel. As for the main contribution of this paper, this improved modulation-estimation analysis is generalized to the model of the two-user Gaussian MAC. We present outer bounds to the achievable region in the plane of the MSE's of the two user parameters, which provides a trade-off between the MSE's, where we used zero-rate lower bounds on the error probability of Gaussian channels by Shannon and Polyanskiy et al. Numerical results showed that, the multi-user adaptation of the zero-rate lower bound by Polyanskiy et al. provides a tighter overall lower bound on the MSE pairs than the classical Shannon bound. In addition, we introduced upper bounds on the MSE exponents, namely, the exponential decay rates of these MSE's in the asymptotic regime of long blocks that could make use of any bound on the error exponent of a single-user AWGN channel. The obtained results are numerically evaluated for three different bounds on the reliability function of the Gaussian channel. It is shown that the adaptation of the reliability function by Ashikhmin et al. to the MAC provides a significantly tighter characterization than Shannon's sphere-packing bound and the divergence bound.

This work contains two main contributions concerning the degraded broadcast channel. The first is an analysis of the exact random coding error exponents for both users, and the second is the derivation of universal decoders for both users. These universal decoders are certain variants of the maximum mutual information (MMI) universal decoder, and which achieve the corresponding random coding exponents. In addition, we introduce some lower bounds, which involve optimization over very few parameters, unlike the original, exact exponents, which involve minimizations over auxiliary probability distributions. Numerical results for the binary symmetric broadcast channel are given as well, which show improvements over previously derived error exponents for the same model.

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given (possibly suboptimal) metric decoding rule. Specifically, it is assumed that the mismatched decoder has incorrect knowledge of the ISI coefficients (or, the impulse response function). The mismatch capacity is the highest achievable rate for a given decoding rule. Unfortunately, existing lower bounds to the mismatch capacity for multi-letter channels and decoding metrics (or, channels and decoding metrics with memory), as in our model, are presented only in the form of multi-letter expressions, and thus cannot be calculated in practice. In this paper, we derive a computable single-letter lower bound to the mismatch capacity, and discuss some implications of our results.

Motivated by applications of biometric identification and content identification systems, we consider the problem of random coding for channels, where each codeword undergoes vector quantization, and where the decoder bases its decision only on the compressed codewords and the channel output, which is in turn, the channel's response to the transmission of an original codeword, before compression. For memoryless sources and memoryless channels with finite alphabets, we propose a new universal decoder and analyze its error exponent, which improves on an earlier result by Dasarathy and Draper (2011), who used the classic maximum mutual information (MMI) universal decoder. We show that our universal decoder provides the same error exponent as that of the optimal, maximum likelihood (ML) decoder, at least as long as all single-letter transition probabilities of the channel are positive.

We consider the problem of lossless compression of individual sequences using finite-state (FS) machines, from the perspective of the best achievable empirical cumulant generating function (CGF) of the code length, i.e., the normalized logarithm of the empirical average of the exponentiated code length. Since the probabilistic CGF is minimized in terms of the Rényi entropy of the source, one of the motivations of this paper is to derive an individual-sequence analogue of the Rényi entropy, in the same way that the FS compressibility is the individual-sequence counterpart of the Shannon entropy. We consider the CGF of the code-length both from the perspective of fixed-to-variable length coding and the perspective of variable-to-variable (V-V) length coding, where the latter turns out to yield a better result, that coincides with the FS compressibility. We also extend our results to compression with side information, available at both the encoder and decoder. In this case, the V-V version no longer coincides with the FS compressibility, but results in a different complexity measure.

We consider the topic of universal decoding with a decoder that does not have direct access to the codebook, but only to noisy versions of the various randomly generated codewords, a problem motivated by biometrical identification systems. Both the source that generates the original (clean) codewords, and the channel that corrupts them in generating the noisy codewords, as well as the main channel for communicating the messages, are all modeled by non-unifilar, finite-state systems (hidden Markov models). As in previous works on universal decoding, here too, the average error probability of our proposed universal decoder is shown to be as small as that of the optimal maximum likelihood (ML) decoder, up to a multiplicative factor that is a sub-exponential function of the block length. It therefore has the same error exponent, whenever the ML decoder has a positive error exponent. The universal decoding metric is based on Lempel-Ziv (LZ) incremental parsing of each noisy codeword jointly with the given channel output vector, but this metric is somewhat different from the one proposed in earlier works on universal decoding for finite-state channels, by Ziv (1985) and by Lapidoth and Ziv (1998). The reason for the difference is that here, unlike in those earlier works, the probability distribution that governs the (noisy) codewords is, in general, not uniform across its support. This non-uniformity of the codeword distribution also makes our derivation more challenging. Another reason for the more challenging analysis is the fact that the effective induced channel between the noisy codeword of the transmitted message and the main channel output is not a finite-state channel in general.

The problem of modulating the value of a parameter onto a band-limited signal to be transmitted over a continuous-time, additive white Gaussian noise (AWGN) channel, and estimating this parameter at the receiver, is considered. The performance is measured by the mean power-α error (MPαE), which is defined as the worst-case αth order moment of the absolute estimation error. The optimal exponential decay rate of the MPαE as a function of the transmission time, is investigated. Two upper (converse) bounds on the MPαE exponent are derived, on the basis of known bounds for the AWGN channel of inputs with unlimited bandwidth. The bounds are computed for typical values of the error moment and the signal-to-noise ratio (SNR), and the SNR asymptotics of the different bounds are analyzed. The new bounds are compared to known converse and achievability bounds, which were derived from channel coding considerations.

We study the random-coding error exponent function of variable-length codes in the presence of a noiseless feedback channel, which is allowed to be used merely for a single bit feedback per each transmitted message. In this study, we harness results and analysis techniques from the theory of sequential hypothesis testing, and combine them with modern distance enumeration methods which are used in the literature on error exponents. For this setup, sometimes referred to as stop-feedback, we derive an exact single-letter expression for the random-coding error exponent over the binary symmetric channel. For symmetric discrete memoryless channels, the exact error exponent at zero rate is obtained, and a lower bound is provided for any other positive rate below capacity.

This paper is about deriving lower bounds on the error exponents for the two-user interference channel under the random coding regime for several ensembles. Specifically, we first analyze the standard random coding ensemble, where the codebooks are comprised of independently and identically distributed (i.i.d.) codewords. For this ensemble, we focus on optimum decoding, which is in contrast to other, suboptimal decoding rules that have been used in the literature (e.g., joint typicality decoding, treating interference as noise, and so on). The fact that the interfering signal is a codeword, rather than an i.i.d. noise process, complicates the application of conventional techniques of performance analysis of the optimum decoder. In addition, unfortunately, these conventional techniques result in loose bounds. Using analytical tools rooted in statistical physics, as well as advanced union bounds, we derive single-letter formulas for the random coding error exponents. We compare our results with the best known lower bound on the error exponent, and show that our exponents can be strictly better. Then, in the second part of this paper, we consider more complicated coding ensembles and find a lower bound on the error exponent associated with the celebrated Han-Kobayashi random coding ensemble, which is based on superposition coding.

Motivated by applications of biometric identification and content identification systems, we consider the problem of random coding for channels, where each codeword undergoes vector quantization, and where the decoder bases its decision only on the compressed codewords and the channel output, which is, in turn, the channel's response to the transmission of an original codeword, before compression. For memoryless sources and memoryless channels with finite alphabets, we propose a new universal decoder and analyze its error exponent, which improves on an earlier result by Dasarathy and Draper (2011), who used the classic maximum mutual information universal decoder. We show that our universal decoder provides the same error exponent as that of the optimal, maximum likelihood decoder, at least as long as all single-letter transition probabilities of the channel are positive.

The likelihood decoder is a stochastic decoder that selects the decoded message at random, using the posterior distribution of the true underlying message given the channel output. In this paper, we study a generalized version of this decoder, where the posterior is proportional to a general function that depends only on the joint empirical distribution of the output vector and the code word. This framework allows both mismatched versions and universal versions of the likelihood decoder, as well as the corresponding ordinary deterministic decoders, among many others. We provide a direct analysis method that yields the exact random coding exponent (as opposed to separate upper bounds and lower bounds that turn out to be compatible, which were derived earlier by Scarlett et al.). We also extend the result from pure channel coding to combined source and channel coding (random binning followed by random channel coding) with side information available to the decoder. Finally, returning to pure channel coding, we derive also an expurgated exponent for the stochastic likelihood decoder, which turns out to be at least as tight (and in some cases, strictly so) as the classical expurgated exponent of the maximum likelihood decoder, even though the stochastic likelihood decoder is suboptimal.

The purpose of this paper is to handle a gap that was found in the proof of Theorem 2 in the paper “The generalized stochastic likelihood decoder: random coding and expurgated bounds.”

We analyze the exact exponential decay rate of the expected amount of information leaked to the wiretapper in Wyner's wiretap channel setting using wiretap channel codes constructed from both i.i.d. and constant-composition random codes. Our analysis for those sampled from i.i.d. random coding ensemble shows that the previously known achievable secrecy exponent using this ensemble is indeed the exact exponent for an average code in the ensemble. Furthermore, our analysis on wiretap channel codes constructed from the ensemble of constant-composition random codes leads to an exponent which, in addition to being the exact exponent for an average code, is larger than the achievable secrecy exponent that has been established so far in the literature for this ensemble (which in turn was known to be smaller than that achievable by wiretap channel codes sampled from i.i.d. random coding ensemble). We show examples where the exact secrecy exponent for the wiretap channel codes constructed from random constant-composition codes is larger than that of those constructed from i.i.d. random codes and examples where the exact secrecy exponent for the wiretap channel codes constructed from i.i.d. random codes is larger than that of those constructed from constant-composition random codes. We, hence, conclude that, unlike the error correction problem, there is no general ordering between the two random coding ensembles in terms of their secrecy exponent.

A Shannon cipher system for memoryless sources in which distortion is allowed at the legitimate decoder is considered. The source is compressed using a secured rate distortion code, which satisfies a constraint on the compression rate, as well as a constraint on the exponential rate of the excess-distortion probability at the legitimate decoder. Secrecy is measured by the exponential rate of the exiguous-distortion probability at the eavesdropper, rather than by the traditional measure of equivocation. The perfect-secrecy exponent is defined as the maximal exiguous-distortion exponent achievable when the key rate is unlimited. The reproduction-based estimate exponent is defined as the maximal exiguous-distortion exponent achievable for a genie-aided eavesdropper, which knows the secret key. Under limited key rate, it is proved that the maximal achievable exiguous-distortion exponent is equal to the minimum between the key rate plus the reproduction-based estimate exponent, and the perfect-secrecy exponent. The result is generalized to a fairly general class of variable key-rate and coding-rate codes.

It was previously shown by Hashimoto that Forney's optimal erasure decoder can be significantly simplified, in the sense that a simplified decoder achieves the same random coding bounds, for the ensemble of independent and identically distributed codewords. In this paper, the analysis of simplified decoders is refined and generalized in several aspects. First, tighter random coding bounds for simplified decoders are derived, which equal the exact exponential behavior of the fixed composition ensemble average. Second, the exponential bounds are valid both in the erasure mode and in the list mode. Third, the analysis pertains to a rather general class of simplified decoders, including the case of mismatch in the threshold function of the decoder. Fourth, expurgated exponents, which are larger than the random coding exponents at low rates, are shown to be achievable using a significantly simpler decoder than Forney's optimal decoder. It is shown numerically that, from the aspect of exact random coding exponents, a decoder in the spirit of Hashimoto's is as good as Forney's in the erasure mode, as well as in the list mode.

The problem of block-coded communication where in each block the channel law belongs to one of two disjoint sets is considered. The decoder is aimed to decode only messages that have undergone a channel from one of the sets, and thus has to detect the set which contains the underlying channel. The simplified case where each of the sets is a singleton is studied first. The decoding error, false alarm, and misdetection probabilities of a given code are defined, and the optimum detection/decoding rule in a generalized Neyman-Pearson sense is derived. Sub-optimal detection/decoding rules are also introduced which are simpler to implement. Then, various achievable bounds on the error exponents are derived, including the exact single-letter characterization of the random coding exponents for the optimal detector/decoder. The random coding analysis is then extended to general sets of channels, and an asymptotically optimal detector/decoder under a worst case formulation of the error probabilities is derived, as well as its random coding exponents. The case of a pair of binary symmetric channels is discussed in detail.

We consider a setting of Slepian-Wolf coding, where the random bin of the source vector undergoes channel coding, and then decoded at the receiver, based on additional side information, correlated to the source. For a given distribution of the randomly selected channel codewords, we propose a universal decoder that depends on the statistics of neither the correlated sources nor the channel, assuming first that they are both memoryless. Exact analysis of the random-binning/random-coding error exponent of this universal decoder shows that it is the same as the one achieved by the optimal maximum a-posteriori (MAP) decoder. Previously known results on universal Slepian-Wolf source decoding, universal channel decoding, and universal source-channel decoding, are all obtained as special cases of this result. Subsequently, we further generalize the results in two directions: (i) finite-state sources and finite-state channels, along with a universal decoding metric that is based on Lempel-Ziv parsing, and (ii) full (symmetric) Slepian-Wolf coding, where both source streams are separately fed into random-binning source encoders, followed by random channel encoders, which are then jointly decoded by a universal decoder.

The likelihood decoder is a stochastic decoder that selects the decoded message at random, using the posterior distribution of the true underlying message given the channel output. In this work, we study a generalized version of this decoder where the posterior is proportional to a general function that depends only on the joint empirical distribution of the output vector and the codeword. This framework allows both mismatched versions and universal (MMI) versions of the likelihood decoder, as well as the corresponding ordinary deterministic decoders, among many others. We provide a direct analysis method that yields the exact random coding exponent (as opposed to separate upper bounds and lower bounds that turn out to be compatible, which were derived earlier by Scarlett et al.). We also extend the result from pure channel coding to combined source and channel coding (random binning followed by random channel coding) with side information (SI) available to the decoder. Finally, returning to pure channel coding, we derive also an expurgated exponent for the stochastic likelihood decoder, which turns out to be at least as tight (and in some cases, strictly so) as the classical expurgated exponent of the maximum likelihood decoder, even though the stochastic likelihood decoder is suboptimal.

We analyze the exact exponential decay rate of the expected amount of information leaked to the wiretapper in Wyner's wiretap channel setting using wiretap channel codes constructed from both i.i.d. and constant-composition random codes. Our analysis for those sampled from i.i.d. random coding ensemble shows that the previously-known achievable secrecy exponent using this ensemble is indeed the exact exponent for an average code in the ensemble. Furthermore, our analysis on wiretap channel codes constructed from the ensemble of constant-composition random codes leads to an exponent which, in addition to being the exact exponent for an average code, is larger than the achievable secrecy exponent that has been established so far in the literature for this ensemble (which in turn was known to be smaller than that achievable by wiretap channel codes sampled from i.i.d. random coding ensemble). We also show examples where the exact secrecy exponent for the wiretap channel codes constructed from random constant-composition codes is larger than that of those constructed from i.i.d. random codes.

This paper considers the problem of jointly estimating two independent continuous-valued parameters sent over a Gaussian multiple-access channel (MAC) subject to the mean square error (MSE) as a fidelity criterion. We generalize the parameter modulation-estimation analysis techniques proposed by Merhav in 2012 to a two-user multiple-access channel model to obtain outer bounds to the achievable region in the plane of the MSE's of the two user parameters, as well as the achievable region of the exponential decay rates of these MSE's in the asymptotic regime of long blocks.

A Shannon cipher system for memoryless sources is considered, in which distortion is allowed at the legitimate decoder. The source is compressed using a rate distortion code secured by a shared key, which satisfies a constraint on the compression rate, as well as a constraint on the exponential rate of the excess-distortion probability at the legitimate decoder. Secrecy is measured by the exponential rate of the exiguous-distortion probability at the eavesdropper, rather than by the traditional measure of equivocation. The perfect secrecy exponent is defined as the maximal exiguous-distortion exponent achievable when the key rate is unlimited. Under limited key rate, it is proved that the maximal achievable exiguous-distortion exponent is equal to the minimum between the average key rate and the perfect secrecy exponent, for a fairly general class of variable key rate codes.

We study the problem of universal decoding for unknown discrete memoryless channels in the presence of erasure/list option at the decoder, in the random coding regime. In particular, we harness a universal version of Forney's classical erasure/list decoder developed in earlier studies, which is based on the competitive minimax methodology, and guarantees universal achievability of a certain fraction of the optimum random coding error exponents. In this paper, we derive an exact single-letter expression for the maximum achievable fraction. Examples are given in which the maximal achievable fraction is strictly less than unity, which imply that, in general, there is no universal erasure/list decoder, which achieves the same random coding error exponents as the optimal decoder for a known channel. This is in contrast to the situation in ordinary decoding (without the erasure/list option), where optimum exponents are universally achievable, as is well known. It is also demonstrated that previous lower bounds derived for the maximal achievable fraction are not tight in general. We then analyze a generalized random coding ensemble, which incorporate a training sequence, in conjunction with a suboptimal practical decoder (“plug-in” decoder), which first estimates the channel using the available training sequence, and then decodes the remaining symbols of the codeword using the estimated channel. One of the implications of our results is setting the stage for a reasonable criterion of optimal training. Finally, we compare the performance of the “plug-in” decoder and the universal decoder, in terms of the achievable error exponents, and show that the latter is noticeably better than the former.

A well-known technique in assessing probabilities of rare events (used, e.g., in the sphere-packing bound), is that of finding a reference measure under which the event of interest has probability of order one and estimating the probability in question using the Kullback-Leibler divergence (KLD). A recent method has been proposed [2], that can be viewed as an extension of this idea in which the probability under the reference measure may itself be decaying exponentially, and the Rényi divergence (RD) is used instead. We demonstrate the usefulness of this approach in various information-theoretic settings. For channel coding, we provide a method for obtaining matched, mismatched and robust error exponent bounds, as well as new results in a variety of particular channel models. Other applications we address include rate-distortion coding and the problem of guessing.

A universal decoding procedure is proposed for the intersymbol interference (ISI) Gaussian channels. The universality of the proposed decoder is in the sense of being independent of the various channel parameters, and at the same time, attaining the same random coding error exponent as the optimal maximum-likelihood (ML) decoder, which utilizes full knowledge of these unknown parameters. The proposed decoding rule can be regarded as a frequency domain version of the universal maximum mutual information (MMI) decoder. Contrary to previously suggested universal decoders for ISI channels, our proposed decoding metric can easily be evaluated.

We consider the model of random binning and finite-temperature (FT) decoding for Slepian-Wolf (SW) codes, from a statistical-mechanical perspective. While ordinary random channel coding is intimately related to the random energy model (REM) in statistical mechanics, it turns out that random binning (for SW coding) is analogous to another, related statistical mechanical model, which we call the random dilution model (RDM). We use the latter analogy to characterize phase transitions pertaining to finite-temperature SW decoding, which are somewhat similar, but not identical, to those of FT channel decoding. We then provide the exact random coding exponent of the bit error rate (BER) as a function of the rate and the decoding temperature, and discuss its properties. Finally, a few modifications and extensions are outlined.

We analyze the optimal trade-off between the error exponent and the excess-rate exponent for variable-rate Slepian-Wolf codes. We first derive upper (converse) bounds on the optimal error and excess-rate exponents, and then lower (achievable) bounds, via a simple class of variable-rate codes which assign the same rate to all source blocks of the same type class. The resulting Slepian-Wolf codes bridge between the two extremes of fixed-rate coding, which has minimal error exponent and maximal excess-rate exponent, and average-rate coding, which has maximal error exponent and minimal excess-rate exponent.

We consider the problem of erasure/list decoding using certain classes of simplified decoders. Specifically, we assume a class of erasure/list decoders, such that a codeword is in the list if its likelihood is larger than a threshold. This class of decoders both approximates the optimal decoder of Forney, and also includes the following simplified subclasses of decoding rules: The first is a function of the output vector only, but not the codebook (which is most suitable for high rates), and the second is a scaled version of the maximum likelihood decoder (which is most suitable for low rates). We provide singleletter expressions for the exact random coding exponents of any decoder in these classes, operating over a discrete memoryless channel. For each class of decoders, we find the optimal decoder within the class, in the sense that it maximizes the erasure/list exponent, under a given constraint on the error exponent. We establish the optimality of the simplified decoders of the first and second kind for low and high rates, respectively.

We study the problem of universal decoding for unknown discrete memoryless channels in the presence of erasure/list option at the decoder, in the random coding regime. Specifically, we harness a universal version of Forney's classical erasure/list decoder developed in earlier studies, which is based on the competitive minimax methodology, and guarantees universal achievability of a certain fraction of the optimum random coding error exponents. In this paper, we derive an exact single-letter expression for the maximum achievable fraction. Examples are given in which the maximal achievable fraction is strictly less than unity, which imply that, in general, there is no universal erasure/list decoder which achieves the same random coding error exponents as the optimal decoder for a known channel. This is in contrast to the situation in ordinary decoding (without the erasure/list option), where optimum exponents are universally achievable, as is well known. It is also demonstrated that previous lower bounds derived for the maximal achievable fraction are not tight in general.

A well-known technique in estimating the probabilities of rare events in general and in information theory in particular (used, for example, in the sphere-packing bound) is that of finding a reference probability measure under which the event of interest has the probability of order one and estimating the probability in question by means of the Kullback-Leibler divergence. A method has recently been proposed in [2] that can be viewed as an extension of this idea in which the probability under the reference measure may itself be decaying exponentially, and the Rényi divergence is used instead. The purpose of this paper is to demonstrate the usefulness of this approach in various information-theoretic settings. For the problem of channel coding, we provide a general methodology for obtaining matched, mismatched, and robust error exponent bounds, as well as new results in a variety of particular channel models. Other applications we address include rate-distortion coding and the problem of guessing.

A universal decoding procedure is proposed for the intersymbol interference (ISI) Gaussian channels. The universality of the proposed decoder is in the sense of being independent of the channel parameters, and at the same time, attaining the same random coding error exponent as the optimal maximum-likelihood decoder, which utilizes full knowledge of these unknown parameters. The proposed decoding rule can be regarded as a frequency domain version of the universal maximum mutual information decoder. Contrary to previously suggested universal decoders for ISI channels, our proposed decoding metric can easily be evaluated.

We take an information theoretic perspective on a classical sparse-sampling noisy linear model and present an analytical expression for the mutual information, which plays a central role in a variety of communications/signal processing problems. Such an expression was addressed previously by bounds, by simulations, and by the (nonrigorous) replica method. The expression of the mutual information is based on techniques used, addressing the minimum mean square error analysis. Using these expressions, we study specifically a variety of sparse linear communication models, which include coding in various settings, accounting also for multiple access channels, broadcast channels, and different wiretap problems. For those, we provide single-letter expressions and derive achievable rates, capturing the communications/signal processing features of these contemporary models.

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.

We derive a single-letter formula for the zero-rate reliability (error exponent) of a finite-state channel whose state variable depends deterministically (and recursively) on past channel inputs, where the code complies with a given channel input constraint. Special attention is then devoted to the important special case of the Gaussian channel with intersymbol interference, where more explicit results are obtained.

We consider the model of random binning and finite-temperature decoding for Slepian-Wolf codes, from a statistical-mechanical perspective. While ordinary random channel coding is intimately related to the random energy model-a statistical-mechanical model of disordered magnetic materials, it turns out that random binning (for Slepian-Wolf coding) is analogous to another, related statistical-mechanical model of strong disorder, which we call the random dilution model. We use the latter analogy to characterize phase transitions pertaining to finite-temperature Slepian-Wolf decoding, which are somewhat similar, but not identical, to those of finite-temperature channel decoding. We then provide the exact random coding exponent of the bit error rate as a function of the coding rate and the decoding temperature, and discuss its properties. Finally, a few modifications and extensions of our results are outlined and discussed.

We consider the multi-user lossy source-coding problem for continuous alphabet sources. In a previous work, Ziv proposed a single-user universal coding scheme which uses uniform quantization with dither, followed by a lossless source encoder (entropy coder). In this paper, we generalize Ziv's scheme to the multi-user setting. For this generalized universal scheme, upper bounds are derived on the redundancies, defined as the differences between the actual rates and the closest corresponding rates on the boundary of the rate region. For the mean-square error distortion measure, it is shown that this scheme can achieve redundancies of no more than 0.754 b per sample for each user. These bounds are obtained without the knowledge of the multi-user rate region, which is an open problem in general. As a direct consequence of these results, the inner and outer bounds on the rate-distortion achievable region are obtained.

We analyze the optimal tradeoff between the error exponent and the excess-rate exponent for variable-rate Slepian-Wolf codes. In particular, we first derive upper (converse) bounds on the optimal error and excess-rate exponents, and then lower (achievable) bounds, via a simple class of variable-rate codes which assign the same rate to all source blocks of the same type class. Then, using the exponent bounds, we derive bounds on the optimal rate functions, namely, the minimal rate assigned to each type class, needed in order to achieve a given target error exponent. The resulting excess-rate exponent is then evaluated. Iterative algorithms are provided for the computation of both bounds on the optimal rate functions and their excess-rate exponents. The resulting Slepian-Wolf codes bridge between the two extremes of fixed-rate coding, which has minimal error exponent and maximal excess-rate exponent, and average-rate coding, which has maximal error exponent and minimal excess-rate exponent.

Compressed sensing is a signal processing technique in which data is acquired directly in a compressed form. There are two modeling approaches that can be considered: the worst-case (Hamming) approach and a statistical mechanism, in which the signals are modeled as random processes rather than as individual sequences. In this paper, the second approach is studied. Accordingly, we consider a model of the form Y = HX +W, where each component of X is given by Xi= SiUi, where {Ui} are i.i.d. Gaussian random variables, and {Si} are binary random variables independent of {Ui{, and not necessarily independent and identically distributed (i.i.d.), H ∈ ℝk×nis a random matrix with i.i.d. entries, and W is white Gaussian noise. Using a direct relationship between optimum estimation and certain partition functions, and by invoking methods from statistical mechanics and from random matrix theory, we derive an asymptotic formula for the minimum mean-square error (MMSE) of estimating the input vector X given Y and H, as k, n → ∞, keeping the measurement rate, R = k/n, fixed. In contrast to previous derivations, which are based on the replica method, the analysis carried in this paper is rigorous. In contrast to previous works in which only memoryless sources were considered, we consider a more general model which allows a certain structured dependency among the various components of the source.

New results are derived concerning random coding error exponents and expurgated exponents for list decoding with a deterministic list size L. Two asymptotic regimes are considered, the fixed list-size regime, where L is fixed independently of the block length n, and the exponential list-size, where L grows exponentially with n. We first derive a general upper bound on the list-decoding average error probability, which is suitable for both regimes. This bound leads to more specific bounds in the two regimes. In the fixed list-size regime, the bound is related to known bounds and we establish its exponential tightness. In the exponential list-size regime, we establish the achievability of the well known sphere packing lower bound. An immediate byproduct of our analysis in both regimes is the universality of the maximum mutual information (MMI) list decoder in the error exponent sense. Finally, we consider expurgated bounds at low rates, using the Csiszár-Körner-Marton approach. This expurgated bound, which involves the notion of multi-information, is also modified to apply to continuous alphabet channels, and in particular, to the Gaussian memoryless channel, where the expression of the expurgated bound becomes quite explicit.

We consider the multi-user lossy source-coding problem for continuous alphabet sources. In previous work, Ziv proposed a universal coding scheme which uses uniform quantization with dither, followed by a lossless source encoder (entropy coder). In this paper, we generalize Ziv's scheme to the multi-user setting. For this generalized scheme, upper bounds are derived on the redundancies, defined as the differences between the actual rates and the closest corresponding rates on the boundary of the rate region. It is shown that this scheme can achieve redundancies of no more than 0.754 bits per sample, for each user. These results are obtained without knowledge of the multi-user rate region, which is an open problem in general.

In information theory, mutual information characterizes the maximal gain in wealth growth rate due to knowledge of side information on a gambling result; the betting strategy that achieves this maximum is named the Kelly criterion. In physics, it was recently shown that mutual information characterizes the maximal amount of work that can be extracted from a single heat bath using measurement-based control protocols; extraction that is done using “information engines”. However, to the best of our knowledge, no relation between gambling and information engines has been presented before. In this paper, we briefly review the two and then show an analogy between gambling, where bits are converted into wealth, and information engines, where bits representing measurements are converted into energy. From this analogy follows an extension of gambling to the continuous-valued case, which can be useful for investments in the stock market using options. Moreover, the analogy enables us to use well-known methods and results from one field to solve problems in the other. We present three such cases: maximum work extraction when the probability distributions governing the system and measurements are unknown, work extraction when some energy is lost in each cycle, e.g., due to friction, and an analysis of systems with memory. In all three cases, the analogy enables us to use known results in order to obtain new ones.

We analyze the asymptotic performance of ensembles of random binning Slepian-Wolf codes, where each type class of the source might have a different coding rate. In particular, we first provide the exact encoder excess rate exponent as well as the decoder error exponent. Then, using the error exponent expression, we determine the optimal rate function, namely, the minimal rate for each type class needed to satisfy a given requirement on the decoder error exponent. The resulting excess rate exponent is then evaluated for the optimal rate function. Alternating minimization algorithms are provided for the calculation of both the optimal rate function and the excess rate exponent. It is thus exemplified that, compared to fixed-rate coding, larger error exponents may be achieved using variable-rate coding, at the price of a finite excess rate exponent.

We consider the problem of slotted asynchronous coded communication, where in each time frame (slot), the transmitter is either silent or transmits a codeword from a given (randomly selected) codebook. The task of the decoder is to decide whether transmission has taken place, and if so, to decode the message. We derive the optimum detection/decoding rule in the sense of the best trade-off among the probabilities of decoding error, false alarm, and misdetection. For this detection/decoding rule, we then derive single-letter characterizations of the exact exponential rates of these three probabilities for the average code in the ensemble. It is shown that previously suggested decoders care in general strictly sub-optimal.

We consider the problem of signal estimation (denoising) from a statistical-mechanical perspective, in continuation to a recent work on the analysis of mean-square error (MSE) estimation using a direct relationship between optimum estimation and certain partition functions. This paper consists of essentially two parts. In the first part, using the aforementioned relationship, we derive single-letter expressions of the asymptotic mismatched MSE of a codeword (from a randomly selected code), corrupted by a Gaussian vector channel. In the second part, we provide several examples to demonstrate phase transitions in the behavior of the MSE. These examples enable us to understand more deeply and to gather intuition regarding the roles of the real and the mismatched probability measures in creating these phase transitions.

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 problem of modulation and estimation of a random parameter U to be conveyed across a discrete memoryless channel. Upper and lower bounds are derived for the best achievable exponential decay rate of a general moment of the estimation error, E|Û-U|ρ, ρ ≥ 0, when both the modulator and the estimator are subjected to optimization. These exponential error bounds turn out to be intimately related to error exponents of channel coding and to channel capacity. While in general, there is some gap between the upper and the lower bounds, they asymptotically coincide both for very small and for very large values of the moment power ρ. This means that our achievability scheme, which is based on simple quantization of U followed by channel coding, is nearly optimum in both limits. Some additional properties of the bounds are discussed and demonstrated, and finally, an extension to the case of a multidimensional parameter vector is outlined, with the principal conclusion that our upper and lower bounds asymptotically coincide also for a high dimensionality.

We consider ensembles of channel codes that are partitioned into bins, and focus on analysis of exact random coding error exponents associated with an optimum decoding of the index of the bin to which the transmitted codeword belongs. Two main conclusions arise from this analysis. First, for an independent random selection of codewords within a given type class, the random coding exponent of an optimal bin index decoding is given by the ordinary random coding exponent function, computed at the rate of the entire code, independently of the exponential rate of the size of the bin. Second, for this ensemble of codes, suboptimal bin index decoding, which is based on an ordinary maximum likelihood decoding, is as good as the optimal bin index decoding in terms of the random coding error exponent achieved. Finally, for the sake of completeness, we also outline how our analysis of exact random coding exponents extends to the hierarchical ensemble that correspond to superposition coding and optimal decoding, where for each bin, first, a cloud center is drawn at random, and then the codewords of this bin are drawn conditionally indepenently given the cloud center. For this ensemble, the two conclusions, mentioned above, no longer hold necessarily in general.

Data processing lower bounds on the expected distortion are derived in the finite-alphabet semideterministic setting, where the source produces a deterministic, individual sequence, but the channel model is probabilistic, and the decoder is subjected to various kinds of limitations, e.g., decoders implementable by finite-state machines, with or without counters, and with or without a restriction of common reconstruction with high probability. Some of our bounds are given in terms of the Lempel-Ziv complexity of the source sequence or the reproduction sequence. We also demonstrate how some analogous results can be obtained for classes of linear encoders and linear decoders in the continuous alphabet case.

Some new results are derived concerning random coding error exponents and expurgated exponents for list decoding with a deterministic list-size L. Two asymptotic regimes are considered, the fixed list-size regime, where L is fixed independently of the block length n, and exponential list size, where L grows exponentially with n. We first derive a general upper bound on the list-decoding average error probability, which is suitable for both regimes. This bound leads to more specific bounds in the two regimes. In the fixed list-size regime, the bound is related to known bounds and we establish its exponential tightness. In the exponential list-size regime, we establish the achievability of the well-known sphere packing lower bound. An immediate byproduct of our analysis in both regimes is the universality of the maximum mutual information list decoder in the error exponent sense. Finally, we consider expurgated bounds at low rates, both using Gallager's approach and Csiszár-Körner-Marton approach, which is equivalent for the optimal input assignment. The latter expurgated bound, which involves the notion of multi-information, is also modified to apply to continuous alphabet channels, and in particular, to the Gaussian memoryless channel, where the expression of the expurgated bound becomes quite explicit.

The problem of joint detection and lossless source coding is considered. We derive asymptotically optimal decision rules for deciding whether or not a sequence of observations has emerged from a desired information source, and to compress it if has. In particular, our decision rules asymptotically minimize the cost of compression in the case that the data have been classified as desirable, subject to given constraints on the two kinds of the probability of error. In another version of this performance criterion, the constraint on the false alarm probability is replaced by a constraint on the cost of compression in the false alarm event. We then analyze the asymptotic performance of these decision rules. We also derive universal decision rules for the case where the underlying sources (under either hypothesis or both) are unknown, and training sequences from each source may or may not be available. Finally, we discuss how our framework can be extended in several directions.

In the above-referenced paper (ibid., vol. 60, no. 10, pp. 6024-6031, Oct. 2014), due to a typesetting error, "[-4pt]" was printed at the end of the first line of equation (2); it did not, however, belong in the equation. The IEEE regrets this error.

The performance of the achievability scheme for Wyner's wiretap channel model is examined from the perspective of the probability of correct decoding, Pc, at the wiretap channel decoder. In particular, for finite-alphabet memoryless channels, the exact random coding exponent of Pcis derived as a function of the total coding rate R1and the rate of each subcode R2. Two different representations are given for this function and its basic properties are provided. We also characterize the region of pairs of rates (R1, R2) of full security in the sense of the random coding exponent of Pc, in other words, the region where the exponent of this achievability scheme is the same as that of blind guessing at the eavesdropper side. Finally, an analogous derivation of the correct-decoding exponent is outlined for the case of the Gaussian channel.

This paper studies expurgated random-coding bounds and exponents for channel coding with a given (possibly suboptimal) decoding rule. Variations of Gallager's analysis are presented, yielding several asymptotic and nonasymptotic bounds on the error probability for an arbitrary codeword distribution. A simple nonasymptotic bound is shown to attain an exponent of Csiszár and Körner under constant-composition coding. Using Lagrange duality, this exponent is expressed in several forms, one of which is shown to permit a direct derivation via cost-constrained coding that extends to infinite and continuous alphabets. The method of type class enumeration is studied, and it is shown that this approach can yield improved exponents and better tightness guarantees for some codeword distributions. A generalization of this approach is shown to provide a multiletter exponent that extends immediately to channels with memory.

We consider the problem of coded communication, where in each time frame, the transmitter is either silent or transmits a codeword from a given (randomly selected) codebook. The task of the decoder is to decide whether transmission has taken place, and if so, to decode the message. We derive the optimum detection/decoding rule in the sense of the best tradeoff among the probabilities of decoding error, false alarm, and misdetection. For this detection/decoding rule, we then derive single-letter characterizations of the exact exponential rates of these probabilities for the average code in the ensemble. It is shown that previously proposed decoders are in general strictly suboptimal.

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 consider the problem of modulation and estimation of a random parameter U to be conveyed across a discrete memoryless channel. Upper and lower bounds are derived for the best achievable exponential decay rate of a general moment of the estimation error, E|û - U|ρ, ρ ≥ 0, when both the modulator and the estimator are subjected to optimization. These exponential error bounds turn out to be intimately related to error exponents of channel coding and to channel capacity. While in general, there is some gap between the upper and the lower bound, they asymptotically coincide both for very small and for very large values of the moment power ρ. This means that our achievability scheme, which is based on simple quantization of U followed by channel coding, is nearly optimum in both limits. Some additional properties of the bounds are discussed and demonstrated, and finally, an extension to the case of a multidimensional parameter vector is outlined, with the principal conclusion that our upper and lower bound asymptotically coincide also for a high dimensionality.

It is known that for memoryless sources, the average and maximal redundancy of fixed-to-variable length codes, such as the Shannon and Huffman codes, exhibit two modes of behavior for long blocks. It either converges to a limit or it has an oscillatory pattern, depending on the irrationality or rationality, respectively, of certain parameters that depend on the source. Here, we extend these findings for the Shannon code to the case of a Markov source, which is considerably more involved. We provide a precise characterization of the redundancy of the Shannon code redundancy for a class of irreducible, periodic and aperiodic Markov sources.

We analyze random coding error exponents associated with erasure/list Slepian-Wolf decoding using two different methods and then compare the resulting bounds. The first method follows the well known techniques of Gallager and Forney and the second method is based on a technique of distance enumeration, or more generally, type class enumeration, which is rooted in the statistical mechanics of a disordered system that is related to the random energy model (REM). The second method is guaranteed to yield exponent functions which are at least as tight as those of the first method, and it is demonstrated that for certain combinations of coding rates and thresholds, the bounds of the second method are strictly tighter than those of the first method, by an arbitrarily large factor. In fact, the second method may even yield an infinite exponent at regions where the first method gives finite values. We also discuss the option of variable-rate Slepian-Wolf encoding and demonstrate how it can improve on the resulting exponents.

In analogy to the well-known notion of finite-state compressibility of individual sequences, due to Lempel and Ziv, we define a similar notion of “finite-state encryptability” of an individual plain-text sequence, as the minimum asymptotic key rate that must be consumed by finite-state encrypters so as to guarantee perfect secrecy in a well-defined sense. Our main basic result is that the finite-state encryptability is equal to the finite-state compressibility for every individual sequence. This is in parallelism to Shannon's classical probabilistic counterpart result, asserting that the minimum required key rate is equal to the entropy rate of the source. However, the redundancy, defined as the gap between the upper bound (direct part) and the lower bound (converse part) in the encryption problem, turns out to decay at a different rate (in fact, much slower) than the analogous redundancy associated with the compression problem. We also extend our main theorem in several directions, allowing: 1) availability of side information (SI) at the encrypter/decrypter/eavesdropper, 2) lossy reconstruction at the decrypter, and 3) the combination of both lossy reconstruction and SI, in the spirit of the Wyner-Ziv problem.

We consider the problem of universal decoding for arbitrary, finite-alphabet unknown channels in the random coding regime. For a given random coding distribution and a given class of metric decoders, we propose a generic universal decoder whose average error probability is, within a subexponential multiplicative factor, no larger than that of the best decoder within this class of decoders. Since the optimum, maximum likelihood (ML) decoder of the underlying channel is not necessarily assumed to belong to the given class of decoders, this setting suggests a common generalized framework for: 1) mismatched decoding, 2) universal decoding for a given family of channels, and 3) universal coding and decoding for deterministic channels using the individual sequence approach. The proof of our universality result is fairly simple, and it is demonstrated how some earlier results on universal decoding are obtained as special cases. We also demonstrate how our method extends to more complicated scenarios, like incorporation of noiseless feedback, the multiple access channel, and continuous alphabet channels.

It is known that for memoryless sources, the average and maximal redundancy of fixed-to-variable length codes, such as the Shannon and Huffman codes, exhibit two modes of behavior for long blocks. It either converges to a limit or it has an oscillatory pattern, depending on the irrationality or rationality, respectively, of certain parameters that depend on the source. In this paper, we extend these findings, concerning the Shannon code, to the case of a Markov source. We provide a precise characterization of the convergent versus oscillatory behavior of the Shannon code redundancy for a class of irreducible, periodic, and aperiodic, Markov sources. These findings are obtained by analytic methods, such as Fourier/Fejér series analysis and spectral analysis of matrices.

In this paper, we introduce new lower bounds on the distortion of scalar fixed-rate codes for lossy compression with side information available at the receiver. These bounds are derived by presenting the relevant random variables as a Markov chain and applying generalized data-processing inequalities a la Ziv and Zakai. We show that by replacing the logarithmic function with other functions, in the data-processing theorem we formulate, we obtain new lower bounds on the distortion of scalar coding with side information at the decoder. The usefulness of these results is demonstrated for uniform sources and the convex functionQ(t)=t1-α, α > 1. The bounds in this case are shown to be better than one can obtain from the Wyner-Ziv rate-distortion function.

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.

We consider a general problem of minimizing the exponential moment of a given loss function, with an emphasis on the relation to the more common criterion of minimization the first moment of the same loss function. Our basic observation is about simple sufficient conditions for a strategy to be optimum in the exponential moment sense. This observation is useful and application examples are given. We also examine the asymptotic regime and investigate universal asymptotically optimum strategies in light of the aforementioned sufficient conditions.

The average redundancy of the Shannon code, Rn, as a function of the block length n, is known to exhibit two very different types of behavior, depending on the rationality or irrationality of certain parameters of the source: It either converges to 1/2 as n grows without bound, or it may have a non-vanishing, oscillatory, (quasi-) periodic pattern around the value 1/2 for all large n. In this paper, we make an attempt to shed some insight into this erratic behavior of Rn, by drawing an analogy with the realm of physics of wave propagation, in particular, the elementary theory of scattering and diffraction. It turns out that there are two types of behavior of wave diffraction patterns formed by crystals, which are correspondingly analogous to the two types of patterns of Rn. When the crystal is perfect, the diffraction intensity spectrum exhibits very sharp peaks, a.k.a. Bragg peaks, at wavelengths of full constructive interference. These wavelengths correspond to the frequencies of the harmonic waves of the oscillatory mode of Rn. On the other hand, when the crystal is imperfect and there is a considerable degree of disorder in its structure, the Bragg peaks disappear, and the behavior of this mode is analogous to the one where Rnis convergent.

We study data processing inequalities (DPI's) that are derived from a certain class of generalized information measures, where a series of convex functions and multiplicative likelihood ratios are nested alternately. A certain choice of the convex functions leads to an information measure that extends the notion of the Bhattacharyya distance: While the ordinary Bhattacharyya distance is based on the geometric mean of two replicas of the channel's conditional distribution, the more general one allows an arbitrary number of replicas. We apply the DPI induced by this information measure to a detailed study of lower bounds of parameter estimation under additive white Gaussian noise (AWGN) and show that in certain cases, tighter bounds can be obtained by using more than two replicas. While the resulting bound may not compete favorably with the best bounds available for the ordinary AWGN channel, the advantage of the new lower bound, becomes significant in the presence of channel uncertainty, like unknown fading. This is explained by the convexity property of the information measure.

In analogy to the well-known notion of finite-state compressibility of individual sequences, due to Lempel and Ziv, we define a similar notion of “finite-state encryptability” of an individual plaintext sequence, as the minimum asymptotic key rate that must be consumed by finite-state encrypters so as to guarantee perfect secrecy in a well-defined sense. Our main basic result is that the finite-state encryptability is equal to the finite-state compressibility for every individual sequence. This is in parallelism to Shannon's classical probabilistic counterpart result, asserting that the minimum required key rate is equal to the entropy rate of the source. However, the redundancy, defined as the gap between the upper bound (direct part) and the lower bound (converse part) in the encryption problem, turns out to decay at a different rate (in fact, much slower) than the analogous redundancy associated with the compression problem. We also extend our main theorem, allowing: (i) availability of side information (SI) at the encrypter/decrypter/eavesdropper, (ii) lossy reconstruction at the decrypter.

In this paper, we derive lower bounds on the distortion of scalar fixed-rate codes for lossy compression with side information available at the receiver. These bounds are derived by presenting the relevant random variables as a Markov chain and applying generalized data processing inequalities a la Ziv and Zakai.

In this work we analyze achievable random coding error exponents pertaining to erasure/list decoding for channels with side information present at the transmitter. The analysis is carried out using the optimal decoding rule proposed by Forney. A key ingredient in the analysis is the evaluation of moments of a certain distance enumerator. This approach leads to a new exponentially tight bounds. These results are obtained by exploring a random binning code with conditionally constant composition codewords previously proposed by Moulin and Wang. Later, these results are used to obtain an achievable random coding error exponent for ordinary decoding.

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.

The average redundancy of the Shannon code,Rn, as a function of the block lengthn, is known to exhibit two very different types of behavior, depending on the rationality or irrationality of certain parameters of the source: It either converges to 1/2 asngrows without bound, or it may have a nonvanishing, oscillatory, (quasi-) periodic pattern around the value 1/2 for all largen. In this paper, we make an attempt to shed some insight into this erratic behavior ofRn, by drawing an analogy with the realm of physics of wave propagation, in particular, the elementary theory of scattering and diffraction. It turns out that there are two types of behavior of wave diffraction patterns formed by crystals, which are correspondingly analogous to the two types of patterns ofRn. When the crystal is perfect, the diffraction intensity spectrum exhibits very sharp peaks, a.k.a. Bragg peaks, at wavelengths of full constructive interference. These wavelengths correspond to the frequencies of the harmonic waves of the oscillatory mode ofRn. On the other hand, when the crystal is imperfect and there is a considerable degree of disorder in its structure, the Bragg peaks disappear, and the behavior of this mode is analogous to the one whereRnis convergent.

We study data-processing inequalities that are derived from a certain class of generalized information measures, where a series of convex functions and multiplicative likelihood ratios is nested alternately. While these information measures can be viewed as a special case of the most general Zakai-Ziv generalized information measure, this special nested structure calls for attention and motivates our study. Specifically, a certain choice of the convex functions leads to an information measure that extends the notion of the Bhattacharyya distance (or the Chernoff divergence): While the ordinary Bhattacharyya distance is based on the (weighted) geometric mean of two replicas of the channel's conditional distribution, the more general information measure allows an arbitrary number of such replicas. We apply the data-processing inequality induced by this information measure to a detailed study of lower bounds of parameter estimation under additive white Gaussian noise (AWGN) and show that in certain cases, tighter bounds can be obtained by using more than two replicas. While the resulting lower bound may not compete favorably with the best bounds available for the ordinary AWGN channel, the advantage of the new lower bound, relative to the other bounds, becomes significant in the presence of channel uncertainty, like unknown fading. This different behavior in the presence of channel uncertainty is explained by the convexity property of the information measure.

We consider the problem of jointly optimum modulation and estimation of a real-valued random parameter, conveyed over an additive white Gaussian noise (AWGN) channel, where the performance metric is the large deviations behavior of the estimator, namely the exponential decay rate (as a function of the observation time) of the probability that the estimation error would exceed a certain threshold. Our basic result is in providing an exact characterization of the fastest achievable exponential decay rate, among all possible modulator-estimator (transmitter-receiver) pairs, where the modulator is limited only in the signal power, but not in bandwidth. This exponential rate turns out to be given by the reliability function of the AWGN channel. We also discuss several ways to achieve this optimum performance, and one of them is based on quantization of the parameter, followed by optimum channel coding and modulation, which gives rise to a separation-based transmitter, if one views this setting from the perspective of joint source-channel coding. This is in spite of the fact that, in general, when error exponents are considered, the source-channel separation theorem does not hold true. We also discuss several observations, modifications, and extensions of this result in several directions, including other channels, and the case of multidimensional parameter vectors. One of our findings concerning the latter is that there is an abrupt threshold effect in the dimensionality of the parameter vector: below a certain critical dimension, the probability of excess estimation error may still decay exponentially, but beyond this value, it must converge to unity.

Threshold effects in the estimation of parameters of non-linearly modulated, continuous-time, wide-band waveforms, are examined from a statistical physics perspective. These threshold effects are shown to be analogous to phase transitions of certain disordered physical systems. Our main message is in demonstrating that this physical point of view is insightful for understanding the interactions between two or more parameters to be estimated, from the aspects of the threshold effect.

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 derive a simple general parametric representation of the rate-distortion function of a memoryless source, where both the rate and the distortion are given by integrals whose integrands include the minimum mean square error (MMSE) of the distortion Δ =d(X,Y) based on the source symbolX, with respect to a certain joint distribution of these two random variables. At first glance, these relations may seem somewhat similar to the I-MMSE relations due to Guo, Shamai and Verdú, but they are, in fact, quite different. The new relations among rate, distortion, and MMSE are discussed from several aspects, and more importantly, it is demonstrated that they can sometimes be rather useful for obtaining non-trivial upper and lower bounds on the rate-distortion function, as well as for determining the exact asymptotic behavior for very low and for very large distortion. Analogous MMSE relations hold for channel capacity as well.

In continuation to a recent work on the statistical-mechanical analysis of minimum mean square error (MMSE) estimation in Gaussian noise via its relation to the mutual information (the I-MMSE relation), here we propose a simple and more direct relationship between optimum estimation and certain information measures (e.g., the information density and the Fisher information), which can be viewed as partition functions and hence are amenable to analysis using statistical-mechanical techniques. The proposed approach has several advantages, most notably, its applicability to general sources and channels, as opposed to the I-MMSE relation and its variants which hold only for certain classes of channels (e.g., additive white Gaussian noise channels). We then demonstrate the derivation of the conditional mean estimator and the MMSE in a few examples. Two of these examples turn out to be generalizable to a fairly wide class of sources and channels. For this class, the proposed approach is shown to yield an approximate conditional mean estimator and an MMSE formula that has the flavor of a single-letter expression. We also show how our approach can easily be generalized to situations of mismatched estimation.

We draw relationships between the generalized data processing theorems of Zakai and Ziv (1973 and 1975) and the dynamical version of the second law of thermodynamics, a.k.a. the Boltzmann H-Theorem, which asserts that the Shannon entropy,H(Xt), pertaining to a finite-state Markov process {Xt}, is monotonically nondecreasing as a function of timet, provided that the steady-state distribution of this process is uniform across the state space (which is the case when the process designates an isolated system). It turns out that both the generalized data processing theorems and the Boltzmann H-Theorem can be viewed as special cases of a more general principle concerning the monotonicity (in time) of a certain generalized information measure applied to a Markov process. This gives rise to a new look at the generalized data processing theorem, which suggests to exploit certain degrees of freedom that may lead to better bounds, for a given choice of the convex function that defines the generalized mutual information. Indeed, we demonstrate an example of a certain setup of joint source-channel coding, where this idea yields an improved lower bound on the distortion, relative to both the 1973 Ziv-Zakai lower bound and the lower bound obtained from the ordinary data processing theorem.

Threshold effects in the estimation of parameters of nonlinearly modulated, continuous-time, wide-band waveforms, are examined from a statistical physics perspective. These threshold effects are shown to be analogous to phase transitions of certain disordered physical systems in thermal equilibrium. The main message, in this work, is in demonstrating that this physical point of view may be insightful for understanding the interactions between two or more parameters to be estimated, from the aspects of the threshold effect.

We present adaptive on-line schemes for lossy encoding of individual sequences, under the conditions of the Wyner-Ziv (WZ) problem. In the first part of this paper, a set of fixed-rate scalar source codes with zero delay is presented. We propose a randomized on-line coding scheme, which achieves asymptotically (and with high probability), the performance of the best source code in the set, uniformly over all source sequences. Efficient algorithms for implementing this scheme for small and large sets of encoders are presented. In the second part of this work, we generalize our results to the case of variable-rate coding. A set of variable-rate scalar source codes is presented. This time, the performance is measured by the Lagrangian Cost (LC), which is defined as a weighted sum of the distortion and the length of the encoded sequence. Efficient algorithms for implementing the generalized on-line coding scheme are presented. We then consider the special case of lossless variable-rate coding. An on-line scheme which uses Huffman codes is presented. We show that this scheme can be implemented efficiently using the same graphic methods from the first part. Finally, combining the results from former sections, we build a generalized efficient algorithm for a structured set of variable-rate encoders.

Random coding of channel decoding with an erasure option is studied. By analyzing the large deviations behavior of the code ensemble, we obtain exact single-letter formulas for the error exponents in lieu of Forney's lower bounds. The analysis technique we use is based on an enhancement and specialization of tools for assessing the statistical properties of certain distance enumerators. We specialize our results to the setup of the binary symmetric channel case with uniform random coding distribution and derive an explicit expression for the error exponent which, unlike Forney's bounds, does not involve optimization over two parameters. We also establish the fact that for this setup, the difference between the exact error exponent corresponding to the probability of undetected decoding error and the exponent corresponding to the erasure event is equal to the threshold parameter. Numerical calculations indicate that for this setup, as well as for a Z-channel, Forney's bound coincides with the exact random coding exponent.

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.

We revisit and extend the physical interpretation recently given to a certain identity between large-deviations rate-functions, as well as applications of this identity to rate-distortion theory, as an instance of thermal equilibrium between several physical systems that are brought into contact. Our new interpretation, of mechanical equilibrium between these systems, is shown to have several advantages. This physical point of view also provides a trigger to the development of certain new alternative representations of the rate-distortion function and channel capacity.

In continuation to a recent work on the statistical-mechanical analysis of optimum estimation in Gaussian noise via its relation to the mutual information (I-MMSE relation), here we propose a more direct relation between optimum estimation and some information measures, which can be viewed as partition functions and hence are amenable to statistical-mechanical analysis. This approach has several advantages, most notably, its applicability to general sources/channels, as opposed to the I-MMSE relation and its variants which hold only for certain classes of channels. We also demonstrate the derivation of the optimum estimator and the MMSE in a few examples. One of them is generalizable to a fairly wide class of sources and channels. For this class, our approach yields an approximate conditional mean estimator and an MMSE formula that has the flavor of a single-letter expression.

Random coding of a channel with an erasure option is studied. By analyzing the large deviations behavior of the code ensemble, we obtain exact single-letter formulas for the error exponents in lieu of Forney's lower bounds. The analysis technique we use is based on an enhancement an specialization of tools for assessing the moments of certain distance enumerators. We specialize our results to the setup of the binary symmetric channel case with uniform random coding distribution and derive an explicit expression for the error exponent which, unlike Forney's bounds, does not involve optimization over two parameters. We also establish the fact that for this setup, the difference between the exact error exponent corresponding to the probability of undetected decoding error and the error exponent corresponding to the erasure event is equal to the threshold parameter. Numerical calculations indicate that for this setup, as well as for a Z-channel, Forney's bound coincides with the exact random coding exponent.

The problem of optimum watermark embedding and detection was addressed in a recent paper by Merhav and Sabbag, where the optimality criterion was the maximum false-negative error exponent subject to a guaranteed false-positive error exponent. In particular, Merhav and Sabbag derived universal asymptotically optimum embedding and detection rules under the assumption that the detector relies solely on second-order joint empirical statistics of the received signal and the watermark. In the case of a Gaussian host signal and a Gaussian attack, however, closed-form expressions for the optimum embedding strategy and the false-negative error exponent were not obtained in that work. In this paper, we derive the false-negative error exponent for any given embedding strategy and use such a result to show that in general the optimum embedding rule depends on the variance of the host sequence and the variance of the attack noise. We then focus on high signal-to-noise ratio (SNR) regime, deriving the optimum embedding strategy for such a setup. In this case, a universally optimum embedding rule turns out to exist and to be very simple with an intuitively appealing geometrical interpretation. The effectiveness of the newly proposed embedding strategy is evaluated numerically.

Exponential error bounds for the finite-alphabet interference channel (IFC) with two transmitter–receiver pairs, are investigated under the random coding regime. Our focus is on optimum decoding, as opposed to heuristic decoding rules that have been used in previous works, like joint typicality decoding, decoding based on interference cancellation, and decoding that considers the interference as additional noise. Indeed, the fact that the actual interfering signal is a codeword and not an independent and identically distributed (i.i.d.) noise process complicates the application of conventional techniques to the performance analysis of the optimum decoder. Using analytical tools rooted in statistical physics, we derive a single-letter expression for error exponents achievable under optimum decoding and demonstrate strict improvement over error exponents obtainable using suboptimal decoding rules, but which are amenable to more conventional analysis.

Consider a source that produces independent copies of a triplet of jointly distributed random variables{Xi,Yi,Zi}z =1∞. The process{Xi} is observed at the encoder, and is supposed to be reproduced at two decoders, decoder Y and decoder Z, where{Yi} and{Zi} are observed, respectively, in either a causal or noncausal manner. The communication between the encoder and the decoders is carried in two successive stages. In the first stage, the transmission is available to both decoders and they reconstruct the source according to the received bit-stream and the individual side information ({Zi} or{Yi}). In the second stage, additional information is sent to both decoders and they refine the reconstructions of the source according to the available side information and the transmissions at both stages. It is desired to find the necessary and sufficient conditions on the communication rates between the encoder and decoders, so that the distortions incurred (at each stage) will not exceed given thresholds. For the case of causal availability of side information at the decoders, an exact single-letter characterization of the achievable region is derived for the case of pure source-coding. Then, for the case of communication between the encoder and decoders carried over independent memoryless discrete channels with random states known causally/noncausally at the encoder and with causal side information about the source at the decoders, a single-letter characterization of all achievable distortion in both stages is provided and it is shown that the separation theorem holds. The results are derived without assuming any structural restrictions on side information, such as a Markov structure, etc. Finally, for noncausal degraded side information, inner and outer bounds to the achievable rate-distortion region are derived. These bounds are shown to be tight for certain cases of reconstruction requirements at the decoders. Due to the system setup, these results also shed some light on a problem of successive refinement with side information which is not degraded in the usual sense.

The problem of universal simulation given a training sequence is studied both in a stochastic setting and for individual sequences. In the stochastic setting, the training sequence is assumed to be emitted by a Markov source of unknown order, extending previous work where the order is assumed known and leading to the notion of twice-universal simulation. A simulation scheme, which partitions the set of sequences of a given length into classes, is proposed for this setting and shown to be asymptotically optimal. This partition extends the notion of type classes to the twice-universal setting. In the individual sequence scenario, the same simulation scheme is shown to generate sequences which are statistically similar, in a strong sense, to the training sequence, for statistics of any order, while essentially maximizing the uncertainty on the output.

Using well-known results from statistical physics, concerning the almost-sure behavior of the free energy of directed polymers in a random medium, we prove that random tree codes achieve the distortion-rate function, not only on the average, but moreover, almost surely under a certain symmetry condition.

We provide a simple physical interpretation, in the context of the second law of thermodynamics, to the information inequality (a.k.a. the Gibbs inequality, which is also equivalent to the log-sum inequality), asserting that the relative entropy between two probability distributions cannot be negative. Since this inequality stands at the basis of the data processing theorem (DPT), and the DPT in turn is at the heart of most, if not all, proofs of converse theorems in Shannon theory, it is observed that conceptually, the roots of fundamental limits of information theory can actually be attributed to the laws of physics, in particular, the second law of thermodynamics, and indirectly, also the law of energy conservation. By the same token, in the other direction: one can view the second law as stemming from information-theoretic principles.

We consider the problem of signal estimation (denoising) from a statistical mechanical perspective, using a relationship between the minimum mean square error (MMSE), of estimating a signal, and the mutual information between this signal and its noisy version. The paper consists of essentially two parts. In the first, we derive several statistical-mechanical relationships between a few important quantities in this problem area, such as the MMSE, the differential entropy, the Fisher information, the free energy, and a generalized notion of temperature. We also draw analogies and differences between certain relations pertaining to the estimation problem and the parallel relations in thermodynamics and statistical physics. In the second part of the paper, we provide several application examples, where we demonstrate how certain analysis tools that are customary in statistical physics, prove useful in the analysis of the MMSE. In most of these examples, the corresponding statistical-mechanical systems turn out to consist of strong interactions that cause phase transitions, which in turn are reflected as irregularities and discontinuities (similar to threshold effects) in the behavior of the MMSE.

We consider a decoder with an erasure option and a variable size list decoder for channels with non-casual side information at the transmitter. First, a universally achievable region of error exponents is offered for decoding with an erasure option using a parameterized decoder in the spirit of Csiszár and Körner's decoder. Then, the proposed decoding rule is generalized by extending the range of its parameters to allow variable size list decoding. This extension gives a unified treatment for erasure/list decoding. An achievable region of exponential bounds on the probability of list error and the average number of incorrect messages on the list are given. Relations to Forney's and Csiszár and Körner's decoders for discrete memoryless channel are discussed. These results are obtained by exploring a random binning code with conditionally constant composition codewords proposed by Moulin and Wang, but with a different decoding rule and a modified analysis.

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.

Using well-known results from statistical physics, concerning the almost-sure behavior of the free energy of directed polymers in a random medium, we prove that random tree codes achieve the distortion-rate function almost surely under a certain symmetry condition.

We examine the classical joint source-channel coding problem from the viewpoint of statistical physics and demonstrate that in the random coding regime, the posterior probability distribution of the source given the channel output is dominated by source sequences, which exhibit a behavior that is highly parallel to that of thermal equilibrium between two systems of particles that exchange energy, where one system corresponds to the source and the other corresponds to the channel. The thermodynamical entropies of the dual physical problem are analogous to conditional and unconditional Shannon entropies of the source, and so, their balance in thermal equilibrium yields a simple formula for the mutual information between the source and the channel output, that is induced by the typical code in an ensemble of joint source-channel codes under certain conditions. In the full version of this paper, we also demonstrate how our results can be used in applications, like the wiretap channel, and how can it be extended to multiuser scenarios, like that of the multiple access channel.

We present adaptive on-line schemes for lossy encoding of individual sequences, under the conditions of the Wyner-Ziv (WZ) problem, i.e., the decoder has access to side information whose statistical dependency on the source is known. Both the source sequence and the side information consist of symbols taking on values in a finite alphabet X. A set of fixed-rate scalar source codes with zero delay is presented. We propose a randomized on-line coding scheme, which achieves asymptotically (and with high probability), the performance of the best source code in the set, uniformly over all source sequences. The scheme uses the same rate and has zero delay.We then present an efficient algorithm for implementing our on-line coding scheme in the case of a relatively small set of encoders. We also present an efficient algorithm for the case of a larger set of encoders with a structure, using the method of the weighted graph and the Weight Pushing Algorithm (WPA). The complexity of these algorithms is no more than linear in the sequence length.

Universally achievable error exponents pertaining to certain families of channels (most notably, discrete memoryless channels (DMCs) and various ensembles of random codes, are studied by combining the competitive minimax approach, proposed by Feder and Merhav, with Chernoff bound and Gallager's techniques for the analysis of error exponents. In particular, we derive a single-letter expression for the largest, universally achievable fractionxiof the optimum error exponent pertaining to the optimum maximum-likelihood (ML) decoding. Moreover, a simpler single-letter expression for a lower bound toxiis presented. To demonstrate the tightness of this lower bound, we use it to show thatxi=1, for the binary symmetric channel (BSC), when the random coding distribution is uniform over: i) all codes (of a given rate), and ii) all linear codes, in agreement with well-known results. We also show thatxi=1for the uniform ensemble of systematic linear codes, and for that of time-varying convolutional codes in the bit-error-rate sense. For the latter case, we also derive the corresponding universal decoder explicitly and show how it can be efficiently implemented using a slightly modified version of the Viterbi algorithm which employs two trellises.

The partition function pertaining to finite-temperature decoding of a (typical) randomly chosen code is known to have three types of behavior, corresponding to three phases in the plane of rate versus temperature: the ferromagnetic phase, corresponding to correct decoding, the paramagnetic phase, of complete disorder, which is dominated by exponentially many incorrect codewords, and the glassy phase (or the condensed phase), where the system is frozen at minimum energy and dominated by subexponentially many incorrect codewords. We show that the statistical physics associated with the two latter phases are intimately related to random coding exponents. In particular, the exponent associated with the probability of correct decoding at rates above capacity is directly related to the free energy in the glassy phase, and the exponent associated with probability of error (the error exponent) at rates below capacity, is strongly related to the free energy in the paramagnetic phase. In fact, we derive alternative expressions of these exponents in terms of the corresponding free energies, and make an attempt to obtain some insights from these expressions. Finally, as a side result, we also compare the phase diagram associated with a simple finite-temperature universal decoder, for discrete memoryless channels, to that of the finite-temperature decoder that is aware of the channel statistics.

In an earlier work, the statistical physics associated with finite-temperature decoding of code ensembles, along with the relation to their random coding error exponents, were explored in a framework that is analogous to Derrida's random energy model (REM) of spin glasses, according to which the energy levels of the various spin configurations are independent random variables. The generalized REM (GREM) extends the REM in that it introduces correlations between energy levels in an hierarchical structure. In this paper, we explore some analogies between the behavior of the GREM and that of code ensembles which have parallel hierarchical structures. In particular, in analogy to the fact that the GREM may have different types of phase transition effects, depending on the parameters of the model, then the above-mentioned hierarchical code ensembles behave substantially differently in the various domains of the design parameters of these codes. We make an attempt to explore the insights that can be imported from the statistical mechanics of the GREM and be harnessed to serve for code design considerations and guidelines.

We examine the classical joint source-channel coding problem from the viewpoint of statistical physics and demonstrate that in the random coding regime, the posterior probability distribution of the source given the channel output is dominated by source sequences, which exhibit a behavior that is highly parallel to that of thermal equilibrium between two systems of particles that exchange energy, where one system corresponds to the source and the other corresponds to the channel. The thermodynamical entropies of the dual physical problem are analogous to conditional and unconditional Shannon entropies of the source, and so, their balance in thermal equilibrium yields a simple formula for the mutual information between the source and the channel output, that is induced by the typical code in an ensemble of joint source-channel codes under certain conditions. This formula, as well as the statistical-mechanical perspective that leads to it, form the main contribution of this paper. We also demonstrate how our results can be used in applications, like the wiretap channel, and how can it be extended to multiuser scenarios, like that of the multiple access channel.

We consider the problem of universal simulation of a memoryless source (with some partial extensions to Markov sources), based on a training sequence emitted from the source. The objective is to maximize the conditional entropy of the simulated sequence given the training sequence, subject to a certain distance constraint between the probability distribution of the output sequence and the probability distribution of the input, training sequence. We derive, for several distance criteria, single-letter expressions for the maximum attainable conditional entropy as well as corresponding universal simulation schemes that asymptotically attain these maxima.

Universally achievable error exponents pertaining to certain families of channels (most notably, discrete memoryless channels (DMCpsilas)), and various ensembles of random codes, are studied by combining the competitive minimax approach, proposed by Feder and Merhav, with the Chernoff bound and Gallagerpsilas techniques for the analysis of error exponents. In particular, we derive a single-letter expression for the largest, universally achievable fraction zeta of the optimum error exponent pertaining to the optimum ML decoding. Moreover, a simpler single-letter expression for a lower bound to zeta is presented. To demonstrate the tightness of this lower bound, we use it to show that zeta = 1, for the binary symmetric channel (BSC), when the random coding distribution is uniform over: (i) all codes (of a given rate), and (ii) all linear codes, in agreement with well-known results. We also show that zeta = 1 for the uniform ensemble of systematic linear codes, and for that of time-varying convolutional codes in the bit-error-rate sense. For the latter case, we also show how the corresponding universal decoder can be efficiently implemented using a slightly modified version of the Viterbi algorithm which employs two trellises.

It is well known from the information theory literature that in the presence of a memoryless channel, as well as some channels with memory, the existence of feedback does not improve channel capacity, but can contribute dramatically to the simplification of the encoder and the decoder. In this paper, we focus on estimating the parameters of an unknown channel when a feedback link from the decoder to the encoder is given. We examine different types of channels and study the conditions under which feedback improves the estimation in the sense of the Cramer-Rao bound (CRB). We additionally find what is the best strategy for designing channel input signals and the channel parameter estimator of the receiver. By assuming a certain class of parametric models for the channel, we show that feedback is essential when some nuisance parameters of the model are unknown, but it is superfluous when there are no unknown nuisance parameters.

Exponential error bounds for the finite-alphabet interference channel (IPC) with two transmitter-receiver pairs, are investigated under the random coding regime. Our focus is on optimum decoding, as opposed to heuristic decoding rules that have been used in previous works, like joint typicality decoding, decoding based on interference cancellation, and decoding that considers the interference as additional noise. Indeed, the fact that the actual interfering signal is a codeword and not an i.i.d. noise process complicates the performance analysis of the optimum decoder. In addition to the single-letter expressions of the error exponents derived, we also present some numerical results and discuss them.

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.

An identity between two versions of the large deviations rate function of the probability a certain rare event is established. This identity has an interpretation in statistical physics, namely, an isothermal equilibrium of a composite system that consists of multiple subsystems. Several information-theoretic application examples, where the analysis of this large deviations probability naturally arises, are then described from the viewpoint of this statistical mechanical interpretation. This results in several relationships between information theory and statistical physics, which we hope, the reader will find insightful.

The partition function of finite-temperature decoding of a typical random code has three phases in the plane of rate vs. temperature: the ferromagnetic phase, corresponding to correct decoding, the paramagnetic phase, which is dominated by exponentially many incorrect codewords, and the glassy phase, where the system is frozen at minimum energy and dominated by subexponentially many incorrect codewords. We show that the statistical physics of the two latter phases are intimately related to random coding exponents: The exponent of the probability of correct decoding at rates above capacity is directly related to the free energy in the glassy phase, and the exponent associated with the error probability at rates below capacity is strongly related to the free energy in the paramagnetic phase. We derive alternative expressions of these exponents in terms of the corresponding free energies, and make an attempt to obtain insights from them.

We consider a decoder with an erasure option and a variable size list decoder for channels with non-causal side information at the transmitter. First, universally achievable error exponents are offered for decoding with an erasure option using a parameterized decoder in the spirit of Csiszar and Korner's decoder. Then, the proposed decoding rule is generalized by extending the range of its parameters to allow variable size list decoding. This extension gives a unified treatment for erasure/list decoding. Exponential bounds on the probability of list error and the average number of incorrect messages on the list are given. Relations to Forney's and Csiszar and Korner's decoders for DMC are discussed. These results are obtained by exploring a random binning code with conditionally constant composition codewords proposed by Moulin and Wang, but with a different decoder.

The use of digital watermarking in real applications is impeded by the weakness of current available algorithms against signal processing manipulations leading to the desynchronization of the watermark embedder and detector. For this reason, the problem of watermarking under geometric attacks has received considerable attention throughout recent years. Despite their importance, only few classes of geometric attacks are considered in the literature, most of which consist of global geometric attacks. The random bending attack contained in the Stirmark benchmark software is the most popular example of a local geometric transformation. In this paper, we introduce two new classes of local desynchronization attacks (DAs). The effectiveness of the new classes of DAs is evaluated from different perspectives including perceptual intrusiveness and desynchronization efficacy. This can be seen as an initial effort towards the characterization of the whole class of perceptually admissible DAs, a necessary step for the theoretical analysis of the ultimate performance reachable in the presence of watermark desynchronization and for the development of a new class of watermarking algorithms that can efficiently cope with them.

We consider the problem of sequential decision making for random fields corrupted by noise. In this scenario, the decision maker observes a noisy version of the data, yet judged with respect to the clean data. In particular, we first consider the problem of scanning and sequentially filtering noisy random fields. In this case, the sequential filter is given the freedom to choose the path over which it traverses the random field (e.g., noisy image or video sequence), thus it is natural to ask what is the best achievable performance and how sensitive this performance is to the choice of the scan. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance, and quantify the excess loss occurring when nonoptimal scanners are used, compared to optimal scanning and filtering.

Consider a process, {XiYi,Zi}infini=1producing independent copies of a triplet of jointly distributed random variables (RVs). The part of the process - the source - is observed at the encoder, and is supposed to be reproduced at two decoders, decoder 1 and decoder 2, where the {Zi} and the {Yi} parts of the process are observed, respectively, in a causal manner. The communication between the encoder and the decoders is carried out across two memoryless channels in two successive communication stages. In the first stage, the compressed transmission is available to both decoders, but only decoder 1 reconstructs the source (according to the received data stream and its causal side information (SI){Zi}). In the second stage, the second decoder reconstructs the source according to {Yi} and the transmissions of the encoder at both stages. It is desired to find necessary and sufficient conditions such that the distortions incurred (in each stage) will not exceed given thresholds. First, a single-letter characterization of achievable rates is derived for a pure source-coding problem with successive refinement and causal SI at the decoders. Then, for a joint source-channel coding setting, a separation theorem is proved, asserting that in the limit of long blocks, no optimality is lost by first applying lossy successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bit streams, regardless of the source. Next, conditions for a source to be successively refinable in two different senses are established, and finally, it is shown that the binary-symmetric source is successively refinable.

Shannon's secrecy system is studied in a setting, where both the legitimate decoder and the wiretapper have access to side information sequences correlated to the source, but the wiretapper receives both the coded information and the side information via channels that are more noisy than the respective channels of the legitmate decoder, which in turn, also shares a secret key with the encoder. A single-letter characterization is provided for the achievable region in the space of five figures of merit: the equivocation at the wiretapper, the key rate, the distortion of the source reconstruction at the legitimate receiver, the bandwidth expansion factor of the coded channels, and the average transmission cost (generalized power). Beyond the fact that this is an extension of earlier studies, it also provides a framework for studying fundamental performance limits of systematic codes in the presence of a wiretap channel. The best achievable performance of systematic codes is then compared to that of a general code in several respects, and a few examples are given.

An identity between two versions of the rate function of the probability a certain large deviations event is established. This identity has an interpretation in statistical physics, namely, an isothermal equilibrium of a composite system that consists of multiple subsystems of particles. Several information-theoretic application examples, where the analysis of this large deviations probability naturally arises, are then described from the viewpoint of this statistical mechanical interpretation. This results in several relationships between information theory and statistical physics, which we hope, the reader will find insightful.

The analysis of random coding error exponents pertaining to erasure/list decoding, due to Forney, is revisited. Instead of using Jensen's inequality as well as some other inequalities in the derivation, we demonstrate that an exponentially tight analysis can be carried out by assessing the relevant moments of certain distance enumerators. The resulting bound has the following advantages: (i) it is at least as tight as Forney's bound, (ii) under certain symmetry conditions associated with the channel and the random coding distribution, it is simpler than Forney's bound in the sense that it involves an optimization over one parameter only (rather than two), and (iii) in certain special cases, like the binary symmetric channel (BSC), the optimum value of this parameter can be found in closed form, and so, there is no need to conduct a numerical search. We have not found yet a numerical example where this new bound is strictly better than Forney's bound and this may provide an additional evidence to support Forney's conjecture that his bound is tight for the average code. However, when applying the proposed analysis technique to a certainuniversaldecoder with erasures, we demonstrate that it may yield significantly tighter exponential error bounds. We believe that this technique can be useful in simplifying and improving exponential error bounds in other problem settings as well.

An information-theoretic approach is proposed to watermark embedding and detection under limited detector resources. First, the attack-free scenario is considered under which asymptotically optimal decision regions in the Neyman-Pearson sense are proposed, along with the optimal embedding rule. Later, the case of zero-mean independent and identically distributed (i.i.d.) Gaussian covertext distribution is explored with unknown variance under the attack-free scenario. For this case, a lower bound on the exponential decay rate of the false-negative probability is proposed. It is proven that the optimal embedding and detecting strategy is superior to the customary linear, additive embedding strategy in the exponential sense. Finally, these results are extended to the case of memoryless attacks and general worst case attacks. Optimal decision regions and embedding rules are offered, and the worst attack channel is identified.

Universal, delay-limited simulation of an unknown information source of a certain parametric family (e.g., the family of memoryless sources or Markov sources of a given order), given a training sequence from that source and a stream of independent and uniformly distributed bits, is considered. The goal of universal simulation is that the probability law of the generated sequence be identical to that of the training sequence, with minimum mutual information between the random processes generating both sequences. In the delay-limited setting, the simulation algorithm generates a random sequence sequentially, by delivering one symbol for each training symbol that is made available after a given initial delay, whereas the random bits are assumed to be available on demand. In this paper, the optimal universal delay-limited simulation scheme is characterized for broad parametric families, and the mutual information achieved by the proposed scheme is analyzed. The results are extended to a setting of variable delay.

In this correspondence, we correct an error in the above paper by Somekh-Baruch and Merhav (see ibid., vol.51, no.3, p.884-99, 2005).

We consider the problem of sequential decision making on random fields corrupted by Additive White Gaussian Noise (AWGN). In particular, we first consider the problem of sequentially filtering an AWGN-corrupted random field. In this scenario, the sequential filter may be given the freedom to choose the path over which it traverses the random field (e.g., noisy image), thus it is natural to ask what is the best achievable performance and how far is the performance of widely used scanning methods from the optimum. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance and quantify the excess loss occurring when non-optimal scanners are used, compared to optimal scanning and filtering. We then discuss the problem of sequential scanning and prediction of noisy random fields. This setting is a natural model for applications such as restoration and coding of noisy images. In this scenario, using predictive coding methods on the noisy image results in both enhancement and compression of the input image, as one expects that the prediction error consists mainly of the noise signal. We formally define the problem of sequential prediction in a noisy array and compute the optimal performance in terms of the clean scandictability defined by Merhav and Weissman.

Consider a source, {Xi, Yi, Zi}i=1infin, producing independent copies of a triplet of jointly distributed random variables (RVs). The {Xi} part of the process is observed at the encoder, and is supposed to be reproduced at two decoders, decoder 1 and decoder 2 , where the {Yi} and the {Zi} parts of the process are observed, respectively, in either a causal or a non-causal manner. The communication between the encoder and the decoders is carried in two successive communication stages. In the first stage, the transmission is available to both decoders and the decoders reconstruct the source according to the received stream and individual side information ({Zi} or {Yi}). In the second stage, additional information is sent to both decoders and the decoders refine the reconstruction of the source according to the side information available to it and the transmissions in both stages. It is desired to find the necessary and sufficient conditions on communication between the encoder and decoders, so that the distortions incurred (at each stage) will not exceed given thresholds. For such a multi-decoder coding setting with successive refinement and non-causal degraded side information, we derive inner and outer bounds to the achievable rate-distortion region. Then, for the case of general causal side information at the decoders, we derive a single-letter characterization of the achievable region for a multi-decoder source-coding problem with successive refinement.

The problem of universal simulation given a training sequence is studied both in a stochastic setting and for individual sequences. In the stochastic setting, the training sequence is assumed to be emitted by a Markov source of unknown order, extending previous work where the order is assumed known and leading to the notion of twice-universal simulation. A simulation scheme, which partitions the set of sequences of a given length into classes, is proposed for this setting and shown to be asymptotically optimal. This partition extends the notion of type classes to the twice-universal setting. In the individual sequence scenario, the same simulation scheme is shown to generate sequences which are statistically similar, in a strong sense, to the training sequence, for statistics of any order, while essentially maximizing the uncertainty on the output.

Shannon's secrecy system is studied in a setting, where both the legitimate decoder and the wiretapper have access to side information sequences correlated to the source, but the wiretapper receives both the coded information and the side information via channels that are more noisy than the respective channels of the legitimate decoder, which in turn, also shares a secret key with the encoder. A single-letter characterization is provided for the achievable region in the space of five figures of merit: the equivocation at the wiretapper, the key rate, the distortion of the source reconstruction at the legitimate receiver, the bandwidth expansion factor of the coded channels, and the average transmission cost (generalized power). Beyond the fact that this is an extension of earlier studies, it also provides a framework for studying fundamental performance limits of systematic codes in the presence of a wiretap channel. The best achievable performance of systematic codes is then compared to that of a general code in several respects, and a few examples are given.

Motivated by applications of rateless coding, decision feedback, and automatic repeat request (ARQ), we study the problem of universal decoding for unknown channels in the presence of an erasure option. Specifically, we harness the competitive minimax methodology developed in earlier studies, in order to derive a universal version of Forney's classical erasure/list decoder, which in the erasure case, optimally trades off between the probability of erasure and the probability of undetected error. The proposed universal erasure decoder guarantees universal achievability of a certain fraction xi of the optimum error exponents of these probabilities. A single-letter expression for xi, which depends solely on the coding rate and the Neyman-Pearson threshold, is provided. The example of the binary symmetric channel is studied in full detail, and some conclusions are drawn.

We revisit the problem of optimal watermark embedding and detection for computationally limited detectors under general attack channels. First, a formal definition of the problem is given for general attack channels under the Neyman-Pearson criterion of optimality. Later, asymptotically optimal decision regions are offered, assuming that the detector is computationally limited and that the attack channel is strongly exchangeable. These results are extended to general attack channels where random watermark sequences are considered. The optimal embedding rule is offered and the worst attack channel is identified.

We investigate the problem of scanning and prediction (ldquoscandiction,rdquo for short) of multidimensional data arrays. This problem arises in several aspects of image and video processing, such as predictive coding, for example, where an image is compressed by coding the error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and whether there exist specific scandiction schemes which are universal in some sense. Specifically, we investigate the following problems: first, modeling the data array as a random field, we wish to examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution were known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a nonoptimal scanning order is used, yet accompanied by an optimal predictor, and derive bounds on the excess loss compared to optimal scanning and prediction. This paper is the first part of a two-part paper on sequential decision making for multidimensional data. It deals with clean, noiseless data arrays. The second part deals with noisy data arrays, namely, with the case where the decision maker observes only a noisy version of the data, yet it is judged with respect to the original, clean data.

Motivated by applications of rateless coding, decision feedback, and automatic repeat request (ARQ), we study the problem of universal decoding for unknown channels in the presence of an erasure option. Specifically, we harness the competitive minimax methodology developed in earlier studies, in order to derive a universal version of Forney's classical erasure/list decoder, which in the erasure case, optimally trades off between the probability of erasure and the probability of undetected error. The proposed universal erasure decoder guarantees universal achievability of a certain fraction xi of the optimum error exponents of these probabilities (in a sense to be made precise in the sequel). A single-letter expression for xi, which depends solely on the coding rate and the Neyman-Pearson threshold (to be defined), is provided. The example of the binary-symmetric channel is studied in full detail, and some conclusions are drawn

We consider the problem of rate-R, channel coding with causal/noncausal side information at the transmitter, under an additional requirement of minimizing the amount of information that can be learned from the channel output about the state sequence, which is defined in terms of the mutual information between the state sequence and the channel output sequence. A single-letter characterization is provided for the achievable region of pairs {(R, E)}. Explicit results for the Gaussian case (Costa's dirty-paper channel) are derived in full detail.

Fingerprinting systems in the presence of collusive attacks are analyzed as a game between a fingerprinter and a decoder on the one hand, and a coalition of two or more attackers on the other hand. The fingerprinter distributes, to different users, different fingerprinted copies of a host data (covertext), drawn from a memoryless stationary source, embedded with different fingerprints. The coalition members create a forgery of the data while aiming at erasing the fingerprints in order not to be detected. Their action is modeled by a multiple-access channel (MAC). We analyze the performance of two classes of decoders, associated with different kinds of error events. The decoder of the first class aims at detecting the entire coalition, whereas the second is satisfied with the detection of at least one member of the coalition. Both decoders have access to the original covertext data and observe the forgery in order to identify member(s) of the coalition. Motivated by a worst case approach, we assume that the coalition of attackers is informed of the hiding strategy taken by the fingerprinter and the decoder, while they are uninformed of the attacking scheme. Achievable single-letter expressions for the two kinds of error exponents are obtained. Single-letter lower bounds are also derived for the subclass of constant composition codes. These lower and the upper bounds coincide for the error exponent of the first class. Further, for the error of the first kind, a decoder that is optimal is introduced, and the worst case attack channel is characterized

We consider the filtering problem, where a finite-alphabet individual sequence is corrupted by a discrete memoryless channel, and the goal is to causally estimate each sequence component based on the past and present noisy observations. We establish a correspondence between the filtering problem and the problem of prediction of individual sequences which leads to the following result: Given an arbitrary finite set of filters, there exists a filter which performs, with high probability, essentially as well as the best in the set, regardless of the underlying noiseless individual sequence. We use this relationship between the problems to derive a filter guaranteed of attaining the "finite-state filterability" of any individual sequence by leveraging results from the prediction problem

Motivated by the evident success of context-tree based methods in lossless data compression, we explore, in this correspondence, methods of the same spirit in universal prediction of individual sequences. By context-tree prediction, we refer to a family of prediction schemes, where at each time instant t, after having observed all outcomes of the data sequence x1,...,xt-1, but not yet xt, the prediction is based on a "context" (or a state) that consists of the k most recent past outcomes xt-k,...,xt-1, where the choice of k may depend on the contents of a possibly longer, though limited, portion of the observed past, xt-kmax,...,xt-1. This is different from the study reported in the paper by Feder, Merhav, and Gutman (1992), where general finite-state predictors as well as "Markov" (finite-memory) predictors of fixed order, were studied in the regime of individual sequences. Another important difference between this study and the work of Feder is the asymptotic regime. While in their work, the resources of the predictor (i.e., the number of states or the memory size) were kept fixed regardless of the length N of the data sequence, here we investigate situations where the number of contexts, or states, is allowed to grow concurrently with N. We are primarily interested in the following fundamental question: What is the critical growth rate of the number of contexts, below which the performance of the best context-tree predictor is still universally achievable, but above which it is not? We show that this critical growth rate is linear in N. In particular, we propose a universal context-tree algorithm that essentially achieves optimum performance as long as the growth rate is sublinear, and show that, on the other hand, this is impossible in the linear case

We investigate several problems in scanning of multidimensional data arrays, such as universal scanning and prediction ("scandiction", for short), and scandiction of noisy data arrays. These problems arise in several aspects of image and video processing, such as predictive coding, filtering and denoising. In predictive coding of images, for example, an image is compressed by coding the prediction error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and if there exist specific scandiction schemes which are universal in some sense. More specifically, we investigate the following problems: first, given a random field, we examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution was known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a non-optimal scanning order is used, yet accompanied by an optimal predictor, and derive a bound on the excess loss compared to optimal scandiction. Finally, we examine the scenario where the random field is corrupted by noise, but the scanning and prediction (or filtering) scheme is judged with respect to the underlying noiseless field

Consider a process, {Xi, Yi, Zi}-infini=1, producing independent copies of a triplet of jointly distributed random variables (RVs). The {Xi} part of the process - the source, is observed at the encoder, and is supposed to be reproduced at two decoders, decoder 1 and decoder 2 , where the {Zi} and the {Yi} parts of the process are observed, respectively in a causal manner. The communication between the encoder and the decoders is carried out across two memoryless channels in two successive communication stages. In the first stage, the compressed transmission is available to both decoders, but only decoder 1 reconstructs the source (according to the received data-stream and its causal side information {Zi}0. In the second stage, the second decoder reconstructs the source according to {Yi} and the transmissions of the encoder in both stages. It is desired to find the necessary and sufficient conditions on communication between the encoder and decoders, so that the distortions incurred (in each round) will not exceed given thresholds. We first derive a single-letter characterization of achievable rates for a pure source-coding problem with successive refinement and causal side information at the decoders. Then, for a joint source-channel coding setting, we prove a separation theorem, asserting that in the limit of long blocks, no optimality is lost by first applying lossy successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bitstreams, regardless of the source

We consider the problem of rate-R channel coding with causal/non-causal side information at the transmitter, under an additional requirement of minimizing the amount of information that can be learned from the channel output about the state sequence, which is defined in terms of the equivocation E (i.e., the mutual information between the state sequence and the channel output sequence). A single-letter characterization is provided for the achievable region of pairs {(R, E)}. Explicit results for the Gaussian case (Costa's dirty-paper channel) are derived in full detail.

We consider the problem of universal simulation of memoryless sources and Markov sources, based on training sequence emitted from these sources. The objective is to maximize the conditional entropy of the simulated sequence given the training sequence, subject to a certain distance constraint between the probability distribution of the output sequence and the probability distribution of the input, training sequence. We derive a single-letter expression for the maximum conditional entropy and then propose a universal simulation scheme that asymptotically attains this maximum

An information-theoretic approach is proposed to the watermark embedding and detection under limited detector resources. First, asymptotically optimal decision regions are presented in the Neyman-Pearson sense. These results are also modified to the case of zero-mean i.i.d. Gaussian covertext distribution with unknown variance. For this case, a lower bound is offered on the exponential decay rate of the false-negative probability and it is proven that the optimal embedding and detecting strategy is superior to the customary linear, additive embedding strategy in the exponential sense

Motivated by the evident success of context-tree based methods in lossless data compression, we explore, in this paper, methods of the same spirit in universal prediction of individual sequences. By context-tree prediction, we refer to a family of prediction schemes, where at each time instant t, after having observed all outcomes of the data sequence x1,...,xt-1, but not yet xt, the prediction is based on a "context" (or a state) that consists of the k most recent past outcomes xt-k,...,xt-1, where the choice of k may depend on the contents of a possibly longer, though limited, portion of the observed past, xt-k(max),...,xt-1. This is different from the study reported in Feder et al. (1992), where general finite-state predictors as well as "Markov" (finite-memory) predictors of fixed order, where studied in the regime of individual sequences. Another important difference between this study and Feder et al. is the asymptotic regime. While in Feder et al., the resources of the predictor (i.e., the number of states or the memory size) were kept fixed regardless of the length N of the data sequence, here we investigate situations where the number of contexts, or states, is allowed to grow concurrently with N. We are primarily interested in the following fundamental question: What is the critical growth rate of the number of contexts, below which the performance of the best context-tree predictor is still universally achievable, but above which it is not? We show that this critical growth rate is linear in N. In particular, we propose a universal context-tree algorithm that essentially achieves optimum performance as long as the growth rate is sublinear, and show that, on the other hand, this is impossible in the linear case.

Consider a source, {X/sub i/,Y/sub i/}/sub i=1//sup /spl infin//, producing independent copies of a pair of jointly distributed random variables (RVs). The {X/sub i/} part of the process is observed at some location, say A, and is supposed to be reproduced at a different location, say B, where the {Y/sub i/} part of the process is observed. Similarly, {Y/sub i/} should be reproduced at location A. The communication between the two locations is carried out across two memoryless channels in K iterative bi-directional rounds. In each round, the source components are reconstructed at the other locations based on the information exchanged in all previous rounds and the source component known at that location, and it is desired to find the amount of information that should be exchanged between the two locations in each round, so that the distortions incurred (in each round) will not exceed given thresholds. Our setting extends the results of Steinberg and Merhav as well as Kaspi, combining the notion of successive refinement with this of two-way interactive communication. We first derive a single-letter characterization of achievable rates for a pure source-coding problem with successive refinement. Then, for a joint source-channel coding setting, we prove a separation theorem, asserting that in the limit of long blocks, no optimality is lost by first applying lossy (two-way) successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bitstreams, regardless of the source.

In continuation to earlier works where the problem of joint information embedding and lossless compression (of the composite signal) was studied in the absence [8] and in the presence [9] of attacks, here we consider the additional ingredient of protecting the secrecy of the watermark against an unauthorized party, which has no access to a secret key shared by the legitimate parties.In other words, we study the problem of joint coding for three objectives: information embedding, compression, and encryption.Our main result is a coding theorem that provides a single-letter characterization of the best achievable tradeoffs among the following parameters: the distortion between the composite signal and the covertext, the distortion in reconstructing the watermark by the legitimate receiver, the compressibility of the composite signal (with and without the key), and the equivocation of the watermark, as well as its reconstructed version, given the composite signal.In the attack-free case, if the key is independent of the covertext, this coding theorem gives rise to a threefold separation principle that tells that asymptotically, for long block codes, no optimality is lost by first applying a ratedistortion code to the watermark source, then encrypting the compressed codeword, and finally, embedding it into the covertext using the embedding scheme of [8].In the more general case, however, this separation principle is no longer valid, as the key plays an additional role of side information used by the embedding unit.

We consider the Shannon cipher system in a setting where the secret key is delivered to the legitimate receiver via a channel with limited capacity. For this setting, we characterize the achievable region in the space of three figures of merit: the security (measured in terms of the equivocation), the compressibility of the cryptogram, and the distortion associated with the reconstruction of the plaintext source. Although lossy reconstruction of the plaintext does not rule out the option that the (noisy) decryption key would differ, to a certain extent, from the encryption key, we show, nevertheless, that the best strategy is to strive for perfect match between the two keys, by applying reliable channel coding to the key bits, and to control the distortion solely via rate-distortion coding of the plaintext source before the encryption. In this sense, our result has a flavor similar to that of the classical source-channel separation theorem. Some variations and extensions of this model are discussed as well

A source of random message bits is to be embedded into a covertext modeled as a discrete memoryless source (DMS), resulting in a stegotext from which the embedded bits should be recoverable. A causal code for such a scenario consists of an encoder that generates the stegotext as a causal function of the message bits and the covertext, and a decoder that reproduces the message bits as a causal function of the stegotext. A semicausal code, on the other hand, has an encoder that is causal only with respect to the covertext, and not necessarily with respect to the message, and has a possibly noncausal decoder. We analyze the possible tradeoffs among: a) the distortion between the stegotext and the covertext, b) the compressibility of the stegotext, and c) the rate at which random bits are embedded, that are achievable with causal and semicausal codes, with and without attacks on the stegotext. We also study causal and semicausal codes for the private version of the above scenario in which the decoder has access to the covertext. Connections are made with the causal rate-distortion function of Neuhoff and Gilbert, as well as the problem of channel coding with causal side information at the transmitter analyzed by Shannon.

We consider both channel coding and source coding, with perfect past feedback/feedforward, in the presence of side information. It is first observed that feedback does not increase the capacity of the Gel'fand-Pinsker channel, nor does feedforward improve the achievable rate-distortion performance in the Wyner-Ziv problem. We then focus on the Gaussian case showing that, as in the absence of side information, feedback/feedforward allows to efficiently attain the respective performance limits. In particular, we derive schemes via variations on that of Schalkwijk and Kailath. These variants, which are as simple as their origin and require no binning, are shown to achieve, respectively, the capacity of Costa's channel, and the Wyner-Ziv rate distortion function. Finally, we consider the finite-alphabet setting and derive schemes for both the channel and the source coding problems that attain the fundamental limits, using variations on schemes of Ahlswede and Ooi and Wornell, and of Martinian and Wornell, respectively

We consider a variation of the Wyner-Ziv (W-Z) problem pertaining to lossy compression of individual sequences using finite-state encoders and decoders. There are two main results in this paper. The first characterizes the relationship between the performance of the best M-state encoder-decoder pair to that of the best block code of size lscr for every input sequence, and shows that the loss of the latter relative to the former (in terms of both rate and distortion) never exceeds the order of (logM)/lscr, independently of the input sequence. Thus, in the limit of large M, the best rate-distortion performance of every infinite source sequence can be approached universally by a sequence of block codes (which are also implementable by finite-state machines). While this result assumes an asymptotic regime where the number of states is fixed, and only the length n of the input sequence grows without bound, we then consider the case where the number of states M=Mnis allowed to grow concurrently with n. Our second result is then about the critical growth rate of Mnsuch that the rate-distortion performance of Mn-state encoder-decoder pairs can still be matched by a universal code. We show that this critical growth rate of Mnis linear in n

We extend the setting of two-stage lossy source coding with successive refinement structures into a joint source-channel coding setting. In particular, we consider a problem where two descriptions of a memoryless source are to be transmitted across two independent memoryless channels and where the output of the channel corresponding to the first (coarse) description is also available to the decoder of the second (refinement) decoder. Side information (SI), correlated to the source, may also be available to the decoders. In such a case, we confine attention to degraded SI, in the sense that the source, the SI available at the refinement decoder, and the SI available at the coarse decoder form a Markov chain in this order. Our first result is a separation theorem asserting that in the limit of long blocks, no optimality is lost by first applying lossy successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bitstreams, regardless of the source and the SI. It is also shown that (even noiseless) feedback from the output of the first channel to the input of the second encoder cannot improve performance, but may sometimes significantly facilitate the implementation of optimum codes. We provide two examples where single-letter codes (of unit block length) achieve optimum performance, if feedback from the channel output of the first stage is provided to the encoder of the refinement stage. In one of these examples, it is evident that if feedback is not provided, optimality cannot be achieved with unit length code. Motivated by these examples, we then investigate single-letter codes for this system. Necessary and sufficient conditions are furnished for the optimality of single-letter codes with and without feedback. A corollary of these conditions is that for the quadratic distortion measure, feedback is necessary to achieve optimality in single-letter codes, regardless of the source distribution and the channel statistics

We develop a single-letter lower bound on the error exponent of trellis source coding. We demonstrate that for the case of a binary source with the Hamming distortion measure, and for rates close to the rate-distortion curve, this bound is superior to Marion's block coding exponent, for the same computational complexity

Consider a source, {Xi, Yi}i=1infin, producing independent copies of a pair of jointly distributed RVs. The {Xi} part of the process is observed at some location, say A, and is supposed to be reproduced at a different location, say B, where the {Yi} part of the process is observed. Similarly, {Yi} should be reproduced at location A. The communication between the two locations is carried out across two memoryless channels in K iterative bidirectional rounds. In each round, the source components are reconstructed at the other locations based on the information exchanged in all previous rounds and the source component known at that location, and it is desired to find the amount of information that should be exchanged between the two locations in each round, so that the distortions incurred (in each round) would not exceed given thresholds. We first derive a single-letter characterization of achievable rates for a pure source-coding problem with successive refinement. Then, for a joint source-channel coding setting, we prove a separation theorem, asserting that in the limit of long blocks, no optimality is lost by first applying lossy (two-way) successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bitstreams, regardless of the source

We consider the problem of universal delay-limited simulation of an unknown information source of a certain parametric family (e.g., the family of memoryless sources or Markov sources of a given order), given a training sequence from that source and a stream of purely random bits. In the delay-limited setting, the simulation algorithm generates a random sequence sequentially, by delivering one symbol for each training symbol that is made available after a given initial delay, whereas the random bits are assumed to be available on demand. The goal of universal simulation is that the probability law of the generated sequence be identical to that of the training sequence, with minimum mutual information between the random processes generating both sequences. We characterize the optimal delay-limited simulation scheme and upper-bound the expected number of random bits it consumes. As in the non-sequential case, this upper bound is related to the entropy rate of the source

We consider both channel coding and source coding, with perfect past feedback/feedforward, in the presence of side information. It is first observed that feedback does not increase the capacity of the Gelfand-Pinsker channel, nor does feedforward improve the achievable rate-distortion performance in the Wyner-Ziv problem. We then focus on the Gaussian case showing that, as in the absence of side information, feedback/feedforward allows to efficiently attain the respective performance limits. In particular, we derive schemes via variations on that of Schalkwijk and Kailath. These variants, which are as simple as their origin and require no binning, are shown to achieve, respectively, the capacity of Costa's channel, and the Wyner-Ziv rate distortion function. Finally, we consider the finite-alphabet setting and derive schemes for both the channel and the source coding problems that attain the fundamental limits, using variations on schemes of Ahlswede and Ooi and Wornell, and of Martinian and Wornell, respectively

In this paper, we develop a single-letter lower bound on the error exponent for the problem of trellis source coding. We demonstrate that for the case of a binary source with the Hamming distortion measure, and for rates close to the rate-distortion curve, this bound is superior to Marton's block-coding exponent, for the same computational complexity.

We consider the problem of optimum joint information embedding and lossy compression with respect to a fidelity criterion. The goal is to find the minimum achievable compression (composite) rate R/sub c/ as a function of the embedding rate R/sub e/ and the average distortion level /spl Delta/ allowed, such that the average probability of error in decoding of the embedded message can be made arbitrarily small for sufficiently large block length. We characterize the minimum achievable composite rate for both the public and the private versions of the problem and demonstrate how this minimum can be approached in principle. We also provide an alternative single-letter expression of the maximum achievable embedding rate (embedding capacity) as a function of R/sub c/ and /spl Delta/, above which there exist no reliable embedding schemes.

We consider the problem of optimum joint public information embedding and lossy compression with respect to a fidelity criterion. The decompressed composite sequence (stegotext) is distorted by a stationary memoryless attack, resulting in a forgery which in turn is fed into the decoder, whose task is to retrieve the embedded information. The goal of this paper is to characterize the maximum achievable embedding rate R/sub e/ (the embedding capacity C/sub e/) as a function of the compression (composite) rate R/sub c/ and the allowed average distortion level /spl Delta/, such that the average probability of error in decoding of the embedded message can be made arbitrarily small for sufficiently large block length. We characterize the embedding capacity and demonstrate how it can be approached in principle. We also provide a single-letter expression of the minimum achievable composite rate as a function of R/sub e/ and /spl Delta/, below which there exists no reliable embedding scheme.

In a recent paper (Merhav and Weinberger, IEEE Trans. Inf. Theory, vol.50, no.1, p.5-20, 2004) we studied the problem of universal simulation of an unknown information source of a certain parametric family, given a training sequence from that source and given a limited budget of purely random bits. The goal was to generate another random sequence (of the same length or shorter), whose probability law is identical to that of the given training sequence, but with minimum statistical dependency (minimum mutual information) between the input training sequence and the output sequence. In this addendum, we point out a concrete optimal simulation scheme that is easy to implement, as opposed to the nonconstructive existence result in that paper, and we make a number of additional observations on the universal simulation problem.

The problem of fingerprinting in the presence of collusive attacks is considered. It is modeled as a game between a fingerprinter and a decoder on the one hand, and a coalition of two or more attackers on the other. The fingerprinter distributes, to different users, different fingerprinted copies of a host data (covertext ) embedded with different fingerprints. The coalition members create a forgery of the data while aiming at erasing the fingerprints in order not to be detected. Their action is modeled by a multiple-access channel (MAC). The decoder, who has access to the original covertext data, observes the forgery and decodes one of the messages in order to identify one of the members of the coalition. Motivated by a worst case approach, we assume that the coalition of attackers is informed of the hiding strategy taken by the fingerprinter and the decoder, while they are uninformed of the attacking scheme. A single-letter expression for the capacity is derived under the assumption that the host data is drawn from a memoryless stationary source and some mild assumptions on the operation of the encoder. It is shown that for a coalition consisting of L

We study the effect of the introduction of side information into the causal source coding setting of Neuhoff and Gilbert. We find that the spirit of their result, namely, the sufficiency of time-sharing scalar quantizers (followed by appropriate lossless coding) for attaining optimum performance within the family of causal source codes, extends to many scenarios involving availability of side information (at both encoder and decoder, or only on one side). For example, in the case where side information is available at both encoder and decoder, we find that time-sharing side-information-dependent scalar quantizers (at most two for each side-information symbol) attains optimum performance. This remains true even when the reproduction sequence is allowed noncausal dependence on the side information and even for the case where the source and the side information, rather than consisting of independent and identically distributed (i.i.d.) pairs, form, respectively, the output of a memoryless channel and its stationary ergodic input.

In the discrete filtering problem, a data sequence over a finite alphabet is assumed to be corrupted by a discrete memoryless channel. The goal is to reconstruct the clean sequence, with as high a fidelity as possible, by way of causal processing of the noisy sequence alone, with the reconstruction at time t depending only on noisy observations occurring no later than t. A universal version of this problem in which no assumptions are made about the distribution of the clean data, which may even be nonstochastic is studied. Using techniques from universal data compression, in particular, the incremental parsing rule of LZ78, and derives a practical and efficient algorithms for the universal filtering of discrete sources. A finite-memory filter of order k has the property that the reconstruction at any time t is a time-invariant function only of noisy observations occurring between times t-k and t, inclusive. The universal filtering algorithms perform essentially as well, in an expected sense (with respect to the noise process), as the best finite-memory filter of any fixed order, determined with full knowledge of the actual clean data sequence, for all such data sequences. Also consider more general finite-state filters and show that any such filter is arbitrarily well approximated by a finite-memory filter of growing order, thereby establishing the universality of the proposed algorithms with respect to this larger class. This result can be viewed as the filtering analogue of the well known optimality of LZ78 relative to the class of finite-state compressors.

In this paper, the best achievable tradeoffs between /spl Delta/, R/sub e/ and R/sub c/, that maintain reliable estimation of V is characterized. The attack-free version of the public problem of joint information embedding and entropy coding, where the covertext, the watermark and the stegotext are drawn from finite alphabets. It is possible to attribute a different watermark to each codebook, and thus, the watermark can be correctly retrieved according to the codebook to which the composite sequence belongs. The achievable rate region can also be expressed in terms of the maximum achievable embedding capacity. The watermark by the joint typicality property of the decompressed composite sequence with the source sequence and the watermark are evaluated.

The problem of joint compression and information embedding under various causality restrictions on the encoder and decoder is studied in this paper. The minimax game between causal encoder-decoder pairs and causal attackers is characterized by a single-letter formula due to the fact that there is a saddle-point where both parties apply memoryless strategies. Main results are based on semicausal codes where causality is required only with respect to the covertext source. Semicausal embedding is related to communication with causal side information at the transmitter. The results are also extended to the case of attacks, and single-letter formulas are provided for the characterization of the minimax game between the communicators and the attacker.

In this paper, an efficient procedure for designing a sequence of predictors with memory size equal to the Markov order of source, with error exponent arbitrarily close to the optimal error exponent is presented. In this procedure the moment-generating function of the prediction loss is recursively minimized.

In this paper, we present the random coding error exponents of the single-user and the multiple-access Gel'fand-Pinsker channels.

In this paper, We extend the notion of successive refinement (SR) of information to the Wyner-Ziv setting, where the decoders of the different stages have access to (possibly different) side informations, Y and Z, both correlated to the source to be encoded, X. We also give necessary and sufficient conditions for successive refineability

In this paper, we extend the setting of source coding with successive refinement into a joint source-channel coding setting: two descriptions of a memoryless source are to be transmitted across two independent memoryless channels. The output of the channel corresponding to the first (coarse) description is also available to the decoder of the second (refinement) channel. Side information (SI) is available to the decoders. Feedback from the output of the first (coarse) channel to the encoder of the second (refinement) channel is also available

New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.

Chaotic sequences and chaotic dynamical systems are attractive candidates for use in signal synthesis and analysis as well as in communications applications. In previous works, various methods for the estimation of chaotic sequences under noise were developed. However, although the methods were different, their qualitative performance was the same: for high signal-to-noise ratio (SNR) the performance was good, but below some threshold SNR, a sharp degradation in performance occurred. We prove and quantify the existence of this threshold effect and derive lower bounds on the value of the threshold SNR. Using information-theoretic tools, we prove that for any ergodic chaotic system, there is a certain threshold SNR level below which the ratio between the mean-square error obtained by any estimator of the system's initial state at the output of additive white Gaussian noise (AWGN) channel and the Cramer-Rao bound increases exponentially fast as the number of observations N grows without bound. We explain the connection between the existence of a threshold effect in the estimation of chaotic sequences and the converse to the joint source-channel coding theorem. We derive lower bounds on SNR/sub th/, the value of the threshold SNR, as a function of the system's Lyapunov exponent. Our bounds have two versions, one for a finite number of observations, and one for the asymptotic regime as N/spl rarr//spl infin/. For the asymptotic regime, the bound we develop on the threshold SNR incorporates the key parameters of chaotic systems, the Lyapunov exponent, and the chaotic sequence power spectrum into a simple formula. We demonstrate our results on the chaotic system governed by the r-diadic map.

We consider the problem of universal simulation of an unknown source from a certain parametric family of discrete memoryless sources, given a training vector X from that source and given a limited budget of purely random key bits. The goal is to generate a sequence of random vectors {Y/sub i/}, all of the same dimension and the same probability law as the given training vector X, such that a certain, prescribed set of M statistical tests will be satisfied. In particular, for each statistical test, it is required that for a certain event, /spl epsiv//sub /spl lscr//, 1 /spl les/ /spl lscr/ /spl les/ M, the relative frequency /sup 1///sub N/ /spl Sigma//sub i=1//sup N/ 1/sub /spl epsiv//spl lscr//(Y/sub i/) (1/sub /spl epsiv//(/spl middot/) being the indicator function of an event /spl epsiv/), would converge, as N /spl rarr/ /spl infin/, to a random variable (depending on X), that is typically as close as possible to the expectation of 1/sub /spl epsiv//spl lscr/,/ (X) with respect to the true unknown source, namely, to the probability of the event /spl epsiv//sub /spl lscr//. We characterize the minimum key rate needed for this purpose and demonstrate how this minimum can be approached in principle.

We consider the problem of universal simulation of an unknown random process, or information source, of a certain parametric family, given a training sequence from that source and given a limited budget of purely random bits. The goal is to generate another random sequence (of the same length or shorter), whose probability law is identical to that of the given training sequence, but with minimum statistical dependency (minimum mutual information) between the input training sequence and the output sequence. We derive lower bounds on the mutual information that are shown to he achievable by conceptually simple algorithms proposed here. We show that the behavior of the minimum achievable mutual information depends critically on the relative amount of random bits and on the lengths of the input sequence and the output sequence. While in the ordinary (nonuniversal) simulation problem, the number of random bits per symbol must exceed the entropy rate H of the source in order to simulate it faithfully, in the universal simulation problem considered here, faithful preservation of the probability law is not a problem, yet the same minimum rate of H random bits per symbol is still needed to essentially eliminate the statistical dependency between the input sequence and the output sequence. The results are extended to more general information measures.

Watermarking codes are analyzed as a game between two players: an information hider and a decoder, on the one hand, and an attacker on the other hand. It is assumed that the covertext (the original data within which the message is hidden) is drawn from a memoryless stationary source and its realization is available at the information hider only. The information hider is allowed to cause some tolerable level of distortion to the covertext, and the resulting distorted data can suffer some additional amount of distortion caused by an attacker who aims at erasing the message. Motivated by a worst case approach, we assume that the attacker is informed of the hiding strategy taken by the information hider and the decoder, while they are uninformed of the attacking scheme. The capacity is expressed as the limit of a sequence of single-letter expressions under the assumption that the encoder uses constant composition codes.

Achievable rates are characterized for successive refinement (SR) in the Wyner-Ziv scenario, namely, in the presence of correlated side information (SI) at the receivers. In this setting, the encoder is assumed to operate in two stages, where the first corresponds to relatively low rate and high distortion, and the second, comprising a refinement code on top of the first code, is aimed at reproduction at reduced distortion. Both decoders (for low rate/high distortion and for high rate/low distortion) are equipped with SI streams, correlated to the source, but unavailable to the encoder. Furthermore, it is assumed that the decoder that receives the higher rate bitstream, i.e., the additional refinement bits, accesses also SI of "better quality" than that of the lower resolution decoder. By "better quality," we mean that the source and the SI are modeled together as a stochastically degraded joint source, where the encoded symbols, the SI at the refinement stage, and the SI at the initial (coarse) stage, form a Markov chain in this order. For a memoryless joint process (that includes the source to be encoded and its instantaneously correlated SI streams), necessary and sufficient conditions are furnished, in terms of single-letter formulas, for the achievability of a pair of rates, corresponding to two given distortion levels. Special attention is devoted to the degenerate, but important, case where the two SI streams, at the two decoders, are identical. For this case, conditions are provided for successive refinability in the sense of the existence of codes that asymptotically achieve the Wyner-Ziv rate-distortion function, simultaneously at both distortion levels. In this context, the doubly symmetric binary source (with the Hamming distortion measure) and the jointly Gaussian source (with the squared error distortion measure) are successively refinable in the Wyner-Ziv setting. It is demonstrated that a source that is not successively refinable in the ordinary sense (i.e., without SI) may become successively refinable in the presence of SI at the decoders.

We consider the Shannon cipher system with a variable key rate, and study the necessary and sufficient conditions for perfect secrecy in the sense that the exponential rate of the probability of breaking into the system would not be improved by observing the cryptogram. For a memoryless plain text source, we derive achievable lower bounds on the number of key bits needed for almost every plain text sequence in every type class. The corresponding minimum achievable average key rate turns out to be the negative logarithm of the probability of the most likely plain text letter, which is in general, smaller than the entropy.

Fundamental limits on the source coding exponents (or large deviations performance) of zero-delay finite-memory (ZDFM) lossy source codes are studied. Our main results are the following. For any memoryless source, a suitably designed encoder that time-shares (at most two) memoryless scalar quantizers is as good as any time-varying fixed-rate ZDFM code, in that it can achieve the fastest exponential rate of decay for the probability of excess distortion. A dual result is shown to apply to the probability of excess code length, among all fixed-distortion ZDFM codes with variable rate. Finally, it is shown that if the scope is broadened to ZDFM codes with variable rate and variable distortion, then a time-invariant entropy-coded memoryless quantizer (without time sharing) is asymptotically optimal under a "fixed-slope" large-deviations criterion (introduced and motivated here in detail) corresponding to a linear combination of the code length and the distortion. These results also lead to single-letter characterizations for the source coding error exponents of ZDFM codes.

We consider the problem of lossy joint source-channel coding in a communication system where the encoder has access to channel state information (CSI) and the decoder has access to side information that is correlated to the source. This configuration combines the Wyner-Ziv (1976) model of pure lossy source coding with side information at the decoder and the Shannon/Gel'fand-Pinsker (1958, 1980) model of pure channel coding with CSI at the encoder. We prove a separation theorem for this communication system, which asserts that there is no loss in asymptotic optimality in applying, first, an optimal Wyner-Ziv source code and, then, an optimal Gel'fand-Pinsker channel code. We then derive conditions for the optimality of a symbol-by-symbol (scalar) source-channel code, and demonstrate situations where these conditions are met. Finally, we discuss a few practical applications, including overlaid communication where the model under discussion is useful.

The problem of sequentially scanning and predicting data arranged in a multidimensional array is considered. We introduce the notion of a scandictor, which is any scheme for the sequential scanning and prediction of such multidimensional data. The scandictability of any finite (probabilistic) data array is defined as the best achievable expected "scandiction" performance on that array. The scandictability of any (spatially) stationary random field on /spl Zopf//sup m/ is defined as the limit of its scandictability on finite "boxes" (subsets of /spl Zopf//sup m/), as their edges become large. The limit is shown to exist for any stationary field, and essentially be independent of the ratios between the box dimensions. Fundamental limitations on scandiction performance in both the probabilistic and the deterministic settings are characterized for the family of difference loss functions. We find that any stochastic process or random field that can be generated autoregressively with a maximum-entropy innovation process is optimally "scandicted" the way it was generated. These results are specialized for cases of particular interest. The scandictability of any stationary Gaussian field under the squared-error loss function is given a single-letter expression in terms of its spectral measure and is shown to be attained by the raster scan. For a family of binary Markov random fields (MRFs), the scandictability under the Hamming distortion measure is fully characterized.

Watermarking systems are analyzed as a game between an information hider, a decoder, and an attacker. The information hider is allowed to cause some tolerable level of distortion to the original data within which the message is hidden, and the resulting distorted data can suffer some additional amount of distortion caused by an attacker who aims at erasing the message. Two games are investigated: the error exponent game and the coding capacity game. Motivated by a worst case approach, we assume that the attacker is informed of the hiding strategy taken by the information hider and the decoder, which are uninformed of the attacking scheme. This approach leads to the maximin error exponent and maximin coding capacity as objective functions. It is assumed that the host data is drawn from a finite-alphabet memoryless stationary source, and its realization (side information) is available at the encoder and the decoder. A single-letter expression for the maximin error exponent is found under large deviations distortion constraints. Moreover, we find an asymptotically optimal random coding distribution, a universal decoder, and a worst case attack channel. It is proved that there is a saddle point in the asymptotic exponent and that the minimax and the maximin error exponents are equal. Finally, a single letter expression for the coding capacity, i.e., the maximin reliable information rate, is found.

Consider the normalized cumulative loss of a predictor F on the sequence x/sup n/=(x/sub 1/,...,x/sub n/), denoted L/sub F/(x/sup n/). For a set of predictors G, let L(G,x/sup n/)=min/sub F/spl isin/G/L/sub F/(x/sup n/) denote the loss of the best predictor in the class on x/sup n/. Given the stochastic process X=X/sub 1/,X/sub 2/,..., we look at EL(G,X/sup n/), termed the competitive predictability of G on X/sup n/. Our interest is in the optimal predictor set of size M, i.e., the predictor set achieving min/sub |G|/spl les/M/EL(G,X/sup n/). When M is subexponential in n, simple arguments show that min/sub |G|/spl les/M/EL(G,X/sup n/) coincides, for large n, with the Bayesian envelope min/sub F/EL/sub F/(X/sup n/). We investigate the behavior, for large n, of min/sub |G|/spl les/e//sup nR/EL(G,X/sup n/), which we term the competitive predictability of X at rate R. We show that whenever X has an autoregressive representation via a predictor with an associated independent and identically distributed (i.i.d.) innovation process, its competitive predictability is given by the distortion-rate function of that innovation process. Indeed, it will be argued that by viewing G as a rate-distortion codebook and the predictors in it as codewords allowed to base the reconstruction of each symbol on the past unquantized symbols, the result can be considered as the source-coding analog of Shannon's classical result that feedback does not increase the capacity of a memoryless channel. For a general process X, we show that the competitive predictability is lower-bounded by the Shannon lower bound (SLB) on the distortion-rate function of X and upper-bounded by the distortion-rate function of any (not necessarily memoryless) innovation process through which the process X has an autoregressive representation. Thus, the competitive predictability is also precisely characterized whenever X can be autoregressively represented via an innovation process for which the SLB is tight. The error exponent, i.e., the exponential behavior of min/sub |G|/spl les/exp(nR)/Pr(L(G,X/sup n/)>d), is also characterized for processes that can be autoregressively represented with an i.i.d. innovation process.

An overview of statistical and information-theoretic aspects of hidden Markov processes (HMPs) is presented. An HMP is a discrete-time finite-state homogeneous Markov chain observed through a discrete-time memoryless invariant channel. In recent years, the work of Baum and Petrie (1966) on finite-state finite-alphabet HMPs was expanded to HMPs with finite as well as continuous state spaces and a general alphabet. In particular, statistical properties and ergodic theorems for relative entropy densities of HMPs were developed. Consistency and asymptotic normality of the maximum-likelihood (ML) parameter estimator were proved under some mild conditions. Similar results were established for switching autoregressive processes. These processes generalize HMPs. New algorithms were developed for estimating the state, parameter, and order of an HMP, for universal coding and classification of HMPs, and for universal decoding of hidden Markov channels. These and other related topics are reviewed.

A novel approach is presented for the long-standing problem of composite hypothesis testing. In composite hypothesis testing, unlike in simple hypothesis testing, the probability function of the observed data, given the hypothesis, is uncertain as it depends on the unknown value of some parameter. The proposed approach is to minimize the worst case ratio between the probability of error of a decision rule that is independent of the unknown parameters and the minimum probability of error attainable given the parameters. The principal solution to this minimax problem is presented and the resulting decision rule is discussed. Since the exact solution is, in general, hard to find, and a fortiori hard to implement, an approximation method that yields an asymptotically minimax decision rule is proposed. Finally, a variety of potential application areas are provided in signal processing and communications with special emphasis on universal decoding.

The problem of hypothesis testing for parametric information sources whose parameters are not explicitly known is considered. A new, modified version of the Neyman-Pearson criterion of optimality, where the uniform constraint on exponential rate of the false-alarm probability is replaced by one that depends on unknown values of the parameters, is proposed. An optimal universal decision rule, based on Kullback-Leibler divergence, is developed and shown to be efficient in the sense of achieving exponential decay of both misdetection and false-alarm probabilities for all values of unknown parameters, whenever such an efficient decision rule exists at all. Furthermore, necessary and sufficient conditions for the existence of such efficient universal tests are established and the best universally achievable error exponents are presented. Finally, the proposed approach is applied to several important problems in signal processing and communications and compared to the generalized likelihood ratio test (LRT).

The problem of optimal sequential decision for individual sequences, relative to a class of competing off-line reference strategies, is studied for general loss functions with memory. This problem is motivated by applications in which actions may have "long-term" effects, or there is a cost for switching from one action to another. As a first step, we consider the case in which the reference strategies are taken from a finite set of generic "experts." We then focus on finite-state reference strategies, assuming finite action and observation spaces. We show that key properties, that hold for finite-state strategies in the context of memoryless loss functions, do not carry over to the case of loss functions with memory. As a result, an infinite family of randomized finite-state strategies is seen to be the most appropriate reference class for this case, and the problem is basically different from its memoryless counterpart. Based on Vovk's (1990) exponential weighting technique, infinite-horizon on-line decision schemes are devised. For an arbitrary sequence of observations of length n, the excess normalized loss of these schemes relative to the best expert in a corresponding reference class is shown to be upper-bounded by an O(n/sup -1/3/) term in the case of a finite class, or an O([(ln n)/n]/sup 1/3/) term for the class of randomized finite-state strategies. These results parallel the O(n/sup -1/2/) bounds attained by previous schemes for memoryless loss functions. By letting the number of states in the reference class grow, the notion of finite-state predictability is also extended.

Lossy compression of a discrete memoryless source (DMS) with respect to a single-letter distortion measure is considered. We study the best attainable tradeoff between the exponential rates of the probabilities that the codeword length and that the cumulative distortion exceed respective thresholds for two main cases. The first scenario examined is that where the source is corrupted by a discrete memoryless channel (DMC) prior to reaching the coder. In the second part of this work, we examine the universal setting, where the (noise-free) source is an unknown member P/sub /spl theta// of a given family {P/sub /spl theta//,/spl theta//spl isin//spl Theta/}. Here, inspired by an approach which was proven fruitful previously in the context of composite hypothesis testing, we allow the constraint on the excess-code-length exponent to be /spl theta/-dependent. Corollaries are derived for some special cases of interest, including Marton's (1974) classical source coding exponent and its generalization to the case where the constraint on the rate of the code is relaxed from an almost sure constraint to a constraint on the excess-code-length exponent.

We continue the study of adaptive schemes for the sequential lossy coding of individual sequences which was initiated by Linder and Lugosi (see ibid., p.2533-38, 2001). Specifically, we consider fixed-rate lossy coding systems of fixed (or zero) delay where the encoder (which is allowed to use randomization) and the decoder are connected via a noiseless channel of a given capacity. It is shown that for any finite set of such coding schemes of a given rate, there exists a source code (adhering to the same structural and delay limitations) with the same rate whose distortion is with high probability almost as small as that of the best scheme in that set, uniformly for all individual sequences. Applications of this result to reference classes of special interest are outlined. These include the class of scalar quantizers, trellis encoders with sliding block decoders, and differential pulse code modulator (DPCM)-based source codes. In particular, for the class of all scalar quantizers, a source code is obtained with (normalized) distortion redundancy relative to the best scheme in the reference class of order n/sup -1/3/ log n (where n is the sequence length). This improves the n/sup -1/5/ log n rate achieved by Linder and Lugosi. More importantly, the decoder here is deterministic and, in particular, does not assume a common randomization sequence available at both encoder and decoder. Finally, we consider the case where the individual sequence is corrupted by noise prior to reaching the coding system, whose goal now is to reconstruct a sequence with small distortion relative to the clean individual sequence. It is shown that for the case of a finite alphabet and an invertible channel transition probability matrix, for any finite set of sliding-window schemes of a given rate, there exists a source code (allowed to use randomization yet adhering to the same delay constraints) whose performance is, with high probability, essentially as good as the best scheme in the class, for all individual sequences.

Watermarking codes are analyzed from an information-theoretic viewpoint as identification codes with side information that is available at the transmitter only or at both ends. While the information hider embeds a secret message (watermark) in a covertext message (typically, text, image, sound, or video stream) within a certain distortion level, the attacker, modeled here as a memoryless channel, processes the resulting watermarked message (within limited additional distortion) in attempt to invalidate the watermark. In most applications of watermarking codes, the decoder need not carry out full decoding, as in ordinary coded communication systems, but only to test whether a watermark at all exists and if so, whether it matches a particular hypothesized pattern. This fact motivates us to view the watermarking problem as an identification problem, where the original covertext source serves as side information. In most applications, this side information is available to the encoder only, but sometimes it can be available to the decoder as well. For the case where the side information is available at both encoder and decoder, we derive a formula for the identification capacity and also provide a characterization of achievable error exponents. For the case where side information is available at the encoder only, we derive upper and lower bounds on the identification capacity. All characterizations are obtained as single-letter expressions.

The problem of predicting the next outcome of an individual binary sequence, based on noisy observations of the past, is considered. The goal of the predictor is to perform, for each individual sequence, "almost" as well as the best in a set of experts, where performance is evaluated using a general loss function. A comprehensive approach to prediction in this noisy setting is presented and proven generally efficient under appropriate conditions. As an illustration of the applicability of the approach suggested for concrete situations, two important special cases are explicitly treated. The first is the case where the data-corrupting noise process is binary-valued (where the observed bit is the bitwise XOR of the clean bit and the noise bit). The second case is that of real-valued additive noise. It is shown that even in this more challenging situation, where the information available to the predictor regarding the past sequence is incomplete, a predictor can be guaranteed to successfully compete with a whole set of experts in considerably strong senses.

The problem of predicting the next outcome of an individual binary sequence corrupted by noise using finite memory, is considered. The conditional finite-state (FS) predictability of an infinite individual sequence given its noisy version is defined as the minimum fraction of errors that can be made by any FS predictor fed by the noisy version. It is proved that the conditional FS predictability can be attained almost surely by universal sequential prediction schemes in the case where the noisy version is the output of a binary-symmetric channel (BSC) whose input is the clean individual sequence. In particular, universal predictors of the original noise-free setting, which operate on the noisy sequence, have this property. Moreover, these universal predictors do not depend on the crossover probability characterizing the BSC. It is seen that the noisy setting gives rise to additional criteria by which the performance of prediction schemes can be assessed. Finally, a closer look is taken at the conditional FS predictability, and this quantity is proposed as an additional measure of the complexity of a sequence, perhaps finer and more informative than the predictive complexity of the noise-free setting.

Watermarking codes are analyzed from an information-theoretic viewpoint as a game between an information hider and an active attacker. While the information hider embeds a secret message (watermark) in a covertext message (typically: text, image, sound, or video stream) within a certain distortion level, the attacker processes the resulting watermarked message, within limited additional distortion, in attempt to invalidate the watermark. For the case where the covertext source is memoryless (or, more generally where there exists some transformation that makes it memoryless), we provide a single-letter characterization of the maximin game of the random coding error exponent associated with the average probability of erroneously decoding the watermark. This single-letter characterization is in effect because if the information hider utilizes a memoryless channel to generate random codewords for every covertext message, the (causal) attacker will maximize the damage by implementing a memoryless channel as well. Partial results for the dual minimax game and the conditions for the existence of a saddle point are also presented.

We propose a universal, asymptotically optimum decision rule for deciding whether or not an observed sequence generated at the output of an unknown finite-state channel corresponds to a given channel-input message. The hypothesized message is tested against a certain alternative message or several alternative messages under the Neyman-Pearson criterion.

A complete characterization of optimal prefix codes for off-centered, two-sided geometric distributions of the integers is presented. These distributions are often encountered in lossless image compression applications, as probabilistic models for image prediction residuals. The family of optimal codes described is an extension of the Golomb codes, which are optimal for one-sided geometric distributions. The new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the heuristic approximations frequently used when modifying a code designed for nonnegative integers so as to apply to the encoding of any integer. Optimal decision rules for choosing among a lower complexity subset of the optimal codes, given the distribution parameters, are also investigated, and the relative redundancy of the subset with respect to the full family of optimal codes is bounded.

Lossless compression is studied for a countably infinite alphabet source with an unknown, off-centered, two-sided geometric (TSG) distribution, which is a commonly used statistical model for image prediction residuals. We demonstrate that arithmetic coding based on a simple strategy of model adaptation, essentially attains the theoretical lower bound to the universal coding redundancy associated with this model. We then focus on more practical codes for the TSG model, that operate on a symbol-by-symbol basis, and study the problem of adaptively selecting a code from a given discrete family. By taking advantage of the structure of the optimum Huffman tree for a known TSG distribution, which enables simple calculation of the codeword of every given source symbol, an efficient adaptive strategy is derived.

The problem of predicting the next outcome of an individual binary sequence, based on noisy observations of the past is considered.The goal of the predictor is to perform, for each individual clean sequence (almost) as well as the best "expert" in a finite set, where performance is evaluated using a general loss function.This setup is a generalization of that considered extensively by researchers from various disciplines of universal prediction and forecasting for the case where the observation of the past data is corrupted by noise.In this work, we restrict ourselves to the case where the noise is an additive, i.i.d Bernoulli(p) process and where its parameter p is assumed known to the predictor.In the expected loss regime, for a given sequence, we define the regret as the difference between the total expected loss of the predictor on the entire sequence and that of the best expert in the comparison class.We generalize and improve the recent order results of Haussler et al. [7] to this noisy setup for a large class of loss functions and show that under certain conditions on the loss functions, the minimax regret is 0(log N) while under other conditions it is e(Jw), where n is the sequence length and N is the cardinality of the expert class.It is also seen that this new setup, which involves a stochastic noise process, gives rise to additional performance 'This work is part of an M.Sc.

A fast multiplication-free algorithm for the inverse discrete cosine transform (IDCT) is developed. This algorithm is an approximation to the IDCT and is applicable in implementations of compression standards such as JPEG, MPEG-1, MPEG-2 H.263. The proposed algorithm is 32% faster than its exact counterpart. For low bit-rate video codecs, the quantization effects introduced by the multiplier-free approach is considerably lower than the distortion introduced by the quantizer settings of the video codec and thus the overall PSNR loss is well within 1 dB for the proposed multiplier-free approach. If DCT data sparseness is taken into account, compared with other recently developed fast approximate DCT and IDCT methods, the proposed scheme provides significant reductions in computation complexity. The approach described here can be easily adapted for the forward DCT.

A method for efficient spatial domain filtering, directly in the discrete cosine transform (DCT) domain, is developed and proposed. It consists of using the discrete sine transform (DST) and the DCT for transform-domain processing on the in JPEG basis of the previously derived convolution-multiplication properties of discrete trigonometric transforms. The proposed scheme requires neither zero padding of the input data nor kernel symmetry. It is demonstrated that, in typical applications, the proposed algorithm is significantly more efficient than the conventional filtered spatial domain and earlier proposed DCT domain methods. The proposed method is applicable to any DCT-based image compression standard, such as JPEG, MPEG, and H.261.

We propose a method for devising approximate multiplication-free algorithms for compressed-domain linear operations on images, e.g., downsampling, translation, filtering, etc. We demonstrate that the approximate algorithms give output images that are perceptually nearly equivalent to those of the exact processing, while the computational complexity is significantly reduced.

The Shannon theory of cipher systems is combined with recent work on guessing values of random variables. The security of encryption systems is measured in terms of moments of the number of guesses needed for the wiretapper to uncover the plaintext given the cryptogram. While the encrypter aims at maximizing the guessing effort, the wiretapper strives to minimize it, e.g., by ordering guesses according to descending order of posterior probabilities of plaintexts given the cryptogram. For a memoryless plaintext source and a given key rate, a single-letter characterization is given for the highest achievable guessing exponent function, that is, the exponential rate of the pth moment of the number of guesses as a function of the plaintext message length. Moreover, we demonstrate asymptotically optimal strategies for both encryption and guessing, which are universal in the sense of being independent of the statistics of the source. The guessing exponent is then investigated as a function of the key rate and related to the large-deviations guessing performance.

Arikan and Merhav (1998) studied the problem of guessing a random vector X within distortion D, and characterized the best attainable exponent E(D,/spl rho/) of the /spl rho/th moment of the number of required guesses G(X) until the guessing error falls below D. We extend these results to a multistage, hierarchical guessing model, which allows for a faster search for a codeword vector at the encoder of a rate-distortion codebook. In the two-stage case of this model, if the target distortion level is D/sub 2/, the guesser first makes guesses with respect to (a higher) distortion level D/sub 1/, and then, upon his/her first success, directs the subsequent guesses to distortion D/sub 2/. As in the above-mentioned earlier paper, we provide a single-letter characterization of the best attainable guessing exponent, which relies heavily on well-known results on the successive refinement problem. We also relate this guessing exponent function to the source-coding error exponent function of the two-step coding process.

Three strongly sequential, lossless compression schemes, one with linearly growing per-letter computational complexity, and two with fixed per-letter complexity, are presented and analyzed for memoryless sources with abruptly changing statistics. The first method, which improves on Willems' (1994) weighting approach, asymptotically achieves a lower bound on the redundancy, and hence is optimal. The second scheme achieves redundancy of O(log N/N) when the transitions in the statistics are large, and O (log log N/log N) otherwise. The third approach always achieves redundancy of O (/spl radic/log N/N). Obviously, the two fixed complexity approaches can be easily combined to achieve the better redundancy between the two. Simulation results support the analytical bounds derived for all the coding schemes.

Several compressed-domain based processing methods such as video downscaling, filtering, inverse motion compensation, etc. have been developed for MPEG compressed digital video. These processing methods assume that the underlying MPEG video was coded in only one mode, namely, frame or field mode. In order to support both frame and field-mode coded video, in this paper, we present a fast algorithm for converting a sequence of DCT blocks in the field mode to a sequence of blocks whose DCT's represent frame-mode coding. A multiplier-free implementation for this algorithm is also developed in this paper. In a typical coding setup, used in MPEG-2, simulations indicate that the image quality degradations resulting from the multiplier-free implementation is around 0.5-1.0 dB; however, a factor of two speedup is obtained compared with a traditional spatial-domain approach.

We develop a method for designing discrete cosine transform (DCT) coefficient multipliers in order to approximate the operation of two-dimensional (2-D) convolution of an image with a given kernel. The method is easy to implement on compressed formats of DCT-based compression methods (JPEG, MPEG, H.261) by using decoding quantization tables that are different from the encoding quantization tables.

We investigate the problem of guessing a random vector X within distortion level D. Our aim is to characterize the best attainable performance in the sense of minimizing, in some probabilistic sense, the number of required guesses G(X) until the error falls below D. The underlying motivation is that G(X) is the number of candidate codewords to be examined by a rate-distortion block encoder until a satisfactory codeword is found. In particular, for memoryless sources, we provide a single-letter characterization of the least achievable exponential growth rate of the /spl rho/th moment of G(X) as the dimension of the random vector X grows without bound. In this context, we propose an asymptotically optimal guessing scheme that is universal both with respect to the information source and the value of /spl rho/. We then study some properties of the exponent function E(D, /spl rho/) along with its relation to the source-coding exponents. Finally, we provide extensions of our main results to the Gaussian case, guessing with side information, and sources with memory.

We extend our earlier work on guessing subject to distortion to the joint source-channel coding context. We consider a system in which there is a source connected to a destination via a channel and the goal is to reconstruct the source output at the destination within a prescribed distortion level with respect to (w.r.t.) some distortion measure. The decoder is a guessing decoder in the sense that it is allowed to generate successive estimates of the source output until the distortion criterion is met. The problem is to design the encoder and the decoder so as to minimize the average number of estimates until successful reconstruction. We derive estimates on nonnegative moments of the number of guesses, which are asymptotically tight as the length of the source block goes to infinity. Using the close relationship between guessing and sequential decoding, we give a tight lower bound to the complexity of sequential decoding in joint source-channel coding systems, complementing earlier works by Koshelev (1973) and Hellman (1975). Another topic explored here is the probability of error for list decoders with exponential list sizes for joint source-channel coding systems, for which we obtain tight bounds as well. It is noteworthy that optimal performance w.r.t. the performance measures considered here can be achieved in a manner that separates source coding and channel coding.

This paper consists of an overview on universal prediction from an information-theoretic perspective. Special attention is given to the notion of probability assignment under the self-information loss function, which is directly related to the theory of universal data compression. Both the probabilistic setting and the deterministic setting of the universal prediction problem are described with emphasis on the analogy and the differences between results in the two settings.

Straightforward techniques for spatial domain processing of compressed video via decompression and recompression are computationally expensive. We describe an alternative approach wherein the compressed stream is processed in the compressed, discrete cosine transform (DCT) domain without explicit decompression and spatial domain processing, so that the output compressed stream, corresponding to the output image, conforms to the standard syntax of 8/spl times/8 blocks. We propose computation schemes for downsampling and for inverse motion compensation that are applicable to any DCT-based compression method. Worst case estimates of computation savings vary between 37% and 50% depending on the task. For typically sparse DCT blocks, the reduction in computations is more dramatic. A by-product of the proposed approach is improvement in arithmetic precision.

We characterize and investigate the highest achievable exponential growth rate of the expected number of rate-distortion codewords that are within a certain distance from a given source vector.

We investigate the minimum amount of side information about the channel statistics that must be provided to the decoder in order to guarantee reliable communication in the random coding sense, for certain classes of channels.

Consider a vector quantizer that is equipped with N side information bits of an arbitrary representation of the statistics of the input source. We investigate the minimum value of N such that rate-distortion performance of this quantizer would be essentially the same as the optimum quantizer for the given source.

One of the important tasks of a multiuser video network server is to composite compressed video streams from several sources into a single compressed video stream. A great deal of the computational load can be saved if this composition is performed directly in the compressed domain rather than using the brute-force approach of converting back to the uncompressed domain, compositing pixel-by-pixel in the spatial domain, and re-compressing the composite stream. We propose a fast algorithm that converts motion compensated compressed video into a sequence of DCT-domain blocks corresponding to the spatial domain blocks of the current frame alone, without prediction based on other frames, i.e., removing the inter-frame element of the compression-decompression. This step enables video compositing in the DCT compressed domain as well as several compositing operations, e.g., scaling, overlapping, translation, filtering, etc. The proposed algorithm saves about 47% of the computations compared to the brute-force approach even without assuming sparseness of the DCT blocks. For typical sparse DCT blocks, where only the top-left 4/spl times/4 quadrant is nonzero, the reduction in computational complexity is about 68%.

Straightforward techniques for spatial domain scaling of compressed video via decompression and re-compression are computationally expensive. We describe an alternative approach wherein the compressed stream is processed in the compressed, DCT domain without explicit decompression and spatial domain scaling, so that the output compressed stream corresponds to a down-sampled image and it conforms the standard syntax of 8/spl times/8 blocks. We propose computation schemes for scaling factors of 2, 3 and 4 that are applicable to any DCT-based compression method. Worst-case estimates of computation savings very between 37% and 50% depending on the scaling factor. For typically sparse DCT blocks, the reduction in computations can be as much as 80%. A byproduct of the proposed approach is improvement in arithmetic precision.

This paper elaborates on the use of discrete, two-sided geometric distribution models for image prediction residuals. After providing achievable bounds for universal coding of a rich family of models, which includes traditional image models, we present a new family of practical prefix codes for adaptive image compression. This family is optimal for two-sided geometric distributions and is an extension of the Golomb (1966) codes. Our new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the rough approximations used when a code designed for non-negative integers is matched to the encoding of any integer. We also provide adaptation criteria for a further simplified, sub-optimal family of codes used in practice.

In an earlier paper, we proved a strong version of the redundancy-capacity converse theorem of universal coding, stating that for "most" sources in a given class, the universal coding redundancy is essentially lower-bounded by the capacity of the channel induced by this class. Since this result holds for general classes of sources, it extends Rissanen's (1986) strong converse theorem for parametric families. While our earlier result has established strong optimality only for mixture codes weighted by the capacity-achieving prior, our first result herein extends this finding to a general prior. For some cases our technique also leads to a simplified proof of the above mentioned strong converse theorem. The major interest in this paper, however, is in extending the theory of universal coding to hierarchical structures of classes, where each class may have a different capacity. In this setting, one wishes to incur redundancy essentially as small as that corresponding to the active class, and not the union of classes. Our main result is that the redundancy of a code based on a two-stage mixture (first, within each class, and then over the classes), is no worse than that of any other code for "most" sources of "most" classes. If, in addition, the classes can be efficiently distinguished by a certain decision rule, then the best attainable redundancy is given explicitly by the capacity of the active class plus the normalized negative logarithm of the prior probability assigned to this class. These results suggest some interesting guidelines as for the choice of the prior. We also discuss some examples with a natural hierarchical partition into classes.

The use of information theory concepts for universal estimation of delay for classes of discrete channels is discussed. The problem is presented as one of hypothesis testing. Although the channel statistics are not known, for large enough signal duration, the exponent of the average error probability is equal to that associated with the optimal maximum-likelihood (ML) decision procedure which utilizes full knowledge of the channel parameters. Two categories of problems are discussed: the single-channel problem, where the random transmitted signal is known to the receiver, and the two-sensor problem, where the random signal is unknown.

The minimum redundancy attainable by universal lossless codes for finite-state arbitrarily varying sources (AVS), and, in general, for an hierarchy of model classes, is investigated. In the AVS case, if the space of all possible underlying state sequences is partitioned into types, then the minimum universal coding redundancy can be essentially lower bounded by a quantity that decomposes into two terms, the first of which is the minimum redundancy within the type class (i.e., intra-type class redundancy), and the second is the minimum redundancy associated with a class of sources that can be thought of as "representatives" of the different types (i.e., inter-type class redundancy). This behavior can be generalized to universal coding for hierarchy of model classes, where each model class in the hierarchy has an increasing complexity. The lower bound for coding with respect to hierarchy of models is achievable by a Shannon code w.r.t an appropriate two-stage mixture, where the first stage mixture is over the sources in each class, and the second is a mixture over the indices of the model classes.

In the above paper (see ibid., vol.39, no.3, p.813-20, 1993) Yu and Speed propose a universal pointwise D-semifaithful code whose expected compression ratio, for discrete memoryless sources, approaches the rate-distortion function at a rate O(n/sup -1/ log n). They also conjecture that this is the fastest achievable convergence rate for pointwise D-semifaithful codes. In this correspondence, we use a simple extension of Kraft's inequality and prove that this conjecture is true, at least for the Hamming distortion measure.>

The capacity of the channel induced by a given class of sources is well known to be an attainable lower bound on the redundancy of universal codes with respect to this class, both in the minimax sense and in the Bayesian (maximin) sense. We show that this capacity is essentially a lower bound also in a stronger sense, that is, for "most" sources in the class. This result extends Rissanen's (1984, 1986) lower bound for parametric families. We demonstrate the applicability of this result in several examples, e.g., parametric families with growing dimensionality, piecewise-fixed sources, arbitrarily varying sources, and noisy samples of learnable functions. Finally, we discuss implications of our results to statistical inference.>

The capacity of the channel induced by a given class of sources is well known to be an attainable lower bound on the redundancy of universal codes w.r.t this class, both in the minimax sense and in the Bayesian (maximin) sense. The authors main contribution is a relatively simple proof that the capacity is essentially a lower bound also in a stronger sense, that is, for "most" sources in the class. This result extends Rissanen's (1984) lower bound for parametric families. Finally, the authors demonstrate the applicability of this result in several examples.>

Robust statistical procedures are studied and applied to speech recognition. The goal is to improve recognition under general nonparametric mismatch situations between training and testing conditions. Towards this end, we develop an M-hypotheses decision rule for a statistical model related to hidden Markov model. The decision rule employs two hypotheses robust likelihood ratio tests between all pairs of the M hypotheses, and is shown to be asymptotically optimal for the worst case mismatch condition. The proposed approach is experimentally evaluated and compared to a known parametric approach where the mismatch is modeled parametrically, and to the standard MAP approach, where no mismatch is assumed.

The relation between the entropy of a discrete random variable and the minimum attainable probability of error made in guessing its value is examined. While Fano's inequality provides a tight lower bound on the error probability in terms of the entropy, the present authors derive a converse result/spl mdash/a tight upper bound on the minimal error probability in terms of the entropy. Both bounds are sharp, and can draw a relation, as well, between the error probability for the maximum a posteriori (MAP) rule, and the conditional entropy (equivocation), which is a useful uncertainty measure in several applications. Combining this relation and the classical channel coding theorem, the authors present a channel coding theorem for the equivocation which, unlike the channel coding theorem for error probability, is meaningful at all rates. This theorem is proved directly for DMCs, and from this proof it is further concluded that for R/spl ges/C the equivocation achieves its minimal value of R/spl minus/C at the rate of n/sup 1/spl sol/2/ where n is the block length.>

Lower bounds on achievable convergence rates of parameter estimators towards the true parameter are derived via universal coding considerations. It is shown that for a parametric class of finite-alphabet information sources, if there exists a universal lossless code whose redundancy decays sufficiently rapidly, then it induces a limitation on the fastest achievable convergence rate of any parameter estimator, at any value of the true parameter, with a possible exception of a vanishingly small subset of parameter values. A specific choice of a universal code yields a slightly different version of this result which extends easily to the continuous case.>

Reliable transmission over a discrete-time memoryless channel with a decoding metric that is not necessarily matched to the channel (mismatched decoding) is considered. It is assumed that the encoder knows both the true channel and the decoding metric. The lower bound on the highest achievable rate found by Csiszar and Korner (1981) and by Hui (1983) for DMC's, hereafter denoted C/sub LM/, is shown to bear some interesting information-theoretic meanings. The bound C/sub LM/ turns out to be the highest achievable rate in the random coding sense, namely, the random coding capacity for mismatched decoding. It is also demonstrated that the /spl epsiv/-capacity associated with mismatched decoding cannot exceed C/sub LM/. New bounds and some properties of C/sub LM/ are established and used to find relations to the generalized mutual information and to the generalized cutoff rate. The expression for C/sub LM/ is extended to a certain class of memoryless channels with continuous input and output alphabets, and is used to calculate C/sub LM/ explicitly for several examples of theoretical and practical interest. Finally, it is demonstrated that in contrast to the classical matched decoding case, here, under the mismatched decoding regime, the highest achievable rate depends on whether the performance criterion is the bit error rate or the message error probability and whether the coding strategy is deterministic or randomized.>

The problem of sequential probability assignment for individual sequences is investigated. The authors compare the probabilities assigned by any sequential scheme to the performance of the best "batch" scheme (model) in some class. For the class of finite-state schemes and other related families, they derive a deterministic performance bound, analogous to the classical (probabilistic) minimum description length (MDL) bound. It holds for "most" sequences, similarly to the probabilistic setting, where the bound holds for "most" sources in a class. It is shown that the bound can be attained both pointwise and sequentially for any model family in the reference class and without any prior knowledge of its order. This is achieved by a universal scheme based on a mixing approach. The bound and its sequential achievability establish a completely deterministic significance to the concept of predictive MDL.>

A minimax approach for robust classification of parametric information sources is studied and applied to isolated-word speech recognition based on hidden Markov modeling. The goal is to reduce the sensitivity of speech recognition systems to a possible mismatch between the training and testing conditions. To this end, a generalized likelihood ratio test is developed and shown to be optimal in the sense of achieving the highest asymptotic exponential rate of decay of the error probability for the worst-case mismatch situation. The proposed approach is compared to the standard approach, where no mismatch is assumed, in recognition of noisy speech and in other realistic mismatch situations.>

A universal decoding procedure is proposed for memoryless Gaussian channels with deterministic interfering signals from a certain class. The proposed decoder is universal in the sense that it is independent of the channel parameters and the unknown interfering signal, and, at the same time, attains the same random coding error exponent as the optimal maximum likelihood (ML) decoder, which utilizes full knowledge of the channel parameters and the interfering signal. The proposed decoding rule can be regarded as a continuous-alphabet version of the universal maximum mutual information decoder.>

Universal lossless coding in the presence of finitely many abrupt changes in the statistics of the source, at unknown points, is investigated. The minimum description length (MDL) principle is derived for this setting. In particular, it is shown that, for any uniquely decipherable code, for almost every combination of statistical parameter vectors governing each segment, and for almost every vector of transition instants, the minimum achievable redundancy is composed from 0.5 log n/n bits for each unknown segmental parameter and log n/n bits for each transition, where n is the length of the input string. This redundancy is shown to be attainable by a strongly sequential universal encoder, i.e., an encoder that does not utilize the knowledge of a prescribed value of n.>

Sequential decision algorithms are investigated in relation to a family of additive performance criteria for individual data sequences. Simple universal sequential schemes are known, under certain conditions, to approach optimality uniformly as fast as n/sup -1/ log n, where n is the sample size. For the case of finite-alphabet observations, the class of schemes that can be implemented by finite-state machines (FSMs) is studied. It is shown that Markovian machines with sufficiently long memory exist, which are asymptotically nearly as good as any given deterministic or randomized FSM for the purpose of sequential decision. For the continuous-valued observation case, a useful class of parametric schemes is discussed with special attention to the recursive least squares algorithm.>

Universal predictions of the next outcome of a binary sequence drawn from a Markov source with unknown parameters is considered. For a given source, the predictability is defined as the least attainable expected fraction of prediction errors. A lower bound is derived on the maximum rate at which the predictability is asymptotically approached uniformly over all sources in the Markov class. This bound is achieved by a simple majority predictor. For Bernoulli sources, bounds on the large deviations performance are investigated. A lower bound is derived for the probability that the fraction of errors will exceed the predictability by a prescribed amount Delta >0. This bound is achieved by the same predictor if Delta is sufficiently small.>

A new notion of empirical informational divergence (relative entropy) between two individual sequences is introduced. If the two sequences are independent realizations of two finite-order, finite alphabet, stationary Markov processes, the empirical relative entropy converges to the relative entropy almost surely. This empirical divergence is based on a version of the Lempel-Ziv data compression algorithm. A simple universal algorithm for classifying individual sequences into a finite number of classes, which is based on the empirical divergence, is introduced. The algorithm discriminates between the classes whenever they are distinguishable by some finite-memory classifier for almost every given training set and almost any test sequence from these classes. It is universal in the sense that it is independent of the unknown sources.>

Sequential learning and decision algorithms are investigated, with various application areas, under a family of additive loss functions for individual data sequences. Simple universal sequential schemes are known, under certain conditions, to approach optimality uniformly as fast as n-1logn, where n is the sample size. For the case of finite-alphabet observations, the class of schemes that can be implemented by finite-state machines (FSM's), is studied. It is shown that Markovian machines with sufficiently long memory exist that are asymptotically nearly as good as any given FSM (deterministic or randomized) for the purpose of sequential decision. For the continuous-valued observation case, a useful class of parametric schemes is discussed with special attention to the recursive least squares (RLS) algorithm.

The performance of a minimum mean-square error (MMSE) estimator for the output signal from a composite source model (CSM), which has been degraded by statistically independent additive noise, is analyzed for a wide class of discrete-time and continuous-time models. In both cases, the MMSE is decomposed into the MMSE of the estimator, which is informed of the exact states of the signal and noise, and an additional error term. This term is tightly upper and lower bounded. The bounds for the discrete-time signals are developed using distribution tilting and Shannon's lower bound on the probability of a random variable exceeding a given threshold. The analysis for the continuous-time signal is performed using Duncan's theorem. The bounds in this case are developed by applying the data processing theorem to sampled versions of the state process and its estimate, and by using Fano's inequality. The bounds in both cases are explicitly calculated for CSMs with Gaussian subsources. For causal estimation, these bounds approach zero harmonically as the duration of the observed signals approaches infinity.>

The problem of predicting the next outcome of an individual binary sequence using finite memory is considered. The finite-state predictability of an infinite sequence is defined as the minimum fraction of prediction errors that can be made by any finite-state (FS) predictor. It is proven that this FS predictability can be achieved by universal sequential prediction schemes. An efficient prediction procedure based on the incremental parsing procedure of the Lempel-Ziv data compression algorithm is shown to achieve asymptotically the FS predictability. Some relations between compressibility and predictability are discussed, and the predictability is proposed as an additional measure of the complexity of a sequence.>

It is proved that for finite-alphabet, finite-state unifilar sources, variable-to-fixed length codes provide better large deviations performance of the empirical compression ratio, than fixed-to-variable length codes. It is shown how to construct a universal variable-to-fixed length code that achieves the optimal performance.>

The generalized likelihood ratio test (GLRT), which is commonly used in composite hypothesis testing problems, is investigated. Conditions for asymptotic optimality of the GLRT in the Neyman-Pearson sense are studied and discussed. First, a general necessary and sufficient condition is established, and then based on this, a sufficient condition, which is easier to verify, is derived. A counterexample where the GLRT is not optimal, is provided as well. A conjecture is stated concerning the optimality of the GLRT for the class of finite-state sources.>

The problem of estimating the number of states of a finite-alphabet, finite-state source is investigated. An estimator is developed that asymptotically attains the minimum probability of understanding the number of states, among all estimators with a prescribed exponential decay rate of overestimation probability. The proposed estimator relies on the Lempel-Ziv data compression algorithm in an intuitively appealing manner.>

Approximate maximum likelihood (ML) hidden Markov modeling using the most likely state sequence (MLSS) is examined and compared with the exact ML approach that considers all possible state sequences. It is shown that, for any hidden Markov model (HMM), the difference between the approximate and the exact normalized likelihood functions cannot exceed the logarithm of the number of states divided by the dimension of the output vectors (frame length). Furthermore, for Gaussian HMMs and a given observation sequence, the MLSS is typically the sequence of nearest-neighbor states in the Itakura-Saito sense, and the posterior probability of any state sequence which departs from the MLSS in a single time instant decays exponentially with the frame length. Hence, for a sufficiently large frame length the exact and approximate ML approaches provide similar model estimates and likelihood values.>

A Bayesian approach to classification of parametric information sources whose statistics are not explicitly given is studied and applied to recognition of speech signals based upon hidden Markov modeling. A classifier based on generalized likelihood ratios, which depends only on the available training and testing data, is developed and shown to be optimal in the sense of achieving the highest asymptotic exponential rate of decay of the error probability. The proposed approach is compared to the standard classification approach used in speech recognition, in which the parameters for the sources are first estimated from the given training data, and then the maximum and posteriori (MAP) decision rule is applied using the estimated statistics.>

Lossless block-to-variable length source coding is studied for finite-state, finite-alphabet sources. The aim is to minimize the probability that the normalized length of the codeword will exceed a given threshold B, subject to the Kraft inequality. It is shown that the Lempel-Ziv algorithm (1978) asymptotically attains the optimal performance in the sense just defined, independently of the source and the value of B. For the subclass of unifilar Markov sources, faster convergence to the asymptotic optimum performance can be accomplished by using the minimum-description-length universal code for this subclass. It is demonstrated that these universal codes are also nearly optimal in the sense of minimizing buffer overflow probability, and asymptotically optimal in a competitive sense.>

Binary hypotheses testing using empirically observed statistics is studied in the Neyman-Pearson formulation for the hidden Markov model (HMM). An asymptotically optimal decision rule is proposed and compared to the generalized likelihood ratio test (GLRT), which has been shown in earlier studies to be asymptotically optimal for simpler parametric families. The proof of the main theorem is provided. The result can be applied to several types of HMMs commonly used in speech recognition and communication applications. Several applications are demonstrated.>

A Bayesian approach for classification of Markov sources whose parameters are not explicitly known is developed and studied. A universal classifier is derived and shown to achieve, within a constant factor, the minimum error probability in a Bayesian sense. The proposed classifier is based on sequential estimation of the parameters of the sources, and it is closely related to earlier proposed universal tests under the Neyman-Pearson criterion.>

A universal nearly efficient estimator is proposed for the first-order autoregressive (AR) model where the probability distribution of the driving noise is unknown. It is shown that universal estimators for the AR model can be derived from universal data compression algorithms and universal tests for randomness. In other words, estimators derived appropriately from efficient universal codes can be expected to inherit good estimation performance under some conditions. The proposed estimator has a simple information-theoretic interpretation related to universal coding, which can be easily generalized to the higher-order case and to other parametric models, e.g. the one-sample location model, the two-sample location model, and the linear regression model.>

Estimators are sought that achieve high exponential rate of decrease in the underestimation probability while keeping the overestimation probability exponent at a certain prescribed level. It is assumed that a given integer is known to upper-bound the true order. Some examples are given of possible applications of the proposed method in specific order estimation and hypothesis testing problems.>

The authors estimate the order of a finite Markov source based on empirically observed statistics. The performance criterion adopted is to minimize the probability of underestimating the model order while keeping the overestimation probability exponent at a prescribed level. A universal asymptotically optimal test, in the sense just defined, is proposed for the case where a given integer is known to be the upper bound of the true order. For the case where such a bound is unavailable, an alternative rule based on the Lempel-Ziv data compression algorithm is shown to be asymptotically optimal also and computationally more efficient.>

Parameter estimation based on data emitted from a finite ergodic Markov source is discussed. This can be considered an extension of the memoryless case. First, an asymptotically optimal estimator is suggested for the case where the parametric model is completely known. For an unknown parametric model (e.g unknown noise distribution with training sequences available) a necessary condition is given for the existence of a universally optimum estimate. A universal estimate is then suggested that is asymptotically nearly optimal. The results hold under fairly mild regularity conditions.>