2.1 Introduzione ai principali codici a correzione di errori

38

Capitolo 2 - Rilevazione e correzione d'errori

2.1 Introduzione ai principali codici a correzione di errori

Tutti i tipi di codici a correzione d'errore, da qui in avanti ECC (Error-Correcting Code), sono basati su un comune principio basilare che è quello di aggiungere ridondanza al messaggio informativo al fine di rilevare ed eventualmente correggere l'errore che può manifestarsi nel processo di memorizzazione o di trasmissione dati. A seconda del procedimento di costruzione della simbologia di ridondanza si differenziano varie tipologie di codice che verranno analizzate di seguito.

In generale, un codice è un set di parole di codice, dette codewords, ognuna di lunghezza n, numero di simboli o bit. L'informazione vera e propria, invece, è un parola costituita da una sequenza di k simboli o bit, con < . Un codice è detto sistematico se ogni sua codeword contiene al proprio interno la corrispondente sequenza di k simboli di informazione non mescolata con la simbologia di parità. In particolare la quasi totalità dei codici utilizzati è sistematica e utilizza la nota convenzione che vede le prime k posizioni della parola di codice occupate dalla word di informazione, mentre le ultime − riservate ai simboli di ridondanza.

k simboli (informazione) n-k simboli (parità)

Figura 2 .1- Codeword sistematica di lunghezza n simboli.

Con l'acronimo ECC (Error-Correcting Code) o EDAC (Error Detecting And Correcting code) ci si riferisce a tutti quei tipi di codice in grado di rilevare e correggere un numero prestabilito di errori nella sequenza del messaggio in ricezione. Dal momento che una rivelazione d'errore scaturisce da una qualunque differenza fra il messaggio ricevuto e una qualsiasi codeword del codice utilizzato, risulta ovvio che un codice ECC

è

1 I codici ECC sono anche noti con l'acronimo di FEC (Forward Error Correction).

39

necessariamente un codice EDAC nel senso che ha intrinsecamente la capacità di scovare errori per poi eventualmente correggerli.

Assumendo che, ai fini pratici di questo studio, le informazioni da correggere sono sequenze di bit, possiamo inizialmente limitarci all'analisi di algoritmi ECC binari operanti su un campo di Galois di ordine 2. Un campo di Galois (1) è, molto brevemente, una struttura algebrica con le proprietà ordinarie di un campo, la cui cardinalità è detta 'ordine'.

Quindi un campo di Galois di ordine due è un campo costituito da 2 soli elementi che nel nostro caso sono il bit '0' e il bit '1'. A tale campo finito ci si riferisce con il termine (2), il cui intero tra parentesi indica la cardinalità del campo. Le operazioni di somma e prodotto, che definiscono il campo di Galois così decritto, sono l'operazione di 'OR esclusivo' (

) e il prodotto 'AND'(  ). Si indicherà questa struttura algebrica con la simbologia (2) = ({1,0} ,

,  ).

E' possibile, a questo punto, introdurre il concetto di linearità del codice: se un codice , costituito dalle sue codewords lunghe n simboli, è contenuto nello spazio di tutte le parole lunghe n, allora il codice si dice lineare. In formule, indicando con (2) l'insieme di tutte le possibili sequenze di bit lunghe n, si ha:

⊆ (2) . In altre parole si dice che è un sottospazio di (2) .

Un qualsiasi codice lineare è analizzabile considerando una sola funzione biiettiva f che associa ad ogni parola d'informazione, un'unica codeword e viceversa. Tutte le parole di informazione costituiscono lo spazio (2) , quindi si definisce la funzione f :

: (2) → .

Tutti i tipi di codice di interesse pratico sono lineari; lo studio sui codici ECC è pertanto limitato ai suddetti tipi di codice e, pertanto, la proprietà di linearità verrà sottintesa.

Le proprietà enunciate finora hanno validità generale e sono riscontrabili in qualunque tipo di codice ECC. Da qui in avanti, invece, saranno analizzati in maniera distinta tutti i principali tipi di codice a correzione d'errore che sono distinguibili in due grosse categorie:

i codici a blocchi e i codici convoluzionali.

40

2.2 Codici a blocchi

2.2.1 Descrizione generale dei codici a blocchi

Un sistema che adotta una codifica a blocchi, o block codes, processa l'informazione a blocchi di simboli, trattando ogni blocco di k simboli in maniera indipendente dagli altri.

L'operazione di encoding, quindi, risulta memoryless, in contrapposizione al processo di codifica convoluzionale basato, appunto, sulla memoria dell'encoder (ved. par. 2.3).

Ovviamente, un encoder di un codice a blocchi è sicuramente dotato di memoria nel senso che comprende elementi con memoria ed è in generale una macchina a stati finiti, ma in riferimento alle codewords (e non ai singoli bit che le compongono) è possibile classificare i codici a blocchi come memoryless.

Ogni block code è contraddistinto dalla terna ( , , ) che ne caratterizza le prestazioni:

 n : la lunghezza del codice. È il numero di simboli di cui è composta la codeword;

 k : la dimensione del codice. È il numero dei simboli di cui è composta la word di informazione;

 d

: la distanza minima di Hamming. È un parametro di merito che definisce la distanza minima fra 2 parole di codice.

Un codice binario

, la cui terna sia ( , , ), è composto da 2 codewords che possono essere pensate come stringhe, o meglio vettori, di n bit. In formule:

∀ ∈ , = ( , , … , ) ∈ (2).

Il numero k è il numero di vettori della base che forma il codice , la cui cardinalità 2 è detta taglia del codice.

Il rapporto / è il code rate ed è un parametro di merito del codice in quanto definisce il rapporto fra il numero di simboli informativi e il numero totale di simboli della parola di

2 Un codice binario è un codice con alfabeto binario in cui ogni componente dei vettori codewords sono i numeri '1' e '0'. Discorsi analoghi valgono per un codice con alfabeto q-ario.

41

codice prodotta dall'encoder; vale, ovviamente, la disuguaglianza < 1. Come è facile intuire, questo parametro è in trade-off con la capacità di correzione del codice. Molti codici, soprattutto i convoluzionali, sono ben lontani dal limite unitario e si assestano in gran parte intorno allo 0.5.

2.2.2 Distanza di Hamming ed Error-Correcting Capability

La distanza minima di Hamming d

è il parametro più importante per valutare le prestazioni di un codice e, in genere, un codice che, a parità di lunghezza e dimensione, ha una distanza maggiore è da preferirsi prestazionalmente

.

In uno spazio vettoriale binario

, la distanza di Hamming fra due vettori è definita come il numero di componenti differenti valutate in modo ordinato, componente per componente. Siano, quindi, = ( , , … , ) e = ( , , … , ) due vettori appartenenti a (2) , si definisce la distanza di Hamming fra i due vettori:

( , ) = ({ : ≠ , 0 ≤ ≤ − 1}) dove con "card(A)" si intende la funzione cardinalità dell'insieme A.

La distanza di Hamming è quindi una funzione a valori interi e, inoltre, gode delle proprietà di una norma nello spazio (2) .

