Codice del rapace - Raptor code

Questo articolo riguarda i codici di correzione degli errori. Per codebase denominate raptor, vedere Raptor (disambigua) .

In informatica , i codici Raptor ( rap id tor nado ; vedi codici Tornado ) sono la prima classe conosciuta di codici fontana con codifica e decodifica temporale lineare. Sono stati inventati da Amin Shokrollahi nel 2000/2001 e sono stati pubblicati per la prima volta nel 2004 come abstract esteso. I codici Raptor sono un significativo miglioramento teorico e pratico rispetto ai codici LT , che sono stati la prima classe pratica di codici fontana .

I codici Raptor, come i codici fontana in generale, codificano un dato blocco di dati sorgente costituito da un numero k di simboli sorgente di uguale dimensione in una sequenza potenzialmente illimitata di simboli di codifica in modo tale che la ricezione di qualsiasi k o più simboli di codifica consenta al blocco sorgente di essere recuperato con qualche probabilità diversa da zero. La probabilità che il blocco sorgente possa essere recuperato aumenta con il numero di simboli di codifica ricevuti sopra k che diventa molto vicino a 1, una volta che il numero di simboli di codifica ricevuti è solo leggermente maggiore di k . Ad esempio, con l'ultima generazione di codici Raptor, i codici RaptorQ , la possibilità di errore di decodifica quando sono stati ricevuti simboli di codifica k è inferiore all'1% e la possibilità di errore di decodifica quando sono stati ricevuti simboli di codifica k+2 è inferiore di uno su un milione. (Vedi la sezione Probabilità di ripristino e sovraccarico di seguito per ulteriori discussioni su questo.) Un simbolo può essere di qualsiasi dimensione, da un singolo byte a centinaia o migliaia di byte.

I codici dei rapaci possono essere sistematici o non sistematici. Nel caso sistematico, i simboli del blocco sorgente originale, cioè i simboli sorgente, sono inclusi nell'insieme dei simboli di codifica. Alcuni esempi di un codice Raptor sistematico sono l'uso da parte del 3rd Generation Partnership Project nella trasmissione e multicasting wireless cellulare mobile , e anche dagli standard DVB-H per il datacast IP su dispositivi palmari (vedi collegamenti esterni). I codici Raptor utilizzati in questi standard sono definiti anche in IETF RFC 5053.

I codici online sono un esempio di codice fontana non sistematico.

Codice RaptorQ

La versione più avanzata di Raptor è il codice RaptorQ definito in IETF RFC 6330. Il codice RaptorQ è un codice sistematico, può essere implementato in modo da ottenere prestazioni di codifica e decodifica in tempo lineare, ha proprietà di ripristino quasi ottimali (vedere Probabilità di ripristino e sezione aerea di seguito per maggiori dettagli), supporta fino a 56.403 simboli di origine e può supportare un numero essenzialmente illimitato di simboli di codifica.

Il codice RaptorQ definito in IETF RFC 6330 è specificato come parte dello standard Next Gen TV ( ATSC 3.0 ) per consentire lo streaming video di trasmissione di alta qualità (TV mobile robusta) e la consegna di file di trasmissione efficiente e affidabile (datacasting). In particolare, il codice RaptorQ è specificato in A/331: Segnalazione, consegna, sincronizzazione e protezione dagli errori all'interno di ATSC 3.0 (vedi Elenco degli standard ATSC per un elenco delle parti standard ATSC 3.0). Next Gen TV (ATSC 3.0) va ben oltre la TV tradizionale per fornire una trasmissione Internet che consente servizi generali di consegna dei dati.

Panoramica

I codici Raptor sono formati dalla concatenazione di due codici.

Un codice di cancellazione a tasso fisso , di solito con un tasso piuttosto elevato, viene applicato come "precodice" o "codice esterno". Questo pre-codice può essere esso stesso una concatenazione di più codici, ad esempio nel codice standardizzato da 3GPP un codice di controllo di parità ad alta densità derivato dalla sequenza Gray binaria è concatenato con un semplice codice di controllo di parità a bassa densità regolare . Un'altra possibilità sarebbe una concatenazione di un codice Hamming con un codice di controllo di parità a bassa densità.

Il codice interno prende il risultato dell'operazione di precodifica e genera una sequenza di simboli di codifica. Il codice interno è una forma di codici LT . Ciascun simbolo di codifica è lo XOR di un insieme di simboli scelti in modo pseudocasuale dall'output pre-codice. Il numero di simboli che sono XOR'ed insieme per formare un simbolo di uscita è scelto in modo pseudo-casuale per ogni simbolo di uscita secondo una specifica distribuzione di probabilità.

