Somador de transporte antecipado - Carry-lookahead adder

Somador de 4 bits com carry lookahead

Um somador carry lookahead (CLA) ou somador rápido é um tipo de somador eletrônico usado em lógica digital. Um somador carry lookahead melhora a velocidade reduzindo a quantidade de tempo necessária para determinar os bits de transporte. Ele pode ser contrastado com o somador de transporte de ondulação (RCA) mais simples, mas geralmente mais lento, para o qual o bit de transporte é calculado junto com o bit de soma, e cada estágio deve esperar até que o bit de transporte anterior tenha sido calculado para começar a calcular o seu próprio soma o bit e transporta o bit. O somador carry lookahead calcula um ou mais bits carry antes da soma, o que reduz o tempo de espera para calcular o resultado dos bits de valor maior do somador.

Já em meados de 1800, Charles Babbage reconheceu a penalidade de desempenho imposta pelo ripple-carry usado em sua Máquina Diferencial e, subsequentemente, projetou mecanismos para antecipar o transporte de sua (nunca construída) Máquina Analítica . Acredita-se que Konrad Zuse tenha implementado o primeiro somador carry lookahead em seu computador mecânico binário dos anos 1930, o Zuse Z1 . Gerald B. Rosenberger, da IBM, entrou com o pedido de patente de um moderno somador binário carry lookahead em 1957.

Duas implementações amplamente utilizadas do conceito são o adicionador Kogge-Stone (KSA) e o adicionador Brent-Kung (BKA).

Teoria de Operação

Adição de ondulação

Um somador binário de transporte de ondulação funciona da mesma maneira que métodos de adição de lápis e papel. Começando na posição do dígito mais à direita ( menos significativo ), os dois dígitos correspondentes são adicionados e um resultado é obtido. Também é possível que haja uma execução desta posição do dígito; por exemplo, "9 + 5 = 4, carregue 1". A aritmética binária funciona da mesma maneira, com menos dígitos. Neste caso, existem apenas quatro operações possíveis, 0 + 0, 0 + 1, 1 + 0 e 1 + 1. O último desses casos gera um transporte. Conseqüentemente, todas as posições dos dígitos, exceto a mais à direita, precisam levar em consideração a possibilidade de ter que adicionar um 1 extra para carregar os dígitos uma posição à direita.

Isso significa que nenhuma posição de dígito pode ter um valor absolutamente final até que seja estabelecido se um transporte está vindo da direita ou não. Além disso, se a soma sem transporte for 9 (nos métodos de lápis e papel) ou 1 (na aritmética binária), nem mesmo é possível dizer se uma determinada posição de dígito vai ou não passar um transporte para o posição à sua esquerda. Na pior das hipóteses, quando uma sequência inteira de somas chega a ... 99999999 ... (em decimal) ou ... 11111111 ... (em binário), nada pode ser deduzido até que o valor do transporte vindo da direita seja conhecido, e esse transporte é então propagado para a esquerda, um passo de cada vez, conforme cada posição de dígito avaliada "9 + 1 = 0, transporta 1" ou "1 + 1 = 0, transporta 1". É a "ondulação" do carry da direita para a esquerda que dá a uma víbora de carry por ondulação seu nome e sua lentidão. Ao adicionar inteiros de 32 bits, por exemplo, deve-se levar em consideração a possibilidade de que um transporte tenha que se espalhar por cada um dos 32 somadores de um bit.

Olhe para frente

O transporte à frente depende de duas coisas:

Calculando para cada posição de dígito se essa posição irá propagar um transporte se alguém vier da direita.
Combinando esses valores calculados, é possível deduzir rapidamente se, para cada grupo de dígitos, aquele grupo vai propagar um transporte que vem da direita.

Supondo que grupos de quatro dígitos sejam escolhidos, a sequência de eventos é mais ou menos assim:

