This paper studies expurgated random coding bounds and exponents for source coding with side information with a given (possibly mismatched) decoding rule. We propose an expurgation technique that is an iterative version of Gallager’s expurgation method for channel coding and enables a direct dual domain derivation of non-asymptotic bounds for discrete sources with arbitrary side information alphabets and decoding metrics. Specializing the bounds to memoryless models a dual domain achievable error exponent for type-by-type random coding is derived and shown to coincide with the Csiszár-Körner exponent obtained via graph decomposition.

We introduce an expurgation method for source coding with side information that enables direct dual-domain derivations of expurgated error exponents. Dual-domain methods yield optimization problems over few parameters, with any sub-optimal choice resulting in an achievable exponent, as opposed to primal-domain optimization over distributions. In addition, dual-domain methods naturally allow for general alphabets and/or memory. We derive two such expurgated error exponents for different random-coding ensembles in the case where the decoder is possibly mismatched with respect to the source and side information joint distribution. We show the better of the exponents coincides with the Csiszár-Körner exponent obtained via a graph decomposition lemma. We show some numerical examples that illustrate the differences between the two exponents and show that in the case of source coding without side information, the expurgated exponent coincides with the error exponent of the source optimal code.

We derive closed-form expressions of the generalized mutual information (GMI) for the Gilbert-Elliott channel by introducing memory in the decoding metric. We first study the simple case of block memory and then propose a unifilar decoder that explicitly tracks state memory. We show that the GMI for both decoders exhibits a monotonic improvement with the memory order, and that the rates achieved by the unifilar decoder of a given memory order are always higher than those achieved by the block decoder.

This paper studies expurgated error exponents for joint source-channel coding for discrete memoryless sources and channels. We consider a partition of the source messages into classes, where the codeword distributions depend on the class. We show that two carefully chosen classes suffice to achieve Csiszár’s expurgated exponent.

This paper provides a dual domain derivation of the error exponent of maximum mutual information (MMI) decoding with constant composition codes, showing it coincides with that of maximum likelihood decoding for discrete memoryless channels. The analysis is further extended to joint source-channel coding, demonstrating that the generalized MMI decoder achieves the same random coding error exponent as the maximum a posteriori decoder.

This paper investigates achievable information rates and error exponents of mismatched decoding when the channel belongs to the class of channels that are close to the decoding metric in terms of relative entropy. For both discrete- and continuous-alphabet channels, we derive approximations of the worst-case achievable information rates and error exponents as a function of the radius of a small relative entropy ball centered at the decoding metric, allowing the characterization of the loss incurred due to imperfect channel estimation. We provide a number of examples including symmetric metrics and modulo-additive noise metrics for discrete systems, and nearest neighbor decoding for continuous-alphabet channels, where we derive the approximation when the channel admits arbitrary statistics and when it is assumed noise-additive with unknown finite second-order moment.

We derive finite-memory upper and lower bounds to the entropy rate of binary 2-state hidden Markov models. These directly provide upper and lower bounds to the capacity of the Gilbert-Elliott channel. As the memory increases, the bounds approach the capacity of the channel. Our numerical experiments suggest that even a simple memory-1 upper bound significantly improves over the current best upper bound by Mushkin and Bar-David.

We study Gaussian i.i.d. codebooks and nearest neighbor decoding over continuous-alphabet channels. We define a class of compound channels that are within a small radius relative entropy ball centered at the nearest neighbor decoding metric. We derive approximations to the worst-case achievable rates and find the penalty terms proportional to the square root of the ball radius.

This paper investigates achievable error exponents of i.i.d. and constant-composition codes for a decoder whose decoding metric is close to the channel probability law in terms of relative entropy. We derive approximations of the worst-case achievable error exponents as functions of the radius of a small relative entropy ball centered at the decoding metric, and characterize the error terms of the underlying approximations.

We show that for a wide range of channels and code ensembles with pairwise-independent codewords, with probability tending to 1 with the code length, expurgating an arbitrarily small fraction of codewords from a randomly selected code results in a code attaining the expurgated exponent.

The statement of Theorem 1 in [1] should have read as follows.

We find the exact typical error exponent of constant composition generalized random Gilbert-Varshamov (RGV) codes over discrete memoryless channels with generalized likelihood decoding. We show that the typical error exponent of the RGV ensemble is equal to the expurgated error exponent, provided that the RGV codebook parameters are chosen appropriately. We also prove that the random coding exponent converges in probability to the typical error exponent, and the corresponding non-asymptotic concentration rates are derived. Our results show that the decay rate of the lower tail is exponential while that of the upper tail is double exponential above the expurgated error exponent. The explicit dependence of the decay rates on the RGV distance functions is characterized.

We study the typical error exponent of constant composition generalized random Gilbert-Varshamov (RGV) codes over discrete memoryless channels (DMC) channels with generalized likelihood decoding. We show that the typical error exponent of the RGV ensemble is equal to the expurgated error exponent, provided that the RGV codebook parameters are chosen appropriately. We also prove that the exponent of a randomly chosen RGV code converges in probability to the typical error exponent; the lower tail is shown to decay exponentially while the upper tail decays double-exponentially above the expurgated exponent.

This paper shows that the probability that the error exponent of a given code randomly generated from a pairwise-independent ensemble is smaller than a lower bound on the typical random-coding exponent tends to zero as the codeword length tends to infinity. This lower bound is known to be tight for i.i.d. ensembles over the binary symmetric channel and for constant-composition codes over memoryless channels. Our results recover both as special cases and remain valid for arbitrary alphabets, arbitrary channels—for example finite-state channels with memory—, and arbitrary pairwise-independent ensembles. We specialize our results to the i.i.d., constant-composition and cost-constrained ensembles over discrete memoryless channels and to ensembles over finite-state channels.

We derive a sphere-packing error exponent for coded transmission over discrete memoryless channels with a fixed decoding metric. By studying the error probability of the code over an auxiliary channel, we find a lower bound to the probability of error of mismatched decoding. The bound is shown to decay exponentially for coding rates smaller than a new upper bound to the mismatch capacity which is established in this paper. For rates higher than the new upper bound, the error probability is shown to be bounded away from zero. The new upper bound is shown to improve over previous upper bounds to the mismatch capacity.

This paper shows that, for discrete memoryless channels, the error exponent of a randomly generated code with independent codewords converges in probability to its expectation—the typical error exponent. For high rates, the result follows from the fact that the random-coding error exponent and the sphere-packing error exponent coincide. For low rates, instead, the convergence is based on the fact that the union bound accurately characterizes the error probability. The paper also zooms into the behavior at asymptotically low rates, and shows that the normalized error exponent converges in distribution to the standard Gaussian or a Gaussian-like distribution. We also state several results on the convergence of the error probability and error exponent for generic ensembles and channels.

We derive a lower bound on the typical random-coding (TRC) exponent of pairwise-independent codeword ensembles used over a finite-state channel (FSC) at rates below capacity. Under some conditions, we also show that the probability of selecting a code from the ensemble with an error exponent larger than our lower bound tends to one as the codeword length tends to infinity. Our result, presented here for the FSC, also applies to compound channels.

We propose a composite hypothesis test in the Neyman-Pearson setting where the null distribution is known and the alternative distribution belongs to a certain family of distributions. The proposed test interpolates between Hoeffding’s test and the likelihood ratio test and achieves the optimal error exponent tradeoff for every distribution in the family. In addition, the proposed test is shown to attain the type-I error probability prefactor of ${n^{\frac{{\bar d - 1}}{2}}}$, where $\bar d$ is the dimension of the family of distributions projected onto a relative entropy ball centered at the null distribution. This can be significantly smaller than the prefactor ${n^{\frac{{a - 2}}{2}}}$ achieved by the Hoeffding’s test where d is the dimension of the probability simplex. In addition, the proposed test achieves the optimal type-II error probability prefactor for every distribution in the family.

