To address the challenging task of achieving effective voice communication over mobile ad hoc networks (MANETs), we introduce a new multiple description (MD) speech coder based on the AMR-WB (adaptive multirate wideband) standard. The MD coder splits the bitstream of the AMR-WB coder into two redundant sub-streams by directly selecting overlapping subsets of encoded data generated for each frame. The sub-streams are transmitted on different network paths. When both sub-streams arrive at the decoder, an output identical to that of AMR-WB is recovered. If only one substream arrives at the decoder, degraded, but still acceptable, speech quality is obtained. The performance of the multiple description coding system is tested for MANETS with a network simulator and an informal listening test. The results demonstrate that this approach makes effective use of the channel capacity and provides reliable end-to-end connections for voice communication in MANETs.

Mobile ad hoc networks (MANET) have more severe operating conditions than traditional wireless networks. The MAC protocol of IEEE 802.11 mitigates collisions and ensures error-free packet transmissions at the cost of limiting capacity and increasing latency. For voice transmission over MANETs this cost should be minimized. We propose and examine selective error checking (SEC) at the MAC layer of 802.11 that takes advantage of the fact that many of the speech bits can tolerate errors while other bits must be protected for effective reconstruction of the speech. Simulation results demonstrate that the network performance and the speech quality are substantially improved by modifying the MAC layer with SEC to suit a particular GSM speech compression standard, the narrow-band adaptive multirate (NB-AMR) coder operating at a rate of 7.95 kbps.

A novel paradigm based on pitch-adaptive windows is proposed for solving the problem of encoding the fixed codebook excitation in low bit-rate CELP coders. In this method, the nonzero excitation in the fixed codebook is substantially localized to a set of time intervals called windows. The positions of the windows are adaptive to the pitch peaks in the linear prediction residual signal. Thus, high coding efficiency is achieved by allocating most of the available FCB bits to the perceptually important segments of the excitation signal. The pitch-adaptive method is adopted in the design of a novel multimode variable-rate speech coder applicable to CDMA-based cellular telephony. Results demonstrate that the adaptive windows method yields excellent voice quality and intelligibility at average bit-rates in the range of 2.5-4.0 kbps.

This paper presents a high quality enhanced waveform interpolative (EWI) speech coder at low bit-rate. The system incorporates novel features such as optimization of the slowly evolving waveform (SEW) for interpolation, analysis-by-synthesis (AbS) vector quantization (VQ) of the SEW dispersion phase, dual-predictive AbS quantization of the SEW, efficient parameterization of the rapidly-evolving waveform (REW) magnitude, and VQ of the REW parameter, a special pitch search for transitions, and switched-predictive analysis-by-synthesis gain VQ. Subjective tests indicate that the 2.8 kb/s EWI coder's quality exceeds that of G.723.1 at 5.3 kb/s, and it is slightly better than that of G.723.1 at 6.3 kb/s.

A new hybrid speech coding technique is presented in this paper, which combines a frequency-domain parametric coder (for stationary voiced and stationary unvoiced speech) with a time-domain waveform coder (for transition speech). Our hybrid coder uses a parametric representation for the excitation of a linear-prediction filter. The excitation of stationary voiced speech is a sum of harmonic cosines with interpolated magnitudes and a synthetic phase model, the excitation for stationary unvoiced speech is a spectrally shaped noise, and the excitation for transition speech is a set of signed pulses. Signal alignment when switching between the harmonic excitation of stationary voiced speech and the pulse model used for transition speech is required, and achieved by special alignment procedures. A 4 kb/s hybrid coder, which achieves high-quality reconstructed speech, is described. The 4 kb/s hybrid coder employs a neural network classifier, and a novel pitch detection and harmonic bandwidth estimation algorithm. The locations of excitation pulses for coding transitions are determined by analysis-by-synthesis. A simple and efficient dimension conversion and quantization of the harmonic. Spectral magnitudes of voiced speech was devised, combining the general nonsquare transform (NST) or dimension conversion and a weighted vector quantization (VQ) approach. Subjective listening tests demonstrate that the 4 kb/s hybrid coding scheme competes favorably with CELP coders at low bit-rates.

We introduce a general and powerful approach to sinusoidal modeling of speech wherein a closed-loop analysis-by-synthesis (AbS) technique sequentially extracts the parameters for each sinusoidal component. Low bit-rate speech coding is achieved by efficiently constraining the allowed frequencies of sinusoidal components into sets of frequency intervals or bins. In conjunction with the closed-loop analysis, the constrained frequency regions allow us to efficiently vector quantize the frequency information in each frame. In voiced frames, two sets of frequency vectors are generated: one for harmonically related components and the other for non-harmonically related components of the voiced segment. In transition frames, a vector of nonuniformly spaced frequencies is selected from a frequency codebook using frequency bin vector quantization (FBVQ) to represent the frequency domain information. The effectiveness of the coding scheme is enhanced by exploiting the critical band concept of auditory perception in defining the frequency bins. In transition segments, the sinusoidal phases are modeled and coded. Subjective tests with a partially quantized model indicate that, for a target rate of 4 kbps, the coder quality exceeds that of the G.729 standard at 8 kbps.

This paper presents a high quality enhanced waveform interpolative (EWI) speech coder at 2.8 kbps. The system incorporates novel features such as: dual-predictive analysis-by-synthesis (AbS) quantization of the slowly evolving waveform (SEW), efficient parametrization of the rapidly evolving waveform (REW) magnitude, and AbS vector quantization (VQ) of the REW parameter. Subjective tests indicate that its quality exceeds that of G.723.1 at 5.3 kbps, and it is slightly better than that of G.723.1 at 6.3 kbps.

This paper proposes a bandwidth-scalable coding scheme based on the G.729 standard as a base layer coder. In the scheme, according to the channel conditions, the output speech of the decoder can be selected to be narrowband (4-kHz bandwidth) or wideband (8-kHz bandwidth). The proposed scheme consists of two layers: base and enhancement. The base coder uses the G.729 algorithm to encode narrowband speech. The enhancement coder is based on a full-band CELP model and it encodes wideband speech while making use of the available base layer information. Two bandwidth-scalable coders are designed: one is scalable with the 8 kbit/s G.729 base coder and another with the 6.4 kbit/s G.729 (Annex D) base coder. Subjective tests show that, for wideband speech, the proposed coders at 16 kbit/s achieve better performance than the 16 kbit/s MPEG-4 CELP with bandwidth scalability.

This paper presents a 1.2 kbps speech coder based on the mixed excitation linear prediction (MELP) analysis algorithm. In the proposed coder, the MELP parameters of three consecutive frames are grouped into a superframe and jointly quantized to obtain a high coding efficiency. The interframe redundancy is exploited with distinct quantization schemes for different unvoiced/voiced (U/V) frame combinations in the superframe. Novel techniques for improving performance make use of the superframe structure. These include pitch vector quantization using pitch differentials, joint quantization of pitch and U/V decisions and LSF quantization with a forward-backward interpolation method. Subjective test results indicate that the 1.2 kbps speech coder achieves approximately the same quality as the proposed federal standard 2.4 kbps MELP coder.

Harmonic coders that synthesize speech without transmitting phase information abandon the benefits of closed-loop parameter estimation via waveform matching. In this paper, we show that effective closed loop parameter estimation can be achieved when a suitable time-scale modification is applied to the speech LP residual in harmonic coders. The concept is demonstrated here specifically for pitch estimation, but is more broadly applicable. For each of a set of pitch candidates generated by a time-domain pitch estimator, the residual is modified to match the pitch contour derived from that candidate. The best candidate is selected by evaluating for each candidate the match between the modified residual and the synthesized residual. The new pitch estimation algorithm significantly reduces gross pitch errors compared to a conventional time-domain pitch estimator and enhances the perceptual performance of a 4 kbps harmonic coder.

