We study the problem of zero-delay coding for the transmission of a Markov source over a noisy channel with feedback and present a reinforcement learning solution which is guaranteed to approach optimality. To this end, we formulate the problem as a Markov decision process (MDP) where the state is a probability-measure valued predictor/belief and the actions are quantizer maps. This MDP formulation has been used to show the optimality of certain classes of encoder policies in prior work, but their computation is prohibitively complex due to the uncountable nature of the constructed state space. Based on recent results for partially observed MDPs, we present an approximation of the belief MDP using a sliding finite window of channel outputs and quantizers. Under an appropriate notion of predictor stability, we show that the lowest distortion achievable by such a sliding finite window policy approaches the true lowest distortion as the window length increases. We give sufficient conditions for predictor stability to hold. Finally, we propose a Q-learning algorithm which provably converges to the optimal policy and provide a detailed comparison of the sliding finite window scheme with another approximation scheme which quantizes the belief MDP in a nearest neighbor fashion, as well as other coding schemes from the literature.

We study the problem of exact sampling under an exponential communication cost, specifically Campbell’s average codeword lengthL(t)of ordert[1], and Rényi’s entropy. We provide a lower bound on the Campbell cost of exact sampling that grows approximately asD1/α(P||Q), the Rényi divergence of order 1/α, with α = 1/1 +t. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound onL(t)whose leading Rényi divergence term has order within ϵ of that of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as α→1. We also provide numerical examples comparing the bounds in the cases of normal and Laplacian distributions, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other. Our results characterize exactly the optimal asymptotic Campbell costL(t)per sample as the number of independent and identically distributed (i.i.d.) samples grows to infinity. We show that under the exponential cost, any causal sampler performs strictly worse asymptotically than noncausal samplers. This contrasts with the case of expected message length, where both causal and noncausal samplers have the same optimal asymptotic cost.

We consider a two sensor distributed detection system transmitting a binary non-uniform source over a Gaussian multiple access channel (MAC). We model the network via binary sensors whose outputs are generated by binary symmetric channels of different noise levels. We prove an optimal one dimensional constellation design under individual sensor power constraints which minimizes the error probability of detecting the source. Three distinct cases arise for this optimization based on the parameters in the problem setup. In the most notable case (Case III), the optimal signaling design is to not necessarily use all of the power allocated to the more noisy sensor (with less correlation to the source). We compare the error performance of the optimal one dimensional constellation to orthogonal signaling. The results show that the optimal one dimensional constellation achieves lower error probability than using orthogonal channels.

Given finite dimensional random vectors$\boldsymbol{Y,X}$and$\boldsymbol{Z}$that form a Markov chain in that order$(\boldsymbol{Y}\rightarrow \boldsymbol{X}\rightarrow \boldsymbol{Z})$, we derive Rényi divergence based upper bounds for excess minimum risk, where$\boldsymbol{Y}$is a (target) vector that is to be estimated from an observed (feature) vector$\boldsymbol{X}$or its (stochastically) degraded version$\boldsymbol{Z}$. We define the excess minimum risk as the difference between the minimum expected loss in estimating$\boldsymbol{Y}$from$\boldsymbol{X}$and the minimum expected loss in estimating$\boldsymbol{Y}$from$\boldsymbol{Z}$. We obtain a family of bounds which generalize the bounds developed by Györfi et al. (2023) expressed in terms of Shannon's mutual information. Our bounds are similar to the bounds by Modak et al. (2021) obtained in the context of the generalization error of learning algorithms, but unlike the latter they do not involve fixed sub-Gaussian parameters and therefore hold for more general joint distributions of$\boldsymbol{Y,X}$, and$\boldsymbol{Z}$. We also provide an example with Bernoulli random variables where Rényi's divergence based upper bound are tighter than mutual information bounds.

Designing machine learning algorithms that are accurate yet fair, not discriminating based on any sensitive attribute, is of paramount importance for society to accept AI for critical applications. In this article, we propose a novel fair representation learning method termed the Rényi Fair Information Bottleneck Method (RFIB) which incorporates constraints for utility, fairness, and compactness (compression) of representation, and apply it to image and tabular data classification. A key attribute of our approach is that we consider - in contrast to most prior work - both demographic parity and equalized odds as fairness constraints, allowing for a more nuanced satisfaction of both criteria. Leveraging a variational approach, we show that our objectives yield a loss function involving classical Information Bottleneck (IB) measures and establish an upper bound in terms of two Rényi measures of order$ \boldsymbol {\alpha }$on the mutual information IB term measuring compactness between the input and its encoded embedding. We study the influence of the$ \boldsymbol {\alpha }$parameter as well as two other tunable IB parameters on achieving utility/fairness trade-off goals, and show that the$ \boldsymbol {\alpha }$parameter gives an additional degree of freedom that can be used to control the compactness of the representation. Experimenting on three different image datasets (EyePACS, CelebA, and FairFace) and two tabular datasets (Adult and COMPAS), using both binary and categorical sensitive attributes, we show that on various utility, fairness, and compound utility/fairness metrics RFIB outperforms current state-of-the-art approaches.

This paper addresses the capacity problem for a class of finite-state two-way channels (FS-TWCs). Specifically, inner and outer bounds for the channel capacity of FS-TWCs are derived, and they are combined to characterize the capacity region in a limiting expression for some special FS-TWCs. Although such an expression is often incomputable, it is illustrated via an example that a reduction to single-letter form is possible as long as the system variables exhibit stationarity and the associated "average channel" satisfies certain symmetry properties.

We construct a system of interacting finite memory Pólya urns to model contagion spread in a network. The urns, which are composed of red and black balls (representing degrees of infection and healthiness, respectively) interact in the sense that the probability at any time instant of drawing a red ball for a given urn not only depends on that urn’s ratio of red balls, but also on the ratio of red balls in the other urns of the network, hence accounting for the effect of spatial contagion. The urns have a finite memory, M, in the sense that reinforcing (black or red) balls added to each urn at time t are only kept in that urn for M future time instants (until time t + M). The resulting vector of all urn drawing variables forms an Mth order time-invariant irreducible and aperiodic Markov chain. We analytically examine the properties of the underlying Markov process and derive its asymptotic behaviour for the case of homogeneous system parameters. We further use mean-field approximation to obtain a class of approximating linear and nonlinear dynamical systems for the non-homogeneous case. Finally, we present simulations to assess the quality of these mean-field approximations.

We propose a novel method for enforcing AI fairness with respect to protected or sensitive factors. This method uses a dual strategy performing training and representation alteration (TARA) for the mitigation of prominent causes of AI bias. It includes the use of representation learning alteration via adversarial independence to suppress the bias-inducing dependence of the data representation from protected factors and training set alteration via intelligent augmentation to address bias-causing data imbalance by using generative models that allow the fine control of sensitive factors related to underrepresented populations via domain adaptation and latent space manipulation. When testing our methods on image analytics, experiments demonstrate that TARA significantly or fully debiases baseline models while outperforming competing debiasing methods that have the same amount of information-for example, with (% overall accuracy, % accuracy gap) = (78.8, 0.5) versus the baseline method's score of (71.8, 10.5) for Eye-PACS, and (73.7, 11.8) versus (69.1, 21.7) for CelebA. Furthermore, recognizing certain limitations in current metrics used for assessing debiasing performance, we propose novel conjunctive debiasing metrics. Our experiments also demonstrate the ability of these novel metrics in assessing the Pareto efficiency of the proposed methods.

