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

Question

El uso de 1bit FAs y 0/1 constantes, mientras que X(x1,x2,x3) y Y(y1,y2,y3) son 3bit cada uno.

Es posible implementar fácilmente con 7FA, y no hay una solución con 6FA así.

Hay una solución con 5 o menos? Si no, ¿por qué? Es allí cualquier manera sistemática para resolver este tipo de problemas?

Esta es la forma en que me descomponer 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 para el problema.

Actualmente, tengo 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 es.

Answer 1

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

Hay una normal de enfoque, donde se ve 13 como una variable como x e y, así que, básicamente, este es capaz de resolver ecuaciones \$4x+3y+a\$\$a = (a_1,a_2,0,a_4)\$. En este enfoque, usted puede calcular fácilmente el número de sumandos necesarios trabajando desde la derecha a la izquierda:

• En \$z_6\$ agregar dos bits, por lo que requieren de 1 adder.
• En \$z_5\$ agregar dos bits y la llevar \$c_6\$ a partir de \$z_6\$, por lo que requieren de 1 adder.
• En \$z_4\$ agregar cuatro bits y \$c_5\$, por lo que requieren de 2 sumandos.
• En \$z_3\$ agregar tres bits y dos lleva, por lo que requieren de 2 sumandos.
• En \$z_2\$ agregar un bit y dos lleva, por lo que requieren de 1 adder.
• En \$z_1\$ que solo en "añadir" de la maleta, lo que hace que 0 serpientes.

Esto requiere de 7 serpientes.

---

Sin embargo, debido a que el 13 no es realmente una variable, sino una constante, usted podría ser capaz de hacer algo inteligente. En ese caso, se puede trabajar desde la instalación normal de \$4x+3y\$:

• \$z_6 = y_3\$ (1 bit, 1 serpiente, 2 bits abierto)
• \$z_5 = c_6 + y_3 + y_2\$ (3 bits, 1 serpiente, los bits 0 abiertas)
• \$z_4 = c_5 + y_2 + y_1 + x_3\$ (4 bits, 2 sumandos, 2 bits abierto)
• \$z_3 = c_{4_1} + c_{4_2} + y_1 + x_2\$ (4 bits, 2 sumandos, 2 bits abierto)
• \$z_2 = c_{3_1} + c_{3_2} + x_1\$ (3 bits, 1 serpiente, los bits 0 abiertas)
• \$z_1 = c_2\$ (1 bit, 0 víboras, los bits 0 abiertas)

Sin embargo, esta configuración básica para \$4x+3y\$ ya requiere 7 serpientes. Desde \$z_4\$ utiliza dos sumandos, usted tendrá dos lleva a que tienes que añadir a \$z_3\$, lo que hace que tiene dos víboras así - y por lo tanto dos lleva.

Podría ser posible hacer algo inteligente para perder una serpiente, pero no va a trabajar con un 5 sumandos, y aquí es por qué:

---

\$z_1\$ es sólo un desbordamiento y no requiere complementos. \$z_2\$ a través de\$z_6\$, sin embargo, no son complementos necesarios. Esto hace 5 complementos. Ahora, usted necesita por lo menos dos sumandos en \$z_4\$, debido a que está añadiendo \$x_3\$, \$y_2\$, \$y_1\$ y el llevar de \$z_5\$, \$c_5\$. Así que a \$z_4\$ tienes que añadir cuatro bits, lo que hace que se necesitan dos serpientes en lugar de uno, para un total de al menos 6.

Por favor, tenga en cuenta que usted necesita por lo menos 6 para el simplificada de la ecuación, \$4x+3y\$, por lo que no es relevante si se puede hacer algo inteligente con el 13 o no - esta es la configuración básica y usted necesitará por lo menos 6 de los sumandos.

Answer 2

Así, para considerar su pregunta básica: ¿cuál es el mínimo número de sumandos necesarios?

Usted tiene inicialmente doce productos parciales (bits), mientras que su resultado tiene seis. Cada plenamente full adder se retire un producto parcial (bit), y por lo tanto, usted necesita exactly12 - 6 = 6 serpientes llenas. Entonces, dado que no se utilice la mitad de los sumandos, en la práctica puede ser más. Las maneras de conseguir alrededor de esto son recodificar los bits y/o simplificar algunos cálculos para no utilizar serpientes llenas (como usted dice, algunas entradas son constantes).

He aquí una solución alternativa:

Reescribir 3Y como 4Y-Y que conduce a (a' denota(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

El signo de la extensión puede escribirse 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

Ahora, esto se traduce 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 invertidas. También, como el segundo menos significativo columna contiene sólo dos productos parciales, tendremos que emplear un adicional de serpiente llena, a pesar de un medio sumador de ser suficiente.

Mirando y2' + 1, la suma de bits se convierte (como usted señala) y2, mientras que la llevan a poco se convierte en y2'. Por lo tanto, no hay adder es necesario. 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 producir un resultado con cuatro bits, es decir, cinco serpientes llenas.

Para conseguir lejos con el inversor, se puede reescribir esto como (utilizando 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 se va a cambiar el número de sumandos.

Ahora, si desea guardar una más completa de la serpiente, puede recodificar algunos de los bits en algo posiblemente "más fácil". Considerar 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 para 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' 

resultando en ocho productos parciales, pero todavía cinco serpientes llenas (de los cuales dos de computación z1 y z2 pueden hacer la mitad de las serpientes).

Answer 3

Usted puede hacer esto con 5 serpientes llenas y 1 puerta.

Z6 y z5 puede llevarse a cabo de la manera que he descrito. Para z4 través z1, usted necesitará utilizar fulladders. Para empezar, vamos a descubrirlo de la maleta que va en z4 de la columna (déjame llamar a este Ci4). Esto es igual a y3, por lo que no se necesita hardware adicional para generar este.

Tenemos que añadir 5 números (Ci4, x3, y2, y1 y 1) para obtener z4. Esto requerirá de 2 sumandos (feed Ci4, x3 y y2 a la primera fulladder para generar un intermedio suma S4x, luego alimentar a esta suma a lo largo de con y1 y 1 para el segundo full adder). Ahora, los dos fulladders se generan 2 lleva (permítanme llamar Ci3a y Ci3b), que vamos a alimentar a la siguiente etapa(z3).

Para z3 también tenemos que añadir 5 números (x2, y1, 1, Ci3a y Ci3b). Utilizar el mismo enfoque que para z4 (agregar 3 señales, y agregar el intermedio de la suma con los dos restantes). Esta etapa nos dejo con dos generado conlleva Ci2a y Ci2b.

Para z2 columna, sólo tenemos una entrada x1, a lo largo de con Ci2a y Ci2b. Nosotros sólo necesitamos una serpiente llena de manejar estas 3 entradas. Suma generada por esta serpiente llena será z2 y sus cargas serán z1.

Puede, tal vez, tener una mirada en multiplicadores de hardware, en particular, la etapa en la que añade el desplazado parcial de los productos.