Cod de verificare a parității de densitate mică

Codurile de verificare a parității cu densitate redusă , cunoscute și sub numele de coduri LDPC sau Gallager , sunt coduri liniare de bloc pentru corectarea erorilor . Au fost dezvoltate în 1962 de Robert Gray Gallager ca parte a disertației sale la MIT .

Cu ajutorul unei matrice, codurile de verificare a parității cu densitate mică descriu multe verificări de paritate conexe . Se utilizează principiul unei matrice de control : unde reprezintă matricea de control (matricea de verificare a parității) și secvența simbolurilor de cod primite (reprezentate ca un vector linie). H este doar puțin populat (de aici și denumirea de densitate scăzută ). ${\ displaystyle H \ cdot b ^ {T} = 0}$${\ displaystyle H}$${\ displaystyle b}$

Uitați de mult, au cunoscut o renaștere atunci când Rüdiger Urbanke și Thomas J. Richardson au arătat în 2001 că pot opera în apropierea frontierei Shannon și că pot fi implementați eficient ca LDPC neregulat. LDPC neregulat include codurile de tornadă pentru codificarea ștergerii ( Michael Luby , Michael Mitzenmacher , Daniel A. Spielman , Amin Shokrollahi 2001).

notaţie

${\ displaystyle (n, l, R) \; {\ text {LDPC}}}$

• ${\ displaystyle n}$ = Lungimea cuvântului cod
• ${\ displaystyle k}$ = Numărul de biți de paritate
• ${\ displaystyle l}$ = Numărul de puncte de informații
• ${\ displaystyle R}$= Rata codului

Definitia termenilor

• ${\ displaystyle a ^ {*}}$sau cuvânt cod sursă (cuvânt info)${\ displaystyle a_ {l}}$
• ${\ displaystyle a_ {k}}$ parte redundantă a cuvântului cod de canal
• ${\ displaystyle a}$ Cuvânt cuvânt cod
• ${\ displaystyle b}$ Secvența de recepție
• ${\ displaystyle H}$ Matricea de control

Coduri regulate și neregulate

Caracteristicile importante ale codului LDPC sunt numărul de 1 biți pe linie ( ) și cei 1 biți pe coloană ( ) din matricea de control . Următoarele se aplică acestor etichete: ${\ displaystyle w_ {r}}$${\ displaystyle w_ {c}}$${\ displaystyle H}$

${\ displaystyle w_ {r} \ ll n}$ la fel de ${\ displaystyle w_ {c} \ ll k}$

Este constant pentru toate rândurile și constant pentru toate coloanele din , acest cod se numește regulat. ${\ displaystyle w_ {r}}$${\ displaystyle w_ {c}}$${\ displaystyle H}$

Pentru un cod LDPC obișnuit se aplică . ${\ displaystyle w_ {r} = w_ {c} \ cdot (l + k) / k}$

Dacă numărul acestora variază, codul este neregulat. De obicei, codurile LDPC neregulate sunt mai puternice decât cele obișnuite.

Codificare

Scopul este de a găsi o secvență care trebuie trimisă care să satisfacă ecuația . ${\ displaystyle a}$${\ displaystyle H \ cdot a ^ {T} = 0}$

O posibilă formă de codare funcționează după cum urmează: Cuvântul de cod al canalului este compus din datele de trimis (care sunt cunoscute) și partea redundantă . Deoarece formula de mai sus trebuie să fie îndeplinită, următoarele trebuie calculate în consecință: ${\ displaystyle a}$${\ displaystyle a_ {l}}$${\ displaystyle a_ {k}}$${\ displaystyle a}$${\ displaystyle a_ {k}}$

• Fii și${\ displaystyle a = [a_ {k}, a_ {l}]}$${\ displaystyle H = [H_ {k}, H_ {l}]}$
• Ar trebui să se aplice următoarele: ${\ displaystyle [H_ {k}, H_ {l}] * [a_ {k}, a_ {l}] ^ {T} = 0}$
• Acest lucru poate fi transformat: ${\ displaystyle [H_ {k}] [a_ {k}] = [H_ {l}] [a_ {l}]}$
• Acest lucru are ca rezultat ${\ displaystyle a_ {k} ^ {T} = H_ {k} ^ {- 1} \ cdot H_ {l} \ cdot a_ {l}}$

Exprimat în cuvinte, pătratul inversat - prima parte H _{k a} matricei de control trebuie să fie înmulțit cu restul restant H _{l al} matricei de control și datele a _{l care} trebuie trimise.

Decodare

