A significant goal of the study of metagenomes obtained from an environment is to find the microbial diversity and the abundance of each organism in the community. Phylotyping and binning methods which address this problem generally operate using either marker sequences or by classifying each genome fragment individually. However, these approaches might not use all the information contained in the metagenome. We propose an approach based on a Multiple Input Multiple Output (MIMO) communication system model. Results from two different implementations of this approach, one using DNA-DNA hybridization simulations and one using short read mapping are evaluated using simulated and actual metagenomes and compared with other methods of phylotyping. The proposed approaches generally performed better under different scenarios including pathogen detection tasks of community complexity and low and high sequencing coverage while being highly computationally effective. The resulting framework can be integrated to metagenome analysis pipelines for phylogenetic diversity estimation. The approach is modular so that techniques other than hybridization simulations and short read mapping may be integrated. We have observed that even for low coverage samples, the method provides accurate estimates. Therefore, the use of the proposed strategy could enable the task of exploring biodiversity with limited resources.

FASTQ is the defacto standard for data from next generation sequencing platforms. The FASTQ format uses four lines per read: two lines for header information, one for the sequence itself, and one for the quality scores. The proposed compression scheme treats the various lines of each four line set differently. The highly repetitive headers are encoded using an LZ77 variant. The reads themselves are compressed using a modified LZ78 method which uses a backward adaptive dictionary. The quality factors are encoded using a context based arithmetic coding scheme. Performance results for the proposed method were obtained using data generated via a sequencing simulation of a random 50kbp section from Escherichia coli str. K-12 substr. DH10B chromosome with 35X and 100X coverages. The two best performing methods for FASTQ compression, Fastqz and Fqzcomp were used to compress the same data. These methods performed the best in a competition to compress next generation sequencing data. We also compare the results to two general purpose compressors bzip and LZMA. The results are shown in Table.

We propose a compression algorithm for the quality scores contained in FASTQ files which are generated in large volumes during high throughput sequencing. The proposed algorithm is a context dependent arithmetic coder which is based on observations of the structure of quality scores in FASTQ files. Simulation results indicate a significantly superior performance of the algorithm to the current state of the art.

BACKGROUND: Computational analysis of metagenomes requires the taxonomical assignment of the genome contigs assembled from DNA reads of environmental samples. Because of the diverse nature of microbiomes, the length of the assemblies obtained can vary between a few hundred bp to a few hundred Kbp. Current taxonomic classification algorithms provide accurate classification for long contigs or for short fragments from organisms that have close relatives with annotated genomes. These are significant limitations for metagenome analysis because of the complexity of microbiomes and the paucity of existing annotated genomes. RESULTS: We propose a robust taxonomic classification method, RAIphy, that uses a novel sequence similarity metric with iterative refinement of taxonomic models and functions effectively without these limitations. We have tested RAIphy with synthetic metagenomics data ranging between 100 bp to 50 Kbp. Within a sequence read range of 100 bp-1000 bp, the sensitivity of RAIphy ranges between 38%-81% outperforming the currently popular composition-based methods for reads in this range. Comparison with computationally more intensive sequence similarity methods shows that RAIphy performs competitively while being significantly faster. The sensitivity-specificity characteristics for relatively longer contigs were compared with the PhyloPythia and TACOA algorithms. RAIphy performs better than these algorithms at varying clade-levels. For an acid mine drainage (AMD) metagenome, RAIphy was able to taxonomically bin the sequence read set more accurately than the currently available methods, Phymm and MEGAN, and more accurately in two out of three tests than the much more computationally intensive method, PhymmBL. CONCLUSIONS: With the introduction of the relative abundance index metric and an iterative classification method, we propose a taxonomic classification algorithm that performs competitively for a large range of DNA contig lengths assembled from metagenome data. Because of its speed, simplicity, and accuracy RAIphy can be successfully used in the binning process for a broad range of metagenomic data obtained from environmental samples.

