Appunti di Teoria dell'Informazione e Codici - tti.unipa.itgarbo/Teoria InfeCodici.pdf · Indice v...

DIPARTIMENTO DI

ENERGIA, INGEGNERIA DELL’INFORMAZIONE

E MODELLI MATEMATICI

(DEIM)

Appunti di Teoria dell'Informazione e

Codici

Giovanni Garbo, Stefano Mangione 06/09/2013

ii Appunti di Teoria dell’Informazione e Codici

Sommario

7 Capitolo - 1

Le Sorgenti d’Informazione 7

1.1 - Premessa ............................................................................................................ 7

1.2 - Misura dell’Informazione .......................................................................................... 9

1.3 - Sorgenti d’Informazione ......................................................................................... 11 Esempio I.1.1 ....................................................................................................................15

1.4 - Informazione Associata a un Messaggio ........................................................................ 15

17 Capitolo - 2

Sorgenti con Alfabeto Continuo 18

2.1 - Entropia di una Sorgente con Alfabeto Continuo............................................................... 18

2.2 - Sorgenti Gaussiane ............................................................................................... 19

23 Capitolo - 3

La Codifica di Sorgente 23

3.1 - Premessa .......................................................................................................... 23

3.2 - La Regola del Prefisso ........................................................................................... 23

3.3 - Lunghezza Media di un Codice. ................................................................................ 24

3.4 - La Disuguaglianza di Kraft. ..................................................................................... 25 Esempio 3.1 .....................................................................................................................26

3.5 - Limite Inferiore per la Lunghezza di un Codice. ............................................................... 27 Esempio 3.2 .....................................................................................................................28

3.6 - La Proprietà di Equipartizione. ................................................................................. 30

3.7 - Teorema sulla Codifica di una Sorgente DMS. ................................................................. 32 Teorema 3.1 .....................................................................................................................34 Esempio 3.3 .....................................................................................................................34

3.8 - Codifica di Sorgenti con Memoria. .............................................................................. 36 Esempio 3.4 .....................................................................................................................37 Esempio 3.5 .....................................................................................................................37

39 Capitolo - 4

Canali Privi di Memoria 39

4.1 - L’Informazione Mutua. .......................................................................................... 39

4.2 - Concetto di Canale. .............................................................................................. 40

4.3 - L’equivocazione. ................................................................................................. 43

4.4 - La capacità di canale ............................................................................................. 44

ii Appunti di Teoria dell’Informazione e Codici

4.5 - Il Canale Simmetrico Binario. .................................................................................. 45

4.6 - Capacità del Canale AWGN a Banda Limitata. ................................................................ 47

4.7 - Informazione Mutua tra -messaggi. .......................................................................... 50

4.8 - Canali in Cascata................................................................................................. 51

4.9 - L’Inverso del Teorema della Codifica di Canale ............................................................... 53 Teorema 4.1 .....................................................................................................................58

4.10 - Il piano di Shannon ............................................................................................. 59

61 Capitolo - 5

Cenni di Trasmissione Numerica 61

5.1 - Scenario di Riferimento. ......................................................................................... 61

5.2 - Struttura del modulatore e del codificatore di sorgente ........................................................ 61

5.3 - Struttura del Ricevitore. ......................................................................................... 62

5.4 - La Regola di Decisione Ottima. ................................................................................ 63

5.5 - Il Criterio della Massima Verosimiglianza. ..................................................................... 64

5.6 - Funzioni di Verosimiglianza. ................................................................................... 65

5.7 - Le Regioni di Decisione. ........................................................................................ 66

5.8 - L’Union Bound. ................................................................................................. 68

5.9 - Bound di Bhattacharrya. ........................................................................................ 70

5.10 - Bound di Gallager............................................................................................... 75

79 Capitolo - 6

Il Teorema di Shannon sulla Codifica di Canale 79

6.1 - Premessa. ........................................................................................................ 79

6.2 - La Disuguaglianza di Jensen.................................................................................... 80 Definizione 6.1 ..................................................................................................................80 Definizione 6.2 ..................................................................................................................81

6.3 - Il Teorema di Shannon sulla Codifica di Canale. .............................................................. 83 Teorema 6.1: Teorema di Shannon sulla codifica di canale ..................................................................92

95 Capitolo - 7

Strutture Algebriche 95

7.1 - Gruppo ........................................................................................................... 95

7.2 - Anello ............................................................................................................ 95

7.3 - Campo............................................................................................................ 95

7.4 - Spazio vettoriale ................................................................................................. 96

Indice iii

97 Capitolo - 8

Distanza di Hamming 97

8.1 - Lo Spazio ..................................................................................................... 97

8.2 - Generalizzazione della distanza di Hamming .................................................................. 98

101 Capitolo - 9

Codici Binari a Blocchi 101

9.1 - Codificatore, Codice, Decodificatore .......................................................................... 101 Definizione 9.1 - codificatore a blocchi ..................................................................................... 101 Definizione 9.2 - codice binario a blocchi ................................................................................... 101 Definizione 9.3 - decodificatore ............................................................................................. 102

9.2 - Utilità della codifica di canale ................................................................................. 103

9.3 - La decodifica a massima verosimiglianza .................................................................... 105 Regola di decisione a Massima Verosimiglianza ............................................................................ 106

9.4 - Definizioni e teoremi sui codici rivelatori e correttori ........................................................ 106 Definizione 9.4 ................................................................................................................ 107 Definizione 9.5 ................................................................................................................ 107 Teorema 9.1 ................................................................................................................... 107 Definizione 9.6 ................................................................................................................ 108 Teorema 9.2 ................................................................................................................... 108 Teorema 9.3 ................................................................................................................... 109

111 Capitolo - 10

Codici Lineari a Blocchi 111

10.1 - Premessa ....................................................................................................... 111

10.2 - Morfismi ....................................................................................................... 111 Definizione 10.1 - omomorfismo ............................................................................................ 112 Definizione 10.2 - monomorfismo .......................................................................................... 112 Definizione 10.3 - isomorfismo .............................................................................................. 112

10.3 - Schema di principio di un codice lineare a blocco .......................................................... 112

10.4 - Matrice generatrice del codice ............................................................................... 113

10.5 - Distribuzione dei pesi di un codice lineare a blocco ........................................................ 115 Definizione 10.4 –Distribuzione dei pesi di un codice lineare ............................................................. 115

10.6 - Capacità di rivelazione di un codice lineare a blocco ....................................................... 116 Teorema 10.1 .................................................................................................................. 116

10.7 - Probabilità di non rivelazione d’errore di un codice lineare ................................................ 116

10.8 - Laterali di un sottogruppo .................................................................................... 117

10.9 - Decodifica tramite i rappresentanti di laterale ............................................................... 119 Teorema 10.2 .................................................................................................................. 120

10.10 - Probabilità d’errore di un codice lineare a blocchi ......................................................... 120

iv Appunti di Teoria dell’Informazione e Codici

10.11 - Codici perfetti, bound di Hamming ........................................................................ 121

123 Capitolo - 11

Codici Sistematici 123

11.1 - Codici Sistematici ............................................................................................. 123

11.2 - Matrice di controllo di parità ................................................................................. 125

11.3 - Codici duali ................................................................................................... 125

11.4 - Decodifica basata sulla sindrome ............................................................................ 126

129 Capitolo - 12

Codici di Hamming e loro duali 129

12.1 - Codici di Hamming .......................................................................................... 129 Esempio 12.1 .................................................................................................................. 130

12.2 - Duali dei codici di Hamming ................................................................................ 131

12.3 - Codici ortogonali e transortogonali .......................................................................... 132

135 Capitolo - 13

Codici Convoluzionali 135

13.1 - Premessa ...................................................................................................... 135

13.2 - Struttura del codificatore ..................................................................................... 135

13.3 - Matrice generatrice e generatori. ............................................................................ 136

13.4 - Diagramma di stato del codificatore. ........................................................................ 138

13.5 - Codici catastrofici ............................................................................................ 140

13.6 - Trellis degli stati .............................................................................................. 141 Esempio 13.1 .................................................................................................................. 143

145 Capitolo - 14

L’Algoritmo di Viterbi 145

14.1 - Decodifica hard e soft di un codice convoluzionale. ........................................................ 145

14.2 - L’algoritmo di Viterbi ........................................................................................ 148

14.3 - Efficienza dell’algoritmo di Viterbi .......................................................................... 150

153 Capitolo - 15

Prestazioni dei Codici Convoluzionali 153

15.1 - Distanza libera di un codifie convoluzionale. ............................................................... 153

15.2 - Funzione di trasferimento di un codificatore convoluzionale. ............................................. 154

15.3 - Bound sulla probabilità di primo evento d’errore. .......................................................... 157

Indice v

Esempio 15.1 .................................................................................................................. 160

15.4 - Bound sulla probabilità d’errore sul bit informativo. ........................................................ 164

169 Capitolo - 16

Anelli di Polinomi 169

16.1 - Premessa ....................................................................................................... 169

16.2 - L’anello polinomi a coefficienti in ......................................................................... 169

16.3 - Spazi di polinomi.............................................................................................. 171

173 Capitolo - 17

Codici polinomiali 173

175 Capitolo - 18

Ideali di un anello di polinomi 175

18.1 - Premessa ....................................................................................................... 175

18.2 - Ideali di un anello con identità. .............................................................................. 176 Teorema 18.1 .................................................................................................................. 176 Teorema 18.2 .................................................................................................................. 177

179 Capitolo - 19

Codici Ciclici 179

19.1 - Rappresentazione polinomiale di un codice ciclico. ........................................................ 179 Definizione 19.1 ............................................................................................................... 179

19.2 - Teorema sui codici ciclici .................................................................................... 180 Teorema 19.1 .................................................................................................................. 180

19.3 - Polinomio generatore di un codice ciclico ................................................................... 181

19.4 - Polinomio di parità di un codice ciclico ..................................................................... 182 Esempio 19.1 .................................................................................................................. 183

19.5 - Matrice generatrice di un codice ciclico ..................................................................... 184

19.6 - Codici ciclici Sistematici ...................................................................................... 185 Esempio 19.2 .................................................................................................................. 186

19.7 - Duale di un codice ciclico .................................................................................... 187

189 Capitolo - 20

Campi finiti 189

20.1 - Polinomi irriducibili e campi a essi associati ................................................................ 189 Definizione 20.1 ............................................................................................................... 189 Teorema 20.1 .................................................................................................................. 189

20.2 - Ordine degli elementi di un gruppo ......................................................................... 190

20.3 - Ordine degli elementi di un campo finito ................................................................... 191

vi Appunti di Teoria dell’Informazione e Codici

20.4 - Ordine di un campo finito ................................................................................... 192 Teorema 20.2 - Ordine di un campo finito ................................................................................. 192

20.5 - Elementi primitivi di un campo ............................................................................. 193

20.6 - Campi di polinomi ........................................................................................... 194 Esempio 20.1 .................................................................................................................. 194

20.7 - Polinomi irriducibili primitivi................................................................................ 195 Definizione 20.2 ............................................................................................................... 195 Teorema 20.3 .................................................................................................................. 195

20.8 - Alcune proprietà dei campi finiti ............................................................................ 195 Esempio 20.2 .................................................................................................................. 196

20.9 - Il logaritmo di Zech .......................................................................................... 198

20.10 - Elementi algebrici di un campo su un sottocampo ........................................................ 199 Definizione 20.3 ............................................................................................................... 200

201 Capitolo - 21

Codici BCH 201

21.1 - Codici BCH ................................................................................................... 201 Esempio 21.1 - Progetto di un codice BCH ................................................................................ 203

207 Capitolo - 22

La Trasformata di Fourier Discreta 207

22.1 - La Trasformata di Fourier Discreta.......................................................................... 207

22.2 - DFT e codici ciclici .......................................................................................... 210 Definizione 22.1 ............................................................................................................... 210

Capitolo - 1

LE SORGENTI D’INFORMAZIONE

1.1 - Premessa

Uno dei maggiori problemi che s’incontrano nella stesura di

un testo che tratti la teoria dell’informazione è quello della

notazione da adottare, non è affatto semplice trovare il giusto

compromesso tra sinteticità e chiarezza della stessa.

Nel seguito avremo spesso a che fare con variabili aleatorie (V.A.)

che indicheremo con lettere maiuscole. Come è noto ad ogni V.A.

si può associare una distribuzione di probabilità (DDP) ed una densità

di probabilità (ddp) che altro non è se non la derivata della DDP,

intesa eventualmente in senso generalizzato.

Nel caso delle variabili aleatorie discrete che possono cioè

assumere un numero finito di valori è più comodo fare riferi-

mento alla distribuzione di massa di probabilità (dmp) cioè ad una

funzione ( ) che associa ad ogni valore che la V.A. può

assumere la probabilità dell’evento: “ assume il valore ”.

Quando si riterrà che non vi siano possibilità d’equivoci si

ometterà il pedice che individua la V.A. affidando all’argomento

della funzione anche questo compito, cioè ( ) ( ).

Si noti che la notazione che qui si adotta è purtroppo

analoga a quella normalmente utilizzata per indicare la ddp di una

variabile aleatoria, un minimo di attenzione al contesto dovrebbe,

si spera, essere sufficiente ad evitare confusioni. Le ddp verranno

di regola indicate con lettere greche con a pedice la V.A. cui si

riferiscono ad esempio ( ).

Come è noto per le variabili aleatorie discrete è particolarmente

semplice desumere da una qualunque delle tre funzioni di proba-

bilità appena citate le altre. In particolare se è nota la dmp di una

variabile aleatoria discreta che assume valori appartenenti all’in-

0 - Appunti di Teoria dell’Informazione e Codici 8

sieme la corrispondente DDP ( ) sarà una fun-

zione definita su tutto costante a tratti con discontinuità d’am-

piezza ( ) in corrispondenza dei valori che la V.A. può assu-

mere. La ddp ( ) sarà espressa da ( ) ∑ ( ) (

).

Nel calcolo delle sommatorie che s’incontreranno ad ogni

piè sospinto si indicherà il più sinteticamente possibile l’indice su

cui le suddette operano. Ad esempio avendo a che fare con una

V.A. discreta che assuma valori in un insieme , la

condizione di normalizzazione della sua dmp sarà indicata come

segue:

∑ ( )

(1.1.1)

anziché:

∑

( ) (1.1.2)

Analogamente quando si avrà a che fare con variabili alea-

torie multidimensionali, come ad esempio nel caso di una -upla

di simboli emessi consecutivamente, si utilizzeranno distribuzioni

di massa congiunte che saranno caratterizzate scrivendo, ove pos-

sibile, pedice e argomento in grassetto. Ad esempio nel caso di

una coppia di variabili aleatorie che assumono entrambe

valori sull’insieme , la condizione di normalizzazione verrà

sinteticamente scritta:

∑ ( )

(1.1.3)

anziché

∑ ∑ ( )

(1.1.4)


Nel caso delle ddm condizionate con

( ) (1.1.5)

si indicherà sinteticamente la seguente probabilità condizionata:

( ) (1.1.6)

anche in questo caso, quando si riterrà che non vi siano possibilità

d’equivoci si ometterà il pedice affidando agli argomenti l’identi-

ficazione delle variabili aleatorie cui si fa riferimento.

1.2 - Misura dell’Informazione

Il concetto d’informazione a livello intuitivo è chiaro. Si

acquisisce un’informazione nel momento in cui si viene a cono-

scenza di qualcosa che prima ci era ignoto. Quantificare l’informa-

zione da un punto di vista matematico richiede invece qualche ri-

flessione.

Per inquadrare meglio il problema facciamo riferimento ad

un esperimento casuale che com’è noto è caratterizzato da un in-

sieme di possibili risultati, da una famiglia d’eventi (insiemi di

risultati) e dalle probabilità associate a ciascuno di essi.

In prima istanza si accetta facilmente l’idea che il contenuto

informativo di un evento sia tanto più grande quanto più esso è

inatteso, ciò ad esempio si riflette nella dimensione del carattere

utilizzato nei titoli di un quotidiano che, di regola, è direttamente

proporzionale alla “sensazionalità” dell’evento di cui il titolo

intende dare notizia. Una notizia è tanto più sensazionale quanto

più essa è inattesa, “un padrone ha morso il suo cane”.

Pertanto, volendo definire una misura per la quantità d’in-

formazione associata ad un evento, minor prevedibilità deve equi-

valere ad un valore maggiore di tale misura.

Inoltre, qualora si verifichino più eventi, per semplicità

prendiamone in considerazione solo due, la misura dell’informa-

zione complessiva dovrebbe essere pari alla somma delle infor-

mazioni acquisite con il manifestarsi dei singoli eventi, sempre che


le informazioni acquisite con il manifestarsi di uno di essi non ab-

biano modificato l’incertezza sul secondo.

In conclusione una misura dell’informazione deve essere:

- legata alla probabilità che il generico evento ha di manifestarsi

ed in particolare deve crescere al diminuire di essa e deve

variare con continuità al variare di quest’ultima;

- nel caso di un evento congiunto deve essere pari alla somma

delle informazioni associate ai singoli eventi, se questi sono

tra loro statisticamente indipendenti cioè se il manifestarsi di

uno dei due lascia inalterata l’incertezza sull’altro.

Ricordando che la probabilità che si verifichino più eventi

statisticamente indipendenti è pari al prodotto delle probabilità

dei singoli eventi, si può pensare di quantificare l’informazione

sfruttando la nota proprietà dei logaritmi

( ) ( ) ( ) (1.2.1)

In particolare si assume come informazione (A) associata ad un

evento che si manifesta con probabilità (A) valga:

( ) (

) (1.2.2)

L’informazione associata all’evento non dipende quindi dal-

la natura di quest’ultimo, ma solo dalla probabilità che esso ha di

manifestarsi, pertanto la notazione utilizzata è impropria poiché fa

apparire l’informazione come associata all’evento, non alla sua

probabilità.

La (1.2.2) soddisfa i due requisiti sopra indicati, in partico-

lare cresce al diminuire di . É stato dimostrato che il logaritmo è

l’unica funzione che soddisfa i requisiti sopra elencati.

Osserviamo anche che la base adottata per il logaritmo non

è concettualmente importante, cambiarla equivale ad introdurre

un fattore di scala, come appare ovvio se si ricorda la regola per il

cambiamento di base dei logaritmi:


(1.2.3)

In pratica scegliere la base nella (1.2.2) equivale a scegliere una

particolare unità di misura. La potenza di un motore non cambia

se viene misurata in KW o in HP, anche se espressa in cavalli è

più accattivante.

Nella Teoria dell’Informazione si utilizzano tipicamente

due basi per il logaritmo che compare nella (1.2.2) la base se si

intende misurare l’informazione il nat, o la base se la si vuole

misurare in bit (binary information unit non binary digit).

Ad esempio nel caso del lancio di una moneta non truccata al

manifestarsi dell’evento è associata un’informazione pari

a –

o a –

L’utilizzo del bit

come unità di misura è di regola preferito dal momento che la

quasi totalità dei moderni sistemi di informazione utilizza sistemi

di calcolo che lavorano in base e che i dati tra computer vengo-

no scambiati tipicamente sotto forma di parole binarie. In quel

che segue il logaritmo naturale verrà indicato con “ ” ed il loga-

ritmo in base con “ ” omettendo l’indicazione della base.

1.3 - Sorgenti d’Informazione

Una sorgente d’informazione, è un sistema che emette in

modo più o meno casuale sequenze d’elementi appartenenti ad un

assegnato insieme, l’alfabeto della sorgente.

Come vedremo, la natura dei simboli è del tutto inessen-

ziale per lo sviluppo della teoria, potremo quindi sempre pensare

che l’alfabeto sia numerico, cioè che la sorgente emetta una se-

quenza di variabili aleatorie, che, se l’insieme è finito, saranno di

tipo discreto. In alternativa possiamo pensare di definire sull’in-

sieme dei simboli emessi, che costituisce in sostanza l’insieme dei

risultati di un esperimento casuale, una V.A. biettiva.

Un sistema di trasmissione ha il compito di recapitare dei

dati in modo affidabile da un emissario a un destinatario. Il grado


d’affidabilità del sistema può essere caratterizzato dal numero

d’errori da cui è mediamente afflitto.

Si osservi che emissario e destinatario possono anche trovarsi nel-

lo stesso luogo ed essere addirittura lo stesso soggetto, come ad

esempio avviene nel caso della memorizzazione di dati, che si au-

spica possano essere utili in futuro, su un supporto fisico.

L’emissario in sostanza è una sorgente d’informazione che

può generare segnali a tempo continuo o discreto.

Le sorgenti di tipo discreto sono quelle che emettono dei

simboli, o lettere, appartenenti ad un assegnato insieme, al più

numerabile, che chiameremo alfabeto di sorgente.

Se la probabilità che in un dato istante la sorgente emetta

una qualunque lettera non dipende dai simboli emessi negli altri

istanti si dice che la sorgente è priva di memoria.

Una sorgente discreta priva di memoria (Discrete Memoryless Source,

DMS) potrebbe ad esempio essere quella che emette la sequenza

dei risultati ottenuti lanciando ripetutamente un dado, l’alfabeto

utilizzato sarebbe in questo caso costituito da sei simboli che si

potrebbero etichettare con i primi sei numeri naturali.

Viceversa una sorgente discreta dotata di memoria potreb-

be essere una sorgente che trasmette testi in lingua italiana. Esiste-

rebbero pochi dubbi su quale sarà il simbolo emesso successiva-

mente alla sequenza “p r e c i p i t e v o l i s s i m e v o l m e n t”,

almeno per quelli che hanno visto Mary Poppins, o sul fatto che

dopo l’emissione della lettera q verrà emessa una u, a meno che i

due simboli precedenti non siano stati s o, fatti salvi, ovviamente,

gli errori, sempre in agguato malgrado e, talvolta, a causa dei cor-

rettori ortografici.

Come anticipato nella premessa, non si perde generalità

ipotizzando che la sorgente emetta una sequenza di variabili

aleatorie che assumono valori appartenenti ad un sotto-

insieme di che si può porre in corrispondenza biunivoca con

l’insieme delle lettere che costituiscono l’alfabeto della sorgente


che supporremo finito.

In sostanza quanto detto equivale ad

associare un’etichetta numerica ad ogni lettera dell’alfabeto della

sorgente.

In quel che segue supporremo che la sia stazionaria

cioè che la sua statistica a qualunque ordine dipenda esclusiva-

mente dalla posizione relativa degli istanti di osservazione, non

dall’origine dei tempi. L’ipotesi appena fatta implica, tra l’altro,

che l’alfabeto utilizzato non vari al variare dell’indice temporale .

Detta la V.A. emessa dalla sorgente all’istante , ad ogni

simbolo dell’alfabeto si può associare una probabilità d’emis-

sione:

( ) (1.3.1)

L’informazione che si acquisirebbe rilevando l’emissione

della lettera senza nulla sapere sulle lettere precedentemente

emesse varrebbe quindi:

( ) ( ) (1.3.2)

assumendo ove necessario (

) , alla sorgente si può asso-

ciare la sua entropia:

( ) ∑ ( )

( )

∑

(1.3.3)

L’entropia ( ) appena definita, è la media statistica

dell’informazione associata all’emissione dell’ -esimo simbolo.

Essa rappresenta pertanto l’informazione che mediamente si

acquisisce per effetto dell’emissione di un simbolo da parte della

sorgente all’istante . Osserviamo che la stazionarietà della sequen-

za comporta che ( ) sia indipendente da , tale indice può

quindi essere omesso.

Si noti che anche l’entropia dipende esclusivamente dalla

distribuzione di probabilità dei simboli emessi e non dalla loro na-

tura.


L’entropia di una sorgente, è non negativa ed è limitata

superiormente. In particolare se l’alfabeto ha cardinalità si ha:

∑

(1.3.4)

Per verificare la precedente disuguaglianza consideriamo

due possibili dmp:

∑

∑

(1.3.5)

vale la seguente catena di disuguaglianze:

∑

∑

∑

∑

∑ (

)

(1.3.6)

La maggiorazione effettuata è

corretta in quanto nell’insieme di

definizione di risulta

(vedi Fig. 1.1). La prece-

dente permette di affermare che

se sostituiamo la dmp ad argo-

mento del logaritmo con una di-

versa da quella utilizzata per il cal-

colo della media otteniamo co-

munque una maggiorazione del-

l’entropia.

In particolare se nella (1.3.6) si

sceglie

si ot-

Fig. 1.1 - , ( ).

x-0.5 0.5 1 1.5 2 2.5 3

-2

-1

1

2

3y


tiene:

∑

∑

( ) ∑

(1.3.7)

da cui la (1.3.4).

Esempio I.1.1

Si consideri una sorgente che emette simboli appartenenti a un alfabeto

binario costituito quindi da due soli simboli ad esempio, , detta la

probabilità che venga emesso il simbolo l’entropia della sorgente vale:

( ) ( )

( )

Si osservi che ( ) (vedi Fig.E 1.1) in accordo con la (1.3.7) rag-

giunge il suo massimo per

.

In sostanza una

sorgente fornisce me-

diamente tanta più in-

formazione quanto me-

no prevedibile è il sim-

bolo che essa emetterà.

Nel caso di una sorgen-

te binaria la massima

entropia è pari ad un bit

e si ottiene quando la

sorgente emette dati equiprobabili.

La (1.3.7) mostra che il massimo contenuto informativo

medio si ottiene da sorgenti in cui ogni simbolo ha la stessa pro-

babilità di essere emesso di qualsiasi altro appartenente all’alfabe-

to.

1.4 - Informazione Associata a un Messaggio

Si può anche definire l’informazione derivante dall’emis-

sione di una -upla di simboli emessi consecutivamente dalla sor-

Fig.E 1.1 - Entropia di una sorgente binaria in

funzione della dmp dei dati

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

p

H p


gente. In questo caso parleremo di -messaggio emesso dalla sor-

gente, che possiamo pensare come la realizzazione di una V.A. -

dimensionale . Se l’alfabeto della sorgente ha

cardinalità allora esisteranno al più possibili messaggi. Indi-

cando con A , il generico -messaggio e con

( ) la probabilità che sia emesso, l’informazione ad esso

associata è data da:

( )

( ) (1.4.1)

mediando sui possibili messaggi otteniamo l’entropia associata

all’ -messaggio:

( ) ∑ ( )

( )

(1.4.2)

Se i simboli emessi dalla sorgente sono i.i.d. allora risulta:

( ) ∏ ( )

(1.4.3)

sostituendo la precedente nella (1.4.2):

( ) ∑ ( )

( )

∑ ( )

∏ ( )

∑ ( )∑

( )

∑ ∑ ( )

( )

∑∑ ( )

( )

( )

(1.4.4)

pertanto, se la sorgente è stazionaria e priva di memoria, l’entropia

associata ad un messaggio di lunghezza è volte l’entropia

associata al singolo simbolo.

Assumiamo adesso:


( ) ∏ ( )

(1.4.5)

( ) soddisfa ovviamente le condizioni necessarie per essere una

possibile dmp di una V.A.multidimensionale. Seguendo la falsa-

riga della (1.3.6) si può scrivere:

∑ ( )

( ) ∑ ( )

( )

∑ ( ) ( )

( )

∑ ( )

( ( )

( ) )

(1.4.6)

d’altro canto risulta:

∑ ( )

( )

∑ ( )

∏ ( )

∑ ( )

∑

( )

∑ ∑ ( )

( ) ∑ ∑ ( )

( )

∑ ( )

( )

(1.4.7)

dove l’ultima uguaglianza vale solo nel caso in cui i simboli emessi

dalla sorgente siano identicamente distribuiti, cioè nel caso in cui

la sorgente sia stazionaria, pur non essendo necessariamente priva

di memoria.

Dalle (1.4.6) e (1.4.7) deduciamo che in generale per sor-

genti stazionarie risulta

( ) ( ) (1.4.8)

cioè a parità di cardinalità dell’alfabeto e di lunghezza del mes-

saggio la massima informazione media è fornita da sorgenti prive

di memoria che emettono simboli equiprobabili.


SORGENTI CON ALFABETO CONTINUO

1.5 - Entropia di una Sorgente con Alfabeto Continuo

Consideriamo adesso una sorgente che emette con cadenza

regolare simboli appartenenti ad un insieme non numerabile.

Potremo cioè pensare che la sorgente emetta una sequenza

di variabili aleatorie di tipo continuo. La sorgente sarà per-

tanto equivalente da un processo aleatorio a tempo discreto conti-

nuo in ampiezza, che è completamente caratterizzato qualora sia

nota la sua statistica a qualunque ordine.

Per definire l’entropia ( ) di una tale sorgente, cioè l’in-

formazione che mediamente acquisiremmo in seguito all’emis-

sione di un singolo simbolo, senza nulla sapere dei simboli emessi

precedentemente da una tale sorgente, dovremo fare riferimento

alla densità di probabilità ( ) della variabile aleatoria che essa

genera in un dato istante. Se supponiamo che la sorgente sia

stazionaria tale densità di probabilità sarà indipendente dall’istante

di osservazione.

Basandoci su quanto detto per le sorgenti con alfabeto

discreto, sorge spontaneo definire tale entropia come segue:

( ) ∫ ( )

( )

(1.5.1)

assumendo che

. Tale definizione non gode di tutte le

proprietà di cui godeva l’entropia di una sorgente con alfabeto

finito, essa ad esempio può assumere anche valori negativi e può

non essere limitata.

Anche per le sorgenti ad alfabeto continuo possiamo defi-

nire l’entropia associata a più simboli emessi. Nel caso di due soli

simboli si ha:


( ) ∫ ∫ ( )

( )

∫ ∫ ( )

( )

∫ ∫ ( )

( )

( ) ( ) ( ) ( )

(1.5.2)

se e sono statisticamente indipendenti dalla precedente si

ottiene:

( ) ( ) ( ) (1.5.3)

Si può provare che in generale risulta:

( ) ( ) ( ) (1.5.4)

1.6 - Sorgenti Gaussiane

Osserviamo che:

( ) ∫ ( ) ( ( ))

∫ ( )( ( ) )

∫ ( ( ))

( ) ∫ ( ( ))

(1.6.1)

ne segue che se ∫ ( ( ))

la ( ) è limitata inferior-

mente. Ciò avviene certamente se la ( ) è limitata. La somma-

bilità di ( ) garantisce in questo caso anche quella di ( ( )) . La

( ) è certamente limitata inferiormente anche quando la ( )

non si mantiene limitata, purchè in corrispondenza ai valori di

in cui diverge lo faccia più lentamente di

con

per

. Consideriamo adesso una generica ddp ( ) risulta:


∫ ( )

( )

∫ ( )

( ) ∫ ( )

( )

( )

∫ ( ) (

( )

( ) )

(1.6.2)

La precedente può essere pensata come una generalizzazione della

(1.4.6).

Supponiamo che la sorgente emetta una variabile aleatoria

con varianza finita , ponendo nella (1.6.2) ( )

√

( )

,

cioè scegliendo una ddp Gaussiana con varianza otteniamo:

∫ ( )

( )

∫ ( ) (√

( )

)

√ ∫ ( )

∫ ( ) ( ( )

)

(

) ∫ ( )( )

(

)

(

)

(1.6.3)

d’altro canto si verifica facilmente che

(

) è anche

l’entropia di una variabile aleatoria Gaussiana, con varianza .

Quanto appena esposto ci porta a concludere che a parità

di varianza le sorgenti continue Gaussiane generano la massima

informazione media.

È opportuno osservare che l’entropia di una sorgente sta-

zionaria continua è indipendente dal valor medio della variabile

aleatoria emessa. Un valor medio non nullo incide solo sul valor

quadratico medio della sequenza emessa aumentandolo. Il che in

altri termine vale a dire che un valor medio diverso da zero au-


menta la potenza media del processo senza offrire alcun beneficio

in termini d’informazione media a esso associata.

Capitolo - 2

LA CODIFICA DI SORGENTE

2.1 - Premessa

Gli attuali sistemi di trasmissione sono spesso basati su un

mezzo trasmissivo di capacità limitata che viene condiviso tra più

