Codice MDS

Template:F 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(\genfrac{}{}{0ex}{}{n}{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 \{0,1\}$

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

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

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

$\rho (x,y):=|\{i:x_i\ne y_i\}|$

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):=\{x\in H[n,2]:\rho (x,c)\le r\}$

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$.