We study the convergence in distribution of the error exponent of random codes, defined as the negative normalized logarithm of the probability of error, of both i.i.d. and constant-composition ensembles over discrete memoryless channels. For a constant number of messages, the distribution of the error exponent converges to that of the minimum of a set of independent normal random variables. For an increasing sub-exponential number of messages, the error exponent converges to a normal distribution, independent of the number of messages. As a byproduct, we provide a new method to prove the convergence to a normal distribution of an infinite number of random variables based on a modification of the Wasserstein metric.

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlós that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurgated exponent at rate zero for a broad family of channel-decoding metric pairs.

We study the problem of mismatched binary hypothesis testing between i.i.d. distributions. We analyze the tradeoff between the pairwise error probability exponents when the actual distributions generating the observation are different from the distributions used in the likelihood ratio test, sequential probability ratio test, and Hoeffding’s generalized likelihood ratio test in the composite setting. When the real distributions are within a small divergence ball of the test distributions, we find the deviation of the worst-case error exponent of each test with respect to the matched error exponent. In addition, we consider the case where an adversary tampers with the observation, again within a divergence ball of the observation type. We show that the tests are more sensitive to distribution mismatch than to adversarial observation tampering.

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlós that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurgated exponent at rate zero for a broad family of channel and decoding metric pairs. A full version of this paper is accessible at: https://arxiv.org/pdf/2101.10238.pdf

We study mismatched sequential hypothesis testing. We analyze the type-I and and type-II error exponents when the actual distributions generating the observation are different from those used in the test. We derive the worst-case error exponents when the actual distributions generating the data are within a relative entropy ball of the test distributions and show the error exponent sensitivity of the test for small relative entropy balls.

For random-coding ensembles with pairwise-independent codewords, we show that the probability that the exponent of a given code from the ensemble being smaller than an upper bound on the typical random-coding exponent is vanishingly small. This upper bound is known to be tight for i.i.d. ensembles over the binary symmetric channel and for constant-composition codes over memoryless channels. Our result recovers these as special cases and remains valid for arbitrary alphabets and channel memory, as well as arbitrary ensembles with pairwise independent codewords.

We derive a sphere-packing error exponent for mismatched decoding over discrete memoryless channels. We find a lower bound to the probability of error of mismatched decoding that decays exponentially for coding rates smaller than a new upper bound to the mismatch capacity. For rates higher than the new upper bound, the error probability is shown to be bounded away from zero. The new upper bound is shown to improve over previous upper bounds to the mismatch capacity.

This paper studies the error exponent of i.i.d. randomly generated codes used for transmission over discrete memoryless channels with maximum likelihood decoding. Specifically, this paper shows that the error exponent of a code, defined as the negative normalized logarithm of the probability of error, converges in probability to the typical error exponent. For high rates, the result is a consequence of the fact that the random-coding error exponent and the sphere-packing error exponent coincide. For low rates, instead, the proof of convergence is based on the fact that the union bound accurately characterizes the probability of error.

The optimal quantization of output binary-input discrete memoryless channels is considered, whereby the optimal quantizer preserves at least a constant$\alpha $-fraction of the original mutual information, with the smallest output cardinality. Two recursive methods with top-down and bottom-up approaches are developed; these methods lead to a new necessary condition for the recursive quantizer design. An efficient algorithm with linear complexity, based on dynamic programming and the new necessary optimality condition, is proposed.

Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder's sequence X differs from the decoder's sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size.

We derive a single-letter upper bound to the mismatched-decoding capacity for discrete memoryless channels. The bound is expressed as the mutual information of a transformation of the channel, such that a maximum-likelihood decoding error on the translated channel implies a mismatched-decoding error in the original channel. In particular, it is shown that if the rate exceeds the upper-bound, the probability of error tends to one exponentially when the block-length tends to infinity. We also show that the underlying optimization problem is a convex-concave problem and that an efficient iterative algorithm converges to the optimal solution. In addition, we show that, unlike achievable rates in the literature, the multiletter version of the bound cannot not improve. A number of examples are discussed throughout the paper.

This paper proposes an efficient simulation method based on importance sampling to estimate the random-coding error probability of coded modulation. The technique is valid for complex-valued modulations over Gaussian channels, channels with memory, and naturally extends to fading channels. The simulation method is built on two nested importance samplers to respectively estimate the pairwise error probability and generate the channel input and output. The effect of the respective number of samples on the overall bias and variance of the estimate of the error probability is characterized. For a memoryless channel, the estimator is shown to be consistent and with a small variance, growing with the square root of the code length, rather than the exponential growth of a standard Monte Carlo estimator.

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.

Motivated by the sequence reconstruction problem from traces in DNA-based storage, we consider the problem of designing codes for the deletion channel when multiple observations (or traces) are available to the decoder. We propose simple binary and non-binary codes based on Varshamov-Tenengolts (VT) codes. The proposed codes split the codeword in blocks and employ a VT code in each block. The availability of multiple traces helps the decoder to identify deletion-free copies of a block, and to avoid mis-synchronization while decoding. The encoding complexity of the proposed scheme is linear in the codeword length; the decoding complexity is linear in the codeword length, and quadratic in the number of deletions and the number of traces. The proposed scheme offers an explicit low-complexity technique for correcting deletions using multiple traces.

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.

Saddlepoint approximations to the error probability are derived for multiple-cost-constrained random coding ensembles where codewords satisfy a set of constraints. Constant-composition inputs over a binary symmetric channel are studied as a particular case. For codewords with equiprobable empirical distribution, the analysis recovers the same error exponent and pre-exponential polynomial decay as the uniform i.i.d. ensemble and provides an explicit formula for the loss in prefactor (third-order term) incurred by the constant-composition ensemble.

We derive a single-letter upper bound to the mismatched-decoding capacity for discrete memoryless channels. The bound is expressed as the mutual information of a transformation of the channel, such that a maximum-likelihood decoding error on the translated channel implies a mismatched-decoding error in the original channel. We show this bound recovers the binary-input binary-output mismatch capacity which is known to either be the channel capacity or zero. In addition, a strong converse is shown for this upper bound: if the rate exceeds the upper-bound, the probability of error tends to 1 exponentially when the block-length tends to infinity.

This paper studies the random-coding exponent of joint source-channel coding for the multiple-access channel with correlated sources. For each user, by defining a threshold, the messages of each source are partitioned into two classes. The achievable exponent for correlated sources with two message-dependent input distributions for each user is determined and shown to be larger than that achieved using only one input distribution for each user. A system of equations is presented to determine the optimal thresholds maximizing the achievable exponent. The obtained exponent is compared with the one derived for the MAC with independent sources.

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.

Channel output quantization to a smaller number of outputs is modeled as a mismatched decoding problem. The conditions that a mismatched decoding metric should satisfy in order to represent an output quantizer are derived. In addition, a mismatched decoding metric and hypothesis test that minimizes the average error probability are found. It is shown that the best possible mismatched decoder is equivalent to maximum-likelihood decoding for the channel between the channel input and the quantized output. This gives a class of mismatched decoding problems where the mismatch capacity is known. This result supports previous studies on quantizer design and optimization over the quantized channel.

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.

We introduce a definition of perfect and quasi-perfect codes for discrete symmetric channels based on the packing and covering properties of generalized spheres whose shape is tilted using an auxiliary probability measure. This notion generalizes previous definitions of perfect and quasi-perfect codes and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to coincide with the estimate provided by the meta-converse lower bound. We illustrate how the proposed definition naturally extends to cover almost-lossless source-channel coding and lossy compression.

This paper addresses the problem of efficient encoding of non-binary Varshamov-Tenengolts (VT) codes. We propose a linear-time encoding method to systematically map binary message sequences onto VT codewords. The method provides a new lower bound on the size of q-ary VT codes of length n.

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.

We propose a saddlepoint approximation of the error probability of a binary hypothesis test between two i.i.d. distributions. The approximation is accurate, simple to compute, and yields a unified analysis in different asymptotic regimes. The proposed formulation is used to efficiently compute the meta-converse lower bound for moderate block-lengths in several cases of interest.

