In this paper, a protocol is designed to manage source rate/channel coding rate adaptation, code allocation, and power control to transmit real-time MPEG-4 FGS video over downlink multicode CDMA networks. We develop a fast adaptive scheme of distortion management to reduce the overall distortion received by all users subject, to the limited number of codes and maximal transmitted power. Compared with a modified greedy method in literature, our proposed algorithm can reduce the overall system's distortion by at least 45%.

In CDMA, resource allocation is a task critical to the performance of this inherently interference limited multiple access technique. This paper also presents the solution to the problem of optimal resource allocation to resolve interference-generated congestion for an arbitrary set of real-time source encoders and shows that this problem could be viewed as the one of statistical multiplexing in source-adapted CDMA. Based on this, we develop optimal algorithms to solve the allocation problem. Simulations using MPEG4 FGS video shows that the proposed systems significantly outperforms systems with no adaptation, being able to support more than three times the number of calls while the quality degrades gracefully.

In CDMA, resource allocation is a task critical to the performance of this inherently interference limited multiple access technique. In this paper we introduce a new technique aimed at increasing the number of real-time calls supported in a CDMA network at the cost of a smooth controllable degradation of reconstructed source quality while channel-induced distortion remains bounded by fixing a maximum target FER. This paradigm is based on real-time source codecs with externally adaptable output rate. This work also includes a study of the relation between interference, the number of users in the network and the reconstructed source quality at the output of the source decoder for the case of a single-state real-time coder. We present mathematical analysis and simulations to show that it is possible to achieve a 30% relative increase in the number of users for a 10% relative increase in distortion and to significantly outperform an equivalent CDMA system in the relative increase in the number of users that can be achieved for a given increase in source distortion.

We present a joint source-channel coding scheme based on incremental redundancy and feedback for transmission of real-time sources over wireless channels under strict delay constraints. The proposed scheme operates at constant bit rate and delay so as to capture the benefits of a feedback channel, while keeping the synchronous nature of pure forward error correction systems. We formulate the underlying Markov chain by introducing the notion of codetype and present a design algorithm for channel and source rate allocation. We present simulation results for speech transmission and show gains of up to 1 dB over pure FEC systems. We also present an application to CDMA networks and show increases of up to 28 % in the number of calls that can be simultaneously supported.

In multiple access wireless networks with co-channel interference, allocating resources such as transmitted powers and source rates is a task critical to improve performance. In this paper, we introduce a new technique aimed at minimizing the overall transmitted power subject to constraints on the incurred source distortion. The technique is based on the use of real-time source codecs with externally adaptable output rate and rate compatible punctured convolutional (RCPC) channel encoders. We develop an adaptive algorithm to find the optimal power and source rate allocation to the different users according to their channel conditions and under distortion constraints. We present simulation results to show that it is possible to reduce the overall transmitted power significantly with a relatively small distortion increases for some users, and while keeping the network average distortion unchanged.

Suppose that the description of a stochastic process needs to be sent to a destination through a communication network. Also assume there is a risk that the description may be lost. A technique to reduce the risk of losing such descriptions is by sending two (or more) descriptions and hoping that in this way at least one of the descriptions will get through. This problem is referred to as multiple description coding (MDC) and was first introduced by Gersho, Witsenhausen, Wolf, Wyner, Ziv and Ozarow (1979). So far, the main focus of research on this subject has been on the achievable rate-distortion functions and the related structural design issues for such encoders and decoders. Little effort has focused on the performance of such coding schemes in simple communication networks and relation of the overall distortion with respect to some network parameter such as congestion. In this paper, a double description coding (DDC) system in a simple network represented by a set of parallel queues is studied. Comparison is made with a single description coding system and it is shown that DDC significantly improves the overall average end-to-end distortion at high network loading.

A diffusion approximation is proposed for the data section of the source encoding assisted multiple access (SEAMA) protocol, a voice and data communication wireless network. In SEAMA, a reservation mechanism handles the slot assignment for the voice traffic which operates as an M/M/N/sub max//N/sub max/ loss system. The data traffic is a Markovian queueing system with a random number of channels assigned. It is shown that for high loads of voice traffic and high loads of data traffic, the data queueing system is similar to a dam with an input which can be decomposed into three independent components: a Markov AR process, a non-zero mean white Gaussian noise process and a zero mean Gaussian random variable. The data process is shown to be approximated by a Wiener process with a reflecting barrier at the origin. Using this approximation, the system behavior is described and the desired parameters for the data traffic, i.e. average data packet delay and average data queue length are obtained.

This paper presents SEAMA, a source encoding assisted multiple access (MAC) protocol, to integrate voice and data traffic in a wireless network. SEAMA exploits the time variations of the speech coding rate, through statistical multiplexing, to efficiently use the available bandwidth and to increase the link utilization. In each frame, SEAMA allocates bandwidth among calls as needed. Ongoing calls are always assigned some minimum bandwidth to allow for coding of the background noise during silence periods. An embedded voice encoding scheme is employed to allow the network to control the rate of the calls during congestion by selectively dropping some of the less significant packets, thus causing a graceful degradation of quality. It is shown that by employing an appropriate voice coding scheme and exploiting the characteristics of the source encoder in the MAC protocol, SEAMA almost doubles the capacity of the voice section compared to a circuit-switched network, while practically maintaining the quality of voice traffic.

An embedded source code allows the decoder to reconstruct the source progressively from the prefixes of a single bit stream. It is desirable to design joint source-channel coding schemes which retain the capability of progressive reconstruction in the presence of channel noise or packet loss. Here, we address the problem of joint source-channel coding of images for progressive transmission over memoryless bit error or packet erasure channels. We develop a framework for encoding based on embedded source codes and embedded error correcting and error detecting channel codes. For a target transmission rate, we provide solutions and an algorithm for the design of optimal unequal error/erasure protection. Three performance measures are considered: the average distortion, the average peak signal-to-noise ratio, and the average useful source coding rate. Under the assumption of rate compatibility of the underlying channel codes, we provide necessary conditions for progressive transmission of joint source-channel codes. We also show that the unequal error/erasure protection policies that maximize the average useful source coding rate allow progressive transmission with optimal unequal protection at a number of intermediate rates.

