BCH code: Difference between revisions

Revision as of 09:33, 23 December 2021

Revision as of 04:02, 12 March 2022

Line 4:

One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an [[Abstract algebra|algebraic]] method known as [[syndrome decoding]]. This simplifies the design of the decoder for these codes, using small low-power electronic hardware.

BCH codes are used in applications such as satellite communications,<ref>{{cite web|title=Phobos Lander Coding System: Software and Analysis|url=http://ipnpr.jpl.nasa.gov/progress_report/42-94/94V.PDF|access-date=25 February 2012}}</ref> [[compact disc]] players, [[DVD]]s, [[Disk storage|disk drives]], [[solid-state drive]]s,<ref>{{cite web|title=Sandforce SF-2500/2600 Product Brief|url=http://www.sandforce.com/index.php?id=133&parentId=2&top=1|access-date=25 February 2012}}</ref> [[Post-quantum cryptography|quantum-resistant cryptography]]<ref>http://pqc-hqc.org/doc/hqc-specification_2020-05-29.pdf {{Bare URL PDF|date=March 2022}}</ref> and [[Bar codes|two-dimensional bar codes]].

== Definition and illustration ==

Line 11:

Given a [[prime number]] {{mvar|q}} and [[prime power]] {{math|''q''^''m''}} with positive integers {{mvar|m}} and {{mvar|d}} such that {{math|''d'' ≤ ''q''^''m'' − 1}}, a primitive narrow-sense BCH code over the [[finite field]] (or Galois field) {{math|GF(''q'')}} with code length {{math|''n'' {{=}} ''q''^''m'' − 1}} and [[Block code#The distance d|distance]] at least {{mvar|d}} is constructed by the following method.

Let {{mvar|α}} be a [[Simple_extensionSimple extension#Definition|primitive element]] of {{math|GF(''q''^''m'')}}.

For any positive integer {{mvar|i}}, let {{math|''m''_''i''(''x'')}} be the [[minimal polynomial (field theory)|minimal polynomial]] with coefficients in {{math|GF(''q'')}} of {{math|α^''i''}}.

The [[generator polynomial]] of the BCH code is defined as the [[least common multiple]] {{math|''g''(''x'') {{=}} lcm(''m''₁(''x''),…,''m''_{''d'' − 1}(''x''))}}.

Line 79:

The generator polynomial <math>g(x)</math> of a BCH code has coefficients from <math>\mathrm{GF}(q).</math>

In general, a cyclic code over <math>\mathrm{GF}(q^p)</math> with <math>g(x)</math> as the generator polynomial is called a BCH code over <math>\mathrm{GF}(q^p).</math>

The BCH code over <math>\mathrm{GF}(q^m)</math> and generator polynomial <math>g(x)</math> with successive powers of <math>\alpha</math> as roots is one type of [[Reed–Solomon code]] where the decoder (syndromes) alphabet is the same as the channel (data and generator polynomial) alphabet, all elements of <math>\mathrm{GF}(q^m)</math> .<ref>{{Harvnb|Gill|n.d.|p=3}}</ref> The other type of Reed Solomon code is an [[Reed%E2%80%93Solomon_error_correctionReed–Solomon error correction#Reed_Reed &_Solomon Solomon's_original_views original view:_The_codeword_as_a_sequence_of_values |The codeword as a sequence of values|original view Reed Solomon code]] which is not a BCH code.

== Properties ==

Line 202:

The first step is 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>

Three popular algorithms for this task are:

# [[#Peterson–Gorenstein–Zierler algorithm|Peterson–Gorenstein–Zierler algorithm]]

# [[Berlekamp–Massey algorithm]]

# [[Reed%E2%80%93Solomon_error_correctionReed–Solomon error correction#Euclidean_decoderEuclidean decoder|Sugiyama Euclidean algorithm]]

====Peterson–Gorenstein–Zierler algorithm====