Disuguaglianza di Singleton

La disuguaglianza di Singleton collega la cardinalità di un codice binario a correzione d'errore C con e, il massimo numero di errori sui bit che compongono il messaggio che il codice stesso consente di correggere. Sia $C$ un sottospazio dello spazio di Hamming di dimensione n:

$C\subseteq H[n,2]$

il cui generico elemento è $x=(x_1,x_2,...,x_n)$ con $x_i\in \{0,1\}$. L'intero e è il più piccolo intero positivo tale che

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

dove $d(C)$ denota la minima distanza di Hamming tra due elementi del codice.

La disuguaglianza di Singleton afferma che

$|C|\le \frac{2^n}{\sum _{k=0}^e(\genfrac{}{}{0ex}{}{n}{k})}$ .

Un codice per il quale la disuguaglianza vale con il segno di uguale è detto codice MDS (Maximum Distance Separable).