We study the design of channel-optimized vector quantizers in the presence of channel mismatch. We show that when the statistics of the channel bit-error rate (BER) are not known, a minimax solution is the one obtained by designing for the worst possible channel. Then, we consider the case when the probability density function of channel BER is known and propose an algorithm that provides a minimum average distortion. Also, by using an estimate of the channel BER at the decoder, we develop a decoder-adaptive scheme that further improves the performance. In all cases, we have limited ourselves to table-lookup decoders, which amount to very small computational complexities. Finally, the utilization of lookup tables at the encoder and the effects of imperfect estimation of channel BERs are considered.

In this correspondence, we propose a channel-matched hierarchical table-lookup vector quantizer for a discrete memoryless channel. We show that this scheme simultaneously provides low encoding complexity and robustness against transmission noise. Additionally, we propose the use of lookup tables for transcoding in heterogeneous networks. We show, through an example motivated by an application in multicasting, that the proposed table-lookup transcoding approach is an elegant alternative to the expensive and delay-introducing method of transcoding achieved by decoding and re-encoding.

We consider the design of power-adaptive systems for minimizing the average bit-error rate over flat fading channels. Channel state information, obtained through estimation at the receiver, is sent to the transmitter over a feedback channel, where it is used to optimally adapt the transmit power. We consider finite-state optimal policies to reflect the limitations of the feedback channel. We develop an iterative algorithm that determines the optimal finite-state power control policy given the probability density function (PDF) of the fading. Next, we present a discretized formulation of the problem and obtain a suboptimal solution via standard dynamic programming techniques. The discretization of the problem enables us to obtain a suboptimal policy for arbitrary fading channels for which the analytic expression of the fading probability density function is not available. Simulation results are used to draw conclusions regarding the effects of limited feedback channel capacity, delay and number of states on the bit-error rate performance of the proposed policies under slow and moderate fading conditions.

Summary form only given. The combination of jointly optimized rate compatible punctured convolutional (RCPC) codes and channel-matched tree-structured vector quantizers (CM-TSVQ) is shown to provide improved performance, in some cases, compared to the use of CM-TSVQ. The embedded nature of the RCPC codes and CM-TSVQ is inherited by the jointly optimized combination so that the resulting coder is itself progressive. The joint design algorithm allows unequal error protection to be applied to each bit of the CM-TSVQ output. When refinement bits are sent they may be used either to: (1) provide new source coding bits; (2) provide protection to new source coding bias; or (3) provide further protection to previous source coding bits. Soft decoding is used for the RCPC codes and, to allow equitable comparisons to be made, q-bit soft-decision BPSK modulation is used for the baseline CM-TSVQ (to which we make comparisons). The codebook size of the q-bit soft-decision based CM-TSVQ is 2/sup qrk/ where r is the rate in bits per sample and k is the vector dimension. An illustration of the results obtained for a Gauss-Markov source with correlation coefficient /spl rho/=0.9 and a channel SNR=0 dB is shown below. In this case, k=4 and end-to-end distortion is given in dB. In the cases marked "x", the system complexity precluded calculation of reliable results. Each row of the table shows the performance of a single embedded quantizer, with incremental rates of 0.5 bits per sample provided at each refinement. Our results show that the joint combination of soft-decoded RCPC codes and CM-TCVQ provides little rate-distortion advantage over soft CM-TSVQ at the first step of refinement. The same conclusion may be made about the joint combination of soft-decoded RCPC codes and COVQ versus soft COVQ.

We present a scheme for joint source-channel coding for transmission of sources compressed by embedded source coders over a memoryless noisy channel. We find an exact solution to the problem of optimal channel code allocation. Then we investigate the properties of the solution which allow us to transmit the source progressively while retaining the optimality at intermediate and final transmission rates, using rate-compatible codes.

When a feedback channel is available from the receiver to the transmitter, adaptive schemes for source-channel coding can be used for image transmission. In this paper we see that the use of embedded source codes and embedded channel codes, when combined in a hybrid ARQ protocol, can provide the desired flexibility at high efficiency, low complexity and low feedback channel usage. We propose optimized schemes for transmission over Gilbert-Elliot channels, with and without constraints on the feedback channel usage. We observe that the end-to-end quality of the received image can be improved significantly by a moderate use of feedback.

We propose an admission control policy subject to a quality of service constraint for real-time traffic in a packet-switched network. Taking advantage of the statistical multiplexing of voice packets, the calls employ a multi-state source encoder whose state is determined by the level of source activity. Further, in each state, the source encoder outputs an embedded bit stream in the sense that any truncated version of the bit stream is meaningful. This makes it possible to drop some of the less significant packets and suffer some amount of quality degradation in order to handle the congestion problem. An optimal rate assignment among calls is performed which minimizes the average end-to-end distortion. Therefore, the network can admit more calls so long as the average end-to-end distortion is acceptable; consequently, the call blocking probability is decreased.

We propose a fast reconstruction method for a subband-decomposed, progressive signal coding system. We show that unlike the conventional approach which requires a fixed computational complexity, the computational complexity of the proposed approach is proportional to the number of refined coefficients at each level of progression. Therefore, unrefined coefficients do not add to the computational complexity of the proposed scheme. It is shown, through specific examples, that the proposed approach can lead to significant reductions in reconstruction complexity. Furthermore, the proposed approach provides the capability for an online updating of the reconstructed image based on receiving the refinement of each coefficient.

Embedded trellis coded quantization (E-TCQ) is introduced as an embedded quantization technique which achieves good rate-distortion performance for reasonable computational complexity. The performance of E-TCQ is investigated for memoryless Gaussian, Laplacian, and uniform sources. E-TCQ is shown to outperform multi-stage TCQ. For Gaussian and Laplacian sources the performance of ETCQ shows large gains over the performance of scalar embedded quantizers. In the case of a Gaussian source, the performance loss of E-TCQ compared with TCQ decreases with increasing number of trellis states.

