Iterative Algebraic SoftDecision List Decoding of Reed-Solomon codes (2010)
Mostafa El-khamy, Robert J. Mceliece
Abstract—In this paper, we present an iterative soft-decision decoding algorithm for Reed–Solomon (RS) codes offering both complexity and performance advantages over previously known decoding...
Performance of sphere decoding of block codes (2009)
El-Khamy, Mostafa, Vikalo, Haris, Hassibi, Babak, McEliece, Robert J.
A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance...
Random sensory networks: a delay in analysis (2009)
Florens, Cedric, Sharif, Masoud, McEliece, Robert J.
A fundamental function performed by a sensory network is the retrieval of data gathered collectively by sensor nodes. The metrics that measure the efficiency of this data collection process are time...
Iterative algebraic soft-decision list decoding of Reed-Solomon codes (2006)
El-Khamy, Mostafa, McEliece, Robert J.
In this paper, we present an iterative soft-decision decoding algorithm for Reed-Solomon (RS) codes offering both complexity and performance advantages over previously known decoding algorithms. Our...
Algebraic list decoding of Reed-Solomon product codes (2006)
Farzad Parvaresh, Mostafa El-khamy, Michael Stepanov, Daniel Augot, Robert J. Mceliece, Er Vardy
The product code of two Reed-Solomon codes can be regarded as an evaluation codes of bivariate polynomials, whose degrees in each variable are bounded. We propose to decode these codes with a...
The partition weight enumerator of MDS codes and its applications (2005)
El-Khamy, Mostafa, McEliece, Robert J.
A closed form formula of the partition weight enumerator of maximum distance separable (MDS) codes is derived for an arbitrary number of partitions. Using this result, some properties of MDS codes...
Iterative Algebraic Soft-Decision List Decoding of Reed-Solomon Codes (2005)
El-Khamy, Mostafa, McEliece, Robert J.
In this paper, we present an iterative soft-decision decoding algorithm for Reed-Solomon codes offering both complexity and performance advantages over previously known decoding algorithms. Our...
The Partition Weight Enumerator of MDS Codes and its Applications (2005)
El-Khamy, Mostafa, McEliece, Robert J.
A closed form formula of the partition weight enumerator of maximum distance separable (MDS) codes is derived for an arbitrary number of partitions. Using this result, some properties of MDS codes...
Performance enhancements for algebraic soft decision decoding of Reed-Solomon codes (2005)
El-Khamy, Mostafa, McEliece, Robert J., Harel, Jonathan
In an attempt to determine the ultimate capabilities of the Sudan-Guruswami-Sudan-Kotter-Vardy algebraic soft decision decoding algorithm for Reed-Solomon codes, we present a new method, based on the...
Reliable Communication in the Presence of Severe Noise or Jamming (2005)
It has been shown that the ultimate limits for some classes of multi- user communications systems can be computed by single linear programs. This theory can be applied to ordinary telephone networks...
Lower bounds on data collection time in sensory networks (2004)
Florens, Cédric, Franceschetti, Massimo, McEliece, Robert J.
Data collection, i.e., the aggregation at the user location of information gathered by sensor nodes, is a fundamental function of sensory networks. Indeed, most sensor network applications rely on...
Yokokawa, Takashi, Shinohara, Yuji, Miyauchi, Toshiyuki, Iida, Yasuhiro, McEliece, Robert J.
We present a method for designing high-rate, high-performance SCTCM systems with in-line interleavers. Using in-line EXIT charts and ML performance analysis, we develop criteria for choosing...
Lower bounds on data collection time in sensory networks (2004)
Cédric Florens, Student Member, Massimo Franceschetti, Robert J. Mceliece
Abstract—Data collection, i.e., the aggregation at the user location of information gathered by sensor nodes, is a fundamental function of sensory networks. Indeed, most sensor network applications...
Performance enhancements for algebraic soft-decision decoding of Reed-Solomon codes (2004)
Mostafa El-khamy, Robert J. Mceliece, Jonathan Harel
Abstract — In an attempt to determine the ultimate capabilities of the Sudan/Guruswami-Sudan/Kötter-Vardy algebraic soft decision decoding algorithm for Reed-Solomon codes, we present a new...
“The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point.” (C. Shannon, 1948) 1 APost-Internet Exegesis...
Coding theorems for turbo code ensembles (2002)
This paper is devoted to a Shannon-theoretic study of turbo codes. We prove that ensembles of parallel and serial turbo codes are "good" in the following sense. For a turbo code ensemble defined by a...
Belief propagation on partially ordered sets (2002)
Robert J. Mceliece, Muhammed Yildirimt
Abstract. In this paper, which is based on the important recent work of Yedidia, Freeman, and Weiss, we present a generalized form of belief propagation, viz. belie) e propagation on a partially...
Permutations preserving divisibility (2001)
McEliece, Robert J., Le Dantec, Claude, Piret, Philippe M.
We give a proof of a theorem on the common divisibility of polynomials and permuted polynomials (over GF(2)) by a polynomial g(x).
Are turbo-like codes effective on nonstandard channels (2001)
Turbo codes and their close relatives, e.g. Gallager and RA codes, have been shown to be extraordinarily effective on the ”standard”channel models, e.g. the binary erasure, binary symmetric, and...
The generalized distributive law (2000)
Aji, Srinivas M., McEliece, Robert J.
We discuss a general message passing algorithm, which we call the generalized distributive law (GDL). The GDL is a synthesis of the work of many authors in information theory, digital communications,...
Coding for Spread-Spectrum Channels in the Presence of Jamming. (1998)
The problem of reliable communication in the presence of extreme and unpredictable fading was studied using the techniques of broadcast coding. It was shown that for low signal-to-noise-ratios, the...
Coding for Spread-Spectrum Channels in the Presence of Jamming. (1998)
The research supported by this grant has led to a significantly improved mathematical understanding of the problems associated with communication in a hostile environment. The basic approach has been...
Coding for Spread-Spectrum Channels in the Presence of Jamming. (1998)
Multi-user communication systems have been studied. There are systems in which many simultaneous two-way conversations have common frequencies. The maximum number of such conversations can be...
Spectrum Allocation Strategies for Communication Networks. (1998)
Models of multi-user communications systems have been developed and studied. The limits for such systems have been computed by linear programming.
Subspace subcodes of Reed-Solomon codes (1998)
Hattori, Masayuki, McEliece, Robert J., Solomon, Gustave
We introduce a class of nonlinear cyclic error-correcting codes, which we call subspace subcodes of Reed-Solomon (SSRS) codes. An SSRS code is a subset of a parent Reed-Solomon (RS) code consisting...
Turbo decoding as an instance of Pearl's “belief propagation” algorithm (1998)
McEliece, Robert J., MacKay, David J. C., Cheng, Jung-Fu
We describe the close connection between the now celebrated iterative turbo decoding algorithm of Berrou et al. (1993) and an algorithm that has been well known in the artificial intelligence...
Iterative decoding on graphs with a single cycle (1998)
Aji, Srinivas M., Horn, Gavin B., McEliece, Robert J.
It is now understood that the turbo decoding algorithm is an instance of a probability propagation algorithm (PPA) on a graph with many cycles. In this paper we investigate the behavior of an PPA in...
Turbo decoding as an instance of Pearl’s belief propagation algorithm (1998)
Robert J. Mceliece, David J. C. Mackay, Jung-fu Cheng
Abstract—In this paper, we will describe the close connection between the now celebrated iterative turbo decoding algorithm of Berrou et al. and an algorithm that has been well known in the...
On the Convergence of Iterative Decoding on Graphs with a Single Cycle (1998)
Srinivas M. Aji, Gavin B. Horn, Robert J. Mceliece
It is now understood [7, 8] that the turbo decoding algorithm is an instance of a probability propagation algorithm (PPA) on a graph with many cycles. However, PPA-type algorithms are known to give...
Iterative Decoding on Graphs with a Single Cycle (1998)
Srinivas M. Aji, Gavin B. Horn, Robert J. Mceliece
It is now understood [2, 3] that the turbo decoding algorithm is an instance of a probability propagation algorithm (PPA) on a graph with many cycles. In this paper we investigate the behavior of an...
On the convergence of iterative decoding on graphs with a single cycle (1998)
Srinivas M. Aji, Gavin B. Horn, Robert J. Mceliece
Abstract- It is now understood [2, 31 that the turbo decoding algorithm is an instance of a prob-ability propagation algorithm (PPA) on a graph with many cycles. In this paper we investigate the...
A general algorithm for distributing information in a graph (1997)
Aji, Srinivas M., McEliece, Robert J.
We present a general “message-passing” algorithm for distributing information in a graph. This algorithm may help us to understand the approximate correctness of both the Gallager-Tanner-Wiberg...
Yu, Zhong, McEliece, Robert J.
In this paper we analyze the buffer occupancy in a statistical multiplexer in ATM networks for a special type of traffic, namely, periodic interchangeable (PI) traffic. Certain generalized Ballot...
Frequency-Efficient Coding with Low-Density Generator Matrices (1997)
Jung-fu Cheng, Robert J. Mceliece
In a recent paper, it is shown that if Pearl's belief propagation algorithm is applied to the Bayesian belief network of a turbo code, the turbo decoding algorithm immediately results. From this...
Belief Propagation in Loopy Bayesian Networks: Experimental Results (1997)
Gavin B. Horn, Robert J. Mceliece
We investigate the hypothesis that belief propagation "converges with high probability to the correct decision" on a broad class of loopy belief networks. Experimental results of belief...
Trellis decoding complexity of linear block codes (1996)
Kiely, Aaron B., Dolinar, Samuel J, Jr., McEliece, Robert J., Ekroot, Laura L., Lin, Wei
In this partially tutorial paper, we examine minimal trellis representations of linear block codes and analyze several measures of trellis complexity: maximum state and edge dimensions, total span...
The trellis complexity of convolutional codes (1996)
Convolutional codes have a natural, regular, trellis structure that facilitates the implementation of Viterbi's algorithm. Linear block codes also have a natural, though not in general a regular,...
On the BCJR trellis for linear block codes (1996)
In this semi-tutorial paper, we will investigate the computational complexity of an abstract version of the Viterbi algorithm on a trellis, and show that if the trellis has e edges, the complexity of...
Some High-Rate Near Capacity Codecs for the Gaussian Channel (1996)
Jung-fu Cheng, Robert J. Mceliece
We present a construction of high-rate linear error-correcting codes based on random bipartite graphs. In contrast to other researchers, our approach uses these graphs to produce generator matrices....
On the BCJR trellis for linear block codes (1996)
Abstruct- In this semi-tutorial paper, we will investigate the computational complexity of an abstract version of the Viterbi algorithm on a trellis, and show that if the trellis has e edges, the...
Unit-memory Hamming turbo codes (1995)
Cheng, Jung-Fu, McEliece, Robert J.
Several parallel concatenated coding schemes (turbo codes) based on multimemory (MM) convolutional codes (more specifically, a (2,1,4,7) code) were proposed to achieve near Shannon-limit error...
Unit-Memory Hamming Turbo Codes (1995)
Jung-fu Cheng, Robert J. Mceliece
this paper, new turbo codes based on the (8; 4; 3; 8) UM Hamming code [5] will be developed and shown to possess better performance potentials than the SI turbo (SIT) codes. 2 Encoder
Unit-memory Hamming turbo codes (1995)
Jung-fu Cheng, Robert J. Mceliece
Several parallel concatenated coding schemes (turbo codes) based on multi-memory (MM) convolutional codes (more specifically, a (2,1,4,7) code) were recently proposed to achieve near Shannon-limit...
Subspace subcodes of Reed-Solomon codes (1994)
Masayuki, Hattori, McEliece, Robert J., Lin, Wei
A subspace subcode of a Reed-Solomon (SSRS) code over GF(2m) is the set of RS code-words, whose components all lie in a particular GF(2)-subspace of GF(2m). SSRS codes include both generalized BCH...
Performance limits for channelized cellular telephone systems (1994)
McEliece, Robert J., Sivarajan, Kumar N.
Studies the performance of channel assignment algorithms for “channelized” (e.g., FDMA or TDMA) cellular telephone systems, via mathematical models, each of which is characterized by a pair...
Phased burst error-correcting array codes (1993)
Goodman, Rodney M., McEliece, Robert J., Sayano, Masahiro
Various aspects of single-phased burst-error-correcting array codes are explored. These codes are composed of two-dimensional arrays with row and column parities with a diagonally cyclic readout...
Performance of binary block codes at low signal-to-noise ratios (1992)
Chao, Chi-Chao, McEliece, Robert J., Swanson, Laif, Rodemich, Eugene R.
The performance of general binary block codes on an unquantized additive white Gaussian noise (AWGN) channel at low signal-to-noise ratios is considered. Expressions are derived for both the block...
IEEE Log Number 9215198. (1991)
Robert J. Mceliece, Kumar N. Sivarajan
Abstract-In this paper, we study the performance of channel a channel to be used simultaneously in several cells, under assignment algorithms for “channelized ” (e.g., FDMA or TDMA) cellular...
Pollara, Fabrizio, McEliece, Robert J., Abdel-Ghaffar, Khaled
A class of codes called finite-state (FS) codes is defined and investigated. The codes, which generalize both block and convolutional codes, are defined by their encoders, which are finite-state...
Two-dimensional burst identification codes and their use in burst correction (1988)
Abdel-Ghaffar, Khaled A. S., McEliece, Robert J., Van Tilborg, Henk C. A.
A new class of codes, called burst identification codes, is defined and studied. These codes can be used to determine the patterns of burst errors. Two-dimensional burst correcting codes can be...
On the capacity of channels with block memory (1988)
Stark, Wayne E., McEliece, Robert J.
The capacity of channels with block memory is investigated. It is shown that, when the problem is modeled as a game-theoretic problem, the optimum coding and noise distributions when block memory is...
The capacity of the Hopfield associative memory (1987)
McEliece, Robert J., Posner, Edward C., Rodemich, Eugene R., Venkatesh, Santosh S.
Techniques from coding theory are applied to study rigorously the capacity of the Hopfield associative memory. Such a memory stores n-tuple of ±1's. The components change depending on a hard-limited...
A Note on the Wide-Band Gaussian Broadcast Channel (1987)
McEliece, Robert J., Swanson, Laif
Recently, Posner noted that on a wide-band Gaussian broadcast channel, ordinary time-shared coding performs almost as well as more sophisticated broadcast coding strategies. In this note, we shall...
Submicron Systems Architecture: Semiannual Technical Report (1987)
Seitz, Charles L., Martin, Alain J., McEliece, Robert J., Rem, Martin
No abstract available.
On the existence of optimum cyclic burst-correcting codes (1986)
Abdel-Ghaffar, Khaled A. S., McEliece, Robert J., Odlyzko, Andrew M., Van Tilborg, Henk C. A.
It is shown that for each integer b >= 1 infinitely many optimum cyclic b-burst-correcting codes exist, i.e., codes whose length n, redundancy r, and burst-correcting capability b, satisfy n =...
On the decoder error probability for Reed-Solomon codes (1986)
McEliece, Robert J., Swanson, Laif
Upper bounds On the decoder error probability for Reed-Solomon codes are derived. By definition, "decoder error" occurs when the decoder finds a codeword other than the transitted codeword; this is...
An entropy maximization problem related to optical communication (1986)
McEliece, Robert J., Rodemich, Eugene R., Swanson, Laif
Motivated by a problem in optical communication, we consider the general problem of maximizing the entropy of a stationary random process that is subject to an average transition cost constraint....
Submicron Systems Architecture: Semiannual Technical Report (1986)
Seitz, Charles L., Kajiya, James T., Martin, Alain J., McEliece, Robert J., Rem, Martin
No abstract available.
Submicron Systems Architecture: Semiannual Technical Report (1986)
Seitz, Charles L., Kajiya, James T., Martin, Alain J., McEliece, Robert J., Rem, Martin
No abstract available.
L.: An entropy maximization problem related to optical communication (1986)
Robert J. Mceliece, Eugene R. Rodemich, Laif Swanson
i.e., an
Coding protection for magnetic tapes: A generalization of the Patel-Hong code (1985)
Blaum, Mario, McEliece, Robert J.
Patel and Hong have constructed a code that can correct any track error or two track erasures in a 9-track magnetic tape. Here the construction is extended to a code that can correct a track error...
Submicron Systems Architecture: Semiannual Technical Report (1985)
Seitz, Charles L., Kajiya, James T., Martin, Alain J., McEliece, Robert J., Rem, Martin, Van Tilborg, Henk
No abstract available.
Submicron Systems Architecture: Semiannual Technical Report (1985)
Seitz, Charles L., Kajiya, James T., Martin, Alain J., McEliece, Robert J., Rem, Martin
No abstract available.
Node Synchronization for the Viterbi Decoder (1984)
Lorden, Gary, McEliece, Robert J., Swanson, Laif
Motivated by the needs of NASA's Voyager 2 mission, in this paper we describe an algorithm which detects and corrects losses of node synchronization in convolutionally encoded data. This algorithm,...
Channels with block interference (1984)
McEliece, Robert J., Stark, Wayne E.
A new class of channel models with memory is presented in order to study various kinds of interference phenomena. It is shown, among other things, that when all other parameters are held fixed,...
Practical codes for photon communication (1981)
In a recent paper, Pierce studied the problems of communicating at optical frequencies using photon-counting techniques, and concluded that "at low temperatures we encounter insuperable problems of...
Asynchronous multiple-access channel capacity (1981)
Cover, Thomas M., McEliece, Robert J., Posner, Edward C.
The capacity region for the discrete memoryless multiple-access channel without time synchronization at the transmitters and receivers is shown to be the same as the known capacity region for the...
Symbol synchronization in convolutionally coded systems (1979)
Baumert, Leonard D., McEliece, Robert J., Van Tilborg, Henk C. A.
Alternate symbol inversion is sometimes applied to the output of convolutional encoders to guarantee sufficient richness of symbol transition for the receiver symbol synchronizer. A bound is given...
On the inherent intractability of certain coding problems (1978)
Berlekamp, Elwyn R., McEliece, Robert J., Van Tilborg, Henk C. A.
The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown. This strongly suggests, but does not...
There is no MacWilliams identity for convolutional codes (1977)
Shearer, James B., McEliece, Robert J.
An example is provided of two convolutional codes that have the same transmission gain but whose dual codes do not. This shows that no analog of the MacWilliams identity for block codes can exist...
McEliece, Robert J., Omura, Jim K.
The recent upper bounds on the minimum distance of binary codes given by McEliece, Rodemich, Rumsey, and Welch are shown to result in improved upper bounds on the block coding error exponent for...
New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities (1977)
McEliece, Robert J., Rodemich, Eugene R., Rumsey, Howard, Jr., Welch, Lloyd R.
With the Delsarte-MacWilliams inequalities as a starting point, an upper bound is obtained on the rate of a binary code as a function of its minimum distance. This upper bound is asymptotically less...
Incluye bibliografía e índice
A low-rate improvement on the Elias bound (1974)
Welch, Lloyd R., McEliece, Robert J., Rumsey, Howard, Jr.
An upper bound on the minimum distance of binary blocks codes, which is superior to Elias' bound for R < 0.0509^+, is obtained. The new bound has the same derivative(-infty) at R = 0 as Gilbert's...
In the above paper [1], Varshamov considers discrete channels with q inputs and q outputs, q being an arbitrary integer.
On the symmetry of good nonlinear codes (1970)
It is shown that there are arbitrarily long "good" (in the sense of Gilbert) binary block codes that are preserved under very large permutation groups. This result contrasts sharply with the...