Elemento C

Retrasos en la implementación y el entorno ingenuo (basado en Earle latch )

Diagrama de tiempo de un elemento C y una puerta OR inclusiva

Realización de la puerta mayoritaria del elemento C y la puerta OR inclusiva (a); Realizaciones propuestas por Maevsky (b), Tsirlin (c) y Murphy (d)

Implementaciones estáticas del elemento C de dos y tres entradas ^{[1] [2] [3]}

Implementaciones semiestáticas del elemento C de dos y múltiples entradas. ^{[4] [5] [6]} Para obtener una versión más rápida, consulte ^[7]

David cell (a) y sus implementaciones rápidas: nivel de puerta (b) y nivel de transistor (c) ^[8]

El elemento C de Muller ( puerta C , flip-flop de histéresis o, a veces, flip-flop coincidente , circuito de seguridad de dos manos ) es un pequeño bloque digital ampliamente utilizado en el diseño de circuitos y sistemas asíncronos . Ha sido especificado formalmente en 1955 por David E. Muller ^[9] y utilizado por primera vez en la computadora ILLIAC II . ^[10] En términos de la teoría de las celosías , el elemento C es un circuito distributivo semimodular, cuyo funcionamiento en el tiempo se describe mediante un diagrama de Hasse . ^{[11] [12] [13]}El elemento C está estrechamente relacionado con los elementos rendezvous ^[14] y join ^[15] , donde no se permite que una entrada cambie dos veces seguidas. En algunos casos, cuando se conocen las relaciones entre los retrasos, el elemento C se puede realizar como un circuito de suma de productos (SOP). ^{[16] [17]} Las técnicas anteriores para implementar el elemento C ^{[18] [19]} incluyen el disparador Schmidt , ^{[20] el} flip-flop Eccles-Jordan y el flip-flop del último punto móvil.

Tabla de verdad y supuestos de demora

Para dos señales de entrada, el elemento C se define mediante la ecuación , que corresponde a la siguiente tabla de verdad:${\displaystyle y_{n}=x_{1}x_{2}+(x_{1}+x_{2})y_{n-1}}$

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle y_{n}}$
0	0	0
0	1	${\displaystyle y_{n-1}}$
1	0	${\displaystyle y_{n-1}}$
1	1	1

Esta mesa se puede convertir en un circuito usando el mapa de Karnaugh. Sin embargo, la implementación obtenida es ingenua, ya que no se dice nada sobre los supuestos de retraso. Para comprender en qué condiciones es viable el circuito obtenido, es necesario hacer un análisis adicional, que revela que

• delay1 es un retardo de propagación desde el nodo 1 a través del entorno al nodo 3,
• delay2 es un retardo de propagación desde el nodo 1 a través de retroalimentación interna al nodo 3,
• delay1 debe ser mayor que delay2.

Por lo tanto, la implementación ingenua es correcta solo para entornos lentos. ^[21] La definición de elemento C se puede generalizar fácilmente para lógica de valores múltiples o incluso para señales continuas:

${\displaystyle {\text{ if }}x_{1}=x_{2}=...=x_{m},{\text{ then }}y_{n}={\text{any}}(x_{1},x_{2},...,x_{m}),{\text{ else }}y_{n}=y_{n-1}.}$

Por ejemplo, la tabla de verdad para un elemento C ternario balanceado con dos entradas es

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle y_{n}}$
−1	−1	−1
−1	0	${\displaystyle y_{n-1}}$
−1	1	${\displaystyle y_{n-1}}$
0	−1	${\displaystyle y_{n-1}}$
0	0	0
0	1	${\displaystyle y_{n-1}}$
1	−1	${\displaystyle y_{n-1}}$
1	0	${\displaystyle y_{n-1}}$
1	1	1

Implementaciones del elemento C

Dependiendo de los requisitos de velocidad de conmutación y consumo de energía, el elemento C se puede realizar como un circuito de grano grueso o fino. Además, se debe distinguir entre realizaciones de elemento C de salida única y diferencial ^[22] . La realización diferencial es posible utilizando solo NAND (solo NOR). Una realización de salida única es viable si y solo si: ^[23]

1. El circuito, donde cada entrada de un elemento C se conecta a través de un inversor separado a su salida, es semimodular en relación con el estado en el que todos los inversores están excitados.
2. Este estado está activo para la puerta de salida del elemento C.

Implementaciones a nivel de puerta

