We consider the lattice-input discrete-time Poisson (LIDTP) channel, which is a discrete-time Poisson (DTP) channel where the input is constrained to a lattice$\alpha \mathbb{Z}^{\geq 0}$, for some fixed parameter$\alpha> 0$, and where$\mathbb{Z}^{\geq 0}$denotes the set of non-negative integers. The LIDTP channel arises in the analysis of some channel models proposed in the DNA storage literature, which motivated our study. We show that the difference in capacity between the LIDTP channel and the standard DTP channel is upper-bounded by$K(\alpha)+R(\mathcal{E})+o(1)$, where$\mathcal{E}$is a mean power constraint on the input and the asymptotics are with respect to the ratio$\mathcal{E} / \alpha$going to infinity. The terms$K(\alpha)$and$R(\mathcal{E})$are given explicitly and tend to 0 with$\alpha \rightarrow 0$and$\mathcal{E} \rightarrow \infty$, as$O\left(\alpha \log \frac{1}{\alpha}\right)$and$O\left(\mathcal{E}^{-1 / 2}\right)$, respectively. Thus, for fixed$\alpha$and$\mathcal{E} \rightarrow \infty$, the term$K(\alpha)$bounds the gap in capacity incurred by enforcing a regular discrete input, and, as$\alpha$gets ever smaller, the asymptotic capacity of the LIDTP with$\mathcal{E} \rightarrow \infty$matches that of the DTP. We also show a non-asymptotic bound on the difference between the capacities of the LIDTP and DTP channels, of the form$K(\alpha)+R^{\prime}(\mathcal{E})+\frac{1}{2} \log 2 \pi e$. The term$R^{\prime}(\mathcal{E})$is also given explicitly and vanishes as$O(1 / \mathcal{E})$when$\mathcal{E} \rightarrow \infty$.

MOTIVATION: Nanopore sequencing technologies are rapidly gaining popularity, in part, due to the massive amounts of genomic data they produce in short periods of time (up to 8.5 TB of data in <72 h). To reduce the costs of transmission and storage, efficient compression methods for this type of data are needed. RESULTS: We introduce RENANO, a reference-based lossless data compressor specifically tailored to FASTQ files generated with nanopore sequencing technologies. RENANO improves on its predecessor ENANO, currently the state of the art, by providing a more efficient base call sequence compression component. Two compression algorithms are introduced, corresponding to the following scenarios: (1) a reference genome is available without cost to both the compressor and the decompressor and (2) the reference genome is available only on the compressor side, and a compacted version of the reference is included in the compressed file. We compare the compression performance of RENANO against ENANO on several publicly available nanopore datasets. RENANO improves the base call sequences compression of ENANO by 39.8% in scenario (1), and by 33.5% in scenario (2), on average, over all the datasets. As for total file compression, the average improvements are 12.7% and 10.6%, respectively. We also show that RENANO consistently outperforms the recent general-purpose genomic compressor Genozip. AVAILABILITY AND IMPLEMENTATION: RENANO is freely available for download at: https://github.com/guilledufort/RENANO. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: The amount of genomic data generated globally is seeing explosive growth, leading to increasing needs for processing, storage and transmission resources, which motivates the development of efficient compression tools for these data. Work so far has focused mainly on the compression of data generated by short-read technologies. However, nanopore sequencing technologies are rapidly gaining popularity due to the advantages offered by the large increase in the average size of the produced reads, the reduction in their cost and the portability of the sequencing technology. We present ENANO (Encoder for NANOpore), a novel lossless compression algorithm especially designed for nanopore sequencing FASTQ files. RESULTS: The main focus of ENANO is on the compression of the quality scores, as they dominate the size of the compressed file. ENANO offers two modes, Maximum Compression and Fast (default), which trade-off compression efficiency and speed. We tested ENANO, the current state-of-the-art compressor SPRING and the general compressor pigz on several publicly available nanopore datasets. The results show that the proposed algorithm consistently achieves the best compression performance (in both modes) on every considered nanopore dataset, with an average improvement over pigz and SPRING of >24.7% and 6.3%, respectively. In addition, in terms of encoding and decoding speeds, ENANO is 2.9× and 1.7× times faster than SPRING, respectively, with memory consumption up to 0.2 GB. AVAILABILITY AND IMPLEMENTATION: ENANO is freely available for download at: https://github.com/guilledufort/EnanoFASTQ. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We study the maximum Markov model order that can be estimated for an (individual) input sequence x of length n over a finite alphabet of size α, for popular estimators of tree models, where the estimated order is determined by the depth of a context tree estimate, and in the special case of plain Markov models, where the tree is constrained to be perfect (with all leaves at the same depth). First, we consider penalized maximum likelihood estimators where a context tree T̂ is obtained by minimizing a cost of the form - log P̂τ(x) + f(n)|Sτ|, where P̂τ(x) is the ML of x under a model with context tree T, Sτis the set of leaves of T, and f(n) is an increasing (penalization) function of n (the popular BIC estimator is a special case with f(n) = α-1/2 log n). For plain Markov models, a simple argument yields a known upper bound k̅(n) = O(log n) on the maximum order that can be estimated for x, and we show that, in fact, this simple bound is not far from tight. For general context trees, we derive an asymptotic upper bound, n1/2-o(1), on the estimated depth, and we exhibit explicit input sequences that asymptotically attain the bound up to a multiplicative constant factor. We show that a similar upper bound applies also to MDL estimators based on the KT probability assignment and, moreover, the same example sequences asymptotically approach the upper bound also in this case.

