An online fountain code is defined as a fountain code for which an optimal encoding strategy can be found efficiently given any instantaneous decoding state. This property is important for data distribution in practical networks. In this paper, we formalize the problem of online fountain code construction, and propose new online fountain codes that outperform known ones in having factor 3-5 lower redundancy overhead. The bounding of the code overhead is carried out using the analysis of the dynamics of random-graph processes.

Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns that satisfy certain subspace constraints. Although these designs correct external errors in recall, they assume neurons that compute noiselessly, in contrast to the highly variable neurons in brain regions thought to operate associatively, such as hippocampus and olfactory cortex. Here we consider associative memories with boundedly noisy internal computations and analytically characterize performance. As long as the internal noise level is below a specified threshold, the error probability in the recall phase can be made exceedingly small. More surprising, we show that internal noise improves the performance of the recall phase while the pattern retrieval capacity remains intact: the number of stored patterns does not reduce with noise (up to a threshold). Computational experiments lend additional support to our theoretical analysis. This work suggests a functional benefit to noisy neurons in biological neuronal networks.

Binary codes over 2D arrays are very useful in data storage, where each array column represents a storage device or unit that may suffer failure. In this paper, we propose a new framework for probabilistic construction of codes on 2D arrays. Instead of a pure combinatorial erasure model used in traditional array codes, we propose a mixed combinatorial-probabilistic model of limiting the number of column failures, and assuming a binary erasure channel in each failing column. For this model, we give code constructions and detailed analysis that allow sustaining a large number of column failures with graceful degradation in the fraction of erasures correctable in failing columns. Another advantage of the new framework is that it uses low-complexity iterative decoding. The key component in the analysis of the new codes is to analyze the decoding graphs induced by the failed columns, and infer the decoding performance as a function of the code design parameters, as well as the array size and failure parameters. A particularly interesting class of codes, called probabilistically maximum distance separable (MDS) array codes, gives fault-tolerance that is equivalent to traditional MDS array codes. The results also include a proof that the 2D codes outperform standard 1D low-density parity-check codes.

We consider the problem of neural association for a network of nonbinary neurons. Here, the task is to first memorize a set of patterns using a network of neurons whose states assume values from a finite number of integer levels. Later, the same network should be able to recall the previously memorized patterns from their noisy versions. Prior work in this area consider storing a finite number of purely random patterns, and have shown that the pattern retrieval capacities (maximum number of patterns that can be memorized) scale only linearly with the number of neurons in the network. In our formulation of the problem, we concentrate on exploiting redundancy and internal structure of the patterns to improve the pattern retrieval capacity. Our first result shows that if the given patterns have a suitable linear-algebraic structure, i.e., comprise a subspace of the set of all possible patterns, then the pattern retrieval capacity is exponential in terms of the number of neurons. The second result extends the previous finding to cases where the patterns have weak minor components, i.e., the smallest eigenvalues of the correlation matrix tend toward zero. We will use these minor components (or the basis vectors of the pattern null space) to increase both the pattern retrieval capacity and error correction capabilities. An iterative algorithm is proposed for the learning phase, and two simple algorithms are presented for the recall phase. Using analytical methods and simulations, we show that the proposed methods can tolerate a fair amount of errors in the input while being able to memorize an exponentially large number of patterns.

The task of a neural associative memory is to retrieve a set of previously memorized patterns from their noisy versions by using a network of neurons. Hence, an ideal network should be able to 1) gradually learn a set of patterns, 2) retrieve the correct pattern from noisy queries and 3) maximize the number of memorized patterns while maintaining the reliability in responding to queries. We show that by considering the inherent redundancy in the memorized patterns, one can obtain all the mentioned properties at once. This is in sharp contrast with the previous work that could only improve one or two aspects at the expense of the third. More specifically, we devise an iterative algorithm that learns the redundancy among the patterns. The resulting network has a retrieval capacity that is exponential in the size of the network. Lastly, by considering the local structures of the network, the asymptotic error correction performance can be made linear in the size of the network.

