Aplicación de campos de Galois a la verificación probabilista de funciones booleanas y métodos de multiplicación sobre campos de extensión GF(2m)

Abstract

El propósito del trabajo de tesis consiste en la aplicación de los campos de Galois a la verificación probabilista de funciones Booleanas, así como en la determinación de métodos de multiplicación sobre los campos de extensión GF(2m) que produzcan multiplicadores sobre dichos campos de complejidad reducida. Con respecto del problema de verificación de circuitos combinacionales, la aproximación probabilista consistente en la obtención de asignaturas a partir de la evaluación, sobre valores seleccionados de un campo finito, de expresiones transformadas de las funciones a verificar, representa una buena alternativa a los métodos de verificación clásicos basados en diagramas de decisión. En este trabajo se ha estudiado la utilización de los campos de Galois como campos finitos debido a las simplificaciones que se obtienen cuando se aplican a la verificación probabilista. Se ha desarrollado un método híbrido de verificación que combina las aproximaciones probabilista y determinista clásica, que es aplicable a circuitos combinacionales de dos niveles. Este método utiliza, asimismo, una nueva formulación que se ha desarrollado para el cálculo de operaciones Booleanas. También se ha utilizado un tipo especial de diagramas de decisión para su aplicación a la verificación probabilista de circuitos combinacionales multinivel. Con respecto de la multiplicación sobre campos de extensión GF(2m), se tiene que esta operación es la más costosa y compleja de las utilizadas en la verificación probabilista. Además, este tipo de campos se utilizan en muchas aplicaciones actuales como la criptografía, los códigos algebraicos, etc. Por este motivo, se requiere que la implementación de los multiplicadores sobre GF(2m) sean rápidos y ocupen el menor área posible. Se ha desarrollado un nuevo método de multiplicación sobre GF(2m), denominado transposicional, que produce multiplicadores cuyas complejidades teóricas temporales y espaciales son menores e iguales, respectivamente, a las mejores encontradas en la literatura. Además, la implementación sobre dispositivos reconfigurables de los multiplicadores diseñados con esta metodología, requiere menos área que los multiplicadores convencionales. Este nuevo método se ha aplicado a campos GF(2m) generados por AOPs y por varios tipos de trinomios irreducibles