# Griesmer and Optimal Linear Codes from the Affine Solomon-Stiffler
Construction

Hao Chen Hao Chen is with the College of Information Science and
Technology/Cyber Security, Jinan University, Guangzhou, Guangdong Province,
510632, China<EMAIL_ADDRESS>This research was supported by NSFC Grant
62032009.

###### Abstract

In their fundamental paper published in 1965, G. Solomon and J. J. Stiffler
invented infinite families of codes meeting the Griesmer bound. These codes
are then called Solomon-Stiffler codes and have motivated various
constructions of codes meeting or close the Griesmer bound.

In this paper, we give a geometric construction of infinite families of affine
and modified affine Solomon-Stiffler codes. Projective Solomon-Stiffler codes
are special cases of our modified affine Solomon-Stiffler codes. Several
infinite families of $q$-ary Griesmer, optimal, almost optimal two-weight,
three-weight, four-weight and five-weight linear codes are constructed as
special cases of our construction. Weight distributions of these Griesmer,
optimal or almost optimal codes are determined. Many optimal linear codes
documented in Grassl’s list are re-constructed as (modified) affine Solomon-
Stiffler codes.

Several infinite families of optimal or Griesmer codes were constructed in two
published papers in IEEE Transactions on Information Theory 2017 and 2019, via
Gray images of codes over finite rings. Parameters and weight distributions of
these Griesmer or optimal codes and very special case codes in our
construction are the same. We also indicate that more general distance-optimal
binary linear codes than that constructed in a recent paper of IEEE
Transactions on Information Theory can be obtained directly from codimension
one subcodes in binary Solomon-Stiffler codes.

Index terms: Griesmer Code. Griesmer defect. Optimal code. Affine Solomon-
Stiffler code. Modified affine Solomon-Stiffler code. Weight distribution.

##  1 Introduction

###  1.1 Preliminaries

We recall some basic facts in the coding theory, see [18]. The Hamming weight
$wt({\bf a})$ of a vector ${\bf a}=(a_{0},\ldots,a_{n-1})\in{\bf F}_{q}^{n}$
is the cardinality of nonzero coordinates. The Hamming distance $d({\bf
a},{\bf b})$ between two vectors ${\bf a}$ and ${\bf b}$ is $d({\bf a},{\bf
b})=wt({\bf a}-{\bf b})$. Then ${\bf F}_{q}^{n}$ is a finite Hamming metric
space. The minimum (Hamming) distance of a code ${\bf C}\subset{\bf
F}_{q}^{n}$ is,

$d({\bf C})=\min_{{\bf a}\neq{\bf b}}\\{d({\bf a},{\bf b}),{\bf a}\in{\bf
C},{\bf b}\in{\bf C}\\}.$

One of the main goal in the theory of error-correcting codes is to construct
codes ${\bf C}\subset{\bf F}_{q}^{n}$ with large cardinalities and minimum
distances. In general, there are some upper bounds on cardinalities or minimum
distances of codes. Optimal codes attaining these bounds are particularly
interesting, see [18]. A linear code over the finite field ${\bf F}_{q}$ with
the length $n$, dimension $k$ and the minimum Hamming weight $d$ is denoted as
a linear $[n,k,d]_{q}$ code. A linear code is called projective if its dual
distance is at least three. Let $A_{i}({\bf C})$, $i=0,1,\ldots,n$, be the
number weight $i$ codewords in the linear code ${\bf C}\subset{\bf
F}_{q}^{n}$. Then it is obvious that there are at most $n-d({\bf C})+1$
nonzero weights $i\in\\{d({\bf C}),d({\bf C})+1,\ldots,n\\}$, such that
$A_{i}({\bf C})\neq 0$. If $A_{i}({\bf C})\neq 0$ for exact $t$ indices
$i_{1}<i_{2}<\cdots<i_{t}$, this linear code is called $t$-weight linear code.
A simplex code is a one-weight code. When $t$ is small, constructions of few-
weight linear codes and the determination of their exact weight distributions
are important topic in coding theory.

For fixed $q,n,k$, if there is a linear $[n,k,d]_{q}$ code, and there is no
$[n,k,d+1]_{q}$ code. We call this code optimal. If there is a linear
$[n,k,d+1]_{q}$ code, but there is no linear $[n,k,d+2]_{q}$ code, we call
this linear $[n,k,d]_{q}$ code almost optimal. If there is a linear
$[n,k,d+2]_{q}$ code, but there is no linear $[n,k,d+3]_{q}$ code, we call
this $[n,k,d]_{q}$ code near optimal.

###  1.2 Related works

The Griesmer bound for a linear $[n,k,d]_{q}$ code in [10] asserts

$n\geq\Sigma_{i=0}^{k-1}\lceil\frac{d}{q^{i}}\rceil.$

Set $g_{q}(k,d)=\Sigma_{i=0}^{k-1}\lceil\frac{d}{q^{i}}\rceil$, for a linear
$[n,k,d]_{q}$ code, the Griesmer defect is $g({\bf C})=n-g_{q}(k,d)$. A linear
$[n,k,d]_{q}$ code attaining this bound, that is, the Griesmer defect zero
code, is called a Griesmer code, see [30, 17]. In 1965, Solomon and Stiffler
constructed infinite families of binary and $q$-ary Griesmer codes in [30]. In
1973, Baumert and McEliece proved that for fixed $q$ and $k$, there are
Griesmer codes for any given fixed large minimum distance $d$, see [1]. Then
many authors constructed Griesmer codes from various methods, see [13, 12, 11,
14, 2, 21, 19, 8, 16, 24, 17]. Optimal linear codes close to the Griesmer
bound were also constructed in [27, 16, 17, 22]. However, codes in [20, 21]
have Griesmer defects one or two.

In coding theory, it is extremely difficult to determine exact weight
distributions of linear codes. For constructions of few-weight linear codes
from Boolean functions and designs, and the determination of their exact
weight distributions, we refer to [3, 4, 5, 6, 7, 31, 22, 23, 8, 16, 17, 32]
and references therein.

We recall the definition of binary Solomon-Stiffler code associated with $h$
integers $u_{1},\ldots,u_{h}$, satisfying

$k>u_{h}>u_{h-1}>\cdots>u_{1}\geq 1.$

Suppose that there are $h$ dimension $u_{1},\ldots,u_{h}$ subspaces
$S_{1},\ldots,S_{h}$ in ${\bf F}_{2}^{k}$, such that $S_{i}\bigcap S_{j}={\bf
0}$. Let $F$ be the set of disjoint nonzero column vectors in dimension
$u_{1}$, $u_{2}$, …, $u_{h}$ subspaces $S_{1},\cdots,S_{h}$ in ${\bf
F}_{2}^{k}$. Deleting these columns in the generator matrix of the binary
simplex $[2^{k}-1,k,2^{k-1}]_{2}$ code, we obtain a binary linear
$[2^{k}-1-\Sigma_{i=1}^{h}(2^{u_{i}}-1),k,2^{k-1}-\Sigma_{i=1}^{h}2^{u_{i}-1}]_{2}$
code meeting the Griesmer bound, see [30]. Similarly, $q$-ary projective
Solomon-Stiffler codes can be defined, we refer to [30]. In particular, when
$h=1$, $u_{1}=k-1$, 1st order Reed-Muller code is a binary Solomon-Stiffler
code associated with one positive integer $u_{1}=k-1$. However, weight
distributions of general Solomon-Stiffler codes have not been determined
completely.

In [14, Theorem 3, 5], it was showed that projective binary or $q$-ary
Griesmer codes are projective Solomon-Stiffler codes, when their minimum
weights satisfy some condition. In the case of a binary Griesmer $[n,k,d]_{2}$
code, if $d\leq 2^{k-1}$, this code is binary Solomon-Stiffler or Belov code.
For $q$-ary Griesmer codes, we refer conditions on $d$ to [14, Theorem 5].
Notice that Griesmer codes constructed in this paper are not projective. Then
these Griesmer codes are not $q$-ary projective Solomon-Stiffler codes
determined by Theorem 3 and Theorem 5 of [14].