We propose a novel architecture to design a neural associative memory that is capable of learning a large number of patterns and recalling them later in presence of noise. It is based on dividing the neurons into local clusters and parallel plains, an architecture that is similar to the visual cortex of macaque brain. The common features of our proposed model with those of spatially-coupled codes enable us to show that the performance of such networks in eliminating noise is drastically better than the previous approaches while maintaining the ability of learning an exponentially large number of patterns. Previous work either failed in providing good performance during the recall phase or in offering large pattern retrieval (storage) capacities. We also present computational experiments that lend additional support to the theoretical analysis.

Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns. Although these designs correct external errors in recall, they assume neurons that compute noiselessly, in contrast to the highly variable neurons in hippocampus and olfactory cortex. Here we consider associative memories with noisy internal computations and analytically characterize performance. As long as the internal noise level is below a specified threshold, the error probability in the recall phase can be made exceedingly small. More surprisingly, we show that internal noise actually improves the performance of the recall phase. Computational experiments lend additional support to our theoretical analysis. This work suggests a functional benefit to noisy neurons in biological neuronal networks.

We introduce irregular product codes, a class of codes where each codeword is represented by a matrix and the entries in each row (column) of the matrix come from a component row (column) code. As opposed to standard product codes, we do not require that all component row codes nor all component column codes be the same. Relaxing this requirement can provide some additional attractive features such as allowing some regions of the codeword to be more error-resilient, providing a more refined spectrum of rates for finite lengths, and improved performance for some of these rates. We study these codes over erasure channels and prove that for any 0 <; ε <; 1, for many rate distributions on component row codes, there is a matching rate distribution on component column codes such that an irregular product code based on MDS codes with those rate distributions on the component codes has asymptotic rate 1 - ε and can decode on erasure channels having erasure probability <; ε (and having alphabet size equal to the alphabet size of the component MDS codes).

A wiretap protocol is a pair of randomized encoding and decoding functions such that knowledge of a bounded fraction of the encoding of a message reveals essentially no information about the message, while knowledge of the entire encoding reveals the message using the decoder. In this paper, the notion of efficiently invertible extractors is studied and it is shown that a wiretap protocol can be constructed from such an extractor. Then, invertible extractors for symbol-fixing, affine, and general sources are constructed and used to create wiretap protocols with asymptotically optimal trade-offs between their rate (ratio of the length of the message versus its encoding) and resilience (ratio of the observed positions of the encoding and the length of the encoding). The results are further applied to create wiretap protocols for challenging communication problems, such as active intruders who change portions of the encoding, network coding, and intruders observing arbitrary Boolean functions of the encoding.

In this paper, the second moment of the ripple size during the Luby transform (LT) decoding process is analyzed. Combined with a result by Karp et al. (2004) stating that the expectation of the ripple size is of the order ofk, our study gives bounds on the error probability of the LT decoder. Furthermore, an analytic expression for the variance of the ripple size up to terms of constant order is given, and the expression of Karp et al. for the expectation of the ripple size is refined up to terms of the order of 1/k. This provides a first step toward an analytic finite-length analysis of LT decoding.

Probabilistic construction of codes on two-dimensional arrays is proposed and analyzed. Instead of a pure combinatorial erasure model used in traditional array codes, we propose a mixed combinatorial-probabilistic model of limiting the number of column failures, with assuming a binary erasure channel in each failing column. In addition, motivated by practical applications, we maintain an array with a fixed number of columns, while allowing the column size to grow to infinity. As a result, we obtain a framework that allows developing powerful constructions and analysis techniques previously only applicable in the theory of iteratively decoded one-dimensional low-density parity-check codes. The new array-code ensembles are shown to approach the performance of traditional MDS codes, with a simple decoder that offers better scalability in the number of column failures.

Suppose that we have two users each of which has a k-dimensional vector over a field FQ. Their goal is to communicate their vectors to a common receiver. At the time of reception, the receiver is given side information consisting of some of the entries of the first vector, some entries of the second vector, and the knowledge that some other entries of the two vectors are equal. The task is to design encoders for the two users in such a way that the receiver is able to recover the two vectors when given the side information and some of the entries of the encoded vectors. We call this problem the simultaneous erasure Slepian-Wolf problem, and we provide an optimal solution to this problem using rank-metric codes, provided that the field size.

We consider the problem of neural association, which deals with the retrieval of a previously memorized pattern from its noisy version. The performance of various neural networks developed for this task may be judged in terms of their pattern retrieval capacities (the number of patterns that can be stored), and their error-correction (noise tolerance) capabilities. While significant progress has been made, most prior works in this area show poor performance with regard to pattern retrieval capacity and/or error correction. In this paper, we propose two new methods to significantly increase the pattern retrieval capacity of the Hopfield and Bidirectional Associative Memories (BAM). The main idea is to store patterns drawn from a family of low correlation sequences, similar to those used in Code Division Multiple Access (CDMA) communications, instead of storing purely random patterns as in prior works. These low correlation patterns can be obtained from random sequences by pre-coding the original sequences via simple operations that both real and artificial neurons are capable of accomplishing.