Todos os somadores de 1 bit calculam seus resultados. Simultaneamente, as unidades de lookahead realizam seus cálculos.
Supondo que um carry surja em um grupo específico, esse carry surgirá na extremidade esquerda do grupo dentro de no máximo cinco atrasos de porta e começará a se propagar pelo grupo à sua esquerda.
Se esse carry vai se propagar por todo o próximo grupo, a unidade de lookahead já terá deduzido isso. Assim, antes que o transporte emerja do próximo grupo , a unidade de lookahead é imediatamente (dentro de um atraso de porta) capaz de dizer ao próximo grupo à esquerda que vai receber um transporte - e, ao mesmo tempo, informar o próxima unidade de lookahead à esquerda que um carry está a caminho.

O efeito líquido é que os transportes começam se propagando lentamente através de cada grupo de 4 bits, assim como em um sistema de transporte ondulatório, mas depois se movem quatro vezes mais rápido, saltando de uma unidade de transporte de antevisão para a próxima. Finalmente, dentro de cada grupo que recebe um transporte, o transporte se propaga lentamente dentro dos dígitos desse grupo.

Quanto mais bits em um grupo, mais complexa se torna a lógica de carry lookahead e mais tempo é gasto nas "estradas lentas" em cada grupo, em vez de na "estrada rápida" entre os grupos (fornecido pela lógica de carry lookahead) . Por outro lado, quanto menos bits há em um grupo, mais grupos precisam ser percorridos para ir de uma extremidade a outra de um número e, como resultado, menos aceleração é obtida.

Decidir o tamanho do grupo a ser governado pela lógica de carry lookahead requer uma análise detalhada dos atrasos de porta e propagação para a tecnologia específica que está sendo usada.

É possível ter mais de um nível de lógica lookahead-carry, e isso geralmente é feito. Cada unidade de carry lookahead já produz um sinal dizendo "se um carry vier da direita, irei propagá-lo para a esquerda", e esses sinais podem ser combinados de forma que cada grupo de, digamos, quatro unidades de carry lookahead torne-se parte de um "supergrupo" governando um total de 16 bits dos números que estão sendo adicionados. A lógica de transporte à frente do "supergrupo" será capaz de dizer se um transporte que entra no supergrupo será propagado por todo o caminho, e usando esta informação, ele é capaz de propagar transportes da direita para a esquerda 16 vezes mais rápido que um ingênuo ripple carry. Com este tipo de implementação de dois níveis, um carry pode primeiro se propagar através da "estrada lenta" de somadores individuais e, em seguida, ao atingir a extremidade esquerda de seu grupo, propagar-se pela "estrada rápida" de lookahead- de 4 bits a lógica de transporte, então, ao atingir a extremidade esquerda de seu supergrupo, se propaga através da "estrada super rápida" da lógica de transporte antecipado de 16 bits.

Novamente, os tamanhos dos grupos a serem escolhidos dependem dos detalhes exatos de quão rápido os sinais se propagam dentro das portas lógicas e de uma porta lógica para outra.

Para números muito grandes (centenas ou mesmo milhares de bits), a lógica lookahead-carry não se torna mais complexa, porque mais camadas de supergrupos e supergrupos podem ser adicionadas conforme necessário. O aumento no número de portas também é moderado: se todos os tamanhos de grupo fossem quatro, um terminaria com um terço das unidades de transporte à frente do que somadores. No entanto, as "estradas lentas" no caminho para os níveis mais rápidos começam a prejudicar todo o sistema (por exemplo, um somador de 256 bits poderia ter até 24 atrasos de porta em seu processamento de transporte) e a mera transmissão física de sinais de uma ponta a outra de um número longo começa a ser um problema. Nesses tamanhos, somadores de carry save são preferíveis, já que eles não perdem tempo na propagação de carry.

Carry lookahead method

Implementação de somador de 4 bits com carry lookahead

A lógica de carry lookahead usa os conceitos de geração e propagação de carregamentos. Embora no contexto de um somador carry lookahead, seja mais natural pensar em gerar e propagar no contexto de adição binária, os conceitos podem ser usados de forma mais geral do que isso. Nas descrições abaixo, a palavra dígito pode ser substituída por bit quando se refere à adição binária de 2.

