information:highlighting
Error locator polynomial

There is a linear recurrence relation that gives rise to a system of linear equations. Solving those equations identifies those error locations X.

Define the error locator polynomial Λ(x) as Λ (x) = ∏ k = 1 ν (1 − x X k) = 1 + Λ 1 x 1 + Λ 2 x 2 + ⋯ + Λ ν x ν {\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }}

The zeros of Λ(x) are the reciprocals X k − 1 {\displaystyle X_{k}^{-1}}. This follows from the above product notation construction since if x = X k − 1 {\displaystyle x=X_{k}^{-1}} then one of the multiplied terms will be zero (1 − X k − 1 ⋅ X k) = 1 − 1 = 0 {\displaystyle (1-X_{k}^{-1}\cdot X_{k})=1-1=0}, making the whole polynomial evaluate to zero. Λ (X k − 1) = 0 {\displaystyle \Lambda (X_{k}^{-1})=0}

Let j {\displaystyle j} be any integer such that 1 ≤ j ≤ ν {\displaystyle 1\leq j\leq \nu }. Multiply both sides by Y k X k j + ν {\displaystyle Y_{k}X_{k}^{j+\nu }} and it will still be zero. Y k X k j + ν Λ (X k − 1) = 0. Y k X k j + ν (1 + Λ 1 X k − 1 + Λ 2 X k − 2 + ⋯ + Λ ν X k − ν) = 0. Y k X k j + ν + Λ 1 Y k X k j + ν X k − 1 + Λ 2 Y k X k j + ν X k − 2 + ⋯ + Λ ν Y k X k j + ν X k − ν = 0. Y k X k j + ν + Λ 1 Y k X k j + ν − 1 + Λ 2 Y k X k j + ν − 2 + ⋯ + Λ ν Y k X k j = 0. {\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0.\\&Y_{k}X_{k}^{j+\nu }\left(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu }\right)=0.\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0.\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\end{aligned}}}

Sum for k = 1 to ν and it will still be zero. ∑ k = 1 ν (Y k X k j + ν + Λ 1 Y k X k j + ν − 1 + Λ 2 Y k X k j + ν − 2 + ⋯ + Λ ν Y k X k j) = 0 {\displaystyle \sum _{k=1}^{\nu }\left(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0}

Collect each term into its own sum. (∑ k = 1 ν Y k X k j + ν) + (∑ k = 1 ν Λ 1 Y k X k j + ν − 1) + (∑ k = 1 ν Λ 2 Y k X k j + ν − 2) + ⋯ + (∑ k = 1 ν Λ ν Y k X k j) = 0 {\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0}

Extract the constant values of Λ {\displaystyle \Lambda } that are unaffected by the summation. (∑ k = 1 ν Y k X k j + ν) + Λ 1 (∑ k = 1 ν Y k X k j + ν − 1) + Λ 2 (∑ k = 1 ν Y k X k j + ν − 2) + ⋯ + Λ ν (∑ k = 1 ν Y k X k j) = 0 {\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0}

These summations are now equivalent to the syndrome values, which we know and can substitute in! This therefore reduces to S j + ν + Λ 1 S j + ν − 1 + ⋯ + Λ ν − 1 S j + 1 + Λ ν S j = 0 {\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0}

Subtracting S j + ν {\displaystyle S_{j+\nu }} from both sides yields S j Λ ν + S j + 1 Λ ν − 1 + ⋯ + S j + ν − 1 Λ 1 = − S j + ν {\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }}

Recall that j was chosen to be any integer between 1 and v inclusive, and this equivalence is true for any and all such values. Therefore, we have v linear equations, not just one. This system of linear equations can therefore be solved for the coefficients Λ of the error location polynomial: = {\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}} The above assumes the decoder knows the number of errors ν, but that number has not been determined yet. The PGZ decoder does not determine ν directly but rather searches for it by trying successive values. The decoder first assumes the largest value for a trial ν and sets up the linear system for that value. If the equations can be solved (i.e., the matrix determinant is nonzero), then that trial value is the number of errors. If the linear system cannot be solved, then the trial ν is reduced by one and the next smaller system is examined. (Gill n.d., p. 35)