This paper proposes lossless and near-lossless compression algorithms for multichannel biomedical signals. The algorithms are sequential and efficient, which makes them suitable for low-latency and low-power signal transmission applications. We make use of information theory and signal processing tools (such as universal coding, universal prediction, and fast online implementations of multivariate recursive least squares), combined with simple methods to exploit spatial as well as temporal redundancies typically present in biomedical signals. The algorithms are tested with publicly available electroencephalogram and electrocardiogram databases, surpassing in all cases the current state of the art in near-lossless and lossless compression ratios.

We study the maximum depth of context tree estimates, i.e., the maximum Markov order attainable by an estimated tree model given an (individual) input sequence of length n. We consider two classes of estimators: 1) Penalized maximum likelihood (PML) estimators where a context tree T̂ is obtained by minimizing a cost of the form - log P̂T(xn)+f(n)|S|, where P̂;T(xn) is the ML probability of the input sequence xnunder a tree model T, STis the set of states defined by T, and f(n) is an increasing (penalization) function of n (the popular BIC estimator corresponds to f(n) = α-1/2 log n where α is the size of the input alphabet). 2) MDL estimators based on the KT probability assignment. In each case we derive an asymptotic upper bound, n1/2+o(1), on the estimated depth, and we exhibit explicit input sequences that asymptotically attain the bound up to the term o(1) in the exponent.

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.

Suffix trees (ST) are useful in information-theoretic applications such as model order estimation and lossless source coding, which require access to occurrence counts of patterns of arbitrary length in an input string x. If the length of x, n, is large, the memory required to represent the ST may become a practical performance bottleneck. This can be alleviated, in cases where a nontrivial upper bound is known on the lengths of the patterns of interest, by using a truncated ST (TST). However, conventional TST implementations still require Ω(n) bits of memory, due to the need to store x. We describe a new TST representation that avoids this limitation by storing all the information necessary to reconstruct the TST edge labels in a string y that is often much shorter than x. We apply TSTs to the implementation of Markov order estimators, where an upper bound knon the estimated order is either imposed (for consistency, as in KT-based MDL estimators), or can be derived (as in the BIC estimator). The new representation allows for estimator implementations with sublinear space complexity in some cases of interest. In other cases we show, experimentally, that even when the new representation does not have an asymptotic advantage, it still achieves very significant memory savings in practice.

Optimal prefix codes are studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameterq, 0qqcannot be optimal for any other value ofq. This is in sharp contrast to the one-dimensional (1-D) case, where codes are optimal for positive-length intervals of the parameterq. Thus, in the 2-D case, it is infeasible to give a compact characterization of optimal codes for all values of the parameterq, as was done in the 1-D case. Instead, optimal codes are characterized for a discrete sequence of values ofqthat provides good coverage of the unit interval. Specifically, optimal prefix codes are described forq= 2-1/k(k≥ 1), covering the rangeq≥ [1/2], andq= 2-k(k> 1), covering the rangeq<; [1/2]. The described codes produce the expected reduction in redundancy with respect to the 1-D case, while maintaining low-complexity coding operations.

We define a g-ary antipodal matching to be a perfect matching in the bipartite graph with vertices corresponding to words of length ℓ over the integer alphabet Q = {0, 1, ..., q -1}, wherein the left and right vertices are those with respective component sums greater and smaller than ℓ(q -1)/2, and wherein two vertices are connected by an edge if one of the corresponding words dominates the other. We present two different constructions of efficiently computable g-ary antipodal matchings. We then show how such matchings can be used for encoding arbitrary data into n × n arrays over the alphabet Q all of whose row and column sums are at most n(q -1)/2. Such encoders might be useful for mitigating parasitic currents in a next generation memory technology based on crossbar arrays of resistive devices.

