Variable-rate universal block source coding subject to a fidelity constraint

Variable-rate universal source codes are data compression schemes that are optimum for the coding of a collection of sources (e.g., a source with unknown parameters) subject to a fixed average distortion constraint. Existence of variable-rate universal source codes is demonstrated for very general classes of sources and distortion measures.     

Block coding for an ergodic source relative to a zero-one valued fidelity criterion

An effective rate for block coding of a stationary ergodic source relative to a zero-one valued fidelity criterion is defined. Under some mild restrictions, a source coding theorem and converse are given that show that the defined rate is optimum. Several examples are given that satisfy the restrictions imposed. A new generalization of the Shannon-McMman Theorem is employed.     

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.     

Strong universal source coding subject to a rate-distortion constraint

The following problem in universal source coding is explored. Some members of a class of sources have various constraints on the maximum rate at which they may be encoded, and thc remainder have various constraints on the maximum distortion that may result from encoding. It is desired to find a universal code that will adapt its performance so that whatever source in the class is encoded, the resulting performance meets the constraint and is optimal in the rate-distortion function sense for that particular source. It is shown that such codes exist when the class is totally bounded and the constraints are uniformly continuous in an appropriate sense. A key result shows that the value of any uniformly continuous function on a totally bounded class can be uniformly well estimated from observations of the output of any source in     

Tree encoding of stationary ergodic sources with a fidelity criterion

Tree source coding theorems with a single letter fidelity criterion are proved for stationary ergodic sources using tree codes with a fixed branch length. The higher-than-exponential convergence of distortions is shown for binary symmetric sources and Hamming distortion measure when an excess in rate is allowed.     

Time-invariant trellis encoding of ergodic discrete-time sources with a fidelity criterion

The theory of sliding-block codes (nonlinear, time-invariant, discrete-time filters) is employed to obtain general source coding theorems for ergodic sources using time-invariant trellis coding (time-invariant decoding filter and replicating trellis). The results are coupled with the theory of universal block source codes to obtain universal trellis source coding theorems for classes of sources. It is shown for a certain class of sources that the problem of designing good trellis codes is equivalent to that of simulating general random processes by filtering digital memoryless sources.     

Variable-rate coding for classes of sources with generalized alphabets

Discrete-time source coding theorems are established for more general reproduction alphabets than allowed in previous results on coding for a class of sources subject to a fidelity constraint. The two different alphabets considered are metric spaces for which every closed bounded subset is compact and separable Hilbert spaces. Potential applications of the Hilbert space results to continuous-time source coding are discussed.     

Fixed rate universal block source coding with a fidelity criterion

A unified theory is developed for fixed rate block source encoding subject to a fidelity criterion in incompletely or inaccurately specified stationary statistical environments. Several definitions of universal encoding are given and compared, and the appropriate theorems are stated and proved for each. The new results and approaches are compared and contrasted with earlier related results of Ziv.     

Variable rate speech coding for asynchronous transfer mode

A new speech coding and multiplexing scheme matched to the asynchronous transfer mode is described. A block coding technique that is based on a variable-rate coding algorithm that makes the most of the burstiness of voice information is employed. The main feature of the scheme is considerable bit reduction, which is attained by a fairly simple algorithm. It is demonstrated that the proposed algorithm exhibits better quality than that of a 32 kb/s ADPCM at a mean bit rate of less than 13 kb/s. The effect of statistical multiplexing is verified by means of simulation employing long conversational speech samples. Methods for constructing variable- and fixed-length frames (units of information multiplexed and transferred in the network) are proposed. The proposed coding algorithm is shown to be applicable to both variable- and fixed-length frame strategies     

Tree coding of discrete-time abstract alphabet stationary block-ergodic sources with a fidelity criterion

A tree coding theorem is established for discrete-time abstract alphabet stationary block-ergodic sources under a single-letter fidelity criterion. The proof of this theorem uses recent results from the theory of branching processes with random environments. The relation to previous work in tree coding is also discussed.     

Image restoration subject to a total variation constraint

Total variation has proven to be a valuable concept in connection with the recovery of images featuring piecewise smooth components. So far, however, it has been used exclusively as an objective to be minimized under constraints. In this paper, we propose an alternative formulation in which total variation is used as a constraint in a general convex programming framework. This approach places no limitation on the incorporation of additional constraints in the restoration process and the resulting optimization problem can be solved efficiently via block-iterative methods. Image denoising and deconvolution applications are demonstrated.     