In un codice , la distanza minima d

è definita come la minima distanza di Hamming fra tutte le possibili coppie distinte di codewords. In formule:

= ( , ) ∶ , ∈

≠

Un codice che ha una d

più alta possibile, è costituito da parole che distano (nel senso di Hamming) di un numero di componenti più alto possibile. Fissata la distanza minima, si ha che quel codice potrà rilevare al massimo − 1 errori in una singola parola (che

3 Questa valutazione è generica, in realtà in base alle "condizioni di lavoro" di un sistema di encoding/decoding si può preferire un codice che ha una dmin relativamente bassa ma che garantisce altri vantaggi. I Turbo Codici ne sono un esempio (2).

4 La definizione data vale anche in uno spazio q-ario.

42

necessariamente sarà una word non corrispondente a nessun vettore appartenente a ).

Ne segue che un codice è tanto più performante quanto più le sue codewords sono distanti fra di loro.

Si definisce, inoltre, il peso di Hamming w

di una word appartenente a (2) , come il numero di componenti del vettore non nulle. In un codice , il peso di una codeword è:

( ) = ( , )

dove il vettore nullo è la codeword composta da elementi tutti nulli

.

È dimostrabile che, per qualunque codice lineare, il calcolo della distanza minima di Hamming è riconducibile semplicemente alla ricerca della codeword non nulla con peso di Hamming più piccolo possibile:

= ( ), ∈

≠ .

Si definisce sfera di Hamming ( ) di raggio r e centro , l'insieme di quei vettori in (2) che distano meno di r dalla codeword .

( ) = {  | ( , ) ≤ }.

Si ha che, la cardinalità della sfera di Hamming è un parametro chiave per le prestazioni di un codice lineare, in quanto il numero di elementi della sfera centrata in è proprio il numero di word che il codice potrà correggere restituendo quella determinata codeword

6

.

Il parametro Error-Correcting Capability, t, di un codice , è definito come il più grande raggio delle sfere di Hamming ( ) centrate su tutte le parole di codice ∈ , tale che le sfere siano tutte disgiunte. La richiesta di sfere non coincidenti esplicita la capacità del codice di "tradurre" un qualsiasi vettore che cade in una determinata sfera centrata in , con la stessa codeword e nessun'altra .

I due parametri di Error-Correcting Capability e distanza minima di Hamming sono legati dalla relazione:

=

(2.1)

5 La codeword appartiene necessariamente al codice perché, per la proprietà di linearità, è un sottospazio di GF(2)ⁿ.

6 Se queste distano meno di un certo numero detto Error-Correcting Capability; ved. più avanti.

43 dove con ⌊ si denota la parte intera di x.

La cardinalità di una sfera di Hamming centrata in una parola di codice e di raggio t è, quindi, il numero di vettori in (2) che saranno effettivamente corretti con la codeword . Il numero di vettori contenuti nella sfera ( ) di centro e di raggio t è dato dalla relazione:

( ) = ∑ .

Ovviamente si ha:

⋃ ( ) ⊆ (2) (2.2)

cioè, l'unione di tutte le sfere di Hamming di raggio t centrate in tutte le 2 codewords è contenuta nello spazio vettoriale (2) . Se le sfere, che costituiscono un ricoprimento dello spazio (2) , sono tali che la loro unione restituisce l'intero spazio vettoriale, allora si parla di una partizione di (2) e, il codice costituito da quelle codewords, si dice perfetto. Quello enunciato nella formula (2.2) è il limite di Hamming, o Hamming Bound, che, riscritto in una forma più nota, diventa (2):

∑ ≤ 2 (2.3)

valida per un codice binario

.

La disuguaglianza precedente ha diverse interpretazioni

; la più generale riguarda il limite massimo del numero di vettori correggibili da un codice binario con lunghezza e dimensione fissata. Un codice perfetto

è un codice per il quale la (2.3) diventa un'uguaglianza e nel quale ogni vettore appartenente a (2) può essere corretto con una specifica codeword a meno di una distanza fra i due pari a t. Il parametro t, in altre parole, indica il peso massimo del vettore errore che è possibile correggere. Una parola ricevuta, , è di fatto analizzabile come la relativa codeword , sommata (modulo-2) all'eventuale vettore errore :

= ⨁ (2.4)

7 Per codici non binari, definiti su un alfabeto q-ario (con q = p^m con p numero primo), l'Hamming Bound

diventa:





 



 

t



i

i

n

0

(q - 1)ⁱ ≤ q^{n - k}.

8 Ne verrà data un'altra più avanti legata al concetto di sindrome.

9 E' dimostrabile che il parametro dmin di un codice perfetto è necessariamente un numero dispari (1).

44

Se il peso di è minore di t, allora la parola ricevuta sarà correttamente decodificata come . Dal momento che il vettore errore non è nient'altro che una sequenza di bit '1' (nelle relative locazioni dove ci sono errori) e bit '0' (nelle corrispondenti locazioni senza errori) si parla anche di Error-Correcting Capability come numero massimo di bit-error random o bit-error-pattern che il codice è capace di correggere. In letteratura sono elencati tutti codici perfetti che, a parte quelli banali, sono principalmente costituiti da 2 famiglie: i codici di Hamming (par. 2.2.4) e i codici di Golay binario e ternario (par.

2.2.5).

Riassumendo, un codice a blocchi definito dalla terna ( , , ) può:

 rilevare fino a − 1 errori;

 correggere un massimo di t errori random.

I parametri delle terna non sono indipendenti; una prima relazione fra di essi è data dalla disuguaglianza di Singleton :

≤ − + 1. (2. 5)

La relazione di Singleton, di fatto, fissa un limite massimo alla distanza minima di Hamming, in funzione della lunghezza n e della dimensione k del codice. A parità di n e k, i codici che hanno massima vengono detti codici MDS (Maximum Distance Separable). Fra i principali codici MDS si annoverano i codici a ripetizione ( , 1, ) e i codici Reed-Solomon.

2.2.3 Encoding e decoding di codici a blocchi

Per una trattazione più generale, d'ora in avanti si assume come alfabeto del codice, un

campo finito ( ), cioè un insieme formato da q elementi con le proprietà di un campo

rispetto alle due operazioni di somma e prodotto. Dalla teoria di Galois (3), affinché la

struttura algebrica su cui si opera sia realmente un campo, è necessario che il numero q

sia una potenza di un numero primo p: = . Senza addentrarsi troppo in sottigliezze

matematiche, se ne conclude che:

45

 se = 1, ( ) = ℤ , con ℤ : le classi di resto modulo p, dove vale l'aritmetica modulare. Ad esempio il campo (2) = ℤ , dove ℤ è la classe di resto modulo 2, formata dagli interi '0' e '1'. In questi casi si parla di Campo di Galois primo perché la sua cardinalità è un numero primo (p).

 se > 1, allora esiste un polinomio f(x) di grado pari a m e irriducibile sull'anello dei polinomi ℤ [ ], tale che ( ) = ℤ [ ] / ( ), dove ℤ [ ] / ( ) è il campo dei polinomi modulo f(x), a coefficienti in ℤ . Ad esempio per

