Codice MDS

Un codice MDS (Maximum Distance Separable) è un codice per cui la diseguaglianza di Singleton vale come uguaglianza, ovvero:

$\ |C|={\frac {2^{n}}{\sum _{k=0}^{e}{n \choose k}}}$

Dove:

• $\ C$ è un Codice binario, sottoinsieme di uno spazio di Hamming a dimensione n:

$\ C\subseteq H[n,2]$

Il cui generico elemento è $\ x=(x_{1},x_{2},...,x_{n})$ con $\ x_{i}\in \left\{0,1\right\}$

• $\ e$ è il massimo numero di errori che il codice è in grado di correggere, ovvero detta $\ d(C)$ la distanza minima del codice:

$\ d(C)\geq 2e+1$

Una volta definite la distanza tra due parole x e y di $\ H[n,2]$:

$\ \rho (x,y):=|\left\{i:x_{i}\neq y_{i}\right\}|$

e l'insieme sfera di centro c e raggio r comprendente le parole di $\ H[n,2]$ aventi distanza da $\ c$ minore o uguale a r:

$\ S(c,r):=\left\{x\in H[n,2]:\rho (x,c)\leq r\right\}$

La prima relazione implica che l'intero spazio $\ H[n,2]$ è partizionabile in sfere di raggio $\ e$ centrate su elementi del codice $\ C$, ovvero non esistono elementi di $\ H[n,2]$ che non cadano in una (e una sola) sfera di raggio $\ e$ centrata su un qualche elemento $\ c\in C$.