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.