= 2 = 3, si ha (2 ) = ℤ [ ] / ( + + 1). Il campo (8) sarà formato quindi da 8 elementi che sono dei polinomi di grado massimo pari a 3, a coefficienti appartenenti al campo finito ℤ .

L'insieme ( ) dei vettori di lunghezza n con componenti polinomiali (o scalari) in ( ) ha quindi una struttura intrinseca di spazio vettoriale su ( )

. Come risultato pratico si ha che le operazioni di codifica e decodifica sono riconducibili a note tecniche dell'algebra lineare; in particolare le operazioni di encoding/decoding si traducono in operazioni matriciali, che in termini di circuitistica digitale significano porte logiche e shift register.

Dal momento che ogni codice lineare con terna ( , , ) è un sottospazio vettoriale di ( ) di dimensione k, è sempre possibile trovare almeno una base dello spazio costituita da k vettori lunghi n. Ogni codeword è una combinazione lineare della base scelta e la relazione di generazione del codice può essere vista come un'operazione matriciale fra ogni vettore informativo lungo k simboli e una matrice detta matrice generatrice , la quale ha, come righe, i vettori costituenti la base del codice . Indicando con il vettore informativo lungo k e con la relativa sequenza codificata, si ha:

∀ ∈ ( ) , = (2.6) con matrice Generatrice di ordine × del tipo:

10 Ogni spazio vettoriale è costruito su una struttura algebrica che deve avere le proprietà di un campo.

46

=

, ,

…

, ,

…

⋮ ⋮ ⋮ ⋮

, ,

…

(2.7)

e il vettore riga :

= ( , , , … , ) ∈ ( ).

Ricordando che la scelta della base non è unica, si ha che più codici possono avere la stessa terna ma matrici generatrici diverse: si parla di codici equivalenti. Formalmente, un codice è equivalente ad un altro se, a partire dalla matrice generatrice , si arriva alla matrice con un numero finito di operazioni quali permutazione di colonne, permutazione di righe, moltiplicazione per uno scalare (1).

Spesso, nelle applicazioni concrete, viene utilizza una codifica sistematica, avvalendosi di una matrice generatrice in una forma detta, appunto, sistematica. Tramite le operazioni elencate precedentemente, è possibile passare dalla forma (2.6) a quella sistematica:

=

























1 ...

0 0

...

...

...

...

...

...

1 0

0 ...

0 1

P

(2.8)

che prevede la concatenazione della matrice identità (matrice quadrata di ordine k con tutti '1' sulla diagonale principale) con la matrice di ordine × ( − ) detta sottomatrice di parità, responsabile della sequenza di ridondanza. In breve si indica

= ( | ) .

La sistematicità del codice presenta vantaggi nel processo di decodifica perché, una volta corretti gli eventuali errori nella sequenza ricevuta, per ricavare i k simboli informativi dalla codeword stimata è sufficiente scartarne gli ultimi − . Per quanto riguarda l'encoder, adottare un codice sistematico non cambia sostanzialmente la complessità del circuito.

Per ogni codice , ottenuto come sottospazio di ( ) , esiste un (unico) codice duale di dimensione − , costituito da tutti quei vettori appartenenti a ( ) ortogonali alle parole del codice . In algebra si parla di come il sottospazio ortogonale a e vale:

= { ∈ ( ) : ∙ = 0, ∀ }.

47

Senza ricadere in finezze matematiche sulle proprietà del prodotto scalare nel mondo ( ) , ci basti sapere che è possibile definirlo nel seguente modo:

∀ , ( ) , ∙ = ∑ ∈ ( ) .

Si definisce, in maniera del tutto analoga a quanto fatto inizialmente per , una matrice di ordine ( − ) × , , generatrice del codice , la quale, rispetto al codice , è detta matrice di parity-check. Questa matrice è utilizzata in sede di decodifica del codice , in quanto vale la seguente proprietà:

∀ ∈ , = . (2.9)

Tale uguaglianza indica che ogni parola del codice , moltiplicata per la matrice trasposta, restituisce il vettore nullo. Sfruttando tale concetto, in fase di decodifica si ha che tutti i vettori ricevuti che verificano l'uguaglianza (2.9) sono codewords valide, mentre un risultato diverso dal vettore nullo indica che la sequenza ricevuta è affetta da errore. Se ha la matrice generatrice in forma sistematica, allora trovare la corrispondente matrice di parità è facilmente ricavabile nel seguente modo:

= (− | ) (2.10)

Il processo di decodifica di qualunque codice a blocchi è legato al concetto di sindrome. Dato un messaggio ricevuto , la sindrome corrispondente ( ) è definita come:

( ) = .

Il vettore sindrome ( ) appartiene a ( ) e identifica l'entità dell'errore contenuto nel messaggio ricevuto indipendentemente dalla codeword specifica. In un codice binario, la sindrome del messaggio ricevuto è riscrivibile come

:

( ) = = ( ⨁ ) = (2.11)

dove si evince che la sindrome dipende solo dal tipo di errore che interessa la parola ricevuta e che la sindrome calcolata è nulla, se la parola ricevuta è una parola di codice.

Un codice con terna ( , , ) ha una corrispondenza univoca fra ogni sindrome e ogni errore di peso massimo t. È ora possibile dare un secondo significato al limite di Hamming introdotto precedentemente. Dal momento che, in un codice binario, il numero di sindromi è pari a 2 , il limite di Hamming è interpretabile così:

11 Si può dimostrare che la relazione (2.11) è valida anche in alfabeti di codice q-ari.

48

il numero di sindromi, 2 , di un codice è maggiore o uguale al numero di error-

pattern correggibili ∑ ≤ 2 (2.3).

I codici perfetti sono quindi quelli che, verificando l'uguaglianza di Hamming, hanno un numero di sindromi pari al numero di error-pattern correggibili (compresa la sindrome nulla che indica l'assenza di errori). In particolare si ha che, un codice perfetto è tale che, ad ogni vettore errore di peso minimo è associato il suo unico vettore sindrome corrispettivo.

In genere un processo di decodifica di una parola ricevuta consiste nel:

1. calcolare la sindrome ( ) = ;

2. ricavare dalla sindrome il corrispettivo vettore errore ; 3. sottrarre l'errore alla word ricevuta .

Le procedure 1. e 3. sono implementabili con semplici strutture logiche in quanto sono

operazioni lineari. Il passo 2. del procedimento di decodifica è, invece, un'operazione non

lineare: occorrerebbe invertire la relazione (2.11) e se il codice è di grossa taglia (valori

alti di k) risulta un'operazione computazionalmente onerosa. La soluzione generica

prevede l'utilizzo di una LUT nel dispositivo di decoding con 2 entrate (il numero di

sindromi) nelle quali sono memorizzati i corrispettivi vettori errori lunghi n bit. Il

principale difetto di questa soluzione è la dimensione della memoria che cresce

