Unique decodability in the “one-shot” lossless coding scenario, where a single block of source samples is compressed, requires the assignment of distinct codewords to different blocks (one-to-one mapping), without the prefix constraint. As a result, for fixed-length blocks, the corresponding block entropy is not a lower bound on the expected code length, a fact that has recently attracted renewed interest. In this note, we consider an alternative scenario, where the encoder is fed with blocks of arbitrary length, which we argue better reflects the conditions under which one-shot codes may be of any interest. Elaborating on an argument by Rissanen, we first show that the block-entropy is still a fundamental performance bound for one-to-one codes. We then design a code that essentially achieves this bound and satisfies Kraft's inequality for each block length. This code can be implemented with a modification to the termination procedure of the popular Shannon-Fano-Elias code. We conclude that Kraft's inequality is relevant also in the one-shot coding scenario.

We study random number generators (RNGs), both in the fixed to variable-length (FVR) and the variable to fixed-length (VFR) regimes, in a universal setting in which the input is a finite memory source of arbitrary order and unknown parameters, with arbitrary input and output (finite) alphabet sizes. Applying the method of types, we characterize essentially unique optimal universal RNGs that maximize the expected output (respectively, minimize the expected input) length in the FVR (respectively, VFR) case. For the FVR case, the RNG studied is a generalization of Elias's scheme, while in the VFR case the general scheme is new. We precisely characterize, up to an additive constant, the corresponding expected lengths, which include second-order terms similar to those encountered in universal data compression and universal simulation. Furthermore, in the FVR case, we consider also a twice-universal setting, in which the Markov order k of the input source is also unknown.

Efficient enumerative coding for tree sources is, in general, surprisingly intricate-a simple uniform encoding of type classes, which is asymptotically optimal in expectation for many classical models, such as FSMs, turns out not to be so in this case. We describe an efficiently computable enumerative code that is universal in the family of tree models in the sense that, for a string emitted by an unknown source whose model is supported on a known tree, the expected normalized code length of the encoding approaches the entropy rate of the source with a convergence rate (K/2)(log n)/n, where K is the number of free parameters of the model family. Based on recent results characterizing type classes of context trees, the code consists of the index of the sequence in the tree type class, and an efficient description of the class itself using a nonuniform encoding of selected string counts. The results are extended to a twice-universal setting, where the tree underlying the source model is unknown.

We study fixed to variable-length random number generators (FVRs) that input a fixed number of symbols from a finite memory source of arbitrary order and unknown parameters, and output a number uniformly distributed in {0, 1,..., M-1}, where M is also random. We review Elias's FVR in the context of the method of types, and show that it remains universal and optimal in the broad class of k-th order finite memory processes. We precisely characterize, up to an additive constant, the expected output length of the optimal FVR, and show that it includes a model cost term similar to those encountered in universal data compression and universal simulation. We further define twice-universal FVRs, which produce quasi-uniform distributions when the input is a finite memory source of unknown order and parameters. We propose a twice-universal FVR whose expected output length is the same, up to an additive constant, as that of an optimal FVR constructed with knowledge of the order k, with the distance of the output to a uniform distribution vanishing exponentially fast with the input length.

We study variable to fixed-length random number generators (VFRs) that input a variable number of symbols from a finite memory source of arbitrary order and unknown parameters, and output a number uniformly distributed in {0, 1, ..., M-1} for arbitrary fixed M. We further require that the VFR output be uniformly distributed also if an arbitrary bound N is imposed on the input length, at the cost of a positive probability of the VFR terminating with no output (failing). We characterize the essentially unique optimal VFR, which minimizes both the expected input length and the failure probability for all truncation levels N. We precisely characterize, up to an additive constant, the expected input length of the optimal VFR, which includes a model cost term similar to those encountered in universal data compression and universal simulation.

We propose a sequence of universal denoisers motivated by the goal of extending the notion of twice-universality from universal data compression theory to the sliding window denoising setting. Given a sequence lengthnand a denoiser, thekth-order regret of the latter is the maximum excess expected denoising loss relative to sliding window denoisers with window length 2k+1, where, for a given clean sequence, the expectation is over all channel realizations and the maximum is over all clean sequences of lengthn. We define the twice-universality penalty of a denoiser as its excesskth-order regret when compared to a bound on thekth-order regret of the denoising algorithm DUDE with parameterk, and we are interested in denoisers with a negligible penalty for allksimultaneously. We consider a class of denoisers that apply one of a number of constituent denoisers based on minimizing an estimated denoising loss and establish a formal relationship between the error in the estimated denoising loss and the twice-universality penalty of the resulting denoiser. Given a sequence of window parameterskn, increasing innsufficiently fast, we use this approach to construct and analyze a specific sequence of denoisers that achieves a much smaller twice-universality penalty forkknthan the sequence of DUDE denoisers with parameterkn.

Minimax prediction of binary sequences is investigated for cases in which the predictor is forced to issue a piecewise constant prediction. The minimax strategy is characterized for Hamming loss whereas, for logarithmic loss, an asymptotically minimax strategy which achieves the leading term of the asymptotic minimax redundancy, is proposed. The average redundancy case is also analyzed for i.i.d. distributions. The piecewise constant prediction paradigm may be of relevance to resource constrained settings.