The generalized Poor-Verdú error lower bound established by Changet al.(2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error.

This paper considers an information bottleneck problem with the objective of obtaining a most informative representation of a hidden feature subject to a Rényi entropy complexity constraint. The optimal bottleneck trade-off between relevance (measured via Shannon's mutual information) and Rényi entropy cost is defined and an iterative algorithm for finding approximate solutions is provided. We also derive an operational characterization for the optimal trade-off by demonstrating that the optimal Rényi entropy-relevance trade-off is achievable by a simple time-sharing scalar coding scheme and that no coding scheme can provide better performance. Two examples where the optimal Shannon entropy-relevance tradeoff can be exactly determined are further given.

We investigate the use of parameterized families of information-theoretic measures to generalize the loss functions of generative adversarial networks (GANs) with the objective of improving performance. A new generator loss function, least kth-order GAN (LkGAN), is introduced, generalizing the least squares GANs (LSGANs) by using a kth-order absolute error distortion measure with k≥1 (which recovers the LSGAN loss function when k=2). It is shown that minimizing this generalized loss function under an (unconstrained) optimal discriminator is equivalent to minimizing the kth-order Pearson-Vajda divergence. Another novel GAN generator loss function is next proposed in terms of Rényi cross-entropy functionals with order α>0, α≠1. It is demonstrated that this Rényi-centric generalized loss function, which provably reduces to the original GAN loss function as α→1, preserves the equilibrium point satisfied by the original GAN based on the Jensen-Rényi divergence, a natural extension of the Jensen-Shannon divergence. Experimental results indicate that the proposed loss functions, applied to the MNIST and CelebA data sets, under both DCGAN and StyleGAN architectures, confer performance benefits by virtue of the extra degrees of freedom provided by the parameters k and α, respectively. More specifically, experiments show improvements with regard to the quality of the generated images as measured by the Fréchet inception distance score and training stability. While it was applied to GANs in this study, the proposed approach is generic and can be used in other applications of information theory to deep learning, for example, the issues of fairness or privacy in artificial intelligence.

Our work focuses on unsupervised and generative methods that address the following goals: (1) learning unsupervised generative representations that discover latent factors controlling image semantic attributes, (2) studying how this ability to control attributes formally relates to the issue of latent factor disentanglement, clarifying related but dissimilar concepts that had been confounded in the past, and (3) developing anomaly detection methods that leverage representations learned in the first goal. For goal 1, we propose a network architecture that exploits the combination of multiscale generative models with mutual information (MI) maximization. For goal 2, we derive an analytical result, lemma 1, that brings clarity to two related but distinct concepts: the ability of generative networks to control semantic attributes of images they generate, resulting from MI maximization, and the ability to disentangle latent space representations, obtained via total correlation minimization. More specifically, we demonstrate that maximizing semantic attribute control encourages disentanglement of latent factors. Using lemma 1 and adopting MI in our loss function, we then show empirically that for image generation tasks, the proposed approach exhibits superior performance as measured in the quality and disentanglement of the generated images when compared to other state-of-the-art methods, with quality assessed via the Fréchet inception distance (FID) and disentanglement via mutual information gap. For goal 3, we design several systems for anomaly detection exploiting representations learned in goal 1 and demonstrate their performance benefits when compared to state-of-the-art generative and discriminative algorithms. Our contributions in representation learning have potential applications in addressing other important problems in computer vision, such as bias and privacy in AI.

We propose an adaptive lossy joint source-channel coding (JSCC) scheme for sending correlated sources over two-terminal discrete-memoryless two-way channels (DM-TWCs). The main idea is to couple the independent operations of the terminals via an adaptive coding mechanism, which can mitigate cross-interference resulting from simultaneous channel transmissions and concurrently exploit the sources' correlation to reduce the end-to-end reconstruction distortions. Our adaptive JSCC scheme not only subsumes existing lossy coding methods for two-way simultaneous communication but also improves their performance. Furthermore, we derive outer bounds for our two-way lossy transmission problem and establish complete JSCC theorems in some special settings. In these special cases, a non-adaptive separate source-channel coding (SSCC) scheme achieves the optimal performance, thus simplifying the design of the source-channel communication system.

The generalized Poor-Verdú error lower bound for multihypothesis testing is revisited. Its asymptotic expression is established in closed-form as its tilting parameter grows to infinity. It is also shown that the asymptotic generalized bound achieves the error exponent (or reliability function) of the memoryless binary symmetric channel at zero coding rates.

An adaptive joint source-channel coding (JSCC) scheme is presented for transmitting correlated sources over discrete-memoryless two-way channels subject to distortion constraints. The proposed JSCC scheme makes use of the previously transmitted and received channel signals as well as the sources' correlation to facilitate coordination between terminals. It is shown that the adaptive scheme strictly subsumes prior lossy coding methods for two-way simultaneous transmission and yields a new adaptive separate source-channel coding result. Two examples are given to show the scheme's advantages.

A joint source-channel coding (JSCC) scheme based on hybrid digital/analog coding is proposed for the transmission of correlated sources over discrete-memoryless two-way channels (DM-TWCs). The scheme utilizes the correlation between the sources in generating channel inputs, thus enabling the users to coordinate their transmission to combat channel noise. The hybrid scheme also subsumes prior coding methods such as rate-one separate source-channel coding and uncoded schemes for two-way lossy transmission, as well as the correlation-preserving coding scheme for (almost) lossless transmission. Moreover, we derive a distortion outer bound for the source-channel system using a genie-aided argument. A complete JSSC theorem for a class of correlated sources and DM-TWCs whose capacity region cannot be enlarged via interactive adaptive coding is also established. Examples that illustrate the theorem are given.

We investigate the problem of estimating a random variable Y under a privacy constraint dictated by another correlated random variable X. When X and Y are discrete, we express the underlying privacy-utility tradeoff in terms of the privacy-constrained guessing probability (PXY, ε), and the maximum probability Pc(Y|Z) of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Yensuring that Pc(X|Z) ≤ ε for a given privacy threshold ε ≥ 0. We prove that ħ (PXY, ·) is concave and piecewise linear, which allows us to derive its expression in closed form for any ε when X and Y are binary. In the non-binary case, we derive (PXY, ε) in the high-utility regime (i.e., for sufficiently large, but nontrivial, values of ε) under the assumption that Y and Z have the same alphabets. We also analyze the privacy-constrained guessing probability for two scenarios in which X, Y, and Z are binary vectors. When X and Y are continuous random variables, we formulate the corresponding privacy-utility tradeoff in terms of sENSR(PXY, ε), the smallest normalized minimum mean squared-error (mmse) incurred in estimating Y from a Gaussian perturbation Z. Here, the minimization is taken over a family of Gaussian perturbations Z for which the mmse of f (X) given Z is within a factor 1-ε from the variance of f (X) for any non-constant real-valued function f . We derive tight upper and lower bounds for sENSR when Y is Gaussian. For general absolutely continuous random variables, we obtain a tight lower bound for sENSR(PXY, ε) in the high privacy regime, i.e., for small ε.

A class of burst noise-erasure channels which incorporate both errors and erasures during transmission is studied. The channel, whose output is explicitly expressed in terms of its input and a stationary ergodic noise-erasure process, is shown to have a so-called “quasi-symmetry” property under certain invertibility conditions. As a result, it is proved that a uniformly distributed input process maximizes the channel's block mutual information, resulting in a closed-form formula for its non-feedback capacity in terms of the noise-erasure entropy rate and the entropy rate of an auxiliary erasure process. The feedback channel capacity is also characterized, showing that the feedback does not increase capacity and generalizing prior related results. The capacity-cost function of the channel with and without feedback is next investigated. A sequence of finite-letter upper bounds for the capacity-cost function without feedback is derived. Finite-letter lower bonds for the capacity-cost function with feedback are obtained using a specific encoding rule. Based on these bounds, it is demonstrated both numerically and analytically that feedback can increase the capacity-cost function for a class of channels with Markov noise-erasure processes.

In this paper, we make use of channel symmetry properties to determine the capacity region of three types of two-way networks: 1) two-user memoryless two-way channels (TWCs); 2) two-user TWCs with memory; and 3) three-user multiaccess/degraded broadcast (MA/DB) TWCs. For each network, symmetry conditions under which a Shannon-type random coding inner bound (under independent non-adaptive inputs) is tight are given. For two-user memoryless TWCs, prior results are substantially generalized by viewing a TWC as two interacting state-dependent one-way channels. The capacity of symmetric TWCs with memory, whose outputs are functions of the inputs and independent stationary and ergodic noise processes, is also obtained. Moreover, various channel symmetry properties under which the Shannon-type inner bound is tight are identified for three-user MA/DB TWCs. The results not only enlarge the class of symmetric TWCs whose capacity region can be exactly determined but also imply that interactive adaptive coding, not improving capacity, is unnecessary for such channels.

We study the curing of epidemics of a network contagion, which is modelled using a variation of the classical Polya urn process that takes into account spatial infection among neighbouring nodes. We introduce several quantities for measuring the overall infection in the network and use them to formulate an optimal control problem for minimizing the average infection rate using limited curing resources. We prove the feasibility of this problem under high curing budgets by deriving conservative lower bounds on the amount of curing per node that turn our measures of network infection into supermartingales. We also provide a provably convergent gradient descent algorithm to find the allocation of curing under limited budgets. Motivated by the fact that this strategy is computationally expensive, we design a suit of heuristic methods that are locally implementable and nearly as effective. Extensive simulations run on large-scale networks demonstrate the effectiveness of our proposed strategies.

New sufficient conditions for determining in closed form the capacity region of point-to-point memoryless two-way channels (TWCs) are derived. The proposed conditions not only relax Shannon's condition which can identify only TWCs with a certain symmetry property but also generalize other existing results. Examples are given to demonstrate the advantages of the proposed conditions.

This work focuses on the construction of optimized binary signaling schemes for two-sender uncoded transmission of correlated non-uniform sources over non-orthogonal Gaussian multiple access channels. Based on an error-rate analysis under joint maximum-a-posteriori decoding, optimized binary-pulsed-amplitude modulation constellations for two senders are derived to minimize the system's error rate. The joint probability distribution of the two-senders' source is observed to induce a special layout of optimized constellations which can effectively control the interference due to non-orthogonal transmission. Numerical results further confirm that significant gains are achievable by the proposed design.

We investigate the problem of guessing a discrete random variable Y under a privacy constraint dictated by another correlated discrete random variable X, where both guessing efficiency and privacy are assessed in terms of the probability of correct guessing. We define h(PXY,ε) as the maximum probability of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Yensuring that the probability of correctly guessing X given Z does not exceed ε. We show that the map ε → h(PXY,ε) is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for h(PxY,ε) when X and Y are connected via a binary-input binary-output channel. For {(Xi, Yi)}ni=1being pairs of independent and identically distributed binary random vectors, we similarly define h_n(PX n Y n, ε) under the assumption that Znis also a binary vector. Then we obtain a closed form expression for h_n(PX n Y n, ε) for sufficiently large, but nontrivial values of ε.

A class of burst noise-erasure channels which incorporate both errors and erasures during transmission is studied. The channel, whose output is explicitly expressed in terms of its input and a stationary ergodic noise-erasure process, is shown to satisfy a so-called “quasi-symmetry” condition under certain invertibility conditions. As a result, it is proved that a uniformly distributed input process maximizes the channel's block mutual information, resulting in a closed-form formula for its nonfeedback capacity in terms of the noise-erasure entropy rate and the entropy rate of an auxiliary erasure process. The feedback channel capacity is also characterized, showing that feedback does not increase capacity and generalizing prior related results.

Achievability and converse results for the lossy transmission of correlated sources over Shannon's two-way channels (TWCs) are presented. A joint source-channel coding theorem for independent sources and TWCs for which adaptation cannot enlarge the capacity region is also established. We further investigate the optimality of scalar coding for TWCs with discrete modulo additive noise as well as additive white Gaussian noise. Comparing the distortion of scalar coding with the derived bounds, we observe that scalar coding achieves the minimum distortion over both families of TWCs for independent and uniformly distributed sources and independent Gaussian sources.

We investigate the problem of the predictability of random variable Y under a privacy constraint dictated by random variable X, correlated with Y , where both predictability and privacy are assessed in terms of the minimum mean-squared error (MMSE). Given that X and Y are connected via a binary-input symmetric-output (BISO) channel, we derive the optimal random mapping PZ|Ysuch that the MMSE of Y given Z is minimized while the MMSE of X given Z is greater than (1-ε)var(X) for a given ε ≥ 0. We also consider the case where (X, Y ) are continuous and PZ|Yis restricted to be an additive-noise channel.

