Justesen code

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

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

Linear binary code
Generalized concatenated code — Justesen codes can be considered as a generalized concatenation of a Reed-Solomon outer code with \(N\) distinct binary inner codes.

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\).
Bose–Chaudhuri–Hocquenghem (BCH) code — Using more general BCH codes instead of RS codes can improve the parameters of the Justesen codes [2].

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

Victor V. Albert (2022-04-22) — most recent
Xiao Xiao (2022-03-25)

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.