Codice di trasformazione Luby - Luby transform code

In informatica , i codici di trasformazione Luby ( codici LT ) sono la prima classe di codici fontana pratici che sono codici di correzione della cancellazione quasi ottimali . Sono stati inventati da Michael Luby nel 1998 e pubblicati nel 2002. Come alcuni altri codici fontana , i codici LT dipendono da grafi bipartiti sparsi per scambiare l'overhead di ricezione per la velocità di codifica e decodifica. La caratteristica distintiva dei codici LT consiste nell'utilizzare un algoritmo particolarmente semplice basato sull'esclusiva o operazione ( ) per codificare e decodificare il messaggio.

I codici LT sono rateless perché l'algoritmo di codifica può in linea di principio produrre un numero infinito di pacchetti di messaggi (cioè, la percentuale di pacchetti che devono essere ricevuti per decodificare il messaggio può essere arbitrariamente piccola). Sono codici di correzione della cancellazione perché possono essere utilizzati per trasmettere dati digitali in modo affidabile su un canale di cancellazione .

La prossima generazione oltre ai codici LT sono i codici Raptor (vedi ad esempio IETF RFC 5053 o IETF RFC 6330), che hanno codifica e decodifica in tempo lineare. I codici Raptor sono fondamentalmente basati sui codici LT, ovvero la codifica per i codici Raptor utilizza due fasi di codifica, dove la seconda fase è la codifica LT. Allo stesso modo, la decodifica con i codici Raptor si basa principalmente sulla decodifica LT, ma la decodifica LT è mescolata con tecniche di decodifica più avanzate. Il codice RaptorQ specificato in IETF RFC 6330, che è il codice fontana più avanzato, ha probabilità di decodifica e prestazioni di gran lunga superiori rispetto all'utilizzo solo di un codice LT.

Perché usare un codice LT?

Lo schema tradizionale per il trasferimento dei dati attraverso un canale di cancellazione dipende da una comunicazione bidirezionale continua.

  • Il mittente codifica e invia un pacchetto di informazioni.
  • Il ricevitore tenta di decodificare il pacchetto ricevuto. Se può essere decodificato, il ricevitore invia una conferma al trasmettitore. In caso contrario, il ricevitore chiede al trasmettitore di inviare nuovamente il pacchetto.
  • Questo processo bidirezionale continua fino a quando tutti i pacchetti nel messaggio sono stati trasferiti con successo.

Alcune reti, come quelle utilizzate per la trasmissione wireless cellulare, non dispongono di un canale di feedback. Le applicazioni su queste reti richiedono ancora affidabilità. I codici fontana in generale, e i codici LT in particolare, aggirano questo problema adottando un protocollo di comunicazione essenzialmente unidirezionale.

  • Il mittente codifica e invia un pacchetto dopo l'altro di informazioni.
  • Il ricevitore valuta ogni pacchetto man mano che viene ricevuto. In caso di errore, il pacchetto errato viene scartato. Altrimenti il ​​pacchetto viene salvato come parte del messaggio.
  • Alla fine il destinatario ha abbastanza pacchetti validi per ricostruire l'intero messaggio. Quando l'intero messaggio è stato ricevuto con successo, il ricevitore segnala che la trasmissione è completa.

Come accennato in precedenza, il codice RaptorQ specificato in IETF RFC 6330 supera in pratica un codice LT.

Codifica LT

Il processo di codifica inizia dividendo il messaggio non codificato in n blocchi di lunghezza approssimativamente uguale. I pacchetti codificati vengono quindi prodotti con l'aiuto di un generatore di numeri pseudocasuali .

  • Il grado d , 1 ≤  d  ≤  n , del pacchetto successivo è scelto a caso.
  • Esattamente d blocchi dal messaggio vengono scelti a caso.
  • Se M i è l' i- esimo blocco del messaggio, la porzione di dati del pacchetto successivo viene calcolata come
dove { i 1 ,  i 2 , …,  i d } sono gli indici scelti casualmente per i d blocchi inclusi in questo pacchetto.
  • Al pacchetto codificato viene aggiunto un prefisso, che definisce quanti blocchi n sono presenti nel messaggio, quanti blocchi d sono stati ordinati in modo esclusivo nella porzione di dati di questo pacchetto e l'elenco degli indici { i 1 ,  i 2 , …,  io d }.
  • Infine, al pacchetto viene applicata una qualche forma di codice di rilevamento degli errori (magari semplice come un controllo di ridondanza ciclica ) e il pacchetto viene trasmesso.

Questo processo continua finché il destinatario non segnala che il messaggio è stato ricevuto e decodificato con successo.

Decodifica LT