In two-way channels, each user transmits and receives at the same time. This allows each encoder to interactively adapt the current input to its own message and all previously received signals. Such coding approach can introduce correlation between inputs of different users, since all the users' outputs are correlated by the nature of the channel. However, for some channels, such adaptation in the coding scheme and its induced correlation among users are useless in the sense that they do not help enlarge the capacity region with respect to the standard coding method (where each user encodes only based on its own message). In this paper, it is shown that adaptation is not helpful for enlarging the capacity region of two classes of two-way discrete channels: the modulo additive-noise channel with memory and the multiple access/degraded broadcast channel.

In this paper, lower bounds on the probability of a finite union of events are considered, i.e., $P(\bigcup_{i=1}^N A_i)$, in terms of the individual event probabilities $\{P(A_i), i=1,\ldots,N\}$ and the sums of the pairwise event probabilities, i.e., $\{\sum_{j:j\neq i} P(A_i\cap A_j), i=1,\ldots,N\}$. The contribution of this paper includes the following: (i) in the class of all lower bounds that are established in terms of only the $P(A_i)$'s and $\sum_{j:j\neq i} P(A_i\cap A_j)$'s, the optimal lower bound is given numerically by solving a linear programming (LP) problem with $N^2-N+1$ variables; (ii) a new analytical lower bound is proposed based on a relaxed LP problem, which is at least as good as the bound due to Kuai, Alajaji, and Takahara [Discrete Math., 215 (2000), pp. 147--158]; (iii) numerical examples are provided to illustrate the performance of the bounds.

We consider the problem of joint recovery of a bivariate Gaussian source and of interference over the two-user Gaussian degraded broadcast channel in the presence of common interference. The interference, that is available non-causally at the encoder, is assumed to be Gaussian and correlated to the sources. The tradeoff between the distortion of the sources and the interference estimation error is studied; information-theoretic outer and inner bounds based on ideas from rate-distortion theory and hybrid coding are derived, respectively. More precisely, the outer bound is found by assuming additional knowledge at each user; the inner bound, however, is obtained by analyzing the distortion of a layered hybrid scheme based on proper power splitting, Costa and Wyner-Ziv coding. Low delay and complexity coding schemes based on analog mapping are next proposed. More specifically, parametric mappings based on linear and sawtooth curves are studied and optimized by minimizing an upper bound on the system's distortion; nonparametric mappings based on joint optimization between the encoder and the decoder using an iterative algorithm are designed. Numerical results show that for the special cases that are previously considered by Abou Saleh et al. (with no fading), the derived outer bound is tighter and the proposed hybrid scheme has a lower complex structure with no loss in performance. In addition, the proposed low delay nonlinear schemes outperform the linear scheme and perform relatively close to the inner bound under certain system settings.

We present new results on bounding the probability of a finite union of events, equation for a fixed positive integer N, using partial information on the events joint probabilities. We first consider bounds that are established in terms of {P(Ai)} and {ΣjcjP(Ai∩ Aj)} where c1, …, cNare given weights. We derive a new class of lower bounds of at most pseudo-polynomial computational complexity. This class of lower bounds generalizes the recent bounds in [1], [2] and can be tighter in some cases than the Gallot-Kounias [3]–[5] and Prékopa-Gao [6] bounds which require more information on the events probabilities. We next consider bounds that fully exploit knowledge of {P(Ai)} and {P(Ai∩ Aj)}. We establish new numerical lower/upper bounds on the union probability by solving a linear programming problem with equation variables. These bounds coincide with the optimal lower/upper bounds when N ≤ 7 and are guaranteed to be sharper than the optimal lower/upper bounds of [1], [2] that use {P(Ai)} and {ΣjP(Ai∩ Aj)}.

We study the problem of recovering sparse and compressible signals using a weighted${\ell _p}$minimization with$0 < p \leq 1$from noisy compressed sensing measurements when part of the support is known a priori. To better model different types of non-Gaussian (bounded) noise, the minimization program is subject to a data-fidelity constraint expressed as the${\ell _q}(2 \leq q < \infty)$norm of the residual error. We show theoretically that the reconstruction error of this optimization is bounded (stable) if the sensing matrix satisfies an extended restricted isometry property. Numerical results show that the proposed method, which extends the range of$p$and$q$comparing with previous works, outperforms other noise-aware basis pursuit programs. For$p < 1$, since the optimization is not convex, we use a variant of an iterative reweighted${\ell _2}$algorithm for computing a local minimum.

We study the optimal maximum likelihood (ML) block decoding of general binary codes sent over two classes of binary additive noise channels with memory. Specifically, we consider the infinite and finite memory Polya contagion and queue-based channel models, which were recently shown to approximate well binary modulated correlated fading channels used with hard-decision demodulation. We establish conditions on the codes and channels parameters under which ML and minimum Hamming distance decoding are equivalent. We also present results on the optimality of classical perfect and quasi-perfect codes when used over the channels under ML decoding. Finally, we briefly apply these results to the dual problem of syndrome source coding with and without side information.

The classes of all lower/upper bounds on the probability of a finite union of events which are expressed only in terms of the individual event probabilities and the sums of the pairwise event probabilities are considered. The optimal lower and upper bounds in each class are given numerically by solving a linear programming (LP) problem. Furthermore, a suboptimal analytical lower bound is established by solving a relaxed LP problem, which is at least as good as an existing bound due to Kuai, et al. [1]. Note that the new lower bounds can be further improved algorithmically by optimizing them over subsets [2], [3], and can be applied to general estimation problems involving the probability of a finite union. Finally, the new lower/upper bounds are illustrated by examining the symbol and bit error rates of an uncoded communication system used in conjunction with Mary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN) channels under maximum a posteriori (MAP) decoding.

We consider the joint source-channel coding (JSCC) problem where the real valued outputs of two correlated memoryless Gaussian sources are scalar quantized, bit assigned, and transmitted, without applying any error correcting code, over a multiple access channel (MAC) which consists of two orthogonal point-to- point time-correlated Rayleigh fading sub-channels with soft- decision demodulation. At the receiver side, a joint sequence maximum a posteriori (MAP) detector is used to exploit the correlation between the two sources as well as the redundancy left in the quantizer's indices, the channel's soft-decision outputs, and noise memory. The MAC's sub-channels are modeled via non-binary Markov noise discrete channels recently shown to effectively represent point-to-point fading channels. For the simple case of quantizing the sources with two levels, we establish a necessary and sufficient condition under which the joint sequence MAP decoder can be reduced to a simple instantaneous symbol-by-symbol decoder. Then, using numerical results obtained by system simulation, it is observed that when the sources are highly correlated and soft-decision quantization is used, JSCC can profit from a high correlation in the channel noise process and provide significant signal-to-distortion ratio improvements of up to 6.3 dB over a fully interleaved channel.

We consider the problem of sending a Gaussian source over a fading channel with Gaussian interference known to the transmitter. We study joint source-channel coding schemes for the case of unequal bandwidth between the source and the channel and when the source and the interference are correlated. An outer bound on the system's distortion is first derived by assuming additional information at the decoder side. We then propose layered coding schemes based on proper combination of power splitting, bandwidth splitting, Wyner-Ziv and hybrid coding. More precisely, a hybrid layer, that uses the source and the interference, is concatenated (superimposed) with a purely digital layer to achieve bandwidth expansion (reduction). The achievable (square error) distortion region of these schemes under matched and mismatched noise levels is then analyzed. Numerical results show that the proposed schemes perform close to the best derived bound and to be resilient to channel noise mismatch. As an application of the proposed schemes, we derive both inner and outer bounds on the source-channel-state distortion region for the fading channel with correlated interference; the receiver, in this case, aims to jointly estimate both the source signal as well as the channel-state (interference).

We consider the transmission of bivariate Gaussian sources (V1, V2) over the two-user Gaussian broadcast channel in the presence of interference that is correlated to the source and known to the transmitter. Each user i is interested in estimating Vi. We study hybrid digital-analog (HDA) schemes and analyze the achievable (square-error) distortion region under matched and expansion bandwidth regimes. These schemes require proper combinations of power splitting, bandwidth splitting, rate splitting, Wyner-Ziv and HDA Costa coding. An outer bound on the distortion region is also derived by assuming knowledge of V1at the second user and full/partial knowledge of the interference at both users. Numerical results show that the HDA schemes outperform tandem and linear schemes and perform close to the derived bound for certain system settings.

A joint source-channel coding problem that combines the efficient compression of discrete memoryless sources with their reliable communication over memoryless channels via binary prefix-free variable-length error-correcting codes (VLECs) is considered. Under a fixed free distance constraint, a priority-first search algorithm is devised for finding an optimal VLEC with minimal average codeword length. Two variations of the priority-first-search-based code construction algorithm are also provided. The first one improves the resilience of the developed codes against channel noise by additionally considering a performance parameter Bdfreewithout sacrificing optimality in average codeword length. In the second variation, to accommodate a large free distance constraint as well as a large source alphabet such as the 26-symbol English data source, the VLEC construction algorithm is modified with the objective of significantly reducing its search complexity while still yielding near-optimal codes. A low-complexity sequence maximum a posteriori (MAP) decoder for all VLECs (including our constructed optimal code) is then proposed under the premise that the receiver knows the number of codewords being transmitted. Simulations show that the realized optimal and suboptimal VLECs compare favorably with existing codes in the literature in terms of coding efficiency, search complexity and error rate performance.

The problem of reliable communication over the memoryless state-dependent multiple-access channel (MAC) is considered, where the encoders and the decoder are provided with various degrees of asymmetric noisy channel state information (CSI). For the case where the encoders observe causal, asymmetric noisy CSI and the decoder observes complete CSI, inner and outer bounds to the capacity region, which are tight for the sum-rate capacity, are provided. Next, single-letter characterizations for the channel capacity regions under each of the following system settings are established: 1) the CSI at the encoders are asymmetric deterministic functions of the CSI at the decoder and the encoders have noncausal noisy CSI; 2) the encoders observe asymmetric noisy CSI with asymmetric delays and the decoder observes complete CSI; 3) a degraded message set scenario with asymmetric noisy CSI at the encoders and complete and/or noisy CSI at the decoder. The main component in these results is a generalization of a recently introduced converse coding approach for the MAC with asymmetric quantized CSI at the encoders and herein considerably extended and adapted for the noisy CSI setup.

