Justesen code[1]
Description
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
Realizations
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\).
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
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.