A binary Goppa code is defined by a polynomial of degree over a finite field without multiple zeros, and a sequence of distinct elements from that aren't roots of the polynomial: Codewords belong to the kernel of syndrome function, forming a subspace of : Code defined by a tuple has minimum distance, thus it can correct errors in a word of size using codewords of size. It also possesses a convenientparity-check matrix in form Note that this form of the parity-check matrix, being composed of a Vandermonde matrix and diagonal matrix, shares the form with check matrices of alternant codes, thus alternant decoders can be used on this form. Such decoders usually provide only limited error-correcting capability. 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 -by- matrix over to a -by- binary matrix by writing polynomial coefficients of elements on successive rows.
Decoding
Decoding of binary Goppa codes is traditionally done by Patterson algorithm, which gives good error-correcting capability, and is also fairly simple to implement. Patterson algorithm converts a syndrome to a vector of errors. The syndrome of a binary word is expected to take a form of Alternative form of a parity-check matrix based on formula for can be used to produce such syndrome with a simple matrix multiplication. The algorithm then computes. That fails when, but that is the case when the input word is a codeword, so no error correction is necessary. is reduced to polynomials and using the extended euclidean algorithm, so that, while and. Finally, the error locator polynomial is computed as. 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 was the binary error vector, then Factoring or evaluating all roots of therefore gives enough information to recover the error vector and fix the errors.
Binary Goppa codes viewed as a special case of Goppa codes have the interesting property that they correct full errors, while only errors in ternary and all other cases. Asymptotically, this error correcting capability meets the famous Gilbert–Varshamov bound. Because of the high error correction capacity compared to code rate and form of parity-check matrix, the binary Goppa codes are used in several post-quantum cryptosystems, notably McEliece cryptosystem and Niederreiter cryptosystem.
