Codifiche TeoriaCodifica di sorgenteCodifica di canaleCodifica di lineaCodifiche esercizi

(1)

Codifiche Teoria

Codifica di sorgente

Codifica di canale Codifica di linea Codifiche esercizi

Codifica di sorgente

Lo scopo è quello di codificare il messaggio da trasmettere con il minore numero possibile di bit.

Così facendo si risparmia spazio di memoria e si aumenta la velocità di bit che si inviano lungo il canale.

Compressione

Immaginiamo di dover trasportare un centinaio di palloncini per addobbare una sala, se sono già gonfi è praticamente impossibile trasportarli su un'automobile, bisognerà necessariamente sgonfiarli prima di caricarli, e rigonfiarli nuovamente una volta giunti a destinazione. Quello appena illustrato altro non è che il concetto di compressione dati, basta sostituire i palloncini con programmi o file e la macchina con gli strumenti di internet o con i dispositivi di memorizzazione, veloci ma limitati per quanto riguarda lo "spazio" a disposizione.

L’algoritmo RLE

Run Lenght Encoding ( Codifica a lunghezza di sequenza = serie ripetuta di caratteri )

Un esempio di compressione è la trasmissione di dati tramite FAX, in cui lo scanner converte la pagina in sequenze di bit, che indicano dove si trovano le aree di scritto e dove quelle bianche. In genere si usa una risoluzione abbastanza elevata, perciò una semplice A diventa una lunga sequenza di simboli uguali (vedi Figura ).

9 (zeri), 1 (uno), 6 + 8=14 (zeri ) …. 1 (uno), 8 (zeri),1(uno ), 2 (zeri).

Altro esempio:

Comprimere la stringa "AAAAAABBBCCCCCCCDD" con l’algoritmo RLE Soluzione:

AAAAAABBBCCCCCCCDD à 6A3B7C2D Stringa originale = 18 Byte

Stringa compressa = 8 Byte Algoritmi lossless e lossy

Troviamo due principali tipi di algoritmi di compressione dati: gli algoritmi lossless e quelli lossy. Come suggerisce il nome, la compressione lossless conserva i dati originali in modo da poterne riottenere una copia esatta, mentre la compressione lossy permette alcuni cambiamenti rispetto ai dati originali.

Chiariamo ora i dettagli di questi tipi di compressione

Supponiamo di dover comprimere un testo costituito dalla sequenza "ABAAABCDDD" un algoritmo di compressione "lossless" fa si che dopo le operazioni di compressione/decompressione la sequenza rimanga intatta, ovvero, dopo la decompressione, ritroveremo la stessa sequenza

"ABAAABCDDD".

La compressione lossless è comunemente usata per la compressione di dati, quali applicazioni eseguibili, testo o database, che devono essere ripristinati nello stato originale.

Per comprimere dati come il suono o le immagini, dove una perdita di qualità potrebbe non essere notata viene usata la compressione lossy . Gli algoritmi di compressione lossy quindi, sacrificano parte dei dettagli contenuti, ad esempio in un'immagine, in favore di un maggiore rapporto di compressione.

L'immagine ricostruita decomprimendo il file inganna l'occhio, ma contiene notevoli differenze. Solitamente tali differenze non risultano percettibili, in quanto la parte di informazione persa è comunque quella che l'utente non avrebbe notato. Eliminando, perciò, alcuni dettagli di un'immagine non la deterioreremo.

Come esempio si considerino le due immagini seguenti in bianco e nero.

ingcasanof

Profilo Blog Sito Foto Amici

Community Esplora

(2)

256 grigi 64 grigi

L'immagine di destra utilizza 256 – 64 = 192 colori in meno di quella di sinistra ma sembrano uguali.

Consideriamo un libro scritto in italiano, sicuramente ci sarà un'alta frequenza nell'uso della lettera a e una bassa della z. Si potrebbe perciò pensare di comprimere il testo usando codici binari molto brevi per la a e più lunghi per la z.

Algoritmo di Shannon-Fano

Si abbia per semplicità un alfabeto di cinque simboli O, R, L, G, I.

Si supponga che nella frase da comprimere, formata da 39 caratteri, vi siano 15 O, 7 R, 6 L,6 G e 5 I.

Si divide la tabella in due parti in modo che contengano grossomodo la stessa somma delle occorrenze. Ad una metà si attribuisce il bit zero, all’altra il bit 1.

Simbolo Occorrenze Prima divisione

O 15 15 + 7 = 22

R 7

0

L 6 6 + 6 + 5 = 17

0

R 7 1

L 6 1

1 1

0

G 6 1

