Ergodicity of Markov channels

A Markov channel is a discrete information channel that includes as special cases the finite state channels and finite state codes of information theory. Kieffer and Rahe proved that one-sided and two-sided Markov channels have the following property: If the input source to a Markov channel is asymptotically mean stationary (AMS), then so is the resulting input-output process and hence the ergodic theorem and the Shannon-McMillan-Breiman theorem hold for the input-output process. Kieffer and Rahe also provided a sufficient condition for any AMS ergodic source to yield an AMS ergodic input-output process. New conditions for a Markov channel to have this ergodicity property are presented and discussed here. Several relations are developed among various classes of channels, including weakly ergodic, indecomposable, and strongly mixing channels. Some connections between Markov channels and the theory of nonhomogeneous Markov chains are also discussed.     

On source coding with side information via a multiple-access channel and related problems in multi-user information theory

A simple proof of the coding theorem for the multiple-access channel (MAC) with arbitrarily correlated sources (DMCS) of Cover-El Carnal-Salehi, which includes the results of Ahlswede for the MAC and of Slepian-Wolf for the DMCS and the MAC as special cases, is first given. A coding theorem is introduced and established for another type of source-channel matching problem, i.e., a system of source coding with side information via a MAC, which can be regarded as an extension of the Ahlswede-Körner-Wyner type noiseless coding system. This result is extended to a more general system with several principal sources and several side information sources subject to cross observation at the encoders in the sense of Han. The regions are shown to be optimal in special situations. Dueck's example shows that this is in general not the case for the result of Cover-El Gamal-Salehi and the present work. In another direction, the achievable rate region for the module-two sum source network found by Körner-Marton is improved. Finally, some ideas about a new approach to the source-channel matching problem in multi-user communication theory are presented. The basic concept is that of a correlated channel code. The approach leads to several new coding problems.     

New results on coding of stationary nonergodic sources

Two results on the coding of stationary nonergodic sources are presented. The first is a source coding theorem stating that there exist variable-rate codes with performance arbitrarily close to the rate-distortion function of the stationary nonergodic source. The second is a converse information transmission theorem. It is shown that the distortion which results when the source is transmitted across a channel with capacityCis no less than the least distortion achievable by fixed-rate codes with rateC.     

The art of signaling: fifty years of coding theory

In 1948 Shannon developed fundamental limits on the efficiency of communication over noisy channels. The coding theorem asserts that there are block codes with code rates arbitrarily close to channel capacity and probabilities of error arbitrarily close to zero. Fifty years later, codes for the Gaussian channel have been discovered that come close to these fundamental limits. There is now a substantial algebraic theory of error-correcting codes with as many connections to mathematics as to engineering practice, and the last 20 years have seen the construction of algebraic-geometry codes that can be encoded and decoded in polynomial time, and that beat the Gilbert-Varshamov bound. Given the size of coding theory as a subject, this review is of necessity a personal perspective, and the focus is reliable communication, and not source coding or cryptography. The emphasis is on connecting coding theories for Hamming and Euclidean space and on future challenges, specifically in data networking, wireless communication, and quantum information theory     

On joint source-channel coding for the Wyner-Ziv source and the Gel'fand-Pinsker channel

We consider the problem of lossy joint source-channel coding in a communication system where the encoder has access to channel state information (CSI) and the decoder has access to side information that is correlated to the source. This configuration combines the Wyner-Ziv (1976) model of pure lossy source coding with side information at the decoder and the Shannon/Gel'fand-Pinsker (1958, 1980) model of pure channel coding with CSI at the encoder. We prove a separation theorem for this communication system, which asserts that there is no loss in asymptotic optimality in applying, first, an optimal Wyner-Ziv source code and, then, an optimal Gel'fand-Pinsker channel code. We then derive conditions for the optimality of a symbol-by-symbol (scalar) source-channel code, and demonstrate situations where these conditions are met. Finally, we discuss a few practical applications, including overlaid communication where the model under discussion is useful.     

Sliding-block joint source/noisy-channel coding theorems

Sliding-block codes are nonblock coding structures consisting of discrete-time time-invariant possibly nonlinear filters. They are equivalent to time-invariant trellis codes. The coupling of Forney's rigorization of Shannon's random-coding/typical-sequence approach to block coding theorems with the strong Rohlin-Kakutani Theorem of ergodic theory is used to obtain a sliding-block coding theorem for ergodic sources and discrete memoryless noisy channels. Combining this result with a theorem on sliding-block source coding with a fidelity criterion yields a sliding-block information transmission theorem. Thus, the basic existence theorems of information theory hold for stationary nonblock structures, as well as for block codes.     

On a strong law in information stability (Corresp.)

The law of the iterated logarithm for the information density between channel input and output sequences is established when certain regularity conditions are imposed on both the input source and on the finite-memory channel. An application to the coding theorem and its converse is given.     

Coding and Common Reconstruction

