CaltechAUTHORS
  A Caltech Library Service

Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs

Alon, Noga and Bruck, Jehoshua and Naor, Joseph and Naor, Moni and Roth, Ron M. (1992) Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38 (2). pp. 509-516. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:ALOieeetit92

[img]
Preview
PDF
See Usage Policy.

812Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ALOieeetit92

Abstract

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel 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 a 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 the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood.


Item Type:Article
Additional Information:© Copyright 1992 IEEE. Reprinted with permission. Manuscript received October 10, 1990. This work was done while N. Alon was on sabbatical from Tel-Aviv University. This work was presented in part at the IEEE International Symposium on Information Theory, Budapest, Hungary, June 24-28, 1991.
Subject Keywords:Expanders, Justesen codes, Zyablov bound, independent sets
Record Number:CaltechAUTHORS:ALOieeetit92
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:ALOieeetit92
Alternative URL:http://dx.doi.org/10.1109/18.119713
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6409
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:07 Dec 2006
Last Modified:26 Dec 2012 09:20

Repository Staff Only: item control page