It is well known that a tree model does not always admit a finite-state machine (FSM) representation with the same (minimal) number of parameters. Therefore, known characterizations of type classes for FSMs do not apply, in general, to tree models. In this paper, the type class of a sequence with respect to a given context tree is studied. An exact formula is derived for the size of the class, extending Whittle's formula for type classes with respect to FSMs. The derivation is more intricate than in the FSM case, since some basic properties of FSM types do not hold in general for tree types. The derivation also yields an efficient enumeration of the tree type class. A formula for the number of type classes with respect to is also derived. The formula is asymptotically tight up to a multiplicative constant and also extends the corresponding result for FSMs. The asymptotic behavior of the number of type classes, and of the size of a class, is expressed in terms of the so-called minimal canonical extension of T, a tree that is generally larger than but smaller than its FSM closure.

We study the problem of deinterleaving a set of finite-memory (Markov) processes over disjoint finite alphabets, which have been randomly interleaved by a finite-memory switch. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or structure of the component Markov processes, or of the switch. We study conditions for uniqueness of the interleaved representation of a process, showing that certain switch configurations, as well as memoryless component processes, can cause ambiguities in the representation. We show that a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function is strongly consistent, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, a set of component and switch Markov processes compatible with the original interleaved process. Furthermore, under certain conditions on the structure of the switch (including the special case of a memoryless switch), we show that the scheme recovers all possible interleaved representations of the original process. Experimental results are presented demonstrating that the proposed scheme performs well in practice, even for relatively short input samples.

We study the minimax pointwise redundancy of universal coding for memoryless models over large alphabets and present two main results. We first complete studies initiated in Orlitsky and Santhanam deriving precise asymptotics of the minimax pointwise redundancy for all ranges of the alphabet size relative to the sequence length. Second, we consider the minimax pointwise redundancy for a family of models in which some symbol probabilities are fixed. The latter problem leads to a binomial sum for functions with superpolynomial growth. Our findings can be used to approximate numerically the minimax pointwise redundancy for various ranges of the sequence length and the alphabet size. These results are obtained by analytic techniques such as tree-like generating functions and the saddle point method.

We study the problem of deinterleaving a set of finite-memory (Markov) processes over disjoint finite alphabets, which have been randomly interleaved by a finite-memory switch, extending previous results obtained for the case of a memoryless switch [1]. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or structure of the Markov processes, or of the switch. We study conditions for uniqueness of the interleaved representation of a process, showing that certain switch configurations can cause ambiguities in the representation, in addition to those caused by memoryless component processes, which were known in the memoryless switch case. We show that a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function is strongly consistent also in the finite-memory switch case, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, a set of component and switch Markov processes compatible with the original interleaved process. Furthermore, under certain conditions on the structure of the switch, we show that the scheme recovers all possible interleaved representations of the original process. Experimental results are presented demonstrating that the proposed scheme performs well in practice, even for relatively short input samples.

We pose the problem of energy-optimized lossless compression and analyze a simple compression framework in which energy consumption is given by a weighted sum of two components, respectively proportional to the compression rate and to the average number of bit flips that occur in a certain hardware register. The latter component, which we term variability, is meant to serve as a proxy for the energy consumption of the computations underlying the compression step. Our results include bounds on the rate-variability tradeoff for symbol-wise compression of discrete memoryless sources and a characterization of the asymptotically optimum tradeoff between rate and variability for block-wise compression.

We present an extension of the discrete universal denoiser DUDE, specialized for the denoising of grayscale images. The original DUDE is a low-complexity algorithm aimed at recovering discrete sequences corrupted by discrete memoryless noise of known statistical characteristics. It is universal, in the sense of asymptotically achieving, without access to any information on the statistics of the clean sequence, the same performance as the best denoiser that does have access to such information. The DUDE, however, is not effective on grayscale images of practical size. The difficulty lies in the fact that one of the DUDE's key components is the determination of conditional empirical probability distributions of image samples, given the sample values in their neighborhood. When the alphabet is relatively large (as is the case with grayscale images), even for a small-sized neighborhood, the required distributions would be estimated from a large collection of sparse statistics, resulting in poor estimates that would not enable effective denoising. The present work enhances the basic DUDE scheme by incorporating statistical modeling tools that have proven successful in addressing similar issues in lossless image compression. Instantiations of the enhanced framework, which is referred to as iDUDE, are described for examples of additive and nonadditive noise. The resulting denoisers significantly surpass the state of the art in the case of salt and pepper (S&P) and M -ary symmetric noise, and perform well for Gaussian noise.

The classical framework of context-tree models used in sequential decision problems such as compression and prediction is generalized to a setting in which the observations are multi-tracked, multi-sided, or multi-directional, and for which it may be beneficial to consider contexts comprised of possibly differing numbers of symbols from each track or direction. Tree representations of context sets and pruning algorithms for those trees are extended from the uni-directional setting to two directions. We further show that such tree representations do not extend, in general, tomdirections,m>; 2, and that, as a result, determining the bestm-directional context set form>; 2 may be substantially more complex than in the case ofm≤ 2. An application of the proposed pruning algorithm to denoising, wherem=2 , is presented.

Bi-directional context sets extend the classical context-tree modeling framework to situations in which the observations consist of two tracks or directions. In this paper, we study the problem of efficiently finding an optimal bi-directional context set for a given data sequence and loss function. This problem has applications in data compression, prediction, and denoising. The main tool in our construction is a new data structure, the compact bi-directional context graph, which generalizes compact suffix trees to two directions.