We introduce a definition of perfect and quasi-perfect codes for symmetric channels parametrized by an auxiliary output distribution. This new definition generalizes previous definitions and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to attain the meta-converse lower bound.

Saddlepoint approximations and expansions of the random coding union bound are derived for the i.i.d. random coding ensemble. Using the inverse Laplace transform of lattice and strongly non-lattice distributions, our results recover the random coding error exponent and refine the pre-exponential coefficient of the error probability. Explicit characterization of the terms are given for the binary symmetric channel and for the binary input AWGN channel.

Saddlepoint approximations to the pairwise error probability and to the random coding union bound are derived for the cost-constrained random coding ensemble. For the special case of the AWGN channel, an alternative expression to approximate the Shannon bound for optimal spherical codes is found.

In this paper, an achievable error exponent for the multiple-access channel with two independent sources is derived. For each user, the source messages are partitioned into two classes and codebooks are generated by drawing codewords from an input distribution depending on the class index of the source message. The partitioning thresholds that maximize the achievable exponent are given by the solution of a system of equations. We also derive both lower and upper bounds for the achievable exponent in terms of Gallager's source and channel functions. Finally, a numerical example shows that using the proposed ensemble gives a noticeable gain in terms of exponent with respect to independent identically distributed codebooks.

This paper considers insertion and deletion channels with the additional assumption that the channel input sequence is implicitly divided into segments such that at most one edit can occur within a segment. No segment markers are available in the received sequence. We propose code constructions for the segmented deletion, segmented insertion, and segmented insertion-deletion channels based on subsets of Varshamov- Tenengolts codes chosen with predetermined prefixes and/or suffixes. The proposed codes, constructed for any finite alphabet, are zero error and can be decoded segment by segment. We also derive an upper bound on the rate of any zero-error code for the segmented edit channel, in terms of the segment length. This upper bound shows that the rate scaling of the proposed codes as the segment length increases is the same as that of the maximal code.

This paper studies channel coding for the discrete memoryless multiple-access channel with a given (possibly suboptimal) decoding rule. A multi-letter successive decoding rule depending on an arbitrary non-negative decoding metric is considered, and achievable rate regions and error exponents are derived both for the standard MAC (independent codebooks), and for the cognitive MAC (one user knows both messages) with superposition coding. In the cognitive case, the rate region and error exponent are shown to be tight with respect to the ensemble average. The rate regions are compared with those of the commonly considered decoder that chooses the message pair maximizing the decoding metric, and numerical examples are given for which successive decoding yields a strictly higher sum rate for a given pair of input distributions.

We consider insertion and deletion channels with the additional assumption that the channel input sequence is implicitly divided into segments such that at most one edit can occur within a segment. We further assume that there are no segment markers in the received sequence. We propose code constructions for the segmented deletion, segmented insertion, and segmented insertion-deletion channels based on subsets of VT codes chosen with pre-determined prefixes and/or suffixes. The proposed codes are zero-error, can be decoded segment-by-segment, and their rate scaling as the segment length increases is the same as that of the maximal code.

This paper provides an asymptotic expansion of the error probability, as the codeword length n goes to infinity, in quasi-static binary symmetric channels. After the leading term, namely the outage probability, the next two terms are found to be proportional to and respectively. Explicit characterizations of the respective coefficients are given. The resulting expansion gives an approximation to the random-coding union bound, accurate even at small codeword lengths.

This paper derives an achievable random-coding error exponent for joint source-channel coding over a multiple access channel with correlated sources. The codebooks are generated by drawing codewords from a multi-letter distribution that depends on the composition of the source message.

This paper studies expurgated random-coding bounds and error exponents for joint source-channel coding (JSCC). We extend Gallager's expurgation techniques for channel coding to the JSCC setting, and derive a non-asymptotic bound that recovers two exponents derived by Csiszár using the method of types. Our approach has the notable advantage of being directly applicable to channels with continuous alphabets.

A coding scheme is proposed for synchronization from a small number of deletions via a one-way error-free link. The scheme is based on multiple layers of Varshamov-Tenengolts codes combined with off-the-shelf linear error-correcting codes.

This paper studies the random-coding union (RCU) bound to the error probability in quasi-static fading channels. An asymptotic expansion and a normal approximation to the RCU bound suggest that the error probability converges to the outage probability as 1/n, where n is the codeword blocklength. We particularize our results for Rayleigh fading, and compare them with the conventional normal approximation.

This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases.

This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth's achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth's achievable rate region is given, and the latter is shown to immediately extend to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters.

Two alternative exact characterizations of the minimum error probability of Bayesian M-ary hypothesis testing are derived. The first expression corresponds to the error probability of an induced binary hypothesis test and implies the tightness of the meta-converse bound by Polyanskiy et al.; the second expression is a function of an information-spectrum measure and implies the tightness of a generalized Verdú-Han lower bound. The formulas characterize the minimum error probability of several problems in information theory and help to identify the steps where existing converse bounds are loose.

The performance of the original successive cancellation decoder of short-length polar codes is inferior to that of the maximum-likelihood decoder. Existing sphere decoding algorithms of polar codes have a high computational complexity even for short lengths. This is because, when exploring the tree defined by the generator matrix of the code, existing algorithms employ loose branching conditions and end up visiting many more nodes than needed. We propose improved branching conditions that significantly reduce the search complexity. A simple example reports an improvement of two orders of magnitude at Ebover N0= 4 dB compared to the standard sphere decoders.

This paper shows that bit-interleaved coded modulation (BICM) over the Gaussian channel can achieve information rates larger than the so-called BICM capacity. For some labelings the improvement with respect to the BICM capacity is significant, especially at low and medium signal-to-noise ratios (SNR). Specifically, natural binary labeling is found to be both first- and second-order optimal at low SNR.

This paper studies likelihood decoding for channel coding over discrete memoryless channels. It is shown that the likelihood decoder recovers the same random-coding error exponents as the maximum-likelihood decoder for i.i.d. and constant-composition random codes. The role of mismatch in likelihood decoding is studied, and the notion of the mismatched likelihood decoder capacity is introduced. It is shown, both in the case of random coding and optimized codebooks, that the mismatched likelihood decoder can lead to strictly worse achievable rates and error exponents compared to the corresponding mismatched maximum-metric decoder.

This paper studies the fixed-error asymptotics of constant-composition codes for discrete memoryless channels. An achievable asymptotic expansion is derived with a third-order term that can be as high as 1/2 log n, while being lower when (i) a certain feasibility-decoding condition fails, or (ii) the channel is a sum channel. Converse bounds are used to provide conditions under which each of these losses is unavoidable.

We derive the channel-coding sphere-packing exponent under a per-codeword cost constraint. The proof is based on hypothesis testing and holds for continuous memoryless channels.

The asynchronous-communication model is studied by means of i.i.d. codes and ML decoding. A random-coding bound to the joint probability of decoding and synchronization error is determined and used to recover the region of achievable information rates and asynchrony exponents.

This paper studies the second-order asymptotics of coding rates for the discrete memoryless multiple-access channel (MAC) with a fixed target error probability. Using constant-composition random coding, coded time-sharing, and a variant of Hoeffding's combinatorial central limit theorem, an inner bound on the set of locally achievable second-order coding rates is given for each point on the boundary of the capacity region. It is shown that the inner bound for constant-composition random coding includes that recovered by independent identically distributed random coding, and that the inclusion may be strict. The inner bound is extended to the Gaussian MAC via an increasingly fine quantization of the inputs.

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.

We study a source-channel coding scheme in which source messages are assigned to classes and encoded using a channel code that depends on the class index. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding as the number of classes increases. The performance of this scheme is studied by means of random-coding bounds and validated by simulation of a low-complexity implementation using existing source and channel codes.

The bit-channels of finite-length polar codes are not fully polarized, and a proportion of such bit-channels are neither completely “noiseless” nor completely “noisy”. By using an outer low-density parity-check code for these intermediate channels, we show how the performance of belief propagation (BP) decoding of the overall concatenated polar code can be improved. A simple example reports an improvement in Ebover N0of 0.3 dB with respect to the conventional BP decoder.

