For the discrete-time additive white generalized Gaussian noise channel with a generalized input power constraint, with the respective shape and power parameters ≥ 1, we derive an upper bound on the optimal block error exponent. Explicit asymptotic upper bounds in the limit of a large block lengthnare given for three special cases: the Laplace noise channel and the Gaussian noise channel with the average absolute value constraint, and for the Laplace noise channel with the average squared value constraint. The derivation uses the method of types with finite alphabets of sizes depending on the block lengthnand with the number of types sub-exponential inn1.

This paper analyzes the effect of adding a pre-decoder processing function to a receiver that contains a fixed mismatched decoder at the output of a discrete memoryless channel. We study properties of the symbolwise pre-processing function and show that it is a simple yet very powerful tool which enables to obtain reliable transmission at a positive rate for almost every metric. We present lower and upper bounds on the capacity of a channel with mismatched decoding and symbolwise pre-processing, and show that the optimal pre-processing function for random coding is deterministic. We also characterize achievable error exponents. Finally, we prove that a separation principle holds for vectorwise pre-processing functions and further, that deterministic functions maximize the reliably transmitted rate in this case.

For the discrete-time AWGN channel with a power constraint, we give an alternative derivation for the sphere-packing upper bound on the optimal block error exponent. The derivation uses the method of types with finite alphabets of sizes depending on the block length$n$and with the number of types sub-exponential in$n^{1}$.

We derive a new upper bound on the reliability function for channel coding over discrete memoryless channels. Our bounding technique relies on two main elements: (i) adding an auxiliary genie-receiver that reveals to the original receiver a list of codewords including the transmitted one, which satisfy a certain type property, and (ii) partitioning (most of) the list into subsets of codewords that satisfy a certain pairwise-symmetry property, which facilitates lower bounding of the average error probability by the pairwise error probability within a subset. We compare the obtained bound to the Shannon-Gallager-Berlekamp straight-line bound, the sphere-packing bound, and an amended version of Blahut’s bound. Our bound is shown to be at least as tight for all rates, with cases of stricter tightness in a certain range of low rates, compared to all three aforementioned bounds. Our derivation is performed in a unified manner which is valid for any rate, as well as for a wide class of additive decoding metrics, whenever the corresponding zero-error capacity is zero. We further present a relatively simple function that coincides with our bound for symmetric channels having binary input, and may be regarded as an approximation to the reliability function in other cases. We also present a dual form of the bound, and discuss a looser bound of a simpler form, which is analyzed for the case of the binary symmetric channel with maximum likelihood decoding.

We derive a new upper bound on the reliability function for channel coding over discrete memoryless channels. Our bounding technique relies on two main elements: (i) adding an auxiliary genie-receiver that reveals to the original receiver a list of codewords including the transmitted one, which satisfy a certain type property, and (ii) partitioning (most of) the list into subsets of codewords that satisfy a certain pairwise-symmetry property, which facilitates lower bounding of the average error probability by the pairwise error probability within a subset. We compare the obtained bound to the Shannon-Gallager-Berlekamp straight-line bound, the sphere-packing bound, and an amended version of Blahut’s bound. Our bound is shown to be at least as tight for all rates, with cases of stricter tightness in a certain range of low rates, compared to all three aforementioned bounds. Our derivation is performed in a unified manner which is valid for any rate, as well as for a wide class of additive decoding metrics, whenever the corresponding zero-error capacity is zero. We also present a dual form of the bound, and discuss a looser bound of a simpler form, which is analyzed for the case of the binary symmetric channel with maximum likelihood decoding.

We develop a novel framework for proving converse theorems for channel coding, which is based on the analysis technique of multicast transmission with an additional auxiliary receiver, which serves as a genie to the original receiver. The genie provides the original receiver a certain narrowed list of codewords to choose from that includes the transmitted one. This technique is used to derive upper bounds on the mismatch capacity of discrete memoryless channels as well as the reliability function with a mismatched decoding metric. Unlike previous works, our bounding technique exploits also the inherent symmetric requirement from the codewords, leading to these new upper bounds. Since the computations of most of the known bounds on the mismatch capacity are rather complicated, we further present a method to obtain relaxed bounds that are easier to compute. As an example, we analyze the obtained bounds in the binary-input channels case. We conclude by presenting simpler bounds on the reliability function, and provide sufficient conditions for their tightness in certain ranges of rates.

