Capitulo-6

Prévia do material em texto

Digital Design 
Copyright © 2006 
Frank Vahid 
1 
Sistemas Digitais 
Capítulo 6: 
Otimizações e Tradeoffs 
Slides to accompany the textbook Digital Design, First Edition, 
by Frank Vahid, John Wiley and Sons Publishers, 2007. 
http://www.ddvahid.com 
Copyright © 2007 Frank Vahid 
Instructors of courses requiring Vahid's Digital Design textbook (published by John Wiley and Sons) have permission to modify and use these slides for customary course-related activities, 
subject to keeping this copyright notice in place and unmodified. These slides may be posted as unanimated pdf versions on publicly-accessible course websites.. PowerPoint source (or pdf 
with animations) may not be posted to publicly-accessible websites, but may be posted for students on internal protected sites or distributed directly to students by other electronic means. 
Instructors may make printouts of the slides available to students for a reasonable photocopying charge, without incurring royalties. Any other use requires explicit permission. Instructors 
may obtain PowerPoint source or obtain special use permissions from Wiley – see http://www.ddvahid.com for information. 
Material traduzido e adaptado para o 
Português pelo Prof. Ricardo O. Duarte e 
revisado pelos Profs. Luciano Pimenta e 
Hermes Magalhães 
DELT – EEUFMG 
(Rev. 6c) 
Digital Design 
Copyright © 2006 
Frank Vahid 
2 
Introdução 
• Aprendemos como projetar circuitos digitais combinacionais. 
– Será que podemos projetar circuitos mais eficientes? 
• Vamos considerar dois critérios para tomada de decisões em projetos: 
– Atrasos (delays) – o tempo em que uma mudança de valor das entradas 
produz um valor estável e correto na saída. 
– Tamanho – o número de transistores 
– Em uma estimativa rápida, assuma que: 
• Cada porta lógica tem um atraso de “1 atraso-porta” 
• Cada entrada de uma porta demanda 2 transistores 
• Ignore portas NOT (inversoras) 
6.1 
16 transistores 
2 atrasos-porta 
F1 
w 
x 
y 
w 
x 
y 
F1 = wxy + wxy’ 
(a) 
4 transistores 
1 atraso-porta 
F2 
F2 = wx 
(b) 
w 
x 
= wx(y+y’) = wx 
Transformando F1 em F2 significa 
uma otimização: Melhora em 
todos os critérios de interesse que 
acabamos de selecionar. 
(c) 
20 
15 
10 
5 
F1 
F2 
1 2 3 4 
Atrasos (atraso-portas) 
ta
m
a
n
h
o
 
(t
ra
n
s
is
to
re
s
) 
Note: Slides with animation are denoted with a small red "a" near the animated items 
Digital Design 
Copyright © 2006 
Frank Vahid 
3 
Introdução 
• Tradeoff – Relação de compromisso entre critérios de 
otimização. 
– Melhora alguns critérios, mas piora outros, conforme critérios de 
interesse no projeto. Transformando G1 em G2 
representa um tradeoff: 
Alguns critérios apresentam 
resultados melhores enquanto 
pioram outros. 
14 transistores 
2 atrasos-porta 
12 transistores 
3 atrasos-porta 
G1 G2 
w w 
x 
y 
z 
x 
w 
y 
z 
G1 = wx + wy + z G2 = w(x+y) + z 
20 
15 
10 
5 
G1 
G2 
1 2 3 4 
Atrasos (atraso-porta) 
ta
m
a
n
h
o
 
(t
ra
n
s
is
to
re
s
) 
Digital Design 
Copyright © 2006 
Frank Vahid 
4 
Introdução 
• Preferimos o caso ótimo, mas conviveremos com tradeoffs 
na maioria dos casos. 
– Podemos fabricar um carro que é o mais confortável, o mais 
econômico e o mais rápido. Mas certamente algumas dessas 
características serão prejudicadas para se alcançar os objetivos. 
atraso atraso 
Otimizações 
Tradeoffs 
Todos os critérios de 
interesse são 
melhorados (ou pelo 
menos mantidos com 
o mesmo valor) 
Alguns critérios de 
interesse são 
melhorados, enquanto 
outros não. ta
m
a
n
h
o
 
ta
m
a
n
h
o
 
Digital Design 
Copyright © 2006 
Frank Vahid 
5 
Otimizações em Lógica Combinacional e Tradeoffs 
• Otimização em Lógica de Dois-níveis 
usando métodos algébricos. 
– Objetivo: circuito somente com 2 níveis 
de portas (OR de portas AND), com o 
mínimo de transistores 
• Definimos o problema de forma 
algébrica. 
– Soma de produtos gera lógica de 2 níveis 
• F = abc + abc’ está na forma de soma de 
produtos; G = w(xy + z) não. 
– Transforme a equação de soma de 
produtos de forma a ter menos termos e 
menos literais. 
• Cada literal e cada termo é convertido em 
uma entrada por porta, cada qual é 
convertido em transistores. 
• Ignore portas NOT (para simplificar) 
6.2 
F = xyz + xyz’ + x’y’z’ + x’y’z 
F = xy(z + z’) + x’y’(z + z’) 
F = xy*1 + x’y’*1 
F = xy + x’y’ 
0 
1 
x’ y’ 
n 
y’ 
x’ 
0 
1 
m 
m 
n 
n 
F 
0 
1 
y 
m 
y 
x 
x 
F 
x 
y 
x’ 
y’ 
m 
n 
4 literais + 2 
termos = 6 
entradas-porta 
6 entradas-porta 
= 12 transistores 
Nota: Assumindo 4-transistores: circuitos AND/OR de 2-entradas; 
Na realidade, somente NAND/NOR são usadas. 
Exemplo 
Digital Design 
Copyright © 2006 
Frank Vahid 
6 
Método Algébrico para Minimização de Número 
de transistores com lógica de 2-níveis. 
• O exemplo anterior mostrou métodos de 
otimização algébricos mais comuns 
– Coloque a equação na forma de soma de 
produtos 
– Simplifique o máximo possível 
• ab + ab’ = a(b + b’) = a*1 = a 
• “Combinando termos para eliminar variáveis” 
– Duplicar termos às vezes é necessário para 
se alcançar uma maior simplificação 
• Note que não altera em nada a função 
– c + d = c + d + d = c + d + d + d + d ... 
– Após combinar termos repetidos, pode-se 
alcançar uma maior simplificação. 
 
F = xyz + xyz’ + x’y’z’ + x’y’z 
F = xy(z + z’) + x’y’(z + z’) 
F = xy*1 + x’y’*1 
F = xy + x’y’ 
F = x’y’z’ + x’y’z + x’yz 
F = x’y’z’ + x’y’z + x’y’z + x’yz 
F = x’y’(z+z’) + x’z(y’+y) 
F = x’y’ + x’z 
G = xy’z’ + xy’z + xyz + xyz’ 
G = xy’(z’+z) + xy(z+z’) 
G = xy’ + xy (novamente) 
G = x(y’+y) 
G = x 
a 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
7 
Mapas de Karnaugh para Minimização de Número 
de transistores com lógica de 2-níveis 
• Mapas de Karnaugh (Mapas K) 
– Método Gráfico criado para encontrarmos 
termos que podem ser combinados para eliminar 
variáveis de forma a obter o mínimo. 
– Mintermos diferindo-se de uma variável ficam 
adjacentes (vizinhos) no mapa 
– Podemos visualizar claramente os casos 
possíveis de combinação de termos – olhamos 
para os “1s” adjacentes. 
• Para F, vemos duas situações. 
• Círculo do topo a esquerda gera a redução de 
x’y’z’+x’y’z = x’y’(z’+z) = x’y’(1) = x’y’ 
• Desenhe circulos, escreva o termo que tem todos 
os literais exceto o(s) literal(is) que muda(m) no 
interior do círculo. 
– Círculo xy, x=1 & y=1 em ambas as células do 
círculo, mas z muda (z=1 em uma célula, 0 na outra) 
• Função minimizada: OR dos termos encontrados 
 
 
 
F = x’y’z + xyz + xyz’ + x’y’z’ 
0 0 
0 0 
00 01 11 10 
0 
1 
F yz 
x 
1 
x ’ y ’ 
1 1 0 0 
00 01 11 10 
0 0 
0 
1 1 1 
F yz 
x 
x y 
x’y’z’ 
00 01 11 10 
0 
1 
x’y’z x’yz x’yz’ 
xy’z’ xy’z xyz xyz’ 
F yz 
x 
1 
Note que não fica ordenado 
de forma binária. 
Considere esquerda e direita 
também vizinhos 
1 1 
F = x’y’ + xy 
Mais fácil que o método 
algébrico: 
F = xyz + xyz’ + x’y’z’ + x’y’z 
F = xy(z + z’) + x’y’(z + z’) 
F = xy*1 + x’y’*1 
F = xy + x’y’ 
K-map 
a 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
8 
Mapas K 
• Quatros “1s” vizinhos 
significa que duas variáveis 
podem ser eliminadas. 
– Desenhe um círculo grande 
envolvendo os 4 “1s”, 
simplifica a transformação 
algébrica acima. 
G = xy’z’ + xy’z + xyz + xyz’ 
G = x(y’z’+ y’z + yz + yz’) (deverá ser = 1) 
G = x(y’(z’+z) + y(z+z’)) 
G = x(y’+y) 
G = x 
0 0 0 0
00 01 11 10
1 1
0
1 1 1
G yz
x
x
0 0 0 0
00 01 11 10
1 1
0
1 1 1
G yz
x
xyxy’
Desenhe o maior círculo possível, 
ou você obterá mais termos do que 
você realmente precisará. 
Digital Design 
Copyright © 2006 
Frank Vahid 
9 
Mapas K 
• Quatro células vizinhas podem 
aparecer em formato de quadrado 
• É permitido envolver um “1”mais 
de uma vez. 
– Assim como um termo duplicado 
• Lembre: c + d = c + d + d 
• Não há necessidadeaparente de 
se cobrir um “1” mais de uma vez. 
– Produz termos adicionais – 
situação não minimizada 
0 1 1 0
00 01 11 10
0 1
0
1 1 0
H yz
x
z
H = x’y’z + x’yz + xy’z + xyz 
 (xy aparece em todas combinações) 
