SCIENZE E TECNOLOGIE INFORMATICHE

[:it]

David Hettinger

La semplice rilevazione dell’errore fa sì che si richieda la ritrasmissione del pacchetto ossia

ARQ che è acronimo di Automatic Request.

Caratteristiche del canale ARQ:

• canale bidimensionale
• si adotti un protocollo tramite cui avviene il colloquio fra trasmettitore e ricevitore.

Il trasmettitore:

• suddivide il messaggio che riceve dalla sorgente in blocchi di k bit  memorizza ogni blocco prima della trasmissione
• per ogni blocco si calcola il CRC, lo si accoda ai bit informativi e invia il blocco codificato di n bit sul canale
• attente una risposta dal ricevitore

Il ricevitore:

• controlla la sequenza di bit contenuta in un blocco codificato
• se non rileva errori invia al trasmettitore un riscontro positivo ACK (ACKnowledge); il trasmettitore cancella dalla propria memoria i blocchi giunti correttamente al ricevitore.
• se il controllo dà esito negativo, (NACK Negatie Acknowledge), si richiede al trasmettitore di ritrasmettere il singolo pacchetto.

Esso può andare bene quando la ritrasmissione del messaggio è ininfluente considerando la velocità di trasmissione del mezzo, la sua banda e la capacità di elaborazione del segnale in entrata ed in uscita.

Nel caso in cui si volesse oltre che rilevare l’errore anche cercare di correggerlo, senza richiedere la ritrasmissione allora si parla di:

FEC acronimo della sigla inglese Forward Error Correction.

Uno stesso tipo di codice può essere utilizzato per rivelare o per correggere errori a seconda dell’architettura del sistema di codifica/decodifica utilizzato

Inoltre entrambi i codici inseriscono della ridondanza nel messaggio trasmesso.[:]

[:it]

David Hettinger

La codifica di canale prepara il pacchetto di bit per la trasmissione sulla linea.

Tale codifica deve permettere al ricevente di verificare se i bit trasmessi siano uguali a quelli ricevuti e nel caso o correggerli o richiedere la ritrasmissione del pacchetto.

Si aggiungono dei bit ridondanti, che consentono, una volta giunti a destinazione, di verificare se ci sono stati errori.

Controllo di parità

Il Controllo di parità (VRC Vertical Redundancy Check) consiste nell’aggiungere un bit supplementare (detto bit di parità) ad un certo numero di bit di dati chiamato code word (generalmente 7 bit, per formare un byte con il bit di parità) il cui valore (0 o 1) è uguale al numero totale di bit a 1 cioè pari.

Per essere più chiari: in una sequenza di 8 bit il numero di 1 presenti deve essere sempre in numero pari e chi fa jolly è sempre il primo posto che rimane 0 se il numero di 1 nelle altre sette posizioni è pari mentre diventa 1 se il numero d bit nelle altre sette posizioni è dispari.

Prendiamo l’esempio seguente:

In questo esempio, il numero di bit di dati a 1 è pari, il bit di parità è quindi posto a 0. Nell’esempio seguente, invece, dato che i bit di dati sono dispari, i bit di parità è a 1:

Immaginiamo ormai che dopo la trasmissione il bit di peso minore (il bit posto a destra) del byte precedente sia vittima di un’interferenza:

Il bit di parità non corrisponde più alla parità del byte: un errore è rilevato.

Tuttavia, se due bit (o un numero pari di bit) arriva a modificarsi simultaneamente durante il trasporto dei dati, nessun errore sarà allora rilevato:

Il sistema di controllo di parità rileva solo gli errori in numero dispari, pari quindi solamente al 50% degli errori totali. Questo sistema di rilevamento degli errori possiede anche l’inconveniente maggiore di non correggere gli errori rilevati (il solo mezzo è di esigere la ritrasmissione del byte errato).

CRC

Tra gli algoritmi più conosciuti è il CRC ossia Cyclic Redundancy Check che contiene degli elementi ridondanti rispetto al frame, che permettono di rilevare gli errori, ma anche di ripararli.

Il CRC prevede la generazione di una stringa di bit di controllo che viene normalmente trasmessa assieme ai dati.

Si deve dividere il frame di partenza per un frame generatore. Al frame di partenza si concatena il resto della divisione e lo trasmette.

Il ricevente divide il frame ricevuto per il generatore e se il resto è nullo allora il pacchetto ricevuto è privo di errori.

I codici generatori sono conosciuti sia dal ricevente che dal generatore.