Summary form only given. We propose a joint source-channel coding scheme for the transmission of images over noisy channels. In this scheme, the interaction between source coding and channel coding is through a small number of parameters. A robust source coder based on the classification of the discrete wavelet transform (DWT) coefficients of the image is coupled with a flexible error control scheme which uses a bank of channel codes. Robustness in the source coder is achieved by scalar quantization of the coefficients followed by robust arithmetic coding to check catastrophic propagation of errors. Robust arithmetic coding generates a sequence of equal-length packets of bits along with a small number of sensitive bits for synchronization. A bank of rate compatible punctured convolutional codes concatenated with an outer error detection code like CRC is used for providing unequal error protection. Error detection is useful for error masking while decoding. The sensitive bits are protected and transmitted separately. An iterative algorithm is developed for selection of source coding rates and channel codes for the sequences of DWT coefficients. The algorithm uses the probabilities of packet decoding errors for the different channel codes and the operational rate distortion performance of the sequences of coefficients for the joint allocation. The system has a high reliability as the sensitive information is kept small. Some simulation results are provided for the transmission of the 512/spl times/512 image Lenna over binary symmetric channels.

We propose algorithms to design channel-optimized vector quantizers in the presence of channel mismatch. We consider two cases: (i) no information about the statistics of the channel bit error rate is available and (ii) the probability density function of the channel bit error rate is known. We also consider the use of an estimate of the channel signal-to-noise ratio to improve the performance. Simulation results demonstrate the advantages of new design algorithms.

We have incorporated a region-of-interest (RoI) coding functionality into Said and Pearlman's (see IEEE. Trans. CSVT, vol.6, p.243-50, 1996) SPIHT coding with integer transforms. By placing a higher emphasis on the transform coefficients pertaining to the RoI, the RoI is coded with higher fidelity than the rest of the image in earlier stages of progressive reconstruction thus the "important" part of the image is reconstructed more quickly than the rest of the image. This method significantly saves transmission time and storage space by terminating encoding or transmission in situations where the RoI needs to be coded losslessly and the rest of the image visually losslessly (lossy). In our model, the RoI can be flexibly specified either in the beginning or in the middle of the encoding process (either on the original image or on the full- or low-resolution image reconstructed by the decoder), through interaction with the user at the transmitting or the receiving end. Also, the speed with which the quality of the RoI improves in progressive decoding is flexibly specified by the user at either end. The proposed method is especially advantageous in an application where the image is browsed interactively, e.g. telemedicine.

We present a new classification scheme, dubbed spectral classification, which uses the spectral characteristics of the image blocks to classify them into one of a finite number of classes. A vector quantizer with an appropriate distortion measure is designed to perform the classification operation. The application of the proposed spectral classification scheme is then demonstrated in the context of adaptive image coding. It is shown that the spectral classifier outperforms gain-based classifiers while requiring a lower computational complexity.

We study the design of entropy-constrained successively refinable scalar quantizers. We propose two algorithms to minimize the average distortion and design such a quantizer. We consider two sets of constraints on the entropy: (i) constraint on the average rate and (ii) constraint on aggregate rates. Both algorithms can be easily extended to design vector quantizers.

Joint source-channel coding for stationary memoryless and Gauss-Markov sources and binary Markov channels is considered. The channel is an additive-noise channel where the noise process is an Mth-order Markov chain. Two joint source-channel coding schemes are considered. The first is a channel-optimized vector quantizer-optimized for both source and channel. The second scheme consists of a scalar quantizer and a maximum a posteriori detector. In this scheme, it is assumed that the scalar quantizer output has residual redundancy that can be exploited by the maximum a posteriori detector to combat the correlated channel noise. These two schemes are then compared against two schemes which use channel interleaving. Numerical results show that the proposed schemes outperform the interleaving schemes. For very noisy channels with high noise correlation, gains of 4-5 dB in signal-to-noise ratio are possible.

This paper investigates various classification techniques, applied to subband coding of images, as a way of exploiting the nonstationary nature of image subbands. The advantages of subband classification are characterized in a rate-distortion framework in terms of "classification gain" and overall "subband classification gain." Two algorithms, maximum classification gain and equal mean-normalized standard deviation classification, which allow unequal number of blocks in each class, are presented. The dependence between the classification maps from different subbands is exploited either directly while encoding the classification maps or indirectly by constraining the classification maps. The trade-off between the classification gain and the amount of side information is explored. Coding results for a subband image coder based on classification are presented. The simulation results demonstrate the value of classification in subband coding.

The problem of successively refinable scaler quantizer design is considered. The weighted average of the expected distortion at each level of refinement is used as a quantizer figure of merit. Quantizers designed using this criterion can find application in many practical situations. Algorithms are presented for the design of both uniform and non-uniform quantizers and performance of quantizers designed for several sources using these algorithms is presented and compared with the performance of other scalar quantizers.

We propose a fast reconstruction method for a progressive subband-decomposed signal coding system. It is shown that unlike the normal approach which contains a fixed computational complexity, the computational complexity of the proposed approach is proportional to the number of refined coefficients. Therefore, using the proposed approach in image coding applications, we can update the image after receiving each new coefficient and create a continuously refined perception. This can be done without any extra computational cost compared to the normal case where the image is reconstructed after receiving a predefined number of bits. The idea for complexity reduction is extended to general filter banks.

We propose a channel-matched hierarchical table-lookup vector quantizer (CM-HTVQ) which provides some robustness against the channel noise. We use a finite-state channel to model slowly fading channels and propose an adaptive coding scheme to transmit a source over wireless channels. The performance of CM-HTVQ is in general slightly inferior to that of channel-optimized vector quantizer (COVQ) (the performances coincide at some cases); however, the encoder complexity of CM-HTVQ is much less than the encoder complexity of COVQ.

