UNIVERSITÀ DEGLI STUDI DI PADOVA
DIPARTIMENTO DI INGEGNERIA DELL’INFORMAZIONE
CORSO DI LAUREA IN INGEGNERIA DELLE TELECOMUNICAZIONI
TESI DI LAUREA
CODICI
CONVOLUZIONALI
BIDIMENSIONALI
RELATORE:
chiar.mo prof. Mauro Bisiacco
CORRELATORI:
chiar.ma prof.ssa Maria Cristina Ronconi
chiar.ma prof.ssa Maria Elena Valcher
LAUREANDO:
Manuel Toniato
Anno Accademico 2003/2004
Padova, 19 aprile 2005
Alla mia famiglia
Indice
Introduzione
V
1
Lo spazio di definizione
1
1.1
Le serie a supporto compatto nel passato . . . . . . . . . . . . .
1
1.2
Le serie causali . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Le serie debolmente causali . . . . . . . . . . . . . . . . . . . . .
4
1.4
Le serie debolmente causali traslate . . . . . . . . . . . . . . . . .
12
2
3
Codici 2D. Definizioni e proprietà
23
2.1
La definizione di codice bidimensionale . . . . . . . . . . . . . .
23
2.2
Codificatori iniettivi . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.3
Codificatori equivalenti . . . . . . . . . . . . . . . . . . . . . . .
24
2.4
Codificatori e decodificatori non catastrofici . . . . . . . . . . . .
26
2.4.1
Decodifica non catastrofica semplice . . . . . . . . . . . .
26
2.4.2
Decodifica non catastrofica robusta . . . . . . . . . . . . .
30
2.5
Codificatori sistematici . . . . . . . . . . . . . . . . . . . . . . . .
34
2.6
Formatori di sindrome . . . . . . . . . . . . . . . . . . . . . . . .
34
Confronto con le altre teorie dei Codici 2D
37
3.1
Le altre definizioni di codice 2D . . . . . . . . . . . . . . . . . . .
37
3.2
Confronto tra le proprietà dei codici . . . . . . . . . . . . . . . .
40
3.2.1
Iniettività . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.2.2
Codificatori Equivalenti . . . . . . . . . . . . . . . . . . .
40
3.2.3
Catastroficità . . . . . . . . . . . . . . . . . . . . . . . . .
41
3.2.4
Formazione della sindrome . . . . . . . . . . . . . . . . .
44
Conclusioni
45
I
INDICE
A Richiami di Algebra
A1 Relazioni d’ordine . . . .
A2 Strutture Algebriche . .
A3 Moduli e spazi vettoriali
A4 Matrici . . . . . . . . . .
A5 Matrici Polinomiali . . .
A6 Matrici Razionali . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Bibliografia
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
49
50
51
53
53
54
55
Ringraziamenti
II
Simbologia
F
F[z1 , z2 ]
F± = F[z1 , z2 , z1−1 , z2−1 ]
F(z1 , z2 )
F[[z1 , z2 ]]
Fp,q,r,s [[z1 , z2 ]]
Fp,q ((z1 , z2 ))
F∞ = F[[z1 , z2 , z1−1 , z2−1 ]]
supp(a)
F(m, n)
P(m, n)
N
Z
Z+
Z+
0
Q
R
Campo finito che costituisce l’alfabeto del codice
Anello dei polinomi ordinari in due indeterminate su F
Anello dei polinomi di Laurent in due indeterminate su F
Campo delle funzioni razionali in due indeterminate su F
Anello delle serie formali causali
P
i j
( ∞
i=0,j=0 aij z1 z2 )
Anello delle serie formali debolmente causali
con supporto contenuto nel cono Cp,q,r,s
Campo delle serie formali debolmente causali
traslate in Cp,q
Gruppo delle serie formali in due indeterminate
P∞
P
i j
( +∞
j=−∞ aij z1 z2 )
i=−∞
supporto di a (dove a è una serie 2D) cioè l’insieme dei punti (m, n) ∈ Z2 tali che amn 6=
0
Futuro di (m, n), cioè l’insieme di punti (x, y) ∈
Z2 tali che (x > m) ∧ (y > n)
Passato di (m, n), cioè l’insieme di punti (x, y) ∈
Z2 tali che (x 6 m) ∧ (y 6 n)
Insieme dei numeri naturali
Insieme dei numeri interi
Insieme dei numeri interi positivi
Insieme dei numeri interi nonnegativi
Insieme dei numeri razionali
Insieme dei numeri reali
III
Introduzione
L’importanza dei codici a correzione d’errore
L’affidabilità del sistema di comunicazione Lo scopo principale di un sistema di comunicazione risiede nella possibilità di riprodurre in modo fedele un
messaggio di informazione in luoghi e/o tempi differenti da quello in cui l’informazione entra nel sistema (in questo senso consideriamo come sistemi di
comunicazione anche le operazioni di data storage su di un supporto). Poiché qualsiasi mezzo di trasmissione (o di registrazione dei dati) è soggetto a
variazioni casuali (rumore) che possono deteriorare il messaggio inviato, ogni
sistema di comunicazione deve elencare tra le sue caratteristiche, non solo la
quantità di informazioni che è in grado di trasmettere, ma anche l’affidabilità
della trasmissione.
Nel caso delle trasmissioni digitali questa affidabilità si misura con la probabilità d’errore del sistema, cioè la probabilità che il simbolo ricevuto sia diverso da quello trasmesso. Lo scopo principale dei codici a correzione d’errore
è proprio quello di rilevare questi errori di trasmissione e, se possibile, di correggerli. Ciò può avvenire grazie all’introduzione di ridondanza nel messaggio
trasmesso. Si aggiunge cioè una correlazione tra i simboli in trasmissione in
modo da poter stimare se il messaggio ricevuto può effettivamente essere stato
trasmesso.
L’esempio della lingua italiana A questo proposito facciamo un esempio con
la lingua italiana, o meglio con il vocabolario italiano che è effettivamente un
codice ridondante1 . Se in una trasmissione di un testo costituito solo da parole
appartenenti alla lingua italiana, riceviamo la parola cmsa formata da 4 simboli siamo sicuri che nella trasmissione c’è stato almeno un errore. Non siamo
1
Un esempio analogo viene illustrato da Shannon nel suo articolo ([28]). Shannon afferma
che, esaminando le parole del vocabolario, si vede che la lingua inglese ha una ridondanza di
circa il 50%, dato, quest’ultimo, che può venire esteso anche alle altre lingue naturali.
V
INTRODUZIONE
però in grado di correggerlo, anche solo ipotizzando che ci sia stato un solo
errore nella trasmissione: infatti ci sono almeno due parole (casa e cosa) che
differiscono da cmsa per un solo simbolo. Se d’altro canto la parola ricevuta
fosse stata prvimento, non essendoci nel vocabolario parole oltre a pavimento,
che differiscano per un solo simbolo dalla parola ricevuta, saremmo stati in
grado non solo di individuare l’errore ma anche di correggerlo. Purtroppo la
lingua italiana non è un buon codice per la trasmissione perché ci sono parole del vocabolario che differiscono per un solo carattere: cosı̀ se trasmettiamo
mare e riceviamo more, con un’analisi ristretta alla sola ortografia, che prescida
cioè dalla semantica del messaggio, non siamo in grado di individuare l’errore.
Il limite di Shannon La fondamentale importanza dei codici a correzione
d’errore nelle comunicazioni digitali si comprese a fondo nel 1948 grazie all’articolo di Claude Elwood Shannon ([28]) che pose le basi per la moderna
teoria dell’informazione. All’interno del suo monumentale articolo Shannon
dimostrò che ogni canale di trasmissione aveva una capacità intrinseca di trasmissione legata al rapporto tra la potenza del segnale trasmesso e la potenza
del rumore del canale. Attraverso tecniche legate alla teoria della probabilità
Shannon arrivò quindi al seguente risultato che avrebbe segnato la fortuna dei
codici a correzione d’errore nei decenni successivi:
Teorema Dato un canale di capacità C, per ogni trasmissione con rate Ri < C
si possono codificare i messaggi con un codice rendendo arbitrariamente piccola la
probabilità d’errore. Tale codice non esiste per Ri > C. ([28, Teor. 21]).
La dimostrazione di Shannon indicava il limite (Ri < C è il cosiddetto limite
di Shannon) ma non dava indicazioni su come dovesse essere costruito il codice. Nei decenni che sono trascorsi dal 1948 a oggi sono state sviluppate varie
soluzioni per la codifica di canale. I codici studiati rientrano tutti in due grandi categorie: i codici a blocco (block codes) e i codici convoluzionali (convolutional
codes).
Codici a blocco e codici convoluzionali In entrambe le tipologie di codice
il messaggio in ingresso al codificatore viene suddiviso in blocchi formati da
k simboli. Ogni blocco viene elaborato aggiungendovi (n − k) simboli di ridondanza: il messaggio trasmesso sul canale è quindi costituito da blocchi di
n simboli. Ovviamente per non perdere informazioni deve essere n > k. In
VI
INTRODUZIONE
ricezione lo studio degli (n − k) simboli di ridondanza permette di ricostruire
i blocchi di k simboli trasmessi. Il rapporto nk viene detto rapporto di codifica
(code rate).
La differenza tra le due tipologie di codice risiede nella modalità con cui
vengono codificati i blocchi. Nei codici a blocco, ogni blocco codificato al tempo t0 è funzione esclusivamente del blocco in ingresso al tempo t0 . La trasformazione è quindi istantanea e si parla di codice a blocchi (n, k). Nel caso dei codici convoluzionali invece, il blocco codificato al tempo t0 non dipende solo dal
blocco in ingresso al tempo t0 ma anche da m simboli precedenti. Si dice che
l’operazione di codifica è un’operazione con memoria. Il parametro m è fondamentale nella definizione del codice: nel caso di un codice convoluzionale
si parla di un codice (n, k, m).
Codici convoluzionali unidimensionali
I codici convoluzionali furono proposti per la prima volta da Peter Elias nel
1955 ([4]). Negli anni successivi ci si concentrò sugli aspetti algoritmici della codifica e decodifica senza approfondire i concetti matematici che stavano
alla base dei codici convoluzionali (un esempio dell’approccio di quel periodo è il celeberrimo algoritmo di Viterbi, [30]). Solo alla fine degli anni ’60 si
cominciò a guardare ai codici da un punto di vista teorico: i primi a studiare
le connessioni tra i codici convoluzionali e la teoria dei sistemi lineari furono
Massey e Sain ([21]). Ma fu nei primi anni ’70 che si posero effettivamente
le basi per uno studio algebrico dei codici convoluzionali. G. D. Forney, con
una serie di articoli successivi ([12], [13], [14]) propose un approccio ai codici
convoluzionali che utilizzava la teoria dei sistemi multivariabili di Rosenbrock
([25]). Lo studio delle proprietà del codice (distanza, memoria, . . . ) si riduceva
allo studio della matrice razionale con cui veniva rappresentato il codificatore. Tutte le trattazioni successive (per esempio [15], [17] e [23]) si sono basate
sull’approccio di Forney.
Negli ultimi anni sono state introdotte nello studio dei codici convoluzionali nuove metodologie, sviluppate inizialmente all’interno della teoria dei sistemi. Esse focalizzano la propria attenzione non tanto sul processo di codifica e
sul codificatore, quanto sulle proprietà del codice stesso o meglio dell’insieme
delle parole di codice. I nuovi approcci sono principalmente tre:
1. dinamica simbolica ([18], [20])
VII
INTRODUZIONE
2. teoria dei behavior ([32], [33],[34])
3. teoria dei moduli ([27])
I tre nuovi approcci unitamente all’approccio classico di Forney sono stati analizzati in dettaglio e comparati da Joachim Rosenthal ([26]). Rinviamo a questo articolo il lettore interessato a una visione di insieme sui codici
convoluzionali unidimensionali.
Codici convoluzionali bidimensionali: approcci esistenti in letteratura
Lo studio dei codici bidimensionali è legato alla teoria dei sistemi bidimensionali. Questa teoria si propone di modellizzare e analizzare sistemi fisici in
cui le grandezze in gioco non dipendono più dalla sola coordinata temporale,
ma da due coordinate (due coordinate spaziali, una temporale e una spaziale,
. . . ). Ettore Fornasini (che insieme a Giovanni Marchesini è stato tra i primi a
studiare i sistemi 2D, [8], [7]) applica per esempio la teoria dei sistemi 2D allo
studio dell’inquinamento lungo un fiume ([5]), dove ciò che accade nel passato influenza il futuro (e non viceversa) e ciò che accade a monte influenza
ciò che accade a valle (e non viceversa): in questo caso il sistema dipende da
una coordinata temporale e da una spaziale. Nel caso dei codici bidimensionali l’applicazione principale è la codifica di segnali bidimensionali come le
immagini (due coordinate spaziali).
I tre approcci introdotti alla fine del paragrafo precedente, sono alla base delle teorie dei codici convoluzionali multidimensionali e, in particolare
bidimensionali, presenti in letteratura.
Sulla scia della dinamica simbolica possiamo per esempio trovare il recente
articolo di Bruce Kitchens ([16]) ma è soprattutto sulla base delle altre due
teorie che si sono avuti i risultati maggiori.
La teoria dei behavior di Willems è stata estesa ed applicata ai codici convoluzionali bidimensionali da E. Fornasini e da M. E. Valcher in una serie di
articoli dei primi anni ’90 ([9], [10], [29]), articoli che hanno costituito il primo
vero studio dei codici 2D.
L’applicazione della teoria dei moduli ai codici è stata sviluppata a partire
dalla metà degli anni ’90 dal gruppo di Joachim Rosenthal alla University of
VIII
INTRODUZIONE
Notre Dame, Indiana. In particolare lo studio dei codici multidimensionali è
stato condotto da Paul Weiner ([31]) che ha rielaborato ed esteso nella sua tesi
alcuni risultati già presenti in un articolo di Fornasini e Valcher ([10]).
Le due teorie propongono due diverse definizioni di codice convoluzionale. La principale differenza fra le due definizioni risiede nella tipologia di
segnali ammessi in ingresso. Infatti, mentre Weiner, per la teoria dei moduli, richiede che i segnali in ingresso siano a supporto finito, Fornasini e Valcher non danno nessuna limitazione (anzi una delle proprietà caratterizzanti
il codice richiede che esistano segnali a supporto infinito). Da questa differenza nella definizione seguono di conseguenza ulteriori e importanti differenze
nelle proprietà dei codici.
C’è però una proprietà che accomuna le due definizioni. Infatti entrambe
richiedono che i codificatori siano polinomiali: le funzioni di trasferimento sono perciò a supporto finito. Tale restrizione non era presente nel lavoro classico
di Forney che anzi prevedeva la possibilità di avere codificatori razionali.
Lo scopo di questa tesi è appunto l’estensione al caso bidimensionale della
teoria di Forney per indagare la possibilità di avere codificatori razionali anche
nel caso 2D.
L’approccio di Forney nel caso 1D
Per poter analizzare le proprietà dei codici sfruttando gli strumenti dell’algebra, Forney associa a ogni sequenza di simboli
u = (. . . , u−2 , u−1 , u0 , u1 , u2 , . . .)
una serie formale di potenze
u = . . . + u−2 z
−2
+ u−1 z
−1
2
+ u0 + u 1 z + u 2 z + . . . =
+∞
X
ui z i
−∞
In questo modo la convoluzione nello spazio delle sequenze diventa un semplice prodotto alla Cauchy nello spazio delle serie formali.
Osservazione In letteratura non c’è uniformità nella terminologia in merito
alle serie formali. Per alcuni autori (soprattutto per i matematici specializzati
P
i
in algebra) si definiscono serie formali di potenze le serie del tipo +∞
i=0 ai z (si
IX
INTRODUZIONE
veda ad esempio il testo di Zariski e Samuel, [35]). Altri autori, soprattutto
coloro che si occupano di teoria dei codici, identificano le serie formali con
P
i
le serie bilatere +∞
−∞ ai z (si veda ad esempio [26], [9], [6]). In questa sede ci
atterremo a questa seconda convenzione che meglio risponde alle esigenze di
modellizzare tutte le possibili sequenze in ingresso.
Purtroppo nello spazio F[[z, z −1 ]] delle serie formali non sempre il prodotto
è definito. In generale non è definito nemmeno il prodotto di una serie formale
per una funzione razionale come si può vedere nel seguente esempio.
Esempio 1 Sia
+∞
X
1
G=
=
zi
1−z
i=0
e
u=
+∞
X
zi
−∞
Si vede facilmente che non si può ricondurre a una somma finita nessun coefficiente della serie prodotto Gu.
Per poter usare codificatori razionali si è perciò costretti a porre restrizioni
sulle sequenze ammissibili in ingresso. Si dimostra che, perché il prodotto sia
sempre ben definito, basta restringersi alle serie formali di Laurent o altrimenti
dette serie a supporto compatto a sinistra. Con questo nome si denotano le serie
P
i
del tipo +∞
i=d ai z con d ∈ Z. Seguendo la simbologia introdotta da Forney,
indicheremo l’insieme delle serie di questo tipo con il simbolo F((z)). Tale
restrizione non solo permette di definire il prodotto per qualsiasi coppia (a, b)
di elementi dell’insieme, ma si dimostra che l’insieme è chiuso rispetto alle
usuali operazioni di somma e prodotto e che esso è un campo rispetto a tali
operazioni. Inoltre la teoria delle trasformate zeta assicura che ogni funzione
razionale r ∈ F(z) può essere sviluppata in una serie di F((z)).
Una volta adottata la restrizione dell’ingresso alle serie a supporto compatto a sinistra, Forney esegue una trasformazione serie/parallelo che mappa
la serie formale di partenza ũ ∈ F((z)) in un vettore k-dimensionale2 di serie
2
Nella teoria dei codici, al contrario della teoria dei sistemi, si è soliti utilizzare vettori riga.
X
INTRODUZIONE
formali u ∈ F((z))k
 P
