Class of constructive asymptotically good algebraic codes

Abstract

For any rateR, 0 < R < 1, a sequence of specific(n,k)binary codes with rateR_n > Rand minimum distancedis constructed such that \begin{equation} \lim_{n \rightarrow \infty} \inf \frac{d}{n} \geq (1 - r ^{-1} R)H^{-1} (1 - r)> 0 \end{equation} (and hence the codes are asymptotically good), whereris the maximum of\frac{1}{2}and the solution of \begin{equation} R = \frac{r^2}{1 + \log_2 [1 - H^{-1}(1 - r)]}. \end{equation} The codes are extensions of the Reed-Solomon codes overGF(2^m)With a simple algebraic description of the added digits. Alternatively, the codes are the concatenation of a Reed-Solomon outer code of lengthN = 2^m - 1withNdistinct 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 ond. This procedure can be carried out by a simple decoder which performs approximatelyn^2 \log ncomputations.