5.3 GiraTartaruga e il [7 , 4 , 3]-codice di Hamming

Testo completo

(1)

Giochi e codici

In questo capitolo studiamo alcuni giochi e collegamenti con la teoria dei codici. Il primo gioco che vediamo `e Nim, che non ha molto da fare con codici, ma che `e molto facile da giocare, e serve come introduzione ai nimeri. Poi con i nimeri studiamo un gioco chiamato GiraTartaruga (Turning Turtles). Vedremo come si pu`o usare la teoria dei codici per trovare delle strategie buone. Per pi`u informazioni sulle cose trattate qui ci riferiamo a [2], [4].

5.1 Nim

Il gioco chiamato “Nim” `e giocato da due persone, Primo e Seconda. Hanno alcuni mucchi di fagioli. Primo fa la prima mossa, e Seconda fa la seconda mossa, e poi Primo la terza, ecc.

Una mossa consiste in prendere da esattamante un mucchio un certo numero (≥ 1) di fagioli.

Chi non pu`o pi`u muovere ha perso. Un gioco semplice; per`o ci sono problemi forse non tanto semplici: Primo o Seconda, data la posizione iniziale, sono in grado di prevedere l’esito del gioco, e quale `e la strategia ottimale?

Per affrontare questi problemi, si esprime una posizione del gioco come P = a1+ · · · + an, che vuole dire che ci sono n mucchi, con a1, . . . , anfagioli rispettivamente. (E’ un’espressione formale. Per esmpio non scriviamo 3 + 3 = 6.) Gli interi ai sono chiamati nimeri. Poi definiamo una funzione G che per una posizione P d`a un intero G(P ) ≥ 0. (G(P ) `e chiamato il nim-valore, o il numero di Grundy.) La posizione finale, dove non ci sono pi`u fagioli ha il nim-valore uguale a 0. Poi per una posizione non banale P consideriamo tutte le posizioni P0 che possiamo ottenere da P mediante una mossa. Per induzione sappiamo tutti i G(P0).

Adesso G(P ) sar`a il pi`u piccolo intero non-negativo non contenuto nel insieme dei G(P0).

Questo esprimiamo come

G(P ) = mex{G(P0) | P0 `e ottenuto da P mediante una mossa}. (5.1) Qui mex viene dal inglese “minimal excluded value”, che `e il minimo intero ≥ 0 non contenuto nel insieme.

Quindi di una posizione P possiamo in una mossa raggiungere una posizione P0 tale che G(P0) = a dove a `e qualsiasi numero tra 0 e G(P ) − 1. Anche G(P0) non `e mai uguale a G(P ).

Quando Seconda sa raggiungere una posizione P1 con G(P1) = 0, allora ha una strategia per vincere. Perch´e poi Primo deve muovere verso una posizione P2 con G(P2) > 0. Poi, Seconda pu`o di nuovo raggiungere una posizione P3 tale che G(P3) = 0. Il gioco continua cos`ı; Primo

(2)

24 Giochi e codici

riceve sempre posizioni da Seconda con il nim-valore zero. Quindi ad un certo punto Primo ha la posizione senza fagioli e perde.

5.2 L’addizione dei nimeri

Adesso vediamo come si pu`o calcolare G(P ). Per questo definiamo la nim-somma di due nimeri a e b come

a⊕ b = mex{a0⊕ b, a ⊕ b0| 0 ≤ a0 < a,0 ≤ b0 < b}.

E’ una definizione induttiva. Per calcolare a ⊕ b bisogna conoscere la nim-somma per nimeri pi`u piccoli. Esempi: 0⊕0 = 0, 1⊕0 = mex{0⊕0} = 1, 1⊕1 = mex{0⊕1, 1⊕0} = mex{1} = 0, 1 ⊕ 2 = mex{0 ⊕ 2, 1 ⊕ 0, 1 ⊕ 1} = mex{0, 1, 2} = 3.

Qui denotiamo con N l’insieme degli interi {0, 1, 2, . . .} con l’operazione ⊕. Vogliamo provare che N `e un gruppo commutativo. Poi vedremo un modo molto comodo per calcolare la nim-somma. Per un a ≥ 0 scriviamo a0 per un variabile che prende i valori 0, 1, . . . , a − 1.

Poi, con a∗ denotiamo un variabile che prende i valori 0, 1, . . . , a − 1, e forse anche un numero finito di valori > a. Quindi un a0 `e un caso speciale di un a∗.

Lemma 5.2.1 Siano a, b, c ∈ N . 1. a ⊕ 0 = 0 ⊕ a = a,

2. a ⊕ b = a ⊕ c se e solo se b = c, 3. a ⊕ b = mex{a ∗ ⊕b, a ⊕ b∗}, 4. a ⊕ b = b ⊕ a,

5. (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c), 6. a ⊕ a = 0.

Dim. Abbiamo a ⊕ 0 = mex{a0⊕ 0}. Ma per induzione a0⊕ 0 = a0.

In 2. se b 6= c, possiamo assumere che b > c. Allora a ⊕ b = mex(S) dove S `e un insieme che contiene a ⊕ c. Quindi a ⊕ b 6= a ⊕ c.

Osserviamo che {a∗⊕b, a⊕b∗} = {a0⊕b, a⊕b0}∪S, dove S contiene (forse) alcuni elementi della forma ˜a⊕ b, e a ⊕ ˜b con ˜a > a e ˜b > b. Da 2. vediamo che S non contiene a ⊕ b. Ma a⊕ b `e il valore minimo non contenuto in {a0⊕ b, a ⊕ b0}. Segue che `e anche il valore minimo non contenuto in {a0⊕ b, a ⊕ b0} ∪ S.

Abbiamo a ⊕ b = mex{a0 ⊕ b, a ⊕ b0}. Per induzione questo ultimo `e uguale a mex{b ⊕ a0, b0⊕ a} = b ⊕ a.

Abbiamo (a ⊕ b) ⊕ c = mex{(a ⊕ b)0 ⊕ c, (a ⊕ b) ⊕ c0}. Sia A questo ultimo insieme.

Sappiamo che a ⊕ b = mex{a0⊕ b, a ⊕ b0}, quindi (a ⊕ b)0 = 0, 1, . . . , u, dove u + 1 = a ⊕ b `e l’intero pi`u piccolo non fra i a0⊕ b e a ⊕ b0. Pu`o anche darsi che a0⊕ b > a ⊕ b, ma allora (a0⊕ b) ⊕ c 6= (a ⊕ b) ⊕ c per 2. Segue che il mex non cambia quando aggiungiamo (a0⊕ b) ⊕ c ad A. Quindi (a ⊕ b) ⊕ c = mex{(a0⊕ b) ⊕ c, (a ⊕ b0) ⊕ c, (a ⊕ b) ⊕ c0}. Per induzione questo `e uguale a mex{a0⊕ (b ⊕ c), a ⊕ (b0⊕ c), a ⊕ (b ⊕ c0)}. Che `e uguale a a ⊕ (b ⊕ c).

Abbiamo a ⊕ a = mex{a0 ⊕ a, a ⊕ a0}. Per induzione a0 ⊕ a0 = 0 e quindi secondo 2., a⊕ a0 6= 0 e a0 ⊕ a 6= 0 per ogni a0. Vediamo che 0 non `e contenuto nel insieme, e quindi

(3)

a⊕ a = 0. 2

Corollario 5.2.2 N con ⊕ `e un gruppo commutativo con elemento neutro 0.

Lemma 5.2.3 Sia ∆ ∈ N e supponiamo che H= {0, 1, . . . , ∆ − 1} `e un sottogruppo di N . Sia a ∈ H; allora ∆ ⊕ a = ∆ + a. (Dove + ´e la somma normale.)

Dim. Visto che ∆0 prende come valori tutti gli elementi di H; e perch´e H`e un gruppo, la stessa cose vale per ∆0 ⊕ a, cio`e ∆0 ⊕ a = 0, 1, . . . , ∆ − 1. Per induzione ∆ ⊕ a0 = ∆ + a0. Quindi ∆ ⊕ a = mex{∆0⊕ a, ∆ ⊕ a0} = mex{0, 1, . . . , ∆ − 1, ∆, . . . , ∆ + a − 1} = ∆ + a. 2

Corollario 5.2.4 Con la notazione del lemma precedente: se H `e un sottogruppo di N , anche H2∆ `e un sottogruppo di N .

Dim. H2∆contiene due tipi di elementi a e ∆ + a per a ∈ H. Usando Lemma 5.2.3 vediamo per esempio che (∆ + a) ⊕ b = (∆ ⊕ a) ⊕ b = ∆ ⊕ (a ⊕ b) = ∆ + (a ⊕ b) ∈ H2∆. 2 Il corollario implica che i H per ∆ = 2k sono sottogruppi di N . Quindi Lemma 5.2.3 implica che se j < k, allora 2j⊕ 2k= 2j+ 2k. Si pu`o usare questo per calcolare la nim-somma di due nimeri molto rapidamente, scrivendoli in forma binaria (e anche usando Lemma 5.2.1).

Esempio 5.2.5 Calcoliamo 7 ⊕ 11. Abbiamo 7 = 1 + 2 + 4 e 11 = 1 + 2 + 8. Quindi

7⊕11 = (1+2+4)⊕(1+2+8) = (1⊕2⊕4)⊕(1⊕2⊕8) = 1⊕1⊕2⊕2⊕4⊕8 = 4⊕8 = 4+8 = 12.

C’`e un altro modo per vedere questo metodo. Sia k tale che 2k+1−1 ≥ a, b e scriviamo a = Pk

i=0ai2i, e b = Pk

i=0bi2i. Consideriamo i vettori va = (a0, a1, . . . , ak), vb = (b0, . . . , bk) ∈ Fk+12 . Allora a⊕b corrisponde al vettore va+vb. Nel esempio: va= (1, 1, 1, 0) e vb = (1, 1, 0, 1), e va+ vb= (0, 0, 1, 1) che corrisponde a 12.

Lemma 5.2.6 Abbiamo G(a1+ · · · + an) = a1⊕ · · · ⊕ an.

Dim. Usiamo induzione su n e sul numero totale di fagioli. Se questi due sono 0 il risultato

`e banale. Quindi possiamo assumere il risultato per ogni gioco dove il numero di mucchi `e minore, o il numero totale di fagioli `e minore.

Scriviamo Q = a1 + · · · + an−1 (una posizione nel gioco con n − 1 mucchi), e P = a1+ · · · + an. Scriviamo Q0 per una posizione raggiungibile da Q in una mossa. Allora, le posizioni raggiungibili da P in una mossa sono

• Q0+ an, con (per induzione) G(Q0+ an) = G(Q0) ⊕ an,

• Q + a, dove 0 ≤ a < an, con G(Q + a) = G(Q) ⊕ a.

Vediamo che G(Q0) prende tutti i valori da 0 a G(Q)−1 (per definizione di G(Q)), e forse anche alcuni valori > G(Q). Quindi G(P ) = mex{G(Q) ∗ ⊕an,G(Q) ⊕ a0n} = G(Q) ⊕ an (Lemma 5.2.1, 3.). Adesso con induzione concludiamo G(P ) = a1⊕ · · · ⊕ an. 2

(4)

26 Giochi e codici

Esempio 5.2.7 Al inizio di un gioco di Nim ci sono tre mucchi con rispettivamente 3, 7, e 10 fagioli. Adesso Primo `e diventato furbo e calcola 3 ⊕ 7 ⊕ 10 = 14. Sa che deve cambiare la posizione tale che il nim-valore diventa 0. Calcola 3 ⊕ 7 = 4, e prende 6 fagioli dal mucchio pi`u grande. Adesso il nim-valore e 3 ⊕ 7 ⊕ 4 = 4 ⊕ 4 = 0. Seconda prende 3 fagioli dal secondo mucchio. Poi Primo prende tutto il primo mucchio, tale che il nim-valore `e 4 ⊕ 4 che di nuovo

`e 0. Adesso semplicemente copia le mosse di Seconda, tale che i mucchi rimangono uguali dopo la sua mossa. Quindi, dopo alcune mosse vince.

5.3 GiraTartaruga e il [7 , 4 , 3]-codice di Hamming

Adesso Primo e Seconda fanno un gioco diverso. Pare che in tempi antichi questo gioco sia giocato con tartarughe. Ma visto che non ne hanno, prendono n monete, e le mettono su una riga, tutte con croce sopra. Adesso una mossa consiste in

1. girare una moneta da croce a testa,

2. volendo girare un’altra moneta a sinistra di quella che `e stata girata prima (e questa pu`o essere girata da croce a testa, o da testa a croce).

Chi non pu`o pi`u muovere perde il gioco.

Per analizzare questo gioco si descrive una posizione con un vettore (ζ1, . . . , ζn) dove ζi= 1 se la i-esima moneta ha croce sopra, altrimenti ζi= 0. Adesso definiamo una funzione G esattamante nella stessa modo che per Nim. Cio`e G(0, . . . , 0) = 0 e se P 6= (0, . . . , 0), allora G(P ) `e definito da (5.1).

Esempio 5.3.1 Dalla posizione (1, 0, . . . , 0) possiamo fare una sola mossa, che d`a la posizione (0, . . . , 0). Quindi G(1, 0, . . . , 0) = 1. Da (0, 1, 0, . . . , 0) possiamo fare due mosse: solo girare la seconda moneta, che d`a la posizione (0, . . . , 0), oppure girare la seconda moneta e poi anche il primo che d`a la posizione (1, 0, . . . , 0). Segue che G(0, 1, 0, . . . , 0)) = 2. Poi G(1, 1, 0, . . . , 0) = 3.

Di nuovo la strategia ottimale `e di cercare di raggiungere una posizione con nim-valore 0. Il fatto, forse un po’ sorprendente, `e che possiamo calcolare il nim-valore di una posizione nello stesso modo che per Nim.

Lemma 5.3.2 Abbiamo G(ζ1, . . . , ζn) = ζ1· 1 ⊕ ζ2· 2 ⊕ · · · ⊕ ζn· n, dove ζi· i = i se ζi= 1 e altrimenti ζi· i = 0.

Dim. La prova `e per induzione su n e N (P ) = Pn

i=1ζi2i. Nota che una mossa fa sempre diminuire questo ultimo numero. Se tutti e due sono 0 allora il lemma `e banale. Quindi sia P una posizione non banale e assumiamo il risultato per posizioni P0 con meno monete, o con N(P0) < N (P ).

Si pu`o scrivere P = (P0, ζn). Se ζn = 0 allora da P abbiamo esattamente le stesse possibilit`a che da P0, quindi G(P ) = G(P0) e concludiamo con induzione.

Assumiamo che ζn= 1. Allora da P possiamo raggiungere due tipi di posizioni. Anzitutto abbiamo (P00, ζn), dove P00`e una posizione raggiungibile da P0 con una mossa. Per induzione G(P00, ζn) = G(P00) ⊕ n. E G(P00) prende tutti i valori 0, 1, . . . , G(P0) − 1 e forse anche alcuni valori > G(P0). Poi abbiamo le posizioni (P000,0) dove P000 `e ottenuto da P0 grirando una o nessuna moneta. Se nessuna moneta `e girata, P000 = P0 e G(P000,0) = G(P0). Se la i-esima

(5)

moneta `e girata da testa a croce, allora G(P000) = G(P0) ⊕ i (perch´e nell’espressione per G(P000) il nimero i non era presente). Ma se viene girata da croce a testa abbiamo anche G(P000) = G(P0) ⊕ i (perch´e i `e presente nell’espressione per G(P0), ma va via nell’espressione per P000; e fare ⊕i ha lo stesso effetto, visto che i ⊕ i = 0). Concludiamo che G(P000,0) = G(P0) ⊕ b dove b= 0, 1, . . . , n − 1.

Adesso G(P ) = mex{G(P0) ∗ ⊕n, G(P0) ⊕ n0} = G(P0) ⊕ n (Lemma 5.2.1, 3.). La prova `e

finita con induzione. 2

Adesso possiamo giocare GiraTartaruga calcolando i nim-valori, e sempre faccendo mosse che portano a nim-valore zero. Per`o, dal Lemma 5.3.2 segue anche un collegamento con la teoria dei codici, che pu`o essere sfruttato.

Nel seguito diremo che una posizione P `e vincente se il giocatore che muove verso P ha una strategia per vincere il gioco.

Prendiamo n = 7. Lemma 5.3.2 dice che P = (ζ1, . . . , ζ7) `e una posizione vincente se e solo se ζ1· 1 ⊕ · · · ⊕ ζ7· 7 = 0. Adesso vediamo P come elemento di F72, e scriviamo i nimeri 1, 2, . . . , 7 come vettori in F32, come nella sezione precedente. Allora vediamo che P `e una posizione vincente se e solo se P HT = 0, dove

H=

1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1

.

La conclusione `e che P `e una posizione vincente se e solo se P sta nel codice con matrice parity check H. Per questo motivo quel codice `e chiamato il codice vincente. In questo caso (n = 7) vediamo che H `e la matrice parity check di un [7, 4, 3]-codice di Hamming. Visto che la posizione iniziale (1, 1, . . . , 1) `e un elemento del codice, Seconda ha una strategia per vincere.

Come abbiamo visto, `e molto facile decidere se un vettore `e un elemento del [7, 4, 3]- codice di Hamming, usando il piano di Fano. Siccome le colonne di H sono ordinate un po’ particolarmente, bisogna cambiare l’enumerazione dei punti. Per esempio, si pu`o fare l’enumerazione cos`ı:

3 5 6

2

1

4

7

(6)

28 Giochi e codici

5.4 GiraTartaruga generalizzato

Adesso giochiamo GiraTartaruga con la regola che si pu`o girare 1, 2, . . . , t monete, e quella pi`u a destra deve essere girata da croce a testa. Allora il gioco della sezione precedente ha t = 2.

Di nuovo descriviamo una posizione del gioco con un vettore di lungezza n, con coeefficienti 0, 1. Anche definiamo la funzione G nello stesso modo.

Lemma 5.4.1 Sia Pi il vettore con 1 sull’i-esima posizione, e 0 altrove. Allora 1. G(Pi) = mex{0, G(Pi1) ⊕ · · · ⊕ G(Pik) | 1 ≤ i1 < i2 <· · · < ik< i,1 ≤ k ≤ t − 1}, 2. G(ζ1, . . . , ζn) = ζ1G(P1) ⊕ · · · ⊕ ζnG(Pn).

Dim. La prova `e analoga alla prova di Lemma 5.3.2. Usiamo induzione su n e Pn

i=1ζi2i. Sia S = {0, G(Pi1) ⊕ · · · ⊕ G(Pik) | 1 ≤ i1 < i2 < · · · < ik < n,1 ≤ k ≤ t − 1}.

Dall’ipotesi di induzione e l’elenco di tutte le mosse posibili da Pnsegue immediatamente che G(Pn) = mex(S).

Scriviamo P = (P0, ζn), e usiamo la stessa ragionamento che nella Prova di Lemma 5.3.2;

in particolare possiamo assumere che ζn= 1. Abbiamo G(P00,1) = G(P0) ∗ ⊕G(Pn), dove P00 percorre le posizioni raggiungibili da P0 con una mossa. Poi possiamo fare una mossa della forma (P0,1) → (P000,0) dove P000 `e ottenuto da P0 girando ≤ t − 1 monete. Siano i1, . . . , ik le posizioni dove una moneta `e girata. Allora G(P000,0) = G(P000) = G(P0)⊕G(Pi1)⊕· · ·⊕G(Pik).

Adesso vediamo che G(Pi1) ⊕ · · · ⊕ G(Pik) percorre tutto l’insieme S. Quindi G(P000,0) = G(P0) ⊕ G(Pn)∗. Segue che G(P ) = mex{G(P0) ∗ ⊕G(Pn), G(P0) ⊕ G(Pn)∗} = G(P0) ⊕ G(Pn),

e possiamo finire la prova con induzione. 2

Adesso possiamo definire il codice vincente come

C= {(ζ1, . . . , ζn) | ζ1G(P1) ⊕ · · · ⊕ ζnG(Pn) = 0}.

Come nella sezione precedente `e un codice lineare in Fn2. Si pu`o trovarene una matrice parity check calcolando i valori G(Pi). E’ anche possibile dare un’altra caratterizzazione di C.

Per P = (ζ1, . . . , ζn) definiamo N (P ) =Pn

i=1ζi2i. Definamo un ordine sui vettori P con P0 < P se N (P0) < N (P ). Questo ordine `e chiamato l’ordine lessicografico.

Adesso percorriamo l’insieme dei P in ordine ascendente. Per ogni P decidiamo se sar`a un elemento di C o no. E P diventa un elemento di C precisamente se non esiste P0 ∈ C (necessariamente con P0 < P) tale che d(P, P0) ≤ t (dove d(P, P0) `e la distanza di Hamming).

Si vede che il codice che viene fuori cos`ı ha distanza minima uguale a t + 1. E’ chiamato il codice lessicografico di lunghezza n e distanza minima t + 1.

Esempio 5.4.2 E’ un po’ laborioso fare questo algoritmo a mano, perch´e bisogna considerare 2nvettori P . Ma per n = 5 si pu`o farlo, scrivendo i numeri 0, 1, . . . , 31 in forma binaria, cio`e come un vettore binario di lunghezza 5. Prendiamo t = 2 (cio`e GiraTartaruga come nella sezione precedente). In questo caso C consiste di 00000, 11100, 10011, 01111. La posizione iniziale `e 11111. Quindi Primo, chi ha letto la proposizione qui sotto, muove verso 01111.

Adesso, se Seconda girasse due monete, Primo avrebbe vinto subito, quindi gira una moneta, ottenendo 01110. Poi Primo va di nuovo verso un elemento del codice, girando la prima e quarta moneta, 11100. Adesso `e ovvio che Seconda deve perdere.

(7)

Proposizione 5.4.3 Giochiamo GiraTartaruga con n monete, ogni mossa girando ≤ t mon- ete. Le posizioni vincenti sono esattamente quelli dentro il codice lessicografico con lunghezza n e distanza minima t + 1.

Dim. Con C denotiamo il codice lessicografico. Con induzione su N (P ) proviamo che P ∈ C se e solo se P `e una posizione vincente.

Sia P una posizione fuori C. Allora esiste P0 ∈ C con N (P0) < N (P ) e d(P0, P) ≤ t.

Quindi, girando al massimo t monete `e possibile cambiare P in P0. Dal fatto N (P0) < N (P ) segue che la moneta girata pi`u a destra deve essere girata da croce a testa (da 1 a 0). Quindi da P in una mossa del gioco possiamo raggiungere P0 che `e una posizione vincente (per induzione). Quindi P non `e une posizione vincente.

Sia P ∈ C e sia P → P0 una mossa del gioco. Allora N (P0) < N (P ) e d(P0, P) ≤ t. Visto che P ∈ C, abbiamo che P0 6∈ C. Per induzione ogni P0 non `e una posizione vincente, quindi

P `e una posizione vicente. 2

Sopra abbiamo visto che il codice vincente `e lineare. La proposizione precedente dice che il codice vicente `e il codice lessicografico. Quindi abbiamo il seguente corollario.

Corollario 5.4.4 Sia C un codice lessicografico. Allora C `e lineare.

Esempio 5.4.5 Giochiamo GiraTartaruga con t = 7 e n = 24 monete. Allora il codice vincente ha distanza minima e lunghezza 24. Scrivendo abbastanza elementi del codice lessicografico corrispondente, si pu`o provare che ha dimensione 12. (E’ anche possibile cal- colare i G(Pi) per 1 ≤ i ≤ 24, usando per esempio un computer. Cos`ı si ottiene la matrice parity check del codice vincente. Da quella `e facile vedere che ha dimensione 12.) Allora per il Teorema 4.3.2 `e equivalente al codice di Golay G24. Quindi usando il MOG si pu`o giocare (in principio) questo tipo di GiraTartaruga. Per farlo velecemente bisogna fare un po’ di eserecizio.

5.5 Esercizi

1. Giochiamo GiraTartaruga con n = 8 e t = 2. Descrivere il codice vincente. Chi ha una strategia per vincere, Primo o Seconda? Quale `e la prima mossa?

2. Giochiamo GiraTartaruga con n = 8 e t = 3. Trovare una matrice parity check per il codice vincente. Quali sono i parametri [n, k, d]? Chi ha la strategia vincente?

3. Si gioca GiraTartaruga con n = 24 e t = 7. Nella prima mossa Primo decide di girare 5 monete. Spiegare come adesso Seconda pu`o trovare una buona mossa.

(8)

30 Giochi e codici

(9)

[1] J. H. Conway. Hexacode and tetracode—MOG and MINIMOG. In Computational group theory (Durham, 1982), pages 359–365. Academic Press, London, 1984.

[2] J. H. Conway. On numbers and games. A K Peters Ltd., Natick, MA, second edition, 2001.

[3] J. H. Conway and N. J. A. Sloane. Sphere packings, lattices and groups, volume 290 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Math- ematical Sciences]. Springer-Verlag, New York, third edition, 1999. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R.

A. Parker, L. Queen and B. B. Venkov.

[4] John H. Conway and N. J. A. Sloane. Lexicographic codes: error-correcting codes from game theory. IEEE Trans. Inform. Theory, 32(3):337–348, 1986.

[5] Jeffrey S. Leon. Computing automorphism groups of error-correcting codes. IEEE Trans.

Inform. Theory, 28(3):496–511, 1982.

figura

Updating...

Riferimenti

Updating...

Argomenti correlati :