Bch error correcting codes

In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called Galois field). BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Chandra Bose and D.K. Ray-Chaudhuri.^[1][2][3] The name Bose–Chaudhuri–Hocquenghem (and the acronym BCH) arises from the initials of the inventors’ surnames (mistakenly, in the case of Ray-Chaudhuri).

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 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,^[4] compact disc players, DVDs, disk drives, USB flash drives, solid-state drives,^[5] quantum-resistant cryptography^[6] and two-dimensional bar codes.

Definition and illustration[edit]

Primitive narrow-sense BCH codes[edit]

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

Let α be a primitive element of GF(q^m).
For any positive integer i, let m_i(x) be the minimal polynomial with coefficients in GF(q) of αⁱ.
The generator polynomial of the BCH code is defined as the least common multiple g(x) = lcm(m₁(x),…,m_{d − 1}(x)).
It can be seen that g(x) is a polynomial with coefficients in GF(q) and divides xⁿ − 1.
Therefore, the polynomial code defined by g(x) is a cyclic code.

Example[edit]

Let q = 2 and m = 4 (therefore n = 15). We will consider different values of d for GF(16) = GF(2⁴) based on the reducing polynomial z⁴ + z + 1, using primitive element α(z) = z. There are fourteen minimum polynomials m_i(x) with coefficients in GF(2) satisfying

The minimal polynomials are

The BCH code with has generator polynomial

It has minimal Hamming distance at least 3 and corrects up to one error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.

The BCH code with has generator polynomial

It has minimal Hamming distance at least 5 and corrects up to two errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.

The BCH code with has generator polynomial

It has minimal Hamming distance at least 7 and corrects up to three errors. Since the generator polynomial is of degree 10, this code has 5 data bits and 10 checksum bits. (This particular generator polynomial has a real-world application, in the format patterns of the QR code.)

The BCH code with and higher has generator polynomial

This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.

General BCH codes[edit]

General BCH codes differ from primitive narrow-sense BCH codes in two respects.

First, the requirement that be a primitive element of can be relaxed. By relaxing this requirement, the code length changes from to the order of the element

Second, the consecutive roots of the generator polynomial may run from instead of

Definition. Fix a finite field where is a prime power. Choose positive integers such that and is the multiplicative order of modulo

As before, let be a primitive th root of unity in and let be the minimal polynomial over of for all
The generator polynomial of the BCH code is defined as the least common multiple

Note: if as in the simplified definition, then is 1, and the order of modulo is
Therefore, the simplified definition is indeed a special case of the general one.

Special cases[edit]

The generator polynomial of a BCH code has coefficients from
In general, a cyclic code over with as the generator polynomial is called a BCH code over
The BCH code over and generator polynomial with successive powers of 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 .^[7] The other type of Reed Solomon code is an original view Reed Solomon code which is not a BCH code.

Properties[edit]

The generator polynomial of a BCH code has degree at most . Moreover, if and , the generator polynomial has degree at most .

A BCH code has minimal Hamming distance at least .

A BCH code is cyclic.

Encoding[edit]

Because any polynomial that is a multiple of the generator polynomial is a valid BCH codeword, BCH encoding is merely the process of finding some polynomial that has the generator as a factor.

The BCH code itself is not prescriptive about the meaning of the coefficients of the polynomial; conceptually, a BCH decoding algorithm’s sole concern is to find the valid codeword with the minimal Hamming distance to the received codeword. Therefore, the BCH code may be implemented either as a systematic code or not, depending on how the implementor chooses to embed the message in the encoded polynomial.

Non-systematic encoding: The message as a factor[edit]

The most straightforward way to find a polynomial that is a multiple of the generator is to compute the product of some arbitrary polynomial and the generator. In this case, the arbitrary polynomial can be chosen using the symbols of the message as coefficients.

As an example, consider the generator polynomial , chosen for use in the (31, 21) binary BCH code used by POCSAG and others. To encode the 21-bit message {101101110111101111101}, we first represent it as a polynomial over :

Then, compute (also over ):

Thus, the transmitted codeword is {1100111010010111101011101110101}.

The receiver can use these bits as coefficients in and, after error-correction to ensure a valid codeword, can recompute

Systematic encoding: The message as a prefix[edit]

A systematic code is one in which the message appears verbatim somewhere within the codeword. Therefore, systematic BCH encoding involves first embedding the message polynomial within the codeword polynomial, and then adjusting the coefficients of the remaining (non-message) terms to ensure that is divisible by .

This encoding method leverages the fact that subtracting the remainder from a dividend results in a multiple of the divisor. Hence, if we take our message polynomial as before and multiply it by (to «shift» the message out of the way of the remainder), we can then use Euclidean division of polynomials to yield:

Here, we see that is a valid codeword. As is always of degree less than (which is the degree of ), we can safely subtract it from without altering any of the message coefficients, hence we have our as

Over (i.e. with binary BCH codes), this process is indistinguishable from appending a cyclic redundancy check, and if a systematic binary BCH code is used only for error-detection purposes, we see that BCH codes are just a generalization of the mathematics of cyclic redundancy checks.

The advantage to the systematic coding is that the receiver can recover the original message by discarding everything after the first coefficients, after performing error correction.

Decoding[edit]

There are many algorithms for decoding BCH codes. The most common ones follow this general outline:

1. Calculate the syndromes s_j for the received vector
2. Determine the number of errors t and the error locator polynomial Λ(x) from the syndromes
3. Calculate the roots of the error location polynomial to find the error locations X_i
4. Calculate the error values Y_i at those error locations
5. Correct the errors

During some of these steps, the decoding algorithm may determine that the received vector has too many errors and cannot be corrected. For example, if an appropriate value of t is not found, then the correction would fail. In a truncated (not primitive) code, an error location may be out of range. If the received vector has more errors than the code can correct, the decoder may unknowingly produce an apparently valid message that is not the one that was sent.

Calculate the syndromes[edit]

The received vector is the sum of the correct codeword and an unknown error vector The syndrome values are formed by considering as a polynomial and evaluating it at Thus the syndromes are^[8]

for to

Since are the zeros of of which is a multiple, Examining the syndrome values thus isolates the error vector so one can begin to solve for it.

If there is no error, for all If the syndromes are all zero, then the decoding is done.

Calculate the error location polynomial[edit]

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 where is the location of the error and is its magnitude. Then the first two syndromes are

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

If there are two or more errors,

It is not immediately obvious how to begin solving the resulting syndromes for the unknowns and

The first step is finding, compatible with computed syndromes and with minimal possible locator polynomial:

Three popular algorithms for this task are:

1. Peterson–Gorenstein–Zierler algorithm
2. Berlekamp–Massey algorithm
3. Sugiyama Euclidean algorithm

Peterson–Gorenstein–Zierler algorithm[edit]

Peterson’s algorithm is the step 2 of the generalized BCH decoding procedure. Peterson’s algorithm is used to calculate the error locator polynomial coefficients of a polynomial

Now the procedure of the Peterson–Gorenstein–Zierler algorithm.^[9] Expect we have at least 2t syndromes s_c, …, s_c+2t−1. Let v = t.

Factor error locator polynomial[edit]

Now that you have the polynomial, its roots can be found in the form by brute force for example using the Chien search algorithm. The exponential
powers of the primitive element will yield the positions where errors occur in the received word; hence the name ‘error locator’ polynomial.

The zeros of Λ(x) are α^−i₁, …, α^−i_v.

Calculate error values[edit]

Once the error locations are known, the next step is to determine the error values at those locations. The error values are then used to correct the received values at those locations to recover the original codeword.

For the case of binary BCH, (with all characters readable) this is trivial; just flip the bits for the received word at these positions, and we have the corrected code word. In the more general case, the error weights can be determined by solving the linear system

Forney algorithm[edit]

However, there is a more efficient method known as the Forney algorithm.

Let

And the error evaluator polynomial^[10]

Finally:

where

Than if syndromes could be explained by an error word, which could be nonzero only on positions , then error values are

For narrow-sense BCH codes, c = 1, so the expression simplifies to:

Explanation of Forney algorithm computation[edit]

It is based on Lagrange interpolation and techniques of generating functions.

Consider and for the sake of simplicity suppose for and for Then

We want to compute unknowns and we could simplify the context by removing the terms. This leads to the error evaluator polynomial

Thanks to we have

Thanks to (the Lagrange interpolation trick) the sum degenerates to only one summand for

To get we just should get rid of the product. We could compute the product directly from already computed roots of but we could use simpler form.

As formal derivative

we get again only one summand in

So finally

This formula is advantageous when one computes the formal derivative of form

yielding:

where

Decoding based on extended Euclidean algorithm[edit]

An alternate process of finding both the polynomial Λ and the error locator polynomial is based on Yasuo Sugiyama’s adaptation of the Extended Euclidean algorithm.^[11] Correction of unreadable characters could be incorporated to the algorithm easily as well.

Let be positions of unreadable characters. One creates polynomial localising these positions
Set values on unreadable positions to 0 and compute the syndromes.

As we have already defined for the Forney formula let

Let us run extended Euclidean algorithm for locating least common divisor of polynomials and
The goal is not to find the least common divisor, but a polynomial of degree at most and polynomials such that
Low degree of guarantees, that would satisfy extended (by ) defining conditions for

Defining and using on the place of in the Fourney formula will give us error values.

The main advantage of the algorithm is that it meanwhile computes required in the Forney formula.

Explanation of the decoding process[edit]

The goal is to find a codeword which differs from the received word minimally as possible on readable positions. When expressing the received word as a sum of nearest codeword and error word, we are trying to find error word with minimal number of non-zeros on readable positions. Syndrom restricts error word by condition

We could write these conditions separately or we could create polynomial

and compare coefficients near powers to

Suppose there is unreadable letter on position we could replace set of syndromes by set of syndromes defined by equation Suppose for an error word all restrictions by original set of syndromes hold,
than

New set of syndromes restricts error vector

the same way the original set of syndromes restricted the error vector Except the coordinate where we have an is zero, if For the goal of locating error positions we could change the set of syndromes in the similar way to reflect all unreadable characters. This shortens the set of syndromes by

In polynomial formulation, the replacement of syndromes set by syndromes set leads to

Therefore,

After replacement of by , one would require equation for coefficients near powers

One could consider looking for error positions from the point of view of eliminating influence of given positions similarly as for unreadable characters. If we found positions such that eliminating their influence leads to obtaining set of syndromes consisting of all zeros, than there exists error vector with errors only on these coordinates.
If denotes the polynomial eliminating the influence of these coordinates, we obtain

In Euclidean algorithm, we try to correct at most errors (on readable positions), because with bigger error count there could be more codewords in the same distance from the received word. Therefore, for we are looking for, the equation must hold for coefficients near powers starting from

In Forney formula, could be multiplied by a scalar giving the same result.

It could happen that the Euclidean algorithm finds of degree higher than having number of different roots equal to its degree, where the Fourney formula would be able to correct errors in all its roots, anyway correcting such many errors could be risky (especially with no other restrictions on received word). Usually after getting of higher degree, we decide not to correct the errors. Correction could fail in the case has roots with higher multiplicity or the number of roots is smaller than its degree. Fail could be detected as well by Forney formula returning error outside the transmitted alphabet.

Correct the errors[edit]

Using the error values and error location, correct the errors and form a corrected code vector by subtracting error values at error locations.

Decoding examples[edit]

Decoding of binary code without unreadable characters[edit]

Consider a BCH code in GF(2⁴) with and . (This is used in QR codes.) Let the message to be transmitted be [1 1 0 1 1], or in polynomial notation,
The «checksum» symbols are calculated by dividing by and taking the remainder, resulting in or [ 1 0 0 0 0 1 0 1 0 0 ]. These are appended to the message, so the transmitted codeword is [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ].