Several infinite families of $q$-ary linear Griesmer codes or optimal codes
have been constructed in [27, 28, 26, 19, 24] as Gray images of two-weight
codes over finite rings. Weight distributions of these Griesmer and optimal
codes were determined in these two papers [27, 19]. In [27], Shi, Guan and
Solé constructed optimal codes in [27, Theorem 6.1, 6.3] via Gray images of
some two-weight codes over the finite ring ${\bf F}_{p}+u{\bf F}_{p}$ and
determined their exact weight distributions. The main contribution of [19] is
the construction of Griemser codes in [19, Theorem 3.5], based a similar
method. Similarly, Mesnager, Qian and Cao constructed optimal codes in [24,
Theorem 5.4] via Gray images of codes over a finite chain ring. In [16], more
general trace codes, which reach the Griesmer bound or are distance-optimal
were constructed. In [26, Theorm 2] and [25, Proposition 4.3, 5)], some binary
$[2^{k}-2^{u},k-1,2^{k-1}-2^{u-1}]_{2}$ codes were constructed. In a recent
paper [15], punctured and shortening optimal codes were obtained from Griesmer
cyclic codes.

###  1.3 Contributions and the organization of the paper

The contributions in this paper are summarized as follows.

1) We construct affine Solomon-Stiffler codes and modified affine Solomon-
Stiffler codes and upper bound their Griesmer defects in some cases. It shows
that many Griesmer, optimal and almost optimal linear codes can be obtained
from our construction.

2) In Sections 2 and 3, we show that these Griesmer codes and optimal codes
constructed in [27, 19] and very special case codes in our construction have
the same parameters and weight distributions. Optimal linear $q$-ary codes
constructed in [24] have same parameters as very special codes in our
construction. It is also indicated that Griesmer and optimal codes constructed
in this paper are less restrictive than that constructed in [16]. In Section
7, we construct much more general distance-optimal binary codes than these
constructed in [26, 25]. Our distance-optimal codes are codimension one or two
subcodes of binary Solomon-Stiffler codes. Distance-optimal punctured codes of
Griesmer codes are also discussed in Section 8. Our results in Section 7 and 8
are more general than main results of [15].

3) Many optimal linear codes documented in [9] are reconstructed as affine
Solomon-Stiffler codes and modified affine Solomon-Stiffler codes, see Table 1
and Table 6. Then these optimal codes have an unified construction and
structural. Similarly, many almost optimal and near optimal linear codes are
constructed as (modified) affine Solomon-Stiffler codes. This gives a natural
geometric structure on these almost optimal and near optimal linear codes.

4) Several infinite families of Griesmer or optimal $q$-ary $t$-weight linear
codes, $q\leq 4$, $t\leq 5$, are constructed and their weight distributions
are determined. Comparing with previous works on few-weight lineae codes in
[3, 4, 5, 22, 23, 8, 32], codes in these infinite families are Griesmer,
optimal or almost optimal. Moreover these codes are more general than codes
constructed in previous papers, such as, [5, 27, 19, 28, 22, 24].

The paper is organized as follows. In Section 2, affine Solomon-Stiffler codes
are introduced. Though these codes are not Griesmer as projective Solomon-
Stiffler codes, their Griesmer defects can be upper bounded in some cases. In
Section 3, several infinite families of optimal affine Solomon-Stiffler codes
are given and their exact weight distributions are determined. In Section 4,
modified affine Solomon-Stiffler codes are presented. Comparing to affine
Solomon-Stiffler codes, their Griesmer defects decrease. Therefore, modified
Solomon-Stiffler codes are more closer to the Griesmer bound. In Section 5,
some infinite families of Griesmer modified affine Solomon-Stiffler codes are
constructed and their weight distributions are determined. In Section 6, an
infinite family of almost optimal codes is given, In Section 7, distance-
optimal binary codes are constructed from codimension one subcodes of Griesmer
codes. In Section 8, distance-optimal punctured codes of Griesmer codes are
give. Section 9 concludes the paper.

##  2 Affine Solomon-Stiffler codes

Let $k$ be a positive integer satisfying $k\geq 3$. Let $u_{1}$, …, $u_{h}$ be
positive integers satisfying $u_{1}\leq u_{2}\leq\cdots\leq u_{h}$. Let
$S_{1},\ldots,S_{h}$ be $h$ linear subspaces of ${\bf F}_{q}^{k}$ of
dimensions $u_{1},\ldots,u_{h}$ satisfying
1) $S_{i}\bigcap S_{j}={\bf 0}$, if $i\neq j$;
2) $\Sigma_{i=1}^{h}(q^{u_{i}}-1)<q^{k}-q^{k-1}$.

Let $s_{1}$ be the number of dimension $u_{1}$ subspaces, $s_{2}$ be the
number of dimension $u_{s_{1}+1}$ subspaces,…, $s_{t}$ be the number of
largest dimension $u_{s_{1}+s_{2}+\cdots+s_{t-1}+1}$ subspaces. Set
$g=(s_{1}-1)+\cdots+(s_{t}-1)$.

Let $S$ be the set of all $q^{k}-1$ nonzero vectors in ${\bf F}_{q}^{k}$
deleting nonzero vectors in $S_{1}\bigcup\cdots\bigcup S_{h}$. Then

$|S|=(q^{k}-1)-\Sigma_{i=1}^{h}(q^{u_{i}}-1).$

Lemma 1 $S$ is not contained in any $(k-1)$ dimension subspace of ${\bf
F}_{q}^{k}$.

Proof. Otherwise, we have $|S|\leq q^{k-1}-1$. This is a contradiction to the
condition 2).

From Lemma 1, column vectors in $S$ is a $k\times|S|$ matrix $G$ of the rank
$k$. Let ${\bf C}$ be the code with the generator matrix $G$. For the
convenience, we denote the above affine Solomon-Stiffler code by parameters
$(k,{\bf u})=(k,u_{1},\ldots,u_{h})$. Then we have the following result.

Theorem 1 The linear code ${\bf C}$ is a linear
$[q^{k}-1-\Sigma_{i=1}^{h}(q^{u_{i}}-1),k,d\geq(q-1)(q^{k-1}-\Sigma_{i=1}^{h}(q^{u_{i}-1})]_{q}$
code. This code has at most $2^{h}$ weights.

Proof. For any hyperplane $H\subset{\bf F}_{q}^{k}$, it is clear that
$|H\bigcap S_{i}|$ is minimal if and only if $H\bigcap S_{i}$ is a hyperplane
in $S_{i}$. Then $H-H\bigcap S$ is maximal, when each $H\bigcap S_{i}$ is a
hyperplane in $S_{i}$, for $i=1,\ldots,h$. The weight of the nonzero codeword
corresponding to $H$ is $|F_{2}^{k}-S|-|(H-H\bigcap S)|$. The first conclusion
follows directly. Since each $|H\bigcap S_{i}|$ has two possible values, then
$|H\bigcap S|$ has at most $2^{h}$ possible values. The second conclusion is
proved.

Notice that the condition $s_{i}\leq q-1$ similar to that in the definition of
Solomon-Stiffler codes is not imposed. If $h$ is large and there are many same
$u_{i}$’s. The Griesmer defect is large. The lower bound

$d\geq(q-1)(q^{k-1}-\Sigma_{i=1}^{h}(q^{u_{i}-1})$

is not tight. For example, if $u_{1}=\cdots=u_{h}=1$, and $h$ is large. Many
columns have to be deleted, a hyperplane cannot intersect each of such line at
the zero point, see Section 6 below.

The lower bound on minimum distances of affine Solomon-Stiffler codes is
simple. However, from this simple lower bound and a direct calculation on

$\Sigma_{i=0}^{k-1}\lceil\frac{(q-1)(q^{k-1}-\Sigma_{i=1}^{h}q^{u_{i}-1})}{q^{i}}\rceil$

, many Griesmer codes and optimal codes can be constructed, as in the
following Theorem 2, Corollary 1 and 2.

Lemma 2 Let ${\bf C}$ be a linear $[n,k,d]_{q}$ code with the Griesmer defect
$g$. Then the optimal distance of a linear $[n,k]_{q}$ code is at most $d+g$.

Proof. The conclusion follows from the Griesmer bound immediately.

We upper bound Griesmer defects in the following result.

Theorem 2. The Griesmer defect of this code ${\bf C}$ can be upper bounded in
the following several cases.
1) If $u_{1}<u_{2}<\cdots<u_{h}$, the code ${\bf C}$ is Griesmer.
2) If $u_{1}=u_{2}=\cdots=u_{h}$, the Griesmer defect is upper bounded by
$h-1$.
3) If
$u_{1}=\cdots=u_{s_{1}}<u_{s_{1}+1}=\cdots=u_{s_{1}+s_{2}}<\cdots<u_{s_{1}+\cdots+s_{t-1}+1}=\cdots=u_{s_{1}+\cdots+s_{t}}$
and $u_{s_{1}+\cdots+s_{j}}\leq u_{s_{1}+\cdots+s_{j}+1}-2$. Then the Griesmer
defect of the linear code ${\bf C}$ is upper bounded by $g$.

