Generación de un circuito que coincida con una función booleana dada utilizando la bidecomposición

Question

Estoy buscando una explicación paso a paso de cómo obtener el circuito de una función booleana dada utilizando bi-recomposición .

Tengo una función dada como:

f(a,b,c,d)=abc~d+ab~cd+a~bcd+~abcd

Las formas normales que conozco son:

A.) Plan de Karnaugh:

k-map:

resultado:

1. DNF: f=~abcd + a~bcd + ab~cd + abc~d
2. KNF: (~a+~b+~c+~d) * (a+b) * (a+c) * (b+c) * (a+d) * (b+d) * (c+d)

DNS en Gates(a~bcd):

B.) Segundo método: minimización de Quine y McCluskey:

El resultado también lo es: f=(~abcd)+(a~bcd)+(a b ~c d)+(a b c ~d)

( herramienta ) con entrada 1: a,b,c,d y 2: [7,11,13,14]

13 puertas lógicas

---

C.) Simplificando la función en Wolfram Alpha

El resultado es: f=(abc)XOR(abd)XOR(acd)XOR(bcd)

11 puertas lógicas

(herramienta utilizada para la visualización: logic.ly )

---

D.) Con la bi-descomposición encontré este resultado:

7 puertas lógicas (el rendimiento tiene que ser probado por los puntos de referencia)

Pero, ¿cómo llegar hasta allí? Una explicación paso a paso / pseudocódigo es lo que estoy buscando.

Answer 1

El truco general para la solución de la bi-descomposición es con la identificación de los XOR.

Un XOR de 4 variables de $X \oplus Y \oplus X \oplus W$ genera el siguiente mapa de Karnaugh (mapa k). Observe el patrón de tablero de ajedrez.

Excepto la última fila y columna, se alinea con su mapa k. Por lo tanto, podemos usar el XOR de 4 variables como base y enmascarar los no deseados. Con su tabla, usted quiere enmascarar los cuando $\bar{A}\bar{D}$ o $\bar{B}\bar{C}$ . La inversa (cuando se permiten unos) es entonces la ecuación $\overline{\bar{A}\bar{D}+\bar{B}\bar{C}}$ que se simplifica a $(A+D)(B+C)$ , prueba abajo.

$$\overline{\bar{A}\bar{D}+\bar{B}\bar{C}} \\ \equiv (\overline{\bar{A}\bar{D}})(\overline{\bar{B}\bar{C}}) \\ \equiv (\overline{(\bar{A})}+\overline{(\bar{D})})(\overline{(\bar{B})}+\overline{(\bar{C})}) \\ \equiv (A+D)(B+C)$$ Añade el XOR y obtén $(A \oplus B \oplus C \oplus D)(A+D)(B+C)$ . Se trata de 4 puertas: una XOR de 4 entradas, dos OR de 2 entradas y una AND de 3 entradas. Si todo se convierte en puertas de 2 entradas, entonces se convierte en 7 puertas; tres XOR, dos OR y dos AND. Esto coincide con la bi-descomposición de la Fig. 2.

$$(A \oplus B \oplus C \oplus D)(A+D)(B+C) \\ \equiv ((A \oplus B) \oplus (C \oplus D))(A+D)(B+C)\\ \equiv (((A \oplus B) \oplus (C \oplus D))(A+D)) (B+C) \, \, \# \, as \, 2-input \, gates$$

La bi-descomposición Fig.3 utiliza un enfoque que agarra el XOR más pequeño; $A \oplus B$ y $C \oplus D$ y, a continuación, la puerta de salida del resto. $(A \oplus B)CD$ y $AB(C \oplus D)$ . Por último, se han juntado $(A \oplus B)CD + AB(C \oplus D)$ . A continuación, convertir en puertas de 2 entradas $((A \oplus B)C)D + A(B(C \oplus D))$ . Esto coincide ahora con la Fig.3.

$$grp0 = (A \oplus B)CD \, \, \# \, first \, smallest \, XOR \, group \\ grp1 = AB(C \oplus D) \, \, \# \, second \, smallest \, XOR \, group \\ grp0 + grp1 = (A \oplus B)CD + AB(C \oplus D) \\ \equiv ((A \oplus B)C)D + A(B(C \oplus D)) \, \, \# \, as \, 2-input \, gates$$

---

He tenido que buscar la definición de "bidecomposición", y mi explicación es demasiado grande para que quepa en un comentario. "Bi-descomposición" solía llamarse "agrupación"; que recuerdo vagamente que mi profesor lo llamaba hace muchos años. El proceso consiste en tomar una función y componerla como subfunciones. Este enfoque es pirablemente útil cuando los únicos 1s vecinos en un mapa K son diagonales. XOR/XNOR expresan entonces las subfunciones.

La mejor descripción online que he encontrado es:

• Funciones y ecuaciones lógicas: Modelos binarios para la informática por Christian Posthoff, Bernd Steinbach
• Un algoritmo para la bidescomposición de la lógica Funciones por Alan Mishchenko, Bernd Steinbach, Marek Perkowski