¿Cómo optimizar las funciones booleanas en muchas variables?

4

Dada una caja negra con N entradas binarias y especificación de la salida para cada uno de los 2 ** N posibles estados de entrada (pero no hay conocimiento previo de la lógica en la caja) Necesito Herramientas de software para diseñar la lógica de compuerta mínima en la caja. ¿Qué método o software puede sugerir cualquiera, y puede manejar problemas con N = 256?

    
pregunta cuddlyable3

4 respuestas

2

Para la implementación de una función booleana compleja, normalmente se realiza colocando un FPGA, en cuyo caso el software FPGA hará la minimización (no necesariamente en las puertas sino más probablemente en las LUT) o puede colocar directamente la tabla en un memoria (FLASH, RAM, según corresponda).

Para la implementación de la memoria, las señales de entrada binarias forman las entradas de dirección en la memoria.

En la lógica moderna, rara vez encontrará un gran número de compuertas utilizadas en la implementación de una función lógica, por lo general se usa un enfoque de búsqueda de tablas (FPGA o discreto).

    
respondido por el Kevin White
1

Veo dos rutas (similares):

  • use una herramienta de programación FPGA, como Xilinx ISE o Vivado (WebPack es gratuito para ambos), ingrese su expresión inicial en Verilog (por ejemplo) y vea su versión optimizada como esquemas RTL después de la síntesis estructural (primer paso de compilación, optimización debe estar habilitado).

    enlace

  • use una herramienta menos compleja, como las herramientas SPLC / CPLD de Atmel, ProChip Designer o WinCUPL, y escriba su expresión inicial para ser optimizada a continuación durante la compilación.

    enlace

En cualquier caso, debe estar un poco familiarizado con la herramienta que elija, al menos para crear un proyecto ficticio / ficticio con archivo (s) de origen y configurarlo correctamente.

    
respondido por el asndre
0

Hace muchos años que estaba en uso, existía una técnica manual llamada "El Método de Máquina Estatal de Algorthmic" (ASM). El Dr. D.H. Green, de la Universidad del Instituto de Ciencia y Tecnología de Manchester, escribió un libro sobre este tema. No estoy seguro de si el libro todavía está impreso, lo dudo.

La técnica se basó en el diseño de máquinas de estados finitos, pero una parte intrínseca de eso fue el diseño de funciones lógicas combinatorias (o combinatorias) que controlan las funciones de salida y las entradas a los biestables.

La técnica incluía un método de reducción / simplificación manual para reducir los circuitos lógicos. Recuerdo que en la universidad tuvimos que escribir un programa de computadora para lograr el mismo resultado. Lo siento, ya no tengo ese programa!

Técnicas automatizadas: lo que está buscando es lo que se conoce como una herramienta de síntesis, que puede tomar una descripción del comportamiento basada en texto y generar un circuito lógico a partir de él.

Una de las primeras (y caras) herramientas fue la de una empresa llamada Synopsys, creo que se llamó Synopsys Design Compiler. Solíamos usar esto en estaciones de trabajo Sun hace muchos años.

Cuando sintetiza lógica a partir de una descripción de comportamiento de texto (lenguajes: VHDL, Verilog) tiene varios parámetros que puede controlar que influyen en los procesos de síntesis.

Puede especificar restricciones de rendimiento y hacer que el software cree un diseño de circuito lógico diseñado para alta velocidad y, como resultado, utilice más puertas lógicas, o puede hacer que el software de síntesis produzca un diseño con la menor cantidad posible de puertas lógicas , lo que generalmente resulta en un diseño más lento.

Las herramientas profesionales como Synopsys incluyeron bibliotecas de puertas lógicas de los grandes fabricantes de ASIC con datos de rendimiento incluidos. Invariablemente, encontrará que la herramienta de síntesis está apuntando a una tecnología lógica particular cuando crea su diseño de salida. En el caso de los proveedores de ASIC, la salida a menudo serán simples puertas lógicas, en el caso de los proveedores de FPGA, la salida de la herramienta de síntesis es bastante diferente, ya que las arquitecturas de FPGA son considerablemente diferentes.

Así que realmente quieres buscar:   1) Una implementación de software del método ASM, o escribir un programa para hacerlo   2) Software de síntesis para dispositivos lógicos programables, pero tenga en cuenta lo que dije, la salida no será necesariamente una implementación de puerta lógica simple (usando puertas AND, OR, NAND, NOR, NOT, XOR) y dependerá de la tecnología de destino. : CPLD, FPGA, ASIC y qué funciones lógicas soportan estas tecnologías de los proveedores.

    
respondido por el Dean
0

Lo que necesita es Minimizador de lógica heurística de espresso

  

Se sigue un enfoque radicalmente diferente a este problema en el   El algoritmo ESPRESSO, desarrollado por Brayton e.a. en la Universidad de   California, Berkeley. [7] En lugar de expandir una función lógica en   Minterms, el programa manipula "cubos", representando el producto.   términos en las coberturas ON, DC y OFF iterativamente. Aunque el   no se garantiza que el resultado de minimización sea el mínimo global, en   La práctica es muy cercana, mientras que la solución es   Siempre libre de redundancia. Comparado con los otros métodos, éste   Es esencialmente más eficiente, reduciendo el uso de la memoria y el cálculo.   Tiempo por varios órdenes de magnitud. Su nombre refleja la forma de   Al instante haciendo una taza de café recién hecho. Casi no hay   Restricción al número de variables, funciones de salida y producto.   términos de un bloque de función combinacional. En general, por ej. Decenas de   las variables con decenas de funciones de salida se tratan fácilmente.

Logic Friday (una aplicación que utiliza Espresso) es 16x16 solo, así que si quieres ir a 256, consulta la fuente en enlace

    
respondido por el JonRB

Lea otras preguntas en las etiquetas