Cod cu o densitate redusă de verificări de paritate

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 mai 2020; verificările necesită 7 modificări .

Cod de verificare de paritate joasă ( LDPC-code din engleză. Cod de verificare de paritate de densitate joasă, cod LDPC, cod de densitate joasă ) este un cod utilizat în transmiterea informațiilor, un caz special al unui cod liniar bloc cu paritate Verifica. O caracteristică este densitatea scăzută a elementelor semnificative ale matricei de verificare , datorită căreia se realizează simplitatea relativă a implementării instrumentelor de codare.

Denumit și codul Gallagher , după autorul primei lucrări pe tema codurilor LDPC.

Fundal

În 1948, Shannon și-a publicat lucrarea despre teoria transmiterii informațiilor. Unul dintre rezultatele cheie ale lucrării este teorema de transmitere a informațiilor pentru un canal zgomotos , care indică posibilitatea de a minimiza probabilitatea unei erori de transmisie pe canal prin alegerea unei lungimi a cuvintelor cheie suficient de mare - o unitate de informație transmisă pe canal . 1] .

La transmiterea informațiilor, fluxul său este împărțit în blocuri de o anumită lungime (cel mai adesea), care sunt convertite de către codificator (codificat) în blocuri numite cuvinte cheie. Cuvintele cheie sunt transmise pe canal, eventual cu distorsiuni. Pe partea de recepție, decodorul convertește cuvintele cheie într-un flux de informații, corectând (dacă este posibil) erorile de transmisie.

Teorema lui Shannon afirmă că, în anumite condiții, probabilitatea unei erori de decodare (adică incapacitatea decodorului de a corecta o eroare de transmisie) poate fi redusă prin alegerea unei lungimi mai lungi a cuvântului cheie. Cu toate acestea, această teoremă (și munca în general) nu arată cum să alegeți o lungime mare, ci mai degrabă cum să organizați eficient procesul de codificare și decodare a informațiilor cu o lungime mare de cuvinte cheie. Dacă presupunem că codificatorul și decodorul au niște tabele de corespondență între blocul de informații de intrare și cuvântul de cod corespunzător, atunci astfel de tabele vor ocupa mult spațiu. Pentru un canal binar simetric fără memorie (pentru a spune simplu, intrarea codificatorului este un flux de zerouri și unu) numărul de blocuri diferite este 2 n , unde n este numărul de biți (zero sau uni) care vor fi convertit într-un singur cuvânt cod. Pentru 8 biți, acestea sunt 256 de blocuri de informații, fiecare dintre ele va conține cuvântul de cod corespunzător. Mai mult, cuvântul de cod este de obicei mai lung, deoarece conține biți suplimentari pentru a proteja împotriva erorilor de transmisie a datelor. Prin urmare, una dintre metodele de codificare este utilizarea unei matrice de verificare, care permite decodarea cuvântului cod într-o singură operație matematică (înmulțirea unui rând cu o matrice). Într-un mod similar, fiecarei matrice de verificare corespunde unei matrice generatoare , într-un mod similar, printr-o operație de înmulțire a unui rând cu o matrice care generează un cuvânt cod.

Astfel, pentru cuvintele de cod relativ scurte, codificatoarele și decodoarele pot stoca pur și simplu toate opțiunile posibile în memorie, sau chiar le pot implementa sub forma unui circuit semiconductor. Pentru un cuvânt de cod mai mare, este mai eficient să stocați generatorul și matricea de paritate. Cu toate acestea, cu lungimi de bloc de câteva mii de biți, stocarea matricelor cu o dimensiune, respectiv, în megabiți , devine deja ineficientă. Una dintre modalitățile de a rezolva această problemă este utilizarea codurilor cu o densitate scăzută a verificărilor de paritate, atunci când numărul de unități din matricea de verificare a parității este relativ mic, ceea ce face posibilă organizarea procesului de stocare a matricei mai eficient sau direct implementați procesul de decodare folosind un circuit semiconductor.