utenti, diventa quindi essenziale cercare di ottimizzarne l’utilizzo

al fine di consentire l’accesso alla risorsa ad un maggior numero di

soggetti. È quindi auspicabile mettere in atto dei metodi che

consentano di “compattare” le informazioni da trasmettere in

modo da utilizzare il sistema per il minor tempo possibile, ovvero

da occupare una minore quantità di banda, senza pregiudicare il

contenuto informativo del messaggio. Lo stesso discorso ovvia-

mente vale nel caso dell’immagazzinamento delle informazioni,

“zippare” un file serve a sfruttare meglio la memoria dell’hard

disk.

La quasi totalità dei sistemi di trasmissione oggigiorno è

numerica, e fa uso di sistemi d’elaborazione digitale che lavorano

in base due, pertanto ci occuperemo di analizzare delle tecniche di

codifica di sorgente che associno alle singole lettere o a interi mes-

saggi emessi da quest’ultima delle parole binarie cioè delle stringhe

di lunghezza non necessariamente costante costituite utilizzando

un alfabeto di due sole lettere.

Una sorgente che utilizza un alfabeto di cardinalità può

emettere al più M-messaggi distinti, se a ciascuno di essi si

associa una parola binaria si dice che si è definito un codice.

2.2 - La Regola del Prefisso

Il codice citato nel precedente paragrafo può essere costru-

ito utilizzando parole binarie tutte con lo stesso numero di bit, nel

qual caso la lunghezza minima di tali parole non potrà essere infe-

riore a:

24 Capitolo - 2 - Appunti di Teoria dell’Informazione e Codici

( ) (2.2.1)

dove indica il primo intero non minore.

Si possono anche utilizzare parole di codice di lunghezza

variabile, in questo caso, però, occorrerà prestare attenzione al

fatto che se s’invia un file costituito da più -messaggi consecu-

tivi i singoli messaggi dovranno essere decodificabili in modo uni-

voco, dovremo in altri termini essere certi del fatto che a coppie

distinte di sequenze finite di messaggi il codice non associ la stessa

stringa binaria (da qui in poi con stringa indicheremo una sequen-

za di lunghezza finita di parole di codice).

Tale requisito è certamente soddisfatto se nessuna delle pa-

role del codice è identica alla parte iniziale di un’altra parola di

codice. In questo caso diciamo che il codice rispetta la regola del

prefisso.

È opportuno sottolineare che la regola del prefisso è solo

sufficiente, si potrebbero cioè individuare dei codici che pur non

rispettandola, sono decodificabili in modo univoco. Tali codici

tuttavia ci obbligherebbero per effettuare la decodifica ad atten-

dere la ricezione se non dell’intera sequenza di -messaggi certa-

mente di più di un messaggio. Viceversa, se il codice soddisfa la

regola del prefisso la decodifica può essere effettuata istanta-

neamente cioè ogniqualvolta una parola binaria coincide con una

parola di codice l’ -messaggio corrispondente si può dare per

identificato, non essendo possibile alcuna ambiguità.

2.3 - Lunghezza Media di un Codice.

Note le caratteristiche della sorgente e fissata la lunghezza

del messaggio da codificare e detto ( ) il numero di bit che co-

stituiscono la parola binaria ( ) che il codice associa all’ -mes-

saggio , ad ogni codice si può associare una lunghezza media del-

la parola di codice:

∑ ( ) ( )

(2.3.1)


ne discende che il numero medio di bit utilizzati per ciascun sim-

bolo emesso dalla sorgente è pari a

.

La conoscenza di tale dato è importante in quanto ci per-

mette ad esempio di stimare con buona approssimazione lo spa-

zio di memoria necessario per archiviare un file “tipico” costituito

da un numero sufficientemente grande di simboli emessi dalla

sorgente .

Dal nostro punto di vista un codice di sorgente è tanto mi-

gliore quanto minore è la sua lunghezza media a patto che ovvia-

mente la sua decodifica non risulti troppo onerosa.

Esiste un importante teorema che, nel caso di sorgenti

DMS stazionarie da un lato pone un limite inferiore alla lunghezza

media ottenibile al variare del codice scelto e dall’altro garantisce

che, se si è disposti ad accettare una maggiore complessità nei

processi di codifica/decodifica è possibile approssimare tale limite

bene quanto si vuole.

Per dimostrare tale teorema ci serviremo di una condizione

necessaria alla decodificabilità di un codice di sorgente, a differen-

za di quella del prefisso che, come già detto, è invece una condi-

zione sufficiente.

2.4 - La Disuguaglianza di Kraft.

Consideriamo una sorgente DMS con alfabeto di cardina-

lità ed un generico codice per gli -messaggi emessi da essa.

Comunque scelto vale l’identità:

( ∑ ( )

)

∑ ∑

∑ ( ( ) ( ) ( ))

(2.4.1)

la sommatoria ad ultimo membro della precedente può anche es-

sere calcolata “accorpando” i termini con uguale esponente. A tale

scopo indichiamo con la massima lunghezza raggiunta dalle

parole di codice. Il massimo esponente che può comparire nel-


l’ultimo membro della (2.4.1) vale quindi . Ciò premesso,

possiamo scrivere:

( ∑ ( )

)

∑

(2.4.2)

essendo il numero di stringhe di bit che si possono ottenere

giustapponendo parole di codice.

Se pretendiamo che il codice sia univocamente decodifi-

cabile, dovrà necessariamente essere , se così non fosse,

esisterebbero certamente almeno due sequenze di -messaggi

codificate con la stessa stringa binaria di bit.

La considerazione fatta suggerisce per la (2.4.2) la seguente

maggiorazione:

( ∑ ( )

)

∑

∑

(2.4.3)

Osserviamo che la precedente deve valere per ogni e, vi-

sto che il primo membro, se crescesse con lo farebbe esponen-

zialmente, non può essere soddisfatta a meno che non risulti

∑ ( )

(2.4.4)

La precedente va sotto il nome di Disuguaglianza di Kraft ed

in quanto condizione necessaria all’univoca decodificabilità costi-

tuisce un vincolo sulla distribuzione delle lunghezze delle parole

di un codice.

Esempio 2.1

Premesso che:un grafo è definito da una coppia d’insiemi ( );

- l’insieme è detto insieme dei vertici ;

- l’insieme è detto insieme dei lati e definisce una

relazione (detta di adiacenza) su

- a ciascun vertice di un grafo si può associare un grado definito

come il numero di lati in cui esso appare;

- un percorso di lunghezza è definito come una sequenza di

vertici , tali che ( ) , ;


- un grafo è detto connesso se comunque scelti due vertici distinti

esiste un percorso tra essi;

- un ciclo è un percorso in cui il primo e l’ultimo vertice coinci-

dono;

- un albero è un grafo connesso senza cicli;

- in un albero i nodi di grado uno sono detti foglie;

- un albero ha radice se uno dei vertici viene etichettato come tale;

- un albero binario è un albero con radice in cui nessun vertice ha

grado maggiore di tre e la radice ha grado non maggiore di due;

- per ordine di un vertice si intende la lunghezza del percorso che

lo connette alla radice, i vertici di ordine adiacenti ad un

nodo di ordine sono detti figli ed il vertice che li connette è

detto padre.

Un metodo per costruire un codice che soddisfi la regola del prefisso

è definire un albero binario avente foglie ed associare ai vertici

stringhe binarie di lunghezza pari al loro ordine secondo le seguenti

regole:

- alla radice si associa la stringa vuota

- ai vertici figli si associano stringhe distinte ottenute a partire da

quelle associate ai vertici padri, giustapponendovi rispettiva-

mente i simboli ‘0’ ed ‘1’.

Al termine della costruzione, le foglie dell’albero hanno associate pa-

role di codice che soddisfano la regola del prefisso. È utile notare che la

diseguaglianza di Kraft è soddisfatta per costruzione. In particolare lo è

come uguaglianza nel caso in cui il numero di vertici dell’albero sia

.

2.5 - Limite Inferiore per la Lunghezza di un Codice.

Forti del precedente risultato consideriamo la seguente

funzione del generico -messaggio

( ) ( )

∑ ( )

(2.5.1)

( ) soddisfa tutte le condizioni per poter essere la dmp di una

-upla di variabili aleatorie discrete che assumono valori apparte-

nenti all’alfabeto , pertanto, tenendo conto della (1.3.6), si può

scrivere:


( ) ∑ ( )

( )

∑ ( )

( )

∑ ( )

( )

∑ ( ) ( ∑ ( )

)

∑ ( ) ( )

( ∑ ( )

) ( ∑ ( )

)

(2.5.2)

La disuguaglianza di Kraft ci garantisce che il logaritmo al-

l’ultimo membro della precedente non è positivo, se ne conclude

che vale la disuguaglianza

( ) (2.5.3)

che, se la sorgente è stazionaria, comporta:

( )

(2.5.4)

La precedente ci fa capire che, non possono esistere codici

univocamente decodificabili che utilizzano un numero medio di

bit per simbolo minore dell’entropia della sorgente da codificare.

Esiste quindi un limite inferiore alla possibilità di “comprimere”,

senza perdite, le informazioni emesse dalla sorgente, a prescindere

dalla complessità del codificatore, che come s’intuisce, tipicamen-

te cresce al crescere di . La (2.5.4) ha anche il merito di chiarire

meglio l’importanza dell’entropia nell’ambito della Teoria dell’In-

formazione.

Esempio 2.2

Un algoritmo ricorsivo per la costruzione di un codice di sorgente

ottimo nel senso della lunghezza media delle parole è dovuto ad Huffman

(1952).

L’algoritmo di Huffman consiste nella costruzione ricorsiva di un

albero binario. Ricordando che l’obiettivo è ottenere la minore lunghezza

media possibile, si intuisce che a simboli meno probabili devono corri-

spondere parole di codice aventi lunghezza maggiore, ovvero foglie

aventi ordine maggiore.

Per costruire l’albero si deve disporre delle probabilità di mani-

festazione degli -messaggi . L’albero costruito dall’algoritmo di

Huffman ha vertici: i primi sono associati alle probabilità


, mentre i restanti vengono determinati ricorsivamente. A

ciascun vertice viene associata una variabile booleana che ne indica

l’utilizzo da parte dell’algoritmo.

Al passo -esimo, si procede come segue:

si scelgono tra i vertici non ancora marcati come utilizzati i due

vertici e aventi le probabilità associate minori, si marcano e

come utilizzati e si introduce un nuovo vertice avente probabilità

associata pari a si aggiungono all’insieme dei lati i due elementi

( ) e ( ).

Sostanzialmente l’algoritmo può essere riassunto come segue:

“inizialmente tutti i vertici sono orfani; a ciascun passo si scelgono i due

orfani aventi probabilità associata minima e li si dota di un vertice padre

(a sua volta orfano) avente probabilità pari alla somma delle probabilità

dei figli”.

Al termine dell’algoritmo resta un unico vertice non ancora utilizzato,

e lo si denota radice dell’albero. Una volta costruito l’albero, il codice di

Huffman è definito dalla procedura dell’Esempio 2.1.

Come esempio, consideriamo la costruzione di un codice di Huffman

per una sorgente DMS stazionaria avente alfabeto e

probabilità di emissione e .

Essendo la sorgente binaria, con il codice contiene due sole

stringhe ‘0’ ed ‘1’; la lunghezza media del codice risulta:

mentre l’entropia è data da:

( )

Con , gli M-messaggi possibili sono quattro, caratterizzati dalle

probabilità di emissione , , e ; l’albero costruito secondo l’algoritmo di Huffman è riportato in

Fig.E 2.1.

La lunghezza media del codice risulta:

( )

AA

BB

BA

AB

M-messaggio Parola di codice

AA 111

AB 110

BA 10

BB 0

1.00

0.51

0.09

0.21

0.49

0.21

0.30

Fig.E 2.1 - Albero e codice di Huffman associato al codice con M = 2


ed il numero medio di bit utilizzati per simbolo ( ),

in accordo con la (2.5.4).

2.6 - La Proprietà di Equipartizione.

Occupiamoci adesso di un’importante proprietà delle

sorgenti d’informazione.

Consideriamo una DMS stazionaria con entropia ( ) ,

fissiamo un e, nell’insieme di tutti gli -messaggi, prendia-

mo in considerazione il sottoinsieme S così definito

{ ( ( ) )

( ) ( ( ) )} (2.6.1)

dalla precedente discende innanzi tutto che:

∑ ( ( ) )

∑ ( )

(2.6.2)

quest’ultima implica che la cardinalità di S non può essere mag-

giore di ( ( ) ) quindi tutti i messaggi appartenenti ad S pos-

sono essere codificati utilizzando parole di codice di lunghezza

fissa con un numero di bit non superiore a:

( ( ) ) (2.6.3)

Tenendo conto del fatto che la sorgente è per ipotesi priva di me-

moria si può anche scrivere:

{ ( ( ) ) ∑

( )

( ( ) )}

{ ( ) ∑ ( ( ))

}

(2.6.4)

Dall’ultimo membro della precedente si può facilmente

dedurre la definizione, del complementare di S rispetto

all’insieme degli -messaggi, precisamente:

{ |∑ ( ( ))

( )| } (2.6.5)


Ci proponiamo di maggiorare la probabilità dell’evento: “la

sorgente ha emesso un messaggio appartenete a ”. A tal fine ricordiamo

che la disuguaglianza di Chebyshev garantisce che la probabilità

che una V.A. con varianza disti dal suo valore medio per più di

è non maggiore di

.

Notiamo che ∑ ( ( ))

può essere interpretata

come una V.A. ottenuta sommando le variabili aleatorie statisti-

camente indipendenti ( ( )) tutte identicamente distri-

buite. Il valor medio di ciascuna di esse vale ( ) quindi il valor

medio di vale:

(∑ ( ( ))

) ( ) (2.6.6)

Anche la varianza di è volte la varianza di ( ( )) e vale:

∑( ( ( )) ( ))

( )

(2.6.7)

In conclusione, ponendo , la probabilità che un -

messaggio appartenga ad sarà non maggiore di

( )

∑ ( ( ( )) ( )) ( ( ))

(2.6.8)

La disuguaglianza appena scritta ci dice che la probabilità

che un -messaggio non appartenga a S tende a zero al tendere

di all’infinito.

In altri termini abbiamo appena mostrato che “asintoticam-

ente” i messaggi emessi da una sorgente possono essere suddivisi

in due classi la prima contiene messaggi sostanzialmente equipro-

babili con probabilità di manifestarsi ( ) , la seconda

contenente messaggi che si presentano con probabilità prossima a

zero.


La proprietà appena descritta, che vale anche per sorgenti

dotate di memoria, va sotto il nome di proprietà di equipartizione

(equipartition property). Essa in sostanza ci dice che, pur di conside-

rare messaggi sufficientemente lunghi, il numero di messaggi di-

stinti che una sorgente emette è approssimativamente pari a

( ) che rappresenta solo una frazione degli teori-

camente generabili.

Il fatto che esista un sottoinsieme di messaggi aventi un’e-

sigua probabilità di manifestarsi può essere utilmente sfruttato nel

caso in cui si vogliano mettere a punto dei sistemi di codifica che

accettino una qualche perdita nel contenuto informativo. Si po-

trebbe ad esempio pensare di progettare un codificatore di sor-

gente che ignori i messaggi poco probabili. Ciò porterebbe a una

perdita d’informazione che potrebbe però essere trascurabile ri-

spetto a quella che si perderebbe comunque a causa ad esempio

degli errori introdotti dal sistema di trasmissione.

2.7 - Teorema sulla Codifica di una Sorgente DMS.

Abbiamo visto che la (2.5.4) impone un limite inferiore alla

lunghezza media del codice, ma, la stessa, nulla ci dice su quanto a

detto limite ci si possa avvicinare.

Per rispondere a questo quesito utilizzeremo la proprietà di

equipartizione introdotta nel paragrafo precedente al fine di co-

struire un codice univocamente decodificabile per gli M-messaggi

emessi dalla sorgente.

Fissiamo ad arbitrio un , possiamo utilizzare il primo

bit (binary digit) della parola del costruendo codice per classifi-

carla come appartenente o meno all’insieme S definito nel prece-

dente paragrafo. Osserviamo quindi che, per identificare univoca-

mente tutti gli elementi di S , sulla base della (2.6.3), saranno suf-

ficienti ulteriori S ( ( ) ) bit. Restano da codificare

gli elementi appartenenti ad . A tal fine ricordiamo che tali ele-

menti hanno una probabilità molto piccola di manifestarsi, quindi


incidono poco sulla lunghezza media del codice che è la quantità

che ci interessa limitare. Ciò premesso possiamo utilizzare per co-

dificarli un numero di bit , laddove bit

sarebbero sufficienti a codificare tutti gli M-messaggi.

In sostanza la generica parola di codice avrà lunghezza S o

, e non vi è nessuna ambiguità per il decodificatore che osser-

vando il primo bit di ogni parola saprebbe quale è la sua lunghez-

za. Ciò ovviamente è vero solo se il codificatore e il decodificatore

sono esenti da errori.

Calcoliamo adesso lunghezza media per simbolo emesso

dalla sorgente del codice che abbiamo appena costruito:

(

( ) ( )) (2.7.1)

che, tenuto conto della (2.6.8), si può maggiorare come segue:

(

( ) ( ))

(

( ))

(

)

( ( ( ) ) ) ( )

( ( ) ) ( )

( )

(2.7.2)

Si osservi che può essere scelto arbitrariamente, in parti-

colare possiamo scegliere

ottenendo:

( )

(

) (2.7.3)

Nella (2.7.3) tutti gli addendi a secondo membro eccetto il primo

tendono a zero al crescere di , possiamo quindi scriverla nella

forma:


( ) ( ) (2.7.4)

La precedente ci permette di affermare che per una DMS,

accettando una maggiore complessità di codifica/decodifica, si

può costruire un codice con un numero medio di bit per simbolo

prossimo quanto si vuole alla sua entropia.

In conclusione mettendo insieme la (2.5.3) e la (2.7.4)

abbiamo dimostrato il seguente

Teorema 2.1 Data una DMS stazionaria con entropia ( ) e comunque scelto

, esiste un intero in corrispondenza al quale si può costruire un

codice univocamente decodificabile che esibisce una lunghezza media per

simbolo di sorgente che soddisfa la seguente disuguaglianza:

( )

( ) (2.7.5)

Inoltre, qualunque sia , non è possibile costruire codici per i quali

risulti:

( ) (2.7.6)

***********

Vale la pena di osservare che il codice che abbiamo co-

struito, se da un lato c’è stato utile per ottenere la (2.7.5), dal

punto di vista pratico sarebbe difficilmente applicabile perché

presuppone la conoscenza della dmp della sorgente, dato questo

di cui in pratica difficilmente si dispone. Esistono algoritmi di

codifica che tendono al limite inferiore imposto dalla (2.7.5) pur

non presupponendo la conoscenza della dmp in parola, e che

quindi si rivelano molto più utili in pratica.

Esempio 2.3

L’algoritmo di Huffman descritto nell’Esempio 2.2 richiede la cono-

scenza a priori delle probabilità dei simboli di sorgente. Descriviamo

brevemente un possibile metodo per ottenere una versione adattativa


dell’algoritmo che presuppone solo la conoscenza della cardinalità

dell’alfabeto .

L’idea è riassumibile in due punti:

- utilizzare, invece delle probabilità di manifestazione, le fre-

quenze relative di manifestazione dei simboli di sorgente, ini-

zializzate con una distribuzione a priori nota a codificatore e

decodificatore

- non aggiornare la tabella delle frequenze relative di apparizione

dei simboli fintanto che il decodificatore non li ha potuti osser-

vare.

Fig.E 2.2 - Andamento temporale (blu), al variare di , della lunghezza media del codice prodotto dal codec adattativo di Fig.E 2.3 per la sorgente DMS dell’Esempio 2.3. In rosso l’entropia stimata in base alle frequenze

relative.

0 500 1000 1500 20000

0.5

1

1.5

2M = 1

0 200 400 600 800 10000

0.5

1

1.5

2M = 2

0 100 200 300 400 500 6000

0.5

1

1.5

2M = 3

0 100 200 300 400 5000

0.5

1

1.5

2M = 4

S Encoder

Relative

Frequency

Computer

kX

1kX

Decoder D

Relative

Frequency

Computer

kX

1kX

1z

1z

Fig.E 2.3 - Schema a blocchi di un generico codec (codificatore/decodificatore) adattativo.


Lo schema di riferimento dell’algoritmo adattativo (che è di carattere

generale) è riportato in Fig.E 2.3Si noti che così descritto, questo metodo

richiede nella peggiore delle ipotesi la ricostruzione (previa verifica di

consistenza) dell’albero di Huffman per ogni simbolo trasmesso, il che

può essere impraticabile. Inoltre, l’algoritmo adattativo così formulato è

basato sull’assunzione che le frequenze relative convergano in tempi

brevi alle probabilità di manifestazione dei simboli; per “brevi” si in-

tende rispetto al tempo durante il quale si può assumere che la sorgente

sia effettivamente stazionaria.

In Fig.E 2.2 è mostrato l’andamento temporale della lunghezza

(media) del codice per un codificatore adattativo che elabora simboli

quaternari caratterizzati dalle probabilità di manifestazione ,

, e , al variare della lunghezza degli

M-messaggi; l’entropia della sorgente è pari a ( ) .

2.8 - Codifica di Sorgenti con Memoria.

Una sorgente è detta con memoria quando la probabilità di

emissione di un simbolo dipende dalla sequenza di simboli emessa

in precedenza:

( ) ( ) (2.8.1)

Come puntualizzato al termine del capitolo precedente, per

una sorgente discreta con memoria l’entropia di un M-messaggio è

minore dell’entropia della sorgente riguardata come senza memo-

ria. Ciò implica che codificare una sorgente con memoria con

metodi che possono essere ottimi nel caso di sorgenti DMS può

risultare ben lontano dall’ottimo.

Si potrebbe osservare che la proprietà di equipartizione,

valida anche per sorgenti con memoria, permette di affermare che

la codifica senza memoria di -messaggi è, asintoticamente per

, ottima; d’altra parte l’impiego di valori di maggiori di

qualche unità è quasi sempre proibitivo.

L’approccio utilizzato in pratica per la codifica di sorgenti

con memoria consiste nell’operare una forma di pre-codifica allo

scopo di rendere il più possibile incorrelata la sorgente. Riportia-

mo di seguito alcuni esempi didattici che s’ispirano a metodi im-

piegati nella pratica.


Esempio 2.4

Nel caso di sorgenti discrete ottenute tramite campionamento di

segnali a valori discreti (si pensi ad esempio ad una scansione FAX), si

può impiegare la codifica run-length (RLE).

L’idea alla base della RLE è sostituire sequenze costituite da simboli

identici con una indicazione di quale simbolo viene ripetuto quante volte.

Ad esempio, la codifica run-length della sequenza:

A, A, A, A, A, B, B, B, B, B, B, C, C, C, C, A, A, B, B, B, B, B, C, C, C

è data da:

(A,5), (B,6), (C,4), (A,2), (B,5), (C,3).

Per valutare l’efficienza della codifica run-length si deve tenere conto

dell’overhead richiesto per codificare la lunghezza dei run. Per ottenere

qualche numero tangibile, consideriamo la piccola immagine in bianco e

nero (32 righe, 128 colonne) in Fig.E 2.4

Questa immagine, riguardata come una sequenza di simboli binari

emessi da una sorgente DMS, ha una entropia di 0.5871 bit/simbolo (578

pixel neri, 3518 pixel bianchi), ovvero un contenuto informativo stimato

di 2405 bit.

Se codificata RLE per colonne con lunghezza massima dei run pari a

511, è rappresentata da 313 run aventi una entropia stimata di 4.582

bit/run ovvero un contenuto informativo complessivo non inferiore a

1435 bit (con un guadagno potenziale del 65% rispetto alla dimensione

non codificata di 4096 bit).

Si deve però notare che la lunghezza massima dei run è un parametro

problematico da impostare, in quanto se, da una parte, incrementandolo il

numero complessivo di run diminuisce, dall’altra il numero di bit

necessario a codificare la lunghezza di un singolo run aumenta, sicché

per immagini di piccola dimensione come questa l’effettivo guadagno

può risultare marginale.

Da segnalare che per la codifica di immagini in bianco e nero (ad.

esempio FAX), esistono generalizzazioni bidimensionali della codifica

run length, che sfruttano le correlazioni esistenti tra le righe.

Esempio 2.5

Nel caso di sorgenti discrete generiche esistono molti metodi, nes-

suno dei quali ottimo. Un approccio utilizzato nella codifica di sorgente

Fig.E 2.4 - Immagine (ingrandita in modo da evidenziare i singoli pixel) per l’esempio di codifica run-length (32x128x1).


di dati correlati è quello a dizionario. Il più diffuso algoritmo di codifica

di sorgente a dizionario è il Lempel-Ziv (del 1977, LZ77), implementato

in molte utility “zip” (pkzip, winzip, infozip, gzip, compress e altre).

L’idea della codifica LZ77 è sostituire, nella sequenza originaria, a

sequenze di simboli già incontrate una indicazione di “a partire da dove”

e “per quanti simboli” è possibile copiarle. Per chiarire, consideriamo la

codifica LZ77 della sequenza dell’Esempio 2.4

(A,1,4), (B,1,5), (C,1,3), (A,11,6), (C,1,2).

Il primo blocco, (A,1,4), viene decodificato come: “dopo un simbolo

A, torna indietro di un passo e copia per quattro volte”, ovvero una

sequenza di cinque simboli A. Il secondo blocco ed il terzo blocco sono

analoghi al primo. Per comprendere come viene interpretato il quarto

blocco, notiamo che dopo i primi tre blocchi il decodificatore avrà

prodotto la sequenza:

A, A, A, A, A, B, B, B, B, B, B, C, C, C, C.

A questo punto, aggiungere un simbolo A, tornare indietro di undici

passi e copiare per sei volte corrisponde ad aggiungere la sequenza A, B,

B, B, B, B, C in coda. L’ultimo blocco è di tipo run-length come i primi

tre.

La codifica LZ77 dell’immagine in bianco e nero di Fig.E 2.4 è una

sequenza di solo 60 triplette aventi una entropia stimata di 11.52 bit

ciascuna, per un contenuto informativo complessivo non minore di 692

bit (con un guadagno potenziale dell’83% sulla dimensione non

codificata di 4096 bit).

Capitolo - 3

CANALI PRIVI DI MEMORIA

3.1 - L’Informazione Mutua.

Consideriamo un generico esperimento casuale. Abbiamo

detto che al manifestarsi di un dato evento è associata una

quantità d’informazione

( ); la stessa quantità può essere in-

terpretata come la nostra incertezza sull’evento . Ad esempio se

( ) allora sul fatto che si manifesti non abbiamo nes-

suna incertezza ed in questo caso si avrebbe

( ) nel caso

in cui ( ) fosse molto piccola avremmo una grande incertezza

sul fatto che si possa manifestare, ed acquisiremmo quindi una

grande informazione qualora si manifestasse.

Consideriamo adesso una coppia d’eventi , , il manife-

starsi di può variare la nostra incertezza su se ad esempio

il manifestarsi di rimuoverebbe tutta l’incertezza

( ) che a priori avevamo su . Se, viceversa, i due eventi

fossero statisticamente indipendenti il manifestarsi di lascereb-

be immutata l’incertezza che a priori avevamo su .

In altri termini se sapessimo che è verificato il manife-

starsi di ci fornirebbe un’informazione in genere diversa da

quella che avremmo avuto a priori (cioè senza saper nulla circa ).

In particolare l’informazione fornita a posteriori (cioè sapendo che

è verificato) dal manifestarsi di varrebbe

( ).

Si definisce informazione mutua ( ) tra due eventi, l’incer-

tezza che rimossa sull’evento per effetto del manifestarsi di

In formule:

( )

( )

( )

( )

( ) (3.1.1)


Alla luce della definizione appena data la scelta del nome

informazione mutua può apparire infelice, esso probabilmente

trae origine dal fatto che ricordando la regola di Bayes possiamo

scrivere:

( ) ( )

( ) ( )

( )

( ) ( ) (3.1.2)

Osserviamo che, nel caso in cui , ( ) varrebbe

( ) cioè ci fornisce su tutta l’informazione che ci po-

trebbe fornire stesso. cioè rimuoverebbe ogni incertezza su

. Se ( ) ( ) ( ) allora ( ) che sta a

significare che il manifestarsi di non modificherebbe la nostra

l’incertezza su .

È anche opportuno sottolineare che ( ) può assumere

anche valori negativi, ciò da conto del fatto che il manifestarsi di

potrebbe rendere molto più incerto, se non impossibile il ma-

nifestarsi di , ad esempio qualora si avrebbe

( ) ( )

( ) (3.1.3)

3.2 - Concetto di Canale.

Come già detto, un sistema di trasmissione serve a inviare

un messaggio da un emissario a un destinatario in luoghi e/o

tempi diversi. Per recapitare il messaggio, il sistema si giova di un

mezzo trasmissivo che viene abitualmente chiamato canale.

Il concetto di canale è piuttosto ampio, nel senso che esso

può includere, a seconda delle necessità, o solo il mezzo fisico, ad

esempio il solo doppino telefonico o un nastro magnetico, o an-

che tutto ciò che è compreso tra un microfono e un altoparlante.

Nel caso di un sistema di trasmissione numerico modulato

linearmente basato su di una costellazione bidimensionale, si può

pensare che il canale includa, modulatore, amplificatore RF, mez-

zo fisico, amplificatore d’ingresso, eventuale demodulatore a fre-

quenza intermedia, demodulatore, filtri adattati e campionatori. In

Canali Discreti Privi di Memoria 41

questo caso il canale accetta in ingresso un numero complesso

associato ad un punto della costellazione e fornisce in uscita un

numero complesso che in genere differisce da quello inviato per

effetto del rumore e dei disturbi introdotti dal mezzo e dagli appa-

rati. Se decidessimo di includere nel canale anche il decisore, l’u-

scita del canale sarebbe sì un punto della costellazione, ma, come

ben sappiamo, non sempre lo stesso che si era inviato.

Qui ci limitiamo a considerare canali di tipo discreto che

sono caratterizzati da un alfabeto d’ingresso e da uno d’uscita ,

legati da un mapping aleatorio.

In pratica non si lede la generalità se si pensano ingresso e

uscita come una coppia di variabili aleatorie definite sullo stesso

esperimento casuale.

Se l’alfabeto d’ingresso e quello d’uscita hanno rispettiva-

mente cardinalità ed e se e

sono i

rispettivi alfabeti, il canale è univocamente individuato quando

sono note le seguenti dmp condizionate:

( | ) ( | )

(3.2.1)

Risulta spontaneo pensare alle come agli elementi di una

matrice con un numero di righe pari alla cardinalità dell’alfa-

beto di ingresso e un numero di colonne uguale alla cardinalità di

quello d’uscita. Chiameremo matrice di transizione di canale.

Nel caso in cui l’alfabeto d’ingresso è finito e quello d’uscita

ha la potenza del continuo il canale è caratterizzato se si cono-

scono le seguenti densità di probabilità condizionate:

( | ) ( | ) (3.2.2)

Si dice che il canale è privo di memoria se, la pro-

babilità di rivelare un data sequenza di simboli d’uscita in

corrispondenza ad un dato -messaggio di ingresso è data da


( [ ] | [ ]) ∏ ( )

(3.2.3)

se l’alfabeto d’uscita è finito.

Ovvero la densità di probabilità della sequenza d’uscita

condizionata ad una sequenza d’ingresso è data da:

( )( ) ∏ ( | )

(3.2.4)

nel caso in cui l’alfabeto d’uscita ha la potenza del continuo.

Se in ingresso al canale è connessa una sorgente che emette

simboli compatibili con il canale, e se sono note le probabilità d’e-

missione ( ) di ciascun simbolo dell’alfabeto di sorgente

dalle (3.2.1) e (3.2.2) possiamo dedurre la distribuzione di massa