We consider maximum a posteriori (MAP) detection of a binary asymmetric Markov source transmitted over a binary Markov channel. The MAP detector observes a long (but finite) sequence of channel outputs and determines the most probable source sequence. In some cases, the MAP detector can be implemented by simple rules such as the "believe what you see" rule or the "guess zero (or one) regardless of what you see" rule. We provide necessary and sufficient conditions under which this is true. When these conditions are satisfied, the exact bit error probability of the sequence MAP detector can be determined. We examine in detail two special cases of the above source: (i) binary independent and identically distributed (i.i.d.) source and (ii) binary symmetric Markov source. In case (i), our simulations show that the performance of the MAP detector improves as the channel noise becomes more correlated. Furthermore, a comparison of the proposed system with a (substantially more complex) traditional tandem source-channel coding scheme portrays superior performance for the proposed scheme at relatively high channel bit error rates. In case (ii), analytical as well as simulation results show the existence of a "mismatch" between the source and the channel (the performance degrades as the channel noise becomes more correlated). This mismatch is reduced by the use of a simple rate-one convolutional encoder.

New intra- and inter-frame coding techniques for coding a wavelet decomposed video signal are proposed. These methods are based on the required accuracy of motion compensation for each of the different frequency subbands. For each subband, our methods prohibit inter-frame coding and switch to intra-frame coding when the estimated motion vector is not sufficiently accurate. The simple switching mechanism adopted results in a low overhead for coding the adaptation parameters while keeping the loss in coding gain negligible, compared to an unconstrained adaptive strategy in which intra- and inter-frame coding can be switched independently in each subband. The required accuracy of motion compensation is derived analytically for equally distributed pass-band signals and used throughout the paper. Simulation results for practical video sequences are presented.

A new wavelet video coder is proposed which uses entropy-constrained trellis-coded quantization to quantize the inter-frame prediction errors of the decomposed subband data. The video sequence is first spatially decomposed into several subbands and motion compensated in the frequency domain. A simple switching mechanism is used to decide between inter-frame and intra-frame coding on a macro-block basis. Symmetric codebooks have been designed for the quantizers assuming that the subband signals are approximated by a generalized Gaussian source. The output rate is controlled by a feedback quantization control mechanism, leading to a fixed-rate system. Simulation results reported for the "Miss America" sequence, indicate that the proposed codec has a very good rate-distortion performance.

A hierarchical pruned tree-structured vector quantizer (PTSVQ) employing multi-stage PTSVQ's is introduced to encode image wavelet coefficients. The result is a low-complexity and scalable image coding system. The effects of non-square selection of the block sizes and normalization on the performance of the system are investigated.

We describe and show the results of video coding based on a three-dimensional (3-D) spatio-temporal subband decomposition. The results include a 1-Mbps coder based on a new adaptive differential pulse code modulation scheme (ADPCM) and adaptive bit allocation. This rate is useful for video storage on CD-ROM. Coding results are also shown for a 384-kbps rate that are based on ADPCM for the lowest frequency band and a new form of vector quantization (geometric vector quantization (GVQ)) for the data in the higher frequency bands. GVQ takes advantage of the inherent structure and sparseness of the data in the higher bands. Results are also shown for a 128-kbps coder that is based on an unbalanced tree-structured vector quantizer (UTSVQ) for the lowest frequency band and GVQ for the higher frequency bands. The results are competitive with traditional video coding techniques and provide the motivation for investigating the 3-D subband framework for different coding schemes and various applications.

Some psychovisual properties of the human visual system are discussed and interpreted in a mathematical framework. The formation of perception is described by appropriate minimization problems and the edge information is found to be of primary importance in visual perception. Having introduced the concept of edge strength, it is demonstrated that strong edges are of higher perceptual importance than weaker edges (textures). We have also found that smooth areas of an image influence our perception together with the edge information, and that this influence can be mathematically described via a minimization problem. Based on this study, we have proposed to decompose the image into three components: (i) primary, (ii) smooth, and (iii) texture, which contain, respectively, the strong edges, the background, and the textures. An algorithm is developed to generate the three-component image model, and an example is provided in which the resulting three components demonstrate the specific properties as expected. Finally, it is shown that the primary component provides a superior representation of the strong edge information as compared with the popular Laplacian-Gaussian operator edge extraction scheme.

For past I see ibid., vol.4, no.4, p.405 (1995). The use of the image model of Part I is investigated in the context of image compression. The model decomposes the image into a primary component that contains the strong edge information, a smooth component that represents the background slow-intensity variations, and a texture component that contains the textures. The primary component, which is known to be perceptually important, is encoded separately by encoding the intensity and geometric information of the strong edge brim contours. Two alternatives for coding the smooth and texture components are studied: entropy-coded adaptive DCT and entropy-coded subband coding. It is shown via simulations that the proposed schemes, which can be thought of as a hybrid of waveform coding and feature-based coding techniques, result in both subjective and objective performance improvements over several other image coding schemes and, in particular, over the JPEG continuous-tone image compression standard. These improvements are especially noticeable at low bit rates. Furthermore, it is shown that a perceptual tuning based on the contrast-sensitivity of the human visual system can be used in the DCT-based scheme, which in conjunction with the three-component model, leads to additional subjective performance improvements.

Considers an application of a structured, fixed-length vector quantizer, called the scalar-vector quantizer, to image coding. The scalar-vector quantizer, while using fixed-length codewords, achieves a rate-distortion performance close to that of the optimum variable-length encoded scalar quantizer. In the paper, an adaptive 2D DCT coding system is developed in which the DCT coefficients are quantized by scalar-vector quantizers. It is shown that performance comparable to variable-length coding systems can be achieved while maintaining a fixed encoding rate. Preliminary results on the performance of the proposed system when employed over a noisy channel, along with a simple error mitigation mechanism are also provided.>

In this paper we present an adaptive discrete wavelet transform image coding scheme. The main contribution of the work is in developing a simple classification procedure which is used to classify the subband blocks into a finite number of classes. The classified subband blocks are subsequently encoded. The low frequency band is encoded by means of a 2-D DCT using entropy-coded trellis coded quantization (ECTCQ); other bands are directly encoded using ECTCQ. The peak signal-to-noise ratio results of the proposed adaptive system are 0.4-1.0 dB superior to those of its non-adaptive counterpart.>

A new scheme, based on the concept of stressed curves, is developed for extracting significant curvature points on a planar curve. The authors show that the problem has an interesting analogy to stable configurations of a mechanical structure. The stressed curve is generated by recursively solving a potential energy minimization problem. The resulting algorithm is rather simple and is local since the iteration for each point of the curve uses at most four of its nearest neighbors. Examples and some of the applications of this new scheme are provided along with a comparison with the curvature primal sketch scheme. The proposed scheme offers efficient and accurate extraction of significant curvature points with a smaller computational complexity.>