We propose a new sequence of universal denoisers motivated by the goal of extending the notion of twice-universality from universal data compression theory to the sliding window denoising setting. Given a sequence length n and a denoiser, we define the twice-universality penalty of the denoiser as the worst case excess expected denoising loss relative to sliding window denoisers with window length k above and beyond the worst case excess loss of DUDE with parameter k. Given a sequence of window parameters kn, increasing in n sufficiently fast, we use loss estimators to construct a sequence of denoisers that achieves a much smaller twice-universality penalty for knthan the sequence of DUDEs with parameter kn.

We study the minimax redundancy of universal coding for large alphabets over memoryless sources and present two main results: We first complete studies initiated in Orlitsky and Santhanam deriving precise asymptotics of the minimax redundancy for all ranges of the alphabet sizes. Second, we consider the minimax redundancy of a source model in which some symbol probabilities are fixed. The latter model leads to an interesting binomial sum asymptotics with super-exponential growth functions. Our findings could be used to approximate numerically the minimax redundancy for various ranges of the sequence length and the alphabet size. These results are obtained by analytic techniques such as tree-like generating functions and the saddle point method.

The problem of universal simulation given a training sequence is studied both in a stochastic setting and for individual sequences. In the stochastic setting, the training sequence is assumed to be emitted by a Markov source of unknown order, extending previous work where the order is assumed known and leading to the notion of twice-universal simulation. A simulation scheme, which partitions the set of sequences of a given length into classes, is proposed for this setting and shown to be asymptotically optimal. This partition extends the notion of type classes to the twice-universal setting. In the individual sequence scenario, the same simulation scheme is shown to generate sequences which are statistically similar, in a strong sense, to the training sequence, for statistics of any order, while essentially maximizing the uncertainty on the output.

We study the concentration of denoiser loss estimators, with application to the selection of denoiser parameters for a given observed sequence (in particular, the window size k of the DUDE algorithm) via minimization of the estimated loss. We show that for a loss estimator proposed earlier, it is not possible to derive strong concentration results for certain pathological input sequences. By modifying the estimator slightly we obtain a loss estimator for which the DUDE's estimated loss strongly concentrates around the true loss provided kM2k= o(n), where M is the size of the alphabet and n the sequence length. We also show that for certain channels, it is possible to estimate the best k using a combination of the two loss estimators. Moreover, for non-pathological sequences and k = o(n¿), we derive concentration results for the original loss estimator and all channels.

We study the problem of deinterleaving a set of finite memory (Markov) processes over disjoint finite alphabets, which have been randomly interleaved by a memoryless random switch. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or structure of the Markov processes, or the parameters of the switch. We present a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function, and show it to be strongly consistent, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, the original Markov and switch processes. Solutions are described for the case where a bound on the order of the Markov processes is available, and for the case where it is not. We demonstrate that the proposed scheme performs well in practice, requiring much shorter input sequences for reliable deinterleaving than previous solutions.

We consider the problem of universal simulation of a memoryless source (with some partial extensions to Markov sources), based on a training sequence emitted from the source. The objective is to maximize the conditional entropy of the simulated sequence given the training sequence, subject to a certain distance constraint between the probability distribution of the output sequence and the probability distribution of the input, training sequence. We derive, for several distance criteria, single-letter expressions for the maximum attainable conditional entropy as well as corresponding universal simulation schemes that asymptotically attain these maxima.

We consider a setting relevant to the design of storage systems in which a list of defective storage blocks, as determined at manufacture time, is stored in a high-speed system controller memory to enable the efficient bypassing of defective blocks in a transparent manner, external to the system. Conventionally, such lists have been compressed losslessly to save on the cost of the controller memory. Under the assumption of a total system cost that is a linear combination of the number of storage blocks and the controller memory size, we study the potential benefits of compressing the defect list using lossy algorithms. The only restriction is that the reconstructed defect list not label any defective storage blocks as being non-defective.

Efficient enumerative coding for tree sources is, in general, surprisingly intricate-a simple uniform encoding of type classes, which is asymptotically optimal in expectation for many classical models such as FSMs, turns out not to be so in this case. We describe an efficiently computable enumerative code that is universal in the class of tree sources in the sense that, for a string emitted by an unknown source supported on a known tree, the expected normalized code length approaches the entropy rate of the source with a convergence rate (K/2)(log n)/n, where K is the number of free parameters of the source. The results extend also to the twice-universal setting, where the tree is unknown.

We consider a setting relevant to the design of storage systems in which a list of defective storage blocks, as determined at manufacture time, is stored in a high-speed system controller memory to enable the efficient bypassing of defective blocks in a transparent manner, external to the system. Conventionally, such lists have been compressed losslessly to save on the cost of the controller memory. Under the assumption of a total system cost that is a linear combination of the number of storage blocks and the controller memory size, we study the potential benefits of compressing the defect list using lossy algorithms, with the restriction that the reconstructed defect list not label any defective storage blocks as being non-defective.

Given a parametric model family, the set of sequences of length n over a finite alphabet A is partitioned into type classes, where two sequences belong to the same class if and only if they are assigned the same probability by all models in the family. Since all sequences in a class are equiprobable, the universal probability assignment problem for the given model family reduces to optimally assigning probabilities to type classes. This reduction is optimally performed by the Normalized Maximum Likelihood (NML) code, which can be interpreted as a description of the type, generated by assigning to it a probability proportional to its ML probability, followed by an enumeration of the sequences in the type class. Unfortunately, implementing the NML code is difficult even for the simplest model classes. Other universal methods, based, for example, on the Krichevskii-Trofimov sequential probability assignment, are computationally efficient and also assign the same code length to all the sequences of a given type. They do not, however, provide a separate and identifiable description of the type. In this paper, we are interested in universal enumerative source codes that possess both qualities: they provide a separate description of the type class of the encoded sequence, and this description can be efficiently computed. By "efficient computation" we mean one with running time that is polynomial in the length of the input sequence, as well as in the number of model parameters.

