Disuguaglianza di Singleton

Da Wikipedia, l'enciclopedia libera.

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| \le \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).

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