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 \left\{0,1\right\}$. L'intero e è il più piccolo intero positivo tale che

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

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

La disuguaglianza di Singleton afferma che

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

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