Celebratio Mathematica — Berlekamp

Complete Bibliography

Works connected to Jørn Justesen

Filter the Bibliography List

year	title	people

			clear

E. R. Berlekamp and J. Justesen: “Some long cyclic linear binary codes are not so bad,” IEEE Trans. Information Theory 20 : 3 (May 1974), pp. 351–356. MR 0381820 Zbl 0309.94023 article

We show that when an inner linear cyclic binary code which has an irreducible check polynomial is concatenated with an appropriately chosen maximal-distance-separable outer code, then the overall code is cyclic over \( \operatorname{GF}(2) \). Using this theorem, we construct a number of linear cyclic binary codes which are better than any previously known. In particular, by taking the inner code to be a quadratic residue code, we obtain linear cyclic binary codes of length \( N \), rate \( R \), and distance \[ D \geq (1 - 2R)N/\sqrt{2\log N} ,\] which compares favorably with the BCH distance \[ D \sim (2\ln R^{-1})N/\log N ,\] although it still fails to achieve the linear growth of distance with block length which is possible with noncyclic linear concatenated codes. While this construction yields many codes, including several with block lengths greater than \( 10^{10^5} \), we have not been able to prove that there are arbitrarily long codes of this type without invoking the Riemann hypothesis or the revised Artin conjecture, as the existence of long codes of our type is equivalent to the existence of large primes \( p \) for which the index of 2 is \( (p-1)/2 \).