Minimización del nivel de puerta – DE Parte 7

En el tutorial anterior, se discutieron todas las funciones booleanas posibles entre dos variables. En el tutorial – Álgebra booleana, se establecieron varios teoremas y postulados que son útiles para simplificar una expresión o función booleana. Sin embargo, simplificar una expresión booleana utilizando teoremas y postulados es bastante complicado y propenso a errores. Por lo tanto, para simplificar las expresiones booleanas, se han desarrollado algunos métodos de mapas. El método de mapas más utilizado es Karnaugh Map o K-Map.

Estos métodos se basan en el hecho de que cada función booleana tiene una tabla de verdad única. Una función booleana se puede representar mediante varias expresiones booleanas, pero su tabla de verdad siempre será la misma. Esto se debe a que un circuito digital siempre tendrá salidas fijas o respuesta correspondiente a las entradas. Primero analicemos el K-map.

Mapa de Karnaugh –

El mapa de Karnaugh es la técnica de simplificación más común para expresiones booleanas. Se basa en los siguientes hechos:

1) Sin embargo, cualquier función booleana se puede representar en múltiples formas o las expresiones booleanas siempre tienen una tabla de verdad única. Si dos expresiones booleanas tienen la misma tabla de verdad, tienen la misma función.

2) Cualquier función booleana se puede representar mediante suma de productos (Minterms) o producto de sumas (Maxterms).

3) La suma de Minterms o producto de Maxterms es reducible aplicando varios teoremas booleanos.

K-map es básicamente una representación tabular de la tabla de verdad. Por ejemplo, una función de dos variables puede tener la siguiente tabla de verdad:

Tabela verdade de uma função booleana de duas variáveis

Figura 1: Tabla de verdad de una función booleana de dos variables

Su K-map tabulará las salidas de las funciones correspondientes a los valores de las variables de entrada de la siguiente manera:

Imagem mostrando K-Map de uma função booleana de duas variáveis

Figura 2: Imagen que muestra K-Map de una función booleana de dos variables

K-Map es útil para minimizar expresiones booleanas que contienen hasta 5 variables o menos. Una vez construido el mapa, la expresión minimizada se puede deducir mediante el siguiente proceso:

1) Inserte unos en las celdas correspondientes a combinaciones para las cuales el valor de la función es 1 en la tabla de verdad. Luego complete 0 en las celdas restantes del K-map. Cada celda del mapa representa un Minterm. La función booleana representada por el mapa (el mapa es solo una representación gráfica de la tabla de verdad) es la suma de mintérminos que pueden contener una o más variables booleanas como literales.

2) Escanee el mapa en busca de celdas con un valor de 1 que no se puedan combinar con ninguna otra celda con un valor de 1 o forme grupos con otras celdas con un valor de 1. Esto significa identificar celdas con un valor de 1 que no tienen celdas adyacentes con un valor de 1. Estos grupos representan mintérminos que contienen todas las variables booleanas como literales en el término como parte de la función booleana.

3) Escanee el mapa en busca de celdas con un valor de 1 que sean adyacentes solo entre sí, celdas con un valor de 1 y formen grupos que contengan solo dos celdas con un valor de 1, pero que no formen parte de ningún grupo que contenga cuatro u ocho celdas. con un valor de 1. Estos grupos representan mintérminos que contienen variables booleanas como literales uno menos que el número máximo de variables booleanas en el término como parte de la función. Estos grupos se llaman pares.

4) Escanee el mapa en busca de celdas con un valor de 1 que sean adyacentes a solo otras tres celdas con un valor de 1 y formen grupos que contengan solo cuatro celdas con un valor de 1, pero que no formen parte de ningún grupo que contenga ocho celdas con un valor de 1. Estos grupos representan mintérminos que contienen variables booleanas como literales dos menos que el número máximo de variables booleanas en el término como parte de la función. Estos grupos se llaman quads. En una función de 2 variables, la formación de cuádruples significa que la salida de la función es 1.

5) Escanee el mapa en busca de celdas con un valor de 1 que sean adyacentes a otras siete celdas con un valor de 1 y formen grupos que contengan ocho celdas con un valor de 1, pero que no formen parte de ningún grupo que contenga dieciséis celdas con un valor de 1 o mayor. Estos grupos representan minitérminos que contienen variables booleanas como literales tres menos que el número máximo de variables booleanas en el término como parte de la función. Estos grupos se llaman octetos. En una función de 3 variables, la formación del octeto significa que la salida de la función es 1.

6) Formar todos los grupos de solteros, parejas, cuatrillizos y octetos de manera que haya un número mínimo de grupos. También se pueden formar pares, cuatrillizos y octetos combinando celdas con un valor de 1 en bordes opuestos del mapa. Como en el siguiente mapa K para una función booleana de 3 variables, m0 y m8 en las esquinas forman un par.

Imagem mostrando K-Map de uma função booleana de três variáveis

Figura 3: Imagen que muestra K-Map de una función booleana de tres variables

7) Elimine los grupos redundantes.