0 1 0 0 
00 01 11 10 
1 1 
0 
1 1 1 
I yz 
x 
x 
y ’ z 
Os dois círculos são a forma reduzida de: 
I = x’y’z + xy’z’ + xy’z + xyz + xyz’ 
I = x’y’z + xy’z + xy’z’ + xy’z + xyz + xyz’ 
I = (x’y’z + xy’z) + (xy’z’ + xy’z + xyz + xyz’) 
I = (y’z) + (x) 
1 1 0 0
00 01 11 10
0 1
0
1 1 0
J yz
x
xz
y’zx’y’
a 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
10 
Mapas K 
• Círculos podem atravessar da 
direita para a esquerda 
– Lembrem: os lados são vizinhos 
• Mintermos se diferem em uma 
única variável. 
• Círculos deverão ter 1, 2, 4, ou 
8 células – 3, 5, ou 7 não são 
permitidos. 
– 3/5/7 não correspondem a 
transformações algébricas válidas 
para eliminar variáveis. 
• Circular todas células também 
é permitido 
– Produz uma função = 1 
0 1 0 0
00 01 11 10
1 0
0
1 0 1
K yz
x
xz’
x’y’z
0 0 0 0
00 01 11 10
1 1
0
1 1 0
L yz
x
1 1 1 1
1
00 01 11 10
1 1
0
1 1 1
E yz
x
Digital Design 
Copyright © 2006 
Frank Vahid 
11 
Mapas K de 4 variáveis 
• Mapas K de 4 variáveis seguem 
o mesmo princípio: 
– Células vizinhas diferem-se de uma 
única variável. 
– Esquerda/Direita são vizinhas 
– Topo/Base também são 
• Mapas de 5 e 6 também existem 
– Mas são mais difíceis de visualisar, 
mas também são ainda viáveis. 
• Mapas de 2 variáveis existem 
– Mas não são muito úteis – melhor 
simplificar algebricamente 
0 0 1 0
00 01 11 10
1 1
00
01 1 0
0 0 1 0
0 0
11
10 1 0
F yz
wx
yz
w
’x
y
’
0 1 1 0
00 01 11 10
0 1
00
01 1 0
0 1 1 0
0 1
11
10 1 0
G yz
wx
z
0 1 
0 
1 
F z 
y 
G=z 
F=w’xy’+yz 
Digital Design 
Copyright © 2006 
Frank Vahid 
12 
Mapas K para Minimização de Número de 
transistores com lógica de 2-níveis 
Método geral 
1. Converta a equação na forma de 
soma de produtos. 
2. Coloque 1s nas células referentes 
a cada termo da equação. 
3. Circule todos os 1s, desenhando o 
menor número de maiores círculos 
possíveis com cada 1 incluído em 
pelo menos um círculo. Escreva o 
termo correspondente para cada 
círculo. 
4. Faça um OR de todos os termos 
resultantes para obter a função 
minimizada. 
Exemplo: Minimize: 
 G = a + a’b’c’ + b*(c’ + bc’) 
1. Converto em soma de produtos 
 G = a + a’b’c’ + bc’ + bc’ 
2. Coloco 1s nas respectivas células 
 
0 0 
00 01 11 10 
0 
1 
G bc 
a 
1 
bc’ 
1 a’b’c’ 
1 1 1 1 
a 
a 
3. Circule os 1s 
 
1 0 0 1 
00 01 11 10 
1 1 
0 
1 1 1 
G bc 
a 
a 
c ’ 
4. Faço um OR com os termos 
circulados: G = a + c’ 
 
Digital Design 
Copyright © 2006 
Frank Vahid 
13 
• Minimizar: 
– H = a’b’(cd’ + c’d’) + ab’c’d’ + ab’cd’ 
+ a’bd + a’bcd’ 
1. Converto para soma de produtos: 
– H = a’b’cd’ + a’b’c’d’ + ab’c’d’ + 
ab’cd’ + a’bd + a’bcd’ 
2. Coloco 1s nas células do Mapa K 
3. Circulo os 1s 
4. Faço um OR dos termos obtidos 
Mapas K para Minimização de Número de 
transistores com lógica de 2-níveis - Exemplo 
1 1 
00 01 11 10 
00 
01 1 1 1 
1 
11 
10 
0 0 
0 
0 0 0 0 
0 0 1 
H c d 
ab 
a 
a ’ bd 
a ’ bc 
b ’ d ’ 
Esquerda/Direita são vizinhos 
Topo/Base são vizinhos 
a’b’c’d’ 
ab’c’d’ a’bd 
a’b’cd’ 
ab’cd’ 
a’bcd’ 
H = b’d’ + a’bc + a’bd 
Digital Design 
Copyright © 2006 
Frank Vahid 
14 
Entradas Indiferentes (X – Don’t Cares) 
• O que fazer se uma combinação em particular 
da entrada não importa para uma dada 
função? (por exemplo, uma condição que nunca ocorre) 
– Ex.: Minimize F = xy’z’, dado que x’y’z’ (xyz=000) não 
está previsto para ocorrer, e xy’z (xyz=101) também 
não. 
– Portanto, não importa qual será a saída F quando x’y’z’ 
ou xy’z for 1, porque esses casos não estão previstos 
para ocorrer. 
– Logo, faça F ser 1 ou 0 para esses caso de forma a 
melhor minimizar a equação final. 
• No mapa K 
– Escreva Xs (don’t cares) para esses casos 
• Inclua X no círculo SOMENTE se ele contribuir para 
minimizar a equação (assuma 1 para estes X). 
• Não inclua outros Xs desnecessariamente nos círculos 
(assuma zero para estes X) 
 Resumindo: faça o que lhe for 
conveniente para obter a melhor 
simplificação ! 
X 0 0 0
00 01 11 10
1 X
0
1 0 0
F yz y’z’
x
X 0 0 0
00 01 11 10
1 X
0
1 0 0
F yz y’z’ unneeded
xy’
x
Bom uso dos don’t cares 
Uso desnecessário dos don’t 
cares; 
Resulta em um termo a mais. 
Digital Design 
Copyright © 2006 
Frank Vahid 
15 
Exemplo de Minimização com Don’t Cares 
• Minimizar: 
– F = a’bc’ + abc’ + a’b’c 
– Dado as seguintes situações 
onde ocorre don’t cares: a’bc, 
abc 
• Obs.: Use don’t cares com 
atenção. 
– Certifique-se que o termo é 
realmente irrelevante para a 
função pedida. 
00 01 11 10 
0 
0 0 
0 
1 
F bc 
a 
’ c a b 
a 
1 1 
1 
X 
X 
F = a’c + b 
Digital Design 
Copyright © 2006 
Frank Vahid 
16 
Exemplo de Minimização com Don’t Cares 
Chave Deslizante (Sliding Switch) 
• Chave com 5 posições 
– Produz a posição em binário com 
3-bits. 
• Queremos um circuito que: 
– Produza saída 1 quando a chave 
estiver na posição 2, 3, or 4 
– Produza saída 0 quando a chave 
estiver na posição 1 or 5 
– Observe que a entrada de 3-bits 
nunca produzirá uma saída 
binária para o detector nos casos: 
0, 6, ou 7 
• Considere-as como entradas 
don’t care para essas 
combinações 
 
2,3,4, 
detector 
x 
y 
z 
1 2 3 4 5 
G 
0 0 1 1
00 01 11 10
1 0
0
1 0 0
G yz
x x’y
xy’z’
Sem 
don’t 
cares: 
G = x’y 
+ xy’z’ 
X 0 1 1
00 01 11 10
1 0
0
1 X X
G yz
x
y
z’
Com don’t 
cares: 
G = y + z’ 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
17 
Automatizando o processo de Minimização em 
Lógica de 2 níveis 
• Minimizando a mão 
– Complicado para funções com 5 ou 
mais variáveis 
– Podemos não obter a menor 
combinação (agrupamento de 1s) 
dependendo da ordem que 
escolhermos. 
– Sujeito a erros (ser humano). 
• Minimização realizada por 
ferramentas computacionais. 
– Algoritmo exato: encontra as 
soluções ótimas. 
– Heuristicas: encontram boas 
soluções, mas não necessariamente 
as melhores 
1 1 1 0 
00 01 11 10 
1 0 
0 
1 1 1 
J yz 
x 
y ’ z ’ x ’ y ’ yz 
( a ) 
( b ) 
1 1 1 0 
00 01 11 10 
1 0 
0 
1 1 1 
J yz 
x 
y ’ z ’ x ’ z 
x y 
4 termos 
x y 
Somente 3 termos 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
18 
Conceitos básicos envolvendo Automação de 
Minimização em Lógica de 2 níveis 
• Definições 
– On-set: Todos os mintermos que 
produzem F=1 
– Off-set: Todos os mintermos que 
produzem F=0 
– Implicante: Qualquer termo 
(mintermo ou não) que produza F=1 
• No mapa K é representado por 
qualquer círculo válido (não 
necessariamente o maior círculo) 
• Cobrir: Implicante xy cobre os 
mintermos xyz e xyz’ 
– Expandir um termo: remover uma 
variável (círculo maior no mapa K) 
• xyz  xy é uma expansão de xyz 
0 1 0 0 
00 01 11 10 
0 0 
0 
1 1 1 
F yz 
x 
x y 
x yz ’ 
x yz 
x ’ y ’ z 
4 implicantes de F 
Obs.: Usamos o mapa K aqui somente 
como uma forma de ilustrar os conceitos; 
ferramentas computacionais não usam 
mapas K. 
• Implicantes primos : Máximo 
Implicante expandido – qualquer 
expansão cobriria um mintermo 
não pertencente ao on-set de F 
(cobriria um zero, modificando F) 
• x’y’z, e xy, acima 
• Mas não xyz ou xyz’ – eles 
poderiam ser expandidos. 
Digital Design 
Copyright © 2006 
Frank Vahid 
19 
Conceitos básicos envolvendo Automação de 
Minimização em Lógica de 2 níveis 
• Definições (continuação) 
– Implicantes primos (PI) essenciais: 
São os implicantes primos que 
cobrem um mintermo dos elementos 
do on-set que não é coberto por mais 
nenhum implicante. 
• Importância de se identificar os PI 
essenciais: Todos os PI essenciais 
em um agrupamento gerador 
(cobertura) devem serincluídos, 
pois contêm condições não cobertas 
por mais nenhum implicante. 
• Implicantes primos não essenciais 
podem ou não ser incluídos, 
dependendo se seus mintermos já 
foram cobertos por outros implicantes. 
1 1 0 
0 
0 
00 01 11 10 
1 
0 
1 1 1 
G yz 
x 
não essencial 
não essencial 
y ’ z 
x ’ y ’ 
xz x y essencial 
1 
essencial 
1 
Digital Design 
Copyright © 2006 
Frank Vahid 
20 
Método de Automação de 
Minimização em Lógica de 2 níveis 
• Passos 1 e 2 são exatos 
• Passo 3: Complicado. Checar todas as possibilidades produz a 
solução ótima, mas é computacionalmente lento. Solução: Checar 
algumas soluções, mas não todas → solução heurística. 
Digital Design 
Copyright © 2006 
Frank Vahid 
21 
Exemplo de Minimização em Lógica de 2 níveis 
automatizada (Quine-McCluskey) 
• 1. Determinamos todos os 
implicantes primos 
• 2. Adicionamos os PIs 
essenciais ao agrupamento 
final 
– Marcamos com fonte itálico os 
1s que já foram cobertos. 
– Somente um único 1 sobrou. 
• 3. Cubro o mintermo que 
sobrou com um Pis não 
essencial. 
– Escolho um dos 2 possíveis 
PIs 
1 1 1 0 
00 01 11 10 
1 0 
0 
1 0 1 
I yz 
x 
y ’ z ’ 
x ’ z 
xz ’ 
( c ) 
1 1 0 
00 01 11 10 
1 0 
0 
1 0 1 
I yz 
x 
1 1 1 0 
00 01 11 10 
1 0 
0 
1 0 1 
I yz 
x 
x ’ y ’ y ’ z ’ 
x ’ z 
xz ’ 
( b ) 
x ’ y ’ y ’ z ’ 
x ’ z 
xz ’ 
( a ) 
1 
1 
1 
Digital Design 
Copyright © 2006 
Frank Vahid 
22 
Problemas de Métodos que enumeram todos os 
Mintermos ou Computam todos os Implicantes Primos 
• Muitos mintermos para funções de muitas variáveis. 
– Funções com 32 variáveis de entrada: 
• 232 = 4 bilhões de mintermos possíveis. 
• Muito tempo/memória computacional 
• Muito tempo de processamento para gerar todos os 
implicantes primos. 
– Comparando cada mintermo com cada outro mintermo, para 32 
variáveis, é (4 billion)2 = 1 quatrilhão de operações computacionais. 
– Funções com muitas variáveis poderiam demandar dias, meses, 
anos ou mais em tempo computacional – Não é razoável!! 
 
 
 
Digital Design 
Copyright © 2006 
Frank Vahid 
23 
Solução para o Problema na forma Computacional 
• Solução 
– Não gerar todos os mintermos nem todos os implicantes primos 
– Em vez disso, basta tomar a equação de entrada, e tentar 
"iterativamente" melhorá-la 
 
