Dati due codici additivi C ⊂ GF (4)n e C0 ⊂ GF (4)n0
de niamo la loro somma diretta come
C ⊕ C0 = {uv : u ∈ C, v ∈ C0} ⊂ GF (4)n+n0,
dove con uv indichiamo il vettore (u, v) ∈ GF (4)n+n0.
In questo modo possiamo formare la somma diretta di due codici correttori quantistici, combinando i codici [[n, k, d]] e [[n0, k0, d0]]
per produrre un codice [[n + n0, k + k0, d00]], dove d00 = min {d, d0} .
Un codice additivo che è somma diretta di due codici additivi è detto decomponibile.
Teorema 5.5
Sia C un codice quantistico [[n, k, d]] :
1. Se k > 0 allora esiste un codice quantistico [[n + 1, k, d]]; 2. Se C è un codice puro e n ≥ 2 allora esiste un codice quantistico
[[n − 1, k + 1, d − 1]];
3. Se C è un codice puro e se k > 1 o se k = 1, allora esiste un
codice quantistico [[n, k − 1, d]];
4. Se n ≥ 2 allora esiste un codice quantistico [[n − 1, k, d − 1]]; 5. Se n ≥ 2 e il codice associato contiene un vettore di peso 1
allora esiste un codice quantistico [[n − 1, k, d]] . Per la dimostrazione vedere [7].
Se abbiamo altre informazioni sul codice C è possibile utilizzare una tecnica, più potente di quella esposta nel teorema 5.5, per accorciare il codice.
Vediamo qualche risultato.
Lemma 5.6
Sia C un codice lineare auto-ortogonale su GF (4). Supponiamo che S sia un insieme di coordinate di C tale che ogni parola del codice incontra S in un vettore di peso pari. Allora il codice ottenuto da C eliminando le coordinate di S è anche auto-ortogonale.
Teorema 5.7
Supponiamo di avere un codice quantistico lineare [[n, k, d]] asso- ciato ad un codice additivo C, n, 2n−k . Allora esiste, per ogni m,
un codice quantistico lineare [[n − m, k0, d0]], con k0 ≥ k e d0 ≥ d,
per ogni m tale che esiste una parola di peso m nel duale del codice binario generato dai supporti delle parole di C.
Dim.
Se S è il supporto della parola di peso m, allora S soddisfa le con- dizioni del lemma precedente e quindi eliminando queste coordinate si ottiene il codice desiderato.
@
Teorema 5.8
Dati due codici [[n1, k1, d1]] e [[n2, k2, d2]] , con k2 ≤ n1, possiamo
costruire un codice [[n1+ n2− k2, k1, d]], dove
d ≥ min {d1, d1+ d2− k2} .
Dim.
Consideriamo i codici additivi associati C1, C1⊥di parametri n1, 2n1−k1 ,
n1, 2n1+k1
e C2, C2⊥ di parametri n2, 2n2−k2 , n2, 2n2+k2
.
Sia ρ la composizione della mappa naturale da C2 a C2⊥/C2 con qual-
siasi prodotto interno che preserva la mappa da C⊥
2 /C2 in GF (4)k2.
Allora formiamo un nuovo codice C =uv : v ∈ C⊥
con
C⊥ =uv : v ∈ C2⊥, uρ (v) ∈ C1⊥ .
Se ρ (v) 6= 0, v contribuisce con almeno d2 al peso di dv, e u ha peso
uguale ad almeno d1− k2.
Se ρ (v) = 0, e uv 6= 0, wt (u) ≥ d1.
@
Diverse scelte di ρ possono produrre codici inequivalenti. In base alla scelta di ρ abbiamo un metodo di codi ca per C2.
Ad esempio, se il secondo codice è [[1, 0, 1]] un codice con matrice generatrice [1] , il nuovo codice ha parametri [[n1+ 1, k1, d1]] ,come
nel Teorema 5.5.
Un altro codice [[n1+ 1, k, d1]] è quello ottenuto se prendiamo il
secondo codice [[2, 1, 1]] con matrice generatrice 1 1 .
In particolare, il secondo codice [[6, 1, 3]] può essere ottenuto in questo modo.
Il Teorema 5.8, può essere utilizzato per produrre un analogo dei codici concatenati1 nell'impostazione quantistica.
Se Q1 è un codice quantistico [[nm, k]], con codice lineare associato
nm, 2nm+k e Q2 è un codice quantistico [[n2, m, d2]], la codi ca
di ciascun blocco di Q1 mediante Q2 produce un codice concatenato
[[nn2, k, dd2]].
1I codici concatenati sono stati introdotti da David Forney nel 1966. In questo tipo di codici
vengono realizzate due codi che, l'una dentro l'altra. Questo metodo consente la realizzazione di codici con elevata capacità di correzione degli errori ed una complessità non eccessiva.
Esempio:
Un esempio particolarmente interessante è ottenuto concatenando il codice di Hamming [[5, 1, 3]] con se stesso.
Prendiamo Q1 = Q2,e sia C, (5, 24) ,il codice lineare associato alla
matrice generatrice
0 1 1 1 1 1 0 1 ω ω
.
Allora otteniamo un codice [[25, 1, 9]] al quale sono associati i codici lineari (25, 224)e (25, 226)che hanno la seguente matrice generatrice
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ω ω¯ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ω ω¯ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ω ω¯ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ω ω¯ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ω ω¯ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ω¯ ω 0 0 1 ω¯ ω 0 0 1 ω¯ ω 0 0 1 ω¯ ω 0 0 1 ω¯ ω 0 0 0 0 0 0 0 1 ω¯ ω 0 0 ω 1 ω¯ 0 0 ω¯ ω 1 0 0 0 0 0 0 0 0 0 0 0 0 1 ω¯ ω 0 0 ω¯ ω 1 0 0 ω 1 ω¯
Sebbene il codice di Hamming sia puro, il codice concatenato non lo è.
@
Un'altra costruzione basata su codici binari può essere generalizzata come segue:
Teorema 5.9 (di Gottesmann)
Sia Sm il classico codice simplesso binario di lunghezza n = 2m− 1,
di dimensione m e di distanza minima 2m − 1. Sia f un automor-
smo, senza punti ssi di Sm e sia Cm il codice additivo (2m, 2m+2)
generato dai vettori u + ωf (u) , u ∈ Sm, con 0 aggiunto, insieme ai
vettori 11 . . . 1, ωω . . . ω di lunghezza 2m.Questo produce un codice
quantistico [[2m, 2m− m − 2, 3]].
Il codice Cm ha le seguenti proprietà:
1. Per ogni scelta f, Cm ha polinomio enumeratore di pesi
x2m+ 4 (2m− 1) x2m−2
y3.2m−2+ 3y2m.
2. I vettori di peso 2m generano un sottocodice di dimensione 2.
3. Supponiamo che Cm sia costruito utilizzando l'automor smo f, e
C0
m utilizzando f0. Allora Cm0 è equivalente a Cm se e solo se f0
è coniugato rispetto ad Aut (Sm) a uno dei
{f, 1 − f, 1/f, 1 − 1/f, 1/ (1 − f ) , f / (1 − f )} . 4. Cm è lineare se f soddisfa f2 + f + 1 = 0.
Notiamo che Aut (Sm) è isomorfo al gruppo lineare GLm(2), e le
classi di coniugio di GLm(2) sono determinate dai loro divisori
elementari.
Quindi il modo più conveniente per speci care f è elencando i suoi divisori elementari.
Per m = 3 c'è un'unica scelta per f, con divisore l'elementare x3 +
x + 1, e quindi esiste un unico C3 di parametri [[8, 3, 3]].
Per m = 4 ci sono tre codici distinti C4, di parametri [[16, 10, 3]]. I
corrispondenti divisori elementari di f sono:
x2+ x + 1 (due volte).
(x2+ x + 1)2.
x4+ x + 1.
Per m = 5 ci sono due codici distinti C5,con parametri [[32, 25, 3]].
x3+ x + 1 e x2+ x + 1.
x5+ x2+ 1.
Utilizzando il teorema Gottesmann su un singolo f, otteniamo, se m è pari, la matrice 0 1 0 0 . . . 0 0 0 1 0 . . . 0 . . . . 0 0 0 0 . . . 1 1 1 1 1 . . . 1 ,
mentre, se m è dispari, la stessa matrice con la prima riga sostituita dal suo completamento a 2.
I codici costruiti nel Teorema 5.9 sono puri e additivi ma, in generale, non sono lineari.
Per m pari si ottengono i codici di Hamming.
Per m dispari otteniamo i codici [[8, 3, 3]] , [[40, 33, 3]], [[168, 159, 3]]. Una matrice generatrice del codice additivo (40, 27) corrispondente
ad un codice quantistico additivo [[40, 33, 3]] è
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 ω ω ω ω ω ω ω ω ω ω ω ω 0 0 1 ω¯ ω ω ω¯ 1 ω 0 1 0 1 ω¯ ω ω ω¯ 1 0 1 0 1 ω ω 1 0 ω¯ ω¯ 0 ω 0 0 ω 0 ω ω¯ 1 ω¯ 1 1 0 ω 0 ω¯ 1 ω¯ 1 ω 0 1 1 0 0 1 1 ω ω ω¯ ω¯ ω 1 0 ω 0 ω ω¯ 1 ω¯ 0 0 0 ω ω ω ω 1 1 1 1 ω¯ ω 0 ω 1 ω¯ 1 ω¯ 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ω ω ω ω ω ω ω ω ω ω ω ω ω ω ω ω ω ω ω ω 0 ω ω¯ 1 0 ω ω¯ ω ω¯ 1 0 0 1 ω¯ ω ω¯ ω 0 1 ω¯ ¯ ω 1 ω¯ ω¯ 1 ω¯ 1 1 ω¯ 1 ω¯ ω 0 ω 0 0 ω 0 ω ω ω ω¯ ω¯ 0 0 1 1 0 0 1 1 ω ω ω¯ ω¯ ω ω ω¯ ω¯ 0 ¯ ω ω¯ ω¯ 0 0 0 0 ω ω ω ω 1 1 1 1 ω¯ ω¯ ω¯ ω¯ 0 1 1 1 ω ω ω ω ω¯ ω¯ ω¯ ω¯ ω ω ω ω ω¯ ω¯ ω¯ ω¯ 0
La costruzione00u|u + v00 sui codici binari ha un analogo per i codici
quantistici.2
Teorema 5.10
Sia Q1 un codice puro [[n, k1, d1]]associato ad un codice additivo C1
n, 2n−k1 , e Q
2 un codice puro [[n, k2, d2]] associato ad un codice
additivo C2, tale che C1 ⊆ C2.
Allora esiste un codice puro [[2n, k1− k2, d]], dove d = min {2d1, δ} ,
δ = dist (C2) .
Dim.
Prendiamo il codice additivo C, 2n, 22n−k1+k2costituito dai vettori
u|u + v, u ∈ C2⊥, v ∈ C1, dove la barra | denota la concatenazione.
Allora
C⊥=u|u + v : u ∈ C1⊥, v ∈ C2
ha distanza minima min {2d1, δ}3.
@
Ad esempio, combinando i codici [[14, 8, 3]] e [[14, 0, 6]] si ottiene un codice [[28, 8, 6]].