Joint Source–Channel Coding Error Exponent for Discrete Communication Systems With Markovian Memory

We study the error exponent, $E_{J}$, for reliably transmitting a discrete stationary ergodic Markov (SEM) source ${mmb Q}$ over a discrete channel ${mmb W}$ with additive SEM noise via a joint source–channel (JSC) code. We first establish an upper bound for $E_{J}$ in terms of the RÉnyi entropy rates of the source and noise processes. We next investigate the analytical computation of $E_{J}$ by 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 CsiszÁr'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 $E_{J}$ with the tandem (separate) coding exponent $E_{T}$. We show that as in the case of memoryless source–channel pairs $E_{J}leq 2E_{T}$ and we provide explicit conditions for which $E_{J}> E_{T}$. Numerical results indicate that $E_{J}thickapprox 2E_{T}$ for many SEM source–channel pairs, hence illustrating a substantial advantage of JSC coding over tandem coding for systems with Markovian memory.      

Improved bounds for the rate loss of multiresolution source codes

We present new bounds for the rate loss of multiresolution source codes (MRSCs). Considering an M-resolution code, the rate loss at the ith resolution with distortion D/sub i/ is defined as L/sub i/=R/sub i/-R(D/sub i/), where R/sub i/ is the rate achievable by the MRSC at stage i. This rate loss describes the performance degradation of the MRSC compared to the best single-resolution code with the same distortion. For two-resolution source codes, there are three scenarios of particular interest: (i) when both resolutions are equally important; (ii) when the rate loss at the first resolution is 0 (L/sub 1/=0); (iii) when the rate loss at the second resolution is 0 (L/sub 2/=0). The work of Lastras and Berger (see ibid., vol.47, p.918-26, Mar. 2001) gives constant upper bounds for the rate loss of an arbitrary memoryless source in scenarios (i) and (ii) and an asymptotic bound for scenario (iii) as D/sub 2/ approaches 0. We focus on the squared error distortion measure and (a) prove that for scenario (iii) L/sub 1/<1.1610 for all D/sub 2/相似文献   

Network information flow with correlated sources

Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G=(V,E), where V={v/sub 0/v/sub 1/...v/sub n/} and E/spl sube/V/spl times/V. If (v/sub i/,v/sub j/)/spl isin/E, then node i can send messages to node j over a discrete memoryless channel (DMC) (X/sub ij/,p/sub ij/(y|x),Y/sub ij/), of capacity C/sub ij/. The channels are independent. Each node v/sub i/ gets to observe a source of information U/sub i/(i=0...M), with joint distribution p(U/sub 0/U/sub 1/...U/sub M/). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M+1 nodes (v/sub 0/ by convention) must have received enough information to reproduce the entire field of observations (U/sub 0/U/sub 1/...U/sub M/), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if H(U/sub s/ | U/sub S(c)/) < /spl Sigma//sub i/spl isin/S,j/spl isin/S(c)/ for all S/spl sube/{0...M},S/spl ne/O,0/spl isin/S(c). Our main finding is that in this setup, a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.     

Achievable key rates for universal simulation of random data with respect to a set of statistical tests

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

Rate-distortion optimized hybrid error control for real-time packetized video transmission.

The problem of application-layer error control for real-time video transmission over packet lossy networks is commonly addressed via joint source-channel coding (JSCC), where source coding and forward error correction (FEC) are jointly designed to compensate for packet losses. In this paper, we consider hybrid application-layer error correction consisting of FEC and retransmissions. The study is carried out in an integrated joint source-channel coding (IJSCC) framework, where error resilient source coding, channel coding, and error concealment are jointly considered in order to achieve the best video delivery quality. We first show the advantage of the proposed IJSCC framework as compared to a sequential JSCC approach, where error resilient source coding and channel coding are not fully integrated. In the USCC framework, we also study the performance of different error control scenarios, such as pure FEC, pure retransmission, and their combination. Pure FEC and application layer retransmissions are shown to each achieve optimal results depending on the packet loss rates and the round-trip time. A hybrid of FEC and retransmissions is shown to outperform each component individually due to its greater flexibility.     