esponenzialmente con il numero di simboli di parità del codice. La performance di un

codice lineare è spesso trattata in termini di semplicità di decodifica, in questa ottica

vengono qui di seguito illustrati i principali tipi di block codes con i relativi algoritmi di

codifica/decodifica.

49 2.2.4 Codici di Hamming

I codici di Hamming sono una famiglia di codici perfetti 1-correttori cioè capaci di correggere tutti gli errori di peso unitario. Scoperti da Hamming e Golay indipendentemente, hanno una decodifica elegante ed efficiente, di conseguenza sono molto utilizzati laddove risultano critici i tempi di decodifica dell'informazione

.

Formalmente i codici di Hamming sono tutti e soli quei codici lineari con terna:

(( − 1) / ( − 1), − , 3

dove:

 q è l'alfabeto del codice;

 m è il numero di simboli di ridondanza;

 3 è il parametro del codice di Hamming.

La distanza minima di Hamming è fissata a 3, da cui ne risulta un parametro di Error- Correcting Capability unitario.

Posto = 2 si ritrova la nota forma di un codice binario di Hamming di parametro m:

((2 − 1), (2 − 1 − ), 3) (2.12)

Un codice binario di Hamming è quindi univocamente definito da m (numero bit di parità) e dalla sua matrice parity-check di ordine × (2 − 1). La lunghezza delle codeword è in tal modo fissata da m: = (2 − 1). In più, avendo t pari ad 1, si conclude che tutti i codici di Hamming, indipendentemente dal numero di bit di parità, sono capaci di correggere errori random di singolo bit e rilevare (ma non correggere) 2 bit errati

. Il code rate di un codice di Hamming si riduce alla forma:

(2 − 1 − ) (2 − 1)

che tende ad 1 al crescere di m, mentre il rapporto fra il numero di bit errati correggibili e il numero di bit delle parole di codice, (2 − 1), tende a 0. Per questo motivo i codici di Hamming realmente utilizzati sono implementati con valori di m non troppo elevati: la terna di Hamming più famosa è difatti: (7, 4, 3) con un numero di bit di parità pari a 3.

12 Sono codici molto utilizzati in operazioni di lettura e scrittura di memorie di massa e di memorie RAM.

13 Si parla anche di codici SEC-DED: Single Error Correcting - Double Error Detecting.

50

Il processo di decodifica di un codice binario di Hamming può essere sgravato scegliendo opportunamente la matrice . Dal momento che i possibili vettori errore correggibili sono di peso unitario, in un codice binario si ha che l'errore sarà una stringa di bit del tipo:

= (00 … 1 … 0) dove i: posizione dell'unico bit '1' all'interno della stringa.

In accordo con la (2.11), quindi, la sindrome trovata sarà la i-esima colonna h

della matrice :

( ) = = ℎ . (2.13)

Scegliendo quindi le colonne della matrice come la rappresentazione binaria del numero i, è quindi possibile

, con il solo calcolo della sindrome, conoscere la posizione dell'errore nella word ricevuta. Questa descritta, è una soluzione chiaramente in forma non sistematica e quindi necessita di un inversione del processo di encoding per arrivare alla stringa informativa, d'altro canto, però, consente una decodifica veloce ed efficiente in quanto non si rende più necessaria la ricerca dell'errore associato alla sindrome ricavata.

Segue un esempio di costruzione della matrice di parità per un codice di Hamming binario con = 3.

Esempio 2.1.

La matrice di parità di un codice di Hamming binario con terna (7, 4, 3) è implementabile, secondo quanto detto, nel seguente modo:

=





















1 0 1 0 1 0 1

1 1 0 0 1 1 0

1 1 1 1 0 0 0

dove ogni colonna è costituita dalla corrispettiva rappresentazione binaria della sua posizione a partire da sinistra. In questo modo la sindrome = (001) indica che l'errore è nel primo bit della word in ingresso (il primo ricevuto), la sindrome = (010) nel secondo etc.

14 Sotto questo risultato ci sono dimostrazioni matematiche, qui omesse, che garantiscono che la matrice così costruita sia realmente una matrice di parità.

51

Chiaramente è possibile invertire l'ordine delle colonne ottenendo un codice equivalente, nel quale la sindrome (001) indica un errore nell'ultimo bit della parola ricevuta, la sindrome (010) nel penultimo etc.

2.2.5 Codici di Golay

I codici di Golay, dal nome del matematico che li studiò Marcel J. E. Golay, sono due codici perfetti: uno binario e l'altro ternario

. In questa sede verrà analizzato il codice binario di Golay caratterizzato dalla terna (23, 12, 7).

Tale codice è capace di correggere 3 bit random errati e di rilevarne fino a 6. Data la sua modesta taglia, il processo di encoding e decoding è implementabile in hardware tramite due LUT.

In fase di codifica la LUT, profonda 2 , è indirizzata dalla word di informazione lunga 12 bit e restituisce la parola di codice su 23 bit. Utilizzando un modello sistematico la codeword conterrà, nelle 12 posizioni più significative, l'informazione vera e propria mentre le ultime 11 saranno occupate dai bit di sindrome relativi alla word che al momento si intende codificare.

In fase di decodifica, invece, la sindrome precalcolata è utilizzata per indirizzare un'altra LUT, profonda 2 , la quale restituisce il corrispondente vettore errore su 23 bit che andrà sommato (modulo-2) alla stringa ricevuta.

Il relativo codice binario di Golay esteso (24, 12, 8) è ottenuto dal (23, 12, 7) semplicemente aggiungendo, ad ogni parola di codice, un bit di parità. Il codice così ottenuto non è più perfetto e corregge, ugualmente, error-pattern di peso massimo pari a 3.

15 In letteratura se ne annoverano 4. Gli altri due codici, qui omessi, sono semplicemente le estensioni dei primi 2 ottenuti aggiungendo un bit di parità (2).

52 2.2.6 Codici Ciclici

I codici ciclici sono una importante sottofamiglia dei codici lineari che ha trovato una grande fortuna nelle applicazioni hardware in quanto gode di una serie di proprietà algebriche che consentono codifiche e decodifiche particolarmente vantaggiose.

Formalmente, un codice lineare si dice ciclico se e solo se:

∀ = ( , , , … , ) ∈ ⟺ = ( , , , … , ) ∈ .

Quindi il codice è ciclico se è chiuso rispetto all'applicazione shift ciclico a destra di una posizione. Iterando l'operazione di shift si può provare facilmente che in realtà un codice ciclico è invariante rispetto a qualunque operazione di shift ciclica (verso destra, sinistra e di qualsiasi posizione).

Un codice ciclico è analizzabile trattando le sue parole come coefficienti di polinomi anziché vettori, come è stato fatto finora. Il mondo in cui si opera non è più uno spazio vettoriale binario, ma un sottospazio dell'anello dei polinomi [ ] costituito da tutti quei polinomi di grado inferiore a n e a coefficienti appartenenti a ( ) (3). Ogni elemento di questo tipo può essere visto come un vettore le cui componenti sono i coefficienti di un polinomio appartenente a [ ]:

∀ = ( , , , … , ) ∈ → ( ) = + + + ⋯ + ∈

dove ogni ( ).

Tutti i polinomi così fatti sono appartenenti al nuovo spazio [ ] = [ ]/ ( − 1) che è l'anello quoziente di tutti i polinomi divisibili per ( − 1) e di grado massimo pari ad − 1. Il codice ciclico sarà ancora un sottospazio di [ ] ed ai suoi elementi ci si riferisce come polinomi di codice, piuttosto che parole di codice.

L'operazione di shift ciclico a destra di un generico elemento ( ) è formalmente:

( ) ( − 1) ∈ (2.14)

dove con mod si intende l'operazione resto della divisione fra ( ) e il polinomio

( − 1). L'operazione di shift ciclico è, com'è noto, riproducibile con semplici shift

register e questo rappresenta il motivo della grande diffusione di questi codici in

implementazioni hardware.

53

Come è stato fatto inizialmente per i codici a blocchi (generici) definendo la matrice generatrice, per i codici ciclici si parla di polinomio generatore intendendo quel polinomio di grado − dal quale è possibile costruire tutto lo spazio di codice . Formalmente, il polinomio generatore ( ) di un ( , )-codice ciclico a elementi in ( ) è quel polinomio monico (i.e. il coefficiente del termine di grado massimo è pari ad 1) appartenente a [ ], di grado − che divide il polinomio ( − 1).

Di conseguenza si ha che, per conoscere gli elementi di un codice ciclico di lunghezza pari ad n, bisogna trovare tutti i fattori monici che fattorizzano il polinomio ( − 1) e scegliere quello opportuno.

Esempio 2. 2.

Sul campo finito ( ) (che equivale al campo

), si vuole scomporre il polinomio ( − ). Anzitutto, dal momento che si opera su un campo binario dove l'operazione di somma è data dalla disgiunzione esclusiva la addizione e la sottrazione sono la stessa operazione: − = + , modulo 2. Quindi è possibile applicare la scomposizione al polinomio ( + ), che risulta:

( + ) = ( + )( + + )( + + ).

Ognuno dei tre polinomi genera tre codici ciclici diversi, ma non sono gli unici polinomi generatori in quanto vanno considerati anche i prodotti fra i 3 termini. I possibili polinomi generatori in questo caso sono 6, di cui 3 sono di seguito elencati:

 se ( ) = (1 + + ), si ottiene un codice ciclico binario di Hamming (7, 4, 3); i polinomi di codice saranno composti da 7 coefficienti appartenenti a ℤ e ogni polinomio avrà grado massimo pari a 6.

 se ( ) = (1 + + )(1 + + ) = 1 + + + + + + +

+ = 1 + + + + + + , dove l'ultimo passaggio è

giustificato dalla proprietà dell'operatore 'XOR' di cancellazione di due elementi

uguali, si ottiene un codice ciclico con terna (7, 6, 2), a singolo bit di parità

capace solo di rilevare errori di peso unitario, ma non di correggerli.

54

In genere la fattorizzazione del polinomio ( − 1), sarà costituita da r termini monici

dai quali scaturiranno 2 polinomi generatori ed altrettanti codici ciclici.

Preso un qualunque ( , )-codice ciclico con il suo polinomio generatore ( ) si ha:

 la dimensione del codice è = − ( ) , quindi il numero dei simboli di parità corrisponde al grado del polinomio generatore;

 l'insieme dei k polinomi { ( ), ( ), ( ), … , ( )} forma una base dello spazio di codice , che origina una matrice generatrice della forma (2.16);

 lo stesso polinomio generatore ( ) è un polinomio di codice; in particolare è l'unico polinomio appartenente a , diverso dal polinomio nullo, che ha grado minore (cioè pari ad − );

 il polinomio generatore ( ) = + + + ⋯ + è tale che, ogni polinomio di codice risulta multiplo del polinomio generatore:

∀ ( ) , ∃ ( ) . . ( ) < ∶ ( ) = ( ) ( ) (2.15) dove il polinomio ( ), di grado massimo pari a − 1, è il polinomio d'informazione da codificare.

Un modo per scrivere la matrice generatrice di un codice ciclico a partire dal suo polinomio generatore è:

=









































k n k n k n k n

g g

g

g g

g

g g

g

g g

g

0 0 0 0

...

0 ...

...

0

...

0 ...

0

...

...

...

...

...

...

...

...

...

...

0

...

0 ...

...

1 0 1 0 1 0 1 0

(2.16)

Tutti i codici ciclici binari hanno il coefficiente di grado massimo del polinomio generatore, , sempre pari ad 1, essendo il polinomio monico per definizione e termine sempre unitario (4). Per un codice ciclico binario il polinomio generatore è quindi del tipo:

16 In realtà gli r fattori irriducibili sono sicuramente distinti se n e q sono coprimi, altrimenti è possibile avere termini con molteplicità ≥ 2 (6).

55

( ) = 1 + + + ⋯ + (2.17)

La matrice (2.16) non è in forma sistematica; un modo per convertirla in un formato sistematico è quello di costruire la sottomatrice di parità nel seguente modo:

∀ è . = ( ) ∈ {1, 2, 3. . . . } Segue un esempio per comprendere meglio l'algoritmo di conversione.

Esempio 2. 3.

Riprendendo il codice ciclico di Hamming ( , , ) binario studiato nell'Esempio 2. 2.

Sul campo finito ( ) (che equivale al campo

), si vuole scomporre il polinomio ( − ). Anzitutto, dal momento che si opera su un campo binario dove l'operazione di somma è data dalla disgiunzione esclusiva la addizione e la sottrazione sono la stessa operazione: − = + , modulo 2. Quindi è possibile applicare la scomposizione al polinomio ( + ), che risulta:, si ha che il polinomio generatore ( ) = ( + + ) è l'equivalente del vettore di codice = ( ) e quindi la sua matrice generatrice di ordine × sarà data da:

=

























1 0 1 1 0 0 0

0 1 0 1 1 0 0

0 0 1 0 1 1 0

0 0 0 1 0 1 1

Volendo trasformarla in forma sistematica è sufficiente costruire la matrice operando 4 divisioni polinomiali i cui resti costituiranno le righe della suddetta matrice:

1° riga: (1 + + ) = 1 + ⟹ 101

Le operazioni di divisione fra polinomi seguono la comune metodologia della cosiddetta divisione lunga, con l'unico accorgimento dovuto alle operazioni da effettuare in (2) e non nei Reali ℝ. Svolgimento esemplificativo del calcolo:

x

+ 0 + 0 + 0 + 0 + 0 + 0 x

+ x +1

x

+ 0 + x

+ x

x

+ x + 1

0 + 0 + x

+ x

56

x

+ 0 + x

+ x 0 + 0 + x

+ x

+ x x

+ 0 + x +1 x

+0 +1

2° riga: (1 + + ) = 1 + + ⟹ 111;

3° riga: (1 + + ) = + ⟹ 011;

4° riga: (1 + + ) = 1 + ⟹ 110.

(si noti come il monomio di grado massimo dell'espressione polinomiale corrisponda al bit più a destra della versione vettoriale; tale convenzione è usata in questa sede per uniformarsi ai testi in letteratura)

infine, si ottiene:

=

























0 1 1 1 0 0 0

1 1 0 0 1 0 0

1 1 1 0 0 1 0

1 0 1 0 0 0 1

.

Dato il polinomio informativo ( ) = + + ⋯ + e il relativo polinomio di codice ( ) = + + + ⋯ + , la procedura di codifica di un codice ciclico binario si suddivide in:

 non sistematica, se vale:

( ) = ( ) ( ); (2. 18)

 sistematica, se vale:

( ) = ( ) + [ ( ) ( )]. (2. 19)

Nella ( ) = ( ) + [ ( ) ( )]. (2. 19)formula precedente i simboli di parità, costituenti il secondo addendo, risultano i coefficienti dei monomi di grado minore del polinomio ( ); nulla vieta di invertire l'ordine dei simboli di ridondanza e di informazione

. Dal momento che in letteratura viene utilizza la

17 La formula di codifica sarà: c(x) = u(x) - x^k ( x^n-k u(x) mod g(x)).

57

notazione esposta (in cui si assume la convenzione che i coefficienti a moltiplicare dei termini di grado maggiore, cioè i simboli informativi, vengano codificati prima della ridondanza), lo studio dei codici ciclici è svolto in questa forma.

Per ogni codice ciclico , esiste un polinomio ℎ( ) detto polinomio di controllo, che è generatore del codice duale , ancora ciclico

. Il polinomio ℎ( ), quindi, verifica tutte le proprietà viste in precedenza; in particolare è monico e divide il polinomio ( − 1) dal momento che la lunghezza del codice generato è ancora n. Si ha che il polinomio di controllo ℎ( ) è tale che:

ℎ( ) ( ) = ( − 1). (2.20)

Quindi, una volta fattorizzato il termine ( − 1) e scelto il polinomio generatore ( ), si fissa univocamente anche il polinomio di controllo ℎ( ), il quale è necessariamente primo rispetto a ( ). Inoltre dalla (2.20)ℎ( ) ( ) = ( − 1).

(2.20), tramite semplici passaggi, si può arrivare alla seguente relazione che è alla base del processo di decodifica per un codice ciclico:

( )ℎ( ) ( − 1) = 0  ( ) . (2.21)

Tale relazione fornisce sostanzialmente un metodo di identificazione di una codeword: se il polinomio associato alla word ricevuta, moltiplicato per il polinomio di controllo è divisibile per ( − 1), allora il messaggio ricevuto è una parola di codice valida.

La matrice di controllo di parità di ordine ( − ) × è costituita, in maniera analoga a quanto fatto per quella generatrice

, a partire dal polinomio di controllo ℎ( ):

=









































0 1

0 1

0 1

0 1

0 0 0

...

0 ...

...

0

...

0 ...

0

...

...

...

0

...

0 ...

...

h h

h

h h

h

h h

h

h h

h

k k k k k k k k

















(2. 22)

dove le righe di sono ortogonali ad ogni parola di codice .

18 In realtà il codice duale Γ è generato dal polinomio ℎ ( ) = ℎ + ℎ + ⋯ + ℎ + ℎ = ℎ( ), che ha i coefficienti ordinati in maniera opposta al polinomio di controllo ℎ( ).

19 I passaggi per arrivare alla (2.22) sono stati omessi perché non banali (6).

58 Esempio 2. 4.

Per cercare il polinomio di controllo del ( , , )-codice ciclico di Hamming partendo dalla fattorizzazione di ( + ) data nell'Esempio 2.1, si prosegue così:

( + ) = ( + )( + + )( + + ) = ( + )( + + ) ( )

Quindi il polinomio di controllo è:

ℎ( ) = (1 + )(1 + + ) = 1 + + +

che, come si può vedere è ancora monico e divide sicuramente ( + 1) per come è stato ricavato.

I due vettori associati ai polinomi di controllo e generatore sono:

= (1101), = (11101).

Ne segue che le due matrici generatrice e di parità sono rispettivamente:

=

























1 0 1 1 0 0 0

0 1 0 1 1 0 0

0 0 1 0 1 1 0

0 0 0 1 0 1 1

=





















1 1 1 0 1 0 0

0 1 1 1 0 1 0

0 0 1 1 1 0 1

Si noti come le colonne della matrice di parità siano disposte secondo un'opportuna permutazione rispetto alla forma data nell'Esempio 2.1 di codice binario di Hamming non ciclico. I due codici sono pertanto equivalenti.

La codifica sistematica di un codice ciclico è scindibile in 3 passi:

1. moltiplicazione del messaggio da codificare ( ) per ;

2. divisione del polinomio ( ) per ( ) ottenendo, così, il polinomio resto ( );

3. costruzione della parola (polinomio) di codice ottenuta concatenando il polinomio ( ) con ( ).

Tutti questi passaggi sono effettuati con un circuito LFSR (Linear Feedback Shift Register) di − stadi dove le connessioni di feedback (taps) sono basate sul polinomio

generatore ( ) = 1 + + + ⋯ + . Un circuito di questo

tipo è mostrato in Figura 2 . 2, per un codice binario.

59

Figura 2 . 2 - Encoder di un (n,k)-codice ciclico binario con polinomio generatore ( ).

Le rete LFSR in figura è composta da − flip-flop separati da porte XOR. Ogni porta logica ha la propria coppia di ingressi costituita dall'uscita del flip-flop precedente e dal coefficiente i-esimo del polinomio generatore (nel caso binario in esame vale '0' o '1' e quindi ad ogni termine g

, corrisponde un cortocircuito ('1') o un circuito aperto ('0'))

. La connessione all'ingresso del gate corrisponde al termine che è sempre unitario vista la natura monica del polinomio generatore (è infatti un collegamento), analogamente l'ultima connessione a sinistra, all'ingresso del primo flip-flop, è il termine

anch'esso sempre unitario (per codici ciclici binari).

Inizialmente, con il gate acceso, i k bit di informazione ( , , … , ) entrano nel circuito sequenziale seguendo l'ordine del grado corrispondente (il primo bit trasmesso è , l'ultimo sarà ) e, simultaneamente, il multiplexer a destra inoltra la stringa informativa in uscita componendo, così, le prime k cifre della codeword sistematica

