Binary Goppa code: Difference between revisions

Revision as of 23:45, 3 June 2023

Latest revision as of 17:54, 18 January 2025

(4 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Kind of error correction code}}

In [[mathematics]] and [[computer science]], the '''binary Goppa code''' is an [[error-correcting code]] that belongs to the class of general Goppa codes originally described by [[Valerii Denisovich Goppa]], but the binary structure gives it several mathematical advantages over non-binary variants, also providing a 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==

AAn irreducible 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> with no repeated roots, and a sequence <math>L_1, ..., L_n</math> of <math>n</math> distinct elements from <math>GF(2^m)</math> that are not roots of <math>g</math>.

Codewords belong to the kernel of the syndrome function, forming a subspace of <math>\{0,1\}^n</math>:

: <math>\Gamma(g,L)=\left\{ c \in \{0,1\}^n \left|,\Bigg\vert\, \sum_{i=1}^{n} \frac{c_i}{x-L_i} \equiv 0 \modbmod g(x) \right. \right\}</math>

The code defined by a tuple <math>(g,L)</math> has dimension at least <math>n-mt</math> and

Line 37 ⟶ 38:

Decoding of binary Goppa codes is traditionally done by Patterson algorithm, which gives good error-correcting capability (it corrects all <math>t</math> design errors), and is also fairly simple to implement.

Patterson algorithm converts a syndrome to a vector of errors. The syndrome of a binary word <math>c=(c_0c_1,\dots,c_{n-1}c_n)</math> is expected to take a form of

: <math>s(x) \equiv \sum_{i=01}^{n-1} \frac{c_i}{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 49 ⟶ 50:

Finally, the ''error locator polynomial'' is computed as <math>\sigma(x) = a(x)^2 + x\cdot b(x)^2</math>. Note that in binary case, locating the errors is sufficient to correct them, as there's only one other value possible. In non-binary cases a separate error correction polynomial has to be computed as well.

If the original codeword was decodable and the <math>e=(e_0,e_1,\dots,e_{n-1}e_n)</math> was the binary error vector, then

: <math>\sigma(x) = \prod_{i=01}^{n-1} e_i(x-L_i)^{e_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.