Reti di calcolatori - Esercizi

Esercizi di teoria.

Formulario

Lista di formule generali per risolvere gli esercizi.

Legenda

BWBanda (bps)BWs→dBanda dalla sorgente alla destinazione (bps)BWd→sBanda dalla destinazione alla sorgente (bps)BWeBanda effettiva (bps)\begin{array}{ll} BW & \text{Banda (bps)} \newline BW_{s \to d} & \text{Banda dalla sorgente alla destinazione (bps)} \newline BW_{d \to s} & \text{Banda dalla destinazione alla sorgente (bps)} \newline BW_e & \text{Banda effettiva (bps)} \end{array}

Legenda

TpRitardo di propagazione (s)TtfRitardo di trasmissione frame (s)TtaRitardo di trasmissione ACK (s)TeRitardo dovuto ad errori (s)RTTRound Trip Time (s)TtTempo totale\begin{array}{ll} T_p & \text{Ritardo di propagazione (s)} \newline T_{tf} & \text{Ritardo di trasmissione frame (s)} \newline T_{ta} & \text{Ritardo di trasmissione ACK (s)} \newline T_{e} & \text{Ritardo dovuto ad errori (s)} \newline RTT & \text{Round Trip Time (s)} \newline T_{t} & \text{Tempo totale} \end{array}

Legenda

IIntestazione (bit)PPayload (bit)LPerdita (percentuale)tTimer (s)WFinestra (pacchetti)NfNumero di frame effettivo in una finestra (pacchetti)\begin{array}{ll} I & \text{Intestazione (bit)} \newline P & \text{Payload (bit)} \newline L & \text{Perdita (percentuale)} \newline t & \text{Timer (s)} \newline W & \text{Finestra (pacchetti)} \newline N_f & \text{Numero di frame effettivo in una finestra (pacchetti)} \end{array}

Tempi senza errori

Tp=Lunghezza da percorrereVelocitaˋ del segnale Ttf=I+PBWs→dTta=IBWd→s RTT=2⋅Tp Tt=RTT+Ttf+TtaT_p = \frac{\text{Lunghezza da percorrere}}{\text{Velocità del segnale}} \newline \space \newline T_{tf} = \frac{I + P}{BW_{s \to d}} \qquad T_{ta} = \frac{I}{BW_{d \to s}} \newline \space \newline RTT = 2 \cdot T_p \newline \space \newline T_{t} = RTT + T_{tf} + T_{ta}

Tempi in presenza di errori

Te=2⋅L⋅t Tt=RTT+Ttf+Tta+Te\begin{array}{ll} T_e = 2 \cdot L \cdot t \newline \space \newline T_{t} = RTT + T_{tf} + T_{ta} + T_e \end{array}

Banda effettiva

BWe=PTt BWe=PRTT+Ttf+Tta+Te BWe=P2⋅Tp+I+PBWs→d+IBWd→s+2⋅L⋅tBW_e = \frac{P}{T_t} \newline \space \newline BW_e = \frac{P}{RTT + T_{tf} + T_{ta} + T_e} \newline \space \newline BW_e = \frac{P}{2 \cdot T_p + \frac{I + P}{BW_{s \to d}} + \frac{I}{BW_{d \to s}} + 2 \cdot L \cdot t}

Banda effettiva con finestra (Go-Back-N)

