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.
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
[modifica | modifica wikitesto]Si consideri un campo di Galois GF(q), con q numero primo. Tale costituirà l'alfabeto Fq, i cui elementi andranno a comporre le varie parole del codice. Fqn costituisce quindi uno spazio vettoriale V(n,q). Un vettore (x1, x2, ..., xn) può essere scritto semplicemente come x1, x2, ..., xn. 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 qk 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
[modifica | modifica wikitesto]- (EN) Eric W. Weisstein, Linear Code, su MathWorld, Wolfram Research.
