Somador Carry-save - Carry-save adder

Parte de uma série sobre
circuitos aritméticos lógicos
Navegação rápida
Teoria
Componentes
Categorias
Veja também

Um somador carry-save é um tipo de somador digital , usado para calcular com eficiência a soma de três ou mais números binários . Ele difere de outros somadores digitais porque produz dois (ou mais) números, e a resposta da soma original pode ser obtida somando essas saídas. Um somador carry save é normalmente usado em um multiplicador binário, uma vez que um multiplicador binário envolve a adição de mais de dois números binários após a multiplicação. Um grande somador implementado usando essa técnica geralmente será muito mais rápido do que a adição convencional desses números.

Motivação

Considere a soma: 

   12345678
+  87654322
= 100000000

Usando aritmética básica, calculamos da direita para a esquerda, "8 + 2 = 0, transporta 1", "7 + 2 + 1 = 0, transporta 1", "6 + 3 + 1 = 0, transporta 1" e assim por diante ao final da soma. Embora conheçamos o último dígito do resultado de uma vez, não podemos saber o primeiro dígito até que tenhamos passado por cada dígito no cálculo, passando o transporte de cada dígito para aquele à sua esquerda. Assim, a adição de dois n quatro dígitos números tem de ter um tempo proporcional a n , mesmo se a máquinas que está a utilizar, de outra forma ser capaz de realizar vários cálculos simultaneamente.

Em termos eletrônicos, usando bits (dígitos binários), isso significa que mesmo se tivermos n somadores de um bit à nossa disposição, ainda temos que permitir um tempo proporcional an para permitir que um possível transporte se propague de uma extremidade do número para o outro. Até que tenhamos feito isso,

  1. Não sabemos o resultado da adição.
  2. Não sabemos se o resultado da adição é maior ou menor que um determinado número (por exemplo, não sabemos se é positivo ou negativo).

Um somador carry look-ahead pode reduzir o atraso. Em princípio, o atraso pode ser reduzido de forma que seja proporcional a log  n , mas para grandes números este não é mais o caso, porque mesmo quando o carry look-ahead é implementado, as distâncias que os sinais têm que viajar no chip aumentam em proporção para n , e os atrasos de propagação aumentam na mesma taxa. Assim que chegarmos aos tamanhos de número de 512 a 2048 bits exigidos na criptografia de chave pública , a análise antecipada não ajudará muito.

O conceito básico

A ideia de atrasar a resolução do carry até o fim, ou salvar o carry, é responsabilidade de John von Neumann .

Aqui está um exemplo de uma soma binária de 3 números binários longos: 

  10111010101011011111000000001101 (a)
+ 11011110101011011011111011101111 (b)
+ 00010010101101110101001101010010 (c)

A maneira convencional de fazer isso seria primeiro calcular (a + b) e, em seguida, calcular ((a + b) + c). Carry-save aritmética funciona abandonando qualquer tipo de propagação de carry. Ele calcula a soma dígito a dígito, como: 

  10111010101011011111000000001101
+ 11011110101011011011111011101111
+ 00010010101101110101001101010010
= 21132130303123132223112112112222

A notação não é convencional, mas o resultado ainda é inequívoco. Se assumirmos que os três números são a, be c. Então, aqui, o resultado será descrito como a soma de 2 números binários, onde o primeiro número, S, é simplesmente a soma obtida pela adição dos dígitos (sem qualquer propagação de transporte), ou seja, S i = a i ⊕ b i ⊕ c ie o segundo número, C, é composto de carregamentos das somas individuais anteriores, ou seja, C i + 1 = (a i b i ) + (b i c i ) + (c i a i ): 

  01110110101101110001110110110000 and
 100110101010110111110010010011110

Agora, esses 2 números podem ser enviados para um somador de propagação de transporte que produzirá o resultado.

