Interleaving
Da Wikipedia, l'enciclopedia libera.
L' Interleaving (letteralmente interfogliamento, l'atto di ridisporre in maniera diversa una pila ordinata di fogli cartacei), in informatica e telecomunicazioni, è una tecnica utilizzata per disporre i dati in maniera non contigua, al fine di migliorare le prestazioni in caso di errori a pacchetto. 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, 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 è alla base dell'utilizzo dei turbo codici.
Indice |
[modifica] L'interleaving nella trasmissione dati
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 d'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.
Si guardi qui per una rappresentazione grafica dell'interleaving.
[modifica] Vantaggi
- 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.
[modifica] Svantaggi
- La latenza di trasmissione e i requisiti di memoria del de/codificatore aumentano.
[modifica] Utilizzo in internet
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.
