Pesi di Hamming generalizzati

Abstract

I pesi di Hamming generalizzati di un codice lineare sono una generalizzazione naturale della nozione di distanza minima, che hanno alcune applicazioni nella crittografia basata sui codici, per esempio nei canali wire-tap di tipo II. Vedremo come associare un matroide ad ogni codice lineare e come la nozione di peso di Hamming si può generalizzare ai matroidi in modo naturale. Faremo quindi uso della teoria dei matroidi e di alcuni risultati di algebra commutativa per legare i pesi di Hamming di un matroide ai numeri di Betti del suo anello di Stanley-Reisner, attraverso un importante risultato di Johnsen e Verdure. Vedremo anche come i pesi di Hamming di un matroide sono legati a quelli del suo duale, tramite un risultato che generalizza un famoso teorema di Wei. Infine, noteremo che utilizzare il teorema di Johnsen e Verdure per calcolare i pesi di Hamming di un codice è molto inefficiente, e presenteremo un approccio diverso basato sulla teoria delle basi di Grobner, che è ancora un'area aperta di ricerca.

The generalised Hamming weights of a linear code are a natural generalisation of the notion of minimum distance, which have some applications in the context of code-based cryptography, for example to type II wire-tap channels. We will see how to associate a matroid to each linear code and how the notion of generalised Hamming weight naturally carries over to matroids. This will allow us to use techniques from commutative algebra and matroid theory to relate the generalised Hamming weights of a matroid to the Betti numbers of its associated Stanley-Reisner rings, through a famous result of Johnsen and Verdure. Along the way, we will also see how to relate the Hamming weights of a matroid to those of its dual, in a way that generalises a famous result of Wei. Finally, we notice that using Johnsen-Verdure's theorem to calculate the generalised Hamming weights of a code is very inefficient, and study a different approach based on the theory of Grobner bases, which is still an open area of research.