BACKGROUND: We propose a sequence clustering algorithm and compare the partition quality and execution time of the proposed algorithm with those of a popular existing algorithm. The proposed clustering algorithm uses a grammar-based distance metric to determine partitioning for a set of biological sequences. The algorithm performs clustering in which new sequences are compared with cluster-representative sequences to determine membership. If comparison fails to identify a suitable cluster, a new cluster is created. RESULTS: The performance of the proposed algorithm is validated via comparison to the popular DNA/RNA sequence clustering approach, CD-HIT-EST, and to the recently developed algorithm, UCLUST, using two different sets of 16S rDNA sequences from 2,255 genera. The proposed algorithm maintains a comparable CPU execution time with that of CD-HIT-EST which is much slower than UCLUST, and has successfully generated clusters with higher statistical accuracy than both CD-HIT-EST and UCLUST. The validation results are especially striking for large datasets. CONCLUSIONS: We introduce a fast and accurate clustering algorithm that relies on a grammar-based sequence distance. Its statistical clustering quality is validated by clustering large datasets containing 16S rDNA sequences.

This paper presents the design and measurements of a predictive coding on-sensor compression CMOS imager. Predictive coding is employed to decorrelate the image. The prediction operations are performed in the analog domain to avoid quantization noise and to decrease the area complexity of the circuit. The decorrelated image is encoded with a bank of column-parallel entropy encoders. Each encoder is combined with a single-slope analog-to-digital converter (ADC) to reduce area complexity and power consumption. The area savings resulting from such combination allow to integrate an ADC and an entropy encoder at the column level. A prototype chip was fabricated in a 0.35 μm CMOS process. The output of the chip is a compressed bit stream. The test chip occupies a silicon area of 2.60 mm × 5.96 mm which includes an 80 × 44 APS array. Tests of the fabricated chip demonstrate the validity of the design.

BACKGROUND: Occult organizational structures in DNA sequences may hold the key to understanding functional and evolutionary aspects of the DNA molecule. Such structures can also provide the means for identifying and discriminating organisms using genomic data. Species specific genomic signatures are useful in a variety of contexts such as evolutionary analysis, assembly and classification of genomic sequences from large uncultivated microbial communities and a rapid identification system in health hazard situations. RESULTS: We have analyzed genomic sequences of eukaryotic and prokaryotic chromosomes as well as various subtypes of viruses using an information theoretic framework. We confirm the existence of a species specific average mutual information (AMI) profile. We use these profiles to define a very simple, computationally efficient, alignment free, distance measure that reflects the evolutionary relationships between genomic sequences. We use this distance measure to classify chromosomes according to species of origin, to separate and cluster subtypes of the HIV-1 virus, and classify DNA fragments to species of origin. CONCLUSION: AMI profiles of DNA sequences prove to be species specific and easy to compute. The structure of AMI profiles are conserved, even in short subsequences of a species' genome, rendering a pervasive signature. This signature can be used to classify relatively short DNA fragments to species of origin.

BACKGROUND: We propose a multiple sequence alignment (MSA) algorithm and compare the alignment-quality and execution-time of the proposed algorithm with that of existing algorithms. The proposed progressive alignment algorithm uses a grammar-based distance metric to determine the order in which biological sequences are to be pairwise aligned. The progressive alignment occurs via pairwise aligning new sequences with an ensemble of the sequences previously aligned. RESULTS: The performance of the proposed algorithm is validated via comparison to popular progressive multiple alignment approaches, ClustalW and T-Coffee, and to the more recently developed algorithms MAFFT, MUSCLE, Kalign, and PSAlign using the BAliBASE 3.0 database of amino acid alignment files and a set of longer sequences generated by Rose software. The proposed algorithm has successfully built multiple alignments comparable to other programs with significant improvements in running time. The results are especially striking for large datasets. CONCLUSION: We introduce a computationally efficient progressive alignment algorithm using a grammar based sequence distance particularly useful in aligning large datasets.

In this paper, a new algorithm for lossless compression of hyperspectral images is proposed. The spectral redundancy in hyperspectral images is exploited using a context-match method driven by the correlation between adjacent bands. This method is suitable for hyperspectral images in the band-sequential format. Moreover, this method compares favorably with the recent proposed lossless compression algorithms in terms of compression, with a lower complexity.