We develop a novel framework for proving converse theorems for channel coding, which is based on the analysis technique of multicast transmission with an additional auxiliary receiver, which serves as a genie to the original receiver. The genie provides the original receiver a certain narrowed list of codewords to choose from that includes the transmitted one. This technique is used to derive upper bounds on the mismatch capacity of discrete memoryless channels as well as the reliability function with a mismatched decoding metric. Unlike previous works, our bounding technique exploits also the inherent symmetric requirement from the codewords, leading to these upper bounds. Since the computations of most of the known bounds on the mismatch capacity are rather complicated, we further present a method to obtain possibly looser bounds that are easier to compute. As an example, we analyze the binary-input channels case. We conclude by presenting simpler bounds on the reliability function, and provide sufficient conditions for their tightness in certain ranges of rates.

We introduce a new analysis technique to derive a single-letter upper bound on the mismatch capacity of a stationary, single-user, memoryless channel with a decoding metric$q$. Our bound is obtained by considering a multicast transmission over a two-user broadcast channel with decoding metrics$q$and$\rho $at the receivers, referred to as$(q,\rho)$-surely degraded. This channel has the property that the intersection event of correct$q$-decoding of receiver 1 and erroneous$\rho $-decoding of receiver 2 has zero probability for any fixed-composition codebook of a certain composition$P$. Our bound holds in the strong converse sense of an exponential decay of the probability of correct decoding at rates above the bound. Further, we refine the proof and present a bound that is tighter than that of any choice of$\rho $. Several examples that demonstrate the strict improvement of our bound compared to previous results are analyzed. Finally, we detect equivalence classes of isomorphic channel-metric pairs$(W,q)$that share the same mismatch capacity. We prove that if the class contains a matched pair, then our bound is tight and the mismatch capacity of the entire class is fully characterized and is equal to the LM rate, which is achievable by random coding, and may be strictly lower that the matched capacity.

We revisit the multicasting approach to the analysis of converse bounds that we recently introduced, and present a refined proof technique for upper bounding the mismatch capacity of the DMC PY|Xwith decoding metric q. To this end, we present an algorithm, which given a 2-user broadcast channel PY Z|X, decoding metrics (q, p), and rate-$R$codebook, produces a sub-codebook of possibly lower rate R’, which has the property that the intersecting event of erroneous p-decoding by the$Z$receiver and correct q-decoding of the$Y$receiver has a vanishing probability. This results in a bound on the mismatch capacity of the channel to the Y-receiver that is given in terms of the sum of an achievable rate for a$Z$receiver of any broadcast channel having marginal PY|Xplus the corresponding rate reduction R - R'. We further detect the p* metric which yields the tightest bound out of all the type-dependent metrics, and focusing on the case of zero rate reduction, we show that the resulting bound is at least as tight as our previous best known upper bound [1]. We conclude by presenting sufficient conditions for the tightness of our bound and equivalence classes of code composition-channel-metric triplets.

For a discrete memoryless channel with finite input and output alphabets, we prove convergence of an iterative computation of the optimal correct-decoding exponent as a function of communication rate, for a fixed rate and for a fixed slope.

We introduce a new analysis technique that we use to derive a single-letter upper bound on the mismatch capacity of a stationary point-to-point memoryless channel with decoding metric q. Our bound is obtained by considering a multicast transmission over a two-user broadcast channel with decoding metrics q and ρ at the receivers, referred to as (q, ρ)-surely degraded. This channel has the property that the intersection event of the correct q-decoding of receiver 1 and the erroneous ρ-decoding of receiver 2 has zero probability for any codebook of a certain composition P. Our bound holds in the strong converse sense of exponential decay of the probability of correct decoding at rates above the bound. Several examples that demonstrate the strict improvement of our bound compared to previous results are analyzed. Further, we detect equivalence classes of isomorphic channel-metric pairs (W, q) that share the same mismatch capacity. We prove that if the class contains a matched pair, then our bound is tight and the mismatch capacity of the entire class is fully characterized and is equal to the LM rate, which is the highest rate achievable by random coding, and may be strictly lower than the Shannon (matched) capacity.

