En matemáticas y ciencias de la computación , el código binario Goppa es un código de corrección de errores que pertenece a la clase de códigos generales Goppa originalmente descritos por Valerii Denisovich Goppa , pero la estructura binaria le da varias ventajas matemáticas sobre variantes no binarias, proporcionando también una mejor ajuste para uso común en computadoras y telecomunicaciones. Los códigos binarios Goppa tienen propiedades interesantes adecuadas para la criptografía en criptosistemas similares a McEliece y configuraciones similares.
Construcción y propiedades
Un código binario de Goppa está definido por un polinomio de grado sobre un campo finito sin varios ceros y una secuencia de elementos distintos de que no son raíces del polinomio:
Las palabras en clave pertenecen al núcleo de la función del síndrome, formando un subespacio de :
Código definido por una tupla tiene distancia mínima , por lo que puede corregir errores en una palabra de tamaño usando palabras en clave de tamaño . También posee una conveniente matriz de verificación de paridad en forma
Tenga en cuenta que esta forma de la matriz de verificación de paridad, que se compone de una matriz de Vandermonde y matriz diagonal , comparte el formulario con matrices de verificación de códigos alternativos , por lo que se pueden utilizar decodificadores alternativos en este formulario. Dichos decodificadores generalmente proporcionan solo 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 Goppa binario generalmente se convierte a una forma binaria más amigable para la computadora mediante una construcción de seguimiento, que convierte la -por- matriz sobre a un -por- matriz binaria escribiendo coeficientes polinomiales de elementos en filas sucesivas.
Descodificación
La decodificación de códigos binarios Goppa se realiza tradicionalmente mediante el algoritmo de Patterson, que ofrece una buena capacidad de corrección de errores (corrige todos los errores de diseño), y también es bastante simple de implementar.
El algoritmo de Patterson convierte un síndrome en un vector de errores. El síndrome de una palabra binaria se espera que tome una forma de
Forma alternativa de una matriz de verificación de paridad basada en la fórmula para se puede utilizar para producir dicho síndrome con una simple multiplicación de matrices.
El algoritmo luego calcula . Que falla cuando, pero ese es el caso cuando la palabra de entrada es una palabra de código, por lo que no es necesaria la corrección de errores.
se reduce a polinomios y utilizando el algoritmo euclidiano extendido , de modo que, tiempo y .
Finalmente, el polinomio del localizador de errores se calcula como. Tenga en cuenta que en el caso binario, localizar los errores es suficiente para corregirlos, ya que solo hay otro valor posible. En casos no binarios, también se debe calcular un polinomio de corrección de errores separado.
Si la palabra de código original era decodificable y la era el vector de error binario, entonces
Factorizar o evaluar todas las raíces de por lo tanto, proporciona suficiente información para recuperar el vector de error y corregir los errores.
Propiedades y uso
Los códigos binarios Goppa vistos como un caso especial de códigos Goppa tienen la propiedad interesante de que corrigen por completo errores, mientras que solo errores en ternario y todos los demás casos. 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 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 post-cuánticos , especialmente el criptosistema McEliece y criptosistema Niederreiter .
Referencias
- Elwyn R. Berlekamp, Goppa Codes, IEEE Transactions on Information Theory, Vol. IT-19, No. 5, septiembre de 1973, https://web.archive.org/web/20170829142555/http://infosec.seu.edu.cn/space/kangwei/senior_thesis/Goppa.pdf
- Daniela Engelbert, Raphael Overbeck, Arthur Schmidt. "Un resumen de los criptosistemas de tipo McEliece y su seguridad". Revista de Criptología Matemática 1, 151-199. Señor 2345114 . Versión anterior: http://eprint.iacr.org/2006/162/
- Daniel J. Bernstein. "Decodificación de listas para códigos goppa binarios". http://cr.yp.to/codes/goppalist-20110303.pdf