We study the maximal values estimated by commonly used Markov model order estimators on individual sequences. We start with penalized maximum likelihood (PML) estimators with cost functions of the form - log Pk(xn) + f (n)αk, where Pk(xn) is the ML probability of the input sequence xnunder a Markov model of order k, a is the size of the input alphabet, and f(n) is an increasing (penalization) function of n (the popular BIC estimator corresponds to f(n) = α - 1/2 log n). Comparison with a memoryless model yields a known upper bound k(n) on the maximum order that xncan estimate. We show that, under mild conditions on f that are satisfied by commonly used penalization functions, this simple bound is not far from tight, in the following sense: for sufficiently large n, and any knthat estimate order k; moreover, for all but a vanishing fraction of the values of n such that k = k̅(n), there are sequences xnthat estimate order k. We also study KT-based MDL Markov order estimators, and show that in this case, there are sequences xnthat estimate order n1/2-ϵ, which is much larger than the maximum log n/log α(l + o(1)) attainable by BIC, or the order o(log n) required for consistency of the KT estimator. In fact, for these sequences, limiting the allowed estimated order might incur in a significant asymptotic penalty in description length. All the results are constructive, and in each case we exhibit explicit sequences that attain the claimed estimated orders.

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 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 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 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 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.

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.

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.

In many applications, an uncompressed source stream is systematically encoded by a channel code (which ignores the source redundancy) for transmission over a discrete memoryless channel. The decoder knows the channel and the code but does not know the source statistics. This paper proposes several universal channel decoders that take advantage of the source redundancy without requiring prior knowledge of its statistics.

We study the classical problem of noisy constrained capacity in the case of the binary symmetric channel (BSC), namely, the capacity of a BSC whose input is a sequence from a constrained set. As stated in [4] "... while calculation of the noise-free capacity of constrained sequences is well known, the computation of the capacity of a constraint in the presence of noise ... has been an unsolved problem in the half-century since Shannon's landmark paper ...." We express the constrained capacity of a binary symmetric channel with (d, k)-constrained input as a limit of the top Lyapunov exponents of certain matrix random processes. We compute asymptotic approximations of the noisy constrained capacity for cases where the noise parameter epsiv is small. In particular, we show that when kles2d, the error term with respect to the constraint capacity is O(epsiv), whereas it is O(epsiv log epsiv) when k > 2d. In both cases, we compute the coefficient of the error term. We also extend previous results on the entropy of a hidden Markov process to higher-order finite memory processes.

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.

New lower bounds are presented on the second moment of the distance distribution of binary codes, in terms of the first moment of the distribution. These bounds are used to obtain upper bounds on the size of codes whose maximum distance is close to their minimum distance. It is then demonstrated how such bounds can be applied to bound from below the smallest attainable ratio between the maximum distance and the minimum distance of codes. Finally, counterparts of the bounds are derived for the special case of constant-weight codes.

Lossless compression is studied for pairs of independent integer-valued symbols emitted by a source with a geometric probability distribution of parameter q /spl isin/ (0,1). Optimal prefix codes are described for q = 1/2/sup k/ (k > 1) and q = 1/k/spl radic/2 (k > 0). The codes described differ from previously characterized cases related to the geometric distribution in that their corresponding trees are of unbounded width, and in that an infinite set of distinct optimal codes is required to cover any interval (0, /spl epsi/), /spl epsi/ > 0, of values of q.

Lossless compression is studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameter q, 0k(k > 1) and q = 1/knthroot2 (k > 0). These codes retain some of the low-complexity and low-latency advantage of symbol by symbol coding of geometric distributions, which is widely used in practice, while improving on the inherent redundancy of the approach. From a combinatorial standpoint, the codes described differ from previously characterized cases related to the geometric distribution in that their corresponding trees are of unbounded width, and in that an infinite set of distinct optimal codes is required to cover any interval (0,epsi), epsi > 0, of values of q

