algoridmos

 Instituto tecnológico de nuevo león




Matemáticas Discretas

Prof.: ing. Iliana E. Méndez Treviño

11/02/13


Tema Algoritmos del Booth para la multiplicación en binarios







Índice
Introducción……………………………………………. 3
Desarrollo……………………………………………….. 4
Conclusión ……………………………………………... 5
Bibliografía ……………………………………………… 6















IntroducciónHace unos días necesité implementar el algoritmo de Booth en C++ para una parte de una de las prácticas de la asignatura Teoría de autómatas y lenguajes formales y la verdad, aunque existe bastante información, eché en falta una explicación didáctica para comprender el procedimiento desde un punto de partida. Así pues, en este artículo intentaré explicar el procedimiento del algoritmo lo mejorposible.
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.
























Desarrollo



Sabiendo que la posición de cada bit es 2^n (elevado a n) y partimos de n=0 de derecha a izquierda, sólo queda realizar la suma total de multiplicar por dicho bit, en este caso, lo quemuestro 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 el resultado de sumar 1 al complemento a uno de dicho número binario (NOTA: En el Ca1 sólo se complementa si el númeroes negativo):

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:

Como se puede ver en la imagen superior, partiendo de los números binarios de la multiplicación 6·2 (multiplicando y multiplicador) creamos tresnuevos 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:

Se realizará esta comparación 8 veces en este ejemplo (número de bits de los operandos) y al final de cada comparación, realizamos un desplazamiento de un bit hacia la derecha, manteniendo elúltimo bit de la izquierda, y descartando el último bit del lado contrario. Si hacemos una traza paso a paso nos quedarían los siguientes resultados:

Finalmente obtenemos el número en binario resultante (12 en este ejemplo), descartando el bit extra que hemos añadido al principio del procedimiento y que se encuentra en el extremo a la derecha.


1.4 Algoritmos de Booth para la multiplicación ydivisión en binario.

ALGORITMO DE BOOTH
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.
Complemento a1
Para obtener el complemento a uno del numero en binario solo consta en cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1:101101)
Complemento a2
El complemento ados de un número binario es el resultado 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):  mi numero en decimal es 86
Realizar una multiplicación con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6·2=12:
1º Obtengo mis números (multiplicando y multiplicador) en binariocon longitud de 8 bits
2º  asigno A= multiplicando, S= Complemento a2 de A, P= 8 bits en 0. Agrego 7 bits extras a la derecha de A y S, en P agrego el valor de multiplicador con longitud de 8 bits y un bit extra con valor 0. Como se indica a continuación:
Como se puede ver en la imagen superior, partiendo de los números binarios de la multiplicación 6·2 (multiplicando y multiplicador) creamos...