Proof. We calculate the Griesmer defect. Notice that
$\lceil\frac{(q-1)(q^{k-1}-\Sigma_{i=s_{1}+1}^{s_{1}+s_{2}}q^{u_{i}-1})}{q^{i}}\rceil\leq(q-1)\lceil\frac{(q^{k-1}-\Sigma_{i=s_{1}+1}^{s_{1}+s_{2}}q^{u_{i}-1})}{q^{i}}\rceil-(s_{2}-1)$,
only when $i=u_{s_{1}+1}$. On the other hand, if
$u_{s_{1}+s_{2}+\cdots+s_{j}+1}\geq u_{s_{1}+s_{2}+\cdots+s_{j}}+2$, this kind
of decreasing happens only when $i=u_{s_{j}+1}$. Then the conclusion follows.

The calculation of the Griesmer defects reveals that, even affine Solomon-
Stiffler codes introduced in this paper are not Griesmer as Solomon-Stiffler
codes in [30]. However their Griesmer defects are small in many cases. Hence,
many affine Solomon-Stiffler codes are close to the Griesmer bound, and are
distance-optimal or distance-almost optimal, distance-near optimal, with
respect to the Griesmer bound, when $h$ is small, see Table 1 below.

The following result follows from Theorem 2 directly.

Corollary 1 Let $m$ be a positive integer satisfying $m\geq 3$. Let $(k,{\bf
u})=(m+2,1,2,m)$. Then we construct an infinite family of Griesmer
$[q^{m+2}-q^{m}-q^{2}-q+2,m+2,(q-1)(q^{m+1}-q^{m-1}-q-1)]_{q}$ codes.

Proof. Let $S_{2}$ be the $2$-dimensional subspace with the base
$(1,0,\ldots,0)$ and $(0,1,0,\ldots,0)$ and $S_{3}$ be the $m$-dimensional
linear subspace with the base $(0,0,1,\ldots,0)$, …, $(0,0,0,\ldots,1)$. Then
$S_{1}$ is a line spanned by $(1,1,\ldots,1)$. It is obvious that the
condition 1) holds. The conclusion then follows from Theorem 2 immediately.

Example 1 Let $q$ be a prime power. When $(k,{\bf u})=(4m+7,m,m+1,m+2,m+3)$,
an infinite family of $q$-ary Griesmer linear

