Giovanni Garbo Stefano Mangione Appunti di Teoria dei Codici

Giovanni Garbo

Stefano Mangione

Appunti di Teoria dei Codici

Sommario

Capitolo I .................................................................................................................... 1

Strutture Algebriche................................................................................................... 1 I.1 Gruppo................................................................................................................... 1 I.2 Anello ..................................................................................................................... 1 I.3 Campo.................................................................................................................... 2 I.4 Spazio vettoriale.................................................................................................... 2

Capitolo II .................................................................................................................. 3

Lo Spazio nB ............................................................................................................ 3

II.1 Lo Spazio nB ........................................................................................................ 3 II.2 Generalizzazione della distanza di Hamming .................................................... 4

Capitolo III................................................................................................................. 7

Codici Binari a Blocchi.............................................................................................. 7 III.1 Codificatore, Codice, Decodificatore .................................................................. 7

Definizione III.1 - codificatore a blocchi ................................................................................. 7 Definizione III.2 - codice binario a blocchi.............................................................................. 7 Definizione III.3 - decodificatore ............................................................................................. 8

III.2 Utilità della codifica di canale.............................................................................. 9 III.3 La decodifica a massima verosimiglianza......................................................... 11

Regola di decisione a Massima Verosimiglianza ................................................................... 11 III.4 Definizioni e teoremi sui codici rivelatori e correttori..................................... 12

Definizione III.4 ..................................................................................................................... 12 Definizione III.5 ..................................................................................................................... 12 Teorema III.1.......................................................................................................................... 13 Definizione III.6 ..................................................................................................................... 13

Capitolo IV ............................................................................................................... 17

Codici Lineari a Blocchi .......................................................................................... 17 IV.1 Premessa .............................................................................................................. 17 IV.2 Morfismi .............................................................................................................. 17

Definizione IV.1 - omomorfismo........................................................................................... 17 Definizione IV.2 - monomorfismo......................................................................................... 18 Definizione IV.3 - isomorfismo ............................................................................................. 18

IV.3 Schema di principio di un codice lineare a blocco ........................................... 18 IV.4 Matrice generatrice del codice........................................................................... 19

ii Sommario

IV.5 Distribuzione dei pesi di un codice lineare a blocco......................................... 20 Definizione IV.4.....................................................................................................................21

IV.6 Capacità di rivelazione di un codice lineare a blocco ...................................... 21 IV.7 Probabilità di non rivelazione d’errore di un codice lineare .......................... 22 IV.8 Laterali di un sottogruppo ................................................................................. 23 IV.9 Decodifica tramite i rappresentanti di laterale ................................................ 24

Teorema IV.2 .........................................................................................................................25 IV.10 Probabilità d’errore di un codice lineare a blocchi ..................................... 26 IV.11 Codici perfetti, bound di Hamming .............................................................. 26

Capitolo V ................................................................................................................. 29

Codici Sistematici ..................................................................................................... 29 V.1 Codici Sistematici................................................................................................ 29 V.2 Matrice di controllo di parità............................................................................. 30 V.3 Codici duali.......................................................................................................... 31 V.4 Decodifica basata sulla sindrome ...................................................................... 32

Capitolo VI................................................................................................................ 35

Codici di Hamming...................................................................................................35 Esempio VI.1..........................................................................................................................36

VI.1 Duali dei codici di Hamming.............................................................................. 37 VI.2 Codici ortogonali e transortogonali................................................................... 38

Capitolo VII .............................................................................................................. 41

Codici Convoluzionali ..............................................................................................41 VII.1 Premessa.......................................................................................................... 41 VII.2 Struttura del codificatore............................................................................... 41 VII.3 Matrice generatrice e generatori................................................................... 42 VII.4 Diagramma di stato del codificatore............................................................. 44 VII.5 Codici catastrofici ........................................................................................... 46 VII.6 Trellis degli stati ............................................................................................. 47

Esempio VII.1 ........................................................................................................................48 VII.7 Decodifica hard e decodifica soft di un codice convoluzionale. .................. 49 VII.8 L’algoritmo di Viterbi .................................................................................... 52 VII.9 Efficienza dell’algoritmo di Viterbi .............................................................. 54 VII.10 Funzione di trasferimento di un codificatore convoluzionale..................... 55

Sommario iii

VII.11 Bound sulla probabilità di primo evento d’errore. ..................................... 59 Esempio VII.2 ........................................................................................................................ 62

VII.12 Bound sulla probabilità d’errore sul bit informativo. ................................ 64 Capitolo VIII ............................................................................................................ 69

Anelli di polinomi..................................................................................................... 69 VIII.1 Premessa.......................................................................................................... 69 VIII.2 L’anello polinomi a coefficienti in F ............................................................ 69 VIII.3 Spazi di polinomi ............................................................................................ 71

Capitolo IX ............................................................................................................... 73

Codici polinomiali .................................................................................................... 73

Capitolo X................................................................................................................. 75

Ideali di un anello di polinomi ................................................................................ 75 X.1 Premessa .............................................................................................................. 75 X.2 Ideali di un anello con identità. ......................................................................... 76

Teorema X.1........................................................................................................................... 76 Teorema X.2........................................................................................................................... 77

Capitolo XI ............................................................................................................... 79

Codici Ciclici ............................................................................................................ 79 XI.1 Rappresentazione polinomiale di un codice ciclico.......................................... 79

Definizione XI.1..................................................................................................................... 79

XI.2 L’anello n

x

x

⎡ ⎤⎢ ⎥⎣ ⎦−

Fe

...................................................................................... 80

Teorema XI.1 ......................................................................................................................... 82 XI.3 Polinomio generatore di un codice ciclico......................................................... 82 XI.4 Polinomio di parità di un codice ciclico ............................................................ 83

Esempio XI.1.......................................................................................................................... 84 XI.5 Matrice generatrice di un codice ciclico ........................................................... 85 XI.6 Codici ciclici Sistematici..................................................................................... 85

Esempio XI.2.......................................................................................................................... 86 XI.7 Duale di un codice ciclico ................................................................................... 87

Capitolo XII.............................................................................................................. 89

Campi finiti............................................................................................................... 89 XII.1 Polinomi irriducibili e campi ad essi associati ............................................. 89

Definizione XII.1 ................................................................................................................... 89

iv Sommario

Teorema XII.1 ........................................................................................................................89 XII.2 Ordine degli elementi di un gruppo .............................................................. 91 XII.3 Ordine degli elementi di un campo finito ..................................................... 92 XII.4 Ordine di un campo finito.............................................................................. 92

Teorema XII.2 - Ordine di un campo finito............................................................................92 XII.5 Elementi primitivi di un campo..................................................................... 94 XII.6 Campi di polinomi .......................................................................................... 95

Esempio XII.1 ........................................................................................................................96 XII.7 Polinomi irriducibili primitivi ....................................................................... 96

Definizione XII.2....................................................................................................................96 Definizione XII.3....................................................................................................................97 Teorema XII.3 ........................................................................................................................98

XII.8 Alcune proprietà dei campi finiti .................................................................. 98 Capitolo XIII........................................................................................................... 101

Codici BCH............................................................................................................. 101 XIII.1 Codici BCH ................................................................................................... 101

Capitolo XIV ........................................................................................................... 105

La Trasformata di Fourier Discreta ...................................................................... 105 XIV.1 La Trasformata di Fourier Discreta ........................................................... 105 XIV.2 DFT e codici ciclici........................................................................................ 108

Definizione XIV.1 ................................................................................................................108 XIV.3 DFT e codici BCH......................................................................................... 109

Equation Chapter (Next) Section 1

Capitolo I

Strutture Algebriche

Al fine di introdurre il concetto di codice è opportuno ricordare alcune definizioni:

I.1 Gruppo Un insieme non vuoto in cui si è definita una legge di composizione interna che

indicheremo con ⊕ è un gruppo rispetto a tale legge se valgono le seguenti proprietà:

( ) ( )1 2 3 1 2 3 1 2 3 , ,

,g g g g g g g g g

g g g g

g g g g g g

⊕ ⊕ ⊕ ⊕

⊕ ⊕

⊕ ⊕

= ∀ ∈

∃ ∈ | ∀ ∈ = =′ ′ ′∀ ∈ ∃ ∈ | = =

o o oo

(I.1.1)

Se la legge di composizione interna è anche commutativa è un gruppo

commutativo o abeliano.

Equation Section (Next)

I.2 Anello Un insieme nel quale siano state individuate due leggi di composizione interna

che chiameremo addizione e moltiplicazione è un anello se:

- è un gruppo commutativo rispetto all’addizione;

- la moltiplicazione gode della proprietà associativa;

- vale la legge distributiva della moltiplicazione rispetto all’addizione sia a destra

che a sinistra.

Se la moltiplicazione gode anche della proprietà commutativa diremo che è un

anello commutativo, se esiste in l’elemento neutro per la moltiplicazione diremo che

è un anello con identità.


2 Capitolo I

I.3 Campo Un insieme F che sia un anello commutativo con identità è un campo se F privato

dell’elemento neutro rispetto all’addizione è un gruppo commutativo rispetto alla

moltiplicazione.

L’insieme dei numeri razionali, l’insieme dei reali e l’insieme dei

complessi, com’è noto, sono dei campi. Si verifica facilmente che anche l’insieme

{ }0,1 , effettuando l’addizione senza riporto, cioè ponendo 1 1 0+ = e con la usuale

moltiplicazione in è un campo che indicheremo con B .


I.4 Spazio vettoriale Dato un gruppo abeliano ed un campo F si dice che è uno spazio vettoriale

sul campo F se si è individuata una legge di composizione esterna, detta prodotto per

scalari, che associa ad ogni elemento di ×F un elemento di e che comunque scelti

1 2, ∈g g e 1 2,α α ∈F goda delle proprietà:

( )( )

1 1 2 2

1 2 1

1 1 2

1

1 1

0

1

α αα αα

⊕

⊕

∈+ ∈

∈

==

g gg

g gg og g

(I.4.1)

dove 0 e 1 indicano rispettivamente gli elementi neutri dell’addizione e della

moltiplicazione del campo, o quello del gruppo, che chiameremo anche origine dello

spazio.


Capitolo II

Lo Spazio nB

II.1 Lo Spazio nB

Fissato un naturale 1n ≥ consideriamo l’insieme nB di tutte le n -uple ordinate

d’elementi di B . Ci si rende conto facilmente che nB è un gruppo rispetto alla legge di

composizione interna che associa ad ogni coppia di elementi di nB quello ottenuto

componendo termine a termine tramite l’addizione in B gli elementi omologhi delle due

n -uple. Si constata che ogni n -upla è l’opposta di se stessa e che l’elemento neutro del

gruppo è la n -upla identicamente nulla.

nB è anche uno spazio vettoriale di dimensione n sopra il campo B , potremo

quindi pensare gli elementi di nB come vettori riga con n componenti che assumono

valori in nB . In quel che segue indicheremo gli elementi di nB con lettere corsive

minuscole in grassetto e li chiameremo parole di nB , o semplicemente parole, le

componenti della generica parola saranno chiamate bit (nel senso di Binary digIT, non di

Binary Informationn uniT).

È opportuno tenere presente che:

- nB è uno spazio metrico, possiamo infatti assumere come distanza tra due

parole di nB la somma in delle somme in B delle componenti omologhe;

- nB è uno spazio normato potendosi assumere come norma del generico

elemento di nB la distanza di detto elemento dall’origine di nB , cioè dalla

parola identicamente nulla.

In quel che segue indicheremo l’addizione nel campo con ⊕ .

La distanza sopra introdotta è detta distanza di Hamming. Essa in pratica è

espressa dal numero di bit corrispondenti diversi delle due parole; in formule:

4 Capitolo II

( )1

,n

i ii

d a b⊕=

= ∑a b (II.1.1)

Che la distanza di Hamming sia effettivamente una metrica si verifica facilmente, essa è

non negativa ed è nulla se e solo se le parole sono uguali, inoltre si può facilmente

verificare che vale la disuguaglianza triangolare, cioè che date tre parole , ,a b c di nB

risulta:

( ) ( ) ( ), , ,d d d≤ +a b a c c b (II.1.2)

per sincerarsene basta esplicitare la (II.1.2):

1 1 1

n n n

i i i i i ii i i

a b a c c b⊕ ⊕ ⊕

= = =

≤ +∑ ∑ ∑ (II.1.3)

ed osservare che tutti gli addendi delle sommatorie che compaiono nella precedente sono

non negativi, pertanto è sufficiente sincerarsi che la (II.1.3) sia soddisfatta addendo per

addendo, fatto questo facilmente verificabile effettuando delle prove esaustive.

La massima distanza possibile tra due parole di nB vale n e si ottiene in

corrispondenza a coppie di parole che siano una la negata dell’altra, cioè ottenute

mutando tutti i bit uno in zero e viceversa.

La norma di un elemento di nB viene denominato peso della parola e coincide con

il numero di bit uno presenti nella parola.

La norma e la metrica appena introdotte sono tra loro coerenti, infatti la distanza tra

due elementi coincide con la norma della differenza tra di essi. Ricordiamo che in nB

addizione e sottrazione coincidono, in quanto ogni elemento è l’opposto di se stesso.


II.2 Generalizzazione della distanza di Hamming

Dato un insieme A di cardinalità q consideriamo l’insieme nA . Anche su detto

insieme si può introdurre la distanza di Hamming tra due suoi elementi, che anche in

questo caso è espressa dal numero di simboli corrispondenti diversi tra loro. La distanza

tra due elementi di nA è quindi al più n .

Lo Spazio nB 5

Si può verificare che la distanza di Hamming è una metrica su nA . Essa è non

negativa, nulla se e solo se i due elementi sono lo stesso elemento, la verifica della

validità della disuguaglianza triangolare può essere effettuata analizzando tutti i casi

possibili.

Fissato un elemento a di nA ed un naturale r n≤ esistono ( )1rn

rq

⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠− elementi

di nA a distanza i dal punto prefissato, potremmo dire che detti elementi giacciono sulla

superficie di una sfera di raggio i centrata in a . La sfera appena citata contiene

esattamente ( )0

1r

in

ii

q⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠

=

−∑ elementi, potremmo dire che il numero di tali elementi

costituisce il “volume” di detta sfera.

Qualora nA fosse anche uno spazio vettoriale, tramite la distanza di Hamming si

potrebbe individuare un “peso” per ogni elemento di nA espresso dalla distanza

dell’elemento dall’origine dello spazio, tale peso costituirebbe una possibile norma per

nA .


Capitolo III

Codici Binari a Blocchi

III.1 Codificatore, Codice, Decodificatore Cominciamo con alcune definizioni:

Definizione III.1 - codificatore a blocchi Un codificatore binario a blocchi è un’applicazione C da kB a nB , se C è iniettiva il

codificatore è non ambiguo.

Definizione III.2 - codice binario a blocchi Dato un codificatore C da kB a nB chiameremo codice binario a blocchi l’insieme

( )k nn,k C= ⊆B B . Gli elementi di n,k sono denominati parole di codice.

In altri termini per codice binario a blocchi intenderemo l’insieme delle parole di

nB che sono immagine secondo il codificatore C di almeno un elemento di kB , uno

solo se il codificatore è non ambiguo.

In questo contesto la finalità di un codice è quella di combattere l’effetto dei

disturbi introdotti dal canale nel segnale ricevuto, tali disturbi potrebbero infatti dar

luogo ad errori nella ricezione. Compito del sistema di codifica è ridurre la frequenza di

tali errori seguendo una delle seguenti strategie:

- individuare e segnalare gli errori che si verificano con maggiore probabilità;

ciò è utile qualora sia disponibile un canale di ritorno, non sia necessario

trasmettere in tempo reale e sia quindi possibile la ritrasmissione del mes-

saggio senza pregiudicare la qualità del servizio, In questo caso si parla di

tecniche di tipo ARQ (Automatic Repeat-reQuest);

- tentare , qualora la ritrasmissione non sia possibile, di correggere gli errori

che più verosimilmente sono presenti nella parola ricevuta in questo caso si

fa riferimento a strategie di tipo FEC (Forward Error Correction).

8 Capitolo III

In alcuni casi sono previste entrambe le strategie, cioè alcuni errori vengono

rivelati e corretti, altri semplicemente segnalati.

In quel che segue ci occuperemo principalmente di sistemi di codifica finalizzati

alla FEC. La funzione di correzione sopra citata è affidata ad un’applicazione D che

chiameremo decodificatore.

Definizione III.3 - decodificatore

Dato un codice binario a blocchi n,k , il decodificatore è un’applicazione Dn k→B B che

sulla base di un criterio prefissato, ha il compito di associare ad ogni elemento di nB

che si presenti all’uscita del canale l’elemento di kB che verosimilmente era stato

immesso nel codificatore C posto all’ingresso del canale stesso.

Quanto appena detto rende chiaro che più che di codici bisognerebbe parlare di

sistemi di codifica-decodifica, sia perché uno stesso codice n,k (in quanto sottoinsieme

di nB ) potrebbe essere ottenuto con codificatori diversi, sia perché potrebbe essere

decodificato con decodificatori basati su criteri diversi.

Nella pratica in effetti quando si parla di codice ci si riferisce indifferentemente,

capiterà anche noi, sia a C che a n,k , lasciando al contesto l’onere di render chiaro al

lettore a cosa si stia effettivamente facendo riferimento.

Appare in conclusione chiaro che un sistema di codifica è in realtà completamente

definito solo dalla terna { }, ,n,kC D .

La capacità di correzione di un codice è in pratica affidata alla ridondanza più o

meno oculatamente introdotta dal codificatore, ne discende che di regola k n< e che il

codificatore C è un’applicazione iniettiva.

Altrettanto evidente è che, se il codice è non ambiguo, il criterio adottato per la

scelta del decodificatore D deve necessariamente essere tale che la restrizione di D a

n,k coincida con l’applicazione inversa della restrizione di C a n,k .


Codici Binari a Blocchi 9

III.2 Utilità della codifica di canale La scelta del codice, e quella del decodificatore possono avere un considerevole

impatto sulle prestazioni del sistema di trasmissione in termini di probabilità d’errore e

di complessità del sistema.

Va anche sottolineato che, per fissato codice, possono essere individuati diversi

decodificatori. Per taluni sistemi può essere più qualificante ottimizzare la probabilità

d’errore sul singolo bit informativo, per altri quella sul simbolo trasmesso, nella scelta

del decodificatore se ne dovrebbe tener conto. Un altro elemento da considerare nella

scelta del sistema di codifica è il tipo di canale, che può essere il classico AWGN, un

canale dotato di memoria, con conseguente presenza di interferenza intersimbolica, o un

canale che introduce disturbi di tipo burst, cioè disturbi che seppur di breve durata

tendono a coinvolgere più simboli consecutivi.

Non si può nemmeno trascurare tra i parametri da tenere in considerazione la

complessità della decodifica. Scegliere ad esempio un algoritmo di decodifica sub-

ottimo, comporta in genere un degrado delle prestazioni, detto degrado, però, potrebbe

essere ampiamente ripagato da una significativa riduzione della complessità e quindi dei

costi, ovvero potrebbe essere una scelta obbligata da limiti tecnologici contingenti.

In particolare per il momento faremo riferimento ad un sistema che trasmette su un

BSC (Binary Symmetric Channel) privo di memoria. I simboli che costituiscono la

generica parola di codice verrano quindi inviati indipendentemente sul canale e ciascuno

di essi avrà una probabilità 12

p < di essere rivelato in modo errato, pertanto in uscita al

canale avremo un elemento di nB che non è certo corrisponda all’elemento inviato.

La probabilità cP di ricevere una parola di nB correttamente sarà data da

( )1np− ad esempio con 7n = e 410p −= avremo 0.9993cP = conseguente-

mente la probabilità di ricevere una parola non corretta vale 36,997 10−⋅ , tale

probabilità è in realtà scomponibile nella somma di tante probabilità d’eventi disgiunti,

precisamente eventi del tipo: “nella parola ricevuta sono presenti esattamente t l≥

errori”.

10 Capitolo III

La probabilità che la parola ricevuta non sia corretta si può quindi anche scrivere

nella forma:

( )1

1 1n

n tn tc e t

t

P P p p⎛ ⎞ −⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠

=

− = −∑ (III.2.1)

dove il t −esimo addendo esprime la probabilità che nella parola ricevuta siano presenti

esattamente t errori. La probabilità che la parola contenga almeno due errori si può

pertanto scrivere anche nella forma:

( )2

1n

n tn tt

t

p p⎛ ⎞ −⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠

=

−∑ (III.2.2)

nel nostro esempio tale probabilità si ridurrebbe a 72, 099 10−⋅ .

Quanto detto mostra come il contributo alla probabilità dell’errore singolo sia di

fatto dominante essendo gli addendi della (III.2.1) rapidamente decrescenti al crescere di

t 1.

Disporre di un codice in grado di correggere anche un numero limitato di errori in

una parola ricevuta sembrerebbe pertanto essere una scelta quasi obbligata, in realtà

bisogna anche tener presente che le capacità correttive di un codice comportano

l’introduzione di una ridondanza cioè l’introduzione di bit non destinati a trasportare

informazione, ciò, a parità di tempo destinato all’invio di una parola, comporta un

aumento della banda, a meno di non voler rallentare il flusso informativo.

Bisogna anche considerare che il confronto tra assenza e presenza di codice

andrebbe fatto a parità d’energia associata al bit informativo, cioè tenendo conto che

parte dell’energia dei bit di informazione non codificati, in presenza di un codice, deve

essere dedicata ai bit di ridondanza, in quanto, a parità di densità spettrale di potenza del

rumore, la eP sul bit cresce al diminuire della energia ad esso associata, il calcolo della

(III.2.2) andrebbe quindi effettuato introducendo un valore di p che tiene conto di ciò.

1 Per verificarlo è sufficiente esprimere ( )1

tn tp p −− nella forma ( ) ( )1 1

t npp p− − ed osservare che se 1

2p < risulta ( )1 1p

p− < , pertanto ( )1tp

p− è una funzione decrescente di t .


Malgrado le considerazioni appena fatte, fin quando è accettabile l’aumento della

banda, l’introduzione di un codice a correzione d’errore è comunque vantaggiosa rispetto

alla trasmissione non codificata.


III.3 La decodifica a massima verosimiglianza In quel che segue ci riferiremo a canali BSC ed adotteremo la tecnica di decodifica

a massima verosimiglianza (MV), che, com’è noto, equivale alla maximum a posteriori

probability (MAP) nel caso in cui i bit informativi trasmessi siano equiprobabili.

Osserviamo che in questo caso lo sono anche tutte le parole di kB e conseguentemente,

in virtù dell’iniettività del codificatore C , lo saranno anche tutte le parole del codice .

Sotto quest’ipotesi, indicando con c la generica parola di codice, con n∈b B la parola

ricevuta e con c la parola di codice scelta dal decodificatore, la regola di decisione sarà:

Regola di decisione a Massima Verosimiglianza

Scegli la parola di codice c per la quale è massima la probabilità di ricevere b , atteso

che c sia la parola trasmessa, in simboli:

( )( )ˆ argmax Pr |∈

= = =c

c B b C c (III.3.1)

Qualora il massimo non dovesse essere unico, scegli a caso, tra le parole di codice che

lo raggiungono.

*********** Nella precedente B e C rappresentano VV.AA. multidimensionali che assumono

rispettivamente valori in nB ed in .

Considerato che nel nostro caso risulta:

( ) ( ) ( ) ( )Pr | Pr | 1 11

mn m nm p

p p pp

− ⎛ ⎞⎟⎜= = = − = −⎟⎜ ⎟⎟⎜ −⎝ ⎠b c B b C c (III.3.2)

dove m rappresenta il numero di bit in cui c differisce da b . Se 12

p < il massimo

della (III.3.2) si raggiunge per tutti i valori di c che rendono m minimo. qualora ciò

avvenisse in corrispondenza ad un'unica parola di codice, si sceglierebbe quella, se

dovessero esservi più parole per le quali ciò avviene il decodificatore o in armonia con la

12 Capitolo III

regola MV sceglie a caso, o può limitarsi a segnalare la presenza d’errori nella parola

ricevuta. Va da se che l’ultima opzione è praticabile solo se si dispone di un canale di

ritorno e se la trasmissione non deve avvenire necessariamente in tempo reale.

Osseviamo che m , è la distanza di Hamming tra b e c , quindi il criterio di

decisione a massima verosimiglianza su canale BSC consiste in pratica nello scegliere a

caso, tra le parole di codice a minima distanza di Hamming dalla parola ricevuta.


III.4 Definizioni e teoremi sui codici rivelatori e correttori Supponiamo che il trasmettitore invii una parola c e che per effetto dei disturbi

venga ricevuta una parola b diversa da c . È immediato constatare che esiste certamente

n∈e B che ci permette di scrivere ⊕=b c e . Chiameremo e evento o pattern