Ex: F = abcdefgh + abcdefgh’+ jklmnop 
 
• Obs: 15 variáveis, poderia produzir milhares de mintermos 
• Mas pode minimizar apenas combinando os dois primeiros termos: 
– F = abcdefg(h+h’) + jklmnop = abcdefg + jklmnop 
Digital Design 
Copyright © 2006 
Frank Vahid 
24 
Minimização em Lógica de 2 níveis usando o 
Método Iterativo 
• Método: Aleatoriamente faça uma 
operação de “expansão”, verifique 
se produziu alguma melhoria. 
– Expansão: remoção de uma variável 
de um termo 
• Assim como expandir um círculo em 
um mapa K 
– i.e.: Expandindo x’z para z (OK), mas 
expandir x’z para x’ (não OK), na 
função mostrada. 
– Depois de expandir, remova outros 
termos cobertos pelo novo termo 
expandido. 
– Continue iterando até não obter mais 
melhorias 
 Ex: 
 F = abcdefgh + abcdefgh’+ jklmnop 
 F = abcdefg + abcdefgh’ + jklmnop 
 F = abcdefg + jklmnop 
0 1 1 0 
00 01 11 10 
0 1 
0 
1 1 0 
I yz 
x 
0 1 1 0 
00 01 11 10 
0 1 
0 
1 1 0 
I yz 
x 
xy’z 
x’z 
xyz 
z (a) 
(b) 
xyz xy’z 
x’z 
x ’ 
http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer 
Logic Friday (Espresso - Windows) http://sontrak.com/default.aspx 
Digital Design 
Copyright © 2006 
Frank Vahid 
25 
Otimização em Lógica Multi-Nível – Tradeoffs de 
Velocidade de Processamento/Tamanho 
• Nem sempre precisamos da velocidade de processamento 
proporcionada pela lógica de 2 níveis. 
– A lógica multi-nível pode produzir circuitos com um número menor de portas. 
– Exemplo: 
• F1 = ab + acd + ace  F2 = ab + ac(d + e) = a(b + c(d + e)) 
• Técnica: Eliminar literais → xy + xz = x(y+z) 
 
a 
c 
e 
c 
a 
a 
b 
d 
4 
F1 
F2 
F1 = ab + acd + ace 
(a) 
F2 = a(b+c(d+e)) 
(b) (c) 
22 transistores 
2 atrasos-porta 
16 transistores 
4 atrasos-porta 
a 
b 
c 
d 
e 
F1 
F2 
20 
15 
10 
5 
1 2 3 4 
Atraso (atrasos-porta) 
4 
4 
4 
4 
4 
6 
6 
6 ta
m
a
n
h
o
 
(t
ra
n
s
is
to
re
s
) 
Digital Design 
Copyright © 2006 
Frank Vahid 
26 
Exemplo Multi-nível 
• Aplique lógica multi-nível para reduzir o número de 
transistores de: F1 = abcd + abcef 
a 
• abcd + abcef = abc(d + ef) 
• Produz um número menor de portas, portanto um número menor de 
transistores. 
a 
b 
c 
e 
f 
b 
c 
a 
d 
F1 
F2 
F1 = abcd + abcef F2 = abc(d + ef) 
(a) (b) (c) 
22 transistores 
2 atrasos-porta 
18 transistores 
3 atrasos-porta 
a 
b 
c 
d 
e 
f 
F1 
F2 
20 
15 
10 
5 
1 2 3 4 
Atraso (atrasos-porta) 
4 
6 
4 
4 
8 
10 
4 t
a
m
a
n
h
o
 
(t
ra
n
s
is
to
re
s
) 
Digital Design 
Copyright © 2006 
Frank Vahid 
27 
Exemplo multi-nível: Caminho não crítico 
• Caminho crítico: caminho mais lento (longo) entre uma entrada e a 
saída. 
• Otimização: reduzir o número de transistores dos caminhos não críticos 
usando lógica multi-nível. 
d 
e 
Digital Design 
Copyright © 2006 
Frank Vahid 
28 
 
Métodos Automatizados 
para Otimização de Lógica Multi-nível 
• As principais técnicas usam métodos iterativos (heurísticos) 
– Baseados em várias operações lógicas: 
• “Fatoração” (ou colocar termos em evidência) para reduzir o número de 
portas: xy + xz = x(y+z) 
• Expansões e outras técnicas. 
– Aleatoriamente aplique uma operação, verifique se produz melhores 
resultados 
• Eventualmente aceita-se situações que possam provocar uma piora 
localizada, desde que essa piora possa gerar uma equação que poderá 
ser melhor manipulada. 
• Continue tentando até não encontrar melhorias. 
– Não é garantido de se encontrar o melhor circuito, mas certamente 
um dos melhores. 
Digital Design 
Copyright © 2006 
Frank Vahid 
29 
Redução de Estados (Minimização de Estados) 
6.3 
x y 
if x = 1,1,0,0 
then y = 0,1,1,0,0 
• Objetivo: Reduzir o número de estados de uma FSM sem 
modificar o seu comportamento sequencial 
– Menos estados implica em se ter registradores menores (menos FF) 
• Considere as duas FSMs abaixo: 
 
x 
state 
y 
x 
state 
y 
S0 S0 S1 S1 S1 S1 S2 S0 S2 S0 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saída: y 
S0 S1 
y=0 y=1 
x’ x 
x 
x’ 
Para a mesma sequencia de entradas a 
Saída das duas FSM é a mesma. 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
30 
Redução de Estados : Estados Equivalentes 
Dois estados são equivalentes se: 
1. Eles fazem as saídas assumirem 
um mesmo valor lógico 
– Ex.: S0 e S2 ambas fazem y ir para 0, 
– S1 e S3 ambas fazem y ir para 1 
2. E para todas as sequências 
possíveis de entradas, as saídas 
da FSM serão as mesmas 
começando de qualquer dos 
estados equivalentes 
– Ex.: suponha x=1,1,0,0,… 
• Começando de S1, y=1,1,0,0,… 
• Começando de S3, y=1,1,0,0,… 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
Estados S0 e S2 são equivalentes 
Estados S1 e S3 são equivalentes 
S0, 
S2 
S1, 
S3 
y=0 y=1 
x’ x 
x 
x’ 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
31 
Redução de Estados: Exemplo sem Estados 
Equivalentes 
• Outro exemplo… 
• Estado S0 não é equivalente a 
nenhum outro estado pois sua 
saída (y=0) difere da saída dos 
demais estados. 
 
S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x x 
x x 
x’ 
x’ 
x’ 
x’ 
Entrada: x; Saída: y 
S0 
• Observe o exemplo de S1 e S3 
S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x x 
x x 
x’ 
x’ 
x’ 
x’ 
S0 
Começando de S1, x=0 
S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x x 
x x 
x’ 
x’ 
x’ 
x’ 
S0 
Começando de S3, x=0 
– Saída inicialmente é a mesma (y=1) 
– De S1, quando x=0, vá para S2 onde y=1 
– De S3, quando x=0, vá para S0 onde y=0 
–As saídas diferem. Logo S1 e S3 não são 
equivalentes!! 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
32 
• Redução de estados feita de forma visual (por inspeção) 
como fizemos nos slides anteriores, não é um método 
confiável e não pode ser automatizada. Uma técnica 
sistemática é normalmente usada: tabelas de implicação 
• Exemplo: 
 
 
Redução de Estados com Tabelas de Implicação 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saída: y 
Redundantes 
Diagonal 
S0 
S0 S1 S2 S3 
S1 
S2 
S3 
– Para comparar cada par de estados, 
construimos uma tabela de pares de estados 
(mostrada acima à direita) 
– Removemos pares de estados redundantes e 
os estados ao longo da diagonal, pois cada 
estado (da diagonal) é equivalente a si 
mesmo 
S0 
S0 S1 S2 S3 
S1 
S2 
S3 
S0 S1 S2 
S1 
S2 
S3 
Digital Design 
Copyright © 2006 
Frank Vahid 
33 
• Marque (com um X) como sendo não 
equivalentes os pares de estado que têm 
saídas diferentes 
Redução de Estados com Tabelas de Implicação 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
– (S1,S0): Em S1, y=1 e em S0, y=0. Logo S1 
e S0 são não equivalentes. 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
– (S2, S0): Em S2, y=0 e em S0, y=0. Logo 
não marcamos S2 e S0 por enquanto. 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
– (S2, S1): Não equivalentes 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
– (S3, S0): Não equivalentes 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
– (S3, S1): Não marque 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
– (S3, S2): Não equivalentes 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
• Podemos observar que S2 & S0 são 
possíveis candidatos à equivalência e 
que S3 & S1 também são, mas somente 
se seus próximos estados forem 
equivalentes (lembre do exemplo 
mostrado dois slides atrás) 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
34 
Redução de Estados com Tabelas de Implicação 
• Necessitamos checar os próximos estados que 
correspondem aos mesmos valores de estado, 
para cada par de estados sem marca na tabela. 
• Podemos começar por listar para cada casa 
sem marca, os próximos estados que os 
mesmos vão para cada combinação de 
entradas 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saída: y 
S0 S1 S2 
S1 
S2 
S3 
– (S2, S0) 
• Em S2, quando x=1 vai para S3 
 Em S0, quando x=1 vai para S1 (S3, S1) 
 Logo incluimos (S3, S1) como um próximo par de esta-
dos 
• Em S2, quando x=0 vai para S2 
 Em S0, quando x=0 vai para S0 
(S2, S0) 
 Logo incluímos (S2, S0) como próximo par de estados 
– (S3, S1) 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
• De forma equivalente, geramos como 
próximos pares de estados (S3, S1) e (S0, S2) 
(S3, S1) 
(S0, S2) 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
35 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
Redução de Estados com Tabelas de Implicação 
• Em seguida, verifique par a par os 
próximos estados de cada casa sem 
marcação 
• Marcaremos o par de estados se um dos 
seus próximos estados estiver marcado 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saída: y 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
– (S2, S0) 
• Continuamos… 
• Par de próximos estados (S3, S1) não tem marca 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
• Par de próximos estados (S2, S0) não tem marca 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
– (S3, S1) 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
• Par de próximos estados (S3, S1) não tem marca 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
• Par de próximos estados(S0, S2) não tem marca 
 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