Questa distribuzione, così come il meccanismo per generare numeri pseudo-casuali per campionare questa distribuzione e per scegliere i simboli da sottoporre a XOR, devono essere noti sia al mittente che al destinatario. In un approccio, ogni simbolo è accompagnato da un identificatore che può essere usato come seme per un generatore di numeri pseudo-casuali per generare queste informazioni, con lo stesso processo seguito sia dal mittente che dal destinatario.

Nel caso di codici Raptor non sistematici, i dati sorgente da codificare vengono utilizzati come input per la fase di pre-codifica.

Nel caso di codici Raptor sistematici, l'ingresso alla fase di pre-codifica è ottenuto applicando dapprima ai dati sorgente l'inverso dell'operazione di codifica che genera i primi k simboli di uscita. Pertanto, l'applicazione della normale operazione di codifica ai simboli risultanti fa sì che i simboli sorgente originali vengano rigenerati come primi k simboli di output del codice. È necessario garantire che i processi pseudocasuali che generano i primi k simboli di output generino un'operazione invertibile.

decodifica

Sono possibili due approcci per la decodifica dei codici Raptor. In un approccio concatenato, il codice interno viene decodificato per primo, utilizzando un algoritmo di propagazione delle credenze, come utilizzato per i codici LT. La decodifica ha esito positivo se questa operazione recupera un numero sufficiente di simboli, in modo che il codice esterno possa recuperare i simboli rimanenti utilizzando l'algoritmo di decodifica appropriato per quel codice.

In un approccio combinato, le relazioni tra simboli definite sia dal codice interno che da quello esterno sono considerate come un unico insieme combinato di equazioni simultanee che possono essere risolte con i soliti mezzi, tipicamente per eliminazione gaussiana .

Complessità computazionale

I codici Raptor richiedono tempo O (dimensione del simbolo) per generare un simbolo di codifica da un blocco di origine e richiedono tempo O (dimensione del blocco di origine) per recuperare un blocco di origine da almeno k simboli di codifica.

Probabilità di recupero e sovraccarico

Il sovraccarico è quanti simboli di codifica aggiuntivi oltre al numero k di simboli di origine nel blocco di origine originale devono essere ricevuti per recuperare completamente il blocco di origine. (In base a considerazioni di teoria dell'informazione elementare, il ripristino completo di un blocco sorgente con k simboli sorgente non è possibile se vengono ricevuti meno di k simboli di codifica.) La probabilità di ripristino è la probabilità che il blocco sorgente venga completamente recuperato dopo aver ricevuto un dato numero di simboli di codifica casuali generati dal blocco sorgente.

Il codice RaptorQ specificato in IETF RFC 6330 ha il seguente compromesso tra probabilità di ripristino e sovraccarico di ripristino:

  • Probabilità di ripristino superiore al 99% con sovraccarico di 0 simboli (recupero da k simboli di codifica ricevuti).
  • Probabilità di recupero maggiore del 99,99% con sovraccarico di 1 simbolo (recupero da k+1 simboli di codifica ricevuti).
  • Probabilità di ripristino superiore al 99,9999% con sovraccarico di 2 simboli (recupero da k+2 simboli di codifica ricevuti).

Queste istruzioni valgono per l'intero intervallo di k supportato in IETF RFC 6330, ovvero k =1,...,56403. Vedere IETF RFC 6330 per maggiori dettagli.

Stato legale

Qualcomm, Inc. ha pubblicato una dichiarazione IPR per il codice Raptor specificato in IETF RFC 5053 e una dichiarazione IPR per il codice RaptorQ più avanzato specificato in IETF RFC 6330. Queste dichiarazioni rispecchiano l'impegno di licenza che Qualcomm, Inc. ha assunto rispetto a lo standard MPEG DASH . Lo standard MPEG DASH è stato implementato da un'ampia varietà di aziende, comprese le aziende membri del DASH Industry Forum.

Guarda anche

Appunti


Riferimenti

  • Shokrollahi, Amin, "Codici Raptor", IEEE Transactions on Information Theory, vol. 52, pp. 2551-2567, 2006. PDF (richiede il login)
  • ATSC 3.0 (Comitato per gli standard televisivi avanzati 3.0)
  • 3GPP (Il progetto di partenariato di terza generazione)
  • DVB (trasmissione video digitale)
  • 3GPP TS26.346 3GPP Specifiche tecniche per il servizio Multimedia Broadcast/Multicast: protocolli e codec.
  • RFC5053 Raptor Forward Error Correction Scheme per la consegna degli oggetti
  • Specifiche di trasmissione dati IP DVB-H
  • RFC6330 RaptorQ Forward Error Correction Scheme per la consegna degli oggetti
  • [1] Risultato di ricerca "IPR" per RFC 5053, con dichiarazioni di alcuni proprietari di brevetti
  • [2] Risultato della ricerca "IPR" per RFC 6330, con dichiarazioni di alcuni proprietari di brevetti