Nowadays there are several classes of constrained codes intended for different applications. The following two large classes can be distinguished. The first class contains codes with local constraints; for example, the source data must be encoded by binary sequences containing no sub-words 00 and 111. The second class contains codes with global constraints; for example, the code-words must be binary sequences of certain even length where half of the symbols are zeros and half are ones. It is important to note that often the necessary codes must fulfill some requirements of both classes. In this paper we propose a general polynomial complexity method for constructing codes for both classes, as well as for combinations thereof. The proposed method uses the Cover enumerative code, but calculates all the parameters on the fly with polynomial complexity, unlike the known applications of that code which employ combinatorial formulae. The main idea of the paper is to use dynamic programming to perform calculations like: how many sequences with a given prefix and a given suffix length satisfying constraints exist. For the constraints under consideration, we do not need to know the entire prefix, but much less knowledge about the prefix is sufficient. That is, we only need a brief description of the prefix.

We consider the problem of constructing an unconditionally secure cipher for the case when the key length is less than the length of the encrypted message. (Unconditional security means that a computationally unbounded adversary cannot obtain information about the encrypted message without the key.) In this article, we propose data compression and randomisation techniques combined with entropically-secure encryption for the case when message statistics are known. The resulting cipher can be used for encryption in such a way that the key length does not depend on the entropy or the length of the encrypted message; instead, it is determined by the required security level.

Embedding hidden data is usually performed by introducing some distortions (errors) in cover objects. If the distortions exceed a certain bound, steganalysis can detect the presence of hidden data. So the problem is to embed as much data as possible and not exceed a permissible distortion level to ensure indetectability. We describe a general class of stegosystems that solves the problem by employing linear hash functions. The suggested stegosystems allow to transmit hidden information of the amount asymptotically close to the maximum possible under the given distortion.

Suppose there is a large file which should be transmitted (or stored) and there are several (say, m) admissible data-compressors. It seems natural to try all the compressors and then choose the best, i.e. the one that gives the shortest compressed file. Then transfer (or store) the index number of the best compressor (it requires [log m] bits) the compressed file. The only problem is the time, which essentially increases due to the need to compress the file m times (in order to find the best compressor). We propose a method that encodes the file with the optimal compressor, but uses a relatively small additional time: the ratio of this extra time and the total time of calculation can be limited by an arbitrary positive constant. A similar situation occurs when forecasting time series.Generally speaking, in many situations it may be necessary find the best data compressor (or predictor) out of a given set, which is often done by comparing them empirically. One of the goals of this work is to turn such a selection process into a part of the data compression method, automating and optimizing it.

In this article we show how the ideas of information theory help to analyze the evolution of processors. As the main tool we use the computer capacity which is close to the channel capacity considered by C.Shannon. It turned out that during the transition "from old to new" the manufacturers change the parameters that affect the computer capacity. It allows to predict the values of parameters for succeeding processors. As the main example we use the Intel processors due to their high popularity and the accessibility of detailed description of all the technical characteristics. In this article we describe the computer capacity, paying attention to its connection with the ideas and theories of information theory. Next we apply it to analysis and prediction of the processors evolution.

Nowadays data compressors are applied to many problems of text analysis, but many such applications are developed outside of the framework of mathematical statistics. In this paper we overcome this obstacle and show how several methods of classical mathematical statistics can be developed based on applications of the data compressors.

The problem of prediction consists in forecasting the conditional distribution of the next outcome given the past. Assume that the source generating the data is such that there is a stationary predictor whose error converges to zero (in a certain sense). The question is whether there is a universal predictor for all such sources, that is, a predictor whose error goes to zero if any of the sources that have this property is chosen to generate the data. This question is answered in the negative, contrasting a number of previously established positive results concerning related but smaller sets of processes.