The universal type class of a sequence xnis defined, in analogy to the notion underlying the classical method of types. Two sequences of the same length are said to be of the same universal (LZ) type if and only if they yield the same dictionary (or, equivalently, parsing tree) in the incremental parsing of Ziv and Lempel (1978). It is shown that for any finite order k, the variational distance between the kth-order empirical probability distributions of two sequences of the same universal type vanishes as the sequence length tends to infinity. Consequently, for any k and any kth-order probability assignment, the difference between the normalized logarithms of the probabilities assigned to two sequences of the same universal type also vanishes asymptotically. The size of a universal type class is studied, and it is shown that its asymptotic behavior parallels that of the conventional counterpart, with the LZ78 code length playing the role of the empirical entropy. The number of universal types for sequences of length n is estimated, and shown to be of the form exp((1+o(1))gamman/logn) for a well characterized constant gamma. Algorithms for enumerating the sequences in a universal type class, and for drawing a sequence from the class with uniform probability are described. As an application, the problem of universal simulation of individual sequences is considered. A sequence drawn with uniform probability from the universal type class of xnis an optimal simulation of xnin a well defined mathematical sense

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

Lower bounds are presented on the second moment of the distance distribution of binary codes. These bounds are used to obtain upper bounds on the size of codes whose maximum distance is close to their minimum distance. It is shown how such results can be applied to bound from below the smallest attainable ratio between the maximum distance and the minimum distance of codes. Improved bounds are then provided for the special case of constant-weight codes

Steganography is the art of secret communication. Its purpose is to hide the presence of information, using, for example, images as covers. We experimentally investigate if stego-images, bearing a secret message, are statistically "natural." For this purpose, we use recent results on the statistics of natural images and investigate the effect of some popular steganography techniques. We found that these fundamental statistics of natural images are, in fact, generally altered by the hidden "nonnatural" information. Frequently, the change is consistently biased in a given direction. However, for the class of natural images considered, the change generally falls within the intrinsic variability of the statistics, and, thus, does not allow for reliable detection, unless knowledge of the data hiding process is taken into account. In the latter case, significant levels of detection are demonstrated.

We consider codes consisting of arrays over an alphabet F, in which certain intersecting subsets of n/spl times/m coordinates are required to form codewords of length n in prescribed codes over the alphabet F/sup m/. Two specific cases are studied. In the first case, referred to as a singly-intersecting coding scheme, the user data is mapped into n/spl times/(2m-1) arrays over an alphabet F, such that the n/spl times/m subarray that consists of the left (respectively, right) m columns forms a codeword of a prescribed code of length n over F/sup m/; in particular, the center column is shared by the left and right subarrays. Bounds are obtained on the achievable redundancy region of singly-intersecting coding schemes, and constructions are presented that approach-and sometimes meet-these bounds. It is shown that singly-intersecting coding schemes can be applied in a certain model of broadcast channels to guarantee reliable communication. The second setting, referred to as a fully-intersecting coding scheme, maps the user data into n/spl times/m/spl times/m three-dimensional arrays in which parallel n/spl times/m subarrays are all codewords of the same prescribed code over F/sup m/. Bounds and constructions are presented for these codes, with the analysis based on representing the n/spl times/m/spl times/m arrays as vectors over certain algebras on m/spl times/m matrices.

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.

In this paper the entropy rate of a binary hidden Markov process (HMP) defined by observing the output of a binary symmetric channel whose input is a first-order binary Markov process is studied. Despite the simplicity of the models involved, the characterization of this entropy is a long standing open problem. By presenting the probability of a sequence under the model as a product of random matrices, and show that the entropy rate sought is a top Lyapunov exponent of the product, which explains the difficulty in its explicit computation. The same product of random matrices to derive an explicit expression for a first order Taylor approximation of the entropy rate with respect to the parameter of the binary symmetric channel is applied. The accuracy of the approximation is validated against empirical simulation results and also extends the results to Renyi's entropy of any order.

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 this paper, the entropy rate of a hidden Markov process (HMP) is computed. The HMP entropy is expressed in terms of a measure Q, which solves an integral equation dependent on the parameters of the process. The measure is hard to extract from the equation in any explicit way. The study focuses on the regime where the channel parameter (noise) /spl epsiv/ is small.

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.

The problem of constructing three-dimensional, ntimesmtimesm arrays over GF(q) is studied, where each ntimesm subarray in one direction contains a codeword of a code Copf1over GF(qm), while each ntimesm subarray in the perpendicular direction contains a codeword of a code Copf2over GF(qm)

This work presents universal simulation of individual sequences based on the type class with uniform probability. Further the properties of universal (LZ) type class, including the number of such types, which is super-polynomial in the sequence length n is studied. This paper also discusses parsing tree and empirical entropy rate of random sequences.

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.

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.

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.

