Reed-Solomon kód
Ugrás a navigációhoz
Ugrás a kereséshez
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
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
Tartalomjegyzék
Konstrukció
- [math]\overline{u}= (u_0, u_1,\ldots , u_{n-1}) \quad u_i \in GF(q)[/math]
- [math]u(x)=u_0x+u_1x+ \ldots+ u_{n-1}x^{k-1} \quad deg(u(x))=k-1[/math]
- [math]\alpha[/math] a legkisebb primitív elem [math]GF(q)[/math]-ban (rendje [math]q-1[/math])
- [math]n=q-1[/math] (nem rövidített R-S kód)
- [math]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}[/math]
- [math]\overline{c}^T= \left(\begin{array}{c} c_0 \\ c_1 \\ \vdots \\ c_{k-1} \end{array} \right)[/math]
- [math]\overline{c}=\overline{u}\overline{\overline{G}}[/math]
- [math]\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)[/math] generátormátrix
Alternatív konstrukció
- [math]\overline{c}= (c_0, c_1,\ldots , c_{n-1})[/math]
- [math]c(x)=c_0x+c_1x+ \ldots+ c_{n-1}x^{k-1}[/math]
- [math]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[/math]
- [math]\overline{\overline{H}}^T\overline{c}^T=0[/math]
- [math]\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)[/math] paritásellenőrző-mátrix
Általános módszer G és H gyors felírására
Kódolás
- [math]\overline{c}=\overline{u} \overline{\overline{G}}[/math]
- [math]\overline{u}[/math] az üzenet
- [math]\overline{\overline{G}}_{k \times n}[/math] a generátormátrix
Dekódolás
1.szindrómavektor kiszámítása: [math]\overline{s}=\overline{v} \overline{\overline{H}}[/math]
- [math]\overline{v}=\overline{c}+\overline{e}[/math] a vett vektor
- [math]\overline{e}[/math] a hibavektor
- [math]\overline{\overline{H}}_{(n-k) \times n}[/math] a paritásellenőrző-mátrix
- detekció PGZ-algoritmussal
- levágás
- szorzás az inverzmátrixszal [math]\overline{u}=\overline{\overline{G}}_{k \times k}^{-1} \overline{c}[/math]
PGZ-algoritmus
- Peterson-Gorenstein-Zierler
- ábra kellene
Az algoritmus lépései
- [math]\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)[/math] mátrixból kell kiválasztani a legnagyobb olyan [math]t \times t[/math] típusú almátrixot, amelyre [math]det(\overline{\overline{U}}_{t \times t})\neq 0[/math] modulo n.
- [math]\overline{\overline{U}}_{t \times t}\overline{L}=\overline{V}[/math], ahol [math]\overline{V}=\left(\begin{array}{c} -s_{t+1} \\ -s_{t+2} \\ \vdots \\ -s_{2t} \end{array} \right)[/math] és [math]\overline{L}=\left(\begin{array}{c} L_{t} \\ L_{t-1} \\ \vdots \\ L_1 \end{array} \right)[/math].
Ezt a lineáris egyenletrendszert modulo n megoldva kapjuk [math] L_1, L_2,\ldots , L_t[/math] értékeket.
- [math]L(x)=1+L_1x+L_2x^2+\ldots +L_tx^t[/math] egyenlet gyökei adják [math] X_1^{-1}, X_2^{-1},\ldots , X_t^{-1}[/math] értékeket, melyeknek ki kell számolni a multiplikatív inverzét modulo n, így kapjuk [math] X_1, X_2,\ldots , X_t[/math] értékeket.
- Az előző lépésben kapott [math]X_j[/math] értékek [math]\alpha[/math] alapú logarimtusát modulo n véve kapjuk a [math]i_j[/math]hibahelyeket: [math]\log_\alpha X_j=i_j[/math]. (A logaritmus számításhoz fel kell írni [math]\alpha[/math] hatványait modulo n.)
- [math]\overline{\overline{A}}_{t \times t}\overline{Y}=\overline{s}[/math], ahol [math]\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)[/math] és [math]\overline{Y}=\left(\begin{array}{c} Y_1 \\ Y_2 \\ \vdots \\ Y_t \end{array} \right)[/math] Ezt a lineáris egyenletrendszert megoldva kapjuk [math] Y_1, Y_2,\ldots , Y_t[/math] értékeket. Ezek az [math]Y_j[/math] hibaértékeket.
Reed-Solomon kódok ciklikus generálása
Reed-Solomon kódok "gyorsítása" -- spektrális kódolás
Példák
- példa
-- adamo - 2006.05.01. -- RebeliSzaboTamas - 2008.01.21.