We present an adaptive lossless video compression algorithm based on predictive coding. The proposed algorithm exploits temporal, spatial, and spectral redundancies in a backward adaptive fashion with extremely low side information. The computational complexity is further reduced by using a caching strategy. We also study the relationship between the operational domain for the coder (wavelet or spatial) and the amount of temporal and spatial redundancy in the sequence being encoded. Experimental results show that the proposed scheme provides significant improvements in compression efficiencies.

Based on the encoding process, arithmetic codes can be viewed as tree codes and current proposals for decoding arithmetic codes with forbidden symbols belong to sequential decoding algorithms and their variants. However, arithmetic coding can also be modeled as a finite state machine and can be treated as a variable-length trellis code. The number of states used for decoding can be reduced and techniques used for convolutional codes such as the list Viterbi decoding algorithm can be applied on the trellis. The proposed approach provides a rich environment for the design of joint source/channel codes. The particular implementation presented here shows significant performance improvement over previous approaches.

A focal plane video compression integrated circuit is presented. The design consists of a 128 times 128 pixel array and a bank of column-level processors. Each one of the column-level processors performs the tasks of image decorrelation, quantization, and entropy encoding. The chip provides at its output a compressed bit stream. The integration of the quantizer and the entropy encoder at the column level is possible by sharing circuitry between a single-slope analog-to-digital converter and a Golomb-Rice entropy encoder. In addition, the design includes a low-complexity algorithm for the adaptation of the Golomb-Rice coder to the statistics of the video signal. The design has been fully verified through simulations and has been implemented in a 0.35 mum CMOS technology. The chip layout occupies an area of 7 times 5 mm2

Two sets of figures are presnted without discussion. The first show (1a): Average Mutual Information Profile for the Human Chromosomes plotted for values of k between 5 and 50; and b) Average Mutual Information Profile for the Mouse Chromosomes plotted for values of k between 5 and 50. Thesecond set of figures show: (2a) Average Mutual Information Profile for the C. Elegans Chromosomes plotted for values of k between 5 and 50; and b) Average Mutual Information Profile for the S. Cerevisiae Chromosomes plotted for values of k between 5 and 50.

In this paper, we propose a compression algorithm focused on the peculiarities of hyperspectral images. The spectral redundancy in hyperspectral images is exploited by using a context matching method driven by the correlation between adjacent bands of hyperspectral spectral images. The method compares favorably with recent proposed lossless compression algorithms in terms of compression, with significantly lower complexity.

Current proposals for using arithmetic coding in a joint source/channel coding framework require 'soft' information to provide error correction. However, in many applications only the binary arithmetic coded output is available at the decoder. We propose a hard decision technique that uses only the information in the bitstream to provide error correction. Where soft information is available this decoder can also be used to substantially enhance the performance of any soft decision decoders by using the two decoders in an iterative fashion.

We present a compression technique that provides progressive transmission as well as lossless and near-lossless compression in a single framework. The proposed technique produces a bit stream that results in a progressive, and ultimately lossless, reconstruction of an image similar to what one can obtain with a reversible wavelet codec. In addition, the proposed scheme provides near-lossless reconstruction with respect to a given bound, after decoding of each layer of the successively refinable bit stream. We formulate the image data-compression problem as one of successively refining the probability density function (pdf) estimate of each pixel. Within this framework, restricting the region of support of the estimated pdf to a fixed size interval then results in near-lossless reconstruction. We address the context-selection problem, as well as pdf-estimation methods based on context data at any pass. Experimental results for both lossless and near-lossless cases indicate that the proposed compression scheme, that innovatively combines lossless, near-lossless, and progressive coding attributes, gives competitive performance in comparison with state-of-the-art compression schemes.

This paper describes the predictive image compression using conditional averages. compare the performance of the proposed predictor with the GAP predictor used in CALIC and the MED predictor used in JPEG-LS and LOCO-I.