Prima lucrare pe acest subiect a fost Robert Gallagher 1963 Low-Density Parity-Check Codes [2] (care a fost fondată în teza sa de doctorat din 1960 ). În lucrare, omul de știință a descris cerințele pentru astfel de coduri, a descris posibile metode de construcție și metode de evaluare a acestora. Prin urmare, codurile LDPC sunt adesea numite coduri Gallagher. În literatura științifică rusă , codurile sunt numite și coduri cu densitate scăzută sau coduri cu o densitate scăzută a verificărilor de paritate.

Totuși, din cauza dificultății de implementare a codificatoarelor și decodorelor, aceste coduri nu au fost folosite și au fost uitate până când lucrarea lui Gallagher a fost redescoperită în 1996 [3] [4] . Odată cu dezvoltarea tehnologiilor de telecomunicații, interesul pentru transmiterea informațiilor cu erori minime a crescut din nou. În ciuda complexității implementării în comparație cu codul turbo , lipsa barierelor de utilizare (neprotejate de brevete) a făcut codurile LDPC atractive pentru industria telecomunicațiilor și, de fapt, au devenit standardul de facto. În 2003, codul LDPC, în loc de codul turbo, a devenit parte a standardului de transmisie de date prin satelit DVB-S2 pentru televiziunea digitală. O înlocuire similară a avut loc în standardul DVB-T2 pentru difuzarea televiziunii digitale terestre [5] .

Codurile LDPC

Codurile LDPC sunt descrise printr-o matrice de paritate cu densitate scăzută care conține în mare parte zerouri și un număr relativ mic de unități. Prin definiție, dacă fiecare rând al matricei conține exact și fiecare coloană conține exact unul, atunci codul se numește regulat (în caz contrar, neregulat ). În cazul general, numărul celor din matrice are ordinul , adică crește liniar odată cu creșterea lungimii blocului de cod (numărul de coloane ale matricei de verificare). $k<n$ $j<r$ $O\stanga(n\dreapta)$

De obicei sunt luate în considerare matrici de dimensiuni mari. De exemplu, munca lui Gallagher în secțiunea de rezultate experimentale utilizează numere „mici” de rânduri n=124, 252, 504 și 1008 rânduri (numărul de coloane din matricea de verificare este puțin mai mare). În practică, se folosesc matrici cu un număr mare de elemente - de la 10 la 100 de mii de rânduri. Numărul de elemente pe rând sau coloană rămâne însă destul de mic, de obicei mai mic de 10. S-a observat că codurile cu același număr de elemente pe rând sau coloană, dar cu o dimensiune mai mare, au performanțe mai bune.

O caracteristică importantă a matricei de cod LDPC este absența ciclurilor de o anumită dimensiune. Un ciclu de lungime 4 este înțeles ca formarea unui dreptunghi în matricea de verificare, în colțurile căruia se află unități. Absența unui ciclu de lungime 4 poate fi determinată și prin produsul scalar al coloanelor (sau rândurilor) matricei. Dacă fiecare produs scalar pe perechi al tuturor coloanelor (sau rândurilor) matricei nu este mai mare de 1, aceasta indică absența unui ciclu de lungime 4. Ciclurile de lungime mai mare (6, 8, 10 etc.) pot fi determinat dacă în matricea de verificare este construit un grafic , cu vârfuri ale căror muchii sunt toate conexiuni posibile ale vârfurilor paralele cu laturile matricei (adică linii verticale sau orizontale). Ciclul minim din această coloană va fi ciclul minim din matricea de verificare a codului LDPC. Evident, ciclul va avea o lungime de cel puțin 4, nu 3, deoarece marginile graficului trebuie să fie paralele cu laturile matricei. În general, orice ciclu din acest grafic va avea o lungime uniformă, dimensiunea minimă este 4, iar dimensiunea maximă de obicei nu contează (deși, evident, nu este mai mult decât numărul de noduri din grafic, adică n × k).

