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
- Maximum distance separable (MDS) code — Singleton bound implies the Griesmer bound.
Children
- Denniston code
- \(q\)-ary simplex code — Simplex codes saturate the Griesmer bound ([5], Exer. 5.1.11).
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.
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
Page edit log
- Victor V. Albert (2022-08-08) — most recent
Cite as:
“Griesmer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/griesmer