Reed-Solomon kódex

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

Reed-Solomon kódex
Valaki után elnevezve	Irving Reed [d] és Gustav Solomon [d]
Típusú	lineáris blokkkód polinom kód elválasztható kód maximális távolsággal
Blokk hossza	$n$
Az üzenet hossza	$k$
Távolság	$n-k+1$
Ábécé mérete	$q=p^{m}\geqslant n$ egyszerűnek , gyakran $p$ $q=n+1$
Kijelölés	${\displaystyle [n,k,n-k+1]_{q))$
Médiafájlok a Wikimedia Commons oldalon

A Reed -Solomon kódok ( eng. Reed-Solomon kódok ) nem bináris ciklikus kódok , amelyek lehetővé teszik az adatblokkokban lévő hibák javítását. A kódvektor elemei nem bitek, hanem bitcsoportok (blokkok). A Reed-Solomon kódok nagyon gyakoriak, bájtokkal (oktettekkel) működnek.

A Reed-Solomon kód a BCH kód speciális esete .

Jelenleg széles körben használják a CD -kről történő adat-helyreállítási rendszerekben , amikor olyan archívumot hoznak létre, amely tartalmazza a sérülések helyreállításához szükséges információkat, zajjavító kódolásban .

Történelem

Reed-Solomon kódot 1960-ban találta fel Reid és Gustav Solomon Massachusetts Institute of Lincoln Laboratóriumából A kód használatának ötletét a „Polinomiális kódok bizonyos véges mezőkön” című cikkben mutatták be. A hatékony dekódoló algoritmusokat 1969-ben Alvin Berlekamp és James Massey ( Berlekamp-Massey algoritmus ), 1977-ben David MandelbaumEuclid algoritmust használó módszer [1] ). A Reed-Solomon kódot először 1982 -ben használták a CD-k sorozatgyártásában.

Formai leírás

A Reed-Solomon kódok fontos speciális esetei egy olyan BCH kódnak, amelynek generátor polinomiális gyökerei ugyanabban a mezőben találhatók , amelyre a kód épül ( ). Legyen a sorrend mező eleme . Ha primitív elem , akkor sorrendje , azaz . Ekkor a mező feletti minimális fokú normalizált polinom , amelynek gyökei az elem egymást követő hatványai, a Reed -Solomon kód generáló polinomja a mező felett : $m=1$ $\alpha$ $\textstyle GF(q)$ $\textstyle n$ $\alpha$ $q-1$ $\alpha ^{{q-1}}=1,\quad \alpha ^{i}\neq 1,0<i<q-1$ $g(x)$ $\textstyle GF(q)$ $d-1$ $\alpha ^{{l_{0}}},\alpha ^{{l_{0}+1}},...,\alpha ^{{l_{0}+d-2}}$ $\alpha$ $\textstyle GF(q)$

g(x)=(x-\alpha ^{l_{0)))(x-\alpha ^{l_{0}+1})\dots (x-\alpha ^{l_{0}+ d-2}),

ahol egy egész szám (0-t és 1-et is beleértve), amelynek segítségével néha egyszerűsíthető a kódoló. Általában állítólag . A polinom mértéke . $l_{0}$ $l_{0}=1$ $\textstyle g(x)$ $d-1$

Az eredményül kapott kód hossza , a minimális távolság (az összes kódszópár összes Hamming-távolságának minimuma , lásd sorkód ) . A kód ellenőrző szimbólumokat tartalmaz, ahol a polinom mértékét jelöli; információs szimbólumok száma . Így a Reed-Solomon kód is egy maximális távolságú elválasztható kód (optimális a Singleton korlát értelmében ). $n$ $d$ $r=d-1=\deg(g(x))$ $\deg()$ $k=nr=n-d+1$ $\textstyle d=n-k+1$

A kódpolinomot a , információs polinomból kaphatjuk meg a és a szorzással : $c(x)$ $m(x)$ $\deg m(x)\leqslant k-1$ $m(x)$ $g(x)$

