verifique si un número binario sin signo es divisible entre 15

Navega tus respuestas
7

Soy un estudiante de informática y me quedé estancado en esta pregunta durante horas.

Tenemos un número binario sin signo X, representado por 12 bits. Nos gustaría construir un sistema con salida de 1 bit - Y, que será '1' si X se divide por 15 sin el resto.

Los únicos componentes que podemos usar son:

  • sumador de 4 bits, que también tiene C0 (acarreo) como entrada y C4 como salida.
  • 1 puerta NOR única con 3 entradas.

Encontré un patrón. Si calculo 2 ^ i% 15 para 0 < = i < = 11 (ya que son 12 bits), entonces obtendré una secuencia 1248 1248 1248.

Y si tengo 0001 1110 1111, puedo simplemente multiplicar todos los dígitos, sumarlos y verificar si mi número es divisible entre 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.

    
pregunta sheldonzy

3 respuestas

19

¿Sabe cómo verificar la divisibilidad entre 9 en la base 10?

Suma todos los dígitos usando aritmética de base 10. Si el resultado tiene varios dígitos, repita el proceso. Detente cuando tengas un dígito. Si el dígito es 9, el número original era divisible por 9. Esto funciona porque el divisor que se está probando es 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 es también, se necesitan dos sumadores para los tres dígitos.

Entonces, ¿tienes una pista de cómo probar la divisibilidad entre 15 cuando tienes a tu disposición bases aritméticas de base 16?

    
respondido por el Neil_UK
4

La técnica es similar a lo que harías para verificar si un número es divisible entre 9 en decimal. Necesitamos dividir el número en cuatro dígitos de bit y luego sumar los dígitos repetidamente hasta que nos quede un solo dígito.

Permite llamar a los dígitos X Y Z 

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 al agregar uno y mirando la bandera de acarreo resultante.

Lo que me está desconcertando es para qué se supone que es ni la puerta.

    
respondido por el Peter Green
0

La respuesta completa:

Como dijo @Neil_UK, tengo 12 bits, y si quiero verificar si ese número es divisible entre 15, tomaré los 12 bits y los veré como 3 números en la base 16.

Agrego los tres números juntos, mientras que siempre agrego el carry al siguiente sumador.

Después de agregarlos todos, obtendré como resultado un número. Como dije, queremos ver si el número es divisible por 15, y porque los números están en la base 16, por lo que si el resultado es 15, el número es divisible por 15.

Si ese número es 15, en binario 1111 , entonces si agrego 1 a 1111 , obtendré carry 1 y 0000 .

Si ese número es 0, en el binario 0000 , entonces si agrego 1 a 0000 , obtendré 0001 .

Aquí es donde NOR viene a jugar.

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 = carry 1 y 1111
  • 1111 + 1111 + carry 1 = carry 1 y 1111
  • 1111 + carry 1 = carry 1 y 0000
  • NOR (0,0,0) = Verdadero

0001 1001 0101 : (405):

  • 0101 + 1001 + 1 = 1111
  • 1111 + 0001 = carry 1 y 0000
  • 0000 + carry 1 = 0001
  • NOR (0,0,0) = Verdadero
respondido por el sheldonzy

Lea otras preguntas en las etiquetas

Acercamiento de pin de esquema esquemático Ejercicios sugeridos para aprender con Arduino