Questa cosa era nell'esame di oggi di
Teoria dei Codici 
!
Non penso che sia richiesto questo livello di esplicitazione
, ma visto che ho questo teorema ancora fresco in testa, lo scriverò
.
Def. Poniamo
Def. Siano
Poniamo
=|\{i:x_i\not{=}y_i\}|)
e chiamiamo
distanza di Hamming
Def. Sia
codice lineare (i codici di Hamming sono esempi di codici lineari)
Poniamo
=\min\{{d(\vec{x}, \vec{y}): \vec{x}, \vec{y}\in{\mathbb{F}_2}^n, \vec{x}\not{=}\vec{y}}\})
cioè
)
è la distanza minima fra tutte le distanze calcolate su parole 2 a 2
diverse e del codice.
Def. Sia
codice lineare
e siano
parola trasmessa e
parola ricevuta (attraverso un canale rumoroso, cioè che lascia i bit trasmessi soggetti a errore)
Allora il
decoder ottimale è una funzione che manda la parola
nella parola
tale che:
=\min{\{d(\vec{y}, \vec{z}): \vec{z}\in C}\})
Teorema Sia
codice lineare
e siano
parola trasmessa e
parola ricevuta (attraverso un canale rumoroso, cioè che lascia i bit trasmessi soggetti a errore)
Sia
)
il numero di bit cambiati in trasmissione (errore) e valga
-1}{2})
, equivalentemente detto
-1)
Allora 
ottenuto dal decoder ottimale è tale che:
Dim.Ricordiamo che
e consideriamo che
=\min{\{d(\vec{y}, \vec{z}): \vec{z}\in C}\}\leq d(\vec{y}, \vec{x}))
poiché essendo che
, allora
\in{\{d(\vec{y}, \vec{z}): \vec{z}\in C}\})
e qualsiasi elemento di un insieme ordinato è maggiore o uguale al minimo di tale insieme.
Stimiamo, allora, il valore
)
\leq_1 d(\vec{x}, \vec{y})+d(\vec{y}, \vec{x'})=_2 e+d(\vec{y}, \vec{x'})\leq_3 e+e=2\cdot e\leq d(C)-1<d(C))
: applicazione della proprietà triangolare delle distanze (e la distanza di Hamming
è una distanza valida), che dice che la distanza tra due elementi è minore o uguale della somma delle distanze di tali elementi rispetto a un terzo elemento qualsiasi.
:
=e)
: poiché valeva
=\leq d(\vec{y}, \vec{x})=e\;\Rightarrow\; d(\vec{y}, \vec{x'})\leq e)
Compattando la catena di diseguaglianze, leggiamo
<d(C))
ma
era la distanza
minima fra parole
diverse del codice, perciò se la distanza tra queste due parole è minore di questa distanza minima, allora queste parole
e
sono necessariamente
uguali, cioè
viene corretta nella parola
che era la parola originariamente trasmessa e su cui si sono verificati, al più,
-1}{2})
errori.
Tutte queste considerazioni si possono fare anche se il campo su cui il codice lineare non è
ma un qualsiasi campo finito.
EDIT: ho tolto due definizioni e un teorema non dimostrato che in effetti non usavo 
