¿Cuál es la cantidad mínima de 1bit Full Adders requerida para implementar la ecuación 4X + 3Y + 13?

6

Usando 1bit FA s y 0 / 1 constants, mientras que X(x1,x2,x3) y Y(y1,y2,y3) son 3 bits cada uno.

Es posible implementarlo fácilmente con 7FA, y también hay una solución con 6FA.

¿Hay una solución con 5 o menos? Si no, ¿por qué? ¿Hay alguna forma sistemática de resolver tales problemas?

Así es como analizo el problema:

0  x1  x2  x3   0  0
0   0  y1  y2  y3  0
0   0   0  y1  y2 y3
0   0   1   1   0  1
====================
z1 z2  z3  z4  z5 z6

Aquí hay una tabla de verdad que hice para el problema.

Actualmente, he llegado a la conclusión de que:

z6 = ~y3
z5 = y2
z4 = ~(x3 XOR y1 XOR y2 XOR y3)

Pero no estoy seguro de lo útil que sea.

    
pregunta Dvir Azulay

3 respuestas

2

El problema está en \ $ z_4 \ $. Desea agregar cuatro bits, que podrían hacer 100 , por lo que tendría que ir a \ $ z_2 \ $ con el carry.

Hay un enfoque normal , donde ves 13 como una variable como xey, así que básicamente esto es capaz de resolver ecuaciones \ $ 4x + 3y + a \ $ con \ $ a = (a_1, a_2,0, a_4) \ $. En este enfoque, puede calcular fácilmente la cantidad de sumadores completos necesarios trabajando de derecha a izquierda:

  • En \ $ z_6 \ $ agrega dos bits, por lo que necesita 1 sumador.
  • En \ $ z_5 \ $ agrega dos bits y el carry \ $ c_6 \ $ from \ $ z_6 \ $, por lo que necesita 1 sumador.
  • En \ $ z_4 \ $ agregas cuatro bits y \ $ c_5 \ $, por lo que necesitas 2 sumadores.
  • En \ $ z_3 \ $ agregas tres bits y dos se lleva, por lo que necesitas 2 sumadores.
  • En \ $ z_2 \ $ agrega un bit y dos , por lo que necesita 1 sumador.
  • En \ $ z_1 \ $ solo 'agregarías' el carry, lo que hace 0 sumadores.

Esto requiere 7 sumadores.

Sin embargo , dado que 13 no es realmente una variable sino una constante, es posible que puedas hacer algo inteligente. En ese caso, puede trabajar desde la configuración normal para \ $ 4x + 3y \ $:

  • \ $ z_6 = y_3 \ $ (1 bit, 1 sumador, 2 bits abierto)
  • \ $ z_5 = c_6 + y_3 + y_2 \ $ (3 bits, 1 sumador, 0 bits abierto)
  • \ $ z_4 = c_5 + y_2 + y_1 + x_3 \ $ (4 bits, 2 sumadores, 2 bits abiertos)
  • \ $ z_3 = c_ {4_1} + c_ {4_2} + y_1 + x_2 \ $ (4 bits, 2 sumadores, 2 bits abiertos)
  • \ $ z_2 = c_ {3_1} + c_ {3_2} + x_1 \ $ (3 bits, 1 sumador, 0 bits abierto)
  • \ $ z_1 = c_2 \ $ (1 bit, 0 sumadores, 0 bits abiertos)

Sin embargo, esta configuración básica para \ $ 4x + 3y \ $ ya requiere 7 sumadores. Como \ $ z_4 \ $ usa dos sumadores, tendrás dos acarreos que debes agregar a \ $ z_3 \ $, lo que hace que tengas también dos sumadores, y por lo tanto dos acarreos.

Podría ser posible hacer algo inteligente para perder un sumador, pero no va a funcionar con 5 sumadores, y aquí es por qué:

\ $ z_1 \ $ es solo un desbordamiento y no requiere sumadores. \ $ z_2 \ $ a través de \ $ z_6 \ $, sin embargo, se necesitan complementos. Esto hace 5 sumadores. Ahora, necesita al menos dos sumadores en \ $ z_4 \ $, ya que está agregando \ $ x_3 \ $, \ $ y_2 \ $, \ $ y_1 \ $ y el acarreo desde \ $ z_5 \ $, \ $ c_5 \ $. Entonces, en \ $ z_4 \ $ tienes que agregar cuatro bits, lo que hace que necesites dos sumadores en lugar de uno, haciendo que el total al menos 6.

Tenga en cuenta que necesita al menos 6 para la ecuación simplificada , \ $ 4x + 3y \ $, por lo que no es relevante si puede hacer algo inteligente con el 13 o no, este es el configuración básica y necesitará al menos 6 sumadores para ello.

    
respondido por el Keelan
2

Bueno, para considerar su pregunta básica: ¿cuál es el número mínimo de sumadores completos requeridos?