This paper presents a saddlepoint approximation of the random-coding union bound of Polyanskiy et al. for i.i.d. random coding over discrete memoryless channels. The approximation is single-letter, and can thus be computed efficiently. Moreover, it is shown to be asymptotically tight for both fixed and varying rates, unifying existing achievability results in the regimes of error exponents, second-order coding rates, and moderate deviations. For fixed rates, novel exact-asymptotics expressions are specified to within a multiplicative 1+o(1) term. A numerical example is provided for which the approximation is remarkably accurate even at short block lengths.

This paper studies channel coding for the discrete memoryless multiple-access channel with a given (possibly suboptimal) decoding rule. A multi-letter successive decoding rule depending on an arbitrary non-negative decoding metric is considered, and achievable rate regions and error exponents are derived both for the standard MAC (independent codebooks), and for the cognitive MAC (one user knows both messages) with superposition coding. In the cognitive case, the rate region and error exponent are shown to be tight with respect to the ensemble average. The rate regions are compared with those of the commonly considered decoder that chooses the message pair maximizing the decoding metric, and numerical examples are given for which successive decoding yields a strictly higher sum rate for a given pair of input distributions.

We study transmission over multiple-input multiple-output block-fading channels with imperfect channel state information (CSI) at both the transmitter and receiver. In particular, based on mismatched decoding theory for a fixed channel realization, we investigate the largest achievable rates with independent and identically distributed inputs and the nearest neighbor decoder. We then study the corresponding information outage probability in the high signal-to-noise ratio (SNR) regime and analyze the interplay between estimation error variances at the transmitter and receiver to determine the optimal outage exponent, defined as the high-SNR slope of the outage probability plotted in a logarithmic-logarithmic scale against the SNR. We demonstrate that despite operating with imperfect CSI, power adaptation can offer substantial gains in terms of outage exponent.

This paper studies the random-coding exponent of joint source-channel coding for a scheme where source messages are assigned to disjoint subsets (referred to as classes), and codewords are independently generated according to a distribution that depends on the class index of the source message. For discrete memoryless systems, two optimally chosen classes and product distributions are found to be sufficient to attain the sphere-packing exponent in those cases where it is tight.

This paper considers the problem of channel coding with a given (possibly suboptimal) maximum-metric decoding rule. A cost-constrained random-coding ensemble with multiple auxiliary costs is introduced, and is shown to achieve error exponents and second-order coding rates matching those of constant-composition random coding, while being directly applicable to channels with infinite or continuous alphabets. The number of auxiliary costs required to match the error exponents and second-order rates of constant-composition coding is studied, and is shown to be at most two. For independent identically distributed random coding, asymptotic estimates of two well-known non-asymptotic bounds are given using saddlepoint approximations. Each expression is shown to characterize the asymptotic behavior of the corresponding random-coding bound at both fixed and varying rates, thus unifying the regimes characterized by error exponents, second-order rates, and moderate deviations. For fixed rates, novel exact asymptotics expressions are obtained to within a multiplicative 1+o(1) term. Using numerical examples, it is shown that the saddlepoint approximations are highly accurate even at short block lengths.

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 study transmission over multiple-antenna block-fading channels with imperfect channel state information at both the transmitter and receiver. Specifically, we investigate achievable rates based on the generalized mutual information. We then analyze the corresponding outage probability in the high signal-to-noise ratio regime.

We study a family of polar codes whose frozen set is such that it discards the bit channels for which the mutual information falls below a certain (fixed) threshold. We show that if the threshold, which might depend on the code length, is bounded appropriately, a coding theorem can be proved for the underlying polar code. We also give accurate closed-form upper and lower bounds to the minimum distance of the resulting code when the design channel is the binary erasure channel.

Mismatched decoding theory is applied to study the error exponents (both random-coding and expurgated) and achievable rates for bit-interleaved coded modulation (BICM). The gains achieved by constant-composition codes with respect to the the usual random codes are highlighted.

An achievable rate is given for discrete memoryless channels with a given (possibly suboptimal) decoding rule. The result is obtained using a refinement of the superposition coding ensemble. The rate is tight with respect to the ensemble average, and can be weakened to the LM rate of Hui and Csiszár-Körner, and to Lapidoth's rate based on parallel codebooks.

This paper considers channel coding for the memoryless multiple-access channel with a given (possibly suboptimal) decoding rule. Non-asymptotic bounds on the error probability are given, and a cost-constrained random-coding ensemble is used to obtain an achievable error exponent. The achievable rate region recovered by the error exponent coincides with that of Lapidoth in the discrete memoryless case, and remains valid for more general alphabets.

We show that the meta-converse bound derived by Polyanskiy et al. provides the exact error probability for a fixed joint source-channel code and an appropriate choice of the bound parameters. While the expression is not computable in general, it identifies the weaknesses of known converse bounds to the minimum achievable error probability.

This paper determines the range of feasible values of standard error exponents for binary-input memoryless symmetric channels of fixed capacity$C$and shows that extremes are attained by the binary symmetric and the binary erasure channel. The proof technique also provides analogous extremes for other quantities related to Gallager's$E_{0}$function, such as the cutoff rate, the Bhattacharyya parameter, and the channel dispersion.

We derive a random-coding upper bound on the average probability of error of joint source-channel coding that recovers Csiszár's error exponent when used with product distributions over the channel inputs. Our proof technique for the error probability analysis employs a code construction for which source messages are assigned to subsets and codewords are generated with a distribution that depends on the subset.

We determine the loss in capacity incurred by using signal constellations with a bounded support over general complex-valued additive-noise channels for suitably high signal-to-noise ratio. Our expression for the capacity loss recovers the power loss of 1.53dB for square signal constellations.

We consider bit-interleaved coded modulation (BICM) schemes where, instead of the true bit or symbol probabilities and the constellation used at the transmitter, the decoder uses arbitrary probabilities or reference constellations. We study the corresponding low- and high- signal-to-noise-ratio regimes and show that even in the presence of this extra sources of mismatch, BICM has a negligible penalty with respect to coded modulation.

This paper studies communication outages in multiple-input multiple-output (MIMO) block-fading channels with imperfect channel state information at the receiver (CSIR). Using mismatched decoding error exponents, we prove the achievability of the generalized outage probability, the probability that the generalized mutual information (GMI) is less than the data rate, and show that this probability is the fundamental limit for independent and identically distributed (i.i.d.) codebooks. Then, using nearest neighbor decoding, we study the generalized outage probability in the high signal-to-noise ratio (SNR) regime for random codes with Gaussian and discrete signal constellations. In particular, we study the SNR exponent, which is defined as the high-SNR slope of the error probability curve on a logarithmic-logarithmic scale. We show that the maximum achievable SNR exponent of the imperfect CSIR case is given by the SNR exponent of the perfect CSIR case times the minimum of one and the channel estimation error diversity. Random codes with Gaussian constellations achieve the optimal SNR exponent with finite block length as long as the block length is larger than a threshold. On the other hand, random codes with discrete constellations achieve the optimal SNR exponent with block length growing with the logarithm of the SNR. The results hold for many fading distributions, including Rayleigh, Rician, Nakagami-$m$, Nakagami-$q$and Weibull as well as for optical wireless scintillation distributions such as lognormal-Rice and gamma-gamma.

This paper studies the asymptotic outage performance of incremental redundancy automatic-repeat-request (INR-ARQ) transmission over multiple-input multiple-output (MIMO) block-fading channels with discrete input constellations. We first show that transmission with random codes using a discrete signal constellation across all transmit antennas achieves the optimal outage diversity given by the Singleton bound. The optimal SNR-exponent and outage diversity of INR-ARQ transmission over the MIMO block-fading channel are then analysed. We show that a significant gain in outage diversity is obtained by providing more than one bit feedback at each ARQ round. Thus, the outage performance of INR-ARQ transmission can be remarkably improved with minimal additional overhead. A practical feedback-and-power-adaptation rule is proposed for MIMO INR-ARQ, demonstrating the benefits provided by multibit feedback. Although the rule is sub-optimal in terms of outage performance, it achieves the optimal outage diversity.