$[q^{4m+7}-q^{m+3}-q^{m+2}-q^{m+1}-q^{m}+3,4m+7,(q-1)(q^{4m+6}-q^{m+2}-q^{m+1}-q^{m}-q^{m-1}]_{q}$

code are constructed from Theorem 2.

Let $q$ be a prime power and $m$ be the positive integer satisfying $m\geq 2$.
When $(k,{\bf u})=(4m+3,m,m,m+1,m+2)$, an infinite family of $q$-ary optimal
linear

$[q^{4m+3}-q^{m+2}-q^{m+1}-2q^{m}+3,4m+3,(q-1)(q^{4m+2}-q^{m+1}-q^{m}-2q^{m-1}]_{q}$

code are constructed from Corollary 1.

We have the following result for distance-optimal codes.

Corollary 2 Suppose that $u_{1}\geq 2$. If only one $s_{j}$ is $2$ and other
$s_{i}$’s are $1$. Moreover,

$u_{s_{1}+\cdots+s_{j-2}}\leq u_{s_{1}+\cdots+s_{j-1}}-2\leq
u_{s_{1}+\cdots+s_{j-1}+1}-4.$

This linear code ${\bf C}$ constructed in Theorem 1 is distance-optimal with
respect to the Griesmer bound.

Proof. The conclusion follows from a similar calculation as in the proof of
Theorem 2.

Example 2 When $q=2$, $(k,{\bf u})=(5,1,2,3)$, we construct a binary linear
Griesmer $[20,5,9]_{2}$ code, from Theorem 2. This is a binary Solomon-
Stiffler code.

Example 3 When $q=7$, $k=2$ and $u_{1}=u_{2}=1$, the code in Theorem 1 is a
linear $[36,2,30]_{7}$ code. This code is only almost optimal. The optimal
distance is $31$, see [9]. This example illustrates that the condition
$u_{1}\geq 2$ in Corollary 2 is necessary.

Example 4 When $q=5$, $(k,{\bf u})=(3,2)$, we construct an optimal
$[100,3,80]_{5}$ code. The optimal linear $[100,3,80]_{5}$ code in [9] was
constructed as the shortening code of a linear $[101,4,81]_{5}$ code, with a
speical generator matrix documented in [9]. However, our construction is
structural and simpler.

Let $q$ be a prime power and $s$ be a positive integer satisfying $s\geq 3$.
The affine Solomon-Stiffler code associated with parameters $(2s-2,s)$ is a
linear Griesmer $[q^{2s-2}-q^{s-1},2(s-1),(q-1)(q^{2s-3}-q^{s-2}]_{q}$ code.
The $q$-copy repetition code is a linear
$[q^{2s-1}-q^{s},2(s-1),(q-1)(q^{2s-2}-q^{s-1})]_{q}$ code. This code is
optimal when $s\geq q$ as argued in [24, Theorem 5.4]. Comparing these two
codes, they have the same parameters. The construction of optimal codes in
[24] is based on Griesmer codes over a finite chain ring. Our construction is
simpler.

In [16, Theorem 1], similar codes with some strong restrictions on dimensions
of subfields of ${\bf F}_{q^{k}}$ are studied. Only codes in the case when
$u_{i}$ is not a factor of $u_{j}$, if $j>i$, or all $u_{i}$’s are the same,
are studied. Comparing to [16], we need the key condition 1). However it is
clear that Theorem 2 gives more general Griesmer and optimal codes than trace
Griesmer and optimal codes given in [16].

In the following table, we give some optimal, almost optimal and near optimal
codes constructed in Theorem 2, Corollary 1, and 2, see [9].

Table 1:  Affine Solomon-Stiffler codes $q$ | $[n,k,d]_{q}$ | $(k,{\bf u})$ | Optimality
---|---|---|---
$3$ | $[52,4,34]_{3}$ | $(4,1,3)$ | optimal
$3$ | $[64,4,42]_{3}$ | $(4,2,2)$ | optimal
$3$ | $[68,4,44]_{3}$ | $(4,1,1,2)$ | almost optimal
$3$ | $[70,4,46]_{3}$ | $(4,1,2)$ | optimal
$3$ | $[74,4,48]_{3}$ | $(4,1,1,1)$ | almost optimal
$3$ | $[78,4,52]_{3}$ | $(4,1)$ | optimal
$3$ | $[206,5,136]_{3}$ | $(5,1,2,3)$ | optimal
$3$ | $[208,5,138]_{3}$ | $(5,2,3)$ | optimal
$3$ | $[214,5,142]_{3}$ | $(5,1,3)$ | optimal
$3$ | $[226,5,5,150]_{3}$ | $(5,2,2)$ | optimal
$3$ | $[232,5,154]_{3}$ | $(5,1,2)$ | optimal
$3$ | $[232,5,152]_{3}$ | $(5,1,1,1,1,1)$ | near optimal
$3$ | $[234,5,154]_{3}$ | $(5,1,1,1,1)$ | near optimal
$3$ | $[236,5,156]_{3}$ | $(5,1,1,1)$ | almost optimal
$3$ | $[238,5,158]_{3}$ | $(5,1,1)$ | almost optimal
$3$ | $[240,5,160]_{3}$ | $(5,1)$ | optimal
$4$ | $[45,3,33]_{4}$ | $(3,1,2)$ | optimal
$4$ | $[48,3,36]_{4}$ | $(3,2)$ | optimal
$4$ | $[54,3,39]_{4}$ | $(3,1,1,1)$ | almost optimal
$4$ | $[57,3,42]_{4}$ | $(3,1,1)$ | almost optimal
$4$ | $[60,3,45]_{4}$ | $(3,1)$ | optimal
$4$ | $[225,4,168]_{4}$ | $(4,2,2)$ | optimal
$4$ | $[237,4,177]_{4}$ | $(4,1,2)$ | optimal
$4$ | $[243,4,180]_{4}$ | $(4,1,1,1,1)$ | near optimal
$4$ | $[246,4,183]_{4}$ | $(4,1,1,1)$ | almost optimal
$4$ | $[249,4,186]_{4}$ | $(4,1,1)$ | almost optimal
$4$ | $[252,4,189]_{4}$ | $(4,1)$ | optimal
$5$ | $[96,3,72]_{5}$ | $(3,1,2)$ | optimal
$5$ | $[116,3,92]_{5}$ | $(3,1,2)$ | almost optimal
$8$ | $[49,2,42]_{8}$ | $(2,1,1)$ | almost optimal
$9$ | $[64,2,56]_{9}$ | $(2,1,1)$ | almost optimal

Notice all codes in Table 1 are not Solomon-Stiffler codes in [30]. Moreover,
it is easy to determine exact weight distributions of optimal, almost optimal
and near optimal codes in Table 1, based on a similar geometric method as the
proof of Theorem 1.

##  3 Optimal few-weight affine Solomon-Stiffler codes

In this section, we construct several infinite families of optimal two and
three weight $q$-ary linear codes, which are based on Theorem 2 and Corollary
1.

Let us consider the case $k=2m$, $u_{1}=u_{2}=m$. Then we construct a linear
$[q^{2m}-2q^{m}+1,2m,(q-1)(q^{2m-1}-2q^{m-1})]_{q}$ code. From Theorem 2, the
Griesmer defect is one and this is an optimal code. These codes have the same
parameters as optimal codes constructed by Shi, Guan and Solé in [27, Theorem
6.1]. The optimal codes in [27, Theorem 6.2], are just a repetition copy of
the above code. Their $q$ needs to be an odd prime satisfying $q\equiv 3$ $od$
$4$, and $m$ needs to be odd. It should be indicated that our codes are more
general. Moreover optimal codes in [27] were constructed via Gray images of
two-weight codes over a finite ring.

Theorem 3 Let $q\geq 3$ be a prime power. Let $(k,{\bf u})=(2m,m,m)$. Then we
construct an infinite family of optimal two-weight
$[q^{2m}-2q^{m}+1,2m,(q-1)(q^{2m-1}-2q^{m-1})]_{q}$ codes. The Griesmer defect
of these codes is $1$. The weight distribution is in the following table.

Table 2:  Weight distribution of optimal two-weight codes Weight | Weight distribution
---|---
$0$ | $1$
$(q-1)(q^{2m-1}-q^{m-1})$ | $2(q^{m}-1)$
$(q-1)(q^{2m-1}-2q^{m-1})$ | $(q^{m}-1)^{2}$

Proof. We only need to count hyperplanes in ${\bf F}_{q}^{2m}$ containing one
$m$-dimensional subspace ${\bf F}_{q}^{m}\subset{\bf F}_{q}^{2m}$. This means
that, the linear function defining $H$ is in the space generated by $m$ normal
vectors of this space. Therefore, there are $2(q^{m}-1)$ such hyperplanes.

Example 5 When $q=3$ and $m=2$, we construct an optimal two-weight
$[64,4,42]_{3}$ codes, see [9]. This is a Griesmer defect one optimal code.
Two weights are $42$ and $48$, $A_{42}=64$ and $A_{48}=16$. The optimal
$[64,4,42]_{3}$ code documented in [9] is the shortening code of a linear
$[65,5,42]_{3}$ code, which is from a stored generator matrix. Our code is
simple and geometric.

Notice that the weight distribution of this infinite family of optimal two-
weight $q$-ary linear codes is the same as the weight distribution Table II of
optimal two-weight codes constructed in [27, Theorem 6.1]. Their construction
via Gray images of two-weight codes over the finite ring ${\bf F}_{p}+u{\bf
F}_{p}$, seems unnecessary, since their strong conditions on $q$ and $m$ are
not essential. When $m=2r$, codes constructed in [16, Proposition 5] are these
codes in Theorem 3.

Similarly, we have the following two result.

Corollary 3 Let $m$ be a positive integer satisfying $m\geq 2$. Let $(k,{\bf
u})=(2m+1,m,m+1)$. Then we construct an infinite family of optimal three-
weight $[q^{2m+1}-q^{m+1}-q^{m}+1,2m+1,(q-1)(q^{2m}-q^{m}-q^{m-1})]_{q}$
codes. The weight distribution is in the following table.

Table 3:  Weight distribution of optimal two-weight codes Weight | Weight distribution
---|---
$0$ | $1$
$(q-1)(q^{2m}-q^{m})$ | $(q^{m+1}-1)$
$(q-1)(q^{2m}-q^{m-1})$ | $(q^{m}-1)$
$(q-1)(q^{2m}-q^{m}-q^{m-1})$ | $(q^{2m+1}-q^{m+1}-q^{m}+1$

Proof. The Griesmer defect is one, from Theorem 1. We only need to prove that
these codes are optimal. Otherwise,

$\Sigma_{i=0}^{2m}\lceil\frac{(q-1)(q^{2m}-q^{m}-q^{m-1})+1}{q^{i}}\rceil>\Sigma_{i=0}^{2m}\lceil\frac{(q-1)(q^{2m}-q^{m}-q^{m-1})}{q^{i}}\rceil+2,$

since $2m\geq 4$. The conclusion is proved.

Example 6 When $q=3$ and $m=2$, we construct an optimal ternary three-weight
$[208,5,138]_{3}$ code, see [9]. This is a Griesmer code. Three weights are
$138,144,156$, $A_{138}=208$, $A_{144}=26$ and $A_{156}=8$. The optimal
$[208,5,138]_{3}$ code in [9] is from a stored generator matrix.

Theorem 4 Let $m$ be a positive integer satisfying $m\geq 2$. Let $(k,{\bf
u})=(3m,m,m,m)$. Then we construct an infinite family of optimal three-weight
$[q^{3m}-3q^{m}+2,3m,(q-1)(q^{3m-1}-3q^{m-1})]_{q}$ codes. The Griesmer defect
of these codes is $2$. The weight distribution is in the following table.

Table 4:  Weight distribution of optimal two-weight codes Weight | Weight distribution
---|---
$0$ | $1$
$(q-1)(q^{3m-1}-q^{m-1})$ | $3(q^{m}-1)$
$(q-1)(q^{3m-1}-2q^{m-1})$ | $3(q^{2m}-1)$
$(q-1)(q^{3m-1}-3q^{m-1})$ | $q^{3m}-3q^{2m}-3q^{m}+5$

Proof. The Griesmer defect is upper bounded by $2$, from Theorem 2. The
calculation of the weight distribution is the same as the proof of Theorem 3.
For the optimality, we notice that the dimension of the code is at least
three. Then

$\Sigma_{i=0}^{3m-1}\lceil\frac{(q-1)(q^{3m-1}-3q^{m-1})+1}{q^{i}}\rceil>q^{3m}-3q^{m}+2,$

the conclusion is proved.

Example 7 In the case $m=1$, the code is near optimal and the weight
distribution is the same. When $q=5$ and $m=1$, we construct an near optimal
three-weight $[112,3,88]_{5}$ code. Three weights are $88$, $92$ and $96$,
$A_{88}=40$, $A_{92}=72$ and $A_{96}=12$. The optimal one in [9] is a linear
$[112,3,90]_{5}$ code.

Similarly, we have the following result.

Theorem 5 1) Let $q>2$ be a prime power. Let $m$ be a positive integer. Let
$(k,{\bf u})=(3m+1,m,m,m+1)$. Then we construct an infinite family of optimal
five-weight
$[q^{3m+1}-2q^{m}-q^{m+1}+2,3m+1,(q-1)(q^{3m}-2q^{m-1}-q^{m})]_{q}$ codes. The
weight distribution is in the following table.

2) In the case $q=2$, this infinite family of optimal binary codes have four
weights, since the weight $q^{3m}-2q^{m-1}$ is the same in the weight
$q^{3m}-q^{m}.$

Table 5:  Weight distribution of optimal two-weight codes Weight | Weight distribution
---|---
$0$ | $1$
$(q-1)(q^{3m}-q^{m-1})$ | $2(q^{m}-1)$
$(q-1)(q^{3m}-q^{m})$ | $q^{m+1}-1$
$(q-1)(q^{3m}-2q^{m-1})$ | $q^{2m}-1$
$(q-1)(q^{3m}-q^{m-1}-q^{m})$ | $2(q^{m+1}-q^{m})$
$(q-1)(q^{3m}-2q^{m-1}-q^{m})$ | $q^{3m+1}-q^{2m}-3q^{m+1}+3$

Example 8 When $q=2$ and $m=2$. Then an optimal $[114,7,56]_{2}$ code is
constructed. The Griesmer defect is two. The four weights are $56,58,60,62$,
$A_{56}=91$, $A_{58}=8$, $A_{60}=22$ and $A_{62}=6$. The optimal linear
$[114,7,56]_{2}$ code documented in [9] is from a quasi-cyclic code. Our
construction is structural.

Notice that this is not the binary Solomon-Stiffler codes invented in [30],
since the Griesmer defect is two. However, this binary Griesmer defect two
code is optimal.

##  4 Modified affine Solomon-Stiffler codes

In affine Solomon-Stiffler codes constructed in Theorem 1, if a vector ${\bf
v}$ is a column vector of the generator matrix $G$, then $\lambda{\bf v}$ is
also a column vector of $G$. If we only pick up these columns of the form
$\lambda{\bf v}$, where $\lambda$ takes over all elements of a subgroup of the
order $e$ in the multiplicative group ${\bf F}_{q}^{*}$, we have the following
result.

Theorem 6 Let ${\bf C}$ be the code with the generator matrix $G$. Then ${\bf
C}$ is a linear
$[\frac{e(q^{k}-1-\Sigma_{i=1}^{h}(q^{u_{i}}-1))}{q-1},k,e(q^{k-1}-\Sigma_{i=1}^{h}(q^{u_{i}-1})]_{q}$
code. The Griesmer defect of this code ${\bf C}$ is upper bounded similar to
Theorem 2.

Proof. The proof is similar to the proof of Theorem 1 and Theorem 2.

The interesting point here is that Griesmer defects of these modified affine
Solomon-Stiffler codes decrease. It is easy to see that when $e=1$ and
$u_{1}<u_{2}<\cdots<u_{h}$. Our modified affine Solomon-Stiffler codes are
$q$-ary projective Solomon-Stiffler codes invented in [30].

Example 9 When $q=5$, $(k,{\bf u})=(4,1,1,1,1)$ and $e=1$. We construct a
modified affine Solomon-Stiffler $[152,4,121]_{5}$ code. This is a linear
Griesmer code. Notice that the punctured $[130,4,99]_{5}$ code is obtained.
The optimal linear $[130,4]_{5}$ code has the optimal distance $103$.

When $q=7$, $(k,{\bf u})=(3,1,1,1)$ and $e=1$. We construct a modified affine
Solomon-Stiffler $[54,3,46]_{7}$ code. This is a linear Griesmer code. When
$e=2$, we construct a linear $[108,3,92]_{7}$ code. This is also a linear
Griesmer code. The punctured $[100,3,84]_{7}$ code is obtained. This code is
almost optimal, see [9].

When $q=8$, $(k,{\bf u})=(3,1,1,1)$ and $e=1$. We construct a modified affine
Solomon-Stiffler $[70,3,61]_{8}$ code. This is a linear Griesmer code. When
$e=2$, we construct a linear $[140,3,122]_{7}$ code. This is also a linear
Griesmer code. The punctured $[130,3,112]_{8}$ code is obtained. This code is
almost optimal, see [9].

Let us consider the modified affine Solomon-Stiffler code associated with
$(2m,m)$ and a divisor $e$ of $q-1$. This is a linear Griesmer
$[\frac{e(q^{2m}-q^{m})}{q-1},2m,e(q^{2m-1}-q^{m-1}]_{q}$ code with two
nonzero weights $e(q^{2m-1}-q^{m-1})$ and $eq^{2m-1}$. The weight distribution
can be calculated directly,

$A_{e(q^{2m-1}-q^{m-1})}=q^{2m}-q^{m}$

and

$A_{eq^{2m-1}}=q^{m}-1.$

Then the repetiton two-copy of this code is a linear Griesmer
$[\frac{2e(q^{2m}-q^{m}}{q-1},2m,2e(q^{2m-1}-q^{m-1})]_{q}$ code, with the
weight distribution

$A_{2e(q^{2m-1}-q^{m-1})}=q^{2m}-q^{m}$

and

$A_{2eq^{2m-1}}=q^{m}-1.$

Notice that this is the same as the Griesmer codes constructed in [19, Theorem
3.5]. The weight distribution is the same as that in [19, Theorem 3.3]. The
construction in [19], as that in [27], is very technique, and some
restrictions on $e$ and $m$ were needed.

Example 10 When $q=5$, $(k,{\bf u})=(4,1,1,1,1),e=1$, we construct a linear
$[152,4,121]_{5}$ code. This code is Griesmer code and non-Solomon-Stiffler.

The optimal linear $[50,3,40]_{5}$ code documented in [9] is constructed from
a constacyclic code. A projective Solomon-Stiffler code associated with
$(k,u_{1})=(3,2)$ has the same parameters.

In the following table, we list some non-Solomon-Stiffler codes constructed
from Theorem 6. Most of them are optimal, see [9].

Table 6:  Modified affine Solomon-Stiffler codes $q$ | $[n,k,d]_{q}$ | $(k,{\bf u})$ | Optimality, comparing with [30]
---|---|---|---
$3$ | $[37,4,24]_{3}$ | $(4,1,1,1)$ | optimal, non-Solomon-Stiffler
$3$ | $[116,5,76]_{3}$ | $(5,1,1,1,1,1)$ | almost optimal, non-Solomon-Stiffler
$3$ | $[117,5,77]_{3}$ | $(5,1,1,1,1)$ | almost optimal, non-Solomon-Stiffler
$3$ | $[118,5,78]_{3}$ | $(5,1,1,1)$ | optimal, non-Solomon-Stiffler
$4$ | $[81,4,60]_{4}$ | $(4,1,1,1,1)$ | optimal, non-Solomon-Stiffler
$4$ | $[83,4,62]_{4}$ | $(4,1,1,1,1)$ | optimal, non-Solomon-Stiffler
$7$ | $[100,3,84]_{7}$ | $(3,1,1,1)$ | almost optimal, non-Solomon-Stiffler
$8$ | $[130,3,112]_{8}$ | $(3,1,1,1)$ | almost optimal, non-Solomon-Stiffler

##  5 Few-weight Griesmer codes from the modified affine Solomon-Stiffler
construction

In this section, we construct some two-weight and three-weight Griesmer codes
and determine their weight distributions.

Theorem 7 Let $q>2$ be a prime power, $h$ and $m$ be a positive integers and
$e$ be a divisor of $q-1$ satisfying

$e(h-1)<q.$

Let $(k,{\bf u})=(hm,m,\ldots,m)$. Then we construct an infinite family of
Griesmer

$[\frac{e(q^{hm}-hq^{m}+h-1)}{q-1},hm,e(q^{hm-1}-hq^{m-1})]_{q}$

codes.

Proof. This follows immediately from Theorem 6.

Corollary 4 Let $q$ be a prime power and $e$ be a divisor of $q-1$. Then we
construct an infinite family of Griesmer
$[\frac{e(q^{2m}-2q^{m}+1)}{q-1},2m,e(q^{2m-1}-2q^{m-1})]_{q}$ codes. The
weight distribution is in the following table.

Table 7:  Weight distribution of optimal two-weight codes Weight | Weight distribution
---|---
$0$ | $1$
$e(q^{2m-1}-q^{m-1})$ | $2(q^{m}-1)$
$e(q^{2m-1}-2q^{m-1})$ | $(q^{m}-1)^{2}$

Proof. This conclusion follows from Theorem 7 directly.

Corollary 5 Let $m$ be a positive integer, $q>3$ be a prime power and $e$ be a
divisor of $q-1$ satisfying $2e<q$. Then we construct an infinite family of
Griesmer three-weight
$[\frac{e(q^{3m}-3q^{m}+2}{q-1},3m,e(q^{3m-1}-3q^{m-1})]_{q}$ codes. The
weight distribution is in the following table.

Table 8:  Weight distribution of optimal two-weight codes Weight | Weight distribution
---|---
$0$ | $1$
$e(q^{3m-1}-q^{m-1})$ | $3(q^{m}-1)$
$e(q^{3m-1}-2q^{m-1})$ | $3(q^{2m}-1)$
$e(q^{3m-1}-3q^{m-1})$ | $q^{3m}-3q^{2m}-3q^{m}+5$

Proof. The conclusion follows from Theorem 4 and Theorem 7 immediately.

Example 11 When $q=9$, $(k,{\bf u})=(3,1,1,1)$ and $e=1$. We construct a
three-weight Griesmer $[88,3,78]_{9}$ code. Three weights are $78$, $79$ and
$80$, $A_{78}=464$, $A_{79}=240$ and $A_{80}=24$. This is a projective
Solomon-Stiffler codes.

It is obvious that our geometric construction is more general and simple than
ring-technique used in [27, 19]. Much more infinite families of Griesmer or
optimal codes can be constructed. Weight distributions of these Griesmer or
optimal codes can be determined geometrically.

##  6 Modified affine Solomon-Stiffler codes when $u_{1}=u_{2}\cdots=u_{h}=1$,
$h$ large

In this section, we consider affine Solomon-Stiffler codes associated with
$u_{1}=\cdots=u_{h}=1$, $h$ is a large positive integer satisfying
$h<q^{k-1}$. We prove the following result.

Theorem 8 Let $q$ be a prime power and $h$ be a positive integer satisfying
$k\leq h<q^{k-1}$. Suppose that $h$ lines span the whole space. If there
exists a projective linear $[h,k]_{q}$ code with the maximum weight $h$. Then
we can construct a linear $[q^{k}-hq+h-1,k,(q-1)(q^{k-1}-h)]_{q}$ code. If
there exists no such a linear $[h,k]_{q}$ code with the maximum weight $h$,
then the minimum weight of this code is at least $d\geq(q-1)(q^{k-1}-h+1)$.

Proof. From the proof of Theorem 1, the conclusion is equivalent to find a
nonzero vector vector ${\bf h}$ such that the inner products of ${\bf h}$ with
these $h$ lines are nonzero. This is equivalent to the existence of a
projective linear $[h,k]_{q}$ code with the maximum weight $h$.

Example 12 Let $q$ be a prime power satisfying $q>2k$. Let
$h=k+\frac{k(k-1)}{2}$. These lines are spanned by vectors with one coordinate
$1$ or two coordinates $1$. Then we can find a vector $(x_{1},\ldots,x_{k})$
satifying

1) $x_{i}\neq 0$;

2) $x_{i}+x_{j}\neq 0$, if $i\neq j$.

Then a linear $[q^{k}-hq+h-1,k,(q-1)(q^{k-1}-h)]_{q}$ code is constructed. The
Griesmer defect is $(q-1)\lfloor\frac{h}{q}\rfloor$. When $k=4$ and $q=9$,
$h=10$. A linear $[6480,4,5752]_{9}$ code is obtained. The Griesmer defect is
$8$.

Corollary 6 Let $q$ be a prime power and $h$ be a positive integer satisfying
$k\leq h<q^{k-1}$. Suppose that $h$ lines span the whole space. If there
exists a projective linear $[h,k]_{q}$ code with the maximum weight $h$. Then
we can construct a projective linear
$[\frac{q^{k}-hq+h-1}{q-1},k,(q^{k-1}-h)]_{q}$ code. The Griesmer defect of
this code is upper bounded by
$\Sigma_{i=0}^{k-1}\lfloor\frac{h}{q^{i}}\rfloor.$

Proof. The proof is similar to the argument of Theorem 8.

Though the projective linear codes described in Corollary 6 is not projective
Solomon-Stiffler codes in [30]. When $h=2q$, the Griesmer defect is at most
$2+\lfloor\frac{h}{q^{2}}\rfloor$. This linear code is almost optimal.

Corollary 7 Let $q$ be a prime power and $h=2q$, and $k$ be a positive integer
satisfying $k\geq 2q$. Suppose that these $2q$ lines are linear independent.
Then we construct a projective linear almost optimal
$[\frac{q^{k}-1}{q-1}-2q,k,d\geq q^{k-1}-2q]_{q}$ code.

Proof. From the proof of Theorem 1, we have $d\geq q^{k-1}-2q$. If the maximal
possible distance of a linear $[\frac{q^{k}-1}{q-1}-2q,k]_{q}$ is
$q^{k-1}-2q+2$, then from the Griesmer bound, $\frac{q^{k}-1}{q-1}-2q\leq
q^{k-1}-2q+2+q^{k-2}-1+q^{k-3}+\cdots+q+1=\frac{q^{k}-1}{q-1}-2q+1$. This is a
contradiction.

When $q=2$, $h=4$, we construct a linear $[2^{k}-5,k,d\geq 2^{k-1}-4]_{2}$
code with the Griesmer defect at most $3$. This code is almost optimal, since

$\Sigma_{i=0}^{k-1}\lceil\frac{2^{k-1}-2}{2^{i}}\rceil=2^{k}-4>2^{k}-5.$

For example, binary linear $[59,6,28]_{2}$ code is constructed. The optimal
minimum weight of linear $[59,6]_{2}$ code is 29, see [9].

When $q=3,h=6$, we construct an infinite family of linear
$[\frac{3^{k}-1}{2}-6,k,3^{k-1}-6]_{3}$ code with the Griesmer defect at most
$2$. This code is almost optimal, since

$\Sigma_{i=0}^{k-1}\lceil\frac{3^{k-1}-4}{3^{i}}\rceil=\frac{3^{k}-1}{2}-5>\frac{3^{k}-1}{2}-6.$

For example, binary linear $[34,4,21]_{3}$ code is constructed. The optimal
minimum weight of linear $[34,4]_{3}$ code is 22, see [9].

These almost optimal projective linear codes constructed in Corollary 7 are
not included in [17].

##  7 Distance-optimal codes as codimension one or two subcodes in Griesmer
codes

We prove that any $k-1$ dimension subcodes of certain binary Griesmer
$[n,k,2d]_{2}$ codes are distance-optimal (with respect to the Griesmer
bound).

Theorem 9 Let ${\bf C}$ be a binary linear Griesmer $[n,k,2d]_{2}$ code
satisfying $k\geq 3$ and $d\leq 2^{k-2}$. Then any dimension $k-1$ subcode of
${\bf C}$ has minimum weight $2d$ and is distance-optimal. The Griesmer defect
of this shortening code is $1$.

Proof. Suppose there exists a linear $[n,k-1,2d+1]_{2}$ code. From the
Griesmer bound,

$n\geq\Sigma_{i=0}^{k-2}\lceil\frac{2d+1}{2^{i}}\rceil\geq
2+\Sigma_{i=0}^{k-2}\lceil\frac{2d}{2^{i}}\rceil=1+\Sigma_{i=0}^{k-1}\lceil\frac{2d}{2^{i}}\rceil.$

Since

$n=\Sigma_{i=0}^{k-1}\lceil\frac{2d}{2^{i}}\rceil,$

this is a contradiction.

Consider binary Solomon-Stiffer code associated with $(k,u)$, $k>u\geq 3$,
then we construct a linear Griesmer $[2^{k}-2^{u},k,2^{k-1}-2^{u-1}]_{2}$
code, from Theorem 1. From Theorem 8, any $k-1$ dimensional subcode is a
linear distance-optimal $[2^{k}-2^{u},k-1,2^{k-1}-2^{u-1}]_{2}$ code.

Distance-optimal codes constructed in [26, Theorem 2] and [25, Proposition
5.3, 5)] have the same parameters as above codes. Their constructions are
complicated and technique. Actually, more general such distance-optimal binary
codes are constructed in the following result. By the way, optimal binary
three-weight $[3\cdot 2^{3m-1},3m,3\cdot 2^{3m-2}]_{2}$ codes constructed in
[29] have the same parameters as repetition codes of the 1st order RM
$[2^{3m-1},3m,2^{3m-2}]_{2}$ codes.

Corollary 8 Let ${\bf C}$ be a binary Solomon-Stiffler
$[2^{k}-1-\Sigma_{i=1}^{h}(2^{u_{i}}-1),k,2^{k-1}-\Sigma_{i=1}^{h}2^{u_{i}-1}]_{2}$
code constructed in [30]. We assume that $k\geq 3$, $2\leq
u_{1}<u_{2}<\cdots<u_{h}<k$, Then we construct many dimension $k-1$ distance-
optimal binary
$[2^{k}-1-\Sigma_{i=1}^{h}(2^{u_{i}}-1),k-1,2^{k-1}-\Sigma_{i=1}^{h}2^{u_{i}-1}]_{2}$
codes. The Griesmer defect is one.

Proof. The conclusion follows from Theorem 9 immediately, since binary
Solomon-Stiffler codes are Griesmer.

Similarly we consider codimension two subcodes of a linear Griesmer code.

Theorem 10 Let ${\bf C}$ be a binary linear Griesmer $[n,k,4d]_{2}$ code
satisfying $k\geq 4$ and $d\leq 2^{k-4}$. Then any dimension $k-2$ subcode of
${\bf C}$ has minimum weight $4d$ and is distance-optimal. The Griesmer defect
of $k-2$ dimension subcode is two.

Proof. If the codimension two subcode is not distance-optimal. Then there
exists a linear $[n,k-2,4d+1]_{2}$ code. From the Griesmer bound,

$n\geq\Sigma_{i=0}^{k-3}\lceil\frac{4d+1}{2^{i}}\rceil\geq
3+\Sigma_{i=0}^{k-3}\lceil\frac{4d}{2^{i}}\rceil=1+\Sigma_{i=0}^{k-1}\lceil\frac{4d}{2^{i}}\rceil.$

Since

$n=\Sigma_{i=0}^{k-1}\lceil\frac{4d}{2^{i}}\rceil,$

this is a contradiction.

Hence there are many codimension two distance-optimal subcodes in binary
Solomon-Stiffler codes.

Corollary 9 Let ${\bf C}$ be a binary Solomon-Stiffler
$[2^{k}-1-\Sigma_{i=1}^{h}(2^{u_{i}}-1),k,2^{k-1}-\Sigma_{i=1}^{h}2^{u_{i}-1}]_{2}$
code constructed in [30]. We assume that $k\geq 4$, $u_{h}=k-1$ and $3\leq
u_{1}<u_{2}<\cdots<u_{h-1}\leq k-2$, Then we construct many dimension $k-2$
distance-optimal binary
$[2^{k}-1-\Sigma_{i=1}^{h}(2^{u_{i}}-1),k-1,2^{k-1}-\Sigma_{i=1}^{h}2^{u_{i}-1}]_{2}$
codes. The Griesmer defect of the dimension $k-2$ subcode is two.

For $q$-ary linear Griesmer codes, similar results can be proved.

Theorem 11 1) Let ${\bf C}$ be a $q$-ary linear Griesmer $[n,k,qd]_{q}$ code
satisfying $k\geq 3$ and $d\leq q^{k-2}$. Then any dimension $k-1$ subcode of
${\bf C}$ has minimum weight $qd$ and is distance-optimal. The Griesmer defect
of this codimension one subcode is one.

2) Let ${\bf C}$ be a $q$-ary linear Griesmer $[n,k,q^{2}d]_{q}$ code
satisfying $k\geq 4$ and $d\leq q^{k-4}$. Then any dimension $k-2$ subcode of
${\bf C}$ has minimum weight $q^{2}d$ and is distance-optimal. The Griesmer
defect of this codimension two subcode is two