The paper describes a structured vector quantization approach for stationary memoryless sources that combines the scalar-vector quantizer (SVQ) ideas (Laroia and Farvardin, 1993) with trellis coded quantization (Marcellin and Fischer, 1990). The resulting quantizer is called the trellis-based scalar-vector quantizer (TB-SVQ). The SVQ structure allows the TB-SVQ to realize a large boundary gain while the underlying trellis code enables it to achieve a significant portion of the total granular gain. For large block-lengths and powerful (possibly complex) trellis codes the TB-SVQ can, in principle, achieve the rate-distortion bound. As indicated by the results obtained, even for reasonable block-lengths and relatively simple trellis codes, the TB-SVQ outperforms all other fixed-rate quantizers at reasonable complexity.>

A scheme for the optimal shaping of multidimensional constellations is proposed. This scheme is motivated by a type of structured vector quantizer for memoryless sources, and results in N-sphere shaping of N-dimensional cubic lattice-based constellations. Because N-sphere shaping is optimal in N dimensions, shaping gains higher than those of N-dimensional Voronoi constellations can be realized. While optimal shaping for a large N can realize most of the 1.53 dB total shaping gain, it has the undesirable effect of increasing the size and the peak-to-average power ratio of the constituent 2D constellation. This limits its usefulness for many real world channels which have nonlinearities. The proposed scheme alleviates this problem by achieving optimal constellation shapes for a given limit on the constellation expansion ratio or the peak-to-average power ratio of the constituent 2D constellation. Results of Calderbank and Ozarow (1990) on nonequiprobable signaling are used to reduce the complexity of this scheme and make it independent of the data rate with essentially no effect on the shaping gain. Comparisons with Forney's (1989) trellis shaping scheme are also provided.>

The authors consider the problem of detecting a discrete Markov source which is transmitted across a discrete memoryless channel. Two maximum a posteriori (MAP) formulations are considered: (i) a sequence MAP detection in which the objective is to determine the most probable transmitted sequence given the observed sequence and (ii) an instantaneous MAP detection which is to determine the most probable transmitted symbol at time n given all the observations prior to and including time n. The solution to the first problem results in a "Viterbi-like" implementation of the MAP detector (with Large delay) while the latter problem results in a recursive implementation (with no delay). For the special case of the binary symmetric Markov source and binary symmetric channel, simulation results are presented and an analysis of these two systems yields explicit critical channel bit error rates above which the MAP detectors become useful. Applications of the MAP detection problem in a combined source-channel coding system are considered. Here, it is assumed that the source is highly correlated and that the source encoder (a vector quantizer (VQ)) fails to remove all of the source redundancy. The remaining redundancy at the output of the source encoder is referred to as the "residual" redundancy. It is shown, through simulation, that the residual redundancy can be used by the MAP detectors to combat channel errors. For small block sizes, the proposed system beats Farvardin and Vaishampayan's channel-optimized VQ by wide margins. Finally, it is shown that the instantaneous MAP detector can be combined with the VQ decoder to form an approximate minimum mean-squared error decoder.>

Two variable rate versions of the finite-state vector quantizer introduced by J. Foster, M.O. Dunham, and R.M. Gray (FDG) (1985) are presented, with the possibility of using structured as well as unstructured state codebooks. In the first scheme, the state codebook sizes can be different for different states, implying different rate distribution among the states. In the second scheme, in addition to this flexibility, pruned tree-structured vector quantizers are used as the state quantizers, i.e., each of the state quantizers can be a variable-rate encoder. For encoding sampled speech data, both schemes perform significantly better than the fixed-rate FDG scheme, and the second scheme gives the best performance of all. The 2-D extension of the above schemes is considered, and two low-bit rate image coding systems based on them are described.>

A precoding scheme for noise whitening on intersymbol interference (ISI) channels is presented. This scheme is compatible with trellis-coded modulation and, unlike Tomlinson precoding, allows constellation shaping. It can be used with almost any shaping scheme, including the optimal SVQ shaping, as opposed to trellis precoding, which can only be used with trellis shaping. The implementation complexity of this scheme is minimal-only three times that of the noise prediction filter, hence effective noise whitening can be achieved by using a high-order predictor.>

A low-complexity, fixed-rate structured vector quantizer for memoryless sources is described. This quantizer is referred to as the scalar-vector quantizer (SVQ), and the structure of its codebook is derived from a variable-length scalar quantizer. Design and implementation algorithms for this quantizer are developed and bounds on its performance are provided. Simulation results show that performance close to that of the optimal entropy-constrained scalar quantizer is possible with the fixed-rate quantizer. The SVQ is also robust against channel errors and outperforms both Lloyd-Max and entropy-constrained scalar quantizers for a wide range of channel error probabilities.>

For Pt.I see ibid., vol.39, no.3, p.851-67 (1993). The fixed-rate scalar-vector quantizer (SVQ) for quantizing stationary memoryless sources is extended to a specific type of vector source in which each component is a stationary memoryless scalar subsource independent of the other components. Algorithms for the design and implementation of the original SVQ are modified to apply to this case. The resulting SVQ, referred to as the extended SVQ (ESVQ), is then used to quantize stationary sources with memory (with known autocorrelation function). Numerical results are presented for the quantization of first-order Gauss-Markov sources using this scheme. It is shown that the ESVQ-based scheme performs very close to entropy-coded transform quantization while maintaining a fixed-rate output and outperforms the fixed-rate scheme that uses scalar Lloyd-Max quantization of the transform coefficients. It is also shown that this scheme performs better than implementable vector quantizers, especially at high rates. >