Isso era muito vantajoso de uma perspectiva de atraso (tempo de computação). Se você fosse somar esses 3 números usando métodos convencionais, levaria 2 atrasos do somador de propagação de transporte para chegar à resposta. Se você usar a técnica carry-save, precisará de apenas 1 atraso de somador de propagação de transporte e 1 atraso de somador completo (que é muito menor do que um atraso de propagação de transporte). Portanto, os somadores de CSA são normalmente muito rápidos.

Carry-save acumuladores

Supondo que temos dois bits de armazenamento por dígito, podemos usar uma representação binária redundante , armazenando os valores 0, 1, 2 ou 3 em cada posição de dígito. Portanto, é óbvio que mais um número binário pode ser adicionado ao nosso resultado de carry-save sem estourar nossa capacidade de armazenamento: mas e depois?

A chave do sucesso é que, no momento de cada adição parcial, adicionamos três bits:

  • 0 ou 1, do número que estamos adicionando.
  • 0 se o dígito em nossa loja for 0 ou 2, ou 1 se for 1 ou 3.
  • 0 se o dígito à sua direita for 0 ou 1, ou 1 se for 2 ou 3.

Em outras palavras, estamos pegando um dígito de transporte da posição à nossa direita e passando um dígito de transporte para a esquerda, assim como na adição convencional; mas o dígito de transporte que passamos para a esquerda é o resultado do cálculo anterior e não o atual. Em cada ciclo de clock, os carregadores precisam apenas se mover uma etapa adiante, e não n etapas como na adição convencional.

Como os sinais não precisam se mover tanto, o relógio pode bater muito mais rápido. ..

Ainda há a necessidade de converter o resultado em binário no final de um cálculo, o que efetivamente significa apenas deixar o transporte percorrer todo o número, como em um somador convencional. Mas se tivermos feito 512 adições no processo de execução de uma multiplicação de 512 bits, o custo dessa conversão final é efetivamente dividido entre essas 512 adições, de modo que cada adição arca com 1/512 do custo dessa adição "convencional" final.

Desvantagens

Em cada estágio de uma adição de transporte e salvamento,

  1. Nós sabemos o resultado da adição imediatamente.
  2. Nós ainda não sabemos se o resultado da adição é maior ou menor do que um determinado número (por exemplo, não sabemos se é positivo ou negativo).

Este último ponto é uma desvantagem ao usar somadores de transporte e salvamento para implementar a multiplicação modular (multiplicação seguida por divisão, mantendo apenas o restante). Se não podemos saber se o resultado intermediário é maior ou menor que o módulo, como podemos saber se devemos subtrair o módulo?

A multiplicação de Montgomery , que depende do dígito mais à direita do resultado, é uma solução; embora mais parecido com a própria adição de transporte e salvamento, ele carrega uma sobrecarga fixa, de modo que uma sequência de multiplicações de Montgomery economiza tempo, mas uma única não. Felizmente a exponenciação, que é efetivamente uma sequência de multiplicações, é a operação mais comum na criptografia de chave pública.

A análise de erro cuidadosa permite que uma escolha seja feita sobre a subtração do módulo, mesmo que não saibamos com certeza se o resultado da adição é grande o suficiente para justificar a subtração. Para que isso funcione, é necessário que o projeto do circuito seja capaz de adicionar -2, -1, 0, +1 ou +2 vezes o módulo. A vantagem sobre a multiplicação de Montgomery é que não há sobrecarga fixa anexada a cada sequência de multiplicações.

Detalhes técnicos

A unidade carry-save consiste em n somadores completos , cada um dos quais calcula uma única soma e bit de transporte com base unicamente nos bits correspondentes dos três números de entrada. Dados os três números de n bits a , b e c , ele produz uma soma parcial ps e um shift-carry sc :

A soma total pode então ser calculada por:

  1. Mudando a sequência de carry sc deixada em um lugar.
  2. Anexando um 0 à frente ( bit mais significativo ) da sequência de soma parcial ps .
  3. Usando um somador de transporte de ondulação para somar esses dois e produzir o valor de ( n + 1) bits resultante .

Veja também

Notas

Referências

Leitura adicional