From $q$-ary projective Solomon-Stiffler codes satisfying certain
restrictions, many distance-optimal $q$-ary linear codes are constructed. All
these distance-optimal codes have positive Griesmer defects.

Results in this section shows that, when some optimal codes with new
parameters were constructed, it would be better to check if these distance-
optimal codes (with respect to the Griesmer bound) are small codimension
subcodes of known Griesmer codes.

##  8 Distance-optimal codes as punctured codes of Griesmer codes

In this section, we prove the following result for punctured codes of $q$-ary
Griesmer codes.

Theorem 12 1) Let ${\bf C}$ be a $q$-ary linear Griesmer $[n,k,qd]_{q}$ code
satisfying $d=qd^{\prime}>1$. Then the punctured code at a position in the
support of a minimum weight codeword of ${\bf C}$ is a linear
$[n-1,k,qd^{\prime}-1]_{q}$ Griesmer code.

2) Let ${\bf C}$ be a $q$-ary linear Griesmer $[n,k,qd^{\prime}+1]_{q}$ code
satisfying $k\geq 3$. Suppose that $d^{\prime}$ satisfies that $d^{\prime}\geq
1$, $d^{\prime}\equiv d^{\prime\prime}$ $mod$ $q$, where
$d^{\prime\prime}<q-1$. Then the punctured code ${\bf C}$ at a position in the
support of a minimum weight codeword of ${\bf C}$ has the Griesmer defect one.
It is distance-optimal.