Now, imagine that there are two bit-errors in the transmission, so the received codeword is [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. In polynomial notation:

In order to correct the errors, first calculate the syndromes. Taking we have and
Next, apply the Peterson procedure by row-reducing the following augmented matrix.

Due to the zero row, S_3×3 is singular, which is no surprise since only two errors were introduced into the codeword.
However, the upper-left corner of the matrix is identical to [S_2×2 | C_2×1], which gives rise to the solution
The resulting error locator polynomial is which has zeros at and
The exponents of correspond to the error locations.
There is no need to calculate the error values in this example, as the only possible value is 1.

Decoding with unreadable characters[edit]

Suppose the same scenario, but the received word has two unreadable characters [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. We replace the unreadable characters by zeros while creating the polynomial reflecting their positions We compute the syndromes and (Using log notation which is independent on GF(2⁴) isomorphisms. For computation checking we can use the same representation for addition as was used in previous example. Hexadecimal description of the powers of are consecutively 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 with the addition based on bitwise xor.)

Let us make syndrome polynomial

compute

Run the extended Euclidean algorithm:

We have reached polynomial of degree at most 3, and as

we get

Therefore,

Let Don’t worry that Find by brute force a root of The roots are and (after finding for example we can divide by corresponding monom and the root of resulting monom could be found easily).

Let

Let us look for error values using formula

where are roots of We get

Fact, that should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Decoding with unreadable characters with a small number of errors[edit]

Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Again, replace the unreadable characters by zeros while creating the polynomial reflecting their positions
Compute the syndromes and
Create syndrome polynomial

Let us run the extended Euclidean algorithm:

We have reached polynomial of degree at most 3, and as

we get

Therefore,

Let Don’t worry that The root of is

Let

Let us look for error values using formula where are roots of polynomial

We get

The fact that should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Citations[edit]

References[edit]

Primary sources[edit]

• Hocquenghem, A. (September 1959), «Codes correcteurs d’erreurs», Chiffres (in French), Paris, 2: 147–156
• Bose, R. C.; Ray-Chaudhuri, D. K. (March 1960), «On A Class of Error Correcting Binary Group Codes» (PDF), Information and Control, 3 (1): 68–79, doi:10.1016/s0019-9958(60)90287-4, ISSN 0890-5401, archived (PDF) from the original on 2022-10-09

Secondary sources[edit]

• Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, archived (PDF) from the original on 2022-10-09, retrieved April 21, 2010^{[dead link]} Course notes are apparently being redone for 2012: http://www.stanford.edu/class/ee387/ Archived 2013-06-05 at the Wayback Machine
• Gorenstein, Daniel; Peterson, W. Wesley; Zierler, Neal (1960), «Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect», Information and Control, 3 (3): 291–294, doi:10.1016/s0019-9958(60)90877-9
• Lidl, Rudolf; Pilz, Günter (1999), Applied Abstract Algebra (2nd ed.), John Wiley
• Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-8528-4

Further reading[edit]

• Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press, ISBN 0-521-55374-1
• Gilbert, W. J.; Nicholson, W. K. (2004), Modern Algebra with Applications (2nd ed.), John Wiley
• Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall
• MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company
• Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications, University at Buffalo, archived from the original on 2010-07-02, retrieved April 21, 2010

In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called Galois field). BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Chandra Bose and D.K. Ray-Chaudhuri.^[1][2][3] The name Bose–Chaudhuri–Hocquenghem (and the acronym BCH) arises from the initials of the inventors’ surnames (mistakenly, in the case of Ray-Chaudhuri).

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 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,^[4] compact disc players, DVDs, disk drives, USB flash drives, solid-state drives,^[5] quantum-resistant cryptography^[6] and two-dimensional bar codes.

Definition and illustration

Primitive narrow-sense BCH codes

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

Let α be a primitive element of GF(q^m).
For any positive integer i, let m_i(x) be the minimal polynomial with coefficients in GF(q) of αⁱ.
The generator polynomial of the BCH code is defined as the least common multiple g(x) = lcm(m₁(x),…,m_{d − 1}(x)).
It can be seen that g(x) is a polynomial with coefficients in GF(q) and divides xⁿ − 1.
Therefore, the polynomial code defined by g(x) is a cyclic code.

Example

Let q = 2 and m = 4 (therefore n = 15). We will consider different values of d for GF(16) = GF(2⁴) based on the reducing polynomial z⁴ + z + 1, using primitive element α(z) = z. There are fourteen minimum polynomials m_i(x) with coefficients in GF(2) satisfying

[math]displaystyle{ m_ileft(alpha^iright) bmod left(z^4 + z + 1right) = 0. }[/math]

The minimal polynomials are

[math]displaystyle{ begin{align}
m_1(x) &= m_2(x) = m_4(x) = m_8(x) = x^4 + x + 1, \
m_3(x) &= m_6(x) = m_9(x) = m_{12}(x) = x^4 + x^3 + x^2 + x + 1, \
m_5(x) &= m_{10}(x) = x^2 + x + 1, \
m_7(x) &= m_{11}(x) = m_{13}(x) = m_{14}(x) = x^4 + x^3 + 1.
end{align} }[/math]

The BCH code with [math]displaystyle{ d = 2, 3 }[/math] has generator polynomial

[math]displaystyle{ g(x) = {rm lcm}(m_1(x), m_2(x)) = m_1(x) = x^4 + x + 1., }[/math]

It has minimal Hamming distance at least 3 and corrects up to one error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.

The BCH code with [math]displaystyle{ d=4,5 }[/math] has generator polynomial

[math]displaystyle{ begin{align}
g(x) &= {rm lcm}(m_1(x),m_2(x),m_3(x),m_4(x)) = m_1(x) m_3(x) \
&= left(x^4 + x + 1right)left(x^4 + x^3 + x^2 + x + 1right) = x^8 + x^7 + x^6 + x^4 + 1.
end{align} }[/math]

It has minimal Hamming distance at least 5 and corrects up to two errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.

The BCH code with [math]displaystyle{ d=6,7 }[/math] has generator polynomial

[math]displaystyle{ begin{align}
g(x) &= {rm lcm}(m_1(x),m_2(x),m_3(x),m_4(x),m_5(x),m_6(x)) = m_1(x) m_3(x) m_5(x) \
&= left(x^4 + x + 1right)left(x^4 + x^3 + x^2 + x + 1right)left(x^2 + x + 1right) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1.
end{align} }[/math]

It has minimal Hamming distance at least 7 and corrects up to three errors. Since the generator polynomial is of degree 10, this code has 5 data bits and 10 checksum bits. (This particular generator polynomial has a real-world application, in the format patterns of the QR code.)

The BCH code with [math]displaystyle{ d=8 }[/math] and higher has generator polynomial

[math]displaystyle{ begin{align}
g(x) &= {rm lcm}(m_1(x),m_2(x),…,m_{14}(x)) = m_1(x) m_3(x) m_5(x) m_7(x)\
&= left(x^4 + x + 1right)left(x^4 + x^3 + x^2 + x + 1right)left(x^2 + x + 1right)left(x^4 + x^3 + 1right) = x^{14} + x^{13} + x^{12} + cdots + x^2 + x + 1.
end{align} }[/math]

This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.

General BCH codes

General BCH codes differ from primitive narrow-sense BCH codes in two respects.

First, the requirement that [math]displaystyle{ alpha }[/math] be a primitive element of [math]displaystyle{ mathrm{GF}(q^m) }[/math] can be relaxed. By relaxing this requirement, the code length changes from [math]displaystyle{ q^m — 1 }[/math] to [math]displaystyle{ mathrm{ord}(alpha), }[/math] the order of the element [math]displaystyle{ alpha. }[/math]

Second, the consecutive roots of the generator polynomial may run from [math]displaystyle{ alpha^c,ldots,alpha^{c+d-2} }[/math] instead of [math]displaystyle{ alpha,ldots,alpha^{d-1}. }[/math]

Definition. Fix a finite field [math]displaystyle{ GF(q), }[/math] where [math]displaystyle{ q }[/math] is a prime power. Choose positive integers [math]displaystyle{ m,n,d,c }[/math] such that [math]displaystyle{ 2leq dleq n, }[/math] [math]displaystyle{ {rm gcd}(n,q)=1, }[/math] and [math]displaystyle{ m }[/math] is the multiplicative order of [math]displaystyle{ q }[/math] modulo [math]displaystyle{ n. }[/math]

As before, let [math]displaystyle{ alpha }[/math] be a primitive [math]displaystyle{ n }[/math]th root of unity in [math]displaystyle{ GF(q^m), }[/math] and let [math]displaystyle{ m_i(x) }[/math] be the minimal polynomial over [math]displaystyle{ GF(q) }[/math] of [math]displaystyle{ alpha^i }[/math] for all [math]displaystyle{ i. }[/math]
The generator polynomial of the BCH code is defined as the least common multiple [math]displaystyle{ g(x) = {rm lcm}(m_c(x),ldots,m_{c+d-2}(x)). }[/math]

Note: if [math]displaystyle{ n=q^m-1 }[/math] as in the simplified definition, then [math]displaystyle{ {rm gcd}(n,q) }[/math] is 1, and the order of [math]displaystyle{ q }[/math] modulo [math]displaystyle{ n }[/math] is [math]displaystyle{ m. }[/math]
Therefore, the simplified definition is indeed a special case of the general one.

Special cases

• A BCH code with [math]displaystyle{ c=1 }[/math] is called a narrow-sense BCH code.
• A BCH code with [math]displaystyle{ n=q^m-1 }[/math] is called primitive.

The generator polynomial [math]displaystyle{ g(x) }[/math] of a BCH code has coefficients from [math]displaystyle{ mathrm{GF}(q). }[/math]
In general, a cyclic code over [math]displaystyle{ mathrm{GF}(q^p) }[/math] with [math]displaystyle{ g(x) }[/math] as the generator polynomial is called a BCH code over [math]displaystyle{ mathrm{GF}(q^p). }[/math]
The BCH code over [math]displaystyle{ mathrm{GF}(q^m) }[/math] and generator polynomial [math]displaystyle{ g(x) }[/math] with successive powers of [math]displaystyle{ 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]displaystyle{ mathrm{GF}(q^m) }[/math] .^[7] The other type of Reed Solomon code is an original view Reed Solomon code which is not a BCH code.

Properties

The generator polynomial of a BCH code has degree at most [math]displaystyle{ (d-1)m }[/math]. Moreover, if [math]displaystyle{ q=2 }[/math] and [math]displaystyle{ c=1 }[/math], the generator polynomial has degree at most [math]displaystyle{ dm/2 }[/math].

A BCH code has minimal Hamming distance at least [math]displaystyle{ d }[/math].

A BCH code is cyclic.

Encoding

Because any polynomial that is a multiple of the generator polynomial is a valid BCH codeword, BCH encoding is merely the process of finding some polynomial that has the generator as a factor.

The BCH code itself is not prescriptive about the meaning of the coefficients of the polynomial; conceptually, a BCH decoding algorithm’s sole concern is to find the valid codeword with the minimal Hamming distance to the received codeword. Therefore, the BCH code may be implemented either as a systematic code or not, depending on how the implementor chooses to embed the message in the encoded polynomial.

Non-systematic encoding: The message as a factor

The most straightforward way to find a polynomial that is a multiple of the generator is to compute the product of some arbitrary polynomial and the generator. In this case, the arbitrary polynomial can be chosen using the symbols of the message as coefficients.

[math]displaystyle{ s(x) = p(x)g(x) }[/math]

As an example, consider the generator polynomial [math]displaystyle{ g(x)=x^{10}+x^9+x^8+x^6+x^5+x^3+1 }[/math], chosen for use in the (31, 21) binary BCH code used by POCSAG and others. To encode the 21-bit message {101101110111101111101}, we first represent it as a polynomial over [math]displaystyle{ GF(2) }[/math]:

[math]displaystyle{ p(x) = x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^9+x^8+x^6+x^5+x^4+x^3+x^2+1 }[/math]

Then, compute (also over [math]displaystyle{ GF(2) }[/math]):

[math]displaystyle{ begin{align}
s(x) &= p(x)g(x)\
&= left(x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^9+x^8+x^6+x^5+x^4+x^3+x^2+1right)left(x^{10}+x^9+x^8+x^6+x^5+x^3+1right)\
&= x^{30}+x^{29}+x^{26}+x^{25}+x^{24}+x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x^9+x^8+x^6+x^5+x^4+x^2+1
end{align} }[/math]

Thus, the transmitted codeword is {1100111010010111101011101110101}.

The receiver can use these bits as coefficients in [math]displaystyle{ s(x) }[/math] and, after error-correction to ensure a valid codeword, can recompute [math]displaystyle{ p(x) = s(x)/g(x) }[/math]

Systematic encoding: The message as a prefix

A systematic code is one in which the message appears verbatim somewhere within the codeword. Therefore, systematic BCH encoding involves first embedding the message polynomial within the codeword polynomial, and then adjusting the coefficients of the remaining (non-message) terms to ensure that [math]displaystyle{ s(x) }[/math] is divisible by [math]displaystyle{ g(x) }[/math].

This encoding method leverages the fact that subtracting the remainder from a dividend results in a multiple of the divisor. Hence, if we take our message polynomial [math]displaystyle{ p(x) }[/math] as before and multiply it by [math]displaystyle{ x^{n-k} }[/math] (to «shift» the message out of the way of the remainder), we can then use Euclidean division of polynomials to yield:

[math]displaystyle{ p(x)x^{n-k} = q(x)g(x) + r(x) }[/math]

Here, we see that [math]displaystyle{ q(x)g(x) }[/math] is a valid codeword. As [math]displaystyle{ r(x) }[/math] is always of degree less than [math]displaystyle{ n-k }[/math] (which is the degree of [math]displaystyle{ g(x) }[/math]), we can safely subtract it from [math]displaystyle{ p(x)x^{n-k} }[/math] without altering any of the message coefficients, hence we have our [math]displaystyle{ s(x) }[/math] as

[math]displaystyle{ s(x) = q(x)g(x) = p(x)x^{n-k} — r(x) }[/math]

Over [math]displaystyle{ GF(2) }[/math] (i.e. with binary BCH codes), this process is indistinguishable from appending a cyclic redundancy check, and if a systematic binary BCH code is used only for error-detection purposes, we see that BCH codes are just a generalization of the mathematics of cyclic redundancy checks.

The advantage to the systematic coding is that the receiver can recover the original message by discarding everything after the first [math]displaystyle{ k }[/math] coefficients, after performing error correction.

Decoding

There are many algorithms for decoding BCH codes. The most common ones follow this general outline:

1. Calculate the syndromes s_j for the received vector
2. Determine the number of errors t and the error locator polynomial Λ(x) from the syndromes
3. Calculate the roots of the error location polynomial to find the error locations X_i
4. Calculate the error values Y_i at those error locations
5. Correct the errors

During some of these steps, the decoding algorithm may determine that the received vector has too many errors and cannot be corrected. For example, if an appropriate value of t is not found, then the correction would fail. In a truncated (not primitive) code, an error location may be out of range. If the received vector has more errors than the code can correct, the decoder may unknowingly produce an apparently valid message that is not the one that was sent.

Calculate the syndromes

The received vector [math]displaystyle{ R }[/math] is the sum of the correct codeword [math]displaystyle{ C }[/math] and an unknown error vector [math]displaystyle{ E. }[/math] The syndrome values are formed by considering [math]displaystyle{ R }[/math] as a polynomial and evaluating it at [math]displaystyle{ alpha^c, ldots, alpha^{c+d-2}. }[/math] Thus the syndromes are^[8]

[math]displaystyle{ s_j = Rleft(alpha^jright) = Cleft(alpha^jright) + Eleft(alpha^jright) }[/math]

for [math]displaystyle{ j = c }[/math] to [math]displaystyle{ c + d — 2. }[/math]

Since [math]displaystyle{ alpha^{j} }[/math] are the zeros of [math]displaystyle{ g(x), }[/math] of which [math]displaystyle{ C(x) }[/math] is a multiple, [math]displaystyle{ Cleft(alpha^jright) = 0. }[/math] Examining the syndrome values thus isolates the error vector so one can begin to solve for it.

If there is no error, [math]displaystyle{ s_j = 0 }[/math] for all [math]displaystyle{ j. }[/math] If the syndromes are all zero, then the decoding is done.

Calculate the error location polynomial

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]displaystyle{ E(x) = e,x^i, }[/math] where [math]displaystyle{ i }[/math] is the location of the error and [math]displaystyle{ e }[/math] is its magnitude. Then the first two syndromes are

[math]displaystyle{ begin{align}
s_c &= e,alpha^{c,i} \
s_{c+1} &= e,alpha^{(c+1),i} = alpha^i s_c
end{align} }[/math]

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

If there are two or more errors,

[math]displaystyle{ 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]displaystyle{ e_k }[/math] and [math]displaystyle{ i_k. }[/math]

The first step is finding, compatible with computed syndromes and with minimal possible [math]displaystyle{ t, }[/math] locator polynomial:

[math]displaystyle{ Lambda(x) = prod_{j=1}^t left(xalpha^{i_j} — 1right) }[/math]

Three popular algorithms for this task are:

1. Peterson–Gorenstein–Zierler algorithm
2. Berlekamp–Massey algorithm
3. Sugiyama Euclidean algorithm

Peterson–Gorenstein–Zierler algorithm

Peterson’s algorithm is the step 2 of the generalized BCH decoding procedure. Peterson’s algorithm is used to calculate the error locator polynomial coefficients [math]displaystyle{ lambda_1 , lambda_2, dots, lambda_{v} }[/math] of a polynomial

