Cod de corecție a erorilor concatenate - Concatenated error correction code

În teoria codificării , codurile concatenate formează o clasă de coduri de corecție a erorilor care sunt derivate prin combinarea unui cod interior și un cod exterior . Dave Forney a fost conceput în 1966 ca o soluție a problemei găsirii unui cod care are atât scăderea exponențială a probabilității de eroare, cu creșterea lungimii blocului, cât și a complexității decodificării în timp polinomial . Codurile concatenate au devenit utilizate pe scară largă în comunicațiile spațiale în anii '70.

fundal

Câmpul de codare a canalului este preocupat de trimiterea unui flux de date la cea mai mare rată posibilă pe un canal de comunicații dat , și apoi decodarea datelor originale în mod fiabil la receptor, folosind algoritmi de codificare și decodare care sunt fezabili pentru a fi implementate într-o tehnologie dată.

Teorema de codare a canalului lui Shannon arată că, în multe canale comune, există scheme de codificare a canalelor care sunt capabile să transmită date în mod fiabil la toate ratele mai puțin de un anumit prag , numit capacitatea canalului dat. De fapt, probabilitatea erorii de decodare poate fi făcută să scadă exponențial pe măsură ce lungimea blocului schemei de codare merge la infinit. Cu toate acestea, complexitatea unei scheme optime de decodare optimă care calculează pur și simplu probabilitatea fiecărui cod de cuvânt transmis transmis crește exponențial , astfel încât un astfel de decoder optim devine rapid imposibil de făcut. ${\ displaystyle R}$${\ displaystyle C}$${\ displaystyle N}$${\ displaystyle N}$

În teza sa de doctorat , Dave Forney a arătat că codurile concatenate pot fi utilizate pentru a obține scăderea exponențială a probabilităților de eroare la toate ratele de date mai mici decât capacitatea, cu o complexitate de decodare care crește doar polinomial cu lungimea blocului de cod.

Descriere

Prezentarea schematică a unui cod concatenat construit pe un cod interior și un cod exterior.

Aceasta este o reprezentare picturală a unei concatenări de cod și, în special, codul Reed – Solomon cu n = q = 4 și k = 2 este folosit ca cod extern și codul Hadamard cu n = q și k = log q este folosit ca cod interior. În general, codul concatenat este un -code.${\ displaystyle [q ^ {2}, k \ log q]}$

Fie C _într- un cod [ n , k , d ], adică un cod de lungime n , dimensiunea k , distanța minimă de Hamming d și rata r = k / n , peste un alfabet A :

${\ displaystyle C_ {in}: A ^ {k} \ rightarrow A ^ {n}}$

Lăsați C _afară să fie o [ N , K , D ] cod peste un alfabet B cu | B | = | A | simboluri ^k :

${\ displaystyle C_ {out}: B ^ {K} \ rightarrow B ^ {N}}$

Codul interior C _în are unul din | A | ^k = | B | intrări posibile, codifică într-o n- triplă peste A , transmite și decodează într-unul din | B | ieșiri posibile. Noi considerăm acest lucru ca un (super - ) canal care poate transmite un simbol din alfabetul B . Noi folosim acest canal N ori pentru a transmite fiecare dintre cele N simboluri într - un cuvânt de cod C _out . Concatenarea de C _afară (ca cod extern) cu C _în (sub formă de cod interior), notat C _din ∘ C _în , este astfel un cod de lungime Nn peste alfabetul A :

${\ displaystyle C_ {out} \ circ C_ {in}: A ^ {kK} \ rightarrow A ^ {nN}}$

