Diseño de circuitos con álgebra de interruptores
Volvemos de nuevo al trabajo del Dr. Claude E. Shannon, esta vez a su tesis de maestría sobre el diseño de interruptores de relé. Esta tesis introdujo cambiando álgebra esto permite el diseño sistemático y la optimización de circuitos lógicos. Si bien el trabajo de Shannon se ha aplicado a interruptores y relés, es igualmente aplicable a todas las formas modernas de circuitos digitales. Su disertación recibió amplia atención cuando se publicó como "Análisis simbólico de circuitos de relés y conmutadores" en 1938. Este trabajo se basó en el álgebra de Boole desarrollada por George Boole y un análisis de la lógica de Augustus De Morgan, que estos matemáticos publicaron casi simultáneamente en 1847. Hasta cierto punto, fue el comienzo de la era de la lógica digital moderna.
Reglas básicas
Cambiar álgebra es fácil de ver con interruptores, ya que solo hay dos valores: plu y fuera de, o cierto y falso. En los sistemas digitales los representamos como 1 y 0, respectivamente. Solo hay dos reglas que crean la base del álgebra. La primera regla es la NO operación, o negado. Matemáticamente esto es:
Físicamente, un normalmente abierto (NO) y un normalmente cerrado (NC) switch son negaciones entre sí. Cuando un interruptor NO está representado por el símbolo X, un interruptor NC se representaría como X ', donde el apóstrofe indica la negación.
Interruptores normalmente cerrados y normalmente abiertos
A y FUNCIONAMIENTO CON INTERRUPTORES
La segunda regla se puede expresar de dos formas diferentes. Una forma es la Y operación, o conunión, mientras que el otro es el UNA., o disyunción. Formalmente estas operaciones son:
Los diagramas de interruptores ayudan a explicar estas reglas, pero ahora pasaremos a las puertas lógicas para usar una representación más moderna.
Tabla verdadera NO, OR y KA
Las matrices verdaderas son una representación que define el funcionamiento de un sistema. Esta matriz verdadera muestra cómo se relacionan Y y O, porque si niega una de las columnas y la invierte de arriba a abajo, obtiene los valores en la otra. La expresión formal de esta relación es:
Dado que cada una de estas operaciones se puede derivar entre sí, solo se necesita una como segunda regla en el álgebra de cambio. Los operadores AND y OR, representados por '•' y '+', son análogos a la multiplicación y la suma y siguen las mismas reglas para conmutación, asociación y distribución. Tenga en cuenta que así como a menudo omitimos el operador de multiplicación en aritmética, el operador Y también se puede omitir al vincular las variables utilizadas en las expresiones. Aquí están las matemáticas que muestran la relación entre estas operaciones:
Uno de los objetivos del álgebra de cambio es utilizar las matemáticas para reducir los circuitos, representados por expresiones, a su forma más simple o, en algunos casos, utilizando puertas lógicas específicas. Hay identidades matemáticas y reglas de simplificación que los diseñadores pueden usar para lograr esta refactorización.
Las identidades algebraicas que se pueden utilizar en la refactorización son:
A continuación, se muestran algunas reglas de simplificación útiles para volver a facturar:
La última consideración importante es la prioridad de las operaciones. Nuevamente, parecen aritmética normal:
- Izquierda derecha
- Complemento (NO)
- Y
- UNA.
Sachleen dice:
En su primera ecuación de conjunción / disyunción, los símbolos se cambian. El punto debe estar con AND y el + con OR.
Rud Merriam dice:
Reparado. Tienes razón, los símbolos estaban mal.
tlvb dice:
La afirmación de cuándo se cambia la verdad. Sea Disyunción: = 1 a menos que x = y = 0 en cuyo caso = 0, y Conjunción: = 0 a menos que x = y = 1 en cuyo caso = 1
Stan dice:
Hay una agradable clase en línea de Coursera que se ocupa de esto y mucho más llamada VLSI CAD: Logic to Layout. Un agradecimiento a Rob A. Rutenbar y la Universidad de Illinois en Urbana-Champaign por animar este curso. Me inscribí tarde como curiosidad, pero espero que lo recoja para obtener un certificado.
pff dice:
¿Cuál fue el propósito de extraer el mapa de karnaugh para el que no lo usará?
pff dice:
el punto del km es ayudar a simplificar
tome la tabla, hay dos grupos, los tres 1 en la fila inferior y los dos 1 en la tercera columna, puede decir que ya para el primer grupo (x y (y o z)) porque está en la fila x es x y, dado que cubre y o z, es x e y o z, el segundo grupo puede decir y y z (cubrimos x 1 y 0, por lo que se ignora). para que pueda sus grupos (expresiones) == (x y (y o z)) o (x e y)
el método matemático (aburrido) de volver a facturar se puede hacer sin el mapa simplemente usando la matriz real.
el problema del grupo funciona debido al código gris que se usa en lugar del binario "normal", que es literalmente para lo que se inventaron los mapas de karnaugh. ustedes me joden, ¿no?Grapa dice:
Sí, son el rey contigo.
Utilizaron la tabla real para hacer una suma estándar de la forma del producto. Se demuestra fácilmente que cada "1" en el mapa K es un producto estándar y que el cartel debería haber realizado la minimización gráfica de C en lugar de la refacturación matemática (desafortunadamente, una suma no podría ser más fácil si el lector no reconoce la XOR directamente desde el K-map).Estoy un poco decepcionado de que el contador completo no esté compuesto por dos medias adiciones y un "Y". Reutilizar módulos más pequeños es una forma mucho mejor y más fácil de hacer las cosas.
Fuente: Doy clases de Circuitos Digitales en un politécnico local.
echodelta dice:
Las matemáticas y los números me dejan frío, pero este tema me deja con el cero absoluto. Veo ambos estados al mismo tiempo porque no puedo pensar en un nivel de bits.
Dan # 9445376854 dice:
Eso tiene el hedor de un troll, pero compartiré esto contigo de todos modos.
Puede aprender a visualizar simultáneamente todas las operaciones lógicas posibles con 2 entradas y 1 salida a través de su combinación con 4 puertos selectores de puerta.
Se parece a esto:
¿Puedes pensar en otra forma de mostrarlo?
Dan # 9445376854 dice:
Curiosamente, una imagen puede estar dañada.
aquí está de nuevo.
TheRegnirps dice:
Diablos con Karnaugh Maps. Todos necesitan algo en lo que perder más tiempo. https://en.wikipedia.org/wiki/Laws_of_Form
Stefano dice:
Por qué en llamas azules las personas que inventaron esto eligieron reutilizar símbolos matemáticos predefinidos. Entendí la lógica bastante bien, pero tener que traducirla constantemente apestaba. Mi cerebro ya está entrenado para reconocer automáticamente esos símbolos. ... Ahora recuerden personas, los recursos morados permanecen ahora y los recursos negros. ! Gusta.
Steven J. Greenfield dice:
¿Cuándo dejamos de llamarlo álgebra booleana? ¡Y cuando dejamos de consumir! ¿A para significar NO A y cambió a usar A '?
Rud Merriam dice:
El álgebra booleana es más válida en general que para el diseño de circuitos de intercambio. Shannon lo llamó álgebra de cambio, así que seguí su uso.
El uso del apóstrofe es el uso clásico para el diseño de circuitos como lo presenta Shannon en su trabajo original. La exclamación es sobre lenguajes de programación. También existe la convención en el análisis de circuitos de una línea horizontal sobre la variable o expresión.
Paul dice:
No olvides la tilde, conoce a los del set que usamos para programar GAL, PAL, CPLD
Stefano dice:
Es posible que desee devolver esto con simbología moderna, con solo una referencia de pasada al método original. A menos que esto solo tuviera como objetivo una lección de historia.
Rud Merriam dice:
¿Qué es el simbolismo moderno? Supongo que este material del curso es moderno y si sigue el símbolo que usé: https://cseweb.ucsd.edu/classes/sp08/cse140/lectures/wk1d2.pdf
Cada uno de nosotros encuentra estos materiales de una variedad de materiales de origen. Simplemente no están de acuerdo en la representación de la negación. Encontrará el apóstrofe ('), el signo de exclamación posterior (A!), El signo de exclamación principal (! A), el signo de exclamación principal (~ A), la barra superior, la cola discontinua (¬A) e incluso solo un signo menos (-A).
PúrpuraTurdoSoporte dice:
Nada le impide producir una versión adecuada y luego enviarla usted mismo. La forma más rápida de hacerlo es utilizar su editor favorito y convertir la página al formato .PNG, si es necesario, a través de PDF. Luego, puede cargar esa imagen de la página en un host de imágenes gratuito y agregar la URL a sus comentarios para que todos puedan ver la página. De lo contrario, siempre existe la ruta de edición más formal que HABÍA, en cualquier caso no hay excusa para simplemente criticar y criticar de una manera que no es constructiva o útil. . ... ... .. .. ..…. …. ..…. . ...
La prioridad está menos definida para los circuitos lógicos, como XOR o NAND, que provienen de los tres circuitos básicos. Es mejor utilizar un corchete para explicar el orden de las operaciones cuando se utilizan estas operaciones.
Utilizando el álgebra de Boole como álgebra de cambio, los circuitos complejos se expresan para que puedan estimarse matemáticamente. Esto aumentó rápidamente la productividad de los ingenieros que diseñaban circuitos de interruptores, algunos de los cuales se usaban en computadoras.
Mitad víbora
Apliquemos el álgebra de cambios al diseño de una media víbora, un circuito central en las CPU. 
Un sumador promedio toma dos entradas binarias y genera dos salidas. Una salida es la suma de las entradas, mientras que la otra se transporta a la siguiente etapa. La verdadera tabla muestra los resultados deseados.
La salida de transferencia es, obviamente, Y de las dos entradas. Eso facilita el diseño.
La cantidad se puede generar de diferentes formas dependiendo de los circuitos que el diseñador quiera usar. Veamos un enfoque que utiliza compuertas OR, NAND y AND. Una verdadera matriz con columnas para cada paso ayuda al análisis. La columna OR muestra los resultados de esa operación en X e Y. Luego está el resultado NAND en X e Y. La columna final es Y de las columnas OR o NAND que producen la suma deseada.
Tabla verdadera de sumador medio
Víbora de la primera mitad
Podemos expresar esto matemáticamente como:
Podemos simplificar el circuito volviendo a facturar las matemáticas para reutilizar C para calcular S. Para hacer esto, se elimina el NAND y la salida de C negada por una puerta NOT se pasa como entrada al AND final del circuito. El semi-vendedor es ahora:
Podemos reducir considerablemente el recuento de puertas introduciendo una puerta XOR para suministrar directamente la operación de suma. La operación XOR está representada por el símbolo matemático '⊕' en las ecuaciones. El semi-vendedor ahora usa solo 2 puertas y aparece matemáticamente como:
Estas diferentes implementaciones de una media víbora ilustran las ventajas obtenidas durante el diseño del circuito. Los circuitos integrados contienen múltiples puertas de tipo, por ejemplo, puertas NAND. Si tiene puertas libres en un IC, usarlas para un circuito en lugar de agregar otro IC, como XOR, ahorra dinero y una placa en un proyecto.
Mapas completos de Adder y Karnaugh
Un proyector útil es el Mapa de Karnaugh elaborado por Maurice Karnaugh en 1953. Este mapa es otra forma de una verdadera matriz que es útil para extraer las relaciones matemáticas entre los valores de entrada y salida. La tabla se construye enumerando los valores de entrada a lo largo del eje superior e izquierdo con los valores de salida en el cuerpo de la tabla. Usaremos mapas para dibujar un contador completo con más rigor del que normalmente se proyecta a la mitad.
Un contador completo tiene las mismas dos entradas X e Y, pero también un transporte de entrada, Cin, enviado desde la etapa anterior. Los resultados son los mismos, la suma, S, y el acarreo de salida, C. Para facilitar y eliminar la confusión entre los dos, representaremos Cin por Z en este análisis.
Tabla de verdad de sumadora completa
Mapa completo de Adder Karnaugh
Con la matriz verdadera definida, podemos construir dos mapas de Karnaugh, uno para la suma y otro para el rumbo. Los valores de X corren a lo largo del lado izquierdo, mientras que en la parte superior son los valores de Y y Z. Tenga en cuenta que los valores de Y y Z están en el orden 00, 01, 11, 10 (0, 1, 3, 2). Cuando se enumeran varias entradas, la secuencia solo puede cambiar un bit por cada columna o fila. Esto se llama Código gris.
El cuerpo del mapa se completa copiando los valores resultantes de las entradas. Por ejemplo, en el mapa de resumen cuando X = 1, Y = 0 y Z = 1, el resultado es 0. El resultado del puerto para las mismas entradas es 1.
Para comenzar el análisis matemático escribimos las expresiones booleanas para las celdas que contienen 1. Usando los mismos valores X, Y, Z de 1, 0 y 1, escribimos una expresión para esta celda, porque el resultado en la tabla carry es 1. No escribimos una expresión para la tabla de suma porque su celda es 0. Las sub-expresiones para las celdas de cada tabla se combinan con OR en una expresión para cada tabla. Las expresiones para la suma y el acarreo son:
Centrándonos en la suma, la refacturación comienza factorizando X 'de las dos primeras subexpresiones:
Entonces, con base en materiales de referencia, sabemos que la expresión (Y'Z + YZ ') es un XOR de Y y Z. Haciendo ese cambio y teniendo en cuenta X en las dos últimas sub-expresiones obtenemos:
De nuevo, según las referencias, sabemos que (Y'Z '+ YZ) es equivalencia, una operación lógica que normalmente no usamos. Su valor es 1 cuando los operandos son iguales, que es la negación de XOR que es 1 cuando los operandos son desiguales. Los siguientes dos pasos se rehacen para la equivalencia y convierten la equivalencia en XOR denegado.
Simplifiquemos la expresión reemplazando K con (Y ⊕ Z) para aclarar el siguiente paso.
Esta forma simplificada nos deja ver que nuevamente tenemos XOR. Reajustamos para usar el operador XOR y reemplazamos K con su valor original.
Esta es la expresión final para la suma que se sabe que es verdadera, porque cualquier XOR de múltiples entradas es 1 cuando hay un número impar de entradas. Sin embargo, existe cierta disputa sobre esta interpretación de gran parte de la entrada XOR.
Volviendo a la expresión de transporte, repetida aquí, reorganizamos la expresión y calculamos Z en las dos primeras subexpresiones. Aquí nuevamente hay una operación XOR, así que hacemos esa refactorización.
Ahora calcule XY a partir de las dos últimas expresiones. De las identidades enumeradas anteriormente, sabemos que la subexpresión (Z + Z ') siempre es 1, por lo que se puede eliminar. Esto complementa las matemáticas para la expresión de transporte. La expresión de suma se repite, podemos examinar ambas expresiones finales.
Obviamente, podemos usar la expresión (X ⊕ Y) para ambos cálculos en el diagrama lógico. Ahora tenemos el circuito de proyección final completo.
Por muy bonito que parezca este diseño, no es práctico como acumulador, p. Ej. Regístrese para agregar muchos bits a la vez. Si desea agregar un número de 32 bits, necesita uno de estos circuitos para cada bit. La entrada de entrada a un circuito proviene del siguiente bit inferior. Una vez que se afirman X e Y para los 32 bits, el transporte del bit menos significativo se extiende al siguiente bit superior. A su vez, este cojinete se extiende hacia arriba y esto se repite hasta que los 32 circuitos se hayan estabilizado. La propagación a través de los 32 circuitos dura un tiempo relativamente largo. Una batería en paralelo de varios bits moderna está diseñada inicialmente como un circuito único para lograr un funcionamiento a alta velocidad.
Tal diseño fue útil al mismo tiempo y podría serlo hoy en un sistema con límites de espacio y energía. Algunas de las primeras computadoras realizaban operaciones, además, en flujos de datos en serie en lugar de las operaciones paralelas actuales. Dos registros de cambio, cada uno con uno de los valores de entrada X o Y, se cambiarían a través de este contador con el rumbo retenido durante el siguiente período de cambio. El resultado total se cambiaría a otro registro, o quizás al registro X, para mantener el resultado.
Envoltura
El álgebra cambiante o booleana no se limita al diseño de hardware. Los lenguajes de programación modernos proporcionan variables booleanas y estas técnicas son igualmente aplicables. Por supuesto, los compiladores refactorizarán un poco para optimizar las expresiones booleanas, pero la cantidad de mejora es incierta. Si se requiere una decisión lógica compleja, puede ser útil aplicar estas técnicas.
Un recurso importante, que utilicé en la preparación, es el sitio web WolframAlpha, que me permitió validar las expresiones matemáticas. Con expresión, el sitio genera la matriz verdadera, refacturación múltiple por diferentes operadores, diagrama y otra información sobre la entrada. La matriz verdadera me permitió verificar que mis expresiones iniciales y factoriales generaron el resultado deseado.
Otro enlace a información sobre el cambio de álgebra que puede resultarle interesante es Aplicaciones del álgebra booleana: Claude Shannon y diseño de circuitos: un resumen del cambio de álgebra. También hice referencia al sitio web All About Circuits, Capítulo 7: Introducción al álgebra booleana a través del artículo para dar un trasfondo a un tema. Todo el sitio web es una referencia útil para el pirata informático.
Este es el cuarto artículo relacionado con Shannon que escribí. Los dos primeros artículos tocaron un artículo que publicó en 1948, que creó el campo de la teoría de la información. El primero abordó su análisis de la cantidad de información que se puede transmitir infaliblemente a través de un canal de comunicación. Este trabajo ha llevado a investigar cómo lograr el máximo rendimiento utilizando técnicas de corrección erróneas, tema de mi segundo artículo. La fiesta de cumpleaños del centenario de Shannon se llevó a cabo el 30 de abril y también recibió un artículo.
Esto concluye la gira de Shannon para mí, pero no de todas sus obras, ni de todo el trabajo que otros han hecho para su brillantez. Hay muchos artículos por escribir sobre teoría de la información y comunicaciones y es posible que regrese con algunos de ellos.