. Appena l'intero messaggio è entrato nel registro a scorrimento (quindi dopo k colpi di clock), gli − bit contenuti nel registro costituiscono il resto ( ) della divisione fra i polinomi ( ) e ( ), cioè i bit di parità. A questo punto si interrompe la catena di feedback spegnendo il gate (l'ingresso proveniente dal gate, di ogni porta XOR sarà '0') e si prosegue con l'estrazione della sequenza di ridondanza dallo shift register. I bit di parità saranno inviati in uscita dal multiplexer il quale selezionerà la linea in basso dopo

20 Si vedrà che nei casi di codici ciclici non binari il circuito si complica in tal senso.

21 Il fatto che la stringa entri da destra corrisponde a premoltiplicare il polinomio ( ) per .

60

k cicli di clock. Questi ultimi − bit ( , , … , ) insieme ai precedenti k bit ( , , … , ) formano il vettore codificato :

= ( , , … , , , , … , ).

Esiste un'altra tecnica, qui solo accennata, per codificare in maniera sistematica un codice ciclico, la quale prevede l'utilizzo del polinomio di controllo ℎ( ) (anziché ( )) con cui ricavare la stringa di ridondanza secondo un procedimento ricorsivo che richiede uno shift register di k stadi (anziché − ). Il codice risultante è perfettamente identico a quello generato da ( ) ed è, nella realtà, utilizzato come alternativa al metodo di divisione per il polinomio generatore ( ), nei casi in cui si utilizzi un codice di lunghezza fissata n con code rate / < 0,5, cioè nei casi in cui i bit di parità siano in numero maggiore di k (4).