In a typical burst error correction application of a product code of n/sub v//spl times/n/sub h/ arrays, one uses an [n/sub h/, n/sub h/-r/sub h/] code C/sub h/ that detects corrupted rows, and an [n/sub v/, n/sub v/-r/sub v/] code C/sub v/ that is applied to the columns while regarding the detected corrupted rows as erasures. Although this conventional product code scheme offers very good error protection, it contains excessive redundancy, due to the fact that the code C/sub h/ provides the code C/sub v/ with information on many error patterns that exceed the correction capability of C/sub v/. A coding scheme is proposed in which this excess redundancy is eliminated, resulting in significant savings in the overall redundancy compared to the conventional case, while offering the same error protection. The redundancy of the proposed scheme is n/sub h/r/sub v/+r/sub h/(lnr/sub v/+O(1))+r/sub v/, where the parameters r/sub h/ and r/sub v/ are close in value to their counterparts in the conventional case, which has redundancy n/sub h/r/sub v/+n/sub v/r/sub h/-r/sub h/r/sub v/. In particular, when the codes C/sub h/ and C/sub v/ have the same rate and r/sub h//spl Lt/n/sub h/, the redundancy of the proposed scheme is close to one-half of that of the conventional product code counterpart. Variants of the scheme are presented for channels that are mostly bursty, and for channels with a combination of random errors and burst errors.

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.

We study codes over GF(q) that can correct t channel errors assuming the error values are known. This is a counterpart to the well-known problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so-called t-location correcting codes (t-LCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional error-correcting codes (ECCs). Based on the new metric, we present bounds on the parameters of t-LCCs that are counterparts to the classical Singleton, sphere packing and Gilbert-Varshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDS-Like) LCCs that attain the Singleton-type bound on the redundancy. We show that these optimal codes are generally much shorter than their erasure (or conventional ECC) analogs. The length n of any t-LCC that attains the Singleton-type bound for t>1 is bounded from above by t+O(/spl radic/(q)), compared to length q+1 which is attainable in the conventional ECC case. We show constructions of optimal t-LCCs for t/spl isin/{1, 2, n-2, n-1, n} that attain the asymptotic length upper bounds, and constructions for other values of t that are optimal, yet their lengths fall short of the upper bounds. The resulting asymptotic gap remains an open research problem. All the constructions presented can be efficiently decoded.

Explicit formulas are given for sets of p elements forming a self-complementary normal basis of GF(q/sup p/) over GF(q), where p is the characteristic of GF(q). Using these formulas, a straightforward construction of self-complementary bases for GF(q/sup alpha /) (where alpha =p/sup m/) over GF(q) is also presented.>

An architecture for a Reed-Solomon (RS) encoder is presented, consisting of r+1 systolic cells, where r is the redundancy of the code. The systolic encoder is systematic, does not contain any feedback or other global signals, its systolic cells are of low complexity, and it is easily reconfigurable for variable redundancy and changes in the choice of generator polynomial of the code. The encoding algorithm is based on the Cauchy representation of the generator matrix of the code. This architecture is suitable for very high-speed applications where global signals (such as the feedback line present in the traditional RS encoder design) and the need for global synchronization may pose restrictions on the achievable switching speed of the encoder.>

A combinatorial characterization of sets of integers $\{ r_0 ,r_1 , \cdots ,r_{n - 1} \} $, with $0\leqq r_i \leqq q^n - 2$, such that $\alpha ^{r_0 } ,\alpha ^{r_1 } , \cdots ,\alpha ^{r_{n - 1} } $ form a basis of $GF( q^n )$ over $GF ( q )$ for some $\alpha \in GF( {q^n } )$ is presented. This characterization is used to prove the following generalization of the normal basis theorem for finite fields of characteristic two: Let $\lambda_0 ,\lambda_1 , \cdots ,\lambda_{n - 1} $ be integers in the range $0\leqq \lambda_i < q$, with at most one $\lambda_i $ equal to zero.Then, there exists an element $\alpha \in GF( {q^n } )$ such that $\alpha ^{\lambda_0 } ,\alpha ^{\lambda_1 q} ,\alpha ^{\lambda_2 q^2 } , \cdots ,\alpha^{\lambda_{n - 1} q^{n - 1} } $ form a bais of $GF( q^n )$ over $GF( q )$. This result, which includes the normal basis theorem as a particular case when $\lambda_0 = \lambda_1 = \cdots = \lambda_{n - 1} = 1$, is proved for all choices of $\lambda_0 ,\lambda_1 , \cdots ,\lambda_{n - 1} $ satisfying the above conditions when n is odd, and for more restricted sets of values $\{ \lambda_i \}$ when n is even.