We study block-fading channels where both transmitter and receiver do not know the actual channel state information (CSI) but they have access to a noisy version. We study the interplay between estimation error variances at the transmitter and at the receiver to give the optimal outage exponents. We also demonstrate that achieving a reliable channel estimate at the receiver is more important than obtaining a reliable channel state information at the transmitter in terms of outage exponent.

We study the information rates of non-coherent, stationary, Gaussian, multiple-input multiple-output (MIMO) flat-fading channels that are achievable with nearest neighbour decoding and pilot-aided channel estimation. In particular, we analyse the behaviour of these achievable rates in the limit as the signal-to-noise ratio (SNR) tends to infinity. We demonstrate that nearest neighbour decoding and pilot-aided channel estimation achieves the capacity pre-log-which is defined as the limiting ratio of the capacity to the logarithm of SNR as the SNR tends to infinity-of non-coherent multiple-input single-output (MISO) flat-fading channels, and it achieves the best so far known lower bound on the capacity pre-log of non-coherent MIMO flat-fading channels.

Random-coding exact characterizations and bounds to the error probability of joint source-channel coding are presented. In particular, upper bounds using maximum-a-posteriori and threshold decoding are derived as well as a lower bound motivated by Verdú-Han's lemma.

We show that Gallager's random coding error exponent of an arbitrary binary-input memoryless symmetric channel is upper-bounded by that of the binary erasure channel and lower-bounded by that of the binary-symmetric channel of the same capacity. We apply the result to find the extremes of the channel dispersion for the aforementioned class of channels.

This paper considers random-coding bounds to the decoding error probability with threshold decoders. A slightly improved version of the dependence-testing bound is derived. A loosening of this bound generates a family of Feinstein-like bounds, which improve on Feinstein's original version. The error exponents of these bounds are determined and simple, yet accurate, saddlepoint approximations to the corresponding error probabilities are derived.

We study the error probability of LDPC codes in delay-limited block-fading channels with channel state information (CSI) at the transmitter and the receiver. We derive the optimal power allocation algorithms for LDPC codes with specific degree distributions using multi-edge-type density evolution error boundaries. The resulting performance approaches the outage probability for a number of power constraints. Furthermore, we adapt the algorithm for finite-length codes and show that the proposed algorithm enables gains larger than 10 dB over uniform power allocation. The method is valid for general, possibly correlated, fading distributions. This represents the first analysis of specific LDPC codes over block-fading channels with full CSI.

We analyze multiuser detection under the assumption that the number of users accessing the channel is unknown by the receiver. In this environment, users' activity must be estimated along with any other parameters such as data, power, and location. Our main goal is to determine the performance loss caused by the need for estimating the identities of active users, which are not known a priori. To prevent a loss of optimality, we assume that identities and data are estimated jointly, rather than in two separate steps. We examine the performance of multiuser detectors when the number of potential users is large. Statistical-physics methodologies are used to determine the macroscopic performance of the detector in terms of its multiuser efficiency. Special attention is paid to the fixed-point equation whose solution yields the multiuser efficiency of the optimal (maximum a posteriori) detector in the large signal-to-noise ratio regime. Our analysis yields closed-form approximate bounds to the minimum mean-squared error in this regime. These illustrate the set of solutions of the fixed-point equation, and their relationship with the maximum system load. Next, we study the maximum load that the detector can support for a given quality of service specified by error probability.

We study iterative multiuser joint decoding in large randomly spread code division multiple access systems under the assumption that the number of users accessing the channel is unknown by the receiver. In particular, we focus on the factor graph representation and iterative algorithms based on belief propagation. We study a suboptimal iterative scheme that jointly detects the encoded data and the users' activity. By using the replica method from statistical physics, we analyze the performance of the iterative detector. Using density evolution, we provide a fixed-point equation of the overall iterative system where the probability messages depend on the users' activity. Finally, when the scaling between the log number of users and the block length is below a threshold, we show that in the large-system limit a simple structure on the users' codes yields a multiuser efficiency fixed-point equation that is equivalent to the case of all-active users with a system load scaled by the activity rate.

We study irregular binary turbo codes over nonergodic block-fading channels. We first propose an extension of channel multiplexers initially designed for regular turbo codes. We then show that, using these multiplexers, irregular turbo codes that exhibit a small decoding threshold over the ergodic Gaussian-noise channel perform very close to the outage probability on block-fading channels, from both density evolution and finite-length perspectives.

We study hybrid free-space optical (FSO) and radio-frequency (RF) communications, whereby information is conveyed simultaneously using both optical and RF carriers. We consider the case where both carriers experience scintillation, which is a slow fading process compared to typical data rates. A parallel block-fading channel model is proposed, that incorporates differences in signalling rates, power scaling and scintillation models between the two carriers. Under this framework, we study the outage probability in the large signal-to-noise ratio (SNR) regime. First we consider the case when only the receiver has perfect channel state information (CSIR case) and obtain the SNR exponent for general scintillation distributions. Then we consider the case when perfect CSI is known at both the receiver and transmitter, and derive the optimal power allocation strategy that minimises the outage probability subject to peak and average power constraints. The optimal solution involves non-convex optimisation, which is intractable in practical systems. We therefore propose a suboptimal algorithm that achieves the same diversity as the optimal one and provides significant power savings (on the order of tens of dBs) over uniform allocation.

We study the outage diversity of the multiple-input multiple-output (MIMO) Rayleigh block-fading channel when causal channel state information (CSI) is available at the transmitter (CSIT). Within this setting, we consider the optimal power allocation for blocks b = 1, ..., B given perfect CSIT for blocks 1, ..., b-u only, subject to a long-term power constraint. The parameter 0 ≤ u ≤ B is a fixed arbitrary integer that determines the delay in acquiring perfect knowledge of the CSI at the transmitter. Without explicitly solving the optimal power allocation problem, we derive the outage diversity of the system. For general 0 ≤ u ≤ B, we derive a simple recursive expression for computing the outage diversity. For the special case u = 0, it is shown that the outage diversity is infinite, coinciding with previously known results. For 1 ≤ u ≤ B, the outage diversity becomes finite and for the special case of u = 1, 2 it can be expressed in simple closed form.

We study analogue source transmission over MIMO block-fading channels with receiver-only channel state information. Unlike previous work which considers the end-to-end expected distortion as a figure of merit, we study the distortion outage probability. We first consider the well known transmitter informed bound, which yields a benchmark lower bound to the distortion outage probability of any coding scheme. We next compare the results with source-channel separation. The key difference from the expected distortion approach is that if the channel code rate is chosen appropriately, source-channel separation can not only achieve the same diversity exponent, but also the same distortion outage probability as the transmitter informed lower bound.

This paper presents the outage analysis of multiple-input multiple-output (MIMO) block-fading channels with nearest neighbour decoding and mismatched channel state information at the receiver (CSIR). Based on mismatched decoding arguments, we demonstrate the achievability of the generalised outage probability, the probability that the generalised mutual information (GMI) is less than the target data rate, and show that this probability is the fundamental limit for independent and identically distributed (i.i.d.) codebooks. We then analyse the behaviour of the generalised outage probability at high signal-to-noise ratio (SNR) regime. For both Gaussian and discrete signal codebooks, we provide a simple characterisation of the mismatched CSIR SNR exponents and derive the necessary condition on the block length to achieve those SNR exponents.

We investigate the effects of imperfect channel knowledge and feedback in incremental-redundancy automatic-repeat request (INR-ARQ) coding systems over multiple-input multiple-output (MIMO) block-fading channels. We propose an ARQ decoder based on nearest neighbour decoding and evaluate the corresponding achievable rates. We then derive the optimal code diversity assuming that the feedback channel is modelled as a binary symmetric channel. Our main results show that the feedback link reliability must improve with the forward (transmission) signal-to-noise ratio (SNR) for the code to exploit the diversity offered by ARQ scheme. We also identify the conditions for achieving full diversity and for ARQ not helping in improving the system's diversity.