Il processo di decodifica utilizza l'operazione " esclusivo o " per recuperare il messaggio codificato.

  • Se il pacchetto corrente non è pulito o se replica un pacchetto che è già stato elaborato, il pacchetto corrente viene scartato.
  • Se il pacchetto corrente ricevuto in modo pulito è di grado d  > 1, viene prima elaborato rispetto a tutti i blocchi completamente decodificati nell'area di accodamento messaggi (come descritto più dettagliatamente nel passaggio successivo), quindi archiviato in un'area buffer se il suo grado ridotto è maggiore di 1.
  • Quando viene ricevuto un nuovo pacchetto pulito di grado d  = 1 (blocco M i ) (o il grado del pacchetto corrente viene ridotto a 1 dal passaggio precedente), viene spostato nell'area di accodamento dei messaggi e quindi confrontato con tutti i pacchetti di grado d  > 1 residenti nel buffer. Viene memorizzato in modo esclusivo nella porzione di dati di qualsiasi pacchetto bufferizzato che è stato codificato utilizzando M i , il grado di quel pacchetto corrispondente viene decrementato e l'elenco degli indici per quel pacchetto viene adattato per riflettere l'applicazione di M i .
  • Quando questo processo sblocca un blocco di grado d  = 2 nel buffer, quel blocco viene ridotto al grado 1 e viene a sua volta spostato nell'area di accodamento dei messaggi, quindi elaborato contro i pacchetti rimasti nel buffer.
  • Quando tutti gli n blocchi del messaggio sono stati spostati nell'area di accodamento messaggi, il ricevitore segnala al trasmettitore che il messaggio è stato decodificato con successo.

Questa procedura di decodifica funziona perché A  A  = 0 per qualsiasi stringa di bit A . Dopo che d  − 1 blocchi distinti sono stati ordinati in modo esclusivo in un pacchetto di grado d , il contenuto originale non codificato del blocco non abbinato è tutto ciò che rimane. Nei simboli abbiamo  

Variazioni

Sono possibili diverse varianti dei processi di codifica e decodifica sopra descritti. Ad esempio, invece di anteporre a ciascun pacchetto un elenco degli indici di blocco dei messaggi effettivi { i 1 ,  i 2 , …,  i d }, l'encoder potrebbe semplicemente inviare una breve "chiave" che funge da seme per il generatore di numeri pseudocasuali (PRNG) o tabella degli indici utilizzata per costruire l'elenco degli indici. Poiché il ricevitore dotato dello stesso RNG o tabella degli indici può ricreare in modo affidabile l'elenco "casuale" di indici da questo seme, il processo di decodifica può essere completato con successo. In alternativa, combinando un semplice codice LT di basso grado medio con un robusto codice di correzione degli errori, è possibile costruire un codice raptor che nella pratica supererà un codice LT ottimizzato.

Ottimizzazione dei codici LT

Esiste un solo parametro che può essere utilizzato per ottimizzare un codice LT lineare: la funzione di distribuzione dei gradi (descritta come generatore di numeri pseudocasuali per il grado d nella sezione di codifica LT sopra). In pratica gli altri numeri "casuali" (la lista degli indici {  i 1 ,  i 2 , …,  i d  } ) sono invariabilmente presi da una distribuzione uniforme su [0, n ), dove n è il numero di blocchi in cui messaggio è stato diviso.

Lo stesso Luby ha discusso la " distribuzione di solitoni ideale " definita da

Questa distribuzione dei gradi teoricamente riduce al minimo il numero previsto di parole di codice ridondanti che verranno inviate prima che il processo di decodifica possa essere completato. Tuttavia, la distribuzione di solitoni ideale non funziona bene in pratica perché qualsiasi fluttuazione attorno al comportamento previsto rende probabile che a un certo punto del processo di decodifica non ci sarà alcun pacchetto disponibile di grado 1 (ridotto), quindi la decodifica fallirà. Inoltre, alcuni dei blocchi originali non verranno modificati in nessuno dei pacchetti di trasmissione. Pertanto, in pratica, alla distribuzione ideale si sostituisce una distribuzione modificata, la " distribuzione di solitoni robusti ". L'effetto della modifica è, in genere, di produrre più pacchetti di grado molto piccolo (circa 1) e meno pacchetti di grado maggiore di 1, salvo un picco di pacchetti di quantità abbastanza grande scelta per garantire che tutti i blocchi originali vengano incluso in qualche pacchetto.

Guarda anche

Note e riferimenti

  1. ^ a b M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.
  2. ^ L'operazione esclusiva o (XOR), simboleggiata da ⊕, ha la proprietà molto utile che A  ⊕  A  = 0, dove A è una stringa arbitraria di bit .
  3. ^ Codici Fountain , di DJC MacKay, pubblicati per la prima volta in IEEE Proc.-Commun., Vol. 152, n. 6, dicembre 2005.
  4. ^ a b Ottimizzazione della distribuzione dei gradi dei codici LT con un approccio al campionamento di importanza , di Esa Hyytiä, Tuomas Tirronen e Jorma Virtamo (2006).

link esterno