Come per un qualsiasi codice lineare, la decodifica di un codice ciclico è basata sulla sindrome (nella sua versione polinomiale) ( ) del messaggio ricevuto ( ) che, date le proprietà dei codici ciclici, è definibile come:

( ) = ( ) ( ) (2.23)

La sindrome di un polinomio di codice sarà nulla, mentre in tutti gli altri casi il polinomio di sindrome sarà diverso dal polinomio ed avrà grado massimo pari a

− − 1. Come un qualsiasi codice a blocchi la sindrome dipende dal solo polinomio

errore e non dalla particolare codeword. Il circuito di computazione della sindrome è

analogo a quello di encoding in quanto anche questa fase è caratterizzata da una divisione

modulo ( ); l'unica differenza è che il vettore ricevuto entra nel circuito dalla sinistra

come mostrato in Figura 2 . 3, non essendoci pre-moltiplicazione per il termine .

61

Figura 2 . 3 - Circuito di sindrome di un ( , )-codice ciclico.

Lo shift register è ancora formato da − stadi ed il suo funzionamento è analogo a quello descritto per l'encoder.

Le decodifica di un codice ciclico è costituita da:

 calcolo della sindrome;

 associazione della sindrome al corrispettivo vettore di error-pattern;

 correzione dell'errore.

