We present an iterative equalization scheme that accounts for both inter-carrier interference (ICI) and inter-symbol interference (ISI) on multicarrier communication systems without a cyclic prefix (CP). We employ two equalizers based on the BCJR algorithm that process data in the two-dimensional (2D) time-frequency space; the equalizers exchange soft-bit information with each other and with a channel decoder. We generalize an existing iterative maximum likelihood equalizer (IMLE) to account for ICI-ISI and compare against it. We also use a 1D ICI-only BCJR equalizer with full CP as a baseline. We show that, in presence of moderate amounts of ICI-ISI, our equalizers improve bit error rate (BER) by exploiting Doppler and time diversity. In fact, our CP-free ICI-ISI equalizers achieve the same performance as the full CP ICI-only equalizer on some channels, which results in a data throughput gain. Furthermore, BERs as low as 10-6are achieved in high-spread channels that surpass the orthogonal time-frequency space (OTFS) crystallization condition for interference-free transmission. Even when perfect channel state information (CSI) is not available, our equalizers are more robust, outperforming the IMLE despite higher CSI estimation error variance.

Abstract For model-based black-box testing, test cases are often selected from the syntactic appearance of the specification of the system under test, according to a pre-given test data adequacy criterion. We introduce a novel approach that is semantics-based, independent of the syntactic appearance of the system specification. Basically, we model the system under test as a random variable, whose sample space consists of all possible behavior sets (with respect to the specification) over the known interface of the black-box. The entropy of the system is measured as the (Shannon) entropy of the random variable. In our criterion, the coverage of a test set is measured as the expected amount of entropy decrease (i.e. the expected amount of information gained) once the test set is run. Since our criterion is syntactic independent, we study the notion of information-optimal software testing where, within a given constraint, a test set is selected to gain the most information.

We introduce (finite and infinite) typical paths of a graph and prove that the typical paths carry all information with probability 1, asymptotically. An automata-theoretic characterization of the typical paths is shown: finite typical paths can be accepted by reversal-bounded multicounter automata and infinite typical paths can be accepted by counting Büchi automata (a generalization of reversal-bounded multicounter automata running on ω-words). We take a statechart example to show how to generate typical paths from a graph using SPIN model checker. The results are useful in automata theory since one can identify an information-concentrated-core of a regular language such that only words in the information-concentrated-core carry nontrivial information. When the graph is used to specify the system under test, the results are also useful in software testing by providing an information-theoretic approach to select test cases that carry nontrivial information of the system specification.

Algebraic Code-Excited Linear Prediction (ACELP) is a popular linear prediction speech coding algorithm that provides good performance with reasonable implementation complexity, and requires low transmission bit rate. The excitation sequence is formed as the sum of two quantized excitations: an adaptive (pitch) codebook excitation and an algebraic (fixed) codebook excitation. Algebraic codevectors are sparse.

A block-based Gaussian mixture model (GMM) is used to model the distribution of transform audio data to be encoded using lattice-based spherical vector quantization (LSVQ). The expectation-maximization algorithm is used to design the GMM to model the marginal density of the transform coefficients and the vector energy density. A GMM-based rate-distortion function is derived and shown to closely match the observed spherical VQ performance. The LSVQ transform audio coding performance is characterized for the best lattices known in 4, 8, 16, and 32 dimensions.

A trellis source code and novel variable-length lossless code are used in transform coded excitation audio coding. Implemented within the extended adaptive multi-rate wideband (AMR-WB+) audio coding framework, the proposed quantization and lossless coding method provide between 0.4 and 0.7 dB increase in signal-to-noise ratio over the E8lattice VQ and spherical lossless code used in the AMR-WB+ standard.

A novel quality-scalable hybrid video coding scheme based on coefficient refinement and encoder quality constraints is developed. The technique, which also enables region-of-interest coding, is tested as a possible extension to the H.264 standard with excellent results. That is, the bit-rate increase typically encountered with scalable hybrid coding schemes is, for certain coding parameters, only small to moderate. The double- and triple-layer constellations of the system are shown to perform superior to other systems.

In this paper, low-complexity block-constrained trellis coded quantization (BC-TCQ) structures are introduced, and a predictive BC-TCQ encoding method is developed for quantization of line spectrum frequencies (LSF) parameters for wideband speech coding applications. The performance is compared to the linear predictive coding (LPC) vector quantizers used in the AMR-WB (ITU-G.722.2) speech coding standard, demonstrating reduction in spectral distortion and significant reduction in encoding complexity.

