La decodifica della sindrome è un metodo di decodifica per i codici lineari . Utilizza una tabella, chiamata tabella standard, per eseguire la decodifica. Può essere utilizzato quando la ridondanza del codice non è eccessiva: la dimensione della tabella è esponenziale nella ridondanza.
Il principio è il seguente: al ricevimento di una parola x , la matrice di controllo consente di determinare se è stata commessa una modifica. In tal caso, la matrice di controllo fornisce una quantità chiamata sindrome ; la tabella standard fornisce una corrispondenza tra questa sindrome e la correzione e portare. Il messaggio corretto è quindi uguale a x - e .
Lo scopo di un codice di correzione è rilevare o correggere errori dopo la trasmissione di un messaggio . Questa correzione è resa possibile aggiungendo informazioni ridondanti. Il messaggio è incorporato in un insieme più grande, la differenza di dimensione contiene ridondanza, viene trasmessa l'immagine del messaggio dall'incorporamento. Se il messaggio è danneggiato, la ridondanza è progettata per rilevare o correggere gli errori. Un semplice esempio è quello del codice di ripetizione , il messaggio viene, ad esempio, inviato tre volte, la decodifica avviene tramite voto. Qui, l'insieme più grande ha una dimensione tripla rispetto a quella del messaggio iniziale.
Ricordiamo gli elementi di base della formalizzazione. Esiste uno spazio vettoriale E costituito da sequenze di valori in un campo finito F d e di lunghezza k , vale a dire che dal rango k , tutti i valori della sequenza sono pari a zero. Questi elementi sono lo spazio dei messaggi che vogliamo comunicare. Per fornire al messaggio la ridondanza desiderata, esiste una mappa lineare iniettiva φ di E con valori in F , lo spazio delle sequenze di lunghezza n con valori in F d . La funzione φ è chiamata codifica , φ ( E ) anche nota C è chiamata codice , un elemento di φ ( E ) parola del codice , n la lunghezza del codice e k la dimensione del codice. Queste annotazioni vengono utilizzate in tutto l'articolo.
La distanza di Hamming è lo strumento di base per la correzione degli errori. È espresso come distanza risultante da una pseudo-norma . Il peso di Hamming , che associa il numero di coordinate diverse da zero a un codice, svolge qui il ruolo di pseudo-norma.
La linearità della struttura sottostante introduce una proprietà diretta:
Per convincersene, è sufficiente notare che, se x ed y sono due parole del codice, allora la loro differenza è anche una parola del codice.
Pertanto, se un messaggio x ricevuto non è una parola in codice, si sono verificate alterazioni durante la trasmissione. L'obiettivo è trovare l'elemento e di F con il minor peso di Hamming, in modo tale che x - e sia una parola in codice. Se la probabilità di ricevere p errori durante una trasmissione è una funzione decrescente di p , la correzione è la più probabile.
Il numero massimo di errori sicuramente correggibili t deriva direttamente dalla distanza minima δ. Infatti, t è il numero intero più grande strettamente minore di δ / 2. La situazione ideale è quella in cui le sfere allegate centro le parole di codice e raggio t formano una partizione di F . Si parla quindi di perfetto .
Se il messaggio ricevuto contiene più di t errori, esiste un'alternativa:
La linearità semplifica notevolmente la decodifica. Per rendersene conto, il modo più semplice è studiare un esempio. Consideriamo un codice utilizzato dal minitel , binario di lunghezza 127 di dimensione 120 e di distanza minima 3 e perfetto. Se un messaggio m viene codificato e quindi inviato al destinatario, viene ricevuto un elemento x di F , suscettibile di errore.
Il numero t di errori massimi sicuramente correggibili è il più grande intero strettamente inferiore a 3/2, cioè t = 1. Poiché il codice è perfetto, le palline chiuse di centro le parole del codice e di raggio uno formano una partitura F . Di conseguenza, x è scritto in modo univoco come c + e dove c è una parola in codice ed e è un elemento di F di peso inferiore o uguale a uno . Se la probabilità di ottenere p errori durante la trasmissione è una funzione decrescente di p , c è probabilmente uguale a φ ( m ).
L'insieme dei possibili valori di e è relativamente piccolo, poiché il codice è binario, o e è il vettore zero, e non deve essere fatta alcuna correzione, oppure e è di peso uno , vale a dire che e è il messaggio contenente solo zeri tranne su una delle 127 coordinate che ne vale uno . Alla fine, ci sono solo 128 casi di errore in uno spazio contenente 2.127 elementi.
La linearità permette di limitarsi alla conoscenza della singola pallina chiusa di centro zero e raggio t , nell'esempio ad una pallina di 128 punti. Nel caso generale, una sfera chiusa di raggio t ha per cardinale V t (vedi terminale di Hamming ) :
La teoria dei codici correttivi afferma l'esistenza di una mappa lineare suriettiva di F in uno spazio di dimensione n - k la cui matrice H è detta matrice di controllo e il cui nucleo è il codice. Di conseguenza, abbiamo le seguenti uguaglianze:
Nel caso di un codice perfetto, la restrizione di H alla palla chiusa di centro vettore zero e raggio t è una biiezione . Qui, la matrice H è identificata dalla sua mappa lineare. Nel caso del minitel, l'unità ball contiene 128 punti, l'insieme di arrivo di H è uno spazio di dimensione 7 e quindi anche del cardinale 128.
I dati di una tabella, chiamata tabella standard associando ad ogni sindrome il suo unico antecedente con H nella sfera centrale il vettore zero e di raggio t , ne consentono la decodifica. La correzione dell'errore consiste nel sottrarre l'antecedente e dall'elemento F ricevuto. La parola in codice di ricerca è c = x - e . L'implementazione del computer di questo metodo utilizza una tabella hash ed è un metodo veloce di decodifica.
Nel caso generale, oltre al valore t del numero massimo di errori sicuramente correggibili, è necessario considerare il valore più piccolo s tale che le sfere chiuse di centro i punti del codice e del raggio s formino una sovrapposizione di F . Un codice è perfetto se e solo se s è uguale a t . H ha quindi le seguenti proprietà:
Vi sono poi due metodi di decodifica se H . t x non ammette un antecedente nella sfera chiusa di raggio t , o viene fatta una nuova richiesta di trasmissione, o un antecedente viene scelto a caso nella sfera chiusa di raggio s , e il metodo rimane lo stesso. In ogni caso, l'array standard contiene d n-k voci dove d è la cardinalità del campo finito.
L'approccio di decodifica della sindrome è adatto per codici piccoli , cioè quelli in cui il numero t di errori certamente correggibili non è troppo grande. Possiamo citare ad esempio alcuni protocolli utilizzati da Internet come TCP o anche Minitel che utilizza un codice perfetto di lunghezza 127 e distanza minima pari a 7.
D'altra parte, un codice che possiede una forte ridondanza e in grado di resistere a grandi cancellazioni, non può utilizzare questa tecnica di decodifica. Lo standard utilizzato dall'azienda Philips per il codice dei compact disc è in grado di ripristinare 4096 bit mancanti. La capacità di archiviazione di un'unità è troppo bassa per memorizzare le sindromi. Altre tecniche, basate essenzialmente sullo studio di polinomi formali con coefficienti in un campo finito, rappresentano gli approcci più utilizzati dall'industria.