di probabilità dell’alfabeto d’uscita del canale, cioè dei simboli

:

( ) ∑

(3.2.5)

ovvero la densità di probabilità della V.A. d’uscita:

( ) ∑ ( )

(3.2.6)

Consideriamo un canale discreto e privo di memoria (DMC

- Discrete Memoryless Channel).

Se in uscita rilevassimo il simbolo l’incertezza residua

sull’emissione del generico simbolo d’ingresso varrebbe:

( )

(3.2.7)

che ricordando la (3.1.2) è uguale a

( )

( )

(3.2.8)


mediando su tutte le possibili coppie ingresso uscita otteniamo

una misura dell’incertezza che mediamente rimane sul simbolo in

ingresso dopo aver osservato il corrispondente simbolo in uscita:

( ) ∑ ∑ ( ) ( )

( )

∑ ∑ ( ) ( | )

( )

∑ ∑ ( )

(3.2.9)

Abbiamo appena definito l’informazione mutua media. Sostituendo

nella precedente la (3.2.5) otteniamo ancora:

( ) ∑ ∑

∑

(3.2.10)

Sebbene l’informazione mutua (3.2.8) possa assumere an-

che valori negativi così non è per l’informazione mutua media

(3.2.9), risulta infatti:

( )

∑ ∑

∑ ∑ (

)

∑ ∑ ( )

[∑ ∑

∑ ∑ ( )

]

(3.2.11)

3.3 - L’equivocazione.

La ( ) si può anche scrivere:


( ) ∑ ∑ ( ) ( )

( )

∑ ( )

( )

∑ ∑ ( )

( )

(3.3.1)

Il primo addendo ad ultimo membro della precedente rappresenta

l’entropia della sorgente ( ), il secondo la cosiddetta equivocazione

( ) ∑ ∑ ( )

( ) . Si costata che ( )

Utilizzando l’equivocazione possiamo scrivere:

( ) ( ) ( ) ( ) (3.3.2)

La ( ) deve il suo nome al fatto che essa rappresenta la

quantità l’informazione che viene mediamente dispersa dal canale.

Essa risulta infatti nulla nel caso di canale ideale, cioè nel caso in

cui il simbolo in uscita dal canale determina con certezza il sim-

bolo emesso dalla sorgente. In questo caso avremmo cioè

( ) ( ). Nel caso di canale inutile, cioè nel caso in cui l’u-

scita del canale sia statisticamente indipendente dal suo ingresso,

avremmo ( ) ( ) e, conseguentemente, ( ) . Tutta

l’informazione della sorgente verrebbe pertanto dispersa dal

canale.

3.4 - La capacità di canale

Osservando la (3.2.10) ci rendiamo conto che l’informa-

zione mutua non dipende solo dal canale, ma anche dalla dmp

della sorgente. Al fine di fornire una grandezza caratteristica del

solo canale si procede alla ricerca del massimo della (3.2.10) al va-

riare delle distribuzioni di massa di probabilità

della sorgente. Otteniamo così la capacità di canale:

( )

(3.4.1)


che, come vedremo, gioca un ruolo fondamentale nel dimensiona-

mento di un sistema di trasmissione. La ricerca del suddetto

massimo, dato il tipo di dipendenza da non è in genere sem-

plice.

Ricordando la (1.3.7) e la (3.3.2) per un canale con alfabeto

di ingresso di cardinalità possiamo scrivere:

( ) ( ) (3.4.2)

La precedente vale per ogni possibile informazione mutua, quindi

anche per quella in corrispondenza alla quale si raggiunge la capa-

cità del canale. Ne concludiamo che la capacità di un canale dis-

creto è limitata superiormente dal logaritmo della cardinalità del-

l’alfabeto d’ingresso.

3.5 - Il Canale Simmetrico Binario.

Si consideri un canale

schematizzato in Fig. 3.1 che

accetta ed emette simboli ap-

partenenti a un alfabeto bi-

nario costituiti cioè rispetti-

vamente da due soli simboli,

, .

La matrice di transizio-

ne ad esso associata è quindi

una che se risulta è simmetrica. La matrice di

transizione di canale in questo caso vale:

|

| (3.5.1)

Un canale caratterizzato dalla matrice appena scritta è detto Canale

simmetrico binario (BSC, Binary Simmetric Channel).

Se il canale è connesso a una sorgente che emette simboli

con probabilità , risulta:

Fig. 3.1 - Canale Simmetrico Binario


( ) ( ) ( )( )

(3.5.2)

L’informazione mutua media di un BSC varrà quindi:

( ) ∑ ∑

∑ ∑

∑ ∑

∑ ∑

∑

( ) ( ) ( )

( )( ) ( ) ∑

( ) ( ) ∑

( ) ( )

(3.5.3)

Dalla precedente si evince che la

capacità di canale si ottiene massimiz-

zando l’entropia dell’uscita ( ), che,

come già visto, raggiunge il suo mas-

simo quando i simboli d’uscita sono e-

quiprobabili, cosa che, data la simme-

tria del canale, avviene quando lo sono

quelli emessi dalla sorgente.

Concludiamo che la capacità di un

BSC vale:

( ) (3.5.4)

(vedi Fig. 3.2).

È interessante osservare che

implicherebbe che

da conto del fatto che in questo caso il canale sarebbe ovviamente

del tutto inutile ai fini del trasferimento d’informazione.

Fig. 3.2 - Capacità del canale sim-metrico binario


3.6 - Capacità del Canale AWGN a Banda Limitata.

Consideriamo adesso il canale

con ingresso e uscita ad alfabeto

continuo rappresentato in Fig. 3.3

esso aggiunge alla variabile aleatoria

generata dalla sorgente un disturbo

costituito da una variabile aleatoria

, Gaussiana a media nulla e varianza , statisticamente indipen-

dente dalla variabile aleatoria in ingresso.

L’informazione mutua associata al canale in questione è da-

ta da:

( ) ( ) ( )

∫ ( )

( )

∫ ∫ ( )

( )

∫ ( )

( )

∫ ( )∫ ( )

( )

(3.6.1)

Osserviamo che ( )

√

( )

in quanto differisce da

per il solo disturbo che abbiamo detto essere Gaussiano. So-

stituendo nella (3.6.1) e ricordando la (1.6.3) otteniamo:

( ) ∫ ( )

( )

∫ ( ) (

)

∫ ( )

( )

(

)

(3.6.2)

Per ottenere la capacità del canale dobbiamo massimizzare

l’integrale ad ultimo membro, cioè l’entropia dell’uscita. Sappiamo

(vedi § 1.6 - ) che il massimo dell’entropia, a parità di varianza, si

ottiene da una sorgente Gaussiana.

SX

n

Y

Fig. 3.3 - Canale Gaussiano


Affinché la ( ) sia Gaussiana, tale deve essere la variabile

aleatoria in ingresso Indicata con la sua varianza, in virtù

della supposta indipendenza tra ed si ha:

(3.6.3)

La capacità del canale Gaussiano è quindi data da:

( )

( )

(

)

(

)

(

)

(3.6.4)

Consideriamo adesso il ca-

nale AWGN (Addittive White

Gaussian Noise) (vedi Fig. 3.4)

cioè un canale con ingresso e u-

scita a tempo continuo che agisce

sul segnale d’ingresso sommando

a quest’ultimo un segnale stazionario Gaussiano a media nulla e

densità spettrale di potenza bilatera costante pari ad

Come sappiamo ogni sistema di trasmissione è affetto quan-

tomeno dal rumore termico che si può modellare proprio con un

processo Gaussiano bianco.

Ogni sistema d’interesse pratico tratta di fatto segnali a banda

limitata. Pertanto, per ridurre la potenza di rumore introdotta il

canale viene sempre limitato in banda tramite un apposito filtro

passabasso o passabanda posto tipicamente in ingresso al ricevito-

re. Se indichiamo con la banda del segnale sappiamo che esso

può essere ricostruito a partire dai suoi campioni purché ne ven-

gano prelevati almeno al secondo. Il canale AWGN equivale

quindi a un canale Gaussiano utilizzato con la stessa cadenza. La

varianza dei campioni del segnale coinciderà con la potenza media

del segnale, e quella del rumore con la frazione di potenza di

quest’ultimo contenuta nella banda del segnale risulta quindi:

Fig. 3.4 - Canale AWGN


( )

(3.6.5)

dove ( ) rappresenta la potenza del segnale e indica la densi-

tà spettrale di potenza monolatera del rumore. Sostituendo nella

(3.6.4) otteniamo:

(

( )

) (3.6.6)

La precedente indica la capacità del canale AWGN limitato

in banda per uso del canale, espressa quindi in bit. In pratica è più

utile esprimere la capacità in termini di bit al secondo, in questo

caso a partire dalla precedente è sufficiente osservare che il canale

viene utilizzato volte al secondo. La capacità espressa in

del canale in questione vale quindi:

( ( )

) (3.6.7)

Osserviamo che nella (3.6.7) appare il rapporto segnale ru-

more. Essa ci dice che per aumentare la capacità di un canale a

tempo continuo possiamo aumentarne il rapporto segnale rumore

o aumentarne la banda. Occorre però tener presente che un

aumento del rapporto segnale rumore comporta sì un aumento

della capacità, ma detto aumento non segue una legge lineare

bensì una legge logaritmica. In sostanza, affinché la capacità del

canale aumenti di un bit al secondo, la potenza del segnale do-

vrebbe approssimativamente raddoppiare quindi parrebbe molto

più efficace agire sulla banda del segnale, osserviamo però che, a

parità di potenza del segnale, un aumento della banda comporta

un deterioramento del rapporto segnale rumore. Per meglio capire

come tali effetti si combinino, mantenendo costante la potenza

del segnale e la densità spettrale monolatera del rumore, fac-

ciamo tendere nella precedente la banda ad infinito. Otteniamo:


( ( )

)

( ( )

)

( )

( )

(3.6.8)

La precedente ci fa capire che un aumento della banda a parità di

potenza del segnale comporta oltre certi limiti effetti trascurabili

sulla capacità del canale, viceversa, a parità di banda aumentando

la potenza trasmessa si può aumentare, almeno in linea di princi-

pio, la capacità del canale indefinitamente. Ciò, come abbiamo

mostrato nel § - 3.4 - non accade nei canale con alfabeto di

ingresso e di uscita finiti la cui capacità è limitata dal logaritmo

della cardinalità dell’alfabeto di ingresso.

3.7 - Informazione Mutua tra -messaggi.

Consideriamo un DMC. Utilizzando le dmp congiunte,

possiamo facilmente definire l’informazione mutua tra -messag-

gi in ingresso e in uscita.

( ) ∑ ∑ ( )

( )

( )

(3.7.1)

la precedente può anche essere riscritta:

( ) ∑ ( )

( )

∑ ∑ ( )

( )

(3.7.2)

e, ricordando la (1.3.6), può essere maggiorata come segue:

( ) ∑ ( )

∏ ( )

∑ ∑ ( )

( )

∑ ∑ ( ) ( ) ∏ ( )

( )

∑ ∑ ∑ ( ) ( ) ( )

( )

∑ ( )

(3.7.3)


L’uguaglianza vale se i simboli d’uscita sono mutuamente statisti-

camente indipendenti perché in questo caso si avrebbe ( )

∏ ( )

. Questa condizione è certamente soddisfatta se la

sorgente è priva di memoria.

Se la sorgente ed il canale sono stazionari tenuto conto del-

la (3.4.1) possiamo ulteriormente scrivere:

( ) ∑ ( )

( ) (3.7.4)

3.8 - Canali in Cascata.

Consideriamo adesso il caso di due canali in cascata (vedi

Fig. 3.5). Supponiamo che l’alfabeto d’uscita del primo canale

coincida con quello d’ingresso del secondo, e che l’uscita di cia-

scun canale dipenda esclusivamente dal suo ingresso. Ciò significa

che

( ) ( ) (3.8.1)

Facendo sempre riferimento alla figura, consideriamo la dif-

ferenza tra le informazioni mutue ( )ed ( ). Si ha:

( ) ( ) ∑ ( ) ( )

( )

∑ ( ) ( )

( )

∑ ( ) ( ) ( )

( ) ( )

(3.8.2)

Fig. 3.5 - Canali in cascata


∑ ( ) (

( ) ( )

( ) ( ) )

(∑

( ) ( ) ( )

( ) ( )

∑ ( )

)

(∑

( ) ( ) ( ) ( )

( ) ( )

)

(∑

( ) ( ) ( )

( )

)

(∑ ( ) ( ) ( )

)

(∑ ( )∑ ( )

)

(∑ ( )

)

In definitiva abbiamo mostrato che se si collegano due, o,

ovviamente, più canali in cascata l’informazione mutua tra ingres-

so e uscita può solo diminuire. Il risultato appena ottenuto vale

anche nel caso in cui si colleghino in cascata al canale dei sistemi

deterministici, come ad esempio un codificatore in ingresso e\o

un decodificatore d’uscita.

Consideriamo (vedi Fig. 3.6) il caso di una DMS connessa a

un codificatore che opera in modo deterministico su M-messaggi

emessi dalla sorgente per generare sequenze di lettere compati-

bili con un DMC con alfabeti d’ingresso e d’uscita della stessa car-

Fig. 3.6

Codificatore Canale DecodificatoreS

1 MX XX 1 MV VV 1 LY YY 1 LZ ZZ


dinalità . L’uscita del canale è poi connessa a un decodificatore

che opera in modo deterministico sugli -messaggi emessi dal

canale per “cercare” di ricostruire gli -messaggi emessi dalla sor-

gente. Ovviamente una condizione sufficiente affinché in uscita

venga ricostruito correttamente il messaggio è che il canale non

abbia introdotto disturbi tali da indurre il decodificatore in errore.

Assumiamo inoltre che le durate dell’ -messaggio emesso

dalla sorgente e del corrispondente -messaggio in uscita al codifi-

catore siano uguali, pertanto se la sorgente emette lettere con una

cadenza regolare la cadenza dei simboli in ingresso al canale

sarà data da:

(3.8.3)

Con riferimento alla Fig. 3.6 considerando l’informazione

mutua ( ), tenuto conto della (3.8.2) possiamo scrivere:

( ) ( ) ( ) (3.8.4)

dove è la capacità relativa ad una coppia di simboli ingres-

so/uscita del canale.

3.9 - L’Inverso del Teorema della Codifica di Canale

Il nostro obiettivo nella progettazione di un sistema di tra-

smissione è ottenere la minore probabilità d’errore compatibil-

mente con dei prefissati vincoli di potenza impiegabile e/o di

banda, senza tralasciare ovviamente la complessità del sistema

che, anche quando non si scontra con barriere tecnologiche, ha

comunque un impatto sui costi.

Facendo sempre riferimento alla Fig. 3.6 considerando ad

esempio la -esima lettera dell’ -messaggio emesso dalla sorgente,

il sistema commette un errore se la -esima lettera del corrispon-

dente -messaggio in uscita dal decodificatore non coincide con

quella emessa.


La probabilità che il sistema commetta un errore sulla -

esima lettera del messaggio è quindi uguale alla ( ), che, in

termini della dmp congiunta delle variabili vale:

∑

( )

(3.9.1)

La probabilità d’errore appena calcolata dipende in genere

dall’indice . Se volessimo farci un’idea della probabilità d’errore

media, , su un generico simbolo dell’ -messaggio potremmo

calcolare la media aritmetica delle ottenendo:

∑

(3.9.2)

Consideriamo la catena di disuguaglianze:

( ) ( )

∑ ( )

( )

∑ ∑ ( ) ( )

( )

∑ ∑ ( )

( )

∑ ( ( ) ∑ ( )

( )

)

∑

(

( ) ∑ ( )

∏ ( | )

)

∑ ∑ ∑ ( )

( | )

∑ ∑ ∑ ( )

( | )

(3.9.3)

Il nostro scopo è quello di esplicitare il legame tra le gran-

dezze associate all’informazione e la probabilità d’errore espressa


dalla (3.9.1), appare pertanto opportuno riscrivere la (3.9.3) nella

forma:

( ) ( )

∑

(

∑ ( )

( )

∑ ( )

( )

)

(3.9.4)

Introducendo la probabilità di corretta decisione

sul -esimo simbolo possiamo maggiorare la seconda somma-

toria in parentesi nella precedente come segue:

∑ ( )

( | )

∑ ( )

( | )

∑ ( )

( | )

∑ ( )

∑ ( ) (

( ) )

∑( ( ) ( ))

( )

( )

(3.9.5)

Procedendo in modo analogo sulla prima sommatoria in

parentesi nella (3.9.4) si ottiene anche:

∑ ( )

( | )

∑ ( ) ( )

( | )( )

(3.9.6)


∑ ( )

( | )( )

∑ ( ) ( )

∑ ( ) (

( | )( ) )

( )

(

∑ ( )

( | )( )

)

( )

(

∑ ( ) ∑

( )

)

( )

( )

(ricordiamo che rappresenta la cardinalità dell’alfabeto ).

Tenuto conto delle (3.9.5) e (3.9.6) il primo membro della

(3.9.4) può essere ulteriormente maggiorato:

( ) ( ) ∑[ ( )

( )

]

∑[ ( )

( )

]

∑ ( ) ( )

( ) ∑ ( )

(3.9.7)


Nella precedente ( ) può essere interpretata come l’entropia di

una sorgente binaria con probabilità e .

Ricordando la (1.3.6) possiamo ancora scrivere:

( ) ( )

( )

∑[

( )

]

( )

( )

( ) ( )

(3.9.8)

Sfruttando il fatto che, per ipotesi, la sorgente è priva di

memoria e tenendo in conto la (3.8.4) abbiamo ancora:

( ) ( ) ( ) ( ) ( ) ( )

( ) (3.9.9)

che, in virtù della (3.8.3), conduce alla:

( ) ( ) ( )

( )

(3.9.10)

Per assegnata cardinalità dell’alfabeto di sorgente possiamo

tracciare il grafico della funzione: ( ) ( ) ( ).

Come si può notare (vedi Fig. 3.7) la ( ) pertanto la

limitazione imposta dalla (3.9.10), che per comodità riscriviamo

nella forma:

( ) ( )

(3.9.11)

non avrà alcun effetto fintanto che risulta ( )

o, che è

lo stesso, quando

( )

(3.9.12)


cioè fintantoché l’entropia

della sorgente espressa in bit

al secondo si mantiene mi-

nore della capacità di canale,

anch’essa espressa in bit al

secondo.

Quando viceversa la

(3.9.12) non è soddisfatta la

(3.9.11) pone un limite infe-

riore alla probabilità d’errore

ottenibile; saranno compati-

bili con la (3.9.11) solo va-

lori di che fanno si che il valore assunto dalla ( ) resti al di

sopra della quantità ( )

.

Nel piano di Fig. 3.7, ( )

è una retta parallela all’asse

delle ascisse. Saranno dunque compatibili con la (3.9.11) soltanto

valori di probabilità d’errore che restino alla destra dell’ascissa

dell’intersezione di detta retta con la curva ( ).

Quello che abbiamo appena dimostrato è noto come: inverso

del teorema della codifica di canale.

Teorema 3.1 Non è possibile ottenere una probabilità d’errore piccola a piacere

all’uscita di un canale che ha una capacità

[

] se quest’ultima è minore

dell’entropia (espressa in [

]) della sorgente ad esso connessa.

**********

Purtroppo il teorema appena enunciato nulla ci dice circa la

probabilità di errore effettivamente ottenibile nel caso in cui la ca-

pacità del canale sia maggiore dell’entropia della sorgente.

Fig. 3.7 - ( ) ( ) ( )

Pe

eF P

1N

N

logN

1


3.10 - Il piano di Shannon

Riprendiamo in considerazione il canale AWGN, abbiamo

calcolato la sua capacità ( ( )

) [

].

Alla luce del teorema appena dimostrato l’entropia di una

sorgente ad esso connessa dovrà essere inferiore a tale capacità se

non vogliamo porre un limite inferiore alla probabilità d’errore ot-

tenibile. Dovremo quindi avere

( )

(

( )

) (3.10.1)

Il primo membro può essere interpretato come il numero medio

di bit che la sorgente emette ogni secondo, lo chiameremo velocità

di informazione . Detto il tempo impiegato dalla sorgente per

emettere un bit di informazione avremo:

(3.10.2)

Sostituendo nella (3.10.1) abbiamo:

(

( )

) (3.10.3)

Vogliamo utilizzare quest’ultima per confrontare l’efficienza di

sistemi di trasmissione numerica diversi. È utile a tal fine fare

riferimento all’energia ( ) che il sistema di trasmissione

utilizzato mediamente assegna ad ogni bit. Utilizzando la (3.10.2)

otteniamo:

(

)

(3.10.4)


Il rapporto

prende il nome di efficienza spettrale del sistema di

trasmissione, le sue dimensioni sono [

⁄ ] L’efficienza spettrale

ci da un’idea di come il sistema di trasmissione utilizzi la banda di

cui dispone. Tanto maggiore è tale rapporto tanto più efficace-

mente sarà utilizzata la banda occupata del segnale trasmesso.

La (3.10.4) pone in sostanza un limite inferiore al rapporto

tra l’energia media per bit e la densità spettrale monolatera del ru-

more per data ef-

ficienza spettrale

(vedi Fig. 3.8).

Ci domandia-

mo quale sia il

minimo valore di

che rispetti la

(3.10.4). A tal fine

notiamo che il se-

condo membro

della (3.10.4) cresce al crescere dell’efficienza spettrale. Il suo mi-

nimo verrà quindi raggiunto all’estremo inferiore del suo insieme

di definizione, quindi per

, o, che è lo stesso, per ot-

teniamo:

(3.10.5)

Possiamo dunque affermare sulla base del Teorema 3.1, che

non è possibile trasmettere con probabilità d’errore piccola a

piacere su un canale AWGN se risulta

Fig. 3.8 – Piano di Shannon.

0

bE

dBN

bR

B-1.6

Capitolo - 4

CENNI DI TRASMISSIONE NUMERICA

4.1 - Scenario di Riferimento.

Al fine di introdurre il teorema di Shannon sulla codifica di

canale, è opportuno introdurre alcuni concetti di trasmissione

numerica.

Come schema di principio del nostro sistema consideriamo

una sorgente che emette lettere appartenenti ad un alfabeto

di cardinalità finita N con una cadenza di lettere al secondo. La

suddetta sorgente è connessa a un codificatore di sorgente che

ogni secondi emette un -messaggio ( ) (

) che potremo pensare come il risultato di un

esperimento casuale . ( ) piloterà un codificatore di canale.

Il codificatore di canale, o modulatore, ha il compito di

associare ad ogni ( ) un segnale ( ) ad energia finita,

individuato da una funzione reale ( )( ), di durata non maggiore

di , che verrà inviato sul canale, che qui supporremo AWGN,

cioè un canale che si limita a sommare al segnale un processo

stazionario Gaussiano bianco ( ), con densità spettrale di poten-

za bilatera costante , o, che è lo stesso, con funzione di autocor-

relazione ( ) ( ).

Il ricevitore è chiamato, a fornire una stima dell’ -

messaggio trasmesso, basandosi sul segnale ricevuto e, ove pos-

sibile, sulla conoscenza della statistica di sorgente.

4.2 - Struttura del modulatore e del codificatore di sorgente

Il set di segnali utilizzato dal codificatore di canale

sopra citato ha cardinalità finita. Esso sarà pertanto contenuto in

un sottospazio S di dimensione dello spazio dei segnali a

energia finita.


Tramite la procedura di ortonormalizzazione di Gram-

Smith potremo costruire quindi una base ortonormale per

S . Ogni segnale emesso dal modulatore si può quindi esprimere

nella forma:

∑

(4.2.1)

La precedente suggerisce anche uno schema di principio

per il codificatore di sorgente che in sostanza associa a ogni se-

quenza di lettere emesse dalla sorgente il vettore

che consente al codificatore di canale di gene-

rare a sua volta tramite la (4.2.1) il segnale da inviare sul ca-

nale.

4.3 - Struttura del Ricevitore.

Trascurando il ritardo introdotto dal canale, nell’intervallo

), il ricevitore vede al suo ingresso il segnale

(4.3.1)

a energia finita che possiamo pensare come una manifestazione di

un segnale aleatorio .

Il segnale ricevuto può essere scomposto in due segnali: il

primo, S , appartenente al sottospazio S il secondo, ,

ortogonale a detto sottospazio.

In particolare avremo

∑

(4.3.2)

dove

∫ ( ( ) ( )) ( )

(4.3.3)

Teniamo presente che tutte le funzioni in gioco sono reali

e, a parte il rumore, nulle al di fuori dell’intervallo , quindi


tali sono anche le funzioni che rappresentano i componenti della

base ortonormale utilizzata. La (4.3.3) esprime pertanto il

prodotto scalare tra il segnale ricevuto e l’ -esimo elemento .

Le sono variabili aleatorie Gaussiane a media nulla con

varianza , l’ortonormalità della base garantisce anche che

esse sono mutuamente statisticamente indipendenti. Osserviamo

che il segnale S non contiene nessuna informazione cir-

ca il segnale trasmesso in quanto non appartiene per costruzione

allo spazio S dei segnali trasmessi. La nostra strategia di decisio-

ne si può quindi basare esclusivamente su S , o, che è lo stesso,

sul vettore delle sue componenti rispetto alla base .

In sostanza il vettore costituisce la cosiddetta statistica suf-

ficiente su cui deve operare il ricevitore per fornire una stima del

messaggio trasmesso.

Possiamo pensare il ricevitore costituito da due sistemi in

cascata, un demodulatore che ha il compito di calcolare il vettore

ed un decisore che sulla base di quest’ultimo provvede a stimare

il messaggio trasmesso.

In pratica si può pensare al vettore come alla realizzazio-

ne di un vettore di variabili aleatorie definito sull’esperimento

casuale innescato dall’emissione di un messaggio e dal suo invio

sul canale AWGN.

4.4 - La Regola di Decisione Ottima.

Vogliamo che la strategia seguita dal ricevitore nel suo com-

plesso conduca alla minima probabilità d’errore media. In altri ter-

mini vogliamo che sia minima la probabilità di prendere decisioni

sbagliate sul messaggio trasmesso, noto il segnale ricevuto e la

probabilità di emissione di ciascun messaggio.

Ovviamente la minimizzazione della probabilità d’errore

equivale alla massimizzazione della probabilità di corretta decisio-

ne. La regola di decisione ottima sarà quindi quella che ci fa sce-

gliere per il messaggio se risulta:


( | ) ( | ) (4.4.1)

La regola di decisione appena descritta si esprime sintetica-

mente scrivendo:

( )

(4.4.2)

Nell’ipotesi, in questo contesto remota, in cui due o più messaggi

massimizzino la precedente sceglieremo a caso tra essi.

Quando si adotta la regola di decisione (4.4.2) si sta

applicando il criterio della massima probabilità a posteriori (MAP

Maximum A posteriori Probability).

4.5 - Il Criterio della Massima Verosimiglianza.

Detto un intorno di e ( ) la sua misura possiamo

scrivere:

( )

( ) ( )

(4.5.1)

indicando con ( ) la densità di probabilità di , la probabilità

che vale ∫ ( )

Scegliendo opportunamente e in

.possiamo ulteriormente elaborare la (4.5.1) come segue:

( ) ( )

( )

( )

( ) ∫ ( )

∫ ( )

( )

∫ ( )

( )

( ) ( )

( )

( ) ( ) ( )

( ) ( )

( ) ( )

( )

(4.5.2)

sostituendo la (4.5.2) nella (4.4.2) otteniamo:


{ ( ) ( )

( )} (4.5.3)

Appare chiaro che la densità di probabilità marginale di al de-

nominatore della precedente non ha alcuna influenza sull’argo-

mento che lo rende massimo, pertanto possiamo ulteriormente

scrivere:

( ) ( )

(4.5.4)

4.6 - Funzioni di Verosimiglianza.

Un’ulteriore semplificazione della (4.5.3), si ottiene infine se

i messaggi sono tutti equiprobabili. In questo caso, sem-

plificando ulteriormente la notazione, ponendo cioè (

) ( ), la regola di decisione ottima diventa:

decidi per se:

( )

(4.6.1)

La densità di probabilità ( ) prende il nome di funzio-

ne di verosimiglianza. Essa, come si può notare, dipende sostanzial-

mente dal canale, che in questo caso pensiamo costituito dalla

cascata del modulatore, del canale AWGN e del demodulatore.

Un ricevitore che adotta la regola di decisione (4.6.1) appli-

ca il criterio della Massima Verosimiglianza MV, o ML (Maximum

Likelihood), se si preferisce l’acronimo inglese.

È opportuno precisare che il criterio MV viene di regola

adottato, anche quando la statistica della sorgente non è nota, in

questo caso il criterio non è ottimo, non conduce cioè alla minima

probabilità d’errore media, ma spesso non si può fare altrimenti

non conoscendo la statistica della sorgente, in ogni caso, in gene-

re, la perdita in termini di prestazioni adottando il criterio MV

anziché il MAP è accettabile.


4.7 - Le Regioni di Decisione.

Ricordiamo che ad ogni messaggio corrisponde trami-

te la (4.2.1) un punto nello spazio S . Quindi, se è stato tra-

smesso , all’uscita del demodulatore sarà presente il vettore

, dove è la realizzazione di un vet-

tore di variabili aleatorie Gaussiane a media nulla e matrice di co-

varianza cioè di variabili tra loro mutuamente statisticamente

indipendenti, ne segue che , per fissato , è anch’esso un

vettore di variabili aleatorie Gaussiane mutuamente indipendenti

con matrice di covarianza e media .

Si ha pertanto:

( | ) ∏

√

(

)

( )

∏

(

)

( )

∑ (

)

( )

(4.7.1)

ad ogni si può quindi associare l’insieme dei punti di S

( ) ( ) (4.7.2)

che è denominato regione di decisione di .

Se abbiamo cura di assegnare a caso all’una o all’altra regio-

ne i punti di S che si trovano al confine tra due o più regioni di

decisione, ci si convince facilmente che

∪

(4.7.3)

Per il canale AWGN possiamo ancora scrivere:

{ ( )

‖ ‖

( )

‖ ‖

}

{ }

(4.7.4)


dalla precedente s’intuisce facilmente che le frontiere delle regioni

di decisione sono iperpiani di S , e che la probabilità che cada

sulla frontiera di una regione di decisione è in questo caso nulla,

essendo nulla la misura di tali frontiere.

Il concetto di regione di decisione è applicabile anche in un

contesto più generale, basandosi direttamente sulla (4.5.3) nel caso

di messaggi non equiprobabili.

Anche nel caso in cui lo spazio d’osservazione S sia dis-

creto si possono definire le regioni di decisione, tenendo però

presente che tutte le ddp che compaiono nelle (4.5.3) e (4.6.1)

vanno intese come dmp e che, in questo caso, l’eventualità che il

vettore cada su un punto di S appartenente alla frontiera di una

regione di decisione può essere diversa da zero.

Indichiamo con la probabilità che il ricevitore stimi

in modo errato il messaggio atteso che sia stato trasmesso il

messaggio . Detto il complementare di rispetto allo

spazio di osservazione S , ( ) si potrà esprimere come segue:

( ) ( ( )) (4.7.5)

La probabilità d’errore media del sistema sarà espressa dalla media

statistica delle ( ). Avremo quindi:

∑ ( ) ( )

(4.7.6)

che nel caso di equiprobabilità dei messaggi trasmessi varrà:

∑ ( )

(4.7.7)

Sebbene la precedente sia concettualmente semplice, calco-

larne il valore può essere complicato. La sua valutazione com-

porta generalmente il calcolo d’integrali su domini multidimensio-


nali che difficilmente si risolvono in forma chiusa, e che anche ap-

procciati per via numerica possono presentare delle criticità.

È pertanto utile, in generale, e in particolare per i nostri

scopi, introdurre dei metodi che permettano di maggiorare la pro-

babilità d’errore:

4.8 - L’Union Bound.

L’union bound è una maggiorazione della che si basa sul