d’errore.

Definizione III.4 Un pattern di errore e è rilevabile se risulta:

⊕ ∈ ∀ ∈e c c (III.4.1)

essendo il complementare di rispetto a nB .

Viceversa diremo che e non è rilevabile se:

| ⊕∃ ∈ ∈c c e (III.4.2)

***********

Ad ogni pattern d’errore corrisponde un peso. Esistono nt

⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠ eventi d’errore di peso

t . Osserviamo che le posizioni dei bit uno nel pattern d’errore identificano i bit errati

nella parola ricevuta.

Si dice che un codice è in grado di rivelare t errori se rivela tutti i pattern di errore

di peso t indipendentemente dalla parola di codice trasmessa.

Definizione III.5 Siano a e ′a due parole di kB . Si definisce distanza minima ( mind ) di un codice:


( ) ( )( )min min ,k

d d C C′≠ ∈

⎡ ⎤′= ⎣ ⎦a aa a

B (III.4.3)

*********** Teorema III.1

Condizione necessaria e sufficiente affinché un codice sia in grado di rivelare tutti i

pattern d’errore di peso non superiore a t è che risulti mind t> .

Dimostrazione:

Necessarietà:

Se il codice è in grado di rivelare tutti gli errori di peso non superiore a t , allora,

comunque scelta una parola di codice c ed un pattern d’errore e di peso t≤ , la parola

⊕c e non può essere una parola di codice. Ammettiamo per assurdo che mind t≤

esisterebbero allora almeno due parole di codice, siano c e ′c , tali che ( ) min,d d′ =c c .

Consideriamo il pattern d’errore '⊕=e c c , risulta:

' '⊕ ⊕ ⊕= = ∈c e c c c c (III.4.4)

esisterebbe quindi un evento d’errore di peso t≤ che non può essere rivelato in quanto

composto con una parola di codice genera un’altra parola di codice.

Sufficienza:

Se mind t> e viene ricevuta la parola ⊕=b c e , con t≤e risulta:

( , ) ( , )d d t⊕ ⊕ ⊕= = = ≤b c c e c c e c e (III.4.5)

la precedente implica che ⊕c e non può essere una parola del codice poiché mind t> ,

l’errore viene pertanto rilevato.

***********

Definizione III.6 Diciamo che un decodificatore D è in grado di correggere un pattern d’errore e se,

quale che sia la parola di codice c , risulta:

( ) ( )1 ,D C−⊕ = ∀ ∈c e c c (III.4.6)

Diciamo che un decodificatore è in grado di correggere errori di peso t se la

precedente è vera per ogni pattern d’errore di peso t .

***********

14 Capitolo III

Teorema III.2

Condizione necessaria affinché un decodificatore MV sia in grado di correggere tutti i

pattern d’errore di peso non superiore a t , è che il codice abbia una min 2 1d t≥ + .

Dimostrazione:

Supponiamo, per assurdo, che esista un codice in grado di correggere tutti gli errori di

peso non superiore a t con min 2 1d t< + . Per detto codice esisterà quindi almeno una

coppia di parole di codice, c e 'c , la cui distanza è 2m t≤ . Esistono certamente due

pattern d’errore, siano e ed 'e , entrambi di peso non maggiore di t , tali che

⊕ ⊕ ⊕ ⊕′ ′ ′ ′= ⇒ =c c e e c e c e (III.4.7)

Nel caso in cui 2 1m l= + potremo scegliere un pattern d’errore e tale che l=e

ed un 'e tale che 1l′ = +e che soddisfino la precedente.

Supponiamo adesso che venga ricevuta la parola ⊕′ ′c e , la sua distanza da ′c vale

1l + quella da c vale:

( ) ( ), ,d d l⊕ ⊕ ⊕ ⊕′ ′ = = = =c e c c e c c e c e (III.4.8)

pertanto il decodificatore a massima verosimiglianza decide per c , o per una qualsiasi

altra parola di codice che disti non più di l da ⊕′ ′c e .

Se 2m l= potremo scegliere due pattern d’errore e ed 'e entrambi di peso l che

soddisfano la (III.4.7). Supponiamo ancora una volta che venga ricevuta la parola

⊕′ ′c e , la sua distanza da ′c vale l come pure la sua distanza da c pertanto, o il

decodificatore sceglie a caso tra ′c e c , ovvero decide a favore di un’altra parola di

codice che disti da ⊕′ ′c e meno di l .

*********** Teorema III.3

Un decodificatore MV è in grado di correggere tutti i pattern d’errore di peso non

superiore a min 1

2

dt

⎢ ⎥−⎢ ⎥= ⎢ ⎥⎣ ⎦.

Dimostrazione:


Supponiamo che il canale modifichi una parola di codice c aggiungendovi un pattern

d’errore di peso non superiore a t . All’ingresso del decodificatore si presenta quindi la

parola ⊕=b c e . Quale che sia ′ ≠c c risulta ′≠b c , in quanto ∉b , poiché dista

da c meno di mind , inoltre:

( ),d ⊕ ⊕′ ′=c b c c e (III.4.9)

osserviamo che il peso di mind⊕′ ≥c c e quello del pattern d’errore è non superiore a

t , pertanto, ′∀ ≠c c , ( ), 1d t′ ≥ +b c , mentre ( ),d t≤b c , quindi il decodificatore

MV in corrispondenza a b restituirà ( ) ( )1D C−=b c , l’errore verrà quindi corretto.

***********


Capitolo IV

Codici Lineari a Blocchi

IV.1 Premessa Abbiamo visto che un codice a blocco è sostanzialmente un’applicazione iniettiva

tra kB e nB con k n< gli n k− bit aggiunti consentono in pratica di migliorare le

prestazioni del sistema introducendo un’opportuna ridondanza ai bit informativi.

Osserviamo che al crescere di k cresce, con legge esponenziale, il numero delle

parole di codice. Ci si rende conto che in queste condizioni la tecnica di decodifica, con-

sistente in una ricerca esaustiva su una tabella (in pratica un banco di memoria) che asso-

cia ad ogni possibile elemento di nB l’elemento di kB che più “verosimilmente” è stato

trasmesso diventa in breve impraticabile a causa delle eccessive dimensioni della succi-

tata tabella, ovvero perchè si preferisce utilizzare la memoria del sistema per altri scopi.

Queste considerazioni inducono alla progettazione di codici che permettano di

adottare delle tecniche di decodifica di tipo algoritmico, o che quantomeno limitino la

quantità di memoria necessaria per effettuare la ricerca sopra citata.

Tale risultato può essere ottenuto ad esempio se si progetta un codice in modo da

individuare nel sottoinsieme una qualche struttura algebrica. Tanto più ricca sarà tale

struttura, tanto maggiore sarà la possibilità di individuare algoritmi di decodifica

efficienti.


IV.2 Morfismi È utile introdurre alcune definizioni

Definizione IV.1 - omomorfismo Un omomorfismo è un’applicazione f avente come dominio un gruppo 1 e come

codominio un gruppo 2 tale che

18 Capitolo IV

( ) ( ) ( )1, f f fα β α β α β∀ ∈ + = + (IV.2.1)

Nella precedente il segno + indica la legge di composizione interna relativa al

gruppo in cui si opera.

Definizione IV.2 - monomorfismo Un monomorfismo è un omomorfismo iniettivo.

Definizione IV.3 - isomorfismo Un monomorfismo suriettivo è un isomorfismo.

Si può dimostrare che l’insieme immagine del dominio di un omomorfismo

( )1 2f ⊆ è un sottogruppo del gruppo d’arrivo. Per sottogruppo s’intende un

sottoinsieme di un gruppo che ha la struttura di gruppo rispetto alla stessa legge di

composizione interna del gruppo in cui è contenuto.


IV.3 Schema di principio di un codice lineare a blocco Un’importante classe di codici a blocco è quella dei codici lineari. Un codificatore

lineare è concettualmente costituito da (vedi Fig. IV.1) un registro d’ingresso dotato di

k celle, da un banco di n sommatori ciascuno dei quali con un numero di ingressi com-

preso tra 1 e k e da un registro di uscita costituito da n celle connesse alle uscite dei

sommatori corrispondenti. Questi ultimi, nel caso dei codici binari, effettuano le somme

in B . Conveniamo che un sommatore con un solo ingresso equivale ad una connessione

diretta tra la cella d’ingresso e quella di uscita corrispondente al sommatore.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

c l k o u tT

1 2 3 4 5 6 7 8 9 10 11S

c l k i nT

Fig. IV.1 Schema di principio di un codice di Hamming 15,11

Codici Lineari a Blocchi 19

I registri sopra citati possono essere in pratica registri a scorrimento (shift register),

in questo caso la sorgente emette una sequenza di bit, non appena il registro d’ingresso è

carico, cioé dopo k periodi del suo clock, l’uscita dei sommatori, che potrebbero essere

realizzati con delle porte logiche di tipo XOR, viene utilizzata per settare le n celle del

registro di uscita che verrà quindi completamente scaricato nel tempo necessario a

ricaricare con i successivi k bit il registro di ingresso.

In sostanza, se clkinT e clkoutT indicano rispettivamente i periodi di clock del

registro d’ingresso e di quello d’uscita, deve risultare clkin clkoutkT nT= .


IV.4 Matrice generatrice del codice I codici lineari a blocco sono anche chiamati codici a controllo di parità (parity

check code) in quanto il generico elemento del registro d’uscita, vale uno ogniqualvolta

la somma in senso ordinario dei valori delle celle di ingresso a cui è connesso è un

numero dispari e vale zero altrimenti.

Se indichiamo con x una parola di kB e con ( )C=c x la corrispondente parola

di nB in uscita dal codificatore, l’ i −esimo bit della parola d’uscita può esprimersi

nella forma:

1 1 2 2 1, ,i i i k kic x g x g x g i n⊕ ⊕ ⊕= =… … (IV.4.1)

dove il generico ijg è un coefficiente che vale 1 se un ingresso del j -esimo sommatore è

connesso alla i -esima cella del registro di ingresso e vale 0 altrimenti.

Ricordiamoci che tutte le operazioni delle (IV.4.1) sono effettuate secondo le

regole del campo B .

Un codice definito tramite le (IV.4.1) si dice lineare in quanto, come si verifica

facilmente, la parola di codice ottenuta in corrispondenza alla somma di due qualsiasi

parole di kB è la somma in nB delle rispettive parole di codice.

20 Capitolo IV

kB e nB sono gruppi, ed un codificatore lineare è un omomorfismo, ovviamente, è

auspicabile che sia anche un monomorfismo, onde evitare che a due parole distinte di

kB corrisponda la stessa parola di codice in nB .

Il codice è pertanto un sottogruppo di nB .

Se pensiamo x e c come vettori riga le (IV.4.1) si possono rappresentare sotto

forma matriciale:

=c xG (IV.4.2)

dove G è una matrice k n× il cui generico elemento è ijg . G è detta matrice

generatrice del codice.

Si osservi che le righe della matrice G , sono le parole di codice che vengono

generate in corrispondenza agli elementi che costituiscono la base canonica di kB . Ci si

convince anche abbastanza facilmente del fatto che le k righe di G generano mediante

tutte le loro possibili combinazioni lineari , che oltre ad essere un sottogruppo di nB

ne è anche un sottospazio. Ovviamente affinché il codice non sia ambiguo C deve

essere un monomorfismo.

Una condizione necessaria e sufficiente affinché C sia un monomorfismo è che le

righe della sua matrice generatrice siano linearmente indipendenti.


IV.5 Distribuzione dei pesi di un codice lineare a blocco Abbiamo detto che la somma di due parole di un codice lineare è una parola di

codice, ciò comporta che la parola identicamente nulla in un codice lineare è sempre una

parola di codice, in quanto ottenibile sommando ad una qualunque parola del codice se

stessa, indicando con o la parola identicamente nulla per un codice lineare avremo:

( ) ( )1 2 1 2 1 2 1 2, , ,d d⊕ ⊕= = ∀ ∈c c c c o c c c c (IV.5.1)

ma, per fissato 1c , al variare di 2c in si ottengono tutte le parole di codice, in

sostanza fissata una distanza di Hamming ogni parola di un codice lineare vedrà lo stesso

numero di parole di codice a quella distanza. Tale proprietà si rivela utile ad esempio nel


calcolo della probabilità d’errore in quanto la probabilità d’errore condizionata all’invio

di una parola di codice non dipende dalla particolare parola inviata, ed è quindi uguale

alla probabilità d’errore non condizionata.

Dalla (IV.5.1) si deduce inoltre facilmente che per calcolare la distanza minima del

codice è sufficiente individuare la parola non nulla di peso minimo, che è evidentemente

la parola a minima distanza di Hamming dalla parola nulla, ovviamente non è detto che

tale parola sia unica.

La (IV.5.1) ci suggerisce di introdurre la cosiddetta distribuzione dei pesi del

codice.

Definizione IV.4 Dato un codice lineare n,k per distribuzione dei pesi s’intende un’applicazione

( )WT i , definita sull’insieme dei naturali non maggiori di n , a valori in ; che asso-

cia ad ogni elemento del suo dominio il numero di parole di codice che hanno peso pari

ad esso.

È facile intuire che le prestazioni di un codice sono in prima istanza influenzate

dalla sua distanza minima, che coincide con il più piccolo elemento non nullo del

dominio di ( )WT i cui corrisponde un’immagine diversa da zero, ma dipendono anche

dalla ( )WT i nel suo insieme.


IV.6 Capacità di rivelazione di un codice lineare a blocco Per la capacità di rivelazione di un codice lineare a blocco vale il seguente teorema:

Teorema IV.1

Un decodificatore a massima verosimiglianza per un codice lineare non è in grado di

rivelare tutti e soli gli eventi d’errore che coincidono con una parola di codice.

Dimostrazione:

Se il canale fa sì che ad una parola di codice c venga aggiunto un pattern d’errore e che

coincide con una parola di codice ′c in ingresso al decodificatore si presenterà la parola

22 Capitolo IV

⊕ ′c c , ma il codice è lineare quindi ⊕ ′c c è una parola di codice pertanto l’errore non

sarà rivelato.

Viceversa se un pattern d’errore e non viene rivelato, allora deve esistere una

parola di codice ′c tale che ⊕ ′=c e c essendo c è la parola trasmessa. L’eguaglianza

appena scritta comporta:

⊕ ′ =c c e (IV.6.1)

pertanto e è una parola di codice.

*********** Equation Section (Next)

IV.7 Probabilità di non rivelazione d’errore di un codice lineare Ci proponiamo di calcolare la probabilità che un codice lineare, impiegato per la

sola rivelazione d’errore, non ne riveli la presenza nella parola ricevuta, sotto l’ipotesi

che il codice venga utilizzato su un canale BSC e che il decodificatore sia del tipo MV.

Sappiamo che (vedi Teorema IV.1) gli unici pattern d’errore non rivelati sono

quelli che coincidono con una parola di codice. Osserviamo che la probabilità che si

presenti un dato pattern d’errore e dipende esclusivamente dal suo peso i e vale in

particolare:

{ } ( )ˆPr 1n iie e p p−

= = − (IV.7.1)

Tra tutti gli ni⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜⎝ ⎠

possibili pattern d’errore di peso i non verranno rivelati soltanto

quelli che coincidono con una parola di codice, cioè tanti quante sono le parole di codice

di quel peso. Poiché i pattern d’errore sono tra loro indipendenti, la probabilità ( )Pru

che un errore non venga rivelato dal codice vale:

( ) ( )min

Pr ( )n

n iiu

i d

WT i p i p−

=

= −∑ (IV.7.2)

La precedente presuppone la conoscenza della distribuzione dei pesi, purtroppo detta

funzione non è nota per molti dei codici d’uso comune, in questo caso può essere utile

una maggiorazione della (IV.7.2) che si basa sulla considerazione che in ogni caso deve

essere:


( ) niWT i⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜⎝ ⎠

≤ (IV.7.3)

non possono cioè esservi più pattern d’errore di peso i di quante non siano le parole di

nB aventi quel peso. Potremo quindi certamente scrivere:

( ) ( )min

Prn

n iinu i

i d

p i p−⎛ ⎞⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠

=

≤ −∑ (IV.7.4)


IV.8 Laterali di un sottogruppo Premesso che in questo paragrafo per comodità utilizzeremo la notazione

moltiplicativa per indicare la legge di composizione di un gruppo e che indicheremo

quindi con 1 l’elemento neutro del gruppo, consideriamo un gruppo abeliano ed un

suo sottogruppo . Ricordiamoci che, per definizione di sottogruppo, è chiuso

rispetto alla legge di composizione di .

Consideriamo adesso un generico elemento g non appartenente a , se componia-

mo questo elemento con gli elementi di otteniamo un sottoinsieme di g disgiunto da

. Se infatti risultasse che, per un qualche elemento c di , g c c ′⋅ = ∈ , ciò impli-

cherebbe che 1g c c −′⋅ ⋅ = 1 e quindi 1 1g c c− −′= ⋅ ∈ , ma se 1g− ∈ allora es-

sendo un gruppo vi appartiene anche g , contro l’ipotesi. g

viene denominato

laterale, coinsieme o coset di .

Consideriamo adesso, se esiste, un elemento che non appartiene né a né a g ,

sia g ′ . Anche g ′ , composto con gli elementi di , genera un sottoinsieme g ′ di ov-

viamente disgiunto da , ma anche da g ; se infatti esistesse c ∈ tale che

gg c g′ = ∈ , ciò implicherebbe 1 1gg cc gc− −′ = ∈ quindi gg ′ ∈ contro l’ipotesi.

Possiamo quindi concludere che i laterali di un sottogruppo se non sono disgiunti sono

coincidenti.

24 Capitolo IV

Appare chiaro che ogni sottogruppo di un gruppo induce una partizione in laterali

del sottogruppo. Si può facilmente verificare che tutti i laterali hanno la stessa cardinalità

del sottogruppo cui sono associati e che ogni elemento di un laterale, composto con gli

elementi del sottogruppo, è in grado di generare il laterale cui appartiene. È quindi legit-

timo scegliere in corrispondenza ad ogni laterale un suo elemento, che viene denominato

rappresentante di laterale o di coinsieme, o ancora coset leader. Il criterio di scelta può

essere qualsiasi.

Ricordiamoci che stiamo considerando gruppi abeliani, se rimuovessimo questa

ipotesi ad ogni sottogruppo potrebbero essere associati dei laterali destri e sinistri, gene-

ralmente distinti, qualora tali laterali dovessero coincidere si direbbe che il sottogruppo

considerato è un sottogruppo normale.

Il fatto che tutti i laterali di un sottogruppo hanno la stessa cardinalità consente di

affermare, nel caso di gruppi finiti, che ogni sottogruppo ha un numero d’elementi sotto-

multiplo di quello del gruppo in cui è contenuto.


IV.9 Decodifica tramite i rappresentanti di laterale Tornando ai codici lineari a blocco ( ),n k , ricordiamo che l’insieme delle parole di

un tale codice costituisce un sottogruppo n⊆ B . Abbiamo anche mostrato che un

codice lineare a blocco è in grado di rivelare tutti i pattern d’errore che non coincidono

con parole di codice.

Occupiamoci adesso delle sue capacità correttive. A tal proposito osserviamo che

ogni parola ricevuta b appartiene ad un solo laterale di nB rispetto a , intendendo ov-

viamente stesso come un laterale. Risulta inoltre ⊕=b c e , il pattern d’errore intro-

dotto dal canale appartiene quindi certamente allo stesso laterale cui appartiene b . Visto

che la probabilità che il canale introduca un pattern d’errore di un dato peso decresce al

crescere di quest’ultimo, l’ipotesi più verosimile è che il pattern d’errore introdotto coin-

cida con una parola di peso minimo appartenente allo stesso laterale della parola rice-

vuta.


Le considerazioni appena fatte portano alla seguente tecnica di decodifica: dato un

codice scegliamo in ciascun suo laterale un coset leader tra le sue parole di peso mi-

nimo. Se viene ricevuta la parola b , essa si potrà scrivere in modo univoco nella forma

⊕=b c l essendo l il coset leader del laterale a cui essa appartiene. Osserviamo che

comunque scelta una parola di codice ′c risulta:

( ) ( ), ,d d ⊕ ⊕ ⊕′ ′ ′= = ≥b c c l c l c c l (IV.9.1)

in quanto ⊕ ⊕ ′l c c è una parola di nB che appartiene allo stesso laterale di b , visto

che ⊕ ′c c è una parola di codice, ed l è per ipotesi una parola di peso minimo di quel

laterale, pertanto se adottiamo la decodifica ML dobbiamo scegliere la parola c .

Se nello stesso laterale più di una parola ha peso minimo significa che la parola ri-

cevuta si trova alla stessa distanza da due o più parole di codice, in questo caso, quale

che sia la scelta effettuata tra le parole candidate, le prestazioni del decodificatore non

cambiano.

Si osservi che qualora la parola ricevuta appartenga al codice tale operazione non la

altera in quanto il rappresentante di laterale relativo a è unico ed è ovviamente la pa-

rola identicamente nulla.

Quanto sopra detto ci porta ad enunciare il seguente

Teorema IV.2

Un decodificatore che adotta la tecnica dei coset leader corregge tutti e soli i pattern

d’errore coincidenti con un coset leader.

******************* Un vantaggio della decodifica basata sui coset leader è quello di restituire sempre

una parola di codice, ovviamente non sempre quella corretta. Il suo principale svantaggio

consiste nel fatto che per metterla in pratica occorre comunque effettuare una ricerca in

tutto nB per individuare il laterale cui appartiene la parola, se n è grande tale ricerca

può diventare improponibile.


26 Capitolo IV

IV.10 Probabilità d’errore di un codice lineare a blocchi Il Teorema IV.2 ci suggerisce come calcolare la probabilità di corretta decisione

( )Pc di un codice, impiegato su un canale BSC.

Osserviamo innanzitutto che all’uscita del decodificatore sarà presente la parola ef-

fettivamente inviata tutte e sole le volte che il pattern d’errore introdotto dal canale coin-

cide con un coset leader, considerando anche tra i pattern d’errore quello identicamente

nullo che è il coset leader del codice.

La ( )Pc coinciderà quindi con la probabilità che il pattern d’errore sia un qual-

siasi coset leader. Possiamo quindi scrivere:

( ) ( )0

P ( ) 1l

n iic

i

L i p p−

=

= −∑ (IV.10.1)

dove l rappresenta il massimo peso raggiunto dai coset leader ed ( )L i un’applicazione

che associa ad ogni intero i compreso tra 0 ed l il numero di coset leader di peso i .

Dalla (IV.10.1) discende facilmente:

( ) ( ) ( )0

P 1 P 1 ( ) 1l

n iie c

i

L i p p−

=

= − = − −∑ (IV.10.2)


IV.11 Codici perfetti, bound di Hamming Una maggiorazione della probabilità d’errore può essere ottenuta ricordando il

Teorema III.3, che afferma che la capacità correttiva di un codice è non minore di

min 1

2

dt

⎢ ⎥−⎢ ⎥= ⎢ ⎥⎣ ⎦. In altri termini il teorema afferma che la regione di decisione di ciascu-

na parola di codice contiene una “ipersfera” di raggio pari a t . In nB che contiene esat-

tamente 0

tnj

j

⎛ ⎞⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠=∑ punti.

Osserviamo che in un codice lineare tutte le regioni di decisione hanno la stessa

forma e che l’insieme dei coset leader costituisce la regione di decisione associata alla


parola nulla. Vi sono 2n k− laterali, quindi 2n k− coset leader. Il Teorema III.3 nel caso

di codici lineari implica quindi che deve valere la disuguaglianza:

0 0

2 ( )t l

n knj

j i

L i⎛ ⎞ −⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠= =

≤ =∑ ∑ (IV.11.1)

la precedente va sotto il nome di Bound di Hamming i codici che lo soddisfano come

uguaglianza sono detti codici perfetti.

Quale che sia il codice lineare che stiamo considerando, i primi 1t + addendi

dell’ultimo membro della (IV.11.1) devono necessariamente essere uguali ai

corrispondenti addendi della sommatoria a primo membro, possiamo pertanto scrivere:

( ) ( ) ( )

( ) ( ) ( )

0 0

0 1

P ( ) 1 1

P 1 1 1

l tn i n ji jn

c ji j

t nn j n jj jn n

e j jj j t

L i p p p p

p p p p

− −⎛ ⎞⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠= =

− −⎛ ⎞ ⎛ ⎞⎟ ⎟⎜ ⎜⎟ ⎟⎜ ⎜⎟ ⎟⎟ ⎟⎜ ⎜⎝ ⎠ ⎝ ⎠= = +

= − ≥ − ⇒

≤ − − = −

∑ ∑

∑ ∑ (IV.11.2)

la precedente è ovviamente soddisfatta come uguaglianza solo dai codici perfetti, quali