De asemenea, este important să rezolvați problema. Algoritmii iterați pe bază de graf sunt adesea aleși în acest scop . După transmiterea cuvântului cod de canal pe un canal de transmisie, de ex. B. se primește de obicei un canal AWGN ( zgomot alb Gaussian aditiv ), cuvântul , format din valori reale. Din acestea se calculează o soluție aproximativă, de obicei cu ajutorul unui proces iterativ. N ecuații sunt date de matricea de ecuații H; fiecare dintre aceste ecuații permite calcularea informațiilor independente despre elementele conținute. Acum aceste informații sunt reutilizate în celelalte calcule ale ecuației. Trebuie remarcat faptul că informațiile care au fost calculate folosind o ecuație trebuie eliminate în următoarea iterație înainte de noul calcul. ${\ displaystyle H \ cdot b ^ {T} = 0}$${\ displaystyle a}$ ${\ displaystyle b_ {M}}$

Construirea codurilor LDPC

Codurile LDPC sunt descrise prin matricea lor de control H. Dezvoltarea unui cod LDPC înseamnă găsirea sau construirea unei matrice de control adecvate. Matricea generator G necesară pentru a crea cuvinte cod poate fi derivată din H cu ajutorul metodei Gauss-Jordan . Următoarele sunt potrivite pentru generarea matricilor de control. următoarele proceduri, care se bazează parțial pe simbolizarea matricei de control ca grafic Tanner și prelucrarea acesteia cu ajutorul diferiților algoritmi:

• Creștere progresivă a marginilor (PEG)
• Construcție conform lui David JC MacKay și Radford M. Neal
• Construcția aleatorie a matricei de control

Pentru a menține numărul celor care apar în matrice relativ scăzut, pot fi folosiți și așa-numiții algoritmi de „împărțire rând” și „împărțire coloană”.

Utilizarea practică a codurilor LDPC

Codurile LDPC sunt utilizate în diferite domenii ale tehnologiei. De regulă, acestea sunt utilizate într-un lanț . Codurile LDPC sunt utilizate, de exemplu, pentru transmiterea datelor de corectare a erorilor semnalelor digitale de televiziune în conformitate cu DVB-S2 și pentru difuzarea multimedia terestră digitală (DTMB). În plus față de standardele WLAN mai noi, cum ar fi IEEE 802.11n („n-WLAN” sau „n-Draft WLAN”), standardul WLAN 802.16e ( Wimax ) implementează și coduri LDPC. Alte standarde sunt GMR-1 , IEEE 802.3an , IEEE 802.22 , CMMB și WiMedia 1.5 .

literatură

• Robert G. Gallager: Coduri de verificare a parității cu densitate redusă . MIT Press Classic Series, Cambridge MA, 1963 ( MIT Press monografii de cercetare 21, ZDB -ID 597839-7 ), ( versiune diferită , PDF, 655 kB).
• David JC MacKay : Teoria informației, inferență și algoritmi de învățare . Cambridge University Press, Cambridge și colab. 2003, ISBN 0-521-64298-1 ( disponibil și online ).
• Todd K. Moon: Codare de corectare a erorilor. Metode și algoritmi matematici . Wiley-Interscience, Hoboken NJ, 2005, ISBN 0-471-64800-0 .
• Amin Shokrollahi : Coduri LDPC: o introducere . În: Keqin Feng și colab. (Ed.): Codificare, criptografie și combinatorică . Birkhäuser, Basel și colab. 2004, ISBN 3-7643-2429-5 , pp. 85-112 ( Progresul în informatică și logica aplicată 23), ( PDF ).

Dovezi individuale

1. ^ Robert G. Gallager: Coduri de verificare a parității cu densitate redusă . ( Memento din 16 martie 2007 în Arhiva Internet ) (PDF; 1,1 MB) în Tranzacțiile IRE privind teoria informației , paginile 21-28, 1962
2. ^ Robert G. Gallager: Coduri de verificare a parității cu densitate redusă . - 1963
3. ↑ Jian Sun: Introducere în codurile de verificare a parității cu densitate redusă (LDPC) ( Memorie din 13 ianuarie 2012 în Arhiva Internet )
4. ↑ Alex Balatsoukas-Stimming: Algoritmul de creștere a muchiei progresive (PDF; 261 kB)
5. ↑ David MacKay: C - Implementarea algoritmului PEG pentru codurile LDPC
6. ↑ Proiectarea și implementarea codurilor LDPC (PDF; 255 kB)
7. ↑ ^{a b} Proiectarea codurilor LDPC (PDF; 563 kB)
8. ↑ IEEE: IEEE Standard 802.11n
9. ↑ IEEE: IEEE Standard 802.16e
10. ↑ Lista codurilor LDPC standardizate cu proprietăți și explicații