Kód alacsony sűrűségű paritásellenőrzéssel

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. május 22-én felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

Az alacsony sűrűségű paritásellenőrző kód ( LDPC-kód angolból . Low-density parity-check code, LDPC-code , low- density code ) információátvitelben használt kód , a paritásos blokk lineáris kód speciális esete. jelölje be. Jellemzője az ellenőrző mátrix jelentős elemeinek alacsony sűrűsége, aminek köszönhetően a kódolóeszközök megvalósításának viszonylagos egyszerűsége érhető el.

Gallagher-kódnak is nevezik , az LDPC kódok témájával foglalkozó első munka szerzője után.

Háttér

Shannon 1948- ban publikálta az információátvitel elméletéről szóló munkáját. A munka egyik kulcsfontosságú eredménye a zajos csatornára vonatkozó információátviteli tétel , amely azt jelzi, hogy a csatornán keresztüli átviteli hiba valószínűsége minimálisra csökkenthető egy kellően nagy kulcsszóhossz - a csatornán továbbított információegység - megválasztásával . 1] .

Az információ továbbításakor annak folyamát egy bizonyos (leggyakrabban) hosszúságú blokkokra osztják, amelyeket a kódoló (kódolva) kulcsszavaknak nevezett blokkokká alakít át. A kulcsszavakat a csatornán keresztül továbbítják, esetleg torzítással. A vevő oldalon a dekóder a kulcsszavakat információfolyammá alakítja, kijavítva (ha lehetséges) az átviteli hibákat.

Shannon tétele kimondja, hogy bizonyos feltételek mellett a dekódolási hiba (vagyis annak, hogy a dekóder nem tudja kijavítani az átviteli hibát) valószínűsége csökkenthető hosszabb kulcsszóhossz választásával. Ez a tétel (és általában a munka) azonban nem azt mutatja meg, hogyan válasszunk nagy hosszúságot, hanem azt, hogy hogyan lehet hatékonyan megszervezni az információ kódolási és dekódolási folyamatát nagy hosszúságú kulcsszavakkal. Ha feltételezzük, hogy a kódoló és a dekódoló rendelkezik néhány megfelelési táblázattal a bemeneti információblokk és a megfelelő kódszó között, akkor az ilyen táblázatok sok helyet foglalnak el. Egy memória nélküli bináris szimmetrikus csatorna esetén (leegyszerűsítve a kódoló bemenete nullák és egyesek folyama) a különböző blokkok száma 2 n , ahol n a bitek (nullák vagy egyesek) száma. egyetlen kódszóvá alakítva. 8 bit esetén ez 256 információblokk, amelyek mindegyike a megfelelő kódszót tartalmazza. Ezenkívül a kódszó általában hosszabb, mivel további biteket tartalmaz az adatátviteli hibák elleni védelem érdekében. Ezért az egyik kódolási mód az ellenőrző mátrix használata, amely lehetővé teszi a kódszó egy matematikai műveletben történő dekódolását (egy sor mátrixszal való szorzását). Hasonló módon minden egyes ellenőrző mátrix egy generáló mátrixnak felel meg , hasonló módon, egyetlen művelettel, amikor egy sort megszorozunk egy kódszót generáló mátrixszal.

Így viszonylag rövid kódszavak esetén a kódolók és dekódolók egyszerűen eltárolhatják az összes lehetséges opciót a memóriában, vagy akár félvezető áramkör formájában is megvalósíthatják azokat. Nagyobb kódszó esetén hatékonyabb a generátor és a paritásmátrix tárolása. Több ezer bites blokkhosszúságnál azonban a megabit méretű mátrixok tárolása már nem hatékony. A probléma megoldásának egyik módja az alacsony paritásellenőrzési sűrűségű kódok használata, amikor a paritásellenőrző mátrixban viszonylag kicsi az egységek száma, ami lehetővé teszi a mátrix tárolási folyamatának hatékonyabb vagy közvetlenebb megszervezését. félvezető áramkör segítségével hajtsa végre a dekódolási folyamatot.