fatto che la probabilità dell’unione di due eventi è minore o uguale

della somma delle probabilità di ciascuno di essi.

In particolare si osservi che se il decisore dovesse scegliere

soltanto tra due alternative, ad esempio tra il messaggio e il

messaggio , vi sarebbero solo due regioni di decisione quella

associata a e la sua complementare rispetto a S ,

.

Ovviamente , risulta inoltre:

⋂

⋃

(4.8.1)

avremo pertanto:

( ∪

)

∑ ( )

(4.8.2)

Nel caso in esame:

{ } (4.8.3)

la ( ) è data da:


( )

∫ ( )

∫ ( )

∏

(

)

(4.8.4)

Al fine di calcolare la (4.8.4) è utile riformulare la disugua-

glianza che definisce la nel modo seguente:

( )

∑(

)

(4.8.5)

Osserviamo che ∑ (

)

può interpretarsi

come il valore assunto da una variabile aleatoria ottenuta combi-

nando linearmente le componenti di che, se è stato trasmesso

( ) , costituiscono una -upla di variabili aleatorie Gaussiane

statisticamente indipendenti. è quindi una variabile aleatoria

Gaussiana con valor medio:

∑(

)

(4.8.6)

e varianza:

∑(

)

(4.8.7)

Ricordando che ( )

√ ∫

potremo scrivere:

( | ) ( ‖ ‖

‖ ‖

) (4.8.8)


√

∫

( )

‖ ‖ ‖ ‖

( )

√ ∫

(

)

(

√ ( ) ( ) )

(

√ )

(

√ )

L’ultimo membro della precedente può essere sostituito

nella (4.8.2) che tenuto conto della (4.7.6) e dell’ipotesi di equipro-

babilità dei simboli trasmissibili, ci permette di scrivere:

∑ ( ) ( )

∑ ( ) ∑ (‖ ‖

√ )

( )

∑ (

√ )

(4.8.9)

4.9 - Bound di Bhattacharrya.

L’union bound può essere applicato anche al caso in cui lo

spazio di osservazione sia discreto. Consideriamo ad esempio il

caso di una sorgente binaria priva di memoria che emetta una

parola di bit. Vogliamo trasmettere la parola in questione

utilizzando un BSC volte con . Il compito del codificatore


di canale consiste quindi nell’associare a ciascuno dei possibili

messaggi di sorgente una tra le possibili parole da affidare al

canale. Chiameremo codice il sottoinsieme delle parole scelte.

Osserviamo che per effetto del canale la parola ricevuta

potrebbe non appartenere al codice, ma in ogni caso sarebbe una

tra le . In sostanza lo spazio d’osservazione è in questo caso

finito.

La probabilità ( ) che venga rivelata la parola quan-

do è stata trasmessa la parola di codice è data da

( ) ( ) ( ) (

)

(4.9.1)

in cui rappresenta il numero di simboli in cui differisce da

e la probabilità di crossover del BSC. Osserviamo che, se

,

, ( ) è quindi una funzione decrescente di che, co-

me vedremo in seguito, è detta distanza di Hamming. Ciò ci permet-

te di associare a ogni parola di codice una regione di decisione,

che conterrà i punti dello spazio d’osservazione, cioè le parole di

bit aventi da essa una distanza minore rispetto a quella che

hanno dalle altre parole di codice, convenendo di assegnare in

modo puramente casuale a una sola delle regioni interessate i pun-

ti dello spazio d’osservazione che dovessero trovarsi a uguale di-

stanza tra due o più parole di codice.

Ciò premesso, il calcolo della probabilità d’errore condizio-

nata all’emissione di una data parola di codice vale:

∑ ( )

(4.9.2)

e la probabilità d’errore media:

∑ ( ) ∑ ( )

(4.9.3)


dove ( ) rappresenta la probabilità di emissione della parola

da parte del codificatore di canale, che equivale, essendo il

codificatore deterministico, a quella di emissione della corrispon-

dente parola di bit dalla sorgente.

Anche in questo contesto è possibile applicare l’union

bound. Individuando le associate alle coppie di parole di co-

dice possiamo infatti scrivere:

( ) ∑ ( )

(4.9.4)

tramite la funzione ausiliaria

( ) {

(4.9.5)

possiamo riformulare la (4.9.4) come segue

( ) ∑ ( ) ( )

(4.9.6)

Osserviamo che S risulta:

( ) ( ( )

( ))

(4.9.7)

possiamo pertanto maggiorare la (4.9.6) ottenendo:

( ) ∑( ( )

( ))

( )

∑( ( )) ( ))

∑[∏( (

) (

))

]

∏ ∑ ( (

) (

))

(4.9.8)


in cui abbiamo anche tenuto conto del fatto che il canale è privo

di memoria.

La sommatoria a ultimo membro della precedente può as-

sumere solo due valori a seconda che risulti o meno uguale a

nel primo caso la somma varrà nell’altro √ ( ). Potre-

mo finalmente scrivere:

( ) ∏ ∑ ( (

) (

))

( √ ( ))

(4.9.9)

essendo la distanza di Hamming tra e .

Quella appena ottenuta è la maggiorazione di Bhattacharyya.

Che utilizzata nello union bound ci permette di scrivere:

∑ ( ) ∑( √ ( ))

(4.9.10)

Il bound di Bhattacharyya sulla probabilità d’errore può es-

sere applicato anche nel caso di spazio d’osservazione continuo.

Per mostrarlo prendiamo nuovamente in considerazione la

(4.8.4), possiamo scrivere:

( | ) ∫ ( | )

∫ √ ( | )

( | ) ( | )

∫ √ ( | ) ( | )

(4.9.11)

la quale sostituendo alle ddp condizionate che vi compaiono le

loro espressioni fornisce:


( | ) ∫ √ ( | ) ( | )

( )

∫

∑ (

) (

)

( )

∫

∑ ( (

)

)

∏∫

√

(

)

)

∏∫

√

(

)

(

)

∏

(

)

∏

∑ (

)

(4.9.12)

La precedente può essere utilizzata nell’union bound

∑ ( ) ( )

∑ (

√ )

∑

‖ ‖

(4.9.13)

La (4.9.13), a ben vedere, si poteva ottenere direttamente

utilizzando una ben nota catena di disuguaglianze relative alla

( ), risulta infatti (vedi Fig. 4.1):

√ (

)

( )

√

(4.9.14)


( )

Constatiamo che, nel caso di uno spazio di osservazione

continuo, la maggiorazione di Bhattacharyya seppur asintotica-

mente stretta è co-

munque più “lasca”

di quelle che si pos-

sono ottenere mag-

giorando la ( )

tramite una delle

precedenti. Utiliz-

zando ad esempio

la seconda si intro-

durrebbe un fattore

vale cioè la se-

guente

disuguaglianza:

∑

‖ ‖

(4.9.15)

L’utilizzo della prima delle (4.9.14) fornirebbe come risulta

evidente dalla Fig. 4.1 una maggiorazione certamente più stretta

solo qualora i valori degli argomenti delle ( ) nella (4.9.13) fos-

sero tutti maggiori di √

.

4.10 - Bound di Gallager.

Lo Union Bound può rivelarsi in molti casi una maggiora-

zione piuttosto lasca, talvolta addirittura palesemente inutile se

dovesse risultare maggiore di uno.

Un diverso approccio per maggiorare è quello di

considerare una regione e valutare la probabilità (

) . Quest’ultima, sarà necessariamente non minore di

Fig. 4.1- ( ),

,

√

0.5 1 1.5 2 2.5 3

0.1

0.2

0.3

0.4

0.5

0.6

2

x


. A tale scopo, scelto ad arbitrio , consideriamo il

sottoinsieme dello spazio d’osservazione S :

{ ∑ ( ( )

( ))

} (4.10.1)

, infatti se deve esistere almeno un in corri-

spondenza al quale risulti ( ) ( ), ciò, ricordando

che , comporta che almeno un addendo, e quindi tutta la

sommatoria nella (4.10.1) che è a termini positivi, assuma un va-

lore maggiore di in ogni punto di . Introducendo la funzione

ausiliaria:

( ) {

(4.10.2)

possiamo scrivere:

( ) ∫ ( )

∫ ( ) ( )

(4.10.3)

È facile verificare che per ogni risulta:

( ) [∑ ( ( )

( ))

]

(4.10.4)

la (4.10.3) può quindi essere ulteriormente maggiorata ottenendo:

( ) ∫[∑ ( ( )

( ))

]

( )

∫[∑( ( ))

]

( )( )

(4.10.5)

Ponendo

, nella precedente otteniamo il bound di Gallager:


( ) ∫[∑( ( ))

]

( )

(4.10.6)

La maggiorazione della probabilità d’errore che si ottiene

dalla (4.10.6), mediando su tutti i messaggi , è applicabile

anche a spazi d’osservazione discreti, a patto di sostituire l’integra-

le con una sommatoria estesa all’intero spazio d’osservazione e di

interpretare le densità di probabilità che vi compaiono come di-

stribuzioni di massa di probabilità:

( ) ∑[∑( ( ))

]

( )

(4.10.7)

L’utilizzo del bound di Gallager, tuttavia, rimane ristretto

ad un limitato insieme di sistemi di trasmissione in quanto esso

comporta comunque il calcolo di integrali o sommatorie multidi-

mensionali la cui complessità cresce con legge esponenziale al

crescere delle dimensioni dello spazio d’osservazione.

Va anche sottolineato che il valore di al secondo membro

delle (4.10.6) e (4.10.7) deve essere ottimizzato se si vuole rendere

la maggiorazione più stretta possibile.

In questo contesto il bound appena introdotto è propedeu-

tico alla dimostrazione del teorema di Shannon sulla codifica di

canale che dimostreremo nel prossimo capitolo.

Capitolo - 5

IL TEOREMA DI SHANNON SULLA CODIFICA

DI CANALE

5.1 - Premessa.

Shannon, nel suo pionieristico lavoro del 1948, individuò

una maggiorazione della probabilità d’errore che, anziché cercare

di maggiorare la probabilità d’errore associata alla scelta di uno

specifico insieme di segnali, si propone di maggiorare la probabi-

lità di errore media tra tutti i possibili insiemi costituiti da un nu-

mero fissato di segnali, contenuti in un sottospazio di dimen-

sione assegnata . Le componenti di ciascun segnale possono

assumere valori appartenenti al medesimo alfabeto di cardinalità

finita .

Sotto queste ipotesi si possono effettuare un numero finito

di scelte per la -upla di segnali da impiegare, esistono infatti solo

( ) possibili -uple di segnali, molte delle quali peraltro pale-

semente “infelici” quali ad esempio quelle che, utilizzando due o

più volte uno stesso segnale per messaggi diversi, darebbero luogo

a probabilità d’errore particolarmente elevate.

Shannon, per dimostrare il suo teorema, sfruttò il fatto che

una qualsiasi funzione di variabili aleatorie assume certamente

almeno un valore non maggiore del suo valor medio.

Tale considerazione, applicata al caso in esame, comporta il

fatto che deve esistere almeno una -upla di segnali, anche se non

sappiamo necessariamente quale, che da luogo ad una probabilità

d’errore non maggiore della media tra le probabilità d’errore di

tutte le possibili -uple.

È interessante osservare che quest’affermazione resta valida

quale che sia la distribuzione di massa di probabilità che si sceglie

per calcolare la media citata. Utilizzando, ad esempio una ddm


uniforme (media aritmetica) daremmo peso uguale a ogni -upla.

Potremmo ritenere più sensato scegliere di attribuire peso nullo a

tutte le -uple in cui uno stesso segnale è utilizzato più di una

volta. Con questa scelta otterremo un valor medio delle probabi-

lità d’errore che sarebbe indubbiamente una maggiorazione più

stretta.

In sostanza esistono infinite possibili scelte, ciascuna delle

quali potrebbe rivelarsi più meno felice, ma costituirebbe co-

munque una maggiorazione per la probabilità d’errore di almeno

una - upla.

5.2 - La Disuguaglianza di Jensen

Per dimostrare il teorema di Shannon è utile impiegare la

disuguaglianza di Jensen che trova applicazione anche nella tratta-

zione di molti altri argomenti legati alla Teoria dell’Informazione.

Per provare tale disuguaglianza, cominciamo con il definire

un sottoinsieme convesso di uno spazio vettoriale:

Definizione 5.1 Un sottoinsieme di uno spazio vettoriale su o su è convesso se

comunque presi due suoi elementi e un reale non negativo non

maggiore di risulta:

( ) (5.2.1)

***********

La precedente in sostanza ci dice che un insieme è con-

vesso se contiene tutte le corde che uniscono coppie di suoi

elementi. Un esempio di regione convessa in è l’insieme di

tutte le possibili distribuzioni di massa di probabilità di una

variabile aleatoria discreta che assume valori appartenenti ad un

insieme di cardinalità . Ad esempio in tale regione è

costituita dalla della retta appartenente al primo

quadrante. Nel caso di (vedi Fig. 5.1) da tutti i punti del piano

di coordinate non negative.


È facile convincersi del fatto che:

- l’intersezione (anche infini-

ta) d’insiemi convessi e convessa

- l’insieme ottenuto moltipli-

cando tutti gli elementi di un

convesso per uno stesso scalare è

convesso.

- è convesso l’insieme che

ha per elementi tutte le possibili

somme tra elementi appartenenti

a due insiemi convessi.

Definizione 5.2 Una funzione ( ) a valori in si dice concava su un sottoinsieme

convesso del suo dominio se comunque presi due elementi apparte-

nenti ad e un reale non negativo risulta:

( ) ( ) ( ) ( ( ) ) (5.2.2)

Se risulta

( ) ( ) ( ) ( ( ) ) (5.2.3)

la funzione si dice strettamente concava.

***********

Le definizioni di funzione convessa e strettamente convessa

sono rispettivamente uguali alle (5.2.2) e (5.2.3) salvo il fatto che

le diseguaglianze cambiano di verso.

Nel caso di funzioni definite su sottoinsiemi di la (5.2.2)

caratterizza le funzioni con concavità rivolta verso il basso in tutti

i punti di un intervallo, di misura non necessariamente finita, che

è l’unico possibile sottoinsieme convesso di .

È noto che, laddove esiste, la derivata seconda di una fun-

zione concava è non positiva.

Inoltre, la combinazione lineare di funzioni concave è

concava, lo è strettamente se anche una sola delle funzioni lo è.

Fig. 5.1

1

1

1


Per verificarlo è sufficiente sommare termine a termine le (5.2.2)

scritte per ciascuno degli addendi della combinazione lineare.

Osservando la (5.2.2) notiamo che se si interpretano ed

come i valori che può assumere una V.A. generalmente multidi-

mensionali e con ed rispettivamente le probabilità che

essa li assuma, potremo affermare che per una funzione concava

su un convesso che contenga tutti i valori che la V.A. può assu-

mere ed una V.A. del tipo citato vale la proprietà:

( ) ( ) (5.2.4)

Vogliamo mostrare che la precedente è valida in generale

cioè per variabili aleatorie discrete generalmente multidimensio-

nali che possano assumere valori.

Abbiamo mostrato che la (5.2.4) è vera per , per

lo è banalmente supponiamo quindi che lo sia per e mo-

striamo che allora lo è anche per .

Se la (5.2.4) è vera per quale che sia la dmp di si ha:

∑ ( )

(∑( )

) (5.2.5)

dove rappresenta la probabilità che la variabile aleatoria

assuma il valore .

Risulta:

∑ ( )

∑

(

∑

∑

( )

)

( ) (5.2.6)

Osserviamo che ∑

∑

soddisfa tutte le proprietà di una

dmp quindi in virtù della (5.2.5) possiamo scrivere:


∑ ( )

∑

(

(

∑

∑

)

)

( )

∑

( ( )) ( )

(5.2.7)

dove è certamente un punto appartenente al convesso su cui è

definita la funzione.

All’ultimo membro della precedente potremo applicare la

(5.2.2) ottenendo:

∑ ( )

∑

( ( )) ( ) (∑

)

(

∑ ∑

∑

)

(∑

)

( )

(5.2.8)

ovviamente la (5.2.5) diventa

∑ ( )

(∑( )

) (5.2.9)

se la ( ) anziché essere concava è convessa.

5.3 - Il Teorema di Shannon sulla Codifica di Canale.

Consideriamo la probabilità d’errore condizionata

all’emissione dello -esimo segnale di una data -upla. è in

realtà una funzione della -upla nel suo complesso, in quanto il

cambiamento anche di un solo segnale nella -upla potrebbe com-

portare la modifica della regione di decisione associata ad .

Per rimarcare questo fatto, porremo in quel che segue

( ).


Dovendo calcolare la media citata nel precedente paragrafo,

e tenuto conto delle considerazioni fatte in merito, possiamo sce-

gliere ad arbitrio una dmp ( ) per le -uple di

possibili segnali. Per semplicità supponiamo che

( ) ∏ ( )

(5.3.1)

e che tutte le dmp marginali che compaiono nella produttoria

siano identiche.

Per non appesantire troppo la notazione calcoliamo la

tale scelta non lede la generalità dei calcoli in quanto come vedre-

mo il risultato finale è indipendente dall’indice . Avremo quindi:

∑ ∑ ∑ ∏ ( ) (

)

(5.3.2)

utilizzando il bound di Gallager otteniamo:

∑ ∑ ∏ (

)

∫ [∑( (

))

]

(

)

(5.3.3)

che, portando la media all’interno dell’integrale, fornisce:

∫ ∑ (

) (

)

{∑ ∑ ∏ (

) [∑ ( (

))

]

}

(5.3.4)

Osserviamo che la quantità ∑ ( (

))

, è reale

positiva e può intendersi come il valore assunto dalla funzione

( ) (5.3.5)


dei messaggi .

Nel derivare il bound di Gallager avevamo supposto

se lo limitiamo all’intervallo , è una funzione concava di

A possiamo quindi applicare la disuguaglianza di Jensen

(vedi § precedente). Maggiorando così il contenuto delle parentesi

graffe della (5.3.4)

∑ ∑ ∏ (

) [∑ ( ( |

))

]

( )

[∑ ∑ ∏ (

) ∑ ( ( |

))

]

[∑ ∑ ∑ ∏ (

) ( ( |

))

]

[∑ ∑ (

) ( ( |

))

]

[( ) ∑ (

) ( (

))

]

(5.3.6)

Abbiamo potuto scrivere l’ultimo membro della precedente

in quanto la quantità ∑ (

) ( ( |

))

, come ci si con-

vince facilmente, non dipende dall’indice .

La precedente ci consente di maggiorare ulteriormente la

ottenendo:

∫ ∑ (

) (

)

[( ) ∑ (

) ( ( |

))

]

(5.3.7)


( ) ∫

[∑ ( )( ( ))

]

Ulteriori elaborazioni si possono ottenere osservando che il

contenuto delle parentesi quadre può intendersi come il valor

medio della ( ( ))

pensata come funzione della V.A.

multidimensionale .

Ciò premesso, ipotizziamo che: ( ) ∏ ( )

,

cioè che il canale sia privo di memoria, se utilizzato in tempi

diversi per inviare le componenti del segnale, ovvero che, per in-

viare dette componenti, si utilizzino contemporaneamente

canali identici mutuamente indipendenti.

Sotto tale ipotesi, ricordando che la media di un prodotto è

uguale al prodotto delle medie, la (5.3.7) si può riscrivere come

segue:

∫[ ∑ ∑ ∑ (

)

∏( ( | ))

]

∫[∏ ∑ (

) ( ( | ))

]

(5.3.8)

la quale limitandoci a considerare delle ( ) ∏ ( )

forni-

sce ancora:

∫ [∏ ∑ ( ) ( ( |

))

]

(5.3.9)


∫ ∏[∑ ( )( ( ))

]

{∫ [∑ ( )( ( ))

]

}

È opportuno ribadire che la maggiorazione appena ricavata,

essendo basata sul bound di Gallager, è del tutto generale quindi

si può applica con semplici modifiche anche a canali discreti.

Pertanto, prima di procedere oltre, provvediamo a riscrive-

re la (5.3.9) per spazi d’uscita discreti.

Per farlo dobbiamo sostituire l’integrale con una sommato-

ria estesa a tutti i possibili simboli dell’alfabeto d’uscita che

supporremo di cardinalità , e la densità di probabilità condizio-

nata che caratterizza il canale con uscita nel continuo con le dmp

condizionate del DMC ottenendo:

[∑(∑ ( )( ( ))

)

]

(5.3.10)

è utile riscrivere la precedente nella forma:

{ [∑ (∑ ( )( ( ))

)

]

}

{ [∑ (∑ ( )( ( ))

)

]}

{

[∑ (∑ ( )( ( ))

)

]}

(5.3.11)

che ne rende esplicita la dipendenza dal rapporto

.

Ricordiamo che è il numero di segnali utilizzati e la di-

mensione del sottospazio in cui detti segnali sono contenuti, si

può quindi interpretate come la massima quantità d’informazio-

ne, espressa in nat, che i parametri fissati per il sistema consenti-

rebbero di affidare a ogni dimensione del sottospazio. rappre-

senta quindi il data rate del sistema.


La (5.3.11) si può esprimere in forma più compatta po-

nendo:

( ( )) [∑(∑ ( )( ( ))

)

] (5.3.12)

Sostituendo la precedente nella (5.3.11) otteniamo:

( ( ( )) ) (5.3.13)

Il minimo al variare di e ( ) del secondo membro della prece-

dente fornisce la maggiorazione più stretta.

La minimizzazione citata equivale alla ricerca di:

( )

( ( )) ( ) (5.3.14)

Ovviamente tale ricerca deve tener conto delle limitazioni

poste su , che deve appartenere all’intervallo e del fatto che

la ( ) è una dmp.

Osserviamo infine che la maggiorazione appena ricavata

non dipende da quindi essa è anche una maggiorazione per la

probabilità d’errore media del sistema. Tutto ciò considerato pos-

siamo scrivere:

( ) (5.3.15)

Appare chiaro quanto siano importanti le proprietà della

( ( )). In quel che segue per semplificare la notazione porre-

mo ( ) , ( ) , e indicheremo la distribuzione di

massa ( ) con

Osserviamo che, indipendentemente dalla ( ), risulta:

( ) [∑(∑ ( )

)

]

[∑ ∑

]

(5.3.16)

si ha inoltre:


( )

|

{ [∑ (∑ ( )

)

]}

||

∑ (∑ ( )

)

||

∑ [∑ ( )

]

||

∑

{( ) [∑ ( )

]}

|

|

∑

{

(∑ )

)

{

[∑ ( )

]

( )∑ ( )

( )

∑ ( )

|

}

}

∑ ( ∑

)

∑

∑∑ ∑∑

( ) ( )

(5.3.17)

Pertanto la pendenza della ( ) , valutata per , è

pari all’informazione mutua del canale connesso ad una sorgente

che emette simboli distribuiti secondo la . Abbiamo indicato la

suddetta informazione mutua come una ( ) proprio per eviden-

ziarne la dipendenza dalla distribuzione sotto il nostro controllo.

Abbiamo già visto che ( ) , se risulta ( ) allora la

( ) che, come abbiamo visto attraversa l’asse delle nell’ori-

gine, assume certamente valori positivi in un intorno destro di

quest’ultima.

Si può anche verificare che la ( ), se ( ) , è una

funzione strettamente crescente e che la sua derivata seconda è

non positiva per . Essa ha quindi la concavità rivolta verso


il basso, salvo alcune eccezioni in cui la derivata seconda è nulla,

ma tali casi non hanno interesse pratico.

Il nostro scopo è quello di massimizzare la ( ) ,

consideriamo per il momento solo la dipendenza da , la derivata

parziale rispetto a della funzione in parola vale:

( )

(5.3.18)

affinché si annulli deve risultare ( )

. Sappiamo che

( )

non è crescente poiché sua derivata è non positiva, pertanto la

(5.3.18) non può annullarsi per se:

( )

|

(5.3.19)

Ovvero se

( )

|

( ) (5.3.20)

per i valori di che soddisfano la (5.3.19) risulta, ( )

quindi ( ) è strettamente crescente nell’intervallo

ed assume il suo massimo valore nell’estremo destro dell’interval-

lo; avremo cioè:

( ) ( ) ( )

|

(5.3.21)

per

( )

|

( ) (5.3.22)

la (5.3.18) si annulla certamente per un valore di appartenente

all’intervallo che risolve l’equazione ( )

. Tale zero

corrisponde certamente a un massimo come si constata facil-


mente analizzando il segno della (5.3.18). La ( ) nel range di

valori di dato dalla (5.3.22) è implicitamente definita dalle:

