Justesen code[1]

Description

Binary 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\). 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)\).

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. [2].

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 [3].

Parents

Cousins

  • Reed-Solomon (RS) code — An RS code is the outer code of Justesen codes
  • Wozencraft ensemble code — Wozencraft ensemble forms the inner codes of Justesen codes
  • Random code — The required inner codes are obtained by random sampling from the Wozencraft ensemble, whose length scales logarithmically with \(n\).

Zoo code information

Internal code ID: justesen

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} }
Permanent link:
https://errorcorrectionzoo.org/c/justesen

References

[1]
J. Justesen, “Class of constructive asymptotically good algebraic codes”, IEEE Transactions on Information Theory 18, 652 (1972). DOI
[2]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977
[3]
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

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.