A fountain coding framework is proposed that endows receivers with the ability to monitor and control the decoding progress given the instantaneous network conditions. These online features allow an optimal recovery from losses manifested by adversarial or other not purely random processes. A uni-partite graph structure and accompanying algorithms are used to efficiently calculate optimal instantaneous degrees. Using analysis of random-graph processes, the average overhead of a simplified scheme is shown to be upper bounded by 0.236, significantly lower than any known on-line fountain scheme.

We consider the problem of neural association for a network of non-binary neurons. Here, the task is to recall a previously memorized pattern from its noisy version using a network of neurons whose states assume values from a finite number of non-negative integer levels. Prior works in this area consider storing a finite number of purely random patterns, and have shown that the pattern retrieval capacities (maximum number of patterns that can be memorized) scale only linearly with the number of neurons in the network. In our formulation of the problem, we consider storing patterns from a suitably chosen set of patterns, that are obtained by enforcing a set of simple constraints on the coordinates (such as those enforced in graph based codes). Such patterns may be generated from purely random information symbols by simple neural operations. Two simple neural update algorithms are presented, and it is shown that our proposed mechanisms result in a pattern retrieval capacity that is exponential in terms of the network size. Furthermore, using analytical results and simulations, we show that the suggested methods can tolerate a fair amount of errors in the input.

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.

This paper studies the stability of some reconstruction algorithms for compressed sensing in terms of the bit precision. Considering the fact that practical digital systems deal with discretized signals, we motivate the importance of the total number of accurate bits needed from the measurement outcomes in addition to the number of measurements. It is shown that if one uses a 2 k times n Vandermonde matrix with roots on the unit circle as the measurement matrix, O(lscr + k log n/k) bits of precision per measurement are sufficient to reconstruct a k-sparse signal x isin Ropfnwith dynamic range (i.e., the absolute ratio between the largest and the smallest nonzero coefficients) at most 2lscrwithin lscr bits of precision, hence identifying its correct support. Finally, we obtain an upper bound on the total number of required bits when the measurement matrix satisfies a restricted isometry property, which is in particular the case for random Fourier and Gaussian matrices. For very sparse signals, the upper bound on the number of required bits for Vandermonde matrices is shown to be better than this general upper bound.

A wiretap protocol is a pair of randomized encoding and decoding functions such that knowledge of a bounded fraction of the encoding of a message reveals essentially no information about the message, while knowledge of the entire encoding reveals the message using the decoder. In this paper we study the notion of efficiently invertible extractors and show that a wiretap protocol can be constructed from such an extractor. We will then construct invertible extractors for symbol-fixing, affine, and general sources and apply them to create wiretap protocols with asymptotically optimal trade-offs between their rate (ratio of the length of the message versus its encoding) and resilience (ratio of the observed positions of the encoding and the length of the encoding). We will then apply our results to create wiretap protocols for challenging communication problems, such as active intruders who change portions of the encoding, network coding, and intruders observing arbitrary boolean functions of the encoding.

In this paper, we introduce a class of decoding algorithms for binary Raptor codes used for transmission over q-ary channels, where q = 2m. The algorithms provide a tradeoff between complexity and decoding capability. Whereas the running time of the q-ary belief-propagation algorithms is m2mtimes that of its binary counterpart, in our case the complexity factor can be chosen between m and 2m, depending on the error-correction capability required. As such, the running time can be much better than the q-ary belief-propagation algorithm. The main idea behind our algorithm is to apply an appropriate set of GF(2)-linear forms of GF(q) to the Raptor code to obtain a set of binary codes which can be decoded independently in parallel. After a prescribed number of iterations, for each of the input symbols of the Raptor code and each of the linear forms an estimate is obtained on the probability that this linear form applied to the input symbol is zero. By gathering these probabilities and performing a maximum-likelihood decoding on a suitable code of very small blocklength, we are able to obtain a good estimate of the value of the input symbol. Simulations results are provided for a families of q-ary symmetric channels and non-symmetric channels which show the performance of our decoding algorithms.

