Codice MDS

Un codice MDS (Maximum Distance Separable) è un codice per cui la diseguaglianza di Singleton vale come uguaglianza, ovvero: | C | = 2 n ∑ k = 0 e ( n k ) {\displaystyle \ |C|={\frac {2^{n}}{\sum _{k=0}^{e}{n \choose k}}}} Dove: C {\displaystyle \ C} è un Codice binario, sottoinsieme di uno spazio di Hamming a dimensione n: C ⊆ H [ n , 2 ] {\displaystyle \ C\subseteq H[n,2]} Il cui generico elemento è x = ( x 1 , x 2 , . . . , x n ) {\displaystyle \ x=(x_{1},x_{2},...,x_{n})} con x i ∈ { 0 , 1 } {\displaystyle \ x_{i}\in \left\{0,1\right\}} e {\displaystyle \ e} è il massimo numero di errori che il codice è in grado di correggere, ovvero detta d ( C ) {\displaystyle \ d(C)} la distanza minima del codice: d ( C ) ≥ 2 e + 1 {\displaystyle \ d(C)\geq 2e+1} Una volta definite la distanza tra due parole x e y di H [ n , 2 ] {\displaystyle \ H[n,2]} : ρ ( x , y ) := | { i : x i ≠ y i } | {\displaystyle \ \rho (x,y):=|\left\{i:x_{i}\neq y_{i}\right\}|} e l'insieme sfera di centro c e raggio r comprendente le parole di H [ n , 2 ] {\displaystyle \ H[n,2]} aventi distanza da c {\displaystyle \ c} minore o uguale a r: S ( c , r ) := { x ∈ H [ n , 2 ] : ρ ( x , c ) ≤ r } {\displaystyle \ S(c,r):=\left\{x\in H[n,2]:\rho (x,c)\leq r\right\}} La prima relazione implica che l'intero spazio H [ n , 2 ] {\displaystyle \ H[n,2]} è partizionabile in sfere di raggio e {\displaystyle \ e} centrate su elementi del codice C {\displaystyle \ C} , ovvero non esistono elementi di H [ n , 2 ] {\displaystyle \ H[n,2]} che non cadano in una (e una sola) sfera di raggio e {\displaystyle \ e} centrata su un qualche elemento c ∈ C {\displaystyle \ c\in C} .

Questa voce o sezione sull'argomento teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Un codice MDS (Maximum Distance Separable) è un codice per cui la diseguaglianza di Singleton vale come uguaglianza, ovvero:

  | C | = 2 n ∑ k = 0 e ( n k ) {\displaystyle \ |C|={\frac {2^{n}}{\sum _{k=0}^{e}{n \choose k}}}}

Dove:

•   C {\displaystyle \ C} è un Codice binario, sottoinsieme di uno spazio di Hamming a dimensione n:

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

Il cui generico elemento è   x = ( x 1 , x 2 , . . . , x n ) {\displaystyle \ x=(x_{1},x_{2},...,x_{n})} con   x i ∈ { 0 , 1 } {\displaystyle \ x_{i}\in \left\{0,1\right\}}

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

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

Una volta definite la distanza tra due parole x e y di   H [ n , 2 ] {\displaystyle \ H[n,2]} :

  ρ ( x , y ) := | { i : x i ≠ y i } | {\displaystyle \ \rho (x,y):=|\left\{i:x_{i}\neq y_{i}\right\}|}

e l'insieme sfera di centro c e raggio r comprendente le parole di   H [ n , 2 ] {\displaystyle \ H[n,2]} aventi distanza da   c {\displaystyle \ c} minore o uguale a r:

  S ( c , r ) := { x ∈ H [ n , 2 ] : ρ ( x , c ) ≤ r } {\displaystyle \ S(c,r):=\left\{x\in H[n,2]:\rho (x,c)\leq r\right\}}

La prima relazione implica che l'intero spazio   H [ n , 2 ] {\displaystyle \ H[n,2]} è partizionabile in sfere di raggio   e {\displaystyle \ e} centrate su elementi del codice   C {\displaystyle \ C} , ovvero non esistono elementi di   H [ n , 2 ] {\displaystyle \ H[n,2]} che non cadano in una (e una sola) sfera di raggio   e {\displaystyle \ e} centrata su un qualche elemento   c ∈ C {\displaystyle \ c\in C} .

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