Universal, delay-limited simulation of an unknown information source of a certain parametric family (e.g., the family of memoryless sources or Markov sources of a given order), given a training sequence from that source and a stream of independent and uniformly distributed bits, is considered. The goal of universal simulation is that the probability law of the generated sequence be identical to that of the training sequence, with minimum mutual information between the random processes generating both sequences. In the delay-limited setting, the simulation algorithm generates a random sequence sequentially, by delivering one symbol for each training symbol that is made available after a given initial delay, whereas the random bits are assumed to be available on demand. In this paper, the optimal universal delay-limited simulation scheme is characterized for broad parametric families, and the mutual information achieved by the proposed scheme is analyzed. The results are extended to a setting of variable delay.

The problem of universal simulation given a training sequence is studied both in a stochastic setting and for individual sequences. In the stochastic setting, the training sequence is assumed to be emitted by a Markov source of unknown order, extending previous work where the order is assumed known and leading to the notion of twice-universal simulation. A simulation scheme, which partitions the set of sequences of a given length into classes, is proposed for this setting and shown to be asymptotically optimal. This partition extends the notion of type classes to the twice-universal setting. In the individual sequence scenario, the same simulation scheme is shown to generate sequences which are statistically similar, in a strong sense, to the training sequence, for statistics of any order, while essentially maximizing the uncertainty on the output.

It is well known that a tree model does not always admit a finite-state machine (FSM) representation with the same (minimal) number of parameters. Therefore, known characterizations of type classes for FSMs do not apply, in general, to tree models. In this paper, the type class of a string with respect to a tree model is studied, and an exact formula is derived for the size of the class. The formula, which applies to arbitrary trees, generalizes Whittle's formula for FSMs. The derivation is more intricate than the FSM case, since some basic properties of FSM types do not hold in general for tree-model types. The derivation also yields an efficient enumeration of the tree-model type class, which has applications in universal data compression and universal simulation. A formula for the number of type classes with respect to a given tree is also derived. The formula is asymptotically tight up to multiplication by a constant and also generalizes a known result for FSMs.

We consider the filtering problem, where a finite-alphabet individual sequence is corrupted by a discrete memoryless channel, and the goal is to causally estimate each sequence component based on the past and present noisy observations. We establish a correspondence between the filtering problem and the problem of prediction of individual sequences which leads to the following result: Given an arbitrary finite set of filters, there exists a filter which performs, with high probability, essentially as well as the best in the set, regardless of the underlying noiseless individual sequence. We use this relationship between the problems to derive a filter guaranteed of attaining the "finite-state filterability" of any individual sequence by leveraging results from the prediction problem

We consider the problem of universal simulation of memoryless sources and Markov sources, based on training sequence emitted from these sources. The objective is to maximize the conditional entropy of the simulated sequence given the training sequence, subject to a certain distance constraint between the probability distribution of the output sequence and the probability distribution of the input, training sequence. We derive a single-letter expression for the maximum conditional entropy and then propose a universal simulation scheme that asymptotically attains this maximum

This paper discusses the challenges of applying the DUDE framework to continuous tone images and the tools used to address these challenges. As in lossless image compression, a key component of the DUDE framework is the determination of a probability distribution for samples of the input (noisy) image, conditioned on their contexts. Thus, we can leverage from tools developed and tested in the context of lossless compression for determining such distributions, together with tools that are specific to the assumptions of the denoising application. These tools combine with the DUDE principles into a framework that yields powerful and practical denoisers for continuous tone images corrupted by a variety of noise processes.

We consider the problem of universal delay-limited simulation of an unknown information source of a certain parametric family (e.g., the family of memoryless sources or Markov sources of a given order), given a training sequence from that source and a stream of purely random bits. In the delay-limited setting, the simulation algorithm generates a random sequence sequentially, by delivering one symbol for each training symbol that is made available after a given initial delay, whereas the random bits are assumed to be available on demand. The goal of universal simulation is that the probability law of the generated sequence be identical to that of the training sequence, with minimum mutual information between the random processes generating both sequences. We characterize the optimal delay-limited simulation scheme and upper-bound the expected number of random bits it consumes. As in the non-sequential case, this upper bound is related to the entropy rate of the source

The classical framework of context-tree models used in sequential decision problems such as compression and prediction is generalized to a setting in which the observations are multi-tracked or multi-directional, and for which it may be beneficial to consider contexts comprised of possibly differing numbers of symbols from each track or direction. Context set definitions, tree representations, and pruning algorithms are all extended from the classical uni-directional setting to the m-directional setting, with an emphasis on the case of m = 2. We provide a simple example suggesting that determining (pruning) the best m-directional context set for m ges 3 is substantially more complex than in the case of m = 2. After briefly describing how the multi-directional framework can be applied to universal data compression, we focus on its application to universal denoising, where we pair the proposed framework with a new technique for estimating the loss of a denoising algorithm based only on noisy observations