This work studies problems of source and joint source-channel coding under the requirement that the encoder can produce an exact copy of the compressed source constructed by the decoder. This requirement, termed here as the common reconstruction constraint (CR), is satisfied automatically in rate-distortion theory for single sources. However, in the common formulation of problems of lossy source coding with side information at the decoder (the Wyner-Ziv problem), distributed source coding, and joint source-channel coding for networks, the destination can exploit the information it receives in a manner that cannot be exactly reproduced at the sender side. Some applications, like the transmission of sensitive medical information, may require that both sides-the sender and the receiver-will share a common version of the compressed data, for the purpose of future discussions or consulting. The purpose of this work is to study the implications of CR constraints on the achievable rates in scenarios of lossy source coding and lossy transmission of sources. Three problems are examined: source coding with side information at the decoder, simultaneous transmission of data and state over state-dependent channels, and joint source-channel coding for the degraded broadcast channel. Single-letter characterizations of the optimal performance are developed for these problems, under corresponding CR constraints. Implications of this constraint on problems of joint source-channel coding in networks are discussed.     

Hypothesis testing and information theory

The testing of binary hypotheses is developed from an information-theoretic point of view, and the asymptotic performance of optimum hypothesis testers is developed in exact analogy to the asymptotic performance of optimum channel codes. The discrimination, introduced by Kullback, is developed in a role analogous to that of mutual information in channel coding theory. Based on the discrimination, an error-exponent functione(r)is defined. This function is found to describe the behavior of optimum hypothesis testers asymptotically with block length. Next, mutual information is introduced as a minimum of a set of discriminations. This approach has later coding significance. The channel reliability-rate functionE(R)is defined in terms of discrimination, and a number of its mathematical properties developed. Sphere-packing-like bounds are developed in a relatively straightforward and intuitive manner by relatinge(r)andE (R). This ties together the aforementioned developments and gives a lower bound in terms of a hypothesis testing model. The result is valid for discrete or continuous probability distributions. The discrimination function is also used to define a source code reliability-rate function. This function allows a simpler proof of the source coding theorem and also bounds the code performance as a function of block length, thereby providing the source coding analog ofE (R).     

Source and Channel Coding for Cooperative Relaying

User cooperation is a powerful tool to combat fading and increase robustness for communication over wireless channels. Although it is doubtless a promising technique for enhancing channel reliability, its performance in terms of average source distortion is not clear since source-channel separation theorem fails under the most common nonergodic slow-fading channel assumption, when channel state information (CSI) is only available at the receiving terminals. This work sheds some light on the end-to-end performance of joint source-channel coding for cooperative relay systems in the high signal-to-noise ratio (SNR) regime. Considering distortion exponent as a figure of merit, we propose various strategies for cooperative source and channel coding that significantly improve the performance compared to the conventional scheme of source coding followed by cooperative channel coding. We characterize the optimal distortion exponent of a full-duplex relay channel for all bandwidth ratios. For the half-duplex relay channel, we provide an upper bound which is tight for small and large bandwidth ratios. We consider the effect of correlated side information on the distortion exponent as well.     

Joint Source–Channel Turbo Techniques for Discrete-Valued Sources: From Theory to Practice

The principles which have been prevailing so far for designing communication systems rely on Shannon's source and channel coding separation theorem. This theorem states that source and channel optimum performance bounds can be approached as close as desired by designing independently the source and channel coding strategies. However, this theorem holds only under asymptotic conditions, where both codes are allowed infinite length and complexity. If the design of the system is constrained in terms of delay and complexity, if the sources are not stationary, or if the channels are nonergodic, separate design and optimization of the source and channel coders can be largely suboptimal. For practical systems, joint source-channel (de)coding may reduce the end-to-end distortion. It is one of the aspects covered by the term cross-layer design, meaning a rethinking of the layer separation principle. This article focuses on recent developments of joint source-channel turbo coding and decoding techniques, which are described in the framework of normal factor graphs. The scope is restricted to lossless compression and discrete-valued sources. The presented techniques can be applied to the quantized values of a lossy source codec but the quantizer itself and its impact are not considered.     

A unification of network coding and tree-packing (routing) theorems

Given a network of lossless links with rate constraints, a source node, and a set of destination nodes, the multicast capacity is the maximum rate at which the source can transfer common information to the destinations. The multicast capacity cannot exceed the capacity of any cut separating the source from a destination; the minimum of the cut capacities is called the cut bound. A fundamental theorem in graph theory by Edmonds established that if all nodes other than the source are destinations, the cut bound can be achieved by routing. In general, however, the cut bound cannot be achieved by routing. Ahlswede et al. established that the cut bound can be achieved by performing network coding, which generalizes routing by allowing information to be mixed. This paper presents a unifying theorem that includes Edmonds' theorem and Ahlswede et al.'s theorem as special cases. Specifically, it shows that the multicast capacity can still be achieved even if information mixing is only allowed on edges entering relay nodes. This unifying theorem is established via a graph theoretic hardwiring theorem, together with the network coding theorems for multicasting. The proof of the hardwiring theorem implies a new proof of Edmonds' theorem.     

Approximation theory of output statistics

