1710

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL 42, NO 6, NOVEMBER 1996

Expander Codes
Michael Sipser and Daniel A. Spielman
Abstract-Using expander graphs, we construct a new family of asymptotically good, linear error-correctingcodes. These codes have linear time sequential decoding algorithms and logarithmic time parallel decoding algorithms that use a linear number of processors. We present both randomized and explicit constructions of these codes. Experimental results demonstrate the good performance of the randomly chosen codes. Index Terms- Asymptotically good error-correcting code, linear-time, expander graph.

I. INTRODUCTION E PRESENT an asymptotically good family of linear error-correcting codes that can be decoded in linear time. As these codes are derived from expander graphs, we call them expander codes. Expander codes belong to the class of low-density parity-check codes introduced by Gallager [ 101. Gallager [lo] suggested using the adjacency matrix of a randomly chosen low-degree bipartite graph as the parity check matrix of an error-correcting code. He showed that such a code probably has a rate and minimum distance near the Gilbe&Varshamov bound. He also suggested a natural sequential algorithm for decoding these codes, although he was unable to demonstrate that it would correct a constant fraction of error. In our first construction, we replace Gallagers random graphs with very good expander graphs. In Section V-A, we analyze the natural sequential decoding algorithm in terms of the expansion of this graph, and show that it will remove a constant fraction of error froin a corrupted codeword. In Appendix I, we show that this algorithm succeeds only if the underlying graph is an expander. Zyablov and Pinsker [35] showed that, with high probability over thc choice of the graph, Gallagers codes could be decoded by circuits of size O(n1ogn) and logxithmic depth. In Section VB, we show that our expander codes can be decoded by slightly simpler circuits of similar complexity. Pippenger [27] pointed out that a proof of the correctness of our parallel decoding algorithm can be obtained from Kuznetsovs proof of correctness of a construction of fault-tolerant memories derived from Gallagers codes [17]. Unfortunately, we are unaware of explicit constructions of expander graphs that have the level of expansion needed for the arguments in Section V.
Manuscript received December 15, 1995; revised Apnl20, 1996 Ths work was supported in part by thc U S AE Forcc undcr Contract F49620-92-5-0125, by DAWA under Grant N00014-92-J-1799, and by the NSF under Grant 9212184CCR. The work of D. A Spielman was also supported in part by an NSF Postdoc and the Fannie and John Hertz Foundation. The authors are with the Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139 USA. Publisher Item Idenhfier S 0018-9448(96)07304-X.

However, a randomly chosen graph will have the required level of expansion with high probability. h Section VI, we construct asymptotically good expander codes that rely on graphs with less expansion. As explicit constructions of graphs with such expansion exist present explicit constructions of asymptotically good codes, along with a simple parallel algorithm that can remove a constant fraction of error from these codes. This algorithm can be implemented as a circuit of size O(n1ogn) and depth O(1og n), or simulated in linear time on a sequential machine. For the sake of accuracy, we begin this paper with a brief overview of a few important models of computation in which our algorithms can be seen to run in linear time. In Section 111, we recall the properties of expander graphs that we will need in this paper. We conclude with some advice to those who might implement these codes along with the results of some experiments that we performed to test the performance of expander codes derived from randomly chosen graphs. We are unaware of an algorithm that will encode our expander codes in less than O ( n 2 ) time (such a time bound is trivial for linear codes). However, our expander codes are an essential element of a construction of asymptotically good codes that can be both encoded and decoded in linear time

r311.
A. Terminology In this paper, we build linear codes over the alphabet (0, l} (although it is easy to generalize the constructions to larger fields). By a code of block length n and rate r , we mean a code in which the words have n symbols, of which r n are message symbols that may be freely chosen and the remaining (1- r ) n are determined by the choice of the message symbols. In particular, a linear code of block length n and rate r is a subspace of GF (2) of dimension r n . If a code has minimum relative distance a , then each pair of words in the code differs in at least cm symbols. When we say that an algorithm will correct an E fraction of error from the code C,we mean that the algorithm, on input a word w that differs from a word U E C in at most en, symbols, will output [Link] make no restrictions on the output of the algorithm n other input words.

n.

MODELS LINEAR M E OF n

The meaning of linear depends on the model of computation considered. In section, we provide a brief description of a few standard models of sequential CO under which our algorithms run in linear time. describe the circuit model, which we will use to analyze our parallel algorithms.

0018-9448/96$05 00 0 1996 IEEE

SIPSER AND SPIELMAN: EXPANDER CODES

1711

A. The Models We analyze the efficiency of algorithms by measuring their running time on a RAM (see [4]).A RAM has a central processor that can access data from a memory. This processor should have a few basic operations: addition, subtraction, read from memory, store to memory, branch if zero, branch if greater than zero, etc. Under the uniform cost model, each of these operations costs one unit of time. Thus the time used by an algorithm in the uniform cost model is just the number of these basic operations that the processor performs. In the logarithmic cost model, the cost of a basic step is proportional to the length of its argument. Thus the addition of two n-bit numbers takes time n, even if each fits within a register. Similarly, reading an n-bit word from memory stored at ain address whose description requires n bits will take time 2n. Our sequential decoding algorithms run quite naturally in line,ar time according to the uniform cost model: Decoding a word of length n requires O(n)-bit additions and O ( n ) mernory accesses. To make these algorithms run in linear time in tlhe logarithmic cost model, we need to add an additional layex to the code (see Section VII). This extra layer enables us tlo perform only O(n/logn) memory access, each of which retriieves O(1og n) bits. The Pointer Machine (also known as the Kolmogorov-Uspenski; machine) is a model of computation designed to capture the time complexity of algorithms, rather than the architecture of any particular computer. The input, output, and working environment of a Pointer Machine is a constantdegree directed graph. The CPU of the machine is a special node in the graph. At each time step, the CPU looks at the configuration of nodes of distance at most two from itself and, depending on their configuration, rearranges the edges between these nodes, possibly creating new edges or new nodes. The Kollmogorov-Uspenskii thesis [ 151 asserts that any reasonable model of computation can be simulated by a Pointer Machine with at most a constant factor difference in speed. For more information about pointer machines, we direct the interested realder to [ll], [15], [18], and [29]. Our sequential decoding algorithms naturally run in linear time on a Pointer Machine. To measure the efficiency of our parallel decoding algorithims, we will use the model of Boolean circuits (see [9] ant1 [28] for a more detailed description of this model). Each wire in one of these circuits carries a 0 or a 1. Each gate in the circuit has as input two wires, and outputs a Boolean function of its two inputs. Its output can be directed to as many wires as desired. We restrict ourselves to considering acyclic circuits-those in which the directed graph naturally associated with the circuit is acyclic. The inputs of the circuit enter and exit on wires. The size and depth of the circuit are the number of wires and the length of the longest path in the digraph of the circuit, respectively. This is a very restrictive model of parallel computation, and it captures many of the difficulties of implementing our algorithms in hardware (although it does ignore the space required to lay out a circuit). We describe the complexity of our parallel decoding algorithm in the circuit model to emphasize that it is efficient even in this restrictive model. We hope that someone implementing this algorithm will have access to more complex devices.

B. Precomputation

When we measure the efficiency of our decoding algorithms, we assume that some precomputation has occurred before decoding begins. This precomputation is independent of the word being decoded. The output of the precomputation is an object whose Size is linear in the codeword length. It should be considered an auxiliary input to the decoding algorithm. The purpose of the precomputation is to build a graph associated with the code as well as the check matrix of the code. This graph is the auxiliary input. On a Pointer Machine, the graph is provided to the machine as its input usually is. On a RAM, the graph should be provided in memory as collections of pointers. For a circuit, the graph is used to decide how the circuit should look. From the description of the codes, it will be obvious that the precomputation can be performed efficiently in polynomial time.
1 1 EXPANDER 1. GRAPHS

Expander graphs have been the focus of much study in theoretical computer science and combinatorics. An expander graph is a graph in which every set of vertices has an unusually large number of neighbors. Our constructions require graphs that expand by a constant factor, but which have only a linear number of edges. It is a remarkable fact that such graphs exist. In fact, a simple randomized process will produce one with high probability. Deterministic, polynomial-time constructions also exist. Let G = (V, E ) be a graph on n vertices. To describe the expansion properties of G, we say every set of at most m vertices expands by a factor of 6 if, for all sets S c V

JSJ m 5

+ l{y

: 3x E

S such that ( x , y) E E } > SISI.

In our constructions, we will make use of unbalanced bipartite expander graphs. That is, the vertices of the graph will be divided into two sets so that there are no edges between vertices in the same set. We call such a graph ( e , d)-regular if all the nodes in one set have degree e and all the nodes in the other have degree d. By counting edges, we find that the number of e-regular vertices must differ from the number of d-regular vertices by a factor of d / c . We will only consider the expansion of sets of vertices contained within one side of the graph. We call a graph a (e, d, E , 6 ) expander if it is a ( e , d)-regular graph in which every subset of at most an E fraction of the e-regular vertices expands by a factor of at least S. We will use families of ( e , d , E , 6) expanders in which e, d, t, and 6 remain constant as the number of vertices increases. It is well known that a randomly chosen ( e , d)-regular graph will probably be a good expander: Proposition 1: Let B be a randomly chosen (e, d)-regular bipartite graph between n e-regular vertices and ( c / d ) n dregular vertices. Then, for all 0 < a < 1,with high probability, all sets of an e-regular vertices in B have at least

neighbors, where H ( . ) is the binary entropy function.

1712

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL 42, NO. 6, NOVEMBER 1996

Pro05 See Appendix 11. U The most common way to prove that a particular graph is a good expander is to examine its second-largest eigenvalue. The largest eigenvalue of a k-regular graph is k. If the secondlargest eigenvalue is far from the first, then the graph is a good expander. The greatest possible separation between the firstand second-largest eigenvalues in a graph was achieved in explicit constructions by Margulis [21] and Lubotzky, Phillips, and Sarnak 1191. Theorem 2 (Lubotzky-Phillips-Sarnak, Margulis): For every pair of primes p , q congruent to 1 modulo 4 such that p is a quadratic residue modulo q, there is a ( p 1)-regular Cayley graph of PSL(2, Z / q Z ) with q(q2 - l ) / Z vertices such that the second-largest eigenvalue of the graph is at most 2&. One can show that a graph with the eigenvalue separation displayed by these graphs is a good expander by using results from [6], [13], and [33]. Other constructions that achieve a similar separation have since appeared ([81, [231, and [241). From the fact that these graphs are Cayley graphs, one can show that they have a simple representation. Proposition 3: Each graph described in Theorem 2 can be constructed in time polynomial in its number of vertices. Moreover, this polynomial-time computation can be used to construct a description of the graph of size logarithmic in the number of vertices in the graph. There is an algorithm that, given this description, will produce the labels of the neighbors of a node in the graph in time polynomial in the length of the labels (i.e., polylogarithmic in the number of vertices). In the remainder of this paper, we can ignore the fact that these graphs are Cayley graphs, and just concentrate on the relation between their degrees and second-largest eigenvalues. Unfortunately, these graphs are not unbalanced-bipartite. To obtain unbalanced-bipartite expander graphs from these graphs, we use their edge-vertex incidence graphs. From a d-regular graph G on n vertices, we derive a (2, d)-regular graph with d n / 2 vertices on one side and n vertices on the other. Dejinifion 4: Let G be a graph with edge set E and vertex set V. The edge-vertex incidence graph of G is the bipartite graph with vertex set E U V and edge set

Variables

constraint restricts

Fig 1. A constraint restricts the variables that are its neighbors.

cally good low-rate error-correcting codes that lie above the Zyablov bound (see [251 and [361).

IV.

THE CONSTRUCTION

To build an expander code, we begin with an unbalanced bipartite expander graph. Say that B is a ( c , d)-regular graph between sets of vertices of size n and ( c / d ) n ,and that d > e. We will identify each of the n nodes on the large side of the graph with one of the bits in a code of length n. We refer to these n bits as variables. Each of the ( c / d ) n vertices on the small side of the graph will be associated with a constraint on the variables. Each constraint will correspond to a set of linear restrictions on the d variables that are its neighbors (see Fig. 1). In particular, a constraint will require that the variables it restricts form a codeword in some linear code of length d. Because the restrictions we impose upon the variables are linear, the resulting expander code will be linear as well. It is convenient to let all the constraints impose isomorphic codes (on different variables, of course). We will construct asymptotically good families of codes from families of ( e , d)regular expander graphs in which e and d remain constant as { ( e , U) E E x V : w is an endpoint of e}. their number of vertices increases. Definition 6: Let B be a (e, d)-regular graph between a To understand the expansion of these edge-vertex incidence set of n nodes {q, . . , wn}, called variables, and a set of . graphs, we use a lemma of Alon and Chung [2]. c n / d nodes {Cl, . . . , Ccn/d},called constraints. Let b ( i , j ) Lemma 5 (Alon-Chung): Let G be a d-regular graph on n be a function designed so that, for each constraint C,, the vertices with second-largest eigenvalue A. Let X be a subset 1), , w b ( % , d ) .Let S be an of the vertices of G of size y n . Then, the number of edges variables neighboring C, are wb(%, error-correcting code of block length d. The expander code contained in the subgraph induced by X in G is at most C(B, ) is the code of block length n whose codewords S are the words ( 2 1 , ... , 2 , ) such that, for 1 5 z 5 e n / & (qZ, , q(,,is a codeword of S. 1), . . . d)) If B is a sufficiently good expanderahd if the constraints We could use this lemma to characterize the edge-vertex are identified with sufficiently good codes, then the resulting incidence graphs of the graphs constructed in Theorem 2 as expander code will be a good code. (2, d , t, 6 expanders for some E and S. However, we will find ) Theorem 7 Let B be a ( c , d, a , c / d E ) expander and S an : it more convenient to work directly with Lemma 5. error-co-rrecting code of block length d, rate T > ( e - l)/c, We note that Alon et al. [ l ] used expander graphs in a and minimum relative distance c. Then C(B, ) has rate at S different way to obtain a uniform construction of asymptoti- least CT - ( e - 1) and minimum relative distance at least a.

SIPSER AND SPIELMAN: EXPANDER CODES

1713

Pro08 To obtain the bound on the rate of the code, we will count the number of linear restrictions imposed by the constraints. As each constraint imposes (1 - r ) d linear restrictions, the variables suffer at most
n - (1 - T ) d = cn(1d
C
T)

these simple codes, we must use a randomized construction of expanders as explained in Section I11 and Appendix 11.

A. Sequential Decoding

There is a natural algorithm for decoding these simple expander codes. We say that a constraint is satis-ed by linear restrictions, which implies that they have at least n(cr - a setting of variables if the sum of the variables in the (e - 1)) degrees of freedom. To prove the bound on the constraint is even; otherwise, the constraint is unsatis-ed. minimum distance, we will show that there can be no nonzero Consider what happens when we flip' a variable that is in codeword of weight an or less. Let w be a nonzero word of more unsatisfied than satisfied constraints. The unsatisfied weight at most an and let V be the set of variables that are 1 constraints containing the variable become satisfied, and vice in this word. There are c(VI edges leaving the variables in V. versa. Thus we have decreased the total number of unsatisfied The expansion property of the graph implies that these edges constraints. The goal of the sequential decoding algorithm is will enter more than (c/dt)lVI constraints. Thus the average to keep doing this until no unsatisfied constraint remains, in number of edges per constraint will be less than de, so there which case it outputs a codeword. Theorem 10 says that if must be some constraint that is a neighbor of V, but which the graph used to define the code is a good expander and if has a number of neighbors in V that is less than the minimum the input to the algorithm is close to a codeword, then the distance of S . This implies that w cannot induce a codeword of algorithm will succeed. S in that constraint; so, w cannot be a codeword in C(B, S).O Simple Sequential Decoding Algorithm: The analysis of our decoding algorithms for these codes will be extensions of this proof. To ease the presentation of our If there is a variable that is in more unsatisfied than arguments, we say that a constraint C, is satisfied by a word satisfied constraints, then flip the value of that (q. , xn) if (q(,,. . , X b ( , , d ) ) is a codeword of S . .. 1), . variable. Remark 8: A construction of codes defined by identifying Repeat until no such variable remains. the nodes on one side of a bipartite graph with the bits of the code and identifying the nodes on the other side with It is easy to implement this algorithm so that it runs in linear constraints first appeared in the work of Tanner 1321. Following time on a Pointer Machine or a RAM under the uniform cost Gallager's lead [lo], Tanner analyzed the performance of his model. In Fig. 2, we present one such way of implementing codes by examining the girth of the bipartite graph. Margulis this algorithm. A discussion of how algorithms such as this [201 also used high-girth graphs to construct error-correcting one can be modified to run in linear time on a RAM in the codes. It seems that analysis resting on high girth is insufficient logarithmic cost model appears in Section VII. to demonstrate that families of codes are asymptotically good. Lemma 9: For c and d constant, the implementation in Fig. 2 runs in linear time on a Pointer Machine, as well as V. A SIMPLEEXAMPLE on a RAM in the uniform cost model. Proof: We assume that the graph has been provided to A simple example of expander codes is obtained by letting B be a graph with expansion greater than c/2 on sets of size the algorithm as a collection of pointers in which each vertex at most an and letting P be the-eode consisting of words of indexes a list of pointers to its neighbors. The implementation runs in two phases: a setup phase that requires linear time, and even weight, i.e., those (XI,. . . , zd) E (0, l}dsuch that then a loop that takes constant time per iteration. z, = 0 modulo 2. During the setup phase, the variables are partitioned into sets by the number of unsatisfied constraints in which they The parity-check matrix of the resulting code, C(B, P ) , is just appear. It is trivial to perform this operation in linear time the adjacency matrix of B. The code P has rate ( d - l ) / d and on a RAM in the uniform cost model. A Pointer Machine can minimum relative distance 2 / d , so C(B, P) has rate 1 - c/d perform this operation in linear time because its input contains and minimum relative distance at least a. the graph between the variables and the constraints; thus it can To obtain a code that we can decode efficiently, we will find the neighbors of a variable in constant time, rather than need even greater expansion. With greater expansion, small the logarithmic time that would be required to access arbitrary sets of corrupt variables will induce noncodewords in many nodes in the graph. constraints. By examining these unsatisfied constraints, we will During normal iteration of the loop, a variable that appears be able to determine which variables are corrupt. In Sections in the greatest number of unsatisfied constraints is flipped; V-A and V-B, we will explain how to decode these simple the status of each constraint that contains that variable is expander codes. updated: and each variable that appears in each of those Unfortunately, we do not know of explicit constructions of constraints is moved to the set that reflects its new number expander graphs with expansion greater than c/2 (Kahale [13] of unsatisfied constraints. These operations can be performed shows that graphs with the eigenvalue separation achieved in in constant time because only a constant number of pieces of Theorem 2 have such expansion, but that eigenvalue separation 'If the variable was 0, make it 1. If it was 1, make it 0. cannot certify greater expansion). Thus in order to construct

1714

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL 42, NO. 6, NOVEMBER 1996

Input: a (c,d)-re@ar graph B between variables and constraints, and

an assignment o values to the variables. f

Set-up phase
For each constraint, determine whether or not it is satisfied by the variables.
Initialize sets So, , . .,S, to empty sets. For each variable, count the number of unsatisfied constraints in which it appears. If this number is i, then put the variable in set S . ,

Loop
Until sets Srcpl,. . . ,S are empty do: , Find the greatest i such that Flip the value of variable v For each constraint C that contains variable v Update the status of constraint C For each variable w in constraint C Recompute the number of unsatisfied constraints in which w appears. Move w to the set indexed by this number.

I
empty

S,is not Choose a variable v from set S,

If all variables are in set So, then outppt the values of the variables.
Otherwise, report failed to decode. ~-

Fig. 2. An implernentation or the simple sequential decoding algoiithm.

data are affected, and the constant number of pointers that are referenced are all linked in the graph. If, at some point, there is no variable in more unsatisfied than satisfied constraints, the implementation leaves the loop and checks whether it has successfully decoded its input. If all the variables are in the $et 50,then there are no unsatisfied constraints and the implementation will output a codeword. To see that the loop will only be executed a linear number of times, observe that the number of unsatisfied constraints decreases with each iteration. As there are only a linear number of constiaints, this decrease can only occur a linear numbel of times. Note that this i s true regardless of the expansion properties of the underlying graph. 0 Theorem 10: Let B be a ( e , d , a , 3 ~ 1 4 ) expander. Let P be the code consisting of all even-weight words of length d. Then, the simple sequential decoding algorithm will correct an a12 fraction of error from the code C(B, P). Prouf: When the algorithm is provided with a word that is within distance an12 of a codeword, we call corrupt the variables in which the word differs from that codeword. We say that the decoding algorithm is in state (w, U ) if w variables are corrupt and U constraints are unsatisfied. We view U as a potential associated with w. Our goal is to show that the potential will eventually reach zero. We will show that if the decoding algorithm begins with a word with at most an12 corrupt variables, then there will always be some variable with more unsatisfied neighbors than satisfied neighbors, until no corrupt variables remain. First, we consider what happens when the algorithm is in a state (w, U ) with w 5 an. Let s be the number of satisfied neighbors of the corrupt variables. By the expansion of the

graph, we know that

U

+ s > (314) cw.

Because each satisfied neighbor of the corrupt variables must share at least two edges with the corrupt variables, and each unsatisfied neighbor must share at least one, we know that

By combining these two inequalities, we obtain

Since each unsatisfied constraint must share at least one edge with a corrupt variable, and since there are only cw edges leaving the corrupt variables, we see from inequality (1) that more than half the edges leaving the compt variables must enter unsatisfied constraints. This implies that there must be some corrupt variable such that more than half of its neighbors are unsatisfied. However, this does not mean that the decoding algorithm will decide to flip a corrupt variable. It does mean that, if w 5 an, the algorithm will flip some variable. We will show that the algorithm successfully decodes its input if it begins with at most an12 corrupt variables. The only way the algorithm could fail is if it flips so many uncorrupt variables that w becomes greater than an. Assume by way u l contradiction that this happens. Then there must be some time at which w equals an. At this time, (1) tells us that U > can/2. This leads to a contradiction because U is initially at most can12 and can only decreasc during the cxecution of thc algorithm. 0 In Appendix I, we show that if thc simplc sequential dccoding algorithm can correct a constant fraction of error from a code C(B, then the graph B must be an-expander. P),

SIPSER AND SPIELMAN EXPANDER CODES

1715

However, our bound on the expansion B must have is far from the bound shown sufficient in Theorem 10.
B. Parallel Decoding

Substituting this inequality into inequality (2), we conclude

(3/4

+ ~)(iviICI) I V I- 1 + I

w 4+

I ~ W

Proposition 12: For c and d constant, the simple parallel decoding algorithm can be implemented as a circuit of size O ( nlog n) and depth O(1og n). Pro08 Each parallel decoding round can be implemented as a circuit of linear size and constant depth: computing which In parallel, flip each variable that is in more unsatisfied constraints are unsatisfied can be performed by a constant than satisfied constraints. number of layers of XOR gates, and the decision of whether Repeat until no such variable remains. or not a given variable should flip can be made a circuit that computes the majority of a constant number of inputs. 0 Theorem 11: Let B be a (e, d, a, (3/4 ) e ) expander, Remark 13: One can show that this parallel algorithm can for any t > 0. Let P be the code consisting of all even- be simulated sequentially in linear time. In this sense, Theorem weight words of length d. Then, the simple parallel decoding 11 is stronger than Theorem 10. We have included Theorem 10 algorithm will correct any a0 < a(1 4)/2 fraction of error because it is a simple analysis of a more natural algorithm, and after logl,(l-4e) (aon) decoding rounds. because the sequential algorithm should be substantially faster Proof: Let V denote the set of corrupt variables in the than a sequential simulation of the parallel algorithm. Moreinput. Assume that /VI < an(1 4)/2. We will show that over, our experiments indicate that the sequential algorithm after one decoding round, the algorithm will produce a word usually corrects more errors than the parallel algorithm (see that has at most (1 - 4 t ) l V I corrupt variables. Section VIII), even though this superiority is not evidenced in L,et F be the set of corrupt variables that fail to flip in our theoretical analyses. one decoding round, and let C be the set of variables that Remark 14: Zyablov and Pinsker [35] demonstrated that if were originally uncorrupt, but which become corrupt after one B is a randomly chosen ( e , d)-regular graph, then, with high decoding round. After one decoding round, the set of corrupt probability over the choice of graph, a parallel algorithm very varjables will be F UC. Set S so that the number of constraints similar to the preceding algorithm will successfully correct a that contain variables in V is Sc(V(. expansion, S > 3 / 4 + ~ . constant fraction of error in the code C(B,P ) . Pippenger has By We first establish that I U C ( < an. Assume by way of pointed out that Kuznetsovs [ 171 analysis of a construction of V V contradiction that I U CJ 2 an, and consider a subset G of fault-tolerant memories also serves as a proof of correctness of C such that (V U CI = an. By expansion, IN(V U C)( 2 our simple parallel decoding algorithm. Pippenger [26] made (3/4 )[Link] the other hand, each variable in C has at a connection between Kuznetsovs work and expander graphs. most c / 2 neighbors that are not neighbors of S ; so,

The simple sequential decoding algorithm has a natural parallel analog: in parallel, flip each variable that appears in more unsatisfied than satisfied constraints. We will see that this algorithm can also correct a constant fraction of error if the code is derived from a sufficiently good expander graph.

which implies

( N ( VU C)(5 SclV(+ c ( a n - IVl)/2.

Combining these two inequalities, we obtain

VI. EXPLICIT CONSTRUCTIONS OF EXPANDER CODES

IV( 2 an(1 + 4)/(4S - 2).

As S _< 1, this contradicts our assumption that IV( < an(1

+ 4t)/2.

]Because IV U C ( < an, we can bound the neighbors of V U C by

(3/4

+ E)C(IV(+ [Cl)I J N ( VU C)l I t SclVl

We now bound Sc(VJin terms of 1 . To do this, we bound 81 the number of neighbors of V by observing that each variable in F must share at least half of its neighbors with other corrupt variables. Thus each variable in F can account for at most (3/4)c neighbors. Moreover, each variable in V\F cain account for most c neighbors, which implies

In this section, we present an explicit construction of asymptotically good expander codes (Theorem 19). We will construct codes of the form C(B, S ) , where S is itself a good code of constant block length and B is the edge-vertex incidence graph of one of the expander graphs constructed in Theorem 2. Almost any good code S will suffice; however, to obtain the best possible performance, one should choose the best code available. We begin with a bound on the minimum distance of these codes. Lemma 15: If S is a linear code of rate r, block length d, and minimum relative distance 6, and if B is the edgevertex incidence graph of a d-regular graph with second-largest eigenvalue A, then the code C(B,S ) has rate at least 2r - 1 and minimum relative distance at least

1I16

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL 42, NO. 6, NOVEMBER 1996

Proot Let G be the d-regular graph from which B is derived. Let n be the number of vertices of G, so the number of variables of C(B, is dn/2 and the number of constraints S) is n. Lemma 5 implies that any set of
dn 2 variables will have at least yn constraints as neighbors. Since each variable has two neighbors, the average number of variables per constraint will be

Pro03 Let G be the d-regular graph from which B is derived. Let n be the number of vertices of G, so C(B, S) has d n / 2 variables and n constraints. Let X be the set of oldn/2 corrupt variables. The variables that are corrupt in the output of the decoding round will be those not in X to which a flip message is sent and those in X that do not receive a flip message. We will call a constraint confused if it sends a flip message to a variable that is not in X . We will call a constraint unhelpful if it contains a variable in X , but does not send a flip message to that variable. In order for a constraint to be confused, the constraint must have at least 3 / 4 ~ d variables of X as neighbors. Each variable of X is a neighbor of two constraints, so there can be at most

Thus if

47 + ( V a l - 7)) Ed <

(3)

confused constraints. Each of these can send at most dc/4 flip signals, so at most
4an - . _ - de
-

then a word of relative weight y2 (X/d)(r - 7) cannot be S). a codeword of C(B, Inequality (3) is satisfied for y < (1- X/d)/(t - X / d ) . So, in particular, C(B, cannot have a S) nonzero codeword of relative weight ( ( e - X/d)/(l - X/d)) or less. U The decoding algorithm for these codes is slightly more complicated that the decoding algorithm used in Section V. Rather than just flipping variables that appear in many unsatisfied constraints, it will flip the variables most likely to satisfy those constraints. As we are unaware of a natural sequential algorithm for decoding these codes, we present a logarithmic time parallel algorithm and then demonstrate that it can be simulated sequentially in linear time. The algorithm proceeds in rounds.
Parallel Decoding Round for C(B,S ) : (where S has block length d and minimum relative distance E)
0

d n 2a 4 2 3

variables not in X will receive flip signals. For a constraint to be unhelpful, it must have more than d~/4 neighbors in [Link] there are at most

dt -

unhelpful constraints. So, by Lemma 5, there can be at most 2

!&((?q+;($))

For each constraint, if the variables in that constraint differ from a codeword of S in at most d ~ / 4 places, then send a flip message to each variable that differs. In parallel, flip the value of each variable that receives at least one flip message.

Proposition 16: For S fixed, a parallel decoding round can be implemented as a linear-size circuit of constant depth. Lemma 17: Let S be a linear code of rate r , block length d , and minimum relative distance E , and let B be the edgevertex incidence graph of a d-regular graph with second-largest eigenvalue A. If a parallel decoding round lor C(B, ) is given S as input a word of relative distance a from a codeword, then it will output a word of relative distance at most

16a

from that codeword.

variables both of whose neighbors are unhelpful. As this set contains all the variables in X that fail to receive a flip message, we have proved the lemma. 0 Remark 18: Unless a < c2((1/3 - 4X/td)/16, and by implication t > 12X/d, the output word can be farther from the codeword than the input is. We will now build asymptotically good expander codes from the graphs constructed in Theorem 2 and good codes known to exist by the Gilbert-Varshamov bound (see [25]).We will then show that these codes can be decoded by the iteration of a logarithmic number of parallel decoding rounds. Theorem 19. For all E such that 1- 2 1 7 ( ~ > 0, where a(.) ) is the binary entropy function, there exists a polynomial-time constructible family of expander codes of rate L - 2H(t) and minimum relative distance arbitrarily close to E in which any a < t2/48 i-raction of errof can be corrected by a circuit of size O(n1og n ) and depth O(1ogn). Moreover, h e action o l this circuit can be simulated in linear lime on a Pointer Machine or a RAM under the uniform cost model. Proof. From the Gilbert-Varshamov bound, we know that for all sufficiently long block lengths there exist linear codes of minimum relative distance t and rate 1 - U ( )We . will use one such code in our asymptotic construction.

SIPSER AND SPIELMAN: EXPANDER CODES

1717

Recall that Theorem 2 allows us to build d-regular expander at graphs with second-largesteigenvalue most Xd = 2 m . So long as a < c2/48, there is a d such that

< e2(1/3 - 4Xd/td)/16

and (5 > 12Xd/d. Fix such a d along with a code S of block length d, minimum relative distance E, and rate 1 - H(E). From now on, B will be the edge-vertex incidence graph of a degree d graph constructed in Theorem 2. The bounds on the rate and minimum relative distance of C(B,S ) follow from Lemma 15. By Lemma 17, a parallel decoding round for C(B,S ) will transform a word of relative distance a from a codeword into a word of relative distance at most

Remark 20: Some may consider the use of the GilbertVarshamov bound in the preceding argument to be nonconstructive. To us, a constant amount of nonconstructivity is negligible. However, we point out that one could replace this argument by using any known asymptotically good code, or just fixing d and picking an appropriate error-correcting code (say, from the back of [25]).In this case, one might want to strengthen the use of Lemma 5 with techniques from [14].

A. Alons Generalization Noga Alon has pointed out that the edge to vertex construction that we use to construct expander codes is a special case of a construction due to Ajtai, Komlbs, and Szemerkdi [5]. They construct unbalanced expander graphs from regular expander graphs by identifying the large side of their graph with all paths of length k in the original graph and the small side of their graph with the vertices of the original graph. A node identified with a path is connected to the nodes identified with the vertices along that path. The construction used in Theorem 17 is the special case in which k = 1. Alon suggested that the codes produced by applying the technique of Theorem 19 to this more general class of graphs can be analyzed by applying the following lemma of Kahale ~41. Lemma 21 (Kahale): Let G,J be a d-regular graph on n nodes with second-largest eigenvalue bounded by A. Let S be a subset of the vertices of Gn,d of size yn. Then, the number of paths of length IC contained in the subgraph induced by S in G,,d is at most

2
from that codeword. Let

16a

0 = ( 2 / 3 + 16a/c2 + Xdd/4~).
Because we chose d so that a < c2(1/3 - 4Xd/~d)/16,we have < 1. Thus the iteration of logllp an parallel decoding rounds will correct an errors in the code C(B, S).Because S is a fixed code, Proposition 16 implies that this decoding algorithm can be implemented by a circuit of size O(n log n) and depth O(1ogn). We now explain how this aigorithm can be simulated in linear time on a Pointer Machine or a RAM under the uniform cost model. During each round, the simulating algorithm will construct a list containing a pointer to each constraint that could possibly be unsatisfied at the beginning of the next round. We will show that the amount of work performed by the algorithm is linear in the total size of these lists and that the total size of all these lists will be linear in n. Before the algorithm has read its input, any constraint could be unsatisfied, so it must begin with a list containing all rhe constraints. However, when it builds its list for the second round, it need only, include those constraints that were unsatisfied in the first round and those that contain a variable that received a flip message in the first round. In general, a constraint can only be unsatisfied in round i if it was unsatisfied in round i - 1 or if a variable it contains received a flip message in round i - 1. Given the list of constraints that could possibly have been unsatisfied in round i - 1, only linear work in the length of this list is needed to construct the list for round i : one need only check which of the constraints were actually unsatisfied and which variables received flip messages. Similarly, the work required to simulate the decoding in round i will be linear in the length of its list. To see that the total size of these lists is linear, observe that the number of corrupt variables decreases by a factor of (1-p)

A proof of this fact can also be found in [3]. Theorem 22: For all integers IC 2 2 and all E such that 1 - ~ H ( E ) 0, there exists a polynomial-time constructible > family of linear codes with rate 1 - kH(t-) and minimum relative distance arbitrarily close to el+/(-) for which a circuit of size O(n1ogn) and logarithmic depth will decode some Q ( c + ~ / ( ~ - ~fraction of error. Moreover, this circuit )) can be simulated in linear time on a sequential machine. Proof: [Sketch] As in Theorem 17, we will use the graphs known to exist by Theorem 2. We will form a code by using the k-path-vertex incidence graph of Gn,p+land by using a Gilbert-Varshamov good code at the constraints. The Gilbert-Varshamov bound implies that for sufficiently large block length p 1, there exist linear codes of rate T and minimum relative distance E provided that T 5 1 - H ( E ) . Moreover, as p 1 grows large, the term involving X / d in Lemma 21 goes to zero. If this term were zero, then we would know that every set containing an E(+)/ fraction of the after each round. So, the sum of the number of variables that variables has at least an $1 fraction of the constraints as are corrupt during each round is the sum of a geometric series neighbors. Because there are nd variables of degree k and whose largest term is an, and thus is linear in a n . As only n constraints of degree kd, Theorem 7 would imply that no constraints that contain these variables may be unsatisfied or word of weight up to E(~+)/ be a codeword. However, can send flip messages, the total size of the lists is also linear in because X l d never actually reaches zero, we can only come n. 0 arbitrarily close to this bound.

+ +

1718

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL 42, NO 6, NOVEMBER 1996

To decode these codes, we modify the parallel decoding algorithm so that each constraint sends a flip message to its variables only if the setting of its variables is within E/h of a codeword, for some constant h depending on k . An analysis similar to that in the proof of Lemma 17 shows that if an a fraction of the variables were corrupt at the start of a round, then at most an a(k+l)+ah(ach -+ I - - :h)) h-1

CorolZary 23: The product of an asymptotically good linear code of length O(1ogn) with one of the expander codes constructed in Section V or VI of length O(n/logn) yields an asymptotically good code that can be decoded in linear time on a RAM in the loganthmic cost model. Vm. NOTES ON IMPLEMENTATION AND EXPERIMENTAL RESULTS
We imagine using expander codes in coding situations where long block length is required. For small block lengths, special codes are known that will provide better performance. Expander codes should be especially useful for coding on write-once media, such as Compact Discs, where fast decoding is essential, the time required to encode is not critical, and codes of block length roughly 10 000 are already being used u21. If one intends to implement expander codes, we suggest using the randomized construction presented in Section V. We obtained the best performance from graphs that had degree 5 at the variables. It might be possible to get good performance with randomly chosen graphs and slightly more complex constraints, but we have not yet observed better performance from these. One drawback of using a randomly chosen graph to generate an expander code is that, while the graph will be a good expander with high probability, we know of no polynomial time algorithm that will certify that a graph has the level of expansion that we need for this construction. On the other hand, it is easy to perform experiments to test the performance of an expander code and thereby weed out those that do not work well on average. We now mention a few ideas that we hope will be helpful to those interested in implementing these codes. When one chooses a random graph as outlined in Appendix 11, there is a good chance that the graph produced will have a double edge. That is, two edges between the same two vertices. We suggest using a simple heuristic to remove one of these edges, such as swapping its endpoint with that of a randomly chosen edge. If one is choosing a relativeIy small graph, say of 2000 nodes, then there is a fair chance that there will be two variables that share two neighbors. Again,we suggest discarding such graphs. In general, if one is choosing a relatively small graph, then there is a reasonable chance that it will have some very small set of vertices with low expansion. We were always able to screen these out by experiment. * The sequential decoding algorithm presented in Section V-A can be improved by the same means as many slopedescent algorithms. In experiments, we found that a good way to escape local minima was to induce some random errors. The sequential decoding algorithm also benefits from a little randomness in the choice of which variable it flips next. We also found that we could decode more errors when we allowed the algorithm to make a limited
2Computation of the eigenvalues of the graph does not work because Kahale [14] has proved that the elgenvalues cannot certify expansion greater than d / 2 .

;1 (

fraction of the variables will be corrupt after the decoding round. We can choose a to be some fixed fraction of and a value for h so that this term is less than a. The idea behind the sequential simulation of this algorithm is the same as that in Theorem 19. U

VII. LINEAR TIMEIN THE LOGARITHMIC COST MODEL

To construct expander codes that can be decoded in linear time on a RAM in the logarithmic cost model, we will take the product of an expander code with a good code of length log n. The reason that we cannot decode the codes presented in Sections V and VI in linear time in the logarithmic cost model is that our decoding algorithms make 0 ( n ) memory accesses, for which they are charged O(1ogn) time each. To solve this problem, we would like to retrieve logn bits with each memory access. Actually, we will replace each bit in those expander codes with a byte of (log n)/2 bits. Where the previous decoding algorithms would compute the exclusive-or of two bits, our new algorithm will compute the bit-wise exclusive-or of two bytes. In this way, we can obtain a code that can be decoded in linear time. However, this code is not asymptotically good: because this algorithm essentially acts independently on different bits within the bytes, one could corrupt the first component of every byte, which is a total of %n/logn bits, in such a way that the decoding algorithm would not be able to correct the errors. To fix this problem, we encode each of the bytes with a good linear error-correcting code of length logn and rate 1/2. This type of construction is called the product of two codes (see [25]). It can also be viewed as the concatenation of an expander code over an alphabet of (log n)/2 bits with a binary code of length logn and rate l / 2 . In linear time, the decoding algorithm can produce a table that it can use to perform nearest neighbor decoding for this code. Such a table lookup will require 0(log n) time. To decode this product code in linear time, we first decode each of the %/log n bytes by a table lookup, This takes O ( n ) time. We then decode the bytes using the expander code. This decoding algorithm will correct a constant fraction of error because, unless a constant fraction of error appears in the encoding of a constant fraction of the bytes, there will be very few errors left after the bytes have been decoded. Note that there are plenty of explicit asymptotically good codes that we could compose with the expander code. But, since we have linear time and the code only has length (logn)/2, we could find a code that meets the Gilbert-Varshamov bound (see [34, p. 1271). We have proved the following Corollary:

SIPSER AND SPIELMAN: EXPANDER CODES

1719

1800
C)

1600 0

1400 0

1200 -

1000 800 600400 200 -

0
0

0
0

0.5

0.55

0.6

0.65

0.7

0.75

Fig. 3. Number of errors that some expander codes of length 40 000 could almost always correct. For example, the point in the upper left-hand corner of the figure indicates that an expander code of rate 1 / 2 corrected all of the 50000 patterns of 1720 errors on which it was tested.

amount of negative progress. This finding is evidenced in Fig. 4. The parallel decoding algorithm presented in Section V-B seems better suited for implementation in hardware than the sequential algorithm. The performance of this parallel algorithm can be improved by changing the threshold at which it flips variables. An easy improvement is to start the threshold high and decrease it only when necessary. The algorithm performs even better if one only flips the variables that have the maximum number of unsatisfied neighbors. Of course, many hardware implementations will not allow this flexibility. One can encode expander codes in quadratic time in the same way that one can encode any linear code: multiply the vector of message bits by a matrix so as to produce their corresponding vector of check bits. One can speed up this process by not actually solving for all check bits. The correct values for the remaining check bits can be found by using one of the decoding algorithms. Since the decoding algorithm knows which bits are correct and which bits it needs to compute, it can actually perform much better than if it were trying to correct errors whose location is unknown. These codes really are easy to implement. We implemented these codes in C after a few hours work and set about testing their performance. In each test, we chose a random bipartite graph of the correct size and tested the performance of various decoding algorithms against random errors. For our tests, we never performed encoding-it suffices to examine the performance of the decoding algorithms around the 6 word. We present some results of our experiments so that the reader will know what to expect from these codes. However, we

encourage researchers to implement and try them out on the error patterns that they expect to encounter.
A. Some Experiments

In our experiments, we found that expander codes of the type discussed in Section V performed best when derived from a randomly chosen graph with degree 5 at the variables. We varied the rates of our codes by changing the degrees of the graphs at the constraints. In Fig. 3, we present the results of experiments performed on some expander codes of length 40 000. We began by choosing an appropriate graph at random as described in Appendix 11. We then implemented a variation of the sequential decoding algorithm from Section VA in which we allowed the algorithm to flip a limited number of variables even if they appeared in only two unsatisfied constraints (we call these negative progress flips). The algorithm would only make a negative progress flip if there were no variable in more unsatisfied than satisfied constraints. We then tested each code on many error patterns of various sizes. For each size, we choose 50000 error pattems of this size uniformly at random. Points in the graph indicate the number of errors that a code corrected in all 50 000 tests. One can see that the expander codes corrected a remarkably large number of errors. The results of these experiments are much better than one would expect if one plugged the estimates for the expansion of random graphs from Appendix I1 into Theorem 10. We believe that there are two principal reasons for this disparity. The first is that our estimation of the expansion obtained by a random graph could be improved. The second is that our experiments analyze the average case performance of these codes, whereas Theorem 10 is only concerned with the worst case.

1720

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 42, NO 6, NOVEMBER 1996

number of errors
Fig. 4. A rate 1 / 2 expander code of length 40 000. The points marked by o indicate the probability that the standard sequential decoding algorithm corrected a given number of errors. The points marked by x indicate the probability when the algonthm was allowed to flip up to 700 variables that appeared in one more satisfied than unsatisfied constraint.

In Fig. 4, we compare the performance of a version of the sequential decoding algorithm in which we allow negative progress flips with a version in which we do not. We chose a rate l/Z expander code of length 40 000. For each number of errors, we performed 2000 tests of each algorithm and counted the number of times that each successfully corrected the errors. While allowing negative progress flips did not seem to have much impact on the number of errors that the algorithms could almost always correct, it did greatly increase the chance that the algorithm could correct a given number of errors. IX. OPEN QUESTIONS This paper leaves many questions unanswered. In particular, we would like to know if one can obtain better constants from a construction such as that of Theorem 19. Another interesting question is whether one can construct expander codes with redundant constraints. The bound on the rate of an expander code in Theorem 7 assumes that all the constraints are linearly independent. Expander codes with a moderate amount of redundancy in their constraints could have many interesting applications. See [30, ch. 51 for a discussion of these. APPENDIX I NECESSITY EXPANSION OF We .will now show that the simple sequential decoding algorithm works only if the graph B is an expander graph. Note that the level of expansion that we prove necessary in the following argument is much less than the level of expansion that we need in the argument of Section V-A. Theorem 24: Let d > e, and let B be a bipartite graph between n variables of degree c and ( c / d ) n constraints of

degree d such that the simple sequential decoding algorithm successfully decodes all sets of at most an errors in the code C(B,P).Then, all sets of an variables must have at least

neighbors. Proof: We will first deal with the case in which c is even. In this case, every time a variable is flipped the number of unsatisfied constraints decreases by at least 2. Consider the performance of the decoding algonthm on a word of weight an. Because the algorithm stops when the number of unsatisfied constraints reaches zero, the algorithm must decrease the number of unsatisfied constraints by at least 2an as it corrects the an corrupt variables. Thus every word of weight an must cause at least 2an constraints to be unsatisfied, so every set of an variables must have at least 2an neighbors. Because we assume that d > c

and we are done with the case in which c is even. When c is odd, we can only guarantee that the number of unsatisfied constraints will d crease by 1 at each iteration. This means that every set of an variables must induce at least an unsatisfied constraints. Alone, this is insufficient to demonstrate expansion by a factor greater than 1. So, let us consider what must happen for the algorithm to be in a state in which an variables are corrupt, but there is no

SIPSEIR AND SPIELMAN EXPANDER CODES

1721

variable that the decoding algorithm can flip that will cause the number of unsatisfied constraints to decrease by more than 1. Each corrupt variable must have at least (e- 1)/2 of its edges in saitisfied constraints. Because each satisfied constraint can have at most d incoming edges, this implies that there must be at least an(. - 1)/2d satisfied neighbors of the an variables. This, together with the fact that there are at least an unsatisfied constraints, implies that the an variables must have at least an( 1 (e - 1)/2d) neighbors. O the other hand, if the algorithm decreases the number of m unsatisfied constraints by more than 1, then it must decrease the rmmber by at least 3. For some word of weight an, assume that the algorithm flips Pan variables before it flips a variable that decreases the number of unsatisfied constraints by only 1. . The original set of an variables must have had at least

APPENDIX I1 THE EXPANSION OF RANDOM GRAPHS In this appendix, we will prove upper and lower bounds on the expansion factors achieved by random graphs that become tight as the degrees of the graphs become large. We use the following procedure to choose a random graph:

3pan

+ (1- p)an

How to Choose a Random ( e , d)-Regular Graph: To choose a random ( e , d)-regular bipartite graph, we first choose a random matching between dn left nodes and d n right nodes. We collapse consecutive sets of d left nodes to form the n c-regular vertices, and we collapse consecutive sets of d right nodes to form the (c/d)n d-regular vertices. It is possible that this graph will have multiedges that should be thrown away, but this does not hurt the lower bound on the expansion of this graph that we will prove.
We now prove a simple upper bound on the expansion any graph can achieve. Theorem 25: Let B be a bipartite graph between n e-regular vertices and ( c / d ) n d-regular vertices. For all 0 < a < 1,there exists a set of an e-regular vertices with at most c n - (1- (1 - a ) d ) 0(1) neighbors. d

neighbor^.^ On the other hand, once the algorithm flips a

variable that causes the number of unsatisfied constraints to decrease by 1, we can apply the bound of the previous paragraph to see that the variables must have at least (1 - i ) a n ( l +

g)
P>a.

neighbors. We note that this bound is strictly decreasing in p, while the previous bound is strictly increasing in @, so the lower bound that we can obtain on the expansion occurs when p is chosen so that

Span

+ (1- p>an =
1+2p =

(1

e-1 + -)(l2d

*
=+

Prooj5 Choose a set X of an e-regular vertices uniformly at random. Now, consider the probability that a given d-regular vertex is not a neighbor of the set of c-regular vertices. Each neighbor of the d-regular vertex is in the set X with probability a . Thus the probability that the d-regular vertex is not a neighbor of X is
d-1

(l-P)(l+%)
2d c- 1

i3=0

p ( 3 + g ) = -c - 1

When we plug p back in, we find that the set of an variables must have at least c-1 e-1

q 3 ( 3+-

:-)+(I- 5,))
3+gd

which tends to (1- a ) das n grows large. This implies that the expected number of nonneighbors tends to n(c/d)(l - a)d.O This simple upper bound becomes tight as c grows large. For convenience, we will call the e-regular vertices variables and the d-regular vertices constraints. Theorem 26: Let B be a randomly chosen ( e , d)-regular bipartite graph between n variables and ( c / d ) n constraints. Then, for all 0 < a! < 1, with exponentially high probability all sets of an variables in B have at least

neighbors, where W(.) the binary entropy function. is Pro08 First, we fix a set of an variables, V, and estimate the probability that Vs set of neighbors is small. The probability that a given constraint is a neighbor of V is &least 1 - (1Thus the expected number of neighbors of V is at least n (c/d) (1 - (1 - a ) d ) Alon suggested that we form . = an a martingale (see [7]) to bound the probability that the size of the set of neighbors deviates from this expectation. Each node in V will have c outgoing edges. We will neighbors. 0 consider the process in which the destinations of these edges 3 0 n e might be tempted to assume a bound of Span + (1 - P)an(l + are revealed one at a time. We will let X i be the random ( c -- 1)/2d); but, there could be overlap between the Span constraints that were flipped previously and the extra (1 - p ) a n ( c- 1 ) / 2 d . variable equal to the expected size of the set of neighbors of

1722

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL 42, NO 6, NOVEMBER 1996

V given that the first i edges leaving V have been revealed. X I , . . . , X,,, form a martingale such that
I % l X%l X+ -

I1
<

for all 0 5 i

< c a n . Thus by Azumas Inequality (see [7])

Prob [E[X,,,] - X,,,

>X

But, E[X,,,] is just the expected number of neighbors of V. Moreover, X,,, is the expected size of the set of neighbors of V given that all edges leaving V have been revealed, which is exactly the size of the set of neighbors of V. Since there are only (a:) choices for the set V, it suffices to choose X so that

By Stirlings formula, this holds for large n if X satisfies .

ACKNOWLEDGMENT The authors wish to thank the many people who made helpful comments after reading early drafts of this paper. Among them, they would especially like to thank [Link], 0. Goldreich, M. Luby, L. Schulman, and S.-H. Teng. The authors wish to thank J. Kilian for asking whether he could use table lookups to speed up the decoding algorithms-the answer led to the material in Section VII. The authors would also like to thank [Link] for supplying them with the material that appears in Section VI-A and for Theorem 26.

REFERENCES
[I] N. Alon, J. Bmck, J. Naor, M. Naor, and R. M. Roth, Constmction of asymptotically good low-rate error-correcting codes through pseudorandom graphs, IEEE Trans. Inform. Theory, vol. 38, no. 2, pp. 509-516, Mar. 1992. [2] N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discr. Math., vol. 72, pp. 15-19, 1988. [3] N. Alon, U. Feige, A. Wigderson, and D. Zuckerman, Derandomized graph products, Comput. Complexity, pp. 60-75, 1995. [4] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley series in computer science and information processing). Reading, MA: Addison-Wesley, 1974. [5] M. Ajtai, J. Koml6s, and E. Szeer$di, Deterministic simulation in logspace, in Proc. 19th Ann. ACM Symp. on Theory of Computing, 1987, pp. 132-139. [6] N. Alon, Eigenvalues and expanders, Combinarorica, vol. 6, no. 2, pp. 83-96, 1986. [7] N. Alon and J. H. Spencer, The Probabilistic Method. New York: Wiley, 1992. [8] F. Bien, Constructions of telephone networks by group representations, Notices Amer. Math. Soc., vol. 36, no. 1, pp. 5-22, 1989.

[9] R. Boppana and M. Sipser, The complexity of finite functions, in Handbook o Theoretical Computer Science, Volume 4. Algorithms f and Complexity, J. van Leeuwen, Ed Cambndge, MA. MIT Press, Amsterdam, The Netherlands Elsevier, 1990, pp 757-804 [lo] R. G. Gallager, Low Density Paripcheck Codes Cambridge, MA. MIT Press, 1963 [ 111 Y Gurevich, Kolmogorov maclxnes and related issues, Bull Europ. Assoc. for Theor. Clop. Sci., vol. 35, pp. 71-82, June 1988. [12] H. Imai, Essentials of Error-Control Coding Techniques. San Diego, C A Academic Press, 1990 [13] N. Kahale, On the second eigenvalue and linear expansion of regular graphs, in Proc 33rd IEEE Symp on Foundations of Computer Science, 1992, pp. 2 9 6 3 0 3 1141 _ _ , Expander graphs, Ph.D dissertation, MIT, Cambridge, MA, Sept. 1993. [15] A. Kolmogorov and V. Uspensku, On the definition of an algorithm, Usp. Mat. Nauk, vol. 13, no 4, pp 3-28, 1958 (English translation in [161). , On the definition of an algorithm, Amer Math Soc Transl , [16] vol. 29, no. 217-245, 1963 [17] A V. Kuznetsov, Informatlon storage in a memory assembled from unreliable components, Probl. Inform. Transm., vol 9, no 3, pp 254-264, 1973. El81 L. Levin, Theory of computation: How to start, SIGACT News,vol 22, no. 1, pp. 47-56, 1991. [19] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica, vol. 8, no. 3, pp. 261-277, 1988. [20] G. A. Margulis, Explicit constructions of concentrators, Probl. Pered. Inform., vol. 9, no 4, pp 71-80, Oct.-Dec 1973 (English translation in [Zl]) [21] ~, Explicit constructions of concentrators, Probl Inform. Transm., vol. 9, pp 325-332, 1975. [22] - Explicit group theorebcal constructions of combinatorial , schemes and thelr application to the design of expanders and concentrators, Probl. Inform. Transm., vol 24, no. 1, pp. 39-46, . . July 1988. 1231 1 regular - . M. Morgenstem, Existance and explicit constructions of Q Ramanujan graphs for every prime power q, J Comb Theory, Ser B, vol. 62, pp. 44-62, 1994 . [24] -, Natural bounded concentrators, Combznatorica, vol. 15, no. 1, pp. 111-122, 1995. [25] F J MacWilliams and N J. A. Sloane, The Theory ofBror-Correcting Codes. Amsterdam, The Netherlands. North Holland, 1977. [26] N. Pippenger, The memory-refresh problem, Adv. Res. zn VLSI, vol. 6, p. 69, 1988, (abstract of talk). [27] , 1994, personal communications. [28] J. E. Savage, The Complexity of Computing. New York Wiley, 1976. [29] A. Schonhage, Storage mohfication machines, SIAM J Comput , vol. 9, no. 3, pp. 490-508, 1980. [30] D. A. Spielman, Computationally efficient error-correcting codes and holographc proofs, Ph.D. dissertafion, MIT, Cambridge, MA, May 1995 [Online.] Available WWW: [Link] edu/- spielman [3I] __ , Linear-time encodable and decodable error-correcting codes, th~s issue, pp. 1723-1731. [32] R. M Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform Theory, vol IT-27, no. 5, pp. 533-547, Sept. 1981. [33] ___, Explicit concentrators from generalized n-gons, SIAM J. Alg. Disc. Meth., vol. 5, no 3, pp 287-293, Sept. 1984. [34] J. H. van Lint, Introductron to Coding Theory New York SpringerVerlag, 1992. [35] V V. Zyahlov and M. S. Pinsker, Esbmation o f the error-correction complexity of Gallager low-density codes, Probl Inform Transm , vol 11, no. 1, pp. 18-28, May 1976. [36] V V. Zyablov, An estimate of the complexity o f constructing binary linear cascade codes, Probl Inform. Transm., vol. 7, pp. 3-10, 1971