MOTIVATION: One of the major problems in DNA sequencing is assembling the fragments obtained by shotgun sequencing. Most existing fragment assembly techniques follow the overlap-layout-consensus approach. This framework requires extensive computation in each phase and becomes inefficient with increasing number of fragments. RESULTS: We propose a new algorithm which solves the overlap, layout, and consensus phases simultaneously. The fragments are clustered with respect to their Average Mutual Information (AMI) profiles using the k-means algorithm. This removes the unnecessary burden of considering the collection of fragments as a whole. Instead, the orientation and overlap detection are solved efficiently, within the clusters. The algorithm has successfully reconstructed both artificial and real data. AVAILABILITY: Available on request from the authors.

MOTIVATION: Most existing approaches for phylogenetic inference use multiple alignment of sequences and assume some sort of an evolutionary model. The multiple alignment strategy does not work for all types of data, e.g. whole genome phylogeny, and the evolutionary models may not always be correct. We propose a new sequence distance measure based on the relative information between the sequences using Lempel-Ziv complexity. The distance matrix thus obtained can be used to construct phylogenetic trees. RESULTS: The proposed approach does not require sequence alignment and is totally automatic. The algorithm has successfully constructed consistent phylogenies for real and simulated data sets. AVAILABILITY: Available on request from the authors.

A novel image compression technique is presented that incorporates progressive transmission and near-lossless compression in a single framework. Experimental performance of the proposed coder proves to be competitive with the state-of-the-art compression schemes.

Previous work has indicated that using an arithmetic encoder with reserved probability space can provide powerful error detection and error correction when used with a sequential decoding algorithm. However, performance improvements were limited at high error rates, principally because of the lack of an explicit decoding tree. In this work a trellis coded modulation scheme is used to provide a convenient tree for a list decoding algorithm. Results are obtained for both a small alphabet application (SPIHT encoded image) and a large alphabet application (predictive lossless image compression). Simulations on AWGN channels with bit error rates in the range of 10/sup -3/ to 10/sup -1.5/ show significant packet recovery rates even for the poorest channels.

Reserving space fur a symbol that is not in the source alphabet has been shown to provide excellent error detection. In this paper, we show how to exploit this capability using two sequential decoder structures to provide powerful error correction capability. This joint source/channel coder design provides significant packet loss recovery with minimal rate overhead, and compares favorably with conventional schemes.

Reserving space for a symbol that is not in the source alphabet has been shown to provide excellent error detection. In this paper we show how to use this capability using a sequential decoder structure to provide powerful error correction capability. This joint source/channel coder design provides significant packet loss recovery with minimal overhead.

When using entropy coding over a noisy channel, it is customary to protect the highly vulnerable bitstream with an error correcting code. In this paper, we propose a technique which utilizes the residual redundancy at the output of the source coder to provide error protection for entropy coded systems.

The use of the residual redundancy present at the output of a source encoder for the purpose of error correction and detection is explored. Joint source/channel coding schemes of this type utilize redundancy due to the mismatch between the source and the model used to design the source encoder. This idea is extended to include the use of a precoder at the transmitter to create additional redundancy for error correction. A list Viterbi decoder is used at the receiver to perform joint source/channel decoding. The efficacy of this approach is investigated through computer simulation and comparisons to alternative joint source/channel coding schemes.

The assumptions made about the source during source coder design result in a residual redundancy at the output of the source coder. This redundancy can be utilized for error protection without any additional channel coding. Joint source/channel coders obtained using this idea via maximum a posteriori probability decoders tend to fail at low probability of error. In this paper, we propose a modification of the standard approach which provides protection at low error rates as well.

When using entropy coding over a noisy channel it is customary to protect the highly vulnerable bitstream with an error correcting code. In this paper we propose a technique which utilizes the residual redundancy at the output of the source coder to provide error protection for entropy coded systems. The proposed approach provides 4-10 dB improvement over the standard approaches at a reduced rate.

Joint source/channel coders obtained using MAP decoders tend to fail at low probability of error. We propose a modification of the standard approach which provides protection at low error rates as well.