[math]displaystyle{ 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.^[9] Expect we have at least 2t syndromes s_c, …, s_c+2t−1. Let v = t.

Factor error locator polynomial

Now that you have the [math]displaystyle{ Lambda(x) }[/math] polynomial, its roots can be found in the form [math]displaystyle{ Lambda(x) = left(alpha^{i_1} x — 1right)left(alpha^{i_2} x — 1right) cdots left(alpha^{i_v} x — 1right) }[/math] by brute force for example using the Chien search algorithm. The exponential
powers of the primitive element [math]displaystyle{ alpha }[/math] will yield the positions where errors occur in the received word; hence the name ‘error locator’ polynomial.

The zeros of Λ(x) are α^−i₁, …, α^−i_v.

Calculate error values

Once the error locations are known, the next step is to determine the error values at those locations. The error values are then used to correct the received values at those locations to recover the original codeword.

For the case of binary BCH, (with all characters readable) this is trivial; just flip the bits for the received word at these positions, and we have the corrected code word. In the more general case, the error weights [math]displaystyle{ e_j }[/math] can be determined by solving the linear system

[math]displaystyle{ begin{align}
s_c & = e_1 alpha^{c,i_1} + e_2 alpha^{c,i_2} + cdots \
s_{c+1} & = e_1 alpha^{(c + 1),i_1} + e_2 alpha^{(c + 1),i_2} + cdots \
& {} vdots
end{align} }[/math]

Forney algorithm

However, there is a more efficient method known as the Forney algorithm.

Let

[math]displaystyle{ S(x) = s_c + s_{c+1}x + s_{c+2}x^2 + cdots + s_{c+d-2}x^{d-2}. }[/math]

[math]displaystyle{ v leqslant d-1, lambda_0 neq 0 qquad Lambda(x) = sum_{i=0}^vlambda_i x^i = lambda_0 prod_{k=0}^{v} left(alpha^{-i_k}x — 1right). }[/math]

And the error evaluator polynomial^[10]

[math]displaystyle{ Omega(x) equiv S(x) Lambda(x) bmod{x^{d-1}} }[/math]

Finally:

[math]displaystyle{ Lambda'(x) = sum_{i=1}^v i cdot lambda_i x^{i-1}, }[/math]

where

[math]displaystyle{ i cdot x := sum_{k=1}^i x. }[/math]

Than if syndromes could be explained by an error word, which could be nonzero only on positions [math]displaystyle{ i_k }[/math], then error values are

[math]displaystyle{ e_k = -{alpha^{i_k}Omegaleft(alpha^{-i_k}right) over alpha^{ccdot i_k}Lambda’left(alpha^{-i_k}right)}. }[/math]

For narrow-sense BCH codes, c = 1, so the expression simplifies to:

[math]displaystyle{ e_k = -{Omegaleft(alpha^{-i_k}right) over Lambda’left(alpha^{-i_k}right)}. }[/math]

Explanation of Forney algorithm computation

It is based on Lagrange interpolation and techniques of generating functions.

Consider [math]displaystyle{ S(x)Lambda(x), }[/math] and for the sake of simplicity suppose [math]displaystyle{ lambda_k = 0 }[/math] for [math]displaystyle{ k gt v, }[/math] and [math]displaystyle{ s_k = 0 }[/math] for [math]displaystyle{ k gt c + d — 2. }[/math] Then

[math]displaystyle{ S(x)Lambda(x) = sum_{j=0}^{infty}sum_{i=0}^j s_{j-i+1}lambda_i x^j. }[/math]

[math]displaystyle{ begin{align}
S(x)Lambda(x)
&= S(x) left { lambda_0prod_{ell=1}^v left (alpha^{i_ell}x-1 right ) right } \
&= left { sum_{i=0}^{d-2}sum_{j=1}^v e_jalpha^{(c+i)cdot i_j} x^i right } left { lambda_0prod_{ell=1}^v left (alpha^{i_ell}x-1 right ) right } \
&= left { sum_{j=1}^v e_j alpha^{c i_j}sum_{i=0}^{d-2} left (alpha^{i_j} right )^i x^i right } left { lambda_0prod_{ell=1}^v left (alpha^{i_ell}x-1 right ) right } \
&= left { sum_{j=1}^v e_j alpha^{c i_j} frac{left (x alpha^{i_j} right )^{d-1}-1}{x alpha^{i_j}-1} right } left { lambda_0 prod_{ell=1}^v left (alpha^{i_ell}x-1 right ) right } \
&= lambda_0 sum_{j=1}^v e_jalpha^{c i_j} frac{ left (xalpha^{i_j} right)^{d-1}-1}{xalpha^{i_j}-1} prod_{ell=1}^v left (alpha^{i_ell}x-1 right ) \
&= lambda_0 sum_{j=1}^v e_jalpha^{c i_j} left ( left (xalpha^{i_j} right)^{d-1}-1 right ) prod_{ellin{1,cdots,v}setminus{j}} left (alpha^{i_ell}x-1 right )
end{align} }[/math]

We want to compute unknowns [math]displaystyle{ e_j, }[/math] and we could simplify the context by removing the [math]displaystyle{ left(xalpha^{i_j}right)^{d-1} }[/math] terms. This leads to the error evaluator polynomial

[math]displaystyle{ Omega(x) equiv S(x) Lambda(x) bmod{x^{d-1}}. }[/math]

Thanks to [math]displaystyle{ vleqslant d-1 }[/math] we have

[math]displaystyle{ Omega(x) = -lambda_0sum_{j=1}^v e_jalpha^{c i_j} prod_{ellin{1,cdots,v}setminus{j}} left(alpha^{i_ell}x — 1right). }[/math]

Thanks to [math]displaystyle{ Lambda }[/math] (the Lagrange interpolation trick) the sum degenerates to only one summand for [math]displaystyle{ x = alpha^{-i_k} }[/math]

[math]displaystyle{ Omega left(alpha^{-i_k}right) = -lambda_0 e_kalpha^{ccdot i_k}prod_{ellin{1,cdots,v}setminus{k}} left(alpha^{i_ell}alpha^{-i_k} — 1right). }[/math]

To get [math]displaystyle{ e_k }[/math] we just should get rid of the product. We could compute the product directly from already computed roots [math]displaystyle{ alpha^{-i_j} }[/math] of [math]displaystyle{ Lambda, }[/math] but we could use simpler form.

As formal derivative

[math]displaystyle{ Lambda'(x) = lambda_0sum_{j=1}^v alpha^{i_j}prod_{ellin{1,cdots,v}setminus{j}} left(alpha^{i_ell}x — 1right), }[/math]

we get again only one summand in

[math]displaystyle{ Lambda’left(alpha^{-i_k}right) = lambda_0alpha^{i_k}prod_{ellin{1,cdots,v}setminus{k}} left(alpha^{i_ell}alpha^{-i_k} — 1right). }[/math]

So finally

[math]displaystyle{ e_k = -frac{alpha^{i_k}Omega left(alpha^{-i_k}right)}{alpha^{ccdot i_k}Lambda’ left(alpha^{-i_k}right)}. }[/math]

This formula is advantageous when one computes the formal derivative of [math]displaystyle{ Lambda }[/math] form

[math]displaystyle{ Lambda(x) = sum_{i=1}^v lambda_i x^i }[/math]

yielding:

[math]displaystyle{ Lambda'(x) = sum_{i=1}^v i cdot lambda_i x^{i-1}, }[/math]

where

[math]displaystyle{ icdot x := sum_{k=1}^i x. }[/math]

Decoding based on extended Euclidean algorithm

An alternate process of finding both the polynomial Λ and the error locator polynomial is based on Yasuo Sugiyama’s adaptation of the Extended Euclidean algorithm.^[11] Correction of unreadable characters could be incorporated to the algorithm easily as well.

Let [math]displaystyle{ k_1, …, k_k }[/math] be positions of unreadable characters. One creates polynomial localising these positions [math]displaystyle{ Gamma(x) = prod_{i=1}^kleft(xalpha^{k_i} — 1right). }[/math]
Set values on unreadable positions to 0 and compute the syndromes.

As we have already defined for the Forney formula let [math]displaystyle{ S(x)=sum_{i=0}^{d-2}s_{c+i}x^i. }[/math]

Let us run extended Euclidean algorithm for locating least common divisor of polynomials [math]displaystyle{ S(x)Gamma(x) }[/math] and [math]displaystyle{ x^{d-1}. }[/math]
The goal is not to find the least common divisor, but a polynomial [math]displaystyle{ r(x) }[/math] of degree at most [math]displaystyle{ lfloor (d+k-3)/2rfloor }[/math] and polynomials [math]displaystyle{ a(x), b(x) }[/math] such that [math]displaystyle{ r(x)=a(x)S(x)Gamma(x)+b(x)x^{d-1}. }[/math]
Low degree of [math]displaystyle{ r(x) }[/math] guarantees, that [math]displaystyle{ a(x) }[/math] would satisfy extended (by [math]displaystyle{ Gamma }[/math]) defining conditions for [math]displaystyle{ Lambda. }[/math]

Defining [math]displaystyle{ Xi(x)=a(x)Gamma(x) }[/math] and using [math]displaystyle{ Xi }[/math] on the place of [math]displaystyle{ Lambda(x) }[/math] in the Fourney formula will give us error values.

The main advantage of the algorithm is that it meanwhile computes [math]displaystyle{ Omega(x)=S(x)Xi(x)bmod x^{d-1}=r(x) }[/math] required in the Forney formula.

Explanation of the decoding process

The goal is to find a codeword which differs from the received word minimally as possible on readable positions. When expressing the received word as a sum of nearest codeword and error word, we are trying to find error word with minimal number of non-zeros on readable positions. Syndrom [math]displaystyle{ s_i }[/math] restricts error word by condition

[math]displaystyle{ s_i=sum_{j=0}^{n-1}e_jalpha^{ij}. }[/math]

We could write these conditions separately or we could create polynomial

[math]displaystyle{ S(x)=sum_{i=0}^{d-2}s_{c+i}x^i }[/math]

and compare coefficients near powers [math]displaystyle{ 0 }[/math] to [math]displaystyle{ d-2. }[/math]

[math]displaystyle{ S(x) stackrel{{0,cdots,,d-2}}{=} E(x)=sum_{i=0}^{d-2}sum_{j=0}^{n-1}e_jalpha^{ij}alpha^{cj}x^i. }[/math]

Suppose there is unreadable letter on position [math]displaystyle{ k_1, }[/math] we could replace set of syndromes [math]displaystyle{ {s_c,cdots,s_{c+d-2}} }[/math] by set of syndromes [math]displaystyle{ {t_c,cdots,t_{c+d-3}} }[/math] defined by equation [math]displaystyle{ t_i=alpha^{k_1}s_i-s_{i+1}. }[/math] Suppose for an error word all restrictions by original set [math]displaystyle{ {s_c,cdots,s_{c+d-2}} }[/math] of syndromes hold,
than

[math]displaystyle{ t_i=alpha^{k_1}s_i-s_{i+1}=alpha^{k_1}sum_{j=0}^{n-1}e_jalpha^{ij}-sum_{j=0}^{n-1}e_jalpha^jalpha^{ij}=sum_{j=0}^{n-1}e_jleft(alpha^{k_1} — alpha^jright)alpha^{ij}. }[/math]

New set of syndromes restricts error vector

[math]displaystyle{ f_j=e_jleft(alpha^{k_1} — alpha^jright) }[/math]

the same way the original set of syndromes restricted the error vector [math]displaystyle{ e_j. }[/math] Except the coordinate [math]displaystyle{ k_1, }[/math] where we have [math]displaystyle{ f_{k_1}=0, }[/math] an [math]displaystyle{ f_j }[/math] is zero, if [math]displaystyle{ e_j = 0. }[/math] For the goal of locating error positions we could change the set of syndromes in the similar way to reflect all unreadable characters. This shortens the set of syndromes by [math]displaystyle{ k. }[/math]

In polynomial formulation, the replacement of syndromes set [math]displaystyle{ {s_c,cdots,s_{c+d-2}} }[/math] by syndromes set [math]displaystyle{ {t_c,cdots,t_{c+d-3}} }[/math] leads to

[math]displaystyle{ T(x) = sum_{i=0}^{d-3}t_{c+i}x^i=alpha^{k_1}sum_{i=0}^{d-3}s_{c+i}x^i-sum_{i=1}^{d-2}s_{c+i}x^{i-1}. }[/math]

Therefore,

[math]displaystyle{ xT(x) stackrel{{1,cdots,,d-2}}{=} left(xalpha^{k_1} — 1right)S(x). }[/math]

After replacement of [math]displaystyle{ S(x) }[/math] by [math]displaystyle{ S(x)Gamma(x) }[/math], one would require equation for coefficients near powers [math]displaystyle{ k,cdots,d-2. }[/math]

One could consider looking for error positions from the point of view of eliminating influence of given positions similarly as for unreadable characters. If we found [math]displaystyle{ v }[/math] positions such that eliminating their influence leads to obtaining set of syndromes consisting of all zeros, than there exists error vector with errors only on these coordinates.
If [math]displaystyle{ Lambda(x) }[/math] denotes the polynomial eliminating the influence of these coordinates, we obtain

[math]displaystyle{ S(x)Gamma(x)Lambda(x) stackrel{{k+v, cdots, d-2}}{=} 0. }[/math]

In Euclidean algorithm, we try to correct at most [math]displaystyle{ tfrac{1}{2}(d-1-k) }[/math] errors (on readable positions), because with bigger error count there could be more codewords in the same distance from the received word. Therefore, for [math]displaystyle{ Lambda(x) }[/math] we are looking for, the equation must hold for coefficients near powers starting from

[math]displaystyle{ k + leftlfloor frac{1}{2} (d-1-k) rightrfloor. }[/math]

In Forney formula, [math]displaystyle{ Lambda(x) }[/math] could be multiplied by a scalar giving the same result.

It could happen that the Euclidean algorithm finds [math]displaystyle{ Lambda(x) }[/math] of degree higher than [math]displaystyle{ tfrac{1}{2}(d-1-k) }[/math] having number of different roots equal to its degree, where the Fourney formula would be able to correct errors in all its roots, anyway correcting such many errors could be risky (especially with no other restrictions on received word). Usually after getting [math]displaystyle{ Lambda(x) }[/math] of higher degree, we decide not to correct the errors. Correction could fail in the case [math]displaystyle{ Lambda(x) }[/math] has roots with higher multiplicity or the number of roots is smaller than its degree. Fail could be detected as well by Forney formula returning error outside the transmitted alphabet.

Correct the errors

Using the error values and error location, correct the errors and form a corrected code vector by subtracting error values at error locations.

Decoding examples

Decoding of binary code without unreadable characters

Consider a BCH code in GF(2⁴) with [math]displaystyle{ d=7 }[/math] and [math]displaystyle{ g(x) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1 }[/math]. (This is used in QR codes.) Let the message to be transmitted be [1 1 0 1 1], or in polynomial notation, [math]displaystyle{ M(x) = x^4 + x^3 + x + 1. }[/math]
The «checksum» symbols are calculated by dividing [math]displaystyle{ x^{10} M(x) }[/math] by [math]displaystyle{ g(x) }[/math] and taking the remainder, resulting in [math]displaystyle{ x^9 + x^4 + x^2 }[/math] or [ 1 0 0 0 0 1 0 1 0 0 ]. These are appended to the message, so the transmitted codeword is [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ].

Now, imagine that there are two bit-errors in the transmission, so the received codeword is [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. In polynomial notation:

[math]displaystyle{ R(x) = C(x) + x^{13} + x^5 = x^{14} + x^{11} + x^{10} + x^9 + x^5 + x^4 + x^2 }[/math]

In order to correct the errors, first calculate the syndromes. Taking [math]displaystyle{ alpha = 0010, }[/math] we have [math]displaystyle{ s_1 = R(alpha^1) = 1011, }[/math] [math]displaystyle{ s_2 = 1001, }[/math] [math]displaystyle{ s_3 = 1011, }[/math] [math]displaystyle{ s_4 = 1101, }[/math] [math]displaystyle{ s_5 = 0001, }[/math] and [math]displaystyle{ s_6 = 1001. }[/math]
Next, apply the Peterson procedure by row-reducing the following augmented matrix.

[math]displaystyle{ left [ S_{3 times 3} | C_{3 times 1} right ] =
begin{bmatrix}s_1&s_2&s_3&s_4\
s_2&s_3&s_4&s_5\
s_3&s_4&s_5&s_6end{bmatrix} =
begin{bmatrix}1011&1001&1011&1101\
1001&1011&1101&0001\
1011&1101&0001&1001end{bmatrix} Rightarrow
begin{bmatrix}0001&0000&1000&0111\
0000&0001&1011&0001\
0000&0000&0000&0000
end{bmatrix} }[/math]

Due to the zero row, S_3×3 is singular, which is no surprise since only two errors were introduced into the codeword.
However, the upper-left corner of the matrix is identical to [S_2×2 | C_2×1], which gives rise to the solution [math]displaystyle{ lambda_2 = 1000, }[/math] [math]displaystyle{ lambda_1 = 1011. }[/math]
The resulting error locator polynomial is [math]displaystyle{ Lambda(x) = 1000 x^2 + 1011 x + 0001, }[/math] which has zeros at [math]displaystyle{ 0100 = alpha^{-13} }[/math] and [math]displaystyle{ 0111 = alpha^{-5}. }[/math]
The exponents of [math]displaystyle{ alpha }[/math] correspond to the error locations.
There is no need to calculate the error values in this example, as the only possible value is 1.

Decoding with unreadable characters

Suppose the same scenario, but the received word has two unreadable characters [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. We replace the unreadable characters by zeros while creating the polynomial reflecting their positions [math]displaystyle{ Gamma(x) = left(alpha^8x — 1right)left(alpha^{11}x — 1right). }[/math] We compute the syndromes [math]displaystyle{ s_1=alpha^{-7}, s_2=alpha^{1}, s_3=alpha^{4}, s_4=alpha^{2}, s_5=alpha^{5}, }[/math] and [math]displaystyle{ s_6=alpha^{-7}. }[/math] (Using log notation which is independent on GF(2⁴) isomorphisms. For computation checking we can use the same representation for addition as was used in previous example. Hexadecimal description of the powers of [math]displaystyle{ alpha }[/math] are consecutively 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 with the addition based on bitwise xor.)

Let us make syndrome polynomial

[math]displaystyle{ S(x)=alpha^{-7}+alpha^{1}x+alpha^{4}x^2+alpha^{2}x^3+alpha^{5}x^4+alpha^{-7}x^5, }[/math]

compute

[math]displaystyle{ S(x)Gamma(x)=alpha^{-7}+alpha^{4}x+alpha^{-1}x^2+alpha^{6}x^3+alpha^{-1}x^4+alpha^{5}x^5+alpha^{7}x^6+alpha^{-3}x^7. }[/math]

Run the extended Euclidean algorithm:

[math]displaystyle{ begin{align}
&begin{pmatrix}S(x)Gamma(x)\ x^6end{pmatrix} \ [6pt]
={} &begin{pmatrix}alpha^{-7} +alpha^{4}x+ alpha^{-1}x^2+ alpha^{6}x^3+ alpha^{-1}x^4+ alpha^{5}x^5 +alpha^{7}x^6+ alpha^{-3}x^7 \ x^6end{pmatrix} \ [6pt]
={} &begin{pmatrix}alpha^{7}+ alpha^{-3}x & 1\ 1 & 0end{pmatrix}
begin{pmatrix}x^6\ alpha^{-7} +alpha^{4}x +alpha^{-1}x^2 +alpha^{6}x^3 +alpha^{-1}x^4 +alpha^{5}x^5 +2alpha^{7}x^6 +2alpha^{-3}x^7end{pmatrix} \ [6pt]
={} &begin{pmatrix}alpha^{7}+ alpha^{-3}x & 1\ 1 & 0end{pmatrix}
begin{pmatrix}alpha^4 + alpha^{-5}x & 1\ 1 & 0end{pmatrix} \
&qquad begin{pmatrix}alpha^{-7}+ alpha^{4}x+ alpha^{-1}x^2+ alpha^{6}x^3+ alpha^{-1}x^4+ alpha^{5}x^5\ alpha^{-3} +left(alpha^{-7}+ alpha^{3}right)x+ left(alpha^{3}+ alpha^{-1}right)x^2+ left(alpha^{-5}+ alpha^{-6}right)x^3+ left(alpha^3+ alpha^{1}right)x^4+ 2alpha^{-6}x^5+ 2x^6end{pmatrix} \ [6pt]
={} &begin{pmatrix}left(1+ alpha^{-4}right)+ left(alpha^{1}+ alpha^{2}right)x+ alpha^{7}x^2 & alpha^{7}+ alpha^{-3}x \ alpha^4+ alpha^{-5}x & 1end{pmatrix}
begin{pmatrix}alpha^{-7}+ alpha^{4}x+ alpha^{-1}x^2+ alpha^{6}x^3+ alpha^{-1}x^4+ alpha^{5}x^5\ alpha^{-3}+ alpha^{-2}x+ alpha^{0}x^2+ alpha^{-2}x^3+ alpha^{-6}x^4end{pmatrix} \ [6pt]
={} &begin{pmatrix}alpha^{-3}+ alpha^{5}x+ alpha^{7}x^2 & alpha^{7}+ alpha^{-3}x \ alpha^4+ alpha^{-5}x & 1end{pmatrix}
begin{pmatrix}alpha^{-5}+ alpha^{-4}x & 1\ 1 & 0 end{pmatrix} \
&qquad begin{pmatrix}alpha^{-3}+ alpha^{-2}x+ alpha^{0}x^2+ alpha^{-2}x^3+ alpha^{-6}x^4\ left(alpha^{7}+ alpha^{-7}right)+ left(2alpha^{-7}+ alpha^{4}right)x+ left(alpha^{-5}+ alpha^{-6}+ alpha^{-1}right)x^2+ left(alpha^{-7}+ alpha^{-4}+ alpha^{6}right)x^3+ left(alpha^{4}+ alpha^{-6}+ alpha^{-1}right)x^4+ 2alpha^{5}x^5end{pmatrix} \ [6pt]
={} &begin{pmatrix}alpha^{7}x+ alpha^{5}x^2+ alpha^{3}x^3 & alpha^{-3}+ alpha^{5}x+ alpha^{7}x^2\ alpha^{3}+ alpha^{-5}x+ alpha^{6}x^2 & alpha^4+ alpha^{-5}xend{pmatrix}
begin{pmatrix}alpha^{-3}+ alpha^{-2}x+ alpha^{0}x^2+ alpha^{-2}x^3+ alpha^{-6}x^4\ alpha^{-4}+ alpha^{4}x+ alpha^{2}x^2+ alpha^{-5}x^3end{pmatrix}.
end{align} }[/math]

We have reached polynomial of degree at most 3, and as

[math]displaystyle{ begin{pmatrix}-left(alpha^4+ alpha^{-5}xright) & alpha^{-3}+ alpha^{5}x+ alpha^{7}x^2\ alpha^{3}+ alpha^{-5}x+ alpha^{6}x^2 & -left(alpha^{7}x+ alpha^{5}x^2+ alpha^{3}x^3right)end{pmatrix} begin{pmatrix}alpha^{7}x+ alpha^{5}x^2+ alpha^{3}x^3 & alpha^{-3} + alpha^{5}x + alpha^{7}x^2\ alpha^{3} + alpha^{-5}x + alpha^{6}x^2 & alpha^4 + alpha^{-5}xend{pmatrix} = begin{pmatrix}1 & 0\ 0 & 1end{pmatrix}, }[/math]

we get

[math]displaystyle{ begin{pmatrix}-left(alpha^4+ alpha^{-5}xright) & alpha^{-3}+ alpha^{5}x+ alpha^{7}x^2\ alpha^{3}+ alpha^{-5}x+ alpha^{6}x^2 & -left(alpha^{7}x+ alpha^{5}x^2+ alpha^{3}x^3right)end{pmatrix}
begin{pmatrix}S(x)Gamma(x)\ x^6end{pmatrix} = begin{pmatrix}alpha^{-3}+ alpha^{-2}x+ alpha^{0}x^2+ alpha^{-2}x^3+ alpha^{-6}x^4\ alpha^{-4}+ alpha^{4}x+ alpha^{2}x^2+ alpha^{-5}x^3end{pmatrix}. }[/math]

Therefore,

[math]displaystyle{ S(x)Gamma(x)left(alpha^{3} + alpha^{-5}x + alpha^{6}x^2right) — left(alpha^{7}x + alpha^{5}x^2 + alpha^{3}x^3right)x^6 = alpha^{-4} + alpha^{4}x + alpha^{2}x^2 + alpha^{-5}x^3. }[/math]

Let [math]displaystyle{ Lambda(x) = alpha^{3}+ alpha^{-5}x+ alpha^{6}x^2. }[/math] Don’t worry that [math]displaystyle{ lambda_0neq 1. }[/math] Find by brute force a root of [math]displaystyle{ Lambda. }[/math] The roots are [math]displaystyle{ alpha^2, }[/math] and [math]displaystyle{ alpha^{10} }[/math] (after finding for example [math]displaystyle{ alpha^2 }[/math] we can divide [math]displaystyle{ Lambda }[/math] by corresponding monom [math]displaystyle{ left(x — alpha^2right) }[/math] and the root of resulting monom could be found easily).

Let

[math]displaystyle{ begin{align}
Xi(x) &= Gamma(x)Lambda(x) = alpha^3 + alpha^4x^2 + alpha^2x^3 + alpha^{-5}x^4 \
Omega(x) &= S(x)Xi(x) equiv alpha^{-4} + alpha^4x + alpha^2x^2 + alpha^{-5}x^3 bmod{x^6}
end{align} }[/math]

Let us look for error values using formula

[math]displaystyle{ e_j = -frac{Omega left(alpha^{-i_j} right)}{Xi’ left(alpha^{-i_j} right)}, }[/math]

where [math]displaystyle{ alpha^{-i_j} }[/math] are roots of [math]displaystyle{ Xi(x). }[/math] [math]displaystyle{ Xi'(x)=alpha^{2}x^2. }[/math] We get

[math]displaystyle{ begin{align}
e_1 &=-frac{Omega(alpha^4)}{Xi'(alpha^{4})} = frac{alpha^{-4}+alpha^{-7}+alpha^{-5}+alpha^{7}}{alpha^{-5}} =frac{alpha^{-5}}{alpha^{-5}}=1 \
e_2 &=-frac{Omega(alpha^7)}{Xi'(alpha^{7})} = frac{alpha^{-4}+alpha^{-4}+alpha^{1}+alpha^{1}}{alpha^{1}}=0 \
e_3 &=-frac{Omega(alpha^{10})}{Xi'(alpha^{10})} = frac{alpha^{-4}+alpha^{-1}+alpha^{7}+alpha^{-5}}{alpha^{7}}=frac{alpha^{7}}{alpha^{7}}=1 \
e_4 &=-frac{Omega(alpha^{2})}{Xi'(alpha^{2})} = frac{alpha^{-4}+alpha^{6}+alpha^{6}+alpha^{1}}{alpha^{6}}=frac{alpha^{6}}{alpha^{6}}=1
end{align} }[/math]

Fact, that [math]displaystyle{ e_3=e_4=1, }[/math] should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Decoding with unreadable characters with a small number of errors

Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Again, replace the unreadable characters by zeros while creating the polynomial reflecting their positions [math]displaystyle{ Gamma(x) = left(alpha^{8}x — 1right)left(alpha^{11}x — 1right). }[/math]
Compute the syndromes [math]displaystyle{ s_1 = alpha^{4}, s_2 = alpha^{-7}, s_3 = alpha^{1}, s_4 = alpha^{1}, s_5 = alpha^{0}, }[/math] and [math]displaystyle{ s_6 = alpha^{2}. }[/math]
Create syndrome polynomial

[math]displaystyle{ begin{align}
S(x) &= alpha^{4} + alpha^{-7}x + alpha^{1}x^2 + alpha^{1}x^3 + alpha^{0}x^4 + alpha^{2}x^5, \
S(x)Gamma(x) &= alpha^{4} + alpha^{7}x + alpha^{5}x^2 + alpha^{3}x^3 + alpha^{1}x^4 + alpha^{-1}x^5 + alpha^{-1}x^6 + alpha^{6}x^7.
end{align} }[/math]

Let us run the extended Euclidean algorithm:

[math]displaystyle{ begin{align}
begin{pmatrix}
S(x)Gamma(x) \
x^6
end{pmatrix}
&= begin{pmatrix}
alpha^{4} + alpha^{7}x + alpha^{5}x^2 + alpha^{3}x^3 + alpha^{1}x^4 + alpha^{-1}x^5 + alpha^{-1}x^6 + alpha^{6}x^7 \
x^6
end{pmatrix} \
&= begin{pmatrix}
alpha^{-1} + alpha^{6}x & 1 \
1 & 0
end{pmatrix} begin{pmatrix}
x^6 \
alpha^{4} + alpha^{7}x + alpha^{5}x^2 + alpha^{3}x^3 + alpha^{1}x^4 + alpha^{-1}x^5 + 2alpha^{-1}x^6 + 2alpha^{6}x^7
end{pmatrix} \
&= begin{pmatrix}
alpha^{-1} + alpha^{6}x & 1 \
1 & 0
end{pmatrix} begin{pmatrix}
alpha^{3} + alpha^{1}x & 1 \
1 & 0
end{pmatrix} begin{pmatrix}
alpha^{4} + alpha^{7}x + alpha^{5}x^2 + alpha^{3}x^3 + alpha^{1}x^4 + alpha^{-1}x^5 \
alpha^{7} + left(alpha^{-5} + alpha^{5}right)x + 2alpha^{-7}x^2 + 2alpha^{6}x^3 + 2alpha^{4}x^4 + 2alpha^{2}x^5 + 2x^6
end{pmatrix} \
&= begin{pmatrix}
left(1 + alpha^{2}right) + left(alpha^{0} + alpha^{-6}right)x + alpha^{7}x^2 & alpha^{-1} + alpha^{6}x \
alpha^{3} + alpha^{1}x & 1
end{pmatrix} begin{pmatrix}
alpha^{4} + alpha^{7}x + alpha^{5}x^2 + alpha^{3}x^3 + alpha^{1}x^4 + alpha^{-1}x^5 \
alpha^{7} + alpha^{0}x
end{pmatrix}
end{align} }[/math]

We have reached polynomial of degree at most 3, and as

[math]displaystyle{
begin{pmatrix}
-1 & alpha^{-1} + alpha^{6}x \
alpha^{3} + alpha^{1}x & -left(alpha^{-7} + alpha^{7}x + alpha^{7}x^2right)
end{pmatrix} begin{pmatrix}
alpha^{-7} + alpha^{7}x + alpha^{7}x^2 & alpha^{-1} + alpha^{6}x \
alpha^{3} + alpha^{1}x & 1
end{pmatrix} = begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix},
}[/math]

we get

[math]displaystyle{
begin{pmatrix}
-1 & alpha^{-1} + alpha^{6}x \
alpha^{3} + alpha^{1}x & -left(alpha^{-7} + alpha^{7}x + alpha^{7}x^2right)
end{pmatrix}begin{pmatrix}
S(x)Gamma(x) \ x^6
end{pmatrix} = begin{pmatrix}
alpha^{4} + alpha^{7}x + alpha^{5}x^2 + alpha^{3}x^3 + alpha^{1}x^4 + alpha^{-1}x^5 \
alpha^{7} + alpha^{0}x
end{pmatrix}.
}[/math]

Therefore,

[math]displaystyle{ S(x)Gamma(x)left(alpha^{3} + alpha^{1}xright) — left(alpha^{-7} + alpha^{7}x + alpha^{7}x^2right)x^6 = alpha^{7} + alpha^{0}x. }[/math]

Let [math]displaystyle{ Lambda(x) = alpha^{3} + alpha^{1}x. }[/math] Don’t worry that [math]displaystyle{ lambda_0 neq 1. }[/math] The root of [math]displaystyle{ Lambda(x) }[/math] is [math]displaystyle{ alpha^{3-1}. }[/math]

Let

[math]displaystyle{ begin{align}
Xi(x) &= Gamma(x)Lambda(x) = alpha^{3} + alpha^{-7}x + alpha^{-4}x^2 + alpha^{5}x^3, \
Omega(x) &= S(x)Xi(x) equiv alpha^{7} + alpha^{0}x bmod{x^6}
end{align} }[/math]

Let us look for error values using formula [math]displaystyle{ e_j = -Omegaleft(alpha^{-i_j}right)/Xi’left(alpha^{-i_j}right), }[/math] where [math]displaystyle{ alpha^{-i_j} }[/math] are roots of polynomial [math]displaystyle{ Xi(x). }[/math]

[math]displaystyle{ Xi'(x) = alpha^{-7} + alpha^{5}x^2. }[/math]

We get

[math]displaystyle{ begin{align}
e_1 &= -frac{Omegaleft(alpha^4right)}{Xi’left(alpha^{4}right)}
= frac{alpha^{7} + alpha^{4}}{alpha^{-7} + alpha^{-2}}
= frac{alpha^{3}}{alpha^{3}}
= 1 \
e_2 &= -frac{Omegaleft(alpha^7right)}{Xi’left(alpha^{7}right)}
= frac{alpha^{7} + alpha^{7}}{alpha^{-7} + alpha^{4}}
= 0 \
e_3 &= -frac{Omegaleft(alpha^2right)}{Xi’left(alpha^2right)}
= frac{alpha^{7} + alpha^{2}}{alpha^{-7} + alpha^{-6}}
= frac{alpha^{-3}}{alpha^{-3}}
= 1
end{align} }[/math]

The fact that [math]displaystyle{ e_3 = 1 }[/math] should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Citations

References

Primary sources

• Hocquenghem, A. (September 1959), «Codes correcteurs d’erreurs» (in fr), Chiffres (Paris) 2: 147–156
• Bose, R. C.; Ray-Chaudhuri, D. K. (March 1960), «On A Class of Error Correcting Binary Group Codes», Information and Control 3 (1): 68–79, doi:10.1016/s0019-9958(60)90287-4, ISSN 0890-5401, http://repository.lib.ncsu.edu/bitstream/1840.4/2137/1/ISMS_1959_240.pdf

Secondary sources

• Gorenstein, Daniel; Peterson, W. Wesley; Zierler, Neal (1960), «Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect», Information and Control 3 (3): 291–294, doi:10.1016/s0019-9958(60)90877-9
• Lidl, Rudolf; Pilz, Günter (1999), Applied Abstract Algebra (2nd ed.), John Wiley
• Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-8528-4

Further reading

• Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press, ISBN 0-521-55374-1
• Gilbert, W. J.; Nicholson, W. K. (2004), Modern Algebra with Applications (2nd ed.), John Wiley
• Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall
• MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company
• Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications, University at Buffalo, http://www.cse.buffalo.edu/~atri/courses/coding-theory/, retrieved April 21, 2010

В теории кодирования используются коды BCH или Bose – Chaudhuri– Коды Хоквенгема образуют класс циклических кодов с исправлением ошибок, которые построены с использованием полиномов над конечным полем (также называемым Поле Галуа ). Коды BCH были изобретены в 1959 году французским математиком Алексисом Хоквенгемом и независимо в 1960 году Раджем Бозом и Д. К. Рэй-Чаудхури. Название Bose – Chaudhuri – Hocquenghem (и аббревиатура BCH) происходит от инициалов фамилий изобретателей (ошибочно в случае Ray-Chaudhuri).

Одной из ключевых особенностей кодов BCH является то, что во время разработки кода существует точный контроль над количеством ошибок символов, исправляемых кодом. В частности, можно разработать двоичные коды BCH, которые могут исправлять несколько битовых ошибок. Другим преимуществом кодов BCH является легкость, с которой они могут быть декодированы, а именно с помощью алгебраического метода, известного как синдромное декодирование. Это упрощает конструкцию декодера для этих кодов с использованием небольшого маломощного электронного оборудования.

коды BCH используются в таких приложениях, как спутниковая связь, проигрыватели компакт-дисков, DVD, дисководы, твердотельные приводы, квантово-стойкая криптография и двумерные штрих-коды.

Содержание

• 1 Определение и иллюстрация
  • 1.1 Примитивные узкосмысловые коды BCH
    • 1.1. 1 Пример
  • 1.2 Общие коды BCH
  • 1.3 Особые случаи
• 2 Свойства
• 3 Кодирование
  • 3.1 Несистематическое кодирование: сообщение как фактор
  • 3.2 Систематическое кодирование: сообщение как префикс
• 4 Декодирование
  • 4.1 Вычисление синдромов
  • 4.2 Вычисление полинома местоположения ошибки
    • 4.2.1 Алгоритм Петерсона – Горенштейна – Цирлера
  • 4.3 Фактор полинома локатора ошибок
  • 4.4 Вычисление значений ошибок
    • 4.4.1 Алгоритм Форни
    • 4.4.2 Объяснение вычисления алгоритма Форни
  • 4.5 Декодирование на основе расширенного алгоритма Евклида
    • 4.5.1 Объяснение процесса декодирования
  • 4.6 Исправление ошибок
  • 4.7 Примеры расшифровки
    • 4.7.1 Декодирование двоичного кода без нечитаемых символов
    • 4.7.2 Декодирование с нечитаемыми символами
    • 4.7.3 Декодирование с нечитаемыми символами с небольшим количеством ошибок
• 5 Цитаты
• 6 Ссылки
  • 6.1 Первичные источники
  • 6.2 Вторичные источники
• 7 Дополнительная литература

Определение и иллюстрация

Примитивные узкосмысловые коды BCH

Дано простое число q и степень простого числа q с положительными целыми числами m и d такими, что d ≤ q — 1, примитивный узкосмысловой код BCH над конечным полем (или полем Галуа) GF (q) с длиной кода n = q — 1 и расстоянием не менее d строится следующим методом.

Пусть α будет примитивным элементом GF (q). Для любого натурального числа i пусть m i (x) будет минимальным многочленом с коэффициентами в GF (q) при α. Генераторный полином кода BCH определяется как наименьшее общее кратное g (x) = lcm (m 1 (x),…, m d — 1 (x)). Можно видеть, что g (x) — многочлен с коэффициентами из GF (q) и делит x — 1. Следовательно, полиномиальный код, определяемый g (x), является циклическим кодом.

Пример

Пусть q = 2 и m = 4 (следовательно, n = 15). Мы рассмотрим разные значения d. Для GF (16) = GF (2) на основе многочлена x + x + 1 с первообразным корнем α = x + 0 существуют минимальные многочлены m i (x) с коэффициентами в GF (2), удовлетворяющие

mi (α i) mod (x 4 + x + 1) = 0. { displaystyle m_ {i} left ( alpha ^ {i} right) { bmod { left (x ^ {4 } + x + 1 right)}} = 0.}

Минимальные многочлены четырнадцати степеней α равны

m 1 (x) = m 2 (x) = m 4 (x) = m 8 (х) = х 4 + х + 1, м 3 (х) = м 6 (х) = м 9 (х) = м 12 (х) = х 4 + х 3 + х 2 + х + 1, м 5 (x) = m 10 (x) = x 2 + x + 1, m 7 (x) = m 11 (x) = m 13 (x) = m 14 (x) = x 4 + x 3 + 1. { Displaystyle { begin {align} m_ {1} (x) = m_ {2} (x) = m_ {4} (x) = m_ {8} (x) = x ^ {4} + x + 1, \ m_ {3} (x) = m_ {6} (x) = m_ {9} (x) = m_ {12} (x) = x ^ {4} + x ^ {3} + x ^ {2} + x + 1, \ m_ {5} (x) = m_ {10} (x) = x ^ {2} + x + 1, \ m_ {7} (x) = m_ { 11} (x) = m_ {13} (x) = m_ {14} (x) = x ^ {4} + x ^ {3} +1. End {align}}}

Код BCH с d = 2, 3 { displaystyle d = 2,3}имеет порождающий полином

g (x) = lcm (m 1 (x), m 2 (x)) = m 1 (х) = х 4 + x + 1. { displaystyle g (x) = { rm {lcm}} (m_ {1} (x), m_ {2} (x)) = m_ {1} (x) = x ^ {4 } + x + 1. ,}

Он имеет минимальное расстояние Хэмминга не менее 3 и исправляет до одной ошибки. Поскольку порождающий полином имеет степень 4, этот код имеет 11 бит данных и 4 бита контрольной суммы.

Код BCH с d = 4, 5 { displaystyle d = 4,5}имеет порождающий полином

g (x) = lcm (m 1 (x), м 2 (х), м 3 (х), м 4 (х)) = м 1 (х) м 3 (х) = (х 4 + х + 1) (х 4 + х 3 + х 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1. { displaystyle { begin {align} g (x) = { rm {lcm}} (m_ {1} (x), m_ {2} (x), m_ {3} (x), m_ {4} (x)) = m_ {1} (x) m_ {3} (x) \ = left (x ^ {4 } + x + 1 right) left (x ^ {4} + x ^ {3} + x ^ {2} + x + 1 right) = x ^ {8} + x ^ {7} + x ^ {6} + x ^ {4} +1. End {align}}}

Он имеет минимальное расстояние Хэмминга не менее 5 и исправляет до двух ошибок. Поскольку порождающий полином имеет степень 8, этот код имеет 7 бит данных и 8 битов контрольной суммы.

Код BCH с d = 6, 7 { displaystyle d = 6,7}имеет порождающий полином

g (x) = lcm (m 1 (x), m 2 (x), m 3 (x), m 4 (x), m 5 (x), m 6 (x)) = m 1 (x) m 3 (x) m 5 (x) = ( x 4 + x + 1) (x 4 + x 3 + x 2 + x + 1) (x 2 + x + 1) = x 10 + x 8 + x 5 + x 4 + x 2 + x + 1. { Displaystyle { begin {align} g (x) = { rm {lcm}} (m_ {1} (x), m_ {2} (x), m_ {3} (x), m_ {4}) (x), m_ {5} (x), m_ {6} (x)) = m_ {1} (x) m_ {3} (x) m_ {5} (x) \ = left (x ^ {4} + x + 1 right) left (x ^ {4} + x ^ {3} + x ^ {2} + x + 1 right) left (x ^ {2} + x + 1 right) = x ^ {10} + x ^ {8} + x ^ {5} + x ^ {4} + x ^ {2} + x + 1. end {align}}}

Он имеет минимальное расстояние Хэмминга не менее 7 и исправляет до трех ошибок. Поскольку порождающий полином имеет степень 10, этот код имеет 5 бит данных и 10 битов контрольной суммы. (Этот конкретный генераторный полином имеет реальное применение в шаблонах формата QR-кода.)

Код BCH с d = 8 { displaystyle d = 8 }и выше имеет порождающий многочлен

g (x) = lcm (m 1 (x), m 2 (x),…, m 14 (x)) = m 1 (x) m 3 (x) m 5 (x) m 7 (x) = (x 4 + x + 1) (x 4 + x 3 + x 2 + x + 1) (x 2 + x + 1) (x 4 + Икс 3 + 1) = Икс 14 + Икс 13 + Икс 12 + ⋯ + Икс 2 + Икс + 1. { Displaystyle { begin {Выровнено} g (x) = { rm {lcm}} (m_ {1 } (x), m_ {2} (x),…, m_ {14} (x)) = m_ {1} (x) m_ {3} (x) m_ {5} (x) m_ {7 } (x) \ = left (x ^ {4} + x + 1 right) left (x ^ {4} + x ^ {3} + x ^ {2} + x + 1 right) left (x ^ {2} + x + 1 right) left (x ^ {4} + x ^ {3} +1 right) = x ^ {14} + x ^ {13} + x ^ { 12} + cdots + x ^ {2} + x + 1. End {align}}}

Этот код имеет минимальное расстояние Хэмминга 15 и исправляет 7 ошибок. Он имеет 1 бит данных и 14 битов контрольной суммы. Фактически, этот код имеет только два кодовых слова: 000000000000000 и 1111111111111.

Общие коды BCH

Общие коды BCH отличаются от примитивных кодов BCH с узким смыслом в двух отношениях.

Во-первых, требование, чтобы α { displaystyle alpha}был примитивным элементом GF (qm) { displaystyle mathrm {GF} (q ^ {m})}можно расслабить. При ослаблении этого требования длина кода изменяется с qm — 1 { displaystyle q ^ {m} -1}на ord (α), { displaystyle mathrm {ord} ( alpha),}порядок элемента α. { displaystyle alpha.}

Во-вторых, последовательные корни порождающего полинома могут начинаться из α c,…, α c + d — 2 { displaystyle alpha ^ {c}, ldots, alpha ^ {c + d-2}}вместо α,…, α d — 1. { displaystyle alpha, ldots, alpha ^ {d-1}.}

Определение. Исправить конечное поле GF (q), { displaystyle GF (q),}где q { displaystyle q}— степень простого числа. Выберите целые положительные числа m, n, d, c { displaystyle m, n, d, c}так, чтобы 2 ≤ d ≤ n, { displaystyle 2 leq d leq n,}gcd (n, q) = 1, { displaystyle { rm {gcd}} (n, q) = 1,}и m { displaystyle m}— порядок умножения числа q { displaystyle q}по модулю n. { displaystyle n.}

Как и раньше, пусть α { displaystyle alpha}будет примитивом n { displaystyle n}корень -й степени из единицы в GF (qm), { displaystyle GF (q ^ {m}),}и пусть mi (x) { displaystyle m_ {i } (x)}быть минимальным многочленом над GF (q) { displaystyle GF (q)}из α i { displaystyle alpha ^ {i}}для всех i. { displaystyle i.}Генераторный полином кода BCH определяется как наименьшее общее кратное g (x) = lcm (mc (x),…, mc + d — 2 (х)). { displaystyle g (x) = { rm {lcm}} (m_ {c} (x), ldots, m_ {c + d-2} (x)).}

Примечание: если n = qm — 1 { displaystyle n = q ^ {m} -1}как в упрощенном определении, затем gcd (n, q) { displaystyle { rm { gcd}} (n, q)}равно 1, и порядок q { displaystyle q}по модулю n { displaystyle n}равно м. { displaystyle m.}Следовательно, упрощенное определение действительно является частным случаем общего.

Особые случаи

Генераторный полином g (x) { displaystyle g (x)}кода BCH имеет коэффициенты из GF (q). { displaystyle mathrm {GF} (q).}В общем, циклический код над GF (qp) { displaystyle mathrm {GF} (q ^ {p})}с g (x) { displaystyle g (x)}в качестве порождающего полинома, называется кодом BCH над GF (qp). { displaystyle mathrm {GF} (q ^ {p}).}Код BCH над GF (qm) { displaystyle mathrm {GF} (q ^ {m})}и порождающий полином g (x) { displaystyle g (x)}с последовательными степенями α { displaystyle alpha}поскольку корни — это один тип кода Рида – Соломона, где алфавит декодера (синдромов) совпадает с алфавитом канала (данные и генераторный полином), все элементы GF (qm) { displaystyle mathrm {GF} (q ^ {m})}. Другой тип кода Рида-Соломона — это исходный код Рида-Соломона, который не является кодом BCH.

Свойства

Генераторный полином кода BCH имеет степень не выше (d — 1) m { displaystyle (d-1) m}. Кроме того, если q = 2 { displaystyle q = 2}и c = 1 { displaystyle c = 1}, порождающий полином имеет степень не более dm / 2 { displaystyle dm / 2}.

Код BCH имеет минимальное расстояние Хэмминга не менее d { displaystyle d}.

Код BCH является циклическим.

Кодирование

Поскольку любой многочлен, кратный образующему многочлену, является допустимым кодовым словом BCH, кодирование BCH — это просто процесс поиска некоторого многочлена, в котором генератор является фактором.

Сам код BCH не определяет значения коэффициентов полинома; концептуально, единственная задача алгоритма декодирования BCH — найти допустимое кодовое слово с минимальным расстоянием Хэмминга до полученного кодового слова. Следовательно, код BCH может быть реализован либо как систематический код , либо нет, в зависимости от того, как разработчик решает внедрить сообщение в закодированный полином.

Несистематическое кодирование: сообщение как фактор

Самый простой способ найти многочлен, кратный генератору, — это вычислить произведение некоторого произвольного полинома и генератора. В этом случае произвольный многочлен можно выбрать, используя символы сообщения в качестве коэффициентов.

s (x) = p (x) g (x) { displaystyle s (x) = p (x) g (x)}

В качестве примера рассмотрим порождающий полином g (x) = x 10 + x 9 + x 8 + x 6 + x 5 + x 3 + 1 { displaystyle g (x) = x ^ {10} + x ^ {9} + x ^ {8} + x ^ { 6} + x ^ {5} + x ^ {3} +1}, выбранный для использования в (31, 21) двоичном коде BCH, используемом POCSAG и другими. Чтобы закодировать 21-битное сообщение {101101110111101111101}, мы сначала представляем его как полином от GF (2) { displaystyle GF (2)}:

p (x) = x 20 + x 18 + x 17 + x 15 + x 14 + x 13 + x 11 + x 10 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + x 2 + 1 { displaystyle p (x) = x ^ {20 } + x ^ {18} + x ^ {17} + x ^ {15} + x ^ {14} + x ^ {13} + x ^ {11} + x ^ {10} + x ^ {9} + x ^ {8} + x ^ {6} + x ^ {5} + x ^ {4} + x ^ {3} + x ^ {2} +1}

Затем вычислите (также более GF (2) { displaystyle GF (2)}):

s (x) = p (x) g (x) = (x 20 + x 18 + x 17 + x 15 + х 14 + х 13 + х 11 + х 10 + х 9 + х 8 + х 6 + х 5 + х 4 + х 3 + х 2 + 1) (х 10 + х 9 + х 8 + х 6 + х 5 + x 3 + 1) = x 30 + x 29 + x 26 + x 25 + x 24 + x 22 + x 19 + x 17 + x 16 + x 15 + x 14 + x 12 + x 10 + x 9 + x 8 + x 6 + x 5 + x 4 + x 2 + 1 { displaystyle { begin {align} s (x) = p (x) g (x) \ = left (x ^ {20}) + x ^ {18} + x ^ {17} + x ^ {15} + x ^ {14} + x ^ {13} + x ^ {11} + x ^ {10} + x ^ {9} + x ^ {8} + x ^ {6} + x ^ {5} + x ^ {4} + x ^ {3} + x ^ {2} +1 right) left (x ^ {10} + x ^ {9} + x ^ {8} + x ^ {6} + x ^ {5} + x ^ {3} +1 right) \ = x ^ {30} + x ^ {29} + x ^ {26} + x ^ {25} + x ^ {24} + x ^ {22} + x ^ {19} + x ^ {17} + x ^ {16} + x ^ {15} + x ^ {14} + x ^ {12 } + x ^ {10} + x ^ {9} + x ^ {8} + x ^ {6} + x ^ {5} + x ^ {4} + x ^ {2} +1 end {выровнено} }}

Таким образом, переданное кодовое слово — {1100111010010111101011101110101}.

Приемник может использовать эти биты в качестве коэффициентов в s (x) { displaystyle s (x)}и после исправления ошибок для проверки правильности кодового слова может повторно вычислить p (x) = s (x) / g (x) { displaystyle p (x) = s (x) / g (x)}

Систематическая кодировка: сообщение в виде префикса

Систематический код — это код, в котором сообщение дословно отображается где-то внутри кодового слова. Следовательно, систематическое кодирование BCH включает в себя сначала встраивание полинома сообщения в полином кодового слова, а затем настройку коэффициентов оставшихся (не связанных с сообщением) членов, чтобы гарантировать, что s (x) { displaystyle s (x)}делится на g (x) { displaystyle g (x)}.

Этот метод кодирования использует тот факт, что вычитание остатка от делимого дает результат, кратный делителю. Следовательно, если мы возьмем наш многочлен сообщения p (x) { displaystyle p (x)}, как прежде, и умножим его на xn — k { displaystyle x ^ {nk}}(чтобы «сдвинуть» сообщение с пути остатка), мы можем затем использовать евклидово деление многочленов, чтобы получить:

p (x) xn — k = q (x) g (x) + r (x) { displaystyle p (x) x ^ {nk} = q (x) g (x) + r (x)}

Здесь мы видим, что q (x) g (x) { displaystyle q (x) g (x)}— допустимое кодовое слово. Поскольку r (x) { displaystyle r (x)}всегда имеет степень меньше n — k { displaystyle nk}(которая является степенью из g (x) { displaystyle g (x)}), мы можем безопасно вычесть его из p (x) xn — k { displaystyle p (x) x ^ { nk}}без изменения каких-либо коэффициентов сообщения, следовательно, мы имеем s (x) { displaystyle s (x)}как

s (x) знак равно Q (Икс) г (Икс) знак равно п (Икс) Икс — К — р (Икс) { Displaystyle s (х) = д (х) г (х) = р (х) х ^ {nk} -r (x)}

Более GF (2) { displaystyle GF (2)}(то есть с двоичными кодами BCH), этот процесс неотличим от добавления циклической проверки избыточности, и если систематический двоичный код BCH используется только для целей обнаружения ошибок, мы видим, что коды BCH являются просто обобщением математики циклических проверок избыточности.

Преимущество систематического кодирования состоит в том, что получатель может восстановить исходное сообщение, отбросив все после первого k { d isplaystyle k}коэффициентов после выполнения исправления ошибок.

Декодирование

Существует множество алгоритмов декодирования кодов BCH. Наиболее распространенные из них следуют этой общей схеме:

1. Вычислить синдромы s j для полученного вектора
2. Определить количество ошибок t и полином локатора ошибок Λ (x) из синдромы
3. Вычислить корни полинома местоположения ошибки, чтобы найти местоположения ошибки X i
4. Вычислить значения ошибки Y i в этих местоположениях ошибки
5. Исправить ошибки

Во время некоторых из этих шагов алгоритм декодирования может определить, что полученный вектор содержит слишком много ошибок и не может быть исправлен. Например, если подходящее значение t не найдено, коррекция не будет выполнена. В усеченном (не примитивном) коде место ошибки может быть вне допустимого диапазона. Если полученный вектор содержит больше ошибок, чем код может исправить, декодер может неосознанно выдать явно действительное сообщение, отличное от того, которое было отправлено.

Вычислить синдромы

Полученный вектор R { displaystyle R}представляет собой сумму правильного кодового слова C { displaystyle C}и неизвестный вектор ошибок E. { displaystyle E.}Значения синдрома формируются путем рассмотрения R { displaystyle R}как полинома и его оценки при α c,…, α c + d — 2. { displaystyle alpha ^ {c}, ldots, alpha ^ {c + d-2}.}Таким образом, синдромы

sj = R (α j) = C (α j) + Е (α j) { Displaystyle s_ {j} = R left ( alpha ^ {j} right) = C left ( alpha ^ {j} right) + E left ( alpha ^ {j} right)}

для j = c { displaystyle j = c}до c + d — 2. { displaystyle c + d-2.}

Поскольку α j { displaystyle alpha ^ {j}}— это нули g (x), { displaystyle g (x),}из которых C (x) { displaystyle C (x)}кратно, C (α j) = 0. { displaystyle C left ( alpha ^ {j} right) = 0.}Таким образом, изучение значений синдрома изолирует вектор ошибок, чтобы можно было приступить к его поиску.

Если ошибки нет, s j = 0 { displaystyle s_ {j} = 0}для всех j. { displaystyle j.}Если все синдромы равны нулю, то декодирование выполнено.

Вычислить многочлен местоположения ошибки

Если есть ненулевые синдромы, значит, есть ошибки. Декодеру необходимо выяснить, сколько ошибок и где они находятся.

Если есть одна ошибка, запишите это как E (x) = exi, { displaystyle E (x) = e , x ^ {i},}где i { displaystyle i}— местоположение ошибки, а e { displaystyle e}— ее величина. Тогда первые два синдрома:

sc = e α cisc + 1 = e α (c + 1) i = α isc { displaystyle { begin {align} s_ {c} = e , alpha ^ { c , i} \ s_ {c + 1} = e , alpha ^ {(c + 1) , i} = alpha ^ {i} s_ {c} end {align}}}

, поэтому вместе они позволяют нам вычислить e { displaystyle e}и предоставить некоторую информацию о i { displaystyle i}(полностью определяя его в случай кодов Рида – Соломона).

Если есть две или более ошибок,

E (x) = e 1 xi 1 + e 2 xi 2 + ⋯ { displaystyle E (x) = e_ {1} x ^ {i_ { 1}} + e_ {2} x ^ {i_ {2}} + cdots ,}

Не сразу понятно, как начать решение результирующих синдромов для неизвестных ek { displaystyle e_ {k }}и ik. { displaystyle i_ {k}.}

Первым шагом является поиск, совместимый с вычисленными синдромами и с минимально возможным t, { displaystyle t,}многочлен локатора:

Λ (Икс) знак равно ∏ J знак равно 1 T (Икс α ij — 1) { Displaystyle Lambda (x) = prod _ {j = 1} ^ {t} left (x alpha ^ {i_ {j}} -1 right)}

Два популярных алгоритма для этой задачи:

1. алгоритм Петерсона – Горенштейна – Цирлера
2. алгоритм Берлекампа – Месси

алгоритм Петерсона – Горенштейна – Цирлера

алгоритм Петерсона — шаг 2 обобщенной процедуры декодирования BCH. Алгоритм Петерсона используется для вычисления коэффициентов полинома локатора ошибок λ 1, λ 2,…, λ v { displaystyle lambda _ {1}, lambda _ {2}, dots, lambda _ {v} }многочлена

Λ (x) = 1 + λ 1 x + λ 2 x 2 + ⋯ + λ vxv. { displaystyle Lambda (x) = 1 + lambda _ {1} x + lambda _ {2} x ^ {2} + cdots + lambda _ {v} x ^ {v}.}

Теперь процедура алгоритма Петерсона – Горенштейна – Цирлера. Ожидается, что у нас будет как минимум 2t синдромов s c,…, s c + 2t − 1. Пусть v = t.

1. Начните с создания матрицы S v × v { displaystyle S_ {v times v}}с элементами, которые являются значениями синдрома

   S v × v = [scsc + 1 … Sc + v — 1 sc + 1 sc + 2… sc + v ⋮ ⋮ ⋱ sc + v — 1 sc + v… sc + 2 v — 2]. { Displaystyle S_ {v times v} = { begin {bmatrix} s_ {c} s_ {c + 1} dots s_ {c + v-1} \ s_ {c + 1} s_ {c + 2} dots s_ {c + v} \ vdots vdots ddots vdots \ s_ {c + v-1} s_ {c + v} dots s_ {c + 2v-2 } end {bmatrix}}.}

2. Сгенерировать вектор cv × 1 { displaystyle c_ {v times 1}}с элементами
   C v × 1 = [сбн + vsc + v + 1 ⋮ sc + 2 v — 1]. { Displaystyle C_ {v times 1} = { begin {bmatrix} s_ {c + v} \ s_ {c + v + 1} \ vdots \ s_ {c + 2v-1} end { bmatrix}}.}
3. Пусть Λ { displaystyle Lambda}обозначает неизвестные полиномиальные коэффициенты, которые задаются как
   Λ v × 1 = [λ v λ v — 1 ⋮ λ 1]. { displaystyle Lambda _ {v times 1} = { begin {bmatrix} lambda _ {v} \ lambda _ {v-1} \ vdots \ lambda _ {1} end { bmatrix}}.}
4. Сформируйте матричное уравнение
   S v × v Λ v × 1 = — C v × 1. { displaystyle S_ {v times v} Lambda _ {v times 1} = — C_ {v times 1 ,}.}
5. Если определитель матрицы S v × v { displaystyle S_ {v times v}}не равно нулю, тогда мы можем фактически найти обратную матрицу и найти значения неизвестного Λ { displaystyle Lambda}значений.
6. Если det (S v × v) = 0, { displaystyle det left (S_ {v times v} right) = 0,}затем выполните

   , если v = 0 { displaystyle v = 0}, то объявите пустой полином локатора ошибок, остановите процедуру Петерсона. конечный набор v ← v - 1 { displaystyle v  leftarrow v-1}

   продолжить с начала декодирования Петерсона, уменьшив S v × v { displaystyle S_ {v times v} }

7. После того, как у вас есть значения Λ { displaystyle Lambda}, у вас будет многочлен локатора ошибок.
8. Остановить процедуру Петерсона.

Факторный полином локатора ошибок

Теперь, когда у вас есть многочлен Λ (x) { displaystyle Lambda (x)}, его корни можно найти в форме Λ (x) знак равно (α я 1 Икс — 1) (α я 2 Икс — 1) ⋯ (α ivx — 1) { Displaystyle Lambda (x) = left ( alpha ^ {i_ {1}} x-1 right) left ( alpha ^ {i_ {2}} x-1 right) cdots left ( alpha ^ {i_ {v}} x-1 right)}грубой силой для пример с использованием алгоритма поиска Chien. Экспоненциальные степени примитивного элемента α { displaystyle alpha}дадут позиции, где возникают ошибки в полученном слове; отсюда и название полином «локатора ошибок».

Нули Λ (x) — это α,…, α.

Расчет значений ошибок

После того, как места ошибок известны, следующим шагом будет определение значений ошибок в этих местах. Затем значения ошибок используются для исправления полученных значений в этих местах для восстановления исходного кодового слова.

Для случая двоичного BCH (со всеми читаемыми символами) это тривиально; просто переверните биты принятого слова в эти позиции, и мы получим исправленное кодовое слово. В более общем случае веса ошибок ej { displaystyle e_ {j}}могут быть определены путем решения линейной системы

sc = e 1 α ci 1 + e 2 α ci 2 + ⋯ сбн + 1 знак равно е 1 α (с + 1) я 1 + е 2 α (с + 1) я 2 + ⋯ ⋮ { displaystyle { begin {align} s_ {c} = e_ {1} alpha ^ {c , i_ {1}} + e_ {2} alpha ^ {c , i_ {2}} + cdots \ s_ {c + 1} = e_ {1} alpha ^ { (c + 1) , i_ {1}} + e_ {2} alpha ^ {(c + 1) , i_ {2}} + cdots \ {} vdots end {выровнено}} }

алгоритм Форни

Однако существует более эффективный метод, известный как алгоритм Форни.

Пусть

S (x) = sc + sc + 1 x + sc + 2 х 2 + ⋯ + сбн + г — 2 х г — 2. { Displaystyle S (x) = s_ {c} + s_ {c + 1} x + s_ {c + 2} x ^ {2} + cdots + s_ {c + d-2} x ^ {d-2 }.}

v ⩽ d — 1, λ 0 ≠ 0 Λ (x) = ∑ i = 0 v λ ixi = λ 0 ∏ k = 0 v (α — ikx — 1). { displaystyle v leqslant d-1, lambda _ {0} neq 0 qquad Lambda (x) = sum _ {i = 0} ^ {v} lambda _ {i} x ^ {i} = lambda _ {0} prod _ {k = 0} ^ {v} left ( alpha ^ {- i_ {k}} x-1 right).}

И полином вычислителя ошибок

Ом (Икс) ≡ S (Икс) Λ (Икс) mod xd — 1 { Displaystyle Omega (x) Equiv S (x) Lambda (x) { bmod {x ^ {d-1}}} }

Наконец:

Λ ′ (x) = ∑ i = 1 vi ⋅ λ ixi — 1, { displaystyle Lambda ‘(x) = sum _ {i = 1} ^ {v} i cdot lambda _ {i} x ^ {i-1},}

где

i ⋅ x: = ∑ k = 1 ix. { displaystyle i cdot x: = sum _ {k = 1} ^ {i} x.}

Чем, если бы синдромы можно было объяснить словом ошибки, которое может быть ненулевым только на позициях ik { displaystyle i_ {k}}, тогда значения ошибок равны

ek = — α ik Ω (α — ik) α c ⋅ ik Λ ′ (α — ik). { displaystyle e_ {k} = — { alpha ^ {i_ {k}} Omega left ( alpha ^ {- i_ {k}} right) over alpha ^ {c cdot i_ {k} } Lambda ‘ left ( alpha ^ {- i_ {k}} right)}.}

Для кодов BCH узкого смысла c = 1, поэтому выражение упрощается до:

ek = — Ω (α — ik) Λ ′ (α — ik). { displaystyle e_ {k} = — { Omega left ( alpha ^ {- i_ {k}} right) over Lambda ‘ left ( alpha ^ {- i_ {k}} right)}.}

Объяснение вычисления алгоритма Форни

Он основан на интерполяции Лагранжа и методах производящих функций.

Рассмотрим S (x) Λ (x), { displaystyle S (x) Lambda (x),}и для простоты предположим, что λ k = 0 { displaystyle lambda _ {k} = 0}для k>v, { displaystyle k>v,}и sk = 0 { displaystyle s_ {k} = 0}для k>+ d — 2. { displaystyle k>c + d-2.}Тогда

S (x) Λ (x) = ∑ j = 0 ∞ i = 0 jsj — i + 1. { Displaystyle S (x) Lambda (x) = sum _ {j = 0} ^ { infty} sum _ {i = 0} ^ {j} s_ {j-i + 1} lambda _ { i} x ^ {j}.}

S (x) Λ (x) = S (x) {λ 0 ∏ ℓ = 1 v (α i ℓ x — 1)} = {∑ i = 0 d — 2 ∑ j = 1 vej α (c + i) ⋅ ijxi} {λ 0 ∏ ℓ = 1 v (α i ℓ x — 1)} = {∑ j = 1 vej α cij ∑ i = 0 d — 2 (α ij) ixi} {λ 0 ∏ ℓ = 1 v (α i ℓ x — 1)} = {∑ j = 1 vej α cij (x α ij) d — 1 — 1 x α ij — 1} {λ 0 ∏ ℓ = 1 v (α i ℓ x — 1)} = λ 0 ∑ j = 1 vej α cij (x α ij) d — 1 — 1 x α ij — 1 ∏ ℓ = 1 v (α i ℓ x — 1) = λ 0 ∑ j = 1 vej α cij ( ( x α ij) d − 1 − 1) ∏ ℓ ∈ { 1, ⋯, v } ∖ { j } ( α i ℓ x − 1) {displaystyle { begin{aligned}S(x)Lambda (x)=S(x)left{lambda _{0}prod _{ell =1}^{v}left(alpha ^{i_ {ell }}x-1right)right}\=left{sum _{i=0}^{d-2}sum _{j=1}^{v}e_ {j}alpha ^{(c+i)cdot i_{j}}x^{i}right}left{lambda _{0}prod _{ell =1}^{v }left(alpha ^{i_{ell }}x-1right)right}\=left{sum _{j=1}^{v}e_{j}alpha ^{ci_{j}}sum _{i=0}^{d-2}left(a lpha ^{i_{j}}right)^{i}x^{i}right}left{lambda _{0}prod _{ell =1}^{v}left(alpha ^{i_{ell }}x-1right)right}\=left{sum _{j=1}^{v}e_{j}alpha ^{ci_{j}}{frac {left(xalpha ^{i_{j}}right)^{d-1}-1}{xalpha ^{i_{j}}-1}}right}left{lambda _{0}prod _{ell =1}^{v}left(alpha ^{i_{ell }}x-1right)right}\=lambda _{0}sum _{j=1}^{v}e_{j}alpha ^{ci_{j}}{frac {left(xalpha ^{i_{j}}right)^{d-1}-1}{xalpha ^{i_{j}}-1}}prod _{ell =1}^{v}left(alpha ^{i_{ell }}x-1right)\=lambda _{0}sum _{j=1}^{v}e_{j}alpha ^{ci_{j}}left(left(xalpha ^{i_{j}}right)^{d-1}-1right)prod _{ell in {1,cdots,v}setminus {j}}left(alpha ^{i_{ell }}x-1right)end{aligned}}}

We want to compute unknowns e j, {displaystyle e_{j},}and we could simplify the context by removing the ( x α i j) d − 1 {displaystyle left(xalpha ^{i_{j}}right)^{d-1}}terms. This leads to the error evaluator polynomial

Ω ( x) ≡ S ( x) Λ ( x) mod x d − 1. {displaystyle Omega (x)equiv S(x)Lambda (x){bmod {x^{d-1}}}.}

Thanks to v ⩽ d − 1 {displaystyle vleqslant d-1}we have

Ω ( x) = − λ 0 ∑ j = 1 v e j α c i j ∏ ℓ ∈ { 1, ⋯, v } ∖ { j } ( α i ℓ x − 1). {displaystyle Omega (x)=-lambda _{0}sum _{j=1}^{v}e_{j}alpha ^{ci_{j}}prod _{ell in {1,cdots,v}setminus {j}}left(alpha ^{i_{ell }}x-1right).}

Thanks to Λ {displaystyle Lambda }(the Lagrange interpolation trick) the sum degenerates to only one summand for x = α − i k {displaystyle x=alpha ^{-i_{k}}}

Ω ( α − i k) = − λ 0 e k α c ⋅ i k ∏ ℓ ∈ { 1, ⋯, v } ∖ { k } ( α i ℓ α − i k − 1). {displaystyle Omega left(alpha ^{-i_{k}}right)=-lambda _{0}e_{k}alpha ^{ccdot i_{k}}prod _{ell in {1,cdots,v}setminus {k}}left(alpha ^{i_{ell }}alpha ^{-i_{k}}-1right).}

To get e k {displaystyle e_{k}}we just should get rid of the product. We could compute the product directly from already computed roots α − i j {displaystyle alpha ^{-i_{j}}}of Λ, {displaystyle Lambda,}but we could use simpler form.

As formal derivative

Λ ′ ( x) = λ 0 ∑ j = 1 v α i j ∏ ℓ ∈ { 1, ⋯, v } ∖ { j } ( α i ℓ x − 1), {displaystyle Lambda ‘(x)=lambda _{0}sum _{j=1}^{v}alpha ^{i_{j}}prod _{ell in {1,cdots,v}setminus {j}}left(alpha ^{i_{ell }}x-1right),}

we get again only one summand in

Λ ′ ( α − i k) = λ 0 α i k ∏ ℓ ∈ { 1, ⋯, v } ∖ { k } ( α i ℓ α − i k − 1). {displaystyle Lambda ‘left(alpha ^{-i_{k}}right)=lambda _{0}alpha ^{i_{k}}prod _{ell in {1,cdots,v}setminus {k}}left(alpha ^{i_{ell }}alpha ^{-i_{k}}-1right).}

So finally

e k = − α i k Ω ( α − i k) α c ⋅ i k Λ ′ ( α − i k). {displaystyle e_{k}=-{frac {alpha ^{i_{k}}Omega left(alpha ^{-i_{k}}right)}{alpha ^{ccdot i_{k}}Lambda ‘left(alpha ^{-i_{k}}right)}}.}

This formula is advantageous when one computes the formal derivative of Λ {displaystyle Lambda }form

Λ ( x) = ∑ i = 1 v λ i x i {displaystyle Lambda (x)=sum _{i=1}^{v}lambda _{i}x^{i}}

yielding:

Λ ′ ( x) = ∑ i = 1 v i ⋅ λ i x i − 1, {displaystyle Lambda ‘(x)=sum _{i=1}^{v}icdot lambda _{i}x^{i-1},}

where

i ⋅ x := ∑ k = 1 i x. {displaystyle icdot x:=sum _{k=1}^{i}x.}

Decoding based on extended Euclidean algorithm

An alternate process of finding both the polynomial Λ and the error locator polynomial is based on Yasuo Sugiyama’s adaptation of the Extended Euclidean algorithm. Correction of unreadable characters could be incorporated to the algorithm easily as well.

Let k 1,…, k k {displaystyle k_{1},…,k_{k}}be positions of unreadable characters. One creates polynomial localising these positions Γ ( x) = ∏ i = 1 k ( x α k i − 1). {displaystyle Gamma (x)=prod _{i=1}^{k}left(xalpha ^{k_{i}}-1right).}Set values on unreadable positions to 0 and compute the syndromes.

As we уже определили для формулы Форни, пусть S (x) = ∑ i = 0 d — 2 s c + i x i. { displaystyle S (x) = sum _ {i = 0} ^ {d-2} s_ {c + i} x ^ {i}.}

Давайте запустим расширенный алгоритм Евклида для определения наименьшего общего делителя многочлены S (x) Γ (x) { displaystyle S (x) Gamma (x)}и xd — 1. { displaystyle x ^ {d-1}.}Цель состоит не в том, чтобы найти наименьший общий делитель, а в том, чтобы найти многочлен r (x) { displaystyle r (x)}степени не выше ⌊ (d + k — 3) / 2 ⌋ { displaystyle lfloor (d + k-3) / 2 rfloor}и многочлены a (x), b (x) { displaystyle a (x), b (x)}такой, что r (x) = a (x) S (x) Γ (x) + б (х) хд — 1. { displaystyle r (x) = a (x) S (x) Gamma (x) + b (x) x ^ {d-1}.}Низкая степень r (x) { displaystyle r (x)}гарантирует, что a (x) { displaystyle a (x)}удовлетворяет расширенному (by Γ { displaystyle Gamma}), определяющие условия для Λ. { displaystyle Lambda.}

Определение Ξ (x) = a (x) Γ (x) { displaystyle Xi (x) = a (x) Gamma (x)}и используя Ξ { displaystyle Xi}вместо Λ (x) { displaystyle Lambda (x)}в формуле Фурни даст нам значения ошибок.

Основное преимущество алгоритма в том, что он тем временем вычисляет Ω (x) = S (x) Ξ (x) mod xd — 1 = r (x) { displaystyle Omega (x) = S (x) Xi (x) { bmod {x}} ^ {d-1} = r (x)}требуется в формуле Форни.

Объяснение процесса декодирования

Цель состоит в том, чтобы найти кодовое слово, которое минимально отличается от принятого слова на читаемых позициях. Выражая полученное слово как сумму ближайшего кодового слова и слова ошибки, мы пытаемся найти слово ошибки с минимальным количеством ненулевых символов на читаемых позициях. Синдром s i { displaystyle s_ {i}}ограничивает слово ошибки условием

s i = ∑ j = 0 n — 1 e j α i j. { displaystyle s_ {i} = sum _ {j = 0} ^ {n-1} e_ {j} alpha ^ {ij}.}

Мы могли бы написать эти условия отдельно или мы могли бы создать многочлен

S (x) знак равно ∑ я знак равно 0 d — 2 сбн + ixi { displaystyle S (x) = sum _ {i = 0} ^ {d-2} s_ {c + i} x ^ {i}}

и сравните коэффициенты около степеней 0 { displaystyle 0}с d — 2. { Displaystyle d-2.}

S (x) = {0, ⋯, d — 2} E (x) = ∑ i = 0 d — 2 ∑ j = 0 n — 1 ej α ij α cjxi. { Displaystyle S (Икс) { stackrel { {0, cdots, , d-2 }} {=}} E (x) = sum _ {i = 0} ^ {d-2} sum _ {j = 0} ^ {n-1} e_ {j} alpha ^ {ij} alpha ^ {cj} x ^ {i}.}

Предположим, на позиции k есть нечитаемая буква 1, { displaystyle k_ {1},}мы могли бы заменить набор синдромов {sc, ⋯, sc + d — 2} { displaystyle {s_ {c}, cdots, s_ {c + d-2} }}по набору синдромов {tc, ⋯, tc + d — 3} { displaystyle {t_ {c}, cdots, t_ { c + d-3} }}определяется уравнением ti = α k 1 si — si + 1. { displaystyle t_ {i} = alpha ^ {k_ {1}} s_ {i} -s_ {i + 1}.}Предположим для слова ошибки все ограничения из исходного набора { sc, ⋯, sc + d — 2} { displaystyle {s_ {c}, cdots, s_ {c + d-2} }}удерживает синдромов, чем

ti = α k 1 si — si + 1 = α k 1 ∑ j = 0 n — 1 ej α ij — ∑ j = 0 n — 1 ej α j α ij = ∑ j = 0 n — 1 ej (α k 1 — α j) α ij. { displaystyle t_ {i} = alpha ^ {k_ {1}} s_ {i} -s_ {i + 1} = alpha ^ {k_ {1}} sum _ {j = 0} ^ {n- 1} e_ {j} alpha ^ {ij} — sum _ {j = 0} ^ {n-1} e_ {j} alpha ^ {j} alpha ^ {ij} = sum _ {j = 0} ^ {n-1} e_ {j} left ( alpha ^ {k_ {1}} — alpha ^ {j} right) alpha ^ {ij}.}

Новый набор синдромов ограничивает вектор ошибок

fj = ej (α k 1 — α j) { displaystyle f_ {j} = e_ {j} left ( alpha ^ {k_ {1}} — alpha ^ {j} right) }

точно так же, как исходный набор синдромов ограничивал вектор ошибок ej. { displaystyle e_ {j}.}За исключением координаты k 1, { displaystyle k_ {1},}, где fk 1 = 0, { displaystyle f_ {k_ {1}} = 0,}an fj { displaystyle f_ {j}}равно нулю, если ej = 0. { displaystyle e_ {j} = 0.}Для определения местоположения ошибок мы могли бы изменить набор синдромов аналогичным образом, чтобы отразить все нечитаемые символы. Это сокращает набор синдромов на k. { displaystyle k.}

В полиномиальной формулировке замена синдромов задает {sc, ⋯, sc + d — 2} { displaystyle {s_ {c}, cdots, s_ {c + d -2} }}по набору синдромов {tc, ⋯, tc + d — 3} { displaystyle {t_ {c}, cdots, t_ {c + d-3} }}приводит к

T (x) = ∑ i = 0 d — 3 tc + ixi = α k 1 ∑ i = 0 d — 3 sc + ixi — ∑ i = 1 d — 2 сбн + ixi — 1. { Displaystyle Т (х) = сумма _ {я = 0} ^ {d-3} t_ {с + я} х ^ {я} = альфа ^ {к_ {1}} сумма _ {я = 0 } ^ {d-3} s_ {c + i} x ^ {i} — sum _ {i = 1} ^ {d-2} s_ {c + i} x ^ {i-1}.}

Следовательно,

x T (x) = {1, ⋯, d — 2} (x α k 1 — 1) S (x). { displaystyle xT (x) { stackrel { {1, cdots, , d-2 }} {=}} left (x alpha ^ {k_ {1}} — 1 right) S ( x).}

После замены S (x) { displaystyle S (x)}на S (x) Γ (x) { displaystyle S (x) Gamma (x)}, потребуется уравнение для коэффициентов около степеней k, ⋯, d — 2. { displaystyle k, cdots, d-2.}

Можно Рассмотрите возможность поиска ошибочных позиций с точки зрения устранения влияния заданных позиций так же, как и для нечитаемых символов. Если мы нашли такие позиции v { displaystyle v}, устранение их влияния приводит к получению набора синдромов, состоящего из всех нулей, то существует вектор ошибок с ошибками только по этим координатам. Если Λ (x) { displaystyle Lambda (x)}обозначает многочлен, исключающий влияние этих координат, мы получаем

S (x) Γ (x) Λ (x) знак равно {к + v, ⋯, d — 2} 0. { displaystyle S (x) Gamma (x) Lambda (x) { stackrel { {k + v, cdots, d-2 }} {=}} 0.}

В алгоритме Евклида мы пытаемся исправить не более 1 2 (d — 1 — k) { displaystyle { tfrac {1} {2}} (d-1- k)}ошибок (на читаемых позициях), потому что с большим количеством ошибок может быть больше кодовых слов на том же расстоянии от полученного слова. Следовательно, для Λ (x) { displaystyle Lambda (x)}, которое мы ищем, уравнение должно выполняться для коэффициентов, близких к степеням, начиная с

k + ⌊ 1 2 (d — 1 — л) ⌋. { displaystyle k + left lfloor { frac {1} {2}} (d-1-k) right rfloor.}

В формуле Форни, Λ (x) { displaystyle Lambda (x)}можно умножить на скаляр, что даст тот же результат.

Может случиться так, что алгоритм Евклида найдет Λ (x) { displaystyle Lambda (x)}со степенью выше, чем 1 2 (d — 1 — k) { displaystyle { tfrac {1} {2}} (d-1-k)}с числом различных корней, равным его степени, где формула Фурни могла бы исправить ошибки в все его корни, в любом случае исправление такого количества ошибок может быть рискованным (особенно без других ограничений на полученное слово). Обычно после получения Λ (x) { displaystyle Lambda (x)}более высокой степени мы решаем не исправлять ошибки. Исправление может завершиться неудачно, если Λ (x) { displaystyle Lambda (x)}имеет корни с большей кратностью или число корней меньше его степени. Отказ также может быть обнаружен по формуле Форни, возвращающей ошибку вне переданного алфавита.

Исправьте ошибки

Используя значения ошибок и местоположение ошибки, исправьте ошибки и сформируйте скорректированный кодовый вектор путем вычитания значений ошибок в местах ошибки.

Примеры декодирования

Декодирование двоичного кода без нечитаемых символов

Рассмотрим код BCH в GF (2) с d = 7 { displaystyle d = 7}и g (x) = x 10 + x 8 + x 5 + x 4 + x 2 + x + 1 { displaystyle g (x) = x ^ {10} + x ^ { 8} + x ^ {5} + x ^ {4} + x ^ {2} + x + 1}. (Это используется в QR-кодах.) Пусть передаваемое сообщение будет [1 1 0 1 1], или в полиномиальной нотации M (x) = x 4 + x 3 + x + 1. { displaystyle M (x) = x ^ {4} + x ^ {3} + x + 1.}Символы «контрольной суммы» вычисляются путем деления x 10 M ( x) { displaystyle x ^ {10} M (x)}по g (x) { displaystyle g (x)}и взяв остаток, в результате x 9 + x 4 + x 2 { displaystyle x ^ {9} + x ^ {4} + x ^ {2}}или [1 0 0 0 0 1 0 1 0 0 ]. Они добавляются к сообщению, поэтому переданное кодовое слово — [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Теперь представьте, что при передаче есть две битовые ошибки, поэтому полученное кодовое слово равно [1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]. В полиномиальной записи:

R (x) = C (x) + x 13 + x 5 = x 14 + x 11 + x 10 + x 9 + x 5 + x 4 + x 2 { displaystyle R (x) = C (x) + x ^ {13} + x ^ {5} = x ^ {14} + x ^ {11} + x ^ {10} + x ^ {9} + x ^ {5} + x ^ {4} + x ^ {2}}

Чтобы исправить ошибки, сначала вычислите синдромы. Взяв α = 0010, { displaystyle alpha = 0010,}, мы имеем s 1 = R (α 1) = 1011, { displaystyle s_ {1} = R ( альфа ^ {1}) = 1011,}s 2 = 1001, { displaystyle s_ {2} = 1001,}s 3 = 1011, { displaystyle s_ {3} = 1011,}s 4 = 1101, { displaystyle s_ {4} = 1101,}s 5 = 0001, { displaystyle s_ {5} = 0001,}и s 6 = 1001. { displaystyle s_ {6} = 1001.}Затем примените процедуру Петерсона путем сокращения строк следующей расширенной матрицы.

[S 3 × 3 | C 3 × 1] = [с 1 с 2 с 3 с 4 с 2 с 3 с 4 с 5 с 3 с 4 с 5 с 6] = [1011 1001 1011 1101 1001 1011 1101 0001 1011 1101 0001 1001] ⇒ [0001 0000 1000 0111 0000 0001 1011 0001 0000 0000 0000 0000] { displaystyle left [S_ {3 times 3} | C_ {3 times 1} right] = { begin {bmatrix} s_ {1} s_ {2 } s_ {3} s_ {4} \ s_ {2} s_ {3} s_ {4} s_ {5} \ s_ {3} s_ {4} s_ {5} s_ {6} end {bmatrix} } = { begin {bmatrix} 1011 1001 1011 1101 \ 1001 1011 1101 0001 \ 1011 1101 0001 1001 end {bmatrix}} Rightarrow { begin {bmatrix} 0001 0000 1000 0111 \ 0000 0001 0001 0001 0001 0001 0001 0001 0001 0001 \ 000075} к концу b строка, S 3 × 3 является сингулярной, что неудивительно, поскольку только две ошибки были введены в кодовое слово. Однако верхний левый угол матрицы идентичен [S 2 × 2 | C 2 × 1 ], что дает решение λ 2 = 1000, { displaystyle lambda _ {2} = 1000,}λ 1 = 1011. { displaystyle lambda _ {1} = 1011.}Результирующий полином локатора ошибок равен Λ (x) = 1000 x 2 + 1011 x + 0001, { displaystyle Lambda (x) = 1000x ^ {2} + 1011x + 0001,}, у которого есть нули в 0100 = α — 13 { displaystyle 0100 = alpha ^ {- 13}}и 0111 = α — 5. { displaystyle 0111 = alpha ^ {- 5}.}Показатели степени α { displaystyle alpha}соответствуют местоположениям ошибок. В этом примере нет необходимости вычислять значения ошибок, поскольку единственное возможное значение — 1.

Декодирование с нечитаемыми символами

Предположим тот же сценарий, но полученное слово содержит два нечитаемых символа [1 0 0? 1 1? 0 0 1 1 0 1 0 0]. Мы заменяем нечитаемые символы нулями при создании полинома, отражающего их позиции Γ (x) = (α 8 x — 1) (α 11 x — 1). { displaystyle Gamma (x) = left ( alpha ^ {8} x-1 right) left ( alpha ^ {11} x-1 right).}Мы вычисляем синдромы s 1 = α — 7, s 2 = α 1, s 3 = α 4, s 4 = α 2, s 5 = α 5, { displaystyle s_ {1} = alpha ^ {- 7}, s_ {2} = alpha ^ {1}, s_ {3} = alpha ^ {4}, s_ {4} = alpha ^ {2}, s_ {5} = alpha ^ {5},}и s 6 = α — 7. { displaystyle s_ {6} = alpha ^ {- 7}.}(Использование логарифмической записи, не зависящей от изоморфизмов GF (2). Для проверки вычислений мы можем использовать то же представление для сложения, что и было использованный в предыдущем примере. Шестнадцатеричное описание степеней α { displaystyle alpha}: последовательно 1,2,4,8,3,6, C, B, 5, A, 7, E, F, D, 9 со сложением на основе побитового xor.)

Сделаем синдромный многочлен

S (x) = α — 7 + α 1 x + α 4 x 2 + α 2 x 3 + α 5 x 4 + α — 7 x 5, { displaystyle S (x) = alpha ^ {- 7} + alpha ^ {1} x + alpha ^ {4} x ^ {2} + alpha ^ {2} x ^ {3} + alpha ^ {5} x ^ {4} + alpha ^ {- 7} x ^ {5},}

вычислить

S (x) Γ (Икс) знак равно α — 7 + α 4 Икс + α — 1 Икс 2 + α 6 Икс 3 + α — 1 Икс 4 + α 5 Икс 5 + α 7 Икс 6 + α — 3 Икс 7. { Displaystyle S (x) Gamma (x) = alpha ^ {- 7} + alpha ^ {4} x + alpha ^ {- 1} x ^ {2} + alpha ^ {6} x ^ { 3} + alpha ^ {- 1} x ^ {4} + alpha ^ {5} x ^ {5} + alpha ^ {7} x ^ {6} + alpha ^ {- 3} x ^ { 7}.}

Запустите расширенный алгоритм Евклида:

(S (x) Γ (x) x 6) = (α — 7 + α 4 x + α — 1 x 2 + α 6 x 3 + α — 1 x 4 + α 5 x 5 + α 7 x 6 + α — 3 x 7 x 6) = (α 7 + α — 3 x 1 1 0) (x 6 α — 7 + α 4 x + α — 1 x 2 + α 6 x 3 + α — 1 x 4 + α 5 x 5 + 2 α 7 x 6 + 2 α — 3 x 7) = (α 7 + α — 3 x 1 1 0) (α 4 + α — 5 x 1 1 0) (α — 7 + α 4 x + α — 1 x 2 + α 6 x 3 + α — 1 x 4 + α 5 x 5 α — 3 + (α — 7 + α 3) x + (α 3 + α — 1) x 2 + (α — 5 + α — 6) x 3 + (α 3 + α 1) x 4 + 2 α — 6 x 5 + 2 x 6) = ((1 + α — 4) + (α 1 + α 2) x + α 7 x 2 α 7 + α — 3 x α 4 + α — 5 x 1) (α — 7 + α 4 x + α — 1 x 2 + α 6 x 3 + α — 1 x 4 + α 5 x 5 α — 3 + α — 2 x + α 0 x 2 + α — 2 x 3 + α — 6 x 4) = (α — 3 + α 5 x + α 7 x 2 α 7 + α — 3 x α 4 + α — 5 x 1) (α — 5 + α — 4 x 1 1 0) (α — 3 + α — 2 x + α 0 x 2 + α — 2 х 3 + α — 6 х 4 (α 7 + α — 7) + (2 α — 7 + α 4) x + (α — 5 + α — 6 + α — 1) x 2 + (α — 7 + α — 4 + α 6) x 3 + ( α 4 + α — 6 + α — 1) x 4 + 2 α 5 x 5) = (α 7 x + α 5 x 2 + α 3 x 3 α — 3 + α 5 x + α 7 x 2 α 3 + α — 5 x + α 6 x 2 α 4 + α — 5 x) (α — 3 + α — 2 x + α 0 x 2 + α — 2 x 3 + α — 6 x 4 α — 4 + α 4 x + α 2 x 2 + α — 5 x 3). { Displaystyle { begin {align} { begin {pmatrix} S (x) Gamma (x) \ x ^ {6} end {pmatrix}} \ [6pt] = {} { begin {pmatrix} alpha ^ {- 7} + alpha ^ {4} x + alpha ^ {- 1} x ^ {2} + alpha ^ {6} x ^ {3} + alpha ^ {- 1} x ^ {4} + alpha ^ {5} x ^ {5} + alpha ^ {7} x ^ {6} + alpha ^ {- 3} x ^ {7} \ x ^ {6} конец {pmatrix}} \ [6pt] = {} { begin {pmatrix} alpha ^ {7} + alpha ^ {- 3} x 1 \ 1 0 end {pmatrix}} { begin {pmatrix} x ^ {6} \ alpha ^ {- 7} + alpha ^ {4} x + alpha ^ {- 1} x ^ {2} + alpha ^ {6} x ^ {3} + alpha ^ {-1} x ^ {4} + alpha ^ {5} x ^ {5} +2 alpha ^ {7} x ^ {6} +2 alpha ^ {- 3} x ^ {7} end {pmatrix}} \ [6pt] = {} { begin {pmatrix} alpha ^ {7} + alpha ^ {- 3} x 1 \ 1 0 end {pmatrix}} { begin {pmatrix} alpha ^ {4} + alpha ^ {- 5} x 1 \ 1 0 end {pmatrix}} \ qquad { begin {pmatrix} alpha ^ {- 7} + alpha ^ {4} x + альфа ^ {- 1} x ^ {2} + alpha ^ {6} x ^ {3} + alpha ^ {- 1} x ^ {4} + alpha ^ {5} x ^ {5} \ alpha ^ {- 3} + left ( alpha ^ {- 7} + alpha ^ {3} right) x + left ( alpha ^ {3} + alpha ^ {- 1} right) x ^ {2} + left ( alpha ^ {- 5} + alpha ^ {- 6} right) x ^ {3} + left ( alpha ^ {3} + alpha ^ {1} right) x ^ {4} +2 alpha ^ {- 6} x ^ {5} + 2x ^ {6} end {pmatrix}} \ [6pt] = {} { begin { pmatrix} left (1+ alpha ^ {- 4} right) + left ( alpha ^ {1} + alpha ^ {2} right) x + alpha ^ {7} x ^ {2} alpha ^ {7} + alpha ^ {- 3} x \ alpha ^ {4} + alpha ^ {- 5} x 1 end {pmatrix}} { begin {pmatrix} alpha ^ {- 7 } + alpha ^ {4} x + alpha ^ {- 1} x ^ {2} + alpha ^ {6} x ^ {3} + alpha ^ {- 1} x ^ {4} + alpha ^ {5} x ^ {5} \ alpha ^ {- 3} + alpha ^ {- 2} x + alpha ^ {0} x ^ {2} + alpha ^ {- 2} x ^ {3} + alpha ^ {- 6} x ^ {4} end {pmatrix}} \ [6pt] = {} { begin {pmatrix} alpha ^ {- 3} + alpha ^ {5} x + alpha ^ {7} x ^ {2} alpha ^ {7} + alpha ^ {- 3} x \ alpha ^ {4} + alpha ^ {- 5} x 1 end {pmatrix}} { begin {pmatrix} alpha ^ {- 5} + alpha ^ {- 4} x 1 \ 1 0 end {pmatrix}} \ qquad { begin {pmatrix} alpha ^ {- 3} + alpha ^ {- 2} x + alpha ^ {0} x ^ {2} + alpha ^ {- 2} x ^ {3} + alpha ^ {- 6} x ^ {4} \ left ( альфа ^ {7} + alpha ^ {- 7} right) + left (2 alpha ^ {- 7} + alpha ^ {4} right) x + left ( alpha ^ {- 5} + alpha ^ {- 6} + alpha ^ {- 1} right) x ^ {2} + left ( alpha ^ {- 7} + alpha ^ {- 4} + alpha ^ {6} вправо) x ^ {3} + left ( alpha ^ {4} + alpha ^ {- 6} + alpha ^ {- 1} right) x ^ {4} +2 alpha ^ {5} x ^ {5} end {pmatrix}} \ [6pt] = {} { begin {pmatrix} alpha ^ {7} x + alpha ^ { 5} x ^ {2} + alpha ^ {3} x ^ {3} alpha ^ {- 3} + alpha ^ {5} x + alpha ^ {7} x ^ {2} \ альфа ^ {3} + alpha ^ {- 5} x + alpha ^ {6} x ^ {2} alpha ^ {4} + alpha ^ {- 5} x end {pmatrix}} { begin { pmatrix} alpha ^ {- 3} + alpha ^ {- 2} x + alpha ^ {0} x ^ {2} + alpha ^ {- 2} x ^ {3} + alpha ^ {- 6} x ^ {4} \ alpha ^ {- 4} + alpha ^ {4} x + alpha ^ {2} x ^ {2} + alpha ^ {- 5} x ^ {3} end {pmatrix }}. end {align}}}

Мы достигли полинома степени не выше 3, а как

(- (α 4 + α — 5 x) α — 3 + α 5 x + α 7 x 2 α 3 + α — 5 x + α 6 x 2 — (α 7 x + α 5 x 2 + α 3 x 3)) (α 7 x + α 5 x 2 + α 3 x 3 α — 3 + α 5). Икс + α 7 Икс 2 α 3 + α — 5 Икс + α 6 Икс 2 α 4 + α — 5 Икс) = (1 0 0 1), { Displaystyle { begin {pmatrix} — left ( alpha ^ {4} + alpha ^ {- 5} x right) alpha ^ {- 3} + alpha ^ {5} x + alpha ^ {7} x ^ {2} \ alpha ^ {3} + alpha ^ {- 5} x + alpha ^ {6} x ^ {2} — left ( alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} right) end {pmatrix}} { begin {pmatrix} alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} alpha ^ {- 3} + alpha ^ {5} x + alpha ^ {7} x ^ {2} \ alpha ^ {3} + alpha ^ {- 5} x + alpha ^ {6} х ^ {2} а lpha ^ {4} + alpha ^ {- 5} x end {pmatrix}} = { begin {pmatrix} 1 0 \ 0 1 end {pmatrix}},}

получаем

(- ( α 4 + α — 5 x) α — 3 + α 5 x + α 7 x 2 α 3 + α — 5 x + α 6 x 2 — (α 7 x + α 5 x 2 + α 3 x 3)) ( S (x) Γ (x) x 6) = (α — 3 + α — 2 x + α 0 x 2 + α — 2 x 3 + α — 6 x 4 α — 4 + α 4 x + α 2 x 2 + α — 5 х 3). { displaystyle { begin {pmatrix} — left ( alpha ^ {4} + alpha ^ {- 5} x right) alpha ^ {- 3} + alpha ^ {5} x + alpha ^ {7} x ^ {2} \ alpha ^ {3} + alpha ^ {- 5} x + alpha ^ {6} x ^ {2} — left ( alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} right) end {pmatrix}} { begin {pmatrix} S (x) Gamma (x) \ x ^ { 6} end {pmatrix}} = { begin {pmatrix} alpha ^ {- 3} + alpha ^ {- 2} x + alpha ^ {0} x ^ {2} + alpha ^ {- 2} x ^ {3} + alpha ^ {- 6} x ^ {4} \ alpha ^ {- 4} + alpha ^ {4} x + alpha ^ {2} x ^ {2} + alpha ^ {-5} x ^ {3} end {pmatrix}}.}

Следовательно,

S (x) Γ (x) (α 3 + α — 5 x + α 6 x 2) — (α 7 x + α 5 x 2 + α 3 x 3) x 6 = α — 4 + α 4 x + α 2 x 2 + α — 5 x 3. { Displaystyle S (x) Gamma (x) left ( alpha ^ {3} + alpha ^ {- 5} x + alpha ^ {6} x ^ {2} right) — left ( alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} right) x ^ {6} = alpha ^ {- 4} + alpha ^ {4 } x + alpha ^ {2} x ^ {2} + alpha ^ {- 5} x ^ {3}.}

Пусть Λ (x) = α 3 + α — 5 x + α 6 х 2. { displaystyle Lambda (x) = alpha ^ {3} + alpha ^ {- 5} x + alpha ^ {6} x ^ {2}.}Не волнуйтесь, что λ 0 ≠ 1. { displaystyle lambda _ {0} neq 1.}Найти корень Λ с помощью грубой силы. { displaystyle Lambda.}Корни: α 2, { displaystyle alpha ^ {2},}и α 10 { displaystyle alpha ^ {10}}(найдя, например, α 2 { displaystyle alpha ^ {2}}, мы можем разделить Λ { displaystyle Lambda}соответствующим мономом (x — α 2) { displaystyle left (x- alpha ^ {2} right)}, и корень полученного монома может быть нашел легко).

Пусть

Ξ (x) = Γ (x) Λ (x) = α 3 + α 4 x 2 + α 2 x 3 + α — 5 x 4 Ω (x) = S (x) Ξ (Икс) ≡ α — 4 + α 4 Икс + α 2 Икс 2 + α — 5 Икс 3 по модулю Икс 6 { Displaystyle { begin {align} Xi (x) = Gamma (x) Lambda (x) = alpha ^ {3} + alpha ^ {4} x ^ {2} + alpha ^ {2} x ^ {3} + alpha ^ {- 5} x ^ {4} \ Омега (x) = S (x) Xi (x) Equiv alpha ^ {- 4} + alpha ^ {4} x + alpha ^ {2} x ^ {2} + alpha ^ {- 5 } x ^ {3} { bmod {x ^ {6}}} end {align}}}

Давайте искать значения ошибок по формуле

ej = — Ω (α — ij) Ξ ′ ( α — ij), { displaystyle e_ {j} = — { frac { Omega left ( alpha ^ {- i_ {j}} right)} { Xi ‘ left ( alpha ^ {- i_ {j}} right)}},}

где α — ij { displaystyle alpha ^ {- i_ {j}}}— корни Ξ (x). { Displaystyle Xi (x).}Ξ ′ (x) = α 2 x 2. { displaystyle Xi ‘(x) = alpha ^ {2} x ^ {2}.}Мы получаем

e 1 = — Ω (α 4) Ξ ′ (α 4) = α — 4 + α — 7 + α — 5 + α 7 α — 5 = α — 5 α — 5 = 1 e 2 = — Ω (α 7) Ξ ′ (α 7) = α — 4 + α — 4 + α 1 + α 1 α 1 = 0 e 3 = — Ω (α 10) Ξ ′ (α 10) = α — 4 + α — 1 + α 7 + α — 5 α 7 = α 7 α 7 = 1 e 4 Знак равно — Ω (α 2) Ξ ′ (α 2) = α — 4 + α 6 + α 6 + α 1 α 6 = α 6 α 6 = 1 { Displaystyle { begin {align} e_ {1} = — { frac { Omega ( alpha ^ {4})} { Xi ‘( alpha ^ {4})}} = { frac { alpha ^ {- 4} + alpha ^ {- 7} + alpha ^ {- 5} + alpha ^ {7}} { alpha ^ {- 5}}} = { frac { alpha ^ {- 5}} { alpha ^ {- 5}}} = 1 \ e_ {2} = — { frac { Omega ( alpha ^ {7})} { Xi ‘( alpha ^ {7})}} = { frac { alpha ^ {- 4 } + alpha ^ {- 4} + alpha ^ {1} + alpha ^ {1}} { alpha ^ {1}}} = 0 \ e_ {3} = — { frac { Omega ( alpha ^ {10})} { Xi ‘( alpha ^ {10})}} = { frac { alpha ^ {- 4} + alpha ^ {- 1} + alpha ^ {7} + alpha ^ {- 5}} { alpha ^ {7}}} = { frac { alpha ^ {7}} { alpha ^ {7}}} = 1 \ e_ {4} = — { frac { Omega ( alpha ^ {2})} { Xi ‘( alpha ^ {2})}} = { frac { alpha ^ {- 4} + alpha ^ {6} + альфа ^ {6} + alpha ^ {1}} { alpha ^ {6}}} = { frac { alpha ^ {6}} { alpha ^ {6}}} = 1 end {align}}}

Факт, что e 3 = e 4 = 1, { displaystyle e_ {3} = e_ {4} = 1,}не должно вызывать удивления.

Таким образом, исправленный код — [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Декодирование с нечитаемыми символами с небольшим количеством ошибок

Покажем поведение алгоритма для случая с небольшим количеством ошибок. Пусть полученное слово [1 0 0? 1 1? 0 0 0 1 0 1 0 0].

Снова замените нечитаемые символы нулями при создании полинома, отражающего их положение Γ (x) = (α 8 x — 1) (α 11 x — 1). { displaystyle Gamma (x) = left ( alpha ^ {8} x-1 right) left ( alpha ^ {11} x-1 right).}Вычислить синдромы s 1 = α 4, s 2 = α — 7, s 3 = α 1, s 4 = α 1, s 5 = α 0, { displaystyle s_ {1} = alpha ^ {4}, s_ {2} = alpha ^ {- 7}, s_ {3} = alpha ^ {1}, s_ {4} = alpha ^ {1}, s_ {5} = alpha ^ {0},}и s 6 = α 2. { displaystyle s_ {6} = alpha ^ {2}.}Создать синдромный многочлен

S (x) = α 4 + α — 7 x + α 1 x 2 + α 1 x 3 + α 0 x 4 + α 2 x 5, S (x) Γ (x) = α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α — 1 x 5 + α — 1 х 6 + α 6 х 7. { Displaystyle { begin {align} S (x) = alpha ^ {4} + alpha ^ {- 7} x + alpha ^ {1} x ^ {2} + alpha ^ {1} x ^ {3} + alpha ^ {0} x ^ {4} + alpha ^ {2} x ^ {5}, \ S (x) Gamma (x) = alpha ^ {4} + alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} + alpha ^ {1} x ^ {4} + alpha ^ {- 1} x ^ {5} + alpha ^ {- 1} x ^ {6} + alpha ^ {6} x ^ {7}. End {align}}}

Запустим расширенный алгоритм Евклида:

(S (x) Γ (x) x 6) = (α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α — 1 x 5 + α — 1 x 6 + α 6 x 7 x 6) = (α — 1 + α 6 x 1 1 0) (x 6 α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α — 1 x 5 + 2 α — 1 x 6 + 2 α 6 x 7) = (α — 1 + α 6 x 1 1 0) (α 3 + α 1 x 1 1 0) (α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α — 1 x 5 α 7 + (α — 5 + α 5) x + 2 α — 7 x 2 + 2 α 6 x 3 + 2 α 4 x 4 + 2 α 2 x 5 + 2 x 6) = ((1 + α 2) + (α 0 + α — 6) x + α 7 x 2 α — 1 + α 6 x α 3 + α 1 x 1) (α 4 + α 7 Икс + α 5 Икс 2 + α 3 Икс 3 + α 1 Икс 4 + α — 1 Икс 5 α 7 + α 0 Икс) { Displaystyle { begin {align} { begin {pmatrix} S (x) Gamma (x) \ x ^ {6} end {pmatrix}} = { begin {p матрица} alpha ^ {4} + alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} + alpha ^ {1} x ^ {4 } + alpha ^ {- 1} x ^ {5} + alpha ^ {- 1} x ^ {6} + alpha ^ {6} x ^ {7} \ x ^ {6} end {pmatrix }} \ = { begin {pmatrix} alpha ^ {- 1} + alpha ^ {6} x 1 \ 1 0 end {pmatrix}} { begin {pmatrix} x ^ {6} \ альфа ^ {4} + alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} + alpha ^ {1} x ^ {4} + alpha ^ {- 1} x ^ {5} +2 alpha ^ {- 1} x ^ {6} +2 alpha ^ {6} x ^ {7} end {pmatrix}} \ = { begin {pmatrix} alpha ^ {- 1} + alpha ^ {6} x 1 \ 1 0 end {pmatrix}} { begin {pmatrix} alpha ^ {3} + alpha ^ {1} x 1 \ 1 0 end {pmatrix}} { begin {pmatrix} alpha ^ {4} + alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} + alpha ^ {1} x ^ {4} + alpha ^ {- 1} x ^ {5} \ alpha ^ {7} + left ( alpha ^ {- 5} + alpha ^ {5 } right) x + 2 alpha ^ {- 7} x ^ {2} +2 alpha ^ {6} x ^ {3} +2 alpha ^ {4} x ^ {4} +2 alpha ^ {2} x ^ {5} + 2x ^ {6} end {pmatrix}} \ = { begin {pmatrix} left (1+ alpha ^ {2} right) + left ( alpha ^ {0} + alpha ^ {- 6} right) x + alpha ^ {7} x ^ {2} alpha ^ {- 1} + alpha ^ {6} x \ alpha ^ {3 } + alpha ^ {1} x 1 end {pmatrix}} { begin {pmatrix} alpha ^ {4} + alpha ^ {7} x + alpha ^ {5} x ^ {2} + альфа ^ {3} x ^ {3} + alpha ^ {1} x ^ {4} + alpha ^ {- 1} x ^ {5} \ alpha ^ {7} + alpha ^ {0} x end {pmatrix}} end {align}}}

