BCH code: Difference between revisions

Revision as of 01:19, 28 September 2019

Revision as of 01:46, 30 September 2019

Line 196:

If there are nonzero syndromes, then there are errors. The decoder needs to figure out how many errors and the ___location of those errors.

If there is a single error, write this as <math>E(x) = e\,x^i,</math> where <math>i</math> is the ___location of the error and <math>e</math> is its magnitude. Then the first two syndromes are

:<math>\begin{align}

where <math>i</math> is the ___location of the error and <math>e</math> is its magnitude. Then the first two syndromes are

:<math> s_c &= e\,\alpha^{c\,i}</math> \\

:<math> s_{c+1} &= e\,\alpha^{(c+1)\,i} = \alpha^i s_c</math>

\end{align}</math>

so together they allow us to calculate <math>e</math> and provide some information about <math>i</math> (completely determining it in the case of Reed–Solomon codes).

If there are two or more errors,

:<math>E(x) = e_1 x^{i_1} + e_2 x^{i_2} + \cdots \, </math>

It is not immediately obvious how to begin solving the resulting syndromes for the unknowns <math>e_k</math> and <math>i_k.</math>

First step is finding locator polynomial

:<math>\Lambda(x)The =first \prod_{j=1}^tstep \left(x\alpha^{i_j}is - 1\right)</math>finding, compatible with computed syndromes and with minimal possible <math>t.,</math> locator polynomial:

:<math>\Lambda(x) = \prod_{j=1}^t \left(x\alpha^{i_j} - 1\right)</math>

Two popular algorithms for this task are:

Line 218 ⟶ 221:

: <math> \Lambda(x) = 1 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_v x^v .</math>

Now the procedure of the Peterson–Gorenstein–Zierler algorithm.<ref>{{Harvnb|Gorenstein|Peterson|Zierler|1960}}</ref> Expect we have at least 2''t'' syndromes ''s''_''c'',... …, ''s''_{''c''+2''t''−1}. Let ''v''&nbsp;=&nbsp;''t''.

Let ''v''&nbsp;=&nbsp;''t''.

{{ordered list

| Start by generating the <math>S_{v\times v}</math> matrix with elements that are syndrome values

Line 242 ⟶ 244:

: <math>S_{v \times v} \Lambda_{v \times 1} = -C_{v \times 1\,} .</math>

| If the determinant of matrix <math>S_{v \times v}</math> is nonzero, then we can actually find an inverse of this matrix and solve for the values of unknown <math>\Lambda</math> values.

| If <math> \det\left(S_{v \times v}\right) = 0 ,</math> then follow

if <math>v = 0</math>

then