In a recent paper (Merhav and Weinberger, IEEE Trans. Inf. Theory, vol.50, no.1, p.5-20, 2004) we studied the problem of universal simulation of an unknown information source of a certain parametric family, given a training sequence from that source and given a limited budget of purely random bits. The goal was to generate another random sequence (of the same length or shorter), whose probability law is identical to that of the given training sequence, but with minimum statistical dependency (minimum mutual information) between the input training sequence and the output sequence. In this addendum, we point out a concrete optimal simulation scheme that is easy to implement, as opposed to the nonconstructive existence result in that paper, and we make a number of additional observations on the universal simulation problem.

Given two probability distributions Q and P, let /spl par/Q-P/spl par//sub 1/ and D(Q/spl par/P), respectively, denote the L/sub 1/ distance and divergence between Q and P. We derive a refinement of Pinsker's inequality of the form D(Q/spl par/P)/spl ges/c(P)/spl par/Q-P/spl par//sub 1//sup 2/ and characterize the best P-dependent factor c(P). We apply the refined inequality to large deviations and measure concentration.

A discrete denoising algorithm estimates the input sequence to a discrete memoryless channel (DMC) based on the observation of the entire output sequence. For the case in which the DMC is known and the quality of the reconstruction is evaluated with a given single-letter fidelity criterion, we propose a discrete denoising algorithm that does not assume knowledge of statistical properties of the input sequence. Yet, the algorithm is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the channel noise. The proposed denoising algorithm is practical, requiring a linear number of register-level operations and sublinear working storage size relative to the input data length.

Applying generalized context trees and their finite state machine closures, a two-pass version of context, a twice-universal lossless coding scheme for tree models, can be implemented in linear encoding/decoding time. As it turns out, an optimal context selection rule and the corresponding context transitions are computationally not more expensive than the various steps involved in the implementation of the Burrows-Wheeler transform (BWT) and use, in fact, similar tools. Also the paper presents a reversible transform that displays the same "context deinterleaving" feature as the BWT but is naturally based on an optimal context tree. This transform offers insight into the workings of the BWT and the nature of its suboptimality for twice-universal coding of tree models.

In the discrete filtering problem, a data sequence over a finite alphabet is assumed to be corrupted by a discrete memoryless channel. The goal is to reconstruct the clean sequence, with as high a fidelity as possible, by way of causal processing of the noisy sequence alone, with the reconstruction at time t depending only on noisy observations occurring no later than t. A universal version of this problem in which no assumptions are made about the distribution of the clean data, which may even be nonstochastic is studied. Using techniques from universal data compression, in particular, the incremental parsing rule of LZ78, and derives a practical and efficient algorithms for the universal filtering of discrete sources. A finite-memory filter of order k has the property that the reconstruction at any time t is a time-invariant function only of noisy observations occurring between times t-k and t, inclusive. The universal filtering algorithms perform essentially as well, in an expected sense (with respect to the noise process), as the best finite-memory filter of any fixed order, determined with full knowledge of the actual clean data sequence, for all such data sequences. Also consider more general finite-state filters and show that any such filter is arbitrarily well approximated by a finite-memory filter of growing order, thereby establishing the universality of the proposed algorithms with respect to this larger class. This result can be viewed as the filtering analogue of the well known optimality of LZ78 relative to the class of finite-state compressors.

This paper presents the first algorithm for linear time encoding/decoding of a twice-universal code in class of tree models. The implemented code is a two-pass (semi-predictive) version of context. The algorithmic tools employed in its derivation and their information-theoretic implications is also investigated. The FSM closure of a generalised context tree, defined as the smallest finite-state machine is characterised.

This paper describes the channel decoding of systematically encoded unknown redundant sources. The redundancy of the data is known at the decoder and the channel decoder incorporates the statistics of the data to enhance the performance. The practical decoders are designed which takes the advantage of the source redundancy of systematically encoded for transmission over a discrete memoryless channel (DMC). The performance is achieved by operating discrete universal denoiser (DUDE) and the experiments involving Reed-Solomon codes show that DUDE-enhanced decoding is very effective at high rates.

Given two probability distributions Q and P, let /spl par/Q-P/spl par//sub 1/ and D(Q/spl par/P), respectively, denote the L/sub 1/ distance and divergence between Q and P. We derive a refinement of Pinsker's inequality of the form D(Q/spl par/P)/spl ges//spl phi/(P)/spl par/Q-P/spl par//sub 1//sup 2/ and characterize the best P-dependent factor /spl phi/(P).

The classical framework of context-tree models, customary in sequential decision problems such as compression and prediction, is generalized to a setting in which the observations are multi-tracked or multi-directional, and for which it may be beneficial to consider contexts comprised of possibly differing numbers of symbols from each track or direction. The notion of a bi-directional context set is formalized and the generalization of the classical context-tree-based representation for a well defined set of bi-directional contexts is presented, together with an efficient dynamic programming algorithm for determining the best set of bi-directional contexts for a given individual sequence, maximum context depth, and loss function. After briefly describing how this framework can be applied to universal data compression, we focus on its application to universal denoising, where we pair the proposed framework with a new technique for estimating the loss of a denoising algorithm based only on noisy observations.