We analyze the second moment of the ripple size during the LT decoding process and prove that the standard deviation of the ripple size for an LT-code with length k is of the order of radick. Together with a result by Karp et. al (2004) stating that the expectation of the ripple size is of the order of k, this gives bounds on the error probability of the LT decoder. We also give an analytic expression for the variance of the ripple size up to terms of constant order, and refine the expression of Karp et. al for the expectation of the ripple size up to terms of the order of 1/k, thus providing a first step towards an analytic finite-length analysis of LT decoding.

We present some simple information inequalities on binary sums of Bernoulli random variables that appear to be new. Consequences for information across binary input memoryless symmetric channels are also presented.

We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time of the algorithm is polynomial in the description of the polynomials and their degrees provided that the number of the polynomials is a constant.

In this paper, two fixed per-information symbol complexity lossless source coding algorithms are modified for estimation and incremental LT decoding over piecewise stationary memoryless channels (PSMC's) with a bounded number of abrupt changes in channel statistics. In particular, as a class of PSMC's, binary symmetric channels are considered with a crossover probability that changes a bounded number of times with no repetitions in the statistics. Simulation results are given which illustrate the benefits of using our algorithms, both in terms of probability of error and in terms of redundancy.

This talk describes the development of various versions of Raptor codes starting from the first one developed at the end of 2000 to the more advanced versions that are being used in many commercial systems today. We will focus on practical aspects and how these have pushed the theoretical frontiers. The talk will conclude with a view on future developments.

In this paper we propose a notion of EXIT functions for LT-codes and Raptor codes, and discuss some of their useful properties that can be used to design good codes. We will further use these results to derive interesting conclusions on ranks of random matrices. New expressions for the asymptotic ranks of certain classes of random binary matrices are derived and the results are compared to previously known bounds and results.

A Fountain code is a code of fixed dimension and a limitless block-length. This is a class of codes with many interesting properties and applications. In this talk I will introduce several classes of probabilistic Fountain codes, including LT-and Raptor codes, show tools for their design and analysis, and discuss how they are used today to solve various data transmission problems on heterogenous unreliable networks. I will also talk about the theory of these codes when transmission takes place over non-erasure channels, and low-complexity algorithms are used for their decoding.

Summary form only given. This paper presents an algorithm in a purely lossless text compression setting based on fountain codes and the Burrows-Wheeler transform (BWT). The scheme consists of five stages, each of which is briefly described in the paper. The algorithm offers encouraging compression rate performance for large files. A summary of the results of the proposed scheme and other compression schemes is provided

We present a new model for LT codes which simplifies the analysis of the error probability of decoding by belief propagation. For any given degree distribution, we provide the first rigorous expression for the limiting bit-error probability as the length of the code goes to infinity via recent results in random hypergraphs by Darling and Norris, Ann. Appl. Probab., 2005. For a code of finite length, we provide an algorithm for computing the probability of block-error of the decoder. This algorithm improves by a linear factor the algorithm of Karp, Luby, and Shokrollahi, Proc. of ISIT, 2004

We introduce "derandomized" versions of the tensor product and the zig-zag product, extending the ideas in the derandomized squaring operation of Rozenman and Vadhan. These enable us to obtain graphs with smaller degrees than those obtained using their non-derandomized counterparts, though at the cost of slightly worse expansion. In this paper we give bounds on these expansions (measured by their second eigenvalues), and also obtain an improved bound on the expansion of the derandomized square.

In this paper we describe some practical aspects of the design process of good Raptor codes for finite block lengths over arbitrary binary input symmetric channels. In particular we introduce a simple model for the finite-length convergence behavior of the iterative decoding algorithm based on density evolution, and propose a practical design procedure. We report simulation results for some example codes.

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the stability condition to the class of Raptor codes. This generalization gives a lower bound on the fraction of output nodes of degree 2 of a Raptor code if the error probability of the belief-propagation decoder converges to zero. Using information-theoretic arguments, we will show that if a sequence of output degree distributions is to achieve the capacity of the underlying channel, then the fraction of nodes of degree 2 in these degree distributions has to converge to a certain quantity depending on the channel. For the class of erasure channels this quantity is independent of the erasure probability of the channel, but for many other classes of BIMSCs, this fraction depends on the particular channel chosen. This result has implications on the "universality" of Raptor codes for classes other than the class of erasure channels, in a sense that will be made more precise in the paper. We will also investigate the performance of specific Raptor codes which are optimized using a more exact version of the Gaussian approximation technique.

LT-codes are a new class of codes introduced by Luby for the purpose of scalable and fault-tolerant distribution of data over computer networks. In this paper, we introduce Raptor codes, an extension of LT-codes with linear time encoding and decoding. We will exhibit a class of universal Raptor codes: for a given integer k and any real epsiv>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1+epsiv) is sufficient to recover the original k symbols with high probability. Each output symbol is generated using O(log(1/epsiv)) operations, and the original symbols are recovered from the collected ones with O(klog(1/epsiv)) operations. We will also introduce novel techniques for the analysis of the error probability of the decoder for finite length Raptor codes. Moreover, we will introduce and analyze systematic versions of Raptor codes, i.e., versions in which the first output elements of the coding system coincide with the original k elements