We study a joint source-channel decoding scheme that exploits the channel's statistical memory and soft-decision information in fading channels. The channel considered is a recently introduced binary input 2q-ary output channel with Markovian ergodic noise based on a finite queue (called NBNDC-QB). This model has been shown to effectively represent soft-decision demodulated correlated Rayleigh fading channels. The coding scheme consists of a scalar quantizer, a proper index assignment, and a sequence maximum a posteriori (MAP) decoder designed to harness the redundancy left in the quantizer's indices, the channel's soft-decision output, and correlation in the channel noise process. We first consider the simple case where the quantized indices form a binary symmetric Markov source and establish a necessary and sufficient condition under which the sequence MAP decoder is reduced to a simple instantaneous symbol-by-symbol decoder. We next assess the signal-to-distortion ratio (SDR) performance of our general system. Our numerical results confirm that this system can successfully take advantage of the channel memory and outperforms systems that use channel interleaving by as much as 2.6 dB in SDR. In addition, SDR gains of up to 2.8 dB are achieved using as few as 2 bits for soft-decision quantization over hard quantized output schemes. Finally, the NBNDC-QB channel model is validated in terms of SDR performance by fitting the NBNDC-QB model to a discrete correlated Rayleigh fading channel, designing a system for this matched NBNDC-QB model, and comparing this system's performance over both the NBNDC-QB and the Rayleigh fading channels.

We consider the problem of reliable communication over multiple-access channels (MAC) where the channel is driven by an independent and identically distributed state process and the encoders and the decoder are provided with various degrees of asymmetric (noisy or partial) channel state information (CSI). Namely, we provide a single letter characterization for the capacity region when the encoders have access to non-causal asymmetric partial CSI and the decoder has complete CSI. When the encoders observe asymmetric noisy CSI with asymmetric delays and the decoder observes complete CSI, we provide a single letter characterization for the capacity region. Finally, we consider a cooperative scenario with common and private messages, with noisy CSIT and complete CSIR and provide a single letter expression for the capacity region. For the cooperative scenario, we also note that as soon as the common message encoder does not have access to CSI, then for any noisy CSIT and CSIR setup it is possible to obtain a single letter characterization for the capacity region.

We propose a low delay and low complexity sensor system based on the combination of Shannon–Kotel'nikov mapping and compressed sensing (CS). The proposed system uses nonlinear analog mappings on the CS measurements to increase their immunity against channel noise. Numerical results show that the proposed purely-analog system outperforms the state-of-the-art purely CS systems in terms of signal-to-distortion ratio. In addition to sparsity knowledge, we use a statistical characterization of the observed signal to further improve system performance.

A discrete (binary-input 2q-ary output) communication channel with memory is introduced to judiciously capture both the statistical memory and the soft-decision information of a time-correlated discrete fading channel (DFC) used with antipodal signaling and soft output quantization of resolution q. The discrete channel, which can be explicitly described via its binary input process and a 2q-ary noise process, is shown to be symmetric, thus admitting a simple expression for its capacity when its noise is stationary ergodic. It is observed that considerable capacity gains can be achieved due to the channel's memory and the use of as few as 2 bits for soft-decision over interleaving the channel (to render it memoryless) and hard-decision demodulation (q=1). The 2q-ary noise process is next modeled via a queue-based (QB) ball-sampling mechanism to produce a mathematically tractable stationary ergodic Markovian noise source. The DFC is fitted by the QB noise model via an iterative procedure that minimizes the Kullback-Leibler divergence rate between the DFC and QB noise sources. Modeling results, measured in terms of channel noise correlation function and capacity reveal a good agreement between the two channels for a broad range of fading conditions.

A lower bound on the minimum error probability for multihypothesis testing is established. The bound, which is expressed in terms of the cumulative distribution function of the tilted posterior hypothesis distribution given the observation with tilting parameter , generalizes an earlier bound due the Poor and Verdú (1995). A sufficient condition is established under which the new bound (minus a multiplicative factor) provides the exact error probability asymptotically in . Examples illustrating the new bound are also provided.

In this paper, we present a novel algorithm that guarantees of finding a variable-length error-correcting code (VLEC) with minimal average codeword length for a fixed free distance dfree. We also propose a low complexity maximum a posterior (MAP) decoding algorithm for our codes under the premise that the receiver knows the number of codewords being transmitted. The resulting VLEC provides significant gains over other codes from the literature. When compared with separate source-channel tandem codes with identical dfree, such as a tandem code consisting of a Huffman source code concatenated with a (2, 1, 4) tail-biting convolutional channel code, our system has only a 0.3 dB performance loss at a bit error rate of 10-5while requiring significantly less decoding complexity.

A discrete fading channel (DFC) consisting of a binary modulated time-correlated Rayleigh fading channel used in conjunction with coherent soft-decision demodulation of resolution q is considered. The capacity of the binary input 2q-ary output DFC, which can be explicitly expressed in terms of a non-binary noise discrete channel with stationary ergodic 2q-ary noise, is evaluated in terms of q and the fading parameters. It is observed that considerable capacity gains can be achieved due to the channel's statistical memory and the use of as few as 2 bits for soft-decision over interleaving the channel (to render it memoryless) and hard-decision demodulation (q = 1). The DFC is next fitted by a recently introduced analytically tractable queue-based (QB) Markovian noise model. The QB parameters are estimated via an iterative procedure that minimizes the Kullback-Leibler divergence rate between the DFC and QB noise sources. Modeling results, measured in terms of both channel noise correlation function and capacity reveal a good agreement between the two channels for a broad range of fading conditions.

We consider the problem of sending a bivariate Gaussian source S=(S1,S2) across a power-limited two-user Gaussian broadcast channel. User i (i=1,2) observes the transmitted signal corrupted by Gaussian noise with power σi2and desires to estimate Si. We study hybrid digital-analog (HDA) joint source-channel coding schemes and analyze the region of (squared-error) distortion pairs that are simultaneously achievable. Two cases are considered: 1) broadcasting with bandwidth compression, and 2) broadcasting with bandwidth expansion. We modify and adapt HDA schemes of Wilson et al. and Prabhakaran et al. , originally proposed for broadcasting a single common Gaussian source, in order to provide achievable distortion regions for broadcasting correlated Gaussian sources. For comparison, we also extend the outer bound of Soundararajan et al. from the matched source-channel bandwidth case to the bandwidth mismatch case.

We consider the feedback capacity of a class of symmetric finite-state Markov channels. Here, symmetry (termed “quasi-symmetry”) is defined as a generalized version of the symmetry defined for discrete memoryless channels. The symmetry yields the existence of a hidden Markov noise process that depends on the channel's state process and facilitates the channel description as a function of input and noise, where the function satisfies a desirable invertibility property. We show that feedback does not increase capacity for such class of finite-state channels and that both their nonfeedback and feedback capacities are achieved by an independent and uniformly distributed (i.u.d.) input. As a result, the channel capacity is explicitly given as a difference of output and noise entropy rates, where the output is driven by the i.u.d. input.

A discrete (binary-input 2q-ary output) communication channel with memory is introduced with the objective to judiciously capture both the statistical memory and the soft-decision information of time-correlated fading channels modulated via binary phase-shift keying and coherently demodulated with an output quantizer of resolution q. It is shown that the discrete channel can be explicitly described in terms of its binary input process and a 2q-ary noise process. It is also shown that the channel is symmetric and admits a simple expression for its capacity when its noise is stationary ergodic. The 2q-ary noise process is next modeled via a generalized version of the recently studied binary queue-based channel (2007) to produce a mathematically tractable stationary ergodic M'th order Markovian noise source with 2q+ 2 parameters. Numerical results indicate that the capacity of the discrete channel with q = 2, 3 is substantially improved over the cases of perfect channel interleaving (which yields an equivalent memoryless channel) and of hard-decision demodulation (q = 1). These results point to potentially large performance gains achievable by designing coding schemes for this discrete channel that exploit both its memory and soft-decision information, as opposed to ignoring either of them.

We consider the transmission of a bivariate Gaussian source S = (S1, S2) across a power-limited two-user Gaussian broadcast channel. User i (i = 1, 2) observes the transmitted signal corrupted by Gaussian noise with power sigmai2and wants to estimate Si. We study hybrid digital-analog (HDA) joint source-channel coding schemes and analyze these schemes to obtain achievable (squared-error) distortion regions. Two cases are considered: 1) source and channel bandwidths are equal, 2) broadcasting with bandwidth compression. We adapt HDA schemes of Wilson et al. and Prabhakaran et al. to provide various achievable distortion regions for both cases. Using numerical examples, we demonstrate that for bandwidth compression, a three-layered coding scheme consisting of analog, superposition, and Costa coding performs well compared to the other provided HDA schemes. In the case of matched bandwidth, a three-layered coding scheme with an analog layer and two layers, each consisting of a Wyner-Ziv coder followed by a Costa coder, performs best.

We study the decoding problem when a binary linear perfect or quasi-perfect code is transmitted over a binary channel with additive Markov noise. After examining the properties of the channel block transition distribution, we derive sufficient conditions under which strict maximum-likelihood decoding is equivalent to strict minimum Hamming distance decoding when the code is perfect. Additionally, we show a near equivalence relationship between strict maximum likelihood and strict minimum distance decoding for quasi-perfect codes for a range of channel parameters and the code's minimum distance. As a result, an improved (complete) minimum distance decoder is proposed and simulations illustrating its benefits are provided.

