Protecció contra errors
La protecció contra errors o FEC (Forward Error Correction en anglès), és una tècnica utilitzada en telecomunicacions per simular un canal de transmissió quasi lliure d'errors en canals de radiodifusió, que són medis hostils on existeix un alt risc d'error deguts a conseqüència del soroll o la distorsió introduïts pel medi com per les no linealitats en el mateix sistema de transmissió.[1][2] Això és equivalent a dir que, gràcies a aquesta tècnica, podem assegurar que el senyal obtingut al final del procés serà igual (o pràcticament igual) a l'enviat des de l'emissor. De la mateixa manera, la protecció contra errors és un d'entre els diversos elements que formen el procés de la radiodifusió digital.
La tècnica consisteix en una sèrie de modificacions sobre el senyal principal (les dades útils) abans de ser transmès que, un cop arriba al receptor alterat pel soroll del canal, són decodificades i ajuden a detectar els errors i, per tant, a minimitzar a gran escala la taxa d'errors per bit. Aquestes modificacions es duen a terme en un ordre determinat i a nivells de profunditat diferents. De manera que al receptor es segueix l'ordre invers per descodificar i anar corregint errors fins a les capes superiors on, eventualment, disposarem del senyal original enviat per l'emissor. A grans trets, les modificacions consisteixen en dos conceptes, on s'aprofundirà més endavant:[3]
Tots dos ajuden a reduir la taxa d'errors de bit (BER) en recepció.
Evitar la retransmissió[modifica]
Els blocs de protecció contra errors intenten evitar les retransmissions en models de telecomunicacions on la retransmissió és impossible, com ara una connexió simplex (unidireccional entre emissor i receptor) o costosa (on, per exemple, els enviaments es produeixen des d'un únic emissor a molts receptors i sol·licitar retransmissions col·lapsaria l'emissor i perjudicaria molt el sistema). Els blocs de protecció contra errors, doncs, són afegits a les dades que es volen enviar de manera que, gràcies a aquests, el receptor és capaç d'obtenir taxes d'error de bit molt baixes (gairebé nul·les) sense necessitar retransmissió.
No obstant això, en diversos models de telecomunicacions diferents als esmentats abans, la retransmissió no comporta cap problema. El receptor pot detectar que hi ha hagut un error i sol·licitar la retransmissió del paquet de dades. De fet, existeixen codis híbrids on s'inclouen uns codis FEC a les dades i si la taxa d'errors es detecta molt elevada, es commuta a un sistema de sol·licitud de retransmissió automàtica (ARQ - Authomatic Repeat-Request en anglès)
Sincronisme[modifica]
.jpg)
El sincronisme del receptor és un factor important a l'hora de mantenir unes taxes d'error de bit baixes. En radiodifusió de seqüències binàries (digital), les dades s'envien segons la modulació digital que es trobi més adequada (depenent de les taxes de bit desitjades, l'amplada de banda disponible, etc.). Depenent d'aquesta modulació, un cert nombre de bits s'agrupen en símbols i totes les diferents combinacións possibles amb aquest nombre de bits es mapen en el que s'anomena constel·lació. El sincronisme no és altra cosa que el fet que el receptor sàpiga amb alta precisió on comença i on acaba cada símbol (en quins instants de temps). Per cada possible símbol l'emissor envia un senyal diferenciable dels altres durant un temps que s'anomena temps de símbol. Quan, després d'un temps de símbol, canvia la seqüència binària que hem d'enviar, veiem un canvi en el senyal transmès que s'anomena transició. Quan es dona el cas on s'ha de transmetre consecutivament un mateix símbol no hi ha transicions durant un cert temps. La falta de transicions perjudica la sincronització del receptor, per tant, el que es fa sovint en telecomunicacions és forçar les transicions de manera que, durant aquests períodes on es transmet el mateix, el receptor pugui mantenir el sincronisme.
Un exemple bastant simple d'una codificació que forci les transicions és el codi de marques bifase (BMC-Biphaseal Mark Code, en anglès), que podem veure a la figura 3.
En l'estàndard de radiodifusió digital de televisió DVB, el bloc de protecció contra errors (FEC) inclou un sistema que força les transicions per mantenir el sincronisme del receptor: l'aleatoritzador.
Redundància[modifica]
La redundància és la tècnica que, juntament amb el sincronisme, s'aplica abans de les transmissions per protegir les dades contra errors. Aquesta tècnica consisteix a afegir informació que ja existeix en el paquet de dades (repetir-la). El propòsit de realitzar aquesta redundància de dades és promitjar el soroll de canal. Si enviem les dades sense redundància, per cada element no podem saber si en recepció el soroll tindrà un valor sufucientment baix com perquè el receptor el pugui identificar com és degut. Sabent que el soroll és gaussià de mitja zero, per tant que els seus valors més probables són propers a zero, és poc probable que aquest sigui prou alt com per perjudicar al receptor a l'hora de decidir la dada enviada.
S'ha de dir, això no obstant, que per fer certes les premises anteriors és necessari treballar amb uns paràmetres de SNR (senyal/soroll, signal to noise ratio en anglès) mínims. Això significa que la potència del senyal transmès ha de ser significativament superior que la del soroll del canal, ja que sinó aquest perjudicaria l'enviament de dades no només quan tingués uns valors alts (poc probable), sinó també quan tingués valors mitjans (molt probable), fent de la redundància una tècnica inútil. Assumint aquesta condició, si enviem cada unitat de dades més d'una vegada, els valors que predominim seran gairebé unívocament els que s'hagin enviat realment. Més endavant però, es veurà que molts cops quan el soroll adquireix un valor alt, aquest perjudica a ràfegues de bits consecutius fins a estabilitzar-se, pel qual s'apliquen unes determinades tècniques. Per fer el procés de detecció-correcció d'errors mitjançant redundància es fan servir uns blocs a l'emissor anomenats codificadors i uns blocs anomenats descodificadors en el receptor.
Compromís velocitat/BER[modifica]
Tal com s'ha esmentat anteriorment la redundància s'utilitza per detectar i corregir errors. Segons el tipus de canal i de protocol, s'utilitzen diferents codis FEC amb diferents proporcions de redundància/dades útils.
És obvi que a més redundància s'afegeixi, més reduïda serà la taxa d'errors per bit (BER) i, per tant, serà una transmissió amb menys pèrdues. Com a contrapartida, però, com més redundància s'afegeixi també s'estarà reduint la velocitat útil, ja que s'enviaran menys dades "úniques" per unitat de temps. Tot i que la velocitat de transmissió (bits per segon) es pot optimitzar, acaba estant limitada per l'amplada de banda disponible i l'energía de transmissió.
Per tant, sempre existeix un compromís entre la taxa d'error per bit (BER) i la taxa de bits útils (bit rate). És un cas relacionat amb les configuracions de modulacions digitals on com més bits per símbol més velocitat s'aconsegueix, però a la vegada, més energía de bit es necessita per mantenir les mateixes taxes d'error (figura 6). La màxima capacitat del canal ve determinada matemàticament pel Teorema de Shannon-Hartley, on hi prenen part l'amplada de banda y la relació senyal/soroll.
Com a conclusió es pot dir que, en tot cas, el que es guanya per una banda es perd per l'altra. Tot i així, per a cada configuració i determinat per les seves propietats, hi ha una relació òptima que identifica el grau de redundància més adient que es pot aplicar. De fet, en moltes configuracions, s'utilitza un detector del BER al final de les transmissións que serveix com a remesa pel mateix codi FEC que s'utilitza a l'emissor, de manera que s'acaba trobant el grau de redundància òptim.
Codis de bloc i convolucionals[modifica]
Existeixen dues famílies segons la naturalesa de treball dels codis FEC (codis de bloc i codis convolucionals), que a la vegada determinen dos algoritmes diferents de correcció d'errors (decisió abrupta i decisió suau respectivament).
Els codis de bloc treballen sobre trames de dades de longitud de bits fixa (a nivell de byte) i s'implementen normalment amb algoritmes de decisió abrupta. El fet d'anomenar-se de decisió abrupta és perquè funcionen amb un resultat all or nothing (tot o res), ja que eventualment es redueix a decidir si tot un bloc de dades es correspon a un o a un altre, de manera que afecta a molts bits la decisió que es prengui. El més conegut d'aquesta família és el codi Reed-Solomon (inventat per Irving S. Reed i Gustave Solomon), degut al seu ampli ús en formats com el DBV (de radiodifusió), DVD o CD (d'emmagatzemament), entre molts altres.
Els codis convolucionals, en canvi, treballen sobre trames de longitud definides a lliure albir (a nivell de bit) i s'implementen amb algoritmes de decisió suau. Aquests algoritmes aporten una eficiència molt major que els utilitzats en els codis de bloc (algoritmes de decisió abrupta), ja que es basen en senyals discrets. El més conegut d'aquesta família és el descodificador de Viterbi (inventat per Andrew J.Viterbi), degut al seu ús massiu en tota mena de protocols de telecomunicacions.
Molts codis fec com els LDPC (Low-density Parity-check en anglès) introduits per primer cop per Robert G. Gallager en 1960[3] o els turbocodis[4] s'implementen a base de repetides iteracions de codis de decisió suau (soft-decision codes), i aporten una eficiència molt alta i s'utilitzen abundantment avui dia.
Els codis FEC aplicats normalment, són una concatenació de codificadors de bloc amb codificadors convolucionals (de Viterbi, majoitáriament). Aquests blocs conjunts de codis de bloc més codis convolucionals s'anomenen supercodificadors (en l'emissor) i superdecodificadors (en el receptor). Aquests blocs són formats per uns codificadors/descodificadors externs i interns (outer coders i inner coders, respectivament, en anglès). Els externs corresponen als codis de bloc (referits al fet que executen la seva funció fora del canal) i els interns als codis convolucionals (treballen dins del canal de transmissió).
Model de blocs de FEC: L'estàndard DVB[modifica]
L'estàndard DVB (utilitzat per la radiodifusió actualment en un gran nombre de països) utilitza el contenidor audiovisual MPEG. Aquest format utilitza dos tipus de corrents de dades: el corrent de transport (TS - Transport Stream en anglès) i el corrent de programa (PS - Program stream, en anglès). Aquest últim, el corrent de programa, utilitza canals amb una taxa d'errors molt baixes (CDs, DVDs, dispositius de memòria, etc.) i, per tant, la mida dels paquets és bastant gran. En canvi, el corrent de transport utilitza mides de paquets reduïts i està ideat per radiocomunicacions, on el risc d'errors és més alt. DVB, com a sistema de radiodifusió treballa amb paquets de dades de transport stream i té el seu propi codi de protecció contra errors. En aquest hi formen part diferents blocs i cada un té una funció diferenciada, però que es complementen entre si per aportar baixes taxes d'errors de bit.
Aleatoritzador[modifica]
L'aleatoritzador (randomizer en anglès) s'encarrega de forçar les transicions de 0 a 1 i viceversa per aportar sincronisme a la transmissió com s'ha esmentat anteriorment. El sistema funciona afegint uns canvis al senyal que després són desfets al receptor pel desaleatoritzador. Principalment hi ha dos tipus d'aleatoritzadors, l'additiu i el multiplicatiu. El que s'utilitza en DVB és l'aleatoritzador additiu. Al senyal a transmetre hi és sumat un codi seqüencial pseudo-aleatori que força les transicions i dispersa l'energía en tota la seqüència reduint les interferències. El desaleatoritzador en recepció desfà aquest canvi mitjançant exactament el mateix esquema que el l'aleatoritzador de l'emissor, deixant el senyal tal com era originalment.
Codificador Reed-Solomon[modifica]
El codificador Reed-Solomon, del qual s'ha parlat anteriorment, resulta el més eficient a l'hora de corregir blocs de dades erronis. Funciona afegint una quantitat X de bytes de redundància al paquet a enviar. En recepció, es defineix una capacitat de corregir fins a X/2 bytes erronis. La notació que s'utliliza per les diferents variants d'aquesta codificació és (n,k) on n és el nombre de bytes totals del paquet i k és el nombre de bytes que no són de redundància. Un exemple de variant és la que s'aplica a MPEG2-TS; la (204,188), on en haver-hi 16 bytes de redundància, se'n poden corregir fins a 8 erronis en recepció.
Dispersor (Interleaver)[modifica]
El dispersor complementa el codificador Reed-Solomon perquè aquest pugui treballar eficientment. Com que el Reed-Solomon només pot corregir un màxim nombre de bytes erronis per paquet, el problema que sorgeix és degut a un esdeveniment freqüent en els canals de radiodifusió: les ràfegues d'error de bit. Aquestes, tal com el seu nom indica, provoquen una sèrie d'errors consecutius sobre el paquet de dades. Si es produeixen més d'un cert nombre de bytes erronis sobre un mateix paquet de dades el Reed-Solomon pot no ser capaç de corregir els errors pel fet que existeixi un nombre d'errors en un paquet més gran del que el codificador pot resoldre. Per solucionar aquest problema s'afegeix el bloc del inter-leaver, que dispersa els bytes dels diferents paquets entre si perquè el Reed-Solomon pugui actuar correctament (menys bytes erronis per paquet).
A continuació es mostra un exemple de com funciona el dispersor, basat en la figura 9:
- Es mostra un exemple de paquets formats per 2 bytes no redundants i 2 bytes de redundància (4,2).
- Es produeix una ràfega d'errors sobre el bloc blau (3 errors).
- El codificador Reed-Solomon, només pot corregir 2 errors per bloc. Es perd el paquet blau.
- Solució: Tenim el mateix cas que en el punt 1. Els bytes dels diversos blocs es dispersen i es barregen entre si.
- Es produeix la mateixa ràfega d'errors de bit, però aquest cop sobre bytes pertanyents a blocs diferents.
- Es recomponen els paquets i el Reed-Solomon és capaç de corregir els errors.
- Obtenim els paquets lliures d'errors.
És evident que com més paquets sigui capaç de dispersar els bytes entre si, més útil serà el dispersor. Aquesta capacitat s'anomena profunditat, i en DVB s'estandarditza una profunditat de 12 bytes. A la variant terrestre de DVB, existeix un segon dispersor a la cadena FEC que treballa a nivell de bit, fent el codi més robust encara contra les ràfegues d'errors.
Codis convolucionals[modifica]
Els codis convolucionals formen el inner-coder i protegeixen la informació a nivell de bit. Només s'utilitzen, però, a les variants DVB de satèl·lit i terrestre. Aquests codis funcionen afegint redundància per cada bit, amb diferents proporcions seleccionables (1/2, 2/3, 3/4, 5/6 i 7/8). Això significa que, per exemple en un model de redundància 2/3, de cada 3 bits que s'enviïn 2 seran de redundància. Els codis convolucionals en recepció es descodifiquen amb l'algoritme de Viterbi, i es pot identificar si hi ha hagut un error quan per un paquet de bits (per exemple amb un model 2/3, per cada 3 bits), hi ha zeros i uns. Quan, en canvi, tot el conjunt de bits és igual, significa que aquest és lliure d'errors.
A continuació es mostra un exemple per un cas "1/2" de redundància del que s'ha esmentat:
| Bits a enviar | Bits rebuts |
|---|---|
| 00 | 00 (lliure d'errors) |
| 00 | 01 (es produeix un error) |
| 11 | 10 (es produeix un error) |
| 11 | 11 (lliure d'errors) |
Quan es detecta un error, l'algoritme de Viterbi calcula el valor que s'ha enviat mitjançant el criteri de màxima versemblança. Aquest consisteix a calcular la mínima distància de Hamming que té tot un procés matemàtic al darrere i que assegura una mínima probabilitat d'error en cada decisió.
Tal com s'ha explicat anteriorment, un major grau de redundància ofereix més robustesa contra els errors però també fa necessari més amplada de banda per transmetre el mateix volum de dades.
Aplicacions[modifica]
Referències[modifica]
- ↑ Miguel Calvo Ramón, Ramón Martínez Rodríguez-Osorio Codificación de Canal Arxivat 2023-03-30 a Wayback Machine., ETSIT
- ↑ José M. Martínez Codificación de Canal, Universitat Autònoma de Madrid
- ↑ 3,0 3,1 Constantino Pérez Vega Codificación de Canal
- ↑ Enrie Armengol Roig, J.A. Delgado-Penín LOS "TURBO-CODIGOS", NUEVOS SUBSISTEMAS DE CODIFICACIÓN DE CANAL PARA MEJORAR LA TRANSMISION DIGITAL DE GRAN CAPACIDAD