A video transmission system is presented based on the 3D SPIHT (set partitioning in hierarchical trees) algorithm for video compression and turbo codes for channel error protection. The channel considered is a binary symmetric channel with packet erasures, used for modeling the concatenation of a congested wired link followed by a noisy wireless hop. Unequal error protection with turbo codes is used to provide strong channel protection, with rate allocation performed by a Viterbi-based algorithm. The received video quality degrades gracefully in the presence of channel errors.

A method of combined source and channel coding is described that provides robustness to errors from a binary symmetric channel and uses the JPEG2000 (JP2) image compression standard. The source code rate and channel code rate are jointly optimized to produce a stream of fixed-size channel packets, such that the rate allocation complexity grows O(N/sup 2/) with the number of transmitted packets, N. Punctured turbo codes are used for channel coding, providing strong error protection. The rate allocation scheme presented obtains all necessary information from the JP2 encoder, and does not require image decompression.

This paper presents numerical capacity curves for two discrete complex channels: (1) a slow-fading Rayleigh channel with discrete carrier tracking by a phase-locked loop (PLL), where the PLL SNR is proportional to the fading amplitude squared, and (2) a fast-fading Rician channel with carrier phase estimation for the line-of-sight path only. Both channel models assume independent fading of successively received symbols. Capacity calculations are performed for equiprobable signaling with 8-ary and 16-ary amplitude-modulated phase-shift-keyed (AM-PSK) constellations. On the Rayleigh channel, the AM-PSK constellations give gains between 2 and 9 dB over PSK, at SNRs between 5 and 40 dB. For the Rician channel, AM-PSK gives a capacity gain over PSK of up to 0.75 bit at high SNR.

The set partitioning in hierarchical trees (SPIHT) wavelet image coding algorithm can be interpreted as implicitly using classification in its bit-plane coding procedure. The source distribution induced by this classification is studied and rate-distortion performance is evaluated. A quadtree sorting procedure, similar to SPIHT, is used to explicitly form classes of wavelet coefficients. The classes are encoded using arithmetic and trellis-coded quantization. The resulting encoding algorithm offers consistent improvement over SPIHT performance due to the granular gain of the trellis code.

This work describes a method for providing robustness to errors from a binary symmetric channel for the JPEG2000 (J2K) image compression standard. It does so while maintaining full J2K compliance. The source rate and channel rate are jointly optimized by using a Viterbi Algorithm (VA) on a stream of fixed-size channel packets, such that the rate allocation complexity grows O(N/sup 2/) with the number of transmitted packets. Punctured turbo codes are used for the channel coding, providing stronger error protection than previously available codes. The rate allocation scheme presented obtains all necessary information from the J2K encoder, and does not require image decompression.

The SPIHT algorithm is shown to implicitly use quadtree-based classification. The rate-distortion encoding performance of the classes is described, and quantization improvements presented. A new encoding algorithm combines a general SPIHT data structure with the granular gain of multi-dimensional quantization to achieve improved PSNR versus rate performance.

The set partitioning in hierarchical trees (SPIHT) image coding algorithm is observed to provide progressive classification of the wavelet coefficients. The achievable quantization performance of the induced classes is evaluated for entropy coded scalar quantization and trellis coded quantization, and is compared to the first-order rate distortion function.

Two image subband coding methods are introduced as combinations of trellis-coded quantization (TCQ) with zerotree and stack-run coding. These TCQ-based image coding algorithms are compared, at low bit rates, with the set partitioning in hierarchical trees and stack-run scalar quantization-based image coding algorithms. Direct use of TCQ with zerotree or stack-run coding methods is found to provide little or no improvement in rate-distortion performance compared to scalar quantization.

Trellis-coded quantizers (TCQ) are designed for the binary erasure channel (BEC) for memoryless sources. When the bit erasure rate is large, the channel-optimized TCQ can provide up to 1.4 dB improvement over TCQ designed for a lossless channel.

Summary form only given. A novel trellis coded quantisation (TCQ) encoding method is introduced that uses a hard thresholding operation to partition the zig-zag scanned coefficients into two classes: significant, |x|/spl ges/T, and insignificant, |x|