Hay varios circuitos diferentes de salida única de elemento C construidos sobre puertas lógicas. ^{[24] [25]} En particular, la llamada implementación de Maevsky ^{[26] [27] [28]} es un circuito no distributivo basado libremente en. ^{[29] A} veces se introduce la no distributividad para aumentar la concurrencia. La puerta 3NAND en este circuito se puede reemplazar por dos puertas 2NAND. El elemento C que utiliza sólo puertas de dos entradas ha sido propuesto por Tsirlin ^[30] y luego sintetizado por Starodoubtsev et al. utilizando lenguaje Taxogram ^[31] Este circuito coincide con el atribuido (sin referencia) a Bartky ^[26]y puede funcionar sin el pestillo de entrada. Murphy ^[32] ha sintetizado otra versión del elemento C construido sobre dos pestillos RS utilizando la herramienta Petrify. Sin embargo, este circuito incluye inversor conectado a una de las entradas. Este inversor debería tener un pequeño retraso. Sin embargo, hay realizaciones de pestillos RS que ya tienen una entrada invertida, por ejemplo. ^[33] Algunos enfoques independientes de la velocidad ^{[34] [35]} asumen que los inversores de entrada de retardo cero están disponibles en todas las puertas, lo cual es una violación de la verdadera independencia de la velocidad, pero es bastante seguro en la práctica. También existen otros ejemplos de uso de esta suposición. ^[36]

Implementaciones estáticas y semiestáticas

En su informe ^[9] Muller propuso realizar el elemento C como una puerta de mayoría con retroalimentación. Sin embargo, para evitar los peligros relacionados con las desviaciones de los retrasos internos, la puerta de la mayoría debe tener la menor cantidad de transistores posible. ^{[37] [38]} Generalmente, los elementos C con diferentes supuestos de temporización ^[39] se pueden construir en AND-OR-Invert (AOI) ^{[40] [41]} o en su puerta dual, OR-AND-Invert (OAI) ^{[ 42] [43]} e inversor. Otra opción más patentada por Varshavsky et al. ^{[44] [45]}es derivar las señales de entrada cuando no son iguales entre sí. Al ser muy simples, estas realizaciones disipan más energía debido a los cortocircuitos. Conectando una puerta mayoritaria adicional a la salida invertida del elemento C, obtenemos la función OR (EDLINCOR) inclusiva: ^{[46] [47]} . Algunos circuitos asíncronos simples, como los distribuidores de pulsos ^[48], pueden construirse únicamente en compuertas mayoritarias.${\displaystyle z_{n}=x_{1}x_{2}+(x_{1}+x_{2}){\overline {y_{n}}}}$

El elemento C semiestático almacena su estado anterior utilizando dos inversores de acoplamiento cruzado, similar a una celda SRAM . Uno de los inversores es más débil que el resto del circuito, por lo que puede ser dominado por las redes pull-up y pull-down . Si ambas entradas son 0, entonces la red pull-up cambia el estado del pestillo y el elemento C genera un 0. Si ambas entradas son 1, entonces la red pull-down cambia el estado del pestillo, lo que hace que el elemento C salida a 1. De lo contrario, la entrada del pestillo no está conectada ni a tierra ni a tierra, por lo que el inversor débil domina y el pestillo genera su estado anterior. También hay versiones de elemento C semiestático integradas en dispositivos con resistencia diferencial negativa (NDR). ^{[49] [50]}${\displaystyle V_{\text{dd}}}$NDR generalmente se define para señales pequeñas, por lo que es difícil esperar que dicho elemento C funcione en un rango completo de voltajes o corrientes. ^{[ investigación original? ]}

Generalizaciones e implementaciones sin transistores.

Dado que la puerta de la mayoría es un caso particular de puerta de umbral, cualquiera de las realizaciones conocidas de la puerta de umbral ^[51] puede utilizarse en principio para construir un elemento C. Sin embargo, en el caso de valores múltiples, conectar la salida de la puerta mayoritaria a una o varias entradas puede no tener un efecto deseable. Por ejemplo, utilizando la función de mayoría ternaria definida como ^[52]

${\displaystyle y={\begin{cases}+1&{\text{if}}\ x_{1}+x_{2}+x_{3}\geqslant +1,\\0&{\text{if}}\ x_{1}+x_{2}+x_{3}=0,\\-1&{\text{if}}\ x_{1}+x_{2}+x_{3}\leqslant -1\end{cases}}}$