Descrierea codului LDPC este posibilă în mai multe moduri:

matricea de verificare
grafic bipartit
un alt mod grafic
moduri speciale

Această din urmă metodă este o desemnare convențională pentru un grup de reprezentări de cod care sunt construite conform unor reguli-algoritmi date, astfel încât pentru a reproduce codul din nou, este suficient să cunoașteți doar parametrii de inițializare ai algoritmului și, bineînțeles, , algoritmul de construcție în sine. Cu toate acestea, această metodă nu este universală și nu poate descrie toate codurile LDPC posibile.

Metoda de specificare a unui cod printr-o matrice de verificare este în general acceptată pentru codurile liniare, atunci când fiecare rând al matricei este un element al unui anumit set de cuvinte de cod. Dacă toate rândurile sunt liniar independente, rândurile matricei pot fi considerate ca bază a mulțimii tuturor vectorilor de cod ai codului. Cu toate acestea, utilizarea acestei metode creează dificultăți pentru reprezentarea matricei în memoria codificatorului - este necesar să stocați toate rândurile sau coloanele matricei ca un set de vectori binari, datorită cărora dimensiunea matricei devine egală cu biții . . $j\times k$

O modalitate grafică comună este reprezentarea codului ca un graf bipartit. Să comparăm toate rândurile matricei cu vârfurile inferioare ale graficului și toate coloanele cu vârfurile superioare și să conectăm vârfurile superioare și inferioare ale graficului dacă există unități la intersecția rândurilor și coloanelor corespunzătoare. $k$ $k$ $n$

Alte metode grafice includ transformări de graf bipartite care au loc fără a schimba efectiv codul în sine. De exemplu, puteți reprezenta toate vârfurile de sus ale graficului ca triunghiuri și toate vârfurile de jos ca pătrate și apoi aranjați marginile și vârfurile graficului pe o suprafață bidimensională într-o ordine convenabilă pentru înțelegerea vizuală a structura codului. De exemplu, o astfel de reprezentare este folosită ca ilustrații în cărțile lui David McKay.

Prin introducerea unor reguli suplimentare pentru afișarea grafică și construcția codului LDPC, este posibil să se realizeze ca codul să primească anumite proprietăți în timpul procesului de construcție. De exemplu, dacă folosim un graf ale cărui vârfuri sunt doar coloanele matricei de verificare, iar rândurile sunt reprezentate prin poliedre construite pe vârfurile grafului, atunci respectarea regulii „două poliedre nu împart o muchie” ne permite să scăpați de ciclurile de lungime 4.

Atunci când se utilizează proceduri speciale de construcție a codului, se pot folosi propriile metode de reprezentare, stocare și procesare (codificare și decodare).

Construirea codului

În prezent, sunt utilizate două principii pentru construirea unei matrice de verificare a codului. Prima se bazează pe generarea unei matrice de verificare inițială folosind un generator pseudo-aleatoriu. Codurile obținute în acest fel sunt numite aleatoriu ( în engleză coduri asemănătoare aleatorii ). Al doilea este utilizarea unor metode speciale bazate, de exemplu, pe grupuri și câmpuri finale . Codurile obținute prin aceste metode se numesc coduri structurate . Codurile aleatoare arată cele mai bune rezultate în corectarea erorilor, cu toate acestea, codurile structurate permit utilizarea metodelor de optimizare a procedurilor de stocare, codificare și decodare, precum și obținerea de coduri cu caracteristici mai previzibile.

În munca sa, Gallagher a ales să folosească un generator de numere pseudo-aleatoare pentru a crea o matrice de verificare inițială de dimensiuni mici, cu caracteristici specificate, apoi să-i mărească dimensiunea prin duplicarea matricei [6] și folosind metoda de amestecare a rândurilor și coloanelor pentru a obține scăpa de ciclurile de o anumită lungime.