Spatial domain redundancy is studied for packet erasure recovery in a video coding system. The image is partitioned into a checkerboard pattern of white (W) and black (B) blocks. A subset of pixels in the B (W) blocks is selected to be encoded as redundant information with the W(B) blocks. The Yu, Liu, and Marcellin (1996) approach is generalized and several different redundancy patterns are investigated. Significant improvement in interpolation performance is achieved with different redundancy patterns.

Methods are presented for intraframe encoding of line spectrum pairs. A two-stage vector quantizer-lattice vector quantizer (VQ-LVQ) has a 2-3 b/vector performance advantage over the split vector quantizer, and can save 1-3 b/vector, compared to multistage vector quantization, depending on the number of stages and the number of survivors retained at each stage. The vector quantizer-lattice vector quantizer has a moderate computational complexity. Among three trellis codes considered, trellis-coded vector quantization with nonlinear prediction provides line spectrum pair encoding performance similar to the split vector quantizer. Hybrid transformations are developed for encoding the reflection coefficients using vector quantization, and offer a small encoding advantage over the commonly used arcsine transformation and log area ratios.

A robust quantizer is developed for encoding memoryless sources and transmission over the binary symmetric channel (BSC). The system combines channel optimized scalar quantization (COSQ) with all-pass filtering, the latter performed using a binary phase-scrambling/descrambling method. Applied to a broad class of sources, the robust quantizer achieves the same performance as the Gaussian COSQ for the memoryless Gaussian source. This quantizer is used in image coding for transmission over a BSC. The peak signal-to-noise ratio (PSNR) performance degrades gracefully as the channel bit error rate increases.

The trellis-based scalar-vector quantizer (TB-SVQ) for memoryless sources combines the scalar-vector quantizer (SVQ) with trellis coded quantization (TCQ) to achieve both boundary gain and granular gain. The resulting quantizer outperforms all other reasonable complexity fixed-rate quantizers. Unfortunately, the resulting code is catastrophic-a single bit error within a block can propagate indefinitely into other blocks. This correspondence presents a new trellis source code that can achieve essentially the same, or in some cases better, performance as the TB-SVQ for error-free channels, but limits the propagation of channel errors.

Image coding for power- and bandwidth-limited continuous-amplitude channels is considered. We address the problem of power- and bandwidth- allocation for subband image coding where the goal is to minimize the overall end-to-end distortion. The decomposed image is modeled as a composite source, and an algorithm for allocating power and bandwidth among the subsources of this source is proposed. The algorithm is used to compute estimates of the optimum performance theoretically attainable (OPTA) for subband image communication over a power- and bandwidth-limited AWGN channel. A gracefully degrading subband image coder with dynamic power- and bandwidth allocation is simulated and the performance compared to OPTA and to results of other schemes for robust image communication.

We compare using traditional separable filter banks with a simple non-separable filter bank with orientation selectivity, for image compression. The image is decomposed into 19 subbands (6-level) using a separable octave-band decomposition. The high-frequency subband at each decomposition level is split into two bands with an orientation selective filter bank. The image data is then coded using stack-run coding. Results based on subjective testing showed an improvement in the oriented data of the reconstructed images.

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.

A robust quantizer is developed for encoding a variety of memoryless sources and transmission over the binary symmetric channel (BSC). The system combines channel optimized scalar quantization (COSQ) with all-pass filtering, the latter performed using a binary phase-scrambling/descrambling method. Applied to a broad class of sources, the robust quantizer achieves the same performance as the Gaussian COSQ for the memoryless Gaussian source. This quantizer is used for image coding for transmission over a BSC. An explicit error protection code is used only to protect the side information. The PSNR performance degrades gracefully as the channel bit error rate increases.

All-pass filtering is used to reduce the visual impact of erased subband trees. The image quality degrades gracefully with the erasure rate. The paper describes a simple subband coding method for combating packet erasures. No explicit redundancy coding is used, and provided the erasure rate is not too large, the visual impairment due to erasures is minor. The inverse all-pass filtering, at the decoder, has the "spread spectrum" effect of spreading over the whole image the spatially localised errors due to channel erasures. Since the filtering is unitary, the mean-squared error distortion is unchanged; however, the perceptual effect can be dramatic.

Trellis coded quantization is used with subband tree and raster scanning patterns for low-rate image coding. Subjective improvements in decoded image quality are observed, compared to scalar quantizer based methods.

