[BASE Cinque - Appunti di Matematica ricreativa]

Zio Hamming ti sgamma

Da un gioco di divinazione binaria al codice di Hamming

Sette domande, una menzogna

Come si può indovinare un numero pensato, ponemdo il numero minimo di domande che hanno risposte del tipo sì/no e correggendo un errore o una menzogna?

La seguente attività è tratta da Sette domande, una menzogna..., di Andrea Caranti, Matteo Zendron, Maurizio Marinelli, Matteo Corazza, Francesco Prantil, Lorenzo Valdan, Dipartimento di Matematica e Corso di Laurea in Matematica, Facoltà di Scienze Matematiche, Fisiche e Naturali Università di Trento.(http://www-math.science.unitn.it/~caranti/).

Pensate un numero da 0 a 15 compresi.

Le domande sono:

  1. È maggiore di 7?
  2. È uno fra 4; 5; 6; 7; 12; 13; 14; 15?
  3. È uno fra 2; 3; 6; 7; 10; 11; 14; 15?
  4. È dispari?
  5. È uno fra 2; 3; 4; 5; 8; 9; 14; 15?
  6. È uno fra 1; 2; 4; 7; 9; 10; 12; 15?
  7. È uno fra 1; 3; 4; 6; 8; 10; 13; 15?

Le domande 1, 2, 3, 4 chiedono i quattro bit che esprimono in base 2 il numero pensato (vedi la pagina Divinazione binaria).

Le domande 5, 6, 7 servono a individuare la menzogna, ovvero l’errore.

I codici a correzione d’errore servono proprio a correggere gli errori che inevitabilmente si verificano nel corso di una trasmissione di dati.

Ai dati da trasmettere (in questo caso, le quattro domande originali, che già da sole determinerebbero il numero) vengono aggiunti dati che sarebbero ridondanti, ma che permettono di rivelare o magari di correggere uno o più errori.

Un gioco geometrico rivela l'errore

L'errore si può scoprire con un piccolo gioco geometrico. Si disegna uno schema come quello della figura qui sotto. Ogni punto rappresenta la risposta ad una domanda. I punti sono numerati secondo lo stesso ordine delle domande.

Mentre voi rispondete alle domande, io segno sul piano un punto nero per ogni “sí”, e un punto bianco per ogni “no”.

Se non avete mentito ci sono 4 possibilità:

Se avete mentito (una volta), c’è un unico modo di cambiare un punto in modo da ricondursi a una di queste situazioni.

Questo punto corrisponde alla risposta inesatta.

Per "indovinare" il numero pensato, si guardano i colori dei punti 1, 2, 3, 4. Ad ogni punto corrisponde un bit:

Facciamo qualche prova.

1. Supponiamo di pensare 4 e di non mentire mai. Il gioco si sviluppa così.

Ci sono tre punti bianchi e quattro neri, e i tre punti bianchi stanno su una retta. Perciò non c'è stata alcuna menzogna e i bit del numero pensato corrispondono ai colori dei primi quattro punti:

0100 = 4 (in base 10)

  1. È maggiore di 7?
    no (punto 1 bianco)
  2. È uno fra 4; 5; 6; 7; 12; 13; 14; 15?
    sì (punto 2 nero)
  3. È uno fra 2; 3; 6; 7; 10; 11; 14; 15?
    no (punto 3 bianco)
  4. È dispari?
    no (punto 4 bianco)
  5. È uno fra 2; 3; 4; 5; 8; 9; 14; 15?
    sì (punto 5 nero)
  6. È uno fra 1; 2; 4; 7; 9; 10; 12; 15?
    sì (punto 6 nero)
  7. È uno fra 1; 3; 4; 6; 8; 10; 13; 15?
    sì (punto 7 nero)


2. Supponiamo di pensare 11 e di mentire alla domanda 4. Il gioco si sviluppa così.

Ci sono 5 punti bianchi e 2 neri. Ciò significa che c'è stata una menzogna. L'unico modo per rientrare in uno dei casi possibili è annerire il punto 4. Dunque la risposta falsa è la quarta e i bit che compongono il numero pensato sono:

1011 = 11 (in base 10)

  1. È maggiore di 7?
    sì (punto 1 nero)
  2. È uno fra 4; 5; 6; 7; 12; 13; 14; 15?
    no (punto 2 bianco)
  3. È uno fra 2; 3; 6; 7; 10; 11; 14; 15?
    sì (punto 3 nero)
  4. È dispari?
    no (menzogna! punto 4 bianco)
  5. È uno fra 2; 3; 4; 5; 8; 9; 14; 15?
    no (punto 5 bianco)
  6. È uno fra 1; 2; 4; 7; 9; 10; 12; 15?
    no (punto 6 bianco)
  7. È uno fra 1; 3; 4; 6; 8; 10; 13; 15?
    no (punto 7 bianco)

Una curiosità: e se mento a una domanda di controllo?

3. Supponiamo di pensare 7 e di mentire alla domanda 5. Il gioco si sviluppa così.

Ci sono 2 punti bianchi e 5 neri. Ciò significa che c'è stata una menzogna. L'unico modo per rientrare in uno dei casi possibili è rendere bianco il punto 5. Dunque la risposta falsa è la quinta e i bit che compongono il numero pensato sono:

0111 = 7 (in base 10)

  1. È maggiore di 7?
    no (punto 1 bianco)
  2. È uno fra 4; 5; 6; 7; 12; 13; 14; 15?
    sì (punto 2 nero)
  3. È uno fra 2; 3; 6; 7; 10; 11; 14; 15?
    sì (punto 3 nero)
  4. È dispari?
    sì (punto 4 nero)
  5. È uno fra 2; 3; 4; 5; 8; 9; 14; 15?
    sì (menzogna! punto 5 nero)
  6. È uno fra 1; 2; 4; 7; 9; 10; 12; 15?
    sì (punto 6 nero)
  7. È uno fra 1; 3; 4; 6; 8; 10; 13; 15?
    no (punto 7 bianco)

4. Supponiamo di pensare 13 e di mentire alla domanda 7. Il gioco si sviluppa così.

Ci sono 4 punti bianchi e 3 neri, ma i 3 neri non sono allineati. Ciò significa che c'è stata una menzogna. L'unico modo per rientrare in uno dei casi possibili è annerire il punto 7. Dunque la risposta falsa è la settima e i bit che compongono il numero pensato sono:

1101 = 13 (in base 10)

  1. È maggiore di 7?
    sì (punto 1 nero)
  2. È uno fra 4; 5; 6; 7; 12; 13; 14; 15?
    sì (punto 2 nero)
  3. È uno fra 2; 3; 6; 7; 10; 11; 14; 15?
    no (punto 3 bianco)
  4. È dispari?
    sì (punto 4 nero)
  5. È uno fra 2; 3; 4; 5; 8; 9; 14; 15?
    no (punto 5 bianco)
  6. È uno fra 1; 2; 4; 7; 9; 10; 12; 15?
    no (punto 6 bianco)
  7. È uno fra 1; 3; 4; 6; 8; 10; 13; 15?
    no (menzogna! punto 7 bianco)

Risposta

Il sistema è in grado di correggere qualsiasi menzogna. Purché sia una sola!

Materiali per fare esperimenti

  1. È maggiore di 7?

  2. È uno fra 4; 5; 6; 7; 12; 13; 14; 15?

  3. È uno fra 2; 3; 6; 7; 10; 11; 14; 15?

  4. È dispari?

  5. È uno fra 2; 3; 4; 5; 8; 9; 14; 15?

  6. È uno fra 1; 2; 4; 7; 9; 10; 12; 15?

  7. È uno fra 1; 3; 4; 6; 8; 10; 13; 15?

  1. È maggiore di 7?

  2. È uno fra 4; 5; 6; 7; 12; 13; 14; 15?

  3. È uno fra 2; 3; 6; 7; 10; 11; 14; 15?

  4. È dispari?

  5. È uno fra 2; 3; 4; 5; 8; 9; 14; 15?

  6. È uno fra 1; 2; 4; 7; 9; 10; 12; 15?

  7. È uno fra 1; 3; 4; 6; 8; 10; 13; 15?

Se necessario, fotocopiate più volte questa pagina.


Zio Hamming ti sgamma

Esistono almeno due tipi di codici ridondanti.

Un esempio di codice a rivelazione d'errore.

Codice BCD (binary coded decimal) con bit di parità

Per costruire un codice BCDa rivelazione di errore, si può aggiungere ad ogni parola codice(=sequenza di 4 bit)un bit ridondante detto di parità.

Il bit di paritàviene posto a 0 o a 1, in modo tale che la somma degli "1" nella parola codice sia pari.

Cifra

decimale

Rappresentazione

in codice BCD

Bit parità

0

0 0 0 0

0

1

0 0 0 1

1

2

0 0 1 0

1

3

0 0 1 1

0

4

0 1 0 0

1

5

0 1 0 1

0

6

0 1 1 0

0

7

0 1 1 1

1

8

1 0 0 0

1

9

1 0 0 1

0

Esempio di codice a correzione d'errore.

Codice di Hamming Autocorrettivo (4+3)

Per ogni 4 bit d'informazione si hanno 3 bit di controllo di parità.

Si possono disporre i 4 bit d'informazione e i 3 bit di parità nel seguente modo:

bit 1

bit 2

bit 3

bit 4

bit 5

bit 6

bit 7

I1

I2

I3

I4

P1

P2

P3

*

*

*


*




*

*

*


*


*

*


*



*

Spiegazione:

Esempi senza errori.

bit 1

bit 2

bit 3

bit 4

bit 5

bit 6

bit 7

I1

I2

I3

I4

P1

P2

P3

0

0

0

0

0

0

0

1

0

1

1

0

0

0

1

1

1

1

1

1

1

Esercizio.

Inserite il bit mancante secondo il codice di Hamming presentato in questa pagina.

bit 1

bit 2

bit 3

bit 4

bit 5

bit 6

bit 7

I1

I2

I3

I4

P1

P2

P3


1

0

1

1

0

0

1

0

0

1

1

1


1

1


0

1

0

0

Una curiosità: i bit di controllo devono stare proprio nelle posizioni 3, 4, 5?

Non necessariamente. Possono stare anche in altre posizioni, ad esempio possono occupare le posizioni:

Inoltre possono controllare la parità di gruppi di bit diversi da quelli indicati.

figura
Il disegno in questa medaglia suggerisce che i bit di controllo possono verificare le parità seguenti:
bit5 - 1, 2, 3
bit6 - 1, 2, 4
bit7 - 1, 3, 4
figura
Richard Wesley Hamming e il suo gatto.

Esempio con un errore da correggere.

Proviamo a correggere la sequenza errata esaminando tutti i casi possibili.


bit 1

bit 2

bit 3

bit 4

bit 5

bit 6

bit 7



I1

I2

I3

I4

P1

P2

P3


Sequenza corretta

1

1

0

1

0

0

1


Sequenza errata (con un solo errore)

1

0

0

1

0

0

1


Se fosse errato il bit1...

0

0

0

1

0

1

1

sarebbe errato anche il bit6

Se fosse errato il bit2...

1

1

0

1

0

0

1

...nessun altro sarebbe errato

Se fosse errato il bit3...

1

0

1

1

0

0

0

sarebbe errato anche il bit7

Se fosse errato il bit4...

1

0

0

0

1

0

1

sarebbe errato anche il bit5

Se fosse errato il bit5...

1

0

0

0

1

0

1

sarebbe errato anche il bit4

Se fosse errato il bit6...

0

0

0

1

0

1

1

sarebbe errato anche il bit1

Se fosse errato il bit7...

1

0

1

1

0

0

0

sarebbe errato anche il bit3

Soltanto nel caso in cui il bit 2 è errato, la sequenza si può "mettere a posto" cambiando un solo bit. Quindi nella sequenza 1001001, il bit errato è il secondo (da sinistra).

Con il triangolo di Fano, correggere l'errore è più veloce e divertente.

Ricorda: 1 = punto nero, 0 = punto bianco.


bit 1

bit 2

bit 3

bit 4

bit 5

bit 6

bit 7

Sequenza errata

1

0

0

1

0

0

1


Ci sono 4 punti bianchi e 3 neri, ma i 3 neri non sono allineati. Ciò significa che c'è stato un errore. L'unico modo per rientrare in uno dei casi possibili è annerire il punto 2. Il bit errato è il secondo e la sequenza esatta è: 1101001.

Una curiosità: ma il computer, per correggere i bit, disegna il triangolo? O esamina tutti i casi possibili?

No, il computer può soltanto esaminare i bit e confrontarli fra di loro. Perciò deve esistere un algoritmo di correzione degli errori basato soltanto sull'esame dei bit. Vogliamo trovarlo?

Un'altra curiosità: il codice di Hamming è in grado di correggere anche se stesso? Cioè, che cosa accade se è errato un bit di controllo?

Lo verificheremo rispondendo alla domanda precedente.

Ecco un possibile algoritmo.

Dato il seguente codice di Hamming:

bit 1

bit 2

bit 3

bit 4

bit 5

bit 6

bit 7

I1

I2

I3

I4

P1

P2

P3

*

*

*


*




*

*

*


*


*

*


*



*

Esamino soltanto i tre bit di controllo: P1, P2, P3.

Ricorda che:

Dalla tabella si deduce facilmente che:

E' quindi evidente che il codice di Hamming "corregge anche se stesso" o meglio corregge un qualunque bit errato su 7.

Tre citazioni di zio Hamming

Data creazione: aprile 2006

Ultimo aggiornamento: aprile 2006

xhtml 1.1


Sito Web realizzato da Gianfranco Bo