Small-bias Probability Spaces: efficient constructions
Noga Alon Shuki Bruck Joseph Naor Moni Naor Ronny Roth
A new technique, based on the pseudo-random properties of certain
graphs, known as expanders, is used to obtain new simple explicit
constructions of asymptotically good codes.
In one of the constructions, the expanders are used to
enhance Justesen codes by replicating, shuffling and then regrouping
the code coordinates. For any fixed (small) rate, and for sufficiently
large alphabet, the codes thus obtained lie above the Zyablov bound.
Using these codes as outer codes in a concatenated scheme,
a second asymptotic good construction is obtained which applies
to small alphabets (say, GF(2)) as well. Although these concatenated
codes lie below Zyablov bound, they are still superior to
previously-known explicit constructions in the zero-rate neighborhood.
The paper: Postscript, gzipped Postscript.
Related On-Line Papers:
Back to On-Line Publications
J. Naor and M. Naor,
Small-Bias Probability Spaces:
Efficient Constructions and Applications, SIAM J. Comput.
Postscript, gzipped Postscript.
Moni Naor, Constructing Ramsey graphs from small probability spaces,
Noga Alon and Moni Naor, Derandomization, witnesses for Boolean matrix
multiplication and construction of perfect hash functions, Algorithmica,
vol 16, 1996, pp. 434-449. Abstract