Class of constructive asymptotically good algebraic codes

For any rate R, 0, a sequence of specific (n, k) binary codes with rate Rₙ > R and minimum distance d is constructed such that equation ₍ dn (1 - r ^-1 R) H^-1 (1 - r) > 0 equation (and hence the codes are asymptotically good), where r is the maximum of 12 and the solution of equation R = r²1 + ₂ 1 - H^{-1 (1 - r) }. equation The codes are extensions of the Reed-Solomon codes over GF (2ᵐ) With a simple algebraic description of the added digits. Alternatively, the codes are the concatenation of a Reed-Solomon outer code of length N = 2ᵐ - 1 with N 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 d. This procedure can be carried out by a simple decoder which performs approximately n² n computations.