Circuito booleano - 4 bits divisible por 3

Enfoque general para \ $ m \ $ bits

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 es divisible por 3 (Hay una variedad de enfoques para esta operación, pero el primero que se encuentra es generalmente a través de sumadores de acarreo y ahorro).

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

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 simple medio adidor, cada uno. La tabla resultante es:

$$ \ begin {smallmatrix} \ begin {array} {r | cccc} & \ overline {C_ \ text {odd}} \: \ overline {S_ \ text {odd}} & \ overline {C_ \ text {odd}} \: S_ \ text {odd} & C_ \ text { odd} \: \ overline {S_ \ text {odd}} \\ \ hline \ overline {C_ \ text {even}} \: \ overline {S_ \ text {even}} & Y & N & N \\ \ overline {C_ \ text {even}} \: S_ \ text {even} & N & Y & N \\ C_ \ text {even} \: \ overline {S_ \ text {even}} & N & N & Y \ end {array} \ end {smallmatrix} $$

En este caso, no es necesario preocuparse por la "divisibilidad entre 3" de la diferencia. En su lugar, es suficiente comparar las dos sumas para "igual", como se muestra en la tabla anterior.

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

^{simular este circuito : esquema creado usando CircuitLab}

Los medios sumadores son fácilmente reconocidos arriba. Además, sus salidas asociadas se comparan directamente utilizando un par de XOR. Los resultados de estas dos comparaciones se consideran luego utilizando un NOR para el resultado final.

Las otras respuestas son simplemente forzadas a la respuesta escribiendo todos los casos verdaderos. Se volverá mucho más complejo cuanto más se agreguen los bits (aproximadamente el doble de la cantidad de casos cada bit).

Alternativamente, podrías considerarlo como un ciclo de módulo

0->1->2->0

El primer bit, si es verdadero, agrega 1, por lo tanto, lo mueve hacia la derecha en 1

El segundo agrega 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 suma de notación de productos:

$$ F (A, B, C, D) = \ Sigma (0,3,6,9,12,15) $$

Dicha representación se convierte de forma trivial en una implementación de MUX, que supongo que se puede usar (como usted menciona mediante el uso de complementos). Simplemente conecte todas las entradas correspondientes a los números listados a 1 lógico, y las otras a 0 :

^{simular este circuito : esquema creado usando CircuitLab}

No puedo encontrar otra cosa que no sea la expresión booleana $$ \ bar {A} \ bar {B} \ bar {C} \ bar {D} + AB \ bar {C} \ bar {D} + \ bar {A} BC \ bar {D} + \ bar {A} \ bar {B} CD + A \ bar {B} \ bar {C} D + ABCD $$

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 de módulo 3, puede calcularlo por byte. Por lo tanto, para un número de 8 bits necesitaría dos veces la cantidad de compuertas, aunque su rango de entrada se haya multiplicado por 16.

Al igual que con los números decimales, si sumas todos los dígitos individuales y encuentras que la suma es exactamente divisible por 3, entonces el número entero también fue exactamente divisible por 3: -

351 (dec) es divisible por 3 porque 3 + 5 + 1 = 9 y 9 es divisible por tres.

Para binario, divida el número de 4 bits en dos números de 2 bits, es decir, 12 (decimal) es 1100 (binario) y la suma de las dos piezas es 11 + 00 = 11 = 3 (decimal). 6 (decimal) es 0110 (binario) y 01 + 10 = 3 (decimal).

Quince (decimal) es 1111 y 11 + 11 es 0110. Este número es mayor que 3 (6) y puede reducirse nuevamente agregando 01 y 10 para producir 3.

Si lo intentaste con (digamos) 7 (0111), el primer agregado sería 100 y el segundo sería solo 01 y esto claramente no es igual a 3. Es la teoría numérica básica .