This paper presents work based on an analysis-by-synthesis approach which aims to develop a reversible coding system for prosody, capable of deriving a `linguistic-like' surface phonological representation directly from acoustic data that is sufficient to reproduce a synthetic version of the original utterance without significant loss of linguistic information. With such a coding system, capable of representing any significant prosodic distinctions, the task of predicting such representations would be greatly simplified, becoming one of mapping between sets of symbolic representations. This approach has already been applied to the stylisation and symbolic coding of fundamental frequency curves by means of the INTSINT transcription system. An automatic version has also been proposed. This paper presents a preliminary proposal for an extension to the INTSINT system to cover segmental duration and the relative alignment of phonematic and tonal segments. 1. INTRODUCTION: INTSINT TRANSCRIP...

In this research, we have investigated about prosodic features of Farsi (Persian) language and quantified major stress rules and some intonation rules for speech synthesis purpose. The research is mostly concentrated on pitch variations and then on durational changes. We have implemented the proposed simplified prosodic rules using a Klatt formant synthesizer, specially modified for Farsi phonemes. In order to achieve to a better speech quality, we have exploited different allophonic forms for some consonants, leading to a total of 207 Farsi diphones synthesized by the speech synthesizer. Subjective listening tests show that the addition of the prosodic features drastically increases both the intelligibility and naturalness of the synthesized speech. The synthesizer is software-implemented on a Pentium PC and operates in real-time.

A new learning algorithm is proposed for piecewise regression modeling. It employs the technique of deterministic annealing to design space partition regression functions. While the performance of traditional space partition regression functions such as CART and MARS is limited by a simple tree-structured partition and by a hierarchical approach for design, the deterministic annealing algorithm enables the joint optimization of a more powerful piecewise structure based on a Voronoi partition. The new method is demonstrated to achieve consistent performance improvements over regular CART as well as over its extension to allow arbitrary hyperplane boundaries. Comparison tests, on several benchmark data sets from the regression literature, are provided.

In code-excited linear prediction (CELP) coders, computation of linear prediction coefficient (LPC) parameters is generally performed open-loop, and subsequently the pitch predictor parameters are found for each subframe by a closed-loop search. To improve these two parameter sets we propose a new closed-loop joint search technique for joint optimization, called the joint pitch and LPC (JP-LPC) method. When applied to a reference CELP coder, performance gains include an overall improvement in segmental signal-to-noise ratio (SNR) of 0.61 dB and for subframes with high pitch periodicity, a gain of 0.83 dB.

Phonetic classification of speech frames allows distinctive quantization and bit allocation schemes suited to the particular class. Separate quantization of the linear predictive coding (LPC) parameters for voiced and unvoiced speech frames is shown to offer useful gains for representing the synthesis filter commonly used in code-excited linear prediction (CELP) and other coders. Subjective test results are reported that determine the required bit rate and accuracy in the two classes of voiced and unvoiced LPC spectra for CELP coding with phonetic classification. It was found, in this context, that unvoiced spectra need 9 b/frame or more whereas voiced spectra need 25 b/frame or more with the quantization schemes used. New spectral distortion criteria needed to assure transparent LPC spectral quantization for each voicing class in CELP coders are presented. Similar subjective test results for speech synthesized from the true residual signal are also presented, leading to some interesting observations on the role of the analysis-by-synthesis structure of CELP. Objective performance assessments based on the spectral distortion measure are also presented. The theoretical distortion-rate function for the spectral distortion measure is estimated for voiced and unvoiced LPC parameters and compared with experimental results obtained with unstructured vector quantization (VQ). These results show a saving of at least 2 b/frame for unvoiced spectra compared to voiced spectra to achieve the same spectral distortion performance.

We attack the general problem of HMM-based speech recognizer design, and in particular, the problem of isolated letter recognition in the presence of background noise. The standard design method based on maximum likelihood (ML) is known to perform poorly when applied to isolated letter recognition. The minimum classification error (MCE) approach directly targets the ultimate design criterion and offers substantial improvements over the ML method. However, the standard MCE method relies on gradient descent optimization which is susceptible to shallow local minima traps. We propose to overcome this difficulty with a powerful optimization method based on deterministic annealing (DA). The DA method minimizes a randomized MCE cost subject to a constraint on the level of entropy which is gradually relaxed. It may be derived based on information-theoretic or statistical physics principles. DA has a low implementation complexity and outperforms both standard ML and the gradient descent based MCE algorithm by a factor of 1.5 to 2.0 on the benchmark CSLU spoken letter database. Further, the gains are maintained under a variety of background noise conditions.

In this paper we present a new approach for speech coding, which combines frequency-domain harmonic coding for periodic and "noise like" unvoiced segments of speech with a time-domain waveform coder for transition signals. This hybrid coder requires special handling of the boundary between voiced and transition segments. We outline the details of a 4 kbps hybrid coder and present subjective quality test results of this coder.

A novel low-delay wideband speech coder, called multiband CELP (MB-CELP) achieves a delay of about 10 ms, by exploiting time-domain correlations with a two stage linear prediction scheme. A low-order forward adaptive LP stage models the coarse shape, and a high order backward-adaptive LP stage models the fine structure of the input spectrum. A conditional pitch prediction method improves the performance of the coder for speech without degrading the music performance. A multi-band bank of off-line filtered codebooks generates the excitation signal. A 24 kbps version of the coder has nine multi-band codebooks with a nonuniform bandwidth. Subjective comparison tests show that this coder outperforms the G.722 coder at the bit-rate of 56 kbps.

Many image compression techniques require the quantization of multiple vector sources with significantly different distributions. With vector quantization (VQ), these sources are optimally quantized using separate codebooks, which may collectively require an enormous memory space. Since storage is limited in most applications, a convenient way to gracefully trade between performance and storage is needed. Earlier work addressed this problem by clustering the multiple sources into a small number of source groups, where each group shares a codebook. We propose a new solution based on a size-limited universal codebook that can be viewed as the union of overlapping source codebooks. This framework allows each source codebook to consist of any desired subset of the universal code vectors and provides greater design flexibility which improves the storage-constrained performance. A key feature of this approach is that no two sources need be encoded at the same rate. An additional advantage of the proposed method is its close relation to universal, adaptive, finite-state and classified quantization. Necessary conditions for optimality of the universal codebook and the extracted source codebooks are derived. An iterative design algorithm is introduced to obtain a solution satisfying these conditions. Possible applications of the proposed technique are enumerated, and its effectiveness is illustrated for coding of images using finite-state vector quantization, multistage vector quantization, and tree-structured vector quantization.

In a standard transform coding scheme of images or video, the decoder can be implemented by a table-lookup technique without the explicit use of an inverse transformation, In this new decoding method, each received code index of a transform coefficient addresses a particular codebook to fetch a component code vector that resembles the basis vector of the linear transformation. The output image is then reconstructed by summing a small number of nonzero component code vectors. With a set of well-designed codebooks, this new decoder can exploit the correlation among the quantized transform coefficients to achieve better rate-distortion performance than the conventional decoding method. An iterative algorithm for designing a set of locally optimal codebooks from a training set of images is presented. We demonstrate that this new idea can be applied to decode improved quality pictures from the bitstream generated from a standard encoding scheme of still images or video, while the complexity is low enough to justify practical implementation.

We propose new techniques for natural quality variable rate spectral speech coding at an average rate of 2.2 kbps for dialog speech and 2.8 kbps for monolog speech. The coder models the Fourier spectrum of each frame and it builds on recent enhancements to the classical multiband excitation (MBE) approach. New techniques for robust pitch estimation and tracking, for efficient quantization of voiced and unvoiced spectra and encoding of partial phase information are the key features that result in improved quality over earlier spectral vocoders. Subjective performance results are reported which show that the coder is very close in quality to the ITU-T G.723.1 algorithm at 5.3 kbps.

A new and effective design method is presented for statistical regression functions that belong to the class of mixture models. The class includes the hierarchical mixture of experts (HME) and the normalized radial basis functions (NRBF). Design algorithms based on the maximum likelihood (ML) approach, which emphasize a probabilistic description of the model, have attracted much interest in HME and NRBF models. However, their design objective is mismatched to the original squared-error regression cost and the algorithms are easily trapped by poor local minima on the cost surface. In this paper, we propose an extension of the deterministic annealing (DA) method for the design of mixture-based regression models. We construct a probabilistic framework, but unlike the ML method, we directly optimize the squared-error regression cost, while avoiding poor local minima. Experimental results show that the DA method outperforms standard design methods for both HME and NRBF regression models.

A novel low-delay wideband speech coder, called multiband CELP (MB-CELP), overcomes the major obstacles usually associated with two traditional CELP approaches to wideband speech coding-namely fullband CELP and split-band CELP. The new MB-CELP coder employs a multi-band bank of off-line filtered excitation codebooks, fullband linear prediction synthesis, and minimization of the error between the original and the synthesized speech signal over the full frequency range. A 16 kbps version of the MB-CELP coder with two equal bands, is described. Subjective comparison test results show that this coder performs better than the G.722 coder at a bit-rate of 48 kbps.

A novel paradigm for fractal coding selectively corrects the fractal code for selected domain blocks with an image-adaptive VQ codebook. The codebook is generated from the initial uncorrected fractal code and is therefore available at the decoder. An efficient trade-off results between incremental performance and bit rate.

A technique for nonlinear prediction of speech via local linear prediction (LLP) is presented and applied to LD-CELP at 16 kbps. With 18th-order backward adaptive LLP for voiced frames, the hybrid LD-CELP coder gives higher segmental signal-to-noise ratio (SNR) compared to a reference version of the ITU-T G.728 LD-CELP algorithm, which has a 50th-order backward adaptive linear predictor. The computational complexity for LLP analysis is significantly less than that of a conventional one-step recursive LLP, and the LLP method gives better prediction gain and a remarkably "whiter" residual compared to backward adaptive linear predictor. With an appropriate state space neighborhood for local linear analysis, the short-delay predictor is also able to effectively model long-term correlations without requiring pitch estimation.

We present a speech coding algorithm called mixed-domain residual coding (MDRC) wherein a prototype pitch cycle in each frame of the speech residual is coded in the time-domain while interpolation of the residual signal is performed in the frequency-domain. A novel quantization scheme takes into account time scaling and differentially codes successive prototypes with a closed-loop perceptually-weighted search. A fixed-rate (3.15 kb/s) implementation of MDRC achieves quality better or comparable to higher rate coders such as FS 1016 CELP and IMBE.

In vector quantization, one approximates an input random vector, Y, by choosing from a finite set of values known as the codebook. We consider a more general problem where one may not have direct access to Y but only to some statistically related random vector X. We observe X and would like to generate an approximation to Y from a codebook of candidate vectors. This operation, called generalized vector quantization (GVQ), is essentially that of quantized estimation. An important special case of GVQ is the problem of noisy source coding wherein a quantized approximation of a vector, Y, is obtained from observation of its noise-corrupted version, X. The optimal GVQ encoder has high complexity. We overcome the complexity barrier by optimizing a structurally-constrained encoder. This challenging optimization task is solved via a probabilistic approach, based on deterministic annealing, which overcomes problems of shallow local minima that trap simpler descent methods. We demonstrate the successful application of our method to the coding of noisy sources.

In many signal compression applications, the evolution of the signal over time can be represented by a sequence of random vectors with varying dimensionality. Frequently, the generation of such variable-dimension vectors can be modeled as a random sampling of another signal vector with a large but fixed dimension. Efficient quantization of these variable-dimension vectors is a challenging task and a critical issue in speech coding algorithms based on harmonic spectral modeling. We introduce a simple and effective formulation of the problem and present a novel technique, called variable-dimension vector quantization (VDVQ), where the input variable-dimension vector is directly quantized with a single universal codebook. The application of VDVQ to low bit-rate speech coding demonstrates significant gain in subjective quality as well as in rate-distortion performance over prior indirect methods.

Current methods for the design of pruned or unbalanced tree-structured vector quantizers such as the generalized Breiman-Friedman-Olshen-Stone (GBFOS) algorithm proposed in 1980 are effective, but suffer from several shortcomings. We identify and clarify issues of suboptimality including greedy growing, the suboptimal encoding rule, and the need for time sharing between quantizers to achieve arbitrary rates. We then present the leaf-optimal tree design (LOTD) method which, with a modest increase in design complexity, alters and reoptimizes tree structures obtained from conventional procedures. There are two main advantages over existing methods. First, the optimal entropy-constrained nearest-neighbor rule is used for encoding at the leaves; second, explicit quantizer solutions are obtained at all rates without recourse to time sharing. We show that performance improvement is theoretically guaranteed. Simulation results for image coding demonstrate that close to 1 dB reduction of distortion for a given rate can be achieved by this technique relative to the GBFOS method.

Many compression applications consist of compressing multiple sources with significantly different distributions. In the context of vector quantization (VQ) these sources are typically quantized using separate codebooks. Since memory is limited in most applications, a convenient way to gracefully trade between performance and storage is needed. Earlier work addressed this problem by clustering the multiple sources into a small number of source groups, where each group shares a codebook. As a natural generalization, we propose the design of a size-limited universal codebook consisting of the union of overlapping source codebooks. This framework allows each source codebook to consist of any desired subset of the universal codevectors and provides greater design flexibility which improves the storage-constrained performance. Further advantages of the proposed approach include the fact that no two sources need be encoded at the same rate, and the close relation to universal, adaptive, and classified quantization. Necessary conditions for optimality of the universal codebook and the extracted source codebooks are derived. An iterative descent algorithm is introduced to impose these conditions on the resulting quantizer. Possible applications of the proposed technique are enumerated and its effectiveness is illustrated for coding of images using finite-state vector quantization.

The low bit rate enhanced multiband excitation or EMBE speech coder adds several important new features including phonetic classification and a naval spectral quantization technique called variable dimension vector quantization (VDVQ) to the basic multiband excitation vocoder. Phonetic classification allows the adaptation of spectral modeling and quantization to the local acoustic-phonetic character of the speech signal, enhancing quality and robustness. The VDVQ scheme quantizes the log-spectrum with relatively few bits while preserving perceptually important features. Both the fixed rate (2.4 kb/s) and the variable rate (1.44 kb/s average) implementations of EMBE deliver speech quality comparable to the 4.8 kb/s Federal Standard 1016 CELP coder and the 4.15 kb/s Inmarsat-M standard IMBE coder.

Variable rate quantization of the linear predictive coding (LPC) parameters based on phonetic classification of the speech frame results in substantial performance gain. Speech frames are classified as unvoiced or voiced and are separately quantized with VQ codebooks designed for each class. Performance results, including listening tests, show that for transparent quality roughly 9 bits is sufficient for unvoiced frames and 24 bits for voiced frames. Test results of LPC quantization are described for a variable rate phonetically segmented CELP coder and for the synthesis of speech from the prediction residual.

An adaptive postfiltering algorithm for enhancing the perceptual quality of coded speech is presented. The postfilter consists of a long-term postfilter section in cascade with a short-term postfilter section and includes spectral tilt compensation and automatic gain control. The long-term section emphasizes pitch harmonics and attenuates the spectral valleys between pitch harmonics. The short-term section, on the other hand, emphasizes speech formants and attenuates the spectral valleys between formants. Both filter sections have poles and zeros. Unlike earlier postfilters that often introduced a substantial amount of muffling to the output speech, our postfilter significantly reduces this effect by minimizing the spectral tilt in its frequency response. As a result, this postfilter achieves noticeable noise reduction while introducing only minimal distortion in speech. The complexity of the postfilter is quite low. Variations of this postfilter are now being used in several national and international speech coding standards. This paper presents for the first time a complete description of our original postfiltering algorithm and the underlying ideas that motivated its development.>

Optimal vector quantization of variable-dimension vectors in principle is feasible by using a set of fixed dimension VQ codebooks. However, for typical applications, such a multi-codebook approach demands a grossly excessive and impractical storage and computational complexity. Efficient quantization of such variable-dimension spectral shape vectors is the most challenging and difficult encoding task required in an important family of low bit-rate vocoders. The authors introduce a simple and effective formulation of variable-dimension vector quantization (VDVQ) which quantizes variable-dimension vectors using a single universal codebook having fixed dimension yet covering the entire range of input vector dimensions under consideration. This VDVQ technique is applied to quantize variable-dimension spectral shape vectors leading to a high quality speech coder at the low bit-rate of 2.5 kb/s. The combination of a universal spectral codebook and structured VQ reduces storage and computational complexity, yet delivers a high quantization efficiency and enhanced perceptual quality of the coded speech.>

The authors address the variable rate tree-structured vector quantizer design problem, wherein the rate is measured by the quantizer's entropy. For this problem, tree pruning via the generalized Breiman-Friedman-Olshen-Stone (1980) algorithm obtains solutions which are optimal over the restricted solution space consisting of all pruned trees derivable from an initial tree. However, the restrictions imposed on such solutions have several implications. In addition to depending on the tree initialization, growing and pruning solutions result in tree-structured vector quantizers which use a sub-optimal encoding rule. To remedy the latter problem, they consider a "tree-constrained" version of entropy-constrained vector quantizer design. This leads to an optimal tree-structured encoding rule for the leaves. In practice, though, improvements obtained in this fashion are limited by the tree initialization, as well as by the sub-optimal encoding performed at non-leaf nodes. To address these problems, they develop a joint optimization method which is inspired by the deterministic annealing algorithm for data clustering, and which extends their previous work on tree-structured vector quantization. The method is based on the principle of minimum cross entropy, using informative priors to approximate the unstructured solution while imposing the structural constraint. As in the original deterministic annealing method, the number of distinct codevectors (and hence the tree) grows by a sequence of bifurcations in the process, which occur as solutions of a free energy minimization. Their method obtains performance gains over growing and pruning methods for variable rate quantization of Gauss-Markov and Gaussian mixture sources.>

Speech and audio compression has advanced rapidly in recent years spurred on by cost-effective digital technology and diverse commercial applications. Recent activity in speech compression is dominated by research and development of a family of techniques commonly described as code-excited linear prediction (CELP) coding. These algorithms exploit models of speech production and auditory perception and offer a quality versus bit rate tradeoff that significantly exceeds most prior compression techniques for rates in the range of 4 to 16 kb/s. Techniques have also been emerging in recent years that offer enhanced quality in the neighborhood of 2.4 kb/s over traditional vocoder methods. Wideband audio compression is generally aimed at a quality that is nearly indistinguishable from consumer compact-disc audio. Subband and transform coding methods combined with sophisticated perceptual coding techniques dominate in this arena with nearly transparent quality achieved at bit rates in the neighborhood of 128 kb/s per channel.>

A low-complexity iterative algorithm is introduced for joint estimation of forward and backward motion vectors in interpolative prediction of video. Starting from the initial values obtained by a commonly-used block matching independent search method, the motion vectors are iteratively refined until a locally optimal solution to the motion estimation problem for interpolative prediction is achieved. Each iteration consists of a series of two similar procedures. First, the backward motion vector is fixed and a new forward motion vector is searched to minimize the interpolation error. Then the forward motion vector is fixed and the backward motion vector is similarly refined by minimizing the interpolation error. This process is repeated until the interpolation error stops decreasing. Computer simulation results demonstrate that with this technique the prediction error in some scenes is significantly reduced.

A Euclidean code is a finite set of points in n-dimensional Euclidean space /spl Rscr//sup n/. The total number of nearest neighbors of a given codepoint in the code is called its touching number. We show that the maximum number of codepoints F/sub n/ that can share the same nearest-neighbor codepoint is equal to the maximum kissing number /spl tau//sub n/ in n dimensions, that is, the maximum number of unit spheres that can touch a given unit sphere without overlapping. We then apply a known upper bound on /spl tau//sub n/ to obtain F/sub n//spl les/2/sup n(0.401+o(1))/, which improves upon the best known upper known upper bound of F/sub n//spl les/2/sup n(1+o(1))/. We also show that the average touching number T of all the points in a Euclidean code is upper bounded /spl tau//sub n/.>

With respect to the generalized product code (GPC) model for structured vector quantization, multistage VQ (MSVQ) and tree-structured VQ are members of a family of summation product codes (SPCs), defined by the prototypical synthesis function x=f/sub 1/+...+f/sub s/, where f/sub i/, i=1, . . ., s are the residual vector features. The authors describe an algorithm paradigm for the joint design of the feature codebooks constituting a GPC. They specialize the paradigm to a joint design algorithm for the SPCs and exhibit experimental results for the MSVQ of simulated sources. The performance improvements over conventional 'greedy' design are essentially 'free' as the only cost is a moderate increase in design complexity.>

In this paper, we present a novel method for sub-pixel motion estimation. Compared to traditional methods, our technique offers a significantly reduced complexity by eliminating the explicit interpolation of pixel values at a finer sampling grid and avoiding the distortion evaluation for each candidate sub-pixel motion vector. Simulation results confirm that its performance is virtually indistinguishable from that of a traditional sub-pixel motion estimator. To illustrate applications of the new method we have developed a variable resolution motion estimator. The performance of the variable resolution motion estimator is evaluated by replacement of the fixed resolution motion estimator in Simulation Model 3 of MPEG-1 video compression standard by the variable resolution motion estimator.

Multispectral satellite images of the earth consist of sets of images obtained by sensing electromagnetic radiation in different spectral bands for each geographical region. We have applied a variable rate multistage vector quantizer for the compression of multispectral imagery. Spectral and spatial correlation are simultaneously exploited by forming vectors from 3-dimensional data blocks. The wide variation in entropy across the data set is efficiently exploited by an adaptive bit allocation algorithm based on a greedy approach where the rate- distortion trade-off is locally optimized for each successive encoding stage. Simulation results on an image set acquired by a Thematic Mapper scanner are presented. A substantial improvement is obtained over prior vector quantization based coders for multispectral data compression.

A block matching algorithm is presented for joint motion compensated prediction and interpolation that significantly reduces the side-information required to represent the motion vectors (MVs) in video coding compared to a method in which prediction and interpolation MVS are transmitted independently as recommended in the current MPEG standard. This is achieved by exploiting the temporal redundancy in MVs of nearby frames. A distortion measure which jointly evaluates the interpolation and prediction error energy is introduced to determine true MVs. Enhancements to the basic algorithm are provided to accommodate blocks whose motion across multiple frames is not correlated. Simulation results demonstrate that the resultant method provides essentially the same performance as an MPEG type method even for complex video sequences.>

Several major modifications to the phonetically segmented vector excitation coding (PS-VXC) coder by the authors (1989, 1990) reported previously have resulted in enhanced speech quality while reducing the delay, complexity, and bit rate. Speech is segmented into variable-length phonetic classes and a VXC coding module is tailored to each class. Coding techniques include adaptive linear predictive coding (LPC) analysis and interpolation, two-stage excitation coding of onsets, comb filtering, modified perceptual weighting, and pitch contour smoothing. The improved PS-VXC coder operates at a peak rate of 3.4 kb/s with an average rate of 3.0 kb/s and has a subjective performance closely matching that of the 4.8 kb/s DoD CELP coder.>

The authors present a novel version of low-delay vector excitation coding (LD-VXC) operating at 8 kb/s that provides very good speech quality with a coding delay below that of the CCITT requirement. The coder integrates techniques such as vector quantization and analysis-by-synthesis, without any excessive buffering of speech samples in the encoder, by incorporating backward adaptive linear prediction. Compared with LD-VXC at 16 kb/s which was reported earlier, this version features an increased vector dimension, closed-loop pitch prediction with a three-tap pitch filter, codebook orthogonalization techniques, and dual-mode interframe coding of the pitch trajectory. Informal listening tests demonstrate that its quality is comparable to that of VSELP operating at the same rate, while maintaining a delay constraint an order of magnitude smaller than that of VSELP.>

A perceptually motivated objective measure for evaluating speech quality is presented. The measure, computed from the original and coded versions of an utterance, exhibits statistically a monotonic relationship with the mean opinion score, a widely used criterion for speech coder assessment. For each 10-ms segment of an utterance, a weighted spectral vector is computed via 15 critical band filters for telephone bandwidth speech. The overall distortion, called Bark spectral distortion (BSD), is the average squared Euclidean distance between spectral vectors of the original and coded utterances. The BSD takes into account auditory frequency warping, critical band integration, amplitude sensitivity variations with frequency, and subjective loudness.>

Multistage vector quantization (MSVQ) can achieve very low encoding and storage complexity in comparison to unstructured vector quantization. However, the conventional stage-by-stage design of the codebooks in MSVQ is suboptimal with respect to the overall performance measure. The authors introduce an algorithm for the joint design of the stage codebooks to optimize the overall performance. The performance improvement, although modest, is achieved with no effect on encoding or storage complexity and only a slight increase in design effort.>

The need for a 16-kb/s speech coding algorithm that has very low coding delay while achieving essentially the same high quality as the 32-kb/s adaptive differential pulse code modulation (ADPCM) standard G.721 is addressed. The authors describe low-delay vector excitation coding (LD-VXC), a new coding algorithm which provides high quality with less than 2 ms of coding delay and is robust to transmission errors. The algorithm combines techniques such as vector quantization, analysis-by-synthesis, and perceptual weighting together with backward adaptive linear predictive encoding, and uses a novel long-term predictor employing backward adaptive pitch tracking. Perceptually based nose shaping and postfiltering contribute to the masking of audible quantization noise.>

Transform coding, a simple yet efficient image coding technique, has been adopted by the Joint Photographic Experts Group (JPEG) as the basis for an emerging coding standard for compression of still images. However, for any given transform encoder, the conventional inverse transform decoder is suboptimal. Better performance can be obtained by a nonlinear interpolative decoder that performs table lookups to reconstruct the image blocks from the code indexes. Each received code index of an image block addresses a particular codebook to fetch a component vector. The image block can be reconstructed as the sum of the component vectors for that block. An iterative algorithm for designing a set of locally optimal codebooks is developed. Computer simulation results demonstrate that this improved decoding technique can be applied in the JPEG baseline system to decode enhanced quality pictures from the bit stream generated by the standard encoding scheme.>

A compression method for multispectral data sets is proposed where a small subset of image bands is initially vector quantized. The remaining bands are predicted from the quantized images. Two different types of predictors are examined, an affine predictor and a new nonlinear predictor. The residual (error) images are encoded at a second stage based on the magnitude of the errors. This scheme simultaneously exploits both spatial and spectral correlation inherent in multispectral images. Simulation results on an image set from the Thematic Mapper with seven spectral bands provide a comparison of the affine predictor with the nonlinear predictor. It is shown that the nonlinear predictor provides significantly improved performance compared to the affine predictor. Image compression ratios between 15 and 25 are achieved with remarkably good image quality.>

The concept and design methods for efficient use of vector quantization (VQ) in high-fidelity audio coding are presented. It is demonstrated that with constrained-storage VQ (CSVQ), tree-structured codebooks can be constructed for very high rates without incurring an exponential growth in storage complexity and without impairing the rate-distortion performance. Nonlinear interpolative VQ allows efficient coding of the power envelope needed for transform-coefficient normalization and adaptive distortion assignment. These techniques lead to a substantial reduction in the overall bit rate and codebook storage for the audio coder.>

A novel perceptually motivated objective measure for estimating the subjective quality of coded speech is presented. It takes into account auditory frequency warping (Bark transformation), critical-band integration, amplitude sensitivity variations with frequency, and conversion from loudness level to loudness. For each 10 ms segment of an utterance, a weighted spectral vector is computed via 15 critical band filters. The overall distortion, called Bark spectral distortion (BSD), is the average squared Euclidean distance between spectral vectors of the original and coded utterance. In tests with speech distorted by a modulated noise reference unit or coded at rates of 2.4-64 kb/s, the measure predicted mean opinion score (MOS) ratings are notably better than segmental SNR. The standard error in estimating MOS scores with the new measure was 0.2-0.3.>

A technique for designing vector quantizers that is well suited for parallel processing environments is presented. The input space is iteratively partitioned into M disjoint connected regions composed of unions of partition regions. Each of M processors then independently commutes an optimal subquantizer for its restricted input space. The partitions can regularly be changed to further improve the overall quantizer performance. This technique can improve on the performance of the generalized Lloyd algorithm by following the traditional design process with the subpartitioning iterations.>

A codebook sharing technique, called constrained storage vector quantization (CSVQ), is introduced. This technique offers a convenient and optimal way of trading off performance against storage. The technique can be used in conjunction with tree-structured vector quantization (VQ) and other structured VQ techniques that alleviate the search complexity obstacle. The effectiveness of CSVQ is illustrated for coding transform coefficients of audio signals with multistage VQ.>

An image coding algorithm for digital video tape recorders (DVTR) must satisfy several requirements which do not arise in other applications of video compression. A key constraint on the data format is satisfied if every frame (or field) of video is partitioned into a small number of subimages, each independently coded with a fixed number of bits. This requirement excludes the use of interframe coding and most variable-rate image coding algorithms. We propose to use a new algorithm that codes a subimage efficiently under this data format constraint and allows virtually lossless reproduction at reasonable low bit rates. Each subimage is partitioned into non-overlapping blocks and each block is coded by one of a finite set of predesigned block quantizers covering a range of bit rates. For the ith block in the subimage, a rate function Ri(Li) and a distortion function Di(Li) is tabulated for each block quantizer Li. A near-optimal quantizer allocation algorithm based on the Lagrange Multiplier method is used to select a particular quantizer for each block. The objective is to minimize the distortion of the entire subimage under the constraint on the total number of bits for the subimage. A system for the compression of HDTV for DVTR's based on this rate-constrained optimal block-adaptive technique is designed using the DCT and vector quantization with a multistage structure. Simulation results demonstrate that this algorithm has the potential of achieving virtually lossless compression for digital tape recording of HDTV.

Multi-stage tree-structured vector quantization (MSTVQ) is examined as an alternative to entropy constrained scalar quantization (ECSQ) in transform coding of high fidelity audio signals with a simultaneous masking model for distortion control. Discrete-cosine-transform coefficients are normalized by an interpolated spectral power envelope and groups of adjacent coefficients are vector coded with variable rate to achieve distortion-masking. With the current coder configuration, high fidelity quality for a sampling rate of 32 kHz is achievable with data rates below 64 kbps for some transform and masking model, preliminary results show that MSTVO and ECSQ have a similar rate-distortion performance.>

A technique for efficient vector quantization (VQ) design based on conjugate-gradient search methods is introduced. It is demonstrated experimentally that the new design algorithm performs better than the generalized Lloyd algorithm in many cases in terms of computation time and/or quality of the codebook it produces.>

It is shown that neural network architectures may offer a valuable alternative to the Bayesian classifier. With neural networks, the a posteriori probabilities are computed with no a priori assumptions about the probability distribution functions (PDFs) that generate the data. Rather than assuming certain types of PDFs for the input data, the neural classifier uses a general type of input-output mapping which is then designed to optimally comply with a given set of examples called the training set. It is demonstrated that the a posteriori class probabilities can be efficiently computed by a deterministic feedforward network which is called the Boltzmann perceptron classifier (BPC). Maximum a posteriori (MAP) classifiers are also constructed as a special case of the BPC. Structural relationships between the BPC and a conventional multilayer perceptron (MLP) are given, and it is demonstrated that rather intricate boundaries between classes can be formed even with a relatively modest number of network units. Simulation results show that the BPC is comparable in performance to a Bayesian classifier.>

A process by which a reduced-dimensionality feature vector can be extracted from a high-dimensionality signal vector and then vector quantized with lower complexity than direct quantization of the signal vector is discussed. In this procedure, a receiver must estimate, or interpolate, the signal vector from the quantized features. The task of recovering a high-dimensional signal vector from a reduced-dimensionality feature vector can be viewed as a generalized form of interpolation or prediction. A way in which optimal nonlinear interpolation can be achieved with negligible complexity, eliminating the need for ad hoc linear or nonlinear interpolation techniques, is presented. The range of applicability of nonlinear interpolative vector quantization is illustrated with examples in which optimal nonlinear estimation from quantized data is needed for efficient signal compression.>

A pseudo-Gray code is an assignment of n-bit binary indexes to 2" points in a Euclidean space so that the Hamming distance between two points corresponds closely to the Euclidean distance. Pseudo-Gray coding provides a redundancy-free error protection scheme for vector quantization (VQ) of analog signals when the binary indexes are used as channel symbols on a discrete memoryless channel and the points are signal codevectors. Binary indexes are assigned to codevectors in a way that reduces the average quantization distortion introduced in the reproduced source vectors when a transmitted index is corrupted by channel noise. A globally optimal solution to this problem is generally intractable due to an inherently large computational complexity. A locally optimal solution, the binary switching algorithm, is introduced, based on the objective of minimizing a useful upper bound on the average system distortion. The algorithm yields a significant reduction in average distortion, and converges in reasonable running times. The sue of pseudo-Gray coding is motivated by the increasing need for low-bit-rate VQ-based encoding systems that operate on noisy channels, such as in mobile radio speech communications.>

An adaptive image coding scheme, called classified transform vector quantization, is proposed. It efficiently exploits correlation in large image blocks by taking advantage of transform coding (TC) and vector quantization (VQ), while overcoming the suboptimalities of TC and avoiding the complexity obstacle of VQ. After local mean luminance values are removed in the spatial domain using two-stage interpolative VQ, the residual errors are encoded in the transform domain by means of perceptual block classification and adaptive subvector construction. This scheme avoids the use of scalar quantization of DC coefficients in the transform domain and yet substantially reduces the blocking effect that tends to arise at low bit rates. Good reconstructed images have been obtained at rates between 0.3 and 0.4 bits/pixel, depending on the nature of the test images. The technique also permits progressive image transmission and reproduces errorless images with compression of about 5.0 bits/pixel. Experimental results indicate that an efficient bit allocation in the coding process produces a substantial improvement in performance.>

A phonetically based segmentation of speech is performed to classify segments into five classes: onset, unvoiced low-pass voiced, steady-state voiced, and transient voiced. The segment lengths are constrained to an integer multiple of a unit-frame. For each segment class, a distinctive coding scheme based on vector excitation coding (VXC) is used. The maximum bit-rate is 3.6 kb/s, and a moderate coding delay of 45 ms is incurred. Performance is roughly comparable to conventional VXC/CELP (code-excited linear prediction) coding at 4.8 kb/s.>

A study of the combination of VSC (vector excitation coding) with subband coding is reported. In subband VXC (SBVXC), the burden of redundancy removal is split between the frequency domain and time domain to take advantage of both predictive coding and subband coding techniques. The conventional adaptive bit-allocation method used in subband coding has been generalized for use in SBVXC. Simulated comparisons of several coding schemes, including one comparing SBVXC with the full-band VXC, are presented. Results show that a two-band version of SBVXC can produce fairly clear, intelligible, and natural-sounding synthetic speech at 4.8 kb/s and very high quality speech at 8 kb/s with a reasonable complexity.>

A hardware subsystem is described which, in conjunction with an IBM PC, facilitates the development of various types of vector-quantization (VQ)-based speech coders and also serves as a powerful general-purpose DSP (digital-signal-processor) development system. Each iteration of the usual VQ codebook-design algorithm can be performed by playing, in real-time, an analog cassette tape of recorded speech into the hardware. The hardware is based on the TMS320C25 processor and a semicustom VLSI coprocessor used for VQ codebook searching. The architecture of the system is described and some of the most useful applications that it supports are outlined.>

An approach to vector-excitation-coding (VXC) speech compression utilizing multiple-stage vector quantization (VQ) is considered. Called multiple-stage VXC (MSVXC), this technique facilitates the use of high-dimensional excitation vectors at medium-band rates without substantially increasing computation. The basic approach consists of successively approximating the input speech vector in several cascaded VQ stages, where the input vector for each stage is the quantization error vector from the preceding stage. It is shown that if a number of VQ stages is increased sufficiently, MSVXC can be expressed as a form of transform coding, in which the computationally intensive excitation codebook search is completely eliminated.>

A hierarchical approach to encoding of images using vector quantization (VQ) is described which allows VQ of large blocks with a tolerable computational complexity and permits progressive image reconstruction at bit rates as low as 0.3 bit/pixel. The technique used, multi-stage hierarchical VQ (MSHVQ), is a successive approximation approach for quantization that is based on recursive decomposition of larger image blocks into smaller subblocks. The encoder of MSHVQ consists of several stages, each of which encodes the quantization error generated from the previous stage. Digital decimation and interpolation techniques are used to convert between different vector dimensions in the higher level stages and to reduce the otherwise highly noticeable blocking effect in the reconstructed image. Variable-rate encoding increases the compression efficiency by allocating greater resolution to high-detail regions and provides a perceptually more consistent image quality throughout all areas of the decoded image. Experimental results show that MSHVQ yields a significantly improved image quality over conventional VQ of equivalent complexity.>

The application of simulated annealing to the design of a codebook for a vector quantizer (VQ) that is used to code images are studied. The traditional method for VQ codebook design is to use the generalized Lloyd algorithm (GLA), an iterative optimization procedure where an initial codebook is continually refined so that each iteration reduces the distortion involved in coding a given training set. However, this algorithm easily gets trapped in local minima of the distortion, resulting in a suboptimal codebook. Simulated annealing is a procedure that uses randomness in a search algorithm and tends to skirt relatively poor local minima in favor of better ones. The mean-squared-error (MSE) is used as the distortion measure during the design, and coded images are evaluated both subjectively and in terms of the peak-signal-to-noise ratio.>

An efficient, low-complexity method called switched-adaptive interframe vector prediction (SIVP) has been developed for linear predictive coding (LPC) of spectral parameters in the development of low-bit-rate speech coding systems. SIVP utilizes vector linear prediction to exploit the high frame-to-frame redundancy present in the successive frames of LPC parameters. When SIVP is combined with scalar quantization, it has been found that the LPC parameter bit rate required to achieve high-quality synthetic speech is only 1300 b/s. With vector quantization, the bit-rate can be reduced even further (to 1000 b/s) without introducing any perceivable quantization noise in the reconstructed speech.>

A novel least-squares formulation of the vector linear prediction (VLP) problem is presented. Based on this formulation, we develop two new design methods for obtaining the optimal vector predictor for frame-adaptive prediction: the covariance method and the autocorrelation method, which bear the names of the corresponding methods in scalar LPC analysis. Our formulation reveals several previously unrecognized properties of the resulting normal equation. Simulation results for VLP of speech waveforms confirm that the two proposed methods indeed give higher prediction gain than previously developed methods.

An improved Vector APC (VAPC) speech coder at 4800 bps produces speech with very good communications quality while maintaining a complexity low enough to allow a real-time implementation with at most two commercially available DSP chips. The VAPC algorithm combines APC with vector quantization and incorporates analysis-by-synthesis, perceptual noise weighting, and adaptive postfiltering. A novel adaptive postfiltering technique helps to achieve an essentially inaudible level of coding noise. Real-time software has been developed for an implementation using the AT&T DSP32 floating-point processor chip. The overall complexity of the implemented VAPC system is about 3 million multiply-adds/second of computation and 6 kwords of memory.

In Vector Excitation Coding (VXC), speech is represented by applying a sequence of excitation vectors to a time-varying speech production filter with each vector chosen from a codebook using a perceptually-based performance measure. Although VXC is a powerful technique for achieving natural and high quality speech compression at low bit-rates, it suffers as other excitation coders do from a very high computational complexity. Recent research has shown that codebook search computation can be reduced to approximately 40 MFlops without compromising speech quality. However, this operation count still prohibits a practical real-time implementation of the coder using today's DSP chips. We present a real-time 4.8 kb/s Pulse Excitation VXC coder (PVXC) which achieves high reconstructed speech quality and incorporates new techniques which reduce the codebook search complexity to only 0.55 MFlops. The coder utilizes an optimized excitation codebook and a promising new interframe vector predictive LPC parameter quantization scheme. A preliminary implementation using a single floating-point signal processor is described.

Current algorithms for the efficient coding of images generally employ one of two techniques: Vector Quantization or Transform Coding. Both of these methods are based on block coding, and the traditional algorithms require the partitioning of the original image into a number of, usually square, regions of uniform size. This paper explores techniques where the size of these regions, or blocks, is varied according to the local detail of the image. By isolating regions of differing detail, using a quad-tree based segmentation algorithm to control the size of the blocks, the low detail areas can be encoded at substantially lower rates than is otherwise possible. Satisfactory quality coding results are achieved at rates between 0.35 and 0.4 bpp; the actual rate depends on the image being encoded.

The generalization of gain adaptation to vector quantization (VQ) is explored in this paper and a comprehensive examination of alternative techniques is presented. We introduce a class of adaptive vector quantizers that can dynamically adjust the "gain" or amplitude scale of code vectors according to the input signal level. The encoder uses a gain estimator to determine a suitable normalization of each input vector prior to VQ encoding. The normalized vectors have reduced dynamic range and can then be more efficiently coded. At the receiver, the VQ decoder output is multiplied by the estimated gain. Both forward and backward adaptation are considered and several different gain estimators are compared and evaluated. Gain-adaptive VQ can be used alone for "vector PCM" coding (i.e., direct waveform VQ) or as a building block in other vector coding schemes. The design algorithm for generating the appropriate gain-normalized VQ codebook is introduced. When applied to speech coding, gain-adaptive VQ achieves significant performance improvement over fixed VQ with a negligible increase in complexity.

Direct space-domain image coding with Vector Quantization (VQ) has been very effective in the range 0.6 to 1.5 bpp. To achieve quality at lower rates, it is necessary to exploit spatial redundancy over a larger region of pixels than is possible with memoryless VQ. One way to do this is to incorporate memory into a VQ-based coder. A finite-state vector quantizer (FSVQ) employs a state variable which summarizes the past to select one of a family of codebooks to encode each vector. As a result, an FSVQ can achieve the same performance as memoryless VQ at lower rates. In this paper we extend the FSVQ technique to image coding, introducing a novel formulation of the state and state-transition rule using a perceptually-based image classifier. A new distortion measure is proposed for image VQ, which appears to be perceptually more effective than the usual MSE-criterion and leads to a modified LBG design algorithm to obtain codebooks which result in improved edge integrity. At 0.375 bpp, the resulting FSVQ coder achieves performance comparable to earlier memoryless VQs at 0.7 bpp.

The architecture and implementation of a novel VLSI bit-level systolic Vector Quantization processor is described. This architecture offers very high data throughput for real-time processing applications. Given a codebook of sizeNand dimensionk, an input vector can be quantized everyNclock cycles, compared to O(kN) cycles for a Single-Instruction, Single-Data (SISD) machine. Any distortion measure which can be expressed as a Euclidean vector inner product can be computed with this array.

We have developed a new speech coder which significantly enhances Adaptive Predictive Coding (APC) by using vector quantization. The coder, called Vector APC (VAPC), gives very good speech quality at 9.6 kb/s and reasonably good quality at 4.8 kb/s. In VAPC, redundancy is first removed by a long-delay predictor and then by a short-delay predictor; the prediction residual is then quantized by a gain-adaptive vector quantizer. In the receiver, decoded residual vectors are used to excite a synthesis filter to obtain the coded speech. The computations required by VAPC are only in the order of 2 to 4 million flops per second. Because of its low complexity and high speech quality, VAPC may offer a low-complexity alternative to Code-Excited Linear Prediction (CELP) at low bit rates.

A critical issue in the use of Vector Quantization is to circumvent the complexity bottleneck that prevents the full power of this data compression technique from being exploited. The demanding exhaustive codebook search can be avoided by more efficient algorithms for locating the nearest codevector in a codebook to a given input vector. This paper introduces a fast nearest neighbor search algorithm, the Binary Hyperplane Testing (BHT) algorithm, for fast codebook searching when least Euclidean distance is the appropriate distortion or dissimilarity measure. LetNdenote the size of a codebook, andkdenote the dimension of a vector. The search complexity of the BHT algorithm increases linearly with the resolutionr = (\log_{2}N)/kfor fixed dimensionk. The search complexity of the BHT algorithm is sufficiently low that it has been used to implement a real-time speech waveform vector quantizer with sampling rate 8 KHz, dimensionk = 4, and codebook sizeN = 128using a single programmable signal processor, the TMS32010.

Vector Excitation Coding (VXC) is based on a new and general source-filter modeling technique in which the excitation signal for a speech production model is encoded at very low bit-rates using vector quantization. Various speech coder structures which fall into this class have recently been shown to reproduce speech with very high perceptual quality. The primary drawback of VXC is the large amount of computation required in the process of selecting an optimal excitation signal. We present several schemes in this paper which substantially reduce search computation in VXC coders while retaining their remarkably high reconstructed speech quality.

A conceptually new approach for describing the excitation signal in multipulse-excited LPC has been developed. The information needed to determine the excitation for each frame is transmitted to the receiver in the form of a crosscorrelation function. With the help of the LPC filter parameters, the receiver computes the excitation pulse sequence needed to generate the reconstructed speech waveform. Both the crosscorrelation function and the set of LPC parameters are coded by vector quantization. We utilize a classified codebook assignment technique in VQ for the crosscorrelation. This paper describes the coder structure, the use of vector quantization, and the results of computer simulation studies.

The major obstacle which has limited the use of Vector Quantization (VQ) for real-time speech coding is the computationally demanding codebook-search algorithm. The essential task of this algorithm, pattern matching, has several properties which make it amenable to VLSI realization using a highly concurrent processor architecture. A VLSI pattern-matching chip provides the essential building-block for a specialpurpose codebook-search processor (CSP). The CSP can serve as a generic architecture for a variety of VQ-based speech coding applications. This paper reports on a working VQ processor for speech coding based on a first generation VLSI chip that efficiently performs the essential pattern-matching operation needed for the codebook-search process. Furthermore, the CSP architecture, using this chip, has been successfully incorporated into a compact single-board Vector PCM implementation which operates at rates between 7 and 18 kbits/s. A real-time Adaptive Vector Predictive Coder system using the CSP and augmented by a TMS-32010 programmable signal processor has been designed and recently implemented. We describe the structure of these two VQ coders and present experimental results obtained using the single-board Vector PCM coder.

Vector quantization (VQ) provides many attractive features for image coding with high compression ratios. However, initial studies of image coding with VQ have revealed several difficulties, most notably edge degradation and high computational complexity. We address these two problems and propose a new coding method, classified vector quantization (CVQ), which is based on a composite source model. Blocks with distinct perceptual features, such as edges, are generated from different subsources, i.e., belong to different classes. In CVQ, a classifier determines the class for each block, and the block is then coded with a vector quantizer designed specifically for that class. We obtain better perceptual quality with significantly lower complexity with CVQ when compared to ordinary VQ. We demonstrate with CVQ visual quality which is comparable to that produced by existing coders of similar complexity, for rates in the range 0.6-1.0 bits/pixel.

Vector Quantization is an attractive block coding scheme which allows more efficient use of a given channel capacity. The computational complexity of the codebook search, however, limits the practical applications of Vector Quantization -- especially in real-time situations. This paper presents a special purpose processing architecture which supports real-time search of large codebooks. The core of the computation required for a squared-error distortion measure is accomplished using a VLSI pattern matching chip. We describe a pipeline architecture which reduces the effective computation time for a single vector component to one period. The chip supports a selectable vector dimension of 2, 4, 8, or 8 and can be used with any codebook size consistent with the input vector rate and the chip's throughput. We have built and tested a 4-micron NMOS chip which supports up to four million squared-error distance calculations per second. We outline three approaches to real-time Vector quantization which use this chip to do the pattern matching: two waveform coding processors using Vector Pulse Code Modulation and Adaptive Vector Predictive Coding, and a novel approach to rapid codebook design.

This paper presents a new class of adaptive vector quantizers in which a codebook is gradually changed to track time-varying source statistics by dynamically updating some of the codevectors. The partial distortion of a codevector, defined as the product of the average distortion when a particular codevector is selected and the probability that selection occurs, is used as a measure to determine which codevectors are updated. Codevectors with small partial distortion are deleted from the codebook, and those with large partial distortion are shifted or split so that the input vectors that are mapped into those codevectors are quantized more finely to give smaller partial distortions. Experimental results illustrate the application of this adaptive vector quantizer to image coding.

Traditional solutions to the bit allocation problem assume nicely behaved quantizers whose distortion versus rate characteristic is a standard exponentially decreasing function. This model is often inadequate and leads to suboptimal bit allocations for actual quantizer characteristics. This inadequacy prevails particularly in coding systems based on vector quantization (VQ). The distortion-rate characteristic for VQ suffers from irregularities because of suboptimality of the codebook and of the codebook search method. We propose a new algorithm which efficiently allocates a given quota of bits, based on the actually measured quantizer performance, without any prior assumptions on its behavior. The algorithm can enhance the performance-of traditional scalar coders as well as any modern coder which employs dynamic bit allocation.

Vector quantization, in its simplest form, may be regarded as a generalization of PCM (independent quantization of each sample of a waveform) to what might be called "vector PCM," where a block of consecutive samples, a vector, is simultaneously quantized as one unit. In theory, a performance arbitrarily close to the ultimate rate-distortion limit is achievable with waveform vector quantization if the dimension of the vector,k, is large enough. The main obstacle in effectively using vector quantization is complexity. A vector quantizer of dimensionkoperating at a rate ofrbits/sample requires a number of computations on the order ofk2^{kr}and a memory of the same order. However, a low-dimensional vector quantizer (dimensions 4-8) achieves a remarkable improvement over scalar quantization (PCM). Consequently, using the vector quantizer as a building block and imbedding it with other waveform data compression techniques may lead to the development of a new and powerful class of waveform coding systems. This paper proposes and analyzes a waveform coding system, adaptive vector predictive coding (AVPC), in which a low-dimensionality vector quantizer is used in an adaptive predictive coding scheme. In the encoding process, a locally generated prediction of the current input vector is subtracted from the current vector, and the resulting error vector is coded by a vector quantizer. Each frame consisting of many vectors is classified into one ofmstatistical types. This classification determines which one ofmfixed predictors and ofmvector quantizers will be used for encoding the current frame.

A fundamental computational task that arises in several areas of signal processing is pattern matching, where a given test pattern is compared with a large set of stored templates, to find the best match that minimizes a given measure of dissimilarity. Three different geometrically-oriented methods are proposed for substantially reducing the computational complexity of the search process by reducing the number of multiplies in exchange for additional low complexity operations and, in two of the methods, additional memory for storing precomputed tables.

Vector quantization (VQ) is examined as a technique to enhance performance in subband coding of speech at 9.6 kb/s. The set of short-term subband power levels is vector quantized, providing low-rate side information to control the coding of the subband signals. Each subband signal is then vector quantized with variable size codebooks that are dynamically assigned by the quantized side information. Two versions are described, a 7-band coder and a 14-band coder. Simulation results demonstrate that vector quantization offers a distinct perceptual improvement compared with scalar quantization of the same subband signals and side information for the same total bit rate.

This paper introduces a Hierarchical Vector Quantization (HVQ) scheme that can operate on "supervectors" of dimensionality in the hundreds of samples. HVQ is based on a tree-structured decomposition of the original super-vector into a large number of low dimensional vectors. The supervector is partitioned into subvectors, the subvectors into minivectors and so on. The "glue" that links subvectors at one level to the parent vector at the next higher level is a feature vector that characterizes the correlation pattern of the parent vector and controls the quantization of lower level feature vectors and ultimately of the final descendant data vectors. Each component of a feature vector is a scalar parameter that partially describes a corresponding subvector. The paper presents a three level HVQ for which the feature vectors are based on subvector energies. Gain normalization and dynamic codebook allocation are used in coding both feature vectors and the final data subvectors. Simulation results demonstrate the effectiveness of HVQ for speech waveform coding at 9.6 and 16 Kb/s.

Vector quantization (VQ) has made it possible to utilize perceptually meaningful techniques for direct space-domain image coding. A simple 2 or 3 way classified codebook approach [2,3] allocates the perceptually important edges with more resolution than the easily encoded monotone regions of an image. In this paper, we introduce a major extension of the classification approach to include edge orientation and location, thereby exploiting an important feature of the human visual mechanism. In particular, each 4 × 4 block of pixels is classified into one of 31 classes for the case of 16 dimensional VQ. The encoding and codebook design complexity is significantly reduced, allowing us to use large codebooks designed from a large database of training images. We present images encoded at 0.7 and 0.8 bits per pixel using this scheme with 16- dimensional vectors. Only a small fraction of one bit per pixel is needed to code the monotone regions of an image; the rest of the bitrate is used to achieve a high level of edge integrity.

An important application of spatial filtering techniques is in the post-processing-of images degraded by coding. Linear post-processing methods are inadequate to reduce the degradations in block-coded images. In this paper, a new nonlinear, space-variant filtering algorithm is proposed, which sharpens jagged edges without blurring them, and smoothes out small abrupt changes in the grey-level in monotone areas. It is not much more complex to implement than simple linear filtering. We show that this kind of post-processing significantly reduces the subjective effects of quantization noise in decoded images with almost no degradation of the signal.

Two related cancellation techniques based on "tentative" decisions are proposed for removing intersymbol interference, due to channel nonlinearities, for voiceband data transmission. Cancellation of intersymbol interference avoids the need for equalizing or "inverting" analog nonlinear operations as in the decision-feedback method previously proposed by Falconer. The nonlinear cancellation approach removes nonlinear interference terms without excessive noise enhancement and allows effective implementation with ROM's to generate the needed nonlinear signal variables that are to be weighted and summed. The first technique can be incorporated as an "add-on" unit to a present-day modem; the second technique requires a different receiver architecture but offers somewhat enhanced improvement. Simulation results for 9.6 kbit/s data transmission over nonlinear channel models show that both techniques can offer substantial performance improvements for 16-point QAM systems.

Any scheme that encrypts an analog message with perfect secrecy using a finite-size digital key must inevitably degrade the quality of the recovered message. With the constraints of perfect secrecy and a finite key size, no analog encryption system can ever achieve less degradation than is achievable by optimal digitization of the message (by block source coding or vector quantization) followed by digital encryption. Optimal analog encryption with perfect secrecy can be implemented in such a way that the bandwidth of the encrypted signal is not greater than the bandwidth of the original analog signal; this can be done without altering the key size and without increasing the degradation incurred in the recovered message.

High-speed modems typically employ quadrature amplitude modulation (QAM) so that two signal paths, in-phase and quadrature, are simultaneously being used. The standard receiver structure has, in effect, four adaptive equalizers, one for each of the two signal paths and two to correct for cross coupling between signal paths. As a result, equalization normally requires8Nmultiplications per baud interval, whereNis the number of taps, to perform the needed signal processing including adaptive updating of the weights., In this correspondence, we present a new signal processing algorithm which requires only6Nmultiplications per baud interval. For fractionally spaced equalization and adaptive cancellation,Nis quite large so that this saving can be of practical value in improwng throughput capability of custom chips, or depending on the architecture, with programmable signal processor chips. Specifically, the algorithm is advantageous for implementations where multiplications require a longer execution time than additions.

A significant improvement in noise immunity can be achieved for digital transmission over band-limited channels by the use of multidimensional signal constellations. Conventional 16-point QAM signaling, such as that used in many digital transmission systems, is a two-dimensional modulation scheme where in each signaling interval a group ofNbits is used to determine the amplitudes of the in-phase and quadrature dimension or coordinate, i.e.,N/2bits are conveyed per dimension. In a2M-dimensional QAM system, a group ofMNbits is used to determine the in-phase and quadrature ampllitudes forMconsecutive, symbol intervals whereN/2bits are still conveyed by each dimension. It is the purpose of this paper to describe the basic theory and implementation for a particular 2 bits/dimension four-dimensional (two-symbol interval) encoding which readily lends itself to simple encoding and decoding. For this encoding, theory predicts a 1.2 dB gain in noise margin over conventional 16-point (two-dimensional) QAM signaling. Experimental results agreed with the theoretical predictions, and have demonstrated an order of magnitude reduction in block error rate. Extension to eight-dimensional signaling offers a theoretical gain of 2.4 dB over conventional 16-point QAM.

Recently there has been increased interest in high speed adaptive filtering where the usual stochastic gradient or least mean-square (LMS) algorithm is replaced with the simpler algorithm where adaptation is guided only by the polarity of the error signal. In this paper the convergence of this binary reinforcement (BR) algorithm is proved under the usual independence assumption, and the surprising observation is made that, unlike the LMS algorithm, convergence occurs for any positive value of the step-size parameter. While the stochastic gradient algorithm attempts to minimize a mean-square error cost function, the binary reinforcement algorithm in fact attempts to minimize a mean-absolute error cost function. It is proved for the binary reinforcement algorithm that the tap weight vector converges in distribution to a random vector that is suitably concentrated about the optimal value based on a least mean-absolute error cost function. For a sufficiently small step size, the expected cost of the asymptotic weight vector can be made as close as desired to thc minimum cost attain,ed by the optimum weight vector.

An image is partitioned into cells of pxp pixels. Each cell is regarded as a vector of dimension p2and is encoded by searching through a codebook for a nearest matching representative vector. A binary word identifying the selected representative vector is assigned as the codeword to describe the original cell. The decoder uses this codeword to address a codebook. Each entry of the codebook contains a full precision digital representation of one of the N representative vectors. The codebook design is based on a clustering technique for vector quantizer design preceded by a classification of training cells into edge or shade cells. Results for coding rates from 0.5 to 1.5 bits/pixel are discussed. Vector quantization appears to be a powerful and promising technique for image coding.

Vector quantization is intrinsically superior to predictive coding, transform coding, and other suboptimal and {\em ad hoc} procedures since it achieves optimal rate distortion performance subject only to a constraint on memory or block length of the observable signal segment being encoded. The key limitation of existing techniques is the very large randomly generated code books which must be stored, and the computational complexity of the associated encoding procedures. The quantization operation is decomposed into its rudimentary structural components. This leads to a simple and elegant approach to derive analytical properties of optimal quantizers. Some useful properties of quantizers and algorithmic approaches are given, which are relevant to the complexity of both storage and processing in the encoding operation. Highly disordered quantizers, which have been designed using a clustering algorithm, are considered. Finally, lattice quantizers are examined which circumvent the need for a code book by using a highly structured code based on lattices. The code vectors are algorithmically generated in a simple manner rather than stored in a code book, and fast algorithms perform the encoding algorithm with negligible complexity.

Coefficient inaccuracy in FIR filters is known to degrade the frequency response particularly in stopband regions. The magnitude of the stopband degradation increases with the number of stages N, the length of the impulse response. A widely used formula for the error in frequency response is proportional to\sqrt{N}. Recently, we have found that for random additive coefficient errors with variance σ2, the maximum error in frequency response for large N is given by\sigma\sqrt{N\logN}. This result is applied to an empirical formula relating the minimum number of stages, N, to specified lowpass filter performance parameters. The results lead to absolute bounds on attainable stopband rejection for band-select FIR filters. The realization of transversal filters with charge-coupled devices (CCD's) is particularly relevant to this study.

In 1948 W. R. Bennett used a companding model for nonuniform quantization and proposed the formulaD \: = \: \frac{1}{12N^{2}} \: \int \: p(x) [ É(x) ]^{-2} \dxfor the mean-square quantizing error whereNis the number of levels,p(x) is the probability density of the input, andE \prime(x) is the slope of the compressor curve. The formula, an approximation based on the assumption that the number of levels is large and overload distortion is negligible, is a useful tool for analytical studies of quantization. This paper gives a heuristic argument generalizing Bennett's formula to block quantization where a vector of random variables is quantized. The approach is again based on the asymptotic situation whereN, the number of quantized output vectors, is very large. Using the resulting heuristic formula, an optimization is performed leading to an expression for the minimum quantizing noise attainable for any block quantizer of a given block sizek. The results are consistent with Zador's results and specialize to known results for the one- and two-dimensional cases and for the case of infinite block length(k \rightarrow \infty). The same heuristic approach also gives an alternate derivation of a bound of Elias for multidimensional quantization. Our approach leads to a rigorous method for obtaining upper bounds on the minimum distortion for block quantizers. In particular, fork = 3we give a tight upper bound that may in fact be exact. The idea of representing a block quantizer by a block "compressor" mapping followed with an optimal quantizer for uniformly distributed random vectors is also explored. It is not always possible to represent an optimal quantizer with this block companding model.

The diffusion of an innovation such as a new communication service is modeled using a randomly generated network of interpersonal influence between members of a social system. Each member decides to adopt the innovation when K out of his particular set of L influencers have already become adopters. A discrete-time recursion is obtained which describes the evolution in time of the fraction of adopters. The model exhibits a critical mass effect, where the number of initial adopters must exceed a critical value for the diffusion to saturate the population, otherwise the diffusion ends prematurely without substantial growth. Also exhibited is a bandwagon effect, which explains a sudden upsurge in growth following an initial period of slow diffusion. Both phenomena are amply corroborated by Monte Carlo simulations for a population of 10 000 people.

In an adaptive quantizer that has been used for speech encoding, the entire amplitude range expands or contracts by a multiplicative constant after each input sample. The constant Midepends only on the magnitude of the current quantizer output. Assuming independent identically distributed input samples, we show that the sequence of quantizer ranges is a stochastically stable process. Furthermore, we derive a key design equation,\Sigma p_{i}xlogM_{i} = O, wherep_{i}(x)is the probability that an input sample is in theith magnitude interval when the ratio of quantizer range to rms signal level isx. A designer may specifyxand solve this equation for multipliers that provide the desired steady-state performance. There are many such sets of multipliers and we show that the adaptation time constant associated with each set decreases as the ratio of the largest multiplier to the smallest multiplier is increased. On the other hand, the spread of the steady-state range distribution about the operating point can be made as small as desired by making this ratio sufficiently small. A bound is obtained for the tradeoff between responsiveness to changing input level and steady-state range accuracy.

A quantizer that must accommodate a wide range of signal powers would ordinarily require a large number of output levels compared to a quantizer of signals with known power. In this paper a quantizlng scheme is described for situations in which the signal power is unknown a priori but remains constant for the duration of a communication. The required number of levels is reduced because the quantizer amplitude range is adjusted during an initial training period to the value appropriate to the current signal power. At each sample time during the training period, the amplitude range is adjusted by a multiplicative quantity that depends on the most recent quantized output and upon the time elapsed since the onset of training. Assuming independent identically distributed inputs, it is shown that the quantizer range converges to a fixed multiple of the rms value of the input. The ratio of final range to rms input is a unique function of the multipliers, and a formula is presented that allows a designer to choose multipliers that result in any desired range-to-signal ratio. For each final ratio, there are many sets of multipliers, and formulas are derived that indicate, for a limited training period, the tradeoff between the accuracy of the quantizer range and the size of the set of signal powers to which the quantizer can adapt. Computer simulations illustrate the effects of particular multiplier sequences.