Efficient adaptive algorithms and minimax bounds for zero-delay lossy source coding

Zero-delay lossy source coding schemes are considered for both individual sequences and random sources. Performance is measured by the distortion redundancy, which is defined as the difference between the normalized cumulative mean squared distortion of the scheme and the normalized cumulative distortion of the best scalar quantizer of the same rate that is matched to the entire sequence to be encoded. By improving and generalizing a scheme of Linder and Lugosi, Weissman and Merhav showed the existence of a randomized scheme that, for any bounded individual sequence of length n, achieves a distortion redundancy O(n/sup -1/3/logn). However, both schemes have prohibitive complexity (both space and time), which makes practical implementation infeasible. In this paper, we present an algorithm that computes Weissman and Merhav's scheme efficiently. In particular, we introduce an algorithm with encoding complexity O(n/sup 4/3/) and distortion redundancy O(n/sup -1/3/logn). The complexity can be made linear in the sequence length n at the price of increasing the distortion redundancy to O(n/sup -1/4//spl radic/logn). We also consider the problem of minimax distortion redundancy in zero-delay lossy coding of random sources. By introducing a simplistic scheme and proving a lower bound, we show that for the class of bounded memoryless sources, the minimax expected distortion redundancy is upper and lower bounded by constant multiples of n/sup -1/2/.     

Estimation with finite memory

A finite-state model for sequential minimum-mean-square-error estimation of a random variable in additive noise is analyzed to determine the dependence of optimum performance and structure on the memory size of the estimator. Necessary conditions for determining the structure of the optimum finite-state estimator are derived for arbitrary statistics. Numerical results are presented for Gaussian statistics. The performance of several different estimators is used to show the trade-off one may obtain between memory size, observation quality, and number of observations.     

Interblock memory for turbo coding

We investigate a binary code, which is implemented by serially concatenating a multiplexer, a multilevel delay processor, and a signal mapper to a binary turbo encoder. To achieve improved convergence behavior, we modify the binary code by passing only a fraction of the bits in the turbo code through the multilevel delay processor and the signal mapper. Two decoding methods are discussed and their performances are evaluated.     

Channels with almost finite memory

A stationary channel can have two kinds of memory--input memory and output memory. Recently, Gray and Ornstein introduced a condition on the decay of input memory calledbar{d}-continuity and established coding theorems for d-continuous channels. In this paper a condition for the decay of output memory is introduced which is called conditional almost block independence (CABI). It is believed that these two properties describe the character of many channels of interest. The principal result states that thebar{d}-continuous CABI channels are precisely those which can be approximated in a very strong sense by a simple kind of finite memory channel, called a primitive channel, in which the source of randomness is memoryless and completely separated from the memory.     

On random coding error exponents of watermarking systems

Watermarking codes are analyzed from an information-theoretic viewpoint as a game between an information hider and an active attacker. While the information hider embeds a secret message (watermark) in a covertext message (typically: text, image, sound, or video stream) within a certain distortion level, the attacker processes the resulting watermarked message, within limited additional distortion, in attempt to invalidate the watermark. For the case where the covertext source is memoryless (or, more generally where there exists some transformation that makes it memoryless), we provide a single-letter characterization of the maximin game of the random coding error exponent associated with the average probability of erroneously decoding the watermark. This single-letter characterization is in effect because if the information hider utilizes a memoryless channel to generate random codewords for every covertext message, the (causal) attacker will maximize the damage by implementing a memoryless channel as well. Partial results for the dual minimax game and the conditions for the existence of a saddle point are also presented     

Source coding for digital HDTV terrestrial broadcasting

It is claimed that an all-digital system will provide true high-definition television quality and coverage area equivalent to NTSC without noise and interference. Less transmission power may be required, and the signal will be easy to encrypt. The proposed source coding algorithms are reviewed, and the methods by which they are used in the proposed digital HDTV terrestrial broadcasting systems are discussed     

Source and channel coding for homogeneous sensor networks with partial cooperation

A sensor networks in which two nodes communicate a remote measurement to an access point is investigated (CEO problem). The focus is on assessing the performance advantages of cooperative encoding strategies as enabled by out-of-band and finite-capacity communication links between the sensors. The analysis assumes Gaussian source and observation noises, a quadratic (MSE) distortion metric and homogeneous sensors. With rate-constrained links between each sensor and the access point, an achievable rate-distortion trade-off is derived that reduces to known rate-distortion characterizations in the cases without and with perfect cooperation. This result is then extended to a Gaussian multiple access channel scenario by deriving achievable distortions with separate or joint source-channel coding. It is concluded that, for both scenarios, even modest values of the capacity of the inter-sensor links enable the optimal performance with full sensor cooperation to be approached.     

Source coding with side information at several decoders

A source coding problem is considered which generalizes source coding with side information [1], [2]. Three correlated information sourcesX,YandZ, are block-encoded:Yis to be reconstructed by two different decoders, one having access to the encoded version ofXand the other having access to the encoded version ofZ. The region of achievable rates is determined, assuming that thc sources are discrete, memoryless, and stationary. The resuit is generalized to an arbitrary finite number of decoders.     

