Reed-Solomon kód

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Konstrukció

• ${\overline {u}}=(u_{0},u_{1},\ldots ,u_{n-1})\quad u_{i}\in GF(q)$
• $u(x)=u_{0}x+u_{1}x+\ldots +u_{n-1}x^{k-1}\quad deg(u(x))=k-1$
• $\alpha$ a legkisebb primitív elem $GF(q)$-ban (rendje $q-1$)
• $n=q-1$ (nem rövidített R-S kód)
• $c_{i}=u(x)|_{x=\alpha ^{i}}=u_{0}+u_{1}\alpha ^{i}+u_{2}(\alpha ^{i})^{2}+\ldots +u_{k-1}(\alpha ^{i})^{k-1}$
• ${\overline {c}}^{T}=\left({\begin{array}{c}c_{0}\\c_{1}\\\vdots \\c_{k-1}\end{array}}\right)$
• ${\overline {c}}={\overline {u}}{\overline {\overline {G}}}$
• ${\overline {\overline {G}}}_{k\times n}=\left({\begin{array}{ccccc}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{k-1}&\alpha ^{2(k-1)}&\cdots &\alpha ^{(k-1)(n-1)}\end{array}}\right)$ generátormátrix

Alternatív konstrukció

• ${\overline {c}}=(c_{0},c_{1},\ldots ,c_{n-1})$
• $c(x)=c_{0}x+c_{1}x+\ldots +c_{n-1}x^{k-1}$
• $c(x)|_{x=\alpha ^{i}}=c_{0}+c_{1}\alpha ^{i}+c_{2}(\alpha ^{i})^{2}+\ldots +c_{k-1}(\alpha ^{i})^{i(n-1)},\quad i=1,2,\ldots ,n-k$
• ${\overline {\overline {H}}}^{T}{\overline {c}}^{T}=0$
• ${\overline {\overline {H}}}_{(n-k)\times n}=\left({\begin{array}{ccccc}1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{n-k}&\alpha ^{2(n-k)}&\cdots &\alpha ^{(k-1)(n-k)}\end{array}}\right)$ paritásellenőrző-mátrix

Kódolás

1. ${\overline {c}}={\overline {u}}{\overline {\overline {G}}}$

• ${\overline {u}}$ az üzenet
• ${\overline {\overline {G}}}_{k\times n}$ a generátormátrix

Dekódolás

1.szindrómavektor kiszámítása: ${\overline {s}}={\overline {v}}{\overline {\overline {H}}}$

• ${\overline {v}}={\overline {c}}+{\overline {e}}$ a vett vektor
• ${\overline {e}}$ a hibavektor
• ${\overline {\overline {H}}}_{(n-k)\times n}$ a paritásellenőrző-mátrix

1. detekció PGZ-algoritmussal
2. levágás
3. szorzás az inverzmátrixszal ${\overline {u}}={\overline {\overline {G}}}_{k\times k}^{-1}{\overline {c}}$

PGZ-algoritmus

• Peterson-Gorenstein-Zierler
• ábra kellene

Az algoritmus lépései

1. ${\overline {\overline {U}}}_{r\times r}=\left({\begin{array}{cccc}s_{1}&s_{1}&\cdots &s_{r}\\s_{2}&s_{3}&\cdots &s_{r+1}\\\vdots &\vdots &\ddots &\vdots \\s_{r}&s_{r+1}&\cdots &s_{2r-1}\\\end{array}}\right)$ mátrixból kell kiválasztani a legnagyobb olyan $t\times t$ típusú almátrixot, amelyre $det({\overline {\overline {U}}}_{t\times t})\neq 0$ modulo n.
2. ${\overline {\overline {U}}}_{t\times t}{\overline {L}}={\overline {V}}$, ahol ${\overline {V}}=\left({\begin{array}{c}-s_{t+1}\\-s_{t+2}\\\vdots \\-s_{2t}\end{array}}\right)$ és ${\overline {L}}=\left({\begin{array}{c}L_{t}\\L_{t-1}\\\vdots \\L_{1}\end{array}}\right)$.

Ezt a lineáris egyenletrendszert modulo n megoldva kapjuk $L_{1},L_{2},\ldots ,L_{t}$ értékeket.

1. $L(x)=1+L_{1}x+L_{2}x^{2}+\ldots +L_{t}x^{t}$ egyenlet gyökei adják $X_{1}^{-1},X_{2}^{-1},\ldots ,X_{t}^{-1}$ értékeket, melyeknek ki kell számolni a multiplikatív inverzét modulo n, így kapjuk $X_{1},X_{2},\ldots ,X_{t}$ értékeket.
2. Az előző lépésben kapott $X_{j}$ értékek $\alpha$ alapú logarimtusát modulo n véve kapjuk a $i_{j}$hibahelyeket: $\log _{\alpha }X_{j}=i_{j}$. (A logaritmus számításhoz fel kell írni $\alpha$ hatványait modulo n.)
3. ${\overline {\overline {A}}}_{t\times t}{\overline {Y}}={\overline {s}}$, ahol ${\overline {\overline {A}}}_{t\times t}=\left({\begin{array}{cccc}X_{1}&X_{2}&\cdots &X_{t}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{t}^{2}\\\vdots &\vdots &\ddots &\vdots \\X_{1}^{t}&X_{2}^{t}&\cdots &X_{t}^{t}\\\end{array}}\right)$ és ${\overline {Y}}=\left({\begin{array}{c}Y_{1}\\Y_{2}\\\vdots \\Y_{t}\end{array}}\right)$ Ezt a lineáris egyenletrendszert megoldva kapjuk $Y_{1},Y_{2},\ldots ,Y_{t}$ értékeket. Ezek az $Y_{j}$ hibaértékeket.

Példák

• példa

-- adamo - 2006.05.01. -- RebeliSzaboTamas - 2008.01.21.