sono ad esempio i codici di Hamming cui accenneremo più avanti.


Capitolo V

Codici Sistematici

V.1 Codici Sistematici Quanto detto nei precedenti paragrafi ci fa comprendere che le prestazioni di un co-

dice lineare sono da attribuirsi sostanzialmente al sottospazio di nB generato dalle righe

della matrice G che supporremo linearmente indipendenti e che quindi costituiranno

una base per il sottospazio da esse generato. In sostanza quindi codici generati da matrici

distinte, delle stesse dimensioni, che generano però lo stesso sottospazio di nB sono del

tutto equivalenti.

Lo spazio generato dalle righe di G non cambia se si permutano le sue righe, o se

si somma ad una qualunque riga di G una combinazione lineare delle restanti.

Dato un codice lineare a blocchi, consideriamo la sua matrice G e selezioniamone

una sua colonna non identicamente nulla. Supponiamo sia la j − esima. Consideriamo

quindi una riga di G che abbia un 1 nella j − esima colonna, supponiamo sia la

i −esima, sommiamo tale riga a tutte le altre righe di G che si trovano nelle stesse con-

dizioni. Otterremo così una matrice, sia ( )1G , equivalente a G la cui j − esima colonna

ha un solo valore 1 in posizione i −esima. Operiamo adesso sulla matrice ( )1G come

avevamo operato sulla G con la sola accortezza di scegliere una colonna che abbia un 1

in una riga diversa dalla i −esima, otterremo così una ( )2G con due colonne che pre-

sentano un solo valore 1 su righe diverse. All’l −esimo passo sceglieremo una colonna

che abbia un 1 in una riga diversa da quelle selezionate ai passi precedenti.

Tale procedura potrà essere ripetuta al più k volte, a meno che non sia più possibi-

le selezionare una colonna, ma ciò accade solo nel caso in cui tutte le righe non ancora

selezionate sono identicamente nulle, in questo caso le righe della matrice G da cui era-

vamo partiti non erano linearmente indipendenti, quindi non erano in grado di generare

30 Capitolo V

un sottospazio di dimensione k , o, che è lo stesso, il codificatore non era un monomor-

fismo di kB in nB cioè avevamo preso in considerazione un codice ambiguo.

Al termine della procedura sopra descritta avremo quindi una matrice ( )kG che ha

almeno k colonne in cui compare un solo 1 , tra le colonne con un solo 1 ne esisterà al-

meno una che lo ha in corrispondenza alla prima riga, una in corrispondenza alla seconda

e cosi via fino alla k -esima.

A questo punto è opportuno osservare che se s’intende utilizzare il codice su un ca-

nale simmetrico binario, ovvero mappando coppie di bit della parola d’uscita in punti di

una costellazione QAM, è anche legittimo permutare le colonne della matrice G , questa

operazione equivale in sostanza ad etichettare diversamente le dimensioni dello spazio

nB .

È ovvio che permutando opportunamente le colonne della ( )kG si può ottenere una

matrice del tipo:

,kn kk k n k−⎡ ⎤= ⎣ ⎦G I P (V.1.1)

un codice lineare a blocchi la cui matrice generatrice assume la forma (V.1.1) si dice

sistematico tale denominazione è dovuta al fatto che i primi k bit della parola di codice

coincidono con i bit informativi, i restanti n k− sono utilizzati per effettuare i controlli

di parità definiti dalle colonne della matrice P .

In pratica in corrispondenza ad ogni codice lineare a blocco non ambiguo esiste

sempre un codice sistematico ad esso equivalente. L’utilizzo dei codici sistematici è

quindi auspicabile, in quanto, solo per fare un esempio, consente di non effettuare nes-

suna decodifica sulla parola ricevuta, limitandosi ad osservarne i primi k bit, accettando

in questo caso un degrado delle prestazioni a fronte di una diminuzione della complessità

del sistema.


V.2 Matrice di controllo di parità Dato un codice lineare a blocco n,k sistematico, indichiamo con x la generica pa-

rola d’ingresso e con c la generica parola di codice. Se prendiamo in considerazione sol-

Codici Sistematici 31

tanto le ultime n k− componenti della parola di codice, ponendo 1,n k nc c− +⎡ ⎤= ⎣ ⎦p …

possiamo scrivere:

,

,

k n k

n k n k

−

− −

⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦

0p c

I (V.2.1)

sostituendo a c la sua espressione in termini della matrice G otteniamo:

( )

, , ,, , , ,

, , ,

, , , , ,

, , 1,

k n k k n k k n kk k k n k k k k n k

n k n k n k n k n k n k

k k k n k k n k n k n k k n k

k n k n k n k n k

− − −− −

− − − − − −

⊕− − − − −

⊕− − − −

⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥= = =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦

= = ⇒⇒ =

0 0 0p xG x I P x I P

I I I

x I 0 P I xPxP pI 0

(V.2.2)

possiamo scrivere anche:

⎡ ⎤= ⎢ ⎥⎣ ⎦c x p (V.2.3)

che ci suggerisce di riscrivere l’ultima eguaglianza nella (V.2.2) nella forma:

,1,

,

k n k Tn k

n k n k

−−

− −

⎡ ⎤⎢ ⎥ = =⎢ ⎥⎢ ⎥⎣ ⎦

Pc cH 0I

(V.2.4)

La matrice H che compare nella precedente prende il nome di matrice di controllo di

parità (parity check matrix), in quanto la (V.2.4) è soddisfatta da tutte e sole le 2k parole

di codice.


V.3 Codici duali Osserviamo che la (V.2.4) implica l’ortogonalità tra la generica parola di codice e

ogni riga della matrice H , le cui n k− righe essendo linearmente indipendenti sono in

grado di generare un sottospazio ,n n k⊥ − di nB ortogonale a n,k , nel senso che combi-

nando linearmente le righe di H si ottengono sempre parole di nB ortogonali a qualsiasi

parola di n,k .

Ci si rende facilmente conto del fatto che si può pensare a ,n n k⊥ − come ad un

codice ( ),n n k− .

32 Capitolo V

Permutando opportunamente le colonne della matrice H si può sempre rendere

,n n k⊥ − sistematico, in un certo senso lo è anche senza permutarle, solo che in questo

caso i bit informativi coincidono con gli ultimi k bit della parola di codice.


V.4 Decodifica basata sulla sindrome Supponiamo di ricevere una parola b , affetta da un pattern d’errore e . Se so-

stituiamo b a primo membro della (V.2.4) otteniamo:

1,T T T T T

n k⊕ ⊕−= = = =bH cH eH 0 eH eH s (V.4.1)

s è una parola di n k− bit che prende il nome di sindrome della parola ricevuta. Vi so-

no 2n k− possibili sindromi.

È interessante osservare che il calcolo della sindrome può essere effettuato in

ricezione con uno schema analogo a quello utilizzato per il codificatore, dimensionando

correttamente i due registri a scorrimento. Il calcolo della sindrome nei codici a

rivelazione d’errore consente verificare facilmente se la parola ricevuta appartiene al

codice (solo le parole di codice hanno infatti sindrome nulla).

Nel caso dei codici a correzione d’errore, osservando la (V.4.1) si rileva che tutti

gli elementi di uno stesso laterale del codice hanno la stessa sindrome.Tutti gli elementi

di un laterale si ottengono infatti sommando ad un qualsiasi elemento del coset stesso

una parola di codice. È altresì chiaro che elementi appartenenti a laterali distinti avranno

sindromi distinte. In sostanza esiste una corrispondenza biunivoca tra il gruppo delle sin-

dromi e l’insieme dei laterali che è esso stesso un gruppo, detto gruppo quoziente indica-

to con n

n,k

B . La composizione tra due laterali del gruppo quoziente si effettua indivi-

duando il coset di appartenenza dell’elemento di nB ottenuto componendo due elementi

arbitrariamente scelti nei due laterali componendi.

Si constata che il gruppo delle sindromi è isomorfo al gruppo quoziente di nB in-

dividuato dal suo sottogruppo normale n,k .

Codici Sistematici 33

La decodifica a massima verosimiglianza può quindi essere effettuata associando

preliminarmente ad ogni sindrome il coset leader nel laterale ad essa associato, da som-

mare alla parola ricevuta per effettuare la decodifica. Tale tecnica comporta la presenza

di un banco di memoria in grado di contenere 2n k− parole di n bit.

In effetti essendo interessati solo ai bit informativi è sufficiente memorizzare sol-

tanto i primi k bit del coset leader, questo accorgimento riduce un po’ il fabbisogno di

memoria.

La decodifica basata sulla sindrome è più efficiente di quella basata sui coset lea-

der, anche essa diventa tuttavia ben presto difficilmente praticabile, al crescere delle di-

mensioni della parola di codice. A causa principalmente della quantità di memoria

necessaria.


Capitolo VI

Codici di Hamming

Abbiamo visto come si calcola la sindrome di un codice ed abbiamo osservato che

più pattern d’errore possono condividere la stessa sindrome. Immaginiamo adesso di

voler costruire un codice che abbia la capacità di correggere tutti i pattern d’errore di

peso 1 . Affinché ciò sia possibile ciascun pattern d’errore di peso 1 deve essere un coset

leader. A cui sono associate sindromi distinte.

Abbiamo visto che un codice ( ),n k consta di 2k parole di n bit. Esistono quindi

n distinti pattern d’errore di peso 1 , ciascuno dei quali, moltiplicato per TH fornisce la

rispettiva sindrome. Detta sindrome coincide con la colonna della matrice H che

corrisponde alla posizione dell’unico bit 1 nel pattern d’errore. Quindi, se vogliamo che

il codice sia in grado di correggere tutti i pattern d’errore di peso 1 , è necessario che le

n colonne della matrice H siano tutte non nulle e diverse tra loro. Poiché ogni colonna

della matrice in questione ha n k− elementi, deve necessariamente essere:

2 1n kn −≤ − (VI.1.1)

La precedente scritta come uguaglianza definisce

implicitamente una famiglia di codici, i codici di

Hamming, che sono in grado di correggere tutti gli errori di

peso 1 e di rivelare quelli di peso non superiore a due in

quanto si può mostrare che la loro mind vale 3 . Alcune

soluzioni della (VI.1.1) sono riportate nella in Tabella VI.1

Il primo codice della tabella è in effetti un codice a

ripetizione, in sostanza ogni bit informativo viene inviato

consecutivamente tre volte, vi sono due sole parole di codice, la distanza di Hamming tra

esse, quindi anche la mind del codice, è 3 , il codice è in grado di correggere errori

singoli, la regola di decisione a massima verosimiglianza per questo codice consiste

n k

3 1

7 4

15 11

31 26

63 57

127 120

Tabella VI.1 Alcuni valori di n e k per i codici di Hamming

36 Capitolo VI

nello scegliere il bit che compare almeno due volte nella parola ricevuta. Se il canale

introduce un errore doppio il codice rileva l’errore, ma non è in grado di correggerlo, nel

senso che restituisce una parola di codice diversa da quella inviata nel caso di decodifica

MV. Vi sono tre laterali del codice a ciascuno di essi appartiene un pattern d’errore

singolo e il suo negato.

Per concludere si può facilmente verificare che la (IV.11.1) è verificata come

uguaglianza per tutti i codici di Hamming risulta infatti

min 11

2

dt

⎢ ⎥−⎢ ⎥= =⎢ ⎥⎣ ⎦ (VI.1.2)

da cui

1

0

1i

nn

i=

⎛ ⎞⎟⎜ ⎟⎜ = +⎟⎜ ⎟⎟⎜⎝ ⎠∑ (VI.1.3)

ma per i codici di Hamming 1 2n kn −+ = , i codici di Hamming appartengono

pertanto all’insieme dei codici perfetti.

Esempio VI.1 Una possibile matrice H del secondo codice della tabella, il 7,4,è data da:

1 1 0 1 1 0 0

1 0 1 1 0 1 0

0 1 1 1 0 0 1

⎡ ⎤⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

H

Osserviamo che la matrice in esame ha per colonne tutte le parole di tre bit ad esclusione di quella costituita da soli zero, ordinate in modo da rispettare la (V.2.4).

Ricordiamoci che le prime quattro colonne di H possono essere permutate tra loro senza che le caratteristiche del codice cambino.

Basandoci sulla (V.2.4) e sulla (V.1.1) potremo facilmente scrivere la matrice G generatrice del codice:

1 0 0 0 1 1 0

0 1 0 0 1 0 1

0 0 1 0 0 1 1

0 0 0 1 1 1 1

G

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

1 2 3 4 5 6 7

clk outT

1 2 3 4S

clk inT

Fig. VI.1 - Schema a blocchi del Codice 7,4 di Hamming

Codici di Hamming 37

il relativo schema a blocchi è mostrato in Fig. VI.1, la lista delle parole del codice è elencata nella Tabella VI.2 dove ogni parola è stata suddivisa tra contenuto informativo (i primi 4 bit) e controlli di parità (gli ultimi 3).

Uno schema a blocchi del codice di Hamming 15,11 è mostrato in Fig. IV.1.

VI.1 Duali dei codici di Hamming Nel caso particolare dei duali dei codici di Hamming, le

colonne della matrice generatrice sono tutte e sole le parole

binarie non nulle che si possono scrivere con k bit vi saranno

quindi esattamente 2 1kn = − colonne nella matrice

generatrice. La matrice H definisce quindi un codice

( )2 1,k k− , le cui parole non nulle hanno tutte peso 12k− .

Infatti ogni riga della matrice generatrice contiene per

costruzione 12 1k− − bit zero e 12k− bit uno. Le restanti pa-

role del codice si ottengono combinando linearmente le righe

della matrice generatrice, tale combinazione lineare, a ben

vedere, consiste nel cancellare un sottoinsieme di righe dalla

matrice generatrice e comporre le restanti.

Per semplificare il ragionamento immaginiamo di ag-

giungere alla matrice H una colonna nulla, sia H la matrice estesa così ottenuta. Os-

serviamo che le parole del codice ( )2 ,k k generato da H differiscono da quelle generate

da H solo per il fatto di avere un bit in più, che essendo generato dalla colonna identica-

mente nulla, vale sistematicamente 0 . Possiamo quindi affermare che le parole corri-

spondenti dei due codici, cioè generate dalla stessa parola di kB hanno lo stesso peso.

Osserviamo adesso che la cancellazione di una riga in H da luogo ad una sottoma-

trice ( )1H che ha le colonne uguali a due a due; se cancellassimo due righe avremmo

una sottomatrice ( )2H con colonne uguali a quattro a quattro e così via.

Codice di Hamming 7,4

0000 000

0001 111

0010 011

0011 100

0100 101

0101 001

0110 110

0111 001

1000 1101001 001

1010 101

1011 010

1100 011

1101 100

1110 000

1111 111 Tabella VI.2 - Parole del codice Hamming 7.4

38 Capitolo VI

In generale quindi cancellando j righe di H , con 0 j k≤ < , avremo una

sottomatrice ( )jH di k j− righe con solo 2k j− colonne distinte che non potranno

essere altro se non tutte le parole binarie di k j− bit.

Il peso della parola di codice ottenuta componendo le k j− righe di ( )jH , è

uguale al numero di colonne che hanno un numero dispari di 1 al loro interno. Ci si

convince facilmente che esattamente la metà delle 2k j− colonne diverse tra loro hanno

peso dispari. Il peso della parola di codice ottenuta componendo le k j− righe vale

122 2

2

k jj k

−−= , indipendente dal numero di righe cancellato, pur di non cancellarle

tutte, nel qualcaso otterremo la parola di codice nulla che ha peso 0 .

Quanto appena visto ci permette di concludere che la distanza minima per codici

generati da matrici di tipo H , o da matrici di tipo H vale 12k− , che è anche, la distanza

tra due parole di codice qualsiasi.


VI.2 Codici ortogonali e transortogonali Immaginiamo di utilizzare un codice generato da una matrice del tipo H ,

introdotta nel paragrafo VI.1, con una segnalazione di tipo antipodale, associando cioè ai

bit 0 un impulso di segnalazione in banda base ( )h t (la cui durata, per semplicità

possiamo pensare sia non maggiore dell’intervallo di segnalazione T ), e ai bit 1 il suo

opposto. Alla generica parola di codice verrà quindi associato il segnale in banda base:

( ) ( ) ( )2

1

1 ( 1 )

k

ic

i

x t h t i T=

= − − −∑c (VI.2.1)

Se effettuiamo il prodotto scalare tra i segnali associati a due distinte parole di

codice otteniamo:

Codici di Hamming 39

( ) ( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )( )

2 22*

01 1

2*

01

2 2

1 1

, 1 ( 1 ) 1 ( 1 )

1 1 ( )

1 1 1 02 2

k kk

i l

k

i

k k

i l i i

T c c

i l

Tc c

i

c c c cb bk ki i

h t i T h t l T dt

h t h t dt

k kE E

⊕

′′

= =

′

=

′ ′

= =

= − − − − − −

= − −

= − − = − =

∑ ∑∫

∑ ∫

∑ ∑

c cx x

(VI.2.2)

nella precedente bE indica l’energia del bit informativo, conseguentemente l’energia

specifica dell’impulso di segnalazione, che tiene conto del Rate 2k

k kn

= del codice,

vale 2

bk

kE . La sommatoria a ultimo membro vale 0 in quanto la distanza di Hamming

tra due parole di codice distinte vale 12k− .

Sotto le ipotesi appena fatte i segnali associati alle parole del codice generato dalla

matrice di parità estesa di un codice di Hamming H sono a due a due ortogonali. Per

quanto riguarda i codici duali dei codici di Hamming, nelle stesse condizioni generano

un set di 2k segnali isoenergetici in uno spazio a 2 1k − dimensioni. Detti segnali non

sono più mutuamente ortogonali, anche se la distanza tra una qualunque coppia di segna-

li è la stessa. I codici duali dei codici di Hamming si chiamano transortogonali. Rispetto

ai codici generati da matrici di tipo H i codici transortogonali hanno il vantaggio a pari-

tà d’energia bE di consentire un aumento dell’energia associata al bit della parola di co-

dice, in virtù del rate più basso, per questo le loro prestazioni sono leggermente migliori.


Capitolo VII

Codici Convoluzionali

VII.1 Premessa I codici convoluzionali furono proposti per la prima volta da P. Elias nel 1955, e

hanno trovato ampia applicazione dopo che A. J. Viterbi propose nel 1967 un efficiente

algoritmo di decodifica. Nei codificatori convoluzionali la parola prodotta non dipende

soltanto dalla parola emessa dalla sorgente al tempo presente, ma anche da quelle emesse

precedentemente. Si tratta quindi di un codificatore dotato di memoria.


VII.2 Struttura del codificatore Lo schema di principio di un codificatore convoluzionale è mostrato in Fig. VII.1.

Dove i simboli emessi dalla sorgente appartengono ad un alfabeto di cardinalità assegna-

ta ed i sommatori opera-

no modulo la cardinalità

dell’alfabeto.

Come si può nota-

re lo schema, a prima

vista, non differisce da

quello di un classico co-

dificatore per codici a

blocchi, se non fosse per

la dimensione dello shift

register d’ingresso che è

maggiore di quello d’u-

scita. La differenza sostanziale tra il codificatore di figura e quello di uno a blocchi, con-

siste nel fatto che il registro d’uscita, nel codificatore di figura, viene letto ogni due

simboli emessi dalla sorgente.

23 sT

2sT

3

iy⎡ ⎤⎢ ⎥⎣ ⎦

2

iy⎡ ⎤⎢ ⎥⎣ ⎦

1

iy⎡ ⎤⎢ ⎥⎣ ⎦

1

ix⎡ ⎤⎢ ⎥⎣ ⎦ 1

2

ix⎡ ⎤−⎢ ⎥⎣ ⎦2

ix⎡ ⎤⎢ ⎥⎣ ⎦ 1

1

ix⎡ ⎤−⎢ ⎥⎣ ⎦

2

1

ix⎡ ⎤−⎢ ⎥⎣ ⎦

2

2

ix⎡ ⎤−⎢ ⎥⎣ ⎦

SsT

sT

sT

sT

sT

sT

Fig. VII.1 - Schema di principio di un codificatore convoluzionale

42 Capitolo VII

In generale in un codificatore convoluzionale il numero di simboli che costituicono

la parola informativa è un sottomultiplo della lunghezza dello shift register d’ingresso. Il

rapporto tra il numero di celle dello shift register e il numero di simboli di sorgente che

costituiscono la parola informativa viene denominato lunghezza di vincolo (costraint

lenght).

Da quanto appena detto segue che la parola di codice non dipende soltanto dalla

parola d’ingresso attuale ma anche dalle 1V − parole emesse precedentemente dalla

sorgente (chiameremo V lunghezza di vincolo).

Nello schema di Fig. VII.1 la lunghezza di vincolo 3V = , la parola di codice

dipenderà pertanto dalla parola corrente e dalle 2 parole informative che la precedono.

Anche nei codificatori convoluzionali si può definire un rate espresso dal rapporto

tra la lunghezza della parola informativa (2 in Fig. VII.1) e quella della parola di codice

generata (3 in Fig. VII.1). A differenza dei codici a blocchi le lunghezze, sia delle parole

d’ingresso, sia di quelle di codice, sono piccole (dell’ordine delle unità), inoltre i simboli

emessi appartengono tipicamente a 2 .


VII.3 Matrice generatrice e generatori. I codificatori convoluzionali come si evince dalla figura del paragrafo precedente

sono lineari. Essi se la

lunghezza di vincolo

fosse unitaria dege-

nererebbero in un

codificatore a blocco.

Se la lunghezza di

vincolo è maggiore di

uno la sequenza d’u-

scita dipende dall’in-

tera sequenza d’ingresso. In ogni caso possiamo affermare che la sequenza codificata

associata a una generica sequenza informativa può sempre essere ottenuta come

Sequenze di ingresso Sequenze codificate 10,00,00,00,0… 001,100,001,000… 01,00,00,00,0… 010,010,100,000… 00,10,00,00,0… 000,001,100,001,000… 00,01,00,00,0… 000,010,010,100,000… 00,00,10,00,0… 000,000,001,100,001,000 00,00,01,00,0… 000,000,010,010,100,000… 00,00,00,10,00,0… 000,000,000,001,100,001,000 00,00,00,01,00,0… 000,000,000,010,010,100,000… Tabella VII.1 - sequenze di uscita del codificatore di Fig. VII.1 in

corrispondenza alle sequenze canoniche

Codici Convoluzionali 43

combinazione lineare delle risposte che il codificatore genererebbe in corrispondenza a

sequenze “canoniche”, cioè a sequenze seminfinite contenenti un unico bit 1. In Tabella

VII.1 sono mostrate le sequenze d’uscita che si otterrebbero dall’analisi del codificatore

Fig. VII.1 in corrispondenza alle citate sequenze, assumendo che in assenza di una

sequenza in ingresso tutte le celle dello shift register contengano il bit 0. Le sequenze

codificate della tabella si possono pensare come le righe di una matrice generatrice del

codice. Detta matrice ha dimensioni semi infinite, motivo questo di per sè sufficiente per

cercare un approccio più efficiente allo studio dei codici in parola. È interessante

osservare che la matrice generatrice ha una struttura ben precisa, come si desume dalla

tabella essa ha una struttura a blocchi del tipo:

1 2 3

1 2 3

31 2

0 0 0

0 00

00 0

G G G

G G G

GG G

⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ ⎣ ⎦

⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ ⎣ ⎦

⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎣ ⎦⎣ ⎦ ⎣ ⎦

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣

… …… …

… …… … … …… … … …

(VII.3.1)

dove le iG⎡ ⎤⎣ ⎦ rappresentano matrici 2 3× e gli zeri indicano matrici nulle delle stesse

dimensioni. Osservando la struttura della generica iG⎡ ⎤⎣ ⎦ ci si rende conto che essa è in

realtà la matrice generatrice di un codice a blocchi 3,2 , il suo generico elemento ilmg⎡ ⎤⎣ ⎦

vale cioè 1 solo se l’l -esima cella dell’ i -esimo blocco dello shift register di ingresso è

connessa al sommatore m - esimo.

La (VII.3.1) è di scarsa utilità pratica. Le matrici iG⎡ ⎤⎣ ⎦ potrebbero essere si usate

per descrivere la struttura del codificatore, ma, anche a questo scopo, esse si rivelano in

genere meno efficienti dei cosiddetti generatori. I generatori sono n vettori binari

ciascuno con kV componenti. Dove la i -esima componente dell’m -esimo generatore

vale 1 solo se l’m -esimo sommatore è connesso all’ i -esima cella del registro

d’ingresso.

Per il codificatore di Fig. VII.1 i generatori sono:

44 Capitolo VII

1

2

3

100010

010100

001001

g

g

g

⎡ ⎤⎣ ⎦

⎡ ⎤⎣ ⎦

⎡ ⎤⎣ ⎦