Tree models are efficient parametrizations of finite-memory processes, offering potentially significant model cost savings. The information theory literature has focused mostly on redundancy aspects of the universal estimation and coding of these models. In this paper, we investigate representations and supporting data structures for finite-memory processes, as well as the major impact these structures have on the universal algorithms in which they are used. We first generalize the class of tree models, and then define and investigate the properties of the finite-state machine (FSM) closure of a tree, which is the smallest FSM that generates all the processes generated by the tree. The interaction between FSM closures, generalized context trees (GCTs), and classical data structures such as compact suffix trees brings together the information-theoretic and the computational aspects, leading to the first algorithm for linear time encoding/decoding of a lossless twice-universal code in the class of three models. The implemented code is a two-pass version of Context. The corresponding optimal context selection rule and context transitions use tools similar to those employed in efficient implementation of the popular Burrows-Wheeler transform (BWT), yielding similar computational complexities. We also present a reversible transform that displays the same "context deinterleaving" feature as the BWT but is naturally based on an optimal context tree. FSM closures are also applied to an investigation of the effect of time reversal on tree models, motivated in part by the following question: When compressing a data sequence using a universal scheme in the class of tree models, can it make a difference whether we read the sequence from left to right or from right to left? Given a tree model of a process, we show constructively that the number of states in the tree model corresponding to the reversed process might be, in the extreme case, quadratic in the number of states of the original tree. This result answers the above motivating question in the affirmative.

We consider the problem of universal simulation of an unknown random process, or information source, of a certain parametric family, given a training sequence from that source and given a limited budget of purely random bits. The goal is to generate another random sequence (of the same length or shorter), whose probability law is identical to that of the given training sequence, but with minimum statistical dependency (minimum mutual information) between the input training sequence and the output sequence. We derive lower bounds on the mutual information that are shown to he achievable by conceptually simple algorithms proposed here. We show that the behavior of the minimum achievable mutual information depends critically on the relative amount of random bits and on the lengths of the input sequence and the output sequence. While in the ordinary (nonuniversal) simulation problem, the number of random bits per symbol must exceed the entropy rate H of the source in order to simulate it faithfully, in the universal simulation problem considered here, faithful preservation of the probability law is not a problem, yet the same minimum rate of H random bits per symbol is still needed to essentially eliminate the statistical dependency between the input sequence and the output sequence. The results are extended to more general information measures.

This paper describes a discrete universal denoiser for two dimensional data and also presents an experimental results of its application to noisy binary images. A discrete universal denoiser (DUDE) is introduced for recovering a signal with finite-valued components corrupted by finite-valued, uncorrelated noise. The DUDE is asymptotically optimal and universal, in the sense of asymptotically achieving, without access to any information on the statistics of the clean signal, the same performance as the best denoiser that does have access to such information. It is also practical, and can be implemented in low complexity.

We propose a discrete denoising algorithm, that, based on the observation of the output of a known discrete memoryless channel (DMC), estimates the input sequence to minimize a given fidelity criterion. The algorithm is universal in the sense that it requires no knowledge of the input sequence or its statistical properties. Yet, asymptotically it performs as well as the optimum denoiser that knows the input sequence distribution. The proposed denoising algorithm is practical, and can be implemented in O(n log n) time and O(n/sup 2/3/ log n) storage complexity. Extensions to the case of delay-constrained denoising, and to the case of channel uncertainty, are briefly discussed.

The problem of optimal sequential decision for individual sequences, relative to a class of competing off-line reference strategies, is studied for general loss functions with memory. This problem is motivated by applications in which actions may have "long-term" effects, or there is a cost for switching from one action to another. As a first step, we consider the case in which the reference strategies are taken from a finite set of generic "experts." We then focus on finite-state reference strategies, assuming finite action and observation spaces. We show that key properties, that hold for finite-state strategies in the context of memoryless loss functions, do not carry over to the case of loss functions with memory. As a result, an infinite family of randomized finite-state strategies is seen to be the most appropriate reference class for this case, and the problem is basically different from its memoryless counterpart. Based on Vovk's (1990) exponential weighting technique, infinite-horizon on-line decision schemes are devised. For an arbitrary sequence of observations of length n, the excess normalized loss of these schemes relative to the best expert in a corresponding reference class is shown to be upper-bounded by an O(n/sup -1/3/) term in the case of a finite class, or an O([(ln n)/n]/sup 1/3/) term for the class of randomized finite-state strategies. These results parallel the O(n/sup -1/2/) bounds attained by previous schemes for memoryless loss functions. By letting the number of states in the reference class grow, the notion of finite-state predictability is also extended.

Prediction of individual sequences is investigated for cases in which the decision maker observes a delayed version of the sequence, or is forced to issue his/her predictions a number of steps in advance, with incomplete information. For finite action and observation spaces, it is shown that the prediction strategy that minimizes the worst case regret with respect to the Bayes envelope is obtained through subsampling of the sequence of observations. The result extends to the case of logarithmic loss. For finite-state (FS) reference prediction strategies, the delayed FS predictability (DFSP) is defined and related to its nondelayed counterpart. As in the nondelayed case, an efficient on-line decision algorithm, based on the incremental parsing rule, is shown to perform in the long run essentially as well as the best FS strategy determined in hindsight, with full knowledge of the given sequence of observations. An application to adaptive prefetching in computer memory architectures is discussed.

Prefetching in computer memory architectures is formalized as a sequential decision problem in which the instantaneous losses depend not only on the current action-observation pair, as in the traditional formulation, but also on past pairs. Motivated by the prefetching application, we study a class of loss functions that admit an efficient on-line decision algorithm. The algorithm uses the LZ78 parsing rule to dynamically build a tree, different from the classical LZ78 tree, and makes decisions based on the current node in a traversal path, determined by the sequence of observations. The asymptotic performance is essentially as good as that of the best finite-state strategy determined in hindsight, with full knowledge of the given sequence of observations. The related notion of delayed FS predictability is introduced, and its properties are studied.