On Joint Source and Channel Coding Using Trellis Coded CPM: Analytical Bounds on the Channel Distortion

Joint source and channel coding (JSCC) using trellis coded quantization (TCQ) in conjunction with trellis coded continuous phase modulation (CPM) is studied. The channel is assumed to be the additive white gaussian noise (AWGN) channel. Analytical bounds on the channel distortion for the investigated systems with maximum-likelihood sequence detection (MLSD) are developed. The bounds are based on the transfer function technique, which was modified and generalized to include continuous-amplitude discrete-time signals. For a memoryless uniform source, the constructed bounds for the investigated systems are shown to be asymptotically tight for increasing channel signal-to-noise ratio (SNR) values. For a memoryless nonuniform source, the constructed bounds are not as tight as the one for the uniform source, however, it still can be used as an indication to how the system performs. It is concluded that the minimum Euclidean distance of the system alone is not enough to evaluate the performance of the considered systems. The number of error events having minimum Euclidean distance and the total distortion caused by those error events also affect the asymptotic performance. This work provides an analysis tool for the investigated systems. The analysis method is very general. It may be applied to any trellis based JSCC schemes.     

Variation of the Electrical Characteristics of an Inhomogeneous Microstrip Line with the Dielectric Constant of the Substrate and with the Geometrical Dimensions (Short Papers)

Studying systematically the variations of electrical characteristics of microstrip lines with the width w of the line, the thickness h, and the dielectric constant epsilon/sub r/ of the substrate, we have obtained a perfect linear variation with epsilon/sub r/. Then using a least squares method, we have been able to give an analytical expression of capacitances usable for 1 /spl les/ epsilon/sub r/ /spl les/ 100 and 0.04 /spl les/ w/h /spl les/ 10. The importance of this result is that we can give impedances and phase velocities without any computation.     

Progressive transmission of images over memoryless noisy channels

An embedded source code allows the decoder to reconstruct the source progressively from the prefixes of a single bit stream. It is desirable to design joint source-channel coding schemes which retain the capability of progressive reconstruction in the presence of channel noise or packet loss. Here, we address the problem of joint source-channel coding of images for progressive transmission over memoryless bit error or packet erasure channels. We develop a framework for encoding based on embedded source codes and embedded error correcting and error detecting channel codes. For a target transmission rate, we provide solutions and an algorithm for the design of optimal unequal error/erasure protection. Three performance measures are considered: the average distortion, the average peak signal-to-noise ratio, and the average useful source coding rate. Under the assumption of rate compatibility of the underlying channel codes, we provide necessary conditions for progressive transmission of joint source-channel codes. We also show that the unequal error/erasure protection policies that maximize the average useful source coding rate allow progressive transmission with optimal unequal protection at a number of intermediate rates     

Random-Coding Lower Bounds for the Error Exponent of Joint Quantization and Watermarking Systems

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.     

Improved-performance, InGaAs/InGaAsP (/spl lambda/=980 nm) asymmetric broad-waveguide diode lasers via waveguide-core doping

Doping the waveguide core (p=2/spl times/10/sup 17/ cm/sup -1/) in asymmetric-waveguide InGaAs/InGaAsP, two-quantum-well diode lasers (/spl lambda/=980 nm) raises the injection efficiency to 90% and decreases the threshold-current density, J/sub th/. For 2 mm long, 100 /spl mu/m wide stripe, uncoated chips J/sub th/ decreases from /spl sim/188 A/cm/sup 2/ to /spl sim/150 A/cm/sup 2/. High characteristic temperatures for J/sub th/ and the slope efficiency are obtained: T/sub 0/=215K and T/sub 1/=600K.     

