I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed HAMMINGma ci siamo mai chiesti in che modo nascono questi errori?
DOVE NASCONO GLI ERRORI?
Quando avviene uno scambio di informazioni tra l’elaboratore e la memoria attraverso i fili paralleli (BUS), il segnale trasmesso può essere soggetto a rumori e quindi si può sovrapporre creando un bit errato. In caso vi sia la presenza di ERRORE questo può esser trattato in 4 modi diversi:
Il messaggio viene scartato.
Viene richiesta la trasmissione del messaggio.
Viene migliorata la qualità del canale.
L’errore viene cercato di correggerlo
HAMMING
Nel 1950 Hamming propone il sistema di codifica a correzione d’errore che porta oggi il suo nome: il codice di Hamming.
L’idea di base del codice di Hamming è quella di codificare la posizione dell’eventuale errore
Si aggiungono alcuni bit di controllo, tanti quanti sono necessari per codificare la posizione del bit errato
Poiché anche i bit di controllo sono soggetti a errore, occorre includere anche le posizioni di questi bit nel conteggio totale.
Data una stringa di 8 bit, si aggiungono 4 bit di controllo, per un totale di 12 bit di codework
4 bit di posizione bastano per codificare le 12 posizioni, dato che 24 = 16 ci permette di codificare 16 posizioni (4 configurazioni non utilizzate).
Codework è il risultato della somma dei bit di dati + i bit di controllo
Esempio
BIT DI CONTROLLO
Costruiamo il singolo codework “mischiando” bit di informazione e bit di controllo. Innanzitutto numeriamo i bit della parola da trasmettere a partire da sinistra verso destra, inserendo a ogni posizione avente per indice una potenza del 2 il posto per un bit di controllo.
Ogni bit di controllo è un bit di parità che esprime la parità di un sottoinsieme opportuno dei bit della stringa
il bit di controllo in posizione 2j controlla la parità di tutti i bit la cui posizione, in binario, ha il j-esimo bit a 1
Il primo bit di controllo si ottiene come parità di tutti i bit che sono in posizione tale per cui la loro codifica binaria ha 1 nel bit meno significativo (sono tutte le posizioni dispari).
primo bit di controllo
Il secondo bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 2° bit = 1, e cioè 2 3 6 7 10 11..
secondo bit è di parità
Il terzo bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 3° bit=1, cioè 4 5 6 7 12 …
Il quarto bit è di parità per tutti i bit in cui la codifica binaria della posizione ha il 4° bit = 1 cioè 8 9 10 11 12 …
terzo e quarto bit di parità
Per approfondire ti consigliamo la lettura di questi articoli:
I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed HAMMING ma ci siamo mai chiesti in che modo nascono questi errori?
DOVE NASCONO GLI ERRORI?
Quando avviene uno scambio di informazioni tra l’elaboratore e la memoria attraverso i fili paralleli (BUS), il segnale trasmesso può essere soggetto a rumori e quindi si può sovrapporre creando un bit errato. In caso vi sia la presenza di ERRORE questo può esser trattato in 4 modi diversi:
Il messaggio viene scartato.
Viene richiesta la trasmissione del messaggio.
Viene migliorata la qualità del canale.
L’errore viene cercato di correggerlo
CHECKSUM
Come funziona CHECKSUM?
Per riuscire a correggere l’errore mediante un codice di parità è necessario utilizzare il sistema di controllo della parità incrociata. Si introduce in coda alla trasmissione di un blocco di n dati un byte, chiamato byte di checksum, che viene calcolato eseguendo l’operazione di XOR su tutti i byte costituenti il blocco-dati da trasmettere.
Questo metodo prende anche il nome di controllo di parità longitudinale LRC(Longitudinal Redundancy Check)
il bit di parità descritto precedentemente è detto anche controllo di parità trasversale o VRL
parità longitudinale e parità trasversale
ESEMPIO
Supponiamo che durante la trasmissione un bit del Dato3 si sporchi
Alla ricezione il controllo di parità trasversale ci segnala la presenza dell’errore sul Dato3 senza però indicarne la posizione.
Rilevamento posizione errore
Alla fine della trasmissione dei dati il controllo “verticale” ci segnala la presenza di un errore nel bit b5, dato che il numero di 1 è dispari
Dall’ intersezione tra la riga e la colonna individuiamo il bit che si è sporcato => siamo quindi in grado di correggere un errore
DIFETTI CHECKSUM
Se gli errori crescono non sono più rilevabili ed è necessario aumentare la distanza minima di Hamming introducendo ulteriori bit di ridondanza.
Per esempio, in presenza di due errori ci troviamo in questa situazione:
situazione
In questo caso però non siamo in grado di correggere perché entrambe le correzioni portano a configurazioni legittime e quindi generano un’ambiguità nella correzione.
I principali metodi di rilevazioni di errori sono 3: CRC, CHECKSUM ed HAMMING ma ci siamo mai chiesti in che modo nascono questi errori?
DOVE NASCONO GLI ERRORI?
Quando avviene uno scambio di informazioni tra l’elaboratore e la memoria attraverso i fili paralleli (BUS), il segnale trasmesso può essere soggetto a rumori e quindi si può sovrapporre creando un bit errato. In caso vi sia la presenza di ERRORE questo può esser trattato in 4 modi diversi:
Il messaggio viene scartato.
Viene richiesta la trasmissione del messaggio.
Viene migliorata la qualità del canale.
L’errore viene cercato di corregerlo
CRC
Esempio esercizio
ll metodo di rilevazione degli errori usato più comunemente nei sistemi di comunicazione è il codice CRC o codice a ridondanza ciclica.
Si utilizza un polinomio G(x), chiamato generatore polinomiale, in cui i bit di ordine più alto e più basso devono essere a 1, noto al mittente e al ricevente. Sia M(x) la stringa di bit da inviare (di m bit) e G(X) il polinomio generatore (di r bit). M(X) deve essere più lungo di G(X) cioè m>r. ll metodo si basa sul calcolo di una checksum che dipende da M(X) e G(x) da aggiungere in fondo a M(x) in modo che la stringa ottenuta sia divisibile per G(X). ll mittente invia un frame composto dai bit di dati (M(x)) e dalla checksum. Per verificare la corretta ricezione basta che il ricevente divida il frame per G(x); se la divisione dà un resto vuol dire che si è verificato un errore.
Parte 1
Per calcolare il CRC di un pacchetto M(X) di m bit si procede così:
Le operazioni sui polinomi sono eseguite in aritmetica modulo 2: non ci sono riporti per l”addizione o prestiti perla sottrazione; addizione e sottrazione sono identiche all’ or esclusivo. La divisione è eseguita come se fosse binaria ma la sottrazione è eseguita in modulo 2 (in pratica un divisore è contenuto nel dividendo se il dividendo ha tanti bit quanti il divisore contando le cifre dal primo 1 a sinistra).
Parte 2
Questo metodo del CRC non è infallibile; possono verificarsi degli errori nel frame inviato che danno comunque O come risultato della divisione del frame per G(X) e che quindi non sono rilevati. La scelta del polinomio G(X) `e importante perla bontà del metodo.
l polinomi che sono diventati standard internazionali sono:
Le problematiche nel creare una interazione tra l’utente e l’hardware sono state le prime ad essere affrontate dai progettisti che decisero così di creare il SOFTWARE DI BASE. Queste migliorarono grazie ai sistemi dedicati, la gestione dei sistemi a lotti dato che introdussero il BUFFERING e il SPOOLING.
La prima fase, quella compresa tra il 1945 e il 1955, può essere definita come quella dei sistemi dedicati. I calcolatori erano valvolari, occupavano intere stanze, erano lenti, molto costosi e a uso quasi esclusivo di università o centri di ricerca.
Il tempo macchina, inteso come tempo di utilizzo della CPU, era una risorsa pregiata concessa a pochi utenti privilegiati per brevi periodi (turni), e durante il proprio turno i vari utenti avevano a disposizione l’intero sistema: il programmatore caricava i propri programmi (scritti in linguaggio macchina prima e successivamente in assembler) in memoria, li faceva eseguire e ne controllava l’esecuzione.
Non esisteva un sistema operativo vero e proprio: le poche funzioni disponibili per la gestione dell’hardware venivano inviate impostando interruttori e commutatori della console. Non esistevano tastiera e monitor, e i risultati dei programmi si leggevano direttamente in alcuni registri rappresentati sul pannello tramite indicatori luminosi.
GESTIONE A LOTTI (1955-1965)
La gestione appena descritta permetteva un basso utilizzo della CPU in quanto la maggior parte del tempo veniva sprecata per caricare i programmi: in un sistema molto costoso sicuramente tale situazione non era soddisfacente. Il passo successivo fu quello di introdurre un sistema automatico di caricamento dei programmi: si utilizzarono le schede perforate come supporti su cui memorizzare i programmi, i comandi con le chiamate di sistema operativo e i lettori di schede come dispositivi di input.Ogni scheda perforata conteneva un’istruzione.
L’utente non utilizzava più la console del calcolatore, ma la sua interazione avveniva semplicemente inserendo un pacco di schede (lotto) nell’apposito lettore: questo tipo di gestione fu proprio chiamata gestione a lotti (batch processing) o elaborazione a lotti. I lavori degli utenti erano costituiti da pacchi di schede perforate dove ogni lotto (chiamato lavoro o job) iniziava con una scheda di identifi cazione dell’utente e consisteva in una sequenza di passi o step, dove i singoli step erano le funzioni richieste dall’utente al sistema operativo, come la compilazione del programma, il caricamento, l’esecuzione ecc.
Le schede di controllo utilizzavano un particolare linguaggio per comunicare con il calcolatore: il JCL o Job Control Language. Un job è delimitato da due schede speciali di controllo: $JOB e $END. Per esempio il comando $FTN attivava il compilatore Fortran, $RUN richiedeva l’esecuzione, $END terminava l’elaborazione ecc. Il processore alternava quindi l’esecuzione di istruzioni di controllo ai programmi: gli eventuali dati dovevano essere inclusi nel pacco di schede e quindi i singoli lavori prevedevano anche un’alternanza di schede di istruzioni, di controllo e di schede dati. I risultati delle elaborazioni finivano stampati su un tabulato comune a tutti i job.
Le principali caratteristiche di questo tipo di sistema possono essere così elencate:
il sistema operativo è sempre residente in memoria (monitor)
In memoria centrale è presente un solo job alla volta;
Finché il job corrente non è terminato, il successivo non può iniziare l’esecuzione;
Non è presente interazione tra utente e job;
Se un job si sospende in attesa di un evento, la CPU rimane inattiva;
Da una scarsa efficienza: durante l’I/O del job corrente, che sono per loro natura molto lente, la CPU rimane inattiva.
Il problema principale della scarsa efficienza di questo tipo di gestione era proprio legato al fatto che la CPU veniva sempre altamente sottoutilizzata dato che sia il lettore di schede sia la stampante, essendo componenti meccanici, erano di gran lunga più lenti del processore, che risultava per la maggior parte del tempo inattivo aspettando le “lentezze” delle sue periferiche. Furono quindi introdotti perfezionamenti nella gestione a lotti per rimuovere tale collo di bottiglia: si passò dalle schede ai nastri magnetici, aumentando così la velocità di trasferimento;
BUFFERING
Un primo rimedio per ovviare ai tempi di attesa delle periferiche fu l’introduzione della tecnica di buffering: un buffer è un’area di memoria intermedia dedicata al salvataggio temporaneo di informazioni, implementato direttamente nel device driver del dispositivo. IBM 1401 fu uno dei primi calcolatori ad utilizzare questa tecnologia (buffering).
Con il buffering l’accesso alla periferica segue questa sequenza di operazioni:
La periferica legge in Input/Output un blocco dati (blocco corrente) e lo passa alla CPU;
Mentre la CPU elabora il blocco dati corrente, la periferica legge il blocco dati successivo;
La CPU produce output solo fino a quando il buffer è pieno e quindi si ferma;
La periferica di uscita legge i dati prodotti dalla CPU prelevandoli dal buffer al suo ritmo.
SPOOLING
Nonostante l’introduzione dei buffer, rimasero alcuni problemi da risolvere:
I buffer non possono essere molto grandi per motivi di costi;
Il buffer tende a riempirsi velocemente e quindi il problema dell’attesa non viene risolto;
Con velocità di I/O << velocità CPU non produce giovamenti;
Se il buffer si riempie, la CPU si blocca.
Si arrivò all’introduzione di meccanismi chiamati dischi di spooling (Simultaneous Peripheral Operations On Line), creando contemporaneità tra le attività di I/O e quelle di computazione: il disco viene impiegato come un buffer molto ampio, dove leggere in anticipo i dati e memorizzare temporaneamente i risultati, in attesa che il dispositivo di output sia pronto. Invece cioè di scrivere e leggere dai dispositivi fisici si legge e si scrive su due dispositivi virtuali:
Il disco di spooling di ingresso contiene le schede lette dal lettore e contenenti job nonancora eseguiti (“job virtuali”);
Il disco di spooling di uscita contiene invece “output virtuali”, ossia tabulati già prodotti relativi a eseguiti ma non ancora stampati. In questo modo è possibile sovrapporre i tempi di elaborazione con quelli di I/O: mentre la CPU elabora il programma, i canali di I/O provvedono a riempire o svuotare i dischi di spooling e a gestire i trasferimenti
Il sistema operativo lo possiamo considerare come il gruppo di programmi che gestisce funzionamento del computer agendo come intermediario tra utente e PC. Se sei interessato a scoprire l’evoluzione del S.O. clicca qui. Se sei curioso riguardo alla storia del sistema operativo clicca qui.
Esempio di S.O.
COMPITI PRINCIPALI DEL SISTEMA OPERATIVO:
Gestisce le risorse dell hardware ovvero della CPU, della memoria e delle periferiche.
Fare da interfaccia per l’utente.
Gestire l’aspetto grafico della visualizzazione su monitor.
La struttura del S.O. è composta da un insieme di sottoprogrammi dove ognuno di esso ho un compito preciso. I sottoprogrammi vengono caricati in RAM solo nel caso vengono richiesti. ONION SKIN è la struttura gerarchica dove ciascuno strato serve a quello inferiore.
Struttura sistema operativo
NUCLEO o KERNEL è sempre caricato in memoria. Viene identificato anche come “nocciolo”, dato che avvolge tutto l’hardware creando una portabilità di un sistema operativo. Tutti i servizi attivati passano tra di lui e i suoi compiti principali sono:
Avviare e terminare processi.
Assegnare dei processi alla CPU .
Sincronizzare processi.
Sincronizzare processi con ambienti esterni
Quando si sta eseguendo il codice del kernel si dice che il processore gira nel cosiddetto “modo supervisore“.
SHELL è un programma che permette di comunicare con l’utente . Infatti il suo compito principale è quello di fare da interfaccia tra utente e nucleo , isolando però quest’ultimo allo scopo di proteggerlo.
Il segnale analogico è la trasformazione di una grandezza fisica tramite una grandezza analoga che bene la descrive.
Questo segnale può essere rappresentato mediante una funzione del tempo che gode delle seguenti caratteristiche: 1) la funzione è definita per ogni valore del tempo (è cioè continua nel dominio) 2) la funzione è continua.
PASSAGGIO DA SEGNALE ANALOGICO A DIGITALE
Il passaggio tra i due segnali viene chiamato “DISCRETIZZAZIONE“. Durante questo passaggio avviene una perdita di dati dovuto al CAMPIONAMENTO. Il campionamento è la rilevazione parziale di un segnale analogico prelevando a particolari istanti di tempo il valore del segnale stesso. Vi mostriamo qua in seguito come avviene quest’ultima fase.ù
campionamento di un segnale analogico
SEGNALE DIGITALE
Come esposto precedentemente, il segnale digitale nasce dal campionamento di un segnale analogico. Proprio per questi motivi il segnale digitale lo dobbiamo considerare come un segnale DISCRETO e FINITO.
Quando un segnale discreto è composto da una serie di valori ottenuti in corrispondenza di istanti spaziati uniformemente nel tempo, si dice che è associato ad una particolare frequenza di campionamento; la frequenza di campionamento non è direttamente desumibile nella sequenza dei valori campionati, ma può essere fornita come dato separato.
DIFFERENZE TRA SEGNALE DIGITALE E BINARIO
Il “BINARIO” è semplicemente una codifica del segnale digitale. Questa è molto spesso associata al segnale digitale per semplificarne il funzionamento. Molto spesso, proprio per questo motivo il sistema binario viene utilizzato per rappresentare due cariche elettriche o due stati di polarizzazione