This paper describes the embedded block coding algorithm at the heart of the JPEG2000 image compression standard. The algorithm achieves excellent compression performance, usually somewhat higher than that of SPIHT with arithmetic coding, but in some cases substantially higher. The algorithm utilizes the same low complexity binary arithmetic coding engine as JBIG2. Together with careful design of the bit-plane coding primitives, this enables comparable execution speed to that observed with the simpler variant of SPIHT without arithmetic coding. The coder offers additional advantages including memory locality, spatial random access and ease of geometric manipulation.

In this paper, we survey some of the recent advances in lossless compression of continuous-tone images. The modeling paradigms underlying the state-of-the-art algorithms, and the principles guiding their design, are discussed in a unified manner. The algorithms are described and experimentally compared.

LOCO-I (LOw COmplexity LOssless COmpression for Images) is the algorithm at the core of the new ISO/ITU standard for lossless and near-lossless compression of continuous-tone images, JPEG-LS. It is conceived as a "low complexity projection" of the universal context modeling paradigm, matching its modeling unit to a simple coding unit. By combining simplicity with the compression potential of context models, the algorithm "enjoys the best of both worlds." It is based on a simple fixed context model, which approaches the capability of the more complex universal techniques for capturing high-order dependencies. The model is tuned for efficient performance in conjunction with an extended family of Golomb-type codes, which are adaptively chosen, and an embedded alphabet extension for coding of low-entropy image regions. LOCO-I attains compression ratios similar or superior to those obtained with state-of-the-art schemes based on arithmetic coding. Moreover, it is within a few percentage points of the best available compression ratios, at a much lower complexity level. We discuss the principles underlying the design of LOCO-I, and its standardization into JPEC-LS.

A complete characterization of optimal prefix codes for off-centered, two-sided geometric distributions of the integers is presented. These distributions are often encountered in lossless image compression applications, as probabilistic models for image prediction residuals. The family of optimal codes described is an extension of the Golomb codes, which are optimal for one-sided geometric distributions. The new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the heuristic approximations frequently used when modifying a code designed for nonnegative integers so as to apply to the encoding of any integer. Optimal decision rules for choosing among a lower complexity subset of the optimal codes, given the distribution parameters, are also investigated, and the relative redundancy of the subset with respect to the full family of optimal codes is bounded.

Lossless compression is studied for a countably infinite alphabet source with an unknown, off-centered, two-sided geometric (TSG) distribution, which is a commonly used statistical model for image prediction residuals. We demonstrate that arithmetic coding based on a simple strategy of model adaptation, essentially attains the theoretical lower bound to the universal coding redundancy associated with this model. We then focus on more practical codes for the TSG model, that operate on a symbol-by-symbol basis, and study the problem of adaptively selecting a code from a given discrete family. By taking advantage of the structure of the optimum Huffman tree for a known TSG distribution, which enables simple calculation of the codeword of every given source symbol, an efficient adaptive strategy is derived.

We study the problem of memory-efficient scalable image compression and investigate some tradeoffs in the complexity versus coding efficiency space. The focus is on a low-complexity algorithm centered around the use of sub-bit-planes, scan-causal modeling, and a simplified arithmetic coder. This algorithm approaches the lowest possible memory usage for scalable wavelet-based image compression and demonstrates that the generation of a scalable bit-stream is not incompatible with a low-memory architecture.

LOGO-I (LOw COmplexity LOssless COmpression for Images) is the algorithm at the core of the new ISO/ITU standard for lossless and near-lossless compression of continuous-tone images, JPEG-LS. The algorithm was conceived as a "low complexity projection" of the universal context modeling paradigm, matching its modeling unit to a simple coding unit based on Golomb codes. The JPEG-LS standard evolved after successive refinements of the core algorithm, and a description of its design principles and main algorithmic components is presented in this paper. LOCO-I/JPEG-LS attains compression ratios similar or superior to those obtained with state-of-the-art schemes based on arithmetic coding. Moreover, it is within a few percentage points of the best available compression ratios, at a much lower complexity level.

We present a new low-complexity method for modeling and coding the bitplanes of a wavelet-transformed image in a fully embedded fashion. The scheme uses a simple ordering model for embedding, based on the principle that coefficient bits that are likely to reduce the distortion the most should be described first in the encoded bitstream. The ordering model is tied to a conditioning model in a way that deinterleaves the conditioned subsequences of coefficient bits, making them amenable to coding with a very simple, adaptive elementary Golomb (1966) code. The proposed scheme, without relying on zerotrees or arithmetic coding, attains PSNR vs. bit rate performance superior to that of SPIHT, and competitive with its arithmetic coding variant, SPIHT-AC.

Off-centered, two-sided geometric distributions of the integers are often encountered in lossless image compression applications, as probabilistic models for prediction residuals. Based on a recent characterization of the family of optimal prefix codes for these distributions, which is an extension of the Golomb (1966) codes, we investigate adaptive strategies for their symbol-by-symbol prefix coding, as opposed to arithmetic coding. Our strategies allow for adaptive coding of prediction residuals at very low complexity. They provide a theoretical framework for the heuristic approximations frequently used when modifying the Golomb code, originally designed for one-sided geometric distributions of non-negative integers, so as to apply to the encoding of any integer.

Most state-of-the-art lossless image compression schemes use prediction followed by some form of context modeling. This might seem redundant at first, as the contextual information used for prediction is also available for building the compression model, and a universal coder will eventually learn the "predictive" patterns of the data. In this correspondence, we provide a format justification to the combination of these two modeling tools, by showing that a combined scheme may result in faster convergence rate to the source entropy. This is achieved via a reduction in the model cost of universal coding. In deriving the main result, we develop the concept of sequential ranking, which can be seen as a generalization of sequential prediction, and we study its combinatorial and probabilistic properties.