Az első ebben a témában készült munka Robert Gallagher 1963 -as alacsony sűrűségű paritásellenőrző kódjai [2] (amelyet 1960 -as Ph.D. értekezésében alapozott meg ). A munkában a tudós ismertette az ilyen kódokkal szemben támasztott követelményeket, leírta a lehetséges konstrukciós módszereket és értékelési módszereket. Ezért az LDPC kódokat gyakran Gallagher-kódoknak nevezik. Az orosz tudományos irodalomban a kódokat alacsony sűrűségű kódoknak vagy alacsony paritásellenőrzési sűrűségű kódoknak is nevezik.

A kódolók és dekóderek megvalósításának nehézségei miatt azonban ezeket a kódokat nem használták, és egészen Gallagher munkájának 1996-os újrafelfedezéséig feledésbe merültek [3] [4] . A távközlési technológiák fejlődésével ismét megnőtt az érdeklődés a minimális hibával történő információtovábbítás iránt. Annak ellenére, hogy a turbókódhoz képest bonyolult volt a megvalósítás , a használati akadályok hiánya (szabadalmak által nem védett) vonzóvá tette az LDPC kódokat a távközlési ipar számára, és valójában de facto szabványokká váltak. 2003-ban a turbó kód helyett az LDPC kód a digitális televíziózás DVB-S2 műholdas adatátviteli szabványának részévé vált. Hasonló csere történt a digitális földfelszíni televíziós műsorszórás DVB-T2 szabványában [5] .

LDPC kódok

Az LDPC kódokat egy kis sűrűségű paritásmátrix írja le, amely többnyire nullákat és viszonylag kis számú egyest tartalmaz. Definíció szerint, ha a mátrix minden sora pontosan és minden oszlop pontosan egyet tartalmaz, akkor a kódot szabályosnak (egyébként irregulárisnak ) nevezzük . Általános esetben az egyesek száma a mátrixban nagyságrendű , azaz a kódblokk hosszának (az ellenőrző mátrix oszlopainak számának) növekedésével lineárisan növekszik. $k<n$ $j<r$ $O\left(n\right)$

Általában a nagy méretű mátrixokat veszik figyelembe. Például Gallagher munkája a kísérleti eredmények részben "kis" számú sort használ, n=124, 252, 504 és 1008 sor (az ellenőrző mátrix oszlopainak száma valamivel nagyobb). A gyakorlatban nagy számú elemet tartalmazó mátrixokat használnak - 10-100 ezer sor. A soronkénti vagy oszloponkénti egyesek száma azonban meglehetősen kicsi marad, általában kevesebb, mint 10. Megfigyelték, hogy a soronként vagy oszloponként azonos számú elemet tartalmazó, de nagyobb méretű kódok jobb teljesítményt nyújtanak.

Az LDPC kódmátrix fontos jellemzője a bizonyos méretű ciklusok hiánya. A 4 hosszúságú ciklus alatt egy téglalap kialakítását értjük az ellenőrző mátrixban, amelynek sarkaiban egységek vannak. A 4 hosszúságú ciklus hiánya a mátrix oszlopainak (vagy sorainak) skaláris szorzatával is meghatározható. Ha a mátrix összes oszlopának (vagy sorának) minden páronkénti skaláris szorzata nem nagyobb 1-nél, ez azt jelzi, hogy nincs 4 hosszúságú ciklus. A nagyobb hosszúságú ciklusok (6, 8, 10 stb.) akkor határozható meg, ha az ellenőrző mátrixba egy gráf épül , olyan csúcsokkal, amelyek élei a mátrix oldalaival párhuzamos csúcsok összes lehetséges kapcsolata (vagyis függőleges vagy vízszintes vonalak). Ebben az oszlopban a minimális ciklus az LDPC kód ellenőrző mátrixának minimális ciklusa lesz. Nyilvánvaló, hogy a ciklus hossza legalább 4 lesz, nem 3, mivel a gráf éleinek párhuzamosnak kell lenniük a mátrix oldalaival. Általában minden ciklus ebben a gráfban páros hosszúságú, a minimális méret 4, és a maximális méret általában nem számít (bár nyilvánvalóan nem több, mint a gráf csomópontjainak száma, azaz n × k).

