The generalized Hamming weights of linear codes were first introduced by Wei. These are fundamental parameters related to the minimal overlap structures of the subcodes and very useful in several …
The generalized Hamming weights of linear codes were first introduced by Wei. These are fundamental parameters related to the minimal overlap structures of the subcodes and very useful in several fields. It was found that the chain condition of a linear code is convenient in studying the generalized Hamming weights of the product codes. In this paper we consider a class of codes defined over some varieties in projective spaces over finite fields, whose generalized Hamming weights can be determined by studying the orbits of subspaces of the projective spaces under the actions of classical groups over finite fields, i.e., the symplectic groups, the unitary groups and orthogonal groups. We give the weight hierarchies and generalized weight spectra of the codes from Hermitian varieties and prove that the codes satisfy the chain condition.
Minimal linear codes have interesting applications in secret sharing schemes and secure two-party computation. This paper uses characteristic functions of some subsets of $\mathbb{F}_q$ to construct minimal linear codes. By …
Minimal linear codes have interesting applications in secret sharing schemes and secure two-party computation. This paper uses characteristic functions of some subsets of $\mathbb{F}_q$ to construct minimal linear codes. By properties of characteristic functions, we can obtain more minimal binary linear codes from known minimal binary linear codes, which generalizes results of Ding et al. [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536-6545, 2018]. By characteristic functions corresponding to some subspaces of $\mathbb{F}_q$, we obtain many minimal linear codes, which generalizes results of [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536-6545, 2018] and [IEEE Trans. Inf. Theory, vol. 65, no. 11, pp. 7067-7078, 2019]. Finally, we use characteristic functions to present a characterization of minimal linear codes from the defining set method and present a class of minimal linear codes.
In this paper, several infinite families of codes over the extension of non-unital non-commutative rings are constructed utilizing general simplicial complexes. Thanks to the special structure of the defining sets, …
In this paper, several infinite families of codes over the extension of non-unital non-commutative rings are constructed utilizing general simplicial complexes. Thanks to the special structure of the defining sets, the principal parameters of these codes are characterized. Specially, when the employed simplicial complexes are generated by a single maximal element, we determine their Lee weight distributions completely. Furthermore, by considering the Gray image codes and the corresponding subfield-like codes, numerous of linear codes over $\mathbb{F}_q$ are also obtained, where $q$ is a prime power. Certain conditions are given to ensure the above linear codes are (Hermitian) self-orthogonal in the case of $q=2,3,4$. It is noteworthy that most of the derived codes over $\mathbb{F}_q$ satisfy the Ashikhmin-Barg's condition for minimality. Besides, we obtain two infinite families of distance-optimal codes over $\mathbb{F}_q$ with respect to the Griesmer bound.
Nested codes have been employed in a large number of communication applications as a specific case of superposition codes, for example to implement binning schemes in the presence of noise, …
Nested codes have been employed in a large number of communication applications as a specific case of superposition codes, for example to implement binning schemes in the presence of noise, in joint network-channel coding, or in physical-layer secrecy. Whereas nested lattice codes have been proposed recently for continuous-input channels, in this paper we focus on the construction of nested linear codes for joint channel-network coding problems based on algebraic protograph LDPC codes. In particular, over the past few years several constructions of codes have been proposed that are based on random lifts of suitably chosen base graphs. More recently, an algebraic analog of this approach was introduced using the theory of voltage graphs. In this paper we illustrate how these methods can be used in the construction of nested codes from algebraic lifts of graphs.
Nested codes have been employed in a large number of communication applications as a specific case of superposition codes, for example to implement binning schemes in the presence of noise, …
Nested codes have been employed in a large number of communication applications as a specific case of superposition codes, for example to implement binning schemes in the presence of noise, in joint network-channel coding, or in physical-layer secrecy. Whereas nested lattice codes have been proposed recently for continuous-input channels, in this paper we focus on the construction of nested linear codes for joint channel-network coding problems based on algebraic protograph LDPC codes. In particular, over the past few years several constructions of codes have been proposed that are based on random lifts of suitably chosen base graphs. More recently, an algebraic analog of this approach was introduced using the theory of voltage graphs. In this paper we illustrate how these methods can be used in the construction of nested codes from algebraic lifts of graphs.
Nested codes have been employed in a large number of communication applications as a specific case of superposition codes, for example to implement binning schemes in the presence of noise, …
Nested codes have been employed in a large number of communication applications as a specific case of superposition codes, for example to implement binning schemes in the presence of noise, in joint network-channel coding, or in physical-layer secrecy. Whereas nested lattice codes have been proposed recently for continuous-input channels, in this paper we focus on the construction of nested linear codes for joint channel-network coding problems based on algebraic photograph LDPC codes. In particular, over the past few years several constructions of codes have been proposed that are based on random lifts of suitably chosen base graphs. More recently, an algebraic analog of this approach was introduced using the theory of voltage graphs. In this paper we illustrate how these methods can be used in the construction of nested codes from algebraic lifts of graphs.
We first summarize the basic structure of the outer distribution module of a completely regular code. Then, employing a simple lemma concerning eigenvectors in association schemes, we propose to study …
We first summarize the basic structure of the outer distribution module of a completely regular code. Then, employing a simple lemma concerning eigenvectors in association schemes, we propose to study the tightest case, where the indices of the eigenspace that appear in the outer distribution module are equally spaced. In addition to the arithmetic codes of the companion paper, this highly structured class includes other beautiful examples and we propose the classification of $Q$-polynomial completely regular codes in the Hamming graphs. A key result is Theorem 3.10 which finds that the $Q$-polynomial condition is equivalent to the presence of a certain Leonard pair. This connection has impact in two directions. First, the Leonard pairs are classified and we gain quite a bit of information about the algebraic structure of any code in our class. But also this gives a new setting for the study of Leonard pairs, one closely related to the classical one where a Leonard pair arises from each thin/dual-thin irreducible module of a Terwilliger algebra of some $P$- and $Q$-polynomial association scheme, yet not previously studied. It is particularly interesting that the Leonard pair associated to some code $C$ may belong to one family in the Askey scheme while the distance-regular graph in which the code is found may belong to another.
We first summarize the basic structure of the outer distribution module of a completely regular code. Then, employing a simple lemma concerning eigenvectors in association schemes, we propose to study …
We first summarize the basic structure of the outer distribution module of a completely regular code. Then, employing a simple lemma concerning eigenvectors in association schemes, we propose to study the tightest case, where the indices of the eigenspace that appear in the outer distribution module are equally spaced. In addition to the arithmetic codes of the companion paper, this highly structured class includes other beautiful examples and we propose the classification of $Q$-polynomial completely regular codes in the Hamming graphs. A key result is Theorem 3.10 which finds that the $Q$-polynomial condition is equivalent to the presence of a certain Leonard pair. This connection has impact in two directions. First, the Leonard pairs are classified and we gain quite a bit of information about the algebraic structure of any code in our class. But also this gives a new setting for the study of Leonard pairs, one closely related to the classical one where a Leonard pair arises from each thin/dual-thin irreducible module of a Terwilliger algebra of some $P$- and $Q$-polynomial association scheme, yet not previously studied. It is particularly interesting that the Leonard pair associated to some code $C$ may belong to one family in the Askey scheme while the distance-regular graph in which the code is found may belong to another.
Given a vertex subset C of a distance-regular graph $\Gamma$ on n vertices, it is shown that C is a completely regular code if and only if the number of …
Given a vertex subset C of a distance-regular graph $\Gamma$ on n vertices, it is shown that C is a completely regular code if and only if the number of vertices at maximum distance from C satisfies an expression in terms of the spectrum of $\Gamma$ and some mean numbers computed from the distances among the vertices of C (the so-called "inner distribution" of C). For such codes, this result can be seen as an improvement of Delsarte's linear programming method, since it gives stronger necessary conditions for their existence. As an application, a purely spectral characterization of those distance-regular graphs which are "edge-distance-regular" (that is, with every edge being a completely regular code with the same parameters) is derived.
Few-weight codes over finite chain rings are associated with combinatorial objects such as strongly regular graphs (SRGs), strongly walk-regular graphs (SWRGs) and finite geometries, and are also widely used in …
Few-weight codes over finite chain rings are associated with combinatorial objects such as strongly regular graphs (SRGs), strongly walk-regular graphs (SWRGs) and finite geometries, and are also widely used in data storage systems and secret sharing schemes. The first objective of this paper is to characterize all possible parameters of Plotkin-optimal two-homogeneous weight regular projective codes over finite chain rings, as well as their weight distributions. We show the existence of codes with these parameters by constructing an infinite family of two-homogeneous weight codes. The parameters of their Gray images have the same weight distribution as that of the two-weight codes of type SU1 in the sense of Calderbank and Kantor (Bull Lond Math Soc 18: 97-122, 1986). Further, we also construct three-homogeneous weight regular projective codes over finite chain rings combined with some known results. Finally, we study applications of our constructed codes in secret sharing schemes and graph theory. In particular, infinite families of SRGs and SWRGs with non-trivial parameters are obtained.
In this paper we give the generalization of lifted codes over any finite chain ring. This has been done by using the construction of finite chain rings from $p$-adic fields. …
In this paper we give the generalization of lifted codes over any finite chain ring. This has been done by using the construction of finite chain rings from $p$-adic fields. Further we propose a lattice construction from linear codes over finite chain rings using lifted codes.
Generalising a classical result of Delsarte [3], it was recently shown that certain codes over finite Frobenius rings with two nonzero homogeneous weights determine strongly regular graphs [1].This thesis gives …
Generalising a classical result of Delsarte [3], it was recently shown that certain codes over finite Frobenius rings with two nonzero homogeneous weights determine strongly regular graphs [1].This thesis gives constructions for infinite families of two-weight codes over Frobenius rings that result in strongly regular graphs.Some of the codes constructed do not have prime power order and the strongly regular graphs they yield therefore cannot arise from the classical construction over finite fields.Many of the strongly regular graphs constructed are shown to be isomorphic to graphs resulting from orthogonal arrays.In addition, relationships between the parameters of a two-weight code and the eigenvalues of the corresponding strongly regular graph are developed, allowing existence criteria for two-weight codes to be derived.The results of a computer search for two-weight codes are presented.
Given $\texttt{S}|\texttt{R}$ a finite Galois extension of finite chain rings and $\mathcal{B}$ an $\texttt{S}$-linear code we define two Galois operators, the closure operator and the interior operator. We proof that …
Given $\texttt{S}|\texttt{R}$ a finite Galois extension of finite chain rings and $\mathcal{B}$ an $\texttt{S}$-linear code we define two Galois operators, the closure operator and the interior operator. We proof that a linear code is Galois invariant if and only if the row standard form of its generator matrix has all entries in the fixed ring by the Galois group and show a Galois correspondence in the class of $\texttt{S}$-linear codes. As applications some improvements of upper and lower bounds for the rank of the restriction and trace code are given and some applications to $\texttt{S}$-linear cyclic codes are shown.
Linear codes with a few weights have applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. This paper first generalizes the …
Linear codes with a few weights have applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. This paper first generalizes the method of constructing two-weight and three-weight linear codes of Ding et al. and Zhou et al. to general weakly regular bent functions and determines the weight distributions of these linear codes. It solves an open problem proposed by Ding et al. Furthermore, this paper constructs new linear codes with two or three weights and presents their weight distributions. They contain some optimal codes meeting certain bound on linear codes.
In this paper, a class of two-weight and three-weight linear codes over GF(p) is constructed, and their application in secret sharing is investigated. Some of the linear codes obtained are …
In this paper, a class of two-weight and three-weight linear codes over GF(p) is constructed, and their application in secret sharing is investigated. Some of the linear codes obtained are optimal in the sense that they meet certain bounds on linear codes. These codes have applications also in authentication codes, association schemes, and strongly regular graphs, in addition to their applications in consumer electronics, communication and data storage systems.
In this paper, we generalize constructions in two recent works of Ding, Heng, and Zhou to any field F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> , q odd, providing infinite families of minimal …
In this paper, we generalize constructions in two recent works of Ding, Heng, and Zhou to any field F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> , q odd, providing infinite families of minimal codes for which the Ashikhmin-Barg bound does not hold.
Minimal linear codes have interesting applications in secret sharing schemes and secure two-party computation. This paper uses characteristic functions of some subsets of $\mathbb{F}_q$ to construct minimal linear codes. By …
Minimal linear codes have interesting applications in secret sharing schemes and secure two-party computation. This paper uses characteristic functions of some subsets of $\mathbb{F}_q$ to construct minimal linear codes. By properties of characteristic functions, we can obtain more minimal binary linear codes from known minimal binary linear codes, which generalizes results of Ding et al. [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536-6545, 2018]. By characteristic functions corresponding to some subspaces of $\mathbb{F}_q$, we obtain many minimal linear codes, which generalizes results of [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536-6545, 2018] and [IEEE Trans. Inf. Theory, vol. 65, no. 11, pp. 7067-7078, 2019]. Finally, we use characteristic functions to present a characterization of minimal linear codes from the defining set method and present a class of minimal linear codes.
<p style='text-indent:20px;'>In this paper, we give a geometric characterization of minimal linear codes. In particular, we relate minimal linear codes to cutting blocking sets, introduced in a recent paper by …
<p style='text-indent:20px;'>In this paper, we give a geometric characterization of minimal linear codes. In particular, we relate minimal linear codes to cutting blocking sets, introduced in a recent paper by Bonini and Borello. Using this characterization, we derive some bounds on the length and the distance of minimal codes, according to their dimension and the underlying field size. Furthermore, we show that the family of minimal codes is asymptotically good. Finally, we provide some geometrical constructions of minimal codes as cutting blocking sets.</p>
In this paper, we first study in detail the relationship between minimal linear codes and cutting blocking sets, recently introduced by Bonini and Borello, and then completely characterize minimal linear …
In this paper, we first study in detail the relationship between minimal linear codes and cutting blocking sets, recently introduced by Bonini and Borello, and then completely characterize minimal linear codes as cutting blocking sets. As a direct result, minimal projective codes of dimension 3 and t-fold blocking sets with t ≥ 2 in projective planes are identical objects. Some bounds on the parameters of minimal codes are derived from this characterization. Using this new link between minimal codes and blocking sets, we also present new general primary and secondary constructions of minimal linear codes. As a result, infinite families of minimal linear codes not satisfying the Aschikhmin-Barg's condition are obtained. In addition to this, open problems on the parameters and the weight distributions of some generated linear codes are presented.
Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. Minimal linear …
Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. Minimal linear codes have been studied since decades but their tight connection with cutting blocking sets of finite projective spaces was unfolded only in the past few years, and it has not been fully exploited yet. In this paper we apply finite geometric and probabilistic arguments to contribute to the field of minimal codes. We prove an upper bound on the minimal length of minimal codes of dimension <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> over the <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-element Galois field which is linear in both <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>, hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well.
Abstract Let <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>PG</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>r</m:mi><m:mo>,</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{PG}(r,q)} be the r -dimensional projective space over the finite field <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>GF</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{GF}(q)} . A set <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mi mathvariant="script">𝒳</m:mi></m:math> {\mathcal{X}} of …
Abstract Let <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>PG</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>r</m:mi><m:mo>,</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{PG}(r,q)} be the r -dimensional projective space over the finite field <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>GF</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{GF}(q)} . A set <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mi mathvariant="script">𝒳</m:mi></m:math> {\mathcal{X}} of points of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>PG</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>r</m:mi><m:mo>,</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{PG}(r,q)} is a cutting blocking set if for each hyperplane Π of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>PG</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mi>r</m:mi><m:mo>,</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{PG}(r,q)} the set <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi mathvariant="normal">Π</m:mi><m:mo>∩</m:mo><m:mi mathvariant="script">𝒳</m:mi></m:mrow></m:math> {\Pi\cap\mathcal{X}} spans Π. Cutting blocking sets give rise to saturating sets and minimal linear codes, and those having size as small as possible are of particular interest. We observe that from a cutting blocking set obtained in [20], by using a set of pairwise disjoint lines, there arises a minimal linear code whose length grows linearly with respect to its dimension. We also provide two distinct constructions: a cutting blocking set of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>PG</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mn>3</m:mn><m:mo>,</m:mo><m:msup><m:mi>q</m:mi><m:mn>3</m:mn></m:msup><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{PG}(3,q^{3})} of size <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mn>3</m:mn><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mrow><m:mi>q</m:mi><m:mo>+</m:mo><m:mn>1</m:mn></m:mrow><m:mo stretchy="false">)</m:mo></m:mrow><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mrow><m:msup><m:mi>q</m:mi><m:mn>2</m:mn></m:msup><m:mo>+</m:mo><m:mn>1</m:mn></m:mrow><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {3(q+1)(q^{2}+1)} as a union of three pairwise disjoint q -order subgeometries, and a cutting blocking set of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>PG</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mn>5</m:mn><m:mo>,</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{PG}(5,q)} of size <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mn>7</m:mn><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mrow><m:mi>q</m:mi><m:mo>+</m:mo><m:mn>1</m:mn></m:mrow><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {7(q+1)} from seven lines of a Desarguesian line spread of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mrow><m:mi>PG</m:mi><m:mo></m:mo><m:mrow><m:mo stretchy="false">(</m:mo><m:mn>5</m:mn><m:mo>,</m:mo><m:mi>q</m:mi><m:mo stretchy="false">)</m:mo></m:mrow></m:mrow></m:math> {\operatorname{PG}(5,q)} . In both cases, the cutting blocking sets obtained are smaller than the known ones. As a byproduct, we further improve on the upper bound of the smallest size of certain saturating sets and on the minimum length of a minimal q -ary linear code having dimension 4 and 6.
We develop three approaches of combinatorial flavor to study the structure of minimal codes and cutting blocking sets in finite geometry, each of which has a particular application. The first …
We develop three approaches of combinatorial flavor to study the structure of minimal codes and cutting blocking sets in finite geometry, each of which has a particular application. The first approach uses techniques from algebraic combinatorics, describing the supports in a linear code via the Alon--Füredi theorem and the combinatorial Nullstellensatz. The second approach combines methods from coding theory and statistics to compare the mean and variance of the nonzero weights in a minimal code. Finally, the third approach regards minimal codes as cutting blocking sets and studies these using the theory of spreads in finite geometry. By applying and combining these approaches with each other, we derive several new bounds and constraints on the parameters of minimal codes. Moreover, we obtain two new constructions of cutting blocking sets of small cardinality in finite projective spaces. In turn, these allow us to give explicit constructions of minimal codes having short length for the given field and dimension.
A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of …
A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis k minus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(k-1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-dimensional projective space over <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F Subscript q"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mi>q</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mathbb {F}_q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that have size at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c q k"> <mml:semantics> <mml:mrow> <mml:mi>c</mml:mi> <mml:mi>q</mml:mi> <mml:mi>k</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">c q k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for some universal constant <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c"> <mml:semantics> <mml:mi>c</mml:mi> <mml:annotation encoding="application/x-tex">c</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F Subscript q"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mi>q</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mathbb {F}_q</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-linear minimal codes of length <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and dimension <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, for every prime power <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q"> <mml:semantics> <mml:mi>q</mml:mi> <mml:annotation encoding="application/x-tex">q</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, for which <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-equal-to c q k"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>c</mml:mi> <mml:mi>q</mml:mi> <mml:mi>k</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \leq c q k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. This solves one of the main open problems on minimal codes.