We investigate lossless compression schemes for video sequences. A simple adaptive prediction scheme is presented that exploits temporal correlations or spectral correlations in addition to spatial correlations. It is seen that even with motion compensation, schemes that utilize only temporal correlations do not perform significantly better than schemes that utilize only spectral correlations. Hence, we look at hybrid schemes that make use of both spectral and temporal correlations. The hybrid schemes give significant improvement in performance over other techniques. Besides prediction schemes, we also look at some simple error modeling techniques that take into account prediction errors made in spectrally and/or temporally adjacent pixels in order to efficiently encode the prediction residual. Implementation results on standard test sequences indicate that significant improvements can be obtained by the proposed techniques.

Conventional vector quantization (VQ)-based techniques partition an image into nonoverlapping blocks that are then raster scanned and quantized. Image blocks that contain an edge result in high-frequency vectors. The coarse representation of such vectors leads to visually annoying degradations in the reconstructed image. The authors present a solution to the edge-degradation problem based on some earlier work on scan models. The approach reduces the number of vectors with abrupt intensity variations by using an appropriate scan to partition an image into vectors. They show how their techniques can be used to enhance the performance of VQ of multispectral data sets. Comparisons with standard techniques are presented and shown to give substantial improvements.

While there exist many asymmetric techniques for the lossy compression of image data, most techniques reported for lossless compression of image data have been symmetric. In this paper we present a new lossless compression technique that is well suited for asymmetric applications. It gives superior performance compared to other lossless compression techniques reported in the literature. Hence, it can also potentially be adapted for use in symmetric applications that require high compression ratios.

When applying predictive compression on image data there is an implicit assumption that the image is scanned in a particular order. Clearly, depending on the image, a different scanning order may give better compression. In earlier work, we had defined the notion of a prediction tree (or scan) which defines a scanning order for an image. An image can be decorrelated by taking differences among adjacent pixels along any traversal of a scan. Given an image, an optimal scan that minimizes the absolute sum of the differences encountered can be computed efficiently. However, the number of bits required to encode an optimal scan turns out to be prohibitive for most applications. In this paper we present a prediction scheme that partitions an image into blocks and for each block selects a scan from a codebook of scans such that the resulting prediction error is minimized. Techniques based on clustering are developed for the design of a codebook of scans. Design of both semiadaptive and adaptive codebooks is considered. We also combine the new prediction scheme with an effective error modeling scheme. Implementation results are then given, which compare very favorably with the JPEG lossless compression standard.>

Proposes a novel approach that combines the space covering property of high rate lattice VQ with the pattern matching ability of clustering VQ. The proposed scheme encompasses a broad range of online algorithms that use suitable VQ encodings and fixed-size, adaptive codebooks. The generic baseline algorithm for the scheme has the following desirable characteristics: the distortion per individual vector is guaranteed to be less than a user specified threshold. Secondly, the algorithm is amenable to fast realtime implementation and requires minimal statistical assumptions for analysis. Finally, with careful analysis, the coding rate can be bounded with respect to some theoretical benchmark.>

We investigate the problem of constructing a prediction scheme for a given image that results in the minimum zero-order entropy of prediction errors. The problem is formulated as a combinatorial optimization problem. This allows the use of some well known techniques from combinatorial optimization in order to construct heuristic solutions. We describe a few heuristics and give preliminary implementation results. The techniques developed can also be generalized in a straight forward manner to composite source modeling where the data is modeled as an interleaved sequence emanating from k different sub-sources. Although the problems and proposed solutions are described in a strictly deterministic manner, they can also be formulated in a stochastic framework to yield solutions that are valid for a family of images emitted by the same source.>

The design of joint source/channel coders in situations where there is residual redundancy at the output of the source coder is examined. It has previously been shown that this residual redundancy can be used to provide error protection without a channel coder. In this paper, this approach is extended to conventional source coder/convolutional coder combinations. A family of nonbinary encoders is developed which more efficiently use the residual redundancy in the source coder output. It is shown through simulation results that the proposed systems outperform conventional source-channel coder pairs with gains of greater than 9 dB in the reconstruction SNR at high probability of error.>