Proof. We have

$\Sigma_{i=0}^{k-1}\lceil\frac{qd^{\prime}-1}{q^{i}}\rceil=qd^{\prime}-1+\lceil\frac{qd^{\prime}-1}{q}\rceil+\cdots+\lceil\frac{qd^{\prime}-1}{q^{k-1}}\rceil=\Sigma_{i=0}^{k-1}\lceil\frac{qd^{\prime}}{q^{i}}-1=n-1.$

The conclusion 1) is proved.

Suppose that $d^{\prime}=qd_{1}+d^{\prime\prime}$, where
$d^{\prime\prime}<q-1$. Then,

$\Sigma_{i=0}^{k-1}\lceil\frac{qd^{\prime}}{q^{i}}\rceil=qd^{\prime}+d^{\prime}+\lceil\frac{q^{2}d_{1}+qd^{\prime\prime}}{q^{2}}\rceil+\cdots+\lceil\frac{q^{2}d_{1}+qd^{\prime\prime}}{q^{k-1}}\rceil=\Sigma_{i=0}^{k-1}\lceil\frac{qd^{\prime}+1}{q^{i}}\rceil-2.$

The Griesmer defect of the punctured code is one.

If there is a linear $[n-1,k,qd^{\prime}+1]_{2}$ code, then it is a
contradiction to the condition that the linear $[n,k,qd^{\prime}+1]_{q}$ code
is Griesmer. Therefore the punctured $[n-1,k,qd^{\prime}]_{q}$ code is
distance-optimal.