The problem of filtering of finite-alphabet stationary ergodic time series is considered. A method for constructing a confidence set for the (unknown) signal is proposed, such that the resulting set has the following properties: First, it includes the unknown signal with probability γ, where γ is a parameter supplied to the filter. Second, the size of the confidence sets grows exponentially with the rate that is asymptotically equal to the conditional entropy of the signal given the data. Moreover, it is shown that this rate is optimal.

In this work, a method for statistical analysis of time series is proposed, which is used to obtain solutions to some classical problems of mathematical statistics under the only assumption that the process generating the data is stationary ergodic. Namely, three problems are considered: goodness-of-fit (or identity) testing, process classification, and the change point problem. For each of the problems a test is constructed that is asymptotically accurate for the case when the data is generated by stationary ergodic processes. The tests are based on empirical estimates of distributional distance.

An algorithm for enumeration and de-numeration of run-length-limited words (dklr-sequences) is proposed. The complexity of the algorithm does not exceed O(log3n log log n), where n is the length of word, whereas known methods have the complexity that is not less than c n, c > 0.

Perfectly secure steganographic systems have been recently described for a wide class of sources of covertexts. The speed of transmission of secret information for these stegosystems is proportional to the length of the covertext. In this work we show that there are sources of covertexts for which such stegosystems do not exist. The key observation is that if the set of possible covertexts has a maximal Kolmogorov complexity, then a high-speed perfect stegosystem has to have complexity of the same order.

We address the problem of online prediction for time series. We show that any universal code (or a universal data compressor) can be used as a basis for constructing asymptotically optimal methods for this problem for a certain class of stationary and ergodic processes.

We address the problem of nonparametric estimation of characteristics for stationary and ergodic time series. We consider finite-alphabet time series and the real-valued ones and the following problems: estimation of the (limiting) probability P(u0hellipus) for every s and each sequence u0hellip usof letters from the process alphabet (or estimation of the density p(x0,hellip, xs) for real-valued time series), so-called on-line prediction, where the conditional probability P(xt+1/x1x2hellipxt) (or the conditional density p(xt+1/x1x2hellipxt)) should be estimated (in the case where x1x2hellip xtis known), regression and classification (or so-called problems with side information). We show that any universal code (or a universal data compressor) can be used as a basis for constructing asymptotically optimal methods for the above problems.

We address three problems of statistical analysis of time series: goodness-of-fit (or identity) testing, process discrimination, and the change point problem. For each of the problems we construct a test that is asymptotically accurate for the case when the data is generated by stationary ergodic processes. All problems are solved in a similar way by using empirical estimates of the distributional distance between the processes.

The statistical structure of DNA-sequences is of a great interest to molecular biology, genetics and the theory of evolution (see Chen and others, GIW-99, 1999, Aktulga and others, EURASIP J. of Bioinformatics and Systems Biology, 2007, Li, Computers and Chemistry , 1997). One of the approaches is a sequence modeling using Markov processes of different orders, and further statistical estimation of their parameters (see Simons and others, JSPI , 2005). In this paper we use firstly the test for the serial independence from Ryabko, Astola (Stat. Methodology, 2006) to estimate the ldquomemoryrdquo (or connectivity) of genetic texts and secondly we apply the homogeneity test for solving the DNA-based problem connected to the phylogenetic system of various organisms.

The problem of predicting a sequence x1,x2,. . . generated by a discrete source with unknown statistics is considered. Each letter xt+1is predicted using the information on the word x1x2hellip xtonly. This problem is of great importance for data compression, because of its use to estimate probability distributions for PPM algorithms and other adaptive codes. On the other hand, such prediction is a classical problem which has received much attention. Its history can be traced back to Laplace. We address the problem where the sequence is generated by an independent and identically distributed (i.i.d.) source with some large (or even infinite) alphabet and suggest a class of new methods of prediction.