A lattice-based vector quantizer (VQ) and noiseless code are proposed for transform and subband image coding. The quantization is simple to implement, and no vector codebooks need to be stored. The noiseless code enumerates lattice codevectors based on their (weighted) l(1) norm. A software implementation is able to handle lattice codebooks of size 2(256). The image coding performance is shown to be comparable or superior to the best encoding methods reported in the literature.

Many well-known video coding algorithms employ block motion estimation and compensation. But not much attention has been given to the problem of rate allocation for encoding the motion vectors and motion compensated difference frame. We propose entropy-constrained vector quantization of a dense motion vector field as a means of controlling the rate allocated to encoding of motion vectors. An algorithm is proposed for accomplishing this task and extension to motion vector encoding using prediction is discussed.

We present a fixed-rate lattice VQ (FRLVQ) for subband image coding. The fixed-rate lattice VQ is an extension of the entropy-coded lattice vector quantizer (ECLVQ) [Mohdyusof and Fischer, 1994]. For an error-free channel, image coding using ECLVQ provides competitive performance with other methods. ECLVQ is a variable length coder, hence a single bit error in the encoded bit stream could lead to error propagation resulting in severe degradation in image quality. A fixed-rate lattice VQ is constructed from the ECLVQ by grouping together several vectors as a "macroblock". The macroblock is encoded at a fixed rate, while allowing a variety of encoding rates for each vector in the macroblock. In the event of a transmission error, error propagation is confined to that particular macroblock. In this work we assume the encoded bit stream is transmitted over a binary symmetric channel. The simulation results show that the FRLVQ subband image coding provides competitive performance with other fixed-rate image coding systems. The simulation results also indicate FRLVQ performance degrades gracefully in the presence of channel noise.

Generalized Gaussian and Laplacian source models are compared in discrete cosine transform (DCT) image coding. A difference in peak signal to noise ratio (PSNR) of at most 0.5 dB is observed for encoding different images. We also compare maximum likelihood estimation of the generalized Gaussian density parameters with a simpler method proposed by Mallat (1989). With block classification based on AC energy, the densities of the DCT coefficients are much closer to the Laplacian or even the Gaussian.>

A method is presented for encoding memoryless sources using trellis coded quantization (TCQ) with uniform thresholds. The trellis symbols are entropy-coded using arithmetic coding. The performance of the arithmetic coded uniform threshold TCQ, for encoding the family of generalized Gaussian densities, is compared with uniform threshold quantization (UTQ) and the Shannon lower bound (SLB). At high rates, the method performs within 0.5 dB of the rate-distortion bound for the family of generalized Gaussian densities. A simple modification of the uniform codebook is shown to result in improved performance at low bit rates. The arithmetic and trellis coding method is used for encoding image subbands. Coding results for monochrome images are presented and compared with other results in the literature. Working C code that implements arithmetic coded uniform threshold TCQ can be obtained using anonymous ftp.

Image subband and discrete cosine transform coefficients are modeled for efficient quantization and noiseless coding. Quantizers and codes are selected based on Laplacian, fixed generalized Gaussian, and adaptive generalized Gaussian models. The quantizers and codes based on the adaptive generalized Gaussian models are always superior in mean-squared error distortion performance but, generally, by no more than 0.08 bit/pixel, compared with the much simpler Laplacian model-based quantizers and noiseless codes. This provides strong motivation for the selection of pyramid codes for transform and subband image coding.

A pyramid source code is a code that assigns equal-length binary strings to all reproduction codevectors of equal (weighted) /spl epsiv//sub 1/ norm. A pyramid source encoding is partitioned into two concatenated mappings; the first from source word to reproduction codeword within a codebook; the second from the reproduction codevector to a binary string. The first mapping allows distortion and is accomplished using lattice quantization or trellis-coded quantization. The second mapping is noiseless and is denoted as enumeration. Efficient pyramid enumeration encoding and decoding algorithms are presented, for use with fixed-rate or variable-rate pyramid lattice and trellis codes.

A two-stage vector quantizer is introduced that uses an unstructured first-stage codebook and a second-stage lattice codebook. Joint optimum two-stage encoding is accomplished by exhaustive search of the parent codebook of the two-stage product code. Due to the relative ease of lattice vector quantization, optimum encoding is feasible for moderate-to-large encoding rates and vector dimensions, provided the first-stage codebook size is kept reasonable. For memoryless Gaussian and Laplacian sources, encoding rates of 2 to 3 b/sample, and vector dimensions of 8 to 35 the signal-to-noise ratio performance is comparable or superior to equivalent-delay encoding results previously reported. For Gaussian sources with memory, the effectiveness of the encoding method is dependent on the feasibility of using a large enough first-stage vector quantizer codebook to exploit most of the source memory.>

