Korjauskoodi

Korjauskoodi (myös virheenkorjauskoodi ) on koodi , joka on suunniteltu havaitsemaan ja korjaamaan virheet .

Päätekniikkana on lisätä erityisesti strukturoitua redundanttia tietoa (esimerkiksi shekkinumero ) hyötykuormaan kirjoitettaessa (lähetettäessä) ja luettaessa (vastaanottaessa) käyttämällä tällaisia redundantteja tietoja virheiden havaitsemiseen ja korjaamiseen. Korjattavien virheiden määrä on rajoitettu ja riippuu käytettävästä koodista.

Virheenilmaisukoodit (joilla voidaan todeta vain virheen tosiasia) kuuluvat samoihin koodiluokkiin kuin virheenkorjauskoodit. Itse asiassa mitä tahansa virheenkorjauskoodia voidaan käyttää myös virheiden havaitsemiseen (jolloin se pystyy havaitsemaan enemmän virheitä kuin se pystyi korjaamaan). Virheenkorjauskoodeja käytetään digitaalisissa viestintäjärjestelmissä , mukaan lukien: satelliitti-, radio-, solu-, tiedonsiirto puhelinkanavien kautta sekä tiedon tallennusjärjestelmissä, mukaan lukien magneettiset ja optiset. Virheentunnistuskoodeja käytetään useilla verkkoprotokollien tasoilla .

Virheenkorjauskoodit on jaettu datan kanssa työskentelytavan mukaan lohkoon , joka jakaa tiedon vakiopituisiksi fragmenteiksi ja käsittelee jokaisen niistä erikseen, sekä konvoluutioon , joka toimii datan kanssa jatkuvana virtana. .

Estä koodit

Lohkokoodi, joka jakaa tiedon bittipituisiksi fragmenteiksi ja muuntaa ne bittipituisiksi koodisanoiksi, on yleensä merkitty ; numeroa kutsutaan koodinopeudeksi . Jos koodi jättää alkuperäiset bitit ennalleen ja lisää tarkistuksia, tällaista koodia kutsutaan systemaattiseksi , muuten - ei- systeemiseksi . $k$ $n$ $(n,\;k)$ $R=\frac{k}{n}$ $k$ $nk$

Voit asettaa lohkokoodin eri tavoilla, mukaan lukien taulukko, jossa jokainen tietobittijoukko liittyy koodisanan bittiin. Hyvän koodin on kuitenkin täytettävä ainakin seuraavat kriteerit: $k$ $n$

kyky korjata mahdollisimman monta virhettä,
mahdollisimman vähän redundanssia,
koodauksen ja dekoodauksen helppous.

Yllä olevat vaatimukset ovat yleensä ristiriidassa keskenään, joten koodeja on suuri määrä, joista jokainen soveltuu tiettyyn tehtäviin. Melkein kaikki käytetyt koodit ovat lineaarisia , mikä johtuu siitä, että epälineaarisia koodeja on paljon vaikeampi tutkia, ja niille on vaikea tarjota hyväksyttävää helpotusta koodaukseen ja dekoodaukseen.

Yleisen muodon lineaariset koodit

Lineaarinen lohkokoodi on sellainen koodi, jonka koodisanojen joukko muodostaa -ulotteisen lineaarisen aliavaruuden -ulotteisessa lineaariavaruudessa , joka on isomorfinen -bittisten vektoreiden avaruuden kanssa . $k$ $C$ $n$ $k$

Tämä tarkoittaa, että koodaustoiminto vastaa alkuperäisen bittivektorin kertomista ei-degeneroituneella matriisilla , jota kutsutaan generaattorimatriisiksi. $k$ $G$

Aliavaruudelle , joka on ortogonaalinen suhteessa tämän aliavaruuteen ja matriisiin , joka määrittää tämän aliavaruuden perustan , ja mille tahansa vektorille , seuraava on totta: $C$ $C^{\perp}$ $H$ $\overrightarrow{v}\in C$

{\overrightarrow {v}}H^{T}={\overrightarrow {0}}

. Minimietäisyys ja korjaava teho