We propose a simple universal (that is, distribution- free) steganographic system in which covertexts with and without hidden texts are statistically indistinguishable. The stegosystem can be applied to any source generating i.i.d. covertexts with unknown distribution, and the hidden text is transmitted exactly, with zero probability of error. Sequences of covertexts with and without hidden information obey the same distribution (the stegosystem is perfectly secure). The proposed steganographic system has two important properties. First, the rate of transmission of hidden information approaches the Shannon entropy of the covertext source as the size of blocks used for hidden text encoding tends to infinity. Second, if the size of the alphabet of the covertext source and its minentropy tend to infinity then the number of bits of hidden text per letter of covertext tends to log(n!)/n where n is the (fixed) size of blocks used for hidden text encoding. Besides, the resource complexity of the proposed algorithms grows only polynomially.

We consider a stationary and ergodic source p generated symbols x1...xtfrom some finite set A and a null hypothesis H0that p is Markovian source with memory (or connectivity) not larger than m, (m ges 0). The alternative hypothesis H1is that the sequence is generated by a stationary and ergodic source, which differs from the source under H0. In particular, if m = 0 we have the null hypothesis H0that the sequence is generated by Bernoully source (or the hypothesis that x1...xtare independent). Some new tests which are based on universal codes and universal predictors, are suggested

This paper addresses the problem of signal compression, basing on the mathematical model, in which a set of all possible signals is considered as a function space with a metric /spl rho/. The main attention is focused on the minimization of the size of compressed representation, when function characteristics are not known precisely.

The problem of predicting a sequence generated by a discrete source with unknown statistics is considered. This problem is of great importance for data compression, because of its use to estimate probability distributions for PPM algorithms and other adaptive codes. This paper suggested a scheme of adaptive coding (and prediction) for a case where a source generates letters from an alphabet with unknown or infinite size. This scheme can be applied along with Laplace, Krichevsky and any other predictors. The general case of the prediction, which is based on such a grouping, is considered and the estimates of the redundancy are given.

For many adaptive codes the speed of coding depends substantially on the alphabet size. In this paper we suggest a method for speeding up codes based on the following main idea. Letters of the alphabet are put in order according to their probabilities (or frequencies of occurrence), and the letters with probabilities close to each others are grouped in subsets (as new super letters), which contain letters with small probabilities. Such a grouping can increase the redundancy of the code. The suggested algorithm is applied to block coding. In order to surmount the block coding problem we suggest applying the described method of grouping to the set of all possible blocks in such a way that the redundancy caused by grouping is relatively small whereas the size of new alphabet is much less than the number of the possible blocks.

This paper suggests a scheme of adaptive coding and prediction for a case where a source generates letters from an alphabet with unknown (and even infinite) size. This scheme can be applied along with any predictor; here we use the Laplace predictor as the main example. We consider a case of prediction for i.i.d. sources, but all results can be easily extended to Markov sources. The suggested scheme is described using the tree notation.

In this paper, we show that a universal code is used for randomness testing. In contrast to known methods, the suggested approach gives a possibility to make a test for randomness, basing on any lossless data compression method even if a distribution law of the codeword lengths is not known. Secondly, we describe two new tests, conceptually connected with universal codes

We consider coding infinite sequences of a finite alphabet. The source is defined as a set of sequences (combinatorial source). The problem is to minimize the worst asymptotic compression ratio between each sequence and its coding output among the sequences in the combinatorial source. Ryabko showed that the optimal value coincides with the Hausdorff dimension of the combinatorial source. This correspondence extends the previous work in that the input and output costs are expressed in terms of not lengths but generalized costs. The essential quantity turns out to be the Hausdorff dimension with respect to the measure associated with the input cost. We construct an asymptotically optimal coding procedure, and also show that no coding scheme can beat the lower bound.

A new algorithm of the block encoding that can be implemented in such a way that block of several letters is coded using almost the same number of operations as a usual code uses for one letter is suggested. The new algorithm is based on methods of grouping of alphabet letters suggested recently in B. Ryabko, J. Astola (2003), B. Ryabko, J. Rissanen (2003) which combines letters from a large alphabet into a small number of subsets without an essential increase of the code redundancy.

