Asymptotic performance of block quantizers with difference distortion measures

Gersho's bounds on the asymptotic (large rate or small distortion) performance of block quantizers are valid for vector distortion measures that are powers of the Euclidean orl_{2}norm. These results are generalized to difference distortion measures that are increasing functions of the seminorm of their argument, where any seminorm is allowed. This provides ak-dimensional generalization of Gish and Pierce's results for single-symbol quantizers. When the distortion measore is a power of a seminorm the bounds are shown to be strictly better than the corresponding bounds provided by thekth-order rate-distortion functions.     

Permutation codes for sources

Source encoding techniques based on permutation codes are investigated. For a broad class of distortion measures it is shown that optimum encoding of a source permutation code is easy to instrument even for very long block lengths. Also, the nonparametric nature of permutation encoding is well suited to situations involving unknown source statistics. For the squared-error distortion measure a procedure for generating good permutation codes of a given rate and block length is described. The performance of such codes for a memoryless Gaussian source is compared both with the rate-distortion function bound and with the performance of various quantization schemes. The comparison reveals that permutation codes are asymptotically ideal for small rates and perform as well as the best entropy-coded quantizers presently known for intermediate rates. They can be made to compare favorably at high rates, too, provided the coding delay associated with extremely long block lengths is tolerable.     

A robust decoding for long convolutional codes

Sequential decoding is an attractive technique to achieve the reliability of communication promised by the channel coding theory. But, because it utilizes the Fano metric, its performance is sensitive to channel parameter variations and it cannot simultaneously minimize both decoding effort and probability of decoding error. Based on the distance properties of the codes, we have derived a new set of metric which not only can overcome the two drawbacks caused by the Fano metric but also can significantly reduce the decoding effort required by sequential decoding.     

On robust and dynamic identifying codes

