Circuito booleano: 4 bits divisibles por 3

Enfoque general para$m$pedacitos

La solución general para una prueba de división por 3 es sumar los bits pares y sumar por separado los bits impares, tomar la diferencia entre estas sumas y luego ver si la diferencia misma es divisible por 3. (Hay Hay una variedad de enfoques para esta operación, pero el primero que se encuentra generalmente es a través de sumadores de acarreo y guardado).

Para un valor binario con$m$pedacitos, donde$m$es par, la diferencia requerirá como máximo$\lceil\operatorname{ln}_2\frac{m}{2}\rceil$pedacitos Para un valor binario con$m$pedacitos, donde$m$es impar, la diferencia requerirá como máximo$\lceil\operatorname{ln}_2\frac{m+1}{2}\rceil$pedacitos Este resultado de diferencia podría enviarse a un nivel mucho más pequeño para, una vez más, calcular la diferencia entre las sumas de bits pares e impares. (Y repetir.)

Caso específico donde$m=4$

En este punto, es bastante fácil ver que las sumas pares e impares se pueden calcular utilizando un medio sumador simple, cada uno. La tabla resultante es:

En este caso, no hay necesidad de preocuparse por la "divisibilidad por 3" de la diferencia. En cambio, es suficiente comparar las dos sumas para "iguales", como se muestra en la tabla anterior.

Esto debería ser muy fácil de implementar:

^{simular este circuito : esquema creado con CircuitLab}

Las medias sumadoras se reconocen fácilmente arriba. Además, sus salidas asociadas se comparan directamente mediante un par de XOR. Los resultados de estas dos comparaciones luego se consideran utilizando un NOR para el resultado final.

Las otras respuestas son simplemente forzar la respuesta al escribir todos los casos verdaderos. Se volverá mucho más complejo cuanto más bits agregue (aproximadamente se duplica la cantidad de casos cada bit).

Alternativamente, podría pensar en ello como un ciclo de módulo

0->1->2->0

El primer bit, si es verdadero, suma 1, por lo tanto, lo mueve a la derecha 1

El segundo suma 2. (+2 / -1)

Continuando con esto, tienes

|bit|num|mod|
| 1 | 1 |+1 |
| 2 | 2 |-1 |
| 3 | 4 |+1 |
| 4 | 8 |-1 |

Entonces, tienes la respuesta como

A-B+C-D=0

o

A+C=B+D

Esta solución es mucho más fácil de expandir a una cantidad arbitraria de bits de entrada.

Su función se puede escribir fácilmente como una notación de suma de productos:

Tal representación se convierte trivialmente en una implementación MUX, que supongo que puede usar (como menciona el uso de sumadores). Simplemente conecte todas las entradas correspondientes a los números enumerados a lógico 1y las otras a 0:

^{simular este circuito : esquema creado con CircuitLab}

No se me ocurre nada más que la expresión booleana

Esta implementación requiere 12 AND, 6 NAND y 5 OR Gates. No creas que es demasiado complicado de construir. Lo bueno es que se escala linealmente con el tamaño de entrada, ya que en el caso del módulo 3 puede calcularlo por bytes. Entonces, para un número de 8 bits, necesitaría el doble de puertas, aunque su rango de entrada se haya multiplicado por 16.

La implementación de un número de 4 bits divisible por 3 es bastante simple. Encontré una forma directa como se muestra en la imagen:

Usé 2 puertas XOR y 1 puerta XNOR.