Ad esempio si vuole trasmettere

0xa3 0xac  con il codice generatore 0x1a.

ossia in binario

1010 0011 1010 1100 con codice generatore 1101 0

Si aggiungono tanti bit al frame di partenza quanti sono quelli del divisore – 1.

1010 0011 1010 1100 0000 questo è il frame di partenza

• Si valuta che il divisore ci sta nel dividendo non quando il dividendo è realmente maggiore del divisore, ma quando ha lo stesso ordine di grandezza, vale a dire quando il suo bit più significativo vale 1.
• La sottrazione per ridurre il dividendo và fatta senza riporti, quindi si riduce ad un’operazione di Exclusive Or (XOR).

Ad esempio i primi passi sono:

1010 0011 1010 1100 0000
1101 0
0111 0

Abbiamo eseguito l’XOR tra i primi bit del dividendo ed il divisore, ottenendo il primo resto.

1010 0011 1010 1100 0000
1101 0|
0111 00

quindi si effettua la somma, se la prima cifra non è 1 non si porta giù un’altra cifra.

Alla fine si troverà come resto:

1010

ed il messaggio o frame trasmesso sarà:

1010 0011 1010 1100 1010.

I polinomi generatori più frequentemente usati sono:

CCITT-32: 0x04C11DB7 (ethernet)= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + \
x8 + x7 + x5 + x4 + x2 + x + 1

CCITT-16: 0x1021 = x16 + x12 + x5 + 1

CRC-16: 0x8005 = x16 + x15 + x2 + 1

XMODEM-16: 0x8408 = x16 + x15 + x10 + x3

12bit-CRC: 0x80f = x12 + x11 + x3 + x2 + x + 1

10bit-CRC: 0x233 = x10 + x9 + x5 + x4 + x + 1

8bit-CRC: 0x07 = x8 + x2 + x + 1

[:]

[:it]Lo schema di un canale trasmissivo può essere visto come segue:

La codifica di sorgente ha il compito di trasformare un messaggio scritto ad esempio in una tastiera in una sequenza di bit.

Tale trasformazione può essere a lunghezza fissa (codice ASCII) o a lunghezza variabile (ad esempio codifica di Huffmann)

Ci sono i pregi e i difetti per entrambi i tipi di decodifica.

Codice ASCII.

Esso permette la codifica dei caratteri in 8 bit. Utilizzando la definizione di distribuzione a ripetizione avendo un alfabeto di 2 cifre per 8 bit in tutto si ha combinazioni diverse.

Codice Huffmann

Il codice di Huffman costruisce una tabella di codifica-decodifica utilizzando un numero di bit differente a seconda della probabilità che si ha di trovare uno specifico valore.

Utilizzando meno bit per i codici più probabili, e più bit per quelli meno diffusi, si può risparmiare memoria.

E’ il codice migliore per ottimizzare l’entropia, è il metodo più efficiente per la compressine dei dati. (pkzip, jpeg, mp3).

Per creare la giusta codifica si usa uno schema ad albero

Ecco la spiegazione dell’algoritmo:

• si ordinano i simboli in ordine decrescente di probabilità
• i due valori più piccoli creano le prime due foglie (leaf node) e si sommano creando il primo nodo. A ramo di sinistra si associa sempre il valore 0 ed al ramo di destra il valore 1.
• si ordinano nuovamente i valori.
• i due valori più piccoli si sommano creando ancora un nodo, Al ramo di sinistra si associa il valore 1, al ramo di destra il valore 0.
• il processo continua finchè non vi sono più simboli o probabilità associati al relativo simbolo.

Esempio

Sia dato un file formato da 120 caratteri con la seguente frequenza di caratteri (attenzione parlare di frequenza o probabilità di un carattere è uguale)

Se si usasse un codice a lunghezza fissa si dovrebbe usare una stringa di bit lunga 3 in quanto essa è l’unica che possa contenere la codifica di 6 caratteri, infatti

Siccome vi sono 120 caratteri da trasmettere bit

Utilizzando invece la codifica a lunghezza variabile si ha:

Bastano bit

Spiegazione di come si crea il codice variabile.

• ordino i valori dal meno frequente al più frequente:

• sommo gli ultimi due
• creo due foglie con il ramo 0 a sinistra 0 ed il ramo 1 a destra
• ordino la sequenza:

• sommo gli ultimi due
• creo due foglie con il ramo 0 a sinistra e il ramo 1 a destra
• ordino la sequenza
• sommo gli ultimi due
• creo un nuovo nodo
• ordino la sequenza