The performance of bit-interleaved coded modulation (BICM) with shaping (i.e., non-equiprobable bit probabilities) is studied. For the AWGN channel, the rates achievable with BICM and shaping are practically identical to those of coded modulation or multilevel coding, virtually closing the gap that made BICM suboptimal in terms of information rates.

In the above titled paper (ibid., vol. 54, no. 12, pp. 5447-5455, Dec. 08), there are three errors that are corrected here.

We design powerful low-density parity-check (LDPC) codes with iterative decoding for the block-fading channel. We first study the case of maximum-likelihood decoding, and show that the design criterion is rather straightforward. Since optimal constructions for maximum-likelihood decoding do not perform well under iterative decoding, we introduce a new family of full-diversity LDPC codes that exhibit near-outage-limit performance under iterative decoding for all block-lengths. This family competes favorably with multiplexed parallel turbo codes for nonergodic channels.

Reliable communication over delay-constrained multiple-input multiple-output (MIMO) block-fading channels with discrete inputs and mismatched (imperfect) channel state information at the transmitter (CSIT) is studied. The CSIT mismatch is modeled as Gaussian random variables, whose variances decay as a power of the signal-to-noise ratio (SNR). A special focus is placed on the large-SNR decay of the error and outage probabilities when power control with long-term power constraints is used. Without explicitly characterizing the corresponding power allocation algorithms, we derive the outage exponent as a function of the system parameters, including the CSIT noise variance exponent and the exponent of the peak power constraint. It is shown that CSIT, even if noisy, is always beneficial and leads to important gains in terms of exponents.

Power allocation is studied for fixed-rate transmission over block-fading channels with arbitrary continuous fading distributions and perfect transmitter and receiver channel state information. Both short- and long-term power constraints for arbitrary input distributions are considered. Optimal power allocation schemes are shown to be direct applications of previous results in the literature. It is shown that the short- and long-term outage exponents for arbitrary input distributions are related through a simple formula. The formula is useful to predict when the delay-limited capacity is positive. Furthermore, this characterization is useful for the design of efficient coding schemes for this relevant channel model.

Communication over delay-constrained block-fading channels with discrete inputs and imperfect channel state information at the transmitter (CSIT) is studied. The CSIT mismatch is modeled as a Gaussian random variable, whose variance decays as a power of the signal-to-noise ratio (SNR). We focus on the large-SNR behavior of the outage probability when transmit power control is used. We derive the outage exponent as a function of the system parameters, including the CSIT noise variance exponent and the exponent of the peak power constraint. It is shown that CSIT, even if noisy, is always beneficial and leads to significant gains in terms of exponents. It is also shown that when precoders are used at the transmitter, further exponent gains can be attained at the expense of higher decoding complexity.

This paper studies the average error probability of bit-interleaved coded modulation with uniform interleaving in fully-interleaved fading channels. At large signal-to-noise ratio, the dominant pairwise error events are mapped into symbols with Hamming weight larger than one, causing a flattening of the error probability. Closed-form expressions for the error probability with general modulations are provided. For interleavers of practical length, the flattening is noticeable only at very low values of the error probability.

We consider improving the outage performance of incremental-redundancy automatic repeat request (INR-ARQ) transmission over the multiple-input multiple-output (MIMO) block-fading channel by allowing multi-bit receiver feedback. We show that multi-bit feedback offers significant gain in outage diversity when power adaptation is employed. A suboptimal feedback and power adaptation rule is proposed, illustrating the benefits provided by multi-bit feedback.

We study the hybrid free-space optical (FSO) and radio-frequency (RF) channel from an information theoretic perspective. Since both links operate at vastly different carrier frequencies, we model the hybrid channel as a pair of parallel channels. Moreover, since the FSO channel signals at a higher rate than the RF channel, we incorporate this key feature in the parallel channel model. Both channels experience fading due to scintillation, which is slow compared to typical signalling rates. Under this framework, we study the fundamental limits of the hybrid channel. In particular, we analyse the outage probability in the large signal-to-noise ratio (SNR) regime, and obtain the outage diversity or SNR exponent of the hybrid system. First we consider the case when only the receiver has perfect channel state information (CSIR case), and obtain the exponents for general scintillation distributions. These exponents relate key system design parameters to the asymptotic outage performance and illustrate the benefits of using hybrid systems with respect to independent FSO or RF links. We next consider the case when perfect CSI is known at both the receiver and transmitter, and derive the optimal power allocation strategy that minimises the outage probability subject to peak and average power constraints. The optimal solution involves non-convex optimisation, which is intractable in practical systems. We therefore propose a suboptimal algorithm that achieves significant power savings (on the order of tens of dBs) over uniform power allocation. We show that the suboptimal algorithm has the same diversity as the optimal power allocation strategy.

We study the asymptotic outage probability of multiple-input multiple-output free-space optical communication with pulse-position modulation. In particular, we consider doubly stochastic scintillation models, lognormal-Rice and I-K distributions. First we consider the case when channel state information is available at the receiver only. Then we consider the case when it is also available at the transmitter.

Atmospheric effects can significantly degrade the reliability of free-space optical communications. One such effect is scintillation, caused by atmospheric turbulence, refers to random fluctuations in the irradiance and phase of the received laser beam. In this paper we investigate the use of multiple lasers and multiple apertures to mitigate scintillation. Since the scintillation process is slow, we adopt a block fading channel model and study the outage probability under the assumptions of orthogonal pulse-position modulation and non-ideal photodetection. Assuming perfect receiver channel state information (CSI), we derive the signal-to-noise ratio (SNR) exponents for the cases when the scintillation is lognormal, exponential and gamma-gamma distributed, which cover a wide range of atmospheric turbulence conditions. Furthermore, when CSI is also available at the transmitter, we illustrate very large gains in SNR are possible (in some cases larger than 15 dB) by adapting the transmitted power. Under a long-term power constraint, we outline fundamental design criteria via a simple expression that relates the required number of lasers and apertures for a given code rate and number of codeword blocks to completely remove system outages.

We revisit the information-theoretic analysis of bit-interleaved coded modulation (BICM) by modeling the BICM decoder as a mismatched decoder. The mismatched decoding model is well defined for finite, yet arbitrary, block lengths, and naturally captures the channel memory among the bits belonging to the same symbol. We give two independent proofs of the achievability of the BICM capacity calculated by Caire, where BICM was modeled as a set of independent parallel binary-input channels whose output is the bitwise log-likelihood ratio. Our first achievability proof uses typical sequences, and shows that due to the random coding construction, the interleaver is not required. The second proof is based on the random coding error exponents with mismatched decoding, where the largest achievable rate is the generalized mutual information. Moreover, the generalized mutual information of the mismatched decoder coincides with the infinite-interleaver BICM capacity. We show that the error exponent—and hence the cutoff rate—of the BICM mismatched decoder is upper-bounded by that of coded modulation and may thus be lower than in the infinite-interleaved model; for binary reflected Gray mapping in Gaussian channels the loss in error exponent is small. We also consider the mutual information appearing in the analysis of iterative decoding of BICM with extrinsic information transfer (EXIT) charts: if the symbol metric has knowledge of the transmitted symbol, EXIT mutual information admits a representation as a pseudo-generalized mutual information, which is in general not achievable. A different symbol decoding metric, for which the extrinsic side information refers to the hypothesized symbol, induces a generalized mutual information lower than the coded modulation capacity. In this case, perfect extrinsic side information turns the mismatched-decoder error exponent into that of coded modulation.

This paper studies the average error probability of bit-interleaved coded modulation with uniform interleaving in fully-interleaved fading channels. At large signal-to-noise ratio, the dominant pairwise error events are mapped into symbols with Hamming weight larger than one, causing a flattening of the error probability. Closed-form expressions for the error probability with general modulations are provided. For interleavers of practical length, the flattening is noticeable only at very low values of the error probability.