When Theorem 12 is applied to binary Solomon codes, then we have the following
result.

Corollary 10 Let ${\bf C}$ be a binary Solomon-Stiffler
$[2^{k}-1-\Sigma_{i=1}^{h}(2^{u_{i}}-1),k,2^{k-1}-\Sigma_{i=1}^{h}2^{u_{i}-1}]_{2}$
code constructed in [30]. We assume that $k\geq 3$, $u_{1}=1,u_{2}=2$ and
$3\leq u_{3}<\cdots<u_{h-1}\leq k-1$, Then we construct many dimension $k$
distance-optimal binary
$[2^{k}-1-\Sigma_{i=1}^{h}(2^{u_{i}}-1),k,2^{k-1}-\Sigma_{i=1}^{h}2^{u_{i}-1}-1]_{2}$
codes, as punctured codes. The Griesmer defect of these punctured codes is
one.

##  9 Conclusion

In this paper, we propose a general construction of Griesmer and optimal
linear codes as an affine version of Solomon-Stiffler codes. Modified affine
Solomon-Stiffler codes include these projective Solomon-Stiffler codes as
special cases. Griesmer or optimal codes constructed in [27, 19] have the same
parameters and weight distributions as very special case codes in our
construction. Our Griesmer and optimal codes are less restrictive than
Griesmer and optimal trace codes constructed in [16]. Optimal binary codes
constructed in a recent paper [25] and another paper [26] and codimension one
subcodes of special binary Solomon-Stiffler codes have the same parameters.
Distance-optimal codes as punctured code of Griesmer codes were also
discussed. We reconstructed many optimal codes in [9] from our modified affine
Solomon-Stiffler construction. Projective linear almost optimal codes similar
to codes in [30] were also constructed.

