CODICI LINEARI
2.3 Alcuni esercizi
2.3 Alcuni esercizi
2.3.1 Codici autoduali
Esercizio 2.26. Dimostrare che il codice di Hamming (8, 4, 4) è autoduale.
Il codice è autoduale se DimC è pari alla metà della lunghezza del codice (qui questa condizione è soddisfatta). La seconda condizione per l’esistenza di codici autoduali è l’esistenza di sottospazi costituiti da vettori isotropi, ovvero vettori (v1, . . . , vn) tali che la somma delle componenti al quadrato sia nulla. Nel caso in cui CarF = 2,
(a + b)2= a2+ b2+ 2ab = a2+ b2
ovvero in un campo di caratteristica 2, a2+b2= 0 equivale ad (a+b)2= 0. Quindi, se il campo ha q elementi e C = Fn i vettori isotropi sono qn−1 (è l’iperpiano ottenuto considerando il duale, perché è dato dagli elementi del codice che elevati al quadrato danno 0).
Una volta fatta l’ipotesi sulla dimensione, per verificare se un codice è autoduale basta verificare che ωi· ωj = 0 per ogni ωi, ωj vettori della base. Questo implica che dati vettori qualsiasi v, w ∈ C, essi sono combinazioni lineari degli elementi della base, in particolare
v =X i ciωi, w =X j cjωj quindi v · w = (X i ciωi) · (X j cjωj) =X i,j ciciωi· ωj
e se tutti i prodotti scalari sono nulli anche v · w = 0. Qui DimC = DimC⊥ = 4, quindi mostrando l’ortogonalità tra i vettori della base segue subito che i due spazi sono uguali.
Osservo che le colonne di ˆH, dette ht 1, . . . , ht
4 costituiscono una base per il codice duale, esse infatti sono linearmente indipendenti perché il rango di ˆH è 4, inoltre stanno nel duale
perché cihit= 0∀i. Basta mostrare che il duale di ˆC è autoduale, ovvero (C⊥)⊥= C.
h1= (1, 1, 1, 1, 0, 0, 0, 0)
h2= (0, 1, 1, 0, 0, 1, 1, 0)
h3= (1, 0, 1, 0, 1, 0, 1, 0)
h4= (1, 1, 1, 1, 1, 1, 1, 1)
Il peso dei vettori di questa base è congruo a 0 modulo 4. Allora h2
i = 0∀i. Inoltre per ogni i,
hi· h4≡ 0 mod 2 (infatti è dato dalla somma delle componenti di hipoiché sto moltiplicando per un vettore che ha tutte le entrate uguali a 1) Negli altri casi si svolgono i calcoli:
h1· h2= 2 ≡ 0 mod 2
h1· h3= 2 ≡ 0 mod 2
h2· h3= 2 ≡ 0 e quindi il codice è autoduale.
Osservazione 2.27. Considero C = Rep2(F2), allora DimC = 1 = n/2. La base di questo codice è costituita solo da (1, 1), che ha prodotto scalare nullo con sé stesso, quindi il codice è autoduale.
Su F = F2, si distinguono due famiglie di codici autoduali: (i) si richiede che wH(c) ≡ 0 mod 4∀c ∈ C.
(ii) si richiede che wH(c) ∼= 1 mod 4∀c ∈ C
Esercizio 2.28. Dimostrare che se C è un codice autoduale definito su F2, allora ogni elemento del codice ha peso di Hamming pari.
Dimostrazione. Dato c = (γ1, . . . , γn), segue che
c · c =X
i
γi2= |{i : γi= 1}| = wH(c) ≡ 0 mod 2 per la dualità, quindi wH(c) dev’essere pari.
Un codice appartenente alla prima famiglia è il cosidetto codice di Golay (ha lunghezza 23 e dimensione 12). Il conteggio del numero di parole di un dato peso nei codici autoduali della prima famiglia è univocamente determinato dall’informazione sul codice di Golay e sul codice di Hamming esteso.
Esercizio 2.29. Dimostrare che il codice di Hamming ternario (definito su F3) è autoduale.
Dimostrazione. H = 0 1 1 0 1 1 1 2
Mostriamo che C = ker H è autoduale. Le colonne della matrice sono date da:
h1= (0, 1, 1, 1)
h2= (1, 0, 1, 2)
h1· h1= 3 ≡ 0 ∈ F3
h1· h2= 0
h2· h2= 1 + 1 + 4 = 6 ≡ 0 mod 3
Questo è un m.d.s. codice, ovvero k + d = n + 1, infatti 2 + 3 = 4 + 1. La lunghezza di m.d.s. codici dev’essere uguale a q + 1 se q è dispari e a q + 2 se q è pari (qui 4 = 3 + 1 quindi questo codice m.d.s. è massimale).
Esercizio 2.30. Mostrare che ogni matrice generatrice per un codice C di parametri (4, 2, 3)
2.3. ALCUNI ESERCIZI 37
Dimostrazione. Poiché il codice è autoduale, la matrice H considerata prima coincide con la
sua matrice generatrice (trasposta), quindi
G =
0 1 1 0 1 1 1 2 Distinguo due casi: ci sono sottomatrici della forma:
0 1 1 ν
!
che hanno determinante −1, quindi non sono singolari. Altre sottomatrici sono della forma 1 ν
1 µ
!
con determinante µ − ν 6= 0.
Proviamo ora che l’assenza di sottomatrici singolari non dipende dalla particolare
scelta della matrice, ma è verificata per una qualsiasi matrice generatrice ¯G. Se ¯G
è un’altra matrice generatrice, essa si ottiene a partire da G attraverso la moltiplicazione per una matrice invertibile, quindi esiste una matrice P invertibile tale che ¯G = P G. Se chiamo
¯
Gi l’i-esima colonna di ¯G, si ha ¯Gi= P Gi. In particolare le sottomatrici 2 × 2 di ¯G sono della
forma:
¯
Gi G¯j = P Gi Gj
ma poiché la matrice di colonne (Gi, Gj) è non singolare per i conti precedenti, e P è non singolare, anche il determinante della matrice al primo membro è diverso da 0 per il teorema di Binet.
2.3.2 Information set
Definizione 2.31. Sia C un codice lineare di lunghezza n su un campo F e di dimensione k,
e sia G una matrice generatrice. Un sottoinsieme S di {1, . . . , n} viene detto information set se ha esattamente k elementi e se il determinante della sottomatrice data dalle colonne di G corrispondenti agli indici di S è non singolare.
E’ possibile ottenere m in Fk a partire dalla scelta delle componenti del vettore codificato se e solo se S è un information set.
Osservazione 2.32. L’ordine di S non può essere inferiore a k, altrimenti non sarebbe
possibile avere una mappa suriettiva da F|S|→ Fk. Allora la cardinalità minima è k. Considero G che abbia due blocchi, il primo di dimensione k × k che chiamo A e il secondo di dimensione k × (n − k). La corrispondenza m 7→ mA è invertibile se e solo se A è non singolare. Se chiamo c1, c2 le porzioni della parola codificata corrispondenti rispettivamente alle prime k e alle ultime n − k componenti di c, riesco a risalire a m moltiplicando c1 per
Dall’esercizio precedente segue che per il codice (4,2,3) di Hamming su F3ogni sottoinsieme di {1, . . . , 4} di cardinalità 2 è un information set.
Dato un codice (4,2,3), si possono ottenere altri codici (4,2,3) permutando le colonne della sua matrice.
Si può mostrare anche che gli information sets di un dato codice non dipendono dalla scelta di una sua matrice generatrice. Infatti abbiamo mostrato che dato un information set relativo a G, la sottomatrice estratta da ¯G è non singolare.
2.3.3 Struttura del gruppo monomiale
Esercizio 2.33. Dimostrare che il gruppo GL(2, F2) è isomorfo al gruppo simmetrico su 3 elementi, e determinare i sottogruppo monomiale e di permutazione.
Dimostrazione. Il sottogruppo monomiale è l’insieme di tutte le matrici che si ottengono
moltiplicando una matrice diagonale invertibile per una matrice di permutazione, mentre il sottogruppo di permutazione è l’insieme delle matrici di permutazione.
GL(2, F2) = { a b
c d t.c. ad − bc 6= 0, a, b, c, d ∈ F2}. Allora GL(2, F2) è in corrispondenza biunivoca con l’insieme delle radici in F4
2 dell’equazione polinomiale xy − zw = 1, che è a coefficienti in F2(varietà algebrica affine).
(i) Caso 1: a = 0 implica bc = 1, ovvero b = c = 1, e si ottengono le due matrici 0 1 1 0 ! 0 1 1 1 !
(ii) Caso 2: se a = 1, d = 1 + bc, e ci sono quattro matrici possibili (corrispondono ai possibili modi in cui si può scegliere la coppia (b, c)):
1 0 0 1 ! 1 0 1 1 ! 1 1 0 1 ! 1 1 1 0 !