1

0

I 5 1

(3)

La codifica risulta pertanto:

Simbolo Parola di Codice

O 0 0

R 0 1

L 1 0

G 1 1 0

I 1 1 1

Decodificare il seguente messaggio:

O R O L O G I O

0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0

Per decodificare il messaggio si ragiona così :

IL primo bit vale zero, potrebbe trattarsi della lettera O o R.

Il secondo bit vale zero. Si tratta certamente della lettera O.

Il terzo bit vale zero, potrebbe trattarsi della lettera O o R.

Il quarto bit vale uno. Si tratta certamente della lettera R.

Il quinto bit vale 0, potrebbe trattarsi della lettera O o R.

Il sesto bit vale zero. Si tratta certamente della lettera O.

Il settimo bit vale uno, potrebbe trattarsi della lettera L o G o I.

L’ottavo bit vale zero. Si tratta certamente della lettera L.

Procedendo come in precedenza si avrà:

L’undicesimo bit vale uno, potrebbe trattarsi della lettera L o G o I.

Il dodicesimo bit vale uno, potrebbe trattarsi della lettera G o I.

Il tredicesimo bit vale zero. Si tratta certamente della lettera G.

Alla fine si ottiene:

0 0 || 0 1 || 0 0 || 1 0 || 0 0 || 1 1 0 || 1 1 1 || 0 0 = OROLOGIO Altri esempi:

0 0 0 1 1 0 1 1 1 = ORLI 0 1 0 0 1 1 0 0 0 = ROGO

1 1 0 0 1 1 1 1 1 0 1 0 0 0 = GRILLO 0 0 0 1 0 0 = ORO

1 1 1 1 1 0 0 0 0 0 = IGLOO 1 1 0 1 1 1 0 1 0 0 = GIRO

La decodifica è univoca poiché ogni lettera non è il prefisso di un altra lettera. Ad esempio 0 1 identifica la lettera R perché nessun’altra lettera inizia con 0 1.

Algoritmo di Huffman

Questo algoritmo viene applicato ancora oggi nei migliore software di compressione ed è migliore di quello di Shannon-Fano.

Esempio:

Si abbia per semplicità un alfabeto di cinque simboli A, B, C, D, E.

Si supponga che nella frase da comprimere, formata da cento caratteri, vi siano 15 A, 51 B, 14 C,9 D e 11 E.

Lettera A B C D E

Frequenza 15 51 14 9 11

Si mettono le lettere in ordine a partire dalla frequenza più bassa.

Lettera D E C A B

Frequenza 9 11 14 15 51

1° Passo

Si accoppiano le lettere con frequenza minore e si assegna alla copia la somma delle frequenze

Si sono formate le coppie 20 e 29. La coppia 29 si segna più a destra della 20 per ricordare che la somma delle frequenze è maggiore ( 29 > 20 )

(4)

2° Passo:

Ora il numero delle unità si è ridotto e si formano altre coppie unendo quelle con frequenza minore.

Si forma la coppia 49 e si scrive la lettera B con frequenza 51 A destra della frequenza 49.

3° passo

Si uniscono le coppie 49 e 51 formando la coppia 100.

Si assegna ora ( arbitrariamente ) il bit zero a tutti i rami di sopra e uno a tutti i rami disotto

Si ottiene la seguente codifica ( si parta dalla radice ) Simbolo Parola di Codice

A 0 1 1

B 1

C 0 1 0

D 0 0 0

E 0 0 1

Se la codifica fosse stata fatta in ASCII ( 8 bit per lettera ) ci sarebbero voluti 5· 8 = 40 bit con questa tecnica ne bastano 1310. Come si fa a decodificare il messaggio?

Ad esempio: 1 0 1 0 0 0 0 0 1 1 1 0 0 1 Il primo bit vale 1 ed è quindi una B

Il secondo bit vale zero. Potrebbe essere A o C o D o E.

Il terzo bit vale 1. Potrebbe essere A o C Il quarto bit vale 0. Di sicuro è una C.

Procedendo in modo analogo si avrà:

(5)

1 0 1 0 0 0 0 0 1 1 1 0 0 1 = B C D A B E Altro esempio:

La stringa da comprimere sia "CIAO-MAMMA".

Si conta la frequenza delle singole lettere:

Lettera C I A M O -

Frequenza 1 1 3 3 1 1

Si individuano le lettere con minore frequenza C e I. Si sommano le frequenze 1 + 1 = 2 . Da questo momento in poi le due lettere si considerano come una coppia di frequenza 2 (

So

mma = 2)

