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 \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), 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">\frac{1}{2}</tex> 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 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.