We consider a generalization of the discrete memoryless channel, in which the channel probability distribution is replaced by a uniform distribution over clouds of channel output sequences. For a random ensemble of such channels, we derive an achievable error exponent and a converse bound on the correct-decoding exponent. As a corollary of these results, we obtain the channel ensemble capacity.

The problem of channel coding over the Gaussian multiple-input multiple-output (MIMO) broadcast channel (BC) with additive independent Gaussian states is considered. The states are known in a noncausal manner to the encoder, and it wishes to minimize the amount of information that the receivers can learn from the channel outputs about the state sequence. The state leakage rate is measured as a normalized blockwise mutual information between the state sequence and the channel outputs' sequences. We employ a new version of a state-dependent extremal inequality and show that Gaussian input maximizes the state-dependent version of Marton's outer bound. Further, we show that our inner bound coincides with the outer bound. Our result generalizes previously studied scalar Gaussian BC with state and MIMO BC without the state.

We show that a recursive cost-constrained random coding scheme attains an error exponent that is at least as high as both the random-coding exponent and the expurgated exponent. The random coding scheme enforces that every pair of codewords in the codebook meets a minimum distance condition, and is reminiscent of the Gilbert-Varshamov construction, but with the notable feature of permitting continuous-alphabet channels. The distance function is initially arbitrary, and it is shown that the Chernoff/Bhattacharrya distance suffices to attain the random coding and expurgated exponents.

We extend the notion of list decoding to ratio list decoding which involves a list decoder whose list size is specified as a function of the number of messages Mnand the block length n. We present the necessary and sufficient conditions on Mnfor the existence of code sequences which enable reliable list decoding with respect to the desired list size L(Mn, n). It is shown that the ratio-capacity, defined as the supremum of achievable normalized logarithms of the ratio r(Mn, n) = Mn/L(Mn, n), is equal to the Shannon channel capacity C, for both stochastic and deterministic encoding. Allowing for random list size, we are able to deduce some properties of identification codes, where the decoder's output can be viewed as a list of messages corresponding to decision regions that include the channel output. We further address the regime of mismatched list decoding, in which the list constitutes of the codewords that accumulate the highest score values (jointly with the channel output) according to some given function. We study the case of deterministic encoding and mismatched ratio list decoding. We establish similar necessary and sufficient conditions for the existence of code sequences which enable reliable mismatched list decoding with respect to the desired list size L(Mn, n), and we show that the ratio-capacity with mismatched decoding is equal to the mismatch capacity. Focusing on the case of an exponential list size Ln= enΘ, its comparison with ordinary mismatched decoding shows that the increase in capacity is by Θ bits per channel used for all channels and decoding metrics. Several properties of the average error probability in the setup of mismatched list decoding with deterministic list size are provided.

We introduce a random coding technique for transmission over discrete memoryless channels, reminiscent of the basic construction attaining the Gilbert-Varshamov bound for codes in Hamming spaces. The code construction is based on drawing codewords recursively from a fixed type class, in such a way that a newly generated codeword must be at a certain minimum distance from all previously chosen codewords, according to some generic distance function. We derive an achievable error exponent for this construction and prove its tightness with respect to the ensemble average. We show that the exponent recovers the Csiszár and Körner exponent as a special case, which is known to be at least as high as both the random-coding and expurgated exponents, and we establish the optimality of certain choices of the distance function. In addition, for additive distances and decoding metrics, we present an equivalent dual expression, along with a generalization to infinite alphabets via cost-constrained random coding.

In this paper, we consider the simultaneous connectivity of primary and secondary networks forming a cognitive model. It is assumed that the cognitive model includes guard zones that prevent the nodes of the secondary network from being active in the vicinity of primary nodes to limit interference. Under these assumptions, we characterize the region of densities, the transmission radii of the nodes in each of the networks, and the guard zones for which the two networks have a unique unbounded connected component. We prove that this model is feasible, that is, there exists simultaneous connectivity with the unique unbounded connected component in each of the networks. We also provide necessary and sufficient conditions for the simultaneous connectivity of this cognitive model.