Si trovano altre due lettere di minore frequenza e si considerano come una coppia con frequenza somma delle frequenze.

Le due coppie C I e O – si risommano tra loro ottenendo un nuovo nodo di frequenza 4

Ora le due lettere con minore frequenza sono la A e la M. Si sommano le frequenze ( 3 + 3 = 6 ) e si pone la coppia più in alto della somma 4.

Ora che l’albero è finito si può attribuire arbitrariamente il bit 0 ai rami a sinistra e il bit 1 ai rami a destra.

La codifica finale risulta pertanto:

Lettera C I O - A M

Codifica 000 001 010 011 10 11 La codifica della frase sarà:

CIAO-MAMMA = 000001100100111110111110

Bastano 24 bit contro gli 80 che sarebbero necessari con il codice ASCII. Il codice ottenuto non è univoco ma dipende dalla scelta iniziale delle lettere con minore frequenza e dall’attribuzione degli zeri e degli uno. Naturalmente la codifica cambia ma il nuovo codice è altrettanto valido quanto il precedente

Generalità sui tipi di errore nella trasmissione dati:

Si debba inviare un messaggio digitale da un trasmettitore ad un ricevitore lungo un canale.

A causa del rumore il messaggio può arrivare con degli errori.

Il problema è:

Come fa il ricevitore ad accorgersi che il messaggio è errato o corretto ed eventualmente a correggere gli errori ?

La rivelazione e correzione degli errori fa parte della

codifica di canale

. Questa tecnica consiste nell’aggiungere ai bit informativi degli ulteriori bit detti

(6)

di ridondanza in modo che il ricevitore possa capire se c’è un errore ed eventualmente correggerlo.

Tipi di errore:

Bit singolo ( single-bit ) 1 1 1 0

0

1 1 0 1 1 1 0

1

1 1 0 messaggio inviato messaggio ricevuto

Al ricevitore arrivano due o più bit errati non consecutivi 1 1 1 0

0 1 1 1 0

1 0 0

0

1 1 1

0 0 1 1

0 1 1 1

1 1 0 0

0 1 1 1

0 0

1 1 0 1 1 1

1 1

1 1 0 messaggio inviato messaggio ricevuto

Gli errori più frequenti sono quelli single-bit mentre quelli di tipo burst sono i meno probabili.

Un metodo molto semplice per individuare l’eventuale presenza di errori potrebbe essere quello di inviare due volte lo stesso messaggio. E’ altamente improbabile la ricezione degli stessi errori. Questa tecnica teoricamente valida non viene mai usata perché renderebbe più che doppio il tempo di trasmissione. Alla durata della doppia trasmissione andrebbe aggiunto il tempo di verifica da parte del dispositivo ricevente.

Non è necessario ripetere l’intera unità dati, ma aggiungere pochi bit in modo sapiente. Questa tecnica è nota come ridondanza. I bit aggiunti sono sovrabbondanti e vengono eliminati non appena il ricevitore si è accertato della bontà del messaggio trasmesso.

1) Controllo di parità pari

Si consideri una porta exor A B A Å B

0 0 0 1 1 0 1 1

0 1 1 0

Nella prima riga non ci sono uno Nella seconda riga ci sono due uno Nella terza riga ci sono due uno Nella quarta riga ci sono due uno

Si vede che se si esegue l’exor tra due bit si ottiene sempre un numero pari di uno ( lo zero è pari ) Si debba ad esempio trasmettere il seguente messaggio ( i bit si muovono verso destra )

0 0 1 0 1 1 0 1 à verso del moto coda testa

Si può ad esempio aggiungere un bit di parità pari in coda ad ogni dibit. La stringa complessiva da trasmettere diventa:

0 0 0 1 1 0 0 1 1 1 0 1 à verso del moto

Il ricevitore si accorge se arriva un solo bit errato su un dibit. Esempio:

0 0 0 1 1 0 0 1 1 1 0

0

à verso del moto

Il tribit 100 è di sicuro errato perché c’è un solo uno ( un numero dispari di uno ). Naturalmente l’esempio precedente è solo didattico. Aggiungere un bit ogni due significa rallentare di un terzo la velocità di trasmissione. Più realisticamente si può aggiungere un bit di parità ogni sette bit ad esempio ad ogni carattere del codice ASCII. Il circuito per generare i bit di parità sarà formato da sei porte exor che, per comodità grafica, si indicano con Å .

Esempio.

1 1 0 1 1 1 0 b₆ b₅b₄b₃b₂b₁b₀

(7)

Per ricavare il bit di controllo di parità si può procedere in due modi 1° Metodo:

b₆Å b₅= 1 Å 1 = 0 ( i bit sono uguali ) ( b₆Å b₅)Å b₄=0 Å 0 = 0 ( i bit sono uguali ) ( b₆Å b₅Å b₄) Å b₃= 0 Å 1 = 1 ( i bit sono diversi ) ( b₆Å b₅Å b₄ Å b₃) Å b₂= 1 Å 1 = 0 ( i bit sono uguali ) ( b6Å b5 Å b4 Å b3 Å b2) Å b1 = 0 Å 1 = 1 ( i bit sono diversi ) P = ( b₆Å b₅Å b₄ Å b₃ Å b₂ Å b₁) Å b₀= 1 Å 0 = 1 ( i bit sono diversi ) 2° Metodo:

Nel messaggio ci sono cinque uno. Per ottenere un numero pari di uno si deve aggiungere un uno.

La sequenza trasmessa ( se si aggiunge il bit di controllo in coda ) sarà:

1

1 1 0 1 1 1 0 à verso del moto

Se c’è un solo bit errato il ricevitore si accorge dell’errore e richiede, al trasmettitore, di rinviare il messaggio.

Aumentando il numero di bit di controllo è possibile correggere un singolo errore senza bisogno di richiedere il rinvio del messaggio.

|

In questa colonna ci sono sette uno

L’errore si trova all’incrocio tra la 3° riga e 5° colonna e può essere corretto.

2) Checksum ( somma di controllo )

serve a capire se c’è un errore senza però riuscire a correggerlo.

Esempio:

Si debbano inviare i quattro seguenti byte:

0 0 1 1 0 1 0 1 35H 1° Byte 1 0 1 0 0 1 1 0 A6H 2° Byte 1 1 1 1 1 1 0 0 FCH 3° Byte 1 1 1 1 1 0 1 1 FBH 4° Byte

Come controllo si può eseguire la somma aritmetica ( non exor ) dei singoli bit colonna per colonna e tenere conto del resto. Si cominci ad esempio da destra e si proceda verso sinistra.

(8)

10 10 11 10 10 10 1 1ßResti 0

1 1 1

0 0 1 1

1 1 1 1

1 0 1 1

0 0 1 1

1 1 1 0

0 1 0 1

1 + 0 + 0 + 1 +

1 1 0 1 0 0 1 0 Somma

8° Col. 7° Col. 6° Col. 5° Col. 4° Col. 3° Col. 2° Col. 1° Col.

1° colonna: 1 + 0 + 0 + 1 = 2₁₀= 10₂ ( zero con il resto di uno ) 2° colonna: 1 + 0 + 1 + 0 + 1 = 3₁₀= 11₂ ( uno con il resto di uno ) 3° colonna: 1 + 1 + 1 + 1 + 0 = 4₁₀= 100₂ ( zero con il resto di 10 ) 4° colonna: 10 + 0 + 0 + 1 + 1 = 4₁₀ = 100₂ ( zero con il resto di 10 ) 5° colonna: 10 + 1 + 0 + 1 + 1 = 5₁₀ = 101₂ ( uno con il resto di 10 ) 6° colonna: 10 + 1 + 1 + 1 + 1 = 6₁₀ = 110₂ ( zero con il resto di 11 ) 7° colonna: 11 + 0 + 0 + 1 + 1 = 5₁₀ = 101₂ ( uno con il resto di 10 ) 8° colonna: 10 + 0 + 1 + 1 + 1 = 5₁₀ = 101₂ ( uno con il resto di 10 ) I bit da aggiungere sono: 1 1 0 1 0 0 1 0 = D2H

Complessivamente si invia il seguente messaggio: In esadecimale

D2H FBH FCH A6H 35H

à verso del moto Checksum Messaggio informativo

In binario

1101 0010 1111 1011 1111 110 0 1010 0110 0011 0101

Il ricevitore esegue lo stesso tipo di procedura precedente e confronta i due checksum. Se sono diversi vi è un errore.

Un altro tipo di checksum consiste nell’eseguire l’exor dei bit colonna per colonna.

Praticamente si ricava il bit di parità pari.

0 1 1 1

0 0 1 1

1 1 1 1

1 0 1 1

0 0 1 1

1 1 1 0

0 1 0 1

1 0 0 1

1 0 0 1 0 1 0 0

8° Col. 7° Col. 6° Col. 5° Col. 4° Col. 3° Col. 2° Col. 1° Col.

1° colonna: Ci sono due uno. Non si deve aggiungere un altro uno 2° colonna: Ci sono due uno. Non si deve aggiungere un altro uno

3° colonna: Ci sono tre uno. Si deve aggiungere un altro uno per ottenere un numero pari di uno 4° colonna: Ci sono due uno. Non si deve aggiungere un altro uno

5° colonna: Ci sono tre uno. Si deve aggiungere un altro uno per ottenere un numero pari di uno 6° colonna: Ci sono quattro uno. Non si deve aggiungere un altro uno

7° colonna: Ci sono due uno. Non si deve aggiungere un altro uno

8° colonna: Ci sono tre uno. Si deve aggiungere un altro uno per ottenere un numero pari di uno I bit da aggiungere sono: 1 0 0 1 0 1 0 0 = 94H

Complessivamente si invia il seguente messaggio: In esadecimale

94H FBH FCH A6H 35H

In binario

1001 0100 1111 1011 1111 110 0 1010 0110 0011 0101

Il ricevitore esegue lo stesso tipo di procedura precedente e confronta i due checksum. Se sono diversi vi è un errore.

Introduzione all’algebra modulo due

(9)

Si indichi con : S = Somma di due bit R = Resto della somma D = Differenza di due bit P = Prestito della differenza Si avrà:

A B S R D P

0 0 0 1 1 0 1 1

0 0 1 0 1 0 0 1

0 0 1 1 1 0 0 0

0 +0 vale zero con il resto di zero

0 –1 Vado in prestito di 1 nella colonna a sinistra. Ora devo fare 10 –1 che vale 1.

Quindi 0 –1 vale 1 con il prestito di uno.

1 + 1 vale 2₁₀=10 cioè zero con il resto di uno

Riporti à R 0 0 0 1

A + 0 + 0 + 1 + 1 +

B = 0 = 1 = 0 = 1 =

S 0 1 1 0

Prestiti à P 0 1 0 0

A - 0 - 0 - 1 - 1 -

B = 0 = 1 = 0 = 1 =

D 0 1 1 0

Si vede che : S = D = A Å B

Se si trascurano i resti e i prestiti la somma e la differenza sono uguali:

A - B = A + B ; 0 - B = 0 + B ; - B = B Esempio:

1 1 0 0 1 Å 1 1 0 0 1 - 0 1 1 0 1 = 0 1 1 0 1 = 1 0 1 0 0 1 0 1 0 0 Altro modo i ragionare:

AB = 00 Ci sono zero uno. Quanti ne mancano per arrivare a due ? Ne mancano due In binario scrivo zero con il riporto di uno. Se trascuro il riporto resta zero à 0 AB = 01 C’è un uno. Manca un bit uno per arrivare a due. à 1

AB = 10 C’è un uno. Manca un bit uno per arrivare a due. à 1 AB = 11 Cisono due bit uno. Ne mancano zero per arrivare a due. à 0

3) Codice di Hamming

( si riesce a trovare l’errore e correggerlo ) Si debba inviare il seguente messaggio

1 0 0 1 1 0 1

Si introducono i bit in tante celle contigue lasciando vuote quelle di posto multiplo di 2ⁿ. Si lasciano libere le celle la cui posizione, a partire da destra verso sinistra , vale 1, 2, 4, 8, 16 …

Posizione à 11 10 9 8 7 6 5 4 3 2 1

1 0 0 1 1 0 1

Si hanno 7 bit di informazione più 4 di check ( controllo ). In totale undici bit.

Si associ agli uno la loro posizione tradotta in binario e si esegua la somma modulo due ( exor senza tenere conto dei resti )

1 0 0 1 1 0 1

11₁₀ 7₁₀ 6₁₀ 3₁₀

11₁₀= 1 0 1 1 Å 7₁₀ = 0 1 1 1 Å 6₁₀ = 0 1 1 0 Å 3₁₀ = 0 0 1 1 Å

1 0 0 1 Bit di ridondanza

Nel seguito con il termine somma si intenderà la somma modulo due.

Si introducano i bit di ridondanza così ottenuti negli spazi vuoti lasciati in precedenza.

Posizione à 11 10 9 8 7 6 5 4 3 2 1

(10)

1 0 0

1

1 1 0

0

1

0 1

La somma delle posizioni occupate dai bit di ridondanza deve essere uguale alla somma delle posizioni occupate dal messaggio originale 8₁₀ = 1 0 0 0 Å

1₁₀ = 0 0 0 1 = 1 0 0 1

11₁₀Å 7₁₀Å 6₁₀Å 3₁₀ = 8₁₀Å 1₁₀ Si avrà infine:

( 11₁₀Å 7₁₀Å 6₁₀Å 3₁₀) Å ( 8₁₀Å 1₁₀ ) = 1 0 0 1 Å 1 0 0 1 = 0 0 0 0

Questo è il controllo eseguito dal ricevitore. Se la somma ( sempre modulo due ) di tutte le posizioni dei bit uno, tradotta in binario, vale zero, significa che il messaggio è corretto. Se c’è un bit errato ad esempio nella posizione sette e vale zero

Posizione à 11 10 9 8 7 6 5 4 3 2 1

1 0 0 1

0

1 0 0 1 0 1

lo devo togliere dalla somma precedente che valeva zero ( 11₁₀Å 7₁₀Å 6₁₀Å 3 Å 8₁₀Å 1₁₀ ) - 7₁₀ = 0000 - 0111 = 0111 - 7₁₀ = + 7₁₀ nell’algebra modulo due

Quindi, non solo si riesce a capire che c’è un errore, ma anche che si trova nella settima posizione e può quindi essere corretto.

Altri esempi:

Si supponga che al ricevitore arrivi il seguente messaggio:

Posizione à 11 10 9 8 7 6 5 4 3 2 1

0 0 0 1 1 1 0 0 1 0 1

Si sommino le posizioni occupate dai bit uno:

810 = 1 0 0 0 Å 7₁₀ = 0 1 1 1 Å 6₁₀ = 0 1 1 0 Å 3₁₀ = 0 0 1 1 Å 1₁₀ = 0 0 0 1 1 0 1 1

Si ottiene 1011 = 11₁₀. Il ricevitore capisce subito che il bit errato è all’undicesimo posto e lo corregge. Se tutti i bit fossero corretti la somma delle loro posizioni dovrebbe essere zero.

L’undicesimo bit vale zero e va quindi tolto dalla somma corretta ottenendo:

( 11₁₀Å 7₁₀Å 6₁₀Å 3) Å (8₁₀Å 1₁₀ ) - 11₁₀ = 0₁₀- 11₁₀ = 11₁₀= 1 0 1 1 - 11₁₀ = +11₁₀nell’algebra modulo due

Si supponga che al ricevitore arriva il seguente messaggio:

Posizione à 11 10 9 8 7 6 5 4 3 2 1

1 0 1 1 1 1 0 0 1 0 1

Si sommino le posizioni occupate dai bit uno:

11₁₀= 1 0 1 1 Å 9₁₀= 1 0 0 1 Å 8₁₀= 1 0 0 0 Å 7₁₀ = 0 1 1 1 Å 6₁₀ = 0 1 1 0 Å 3₁₀ = 0 0 1 1 Å 1₁₀ = 0 0 0 1 1 0 0 1

Il nono bit vale uno e quindi va aggiunto alla somma corretta

( 11₁₀Å 7₁₀Å 6₁₀Å 3) +( Å 8₁₀Å 1₁₀ ) + 9₁₀ = 0₁₀- 9₁₀ = 9₁₀= 1 0 0 1

(11)

- 9₁₀ = + 9₁₀ nell’algebra modulo due

Il ricevitore capisce che il bit errato è il nono e lo corregge.

La spiegazione svolta precedentemente in dettaglio dimostra che la somma degli uno fornisce direttamente ( se diversa da zero ), la posizione del bit errato.

Più velocemente si può procedere ricordando che l’exor fornisce il bit di parità pari. Si riprenda il caso dell’errore al settimo posto.

Posizione à 11 10 9 8 7 6 5 4 3 2 1

1 0 0 1

0

1 0 0 1 0 1

P e s i

1 1 1 1 1 1 1°

Riga

2 2 2 2 2 2 2°

Riga

4 4 4 4 3°

Riga

8 8 8 8 4°

Riga Si traducano le posizioni dal decimale al binario e si osservino le varie righe.

Nella prima riga ci sono tre uno in corrispondenza agli uno del messaggio. La riga di peso uno è sbagliata perché il numero degli uno è dispari.

Nella seconda riga vi sono tre due in corrispondenza agli uno del messaggio. Il peso due è errato.

Nella terza riga vi è un quattro. Il peso quattro è errato.

Nella quarta riga vi sono due otto. Il peso otto è corretto perché corrisponde ad un numero pari di uno del messaggio.

I pesi sbagliati sono 1₁₀ + 2₁₀ + 4₁₀ = 7₁₀. L’errore si trova al settimo posto.

Altro esempio:

Posizione à 11 10 9 8 7 6 5 4 3 2 1

0

0 0 1 1 1 0 0 1 0 1

P e s i

1 1 1 1 1 1 1°

Riga

2 2 2 2 2 2 2°

Riga

4 4 4 4 3°

Riga

8 8 8 8 4°

Riga Prima riga errata ( tre uno ).

Seconda riga errata ( tre due ).

Terza riga corretta ( due quattro ).

Quarta riga errata ( un otto ).

1₁₀ + 2₁₀ + 8₁₀ = 11₁₀. L’errore si trova all’undicesimo posto.

Si fornisce un altro esempio completo con pochi commenti:

Si debba inviare il seguente messaggio:

1 0 1 0 1 1 1

Posizione à 11 10 9 8 7 6 5 4 3 2 1

1 0 1 0 1 1 1

P e s i

1 1 1 1 1

2 2 2 2 2

4 4 4

8 8 8

Peso uno ( quattro uno ) si mette uno zero nella posizione uno.

Peso due ( tre due ) si mette un uno nella posizione due.

Peso quattro ( due quattro ) si mette uno zero nella posizione quattro.

Peso otto ( due otto ) si mette uno zero nella posizione otto.

Posizione à 11 10 9 8 7 6 5 4 3 2 1

1 0 1

0

0 1 1

0

1

1 0

(12)

Se al ricevitore arriva 1 0 1

0

0 1 1

0

1

1 0

si ripete il procedimento precedente e si vede che i bit di ridondanza

0 0 1 0

coincidono con quelli inviati. Il messaggio risulta pertanto corretto.

Se al ricevitore arriva 1 1 1

0

0 1 1

0

1

1 0

si ripete il procedimento precedente e si ottiene:

Posizione à 11 10 9 8 7 6 5 4 3 2 0

1 1 1 0 0 1 1 0 1 1 0

P e s i

1 1 1 1 1 Riga

Corretta

2 2 2 2 2 Riga

Corretta

4 4 4 Riga

Corretta

8 8 8 Riga

Scorretta

Le posizioni 1₁₀, 2₁₀, 4₁₀, dovrebbero contenere uno zero. La posizione 8₁₀ dovrebbe contenere un uno. Le posizioni scorrette sono la 2₁₀ e la 8₁₀. 210 + 810 = 1010. L’errore si trova nella decima posizione. Il ricevitore cambia l’uno con uno zero.

4) Controllo di ridondanza ciclica

Si indichi con il simbolo Å una porta Exor e con un rettangolo un flip-flop D ( Il clock non compare nello schema per semplicità ).

Si consideri una struttura del tipo di figura detto circuito generatore.

Si associ a questo circuito un polinomio di grado n detto polinomio generatore.

I bit b_i possono valere o zero o uno a secondo che l’interruttore sia aperto o chiuso.

Dalla tabella della porta Exor

A B A Å B A 0 A Å 0

0 0 0 1 1 0 1 1

0 1 1 0

0 0 1 0

0 1

si vede che A Å 0 = A. Se ne deduce quindi che non occorre mettere la corrispondente porta Exor se un bit vale zero. Si noti che il numero di flip-flop corrisponde al grado del polinomio.

Esempi:

(13)

Si invii ora all’ingresso m un messaggio formato da zeri e uno in modo che i bit avanzino con la cadenza del clock dei flip-flop. Alla fine del messaggio resterà all’uscita dei flip-flop una sequenza

ridondanza ciclica). Questa sequenza viene aggiunta al messaggio originale e trasmessa in coda ad esso.

Esempi:

Il circuito generatore del crc sarà:

Si indichi con Q₂, Q₁, Q₀ le uscite attuali dei flip flop con D₂, D₁, D₀ le uscite future ( gli ingressi attuali ). Si ricordi che il flip flop D riporta all’uscita, in sincronismo con la commutazione del

Si supponga ad esempio che all’inizio le uscite dei flip flop siano tutte a zero.

Osservando il circuito si ricavano le seguenti equazioni booleane:

Da queste equazioni si ricava la seguente tabella m Q₂Q₁ Q₀ D₂ D₁ D₀

1° Clock 1 0 0 0 0 1 1 D₂= 0 D₁= 1 Å 0 Å 0 = 1 D₀ = 1 Å 0 = 1 2° Clock 1 0 1 1 1 0 1 D2 = 1 D1 = 1 Å 0 Å 1 = 0 D0 = 1 Å 0 = 1 3° Clock 0 1 0 1 0 0 1 D₂= 0 D₁= 0 Å 1 Å 1 = 0 D₀ = 0 Å 1 = 1 4° Clock 1 0 0 1 0 0 1 D₂= 0 D₁= 1 Å 0 Å 1 = 0 D₀ = 1 Å 0 = 1

1° Bit 2° Bit 3° Bit

Si aggiunge il CRC in coda al contenuto informativo m. Il messaggio complessivo trasmesso ( T ) sarà:

All’arrivo si invia il messaggio T ricevuto ad un circuito generatore identico a quello di partenza con le stesse condizioni iniziali ( nel nostro caso tutti i flip flop azzerati ). Se non ci sono errori, esauriti i bit del messaggio m si ottiene lo stesso CRC inviato e quindi ( si ricordi che A Å A = 0 ), alla fine, i registri devono essere tutti azzerati.

CRC Q₂Q₁ Q₀ D₂ D₁ D₀

1° Clock 0 0 0 1 0 1 0 D₂= 0 D₁= 0 Å 0 Å 1 = 1 D₀ = 0 Å 0 = 0 1° Clock 0 0 1 0 1 0 0 D₂= 1 D₁= 0 Å 0 Å 0 = 0 D₀ = 0 Å 0 = 0 1° Clock 1 1 0 0 0 0 0 D₂= 0 D₁= 1 Å 1 Å 0 = 0 D₀ = 1 Å 1 = 0

Si usano i seguenti polinomi standard : CRC 16 x¹⁶+ x¹⁵+ x²+1

E' usato quando il carattere e' lungo 8 bits

(14)

CRC-CCIT x¹⁶+ x¹²+ x⁵+1

Con i circuiti standard sopra riportati si rivelano tutti gli errori singoli, doppi e in numero dispari e tutte le "raffiche" di errore di lunghezza fino a 16 e circa il 99,997 % delle "raffiche" di lunghezza maggiore.

Codifica di linea Tipi di Codici

La codifica di linea è l’operazione che trasforma un messaggio digitale, costituito da una successione di “1”e “0” logici, in un segnale costituito da una sequenza di impulsi elettrici o ottici.

Codice ideale per la codifica di linea:

Dovrebbe contenere la frequenza del clock in modo che il ricevitore riesca a sincronizzare il PLL.

Se il codice non contiene la frequenza di clock, quest’ultima si deve ricavare con facilità

Non deve contenere la componente continua. Questa componente non porta informazione ed oltre a costituire una potenza sprecata, non è adatta ad essere trasferita attraverso un trasformatore o un condensatore di accoppiamento.

Deve occupare una banda stretta. Più stretta è la banda più informazioni posso inviare lungo il canale necessariamente a banda limitata.

Non deve avere lunghe stringhe di zeri e uno altrimenti il PLL del ricevitore non riesce a mantenere il sincronismo ( perde l’aggancio ).

Scrambler Desclamber

Si ricordi che:

L’uscita U risulta uguale al dato D ma il segnale B non contiene mai lunghe stringhe di zeri e uno.

In questo modo si ottengono due vantaggi:

1) Si facilita la sincronizzazione tra ricevitore e trasmettitore 2) Si rende incomprensibile il segnale lungo il canale

Codice NRZ

Difetti:

Non contiene la frequenza di clock Valore medio diverso da zero

Se ci sono lunghe stringhe di zeri e uno il PLL al ricevitore perde l’aggancio E necessario lo scrambler

Pregi:

Banda occupata 1/Tb

Si ricordi che un singolo impulso contiene tutte le frequenze di un segnale digitale e che la trasformata di un impulso di ampiezza A e durata Tb vale:

Banda di un Segnale Digitale

(15)

Studio in frequenza di un Impulso Rettangolare

Codice RZ

Difetti:

Valore medio diverso da zero Banda occupata doppia rispetto a NRZ

Se ci sono lunghe stringhe di zeri e uno il PLL al ricevitore perde l’aggancio E necessario lo scrambler

Pregi:

contiene fc ( la frequenza del clock )

Codice Manchester o bifase

Difetti:

Banda occupata come RZ

Pregi:

Contiene fc Valore medio nullo

Non serve lo scrambler perché anche con lunghe stringhe di zeri o uno il segnale varia continuamente

Codice ami (alternate mark inversion)

Inverte alternativamente il mark cioè l’uno

Difetti:

Serve lo scrambler se ci sono lunghe stringhe di zeri perché altrimenti il PLL non si aggancia Pregi:

Valore medio nullo

Contiene fc/2 (posso usare un raddrizzatore per raddoppiare la frequenza)

(16)

Per convincersi che il segnale contiene metà della frequenza del clock basta considerare la sinusoide ( prima armonica ) che approssima l’alternanza dei valori positivi e negativi.

Si vede che la durata della sinusoide è doppia del periodo del clock e quindi la frequenza sarà metà.

Il comportamento in frequenza sarà quindi simile al codice bifase