Codes of Belov Type

For a prime power b and positive integers n and d, write

d = wbn−1 – $\displaystyle \sum_{{i=1}}^{{v}}$qui−1

where w = ⌈d /bn−1⌉, n > u1 ≥ u2 ≥ ⋯ ≥ uv ≥ 1, and at most b−1 ui’s take any given integer value. Then there exists an [s, n, d]-code C over Fb meeting the Griesmer bound with equality provided that

$\displaystyle \sum_{{i=1}}^{{\min(w+1,v)}}$ui ≤ wn.

The special case for b = 2 is shown in [1], therefore the resulting codes are usually denoted as codes of Belov type. The general result is from [2].

Construction

Consider the multiset containing every point of the projective space PG(n−1, b) exactly w times and remove subspaces Ui of dimension ui − 1 for i = 1,…, v. Obviously, the subspace Ui must be chosen such that no point of PG(n−1, b) is contained in more than w of them. This can be done as follows: Identify a point (a0 : … : an−1) ∈ PG(n−1, b) with the polynomial a0 + a1X + … + an−1Xn−1 ∈ Fb[X]. For each i = 1,…, v choose a different monic, irreducible polynomial pi of degree k – ui (this is always possible, because there are at least b−1 such polynomials of each degree in Fb[X]). Then Ui can be identified with the monic polynomials in ⟨pi⟩ with degree less than n.

The remaining points form the columns of the generator matrix of C. In other words C is a properly truncated version of a w times juxtapositioned simplex code.

See Also

References

[1]B. I. Belov.
A conjecture on the Griesmer boundary.
In Optimization methods and their applications (All-Union Summer Sem., Khakusy, Lake Baikal, 1972) (Russian), pages 100–106, 182. Sibirsk. Ènerget. Inst. Sibirsk. Otdel. Akad. Nauk SSSR, Irkutsk, 1974.
[2]Raymond Hill.
Optimal linear codes.
In Cryptography and Coding, II (Cirencester, 1989), volume 33 of Inst. Math. Appl. Conf. Ser. New Ser., pages 75–104. Oxford Univ. Press, New York, 1992.
[3]F. Jessie MacWilliams and Neil J. A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977.
[4]Andries E. Brouwer.
Bounds on the size of linear codes.
In Vera S. Pless and W. Cary Huffman, editors, Handbook of Coding Theory, volume 1, pages 295–461. Elsevier Science, 1998.

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Codes of Belov Type.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CBelov.html

Show usage of this method