IEEE Transactions on Information Theory · 1996 · 942 citations · 14 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsInformation TheoryParallel ComputingChannel CodingCoding TheoryError Control CodingError CorrectionError-correcting CodesRandomized ComputationCode BoundsCode ConstructionsDecoding AlgorithmsExpander GraphsLinear Block CodesLinear CodesSequential Decoding
Using expander graphs, we construct a new family of asymptotically good, linear error-correcting codes. 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.
14
COMBINATORICA · 1986 · 1.2K citations
Alexander Lubotzky, Ralph S. Phillips, Peter Sarnak · COMBINATORICA · 1988 · 1K citations
Explicit construction of linear sized tolerant networks
Noga Alon, Fan Chung · Discrete Mathematics · 1988 · 336 citations