=

=

=

(VII.3.2)

Noto il rate del codificatore i generatori permettono di tracciare facilmente lo

schema del codificatore.

Il vantaggio che si ha nell’utilizzo dei generatori rispetto all’uso delle matrici co-

stituenti la matrice generatrice è legato al fatto che i generatori sono in numero pari al

numero di bit della parola d’uscita dell’ordine delle unità, mentre le matrici in parola so-

no in numero pari alla lunghezza di vincolo che può essere dell’ordine delle decine. Inol-

tre i generatori si prestano a essere rappresentati in notazione diversa da quella binaria,

tipicamente quella ottale, rappresentando cioè gruppi di tre bit con la corrispondente ci-

fra ottale per il nontro codificatore ciascun generatore si può rappresentare mediante due

cifre ottali in particolare si ha:

18

28

38

42

24

11

g

g

g

⎡ ⎤⎣ ⎦

⎡ ⎤⎣ ⎦

⎡ ⎤⎣ ⎦

=

=

=

(VII.3.3)

VII.4 Diagramma di stato del codificatore. Equation Section (Next) La matrice generatrice, non è certamente uno strumento di semplice impiego per

analizzare un codificatore convoluzionale. I generatori sono sì un efficace strumento per

descriverne la struttura, ma anch’essi mal si prestano al calcolo della sequenza d’uscita

del codificatore. Un modo alternativo, certamente più efficace, per descrivere il compor-

tamento del codificatore è quello di tener conto del fatto che l’uscita prodotta in un certo

istante dipende oltre che dalla parola d’ingresso corrente anche dalla storia della sequen-

za d’ingresso, in particolare essa dipende dai ( )1k V − bit d’ingresso che hanno prece-

duto la parola corrente. In altri termini, noti tali bit e i k bit della parola corrente pos-

sono essere determinati univocamente, sia l’uscita corrente, sia i ( )1k V − bit che con-

tribuiranno unitamente alla parola d’ingresso successiva a determinare la parola d’uscita

seguente. Osserviamo che esistono esattamente ( )12k V− contenuti distinti per le celle del


registro che costituiscono la memoria del sistema. Possiamo dire pertanto che il codifi-

catore può assumere ( )12k V− stati diversi (16 nel nostro esempio). L’arrivo di una parola

d’ingresso comporta tipicamente una variazione del contenuto della memoria, quindi una

variazione dello stato del sistema. In sintesi un codificatore convoluzionale è una mac-

china a stati finiti.

Gli stati del codificatore possono essere associati ai vertici di un grafo (vedi Esem-

pio III.1 parte I) due vertici vengono connessi tramite un lato se esiste una parola di in-

gresso che induce la transizione tra i due stati. Ad ogni lato potremo associare un’e-

tichetta che contiene la parola d’ingresso ad esso relativa, ma anche la corrispondente

parola di uscita che dipende anche dal vertice da cui il suddetto lato fuoriesce.

Osserviamo che da ogni vertice origineranno e si dipartiranno esattamente 2k lati,

tanti quante sono le possibili parole d’ingresso (nel nostro esempio 4). Quindi ogni ver-

tice è di grado ( )12 k+ . Il grafo è anche connesso in quanto, comunque scelti due vertici

distinti, esiste sempre

un percorso che li

congiunge, osservia-

mo che tale percorso

è costituito al più da

( )1V − lati.

Il grafo relativo

al codificatore di Fig.

VII.1 è mostrato in

Fig. VII.2 dove si so-

no utilizzati colori di-

versi per distinguere

le parole d’ingresso

associate ai lati. Nella

stessa figura si sono

indicate solo alcune

1000

1010

0100

0101

1111

1100

0001

0010

0011

0110

0111

1001

10111101

1110

0000

00

01

10

11

111

000

100

100

111

Fig. VII.2 - Grafo del codificatore mostrato in Fig. VII.1

46 Capitolo VII

parole d’uscita per non pregiudicarne la leggibilità.

Tracciato che sia il grafo del codificatore, per dato stato iniziale, si può valutare la

sequenza codificata associata a una qualsiasi sequenza d’ingresso seguendo il percorso a

essa individuato ed annotando le corrispondenti parole d’uscita. Ovviamente per se-

quenze molto lunghe, anche questa rappresentazione manifesta dei limiti, si pensi al caso

in cui uno stesso lato compaia più volte nell’ambito di una stessa sequenza.


VII.5 Codici catastrofici Osserviamo che ogni codificatore convoluzionale associa alla sequenza d’ingresso

nulla la sequenza nulla, ciò è un’immediata conseguenza della sua linearità.

Il percorso associato alla sequenza di ingresso identicamente nulla nel grafo di Fig.

VII.1 consisterebbe nel percorrere infinite volte il ramo che emerge e termina nello stato

zero. I rami che originano e terminano nello stesso stato vengono denominati self loop.

Notiamo che lo stesso codificatore associa alla sequenza costituita solo da bit 1 , la

sequenza 011 101 000 000 000 000… come possiamo notare tale sequenza seppur se-

mi-infinita ha peso 4 ; cioè, nonostante la sequenza di ingresso considerata sia quella a

massima distanza dalla sequenza nulla, le rispettive sequenze codificate distano tra loro

non più di 4 indipendentemente dalla loro lunghezza. Il codificatore di Fig. VII.1 è un

classico esempio di Codice catastrofico. Tale denominazione discende dal fatto che da

un codificatore ci si aspetta quantomeno che al crescere della distanza di Hamming tra le

sequenze d’ingresso (parliamo si sequenze semi-infinite) cresca anche quella tra le

corrispondenti sequenze codificate. Il motivo per il quale il “nostro” codificatore è

catastrofico risiede nella presenza di un selfloop che associa a una parola di peso non

nullo la parola d’uscita nulla, sicchè ciclando su questo ramo il peso della sequenza

d’uscita non varia. Il codificatore fin qui utilizzato, malgrado sia catastrofico non perde

la sua valenza che è puramente didattica.



VII.6 Trellis degli stati I limiti all’utilizzo del grafo per lo studio di un codice convoluzionale, sono essen-

zialmente legati al fatto che in questa rappresentazione non compare il tempo.

Premesso che in quel che segue per brevità enumereremo talvolta gli stati con il

numero decimale corrispondente al contenuto della memoria, supponiamo che all’istante

iniziale il codificatore si trovi nello stato 0 , da esso all’istante skT , potranno essere rag-

0 8sT6

sT4

sT2

sT

0 0 0 0

0 1 0 0

1 0 0 0

1 1 0 0

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

0 0 0 0

0 0 0 1 1 0 1 1

0 0 0 0 0 0 0 0 0 0 0 0

Fig. VII.3– Trellis degli stati del codificatore di Fig. VII.1

48 Capitolo VII

giunti 2k nuovi stati figli e da ciascuno di questi ultimi all’istante 2 skT ne potranno

essere raggiunti 2k per un totale di 22 k stati figli raggiungili all’istante 2s

kT .

Ci rendiamo conto del fatto che all’istante ( )1 sV kT− tutti i possibili stati del co-

dificatore saranno raggiungibili. Ciò è vero anche in virtù del fatto che, per la struttura

del codificatore, partendo da un qualsiasi stato, a parole d’ingresso distinte corrispondo-

no necessariamente stati di arrivo distinti.

Quanto appena detto può essere rappresentato graficamente mediante il trellis

(letteralmente graticcio) degli stati del codice. Il trellis associato al codificatore di Fig.

VII.1 è rappresentato in Fig. VII.3 Come possiamo notare il trellis è un albero, che ha

origine nello stato in cui si trova il codificatore all’istante iniziale, che generalmente, ma

non necessariamente, è lo stato 0 . Esso costituisce la radice dell’albero, da cui si

dipartono i lati associati a tutte le possibili parole di ingresso che terminano sui 2k

vertici raggiungibili all’istante skT da ciascuno di detti vertici si dipartiranno 2k

ulteriori lati che termineranno su 22 k vertici figli al tempo 2 skT .

Al tempo ( )1 sV kT− tutti gli stati vengo-

no raggiunti da un lato ed al passo successivo la

sezione di trellis, cioè l’insieme dei lati com-

presi tra i vertici relativi a due istanti di tempo

consecutivi, è completa, nel senso che contiene

tutti i possibili lati, tutte le sezioni successive

saranno complete, uguali tra loro ed, ideal-

mente, in numero infinito. Ogni sezione si può

etichettare con un numero che esprime la “pro-

fondità” della sezione cioè la collocazione di

una data sezione nel trellis.

Seguire l’evoluzione dell’uscita sul trellis è semplice in quanto il percorso

associato alla sequenza d’ingresso non vi sono sovrapposizioni.

Esempio VII.1

1sT

2

2

iy⎡ ⎤⎢ ⎥⎣ ⎦

1

iy⎡ ⎤⎢ ⎥⎣ ⎦

S

sT

sT

sT

sT

[ ]1ix −[ ]ix [ ]2ix − [ ]3ix −

Fig. VII.4 schema del codificatore convo-

luzionale 8 815 ,17 rate 12


Si Calcoli l’uscita del codice di rate 12

individuato dai generatori 8 815 ,17 . In corrispondenza alla

sequenza d’ingresso 101100 . I due generatori rappresentati in binario sono:

1

2

1101

1111

g

g

⎡ ⎤⎣ ⎦

⎡ ⎤⎣ ⎦

=

= (VII.6.1)

e corrispondono allo schema mostrato in Fig. VII.4. Il codificatore ha 8 stati, il suo trellis è mostrato in Fig. VII.5, nella stessa figura è evidenziato il

percorso associato alla sequenza di ingresso 101100 , la corrispondente sequenza d’uscita è quindi: 11 11 01 11 01 01 .

È interessante osservare che un ulteriore zero nella sequenza d’ingresso riporterebbe il co-dificatore allo stato zero.


VII.7 Decodifica hard e decodifica soft di un codice convoluzionale. Occupiamoci adesso della decodifica utilizzando il criterio della massima verosimi-

glianza.

Facciamo riferimento per chiarirci le idee allo schema di principio mostrato in Fig.

VII.6. Esso rappresenta una sorgente binaria che emette una sequenza binaria di kN bit,

{ }1

kNi ix

=, cui è connesso un codificatore covoluzionale con rate

kn

che produce una se-

quenza codificata di nN bit, { }1

nNi ic

=, che modula antipodalmente un impulso di segna-

000

0

1

100

000

010

100

110

00000 00 00 00 00 00

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

000

Fig. VII.5 – Trellis del codice convoluzionale 8 815 ,17 rate 12

50 Capitolo VII

lazione ( )p t in banda base di durata non maggiore dell’intervallo s bk

T Tn

= assegnato

ad ogni bit codificato ottenendo il segnale ( ) ( ) ( )( )1

2 1 1nN

i si

s t c p t i T=

= − − −∑ .

( )s t viene quindi inviato su un canale AWGN che introduce cioè un rumore

gaussiano ( )n t con densità spettrale di potenza bilatera η .

Il segnale ( )r t , in uscita al canale, che perviene al ricevitore, trascurando ritardo

ed attenuazione, sarà quindi ( ) ( ) ( )r t s t n t= + .

Il ricevitore di figura è costituito da un filtro adattato all’impulso di segnalazione la

cui uscita viene campionata a cadenza sT , producendo la sequenza { }1

nNi ir

=, che per le

ipotesi fatte non sarà affetta da interferenza intersimbolica. Avremo cioè

2 1i i ir c n= − + in cui in è una variabile aleatoria Gaussiana a media nulla e varianza

η . Ne segue che la generica ir , condizionata all’invio di ic è la realizzazione di una

( )n t

filtroadattato

rivelatorea soglia

decodificatorehard

decodificatoresoft

S

bT

{ } 1

kNi i

x=

Codificatoreconvoluzionale Modulatore

sT

sT

{ } 1

nNi i

c=

{ } 1

nNi i

c=

( ) ( ) ( )r t s t n t= +

( ) ( ) ( )( )1

2 1 1nN

i si

s t c p t i T=

= − − −∑

{ } { }1 12 1nN nN

i i ii ir c n

= == − + { } { }1 1

ˆ ˆe/onN kNi ii i

c x= =

Fig. VII.6 – schema di principio di un sistema di trasmissione, con codificatore convoluzionale e modulazione

antipodale in banda base - decodificatore hard, ramo superiore, decodificatore soft, ramo inferiore.


variabile aleatoria gaussiana a media 2 1ic − e varianza η . Inoltre Le ir condizionate

all’invio di una data { }1

nNi ic

= saranno mutualmente statisticamente indipendenti.

In Fig. VII.6 Abbiamo a questo punto indicato due alternative:

- la prima (ramo superiore) consiste nell’utilizzare un rivelatore a soglia che

fornirebbe in uscita una sequenza binaria stimata { }1

nNi ic

=, da dare in

“pasto” ad un decodificatore che in questo caso sarebbe di tipo hard;

- la seconda (ramo inferiore in Fig. VII.6) utilizzare un decodificatore in

grado di utilizzare direttamente la { }1

nNi ir

= in questo caso il nostro

decodificatore sarebbe di tipo soft.

Indipendentemente dal tipo di decodificatore viene prodotta una sequenza

informativa stimata { } 1ˆkN

i ix

= ottenuta in corrispondenza a una sequenza codificata

{ } 1ˆnN

i ic

=, cioè una sequenza che corrisponde ad un percorso sul trellis del codificatore.

Ovviamente non è detto che i due decodificatori producano la stessa { }1

ˆkN

i ix

=.

In quel che segue supporremo di voler decodificare una sequenza di lunghezza

finita. Supporremo anche che il decodificatore hard o soft che sia:

- conosca la struttura del codificatore convoluzionale;

- conosca lo stato iniziale ins del codificatore;

- conosca lo stato finale fins del codificatore,

Osserviamo che la conoscenza dello stato finale da parte del decodificatore, impli-

ca che il codificatore abbia provveduto ad aggiungere alla sequenza informativa un

suffisso in grado di condurre il codificatore in uno stato assegnato. Va da se che i

simboli del suffisso non conterranno informazione e comporteranno quindi un

peggioramento dell’effettivo rate del codice. Tale peggioramento sarà tanto meno

rilevante quanto più lunghe saranno le sequenze da trasmettere.

52 Capitolo VII

Osserviamo che in linea di principio la decodifica MV hard della sequenza

{ } 1

nMi ic

= costituita da M n -uple di bit in uscita al rivelatore a soglia è semplice, è, in-

fatti, sufficiente scegliere la sequenza ammissibile2 che ha la minima distanza di Ham-

ming dalla { } 1

Mni ic

= generata dal rivelatore, scegliendo eventualmente a caso qualora do-

vesse esservi più d’una sequenza ammissibile con lo stesso requisito.

Analogamente la decodifica MV soft consisterebbe nello scegliere, tra le sequenze

ammissibili, quella cui è associata una sequenza { } 1ˆ2 1

Mni ic

=− che, pensata come un

punto di Mn , ha la minima distanza Euclidea dalla sequenza { }1

Mni ir

= corrispondente al

segnale ricevuto, rappresentata nello stesso spazio. Va da se che, in questo caso, la

probabilità che due sequenze ammissibili abbiano la stessa distanza da quella ricevuta è

nulla.

Già questa sola considerazione ci fa intuire che l’impiego della decodifica soft

migliora le prestazioni del sistema in termini di probabilità d’errore.

Al crescere della lunghezza dei messaggi da decodificare, appare chiaro che

l’approccio sopra descritto seppur formalmente corretto diventa improponibile in pratica,

sia per la crescita esponenziale del numero di sequenze ammissibili, sia per il ritardo che

un decodificatore siffatto comporterebbe. Sarebbe infatti indispensabile attendere la rice-

zione dell’intera sequenza prima che il processo di decodifica abbia inizio.


VII.8 L’algoritmo di Viterbi In questo paragrafo descriveremo un algoritmo di decodifica che, con modifiche

non concettuali, può essere impiegato sia per decodificatori hard che soft dei codici

convoluzionali.

In quel che segue chiameremo:

2 per sequenza ammissibile intendiamo una sequenza { } 1

Mni ic

= associabile ad un percorso sul trellis che abbia

inizio in ins e termini in fins .


- metrica di ramo la distanza di Hamming, o il quadrato della distanza Euclidea, tra

gli n bit 1 2,L LL L

xy nb b b⎡ ⎤ ⎡ ⎤⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦⎣ ⎦ ⎣ ⎦⎡ ⎤= ⎢ ⎥⎣ ⎦

b … codificati che etichettano il ramo e la porzione di

sequenza ricevuta corrispondente precisamente

( )( )

( ) ( )1

12

11

2

metrica di Hamming

1 metrica Euclidea

L

nL

L n i ii

xy nL

L n i ii

b

b

cm

r

⎡ ⎤⎣ ⎦

⎡ ⎤⎣ ⎦− +

=

⎡ ⎤⎣ ⎦− +

=

⊕⎧⎪⎪⎪⎪⎪⎪= ⎨⎪⎪ ⎡ ⎤⎪ − −⎢ ⎥⎪ ⎣ ⎦⎪⎪⎩

∑

∑b (VII.8.1)

(ad apice abbiamo indicato la sezione di trellis cui il ramo appartiene ed i pedici,

,x y individuano lo stato di partenza e quello di arrivo del ramo in esame);

- percorso una sequenza ininterrotta di rami che origina in ins

- lunghezza del percorso il numero di rami compongono il percorso

- metrica di percorso la somma delle metriche di ramo che compongono il percorso;

- cammino una sequenza ininterrotta di rami del tipo 1 1

, , ,,H H H J

x y y z i l

⎡ ⎤ ⎡ ⎤ ⎡ ⎤+ + −⎣ ⎦ ⎣ ⎦ ⎣ ⎦⎡ ⎤⎢ ⎥⎣ ⎦b b b…

- lunghezza del cammino il numero di rami compongono il cammino

- metrica di cammino la somma delle metriche dei rami che lo compongono;

Abbiamo detto che il decodificatore conosce lo stato iniziale in cui si trova il codi-

ficatore all’arrivo di una sequenza informativa, supponiamo sia lo stato zero. Al primo

passo, osservando la sequenza ricevuta, il decodificatore può etichettare ciascuno dei 2k

rami del trellis che emergono dallo stato iniziale, con la metrica ad essi associata, calco-

lata mediante la prima o la seconda delle (VII.8.1), a seconda che la decodifica sia di tipo

hard o soft rispettivamente. Il decodificatore provvederà anche ad etichettare gli stati

raggiunti con le metriche dei percorsi che vi pervengono. Le metriche di percorso in que-

sto caso coincidono banalmente con quelle del singolo ramo che compone i percorsi cui

si riferiscono. Agli stati raggiunti verrà associata anche la sequenza informativa associata

al relativo percorso.

Al secondo passo da ciascuno dei 2k stati raggiunti emergeranno 2k rami, a

ciascuno di essi si può associare una metrica di ramo come al passo precedente. Ad ogni

stato in cui termina un ramo assoceremo:

54 Capitolo VII

- una metrica di percorso ottenuta sommando alla metrica del ramo che termina nello

stato in parola quella di percorso associata allo stato da cui il ramo emergeva;

- una sequenza informativa di percorso ottenuta giustapponendo a quella associata

allo stato di partenza quella del ramo.

Potremo continuare ad addentrarci nel trellis seguendo questa logica fino al passo

1V − , in quanto fino a tale passo ogni stato viene raggiunto al più da un percorso.

Al V - esimo passo potremo ancora associare ad ogni ramo la sua metrica, ma per

associare le metriche di percorso agli stati sorgerà un problema. Esistono infatti 2k

percorsi distinti che terminano in ciascuno stato.

Se consideriamo un cammino nel trellis di lunghezza 1J ≥ che abbia origine in

uno stato in cui confluiscano 2k percorsi di lunghezza M , giustapponendo il cammino a

ciascun percorso di lunghezza M otterremmo 2k percorsi ammissibili di lunghezza

M J+ . La metrica di ciasuno di essi sarà data dalla somma della metrica di uno dei

percorsi di lunghezza M più la metrica del cammino. Tra i percorsi così ottenuti quello

che avrà la metrica minore sarà evidentemente ottenuto a partire dal percorso di

lunghezza M che aveva la metrica minore. Ne segue che se più percorsi confluiscono in

uno stesso stato ha senso memorizzare solo quello che ha la metrica minore.

Osserviamo che nel caso in cui la metrica fosse quella di Hamming (decodifica

hard) potrebbe darsi che più di un percorso abbia minima metrica, il decodificatore in

questa eventualità dovrebbe scegliere a caso.

Dal V - esimo passo in poi il decodificatore memorizzerà per ogni stato solo la

metrica e la sequenza informativa associata al “miglior” percorso che vi confluisce.

Fa eccezione solo l’ultimo passo, in questo caso il decodificatore conoscendo lo

stato di arrivo si limiterà a considerare solo i 2k percorsi che vi confluiscono scegliendo

il migliore tra essi (quello che ha accumulato la metrica minore).

Abbiamo appena descritto l’algoritmo di Viterbi.

VII.9 Efficienza dell’algoritmo di Viterbi Appare evidente la riduzione di complessità di questo algoritmo rispetto alla ricerca

esaustiva teorizzata nel paragrafo precedente. Ad ogni passo di decodifica, a parte il


transitorio iniziale, dovremo infatti calcolare 2k metriche di ramo per ciascuno dei

( )12k V− stati iniziali della sezione di trellis ed utilizzarle per calcolare le metriche di

2kV percorsi. Di questi ultimi solo ( )12k V − verranno memorizzati per utilizzarli al passo

successivo. Ne segue che la complessità dell’algoritmo cresce solo linearmente con la

lunghezza della sequenza informativa, a differenza della ricerca esaustiva che invece cre-

scerebbe esponenzialmente. Va comunque sottolineato che la complessità dell’algoritmo

di Viterbi cresce esponenzialmente con la lunghezza di vincolo del codificatore.

Un altro vantaggio nell’utizzo dell’algoritmo di Viterbi consiste nel fatto che dopo

un certo numero di passi di decodifica che dipende dalla lunghezza di vincolo

(tipicamente una decina di lunghezze di vincolo) tutti i percorsi “sopravvissuti” fini-

scono con l’avere una parte iniziale in comune. Ciò limita sia la latenza sia il fabbisogno

di memoria del decodificatore.


VII.10 Funzione di trasferimento di un codificatore convoluzionale. I codici convoluzionali sono come abbiamo già detto lineari, nel senso che la

somma di due sequenze codificate è ancora una sequenza codificata, esattamente quella

che si otterrebbe codificando la somma delle due sequenze informative.

Ciò significa possiamo valutare le prestazioni del codice in termini di probabilità

d’errore ammettendo che venga inviata la sequenza nulla e valutare la probabilità che per

effetto del canale venga rivelata dal decodificatore una sequenza diversa.

Per i nostri scopi è utile definire alcune grandezze associate al codificatore. La

prima è la cosiddetta distanza colonna ( )cold N essa è in realtà un’applicazione che

associa ad ogni livello di profondità del trellis del codice la minima distanza ottenibile

dalla sequenza nulla prendendo in considerazione tutte le possibili sequenze d’ingresso

cui corrispondono percorsi sul trellis che si discostano da quello relativo alla sequenza

nulla a partire dall’istante iniziale. Il limite di ( )cold N per N → ∞ si chiama distanza

libera, fd , del codice. Il percorso cui corrisponde la distanza libera non è necessariamen-

te unico, ma certamente salvo il caso in cui il codice sia catastrofico è un percorso che si

56 Capitolo VII

discosta dalla sequenza nulla per poi ricongiungersi ad essa. Sia la distanza colonna che

la distanza libera possono in teoria essere calcolate per ispezione diretta sul trellis del

codice, ma è anche possibile ottenere la distanza libera e molte altre informazioni sul

codice procedendo in modo diverso.

Ci proponiamo in particolare di raccogliere informazioni sul numero di percorsi che

hanno origine e termine nello stato zero diversi da quello che da esso non si discosta

mai.

Per farlo consideriamo il diagramma degli stati del codificatore e sopprimiamo il

self loop associato allo stato zero sdoppiamo quindi lo stato zero in due stati uno, sor-

gente, da cui fuoriescono i rami ed uno, pozzo con solo rami entranti come in Fig. VII.7.

Nella stessa figura si può notare anche che i rami del grafo sono stati etichettati con dei

trinomi l’indeterminata L vi compare sempre con grado 1 , la sua funzione è in realtà

solo quella di tener conto del passaggio attraverso il ramo, il grado di J esprimerà il

peso della parola informativa associata al ramo esso è quindi compreso tra 0 e k , il

grado di D esprimerà il peso della parola di codice associata al ramo, non potrà quindi

essere maggiore di n .

Basandoci sulla teoria dei grafi orientati e pesati possiamo ricavare la funzione di