c(x)=m(x)g(x).

Tulajdonságok

A Reed-Solomon kód over , amely kijavítja a hibákat, paritásszimbólumokat igényel, és tetszőleges vagy kisebb hosszúságú hibacsomagok javítására használható . A Reiger-határtétel szerint a Reed-Solomon kódok optimálisak a csomagok hosszának arányát és a hibajavítás lehetőségét tekintve - további ellenőrző szimbólumok használatával a hibákat javítják (és kevesebbet). $\textstyle GF(q^{m})$ $t$ $2t$ $t$ $2t$ $t$

Tétel (Reiger-kötött) . Minden olyan lineáris blokkkódnak, amely kijavítja az összes vagy annál rövidebb sorozatot, legalább paritásszimbólumot kell tartalmaznia. $t$ $2t$

A Reed-Solomon kóddal kettős kód egyben Reed-Solomon kód is. A ciklikus kód kettős kódja az ellenőrző polinom által generált kód.

A mátrix akkor és csak akkor generál Reed-Solomon kódot, ha a mátrix bármely kisebb értéke nem nulla. $G=[{\begin{array}{cc}I_{{k*k}}&P_{{k*(nk)}}\\\end{array}}]$ $P_{{k*(nk)}}$

A Reed-Solomon kód kiszúrásakor vagy lerövidítésekor ismét a Reed-Solomon kódot kapjuk. A kiszúrás olyan művelet, amely egy ellenőrző karaktert eltávolít. A kód hossza eggyel csökken, a méret megmarad. A kód távolságának eggyel csökkentenie kell, különben a törölt karakter használhatatlan lenne. Rövidítés - egy tetszőleges kódoszlopot rögzítünk , és csak azokat a vektorokat jelöljük ki, amelyek ebben az oszlopban 0-t tartalmaznak.. Ez a vektorkészlet egy alteret alkot . $n$ $k$ $d$ $(n, k, d)$

Több hibajavítás

A Reed-Solomon kód az egyik leghatékonyabb kód a többszörös hibakitörések javítására. Olyan csatornákon használják, ahol olyan gyakran fordulhatnak elő hibakitörések, hogy azokat már nem lehet kijavítani egyedi hibákat javító kódokkal.

A kódtávolságú Reed-Solomon mező feletti kódot úgy tekinthetjük, mint egy mező feletti kódot, amely képes kijavítani az m karakterből álló vagy annál kevesebb blokkban koncentrált hibák bármilyen kombinációját . Egy hosszúságú csomag által befolyásolható hosszúságú blokkok legnagyobb száma , ahol , nem haladja meg , tehát a hibablokkokat kijavító kód mindig ki tudja javítani a teljes hosszúságú csomagok bármilyen kombinációját, ha . $(q^{m}-1,q^{m}-1-2t)$ $\textstyle GF(q^{m})$ $d=2t+1$ $((q^{m}-1)m,(q^{m}-1-2t)m)$ $\textstyle GF(q)$ $t$ $m$ $l_{i}$ $l_{i}\leqslant mt_{i}-(m-1)$ $t_{i}$ $t$ $p$ $l$ $l+(m-1)\leqslant mt$

Gyakorlati megvalósítás

A Reed-Solomon kódolás kétféleképpen valósítható meg: szisztematikus és nem szisztematikus ( a kódoló leírását lásd [1] ).

Nem szisztematikus kódolással az információ szót megszorozzuk valamilyen irreducibilis polinommal a Galois mezőben. A kapott kódolt szó teljesen eltér az eredetitől, és az információs szó kinyeréséhez egy dekódolási műveletet kell végrehajtani, és csak ezután lehet ellenőrizni az adatok hibáit. Az ilyen kódolás csak az információs adatok kinyeréséhez igényel sok erőforrást, miközben hibamentes lehet.