Entropy and the law of small numbers

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when S/sub n/=/spl Sigma//sub i=1//sup n/X/sub i/ is the sum of the (possibly dependent) binary random variables X/sub 1/,X/sub 2/,...,X/sub n/, with E(X/sub i/)=p/sub i/ and E(S/sub n/)=/spl lambda/, then D(P(S/sub n/)/spl par/Po(/spl lambda/)) /spl les//spl Sigma//sub i=1//sup n/p/sub i//sup 2/+[/spl Sigma//sub i=1//sup n/H(X/sub i/)-H(X/sub 1/,X/sub 2/,...,X/sub n/)] where D(P(S/sub n/)/spl par/Po(/spl lambda/)) is the relative entropy between the distribution of S/sub n/ and the Poisson (/spl lambda/) distribution. The first term in this bound measures the individual smallness of the X/sub i/ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the X/sub i/ are independent, the following sharper bound is established: D(P(S/sub n/)/spl par/Po(/spl lambda/))/spl les/1//spl lambda/ /spl Sigma//sub i=1//sup n/ ((p/sub i//sup 3/)/(1-p/sub i/)) and it is also generalized to the case when the X/sub i/ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.     

Slepian-Wolf coding over broadcast channels

We discuss reliable transmission of a discrete memoryless source over a discrete memoryless broadcast channel, where each receiver has side information (of arbitrary quality) about the source unknown to the sender. When there are K=2 receivers, the optimum coding strategy using separate and stand-alone source and channel codes is to build two independent binning structures and send bin indices using degraded message sets through the channel, yielding a full characterization of achievable rates. However, as we show with an example, generalization of this technique to multiple binning schemes does not fully resolve the K>2 case. Joint source-channel coding, on the other hand, allows for a much simpler strategy (i.e., with no explicit binning) yielding a successful single-letter characterization of achievable rates for any Kges2. This characterization, which utilizes a trivial outer bound to the capacity region of general broadcast channels, is in terms of marginal source and channel distributions rather than a joint source-channel distribution. This contrasts with existing results for other multiterminal scenarios and implies that optimal schemes achieve "operational separation." On the other hand, it is shown with an example that an optimal joint source-channel coding strategy is strictly advantageous over the combination of stand-alone source and channel codes, and thus "informational separation" does not hold     

Two-way successively refined joint source-channel coding

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

Prime-length real-valued polynomial residue division algorithms

One class of efficient algorithms for computing a discrete Fourier transform (DFT) is based on a recursive polynomial factorization of the polynomial 1-z/sup -N/. The Bruun algorithm is a typical example of such algorithms. Previously, the Bruun algorithm, which is applicable only when system lengths are powers of two in its original form, is generalized and modified to be applicable to the case when the length is other than a power of two. This generalized algorithm consists of transforms T/sub d,f/ with prime d and real f in the range 0/spl les/f<0.5. T/sub d,0/ computes residues X(z)mod(1-z/sup -2/) and X(z)mod(1-2 cos(/spl pi/k/d)z/sup -1/+z/sup -2/), k=1, 2, ..., d-1, and T/sub d,f/ (f /spl ne/0) computes residues X(z)mod(1-2cos(2/spl pi/(f+k)/d)z/sup -1/+z/sup -2/), k=0, 1, ..., d-1 for a given real signal X(z) of length 2d. The purpose of this paper is to find efficient algorithms for T/sub d,f/. First, polynomial factorization algorithms are derived for T/sub d,0/ and T/sub d,1/4/. When f is neither 0 nor 1/4, it is not feasible to derive a polynomial factorization algorithm. Two different implementations of T/sub d,f/ for such f are derived. One implementation realizes T/sub d,f/ via a d-point DFT, for which a variety of fast algorithms exist. The other implementation realizes T/sub d,f/ via T/sub d, 1/4/, for which the polynomial factorization algorithm exists. Comparisons show that for d/spl ges/5, these implementations achieve better performance than computing each output of T/sub d,f/ separately.     

Universal Zero-Delay Joint Source–Channel Coding

We consider zero-delay joint source-channel coding of individual source sequences for a general known channel. Given an arbitrary finite set of schemes with finite-memory (not necessarily time-invariant) decoders, a scheme is devised that does essentially as well as the best in the set on all individual source sequences. Using this scheme, we construct a universal zero-delay joint source-channel coding scheme that is guaranteed to achieve, asymptotically, the performance of the best zero-delay encoding-decoding scheme with a finite-state encoder and a Markov decoder, on all individual sequences. For the case where the channel is a discrete memoryless channel (DMC), we construct an implementable zero-delay joint source-channel coding scheme that is based on the "follow the perturbed leader" scheme of Gyoumlrgy for lossy source coding of individual sequences. Our scheme is guaranteed to attain asymptotically the performance of the best in the set of all encoding-decoding schemes with a "symbol-by-symbol" decoder (and arbitrary encoder), on all individual sequences     