Inicialmente tienes doce productos parciales (bits), mientras que tu resultado tiene seis. Cada sumador completo totalmente utilizado eliminará un producto parcial (bit) y, por lo tanto, necesita exactamente 12 - 6 = 6 sumadores completos. Entonces, dado que no usa los medios sumadores, en la práctica puede haber más. Las formas de solucionar esto son recodificar los bits y / o simplificar algunos cálculos para no usar sumadores completos (como usted dice, algunas entradas son constantes).

Aquí hay una solución alternativa:

Reescriba 3Y como 4Y-Y, lo que lleva a (a 'denotando no (a))

 0  x1  x2  x3   0   0
 0  y1  y2  y3   0   0
y1' y1' y1' y1' y2' y3'  -- Sign-extend, invert and add a one at the LSB position
 0   0   0   0   0   1   
 0   0   1   1   0   1

La extensión de signo se puede reescribir como

 0  x1  x2  x3   0   0
 0  y1  y2  y3   0   0
 0   0   0  y1 y2' y3'  -- Sign-extend, invert and add a one at the LSB position
 1   1   1   1   0   0  -- In two's complement one can use this trick to avoid the negative sign bit -b = 1-b'
 0   0   0   0   0   1   
 0   0   1   1   0   1

Esto ahora resulta en:

 0  x1  x2  x3   0   0
 0  y1  y2  y3   0   0
 0   0   0  y1  y2' y3'
 0   0   1   0   1   0 

Ahora, hay once productos parciales, pero dos de ellos están invertidos. Además, como la segunda columna menos significativa contiene solo dos productos parciales, tendremos que emplear un sumador completo adicional, a pesar de que la mitad del sumador sea suficiente.

Mirando y2 '+ 1, el bit de suma se convierte en (y como has notado) y2, mientras que el bit de acarreo se convierte en y2'. Por lo tanto, no se necesita una adición completa. Esto te deja con

 0  x1  x2  x3   
 0  y1  y2  y3   
 0   0   1  y1     
 0   0   0  y2' 
----------------------
z1  z2  z3  z4  y2  y3' 

y nueve productos parciales que producen un resultado con cuatro bits, es decir, cinco sumadores completos.

Para salirse con el inversor, uno puede reescribir esto como (usando 2y2 + y2 '= 1 + y2)

 0  x1  x2  x3   
 0  y1   1  y3   
 0   0   0  y1     
 0   0   0  y2
 0   0   0   1 
----------------------
z1  z2  z3  z4  y2  y3' 

aunque no cambiará el número de sumadores completos.

Ahora, si desea guardar un sumador completo más, puede recodificar algunos de los bits en algo posiblemente "más fácil". Considere los productos parciales

0  y1   1  y1   
0   0   0   1     

Que es la expresión 5y1 + 3. Por lo tanto, la tabla de verdad para esta parte es

y1   result  binary
---------------------
 0      3     0011
 1      8     1000

Esto lleva a que podemos cambiar estos cuatro productos parciales a los siguientes tres

y1  x1  x2  x3   
 0   0  y1' y3   
 0   0   0  y2    
 0   0   0  y1'    
----------------------
z1  z2  z3  z4  y2  y3' 

dando como resultado ocho productos parciales, pero aún así cinco sumadores completos (de los cuales, dos computadores z1 y z2 se pueden hacer medio sumadores).

    
respondido por el Oscar
1

Puedes hacer esto con 5 sumadores completos y 1 Sin compuerta.

Z6 y z5 se pueden implementar de la forma que has descrito. Para z4 hasta z1 , deberá usar fulladders. Para empezar, descubramos el acarreo que va a la columna de z4 (déjame llamar a este Ci4 ). Esto es igual a y3 , por lo que no se requiere hardware adicional para generar esto.

Necesitamos agregar 5 números ( Ci4 , x3 , y2 , y1 y 1 ) para obtener z4 . Esto requerirá 2 sumadores completos (feed Ci4 , x3 y y2 en el primer fulladder para generar una suma intermedia S4x , luego alimente esta suma junto con y1 y 1 para el segundo sumador completo ). Ahora, los dos fulladders generarán 2 acarreos (permítanme llamarlos Ci3a y Ci3b ), que alimentaremos la siguiente etapa ( z3 ).

Para z3 también tenemos que sumar 5 números ( x2 , y1 , 1 , Ci3a y Ci3b ). Utilice el mismo enfoque que hicimos para z4 (agregue 3 señales y agregue la suma intermedia con las dos restantes). Esta etapa nos dejará con dos acarreos generados Ci2a y Ci2b .

Para la columna de z2, solo tenemos una entrada x1 , junto con Ci2a y Ci2b . Necesitamos solo un sumador completo para manejar estas 3 entradas. La suma generada por este sumador completo será z2 y su acarreo será z1 .

Puede, quizás, echar un vistazo a los multiplicadores de hardware, particularmente la etapa que agrega los productos parciales modificados.

    
respondido por el nav

Lea otras preguntas en las etiquetas