Esercizio 6codice SEC per una parola di 16 bit

In questa pagina 5

Testo (svolto in aula, lezione del 2 novembre 2016). Sviluppare un codice SEC (single error correcting) per una parola di dati di 16 bit. Generare il codice per la parola di dati $0101\,0000\,0011\,1001$ .

Numero di bit di controllo

$2^k - 1 \ge 16 + k$ : con $k = 4$ , $15 < 20$ ; con $k = 5$ , $31 \ge 21$ ✓. Quindi 5 bit di controllo e $16 + 5 = 21$ posizioni (vedi Codifiche binarie e informazione non numerica).

Tabella delle posizioni

Controllo nelle potenze di 2 (1, 2, 4, 8, 16); i dati riempiono le altre posizioni partendo da destra con il bit meno significativo $D_1$ :

Pos.	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
	$D_{16}$	$D_{15}$	$D_{14}$	$D_{13}$	$D_{12}$	$C_{16}$	$D_{11}$	$D_{10}$	$D_9$	$D_8$	$D_7$	$D_6$	$D_5$	$C_8$	$D_4$	$D_3$	$D_2$	$C_4$	$D_1$	$C_2$	$C_1$

Equazioni del codice

Ogni dato entra nei bit di controllo corrispondenti agli 1 della sua posizione in binario (es. $D_1$ in posizione $3 = 00011$ entra in $C_1$ e $C_2$ ):

$C_1 = D_1 \oplus D_2 \oplus D_4 \oplus D_5 \oplus D_7 \oplus D_9 \oplus D_{11} \oplus D_{12} \oplus D_{14} \oplus D_{16}$ (posizioni dispari)
$C_2 = D_1 \oplus D_3 \oplus D_4 \oplus D_6 \oplus D_7 \oplus D_{10} \oplus D_{11} \oplus D_{13} \oplus D_{14}$ (posizioni 3, 6, 7, 10, 11, 14, 15, 18, 19)
$C_4 = D_2 \oplus D_3 \oplus D_4 \oplus D_8 \oplus D_9 \oplus D_{10} \oplus D_{11} \oplus D_{15} \oplus D_{16}$ (posizioni 5, 6, 7, 12, 13, 14, 15, 20, 21)
$C_8 = D_5 \oplus D_6 \oplus D_7 \oplus D_8 \oplus D_9 \oplus D_{10} \oplus D_{11}$ (posizioni 9–15)
$C_{16} = D_{12} \oplus D_{13} \oplus D_{14} \oplus D_{15} \oplus D_{16}$ (posizioni 17–21)

Codice della parola data

$D_{16} \dots D_1 = 0101\,0000\,0011\,1001$ , quindi valgono 1 solo $D_1, D_4, D_5, D_6, D_{13}, D_{15}$ .

$C_1$ : tra $D_1, D_2, D_4, D_5, D_7, D_9, D_{11}, D_{12}, D_{14}, D_{16}$ sono a 1 $D_1, D_4, D_5$ → tre 1 → $C_1 = 1$
$C_2$ : tra $D_1, D_3, D_4, D_6, D_7, D_{10}, D_{11}, D_{13}, D_{14}$ sono a 1 $D_1, D_4, D_6, D_{13}$ → quattro → $C_2 = 0$
$C_4$ : tra $D_2, D_3, D_4, D_8, D_9, D_{10}, D_{11}, D_{15}, D_{16}$ sono a 1 $D_4, D_{15}$ → due → $C_4 = 0$
$C_8$ : tra $D_5 \dots D_{11}$ sono a 1 $D_5, D_6$ → due → $C_8 = 0$
$C_{16}$ : tra $D_{12} \dots D_{16}$ sono a 1 $D_{13}, D_{15}$ → due → $C_{16} = 0$

Risultato

$C_{16}C_8C_4C_2C_1 = 00001$ . Parola memorizzata di 21 bit (posizioni 21 → 1):

$0\,1\,0\,1\,0\ \ 0\ \ 0\,0\,0\,0\,0\,1\,1\ \ 0\ \ 1\,0\,0\ \ 0\ \ 1\ \ 0\,1$

cioè $D_{16}..D_{12} = 01010$ , $C_{16} = 0$ , $D_{11}..D_5 = 0000011$ , $C_8 = 0$ , $D_4D_3D_2 = 100$ , $C_4 = 0$ , $D_1 = 1$ , $C_2C_1 = 01$ .

Versione ripasso

Metodo: Hamming SEC; $2^k - 1 \ge 16 + k$ : $k = 4$ dà $15 < 20$ , $k = 5$ dà $31 \ge 21$ $\Rightarrow$ 5 controlli, 21 posizioni.

Controlli in 1, 2, 4, 8, 16; dati nelle altre, $D_1$ in posizione 3 fino a $D_{16}$ in 21.
Equazioni (posizioni coperte):
- $C_1 = D_1 \oplus D_2 \oplus D_4 \oplus D_5 \oplus D_7 \oplus D_9 \oplus D_{11} \oplus D_{12} \oplus D_{14} \oplus D_{16}$
- $C_2 = D_1 \oplus D_3 \oplus D_4 \oplus D_6 \oplus D_7 \oplus D_{10} \oplus D_{11} \oplus D_{13} \oplus D_{14}$
- $C_4 = D_2 \oplus D_3 \oplus D_4 \oplus D_8 \oplus D_9 \oplus D_{10} \oplus D_{11} \oplus D_{15} \oplus D_{16}$
- $C_8 = D_5 \oplus \dots \oplus D_{11}$ ; $C_{16} = D_{12} \oplus \dots \oplus D_{16}$
I dati a 1 sono $D_1, D_4, D_5, D_6, D_{13}, D_{15}$ $D_{1}, D_{4}, D_{5}, D_{6}, D_{13}, D_{15}$ :
- $C_1$ : $D_1, D_4, D_5$ (tre) $\to 1$ ; $C_2$ : $D_1, D_4, D_6, D_{13}$ (quattro) $\to 0$ ; $C_4$ : $D_4, D_{15}$ $\to 0$ ; $C_8$ : $D_5, D_6$ $\to 0$ ; $C_{16}$ : $D_{13}, D_{15}$ $\to 0$ .

$C_{16}C_8C_4C_2C_1 = 00001$ . Parola di 21 bit: $D_{16}..D_{12} = 01010$ , $C_{16} = 0$ , $D_{11}..D_5 = 0000011$ , $C_8 = 0$ , $D_4D_3D_2 = 100$ , $C_4 = 0$ , $D_1 = 1$ , $C_2C_1 = 01$ .

Esercizi su questo argomento

Esercizio 29 · codice di Hamming su 16 bit di dati

Lezioni in cui compare

Lezione 12 · Esercizi su Hamming e dischi magnetici

Teoria collegata

Codifiche binarie e informazione non numerica