We introduce a random code construction for channel coding in which the codewords are constrained to be well-separated according to a given distance function, analogously to an existing construction attaining the Gilbert-Varshamov bound. We derive an achievable error exponent for this construction, and prove its tightness with respect to the ensemble average. We show that the exponent recovers the Csiszár and Körner exponent as a special case by choosing the distance function to be the negative of the empirical mutual information. We further establish the optimality of this distance function with respect to the exponent of the random coding scheme.

This paper surveys recent works characterizing the fundamental limits of general channels with mismatched decoding from an information-spectrum analysis perspective. It focuses on channel decoding, threshold decoding, and list decoding, all in the mismatched regime.

The problem of mismatched decoding with an additive bounded metric q for a discrete memoryless channel W is addressed. We study two kinds of decoders. The δ-margin mismatched decoder outputs a message whose metric with the channel output exceeds that of all the other codewords by at least δ. The τ-threshold decoder outputs a single message whose metric with the channel output exceeds a threshold τ. It is proved that the mismatch capacity with a constant margin decoder is equal to the “product-space” improvement of the random coding lower bound on the mismatch capacity, Cq(∞)(W), which was introduced by Csiszár and Narayan. We next consider sequences of P-constant composition codebooks. Using the Central Limit Theorem, it is shown that for such sequences of codebooks the supremum of achievable rates with constant threshold decoding is upper bounded by the supremum of the achievable rates with a constant margin decoder, and therefore also by Cq(∞)(W). Further, a soft converse is proved stating that if the average probability of error of a sequence of codebooks with ordinary mismatched decoding converges to zero sufficiently fast, the rate of the code sequence is upper bounded by Cq(∞)(W). In particular, if q is a bounded rational metric, and the average probability of error converges to zero faster than O(n-1), then R ≤ Cq(∞)(W). Finally, a max-min multi-letter upper bound on the mismatch capacity that bears some resemblance to Cq(∞)(W) is presented.

We address the problem of existence of unbiased constrained parameter estimators. We show that if the constrained set of parameters is compact and the hypothesized distributions are absolutely continuous with respect to one another, then there exists no unbiased estimator. Weaker conditions for the absence of unbiased constrained estimators are also specified. We provide several examples, which demonstrate the utility of these conditions.

The problem of identification via channels concerns a decoder that needs to provide a reliable answer to the question of whether or not a specific message (unknown in advance) was transmitted. The achievability result of Ahlswede and Dueck who introduced this problem, relied on a universal identification decoder. This decoder assigns a channel output vector ynto a decision region Dmif the empirical mutual information between ynand an input vector that could have been transmitted given message m exceeds a certain threshold. We study a generalized class of identification decoders that determine the decision regions by comparing a type-dependent “metric” to a threshold. We introduce the notion of identification capacity with respect to a given decoding metric as the supremum of achievable normalized iterated logarithms of the number of messages that can be identified reliably using these metrics. We characterize achievable identification rates and error exponents using a type-dependent metric. In the case of an additive metric we show that the random coding achievable rate for classical mismatched decoding is an achievable identification rate.

In this paper we analyze the connectivity of cognitive radio ad-hoc networks. Contrary to previous works, we pursue the connectivity of both the primary and secondary networks, a state we call “simultaneous connectivity”. We determine that if the networks are simultaneously connected then their infinite connected components are unique. In addition, we characterize the region of densities in which both the primary and secondary networks have a unique infinite connected component.

A single-user state-dependent channel with mismatched decoding is considered. Several setups are studied, which differ by the manner in which the state information is available to the encoder (causally or non-causally), and by whether or not the decoder is cognizant of the state sequence. We present achievable rates for these channels based on random coding and random binning and we also observe special cases. In the non-causal case (the mismatched Gelfand Pinsker channel) we introduce a scheme of layered binning and calculate the corresponding achievable rate.