Nf=RTTTtf {BWe=W⋅PTtse W≤Nf BWe=⌊Nf⌋⋅PTtse W>Nf\begin{array}{ll} N_f = \frac{RTT}{T_{tf}} \end{array} \newline \space \newline \begin{cases} BW_e = \frac{W \cdot P}{T_t} & \text{se } W \leq N_f \newline \space \newline BW_e = \frac{\lfloor N_f \rfloor \cdot P}{T_t} & \text{se } W > N_f \end{cases}

Protocollo stop-and-wait

Un protocollo stop-and-wait è un protocollo di comunicazione che prevede che il mittente invii un pacchetto e attenda la ricezione di un ACK prima di inviare il pacchetto successivo.

Schema

Loading diagram...

Esercizio 1

Banda(BW)=8 Mbps=8⋅106 bpsRitardo di propagazione(Tp)=10 ms=10−2 sIntestazione(I)=10 byte=80 bitBanda effettiva(BWe)=5 Mbps=5⋅106 bpsTimer(t)=100 ms=10−1 sPerdita(L)=0.01\begin{array}{lll} \text{Banda}(BW) &= 8 \text{ Mbps} &= 8 \cdot 10^6 \text{ bps} \newline \text{Ritardo di propagazione}(T_p) &= 10 \text{ ms} &= 10^{-2} \text{ s} \newline \text{Intestazione}(I) &= 10 \text{ byte} &= 80 \text{ bit} \newline \text{Banda effettiva}(BW_e) &= 5 \text{ Mbps} &= 5 \cdot 10^6 \text{ bps} \newline \text{Timer}(t) &= 100 \text{ ms} &= 10^{-1} \text{ s} \newline \text{Perdita}(L) &= 0.01 \end{array} Ritardo di trasmissione frame(Ttf)= ?Ritardo di trasmissione ACK(Tta)= ?Dimensione Payload(P)= ?\begin{array}{ll} \text{Ritardo di trasmissione frame}(T_{tf}) &= \text{ ?} \newline \text{Ritardo di trasmissione ACK}(T_{ta}) &= \text{ ?} \newline \text{Dimensione Payload}(P) &= \text{ ?} \end{array}

Formule

BWe==PRTT+Ttf+Tta+L⋅2⋅t==P2⋅Tp+I+PBW+IBW+L⋅2⋅t\begin{array}{lll} & BW_e &= \newline \newline =& \frac{P}{RTT + T_{tf} + T_{ta} + L \cdot 2 \cdot t} &= \newline \newline =& \frac{P}{2 \cdot T_p + \frac{I + P}{BW} + \frac{I}{BW} + L \cdot 2 \cdot t} \end{array}

Ricavare P

BWe(2⋅Tp+I+PBW+IBW+L⋅2⋅t)=PBWe⋅BW(2⋅Tp+I+PBW+IBW+L⋅2⋅t)=BW⋅PBWe(BW⋅2⋅Tp+I+P+I+BW⋅L⋅2⋅t)=BW⋅PBWe⋅P+2⋅BWe(BW⋅Tp+I+BW⋅L⋅t)=BW⋅P2⋅BWe(BW⋅Tp+I+BW⋅L⋅t)=BW⋅P−BWe⋅P2⋅BWe(BW⋅Tp+I+BW⋅L⋅t)=(BW−BWe)⋅P2⋅BWe(BW⋅Tp+I+BW⋅L⋅t)BW−BWe=P10⋅106(8⋅104+80+8⋅103)3⋅106=P\begin{array}{ll} BW_e(2 \cdot T_p + \frac{I + P}{BW} + \frac{I}{BW} + L \cdot 2 \cdot t) &= P \newline BW_e \cdot BW(2 \cdot T_p + \frac{I + P}{BW} + \frac{I}{BW} + L \cdot 2 \cdot t) &= BW \cdot P \newline BW_e ( BW \cdot 2 \cdot T_p + I + P + I + BW \cdot L \cdot 2 \cdot t) &= BW \cdot P \newline BW_e \cdot P + 2 \cdot BW_e ( BW \cdot T_p + I + BW \cdot L \cdot t) &= BW \cdot P \newline 2 \cdot BW_e ( BW \cdot T_p + I + BW \cdot L \cdot t) &= BW \cdot P - BW_e \cdot P \newline 2 \cdot BW_e ( BW \cdot T_p + I + BW \cdot L \cdot t) &= (BW - BW_e) \cdot P \newline \frac{2 \cdot BW_e ( BW \cdot T_p + I + BW \cdot L \cdot t)}{BW - BW_e} &= P \newline \frac{10 \cdot 10^6 ( 8 \cdot 10^4 + 80 + 8 \cdot 10^3)}{3 \cdot 10^6} &= P \end{array} P=293600 bitP=36700 byteP = 293600 \text{ bit} \newline P = 36700 \text{ byte}

Esercizio 2

Banda(BW)=80 Mbps=8⋅107 bpsRitardo di propagazione(Tp)=10 ms=10−2 sIntestazione(I)=100 byte=800 bitPayload(P)=900 byte=7200 bitACK(A)=200 byte=1600 bitTimer(t)=200 ms=2⋅10−1 sPerdita andata(Ls→d)=0.01Perdita ritorno(Ld→s)=0.02\begin{array}{lll} \text{Banda}(BW) &= 80 \text{ Mbps} &= 8 \cdot 10^7 \text{ bps} \newline \text{Ritardo di propagazione}(T_p) &= 10 \text{ ms} &= 10^{-2} \text{ s} \newline \text{Intestazione}(I) &= 100 \text{ byte} &= 800 \text{ bit} \newline \text{Payload}(P) &= 900 \text{ byte} &= 7200 \text{ bit} \newline \text{ACK}(A) &= 200 \text{ byte} &= 1600 \text{ bit} \newline \text{Timer}(t) &= 200 \text{ ms} &= 2 \cdot 10^{-1} \text{ s} \newline \text{Perdita andata}(L_{s \to d}) &= 0.01 \newline \text{Perdita ritorno}(L_{d \to s}) &= 0.02 \end{array} Banda effettiva(BWe)= ?\begin{array}{ll} \text{Banda effettiva}(BW_e) &= \text{ ?} \end{array}

Formule

Te=(Ls→d+Ld→s)⋅t=(0.01+0.02)⋅2⋅10−1=6⋅10−3 sTt=RTT+Ttf+Tta+Te=2⋅Tp+I+PBW+I+ABW+Te=(20+6)⋅10−3+800+7200+800+16008⋅107=2.613⋅10−2 s\begin{array}{llll} T_e &= (L_{s \to d} + L_{d \to s}) \cdot t &= (0.01 + 0.02) \cdot 2 \cdot 10^{-1} &= 6 \cdot 10^{-3} \text{ s} \newline \newline T_t &= RTT + T_{tf} + T_{ta} + T_e &= 2 \cdot T_p + \frac{I + P}{BW} + \frac{I + A}{BW} + T_e \newline &= (20 + 6) \cdot 10^{-3} + \frac{800 + 7200 + 800 + 1600}{8 \cdot 10^7} &= 2.613 \cdot 10^{-2} \text{ s} \end{array}

Ricavare BWe

BWe=PTtBWe=72002.613⋅10−2BWe≈2.76⋅105 bps=276 Kbps\begin{array}{ll} BW_e &= \frac{P}{T_t} \newline \newline BW_e &= \frac{7200}{2.613 \cdot 10^{-2}} \newline \newline BW_e &\approx 2.76 \cdot 10^5 \text{ bps} &= 276 \text{ Kbps} \end{array}

Protocollo go back n

Un protocollo go back n è un protocollo di comunicazione che prevede che il mittente invii un pacchetto certo numero di pacchetti e attenda la ricezione di un ACK prima di inviarne un altro. In caso di perdita di un pacchetto, il mittente invia nuovamente tutti i pacchetti successivi a quello perso.

Schema

Loading diagram...

Esercizio 1

Ritardo di propagazione(Tp)=10 ms=10−2 sBanda(BW)=100 Mbps=108 bpsIntestazione(I)=100 byte=800 bitDimensione payload(P)=1000 byte=8000 bitWindow(W)=20\begin{array}{lll} \text{Ritardo di propagazione}(T_p) &= 10 \text{ ms} &= 10^{-2} \text{ s} \newline \text{Banda}(BW) &= 100 \text{ Mbps} &= 10^8 \text{ bps} \newline \text{Intestazione}(I) &= 100 \text{ byte} &= 800 \text{ bit} \newline \text{Dimensione payload}(P) &= 1000 \text{ byte} &= 8000 \text{ bit} \newline \text{Window}(W) &= 20 \end{array} Lunghezza di banda effettiva(BWe)= ?\text{Lunghezza di banda effettiva}(BW_e) = \text{ ?}

Formule

Trasferimento frame(Ttf)=I+PBW=800+8000108=8.8⋅10−5 sTrasferimento ACK(Tta)=IBW=800108=8⋅10−6 sNumero di frame in RTT=2⋅TpTf=2⋅10−28.8⋅10−5≈227.27\begin{array}{lll} \text{Trasferimento frame}(T_{tf}) &= \frac{I + P}{BW} &= \frac{800 + 8000}{10^8} &= 8.8 \cdot 10^{-5} \text{ s} \newline \newline \text{Trasferimento ACK}(T_{ta}) &= \frac{I}{BW} &= \frac{800}{10^8} &= 8 \cdot 10^{-6} \text{ s} \newline \newline \text{Numero di frame in } RTT &= \frac{2 \cdot T_p}{T_f} &= \frac{2 \cdot 10^{-2}}{8.8 \cdot 10^{-5}} &\approx 227.27 \end{array}

Ricavare BWe

Poiché il numero di frame che sarebbe possibile inviare nell'RTT è maggiore o uguale alla finestra massima stabilita, prendiamo in considerazione quella: 20.

BWe=P⋅WTt=P⋅W2⋅Tp+Ttf+TtaBWe=8000⋅202⋅10−2+8.8⋅10−5+8⋅10−6BWe≈8⋅106 bps=8 Mbps\begin{array}{lll} BW_e &= \frac{P \cdot W}{T_t} &= \frac{P \cdot W}{2 \cdot T_p + T_{tf} + T_{ta}} \newline \newline BW_e &= \frac{8000 \cdot 20}{2 \cdot 10^{-2} + 8.8 \cdot 10^{-5} + 8 \cdot 10^{-6}} \newline \newline BW_e &\approx 8 \cdot 10^6 \text{ bps} &= 8 \text{ Mbps} \end{array}

Esercizio 2

Window(W)=5Band Width(BW)=12 Mbit/s=12⋅106 bit/sIntestazione(I)=100 byte=800 bitPayLoad(P)=900 byte=7200 bitLunghezza canale(L)=100 km=105 mVelocitaˋ del segnale(V)=200000 km/s=2⋅108 m/s\begin{array}{lll} \text{Window}(W) &= 5 \newline \text{Band Width}(BW) &= 12 \text{ Mbit/s} &= 12 \cdot 10^6 \text{ bit/s} \newline \text{Intestazione}(I) &= 100 \text{ byte} &= 800 \text{ bit} \newline \text{PayLoad}(P) &= 900 \text{ byte} &= 7200 \text{ bit} \newline \text{Lunghezza canale}(L) &= 100 \text{ km} &= 10^5 \text{ m} \newline \text{Velocità del segnale}(V) &= 200000 \text{ km/s} &= 2 \cdot 10^8 \text{ m/s} \end{array} Lunghezza di banda effettiva(BWe)= ?\text{Lunghezza di banda effettiva}(BW_e) = \text{ ?}

Formule

Tp=LV=1052⋅108=5⋅10−4 sTtf=I+PBW=800+720012⋅106≈6⋅10−4 sTta=IBW=80012⋅106≈6⋅10−5 sTt=2⋅Tp+Ttg+Tta=10−3+6.6⋅10−4=1.66⋅10−3 sNf=⌊2⋅TpTtf⌋=⌊10−36⋅10−4⌋≈⌊1.6⌋=1\begin{array}{llll} T_p &= \frac{L}{V} &= \frac{10^5}{2 \cdot 10^8} &= 5 \cdot 10^{-4} \text{ s} \newline \newline T_{tf} &= \frac{I + P}{BW} &= \frac{800 + 7200}{12 \cdot 10^6} &\approx 6 \cdot 10^{-4} \text{ s} \newline \newline T_{ta} &= \frac{I}{BW} &= \frac{800}{12 \cdot 10^6} &\approx 6 \cdot 10^{-5} \text{ s} \newline \newline T_t &= 2 \cdot T_p + T_{tg} + T_{ta} &= 10^{-3} + 6.6 \cdot 10^{-4} &= 1.66 \cdot 10^{-3} \text{ s} \newline \newline N_f &= \left\lfloor \frac{2 \cdot T_p}{T_{tf}} \right\rfloor &= \left\lfloor \frac{10^{-3}}{6 \cdot 10^{-4}} \right\rfloor &\approx \lfloor 1.6 \rfloor = 1 \end{array}

Ricavare BWe

Poiché il numero di frame che è possibile inviare nell'RTT è minore della finestra massima stabilita, prendiamo in considerazione il più piccolo: 1.

BWe=P⋅1TtBWe=7200⋅11.66⋅10−3BWe≈4.33⋅106 bps=4.33 Mbps\begin{array}{lll} BW_e &= \frac{P \cdot 1}{T_t} \newline \newline BW_e &= \frac{7200 \cdot 1}{1.66 \cdot 10^{-3}} \newline \newline BW_e &\approx 4.33 \cdot 10^6 \text{ bps} &= 4.33 \text{ Mbps} \end{array}

Esercizio 3

Ritardo di propagazione(Tp)=100 ms=10−1 sBand Width andata(BWs→d)=1 Mbit/s=106 bit/sBand Width ritorno(BWd→s)=10 Kbit/s=104 bit/sIntestazione(I)=1000 byte=8000 bitPayLoad(P)=9000 byte=72000 bitACK(A)=100 byte=800 bit\begin{array}{lll} \text{Ritardo di propagazione}(T_p) &= 100 \text{ ms} &= 10^{-1} \text{ s} \newline \text{Band Width andata}(BW_{s \to d}) &= 1 \text{ Mbit/s} &= 10^6 \text{ bit/s} \newline \text{Band Width ritorno}(BW_{d \to s}) &= 10 \text{ Kbit/s} &= 10^4 \text{ bit/s} \newline \text{Intestazione}(I) &= 1000 \text{ byte} &= 8000 \text{ bit} \newline \text{PayLoad}(P) &= 9000 \text{ byte} &= 72000 \text{ bit} \newline \text{ACK}(A) &= 100 \text{ byte} &= 800 \text{ bit} \end{array}

Con la condizione che la banda minima a livello superiore sia maggiore di 500 Kbps (500000 bps), calcolare la finestra di trasmissione.

Window(W)= ?\text{Window}(W) = \text{ ?}

Formule

Ttf=I+PBWs→d=8000+72000106=0.08 sTta=I+ABWd→s=8000+800104=0.88 sTt=2⋅Tp+Ttf+Tta=0.2+0.08+0.88=1.16 s\begin{array}{llll} T_{tf} &= \frac{I + P}{BW_{s \to d}} &= \frac{8000 + 72000}{10^6} &= 0.08 \text{ s} \newline \newline T_{ta} &= \frac{I + A}{BW_{d \to s}} &= \frac{8000 + 800}{10^4} &= 0.88 \text{ s} \newline \newline T_t &= 2 \cdot T_p + T_{tf} + T_{ta} &= 0.2 + 0.08 + 0.88 &= 1.16 \text{ s} \end{array}

Ricavare W

BWe=W⋅PTt≥500000W≥⌈500000⋅TtP⌉W≥⌈500000⋅1.1672000⌉=9\begin{array}{lll} BW_e &= \frac{W \cdot P}{T_t} &\ge 500000 \newline \newline W &\ge \left\lceil \frac{500000 \cdot T_t}{P} \right\rceil \newline \newline W &\ge \left\lceil \frac{500000 \cdot 1.16}{72000} \right\rceil &= 9 \end{array}

Cyclic Redundancy Check (CRC)

Il CRC è un codice di controllo a ridondanza ciclica che permette di rilevare errori di trasmissione.
Il CRC viene calcolato dal mittente e viene inviato insieme al messaggio. Il destinatario calcola il CRC del messaggio ricevuto e lo confronta con quello ricevuto.
Se i due CRC coincidono, il messaggio è stato trasmesso correttamente.

Esercizio 1

M=101101G=1101∣G∣−1=4−1=3M = 101101 \quad G = 1101 \quad |G| - 1 = 4 - 1 = 3

Calcolare il CRC.

101101 0001101011001 000  1101000011 000        11 01000000 010⏟resto\begin{array}{ll} 101101 \space 000 \newline 1101 \newline 011001 \space 000 \newline \space\space 1101 \newline 000011 \space 000 \newline \space\space \space\space \space\space \space\space 11 \space 01 \newline 000000 \space \underbrace{010}_{\text{resto}} \end{array}

Esercizio 2

M=1101101G=11010∣G∣−1=4M = 1101101 \qquad G = 11010 \qquad |G| - 1 = 4

Calcolare il CRC.

1101101 0000110100000101 0000        110 100000011 1000          11 0100000000 1100⏟resto\begin{array}{ll} 1101101 \space 0000 \newline 11010 \newline 0000101 \space 0000 \newline \space\space \space\space \space\space \space\space 110 \space 10 \newline 0000011 \space 1000 \newline \space\space \space\space \space\space \space\space \space\space 11 \space 010 \newline 0000000 \space \underbrace{1100}_{\text{resto}} \end{array}

Esercizio 3

M=101001 011G=1001∣G∣−1=3M = 101001 \space 011 \qquad G = 1001 \qquad |G| - 1 = 3

Verificare se il messaggio è stato trasmesso correttamente.

101001 0111001001101 011    1001000100 011      100 1000000 111≠0→errore\begin{array}{ll} 101001 \space 011 \newline 1001 \newline 001101 \space 011 \newline \space\space \space\space 1001 \newline 000100 \space 011 \newline \space\space \space\space \space\space 100 \space 1 \newline 000000 \space 111 & \ne 0 \to \text{errore} \end{array}

Esercizio 4

M=101101 0000G=11011∣G∣−1=4M = 101101 \space 0000 \qquad G = 11011 \qquad |G| - 1 = 4

Verificare se il messaggio è stato trasmesso correttamente.

101101 000011011011011 0000  11011000000 0000=0→corretto\begin{array}{ll} 101101 \space 0000 \newline 11011 \newline 011011 \space 0000 \newline \space\space 11011 \newline 000000 \space 0000 & = 0 \to \text{corretto} \end{array}

Esercizio 5

M=1001 110G=1011∣G∣−1=3M = 1001 \space 110 \qquad G = 1011 \qquad |G| - 1 = 3

Verificare se il messaggio è stato trasmesso correttamente.

1001 11010110010 110    10 110000 000=0→corretto\begin{array}{ll} 1001 \space 110 \newline 1011 \newline 0010 \space 110 \newline \space\space \space\space 10 \space 11 \newline 0000 \space 000 & = 0 \to \text{corretto} \end{array}

Codifica di Hamming

La codifica di Hamming è un codice di correzione degli errori che permette di correggere errori su un singolo bit e di rilevare quelli su due.

Esercizio 1

Sia data la seguente word:

1000101101011110110001011010111101

Sapendo che vi sono state aggiunte la ridondanza CRC4 e successivamente la ridondanza della codifica di Hamming per la correzione di un singolo bit, descrivere l’operazione che il ricevente andrà fare per determinare se la word ricevuta sia corretta o, in caso di un singolo errore, correggerlo.
Il generatore utilizzato è x4+x3+1x^4 + x^3 + 1.
Per la codifica di Hamming i bit vanno considerati da sinistra verso destra.

10001011010111101b1=d3⊕d5⊕d7⊕d9⊕d11⊕d13⊕d15⊕d17==0⊕1⊕1⊕0⊕0⊕1⊕1⊕1=1b2=d3⊕d6⊕d7⊕d10⊕d11⊕d14⊕d15==0⊕0⊕1⊕1⊕0⊕1⊕1=0b3=d5⊕d6⊕d7⊕d12⊕d13⊕d14⊕d15==1⊕0⊕1⊕1⊕1⊕1⊕1=0b4=d9⊕d10⊕d11⊕d12⊕d13⊕d14⊕d15==0⊕1⊕0⊕1⊕1⊕1⊕1=1b5=d17=1{\color{blue} 10}0{\color{blue} 0}101 {\color{blue} 1}0101111{\color{blue} 0}1 \newline \begin{array}{ll} \newline b_1 &= d_3 \oplus d_5 \oplus d_7 \oplus d_9 \oplus d_{11} \oplus d_{13} \oplus d_{15} \oplus d_{17} = \newline &=0 \oplus 1 \oplus 1 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 1 = {\color{green} 1} \newline b_2 &= d_3 \oplus d_6 \oplus d_7 \oplus d_{10} \oplus d_{11} \oplus d_{14} \oplus d_{15} = \newline &= 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 1 = {\color{green} 0} \newline b_3 &= d_5 \oplus d_6 \oplus d_7 \oplus d_{12} \oplus d_{13} \oplus d_{14} \oplus d_{15} = \newline &= 1 \oplus 0 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = {\color{green} 0} \newline b_4 &= d_9 \oplus d_{10} \oplus d_{11} \oplus d_{12} \oplus d_{13} \oplus d_{14} \oplus d_{15} = \newline &= 0 \oplus 1 \oplus 0 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = {\color{green} 1} \newline b_5 &= d_{17} = {\color{red} 1} \end{array}

Esercizio 1

Il codice di hamming indica che è avvenuto un errore nel bit 16, che però è un bit di ridondanza. L'errore non può essere il bit 17 in quanto è "coperto" anche dal bit di controllo 1.
Rimuoviamo quindi tutti i bit aggiunti dalla codifica. Rimane la word:

010101011111010101011111

Applichiamo quindi il CRC4 per verificare se ci sono stati errori di trasmissione con il generatore x4+x3+1x^4 + x^3 + 1.

1100111001

Esercizio 1

M=01010101 1111G=11001∣G∣−1=4M = 01010101 \space 1111 \qquad G = 11001 \qquad |G| - 1 = 4

01010101 1111  1100100110001 1111    1100100000011 1111            11 00100000000 1101≠0→errore\begin{array}{ll} 01010101 \space 1111 \newline \space\space 11001 \newline 00110001 \space 1111 \newline \space\space \space\space 11001 \newline 00000011 \space 1111 \newline \space\space \space\space \space\space \space\space \space\space \space\space 11 \space 001 \newline 00000000 \space 1101 & \ne 0 \to \text{errore} \end{array}

Distanza di Hamming

La distanza di Hamming è la distanza tra due parole di uguale lunghezza, definita come il numero di posizioni in cui le due parole differiscono.

Esercizio 1

Fanno parte del dizionario tutte le parole di 3 bit dove i primi 2 vengono usati per trasferire i dati e l'ultimo viene usato per il controllo di parità.

Parole valideParole non valide000001011010101100110111\begin{array}{ll} \text{Parole valide} & \text{Parole non valide} \newline 000 & 001 \newline 011 & 010 \newline 101 & 100 \newline 110 & 111 \end{array}

Distanza minima

La distanza minima è la distanza più piccola tra tutte le coppie di parole diverse del dizionario.

[0000111011100000222011202210122021102220]\begin{bmatrix} & 000 & 011 & 101 & 110 \newline 000 & 0 & 2 & 2 & 2 \newline 011 & 2 & 0 & 2 & 2 \newline 101 & 2 & 2 & 0 & 2 \newline 110 & 2 & 2 & 2 & 0 \end{bmatrix}

La distanza più piccola fra parole diverse è 2, quindi la distanza minima è 2.