trasferimento tra il nodo sorgente ed il nodo pozzo. Per farlo si può procedere in due

modi, il più semplice consiste nello scrivere il sistema lineare di equazioni che il grafo

rappresenta. Per farlo ricordiamo che ad ogni nodo, corrisponde una incognita del siste-

4

1 0

2 35

6 70

JLD

L

JLD

JLD

LD2

Fig. VII.7 – Grafo modificato del Codice 8 815 ,17 rate 12


ma. In corrispondenza a ciascun nodo possiamo scrivere un’equazione che, detta jV

l’incognita associata al nodo j -esimo e lmT la trasferenza associata al ramo che emerge

dal nodo l -esimo e converge in quello m -esimo, sarà del tipo:

( )12

0

k V

j i iji

V VT

−

=

= ∑ (VII.9.1)

Osserviamo che l’equazione associata al ramo sorgente si riduce ad un’identità es-

sendo quest’ultimo privo di rami entranti. A titolo d’esempio, denominando rispettiva-

mente inV e outV le variabili associate al nodo sorgente ed al nodo pozzo in cui abbiamo

sdoppiato lo stato 0 , scriviamo le equazioni associate al grafo di Fig. VII.7:

1 2 32

2 4 5

3 6 72

4 1

5 2 32

6 4 5

7 6 72

1

in

out

V LDV LDV

V LD V LV

V LDV LDV

V JLD V JLDV

V JLDV JLDV

V JLV JLD V

V JLDV JLDV

V LD V

⎧ = +⎪⎪⎪⎪ = +⎪⎪⎪⎪ = +⎪⎪⎪⎪ = +⎪⎨⎪ = +⎪⎪⎪ = +⎪⎪⎪⎪ = +⎪⎪⎪⎪ =⎪⎩

(VII.9.2)

Possiamo quindi procedere all’eliminazione di tutte le variabili ad eccezione delle

inV e outV . Utilizzando ad esempio le prime tre equazioni otteniamo

2 3 2 3 3 3 35 6 7

4 3 4

2 3 2 2 2 2 25 4 5 6 7

26 4 5

7 6 73 5 3 3 3 4 3 4

4 5 6 7

1in

out

JLD V JL D V JL D V JL D VV

JL DV JL D V JL DV JL D V JL D V

V JLV JLD V

V JLDV JLDV

V L D V L D V L D V L D V

⎧⎪ + + +⎪ =⎪⎪⎪ −⎪⎪ = + + +⎪⎪⎪⎪ = +⎨⎪⎪ = +⎪⎪⎪⎪ = + + +⎪⎪⎪⎪⎪⎩

(VII.9.3)

Quindi, procedendo in modo analogo, dopo “qualche semplice” passaggio ottenia-

mo:

58 Capitolo VII

( )4 7 2 5 6 2 5 8

2 3 4 2 3 2 2 3 4 2 4 3 2 4 5, ,

1out

in

V JL D J L D J L DT J L D

V JLD JL D JL D J L D J L D J L D J L D

+ −=

− − − + − − +(VII.9.4)

la ( ), ,T J L D prende il nome di funzione di trasferimento del codice.

Se con la tecnica della divisione lunga espandiamo la (VII.9.4), pensando il nume-

ratore e il denominatore come polinomi nell’indeterminata D , possiamo ancora scrivere:

( ) 2 5 6 4 3 6 3 7 7 2 6 4 7 4 8 4 9 8

3 8 5 8 4 9 5 9 5 10 5 11 9

3 8 4 8 6 9 4 10 5 10 6 10 5 11 6 11 6 12 6 13 10

, , ( ) ( )

( )

(2 2 2 ) ....

T J L D J L D JL J L J L D J L J L J L J L D

J L J L J L J L J L J L D

J L J L J L J L J L J L J L J L J L J L D

= + + + + + + + +

+ + + + + + +

+ + + + + + + + + + +

(VII.9.5)

dal coefficiente della potenza più piccola di D a secondo membro della precedente, de-

sumiamo che vi è un cammino con peso d’ingresso 2 che si discosta dallo stato 0 e che

torna ad esso dopo 5 rami accumulando un peso d’uscita pari a 6 . Ne segue che la

distanza libera del codice in parola sarà esattamente 6fd = . Osservando il coefficiente

della potenza di D immediatamente superiore scopriamo che esistono anche tre percorsi

con peso d’uscita 7, di cui: uno di lunghezza 4 e peso d’ingresso 1; il secondo di

lunghezza 6 e peso d’ingresso 3; il terzo di lunghezza 7 con peso d’ingresso 3, e così via.

Qualora fossimo interessati solo al peso delle sequenze codificate che si discostano

dalla sequenza nulla per poi ricongiungersi con essa, potremmo porre nella (VII.9.4) o

nella (VII.9.5) 1J = e 1L = , ottenendo

( ) 6 7 8 9 103 4 6 13 ....T D D D D D D= + + + + + (VII.9.6)

In generale la funzione di trasferimento di un codice convoluzionale può essere

espressa nella forma:

( ) ( )2 1

, , , ,fd

T J L D w J L Dι λ δ

δ λ ι

δ λ ι∞ ∞ ∞

= = =

= ∑ ∑∑ (VII.9.7)

dove ( ), ,w δ λ ι esprime il numero di cammini di peso δ , con peso della sequenza

d’ingresso ι che emergono dallo stato zero per poi farvi ritorno dopo λ rami.

Dalla precedente, eguagliando ad 1 le variabili che non ci interessano e sommando

rispetto ai rispettivi indici, otteniamo delle funzioni di trasferimento semplificate, ad

esempio ponendo 1J = e 1L = nella (VII.9.7) otteniamo


( ) ( ) ( ) ( )1, 1

2 1

, , , ,f f

J Ld d

T D T J L D w D w Dδ δ

δ λ ι δ

δ λ ι δ∞ ∞ ∞ ∞

= == = = =

= =∑ ∑∑ ∑ (VII.9.8)

dove ( ) ( )2 1

, ,w wλ ι

δ δ λ ι∞ ∞

= =∑∑ .


VII.11 Bound sulla probabilità di primo evento d’errore. Per analizzare le prestazioni di un codice convoluzionale si fa riferimento, oltre che

alla probabilità d’errore sul bit informativo anche alla cosiddetta probabilità di primo

evento d’errore, o anche probabilità d’errore di nodo. Essa esprime la probabilità che in

un certo istante la sequenza stimata si discosti da quella effettivamente trasmessa per poi

ricongiungersi con essa. Possiamo sempre assumere ai fini del calcolo della probabilità

d’errore, che la sequenza trasmessa sia quella identicamente nulla. Ciò in virtù della

linearità del codificatore e del fatto che la decodifica che effettuiamo è a MV,.

Sappiamo che il decodificatore opera le sue scelte basandosi sulla sequenza binaria

{ }ic prodotta dal rivelatore a soglia nel caso di decodifica hard, ovvero sulla sequenza

reale { }ir dei campioni in uscita al filtro adattato per decodifica soft.

Ammettiamo che fino alla profondità α nel trellis il decodificatore non abbia

commesso errori. In altri termini la sequenza nulla è quella che fino al passo α ha accu-

mulato la più piccola metrica di percorso. Al passo successivo ha inizio un evento

d’errore, cioè avrà origine un cammino ( ){ } ( )

1

lnll i

nP c

α ν

α

+

+. In realtà, che si è innescato

l’evento errore associato a lP , risulta evidente solo quando alla profondità lα ν+ il

percorso che lo contiene raggiunge nuovamente lo stato 0 , ed il decodificatore preferi-

sce quest’ultimo al percorso corretto, quello che dallo stato 0 non si discosta mai, aven-

do esso accumulato una metrica minore.

Osserviamo che ai fini di tale scelta saranno determinanti soltanto le metriche accu-

mulate dal cammino corretto 0 lP ν e lP , in quanto fino al passo α i due percorsi coinci-

devano quindi condividevano la stessa metrica.

60 Capitolo VII

Il calcolo esatto della probabilità di primo evento d’errore è purtroppo impraticabi-

le, possiamo tuttavia maggiorare la probabilità cercata, basandoci sull’union bound.

Per farlo dobbiamo valutare in corrispondenza a ciascun evento d’errore la probabi-

lità che esso si manifesti nell’ipotesi che il decodificatore possa scegliere solo tra il cam-

mino corretto e quello relativo all’evento d’errore in parola.

Ciò, detto in altri termini, equivale a calcolare la probabilità che la porzione di se-

quenza { } ( )1ln

i i nc

α ν

α

+

= + in uscita al rivelatore a soglia, per il decodificatore hard, o la por-

zione { } ( )1ln

i i nr

α ν

α

+

= + di campioni in uscita al filtro adattato per quello soft, corrispondente

alle sezioni del trellis che contengono i due cammini 0 lP ν e lP , a causa del rumore in-

trodotto dal canale, appartenga alla regione di decisione di lP malgrado la sequenza

inviata fosse quella identicamente nulla.

Una piccola riflessione ci convince che la somma di tutte le probabilità appena

descritte maggiora la probabilità d’errore di nodo, in quanto quest’ultima rappresenta la

probabilità dell’evento unione tra tutti quelli associati ai possibili cammini che dallo

stato zero si discostano per poi ricongiungersi ad esso.

Detto 0 , llP PR

νil complementare della regione di decisione del cammino corretto,

possiamo scrivere, per un codice con rate kn

:

{ } ( ) { } { }( )0 ,11

Pr | 0l

nodo ll

ne i P P ii n

l

P c R cν

α ν

α

∞+

= +=

≤ ∈ =∑ (VII.10.1)

Nel caso di decodifica hard è opportuno osservare che ai fini del calcolo della

probabilità che compare ad argomento della sommatoria nella (VII.10.1), non

contribuiscono i bit codificati di lP uguali a quelli di 0 lP ν (cioè i bit nulli di lP ), in

quanto quale che sia il corrispondente bit della sequenza ricevuta { } ( )1ln

i i nc

α ν

α

+

= + esso


apporterebbe un eguale contributo alle distanze di { } ( )1ln

i i nc

α ν

α

+

= + da entrambi i cammini

lP e 0 lP ν .

Indichiamo adesso con ( )lw P il peso del cammino lP e soffermiamoci sul sotto-

insieme S di indici cui corrispondono i ( )lw P bit 1 di lP . Osserviamo che se ( )lw P è

dispari il decodificatore sceglierà il cammino lP ogniqualvolta la distanza tra { }i i Sc∈

e

( ){ }lii S

c∈

è minore di ( )

12lw P

t⎢ ⎥⎢ ⎥= +⎢ ⎥⎢ ⎥⎣ ⎦

. La probabilità che ciò accada, sapendo che è

stata inviata la sequenza nulla è data da:

{ } ( ) { } { }( ){ } { }( ) { } { }( )( ) ( ) ( )

( )

1ˆPr | 0

Pr , 0 | 0

1

l

ll

ni l ii n

H i ii S i Sw P

w Pl

t

c P c

d c t c

w Pp p

α ν

α

ξξ

ξ ξ

+

= +

∈ ∈

−

=

= =

= ≥ =⎛ ⎞⎟⎜ ⎟⎜= −⎟⎜ ⎟⎟⎜⎝ ⎠

∑

(VII.10.2)

Se la distanza tra lP e 0 lP ν è pari esisteranno

( )( )2

l

l

w P

w P

⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠ possibili sequenze ricevute tali che

{ }i i Sc∈

avrà eguale distanza da { }0i S∈

e da ( ){ }lii S

c∈

. In tale eventualità il

decodificatore sceglierebbe in modo puramente casuale tra lP e 0 lP ν . La probabilità che

venga scelto il cammino lP sarà in questo caso data da:

{ } ( ) { } { }

{ } { }( ) ( ) { } { }

{ } { }( ) { } { }( )( )( ) ( )

( ) ( ) ( ) ( )( )

1

2

ˆPr | 0

1Pr , 0 | 0

2 2

Pr , 0 | 0

11 1

22

l

l ll

n

i l ii n

l

H i ii S i S

H i ii S i S

w P w Pl w Pl

lt

c P c

w Pd c c

d c t c

w Pw P

p p p pw P

α ν

α

ξξ

ξ ξ

+

= +

∈ ∈

∈ ∈

−

=

⎛ ⎞⎟⎜ = = =⎟⎜ ⎟⎜⎝ ⎠⎛ ⎞⎟⎜ ⎟⎜ ⎟= = +⎜ ⎟⎜ ⎟⎜ ⎟⎜⎝ ⎠

+ ≥ =

⎛ ⎞⎟⎜ ⎛ ⎞⎟⎜ ⎟⎟ ⎜⎜ ⎡ ⎤ ⎟⎟ ⎜= − + −⎜ ⎟⎟ ⎜⎢ ⎥⎜ ⎟⎟ ⎣ ⎦ ⎜ ⎟⎜ ⎜⎟ ⎝ ⎠⎟⎜ ⎟⎜⎝ ⎠∑

(VII.10.3)

62 Capitolo VII

dove p indica la probabilità di crossover del BSC con cui può essere schematizzata

la parte inclusa nel poligono tratteggiato in rosso del sistema di trasmissione mostrato in

Fig. VII.6

Esempio VII.2 La probabilità di crossover del BSC con cui puo essere schematizzata la parte inclusa nel poligono

tratteggiato in rosso del sistema di trasmissione mostrato in Fig. VII.6, assumendo che al bit codificato

competa un’energia 1s b bk

E E REn

= = = e che il rumore gaussiano abbia una densità spettrale di

potenza monolatera 0 2N η= , sarà espressa dalla probabilità che il campione in uscita al filtro adattato per effetto del rumore sia minore di zero, malgrado il bit codificato fosse un uno, o indifferentemente, dalla probabilità che il succitato campione, per lo stesso motivo, sia maggiore di zero malgrado il bit codificato inviato fosse uno zero. Nel caso in cui il bit trasmesso sia un uno avremo:

( )

( ) ( )

2 1 21

10

2 2

1 1

1 1Pr( 0 | 1)

2 2

1

xx

i ip r c e dx e dx

Q Q

ηη

ν νη

η η

πη π

− =−−

−∞ −∞= < = = =

= − − =

∫ ∫

Tenuto conto delle ipotesi fatte sull’energia del bit codificato, se vogliamo fare comparire nella precedente il rapporto tra l’energia associata al bit informativo e la densità spettrale monolatera di rumore possiamo scrivere:

0 0 0

21 1

2s b bE RE RE

N N Nη η= = ⇒ =

Da cui:

0

2 bREp QN

⎛ ⎞⎟⎜ ⎟⎜= ⎟⎜ ⎟⎜ ⎟⎜⎝ ⎠

Osserviamo che la (VII.10.2) e la (VII.10.3) dipendono solo dal peso di lP non dal

numero di rami da cui esso è costituito. In altri termini, tutti i cammini di uguale peso

avranno la stessa probabilità di essere erroneamente scelti dal decodificatore indipenden-

temente dalla loro lunghezza. Sulla base di quest’ultima osservazione possiamo compat-

tare in un'unica espressione la (VII.10.2) e la(VII.10.3), indicando semplicemente con eδ

un evento d’errore di peso δ , ottenendo:

{ } { }( )

( ) ( ) ( ) { }( )2

12

Pr | 0

1 11 1 Pr | 0

42

ie c

p p p p e

δ

δ δδδ ξξ

δδξ

δ δδ ξ

−

⎢ ⎥⎢ ⎥= +⎢ ⎥⎣ ⎦

=⎛ ⎞⎟⎜ ⎛ ⎞− + ⎟⎜ ⎟⎜⎟⎜ ⎡ ⎤ ⎟⎢ ⎥ ⎜= − + −⎟ ⎟⎜ ⎟ ⎜⎣ ⎦ ⎟⎜ ⎢ ⎥ ⎟⎟ ⎜⎝ ⎠⎜ ⎟⎟⎜ ⎢ ⎥⎝ ⎠⎣ ⎦

∑ (VII.10.4)


La precedente ci suggerisce di riordinare la (VII.10.1) accorpando tutti gli eventi

d’errore di ugual peso. Il numero di tali eventi può essere dedotto dalla ( )T D del codi-

ce. Tenendo conto della (VII.9.8) possiamo quindi scrivere:

{ } ( ) { } { }( )( ) { }( )

0 ,11

Pr | 0

Pr | 0

l

nodo ll

f

ne i P P ii n

l

d

P c R x

w e

ν

α ν

α

δδ

δ

∞+

= +=∞

=

≤ ∈ =

=

∑

∑ (VII.10.5)

Nel caso di decodifica soft, basandoci sullo schema di Fig. VII.6 e assumendo che

l’impulso di segnalazione abbia energia sE , potremo scrivere:

{ } ( ) ( )( ){ } ( )

{ } ( ) { } ( ){ } { }

( )( )( )

( )

1 1

11 1

2

1

1

, 2 1Pr

, | 0

2

2

ll

nodo ll

l

nn lE i s ii n n

e nnlE i s ii n n

nl

s is li n

l

d r E cP

d r E c

E cE w P

Q Q

α να ν

α αα να ν

α α

α ν

α

ηη

++∞

= + +++=

= + +

+

∞= +

=

⎛ ⎛ ⎞ ⎞⎟ ⎟⎜ ⎜ ⎟ ⎟−⎜ ⎜ ⎟ ⎟⎜ ⎜ ⎟⎜ ⎟⎝ ⎠⎜ ⎟≤ ⎜ ⎟⎜ ⎟⎛ ⎞⎜ ⎟⎟⎜ ⎟≤ − =⎜ ⎟⎜ ⎟⎜ ⎟ ⎟⎜⎝ ⎝ ⎠ ⎠⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟ ⎛⎜ ⎟⎜ ⎜⎟⎜ ⎟= =⎜ ⎟⎟⎜ ⎟⎜ ⎝⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠

∑

∑∑

1l

∞

=

⎞⎟⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎠∑

(VII.10.6)

che può essere anche riformulata in termini dell’energia per bit informativo, ponendo

cioè s bE RE= , e della densità spettrale di potenza monolatera 0 2N η= ottenendo:

( )1 0

2nodo

be l

l

EP Q Rw P

N

∞

=

⎛ ⎞⎟⎜ ⎟⎜≤ ⎟⎜ ⎟⎟⎜⎝ ⎠∑ (VII.10.7)

Osserviamo che anche gli argomenti delle ( )Q ⋅ a secondo membro della preceden-

te non dipendono dalla lunghezza lν di lP , ma solo dal suo peso. La sommatoria a se-

condo membro della precedente può quindi, anche in questo caso, essere riordinata ac-

corpando tutti gli eventi di errore di egual peso, ottenendo:

( )0

2nodo

f

be

d

REP w Q

Nδ

δδ

∞

=

⎛ ⎞⎟⎜ ⎟⎜≤ ⎟⎜ ⎟⎟⎜⎝ ⎠∑ (VII.10.8)

64 Capitolo VII

La precedente, a fronte di un’ulteriore maggiorazione può assumere una forma più

semplice da calcolare. Ricordando infatti che, per argomento non negativo, vale la disu-

guaglianza ( )2

212

x

Q x e−

≤ possiamo ancora scrivere:

{ }( ) 0

0

2 1Pr | 0

2

bRE

NbREe Q eN

δ

δδ −⎛ ⎞⎛ ⎞ ⎟⎜⎟ ⎟⎜ ⎜⎟ ⎟⎜= ≤ ⎜⎟ ⎟⎜ ⎜⎟ ⎟⎟⎜ ⎜ ⎟⎝ ⎠ ⎟⎜⎝ ⎠

(VII.10.9)

per mezzo della quale otteniamo:

( ) ( ) ( )0

00

2 1 1

2 2

b

REbnodo N

f f

RE

Nbe

d d D e

REP w Q w e T D

N

δ

δ δ

δδ δ

−

∞ ∞ −

= = =

⎛ ⎞⎟⎜ ⎟⎜≤ < =⎟⎜ ⎟⎜ ⎟⎜⎝ ⎠∑ ∑ (VII.10.10)

Anche nel caso della decodifica Hard possiamo maggiorare ulteriormente la nodoeP

ricordando la maggiorazione di Bhattacharyya che ci permette di scrivere

{ }( ) ( ) 2Pr | 0 4 1e p p Bδ

δδ

⎡ ⎤≤ −⎣ ⎦ (VII.10.11)

Quest’ultima ci permette, partendo dalla (VII.10.5) di scrivere:

( ) { }( ) ( ) ( ) ( )2Pr | 0 4 1nodo

f f

e D Bd d

P w e w p p T Dδ

δδ δ

δ δ∞ ∞

== =

⎡ ⎤≤ ≤ − =⎣ ⎦∑ ∑ (VII.10.12)

La (VII.10.10) e la (VII.10.12) possono essere calcolate facilmente, disponendo

della ( )T D del codice, la (VII.10.5) e la (VII.10.8) sono dei bound più stretti, ma pos-

sono essere calcolati solo in modo approssimato, entrambe tuttavia sono in genere domi-

nate dal primo addendo della sommatoria che corrisponde alla distanza libera del codice.

Il primo addendo di ciascuna di esse rappresenta in genere già da solo una maggiorazio-

ne della probabilità d’errore di nodo.


VII.12 Bound sulla probabilità d’errore sul bit informativo. Al fine di calcolare la probabilità d’errore sul bit d’informazione consideriamo una

porzione di sequenza decodificata { }icν⎡ ⎤⎣ ⎦ costituita da nN bit codificati con 1N >>

(l’apice ν ha la sola funzione di etichetta). Nella corrispondente porzione di sequenza


decodificata { }ixν⎡ ⎤⎣ ⎦ costituita da kN bit saranno presenti un certo numero di bit errati.

Osserviamo che la presenza di un bit errato è possibile solo se nella { }icν⎡ ⎤⎣ ⎦ si è

manifestato un errore di nodo. Sappiamo anche che ad ogni evento d’errore di nodo

corrisponde un ben preciso numero di bit d’informazione errati.

Il numero totale di bit informativi errati potrà anche essere espresso accorpando

tutti gli eventi d’errore di nodo caratterizzati da uno stesso numero di bit informativi

errati che in essa si sono presentati. La frequenza relativa d’errore sul bit ( ),Nf eν⎡ ⎤⎣ ⎦ ,

associata alla sequenza ν -esima, sarà quindi espressa dal rapporto tra il numero di bit

informativi errati e il numero totale dei bit informativi inviati della sequenza in esame.

Detto quindi , ( )N jνμ⎡ ⎤⎣ ⎦ il numero di eventi d’errore che si sono manifestati nella

sequenza decodificata ν -esima e che contengono esattamente j bit informativi errati,

possiamo scrivere:

( )max ,

,

1

( )j NN

j

j jf e

kN

νν μ

⎡ ⎤⎣ ⎦⎡ ⎤⎣ ⎦

=

= ∑ (VII.11.1)

La probabilità d’errore sul bit informativo si può ottenere mediando su un numero

idealmente infinito di repliche dello stesso esperimento come segue:

( )( ),

1

lim

lim

N

N

b

f e

P e

γ

γ

Γ⎡ ⎤⎣ ⎦

→∞=

Γ→∞=

Γ

∑ (VII.11.2)

sostituendo la (VII.11.1) nella precedente abbiamo:

( )( )

max ,,

1 1 1

,

1

1

( )lim lim

1lim lim

( )lim

1lim

j NN

N N jb

N

N

j

j jf e

NP e

kj

Nj

k

γγ

γ γ

γ

γ

μ

μ

⎡ ⎤Γ Γ ⎣ ⎦⎡ ⎤⎣ ⎦→∞ →∞= = =

Γ→∞ Γ→∞⎡ ⎤Γ ⎣ ⎦

∞ →∞=

Γ→∞=

= =Γ Γ

=Γ

∑ ∑ ∑

∑∑

(VII.11.3)

nella quale, prima di invertire l’ordine delle sommatorie, si è tenuto conto del fatto

che al crescere della lunghezza della sequenza si possono manifestare eventi d’errore con

66 Capitolo VII

un numero arbitrariamente grande di bit informativi errati. Si constata facilmente che il

limite ad ultimo membro della (VII.11.3) esprime la probabilità che si manifesti un

qualsiasi evento d’errore di nodo che contenga esattamente j bit informativi errati.

Indicando con Iι l’insieme di tutti gli eventi d’errore con ι bit informativi errati

possiamo scrivere:

( )

,

1

( )lim

| lim

N

N

nodo

NP e I

γ

γι

μ ι⎡ ⎤Γ ⎣ ⎦

→∞=

Γ→∞=

Γ

∑ (VII.11.4)

Il calcolo della precedente non è praticabile, essa può tuttavia essere facilmente

maggiorata applicando, come nel paragrafo precedente, l’union bound.

( ) { }( )| Pr | 0nodoe I

P e I eδ ι

ι δ∈

≤ ∑ (VII.11.5)

A partire dalla (VII.11.3) possiamo ancora scrivere:

( ) ( ) { }( )1 1

1 1| Pr | 0b nodo

e I

P e P e I ek k

δ ι

ι δι ι

ι ι∞ ∞

= = ∈

= ≤∑ ∑ ∑ (VII.11.6)

Ricordando la (VII.9.7) che per comodità riscriviamo:

( ) ( )2 1

, , , ,fd

T J L D w J L Dι λ δ

δ λ ι

δ λ ι∞ ∞ ∞

= = =

= ∑ ∑∑ (VII.11.7)

e tenuto conto che, indipendentemente dal tipo di decodificatore, la probabilità che si

presenti un dato errore di nodo dipende solo dal suo peso possiamo ancora scrivere:

( ) { }( ) ( ) { }( )

( ) { }( )

1 1 2

1

1 1Pr | 0 , , Pr | 0

1, Pr | 0

f

f

be I d

d

P e e w j ek k

w j ek

δ ι

δ δι ι δ λ

δι δ

ι ι δ λ

ι δ

∞ ∞ ∞ ∞

= ∈ = = =∞ ∞

= =

≤ =

=

∑ ∑ ∑ ∑ ∑

∑ ∑(VII.11.8)

La precedente può essere ulteriormente maggiorata applicando la (VII.10.11) nel

caso di decodifica hard o la (VII.10.9) in quella soft ottenendo rispettivamente:

( ) ( ) ( ) ( )2

1 1

1 1, 4 1 ,

f f

bd d

P e w j p p w j Bk k

δδ

ι δ ι δ

ι δ ι δ∞ ∞ ∞ ∞

= = = =

⎡ ⎤≤ − =⎣ ⎦∑ ∑ ∑ ∑ (VII.11.9)


( ) ( ) 0

1

1,

2

b

f

RE

Nb

d

P e w j ek

δ

ι δ

ι δ∞ ∞

= =

⎛ ⎞⎟⎜ ⎟⎜ ⎟≤ ⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎝ ⎠∑ ∑ (VII.11.10)

Osserviamo adesso che risulta:

( ) ( )

( ) ( )

1

2 11, 1 1, 1

1 2 1

, ,, ,

, , ,

f

f f

dL J L J

d d

T J L Dw J L D

J

w D w D

ι λ δ

δ λ ι

δ δ

ι δ λ ι δ

ι δ λ ι

ι δ λ ι ι δ ι

∞ ∞ ∞−

= = == = = =∞ ∞ ∞ ∞ ∞

= = = = =

∂=

∂

= =

∑ ∑∑

∑ ∑ ∑ ∑ ∑ (VII.11.11)

la quale ci permette di riscrivere la (VII.11.9) e la (VII.11.10) rispettivamente nella

forma più compatta:

( ) ( )1, 1,

, ,1b

L J D B

T J L DP e

k J= = =

∂≤

∂ (VII.11.12)

e

( ) ( )01, 1,

, ,12

REbN

bL J D e

T J L DP e

k J= = =

∂≤

∂ (VII.11.13)


Capitolo VIII

Anelli di polinomi

VIII.1 Premessa Abbiamo già fornito la definizione di campo e abbiamo anche operato nel campo

B costituito da due soli elementi. Si possono costruire anche campi finiti (Campi di

Galois GF Galois Field) con un numero d’elementi p che sia un primo o una potenza di

un primo. Nel caso in cui il campo abbia un numero primo p d’elementi, l’addizione e

la moltiplicazione tra elementi del campo si possono effettuare in modo tradizionale

avendo cura di ridurre il risultato modulo p . Nella Tabella VIII.1 a titolo d’esempio so-

no riportati i risultati di tutte le possibili somme e prodotti tra coppie d’elementi di 7GF ,

il campo di Galois con sette elementi.

VIII.2 L’anello polinomi a coefficienti in F Consideriamo un campo F e un’indeterminata x , indichiamo con x⎡ ⎤⎣ ⎦F l’insieme

di tutti i possibili polinomi (cioè di qualunque grado) nella variabile x con coefficienti

appartenenti ad F , il generico elemento di x⎡ ⎤⎣ ⎦F sarà cioè del tipo:

7GF

⊕ 0 1 2 3 4 5 6 ⊗ 0 1 2 3 4 5 6

0 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0

1 1 2 3 4 5 6 0 1 0 1 2 3 4 5 6

2 2 3 4 5 6 0 1 2 0 2 4 6 1 3 5

3 3 4 5 6 0 1 2 3 0 3 6 2 5 1 4

4 4 5 6 0 1 2 3 4 0 4 1 5 2 6 3

5 5 6 0 1 2 3 4 5 0 5 3 1 6 4 2

6 6 0 1 2 3 4 5 6 0 6 5 4 3 2 1

Tabella VIII.1 - Campo di Galois di 7 elementi

70 Capitolo VIII

( ) ( ) 20 1 2

n nna x a a x a x a x= + + + +… (VIII.1.1)

dove n è un intero non negativo qualsiasi ed na ≠ o , essendo o l’elemento neu-

tro rispetto all’addizione in F .

Conveniamo inoltre:

- di utilizzare per le leggi di composizione del campo i simboli utilizzati per il campo

reale

- di indicare con ( ) ( )a x−∞ il polinomio identicamente nullo, cioè coincidente con o

- di omettere l’apice tra parentesi per indicare un polinomio di grado generico;

- che dato ( ) ( )na x , ia ≡ o per i n> .

Siano ( ) ( ) ( ) ( ),n ma x b x due elementi di x⎡ ⎤⎣ ⎦F e α un elemento di F , poniamo:

( ) ( ) ( ) ( ) ( )20 1 2

n nna a a x a x a xα α α α α= + + + +… (VIII.1.2)

( ) ( ) ( ) ( ) ( ) ( )

{ }max ,

n m l

i i i

a x b x c x

c a b l n m+

+ == ⇒ ≤

(VIII.1.3)

e

( ) ( ) ( ) ( ) ( ) ( )

0

0

n m m n

k

k m nk i k ii

a x b x c x

c a b

+

≤ ≤ +−=

=

= ∑F (VIII.1.4)

Nella precedente ∑F è utilizzato per ricordare che la sommatoria si deve ef-

fettuare secondo le regole di F , come del resto anche il prodotto al suo interno.

In sostanza abbiamo appena introdotto in x⎡ ⎤⎣ ⎦F l’addizione e la moltiplicazione.

Rispetto all’addizione è facile verificare che x⎡ ⎤⎣ ⎦F è un gruppo commutativo,

inoltre la moltiplicazione tra polinomi in F è commutativa e distributiva rispetto

all’addizione. x⎡ ⎤⎣ ⎦F è pertanto un anello commutativo, con identità, che coincide con

l’identità di F , che indicheremo con e .

Anelli di Polinomi 71

Osserviamo che il prodotto tra polinomi non nulli è un polinomio non nullo. Si

ottiene il polinomio nullo se e solo se uno almeno dei due moltiplicandi è il polinomio

nullo. Vale cioè anche la legge di annullamento del prodotto.

Quanto detto comporta tra l'altro che i polinomi { }2 3, , , , mx x x x… …e sono

linearmente indipendenti su x⎡ ⎤⎣ ⎦F .


VIII.3 Spazi di polinomi

Consideriamo adesso il sottoinsieme ( )1nx

− ⎡ ⎤⎣ ⎦F di x⎡ ⎤⎣ ⎦F costituito da tutti i

polinomi di grado minore di n . La somma di due elementi di ( )1nx

− ⎡ ⎤⎣ ⎦F è ancora un

elemento di ( )1nx

− ⎡ ⎤⎣ ⎦F . Inoltre moltiplicando un qualunque elemento di ( )1nx

− ⎡ ⎤⎣ ⎦F per

un elemento di F , che coincide con ( )0x⎡ ⎤⎣ ⎦F , otteniamo ancora un elemento di

( )1nx

− ⎡ ⎤⎣ ⎦F .

( )1nx

− ⎡ ⎤⎣ ⎦F è quindi uno spazio vettoriale su F di dimensione n in quanto è

evidentemente generabile tramite i suoi elementi linearmente indipendenti

{ }2 1, , , nx x x −…e .

Ci si convince facilmente che detto spazio vettoriale è isomorfo allo spazio nF

costituito da tutte le n -uple ordinate di elementi di F , basta infatti associare al polino-

mio ( ) ( ) ( )1nka x x− ⎡ ⎤∈ ⎣ ⎦F , l’elemento [ ]0 1 1, , , n

na a a −= ∈a … F se 1k n= − , ovvero

l’elemento 0 1, , , ,ka a a⎡ ⎤⎣ ⎦… …o o se 1k n< −


Capitolo IX

Codici polinomiali

Dati due interi 2n ≥ e k n< , scegliamo un polinomio ( ) ( )n kg x x− ⎡ ⎤∈ ⎣ ⎦F che

chiameremo polinomio generatore, tramite ( ) ( )n kg x− possiamo individuare il sottoin-

sieme ( )1nx x

−⎡ ⎤ ⎡ ⎤⊆⎣ ⎦ ⎣ ⎦F che contiene i polinomi che si ottengono da tutti i possibili

prodotti tra ( ) ( )n kg x

− e i polinomi ( ) ( )1na x x

− ⎡ ⎤∈ ⎣ ⎦F .

Consideriamo adesso due elementi ( )c x e ( )'c x appartenenti a x⎡ ⎤⎣ ⎦ , quindi

esprimibili rispettivamente nella forma:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ), ' 'n k n kc x a x g x c x a x g x− −= = (IX.1.1)

Comunque scelti ,α β ∈ F risulta:

( ) ( ) ( ) ( )( ) ( ) ( )' ' n kc x c x a x a x g xα β α β −+ = + ∈ (IX.1.2)

La precedente ci mostra che ( )x è un sottospazio di ( )1nx

− ⎡ ⎤⎣ ⎦F , quindi ne è

anche un sottogruppo.

Il corrispondente sottoinsieme di nF è quindi un codice di gruppo.

Abbiamo già detto (vedi par. II.2) che la distanza di Hamming tra parole di nF è

una metrica, la distanza minima di è data dalla sua parola di peso minimo cioè dalla

parola che ha il minor numero di lettere diverse da o , che non è necessariamente unica.

Ci si convince anche facilmente del fatto che se s’intende impiegare un codice

polinomiale per la rilevazione d’errore è sufficiente dividere il polinomio corrispondente

alla parola ricevuta per il polinomio generatore, e verificare che il resto di tale divisione

sia il polinomio nullo, per essere certi che la parola ricevuta appartiene al codice.

74 Capitolo IX

Consideriamo adesso il caso dei codici polinomiali sul campo B essi sono

certamente codici binari a blocchi, nel senso che ammettono una matrice generatrice che

si può facilmente costruire a partire da ( ) ( )n kg x− . Come righe di tale matrice si

possono scegliere infatti le stringhe dei coefficienti dei polinomi di codice ottenuti

moltiplicando il polinomio generatore per i polinomi { }2 1, , , kx x x −…e . Viceversa non

è vero in generale che i codici lineari a blocchi siano polinomiali, al fine di verificare se

un codice lineare a blocchi è polinomiale è sufficiente verificare che tutti i polinomi

associati alle righe della matrice generatrice ammettano un fattore comune di grado

n k− .


Capitolo X

Ideali di un anello di polinomi

X.1 Premessa Torniamo adesso a parlare di campi finiti, abbiamo visto come si possono costruire

campi finiti con un numero primo d’elementi; è anche possibile, come mostreremo più

avanti, definire campi che hanno un numero di elementi che è una potenza (ad esponente

intero) di un numero primo. Il generico elemento di un tale campo si può quindi mettere

in corrispondenza biunivoca con l’insieme ( )( )1n

px

− ⎡ ⎤⎣ ⎦GF , che ha la stessa cardinalità.

Sorge quindi spontaneo indagare sulla possibilità di individuare in ( )1nx

− ⎡ ⎤⎣ ⎦F due

opportune leggi di composizione tra suoi elementi che consentano di pensare a

( )1nx

− ⎡ ⎤⎣ ⎦F come ad un campo di np elementi. Sarebbe a questo punto possibile definire

degli isomorfismi tra ( )( )1n

px

− ⎡ ⎤⎣ ⎦GF e ( )npGF . Parliamo di isomorfismi perché

potrebbero esistere più leggi di composizione interna che soddisfano le condizioni

necessarie per interpretare ( )1n−F come campo.

Abbiamo già visto che ( )1nx

− ⎡ ⎤⎣ ⎦F è un gruppo commutativo rispetto all’addizione

tra polinomi, purtroppo l’ordinaria moltiplicazione tra polinomi non può andar bene, non

foss’altro perché ( )1nx

− ⎡ ⎤⎣ ⎦F non è chiuso rispetto ad essa.

È quindi necessario ricercare una legge di composizione interna per ( )1nx

− ⎡ ⎤⎣ ⎦F

che abbia tutte le proprietà di cui deve godere la moltiplicazione tra elementi di un

campo. A tal fine è necessaria una piccola digressione di carattere generale.


76 Capitolo X

X.2 Ideali di un anello con identità. Consideriamo un anello commutativo con identità diciamo che un suo

sottogruppo è un ideale se:

i r ⊗∈ ∧ ∈ ⇒ ∈ (X.2.1)

Qualora l’anello non fosse commutativo dovremmo distinguere tra ideale sinistro e

ideale destro, che potrebbero anche coincidere, nel qual caso si parlerebbe di ideale

bilaterale.

Abbiamo detto che un ideale è un sottogruppo di , quindi definisce un gruppo

quoziente , i cui elementi sono l’ideale stesso, che ne costituisce l’elemento neutro,

e tutti i suoi laterali in , che indicheremo con { }r ⊕ . Con questa notazione risulta:

{ } { } ( ){ }{ } { } ( ){ }

;r r r r

r r r r

⊕ ⊕ ⊕ ⊕⊕

⊕ ⊕ ⊕⊗ ⊗

′ ′′ ′ ′′=′ ′′ ′ ′′=

(X.2.2)

Osserviamo che le precedenti sono indipendenti dalla scelta dei rappresentanti di

laterale. Si può anche verificare che è come un anello commutativo con identità.

Detto anello quoziente di rispetto a . Dalla seconda delle (X.2.2) si deduce

facilmente che l’identità moltiplicativa è il laterale che si può indicare con { }⊕e ,

cioè quello che contiene l’identità e di

Osserviamo che comunque scelto un elemento i di , l’insieme

{ }|i r r i⊗= ∈ è un ideale, infatti ( ) ( ) ( )i r i r i r r⊗ ⊕ ⊗ ⊗ ⊕′ ′= ∈ ,

inoltre indicando con r− , l’opposto di r , ( )i r⊗ − ∈ e risulta

( ) ( ) ( )( )i r i r i r r⊗ ⊕ ⊗ ⊗ ⊕⎡ ⎤− = − =⎣ ⎦ o , pertanto è un sottogruppo di . Ogni

ideale generato da un elemento di è detto ideale principale.

Vale il seguente teorema:

Teorema X.1

Tutti gli ideali dell’anello x⎡ ⎤⎣ ⎦F dei polinomi su un campo F sono principali.

Dimostrazione:

Ideali di un Anello di Polinomi 77

Osserviamo innanzitutto che ( ) ( ) { }a x−∞ ≡ o è un ideale principale per

l’anello commutativo con identità x⎡ ⎤⎣ ⎦F . Consideriamo adesso un ideale di x⎡ ⎤⎣ ⎦F di-

verso da ( ) ( )a x−∞ , in esso scegliamo un elemento ( ) ( )na x ≠ o di grado minimo.

Comunque scelto un polinomio ( ) ( )mb x ∈ potremo scrivere:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )m m n n kb x q x a x r x−= + (X.2.3)

dove se k ≠ −∞ (cioè ( ) ( )na x non è un divisore di ( ) ( )mb x ) risulterà

0 1k n≤ ≤ − , ma in questo caso potremmo scrivere:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )k m m n nr x b x q x a x−= − (X.2.4)

che è un assurdo in quanto ( ) ( )kr x deve appartenere ad , essendo esprimibile com-

ponendo elementi di quest’ultimo, ma deve avere anche grado n< che per ipotesi è il

grado minimo dei polinomi non nulli contenuti in . Deve pertanto essere k = −∞ , o,

che è lo stesso, ( ) ( ) ( ) ( )kr x a x−∞= = o , pertanto ogni ideale di x⎡ ⎤⎣ ⎦F è principale.

***********

Ci si convince facilmente che comunque scelto |α α∈ ≠F o , anche il polinomio

( ) ( )nh xα ⊗ genera lo stesso ideale. Ovviamente sarà sempre possibile individuare tra i

generatori di un ideale x⎡ ⎤⎣ ⎦F un solo polinomio monico cioè con il coefficiente del ter-

mine di massimo grado pari ad e .


Teorema X.2

Dati due ideali di x⎡ ⎤⎣ ⎦F , siano ( )1 1h x= ed ( )2 2h x= , risulta 1 2⊆ se e

solo se ( )1h x ha ( )2h x tra i suoi fattori.

***********

78 Capitolo X

Dato un ideale ( ) ( )nh x ed un polinomio ( ) ( )kg x , sappiamo che esistono

( ) ( )mq x e ( ) ( )jr x tali che si può scrivere :

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ } { } ,

| , 0 1 ,

,k m n j

m k nj n

m n k k n

g x q x h x r x

ν ν ν

+

⎧⎪ =−∞ <⎪⎪∈ −∞ ∪ ∈ ≤ ≤ − ⎨⎪ = − ≥⎪⎪⎩

= (X.2.5)

che ci permette di affermare che ( ) ( )kg x ed ( ) ( )jr x appartengono allo stesso laterale

di ( ) ( )nh x

( ) ( ) ( ) ( ){ } ( ) ( ) ( ) ( ){ }k n j ng x h x r x h x⊕ ⊕= (X.2.6)

ciascun laterale di un ideale contiene un unico polinomio di grado minimo, grado che, in

virtù della (X.2.5), deve essere minore di n . Per convincersene è sufficiente ricordare

che due elementi di un gruppo appartengono allo stesso laterale se e solo se la loro

differenza appartiene al sottogruppo, ma la differenza tra due polinomi distinti di grado

minore n non potrà appartenere all’ideale che essendo principale contiene solo polinomi

di grado maggiore od uguale ad n , fatta eccezione per il polinomio nullo, che peraltro è

l’unico polinomio di grado minimo contenuto nell’ideale pensato come laterale di se

stesso.

Esiste quindi un isomorfismo “naturale” tra l’anello ( ) ( )n

x

h x

⎡ ⎤⎣ ⎦F e l’insieme

( )1nx

− ⎡ ⎤⎣ ⎦F dei polinomi a coefficienti in F di grado minore di n . si può quindi pensare

a ( )1nx

− ⎡ ⎤⎣ ⎦F come ad un anello commutativo con identità assumendo come risultato

della moltiplicazione tra due polinomi di ( )1nx

− ⎡ ⎤⎣ ⎦F il resto della divisione tra l’usuale

prodotto dei due polinomi e ( ) ( )nh x .


Capitolo XI

Codici Ciclici

XI.1 Rappresentazione polinomiale di un codice ciclico.

Definizione XI.1 Un codice lineare a blocchi n

n,k ⊆ F si dice ciclico se e solo se comunque scelta una

sua parola di codice

0 1 2 2 1 1 0 1 2 2, , , , , , , ,n n n,k n n n,kc c c c c c c c c c− − − −⎡ ⎤ ⎡ ⎤′= ∈ ⇒ = ∈⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦c c… … (XI.1.1)

In quel che segue mostreremo che i codici ciclici sono polinomiali. Dovremo in

altri termini mostrare che se un codice è ciclico allora la sua rappresentazione

polinomiale ammette un polinomio generatore.

Ad ogni parola di codice possiamo associare un polinomio appartenente a

( )1nx

− ⎡ ⎤⎣ ⎦F come segue:

( ) 2 10 1 2 2 1 0 1 2 1, , , , n

n n nc c c c c c x c c x c x c x −− − −

⎡ ⎤= → = + + +⎢ ⎥⎣ ⎦c … … (XI.1.2)

denoteremo con ( )n,k x l’insieme dei polinomi associati alle parole di codice.

Risulta:

( ) 2 30 1 2 1

nnxc x c x c x c x c x−= + + +… (XI.1.3)

notiamo che per trasformare ( )xc x in ( )c x′ occorrerebbe sottrarre a ( )xc x il polino-

mio 1 1n

n nc x c− −− . Risulta:

( ) ( ) ( )2 3 21 1 0 1 2 2

n nn n nxc x c x c c x c x c x c x c x−− − − ′− − = + + + + =…e (XI.1.4)

ma 1nc − è il quoto della divisione tra ( )xc x e nx −e , dalla (XI.1.4) si deduce quindi

che ( )c x′ altro non è se non il resto della divisione appena citata.

80 Capitolo XI

In altri termini, l’operazione corrispondente alla rotazione ciclica di una parola in

nF equivale, nel linguaggio dei polinomi, a considerare il resto della divisione per

nx −e del prodotto tra il polinomio corrispondente alla parola ed x . In simboli:

( ) ( ) ( )mod nxc x xc x

−⎡ ⎤′ = ⎣ ⎦ e

(XI.1.5)


XI.2 L’anello n

x

x

⎡ ⎤⎢ ⎥⎣ ⎦−

Fe

Notiamo che l’insieme dei polinomi di codice ( )n,k x essendo costituito da

polinomi appartenenti a ( )1nx

− ⎡ ⎤⎣ ⎦F costituisce anche un sottoinsieme dei coset leader

(intesi come i polinomi di grado minimo) dei laterali di n

x

x

⎡ ⎤⎣ ⎦−e

F.

Osserviamo inoltre che:

• avendo supposto che il codice nn,k ⊆ F sia lineare, esso deve avere la

struttura di spazio vettoriale sul campo F , quindi la sua rapprentazione in

forma polinomiale ( )n,k x deve essere anche un sottospazio di ( )1n−F ;

• l’anello n

x

x

⎡ ⎤⎣ ⎦−e

F ha la struttura di spazio vettoriale sul campo F ;

• esiste un isomorfismo naturale tra ( )1n−F ed n

x

x

⎡ ⎤⎣ ⎦−e

F, quello che

associa ad ogni polinomio di ( )1nx

− ⎡ ⎤⎣ ⎦F l’unico laterale che lo contiene in

n

x

x

⎡ ⎤⎣ ⎦−e

F.

Codici Ciclici 81

Dalle considerazioni appena fatte discende facilmente che l’immagine secondo

l’isomorfismo sopra citato di ( )n,k x in n

x

x

⎡ ⎤⎣ ⎦−e

F è a sua volta un sottospazio

vettoriale, quindi anche un sottogruppo, ( )n,k x di n

x

x

⎡ ⎤⎣ ⎦−e

F, i cui elementi

sono i laterali di nx −e che contengono i polinomi di codice.

Osserviamo che la ciclicità e la linearità del codice implicano:

( ) ( ) ( )mod

( ) ( ) ; ,n

kn,k n,kx

c x x ax c x x a k−

⎡ ⎤∈ ⇒ ∈ ∀ ∈ ∈⎢ ⎥⎣ ⎦ eF (XI.2.1)

Dalla quale sempre in virtù della linearità di ( )n,k x discende anche facilmente:

( ) ( ) ( ) ( ) ( )mod

( ) ( ) ;nn,k n,kxc x x p x c x x p x x

−⎡ ⎤ ⎡ ⎤∈ ⇒ ∈ ∀ ∈⎣ ⎦ ⎣ ⎦e

F (XI.2.2)

Quest’ultima, sulla base dell’osservazione c), può essere rivisitata in termini di

laterali di nx −e :

{ } ( )( ) ( ){ } ( ){ }( ){ } { } ( )

( ){ }

mod

( )

( ) ( )

( ) ;

n

nn,k

n nx

n nn,k

nn

c x x x

p x c x x p x c x x

p x x c x x x

xp x x

x

⊕

⊕ ⊕−

⊗⊕ ⊕

⊕

− ∈

⎡ ⎤⇒ − ≡ −⎣ ⎦

⇒ − − ∈⎡ ⎤⎣ ⎦∀ − ∈

−

e

e

e e

e e

ee

F

(XI.2.3)

La precedente ci permette di affermare che se il codice è ciclico allora ( )n,k x è un

ideale dell’anello n

x

x

⎡ ⎤⎣ ⎦−e

F.

Viceversa consideriamo un ideale di n

x

x

⎡ ⎤⎣ ⎦−e

F comunque preso un suo

elemento, sia ( ){ }nc x x⊕ −e , il fatto che sia un ideale implica che

82 Capitolo XI

( ){ } ( ){ }( ) ( ){ } ( ) ( ) ( ){ }

( ){ } ( ){ }mod

;n

n n

n nx

n nn

c x x p x x

c x p x x c x p x x

