Multiplicador binário - Binary multiplier
| Parte de uma série sobre | |||||||
| Circuitos lógicos aritméticos | |||||||
|---|---|---|---|---|---|---|---|
| Navegação rápida | |||||||
|
Componentes
|
|||||||
|
Veja também |
|||||||
Um multiplicador binário é um circuito eletrônico usado em eletrônica digital , como um computador , para multiplicar dois números binários .
Uma variedade de técnicas aritméticas de computador pode ser usada para implementar um multiplicador digital. A maioria das técnicas envolve o cálculo do conjunto de produtos parciais, que são somados usando somadores binários . Este processo é semelhante à multiplicação longa , exceto que usa um sistema numeral de base 2 ( binário ) .
História
Entre 1947 e 1949, Arthur Alec Robinson trabalhou para a English Electric Ltd, como estudante aprendiz e depois como engenheiro de desenvolvimento. Crucialmente durante este período, ele estudou para um doutorado na Universidade de Manchester, onde trabalhou no design do multiplicador de hardware para o primeiro computador Mark 1. [3] No entanto, até o final dos anos 1970, a maioria dos minicomputadores não tinha uma instrução multiplicação, e assim os programadores usaram uma "rotina multiplicar" que alterna e acumula resultados parciais repetidamente , muitas vezes escrita usando o desenrolamento de loop . Os computadores mainframe tinham instruções de multiplicação, mas faziam os mesmos tipos de mudanças e acréscimos como uma "rotina de multiplicação".
Os primeiros microprocessadores também não tinham instrução de multiplicação. Embora a instrução multiplique tenha se tornado comum com a geração de 16 bits, pelo menos dois processadores de 8 bits têm uma instrução multiplique: o Motorola 6809 , introduzido em 1978, e a família Intel MCS-51 , desenvolvida em 1980, e posteriormente o moderno Atmel AVR Microprocessadores de 8 bits presentes nos microcontroladores ATMega, ATTiny e ATXMega.
À medida que mais transistores por chip se tornaram disponíveis devido à integração em maior escala, tornou-se possível colocar somadores suficientes em um único chip para somar todos os produtos parciais de uma vez, em vez de reutilizar um único somador para lidar com cada produto parcial, um de cada vez.
Como alguns algoritmos comuns de processamento de sinais digitais passam a maior parte do tempo se multiplicando, os projetistas de processadores de sinais digitais sacrificam uma área considerável do chip para fazer a multiplicação o mais rápido possível; uma unidade de multiplicação-acumulação de ciclo único costumava usar a maior parte da área do chip dos primeiros DSPs.
Multiplicação binária longa
O método ensinado na escola para a multiplicação de números decimais é baseado no cálculo de produtos parciais, deslocando-os para a esquerda e depois somando-os. A parte mais difícil é obter os produtos parciais, pois isso envolve a multiplicação de um número longo por um dígito (de 0 a 9):
123
x 456
=====
738 (this is 123 x 6)
615 (this is 123 x 5, shifted one position to the left)
+ 492 (this is 123 x 4, shifted two positions to the left)
=====
56088
Um computador binário faz exatamente a mesma multiplicação que os números decimais, mas com números binários. Na codificação binária, cada número longo é multiplicado por um dígito (0 ou 1), e isso é muito mais fácil do que na decimal, pois o produto por 0 ou 1 é apenas 0 ou o mesmo número. Portanto, a multiplicação de dois números binários se resume a calcular produtos parciais (que são 0 ou o primeiro número), deslocando- os para a esquerda e, em seguida, adicionando-os (uma adição binária, é claro):
1011 (this is binary for decimal 11)
x 1110 (this is binary for decimal 14)
======
0000 (this is 1011 x 0)
1011 (this is 1011 x 1, shifted one position to the left)
1011 (this is 1011 x 1, shifted two positions to the left)
+ 1011 (this is 1011 x 1, shifted three positions to the left)
=========
10011010 (this is binary for decimal 154)
Isso é muito mais simples do que no sistema decimal, pois não há uma tabela de multiplicação para lembrar: apenas desloca e soma.
Este método é matematicamente correto e tem a vantagem de que uma pequena CPU pode realizar a multiplicação usando o deslocamento e adicionar recursos de sua unidade lógica aritmética em vez de um circuito especializado. O método é lento, entretanto, pois envolve muitas adições intermediárias. Essas adições são demoradas. Multiplicadores mais rápidos podem ser projetados para fazer menos adições; um processador moderno pode multiplicar dois números de 64 bits com 6 adições (em vez de 64) e pode executar várias etapas em paralelo.
O segundo problema é que o método básico da escola trata o sinal com uma regra separada ("+ com + produz +", "+ com - produz -", etc.). Os computadores modernos incorporam o sinal do número no próprio número, geralmente na representação de complemento de dois . Isso força o processo de multiplicação a ser adaptado para lidar com os números do complemento de dois, o que complica um pouco mais o processo. Da mesma forma, os processadores que usam o complemento , sinal e magnitude , IEEE-754 ou outras representações binárias requerem ajustes específicos para o processo de multiplicação.
Inteiros sem sinal
Por exemplo, suponha que queiramos multiplicar dois inteiros de oito bits sem sinal : a [7: 0] eb [7: 0]. Podemos produzir oito produtos parciais realizando oito multiplicações de um bit, uma para cada bit no multiplicando a :
p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0]
p1[7:0] = a[1] × b[7:0] = {8{a[1]}} & b[7:0]
p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0]
p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0]
p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0]
p5[7:0] = a[5] × b[7:0] = {8{a[5]}} & b[7:0]
p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0]
p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0]
onde {8 {a [0]}} significa repetir a [0] (o 0º bit de a) 8 vezes ( notação Verilog ).
Para obter nosso produto, precisamos somar todos os oito produtos parciais, conforme mostrado aqui:
p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0]
+ p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0
+ p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0 0
+ p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0
+ p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0
+ p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0
+ p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0
+ p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0 0 0 0 0 0 0
-------------------------------------------------------------------------------------------
P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0]
Em outras palavras, P [15: 0] é produzido somando p 0, p 1 << 1, p 2 << 2 e assim por diante, para produzir nosso produto final de 16 bits sem sinal.
Inteiros assinados
Se b tinha sido assinado inteiro em vez de um sem assinatura inteiro, em seguida, os produtos parciais precisaria ter sido sign-prorrogado até a largura do produto antes de soma. Se a fosse um número inteiro com sinal, o produto parcial p7 precisaria ser subtraído da soma final, em vez de adicionado a ela.
O multiplicador de matriz acima pode ser modificado para suportar dois números assinados de notação de complemento, invertendo vários dos termos do produto e inserindo um à esquerda do primeiro termo parcial do produto:
1 ~p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0]
~p1[7] +p1[6] +p1[5] +p1[4] +p1[3] +p1[2] +p1[1] +p1[0] 0
~p2[7] +p2[6] +p2[5] +p2[4] +p2[3] +p2[2] +p2[1] +p2[0] 0 0
~p3[7] +p3[6] +p3[5] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0] 0 0 0
~p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4[2] +p4[1] +p4[0] 0 0 0 0
~p5[7] +p5[6] +p5[5] +p5[4] +p5[3] +p5[2] +p5[1] +p5[0] 0 0 0 0 0
~p6[7] +p6[6] +p6[5] +p6[4] +p6[3] +p6[2] +p6[1] +p6[0] 0 0 0 0 0 0
1 +p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0] 0 0 0 0 0 0 0
------------------------------------------------------------------------------------------------------------
P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0]
Onde ~ p representa o complemento (valor oposto) de p.
Existem muitas simplificações na matriz de bits acima que não são mostradas e não são óbvias. As sequências de um bit complementado seguido por bits não complementados estão implementando um truque de complemento de dois para evitar a extensão do sinal. A sequência de p7 (bit não complementado seguido por todos os bits complementados) é porque estamos subtraindo esse termo, então eles foram todos negados no início (e um 1 foi adicionado na posição menos significativa). Para ambos os tipos de sequências, o último bit é invertido e um -1 implícito deve ser adicionado diretamente abaixo do MSB. Quando o +1 da negação do complemento de dois para p7 na posição de bit 0 (LSB) e todos os -1s nas colunas de bits 7 a 14 (onde cada um dos MSBs estão localizados) são somados, eles podem ser simplificados para o único 1 que "magicamente" está flutuando para a esquerda. Para obter uma explicação e uma prova de por que virar o MSB nos economiza a extensão do sinal, consulte um livro de aritmética de computador.
Números de ponto flutuante
Um número flutuante binário contém um bit de sinal, bits significativos (conhecidos como significando) e bits expoentes (para simplificar, não consideramos campo de base e combinação). Os bits de sinal de cada operando são submetidos a XOR para obter o sinal da resposta. Em seguida, os dois expoentes são adicionados para obter o expoente do resultado. Finalmente, a multiplicação do significando de cada operando retornará o significando do resultado. No entanto, se o resultado da multiplicação binária for maior do que o número total de bits para uma precisão específica (por exemplo, 32, 64, 128), o arredondamento é necessário e o expoente é alterado apropriadamente.
Implementação de hardware
O processo de multiplicação pode ser dividido em 3 etapas:
- gerando produto parcial
- reduzindo produto parcial
- produto final de computação
As arquiteturas de multiplicador mais antigas empregavam um deslocador e um acumulador para somar cada produto parcial, geralmente um produto parcial por ciclo, trocando a velocidade pela área da matriz. As arquiteturas multiplicadoras modernas usam o algoritmo Baugh – Wooley (modificado) , árvores Wallace ou multiplicadores Dadda para adicionar os produtos parciais em um único ciclo. O desempenho da implementação da árvore Wallace às vezes é melhorado pelo Booth modificado que codifica um dos dois multiplicandos, o que reduz o número de produtos parciais que devem ser somados.
Para velocidade, os multiplicadores shift-and-add requerem um somador rápido (algo mais rápido do que o ripple-carry).
Um multiplicador de "ciclo único" (ou "multiplicador rápido") é pura lógica combinatória .
Em um multiplicador rápido, o processo de redução parcial do produto geralmente contribui mais para o atraso, a potência e a área do multiplicador. Para velocidade, os estágios de "redução do produto parcial" são normalmente implementados como um somador de transporte e economia composto de compressores e a etapa de "cálculo do produto final" é implementado como um somador rápido (algo mais rápido do que o transporte de ondulação).
Muitos multiplicadores rápidos usam somadores completos como compressores ("compressores 3: 2") implementados em CMOS estáticos . Para obter melhor desempenho na mesma área ou o mesmo desempenho em uma área menor, os projetos de multiplicadores podem usar compressores de ordem superior, como compressores 7: 3; implementar os compressores em lógica mais rápida (como lógica de porta de transmissão, lógica de transistor de passagem, lógica de dominó ); conecte os compressores em um padrão diferente; ou alguma combinação.
Circuitos de exemplo
Veja também
- Algoritmo de multiplicação de Booth
- Multiplicar fundido - adicionar
- Árvore Wallace
- Algoritmo BKM para logaritmos complexos e exponenciais
- Multiplicação Kochanski para multiplicação modular
- Mudança lógica à esquerda
Referências
- Hennessy, John L .; Patterson, David A. (1990). "Seção A.2, seção A.9". Arquitetura de Computadores: Uma Abordagem Quantitativa . Morgan Kaufmann Publishers, Inc. pp. A – 3..A – 6, A – 39..A – 49. ISBN 978-0-12383872-8.