The covering polynomial method is a generalization of error-trapping decoding and is a simple and effective way to decode cyclic codes. For cyclic codes of rate R0, equal to n/spl rho/+2V/spl radic/n/spl rho/+(1/2) log/sub /spl phi//(n//spl rho/)+O(1), where /spl phi/=(1+/spl radic/5)/2. For all codes correcting up to three errors, the number of covering polynomials is at least n/spl rho/+2/spl radic/n/spl rho/+O(log n); covering polynomial sets achieving this bound (and thus within O(log n) of the minimum) are presented in closed-form specifications for rates in the range 11/15/spl les/R<3/4.

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

This paper examines the performance gains achievable by adding interblock memory to, and altering the mapping of coded bits to symbols in, block-coded modulation systems. The channel noise considered is additive Gaussian, and the twin design goals are to maximize the asymptotic coding gain and to minimize the number of apparent nearest neighbors. In the case of the additive white Gaussian noise channel, these goals translate into the design of block codes of a given weighted or 'normalized' distance whose rate is as high as possible, and whose number of codewords at minimum normalized distance is low. The effect of designing codes for normalized distance rather than Hamming distance is to ease the problem of determining the best codes for given parameters in the cases of greatest interest, and many such best codes are given.

There are many situations in which a coding scheme is fixed for a given channel. The data processing theorem implies that the capacity of the composite channel cannot be higher than that of the original channel; usually, the capacity will be strictly lower. This paper examines the problem of how much capacity must be lost in the most common such situations. The various combinations of presence and absence of encoder and decoder, along with choice of encoder and decoder, are considered. The degree to which coding schemes can both deliver low error probability and maintain high capacity in the composite channel is examined.

Branch prediction is an important mechanism in modern microprocessor design. The focus of research in this area has been on designing new branch prediction schemes. In contrast, very few studies address the theoretical basis behind these prediction schemes. Knowing this theoretical basis helps us to evaluate how good a prediction scheme is and how much we can expect to improve its accuracy.In this paper, we apply techniques from data compression to establish a theoretical basis for branch prediction, and to illustrate alternatives for further improvement. To establish a theoretical basis, we first introduce a conceptual model to characterize each component in a branch prediction process. Then we show that current "two-level" or correlation based predictors are, in fact, simplifications of an optimal predictor in data compression, Prediction by Partial Matching (PPM).If the information provided to the predictor remains the same, it is unlikely that significant improvements can be expected (asymptotically) from two-level predictors, since PPM is optimal. However, there are a rich set of predictors available from data compression, several of which can still yield some improvement in cases where resources are limited. To illustrate this, we conduct trace-driven simulation running the Instruction Benchmark Suite and the SPEC CINT95 benchmarks. The results show that PPM can outperform a two-level predictor for modest sized branch target buffers.

We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>

A class of information-theoretic problems is introduced that deals with systems in which information is transmitted through a series of noisy channels with limited or no processing between channels. Some basic questions that arise in such systems are examined in detail. The effects of ordering of the channels on overall capacity and the characteristics that cause channels to have high capacity when cascaded with themselves are dealt with.>

Information set decoding is an algorithm for decoding any linear code. Expressions for the complexity of the procedure that are logarithmically exact for virtually all codes are presented. The expressions cover the cases of complete minimum distance decoding and bounded hard-decision decoding, as well as the important case of bounded soft-decision decoding. It is demonstrated that these results are vastly better than those for the trivial algorithms of searching through all codewords or through all syndromes, and are significantly better than those for any other general algorithm currently known. For codes over large symbol fields, the procedure tends towards a complexity that is subexponential in the symbol size.>

A central paradox of coding theory concerns the existence and construction of the best codes. Virtually every linear code is good, in the sense that it meets the Gilbert-Varshamov bound on distance versus redundancy. Despite the sophisticated constructions for codes derived over the years, however, no one has succeeded in demonstrating a constructive procedure that yields such codes over arbitrary symbol fields. Using the theory of Kolmogorov complexity, it is shown that this statement holds true in a rigorous mathematical sense: any linear code that is truly random, in the sense that there is no concise way of specifying the code, is good. Furthermore, random selection of a code that does contain some constructive pattern results, with probability bounded away from zero, in a code that does not meet the Gilbert-Varshamov bound regardless of the block length of the code. In contrast to the situation for linear codes, it is shown that there are effectively random nonlinear codes which have no guarantee on distance. In addition, it is shown that the techniques of Kolmogorov complexity can be used to derive typical properties of classes of codes in a novel way.>