Two-stage vector quantization-lattice vector quantization (VQ-LVQ) is used to encode the speech line spectrum pair (LSP) parameters. VQ-LVQ has the advantages of lower implementational complexity and less required memory than split vector quantization (SVQ) and multi-stage vector quantization (MSVQ) with unstructured codebooks. Based on the authors' speech data base and the same spectral measure, VQ-LVQ can save about 3 bits/frame compared to SVQ, and has advantages of about 2 to 3 bits/frame compared to unstructured codebook MSVQ, depending on the number of stages and the survivor path search complexity. The paper also provides a discussion on some factors influencing the evaluation of the LSP encoding performance.>

This paper investigates the classification technique, applied to subband coding of images, as a way of exploiting the non-stationary nature of image subbands. An algorithm for maximizing the classification gain, is presented. Each subband is optimally classified and the classification map is sent as side information. After optimum rate allocation, the classes are encoded using arithmetic and trellis coded quantization (ACTCQ) system. We compare this approach with other approaches for classification proposed in the literature. We propose a method for reducing the side rate which exploits the dependence between subbands as well as the within band dependence.>

A lattice-based vector quantizer (VQ) and noiseless code are proposed for transform and subband image coding. The quantization is simple to implement and no vector codebooks need be stored. The noiseless code enumerates lattice codevectors based on their (weighted) l/sub 1/ norm. A software implementation is able to handle lattice codebooks of size 2/sup 256/. The image coding performance is shown to be comparable or superior to the best encoding methods reported in the literature.>

This paper presents an asynchronous version of the Add-Compare-Select (ACS) processor. It is shown that in a statistical sense the asynchronous version of the ACS processor is faster than the synchronized version. Thus, it provides an alternative solution to overcome the speed bottleneck of the ACS processor for the Viterbi processor. An 8-bit asynchronous ACS processor requires 1.2 mm/spl times/1.2 mm in a 2/spl mu/ CMOS technology.>

The performance of linear prediction of fullband and subband signals is described in terms of the respective prediction gain. The subband prediction gain is characterized in terms of the fullband signal power spectral density and the frequency response of the subband filters. For Gaussian fullband signals, the asymptotic subband prediction gain can never be larger than the asymptotic fullband prediction gain. Simulation results compare fixed and adaptive fullband and subband prediction gains for Gaussian sources and speech. For speech, the subband prediction gain can exceed the fullband prediction gain.>

Trellis coded vector quantization (TCVQ) and code-excited linear prediction (CELP) coding are combined to form an efficient low-bit rate speech coding system. The resulting system uses a trellis search to select the synthesis filter excitation sequence, and is referred to as trellis excitation coding (TEC). Simulations are performed for encoding rates of 6.4 and 8 kbps. Informal listening tests indicate that the 8 kbps TEC system has quality roughly between that of 6-bit and 7-bit /spl mu/-law PCM with /spl mu/=255. The 6.4 kbps TEC system provides speech quality between 5-bit and 6-bit /spl mu/-law PCM. A subjective comparison with vector sum excited linear prediction (VSELP) indicates that the 8 kbps TEC and the VSELP reconstructed speech is about equally preferable.>

Trellis-coded quantization (TCQ) of memoryless sources is developed for transmission over a binary symmetric channel. The optimized TCQ coder can achieve essentially the same performance as Ayanoglu and Gray's (1987) unconstrained trellis coding optimized for the binary symmetric channel, but with a much lower implementation complexity for transmission rates above 1 b/sample. In most cases, the optimized TCQ coder also provides larger signal-to-noise ratio than Farvardin and Vaishampayan's (1991) channel-optimized vector quantization. Algorithms are developed for the joint design of trellis-coded quantization/modulation (TCQ/TCM). The jointly designed TCQ/TCM system outperforms the straightforward cascade of separately designed TCQ and TCM systems. The improvement is most significant at low channel signal-to-noise ratio. For a first-order Gauss-Markov source, the predictive TCQ/TCM performance can exceed that of optimum pulse amplitude modulation.>