We study the maximum a posteriori (MAP) decoding of memoryless non-uniform sources over multiple-antenna channels. Our model is general enough to include space-time coding, BLAST architectures, and single-transmit multi-receive antenna systems which employ any type of channel coding. We derive a closed-form expression for the codeword pairwise error probability (PEP) of general multi-antenna codes using moment generating function and Laplace transform arguments. We then consider space-time orthogonal block (STOB) coding and prove that, similar to the maximum likelihood (ML) decoding case, detection of symbols is decoupled in MAP decoding. We also derive the symbol PEP in closed-form for STOB codes. We apply these results in several scenarios. First, we design a binary antipodal signaling scheme which minimizes the system bit error rate (BER) under STOB coding. At a BER of 10-6, this constellation has a channel signal-to-noise ratio (CSNR) gain of 4.7 dB over conventional BPSK signaling for a binary nonuniform source with p0Delta=P(0) = 0.9. We next design space-time linear dispersion (LD) codes which are optimized for the source distribution under the criterion of minimizing the union upper bound on the frame error rate (FER). Two codes are given here: one outperforms V-BLAST by 3.5 dB and Alamouti's code by 12.3 dB at an FER of 10-2for a binary source with p0= 0.9, and the other outperforms V-BLAST by 4.2 dB at an FER of 10-3for a uniform source. These codes also outperform the LD codes of constructed under a different criteria. Finally, the problem of bit-to-signal mapping is studied. It is shown that for a binary source with p0= 0.9, 64-QAM signaling, and SER = 10-3, a gain of 3.7 dB can be achieved using a better-than-Gray mapping. For a system with one transmit and two receive antennas that uses trellis coding with 16-QAM signaling, a 1.8 dB gain over quasi-Gray mapping and ML decoding is observed when MAP decoding is used for binary sources with p0= 0.9.

Three hybrid digital-analog (HDA) systems, denoted by HDA-I, HDA* and HDA-II, for the coding of a memoryless discrete-time Gaussian source over a discrete-time additive memoryless Gaussian channel under bandwidth compression are studied. The systems employ simple linear coding in their analog component and superimpose their analog and digital signals before channel transmission. Information-theoretic upper bounds on the asymptotically optimal mean squared error distortion of the systems are obtained under both matched and mismatched channel conditions. Allocation schemes for distributing the channel input power between the analog and the digital signals are also examined. It is shown that systems HDA* and HDA-II can asymptotically achieve the optimal Shannon-limit performance under matched channel conditions. Low-complexity and low-delay versions of systems HDA-I and HDA-II are next designed and implemented without the use of error correcting codes. The parameters of these HDA systems, which employ vector quantization in conjunction with binary phase-shift keying modulation in their digital part, are optimized via an iterative algorithm similar to the design algorithm for channel-optimized vector quantizers. Both systems have low complexity and low delay, and guarantee graceful performance improvements for high CSNRs. For memoryless Gaussian sources the designed HDA-II system is shown to be superior to the HDA-I designed system. When applied to a Gauss-Markov source under Karhunen-Loeve processing, the HDA-I system is shown to provide considerably better performance.

We investigate the joint source-channel coding (JSCC) excess distortion exponentEJ(the exponent of the probability of exceeding a prescribed distortion level) for some memoryless communication systems with continuous alphabets. We first establish upper and lower bounds forEJfor systems consisting of a memoryless Gaussian source under the squared-error distortion fidelity criterion and a memoryless additive Gaussian noise channel with a quadratic power constraint at the channel input. A necessary and sufficient condition for which the two bounds coincide is provided, thus exactly determining the exponent. This condition is observed to hold for a wide range of source-channel parameters. As an application, we study the advantage in terms of the excess distortion exponent of JSCC over traditional tandem (separate) coding for Gaussian systems. A formula for the tandem exponent is derived in terms of the Gaussian source and Gaussian channel exponents, and numerical results show that JSCC often substantially outperforms tandem coding. The problem of transmitting memoryless Laplacian sources over the Gaussian channel under the magnitude-error distortion is also carried out. Finally, we establish a lower bound forEJfor a certain class of continuous source-channel pairs when the distortion measure is a metric.

We study the transmission of two discrete memoryless correlated sources, consisting of a common and a private source, over a discrete memoryless multiterminal channel with two transmitters and two receivers. At the transmitter side, the common source is observed by both encoders but the private source can only be accessed by one encoder. At the receiver side, both decoders need to reconstruct the common source, but only one decoder needs to reconstruct the private source. We hence refer to this system by the asymmetric two-user source-channel coding system. We derive a universally achievable lossless joint source-channel coding (JSCC) error exponent pair for the two-user system by using a technique which generalizes Csiszar's type-packing lemma (1980) for the point-to-point (single-user) discrete memoryless source-channel system. We next investigate the largest convergence rate of asymptotic exponential decay of the system (overall) probability of erroneous transmission, i.e., the system JSCC error exponent. We obtain lower and upper bounds for the exponent. As a consequence, we establish a JSCC theorem with single-letter characterization and we show that the separation principle holds for the asymmetric two-user scenario. By introducing common randomization, we also provide a formula for the tandem (separate) source-channel coding error exponent. Numerical examples show that for a large class of systems consisting of two correlated sources and an asymmetric multiple-access channel with additive noise, the JSCC error exponent considerably outperforms the corresponding tandem coding error exponent.

We establish random-coding lower bounds to the error exponent of discrete and Gaussian joint quantization and private watermarking systems. In the discrete system, both the covertext and the attack channel are memoryless and have finite alphabets. In the Gaussian system, the covertext is memoryless Gaussian and the attack channel has additive memoryless Gaussian noise. In both cases, our bounds on the error exponent are positive in the interior of the achievable quantization and watermarking rate region.

We consider the estimation of a Gaussian source by a Gaussian sensor network where L distributed sensors transmit noisy observations of the source through a fading Gaussian multiple access channel (MAC) to a fusion center (FC). Since sensor power is usually limited, our goal is to characterize the optimal tradeoff between the transmission cost, i.e., the power vector P = (P1, P2, ..., PL), and the average estimation distortion, D. We focus on asymmetric fading sensor networks in which the sensors have differing signal to noise ratios and transmission powers. We present necessary and sufficient conditions for the achievability of (L + 1)-tuples (P1, P2, ..., PL, D). For a symmetric Gaussian sensor network with deterministic and equal-magnitude fading, we derive the optimal power-distortion tradeoff. We also provide an achievable power-distortion region for the asymmetric sensor network with deterministic fading by analyzing the transmission of scaled versions of vector-quantized observations. We show that some of the power-distortion tuples achievable by this scheme are not achievable via an uncoded system.

We consider a public multi-user information embedding (watermarking) system in which two messages (watermarks) are independently embedded into two correlated covertexts and are transmitted through a multiple-access attack channel. The tradeoff between the achievable embedding rates and the average distortions for the two embedders is studied. For given distortion levels, inner and outer bounds for the embedding capacity region are obtained in single-letter form. Tighter bounds are also given for independent covertexts.

Consider a multi-user private information-hiding scenario in which two information hiders separately embed correlated sources (S1, S2) into a common host source U (covertext). The i-th information hider embeds the secret source Siinto the covertext U subject to a distortion constraint Di(i = 1, 2). The outputs (stegotexts) are corrupted by a multiple access channel attack WY|X1X2. A sufficient condition (in single-letter form) under which (S1, S2) can be successfully embedded into U under WY|X1X2is established.

Consider transmitting two discrete memoryless correlated sources, consisting of a common and a private source, over a discrete memoryless multi-terminal channel with two transmitters and two receivers. At the transmitter side, the common source is observed by both encoders but the private source can only be accessed by one encoder. At the receiver side, both decoders need to reconstruct the common source, but only one decoder needs to reconstruct the private source. We hence refer to this system by the asymmetric 2-user source-channel system. In this work, we derive a universally achievable joint source-channel coding (JSCC) error exponent pair for the 2-user system by using a technique which generalizes Csiszar's method (1980) for the point- to-point (single-user) discrete memoryless source-channel system. We next investigate the largest convergence rate of asymptotic exponential decay of the system (overall) probability of erroneous transmission, i.e., the system JSCC error exponent. We obtain lower and upper bounds for the exponent. As a consequence, we establish the JSCC theorem with single letter characterization.

We present an efficient algorithmic lower bound for the block error rate of linear binary block codes under soft maximum-likelihood decoding over binary phase-shift keying modulated additive white Gaussian noise channels. We cast the problem of finding a lower bound on the probability of a union as an optimization problem that seeks to find the subset that maximizes a recent lower bound - due to Kuai, Alajaji, and Takahara - that we will refer to as the KAT bound. The improved bound, which is denoted by LB-s, is asymptotically tight [as the signal-to-noise ratio (SNR) grows to infinity] and depends only on the code's weight enumeration function for its calculation. The use of a subset of the codebook to evaluate the LB-s lower bound not only significantly reduces computational complexity, but also tightens the bound specially at low SNRs. Numerical results for binary block codes indicate that at high SNRs, the LB-s bound is tighter than other recent lower bounds in the literature, which comprise the lower bound due to Seguin, the KAT bound (evaluated on the entire codebook), and the dot-product and norm bounds due to Cohen and Merhav.

We study the error exponent, EJ, for reliably transmitting a discrete stationary ergodic Markov (SEM) source Q over a discrete channel W with additive SEM noise via a joint source-channel (JSC) code. We first establish an upper bound for EJin terms of the Renyi entropy rates of the source and noise processes. We next investigate the analytical computation of EJby comparing our bound with Gallager's lower bound (1968) when the latter one is specialized to the SEM source-channel system. We also note that both bounds can be represented in Csiszar's form (1980), as the minimum of the sum of the source and channel error exponents. Our results provide us with the tools to systematically compare EJwith the tandem (separate) coding exponent EJ. We show that as in the case of memoryless source-channel pairs EJles 2Erand we provide explicit conditions for which EJ> ET. Numerical results indicate that EJap 2ETfor many SEM source-channel pairs, hence illustrating a substantial advantage of JSC coding over tandem coding for systems with Markovian memory.

