On zero-error source coding with decoder side information

Let (X,Y) be a pair of random variables distributed over a finite product set V/spl times/W according to a probability distribution P(x,y). The following source coding problem is considered: the encoder knows X, while the decoder knows Y and wants to learn X without error. The minimum zero-error asymptotic rate of transmission is shown to be the complementary graph entropy of an associated graph. Thus, previous results in the literature provide upper and lower bounds for this minimum rate (further, these bounds are tight for the important class of perfect graphs). The algorithmic aspects of instantaneous code design are considered next. It is shown that optimal code design is NP-hard. An optimal code design algorithm is derived. Polynomial-time suboptimal algorithms are also presented, and their average and worst case performance guarantees are established.     

On Witsenhausen's zero-error rate for multiple sources

We investigate the problem of minimum rate zero-error source coding when there are several decoding terminals having different side information about the central source variable and each of them should decode in an error-free manner. For one decoder this problem was considered by Witsenhausen. The Witsenhausen rate of the investigated multiple source is the asymptotically achievable minimum rate. We prove that the Witsenhausen rate of a multiple source equals the Witsenhausen rate of its weakest element. The proof relies on a powerful result of Gargano, Korner, and Vaccaro about the zero-error capacity of the compound channel.     

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.     

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.     

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     

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.     

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.     

基于分离信源信道码的相关信源在有噪广播信道下的可靠和安全传输

从信息论的角度对相关信源在离散无记忆广播信道下可靠和安全传输的问题进行研究。2个信源经过有噪信道分别到达各自指定的目的节点并被无损恢复,同时还要保证信源信息对于非指定的目的节点要有一定的保密性。采用信源信道分离的随机码策略,得到相关信源在一般广播信道下能够可靠和安全传输的充分条件。当2个信源的公共信息为二者的互信息时,可获得最佳压缩传输效率,并且能够做到信源信息传输的部分绝对保密。当广播信道采用退化信源集或满足more capable广播信道性质时,得到了可靠和安全传输的充分必要条件,此时分离信源信道码为最优码。     

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.     

On the lower bound of zero-error capacity (Corresp.)

It is shown that the lower bound on zero-error capacityC_{0}as presented by Shannon [1] and Gallager [2] isln alpha, wherealphais the maximum number of channel input symbols, no two of which have a common output symbol.     

Independent key frame coding using correlated pixels in distributed video coding

A novel intra-coding technique is proposed that eliminates the requirement of a secondary coding scheme for coding the key frames in distributed video coding (DVC). The proposed technique uses the Slepian-Wolf theorem and Wyner-Ziv (WZ) coding with spatially predicted information to transmit the key-frames to the DVC decoder. Simulation results show that the proposed WZ-intra coding technique (WZ-I) can achieve up to 5 dB PSNR gain compared to MPEG-2 intra coding (MPEG-I) at the same bit rate with negligible computational cost to the encoder     

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.     

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     

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.     

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     

Space-time-Doppler block coding for correlated time-selective fading channels

Coping with time-selective fading channels is challenging but also rewarding, especially with multiantenna systems, where joint space-Doppler diversity and coding gains can be collected to enhance performance of wireless mobile links. These gains have not been quantified, and space-time coded systems maximizing joint space-Doppler benefits have not been designed. Based on a parsimonious basis expansion model for the underlying time-selective (and possibly correlated) channels, we quantify these gains in closed form. Furthermore, we develop space-time-Doppler coded systems that guarantee the maximum possible space-Doppler diversity, along with the largest coding gains within all linearly coded systems. Our three novel designs exploit knowledge of the maximum Doppler spread, and each offers a uniquely desirable tradeoff, including high spectral efficiency, low decoding complexity, and high performance. Our analytical results are confirmed by simulations and reveal the relative of merits of our three designs in comparison with an existing approach.     

On the zero-error capacity of a noisy channel with feedback (Corresp.)

It is shown by Shannon that the zero-error capacity of a noisy channel may be increased with feedback. However, feedback cannot improve the zero-error capacity of all memoryless channels. The graphs of discrete memoryless channels are classified on the basis of whether feedback increases the zero-error capacity or not.