Binary Goppa code: Difference between revisions

Revision as of 18:52, 15 December 2023

Revision as of 11:46, 8 January 2024

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) </math>

Factoring or evaluating all roots of <math>\sigma(x)</math> therefore gives enough information to recover the error vector and fix the errors.