Reed-Solomon kód

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

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

Kódolás

1. [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

1. detekció PGZ-algoritmussal
2. levágás
3. 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

1. [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.
2. [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.

1. [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.
2. 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.)
3. [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.

Példák

• példa

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