In this paper, we introduce the two-user asynchronous cognitive multiple access channel (ACMAC). This channel model includes two transmitters, an uninformed one and an informed one, which knows prior to the beginning of a transmission the message which the uninformed transmitter is about to send. We assume that the channel from the uninformed transmitter to the receiver suffers a fixed but unknown delay. We further introduce a modified model, referred to as the asynchronous codeword cognitive multiple access channel (ACC-MAC), which differs from the ACMAC in that the informed user knows the signal that is to be transmitted by the other user, rather than the message that it is about to transmit. We state inner and outer bounds on the ACMAC and the ACC-MAC capacity regions, and we specialize the results to the Gaussian case. Furthermore, we characterize the capacity regions of these channels in terms of multi-letter expressions. Finally, we provide an example that instantiates the difference between message side-information and codeword side-information.

The setup of a general channel is considered in the mismatched case, i.e., when the decoder uses a general decoding metric. An expression for the average error probability in list decoding with block length n, metric qn, list size enΘnand rate R, denoted ε(n)qn(R, Θn), is established. Further, a general multi-letter formula for the mismatched capacity with list decoding is derived. It is shown that similarly to the matched capacity of the discrete memoryless channel, if the list size grows exponentially at a fixed rate Θ, then the increase in capacity is Θ bits per channel use. Additionally, a random coding lower bound on ε(n)qn(R, Θn) is presented. We conclude by presenting an inequality that can be regarded as an extension of Fano's inequality in the mismatched case with list decoding. As a special case, we derive a lower bound on the average probability of error at rates above the erasures only capacity of the discrete memoryless channel.

The problem of mismatched decoding with an additive metric q for a discrete memoryelss channel W is addressed. Two max-min multi-letter upper bounds on the mismatch capacity Cq(W) are derived. We further prove that if the average probability of error of a sequence of codebooks converges to zero sufficiently fast, then the rate of the code-sequence is upper bounded by the “product-space” improvement of the random coding lower bound on the mismatched capacity, C(∞)q(W), introduced by Csiszár and Narayan. In particular, if q is a bounded rational metric, and the average probability of error converges to zero faster than O(1/n), then R ≤ C(∞)q(W). Consequently, in this case if a sequence of codes of rate R is known to achieve average probability of error which is o(1/n), then there exists a sequence of codes operating at a rate arbitrarily close to R with average probability of error which vanishes exponentially fast. We conclude by presenting a general expression for the mismatch capacity of a general channel with a general type-dependent decoding metric.

This paper studies the mismatched decoding problem for binary-input discrete memoryless channels. An example is provided for which an achievable rate based on superposition coding exceeds the Csiszár-Körner-Hui rate, thus providing a counter-example to a previously reported converse result. Both numerical evaluations and theoretical results are used in establishing this claim.

The problem of characterizing achievable rates and error exponents for discrete memoryless channels with mismatched decoding is addressed. A mismatched cognitive multiple-access channel is introduced, and an inner bound on its capacity region is derived using two alternative encoding methods: 1) superposition coding and 2) random binning. The inner bounds are derived by analyzing the average error probability of the code ensemble for both methods and by a tight characterization of the resulting error exponents. Random coding converse theorems are also derived. A comparison of the achievable regions shows that in the matched case, random binning performs as well as superposition coding, i.e., the region achievable by random binning is equal to the capacity region. The achievability results are further specialized to obtain a lower bound on the mismatch capacity of the single-user channel by investigating a cognitive multiple-access channel whose achievable sum-rate serves as a lower bound on the single-user channel's capacity. While the achievable rate presented here may not improve the rate achieved by Lapidoth's scheme in optimizing over the parameters of the random coding scheme, it can improve the achieved rate for given parameters, and thereby may reduce the computational complexity required to find a good code.

The fundamental limits of channels with mismatched decoding are addressed. A general formula is established for the mismatch capacity of a general channel, defined as a sequence of conditional distributions with a general decoding metrics sequence. We deduce an identity between the Verdú-Han general channel capacity formula, and the mismatch capacity formula applied to maximum likelihood decoding metric. Furthermore, several upper bounds on the capacity are provided, and a simpler expression for a lower bound is derived for the case of a non-negative decoding metric. The general formula is specialized to the case of finite input and output alphabet channels with a type-dependent metric. The closely related problem of threshold mismatched decoding is also studied, and a general expression for the threshold mismatch capacity is obtained. As an example of threshold mismatch capacity, we state a general expression for the erasures-only capacity of the finite input and output alphabet channel. We observe that for every channel, there exists a (matched) threshold decoder, which is capacity achieving. In addition, necessary and sufficient conditions are stated for a channel to have a strong converse.

