Tengo \ $ 2 ^ n \ $ entradas \ $ a_ {0}, a_ {1} .. a_ {2 ^ n} \ $, estas pueden ser altas o bajas, y \ $ n \ $ salidas \ $ z_ {0}, z_ {1} .. z_ {n} \ $, estos dan un número binario de cuántas entradas son altas. ¿Existe alguna forma sencilla de realizar esto sin utilizar la mitad y / o los sumadores completos?
No. No hay Si desea un número binario en el que la salida número n representa el valor de posición de 2 n , debe agregar en cascada los sumadores. Tenga en cuenta que un sumador es solo una puerta AND para el bit de acarreo y una puerta XOR para el bit de suma.
Si tiene un reloj, puede usar un mux para recorrer y contar las entradas.
Si esta debe ser una lógica combinatoria, puede buscar en el "árbol de compresores" métodos eficientes.
La idea básica de un árbol de compresores es reducir el número de señales en cada etapa en cascada hasta que las señales representen la suma final:
Un sumador de 2 entradas no ayuda mucho en esta situación porque la suma de dos bits de entrada todavía necesita dos bits de salida para representar la cuenta de 0, 1 o 2 bits de entrada alta. Pero como Jotorius señaló en los comentarios, puede crear una lógica que agregue grupos de tres bits de entrada para generar las correspondientes sumas de dos bits (0, 1, 2 o 3 entradas altas). Esto está progresando porque la cantidad de señales se ha reducido en un factor de 2/3. La siguiente etapa utiliza el mismo enfoque, pero ahora los bits de entrada tienen diferentes ponderaciones o "rangos". La mitad de los bits tienen un peso de 1 (los LSB de las sumas de dos bits) y los otros tienen un peso de 2 (los MSB de las sumas de dos bits).
En la segunda etapa, los bits del 1 se suman en grupos de tres y los bits del 2 se agrupan y se suman en grupos de tres, lo que resulta en un conjunto aún más pequeño de señales con pesos de 1, 2 y 4. (La suma los bits de las entradas de 2 tendrán un peso de 2 y 4.)
Las etapas del compresor continúan hasta que solo quedan dos o menos bits de cada peso. En este punto, puede utilizar un sumador de arrastre de ondulación estándar para obtener el resultado final.
Dependiendo de la cantidad exacta de bits en cada etapa, algunos sumadores de tres bits no utilizarán todas sus entradas.
Un árbol de compresores no se limita a una compresión de 3: 2 en cada etapa. Por ejemplo, un FPGA con LUT de 6 entradas podría implementar de manera eficiente la compresión 6: 3 en cada etapa del árbol.
Si N es pequeña, puedes hacer trampa y usar una EEPROM paralela estática para hacer una tabla de búsqueda.
Estás pidiendo una suma de entradas altas / activas. Una suma necesita sumadores para ser calculada! Puede ponerle el nombre que desee, pero al final hay agregadores involucrados.
Si desea encontrar soluciones rápidas, busque 'Hamming Weight' o 'Bit Count'.
Hay soluciones que utilizan tablas de búsqueda o DSP para lograr una mayor velocidad que el uso de RCA simples.
Lea otras preguntas en las etiquetas digital-logic logic-gates input adder binary