A subset C of vertices in an undirected graph G=(V,E) is called a 1-identifying code if the sets I(v)={u/spl isin/C:d(u,v)/spl les/1}, v/spl isin/V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I(v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G.     

Information-theoretic distortion measures for speech recognition

A wide variety of speech recognition distortion measures have been proposed and tested, including some especially effective ones. It is shown that there is a general framework, based on the concepts of information theory, linking most of these measures. The distortion measure between any two speech spectra can be defined in terms of the distortions between the associated probability distributions. This general framework defines three broad families of distortion measures for speech recognition and provides a consistent way of combining the energy and the spectral information of a phonetic event. In addition, the cepstral-domain representation for several distortion measures is derived, allowing comparison of these measures in a domain that also yields convenient equations for their practical implementation     

Variable-to-fixed length codes are better than fixed-to-variablelength codes for Markov sources

It is demonstrated that for finite-alphabet, kth-order ergodic Markov sources (i.e. memory of k letters), a variable-to-fixed length code is better than the best fixed-to-variable length code (Huffman code). It is shown how to construct a variable-to-fixed length code for a kth order ergodic Markov source, which compresses more effectively than the best fixed-to-variable code     

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.     

Generalized Tunstall codes for sources with memory

Tunstall codes are variable-to-fixed length codes that maximize the expected number of source letters per dictionary string for discrete, memoryless sources. We analyze a generalization of Tunstall coding to sources with memory and demonstrate that as the dictionary size increases, the number of code letters per source symbol comes arbitrarily close to the minimum among all variable-to-fixed length codes of the same size. We also find the asymptotic relationship between the dictionary size and the average length of a dictionary entry     

Worst case estimate of mismatch induced distortion in complementaryCMOS current mirrors

Mismatching between the MOS transistors in a current mirror causes harmonic distortion. In a complementary class AB current mirror, mismatching of threshold voltages, geometries and transconductance parameters causes a distortion which cannot be eliminated by circuit techniques but which can be reduced by careful device matching. In this Letter, the author presents a worst case estimate of the harmonic distortion introduced by device mismatch     

A rate and distortion analysis of chain codes for line drawings

The performance of chain codes for line drawings in the framework of source coding with a fidelity criterion is investigated. A formal characterization is given for a broad class of chain codes that includes the generalized chain codes of Freeman and the convex quantizers of Koplowitz. Measures of distortion (fidelity) and rate (efficiency) are introduced. The distortion and rate are calculated for several types of chain codes applied to straight and slowly curving lines. Several statistical models for straight lines are introduced and the average performance of chain codes for these models is investigated.     

Perfect difference codes for synchronous fiber-optic CDMAcommunication systems

In this paper, we introduce the perfect difference sets and propose a synchronous fiber-optic code-division multiple-access system (CDMA) using these sets to generate the signature codes. Two interesting properties of these codes are discussed: (1) any two different codes are cyclic-shifted with each other; and (2) the cross correlation between any two different codes is exactly one. Thus, we may treat these codes as quasi-orthogonal codes. Using the first property of these codes, we can simplify design of the transmitter. In the receiver, we can use the second property to effectively eliminate the multiple-user interference (MUI) without reducing the number of usable codes. Based on the proposed transmitter and receiver, the system performance is derived. The numerical examples reveal that the proposed system can provide reliable communication even under heavy load. We believe that the proposed system using perfect difference codes outperforms any other synchronous fiber-optic CDMA systems     

Optimal prefix codes for sources with two-sided geometricdistributions

A complete characterization of optimal prefix codes for off-centered, two-sided geometric distributions of the integers is presented. These distributions are often encountered in lossless image compression applications, as probabilistic models for image prediction residuals. The family of optimal codes described is an extension of the Golomb codes, which are optimal for one-sided geometric distributions. The new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the heuristic approximations frequently used when modifying a code designed for nonnegative integers so as to apply to the encoding of any integer. Optimal decision rules for choosing among a lower complexity subset of the optimal codes, given the distribution parameters, are also investigated, and the relative redundancy of the subset with respect to the full family of optimal codes is bounded     

Dominance--A relation between distortion measures

A relation between distortion measures for source coding, called dominance, is defined so that ifd_{1}andd_{2}are two distortion measures andd_{1}dominatesd_{2}, then a source coding system which meets the distortion criterion(d_{l}, Delta)simply yields a system meeting the distortion criterion(d_{2}, Delta)by a simple change of decoder. It is shown that a very simple characterization of dominance can be given in terms of the characteristic sets of the distortion measures. The characteristic set of a distortion matrix is defined as the sum of the convex hull of the columns of the matrix and the nonnegative orthant. If two distortion measures have the same characteristic set they are regarded as equivalent. It is shown that the definition of dominance is robust in the sense that some alternative definitions are equivalent to the given one. The definition of dominance is extended to the case where a pair of distortion measures dominates a third distortion measure. Here a simple characterization is given in terms of the characteristic sets of the distortion measures.     

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.     

Tree encoding for symmetric sources with a distortion measure

A simple algorithm is developed for mapping the outputs of a source into the set of code sequences generated by a tree code. The algorithm is analyzed for a special case in which the source produces discrete independent equiprobable letters, and the distortion measure satisfies a symmetry condition. LettingRbe the code rate andD^{ast}be the minimum average distortion for that rate as given by Shannon's rate-distortion theorem, we show that the algorithm is capable of achieving average distortion as close toD^{ast}as desired. Furthermore an upper bound is developed on the average amount of computation for the algorithm. Asymptotically as the average distortionapproaches the theoretical limitD^{ast}, the bound on average computation has the formexp [a/ sqrt{ - D^{ast} }]for some constanta.     

Turbo codes for nonuniform memoryless sources over noisy channels

This work addresses the problem of designing turbo codes for nonuniform binary memoryless or independent and identically distributed (i.i.d.) sources over noisy channels. The extrinsic information in the decoder is modified to exploit the source redundancy in the form of nonuniformity; furthermore, the constituent encoder structure is optimized for the considered nonuniform i.i.d. source to further enhance the system performance. Some constituent encoders are found to substantially outperform Berrou's (1996) (37, 21) encoder. Indeed, it is shown that the bit error rate (BER) performance of the newly designed turbo codes is greatly improved as significant coding gains are obtained     

Analysis of recursive convolutional codes and turbo codes as sources with memory

The paper proposes a general method to analyze discrete sources with memory. Besides the classical entropy, we define new information measures for discrete sources with memory, similar to the information quantities specific to discrete channels. On the base of this method, we show for the first time that, as result of convolutional and turbo encoding, sources with memory are obtained. We apply this information analysis method for the general case of a recursive convolutional encoder of rate R_CC = 1/n₀ and memory of order m, and for a turbo encoder of rate R_TC = 1/3, with two systematic recursive convolutional component encoders. Each component encoder has memory of order m, and is built based on the same primitive feedback polynomial. For the convolutional and turbo codes, the information quantities H(Y/S), H(S,Y), H(S/Y), H(Y), H(S) and I(S,Y) have been computed, where S and Y denote the set of states and the set of messages of the encoder, respectively. The analysis considered two cases: n₀ ≤ m + 1 and n₀ > m + 1. When n₀ = m + 1, the mutual information I(S,Y) is maximum and equal to m, as is the entropy of the set of states. For turbo codes, the quantity I(S,Y) also depends on the input bit and on its probability.     

Rotationally invariant and rotationally robust codes for the AWGN and the noncoherent channel

The paper investigates the design and robustness of rotationally invariant (RI) codes. First, RI codes are extended to the case of serially concatenated (SC) trellis-coded modulation (TCM) and several high-rate powerful RI-SCTCM codes are designed over 8-phase-shift keying and 16-quadrature amplitude modulation alphabets. The investigation continues by considering more realistic channels that introduce cycle slips during phase estimation, and thus rotate only part of the transmitted codeword. It is proven that RI codes with small state space are robust in these channels, even when traditional coherent decoders are utilized. Furthermore, it is demonstrated through simulations that the addition of a simple stopping criterion to the coherent iterative decoding algorithm is sufficient for robustness of the more powerful RI-SCTCM codes when partial codeword rotations are considered. Finally, it is investigated whether RI codes are useful for transmission in the noncoherent channel. It is proved that RI codes are as good as any other good codes for this channel when the phase dynamics are low, and optimal decoding is performed. However, it is shown that for a certain class of receivers, RI codes are also robust to partial phase rotations in this channel.