## References

  * [1] L. D. Baumert and R. J. McEliece, A not on the Griesmer bound, IEEE Transactions on Information Theory, vol. 19, no. 1, pp. 134-135, 1973.
  * [2] I. Bouyukliev, D.B. Jaffe, Z. Vabrek, The smallest length of eight-dimensional binary linear codes with prescribed minimum distance, IEEE Transactions on Information Theory vol. 46, no. 4, pp. 1539-1544, 2000.
  * [3] C. Carlet, P. Charpin and V. Zinoviev, Codes,bent functions and permutations suitable for DES-like cryptosystems, Designs, Codes and Cryptography, vol. 15, pp. 125-156, 1998.
  * [4] C. Ding, Linear codes from $2$-designs, IEEE Transactions on Information Theory, vol. 61, no. 8, pp. 3265-3275, 2015.
  * [5] K. Ding, and C. Ding, Binary linear codes with three weights, IEEE Communication Letters, vol. 18, no. 11, pp. 1679-1882, 2014.
  * [6] C. Ding, Z. Heng and Z. Zhou, Minimal binary linear codes, IEEE Transactions on Information Theory, vol. 64, pp. 6536-6545, 2018.
  * [7] C. Ding and Z. Heng, The subfield codes of ovoid codes, IEEE Transactions on Information Theory, vol. 65, pp. 4715-4729, 2019.
  * [8] C. Ding and C. Tang, Designs from linear codes, World Scientific Publ., second edition, 2023.
  * [9] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at http://www.codetables.de.
  * [10] J. H. Griesmer, A bound for error-correcting code, IBM Journal of Research and Development., vol. 4, pp. 532-542, 1960.
  * [11] T. Helleseth, A new class of codes meeting the Griesmer bound, IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 548-555, 1981.
  * [12] T. Helleseth, A characterization of codes meeting the Griesmer bound, Information and Control, vol. 50, pp. 128-159, 1981.
  * [13] T. Helleseth, New constructions of codes meeting the Griesmer bound, IEEE Transactions on Information Theory, vol. 29, no. 3, pp. 434-439, 1983.
  * [14] T. Helleseth, Projective codes meeting the Griesmer bound, Discrete Mathematics, vol. 106/107, pp. 265-271, 1985.
  * [15] F. Hernández and G. Vega, Obtaining new classes of optimal linear codes by puncturing and shortening optimal cyclic codes, Applicable Algebra in Engineering, Communication and Computing, online, 2024.
  * [16] Z. Hu, N. Li, X. Zeng, L. Wang and X. Tang, New constructions of optimal linear codes from simplicial complexes, IEEE Transactions on Information Theory, vol. 68, no. 7, pp. 4408-4421, 2022.
  * [17] Z. Hu, Y. Xu, N. Li, X. Zeng, L. Wang and X. Tang, New constructions of optimal linear codes from simplicial complexes, IEEE Transactions on Information Theory, vol. 70, no. 3, pp. 1823-1835, 2024.
  * [18] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge University Press, Cambridge, U. K., 2003.
  * [19] H. Liu and M. Youcef, Two or few-weight trace codes over ${\bf F}_{q}+u{\bf F}_{q}$, IEEE Transactions on Information Theory, vol. 65, no. 5, pp. 2676-2703, 2019.
  * [20] Y. Kageyama and T. Maruta, On the geometric construction of optimal linear codes, Designs, Codes and Cryptography, vol. 81., pp. 469-480, 2016.
  * [21] T. Maruta, http://mars39.lomo.jp/opu/griesmer.htm, 2022.
  * [22] S. Mesnager and A. Sinak, Several classes of minimal linear codes with few weights from weakly regular plateaued functions, IEEE Transactions on Information Theory, vol. 66, pp. 2296-2310, 2020.
  * [23] S. Mesnager, L. Qian X. Cao and M. Yuan, Several families of minimal binary linear codes from two-to-one functions, IEEE Transactions on Information Theory, vol. 69, pp. 3285-3301, 2023.
  * [24] S. Mesnager, L. Qian and X. Cao, Two families of few-weight codes over a finite chain ring, Discrete Mathematics, vol. 346, 113464, 2023.
  * [25] N. K. Mondal and Y. Lee, Optimal binary few-weight codes using a mixed alphabet ring and simplicial complexes, IEEE Transactions on Information Theory, early access, 2024.
  * [26] M. Shi, Y. Liu, and P. Solé, Optimal two-weight codes from trace codes, IEEE Communication Letters, vol. 20, no. 12, pp. 2346-2349, 2016.
  * [27] M. Shi, Y. Guan and P. Solé, Two new families of Two-Weight codes, IEEE Transactions on Information Theory, vol. 63, no. 10, pp. 6240-6246, 2017.
  * [28] M. Shi, R. Wu, Y. Liu, and P. Solé, Two and three weight codes over ${\bf F}_{p}+u{\bf F}_{p}$, Cryptography and Communications, vol. 9, no. 5, pp. 637-646. 2017.
  * [29] X. Li and M. Shi, A new family of optimal binary few-weight codes from simplicial complexes, IEEE Communication Letters, vol. 25, no. 4. pp. 1048-1051, 2020.
  * [30] G. Solomon and J. J. Stiffler, Algebraically punctured cyclic codes, Information and Controll, vol. 8, pp. 170-179, 1965.
  * [31] C. Tang, N. Li, Y. Qi, Z. Zhou, and T. Hellseth, Linear codes with two or three weights from weakly rugular bent functions, IEEE Transactions on Information Theory, vol. 62, no. 3, pp. 1166-1176, 2016.
  * [32] L. Xu, S. Mesnager, R. Luo and H. Yan, Subfield codes of several few-weight linear codes parametrized by functions and their consquences, IEEE Transactions on Information Theory, vol. 70, no. 6, pp. 3941-3964, 2024.