Diz- se que a adição de duas entradas A e B de 1 dígito gera se a adição sempre carregará, independentemente de haver um transporte de entrada (de forma equivalente, independentemente de haver dígitos menos significativos no transporte de soma). Por exemplo, na adição decimal 52 + 67, a adição dos dígitos das dezenas 5 e 6 é gerada porque o resultado chega ao dígito das centenas, independentemente de o dígito da unidade ser transportado; no exemplo, o dígito da unidade não é válido (2 + 7 = 9). Mesmo se os números fossem, digamos, 54 e 69, a adição dos dígitos das dezenas 5 e 6 ainda geraria porque o resultado mais uma vez carrega para o dígito das centenas, apesar de 4 e 9 criarem um carregamento.

No caso de adição binária, gera se e somente se A e B forem 1. Se escrevermos para representar o predicado binário que é verdadeiro se e somente se gerar, temos ${\ displaystyle A + B}$ ${\ displaystyle G (A, B)}$ ${\ displaystyle A + B}$

{\ displaystyle G (A, B) = A \ cdot B}

onde é uma conjunção lógica (ou seja, um e ). ${\ displaystyle A \ cdot B}$

Diz- se que a adição de duas entradas A e B de 1 dígito se propaga se a adição for transportada sempre que houver transporte de entrada (equivalentemente, quando o próximo dígito menos significativo na soma for transportado). Por exemplo, na adição decimal 37 + 62, a adição dos dígitos das dezenas 3 e 6 se propagam porque o resultado seria transportado para o dígito das centenas se os uns fossem transportados (o que, neste exemplo, não ocorre). Observe que propagar e gerar são definidos em relação a um único dígito de adição e não dependem de quaisquer outros dígitos na soma.

No caso de adição binária, propaga se e somente se pelo menos um de A ou B for 1. Se for escrito para representar o predicado binário que é verdadeiro se e somente se se propagar, um ${\ displaystyle A + B}$ ${\ displaystyle P (A, B)}$ ${\ displaystyle A + B}$

{\ displaystyle P (A, B) = A + B}

onde no lado direito da equação está uma disjunção lógica (ou seja, um ou ). ${\ displaystyle A + B}$

Às vezes, uma definição ligeiramente diferente de propagação é usada. Por esta definição, diz-se que A + B se propaga se a adição for transportada sempre que houver transporte de entrada, mas não será transportado se não houver transporte de entrada. Devido à maneira como os bits de geração e propagação são usados pela lógica de carry lookahead, não importa qual definição é usada. No caso de adição binária, esta definição é expressa por