Universal source coding of finite alphabet sources via composition classes

The universal source coding theorem for stationary sources states that, by using a preselected code with sufficiently large block length, any stationary source can be encoded arbitrarily close to the optimum performance theoretically attainable for the source. The code construction typically used to prove this theorem offers no performance guarantees for nonstationary sources. A code construction (based on composition classes) is described which is shown to be universal for stationary sources. In addition, this code construction guarantees that the distortion for any block in the sequence will not exceed a maximum value determined by its composition.     

On the optimum average distortion attainable by fixed-rate coding of a nonergodic source

A simple proof is given for the Gray-Davisson result on the ergodic decomposition of the optimum average distortion attainable by fixed-rate coding of a nonergodic source, for the special ease of a bounded distortion measure. A second proof is given for a more general class of distortion measures using a result of Ziv.     

Topological optimization of a communication network subject to areliability constraint

Network topological optimization with a reliability constraint is considered. The objective is to find the topological layout of links, at a minimal cost, under the constraint that the network reliability is not less than a given level of system reliability. A decomposition method, based on branch and bound, is used for solving the problem. In order to speed up the procedure, an upper bound on system reliability, in terms of node degrees, is applied. A numerical example illustrates the effectiveness of the method     

Strong converses in source coding relative to a fidelity criterion

Two strong converses are obtained for an abstract alphabet stationary ergodic source coded relative to an appropriate fidelity criterion. It is shown that given a distortion rate point (D, R) that lies below the rate distortion curve, (1) block codes that operate at rate level R must encode sample source blocks at a rate exceeding D with probability tending to one as the block length tends to infinity, and (2) variable-rate codes that operate at distortion level D must encode sample source blocks at a rate exceeding R with probability tending to one as the block length tends to infinity. The previously known weak converses guarantee only that the indicated probabilities remain bounded away from zero as block length tends to infinity. The proofs of the strong converses involve sample converses in source coding theory     

Distortion-rate functions for vector sources and a maximum fidelity criterion

The problem of distortion-rate functions for vector sources is considered. Two fidelity criteria are treated. The first considers the maximum of the weighted component distortions and then takes the per-letter average. The second takes the maximum of the weighted component per-letter averages. In either case, a well-defined distortion-rate function results, giving the minimum possible distortion achievable at a given rate of transmission. Upper and lower bounds to these distortion-rate functions are derived in terms of more easily calculated functions.     

A stack algorithm for source coding with a fidelity criterion

A new scheme for encoding source information with respect to a fidelity criterion by tree codes is analyzed. Taking its design from earlier stack sequential decoders for channels, the algorithm keeps a stack of code tree paths of variable lengths ordered by a metric. It repeatedly extends the topmost path and reorders, until the topmost rises above a given metricA. The analysis uses difference equations, both linear and nonlinear; a commonly occurring nonlinear equation is solved asymptotically for the first time. The distribution of the worst metric to appear at the stack top is found to fall off faster than exponentially below a specifiable metric, whenever the encoder performance lies above the rate-distortion limit. Next, development of the top path is found to follow asymptotically a certain trajectory in the length-metric plane; this leads to a tight bound on path length released at termination. Finally, difference equations are written to bound the nodes searched. The work concludes with numerical calculations and simulations for the binary lid source with Hamming distortion measure. Comparison is made to other algorithms.     

Optimization of connecting two communication networks subject to a reliability constraint

This paper considers optimization of two networks with a reliability constraint. The objective is to find some links to connect two networks, at a minimal cost, under the constraint that the system reliability of the resultant network is not less than a given level. A decomposition method based on branch and bound is used for solving the problem. In order to speed up the solution procedure, an upper bound on system reliability in terms of node degrees is applied. In particular, when the threshold P_o is large enough, a new algorithm, the cut tree algorithm, can more effectively give an optimal solution.     

Variable to fixed-length codes for Markov sources

Petry's efficient and optimal variable to fixed-length source code for discrete memoryless sources was described by Schalkwijk. By extending this coding technique we are able to give an algorithm for Markov sources that is easy to implement. We can bound the loss of efficiency as a function of the code complexity and the mismatch between the source and the code. Rates arbitrarily close to the source entropy are shown to be achievable. In this sense the codes introduced are optimal.