• sommo gli ultimi due
• creo un nuovo nodo
• ordino la sequenza

• sommo gli ultimi 2
• creo l’ultimo nodo

Adesso come si legge il codice?

• o partendo dal basso e poi invertendo i bit: ad esempio f: 0011 lo inverto 1100
• o partendo dall’alto (root) ed arrivando a tutte le radici

Come avviene la decodifica?

Siccome nessuna parola codice è prefisso di un’altra, la prima parola codice del file codificato risulta univocamente determinata.

Ad esempio trasmetto 0101100, comincio a leggere da sinistra verso destra. Prendo i primi 4 caratteri, non corrisponde a nessuna cifra, prendo i primi tre ancora nessuna, prendo il primo e corrisponde ad a, elimino lo 0 rimane

101100

1011 non corrisponde a nessun carattere,

101 corrisponde alla b

rimane 100 che corrisponde alla c

per cui il messaggio è abc.[:]

[:it]

Franz Marc

La sorgente aleatoria numerica viene anche definita una sorgente aleatoria discreta, essere senza memoria significa che i simboli sono indipendenti ed identicamente distribuiti estratti da un alfabeto A di dimensione finita L.

Quindi ogni simbolo ha una certa probabilità di essere emesso.

In inglese esso è definito come:

Discrete Memoryless source, DMS[:]

[:it]

Charles S. Raleigh

Tutti questi esercizi possono essere risolti mediante l’applicazione delle relazioni definite nei posti precedenti sulla definizione di informazione, entropia, lunghezza di un messaggio, ridondanza.

1. Una sorgente discreta emette i simboli aventi probabilità rispettivamente . Determinare l’informazione associata a ciascun simbolo e l’entropia della sorgente
2.  Calcola la ridondanza di una sorgente binaria discreta le cui probabilità di emissione sono
3. Una sorgente discreta emette 5 simboli con probabilità . a) Calcola la ridondanza della sorgente b) La lunghezza del codice necessaria ad effettuare una corretta codifica della sorgente.
4. Si ha una sorgente di 6 simboli discreti con ridondanza ; calcola: a) L’entropia b) la lunghezza del codice c) l’efficienza della codifica
5. Una sorgente ha alfabeto di n=4 simboli con le seguenti probabilità di emissione: simbolo probabilità 0.38 0,25 0,22 0,15 a) Calcola l’entropia della sorgente b)Calcola il contenuto informativo dei due seguenti messaggi: e
6. Una sorgente ha un alfabeto di n=7 simboli con le seguenti probabilità di emissione: simbolo probabilità codice 0,32 00 0,23 01 0,13 100 0,1 101 0,09 110 0,08 1110 0,05 1111 Calcola la lunghezza media del codice
7. Una sorgente discreta emette 3 simboli statisticamente indipendenti; sapendo che , calcolare la ridondanza .
8. Un alfabeto è costituito da 2 simboli equiprobabili. IL tempo impiegato per trasmettere il primo simbolo è mentre , calcolare: a) l’entropia della sorgente b) il tempo medio per trasmettere un simbolo c) la velocità di trasmissione

 [:]

[:it]Anno2015

Anno2017[:]

[:it]

Vladimir Kush

La lunghezza media di un codice è data da quanti simboli in media sono necessari per mandare un messaggio con tali simboli ossia:

dove con è il numero di simboli.

oppure se si conosce la lunghezza del codice:

Per efficienza si intende:

Per ridondanza si intende quindi

ossia quanto più una sorgente ha una grande entropia (ossia fornisce molte informazioni) con un alfabeto molto basso, minore è la ridondanza ossia la necessità di trasmettere segnali simili nel canale trasmissivo.[:]

[:it]

Vladimir Kush

Che cos’è l’entropia di una sorgente?

E’ il massimo grado di informazione che può darci un opportuno codice.

In fisica l’entropia fornisce il grado di disordine di un particolare sistema, nella teoria dell’informazione quanto più un codice ha un’elevata entropia quanta più informazione esso potrà portare.

Nella teoria della probabilità, quando due eventi sono statisticamente indipendenti la probabilità che uno accada in seguito all’altro è dato dal prodotto delle loro probabilità ossia: (principio delle probabilità composte)

L’unica funzione matematica che dal prodotto permette di passare alla somma è ancora il logaritmo per cui esso compare ancora nella definizione di entropia:

L’unità di misura dell’entropia è il bit/carattere.

La velocità di trasmissione viene definita non come la frequenza con cui si trasmette ma come il prodotto tra l’entropia e la frequenza dei simboli emessi.[:]

[:it]

Vladimir Kush

L’informazione, nell’ambito delle telecomunicazioni,  viene definita come la riduzione di incertezza che si poteva avere a priori sul simbolo trasmesso.

Sembra un panegirico ma, in realtà, il concetto è che se io trasmetto sempre un solo segnale sempre uguale, la probabilità di riceverlo è sempre 1. Ma tale fatto significa anche che l’informazione trasmessa è nulla.

Per trasmettere un’informazione vi è bisogno che si modifichi uno stato da luce a buio o viceversa; si pensi ai solo caratteri morse: per comunicare un messaggio, ossia un’informazione, si alternano i punti con le linee in un’opportuna combinazione.

Per dare una definizione che possa essere misurabile si utilizza la funzione logaritmo perché è l’unica che quando il suo argomento vale 1, il suo valore va a zero ed inoltre lo si caperà ancora di più quando si definisce l’entropia.

dove con si intende la probabilità con cui quel simbolo possa presentarsi.

Se la base del logaritmo è:

• 2 l’informazione si misura in bit
• 10 l’informazione si misura in hartley
• e (numero di Eulero) l’informazione si misura in nat

[:en]trasmesso e viene definita come la riduzione di incertezza che si poteva avere a priori sul simbolo trasmesso.
Sembra un panegirico ma, in realtà, il concetto è che se io trasmetto sempre un solo segnale sempre uguale, la probabilità di riceverlo è sempre 1. Ma tale fatto significa anche che l’informazione trasmessa è nulla.
Per trasmettere un’informazione vi è bisogno che si modifichi uno stato da luce a buio o viceversa; si pensi ai solo caratteri morse: per comunicare un messaggio, ossia un’informazione, si alternano i punti con le linee in un’opportuna combinazione.
Per dare una definizione che possa essere misurabile si utilizza la funzione logaritmo perché è l’unica che quando il suo argomento vale 1, il suo valore va a zero ed inoltre lo si caperà ancora di più quando si definisce l’entropia.

dove con si intende la probabilità con cui quel simbolo possa presentarsi.
Se la base del logaritmo è:
2 l’informazione si misura in bit
10 l’informazione si misura in hartley
e (numero di Eulero) l’informazione si misura in nat[:de]trasmesso e viene definita come la riduzione di incertezza che si poteva avere a priori sul simbolo trasmesso.
Sembra un panegirico ma, in realtà, il concetto è che se io trasmetto sempre un solo segnale sempre uguale, la probabilità di riceverlo è sempre 1. Ma tale fatto significa anche che l’informazione trasmessa è nulla.
Per trasmettere un’informazione vi è bisogno che si modifichi uno stato da luce a buio o viceversa; si pensi ai solo caratteri morse: per comunicare un messaggio, ossia un’informazione, si alternano i punti con le linee in un’opportuna combinazione.
Per dare una definizione che possa essere misurabile si utilizza la funzione logaritmo perché è l’unica che quando il suo argomento vale 1, il suo valore va a zero ed inoltre lo si caperà ancora di più quando si definisce l’entropia.

dove con si intende la probabilità con cui quel simbolo possa presentarsi.
Se la base del logaritmo è:
2 l’informazione si misura in bit
10 l’informazione si misura in hartley
e (numero di Eulero) l’informazione si misura in nat[:]

[:it]

1. Lanciando due monete qual è la probabilità di ottenere due teste?
2. Si lanciano due dadi. Trova la probabilità che escano due 3; che escano un 3 e un 4; che escano due numeri pari.
3. Calcola la probabilità che lanciando una moneta esca testa
4. Calcola la probabilità che lanciando 1 dado esca il numero 1.
5. Calcola la probabilità che lanciando 1 dado esca un numero divisibile per 2
6. Determina la probabilità che, lanciando 3 volte di seguito 1 moneta, si verifichi l’evento “esca almeno una croce”, sapendo che il primo lancio ha dato testa.
7. Da un’urna contenente 9 palline nere e 7 bianche si estraggono successivamente 3 palline, rimettendo ogni volta nell’urna la pallina estratta. Qual è la probabilità che siano tutte e tre nere? Che siano tutte e 3 bianche? Che siano le prime 2 bianche e la terza nera? Che siano  bianche e 1 nera?	;;;

 [:]