A model for a binary additive noise communication channel with memory is introduced. The channel noise process, which is generated according to a ball sampling mechanism involving a queue of finite length$M$, is a stationary ergodic$M$th-order Markov source. The channel properties are analyzed and several of its statistical and information-theoretical quantities (e.g., block transition distribution, autocorrelation function (ACF), capacity, and error exponent) are derived in either closed or easily computable form in terms of its four parameters. The capacity of the queue-based channel (QBC) is also analytically and numerically compared for a variety of channel conditions with the capacity of other binary models, such as the well-known Gilbert–Elliott channel (GEC), the Fritchman channel, and the finite-memory contagion channel. We also investigate the modeling of the traditional GEC using this QBC model. The QBC parameters are estimated by minimizing the Kullback–Leibler divergence rate between the probability of noise sequences generated by the GEC and the QBC, while maintaining identical bit-error rates (BER) and correlation coefficients. The accuracy of fitting the GEC via the QBC is evaluated in terms of ACF, channel capacity, and error exponent. Numerical results indicate that the QBC provides a good approximation of the GEC for various channel conditions; it thus offers an interesting alternative to the GEC while remaining mathematically tractable.

For a memoryless Gaussian source under the squared-error distortion fidelity criterion and a memoryless additive Gaussian noise channel with a quadratic power constraint at the channel input, upper and lower bounds for the joint source-channel coding excess distortion exponent (which is the exponent of the probability of excess distortion) are established. A necessary and sufficient condition for which the two bounds coincide is provided, thus exactly determining the exponent. This condition is observed to hold for a wide range of source-channel parameters

An approach to hybrid digital-analog (HDA) source-channel coding for the communication of analog sources over memoryless Gaussian channels is introduced. The HDA system, which exploits the advantages of both digital and analog systems, generalizes a scheme previously presented by the authors, and can operate for any bandwidth ratio (bandwidth compression and expansion). It is based on vector quantization and features turbo coding in its digital component and linear/nonlinear processing in its analog part. Simulations illustrate that, under both bandwidth compression and expansion modes of operation, the HDA system provides a robust and graceful performance with good reproduction fidelity for a wide range of channel conditions

We investigate the computation of Csisza/spl acute/r's bounds for the joint source-channel coding (JSCC) error exponent E/sub J/ of a communication system consisting of a discrete memoryless source and a discrete memoryless channel. We provide equivalent expressions for these bounds and derive explicit formulas for the rates where the bounds are attained. These equivalent representations can be readily computed for arbitrary source-channel pairs via Arimoto's algorithm. When the channel's distribution satisfies a symmetry property, the bounds admit closed-form parametric expressions. We then use our results to provide a systematic comparison between the JSCC error exponent E/sub J/ and the tandem coding error exponent E/sub T/, which applies if the source and channel are separately coded. It is shown that E/sub T//spl les/E/sub J//spl les/2E/sub T/. We establish conditions for which E/sub J/>E/sub T/ and for which E/sub J/=2E/sub T/. Numerical examples indicate that E/sub J/ is close to 2E/sub T/ for many source-channel pairs. This gain translates into a power saving larger than 2 dB for a binary source transmitted over additive white Gaussian noise (AWGN) channels and Rayleigh-fading channels with finite output quantization. Finally, we study the computation of the lossy JSCC error exponent under the Hamming distortion measure.

We investigate the construction of joint source-channel (JSC) turbo codes for the reliable communication of binary Markov sources over additive white Gaussian noise and Rayleigh fading channels. To exploit the source Markovian redundancy, the first constituent turbo decoder is designed according to a modified version of Berrou's original decoding algorithm that employs the Gaussian assumption for the extrinsic information. Due to interleaving, the second constituent decoder is unable to adopt the same decoding method; so its extrinsic information is appropriately adjusted via a weighted correction term. The turbo encoder is also optimized according to the Markovian source statistics and by allowing different or asymmetric constituent encoders. Simulation results demonstrate substantial gains over the original (unoptimized) Turbo codes, hence significantly reducing the performance gap to the Shannon limit. Finally, we show that our JSC coding system considerably outperforms tandem coding schemes for bit error rates smaller than 10/sup -4/, while enjoying a lower system complexity.

A joint source-channel coding system for image communication over an additive white Gaussian noise channel is presented. It employs vector quantization based hybrid digital-analog modulation techniques with bandwidth compression and expansion for transmitting and reconstructing the wavelet coefficients of an image. The main advantage of the proposed system is that it achieves good performance at the design channel signal-to-noise ratio (CSNR), while still maintaining a "graceful improvement" characteristic at higher CSNR. Comparisons are made with two purely digital systems and two purely analog systems. Simulation shows that the proposed system is superior to the other investigated systems for a wide range of CSNR.

We establish an upper bound for the joint source-channel coding (JSCC) error exponent E/sub J/(Q, W) for a discrete stationary ergodic Markov (SEM) source Q and a discrete channel W with additive SEM noise. This bound, which is expressed in terms of the Renyi entropy rates of the source and noise processes, admits an identical form to Csiszar's sphere-packing upper bound for the JSCC error exponent for memoryless systems (I. Csiszar, Nov. 1982). In this regard, our result is a natural extension of Csiszar's upper bound of the JSCC error exponent from the case of memoryless systems to the case of SEM systems. We also investigate the analytical computation of E/sub J/(Q,W) by comparing our bound with Gallager's random-coding lower bound (R. G. Gallager, 1968), when the latter one is specialized to the SEM source-channel system.

The performance of space-time orthogonal block (STOB) codes over slow Rayleigh fading channels and maximum-likelihood (ML) decoding is investigated. Two Bonferroni-type bounds (one upper bound and one lower bound) for the symbol error rate (SER) and bit error rate (BER) of the system are obtained. The bounds are expressed in terms of the pairwise error probabilities (PEPs) and the two-dimensional pairwise error probabilities (2-D PEPs) of the transmitted symbols. Furthermore, the bounds can be efficiently evaluated and they hold for arbitrary (nonstandard) signaling schemes and mappings. Numerical results demonstrate that the bounds are very accurate in estimating the performance of STOB codes. In particular, the upper and lower bounds often coincide even at low channel signal-to-noise ratios, large constellation sizes, and large diversity orders.

Channel-optimized vector quantization (COVQ) has proven to be an effective joint source-channel coding technique that makes the underlying quantizer robust to channel noise. Unfortunately, COVQ retains the high encoding complexity of the standard vector quantizer (VQ) for medium-to-high quantization dimensions and moderate-to-good channel conditions. A technique called sample adaptive product quantization (SAPQ) was recently introduced by Kim and Shroff to reduce the complexity of the VQ while achieving comparable distortions. In this letter, we generalize the design of SAPQ for the case of memoryless noisy channels by optimizing the quantizer with respect to both source and channel statistics. Numerical results demonstrate that the channel-optimized SAPQ (COSAPQ) achieves comparable performance to the COVQ (within 0.2 dB), while maintaining considerably lower encoding complexity (up to half of that of COVQ) and storage requirements. Robustness of the COSAPQ system against channel mismatch is also examined.

We investigate the error performance of a communication system where a nonuniform memoryless binary source is transmitted via Gray-mapped-ary phase-shift keying or quadrature amplitude modulation over memoryless Rayleigh fading channels, and demodulated via optimal maximum a posteriori detection. Using recently derived upper and lower bounds on the probability of a general union of events, which are tight and can be efficiently computed, the system symbol-error () and bit-error ( ) rates are evaluated for a wide range of channel conditions. Since for nonuniform signaling, Gray mapping is not necessarily optimal for minimizing or (as was recently shown by Takahara et al.), we also evaluate the system performance under the map obtained by Takahara et al. and compare it with a Gray-mapped system.

We study the analytical computation of Csiszar's [1980] random-coding lower bound and sphere-packing upper bound for the lossless joint source-channel (JSC) error exponent, E/sub J/(Q, W), for a discrete memoryless source (DMS) Q and a discrete memoryless channel (DMC) W. We provide equivalent expressions for these bounds, which can be readily calculated for arbitrary (Q,W) pairs. We also establish explicit conditions under which the bounds coincide, thereby exactly determining E/sub J/(Q,W).

We investigate the modeling of the well-known burst-noise Gilbert-Elliott channel (GEC) using a recently introduced queue-based channel (QBC) model. The QBC parameters are estimated by minimizing the Kullback-Leibler divergence rate between the probability of error sequences generated by the QBC and the GEC, while maintaining identical bit error rates and correlation coefficients. The accuracy of fitting the GEC via the QBC is evaluated in terms of channel capacity and autocorrelation function. Numerical results show that the QBC provides a very good approximation of the GEC for various channel conditions. It thus offers an interesting alternative to the GEC while remaining mathematically tractable.

We investigate the joint source-channel coding problem of transmitting nonuniform memoryless sources over binary phase-shift keying-modulated additive white Gaussian noise and Rayleigh fading channels via turbo codes. In contrast to previous work, recursive nonsystematic convolutional encoders are proposed as the constituent encoders for heavily biased sources. We prove that under certain conditions, and when the length of the input source sequence tends to infinity, the encoder state distribution and the marginal output distribution of each constituent recursive convolutional encoder become asymptotically uniform, regardless of the degree of source nonuniformity. We also give a conjecture (which is empirically validated) on the condition for the higher order distribution of the encoder output to be asymptotically uniform, irrespective of the source distribution. Consequently, these conditions serve as design criteria for the choice of good encoder structures. As a result, the outputs of our selected nonsystematic turbo codes are suitably matched to the channel input, since a uniformly distributed input maximizes the channel mutual information, and hence, achieves capacity. Simulation results show substantial gains by the nonsystematic codes over previously designed systematic turbo codes; furthermore, their performance is within 0.74-1.17 dB from the Shannon limit. Finally, we compare our joint source-channel coding system with two tandem schemes which employ a fourth-order Huffman code (performing near-optimal data compression) and a turbo code that either gives excellent waterfall bit-error rate (BER) performance or good error-floor performance. At the same overall transmission rate, our system offers robust and superior performance at low BERs (< 10/sup -4/), while its complexity is lower.

