## Séminaire Algorithmique |

Le séminaire a lieu **le mardi à 11 h 45** (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

# Résumé du
séminaire du
Mardi 28 Février 2017
à **10:15**

*Choosing parameters in coding theory with a focus on Griesmer bound*

## par Eleonora Guerrini

Shannon says that error correcting codes performing a given channel exist, but no explicit construction is given. Nowadays, it is still hard to know what is feasible with respect to given parameters as the size of the alphabet, the rank of the code and the correction capability.

The problem of bounding the size of a code heavily depends on
the code family that we are considering. We can define three types
of block codes: linear codes, systematic codes and non-linear
codes. Systematic codes form a less-studied family of non-linear
codes, sharing properties with linear codes. The size of a
systematic code is directly comparable with that of a linear code,
since it is a power of the field size. Recent results on systematic
codes prove that if a linear code admits an extension (where both
the length and the distance are increased exactly by 1), then it
admits also a linear extension. Therefore, we observe that, if by
puncturing a systematic code *C* we obtain a linear code, then
there exists a linear code with the same parameters as
*C*.

In this talk we are interested in bounds on the size of a code that can be obtained by a closed-form expression, evec if other algorithmic bounds exist (e.g. the Linear Programming bound ). The academic literature reports only one bound for linear codes, the Griesmer bound, no bounds for systematic codes and many bounds for non-linear codes. Since the Griesmer bound is specific to linear codes, we would expect it to beat the other bounds, but this does not happen in general, except in some cases. So we have an unexpected situation where the bounds that hold for the more general case are numerous and beat bounds that hold for the specialised case.

The Griesmer bound, which can be seen as an extension of the
Singleton bound in the linear case, was introduced by Griesmer in
the case of binary linear codes and then eneralised by Solomon and
Stiffler to the case of q−ary linear codes. It is known that the
Griesmer bound is not always sharp. We present some results on
systematic codes and their relations to (possible extensions of)
the Griesmer bound. We prove that, once q and d have been chosen,
if all nonlinear systematic codes with *k* ≤ 1 + log
*q*(*d*) respect the Griesmer bound, then the Griesmer
bound holds for all systematic codes with the same *q* and
*d*. Therefore, for any *q* and *d* only a finite
set of (*k*, *n*) pairs has to be analysed in order to
prove the bound for all *k* and *n*. We also try to point
out known results on codes having parameters reaching classical
bound and some related open problems.