Actualmente me encuentro en la situación de tener que optimizar un circuito binario reduciendo su número de puertas. Consideramos un circuito simplemente como un grafo acíclico dirigido con algunos cables de entrada y algunos cables de salida. Algunos de los cables de entrada pueden contener constantes, y otros contienen "variables". Los vértices contienen puertas que pueden ser XOR o AND .
El circuito apareció en un contexto de Ciencias de la Computación, no en uno de Ingeniería Eléctrica. Necesitamos optimizar nuestro circuito reduciendo su número de puertas, así que empezamos a pensar en algunos enfoques para lograr esta tarea. Investigando en Internet descubrimos que este es un problema bien estudiado en Ingeniería Eléctrica, con un montón de software que ayuda en esta dirección. Sin embargo, como era de esperar, la mayor parte de la documentación/información/blogs/etc. están dirigidos a los ingenieros eléctricos, y resultan abrumadores para las personas ajenas a la terminología.
Por ejemplo, logré reunir de aquí los siguientes pasos
...Primero creamos listas de redes Verilog aplanadas partimos de una combinación pura. Descripción de la HDL de la aplicación. Hemos utilizado Compilador RTL Cadence Encounter junto con el Faraday FSA0A_C 0.18 mm ASIC Standard Cell Library para síntesis . Para la síntesis, aplanamos el jerarquía de los módulos de hardware y sólo permitimos el uso de Células INV1S, AN2, XOR2HS, TIE0 y TIE1. Después de esto, reescribimos la salida y ordenamos topológicamente los circuitos resultantes.
He resaltado los términos que no tienen sentido para mí, incluso después de extensas búsquedas en Internet. Además, otras fuentes que he encontrado que pueden ayudar con este problema mantienen una notación similar y son difíciles de entender para una persona ajena.
Teniendo en cuenta lo anterior, mi pregunta es
Dado un circuito booleano con sólo
XORyANDpuertas, ¿cuál debería ser el punto de partida para minimizar su número de puertas?
Cualquier recomendación sobre programas informáticos, ejemplos, términos, etc. será muy apreciada.
Apéndice
Me sugirieron que diera más detalles sobre el problema que estoy tratando de resolver aquí. Tengo un gran circuito binario (para ser explícito, este circuito está escrito en un archivo como este ), aproximadamente 300K puertas (como he dicho anteriormente, estas son XOR o AND puertas). Quiero algorítmicamente minimizar el tamaño de este circuito para que acabe teniendo menos puertas. Además, debido al contexto en el que apareció este circuito, AND puertas tienen un coste mucho mayor que XOR puertas. Por lo tanto, una optimización con un menor número de AND es muy preferible (creo que esto puede contrastar con la optimización habitual en ingeniería eléctrica en la que sólo importa el tamaño sin distinción de los diferentes tipos de compuertas, pero puedo estar equivocado).
Para recibir respuestas más precisas incluyo un poco de mis antecedentes para este problema. Conozco la lógica booleana y puedo identificar las técnicas de optimización que se pueden utilizar para este fin. He leído sobre la optimización de dos niveles y de varios niveles (aunque no entiendo las diferencias entre ambos). También conozco la existencia de algoritmos como Esspreso y Quine-McCluskey. Por último, he leído algo sobre lenguajes HDL y RTL y compiladores, pero no estoy seguro de que sea relevante.
Mi principal problema es que no sé por dónde empezar. ¿Cuál de estos conceptos/herramienta encaja mejor en mi entorno?
Contexto de la pregunta
Por si te interesa, aquí añado algunos detalles sobre el contexto en el que apareció esta pregunta.
El campo es la criptografía, un subdominio de la informática. Más concretamente, estoy hablando de algo llamado Computación Multipartita y Cifrado Totalmente Homomórfico. El punto importante aquí es que consideramos las funciones a computar como circuitos, o DAGs, donde cada vértice es una operación (ya sea suma o multiplicación). Esta es otra forma de decir polinomios multivariados. Cuando esto se hace módulo 2 estamos hablando entonces de circuitos binarios con AND y XOR como las dos operaciones permitidas.
Ahora, el objetivo de estas técnicas es poder calcular secretamente alguna función sobre algunos datos. Esto se hace escribiendo la función en términos de XOR y AND operaciones (por ejemplo, un circuito binario o una expresión booleana muy larga) y procediendo de las entradas a las salidas de manera operación por operación.
Debido al funcionamiento de estas técnicas, cada AND operación para nosotros es mucho más caro que un XOR operación. Esto significa que tener representaciones equivalentes para el mismo programa con un menor número de AND operaciones es mucho mejor, ya que se puede realizar de forma más eficiente. Además, tener un circuito muy "profundo" es malo, así que también queremos optimizar para tener un circuito más superficial (espero que estos términos de "profundo" y "superficial" tengan sentido en este contexto).
Mi impresión inicial es que este problema podría ser similar a algunos problemas que se plantean en la ingeniería eléctrica. ¿Hay alguna correlación?
PS: Por favor, tened en cuenta que provengo de la Informática y no tengo ningún conocimiento de Ingeniería Eléctrica, por lo que esta pregunta puede ser tonta, contener terminología incorrecta, etiquetas erróneas, o incluso estar fuera de tema, en cuyo caso os pido amablemente que me indiquéis el lugar adecuado para preguntar.
