En matemáticas e informática , el código binario Goppa es un código de corrección de errores que pertenece a la clase de códigos Goppa generales descritos originalmente por Valerii Denisovich Goppa , pero la estructura binaria le otorga varias ventajas matemáticas sobre las variantes no binarias, proporcionando también una mejor ajuste para el uso común en computadoras y telecomunicaciones. Los códigos binarios Goppa tienen propiedades interesantes adecuadas para la criptografía en criptosistemas tipo McEliece y configuraciones similares.
Un código Goppa binario irreducible se define por un polinomio de grado sobre un campo finito sin raíces repetidas, y una secuencia de elementos distintos que no son raíces de .
Las palabras clave pertenecen al núcleo de la función del síndrome y forman un subespacio de :
El código definido por una tupla tiene al menos dimensión y distancia al menos , por lo que puede codificar mensajes de longitud al menos utilizando palabras clave de tamaño mientras corrige al menos errores. Posee una conveniente matriz de verificación de paridad en la forma
Tenga en cuenta que esta forma de matriz de verificación de paridad, que está compuesta por una matriz de Vandermonde y una matriz diagonal , comparte la forma con matrices de verificación de códigos alternativos , por lo que se pueden usar decodificadores alternativos en esta forma. Estos decodificadores normalmente sólo proporcionan una capacidad limitada de corrección de errores (en la mayoría de los casos ).
Para fines prácticos, la matriz de verificación de paridad de un código binario Goppa generalmente se convierte a una forma binaria más amigable para la computadora mediante una construcción de traza, que convierte la matriz -por- en una matriz binaria -por- escribiendo coeficientes polinomiales de elementos . en filas sucesivas.
La decodificación de códigos binarios Goppa se realiza tradicionalmente mediante el algoritmo de Patterson, que proporciona una buena capacidad de corrección de errores (corrige todos los errores de diseño) y también es bastante sencillo de implementar.
El algoritmo de Patterson convierte un síndrome en un vector de errores. Se espera que el síndrome de una palabra binaria adopte la forma de
Se puede utilizar una forma alternativa de una matriz de verificación de paridad basada en la fórmula para producir dicho síndrome con una simple multiplicación de matrices.
Luego el algoritmo calcula . Eso falla cuando , pero ese es el caso cuando la palabra de entrada es una palabra de código, por lo que no es necesaria ninguna corrección de errores.
se reduce a polinomios y utilizando el algoritmo euclidiano extendido , de modo que , while y .
Finalmente, el polinomio localizador de errores se calcula como . Tenga en cuenta que en el caso binario, localizar los errores es suficiente para corregirlos, ya que sólo hay otro valor posible. En casos no binarios, también se debe calcular un polinomio de corrección de errores por separado.
Si la palabra clave original era decodificable y era el vector de error binario, entonces
Por lo tanto , factorizar o evaluar todas las raíces proporciona suficiente información para recuperar el vector de error y corregir los errores.
Los códigos binarios Goppa vistos como un caso especial de códigos Goppa tienen la interesante propiedad de que corrigen errores completos, mientras que solo corrigen errores en los casos ternarios y en todos los demás. Asintóticamente, esta capacidad de corrección de errores cumple con el famoso límite de Gilbert-Varshamov .
Debido a la alta capacidad de corrección de errores en comparación con la tasa de código y la forma de la matriz de verificación de paridad (que generalmente apenas se distingue de una matriz binaria aleatoria de rango completo), los códigos binarios Goppa se utilizan en varios criptosistemas poscuánticos , en particular el criptosistema McEliece. y criptosistema Niederreiter .
