comprobar si un número binario sin signo es divisible por 15
sheldonzy
Soy estudiante de informática y me quedé atascado en esta pregunta durante horas.
Tenemos un número X binario sin signo, representado por 12 bits. Nos gustaría construir un sistema con una salida de 1 bit: Y, que será '1' si X se divide por 15 sin resto.
Los únicos componentes que podemos utilizar son:
- Sumador de 4 bits, que también tiene C0 (carry) como entrada y C4 como salida.
- 1 puerta NOR simple con 3 entradas.
Encontré un patrón. Si calculo 2^i % 15 para 0<=i<=11 (dado que son 12 bits), entonces obtendré una secuencia 1248 1248 1248.
Y si tengo 0001 1110 1111 entonces puedo simplemente multiplicar todos los dígitos, sumarlos y verificar si mi número es divisible por 15.
0 + 0 + 0 + 8 + 1 + 2 + 4 + 0 + 1 + 2 + 4 + 8 = 30
El problema es que no tengo ni idea de cómo implementarlo, y si es incluso eficiente.
Me encantaría un poco de ayuda.
Respuestas (3)
Neil_ES
¿Sabes cómo verificar la divisibilidad por 9 en base 10?
Suma todos los dígitos usando aritmética de base 10. Si el resultado tiene varios dígitos, repita el proceso. Deténgase cuando tenga un dígito. Si el dígito es 9, el número original era divisible por 9. Esto funciona porque el divisor que se prueba es de base 1. Por ejemplo, 45 es divisible por 9, y los dígitos suman 9, solo se necesita un sumador para dos dígitos. 999 también lo es, se necesitan dos sumadores para los tres dígitos.
Entonces, ¿ahora tiene una pista de cómo probar la divisibilidad por 15 cuando tiene a mano las instalaciones aritméticas de base 16?
sheldonzy
el fotón
sheldonzy
pedro verde
La técnica es similar a lo que harías para verificar si un número es divisible por 9 en decimal. Necesitamos dividir el número en dígitos de cuatro bits y luego sumar los dígitos repetidamente hasta que nos quede un solo dígito.
Llamemos a los dígitos XYZ
c1,r1 = X + Y
c2,r2 = Z + r1 + c1
c3,r3 = r2 + 1
SI X,Y,Z es divisible por 15, entonces c2,r2 también es divisible por 15. Además, c2,r2 es menor que 0x1e. Entonces, si r = 15, entonces el número original era divisible por 15. Probamos si r es igual a 15 sumando uno y observando la bandera de acarreo resultante.
Lo que me desconcierta es para qué se supone que sirve la puerta nor.
nick gammon
0FF, 1EF, 2DF, 3CF, 4BF, 5AF, 69F, 78F, 87F, 96F, A5F, B4F, C3F, D2F, E1F, F0F, FFF. Su tercera línea necesita leerc3,r3 = r2 + c2 + 1sheldonzy
La respuesta completa:
Como dijo @Neil_UK, tengo 12 bits, y si quiero verificar si ese número es divisible por 15, tomaré los 12 bits y los miraré como 3 números en base 16.
Sumo los tres números, siempre sumando el acarreo al siguiente sumador.
Después de agregarlos a todos, obtendré como resultado algún número. Como dije, queremos ver si el número es divisible por 15, y como los números están en base 16, si el resultado es 15, el número es divisible por 15.
Si ese número es 15, en binario 1111, entonces si voy a sumar 1, 1111obtendré carry 1y 0000.
Si ese número es 0, en binario 0000, entonces si lo sumo 1, 0000obtendré 0001.
Aquí es donde entra en juego el NOR.
El número es divisible por 15 si los últimos 3 dígitos son 0.
El circuito:
Por ejemplo:
1111 1111 1111:
1111+1111+1= llevar1y11111111 + 1111+ llevar1= llevar1y11111111+ llevar1= llevar1y0000- NOR(0,0,0)=Verdadero
0001 1001 0101: (405):
0101+1001+1=11111111+0001= llevar1y00000000+ llevar1=0001- NOR(0,0,0)=Verdadero
¿Cómo funciona un medio sumador hecho de pestillos de barra transversal?
Construcción de un sumador completo con transistores NPN BJT
¿Cómo saber si un número binario es cero o no usando puertas lógicas?
Número mínimo de CMOS complementarios a implementar F=ABC+(A+B+C)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯F=ABC+(A+ B+C)¯F=ABC+\overline{(A+B+C)}?
Medio sumador y dos funciones, un concurso ¿Preguntas?
¿Cómo se usan sumadores completos y medios juntos?
Efectos de la capacitancia de entrada en el retardo de propagación (con análisis de esfuerzo lógico)
Fórmulas para llevar a cabo en un sumador completo
¿Cómo podemos convertir el diagrama de puerta NOR de múltiples entradas en un diagrama de puerta NOR de 2 entradas?
¿Cómo construir un circuito lógico de división? [cerrado]
marcelmo
MSalters