Several channels with asynchronous side information are introduced. We first consider single-user state-dependent channels with asynchronous side information at the transmitter. It is assumed that the state information sequence is a possibly delayed version of the state sequence, and that the encoder and the decoder are aware of the fact that the state information might be delayed. It is additionally assumed that an upper bound on the delay is known to both the encoder and the decoder, but other than that, they are ignorant of the actual delay. We consider both the causal and the noncausal cases and present achievable rates for these channels, and the corresponding coding schemes. We find the capacity of the asynchronous Gel'fand-Pinsker channel with feedback. Finally, we consider a memoryless state-dependent channel with asynchronous side information at both the transmitter and the receiver, and establish a single-letter expression for its capacity.

The fundamental limits of channels with mismatched decoding are addressed. A general formula is established for the mismatch capacity of a general channel, defined as a sequence of conditional distributions with a general decoding metrics sequence. We deduce an identity between the Verdú-Han general channel capacity formula, and the mismatch capacity formula applied to Maximum Likelihood decoding metric. Further, several upper bounds on the capacity are provided, and a simpler expression for a lower bound is derived for the case of a non-negative decoding metric. The closely related problem of threshold mismatched decoding is also studied, and a general expression for the threshold mismatch capacity is obtained. As an example of threshold mismatch capacity, we state a general expression for the erasures-only capacity of the finite input and output alphabet channel. We observe that for every channel there exists a (matched) threshold decoder which is capacity achieving. Additionally, necessary and sufficient conditions are stated for a channel to have a strong converse.

We introduce the asynchronous cognitive multiple-access channel with an uninformed encoder and an informed one. We assume that the informed encoder knows in advance the message of the uninformed encoder and consequently its codeword, up to some delay. In addition, the informed encoder knows the set of all possible delays in the channel. We characterize the capacity region of the ACMAC in terms of multi-letter expressions. In addition, we present single-letter inner and outer bounds on the capacity region of this channel. We conclude by studying the special case of the Gaussian asynchronous multiple-access channels with an uninformed encoder.

The problem of mismatched decoding for discrete memoryless channels is addressed. A mismatched cognitive multiple-access channel is introduced, and an inner bound on its capacity region is derived using two alternative encoding methods: superposition coding and random binning. The inner bounds are derived by analyzing the average error probability of the code ensemble for both methods and by a tight characterization of the resulting error exponents. Random coding converse theorems are also derived. A comparison of the achievable regions shows that in the matched case, random binning performs as well as superposition coding, i.e., the region achievable by random binning is equal to the capacity region. The achievability results are further specialized by investigating a cognitive multiple access channel whose achievable sum-rate serves as a lower bound on the single-user channel's capacity. In certain cases, for given auxiliary random variables this bound strictly improves on the achievable rate derived by Lapidoth.

In this paper, we investigate a three-user cognitive communication network where a primary two-user Multiple Access Channel (MAC) suffers interference from a secondary point-to-point (P2P) channel, sharing the same medium. While the P2P channel transmitter — transmitter 3 — causes an interference at the primary MAC receiver, we assume that the primary channel transmitters — transmitters 1 and 2 — do not cause any interference at the P2P receiver. It is assumed that one of the MAC transmitters has cognitive capabilities and cribs causally from the other MAC transmitter. Furthermore, we assume that the cognitive transmitter knows the message of transmitter 3 in a noncausal manner, thus introducing the three-user Multiple Access Cognitive Z-Interference Channel (MA-CZIC). We obtain inner and outer bounds on the capacity region of the three-user MA-CZIC for both strictly and nonstrictly causal cribbing cognitive encoders.