Az LDPC kód leírása többféleképpen lehetséges:

ellenőrző mátrix
kétrészes gráf
egy másik grafikus módszer
speciális módokon

Ez utóbbi módszer egy konvencionális megnevezése a kódreprezentációk egy csoportjának, amelyek meghatározott szabályok-algoritmusok szerint épülnek fel úgy, hogy a kód ismételt reprodukálásához elegendő csak az algoritmus inicializálási paramétereit ismerni, és természetesen , maga az építési algoritmus. Ez a módszer azonban nem univerzális, és nem írja le az összes lehetséges LDPC kódot.

A kód ellenőrzési mátrix segítségével történő megadásának módszere általánosan elfogadott lineáris kódoknál, amikor a mátrix minden sora egy bizonyos kódszókészlet eleme. Ha minden sor lineárisan független, akkor a mátrix sorai tekinthetők a kód összes kódvektorának halmazának alapjának. Ennek a módszernek a használata azonban nehézségeket okoz a mátrixnak a kódoló memóriájában való megjelenítésében - a mátrix összes sorát vagy oszlopát bináris vektorok halmazaként kell tárolni, ami miatt a mátrix mérete bitekkel egyenlővé válik. . $j\times k$

Egy gyakori grafikus módszer a kód kétrészes gráfként való megjelenítése. Hasonlítsuk össze a mátrix összes sorát a gráf alsó csúcsaival, és az összes oszlopot a felső csúcsokkal, és kössük össze a gráf felső és alsó csúcsát, ha a megfelelő sorok és oszlopok metszéspontjában egységek vannak. $k$ $k$ $n$

Más grafikus módszerek közé tartoznak a kétrészes gráftranszformációk, amelyek a kód tényleges megváltoztatása nélkül történnek. Például ábrázolhatja a gráf összes felső csúcsát háromszögként, az összes alsó csúcsot pedig négyzetként, majd elrendezheti a gráf éleit és csúcsait egy kétdimenziós felületen olyan sorrendben, amely kényelmes a vizuális megértéshez. a kódszerkezet. Például egy ilyen ábrázolást David McKay könyveiben illusztrációként használnak.

Az LDPC kód grafikus megjelenítésére és felépítésére vonatkozó további szabályok bevezetésével elérhető, hogy a kód bizonyos tulajdonságokat kapjon az építési folyamat során. Például, ha olyan gráfot használunk, amelynek csúcsai csak az ellenőrző mátrix oszlopai, és a sorokat a gráf csúcsaira épített poliéderek reprezentálják, akkor a „két poliéder nem osztozik egy élen” szabályt követve lehetővé válik, hogy megszabadulni a 4 hosszúságú ciklusoktól.

Speciális kódszerkesztési eljárások alkalmazásakor saját ábrázolási, tárolási és feldolgozási (kódolási és dekódolási) módszerek alkalmazhatók.

Kódépítés

Jelenleg két elvet alkalmaznak a kódellenőrző mátrix felépítésére. Az első egy kezdeti ellenőrző mátrix létrehozásán alapul egy pszeudo-véletlen generátor segítségével. Az így kapott kódokat véletlennek ( angolul random-like codes ) nevezzük. A második a speciális módszerek alkalmazása, amelyek például csoportokon és végső mezőkön alapulnak . Az ezekkel a módszerekkel kapott kódokat strukturált kódoknak nevezzük . A véletlenszerű kódok mutatják a legjobb eredményt a hibajavításban, azonban a strukturált kódok lehetővé teszik a tárolás optimalizálásának, a kódolási és dekódolási eljárásoknak a használatát, valamint a kiszámíthatóbb jellemzőkkel rendelkező kódok beszerzését.