8) Una celda con valor 1 sin ninguna celda adyacente con valor 1 proporciona un Minterm que contiene 2, 3, 4, 5 términos variables para una función booleana o mapa K de 2 variables, 3 variables, 4 variables y 5 variables, respectivamente. Un par de celdas con valor 1 proporciona un Minterm que contiene 1, 2, 3, 4 términos variables para una función booleana o mapa K de 2 variables, 3 variables, 4 variables y 5 variables, respectivamente. Un cuádruple de celdas con valor 1 da un Minterm que contiene 1, 2, 3 términos variables para una función booleana o mapa K de 3 variables, 4 variables y 5 variables, respectivamente. La formación de cuádruple para una función de 2 variables significa que es igual a 1. Un octeto de celdas con valor 1 proporciona un Minterm que contiene 2 o 3 términos variables para una función booleana de 4 y 5 variables o K-map, respectivamente. La formación de octetos para una función de 3 variables significa que es igual a 1.

9) Si se identifica una sola celda con valor 1, representa un Minterm que tiene la variable booleana como literal en el término corresponde al valor 1 para la respectiva variable booleana y/o que tiene el complemento de la variable booleana como literal en el término corresponde al valor 0 para la respectiva variable booleana. Esta celda con valor 1 inducirá un Minterm en la función que contiene todas las variables booleanas en forma complementaria o normal. Si se identifica un par, se eliminará una variable booleana y se inducirá en la función booleana un Minterm que contenga un número menos de variables booleanas máximas. De manera similar, un quad conduce a la eliminación de dos variables booleanas en Minterm, y así sucesivamente. Se elimina del término la variable booleana que tenga un desplazamiento de bit dentro del par, cuádruple o octeto.

10) La función booleana es la suma lógica de los Minterms generados por todos los grupos. La función booleana como producto de la suma se puede generar de forma similar mediante grupos de ceros.

Mapa K de dos variables

Un K-map de dos variables tiene cuatro celdas, ya que el número máximo de minitérminos posibles con dos variables booleanas es 4 (2^2). Puede haber un máximo de 16 funciones (2^2*2) generadas por dos variables booleanas.

Imagem mostrando K-Map de uma função booleana de duas variáveis ​​por Minterms

Figura 4: Imagen que muestra K-Map de una función booleana de dos variables según Minterms

Una función generada por un mapa K de dos variables es reducible por celdas individuales o pares de valor 1. La formación de un cuadrilátero en el mapa K de dos variables significa que la función es igual a 1.

Mapa K de tres variables

Un K-map de tres variables tiene ocho celdas, ya que el número máximo de minitérminos posibles con tres variables booleanas es 8 (2^3). Puede haber un máximo de 64 funciones (2^2*3) generadas por tres variables booleanas.

Imagem mostrando K-Map de uma função booleana de três variáveis ​​por Minterms

Figura 5: Imagen que muestra K-Map de una función booleana de tres variables realizada por Minterms

Una función generada por un mapa K de tres variables se puede reducir a celdas de valor simple, par o cuádruple. La formación de un octeto en el mapa K de tres variables significa que la función es igual a 1.

Mapa K de cuatro variables

Un K-map de cuatro variables tiene dieciséis celdas, ya que el número máximo de minitérminos posibles con cuatro variables booleanas es 16 (2^4). Puede haber un máximo de 256 funciones (2^2*4) generadas por cuatro variables booleanas.

Imagem mostrando K-Map de uma função booleana de quatro variáveis ​​por Minterms

Figura 6: Imagen que muestra K-Map de una función booleana de cuatro variables realizada por Minterms

Una función generada por un mapa K de cuatro variables se puede reducir a celdas individuales de valor 1, pares, cuatrillizos u octetos. La formación de 16 celdas de un solo valor en un mapa K de cuatro variables significa que la función es igual a 1.

Mapa K de cinco variables

Un K-map de cinco variables tiene treinta y dos celdas, ya que el número máximo de mintérminos posibles con cinco variables booleanas es 32 (2^5). Puede haber un máximo de 1024 funciones (2^2*5) generadas por cinco variables booleanas.

Imagem mostrando K-Map de uma função booleana de cinco variáveis ​​por Minterms

Figura 7: Imagen que muestra K-Map de una función booleana de cinco variables realizada por Minterms

Una función generada por un mapa K de cinco variables se puede reducir a celdas individuales de valor 1, pares, cuatrillizos, octetos o grupos de 16 celdas de valor 1. La formación de 32 celdas de un solo valor en un mapa K de cinco variables significa que la función es igual a 1.

No me importan las combinaciones

No es necesario que se conozcan siempre todas las salidas de una función booleana. En los circuitos digitales, puede existir la posibilidad de que para ciertas combinaciones la salida sea 1 o 0. En este caso, d, x o Ø se insertan en el mapa K para las combinaciones de entrada correspondientes. Para derivar la expresión booleana, se puede asumir 1 o 0 en combinaciones indiferentes para deducir una suma mínima de productos o producto de la expresión suma.