In , Csisza/spl acute/r established the concept of forward /spl beta/-cutoff rate for the error exponent hypothesis testing problem based on independent and identically distributed (i.i.d.) observations. Given /spl beta/0, /spl alpha//spl ne/1. Similarly, for 0</spl beta/<1, Csisza/spl acute/r also established the concept of reverse /spl beta/-cutoff rate for the correct exponent hypothesis testing problem. In this work, we extend Csisza/spl acute/r's results by investigating the forward and reverse /spl beta/-cutoff rates for the hypothesis testing between two arbitrary sources with memory. We demonstrate that the lim inf Re/spl acute/nyi /spl alpha/-divergence rate provides the expression for the forward /spl beta/-cutoff rate. We also show that if the log-likelihood large deviation spectrum admits a limit, then the reverse /spl beta/-cutoff rate equals the liminf /spl alpha/-divergence rate, where /spl alpha/=(1/1-/spl beta/) and 0</spl beta/</spl beta//sub max/, where /spl beta//sub max/ is the largest /spl beta/<1 for which the lim inf (1/1-/spl beta/)-divergence rate is finite. For /spl beta//sub max//spl les//spl beta/<1, we show that the reverse cutoff rate is in general only upper-bounded by the lim inf Re/spl acute/nyi divergence rate. Unlike in , where the alphabet for the source coding cutoff rate problem was assumed to be finite, we assume arbitrary (countable or continuous) source alphabet. We also provide several examples to illustrate our forward and reverse /spl beta/-cutoff rates results and the techniques employed to establish them.

In this work, we provide a computable expression for the Kullback-Leibler divergence rate lim/sub n/spl rarr//spl infin//1/nD(p/sup (n)//spl par/q/sup (n)/) between two time-invariant finite-alphabet Markov sources of arbitrary order and arbitrary initial distributions described by the probability distributions p/sup (n)/ and q/sup (n)/, respectively. We illustrate it numerically and examine its rate of convergence. The main tools used to obtain the Kullback-Leibler divergence rate and its rate of convergence are the theory of nonnegative matrices and Perron-Frobenius theory. Similarly, we provide a formula for the Shannon entropy rate lim/sub n/spl rarr//spl infin//1/nH(p/sup (n)/) of Markov sources and examine its rate of convergence.

We derive a closed-form expression for the exact pairwise error probability (PEP) of a non-uniform memoryless binary source transmitted over a Rayleigh fading channel using space-time orthogonal block codes and maximum a posteriori (MAP) detection. The expression is easy to evaluate and holds for any signaling scheme. We then use this result to minimize the bit error rate of the binary antipodal signaling scheme. Numerical results for the case of binary antipodal signaling (BPSK and optimal) verify the accuracy of our formula and quantify substantial gains of MAP decoding over maximum likelihood (ML) decoding for sources with strong non-uniformity.

The design of two-dimensional constellation mappings for the transmission of binary nonuniform memoryless sources over additive white Gaussian noise channels using standard M-ary PSK and QAM modulation schemes is investigated. The main application of this problem is the incorporation of an adaptive mapping assignment in modem devices that employ fixed PSK/QAM modulation schemes for the transmission of heterogenous data (such as multimedia information) containing various levels of nonuniformity. In general, the optimal mapping depends on both the probability distribution of the input signals and the signal-to-noise ratio (SNR) in the channel, in addition to the geometry of the signal constellation. We show that constellation mappings which follow the objective of minimizing the average symbol energy and, given this, maximizing the decoding probability of the most likely signals, can yield symbol-error-rate and bit-error-rate performance that is substantially better than Gray encoding maps. Gains as high as 3.5 dB in SNR E/sub b//N/sub 0/ are obtained for highly nonuniform sources. Finally, we note that the mappings techniques result in nonzero mean constellations and briefly consider their performances when they are converted to zero mean constellations by shifting. In this case, we observe that the shifted zero-mean Gray map outperforms our shifted maps for small- to medium-sized constellations (M/spl les/32), but not for larger sizes.

A progressive method for transmission of images over a bursty noise channel is presented. It is based on discrete wavelet transform (DWT) coding and channel-optimized scalar quantization. The main advantage of the proposed system is that it exploits the channel memory and hence has superior performance over a similar scheme designed for the equivalent memoryless channel through the use of channel interleaving. In fact, the performance of the proposed system improves as the noise becomes more correlated, at a fixed bit error rate. Comparisons are made with other alternatives which employ independent source and channel coding over the fully interleaved channel at various bit rates and bit error rates. It is shown that the proposed method outperforms these substantially more complex systems for the whole range of considered bit rates and for a wide range of channel conditions.

In an earlier work, Poor and Verdu (1995) established an upper bound for the reliability function of arbitrary single-user discrete-time channels with memory. They also conjectured that their bound is tight for all coding rates. We demonstrate via a counterexample involving memoryless binary erasure channels (BECs) that the Poor-Verdu upper bound is not tight at low rates. We conclude by examining possible improvements to this bound.

A joint source-channel hybrid digital-analog (HDA) vector quantization (VQ) system is presented. The main advantage of the new VQ-based HDA system is that it achieves excellent rate-distortion-capacity performance at the design signal-to-noise ratio (SNR) while maintaining a "graceful improvement" characteristic at higher SNRs. It is demonstrated that, within the HDA framework, the parameters of the system can be optimized using an iterative procedure similar to that of channel-optimized vector quantizer design. Comparisons are made with three purely digital systems and one purely analog system. It is found that, at high SNRs, the VQ-based HDA system is superior to the other investigated systems. At low SNRs, the performance of the new scheme can be improved using the optimization procedure and using soft decoding in the digital part of the system. These results demonstrate that the introduced scheme provides an attractive method for terrestrial broadcasting applications.

Csiszar's (1995) forward /spl beta/-cutoff rate (given a fixed /spl beta/>0) for a discrete source is defined as the smallest number R/sub 0/ such that for every R>R/sub 0/, there exists a sequence of fixed-length codes of rate R with probability of error asymptotically vanishing as e/sup -n/spl beta/(R-R0)/. For a discrete memoryless source (DMS), the forward /spl beta/-cutoff rate is shown by Csiszar to be equal to the source Renyi (1961) entropy. An analogous concept of reverse /spl beta/-cutoff rate regarding the probability of correct decoding is also characterized by Csiszar in terms of the Renyi entropy. In this work, Csiszar's results are generalized by investigating the /spl beta/-cutoff rates for the class of arbitrary discrete sources with memory. It is demonstrated that the limsup and liminf Renyi entropy rates provide the formulas for the forward and reverse /spl beta/-cutoff rates, respectively. Consequently, new fixed-length source coding operational characterizations for the Renyi entropy rates are established.

In this work, we examine the existence and the computation of the Renyi divergence rate, lim/sub n/spl rarr//spl infin// 1/n D/sub /spl alpha//(p/sup (n)//spl par/q/sup (n)/), between two time-invariant finite-alphabet Markov sources of arbitrary order and arbitrary initial distributions described by the probability distributions p/sup (n)/ and q/sup (n)/, respectively. This yields a generalization of a result of Nemetz (1974) where he assumed that the initial probabilities under p/sup (n)/ and q/sup (n)/ are strictly positive. The main tools used to obtain the Renyi divergence rate are the theory of nonnegative matrices and Perron-Frobenius theory. We also provide numerical examples and investigate the limits of the Renyi divergence rate as /spl alpha//spl rarr/1 and as /spl alpha//spl darr/0. Similarly, we provide a formula for the Renyi entropy rate lim/sub n/spl rarr//spl infin// 1/n H/sub /spl alpha//(p/sup (n)/) of Markov sources and examine its limits as /spl alpha//spl rarr/1 and as /spl alpha//spl darr/0. Finally, we briefly provide an application to source coding.

In this work, the design of a q-bit (scalar and vector) soft-decision demodulator for Gaussian channels with binary phase-shift keying modulation is investigated. The demodulator is used in conjunction with a soft-decision channel-optimized vector quantization (COVQ) system. The COVQ is constructed for an expanded (q>1) discrete channel consisting of the concatenation of the modulator, the Gaussian channel, and the demodulator. It is found that as the demodulator resolution q increases, the capacity of the expanded channel increases, resulting in an improvement of the COVQ performance. Consequently, the soft-decision demodulator is designed to maximize the capacity of the expanded channel. Three Gaussian channel models are considered as follows: (1) additive white Gaussian noise channels; (2) additive colored Gaussian noise channels; and (3) Gaussian channels with intersymbol interference. Comparisons are made with (a) hard-decision COVQ systems, (b) COVQ systems which utilize interleaving, and (c) an unquantized (q=/spl infin/) soft-decision decoder proposed by Skoglund and Hedelin (1999). It is shown that substantial improvements can be achieved over COVQ systems which utilize hard decision demodulation and/or channel interleaving. The performance of the proposed COVQ system is comparable with the system by Skoglund and Hedelin-though its computational complexity is substantially less.

We consider modulo-q additive noise channels, where the noise process is a stationary irreducible and aperiodic Markov chain of order k. We begin by investigating the capacity-cost function (C(/spl beta/)) of such additive-noise channels without feedback. We establish a tight upper bound to (C(/spl beta/)) which holds for general (not necessarily Markovian) stationary q-ary noise processes. This bound constitutes the counterpart of the Wyner-Ziv lower bound to the rate-distortion function of stationary sources with memory. We also provide two simple lower bounds to C(/spl beta/) which along with the upper bound can be easily calculated using the Blahut algorithm for the computation of channel capacity. Numerical results indicate that these bounds form a tight envelope on C(/spl beta/). We next examine the effect of output feedback on the capacity-cost function of these channels and establish a lower bound to the capacity-cost function with feedback (C/sub FB/(/spl beta/)). We show (both analytically and numerically) that for a particular feedback encoding strategy and a class of Markov noise sources, the lower bound to C/sub FB/(/spl beta/) is strictly greater than C(/spl beta/). This demonstrates that feedback can increase the capacity-cost function of discrete channels with memory.

