One of the major challenges when applying (serial) universal source coding to 2-dimensional data, e.g., images, is to determine suitable context data. For this reason the concept of context mapping function (CMF) has been introduced. In this paper we discuss the foundation for CMF as well an off-line construction method via a combinatorial optimization method.

The problem of optimizing PPM with the help of different choices of estimators and their parameters for different subsets of nodes in the context tree is considered. Methods of such optimization for Markov chain and context tree models for individual files and over given sets of files are presented, and it is demonstrated that the extension from Markov chain models to context tree models is necessary to receive significant improvements of the compression ratio.

Summary form only given. State-of-the-art lossless image compression schemes use a prediction scheme, a context model and an arithmetic encoder. The discrepancy between the predicted value and the actual value is regarded to be double exponentially distributed. The BT/CARPscheme was considered in Weinberger et al. (1996) as a means to find limits in lossless image compression. The scheme uses the context-algorithm (Rissanen 1983) which is, in terms of redundancy, an asymptotically optimal tree-algorithm. Further, BT/CARP uses extended tree nodes which contain a linear prediction scheme and a model for the double exponentially distributed data (DE-data). The model parameters are estimated and from the corresponding distribution the symbol probability distribution can be calculated. The drawback of the parameter estimating technique is its poor performance for short sequences. In order to improve the BT/CARP-scheme we have exchanged the estimation techniques with probability assignment techniques: the CTW-algorithm (Williams et al. 1995) and our weighting method for DE-data. We conclude that the suggested probability assignment technique has a favorable effect on the compression performance when compared with the traditional estimation techniques. On a test-image set the assumed improvement was verified.

The choice of expressions for the coding probabilities in general, and the escape probability in particular, is of great importance in the family of prediction by partial matching (PPM) algorithms. We present a parameterized version of the escape probability estimator which, together with a "compactness" criterion, provides guidelines for the estimator design given a "representative" set of files. This parameterization also makes it possible to adapt the expression of the escape probability during one-pass coding. Finally, we present results for one such compression scheme that illustrates the usefulness of our approach.

In both open and private communication the participants face potential threats from a malicious enemy who has access to the communication channel and can insert messages (impersonation attack) or alter already transmitted messages (substitution attack). Authentication codes (A-codes) have been developed to provide protection against these threats. In this paper we introduce a new distance, called the authentication distance (A-distance), and show that an A-code can be described as a code for the A-distance. The A-distance is directly related to the probability P/sub S/ of success in a substitution attack. We show how to transform an error-correcting code into an A-code and vice versa. We further use these transformations to provide both upper and lower bounds on the size of the information to be authenticated, and study their asymptotic behavior. As examples of obtained results, we prove that the cardinality of the source state space grows exponentially with the number of keys provided P/sub S/>P/sub I/, we generalize the square-root bound given by Gilbert, MacWilliams, and Sloane in 1979, and we provide very efficient constructions using concatenated Reed-Solomon codes.

The frequently assumed "freshness" constraint on the source states in multiple authentication schemes is not necessary if one allows the encoding rule to change between subsequent transmissions. In the paper it is shown that the main existing lower bounds on the probabilities of successful attack on multiple authentication schemes also hold for this new setup. Furthermore, Stinson's (1988) bound for the substitution attack is strengthened.>

Various constructions of authentication codes using spaces related to the general linear group have been proposed and analyzed. In the paper the authors describe two new constructions of Cartesian authentication codes using symplectic spaces. This illustrates the feasibility of codes from spaces based on geometries of the other classical groups.>

The long standing question whether the free distance of fixed rate convolutional codes is as good as the Costello bound was almost solved by K.S. Zigangirov and J.L. Massey (1987). They proved that this is indeed the case for codes with long branch length and rates 2/c, c>or=5. It is shown that there exist fixed convolutional codes of rate 2/4 whose free distance d/sub free/ meets the Costello bound originally derived for time varying convolutional codes.>