Método Quine-McCluskey

K-map es útil para deducir expresiones booleanas que involucran cuatro variables booleanas o menos. Además, se vuelve complejo. Por lo tanto, se utiliza otro método llamado método Quine-McCluskey para deducir expresiones booleanas que involucran cuatro o más variables booleanas. El método Quine-McCluskey es un método tabular para derivar la expresión booleana mínima. En la tabla de verdad de una función booleana, se pueden enumerar combinaciones para las cuales la salida de la función es 1. Estas combinaciones se pueden indexar en orden ascendente como números binarios. Por ejemplo, supongamos que hay una función booleana que involucra cuatro variables booleanas (A, B, C, D) con la siguiente tabla de verdad:

Tabela verdade de uma função booleana de quatro variáveis

Fig. 8: Tabla de verdad de una función booleana de cuatro variables

Las combinaciones que dan como resultado 1 cuando se indexan en orden ascendente como números binarios dan la siguiente tabla para el caso anterior

Tabela usada no método Quine-McCluskey para função booleana de quatro variáveis

Fig. 9: Tabla utilizada en el método Quine-McCluskey para una función booleana de cuatro variables

Esta función booleana se puede escribir de la siguiente manera: las combinaciones que dan como resultado 1 cuando se indexan en orden ascendente como números binarios dan la siguiente tabla para el caso anterior:

F(A, B, C, D) = ∑ (0, 5, 8, 9, 10, 11, 14, 15)

En el primer paso del método Quine-McCluskey , los minitérminos se organizan en grupos según el número de unos que contienen de la siguiente manera:

Tabela usada no método Quine-McCluskey para função booleana de quatro variáveis

Fig. 10: Tabla utilizada en el método Quine-McCluskey para una función booleana de cuatro variables

Dos minitérminos cualesquiera en grupos adyacentes como el grupo 0 y 1, el grupo 1 y 2 o el grupo 2 y 3, etc., ahora se comparan y examinan para detectar el cambio en el valor de una sola variable booleana. Estos minitérminos se seleccionan como coincidencias y se tabulan como pares en el siguiente paso con un guión donde una única variable booleana se cambia para coincidir de la siguiente manera:

Tabela usada no método Quine-McCluskey para função booleana de quatro variáveis

Fig. 11: Tabla utilizada en el método Quine-McCluskey para una función booleana de cuatro variables

En el siguiente paso, las coincidencias en los grupos de tablas adyacentes en el paso 2 se comparan y examinan para rastrear la misma variable y cambiar el valor de una sola variable booleana. Estos partidos se seleccionan como canchas y se tabulan en la siguiente tabla con un guión donde se cambió la variable booleana única para el partido. Los pares en la segunda tabla y los términos mínimos en la primera tabla que no coincidieron en las tablas respectivas también se tabulan en la siguiente tabla (tercera tabla) de la siguiente manera:

Tabela usada no método Quine-McCluskey para função booleana de quatro variáveis

Fig. 12: Tabla utilizada en el método Quine-McCluskey para una función booleana de cuatro variables

Los cuatrillizos, pares o simples derivados en la tercera tabla (eliminando los redundantes) se denominan implementos principales. En el siguiente paso, los implementos principales se tabulan con los minterms y los minterms incluidos en el respectivo implemento principal (cuádruple, par o simple) se marcan con una X con respecto al respectivo implemento principal de la siguiente manera:

Tabela usada no método Quine-McCluskey para função booleana de quatro variáveis

Fig. 13: Tabla utilizada en el método Quine-McCluskey para una función booleana de cuatro variables

En la tabla final, se examinan las columnas que tienen una única X y se identifican las filas que contienen esa X. Se anotan los principales implementos respectivos a estas filas y los términos respectivos a estos implementos principales se incluyen como suma de productos en la expresión booleana comparando los implementos principales y las variables booleanas de la tercera tabla. En la tercera tabla, la variable booleana del implemento principal seleccionado con valor de guión no está incluida, la variable booleana del implemento principal seleccionado con valor 1 se incluye en forma normal en el término respectivo y la variable booleana del implemento principal seleccionado con valor 0 se incluye en forma complementaria en el término respectivo. Los principales implementos seleccionados de la cuarta tabla se denominan implementos esenciales. Para la función booleana anterior, en la cuarta tabla, todas las filas tienen una X que es única en al menos una columna. Por lo tanto, se seleccionan todas las filas y todos los implementos principales son implementos principales para la función booleana. De la tercera tabla, la expresión booleana para la función se puede derivar de la siguiente manera:

F (A, B, C, D) =AB' + AC + B'C'D' + A'BC'D

Ahora, con el conocimiento de K-map y el método Quine-McCluskey, cualquier función booleana con una tabla de verdad determinada se puede minimizar fácilmente. En el siguiente tutorial, aprenderá sobre la implementación de la puerta lógica de una expresión booleana minimizada.

contenido relacionado

Regresar al blog

Deja un comentario

Ten en cuenta que los comentarios deben aprobarse antes de que se publiquen.