We consider power allocation strategies for arbitrary input channels with peak, average and peak-to-average power ratio (PAPR) constraints. We are focusing on systems with a fixed and finite input constellation, as encountered in most practical systems. Generalizing previous results, we derive the optimal power allocation scheme that minimizes the outage probability of block-fading channels with arbitrary input constellations, subject to PAPR constraints. We further show that the signal-to-noise ratio exponent for any finite peak-to-average power ratio is the same as that of the peak-power limited problem, resulting in an error floor. We also derive the optimal power allocation strategies that maximize the ergodic capacity for arbitrary input channels, subject to average and PAPR constraints.We show that capacities with peak-to-average power ratio constraints, even for small ratios, are close to capacities without peak-power restrictions. For both delay-limited and ergodic block-fading channels, the optimal power allocation strategies rely on the first derivative of the input-output mutual information, which may be computationally prohibitive for efficient practical implementation. To overcome this limitation, we develop suboptimal power allocation schemes that resemble the traditional water-filling technique. The suboptimal power allocation schemes significantly reduce computational and storage requirements, while enjoying minimal performance losses as compared to optimal schemes.

A new graph-based construction of generalized low density codes (GLD-Tanner) with binary BCH constituents is described. The proposed family of GLD codes is optimal on block erasure channels and quasi-optimal on block fading channels. Optimality is considered in the outage probability sense. A classical GLD code for ergodic channels (e.g., the AWGN channel, the i.i.d. Rayleigh fading channel, and the i.i.d. binary erasure channel) is built by connecting bitnodes and subcode nodes via a unique random edge permutation. In the proposed construction of full-diversity GLD codes (referred to as root GLD), bitnodes are divided into 4 classes, subcodes are divided into 2 classes, and finally both sides of the Tanner graph are linked via 4 random edge permutations. The study focuses on non-ergodic channels with two states and can be easily extended to channels with 3 states or more.

The main drawback in communicating via the free-space optical channel is the detrimental effect the atmosphere has on a propagating laser beam. Atmospheric turbulence causes random fluctuations in the irradiance of the received laser beam, commonly referred to as scintillation. We investigate the mitigation of scintillation through the use of multiple lasers and multiple apertures, thereby creating a multiple-input multiple output (MIMO) channel. We adopt a quasi-static block fading model and study the outage probability of the channel under the assumption of orthogonal pulse-position modulation. Non-ideal photodetection is also assumed such that the combined shot noise and thermal noise are considered as signal-independent additive Gaussian white noise. Assuming perfect receiver channel state information (CSI), we compute the signal-to-noise ratio exponents for the cases when the scintillation is lognormal, exponential and gamma-gamma distributed, which cover a wide range of atmospheric turbulence conditions. Furthermore, we illustrate very large gains when CSI is also available at the transmitter.

We revisit the information-theoretic analysis of bit-interleaved coded modulation (BICM) by modeling the BICM decoder as a mismatched decoder. The mismatched-decoding model is well-defined for finite, yet arbitrary, block lengths, and captures the channel memory among the bits belonging to the same symbol. The generalized mutual information of the mismatched decoder coincides with the infinite-interleaver BICM capacity, where BICM is modeled as a set of independent parallel binary-input channels whose output is the bitwise log-likelihood ratio. The error exponent —and hence the cutoff rate— of the BICM mismatched decoder is upper bounded by that of coded modulation and may thus be lower than in the infinite-interleaved model. For binary reflected Gray mapping in Gaussian channels the loss in error exponent is small.

Power allocation with peak-to-average power constraints over Nakagami-m block-fading channels with arbitrary input distributions is studied. In particular, we find the solution to the minimum outage power allocation scheme with peak-to-average power constraints and arbitrary input distributions, and show that the signal-to-noise ratio exponent for any systems with a finite peak-to-average power ratio constraint is the same as that of systems with peak-power constraints, resulting in an error floor.

We characterize the asymptotic outage performance of power allocation techniques for systems with average power constraints. We show that the outage diversity of a system with average power constraints can be obtained from the diversity of the corresponding system with peak power constraints. The characterization is therefore useful since the asymptotic performance of systems with peak power constraints is well known in the literature.

We show how to build full-diversity product codes under both iterative encoding and decoding over non-ergodic channels, in presence of block erasure and block fading. The concept of a rootcheck or a root subcode is introduced by generalizing the same principle recently invented for low-density parity-check codes. We also describe some channel related graphical properties of the new family of product codes, a family referred to as root product codes.

In this paper, we consider an automatic-repeat-request (ARQ) retransmission protocol signaling over a block-fading multiple-input–multiple-output (MIMO) channel. Unlike previous work, we allow for multiple fading blocks within each transmission (ARQ round), and we constrain the transmitter to fixed rate codes constructed over complex signal constellations. In particular, we examine the general case of average input-power-constrained constellations with a fixed signaling alphabet of finite cardinality. This scenario is a suitable model for practical wireless communications systems employing orthogonal frequency division multiplexing (OFDM) techniques over a MIMO ARQ channel. Two cases of fading dynamics are considered, namely, short-term static fading where channel fading gains change randomly for each ARQ round, and long-term static fading where channel fading gains remain constant over all ARQ rounds pertaining to a given message. As our main result, we prove that for the block-fading MIMO ARQ channel with a fixed signaling alphabet satisfying a short-term power constraint, the optimal signal-to-noise ratio (SNR) exponent is given by a modified Singleton bound, relating all the system parameters. To demonstrate the practical significance of the theoretical analysis, we present numerical results showing that practical Singleton-bound-achieving maximum distance separable codes achieve the optimal SNR exponent.

We study coded modulation over multidimensional signal sets in Nakagami-m block-fading channels. We consider the optimal diversity reliability exponent of the error probability when the multidimensional constellation is obtained as the rotation of complex-plane signal constellations. We show that multidimensional rotations of full dimension achieve the optimal diversity reliability exponent, also achieved by Gaussian constellations. Rotations of full dimension induce a large decoding complexity, and in some cases it might be beneficial to use multiple rotations of smaller dimension. We also study the diversity reliability exponent in this case, which yields the optimal rate-diversity-complexity tradeoff in block-fading channels with discrete inputs.

The wideband regime of bit-interleaved coded modulation (BICM) in Gaussian channels is studied. The Taylor expansion of the coded modulation capacity for generic signal constellations at low signal-to-noise ratio (SNR) is derived and used to determine the corresponding expansion for the BICM capacity. Simple formulas for the minimum energy per bit and the wideband slope are given. BICM is found to be suboptimal in the sense that its minimum energy per bit can be larger than the corresponding value for coded modulation schemes. The minimum energy per bit using standard Gray mapping on$M$-PAM or$M^2$-QAM is given by a simple formula and shown to approach${-}$0.34 dB as$M$increases. Using the low SNR expansion, a general tradeoff between power and bandwidth in the wideband regime is used to show how a power loss can be traded off against a bandwidth gain.

We study the error probability performance of rotated lattice constellations in frequency-flat Nakagami-m block-fading channels. In particular, we use the sphere lower bound on the underlying infinite lattice as a performance benchmark. We show that the sphere lower bound has full diversity. We observe that optimally rotated lattices with largest known minimum product distance perform very close to the lower bound, while the ensemble of random rotations is shown to lack diversity and perform far from it.

In this paper, we consider an automatic-repeat-request (ARQ) retransmission protocol signaling over a block-fading multiple-input, multiple-output (MIMO) channel. In particular, we consider fixed rate codes constructed over discrete complex signal constellations. We show that the optimal signal-to-noise ratio (SNR) exponent is given by a modified Singleton bound, relating all the system parameters. To demonstrate the practical significance of the theoretical analysis, we present numerical results showing that practical Singleton-bound-achieving maximum distance separable codes achieve the optimal SNR exponent.

We study the problem of constructing coded modulation schemes over multidimensional signal sets in Nakagami-m block-fading channels. In particular, we consider the optimal diversity reliability exponent of the error probability when the multidimensional constellation is obtained as the rotation of classical complex-plane signal constellations. We show that multidimensional rotations of full dimension achieve the optimal diversity reliability exponent, also achieved by Gaussian constellations. Multidimensional rotations of full dimension induce a large decoding complexity, and in some cases it might be beneficial to use multiple rotations of smaller dimension. We also study the diversity reliability exponent in this case, which yields the optimal rate-diversity-complexity tradeoff in block-fading channels with discrete inputs.

