BCH code: Difference between revisions

Revision as of 20:31, 9 December 2005

Revision as of 20:50, 9 December 2005

Line 81:

Popular decoding algorithms are,

# Peterson Gorenstein Zierler algorithm

# Peterson Gorenstein Zierler algorithm

===Peterson Gorenstein Zierler Algorithm===

==Assumptions==

Petersons algorithm, is the step 2, of the generalized BCH decoding procedure. We use Peterson's algorithm, to calculate the error locator polynomial coefficients

Petersons algorithm, is the step 2, of the generalized BCH decoding procedure. We use Peterson's algorithm, to calculate the error locator polynomial coefficients <math> \lambda_1 , \lambda_2 ... \lambda_{2t} </math>

of a polynomial

<math> \Lambda(x) = 1 + \lambda_1 X + \lambda_2 X^2 + ... + \lambda_{2t}X^{2t} </math>.

Now the procedure of the Peterson Gorenstein Zierler algorithm, for a given <math>(n,k,d_{min}) </math> BCH code

designed to correct <math>[t=\frac{d_{min}-1}{2}]</math> errors, is

<math>[t=\frac{d_{min}-1}{2}]</math>

errors, is

== Algorithm ==

* First generate the Matrix of <math>2t</math> syndromes,

* Next generate the <math>S_{txt}</math> matrix with the elements, Syndrome values,

Line 124:

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

* If <math> det(S_{t \times t}) = 0 </math>, then follow

if <math> t = 0</math>

then

if <math> t = 0</math>

then

declare a empty error locator polynomial

stop peterson procedure.

end

set <math> t \rightarrowleftarrow t -1</math>

continue from the beginning of petersons decoding

end

* After you have values of <math>\Lambda</math> you have with you the error locator polynomial.

* Stop peterson procedure.

==Factoring Error Locator polynomial==

<!-- # Berlekamp-Massey algorithm ==Berlekamp-Massey algorithm== -->

Now that you have <math>\Lambda(x)</math> polynomial, you can find its roots in the form <math>\Lambda(x)=(\alpha^i X + 1) (\alpha ^j X + 1) ... (\alpha^k X + 1)</math> using, the ''Chiens search'' algorithm. The exponential

powers of the primitive element <math>\alpha</math>, will yield the positions where errors occur in the received

word; hence the name 'error locator' polynomial.

==Correcting Errors==

For the case of binary BCH, you can directly correct the received vectors, at the positions of the powers of

primitive elements, of the error locator polynomial factors. Finally, just flip the bits for the received word,

at these positions, and we have the corrected code word, from BCH decoding.

We may also, ''Berlekamp-Massey algorithm'' for determinig the error locator polynomial, and hence solve the BCH decoding problem.