Given a channel and an input process with output statistics that approximate the original output statistics with arbitrary accuracy, the randomness of the input processes is studied. The notion of resolvability of a channel, defined as the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process, is introduced. A general formula for resolvability that holds regardless of the channel memory structure is obtained. It is shown that for most channels, resolvability is equal to the Shannon capacity. By-products of the analysis are a general formula for the minimum achievable source coding rate of any finite-alphabet source and a strong converse of the identification coding theorem, which holds for any channel that satisfies the strong converse of the channel coding theorem     

A two-way communication problem with application to information retrieval

A special case of two-way communication is considered. Two memoryless channels are used. The forward channel carries questions, generated by a memoryless source. Each question specifies a component of a vector, generated by a memoryless vector source. The value of that component is transmitted to the requesting party via the backward channel. The goal is to minimize the capacity required in the backward channel when the information rate in the forward channel is given. The result is formulated as a coding theorem stating the necessary and sufficient capacity of the backward channel when all possible questions are equally likely and the components of the above mentioned vector are independent stochastic variables with equal entropy. Some explicit codes are also derived. The rates of these codes are close to the necessary minimum. The nonsymmetric case where the questions have unequal probability and the vector components have unequal entropy is reformulated as a source coding problem.     

Combined source-channel coding schemes for video transmission overan additive white Gaussian noise channel

There has been an increased interest in the transmission of digital video over real-world transmission media, such as the direct broadcast satellite (DBS) channel. Video transmitted over such a channel is subject to degradation due, in part, to additive white Gaussian noise (AWGN). Some form of forward error-control (FEC) coding may be applied in order to reduce the effect of the noise on the transmitted bitstream; however, determination of the appropriate level of FEC coding is generally an unwieldy and computationally intensive problem, as it may depend upon a variety of parameters such as the type of video, the available bandwidth, and the channel SNR. More specifically, a combined source-channel coding approach is necessary in optimally allocating rate between source and channel coding subject to a fixed constraint on overall transmission bandwidth. In this paper we develop a method of optimal bit allocation under the assumption that the distortion is additive and independent on a frame-by-frame basis. A set of universal operational distortion-rate characteristics is developed which balances the tradeoff between source coding accuracy and channel error protection for a fixed overall transmission rate and provides the basis for the optimal bit allocation approach. The results for specific source and channel coding schemes show marked improvement over suboptimum choices of channel error protection. In addition, we show that our results approach information-theoretic performance bounds which are developed in this work     

基于纠错算术码的信源信道自适应联合编解码系统

对信源信道自适应联合编码方法进行了研究,提出了一种新的基于纠错算术码的联合信源信道编解码系统。该系统在编码端利用算术码内嵌禁用符号实现信源信道一体式编码,即利用马尔科夫信源模型和根据信道状态信息自适应地调整禁用符号概率大小从而调整编码码率来实现信道自适应;在解码端,推导出了基于MAP的解码测度数学公式并基于此测度公式提出了一种改进的堆栈序列估计算法。与传统的信道自适应编码算法不同,该自适应编码算法只需调整一个参数:禁用符号,且理论上可获得连续可变的编码码率。实验结果表明,与经典的Grangetto联合编码系统以及分离编码系统相比,所提出的编码系统具有明显改善的性能增益。     

与经典信道相关的网络编码

传统的网络信息流传输方式是存储转发,但通常无法达到通信的最大流界。为了实现更高的传输效率,Ahlswede等人提出采用网络编码的方法,不但可以提高网络吞吐量,而且在普适性、鲁棒性、可靠性和安全性等方面都具有优势。网络中的信道通常是有噪声的,目前网络编码理论的研究重点包括经典多用户信道、网络-信道编码分离和网络安全编码等问题。     

A separation theorem for single-source network coding

In this paper, we consider a point-to-point communication network of discrete memoryless channels. In the network, there are a source node and possibly more than one sink node. Information is generated at the source node and is multicast to each sink node. We allow a node to encode its received information before loading it onto an outgoing channel, where the channels are independent of each other. We also allow the nodes to pass along messages asynchronously. In this paper, we characterize the admissibility of single-source multi-sink communication networks. Our result can be regarded as a network generalization of Shannon's result that feedback does not increase the capacity of a discrete memoryless channels (DMCs), and it implies a separation theorem for network coding and channel coding in such a communication network.     

The role of the asymptotic equipartition property in noiselesssource coding

The (noiseless) fixed-length source coding theorem states that, except for outcomes in a set of vanishing probability, a source can be encoded at its entropy but not more efficiently. It is well known that the asymptotic equipartition property (AEP) is a sufficient condition for a source to be encodable at its entropy. This paper shows that the AEP is necessary for the source coding theorem to hold for nonzero-entropy finite-alphabet sources. Furthermore, we show that a nonzero-entropy finite-alphabet source satisfies the direct coding theorem if and only if it satisfies the strong converse. In addition, we introduce the more general setting of nonserial information sources which need not put out strings of symbols. In this context, which encompasses the conventional serial setting, the AEP is equivalent to the validity of the strong coding theorem. Fundamental limits for data compression of nonserial information sources are shown based on the flat-top property-a new sufficient condition for the AEP