{

( ) ( )

( )

( )

(5.3.23)

dalle quali si ottiene:

( )

( ( ) ( )

)

( )

( )

( )

( )

(5.3.24)

che comporta:

( )

( ( )

)

( )

(5.3.25)

Nelle ultime due equazioni il secondo membro è una fun-

zione di essendo la soluzione della seconda delle (5.3.23) che

è unica in quanto nell’intervallo di interesse abbiamo visto che la ( )

è una funzione monotona di .

Per i valori di ( ) la (5.3.18) assumerebbe valori nega-

tivi quindi la ( ) sarebbe una funzione decrescente di

quindi il suo massimo lo raggiungerebbe per , ma ( )

indipendentemente da ne seguirebbe ( ) e la (5.3.15) si

rivelerebbe del tutto inutile.

In conclusione la ( ) per valori di appartenenti al-

l’intervallo [ ( )

|

] è un tratto di retta parallela alla secon-

da bisettrice che tocca l’asse delle ordinate in ( ( )) alla

quale si raccorda un tratto di curva con concavità rivolta verso

l’alto che tocca l’asse delle ascisse in I( ), come si verifica


facilmente valutando le (5.3.23) per . A questo punto non

resta che massimizzare la ( ( )) rispetto alla ( ).

La che massimizza la ( ) dipende dal canale che si sta

utilizzando, e, per fissato canale può dipendere dal rate , in

particolare esistono canali per cui la ( ) è massimizzata da

un'unica , canali per i quali esistono delle distinte che massi-

mizzano la funzione in parola in intervalli di disgiunti e canali

per cui la ( ) che massimizza la ( ) varia con continuità con

. In ogni caso il fatto che la ( ) sia una funzione limitata

convessa per I( ) , assicura che la massimizzazione

desiderata è in pratica l’inviluppo superiore di tutte le ( ), si

può dimostrare che detta funzione è anch’essa convessa,

decrescente e non negativa per , dove

( ( )) è la

capacità di canale e che in questo contesto assume un ruolo fon-

damentale.

In sostanza abbiamo appena dimostrato il:

Teorema 5.1: Teorema di Shannon sulla codifica di canale Dato un qualsiasi canale discreto privo di memoria, esiste un codice

con un rate [

], con parole di simboli per il quale risulta:

( ) (5.3.26)

dove è la probabilità d’errore ottenuta tramite un ricevitore a massima

verosimiglianza ed ( ) una funzione decrescente, convessa e maggiore di

zero nell’intervallo .

***********

Il precedente teorema in pratica mostra che se aumentiamo

mantenendo costante possiamo individuare codici con proba-

bilità d’errore piccola a piacere purché risulti . È opportuno

tuttavia osservare che al crescere di il numero di parole di

codice necessario per mantenere costante il rate cresce anch’esso,

“purtroppo” con legge esponenziale, portando così, spesso a livel-

li improponibili, la complessità di decodifica. Da qui la necessità

di individuare dei codici su spazi dotati di strutture algebriche


molto ricche che permettano operazioni di codifica e decodifica

relativamente semplici, malgrado l’elevato numero di parole che li

costituiscono.

Potrebbe sorgere una perplessità circa il risultato appena ot-

tenuto, si potrebbe infatti sospettare che il bound ottenuto per la

probabilità d’errore media del codice nasconda delle probabilità

d’errore condizionate all’emissione di una specifica parola del co-

dice molto maggiore del bound relativo alla probabilità d’errore

media.

Per fugare questa, legittima, perplessità consideriamo uno

spazio di dimensione , o che è lo stesso un codice costituito da

parole di simboli emessi consecutivamente da un codificatore di

canale. Il teorema di Shannon ci garantisce che esiste almeno un

set di parole tra le possibili scelte, che esibisce una pro-

babilità d’errore media non maggiore di:

(

( )

) (5.3.27)

Se assumiamo che le parole che costituiscono il codice abbiano

uguale probabilità di essere emesse, allora avremo:

∑

(5.3.28)

Scartando gli segnali cui corrispondono le probabilità d’errore

più grandi, ci rendiamo conto che la probabilità d’errore associata

ad uno qualsiasi dei segnali sopravvissuti non può essere maggiore

di ( ( )

). Se così non fosse, almeno ad un termine dei so-

pravvissuti corrisponderebbe una ( ( )

) vi sarebbero

quindi almeno segnali, quelli scartati più quello appena

citato, con ( ( )

) e potremmo scrivere:

( )

( ( )

)

(

( )

)

( ( )

) (5.3.29)

contro l’ipotesi che il codice soddisfa la (5.3.27).


Per ogni del gruppo dei sopravvissuti potremo allora

scrivere:

(

( )

)

(

( ( ) ( )

))

( ( ) ( )

)

(

( ( )

( )

))

(

( )

)

(5.3.30)

Pertanto esiste certamente un codice costituito da parole di K

simboli per il quale la peggiore delle probabilità d’errore condizio-

nata supera il bound sulla probabilità d’errore media per al più un

fattore .

Capitolo - 6

STRUTTURE ALGEBRICHE

Al fine di introdurre il concetto di codice è opportuno

ricordare alcune definizioni:

6.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à:

( ) ( )

(6.1.1)

Se la legge di composizione interna è anche commutativa

è un gruppo commutativo o abeliano.

6.2 - Anello

Un insieme nel quale siano state individuate due leggi di

composizione interna che chiameremo addizione e moltiplicazio-

ne è un anello se:

- è un gruppo commutativo rispetto all’addizione;

- la moltiplicazione gode della proprietà associativa;

- vale la legge distributiva della moltiplicazione rispetto all’addi-

zione sia a destra che a sinistra.

Se la moltiplicazione gode anche della proprietà commutati-

va diremo che è un anello commutativo, se esiste in l’elemento

neutro per la moltiplicazione diremo che è un anello con identità.

6.3 - Campo

Un insieme che sia un anello commutativo con identità è

anche un campo se privato dell’elemento neutro rispetto all’addi-

zione è un gruppo commutativo rispetto alla moltiplicazione.


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

sieme dei complessi sono campi. Si verifica facilmente che an-

che l’insieme , effettuando l’addizione senza riporto, cioè po-

nendo e con la usuale moltiplicazione in è un campo

che indicheremo con .

6.4 - Spazio vettoriale

Dato un gruppo abeliano ed un campo si dice che è

uno spazio vettoriale sul campo se si è individuata una legge di

composizione esterna, detta prodotto per scalari, che associa ad

ogni elemento di un elemento di e che comunque scelti

e goda delle proprietà:

{

( ) ( )

(6.4.1)

dove e indicano rispettivamente gli elementi neutri dell’addi-

zione e della moltiplicazione del campo, quello del gruppo, che

chiameremo anche origine dello spazio.

Capitolo - 7

DISTANZA DI HAMMING

7.1 - Lo Spazio

Fissato un naturale consideriamo l’insieme di tutte

le -uple ordinate d’elementi di . Ci si rende conto facilmente

che è un gruppo rispetto alla legge di composizione interna

che associa ad ogni coppia di elementi di quello ottenuto com-

ponendo termine a termine tramite l’addizione in gli elementi

omologhi delle due -uple. Si constata che ogni -upla è l’opposta

di se stessa e che l’elemento neutro del gruppo è la -upla

identicamente nulla.

è anche uno spazio vettoriale di dimensione sopra il

campo , potremo quindi pensare gli elementi di come vettori

riga con componenti che assumono valori in . In quel che se-

gue indicheremo gli elementi di con lettere corsive minuscole

in grassetto e li chiameremo parole di , o semplicemente parole,

le componenti della generica parola saranno chiamate bit (nel sen-

so di Binary digIT, non di Binary Informationn uniT).

È opportuno tenere presente che:

- è uno spazio metrico, possiamo infatti assumere come di-

stanza tra due parole di la somma in delle somme in

delle componenti omologhe;

- è uno spazio normato potendosi assumere come norma

del generico elemento di la distanza di detto elemento dal-

l’origine di , cioè dalla parola identicamente nulla.

In quel che segue indicheremo l’addizione in con .

La distanza sopra introdotta è detta distanza di Hamming.

Essa in pratica è espressa dal numero di bit corrispondenti diversi

delle due parole; in formule:


( ) ∑

(7.1.1)

Che la distanza di Hamming sia effettivamente una metrica

si verifica facilmente, essa infatti è 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

di risulta:

( ) ( ) ( ) (7.1.2)

per sincerarsene basta esplicitare la precedente:

∑

∑

∑

(7.1.3)

ed osservare che tutti gli addendi delle sommatorie che compaio-

no nella precedente sono non negativi, pertanto è sufficiente veri-

ficare che la (7.1.3) sia soddisfatta addendo per addendo, fatto

questo facilmente verificabile effettuando prove esaustive.

La massima distanza possibile tra due parole di vale 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 vi-

ceversa.

La norma di un elemento di 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 addizione e sot-

trazione coincidono, in quanto ogni elemento è l’opposto di se

stesso.

7.2 - Generalizzazione della distanza di Hamming

Dato un insieme di cardinalità consideriamo l’insieme

A . Anche su detto insieme si può introdurre la distanza di Ham-

ming tra due suoi elementi, che anche in questo caso è espressa


dal numero di simboli corrispondenti diversi tra loro. La distanza

tra due elementi di A è quindi al più .

Si può verificare che la distanza di Hamming è una metrica

su A . 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 di A ed un naturale esistono

( )( ) elementi di A a distanza da . Potremmo dire che

detti elementi giacciono sulla superficie di una sfera di raggio

centrata in . Detta sfera contiene esattamente ∑ ( )( )

elementi, il numero di tali elementi, per analogia, ne costituisce il

“volume”.

Qualora A fosse anche uno spazio vettoriale, tramite la

distanza di Hamming si potrebbe individuare un “peso” per ogni

elemento di A espresso dalla distanza dell’elemento dall’origine

dello spazio, tale peso costituirebbe una possibile norma per A .

Capitolo - 8

CODICI BINARI A BLOCCHI

8.1 - Codificatore, Codice, Decodificatore

Cominciamo con alcune definizioni:

Definizione 8.1 - codificatore a blocchi Un codificatore binario a blocchi è un’applicazione da a , se

è iniettiva il codificatore è non ambiguo.

***********

Definizione 8.2 - codice binario a blocchi Dato un codificatore da a chiameremo codice binario a

blocchi l’insieme ( ) . Gli elementi di sono denominati

parole di codice.

***********

In altri termini per codice binario a blocchi intenderemo

l’insieme delle parole di che sono immagine secondo il codifi-

catore di almeno un elemento di , uno solo se il codificatore

è non ambiguo.

In questo contesto la finalità di un codice è quella di com-

battere l’effetto dei disturbi introdotti dal canale nel segnale rice-

vuto, tali disturbi potrebbero infatti dar luogo ad errori nella rice-

zione. 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 mag-

giore probabilità.

Ciò è utile qualora:

o sia disponibile un canale di ritorno;

o non sia necessario trasmettere in tempo reale e sia quin-

di possibile la ritrasmissione del messaggio senza pregiu-

dicare 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 correg-

gere gli errori che più verosimilmente sono presenti nella pa-

rola ricevuta in questo caso si fa riferimento a strategie di tipo

FEC (Forward Error Correction).

In alcuni casi sono previste entrambe le strategie, cioè alcu-

ni 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 a un’applicazione che chiameremo decodifi-

catore.

Definizione 8.3 - decodificatore Dato un codice binario a blocchi , il decodificatore è un’appli-

cazione

che sulla base di un criterio prefissato, ha il compito di as-

sociare ad ogni elemento di che si presenti all’uscita del canale l’elemento

di che verosimilmente era stato immesso nel codificatore posto all’ingresso

del canale stesso.

***********

Quanto appena detto rende chiaro che più che di codici bi-

sognerebbe parlare di sistemi di codifica-decodifica, sia perché uno

stesso codice (in quanto sottoinsieme di ) potrebbe essere

ottenuto con codificatori diversi, sia perché potrebbe essere deco-

dificato con decodificatori basati su criteri diversi.

Nella pratica in effetti quando si parla di codice ci si rife-

risce indifferentemente, lo faremo anche noi, sia a che a ,

lasciando al contesto l’onere di rendere chiaro a cosa si stia effetti-

vamente facendo riferimento.

Appare in conclusione chiaro che un sistema di codifica è

in realtà completamente definito solo dalla terna .

La capacità di correzione di un codice è in pratica affidata

alla ridondanza più o meno oculatamente introdotta dal codifica-


tore, ne discende che di regola e che il codificatore è una

applicazione iniettiva.

Altrettanto evidente è che, se il codice è non ambiguo, il

criterio adottato per la scelta del decodificatore deve necessaria-

mente essere tale che la restrizione di a coincida con

l’applicazione inversa della restrizione di a .

8.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 d’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 esem-

pio 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 comples-

sità e quindi dei costi, ovvero potrebbe essere una scelta obbligata

da limiti tecnologici contingenti.

In particolare per il momento faremo riferimento a un si-

stema che trasmette su un BSC (Binary Symmetric Channel) privo

di memoria. I simboli che costituiscono la generica parola di codi-


ce vengono quindi inviati indipendentemente sul canale e ciascu-

no di essi avrà una probabilità

di essere rivelato in modo er-

rato, pertanto in uscita al canale avremo un elemento di che

non è certo corrisponda all’elemento inviato.

La probabilità di ricevere una parola di correttamente

sarà data da ( ) ad esempio con e avremo

conseguentemente la probabilità di ricevere una paro-

la non corretta vale , tale probabilità è in realtà scom-

ponibile nella somma di tante probabilità d’eventi disgiunti, preci-

samente eventi del tipo: “nella parola ricevuta sono presenti esat-

tamente errori”.

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

quindi anche scrivere nella forma:

∑( ) ( )

(8.2.1)

dove il - esimo addendo esprime la probabilità che nella parola

ricevuta siano presenti esattamente errori. La probabilità che la

parola contenga almeno due errori si può pertanto scrivere anche

nella forma:

∑( ) ( )

(8.2.2)

nel nostro esempio tale probabilità si ridurrebbe a .

Quanto detto mostra come il contributo alla probabilità

dell’errore singolo sia di fatto dominante essendo gli addendi della

(8.2.1) rapidamente decrescenti al crescere di 1.

1 Per verificarlo è sufficiente esprimere ( ) nella forma (

⁄ )

(

) ed osservare che se

risulta (

) , pertanto (

) è una funzione

decrescente di t .


Disporre di un codice in grado di correggere anche un nu-

mero limitato di errori in una parola ricevuta sembrerebbe per-

tanto 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 de-

stinati 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 sul bit cresce al diminuire

della energia ad esso associata, il calcolo della (8.2.2) andrebbe

quindi effettuato introducendo un valore di che tiene conto di

ciò.

Malgrado le considerazioni appena fatte, fin quando è ac-

cettabile l’aumento della banda, l’introduzione di un codice a cor-

rezione d’errore è comunque vantaggiosa rispetto alla trasmis-

sione non codificata.

8.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), nel caso

in cui i bit informativi emessi dalla sorgente siano equiprobabili,

che, com’è noto, equivale alla maximum a posteriori probability

(MAP). Osserviamo che in questo caso sono equiprobabili anche

tutte le parole di e quindi, in virtù dell’iniettività del codificato-

re , lo saranno anche tutte le parole del codice .

Sotto quest’ipotesi, indicando con la generica parola di

codice, con la parola ricevuta e con la parola di codice

scelta dal decodificatore, la regola di decisione sarà:


Regola di decisione a Massima Verosimiglianza Scegli la parola di codice per la quale è massima la probabilità di

ricevere , atteso che sia la parola trasmessa, in simboli:

( ( ))

(8.3.1)

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

codice che lo raggiungono.

***********

Nella precedente e rappresentano VV.AA. multidimen-

sionali che assumono rispettivamente valori in ed in .

Considerato che nel nostro caso risulta:

( ) ( ) ( )

(

)

( ) (8.3.2)

dove rappresenta il numero di bit in cui differisce da Se

il massimo della (8.3.2) si raggiunge per tutti i valori di che

rendono minimo. Qualora ciò avvenga in corrispondenza ad

un'unica parola di codice, si sceglie quella. Se dovessero esservi

più parole per le quali ciò avviene, il decodificatore, o, in armonia

con la regola MV, sceglie a caso, o segnala al trasmettitore la

presenza di errori nella parola ricevuta. Va da se che l’ultima op-

zione è praticabile solo se si dispone di un canale di ritorno e se la

trasmissione non deve necessariamente avvenire in tempo reale.

Osserviamo che , è la distanza di Hamming tra e ,

quindi il criterio di decisione a massima verosimiglianza su canale

BSC consiste in pratica nello scegliere a caso, tra le parole del co-

dice a minima distanza di Hamming dalla parola ricevuta.

8.4 - Definizioni e teoremi sui codici rivelatori e correttori

Supponiamo che il trasmettitore invii una parola e che per

effetto dei disturbi venga ricevuta una parola diversa da . Si

constata che esiste certamente che ci permette di scrivere

. Chiameremo evento o pattern d’errore.


Definizione 8.4 Un pattern di errore è rilevabile se risulta:

(8.4.1)

essendo il complementare di rispetto a .

Viceversa diremo che non è rilevabile se:

(8.4.2)

***********

Ad ogni pattern d’errore corrisponde un peso. sistono

( ) eventi d’errore di peso Osserviamo che le posizioni dei bit

uno nel pattern d’errore identificano i bit errati nella parola rice-

vuta.

Si dice che un codice è in grado di rivelare errori se rivela

tutti i pattern di errore di peso indipendentemente dalla parola

di codice trasmessa.

Definizione 8.5 Siano e due parole di . Si definisce distanza minima ( ) di

un codice:

( ( ) ( ))

(8.4.3)

***********

Teorema 8.1 Un codice binario a blocchi, rivela tutti gli errori di peso se e solo se

.

Dimostrazione:

Necessarietà:

Se il codice rivela tutti gli errori di peso non superiore a ,

allora, comunque scelta una parola di codice ed un pattern

d’errore di peso , la parola non può essere una parola di

codice.

Ammettiamo per assurdo che esisterebbero allora

almeno due parole di codice, siano e , tali che ( ) .


Consideriamo il pattern d’errore , risulta:

(8.4.4)

esisterebbe quindi un evento d’errore di peso che non può es-

sere rivelato in quanto composto con una parola di codice ne

genera un’altra.

Sufficienza:

Se e viene ricevuta la parola , con

risulta:

( ) ( ) (8.4.5)

non può quindi essere una parola di codice poiché ,

l’errore viene pertanto rilevato.

***********

Definizione 8.6 Diciamo che un decodificatore è in grado di correggere un pattern

d’errore se, quale che sia la parola di codice c , risulta:

( ) ( ) (8.4.6)

Diciamo che un decodificatore è in grado di correggere errori di peso

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

***********

Teorema 8.2 Affinché un decodificatore MV possa correggere tutti i pattern d’errore

di peso non superiore a , il codice deve avere una .

Dimostrazione:

Supponiamo, per assurdo, che esista un codice in grado di

correggere tutti gli errori di peso non superiore a con

. Per detto codice esisterà quindi almeno una coppia di pa-

role di codice, e , la cui distanza è . Esistono anche

certamente due pattern d’errore, siano ed , entrambi di peso

non maggiore di , tali che:

(8.4.7)


Nel caso in cui potremo scegliere un pattern d’errore

tale che ed un tale che che soddisfino la

precedente.

Supponiamo adesso che venga ricevuta la parola , la

sua distanza da vale quella da vale:

( ) ( ) (8.4.8)

pertanto il decodificatore a massima verosimiglianza decide per ,

o per una qualsiasi altra parola di codice che disti non più di da

.

Se potremo scegliere due pattern d’errore ed

entrambi di peso che soddisfano la (8.4.7). Supponiamo ancora

una volta che venga ricevuta la parola , la sua distanza da

vale come pure la sua distanza da pertanto, o il decodificatore

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

di codice che disti da , meno di .

***********

Teorema 8.3 Un decodificatore MV è in grado di correggere tutti i pattern d’errore

di peso non superiore a

.

Dimostrazione:

Supponiamo che il canale modifichi una parola di codice

aggiungendovi un pattern d’errore di peso non superiore a .

All’ingresso del decodificatore si presenta quindi la parola

. Quale che sia risulta , in quanto ,

poiché dista da meno di , inoltre:

( ) (8.4.9)

Il peso di e quello del pattern d’errore è non

superiore a , pertanto, , ( ) , mentre ( )


, quindi il decodificatore MV in corrispondenza a restituirà

( ) ( ), l’errore verrà quindi corretto.

***********

Capitolo - 9

CODICI LINEARI A BLOCCHI

9.1 - Premessa

Abbiamo visto che un codice a blocco è sostanzialmente

un’applicazione iniettiva tra e con gli bit ag-

giunti consentono in pratica di migliorare le prestazioni del siste-

ma introducendo un’opportuna ridondanza ai bit informativi.

Osserviamo che al crescere di cresce, con legge esponen-

ziale, il numero delle parole di codice. Ci si rende conto che in

queste condizioni la tecnica di decodifica, consistente in una ri-

cerca esaustiva su una tabella (in pratica un banco di memoria)

che associa ad ogni possibile elemento di l’elemento di che

più “verosimilmente” è stato trasmesso diventa in breve imprati-

cabile a causa delle eccessive dimensioni della succitata tabella, ov-

vero 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 al-

goritmico, o che quantomeno limitino la quantità di memoria ne-

cessaria 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 mag-

giore sarà la possibilità di individuare algoritmi di decodifica effi-

cienti.

9.2 - Morfismi

È utile introdurre alcune definizioni


Definizione 9.1 - omomorfismo Un omomorfismo è un’applicazione avente come dominio un gruppo

e come codominio un gruppo tale che

( ) ( ) ( ) (9.2.1)

***********

Nella precedente il segno indica la legge di composizione

interna relativa al gruppo in cui si opera.

Definizione 9.2 - monomorfismo Un monomorfismo è un omomorfismo iniettivo.

***********

Definizione 9.3 - isomorfismo Un monomorfismo suriettivo è un isomorfismo.

***********

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

un omomorfismo ( ) è 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 composi-

zione interna del gruppo in cui è contenuto.

9.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. 9.1) un registro d’ingresso dotato di celle, da un banco

di sommatori ciascuno dei quali con un numero di ingressi

compreso tra e e da un registro di uscita costituito da celle

connesse alle uscite dei sommatori corrispondenti. Questi ultimi,

nel caso dei codici binari, effettuano le somme in . Conveniamo

che un sommatore con un solo ingresso equivale ad una connes-

sione diretta tra la cella d’ingresso e quella di uscita corrispon-

dente al sommatore.


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 periodi del suo clock, l’uscita dei sommatori, che potreb-

bero essere realizzati con delle porte logiche di tipo XOR, viene

utilizzata per settare le celle del registro di uscita che verrà

quindi completamente scaricato nel tempo necessario a ricaricare

con i successivi bit il registro di ingresso.

In sostanza, se e indicano rispettivamente i pe-

riodi di clock del registro d’ingresso e di quello d’uscita, deve ri-

sultare .

9.4 - Matrice generatrice del codice

I codici lineari a blocco sono anche chiamati codici a con-

trollo 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 una parola di e con ( ) la

corrispondente parola di in uscita dal codificatore, l’ esimo

bit della parola d’uscita può esprimersi nella forma:

(9.4.1)

Fig. 9.1 - Schema di principio di un codice di Hamming 15,11

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

clkoutT

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

clk inT


dove il generico è un coefficiente che vale se un ingresso

del -esimo sommatore è connesso alla -esima cella del registro di

ingresso e vale altrimenti.

Ricordiamoci che tutte le operazioni delle (9.4.1) sono

effettuate secondo le regole del campo .

Un codice definito tramite le (9.4.1) si dice lineare in quan-

to, come si verifica facilmente, la parola di codice ottenuta in cor-

rispondenza alla somma di due qualsiasi parole di è la somma

in delle rispettive parole di codice.

e sono gruppi, ed un codificatore lineare è un omo-

morfismo, ovviamente, è auspicabile che sia anche un monomor-

fismo, onde evitare che a due parole distinte di corrisponda la

stessa parola di codice in .

Il codice è pertanto un sottogruppo di .

Se pensiamo e come vettori riga le (9.4.1) si possono

rappresentare sotto forma matriciale:

(9.4.2)

dove è una matrice il cui generico elemento è . è

detta matrice generatrice del codice.

Si osservi che le righe della matrice , sono le parole di

codice che vengono generate in corrispondenza agli elementi che

costituiscono la base canonica di . Ci si convince anche abba-

stanza facilmente del fatto che le righe di generano mediante

tutte le loro possibili combinazioni lineari , che oltre ad essere

un sottogruppo di ne è anche un sottospazio. Ovviamente af-

finché il codice non sia ambiguo deve essere un monomor-

fismo.

Una condizione necessaria e sufficiente affinché sia un

monomorfismo è che le righe della sua matrice generatrice siano

linearmente indipendenti.


9.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 identica-

mente nulla in un codice lineare è sempre una parola di codice, in

quanto ottenibile sommando ad una qualunque parola del codice

se stessa, indicando con la parola identicamente nulla per un

codice lineare avremo:

( ) ( ) (9.5.1)

ma, per fissato , al variare di 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 calco-

lo della probabilità d’errore in quanto la probabilità d’errore con-

dizionata all’invio di una parola di codice non dipende dalla par-

ticolare parola inviata, ed è quindi uguale alla probabilità d’errore

non condizionata.

