Class of constructive asymptotically good algebraic codes

For any rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R, 0 < R < 1</tex> , a sequence of specific <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(n,k)</tex> binary codes with rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_n > R</tex> and minimum distance <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</tex> is constructed such that {equation} limn → ∞ inf d/n ≥ (1 - r ⁻¹ R)H⁻¹ (1 - r)> 0 {equation} (and hence the codes are asymptotically good), where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</tex> is the maximum of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2</tex> and the solution of {equation} R = {r^2}{1 + log_2 [1 - H⁻¹(1 - r)]}. {equation} The codes are extensions of the Reed-Solomon codes over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">GF(2^m)</tex> With a simple algebraic description of the added digits. Alternatively, the codes are the concatenation of a Reed-Solomon outer code of length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N = 2^m - 1</tex> with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> distinct inner codes, namely all the codes in Wozeneraft's ensemble of randomly shifted codes. A decoding procedure is given that corrects all errors guaranteed correctable by the asymptotic lower bound on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</tex> . This procedure can be carried out by a simple decoder which performs approximately <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n^2 log n</tex> computations.