BCH符号
このアルゴリズムは上述の工程の第2段階、すなわち誤り位置多項式の計算を行う。誤り位置多項式(error locator polynomial)の係数を λ 1 , λ 2 , ... , λ t {\displaystyle \lambda _{1},\lambda _{2},\dots ,\lambda _{t}} とすると、誤り位置多項式は Λ ( x ) = 1 + λ 1 x + λ 2 x 2 + ⋯ + λ t x t {\displaystyle \Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{t}x^{t}} となる。
[ t = d m i n − 1 2 ] {\displaystyle [t={\frac {d_{min}-1}{2}}]} 個の誤りを訂正できるよう設計された ( n , k , d m i n ) {\displaystyle (n,k,d_{min})} BCH符号に対して、PGZアルゴリズムは次のように実施される。
まず、 2 t {\displaystyle 2t} シンドロームの行列を生成する。
次に、下記のようにシンドローム値を配置した S t × t {\displaystyle S_{t\times t}} 行列を生成する。
S t × t = [ s 1 s 2 s 3 ... s t s 2 s 3 s 4 ... s t + 1 s 3 s 4 s 5 ... s t + 2 ... ... ... ... ... s t s t + 1 s t + 2 ... s 2 t − 1 ] {\displaystyle S_{t\times t}={\begin{bmatrix}s_{1}&s_{2}&s_{3}&\dots &s_{t}\\s_{2}&s_{3}&s_{4}&\dots &s_{t+1}\\s_{3}&s_{4}&s_{5}&\dots &s_{t+2}\\\dots &\dots &\dots &\dots &\dots \\s_{t}&s_{t+1}&s_{t+2}&\dots &s_{2t-1}\end{bmatrix}}}
下記のような c t x 1 {\displaystyle c_{tx1}} 行列を生成する。
C t × 1 = [ s t + 1 s t + 2 ⋮ ⋮ s 2 t ] {\displaystyle C_{t\times 1}={\begin{bmatrix}s_{t+1}\\s_{t+2}\\\vdots \\\vdots \\s_{2t}\end{bmatrix}}}
符号語 p ( x ) {\displaystyle p(x)} にはゼロでない項が d {\displaystyle d} 個未満存在するとする。すると、
p ( x ) = b 1 x j 1 + ⋯ + b d − 1 x j d − 1 , where j 1 < j 2 < ⋯ < j d − 1 {\displaystyle p(x)=b_{1}x^{j_{1}}+\cdots +b_{d-1}x^{j_{d-1}},{\text{ where }}j_{1}<j_{2}<\cdots <j_{d-1}}
と表せる。 α 1 , ... , α d − 1 {\displaystyle \alpha ^{1},\ldots ,\alpha ^{d-1}} は g ( x ) {\displaystyle g(x)} の根なので、 p ( x ) {\displaystyle p(x)} にとっても根である。したがって b 1 , ... , b d − 1 {\displaystyle b_{1},\ldots ,b_{d-1}} は i = 1 , ... , d − 1 {\displaystyle i=1,\ldots ,d-1} について以下の式も満たす。
p ( α i ) = b 1 α i j 1 + b 2 α i j 2 + ⋯ + b d − 1 α i j d − 1 = 0 {\displaystyle p(\alpha ^{i})=b_{1}\alpha ^{ij_{1}}+b_{2}\alpha ^{ij_{2}}+\cdots +b_{d-1}\alpha ^{ij_{d-1}}=0}