+∞
uk·i z k·i
 P−∞
k·i+1
 +∞
+∞
 P−∞ uk·i+1 z
X
 +∞
ũ =
ui z i 7→ u =  −∞ uk·i+2 z k·i+2
 .
−∞
 ..

P+∞
k·i+(k−1)
−∞ uk·i+(k−1) z
T








con k ∈ N
In questo contesto l’operazione di codifica convoluzionale diventa una trasformazione tra i vettori u ∈ F((z))k e i vettori y ∈ F((z))n , trasformazione
operata da una matrice razionale G(z) ∈ F(z)k×n .
y = uG
E proprio a questo fatto fa riferimento la definizione di Forney ([13]) di codice convoluzionale, definizione che estende una precedente definizione dovuta a Massey e Sain3 ([21]).
Definizione Un codice convoluzionale (n, k) sul campo F è un F((z))-sottospazio
C di F((z))n , di dimensione k e avente una base di vettori in F(z)n .
In questo modo un codice convoluzionale risulta essere uno sottospazio vettoriale di dimensione k dello spazio vettoriale F((z))n e l’analisi del codice può
avvalersi dei potenti strumenti dell’algebra lineare.
Struttura della tesi
La struttura della tesi ricalca l’approccio usato da Forney.
Nel capitolo 1 cercheremo quale possa essere un equivalente bidimensionale del concetto di serie compatta a sinistra per poter definire convenientemente un codice convoluzionale 2D. Partiremo dall’analisi delle serie a supporto
compatto nel passato per poi restringerci alle serie debolmente causali e infine
alle serie debolmente causali traslate.
Nel capitolo 2 daremo la definizione di codice 2D e ne studieremo le proprietà principali quali l’equivalenza fra i codificatori, i codificatori sistematici
3
Massey e Sain avevano posto condizioni più restrittive sulle sequenze in ingresso. Essi
infatti avevano imposto che le sequenze in ingresso fossero razionali e quindi che le serie
formali compatte a sinistra che le rappresentavano fossero definitivamente periodiche.
XI
INTRODUZIONE
e la formazione della sindrome. Una particolare attenzione verrà riservata al
problema dei codificatori catastrofici in quanto in tale argomento si vedono le
maggiori differenze tra i codici unidimensionali e i codici 2D.
Nel capitolo 3 infine confronteremo i risultati ottenuti con i risultati già
presenti in letteratura per quanto riguarda i codici bidimensionali.
XII
Capitolo 1
Lo spazio di definizione
Lo studio dei codici convoluzionali in ambito bidimensionale si avvale, come
nel caso unidimensionale, degli strumenti dell’algebra (lineare e commutativa). Considerando messaggi di informazione a tempo discreto e a valori in un
campo (solitamente finito) F, si può stabilire una corrispondenza biunivoca tra
2
lo spazio dei messaggi FZ e lo spazio delle serie formali a indici in Z2 . Le serie
P
formali nel caso 2D saranno serie del tipo a = (i,j)∈Z2 aij z1i z2j e l’insieme di
tali serie sarà indicato con F∞ .
È ben noto che si può dotare F∞ di una struttura di gruppo commutativo con
l’usuale operazione di somma, definita termine a termine. L’elemento neutro
P
P
risulta la serie nulla 0 = i,j 0z1i z2j e, data una serie a = i,j aij z1i z2j , l’opposto
P
di a è la serie −a = i,j −aij z1i z2j . Purtroppo, come nel caso unidimensionale,
l’usuale prodotto alla Cauchy non è definito per tutte le coppie di F∞ × F∞ . Si
dimostra però che, nei casi in cui esso si può definire, esso gode delle proprietà
associativa, commutativa e distributiva rispetto alla somma.
Per poter estendere la teoria di Forney al caso 2D e studiare perciò codici
che ammettano anche codificatori razionali, è necessario costruire un opportuno sottoinsieme proprio di F∞ in cui sia definito, per ogni elemento a del sottoinsieme, il prodotto ab dove b ∈ F(z1 , z2 ) (ruolo ricoperto nel caso 1D dalle
serie a supporto compatto a sinistra). Inoltre tale sottoinsieme dovrà essere un
campo rispetto alle usuali operazioni di somma e prodotto, come accade nel
caso unidimensionale per le serie a supporto compatto a sinistra.
1.1
Le serie a supporto compatto nel passato
La scelta più ovvia sarebbe quella di restringersi banalmente alle serie formali a
supporto compatto nel passato, estensione immediata del concetto di compattezza
1
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
a sinistra. Dato un punto (i, j) ∈ Z2 il suo passato è rappresentato dal quarto
di piano P(x, y) = {(x, y)|x 6 i, y 6 j}.
P
Definizione 1.1 La serie a = aij z1i z2j è una serie formale a supporto compatto
nel passato se, preso un qualsiasi punto (m, n) ∈ Z2 , si ha che l’insieme supp(a) ∩
P(m, n) contiene un numero finito di punti.
I due esempi che seguono 1.1 mostrano la scelta delle serie a supporto
compatto nel passato però non sia una buona scelta.
Esempio 1.1 Si considerino le due serie a supporto compatto nel passato:
a=
X
z1i z2j
i+j=0
i60
b=
X
z1i z2j
i+j=0
i>0
e si costruisca il prodotto
c=a·b
Il coefficiente c00 si ottiene come
c00 = a00 b00 + a−1,1 b1,−1 + a−2,2 b2,−2 + . . . =
+∞
X
1
i=0
che analogamente a quanto visto nell’esempio del caso 1D non può essere
ricondotto a una somma finita.
Esempio 1.2 Quando un operazione è ben definita, se essa è associativa e
dotata di elemento neutro, si dimostra facilmente che, quando un elemento
ammette simmetrico rispetto a tale operazione, esso è unico.
Infatti supponiamo che, rispetto all’operazione ∗, esistano due elementi
simmetrici distinti per l’elemento a 6= 0, elementi che verranno denotati rispettivamente c e c′ :
a∗c=c∗a=e
a ∗ c′ = c′ ∗ a = e
Allora si ha
c = c ∗ e = c ∗ (a ∗ c′ ) = (c ∗ a) ∗ c′ = e ∗ c′ = c′
2
1.1 Le serie a supporto compatto nel passato
z2
b
b
z2
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
z1
z1
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
a=
P
i j
i+j=0 z1 z2
i60
b=
P
i j
i+j=0 z1 z2
i>0
Figura 1.1: Le due serie dell’esempio 1.1. Il loro prodotto non è definito.
contro l’ipotesi che siano distinti.
Utilizzando tale risultato dimostriamo che il prodotto alla Cauchy non è
ben definito tra le serie a supporto compatto nel passato. Si consideri il polinomio a = z1 + z2 : esso ovviamente è anche una serie a supporto compatto
nel passato. Calcoliamone l’inversa. Cerchiamo cioè tutte le serie b a supporto
compatto nel passato per cui
ba = 1
Passando alla scrittura con le serie si ha:


X

