Virheenkorjauskoodi

Virheenkorjauskoodi (ECC, engl. Error Correcting Code) on informaatioteoriassa koodi, jossa jokainen datasignaali noudattaa tiettyjä rakennesääntöjä. Tällöin virhetilanteet voidaan havaita automaattisesti. EDAC (engl. Error Detection and Correction) tarkoittaa virheen ja havaitsemista ja sen korjaamista.^[1]

Virheenkorjausta varten tietokoneen muistipiireihin voidaan lisätä ylimääräisiä muistikennoja. Muistikennojen lisäys ei onnistu, ellei piirisarja tue tätä. Harva on valmis maksamaan muistikennojen lisähinnasta aiheutuvan kustannuksen kotikoneeseensa, joten virheenkorjauskoodi on käytännössä käytössä verkkopalvelimissa ja muissa kriittisissä kohteissa.^lähde?

Menetelmät

Yksinkertainen esimerkki virheitä korjaavasta koodista on ${\displaystyle n}$ bitin toistokoodi. Tätä koodia käytettäessä kanavaan lähetetään peräkkäin n kpl nollia, kun halutaan välittää vastaanottajalle bittitila 0 ja vastaavasti n kpl ykkösiä, kun halutaan välittää bittitila 1. Tämän koodi muodostuu siis koodisanajoukosta ${\displaystyle C=\lbrace 000...0,111...1\rbrace }$. Jos kanavan kautta kulkeneessa koodisanassa alle puolet biteistä on vaihtanut tilaansa, koodisana on mahdollista tunnistaa.

Virheitä korjaavien koodien teoriassa keskeinen käsite on koodin minimietäisyys. Kahden samanpituisen koodisanan välisellä etäisyydellä tarkoitetaan niiden kohtien lukumäärää, joissa ne eroavat toisistaan. Esimerkiksi binäärisanojen '0100011101' ja '0111011001' välinen etäisyys on kolme. Koodin minimietäisyydellä tarkoitetaan pienintä arvoa, minkä kahden eri kyseiseen koodiin kuuluvan koodisanan välinen etäisyys voi saada.

Koodin määrittämiseksi valitaan yleensä ensimmäiseksi jokin aakkosto, merk. ${\displaystyle A}$. Hyvin usein käytetään binääriaakkostoa ${\displaystyle A=\lbrace 0,1\rbrace }$.

Kaikkien ${\displaystyle n}$-pituisten aakkoston ${\displaystyle A}$ sanojen joukkoa merkitään tavallisesti ${\displaystyle A^{n}}$.

Koodi, jonka pituus on ${\displaystyle n}$, saadaan valitsemalla jokin ei-tyhjä osajoukko ${\displaystyle C\subseteq A^{n}}$.

Koodisanojen ${\displaystyle a_{1}a_{2}...a_{n}\in A^{n}}$ ja ${\displaystyle b_{1}b_{2}...b_{n}\in A^{n}}$ välinen Hamming-etäisyys on

${\displaystyle d(a_{1}a_{2}...a_{n},b_{1}b_{2}...b_{n})=\sum _{i=1,a_{i}\not =b_{i}}^{n}1}$.

Koodin ${\displaystyle C\subseteq A^{n}}$ minimietäisyys on

${\displaystyle d_{min}(C)=}$min${\displaystyle \lbrace d(c_{1},c_{2})\vert c_{1},c_{2}\in A^{n},\quad c_{1}\not =c_{2}\rbrace }$.

Helposti todetaan, että koodin, jonka sanojen lukumäärä on ${\displaystyle N=\sharp C}$, minimietäisyyden laskemiseen tarvitaan yleisessä tapauksessa

${\displaystyle {N \choose 2}={N! \over 2!(N-2)!}={N(N-1) \over 2}}$

koodisanojen vertailua.

Koodi ${\displaystyle C\subseteq A^{n}}$ kykenee korjaamaan ${\displaystyle r}$ virhettä, jos koodisanakeskiset ${\displaystyle r}$-säteiset pallot

${\displaystyle {\bar {B}}(c_{1},r)=\lbrace c_{2}\in C\vert d(c_{1},c_{2})\leq r\rbrace }$

ovat erilliset eli yhteispisteettömät.

Koodin virheenkorjauskyky ${\displaystyle e}$ saadaan, kun ${\displaystyle r}$ valitaan maksimaaliseksi.

Koodia sanotaan täydelliseksi ${\displaystyle n}$-pituiseksi ${\displaystyle e}$-virhettä korjaavaksi koodiksi, jos koodisanakeskiset ${\displaystyle e}$-säteiset pallot ovat yhteispisteettömät ja täyttävät koko avaruuden ${\displaystyle A^{n}}$.

Lineaariset koodit

Lineaarisia koodeja muodostettaessa aakkostoksi ${\displaystyle A}$ valitaan jokin äärellinen kunta ${\displaystyle \mathbb {F} _{q}}$, missä ${\displaystyle q}$ on kunnan alkioiden lukumäärä eli kunnan kertaluku.

Lineaariset koodit ovat vektoriavaruuden ${\displaystyle \mathbb {F} _{q}^{n}}$ lineaarisia aliavaruuksia.

Katso myös

• Hamming-koodi
• Reed–Solomon-koodit
• Muistivirhe

Lähteet

Kirjallisuutta

• Huffman, W. Cary & Pless, Vera: Fundamentals of error-correcting codes. Cambridge University Press, 2003. ISBN 0-521-78280-5. (englanniksi)