Hamming-etäisyys (Hamming-metriikka) kahden koodisanan välillä on eri bittien lukumäärä vastaavissa paikoissa: $\overrightarrow{u}$ $\overrightarrow{v}$

d_H(\overrightarrow{u},\;\overrightarrow{v})=\sum_s{|u^{(s)}-v^{(s)}|}

Pienin Hamming-etäisyys on lineaarisen lohkokoodin tärkeä ominaisuus. Se näyttää kuinka kaukana koodit ovat toisistaan. Se määrittelee toisen, yhtä tärkeän ominaisuuden - korjaavan kyvyn : $d_\min=\min_{u\ne v}d_H(\overrightarrow{u},\;\overrightarrow{v})$

t=\left\lfloor\frac{d_\min-1}{2}\right\rfloor

Korjausteho määrittää, kuinka monta koodin lähetysvirhettä (tyyppiä ) voidaan taata korjata. Toisin sanoen jokaisen koodisanan ympärillä on -naapuruus , joka koostuu kaikista mahdollisista vaihtoehdoista koodisanan lähettämiseksi virheiden määrällä ( ) enintään . Kahden koodisanan kaksi lähialuetta eivät leikkaa toisiaan, koska koodisanojen välinen etäisyys (eli näiden naapureiden keskipisteet) on aina suurempi kuin niiden kaksi sädettä . $1\nuoli vasemmalle oikealle 0$ $A$ $t$ $A_t$ $A$ $1\nuoli vasemmalle oikealle 0$ $t$ $d_H(A,\;B)\geqslant d_\min>2t$

Siten vastaanotettuaan vääristyneen koodiyhdistelmän osoitteesta dekooderi päättää, että alkuperäinen koodiyhdistelmä oli , mikä ei korjaa enempää virheitä. $A_t$ $A$ $t$

Esimerkiksi, jos koodisanoja on vain kaksi ja niiden välinen Hamming-etäisyys on 3, sanan yhden bitin virhe voidaan korjata, koska myös tässä tapauksessa vastaanotettu sana on lähempänä koodisanaa kuin . Mutta jos kanava aiheutti virheitä kahdessa bitissä (joissa se poikkesi arvosta ), virheellisen lähetyksen tulos on lähempänä kuin , ja dekooderi päättää, että sana lähetettiin . $A$ $B$ $A$ $A$ $B$ $A$ $B$ $A$ $B$ $A$ $B$

Hamming-koodit

Hamming-koodit ovat yksinkertaisimpia lineaarisia koodeja, joiden vähimmäisetäisyys on 3, eli pystyvät korjaamaan yhden virheen. Hamming-koodi voidaan esittää siten, että oireyhtymä on:

\overrightarrow{s}=\overrightarrow{r}H^T

missä on vastaanotettu vektori, on yhtä suuri kuin sen paikan numero, jossa virhe tapahtui. Tämä ominaisuus tekee dekoodauksesta erittäin helppoa. $\overrightarrow{r}$

Yleinen menetelmä rivikoodien dekoodaamiseen

Mikä tahansa koodi (mukaan lukien epälineaarinen) voidaan dekoodata käyttämällä säännöllistä taulukkoa, jossa jokainen vastaanotetun sanan arvo vastaa todennäköisintä lähetettyä sanaa . Tämä menetelmä edellyttää kuitenkin valtavien taulukoiden käyttöä jo suhteellisen pienille koodisanoille. $\overrightarrow{r}_i$ $\overrightarrow{u}_i$

Lineaarisille koodeille tätä menetelmää voidaan yksinkertaistaa merkittävästi. Tässä tapauksessa jokaiselle vastaanotetulle vektorille lasketaan oireyhtymä . Koska , missä on koodisana ja virhevektori, niin . Sitten oireyhtymätaulukon avulla määritetään virhevektori, jonka avulla määritetään lähetetty koodisana. Tässä tapauksessa taulukko on paljon pienempi kuin edellistä menetelmää käytettäessä. $\overrightarrow{r}_i$ $\overrightarrow{s}_i=\overrightarrow{r}_i H^T$ $\overrightarrow{r}_i=\overrightarrow{v}_i+\overrightarrow{e}_i$ $\overrightarrow{v}_i$ $\overrightarrow{e}_i$ $\overrightarrow{s}_i=\overrightarrow{e}_i H^T$