A szisztematikus kódolás során az ellenőrző szimbólumok egy információs szimbólumblokkhoz vannak rendelve , az egyes ellenőrző szimbólumok kiszámításakor az eredeti blokk összes szimbólumát felhasználjuk. Ebben az esetben nincs többletköltség az eredeti blokk kibontásánál, ha az információs szó nem tartalmaz hibákat, de a kódolónak/dekódolónak összeadási és szorzási műveleteket kell végrehajtania a paritásszimbólumok generálásához. Ezenkívül, mivel minden műveletet a Galois mezőben hajtanak végre, maguk a kódolási / dekódolási műveletek sok erőforrást és időt igényelnek. A gyors Fourier-transzformáción alapuló gyors dekódoló algoritmus a - nagyságrendű időben fut . $k$ $2t$ $k$ $k(nk)$ $O(ln^{2}{n})$

Kódolás

A kódolási művelet során az információs polinomot megszorozzuk a generáló polinommal. Az eredeti hosszúságú szó irreducibilis polinommal való szorzása szisztematikus kódolásban a következőképpen történhet: $S$ $k$

Az eredeti szóhoz nullákat adunk , ami egy polinomot eredményez . $2t$ $\textstyle T=Sx^{{2t}}$
Ezt a polinomot elosztjuk a generáló polinommal , a maradékot megtaláljuk , , ahol a hányados. $G$ $R$ $\textstyle Sx^{{2t}}=QG+R$ $K$
Ez a maradék a Reed-Solomon korrekciós kód lesz, az eredeti karakterblokkhoz van hozzárendelve. Kódszó érkezett . $\textstyle C=Sx^{{2t}}+R$

A kódoló műszakregiszterekből, összeadókból és szorzókból épül fel. A shift regiszter memóriacellákból áll, amelyek mindegyike tartalmazza a Galois mező egy-egy elemét.

Van egy másik kódolási eljárás is (praktikusabb és egyszerűbb). Legyen a mező egy primitív eleme , és legyen információs szimbólumok vektora, tehát információs polinom. Ekkor a vektor az információs vektornak megfelelő Reed-Solomon kódvektor . Ez a kódolási módszer azt mutatja, hogy a PC kódhoz egyáltalán nem szükséges ismerni a kód generáló polinomját és generáló mátrixát, elég ismerni a mező kiterjesztését a primitív elem és a kód dimenziója tekintetében. (a kód hossza ebben az esetben definíció szerint ). Az a helyzet, hogy a generáló polinom és a kódtávolság teljesen el van rejtve a különbség mögött. $a_{{i}}\in GF(q),(i=1,2,\lpontok ,k-1),\alpha \in GF(q)$ $GF(q)$ $a=(a_{0},a_{1},\ldots ,a_{{k-1}})$ $a(x)=a_{0}+a_{{1}}x+\ldots +a_{{k-1}}x^{{k-1}}$ $u=(a(1),a(\alpha ),\ldots ,a(\alpha ^{{q-2}}))$ $a$ $GF(q)$ $\alpha$ $k$ $n=q-1$ $nk$ $g(x)$

Dekódolás

Az autoregresszív spektrális dekódolási módszer szerint működő dekóder egymás után a következő műveleteket hajtja végre:

Kiszámítja a hiba szindrómát
Hibapolinomot épít
Megkeresi az adott polinom gyökereit
Meghatározza a hiba természetét
Javítja a hibákat

Hiba szindróma számítása

A hibaszindróma kiszámítását a szindrómadekóder végzi, amely a kódszót generátorpolinomra osztja. Ha van maradék az osztás során, akkor hiba van a szóban. A felosztás fennmaradó része a hiba szindróma.

A hibapolinom felépítése