Munkája során Gallagher úgy döntött, hogy egy pszeudo-véletlenszám-generátort használ egy kezdeti kis méretű ellenőrző mátrix létrehozásához meghatározott jellemzőkkel, majd növeli a méretét a mátrix megkettőzésével [6] és a sorok és oszlopok keverésének módszerét, hogy megkapja. megszabadulni a bizonyos hosszúságú ciklusoktól.

2003- ban James McGowan és Robert Williamson javasolta a ciklusok eltávolítását egy LDPC kód mátrixából, így lehetővé vált, hogy először egy adott (n, j, k) jellemzőkkel rendelkező mátrixot állítsanak elő, majd eltávolítsanak belőle ciklusokat. Ez történik az Ozarov-Weiner sémában [7] .

2007 -ben egy cikk jelent meg az "IEEE Transactions on Information Threory" folyóiratban a véges mezők felhasználásáról kváziciklikus LDPC kódok létrehozására additív fehér Gauss-zajcsatornákhoz és bináris törlési csatornákhoz.

A kód dimenziójának növelésére a mátrixok generálásának többszörös végterméke használható [6] .

Dekódolás

Mint minden más lineáris kód esetében, a generáló és transzponált ellenőrző mátrixok ortogonalitási tulajdonságát használják a dekódoláshoz:

G\odot H^{T}=0

ahol a generáló mátrix, és az ellenőrző mátrix, a modulo 2 szorzás szimbóluma (ha a kapott mátrix elemeként 2 többszörösét kapjuk, akkor helyette nullát írunk). Ezután minden hiba nélkül kapott kódszóhoz a reláció $G$ $H$ $\odot$

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

és a hibás kódszóhoz:

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

ahol az elfogadott vektor, a szindróma . Ha a vett kódszónak a transzponált paritásmátrixszal való megszorzása után nullát kapunk, akkor a blokkot hibamentesnek tekintjük. Ellenkező esetben speciális módszereket alkalmaznak a hiba felderítésére és kijavítására. Egy LDPC kód esetében a szabványos korrekciós módszerek túlságosan időigényesnek bizonyulnak - NP-teljes problémáknak minősülnek, amelyek a nagy blokkhossz miatt nem alkalmazhatók a gyakorlatban. Ehelyett a valószínűségi iteratív dekódolás módszerét alkalmazzák, amely a hibák nagy részét a kódtávolság felén túl javítja [8] . $v$ $s$

Tekintsünk [9] szimmetrikus memória nélküli csatornát bemenettel és additív Gauss-zajjal . A kapott kódszóhoz meg kell találni a megfelelő legvalószínűbb vektort úgy, hogy $\pm a$ $\sigma ^{2}=1$ $y$ $x$

H\odot x=0\mod 2