The large encoding complexity and sensitivity to channel errors of vector quantization (VQ) are discussed. The performance of two low-complexity VQs-the tree-structured VQ (TSVQ) and the multistage VQ (MSVQ)-when used over noisy channels are analyzed. An algorithm is developed for the design of channel-matched TSVQ (CM-TSVQ) and channel-matched MSVQ (CM-MSVQ) under the squared-error criterion. Extensive numerical results are given for the correlation coefficient 0.9. Comparisons with the ordinary TSVQ and MSVQ designed for the noiseless channel show substantial improvements when the channel is very noisy. The CM-MSVQ, which can be regarded as a block-structured combined source-channel coding scheme, is compared with a block-structured tandem source-channel coding scheme (with the same block length as the CM-MSVQ). For the Gauss-Markov source, the CM-MSVQ outperforms the tandem scheme in all cases that the authors have considered. It is demonstrated that the CM-MSVQ is fairly robust to channel mismatch.>

The authors describe a noisy channel finite-state vector quantizer (FSVQ) for quantizing speech line spectrum pair (LSP) parameters. First they show that under noiseless channel conditions, the ordinary FSVQ of J. Foster et al (1985), when used to encode the LSP parameters, achieves a 1-dB average spectral distortion at 24 b/frame; each LSP vector is split into three subvectors and an eight-state FSVQ is used for each subvector. However, when channel noise is present, the ordinary FSVQ performance degrades drastically. Therefore, the authors describe a modified FSVQ system that is designed taking into account the channel noise. It is shown by means of simulations that the new system is robust to channel noise and outperforms the channel-optimized VQ and the channel-matched multistage VQ of N. Phamdo et al, (1990) by saving 1.5-4 b/vector, depending on the level of noise in the channel.>