• Não marcamos nada e continuamos… 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
Digital Design 
Copyright © 2006 
Frank Vahid 
36 
Redução de Estados com Tabelas de Implicação 
• Acabamos de fazer uma passagem 
através da tabela implicação 
– Faça novas passagens até que 
nenhuma mudança ocorra 
• Em seguida, mescle os pares de 
estado desmarcados – eles são 
considerados equivalentes. 
S0 S1 
y=0 y=1 
S2 
y=0 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saida: y 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S2, S0) 
(S3, S1) 
(S0, S2) 
S0,S2 S1,S3 
y=0 y=1 
x’ x 
x 
x’ 
Digital Design 
Copyright © 2006 
Frank Vahid 
37 
Redução de Estados com Tabelas de Implicação 
Digital Design 
Copyright © 2006 
Frank Vahid 
38 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 S2 
S1 
S2 
S3 
Exemplo de Redução de Estados em FSMs 
• Dada a FSM à direita 
– Passo 1: Marque como sendo não 
equivalentes os pares de estados que 
têm saídas diferentes 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saída: y 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
39 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
S0 S1 S2 
S1 
S2 
S3 
Exemplo de Redução de Estados em FSMs 
• Dada a FSM a direita 
– Passo 1: Marque como sendo não 
equivalentes os pares de estados que 
têm saídas diferentes 
– Passo 2: Para cada par de estados 
não marcado, escreva os pares de 
próximos estados que correspondem 
aos mesmos valores de entrada. 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
x=0 
(S2, S2) 
x’ 
x’ 
x=1 
(S2, S2) 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
x 
x 
(S3, S1) 
x=0 
(S2, S2) 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
(S3, S1) 
x’ 
x’ 
(S0, S2) 
x=1 
S0 S1 S2 
S1 
S2 
S3 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
(S0, S2) 
x x 
(S3, S1) 
x=0 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
(S2, S2) 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S0, S2) 
(S3, S1) 
x’ x’ 
(S0, S2) 
x=1 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Inputs: x; Outputs: y 
(S2, S2) 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S0, S2) 
(S3, S1) 
(S0, S2) 
x 
x 
(S3, S3) 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saída: y 
(S2, S2) 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S0, S2) 
(S3, S1) 
(S0, S2) 
(S3,S3) 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
40 
Exemplo de Redução de Estados em FSMs 
• Dada a FSM a direita 
– Passo 1: Marque como sendo não 
equivalentes os pares de estados que 
têm saídas diferentes 
– Passo 2: Para cada par de estados 
não marcado, escreva os pares de 
próximos estados que correspondem 
aos mesmos valores de entrada. 
– Passo 3: Para cada par de estados não 
marcado, assinale como não equivalente os 
pares estados cujos pares de próximos 
estados não são equivalentes. Repita isso 
até que não ocorram mais alterações ou até 
que todos estados estejam marcados. 
– Passo 4: Combine os pares restantes de 
estados 
Todos os pares estão marcados – 
não existem mais pares de estados 
equivalentes a serem combinados 
(S2, S2) 
S0 S1 S2 
S1 
S2 
S3 
(S3, S1) 
(S0, S2) 
(S3, S1) 
(S0, S2) 
(S3, S3) 
S0 S1 
y=0 y=1 
S2 
y=1 
S3 
y=1 
x 
x x 
x’ 
x’ 
x x’ x’ 
Entrada: x; Saída: y 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
41 
Outro Exemplo de Redução de Estados com 
Tabelas de Implicação 
– Passo 1: Marque como sendo não equivalentes os 
 pares de estados que têm saídas diferentes 
– Passo 2: Para cada par de estados não marcado, escreva 
os pares de próximos estados que correspondem aos 
mesmos valores de entrada. 
– Passo 3: Para cada par de estados não marcado, assinale 
como não equivalente os pares estados cujos pares de 
próximos estados não são equivalentes. Repita isso até 
que não ocorram mais alterações ou até que todos 
estados estejam marcados. 
– Passo 4: Combine os pares restantes de estados 
 
S3 S0 
y=0 y=0 
y=1 y=1 
S1 S2 
S4 
x 
x’ x’ 
x’ x’ 
x’ x 
x x 
Entrada: x; Saída: y 
S2 
S1 
S3 
S4 
S0 S1 S2 S3 
(S4,S2) 
(S0,S1) 
(S3,S2) 
(S0,S1) 
(S3,S4) 
(S2,S1) 
(S4,S3) 
(S0,S0) 
y=0 
a 
x 
Digital Design 
Copyright © 2006 
Frank Vahid 
42 
S2 
S1 
S3 
S4 
S0 S1 S2 S3 
(S4,S2) 
(S0,S1) 
(S3,S2) 
(S0,S1) 
(S3,S4) 
(S2,S1) 
(S4,S3) 
(S0,S0) 
Outro Exemplo de Redução de Estados com 
Tabelas de Implicação (cont.) 
– Passo 1: Marque como sendo não equivalentes os 
 pares de estados que têm saídas diferentes 
– Passo 2: Para cada par de estados não marcado, escreva os 
pares de próximos estados que correspondem aos mesmos 
valores de entrada. 
– Passo 3: Para cada par de estados não marcado, assinale como 
não equivalente os pares estados cujos pares de próximos 
estados não são equivalentes. Repita isso até que não ocorram 
mais alterações ou até que todos estados estejam marcados. 
– Passo 4: Combine os pares restantes de estados 
 
S3 S0 
y=0 y=0 
y=1 y=1 
S1 S2 
S4 
x 
x’ x’ 
x’ x’ 
x’ x 
x x 
Entrada: x; Saída: y 
y=0 
y=0 
y=0 
y=1 
S0 S1,S2 
S3,S4 
x 
x 
x x’ 
x’ 
x’ 
Entrada: x; Saída: y 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
43 
Automação do Processo de Redução de Estados 
x’ 
x’ 
x’ 
x’ 
x’ 
x’ 
x’ 
x' x’ 
x’ 
x’ 
x’ 
x’ 
x’ 
x’ 
x 
x 
x 
x 
x 
x 
x 
x 
x 
x 
x 
x 
x 
x 
x 
SO 
SM 
SI 
SN SL 
SJ 
SK 
SG 
SH 
SB 
z=0 
z=0 
z=0 
z=1 
z=1 
z=1 
z=1 
z=1 
z=0 
z=0 
z=0 z=0 
z=1 
z=0 
z=1 
SA 
SD SC 
SE 
SF 
Entrada: x; Saída: z • Exemplo onde a automação desse 
processso é necessária 
– A tabela para uma FSM grande fica 
enorme para se minimizar dessa 
forma 
• n entradas: cada par de estado pode 
ter 2n pares de próximos estados. 
• 4 entradas  24=16 pares de próximos 
estados 
– 100 estados gerariam uma tabela com 100*100=100,000 células 
– O processo de redução de estados é automatizado (computador) 
• Heurísticas são adotadas para reduzir o tempo computacional. 
Digital Design 
Copyright © 2006 
Frank Vahid 
a 
Combinational
logic
State register
s1 s0
n1
n0
xb
clk
F
S
M
in
p
u
ts FS
M
o
u
tp
u
ts
n1 
n0 
s0 s1 
clk 
Logica Combinacional 
Registrador 
b x 
44 
Codificação de Estados 
• Codificação de Estados: Atribuir 
uma única combinação de bits a 
um único estado. 
• Codificações distintas podem 
produzir FSM menores ou mais 
rápidas 
• Vejamos o caso do Temporizador 
de laser que fica ativo por 3 Ciclos 
– Exemplo de codificação que 
usamos na seção 3.7: produzia 
15 entradas de portas lógicas 
– Tente outra forma de codificação 
• x = s1 + s0 
• n1 = s0 
• n0 = s1’b + s1’s0 
• Somente 8 entradas/porta lógica 
 
11 10 
00 
01 10 11 
b’ 
b 
x=0 
x=1 x=1 x=1 
Entrada: b; Saída: x 
On1 On2 On3 
Off 
1 
1 
0 
0 
1 
1 
0 
0 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
45 
Codificação de Estados: One-Hot Encoding 
• One-hot encoding 
– Um bit por estado – um bit igual a ‘1’ 
corresponde a um único estado. 
– É um modo alternativo a codificação com 
número mínimo de bits (slide anterior) 
– Para A, B, C, D: A: 0001, B: 0010, C: 
0100, D: 1000 
• Exemplo: FSM que produz como saída 
0, 1, 1, 1 
– Equações produzidas usando-se one-hot 
encoding: 
• n3 = s2; n2 = s1; n1 = s0; x = s3 + s2 + 
s1 
– Número menor de portas – menor tempo 
de propagação (possibilita CLK com 
maior frequencia) 
00 
01 
Entrada: nenhuma; Saída: x 
x=0 
x=1 
A 
B 
11 
10 
D 
C 
x=1 
x=1 
1000 
0100 
0001 
0010 
clk 
s1 
n1 
x 
s0 
n0 
State register 
clk 
n0 
s3 s2 s1 s0 
n1 
n2 
n3 
State register 
x 
a 
8 
6 
4 
2 
2 3 4 1 
Atraso (portas) 
one-hot 
binário 
Q
td
. 
e
n
tr
a
d
a
s
 
