Trellis encoding of continuous-amplitude memoryless sources (Corresp.)

Trellis coding of analog memoryless sources with respect to the squared-error distortion criterion is investigated via simulation. Sources treated are the Gaussian, uniform, Laplacian, and Gaussian mixture models, and the encoding algorithms studied are the Viterbi andMalgorithms. Performance versus complexity trade-offs are presented for these source models, and practical aspects of finite encoder memory and unknown source statistics are examined.     

Efficient encoding of sources with memory (Corresp.)

A noiseless encoding scheme is presented for sources with memory. The source is modeled by an ruth-order finite ergodic Markov process. A secondary source is derived which has as its symbol set the ordinal numbers of the symbol probabilities. The secondary source is approximately memoryless and has entropy smaller than that of the adjoint     

On convergence of distortion for block and tree encoding of symmetric sources (Corresp.)

For symmetric sources we examine the rate of convergence to the rate-distortion function using block codes and tree codes. With block codes the average distortion decreases toward distortionDat a doubly exponential rate in block length for any fixed rate greater thanR(D), the rate-distortion function. For tree codes a difference equation for the probability distribution of the distortion is derived with tree depth as an independent variable. Its numerical solution suggests that the same doubly exponential convergence behavior applies to tree codes.     

Low-rate tree coding of autoregressive sources (Corresp.)

The performance of differential pulse-code modulation and random codes is evaluated experimentally for a range of autoregressive sources, including Gaussian and Laplacian sources of orders1, 2, and3encoded at rates1, 2, and7. Correlations are typical of those encountered in speech and images. Results show that the gain from a fixed moderate degree of code searching increases as the rate decreases, and increases consistently with1 /D_{o}, whereD_{o}is the Berger-Gray critical distortion. Laplacian and Gaussian sources behave similarly. Random codes perform better than DPCM codes for lightly correlated Laplacian sources but are otherwise worse.     

Rate-distortion theory for ergodic sources with side information (Corresp.)

The definition of the rate-distortion function is extended to the case of a stationary-ergodic source with side information, and the appropriate coding theorem is proved. Inequalities between the joint, marginal, and conditional rate-distortion functions for ergodic processes are given, and their implications in terms of universal coding are discussed.     

Incremental tree coding of speech (Corresp.)

Tree coding of speech has been investigated by several workers. Virtually all of these investigations have involved incremental tree coding in that no matter how deep the tree is searched, only a single path map symbol is released at a time. As noted by Gray, even if a good long-term fit is found, the first step in the fit may be a poor one, thus yielding large sample distortions. Hence, it is important to stay on a path long enough to achieve the promised long-term distortion value. The relative frequency of path switching for the single symbol release rule is investigated for the(M,L)and truncated Viterbi tree search algorithms, various search depths, and different code generators. In addition, two multiple symbol release rules are investigated. One rule releases a fixed number of path symbols at a time, while the other rule releases a variable number of path symbols, the exact number depending on how many symbols are required for the average sample distortion to be less than or equal to theL-depth path average distortion. Speech sources are considered exclusively.     

Optimal symbol error rate encoding (Corresp.)

It is shown that in a digital communication system that uses an(N,K)linear code, the symbol error rate, measured on the information symbols, is a function of the encoderGused for the code. An algorithm is proposed, identical in nature to that encountered in unequal error protection codes, for finding an optimal linear encoderG_{0}that minimizes the symbol error rate for a fixed complete standard array decoder.     

Axioms for discrimination information (Corresp.)

Axioms characterizing combinatorial discrimination information are given and extended to characterize arbitrary measure theoretic discrimination information.     

Convolutional encoding for Wyner's wiretap channel (Corresp.)

The wiretap channel introduced by Wyner is studied for the special case when the main channel is a noiseless binary channel and the wiretap channel is a binary symmetric channel. With a rate-one convolutional encoder, the steady-state uncertainty of the wiretapper is shown to depend only on the constraint lengthvof the code, not on the specific taps, and is complete on k successive bits providedkleq v. During the initial transient period, the rate of growth of uncertainty does depend on the tap connections of the shift register.     

Linear programming bounds for tree codes (Corresp.)

Two asymptotic upper bounds on the information rate of a tree code as a function of its feedback decoding minimum distance are presented. These bounds are generalizations of the linear programming bounds for binary block codes proved by McEliece et al., and they are derived from linear programming problems based on Delsarte's theory of association schemes.     

On critical distortion for Markov sources (Corresp.)

The authors underbound the critical distortion below which the rate-distortion function of a Markov chain equals its Shannon lower bound. The bound is tight in all cases in which the exact answer is currently known.     

Noiseless coding of binary finite-order Markov sources (Corresp.)

The performance of several simple noiseless coding schemes for binary finite-order Markov sources is considered. Bounds are derived on the maximum difference between the performance achievable by the schemes and the entropy of the sources. The schemes can be modified for the case where the source statistics are unknown.     

On the convergence of discrimination information (Corresp.)

A sufficient condition involving a hypothesis of mean-square convergence is given for the convergence of discrimination information. A stronger condition requiring uniform convergence has already been given. An example is given which satisfies the mean-square convergence hypothesis but not the uniform convergence hypothesis.     

Noiseless coding of error detection information (Corresp.)

Correlated information sequences{X_{i}}and{Y_{i}}are generated by a source and receiver, respectively. The least number of bits per source character that must be given to the receiver to allow perfect detection of errors in the sequence{Y_{i}}is found. The performance of error detecting codes used over noisy channels is characterized by this result.     

Joint source and noisy channel trellis encoding (Corresp.)

In a trellis encoding communication system the decoder is a time-invariant nonlinear filter with finite memory (sliding-block code), and the encoder is a trellis search algorithm matched to the decoder. A coding theorem is established for a trellis encoding of a stationary and ergodic source over a discrete memoryless noisy channel which shows that such communication systems can perform arbitrarily close to the source distortion-rate function evaluated at the channel capacity.     

Convolutional tree codes for multiple access channels (Corresp.)

The decoding algorithm of Viterbi is extended to the case of a memoryless multiple access channel. It is Shown that in the capacity region, the probability of decoding error is bounded from above by a function of the constraint length of the code.     

Decision tree design using a probabilistic model (Corresp.)

A sequential optical character recognition algorithm, ideally suited for implementation by means of microprocessors with limited storage capabilities, is formulated in terms of a binary decision tree. Upper bounds On the recognition performance are derived in terms of the stability of the digitized picture elements. The design process is described in detail. The algorithm is tested on single-font typewritten characters and the experimental and theoretical results are compared.     

Real-number convolutional codes for speech-like quasi-stationary sources (Corresp.)

A quasi-stationary source is one which is stationary over short periods, but changes occasionally to a new mode of stationarity; a typical example is the speech source. Convolutional codes are designed for the speech source for use with search algorithms such as the Viterbi, stack, andM-algorithms; the design is first by heuristic means and then by an empirical optimization. These codes have the same generating structure as the usual binary convolutional codes, but employ ordinary arithmetic. It is found by experiment that, at rate 2 bits/sample (which allows telephone quality speech), such codes need not have constraint length longer than five or six, which implies a generating circuit of about 1000 states. Encoding noise becomes white and uncorrelated with simple code searching; this shows that a short fixed code can successfully decorrelate waveforms from different source modes.