bij z1i z2j  (z1 + z2 ) = 1
X
(i,j)
(i,j)
bij z1i+1 z2j +
X
X
bij z1i z2j+1 = 1
(i,j)
(bi−1,j + bi,j−1 ) z1i z2j = 1
(i,j)
Da cui uguagliando termine a termine si ha:
(
bi−1,j + bi,j−1 = 0 per (i, j) 6= (0, 0)
b−1,0 + b0,−1 = 1
Tale sistema resta completamente indeterminato anche imponendo la compattezza nel passato del supporto. Esistono cioè infinite serie b a supporto compatto nel passato tali per cui ba = 1 contro il risultato esposto in precedenza.
3
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
Nella ricerca dello spazio su cui definire il codice procederemo a passi successivi, partendo da condizioni molto restrittive e quindi rilassandole passo
dopo passo.
1.2
Le serie causali
Il primo sottoinsieme di cui studieremo le proprietà sono le serie formali ad
esponenti non-negativi o serie formali causali:
F[[z1 , z2 ]] =
(
a|a =
∞ X
∞
X
aij z1i z2j , (i, j) ∈ Z2
i=0 j=0
)
Seppur con una notazione diversa, questa classe di serie formali è la stessa
studiata da O. Zariski e P. Samuel1 ([35, cap. VII]). Con le usuali operazioni
di somma e prodotto alla Cauchy, F[[z1 , z2 ]] è un dominio di integrità ([35, cap.
VII, theor. 1]). Purtroppo esistono serie formali causali non invertibili e perciò F[[z1 , z2 ]] non è un campo. Si possono però caratterizzare in maniera semplice gli elementi invertibili. Questo risultato sarà fondamentale per tutta la
trattazione successiva.
Teorema 1.1 Un elemento di F[[z1 , z2 ]] è invertibile se e solo se a00 6= 0
Per la dimostrazione si veda [35, cap. VII, theor. 2].
Perciò tutte le funzioni razionali avente denominatore con termine noto
non nullo si possono scrivere in modo unico (grazie all’unicità dell’inversa)
come una serie di F[[z1 , z2 ]] (risultano infatti essere prodotto di due elementi
appartenenti a F[[z1 , z2 ]]).
1.3
Le serie debolmente causali
Alla ricerca del sottoinsieme di F∞ che ci permetta di estendere le definizioni del caso unidimensionale, ampliamo il nostro spazio di lavoro dalle serie
formali causali alle serie formali debolmente causali. Le serie di questo tipo sono
state ampiamente studiate da R. Eising ([3]). Per chiarezza e continuità di esposizione riportiamo i concetti principali introdotti da Eising e i risultati da lui
1
Nel libro di Zariski e Samuel gli esponenti sono definiti in N2 . L’insieme delle serie da
loro studiate perciò non coincide esattamente con l’insieme F[[z1 , z2 ]], ma vi è un isomorfismo
d’anello tra i due insiemi.
4
1.3 Le serie debolmente causali
ottenuti, integrando con dimostrazioni e osservazioni dove necessario. Il primo concetto da introdurre per poter lavorare con le serie debolmente causali è
il concetto di cono.
Definizione 1.2 Un insieme C ⊂ R2 è un cono se, preso un qualsiasi punto (x, y)
appartenente all’insieme, vi appartiene anche il punto (λx, λy) con λ ∈ R+
0 . In
particolare un cono si dice proprio se soddisfa le seguenti proprietà:
1. C ∩ (−C) = {(0, 0)}
2. Q1 ⊆ C
dove si sono indicati con −C il simmetrico di C rispetto all’origine di R2 e con Q1 il
primo quadrante di R2 .
z2
z1
Figura 1.2: Esempio di cono
Chiarito il concetto di cono possiamo ora definire le serie debolmente causali.
P
Definizione 1.3 Una serie formale a = (i,j)∈Z2 aij z1i z2j è detta debolmente causale se esiste un cono proprio C tale che
supp(a) ⊂ C
Dalle definizioni si vede come valgano le inclusioni:
{serie causali} ⊂ {serie debolm. causali} ⊂ {serie a supp. comp. passato}
Osservazione Se il prodotto di due serie causali è sempre definito, ciò non è
generalmente vero per le serie debolmente causali. A tal proposito si considerino nuovamente le due serie dell’esempio 1.1. Esse sono entrambe debolmente causali secondo la definizione appena fornita; d’altronde abbiamo già
5
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
causali
debolm. causali
supp. comp. passato
visto come il loro prodotto non sia definito. Questo dipende dell’impossibilità
di trovare un cono proprio che contenga il supporto di entrambe le serie. Per
poter dimostrare questa affermazione si deve introdurre il concetto di cono di
causalità.
Definizione 1.4 Un cono di causalità Cp,q,r,s è l’intersezione di due semipiani Hp,q
e Hr,s :
Hp,q = (x, y) ∈ R2 | p x + q y > 0
Hr,s = (x, y) ∈ R2 | r x + s y > 0
dove p, q, r, s sono coefficienti interi non negativi2 tali che:
ps − qr = 1
z2
z1
Figura 1.3: C2,1,1,1
Osservazione Banalmente un Cp,q,r,s cosı̀ definito è un cono proprio secondo
2
Si noti come in realtà solo q o r possano essere nulli. Quando questo avviene, la condizione
impone p = s = 1 e il cono di causalità si riduce a Q1 .
6
1.3 Le serie debolmente causali
la definizione 1.2. Esso è un cono perché moltiplicando ambo i membri delle
disequazioni per λ si ottiene:
p x̄ + q ȳ > 0 ⇒ p (λx̄) + q (λȳ) > 0
con λ > 0
Essendo intersezione di due semipiani definiti da rette non parallele, Cp,q,r,s
rappresenta un angolo minore di 180◦ e quindi soddisfa la prima condizione
dei coni propri. La seconda condizione invece discende dalla positività di p, q,
r e s (le rette che delimitano Cp,q,r,s giacciono nel 2◦ e 4◦ quadrante).
Preso un qualsiasi cono proprio C si dimostra che si può sempre trovare un
Cp,q,r,s tale che C ⊂ Cp,q,r,s ([3, Lemma 2.5]).
Una delle proprietà fondamentali dei coni di causalità, è che comunque
scelto un cono di causalità Cp,q,r,s , esiste un ordinamento totale tale per cui
l’insieme Z2 ∩ Cp,q,r,s risulta bene ordinato secondo tale ordinamento.
Proposizione 1.2 Sia Cp,q,r,s un cono di causalità. Si consideri l’ordinamento3 dei
punti di Z2 :
(x1 , y1 ) ≺ (x2 , y2 )
se
i. p (x2 − x1 ) + q (y2 − y1 ) > 0
oppure
ii. [p (x2 − x1 ) + q (y2 − y1 ) = 0] ∧ (y1 < y2 ) 4
L’insieme Z2 ∩ Cp,q,r,s è un insieme ben ordinato secondo tale ordinamento (per la
definizione di insieme bene ordinato si veda la definizione A3).
Dimostrazione. La dimostrazione è legata al fatto che N (e quindi Z+
0 ) è un
5
insieme ben ordinato . La prima condizione (che induce un ordine parziale su
Z2 ) può essere riscritta nel seguente modo:
px2 + qy2 > px1 + qy1
3
Questo non è l’unico ordinamento possibile. La scelta cade su questo particolare
ordinamento per proprietà ulteriori che verranno illustrate in seguito.
4
Per le proprietà dei coni di causalità, p 6= 0 perciò y2 = y1 ⇒ x2 = x1
5
A proposito del buon ordinamento di N si veda [19, cap. II, par. 3, prop. 7]
7
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
Preso un qualsiasi I ⊆ Cp,q,r,s , ad ogni punto (x, y) ∈ I ∩ Z2 viene associato
l’intero c(x,y) = p x + q y che per la definizione di Cp,q,r,s è positivo o nullo.
+
L’insieme dei c(x,y) è un sottoinsieme di Z+
0 e per il buon ordinamento di Z0
ammette un minimo c0 .
Si consideri ora l’insieme
M = (x, y) ∈ I ∩ Z2 | p x + q y = c0
Essi sono i minimali secondo l’ordine parziale definito dalla condizione 1. La
loro appartenenza a Cp,q,r,s impone che rx + sy > 0
(
px + qy = c0
⇒
(
qy = c0 − px
⇒
(
qy = c0 − px
⇒
rx + sy > 0
qrx + qsy > 0
qrx + s(c0 − px) > 0
(
(
qy = c0 − px
qy = c0 − px
⇒
⇒
⇒ qy > (1 − ps)c0 ⇒
(qr − ps)x + sc0 > 0
x 6 sc0
⇒ y > −rc0
Come N, anche ogni insieme del tipo {k ∈ Z | k > k0 , k0 ∈ Z} è un insieme
bene ordinato. Le ordinate dei punti di M sono interi e soddisfano la relazione
y > −rc0 . L’insieme delle ordinate ammette perciò minimo ȳ. Il punto (x̄, ȳ) è
il punto cercato.
z2
P7
P9
P4 P3
P2
P6
P1
b
b
b
b
b
b
b
P8
z1
b
P 1 < P2 < P3 < P4 < P5 < P6 < P7 < P8 < P9
Figura 1.4: Esempio di ordinamento con p = 2 e q = 1
A questo punto si hanno gli strumenti necessari per dimostrare che il pro8
1.3 Le serie debolmente causali
dotto di due serie debolmente causali con supporto opportuno è ben definito.
Anzi assegnato un Cp,q,r,s si può dotare l’insieme delle serie definite su di esso
di una struttura algebrica come attestato dalla seguente proposizione.
Proposizione 1.3 Dato un cono di causalità Cp,q,r,s , sia Fp,q,r,s [[z1 , z2 ]] l’insieme costutuito dalla serie nulla e da tutte le serie debolmente causali con supporto contenuto
nel cono Cp,q,r,s . Esso, con le usuali operazioni di somma e prodotto, è un anello6 (per
la definizione di anello si veda A6).
Dimostrazione. Come affermato ad inizio capitolo ricordiamo che F∞ è un
gruppo commutativo rispetto all’usuale operazione di somma e che, per i termini per cui è definito, il prodotto alla Cauchy gode delle proprietà associativa, commutativa e distributiva rispetto alla somma. Tale fatto semplificherà di
molto la dimostrazione.
Siano a e b due generici elementi di Fp,q,r,s [[z1 , z2 ]]
a=
X
aij z1i z2j
b=
X
bhk z1h z2k
(i, j) ∈ Cp,q,r,s ∩ Z2
(h, k) ∈ Cp,q,r,s ∩ Z2
Guardando ai supporti delle serie si ha:
supp(a) ⊆ Cp,q,r,s
supp(b) ⊆ Cp,q,r,s
supp(a + b) ⊆ supp(a) ∪ supp(b) ⊆ Cp,q,r,s
Il supporto della somma è ancora contenuto in Cp,q,r,s ∩ Z2 . Di conseguenza
l’insieme Fp,q,r,s [[z1 , z2 ]] è chiuso rispetto alla somma.
Inoltre la serie nulla (elemento neutro della somma) appartiene per definizione a Fp,q,r,s [[z1 , z2 ]] e data una serie a ∈ Fp,q,r,s [[z1 , z2 ]] si ha che −a ∈
Fp,q,r,s [[z1 , z2 ]] in quanto supp(a) = supp(−a).
Riconoscendo che la somma su Fp,q,r,s [[z1 , z2 ]] è l’operazione indotta dalla
somma su F∞ , essa possiede tutte le proprietà dell’operazione su F∞ . Perciò Fp,q,r,s [[z1 , z2 ]] è un gruppo commutativo rispetto alla somma di Fp,q,r,s [[z1 , z2 ]]
(definizione A5).
6
Una traccia di dimostrazione si può trovare in un articolo di Françoise Delon ([2]) che però
affronta il problema con serie formali definite su gruppi generici e il cui supporto è contenuto
in un generico insieme bene ordinato.
9
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
Il prodotto fra due serie di Fp,q,r,s [[z1 , z2 ]] è definito come:
a·b=


X X

(aij · bhk ) z1m z2n

(m,n)
i+h=m
j+k=n
Dimostriamo innanzitutto che, comunque si prendano a e b in Fp,q,r,s [[z1 , z2 ]],
il prodotto a · b è sempre definito. Esso è ben definito se e solo se è definita la
P
somma (aij · bhk ). Per dimostrare che tale somma è definita si deve sfruttare
il buon ordinamento introdotto nella proposizione 1.2. Ordiniamo i termini
a(i,j) b(h,k) = a(i,j) b(m,n)−(i,j) secondo l’indice (i, j) utilizzando tale ordine. Al
crescere di (i, j), l’indice (h, k) = (m, n) − (i, j) decresce. D’altro canto, ogni
sequenza decrescente di elementi di Cp,q,r,s ∩ Z2 è necessariamente finita visto
che l’insieme è ben ordinato. Perciò a parte un numero finito di termini, gli
a(i,j) b(h,k) hanno indice (h, k) ∈
/ Cp,q,r,s ∩Z2 e per definizione di serie debolmente
P
causale sono nulli. La somma (aij · bhk ) contiene solo un numero finito di
termini non nulli ed è quindi ben definita.
Una volta dimostrato che il prodotto esiste, verifichiamo che supp(a · b) ⊂
Cp,q,r,s . Di seguito riportiamo la dimostrazione che per ogni punto (m, n) del
supporto si ha pm + qn > 0: la dimostrazione che rm + sn > 0 è analoga.
(
pi + qj > 0
ph + qk > 0
⇒ p(i + h) + q(j + k) > 0 ⇒ pm + qn > 0
L’insieme Fp,q,r,s [[z1 , z2 ]] è chiuso rispetto al prodotto alla Cauchy. Il prodotto possiede le proprietà associativa, commutativa e distributiva rispetto alla
somma e quindi Fp,q,r,s [[z1 , z2 ]] è un anello. In particolare poiché la serie formale
1 (elemento neutro del prodotto) appartiene a Fp,q,r,s [[z1 , z2 ]] l’anello è un anello
con unità.
Oltre alla struttura d’anello, Fp,q,r,s [[z1 , z2 ]] possiede tutte le proprietà di
F[[z1 , z2 ]]. I due spazi sono legati infatti da un isomorfismo d’anello.
La costruzione dell’isomorfismo si basa sulla funzione seguente:
ϕ : Cp,q,r,s ∩ Z2 → Q1 ∩ Z2
(m, n) 7→ (pm + qn, rm + sn)
Essa è una funzione biunivoca che mappa i punti di Cp,q,r,s nel primo qua10
1.3 Le serie debolmente causali
drante Q1 . A partire da essa si costruisca la funzione Φ. Essa risulta essere
l’isomorfismo d’anello cercato.
Φ : Fp,q,r,s [[z1 , z2 ]] → F[[z1 , z2 ]]
X
X
aij z1i z2j 7→
aij z1m z2n
dove
(m, n) = ϕ[(i, j)]
Grazie a questo isomorfismo si possono estendere tutte le proprietà delle
serie causali alle serie debolmente causali con supporto nello stesso Cp,q,r,s . In
particolare:
1. dato che ϕ[(0, 0)] = (0, 0) un elemento a di Fp,q,r,s [[z1 , z2 ]] è invertibile se
e solo se il termine noto a00 è non nullo. L’inversa sarà ancora una serie
debolmente causale con il supporto contenuto nello stesso cono Cp,q,r,s
della serie di partenza.
2. assegnato Cp,q,r,s , l’espansione in serie formale di una funzione razionale
è unica.
3. Fp,q,r,s [[z1 , z2 ]] è un dominio di integrità. Se infatti esistessero due elementi a e b entrambi non nulli tali che:
a·b=0
applicando l’isomorfismo ad ambo i membri si avrebbe:
Φ (a · b) = Φ(0)
Φ(a) · Φ(b) = 0
il che è assurdo visto che F[[z1 , z2 ]] è un dominio di integrità.
Essendo isomorfo a F[[z1 , z2 ]], anche Fp,q,r,s [[z1 , z2 ]] non è un campo. Le serie
con termine noto nullo non sono infatti invertibili.
11
Capitolo 1.
1.4
LO SPAZIO DI DEFINIZIONE
Le serie debolmente causali traslate
L’utilizzo delle traslazioni nel campo dei codici è di fondamentale importanza.
Infatti non si vuole che, a messaggi identici elaborati in istanti diversi, corrispondano parole di codice differenti (a meno di una traslazione). L’invarianza alle traslazioni è perciò una richiesta comune nelle definizioni dei codici
convoluzionali7 . La prima conseguenza dell’introduzione delle traslazioni è
la possibilità di estendere la definizione di serie formale debolmente causale
e di poter definire, in opportuni insiemi di tali serie, la struttura di campo.
Innanzitutto diamo la definizione di traslazione.
Definizione 1.5 Dati una serie formale a ∈ F∞ e un punto P = (m, n), P ∈ Z2 ,
l’operatore di traslazione σP si definisce come:
σP (a) = z1m z2n a
(1.1)
L’operatore traslazione σP induce una traslazione anche sui punti di R2
che verrà denotata, per semplicità, ancora con σP . È ben noto che l’operatore
traslazione cosı̀ definito è un automorfismo sul gruppo delle serie formali.
Indicati con P = (m, n) e Q = (h, k) due generici punti di Z2 , l’operatore di
traslazione gode delle seguenti proprietà:
σO (a) = a,
con O = (0, 0)
σP (σQ (a)) = σQ (σP (a))
σP (ab) = z1m z2n ab = σP (a)b = a σP (b)
σP (a + b) = z1m z2n (a + b) = z1m z2n a + z1m z2n b = σP (a) + σP (b)
(m+h) (n+k)
z2
ab
σP (a)σQ (b) = z1m z2n a z1h z2k b = z1
σP (σ−P (a)) = z1m z2n (z1−m z2−n a) = a
= σP +Q (ab)
da cui si deduce che:
σ−P = σP−1
σP (0) = 0
Grazie alle traslazioni possiamo estendere il concetto di cono di causalità.
Definizione 1.6 Sia P = (m, n) ∈ Z2 . Un cono di causalità traslato Cp,q,r,s (P )
è il sottoinsieme di R2 che si ottiene applicando la traslazione σP al cono di causalità
Cp,q,r,s . Con questa notazione si ha ovviamente Cp,q,r,s (O) = Cp,q,r,s .
7
A questo proposito si vedano le definizioni 1D nell’articolo di J. Rosenthal ([26]), oppure
le definizioni 2D di Weiner ([31]) o di Fornasini e Valcher ([9])
12
1.4 Le serie debolmente causali traslate
Osservazione Dalla definizione precedente segue che Cp,q,r,s (P ) può essere
visto anche come l’intersezione di semipiani Hp,q (m, n) e Hr,s (m, n) dove:
Hp,q (m, n) = (x, y) ∈ R2 | p (x − m) + q (y − n) > 0
Hr,s (m, n) = (x, y) ∈ R2 | r (x − m) + s (y − n) > 0
(m, n) ∈ Z2 e p, q, r, s numeri interi nonnegativi per cui ps − qr = 1.
Osservazione I coni di causalità traslati Cp,q,ri ,si (Pi ) mantengono la proprietà
di essere ben ordinati secondo l’ordinamento della proposizione 1.2. Perciò
ogni sottoinsieme di un cono Cp,q,ri ,si (Pi ) ammette minimo.
Per poter definire con maggior facilità le serie debolmente causali traslate,
è utile introdurre a questo punto l’insieme Cp,q .
Definizione 1.7 Dati due numeri interi p > 0 e q > 0, indichiamo con Cp,q l’insieme
di tutti i Cp,q,r,s (P ), con P ∈ Z2 , r ∈ Z0+ , s ∈ Z + e ps − qr = 1.
Tramite Cp,q possiamo ora definire l’insieme Fp,q ((z1 , z2 )) delle serie debolmente causali traslate in Cp,q .
Definizione 1.8 Dati due interi nonnegativi e coprimi p e q, una serie formale a ∈
F∞ si definisce serie debolmente causale traslata in Cp,q se è la serie nulla oppure,
se non nulla, se esistono un punto Pa ∈ Z2 e due interi nonnegativi ra e sa , con
psa − qra = 1, tali che:
supp(a) ⊆ Cp,q,ra ,sa (Pa )
L’insieme delle serie debolmente causali traslate in Cp,q verrà denotato con il simbolo
Fp,q ((z1 , z2 )).
Osservazione Evidenziamo in questo momento una proprietà dei coni di causalità che si può estendere facilmente anche ai coni traslati: essa ci sarà utile
nelle dimostrazioni successive. Siano Cp,q,r1 ,s1 e Cp,q,r2 ,s2 due coni di causalità in
cui p e q sono fissati. Il fatto che (r1 , s1 ) e (r2 , s2 ) siano soluzioni dell’equazione
di Bézout ps − qr = 1 porta le seguenti conseguenze:
r2
r1
Cp,q,r1 ,s1 ⊆ Cp,q,r2 ,s2 ⇐⇒
>
s2
s1
(
(
r2 > r1
r2 = r1 + tp
r1
r2
>
⇐⇒
⇐⇒
per qualche t ∈ Z+
0
s2
s1
s2 > s1
s2 = s1 + tq
13
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
Per poter dimostrare che Fp,q ((z1 , z2 )) è un campo rispetto alle usuali operazioni, dobbiamo anteporre la dimostrazione di due lemmi sui coni di causalità. Il primo lemma ci permetterà di estendere la struttura d’anello delle serie
debolmente causali alle serie debolmente causali traslate. Il secondo lemma
invece sarà la chiave per dimostrare che ogni serie debolmente causale traslata
non nulla è invertibile.
Lemma 1.4 Comunque si prendano Cp,q,r1 ,s1 (P1 ), . . . , Cp,q,rn ,sn (Pn ) in Cp,q si può
sempre trovare un ulteriore cono Cp,q,r0 ,s0 (P0 ) ∈ Cp,q tale che:
Cp,q,r1 ,s1 (P1 ) ⊆ Cp,q,r0 ,s0 (P0 )
..
.
Cp,q,rn ,sn (Pn ) ⊆ Cp,q,r0 ,s0 (P0 )
Dimostrazione. Si individui, innanzitutto, tra le coppie (ri , si ), una coppia
(r0 , s0 ) che massimizzi la quantità srii . Per la proprietà appena evidenziata la
coppia sarà tale per cui anche r0 sarà il massimo tra gli ri . Si costruiscano
quindi i seguenti ordinamenti parziali fra i punti di Z2
(xa , ya ) ≺ (xb , yb ) ⇐⇒ p(xb − xa ) + q(yb − ya ) > 0
p,q
(xa , ya ) ≺ (xb , yb ) ⇐⇒ r0 (xb − xa ) + s0 (yb − ya ) > 0
r0 ,s0
Si noti che per ogni coppia di punti Pa e Pb è vera una ed una sola delle seguenti
affermazioni:
1. Pa ≺ Pb
p,q
2. Pb ≺ Pa
p,q
3. p(xb − xa ) + q(yb − ya ) = 0
e quindi Pa e Pb non sono confrontabili secondo ≺
p,q
Lo stesso si può affermare per l’ordinamento ≺ .
r0 ,s0
Sia ora Pµ uno dei minimali secondo l’ordinamento parziale ≺ e Pν uno dei
p,q
minimali secondo l’ordinamento parziale ≺ . A partire da Pµ e Pν si calcoli il
r0 ,s0
punto Pχ
Pχ :
(
p(x − xµ ) + q(y − yµ ) = 0
r0 (x − xν ) + s0 (y − yν ) = 0
14
1.4 Le serie debolmente causali traslate
Il punto Pχ ∈ R2 esiste sicuramente dato che le due rette non sono parallele.
Una volta calcolato Pχ , sia P0 = (⌊xχ ⌋ , ⌊yχ ⌋), P0 ∈ Z2 . Si vede che P0 Pµ
p,q
e P0 Pν .
r0 ,s0
Il cono Cp,q,r0 ,s0 (P0 ) soddisfa le condizioni della proposizione. Infatti sia
(x̄, ȳ) un qualsiasi punto di Cp,q,ri ,si (Pi ): dimostriamo che (x̄, ȳ) ∈ Cp,q,r0 ,s0 (P0 ).
Si ricorda che, essendo Z un anello algebricamente ordinato(si veda la def. A4),
la somma (e il prodotto) di interi positivi è ancora un intero positivo.
(
p(x̄ − xi ) + q(ȳ − yi ) > 0
(definizione di Cp,q,ri ,si (Pi ))
p(xi − x0 ) + q(yi − y0 ) > 0 (infatti P0
Pi , ∀Pi )
p,q
(sommando le due quantità si ottiene ancora un intero positivo)
⇒ p(x̄ − x0 ) + q(ȳ − y0 ) > 0

p(x̄ − xi ) + q(ȳ − yi ) > 0






r (x̄ − xi ) + si (ȳ − yi ) > 0

 i
r0 (xi − x0 ) + s0 (yi − y0 ) > 0

)


r0 = ri + tp



+
per qualche t ∈ Z0


s0 = si + tq
(definizione di Cp,q,ri ,si (Pi ))
(definizione di Cp,q,ri ,si (Pi ))
(ordinamento dei Pi )
(r0 > ri , ∀ri )
(moltiplicando la prima eq. per t e sommandola alla seconda ci si riconduce al caso precedente)
⇒ r0 (x̄ − x0 ) + s0 (ȳ − y0 ) > 0
Poiché il punto (x̄, ȳ) soddisfa le due condizioni
(
p(x̄ − x0 ) + q(ȳ − y0 ) > 0
r0 (x̄ − x0 ) + s0 (ȳ − y0 ) > 0
esso per definizione appartiene a Cp,q,r0 ,s0 (P0 ).
Lemma 1.5 Sia a 6= 0, a ∈ Fp,q ((z1 , z2 )). Allora esistono un punto Pa = (xa , ya ) ∈
supp(a) e due interi nonnegativi ra e sa con psa − qra = 1 tali che:
supp(a) ⊆ Cp,q,ra ,sa (Pa )
Pa risulta univocamente determinato e coincide con il minimo del supporto di a secondo l’ordinamento della proposizione 1.2.
Dimostrazione. Dimostriamo innanzitutto che scegliendo Pa come vertice del
15
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
cono di causalità traslato si riescono a trovare ra e sa . La dimostrazione sarà
condotta in tre passi successivi.
Primo passo
Osserviamo innanzitutto che grazie all’ordinamento della proposizione 1.2 tutti i punti (x, y) ∈ supp(a) verificano la disuguaglianza p(x − xa ) + q(y − ya ) >
0 che costituisce la prima condizione da soddisfare per l’appartenenza a un
qualsiasi Cp,q,ri ,si (Pa ).
Per la definizione di serie debolmente causale traslata in Cp,q esiste un cono
Cp,q,r1 ,s1 (P1 ) tale che
supp(a) ⊆ Cp,q,r1 ,s1 (P1 )
Si ponga ra = r1 e sa = s1 . A questo punto possono verificarsi due situazioni: supp(a) ∈ Cp,q,ra ,sa (Pa ) oppure supp(a) ∈
/ Cp,q,ra ,sa (Pa ). Nel primo caso la
ricerca è conclusa; nel secondo caso, dato che come abbiamo osservato la prima equazione del cono Cp,q,ra ,sa (Pa ) è soddisfatta ∀(x, y) ∈ supp(a), i punti del
supporto che non appartengono al cono devono essere tali per cui:
r1 (x − xa ) + s1 (y − ya ) < 0
Indichiamo con N l’insieme dei punti di supp(a) che non appartengono al cono
Cp,q,r1 ,s1 (Pa ).
z2
z2
Pa
b
b
P1
b
z1
P1
N
z1
Secondo passo
Analogamente a quanto visto nella proposizione 1.2 con gli interi p e q, anche a
partire dagli interi nonnegativi r ed s (sempre con ps − qr = 1) si può costruire
un ordinamento totale in modo che il cono di causalità Cp,q,r,s (e quindi anche
16
1.4 Le serie debolmente causali traslate
tutti i coni Cp,q,r,s (Pi )) risulti ben ordinato8 . Tale ordinamento è cosı̀ definito
(x1 , y1 ) ≺ (x2 , y2 )
se
i. r (x2 − x1 ) + s (y2 − y1 ) > 0
oppure
ii. [r (x2 − x1 ) + s (y2 − y1 ) = 0] ∧ (x1 < x2 ) 9
Dato che N ⊂ supp(a) ⊂ Cp,q,r1 ,s1 (P1 ), per la definizione di insieme ben ordinato N ha un minimo secondo l’ordinamento indotto da r1 e s1 . Indichiamo
con P2 = (x2 , y2 ) tale minimo. Si ponga r̃2 = ya − y2 e s̃2 = x2 − xa . Come
conseguenza dei passi precedenti dell’algoritmo si ha r̃2 > 0 e s̃2 > 0. Infatti se
r̃2 = ya − y2 6 0, o P2 ∈ Cp,q,r1 ,s1 (Pa ) oppure P2 ≺ Pa con l’ordinamento della
proposizione 1.2. Allo stesso modo si vede che s̃2 > 0. Inoltre si ha
r̃2
r1
>
s̃2
s1
perché altrimenti si avrebbe P2 ∈ Cp,q,r1 ,s1 (Pa ).
Consideriamo i punti (x, y) ∈ N per cui x > x2 . Risulta:
r1 (x − x2 ) + s1 (y − y2 ) > 0 =⇒
=⇒
r1
y2 − y
6
=⇒
x − x2
s1
y2 − y
r̃2
6
=⇒ r̃2 (x − x2 ) + s̃2 (y − y2 ) > 0 =⇒
x − x2
s̃2
=⇒ (ya − y2 )(x − x2 ) + (x2 − xa )(y − y2 ) > 0 =⇒
=⇒ ya x − ya x2 − xy2 + x2 y2 + x2 y − x2 y2 − yxa + xa y2 > 0 =⇒
=⇒ ya x − ya x2 − xy2 + x2 y − yxa + xa y2 > 0 =⇒
=⇒ ya x − xy2 − xa ya + xa y2 + x2 y − x2 ya − yxa + xa ya > 0 =⇒
=⇒ (ya − y2 )(x − xa ) + (x2 − xa )(y − ya ) > 0 =⇒
=⇒ r̃2 (x − xa ) + s̃2 (y − ya ) > 0
I punti di N per cui x > 2 perciò sono contenuti nel cono Cp,q,r̃2 ,s̃2 (Pa ). Risulta
allora: La coppia (r̃2 , s̃2 ) non è in generale soluzione dell’equazione ps−qr = 1.
8
La dimostrazione di questo fatto è in tutto e per tutto analoga alla proposizione 1.2 e perciò
verrà omessa.
9
Si noti che stavolta si ha s 6= 0 perciò x2 = x1 ⇒ y2 = y1
17
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
Se (r̃2 , s̃2 ) non è soluzione, per la struttura delle soluzioni di un’equazione di
Bézout, possiamo trovare sempre una soluzione (r2 , s2 ) in modo che sr22 > s̃r̃22 .
Risulta perciò:
Cp,q,r2 ,s2 (Pa ) ⊇ Cp,q,r̃2 ,s̃2 (Pa ) ⊃ Cp,q,r1 ,s1 (Pa )
Come al passo precedente anche in questo caso si può avere supp(a) ∈ Cp,q,r2 ,s2 (Pa ),
e in tal caso la nostra ricerca sarebbe finita, oppure supp(a) ∈
/ Cp,q,r2 ,s2 (Pa ) e in
tal caso passiamo al terzo e ultimo passo dell’algoritmo.
z2
Pa
z2
Pa
b
b
b
b
b
P2
z1
b
P2
z1
Terzo passo
Noi sappiamo delimitare con precisione i punti di supp(a) che non appartengono a Cp,q,r2 ,s2 (Pa ). Per come è stato costruito il cono Cp,q,r2 ,s2 (Pa ) infatti essi
devono appartenere al seguente triangolo:



 p(x − xa ) + q(y − ya ) > 0
r1 (x − xa ) + s1 (y − ya ) > 0



r2 (x − xa ) + s2 (y − ya ) < 0
(Pa è il minimo con l’ordinamento secondo p e q)
(P2 è il minimo con l’ordinamento secondo r1 e s1 )
(i punti non appartengono tuttavia al cono Cp,q,r2 ,s2 (Pa ))
Per costruzione le tre rette non sono parallele e quindi effettivamente l’intersezione dei tre semipiani è un triangolo. Essendo racchiusi in una porzione di
piano finita, i punti del supporto che non appartengono al cono Cp,q,r2 ,s2 (Pa )
sono in numero finito. Indichiamo tali punti come Q1 , . . . , Qn . Tra i Qi si scelga
−yi
il punto Qm che massimizza la quantità xyai −x
. Con un ragionamento analogo
a
a quello condotto nel secondo passo si dimostra che tutti i Qi appartengono
al cono Cp,q,r̃3 ,s̃3 (Pa ) con r̃3 = ya − ym e s̃3 = xm − xa . Anche questa volta si
possono determinare r3 e s3 , soluzioni dell’equazione ps − qr = 1, in modo che
18
1.4 Le serie debolmente causali traslate
r3
s3
>
r̃3
.
s̃3
Il cono Cp,q,r3 ,s3 (Pa ) è il cono cercato.
Unicità
È banale rendersi conto che Pa è l’unico punto del supporto per cui si possa
trovare un cono di causalità Cp,q,r,s (Pa ) che contenga il supporto. Scegliendo
qualsiasi altro punto Pi del supporto, per l’ordinamento della proposizione
1.2, o si ha p(xa − xi ) + q(ya − yi ) < 0 o p(xa − xi ) + q(ya − yi ) = 0 e ya < yi .
In quest’ultimo caso è impossibile trovare r ed s che soddisfino la relazione
ps − qr = 1 visto che Pa si trova sulla retta p(x − xi ) + q(x − xi ) = 0.
z2
Pa
z2
Pa
b
b
b
b
b
z1
z1
Osservazione A posteriori ci si potrebbe chiedere perché nella dimostrazione
della proposizione 1.5 non si applichi direttamente il terzo passo a tutti i punti
∗ −y
i
di supp(a). Il problema è che le quantità xyai −x
∗ sono numeri razionali e in Q non
a
è garantito a priori che un insieme di infiniti elementi, seppur limitato (infatti
∗ −y
p
i
si ha sr11 6 xyai −x
∗ < q ), ammetta massimo.
a
Le proposizioni 1.4 e 1.5 sono la chiave per la dimostrazione che Fp,q ((z1 , z2 ))
è un campo con le usuali operazioni di prodotto.
Proposizione 1.6 Siano p ∈ Z+ e q ∈ Z+
0 due interi coprimi. L’insieme Fp,q ((z1 , z2 ))
delle serie debolmente causali traslate in Cp,q , con le operazioni usuali di somma e
prodotto, risulta essere un campo (si veda la definizione A7)
Dimostrazione. Analogamente quanto visto per la proposizione 1.3, per dimostrare che Fp,q ((z1 , z2 )) è un anello basta far vedere che Fp,q ((z1 , z2 )) è un
insieme chiuso rispetto alle usuali operazioni di somma e prodotto. Le proprietà delle operazioni poi saranno ereditate dalle operazioni definite in F∞ .
19
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
Somma
Siano a e b due serie appartenenti a Fp,q ((z1 , z2 )). In generale i supporti delle due serie sono contenuti in due coni differenti, Cp,q,ra ,sa (Pa ) e Cp,q,rb ,sb (Pb ).
Tramite il lemma 1.4 si trova un cono Cp,q,r0 ,s0 (P0 ) che contiene entrambi i supporti. A questo punto, similmente a quanto accade per le serie debolmente
causali, risulta:
supp(a) ⊆ Cp,q,ra ,sa (Pa )
supp(b) ⊆ Cp,q,rb ,sb (Pb )
supp(a + b) ⊆ supp(a) ∪ supp(b) ⊆ Cp,q,r0 ,s0 (P0 )
Fp,q ((z1 , z2 )) di conseguenza è chiuso rispetto all’usuale operazione di somma.
Inoltre l’elemento neutro della somma appartiene a Fp,q ((z1 , z2 )) per definizione e l’opposto di una serie a ∈ Fp,q ((z1 , z2 )) è ancora ovviamente una serie debolmente causale traslata in Cp,q (le due serie hanno lo stesso supporto). Con
l’usuale operazione di somma perciò Fp,q ((z1 , z2 )) è un gruppo commutativo.
Prodotto
Per determinare se Fp,q ((z1 , z2 )) sia chiuso anche rispetto al prodotto sfruttiamo
un ragionamento simile a quello della somma. Date due serie debolmente causali traslate a e b, determiniamo un cono Cp,q,r0 ,s0 (P0 ) che contenga i supporti
di entrambe le serie. Cp,q,r0 ,s0 (P0 ) è un insieme bene ordinato secondo l’ordinamento della proposizione 1.2. Similmente a quanto visto nella proposizione
1.3, il “buon ordinamento” fa sı̀ che ogni singolo coefficiente del prodotto a · b
sia riconducibile a una somma finita e che quindi la definizione di prodotto
alla Cauchy sia ben posta anche per gli elementi di Fp,q ((z1 , z2 )). Grazie alle
proprietà delle traslazioni si vede come il prodotto a · b sia ancora una serie di
Fp,q ((z1 , z2 ))10 .
a · b = σPa +Pb σP−1a +Pb (a · b) = σPa +Pb σP−1a (a) · σP−1b (b)
Il prodotto σP−1a (a) · σP−1b (b), infatti, risulta essere il prodotto di due serie debolmente causali. Il supporto di tale prodotto sarà contenuto in un opportuno
cono di causalità Cp,q,r̃,s̃ . Applicando la traslazione a ogni punto del supporto
10
Pa e Pb sono i punti la cui esistenza è assicurata dal lemma 1.5
20
1.4 Le serie debolmente causali traslate
risulta:
supp(a · b) = σPa +Pb (supp(σP−1a (a) · σP−1b (b))) ⊆ σPa +Pb (Cp,q,r̃,s̃ ) = Cp,q,r̃,s̃ (Pa + Pb )
L’elemento neutro del prodotto è una serie debolmente causale e quindi
anche debolmente causale traslata. Come già per le serie debolmente causali
anche in questo caso il prodotto eredita tutte le proprietà del prodotto in F∞ .
Esponiamo brevemente di seguito una verifica alternativa della proprietà
distributiva che sfrutta le proprietà delle traslazioni:
(a + b) · c = σP0 +Pc σP−10 +Pc [(a + b) · c] = σP0 +Pc σP−10 (a + b) · σP−1c (c) =
= σP0 +Pc σP−10 (a) + σP−10 (b) · σP−1c (c) =
(le serie sono ora tutte debolmente causali e posso applicare la proprietà distributiva)
= σP0 +Pc σP−10 (a) · σP−1c (c) + σP−10 (b) · σP−1c (c) =
= σP0 +Pc σP−10 (a) · σP−1c (c) + σP0 +Pc σP−10 (b) · σP−1c (c) =
=a·c+b·c
Il lemma 1.4 ci permette infine di dimostrare anche che Fp,q ((z1 , z2 )) è un
dominio di integrità. Se infatti esistessero due serie a 6= 0 e b 6= 0 tali che:
a·b=0
applicando la traslazione σP−1a +Pb a entrambi i membri si otterrebbe:
σP−1a +Pb (a · b) = σP−1a +Pb (0)
σP−1a (a) · σP−1b (b) = 0
Si sarebbero cosı̀ trovate due serie debolmente causali non nulle il cui prodotto
è nullo. Questo è impossibile perché l’insieme delle serie debolmente causali è
un anello di integrità.
Da quanto emerso finora si vede che Fp,q ((z1 , z2 )) è un dominio di integrità.
Inversa di una serie non nulla
Per dimostrare che ogni elemento non nullo di Fp,q ((z1 , z2 )) è invertibile ci si
serve del lemma 1.5.
21
Capitolo 1.
LO SPAZIO DI DEFINIZIONE
Sia a 6= 0 una serie di Fp,q ((z1 , z2 )). Si vede che σP−1a (a) è una serie debolmente causale11 invertibile in quanto il termine noto è non nullo (si ricorda che
Pa ∈ supp(a)). Sia b la serie debolmente causale inversa di σP−1a (a). Allora:
σP−1a (a) · b = 1
σP−1a σPa σP−1a (a) · b = 1
a · σP−1a (b) = 1
Perciò la serie a è invertibile e σP−1∗ (b) ne è l’inversa.
Da quest’ultima proprietà segue che Fp,q ((z1 , z2 )) è un campo.
Corollario 1.7 Tutte le funzioni razionali si possono espandere in modo unico come
serie del campo Fp,q ((z1 , z2 )).
Dimostrazione. Sia
u(z1 , z2 ) =
a[z1 , z2 , z1−1 , z2−1 ]
b[z1 , z2 , z1−1 , z2−1 ]
la funzione razionale da rappresentare. I due polinomi a ∈ F[z1 , z2 , z1−1 , z2−1 ]
e b ∈ F[z1 , z2 , z1−1 , z2−1 ] possono sempre venire interpretati come elementi di
Fp,q ((z1 , z2 )), qualunque siano p e q. In particolare anche b1 sarà ancora un elemento di Fp,q ((z1 , z2 )) e il prodotto di due elementi di Fp,q ((z1 , z2 )) è ancora
un elemento di Fp,q ((z1 , z2 )). L’espansione è unica perché unica è l’inversa di
b.
Osservazione La struttura di campo conferita a Fp,q ((z1 , z2 )) dalle usuali operazioni di somma e prodotto ha come immediata conseguenza che Fp,q ((z1 , z2 ))n
è uno spazio vettoriale su Fp,q ((z1 , z2 )) con le seguenti operazioni di somma e
prodotto esterno:
a = (a1 , a2 , . . . , an ) ∈ Fp,q ((z1 , z2 ))n
b = (b1 , b2 , . . . , bn ) ∈ Fp,q ((z1 , z2 ))n
c ∈ Fp,q ((z1 , z2 ))
a + b = (a1 + b1 , a2 + b2 , . . . , an + bn )
c a = (c · a1 , c · a2 , . . . , c · an )
11
Se al posto di Pa si fosse scelto per la traslazione un qualsiasi altro punto Q del supporto,
non sarebbe stata una serie debolmente causale traslata appartenente a Fp,q,r,s [[z1 , z2 ]].
−1
σQ
(a)
22
Capitolo 2
Codici 2D. Definizioni e proprietà
2.1
La definizione di codice bidimensionale
Dopo la lunga analisi condotta nell’ambito delle serie formali per costruire il
campo, possiamo finalmente introdurre la definizione che estende al caso 2D
la definizione di Forney. Dovendo specificare obbligatoriamente un insieme
Fp,q ((z1 , z2 )) ben preciso, sceglieremo nel seguito p = 1 e q = 1.
Definizione 2.1 Un codice convoluzionale bidimensionale C è un F1,1 ((z1 , z2 ))-sottospazio
di F1,1 ((z1 , z2 ))n , di dimensione k, avente una base di vettori in F(z1 , z2 )n
Osservazione Il fatto di avere una base in F(z1 , z2 )n garantisce l’esistenza di
una matrice razionale G le cui righe sono formate dai vettori della base, per cui
C = y ∈ F1,1 ((z1 , z2 ))n |y = uG, u ∈ F1,1 ((z1 , z2 ))k
G si dice codificatore del codice C.
Osservazione Nel proseguo della trattazione in alcuni casi considereremo i
codici come serie debolmente causali traslate in Cp,q con coefficienti in Fn .
È immediato vedere che le due interpretazioni del codice C hanno le stesse
proprietà e i risultati dell’una corrispondono ai risultati dell’altra.
2.2
Codificatori iniettivi
Uno dei requisiti fondamentali di un codice è sicuramente che l’operazione di
codifica sia iniettiva, cioè che a sequenze in ingresso differenti corrispondano
sequenze codificate differenti. A questo fatto è legata anche la possibilità di
ricostruire dalle sequenze codificate la sequenza di informazione in ingresso.
23
Capitolo 2.
CODICI 2D. DEFINIZIONI E PROPRIETÀ
La definizione 2.1 non specifica quale sia lo spazio delle sequenze in ingresso: esso in generale sarà uno spazio del tipo F1,1 ((z1 , z2 ))h . L’immagine
di F1,1 ((z1 , z2 ))h tramite il processo di codifica è proprio il codice C che ha dimensione k. Indicato con G un codificatore di C, per le proprietà dell’algebra
lineare ([24, prop. 1.3, pag. 106]) si ha:
h = k + dim(ker(G))
Da questo segue che se e solo se h = k si ha che dim(ker(G)) = 0 e l’operazione
di codifica risulta iniettiva ([24, oss. 1.4, pag. 103]).
Considerando il problema dal punto di vista dei codificatori, si vede come
i codificatori iniettivi per C siano tutte e sole le matrici a rango pieno di riga di
dimensioni k × n.
2.3
Codificatori equivalenti
Un’altra caratteristica del codice che si può ricavare dalle proprietà dell’algebra lineare è la caratterizzazione dei codificatori equivalenti. Innanzitutto
diamo la definizione di codificatori equivalenti
Definizione 2.2 Due matrici razionali G1 ∈ F(z1 , z2 )k1 ×n e G2 ∈ F(z1 , z2 )k2 ×n si
definiscono codificatori equivalenti per il codice C se
im(G1 ) = im(G2 ) = C
L’equivalenza dei codificatori non dipende perciò dalle dimensioni delle
matrici, né dallo spazio delle sequenze in ingresso. L’interesse è focalizzato
tutto sul codice, indipendentemente da come esso sia stato prodotto.
Grazie a questo approccio possiamo vedere come banalmente, dato un codice C, esso ammette sempre un codificatore iniettivo. Dato un codificatore
generico G, un codificatore iniettivo si costruisce infatti selezionando tra le k1
righe di G un insieme massimale di k righe linearmente indipendenti.
Come conseguenza, d’ora in poi considereremo solo codificatori iniettivi.
Restringendoci a questa classe di codificatori, possiamo estendere i risultati sui
codificatori equivalenti presenti nella teoria dei codici 1D (si veda ad esempio
[6, pag. 223]).
Proposizione 2.1 Sia G ∈ F(z1 , z2 )k×n un codificatore (iniettivo) per il codice C.
24
2.3 Codificatori equivalenti
i. Tutti gli altri codificatori iniettivi di C sono le matrici
G′ (z1 , z2 ) = T (z1 , z2 )G(z1 , z2 )
con T (z1 , z2 ) ∈ F(z1 , z2 )k×k matrice razionale invertibile.
ii. Fra i codificatori equivalenti a G ne esistono sempre di polinomiali
iii. Fra i codificatori polinomiali ne esistono sempre di left factor prime (ℓF P )
Dimostrazione.
i. La matrice T è la matrice di cambiamento di base tra G e G′ . Al variare
di T tra le matrici quadrate invertibili a elementi in F(z1 , z2 ) si ottengono
tutte le possibili basi di C, si ottengono cioè tutti i codificatori iniettivi
equivalenti (si veda ad esempio [24, cap. 3, par 8.]).
ii. Diamo la rappresentazione matriciale fratta sinistra di G.
G(z1 , z2 ) = D−1 (z1 , z2 )N (z1 , z2 ) con D ∈ F[z1 , z2 ]k×k , N ∈ F[z1 , z2 ]k×n
Basta scegliere T = D((z1 , z2 ). N (z1 , z2 ) è il codificatore polinomiale
equivalente cercato.
iii. In due dimensioni è ancora disponibile un algoritmo per estrarre il massimo comun divisore sinistro ([9, coroll. A.2]). Si può perciò esprimere il
codificatore polinomiale G[z1 , z2 ] come:
e 1 , z2 ]
G[z1 , z2 ] = ∆[z1 , z2 ]G[z
e matrice ℓF P
con G
e 1 , z2 ] è un codificatore iniettivo equivaPer quanto visto al punto (i) G[z
lente a G[z1 , z2 ]. In particolare ricordiamo che per matrici in due indeterminate i concetti di factor primeness e minor primeness coincidono. Quindi
e è anche ℓM P . Se si stessero considerando codici nD, con n > 3, questo
G
non sarebbe più vero.
Osservazione Rispetto alle analoghe proprietà dei codificatori equivalenti nel
caso unidimensionale, si noti che non sono presenti, nel caso 2D, le proprietà
legate ai gradi delle righe. Questa non è una dimenticanza ma è una mancanza legata al fatto che nel caso 2D è ancora aperto il problema della realizzazione minima. Si potrebbero costruire codificatori equivalenti ridotti per
25
Capitolo 2.
CODICI 2D. DEFINIZIONI E PROPRIETÀ
righe rispetto a z1 o a z2 , senza ottenere però alcun riscontro nelle proprietà del
codice.
Osservazione Oltre alle differenze nelle proprietà legate ai gradi (e quindi al
numero di elementi di memoria coinvolti nella realizzazione del codificatore) sottolineiamo il fatto che nel caso 2D, dato un codificatore, non è sempre
possibile ottenere un codificatore polinomiale ad esso equivalente che sia left
zero prime. Una volta trovato un codificatore polinomiale ℓF P tutti gli altri
codificatori ℓF P equivalenti si ottengono scegliendo la matrice T unimodulare. Siccome la Zero Primeness è una proprietà invariante nella moltiplicazione
per una matrice unimodulare o tutti i codificatori polinomiali ℓF P sono anche ℓZP oppure nessuno di essi lo è ed è impossibile costruire un codificatore
polinomiale ℓZP equivalente (infatti si ha che ℓZP ⇒ℓF P ).
Questo fatto ha conseguenze molto importanti che non si ritrovano negli
analoghi risultati del caso unidimensionale. In particolare, come vedremo, se
non esiste un codificatore equivalente ℓZP sarà impossibile avere contemporaneamente codificatore e decodificatore polinomiali.
2.4
Codificatori e decodificatori non catastrofici
2.4.1 Decodifica non catastrofica semplice
Come è stato detto nell’introduzione, lo scopo principale di un codice a correzione d’errore è quello di rilevare e in caso correggere gli errori di trasmissione
di un sistema di comunicazione. Utilizzando i codici convoluzionali possono
presentarsi casi in cui il verificarsi di un numero finito di errori di trasmissione,
non solo non viene rilevato, ma addirittura porta ad avere un numero infinito
di errori in decodifica. In questi casi si parla di decodifica catastrofica.
La possibilità di verificarsi di tale situazione è legata alla struttura dei codificatori e allo spazio di definizione dei segnali. Dipendentemente dalla struttura dei segnali in ingresso (serie formali, serie formali causali, serie formali
debolmente causali traslate) variano le condizioni per la non catastroficità.
Vediamo innanzitutto come la decodifica catastrofica sia sempre legata alla
capacità del codificatore di mappare sequenze a supporto infinito in parole di
codice a supporto finito.
Sia y una parola di codice. Dopo essere stata prodotta dal codificatore, la
sequenza y viene inviata su un canale di trasmissione rumoroso. In ricezione
26
2.4 Codificatori e decodificatori non catastrofici
la sequenza ricevuta r conterrà perciò un certo numero di errori e in generale
non apparterrà più al codice C.
rumore
y
u
G
r̂
+
+
F1,1 ((z1 , z2 ))n
F1,1 ((z1 , z2 ))k
ŷ
proiez.
û
X
F1,1 ((z1 , z2 ))n
F1,1 ((z1 , z2 ))k
Figura 2.1: Sistema di trasmissione con codifica
Il processo di decodifica di r si compone di due fasi. Nella prima fase la parola r viene “proiettata” su C, si cerca cioè la parola di codice ŷ che ha minima
distanza (di Hamming) da r. Sotto la ragionevole ipotesi che la probabilità che
si siano verificati x errori sia inversamente proporzionale al numero degli errori, ŷ risulta essere la miglior stima della parola di codice trasmessa. Una volta
effettuata la stima si può operare la decodifica vera e propria, ricostruendo il
messaggio di informazione û applicando a ŷ la trasformazione inversa rispetto
a quella del codificatore. Se il codificatore è iniettivo tale trasformazione esiste
sempre come afferma la seguente proposizione.
Proposizione 2.2 Sia G ∈ F(z1 , z2 )k×n una matrice razionale a rango pieno di riga.
Essa ammette una inversa destra X ∈ F(z1 , z2 )n×k .
Dimostrazione. Essendo una matrice razionale con rango di riga pieno G può
e ∈ F(z1 , z2 )n×n invertibile.
venire completata a una matrice quadrata G
e=
G
"
G
G2
#
e ∈ F(z1 , z2 )n×n la matrice inversa di G.
e
Sia X
eX
e=
G
"
#
G h
G2
X
i
X2 =
"
GX
GX2
G2 X
G2 X2
#
=
"
Ik
0
0
In−k
#
= In
La matrice X ∈ F(z1 , z2 )n×k è una inversa destra della matrice G. Essa non è
unica perché dipende dalla scelta della matrice G2 . Si noti che se G non fosse
stata a rango di riga pieno sarebbe stato impossibile completarla a una matrice
invertibile e trovare quindi l’inversa destra.
27
Capitolo 2.
CODICI 2D. DEFINIZIONI E PROPRIETÀ
Il messaggio di informazione û si ottiene perciò come
û = ŷX
Si consideri ora il caso in cui il codificatore G trasformi un messaggio a
supporto infinito y in un messaggio a supporto finito u in cui solo un numero
x di campioni siano diversi da 0. Se nella trasmissione si verificassero degli
errori proprio in corrispondenza di questi x campioni il ricevitore riceverebbe
la parola r = 0 che verrebbe a sua volta decodificata nella parola nulla û =
0. In questo caso un numero finito x di errori avrebbe causato un numero
infinito di errori sul messaggio di informazione (il messaggio originario aveva
un numero infinito di campioni non nulli).
Per capire come effettivamente si abbia una decodifica catastrofica solo in
presenza di un siffatto codificatore andiamo ad esaminare gli errori nella decodifica. In decodifica possiamo commettere un errore nella stima della parola
di codice
ey = ŷ − y
che si riflette in un errore nel messaggio di informazione:
eu = û − u = ey X
ey essendo differenza di due parole di codice è anch’esso una parola di codice,
ey = vG. Si può vedere come esso sia effettivamente l’immagine di eu . Infatti
si ha:
eu G − ey = ey (XG − In ) = vG (XG − In ) = v(G − G) = 0
Perciò un errore di stima ey su un numero finito di campioni può dar luogo a
un errore eu su un numero infinito di campioni del messaggio se e solo se il
codificatore può codificare messaggi a supporto infinito in parole di codice a
supporto finito.
Su questa base diamo la definizione di codificatore catastrofico.
Definizione 2.3 Dato un codice C un suo codificatore G si dice catastrofico se esistono delle parole di codice y a supporto finito che sono immagine di un messaggio u a
supporto infinito.
Per la caratterizzazione dei codificatori catastrofici partiamo ad analizzare
dapprima i codificatori polinomiali.
28
2.4 Codificatori e decodificatori non catastrofici
Proposizione 2.3 Sia G un codificatore polinomiale del codice C. Condizione necessaria e sufficiente perché G sia un codificatore non catastrofico è che la matrice G sia
left factor prime.
Dimostrazione. Per la dimostrazione si veda il lemma 2.4 dell’articolo di Fornasini e Valcher ([9]).
Nel caso generale di codificatori razionali la condizione va posta sul numeratore delle rappresentazioni matriciali fratte sinistre irriducibili, come d’altronde nel caso unidimensionale ([6]).
Proposizione 2.4 Sia G un codificatore razionale del codice C. Condizione necessaria e sufficiente perché G sia un codificatore non catastrofico è che per ogni rappresentazione matriciale fratta sinistra di G, G = D−1 N la matrice numeratore N sia left
factor prime.
Dimostrazione.
Condizione necessaria
La dimostrazione della condizione necessaria ricalca la dimostrazione del caso
unidimensionale. Se la matrice numeratore N non fosse ℓF P , per la proposizione 2.3 esisterebbe un vettore u ∈
/ F[z1 , z2 , z1−1 , z2−1 ]k tale che
y = uN
con y ∈ F[z1 , z2 , z1−1 , z2−1 ]n . Consideriamo ora il vettore v = uD. Si ha che:
vG = uDD−1 N = uN = y
vG è perciò polinomiale di Laurent. D’altra parte v ∈
/ F[z1 , z2 , z1−1 , z2−1 ]k . Infatti,
dato che D−1 N è una RMF irriducibile e u è razionale, si ha che
h
i h
i
u D N = v y
h
i
che non può essere polinomiale dato che D N è ℓF P . Visto che abbiamo
imposto y ∈ F[z1 , z2 , z1−1 , z2−1 ]n , da questo segue che v non può essere polinomiale. A questo punto avremmo che il vettore a supporto infinito v viene
mappato in un vettore polinomiale vG, contro l’ipotesi.
29
Capitolo 2.
CODICI 2D. DEFINIZIONI E PROPRIETÀ
Condizione sufficiente
Similmente a quanto visto per la condizione necessaria se G fosse un codificatore catastrofico esisterebbe un u ∈
/ F[z1 , z2 , z1−1 , z2−1 ]k tale che
y = uG = uD−1 N
con y ∈ F[z1 , z2 , z1−1 , z2−1 ]
h
−1
i
Consideriamo ora il vettore v = uD . Moltiplicandolo per la matrice D N
si ottiene
h
i h
i
v D N = u y
h
i
che è un vettore non polinomiale. Essendo D N polinomiale, segue che
anche v è non polinomiale. A questo punto si avrebbe che un vettore v non
polinomiale viene mappato dalla matrice N nel vettore polinomiale y contro
l’ipotesi.
Osservazione La condizione di non catastroficità è fortemente legata allo spazio di definizione dei segnali: essa infatti è legata all’invertibilità dei polinomi
all’interno dello spazio di definizione (si veda la propos. 3.2). Per esempio
considerando codici costruiti sullo spazio F[[z1 , z2 ]] delle serie causali (si veda
ad esempio [31, chap. 5]), la condizione di catastroficità diventa: un codice è
catastrofico se e solo se esiste un polinomio non costante d ∈ F[z1 , z2 ] con termine
noto non nullo tale che d sia un divisore comune di tutti i divisori del codificatore ([31,
prop. 5.1.7]. Vengono cioè permessi fattori comuni con termine noto nullo.
Osservazione Come si può vedere nell’articolo di Fornasini-Valcher ([11]), in
realtà la non catastroficità è legata alla left minor primeness (ℓM P ) del codificatore. In questa sede abbiamo parlato sempre di left factor primeness (ℓF P )
perché nel caso bidimensionale i due concetti coincidono.
2.4.2 Decodifica non catastrofica robusta
La condizione di non catastroficità che abbiamo trovato presuppone che la parola ŷ che viene introdotta nel decodificatore sia una parola di codice. Se non
si effettua preventivamente la stima e si decodifica il messaggio in un unico
passo, la condizione da porre sul codificatore deve essere più restrittiva. Per
avere una decodifica non catastrofica, qualunque sia la parola in ingresso al decodificatore, il decodificatore deve essere polinomiale. Vale infatti il seguente
risultato.
30
2.4 Codificatori e decodificatori non catastrofici
Proposizione 2.5 Sia X un decodificatore razionale non polinomiale per il codice C.
Allora esiste sempre almeno un vettore polinomiale d’errore e ∈ F± n \ C che produce
un errore catastrofico.
Dimostrazione. Se il codificatore è catastrofico il risultato è ovvio. Senza perdita di generalità assumiamo perciò che G sia un codificatore non catastrofico per il codice C, in modo che GX = Ik . Tutti i vettori in F± n ∩ C, per la
non catastroficità, sono immagini di vettori appartenenti a F± k . D’altra parte essendo X matrice razionale non polinomiale, esisterà sempre un vettore
e ∈ F[z1 , z2 , z1−1 , z2−1 ]n che viene mappato da X in un vettore razionale eX non
polinomiale. Risulta ovviamente che e ∈
/ C. Sia ora u ∈ F± k . Supponiamo che
la sua immagine y = uG, y ∈ F± n sia corrotta dal rumore e. In decodifica si
ha:
(y + e)X = yX + eX = u + eX
In questo modo un errore a supporto finito provoca un errore a supporto infinito in decodifica. D’altra parte se X fosse polinomiale comunque scelto e ∈ F± n ,
eX sarebbe polinomiale e l’errore in decodifca sarebbe a supporto finito.
Nel caso di decodificatore polinomiale si parla di decodifica non catastrofica robusta per distinguerla dal caso in cui in ingresso si hanno solo parole di
codice, caso in cui si parla di decodifica non catastrofica semplice.
Dato un codice C è sempre possibile trovare un decodificatore polinomiale.
Infatti dato un codificatore polinomiale G, che, per la proposizione 2.1, esiste
sempre, si calcoli il corrispondente decodificatore X. Se esso è polinomiale è il
decodificatore cercato altrimenti, se è razionale sarà esprimibile come
e −1
X = Xd
e è una matrice polinomiale. A questo punto il codificatore razionadove X
e come
le Gd−1 è un codificatore di C che ammette la matrice polinomiale X
decodificatore.
e −1 ) = (Gd−1 )X
e = Ik
GX = G(Xd
Differentemente dal caso unidimensionale, può non essere possibile avere contemporaneamente sia un codificatore polinomiale sia un decodificatore
polinomiale. Vale infatti il seguente risultato:
31
Capitolo 2.
CODICI 2D. DEFINIZIONI E PROPRIETÀ
Proposizione 2.6 Dato un codice C esso ammette contemporaneamente codificatori
polinomiali e decodificatori polinomiali se e solo se ogni codificatore polinomiale ℓF P
è anche ℓZP .
Per la dimostrazione si vedano gli articoli di Fornasini e Valcher ([11, prop.
2.1] e [9, prop. 3.1]).
Vediamo ora quale sia la condizione generale su un codificatore G ∈ F(z1 , z2 )k×n
perché esso ammetta un decodificatore polinomiale. Per poter caratterizzare tali codificatori anteponiamo un lemma dovuto a Morf, Lévy e Kung ([22,
Lemma 5.3]).
Lemma 2.7 Siano N ,D,X matrici polinomiali in due indeterminate e sia P =
N D−1 X. Se N e D sono coprime a destra (cioè se N D−1 è una rappresentazione
matriciale fratta coprima), allora P è polinomiale se e solo se D−1 X è polinomiale.
Proposizione 2.8 Sia G ∈ F(z1 , z2 )k×n un codificatore razionale del codice C. Condizione necessaria e sufficiente perché G ammetta un decodificatore polinomiale è che
−1
per ogni rappresentazione matriciale fratta destra coprima G = NR DR
la matrice
numeratore NR sia left zero prime.
Dimostrazione.
Condizione Sufficiente
Se NR è ℓZP essa ammetterà un’inversa destra polinomiale P .
N R P = Ik
Risulta perciò:
−1
−1
N R P = N R DR
D R P = N R DR
(DR P ) = Ik
G(DR P ) = Ik
Ma X = DR P è polinomiale in quanto prodotto di matrici polinomiali: essa è
l’inversa destra cercata.
Condizione Necessaria
32
2.4 Codificatori e decodificatori non catastrofici
Sia X una matrice inversa destra polinomiale di G. Risulta:
−1
GX = NR DR
X = Ik
−1
Per il lemma 2.7 si ha che la matrice P = DR
X è una matrice polinomiale.
N R P = Ik
Poiché la matrice polinomiale NR ha un’inversa polinomiale destra essa deve
essere ℓZP .
Osservazione La condizione va posta sulla rappresentazione matriciale fratta destra. Se infatti si scegliesse di porre la condizione di left zero primeness
sul numeratore delle rappresentazioni matriciali fratte sinistre, tale condizione sarebbe solo sufficiente e non necessaria. Si consideri infatti la seguente
matrice
h
i
x
G = 1 −y
" #
1
. Consideessa banalmente ammette come inversa destra la matrice X =
0
riamo le due rappresentazioni matriciali fratte coprime di G:
#
"
i 1 x −1
G= 1 0
0 y
h i−1 h
i
G= y
y −x
h
La rappresentazione matriciale fratta sinistra ha la matrice numeratore non
ℓZP eppure G possiede un’inversa destra polinomiale. D’altra parte è banale
vedere che se la matrice numeratore di ogni rappresentazione matriciale fratta sinistra di G è ℓZP allora G possiede un’inversa destra polinomiale (basta
prendere infatti X = Y D dove Y è un’inversa destra polinomiale della matrice
numeratore).
Osservazione Nel caso unidimensionale non c’è distinzione tra decodifica non
catastrofica semplice e decodifica non catastrofica robusta in quanto left factor
primeness e left zero primeness sono proprietà equivalenti.
33
Capitolo 2.
2.5
CODICI 2D. DEFINIZIONI E PROPRIETÀ
Codificatori sistematici
Definizione 2.4 Un codificatore G ∈ F1,1 ((z1 , z2 ))k×n si dice sistematico se, a meno
di una permutazione delle colonne, ha come sottomatrice la matrice identità Ik .
Un codificatore sistematico costruisce la parola di codice replicando i k simboli in ingresso e aggiungendo n − k simboli di ridondanza. In questo modo
esso non è mai catastrofico (il decodificatore di un codificatore sistematico ha
la forma I0k ).
Dato un codice C, esso ammette sempre un codificatore sistematico Gs .
Infatti preso un qualsiasi codificatore iniettivo G esso si può partizionare:
h
G = G1 | G2
i
G1 ∈ F(z1 , z2 )k×k
con
G2 ∈ F(z1 , z2 )k×(n−k)
Un codificatore sistematico equivalente si ottiene moltiplicando G per la mak×k
trice quadrata invertibile G−1
1 ∈ F(z1 , z2 )
h
i
−1
Gs = G−1
G
=
I
|
G
G
k
2
1
1
È interessante poi vedere quando si riesca ad ottenere un codificatore sistematico polinomiale. Ovviamente se G è un codificatore polinomiale e G1 è
unimodulare allora G−1
1 sarà polinomiale e Gs risulterà polinomiale. Tale condizione è anche necessaria e per la dimostrazione rinviamo alla dispensa di
Fornasini ([6, prop 7.5.2]).
2.6
Formatori di sindrome
Uno dei passi fondamentali nel processo di decodifica è la verifica se la parola
ricevuta r̂ è una parola di codice o meno. Questa verifica viene effettuata di solito per mezzo della cosiddetta matrice dei check di parità o formatore di sindrome.
Alla parola ricevuta r̂ viene associata la sindrome s ∈ F1,1 ((z1 , z2 ))n−k
s = r̂H
La sindrome è nulla se e solo se r̂ ∈ C.
34
2.6 Formatori di sindrome
Introduciamo nello spazio vettoriale F1,1 ((z1 , z2 ))n il prodotto scalare1
u · v = uvT
Per note proprietà di algebra lineare il sottospazio C ⊂ F1,1 ((z1 , z2 ))n di dimensione k individua univocamente un secondo sottospazio C ⊥ di dimensione
n − k, detto complemento ortogonale2 di C, tale che per ogni coppia (u, v), u ∈ C e
v ∈ C ⊥ si ha u · v = 0. Anche C ⊥ risulta essere un codice secondo la definizione
2.1 e viene denominato codice duale di C.
Tramite il codice duale possiamo dare la definizione di formatore di sindrome.
Definizione 2.5 Dato un codice convoluzionale C, si dice formatore di sindrome
ogni matrice H T dove H è un codificatore del codice duale C ⊥ .
È immediato vedere che per ogni y ∈ C risulta yH T = 0. Essendo H il codificatore di un codice convoluzionale valgono i risultati della proposizione 2.1.
In particolare è sempre possibile trovare un formatore di sindrome polinomiale
indipendentemente dalla struttura del codice C.
1
In realtà, essendo F un campo finito, questo prodotto non soddisfa il terzo assioma del
prodotto scalare (come già accadeva per gli spazi definiti sul campo complesso C). Esistono
cioè vettori u non nulli tali che u · u = 0 (un esempio è il vettore [ 1 1 ] quando F = GF2 ). Per
questo, contrariamente a quanto accade negli spazi vettoriali costruiti su R, dato un sottospazio C, risulta che C ⊥ può non essere un complemento diretto di C, in quanto si potrebbe avere
C ∩ C ⊥ 6= 0. Nell’ambito dei codici, per comodità, tale prodotto viene comunque chiamato
ugualmente prodotto scalare.
2
A causa della definizione non propriamente corretta di prodotto scalare certi autori non
parlano di complemento ortogonale ma di annullatore (annihilator).
35
Capitolo 3
Confronto con le altre teorie dei
Codici 2D
Nel corso del capitolo 2 abbiamo più volte confrontato i risultati che derivavano dalla definizione 2.1 di codice bidimensionale con le altre teorie, specialmente quella di Fornasini-Valcher e quella di Weiner. In questo terzo e ultimo
capitolo ci proponiamo un confronto approfondito tra le tre teorie cercando di
evidenziare pregi e difetti di ognuna.
3.1
Le altre definizioni di codice 2D
Innanzitutto vediamo come sono definiti i codici bidimensionali nell’ambito
delle altre due teorie.
Definizione 3.1 (Fornasini-Valcher) Un codice convoluzionale C è un F± -sottomodulo
di F∞ n completo e controllabile.
Ricordiamo che un insieme si dice completo rispetto a una certa topologia se
ogni successione di Cauchy di elementi dell’insieme converge a un elemento
dell’insieme. La topologia considerata per lo spazio F∞ n è quella indotta dalla
distanza ∆(·, ·)
∆(u, v) =
(
0
se u = v
2− min{d[(i,j),(0,0)]:vij 6=uij } altrimenti
dove d è la distanza tra i punti di Z2 cosı̀ definita:
d[(i, j), (h, k)] = |i − h| + |j − k|
37
Capitolo 3.
CONFRONTO CON LE ALTRE TEORIE DEI CODICI 2D
Una definizione alternativa di completezza che chiarisce perché questa proprietà sia richiesta per i codici è la seguente.
Definizione 3.2 Sia S1 ⊂ S2 ⊂ S3 ⊂ . . . una sequenza di sottoinsiemi di Z2 tale
S
che m∈N Sm = Z2 . Un insieme C ∈ F∞ n si dice completo se per ogni elemento
w ∈ F∞ n , w appartiene a C se e solo se ∀m ∈ N, esiste un elemento vm ∈ C tale che:
w|Sm = vm |Sm
Ogni parola di codice può cioè essere “troncata” in qualsiasi modo ottenendo ancora una parola di codice.
La nozione di controllabilità per i sistemi 2D e per i codici 2D, differisce
dall’usuale concetto presente nella teoria dei sistemi 1D. Se in tale ambito si
parlava di esistenza di un ingresso che annullasse lo stato in un numero finito
di passi, nell’ambito della teoria dei codici 2D la controllabilità è legata alla
possibilità di concatenare due parole di codice ottenendo ancora una parola di
codice.
Definizione 3.3 Un insieme C ∈ F∞ si dice controllabile se per ogni insieme finito
S ⊂ Z×Z e ogni elemento v1 ∈ C, esistono un intero positivo δ e un secondo elemento
v2 ∈ C tali che:
v1 |S = v2 |S
e
supp(v2 ) ⊆ S δ
dove
S δ = (i, j) ∈ Z2 : d [(i, j), S] < δ
Un codice è controllabile, cioè, se per ogni parola di codice ne esiste un’altra
a supporto finito che coincide con la prima su un opportuno insieme di Z2 .
Una definizione alternativa utilizza il concetto di concatenazione. Un codice è
controllabile se per ogni coppia di parole di codice si può costruire una terza
parola di codice formata da porzioni della prima e della seconda purché le
porzioni siano sufficientemente distanti.
Contrariamente alla teoria di Fornasini e Valcher, la teoria di Weiner ricava gran parte dei risultati considerando parole a supporto finito generate da
ingressi a supporto finito. Infatti la sua definizione di codice convoluzionale
bidimensionale è la seguente ([31, def. 2.1.6]):
38
3.1 Le altre definizioni di codice 2D
Definizione 3.4 (Weiner) Un codice convoluzionale C è un F[z1 , z2 ]-sottomodulo
di F[z1 , z2 ]n .
Solo nell’ultima parte della trattazione, nel capitolo dedicato ai codificatori
catastrofici, l’autore considera ingressi e parole di codice a supporto infinito,
aventi comunque supporto contenuto nel primo quadrante di Z2 . Considera
cioè codici definiti nel seguente modo:
Definizione 3.5 (Weiner) Un codice convoluzionale C è un F[z1 , z2 ]-sottomodulo
di F[[z1 , z2 ]]n .
Come si vede la principale differenza tra le due definizioni sta nello spazio
di definizione dei segnali. Entrambe, al contrario della nostra estensione al 2D
della teoria di Forney, sfruttano la teoria dei moduli e in entrambe le teorie
occupano ovviamente un posto di primaria importanza i moduli liberi.
La teoria di Forney 2D occupa un posto intermedio tra le due esistenti in
letteratura, se non altro dal punto di vista delle condizioni che imponiamo
sugli ingressi. Le condizioni che abbiamo dovuto imporre sono molto meno
restrittive di quelle imposte da Weiner ma sono certo più restrittive della totale
assenza di restrizioni che appare nella teoria di Fornasini-Valcher. Se a un
primo sguardo la teoria di Forney 2D sembra porsi a un punto equidistante,
come vedremo essa si avvicina di più ai risultati di Weiner che non a quelli di
Fornasini-Valcher e questo è dovuto alla ricchezza delle strutture algebriche in
cui sono definiti sia i codici 2D alla Forney sia i codici di Weiner.
Prima di confrontare nei particolari le proprietà dei codici andiamo ad esaminare le proprietà richieste nelle definizioni.
Linearità e Invarianza alle traslazioni Entrambe queste proprietà sono richieste da tutte e tre le definizioni. Esse sono incluse nei concetti di sottospazio e
di sottomodulo e sono tra le proprietà fondanti di un codice. Infatti è assolutamente necessario che un codice non cambi le sue proprietà se la codifica
avviene in istanti differenti (in Z2 ). La proprietà di linearità, non fondamentale
quanto l’invarianza (tanto che sono stati pensati codici non lineari), semplifica
tuttavia in maniera decisiva le operazioni di codifica e decodifica.
Completezza Tale proprietà è richiesta solo da Fornasini e Valcher che, subito
dopo averla introdotta, dimostrano anche che sia i nostri codici di Forney 2D
che i codici di Weiner non sono mai completi ([9, Examp. 1 e Examp. 2]. Non
39
Capitolo 3.
CONFRONTO CON LE ALTRE TEORIE DEI CODICI 2D
ci si lasci ingannare dal teorema di Willems ([32, Theor. 5]) che afferma che
un behavior è completo se e solo se ammette una rappresentazione a nucleo.
Infatti i nostri codici di Forney 2D e i codici di Weiner ammettono entrambi
rappresentazioni a nucleo ma all’interno degli spazi in cui sono definiti e non
2
nello spazio generico FZ . Tuttavia visto che la conseguenza più importante
della completezza è il fatto di avere una matrice di parità polinomiale, il fatto
che i nostri codici siano non completi non comporta grandi problemi.
3.2
Confronto tra le proprietà dei codici
Nel confronto tra le proprietà dei codici nelle tre teorie seguiremo l’ordine
utilizzato nel capitolo 2.
3.2.1 Iniettività
Guardando all’iniettività del processo di codifica si trovano le prime importanti differenze tra le tre teorie. Nella nostra estensione alla teoria di Forney,
dato un codice C, è sempre possibile ottenere un codificatore iniettivo per C.
Questo purtroppo non è vero nelle altre due.
Nella teoria di Fornasini-Valcher l’iniettività è legata alla proprietà di Zero
Primeness del codificatore ([9, Prop. 3.1]) e come abbiamo visto nella proposizione 2.6 può non essere possibile ottenere un siffatto codificatore.
Nella teoria di Weiner la condizione perché un codice ammetta codificatori
iniettivi è il codice sia libero e, in tal caso, un codificatore è iniettivo per un
codice di rango k se e solo se il codificatore ha dimensioni k × n.
Questa prima grande differenza porta a notare che in entrambe le teorie
i codici si possono partizionare in due grandi sottoclassi: i codici “utili” che
ammettono un codificatore iniettivo e quindi ammettono a loro volta un decodificatore e i codici che, al contrario, una volta codificata l’informazione non
permettono di riottenerla a partire dalle parole codificate.
3.2.2 Codificatori Equivalenti
Le condizioni per i codificatori equivalenti sono analoghe nelle tre teorie. Considerando solo i codificatori a rango pieno di riga (che nel nostro caso sono
anche codificatori iniettivi) si vede che le proprietà di equivalenza sono legate
40
3.2 Confronto tra le proprietà dei codici
alle condizioni di invertibilità delle matrici utilizzate. Nel nostro caso le matrici invertibili sono tutte le matrici quadrate a rango pieno mentre nelle altre
due teorie, che fanno uso di matrici polinomiali, le uniche matrici invertibili
sono le matrici unimodulari.
3.2.3 Catastroficità
Le tre teorie danno condizioni diverse per la non catastroficità. Se infatti sia
nella nostra estensione della teoria di Forney, sia nella teoria di FornasiniValcher la condizione di non catastroficità semplice richiede che i minori di
ordine massimo non ammettano fattori comuni, nella teoria di Weiner la condizione permette che ci siano fattori comuni non invertibili purché questi abbiano termine noto nullo.
Per capire a fondo tale problematica è necessario capire, dato un codificatore catastrofico, quali siano i vettori a supporto infinito che vengono mappati in
vettori a supporto finito. Tali vettori verrano denominati per comodità vettori
catastrofici.
Proposizione 3.1 Sia G ∈ F[z1 , z2 , z1−1 , z2−1 ]k×n un codificatore iniettivo polinomiale per il codice C. Condizione necessaria perché il vettore y = uG sia polinomiale è
che u sia un vettore razionale.
Dimostrazione. Poiché la trasformazione legata alla matrice G è iniettiva essa
ammetterà una trasformazione inversa legata a una matrice X ∈ F(z1 , z2 )k×n .
GX = Ik
La matrice X sarà in generale razionale (prop. 2.2). Consideriamo ora la relazione y = uG e moltiplichiamo a destra ambo i membri per la matrice X.
Risulta:
u = yX
u è un vettore razionale in quanto risultato di un numero finito di somme
e prodotti di funzioni razionali. D’altra parte la trasformazione è iniettiva e
quindi u è l’unica controimmagine di y.
Osservazione Tale risultato vale banalmente anche per la teoria di FornasiniValcher e, sostituendo l’anello dei polinomi di Laurent con l’anello dei polinomi ordinari, anche per la teoria di Weiner. In particolare, nella teoria di
41
Capitolo 3.
CONFRONTO CON LE ALTRE TEORIE DEI CODICI 2D
Fornasini-Valcher, la matrice X risulterà necessariamente polinomiale in quanto l’iniettività del codificatore equivale alla sua left zero primeness.
È noto che tutti i vettori razionali u ammettono una
u = d−1 v
h RMF coprima
i
dove d ∈ F[z1 , z2 , z1−1 , z2−1 ] è un polinomio e v = v1 . . . vk è un vettore
polinomiale tali che MCD(d, v1 , . . . , vk ) = 1. Tale rappresentazione inoltre è
unica a meno di elementi invertibili nell’anello F[z1 , z2 , z1−1 , z2−1 ].
Proposizione 3.2 Sia G ∈ F[z1 , z2 , z1−1 , z2−1 ]k×n un codificatore polinomiale per il
codice C e u = d−1 v un vettore razionale appartenente a F(z1 , z2 )k . Se y = uG è un
vettore polinomiale, allora d divide tutti i minori k × k della matrice G.
Dimostrazione. Moltiplicando per d entrambi i membri di y = d−1 vG risulta:
dy = vG
Dato che l’anello F[z1 , z2 , z1−1 , z2−1 ] è un dominio a fattorizzazione unica, il risultato segue dal Corollario 3.3.11 di Weiner ([31]).
Allo stesso modo si dimostra a partire dal corollario 3.3.15 di Weiner che
se un polinomio d divide tutti i minori di ordine massimo di un codificatore
G, allora esisterà un vettore catastrofico rappresentabile come u = d−1 v (il
risultato è indipendente dall’ipotesi di iniettività del codificatore).
Osservazione Si noti che il fatto di essere rappresentabile come u = d−1 v
per ogni rappresentazione coprima non è una condizione sufficiente perché
il vettore u sia catastrofico. Si veda banalmente il seguente esempio:
#
"
(z1 + 1)(z2 + 1)
0
z2
G=
0
z2 + 1 1
Risulta:
h
y = uG = z1 + 1 z1
h
i−1 h
i
u = z2 + 1
1 z1
z1 +z2
z2 +1
i
che è evidentemente non polinomiale. D’altra parte si potrebbe pensare che
la condizione necessaria e sufficiente sia il fatto che d divida ogni singolo
elemento di G. Essa è solo sufficiente ma non necessaria. Si veda ad esempio:
#
(z1 + 1)(z2 + 1)
0
z1
G=
0
z2 + 1 −1
"
42
h
i−1 h
i
u = z2 + 1
1 z1
3.2 Confronto tra le proprietà dei codici
Risulta:
h
i
y = uG = z1 + 1 z1 0
che invece è polinomiale senza che z2 + 1 divida tutti gli elementi di G.
Di conseguenza, nella nostra estensione alla teoria di Forney e nella teoria
di Weiner, i vettori catastrofici per un codificatore iniettivo G sono tutti vettori
di serie formali rappresentabili come vettori razionali u = d−1 v, dove d in
ogni rappresentazione coprima di u è il fattore comune dei minori di ordine
massimo di G.
Quando il codificatore non è iniettivo (teoria di Fornasini-Valcher e codificatori non iniettivi per le altre due) la proposizione 3.1 non sarà più verificata
e potranno esistere vettori catastrofici non razionali. Tuttavia per ogni vettore
catastrofico non razionale c ne esisterà uno di razionale r (che per la proposizione 3.2 sarà rappresentabile come r = d−1 v con d fattore comune di tutti i
minori di ordine massimo del codificatore G) tale che:
rG = cG
Grazie a queste osservazioni possiamo ora capire perché spazi di definizione diversi diano origine a condizioni di non catastroficità diverse. Sia d
un fattore comune dei minori di ordine massimo di un codificatore G. Come abbiamo detto in precedenza, esiste sempre un vettore catastrofico avente
rappresentazione fratta coprima u = d−1 v. Le componenti di u saranno funzioni razionali che, a seconda dello spazio di definizione del codice, potranno
ammettere o meno una espansione come serie formale.
Se si opera nello spazio delle serie debolmente causali traslate F1,1 ((z1 , z2 ))
ogni funzione razionale è sempre espandibile in serie e quindi ogni codificatore che non sia ℓM P è catastrofico.
Nello spazio delle serie formali causali F[[z1 , z2 ]], invece, è noto che le funzioni razionali coprime, aventi denominatore con termine noto nullo, non sono
espandibili in serie (si veda il teorema 1.1). Perciò se anche il codificatore ha i
minori con fattore comune un polinomio con termine noto nullo, non esiste un
vettore a elementi in F[[z1 , z2 ]] che rappresenti il vettore razionale catastrofico.
Questo spiega la diversa condizione di non catastroficità di Weiner.
43
Capitolo 3.
CONFRONTO CON LE ALTRE TEORIE DEI CODICI 2D
3.2.4 Formazione della sindrome
Come abbiamo visto nella nostra estensione alla teoria di Forney, dato un codice C, si può sempre costruire la matrice di parità: dato un sottospazio C infatti
è univocamente determinato C ⊥ . Per quanto riguarda la teoria di FornasiniValcher l’esistenza della matrice di parità è richiesta nella definizione di codice.
Infatti per il già citato teorema di Willems ([32, Theor. 5]) la completezza del
behavior equivale all’esistenza di una rappresentazione a nucleo. Per quanto
riguarda infine la teoria di Weiner, egli dimostra che, condizione necessaria e
sufficiente perché un codice C ammetta una rappresentazione a nucleo, è che
ogni sua rappresentazione a immagine sia ℓM P . Nel caso dei codici 2D, se il
codice è libero tale condizione è sempre soddisfatta. Infatti, dato che nel caso
2D factor primeness e minor primeness coincidono e che si può sempre trovare un
codificatore equivalente ℓF P , tale codificatore sarà anche ℓM P .
44
Conclusioni
Come si può notare anche dalla composizione di questa tesi in termini di pagine, la parte più difficoltosa dell’estensione al 2D della teoria di Forney risiede
nella costruzione del campo all’interno di F∞ . Una volta definiti i codici sul
campo da noi costruito, la maggior parte delle proprietà del caso unidimensionale vengono estese banalmente al caso bidimensionale. La nostra attenzione si è soffermata in particolare sul problema della catastroficità dove si
evidenziano le maggiori differenze rispetto al caso 1D.
A conclusione di questa tesi vogliamo indicare qualche problema che resta
aperto nell’ambito della teoria dei codici bidimensionali, e che potrebbe essere
oggetto di future ricerche.
Estensione della teoria di Forney al caso nD L’estensione della teoria di
Forney al caso nD non è ricavabile direttamente dalla nostra estensione al 2D.
Infatti la nostra costruzione del campo per il caso 2D ha richiesto strumenti
propri del caso bidimensionale (coni, serie debolmente causali. . . ) che non
trovano banale riscontro negli spazi a più di due dimensioni. Sicuramente sarà
possibile trovare concetti analoghi una volta fissato il numero di dimensioni:
ciò che sembra più arduo è una generalizzazione al caso n-dimensionale.
Distanza dei codici Tale argomento, di fondamentale importanza per quanto riguarda le applicazioni dei codici, non è stato minimamente toccato in
questa tesi. D’altra parte esso è completamente assente anche nella teoria di
Fornasini-Valcher ed è solamente accennato nella tesi di Weiner. Le soluzioni
al problema nel caso unidimensionale utilizzano tecniche di minimizzazione
sui grafi (simili all’algoritmo di Viterbi) che non hanno riscontro nel caso 2D.
D’altra parte già nel caso unidimensionale tali algoritmi, pur esistendo, hanno interesse pratico praticamente nullo visto che la loro complessità aumenta
esponenzialmente con il numero di elementi di memoria coinvolti.
45
CONCLUSIONI
Realizzazione minima e proprietà di memoria Come accennato nel corso del
capitolo 2, il problema della realizzazione minima nell’ambito dei sistemi bidimensionali è ancora un problema aperto e ben lungi dall’essere risolto. Di
conseguenza non è ancora possibile caratterizzare i codici bidimensionali rispetto al numero di elementi di memoria richiesti come accade, invece, nel
caso unidimensionale. Tuttavia, essendo l’alfabeto del codice un campo finito,
non è da escludere che sia possibile trovare una soluzione al problema nel caso
dei codici senza che sia possibile risolvere il caso generale.
Trasformazioni serie/parallelo e parallelo/serie Tale problematica è legata al
fatto che solitamente i segnali processati dai codici sono segnali scalari. Tutte
le teorie per i codici 2D presenti in letteratura, compresa la nostra estensione della teoria di Forney, invece suppongono di avere in ingresso un segnale
già vettoriale di dimensione k e, dopo la codifica, suppongono di spedire un
segnale vettoriale di n componenti. Resta aperto il problema di come effettuare la trasformazione serie/parallelo e parallelo/serie. Se, infatti, nel caso
unidimensionale, fissati k e n, tale trasformazione è essenzialmente unica (si
vedano gli esempi presenti nell’introduzione), nel caso bidimensionale le possibilità si moltiplicano. Si prenda ad esempio un codice iniettivo con k = 2 e
n = 6. Se la trasformazione in ingresso al codificatore ammette solo due possibilità (campionamento con rapporto 21 lungo z1 oppure lungo z2 ), all’uscita
del codificatore la trasformazione parallelo/serie ammette addirittura quattro
possibilità: 1 × 6, 2 × 3, 3 × 2 e 6 × 1. Dal punto di vista del codice la situazione non cambia ma dal punto di vista della sensibilità al rumore nel canale
la scelta sembra non essere indifferente. Tale argomento però esula dalla teoria classica dei sistemi in quanto necessita di strumenti probabilistici e modelli
probabilistici bidimensionali del rumore.
Applicazioni Il maggiore problema legato ai codici bidimensionali e in generale ai sistemi bidimensionali è legato alle applicazioni pratiche. Se, infatti, tale tipologia di sistemi riveste un importante ruolo dal punto di vista teorico, a
tutt’oggi non si sono trovate applicazioni pratiche se non in qualche caso molto ristretto. L’applicazione più ovvia dei codici convoluzionali bidimensionali
sembrerebbe legata alla codifica dei segnali bidimensionali come le immagini ma negli ultimi tempi si sta facendo strada un loro possibile utilizzo nella
46
CONCLUSIONI
codifica dei segnali unidimensionali grazie a particolari applicazioni legate ai
turbo codes.
47
Appendice A
Richiami di Algebra
Questa appendice non pretende di essere un quadro esauriente dell’algebra
utilizzata in questa tesi. Tuttavia ci sembrava necessario includere le definizioni dei principali elementi utilizzati nel corso della tesi per permettere una
rapida consultazione e aumentare, auspicabilmente, la chiarezza del testo. Al
lettore interessato consigliamo di consultare testi specifici come il ChambedalOvaert ([1]), il Birkhoff-Mac Lane ([19]) o lo Zariski-Samuel ([35]).
A1
Relazioni d’ordine
Definizione A1 Dato un insieme I, una relazione su I che indicheremo con il simbolo ≦ si dice relazione d’ordine (o ordine parziale1 ) se gode delle seguenti proprietà:
1. a ≦ a, ∀a ∈ I
(proprietà riflessiva)
2. (a ≦ b) ∧ (b ≦ c) ⇒ a ≦ c, ∀a, b, c ∈ I
3. (a ≦ b) ∧ (b ≦ a) ⇒ a = b, ∀a, b ∈ I
(proprietà transitiva)
(proprietà antisimmetrica)
Definizione A2 Dato un insieme I e una relazione d’ordine ≦ si dice che l’insieme
è totalmente ordinato se ∀a, b ∈ I è vera una ed una sola delle seguenti affermazioni
(legge di tricotomia)
1. a ≦ b
2. b ≦ a
3. a = b
1
Si veda ad esempio in [19, pag. 71]
49
APPENDICE A. RICHIAMI DI ALGEBRA
Definizione A3 Un insieme totalmente ordinato I si dice bene ordinato se ogni suo
sottoinsieme S 6= ∅ contiene un elemento minimo m, tale cioè che:
∀x ∈ S
m6x
Definizione A4 Un anello R si dice algebricamente ordinato (o anche solo ordinato2 ) se esiste un sottoinsieme non vuoto P ⊂ R, chiamato insieme dei numeri
positivi di R tale che:
1. (a ∈ P ) ∧ (b ∈ P ) ⇒ (a + b ∈ P ) ∧ (a · b ∈ P )
2. ∀a ∈ R vale una ed una sola delle seguenti alternative:
(a) a ∈ P
(b) a = 0
(c) (−a) ∈ P
A2
Strutture Algebriche
Si consideri l’insieme I e le due relazioni binarie chiamate rispettivamente
somma e prodotto:
+:I ×I →I
(a, b) 7→ a + b
·:I ×I →I
(a, b) 7→ a · b
definite per tutte le coppie ordinate del prodotto cartesiano I × I.
Definizione A5 La coppia (I, +) è un gruppo se sono verificate le seguenti proprietà
1. (a + b) + c = a + (b + c)
(associativa)
2. ∃0 ∈ I : a + 0 = 0 + a = a
3. ∀a ∈ I
2
(esistenza dell’elemento neutro)
∃b : a + b = z
(esistenza del simmetrico)
Si veda ad esempio in [19, pag. 178]
50
Moduli e spazi vettoriali
Se inoltre l’operazione somma verifica anche la proprietà
4. a + b = b + a
(commutativa della somma)
si parla di gruppo commutativo o abeliano
Definizione A6 La terna (I, +, ·) è un anello se sono verificate le seguenti proprietà
1. La coppia (I, +) è un gruppo commutativo
2. (a · b) · c = a · (b · c)
(associativa del prodotto)
3. (a + b) · c = a · c + b · c
(distributiva del prodotto rispetto alla somma)
Si parla rispettivamente di anelli commutativi, anelli con unità e anelli di integrità
se, oltre alle proprietà precedenti, sono verificate rispettivamente:
4. a · b = b · a
(commutativa del prodotto)
5. ∃1 ∈ I : a · 1 = 1 · a = a
(esistenza dell’elemento neutro del prodotto)
6. (a · b = 0) ⇒ (a = 0) ∨ (b = 0)
(assenza di divisori di 0)
Definizione A7 La terna (I, +, ·) è un corpo commutativo o campo se I è costituito da almeno due elementi distinti, se sono verificate contemporaneamente le 6
proprietà degli anelli e vale inoltre la seguente proprietà:
7. ∀a ∈ I \ {0}
A3
∃b : a · b = 1
(esistenza del simmetrico rispetto al prodotto)
Moduli e spazi vettoriali
Sia M un insieme non vuoto e sia A un anello commutativo con unità. Si
definiscano le seguenti operazioni chiamate rispettivamente somma e prodotto
per uno scalare
+:M×M→M
(a, b) 7→ a + b
◦:A×M→M
(α, a) 7→ αa
51
APPENDICE A. RICHIAMI DI ALGEBRA
Definizione A8 L’insieme M si dice A-modulo rispetto alle operazioni appena
definite se
1. (M, +) è un gruppo commutativo
2. λ ◦ (a + b) = λ ◦ a + λ ◦ b
(distributiva del prodotto scalare rispetto alla somma)
3. (λ + µ) ◦ a = λ ◦ a + µ ◦ a
4. λ ◦ (µ ◦ a) = (λµ) ◦ a
5. 1 ◦ a = a
(dove 1 è l’elemento neutro del prodotto in A)
Il simbolo della moltiplicazione in A viene omesso come pure viene omesso, ove non vi
siano ambiguità, il simbolo ◦ del prodotto per uno scalare.
Definizione A9 Un sottoinsieme di M chiuso rispetto alle operazioni di somma e di
prodotto per uno scalare viene chiamato sottomodulo.
Definizione A10 Sia M è un A-modulo e B = {b1 , . . . , bn } un suo sottoinsieme
finito. L’insieme hBi di tutte le combinazioni lineari a coefficienti αi ∈ A del tipo:
n
X
αi bi
i=1
è un sottomodulo di M detto sottomodulo generato da B. Se hBi = M, B è un
insieme di generatori del modulo M. M è finitamente generato se ammette un
insieme finito di generatori.
Definizione A11 Gli elementi a1 , . . . , at dell’A-modulo M sono linearmente diP
pendenti se esistono α1 , . . . , αt ∈ A, non tutti nulli tali che ti=1 αi ai = 0. In caso
contrario diciamo che a1 , . . . , at sono linearmente indipendenti. Una famiglia B
di generatori linearmente indipendenti di M è detta base di M ed un modulo che
ammette una base è detto libero.
Definizione A12 Un modulo V definito su un campo K è detto spazio vettoriale
su K o K-spazio vettoriale. Ogni suo sottomodulo è detto sottospazio vettoriale e
ogni suo elemento è detto vettore.
Proposizione A1 Ogni spazio vettoriale ammette una base. Ogni spazio vettoriale
è cioè un K-modulo libero.
Definizione A13 Sia V uno spazio vettoriale finitamente generato. Ogni base di V
ha lo stesso numero n di elementi. Tale numero è detto dimensione di V e si scrive
n = dim(V ).
52
Matrici
A4
Matrici
Dando per noti i concetti di matrice a elementi in un anello R e di determinante
di una matrice, ci soffermiamo su alcuni concetti dell’algebra matriciale per
cui non c’è in letteratura una uniformità nella terminologia e nelle definizioni.
Riportiamo in questa sede le definizioni e la terminologia utilizzata all’interno
della tesi indicando comunque anche le altre possibilità presenti in letteratura.
Definizione A14 Sia M ∈ Rk×n una matrice. Si definiscono minori3 i determinanti
delle sottomatrici quadrate di M . In particolare si dicono minori di ordine massimo
(maximal order minors) i minori delle sottomatrici di M di ordine massimo.
Definizione A15 Una matrice M ∈ Rk×n ha rango4 r e si scrive rank(M ) = r se i
suoi minori di ordine r + 1 sono tutti nulli mentre esiste almeno un minore di ordine
r non nullo. Se r = k, M è detta a rango pieno di riga, mentre se r = n, M è detta
a rango pieno di colonna.
A5
Matrici Polinomiali
Indichiamo con R l’anello dei polinomi a d indeterminate z = (z1 , . . . , zd ) con
coefficienti in un campo F. Per le definizioni seguenti è indifferente che R sia
l’anello dei polinomi ordinari F[z] o l’anello dei polinomi di Laurent F[z, z−1 ].
Definizione A16 Una matrice polinomiale G ∈ Rk×k è singolare se il suo determinante det(G) è il polinomio nullo, cioè il polinomio a coefficienti tutti nulli5 .
Definizione A17 Una matrice polinomiale G ∈ Rk×k è detta unimodulare se è un
elemento invertibile nell’anello Rk×k . Il determinante di una matrice unimodulare è
un elemento invertibile dell’anello R.
Definizione A18 Una matrice polinomiale G ∈ Rk×n si definisce left zero prime
(ℓZP ) se k 6 n e l’ideale IG generato dai minori di ordine massimo di G è l’anello R.
3
Altri autori definiscono minori le sottomatrici quadrate.
Nei testi di algebra lineare si introducono i ranghi per riga rr e i ranghi per colonna rc
definiti come le dimensioni dei sottospazi vettoriali generati rispettivamente dalle righe e dalle
colonne di M . Una volta dimostrato che per ogni matrice si ha rr = rc si definisce rango
r tale quantità. In questa sede si è preferito utilizzare la definizione con i minori potendo
cosı̀ estendere il concetto di rango anche alle matrici con elementi in un anello (le matrici
polinomiali ad esempio).
5
Si ricordi che per polinomi definiti su campi finiti non si ha che una funzione polinomiale
è identicamente nulla solo se i coefficienti sono tutti nulli. Un esempio è il polinomio z 2 + z in
GF2 .
4
53
APPENDICE A. RICHIAMI DI ALGEBRA
Definizione A19 Una matrice polinomiale G ∈ Rk×n si definisce left minor prime
(ℓM P ) se k 6 n e i minori di ordine massimo di G non hanno fattori comuni.
Definizione A20 Una matrice polinomiale G ∈ Rk×n si definisce left factor prime
(ℓF P ) se, per ogni fattorizzazione G = T Ḡ con Ḡ ∈ Rk×n , T è unimodulare.
Per un’analisi approfondita delle condizioni equivalenti ai vari tipi di primalità rinviamo all’articolo di Fornasini-Valcher ([11]).
A6
Matrici Razionali
È immediato accorgersi che il quoziente costruito sull’anello F[z1 , z2 ] dei polinomi ordinari coincide con il quoziente costruito sull’anello F[z1 , z2 , z1−1 , z2−1 ]
dei polinomi di Laurent. Denotiamo tale quoziente come F(z1 , z2 ). Una matrice
M a elementi in F(z1 , z2 ) è detta matrice razionale.
Definizione A21 Ogni matrice razionale M ∈ F(z1 , z2 )k×n si può scrivere per mezzo di matrici polinomiali. Si definisce Rappresentazione Matriciale Fratta (RMF)
−1
destra una rappresentazione del tipo M = NR DR
con NR ∈ F[z1 , z2 ]k×n e DR ∈
F[z1 , z2 ]n×n matrice non singolare. Si definisce Rappresentazione Matriciale Fratta
(RMF) sinistra una rappresentazione del tipo M = DL−1 NL con NL ∈ F[z1 , z2 ]k×n e
DL ∈ F[z1 , z2 ]k×k matrice non singolare.
54
Bibliografia
[1] L. C HAMBADAL E J. L. O VAERT.
Dunod, Paris, 1968.
Algèbre linéaire et algèbre tensorielle.
[2] F. D ELON. “Formal power series.”. Annals of Mathematics and Artificial
Intelligence, 16:59–73, 1996.
[3] R. E ISING. “State-space realization and inversion of 2-D systems”. IEEE
Trans. on Circuits and Systems, CAS-27(7):612–619, 1980.
[4] P. E LIAS. “Coding for noisy channels”. IRE Convention Record, 4:37–46,
1955.
[5] E. F ORNASINI. “A 2D systems approach to river pullution modelling”.
Multidimensional Systems and Signal Processing, 2:233–265, 1991.
[6] E. F ORNASINI. Sistemi Multivariabili.
2003/2004. Università di Padova.
Dispensa per il corso, A. A.
[7] E. F ORNASINI E G. M ARCHESINI. “Algebraic realization theory of twodimensional filters”, in Variable Structure Systems, a cura di R. Mohler e
A. Ruberti, Springer Lect. Notes. in Econ. Math. Sys., n 111, pagg. 64–82.
Springer-Verlag, 1974.
[8] E. F ORNASINI E G. M ARCHESINI.
“State–space realization theory
of two–dimensional filters”. IEEE Transactions on Automatic Control,
AC–21(4):484–492, 1976.
[9] E. F ORNASINI E M. E. VALCHER. “Algebraic aspects of two-dimensional
convolutional codes”. IEEE Transactions on Information Theory, 40(4):1068–
1082, 1994.
55
BIBLIOGRAFIA
[10] E. F ORNASINI E M. E. VALCHER. “On 2D finite support convolutional codes: An algebraic approach”. Multidimensional Systems and Signal
Processing, 5:231–243, 1994.
[11] E. F ORNASINI E M. E. VALCHER. “nD polynomial matrices with applications to multidimensional signal analysis”. Multidimensional Systems and
Signal Processing, 1996.
[12] G. D. F ORNEY, J R. “Convolutional codes I: Algebraic structure”. IEEE
Transactions on Information Theory, 16(5):720–738, 1970.
[13] G. D. F ORNEY, J R. “Structural analysis of convolutional codes via dual
codes”. IEEE Transactions on Information Theory, 19(5):512–518, 1973.
[14] G. D. F ORNEY, J R. “Minimal bases of rational vector spaces with applications to multivariable linear systems”. SIAM Journal on Control,
13(3):493–520, 1975.
[15] R. J OHANNESSON E K. S. Z IGANGIROV. Fundamentals of Convolutional
Coding. IEEE Press, New York, 1999.
[16] B. K ITCHENS. “Multidimensional convolutional codes.”. SIAM J. Discrete
Math., 15(3):367–381, 2002.
[17] S. L IN E D. J. C OSTELLO J R . Error Control Coding: Fundamentals and
Applications. Prentice-Hall, Englewood Cliffs, NJ, 1983.
[18] D. L IND E B. M ARCUS. An Introduction to Symbolic Dynamics and Coding.
Cambridge University Press, 1995.
[19] S. M AC L ANE E G. B IRKHOFF. Algebra. Mursia, Milano, Seconda edizione,
1978. Traduzione Italiana di Pietro Canetta.
[20] B. M ARCUS. “Symbolic dynamics and connections to coding theory, automata theory and system theory”, in Different aspects of coding theory (San
Francisco, CA, 1995), vol. 50, pagg. 95–108. Amer. Math. Soc., Providence,
RI, 1995.
[21] J. L. M ASSEY E M. K. S AIN. “Codes, automata, and continuous systems:
Explicit interconnections”. IEEE Transactions on Automatic Control, AC12(6):644–650, 1967.
56
BIBLIOGRAFIA
[22] M. M ORF, B. C. L EVY E S. Y. K UNG. “New results in 2-D systems theory,
part I: 2-D polynomial matrices, factorization, and coprimeness”. Proc.
IEEE, 65(6):861–872, 1977.
[23] P. P IRET. Convolutional Codes, an Algebraic Approach.
Cambridge, MA, 1988.
MIT Press,
[24] C. R ONCONI. Appunti di Algebra Lineare. Univer Editrice, 1992.
[25] H. H. R OSENBROCK. State Space and Multivariable Theory. Nelson-Wiley,
1970.
[26] J. R OSENTHAL. “Connections between linear systems and convolutional
codes”, in Codes, Systems and Graphical Models, a cura di B. Marcus e J. Rosenthal, IMA Vol. 123, pagg. 39–66. Springer-Verlag, 2001. Disponibile in
rete all’indirizzo: http://www.math.unizh.ch/rosen/preprints.html.
[27] J. R OSENTHAL , J. M. S CHUMACHER E E. V. Y ORK. “On behaviors and
convolutional codes”. IEEE Transactions on Information Theory, 42(6, part
1):1881–1891, 1996. Disponibile in rete all’indirizzo:
http://www.math.unizh.ch/rosen/preprints.html.
[28] C. E. S HANNON. “A mathematical theory of communication”. Bell System
Technical Journal, 27:379–423 (Part I) and 623–656 (Part II), luglio e ottobre
1948.
[29] M. E. VALCHER. Modellistica ed Analisi dei Sistemi 2D con Applicazioni alla
Codifica Convoluzionale. PhD thesis, Università di Padova, 1995.
[30] A. J. V ITERBI. “Error bounds for convolutional codes and an asymptotically optimum algorithm,”. IEEE Transactions on Information Theory,
IT-13:260–269, 1967.
[31] P. A. W EINER. Multidimensional Convolutional Codes. PhD thesis, University of Notre Dame, 1998. Disponibile in rete all’indirizzo:
http://www.math.unizh.ch/rosen/preprints.html.
[32] J. C. W ILLEMS. “From time series to linear system. Part I: Finite dimensional linear time invariant systems”. Automatica, 22:561–580, 1986. Disponibile in rete all’indirizzo:
http://www.esat.kuleuven.ac.be/~jwillems/Publications/Publications.html.
57
BIBLIOGRAFIA
[33] J. C. W ILLEMS. “Models for dynamics”, in Dynamics Reported, a cura di
U. Kirchgraber e H. O. Walther, vol. 2, pagg. 171–269. John Wiley & Sons
Ltd, 1989. Disponibile in rete all’indirizzo:
http://www.esat.kuleuven.ac.be/~jwillems/Publications/Publications.html.
[34] J. C. W ILLEMS. “Paradigms and puzzles in the theory of dynamical systems”. IEEE Trans. Automat. Control, AC-36(3):259–294, 1991. Disponibile
in rete all’indirizzo:
http://www.esat.kuleuven.ac.be/~jwillems/Publications/Publications.html.
[35] O. Z ARISKI E P. S AMUEL. Commutative Algebra.
Mathematics. Springer-Verlag, New York, 1960.
58
Graduate Texts in
Ringraziamenti
La tesi di laurea non è semplicemente il frutto di alcuni mesi di ricerca e di
lavoro. Essa si pone come la conclusione e il coronamento di un iter iniziato
con la scuola dell’obbligo, poi proseguito nelle scuole superiori e infine all’università. Le persone incontrate lungo questo cammino sono state molte e ad
ognuna di esse devo un frammento più o meno grande di questa tesi.
Sicuramente il primo ringraziamento, il più sentito, va alla mia famiglia, a
mamma, papà, Francesco, Luca, Paola, Federico e Stefano. Sono loro che con il loro
aiuto e con il loro sostegno mi hanno permesso di arrivare fino a qui. Sono loro
che hanno condiviso con me successi e insuccessi. Con loro ringrazio anche le
zie, soprattutto la zia Rosetta che ha continuato ad essermi vicina pur vivendo
un periodo difficile.
Un grande ringraziamento va al mio relatore, Mauro Bisiacco. La sua disponibilità in questi mesi è stata stupefacente, soprattutto nei momenti in cui le
mie idee erano confuse e le mie spiegazioni incomprensibili. Insieme a lui voglio ringraziare le due correlatrici, Maria Elena Valcher e Maria Cristina Ronconi
che, senza nessuna “investitura” ufficiale, sono sempre state pronte a prestare
il loro aiuto e a mettere a disposizione la loro competenza. Con tutti e tre mi
scuso per averli costretti a perdere ore a leggere email e pagine e pagine di
dimostrazioni.
Se ho scelto una tesi a prevalente contenuto matematico è perché ho sempre
avuto accanto persone che mi hanno fatto appassionare al mondo dei numeri. Questa tesi esiste solo perché nel mio cammino ho incontrato insegnanti
eccezionali come la mia maestra Rossana Testa, la mia professoressa di matematica delle scuole medie inferiori Laura Chiarelli, i due professori del Liceo
Silvana Pierobon e Lamberto Leoni e la professoressa di Metodi Matematici per
l’Ingegneria Anna Maria Bresquar.
La tesi è anche la conclusione in solitaria di un cammino comune. Si arriva a
questo punto solo con la forza della collaborazione. Voglio perciò ringraziare i
miei compagni di corso, in particolar modo Elena e Mattia con cui ho condiviso,
tra gli altri, il momento forse più difficile dei cinque anni. Il confronto con loro
è stato prezioso e molti dei 28 esami non sarebbero scritti nel mio libretto se
non fosse stato per le ore passate a studiare insieme.
Ringrazio, infine, quanti in questi anni hanno fatto un pezzo di strada con
me, chi da vicino e chi facendo sentire forte la sua presenza anche da molto
lontano. Soprattutto ringrazio chi questi mesi di tesi ha sopperito alla mia
mancanza di tempo, lavorando anche per me: la Commissione Web e il centro
diocesano di AC, i Loop Kattiv, Martina e tutto il gruppo giovanissimi, Elena, Chiara
e tutto il Coretto.
Un ultimo ringraziamento va ai bibliotecari del DEI che cercando tra gli archivi hanno trovato le decine di articoli che sono serviti per la tesi: auguro loro
che al più presto l’IEEE si decida a trasferire tutto il materiale su supporto digitale in modo da non dover più lottare con centinaia di volumi dalle rilegature
cadenti.