Határozzuk meg $f_{n}^{1}={1/{\mathord {\left(1+\exp \left(-2ay_{n}/{\mathord {\sigma ^{2))}\right) \jobb)}}}$ ; $f_{n}^{0}=1-f_{n}^{1}$ ; ahol a kódszó n-edik szimbólumának vett értéke (amely adott csatornánál tetszőleges értékű, általában belül ). $y_{n}$ $\pm (a+3\sigma )$
A "bit" szót fogjuk használni a vektor egyes elemeinek, a "check" szót pedig az ellenőrző mátrix sorainak jelölésére . Jelölje az m-edik ellenőrzésben részt vevő bitek halmazával. Hasonlóképpen jelöljük az ellenőrzések halmazát, amelyben az n bit részt vesz. (Azaz az ellenőrző mátrix minden sorához és oszlopához felsoroljuk a nem nullától eltérő elemek indexeit ). $x$ $H$ ${\displaystyle N\left(m\right)\equiv \{n:H_{nm}=1\))$ ${\displaystyle M\left(n\right)\equiv \{m:H_{nm}=1\))$ $H$
Inicializáljuk a mátrixokat és az értékeket , ill $q_{mn}^{0}$ ${\displaystyle q_{mn}^{1))$ $f_{n}^{0}$ ${\displaystyle f_{n}^{1))$
(vízszintes lépés) ${\displaystyle \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)$
(függőleges hangmagasság) $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}}$ ahol mindegyik és kiválasztott esetében : $m$ $n$ $\alpha _{mn}$ $q_{mn}^{0}+q_{mn}^{1}=1$ Most frissítjük a "pszeudo-posterior valószínűségeket" is, hogy a vektor bitjei 0 vagy 1 értéket vesznek fel: $x$ $q_{n}^{0}=\alpha _{n}f_{n}^{0}\prod \limits _{m\in 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}^ {egy}}$ Továbbá, mint korábban, úgy van megválasztva, hogy $\alpha_{n}$ $q_{n}^{0}+q_{n}^{1}=1$

Ezeket az értékeket az x vektor újbóli létrehozására használják. Ha a kapott vektor kielégíti a -t, akkor az algoritmus megszakad, ellenkező esetben a vízszintes és függőleges lépések megismétlődnek. Ha az algoritmus egy bizonyos lépésig (például 100-ig) folytatódik, akkor megszakad, és a blokkot hibásan elfogadottnak nyilvánítja. $H\odot x=0\mod 2$

Ismeretes, hogy ez az algoritmus megadja a vektor pontos értékét (vagyis a klasszikus módszerekkel egybeesve), ha az ellenőrző mátrix nem tartalmaz ciklusokat [10] . $x$ $H$

Jegyzetek

↑ Shannon CE A kommunikáció matematikai elmélete // Bell System Technical Journal. - 1948 . - T. 27 . - S. 379-423, 623-656 .
↑ Gallager, R. G. Alacsony sűrűségű paritásellenőrző kódok . - Cambridge : MIT Press, 1963 . — 90. o.
↑ David JC MacKay és Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes", Electronics Letters, 1996. július
↑ David JC MacKay. Információelmélet, következtetési és tanulási algoritmusok . - KUPA, 2003. - ISBN 0-521-64298-1 .
↑ Dr. Lin Nan Lee. LDPC kódok, alkalmazás a következő generációs kommunikációs rendszerekre // IEEE Semianual Vehicular Technology Conference. - 2003. október. Archiválva az eredetiből: 2006. október 8.
↑ 1 2 Slyusar V. I. LDPC és polárkódok szintézise a mátrixok végterméke alapján.// Education, Science and Business Development: Results 2020: abstracts of the International Scientific and Practical Internet Conference, 2020. december 3-4. – 2. rész - Pp. 393-396. [1] Archiválva : 2021. január 25. a Wayback Machine -nél .
↑ Yu.V. Kosolapov. Az Ozarov-Weiner séma alkalmazásáról információvédelemre vezeték nélküli többcsatornás adatátviteli rendszerekben // Információs terrorizmus elleni küzdelem : Tudományos és gyakorlati folyóirat. – 2007 . - No. 10 . - S. 111-120 . Archiválva az eredetiből: 2013. június 24.
↑ V. B. Afanasiev, D. K. Zigangirov „Az alacsony sűrűségű kódok egyes konstrukcióiról Reed-Solomon kóddal”
↑ David JC MacKay, Radford M. Neal Alacsony sűrűségű paritásellenőrző kódok Shannon-határhoz közeli teljesítménye . Letöltve: 2008. augusztus 28. Az eredetiből archiválva : 2007. április 17.. (határozatlan)
↑ J. Pearl. Valószínűségi érvelés intelligens rendszerekben: Valószínű következtetések hálózatai. Morgan Kaufmann, San Mateo, 1988.