Content deleted Content added
No edit summary |
|||
Line 1:
In [[mathematics]] and [[computer science]],
▲In [[mathematics]] and [[computer science]], Binary Goppa code is an [[error-correcting code]] that belongs to the class of general [[Goppa code|Goppa codes]] originally described by [[Valerii Denisovich Goppa]], but the binary structure gives it better fit for common usage in computers and telecommunication. Binary Goppa codes have interesting properties suitable for [[cryptography]] in [[McEliece cryptosystem|McEliece-like cryptosystems]] and similar setups.
==Construction and properties==
Line 7 ⟶ 5:
Binary Goppa code is defined by a [[polynomial]] <math>g(x)</math> of degree <math>t</math> over a [[finite field]] <math>GF(2^m)</math> without multiple zeros, and a sequence <math>L</math> of <math>n</math> distinct elements from <math>GF(2^m)</math> that aren't roots of the polynomial:
: <math>\forall i,j \in \mathbb{Z}_n: L_i \in GF(2^m) \and L_i \neq L_j \and g(L_i) \neq 0</math>
Code defined by a tuple <math>(g,L)</math> has minimum distance <math>2t-1</math>, thus it can correct <math>t</math> errors in a word of size <math>n-mt</math> using codewords of size <math>n</math>. It possesses a [[parity-check matrix]] <math>H</math> in form
: <math>
H=VD=\begin{pmatrix}
1 & 1 & 1 & \cdots & 1\\
Line 28 ⟶ 26:
</math>
Note that this form of the parity-check matrix, being composed of a [[Vandermonde matrix]] <math>V</math> and [[diagonal matrix]] <math>D</math>, shares the form with check matrices of [[
For practical purposes, parity-check matrix of a binary Goppa code is usually converted to a more computer-friendly binary form by a trace construction, that converts the <math>t</math>-by-<math>n</math> matrix over <math>GF(2^m)</math> to a <math>mt</math>-by-<math>n</math> binary matrix by writing polynomial cofficients of <math>GF(2^m)</math> elements on <math>m</math> successive rows.
Line 38 ⟶ 36:
Patterson algorithm converts a syndrome to a vector of errors. The syndrome of a word <math>c=(c_0,\dots,c_{n-1})</math> is expected to take a form of
: <math>s(x) = \sum_{c_i=1} \frac{1}{x - L_i} \mod g(x)</math>
Alternative form of a parity-check matrix based on formula for <math>s(x)</math> can be used to produce such syndrome with a simple matrix multiplication.
Line 44 ⟶ 42:
The algorithm then computes <math>v(x)=\sqrt{s(x)^{-1}-x} \mod g(x)</math>. That fails when <math>s(x)=0</math>, but that is the case when the input word is a codeword, so no error correction is necessary.
<math>v(x)</math> is reduced to polynomials <math>a(x)</math> and <math>b(x)</math> using the [[extended euclidean algorithm]], so that <math>a(x)=b(x)\cdot v(x) \mod g(x)</math>, while <math>\deg(a)\leq\lfloor t/2 \rfloor</math> and <math>\deg(b)\leq\lfloor (t-1)/2 \rfloor</math>.
Finally, error correction polynomial is computed as <math>\sigma(x) = a(x)^2 + x\cdot b(x)^2</math>.
Line 50 ⟶ 48:
If the original codeword was decodable and the <math>e=(e_0,e_1,\dots,e_{n-1})</math> was the error vector, then
: <math>\sigma(x) = \prod_{e_i=1} (x-L_i) </math>
Factoring or evaluating all roots of <math>\sigma(x)</math> therefore gives enough information to recover the error vector and fix the errors.
Line 56 ⟶ 54:
==Properties and usage==
Binary Goppa codes viewed as a special case of Goppa codes have the interesting property that they correct full <math>\deg(g)</math> errors, while only <math>\deg(g)/2</math> errors in ternary and all other cases. Asymptotically, this error correcting capability meets the famous [[
Because of the high error correction capacity compared to code rate and form of parity-check matrix (which is usually hardly distinguishable from a random binary matrix of full rank), the binary Goppa codes are used in several [[post-quantum]] [[cryptosystem|cryptosystems]], notably [[McEliece cryptosystem]] and [[Niederreiter cryptosystem]].
Line 70 ⟶ 68:
* [[BCH codes]]
* [[Code rate]]
* [[
[[Category:Coding theory]]
| |||