Мы достигли полинома степени не выше 3, а как

(- 1 α — 1 + α 6 x α 3 + α 1 x — ( α — 7 + α 7 x + α 7 x 2)) (α — 7 + α 7 x + α 7 x 2 α — 1 + α 6 x α 3 + α 1 x 1) = (1 0 0 1), { displaystyle { begin {pmatrix} -1 alpha ^ {- 1} + alpha ^ {6} x \ alpha ^ {3} + alpha ^ {1} x — left ( alpha ^ { -7} + alpha ^ {7} x + alpha ^ {7} x ^ {2} right) end {pmatrix}} { begin {pmatrix} alpha ^ {- 7} + alpha ^ {7 } x + alpha ^ {7} x ^ {2} alpha ^ {- 1} + alpha ^ {6} x \ alpha ^ {3} + alpha ^ {1} x 1 end {pmatrix} } = { begin {pmatrix} 1 0 \ 0 1 end {pmatrix}},}

получаем

(- 1 α — 1 + α 6 x α 3 + α 1 x — (α — 7 + α 7 x + α 7 x 2)) (S (x) Γ (x) x 6) = (α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α — 1 x 5 α 7 + α 0 x). { displaystyle { begin {pmatrix} -1 alpha ^ {- 1} + alpha ^ {6} x \ alpha ^ {3} + alpha ^ {1} x — left ( alpha ^ { -7} + alpha ^ {7} x + alpha ^ {7} x ^ {2} right) end {pmatrix}} { begin {pmatrix} S (x) Gamma (x) \ x ^ {6} end {pmatrix}} = { begin {pmatrix} alpha ^ {4} + alpha ^ {7} x + alpha ^ {5} x ^ {2} + alpha ^ {3} x ^ {3} + alpha ^ {1} x ^ {4} + alpha ^ {- 1} x ^ {5} \ alpha ^ {7} + alpha ^ {0} x end {pmatrix}}.}