În 2003, James McGowan și Robert Williamson au propus o modalitate de a elimina ciclurile din matricea unui cod LDPC și, prin urmare, a devenit posibil să se genereze mai întâi o matrice cu caracteristici date (n, j, k) și apoi să se elimine ciclurile din aceasta. Așa se întâmplă în schema Ozarov-Weiner [7] .

În 2007, a fost publicat un articol în revista „IEEE Transactions on Information Threory” despre utilizarea câmpurilor finite pentru a construi coduri LDPC cvasiciclice pentru canale aditive de zgomot alb Gaussian și canale binare de ștergere.

Pentru a mări dimensiunea codului, se poate folosi un produs final multiplu al matricelor generatoare [6] .

Decodare

Ca și pentru orice alt cod liniar, proprietatea de ortogonalitate a matricelor de verificare generatoare și transpuse este utilizată pentru decodare:

G\odot H^{T}=0

unde este matricea generatoare și este matricea de verificare , este simbolul înmulțirii modulo 2 (dacă se obține un număr care este multiplu de 2 ca element al matricei rezultate, atunci se scrie în schimb zero). Apoi, pentru fiecare cuvânt cod primit fără erori, relația $G$ $H$ $\odot$

s=v\odot H^{T}=0

și pentru cuvântul de cod primit cu o eroare:

s=v\odot H^{T}\neq 0

unde este vectorul acceptat, este sindromul . Dacă, după înmulțirea cuvântului de cod primit cu matricea de paritate transpusă, se obține zero, blocul este considerat primit fără erori. În caz contrar, sunt folosite metode speciale pentru a localiza eroarea și a o corecta. Pentru un cod LDPC, metodele standard de corecție se dovedesc a fi prea consumatoare de timp - sunt clasificate ca probleme NP-complete, care, având în vedere lungimea mare a blocului, nu pot fi aplicate în practică. În schimb, ei folosesc metoda decodării iterative probabilistice, care corectează o mare parte a erorilor peste jumătate din distanța codului [8] . $v$ $s$

Considerăm [9] un canal simetric fără memorie cu zgomot Gaussian de intrare și aditiv . Pentru cuvântul de cod primit , trebuie să găsiți vectorul cel mai probabil corespunzător , astfel încât $\pm a$ $\sigma ^{2}=1$ $y$ $X$

H\odot x=0\mod 2

Să definim $f_{n}^{1}={1/{\mathord {\left(1+\exp \left(-2ay_{n}/{\mathord {\sigma ^{2))}\right) \dreapta)}}}$ ; ${\displaystyle f_{n}^{0}=1-f_{n}^{1))$ ; unde este valoarea primită a celui de-al n-lea simbol al cuvântului cod (care pentru un canal dat are o valoare arbitrară, de obicei în ). $y_{n}$ $\pm (a+3\sigma )$
Vom folosi cuvântul „bit” pentru a desemna elemente individuale ale vectorului , iar cuvântul „verificare” pentru a desemna rândurile matricei de verificare . Se notează prin setul de biți care vor participa la a-a-a verificare. În mod similar, să notăm setul de verificări la care participă bit n. (Adică listăm indicii elementelor non-nule pentru fiecare rând și pentru fiecare coloană a matricei de verificare ). $X$ $H$ $N\stanga(m\dreapta)\equiv \{n:H_{nm}=1\)$ $M\stanga(n\dreapta)\equiv \{m:H_{nm}=1\)$ $H$
Inițializam matrice și valori și respectiv $q_{mn}^{0)$ $q_{mn}^{1}$ $f_{n}^{0)$ $f_{n}^{1)$
(pas orizontal) $\delta q_{mn}=q_{mn}^{0}-q_{mn}^{1)$ $\delta r_{mn}=\prod \limits _{n'\in N(m)\backslash n}{\delta q_{mn'}}$ $r_{mn}^{0}={1 \over 2}\left({1+\delta r_{mn}}\right)$ $r_{mn}^{1}={1 \over 2}\left({1-\delta r_{mn}}\right)$
(pas vertical) $q_{mn}^{0}=\alpha _{mn}f_{n}^{0}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_ {m'n}^{0}}$ $q_{mn}^{1}=\alpha _{mn}f_{n}^{1}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_ {m'n}^{1}}$ unde pentru fiecare și ales oferă: $m$ $n$ $\alpha _{mn}$ $q_{mn}^{0}+q_{mn}^{1}=1$ Acum actualizăm și „probabilitățile pseudo-posterioare” pe care biții vectorului iau valorile 0 sau 1: $X$ $q_{n}^{0}=\alpha _{n}f_{n}^{0}\prod \limits _{m\în M\left(n\right)}{r_{mn}^ {0}}$ $q_{n}^{1}=\alpha _{n}f_{n}^{1}\prod \limits _{m\in M\left(n\right)}{r_{mn}^ {unu}}$ De asemenea, ca și înainte, este ales în așa fel încât $\alpha_{n}$ $q_{n}^{0}+q_{n}^{1}=1$

