Settimo Articolo
TCP/IP, protocolli ed altri misteri
Parte 7
LA CORREZIONE DEGLI ERRORI
La cosa pi— appariscente che gli OM hanno notato nel passaggio
dalla RTTY al Packet Š che non si hanno pi— errori di
trasmissione: per magia i dati appaiono sul diplay esattamente
come sono stati inviati od, eventualmente, non appaiono affatto.
In questa puntata cercheremo di analizzare la natura degli
errori, il modo in cui questi vengono individuati e corretti e
le limitazioni del sistema. Vedremo, inoltre, possibili
alternative ed i loro campi specifici di impiego.
Tutte le volte che dei dati ( o informazioni, sia digitali che
analogiche ) vengono inviati su un canale fisico reale questi
subiscono un degrado. Le cause di tale degrado sono molteplici:
interferenza, rumore termico, distorsioni del canale. Il
risultato Š comunque simile: si perde parte della informazione
spedita, o meglio, si perde la sicurezza che quel che Š stato
ricevuto sia identico a quello che Š stato trasmesso. Il
degrado che i dati subiscono Š molto simile al degrado totale
che subisce l'intero universo in cui l'energia ben organizzata
lentamente si trasforma in energia termica caotica. Ritorneremo
su questo argomento, ma qu mi preme introdurre solo il concetto
che tale degrado Š un aspetto fondamentale ineliminabile.
Ovviamente non tutti i canali di trasmissione sono uguali: ce ne
sono di migliori e di peggiori. Nei migliori il degrado sar…
contenuto, ma negli altri sar… pi— accentuato. A questo punto,
capite che occorre un qualche modo o unit… di misura per
valutare la bont… di un canale. Se il canale lo compro sul
mercato voglio che i miei soldi siano ben spesi, quindi devo
essere in grado di valutarlo per poter confrontare le offerte
dei vari fornitori. Se il canale lo "costruisco" devo essere in
grado di farlo al meglio per avere un buon prodotto. In
entrambe i casi occorre un metodo sensato e riproducibile per
misurare la portata di un canale di trasmissione ed il grado di
affidabilit…. Questo sar… l'argomento delle prossime puntate;
di seguito vedremo come sia possibile migiorare l'affidabilit…
di una trasmissione di dati qualora non si possa intervenire pi—
sul canale. Per quanto riguarda il concetto di CANALE consiglio
la meditata lettura dell'articolo di I2VGO su RR 7/90 p.p.44-46.
Dunque anche col miglior canale disponibile un qualche livello
di degrado rimane sempre e questo produce ERRORI di
TRASMISSIONE. Ma cos'Š un errore di trasmissione ?
Il caso pi— semplice Š che i dati da trasmettere siano
codificati con soli due simboli..i soliti UNO e ZERO, come
appunto succede col nostro packet radio: allora se viene
trasmesso un UNO ed il ricevitore capisce ZERO si Š verificato
un errore. Analogamente se viene trasmesso ZERO ed il riceviore
capisce UNO siamo nella stessa condizione.
Gi…, ma come si fa a sapere se c'Š stato un errore ?
Occorrerebbe che il ricevitore conoscesse gi… la sequenza
trasmessa per poterla confrontare con quella effettivamente
ricevuta ! Bello vero ? Solo che in questo caso la
trasmissione sarebbe del tutto inutile. Le trasmissioni servono
proprio quando il ricevente ignora i messaggi posseduti dal
trasmittente. Le trasmissioni servono ad aumentare le
conoscenze del ricevente il quale cos diminuisce la propria
ignoranza.
Dunque tutti i canali, anche i migiori, qualche errore lo
inducono, per di pi— il ricevente non Š in grado di accorgersi
di eventuali errori se non conosce gi… in precedenza il
messaggio. Stando cos le cose non ci rimarrebbe che strapparci
i capelli o dedicarci alla maglia. Ma dei modi ci sono per
migliorare la situazione. Grazie al lavoro teorico di Claude
Shannon dal 1949 si sa che il tasso di errore di un sistema
trasmissivo, ovvero la percentuale di bit sbagliati sul totale
dei trasmessi, pu• essere reso piccolo a piacere, purchŠ la
velocit… di trasmissione sia inferiore alla massima capacit… C
di quel canale. Ma quanto "piccolo" ? Tanto quanto basta per
le normali applicazioni umane, compresi i trasferimenti dei
fondi da una banca all'altra. In seguito al lavoro teorico di
Shannon molti metodi sono stati trovati per ridurre il tasso di
errori sui canali, avvicinandosi a poco a poco a quel limite
teorico. Questi metodi ci fanno dire che, agli effetti pratici,
una trasmissione avviene senza errori, ma non dobbiamo mai
dimenticare che quello che si riesce a ridurre Š solo la
probabilit… che un errore non sia individuato e corretto.
==> L'individuazione di un errore analizzando un singolo bit Š
impossibile.
E' possibile, al contrario, accorgersi che un certo blocco di
bit ricevuti ne contiene uno o pi— sbagliati aggiungendo a
questo blocco altri bit opportunamente generati (ridondanza).
Quindi per rendere un canale di trasmissione utile per le
applicazioni umane occorre innanzitutto costruirlo bene in modo
che il suo tasso di errore sia il pi— basso possibile ( azioni
sul livello fisico [1]). Gli errori residui possono essere poi
individuati e corretti a livello di blocco (livello di link [2])
con le tecniche che ora vediamo.
PoichŠ nulla al mondo viene gratis la correzione degli errori si
paga con una diminuzione del flusso effettivo di dati trasmessi,
ovvero con una diminuzione dell'efficienza trasmissiva del
sistema.
Il protocollo di Link del nostro AX.25 realizza la tecnica di
individuazione di un blocco (trama) con errori e la sua
correzione tramite RITRASMISSIONE su richiesta. (ARQ Automatic
Repeat reQuest)
Per ogni blocco di bit da trasmettere il trasmettitore calcola
da essi 16 bit aggiuntivi, detti FCS (Frame Check Sequence), con
l'algoritmo del CRC, che significa "Cyclic Redundancy Check".
Questi 16 bit vengono aggiunti ai dati veri che, insieme ad
altre informazioni vanno a formare la trama o frame. ( Ricordo
che noi chiamiamo impropriamente "Pacchetti" le trame che
compongono il livello 2, mentre pi— propriamente dovremmo
chiamare pacchetti solo i blocchi effettivamente instradati dai
nodi al livello 3). Il TNC ricevente analizza i bit ricevuti e
da essi ricalcola i 16 bit di controllo con lo stesso algoritmo
CRC.
Se i 16 bit di CRC ricevuti sono identici ai 16 calcolati
localmente la trama viene accettata. Al contrario ne viene
richiesta la ritrasmissione secondo il protocollo che gi…
conoscete. Chi vuole approfondire l'argomento pu• leggere sul
"Packet Radio Handbook" dell'ARI l'articolo di IW1AYD intitolato
"AX.25, Specifiche del Protocollo Livello 2".
E' importante essere consci del fatto che la tecnica del CRC pu•
occasionalmente fallire ! Pu• , cioŠ, succedere che, pur
essendo stati ricevuti dei bit sbagliati, le due sequenze di 16
bit del CRC siano identiche. Ovviamente la probabilit… di
questo evento Š piuttosto bassa per• essa aumenta con
l'aumentare della lunghezza del blocco su cui il CRC viene
calcolato. Se ne deduce che, se si vuole un'alta affidabilit…,
occorre fare i pacchetti corti il che peggiora l'efficienza
globale. Per un CRC a 16 bit un blocco di 256 byte Š da
ritenersi al limite. Se si vogliono trasmettere blocchi pi—
lunghi occorre generare la sequenza del CRC con pi— bit come
avviene, per esempio sull'Ethernet dove i frame sono da 1518
byte al massimo con 32 bit di CRC.
Un fatto che influenza molto l'efficienza di un link che usi
questa tecnica di correzione degli errori Š il modo in cui gli
errori sono distribuiti nel tempo. Se un link Š affetto da
rumore termico (segnale debole p.es.) allora i bit sbagliati
sono mediamente ben distribuiti nel tempo. Se, al contrario, il
rumore Š di tipo impulsivo ( QRN o motori elettrici ) allora gli
errori arrivano in gruppo: ci sono cioŠ lunghi periodi senza
errori ed altri periodi di errori fitti.
Un frame col CRC sbagliato pu• essere tale sia se c'e' un errore
solo sia se ce ne sono 100. In entrambe i casi va ritrasmesso.
Se ne deduce che per il nostro protocollo di link Š meglio avere
tanti errori concentrati nel tempo che pochi ma ben distribuiti.
Pochi errori ben distribuiti nel tempo possono magari
danneggiare tutti i pacchetti mentre un singolo burst di 100
errori forse danneggia un singolo frame. Quindi errori in burst
sono meglio...si ma fino ad un certo punto perchŠ il CRC
fallisce pi— facilmente se gli errori sono in burst !!
Da queste argomentazioni intuitive si capisce come la misura del
solo tasso di errore ( % di bit errati) pu• non descrivere
totalmente la situazione. E' per questo che gli strumenti
professionali, oltre a misurare il tasso di errore medio
misurano anche i "Secondi senza errori" ed i "Secondi con
errori", nonchŠ in numero di blocchi da 1000 bit con errori
(BLER).
Una seconda e pi— importante deduzione Š che, per avere una
buona efficienza di link, occore curare molto bene i fenomeni
che generano errori equamente distribuiti nel tempo. Ci• si
ottiene curando molto bene i modulatori e demodulatori nonchŠ la
parte radio dei nostri sistemi. Ecco che il rapporto
Segnale/Rumore, che alcuni pacchettari considerano di esclusiva
pertinenza dei DXers, diventa un fattore determinante per la
qualit… del protocollo di livello 2.
Lascio poi ai lettori pi— diligenti (masochisti) la
determinazione della lunghezza ottimale dei frame in funzione
della distribuzione casuale degli errori.
FEC
La tecnica di correzione tramite ritrasmissione ha un grosso
problema che la rende inutilizzabile in alcune situazioni.
Supponiamo di voler fare una connessione in Packet con una
stazione che si trova sulla Luna. [ prima o poi qualche OM
astronauta ci finir… lassu !... o qualche appassionato di DX
Expedition ?]
Come tutti sanno la Luna in media dista dalla terra 390.000 Km,
che alla velocit… di propagazione delle onde radio di 300.000
Km/sec fa circa 1.3 secondi di tempo di propagazione e, quindi,
2.6 fra andata e ritorno. Se il nostro TNC va a 1200 baud sulla
radio e lo impostiamo con MAX 3 e PACLEN 255 allora una
finestra, che Š formata da 3 frame con poco pi— di 6200 bit
viene trasmessa in in 5.2 secondi. Dopo aver trasmesso una
finestra di 3 frame occorre aspettare altri 2.6 secondi per
avere l'OK di ritorno. Ci vogliono quindi 7.8 secondi per
trasmettere 5.2 secondi di dati con uno spreco del 33% !!
Poi la cosa diventerebbe ancora pi— drammatica se il TNC
trasmettesse a 9600 baud (una velocit… ancora bassa), infatti 3
frame verrebero trasmessi in 0.65 secondi ma l'OK potrebbe
arrivare solo dopo 3.25 secondi con uno spreco dell'80 % !!
Decisamente questa tecnica non Š adatta per le comunicazioni
interplanetarie ! ..ed in realt… presenta gi… dei grossi
problemi con canali passanti su satelliti geostazionari con
velocit… di trasmissione abbastanza basse.
Un rimedio parziale consiste nel fare le finestre molto lunghe
(l'HDLC, un protocollo di link professionale, nonno dell'AX.25,
prevede opzionalmente una finestra di 128). Il rimedio decisivo
Š quello di cambiare tecnica. [ Si veda l'articolo sul Voyager
R.R. 4/90 dove si accenna al codice di Golay ed al successivo
Reed-Salomon utilizzati per la protezione dei dati critici ]
Il cambiamento consiste nell'usare degli opportuni codici che
permettano non solo di accorgersi della presanza di errori, ma
anche di correggerli (ovviamente purchŠ il numero degi bit
sbagliati sia contenuto). Questi codici, detti FEC Forward
Error Correction, oltre che nelle comunicazioni con le sonde
interplanetarie, sono per esempio, usati dai Compact Disk (
codice di Reed-Solomon ) come pure nelle RAM dei computer
professionali. Anche i programmi di compressione dei file, tipo
PKZIP, hanno a che fare con la teoria dei codici.
La teoria dei codici Š un argomento vastissimo ed assai
complicato nato nel 1950 col codice di Hamming capace di
correggere un singolo bit sbagliato in un blocco, ed Š ancora in
frenetica evoluzione per mettere in pratica le idee maturate
negli anni '60.
Non tenter• qu di approfondire questo argomento perchŠ Š al di
fuori delle mie competenze; per di pi— la matematica necessaria
rende ogni trattazione troppo complessa per l'hobbista medio.
Quello che per• posso fare Š dare un'idea dei concetti
fondamentali con un facile esempio tratto da un libro
divulgativo che TUTTI I RADIOAMATORI dovrebbero avere sul
comodino. Il libro in questione Š "La Teoria dell'Informazione"
di John R. Pierce edito da Mondadori nella serie EST.
Anche in questo caso la correzione si pu• fare solo lavorando a
blocchi di bit: al blocco da trasmettere vengono aggiunti altri
bit opportunamente calcolati. Il ricevente Š in grado di
recuperare il blocco originale anche se durante il processo di
trasmissione si Š avvenuto un errore su uno o pi— bit. ...ma
vediamo l'esempio.
Supponiamo che si voglia trasmettere un messaggio spezzandolo in
blocchi da 16 bit. Ad ognuno di questi blocchi verranno
aggiunti altri 8 bit "di controllo" calcolati come segue. Ad
esempio uno dei blocchi Š il seguente: [1101001101011000].
Disponiamo questi bit su un quadrato da 4X4:
0 0 1 1
ÚÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄÂÄÄÄÄÄ¿
1 ³ 1 ³ 1 ³ 0 ³ 1 ³
ÃÄÄÄÄÄÅÄÄÄÄÄÅÄÄÄÄÄÅÄÄÄÄÄ´
0 ³ 0 ³ 0 ³ 1 ³ 1 ³
ÃÄÄÄÄÄÅÄÄÄÄÄÅÄÄÄÄÄÅÄÄÄÄÄ´
0 ³ 0 ³ 1 ³ 0 ³ 1 ³
ÃÄÄÄÄÄÅÄÄÄÄÄÅÄÄÄÄÄÅÄÄÄÄÄ´
1 ³ 1 ³ 0 ³ 0 ³ 0 ³
ÀÄÄÄÄÄÁÄÄÄÄÄÁÄÄÄÄÄÁÄÄÄÄÄÙ
I bit di controllo vengono generati analizzando le righe e le
colonne. Per ogni riga e per ogni colonna si scrive 0 se gli
UNI sono in numero pari, altrimenti si scrive 1. Come vedete la
regola Š semplicissima ed in pratica consiste nell'avere sempre
righe o colonne da 5 bit in cui il numero degli UNI Š pari.
Ed ecco cosa succede in caso di un errore su uno dei 16 bit del
blocco: la parit… salta sia in una riga che in una colonna. Il
bit sbagliato (e quindi da invertire) Š proprio quello
all'intersezione delle due. Se l'intersezione fra riga e
colonna Š al di fuori del blocco dei 16 allora l'errore Š stato
su uno dei bit di controllo, il che non ci importa molto.
Dunque trasmettendo 24 bit per significarne 16 riusciamo ad
identificare e correggere blocchi con un bit errato, ossia siamo
in grado di correggere un bit ogni sedici e questo lo paghiamo
con una perdita del 33% del canale. Se si facessero dei blocchi
pi— lunghi, diciano da 400 bit, ne occorrerebbero 40 di agguinta
per la correzione. L'efficienza del canale migliorerebbe, ma
saremmo in grado di correggere un solo bit su 400....Š la solita
storia delle cene gratis !
Questo codice non Š certo il massimo dell'efficienza ed infatti
gli ultimi 40 anni sono stati impiegati nella ricerca di codici
pi— efficienti, ma anche pi— complessi. Alcuni codici molto
interessanti sono stati applicati molti anni dopo la loro
scoperta grazie all'evoluzione delle tecniche di
miniaturizzazione ed integrazione che permettono di realizzare a
bassi costi i complicatissimi circuiti di decodifica.
TRELLIS
Fin'ora abbiamo visto come sia possibile correggere errori
commessi fra il modulatore ed il demodulatore di un sistema di
comunicazione. Esiste per• una terza tecnica di correzione
degli errori di trasmissione che Š intrinsecamente collegata al
modo in cui i processi di modulazione e demodulazione vengono
realizzati. E' come se il livello 1 ed il 2 si mettessero
d'accordo per lavorare insieme e realizzare cos un vantaggio
reciproco.
Questa tecnica si chiama "Modulazione Trellis" ( TCM Trellis
Code Modulation). Per avere un'idea di questa tecnica dovremmo
aver gi… parlato a fondo delle modulazioni, quindi rimanderemo
la trattazione di questo argomento a tempi migliori. Qu vorrei
dare solo qualche notizia generale visto che i modem che
utilizzano questa tecnica, detti V.29, cominciano ad essere
piuttosto comuni.
Il fatto pi— appariscente Š che con questa tecnica di
modulazione si ottiente un miglioramento di almeno 3 ordini di
grandezza del tasso di errori: dove un modem normale, per un
certo rapporto Segale/Rumore, fa in media un blocco sbagliato
ogni 10 un modem Trellis fa un blocco sbaliato ogni 10.000 !!
Il miglioramento Š considerevole ed in pratica permette di usare
velocit… maggiori a parit… di canale trasmissivo: per esempio un
modem Trellis su linea telefonica pu• tranquillamente andare a
14.4 Kbit/sec.
CONCLUSIONI e RACCOMANDAZIONI
Per fare un buon Link fra due nodi di una rete ben fatta occorre
curare molto bene la parte radio e la coppia
Modulatore/Demodulatore compatibilmente con i costi dei medesimi
perchŠ sono queste le parti che generano gli Errori di
Trasmissione. Una volta che l'errore Š avvenuto ci si pu•
affidare solo al protocollo di livello 2 per la sua correzione,
ma questo degrada la performance globale. E' molto sbagliato
affidarsi al solo protocollo di link infischiandosene della
radio...proprio noi che della radio abbiamo il culto !!
Con un p• di attenzione, e soprattutto con scelte accurate e
ragionate, si possono mantenere i Link in buona efficienza.
Tutto quello che conta per fare il DX conta anche per fare un
buon Link e cioŠ la cifra di rumore del ricevitore, la sua
resistenza ai segnali forti sul canale e fuori. L'aspetto MODEM
va poi considerato con grande attenzione specialmente perchŠ la
trasmissione dati via radio pone dei problemi che le
trasmissioni via doppino telefonico non hanno: la tratta radio
con i suoi fading e le riflessioni multiple pu• rendere del
tutto inefficienti i normali modem "telefonici". Se per fare
del packet ruspante anche i 7910 vanno bene, per ottenere buone
prestazioni ci vogliono modem appositamente studiati per la
radio. Per fare e manutenere dei link di una rete dovremo
imparare anche a fare delle misure di qualit… con l'opportuna
strumentazione al fine da valutare, confrontare e tarare le
nostre apparecchiature.
BIBLIOGRAFIA
Il gi… citato "La Teoria dell'Informazione" di J.R.Pierce, EST
Mondadori Š da considerarsi il libro pi— adatto ai Radioamatori.
Infatti contiene idee importantissime per i DXers, i
Microondari, i Satellitari, i VHFrs, gli UHFers, gli EMEisti, i
MeteorScatteristi, gli SWL, i CWisti, i Musicisti, i Linguisti
ed anche i Pacchettari. Anche gli Storici delle
telecomunicazioni troveranno l notizie interessanti.
Il protocollo AX.25 di tipo ARQ Š egregiamente descritto sul
Packet Radio Handbook ARI da IW1AYD.
Il livello fisico [1] Š chiaramente descritto dal CANALE (p.45
RR 7/90) [Beppe che fine hai fatto ? son gi… finiti i tuoi dubbi
?!]
Per la Teoria dei codici si consiglia agli esperti matematici il
libro di R.E.Blahut "Theory and Practice of Error Control Codes"
della Addison-Wesley.
Per restare in Italia vale la pena di leggere nelle serate di
scarsa propagazione "Digital Transmission Theory" di
S.Benedetto, E.Biglieri e V.Castellani del Politecnico di Torino
(Prentice-Hall, Inc).