Multispectral data is often displayed and stored as a color-mapped or pseudo-color image. Pseudo-color is also used to enhance features in a single-band image. The use of pseudo-color tends to rearrange the structure in the image in such a way as to prevent efficient compression. This structure can be restored by sorting the color maps. Restoration of the structure increases the efficiency of lossless compression and permits the use of lossy compression algorithms. The latter benefit is especially useful for many progressive transmission algorithms.>

While spatial correlations are adequately exploited by standard lossless image compression techniques, little success has been attained in exploiting spectral correlations when dealing with multispectral image data. The authors present some new lossless image compression techniques that capture spectral correlations as well as spatial correlation in a simple and elegant manner. The schemes are based on the notion of a prediction tree, which defines a noncausal prediction model for an image. The authors present a backward adaptive technique and a forward adaptive technique. They then give a computationally efficient way of approximating the backward adaptive technique. The approximation gives good results and is extremely easy to compute. Simulation results show that for high spectral resolution images, significant savings can be made by using spectral correlations in addition to spatial correlations. Furthermore, the increase in complexity incurred in order to make these gains is minimal.>

Some of the important characteristics and requirements of packet video are discussed. A layered packet video coding algorithm based on a progressive transmission scheme is presented. The algorithm provides good compression and can handle significant packet loss with graceful degradation in the reconstruction sequence. A network simulator used in testing the scheme is introduced, and simulation results for various conditions are presented.>

Differential encoding techniques are fast and easy to implement. However, a major problem with the use of differential encoding for images is the rapid edge degradation encountered when using such systems. This makes differential encoding techniques of limited utility, especially when coding medical or scientific images, where edge preservation is of utmost importance. A simple, easy to implement differential image coding system with excellent edge preservation properties is presented. The coding system can be used over variable rate channels, which makes it especially attractive for use in the packet network environment.

A recursively indexed scalar quantizer that performs as well as high-dimensional vector quantizers for several important sources, without the attendant complexity, is presented. The recursively indexed quantizer provides a simple technique, both in terms of design and operation, for use with entropy coding. It also provides a simple quantization technique for use in noisy channel conditions where a variable length code would be inappropriate but performance greater than that provided by Lloyd-Max quantizers is desired.>

Prediction techniques have been applied very successfully in compression of speech data. For image data this paper employs an approach based on spanning trees to construct nonlinear predictive schemes. Images are not scanned in any predetermined fashion, nor is the prediction for any pixel based on a single fixed scheme. Preliminary implementations give promising results over a wide range of images.>

A technique for providing error protection without the additional overhead required for channel coding is presented. The authors start from the premise that, during source coder design, for the sake of simplicity or due to imperfect knowledge, assumptions have to be made about the source which are often incorrect. This results in residual redundancy at the output of the source coder. The residual redundancy can then be used to provide error protection in much the same way as the insertion of redundancy in convolutional coding provides error protection. The authors develop an approach for utilizing this redundancy. To show the validity of this approach, the authors apply it to image coding using differential pulse code modulation (DPCM), and obtain substantial performance gains, both in terms of objective and subjective measures.>

A routing strategy called NELHNET has been developed for networks with multiprecedence traffic and operating under dynamic traffic and topological conditions. An adaptive distributed algorithm that uses least-hop and least-hop-plus-1 routes in a table of routing vectors, as opposed to the usual table of routing scalars, is described. Current delays are passed backward and forward with the packets to allow development of expected delays to each node via all acceptable routes. The route then selected is the acceptable route with the least expected delay. For speedier recovery, a node returning to service receives the current network status from an adjoining node as soon as the link connecting them is operational. The resultant algorithms show far greater than the marginal improvements originally expected over Arpanet simulations. NELHENET strategies also permit the network to function stably under more heavily loaded conditions than do the Arpanet strategies.>

A generic algorithm is presented that can be used, along with simulated annealing, to provide lattice vector quantizers based on different lattices. It is a two-stage algorithm, with each stage based on different ways of looking at the structural regularity of the lattice. The first stage is based on the mathematical definition of a lattice, while the second stage depends on the observation that the view of the surroundings at any lattice point is identical to that at any other lattice point.>

