Noiseless coding of correlated information sources

Correlated information sequencescdots ,X_{-1},X_0,X_1, cdotsandcdots,Y_{-1},Y_0,Y_1, cdotsare generated by repeated independent drawings of a pair of discrete random variablesX, Yfrom a given bivariate distributionP_{XY} (x,y). We determine the minimum number of bits per characterR_XandR_Yneeded to encode these sequences so that they can be faithfully reproduced under a variety of assumptions regarding the encoders and decoders. The results, some of which are not at all obvious, are presented as an admissible rate regionmathcal{R}in theR_X - R_Yplane. They generalize a similar and well-known result for a single information sequence, namelyR_X geq H (X)for faithful reproduction.     

Network information flow

We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a “fluid” which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems     

A variable-length source coding theorem for correlated information sources

A variable-length source coding theorem is proved for a pair of discrete memoryless correlated information sources. The average length of codewords per source letter for source X provided the side information Y is bounded below by the conditional entropy H(X|Y) and above by the same entropy plus J/L where L is the number of source letters encoded and J is the size of ensemble Y. The Huffman encoding procedure is also generalized for this case.     

Broadcast channels with arbitrarily correlated sources

A new coding theorem for the broadcast channel with arbitrarily correlated sources is presented. The result covers all the previously established coding techniques. In particular, it includes Marton's coding theorem as a properly special case.     

Multiple access channels with arbitrarily correlated sources

Let{(U_{i},V_{i})}_{i=1}^{n}be a source of independent identically distributed (i.i.d.) discrete random variables with joint probability mass functionp(u,v)and common partw=f(u)=g(v)in the sense of Witsenhausen, Gacs, and Körner. It is shown that such a source can be sent with arbitrarily small probability of error over a multiple access channel (MAC){cal X_{1} times cal X_{2},cal Y,p(y|x_{1},x_{2})},with allowed codes{x_{l}(u), x_{2}(v)}if there exist probability mass functionsp(s), p(x_{1}|s,u),p(x_{2}|s,v), such thatH(U|V)H(V|U )H(U,V|W)H(U,V)mbox{where}p(s,u,v,x_{1},x_{2},y), Xl, X2, y)=p(s)p(u,v)p(x_{1}|u,s)p(x_{2}|v,s)p(y|x_{1},x_{2}).lifts region includes the multiple access channel region and the Slepian-Wolf data compression region as special cases.     

Universal coding for correlated sources with linked encoders

On the coding for correlated sources we extend the Slepian-Wolf (1973) data compression system (called the SW system) to define a new system (called the SWL system), where two separate encoders of the SW system are mutually linked. Determining the optimal error exponent for all rates inside the admissible rate region remains an open problem for the SW system. We completely solve this problem for the SWL system, and show that the optimal exponents can be achieved by universal codes. Furthermore, it is shown that the linkage of two encoders does not extend the admissible rate region and does not even improve the exponent of correct decoding outside this region. The zero error data transmission problem for the SWL system is also considered. We determine the zero error rate region, the admissible rate region under the condition that the decoding error probability is strictly zero, and show that this region can be attained by universal codes. Furthermore, we make it clear that the linkage of encoders enlarges the zero error rate region. It is interesting to note that the above results for the SWL system correspond in some sense to the previous results for the discrete memoryless channel with feedback     

Rate-distortion for correlated sources with partially separated encoders

We resolve some open problems concerning the encoding of a pair of correlated sources with respect to a fidelity criterion. Two encoders are used. One encoder observes only the output of the first source, while the other is supplied both with the second source output and with partial information about the first source at some predetermined rate. A general coding theorem is proved which established that{cal S} ast, a certain region defined in terms of "single-letter" information theoretic quantities, is an inner bound to the region of all attainable vectors of rates and distortions. For certain cases of interest the converse is proved, too, thereby establishing the rate-distortion region for these cases.     

Successive encoding of correlated sources

The encoding of a discrete memoryless multiple source{( X_{i}, Y_{i})}_{i=1}^{infty}for reconstruction of a sequence{Z_{i}}_{i=1}^{infty}}, withZ_{i} = F( X_{i}, Y_{i}); i = 1,2, cdotsis considered. We require that the encoding should be such that{X_{i}}_{i=1}^{infty}is encoded first without any consideration of{Y_{i}}_{i=1}^{infty}, while in a second part of the encoding, this latter sequence is encoded based on knowledge of the outcome of the first encoding. The resulting scheme is called successive encoding. We find general outer and inner bounds for the corresponding set of achievable rates along with a complete single letter characterization for the special caseH( X_{i}|Z_{i}, Y_{i}) = 0. Comparisons with the Slepian-Wolf problem and the Ahlswede-Korner-Wyner side information problem are carried out.     

Discrete-time model for multimedia correlated sources

A multimedia source model is presented. To capture the intermedia synchronisation requirements of the streams in the multimedia flow, the model is defined as the superposition of heterogeneous correlated monomedia arrival processes. Transition probability matrices and correlation functions are calculated to allow any designer to investigate network performance by means of well-known analytical techniques     

On zero-error coding of correlated sources

