Justesen code[1] 

Description

Binary linear code resulting from generalized concatenation of a Reed-Solomon (RS) outer code with multiple inner codes sampled from the Wozencraft ensemble, i.e., \(N\) distinct binary inner codes of dimension \(m\) and length \(2m\). The first asymptotically good codes.

Justesen codes are parameterized by \(m\), with length \(n=2mN\) and dimension \(k=mK\), where \((N=2^m-1,K)\) is the RS outer code over \(GF(2^m)\). Further modifications have improved code parameters [24].

Rate

The first asymptotically good codes. Rate is \(R_m=k/n=K/2N\geq R\) and the relative minumum distance satisfy \(\delta_m=d_m/n\geq 0.11(1-2R)\), where \(K=\left\lceil 2NR\right\rceil\) for asymptotic rate \(0<R<1/2\); see pg. 311 of Ref. [5].

The code can be improved and extend the range of \(R\) from 0 to 1 by puncturing, i.e., by erasing \(s\) digits from each inner codeword. This yields a code of length \(n=(2m-s)N\) and rate \(R=mk/(2m-s)N\). The lower bound of the distance of the punctured code approaches \(d_m/n=(1-R/r)H^{-1}(1-r)\) as \(m\) goes to infinity, where \(r\) is the maximum of 1/2 and the solution to \(R=r^2/(1+\log(1-h^{-1}(1-r)))\), and \(h\) is the binary entropy function.

Decoding

Generalized minimum distance decoding [1].

Realizations

Generating small-bias sample spaces, i.e., probability distributions that parity functions cannot typically distinguish from the uniform distribution [6].

Parents

Cousins

References

[1]
J. Justesen, “Class of constructive asymptotically good algebraic codes”, IEEE Transactions on Information Theory 18, 652 (1972) DOI
[2]
E. J. Weldon, “Justesen’s construction--The low-rate case (Corresp.)”, IEEE Transactions on Information Theory 19, 711 (1973) DOI
[3]
Y. Sugiyama et al., “A modification of the constructive asymptotically good codes of Justesen for low rates”, Information and Control 25, 341 (1974) DOI
[4]
Y. Sugiyama et al., “A new class of asymptotically good codes beyond the Zyablov bound”, IEEE Transactions on Information Theory 24, 198 (1978) DOI
[5]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[6]
J. Naor and M. Naor, “Small-bias probability spaces: efficient constructions and applications”, Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC ’90 (1990) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: justesen

Cite as:
“Justesen code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/justesen
BibTeX:
@incollection{eczoo_justesen,
  title={Justesen code},
  booktitle={The Error Correction Zoo},
  year={2022},
  editor={Albert, Victor V. and Faist, Philippe},
  url={https://errorcorrectionzoo.org/c/justesen}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/justesen

Cite as:

“Justesen code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/justesen

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/justesen.yml.