Search

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 of outage – the event in which the capacity of the channel induced by the DNA molecule sampling operation does not support the target rate. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 $\rho $ –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 $\rho $. 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 $\rho $ : 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 $\rho $ is larger than a certain critical value, $\rho _{{\text { c}}}$ , there is no penalty at all in the guessing exponent, compared to the case of noiseless guessing. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 single (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 it has some interesting implications, which are discussed in depth. Several modifications and extensions of the basic setup are also studied and discussed. [ABSTRACT FROM AUTHOR]

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 $x^{n}=(x_{1},\ldots,x_{n})$ , 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 $x^{n}$ 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, $y^{n}=(y_{1},\ldots,y_{n})$ , which is also an individual sequence. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Consider the problem of guessing the realization of a random vector ${X}$ by repeatedly submitting queries (guesses) of the form “Is ${X}$ equal to ${x}$ ?” until an affirmative answer is obtained. In this setup, a key figure of merit is the number of queries required until the right vector is identified, a number that is termed the guesswork. Typically, one wishes to devise a guessing strategy which minimizes a certain guesswork moment. In this work, we study a universal, decentralized scenario where the guesser does not know the distribution of ${X}$ , and is not allowed to use a strategy which prepares a list of words to be guessed in advance, or even remember which words were already used. Such a scenario is useful, for example, if bots within a Botnet carry out a brute–force attack in order to guess a password or decrypt a message, yet cannot coordinate the guesses between them 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 for finite–state sources. In each case, we derive the guessing exponent, and then prove its asymptotic optimality by deriving a compatible converse bound. The strategies are based on randomized guessing using a universal distribution. We also extend the results to guessing with side information. Finally, for all above scenarios, we design efficient algorithms in order to sample from the universal distributions, resulting in strategies which do not depend on the source distribution, are efficient to implement, and can be used asynchronously by multiple agents. [ABSTRACT FROM AUTHOR]

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 of 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. These include: general properties, a parametric representation, critical rates, phase transitions, optimal input spectrum (water pouring), and comparison to the random coding exponent. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 [ABSTRACT FROM AUTHOR]