no conduce al elemento C ternario especificado por la tabla de verdad, si la suma no se divide en pares. Sin embargo, incluso sin tal división, dos funciones mayoritarias ternarias son adecuadas para construir una puerta OR ternaria inclusiva. Tanto el circuito de Maevsky como el de Tsirlin se basan en realidad en la llamada celda de David. ^[53] Su rápida implementación a nivel de transistor se utiliza en el elemento C semiestático propuesto. ^{[54] Se} ha propuesto otro circuito semiestático que utiliza transistores de paso (en realidad, MUX 2: 1). ^[55] Otras tecnologías adecuadas para realizar primitivas asincrónicas, incluido el elemento C, son: nanotubos de carbono, ^{[ cita requerida ]} dispositivos de efecto túnel de un solo electrón, ^[56]${\displaystyle x_{1}+x_{2}+x_{3}}$puntos cuánticos, ^[57] y nanotecnología molecular. ^[58]

Referencias

1. IE Sutherland, "Micropipelines ", Comunicaciones de la ACM, vol. 32, no. 6, págs. 720–738, 1989.
2. CH van Berkel, "Cuidado con la bifurcación isocrónica" , Informe UR 003/91, Laboratorios de investigación de Philips, 1991.
3. VB Marakhovsky, Diseño lógico de circuitos asincrónicos . Diapositivas del curso. Departamento de CS&SE, SPbPU.
4. VI Varshavsky, NM Kravchenko, VB Marakhovsky, BS Tsirlin, "H flip-flop", certificado de autor de la URSS SU1562964, 5 de julio de 1990.
5. VI Varshavsky, "elementos de umbral impulsados ​​por β", IEEE Great Lakes Symposium sobre VLSI 1998, págs. 52-58.
6. VI Varshavsky, "Elemento de umbral y método de diseño del mismo", patente US6338157, 8 de enero de 2002.
7. YA Stepchenkov, YG Dyachenko, AN Denisov, YP Fomin, "H flip-flop", Patente RU2371842, 27 de octubre de 2009.
8. A. Bystrov, A. Yakovlev, Síntesis de circuitos asincrónicos por mapeo directo: Interfaz con el medio ambiente . Informe técnico, Departamento de informática, Universidad de Newcastle upon Tyne, octubre de 2001.
9. D. E. Muller, Teoría de circuitos asincrónicos . Reporte no. 66, Laboratorio de Computación Digital, Universidad de Illinois en Urbana-Champaign, 1955.
10. HC Breadley, "ILLIAC II - Una breve descripción y bibliografía comentada" , IEEE Transactions on Electronic Computers, vol. EC-14, núm. 3, págs. 399–403, 1965.
11. DE Muller y WS Bartky, "Una teoría de circuitos asincrónicos" , Int. Simposio sobre la teoría del cambio en la Universidad de Harvard, págs. 204–243, 1959.
12. WJ Poppelbaum, Introducción a la teoría de las máquinas digitales . Math., EE 294 Lecture Notes, Universidad de Illinois en Urbana-Champaign.
13. J. Gunawardena, "Una estructura de eventos generalizada para el despliegue de Muller de una red segura" , Int. Conferencia sobre teoría de la concurrencia (CONCUR) 1993, págs. 278-292.
14. MJ Stucki, SM Ornstein, WA Clark, "Diseño lógico de macromódulos" , en Proceedings of AFIPS 1967, págs. 357–364.
15. JC Ebergen, J. Segers, I. Benko, "Programa paralelo y diseño de circuitos asincrónicos" , Talleres de informática, págs. 50-103, 1995.
16. PA Beerel, JR Burch y TH Meng, "Comprobación de la equivalencia combinatoria de circuitos independientes de la velocidad", Métodos formales en el diseño de sistemas, vol. 13, no. 1, págs. 37-85, 1998.
17. H. Park, A. He, M. Roncken y X. Song, "Modelo de retardo semimodular revisitado en el contexto de la sincronización relativa" , IET Electronics Letters, vol. 51, no. 4, págs. 332–334, 2015.
18. Informe de progreso técnico, enero de 1959 , Universidad de Illinois en Urbana-Champaign.
19. W. J. Poppellbaum, NE Wiseman, "Diseño de circuito para la nueva computadora de Illinois" , Informe no. 90, Universidad de Illinois en Urbana-Champaign, 1959.
20. NP Singh, Metodología de diseño para sistemas automáticos . Tesis de maestría, MIT, 1981, 98 p.
21. J. Cortadella, M. Kishinevsky, Tutorial: Síntesis de circuitos de control a partir de especificaciones STG . Escuela de verano, Lyngby, 1997.
22. A. Mokhov, V. Khomenko, D. Sokolov y A. Yakovlev, "Sobre la lógica de control de doble carril para mejorar la robustez del circuito" , IEEE Int. Conferencia sobre la aplicación de la concurrencia al diseño de sistemas (ACSD) 2012, págs. 112–121.
23. BS Tsirlin, "Un estudio de los problemas equivalentes de realizar circuitos en la base Y-NO que son independientes de la velocidad", Revista soviética de Ciencias de la Computación y Sistemas, vol. 24, 1986, pp. 58-69 (Б. С. Цирлин, "Обзор эквивалентных проблем реализации схем в базисе И-НЕ, не зависящих от скорости" , Изв. АН СССР, кибернетика Техническая, №2, 1986, с. 159 –171).
24. BS Tsirlin, "H flip-flop" , certificado de autor de la URSS SU1096759, 7 de junio de 1984.
25. BS Tsirlin, "Flip-flop H de entrada múltiple" , certificado de autor de la URSS SU1162019, 15 de junio de 1985.
26. M. Kuwako, T. Nanya, "Evaluación de confiabilidad del tiempo de circuitos asincrónicos basados ​​en diferentes modelos de retardo" , Simposio internacional IEEE sobre investigación avanzada en circuitos y sistemas asincrónicos (ASYNC) 1994, págs. 22-31.
27. JA Brzozowski, K. Raahemifar, "Probar elementos C no es elemental" , Conferencia de trabajo sobre metodologías de diseño asincrónico (ASYNC) 1995, págs. 150-159.
28. PA Beerel, JR Burch, TH Meng, "Comprobación de la equivalencia combinatoria de circuitos independientes de la velocidad" , Métodos formales en el diseño de sistemas, vol. 13, no. 1, 1998, págs. 37–85.
29. VI Varshavsky, OV Maevsky, Yu. V. Mamrukov, BS Tsirlin, "H flip-flop" , certificado de autor de la URSS SU1081801, 23 de marzo de 1984.
30. BS Tsirlin, "H-flip-flop" , certificado de autor de la URSS SU1324106, 15 de julio de 1987.
31. NA Starodoubtsev, SA Bystrov, "Refinamiento del comportamiento monótono para la síntesis de circuitos asincrónicos de dos puertas de entrada" , IEEE Int. Simposio sobre circuitos y sistemas del Medio Oeste (MWSCAS) 2004, vol. I, págs. I-521-524.
32. JP Murphy, "Diseño de elemento C basado en pestillos" , Electronics Letters, vol. 48, no. 19, 2012, págs. 1190-1191.
33. VA Maksimov y Ya. Ya. Petrichkovich "RS flip-flop" , certificado de autor de la URSS SU1164867, 30 de junio de 1985.
34. P. Beerel y TH-Y. Meng. "Síntesis automática a nivel de puerta de circuitos independientes de la velocidad" , IEEE / ACM Int. Conferencia sobre diseño asistido por computadora (ICCAD) 1992, págs. 581–587.
35. A. Kondratyev, M. Kishinevsky, B. Lin, P. Vanbekbergen y A. Yakovlev, "Implementación de puerta básica de circuitos independientes de la velocidad" , Conferencia de automatización de diseño de ACM (DAC) 1994, págs. 56-62.
36. AV Yakovlev, AM Koelmans, A. Semenov, DJ Kinniment, "Modelado, análisis y síntesis de circuitos de control asincrónicos utilizando redes de Petri" , Integración, VLSI Journal, vol. 21, no. 3, págs. 143-170, 1996.
37. D. Hampel, K. Prost y N. Scheingberg, "Lógica de umbral mediante dispositivo MOS complementario" , patente US3900742, 19 de agosto de 1975.
38. D. Doman, Ingeniería de la biblioteca CMOS: mejora de los kits de diseño digital para el silicio competitivo Archivado el 8 de octubre de 2015 en Wayback Machine . Wiley, 2012, 327 p.
39. KS Stevens, R. Ginosar y S. Rotem, "Tiempo relativo [diseño asincrónico]" , Transacciones IEEE en sistemas de integración a gran escala (VLSI), vol. 11, no. 1, págs. 129–140, 2003.
40. H. Zemanek, "Sequentielle asynchrone Logik" , Elektronische Rechenanlagen, vol. 4, no. 6, págs. 248-253, 1962. También disponible en ruso como Г. Цеманек, "Последовательная асинхронная логика" , Mеждународный симпозиум ИФАК Теория конечных и верия конечных и нсоямы вероый. 232—245.
41. W. Fleischhammer, "Mejoras en o en relación con los circuitos de disparo biestables asincrónicos" , especificación de patente del Reino Unido GB1199698, 22 de julio de 1970.
42. T.-Y. Wuu y SBK Vrudhula, "Un diseño de un elemento C de Muller de múltiples entradas rápido y eficiente en el área" , IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 1, no. 2, págs. 215-219, 1993.
43. HKO Berge, A. Hasanbegovic, S. Aunet, "Elementos C de Muller basados ​​en funciones minoritarias-3 para suministros de voltaje ultra bajo" , IEEE Int. Simposio sobre diseño y diagnóstico de circuitos y sistemas electrónicos (DDECS) 2011, págs. 195–200.
44. VI Varshavsky, AY Kondratyev, NM Kravchenko y BS Tsirlin, "H flip-flop" , Certificado de autor de la URSS SU1411934 23 de julio de 1988.
45. VI Varshavsky, NM Kravchenko, VB Marakhovsky y BS Tsirlin, "H flip-flop" , Certificado de autor de la URSS SU1443137, 7 de diciembre de 1988.
46. DA Pucknell, " Enfoque de lógica impulsada por eventos (EDL) para la representación de sistemas digitales y procesos de diseño relacionados" , IEE Proceedings E, Computers and Digital Techniques, vol. 140, no. 2, págs. 119-126, 1993.
47. A. Yakovlev, M. Kishinevsky, A. Kondratyev, L. Lavagno, M. Pietkiewicz-Koutny, "Sobre los modelos para el comportamiento del circuito asincrónico con causalidad OR" , Métodos formales en el diseño de sistemas, vol. 9, no. 3, págs. 189-233. 1996.
48. JC Nelson, circuitos de conteo independientes de la velocidad . Reporte no. 71, Laboratorio de Computación Digital, Universidad de Illinois en Urbana-Champaign, 1956.
49. C.-H. Lin, K. Yang, AF González, JR East, P. Mazumder, GI Haddad, "Puertas lógicas digitales de alta velocidad basadas en InP que utilizan una heteroestructura RTD / HBT" , Int. Conferencia sobre fosfuro de indio y materiales relacionados (IPRM) 1999, págs. 419–422.
50. P. Glosekotter, C. Pacha, KF Goser, W. Prost, S. Kim, H. van Husen, et al., "Diseño de circuito asíncrono basado en el elemento de transición lógica monoestable-biestable RTBT (MÓVIL)" , Simposio integrado Diseño de circuitos y sistemas 2002, págs. 365–370.
51. V. Beiu, JM Quintana, MJ Avedillo, "Implementaciones VLSI de lógica de umbral - Una encuesta completa" , IEEE Transactions on Neural Networks, vol. 14, no. 5, págs. 1217-1243, 2003.
52. V. Varshavsky, B. Ovsievich, "Redes compuestas por elementos de mayoría ternaria" , IEEE Transactions on Electronic Computers, vol. EC-14, núm. 5, págs. 730–733, 1965.
53. M. Courvoisier y P. Azema, "Máquinas secuenciales asíncronas con modo de funcionamiento de solicitud / reconocimiento", IEE Electronics Letters, vol. 10, no. 1, págs. 8-10, 1974.
54. SM Fairbanks, "Elemento C de Muller de dos etapas" , Patente de Estados Unidos US6281707, 28 de agosto de 2001.
55. A. Morgenshtein, M. Moreinis, R. Ginosar, "Circuitos de entrada de difusión de puerta asincrónica (GDI)" , Transacciones IEEE en sistemas de integración a gran escala (VLSI), vol. 12, no. 8, págs. 847–856, 2004.
56. S. Safiruddin, SD Cotofana, "Bloques de construcción para circuitos insensibles al retardo que utilizan dispositivos de túnel de un solo electrón" , Conferencia IEEE sobre nanotecnología 2007, págs. 704–708.
57. VI Varshavsky, "Diseño lógico y desafío cuántico" , Int. Taller sobre física y modelado informático de dispositivos basados ​​en estructuras de baja dimensión 1995, págs. 134-146.
58. AJ Martin, P. Prakash, "Nanoelectrónica asincrónica: investigación preliminar" Archivado el 4 de marzo de 2016 en la Wayback Machine , IEEE Int. Simposio sobre circuitos y sistemas asincrónicos (ASYNC) 2008, págs. 58–68.

enlaces externos

• Herramienta de trabajo: síntesis y verificación del elemento C