The authors described a three-component image model developed based on psychovisual studies of the human visual system. This image model consists of the primary component which contains the strong edge information of the image, the smooth component which represents the background slow-intensity variations, and the texture component which contains the textures. Using the image model, an adaptive discrete cosine transform (DCT) image coder is developed in order to achieve high subjective performance at low bit rates (>

Under the assumption of noiseless transmission the authors develop two entropy-coded subband image coding schemes. The difference between these schemes is the procedure used for encoding the lowest frequency subband: predictive coding is used in one system and transform coding in the other. After demonstrating the unacceptable sensitivity of these schemes to transmission noise, the authors also develop a combined source/channel coding scheme in which rate-compatible convolutional codes are used to provide protection against channel noise. A packetization scheme to prevent infinite error propagation is used and an algorithm for optimal assignment of bits between the source and channel encoders of different subbands is developed. It is shown that, in the presence of channel noise, these channel-optimized schemes offer dramatic performance improvements.>

An algorithm for designing switched scalar quantizers for hidden Markov sources is described. The design problem is cast as a nonlinear optimization problem. The optimization variables are the thresholds and reproduction levels for each quantizer and the parameters defining the next-quantizer map. The cost function is the average distribution incurred by the system in steady-state. The next-quantizer map is treated as a stochastic map so that all of the optimization variables are continuous-valued, allowing the use of a gradient-based optimization procedure. This approach solves a major problem in the design of switched scalar quantizing systems, namely, that of determining an optimal next-quantizer decision rule. Details are given for computing the cost function and its gradient for weighted-squared-error distortion. Simulation results which compare the new system to current systems show that the present system performs better. It is observed that the optimal system can in fact have a next-quantizer map with stochastic components.>

The problem of designing block source codes and modulation signal sets that are both energy and bandwidth constrained is considered. For the class of linear estimator-based decoders, necessary conditions for optimality for the encoder, decoder and modulation signal set are derived. An algorithm that iteratively solves these necessary conditions to converge to a locally optimum solution has been developed. By studying the performance of the previous class of digital communication systems in the limit of infinite encoding rates, it is demonstrated that the MSE of a bandwidth and energy constrained digital system is bounded from below by that of a block pulse amplitude modulation system. This bound is readily computable in terms of the eigenvalues of the source and channel covariance matrices. The results indicate that for a correlated source, a sufficiently noisy channel and specific source block sizes and bandwidths, the digital system performance coincides with the optimum performance theoretically attainable. Further, significant performance improvements over the standard VQ-based system are demonstrated when the channel is noisy.>

A description is given of two variable-rate finite-state vector quantization systems for low bit rate image coding. The first system subtracts the mean from each input block and then encodes the mean-subtracted block by means of the 2-D version of the variable-rate finite-state vector quantization system. The block-mean is separately encoded efficiently by exploiting the high correlation present in the means of the adjacent blocks. At a bit rate of 0.31 b/pixel, a peak signal-to-noise ratio of 31.66 dB is achieved for encoding the 512*512 version of the Lena image using this system. The second system is a generalization of the system described by Riskin, Daly, and Gray (see Proc. IEEE ICASSP, P.1735, 1989). A prediction is made on each pixel using a fifth-order predictor, and the residual is again encoded using the same type of finite-state vector quantization. A peak signal-to-noise ratio of 31.2 dB is achieved at 0.31 bits/pixel for encoding the 512*512 version of Lena using this system.>

Three robust algorithms based on the recently proposed concept of structured vector quantization have been developed for quantization of speech LSP (line spectrum pair) parameters. The first algorithm exploits interframe correlation of the LSP parameters and requires 24 bits per LSP vector to achieve 1 dB average spectral distortion. The second and third algorithms quantize each LSP vector independently and for 1 dB distortion require 29 and 25 bits per vector, respectively. The last two algorithms result in a considerably smaller fraction of frames with distortions greater than 2 dB as compared to other schemes proposed so far.>

The full motion video described is based on the efficient coding of three dimensional subband data. The resulting bit rates of this coder include 384 kb/s results for image sequences of medium complexity and 128 kb/s results for simpler image sequences. The image data are decomposed into spatiotemporal frequency bands and different quantization schemes are applied to each frequency band based on the characteristics of the data in that band. The lowest spatiotemporal frequency band is coded using an unbalanced tree-structured vector quantization technique where the temporal and spatial correlations are exploited in a lossless coding technique referred to as interblock noiseless coding.>

An analysis of the rate-distortion performance of an entropy-constrained block transform quantization scheme operating on first-order stationary Gauss-Markov sources is presented. Uniform threshold quantization is employed to quantize the transform coefficients. An algorithm for optimum stepsize (or, equivalently, entropy) assignment among the quantizers is developed and a simple asymptotic formula indicating the high-rate performance of the block transform quantization scheme is presented. Specific results determining the rate-distortion performance of the entropy-constrained block transform quantization scheme operating upon first-order Gauss-Markov sources are presented, and comparisons are made with the Huang and Schultheiss (1963) block transform quantization, vector quantization, and predictive quantization.>

The performance and complexity of channel-optimized vector quantizers are studied for the Gauss-Markov source. Observations on the geometric structure of these quantizers are made, which have an important implication on the encoding complexity. For the squared-error distortion measure, it is shown that an operation equivalent to a Euclidean distance measurement with respect to an appropriately defined set of points (used to identify the encoding regions) can be used to perform the encoding. This implies that the encoding complexity is proportional to the number of encoding regions. It is then demonstrated that for very noisy channels and a heavily correlated source, when the codebook size is large, the number of encoding regions is considerably smaller than the codebook size-implying a reduction in encoding complexity.>

Several methods based on tree-searched vector quantization (TSVQ) are developed for the efficient encoding of speech line spectrum pair (LSP) parameters. The TSVQ effectively exploits the intraframe correlation of the LSP parameters. To make use of the interframe correlation, a differential coding scheme called interblock noiseless coding (IBNC) is used to encode the binary TSVQ codewords. Two possible applications of this coding scheme are studied: coding at very low bit rates ( approximately=5-10 bits/frame) and coding for high-quality speech (i.e., 1-dB/sup 2/ spectral distortion). In the first application, a frame repeat TSVQ scheme is used with IBNC to reduce the average bit rate. For the second application, in order to obtain the desired reproduction fidelity, the components of the TSVQ error vector are encoded using scalar quantizers. It is shown that, with only one frame encoding delay, a spectral distortion of 1 dB/sup 2/ can be obtained at approximately 20 bits/frame.>

Combined vector quantization (VQ) and two-dimensional discrete cosine transform (DCT) coding of images is discussed. An algorithm for bit allocation for a composite source is developed. This algorithm is used to vary the bit allocation of the transform encoder based on the VQ outputs. An important feature of the scheme is that the bit allocation map used for the scalar quantization of the 2D DCT coefficients varies according to the VQ output-one bit allocation map per VQ codevector. Thus, the VQ achieves two purposes: (1) it performs bit rate reduction, and (2) its output is used to determine the bit-allocation map for the 2D DCT coding. To exploit the interblock correlation, a two-dimensional interblock noiseless coding is used to encode the VQ outputs. Simulation results indicate that performance improvements over several other image-coding schemes can be obtained. The improvements are more noticeable at lower bit rates.>

The design and performance of two entropy-coded subband image coding schemes are studied. The difference between these schemes is the procedure used for encoding the lowest-frequency subband; predictive coding is used in one system and transform coding in the other. Other subbands are encoded using zero-memory quantization. It is shown that, in the absence of channel noise, both schemes perform better than other subband coding methods. The unacceptable sensitivity of these schemes to transmission noise is demonstrated, and a combined source/channel coding scheme in which rate-compatible punctured convolutional codes are used to provide protection against channel noise is developed. In the presence of channel noise, these channel-optimized schemes offer dramatic performance improvements over schemes designed based on a noiseless-channel assumption.>

An investigation is conducted of the effects of various source statistics and buffer management algorithms for a buffer of fixed size, and an algorithm that provides particularly robust rate-distortion performance for a wide range of stationary sources is described. The performance of this scheme, which is referred to as the adaptive entropy-coded quantizer (AECQ), is compared to that of conventional adaptive pulse code modulation (APCM) operating at the same fixed channel transmission rate. Experimental results indicate that the AECQ can provide considerably improved performance and more robust operation than APCM. The relative sensitivity of the AECQ to scale mismatch is directly related to the rather simple memoryless feedback control strategy employed. This might be remedied by alternative choices of the memoryless feedback control function or by introducing memory. The former is much easier to implement and/or analyze than the latter.>

A method is presented for the joint source-channel coding optimization of a scheme based on the two-dimensional block cosine transform when the output of the encoder is to be transmitted via a memoryless binary symmetric channel. The authors' approach involves an iterative algorithm for the design of the quantizers (in the presence of channel errors) used for encoding the transform coefficients. This algorithm produces a set of locally optimum (in the mean-squared error sense) quantizers and the corresponding binary codeword assignment for the assumed transform coefficient statistics. To determine the optimum bit assignment among the transform coefficients, the authors have used an algorithm based on the steepest descent method, which, under certain convexity conditions on the performance of the channel-optimized quantizers, yields the optimal bit allocation. Simulation results for the performance of this locally optimum system over noisy channels have been obtained, and appropriate comparisons with a reference system designed for no channel errors have been made. It is shown that substantial performance improvements can be obtained by using this scheme. Furthermore, theoretically predicted results and rate distortion-theoretic bounds for an assumed two-dimensional image model are provided.>

Several issues related to vector quantization for noisy channels are discussed. An algorithm based on simulated annealing is developed for assigning binary codewords to the vector quantizer code-vectors. It is shown that this algorithm could result in dramatic performance improvements as compared to randomly selected codewords. A modification of the simulated annealing algorithm for binary codeword assignment is developed for the case where the bits in the codeword are subjected to unequal error probabilities (resulting from unequal levels of error protection). An algorithm for the design of an optimal vector quantizer for a noisy channel is briefly discussed, and its robustness under channel mismatch conditions is studied. Numerical results for a stationary first-order Gauss-Markov source and a binary symmetric channel are provided. It is concluded that the channel-optimized vector quantizer design algorithm, if used carefully, can result in a fairly robust system with no additional delay. The case in which the communication channel is nonstationary (as in mobile radio channels) is studied, and some preliminary ideas for quantizer design are presented.>

The intraframe and interframe correlation properties are used to develop two efficient encoding algorithms for speech line spectrum pair (LSP) parameters. The first algorithm (2-D DCT), which requires relatively large coding delays, is based on two-dimensional (time and frequency) discrete cosine transform coding techniques; the second algorithm (DCT-DPCM), which does not need any coding delay, uses one-dimensional discrete cosine transform in the frequency domain and DPCM (differential pulse-code modulation) in the time domain. The performances of these systems for different bit rates and delays are studied, and appropriate comparisons are made. It is shown that an average spectral distortion of approximately 1 dB/sup 2/ can be achieved with 21 and 25 bits/frame using the 2-D DCT and DCT-DPCM schemes, respectively. This is a noticeable improvement over the previously reported bit rates of 32 bits/frame and above.>

The performance of several algorithms for the quantization of the line spectrum pair (LSP) parameters is studied. An adaptive method which utilizes the ordering property of the LSP parameters is presented. The performance of the different quantization schemes is studied on a long sequence of speech samples. For the spectral distortion measure, appropriate performance comparisons between the different quantization schemes are rendered. Experimental results indicate that high-quality synthesized speech can be obtained using the LSP parameters at relatively low rates.>

The performance of several algorithms for the quantization of the LSP (line spectrum polar) parameters is studied. An adaptive method that utilizes the ordering property of the LSP parameters is introduced. A combination of this adaptive algorithm with nonuniform-step-size quantization is shown to be very effective for encoding the LSP parameters. The performance of the different quantization schemes is studied on several sequences of speech samples. For the spectra distortion measure, appropriate performance comparisons between the different quantization schemes are rendered.>

We present an analysis of the zero-memory quantization of memoryless sources when the quantizer output is to be encoded and transmitted across a noisy channel. Necessary conditions for the joint optimization of the quantizer and the encoder/decoder pair are presented, and an iterative algorithm for obtaining a locally optimum system is developed. The performance of this locally optimal system, obtained for the class of generalized Gaussian distributions and the binary symmetric channel, is compared against the optimum performance theoretically attainable (using rate-distortion theoretic arguments), as well as against the performance of Lloyd-Max quantizers encoded using the natural binary code and the folded binary code. It is shown that this optimal design could result in substantial performance improvements. The performance improvements are more noticeable at high bit rates and for broad-tailed densities.

Variable-length codes can be used in entropy coding the outputs of an optimum entropy-constrained quantizer. Transmitting these codes over a synchronous channel; however, requires a buffer connecting the entropy coder to the channel. In a practical application, this buffer is of finite size and hence might overflow or undertow. To alleviate this difficulty, we use an adaptive scheme in which the quantizer parameters are changed successively according to the state of the buffer. Rate-distortion performance of optimum entropy-constrained quantizers in conjunction with this adaptive scheme is studied for the class of generalized Gaussian sources. It is demonstrated through simulations that the overflow/ undertow problem can be practically eliminated at the cost of a negligible increase in average distortion. Furthermore, it is shown that the efficiency of this system is more pronounced at high rates and for more broadtailed source densities. Easily computable upper and lower bounds on the average distortion of the adaptive system are developed.

It is well-known that variable-length coding schemes can be employed in entropy encoding of finite-alphabet sources. To transmit these codes over a synchronous channel, however, requires a buffer. Since in practice this buffer is of finite size, it is subject to both overflow and undertow. The buffer behavior is studied with particular application to Huffman coding of the outputs of an optimum uniform-threshold quantizer driven by a memoryless Gaussian source. Fairly general upper and lower bounds on the average terminal time are developed. Under certain conditions, the tightness of these bounds is verified, and asymptotic formulas are developed. As an example, an encoding scheme employing Huffman codes in conjunction with uniform quantization of memoryless Gaussian sources is considered, and the buffer behavior as a function of the buffer size and output rate is studied.

Quantizers for block transform image coding systems are typically designed under the assumption of Gaussian statistics for the transform coefficients. While convincing arguments can be provided in support of this approach, empirical evidence is presented demonstrating that, except possibly for the dc term, wide departures from Gaussian behavior can be expected for real-world imagery at typical block sizes. In this paper we describe the performance of a block cosine image coding system with an adaptive quantizer matched to the statistics of the transform coefficients. The adaptive quantizer is based upon a recently developed algorithm which employs a training sequence in the design procedure. At encoding rates of approximately 1 bit/pixel and above, this approach results in significant improvement in reconstructed image quality compared to fixed quantization schemes designed under the Gaussian assumption. For rates much below 1 bit/pixel the relative improvement is negligible.

An analysis of the rate-distortion performance of differential pulse code modulation (DPCM) schemes operating on discrete-time auto-regressive processes is presented. The approach uses an iterative algorithm for the design of the predictive quantizer subject to an entropy constraint on the output sequence. At each stage the iterative algorithm optimizes the quantizer structure, given the probability distribution of the prediction error, while simultaneously updating the distribution of the resulting prediction error. Different orthogonal expansions specifically matched to the source are used to express the prediction error density. A complete description of the algorithm, including convergence and uniqueness properties, is given. Results are presented for rate-distortion performance of the optimum DPCM scheme for first-order Gauss-Markov and Laplace-Markov sources, including comparisons with the corresponding rate-distortion bounds. Furthermore, asymptotic formulas indicating the high-rate performance of these schemes are developed for both first-order Gaussian and Laplacian autoregressive sources.

We consider the performance and complexity of optimum quantization schemes subject to an entropy constraint for discrete-time memoryless sources. In particular we describe the performance of optimum zero-memory quantizers for a generalized Gaussian source distribution, Specific implementation of these schemes generally requires variable-length coding of the quantizer output. For transmission over a synchronous fixed-rate channel some form of buffering is required which is subject to overflow or underflow. To alleviate this problem we describe an adaptive scheme in which the quantizer parameters are controlled by the state of the buffer in an effort to avoid overflow/underflow.

The performance of optimum quantizers subject to an entropy constraint is studied for a wide class of memoryless sources. For a general distortion criterion, necessary conditions are developed for optimality and a recursive algorithm is described for obtaining the optimum quantizer. Under a mean-square error criterion, the performance of entropy encoded uniform quantization of memoryless Gaussian sources is well-known to be within0.255bits/sample of the rate-distortion bound at relatively high rates. Despite claims to the contrary, it is demonstrated that similar performance can be expected for a wide range of memoryless sources. Indeed, for the cases considered, the worst case performance is observed to be less than0.3bits/sample from the rate-distortion bound, and in most cases this disparity is less at Iow rates.