Lineaariset sykliset koodit

Huolimatta siitä, että lineaaristen koodien dekoodaus on paljon helpompaa kuin useimpien epälineaaristen koodien dekoodaus, useimmille koodeille tämä prosessi on silti melko monimutkainen. Syklisillä koodeilla on yksinkertaisemman dekoodauksen lisäksi muita tärkeitä ominaisuuksia.

Syklinen koodi on lineaarinen koodi , jolla on seuraava ominaisuus: if on koodisana, niin sen syklinen permutaatio on myös koodisana. $\overrightarrow{v}$

Syklisen koodin sanat esitetään kätevästi polynomeina. Esimerkiksi koodisana esitetään polynomina . Tässä tapauksessa koodisanan syklinen siirto vastaa polynomin kertomista modulolla . $\overrightarrow{v}=(v_0,\;v_1,\;\ldots,\;v_{n-1})$ $v(x)=v_0+v_1 x+\ldots+v_{n-1}x^{n-1}$ $x$ $x^n-1$

Useimmiten käytetään binäärisiä syklisiä koodeja (eli ne voivat ottaa arvot 0 tai 1). $v_0,\;v_1,\;\ldots$

Polynomin luominen

Voidaan osoittaa, että kaikki tietyn syklisen koodin koodisanat ovat tietyn generoivan (generaattorin) polynomin kerrannaisia . Generaattoripolynomi on jakaja . $g(x)$ $x^n-1$

Generoivan polynomin avulla koodaus suoritetaan syklisellä koodilla. Erityisesti:

ei-systeeminen koodaus suoritetaan kertomalla koodattu vektori arvolla : ; $g(x)$ $v(x)=u(x)g(x)$
systemaattinen koodaus suoritetaan "lisäämällä" koodattuun sanaan jaon loppuosa : lla , eli . $x^{nk}u(x)$ $g(x)$ $v(x)=x^{nk}u(x)+[x^{nk}u(x)\,\bmod\,g(x)]$

CRC-koodit

CRC - koodit ( englanniksi cyclic redundancy check - cyclic redundant check) ovat systemaattisia koodeja, joiden tarkoituksena ei ole korjata virheitä, vaan havaita ne. He käyttävät edellä kuvattua systemaattista koodausmenetelmää: "tarkistussumma" lasketaan jakamalla luvulla . Koska virheenkorjausta ei tarvita, lähetyksen validointi voidaan tehdä samalla tavalla. $x^{nk}u(x)$ $g(x)$

Näin ollen polynomin muoto määrittää tietyn CRC-koodin. Esimerkkejä suosituimmista polynomeista: $g(x)$