Следовательно,

S (x) Γ (x) (α 3 + α 1 x) — (α — 7 + α 7 x + α 7 x 2) x 6 = α 7 + α 0 x. { Displaystyle S (x) Gamma (x) left ( alpha ^ {3} + alpha ^ {1} x right) — left ( alpha ^ {- 7} + alpha ^ {7} x + alpha ^ {7} x ^ {2} right) x ^ {6} = alpha ^ {7} + alpha ^ {0} x.}

Пусть Λ (x) = α 3 + α 1 х. { displaystyle Lambda (x) = alpha ^ {3} + alpha ^ {1} x.}Не беспокойтесь, что λ 0 ≠ 1. { displaystyle lambda _ {0} neq 1.}Корень Λ (x) { displaystyle Lambda (x)}равен α 3 — 1. { displaystyle alpha ^ {3-1}.}

Пусть

Ξ (x) = Γ (x) Λ (x) = α 3 + α — 7 x + α — 4 x 2 + α 5 Икс 3, Ом (Икс) знак равно S (Икс) Ξ (Икс) ≡ α 7 + α 0 Икс модуль Икс 6 { Displaystyle { begin {align} Xi (x) = Gamma (x) Lambda ( x) = alpha ^ {3} + alpha ^ {- 7} x + alpha ^ {- 4} x ^ {2} + alpha ^ {5} x ^ {3}, \ Omega (x) = S (x) Xi (x) Equiv alpha ^ {7} + alpha ^ {0} x { bmod {x ^ {6}}} end {align}}}