Dalla (9.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 mini-

ma distanza di Hamming dalla parola nulla, ovviamente non è

detto che tale parola sia unica.

La (9.5.1) ci suggerisce di introdurre la cosiddetta distribu-

zione dei pesi del codice.

Definizione 9.4 –Distribuzione dei pesi di un codice lineare

Dato un codice lineare per distribuzione dei pesi s’intende una

applicazione ( ), definita sull’insieme dei naturali non maggiori di , a

valori in ; che associa 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 pri-

ma istanza influenzate dalla sua distanza minima, che coincide con


il più piccolo elemento non nullo del dominio di ( ) cui corri-

sponde un’immagine diversa da zero, ma dipendono anche dalla

( ) nel suo insieme.

9.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 9.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 venga ag-

giunto un pattern d’errore che coincide con una parola di codice

in ingresso al decodificatore si presenterà la parola , ma il

codice è lineare quindi è una parola di codice pertanto

l’errore non sarà rivelato.

Viceversa se un pattern d’errore non viene rivelato, allora

deve esistere una parola di codice tale che essendo

la parola trasmessa. L’eguaglianza appena scritta comporta:

(9.6.1)

pertanto è una parola di codice.

***********

9.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 a MV.

Sappiamo che (vedi Teorema 9.1) gli unici pattern d’errore

non rivelati sono quelli che coincidono con una parola di codice.


La probabilità che si presenti un dato pattern d’errore dipende

esclusivamente dal suo peso e vale in particolare:

( ) (9.7.1)

Tra tutti gli ( ) possibili pattern d’errore di peso 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à ( )

che un errore non venga rivelato dal codice vale:

( ) ∑ ( )

( ) (9.7.2)

La precedente presuppone la conoscenza della distribuzio-

ne dei pesi. Purtroppo detta funzione non è nota per molti dei co-

dici d’uso comune, in questo caso può essere utile una maggiora-

zione della (9.7.2) che si basa sulla considerazione che in ogni

caso deve essere:

( ) (

) (9.7.3)

non possono cioè esservi più pattern d’errore di peso di quante

non siano le parole di aventi quel peso. Potremo quindi certa-

mente scrivere:

( ) ∑ (

)

( ) (9.7.4)

9.8 - Laterali di un sottogruppo

In questo paragrafo utilizzeremo la notazione moltiplicativa

per indicare la legge di composizione di un gruppo e indicheremo

con l’elemento neutro rispetto ad essa.

Consideriamo un gruppo abeliano ed un suo sottogruppo

è quindi chiuso rispetto alla legge di composizione di .


Consideriamo un generico elemento non appartenente a

. Se componiamo con gli elementi di otteniamo un sottoin-

sieme di disgiunto da . Se, infatti, risultasse che, per un qual-

che elemento di , , ciò implicherebbe che

, quindi

, ma se allora, es-

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

viene denominato laterale, coinsieme o coset di .

Consideriamo adesso, se esiste, un elemento che non ap-

partiene né a né a , sia . Anche , composto con gli ele-

menti di , genera un sottoinsieme di disgiunto da , ma an

che da ; se infatti esistesse tale che , ciò

implicherebbe quindi contraddi-

cendo l’ipotesi. Possiamo quindi concludere che i laterali di un

sottogruppo se non sono disgiunti sono coincidenti.

Ogni sottogruppo induce quindi nel gruppo una partizione

in laterali. 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 sotto-

gruppo, è in grado di generare il laterale cui appartiene. È quindi

legittimo scegliere in corrispondenza a ogni laterale un suo ele-

mento, 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 es-

sere associati dei laterali destri e sinistri, generalmente distinti,

qualora tali laterali dovessero coincidere si direbbe che il sotto-

gruppo 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 sottomultiplo di quel-

lo del gruppo in cui è contenuto.


9.9 - Decodifica tramite i rappresentanti di laterale

Tornando ai codici lineari a blocco ( ), ricordiamo che

l’insieme delle parole di un tale codice costituisce un sottogruppo

. 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 appartiene ad un

solo laterale di rispetto a , intendendo ovviamente stesso

come un laterale. Risulta inoltre , il pattern d’errore in-

trodotto dal canale appartiene quindi certamente allo stesso late-

rale cui appartiene .

Visto che la probabilità che il canale introduca un pattern

d’errore di un dato peso decresce al crescere di quest’ultimo, l’ipo-

tesi più verosimile è che il pattern d’errore introdotto coincida

con una parola di peso minimo appartenente allo stesso laterale

della parola ricevuta.

Dato un codice scegliamo quindi in ogni suo laterale una

parola di peso minimo. Qualora in un laterale vi siano più parole

di peso minimo ne sceglieremo una a caso fra esse. Osserviamo

che, quale che sia la parola ricevuta, esisterà una sola parola di

codice che permette di scrivere: essendo il coset leader

del laterale a cui appartiene.

Comunque scelta una parola di codice risulta:

( ) ( ) (9.9.1)

in quanto è una parola di che appartiene allo stesso

laterale di , visto che è una parola di codice, ed è per ipo-

tesi una parola di peso minimo di quel laterale, pertanto se adot-

tiamo la decodifica ML dobbiamo necessariamente scegliere la pa-

rola .

Se nello stesso laterale più di una parola ha peso minimo,

ciò significa che la parola ricevuta 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 codi-

ce, tale operazione non la altera in quanto il rappresentante di la-

terale relativo a è unico ed è ovviamente la parola identicamente

nulla.

Quanto sopra detto ci porta ad enunciare il seguente

Teorema 9.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 per individuare il laterale cui appartiene la pa-

rola, se è grande tale ricerca può diventare troppo onerosa.

9.10 - Probabilità d’errore di un codice lineare a blocchi

Il Teorema 9.2 ci suggerisce come calcolare la probabilità di

corretta decisione di un codice, impiegato su un canale BSC.

Osserviamo innanzitutto che all’uscita del decodificatore

sarà presente la parola effettivamente inviata tutte e sole le volte

che il pattern d’errore introdotto dal canale coincide con un coset

leader, considerando anche tra i pattern d’errore quello identica-

mente nullo che è il coset leader del codice.

La coinciderà quindi con la probabilità che il pattern di

errore sia un qualsiasi coset leader. Possiamo quindi scrivere:

∑ ( ) ( )

(9.10.1)


dove rappresenta il massimo peso raggiunto dai coset leader ed

( ) un’applicazione che associa ad ogni intero compreso tra

ed il numero di coset leader di peso .

Dalla (9.10.1) discende facilmente:

∑ ( ) ( )

(9.10.2)

9.11 - Codici perfetti, bound di Hamming

Una maggiorazione della probabilità d’errore può essere ot-

tenuta ricordando il Teorema 8.3, che afferma che la capacità

correttiva di un codice è non minore di

. In altri ter-

mini il teorema afferma che la regione di decisione di ciascuna pa-

rola di codice contiene una “ipersfera” di raggio pari a in , che

contiene esattamente ∑ ( )

punti.

In un codice lineare tutte le regioni di decisione hanno la

stessa forma e l’insieme dei coset leader costituisce la regione di

decisione associata alla parola nulla. Vi sono laterali, quindi

coset leader. Il Teorema 8.3 nel caso di codici lineari implica

quindi che deve valere la disuguaglianza:

∑( )

∑ ( )

(9.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 addendi dell’ultimo membro della (9.11.1) devono

necessariamente essere uguali ai corrispondenti addendi della

sommatoria a primo membro, possiamo pertanto scrivere:

∑ ( ) ( )

∑( )

( ) (9.11.2)


∑( )

( ) ∑ ( )

( )

La precedente è ovviamente soddisfatta come uguaglianza

solo dai codici perfetti, quali sono ad esempio i codici di Ham-

ming cui accenneremo più avanti.

Capitolo - 10

CODICI SISTEMATICI

10.1 - Codici Sistematici

Quanto detto nei precedenti paragrafi ci fa comprendere

che le prestazioni di un codice lineare sono da attribuirsi sostan-

zialmente al sottospazio di generato dalle righe della matrice

che se sono linearmente indipendenti costituiscono 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 sono, da questo punto di vista, del tutto

equivalenti.

In pratica lo spazio generato dalle righe di non cambia se

si permutano le sue righe, o se si somma ad una qualunque riga di

una combinazione lineare delle restanti.

Dato un codice lineare a blocchi, consideriamo la sua ma-

trice e selezioniamone una sua colonna non identicamente

nulla. Supponiamo sia la -esima. Consideriamo quindi una riga di

che abbia un nella -esima colonna, supponiamo sia la -esima,

sommiamo tale riga a tutte le altre righe di che si trovano nelle

stesse condizioni. Otterremo così una matrice, sia ( ) , equiva-

lente a la cui -esima colonna ha un solo valore in posizione -

esima. Operiamo adesso sulla matrice ( ) come avevamo operato

sulla con la sola accortezza di scegliere una colonna che abbia

un in una riga diversa dalla -esima, otterremo così una ( ) con

due colonne che presentano un solo valore su righe diverse.

All’ -esimo passo sceglieremo una colonna che abbia un in una

riga diversa da quelle selezionate ai passi precedenti.

Tale procedura potrà essere ripetuta al più volte, a meno

che non sia più possibile 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 da cui

eravamo partiti non erano linearmente indipendenti, quindi non

erano in grado di generare un sottospazio di dimensione , o, che

è lo stesso, il codificatore non era un monomorfismo di in

cioè si tratterebbe di un codice ambiguo.

Al termine della procedura sopra descritta avremo quindi

una matrice ( ) che ha almeno colonne in cui compare un solo

. Tra le colonne con un solo ne esisterà almeno una che lo ha

in corrispondenza alla prima riga, una in corrispondenza alla

seconda e cosi via fino alla -esima.

Se poi s’intende utilizzare il codice su un canale simmetrico

binario, ovvero mappando coppie di bit della parola di codice in

punti di una costellazione QAM, è anche legittimo permutare le

colonne della matrice , questa operazione equivale in sostanza ad

etichettare diversamente le dimensioni dello spazio .

È ovvio che permutando opportunamente le colonne della

( ) si può ottenere una matrice del tipo:

(10.1.1)

Un codice lineare a blocchi la cui matrice generatrice assu-

ma la forma (10.1.1) si dice sistematico tale denominazione è do-

vuta al fatto che i primi bit della parola di codice coincidono

con i bit informativi, i restanti sono utilizzati per effettuare i

controlli di parità definiti dalle colonne della matrice .

In pratica in corrispondenza a ogni codice lineare a blocco

non ambiguo esiste un codice sistematico ad esso equivalente.

L’utilizzo dei codici sistematici è auspicabile, in quanto, so-

lo per fare un esempio, consente di non effettuare nessuna deco-

difica sulla parola ricevuta, limitandosi ad osservarne i primi bit,

compensando, in questo caso, il degrado delle prestazioni con la

diminuzione della complessità del sistema.


10.2 - Matrice di controllo di parità

Dato un codice lineare a blocco sistematico, indichia-

mo con la generica parola d’ingresso e con la generica parola

di codice. Se prendiamo in considerazione soltanto le ultime

componenti della parola di codice, ponendo

possiamo scrivere:

[

] (10.2.1)

sostituendo a la sua espressione in termini della matrice otte-

niamo:

[

] [

]

( )

(10.2.2)

Sempre in virtù del fatto che il codice è sistematico possia-

mo scrivere anche:

(10.2.3)

che ci suggerisce di riscrivere l’ultima eguaglianza nella (10.2.2)

nella forma:

[

] (10.2.4)

La matrice che compare nella precedente prende il nome

di matrice di controllo di parità (parity check matrix), in quanto la

(10.2.4) è soddisfatta da tutte e sole le parole di codice.

10.3 - Codici duali

Osserviamo che la (10.2.4) implica l’ortogonalità tra la

generica parola di codice e ogni riga della matrice , le cui

righe essendo linearmente indipendenti sono in grado di generare

un sottospazio di ortogonale a , nel senso che com-


binando linearmente le righe di si ottengono sempre parole di

ortogonali a qualsiasi parola di .

Ci si rende facilmente conto del fatto che si può pensare a

come ad un codice ( ).

Permutando opportunamente le colonne della matrice si

può sempre rendere sistematico, in un certo senso lo è

anche senza permutarle, solo che in questo caso i bit informativi

coincidono con gli ultimi bit della parola di codice.

10.4 - Decodifica basata sulla sindrome

Supponiamo di ricevere una parola , affetta da un pattern

d’errore . Se sostituiamo a primo membro della (10.2.4) otte-

niamo:

(10.4.1)

è una parola di bit che prende il nome di sindrome della

parola ricevuta. Vi sono 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.

Osservando la (10.4.1) si rileva che gli elementi di uno

stesso laterale del codice hanno la stessa sindrome. Gli elementi di

un laterale si ottengono infatti sommando ad un qualsiasi elemen-

to 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 sindromi e l’insieme dei laterali che è esso stesso un gruppo,

detto gruppo quoziente indicato con

⁄ . La composizione tra

due laterali del gruppo quoziente si effettua individuando il coset


di appartenenza dell’elemento di ottenuto componendo due

elementi arbitrariamente scelti nei due laterali componendi.

Il gruppo delle sindromi è isomorfo al gruppo quo-

ziente di individuato dal suo sottogruppo .

Le considerazioni appena fatte ci permettono di concludere

che la decodifica a massima verosimiglianza può essere effettuata

calcolando la sindrome della parola ricevuta ed utilizzandola come

indirizzo di una cella di memoria in cui è scritto il coset leader del

laterale ad essa associato, che va sommato alla parola ricevuta per

effettuare la decodifica.

Tale tecnica comporta quindi un banco di memoria in

grado di contenere parole di bit.

In effetti essendo interessati solo ai bit informativi è

sufficiente memorizzare soltanto i primi 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 leader, anche se, inevitabilmente, al crescere delle

dimensioni della parola di codice, diventa anch’essa impraticabile,

a causa della crescita esponenziale della quantità di memoria di cui

necessita.

Capitolo - 11

CODICI DI HAMMING E LORO DUALI

11.1 - 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 . Affinché ciò sia possibile ciascun pattern d’errore di peso

deve essere un coset leader.

Abbiamo visto che un codice ( ) consta di parole di

bit. Esistono quindi distinti pattern d’errore di peso , ciascuno

dei quali, moltiplicato per fornisce la rispettiva sindrome.

Detta sindrome coincide con la colonna della matrice che corri-

sponde alla posizione dell’unico bit nel pattern d’errore. Quindi,

se vogliamo che il codice sia in grado di correggere tutti i pattern

d’errore di peso , è necessario che le colonne della matrice

siano tutte diverse tra loro e non nulle. Poiché ogni colonna della

matrice in questione ha elementi, deve necessariamente

essere:

(11.1.1)

La precedente scritta come uguaglian-

za definisce implicitamente una fami-

glia di codici, i codici di Hamming,

che sono in grado di correggere tutti

gli errori di peso e di rivelare quelli

di peso non superiore a due in quanto

si può mostrare che la loro vale

. Alcune soluzioni della (11.1.1) sono

riportate nella in Tabella 11.1.

3 1

7 4

15 11

31 26

63 57

127 120

Tabella 11.1 Alcuni valori di

e per i codici di Hamming


Il primo codice della tabella è in effetti un codice a ripe-

tizione, in sostanza ogni bit informativo viene inviato consecuti-

vamente tre volte, vi sono due sole parole di codice, la distanza di

Hamming tra esse, quindi anche la del codice, è , il codice è

in grado di correggere errori singoli, la regola di decisione a massi-

ma verosimiglianza per questo codice consiste 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 (9.11.1) è

verificata come uguaglianza per tutti i codici di Hamming risulta

infatti:

⌊

⌋ (11.1.2)

da cui

∑ ( )

(11.1.3)

ma per i codici di Ham-

ming I co-

dici di Hamming sono

quindi codici perfetti.

Esempio 11.1

Una possibile matrice del

secondo codice della

Tabella 11.1, il 7,4,è data

da:

[

]

Fig.E 11.1 - Schema a blocchi del Codice 7,4 di Hamming

1 2 3 4

1 2 3 4 5 6 7

clk outT

S

clk inT

Codici di Hamming e loro Duali 131

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 (10.2.4).

Ricordiamoci che le prime quattro colon-

ne di possono essere permutate tra loro

senza che le caratteristiche del codice cam-

bino.

Basandoci sulla (10.2.4) e sulla (10.1.1)

potremo facilmente scrivere la matrice ge-

neratrice del codice:

[

]

il relativo schema a blocchi è mostrato in

Fig.E 11.1, la lista delle parole del codice è

elencata nella Tabella 11.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. 9.1

11.2 - Duali dei codici di Hamming

Nel caso dei duali dei codici di Hamming, le colonne della

loro matrice generatrice sono tutte e sole le parole binarie non

nulle che si possono scrivere con bit vi saranno quindi esatta-

mente colonne nella matrice generatrice. La matrice

definisce quindi un codice ( ) , le cui parole non nulle

hanno tutte peso .

Infatti ogni riga della matrice generatrice contiene per co-

struzione bit zero e bit uno. Le restanti parole del

codice si ottengono combinando linearmente le righe della ma-

trice generatrice, tale combinazione lineare, a ben vedere, consiste

nel cancellare un sottoinsieme di righe dalla matrice generatrice e

sommare le restanti.

Per semplificare il ragionamento immaginiamo di aggiun-

gere alla matrice una colonna nulla, sia la matrice estesa così

ottenuta. Osserviamo che le parole del codice ( ) generato da

Codice di Hamming 7,4 0000 000 0001 111 0010 011 0011 100 0100 101 0101 001 0110 110 0111 001 1000 110 1001 001 1010 101 1011 010 1100 011 1101 100 1110 000 1111 111

Tabella 11.2 - Parole del codice Hamming 7.4


differiscono da quelle generate da solo per il fatto di avere un

bit in più, che essendo generato dalla colonna identicamente nulla,

vale sistematicamente . Possiamo quindi affermare che le parole

corrispondenti dei due codici, cioè generate dalla stessa parola di

hanno lo stesso peso.

Osserviamo adesso che la cancellazione di una riga in da

luogo ad una sottomatrice ( ) che ha le colonne uguali a due a

due; se cancellassimo due righe avremmo una sottomatrice ( )

con colonne uguali a quattro a quattro e così via.

In generale quindi cancellando righe di , con ,

avremo una sottomatrice ( ) di righe con solo colonne

distinte che non potranno essere altro se non tutte le parole

binarie di bit.

Il peso della parola di codice ottenuta componendo le

righe di ( ), è uguale al numero di colonne che hanno un numero

dispari di al loro interno. Ci si convince facilmente che

esattamente la metà delle colonne diverse tra loro hanno

peso dispari. Il peso della parola di codice ottenuta componendo

le righe vale

, indipendente dal numero di righe

cancellato, pur di non cancellarle tutte, in questo caso otterremo

la parola di codice nulla che ha peso .

Possiamo quindi concludere che la distanza minima per

codici generati da matrici di tipo , o da matrici di tipo vale

, che è anche, la distanza tra due parole di codice qualsiasi.

11.3 - Codici ortogonali e transortogonali

Immaginiamo di utilizzare un codice generato da una matri-

ce del tipo , introdotta nel § 11.1 - , con una segnalazione di tipo

antipodale, associando cioè ai bit un impulso di segnalazione in

banda base ( ) (la cui durata, per semplicità possiamo pensare sia

non maggiore dell’intervallo di segnalazione ), e ai bit il suo

opposto. Alla generica parola di codice verrà quindi associato il

segnale in banda base:

Codici di Hamming e loro Duali 133

( ) ∑( ) ( ( ) )

(11.3.1)

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

stinte parole di codice otteniamo:

∫ ∑( ) ( ( ) )

∑( ) ( ( ) )

∑∑( ) ( )

∫ ( ( ) ) (

( ) )

∑( ) ( ) ∫ ( ( ) ) (

( )

( ) ) ∑( )( ) ∫ ( ) ( )

∑( )(

)

(11.3.2)

nella precedente indica l’energia del bit informativo, conse-

guentemente l’energia specifica dell’impulso di segnalazione, che

tiene conto del Rate

del codice, vale

. La sommatoria a

ultimo membro vale in quanto la distanza di Hamming tra due

parole di codice distinte vale .

Sotto le ipotesi appena fatte i segnali associati alle parole del

codice generato dalla matrice di parità estesa di un codice di

Hamming sono a due a due ortogonali. Per quanto riguarda i

codici duali dei codici di Hamming, nelle stesse condizioni

generano un set di segnali isoenergetici in uno spazio a

dimensioni. Detti segnali non sono più mutuamente ortogonali,

anche se la distanza tra una qualunque coppia di segnali è la stes-


sa. I codici duali dei codici di Hamming si chiamano transortogonali.

Rispetto ai codici generati da matrici di tipo i codici transorto-

gonali hanno il vantaggio a parità d’energia di consentire un

aumento dell’energia associata al bit della parola di codice, in virtù

del rate più basso, per questo le loro prestazioni sono leggermente

migliori.

Capitolo - 12

CODICI CONVOLUZIONALI

12.1 - Premessa

I codici convoluzionali furono proposti per la prima volta

da P. Elias nel 1955, ma hanno trovato ampia applicazione dopo

che A. J. Viterbi propose nel 1967 un efficiente algoritmo di deco-

difica. Nei codificatori convoluzionali la parola prodotta non di-

pende soltanto dalla parola emessa dalla sorgente al tempo pre-

sente, ma anche da quelle emesse precedentemente. Si tratta quin-

di di un codificatore dotato di memoria.

12.2 - Struttura del codificatore

Lo schema di prin-

cipio di un codificato-

re convoluzionale è

mostrato in Fig. 12.1.

I simboli emessi dalla

sorgente appartengo-

no a un alfabeto di

cardinalità assegnata

ed i sommatori opera-

no modulo la cardina-

lità dell’alfabeto.

Lo schema di Fig.

12.1, a prima vista,

non differisce da quello di un codificatore per codici a blocchi, se

non fosse per la dimensione dello shift register d’ingresso che è

maggiore di quello d’uscita. La differenza sostanziale tra il codi-

ficatore di figura e quello di uno a blocchi, consiste nel fatto che il

registro d’uscita, nel codificatore di figura, viene letto ogni due

simboli emessi dalla sorgente.

Fig. 12.1 - Schema di principio di un codificatore convoluzionale

2

3 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


In generale in un codificatore convoluzionale il numero di

simboli che costituiscono 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 deno-

minato lunghezza di vincolo (costraint lenght) ( in quel che segue).

Da quanto appena detto discende che la parola di codice

non dipende soltanto dalla parola d’ingresso attuale ma anche

dalle parole precedentemente emesse dalla sorgente.

Nello schema di Fig. 12.1 la lunghezza di vincolo , la

parola di codice dipende pertanto dalla parola corrente e dalle

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. 12.1) e quella della parola di codice generata (3 in Fig.

12.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à), i simboli utilizzati appartengono tipicamente a .

12.3 - Matrice generatrice e generatori.

I codificatori convoluzionali come si evince dalla Fig. 12.1

figura del paragrafo precedente sono lineari. Osserviamo che, se la

lunghezza di vincolo fosse unitaria, degenererebbero in un codifi-

catore a blocco. Se, come sempre accade, la lunghezza di vincolo

è maggiore di uno la sequenza d’uscita dipende dall’intera sequen-

za in ingresso. In ogni caso possiamo affermare che la sequenza

codificata associata a una generica sequenza informativa può sem-

pre essere ottenuta come combinazione lineare delle risposte che

il codificatore genererebbe in corrispondenza a sequenze “canoni-

che”, cioè a sequenze seminfinite contenenti un unico bit .


In Tabella 12.1 sono mostrate le sequenze d’uscita che si

otterrebbero dal-

l’analisi del codi-

ficatore Fig. 12.1

in corrispondenza

alle citate sequen-

ze, assumendo

che, in assenza di

una sequenza in

ingresso, tutte le

celle dello shift re-

gister contengano

il bit . Le se-

quenze 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 12.1essa è a

blocchi del tipo:

[

] (12.3.1)

dove le rappresentano matrici e gli zeri indicano matrici

nulle delle stesse dimensioni. Osservando la struttura della gene-

rica ci si rende conto che essa è in realtà la matrice generatrice

di un codice a blocchi , il suo generico elemento vale cioè

solo se l’ -esima cella dell’ -esimo blocco dello shift register di

ingresso è connessa al sommatore - esimo.

La (12.3.1) è di scarsa utilità pratica. Le matrici po-

trebbero essere si usate per descrivere la struttura del codificatore,

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 12.1 - sequenze di uscita del codificatore di Fig. 12.1 in corrispondenza alle sequenze canoniche


ma, anche a questo scopo, esse si rivelano in genere meno effi-

cienti dei cosiddetti generatori.

I generatori sono vettori binari ciascuno con compo-

nenti. Dove la -esima componente dell’ -esimo generatore vale

solo se l’ -esimo sommatore è connesso all’ -esima cella del

registro d’ingresso.

Per il codificatore di Fig. 12.1 i generatori sono:

{

(12.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 costituenti 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

sono in numero pari alla lunghezza di vincolo che può essere del-

l’ordine delle decine. Inoltre i generatori si prestano a essere rap-

presentati in notazione diversa da quella binaria, tipicamente quel-

la ottale, rappresentando cioè gruppi di tre bit con la corrispon-

dente cifra ottale per il nostro codificatore ciascun generatore si

può rappresentare mediante due cifre ottali in particolare per il

nostro esempio si ha:

(12.3.3)

12.4 - Diagramma di stato del codificatore.

La matrice generatrice, non è certamente uno strumento di

semplice impiego per analizzare un codificatore convoluzionale. I

generatori, sono sì uno strumento efficace per descrivere la strut-

tura del codificatore, ma mal si prestano al calcolo della sequenza

che esso genera in uscita. Un modo alternativo, certamente più ef-


ficace, per descrivere il comportamento del codificatore è quello

di tener conto del fatto che l’uscita prodotta in un certo istante di-

pende oltre che dalla parola d’ingresso corrente anche dalla storia

della sequenza d’ingresso, in particolare l’uscita dipende dai

( ) bit d’ingresso che hanno preceduto la parola corrente.

In altri termini, noti i ( ) bit precedenti e i bit della

parola corrente, possono essere univocamente determinati, sia

l’uscita corrente, sia i ( ) bit che contribuiranno unitamente

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

seguente. Osserviamo che esistono esattamente ( ) contenuti

distinti per le celle del registro che costituiscono la memoria del

sistema. Possiamo dire pertanto che il codificatore può assumere

( ) stati diversi ( 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

sostanza un codificatore convoluzionale non è altro che una

macchina a stati finiti.

Gli stati del codificatore possono essere associati ai vertici

di un grafo (vedi Esempio 2.1) due vertici vengono connessi tra-

mite un lato se esiste una parola di ingresso che induce la tran-

sizione tra i due stati. Ad ogni lato potremo associare un’etichetta

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

corrispondente parola di uscita che dipende dal vertice da cui il

suddetto lato fuoriesce.

Osserviamo che da ogni vertice origineranno e si dipar-

tiranno esattamente lati, tanti quante sono le possibili parole

d’ingresso (nel nostro esempio 4). Quindi ogni vertice è di grado

( ). Il grafo è anche connesso in quanto, comunque scelti due

vertici distinti, esiste sempre un percorso che li congiunge, os-

serviamo che tale percorso è costituito al più da ( ) lati.


Il grafo relativo al codificatore di Fig. 12.1 è mostrato in

Fig. 12.2 dove si

sono utilizzati co-

lori diversi per

distinguere le pa-

role d’ingresso as-

sociate ai lati. Nel-

la stessa figura si

sono indicate solo

alcune parole d’u-

scita per non pre-

giudicarne la leggi-

bilità.

Tracciato che

sia il grafo del co-

dificatore, per dato stato iniziale, si può valutare la sequenza

codificata associata a una qualsiasi sequenza d’ingresso seguendo

il percorso da essa individuato ed annotando le corrispondenti

parole d’uscita. Ovviamente, per sequenze molto lunghe, anche

questa rappresentazione manifesta i suoi limiti. Si pensi al caso in

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

sequenza.

12.5 - Codici catastrofici

Osserviamo che ogni codificatore convoluzionale, essendo

lineare, associa alla sequenza d’ingresso nulla la sequenza nulla.

Il percorso associato alla sequenza d’ingresso identicamente nulla

nel grafo di Fig. 12.2 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, partendo dallo stato

zero, associa alla sequenza costituita solo da bit , la sequenza

come possiamo notare tale sequenza

seppur semi-infinita ha peso ; cioè, nonostante la sequenza

Fig. 12.2 - Grafo del codificatore mostrato in Fig. 12.1

1000

1010

0100

0101

1111

1100

0001

0010

0011

0110

0111

1001

10111101

1110

0000

00

01

10

11

111

000

100

100

111


d’ingresso considerata sia quella a massima distanza dalla se-

quenza nulla, le rispettive sequenze codificate distano tra loro non

più di indipendentemente dalla loro lunghezza. Il codificatore di

Fig. 12.1 è in realtà un esempio di Codice catastrofico. Tale

denominazione discende dal fatto che da un codificatore ci si

aspetterebbe, 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. un codificatore, come ad esempio quello di Fig. 13.1, è

catastrofico se il suo diagramma di stato contiene un selfloop che

associa a una parola d’ingresso di peso non nullo la parola d’uscita

nulla, sicché "ciclando" su detto selfloop il peso della sequenza

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

catastrofico non perde la sua valenza che è puramente didattica.

12.6 - Trellis degli stati

I limiti all’utilizzo del grafo per lo studio di un codice con-

voluzionale, sono essenzialmente legati al fatto che in questa rap-

presentazione non compare il tempo.

Premesso che in quel che segue per brevità enumereremo

talvolta gli stati con il numero decimale corrispondente al conte-

nuto della memoria, supponiamo che all’istante iniziale il codifica-

tore si trovi nello stato , da esso all’istante , potranno essere

raggiunti nuovi stati figli e da ciascuno di questi ultimi all’i-

stante ne potranno essere raggiunti per un totale di

stati figli raggiungili all’istante a partire dallo stato iniziale do-

po due parole d’ingresso.

Ci rendiamo conto del fatto che all’istante ( ) tutti i

possibili stati del codificatore saranno raggiungibili. Ciò è vero

anche in virtù del fatto che, per la struttura stessa del codificatore,

a prescindere dallo stato in cui si trova, a parole d’ingresso distinte

corrispondono stati di arrivo distinti.


Quanto appena detto può essere rappresentato graficamen-

te mediante il trellis (letteralmente, ma è “infelice”, graticcio) degli

stati del codice. Il trellis associato al codificatore di Fig. 12.1 è rap-

presentato in Fig. 12.3 Come possiamo notare il trellis è un al-

bero, che ha origine nello stato in cui si trova il codificatore all’i-

stante iniziale, che generalmente, ma non necessariamente, è lo

stato . Esso costituisce la radice dell’albero, da cui si dipartono i

lati associati a tutte le possibili parole di ingresso che terminano

sui vertici raggiungibili all’istante da ciascuno di detti vertici

si dipartiranno ulteriori lati che termineranno su vertici figli

al tempo .

Fig. 12.3 – Trellis degli stati del codificatore di Fig. 12.1

0 8sT6

sT4

sT2

sT

0000

0100

1000

1100

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

0000

00 01 10 11

000 000 000 000


Al tempo ( ) tutti gli stati vengono raggiunti da un

lato ed al passo successivo la sezione di trellis, cioè l’insieme dei lati

compresi tra i vertici relativi a due istanti di tempo consecutivi, è

completa, nel senso che con-

tiene tutti i possibili lati, tutte

le sezioni successive saranno

complete, uguali tra loro ed,

idealmente, in numero infi-

nito. Ogni sezione si può eti-

chettare con un numero che

esprime la “profondità” della se-

zione cioè la collocazione tem-

porale di una data sezione nel

trellis.

Seguire l’evoluzione del-

l’uscita sul trellis è semplice in

quanto nel percorso associato alla sequenza d’ingresso non vi pos-

sono essere sovrapposizioni.

Esempio 12.1

Si Calcoli l’uscita del codice di rate

individuato dai generatori

. In corrispondenza alla sequenza d’ingresso .

I due generatori rappresentati in binario sono:

Fig.E 12.1 - schema del codificatore

convoluzionale rate

Fig.E 12.2 – Trellis del codice convoluzionale rate


e corrispondono allo schema mostrato in Fig.E 12.1. Il codificatore ha

stati, il suo trellis è mostrato in Fig.E 12.2, nella stessa figura è

evidenziato il percorso associato alla sequenza di ingresso , la

corrispondente sequenza d’uscita è quindi: .

È interessante osservare che un ulteriore zero nella sequenza

d’ingresso riporterebbe il codificatore allo stato zero.

Capitolo - 13

L’ALGORITMO DI VITERBI

13.1 - Decodifica hard e soft di un codice convoluzionale.

Occupiamoci adesso della decodifica utilizzando il criterio

MV.

Facciamo riferimento allo schema di principio mostrato in

Fig. 13.1. Esso rappresenta una sorgente binaria che emette una

sequenza binaria di bit, , cui è connesso un codificatore

convoluzionale con rate

che produce una sequenza codificata di

bit, , che modula antipodalmente un impulso di segnala-

zione ( ) in banda base di durata non maggiore dell’intervallo

assegnato a ogni bit codificato ottenendo il segnale:

( ) ∑( )

( ( ) ) (13.1.1)

Fig. 13.1 - 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.

n t

filtroadattato

rivelatorea soglia

decodificatorehard

decodificatoresoft

S

bT

1

kN

i ix

Codificatoreconvoluzionale

Modulatore

sT

sT

1

nN

i ic

r t s t n t

1

2 1 1nN

i s

i

s t c p t i T

1 12 1

nN nN

i i ii ir c n

{bi}i=1

nN

1

ˆnN

i ic


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

un rumore gaussiano ( ) con densità spettrale di potenza bilatera

.

Il segnale ricevuto ( ), trascurando ritardo ed attenuazio-

ne, sarà quindi ( ) ( ) ( ).

Il ricevitore di figura è costituito da un filtro adattato all’im-

pulso di segnalazione la cui uscita viene campionata a cadenza ,

producendo la sequenza , che per le ipotesi fatte non sarà

affetta da interferenza intersimbolica. Avremo cioè

in cui è una variabile aleatoria Gaussiana a media nulla e va-

rianza η. Ne segue che la generica , condizionata all’invio di è

la realizzazione di una variabile aleatoria gaussiana a media

e varianza η. Inoltre Le condizionate all’invio di una data

saranno mutualmente statisticamente indipendenti.

In Fig. 13.1 Abbiamo a questo punto indicato due alterna-

tive:

- la prima (ramo superiore in blu in Fig. 13.1) consiste

nell’utilizzare un rivelatore a soglia che fornirebbe in uscita

una sequenza binaria stimata , da dare in “pasto” ad un

decodificatore che in questo caso sarebbe di tipo hard;

- la seconda (ramo inferiore in verde in Fig. 13.1) consiste

nell’utilizzare un decodificatore che si basa direttamente sulla

; in questo caso il nostro decodificatore sarebbe di tipo

soft.

Indipendentemente dal tipo di decodificatore viene pro-

dotta una sequenza informativa stimata ottenuta in

corrispondenza a una sequenza codificata , cioè una sequen-

za che corrisponde ad un percorso sul trellis del codificatore.

Ovviamente non è detto che i due decodificatori produca-

no la stessa e conseguentemente la stessa sequenza infor-

mativa stimata .


In quel che segue supporremo di voler decodificare una se-

quenza di lunghezza finita. Supporremo anche che il decodificato-

re hard o soft che sia:

- conosca la struttura del codificatore convoluzionale;

- conosca lo stato iniziale in del codificatore;

- conosca lo stato finale fin del codificatore,

Osserviamo che la conoscenza dello stato finale da parte

del decodificatore, implica che il codificatore abbia provveduto ad

aggiungere alla sequenza informativa un suffisso in grado di con-

durre 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.

In linea di principio la decodifica MV hard della sequenza

costituita da -uple di bit in uscita al rivelatore a soglia è

semplice, è, infatti, sufficiente scegliere la sequenza ammissibile2

che ha la minima distanza di Hamming dalla generata dal

rivelatore, scegliendo eventualmente a caso qualora dovesse esser-

vi 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 se-

quenza che, pensata come un punto di , ha la

minima distanza Euclidea dalla sequenza corrispondente al

segnale ricevuto, rappresentata nello stesso spazio.

Va da se che, in questo caso, la probabilità che due sequen-

ze ammissibili abbiano la stessa distanza da quella ricevuta è nulla.

2 per sequenza ammissibile intendiamo una sequenza associabile ad un

percorso sul trellis che abbia inizio in e termini in .


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 espo-

nenziale del numero di sequenze ammissibili, sia per il ritardo che

un tale decodificatore comporterebbe. Sarebbe infatti indispensa-

bile attendere la ricezione dell’intera sequenza prima che il proces-

so di decodifica possa avere inizio.

13.2 - L’algoritmo di Viterbi

In questo paragrafo descriveremo un algoritmo di decodi-

fica che, con modifiche non concettuali, può essere impiegato sia

per decodificatori hard che soft dei codici convoluzionali.

In quel che segue chiameremo:

- metrica di ramo la distanza di Hamming, o il quadrato della

distanza Euclidea, tra gli bit

codificati

che etichettano il ramo e la porzione di sequenza ricevuta cor-

rispondente precisamente

(

)

{

∑ ( )

∑ ( ) (

)

(13.2.1)

(ad apice abbiamo indicato la sezione di trellis cui il ramo ap-

partiene ed i pedici, individuano lo stato di partenza e quello

di arrivo del ramo in esame);

- percorso una sequenza ininterrotta di rami che origina in in

- lunghezza del percorso il numero di rami compongono il percor-

so

- metrica di percorso la somma delle metriche di ramo che com-

pongono il percorso;


- cammino una sequenza ininterrotta di rami del tipo

- 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 ini-

ziale in cui si trova il codificatore all’arrivo di una sequenza infor-

mativa, supponiamo sia lo stato zero. Al primo passo, osservando

la sequenza ricevuta, il decodificatore può etichettare ciascuno dei

rami del trellis che emergono dallo stato iniziale, con la metrica

ad essi associata, calcolata mediante la prima o la seconda delle

(13.2.1), a seconda che la decodifica sia di tipo hard o soft rispetti-

vamente. Il decodificatore provvederà anche ad etichettare gli stati

raggiunti con le metriche dei percorsi che vi pervengono. Le me-

triche di percorso in questo 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 stati raggiunti emerge-

ranno 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:

- 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 , in quanto fino a tale passo ogni

stato viene raggiunto al più da un percorso.


Al - esimo passo potremo ancora associare a ogni ramo la

sua metrica, ma per associare le metriche di percorso agli stati sor-

gerà un problema. Esistono infatti percorsi distinti che termi-

nano in ciascuno stato.

Se consideriamo un cammino nel trellis di lunghezza

che abbia origine in uno stato in cui confluiscano percorsi di

lunghezza , giustapponendo il cammino a ciascun percorso di

lunghezza otterremmo percorsi ammissibili di lunghezza

. La metrica di ciasuno di essi sarà data dalla somma della

metrica di uno dei percorsi di lunghezza 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 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à do-

vrebbe scegliere a caso.

Dal - 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 decodifi-

catore conoscendo lo stato di arrivo si limiterà a considerare solo i

percorsi che vi confluiscono scegliendo il migliore tra essi

(quello che ha accumulato la metrica minore).

Abbiamo appena descritto l’algoritmo di Viterbi.

13.3 - Efficienza dell’algoritmo di Viterbi

Appare evidente la riduzione di complessità di questo algo-

ritmo rispetto alla ricerca esaustiva teorizzata nel paragrafo prece-

dente. Infatti ad ogni passo di decodifica, a parte il transitorio

iniziale, dovremo calcolare metriche di ramo per ciascuno dei

( ) stati iniziali della sezione di trellis e utilizzarle per calcola-


re le metriche di percorsi. Di questi ultimi solo ( )

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 su tutti i percorsi ammissibili il cui numero cresce

esponenzialmente al crescere della lunghezza della sequenza

informativa.

Va comunque sottolineato che la complessità dell’algoritmo

di Viterbi cresce esponenzialmente con la lunghezza di vincolo

del codificatore.

Un altro vantaggio nell’utilizzo 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” finiscono

con l’avere una parte iniziale in comune. La parte della sequenza

informativa associata alla parte comune a tutti i percorsi non

potendo subire alcuna modifica potrà essere resa immediatamente

disponibile in uscita al decodificatore. Potremo cioè utilizzare una

decodifica a finestra mobile che limita sia la latenza sia il fabbisogno di

memoria del decodificatore.

Capitolo - 14

PRESTAZIONI DEI CODICI CONVOLUZIONALI

14.1 - Distanza libera di un codifie convoluzionale.

I codici convoluzionali sono come abbiamo già detto linea-

ri, nel senso che la somma di due sequenze codificate è ancora

una sequenza codificata, esattamente quella che si otterrebbe co-

dificando la somma delle corrispondenti sequenze informative.

Ciò significa che possiamo valutare le prestazioni del codice

in termini di probabilità d’errore ammettendo che venga inviata la

sequenza nulla e valutare la probabilità che, a causa del canale,

venga rivelata una sequenza ammissibile diversa.

Per i nostri scopi è utile definire alcune grandezze associate

al codificatore. La prima è la cosiddetta distanza colonna ( )

essa è un’applicazione che associa ad ogni livello di profondità del

trellis del codice la minima distanza di Hamming ottenibile dalla

sequenza nulla prendendo in considerazione tutte le possibili se-

quenze d’ingresso cui corrispondono percorsi sul trellis che si di-

scostano da quello relativo alla sequenza nulla a partire dall’istante

iniziale. Il limite di ( ) per si chiama distanza libera,

, del codice. Il percorso cui corrisponde la distanza libera non è

necessariamente unico, ma certamente salvo il caso in cui il codice

sia catastrofico è un percorso che si 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.

154 Capitolo - 14

14.2 - Funzione di trasferimento di un codificatore convolu-zionale.

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 consi-

deriamo il diagramma

degli stati del codifi-

catore, sopprimiamo

il self loop associato

allo stato zero, quindi sdoppiamo lo stato zero in due stati uno,

sorgente, da cui fuoriescono i rami ed uno, pozzo con solo rami

entranti come in Fig. 14.1. Nella stessa figura si può notare anche

che i rami del grafo sono stati etichettati con dei trinomi

l’indeterminata vi compare sempre con grado , la sua funzione

è in realtà solo quella di tener conto del passaggio attraverso il

ramo, il grado di esprime il peso della parola informativa

associata al ramo esso è quindi compreso tra e , il grado di

esprime il peso della parola di codice associata al ramo, e non può

quindi essere maggiore di .

Basandoci sulla teoria dei grafi orientati e pesati possiamo

ricavare la funzione di trasferimento tra il nodo sorgente ed il

nodo pozzo.

Si può procedere in due modi, il più semplice consiste nello

scrivere il sistema lineare di equazioni che il grafo rappresenta.

Ciò si ottiene associando a ogni nodo un’incognita del sistema.

In corrispondenza a ciascun nodo possiamo scrivere un’e-

quazione che, detta l’incognita associata al nodo -esimo e la

trasferenza associata al ramo che emerge dal nodo -esimo e

converge in quello -esimo, sarà del tipo:

Fig. 14.1 – Grafo modificato del Codice

rate ⁄

4

1 0

2 35

6 70

JLD

L

JLD

JLD

LD2


∑

( )

(14.2.1)

In corrispondenza al ramo sorgente non si scrive alcuna

equazione essendo quest’ultimo privo di rami entranti. A titolo

d’esempio, denominando rispettivamente e le variabili as-

sociate al nodo sorgente ed al nodo pozzo in cui abbiamo sdop-

piato lo stato , scriviamo le equazioni associate al grafo di Fig.

14.1:

{

(14.2.2)

Possiamo quindi procedere all’eliminazione di tutte le varia-

bili ad eccezione delle e . Utilizzando ad esempio le prime

tre equazioni otteniamo:

{

(14.2.3)

quindi, procedendo in modo analogo, dopo qualche passaggio ot-

teniamo:

( ) (14.2.4)

156 Capitolo - 14

la ( ) prende il nome di funzione di trasferimento del codi-

ce.

Se con la tecnica della divisione lunga espandiamo la

(14.2.4), pensando il numeratore e il denominatore come polino-

mi nell’indeterminata , possiamo ancora scrivere:

( ) ( ) (

) (

) (

)

(14.2.5)

dal coefficiente della potenza più piccola di a secondo membro

della precedente, desumiamo che vi è un cammino con peso

d’ingresso che si discosta dallo stato per tornarvi dopo rami

accumulando un peso d’uscita pari a . Ne segue che la distanza

libera del codice in parola sarà .

Osservando il coefficiente della potenza di immediata-

mente superiore scopriamo che esistono anche tre percorsi con

peso d’uscita , di cui: uno di lunghezza e peso d’ingresso ; il

secondo di lunghezza e peso d’ingresso ; il terzo di lunghezza

con peso d’ingresso .

Qualora fossimo interessati solo al peso delle sequenze co-

dificate che si discostano dalla sequenza nulla per poi ricon-

giungersi con essa, potremmo porre nella (14.2.4) o nella (14.2.5)

e , ottenendo

( ) (14.2.6)

In generale la funzione di trasferimento di un codice con-

voluzionale può essere espressa nella forma:

( ) ∑ ∑ ∑ ( )

(14.2.7)


dove ( , , ) 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 le variabili che non ci

interessano e sommando rispetto ai rispettivi indici, otteniamo

delle funzioni di trasferimento semplificate, ad esempio ponendo

e nella (14.2.7) otteniamo

( ) ( ) ∑ ∑ ∑ ( )

∑ ( )

(14.2.8)

dove ( ) ∑ ∑ ( )

.

14.3 - 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 infor-

mativo anche alla cosiddetta probabilità di primo evento d’errore,

o anche probabilità d’errore di nodo. ssa esprime la probabilità

che in un certo istante la sequenza stimata si discosti da quella ef-

fettivamente trasmessa per poi ricongiungersi con essa.

Possiamo assumere ai fini del calcolo che la sequenza tras-

messa sia quella identicamente nulla, indicheremo con

tale sequenza che corrisponde al percorso semiinfinito sul trellis

che non si discosta mai dallo stato . Possiamo fare tale ipotesi in

virtù della linearità del codificatore e del fatto che la decodifica è a

massima verosimiglianza.

Sappiamo che il decodificatore opera le sue scelte basandosi

sulla sequenza binaria prodotta dal rivelatore a soglia nel

caso di decodifica hard, ovvero sulla sequenza reale dei

campioni in uscita al filtro adattato per decodifica soft.

158 Capitolo - 14

Ammettiamo che fino alla profondità nel trellis il deco-

dificatore abbia attribuito al percorso la metrica minore e che al

passo successivo abbia inizio un cammino ( )

( ) che si

discosta dallo stato per ritornarvi dopo sezioni di trellis. Alla

profondità il decodificatore lascerà sopravvivere un solo

percorso tra quelli che pervengono allo stato se il percorso ,

coincidente con fino alla profondità nel trellis e con da

fino alla sezione , avrà accumulato la metrica minore

di , quest’ultimo verrà scartato. è un possibile primo evento

d’errore. Va da sé che vi è un’infinità numerabile di possibili primi

eventi d’errore, cioè tutti i cammini che si discostano dallo stato

zero per poi ricongiungersi ad esso.

Purtroppo il calcolo esatto della probabilità di primo evento

d’errore è impraticabile. Possiamo tuttavia maggiorare la proba-

bilità cercata, basandoci sull’union bound.

Detto il cammino coincidente con tra le sezioni

e Osserviamo che la scelta del decodificatore sarà

determinata soltanto dalle metrica accumulata dai cammini e

, in quanto fino al passo i due percorsi coincidevano quindi

condividevano la stessa metrica.

Per applicare l’union bound dobbiamo valutare, in corri-

spondenza a ciascun primo evento d’errore, la probabilità che det-

to evento si manifesti nell’ipotesi che il decodificatore possa sce-

gliere solo tra il percorso corretto e quest’ultimo.

Ciò, detto in altri termini, equivale a calcolare la probabilità

che, a causa del rumore introdotto dal canale BSC, la porzione di

sequenza ( ) in uscita al rivelatore a soglia, per il decodifi-

catore hard (la porzione ( ) di campioni in uscita al filtro

adattato per quello soft) corrispondente alle sezioni del trellis

che contengono i due cammini e , appartenga alla regione di

decisione di malgrado sia stata inviata la sequenza identicamen-

te nulla, corrispondente a


Ci si convince facilmente che la somma di tutte le probabi-

lità 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 primi eventi d’errore sopra

descritti.

Detta la regione di decisione di nell’ipotesi che il

decisore sia chiamato a scegliere tra e , possiamo scrivere:

∑ (

( )

)

(14.3.1)

Nel caso di decodifica hard, è opportuno osservare che ai

fini del calcolo della probabilità che compare ad argomento della

sommatoria nella (14.3.1), non contribuiscono i bit codificati di

uguali a quelli di (cioè i bit nulli di ), in quanto quale che sia

il corrispondente bit della sequenza ricevuta esso apporterebbe un

eguale contributo alle distanze di ( ) da entrambi i cammi-

ni.

Indichiamo con ( ) il peso del cammino . Osserviamo

che se ( ) è dispari, posto ⌊ ( )

⌋ , il decodificatore sce-

glierà il cammino ogniqualvolta il numero di bit 1 di ( )

che corrispondono ai bit 1 di risulti maggiore o uguale a . La

probabilità che ciò accada, condizionata all’invio della sequenza

nulla è data da:

( ( )

) ∑ ( ( )

) ( ) ( )

( )

(14.3.2)

dove ( ) indica il cammino stimato e indica la probabilità

di crossover del BSC con cui può essere schematizzata la parte

inclusa nel poligono tratteggiato in rosso del sistema di trasmis-

sione mostrato in Fig. 13.1

160 Capitolo - 14

Se il peso di è pari esisteranno ( ( ) ( )

) possibili sequen-

ze ricevute ( ) che hanno eguale distanza da e

. In

tale eventualità il decodificatore sceglierebbe in modo puramente

casuale tra e . La probabilità che venga scelto il cammino

sarà in questo caso espressa dalla:

( ( )

)

(

( ) ( )

) ( ) ( )

∑ ( ( )

) ( ) ( )

( )

⌊ ( )

⌋

(14.3.3)

Esempio 14.1

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. 13.1, assumendo che al bit codificato

competa un’energia

e che il rumore gaussiano

abbia una densità spettrale di potenza monolatera , 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

( ) ∫

√

( )

√

√ ∫

√

(

√ ) (

√ )

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:

√ √

Da cui:


(√

)

Osserviamo che la (14.3.2) e la (14.3.3), dipendono solo dal

peso di non dal numero di rami da cui esso è costituito. In altri

termini, tutti gli eventi d’errore di uguale peso avranno la stessa

probabilità di essere erroneamente scelti dal decodificatore indi-

pendentemente dal numero di rami in essi contenuti. Sulla base di

quest’ultima osservazione possiamo compattare in un'unica

espressione la (14.3.2) e la (14.3.3), indicando semplicemente con

un evento d’errore di peso , ottenendo:

( ) ( )

(

⌊

⌋) ( )

∑ ( ) ( )

⌊

⌋

(14.3.4)

Osserviamo adesso che la probabilità di primo evento di

errore di peso condizionata all’invio di una qualunque sequenza

è uguale a quella condizionata all’invio della sequenza nulla. Ne

segue che, se tutti i percorsi sul trellis sono equiprobabili, la pro-

babilità di errore di nodo di peso è uguale alla probabilità di

errore di nodo condizionata all’invio della sequenza nulla:

( ) ( ) (14.3.5)

La (14.3.4) ci suggerisce di riordinare la (14.3.1) accorpando

tutti gli eventi d’errore di ugual peso. Il numero di tali eventi può

essere dedotto dalla ( ) del codice. Tenendo conto della (14.2.8)

e della (14.3.5) possiamo quindi scrivere:

∑ ( ( )

)

∑ ( )

( )

(14.3.6)

162 Capitolo - 14

Nel caso di decodifica soft, basandoci sullo schema di Fig. 13.1 e

assumendo che l’impulso di segnalazione abbia energia ,

potremo scrivere:

∑ ( (

( ) {√ ( ( )

)}

( ))

( ( ) { √ }

( ))

( )

) ∑

(

√∑ ( √

( ))

( )

√

)

∑ (√ ( )

)

(14.3.7)

che può essere anche riformulata in termini dell’energia per bit

informativo, ponendo cioè , dove ⁄ è il rate del

codice e della densità spettrale di potenza monolatera

ottenendo:

∑ (√ ( )

)

(14.3.8)

Osserviamo che anche gli argomenti delle ( ) a secondo

membro della precedente non dipendono dalla lunghezza di ,

ma solo dal suo peso. La sommatoria a secondo membro della

precedente può quindi, anche in questo caso, essere riordinata ac-

corpando tutti gli eventi di errore di egual peso, ottenendo:

∑ ( ) (√

)

(14.3.9)

La precedente, a fronte di un’ulteriore maggiorazione può

assumere una forma più semplice da calcolare. Ricordando infatti


che vedi , per argomento non negativo, vale la disuguaglianza

( )

(vedi (4.9.14), possiamo ancora scrivere:

( ) (√

)

(

)

(14.3.10)

per mezzo della quale otteniamo:

∑ ( ) (√

)

∑ ( )

( )|

(14.3.11)

Anche nel caso della decodifica Hard possiamo maggiorare

ulteriormente la ricordando la maggiorazione di Bhattacha-

ryya (4.9.10) che ci permette di scrivere:

( ) ( )

(14.3.12)

Quest’ultima ci permette, partendo dalla (14.3.6) di scrivere:

∑ ( )

( ) ∑ ( )

( )

( )

(14.3.13)

La (14.3.11) e la (14.3.13) possono essere calcolate facil-

mente, disponendo della ( ) del codice, la (14.3.6) e la (14.3.9)

sono dei bound più stretti, ma possono essere calcolati solo in

modo approssimato, entrambe tuttavia sono in genere dominate

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 maggiorazione della probabilità d’errore

di nodo.

164 Capitolo - 14

14.4 - Bound sulla probabilità d’errore sul bit informativo.

Al fine di calcolare la probabilità d’errore sul bit d’informa-

zione , consideriamo una porzione di sequenza codificata

costituita da bit con (l’apice ha la sola funzio-

ne di etichetta). Nella corrispondente porzione di sequenza deco-

dificata costituita da bit saranno presenti un certo nu-

mero di bit errati. La presenza di bit errati è possibile solo se nella

si sono manifestati errori di nodo. Sappiamo che ad ogni

evento d’errore di nodo corrisponde un ben preciso numero di bit

informativi errati.

Indichiamo adesso con

la frequenza relativa d’errore

sul bit, della sequenza -esima. Essa è espressa dal rapporto tra il

numero di bit informativi errati e di quelli inviati. Il numero totale

di bit informativi errati può essere anche calcolato accorpando

tutti gli eventi d’errore di nodo caratterizzati da uno stesso nume-

ro di bit informativi errati. Indicando con ( ) il numero di

eventi d’errore che contengono esattamente bit informativi errati

manifestatisi nella -esima realizzazione dell’esperimento, possia-

mo scrivere:

∑

( )

(14.4.1)

La probabilità d’errore sul bit informativo si può ottenere

mediando su un numero idealmente infinito di repliche dello

stesso esperimento come segue:

∑

(14.4.2)

sostituendo la (14.4.1) nella precedente abbiamo:


∑

∑ ( )

∑

∑

( )

(14.4.3)

Nella precedente, prima di invertire l’ordine delle sommatorie, si è

tenuto conto del fatto che, al crescere della lunghezza della se-

quenza, si possono manifestare eventi d’errore con un numero ar-

bitrariamente grande di bit informativi errati. Si constata facilmen-

te che il limite all’interno della sommatoria di indice ad ultimo

membro della precedente, esprime la probabilità che si manifesti

un qualsiasi evento d’errore di nodo che contenga esattamente

bit informativi errati.

Indicando con l’insieme di tutti gli eventi d’errore con

bit informativi errati possiamo scrivere:

( )

∑

( )

(14.4.4)

la precedente può essere maggiorata applicando, come nel

paragrafo precedente, l’union bound:

( ) ∑ ( )

(14.4.5)

A partire dalla (14.4.3) possiamo ancora scrivere:

∑ ( )

∑ ∑ ( )

(14.4.6)

Ricordando la (14.2.7) che per comodità riscriviamo:

( ) ∑ ∑ ∑ ( )

(14.4.7)

166 Capitolo - 14

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:

∑ ∑ ( )

∑ ∑ ∑ ( ) ( )

∑ ∑ ( ) ( )

(14.4.8)

La precedente può essere ulteriormente maggiorata appli-

cando la (14.3.13) nel caso di decodifica hard o la (14.3.11) in

quella soft ottenendo rispettivamente:

∑ ∑ ( ) ( )

∑ ∑ ( )

(14.4.9)

∑ ∑ ( ) (

)

(14.4.10)

Osserviamo adesso che:

( )

|

∑ ∑ ∑ ( )

|

∑ ∑ ∑ ( )

∑ ∑ ( )

(14.4.11)

la quale ci permette di riscrivere la (14.4.9) e la (14.4.10) rispettiva-

mente nella forma più compatta:

( )

|

(14.4.12)

e


( )

|

(14.4.13)

Capitolo - 15

ANELLI DI POLINOMI

15.1 - Premessa

Abbiamo già fornito la definizione di campo e abbiamo anche

operato nel campo costituito da due soli elementi. Si possono

costruire anche campi finiti (Campi di Galois Galois Field) con un

numero d’elementi che sia un primo o una potenza di un primo.

Nel caso in cui il campo abbia un numero primo d’elementi,

l’addizione e la moltiplicazione tra elementi del campo si possono

effettuare in modo tradizionale avendo cura di ridurre il risultato

modulo .

Nella Tabella 15.1 a titolo d’esempio sono riportati i risul-

tati di tutte le possibili somme e prodotti tra coppie d’elementi di

, il campo di Galois con sette elementi.

15.2 - L’anello polinomi a coefficienti in

Consideriamo un campo e un’indeterminata , indichia-

mo con l’insieme di tutti i possibili polinomi (cioè di qualun-

que grado) nella variabile con coefficienti appartenenti ad , il

generico elemento di sarà cioè del tipo:

( )( )

(15.2.1)

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 15.1 - Campo di Galois di 7 elementi


dove è un intero non negativo qualsiasi e , essendo l’e-

lemento neutro rispetto all’addizione in . Conveniamo inoltre:

a) di utilizzare per le leggi di composizione del campo i simboli

utilizzati per il campo reale

b) di indicare con ( )( ) il polinomio identicamente nullo,

cioè coincidente con

c) di omettere l’apice tra parentesi per indicare un polinomio di

grado qualsiasi;

d) che dato ( )( ), per .

Siano ( )( ) ( )( ) due elementi di e un elemento

di , poniamo:

( ) ( ) ( ) ( )

( )

(15.2.2)

( )( ) ( )( ) ( )( )

(15.2.3)

e

( )( ) ( )( ) ( )( )

∑

(15.2.4)

Nella precedente, la sommatoria va calcolata secondo le regole di

, come pure il prodotto al suo interno.

In sostanza abbiamo appena introdotto in l’addizione

e la moltiplicazione. ispetto all’addizione è facile verificare che

è un gruppo commutativo, inoltre la moltiplicazione tra poli-

nomi in è commutativa e distributiva rispetto all’addizione.

è pertanto un anello commutativo, con identità, che, ovviamente,

coincide con l’identità del campo , che indicheremo con .

Inoltre il prodotto tra polinomi non nulli è non nullo. Il po-

linomio nullo si ottiene se e solo se almeno uno dei due moltipli-

candi è il polinomio nullo. Vale cioè anche la legge di annullamen-

to del prodotto.

Anelli di Polinomi 171

Quanto detto comporta che i polinomi

sono linearmente indipendenti su .

15.3 - Spazi di polinomi

Consideriamo il sottoinsieme ( )

di costituito da

tutti i polinomi di grado minore di . La somma di due elementi

di ( )

è ancora un elemento di ( )

. Inoltre, moltipli-

cando un qualunque elemento di ( )

per un elemento di ,

che coincide con ( )

, otteniamo un elemento di ( )

.

( )

è quindi uno spazio vettoriale su . La sua dimen-

sione è in quanto generabile tramite i suoi elementi linearmen-

te indipendenti .

Ci si convince facilmente che detto spazio vettoriale è iso-

morfo allo spazio costituito da tutte le -uple ordinate di ele-

menti di , basta infatti associare al polinomio ( )( ) ( )

,

l’elemento a se , ovvero l’ele-

mento se

Capitolo - 16

CODICI POLINOMIALI

Dati due interi e , scegliamo un polinomio

( )( ) che chiameremo polinomio generatore, tramite

( )( ) possiamo individuare il sottoinsieme ( )

che contiene i polinomi che si ottengono da tutti i possibili pro-

dotti tra ( )( ) e i polinomi ( ) ( )

.

Consideriamo adesso due elementi ( ) e ( ) appartenenti

a , quindi esprimibili rispettivamente nella forma:

( ) ( ) ( )( ) ( ) ( ) ( )( ) (16.1.1)

Comunque scelti risulta:

( ) ( ) ( ( ) ( )) ( )( ) (16.1.2)

La precedente ci mostra che ( ) è un sottospazio di ( )

,

quindi ne è anche un sottogruppo.

Il corrispondente sottoinsieme di è quindi un codice

di gruppo.

Abbiamo già detto (vedi § 7.2 - ) che la distanza di Ham-

ming tra parole di è 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 , che non è necessariamente unica.

Ci si convince anche facilmente del fatto che se s’intende

impiegare un codice polinomiale per la rilevazione d’errore è suf-

ficiente dividere il polinomio corrispondente alla parola ricevuta

per il polinomio generatore e verificare che il resto di tale divisio-

ne sia il polinomio nullo, per essere certi che la parola ricevuta ap-

partiene al codice.

Consideriamo adesso il caso dei codici polinomiali sul cam-

po essi sono certamente codici binari a blocchi, nel senso che

ammettono una matrice generatrice che si può facilmente

174 Capitolo - 16

costruire a partire da ( )( ) . Come righe di tale matrice si

possono scegliere infatti le stringhe dei coefficienti dei polinomi

di codice ottenuti moltiplicando il polinomio generatore per i po-

linomi . 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 am-

mettano un fattore comune di grado .

Capitolo - 17

IDEALI DI UN ANELLO DI POLINOMI

17.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, defini-

re 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

( ) , che ha la stessa cardinalità.

Sorge quindi spontaneo indagare sulla possibilità di indivi-

duare in

( ) due opportune leggi di composizione tra suoi

elementi che consentano di pensare a

( ) come ad un cam-

po di elementi. Sarebbe a questo punto possibile definire degli

isomorfismi tra

( ) e . Parliamo di isomorfismi perché

potrebbero esistere più leggi di composizione interna che soddi-

sfano le condizioni necessarie per interpretare

( ) come

campo.

Abbiamo già visto che ( )

è un gruppo commutativo

rispetto all’addizione tra polinomi, purtroppo non possiamo dire

lo stesso della moltiplicazione tra polinomi non fosse altro perché

( )

non è chiuso rispetto ad essa.

È quindi necessario definire una legge di composizione in-

terna per ( )

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.


17.2 - Ideali di un anello con identità.

Consideriamo un anello commutativo con identità dicia-

mo che un suo sottogruppo è un ideale se:

(17.2.1)

Qualora l’anello non fosse commutativo dovremmo distinguere

tra ideale sinistro e ideale destro, che potrebbero anche coincide-

re, nel qual caso si tratterebbe di un 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 . Con questa notazione risulta:

( ) ( )

(17.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 quo-

ziente di rispetto a . Dalla seconda delle (17.2.2) si deduce

facilmente che l’identità moltiplicativa è il laterale che si può indi-

care con , cioè quello che contiene l’identità moltiplicativa

di

Osserviamo che comunque scelto un elemento di , l’in-

sieme è un ideale, infatti ( ) ( )

( ) , inoltre indicando con , l’opposto di , ( )

e risulta ( ) ( ) ( ( )) , pertanto è un sotto-

gruppo d . Ogni ideale generato da un elemento di è detto

ideale principale.

Vale il seguente teorema:

Teorema 17.1 Tutti gli ideali dell’anello dei polinomi su un campo sono

principali.

Dimostrazione:

Ideali di un Anello di Polinomi 177

Osserviamo innanzitutto che ( )( ) è un ideale

principale per l’anello commutativo con identità . Consideria-

mo adesso un ideale di diverso da ( )( ) , in esso

scegliamo un elemento ( )( ) di grado minimo.

Comunque scelto un polinomio ( )( ) potremo scri-

vere:

( )( ) ( )( ) ( )( ) ( )( ) (17.2.3)

dove se (cioè ( )( ) non è un divisore di ( )( ) )

risulterà , ma in questo caso potremmo scrivere:

( )( ) ( )( ) ( )( ) ( )( ) (17.2.4)

che è un assurdo in quanto ( )( ) deve appartenere ad , come

mostra la precedente, pur avendo grado minore di che per ipo-

tesi è il grado minimo dei polinomi non nulli contenuti in . Deve

pertanto essere , o, che è lo stesso, ( )( ) ( )( ) ,

pertanto ogni ideale di è principale.

***********

Ci si convince facilmente che comunque scelto ,

anche il polinomio ( )( ) genera lo stesso ideale. Ovviamente

sarà sempre possibile individuare tra i generatori di un ideale

un solo polinomio monico cioè con il coefficiente del termine di

massimo grado pari ad .


Teorema 17.2 Dati due ideali di , siano ( ) ed ( )

se e solo se ( ) ha ( ) tra i suoi fattori.

***********

Dato un ideale ( )( ) e un polinomio ( )( ), sappiamo

che esistono ( )( ) e ( )( ) tali che si può scrivere:

( )( ) ( )( ) ( )( ) ( )( )

∪ {

(17.2.5)


che ci permette di affermare che ( )( )ed ( )( ) appartengono

allo stesso laterale di ( )( ) , cioè:

( )( ) ( )( ) ( )( ) ( )( ) (17.2.6)

Ciascun laterale di un ideale contiene un unico polinomio di

grado minimo, grado che, in virtù della (17.2.5), deve essere mino-

re di . 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 po-

linomi distinti di grado minore non potrà appartenere all’ideale

che essendo principale contiene solo polinomi di grado maggiore

od uguale ad , fatta eccezione per il polinomio nullo, che peral-

tro è l’unico polinomio di grado minimo contenuto nell’ideale

pensato come laterale di se stesso.

siste quindi un isomorfismo “naturale” tra l’anello

( )( ) ⁄ e l’insieme ( )

dei polinomi a coefficienti in

di grado minore di . si può quindi pensare a ( )

come ad un

anello commutativo con identità assumendo come risultato della

moltiplicazione tra due polinomi di ( )

il resto della divisio-

ne tra l’usuale prodotto dei due polinomi e ( )( ).

Capitolo - 18

CODICI CICLICI

18.1 - Rappresentazione polinomiale di un codice ciclico.

Definizione 18.1 Un codice lineare a blocchi si dice ciclico se e solo se comun-

que scelta una sua parola di codice

(18.1.1)

***********

In quel che segue mostreremo che i codici ciclici sono poli-

nomiali. Dovremo in altri termini mostrare che se un codice è ci-

clico allora la sua rappresentazione polinomiale ammette un poli-

nomio generatore.

Ad ogni parola di codice possiamo associare un polinomio

appartenente a ( )

come segue:

( )

(18.1.2)

denoteremo con ( ) l’insieme dei polinomi associati alle paro-

le di codice.

Risulta:

( )

(18.1.3)

Notiamo che per trasformare ( ) in ( ) occorre sottrarre a

( ) il polinomio :

( ) ( )

( )

(18.1.4)


ma poiché è il quoto della divisione tra ( ) e , dalla

precedente si deduce che ( ) è il resto della divisione appena

citata.

In altri termini, l’operazione corrispondente alla rotazione

ciclica di una parola in equivale, nel linguaggio dei polinomi, a

considerare il resto della divisione per del prodotto tra il

polinomio corrispondente alla parola ed . In simboli:

( ) ( ) ( ) (18.1.5)

18.2 - Teorema sui codici ciclici

Teorema 18.1 Condizione necessaria e sufficiente affinché un codice sia ciclico è che il

sottoinsieme ( ) dei laterali dell’ideale contenenti i polimomi

di codice sia un ideale di ⁄ .

Necessarietà:

L’insieme dei polinomi di codice ( ) essendo costituito

da polinomi appartenenti a ( )

costituisce anche un sottoin-

sieme dei coset leader (intesi come i polinomi di grado minimo)

dei laterali di ⁄ .

Inoltre:

a) il codice è lineare, pertanto è uno spazio vettoriale

sul campo , quindi la sua rappresentazione in forma polino-

miale ( ) deve essere anche un sottospazio di ;

b) l’anello ⁄ ha la struttura di spazio vettoriale sul

campo ;

c) esiste un isomorfismo naturale tra ( )

ed ⁄ ,

quello che associa ad ogni polinomio di ( )

l’unico late-

rale che lo contiene in ⁄ .

Dalle considerazioni appena fatte discende che l’immagine,

( ) , secondo l’isomorfismo sopra citato di ( ) in

⁄ è a sua volta un sottospazio vettoriale, quindi anche

un sottogruppo, ( ) di ⁄ , i cui elementi sono i la-

terali di che contengono i polinomi di codice.

Codici Ciclici 181

La ciclicità e la linearità del codice implicano:

( ) ( ) ( ) ( ) ( ) (18.2.1)

dalla quale sempre in virtù della linearità di ( ) discende anche

facilmente:

( ) ( ) ( ) ( ) ( ) ( ) ( ) (18.2.2)

Quest’ultima, sulla base dell’osservazione c), può essere rivisitata

in termini di laterali di , infatti ( ) possiamo

scrivere:

( ) ( ) { ( ) ( ) ( ) }

( ) ( ) ( )

( ) ( )

( ) ( ) ⁄

(18.2.3)

( ) è dunque un ideale dell’anello ⁄ .

Sufficienza:

Consideriamo un ideale di ⁄ comunque preso

un suo elemento, sia ( ) , il fatto che sia un ideale

implica che:

( ) ( ) ( ) ( )

( ) ( ) ( )

( ) ( )

⁄ (18.2.4)

Ne discende che la controimmagine dell’isomorfismo di cui all’os-

servazione c) è un codice ciclico.

***********

18.3 - Polinomio generatore di un codice ciclico

Il sottoinsieme di costituito dall’unione di tutti i laterali

di che appartengono ( ) , in virtù della (18.2.2), è un


ideale, ma tutti gli ideali di sono principali (vedi Teorema

17.1), esiste cioè un polinomio di grado minimo che li genera, tale

polinomio deve appartenere a ( ) ( )

in particolare

potremmo scegliere in quest'ultimo l’unico polinomio monico di

grado minimo, sia ( ). Il grado di ( ) dovrà necessariamente

essere per un codice .

( ) , quindi, in virtù del Teorema 17.2, ( )

deve essere un divisore di , ne discende che:

un codice ciclico esiste se e solo se il polinomio , a coefficienti nel

campo , si può scomporre nel prodotto tra due polinomi uno dei quali di

grado .

18.4 - Polinomio di parità di un codice ciclico

Nel paragrafo precedente abbiamo visto che se ( )( )

genera un codice ciclico ( ), allora deve esistere

( )( ) ( )( ) ( )( ) (18.4.1)

D’altro canto nel precedente capitolo abbiamo visto che o-

gni parola di un codice polinomiale può essere scritta nella forma:

( ) ( ) ( )( ) (18.4.2)

dove ( ) è un qualsiasi polinomio appartenente a ( )

.

Risulta:

( )( ) ( ) ( ) ( )( ) ( )( ) ( )( )

( )( ) ( ) (18.4.3)

La precedente è vera per tutti e soli i polinomi di codice, ne

discende che ( )( ), o un qualunque altro polinomio di che

lo contenga come fattore senza contenere , può essere uti-

lizzato per effettuare il controllo di parità nel caso in cui si intenda

utilizzare il codice esclusivamente per la rivelazione dell’errore.

Il polinomio ( )( ) ( )( ) ( ) ha tutti i coeffi-

cienti di grado maggiore di e minore di nulli. Questa os-

Codici Ciclici 183

servazione ci permette di scrivere equazioni che devono

essere soddisfatte dai coefficienti del polinomio ( )( ) ( ):

∑

(18.4.4)

ciascuna delle equazioni appena scritte coinvolge simboli

consecutivi della parola di codice e può quindi essere utilizzata co-

me controllo di parità qualora si intenda utilizzare il codice per la

correzione di errore. Le (18.4.4) potrebbero anche essere utilizzate

per implementare un codificatore sistematico utilizzando un filtro

FIR.

Infatti nella prima delle (18.4.4) possiamo scegliere arbitra-

riamente , (in sostanza la parola informativa) e cal-

colare , quindi utilizzare nella seconda per calcolare

e così via fino ad ottenere una parola di codice. In sostanza si

risolvono ricorsivamente equazioni del tipo

∑

(18.4.5)

Nell’incognita tali equazioni ammettono certamente soluzione

dal momento che deve essere diverso da . Se così non fosse,

tra le radici di ( ) vi sarebbe lo zero del campo che non è una ra-

dice di , quindi non può esserlo per nessuno dei suoi fattori.

Esempio 18.1

Vogliamo implementare un codificatore basato sulle (18.4.5) che

emetta gli simboli della parola di codice in sequenza. Osserviamo che

il codificatore è sistematico, i 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.E 18.1, nel quale sono indicati in

rosso i simboli presenti nelle celle di memoria, schematizzate come ele-

menti di ritardo. Ci rendiamo conto che, non appena la sorgente emette il

-esimo simbolo informativo ( ), all’uscita del moltiplicatore posto in

serie al sommatore sarà presente . Il passo successivo consisterà nel


chiudere l’anello di reazione, spostando sulla posizione b il commutatore

e mantenerlo in questa posizione per periodi di clock per calcolare

i restanti simboli di parità.

Osserviamo che ( ) può essere scelto in modo che risulti ,

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 me-

moria 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 codifi-

catore è sostanzialmente un filtro FIR.

18.5 - Matrice generatrice di un codice ciclico

Consideriamo un codice ciclico sul campo la cui rappre-

sentazione polinomiale sia l’insieme ( ) , abbiamo visto che

esso deve ammettere un polinomio generatore di grado , sia:

( )( ) (18.5.1)

Sappiamo che, anche i polinomi ( )( ) ( ) devono

appartenere a ( ) in virtù della ciclicità. Osserviamo che per i

polinomi ottenuti al variare di tra e risulta

( )( ) ( ) ( )( ) (18.5.2)

Detti polinomi sono linearmente indipendenti, giacché tutti di

grado diverso e sono in numero pari alla dimensione di ( )

pensato come sottospazio di ( )

, ne costituiscono quindi

una base.

Quanto appena detto ci consente di scrivere una matrice

generatrice del codice che avrà evidentemente come

righe le parole corrispondenti ai polinomi appena individuati

Fig.E 18.1 Codificatore sistematico basato sul polinomio di parità

Codici Ciclici 185

[

] (18.5.3)

18.6 - Codici ciclici Sistematici

La matrice generatrice individuata nel paragrafo precedente

non è in forma sistematica, vogliamo mostrare che è possibile in-

dividuarne una che lo è.

Dato un codice ciclico ( ) generato da ( )( ) consi-

deriamo polinomi del tipo:

(18.6.1)

Essi non sono certamente polinomi di codice in quanto tra le loro

radici non compaiono certamente quelle di ( )( ) , tuttavia sot-

traendo da ciascuno di essi il resto della divisione per ( ) otte-

niamo un polinomio di codice possiamo cioè affermare che:

( ( )) ( ) (18.6.2)

Se scriviamo i polinomi ottenuti tramite la (18.6.2) in corri-

spondenza ai valori di compresi tra tra ed otteniamo

polinomi di codice che hanno il solo coefficiente -esimo pari a

uno e tutti i restanti nulli nel range di valori di in parola, ciò in

quanto il resto di una divisione per ( ) è un polinomio che al più

può avere grado . I polinomi appena ottenuti, essendo di

grado diverso, 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:

(18.6.3)

in grado quindi di generare un codice sistematico con la parte in-

formativa “in coda” anziché “in testa”.

Da quanto detto discende che il polinomio di codice asso-

ciato al polinomio informativo ( ) ( )

è dato da:

( ) ( ) ( ) ( ( )( )) (18.6.4)


Prendiamo adesso in considerazione la matrice:

(18.6.5)

che si ottiene effettuando rotazioni cicliche su ciascuna riga del-

la . Essa ha per righe parole di linearmente indipendenti

ed è quindi anch’essa una matrice generatrice.

Esempio 18.2

Per costruire un codificatore basato sulla (18.6.4) dobbiamo disporre

di un sistema in grado di calcolare il resto della divisione tra due

polinomi.

Supponiamo di disporre all’istante - esimo del polinomio ( ), e

che tale polinomio all’istante - esimo venga aggiornato, per effetto

dell’emissione da parte di una sorgente di un simbolo secondo la

regola:

( ) ( )

Indichiamo rispettivamente con ( ) e ( ) il resto e il quoto del-

la divisione tra ( )e ( ) che supponiamo monico. Vogliamo calco-

lare ( ). Risulta:

( ) [ ( )] ( ( ))

[ ( ) ( ) ( ) ] ( ( ))

[ ( ) ] ( ( ))

Ma ( ) ha al più grado possiamo quindi ulterior-

mente scrivere:

( ) ( ) ( ) ( )

( ) ( ( ) )

( ( ) )

Possiamo quindi facilmente tracciare lo schema di principio mostrato in

Fig.E 18.2

Fig.E 18.2 Schema di principio di un sistema che calcola il resto della divisione tra due polinomi

Codici Ciclici 187

Non appena tutti i coefficienti del dividendo, a partire da quello di

grado maggiore, saranno immessi nel sistema, sarà sufficiente aprire

l’anello di reazione tramite il deviatore in uscita e nei successivi

passi si presenteranno in uscita i coefficienti del resto.

18.7 - Duale di un codice ciclico

Abbiamo mostrato che un codice ciclico ( ), ha come

generatore un fattore ( )( ) del polinomio . Esiste

quindi un ( )( ) tale che:

( )( ) ( )( ) (18.7.1)

Abbiamo già visto come ( )( ) possa essere utilizzato come poli-

nomio di parità, ma ( )( ) , in quanto fattore di , è in

grado, a sua volta, di generare un codice ciclico ( )

anch’esso contenuto in ( )

che viene chiamato, seppur im-

propriamente in quanto le parole di non sono in genere or-

togonali a quelle di , duale di ( ).

Consideriamo due polinomi ( ) ( ) e ( )

( ). Risulta:

( ) ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) (18.7.2)