Trellis coded vector quantization (TCVQ) and forward adaptive predictive coding (APC) are used to form an efficient speech coding system operating at bit rates of 16 and 9.6 kb/s. The effectiveness of the system is studied for a variety of system parameters and utterances. Simulation results indicate that segmental signal-to-noise ratios as high as 23.8 and 15.4 dB are obtainable at 16 and 9.6 kb/s respectively. The quality of the reconstructed speech is deemed to be excellent at 16 kb/s and very good at 9.6 kb/s. An algorithm for optimizing the residual codebooks is presented.>

Speech coders employing forward adaptive predictive coding (APC) and operating at medium-to-low bit rates necessitate efficient encoding of the linear predictive coding (LPC) coefficients. Line spectrum pair (LSP) parameters are currently one of the most efficient choices of transmission parameters for the LPC coefficients. The authors briefly reviews LSP parameters and presents several low-delay coding schemes for the parameters. The coders are simulated using data generated from both the autocorrelation and covariance LPC analysis methods. The performances of the coders are given for a variety of rates and LPC analysis conditions. The most efficient scheme developed uses a uses a predictive form of trellis-coded quantization (TCQ). Its performance is comparable or superior to that of other low-delay LSP coding schemes. An enumeration scheme that reduces the rate of a given scalar quantization structure without decreasing coder performance is also presented.>

It is shown that for the realizable subband coding of a wide sense stationary Gaussian source, with the implied separate encoding of the subband signals, the encoding performance is generally inferior to the rate-distortion function of the source. It is established that, for small encoding distortion, except for special cases, the subband coding is generally suboptimum.>

Trellis-coded quantization is generalized to allow noiseless coding of the trellis branch reproduction symbols. An entropy-constrained trellis-coded quantization (ECTCQ) design algorithm is presented, based on the generalized Lloyd algorithm for trellis code design and the entropy-constrained vector quantization design algorithm. ECTCQ systems are designed for memoryless Gaussian and Laplacian sources, and for first- and second-order Gauss-Markov sources. With an 8-state trellis, the mean-squared error ECTCQ encoding performance for memoryless sources with smooth densities is within about 0.5 dB of the rate-distortion function. Small additional improvements are achieved with larger trellises. Similar, though not quite as good, performance is achieved for the Gauss-Markov sources by using the ECTCQ in a predictive coding structure.>

Improved encoding performance is shown by simulation based on trellises generated by rate-1/2 convolutional encoding circuits. The formulation reserves one bit/branch to specify the path through the trellis, and the trellis branch codewords are encoded with a suitable entropy code.>

A noiseless code is combined with a lattice-based vector quantizer (VQ). For small distortion encoding of Laplacian data, the noiseless code has redundancy of at most 2/L, where L is the vector dimension. The VQ and noiseless code are used in discrete cosine transform image coding. An image coder using a single VQ/noiseless code yields performance roughly equivalent to a benchmark coder using entropy-constrained scalar quantization with entropy codes designed for each transform coefficient. The use of several VQ/noiseless codes can further reduce the encoding rate.>

A joint source/channel coding system constructed using trellis coded quantization (TCQ) and trellis coded modulation (TCM) is described. Identical trellises are used in the TCQ and TCM systems, and a straightforward mapping of TCQ codewords to TCM symbols is presented which guarantees that Euclidean squared distance in the channel is commensurate with quantization mean-square error (MSE). Hence, likely TCM error events of small Euclidean distance cause only a small increase in overall source coding MSE.>

Trellis-coded quantization is generalized to allow a vector reproduction alphabet. Three encoding structures are described, several encoder design rules are presented, and two design algorithms are developed. It is shown that for a stationary ergodic vector source, if the optimized trellis-coded vector quantization reproduction process is jointly stationary and ergodic with the source, then the quantization noise is zero-mean and of a variance equal to the difference between the source variance and the variance of the reproduction sequence. Several examples illustrate the encoder design procedure and performance.>