We show, using a probabilistic argument, that for any y with 01+y)

In this paper we extend the double verification algorithm of Luby and Mitzenmacher to the class of Raptor codes, analyze it, and design Raptor codes that perform very well with respect to this algorithm

We consider a simple network, where a source and destination node are connected with a line of erasure channels. It is well known that in order to achieve the min-cut capacity, the intermediate nodes are required to process the information. We propose coding schemes for this setting, and discuss each scheme in terms of complexity, delay, achievable rate, memory requirement, and adaptability to unknown channel parameters. We also briefly discuss how these schemes can be extended to more general networks

We show that the error probability for decoding interleaved Reed-Solomon Codes with the decoder found by Bleichenbacher et al. [1] is upper bounded by O(1/q), independently of η.

This paper investigates the use of algebraic-geometric codes for data transmission over a packet network, by comparing their encoding/decoding speeds to those of the ubiquitous Reed-Solomon Codes. We take advantage of the fact that AG codes allow the construction of longer codes over a given alphabet, which in turn means we can create an [n, k]-code over a smaller field in which the encoding/decoding algorithms run faster. We also obtain some probabilistic bounds on the overheads required for the codes we use.

This paper extends the construction and analysis of Raptor codes originally designed in A. Shokrollahi (2004) for the erasure channel to general symmetric channels. We explicitly calculate the asymptotic fraction of output nodes of degree one and two for capacity-achieving Raptor codes, and discuss techniques to optimize the output degree distribution.

This paper provides an efficient method for analyzing the error probability of the belief propagation (BP) decoder applied to LT Codes. Each output symbol is generated independently by sampling from a distribution and adding the input symbols corresponding to the support of the sampled vector.

