Paniere svolto di Codifica e crittografia (2025) - Risposte aperte

La distanza di Hamming, dati due vettori e della stessa lunghezza è definita come

(,)

il numero dei loro elementi che sono diversi, ovvero ≠ }

(,)={ ℎ

Ad esempio, se e abbiamo ≠ , = , = , ≠ e = ,

=[0,3,5,0,1] =[4,3,5,2,1],

1 1 2 2 3 3 4 4 5 5

quindi la loro distanza di Hamming è pari a 2; è chiaro che, per due vettori uguali, la distanza

di Hamming è pari a 0.

Il peso di Hamming, di un vettore è pari al numero di componenti non nulle, ovvero

, { ≠0}

()= ℎ

Alla base di questa definizione la distanza di Hamming tra due vettori si può definire anche

come il peso di Hamming della loro differenza, ovvero (,)=(−)=(−)

Riprendendo l’esempio precedente si ha

{ - ≠0, - =0, - =0, - ≠0 e - =0}=2

(−)=

1 1 2 2 3 3 4 4 5 5

19. Considerare un codice con distanza minima d, che viene decodificato a

massima verosomiglianza. Indicare il numero massimo di errori che il decoder

può sempre correggere, ed il numero massimo di errori che il decoder può sempre

rivelare.

Il numero massimo di errori che il decoder a massima verosimiglianza è in grado di

correggere, in un codice con distanza minima è

, /2

Quando c’è una certa probabilità che il decoder fallisca; questa probabilità

>/2,

dipende dal valore di e dalla struttura del codice.

Il numero massimo di errori che il decoder può sempre rivelare è

-1.

20. Spiegare la differenza tra correzione di errori.

Per correzione di errori da parte di un decoder si intende la sua idoneità nel capire che il

canale ha introdotto degli errori ed è capace di correggerli, ovvero, è in grado di riscostruire

il vettore introdotto dal canale.

21. Spiegare cosa si intende per rivelazione di errori tramite l'utilizzo di un

codice.

Per rivelazione di errori tramite l'utilizzo di un codice si intende la capacità del decoder di

capire che il canale ha introdotto degli errori, senza essere in grado di correggerli. 6

22. Illustrare il funzionamento di un codificatore a blocco sistematico.

Un codice viene definito sistematico se le parole di codice vengono ottenute aggiungendo

alla fine della sequenza di informazione le cifre di ridondanza.

Disporre di un codice in forma sistematica può essere conveniente da un punto di vista

algoritmico: questo semplifica infatti il numero di operazioni che devono essere eseguite per

codificare. Infatti, per un codice sistematico, per codificare è sufficiente calcolare gli −

simboli di ridondanza ed accostarli alla sequenza di informazione in ingresso.

Per un codice non sistematico, ogni simbolo della parola deve essere calcolato: pertanto, i

simboli da calcolare sono in questo caso .

In generale, un codice in forma sistematico può anche essere rappresentato in maniera più

efficiente (ovvero, con una minore occupazione di memoria) e garantisce una maggiore

semplicità anche in decodifica.

23. Illustrare il funzionamento di un codice a blocco.

Un codificatore a blocco prende in input sequenze di lunghezza fissata e le codifica in parole

la cui lunghezza è anch’essa fissata.

La sequenza in ingresso viene chiamata sequenza di informazione e la sua lunghezza viene

indicata con mentre l’output del codificatore è detto parola di codice e la lunghezza è

,

indicata con Il parametro viene chiamato dimensione del codice, il parametro viene

.

detto lunghezza del codice.

Un codice a blocco costituisce un mapping tra le sequenze di lunghezza input

(possibili

di codice definito su un campo finito con elementi) e le parole di codice , (numero

massimo di parole del codice), pertanto, affinché non vi sia perdita di informazione, deve

necessariamente essere >

↦>

L’espansione nella lunghezza viene misurata tramite l’inverso del code rate, definito come

=/.

La differenza tra e viene chiamata ridondanza, e viene generalmente indicata con

=−.

Quello che fa un codice è aggiungere “ridondanza” alla trasmissione, in altre parole: per

trasmettere simboli, se ne usano in realtà

>.

Un codificatore a blocco può lavorare solamente con sequenze di lunghezza pari

a .

24. Illustrare brevemente a cosa serve la matrice generatrice di un codice

lineare.

La matrice generatrice è tale per cui le parole di codice corrispondono a combinazioni lineari

delle sue righe.

Se un codice ha dimensione allora una sua matrice generatrice deve avere rango

, .

G u

In altre parole, se è la matrice generatrice di un codice lineare, ed è la sequenza di

informazione da codificare. La parola di codice corrispondente si calcola come c = ⋅. 7

25. Spiegare cosa è la matrice di parità di un codice lineare.

Una matrice di parità per dove un codice lineare con dimensione e ridondanza

,

è una matrice di dimensioni con rango tale per cui =0, e viene

=−, ×, , ⋅ ∀∈

utilizzata in ricezione per riconoscere se la sequenza che è stata ricevuta è una parola di

codice, oppure no.

26. Spiegare cose rappresenta la sindrome, in un codice lineare, e come può

essere utilizzata per rivelare errori.

La sindrome di attraverso può essere definita come (dove è un codice lineare

=⋅

e è la matrice di parità di dimensioni con rango essa a sua volta è un vettore di

×, )

lunghezza .

Si utilizza per rivelare facilmente gli errori:

• se la sindrome ottenuta è nulla, allora è una parola di codice;

• Se la sindrome di è non nulla, allora questo significa che non è una parola di

codice.

27. Illustrare brevemente la decodifica del codice a ripetizione binario.

Osserviamo che un codice a ripetizione binario con distanza minima può rivelare fino a

errori e ne può correggere fino a errori se è dispari e se è pari.

−1 −1/2 −2/2

Il processo di decodifica è immediato: si contano il numero di uni presenti nella sequenza

ricevuta, e se questo numero è minore di allora si sceglie la parola nulla; se questo

/2

numero è maggiore di allora si sceglie la parola formata da tutti uni.

/2,

28. Illustrare brevemente il processo di codifica del codice a ripetizione binario.

Considereremo solamente il caso del campo finito binario .

2

Questo codice esiste per ogni valore di lunghezza ha sempre dimensione e

, =1

ridondanza e contiene 2 =2 parole, che sono ;[1,1,⋯,1 ]}.