Source coding theory for a triangular communication system

A rate-distortion problem is considered for a triangular communication system (TCS), which has one encoder f and two decoders g _X and g_Y. The encoder f maps correlated source outputs (X^K,Y^K) to two codewords W_X and W_Y, which are sent to g_X and g_Y, respectively. The decoders g_X and g_Y can communicate with each other via rate-constrained channels as many times as they need, and g_X reproduces Xˆ^K while g _Y reproduces Yˆ^K. The admissible rate-distortion region is determined for this TCS. Furthermore, the relations between the TCS and the Gray-Wyner (1974) system, Wyner's (1974) common information, Yamamoto's cascade communication system (1981), and the successive refinement system are discussed     

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.     

Source coding and graph entropies

A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Korner (1973) entropies of a naturally defined graph     

Source coding with side information and a converse for degraded broadcast channels

Let{(X_i, Y_i,)}_{i=1}^{infty}be a memoryless correlated source with finite alphabets, and let us imagine that one person, encoder 1, observes onlyX^n = X_1,cdots,X_nand another person, encoder 2, observes onlyY^n = Y_1,cdots,Y_n. The encoders can produce encoding functionsf_n(X^n)andg_n(Y^n)respectively, which are made available to the decoder. We determine the rate region in case the decoder is interested only in knowingY^n = Y_1,cdots,Y_n(with small error probability). In Section H of the paper we give a characterization of the capacity region for degraded broadcast channels (DBC's), which was conjectured by Bergmans [11] and is somewhat sharper than the one obtained by Gallager [12].     

Hypothesis testing with finite memory in finite time (Corresp.)

The hypothesis-testing problem has recently been studied under a finite-memory constraint. However, most work has been concerned with the large-sample theory. Here we study the small-sample theory for binary-valued observations.     

On tests with finite memory in finite time (Corresp.)

The purpose of this correspondence is to display an inductive proof of an optimality result for testing symmetric simple hypotheses concerning a binomial parameter with a three-state memory andnobservations. Specifically, it is shown that if one restricts attention to three-state automata allowing transitions only between adjacent states, then no artificial randomization is required in the middle state of the optimal machine. The success in this problem of what will be called simultaneous induction suggests the possibility of obtaining characterizations of optimal automata in more general problems by similar techniques.     

Channel capacity and error exponents of variable rate adaptivechannel coding for Rayleigh fading channels

We have evaluated the information theoretical performance of variable rate adaptive channel coding for Rayleigh fading channels. The channel states are detected at the receiver and fed back to the transmitter by means of a noiseless feedback link. Based on the channel state informations, the transmitter can adjust the channel coding scheme accordingly. Coherent channel and arbitrary channel symbols with a fixed average transmitted power constraint are assumed. The channel capacity and the error exponent are evaluated and the optimal rate control rules are found for Rayleigh fading channels with feedback of channel states. It is shown that the variable rate scheme can only increase the channel error exponent. The effects of additional practical constraints and finite feedback delays are also considered. Finally, we compare the performance of the variable rate adaptive channel coding in high bandwidth-expansion systems (CDMA) and high bandwidth-efficiency systems (TDMA)     

A direct proof of the coding theorem for discrete sources with memory

In this paper we provide an alternate method of proving the existence theorem for the coding of discrete stationary ergodic sources subject to a fidelity constraint. This method differs from previously published proofs for sources with memory in that a random coding argument is obtained directly for the coding of sourcen-tuples. The main advantage of the technique employed in this paper is that it can easily be extended to yield the basis for the proof of the coding theorem for more general sources (e.g., nonergodic) and for sources with unknown parameters.     

Source coding theory for cascade and branching communication systems

A source coding problem is considered for cascade and branching communication systems. The achievable rate region is established for the cascade systems and bounds are obtained for the branching systems. Some examples are also included.     

Binary shape coding using finite automata

Two new binary shape-coding techniques that are based on finite automata methods are proposed. Both contour-based and bitmap-based approaches to shape coding are investigated using one-dimensional weighted finite automata (1D-WFA) and generalised finite automata (GFA) algorithms, respectively. We evaluate the fidelity of shape representation, using 1D-WFA and GFA methods in intraframe mode and compare the performance of the proposed coding techniques against each other and with the benchmark, context-based arithmetic encoding (CAE) of shapes used in MPEG-4. It is found that the GFA method is more suitable for video applications than 1D-WFA and therefore it is adapted to operate in interframe mode. More importantly, GFA is the first shape-coding technique reported to date that has the unique advantage of shape processing in the compressed domain. This is due to the fact that the shape representation in the compressed domain using GFA facilitates processing at the expense of less compression efficiency compared with MPEG-4 CAE. Moreover, shapes encoded using the GFA method can be decoded at any desirable resolution