It is shown that every q-ary primitive Bose-Chaudhuri-Hocquenghen code of designed distance delta and sufficiently large length n contains a codeword c/sub 0/ of weight w=O( delta ) and degree deg(c/sub 0/)=o(n). Here, the standard asymptotic notation O( delta ) is used for a function f( delta ) bounded above by lambda delta for some constant lambda , and o(n) for a function h(n) such that lim/sub n/ to infinity h(n)/n=O. These so-called light and short codewords are used to describe encoding and decoding algorithms which run on sequential machines in time O( delta n), i.e., linear in n for fixed delta . For high-rate primitive BCH codes this is faster than the commonly used algorithms, which are nonlinear in n when run on sequential machines.>

(L, d)-universal sets are useful for exhaustively testing logic circuits with a large number of functional components, designed so that every functional component depends on at most d inputs. Randomized and deterministic constructions of (L, d)-universal test sets are presented, and lower and upper bounds on the optimal sizes of such sets are proven. It is also proven that the design of an optimal exhaustive test set for an arbitrary logic circuit is an NP-complete problem.>

It is shown that a cyclic codeCof lengthqover GF(q)is the maximum distance separable if and only if either1) qis a prime, in which caseCis equivalent, up to a coordinate permutation, to an extended Reed-Solomon code, or2) Cis a trivial code of dimensionk \in \{1, q - 1, q \}. Hence there exists a nontrivial cyclic extended Reed-Solomon code of lengthqover GF(q)if and only ifqis a prime.

An(n, k, d)linear code overF=GF(q)is said to be {\em maximum distance separable} (MDS) ifd = n - k + 1. It is shown that an(n, k, n - k + 1)generalized Reed-Solomon code such that2\leq k \leq n - \lfloor (q - 1)/2 \rfloor (k \neq 3 {\rm if} qis even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withkin the above range can be {\em uniquely} extended to a maximal MDS code of lengthq + 1, and that generalized Reed-Solomon codes of lengthq + 1and dimension2\leq k \leq \lfloor q/2 \rfloor + 2 (k \neq 3 {\rm if} qis even) do not have MDS extensions. Hence, in cases where the(q + 1, k)MDS code is essentially unique,(n, k)MDS codes withn > q + 1do not exist.

It is shown that the family ofq-ary generalized Reed-Solomon codes is identical to the family ofq-ary linear codes generated by matrices of the form[I|A], whereIis the identity matrix, andAis a generalized Cauchy matrix. Using Cauchy matrices, a construction is shown of maximal triangular arrays over GF(q), which are constant along diagonals in a Hankel matrix fashion, and with the property that every square subarray is a nonsingular matrix. By taking rectangular subarrays of the described triangles, it is possible to construct generator matrices[I|A]of maximum distance separable codes, whereAis a Hankel matrix. The parameters of the codes are(n,k,d), for1 \leq n \leq q+ 1, 1 \leq k \leq n, andd=n-k+1.

We find the minimum distances of the binary(113, 57), and ternary(37, 19), (61, 31), (71, 36), and(73, 37)quadratic residue codes and the corresponding extended codes. These distances are15, 10, 11, 17, and17, respectively, for the nonextended codes and are increased by one for the respective extended codes. We also characterize the minimum weight codewords for the(113, 57)binary code and its extended counterpart.

We present an efficient maximum likelihood decoding algorithm for the punctured binary Reed-Muller code of order(m - 3)and length2^{m} - 1, M \geq 3, and we give formulas for the weight distribution of coset leaders of such codes.

It is shown that a lower hound ofn^{3}or more on the straight-line complexity of a functionfover GF(2^{n})is also a lower bound on the network complexity offand, hence, on the product of run time and program size of Turing machines. It is further shown that most functions over a finite field are hard to compute and that for most hard functions there exists no approximation via an easy algorithm.

It is shown that every symmetric matrix A, with entries from a finite field F, can be factored over F into $A = BB'$, where the number of columns of B is bounded from below by either the rank $\rho (A)$ of A, or by $1 + \rho (A)$, depending on A and on the characteristic of F This result is applied to show that every finite extension $\Phi $ of a finite field F has a trace-orthogonal basis over F. Necessary and sufficient conditions for the existence of a trace-orthonormal basis are also given. All proofs are constructive, and can be utilized to formulate procedures for minimal factorization and basis construction.