We investigate the capacity of a multiple access channel with cooperating encoders where partial state information is known to each encoder in a non-causal way and full state information is known to the decoder. The cooperation between the encoders has a two-fold purpose: to generate empirical state coordination between the encoders, and to share information about the private messages that each encoder has. For two-way cooperation, this two-fold purpose is achieved by double-binning, where the first layer of binning is used to generate the state coordination similarly to the two-way source coding, and the second layer of binning is used to transmit information about the private messages. The complete result provides the framework and perspective for addressing a complex level of cooperation that mixes states and messages in an optimal way. We present few examples and compare the optimal coding scheme that combines the message and the state to naive cooperation schemes that are based on separate message and state coding.

We investigate the capacity of a multiple access channel with cooperating encoders where partial state information is known to each encoder and full state information is known to the decoder. The cooperation between the encoders has a two-fold purpose: to generate empirical state coordination between the encoders, and to share information about the private messages that each encoder has. For two-way cooperation, this two-fold purpose is achieved by double-binning, where the first layer of binning is used to generate the state coordination similarly to the two-way source coding, and the second layer of binning is used to transmit information about the private messages. The complete result provides the framework and perspective for addressing a complex level of cooperation that mixes states and messages in an optimal way.

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.

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.

Like the conventional two-user interference channel, the cognitive interference channel consists of two transmitters whose signals interfere at two receivers. It is assumed that there is a common message (message 1) known to both transmitters, and an additional independent message (message 2) known only to the cognitive transmitter (transmitter 2). The cognitive receiver (receiver 2) needs to decode messages 1 and 2, while the non cognitive receiver (receiver 1) should decode only message 1. Furthermore, message 2 is assumed to be a confidential message which needs to be kept as secret as possible from receiver 1, which is viewed as an eavesdropper with regard to message 2. The level of secrecy is measured by the equivocation rate. In this paper, a single-letter expression for the capacity-equivocation region of the discrete memoryless cognitive interference channel is obtained. The capacity-equivocation region for the Gaussian cognitive interference channel is also obtained explicitly. Moreover, particularizing the capacity-equivocation region to the case without a secrecy constraint, the capacity region for the two-user cognitive interference channel is obtained, by providing a converse theorem.

Cognitive state-dependent interference channels are analyzed. We focus on the two-user case with two message sources. One of the transmitters, referred to as the cognitive informed user, knows both messages and also the states of the channel in a non-causal manner. The other transmitter knows only one of the messages and does not know the channel states. Each of the two decoders is supposed to decode only its intended message. Inner and outer bounds on the capacity region of this channel are provided for the general finite input alphabet case. The asymmetric state-dependent Gaussian weak interference channel with non-causal state information is then considered, and a closed form formula for the capacity region is established in the regime of weak interference.

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 generalize the Gel'fand–Pinsker model to encompass the setup of a memoryless multiple-access channel (MAC). According to this setup, only one of the encoders knows the state of the channel (noncausally), which is also unknown to the receiver. Two independent messages are transmitted: a common message and a message transmitted by the informed encoder. We find explicit characterizations of the capacity region with both noncausal and causal state information. Further, we study the noise-free binary case, and we also apply the general formula to the Gaussian case with noncausal channel state information, under an individual power constraint as well as a sum power constraint. In this case, the capacity region is achievable by a generalized writing-on-dirty-paper scheme.

We generalize the Gel'fand-Pinsker model to encompass the setup of a memoryless multiple-access channel. According to this setup, only one of the encoders knows the state of the channel (non-causally), which is also unknown to the receiver. Two independent messages are transmitted: a common message and a message transmitted by the informed encoder. We find explicit characterizations of the capacity region with both non-causal and causal state information. Further, we apply the general formula to the Gaussian case with non-causal channel state information, under an individual power constraint as well as a sum power constraint. In this case, the capacity region is achievable by a generalized writing-on-dirty-paper scheme.

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

Using an information-spectrum approach, a limiting expression for the capacity region of a general network without relays combined of M transmitters observing K input messages, and L receivers, is found. This general setup accounts for the broadcast channel with common messages, the general interference channel, and the multiple access channel as special cases. It is demonstrated how the limiting expression can be used to yield a single-letter tight outer bound for the case of a two-user stationary memoryless degraded broadcast channel

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

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, we present the random coding error exponents of the single-user and the multiple-access Gel'fand-Pinsker channels.

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.

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.

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.