In genere, per associare ogni sindrome al corrispettivo vettore di errore, è utilizzabile una

LUT indirizzata dalla stringa della sindrome, ma il limite di questo approccio è dato dalla

complessità del circuito di decodifica che cresce esponenzialmente con il numero di

simboli di parità (in un codice ciclico q-ario le sindromi sono ). Le proprietà viste di

un codice ciclico sono sfruttate in fase di decodifica con lo schema generico detto

decoder di Meggitt, che utilizza delle proprietà delle sindromi di codici ciclici (2). Il

decoder di Meggit, in questa sede solo accennato, è un tipo di decodifica seriale

applicabile, in principio, a qualunque codice ciclico. La convenienza pratica dipende

fortemente dal tipo di codice utilizzato: ci sono casi di codici ciclici che utilizzano in

maniera efficiente l'algoritmo di Meggitt come il (7, 4, 3)-codice binario di Hamming ed

altri no. In Figura 2 . 4 è mostrato lo schema di principio di un generico decoder di

62

Meggit che utilizza il circuito di computazione della sindrome descritto precedentemente, seguito da un circuito di rilevazione di error-pattern che è critico per l'implementazione reale del decoder.

È possibile dimostrare che un qualunque ( , )-codice ciclico è capace di rilevare (non necessariamente correggere) fino a − errori di tipo burst cioè errori che interessano locazioni del messaggio contigue, indipendentemente dal parametro di distanza minima.

Fra le tipologie di errori burst rintracciabili, ci sono anche gli errori end-around che interessano i primi l e gli ultimi − − simboli della stringa in ricezione; per esempio il vettore errore

= (111000 … 001111)

è un tipo di errore burst end-around con, in totale, 7 locazioni errate.

Figura 2 . 4 - Schema del decoder di Meggitt.

63 2.2.7 Codici ciclici shortened e codici CRC

Preso un determinato ( , )-codice ciclico , è sempre possibile costruirne una versione ridotta, chiamata shortened, che è ancora un codice polinomiale ma non più ciclico. Il metodo più diffuso per ridurre un codice ciclico è quello di considerare un sottoinsieme di formato da tutte e sole quelle codewords con gli s simboli più significativi (cioè i coefficienti di grado maggiore; di tipo informativo) pari a 0. Una volta eliminati tali simboli queste parole di codice saranno costituite da − cifre e formeranno un ( − , − )-sottocodice, , con capacità di correzione pari al codice ciclico originale.

Le reti di encoding/decoding sono essenzialmente le stesse utilizzate per il codice ciclico originario , in quanto la cancellazione delle s cifre di informazione non influenzano il calcolo della simbologia di parità (in codifica), né quello dell'estrazione della sindrome (in decodifica). L'unica accortezza è dovuta al fatto che, in fase di decodifica, una volta ricevuto il vettore lungo − , si dovranno effettuare ulteriori s shift per ottenere la sindrome corretta. Per valori alti di s si utilizzano soluzioni ad-hoc che ottimizzano la circuiteria per la computazione della sindrome (2), (4).

I codici CRC (Cyclic Redundancy Check) sono una famiglia molto popolare di codici ciclici binari, utilizzati frequentemente in meccanismi di protezione di grosse quantità di dati. I codici CRC sono caratterizzati da una lunghezza < 2 − 1 con m numero di bit di parità e con polinomio generatore

( ) = (1 + ) ( ).

dove ( ) è il polinomio generatore di un opportuno codice ciclico di Hamming di lunghezza n.

I metodi di codifica e decodifica sono essenzialmente quelli precedentemente descritti, a meno di soluzioni specifiche ed ottimizzate per specifici codici CRC (5).

Segue una tabella dei più comuni codici CRC con i relativi polinomi generatori (2):

Codice CRC m g(x) polinomio generatore

CRC-12 12 x¹² + x¹¹ + x³ + x² + x + 1

CRC-16 16 x¹⁶ + x¹⁵ + x² + 1

CRC-CCITT 16 x¹⁶ + x¹² + x⁵ + 1

CRC-32 32 x³²+ x²⁶ + x²³+ x²² + x¹⁶ + x¹²+ x¹¹+ x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

64

Tabella 2.1 - Principali codici CRC con relativi polinomi generatori e bit di parità.

2.2.8 Aritmetica sui campi finiti e codici BCH

I codici BCH (Bose, Chaudhuri, Hocquengheim dal nome degli inventori) sono un'ampia sottofamiglia di codici ciclici che permettono di raggiungere grossi valori di Error- Correcting Capability e quindi di correggere un gran numero di errori random.

