Justesen code[1]


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


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.


Generalized minimum distance decoding [1].


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



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


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

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.