This paper studies the wideband regime of bit-interleaved coded modulation (BICM) in Gaussian channels. Simple formulas for the minimum energy per bit and the wideband slope, both for coded modulation and for bit-interleaved coded modulation, are given. The wideband slope can be decomposed into the product of two terms, respectively due to the fading characteristics and the modulation and binary labeling rule. BICM is found to be suboptimal in the sense that its minimum energy per bit can be larger than the corresponding value for coded modulation schemes. The minimum energy per bit using standard Gray mapping on M-PAM, or M2-QAM is given by a simple formula, and shown to approach -0.34 dB as M increases.

In this paper, we propose a tight lower bound to the outage probability of Nakagami-m block-fading channels. The approach permits an efficient method for numerical evaluation of the bound, providing an additional tool for system design. The optimal rate-diversity trade-off for the Nakagami-m block-fading channel is also derived and a tight upper bound is obtained for the optimal coding gain constant.

In this correspondence, a tight lower bound to the outage probability of discrete-input Nakagami-$m$block-fading channels is proposed. The approach permits an efficient method for numerical evaluation of the bound, providing an additional tool for system design. The optimal rate-diversity tradeoff for the Nakagami-$m$block-fading channel is also derived and a tight upper bound is obtained for the optimal coding gain constant.

The paper describes a curve-fitting approach for the design of capacity approaching coded modulation for orthogonal signal sets with non-coherent detection. In particular, bit-interleaved coded modulation with iterative decoding is considered. Decoder metrics are developed that do not require knowledge of the signal-to-noise ratio, yet still offer very good performance.

This letter presents a simple closed-form expression to evaluate the error probability of binary fully-interleaved fading channels. The proposed expression does not require a numerical Laplace transform inversion, numerical integration or similar techniques, and captures the role of the relevant system parameters in the overall error performance. The expression has the same asymptotic behavior as the Bhattacharyya (Chernoff)-union bound but closes the gap with the simulation results. Its precision is numerically validated for coded and uncoded transmission over generic Nakagami-m fading channels.

We study the error probability performance of rotated lattice constellations in frequency-flat block-fading channels. In particular, we use the sphere lower bound on the underlying infinite lattice as a performance benchmark. We show that the sphere lower bound has full diversity. We observe that optimally rotated lattices with largest known minimum product distance perform very close to the lower bound, while the ensemble of random rotations is shown to lack diversity and perform far from it. We furthermore use the bound in the multiple-antenna case, and we observe that the Golden code, the optimal full-rate full-diversity 2x2 space-time block code, is also very close to the lower bound.

New space-time trellis codes with 4-PSK and 8-PSK for two transmit antennas in slow fading channels are proposed in this paper. The codes are designed specifically to minimize the frame error probability. The performance of the proposed codes with various memory orders and receive antennas is evaluated by simulation. It is shown that the proposed codes outperform previously known codes1.

We consider coded modulation schemes for the block-fading channel. In the setting where a codeword spans a finite number N of fading degrees of freedom, we show that coded modulations of rate R bit per complex dimension, over a finite signal set /spl chi//spl sube//spl Copf/ of size 2/sup M/, achieve the optimal rate-diversity tradeoff given by the Singleton bound /spl delta/(N,M,R)=1+/spl lfloor/N(1-R/M)/spl rfloor/, for R/spl isin/(0,M/spl rfloor/. Furthermore, we show also that the popular bit-interleaved coded modulation achieves the same optimal rate-diversity tradeoff. We present a novel coded modulation construction based on blockwise concatenation that systematically yields Singleton-bound achieving turbo-like codes defined over an arbitrary signal set /spl chi//spl sub//spl Copf/. The proposed blockwise concatenation significantly outperforms conventional serial and parallel turbo codes in the block-fading channel. We analyze the ensemble average performance under maximum-likelihood (ML) decoding of the proposed codes by means of upper bounds and tight approximations. We show that, differently from the additive white Gaussian noise (AWGN) and fully interleaved fading cases, belief-propagation iterative decoding performs very close to ML on the block-fading channel for any signal-to-noise ratio (SNR) and even for relatively short block lengths. We also show that, at constant decoding complexity per information bit, the proposed codes perform close to the information outage probability for any block length, while standard block codes (e.g., obtained by trellis termination of convolutional codes) have a gap from outage that increases with the block length: this is a different and more subtle manifestation of the so-called "interleaving gain" of turbo codes.

In this correspondence, we study an$M$-ary block-erasure channel with$B$blocks, where with probability$epsilon $a block of$L$coded symbols is erased. The behavior of the error probability of coded systems over such channels is studied, and we show that, if the code is diversity-wise maximum-distance separable, its word error probability is equal to the outage probability, which admits a very simple expression. This correspondence is intended to complement the error probability analysis in previous work by Lapidoth and shed some light on the design of coding schemes for nonergodic channels.

This correspondence presents a simple method to accurately compute the error probability of bit-interleaved coded modulation (BICM). Thanks to the binary-input output-symmetric (BIOS) nature of the channel, the pairwise error probability (PEP) is equal to the tail probability of a sum of random variables with a particular distribution. This probability is in turn computed with a saddlepoint approximation. Its precision is numerically validated for coded transmission over standard Gaussian noise and fully interleaved fading channels for both convolutional and turbo-like codes.

This letter studies the effect of signal constellation expansion on the achievable diversity of pragmatic bit-interleaved space-time codes in quasistatic multiple antenna channels. Signal constellation expansion can be obtained either by increasing the size of the constellation in the complex plane or by using multidimensional linear mappings. By means of two simple constructions, we provide a comparison of the two options with message passing decoding. We show that multidimensional expansion achieves some performance advantage over complex-plane expansion at the cost of significantly higher decoding complexity and larger peak-to-average power ratio of the transmitted signals.

This paper investigates the performance of M-ary amplitude-phase shift keying (APSK) digital modulation over typical nonlinear satellite channels. The effect of the satellite nonlinearity is studied, and distortion pre- and post-compensation techniques for coded APSK are presented. Moreover, clock timing, signal amplitude and carrier phase recovery schemes are discussed. For the latter, a new class of non turbo decoder-aided closed-loop phase synchronizers featuring good performance and low complexity is studied. Finally, an end-to-end coded APSK system simulator inclusive of the satellite channel model and synchronization sub-systems is discussed and its performance compared to standard trellis-coded QAM concatenated with Reed-Solomon codes, showing a remarkable gain in both power and spectral efficiency. Coded APSK, recently selected for the new standard -DVB-S2- for digital video broadcasting and interactive broadband satellite services, is shown to represent a powerand spectral-efficient solution for satellite nonlinear channels.

This paper presents a general methodology to extend Gallager bounds on the maximum-likelihood decoding error probability to arbitrary binary-input output-symmetric memoryless channels. Based on the log-likelihood ratios, a new space is constructed in which the signals naturally lie on a sphere, and for which geometric analysis is straightforward. In particular, we focus on Poltyrev's tangential-sphere bound, and we illustrate its connections with the Engdahl-Zigangirov bound. Approximations to these bounds are shown to be very tight.

We consider the coded modulation family of block-wise concatenated codes (BCC). The blocks are separately interleaved and fed to binary inner encoders. Finally, the output of each component inner code is mapped onto a sequence of signal components by the modulator mapping. The proposed BCCs significantly outperform conventional serial and parallel turbo codes in the block-fading channel. Differently from the AWGN and fully-interleaved fading cases, iterative decoding performs very close to ML on the block-fading channel, even for relatively short block lengths. Moreover, at constant decoding complexity per information bit, BCCs are shown to be weakly good, while standard block codes obtained by trellis-termination of convolutional codes have a gap from outage that increases with the block length: this is a different and more subtle manifestation of the so-called "interleaving gain" of turbo-like codes.