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-like cryptosystems and similar setups.

An irreducible binary Goppa code is defined by a polynomial ${\displaystyle g(x)}$ of degree ${\displaystyle t}$ over a finite field ${\displaystyle GF(2^{m})}$ with no repeated roots, and a sequence ${\displaystyle L_{1},...,L_{n}}$ of ${\displaystyle n}$ distinct elements from ${\displaystyle GF(2^{m})}$ that are not roots of ${\displaystyle g}$.

Codewords belong to the kernel of the syndrome function, forming a subspace of ${\displaystyle \{0,1\}^{n}}$:

The code defined by a tuple ${\displaystyle (g,L)}$ has dimension at least ${\displaystyle n-mt}$ and distance at least ${\displaystyle 2t+1}$, thus it can encode messages of length at least ${\displaystyle n-mt}$ using codewords of size ${\displaystyle n}$ while correcting at least ${\displaystyle \left\lfloor {\frac {(2t+1)-1}{2}}\right\rfloor =t}$ errors. It possesses a convenient parity-check matrix ${\displaystyle H}$ in form

Note that this form of the parity-check matrix, being composed of a Vandermonde matrix ${\displaystyle V}$ and diagonal matrix ${\displaystyle D}$, 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 (in most cases ${\displaystyle t/2}$).

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 ${\displaystyle t}$-by-${\displaystyle n}$ matrix over ${\displaystyle GF(2^{m})}$ to a ${\displaystyle mt}$-by-${\displaystyle n}$ binary matrix by writing polynomial coefficients of ${\displaystyle GF(2^{m})}$ elements on ${\displaystyle m}$ successive rows.

Decoding of binary Goppa codes is traditionally done by Patterson algorithm, which gives good error-correcting capability (it corrects all ${\displaystyle t}$ 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 ${\displaystyle c=(c_{1},\dots ,c_{n})}$ is expected to take a form of