Koodinimi	Tutkinto	Polynomi
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC- CCITT	16	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^ {8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

BCH-koodit

Bose-Chowdhury-Hockwingham (BCH) -koodit ovat syklisten koodien alaluokka. Niiden erottuva piirre on kyky rakentaa BCH-koodi, jonka vähimmäisetäisyys on vähintään annettu. Tämä on tärkeää, koska yleisesti ottaen minimikoodietäisyyden määrittäminen on erittäin vaikea tehtävä.

Reed-Solomon virheenkorjauskoodit

Reed-Solomon-koodit ovat ei-binaarisia syklisiä koodeja, joiden avulla voit korjata tietolohkojen virheet. Koodivektorin elementit eivät ole bittejä, vaan bittiryhmiä (lohkoja). Tavuilla ( oktettilla ) toimivat Reed-Solomon-koodit ovat hyvin yleisiä.

Matemaattisesti Reed-Solomon-koodit ovat BCH-koodeja .

Lohkokoodien edut ja haitat

Vaikka lohkokoodit pärjäävät yleensä hyvin harvoin mutta suurilla virhepurskeilla , ne ovat vähemmän tehokkaita toistuvissa mutta pienissä virheissä (esimerkiksi AWGN -kanavassa).

Konvoluutiokoodit

Konvoluutiokoodit, toisin kuin lohkokoodit, eivät jaa tietoa fragmenteiksi ja toimivat sen kanssa kuten jatkuvan tietovirran kanssa. Tällaiset koodit generoidaan pääsääntöisesti diskreetillä lineaarisella aikainvariantilla järjestelmällä . Siksi, toisin kuin useimmat lohkokoodit, konvoluutiokoodaus on hyvin yksinkertainen toimenpide, mitä ei voida sanoa dekoodauksesta.

Konvoluutiokoodikoodaus suoritetaan siirtorekisterillä , jonka väliotokset summataan modulo kaksi. Tällaisia summia voi olla kaksi (useimmiten) tai useampia.

Konvoluutiokoodit dekoodataan yleensä Viterbi-algoritmilla , joka yrittää palauttaa lähetetyn sekvenssin maksimitodennäköisyyskriteerin mukaisesti .

Konvoluutiokoodit toimivat tehokkaasti valkoisen kohinan kanavassa, mutta eivät käsittele hyvin virhepurskeita. Lisäksi, jos dekooderi tekee virheen, se tuottaa aina virhepurskeen ulostulossaan.

kaskadikoodaus. Iteratiivinen dekoodaus

Eri koodausmenetelmien edut voidaan yhdistää käyttämällä ketjutettua koodausta . Tässä tapauksessa tiedot koodataan ensin yhdellä koodilla ja sitten toisella, jolloin saadaan tuotekoodi .

Esimerkiksi seuraava rakenne on suosittu: tiedot koodataan Reed-Solomon-koodilla, sitten limitetään (merkit sijaitsevat lähellä, kaukana toisistaan) ja koodataan konvoluutiokoodilla. Vastaanottimessa dekoodataan ensin konvoluutiokoodi, sitten suoritetaan käänteinen lomitus (tässä tapauksessa konvoluutiodekooderin lähdössä olevat virhepurskeet jakautuvat Reed-Solomon-koodin eri koodisanoihin), ja sitten Reed- Salomon-koodi puretaan.

Jotkin tuotekoodit on suunniteltu erityisesti iteratiiviseen dekoodaukseen, jossa dekoodaus suoritetaan useilla kulkuehdoilla, joista jokainen käyttää edellisen koodin tietoja. Tämä mahdollistaa suuren tehokkuuden, mutta dekoodaus on resurssivaltaista. Nämä koodit sisältävät turbokoodit ja LDPC-koodit (gallager-koodit).

Koodien tehokkuuden arviointi

Koodien tehokkuuden määräävät sen korjaamien virheiden määrä, lisättävän redundantin tiedon määrä sekä koodauksen ja dekoodauksen toteutuksen monimutkaisuus (sekä laitteisto että tietokoneohjelmisto ).

Hamming-sidotut ja täydelliset koodit

Olkoon binäärilohkokoodi, jolla on korjauskyky . Sitten epäyhtälö (kutsutaan Hammingin rajoitukseksi) pätee: $(n,k)$ $t$

\sum_{i=0}^t {n\choose i}\leqslant 2^{nk}.

Koodeja, jotka täyttävät tämän yhtäläisyysrajan, kutsutaan täydellisiksi. Täydellisiä koodeja ovat esimerkiksi Hamming-koodit . Käytännössä usein käytetyt suuren korjausvoiman omaavat koodit (kuten Reed-Solomon -koodit ) eivät ole täydellisiä.

Kirjallisuus

Blahut R. Virheenhallintakoodien teoria ja käytäntö. — M .: Mir , 1986. — 576 s.
McWilliams F. J., Sloan N. J. A. Theory of error-correcting codes. Moskova: Radio ja viestintä, 1979.
Morelos-Zaragoza R. Virheenkorjauskoodauksen taito. Menetelmät, algoritmit, sovellus / per. englannista. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 s. — (Viestintämaailma). - 2000 kappaletta. — ISBN 5-94836-035-0 .