The problem of constructing a binary search tree for a set of binary words has wide applications in computer science, biology, mineralogy, etc. Shannon considered a similar statement in his optimal coding theorem. It is NP-complete to construct a tree of minimum cost; therefore, the problem arises of finding simple algorithms for constructing nearly optimal trees. We show that there is a simple algorithm for constructing search trees sufficiently close to the optimal tree on average. By means of this algorithm we prove that for the optimal tree the average number of bits to be checked is near to its natural lower bound, i.e., the binary logarithm of the number of given words: their difference is less than 1.04.

The problem of converting a sequence of symbols generated by a Bernoulli source into an unbiased random sequence is well-known in information theory. The proposed method is based on Elias' (1972) algorithm in which the sequence of symbols is divided into blocks of length N,N/spl ges/1. We suggest a new method of constructing an unbiased random sequence which uses O(Nlog/sup 2/N) bits of memory and takes O(log/sup 8/Nloglog(N)) bit operations per letter.

Homophonic coding, or homophonic substitution, is referred to as a technique that contributes to reliability of the secret key cipher systems. Its main goal is to convert the plaintext into a sequence of completely random (equiprobable and independent) code letters. In solving this problem three characteristics are to be considered: (i) redundancy, defined as the difference between the mean codeword length and the source entropy, (ii) an average number of random bits used in encoding, and (iii) complexity of the encoder and decoder, measured by memory size (in bits) and computation time (in bit operations). A class of homophonic codes is suggested for which both the redundancy and the average number of random bits can be made as small as required with nonexponential growth of memory size and roughly logarithmic growth of computation time.

The problem of coding low-entropy information sources is considered. Since the run-length code was offered about 50 years ago by Shannon, it is known that for such sources there exist coding methods much simpler than for sources of a general type. However, known coding methods of low-entropy sources do not reach the given redundancy. In this correspondence, a new method of coding low-entropy sources is offered. It permits a given redundancy r with almost the same encoder and decoder memory size as that obtained by Ryabko (see ibid., vol.40, p.96-9, 1994) for general methods, while encoding and decoding much faster.

The author considers the problem of source coding and investigates the cases of known and unknown statistics. The efficiency of the compression codes can be estimated by three characteristics: 1) the redundancy (r), defined as the maximal difference between the average codeword length and Shannon entropy in case the letters are generated by a Bernoulli source; 2) the size (in bits) of the encoder and the encoder programs (S) when implemented on a computer; and 3) the average time required for encoding and decoding of a single letter (T). He investigates S and T as a function of r when r/spl rarr/0. All known methods may be divided into two classes. The Ziv-Lempel codes and their variants fall under the first class, and the arithmetic code with the Lynch-Davisson code fall under the second one. The codes from the first class need exponential memory size S=0(exp(1/r)) for redundancy r when r/spl rarr/O. The methods from the second class have a small memory size but a low encoding speed: S=0(1/r/sup const/), T=0(log/sup const/(1/r) log log (1/r)). In this paper, the author presents a code that combines the merits of both classes; the memory size is small and the speed is high: S=0(1/r/sup const/),T=0(log/sup const/(1/r) log log (1/r)).>

There are two classes of data compression algorithms. One class has redundancy log log n+O(1), where n is the alphabet size, and an encoding time O(log/sup 2/ n), n to infinity . The other has redundancy O(1) and an encoding time O(n). A code is presented combining advantages of both classes of compression methods: its redundancy is O(1) and the encoding and decoding time is O(log/sup 2/ n) per letter, which is close to the lower bound O(log n).>

In the above paper^{1}Davisson and Leon-Garcia prove a result equating the minimax redundancy for universal codes to a channel capacity that is computable by standard techniques. They point out that the result had been developed earlier in unpublished work by Gallager. I would like to point out an alternative development of this result and to compare this work with that of Davisson and Leon-Garcia.