{\ displaystyle P '(A, B) = A \ oplus B}

onde é um ou exclusivo ( ou seja, um xor ). ${\ displaystyle A \ oplus B}$

${\ displaystyle A}$	${\ displaystyle B}$	${\ displaystyle C_ {i}}$	${\ displaystyle C_ {o}}$	Tipo de transporte
0	0	0	0	Nenhum
0	0	1	0	Nenhum
0	1	0	0	Nenhum
0	1	1	1	Propagar
1	0	0	0	Nenhum
1	0	1	1	Propagar
1	1	0	1	Gerar
1	1	1	1	Gerar / Propagar

Tabela mostrando quando os carregamentos são propagados ou gerados.

Para aritmética binária, or é mais rápido que xor e requer menos transistores para implementar. No entanto, para um somador de carry lookahead de vários níveis, é mais simples de usar . ${\ displaystyle P '(A, B)}$

Dados esses conceitos de gerar e propagar, um dígito de adição é transportado precisamente quando a adição gera ou o próximo bit menos significativo é transportado e a adição se propaga. Escrito em álgebra booleana, com o carry de dígitos i e e a propagar e gerar pedaços de dígitos i , respectivamente, ${\ displaystyle C_ {i}}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle G_ {i}}$

{\ displaystyle C_ {i + 1} = G_ {i} + (P_ {i} \ cdot C_ {i}).}

Detalhes de implementação

Para cada bit em uma sequência binária a ser adicionado, a lógica de carry lookahead determinará se esse par de bits gerará um transporte ou propagará um transporte. Isso permite que o circuito "pré-processe" os dois números que estão sendo adicionados para determinar o transporte antecipado. Então, quando a adição real é realizada, não há atraso de esperar pelo efeito de propagação do carry (ou o tempo que leva para o carry do primeiro somador completo ser passado para o último somador completo). Abaixo está um circuito de carry lookahead generalizado de 4 bits que se combina com o somador de ripple carry de 4 bits que usamos acima com alguns pequenos ajustes:

Para o exemplo fornecido, a lógica para os valores generate ( ) e propagate ( ) são fornecidos abaixo. O valor numérico determina o sinal do circuito acima, começando de 0 na extrema direita a 3 na extrema esquerda: ${\ displaystyle G}$ ${\ displaystyle P}$

{\ displaystyle C_ {1} = G_ {0} + P_ {0} \ cdot C_ {0},}

{\ displaystyle C_ {2} = G_ {1} + P_ {1} \ cdot C_ {1},}

{\ displaystyle C_ {3} = G_ {2} + P_ {2} \ cdot C_ {2},}

{\ displaystyle C_ {4} = G_ {3} + P_ {3} \ cdot C_ {3}.}

Substituindo para , em seguida, para , em seguida, em rendimentos as seguintes equações expandidos: ${\ displaystyle C_ {1}}$ ${\ displaystyle C_ {2}}$ ${\ displaystyle C_ {2}}$ ${\ displaystyle C_ {3}}$ ${\ displaystyle C_ {3}}$ ${\ displaystyle C_ {4}}$

{\ displaystyle C_ {1} = G_ {0} + P_ {0} \ cdot C_ {0},}

{\ displaystyle C_ {2} = G_ {1} + G_ {0} \ cdot P_ {1} + C_ {0} \ cdot P_ {0} \ cdot P_ {1},}

{\ displaystyle C_ {3} = G_ {2} + G_ {1} \ cdot P_ {2} + G_ {0} \ cdot P_ {1} \ cdot P_ {2} + C_ {0} \ cdot P_ {0 } \ cdot P_ {1} \ cdot P_ {2},}

{\ displaystyle C_ {4} = G_ {3} + G_ {2} \ cdot P_ {3} + G_ {1} \ cdot P_ {2} \ cdot P_ {3} + G_ {0} \ cdot P_ {1 } \ cdot P_ {2} \ cdot P_ {3} + C_ {0} \ cdot P_ {0} \ cdot P_ {1} \ cdot P_ {2} \ cdot P_ {3}.}

Para determinar se um par de bits irá gerar um transporte, a seguinte lógica funciona:

{\ displaystyle G_ {i} = A_ {i} \ cdot B_ {i}.}

Para determinar se um par de bits propagará um transporte, uma das seguintes instruções lógicas funciona:

{\ displaystyle P_ {i} = A_ {i} \ oplus B_ {i},}

{\ displaystyle P_ {i} = A_ {i} + B_ {i}.}

A razão pela qual isso funciona é baseada na avaliação de . A única diferença nas tabelas de verdade entre ( ) e ( ) é quando ambos e são 1. No entanto, se ambos e são 1, então o termo é 1 (já que sua equação é ), e o termo se torna irrelevante. O XOR é usado normalmente em um circuito somador completo básico; o OR é uma opção alternativa (para um carry lookahead apenas), que é muito mais simples em termos de contagem de transistores. ${\ displaystyle C_ {1} = G_ {0} + P_ {0} \ cdot C_ {0}}$ ${\ displaystyle A \ oplus B}$ ${\ displaystyle A + B}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle G_ {0}}$ ${\ displaystyle A \ cdot B}$ ${\ displaystyle P_ {0} \ cdot C_ {0}}$

O somador de 4 bits carry lookahead também pode ser usado em um circuito de nível superior fazendo com que cada circuito lógico CLA produza uma propagação e gere sinal para um circuito lógico CLA de nível superior. O grupo propagate ( ) e group generate ( ) para um CLA de 4 bits são: ${\ displaystyle PG}$ ${\ displaystyle GG}$