Digital Design 
Copyright © 2006 
Frank Vahid 
46 
Exemplo do Temporizador de Laser usando a 
técnica de One-Hot Encoding 
• Quatro estados – Usaremos 4 bits para 
fazer one-hot encoding 
– Tabela de estados produzem as novas 
equações: 
• x = s3 + s2 + s1 
• n3 = s2 
• n2 = s1 
• n1 = s0*b 
• n0 = s0*b’ + s3 
– Resultado menor 
• 3+0+0+2+(2+2) = 9 entradas de porta 
• Codificação em 2 bits (solução anterior, 
no cap. 3): 15 entradas de porta 
– Resultado mais rápido 
• Caminho crítico: n0 = s0*b’ + s3 
• Antes: n0 = s1’s0’b + s1s0’ 
• Uma AND de 2 entradas é um pouco 
mais rápida que uma AND de 3 entradas. 
0001 
0010 0100 1000 
b’ 
b 
x=0 
x=1 x=1 x=1 
Entrada: b; Saída: x 
On1 On2 On3 
Off 
a 
a 
Combinational
logic
State register
s1 s0
n1
n0
xb
clk
F
S
M
in
p
u
ts FS
M
o
u
tp
u
ts
n1 
n0 
s0 s1 
clk 
Logica Combinacional 
Registrador 
b x 
Solução 
Anterior: 
Digital Design 
Copyright © 2006 
Frank Vahid 
47 
Codificação das Saídas (Output encoding) 
• Output encoding: Método de 
codificação onde a codificação 
do estado segue a mesma 
codificação dos valores das 
saídas. É possível se: 
– A FSM tiver no mínimo tantas 
saídas quantas as necessárias 
para a codificação binária dos 
estados E ... 
– Se cada estado tiver uma 
combinação única de saída (a 
saída não pode ter valores iguais 
para estados diferentes) 
00 
01 
Entrada: nenhuma; Saídas: x,y 
x y=00 
x y=11 
A 
B 
11 
10 
D 
C 
x y=01 
x y=10 
Uso os valores das 
saídas para codificar 
os estados 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
48 
Exemplo de Output Encoding: Gerador de Sequências 
• Gerador de sequências 0001, 0011, 1100, 
1000, repete 
– FSM mostrada ao lado 
• Usaremos os valores das saídas para 
codificar os estados 
• Montamos a tabela de transição de estados 
• Obtemos as equações para os próximos 
estados (circuito combinacional) 
Entradas: nenhuma; Saídas: w, x, y, z 
wxyz=0001 
wxyz=0011 
A 
B 
D 
C 
wxyz=1000 
wxyz=1100 
clk 
n0 
s3 s2 s1 s0 
n1 
n2 
n3 
State register 
w 
x 
y 
z 
n3 = s1 + s2; n2 = s1; n1 = s1’s0; n0 = s1’s0 + s3s2’ 
Digital Design 
Copyright © 2006 
Frank Vahid 
49 
Arquiteturas Diferentes de FSMs: 
FSM de Moore versus FSM de Mealy 
• Formas diferentes de se implementar FSMs 
(Arquiteturas diferentes de FSM) 
– Registrador + Circuito combinacional 
– Vista mais detalhada: 
• Lógica do próximo estado – função do estado atual e das 
entradas da FSM 
• Lógica da saída: 
– Se as saídas forem um mapeamento apenasdo estado atual 
(as entradas influem nas saídas indiretamante, através dos estados) 
– Se as saídas forem função do estado atual 
E das entradas externas da FSM (alterações nas 
entradas refletem momentaneamente nas saídas) 
clk 
I O 
State register 
Combinational 
logic 
S 
N 
Moore Mealy 
/x=0 
b/x=1 
b’/x=0 
Entrada: b; Saída: x 
S1 S0 
Graficamente: mostra saídas 
nos arcos, não nos estados 
a 
Moore 
Mealy Digital Design 
Copyright © 2006 
Frank Vahid 
50 
Mealy FSMs podem produzir menos estados 
• Exemplo da máquina de refrigerantes: Iniciar (I), Esperar até encher o 
copo (W), Retirar (D) 
– Moore: 3 estados; Mealy: 2 estados 
Moore Mealy 
Entrada: enough (bit) 
Saída: d, clear (bit) 
Wait 
Disp 
Init 
enough’ 
enough d=0 
clear=1 
d=1 
Entrada: enough (bit) 
Saída: d, clear (bit) 
Wait Init 
enough’ 
enough/d=1 
clk 
Inputs: enough 
State: 
Outputs: clear 
d 
I I W W D 
(a) 
clk 
Inputs: enough 
State: 
Outputs: clear 
d 
I I W W 
(b) 
/d=0, clear=1 
Digital Design 
Copyright © 2006 
Frank Vahid 
51 
Exemplo Mealy vs. Moore: Relógio de Pulso com Bip 
• Botão b 
– Ao pressionar, gera uma 
sequencia de seleção das 
entradas de controle (s1s0) de 
um MUX 4:1 (00, 01, 10, e 11) 
• Cada combinação mostra uma 
funcionalidade diferente do 
relógio no mostrador 
– Cada pressionar gera um 1 bip 
de duração de 1 ciclo, com p=1 
representando o bip 
• Deve esperar o botão ser solto 
(b’) e pressionado novamente (b) 
antes de passar para uma nova 
função 
• Observe que a FSM de Moore 
demanda estados específicos 
para p=1, enquanto que a FSM 
de Mealy faz isso nas transições 
• Tradeoff: Na FSM de Mealy p=1 
pode não durar um ciclo 
completo de clock. 
Mealy 
Moore 
Entrada: b; Saída: s1, s0, p 
Time 
Alarm 
Date 
Stpwch 
b’/s1s0=00, p=0 
b/s1s0=00, p=1 
b/s1s0=01, p=1 
b/s1s0=10, p=1 
b/s1s0=11, p=1 
b’/s1s0=01, p=0 
b’/s1s0=10, p=0 
b’/s1s0=11, p=0 
Entrada: b; Saída: s1, s0, p 
Time 
S2 
Alarm 
b 
b 
b 
b 
b 
b 
b 
s1s0=00, p=0 
s1s0=00, p=1 
s1s0=01, p=0 
s1s0=01, p=1 
s1s0=10, p=0 
s1s0=10, p=1 
s1s0=11, p=0 
s1s0=11, p=1 
S4 
Date 
S6 
Stpwch 
S8 
b’ 
b’ 
b’ 
b’ 
Digital Design 
Copyright © 2006 
Frank Vahid 
53 
Tradeoff: FSM de Mealy versus FSM Moore 
• As saídas da FSM de Mealy mudam no meio do ciclo se as entradas mudam 
– Observe o exemplo da máquina de refrigerantes 
• Mealy possui um número menor de estados, mas faz com que d não fique em 1 no ciclo 
completo 
– Isso representa uma relação de compromisso (tradeoff) 
Moore Mealy 
Entrada: enough (bit) 
Saída: d, clear (bit) 
Wait 
Disp 
Init 
enough’ 
enough d=0 
clear=1 
d=1 
Entradas: enough (bit) 
Saída: d, clear (bit) 
Wait Init 
enough’ 
enough/d=1 
clk 
Entrada: enough 
State: 
Saída: clear 
d 
I I W W D 
(a) 
clk 
Entrada: enough 
State: 
Saída: clear 
d 
I I W W 
(b) 
/d=0, clear=1 
Digital Design 
Copyright © 2006 
Frank Vahid 
54 
Implementando uma FSM Mealy 
• Modo direto 
– Converta em uma tabela 
de estados 
– Escreva as equações 
para cada saída 
– Diferença principal para a 
FSM de Moore: Saídas 
externas (d, clear) podem 
assumir valores lógicos 
diferentes no mesmo 
estado, dependendo dos 
valores das entradas! 
Entradas: enough (bit) 
Saídas: d, clear (bit) 
Wait Init 
enough’/d=0 
enough/d=1 
/ d=0, clear=1 
Digital Design 
Copyright © 2006 
Frank Vahid 
56 
Tradeoffs na Geração de Componentes de 
Caminhos de Dados 
• Podemos construir componentes mais rápidos (porém muito 
maiores),ou muito menores (porém mais lentos), que os componentes 
que projetamos no capítulo 4. 
• Nessa seção construiremos: 
– Um somador mais rápido que o somador ripple-carry, porém bem maior. 
– Um multiplicador bem menor que o multiplicador na forma de array (visto 
no cap. 4), porém bem mais lento. 
• Outros componentes do capítulo 4 poderiam ser projetados também 
de forma diferente. 
6.4 
Digital Design 
Copyright © 2006 
Frank Vahid 
57 
Somador mais rápido 
• Somador Ripple-Carry visto no cap. 4 
– Imita a adição feita com lápis e papel. 
– Desvantagem: Lento 
• A saída da soma não fica pronta até que o último 
carry esteja pronto. 
• Um somador ripple-carry de 4 bits apresenta 4*2 = 
8 atrasos-porta 
– Vantagem: Pequeno 
• Um somador Ripple-carry de 4 bits demanda 
somente 4*5 = 20 portas 
F A 
a3 
c out s3 
b3 
F A 
a0 b0 cin 
F A 
a2 
s2 s1 s0 
b2 
F A 
a1 b1 
c3 ca rr ies: 
b3 
a3 
s3 
c2 
b2 
a2 
s2 
c1 
b1 
a1 
s1 
cin 
b0 
a0 
s0 
+ 
cout 
A: 
B: 
a3 b3 a2 b2 a1 b1 a0 b0 cin 
s3 s2 s1 s0 c out 
Somador de 4 bits 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
58 
Somador mais rápido 
• Um somador mais rápido – Pode ser 
implementado com lógica combinacional de 2 
níveis (cap. 2) 
– Lembre que aplicar o método de lógica de 2 
níveis a um somador de 4 bits produzia tabelas 
verdade muito grandes. 
– Vantagens: Rápidos 
• 2 atrasos-porta 
– Desvantagens: Muito grandes 
• Tabela verdade teria 2
(4+4)
 =256 linhas! 
• O gráfico ao lado mostra que um somador de 4-
bits necessitaria 500 portas! 
• Existe um método de projeto intermediário? 
– Que gere somadores entre 2 e 8 atrasos-porta 
– Entre 20 e 500 portas lógicas. 
 
 
10000 
8000 
6000 
4000 
2000 
0 
1 2 3 4 5 
N 
6 7 8 
a3 
c 
out 
s3 
b3 a0 b0 cin a2 
s2 s1 s0 
b2 a1 b1 
Lógica de 2 níveis: 
Nível de ANDs seguido 
de nível de ORs 
Digital Design 
Copyright © 2006 
Frank Vahid 
59 
F A 
a3 
c o s3 
b3 
F A 
a0 b0 ci 
F A 
a2 
s2 s1 s0 
b2 
F A 
a1 b1 
a 
Somador Mais Rápido 
• Primeira Idéia: 
– Modificar o somador ripple-carry – Para o carry-in de cada estágio, 
não espere pelo carry se propagar, faça entretanto, o cálculo dos 
carries dos estágios anteriores. 
• É chamado de somador “lookahead” porque em cada estágio o carry é 
calculado de forma a “prever o carry dos estágios seguintes” 
 
 
F A 
c4 
c3 c2 
s3 s2 
Estágio 3 Estágio 2 
c1 
s1 
Estágio 1 
c0 
s0 
c0 b0 b1 b2 b3 a0 a1 a2 a3 
Estágio 0 
c out 
look 
ahead 
look 
ahead 
look 
ahead 
Repare que não acontece 
propagação do carry 
Digital Design 
Copyright © 2006 
Frank Vahid 
60 
F A 
a3 
C out,3 s3 
b3 
F A 
a0 b0 c0 
F A 
a2 
s2 s1 s0 
b2 
F A 
a1 b1 
a 
Somador Mais Rápido - Primeira Idéia (cont.) 
Estágio 0: O Carry-in já é uma 
entrada externa: c0 
Cout,0 
c1 
Estágio 1: c1=Cout,0 
Cout,0= b0c0 + a0c0 + a0b0 
c1 = b0c0 + a0c0 + a0b0 
Cout,1 
c2 
Estágio 2: c2=Cout,1 
Cout,1 = b1c1 + a1c1 + a1b1 
c2 = b1c1 + a1c1 + a1b1 
• Lembre-se das equações do somador completo: 
– s = a xor b xor c (onde c = carry-in) 
– Cout = bc + ac + ab (onde Cout = carry-out) 
• Queremos que o bit de carry-in de cada estágio seja função somente das entradas externas 
(a’s, b’s, or c0) 
c2 = b1(b0c0 + a0c0 + a0b0) + a1(b0c0 + a0c0 + a0b0) +a1b1 
c2 = b1b0c0 + b1a0c0 + b1a0b0 + a1b0c0 + a1a0c0 + a1a0b0 + a1b1 
F A 
c4 
c3 c2 
s3 s2 
stage 3 stage 2 
c1 
s1 
stage 1 
c0 
s0 
c0 b0 b1 b2 b3 a0 a1 a2 a3 
stage 0 
look 
ahead 
look 
ahead 
look 
ahead 
c out 
Faça o mesmo com c3 
c3 
Cout,2 
Digital Design 
Copyright © 2006 
Frank Vahid 
61 
Somador Mais Rápido - Primeira Idéia (cont.) 
c1 = b0c0 + a0c0 + a0b0 
• A função lógica do Carry 
lookahead é gerada 
somente a partir das 
entradas externas 
– Não espera por 
propagação 
• Problema 
– Equações ficam muito 
grandes 
– Ineficientes 
– Necessitamos de uma 
forma melhor de 
implementar o princípio 
do lookahead 
c2 = b1b0c0 + b1a0c0 + b1a0b0 + a1b0c0 + a1a0c0 + a1a0b0 + a1b1 
F A 
c4 
c3 c2 
s3 s2 
Estágio 3 Estágio 2 
c1 
s1 
Estágio 1 
c0 
s0 
c0 b0 b1 b2 b3 a0 a1 a2 a3 
Estágio 0 
look 
ahead 
look 
ahead 
look 
ahead 
c 
out 
c3 = b2b1b0c0 + b2b1a0c0 + b2b1a0b0 + b2a1b0c0 + b2a1a0c0 + b2a1a0b0 + b2a1b1 + a2b1b0c0 + a2b1a0c0 
+ a2b1a0b0 + a2a1b0c0+ a2a1a0c0 + a2a1a0b0 + a2a1b1 + a2b2 
Digital Design 
Copyright © 2006 
Frank Vahid 
62 
Uma forma melhor de implementar o conceito 
Lookahead do sinal de Carry 
• Cada estágio deverá calcular 2 termos: 
– Termo de Propagação do Carry no estágio: P = a xor b (= soma do meio somador) 
– Termo de Geração do Carry no estágio: G = ab (= carry-out do meio somador) 
• Implementar o conceito look-ahead usando os termos P e G, e não com 
as entradas externas. 
– A lógica combinacional se torna muito mais simples. 
• G: Se a e b são iguais a 1, o carry-out será igual a 1 – “Gerar” um carry-
out igual a 1 nesse caso. 
• P: Se uma das entradas a ou b é igual a 1, então o carry-out será igual ao 
carry-in – “Propaga” o bit de carry-in para a saída de carry-out nesse caso. 
( a ) 
b3 
a3 
s3 
b2 
a2 
s2 
b1 
a1 
s1 
b0 
a0 
s0 
1 
1 
0 
0 1 carries: c4 c3 c2 c1 c0 
B: 
A: + + 
c 
out 
cin 
1 
1 
1 
1 1 
+ 
0 
1 
0 
1 1 
+ 
1 
0 
0 
1 1 
+ 
c1 
c0 
b0 
a0 
se a0 x or b0 = 1 
então c1 = 1 se c0 = 1 
(chame de P: Propagador) 
se a0b0 = 1 
então c1 = 1 
(chame de G: Gerador) 
Digital Design 
Copyright © 2006 
Frank Vahid 
63 
“Bad” lookahead 
F A 
c4 
c3 c2 
s3 s2 
stage 3 stage 2 
c1 
s1 
stage 1 
c0 
s0 
c0 b0 b1 b2 b3 a0 a1 a2 a3 
stage 0 
look 
ahead 
look 
ahead 
look 
ahead 
c out 
Uma forma melhor de implementar o conceito 
Lookahead do sinal de Carry 
• Com P e G, a implementação das 
equações do somador carry 
lookahead ficam muito mais 
simples 
– Antes de conectá-las: 
• c1 = G0 + P0c0 
• c2 = G1 + P1c1 
• c3 = G2 + P2c2 
• cout = G3 + P3c3 
Depois de conectá-las: 
c1 = G0 + P0c0 
c2 = G1 + P1c1 = G1 + P1(G0 + P0c0) 
c2 = G1 + P1G0 + P1P0c0 
c3 = G2 + P2c2 = G2 + P2(G1 + P1G0 + P1P0c0) 
c3 = G2 + P2G1 + P2P1G0 + P2P1P0c0 
cout = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0c0 
Muito mais simples que a primeira forma de 
implementação! 
a 
a 
C a r r y -loo k ahead lo g ic 
G3 
a3 b3 
P3 c3 
c out s3 
G2 
a2 b2 
P2 c2 
s2 
G1 
a1 b1 
P1 c1 
s1 
G0 
a0 b0 cin 
P0 c0 
s0 ( b ) 
Half-adder Half-adder Half-adder Half-adder 
Digital Design 
Copyright © 2006 
Frank Vahid 
64 
Uma forma melhor de implementar o conceito 
Lookahead do sinal de Carry 
C a r r y -loo k ahead lo g ic 
G3 
a3 b3 
P3 c3 
c out s3 
G2 
a2 b2 
P2 c2 
s2 
G1 
a1 b1 
P1 c1 
s1 
G0 
a0 b0 cin 
P0 c0 
s0 ( b ) 
Half-adder Half-adder Half-adder Half-adder 
c1 = G0 + P0c0 
c2 = G1 + P1G0 + P1P0c0 
c3 = G2 + P2G1 + P2P1G0 + P2P1P0c0 
c 
out = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0c0 
( c ) 
SPG 
block 
C
h
a
m
e
 e