Acesta mapează fiecare mesaj de intrare m = ( m ₁ , m ₂ , ..., m _K ) către un cod cod ( C _în ( m ' ₁ ), C _în ( m ' ₂ ), ..., C _in ( m ' _N )), unde ( m ' ₁ , m ' ₂ , ..., m ' _N ) = C _afară ( m ₁ , m ₂ , ..., m _K ).

Perspectiva esențială a acestei abordări este că dacă C _în este decodificat folosind o abordare de probabilitate maximă (arătând astfel o probabilitate de eroare în scădere exponențială cu lungimea în creștere), iar C _afară este un cod cu lungimea N = 2 ^nr care poate fi decodat în polinom timp de N , atunci codul concatenat poate fi decodat în timp polinomial lungimii sale combinate n 2 ^nr = o ( N ⋅log ( N )) și arată o probabilitate de eroare exponențial în scădere, chiar dacă C _în are o complexitate de decodificare exponențială. Acest lucru este discutat mai detaliat în secțiunea Decodarea codurilor concatenate .

Într - o generalizare a concatenare de mai sus, există N posibile coduri interioare C _{în , i} și i simbolul -lea într - un cuvânt de cod C _out este transmisa prin canalul interior folosind i -lea cod interior. Cele Codurile Justesen sunt exemple de coduri concatenate generalizate, în cazul în care codul extern este un cod Reed-Solomon .

Proprietăți

1. Distanța codului concatenat C în _afara ∘ C _în este cel puțin dD , adică este un cod [ nN , kK , D '] cu D ' ≥ dD .

Dovada: Luați în considerare două mesaje diferite m ¹ ≠ m ² ∈ B ^K . Să Δ denotăm distanța dintre două coduri de ordine. Apoi

${\ displaystyle \ Delta (C_ {out} (m ^ {1}), C_ {out} (m ^ {2})) \ geq D.}$

Astfel, există cel puțin D poziții în care secvența de N simboluri ale codurilor C _out ( m ¹ ) și C _out ( m ² ) diferă. Pentru aceste poziții, notate i , avem

${\ displaystyle \ Delta (C_ {in} (C_ {afară} (m ^ {1}) _ {i}), C_ {in} (C_ {afară} (m ^ {2}) _ {i})) \ geq d.}$

Prin urmare, există cel puțin d ⋅ D poziții în secvența de n ⋅ N simboluri luate din alfabetul A în care cele două diferă cuvintele de cod, și , prin urmare ,

${\ displaystyle \ Delta (C_ {in} (C_ {afară} (m ^ {1})), C_ {in} (C_ {afară} (m ^ {2}))) \ geq dD.}$

2. Dacă C _out și C _in sunt coduri liniare de bloc , atunci C _out ∘ C _in este de asemenea un cod bloc liniar.

Această proprietate poate fi arătată cu ușurință pe baza ideii de a defini o matrice generatoare pentru codul concatenat în termeni de matrice generatoare de C _out și C _in .

Decodarea codurilor concatenate

Un concept natural pentru un algoritm de decodare a codurilor concatenate este de mai întâi decodarea codului interior și apoi a codului exterior. Pentru ca algoritmul să fie practic, acesta trebuie să fie timp polinomial în lungimea finală a blocului. Luați în considerare faptul că există un algoritm de decodificare unic în timp polinomial pentru codul exterior. Acum trebuie să găsim un algoritm de decodificare în timp polinomial pentru codul interior. Se înțelege că timpul de rulare polinomial înseamnă că timpul de rulare este polinomial în lungimea finală a blocului. Ideea principală este că dacă lungimea blocului interior este selectată pentru a fi logaritmică în mărimea codului exterior, atunci algoritmul de decodare pentru codul interior poate rula în timp exponențial al lungimii blocului interior, și astfel putem folosi un timp exponențial dar decodorul de probabilitate maximă optimă (MLD) pentru codul interior.

Detaliat, lăsați intrarea decodorului să fie vectorul y = ( y ₁ , ..., y _N ) ∈ ( A ⁿ ) ^N . Atunci algoritmul de decodare este un proces în două etape:

1. Utilizați MLD codului interior al C _în a reconstitui un set de cuvinte cod interior y '= ( y ' ₁ , ..., y ' _N ), cu y ' _i = MLD _{C în} ( y _i ), 1 ≤ i ≤ N .
2. Rulați algoritmul de decodare unic pentru C _out pe y “.

Acum, complexitatea de timp a primului pas este O ( N ⋅exp ( n )), unde n = O (log ( N )) este lungimea interioară a blocului. Cu alte cuvinte, este N ^{O (1)} ( de exemplu, polinomul-timp) în ceea ce privește exterior lungimii blocului N . Deoarece se presupune că algoritmul de decodare extern din etapa a doua rulează în timp polinomial, complexitatea algoritmului de decodare generală este de asemenea timp polinomial.

Comentarii

Algoritmul de decodare descris mai sus poate fi utilizat pentru a corecta toate erorile cu mai puțin de dD / 4 la număr. Folosind decodarea la distanță minimă , decodorul exterior poate corecta toate intrările y 'cu mai puțin de simbolurile D / 2 y ' _i din greșeală. În mod similar, codul interior poate corecta în mod fiabil o intrare y _i dacă mai puțin de d / 2 simboluri interioare sunt eronate. Astfel, pentru un simbol exterior y ' _i pentru a fi incorecte după decodificare interior cel puțin d / 2 simboluri interioare trebuie să fi fost în eroare și pentru codul extern să nu reușească acest lucru trebuie să se fi întâmplat de cel puțin D / 2 simboluri exterioare. În consecință, numărul total de simboluri interioare care trebuie primite incorect pentru ca codul concatenat să nu reușească trebuie să fie cel puțin d / 2⋅ D / 2 = dD / 4.

Algoritmul funcționează, de asemenea, dacă codurile interioare sunt diferite, de exemplu, pentru codurile Justesen . Algoritmul minim distanță generalizat , dezvoltat de Forney, pot fi folosite pentru a corecta până la dD / 2 erori. Folosește informațiile de ștergere din codul interior pentru a îmbunătăți performanța codului exterior și a fost primul exemplu de algoritm care utilizează decodarea soft-decision .

Aplicații

Deși o schemă simplă de concatenare a fost deja implementată pentru misiunea orbitară Mariner Mars din 1971 , codurile concatenate au început să fie folosite în mod regulat pentru comunicarea spațială profundă cu programul Voyager , care a lansat două sonde spațiale în 1977. De atunci, codurile concatenate au devenit capul de lucru pentru codare eficientă de corectare a erorilor și a rămas așa cel puțin până la inventarea codurilor turbo și a codurilor LDPC .

De obicei, codul interior nu este un cod bloc , ci un soft-decizie convoluțională Viterbi-decodat cod cu o lungime de constrângere scurtă. Pentru codul exterior , se folosește un cod bloc de decizie mai lung, frecvent un cod Reed-Solomon cu simboluri pe opt biți. Dimensiunea mai mare a simbolului face ca codul exterior să fie mai robust pentru exploziile de eroare care pot apărea din cauza deprecierii canalului și, de asemenea, pentru că ieșirea eronată a codului convolutional în sine este explozivă. De obicei, se adaugă un strat de intercalare între cele două coduri pentru a răspândi exploziile de eroare pe o gamă mai largă.

Combinația unui cod convoluțional Viterbi interior cu un cod Reed-Solomon exterior (cunoscut sub numele de cod RSV) a fost utilizată pentru prima dată în Voyager 2 și a devenit o construcție populară atât în ​​interiorul cât și în afara sectorului spațial. Acesta este încă utilizat în prezent în special pentru comunicațiile prin satelit , cum ar fi standardul de difuzare a televiziunii digitale DVB-S .

Într-un sens mai slab, orice combinație (serială) a două sau mai multe coduri poate fi denumită cod concatenat. De exemplu, în cadrul standardului DVB-S2 , un cod LDPC de înaltă eficiență este combinat cu un cod exterior algebric pentru a elimina eventualele erori rezistente rămase din codul LDPC interior datorită planului său de eroare inerent .

O schemă simplă de concatenare este de asemenea folosită pe discul compact (CD), unde un strat de intercalare între două coduri Reed-Solomon de dimensiuni diferite răspândește erori pe diferite blocuri.

Coduri turbo: o abordare paralelă de concatenare

Descrierea de mai sus este dată pentru ceea ce se numește acum un cod în mod concatenat. Codurile turbo , așa cum s-a descris mai întâi în 1993, au implementat o concatenare paralelă a două coduri convoluționale, cu o intercalare între cele două coduri și un decodificator iterativ care transmite informații înainte și înapoi între coduri. Acest design are o performanță mai bună decât orice coduri concatenate concepute anterior.

Cu toate acestea, un aspect cheie al codurilor turbo este abordarea lor de decodare iterată. Decodarea iterată este acum aplicată și la concatenările seriale pentru a obține câștiguri de codificare mai mari, cum ar fi în cadrul codurilor convolutive seriale concatenate (SCCC). O formă timpurie de decodare iterată a fost implementată cu două-cinci iterații în „codul Galileo” al sondei spațiale Galileo .

Vezi si

• Codul Justesen
• Zyablov a legat
• Singleton legat
• Gilbert – Varshamov s-a legat

Referințe

Citirea ulterioară

• Shu Lin; Daniel J. Costello Jr. (1983). Codarea controlului erorilor: Fundamente și aplicații . Sala Prentice . p. 278–280. ISBN  0-13-283796-X .
• FJ MacWilliams ; NJA Sloane (1977). Teoria codurilor de corectare a erorilor . Nord-Olanda. p. 307–316. ISBN  0-444-85193-3 .

linkuri externe

• Dave Forney (ed.). „Coduri concatenate” . Scholarpedia .
• Universitatea de la Buffalo Note de prelegere privind teoria codificării - Dr. Atri Rudra