We consider a Bonferroni-type lower bound due to Kounias (1968) on the probability of a finite union. The bound is expressed in terms of only the individual and pairwise event probabilities; however, it suffers from requiring an exponentially complex search for its direct implementation. We address this problem by presenting a practical algorithm for its evaluation. This bound is applied together with two other bounds, a recent lower bound (the KAT bound) and a greedy algorithm implementation of an upper bound due to Hunter (1976), to examine the symbol error (P/sub a/) and bit error (P/sub b/) probabilities of an uncoded communication system used in conjunction with M-ary phase-shift keying (PSK)/quadrature amplitude (QAM) (PSK/QAM) modulations and maximum a posteriori (MAP) decoding over additive white Gaussian noise (AWGN) channels. It is shown that the bounds-which can be efficiently computed-provide an excellent estimate of the error probabilities over the entire range of the signal-to-noise ratio (SNR) E/sub b//N/sub 0/. The new algorithmic bound and the greedy bound are particularly impressive as they agree with the simulation results even during very severe channel conditions.

An unequal error protection approach for the reliable communication of visual information over additive white Gaussian noise channels is proposed and studied. This method relies on a bandwidth-efficient coded modulation scheme that employs selective channel coding and transmission energy allocation in conjunction with sequence maximum a posteriori soft-decision detection. Experimental results indicate that this scheme exhibits graceful performance degradation as the channel conditions deteriorate and provides substantial objective and subjective improvements over uncoded and equal-error protection systems. Coding gains of up to 4 dB in E/sub b//N/sub o/ are achieved.

We propose a segmentation method based on Polya's (1931) urn model for contagious phenomena. A preliminary segmentation yields the initial composition of an urn representing the pixel. The resulting urns are then subjected to a modified urn sampling scheme mimicking the development of an infection to yield a segmentation of the image into homogeneous regions. This process is implemented using contagion urn processes and generalizes Polya's scheme by allowing spatial interactions. The composition of the urns is iteratively updated by assuming a spatial Markovian relationship between neighboring pixel labels. The asymptotic behavior of this process is examined and comparisons with simulated annealing and relaxation labeling are presented. Examples of the application of this scheme to the segmentation of synthetic texture images, ultra-wideband synthetic aperture radar (UWB SAR) images and magnetic resonance images (MRI) are provided.

The conventional definitions of the source coding rate and of channel capacity require the existence of reliable codes for all sufficiently large block lengths. Alternatively, if it is required that good codes exist for infinitely many block lengths, then optimistic definitions of source coding rate and channel capacity are obtained. In this work, formulas for the optimistic minimum achievable fixed-length source coding rate and the minimum /spl epsi/-achievable source coding rate for arbitrary finite-alphabet sources are established. The expressions for the optimistic capacity and the optimistic /spl epsi/-capacity of arbitrary single-user channels are also provided. The expressions of the optimistic source coding rate and capacity are examined for the class of information stable sources and channels, respectively. Finally, examples for the computation of optimistic capacity are presented.

We propose a segmentation method based on Polya's urn model for contagious phenomena. Initial labeling of the pixel is obtained using a Maximum Likelihood (ML) estimate or the Nearest Mean Classifier (NMC), which are used to determine the initial composition of an urn representing the pixel. The resulting urns are then subjected to a modified urn sampling scheme mimicking the development of an infection to yield a segmentation of the image into homogeneous regions. Examples of the application of this scheme to the segmentation of synthetic texture images, Ultra-Wideband Synthetic Aperture Radar (UWB SAR) images and Magnetic Resonance Images (MRI) are provided.

This correspondence addresses the use of a joint source-channel coding strategy for enhancing the error resilience of images transmitted over a binary channel with additive Markov noise. In this scheme, inherent or residual (after source coding) image redundancy is exploited at the receiver via a maximum a posteriori (MAP) channel detector. This detector, which is optimal in terms of minimizing the probability of error, also exploits the larger capacity of the channel with memory as opposed to the interleaved (memoryless) channel. We first consider MAP channel decoding of uncompressed two-tone and bit-plane encoded grey-level images. Next, we propose a scheme relying on unequal error protection and MAP detection for transmitting grey-level images compressed using the discrete cosine transform (DCT), zonal coding, and quantization. Experimental results demonstrate that for various overall (source and channel) operational rates, significant performance improvements can be achieved over interleaved systems that do not incorporate image redundancy.

A rate-distortion theorem for arbitrary (not necessarily stationary or ergodic) discrete-time finite-alphabet sources is given. This result, which provides the expression of the minimum /spl epsiv/-achievable fixed-length coding rate subject to a fidelity criterion, extends a recent data compression theorem by Steinberg and Verdu (see ibid., vol.42, p.63-86 (Jan. 1996).

Joint source-channel coding for stationary memoryless and Gauss-Markov sources and binary Markov channels is considered. The channel is an additive-noise channel where the noise process is an Mth-order Markov chain. Two joint source-channel coding schemes are considered. The first is a channel-optimized vector quantizer-optimized for both source and channel. The second scheme consists of a scalar quantizer and a maximum a posteriori detector. In this scheme, it is assumed that the scalar quantizer output has residual redundancy that can be exploited by the maximum a posteriori detector to combat the correlated channel noise. These two schemes are then compared against two schemes which use channel interleaving. Numerical results show that the proposed schemes outperform the interleaving schemes. For very noisy channels with high noise correlation, gains of 4-5 dB in signal-to-noise ratio are possible.

A joint source-channel coding technique is proposed for transmitting grey-level images over a binary channel with additive Markov noise. In this scheme, inherent or residual (after source coding) image redundancy is exploited at the receiver in an appropriately designed MAP detector. Two methods are presented. The first method relies on MAP decoding of uncompressed bit-plane encoded images. The second method deals with compressed images (DCT coded and quantized) and uses unequal error protection along with the MAP detection procedure. Experimental results demonstrate that particularly during bad channel conditions, significant performance improvements can be achieved.

We consider the problem of reliably transmitting CELP-encoded speech over noisy communication channels. Our objective is to design efficient coding/decoding schemes for the transmission of the CELP line spectral parameters (LSPs) over very noisy channels. We begin by quantifying the amount of "residual redundancy" inherent in the LSPs of Federal Standard 1016 CELP. This is done by modeling the LSPs as first- and second-order Markov chains. Two models for LSP generation are proposed; the first model characterizes the intraframe correlation exhibited by the LSPs, while the second model captures both intraframe and interframe correlation. By comparing the entropy rates of the models thus constructed with the CELP rates, it is shown that as many as one-third of the LSP bits in every frame of speech are redundant. We next consider methods by which this residual redundancy can be exploited by an appropriately designed channel decoder. Before transmission, the LSPs are encoded with a forward error control (FEC) code; we consider both block (Reed-Solomon) codes and convolutional codes. Soft-decision decoders that exploit the residual redundancy in the LSPs are implemented assuming additive white Gaussian noise (AWGN) and independent Rayleigh fading environments. Simulation results employing binary phase-shift keying (BPSK) indicate coding gains of 2-5 dB over soft-decision decoders that do not exploit the residual redundancy.

We consider maximum a posteriori (MAP) detection of a binary asymmetric Markov source transmitted over a binary Markov channel. The MAP detector observes a long (but finite) sequence of channel outputs and determines the most probable source sequence. In some cases, the MAP detector can be implemented by simple rules such as the "believe what you see" rule or the "guess zero (or one) regardless of what you see" rule. We provide necessary and sufficient conditions under which this is true. When these conditions are satisfied, the exact bit error probability of the sequence MAP detector can be determined. We examine in detail two special cases of the above source: (i) binary independent and identically distributed (i.i.d.) source and (ii) binary symmetric Markov source. In case (i), our simulations show that the performance of the MAP detector improves as the channel noise becomes more correlated. Furthermore, a comparison of the proposed system with a (substantially more complex) traditional tandem source-channel coding scheme portrays superior performance for the proposed scheme at relatively high channel bit error rates. In case (ii), analytical as well as simulation results show the existence of a "mismatch" between the source and the channel (the performance degrades as the channel noise becomes more correlated). This mismatch is reduced by the use of a simple rate-one convolutional encoder.

We introduce a novel class of nonlinear stochastic filters based on contagion urn schemes. These filters which rely on biologically inspired sampling processes, offer good restoration results on heavily corrupted binary images.

We consider discrete-time finite alphabet channels with additive random noise. We show that output feedback does not increase the capacity of such channels. This result holds in the most general case; i.e., for arbitrary additive noise processes.>

Consider an additive noise channel with inputs and outputs in the field GF(q) where q>2; every time a symbol is transmitted over such a channel, there are q-1 different errors that can occur, corresponding to the q-1 non-zero elements that the channel can add to the transmitted symbol. In many data communication/storage systems, there are some errors that occur much more frequently than others; however, traditional error correcting codes/spl minus/designed with respect to the Hamming metric/spl minus/treat each of these q-1 errors the same. Fuja and Heegard (1990) have designed a class of codes, called focused error control codes, that offer different levels of protection against "common" and "uncommon" errors; the idea is to define the level of protection in a way based not only on the number of errors, but the kind as well. In this paper, the performance of these codes is analyzed with respect to idealized "skewed" channels as well as realistic non-binary modulation schemes. It is shown that focused codes, used is conjunction with PSK and QAM signaling, can provide more than 1.0 dB of additional coding gain when compared with Reed-Solomon codes for small blocklengths.>

We introduce a binary additive communication channel with memory. The noise process of the channel is generated according to the contagion model of G. Polya (1923); our motivation is the empirical observation of Stapper et al. (1980) that defects in semiconductor memories are well described by distributions derived from Polya's urn scheme. The resulting channel is stationary but not ergodic, and it has many interesting properties. We first derive a maximum likelihood (ML) decoding algorithm for the channel; it turns out that ML decoding is equivalent to decoding a received vector onto either the closest codeword or the codeword that is farthest away, depending on whether an "apparent epidemic" has occurred. We next show that the Polya-contagion channel is an "averaged" channel in the sense of Ahlswede (1968) and others and that its capacity is zero. Finally, we consider a finite-memory version of he Polya-contagion model; this channel is (unlike the original) ergodic with a nonzero capacity that increases with increasing memory.>