Il polinomio ( ) ( ) ha grado al più ( ) ( )

, ne segue che il coefficiente del termine di grado di

( ) ( ) deve essere nullo. Possiamo quindi scrivere:

∑

(18.7.3)

la precedente vale per ogni scelta di ( ) ( ) e ( )

( ) . Essa ci suggerisce come costruire il codice duale

propriamente detto che si ottiene ribaltando le parole di .

Anche il codice duale propriamente detto è polinomiale il

suo polinomio generatore risulta essere:

( ) (18.7.4)

una sua matrice generatrice potrebbe essere:


[

] (18.7.5)

Capitolo - 19

CAMPI FINITI

19.1 - Polinomi irriducibili e campi a essi associati

Definizione 19.1 Diciamo che un polinomio ( )( ) di grado non inferiore a

è irriducibile se:

( )( ) ( )( ) ( )( ) (19.1.1)

Ovviamente tutti i polinomi di primo grado sono irriducibi-

li. In . Anche il polinomio è irriducibile esso in-

fatti non è divisibile né per né per , che sono tutti e soli i

polinomi di primo grado appartenenti a . Non sono neces-

sarie altre verifiche in quanto le eventuali fattorizzazioni devono

comunque contenere un polinomio di primo grado. Il polinomio

è irriducibile in , ma pensato come elemento di

