Binary Goppa code: Difference between revisions

Revision as of 18:52, 15 December 2023

Latest revision as of 17:54, 18 January 2025

(2 intermediate revisions by 2 users not shown)

Line 8:

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 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 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.