Trellis-coded quantization (TCQ) is developed and applied to the encoding of memoryless and Gauss-Markov sources. The theoretical justification for the approach is alphabet-constrained rate distortion theory, which is a dual to the channel capacity argument that motivates trellis-coded modulation (TCM). The authors adopt the notions of signal set expansion, set partitioning, and branch labeling of TCM, but modify the techniques to account for the source distribution, to design TCQ coders of low complexity with excellent mean-squared-error (MSE) performance. For a memoryless uniform source, TCQ provides an MSE within 0.21 dB of the distortion-rate bound at all positive (integral) rates. The performance is superior to that promised by the coefficient of quantization for all of the best lattices known in dimensions 24 or less. For a memoryless Gaussian source, the TCQ performance at rates of 0.5, 1, and 2 b/sample is superior to all previous results the authors found in the literature. The encoding complexity of TCQ is very modest. TCQ is incorporated into a predictive coding structure for the encoding of Gauss-Markov sources. Simulation results for first-, second-, and third-order Gauss-Markov sources are presented.>

An implementation of trellis coded quantization (TCQ) of memoryless sources on dedicated digital signal processing hardware is described. The effect of encoding delay (i.e. the TCQ symbol release rule) on the overall encoding performance is evaluated. It is shown that quite modest encoding delays cause negligible loss in performance, compared to very long (e.g. 1000 sample) trellis search depths. The hardware requirements of TCQ encoding are discussed. A TCQ implementation on the DSP32 and TMS32020 digital signal processing (DSP) integrated circuits is described. Analytical expressions are provided for the per source sample implementation complexity (in clock cycles) for each DSP integrated circuit.>

A geometric formulation is presented for source coding and vector quantizer design. Motivated by the asymptotic equipartition principle, the authors consider two broad classes of source codes and vector quantizers: elliptical codes and quantizers based on the Gaussian density function, and pyramid codes and quantizers based on the Laplacian density function. Elliptical and weighted pyramid vector quantizers are developed by selecting codewords as points in a lattice that lie on (or near) a specified ellipse or pyramid. The combination of geometric structure and lattice basis allows simple encoding and decoding algorithms.>

Two algorithms are presented that approximate complex numbers by elements of the algebraic integers of Q(w) where w=e/sup 2 pi i/8/. These algorithms substantially reduce the computational burden. Range and memory requirements are given as a function of the desired accuracy, and expressions are obtained for the number of computations required by each algorithm.>

The block and alphabet-constrained formulations are compared for the problem of vector quantization of noisy speech. In the optimum estimator/source-coder structures, a training mode vector quantizer due to Linde et al. (1980) is used as the source coder for the estimator outputs in all cases, and three block estimators and five alphabet-constrained estimators are examined. Objective and subjective performance results are obtained for all eight estimators used in conjunction with training mode vector quantizers at a rate of 1 bit/dimension, for dimensions 1,2,. . . ,8, and 2 bits/dimension, for dimensions 1,2,3, and 4, on five sentences, The results show the superiority of the alphabet-constrained approach, using the frame-adaptive Kalman filter, with improvements in output signal-to-noise ratio over the block approach of 20%.>

Trellis coded quantization is incorporated into a predictive coding structure for encoding sampled speech. Systems are developed using fixed prediction/fixed residual encoding, fixed prediction/adaptive residual encoding, and adaptive prediction/adaptive residual encoding. For a fully adaptive 16 kbps speech coding system, segmental signal-to-noise ratios in the range of 17.5 to 20.2 dB are obtained for a variety of speakers and test sentences. Reconstructed speech obtained from this system can be described as being of excellent communications quality.>

The optimum rate allocation is derived for pyramid vector quantization (PVQ) in transform coding of monochromatic imagery. A modification to the low-rate PVQ encoding algorithm is described, which provides improved performance. Images are encoded with both the PVQ and standard scalar quantizer transform coders, demonstrating that the PVQ coder reduces the mean-square encoding error and better preserves image edges.

A single-chip, dedicated processor for implementation of pyramid vector quantization is presented. The computational requirements of the vector quantizer encoding algorithm are described, and a processor architecture and instruction set selected for efficient implementation of the vector quantization. The processor performance is characterized by analysis and simulation, with a general conclusion that for a state-of-the-art VLSI implementation, 64 dimensional vectors can be vector quantized at a sample rate of 16 kHz.

