Griesmer code[1–3] 

Description

A type of \(q\)-ary code whose parameters satisfy the Griesmer bound with equality.

A \([n,k,d]_q\) code is a Griesmer code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Griesmer bound \begin{align} n\geq\sum_{j=0}^{k-1}\left\lceil \frac{d}{q^{j}}\right\rceil ~, \tag*{(1)}\end{align} where \(\left\lceil x\right\rceil \) is the ceiling function, becomes an equality.

An \([n,2,d]_q\) code exists if and only if it is not excluded by the Griesmer bound. Every Griesmer code is generated by its minimum-weight codewords [4].

Parent

Children

Cousins

  • Divisible code — If a \(p\)-ary Griesmer code with \(p\) prime is such that a power of \(p\) divides the distance, then the code is divisible by that power [6].
  • Binary BCH code — The \([15,5,7]\) BCH code extended with a parity check saturates the Griesmer bound ([5], pg. 157).
  • Kasami code — Kasami codes satisfy the Griesmer bound for certain parameters [7].
  • \([7,4,3]\) Hamming code — Starting with the \([6,3,3]\) shortened Hamming code and applying the \((u|u+v)\) construction recursively using the repetition code yields a family of \([2^m,m+1,2^{m-1}]\) codes for \(m\geq1\) that saturate the Griesmer bound [5; pg. 90].
  • Anticode — Several anticode (e.g., [8,9]) and related [10] constructions saturate the Griesmer bound; see Refs. [5,11,12] for more details.
  • Projective RM (PRM) code — PRM codes for \(r=1\) attain the Griesmer bound for all \(m\) [13].
  • Grassmannian code — The binary Grassmannian \([35,6,16]\) code, whose points lie on the Grassmannian \({\mathbb{G}(2,4)}\), attains the Griesmer bound [13].
  • Projective geometry code — Acrs corresponding to Griesmer codes are called Griesmer arcs [14; pg. 248]. There is a one-to-one correspondence between Griesmer codes and minihypers [15,16]; see [18][17; Sec. 14.2.4] for more details.
  • Galois-qudit CSS code — A quantum version of the Griesmer bound has been derived for Galois-qudit CSS codes [19].

References

[1]
J. H. Griesmer, “A Bound for Error-Correcting Codes”, IBM Journal of Research and Development 4, 532 (1960) DOI
[2]
G. Solomon and J. J. Stiffler, “Algebraically punctured cyclic codes”, Information and Control 8, 170 (1965) DOI
[3]
R. R. Varshamov, On the general theory of linear coding, Ph.D. Thesis, Moscow State University, 1959.
[4]
S. Dodunekov, Optimal linear codes, Ph.D. Thesis, Sofia, 1985.
[5]
J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[6]
H. N. Ward, “Divisibility of Codes Meeting the Griesmer Bound”, Journal of Combinatorial Theory, Series A 83, 79 (1998) DOI
[7]
T. Helleseth and P. Vijay Kumar, “The weight hierarchy of the Kasami codes”, Discrete Mathematics 145, 133 (1995) DOI
[8]
B. I. Belov, V. N. Logachev, V. P. Sandimirov, “Construction of a Class of Linear Binary Codes Achieving the Varshamov-Griesmer Bound”, Probl. Peredachi Inf., 10:3 (1974), 36–44; Problems Inform. Transmission, 10:3 (1974), 211–217
[9]
R. Hill, "Optimal Linear Codes in: C. Mitchell (Ed.) Crytography and Coding." (1992): 75-104.
[10]
B. I. Belov, "A conjecture on the Griesmer bound." Optimization Methods and Their Applications,(Russian), Sibirsk. Energet. Inst. Sibirsk. Otdel. Akad. Nauk SSSR, Irkutsk 182 (1974): 100-106.
[11]
I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
[12]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[13]
J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
[14]
I. N. Landjev, “The Geometric Approach to Linear Codes”, Developments in Mathematics 247 (2001) DOI
[15]
N. Hamada and M. Deza, “A characterization of νμ + 1 + ε, νμ; t, q-min.hypers and its applications to error-correcting codes and factorial designs”, Journal of Statistical Planning and Inference 22, 323 (1989) DOI
[16]
N. Hamada, Characterization of minihypers in a finite projective geometry and its applications to error-correcting codes, Bull. Osaka Women's Univ. 24 (1987), 1-24.
[17]
L. Storme, "Coding Theory and Galois Geometries." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[18]
J. W. P. Hirschfeld and L. Storme, “The Packing Problem in Statistics, Coding Theory and Finite Projective Spaces: Update 2001”, Developments in Mathematics 201 (2001) DOI
[19]
P. Sarvepalli and A. Klappenecker, “Degenerate quantum codes and the quantum Hamming bound”, Physical Review A 81, (2010) arXiv:0812.2674 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: griesmer

Cite as:
“Griesmer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/griesmer
BibTeX:
@incollection{eczoo_griesmer, title={Griesmer code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/griesmer} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/griesmer

Cite as:

“Griesmer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/griesmer

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/projective/griesmer.yml.