s
s
e
 b
lo
c
o
 d
e
 
B
lo
c
o
 d
e
 G
e
ra
ç
ã
o
 e
 
P
ro
p
a
g
a
ç
ã
o
 d
e
 S
in
a
is
 
(S
P
G
) 
G3 P3 G2 P2 G1 G0 c0 P1 P0 
C a r r y -loo k ahead lo g ic 
S tage 4 S tage 3 S tage 2 S tage 1 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
65 
Uma forma melhor de implementar o conceito 
Lookahead do sinal de Carry (High Level View) 
• Mais rápido – somente 4 atrasos-porta 
– Cada estágio possui um bloco SPG (cada um 
com 2 atrasos-porta) 
– A lógica do somador Carry-lookahead 
rapidamente calcula o carry usando P e G vindo 
dos blocos SPG com 2 atrasos-porta 
• Número de portas razoavelmente pequeno – 
Para um somador de 4-bits = 26 portas lógicas 
 
a3 b3 
a b 
P G 
cout 
cout 
G3 P3 
cin 
a2 b2 
a b 
P G 
G2 P2 c3 
cin 
SPG block SPG block 
a1 b1 
a b 
P G 
G1 P1 c2 c1 
cin 
SPG block 
a0 b0 c0 
a b 
P G 
G0 P0 
cin 
SPG block 
4-bit carry-lookahead logic 
s3 s2 s1 s0 
• Comparação entre os 
somadores de 4-bits 
(atrasos, no de portas) 
– Ripple-carry: (8, 20) 
– 2 Níveis: (2, 500) 
– CLA: (4, 26) (*) 
 
 
(*) CLA = Carry-Look-Ahead 
Digital Design 
Copyright © 2006 
Frank Vahid 
66 
Como implementar um somador 
Carry-Lookahead de 32-bits? 
• Problema: Portas passam a ter muitas entradas 
em cada estágio 
– 4o estágio vai ter portas com 5 entradas! 
– 32o estágio teria portas com 33 entradas! 
• Muitas entradas para uma única porta (fan-in alto) 
• Seria necessário construir blocos com portas 
lógicas menores, o que significa mais níveis (mais 
lento), e mais portas (bloco maior) 
• Uma solução: Conectar um bloco somador CLA 
na forma ripple-carry 
– Solução lenta: (4 + 4 + 4 + 4 atrasos-porta) 
 
a3 a2 a1 a0 b3 
s3 s2 s1 s0 c out 
c out 
cin 
b2 b1 b0 
4-bit adder 
a3 a2 a1 a0 b3 
s3 s2 s1 s0 
s11-s8 s15-s12 
a15-a12 b15-b12 a11-a8 b11-b8 
c out 
cin 
b2 b1 b0 
4-bit adder 
a3 a2 a1 a0 b3 
s3 s2 s1 s0 c out 
s7 s6 s5 s4 
cin 
b2 b1 b0 
a7 a6 a5 a4 b7 b6 b5 b4 
4-bit adder 
a3 a2 a1 a0 b3 
s3 s2 s1 s0 
s3 s2 s1 s0 
c out 
cin 
b2 b1 b0 
a3 a2 a1 a0 b3 b2 b1 b0 
4-bit adder 
Digital Design 
Copyright © 2006 
Frank Vahid 
67 
Somadores Hierárquicos 
na forma Carry-Lookahead 
• Solução melhor -- Ao invés de conectar os módulos em modo ripple-
carry, basta repetir o conceito do carry-lookahead 
– Vai demandar uma pequena modificação no CLA de 4 bits para gerar as 
saídas P e G 
a3 a2 a1 a0 b3 
s3 s2 s1 s0 
cout 
cout 
cin 
b2 b1 b0 
4-bit adder 
a3 a2 a1 a0 b3 
a15-a12 b15-b12 a11-a8 b11-b8 
cin 
b2 b1 b0 
4-bit adder 
4-bit carry-lookahead logic 
a3 a2 a1 a0 b3 
s3 s2 s1 s0 
cin 
b2 b1 b0 
a7 a6 a5 a4 b7 b6 b5 b4 
4-bit adder 
a3 a2 a1 a0 b3 
s3 s2 s1 s0 
cin 
b2 b1 b0 
a3 a2 a1 a0 b3 b2 b1 b0 
4-bit adder 
s3 s2 s1 s0 P G 
P G 
P3 G3 
cout P G 
P2 c3 G2 
cout P G 
P1 c2 G1 
cout P G 
P0 c1 G0 
s15-s12 
s11-s8 s7-s4 s3-s0 
Esses adotam o princípio do carry-lookahead internamente 
Segundo nível de carry-lookahead 
a 
G3 P3 G2 P2 G1 G0 c0 P1 P0 
Carry lookahead logic 
Stage 4 Stage 3 Stage 2 Stage 1 
Mesma lógica 
lookahead como a dos 
CLAs de 
4-bits do nível 1. 
cout c3 c2 c1 
P=P3P2P1P0 
G= G3+P3G2+P3P2G1+P3P2P1G0 
Termos da direita da equação vêm 
dos SPG internos ao 4-bit-adder 
Digital Design 
Copyright © 2006 
Frank Vahid 
68 
Somadores Hierárquicos 
na forma Carry-Lookahead 
• O conceito de CLAs hierárquicos podem ser aplicados para somadores maiores 
• No caso do CLA hierárquico de 32-bits 
– Somente 8 atrasos-porta (2 para o bloco SPG, depois 2 por cada nível de CLA) 
– Somente 14 portas em cada CLA de 4-bits + 5 portas para P e G do bloco (19 portas) 
Q: Quantos atrasos-
porta para um CLA 
hierárquico de 64-bits 
usando um CLA de 4 
bits como base? 
A: 16 blocos CLA no 
1o nível, 4 no 2o, 1 no 
3o – portanto: 8 
atrasos-porta (2 pelo 
SPG, e 2+2+2 pela 
lógica do CLA). 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
69 
Somadores Carry Select 
• Outra maneira de arranjo de somadores 
– O estágio de ordem mais alta – Computa o resultado para um carry 
in igual a 1 e igual a 0 simultaneamente 
• Seleciona baseado no carry-out dos estágios de ordem inferior 
• Mais rápido que fazer ripple-carry 
Calcula em paralelo 
Suponha =1 
Digital Design 
Copyright © 2006 
Frank Vahid 
70 
Tradeoffs na Implementação de Somadores 
• O projetista deve escolher o componente que satisfaça os requisitos de 
atraso específico e tamanho 
– Pode utilizar diferentes tipos de componentes em diferentes partes do mesmo 
projeto 
– Somadores mais rápidos no caminho crítico, somadores menores sobre os 
caminhos menos críticos 
Atraso (atrasos-porta) 
carry-select 
carry- 
ripple 
carry-lookahead 
multilevel 
carry-lookahead 
T
a
m
a
n
h
o
 (
n
o
 p
o
rt
a
s
 l
ó
g
ic
a
s
) 
Digital Design 
Copyright © 2006 
Frank Vahid 
71 
Multiplicadores Menores 
+ (5-bit) 
+ (6-bit) 
+ (7-bit) 
0 0 
0 0 0 
0 
a0 a1 a2 a3 
b0 
b1 
b2 
b3 
0 
p7..p0 
p
p
1
 
p
p
2
 
p
p
3
 
p
p
4
 
Multiplicador de 32-bits teria 1024 portas aqui ... 
... e 31 somadores 
aqui (muito grandes) 
• Multiplicador do capítulo 4 (implementado na forma de uma matriz) 
– Rápido, bom tamanho para um multiplicador de 4-bits: 4*4 = 16 produtos 
parciais (portas AND), 3 somadores– Entretanto para um multiplicador de 32-bits: 32*32 = 1024 ANDs e 31 
somadores 
a 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
72 
Multiplicadores Menores – Implementados adotando 
o Estilo Sequencial (Soma e Desloca) 
• Idéia principal 
– Não computar todos os produtos parciais simultaneamente 
– Pelo contrário, computar um de cada vez (semelhante à 
multiplicação realizada manualmente) 
0 1 1 0 
0 0 1 1 
0 0 0 0 
+ 
Step 1 
0 1 1 0 
0 1 0 0 1 0 
+ 
0 1 1 0 
0 0 1 1 
0 0 1 1 0 
+ 
Step 2 
0 0 0 0 
0 0 1 0 0 1 0 
+ 
0 1 1 0 
0 0 1 1 
0 1 0 0 1 0 
+ 
Step 3 
0 0 0 0 
0 0 0 1 0 0 1 0 
+ 
0 1 1 0 
0 0 1 1 
0 0 1 0 0 1 0 
+ 
Step 4 
0 1 1 0 + (produto parcial) 
0 0 1 1 0 (nova soma) 
(soma inicial) 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
73 
Multiplicadores Menores – Implementados 
adotando o Estilo Sequencial (Soma e Desloca) 
• Projete um circuito que 
computa um produto parcial 
por vez, adicionando-o a um 
registrador para guardar a 
soma parcial dos produtos 
– Observe que deslocar o 
resultado da soma parcial para 
a direita (relativo ao produto 
parcial) após cada passo, 
garante que o produto parcial 
seja somado corretamente a 
nova soma parcial 
 
