Algoritmo de Booth en forma de dígitos signados

BOOTH ALGORITHM IN SIGNED-DIGIT REPRESENTATION

Descargar PDF Descargar PDF

Publicado en 3C TIC – Volumen 5 Número 3 (Edición 18)

portada 3c tic

Autores

Resumen

El algoritmo dado por Andrew Donald Booth en 1950 para la multiplicación puede interpretarse de la forma clásica: una manera de reducir las secuencias de 1s consecutivas existentes en la representación binaria de un número, o puede mirarse más desde el prisma en que lo hacen técnicas como la representación NAF, donde se entiende que, en lugar de apostar por una representación binaria del número se tiene una representación ternaria, que cumple la propiedad (o se espera que cumpla) de tener más 0s que la representación binaria clásica. En ambos enfoques el aumento de rendimiento se obtiene debido a que, en el esquema algorítmico de Booth, cuando el número contra el que se opera tiene un 0 en la i-esima posición. En ese i-esimo paso algorítmico nos ahorramos los cálculos (o parte de ellos), de ahí que en este documento vayamos a optimizar esos casos donde, según el prisma por el que miremos, compactamos las secuencias consecutivas de 1s o la representación ternaria tenga más 0s que la binaria.

Abstract

The algorithm given by Andrew Donald Booth in 1950 for multiplication, can be interpreted in the classic way: a way to reduce existing sequences consecutive 1s in the binary representation of a number. Or you can look more from the prism they do techniques such as NAF representation: where it is understood that instead of opting for a binary representation of the number, it is a ternary representation, which meets the property (or is expected to meet) having more 0s than classical binary representation. In both approaches, the performance increase is achieved because, in the algorithmic scheme Booth, when the number against which it has a 0 in the ith position operates in the i-th algorithmic step, we saved the calculations (or part thereof). Hence in this paper we are going to optimize those cases where, according to the prism through which we look, we compact sequences of consecutive 1s or 0s ternary representation has more than binary.

Artículo

Palabras clave

Booth, algoritmo, multiplicación, inverso, dígitos signados.

Keywords

Booth, algorithm, multiplication, inverse, signed-digit.

Articulos relacionados