Aceste valori sunt folosite pentru a recrea vectorul x. Dacă vectorul rezultat satisface , atunci algoritmul este întrerupt, în caz contrar se repetă pașii orizontal și vertical. Dacă algoritmul continuă până la un anumit pas (de exemplu, 100), atunci este întrerupt și blocul este declarat acceptat cu o eroare. $H\odot x=0\mod 2$

Se știe că acest algoritm dă valoarea exactă a vectorului (adică coincide cu metodele clasice) dacă matricea de verificare nu conține cicluri [10] . $X$ $H$

Note

↑ Shannon CE A Mathematical Theory of Communication // Bell System Technical Journal. - 1948 . - T. 27 . - S. 379-423, 623-656 .
↑ Gallager, R. G. Codurile de verificare a parității de densitate scăzută . — Cambridge : MIT Press, 1963 . — P. 90.
↑ David JC MacKay și Radford M. Neal, „Near Shannon Limit Performance of Low Density Parity Check Codes”, Electronics Letters, iulie 1996
↑ David JC MacKay. Teoria informației, inferență și algoritmi de învățare . - CUP, 2003. - ISBN 0-521-64298-1 .
↑ Dr. Lin Nan Lee. Coduri LDPC, aplicație la sistemele de comunicații de generație următoare // Conferința semestrială IEEE privind tehnologia vehiculelor. - octombrie 2003. Arhivat din original la 8 octombrie 2006.
↑ 1 2 Slyusar V. I. Sinteza codurilor LDPC și polare bazate pe produsul final al matricelor.// Development of Education, Science and Business: Results 2020: abstracts of the International Scientific and Practical Internet Conference, 3-4 decembrie 2020. – Partea 2. - pp. 393-396. [1] Arhivat pe 25 ianuarie 2021 la Wayback Machine .
↑ Yu.V. Kosolapov. Despre aplicarea schemei Ozarov-Weiner pentru protecția informațiilor în sistemele de transmisie de date fără fir multicanal // Information Counteraction to Terrorism Threats : Scientific and Practical Journal. — 2007 . - Nr . 10 . - S. 111-120 . Arhivat din original pe 24 iunie 2013.
↑ V. B. Afanasiev, D. K. Zigangirov „Despre unele construcții de coduri de joasă densitate cu un cod component Reed-Solomon”
↑ David JC MacKay, Radford M. Neal Near Shannon Limit Performance of Low Density Parity Check Codes . Preluat la 28 august 2008. Arhivat din original la 17 aprilie 2007. (nedefinit)
↑ J. Pearl. Raționamentul probabilistic în sistemele inteligente: rețele de inferență plauzibilă. Morgan Kaufmann, San Mateo, 1988.