L'esempio più importante di codici BCH non binari è la famiglia di codici Reed-Solomon scoperta da Irving S. Reed e Gustave Solomon nel 1960, indipendentemente dal lavoro di Bose, Chaudhuri ed Hocquengheim dello stesso anno. In questa sezione saranno analizzati brevemente i codici BCH per poi soffermarsi sui codici Reed-Solomon nel paragrafo successivo.

Per comprendere il funzionamento di un codice BCH e, ancora di più di un codice Reed- Solomon, si introducono adesso alcuni concetti di algebra finita e della teoria di Galois.

Riprendendo quello che è stato descritto nel paragrafo. 2.2.3, si ha che per ogni campo finito di ordine q, ( ), esiste almeno un elemento non nullo detto elemento primitivo, appartenente al campo, che genera ciclicamente tutti gli elementi di ( ) tranne l'elemento nullo (1; 6). Ogni elemento non nullo del campo finito ( ) è di conseguenza esprimibile come potenza finita di un unico elemento :

∀ ( )

≠ 0 , = .

L'elemento primitivo di un campo finito (2 ) è la radice di un polinomio irriducibile su (2) chiamato polinomio primitivo ( ) di grado pari ad m: i.e. ( ) = 0.

L'elemento primitivo di ( ) è tale che:

= 1 Si dice che "l'ordine di α

è pari a − 1.

La struttura di un campo finito è quindi analizzabile in maniera duale

come insieme di polinomi o come elementi che sono potenze dell'elemento primo .

22 Ovviamente questo approccio risulta conveniente quando l'ordine del campo non è un numero primo, perché in questo ultimo caso il campo finito è analizzabile come un classe di resto modulo q.

65

Dal momento che l'informazione che interessa proteggere è costituita da bit, lo studio è focalizzato su codici i cui simboli sono esprimibili su un numero finito (m) di bit. Un campo finito ( = 2 ) è composto da 2 elementi compreso l'elemento nullo che sono:

( ) = {0, 1, , , … , }

dove risulta = = 1: elemento neutro della moltiplicazione.

I ( − 1) elementi non nulli formano un gruppo moltiplicativo (commutativo e associativo) del campo ( ), indicato con la simbologia ( ( )\{0}, · ), cioè una struttura algebrica chiusa rispetto alla moltiplicazione (·), la quale è definita nel seguente modo:

∀ , ( )\{0}: = = , ∙ =

; e

∀ ( )\{0}: = → ∙ 0 = 0.

In più, ogni elemento del gruppo ha il suo inverso (appartenente al gruppo) definito così:

∀ = ( )\{0}, ∃ = . . · = 1.

Per quanto riguarda l'operazione di addizione '+', è dimostrabile che il campo finito (2 ), rispetto all'operazione '+', è isomorfico allo spazio vettoriale {0,1} , cioè vi è una corrispondenza biunivoca fra ogni elemento di (2 ) e ogni vettore di m bit. Ogni elemento del campo (2 ) è rappresentabile come un polinomio in (non più

"dell'incognita x") a coefficienti in (2) e di grado massimo pari a − 1. L'operazione di somma è quella modulo-2 in (2) fra gli elementi esprimibili come vettori di bit, in particolare si ha che l'elemento , costituto dal polinomio nullo è l'elemento neutro dell'addizione. Formalmente si indica (2 ) come l'estensione del campo (2).

L'utilizzo di aritmetica su campi finiti, in particolare dell'aritmetica in (2 ), permette di semplificare l'implementazione delle strutture di encoding/decoding. In maniera specifica, l'equazione (2.23), che è alla base del processo di decodifica di ogni codice ciclico, viene ricondotta a semplici operazioni lineari.

Esempio 2. 5.

Sia = 4. Per generare il campo finito (2 ) è sufficiente trovare un polinomio

primitivo di grado pari a 4 ed a coefficienti in (2): si sceglie il polinomio ( ) = 1 +

66

+ che soddisfa le richieste

. Quindi risulterà, per la definizione data di elemento primitivo:

( ) = 1 + + = 0  = 1 + .

Da questa equazione si può procedere, in maniera ricorsiva, a descrivere tutti gli elementi del campo ottenendo la Tabella 2. 2.

Nella tabella sono rappresentati i 16 elementi di (2 ) in forma esponenziale, polinomiale e vettoriale (una sequenza ordinata di m bit che sono i coefficienti dei polinomi del campo finito). Quando si tratta di moltiplicare 2 elementi è conveniente utilizzare la prima colonna trattando gli elementi come esponenziali dell'elemento primitivo , ad esempio:

· = , · = = .

Per una addizione, invece conviene usare la notazione vettoriale (polinomiale) ad esempio:

+ = ( + ) + (1 + + ) ⇒ 0110 ⊕ 1101 = 1011 ⇒ 1 + + = .

Potenze Polinomi Vettori

0 0 0000

1 1 1000

α α 0100

α

α

0010

α

α

0001

α

1 + α 1100

α

α + α

0110

α

α

+ α

0011

α

1 + α + α

1101

α

1 + α

1010

α

α

+ α

0101

α

1 + α + α

1110

α

α

+ α

+ α

0111 α

1 + α

+ α

+ α

1111 α

1 + α

+ α

1011

α

1 + α

1001

Tabella 2. 2 - Tavola degli elementi del campo GF(2⁴) generati dal polinomio primitivo + + .

23 Esistono tabelle di polinomi primitivi per ogni m (6).

67

Sulla pagina web (7) è presente una comoda applet che fornisce la tavola degli elementi di ogni estensione del campo (2), per ≤ 9.

Un codice BCH binario è tale che:

1. ha una lunghezza = 2 − 1

;

2. ha un numero di bit di parità − ≤ , dove t è la capacità d'errore del codice;

3. ≥ 2 + 1; dove la quantità 2 + 1 è detta distanza di progetto.

Un codice binario BCH è costruito specificando gli zeri del polinomio generatore ( ) appartenenti al campo (2 ). Formalmente si ha che, il polinomio generatore ( ) a coefficienti in (2), è quel polinomio di grado minimo tale che 2 elementi consecutivi del campo estensione di (2), sono sue radici:

∀ {1,2,3, … ,2 }, ∃ (2 )

≠ 0 . . = 0.

Se è proprio l'elemento primitivo , allora si parla di codici BCH primitivi che hanno lunghezza n maggiore rispetto agli altri codici BCH. Il polinomio ( ) ha grado minore o uguale a , da cui si deduce che un codice BCH ha un numero massimo di bit di ridondanza pari ad : conclusione del punto 2. Il punto 1. fissa, invece, la lunghezza del codice che quindi risulta una estensione dei codici di Hamming 1-correttori a codici t- correttori (ved. par. 2.2.3). Il punto 3. è, invece, una relazione fra la distanza minima di Hamming del codice (d

) e la cosiddetta distanza minima di progetto (2 + 1). La disuguaglianza

≥ 2 + 1 (2.24)

è il limite BCH o BCH-Bound che, interpretato in maniera diversa, può essere riformulato nel seguente modo:

>

24 Se il codice è primitivo.