Class of constructive asymptotically good algebraic codes
Class of constructive asymptotically good algebraic codes
复制标题
DOI：
10.1109/tit.1972.1054893
复制
发表时间：
1972-09
期刊：
影响因子：
--
通讯作者：
J. Justesen
中科院分区：
文献类型：
--
作者：
J. Justesen
对于任何速率r，0，构建具有速率r_n> r和最小距离d的特定（n，k）二进制代码的序列，以使\ begin {equation} \ lim_ {n \ rightarrow \ rightarrow \ infty} \ infty} \ inf \ frac { d} {n} \ geq（1 -r ^{ - 1} r）h ^{ - 1}（1- r）> 0 \ end {equation}（因此，代码渐近地很好），其中r是\ frac {1} {2}的最大值，并且\ begin of \ begin {equication} r = \ frac {r^2} {1 + \ log_2 [1 -h^{ - 1}（1- r）]}。 \ end {equation}代码是在gf（2^m）上使用的芦苇 - 固体代码的扩展，并具有简单的代数描述。另外，这些代码是长度n = 2^m -1的芦苇 - 固体外部代码的串联，该代码具有n个不同的内部代码，即Wozeneraft的随机移动代码的集合中的所有代码。给出了一个解码程序，该过程纠正了通过d上的渐近下限确保纠正的所有误差。可以通过简单的解码器执行该过程，该简单解码器执行大约n^2 \ log n计算。
For any rate R, 0 , a sequence of specific (n,k) binary codes with rate R_n > R and minimum distance d 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 r is 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 over GF(2^m) 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^m - 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^2 \log n computations.