The problem of separate zero-error coding of correlated sources is considered. Inner and outer single-letter bounds are established for the achievable rate region, and conditions for their coincidence are investigated. It is shown that successive encoding combined with time sharing is not always an optimal coding strategy. Conditions for its optimality are derived. The inner bound to the achievable rate region follows as a special case of the single-letter characterization of a generalized zero-error multiterminal rate-distortion problem. The applications of this characterization to a problem of remote computing are also explored. Other results include (i) a product-space characterization of the achievable rates, (ii) bounds for finite block length, and (iii) asymptotic fixed-length rates.     

LDPC-based channel coding of correlated sources with iterative joint decoding

This letter considers low-density parity-check (LDPC) coding of correlated binary sources and a novel iterative joint channel decoding without communication of any side information. We demonstrate that depending on the extent of the source correlation, additional coding gains can be obtained. Two stages of iterative decoding are employed. During global iterations, updated estimates of the source correlation are obtained and passed on to the sum-product decoder that performs local iterations with a predefined stopping criterion and/or a maximum number of local decoding iterations. Simulation results indicate that very few global iterations (2-5) are sufficient to reap significant benefits from implicit knowledge of source correlation. Finally, we provide analytical performance bounds for our iterative joint decoder and comparisons with sample simulation results.     

Separation of independent sources from correlated inputs

The characterization of independent stationary stochastic components (sources), is generally achieved by using the spectral matrix of partially correlated measurements, which are linearly related to the components of interest. In the general case where no assumptions are made concerning the way the sources are mixed on the measurements, the spectral matrix is not able to extract the true sources. While spectral analysis only uses second-order properties of independent stochastic sources, a procedure based on higher-order analysis (fourth-order cross cumulants) is developed. This approach leads to a complete identification of the sources     

Generalized Gaussian modeling of correlated signal sources

A generalized Gaussian model for correlated signal sources is introduced. The probability density function of a first-order autoregressive process driven by generalized Gaussian white noise is approximated by a generalized Gaussian probability density function. The interdependence between the correlation coefficient and the shape parameter of the first-order autoregressive process and the shape parameter of the driving noise is investigated. Application of the proposed method for modeling of probability density functions of transform and subband coefficients is considered     

Low-density parity-check matrices for coding of correlated sources

Linear codes for a coding problem of correlated sources are considered. It is proved that we can construct codes by using low-density parity-check (LDPC) matrices with maximum-likelihood (or typical set) decoding. As applications of the above coding problem, a construction of codes is presented for multiple-access channel with correlated additive noises and a coding theorem of parity-check codes for general channels is proved.     

Multiple-antenna capacity in correlated Rayleigh fading with channel covariance information

We analyze a mobile multiple input multiple output wireless link with M transmit and N receive antennas operating in a spatially correlated Rayleigh flat fading environment. Only the correlations between the channel coefficients are assumed to be known at the transmitter and the receiver. The channel coefficients are correlated in space and uncorrelated in time from one coherence interval to another. These coefficients remain constant for a coherence interval of T symbol periods after which they change to another independent realization according to the spatial correlation model. For this system we characterize the structure of the input signal that achieves capacity. The capacity achieving transmit signal is expressed as the product of an isotropically distributed unitary matrix, an independent nonnegative diagonal matrix and a unitary matrix whose columns are the eigenvectors of the transmit fade covariance matrix. For the case where the number of transmit antennas M is larger than the channel coherence interval T, we show that the channel capacity is independent of the smallest M-T eigenvalues of the transmit fade covariance matrix. In contrast to the previously reported results for the spatially white fading model where adding more transmit antennas beyond the coherence interval length (M>T) does not increase capacity, we find that additional transmit antennas always increase capacity as long as their channel fading coefficients are spatially correlated with the other antennas. We show that for fast hopping or fast fading systems (T=1) with only channel covariance information available to the transmitter and receiver, transmit fade correlations are beneficial. Mathematically, we prove this by showing that capacity is a Schur-convex function of the vector of eigenvalues of the transmit fade correlation matrix. We also show that the maximum possible capacity gain due to transmitter fade correlations is 10logM dB.     

Resolving uncorrelated and correlated sources by linear prediction

The resolution and the estimation error are investigated for two linear prediction (LP) algorithms for bearing estimation with uniform linear array of sensors, in the presence of incoherent and coherent sources: the Burg algorithm (BA) and the generalized Burg algorithm (GBA). The superresolution is easily achieved with both algorithms when the sources are incoherent. For coherent sources, however, the BA estimate is somewhat more sensitive to the magnitude and the phase of the intersignal correlation than the GBA, thereby resulting in the increased error in the bearing estimates.     

Compression of correlated binary sources using turbo codes

We propose the use of punctured turbo codes for compression of correlated binary sources. Compression is achieved because of puncturing. The resulting performance is close to the theoretical limit provided by the Slepian-Wolf (1973) theorem. No information about the correlation between sources is required in the encoding process. The proposed source decoder utilizes iterative schemes, and performs well even when the correlation between the sources is not known in the decoder, since it can be estimated jointly with the iterative decoding process