0 1 1 0 
0 0 1 1 
0 0 0 0 
+ 
Passo 1 
0 1 1 0 
0 1 0 0 1 0 
+ 
0 1 1 0 
0 0 1 1 
0 0 1 1 0 
+ 
Passo 2 
0 0 0 0 
0 0 1 0 0 1 0 
+ 
0 1 1 0 
0 0 1 1 
0 1 0 0 1 0 
+ 
Passo 3 
0 0 0 0 
0 0 0 1 0 0 1 0 
+ 
0 1 1 0 
0 0 1 1 
0 0 1 0 0 1 0 
+ 
Passo 4 
0 1 1 0 + (produto parcial) 
0 0 1 1 0 (nova soma parcial) 
(soma parcial) 
mr3 
m r ld 
mdld 
mr2 
mr1 
mr0 
rsload 
rsclear 
rsshr 
start 
load 
load 
clear 
shr 
produto 
Somador parcial 
Registrador de 8 bits 
registrador 
Multiplicador (4) 
multiplicador 
registrador 
Multiplicando (4) 
multiplicando 
load 
Somador de 4 bits 
a 
C
O
N
T
R
O
L
A
D
O
R
A
 
Digital Design 
Copyright © 2006 
Frank Vahid 
74 
Multiplicadores Menores – Implementados 
adotando o Estilo Sequencial (Soma e Desloca) 
• Espera pelo sinal de start=1 
• Considera um bit do 
multiplicador por vez (evento de 
clock) 
– Adiciona o produto parcial 
(multiplicando) ao registrador 
de soma parcial se o bit do 
multiplicador for igual a 1 
– Depois desloca o registrador de 
soma parcial para a direita de 
uma posição 
 
 
mr3
mrld
mdld
mr2
mr1
mr0
rsload
rsclear
rsshr
start
load
load
clear
shr
product
running sum
register (8)
multiplier
register (4)
multiplier
multiplicand
register (4)
multiplicand
load
co
nt
ro
lle
r 4-bit adder
start’ 
mr0’ 
mr0 mr1 mr2 mr3 
mr1’ mr2’ mr3’ 
start 
sta r t 
mdld = 1 
mrld = 1 
rsclear = 1 
rsshr=1 rsshr=1 rsshr=1 rsshr=1 
rsload=1 rsload=1 rsload=1 rsload=1 
controladora 
mr3 
m r ld 
mdld 
mr2 
mr1 
mr0 
rsload 
rsclear 
rsshr 
Comparado com a forma 
mostrada no cap.4: 
 Prós: pequeno 
• Somente 3 
registradores, somador, 
e uma controladora 
 Contras: lento 
• 2 períodos por cada 
bit do multiplicador 
• 32-bits: 32*2=64 
perídos (mais 1 para o 
start) 
a 
0110 
0011 
00000000 
a 
01100000 00110000 10010000 01001000 00100100 00010010 
Produto final 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
75 
Projeto RTL: Otimizações e Tradeoffs 
• Ao criar um caminho de dados durante o projeto RTL, 
existem várias otimizações e relações de compromisso na 
implementação de um projeto. Isso envolve os seguintes 
conceitos: 
– Pipelining 
– Concorrência 
– Alocação de componentes 
– Mapeamento de operadores (binding) 
– Escalonamento de operadores 
– FSMs de alto nível implementadas na forma de Moore versus Mealy 
6.5 
Digital Design 
Copyright © 2006 
Frank Vahid 
76 
Pipelining 
• Exemplo intuitivo: Lavar pratos. Enquanto 
você lava pratos, seu amigo os enxuga 
– Você lava o prato 1 (W1) 
– Após, seu amigo enxuga o prato 1 (D1), 
enquanto você lava o prato 2 (W2) 
– Então seu amigo seca o prato 2 (D2), 
enquanto você lava o prato 3 (W3); e assim 
por diante 
 
• Pipelining: Quebre as tarefas em estágios, 
a saída de cada estágio gera dados para o 
próximo estágio, todas os estágios operam 
concorrentemente (se tiverem dados) 
W1 W2 W3 D1 D2 D3 
Sem pipelining: 
Com pipelining: 
“Estágio 1” 
“Estágio 2” 
Tempo 
W1 
D1 
W2 
D2 
W3 
D3 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
77 
Exemplo de Pipelining 
• S = W+X+Y+Z 
• O caminho crítico do caminho de dados da figura à esquerda é de 4 ns, 
logo o menor período de clock será de 4 ns 
– Podemos ler novos dados, somar e escrever o resultado em S, a cada 4 ns 
W X Y Z 
2ns 2ns 
2ns 
+ + 
+ 
S 
clk 
Caminho mais logo 
Vale = 2 ns 
clk 
S S(0) 
Logo o período mínimo 
De clock será = 2ns 
S(1) 
clk 
S S(0) 
Logo o período mínimo 
De clock será = 4ns 
S(1) 
Caminho mais longo 
vale 2+2 = 4 ns 
2ns 2ns 
2ns 
Estágio 2 
Estágio 1 
W X Y Z 
+ + 
+ 
S 
clk 
2
n
s
 registradores 
de Pipelining 
E
s
tá
g
io
 1
 
E
s
tá
g
io
 2
 a 
• O caminho crítico do caminho de dados da figura à direita é 
somente 2 ns: podemos ler um dado a cada 2 ns. 
 – O desempenho dobrou !!! 
Digital Design 
Copyright © 2006 
Frank Vahid 
78 
Exemplo de Pipelining 
• Definições de desempenho usadas para avaliação dos efeitos do uso da 
técnica de Pipelining 
– Latência: Tempo para que um conjunto de dados de entrada percorra a 
estrutura do pipeline e resulte em uma saída (segundos) 
– Throughput: Taxa de processamento de pares entrada/saída (itens / segundo). 
Tem a ver com a velocidade com que um dado entra/sai da estrutura 
– Esses conceitos aplicados ao exemplo acima: 
• O throughput dobra: vai de 1 item/4ns, para 1 item/2ns. 
• A latência é a mesma: 4 ns. 
Digital Design 
Copyright © 2006 
Frank Vahid 
79 
Exemplo de aplicação de Pipelining: Caminho de 
Dados do Filtro FIR 
• Um filtro FIR (100-tap): Linha de 100 
multiplicadores concorrentes, seguidos 
de uma árvore de somadores 
– Assuma: 
• 20 ns para cada multiplicador 
• 14 ns para a árvore de somadores 
– Caminho crítico de 20+14 = 34 ns 
• Adicione registradores de pipeline 
– O caminho mais longo agora será 20 ns 
– A frequência de clock pode ser quase 
dobrada 
• Maior speedup (aceleração) com a 
inclusão mínima de hardware 
 
Digital Design 
Copyright © 2006 
Frank Vahid 
80 
Concorrência 
• Concorrência: Divide a tarefa em 
várias partes, executa as várias partes 
de forma simultânea 
– Exemplo de lavar pratos: Divida a pilha 
de pratos em 3 pilhas menores, passe 
a tarefa de lavar os pratos da pilha 
para 2 vizinhos, que trabalhão 
simultaneamente com você lavando os 
pratos – Isso produz um speedup de 3 
vezes (ignorando o tempo levado para 
mover os pratos para os vizinho) 
– Concorrência permite fazer tarefas 
“lado a lado”; pipelining demanda 
estágios (assim como em uma linha de 
produção de uma indústria) 
– Usamos o conceito de concorrência no 
caso do filtro FIR: multiplicadores 
 * * * 
Tarefa 
Pipelining 
Concorrência a 
Os dois juntos, tb 
Digital Design 
Copyright © 2006 
Frank Vahid 
81 
Exemplo de Concorrência: Projeto SAD 
• Exemplo de compressão de vídeo usando SAD (Sum-of-absolute differences) 
– Computar a soma das diferenças absolutas (SAD) de 256 pares de pixels 
– Projeto Inicial: O loop principal faz 1 soma p/ iteração, 256 iterações, 2 ciclos/iteração. 
i_lt_256 
i_inc 
i_clr 
sum_ld 
sum_clr 
sad_reg_ld 
Datapath 
sum 
sad_reg 
sad 
AB_addr A_data B_data 
<256 
9 
32 
8 
8 
8 8 
32 32 
32 
i – 
+ 
abs 
!go S0 
go 
S1 
sum = 0 
i = 0 
S3 
sum=sum+abs(A[i]-B[i]) 
i=i+1 
S4 sad_ reg=sum 
S2 
i<256 
(i<256)’ 
-/abs/+ prontos em 1 
ciclo, mas realizados 
256 vezes 
256 iterações.*2 ciclos/iter. = 512 ciclos 
Digital Design 
Copyright © 2006 
Frank Vahid 
82 
Exemplo de Concorrência: Projeto SAD 
• Uma maneira de projetá-lo de forma concorrente: 
– Compute a SAD para16 pares concorrentemente, faça16 vezespara 
computar todos 16*16=256 SADs. 
– O loop principal leva 16 somas/iteração, somente16 iters., ainda 2 ciclos/iter. 
go AB_ r d 
AB_addr 
AB_ r d=1 
S0 
S1 
S2 
S4 
go 
!go 
sum_clr=1 
i_clr=1 
sum_ld=1 
sad_ r eg_ld=1 
i_inc=1 
i_lt_16 
C o n t r oller D a tap a th 
sad 
sad_ r eg 
sum 
i 
<16 
i_lt_16 
i_clr 
sum_ld 
sum_clr 
sad_ r eg_ld 
i_inc 
A0 B0 A1 A14 A15 B1 B14 B15 
– – – – 
16 subtratores 
abs abs abs abs 
16 valores 
absolutos 
+ + 
+ + 
Árvore de 
somadores 
para somar 
16 valores 
i_
lt
_
1
6
’ 
a 
Todos -/abs/+ prontos em 1 
ciclo, mas realizados somente 
16 vezes 
In
ic
ia
l:
 2
5
6
*2
 =
 5
1
2
 c
ic
lo
s
 
N
o
v
a
 v
e
rs
ã
o
: 
1
6
*2
 =
 3
2
 c
ic
lo
s
 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
83 
Exemplo de Concorrência: Projeto SAD 
• Comparando os dois projetos 
– Inicial: 256 iterações * 2 ciclos/iter = 512 ciclos 
– Forma concorrente: 16 iterações * 2 ciclos/iter = 32 ciclos 
– Speedup: 512/32 = 16x speedup 
• Versão software 
– Lembrando: Estimado aprox. 6 ciclos/iter. em um microprocessor 
• 256 iterações * 6 ciclos/iter = 1536 ciclos 
• Speedup Projeto Inicial versus Software: 1536 / 512 = 3x 
– (assumindo que o período de clock é o mesmo!) 
• Speedup da versão concorrente versus Software : 1536 / 32 = 48x 
– 48x é muito ganho! 
• A velocidade de processamento do vídeo ficaria muito maior !!! 
• Poderia resultar em maior taxa de atualização do display. 
• Poderia resultar em melhor sensação de movimento, melhor qualidade. 
Digital Design 
Copyright © 2006 
Frank Vahid 
84 
Alocação de Componentes 
• Outro tradeoff do projeto RTL: Alocação de Componentes – Escolha 
do conjunto de unidades funcionais para implementar o conjunto de 
operações definidas pelos requisitos de projeto 
– Por exemplo, dados dois estados, cada um com multiplicações 
• Podemos usar 2 multiplicadores (*) 
• OU, podemos usar: 1 multiplicador, e 2 MUXs 
• Menor em tamanho, mas um pouco mais lento devido ao atraso dos MUXs 
 