{\ displaystyle PG = P_ {0} \ cdot P_ {1} \ cdot P_ {2} \ cdot P_ {3},}

{\ displaystyle GG = G_ {3} + G_ {2} \ cdot P_ {3} + G_ {1} \ cdot P_ {3} \ cdot P_ {2} + G_ {0} \ cdot P_ {3} \ cdot P_ {2} \ cdot P_ {1}.}

Eles podem então ser usados para criar um carry-out para esse grupo de 4 bits específico:

{\ displaystyle CG = GG + PG \ cdot C_ {in}.}

Pode-se ver que isso é equivalente ao das equações anteriores. ${\ displaystyle C_ {4}}$

Colocar quatro CLAs de 4 bits juntos produz quatro propagações de grupo e quatro gerações de grupo. Uma unidade lookahead-carry (LCU) assume esses 8 valores e usa lógica idêntica para calcular nos CLAs. A LCU então gera a entrada de transporte para cada um dos 4 CLAs e um quinto igual a . ${\ displaystyle C_ {i}}$ ${\ displaystyle C_ {16}}$

O cálculo do atraso de porta de um somador de 16 bits (usando 4 CLAs e 1 LCU) não é tão direto quanto o somador de carry por ondulação.

Começando no tempo de zero:

cálculo de e é feito no tempo 1, ${\ displaystyle P_ {i}}$ ${\ displaystyle G_ {i}}$
o cálculo de é feito no tempo 3, ${\ displaystyle C_ {i}}$
o cálculo de é feito no tempo 2, ${\ displaystyle PG}$
o cálculo de é feito no tempo 3, ${\ displaystyle GG}$
o cálculo das entradas para os CLAs da LCU é feito em:
- tempo 0 para o primeiro CLA,
- tempo 5 para o segundo, terceiro e quarto CLA,
o cálculo do é feito em: ${\ displaystyle S_ {i}}$ $Si}$
- tempo 4 para o primeiro CLA,
- tempo 8 para o segundo, terceiro e quarto CLA,
o cálculo do bit de transporte final ( ) é feito no tempo 5. ${\ displaystyle C_ {16}}$

O tempo máximo é de 8 atrasos de porta (para ). ${\ displaystyle S _ {[8-15]}}$

Um somador ripple-carry padrão de 16 bits levaria 16 × 3 - 1 = 47 atrasos de porta.

Corrente de transporte manchester

A cadeia de transporte Manchester é uma variação do somador carry lookahead que usa lógica compartilhada para diminuir a contagem de transistores. Como pode ser visto acima na seção de implementação, a lógica para gerar cada transporte contém toda a lógica usada para gerar os transportes anteriores. Uma cadeia de transporte Manchester gera os transportes intermediários, derivando nós na porta que calcula o valor de transporte mais significativo. No entanto, nem todas as famílias lógicas têm esses nós internos, sendo o CMOS um exemplo importante. A lógica dinâmica pode suportar a lógica compartilhada, assim como a lógica da porta de transmissão . Uma das principais desvantagens da cadeia de carry Manchester é que a carga capacitiva de todas essas saídas, junto com a resistência dos transistores, faz com que o atraso de propagação aumente muito mais rapidamente do que um carry lookahead normal. Uma seção de cadeia de transporte de Manchester geralmente não excede 4 bits.

Veja também

Referências

Leitura adicional

Algoritmos de hardware para módulos aritméticos , grupo de pesquisa ARITH, Aoki lab., Tohoku University
Katz, Randy (1994). Design Lógico Contemporâneo . Microelectronics Journal . 26 . Benjamin / Cummings Publishing Company . pp. 249-256 . doi : 10.1016 / 0026-2692 (95) 90052-7 . ISBN 0-8053-2703-7.
Savard, John JG (2018) [2006]. "Técnicas Aritméticas Avançadas" . quadibloc . Arquivado do original em 03/07/2018 . Página visitada em 16/07/2018 .

links externos

Carry Look Ahead Adder Simulador JavaScript

Languages

In other projects