xc x x p x x

x

⊗⊕ ⊕

⊕ ⊕−

⊕ ⊕

− −

⎡ ⎤= − = − ∈⎣ ⎦⎡ ⎤⎣ ⎦∀ − ∈ ∧ ∀ − ∈

−

e

e e

e e

e ee

F

(XI.2.4)

Ne discende che la controimmagine dell’isomorfismo di cui all’osservazione c) è un

codice ciclico.

Quanto finora esposto costituisce in pratica la dimostrazione del seguente teorema:

Teorema XI.1

Condizione necessaria e sufficiente affinché un codice sia ciclico è che ( )n,k x sia un

ideale di n

x

x

⎡ ⎤⎣ ⎦−e

F.

***********


XI.3 Polinomio generatore di un codice ciclico Ci convinciamo facilmente del fatto che il sottoinsieme di x⎡ ⎤⎣ ⎦F costituito dall’u-

nione di tutti i laterali di nx −e che appartengono ( )n,k x , in virtù della (XI.2.2),

è un ideale, ma tutti gli ideali di x⎡ ⎤⎣ ⎦F sono principali (vedi Teorema X.1), esiste cioè un

polinomio di grado minimo che li genera, tale polinomio apparterrà evidentemente a

( ) ( )1nn,k x x

− ⎡ ⎤⊆ ⎣ ⎦F in particolare potremmo scegliere in quest'ultimo l’unico polino-

mio monico di grado minimo, sia ( )g x . Rileviamo che il grado di ( )g x dovrà necessa-

riamente essere n k− per un codice n,k .

Abbiamo visto che ( ) ng x x⊇ −e , quindi, in virtù del Teorema X.2, ( )g x

deve essere un divisore di nx −e , ne discende che un codice ciclico n,k esiste se e so-

lo se nx −e pensato come polinomio a coefficienti nel campo F si può scomporre nel

prodotto tra due polinomi di cui uno di grado n k− .

Codici Ciclici 83


XI.4 Polinomio di parità di un codice ciclico

Nel paragrafo precedente abbiamo visto che se ( ) ( )n kg x− genera un codice ciclico

( )n,k x , allora deve esistere

( ) ( ) ( ) ( ) ( ) ( )|k n k k nh x g x h x x e− = − (XI.4.1)

D’altro canto nel precedente capitolo abbiamo visto che ogni parola di un codice

polinomiale può essere scritta nella forma:

( ) ( ) ( ) ( )n kc x a x g x−= (XI.4.2)

Dove ( )a x è un qualsiasi polinomio appartenente a ( )1kx

− ⎡ ⎤⎣ ⎦F . Risulta:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( )( ) ( )( ) ( )mod

0n

k n k k

n n

x

h x c x a x g x h x

a x x a x x

−

−

= =⎡ ⎤= − ⇒ − =⎢ ⎥⎣ ⎦ e

e e (XI.4.3)

Poiché la precedente è vera per tutti e soli i polinomi di codice, ne discende che

( ) ( )kh x , o un qualunque altro polinomio di x⎡ ⎤⎣ ⎦F che lo contenga come fattore senza

contenere nx −e , può essere utilizzato per effettuare il controllo di parità nel caso in

cui si intenda utilizzare il codice esclusivamente per la rivelazione dell’errore.

Osserviamo che il polinomio ( )( ) ( ) ( ) ( )kna x x h x c x− =e ha tutti i

coefficienti di grado maggiore di 1k − e minore di n nulli per costruzione. Questa

osservazione ci permette di scrivere le seguenti n k− equazioni che devono essere

soddisfatte dai coefficienti del polinomio ( ) ( ) ( )kh x c x :

0

0; 1k

i j ii

h c k j n−=

= ≤ ≤ −∑ (XI.4.4)

ciascuna delle equazioni appena scritte coinvolge 1k + simboli consecutivi della

parola di codice e può quindi essere utilizzata come controllo di parità qualora si intenda

utilizzare il codice per la correzione di errore. Le (XI.4.4) potrebbero anche essere

84 Capitolo XI

utilizzate per implementare un codificatore sistematico utilizzando un filtro FIR, a tal

fine osserviamo che nella prima delle (XI.4.4) possiamo scegliere arbitrariamente

0 1 1, kc c c −… , e calcolare kc , quindi utilizzare nella seconda 1 1,k kc c c−… per calcolare

1kc + e così via fino ad ottenere una parola di codice. In sostanza si risolvono

ricorsivamente equazioni del tipo

01

1k

i j i ji

h c h c k j n−=

= − ≤ ≤ −∑ (XI.4.5)

Nell’incognita jc tali equazioni ammettono certamente soluzione dal momento che

deve 0 0h ≠ se così non fosse, tra le radici di ( )h x vi sarebbe lo zero del campo che

non essendo una radice di nx −e non può esserlo per nessuno dei suoi fattori.

Esempio XI.1 Vogliamo implementare un codificatore basato sulle (XI.4.5) che emetta gli n simboli della parola di codice in sequenza. Osserviamo che il codificatore è sistematico, i k simboli informativi emessi dalla sorgente potranno quindi essere resi disponibili direttamente all’uscita del codificatore. Nello

stesso tempo, al fine di calcolare i simboli di parità essi dovranno essere temporaneamente memorizzati in uno stack di memoria che nel caso di codici binari si identifica di fatto con uno shift register. Osserviamo lo schema di Fig. XI.1, nel quale sono indicati in rosso i simboli presenti nelle celle di memoria, schematizzate come elementi di ritardo. Ci rendiamo conto che, non appena la sorgente emette il k -esimo simbolo informativo ( 1kc − ), all’uscita del moltiplicatore posto in serie al

sommatore sarà presente kc . Il passo successivo consisterà nel chiudere l’anello di reazione, spostando sulla posizione b il commutatore e mantenerlo in questa posizione per n k− periodi di clock per calcolare i restanti simboli di parità. Osserviamo che ( )h x può essere scelto in modo che risulti 0 1h = − , nel qual caso sarebbe possibile eliminare il moltiplicatore in uscita al sommatore; d’altra parte tale scelta comporta in genere la rinuncia ad un polinomio generatore monico. Nel caso in cui il codice sia binario, la sua struttura si semplifica ulteriormente in quanto si potrebbero abolire tutti i moltiplicatori limitandosi a connettere al sommatore solo le celle di memoria cui corrisponde un coefficiente non nullo del polinomio di parità. Notiamo anche che in questo caso le celle di memoria si ridurrebbero a dei Flip Flop. Per concludere osserviamo che il “cuore” di questo codificatore è sostanzialmente un filtro FIR.


Σ

sT

a

bsT sT

1h 3h2h kh1

0h−−

0c

1kc

2kc

− 3kc

− 1c

1kc

1kc −

kc

2 3 0k kc c c− −

Fig. XI.1 Codificatore sistematico basato sul polinomio di parità

Codici Ciclici 85

XI.5 Matrice generatrice di un codice ciclico Consideriamo un codice ciclico sul campo F la cui rappresentazione polinomiale

sia l’insieme ( )n,k x , abbiamo visto che esso deve ammettere un polinomio generatore

di grado n k− , sia

( ) ( ) 1n k n k

o n kg x g g x g x− −−= + +… (XI.5.1)

Sappiamo che, in virtù della ciclicità, anche i polinomi ( ) ( )( )mod 1n

n kj

xx g x−

−

⎡ ⎤⎢ ⎥⎣ ⎦

devono appartenere a ( )n,k x . Osserviamo che per i k polinomi ottenuti al variare di j

tra 0 e 1k − risulta

( ) ( )( )

( ) ( )mod n

n k n kj j

xx g x x g x− −

−

⎡ ⎤ =⎢ ⎥⎣ ⎦ e (XI.5.2)

Inoltre essi sono linearmente indipendenti, giacché tutti di grado diverso. Essi sono

anche in numero pari alla dimensione di ( )n,k x pensato come sottospazio di

( )1n x− ⎡ ⎤⎣ ⎦ , ne costituiscono quindi una base.

Quanto appena detto ci consente di scrivere una matrice generatrice del codice

nn,k ⊆ F che avrà evidentemente come righe le parole corrispondenti ai polinomi

appena individuati

1

1,

1

o n k

o n kk n

o n k

g g g

g g gG

g g g

−

−

−

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

… … …… …

… …… … … … … … … … …

o o oo o o oo o o o

(XI.5.3)

XI.6 Codici ciclici Sistematici La matrice generatrice individuata nel paragrafo precedente non è in forma

sistematica, vogliamo mostrare che è possibile individuarne una che lo è.

A tal fine dato un codice ciclico ( )n,k x generato da ( ) ( )n kg x− consideriamo

polinomi del tipo:

jx (XI.5.4)

86 Capitolo XI

Essi non sono certamente polinomi di codice in quanto tra le loro radici non com-

paiono certamente quelle di ( ) ( )n kg x− , tuttavia sottraendo da ciascuno di essi il resto

della divisione per ( )g x otteniamo un polinomio di codice possiamo cioè affermare

che:

( )( )

( )mod

j jn,kg x

x x x⎡ ⎤− ∈⎢ ⎥⎣ ⎦ (XI.5.5)

Ci rendiamo conto del fatto che se scriviamo i polinomi ottenuti tramite la (XI.5.5) in

corrispondenza a 1n k j n− ≤ ≤ − otteniamo k polinomi di codice che hanno il solo

coefficiente j -esimo pari a uno e tutti i restanti nulli nel range di valori di j in parola,

ciò in quanto il resto di una divisione per ( )g x è un polinomio che al più può avere

grado 1n k− − . Si costata anche immediatamente che i polinomi appena ottenuti sono

linearmente indipendenti, si possono quindi utilizzare le parole di codice ad essi

associate per costruire una matrice generatrice del codice che sarà del tipo:

, , ,k n k n k k kG P I−⎡ ⎤= ⎣ ⎦ (XI.5.6)

in grado quindi di generare un codice sistematico con la parte informativa “in coda”

anziché “in testa”.

Da quanto detto discende che il polinomio di codice associato al polinomio

informativo ( ) ( )1ka x x

− ⎡ ⎤∈ ⎣ ⎦F è dato da:

( ) ( ) ( ) ( )( )( )mod n kn k n k

g xc x a x x a x x −

− −⎡ ⎤= − ⎢ ⎥⎣ ⎦ (XI.5.7)

Prendiamo adesso in considerazione la matrice

, , ,k n k k k n kG I P −⎡ ⎤′ = ⎣ ⎦ (XI.5.8)

che si ottiene effettuando k rotazioni cicliche su ciascuna riga della ,k nG . Essa ha per

righe k parole di n,k linearmente indipendenti ed è quindi anch’essa una matrice

generatrice.

Esempio XI.2 Per costruire un codificatore basato sulla (XI.5.7) dobbiamo disporre di un sistema in grado di

calcolare il resto della divisione tra due polinomi.

Codici Ciclici 87

Supponiamo di disporre all’istante i - esimo del polinomio ( )ip x⎡ ⎤⎣ ⎦, e che tale polinomio

all’istante 1i + - esimo venga aggiornato, per effetto dell’emissione da parte di una sorgente di un simbolo 1ia ⎡ ⎤+⎣ ⎦

secondo la regola:

( ) ( )1 1i i ip x xp x a⎡ ⎤ ⎡ ⎤ ⎡ ⎤+ +⎣ ⎦ ⎣ ⎦ ⎣ ⎦= +

Indichiamo rispettivamente con ( )ir x⎡ ⎤⎣ ⎦ e ( )iq x⎡ ⎤⎣ ⎦

il resto e il quoto della divisione tra ( )ip x⎡ ⎤⎣ ⎦e

( )g x che supponiamo monico. Vogliamo calcolare ( )1ir x⎡ ⎤+⎣ ⎦. Risulta:

( ) ( )

( )( )( ) ( ) ( )

( )( )

( )( )( )

1 1 1mod mod

1 mod

i i i i ig x g x

i i g x

r x p x xq x g x xr x a

xr x a

⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤+ + +⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦

⎡ ⎤ ⎡ ⎤+⎣ ⎦ ⎣ ⎦

⎡ ⎤ ⎡ ⎤= = + +⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦⎡ ⎤= +⎢ ⎥⎣ ⎦

Ma ( ) 1i ixr x a⎡ ⎤ ⎡ ⎤+⎣ ⎦ ⎣ ⎦+ ha al più grado n k− possiamo quindi ulteriormente scrivere:

( ) ( ) ( ) ( )

( ) ( )( ) ( )( )1 1 1

11 1 0 0 1 1 2 1 1

i i i i n k

n ki i n k i i n k i n k i n k n k

r x a xr x r g x

a r g r r g x r r g x

⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤+ + − −⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦− −

⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤+ − − − − − − − − − −⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦

= + −

= − + − + −…

Possiamo quindi fa-cilmente tracciare lo schema di principio mostrato in Fig. XI.2.

Non appena tutti i coefficienti del dividen-do, a partire da quello di grado maggiore, saranno immessi nel sistema, sarà sufficiente aprire l’anello di reazione tramite il de-

viatore in uscita e nei successivi n k− passi si presenteranno in uscita i coefficienti del resto. Equation Section (Next)

XI.7 Duale di un codice ciclico Abbiamo mostrato che un codice ciclico ( )n,k x , ha come generatore un fattore

( ) ( )n kg x− del polinomio nx −e . Esiste quindi un ( ) ( )kh x tale che:

( ) ( ) ( ) ( )n k k ng x h x x− = −e (XI.6.1)

Abbiamo gia visto come ( ) ( )kh x possa essere utilizzato come polinomio di parità,

ma esso, in quanto fattore di nx −e è in grado di generare un codice ciclico

( )n,n k x⊥ − anch’esso contenuto in ( )1nx

− ⎡ ⎤⎣ ⎦F che viene chiamato (seppur impropria-

D

0g 1g

[ ] 1i n kr − −[ ]0ir [ ]1ir[ ]1ia +

[ ]1 0ir+ [ ]1 1i

r+

1n kg − −

[ ] 2i n kr

− − [ ]1 1i n kr + − −DD D

Fig. XI.2 Schema di principio di un sistema che calcola il resto della

divisione tra due polinomi

88 Capitolo XI

mente) duale di ( )n,k x , in quanto le parole di n,k non sono in genere ortogonali a

quelle di n,n k⊥ − .

Consideriamo due polinomi ( ) ( )n,kc x x∈ e ( ) ( )n,n kd x x⊥ −∈ . Risulta:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( )n k k nc x d x a x g x b x h x a x b x x−= = −e (XI.6.2)

Osserviamo che il polinomio ( ) ( )a x b x ha grado al più

( ) ( )1 1 2k n k n− + − − = − , ne consegue che il coefficiente del termine di grado

1n − di ( ) ( )c x d x deve essere nullo. Possiamo quindi scrivere:

1

10

0n

i n ii

c d−

− −=

=∑ (XI.6.3)

la precedente vale per ogni scelta di ( ) ( )n,kc x x∈ e ( ) ( )n,n kd x x⊥ −∈ . Essa ci

suggerisce come costruire il codice duale propriamente detto che si ottiene ribaltando le

parole di n,n k⊥ − .

Anche il codice duale propriamente detto è polinomiale il suo polinomio generatore

risulta essere:

( )1kx h x− (XI.6.4)

una sua matrice generatrice potrebbe essere:

2 1 0

2 1 0,

2 1 0

k

kn k n

k

h h h h

h h h hH

h h h h−

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

… …… …… …… … … … … … … … …

o o oo o oo o o

(XI.6.5)


Capitolo XII

Campi finiti

XII.1 Polinomi irriducibili e campi ad essi associati

Definizione XII.1 Diciamo che un polinomio ( ) ( )nh x x⎡ ⎤∈ ⎣ ⎦F di grado non inferiore a 1 è irriducibile

se:

( ) ( ) ( ) ( ) ( ) ( ) 0n l mh x a x b x lm= ⋅ ⇒ = (XII.1.1)

Ovviamente tutti i polinomi di primo grado sono irriducibili. In 2 x⎡ ⎤⎣ ⎦GF . Anche il

polinomio 3 1x x+ + è irriducibile esso infatti non è divisibile né per x né per 1x + ,

che sono tutti e soli i polinomi di primo grado appartenenti a 2 x⎡ ⎤⎣ ⎦GF . Non sono

necessarie altre verifiche in quanto le eventuali fattorizzazioni devono comunque

contenere un polinomio di primo grado. Il polinomio 2 1x x⎡ ⎤+ ∈ ⎣ ⎦ è irriducibile in

, ma pensato come elemento di x⎡ ⎤⎣ ⎦ non lo è


Teorema XII.1

Se ( ) ( )nh x è un polinomio irriducibile di x⎡ ⎤⎣ ⎦F allora il gruppo quoziente individuato

dall’ideale ( ) ( )nh x è un campo.

Dimostrazione:

Sappiamo già che ( ) ( )n

x

h x

⎡ ⎤⎣ ⎦F è un anello commutativo con identità,

dobbiamo quindi solo verificare che per ogni suo elemento, fatta eccezione per

( ) ( )nh x , esiste un inverso.

90 Capitolo XII

Osserviamo che ( ) ( )nh x non coincide con x⎡ ⎤⎣ ⎦F . Se così non fosse, esiste-

rebbe ( ) ( ) ( ) ( )| ng x x h x g x⎡ ⎤∈ ⋅ =⎣ ⎦ eF , ma la precedente può essere soddisfatta

solo se 0n = , contro l’ipotesi che ( ) ( )nh x è irriducibile, quindi il suo grado non può

essere inferiore ad 1. Possiamo pertanto affermare che ( ) ( )n

x

h x

⎡ ⎤⎣ ⎦F contiene

almeno un polinomio ( ) ( ) ( )ng x h x∉ .

Consideriamo adesso l’insieme

( ) ( ) ( ) ( ) ( ) ( ) ( ){ }| ,na x h x b x g x a x b x x⎡ ⎤= + ∈ ⎣ ⎦F (XII.1.2)

si constata facilmente che è un ideale di x⎡ ⎤⎣ ⎦F , ma (vedi Teorema X.1) tutti gli ideali

di x⎡ ⎤⎣ ⎦F sono principali, deve pertanto esistere in x⎡ ⎤⎣ ⎦F un polinomio ( ) ( )wj x tale che

risulti ( ) ( )wj x = .

Dalla (XII.1.2) deduciamo che ( ) ( )nh x ∈ , quindi deve esistere un polinomio

per il quale risulti ( ) ( ) ( ) ( ) ( ) ( )n w qh x j x y x= , ma ( ) ( )nh x è irriducibile, quindi,

necessariamente, o 0q = , o 0w = . nel primo caso ( ) ( )nh x ≡ , ma ciò è as-

surdo perché contiene anche ( ) ( ) ( ) ( )k ng x h x∉ , deve quindi essere 0w = .

Ciò implica x⎡ ⎤≡ ⎣ ⎦F da cui discende che esistono ( ) ( ),a x b x x⎡ ⎤∈ ⎣ ⎦F che

soddisfano l’uguaglianza

( ) ( ) ( ) ( ) ( ) ( )n ka x h x b x g x= +e (XII.1.3)

La precedente implica:

Campi Finiti 91

( ) ( ){ } ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ){ }( ) ( ) ( ) ( ) ( ) ( ){ }( ) ( ) ( ) ( ){ } ( ) ( ) ( ) ( ){ }

n l n m k n

m k n

m n k n

h x a x h x b x g x h x

b x g x h x

b x h x g x h x

⊕ ⊕

⊕

⊕ ⊗ ⊕

= + =

=

=

e

(XII.1.4)

osservando primo ed ultimo membro della precedente si deduce che il laterale

( ) ( ) ( ) ( ){ }m nb x h x⊕ è l’inverso di ( ) ( ) ( ) ( ){ }k ng x h x⊕ .

***********


XII.2 Ordine degli elementi di un gruppo Consideriamo un gruppo finito , abbiamo già visto che ogni suo sottogruppo

individua una partizione del gruppo in laterali, che hanno tutti la stessa cardinalità del

sottogruppo. Ciò comporta il fatto che il numero di elementi di un sottogruppo, il suo

ordine ( )O , è un sottomultiplo dell’ordine del gruppo in cui esso è contenuto.

Sia x un elemento di un gruppo finito . Consideriamo l’insieme

{ }1 2 3 2 1, , , , ,k kx x x x x x x x x x x x

⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤−⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦⊕ ⊕ ⊕= = =… … (XII.2.1)

x è un sottoinsieme di , in quanto è chiuso rispetto alla legge ⊕ , quindi x deve

avere un numero finito di elementi, da cui facilemente discende che deve esistere un

intero ( )m O≤ , tale che risulti 1mx x⎡ ⎤+⎣ ⎦ = , o, che è lo stesso, tale che

0mx x⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦= o (XII.2.2)

Abbiamo appena mostrato che x contiene o . Considerando adesso il più piccolo

valore di m che soddisfa la (XII.2.2), risulta:

i m i i m i mx x x x⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤− + −⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦⊕ = = = o (XII.2.3)

x è quindi un sottogruppo di . L’ordine del sottogruppo generato da un elemento x

di un gruppo è detto ordine di x , ( )O x .


92 Capitolo XII

XII.3 Ordine degli elementi di un campo finito Consideriamo un campo finito F . Sia p l’ordine di e rispetto alla legge ⊕ ,

possiamo affermare che p è un numero primo. Infatti, se p non lo fosse esisterebbero

due interi, k ed l , entrambi 1> per i quali varrebbe l’uguaglianza:

( ) lp kl k k l⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎣ ⎦⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦⊗ =e = e = e = e e o (XII.3.1)

ma F è un campo vale quindi la legge di annullamento del prodotto, quindi o k⎡ ⎤⎣ ⎦ =e o

o l⎡ ⎤⎣ ⎦ =e o . ( )O e sarebbe quindi il minimo tra k ed l e non p . Ne segue che ( )O e

deve essere un numero primo.

Osserviamo che per ogni elemento α di F si può scrivere eα α ⊗= , che ci

permette di scrivere anche:

( ) ( ) ( )2 2α α α α α⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦⊗ ⊕ ⊗ ⊗ ⊕ ⊗= = =e e e e e (XII.3.2)

più in generale k kα α⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦⊗= e , ma kα

⎡ ⎤⎣ ⎦⊗ =e o solo se α = o , ovvero se k⎡ ⎤⎣ ⎦ =e o ,

possiamo quindi concludere che tutti gli elementi diversi da o di un campo finito hanno

tutti lo stesso ordine rispetto alla somma, e che tale ordine è un primo risulta cioè:

;

,

p p

kk p

α α

α α

⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦⊗

⎡ ⎤⎣ ⎦

= =

< ≠ ⇒ ≠ o

e o

o (XII.3.3)


XII.4 Ordine di un campo finito Consideriamo un campo F , ed un suo sottocampo K , in questo caso diremo che

F è un’estensione di K . Si constata che F ha la struttura di spazio vettoriale sul campo

K . La dimensione di questo spazio se è finita è detta grado di F su K .


Teorema XII.2 - Ordine di un campo finito

L’ordine di un campo finito o è primo, o è una potenza (intera) di un primo.

Dimostrazione:

Campi Finiti 93

Abbiamo visto che l’ordine dell’elemento e di un qualsiasi campo F è un primo p , si

verifica facilmente che l’insieme

{ }2 3, , , p⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ ⎣ ⎦= = ⊆…K Fe e e e o (XII.4.1)

é un campo (isomorfo a pGF ) quindi è un sottocampo non necessariamente proprio di

F .

D’altro canto, F ha la struttura di spazio vettoriale sul campo K la cui dimensione

deve necessariamente essere finita, essendo F finito per ipotesi.

Un qualsiasi elemento di F potrà essere quindi espresso in modo univoco come

combinazione lineare, con coefficienti appartenenti a K , di n elementi che

costituiscano una base per F , cioè che siano linearmente indipendenti su K .

Osservando che esistono esattamente np combinazioni lineari distinte si conclude che

l’ordine di F se non è primo è una potenza di un primo.

***********

Quale che sia il campo finito npGF , il campo pGF generato dalla sua unità

moltiplicativa è detto sottocampo primo o fondamentale. Esso è contenuto in tutti i

sottocampi di npGF , o, che è lo stesso, è l’intersezione di tutti i sottocampi di np

GF

quindi è anche il più piccolo sottocampo di npGF che contiene e (si dice che p è la

caratteristica del campo).

Osserviamo che se un Campo F non è finito, allora anche l’insieme definito nella

(XII.4.1) non lo è, e non è nemmeno un sottocampo di F (non è nemmeno un gruppo) in

questo caso si può dimostrare che il sottocampo minimo contenuto in F è isomorfo al

campo dei razionali e che l’insieme definito nella (XII.4.1) è isomorfo all’insieme

dei naturali. In questo caso diremo che il campo ha caratteristica 0


94 Capitolo XII

