Content deleted Content added
No edit summary Tags: Mobile edit Mobile web edit |
Link suggestions feature: 3 links added. Tags: Visual edit Mobile edit Mobile web edit Newcomer task Suggested: add links |
||
Line 208:
====Peterson–Gorenstein–Zierler algorithm====
<!-- this confuses t (max number of errors that can be corrected) with ν (actual number of errors) -->
[[Peterson's algorithm]] is the step 2 of the generalized BCH decoding procedure. Peterson's algorithm is used to calculate the error locator polynomial coefficients <math> \lambda_1 , \lambda_2, \dots, \lambda_{v} </math> of a polynomial
: <math> \Lambda(x) = 1 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_v x^v .</math>
Line 407:
:<math>R(x) = C(x) + x^{13} + x^5 = x^{14} + x^{11} + x^{10} + x^9 + x^5 + x^4 + x^2</math>
In order to correct the errors, first calculate the syndromes. Taking <math>\alpha = 0010,</math> we have <math>s_1 = R(\alpha^1) = 1011,</math> <math>s_2 = 1001,</math> <math>s_3 = 1011,</math> <math>s_4 = 1101,</math> <math>s_5 = 0001,</math> and <math>s_6 = 1001.</math>
Next, apply the Peterson procedure by row-reducing the following [[augmented matrix]].
:<math>\left [ S_{3 \times 3} | C_{3 \times 1} \right ] =
\begin{bmatrix}s_1&s_2&s_3&s_4\\
Line 426:
==== Decoding with unreadable characters ====
Suppose the same scenario, but the received word has two unreadable characters [ 1 {{color|red|0}} 0 ? 1 1 ? 0 0 {{color|red|1}} 1 0 1 0 0 ]. We replace the unreadable characters by zeros while creating the polynomial reflecting their positions <math>\Gamma(x) = \left(\alpha^8x - 1\right)\left(\alpha^{11}x - 1\right).</math> We compute the syndromes <math>s_1=\alpha^{-7}, s_2=\alpha^{1}, s_3=\alpha^{4}, s_4=\alpha^{2}, s_5=\alpha^{5},</math> and <math>s_6=\alpha^{-7}.</math> (Using log notation which is independent on GF(2<sup>4</sup>) isomorphisms. For computation checking we can use the same representation for addition as was used in previous example. [[Hexadecimal]] description of the powers of <math>\alpha</math> are consecutively 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 with the addition based on bitwise xor.)
Let us make syndrome polynomial
| |||