Content deleted Content added
Link suggestions feature: 3 links added. Tags: Visual edit Mobile edit Mobile web edit Newcomer task Suggested: add links |
|||
| (45 intermediate revisions by 27 users not shown) | |||
Line 1:
{{short description|Error correction code}}
In [[coding theory]], the
One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an [[Abstract algebra|algebraic]] method known as [[syndrome decoding]]. This simplifies the design of the decoder for these codes, using small low-power electronic hardware.
BCH codes are used in applications such as satellite communications,<ref>{{cite web|title=Phobos Lander Coding System: Software and Analysis|url=http://ipnpr.jpl.nasa.gov/progress_report/42-94/94V.PDF |
== Definition and illustration ==
Line 10 ⟶ 11:
Given a [[prime number]] {{mvar|q}} and [[prime power]] {{math|''q''<sup>''m''</sup>}} with positive integers {{mvar|m}} and {{mvar|d}} such that {{math|''d'' ≤ ''q''<sup>''m''</sup> − 1}}, a primitive narrow-sense BCH code over the [[finite field]] (or Galois field) {{math|GF(''q'')}} with code length {{math|''n'' {{=}} ''q''<sup>''m''</sup> − 1}} and [[Block code#The distance d|distance]] at least {{mvar|d}} is constructed by the following method.
Let {{mvar|α}} be a [[
For any positive integer {{mvar|i}}, let {{math|''m''<sub>''i''</sub>(''x'')}} be the [[minimal polynomial (field theory)|minimal polynomial]] with coefficients in {{math|GF(''q'')}} of {{math|α<sup>''i''</sup>}}.
The [[generator polynomial]] of the BCH code is defined as the [[least common multiple]] {{math|''g''(''x'') {{=}} lcm(''m''<sub>1</sub>(''x''),…,''m''<sub>''d'' − 1</sub>(''x''))}}.
It can be seen that {{math|''g''(''x'')}} is a polynomial with coefficients in {{math|GF(''q'')}} and divides {{math|''x''<sup>''n''</sup> − 1}}.
Therefore, the [[polynomial code]] defined by {{math|''g''(''x'')}} is a cyclic code.
==== Example ====
Let {{math|''q'' {{=}} 2}} and {{math|''m'' {{=}} 4}} (therefore {{math|''n'' {{=}} 15}}). We will consider different values of {{mvar|d}}
:<math>m_i\left(\alpha^i\right) \bmod \left(
The minimal polynomials
:<math>\begin{align}
m_1(x) &= m_2(x) = m_4(x) = m_8(x) = x^4 + x + 1, \\
Line 28 ⟶ 29:
\end{align}</math>
The BCH code with <math>d = 2, 3</math> has the generator polynomial
:<math>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. It is also denoted as: '''(15, 11) BCH''' code.
The BCH code with <math>d=4,5</math> has the generator polynomial
:<math>\begin{align}
g(x) &= {\rm lcm}(m_1(x),m_2(x),m_3(x),m_4(x)) = m_1(x) m_3(x) \\
Line 39 ⟶ 40:
\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. It is also denoted as: '''(15, 7) BCH''' code.
The BCH code with <math>d=6,7</math> has the generator polynomial
:<math>\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) \\
Line 47 ⟶ 48:
\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. It is also denoted as: '''(15, 5) BCH''' code. (This particular generator polynomial has a real-world application, in the "format
The BCH code with <math>d=8</math> and higher has the generator polynomial
:<math>\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)\\
Line 55 ⟶ 56:
\end{align}</math>
This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. It is also denoted as: '''(15, 1) BCH''' code. In fact, this code has only two codewords: 000000000000000 and 111111111111111 (a trivial [[repetition code]]).
=== General BCH codes ===
Line 78 ⟶ 79:
The generator polynomial <math>g(x)</math> of a BCH code has coefficients from <math>\mathrm{GF}(q).</math>
In general, a cyclic code over <math>\mathrm{GF}(q^p)</math> with <math>g(x)</math> as the generator polynomial is called a BCH code over <math>\mathrm{GF}(q^p).</math>
The BCH code over <math>\mathrm{GF}(q^m)</math> and generator polynomial <math>g(x)</math> with successive powers of <math>\alpha</math> as roots is one type of [[Reed–Solomon code]] where the decoder (syndromes) alphabet is the same as the channel (data and generator polynomial) alphabet, all elements of <math>\mathrm{GF}(q^m)</math> .<ref>{{Harvnb|Gill|n.d.|p=3}}</ref> The other type of Reed Solomon code is an [[
== Properties ==
The generator polynomial of a BCH code has degree at most <math>(d-1)m</math>. Moreover, if <math>q=2</math> and <math>c=1</math>, the generator polynomial has degree at most <math>dm/2</math>.
{{Collapse top|title=Proof}}
Each minimal polynomial <math>m_i(x)</math> has degree at most <math>m</math>. Therefore, the least common multiple of <math>d-1</math> of them has degree at most <math>(d-1)m</math>. Moreover, if <math>q=2,</math> then <math>m_i(x) = m_{2i}(x)</math> for all <math>i</math>. Therefore, <math>g(x)</math> is the least common multiple of at most <math>d/2</math> minimal polynomials <math>m_i(x)</math> for odd indices <math>i,</math> each of degree at most <math>m</math>.▼
▲Therefore, <math>g(x)</math> is the least common multiple of at most <math>d/2</math> minimal polynomials <math>m_i(x)</math> for odd indices <math>i,</math> each of degree at most <math>m</math>.
{{Collapse bottom}}
Line 96 ⟶ 93:
: <math>p(x) = b_1x^{k_1} + \cdots + b_{d-1}x^{k_{d-1}},\text{ where }k_1<k_2<\cdots<k_{d-1}.</math>
Recall that <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> are roots of <math>g(x),</math> hence of <math>p(x)</math>. This implies that <math>b_1,\ldots,b_{d-1}</math> satisfy the following equations, for each <math>i \in \{c, \dotsc, c+d-2\}</math>:
: <math>p(\alpha^i) = b_1\alpha^{ik_1} + b_2\alpha^{ik_2} + \cdots + b_{d-1}\alpha^{ik_{d-1}} = 0.</math>
In matrix form, we have
: <math>\begin{bmatrix}
\alpha^{ck_1} & \alpha^{ck_2} & \cdots & \alpha^{ck_{d-1}} \\
\alpha^{(c+1)k_1} & \alpha^{(c+1)k_2} & \cdots & \alpha^{(c+1)k_{d-1}} \\
\vdots & \vdots & & \vdots \\
\alpha^{(c+d-2)k_1} & \alpha^{(c+d-2)k_2} & \cdots & \alpha^{(c+d-2)k_{d-1}} \\
\end{bmatrix}\begin{bmatrix}
b_1 \\ b_2 \\ \vdots \\ b_{d-1}▼
\begin{bmatrix}▼
\end{bmatrix} = \begin{bmatrix}
▲b_1 \\ b_2 \\ \vdots \\ b_{d-1}
0 \\ 0 \\ \vdots \\ 0▼
▲\begin{bmatrix}
▲0 \\ 0 \\ \vdots \\ 0
</math>
The determinant of this matrix equals
:<math>\left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right)\det\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha^{k_1} & \alpha^{k_2} & \cdots & \alpha^{k_{d-1}} \\
\vdots & \vdots & & \vdots \\
\alpha^{(d-2)k_1} & \alpha^{(d-2)k_2} & \cdots & \alpha^{(d-2)k_{d-1}} \\
\end{pmatrix} = \left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right) \det(V).</math>
The matrix <math>V</math> is seen to be a [[Vandermonde matrix]], and its determinant is
:<math>\det(V) = \prod_{1\le i<j\le d-1} \left(\alpha^{k_j} - \alpha^{k_i}\right),</math>
which is non-zero. It therefore follows that <math>b_1,\ldots,b_{d-1}=0,</math> hence <math>p(x) = 0.</math>
{{Collapse bottom}}
A BCH code is cyclic.
{{Collapse top|title=Proof}} A polynomial code of length <math>n</math> is cyclic if and only if its generator polynomial divides <math>x^n-1.</math> Since <math>g(x)</math> is the minimal polynomial with roots <math>\alpha^c,\ldots,\alpha^{c+d-2},</math> it suffices to check that each of <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> is a root of <math>x^n-1.</math> This follows immediately from the fact that <math>\alpha</math> is, by definition, an <math>n</math>th root of unity.
{{Collapse bottom}}
Line 142 ⟶ 134:
=== 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.
Line 152 ⟶ 143:
:<math>\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{align}</math>
Line 160 ⟶ 151:
=== 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>s(x)</math> is divisible by <math>g(x)</math>.
Line 209 ⟶ 199:
The first step is finding, compatible with computed syndromes and with minimal possible <math>t,</math> locator polynomial:
:<math>\Lambda(x) = \prod_{j=1}^t \left(x\alpha^{i_j} - 1\right)</math>
# [[
# [[Berlekamp–Massey algorithm]]
# [[Reed–Solomon error correction#Euclidean decoder|Sugiyama Euclidean algorithm]]
====Peterson–Gorenstein–Zierler algorithm====
<!-- this confuses t (max number of errors that can be corrected) with ν (actual number of errors) -->
[[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> \lambda_1 , \lambda_2, \dots, \lambda_{v} </math> of a polynomial
: <math> \Lambda(x) = 1 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_v x^v .</math>
Line 252 ⟶ 243:
set <math>v \leftarrow v -1</math>
continue from the beginning of Peterson's decoding by making smaller <math>S_{v \times v}</math>
| After you have values of <math>\Lambda</math>, you have
| Stop Peterson procedure.
}}
Line 276 ⟶ 267:
Let
:<math>S(x) = s_c + s_{c+1}x + s_{c+2}x^2 + \cdots + s_{c+d-2}x^{d-2}.</math>▼
:<math>v \leqslant d-1, \lambda_0 \neq 0 \qquad \Lambda(x) = \sum_{i=0}^v\
▲:<math>S(x)=s_c+s_{c+1}x+s_{c+2}x^2+\cdots+s_{c+d-2}x^{d-2}.</math>
▲:<math>v\leqslant d-1, \lambda_0\neq 0 \qquad \Lambda(x)=\sum_{i=0}^v\lambda_ix^i=\lambda_0 \prod_{k=0}^{v} (\alpha^{-i_k}x-1).</math>
And the error evaluator polynomial<ref name="Gill-Forney">{{Harvnb|Gill|n.d.|p=47}}</ref>
:<math>\Omega(x) \equiv S(x) \Lambda(x) \bmod{x^{d-1}}</math>
Finally:
:<math>\Lambda'(x) = \sum_{i=1}^v i \cdot \lambda_i x^{i-1},</math>
where
:<math>i \cdot x := \sum_{k=1}^i x.</math>▼
▲:<math>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>i_k</math>, then error values are
:<math>e_k = -{\alpha^{i_k}\Omega\left(\alpha^{-i_k}\right) \over \alpha^{c\cdot i_k}\Lambda'\left(\alpha^{-i_k}\right)}.</math>
For narrow-sense BCH codes, ''c'' = 1, so the expression simplifies to:
:<math>e_k = -{\Omega\left(\alpha^{-i_k}\right) \over \Lambda'\left(\alpha^{-i_k}\right)}.</math>
==== Explanation of Forney algorithm computation ====
It is based on [[Lagrange polynomial|Lagrange interpolation]] and techniques of [[generating function]]s.
Consider <math>S(x)\Lambda(x),</math> and for the sake of simplicity suppose <math>\lambda_k = 0</math> for <math>k > v,</math> and <math>s_k = 0</math> for <math>k > c + d - 2.</math> Then
:<math>S(x)\Lambda(x) = \sum_{j=0}^{\infty}\sum_{i=0}^j s_{j-i+1}\lambda_i x^j.</math>
:<math>\begin{align}
Line 319 ⟶ 306:
Thanks to <math>v\leqslant d-1</math> we have
:<math>\Omega(x) = -\lambda_0\sum_{j=1}^v e_j\alpha^{c i_j} \prod_{\ell\in\{1,\cdots,v\}\setminus\{j\}} \left
Thanks to <math>\Lambda</math> (the Lagrange interpolation trick) the sum degenerates to only one summand for <math>x = \alpha^{-i_k}</math>
:<math>\Omega \left
To get <math>e_k</math> we just should get rid of the product. We could compute the product directly from already computed roots <math>\alpha^{-i_j}</math> of <math>\Lambda,</math> but we could use simpler form.
As [[formal derivative]]
:<math>\Lambda'(x) = \lambda_0\sum_{j=1}^v \alpha^{i_j}\prod_{\ell\in\{1,\cdots,v\}\setminus\{j\}} \left
we get again only one summand in
:<math>\Lambda'\left(\alpha^{-i_k}\right) = \lambda_0\alpha^{i_k}\prod_{\ell\in\{1,\cdots,v\}\setminus\{k\}} \left
So finally
:<math>e_k = -\frac{\alpha^{i_k}\Omega \left
This formula is advantageous when one computes the formal derivative of <math>\Lambda</math> form
:<math>\Lambda(x) = \sum_{i=1}^v \
yielding:
Line 348 ⟶ 335:
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]].<ref>Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa, and Toshihiko Namekawa. A method for solving key equation for decoding Goppa codes. Information and Control, 27:87–99, 1975.</ref> Correction of unreadable characters could be incorporated to the algorithm easily as well.
Let <math>k_1, ...
Set values on unreadable positions to 0 and compute the syndromes.
Line 377 ⟶ 364:
than
:<math>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}.</math>
New set of syndromes restricts error vector
:<math>f_j=e_j\left(\alpha^{k_1} - \alpha^j\right)</math>
the same way the original set of syndromes restricted the error vector <math>e_j.</math> Except the coordinate <math>k_1,</math> where we have <math>f_{k_1}=0,</math> an <math>f_j</math> is zero, if <math>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>k.</math>
Line 387 ⟶ 374:
In polynomial formulation, the replacement of syndromes set <math>\{s_c,\cdots,s_{c+d-2}\}</math> by syndromes set <math>\{t_c,\cdots,t_{c+d-3}\}</math> leads to
:<math>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>xT(x) \stackrel{\{1,\cdots,\,d-2\}}{=} \left
After replacement of <math>S(x)</math> by <math>S(x)\Gamma(x)</math>, one would require equation for coefficients near powers <math>k,\cdots,d-2.</math>
Line 398 ⟶ 385:
If <math>\Lambda(x)</math> denotes the polynomial eliminating the influence of these coordinates, we obtain
:<math>S(x)\Gamma(x)\Lambda(x) \stackrel{\{k+v, \cdots, d-2\}}{=} 0.</math>
In Euclidean algorithm, we try to correct at most <math>\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>\Lambda(x)</math> we are looking for, the equation must hold for coefficients near powers starting from
:<math>k + \left
In Forney formula, <math>\Lambda(x)</math> could be multiplied by a scalar giving the same result.
It could happen that the Euclidean algorithm finds <math>\Lambda(x)</math> of degree higher than <math>\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
===Correct the errors===
Line 420 ⟶ 407:
:<math>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>\alpha = 0010,</math> we have <math>s_1 = R(\alpha^1) = 1011,</math> <math>s_2 = 1001,</math> <math>s_3 = 1011,</math> <math>s_4 = 1101,</math> <math>s_5 = 0001,</math> and <math>s_6 = 1001.</math>
Next, apply the Peterson procedure by row-reducing the following [[augmented matrix]].
:<math>\left [ S_{3 \times 3} | C_{3 \times 1} \right ] =
\begin{bmatrix}s_1&s_2&s_3&s_4\\
Line 439 ⟶ 426:
==== Decoding with unreadable characters ====
Suppose the same scenario, but the received word has two unreadable characters [ 1 {{color|red|0}} 0 ? 1 1 ? 0 0 {{color|red|1}} 1 0 1 0 0 ]. We replace the unreadable characters by zeros while creating the
Let us make syndrome polynomial
Line 452 ⟶ 439:
:<math>\begin{align}
&\begin{pmatrix}S(x)\Gamma(x)\\ x^6\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^{7}x^6+ \alpha^{-3}x^7 \\ x^6\end{pmatrix} \\ [6pt] \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^4 + \alpha^{-5}x & 1\\ 1 & 0\end{pmatrix} &\qquad
\begin{pmatrix} \begin{pmatrix}\alpha^{-5}+ \alpha^{-4}x & 1\\ 1 & 0 \end{pmatrix} &\qquad
\begin{pmatrix}
\end{align}</math>
We have reached polynomial of degree at most 3, and as
:<math>\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}
we get
:<math>
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix} = \begin{pmatrix}
Therefore,
Line 476 ⟶ 468:
:<math>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.</math>
Let <math>\Lambda(x) = \alpha^{3}+ \alpha^{-5}x+ \alpha^{6}x^2.</math> Don't worry that <math>\lambda_0\neq 1.</math> Find by brute force a root of <math>\Lambda.</math> The roots are <math>\alpha^2,</math> and <math>\alpha^{10}</math> (after finding for example <math>\alpha^2</math> we can divide <math>\Lambda</math> by corresponding monom <math>\left(x - \alpha^2\right)</math> and the root of resulting monom could be found easily).
Let
:<math>\begin{align}
\Xi(x) &= \Gamma(x)\Lambda(x) = \alpha^3 + \alpha^4x^2 + \alpha^2x^3 + \alpha^{-5}x^4 \end{align}</math>
Let us look for error values using formula
Line 490 ⟶ 484:
:<math>\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>
Line 503 ⟶ 497:
Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 {{color|red|0}} 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].
Again, replace the unreadable characters by zeros while creating the
Compute the syndromes <math>s_1 = \alpha^{4}, s_2 = \alpha^{-7}, s_3 = \alpha^{1}, s_4 = \alpha^{1}, s_5 = \alpha^{0},</math> and <math>s_6 = \alpha^{2}.</math>
Create syndrome polynomial
Line 616 ⟶ 610:
|author-link= Alexis Hocquenghem
|title=Codes correcteurs d'erreurs
|language=
|journal= Chiffres
|___location= Paris
Line 622 ⟶ 616:
|pages= 147–156
|date= September 1959
}}
* {{Citation
|
|
|author-link= R. C. Bose
|first2= D. K.
Line 638 ⟶ 631:
|date= March 1960
|issn= 0890-5401
|doi=10.1016/s0019-9958(60)90287-4|url= http://repository.lib.ncsu.edu/bitstream/1840.4/2137/1/ISMS_1959_240.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://repository.lib.ncsu.edu/bitstream/1840.4/2137/1/ISMS_1959_240.pdf |archive-date=2022-10-09 |url-status=live
}}
===Secondary sources===
* {{Citation|last=Gill |first=John |title=EE387 Notes #7, Handout #28 |date=n.d. |
* {{Citation
|
|
|
|last2= Peterson
|first2= W. Wesley
|
|last3= Zierler
|first3 = Neal
|
|title= Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect
|journal= Information and Control
Line 659 ⟶ 652:
|pages= 291–294
|year= 1960
|doi= 10.1016/s0019-9958(60)90877-9
}}
* {{Citation
|
|
|first2= Günter
|last2= Pilz
Line 669 ⟶ 663:
|publisher= John Wiley
|year= 1999
}}
* {{Citation
|
|
|
|first2= Xuemin
|last2= Chen
Line 683 ⟶ 675:
|year= 1999
|isbn= 0-7923-8528-4
==Further reading==
* {{Citation |last1=Blahut |first1=Richard E. |author-link1=Richard Blahut |title=Algebraic Codes for Data Transmission |edition=2nd |publisher=[[Cambridge University Press]] |year=2003 |isbn=0-521-55374-1}}
* {{Citation
|
|
|first2= W. K.
|last2= Nicholson
Line 696 ⟶ 688:
|publisher= John Wiley
|year= 2004
}}
* {{Citation
|
|
|first2= D.
|last2= Costello
Line 708 ⟶ 698:
|___location= Englewood Cliffs, NJ
|year= 2004
}}
* {{Citation
|
|
|first2= N. J. A.
|last2= Sloane
|
|title= The Theory of Error-Correcting Codes
|___location= New York, NY
|publisher= North-Holland Publishing Company
|year= 1977
}}
* {{Citation
|first = Atri
Line 728 ⟶ 716:
|publisher = University at Buffalo
|url = http://www.cse.buffalo.edu/~atri/courses/coding-theory/
|archive-url = https://web.archive.org/web/
▲ |archive-url = https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
▲ |archive-date = 2010-07-02
|url-status = dead
}}
| |||