Algoritmos de both

INSTITUTO TECNOLÓGICO SUPERIOR DE TIERRA BLANCA (ITSTB)

CATEDRÁTICO:
M.R.T. MARIO LOTH ÁLVAREZ MÉNDEZ
MATERIA:
MATEMÁTICAS DISCRETAS
TRABAJO:
ENSAYO
TEMA:
ALGORITMOS DE BOOTH PARA MULTIPLICAR Y DIVIDIR BINARIOS
ALUMNO:
SALVADOR REYES ARRIOLA
CARRERA:
ISC
GRUPO:
102-C

ÍNDICE
Introducción al tema…………………………………………(3)
Algoritmo de booth para multiplicación de binarios… (4)Algoritmo de booth para división de binarios……….… (8)
Conclusión………………………….……………………….. (11)
Referencias……………………………………………..…….. (11)

INTRODUCCIÓN AL TEMA

EN LOS SIGUIENTES TEMAS A TRATAR VEREMOS Y REALIZAREMOS ALGUNAS OPERACIONES CON BASE AL ALGORITMO DE UN AUTOR LLAMADO BOOTH QUE UTILIZA UN CIERTO TIPO DE PASOS O ALGORITMOS PARA MULTIPLICAR Y DIVIDIR BINARIOS.
SEGUIREMOS PASO A PASO LASFORMAS PARA REALIZAR LAS MULTIPLICACIONES Y DIVISIONES A PARTIR DE ESTE ALGORITMO POR LO TANTO AL FINAL DE LA LECTURA Y LAS OPERACIONES, EL LECTOR O EL CAPACITADOR COMO LOS ALUMNOS PODRÁN REALIZAR ESTA OPERACIONES CON BASE CALOS TEMAS QUE REVISARAN CON ESTOS APARTADOS, ES DECIR, REALIZARÁN MULTIPLICACIONES Y DIVISIONES A PARTIR DEL ALGORITMO DE BOOTH.

Algoritmo de booth para multiplicación debinarios

Procedimiento
Supongamos dos números, multiplicando y multiplicador, con longitudes en bits, x para el primero, e y para el segundo:
• Construimos una matriz de tres filas y x+y+1 columnas. Identificaremos las filas como, A la primera, S la segunda y P la tercera.
• Se inician los x primeros bits de cada fila con:
o A, el multiplicando.
o S, el complemento ados del multiplicando.
o P, ceros.
• Los siguientes y bits se completan con:
o A, ceros.
o S, ceros.
o P, el multiplicador.
• Para finalizar la matriz, se inician a 0 todos los valores de la última columna.

Una vez iniciada esta matriz, se realiza el algoritmo.
• Se realizan y iteraciones del siguiente bucle.
1. Comparar los dosúltimos bits de P, para realizar la siguiente acción:
▪ 00 o 11: no se hace nada.
▪ 01: P = P + A. Se ignora el acarreo.
▪ 10: P = P + S. Se ignora el acarreo.
2. Desplazamiento aritmético de P a la derecha (se conserva el bit de signo).
• Finalmente, tras y iteraciones, se elimina el último bit de la derecha (menos significativo),obteniendo el resultado.

El algoritmo de Booth es un método rápido y sencillo para obtener el producto de dos números binarios con signo en notación complemento a dos.

Debemos saber que un número binario está formado por bits de ceros y unos, y que se puede traducir a decimal fácilmente de la siguiente forma:

[pic]
Sabiendo que la posición de cada bit es 2^n (elevado a n) y partimos de n=0 dederecha a izquierda, sólo queda realizar la suma total de multiplicar por dicho bit, en este caso, lo que muestro a continuación:
0·27+1·26+0·25+1·24+0·23+1·22+1·21+0·20 = 86.

También debemos saber que el complemento a uno de un número binario es cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1: 101101) y que el complemento a dos de un número binario es elresultado de sumar 1 al complemento a uno de dicho número binario (NOTA: En el Ca1 sólo se complementa si el número es negativo):

[pic]

Realizar una suma con dos números binarios es tarea fácil, pero la multiplicación resulta algo más complicada. Con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6·2=12:

[pic]

Como se puede ver enla imagen superior, partiendo de los números binarios de la multiplicación 6·2 (multiplicando y multiplicador) creamos tres nuevos números binarios del doble de tamaño (16 en el ejemplo): A, S y P.

Partiendo del número P (producto) comenzamos a comparar los últimos 2 bits de la derecha, siguiendo los casos base del recuadro:

[pic]

Se realizará esta comparación 8 veces en este ejemplo...