A számított hiba szindróma nem jelzi a hibák helyzetét. A szindróma polinom foka , ami jóval kisebb , mint a kódszó mértéke . A hiba és az üzenetben elfoglalt hely közötti megfelelés megállapításához hibapolinomot állítunk össze. A hibapolinomot a Berlekamp-Massey algoritmus vagy az Euclid algoritmus segítségével valósítjuk meg. Euklidész algoritmusának megvalósítása egyszerű, de erőforrásigényes. Ezért a bonyolultabb, de kevésbé költséges Berlekamp-Massey algoritmust gyakrabban használják. A talált polinom együtthatói közvetlenül megfelelnek a kódszóban található hibás szimbólumok együtthatóinak. $2t$ $n$

Gyökerek keresése

Ebben a szakaszban megkeresik a hibapolinom gyökereit, amelyek meghatározzák a torz szimbólumok helyzetét a kódszóban. Chen eljárásával valósítják meg, amely egyenértékű a kimerítő felsorolással. Az összes lehetséges értéket szekvenciálisan behelyettesítjük a hibapolinomba, amikor a polinom eltűnik, a gyököket megtaláljuk.

A hiba jellegének meghatározása és javítása

A hibaszindróma és a talált polinomgyökök alapján a Forney algoritmus segítségével meghatározzuk a hiba jellegét, és összeállítjuk a torz szimbólumok maszkját. Az RS-kódok esetében azonban van egy egyszerűbb módszer a hibák természetének megállapítására. Ahogy a [2] -ban látható, tetszőleges egymást követő nullák halmazával rendelkező RS kódok esetén : $2t_{d}$ $\alpha ^{b},\alpha ^{{b+1}},\ldots ,\alpha ^{{b+\delta }},\delta =2t_{d}-1$