Linear codes for sources and source networks: Error exponents, universal coding

For Slepian-Wolf source networks, the error exponents obtained by Körner,Marton, and the author are shown to be universally attainable by linear codes also. Improved exponents are derived for linear codes with "large rates." Specializing the results to simple discrete memoryless sources reveals their relationship to the random coding and expurgated bounds for channels with additive noise. One corollary is that there are universal linear codes for this class of channels which attain the random coding error exponent for each channel in the class. The combinatorial approach of Csiszár-Körner-Marton is used. In particular, all results are derived from a lemma specifying good encoders in terms of purely combinatorial properties.     

Discrete Chaos-I: Theory

We propose a definition of the discrete Lyapunov exponent for an arbitrary permutation of a finite lattice. For discrete-time dynamical systems, it measures the local (between neighboring points) average spreading of the system. We justify our definition by proving that, for large classes of chaotic maps, the corresponding discrete Lyapunov exponent approaches the largest Lyapunov exponent of a chaotic map when M/spl rarr//spl infin/, where M is the cardinality of the discrete phase space. In analogy with continuous systems, we say the system has discrete chaos if its discrete Lyapunov exponent tends to a positive number, when M/spl rarr//spl infin/. We present several examples to illustrate the concepts being introduced.     

Dissipative Parameters in Ferrites and Insertion Losses in Waveguide Y-Circulators Below Resonance

Extensive microwave loss measurements have been performed at frequencies from 1.3 to 11 GHz on below-resonance waveguide Y circulators loaded with a wide variety of ferrite and garnet compositions. Dissipative internal and external magnetic parameters have been measured on the same compositions. Also, dielectric loss measurements have been carried out. Two classes have been distinguished, defined by the following conditions: /spl omega//sub M/ / /spl omega/ /spl les/0.8 and 0.85 /spl les//spl omega//sub M/ / /spl omega/ /spl les/1.05. It is inferred that the (insertion loss) IL of such devices is independent of /spl Delta/H and mainly depends on the internal dissipative susceptibility x/sub i/" and on the dielectric loss tan /spl delta/. The relation of the IL versus x/sub i/" and tan /spl delta/ in the case /spl omega//sub M/ / /spl omega/ /spl les/0.8 is independent of frequency and given by the semiempirical equation IL= 10 log/sub 10/ (1-2.85 x/sub i/" - 1.60 tan /spl delta/ - 0.017)/sup -1/.     

On the design of layered space-time systems for autocoding

Hochwald et al.(see IEEE Trans. Inform. Theory, Nov. 2001) have recognized that arbitrarily reliable communication is possible in multiantenna systems with coding over only a single coherence interval. In particular, they showed that reliable communication is possible for all rates R/spl les/C/sub a/ with code words that extend over a single coherence interval when the number of transmit antennas and coherence interval (n,T)/spl rarr//spl infin/. They coined the names "autocoding" for this phenomenon and "autocapacity" for C/sub a/. They also proposed a signalling scheme based on random unitary matrices that achieves a significant fraction of this capacity. The main limitation, however, is that currently no decoder of reasonable complexity is known for this signalling scheme. We investigate the application of space-time layering to autocoding. We show that properly constructed layered systems can achieve the autocapacity with a reasonable complexity receiver composed of minimum mean-square error (MMSE) decision feedback multiuser detectors and single user decoders. In addition to this asymptotic result, we propose a specific layering approach, the threaded space-time layering, that combines generalized bit interleaved space-time coded modulation, iterative signal processing and pilot symbol assisted channel estimation. We show that this approach is well suited for practical systems with limited numbers of transmit antennas and small coherence intervals. Finally, we report simulation results that demonstrate the ability of the threaded approach to achieve significant fractions of the autocapacity with a realizable receiver. The simulation results also indicate significant performance gains over the Cayley differential space-time signalling scheme in certain scenarios.