Disuguaglianza di Singleton

Questa voce sull'argomento matematica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

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 ${\displaystyle \ C}$ un sottospazio dello spazio di Hamming di dimensione n:

${\displaystyle \ C\subseteq H[n,2]}$

il cui generico elemento è ${\displaystyle \ x=(x_{1},x_{2},...,x_{n})}$ con ${\displaystyle \ x_{i}\in \left\{0,1\right\}}$. L'intero e è il più piccolo intero positivo tale che

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

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

La disuguaglianza di Singleton afferma che

${\displaystyle \ |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).

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica