Interleaving
In informatica e telecomunicazioni con il termine Interleaving (letteralmente interfogliamento, l'atto di ridisporre in maniera diversa una pila ordinata di fogli cartacei), si indica una tecnica di elaborazione di un segnale digitale utilizzata nelle trasmissioni digitali per disporre i dati in maniera non contigua al fine di migliorare le prestazioni in termini di rilevazione e correzione di errori in ricezione nel caso di errori multipli a pacchetto, cioè consecutivi. Esso è un processo che dispone in maniera apparentemente disordinata un certo numero di oggetti ordinati. L'operazione inversa, usata al fine di ricostituire l'ordine originario dei dati, prende il nome di deinterleaving.
L'interleaving viene principalmente usato nella comunicazione dati, nei file multimediali, nella trasmissione via radio (per esempio, su satellite o sulla TV digitale o su ADSL). Storicamente, l'interleaving è stato anche usato per l'immagazzinamento di dati ordinati su disco rigido. L'interleaving viene utilizzato anche nei supporti ottici (CD-ROM, DVD, etc) per proteggere i dati da graffi e danni al supporto di memorizzazione.
L'interleaving è alla base dell'utilizzo dei turbo codici.
L'interleaving nella trasmissione dati[modifica | modifica wikitesto]
Attualmente, l'interleaving viene usato soprattutto nella tecnologia digitale di trasmissione dati, per proteggere la trasmissione da pacchetti con errori. Questo genere di errori ha la caratteristica di sovrascrivere o modificare un gran numero di bit trasmessi consecutivamente, anche se ciò avviene non molto frequentemente. In genere i dati sono trasmessi (indipendentemente dal fatto che si usi l'interleaving o meno) assieme a bit di controllo, che permettono al decodificatore di canale (al ricevitore) la correzione di un certo numero di bit errati. Se si verifica l'evento di un pacchetto di errori, un numero troppo grande di bit viene cancellato e i dati originari non possono più essere recuperati. Invece, se si usa l'interleaving, il decodificatore può riuscire a determinare i bit trasmessi.
Utilizziamo il seguente esempio. Applichiamo un codice di correzione dall'errore molto semplice (detto codice a ripetizione), nel quale la parola di codice viene formata replicando per quattro volte il dato di messaggio:
messaggio ==> a b c d e f g messaggio codificato ==> aaaabbbbccccddddeeeeffffgggg
Se un errore di trasmissione modifica il 13° bit trasmesso (sostituito con una "X"), il decodificatore riesce sicuramente a capire quale è stato il dato trasmesso (decodifica a maggioranza):
messaggio ricevuto ==> aaaabbbbccccXdddeeeeffffgggg messaggio decodificato (a maggioranza) ==> a b c d e f g
Se si verifica un evento d'errore a pacchetto, ad esempio dal 12º al 15º bit, non si riesce più a decodificare con certezza la parola di codice "dddd" (mancata o sbagliata decodifica, a seconda del tipo di codice di correzione utilizzato):
messaggio ricevuto ==> aaaabbbbcccXXXXdeeeeffffgggg messaggio decodificato (a maggioranza) ==> a b c ? e f g
Vediamo ora cosa succede se applichiamo una semplice legge di interleaving sui bit trasmessi:
messaggio ==> a b c d e f g messaggio codificato ==> aaaabbbbccccddddeeeeffffgggg messaggio codificato con interleaving ==> abcdefgabcdefgabcdefgabcdefg messaggio ricevuto con errori ==> abcdefgabcdXXXXbcdefgabcdefg messaggio ricevuto dopo deinterleaving ==> aaXabbbbccccddddeXeefXffgXgg messaggio decodificato (a maggioranza) ==> a b c d e f g
Stavolta si nota che, nonostante gli errori si siano sparpagliati su più parole di codice, tutte possono essere ricostruite con la regola della maggioranza, ed il messaggio originale è perfettamente determinato.
Ovviamente, così facendo si introduce una latenza, perché il messaggio interfogliato deve essere trasmesso dopo che la regola di sparpagliamento è stata applicata su un certo numero di bit codificati.
Vantaggi[modifica | modifica wikitesto]
- La comunicazione è protetta da pacchetti d'errore non troppo frequenti.
- Non si usano ulteriori bit di protezione, a parte quelli normalmente usati per difendersi da errori isolati: la banda utilizzata è la stessa.
Svantaggi[modifica | modifica wikitesto]
- La latenza di trasmissione e i requisiti di memoria del de/codificatore aumentano.
Utilizzo in internet[modifica | modifica wikitesto]
L'interleaving può essere utilizzato anche per i collegamenti DSL, nella comunicazione tra router dell'utente e DSLAM alla centrale del provider. In questo caso si parla di modalità interleaved, in contrapposizione alla modalità FastPath che non utilizza questa protezione e richiede sempre la ritrasmissione dei pacchetti errati.
La modalità interleaved risulta più efficiente nei collegamenti con una percentuale di errore relativamente alta. La modalità fast ha il vantaggio su linee affidabili di snellire la comunicazione e abbassare i tempi di latenza, molto utile ad esempio con software di gioco in rete e programmi di telefonia VoIP che richiedono bassi tempi di risposta e una percettibilità dell'errore più bassa rispetto ad altri tipi di trasmissione, per esempio la trasmissione di un documento.
Memorie[modifica | modifica wikitesto]
I computer moderni possono gestire la memoria con la modalità interleaving. Questa modalità prevede le presenza di almeno due banchi di memoria indipendenti e nella modalità più semplice prevede che un banco contenga gli indirizzi di memoria pari mentre l'altro banco contenga gli indirizzi dispari. Quando il processore accede alla memoria il controller della memoria manda le richieste di lettura ad entrambi i banchi in modo da leggere l'indirizzo richiesto e il successivo. Questa modalità di funzionamento risulta conveniente dal punto di vista delle prestazioni dato che per il principio di località quando il processore accede a una locazione molto probabilmente accederà anche a quella successiva. Mandando la richiesta di entrambi gli indirizzi il controller riceve entrambe le locazioni con il tempo di accesso di una sola locazione in modo da poter rispondere subito alla richiesta successiva. Questo riduce gli stalli del processore e quindi migliora le prestazioni.
