Codice lineare

In matematica ed in teoria dell'informazione un codice lineare è un'importante tipologia di codice a blocchi usato negli schemi per la rilevazione e la correzione d'errore. I codici lineari consentono di realizzare algoritmi di codifica e decodifica più efficienti rispetto alle altre tipologie di codici.

I codici che costituiscono un codice lineare sono blocchi di simboli (tipicamente bit), i quali sono codificati utilizzando dei simboli in più rispetto a quelli che compongono il messaggio originale; si aggiunge cioè della ridondanza. Quest'ultima consente a colui che riceve il messaggio di individuare l'errore e, a seconda del numero di errori e del tipo di codice utilizzato (cioè se si sta usando una rilevazione d'errore o a correzione d'errore), eventualmente di correggerlo. Naturalmente quanti più simboli di ridondanza vengono aggiunti a ciascun blocco, tanto maggiore sarà la quantità di errori che sarà possibile rilevare e correggere per ciascuno di essi.

Definizione

Si consideri un campo di Galois GF(q), con q numero primo. Tale costituirà l'alfabeto F_q, i cui elementi andranno a comporre le varie parole del codice. F_qⁿ costituisce quindi uno spazio vettoriale V(n,q). Un vettore (x₁, x₂, ..., x_n) può essere scritto semplicemente come x₁, x₂, ..., x_n. Si definisce codice lineare sopra GF(q) un sottospazio di V(n,q). Chiamiamo tale sottospazio codice lineare C.

Se q=2 il codice sarà detto codice lineare binario.

Un codice lineare è descritto solitamente da una terna di parametri [n, k, d]_q: n indica la dimensione dello spazio vettoriale che contiene C ed è chiamato lunghezza del codice. k rappresenta la dimensione del codice, e q^k rappresenta il numero di parole che costituiscono il codice (e quindi il numero di parole che è possibile codificare per mezzo del codice scelto). Infine d indica la distanza (intesa nel senso di Distanza di Hamming) minima tra due parole del codice.

Collegamenti esterni

• (EN) Eric W. Weisstein, Codice lineare, su MathWorld, Wolfram Research.