Minimización de la función booleana para más de 100 variables

Navega tus respuestas
1

Necesito minimizar las funciones booleanas con más de 100 variables. Además, cada fila tiene algunas condiciones que no importan.

Por ejemplo, 

  | A | B | C | D ........................| Y |
  _____________________________________________
  | 1 | 1 | 0 | 1 ........................| 1 |
  | 1 | 1 | 0 | X.........................| 1 |
  | 0 | 0 | 1 | 0.........................| 0 |

En el ejemplo anterior, si los primeros 3 bits son "110", no necesitamos considerar otros bits. Aunque el número de variables es 100, el número de entradas de fila es muy pequeño, alrededor de 3000. Sé sobre K-map y el algoritmo Quine-McCluskey que funciona muy bien para un pequeño número de variables. Hay algunos programas que pueden minimizar tales expresiones con menos de 16 variables. Pero he oído que existen algoritmos mejores y más rápidos para minimizar los circuitos que los ingenieros electrónicos utilizan para minimizar los circuitos. Desafortunadamente, no pude encontrar dicho programa que tomará mis entradas y sus salidas respectivas y proporcionará una expresión booleana minimizada. O en definitiva necesito una expresión booleana al final. Apreciaré tu ayuda.

    
pregunta Rick

2 respuestas

2

Soy perezoso.

A menudo permito que los compiladores y otros hagan mi trabajo.

Por lo tanto, te recomiendo que encuentres un lenguaje en el que puedas formular valores lógicos y luego optimizarlos.

Este es el problema principal de los sintetizadores de lenguaje de descripción de hardware (HDL), como se usa para el diseño de FPGA y IC digital.

Por lo tanto, los sintetizadores HDL son exactamente el tipo de programa al que te refieres.

Por lo tanto, simplemente tomaría mi mesa y la convertiría a un conjunto de condiciones en verilog (un HDL popular).

Luego, usaría el excelente Yosys para analizar, optimizar y emitir en uno de los muchos formatos (incluida la representación gráfica o una lista de redes de nivel de puerta) mi lógica.

Eso es bastante fácil, en realidad: 

module thing_to_be_simplified (input [399:0] in, output [12:0] out)
    if(in[2:0]==0b'110) then
       out = value;
    else if( ... ) 
       ...
endmodule

Convierta su tabla a una cascada de else if s con un simple script de python.

Luego ejecuté yosys , ejecuté el comando read_verilog en mi código fuente de verilog, ejecuté un check , ejecuté un opt (optimización), y luego show (para ver un gráfico de gates) o write_verilog (o write_<otherformat> ).

    
respondido por el Marcus Müller
1

Una excelente manera de resolver este problema es usar la herramienta de código abierto espresso. El problema con el algoritmo Quine-McCluskey es que realmente no se adapta bien con más entradas (100 es un poco de entradas).

enlace

Esta es una herramienta de código abierto creada por una universidad. Utiliza un algoritmo heurístico para (muy eficientemente) reducir las expresiones booleanas grandes.

También es lo que se usa (debajo de las coberturas) para minimizar la lógica en muchas herramientas estándar de la industria.

Un poco más de información aquí: ¿Cómo puedo convertir múltiples mapas de Karnaugh en un circuito de puerta lógica?

    
respondido por el jbord39

Lea otras preguntas en las etiquetas

Diseñar un tablero de control de horno dental ¿Cuál será la caída de voltaje en el rectificador de onda de puente 1N4007 a 24 voltios de CA? [cerrado]