Parole di peso piccolo dei codici Hermitiani

Richiami
Indichiamo con Fq un campo finito con q elementi, dove q è una potenza di un
numero primo p, e consideriamo le seguenti definizioni:
Definizione 2.0.1. La norma è una funzione N : Fqm → Fq tale che
N(x) = x1+q+···+qm−1
Definizione 2.0.2. La traccia è una funzione Tr : Fqm → Fq tale che
Tr(x) = x + xq + · · ·+ xqm−1
In questa trattazione si studia solamente il caso in cui m = 2 quindi:
N(x) = x1+q Tr(x) = x + xq
Quello che interessa per i codici Hermitiani è capire qual'è la controimmagine delle
due funzioni, cioè capire quante soluzioni ha il seguente sistema:
{
N(x) = x1+q = λ
Tr(x) = x + xq = λ con λ ∈ Fq.
Una volta studiato questo sistema sapremo dire quanti sono i punti che stanno nel-
l'intersezione della curva Hermitiana χ e le rette verticali e oblique.
Tale argomento è stato in parte tratto dal testo [Pel].
Alla fine di questo capitolo saranno trattati di codici lineari.
2.1 Algebra lineare
Teorema 2.1.1. Siano V,W spazi vettoriali e sia f : V → W funzione lineare allora:
dim(Ker(f)) + dim(Im(f)) = dimV
Teorema 2.1.2. Siano V,W spazi vettoriali e sia f : V → W funzione lineare allora:
f−1(a) = b + Ker(f)
dove f(b) = a
1
Capitolo 2. Richiami
Teorema 2.1.3 (Divisione con resto fra interi). Dati due numeri interi a, b con b > 0,
esistono unici due numeri q, r ∈ Z tali che
a = bq + r
0 ≤ r < b.
2.2 La Norma
Sia α elemento primitivo di Fq2\{0} cioè F∗q2 = {α, . . . , αq
2−1}
Lemma 2.2.1. Se α genera F∗q2 allora αq+1 genera F∗q.
Dimostrazione. Basta mostrare che (αq+1)r ∈ F∗q con 1 ≤ r ≤ q − 1 e che sono tutte
distinte.
αq+1
α2q+2
.
.
.
αq2−1
Sono esattamente q − 1 elementi distinti.
Sono tutti diversi tra loro perchè 〈α〉 = F∗q2
e quindi αj ∈ F∗q2
Ovviamente αq+1 ∈ F∗q, infatti se a ∈ F∗q cioè aq−1 = 1. Quindi, poichè α ∈ F∗q2 , si
ha che
(αq+1)q−1 = αq2−1 = 1
Grazie al lemma appena dimostrato, possiamo prendere λ = (αq+1)r con 1 ≤
r ≤ q − 1 fissato. Si ha, quindi, che la N(x) = xq+1 = λ = (αq+1)r cioè x =
αr è una soluzione. Cerchiamo, ora, se esiste, un'altra soluzione del tipo x = αs:
xαβ = αrαβ = αr+β
Ma se αr+β è una soluzione, allora deve verificare xq+1 = λ = (αq+1)r, quindi si ha
che
(αr)q+1 = xq+1 = (αr+β)q+1 ⇐⇒ (αβ)q+1 = 1 = αq2−1
⇐⇒ β(q + 1) ≡ 0 mod q2 − 1
⇐⇒ β(q + 1) = i(q2 − 1) = i(q + 1)(q − 1)
⇐⇒ β = i(q − 1)
Perciò
x = αr+i(q−1) con 0 ≤ i ≤ q.
Cioè ci sono esattamente q + 1 soluzioni dell'equazione N(x) = λ.
2
2.3. La Traccia
La controimmagine della norma
N : Fq2 → Fq
x 7→ xq+1
• N(x) = 0 ⇒ |Im(N−1(x))| = 1
• N(x) 6= 0 ⇒ |Im(N−1(x))| = (q − 1)(q + 1) = q2 − 1
In quanto (q − 1) sono i possibili elementi del campo e (q + 1) sono tutte le
possibili soluzioni.
2.3 La Traccia
Tr : Fq2 → Fq
x 7→ x + xq
Notiamo che la traccia è una funzione lineare infatti:
• Tr(0) = 0
• Tr(a + b) = (a + b) + (a + b)q = a + aq + b + bq = Tr(a) + Tr(b)
Quindi possiamo identificare Fq2 con (Fq)2.
Vediamo ora quante soluzioni ha la seguente equazione: Tr(x) = λ.
- Se y = 0 allora Tr(y) = 0
- Studiamo, quindi, il caso in cui y 6= 0 cioè y ∈ F∗q2 = 〈α〉.
In questo caso z = yq − y ∈ F∗q2 . Infatti
zq
2 = (yq − y)q2 = (yq2)q − yq2 = yq − y = z
Inoltre se si prende z di questo tipo:
z = yq − y ⇒ Tr(z) = 0
Infatti
Tr(z) = z + zq = (yq − y) + (yq − y)q =6 yq − y + yq2− 6 yq = −y + y = 0
Questo vuol dire che z 6= 0 appartiene al Ker(Tr) = {x ∈ Fq2 | Tr(x) = 0} e
cioè che Ker(Tr) 6= {0}.
3
Capitolo 2. Richiami
In questo caso, quindi, la dimensione del Ker(Tr) può essere solamente 1 op-
pure 2, cioè il Ker(Tr) o è tutto Fq oppure1 Ker(Tr) ≡ Fq2 . Ma poichè la
traccia è una funzione lineare, possiamo utilizzare il Teorema 2.1.1. Dunque la
dimensione dell'immagine della traccia
dim(Im(Tr)) = dim({x ∈ Fq | ∃ y ∈ F∗q2 , T r(y) = x})
può essere solamente 0 oppure 1.
Facciamo vedere che dim(Im(Tr)) = 1.
Tr(αq+1) = αq+1 + (αq+1)q = αq+1 + αq2+q = 2αq+1 ∈ F∗q
Perciò
Im(Tr) 6= {0} ⇐⇒ dim(Im(Tr)) = 1 ⇐⇒ dim(Ker(Tr)) = 1
Ker(Tr) ≡ Fq ⇐⇒ V({xq + x = 0}) = |Ker(Tr)| = |Fq| = q
Questo vuol dire che l'equazione yq + y = 0 ha esattamente q soluzioni.
Dal Teorema 2.1.2 si può dedurre che ∀λ ∈ F∗q (che sono q − 1) abbiamo esat-
tamente q soluzioni dell'equazione yq + y = λ.
La controimmagine della traccia
Tr : Fq2 → Fq
y 7→ y + yq
• Tr(y) = 0 ⇒ |Im(Tr−1(y))| = q
• Tr(y) 6= 0 ⇒ |Im(Tr−1(y))| = (q − 1)q = q2 − q
In quanto (q − 1) sono i possibili elementi del campo e q sono tutte le possibili
soluzioni.
2.4 La curva Hermitiana
Definizione 2.4.1. Sia f un polinomio in due variabili a coefficienti in Fq. Si può
definire una curva Cf in Fq[x, y] come
Cf = {(x, y) ∈ (Fq)2 | f(x, y) = 0}
Consideriamo la curva Hermitina χ : xq+1 = yq + y cioè la curva χ : Fq2 → Fq tali
che presi x, y ∈ Fq2 si ha che
N(x) = Tr(y)
1Chiaramente dimFq (Fq2) = 2
4
2.4. La curva Hermitiana
Intersezione di χ con le rette verticali
Siano x, y ∈ Fq2
{
xq+1 = yq + y
x = k
Bisogna quindi risolvere
t = kq+1 = yq + y
Abbiamo appena visto che per t fis-
sato (possiamo prendere q2 valori
distinti di t perchè x ∈ Fq2) si han-
no esattamente q soluzioni. Perciò le
rette verticali intersecano la curva χ
in
q2 · q = q3 punti
Intersezione di χ con le rette oblique
Siano x, y ∈ Fq2
{
xq+1 = yq + y
y = ax + b
Risolvendo il sistema si ha che
(ax + b)q + (ax + b) = xq+1
m
aqxq + bq + ax + b = xq+1 (2.1)
5
Capitolo 2. Richiami
Consideriamo due casi distinti a seconda del valore di aq+1 + bq + b per a, b ∈ Fq2 .
aq+1 + bq + b = 0 (2.2)
In questo caso bq + b = −aq+1 sostituendo quest'uguaglianza all'equazione (2.1)
si ottiene
aqxq − aq+1 + ax = xq+1 ⇐⇒ xq(x− aq) = a(x− aq)
⇐⇒ (xq − a)(x− aq) = 0
⇐⇒ (xq − aq2)(x− aq) = 0
⇐⇒ (x− aq)q(x− aq) = 0
⇐⇒ (x− aq)q+1 = 0
⇐⇒ x = aq
Quindi si ha un unico punto, cioè tutte le x sono uguali. Questo è un caso
degenere perchè ricadiamo nel caso delle rette verticali.
Vediamo, ora, quante coppie (a, b) ∈ (Fq2)2 verificano la condizioni (2.2). Per il
Lemma 2.2.1 si ha che
∀ a ∈ Fq2 ⇒ −aq+1 ∈ Fq
Quindi per quello che abbiamo appena visto si ha che Tr(b) = bq + b = −aq+1
ha esattamente q soluzioni. Cioè ci sono esattamente q · q2 = q3 coppie di punti
che verificano l'equazione (2.2).
aq+1 + bq + b = c 6= 0 (2.3)
In questo caso sostituendo l'uguaglianza (2.3) all'equazione (2.1) si ottiene
xq+1 − aqxq + aq+1 − ax = c ⇐⇒ xq(x− aq)− a(x− aq) = c
⇐⇒ (xq − a)(x− aq) = c
⇐⇒ (xq − aq2)(x− aq) = c
⇐⇒ (x− aq)q(x− aq) = c
⇐⇒ (x− aq)q+1 = c
Poichè c ∈ Fq e Fq2 = 〈α〉 allora per il Lemma 2.2.1 possiamo prendere
c = (αq+1)r con 1 ≤ r ≤ q − 1 fissato.
Si ha, quindi, che (x− aq)q+1 = c = (αq+1)r cioè x = aq + αr è una soluzione.
Cerchiamo, ora, se esiste, un'altra soluzione del tipo x = aq + αs:
(x− aq)αs = αrαs = αr+s
6
2.4. La curva Hermitiana
Ma se αr+s è una soluzione, allora deve verificare (x − aq)q+1 = c = (αq+1)r,
quindi si ha che
(αr)q+1 = (x− aq)q+1 = (αr+s)1+q ⇐⇒ (αs)1+q = 1 = αq2−1
⇐⇒ s(q + 1) ≡ 0 mod q2 − 1
⇐⇒ s(q + 1) = i(q2 − 1) = i(q + 1)(q − 1)
⇐⇒ s = i(q − 1)
Perciò
x = aq + αr+i(q−1) con 0 ≤ i ≤ q
Cioè ci sono esattamente q + 1 punti di intersezione tra χ e la rette oblique.
Vediamo, ora, quante coppie (a, b) ∈ (Fq2)2 verificano la condizioni (2.3). Sono
tutti i punti (a, b) ∈ (Fq2)2 che non verificano la condizioni (2.2) cioè:
q2 · q2 − q3 = q4 − q3
In quanto abbiamo q2 possibili valori per a poichè è un elemento di Fq2 e q2
possibili valori per b.
Se si scelgono w punti dell'intersezione tra la curva χ e tutte le possibili
rette si ha che il numero di configurazioni possibili è:
q2
(
q
w
)
+ (q4 − q3)
(
q + 1
w
)
In quanto:
q2
(
q
w
)
sono le rette verticali in quanto abbiamo
- q2 modi per scegliere x
- per ogni x ci sono q possibili y. Ma di questi q ce ne bastano solamente w.
(q4 − q3)
(
q + 1
w
)
sono le rette oblique/orizzontali in quanto abbiamo
- (q4 − q3) modi per scegliere i coefficienti della retta in modo da non ottenerla
verticale
- q + 1 punti per ogni retta. Ma di questi punti ce ne bastano solamente w.
7
Capitolo 2. Richiami
2.5 Codici Lineari
Sia Fq un campo finito con q elementi e siano k, n due interi tali che k ≤ n. Se C
un sottospazio vettoriale di (Fq)n di dimensione k, allora C è detto codice lineare di
dimensione k e lunghezza n. Gli elementi di C sono chiamati parole.
Consideriamo v, w elementi di (Fq)n, cioè v = (v1, . . . , vn) e w = (w1, . . . , wn). Allora
definiamo la distanza di Hamming tra i due vettori v, w come
d(v, w) := |{i | vi 6= wi}|
Mentre il peso di Hamming del vettore v è definito come il numero di coordinate di
v diverse da 0, cioè w(v) = d(0, v). La distanza del codice C è, invece,
d(C) = min
c,c∈C c 6=c
d(c, c)
Un codice [n,k,d] è un codice di lunghezza n, dimensione k e distanza d. Inoltre
se q = 2 si dice codice binario.
Proposizione 2.5.1. Sia C un codice lineare [n,k,d] allora
d(C) = min
c∈C
w(c)
Definizione 2.5.2. Sia C un codice [n,k,d], indichiamo con Ai il numero di parole
di peso i. L'insieme {Ai} è chiamata distribuzione dei pesi di C.
Una distribuzione dei pesi si dice simmetrica se
Ai = An−i per 0 ≤ i ≤ [
n− 1
2
]
Definizione 2.5.3. Sia C un codice [n,k,d] generato da g1, . . . , gk ∈ (Fq)n.
La matrice G, k× n a coefficienti in Fq formata dai suoi generatori è detta matrice
generatrice del codice.
Se C è un codice [n,k,d], allora il suo duale è l'insieme dei vettori di dimensione n
che sono ortogonali a tutte le parole del codice.
C⊥ = {v ∈ (Fq)n tc c · v = 0 ∀ c ∈ C}
La matrice che genera C⊥ è detta matrice di controllo di parita H.
8