This paper exhibits a class of universal Raptor codes: for a given integer k, and any real /spl epsiv/>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1 + /spl epsiv/) is sufficient to recover the original k symbols, with high probability. Each output symbol is generated using O(log(1//spl epsiv/)) operations, and the original symbols are recovered from the collected ones with O(klog(1//spl epsiv/)) operations.

Transmission of packets over computer networks is subject to packet-level errors, which appear as "bursts" of bit-level errors and are not well modeled by memoryless binary channels. A standard scrambling technique is used for transmission of packets by the q-ary symmetric channel (q-SC) with alphabet size q and error probability p. Furthermore, significant improvements in computational efficiency can be obtained by codes that operate at the packet-level instead of the bit-level. The capacity of the q-SC is 1+p log/sub q/ (p)+(1-p)log/sub q/ (1-p)-plog/sub q/ (1-q), which is close to 1-p for large q. First designed an efficient decoding algorithm for LDPC codes on the q-SC, and showed that it can afford rates arbitrarily close to 1-2p. We improve the analysis of this decoding algorithm to show that LDPC codes with the Tornado edge distribution, together with an erasure precode, can achieve rates e-close to capacity. We also extend this decoder into a family of decoding algorithms, which become progressively more powerful but also more complex. We show that in the limit, when the decoder is allowed to look infinitely deep into the decoding tree, it can achieve capacity without precoding. However computational requirements make this decoder impractical.

This paper proposes a universal variable-length lossless compression algorithm based on fountain codes. The compressor concatenates the Burrows-Wheeler block sorting transform (BWT) with a fountain encoder, together with the closed-loop iterative doping algorithm. The decompressor uses a belief propagation algorithm in conjunction with the iterative doping algorithm and the inverse BWT. Linear-time compression/decompression complexity and competitive performance with respect to state-of-the-art compression algorithms are achieved.

We describe an authentication scheme whose security is based on the hardness of finding roots of systems of sparse polynomial equations in many variables and of high degree. One of the new ideas is the use of many keys. In one authentication session, a small amount of information about only one of them, chosen randomly, is released; this may be useful in other situations as well. Although the practicality of this scheme has still to be investigated, we believe that the new ideas described here may be of independent interest.

This paper starts a systematic study of capacity-achieving (c.a.) sequences of low-density parity-check codes for the erasure channel. We introduce a class A of analytic functions and develop a procedure to obtain degree distributions for the codes. We show various properties of this class which help us to construct new distributions from old ones. We then study certain types of capacity-achieving sequences and introduce new measures for their optimality. For instance, it turns out that the right-regular sequence is c.a. in a much stronger sense than, e.g., the Tornado sequence. This also explains why numerical optimization techniques tend to favor graphs with only one degree of check nodes.

Multiple antennas can greatly increase the data rate and reliability of a wireless communication link in a fading environment. Their success, however, depends on the design of cedes that achieve these promises. It is well known that unitary matrices can be used to design differentially modulated space-time codes. These codes have a particularly efficient description if they form a finite group under matrix multiplication. We show how to compute the parameters of such groups crucial for their use as space-time codes, using only the character table of the group. Since character tables for many groups are known and tabulated, this method could be used to quickly test, for a given group, which of its irreducible representations can be used to design good unitary space-time codes. We demonstrate our method by computing the eigenvalues of all the irreducible representations of the special linear group SL/sub 2/(F/sub q/) over a finite prime field F/sub q/ of odd characteristic, and study in detail the performance of a particular eight-dimensional representation of SL/sub 2/(F/sub 17/).

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number /spl epsiv/ a family of linear codes of rate R which can be encoded in time proportional to ln(1//spl epsiv/) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+/spl epsiv/)Rn or more. The recovery algorithm also runs in time proportional to n ln(1//spl epsiv/). Our algorithms have been implemented and work well in practice; various implementation issues are discussed.

We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance.

We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the codes is based on the work of Richardson and Urbanke (see ibid., vol.47, no.2, p.599-618, 2000). Assuming that the underlying communication channel is symmetric, we prove that the probability densities at the message nodes of the graph possess a certain symmetry. Using this symmetry property we then show that, under the assumption of no cycles, the message densities always converge as the number of iterations tends to infinity. Furthermore, we prove a stability condition which implies an upper bound on the fraction of errors that a belief-propagation decoder can correct when applied to a code induced from a bipartite graph with a given degree distribution. Our codes are found by optimizing the degree structure of the underlying graphs. We develop several strategies to perform this optimization. We also present some simulation results for the codes found which show that the performance of the codes is very close to the asymptotic theoretical bounds.

Multiple antennas can greatly increase the data rate and reliability of a wireless communication link in a fading environment, but the practical success of using multiple antennas depends crucially on our ability to design high-rate space-time constellations with low encoding and decoding complexity. It has been shown that full transmitter diversity, where the constellation is a set of unitary matrices whose differences have nonzero determinant, is a desirable property for good performance. We use the powerful theory of fixed-point-free groups and their representations to design high-rate constellations with full diversity. Furthermore, we thereby classify all full-diversity constellations that form a group, for all rates and numbers of transmitter antennas. The group structure makes the constellations especially suitable for differential modulation and low-complexity decoding algorithms. The classification also reveals that the number of different group structures with full diversity is very limited when the number of transmitter antennas is large and odd. We, therefore, also consider extensions of the constellation designs to nongroups. We conclude by showing that many of our designed constellations perform excellently on both simulated and real wireless channels.

Many important problems in pure and applied mathematics and engineering can be reduced to linear algebra on dense structured matrices. The structure of these dense matrices is understood in the sense that their n2 entries can be "compressed" to a smaller number O(n) of parameters. Operating directly on these parameters allows one to design efficient fast algorithms for these matrices. One of the most prominent matrix problems is that of multiplying a (structured) matrix with a vector. Many fundamental algorithms like convolution, Fast Fourier Transform, Fast Cosine/Sine Transform, and polynomial and rational multipoint evaluation and interpolation can be interpreted as superfast multiplication of a vector by structured matrices (like Toeplitz, DFT, Vandermonde, Cauchy). In this paper, we introduce a novel and fairly general class of structured matrices, which we call confluent Cauchy- like matrices, that contains all the above classes as a special case, and we will des a confluent Cauchy-like matrix by a vector. This is precisely what has been done in this paper

We construct signal constellations for differential transmission with multiple basestation antennas. The signals are derived using the theory of fixed-point-free groups and are especially suitable for mobile cellular applications because they do not require the handset to have more than one antenna or to know the time-varying propagation environment. Yet we achieve full transmitter diversity and excellent performance gains over a single-antenna system.

Many applications of fast Fourier transforms (FFTs), such as computer tomography, geophysical signal processing, high-resolution imaging radars, and prediction filters, require high-precision output. An error analysis reveals that the usual method of fixed-point computation of FFTs of vectors of length 2/sup l/ leads to an average loss of l/2 bits of precision. This phenomenon, often referred to as computational noise, causes major problems for arithmetic units with limited precision which are often used for real-time applications. Several researchers have noted that calculation of FFTs with algebraic integers avoids computational noise entirely. We combine a new algorithm for approximating complex numbers by cyclotomic integers with Chinese remaindering strategies to give an efficient algorithm to compute b-bit precision FFTs of length L. More precisely, we approximate complex numbers by cyclotomic integers in Z[e(2/spl pi/i/2/sup n/)] whose coefficients, when expressed as polynomials in e(2/spl pi/i/2/sup n/), are bounded in absolute value by some integer M. For fixed n our algorithm runs in time O(log(M)), and produces an approximation with worst case error of O(1/M(2/sup n-2/-1)). We prove that this algorithm has optimal worst case error by proving a corresponding lower bound on the worst case error of any approximation algorithm for this task. The main tool for designing the algorithms is the use of the cyclotomic units, a subgroup of finite index in the unit group of the cyclotomic field. First implementations of our algorithms indicate that they are fast enough to be used for the design of low-cost high-speed/high-precision FFT chips.

Using methods originating in numerical analysis, we will develop a unified framework for derivation of efficient list decoding algorithms for algebraicgeometric codes.We will demonstrate our method by accelerating Sudan's list decoding algorithm for Reed-Solomon codes [22], its generalization to algebraic-geometric codes by Shokrollahi and Wasserman [21], and the recent improvement of Guruswami and Sudan [8] in the case of Reed-Solomon codes.The basic problem we attack in this paper is that of efficiently finding nonzero elements in the kernel of a structured matrix.The structure of such an n x n-matrix allows it to be "compressed" to an parameters for some (Y which is usually a constant in applications.The concept of structure is formalized using the displacement operator.The displacement operator allows to perform matrix op erations on the compressed version of the matrix.In particular, we can find a PLU-decomposition of the original matrix in time O(cun'), which is quadratic in n for constant (Y.We will derive appropriate displacement operators for matrices that occur in the context of list decoding, and apply our general algorithm to them.For example, we will obtain algorithms that use O(&) and O(n7/3!) operations over the base field for list decoding of Reed-Solomon codes and algebraic-geometric codes from certain plane curves, respectively, where e is the length of the list.Assuming that e is constant, this gives algorithms of running time O(n') and O(n7/s), which is the same as the running time of conventional decoding algorithms.We will also sketch methods lo parallelize our algorithms.

We generalize Sudan's (see J. Compl., vol.13, p.180-93, 1997) results for Reed-Solomon codes to the class of algebraic-geometric codes, designing algorithms for list decoding of algebraic geometric codes which can decode beyond the conventional error-correction bound (d-1)/2, d being the minimum distance of the code. Our main algorithm is based on an interpolation scheme and factorization of polynomials over algebraic function fields. For the latter problem we design a polynomial-time algorithm and show that the resulting overall list-decoding algorithm runs in polynomial time under some mild conditions. Several examples are included.

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a good bound on the fraction of errors that can be corrected. As the codes that Gallager builds are derived from regular graphs, we refer to them as regular codes. Following the general approach introduced in [7] for the design and analysis of erasure codes, we consider error-correcting codes based on random irregular bipartite graphs, which we call irregular codes. We introduce tools based on linear programming for designing linear time irregular codes with better error-correcting capabilities than possible with regular codes. For example, the decoding algorithm for the rate 1/2 regular codes of Gallager can provably correct up to 5.17% errors asymptotically, whereas we have found irregular codes for which our decoding algorithm can provably correct up to 6.27 % errors asymptotically. We include the results of simulations demonstrating the effectiveness of our codes on systems of reasonable size. 1

Generalizing the high-noise decoding methods of [1, 19] to the class of algebraic-geometric codes, we design the first polynomialtime algorithms to decode algebraic-geometric codes significantly beyond the conventional error-correction bound. Applying our results to codes obtained from curves with many rational points, we construct arbitrarily long, constant-rate linear codes over a fixed field F q such that a codeword is efficiently, non-uniquely reconstructible after a majority of its letters have been arbitrarily corrupted. We also construct codes such that a codeword is uniquely and efficiently reconstructible after a majority of its letters have been corrupted by noise which is random in a specified sense. We summarize our results in terms of bounds on asymptotic parameters, giving a new characterization of decoding beyond the error-correction bound. 1 Introduction Error-correcting codes, originally designed to accommodate reliable transmission of information through unreliable ...

The polynomial time algorithm of Lenstra, Lenstra, and Lovasz (1982) for factoring integer polynomials and variants thereof have been widely used to show that various computational problems in number theory have polynomial time solutions. Among them is the problem of factoring polynomials over algebraic number fields, which is used itself as a major subroutine for several other algorithms. Although a theoretical breakthrough, algorithms based on factorization of polynomials are notoriously slow and hard to implement, with running times ranging between O(n/sup 12/) and O(n/sup 18/) depending on which variant of the lattice basis reduction is used. Here, n is an upper bound for the maximum of the degrees and the bit-lengths of the coefficients of the polynomials involved. On the other hand, in many situations one does not need the full power of factorization, so one may ask whether there exist faster algorithms in these cases. In this paper we develop more efficient Monte Carlo algorithms to decide certain properties of roots of integer polynomials, without factoring them. Such problems arise, e.g., when solving systems of algebraic equations. Our methods applied to this situation thus give information about the solutions of such systems of equations.

Many applications of fast fourier transforms (FITs), such as computer-tomography, geophysical signal processing, high resohstion imaging radars, and prediction filters, require high precision output.The usual method of fixed point computation of FIT's of vectors of length 21 leads to an average loss of f/2 bits of precision.This phenomenon, often referredto as computationalnoise, causes major problems for arithmeticunits with limited precision which areoften used for real time applications.Severalresearchers have noted thatcalculation of ITT's with algebraic integersavoids computationalnoise entirely,see, e.g., [3].We will show thatcomplex numbers can be approximated accurately by cyclotomic integers, andcombine this idea with Chinese remainderingstmtegiesin the cyclotomic integersto, rotsgbly,give a O(b'" L log( L) ) algorithm to compute b-bit precision FIT's of length L. The firstpart of the paperwill describe the ~strategy,assuminggood approximationalgorithms;the second partpresentsanew, general,andefticient algorithmfor a~proximatingcomplex numbersby cyclotomic integersin Z[e2*'\2 ] whose coefficients, when expressedas polynomials in e'~ii'", are bounded in absolute value by some integer M. For fixed n our algorithm runs in time 0(log(A4)), and produces an approximation with worst case errorof 0(1/A42"-2'1).We will prove that this algorithm has optimal worst case emor by proving a correspondinglower bound on the worstcase errorof any approximationalgorithm for this task.Firstimplementationsof our algorithmsindicate thatthey are fast enough to be used for the design of low cost high speecfhigh precision FIT-chips.

Abstract | We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for these codes have fast and simple software implementations. Implementations of our algorithms are faster by orders of magnitude than the software implementations of previous algorithms. We expect these codes will be extremely useful for applications where lossy channels are common and fast decoding is a requirement, e.g., satellite transmission and multicast transmission over the Internet. I.

Using the results given in [D,. V. Chudnovsky and G. V Chudnovsky, Proc. Nat. Acad. Sci. USA, 84 (1987), pp. 1739-1743] and [W. C. Waterhouse, Ann. Sci. École Norm. Sup., 4 (1969), pp. 521–560], it is proven that the rank (= bilinear complexity of multiplication) of the finite field $\mathbb{F}_{q^n } $ viewed as an $\mathbb{F}_q $-algebra is $2n$ if n satisfies $\frac{1}{2}q+1< n <\frac{1}{2}(q+1+ \epsilon (q))$. Here $\epsilon (q)$ is the greatest integer $ \leq 2\sqrt q $ which is prime to q if q is not a perfect square and $\epsilon (q) = 2\sqrt q $ if q is a perfect square.