LOCO-I (low complexity lossless compression for images) is a novel lossless compression algorithm for continuous-tone images which combines the simplicity of Huffman coding with the compression potential of context models, thus "enjoying the best of both worlds." The algorithm is based on a simple fixed context model, which approaches the capability of the more complex universal context modeling techniques for capturing high-order dependencies. The model is tuned for efficient performance in conjunction with a collection of (context-conditioned) Huffman codes, which is realized with an adaptive, symbol-wise, Golomb-Rice code. LOCO-I attains, in one pass, and without recourse to the higher complexity arithmetic coders, compression ratios similar or superior to those obtained with state-of-the-art schemes based on arithmetic coding. In fact, LOCO-I is being considered by the ISO committee as a replacement for the current lossless standard in low-complexity applications.

This paper elaborates on the use of discrete, two-sided geometric distribution models for image prediction residuals. After providing achievable bounds for universal coding of a rich family of models, which includes traditional image models, we present a new family of practical prefix codes for adaptive image compression. This family is optimal for two-sided geometric distributions and is an extension of the Golomb (1966) codes. Our new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the rough approximations used when a code designed for non-negative integers is matched to the encoding of any integer. We also provide adaptation criteria for a further simplified, sub-optimal family of codes used in practice.

Inspired by theoretical results on universal modeling, a general framework for sequential modeling of gray-scale images is proposed and applied to lossless compression. The model is based on stochastic complexity considerations and is implemented with a tree structure. It is efficiently estimated by a modification of the universal algorithm context. Several variants of the algorithm are described. The sequential, lossless compression schemes obtained when the context modeler is used with an arithmetic coder are tested with a representative set of gray-scale images. The compression ratios are compared with those obtained with state-of-the-art algorithms available in the literature, with the results of the comparison consistently favoring the proposed approach.

An irreducible parameterization for a finite memory source is constructed in the form of a tree machine. A universal information source for the set of finite memory sources is constructed by a predictive modification of an earlier studied algorithm-Context. It is shown that this universal source incorporates any minimal data-generating tree machine in an asymptotically optimal manner in the following sense: the negative logarithm of the probability it assigns to any long typical sequence, generated by any tree machine, approaches that assigned by the tree machine at the best possible rate.>

The problem of sequential probability assignment for individual sequences is investigated. The authors compare the probabilities assigned by any sequential scheme to the performance of the best "batch" scheme (model) in some class. For the class of finite-state schemes and other related families, they derive a deterministic performance bound, analogous to the classical (probabilistic) minimum description length (MDL) bound. It holds for "most" sequences, similarly to the probabilistic setting, where the bound holds for "most" sources in a class. It is shown that the bound can be attained both pointwise and sequentially for any model family in the reference class and without any prior knowledge of its order. This is achieved by a universal scheme based on a mixing approach. The bound and its sequential achievability establish a completely deterministic significance to the concept of predictive MDL.>

The authors propose a general model for a sequential coder, and investigate the associated coding delay. This model is employed to derive lower and upper bounds on the delay associated with commonly used encoders and decoders for noiseless data compression.>

An upper bound on the probability of a sequence drawn from a finite-state source is derived. The bound is given in terms of the number of phrases obtained by parsing the sequence according to the Lempel-Ziv (L-Z) incremental parsing rule, and is universal in the sense that it does not depend on the statistical parameters that characterize the source. This bound is used to derive an upper bound on the redundance of the L-Z universal data compression algorithm applied to finite-state sources, that depends on the length N of the sequence, on the number K of states of the source, and, eventually, on the source entropy. A variation of the L-Z algorithm is presented, and an upper bound on its redundancy is derived for finite-state sources. A method to derive tighter implicit upper bounds on the redundancy of both algorithms is also given, and it is shown that for the proposed variation this bound is smaller than for the original L-Z algorithm, or every value of N and K.>

The estimation and universal compression of discrete sources are considered, and a sequential algorithm for the universal coding of finite memory sources, attaining asymptotically minimum redundancy, is presented. The algorithm performs an online estimation of the source states and uses an arithmetic code.>

The authors consider the problem of ordering strings of a fixed length over a discrete alphabet according to decreasing probabilities of having been emitted by an unknown finite-state source. Data compression is applied to derive a universal algorithm that solves this problem with an optimal asymptotic performance. This result is employed in the solution of the following problem: discriminate an individual sequence as emitted by an independently identically distributed random source of equally likely symbols or as a signal corrupted by noise. Tight lower and upper bounds on the asymptotic performance of finite-state discriminators are given.>

The authors consider the problem of ordering of strings of a fixed length over a discrete alphabet, according to decreasing probabilities of having been emitted by an unknown finite-state source. Data compression is applied to derive a universal algorithm that solves this problem with an optimal asymptotic performance. The result is applied to discriminate an individual sequence as emitted by an i.i.d. random source or as a signal corrupted by noise. Tight lower and upper bounds on the asymptotic performance of finite-state discriminators are given.>

It is shown that $\mathrm{GF} ( q^n )$ has a self complementary normal basis over $\mathrm{GF} ( q )$ if and only if n is odd or $n \equiv 2(\bmod{\text{-}}4)$ and q is even. All existence proofs are constructive and can be readily employed to obtain such bases.