BCH code: Difference between revisions

Revision as of 06:18, 26 December 2005

Revision as of 05:27, 27 December 2005

Line 1:

A '''BCH (Bose, Ray-Chaudhuri, Hocquenghem) code''' is a much studied code within the study of [[coding theory]] and more specifiicallyspecifically error-correcting codes. Roughly, a code is a way of encoding information to be transmitted so that any error introduced (e.g. by noise) during the transmission may be corrected on the receiving end. In technical terms a BCH code is a multilevel, cyclic, [[error]]-correcting, variable-length [[digital]] code used to correct mutiplemultiple random error patterns. BCH codes may also be used with multilevel [[phase-shift keying]] whenever the number of levels is a prime number or a power of a [[prime number]]. A BCH code in 11 levels has been used to represent the 10 decimal digits plus a sign [[numerical digit|digit]].

== Construction ==

BCH codes use [[field theory (mathematics)|field theory]] and polynomials over finite fields. To detect errors a check polynomial can be constructed so the receiving end can detect if some errors had occurred.

The BCH code with designed distance δ over the field GF(''q^m'') is contrustedconstructed by first finding a polynomial over GF(''q'') whose roots include δ consecutive powers of γ, some root of unity.

To construct a BCH code that can detect and correct up to two errors, we use the [[finite field]] GF(16) or '''Z'''₂[''x'']/<''x''⁴ + ''x'' + 1>. Now if &alpha; is a root of ''m''₁(''x'') = ''x''⁴ + ''x'' + 1, then ''m''₁ is minimal for &alpha; since

Line 85:

==Peterson Gorenstein Zierler Algorithm==

===Assumptions===

PetersonsPeterson's 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>

Line 128:

then

declare a empty error locator polynomial

stop petersonPeterson procedure.

end

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

continue from the beginning of petersonsPeterson's decoding

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

* Stop petersonPeterson procedure.

==Factoring Error Locator polynomial==