Multiplicador binari
Un multiplicador binari és un circuit electrònic utilitzat en electrònica digital, com ara un ordinador, per multiplicar dos nombres binaris.
Es poden utilitzar diverses tècniques aritmètiques informàtiques per implementar un multiplicador digital. La majoria de les tècniques impliquen calcular el conjunt de productes parcials, que després es sumen mitjançant sumadors binaris. Aquest procés és similar a la multiplicació llarga, excepte que utilitza un sistema de numeració en base 2 (binari).
Història
[modifica]Entre 1947 i 1949 Arthur Alec Robinson va treballar per a English Electric Ltd, com a aprenent estudiant, i després com a enginyer de desenvolupament. De manera crucial durant aquest període va estudiar un doctorat a la Universitat de Manchester, on va treballar en el disseny del multiplicador de maquinari per a l'ordinador Mark 1 primerenc. No obstant això, fins a finals de la dècada de 1970, la majoria de minicomputadors no tenien una instrucció de multiplicació, de manera que els programadors utilitzaven una "rutina de multiplicació" [1][2][3] que canvia repetidament i acumula resultats parcials, sovint escrits mitjançant el desenrotllament de bucles. Els ordinadors mainframe tenien instruccions de multiplicació, però feien el mateix tipus de canvis i afegeix com a "rutina de multiplicació".
Els primers microprocessadors tampoc no tenien instruccions de multiplicació. Tot i que la instrucció de multiplicació es va fer comuna amb la generació de 16 bits, almenys dos processadors de 8 bits tenen una instrucció de multiplicació: el Motorola 6809, introduït el 1978,[4] i la família Intel MCS-51, desenvolupada el 1980, i més tard els moderns microprocessadors Atmel AVR de 8 bits presents als microcontroladors ATMega, ATTiny i ATXMega.
A mesura que es van disposar més transistors per xip a causa d'una integració a més gran escala, va ser possible posar suficients sumadors en un sol xip per sumar tots els productes parcials alhora, en lloc de reutilitzar un únic sumador per gestionar cada producte parcial d'un en un.
Com que alguns algorismes comuns de processament de senyals digitals passen la major part del temps multiplicant-se, els dissenyadors de processadors de senyals digitals sacrifiquen una àrea de xip considerable per tal de fer la multiplicació el més ràpid possible; una unitat de multiplicació i acumulació d'un sol cicle sovint utilitzava la major part de l'àrea de xip dels primers DSP.
Multiplicació binària llarga
[modifica]El mètode que s'ensenya a l'escola per multiplicar nombres decimals es basa en calcular productes parcials, desplaçar-los cap a l'esquerra i després sumar-los. La part més difícil és obtenir els productes parcials, ja que consisteix a multiplicar un nombre llarg per una xifra (de 0 a 9):
123
× 456
=====
738 (això és 123 × 6)
615 (això és 123 × 5, desplaçat una posició cap a l'esquerra)
+ 492 (això és 123 × 4, desplaçat dues posicions a l'esquerra)
=====
56088
Implementació de maquinari
[modifica]El procés de multiplicació es pot dividir en 3 passos: [5][6]
- generant un producte parcial
- reducció del producte parcial
- calculant el producte final
Les arquitectures multiplicadores més antigues utilitzaven un canviador i un acumulador per sumar cada producte parcial, sovint un producte parcial per cicle, intercanviant la velocitat per l'àrea de matriu. Les arquitectures multiplicadores modernes utilitzen l'algoritme de Baugh-Wooley (modificat), arbres de Wallace o multiplicadors de Dadda per sumar els productes parcials en un sol cicle. El rendiment de la implementació de l'arbre de Wallace de vegades es millora mitjançant la modificació de Booth que codifica un dels dos multiplicands, la qual cosa redueix el nombre de productes parcials que s'han de sumar.
Per a la velocitat, els multiplicadors de canvi i suma requereixen un sumador ràpid (alguna cosa més ràpid que el transport de ondulacions).
Un multiplicador de "cicle únic" (o "multiplicador ràpid") és pura lògica combinacional.
En un multiplicador ràpid, el procés de reducció parcial del producte normalment contribueix més al retard, la potència i l'àrea del multiplicador.[7] Per a la velocitat, les etapes de "reduir el producte parcial" s'implementen normalment com a sumador d'estalvi de transport compost per compressors i el pas de "càlcul del producte final" s'implementa com a sumador ràpid (alguna cosa més ràpid que el transport de ondulació).
Referències
[modifica]- ↑ Rather, Elizabeth D. «The evolution of Forth». A: Bergin. History of programming languages---II (en anglès). Association for Computing Machinery, 1996, p. 625–670. DOI 10.1145/234286.1057832. ISBN 0201895021.
- ↑ Davies, A.C.; Fung, Y.T. Microprocessors, 1, 7, 1977, pàg. 425–432. DOI: 10.1016/0308-5953(77)90004-6.
- ↑ Rafiquzzaman, M. «[[[:Plantilla:GBurl]] §2.5.1 Binary Arithmetic: Multiplication of Unsigned Binary Numbers]». A: Fundamentals of Digital Logic and Microcomputer Design (en anglès). Wiley, 2005, p. 46. ISBN 978-0-47173349-2.
- ↑ Kant, Krishna. «[[[:Plantilla:GBurl]] §2.11.2 16-Bit Microprocessors]». A: Microprocessors and Microcontrollers: Architecture, Programming and System Design 8085, 8086, 8051, 8096 (en anglès). PHI Learning, 2007, p. 57. ISBN 9788120331914.
- ↑ Rouholamini, Mahnoush. «A New Design for 7:2 Compressors» (en anglès).
- ↑ Leong, Yuhao. «Performance Comparison Review of 8-3 compressor on FPGA» (en anglès).
- ↑ Rouholamini, Mahnoush. «A New Design for 7:2 Compressors» (en anglès).