=−1 ={[0,0,⋯,0]

La generatrice è data 1 1⋯1], e il processo di codifica è molto semplice: si prende il

=[1

bit, e lo si replica per volte.

29. Consideriamo la trasmissione tramite un codice a ripetizione con lunghezza

4, su un canale AWGN, utilizzando un formato antipodale per i simboli (+A per

un bit 1, -A per un bit 0). Supponiamo che la sequenza ricevuta sia [-1.1 , -0.5 ,

0.6 , -0.2]. Decodificare in maniera hard, e stabilire se il risultato della decodifica

può considerarsi affidabile.

La sequenza ricevuta [-1.1 , -0.5 , 0.6 , -0.2] tramite la decodifica hard diventa [0, 0, 1, 0],

il numero di uni presenti nella sequenza ricevuta è 1 che è minore di allora viene

/2=2

codificata con la parola nulla, in questo caso si nota che è stato commesso solo 1 errore che

può essere corretto poiché se è pari, allora un codice a ripetizione di lunghezza può

correggere fino a errori, quindi corregge fino a 4-2/2=1 errore.

−2/2

Quindi il risultato della decodifica può considerarsi affidabile. 8

30. Consideriamo la trasmissione tramite un codice a ripetizione con lunghezza

5, su un canale AWGN, utilizzando un formato antipodale per i simboli (+A per

un bit 1, -A per un bit 0). Supponiamo che la sequenza ricevuta sia [1.1 , -0.5 ,

0.6 , -0.2 , 0.1]. Decodificare in maniera hard, e stabilire se il risultato della

decodifica può considerarsi affidabile.

La sequenza ricevuta [1.1, -0.5, 0.6, -0.2, 0.1] tramite la decodifica hard diventa

[1, 0, 1, 0, 1], il numero di uni presenti nella sequenza ricevuta è 3 che è maggiore di /2=

5/2=2.5 allora viene codificata con la parola formata da tutti 1, in questo caso si nota che

sono stati commessi 2 errori che possono essere corretti poiché se è dispari, allora un

codice a ripetizione di lunghezza può correggere fino a errori, quindi corregge fino

−1/2

a 5-1/2=2 errori. Quindi il risultato della decodifica può considerarsi affidabile.

31. Consideriamo la trasmissione tramite un codice a ripetizione con lunghezza

4, su un canale AWGN, utilizzando un formato antipodale per i simboli (+A per

un bit 1, -A per un bit 0). Supponiamo che la sequenza ricevuta sia [1.1 , -0.5 ,

0.6 , -0.2]. Decodificare in maniera hard, e stabilire se il risultato della decodifica

può considerarsi affidabile.

La sequenza ricevuta [1.1, -0.5 , 0.6 , -0.2] tramite la decodifica hard diventa [1, 0, 1, 0],

il numero di uni presenti nella sequenza ricevuta è 2 che è uguale a allora siamo in

/2=2

una situazione ambigua poiché ci troviamo a distanza 2 dalla parola nulla, ed a distanza 2

dalla parola di tutti uni. Il decoder potrebbe semplicemente segnalare la situazione ambigua,

o potrebbe decidere a caso, con una probabilità d’errore del 50%, quindi la decodifica non

può considerarsi affidabile.

32. Illustrare la differenza tra decodifica soft e decodifica hard.

Si parla di decodifica hard quando un decoder lavora solamente con elementi del campo

finito (nel caso binario, zeri ed uni), se il decoder sfrutta informazione aggiuntiva, cioè sfrutta

l’informazione ricevuta dal canale per migliorare il processo di decodifica si parla di

decodifica soft.

33. Illustrare il funzionamento del codice a bit di parità.

Il codice a bit di parità esiste per qualsiasi lunghezza ha dimensione e distanza

, &minu