Позвольте нам найдите значения ошибок с помощью формулы ej = — Ω (α — ij) / Ξ ′ (α — ij), { displaystyle e_ {j} = — Omega left ( alpha ^ {- i_ {j}) } right) / Xi ‘ left ( alpha ^ {- i_ {j}} right),}где α — ij { displaystyle alpha ^ {- i_ {j }}}являются корнями многочлена Ξ (x). { Displaystyle Xi (x).}

Ξ ′ (x) = α — 7 + α 5 x 2. { displaystyle Xi ‘(x) = alpha ^ {- 7} + alpha ^ {5} x ^ {2}.}

Мы получаем

e 1 = — Ω (α 4) Ξ ′ (α 4) = α 7 + α 4 α — 7 + α — 2 = α 3 α 3 = 1 e 2 = — Ω (α 7) Ξ ′ (α 7) = α 7 + α 7 α — 7 + α 4 знак равно 0 е 3 знак равно — Ω (α 2) Ξ ′ (α 2) = α 7 + α 2 α — 7 + α — 6 = α — 3 α — 3 = 1 { displaystyle { begin {align} e_ {1} = — { frac { Omega left ( alpha ^ {4} right)} { Xi ‘ left ( alpha ^ {4} right)}} = { frac { alpha ^ {7} + alpha ^ {4}} { alpha ^ {- 7} + alpha ^ {- 2}}} = { frac { alpha ^ {3}} { alpha ^ {3}} } = 1 \ e_ {2} = — { frac { Omega left ( alpha ^ {7} right)} { Xi ‘ left ( alpha ^ {7} right)}} = { frac { alpha ^ {7} + alpha ^ {7}} { alpha ^ {- 7} + alpha ^ {4}}} = 0 \ e_ {3} = — { frac { Omega left ( alpha ^ {2} right)} { Xi ‘ left ( alpha ^ {2} right)}} = { frac { alpha ^ {7} + alpha ^ {2 }} { alpha ^ {- 7} + alpha ^ {- 6}}} = { frac { alpha ^ {- 3}} { alpha ^ {- 3}}} = 1 end {выровнено} }}