The technical issues relevant to providing high-quality digital service over analog radio using 1.544-Mbit/s DS-1 data-invoice modems operating through analog supergroup channels with 256-QAM modulation are reviewed. By means of a typical example, the desirability of increasing the fading margin when operating over FM radio systems is demonstrated. This motivates the consideration of coded modulation as a means of extending the threshold of the modem System, so that operation of the modem can be achieved in supergroup channels located higher in the radio baseband. It is found that trellis coded modulation provides better improvement of threshold performance than lattice coded modulation when the actual coding gain realized near the R0channel bound is used rather than the high signalto-noise-ratio (SNR)asymptotic coding gains. Using Ungerboeck's eight-state trellis code [3], a coding gain of approximately 2 dB is found for operation at 28 dB SNR (1 dB from the R0bound). Furthermore, it is found that even at this low operating SNR (where error events at the coded modulation receiver ouput can be long), high-rate, interleaved Reed-Solomon codes, used for burst noise protection at high SNR, still provide over 2 dB of additional coding gain.

The geometric properties of a memoryless Laplacian source are presented and used to establish a source coding theorem. Motivated by this geometric structure, a pyramid vector quantizer (PVQ) is developed for arbitrary vector dimension. The PVQ is based on the cubic lattice points that lie on the surface of anL-dimensional pyramid and has simple encoding and decoding algorithms. A product code version of the PVQ is developed and generalized to apply to a variety of sources. Analytical expressions are derived for the PVQ mean square error (mse), and simulation results are presented for PVQ encoding of several memoryless sources. For large rate and dimension, PVQ encoding of memoryless Laplacian, gamma, and Gaussian sources provides rose improvements of5.64, 8.40, and2.39dB, respectively, over the corresponding optimum scalar quantizer. Although suboptimum in a rate-distortion sense, because the PVQ can encode large-dimensional vectors, it offers significant reduction in rose distortion compared with the optimum Lloyd-Max scalar quantizer, and provides an attractive alternative to currently available vector quantizers.

A modified differential encoding structure is proposed and optimized based upon the concept of preposterior analysis from the theory of alphabet-constrained data compression. Using preposterior analysis, the quantizer input sequence is chosen to minimize the expected distortion over a fixed but arbitrary interval, say,Nsamples long. By computing the expected distortion over future inputs, preposterior analysis allows future behavior to be modeled, but without an encoding delay as in tree coding. The optimized quantizer input sequence is not simply the prediction error as in classical differential pulse code modulation, but it is a weighted combination of the current prediction error and past encoding errors. The optimization is accomplished using a backward dynamic programming argument.

Motivated by the implicit geometry of a stationary, ergodic process, a vector quantizer (VQ) design algorithm is proposed, based on a contour of constant probability density. The approach is explicitly related to the differential entropy of the source, and uses this characteristic of the source to provide structure for the location of VQ output, vectors. A correlated Gaussian source is treated in detail and used as an appropriate model for the design of a contour gain VQ for speech. The resulting mean-square error performance is competitive with alternative VQ based results in the literature.

The relationship between variance estimation and adaptive quantization is investigated for memoryless Laplacian and Gaussian sources. Comparison of block average, exponential average, and maximum likelihood estimators in an adaptive quantization scheme indicates that estimator precision (variance) is more important than accuracy (bias) in minimizing distortion. Further, the block average and exponential average estimators are inconsistent when used in backward adaptive quantization.

A tandem differential pulse code modulation (DPCM) system structure is developed and the design problem formulated. In the simplified case of cascaded quantizers, the low-to-high and high-to-low bit rate tandems are examined and the performance limitations discussed, Finally the performance of tandem DPCM systems operating at various bit rates is evaluated by simulation.

The optimal data compression problem is posed in terms of an alphabet constraint rather than an entropy constraint. Solving the optimal alphabet-constrained data compression problem yields explicit source encoder/decoder designs, which is in sharp contrast to other approaches. The alphabet-constrained approach is shown to have the additional advantages that (1) classical waveform encoding schemes, such as pulse code modulation (PCM), differential pulse code modulation (DPCM), and delta modulation (DM), as well as rate distortion theory motivated tree/trellis coders fit within this theory; (2) the concept of preposterior analysis in data compression is introduced, yielding a rich. new class of coders: and (3) it provides a conceptual framework for the design of joint source/channel coders for noisy channel applications. Examples are presented of single-path differential encoding, delayed (or tree) encoding, preposterior analysis, and source coding over noisy channels.

The results of optimal control theory applied to deterministic fishery models is extended to the continuous stochastic case. The simple logistic model is generalized to stochastic models by singly considering the logistic parameters and the fishing harvest as random processes. Approximate probability density functions are calculated for one model. The stochastic models are applied to the Atlantic sea-scallop fishery. Dynamic programming is used to obtain control solutions.