A B 
t1 = t2*t3 t4 = t5*t6 
* 
t2 
t1 
t3 
* 
t5 
t4 
t6 
(a) 
FSM-A: (t1ld=1) B: (t4ld=1) 
* 
2 × 1 
t4 t1 
(b) 
2 × 1 sl 
t2 t5 t3 t6 
sr 
A: (sl=0; sr=0; t1ld=1) 
B: (sl=1; sr=1; t4ld=1) 
a 
2 mul 
1 mul 
(c) 
atraso 
ta
m
a
n
h
o
 
Digital Design 
Copyright © 2006 
Frank Vahid 
85 
Mapeamento de Operadores 
• Outro tradeoff do projeto RTL: Mapeamento de Operadores – Mapear um 
conjunto de operações para uma alocação de componentes definida 
– Observe: operador/operação significa comportamento (multiplicação, adição), 
enquanto componente (unidade funcional) significa hardware (multiplicador, 
somador) 
– Mapeamentos de operadores diferentes implicam em projetos de tamanho e 
desempenho diferentes 
 
 
Mapeamento 2 
A B 
t1 = t2 * t3 t4 = t5 * t6 t7 = t8 * t3 
C A B 
t1 = t2 * t3 t4 = t5 * t6 t7 = t8 * t3 
C 
MULA MULB 
2x1 
t7 t4 
2x1 
t5 t3 t2 t8 t6 t3 
sr 
t1 
sl 2x1 
t2 t8 t3 
sl 
t6 t5 
t7 t1 t4 
MULB MULA 
2 
multiplicadores 
alocados 
Mapeamento 1 Mapeamento 2 
Mapeamento 1 
del a y 
s
iz
e
 
2 muxes 
versus 
1 mux 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
86 
Escalonamento de Operadores 
• Outra relação de compromisso de um projeto RTL: 
Escalonamento de Operadores – Incluir ou concatenar 
estados, seguido de associação de operações a esses 
estados. 
* 
t3 t2 
* 
t1 
t6 t5 
* 
t4 
B2 
(outras 
operações) 
(algumas 
operações) 
t1 = t2 * t3 
t4 = t5 * t6 
A B C 
* t4 = t5 t6 
Escalonamento 
com 3 estados 
atraso 
ta
m
a
n
h
o
 
2x1 
t4 t1 
2x1 
t2 t5 t3 t6 
sr sl 
Escalonamento com 4 
estados 
menor 
(somente 1 *) 
Entretanto 
produz maior 
atraso (MUX) 
a 
A B 
(algumas 
operações) 
(outras 
operações) 
t1 = t2*t3 
t4 = t5*t6 
C 
Digital Design 
Copyright © 2006 
Frank Vahid 
87 
Exemplo de Escalonamento de Operadores: 
Um Filtro FIR menor 
• No filtro FIR do cap.5 : Só tinhamos 1 estado – o caminho de dados 
computava um novo “y” a cada ciclo de clock 
– Usávamos 3 multiplicadores e 2 somadores: 
xt0 xt1 xt2 
x(t-2) x(t-1) x(t) 
3-tap FIR filter 
x 
y 
clk 
c0 c1 c2 
* * 
+ 
* 
+ 
3 
2 
1 
0 
2x4 
yreg 
e 
Ca1 
CL 
C 
Ca0 
y(t) = c0*x(t) + c1*x(t-1) + c2*x(t-2) 
Entradas: X (N bits) 
Saídas: Y (N bits) 
Registradores locais: 
xt0, xt1, xt2 (N bits) 
S1 
xt0 = x 
xt1 = xt0 
xt2 = xt1 
y = xt0*c0 
 + xt1*c1 
 + xt2*c2 
– Pergunta: 
Podemos 
reduzir o 
tamanho do 
projeto? 
Digital Design 
Copyright © 2006 
Frank Vahid 
88 
Exemplo de Escalonamento de Operadores: 
Um Filtro FIR menor 
• Reduziremos o tamanho do projeto re-escalonando as 
operações 
– Fazendo uma operação de multiplicação por estado 
a 
y(t) = c0*x(t) + c1*x(t-1) + c2*x(t-2) 
Entradas: X (N bits) 
Saídas: Y (N bits) 
Registradores Locais: 
xt0, xt1, xt2 (N bits) 
S1 
(a) 
xt0 = X 
xt1 = xt0 
xt2 = xt1 
Y = xt0*c0 
 + xt1*c1 
 + xt2*c2 
Entradas : X (N bits) 
Saídas : Y (N bits) 
Registradores Locais: 
xt0, xt1, xt2, sum (N bits) 
S1 
S2 
S3 
S4 
S5 
sum = sum + xt0 * c0 
sum = 0 
xt0 = X 
xt1 = xt0 
xt2 = xt1 
sum = sum +xt1 * c1 
sum = sum + xt2 * c2 
Y = sum 
(b) 
Digital Design 
Copyright © 2006 
Frank Vahid 
89 
Exemplo de Escalonamento de Operadores: 
Um Filtro FIR menor 
• Reduziremos o tamanho do projeto re-escalonando as operações 
– Fazendo uma única multiplicação (*) por estado, em conjunto com uma 
adição (+) 
a 
Entradas: X (N bits) 
Saídas: Y (N bits) 
Registradores Locais: 
xt0, xt1, xt2, sum (N bits) 
S1 
S2 
S3 
S4 
S5 
sum = sum + xt0 * c0 
sum = 0 
xt0 = X 
xt1 = xt0 
xt2 = xt1 
sum = sum + xt1 * c1 
sum = sum + xt2 * c2 
Y = sum sum 
* 
+ 
y r eg 
c2 c1 c0 
x t0 x t1 x t2 X 
clk 
x_ld 
y_ld 
Y 
mul_s0 
3 x 1 3 x 1 
mul_s1 
MAC 
Multiplica-acumula 
(MAC): um 
componente comum 
encontrados em 
caminhos de dados 
Digital Design 
Copyright © 2006 
Frank Vahid 
90 
Exemplo de Escalonamento de Operadores: 
Um Filtro FIR menor 
• Muitas outras formas existem 
entre soluções completamente 
concorrente e completamente 
serializadas 
– Ex.: para o caso do filtro FIR, 
podemos ter 1, 2, ou 3 
multiplicadores 
– Podemos também escolher entre 
multiplicadores na forma de array 
(concorrentes) ou 
multiplicadores mais lentos 
(serializados) 
– Cada opção representa um 
compromisso de projeto 
FIR concorrente 
Outras versões 
FIR serial 
atraso 
ta
m
a
n
h
o
 
Digital Design 
Copyright © 2006 
Frank Vahid 
91 
More on Optimizations and Tradeoffs 
• Serial vs. concurrent computation has been a common tradeoff 
theme at all levels of design 
– Serial: Perform tasks one at a time 
– Concurrent: Perform multiple tasks simultaneously 
• Combinational logic tradeoffs 
– Concurrent: Two-level logic (fast but big) 
– Serial: Multi-level logic (smaller but slower) 
• abc + abd + ef  (ab)(c+d) + ef – essentially computes ab first (serialized) 
• Datapath component tradeoffs 
– Serial: Carry-ripple adder (small but slow) 
– Concurrent: Carry-lookahead adder (faster but bigger) 
• Computes the carry-in bits concurrently 
– Also multiplier: concurrent (array-style) vs. serial (shift-and-add) 
• RTL design tradeoffs 
– Concurrent: Schedule multiple operations in one state 
– Serial: Schedule one operation per state 
 
 
6.6 
Digital Design 
Copyright © 2006 
Frank Vahid 
92 
Higher vs. Lower Levels of Design 
• Optimizations and tradeoffs at higher levels typically have 
greater impact than those at lower levels 
– RTL decisions impact size/delay more than gate-level decisions 
Spotlight analogy: The lower you 
are, the less solution landscape is 
illuminated (meaning possible) 
Digital Design 
Copyright © 2006 
Frank Vahid 
93 
Algorithm Selection 
• Chosen algorithm can have big impact 
– e.g., which filtering algorithm? 
• FIR is one type, but others require less computation at 
expense of lower-qualityfiltering 
• Example: Quickly find item’s address in 256-word 
memory 
– One use: data compression. Many others. 
– Algorithm 1: “Linear search” 
• Compare item with M[0], then M[1], M[2], ... 
• 256 comparisons worst case 
– Algorithm 2: “Binary search” (sort memory first) 
• Start considering entire memory range 
– If M[mid]>item, consider lower half of M 
– If M[mid]<item, consider upper half of M 
– Repeat on new smaller range 
– Dividing range by 2 each step; at most 8 such divisions 
• Only 8 comparisons in worst case 
• Choice of algorithm has tremendous impact 
– Far more impact than say choice of comparator type 
 
 
 
0x00000000 
0x00000001 
0x0000000F 2: 
96: 
128: 
255: 
3: 
1: 
0: 
0x000000FF 
0x00000F0A 
0x0000FFAA 
0xFFFF0000 
256x32 memory 
128 
96 
64 
Linear 
search 
Binary 
search 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
94 
Power Optimization 
• Until now, we’ve focused on size and delay 
• Power is another important design criteria 
– Measured in Watts (energy/second) 
• Rate at which energy is consumed 
• Increasingly important as more transistors fit on a 
chip 
– Power not scaling down at same rate as size 
• Means more heat per unit area – cooling is difficult 
• Coupled with battery’s not improving at same rate 
– Means battery can’t supply chip’s power for as long 
– CMOS technology: Switching a wire from 0 to 1 
consumes power (known as dynamic power) 
• P = k * CV
2
f 
– k: constant; C: capacitance of wires; V: voltage; f: switching 
frequency 
• Power reduction methods 
– Reduce voltage: But slower, and there’s a limit 
– What else? 
e
n
e
rg
y 
(1
=
v
a
lu
e
 i
n
 2
0
0
1
) 
8 
4 
2 
1 
battery energy 
density 
energy 
demand 
2001 03 05 07 09 
Digital Design 
Copyright © 2006 
Frank Vahid 
95 
Power Optimization using Clock Gating 
• P = k * CV
2
f 
• Much of a chip’s switching f (>30%) 
due to clock signals 
– After all, clock goes to every register 
– Portion of FIR filter shown on right 
• Notice clock signals n1, n2, n3, n4 
• Solution: Disable clock switching to 
registers unused in a particular state 
– Achieve using AND gates 
– FSM only sets 2nd input to AND gate to 
1 in those states during which register 
gets loaded 
• Note: Advanced method, usually done 
by tools, not designers 
– Putting gates on clock wires creates 
variations in clock signal (clock skew); 
must be done with great care 
y r eg 
c2 c1 c0 
x t0 x t1 x t2 X 
x_ld 
y_ld 
clk n2 n3 n4 n1 
y r eg 
c2 c1 c0 
x t0 x t1 x t2 X 
x_ld 
y_ld 
n2 n3 n4 
n1 
clk 
clk 
n1, n2, n3 
n4 
Much 
switching 
on clock 
wires 
clk 
n1, n2, n3 
n4 
Greatly reduced 
switching – less power 
s1 
s5 
a 
Digital Design 
Copyright © 2006 
Frank Vahid 
96 
Power Optimization using Low-Power Gates on 
Non-Critical Paths 
• Another method: Use low-power gates 
– Multiple versions of gates may exist 
• Fast/high-power, and slow/low-power, versions 
– Use slow/low-power gates on non-critical paths 
• Reduces power, without increasing delay 
high-p o w er g a t es 
l o w -p o w er g a t es 
on nonc r itical p a th 
l o w -p o w er 
g a t es 
del a y 
p 
o 
w 
e 
si
ze
 
r