Тот факт, что e 3 = 1 { displaystyle e_ {3} = 1}, не должен вызывать удивления.

Таким образом, исправленный код — [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Цитаты

Ссылки

Первичные источники

• Hocquenghem, A. (сентябрь 1959 г.), «Codes correcteurs d’erreurs», Chiffres (на французском языке), Paris, 2 : 147–156
• Bose, RC ; Рэй-Чаудхури, Д.К. (март 1960), «Класс исправления ошибок двоичных групповых кодов» (PDF), Информация и управление, 3(1): 68–79, doi : 10.1016 / s0019-9958 (60) 90287-4, ISSN 0890-5401

Вторичные источники

• Джилл, Джон (nd), EE387 Notes # 7, раздаточный материал # 28 (PDF), Stanford University, стр. 42–45, получено 21 апреля 2010 г. Примечания к курсу явно переделано на 2012 год: http://www.stanford.edu/class/ee387/
• Горенштейн, Дэниел ; Петерсон, У. Уэсли ; (1960), «Коды Бозе-Чаудхури с исправлением двух ошибок являются квази-совершенными», Информация и управление, 3 (3): 291–294, doi : 10.1016 / s0019-9958 (60) 90877-9
• Лидл, Рудольф; Пильц, Гюнтер (1999), Прикладная абстрактная алгебра (2-е изд.), Джон Вили
• Рид, Ирвинг С. ; Чен, Сюэминь (1999), Кодирование с контролем ошибок для сетей передачи данных, Бостон, Массачусетс: Kluwer Academic Publishers, ISBN 0-7923-8528-4

Далее чтение

• Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Cambridge University Press, ISBN 0-521 -55374-1
• Gilbert, WJ; Николсон, В. К. (2004), Современная алгебра с приложениями (2-е изд.), John Wiley
• Lin, S.; Костелло, Д. (2004), Кодирование с контролем ошибок: основы и приложения, Englewood Cliffs, NJ: Prentice-Hall
• MacWilliams, F.J.; Sloane, NJA (1977), Теория кодов с исправлением ошибок, Нью-Йорк, Нью-Йорк: издательство North-Holland Publishing Company
• Рудра, Атри, CSE 545, Коды с исправлением ошибок: комбинаторика, Алгоритмы и приложения, Университет в Буффало, заархивировано из оригинального 02.07.2010, получено 21 апреля 2010 г.