non lo è


Teorema 19.1 Il gruppo quoziente ( )( ) ⁄ individuato dall’ideale generato

dal polinomio ( )( ) è un campo se ( )( ) è un polinomio irriducibile di

.

Dimostrazione:

Sappiamo già che ( )( ) ⁄ è un anello commutativo

con identità, quindi dobbiamo solo verificare che per ogni suo

elemento, fatta eccezione per ( )( ) , esiste un inverso.

Osserviamo che ( )( ) non coincide con . Infatti, se

così non fosse, esisterebbe ( ) ( )( ) ( ) , ma la

precedente può essere soddisfatta solo se , ma essendo, per

ipotesi, ( )( ) irriducibile, il suo grado non può essere inferiore


ad . Possiamo pertanto affermare che ( )( ) ⁄ contiene

almeno un polinomio ( ) ( )( ) .

Consideriamo adesso l’insieme

{ ( ) ( )( ) ( ) ( ) | ( ) ( ) (19.1.2)

si constata facilmente che è un ideale di , ma (vedi Teorema

17.1) tutti gli ideali di sono principali, deve pertanto esistere

in un polinomio ( )( ) tale che risulti ( )( ) .

Dalla (19.1.2) deduciamo che ( )( ) , quindi deve

esistere un polinomio per il quale risulti ( )( ) ( )( ) ( )( ),

ma ( )( ) è irriducibile, quindi, necessariamente, o , o

. Nel primo caso ( )( ) , ma ciò è assurdo perché

contiene anche ( )( ) ( )( ) , deve quindi essere . Ciò

implica da cui discende che devono esistere ( ) ( )

che soddisfano l’uguaglianza

( ) ( )( ) ( ) ( )( ) (19.1.3)

La precedente implica:

( )( ) ( ( )( ) ( )( ) ( )( ) ( )( )) ( )( )

( )( ) ( )( ) ( )( )

( )( ) ( )( ) ( )( ) ( )( )

(19.1.4)

Dalla precedente si deduce che il laterale ( )( ) ( )( ) è

l’inverso di ( )( ) ( )( ) .

***********

19.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 ( ), è un sottomultiplo dell’ordine del gruppo in cui

esso è contenuto.

Campi Finiti 191

Sia un elemento di un gruppo finito . Consideriamo

l’insieme:

(19.2.1)

è un sottoinsieme di , in quanto è chiuso rispetto alla legge

, quindi deve avere un numero finito di elementi, da cui

facilmente discende che deve esistere un intero ( ), tale che

risulti , o, che è lo stesso, tale che

(19.2.2)

Abbiamo appena mostrato che contiene . Considerando

adesso il più piccolo valore di che soddisfa la (19.2.2), risulta:

(19.2.3)

è quindi un sottogruppo di . L’ordine del sottogruppo

generato da un elemento di un gruppo è detto ordine di , ( ).

19.3 - Ordine degli elementi di un campo finito

Consideriamo un campo finito . Sia l’ordine di rispetto

alla legge , possiamo affermare che è un numero primo. Infat-

ti, se così non fosse, esisterebbero due interi, ed , entrambi

per i quali varrebbe l’uguaglianza:

( ) (19.3.1)

ma è un campo vale quindi la legge di annullamento del prodot-

to, quindi o o . ( ) sarebbe quindi il minimo tra

ed e non . Ne segue che ( ) deve essere un primo.

Osserviamo che per ogni elemento di si può scrivere

, da cui:

( ) ( ) ( ) (19.3.2)

più in generale , ma solo se , ovvero

se , possiamo quindi concludere che tutti gli elementi di-


versi da di un campo finito hanno lo stesso ordine rispetto alla

somma, e che tale ordine è un primo risulta cioè:

(19.3.3)

19.4 - Ordine di un campo finito

Consideriamo un campo , ed un suo sottocampo , in

questo caso diremo che è un’estensione di . Si constata che

ha la struttura di spazio vettoriale sul campo , se la dimensione

dello spazio è finita è detta grado di su .


Teorema 19.2 - Ordine di un campo finito L’ordine di un campo finito o è un primo, o è una potenza (intera) di

un primo.

Dimostrazione:

Abbiamo visto che l’ordine dell’elemento di un qualsiasi

campo è un primo , si verifica facilmente che l’insieme

3 (19.4.1)

é un campo (isomorfo a ) quindi è un sottocampo non neces-

sariamente proprio (in quanto potrebbe coincidere con ) di .

D’altro canto, ha la struttura di spazio vettoriale sul cam-

po e la sua dimensione deve essere finita, essendo finito.

Un qualsiasi elemento di potrà essere quindi espresso in

modo univoco come combinazione lineare, con coefficienti ap-

partenenti a , di elementi che costituiscano una base per ,

cioè che siano linearmente indipendenti su . Osservando che

esistono esattamente combinazioni lineari distinte si conclude

che l’ordine di se non è primo è una potenza di un primo.

***********

Quale che sia il campo finito , il campo generato

dalla sua unità moltiplicativa è detto sottocampo primo o fonda-

mentale. Esso è contenuto in tutti i sottocampi di , o, che è

Campi Finiti 193

lo stesso, è l’intersezione di tutti i sottocampi di quindi è an-

che il più piccolo sottocampo di che contiene (si dice che

è la caratteristica del campo).

Se un Campo non è finito, allora anche l’insieme definito

nella (19.4.1) non lo è, e non è neppure un sottocampo di (non

è nemmeno un gruppo) in questo caso si può dimostrare che il

sottocampo minimo contenuto in è isomorfo al campo dei

razionali e che l’insieme definito nella (19.4.1) è isomorfo al-

l’insieme dei naturali. In questo caso diremo che il campo ha

caratteristica

19.5 - Elementi primitivi di un campo

Sappiamo che un campo privato dell’elemento neutro

rispetto alla somma è un gruppo rispetto alla moltiplicazione, in-

dichiamolo con . L’ordine di

è .

Sia l’ordine di un generico elemento di , risulta

⏟

fattori

(19.5.1)

deve necessariamente essere un divisore di esiste cioè un

naturale tale che . Ne segue:

( ) (19.5.2)

Dalla precedente discende che per ogni elemento di

potre-

mo scrivere:

(19.5.3)

La precedente vale anche per , quindi:

(19.5.4)

Si può dimostrare che il gruppo è un gruppo ciclico,

cioè che in vi sono elementi il cui ordine è uguale all’ordine

del gruppo. Un tale elemento si chiama generatore del gruppo.

Un generatore di si dice elemento primitivo del campo,

in particolare si può dimostrare che vi sono elementi primitivi in


numero uguale a quello dei naturali e con esso relati-

vamente primi, ad esempio in ve ne saranno , in .

Inoltre in ogni campo per cui è un primo, quale ad esem-

pio tutti gli elementi diversi da sono primitivi.

19.6 - Campi di polinomi

Cerchiamo adesso di mettere un po’ d’ordine, sappiamo

che:

- se ( )( ) è un polinomio irriducibile appartenente a ,

allora ( )( ) ⁄ è un campo.

- ogni campo finito ha un numero di elementi che se non è

un numero primo è una potenza di un primo;

-

( ) , è isomorfo ad uno spazio vettoriale di

dimensione , costituito esattamente da ( ) elementi

(una potenza di un primo).

Fissato un polinomio irriducibile ( )( ), a coefficienti in

e comunque scelto un polinomio ( )( ) di possiamo

scrivere:

( )( ) ( )( ) ( )( ) ( )( ) (19.6.1)

La precedente ci mostra che ( )( ) ed ( )( ), appartengono allo

stesso laterale dell’ideale generato da ( )( ). Notiamo anche che

il grado di ( )( ) è, inferiore al grado di ( )( ).

Osserviamo che ( )( ) può essere un qualunque polino-

mio appartenente a ( )

in definitiva quindi, individuato un

polinomio irriducibile ( )( ), possiamo affermare che ( )

,

con l’usuale somma tra polinomi in e definendo come pro-

dotto tra due suoi elementi il resto della divisione tra il loro pro-

dotto in e ( )( ), è un campo isomorfo a ( )( ) ⁄ , in

quanto ogni elemento di ( )

individua uno e un solo laterale

di ( )( ) , e viceversa.

Esempio 19.1

Campi Finiti 195

Consideriamo l’anello dei polinomi sul Campo . Il polinomio

è irriducibile. Pertanto ⁄ è un

campo, di ordine , in

quanto sono i poli-

nomi di grado minore

di a coefficienti in .

Osserviamo che tutti i

suoi elementi non nulli

sono primitivi in quan-

to il gruppo ha

elementi, e sette è un

primo. In particolare

anche l’elemento:

sarà primitivo. Assu-

mendo come rappre-

sentanti di laterale i po-

linomi di grado inferiore a otterremo la Tabella 19.1, nella quale

abbiamo convenzionalmente indicato l’elemento neutro rispetto alla som-

ma con e, nella quarta colonna, abbiamo associato ai rappresentanti

di laterale le corrispondenti parole binarie di bit.

19.7 - Polinomi irriducibili primitivi

Definizione 19.2 Diciamo che un polinomio irriducibile ( )( ) è primitivo

se esso è fattore di e non di con .


Teorema 19.3 Se ( )( ) è un polinomio irriducibile di l’elemento

( )( ) ( )( ) ⁄ è primitivo per ( )( ) ⁄ se e

solo se ( )( ) è un polinomio primitivo.

19.8 - Alcune proprietà dei campi finiti

Consideriamo due elementi e di ci convinciamo

facilmente che vale l’uguaglianza:

( ) ∑( )[(

)]

∑( )[(

)]

(19.8.1)

Tabella 19.1 - ⁄


Osserviamo adesso che i coefficienti binomiali nella som-

matoria a ultimo membro sono multipli di , essendo primo, ciò

premesso ci basta ricordare la (19.3.3) per concludere che tutti gli

addendi della sommatoria all’ultimo membro della precedente so-

no uguali ad ne discende che

( ) (19.8.2)

Risulta anche:

( ) ( ) ( )

(19.8.3)

Dalle precedenti, sfruttando la proprietà associativa della

somma e tenuto conto che la precedente può essere applicata ite-

rativamente, otteniamo l’equazione:

( )

(19.8.4)

Un interessante caso particolare si ha quando si eleva a

una combinazione lineare di elementi di pensato come spa-

zio vettoriale sul suo sottocampo primo:

(∑

)

∑

(19.8.5)

La precedente consente di affermare che per un qualsiasi polino-

mio ( )( ) risulta:

( ( )( ))

(∑

)

∑ ( )

( )( )

(19.8.6)

dalla quale discende che, se il polinomio ammette come

radice, ammette anche con . Tali radici non saranno ov-

viamente tutte distinte.

Esempio 19.2

Campi Finiti 197

Vogliamo costruire un campo con elementi . Per farlo

abbiamo bisogno di individuare un polinomio irriducibile a coefficienti

in di quarto grado.

Prendiamo quindi in

considerazione il poli-

nomio . Detto

polinomio non è divisibile

per poiché non è

omogeneo né per

poiché ha un numero di-

spari di coefficienti non

nulli. quindi non è divi-

sibile neppure per polinomi

di terzo grado. Esso non è

divisibile neppure per i

polinomi di secondo grado

, , , per-

tanto è irriducibile.

Dovremmo a questo

punto verificare che si

tratta di un polinomio pri-

mitivo, accertandoci che

non è un fattore di

con . Tale

verifica è piuttosto noiosa,

d’altro canto, qualora il po-

linomio in parola non fosse

0010

0100

1000

1001

1011

1111

0111

1110

0101

1010

1101

0011

0110

1100

0001

0000

Tabella 19.2 - possibile rappresentazione di

Tabella 19.3 Addizioni e moltiplicazioni in


primitivo lo scopriremmo facilmente in quanto

il polinomio non sarebbe un generatore per il

campo, esso avrebbe cioè un ordine inferiore a

.

A partire dal polinomio che associamo al-

l’elemento del campo cominciamo a riempire

la Tabella 19.2 con il resto della divisione tra le

successive potenze di e il polinomio

. Come si può notare dalla Tabella

19.2 il polinomio è primitivo in quanto l’ordine

di . Nella terza colonna

della Tabella abbiamo

indicato la rappresentazione

binaria dei polinomi.

Abbiamo a questo punto

generato gli elementi del

campo.

Per operare più rapi-

damente su di esso possiamo

costruire la Tabella 19.3 che

riassume tutti i possibili

risultati di somme e prodotti

tra gli elementi del campo. È

opportuno sottolineare che

tale tabella dipende dal

polinomio irriducibile scelto

nel senso che se avessimo

utilizzato un polinomio diverso avremmo ottenuto una diversa

rappresentazione di e conseguentemente una Tabella 19.3 diversa.

19.9 - Il logaritmo di Zech

Un modo alternativo per calcolare le somme in un campo fini-

to è quello di fare riferimento ai logaritmi di Zech.

( )

Tabella 19.4 - logaritmo di Zech per la rappre-

sentazione di del-l’Esempio 19.2

0010

0100

1000

0011

0110

1100

1011

0101

1010

0111

1110

1111

1101

1001

0001

0000

Tabella 19.5 – altra possibile rappresentazio-

ne di

Campi Finiti 199

Sia un elemento primitivo del campo; supponiamo di

voler calcolare la somma di due elementi siano ed entrambi

diversi da possiamo scrivere:

( ) (19.9.1)

Osserviamo che il termine in parentesi si può esprimere come po-

tenza di . Notiamo inoltre che esso dipende esclusivamente dalla

differenza tra gli esponenti , che va valutata modulo la cardi-

nalità di , ovvero . Possiamo quindi scrivere

( ) , convenendo che ( ) qualora dovesse risultare

, (in tutte le estensioni di ogni elemento ha se

stesso come opposto, ma non è vero in generale!).

I possibili valori assunti dalla quantità in parentesi si

possono leggere nella Tabella 19.3. e possiamo scrivere

( ) ( ) (19.9.2)

La funzione ( ) è detta logaritmo di Zech. Essa, ovviamente,

dipende sia dalla scelta del polinomio irriducibile, sia da quella del-

l’elemento primitivo. Il vantaggio nell’utilizzazione del logaritmo

di Zech, anziché della Tabella 19.3, consiste nel fatto che la tabella

che si ottiene è più compatta essendo costituita solo da

valori contro i ( ) della parte additiva della Tabella 19.3

che diventa ben presto ingestibile al crescere della cardinalità del

campo.

Si osservi che qualora avessimo utilizzato il polinomio

, anch’esso irriducibile e primitivo, per generare

avremmo ottenuto la rappresentazione di Tabella 19.5 per la quale

la Tabella 19.3 e la Tabella 19.4 dovrebbero essere riscritte.

Il logaritmo di Zech si presta meglio ad essere implementa-

to in un programma di calcolo.

19.10 - Elementi algebrici di un campo su un sottocampo

Consideriamo adesso un campo e una sua estensione .


Definizione 19.3 Diciamo che un elemento è algebrico su un suo sottocampo se

esiste un polinomio ( )( ) di che ha come radice, cioè tale che

effettuando le operazioni in risulti ( )( ) .

Consideriamo ad esempio il campo dei razionali e la sua

estensione (il campo eale) l’elemento √ è algebrico su in

quanto il polinomio ha √ tra le sue radici se lo si

pensa come un polinomio appartenente a .

Osserviamo che l’insieme contenente i polinomi

che hanno tra le radici è un ideale di . Infatti, comun-

que scelto un polinomio in moltiplicandolo per un qualunque

polinomio di si ottiene ancora un polinomio che ha tra le

sue radici.

L’ideale deve ammettere quindi un polinomio generatore

sia ( )( ), osserviamo che esiste sempre un polinomio generatore

che ha come coefficiente del termine di grado massimo. Un tale

polinomio sarà detto monico, da ora in poi quando parleremo di

polinomio generatore ci riferiremo a quello monico.

Il polinomio ( )( ) è irriducibile in , (non è detto che

lo sia in ) in quanto se così non fosse almeno uno dei fattori

in cui potrebbe essere scomposto ammetterebbe come radice.

Tale fattore apparterrebbe quindi ad , ed avrebbe grado inferiore

a ( )( ) , ( )( ) non sarebbe in grado di generarlo e per-

verremmo ad un assurdo.

Da quanto sopra segue che esiste un unico polinomio gene-

ratore monico di che è chiamato polinomio minimale di su .

Osserviamo che ogni elemento di è algebrico su . Inol-

tre è facile constatare che se è finito ogni elemento di è alge-

brico sul suo sottocampo primo, in quanto si annulla in

virtù della (19.5.2) .

Capitolo - 20

CODICI BCH

20.1 - Codici BCH

Supponiamo di voler generare un codice polinomiale con

parole di lunghezza i cui simboli appartengano a un campo

che abbia una distanza minima non inferiore a .

Un modo per farlo è scegliere un’estensione di di

grado con un numero di elementi pari a , sia .

Scegliamo in un elemento primitiv e costruiamo il

polinomio ( ) di grado minimo che ha come radici gli

elementi dell’insieme con

. Detto polinomio è il minimo comune multiplo tra i polinomi

minimali associati agli elementi .

Affermiamo che un polinomio ( ) così costruito è in gra-

do di generare un codice con distanza minima non inferiore a .

Per provarlo osserviamo che l’insieme delle radici di ogni

polinomio associato a una parola di codice conterrà l’insieme

. Affinché un codice abbia distanza mini-

ma pari almeno a non devono esistere parole di codice, ad ecce-

zione di quella nulla, che abbiano meno di simboli diversi da .

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:

( )

(20.1.1)

Essendo ( ) un polinomio di codice l’insieme delle sue radici

conterrà l’insieme devono quindi essere contemporaneamente

soddisfatte le equazioni:


{

( )

( ) ( )

( ) ( )

( )

(20.1.2)

Abbiamo così ottenuto un sistema lineare e omogeneo di

equazioni in incognite.

La matrice dei coefficienti del sistema di cui sopra è:

[

( ) ( ) ( )

( ) ( ) ( )

] (20.1.3)

risulta:

[

( ) ( ) ( )

]

[

]

(20.1.4)

Il determinante di vale quindi :

∏( )

∏

(20.1.5)

essendo la prima matrice a secondo membro della (20.1.4) di Van-

dermonde e la seconda diagonale.

è certamente non singolare ciò discende dal fatto che,

essendo per ipotesi, elemento primitivo di , possiamo scri-

vere:

(20.1.6)

Possiamo quindi concludere che il sistema omogeneo

(20.1.2) è di Cramer. Esso ammette quindi solo la soluzione bana-

le. Non esistono pertanto parole di codice, ad eccezione di quella

Codici BCH 203

con simboli tutti nulli, che abbiano meno di simboli diversi da

.

Quanto appena mostrato permette di costruire un’impor-

tante classe di codici detti BCH, dalle iniziali dei loro scopritori:

Bose (1959), Chaundhuri e Hocquenghem (1960). Alla classe dei

codici BCH appartengono anche i codici di Hamming che ab-

biamo già visto, nonché i codici di Reed Solomon (RS).

Osserviamo che i codici BCH sono ciclici in quanto il loro

polinomio generatore ( )( ) ha tra le sue radici un sottoinsie-

me di quelle di (pensato come polinomio a coefficienti in

). ( )( ) ne è pertanto un fattore.

Osserviamo anche che il grado del polinomio generatore

non è assegnato a priori, ma dipende dalla scelta dell’elemento pri-

mitivo di . ne segue che anche il numero di simboli che costi-

tuiscono la parola informativa non può essere prefissato. Va

anche osservato che la distanza minima del codice potrebbe

risultare maggiore di quella di progetto.

Tipicamente i simboli che costituiscono la parola di codice

appartengono a un campo , cioè ad un campo con un nume-

ro di elementi che sia una potenza di .

In particolare i codici di Reed Solomon, che sono certa-

mente i più importanti tra i codici BCH, hanno simboli apparte-

nenti a , lunghezza della parola di codice , lun-

ghezza della parola informativa qualsiasi, purché (ovviamente)

minore di , e distanza minima .

Un codice di RS che ha trovato diverse applicazioni pra-

tiche è il ( ) che presenta una distanza minima di con

simboli appartenenti a , cioè costituite da un byte. Pensato

come codice binario la parola di codice è quindi di

bit e la corrispondente parola informativa di bit. Questo co-

dice è in grado di correggere fino ad byte errati indipendente-

mente dal numero di bit errati nel byte.

Esempio 20.1 - Progetto di un codice BCH


Vogliamo realizzare

un codice BCH con una

parola di codice di

bit in grado di correg-

gere almeno errori

quindi con una distanza

minima pari almeno a . Per farlo abbiamo bisogno di generare .

Possiamo verificare che

è un polinomio irriducibile pri-

mitivo. A partire da quest’ultimo ricaviamo la Tabella 20.2, da essa

possiamo facilmente calcolare i logaritmi di Zech riportati in Tabella

20.1.

( )

Tabella 20.1

01010

10010

00001

Tabella 20.2 - Possibile rappresentazione di

Codici BCH 205

Possiamo quindi procedere alla costruzione del polinomio generatore

a coefficienti in , che deve avere come radici 6 potenze consecutive

di un elemento primitivo . Possiamo scegliere:

Tale scelta ha il vantaggio di semplificare la ricerca del polinomio ge-

neratore, in quanto il polinomio minimale associato ad tenendo conto

della (19.8.6) è anche minimale per ed quello di lo è anche per

. Il polimomio generatore cercato sarà quindi il prodotto di tre

polinomi minimali, quello associato ad , quello associato ad e quello

associato ad .

Osserviamo che se avessimo scelto il polinomio generatore avente

come radici:

Esso avrebbe avuto certamente un grado non minore di quello

associato alla scelta precedente in quanto oltre ai tre fattori citati avrebbe

dovuto avere tra i suoi fattori il polinomio minimale associato ad .

L’aumento del grado del polinomio generatore comporta inevitabilmente

una riduzione del grado del polinomio informativo. Inoltre nel caso

specifico, la distanza minima di progetto sarebbe anche aumentata perché

il polinomio generatore avrebbe avuto almeno 7 potenze consecutive di

tra le sue radici.

La ricerca dei polinomi minimali può essere fatta per tentativi

possiamo solo ridurne il numero. Nel caso ad esempio del polinomio

minimale associato ad sappiamo che esso avrà anche le radici

quindi dovrà essere almeno di quinto grado, possiamo

quindi cominciare a prendere in considerazione i polinomi non omogenei

di 5 grado con un numero dispari di coefficienti, in quanto quelli con un

numero pari di coefficienti, essendo divisibili per , non sarebbero

irriducibili. Restano quindi 8 possibili polinomi di quinto grado da

prendere in considerazione.

Il polinomio minimale associato ad risulta essere

. Che

sia una sua radice si constata immediatamente osservando che e

, appartengono allo stesso laterale (vedi Tabella 20.2).

è

irriducibile in quanto è il polinomio che abbiamo utilizzato per generare

il campo.

Il polinomio irriducibile associato ad deve avere tra le sue radici

anche , anch’esso avrà quindi un grado non inferiore al

quinto il polinomio che cerchiamo è

. Proviamo a

verificare che è una sua radice. Utilizzando i logaritmi di Zech (vedi

Tabella 20.1) otteniamo:


Dobbiamo anche verificare che sia irriducibile. Non avendo tra i suoi

fattori nessun polinomio di primo grado, verifichiamo che non ne abbia

di secondo grado. Ovviamente esso non è divisibile per , non lo è

neppure per ne per

, quindi è irriducibile in quanto non

possono esistere fattori di terzo grado, se non ve ne sono di secondo, in

un polinomio di quinto grado.

Il polinomio minimale associato ad è

, come si

può analogamente verificare.

Possiamo a questo punto calcolare il polinomio generatore del codice

che sarà il prodotto dei tre polinomi minimali sopra indicati che sarà di

quindicesimo grado: ( ) ( )( )( )

( )( )

Poiché il polinomio di codice è di trentesimo grado e il polinomio

generatore di quindicesimo il polinomio informativo sarà anch’esso di 15

grado la parola informativa sarà quindi costituita da 16 bit, avremo

quindi 65.536 parole di codice immerse in uno spazio di parole (tutte le possibili parole costituite da 31 bit.

Le parole di codice si possono a questo punto generare moltiplicando

il polinomio associato alla parola informativa per il polinomio gene-

ratore, ma in questo caso il codice non sarebbe sistematico, ovvero pos-

siamo ricordare che i codici BCH sono ciclici e basandoci sul § 18.6 -

possiamo generare le parole di codice a partire da un polinomio infor-

mativo ( ) effettuando rotazioni cicliche sulla parola di codice

( ) ( ) ( ) ( ( ))

Capitolo - 21

LA TRASFORMATA DI FOURIER DISCRETA

21.1 - La Trasformata di Fourier Discreta

Ricordiamo che la trasformata (DFT) e l’antitrasformata

(IDFT) di Fourier discreta di una sequenza a valori nel

campo complesso di durata , o periodica di periodo è data da:

∑

∑

∑

∑

(21.1.1)

dove rappresenta una radice -esima dell’unità, in altri termini

nelle (21.1.1) compaiono le radici appartenenti al campo comples-

so del polinomio, a coefficienti in , . Si noti che il

campo complesso è un’estensione del campo reale.

Volendo generalizzare le (21.1.1) ai campi finiti, occorre innan-

zitutto soffermarsi sull’esistenza della radice -esima dell’unità del

campo. Ricordando la (19.5.1) e la (19.5.3) concludiamo che se

operiamo in la lunghezza della sequenza deve essere un

divisore di .

Ciò premesso consideriamo una sequenza, appartenente a

ed una radice -esima dell’unità in , cioè un

elemento di ordine per il gruppo , sia . Prendendo spun-

to dalle (21.1.1) possiamo scrivere la coppia di trasformate

∑

∑

(21.1.2)


Vogliamo verificare se esiste un elemento in corri-

spondenza al quale risulti . A tal fine sosti-

tuiamo la prima delle (21.1.2) nella seconda:

∑ ∑

∑ ∑ ( )

(

∑

∑ ∑ ( )

)

(

∑

∑ ∑ ( )

)

{

∑ { ( )

( ) ( )

( ) }

}

(21.1.3)

Affinché le (21.1.1) siano una coppia di trasformate è quindi suffi-

ciente che sia l’inverso di in , in realtà è anche l’inver-

so di in .

Possiamo quindi scrivere la coppia di trasformate:

∑

( ) ∑

(21.1.4)


Per la DFT su un campo finito valgono quasi tutte le pro-

prietà già note per quella nel campo complesso, ad esempio la li-

nearità, la cui verifica è banale, o quella di traslazione ciclica.

Sia data una sequenza , la cui DFT sia

, fis-

sato un intero consideriamo la sequenza il cui generico elemento

, dove sta ad indicare che la differenza va effet-

tuata modulo . Vogliamo calcolare la DFT di otteniamo:

∑

∑

∑ ( )

∑

(21.1.5)

Dualmente fissato un intero consideriamo la sequenza

la sua DFT vale:

∑

∑

( )

(21.1.6)

Alla sequenza possiamo associare il polinomio:

( ) (21.1.7)

lo stesso possiamo fare per la sua DFT , ammesso che esi-

sta, definendo in modo analogo un polinomio ( ) di grado al più

. Osservando le (21.1.4) ci rendiamo conto che risulta:

(

)

( ) ( )

(21.1.8)

Dalle precedenti discende che se allora ( ) ha

come radice, o, che è lo stesso, ha il polinomio tra i suoi


fattori. Analoghe considerazioni possono farsi su ( ) se qualche

.

Consideriamo una sequenza non banale cui corri-

sponda un ( )di grado non maggiore di . Detto polino-

mio può avere al più radici che qualora coincidessero

tutte con le , comporterebbero l’annullamento di non più di

elementi della che conseguentemente avrebbe

almeno elementi non nulli. Applicando la (21.1.5) possiamo fa-

cilmente concludere che è in realtà sufficiente che in una sequenza

non banale siano nulli elementi consecutivi (modulo ),

affinché la sequenza trasformata, o antitrasformata abbia almeno

elementi non nulli.

21.2 - DFT e codici ciclici

Le considerazioni fatte dopo la (21.1.8) ci permettono di

introdurre una definizione alternativa per i codici ciclici. Possiamo

infatti affermare che

Definizione 21.1 Un codice ciclico ( ) è costituito dal sottoinsieme di

la cui

DFT si annulla in posizioni prefissate.

La definizione appena data comporta ovviamente l’esistenza

della DFT, deve esistere cioè un elemento di ordine per ,

che consenta di calcolarla, ne discende che deve essere un sotto-

multiplo di , cioè una radice -esima dell’unità di . 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 . Il fatto che la Definizione

21.1 sia equivalente alla Definizione 18.1 risulta evidente tenendo

conto della (21.1.8) che ci permette di affermare che ogni polino-

mio di un codice costruito sulla base della Definizione 21.1 è mul-


tiplo di uno stesso polinomio che è a sua volta un fattore di

inteso come polinomio a coefficienti in .

Appunti di Teoria dell'Informazione e Codici - tti.unipa.itgarbo/Teoria InfeCodici.pdf · Indice v...

Documents

Transcript of Appunti di Teoria dell'Informazione e Codici - tti.unipa.itgarbo/Teoria InfeCodici.pdf · Indice v...