XII.5 Elementi primitivi di un campo Sappiamo che un campo np

GF privato dell’elemento neutro rispetto alla somma è

un gruppo rispetto alla moltiplicazione, indichiamolo con np

⊗GF . L’ordine di np

⊗GF è

1np − .

Sia l l’ordine di un generico elemento α di np

⊗GF , risulta

fattori

l

l

α α α α α⊗ ⊗ ⊗ ⊗ =… e (XII.5.1)

l deve necessariamente essere un divisore di 1np − esiste cioè un naturale k tale che

1nlk p= − . Ne segue:

( )1n kp lk l kα α α− = = = =e e (XII.5.2)

Dalla precedente discende che per ogni elemento di np

⊗GF potremo scrivere

n

np

pα α α

⊗= ∀ ∈GF (XII.5.3)

Constatiamo immediatamente che la precedente vale anche per o , possiamo quindi

anche scrivere:

n

np

pα α α= ∀ ∈GF (XII.5.4)

Si può dimostrare che il gruppo np

⊗GF è un gruppo ciclico, cioè che in np

⊗GF vi

sono elementi il cui ordine è uguale all’ordine del gruppo. Un tale elemento si chiama

generatore del gruppo.

Un generatore di np

⊗GF si dice elemento primitivo del campo, in particolare si può

dimostrare che vi sono elementi primitivi in numero uguale a quello dei naturali

1np≤ − e con esso relativamente primi, ad esempio in 4GF ve ne saranno 2 , in

16GF 8 . Inoltre in ogni campo per cui 1np − è un primo, quale ad esempio 8GF tutti

gli elementi diversi da o sono primitivi.


Campi Finiti 95

XII.6 Campi di polinomi Cerchiamo adesso di mettere un po’ d’ordine, sappiamo che:

- se ( )( )nh x è un polinomio irriducibile appartenente a x⎡ ⎤⎣ ⎦F , allora

( ) ( )n

x

h x

⎡ ⎤⎣ ⎦F è un campo.

- ogni campo finito qGF ha un numero di elementi che se non è un numero

primo è una potenza di un primo;

- ( )1k

np

x x− ⎡ ⎤ ⎡ ⎤⊂⎣ ⎦ ⎣ ⎦GF , è isomorfo ad uno spazio vettoriale di dimensione n ,

costituito esattamente da ( )nk nkp p= elementi (una potenza di un primo).

Fissato un polinomio irriducibile ( )( )nh x , e comunque scelto un polinomio

( ) ( )ka x di x⎡ ⎤⎣ ⎦F possiamo scrivere:

( ) ( ) ( ) ( ) ( ) ( )( ) ( )k l n ma x q x h x r x= + (XII.6.1)

la precedente ci mostra che ( )( )mr x ed ( ) ( )ka x , appartengono allo stesso laterale

dell’ideale generato da ( )( )nh x . Notiamo anche che il grado di ( )( )mr x è, inferiore al

grado di ( )( )nh x .

Osserviamo che ( )( )mr x può essere un qualunque polinomio appartenente a

( )1n x− ⎡ ⎤⎣ ⎦ .

In definitiva quindi, individuato un polinomio irriducibile ( )( )nh x , possiamo af-

fermare che ( )1n x− ⎡ ⎤⎣ ⎦ , con l’usuale somma tra polinomi in x⎡ ⎤⎣ ⎦F e definendo come

prodotto tra due suoi elementi il resto della divisione tra il loro prodotto in x⎡ ⎤⎣ ⎦F e

96 Capitolo XII

( )( )nh x , è un campo isomorfo a ( ) ( )n

x

h x

⎡ ⎤⎣ ⎦F, in quanto ogni elemento di

( )1n x− ⎡ ⎤⎣ ⎦ individua uno e un solo laterale di ( ) ( )nh x , e viceversa.

Esempio XII.1 Consideriamo l’anello x⎡ ⎤⎣ ⎦B dei po-

linomi sul Campo 2B GF . Il po-

linomio 3 1x x+ + è irriducibile.

Pertanto 3 1

x

x x

⎡ ⎤⎣ ⎦+ +

B è un

campo, di ordine 8 , in quanto 8 so-no i polinomi di grado minore di 3 a coefficienti in B . Osserviamo che tutti i suoi elementi non nulli sono primitivi in quanto il gruppo 8

⊗GF ha 7 elementi, e sette è un primo. In particolare anche l’elemento

3 1x x xα = + + + sarà primi-

tivo. Assumendo come rappresentan-ti di laterale i polinomi di grado infe-riore a 3 otterremo la Tabella XII.1, nella quale abbiamo convenzional-mente indicato l’elemento neutro ri-

spetto alla somma con α−∞ e, nella quarta colonna, abbiamo associato ai rappresentanti di laterale le corrispondenti parole binarie di 3 bit.


XII.7 Polinomi irriducibili primitivi Consideriamo adesso un campo F e una sua estensione K .

Definizione XII.2 Diciamo che un elemento α ∈ K è algebrico su F se esiste un polinomio ( ) ( )ng x di

x⎡ ⎤⎣ ⎦F che ha α come radice, cioè tale che effettuando le operazioni in K risulti

( ) ( )ng α = o .

α 3 1x x x+ + + 010

2α 2 3 1x x x+ + + 100

3α 31 1x x x+ + + + 011

4α 2 3 1x x x x+ + + + 2α α⊕ 110

5α 2 31 1x x x x+ + + + + 3 2α α⊕ 111

6α 2 31 1x x x+ + + + 4 3α α⊕ 101

7α 31 1x x+ + + 001

α−∞ 0 000Tabella XII.1

Campi Finiti 97

Consideriamo ad esempio il campo dei razionali e la sua estensione (il

campo Reale) l’elemento 2 è algebrico su in quanto il polinomio 2 2x x⎡ ⎤− ∈ ⎣ ⎦

ha 2 tra le sue radici se lo si pensa come un polinomio appartenente a x⎡ ⎤⎣ ⎦ .

Osserviamo che l’insieme x⎡ ⎤⊆ ⎣ ⎦A F contenente i polinomi che hanno α ∈ K tra

le radici è un ideale di x⎡ ⎤⎣ ⎦F . Infatti, comunque scelto un polinomio in A molti-

plicandolo per un qualunque polinomio di x⎡ ⎤⎣ ⎦F si ottiene ancora un polinomio che ha

α tra le sue radici.

L’ideale A deve ammettere quindi un polinomio generatore sia ( )( )ng x .

Osserviamo che esiste sempre un polinomio generatore che ha e come coefficiente del

termine di grado massimo. Un tale polinomio sarà detto monico, da ora in poi quando

parleremo di polinomio generatore sottoinderemo che sia quello monico.

Il polinomio ( )( )ng x è irriducibile in x⎡ ⎤⎣ ⎦F , (non è detto che lo sia in x⎡ ⎤⎣ ⎦K ) in

quanto se così non fosse almeno uno dei fattori in cui potrebbe essere scomposto

ammetterebbe α come radice. Tale fattore apparterrebbe quindi ad A , ed avrebbe grado

inferiore a ( )( )ng x , ( )( )ng x non sarebbe quindi in grado di generarlo e perverremmo ad

un assurdo.

Da quanto sopra segue che esiste un unico polinomio generatore monico di A che

è chiamato polinolinomio minimale di α su F .

Osserviamo che ogni elemento di F è algebrico su F . Inoltre è facile constatare

che se K è finito ogni elemento di K è algebrico sul suo sottocampo primo, in quanto

1npx − − e si annulla in virtù della (XII.5.3) α ⊗∀ ∈ K .

Definizione XII.3 Diciamo che un polinomio irriducibile ( )( )n

ph x x⎡ ⎤∈ ⎣ ⎦GF (p primo) è primitivo se esso

è fattore di 1npx − − e ,ma non di mx − e con 1nm p< − .


98 Capitolo XII

Teorema XII.3

Se ( ) ( )nh x è un polinomio irriducibile di p x⎡ ⎤⎣ ⎦GF l’elemento

( ) ( ) ( ) ( )n p

n

xx h x

h xα

⎡ ⎤⎣ ⎦= + ∈GF

è primitivo per ( ) ( )p

n

x

h x

⎡ ⎤⎣ ⎦GF se e

solo se ( ) ( )nh x è un polinomio primitivo.


XII.8 Alcune proprietà dei campi finiti Consideriamo due elementi α e β di np

GF ci convinciamo facilmente che vale

l’uguaglianza:

( ) ( )

( )0

1

1

;

p pp jj p j

jp p

jp j p j p

j

α β α β

α α β β

⎡⎛ ⎞⎤⎟⎜⎢ ⎥⎟⎜ ⎟⎟⎜− ⎢ ⎥⎝ ⎠⎣ ⎦⊕ ⊗

=⎡⎛ ⎞⎤− ⎟⎜⎢ ⎥⎟⎜ ⎟⎟⎜− ⎢ ⎥⎝ ⎠⎣ ⎦⊕ ⊗ ⊕

=

=

=

∑

∑

F

F

(XII.8.1)

Osserviamo adesso che i coefficienti binomiali nella sommatoria a ultimo membro,

essendo p primo, sono tutti multipli di p . Ciò premesso ci basta ricordare la (XII.3.3)

per concludere che tutti gli addendi della sommatoria all’ultimo membro della

precedente sono uguali ad o ne discende che

( ) ;p p pα β α β⊕ ⊕= (XII.8.2)

Osserviamo anche che risulta:

( ) ( ) 2 2p pp p p p pα β α β α β⊕ ⊕ ⊕

⎡ ⎤ = =⎢ ⎥⎣ ⎦

(XII.8.3)

Dalle precedenti sfruttando la proprietà associativa della della somma e tenuto

conto che la (XII.8.3) può essere applicata iterativamente otteniamo l’equazione:

( ) ,i i i ip p p p iα β γ α β γ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ∈=… … (XII.8.4)

Campi Finiti 99

Un interessante caso particolare si ha quando si eleva ad una potenza p una

combinazione lineare di elementi di npGF pensato come spazio vettoriale sul suo

sottocampo primo:

{ }1 2

0 0

; , ,

i

i

pn np

j j j j jj j

k k i k e eα α⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦

= =

⎛ ⎞⎟⎜ ⎟⎜ = ∈ ∧ ∈⎟⎜ ⎟⎜ ⎟⎜⎝ ⎠∑ ∑ …F F (XII.8.5)

la precedente consente di affermare che per un qualsiasi polinomio ( ) ( )npg x x⎡ ⎤∈ ⎣ ⎦GF

risulta:

( ) ( )( ) ( ) ( ) ( )0 0

;

ii

i i

pn np jn nj p pj j

j j

g x k x k x g x i= =

⎛ ⎞⎟⎜ ⎟⎜= = = ∀ ∈⎟⎜ ⎟⎜ ⎟⎜⎝ ⎠∑ ∑F F (XII.8.6)

dalla quale discende immediatamente che, se il polinomio ammette npα ∈ GF come ra-

dice, esso ammette anche come radice ipα con i ∈ . Tali radici non saranno

ovviamente tutte distinte.


Capitolo XIII

Codici BCH

XIII.1 Codici BCH Supponiamo di voler generare un codice polinomiale con parole di lunghezza n i

cui simboli appartengono ad un campo finito qGF che abbia una distanza minima non

inferiore a d .

Un modo per farlo è quello di scegliere un’estensione di qGF di grado r con un

numero d’elementi non minore di 1n + , sia rqGF . In rq

GF sceglieremo un elemento

primitivo α e costruiremo il polinomio ( ) qg x x⎡ ⎤∈ ⎣ ⎦GF di grado minimo che ha come

radici gli elementi dell’insieme { }2 1, , dα α α −… . Detto polinomio sarà evidentemente il

minimo comune multiplo tra i polinomi minimali associati agli | 0i i dα < < ,

Mostreremo che un polinomio ( )g x così costruito è in grado di generare un codice

con distanza minima non inferiore a d .

A tale scopo osserviamo che l’insieme delle radici di ogni polinomio associato ad

una parola di codice conterrà l’insieme { }2 1, , dα α α −=R … . Affinché un codice abbia

distanza minima pari almeno a d non devono esistere parole di codice, ad eccezione di

quella nulla, che abbiano meno di d simboli diversi da o .

Supponiamo per assurdo che un codice generato nel modo anzidetto non rispetti

questa condizione, in questo caso esisterà almeno una parola di codice individuata da un

polinomio del tipo:

( ) 1 2 1

1 2 1 1 2 1;d

d

n n nn n n dc x c x c x c x n n n−

− −= + + > > >… … (XIII.1.1)

Essendo ( )c x un polinomio di codice l’insieme delle sue radici conterrà l’insieme R

devono quindi essere contemporaneamente soddisfatte le equazioni:

102 Capitolo XIII

( ) ( ) ( )

1 2 1

1 2 1

1 2 1

1 2 1

1 2 1

1 2 1

2 2 2

1 1 1

d

d

d

d

d

d

n n nn n n

n n nn n n

d n d n d nn n n

c c c

c c c

c c c

α α α

α α α

α α α

−

−

−

−

−

−

− − −

⎧⎪ + + =⎪⎪⎪⎪ + + =⎪⎪⎨⎪⎪⎪⎪⎪ + + =⎪⎪⎩

…

…………

…

o

o

o

(XIII.1.2)

Abbiamo così ottenuto un sistema lineare ed omogeneo di 1d − equazioni in 1d −

incognite.

La matrice dei coefficienti del sistema di cui sopra è:

( ) ( ) ( )

1 2 1

1 2 1

1 2 1

2 2 2

1 1 1

d

d

d

n n n

n n n

d n d n d n

α α α

α α α

α α α

−

−

−− − −

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥

= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

A

…

…… … … …

…

(XIII.1.3)

che si può scrivere come segue:

( ) ( ) ( )

1

1 2 1 2

1 2 1 12 2 2

1 1 1 0 0

0 0

0 0

d

d d

n

n n n n

d n d n d n n

α

α α α α

α α α α

−

− −− − −

⎡ ⎤⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦

A

… …… …

… … … … … … … …

… …

(XIII.1.4)

osserviamo che la prima matrice a secondo membro è una matrice di Vandermonde il

suo determinante vale pertanto

( )jinn

i j

α α>

−∏ (XIII.1.5)

A è quindi non singolare, poiché, per ipotesi, α è un elemento primitivo di rqGF

quindi il suo ordine è maggiore di 1d − , ne discende che tutti i binomi della produttoria

(XIII.1.5) sono diversi da o , inoltre il determinante della seconda matrice è certamente

diverso da zero in quanto essa è diagonale e gli elementi della diagonale tutti certamente

diversi da o .

Possiamo quindi concludere che il sistema (XIII.1.2) è di Cramer ed essendo anche

omogeneo esso ammette solo la soluzione banale. Non esistono pertanto parole di

codice, ad eccezione di quella con simboli tutti nulli, che abbiano meno di d simboli

diversi da o .

Codici BCH 103

Quanto appena mostrato permette di costruire un’importante classe di codici detti

BCH, dalle iniziali dei loro scopritori: Bose, Chaundhuri, Hocquenghem.

Alla classe dei codici BCH appartengono anche i codici di Hamming che abbiamo

già visto, nonché i codici di Reed Solomon (RS).

Osserviamo anche che il grado del polinomio generatore non è assegnato a priori,

ma dipende dalla scelta dell’elemento primitivo di rqGF . ne segue che anche il numero

di simboli che costituiscono la parola informativa non può essere prefissato. Osserviamo

anche che la distanza minima del codice potrebbe anche essere maggiore di quella di

progetto.

Tipicamente i simboli che costituiscono la parola di codice appartengono ad un

campo 2m

GF , cioè ad un campo con un numero di elementi che sia una potenza di 2 .

In particolare i codici di Reed Solomon che sono certamente i più importanti tra i

codici BCH hanno simboli appartenenti a 2m

GF lunghezza della parola di codice

2 1mn = − lunghezza della parola informativa k qualsiasi, purchè (ovviamente)

minore di n , e distanza minima 1d n k= − + . Un codice di RS che ha trovato

diverse applicazioni pratiche è il (255,239, 17) che presenta una distanza minima di 17

con parole appartenenti a 82GF , cioè costituite da un byte, il che significa che pensato

come codice binario la parola di codice è di 255 * 8 2040= bit e la corrispondente

parola informativa di 1912 . Questo codice è in grado di correggere fino ad 8 byte errati

indipendentemente dal numero di bit errati nel byte.


Capitolo XIV

La Trasformata di Fourier Discreta

XIV.1 La Trasformata di Fourier Discreta Ricordiamo che la trasformata (DFT) e l’antitrasformata (IDFT) di Fourier

discreta di una sequenza { } 1

0

Ni ic

−

= a valori nel campo complesso di durata N , o

periodica di periodo N è data da:

2

1 12

0 01 1

0 0

1 1nm

jN

nmN Nj nmN

m n n Nn nN N

nmn m m N

m m

C c e c W

c C e C WN N

π

π− −− −

= =− −

= =

=

=

∑ ∑

∑ ∑ (XIV.1.1)

dove NW rappresenta una radice N -esima dell’unità, in altri termini nelle

(XIV.1.1) compaiono le radici appartenenti al campo complesso del polinomio, a

coefficienti in , 1Nx − . Si noti che il campo complesso è un’estensione del campo

reale.

Volendo generalizzare le (XIV.1.1) ai campi finiti, occorre innanzitutto soffermarsi

sull’esistenza della radice N -esima dell’unità del campo. Ricordando la (XII.5.1)e la

(XII.5.3) concludiamo che se operariamo in npx⎡ ⎤⎣ ⎦GF la lunghezza N della sequenza

deve essere un divisore di 1np − .

Ciò premesso consideriamo una sequenza { } 1

0n

N

i p ic

−

=∈ GF ed una radice N -

esima dell’unità in npGF , cioè un elemento di ordine N per il gruppo np

⊗GF , sia Nα .

Prendendo spunto dalle (XIV.1.1) possiamo scrivere la coppia di trasformate

106 Capitolo XIV

1

01

0

Nkm

m k NkN

kmk m N

m

C c

c C

α

χ α

−−

=−

=

=

=

∑

∑

F

F

(XIV.1.2)

Vogliamo verificare se esiste un elemento npχ ∈ GF in corrispondenza al quale

risulti , 0 1k kc c k N= ≤ ≤ − . A tal fine sostituiamo la prima delle (XIV.1.2) nella

seconda:

( )

( )

( )

1 1 1 1

0 0 0 0

1 1 10

0 0 0

1 1 1

0 0 0

N N N Nj k mjm km

k j N N j Nm j j m

N N Nj k m

k N j Nm j m

j k

N N Nj k m

k j Nm j m

j k

c c c

c c

c c

χ α α χ α

χ α α

χ α

− − − −−−⊗ ⊗ ⊗ ⊗ ⊗

= = = =

− − −−

⊗ ⊗ ⊕ ⊗

= = =≠

− − −−

⊗ ⊗ ⊕ ⊗

= = =≠

= = =

⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜= =⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜ ⎟⎜⎝ ⎠⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜= ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜⎜⎝ ⎠

∑ ∑ ∑ ∑

∑ ∑ ∑

∑ ∑ ∑

F F F F

F F F

F F Fe

( ) ( ) ( ) ( )1 1

0

Nj k N j kN N

k j N N kjj k

c c cχ α α χ− −⎡ ⎤ ⎡ ⎤− −⎣ ⎦ ⎣ ⎦⊗ ⊗ ⊗ ⊕ ⊗ ⊕ ⊗ ⊗

=≠

=

⎟⎧ ⎫⎪ ⎪⎪ ⎪⎪ ⎪⎧ ⎫⎪ ⎪⎡ ⎤ ⎡ ⎤⎪ ⎪⎪ ⎪= + − − =⎨ ⎨ ⎬ ⎬⎢ ⎥ ⎢ ⎥⎪ ⎪ ⎪ ⎪⎣ ⎦ ⎣ ⎦⎪ ⎪⎩ ⎭⎪ ⎪⎪ ⎪⎪ ⎪⎩ ⎭

∑Fe e e e

(XIV.1.3)

Affinchè le (XIV.1.2) siano una coppia di trasformate è quindi sufficiente che χ

sia l’inverso di N⎡ ⎤⎣ ⎦e in npGF , in realtà χ è anche l’inverso di N⎡ ⎤⎣ ⎦e in pGF .

Possiamo quindi scrivere la coppia di trasformate:

( )

1

011

0

Nkm

m k Nk

NN km

k m Nm

C c

c C

α

α

−−

=−−⎡ ⎤⎣ ⎦

=

=

=

∑

∑

F

Fe (XIV.1.4)

La Trasformata di Fourier Discreta 107

Per la DFT su un campo finito valgono quasi tutte le proprietà già note per quella

nel campo complesso, ad esempio la linearità, la cui verifica è banale, o quella di

traslazione ciclica.

Sia data una sequenza { } 1

0

Ni ic

−

=, la cui DFT sia { } 1

0

Nm mC

−

=, fissato un intero j

consideriamo la sequenza il cui generico elemento N

k k jc c −= , dove Ni j− sta ad

indicare che la differenza va effettuata modulo N . Vogliamo calcolare la DFT di

{ } 1

0

Ni ic

−

= otteniamo:

( )

1 1

0 01 1

0 0

N

N

N Nkm km

m k N k j Nk kN N

k j mjm jm km jmN k j N N k N N m

k k

C c c

c c C

α α

α α α α α

− −− −

−= =− −

− −− − − −−

= =

= = =

= = =

∑ ∑

∑ ∑ (XIV.1.5)

Dualmente fissato un intero j consideriamo la sequenza { } 1

0

NijN i icα

−

= la sua DFT

vale:

( )1 1

0 0N

N Ni m jij im

m N i N i N m ji i

C c c Cα α α− −

− −−−

= =

= = =∑ ∑ (XIV.1.6)

Alla sequenza { } 1

0

Ni ic

−

= possiamo associare il polinomio:

( ) 10 1 1

NNc x c c x c x −⊕ ⊕ ⊕ −= … (XIV.1.7)

lo stesso possiamo fare per la sua DFT { } 1

0

Nm mC

−

=, ammesso che esista, definendo in

modo analogo un polinomio ( )C x di grado al più 1N − . Osservando le (XIV.1.4) ci

rendiamo conto che risulta

( )

( ) ( )1

mm N

N kk N

C c

c C

α

α

−

−⎡ ⎤⎣ ⎦

=

= e (XIV.1.8)

108 Capitolo XIV

Dalle precedenti discende che se jC = o allora ( )c x ha jNα− come radice, o che

è lo stesso, ha il polinomio jNx α−− tra i suoi fattori. Analoghe considerazioni possono

farsi su ( )C x se qualche 0jc = .

Consideriamo una sequenza { } 1

0

Ni ic

−

= non banale cui corrisponda un ( )c x di grado

non maggiore di 1N k− − . Detto polinomio può avere al più 1N k− − radici che

qualora coincidessero tutte con le iNα , comporterebbero l’annullamento di non più di

1N k− − elementi della { } 1

0

Nm mC

−

= che conseguentemente avrebbe almeno k

elementi non nulli. Applicando la (XIV.1.5) possiamo facilmente concludere che è in

realtà sufficiente che in una sequenza non banale siano nulli 1N k− − elementi

consecutivi (modulo N ), affinché la sequenza trasformata, o antitrasformata abbia

almeno k elementi non nulli.


XIV.2 DFT e codici ciclici Le considerazioni fatte dopo la (XIV.1.8) ci permettono di introdurre una

definizione alternativa per i codici ciclici. Possiamo infatti affermare che

Definizione XIV.1 Un codice ciclico ( ),n k è costituito dal sottoinsieme di m

nq

GF la cui DFT si annulla in

1n k− + posizioni prefissate. La (XIV.1.8).

La definizione appena data comporta ovviamente l’esistenza della DFT, deve

esistere cioè un elemento di ordine n per mq

⊗GF , che consenta di calcolarla, ne discende

che n deve essere un sottomultiplo di 1mq − , cioe una radice n -esima dell’unità di

mqGF . Se vogliamo che le parole di codice abbiano la massima lunghezza l’elemento

scelto per il calcolo della DFT dovrà essere primitivo. In questo caso avremmo

1mn q= − . Il fatto che la Definizione XIV.1 sia equivalente alla Definizione XI.1

La Trasformata di Fourier Discreta 109

risulta evidente tenendo conto della (XIV.1.8) che ci permette di affermare che ogni

polinomio di un codice costruito sulla base della Definizione XIV.1 è multiplo di uno

stesso polinomio che è a sua volta un fattore di 1nx − inteso come polinomio a

coefficienti in mqGF .


XIV.3 DFT e codici BCH

Giovanni Garbo Stefano Mangione Appunti di Teoria dei Codici

Documents

Transcript of Giovanni Garbo Stefano Mangione Appunti di Teoria dei Codici