$e_{j_{l))={\frac {(\alpha ^{j_{l)))^{2-b}\Lambda (\alpha ^{-j_{l)))}{\sigma '(\alpha ^{-j_{l}})}},\quad \quad \quad (*)$

ahol a formális derivált a hibakereső polinomhoz képest , és $\sigma '(x)$ $x$ $\sigma (x)$ $\Lambda (x)=\sigma (x)S(x)\mod x^{2t_{d}+1}.$

Továbbá, miután megtalálta a maszkot, az XOR művelettel rákerül a kódszóra , és visszaállítja a torz karaktereket. Ezt követően a rendszer eldobja az ellenőrző karaktereket, és megkapja a helyreállított információs szót.

Szudán algoritmusa

Ebben az időben alapvetően új dekódolási módszereket alkalmaztak, például a Madhu Sudan által 1997-ben javasolt algoritmust [3] .

RS kódok kiterjesztése

Az RS kódhosszabbítás egy olyan eljárás, amelyben a kód hossza és távolsága növekszik (amíg a kód még mindig a Singleton-határon van , és a kód ábécéje nem változik), és a kód információs szimbólumainak száma nem változik [4] . Ez az eljárás növeli a kód korrekciós képességét . Fontolja meg az RS-kód egy szimbólummal való meghosszabbítását. Legyen egy RS kódvektor, amelynek generáló polinomja . Most engedd . Mutassuk meg, hogy ha egy szimbólumot adunk a vektorhoz, akkor annak súlya , ha . A kódvektornak megfelelő polinom felírható így , de ekkor a kifejezést figyelembe véve a -t kapjuk . , mivel 1 nem tartozik a generáló polinom gyökeinek listájához. De azt is , mivel ebben az esetben , ami a feltétellel ellentétben növelné a kód távolságát, ez azt jelenti, hogy a kód súlya megnőtt egy új karakter hozzáadása miatt . Új kódparaméterek , meghosszabbított vektor . A nem nyújtott kód ellenőrző mátrixának alakja van $\upsilon =(c_{0},c_{1},\ldots ,c_{{q-2}})$ $g(x)=(x-\alpha )(x-\alpha ^{2})\ldots (x-\alpha ^{{d-1}}),\deg g(x)=d-1=r =nk,n=q-1$ $c_{{q-1}}=-\sum _{{i=1}}^{{q-2}}c_{{i}}$ $\upsilon$ $c_{{q-1}}$ $d+1$ $c_{{q-1}}\neq 0$ $\upszilon(x)=g(x)*z(x)$ $c_{{q-1}}$ $\upszilon(1)=g(1)z(1)=-c_{{q-1}}$ $g(1)\neq 0$ $z(1)\neq 0$ $(x-1)g(x)|\upszilon (x)$ $c_{{q-1}}\neq 0$ $c_{{q-1}}$ $n_{1}=n+1,k_{1}=k,d_{1}=d+1$ $v_{1}=(c_{0},c_{1},\ldots ,c_{q-2},c_{q-1})$

H={\begin{Vmátrix}1&\alpha &\alpha ^{2}&\cdots &\alpha ^{{q-2}}\\1&\alpha ^{2}&\alpha ^{4}&\ cdots &\alpha ^{{2(q-2)}}\\\cdots &\cdots &\cdots &\cdots &\cdots \\1&\alpha ^{{d-1}}&\alpha ^{{ 2(d-1)}}&\cdots &\alpha ^{{(d-1)(q-2)}}\end{Vmátrix}}

Ekkor a PC kód egy szimbólumával meghosszabbított ellenőrző mátrix lesz

H_{1}={\begin{Vmátrix}1&1&1&\cdots &1&1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{{q-2}}&0\\1&\alpha ^{2 }&\alpha ^{4}&\cdots &\alpha ^{{2(q-2)}}&0\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\1&\alpha ^{{d-1}}&\alpha ^{{2(d-1)}}&\cdots &\alpha ^{{(d-1)(q-2)}}&0\end{Vmátrix}}

Alkalmazás

Közvetlenül a megjelenés után (XX. század 60-as évei) a Reed-Solomon kódokat külső kódként kezdték használni a műholdas kommunikációban használt kaszkád struktúrákban. Az ilyen konstrukciókban a -edik PC-szimbólumok (lehet több is) belső konvolúciós kódokkal vannak kódolva . A vételi oldalon ezeket a szimbólumokat egy puha Viterbi algoritmus dekódolja (az AWGN csatornákon érvényes ). Egy ilyen dekóder kijavítja a q-ary szimbólumok egyedi hibáit, de ha sorozathibák lépnek fel, és a q-ary szimbólumok egyes csomagjait helytelenül dekódolják, akkor a külső Reed-Solomon dekóder kijavítja ezeknek a hibáknak a sorozatait. Így az információtovábbítás megkívánt megbízhatósága megvalósul ( [5] ). $q$

Jelenleg a Reed-Solomon kódok nagyon széles hatókörrel rendelkeznek, mivel képesek megtalálni és kijavítani a többszörös hibákat.

Információk rögzítése és tárolása

A Reed-Solomon kódot a RAM vezérlőkben való írás és olvasás során, adatok archiválásakor, merevlemezre ( ECC ) írva, CD / DVD lemezekre írásakor használják. Még ha jelentős mennyiségű információ is megsérül, a lemezes adathordozó több szektora megsérül, akkor a Reed-Solomon kódok lehetővé teszik az elveszett információk nagy részének helyreállítását. Akkor is használatos, ha olyan adathordozókra ír, mint például mágnesszalagok és vonalkódok.

Írás CD-ROM-ra

A lemezről történő olvasás során előforduló hibák már a lemezgyártás szakaszában megjelennek, mivel a modern technológiákkal lehetetlen ideális lemezt készíteni. A hibákat a lemez felületén lévő karcok, por stb. is okozhatják. Ezért az olvasható CD készítésekor a CIRC (Cross Interleaved Reed Solomon Code) korrekciós rendszert alkalmazzuk. Ezt a korrekciót minden olyan eszközben végrehajtják, amely lehetővé teszi az adatok CD-kről történő olvasását firmware-szel ellátott chip formájában. A hibaészlelés és -javítás a redundancián és az átlapoláson alapul . Redundancia - az eredeti információ körülbelül 25%-a.

Az audio CD -re történő felvétel a Red Book szabványt használja . A hibajavítás két szinten, C1 és C2 szinten történik. Az első szakaszban történő kódoláskor az eredeti adatokhoz ellenőrző szimbólumokat adnak, a második szakaszban pedig újra kódolják az információkat. A kódoláson kívül a bájtokat interleaveljük ( interleaved ), így a javítás során a hibablokkok különálló bitekre bomlanak, amelyeket könnyebb javítani. Az első szinten az egy és két bájt hosszúságú (egy, illetve két hibás karakteres) hibás blokkokat észleli és javítja. A három bájtos hibablokkokat észleli és továbbítja a következő rétegnek. A második szinten a C2-ből származó 1 és 2 bájtos hibablokkokat észleli és javítja. Három hibás karakter észlelése végzetes hiba, és nem javítható.

Vezeték nélküli és mobil kommunikáció

Ezt a kódolási algoritmust használják a WiMAX hálózatokon keresztüli adatátvitelben , optikai kommunikációs vonalakban , műholdas és rádiórelé kommunikációban . A Forward Error Correction (FEC) módszer Reed-Solomon kódokon alapul.

Kódolási példák

Hexadecimális (15,11) Reed-Solomon kód

Hadd . Akkor $t=2,l_{0}=1$

$g(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)=x^4+\alpha^{13}x^3+ \alpha^{6}x^2+\alpha^{3}x+\alpha^{10}.$

A fokozat 4, és . Minden mezőelem leképezhető 4 bitre. Az információs polinom egy 11 karakterből álló sorozat , amely 44 bitnek felel meg, a teljes kódszó pedig 60 bites halmaz. $g(x)$ $nk=4$ $k=11$ ${\mathrm {GF}}(16)$ ${\mathrm {GF}}(16)$

8 éves (7,3) Reed-Solomon kód

Hadd . Akkor $t=2,l_{0}=4$

$g(x)=(x-\alpha ^{4})(x-\alpha ^{5})(x-\alpha ^{6})(x-\alpha ^{0})=x ^{4}+\alpha ^{6}x^{3}+\alpha ^{6}x^{2}+\alpha ^{3}x+\alpha .$

Legyen az információs polinom alakja:

$m(x)=\alpha ^{4}x^{2}+x+\alpha ^{3}.$

A nem szisztematikus kód kódszava a következőképpen lesz írva:

$c(x)=m(x)g(x)=(\alpha ^{4}x^{2}+x+\alpha ^{3})(x^{4}+\alpha ^{6 }x^{3}+\alpha ^{6}x^{2}+\alpha ^{3}x+\alpha )=\alpha ^{4}x^{6}+\alpha x^{5}+ \alpha ^{6}x^{4}+0x^{3}+0x^{2}+\alpha ^{5}x+\alpha ^{4},$

amely hét nyolcas karakterből álló sorozat.

Egy alternatív kódolási módszer a 9 éves (8,4) Reed-Solomon kódhoz

Szerkesszük meg a Galois-mezőt modulo polinomnak . Legyen a gyökér, akkor a mezőtábla így néz ki: $GF(3^{2})$ $x^{2}+x+2$ $\alpha$ $\alpha ^{2}+\alpha +2=0$

0=0=(00),

\alpha ^{0}=1=(10),

\alpha ^{1}=\alpha =(01),

\alpha ^{2}=1+2\alpha =(12),

\alpha ^{3}=2+2\alpha =(22),

\alpha ^{4}=2=(20),

\alpha ^{5}=2\alpha =(02),

\alpha ^{6}=2+\alpha =(21),

\alpha ^{7}=1+\alpha =(11).

Legyen az információs polinom , majd a konstruált mezőn a megfelelő számításokat végezve kapjuk: ${\displaystyle a(x)=1+\alpha x+\alpha ^{2}x^{2}+\alpha ^{3}x^{3))$ $a(1)=\alpha ^{2},\ a(\alpha )=0,\ a(\alpha ^{2})=\alpha ^{6},\ a(\alpha ^{3 })=0,\ a(\alpha ^{4})=\alpha ^{5},\ a(\alpha ^{5})=0,\ a(\alpha ^{6})=\alpha ^ {7},\ a(\alpha ^{7})=1.$

Ennek eredményeként létrejött egy paraméterekkel rendelkező RS kódvektor . Ezzel befejeződik a kódolás. Vegyük észre, hogy ezzel a módszerrel nem volt szükségünk generáló kódpolinomra [4] . $n=8,\ k=4,\ d=5$

Dekódolási példák

Generálja a mezőt egy primitív elem, amelynek irreducibilis polinomja . Akkor . Hadd . Ekkor a PC kód generáló polinomja egyenlő . Most fogadjuk el a polinomot . Akkor . Ezután a kulcsfontosságú egyenletrendszert a következő formában kapjuk meg: $GF(2^{3})$ $p(x)=x^{3}+x+1$ $p(\alpha )=\alpha ^{3}+\alpha +1=0$ $b=0,\t_{d}=2$ $g(x)=(x+1)(x+\alpha )(x+\alpha ^{2})(x+\alpha ^{3})=x^{4}+\alpha ^{2}x ^{3}+\alpha ^{5}x^{2}+\alpha ^{5}x+\alpha ^{6}$ $r(x)=\alpha x^{2}+\alpha ^{5}x^{4}$ $S_{1}=r(1)=\alpha +\alpha ^{5}=\alpha ^{6},\ S_{2}=r(\alpha )=\alpha ^{5},\ S_{3}=\alpha ,\ S_{4}=\alpha$

${\begin{pmatrix}\alpha ^{6}&\alpha ^{5}\\\alpha ^{5}&\alpha \end{pmatrix)){\begin{pmatrix}\sigma _{2 }\\\sigma _{1}\end{pmatrix}}={\begin{pmatrix}\alpha \\\alpha \end{pmatrix}}.$

Most nézzük meg az euklideszi algoritmust ennek az egyenletrendszernek a megoldására.

Kezdeti feltételek :

r_{0}(x)=x^{5},\ r1(x)=S(x)=1+\alpha ^{6}x+\alpha ^{5}x^{2}+\ alfa x^{3}+\alpha x^{4},

b_{0}(x)=0,\ b_{1}(x)=1;

$i=2$

x^{5}=(1+\alpha ^{6}x+\alpha ^{5}x^{2}+\alpha x^{3}+\alpha x^{4})(\alpha ^{6}x+\alpha ^{6})+\alpha ^{5}x+x^{2}+\alpha x+\alpha ^{6},

r_{2}(x)=\alpha ^{5}x^{3}+x^{2}+\alpha x+\alpha ^{6},

q_{2}(x)=\alpha ^{6}x+\alpha ^{6},

b_{2}(x)=0+(\alpha ^{6}x+\alpha ^{6})(1)=\alpha ^{6}x+\alpha ^{6};

$i=3$

$1+\alpha ^{6}x+\alpha ^{5}x^{2}+\alpha x^{3}+\alpha x^{4}=(\alpha ^{5}x^{ 3}+x^{2}+\alpha x+\alpha ^{6})(\alpha ^{3}x+\alpha ^{2})+\alpha ^{6}x^{2}+\alpha x+ \alpha ^{3},$

$\quad \quad ~r_{3}(x)=\alpha ^{6}x^{2}+\alpha x+\alpha ^{3},$

$\quad \quad ~q_{3}(x)=\alpha ^{3}x+\alpha ^{2},$

$\quad \quad ~b_{3}(x)=1+(\alpha ^{3}x+\alpha ^{2})(\alpha ^{6}x+\alpha ^{6})=\ alfa ^{3}+\alpha ^{4}x+\alpha ^{2}x^{2}.$

Az algoritmus leáll, mert , ebből következik, hogy ${\displaystyle \deg[r_{3}(x)]=2=t_{d))$ $\sigma (x)=\alpha ^{3}+\alpha ^{4}x+\alpha ^{2}x^{2}.$

Továbbá a Cheney algoritmussal végzett teljes keresés megadja a hibák helyzetét, ez a . Akkor a képlet alapján azt kapjuk $j_{1}=2,\quad j_{2}=4$ $(*)$ $e_{2}=\alpha ,\ e_{4}=\alpha .$

Így a dekódolt vektor . A dekódolás befejeződött, két hiba javítva [6] . $c(x)=r(x)+e(x)=0$

Alkalmazás

A Reed-Solomon kódot használják egyes tárolóalkalmazásokban, például a RAID 6 -ban ;

Lásd még

Jegyzetek

↑ Morelos-Zaragoza R. A hibajavító kódolás művészete. Módszerek, algoritmusok, alkalmazás / per. angolról. V. B. Afanasjev . - M . : Technosfera, 2006. - S. 92-93. — (A kommunikáció világa). - 2000 példányban. — ISBN 5-94836-035-0 .
↑ Morelos-Zaragoza R. A hibajavító kódolás művészete. Módszerek, algoritmusok, alkalmazás / per. angolról. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 p. — (A kommunikáció világa). - 2000 példányban. — ISBN 5-94836-035-0 .
↑ Szudáni algoritmus . Letöltve: 2018. december 24. Az eredetiből archiválva : 2018. december 24.. (határozatlan)
↑ 1 2 Sagalovich, 2007 , p. 212-213.
↑ M. Werner. A kódolás alapjai. - Technoszféra, 2004. - S. 268-269. — ISBN 5-94836-019-9 .
↑ Morelos-Zaragoza R. A hibajavító kódolás művészete. Módszerek, algoritmusok, alkalmazás / per. angolról. V. B. Afanasjev . - M . : Technosfera, 2006. - S. 116-119. — (A kommunikáció világa). - 2000 példányban. — ISBN 5-94836-035-0 .

Irodalom

Peterson W, Weldon E. Hibajavító kódok . - M . : Mir, 1976. - S. 596 .
Blahut R. A hibaellenőrző kódok elmélete és gyakorlata. — M .: Mir , 1986. — 576 p.
Berlekamp E. Algebrai kódoláselmélet = Algebraic Coding Theory. - M . : Mir, 1971. - S. 478 .
Egorov S.I. Hibajavítás a számítógép-perifériák információs csatornáiban. - Kurszk: KurskGTU, 2008. - S. 252.
Sagalovich Yu. L. Bevezetés az algebrai kódokba - M .: MIPT , 2007. - 262 p. — ISBN 978-5-7417-0191-1
Morelos-Zaragoza R. A hibajavító kódolás művészete. Módszerek, algoritmusok, alkalmazás / per. angolról. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 p. — (A kommunikáció világa). - 2000 példányban. — ISBN 5-94836-035-0 .
M. Werner. A kódolás alapjai. - Technoszféra, 2004. - 288 p. — ISBN 5-94836-019-9 .

Linkek

Reed-Solomon kódok ereje vagy a hamvakból feltámadt információ (Chris Kaspersky cikke)
Zajjavító kódolás csomaghálózatokban (Vargauzin V. cikke)
Hibajavító kód (ECC)
CD-R lemezek, technológia belülről
CD formátum
Reed-Solomon kódok
wiki.linuxformat.ru/wiki/LXF134:par2 - a par2 használatával , egy fájl-helyreállító segédprogrammal a Reed-Solomon Code módszerrel (orosz)