Vector quantizers based on the A and D lattices are explored, using the mean square error (MSE) fidelity criterion for independent identically distributed sources with normal, Laplacian, and gamma probability density functions. Code books are studied for uniform coding rates of up to 2 b/sample and two and four dimensions. The expected MSE performance of the quantizers is better than that of optimal (nonuniform) Lloyd-Max quantizers. While the design algorithm presented offers only modest improvements in MSE performance for a normally distributed source, improvement gains of up to several decibels can be achieved when coding Laplacian and gamma sources.>

Differential PCM with backward adaptive prediction (DPCM-APB) is a popular technique for data compression. Because of the presence of the quantizer in the feedback loop the adaptation process has been difficult to analyze. In this paper we present a bound on the predictor misadjustment and obtain some easily verifiable conditions for convergence of the bound.

Quantization noise constitutes the limiting factor on DPCM performance. For a low number of levels in the quantizer, this noise is also correlated. In this correspondence we present a technique for improving the performance of the DPCM system at a very modest cost. The technique involves the use of an adaptive transversal filter at the receiver output to reduce the effects of quantization noise. The filter is trained at the transmitter and periodic updates sent to the receiver.

A vector quantizer maps ak-dimensional vector into one of a finite set of output vectors or "points". Although certain lattices have been shown to have desirable properties for vector quantization applications, there are as yet no algorithms available in the quantization literature for building quantizers based on these lattices. An algorithm for designing vector quantizers based on the root latticesA_{n}, D_{n}, andE_{n}and their duals is presented. Also, a coding scheme that has general applicability to all vector quantizers is presented. A four-dimensional uniform vector quantizer is used to encode Laplacian and gamma-distributed sources at entropy rates of one and two bits/sample and is demonstrated to achieve performance that compares favorably with the rate distortion bound and other scalar and vector quantizers. Finally, an application using uniform four- and eight-dimensional vector quantizers for encoding the discrete cosine transform coefficients of an image at0.5bit/pel is presented, which visibly illustrates the performance advantage of vector quantization over scalar quantization.

This research is concerned with investigating the problem of data compression utilizing an unsupervised estimation algorithm. This extends previous work utilizing a hybrid source coder which combines an orthogonal transformation with differential pulse code modulation (DPCM). The data compression is achieved in the DPCM loop, and it is the quantizer of this scheme which is approached from an unsupervised learning procedure. The distribution defining the quantizer is represented as a set of separable Laplacian mixture densities for two-dimensional images. The condition of identifiability is shown for the Laplacian case and a decision directed estimate of both the active distribution parameters and the mixing parameters are discussed in view of a Bayesian structure. The decision directed estimators, although not optimum, provide a realizable structure for estimating the parameters which define a distribution which has become active. These parameters are then used to scale the optimum (in the mean square error sense) Laplacian quantizer. The decision criteria is modified to prevent convergence to a single distribution which in effect is the default condition for a variance estimator. This investigation was applied to a test image and the resulting data demonstrate improvement over other techniques using fixed bit assignments and ideal channel conditions.

Adaptive signal processing algorithms are often used in order to "track" an unknown time-varying parameter vector. Such algorithms are typically some form of stochastic gradient-descent algorithm. The Widrow LMS algorithm is apparently the most frequently used. This work develops an upper bound on the norm-squared error between the parameter vector being tracked and the value obtained by the algorithm. The upper bound illustrates the relationship between the algorithm step-size and the maximum rate of variation in the parameter vector. Finally, some simple covariance decay-rate conditions are imposed to obtain a bound on the mean square error.

Sufficient conditions are presented for establishing "desirable" convergence properties of commonly used adaptive signal processing algorithms which use correlated training data. The family of algoriths considered includes the Widrow LMS algorithm. Desirable properties include, e.g., an asymptotic bound on the mean-square error between the parameter vector trained by the adaptive algorithm and the optimal solution. This asymptotic bound should decrease with decreasing step size. The results contained in this paper illustrate the trade-offs involved in choosing the step size to achieve an acceptable convergence rate as well as an acceptable steady state error. The sufficient conditions include bounded data and easily verified covariance decay rate conditions.