Algorithms for compression of hyperspectral data are commonly evaluated on a readily available collection of Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) images. These images are the end product of processing raw data from the instrument, and their sample value distributions contain artificial regularities that are introduced by the conversion of raw data values to radiance units. It is shown that some of the best reported lossless compression results for these images are achieved by algorithms that significantly exploit these artifacts. This fact has not been widely reported and may not be widely recognized. Compression performance comparisons involving such algorithms and these standard AVIRIS images can be misleading if they are extrapolated to images that lack such artifacts, such as unprocessed hyperspectral images. In fact, two of these algorithms are shown to achieve rather unremarkable compression performance on a set of more recent AVIRIS images that do not contain appreciable calibration-induced artifacts. This newer set of AVIRIS images, which contains both calibrated and raw images, is made available for compression experiments. To underscore the potential impact of exploiting calibration-induced artifacts in the standard AVIRIS data sets, a compression algorithm is presented that achieves noticeably smaller compressed sizes for these data sets than is reported for any other algorithm.

Redundancy and optimality are standard concepts for prefix codes for finite-entropy sources, but they can be extended to codes for (discrete) infinite-entropy sources as well. Here three redundancy definitions and two optimality definitions are considered that accomplish this. The redundancy definitions turn out to be equivalent, and they are also equivalent to the 'expected codeword length minus entropy' definition when the source entropy is finite. An analogous statement holds for the optimality definitions. A theorem on the redundancy of finite sources is also presented; it provides a simple bound on the difference between the redundancies of optimal codes for two sources that contain an identical subset of symbol probabilities.

By definition Huffman codes only exist for finite sources, since the Huffman algorithm cannot be applied to an infinite source. On the other hand, Gallager's sibling property, which was introduced as a characterization of Huffman codes, extends naturally to (countably) infinite sources. Thus we define a Huffman-Gallager code as any code that has the sibling property, and we present some basic facts about such codes. (1) For any source, a Huffman-Gallager code exists and its list of node probabilities is unique. (2) A Huffman-Gallager code is optimal, and given an optimal code, there exists a Huffman-Gallager code with the same codeword lengths. (3) For sources with infinite entropy, the existence and uniqueness results continue to hold, and the optimality results hold for a natural extended form of optimality

We show the capacity of a generalized pulse position modulation (PPM) channel, where the input vectors may be any set that allows a transitive group of coordinate permutations, is achieved by a uniform input distribution. We derive a simple expression for capacity in terms of the Kullback-Leibler distance for the binary case, and find the asymptote in the PPM order. We prove a subadditivity result for the PPM channel and use it to show PPM capacity is monotonic in the order.

Given probability vectors x and y, necessary and sufficient conditions are given for the existence of a probability vector z such that xominusz is majorized by yominusz. This is of interest because the "catalytic majorization" relation is known to be useful in classifying which transformations of jointly held pure quantum states are possible using local operations and classical communication when an additional jointly held state may be specified to facilitate the transformation without being consumed

We present a novel entropy coding technique which is based on recursive interleaving of variable-to-variable length binary source codes. The encoding is adaptable in that each bit to be encoded may have an associated probability estimate which depends on previously encoded bits. The technique may have advantages over arithmetic coding. The technique can achieve arbitrarily small redundancy, and admits a simple and fast decoder. We discuss code design and performance estimation methods, as well as practical encoding and decoding algorithms.

Subtractive dither is a technique which may be used to reduce the occurrence of compression artifacts from near-lossless compression. Standard subtractive dither incurs a cost, however, in the form of an increase in rate and distortion, and by giving the reconstructed signal an overall grainy appearance. It is possible to compromise between the costs and benefits of dithering by using dither signals which tend to take on smaller values than the standard dither signal. For reasonable cost and benefit metrics, the optimal dither signals are shown to be those which are uniform on intervals of the form [-k/2,k/2], where k/spl epsiv/[0,q] and q is the quantization step size. Additional results are given under more general assumptions.

The fundamental limits of performance for a general model of information retrieval from databases are studied. In the scenarios considered, a large quantity of information is to be stored on some physical storage device. Requests for information are modeled as a randomly generated sequence with a known distribution. The requests are assumed to be "context-dependent," i.e., to vary according to the sequence of previous requests. The state of the physical storage device is also assumed to depend on the history of previous requests. In general, the logical structure of the information to be stored does not match the physical structure of the storage device, and consequently there are nontrivial limits on the minimum achievable average access times, where the average is over the possible sequences of user requests. The paper applies basic information-theoretic methods to establish these limits and demonstrates constructive procedures that approach them, for a wide class of systems. Allowing redundancy greatly lowers the achievable access times, even when the amount added is an arbitrarily small fraction of the total amount of information in the database. The achievable limits both with and without redundancy are computed; in the case where redundancy is allowed the limits essentially coincide with lower limits for more general storage systems.

The problem of shaping signal constellations that are designed for the Gaussian channel is considered. The signal constellation consists of all points from some translate of a lattice Lambda that lie within a region R. The signal constellation is partitioned into T annular subconstellations Omega /sub o/,..., Omega /sub T-1/, by scaling the region R. Signal points in the same subconstellation are used equiprobably, and a shaping code selects region Omega /sub i/ with frequency f/sub i/. If the signal constellation is partitioned into annular subconstellations of unequal size. then the transmission rate should vary with the choice of codeword in the shaping code. and it will be necessary to queue the data in buffers. It is described how the balanced binary codes constructed by D. E. Knuth (1986) can be used to avoid a data rate that is probabilistic. The basic idea is that if symbols 0 and 1 represent constellations of unequal size. and if all shaping codewords have equally many 0's and 1's, then the data rate will be deterministic.>