Buscar

Numeração e codificação Álgebra de Boole Circuitos combinacionais

Prévia do material em texto

Universidade Federal de Santa Catarina
Departamento de Engenharia El
�
etrica
EEL ���� � Sistemas Digitais
Prof� Carlos Maziero
Departamento de Automa�c�ao e Sistemas
Vers�ao ���
Florian�opolis� agosto de ����
�
Indice
� Sistemas de numera�c�ao e codi�ca�c�ao �
��� Sistemas de numera�c�ao � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
����� O sistema decimal � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
����� O sistema bin�ario � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
����� Os sistemas octal e hexadecimal � � � � � � � � � � � � � � � � � � � � � � � �
��� Convers�ao entre bases � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	
����� N�umeros inteiros � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	
����� N�umeros fracion�arios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��� Representa�c�ao de n�umeros com sinal � � � � � � � � � � � � � � � � � � � � � � � � � �
����� Usando sinal e grandeza � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
����� Usando n�umeros complementares � � � � � � � � � � � � � � � � � � � � � � � �
����� Complemento � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
����� Complemento � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��� Opera�c�oes aritm�eticas � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Aritm�etica bin�aria � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Aritm�etica hexadecimal � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Aritm�etica em BCD � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��	 Outros c�odigos importantes � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��	�� Decimal Codi�cado em Bin�ario �BCD� � � � � � � � � � � � � � � � � � � � � ��
��	�� C�odigo Gray � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��	�� C�odigo � segmentos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��	�� C�odigo ASCII � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��
 Exerc��cios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
�
�
Algebra de Boole ��
��� Introdu�c�ao � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �	
��� Fun�c�oes L�ogicas e Tabelas�Verdade � � � � � � � � � � � � � � � � � � � � � � � � � � �
��� Interpola�c�ao de Lagrange � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
��� Formas�padr�ao para express�oes l�ogicas � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Produto�padr�ao de somas � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Soma�padr�ao de produtos � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Expans�ao �as formas�padr�ao � � � � � � � � � � � � � � � � � � � � � � � � � � ��
����� Especi�ca�c�ao de fun�c�oes por maxitermos e minitermos � � � � � � � � � � � ��
��	 Mapas de Karnaugh � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��
 Simpli�ca�c�ao de fun�c�oes l�ogicas � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��� Fun�c�oes incompletamente especi�cadas � � � � � � � � � � � � � � � � � � � � � � � � �
��� Exerc��cios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
ii
� Circuitos Combinacionais �	
��� Introdu�c�ao � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��� S��ntese de circuitos combinacionais � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��� Conversores de c�odigos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��� Codi�cadores e decodi�cadores � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��	 Comparadores de palavras � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��
 Geradores e detectores de paridade � � � � � � � � � � � � � � � � � � � � � � � � � � �
��� Multiplexadores e demultiplexadores � � � � � � � � � � � � � � � � � � � � � � � � � ��
��� Somadores � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��
 Matrizes de fun�c�oes l�ogicas � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �	
���� Exerc��cios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
 L�ogica Seq�uencial 
�
��� Introdu�c�ao � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
��� Flip��ops � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
����� Flip��op RS �Reset�Set� � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	�
����� N��veis e transi�c�oes � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	�
����� Flip��op D �Data� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	�
����� Flip��op T �Toggle� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	�
����	 Flip��op JK � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 		
����
 Flip��op mestre�escravo � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	
����� Convers�ao entre �ip��ops � � � � � � � � � � � � � � � � � � � � � � � � � � � 	
����� Par�ametros operacionais � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	�
��� Diagramas de estado � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	�
����� Estrutura b�asica � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 	
����� Um exemplo� o somador serial � � � � � � � � � � � � � � � � � � � � � � � � 	
����� Tabelas de estados � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
����� Diagramas de estado dos �ip��ops � � � � � � � � � � � � � � � � � � � � � � 
�
��� An�alise de circuitos seq�uenciais s��ncronos � � � � � � � � � � � � � � � � � � � � � � 
�
����� Objetivo � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
����� Um exemplo � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
����� Outro exemplo � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��	 Projeto de circuitos seq�uenciais s��ncronos � � � � � � � � � � � � � � � � � � � � � � 
�
��	�� Um exemplo � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��	�� Outro exemplo � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
��
 Principais circuitos seq�uenciais s��ncronos � � � � � � � � � � � � � � � � � � � � � � � ��
��
�� Registradores de deslocamento � � � � � � � � � � � � � � � � � � � � � � � � ��
��
�� Contadores � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
��� Exerc��cios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
� Circuitos Complementares 	�
	�� Circuitos multivibradores � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
	���� Circuitos mono�est�aveis � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
	���� Circuitos ast�aveis � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �	
	�� Schmitt�Trigger � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
	�� Exerc��cios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
 Mem�orias 	�
�� Introdu�c�ao � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
�� Estrutura do computador � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
�� Mem�orias ROM � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
���� Estrutura b�asica � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
���� Tecnologias� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
���� Aplica�c�oes � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
�� Mem�orias RAM � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
���� Estrutura b�asica � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
���� Tecnologias � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
�	 Bancos de mem�oria � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
�
 Exerc��cios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
� Fam��lias L�ogicas ��
��� Introdu�c�ao � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
��� Tecnologias de Fabrica�c�ao � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
��� Par�ametros de Circuitos Integrados � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
��� Estrutura das sa��das � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��	 A Fam��lia TTL � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
��
 A Fam��lia ECL � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
��� A Fam��lia CMOS � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
��� Compatibilidade entre TTL e CMOS � � � � � � � � � � � � � � � � � � � � � � � � � ���
��
 Exerc��cios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Introdu�c�ao
A palavra �digital� vem do grego digitus� que signi�ca n�umero� Um sistema digital �e portanto
um sistema no qual a informa�c�ao est�a codi�cada e circula sob a forma de n�umeros �ou seja� de
valores discretos�� No lado oposto� nos sistemas ditos anal�ogicos a informa�c�ao varia de modo
cont��nuo� Exemplos comuns de sistemas digitais e anal�ogicos s�ao�
� Sistemas digitais� computador� comutador telef�onico� sem�aforos� etc�
� Sistemas anal�ogicos� ampli�cadores de som� TV tradicional� etc�
As vantagens de usar um sistema no qual a informa�c�ao �e tratada e armazenada sob uma
forma digital s�ao sobretudo a maior precis�ao no tratamento da informa�c�ao e a maior imunidade
a ru��dos externos�
No mundo real a maioria das grandezas s�ao anal�ogicas �ou seja� variam de forma cont��nua��
Para compatibiliz�a�las com o mundo digital �e necess�ario converter os sinais anal�ogicos em digitais
e vice�versa� Isso �e feito atrav�es de circuitos de amostragem �ltros e conversores especiais
chamados conversores anal�ogico�digitais� como mostra a �gura abaixo�
tratamento digital do sinal
conversor
anal�ogico
digital
conversor
digital
anal�ogico
amostrador �ltro
sinal digital
sinal discreto
sinal cont��nuo
Um sistema digital �e chamado bin�ario quando considera somente dois valores poss��veis para a
codi�ca�c�ao da informa�c�ao a ser tratada ou armazenada� Podemos considerar esses valores como
um par aceso�apagado� ligado�desligado� verdadeiro�falso� etc� Veremos mais tarde que esses
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
dois valores s�ao su�cientes para armazenar qualquer informa�c�ao sob a forma digital� embora
nem sempre sejam pr�aticos� A grande vantagem da representa�c�ao bin�aria est�a na facilidade de
implementa�c�ao de circuitos eletr�onicos para armazenar e realizar opera�c�oes sobre informa�c�oes
bin�arias� permitindo a produ�c�ao em larga escala de unidades que efetuam opera�c�oes padroniza�
das e que podem ser associadas entre si para realizar opera�c�oes mais complexas� Al�em disso�
podem ser obtidas implementa�c�oes bastante r�apidas� operando em velocidades que ultrapassam
as centenas de MHz�
A evolu�c�ao dos sistemas digitais teve seu in��cio no s�eculo �
� mas estes somente mostraram�se
�uteis neste s�eculo� e sua vulgariza�c�ao se deu gra�cas �a recente evolu�c�ao na microeletr�onica� Eis
um breve resumo� bastante incompleto� dessa evolu�c�ao�
� s�eculo ��� Pascal e Leibniz prop�oe calculadoras baseadas em engrenagens�
� s�eculo ��� Charles Babbage constr�oi um computador program�avel mec�anico�
� d�ecada de �	� computadores baseados em rel�es s�ao usados para c�alculos de bal��stica�
� ��
�� construido o Eniac� com ������ v�alvulas�
� ��
�� inven�c�ao do transistor�
� ����� primeiro computador comercial� o Univac I�
� anos �	� apogeu dos computadores transistorizados�
� anos 
	� circuitos integrados� inven�c�ao do micro�processador�
� anos �	� integra�c�ao em larga escala �VLSI��
� anos �	� mais de ��
�
transitores em um chip�
� futuro� circuitos biol�ogicos� circuitos usando luz� ���
Este curso visa apresentar as bases necess�arias �a compreens�ao� an�alise e projeto de circuitos
envolvendo sinais digitais� e deve servir como base para um curso posterior sobre microproces�
sadores e microcontroladores� No cap��tulo � veremos o sistema de numera�c�ao bin�ario e como
representar grandezas cont��nuas sob essa forma� Tamb�em veremos outros sistemas de numera�c�ao
�uteis� como o hexadecimal e o octal� O cap��tulo � ser�a dedicado ao estudo da �algebra booleana�
que permite tratar valores codi�cados no sistema bin�ario� No cap��tulo � apresentaremos os
circuitos ditos combinacionais� nos quais as sa��das em um dado momento s�ao fun�c�ao unica e
exclusivamente das entradas naquele instante� ou seja� s�ao circu��tos sem mem�oria� Os circuitos
com mem�oria� nos quais o estado das sa��das em um instante pode depender de estados ante�
riores das entradas� s�ao tamb�em chamados circuitos seq�uenciais� e ser�ao estudados no cap��tulo
� No cap��tulo � ser�ao apresentados alguns circuitos complementares� que n�ao se encaixam
nas classi�ca�c�oes anteriores� como os ast�aveis� mono�est�aveis e o schmitt�trigger� O cap��tulo 
apresenta os princ��pios de funcionamento das mem�orias e seu emprego no projeto de circuitos�
Finalmente o cap��tulo � apresenta as diversas fam��lias de circuitos integrados digitais existentes
no mercado� com especial aten�c�ao para as fam��lias TTL e CMOS�
Cap��tulo �
Sistemas de numera�c�ao e codi	ca�c�ao
��� Sistemas de numera�c�ao
����� O sistema decimal
O sistema decimal� tamb�em chamado sistema na base ��� �e nosso sistema de numera�c�ao cor�
rente� Ele opera com dez d��gitos� �� �� �� �� �� 	� 
� �� � e 
� e os n�umeros s�ao formados por
combina�c�ao destes d��gitos� O incremento de uma unidade a um d��gito faz avan�car ao d��gito
seguinte� at�e chegar ao �ultimo �
�� Ao incrementar este� ele retorna ao d��gito inicial ��� e o
d��gito imediatamente �a esquerda �e incrementado seguindo a mesma regra�
�� � � � �
�
 � � � ��
�� � � � ��
 � � � ���
Assim� a posi�c�ao dos d��gitos em um n�umero tem efeito multiplicador sobre a base� Desta
forma� podemos decompor um n�umero inteiro na base �� da seguinte forma�
��	� � �� ��
�
� �� ��
�
� 	� ��
�
� �� ��
�
e da mesma forma podemos decompor um n�umero fracion�ario�
�����
� � �� ��
�
� �� ��
�
� �� ��
�
� �� ��
��
� 
� ��
��
� �� ��
��
Dos exemplos acima podemos deduzir uma regra gen�erica para a decomposi�c�ao de n�umeros
na base ��� que nos servir�a mais tarde para opera�c�oes de mudan�ca de base�
� � � d
�
d
�
d
�
�d
��
d
��
� � � � � � � � d
�
� ��
�
� d
�
� ��
�
� d
�
� ��
�
� d
��
� ��
��
� d
��
� ��
��
� � � �
����� O sistema bin�ario
O sistema bin�ario� ou sistema na base �� tem uma estrutura an�aloga �a do sistema decimal� com
a ressalva de operar somente com dois d��gitos� � e �� O incremento funciona da mesma forma
que no sistema decimal�
EEL���� � Sistemas Digitais � EEL�UFSC� Prof� Carlos Maziero �
�� � � � ��
�� � � � ��
�� � � � ��
�� � � � ���
Podemos decompor um n�umero bin�ario da mesma forma que �zemos para um n�umero deci�
mal� como uma soma de pot�encias da base�
������
�
� �� ��
�
�
� �� ��
�
�
� �� ��
�
�
� �� ��
�
�
� �� ��
�
�
� �� ��
�
�
A nota�c�ao ��
�
acima indica o n�umero ���� na base � �que equivale ao n�umero � na base ���
como veremos mais tarde�� e que n�ao deve ser confundido com o n�umero ��
��
� Por isso� todas as
opera�c�oes alg�ebricas acima devem ser efetuadas na base �� A decomposi�c�ao tamb�em vale para
os n�umeros fracion�arios�
Considerando os primeiros inteiros� podemos construir uma tabela de equival�encia entre
n�umeros decimais e bin�arios �mais tarde veremos como converter n�umeros entre bases quaisquer
atrav�es de m�etodos num�ericos��
base � � � �� �� ��� ��� ��� ��� ���� ���� ���� � � �
base �� � � � � � 	 
 � � 
 �� � � �
Devido ao seu largo emprego em computadores� os n�umeros bin�arios possuem uma nomen�
clatura pr�opria� Assim� um d��gito bin�ario �e chamado bit� enquanto um grupo de � bits �ou seja�
um n�umero bin�ario inteiro positivo com � d��gitos� �e chamado byte� Em um n�umero bin�ario o bit
mais signi�cativo �o que tem maior peso� �e chamado MSB �Most Signi�cant Bit�� e o bit menos
signi�cativo �e chamado LSB �Least Signi�cant Bit��
����� Os sistemas octal e hexadecimal
De forma forma an�aloga ao anterior� o sistema octal usa a base � e emprega os d��gitos de � a � para
a constru�c�ao de n�umeros� A decomposi�c�ao de n�umeros em pot�encias da base funciona da mesma
forma que nos casos anteriores� Entretanto� como � � �
�
� a convers�ao entre n�umeros bin�arios e
octais �e bastante facilitada� bastando agrupar os d��gitos bin�arios em grupos de � �come�cando pelo
ponto decimal� tanto para a direita quanto para a esquerda� e obter os respectivos equivalentes
octais� fazendo uso da seguinte tabela�
base �� � � � � � 	 
 � � � � �
base � � � �� �� ��� ��� ��� ��� ���� � � �
base � � � � � � 	 
 � �� � � �
Desta forma� o n�umero �������������
�
teria seus d��gitos agrupados na forma
�
��z�
�
���
��z�
�
���
��z�
�
���
��z�
�
���
��z�
�
e seu equivalente octal seria �����
�
�
O sistema hexadecimal usa a base �
 para seus n�umeros� e seus d��gitos s�ao
f�� � � � � 
� A�B�C�D�E� Fg� Podemos construir a seguinte tabela de equival�encia entre os pri�
meiros inteiros nas bases decimal� bin�aria� octal e hexadecimal�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero 	
base �� base � base � base �
� � � �
� � � �
� �� � �
� �� � �
� ��� � �
	 ��� 	 	
 ��� 
 
� ��� � �
� ���� �� �
 ���� �� 
�� ���� �� A
�� ���� �� B
�� ���� �� C
�� ���� �	 D
�� ���� �
 E
�	 ���� �� F
�
 ����� �� ��
� � � � � � � � � � � �
Como �
 � �
�
� a convers�ao entre bin�arios e hexadecimais pode ser obtida agrupando os
d��gitos do n�umero bin�ario em grupos de �� de forma similar �a efetuada para os n�umeros octais�
Assim� o n�umero �������������
�
teria seus d��gitos agrupados na forma
�
��z�
�
����
� �z �
E
����
� �z �
	
����
� �z �
�
e seu equivalente hexa seria �E
�
�	
�
A representa�c�ao em octal ou hexadecimal de n�umeros bin�arios �e bastante empregada em
sistemas digitais� por oferecer n�umeros mais compactos �com menos d��gitos� e mais f�aceis de
visualizar� e tamb�em porque as convers�oes da forma bin�aria para hexa ou octal� e vice�versa�
s�ao bastante simples e r�apidas�
��� Convers�ao entre bases
Podemos realizar as opera�c�oes b�asicas de adi�c�ao� subtra�c�ao� multiplica�c�ao e divis�ao na pr�opria
base em que estamos trabalhando� No entanto� como nos �e natural efetuar essas opera�c�oes
na base ��� frequentemente �e mais simples converter os operandos para essa base� efetuar as
opera�c�oes e reconvert�e�los novamente para a base de origem� Vamos estudar agora a convers�ao
entre uma base qualquer e a base �� de n�umeros inteiros e fracion�arios�
����� N�umeros inteiros
Para converter um n�umero inteiro na base �� �n
��
� para uma base b qualquer �n
��
� n
b
�� basta
dividi�lo por essa base sucessivamente� usando opera�c�oes de divis�ao inteira na base ��� Os restos
r das divis�oes inteiras� tomados de tr�as para frente� nos fornecer�ao os d��gitos do n�umero n
b
� O
exemplo a seguir ilustra a convers�ao do n�umero ��
��
para a base � �q� quociente da divis�ao de
n por b��
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero 
passo � � � � 	 
 � �
n �� �� �� �� 	 � � �
q �� �� �� 	 � � � �
r � � � � � � � �
Assim� ��
��
equivale a �������
�
� Essa opera�c�ao pode ser empregada para converter qualquer
n�umero na base �� para outra base qualquer�
A convers�ao de um n�umero inteiro em uma base qualquer para a base �� �n
b
� n
��
� segue
um processo diferente� que toma por base a decomposi�c�ao do n�umero em pot�encias da base�
como vimos no in��cio deste cap��tulo� Para converter um n�umero n
b
de uma base qualquer b
para a base �� basta exprimi�lo como uma soma de pot�encias da base� exprimir a base em seu
equivalente na base �� e em seguida efetuar as opera�c�oes indicadas na base ��� O exemplo a
seguir� no qual convertemos o n�umero �������
�
para a base ��� ilustra esse processo�
�������
�
� �� ��
	
�
� �� ��
�
�
� �� ��
�
�
�
�� ��
�
�
� �� ��
�
�
� �� ��
�
�
� �� ��
�
�
� �� �
	
� �� �
�
� �� �
�
� �� �
�
� �� �
�
� �� �
�
� �� �
�
� 
� � �
 � � � � � �
� ��
A maneira mais simples de efetuar a convers�ao de um n�umero de uma base a qualquer
para outra base b qualquer �n
a
� n
b
� �e usar a base �� como passo intermedi�ario� efetuando
n
a
� n
��
� n
b
�
����� N�umeros fracion�arios
Em uma mudan�ca de base� a separa�c�ao entre as partes inteira e fracion�aria de um n�umero �e
mantida� Assim� a mudan�ca de base de um n�umero fracion�ario consiste da mudan�ca de base de
suas partes inteira e fracion�aria� separadamente� Como j�a vimos a mudan�ca de base de n�umeros
inteiros� resta agora estudar a troca de base da parte fracion�aria� Dado um n�umero fracion�ario
n
b
� este pode ser expresso sob a forma i
b
�f
b
� onde i
b
e f
b
s�ao respectivamente as partes inteira
e fracion�aria de n
b
� A parte f
b
pode ser expressa da forma
f
b
� d
��
� b
��
� d
��
� b
��
� d
��
� b
��
� d
��
� b
��
� � � �
A convers�ao de um n�umero fracion�ario de uma base b qualquer para a base �� segue o mesmo
procedimento da convers�ao de n�umeros inteiros� usando a decomposi�c�ao acima� Por exemplo� a
convers�ao do n�umero x
�
� �����������
�
para a base �� efetua�se da seguinte forma�
x
��
� �� �
�
� �� �
�
� �� �
�
� �� �
�
�
�� �
��
� �� �
��
� �� �
��
� �� �
��
� �� �
��
� �� �
�	
� �
�
� �
�
� �
�
� �
��
� �
��
� �
�	
� � � � � � �
�
�
�
�
�
�
�
�
� ��������	
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
Para a convers�ao de um n�umero fracion�ario da base �� para outra base b qualquer �n
��
� n
b
��
convertemos a parte inteira usando o m�etodo apresentado anteriormente �divis�ao inteira� e
convertemos a parte fracion�aria usando o m�etodo apresentado a seguir� vimos que podemos
representar a parte fracion�aria f de um n�umeroem uma base b por�
f � d
��
b
��
� d
��
b
��
� d
��
b
��
� � � �
onde d
i
� � s�ao os d��gitos que comp�oe a parte fracion�aria� Por exemplo� �����
��
� ����
��
�
�� ��
��
� �� ��
��
� A convers�ao para uma base b qualquer consiste portanto em encontrar os
valores d
i
na base desejada b� Multiplicando f pela base b obtemos�
f � b � d
��
b
�
� d
��
b
��
� d
��
b
��
� � � �
Assim d
��
pode ser retirado da parte inteira de f � b� Aplicando sucessivamente essa mul�
tiplica�c�ao sobre a parte fracion�aria restante obteremos os demais d��gitos de f � Como exemplo�
vamos converter o valor decimal X
��
� ����� para a base ��
�� Parte inteira� �
��
� ���
�
�� Parte fracion�aria� f � �����
itera�c�ao f
i
f
i
� b d
�i
� ����� ����� �
� ����� ��
�� �
� ��
�� ���	
 �
� ���	
 ��	�� �
	 ��	�� ����� �
 ����� ����� �
� ����� ���
 �
� ���
 ���
� �
 ���
� ����� �
�� ����� ���
� �
�� ���
� ��	�
 �
�� ��	�
 ����� �
�� ����� ����� �
�� � � � � � � � � �
E assim f
��
� �����
��
� �������������� � � �
�
e �nalmente X
��
� �����
��
�
���������������� � � �
�
�
Observe que um n�umero com um n�umero �nito de d��gitos em uma base pode tornar�se uma
d��zima peri�odica em outra base� isso ocorre com bastante freq�u�encia�
��� Representa�c�ao de n�umeros com sinal
Usando n�umeros bin�arios com d bits podemos representar at�e �
d
valores distintos� Por exemplo�
em uma posi�c�ao de mem�oria de � bits podemos representar at�e �	
 valores distintos� Em um
registrador de � bits podemos ter os valores inteiros positivos de � a �	� como mostra a �gura a
seguir�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
�
�
�
�
�
�
�
	
��
��
��
��
��
��
�
Caso desejarmos representar valores negativos� podemos empregar diversas abordagens� como
veremos na seq�u�encia�
����� Usando sinal e grandeza
Podemos empregar o bit mais signi�cativo �MSB� para indicar o sinal �� � � e � � �� e os
demais bits para a grandeza do valor� Assim teriamos�
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
�
�
�
�
�
�
�
�
��
��
��
��
��
��
��
��
A faixa de valores representados vai de �� a �� ����
d��
� ���� A grande desvantagem
desta t�ecnica �e a dupla representa�c�ao do zero ��� e ���� Esta t�ecnica tamb�em �e chamada
sinal�magnitude�
����� Usando n�umeros complementares
Os n�umeros bin�arios manipulados por um processador tem um n�umero n �nito e normalmente
constante de d��gitos ��� �
� ��� � � � �� As opera�c�oes aritm�eticas entre esses n�umeros s�ao ent�ao
efetuadas sempre em m�odulo M � �
n
� Para uma contagem usando � bits ter��amos ent�ao�
���� ���� ���� ���� ���� ���� ���� ���� ���� ���� � � �
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero 
Veremos agora que atrav�es dos n�umeros chamados complementares �e poss��vel implementar
a subtra�c�ao usando as opera�c�oes de soma em m�odulo� o que permite simpli�car bastante os
circuitos necess�arios �as opera�c�oes aritm�eticas� Existem dois tipos de n�umeros complementares�
o complemento � �C�� e o complemento � �C��� que estudaremos a seguir�
����� Complemento �
Tendo sido especi�cado o n�umero de d��gitos d� e o m�odulo M � �
d
� o complemento � �C�� de
um n�umero n� indicado por n
�
� �e de�nido por�
n
�
�M � n modM
Por exemplo� sendo um n�umero de � bits n � 	
��
� ����
�
� nosso m�oduloM vale �
�
� �����
�
e o complemento � de n �e dado por�
n
�
� �
�
� 	 mod �
 � �����
�
� ����
�
� ����
�
Vejamos os complementos � dos primeiros n�umeros com � bits�
n
��
n
�
�
�
� n n
�
� ���� ����� ����
� ���� ���� ����
� ���� ���� ����
� ���� ���� ����
� ���� ���� ����
	 ���� ���� ����
Ao inv�es de efetuarmos opera�c�oes de subtra�c�ao em bin�ario� podemos calcular n
�
atrav�es de
uma simples regra pr�atica�
�� O complemento � n
�
tem o mesmo n�umero de bits d que o n�umero n�
�� Percorrendo n da direita para a esquerda �MSB � LSB�� preservar todos os bits at�e o
primeiro ��� �inclusive�� e complementar os demais�
Vejamos alguns exemplos�
d n n
�
� ���� ����
� ������� �������
� ��� ���
� � �
� �������� ��������
Vamos agora representar n�umeros negativos usando esta t�ecnica� o bit mais signi�cativo
continua representando o sinal� mas os n�umeros negativos s�ao representados pelos complementos
� dos n�umeros positivos correspondentes� Por exemplo� se n
��
� ��� e �
��
� ����
�
ent�ao
n
�
� ����
�
� ����� No sentido contr�ario� caso n
�
� ���� ent�ao o n�umero �e negativo �MSB vale
�� e j n
��
j� n
�
�
� ����
�
� ���� � �
��
e �nalmente n
��
� ��� O uso deste m�etodo em n�umeros
de � bits est�a ilustrado na �gura a seguir�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
�
�
�
�
�
�
�
�	
��
��
��
��
��
��
��
�
����� Complemento �
O complemento � �C�� de um n�umero bin�ario n com d bits� indicado por n
�
� �e de�nido por�
n
�
� ��
d
� ��� n modM
Como regra pr�atica� basta complementar todos os bits do n�umero n� como mostram os
exemplos a seguir�
d n n
�
� ���� ����
� ������� �������
� ��� ���
� � �
� �������� ��������
A diferen�ca entre os complementos � e � �e de uma unidade� n
�
� n
�
� � ou n
�
� n
�
� ��
Usando esta t�ecnica� os n�umeros negativos podem ser representados pelos complementos �
dos n�umeros positivos correspondentes� Assim temos�
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
����
�
�
�
�
�
�
�
��
��
��
��
��
��
��
��
�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
Por exemplo� se n
��
� �� ent�ao n
�
� ����
�
� ���� �usando � bits temos �
��
� ����
�
�� De
modo inverso se n
�
� ���� ent�ao n
��
� � e n
�
�
� ����
�
� ���� � �
��
� Assim temos n
��
� ���
�
E importante observar que� em todas as t�ecnicas apresentadas� quando MSB�n
�
� � � ent�ao
n
��
�e negativo�
��� Opera�c�oes aritm�eticas
����� Aritm�etica bin�aria
As opera�c�oes aritm�eticas b�asicas em c�odigo bin�ario seguem o mesmo mecanismo que as opera�c�oes
em base ��� Por exemplo� vejamos a opera�c�ao de soma entre os n�umeros ��������
�
e ��������
�
�
� � � �
� � � � � � � �
� � � � � � � � �
� � � � � � � � �
Em muitos casos o resultado de uma opera�c�ao deve ser mantido dentro de um determinado
n�umero de bits� e para isso os bits mais signi�cativos em excesso devem ser descartados� Se
quisermos manter o resultado da soma acima em � bits� o resultado a ser considerado deve ser
��������
�
�
Deve ser tomado muito cuidado em rela�c�ao �a codi�ca�c�ao usada� Se estivermos considerando
n�umeros com sinal �C�� C�� etc�� a soma de dois n�umeros positivos pode ter seu bit mais
signi�cativo ativado e assim indicar um n�umero negativo� como mostra o exemplo a seguir�
� �
� � � � � � � �� � � � � � � � �
� � � � � � � �
Da mesma maneira� a soma de dois n�umeros negativos pode provocar um excesso �que ser�a
descartado para manter o resultado em n bits� e assim gerar um resultado positivo�
A subtra�c�ao entre dois n�umeros bin�arios pode ser facilmente realizada atrav�es da soma do
primeiro com o complemento �C�� C�� do segundo� O resultado deve ser considerado usando a
mesma codi�ca�c�ao de complemento� Vejamos por exemplo a opera�c�ao X � ��
��
� �
��
� que em
bin�ario �ca ��������
�
� ��������
�
�vamos considerar valores em � bits e usar uma codi�ca�c�ao
em C���
X � �������� � ��������
� �������� � ��������
�
� �������� � ��������
� ��������
� ����������
�
�
� ���������
� ��
��
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
Assim como a soma� a subtra�c�ao tamb�em pode ser afetada por eventuais excessos que devam
ser descartados� Embora bem mais complexas� as opera�c�oes de produto e divis�ao seguem os
mecanismos conhecidos para a base decimal�
����� Aritm�etica hexadecimal
����� Aritm�etica em BCD
��	 Outros c�odigos importantes
Embora os sistemas digitais sejam sempre bin�arios� isto �e� todos os sinais existentes no sistema
s�o podem assumir dois valores� em alguns casos espec���cos �e interessante a utiliza�c�ao de outras
codi�ca�c�oes bin�arias distintas da cl�assica� devido a certas vantagens oferecidas por estas�
����� Decimal Codi�cado em Bin�ario 	BCD
Neste c�odigo cada d��gito de um n�umero decimal �e codi�cado na forma de um n�umero bin�ario�
Para representar os dez d��gitos �� � � � 
� s�ao necess�arios � bits� Assim� o n�umero ���
��
seria
codi�cado como ����
� �z �
�
����
� �z �
�
����
� �z �
�
� Observe que usando uma codi�ca�c�ao bin�aria cl�assica ter��amos
���
��
� ���������
�
� Os n�umeros em BCD s�ao mais longos que os bin�arios normais� pois cada
d��gito decimal �e representado separadamente� Um dos principais usos da codi�ca�c�ao em BCD
encontra�se na implementa�c�ao de displays num�ericos de calculadoras� rel�ogios� etc�
����� C�odigo Gray
Este c�odigo tamb�em �e chamado de �c�odigo espelhado� e caracteriza�se pelo fato de que a re�
presenta�c�ao de dois n�umeros consecutivos nunca difere em mais que um bit� A tabela a seguir
indica a constru�c�ao dos primeiros n�umeros neste c�odigo�
Decimal Bin�ario Gray Decimal Bin�ario Gray
� ���� ���� � ���� ����
� ���� ���� 
 ���� ����
� ���� ���� �� ���� ����
� ���� ���� �� ���� ����
� ���� ���� �� ���� ����
	 ���� ���� �� ���� ����
 ���� ���� �� ���� ����
� ���� ���� �	 ���� ����
O c�odigo Gray pode ser importante em situa�c�oes onde �e necess�ario minimizar as transi�c�oes
de bits no sistema �por quest�oes de velocidade e imunidade a ru��dos�� Por exemplo� para passar
de � a � no sistema bin�ario cl�assico s�ao necess�arias � transi�c�oes de bits ����� � ����� enquanto
usando o c�odigo Gray apenas uma transi�c�ao �e necess�aria ����� � ������
����� C�odigo � segmentos
Este c�odigo est�a relacionado com os mostradores de � segmentos usados normalmente em cal�
culadoras e outros aparelhos simples� para a apresenta�c�ao de resultados� Um mostrador desse
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
tipo �e constru��do usando sete segmentos luminosos que podem ser combinados para representar
os d��gitos de � a 
� e as letras de �A� a �F�� como mostra a �gura a seguir�
f
a
b
c
d
e
g
Considerando um segmento iluminado como tendo o valor ���� temos a seguinte tabela para
os d��gitos hexadecimais n c�odigo de � segmentos�
n
o
a b c d e f g n
o
a b c d e f g
� � � � � � � � � � � � � � � �
� � � � � � � � 
 � � � � � � �
� � � � � � � � A � � � � � � �
� � � � � � � � B � � � � � � �
� � � � � � � � C � � � � � � �
	 � � � � � � � D � � � � � � �
 � � � � � � � E � � � � � � �
� � � � � � � � F � � � � � � �
����� C�odigo ASCII
��
 Exerc��cios
�� Converta os seguintes n�umeros para as bases bin�aria� octal� decimal e hexadecimal� ��	
��
�
�� ���� ����
�
� �
�
��
� �� ���� ����
�
� �AC
�	
� ���� ����
�
� 	BD
�	
e ��
���
��
�
�� Indique quais dos seguintes n�umeros s�ao hexadecimais v�alidos� BED� CAB� DEAD�
BAG e F�CA�
�� Quantos n�umeros inteiros positivos podem ser expressos usando k d��gitos em uma base b�
�� Expresse os seguintes n�umeros decimais no sistema sinal�magnitude� com m�odulo de � bits�
����� �	
� ����� ��� �� �� e �����
	� Idem ao anterior� usando os sistemas complemento � e complemento �� Analise e compare
a representa�c�ao dos n�umeros em cada um desses sistemas� Quais s�ao as vantagens e
desvantagens de cada um deles�
� Os seguintes n�umeros positivos e negativos correspondem a representa�c�oes em diferentes
bases� ajustados em �
 bits �ou seja� m�odulo �
�� Encontre as representa�c�oes decimais�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
considerando que todos est�ao representados no sistema C�� ���� ���� ���� ����
�
� FA��
H
e ���� ���� ���� ����
�
�
�� Passando previamente os valores �a base bin�aria� calcular X � Y e X �Y � considerando os
n�umeros em C�� Indicar em que situa�c�ao ocorre over�ow ��estouro� da capacidade de um
registro de n bits��
a� em � bits� X � B�
H
b� em �
 bits� X � F�A
H
Y � 
C
H
Y � ��	��
��
�� Resolver as seguintes opera�c�oes�
a� S
�
� �����
�
� ������
�
c� S
�
� ��
��
� �������
�
b� S
�
� ��������
�
� �A
H
d� S
�
� ���� � ����
Cap��tulo �
�
Algebra de Boole
��� Introdu�c�ao
Uma vari�avel booleana pode assumir somente dois valores� � �falso� e � �verdadeiro�� Portanto�
se x 	� � ent�ao x � � e se x 	� � ent�ao x � �� Chamamos de fun�c�ao booleana uma rela�c�ao F
entre duas ou mais vari�aveis booleanas x
�
� x
�
� � � � � x
n
� realizada com as opera�c�oes de soma ���
e produto ��� �muitas vezes A �B �e representado na forma AB��
A �algebra de Boole apresenta uma s�erie de propriedades que nos ser�ao �uteis na manipula�c�ao
de fun�c�oes l�ogicas� que estudaremos a seguir� Sendo A� B e C vari�aveis booleanas �tamb�em
chamadas vari�aveis l�ogicas�� temos�
�� Propriedade Comutativa�
A � B � B � A
A�B � B �A
�� Propriedade associativa�
A�BC� � �AB�C
A� �B � C� � �A�B� � C
�� Propriedade distributiva�
A�B � C� � AB �AC
A�BC � �A�B��A� C�
Al�em das propriedades acima� uma s�erie de postulados �ou leis fundamentais� rege a
�
Algebra
de Boole� Esses postulados podem ser facilmente provados� mas isto foge ao objetivo deste curso�
Os postulados b�asicos que utilizaremos s�ao�
��
se A 	� � ent�ao A � �
se A 	� � ent�ao A � �
��
� � � � �
� � � � �
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
��
� � � � �
� � � � �
��
� � � � �
� � � � �
	�
� � �
� � �
Al�em dos postulados� alguns teoremas envolvendo vari�aveis booleanas nos ser�ao �uteis�
��
A� � � A
A � � � A
��
A� � � �
A � � � �
��
A�A � A
A � A � A
�� �A� � A
	�
A�A � �
A � A � �
� Teoremas de Morgan�
A�B � C � � � � � A � B � C � � � �
A � B � C � � � � � A�B �C � � � �
��
A�A�B� � A�AB � A
A�AB � A�A�B� � A
A veri�ca�c�ao da validade dos teoremas �e bastante simples� bastando construir as tabelas�
verdade com todos os valores poss��veis para as vari�aveis envolvidas�
Tanto os teoremas quanto os postulados se apresentam aos pares� Para cada um deles� seu
par respectivo pode ser obtido trocando�se os ��� por ��� e os ��� por ���� e vice�versa� Essa
propriedade �e chamada dualidade�Por exemplo� A� � � A
� A � � � A�
��� Fun�c�oes L�ogicas e Tabelas�Verdade
As fun�c�oes l�ogicas ou booleanas b�asicas s�ao descritas abaixo� com seus s��mbolos e suas tabelas�
verdade� Uma tabela�verdade �e simplesmente uma tabela enumerando todos os poss��veis estados
das entradas de uma fun�c�ao e seu respectivo valor de sa��da� As fun�c�oes l�ogicas podem tambem
ser chamadas portas l�ogicas� sobretudo quando implementadas em circuitos�
Fun�c�ao N
�
AO � tamb�em chamada inversor ou NOT� e representada por F�A� � A� Sua
tabela�verdade �e dada por�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
A A
� �
� �
Em diagramas de circuitos digitais um inversor �e representado pelo s��mbolo abaixo�
A F
Fun�c�ao E � tamb�em denominada AND� assume valor verdadeiro se e somente se ambas as
entradas s�ao verdadeiras�
�
E representada por F�A�B� � A � B ou simplesmente AB �em
l�ogica tamb�em pode ser encontrada a forma A �B�� Sua tabela�verdade �e�
A B A �B
� � �
� � �
� � �
� � �
Seu s��mbolo em diagramas �e�
A
B
F
Fun�c�ao OU � tamb�em denominada OR� esta fun�c�ao �e verdadeira se alguma de suas entradas
o for� F�A�B� � A � B �em l�ogica tamb�em pode ser encontrada a forma A 
 B�� Sua
tabela�verdade �e�
A B A�B
� � �
� � �
� � �
� � �
Seu s��mbolo em diagramas �e�
A
B
F
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
Al�em das fun�c�oes b�asicas E� OU e N
�
AO� algumas outras fun�c�oes simples que podem ser
derivadas destas tamb�em nos ser�ao �uteis� S�ao elas�
Fun�c�ao n�ao�E � tamb�em chamada NAND� �e a inversa da fun�c�ao E� F�A�B� � A � B�
A B A �B
� � �
� � �
� � �
� � �
Seu s��mbolo em diagramas �e�
A
B
F
Fun�c�ao n�ao�OU � tamb�em chamada NOR� �e a inversa da fun�c�ao OU � F�A�B� � A�B�
A B A�B
� � �
� � �
� � �
� � �
Seu s��mbolo em diagramas �e�
A
B
F
Fun�c�ao OU�exclusivo � tamb�em chamada XOR� �e indicada pelo operador ���� e �e verdadeira
somente se suas duas entradas forem opostas� F�A�B� � A�B � AB �AB�
A B A�B
� � �
� � �
� � �
� � �
Seu s��mbolo em diagramas �e�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
A
B
F
As fun�c�oes N�ao�E e N�ao�OU s�ao conhecidas como fun�c�oes universais� por serem freq�uente�
mente empregadas na s��ntese das demais fun�c�oes� devido �a simplicidade de sua implementa�c�ao
interna�
��� Interpola�c�ao de Lagrange
Uma ferramenta muito �util na resolu�c�ao de problema l�ogicos �e a interpola�c�ao de Lagrange� Para
uma fun�c�ao l�ogica F desconhecida com n vari�aveis� a partir de todas as combina�c�oes de suas
vari�aveis de entrada e dos respectivos valores de sa��da� ela nos permite encontrar um polin�omio
representando a fun�c�ao F � Por exemplo� para n � � temos a seguinte tabela�verdade�
x F�x�
� F���
� F���
O que nos d�a o seguinte polin�omio de Lagrange� F�x� � F���x � F���x� De modo similar�
se n � � temos a seguinte tabela�verdade�
x y F�x� y�
� � F��� ��
� � F��� ��
� � F��� ��
� � F��� ��
Que resulta no seguinte polin�omio�
F�x� y� � F��� ��x y � F��� ��x y � F��� ��x y � F��� ��x y
De maneira gen�erica� se tivermos valores da forma�
x
�
x
�
x
�
� � � x
n
F�x
�
� x
�
� x
�
� � � � � x
n
�
� � � � � � � F��� �� � � � � �� ��
� � � � � � � F��� �� � � � � �� ��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � � � � � � F��� �� � � � � �� ��
� � � � � � � F��� �� � � � � �� ��
O que nos d�a o seguinte polin�omio gen�erico�
P�x
�
� x
�
� x
�
� � � � � x
n
� � F��� �� �� � � � � ��x
�
x
�
x
�
� � � x
n
� F��� �� �� � � � � ��x
�
x
�
x
�
� � � x
n
� � � �
� F��� �� �� � � � � ��x
�
x
�
x
�
� � � x
n
� F��� �� �� � � � � ��x
�
x
�
x
�
� � � x
n
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
Vejamos agora um exemplo� Dada a seguinte tabela�verdade para uma fun�c�ao F�x� y��
podemos determin�a�la atrav�es do polin�omio de Lagrange�
x y F�x� y�
� � �
� � �
� � �
� � �
O polin�omio resultante tem a seguinte forma�
F�x� y� � F��� ��x y � F��� ��x y � F��� ��x y � F��� ��x y
� � � x y � � � x y � � � x y � � � x y
F�x� y� � x y
��� Formas�padr�ao para express�oes l�ogicas
Neste ��tem estudaremos as formas�padr�ao nas quais as express�oes l�ogicas podem ser escritas�
Estas nos ser�ao �uteis mais tarde� para simpli�car o estudo das fun�c�oes l�ogicas� Existem basica�
mente duas formas� a soma padr�ao de produtos e o produto padr�ao de somas�
����� Produto�padr
ao de somas
Neste caso a fun�c�ao l�ogica �e expressa como um produto de termos� cada termo sendo uma soma
envolvendo todas as vari�aveis� Por exemplo�
F�A�B�C� � �A�B � C� � �A�B � C� � �A�B � C�
Cada termo da express�ao �e chamado maxitermo� e a express�ao em sua forma m��nima �e
chamada forma can�onica de maxitermos�
Esta forma apresenta a seguinte propriedade� F � � se ao menos um dos maxitermos for
zero� e um maxitermo ser�a zero somente se todas as suas vari�aveis forem zero� Assim� pode�
se concluir que cada maxitermo corresponde a uma linha da tabela�verdade na qual F � ��
Veremos como empregar esta propriedade na se�c�ao ������
����� Soma�padr
ao de produtos
Neste caso a fun�c�ao l�ogica �e expressa como uma soma de termos� cada termo sendo um produto
envolvendo todas as vari�aveis� Por exemplo�
F�A�B�C� � ABC �ABC �ABC
Cada termo da express�ao �e chamado minitermo� e a express�ao em sua forma m��nima �e
chamada forma can�onica de minitermos�
Esta forma apresenta a seguinte propriedade� F � � se ao menos um dos minitermos for
�� e um minitermo ser�a � somente se todas as suas vari�aveis forem �� Assim� pode�se concluir
que cada minitermo corresponde a uma linha da tabela�verdade na qual F � �� Veremos como
empregar esta propriedade na se�c�ao ������
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
����� Expans
ao �as formas�padr
ao
Dada uma fun�c�ao l�ogica expressa sob a forma de uma soma de produtos� �e poss��vel expandi�la
para a forma padr�ao aplicando os teoremas da l�ogica booleana� como mostra o exemplo abaixo�
Y � AB �AC �BC
� AB � � �AC � � �BC � �
� AB�C � C� �AC�B �B� �BC�A�A�
� ABC �ABC �ABC �ABC �ABC �A BC
� ABC �ABC �ABC �A BC
Da mesma forma� um produto de somas pode ser expandido para a forma padr�ao� como
mostra o exemplo�
Y � �P �Q��Q�R��P �R�
� �P �Q� ���Q�R� ���P �R� ��
� �P �Q�RR��PP �Q�R��P �QQ�R�
� �P �Q�R��P �Q�R��P �Q�R��P �Q�R��P �Q�R��P �Q�R�
� �P �Q�R��P �Q�R��P �Q�R��P �Q�R��P �Q�R�
����� Especi�ca�c
ao de fun�c
oes por maxitermos e minitermos
Veremos agora como utilizar as formas padr�ao de maxitermos e minitermos para representar
fun�c�oes l�ogicas� Dada uma fun�c�ao envolvendo n vari�aveis� teremos �
n
minitermos �indicados por
m
i
� e �
n
maxitermos �indicados por M
i
� distintos� Veja o exemplo abaixo para tr�es vari�aveis�
A B C minitermo maxitermo
� � � A B C � m
�
A�B � C �M
�
� � � A B C � m
�
A�B � C �M
�
� � � A B C � m
�
A�B � C �M
�
� � � A B C � m
�
A�B � C �M
�
� � � A B C � m
�
A�B � C �M
�
� � � A B C � m
�
A�B � C �M
�
� � � A B C � m
	
A�B � C �M
	
� � � A B C � m
�
A�B � C �M
�
Dada sua tabela�verdade� podemos expressar uma fun�c�ao sob a forma de maxitermos ou
minitermos� Por exemplo� para a fun�c�ao l�ogica de�nida pela tabela�verdade abaixo�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
A B C F�A�B�C�� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
Teremos sua express�ao sob a forma de minitermos �nos quais F � �� dada por�
F�A�B�C� � A B C �ABC �ABC �ABC
� m
�
�m
�
�m
�
�m
�
�
X
m��� �� �� ��
E a mesma fun�c�ao sob a forma de maxitermos �nos quais F � �� �ca�
F�A�B�C� � �A�B � C��A�B � C��A�B � C��A �B � C�
� M
�
�M
�
�M
�
�M
	
�
Y
M��� � � 
�
��	 Mapas de Karnaugh
O mapa de Karnaugh de uma fun�c�ao l�ogica� tamb�em chamado mapa K� �e uma representa�c�ao
gr�a�ca da tabela�verdade da fun�c�ao �ou seja� de todas as combina�c�oes de todas as vari�aveis
da fun�c�ao�� expressa sob a forma de minitermos e ou maxitermos� O ordenamento das c�elulas
adjacentes em um mapa de Karnaugh segue o c�odigo Gray� A principal utilidade dos mapas de
Karnaugh �e a simpli�ca�c�ao de express�oes l�ogicas� como veremos na pr�oxima se�c�ao�
O mapa de Karnaugh de uma fun�c�ao pode ser constru��do diretamente a partir de sua tabela
verdade� Para uma fun�c�ao F com duas vari�aveis A e B ter��amos a seguinte tabela�verdade e o
respectivo mapa de Karnaugh�
A B F�A�B�
� � F��� �� � m
�
� � F��� �� � m
�
� � F��� �� � m
�
� � F��� �� � m
�
B
A
� �
� m
�
m
�
� m
�
m
�
Para fun�c�oes com tr�es e quatro vari�aveis ter��amos os seguintes mapas�
C
AB
�� �� �� ��
� m
�
m
�
m
	
m
�
� m
�
m
�
m
�
m
�
CD
AB
�� �� �� ��
�� m
�
m
�
m
��
m
�
�� m
�
m
�
m
��
m
�� m
�
m
�
m
��
m
��
�� m
�
m
	
m
��
m
��
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
Vejamos como exemplo a fun�c�ao abaixo� representada atrav�es de uma tabela�verdade e de
seu respectivo mapa de Karnaugh�
A B F�A�B�
� � �
� � �
� � �
� � �
B
A
� �
� �
� �
Vejamos outro exemplo�
A B C F�A�B�C�
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
C
AB
�� �� �� ��
� � � �
� � �
No caso acima podemos escrever F �
P
m��� �� �� 
� �� �
Q
M��� �� 	�� Deve�se observar que
existe uma rela�c�ao direta entre os minitermos maxitermos e os quadros do mapa de Karnaugh�
Al�em disso� em um mapa de Karnaugh representamos somente os minitermos ��� ou os maxi�
termos ���� por raz�oes de clareza �para o processo de simpli�ca�c�ao estaremos interessados em
associar somente os minitermos ou somente os maxitermos��
Para construir um mapa de Karnaugh com mais de quatro vari�aveis constru��mos um mapa
b�asico com quatro vari�aveis e o repetimos tantas vezes quantas forem as combina�c�oes das va�
ri�aveis restantes� formando assim um mapa externo� O exemplo abaixo mostra a constru�c�ao de
um mapa de Karnaugh para uma fun�c�ao de seis vari�aveis�
B
A
� �
�
CD
EF
�� �� �� ��
��
��
��
��
CD
EF
�� �� �� ��
��
��
��
��
�
CD
EF
�� �� �� ��
��
��
��
��
CD
EF
�� �� �� ��
��
��
��
��
��
 Simpli
ca�c�ao de fun�c�oes l�ogicas
A minimiza�c�ao de fun�c�oes l�ogicas �e importante para minimizar os custos de implementa�c�ao dos
circuitos digitais e melhorar sua velocidade de trabalho �a cada opera�c�ao l�ogica est�a associado
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
uma dura�c�ao�� Podemos encontrar uma forma m��nima para uma fun�c�ao atrav�es dos mapas de
Karnaugh ou atrav�es da aplica�c�ao dos postulados e teoremas da �algebra de Boole� Vejamos dois
exemplos de simpli�ca�c�ao usando a �algebra de Boole�
Y � ABC �ABC �ABC �ABC
� AB�C � C� �AB�C � C�
� AB �AB
� B�A�A�
� B
Y � �A�B � C� �A�B � C� �A�B � C� �A�B �C�
� !A� �B �C�" !A� �B � C�" !�A�B� � C" !�A�B� � C"
� !AA�A�B � C� � �B � C�A� �B � C��B � C�"
!�A�B��A�B� � �A�B�C �C�A�B� � CC"
� !A�B � C� � �B � C�A� �B � C�"
!�A�B� � �A�B�C � C�A�B�"
� !�A�A� ���B � C�" !�� �C � C��A�B�"
� !��B � C�" !��A�B�"
� �B � C��A �B�
Para a simpli�ca�c�ao usando os mapas de Karnaugh� nos baseamos em sua principal proprie�
dade que �e o fato de que dois quadros adjacentes �na horizontal ou na vertical� em um mapa de
Karnaugh correspondem a dois minitermos �ou dois maxitermos� nos quais apenas uma vari�avel
difere� estando complementada em um deles e n�ao no outro� Esses dois minitermos adjacen�
tes podem ser combinados com a remo�c�ao da vari�avel que difere entre ambos� como mostra o
exemplo a seguir� para F � m
�
�m
��
�
CD
AB
�� �� �� ��
�� � �
��
��
��
Podemos escrever F � AB C D � ABC D � AC D�B � B� � AC D� Assim� dois termos
envolvendo quatro vari�aveis puderam ser substitu��dos por um s�o termo envolvendo tr�es vari�aveis�
Como regra geral� um conjunto regular de �
n
minitermos adjacentes �ou seja� um ret�angulo com
�� �� �� �� � � �minitermos� pode ser agrupado em um termo �unico do qual podem ser eliminadas
n vari�aveis� Por exemplo� para o mapa abaixo�
CD
AB
�� �� �� ��
��
�� � �
�� � �
��
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �	
Podemos escrever F � m
�
�m
�
�m
�
�m
�
� AD�
�
E importante observar que� devido ao
uso do c�odigo Gray� as colunas e linhas externas s�ao adjacentes entre si� como mostra o exemplo
abaixo� no qual encontramos dois grupos com quatro termos cada�
CD
AB
�� �� �� ��
�� � �
�� � �
�� � �
�� � �
De acordo com o mapa acima podemos escrever� F � m
�
�m
�
�m
�
�m
	
�m
�m
��
�
m
��
�m
��
� BD �BD � B �D� Vejamos mais um exemplo�
CD
AB
�� �� �� ��
�� � �
��
��
�� � �
Neste caso F � m
�
�m
�
�m
�
�m
��
� B D� Ao construir a fun�c�ao m��nima devemos associar
entre si os termos de maneira a eliminar o maior n�umero poss��vel de vari�aveis� at�e cobrir todos
os termos existentes no mapa�
�
As vezes um termo tem de ser usado em mais de uma associa�c�ao�
como mostra o exemplo abaixo� no qual temos F � BD �A CD�
CD
AB
�� �� �� ��
��
�� � � �
�� � �
��
Para levar a uma boa simpli�ca�c�ao da fun�c�ao� devem ser seguidas as seguintes regras na
constru�c�ao dos grupos�
� Minimizar o n�umero de grupos �para minimizar o n�umero de termos na express�ao �nal��
� Cada grupo deve englobar o maior n�umero poss��vel de casas �para eliminar o maior n�umero
poss��vel de vari�aveis no termo correspondente ao grupo� na express�ao �nal��
Por exemplo� no mapa abaixo as associa�c�oes da esquerda levam a uma express�ao m��nima
da fun�c�ao �F � A CD � ABC � ACD � ABC�� enquanto as associa�c�oes da direita n�ao �F �
BD �A B CD �ABCD �ABCD �ABCD��
CD
AB
�� �� �� ��
�� �
�� � � �
�� � � �
�� �
CD
AB
�� �� �� ��
�� �
�� � � �
�� � � �
�� �
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
Caso sejam empregados maxitermos ao inv�es de minitermos� devemos tentar agrupar os zeros
do mapa de Karnaugh� lembrando que a regra de complemento funciona ao contr�ario� Veja o
exemplo�
CD
AB
�� �� �� ��
�� � �
�� � �
�� � �
��
Podemos escrever F �M
�
�M
�
�M
�
�M
�
�M
��
�M
��
� �A� C� � �A� C �D��
��� Fun�c�oes incompletamente especi
cadas
Uma fun�c�ao l�ogica �e dita incompletamente especi�cada quando� para uma dada combina�c�ao das
vari�aveis de entrada� a sa��da �e irrelevante� podendo assumir � ou �� Isso ocorre quando�
� certas combina�c�oes das vari�aveis de entrada nunca ocorrem�
� as entradas existem em circunst�ancias tais que n�ao in�uenciam no comportamento global
do sistema�
Nestascondi�c�oes a fun�c�ao pode assumir � ou � na tabela�verdade ou no mapa de Karnaugh�
sendo ent�ao indicada por um �X�� Podemos considerar a fun�c�ao nessas condi�c�oes como � ou �� de�
pendendo da conveni�encia �por exemplo� para auxiliar os agrupamentos no mapa de Karnaugh��
Vejamos o exemplo da fun�c�ao dada por F �
P
m��� �� 	� 
� 
� �
P
X���� ��� ��� ��� ��� �	� e seu
respectivo mapa de Karnaugh�
CD
AB
�� �� �� ��
��
�� � � X �
�� X X
�� � � X X
Se interpretarmos como � os valores dem
��
em
��
e como � os demais valores indeterminados�
ent�ao podemos agrupar os termos em dois grupos e teremos a forma m��nima F � CD � CD �
C �D�
��� Exerc��cios
�� Utilize os postulados e teoremas da �algebra de Boole para simpli�car as seguintes ex�
press�oes l�ogicas�
a� S �W �X � Y �Z �W �� c� S � �X�Y �W �Z� �X � Y �
b� S � �W �X � Y ��WX � Y ��Y � Z��W � Z� d� S � X � �X Y �X X�
�� Indique quais das seguintes a�rma�c�oes s�ao v�alidas�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
a� a opera�c�ao NAND n�ao �e associativa c� AB AB � AB
b� AB �AB � AB d� AC �AC � B 
� AB �AB � C
�� Expresse as fun�c�oes abaixo como somas de produtos� indicando tamb�em sua formas
can�onicas �somas padr�ao de produtos��
a� X � �A�BC��B �CD� b� X � �A�BC��D �BC�
�� Idem ao anterior� mas usando produtos de somas�
a� X � A�BC c� X � �A�B��A� C��B � C�
b� X � �A�BC��B � CD�
	� Encontrar as express�oes duais das express�oes abaixo�
a� F � XY Z �XY Z c� F � X�Y � Z�X � Y ��
b� F � �X � Y �Z �XY Z
� Minimize as seguintes fun�c�oes usando o mapa de Karnaugh�
a� F
�
�
P
m��� �� �� d� F
�
�
Q
M��� �� �� 	� ��� ��� ���
b� F
�
�
P
m��� �� 	 � �� e� F
�
�
P
m��� �� 	� ��� ��� ���
c� F
�
�
P
m��� 	� �� ��� �� � �	� f� F
	
�
Q
M�	� ��� ��� �X��� ��
�� Uma fun�c�ao chamada majorit�aria produz uma sa��da l�ogica alta ��� quando a maioria
de suas entradas est�a em n��vel alto ���� Considere e fun�c�ao para � entradas e encontre a
express�ao l�ogica correspondente atrav�es da tabela�verdade e do mapa de Karnaugh �escolha
a forma mais conveniente� maxitermos ou minitermos��
Cap��tulo �
Circuitos Combinacionais
��� Introdu�c�ao
Este cap��tulo �e dedicado ao estudo e projeto de sistemas l�ogicos combinacionais� Um circuito
l�ogico �e dito combinacional quando suas sa��das em um determinado instante t s�ao fun�c�ao uni�
camente de suas entradas naquele instante� ou seja� suas sa��das s�ao combina�c�oes l�ogicas de suas
entradas naquele instante� Isso signi�ca que qualquer modi�ca�c�ao nas entradas ser�a imediata�
mente considerada pelas sa��das�
e
�
�t�
e
�
�t�
e
�
�t�
e
m
�t�
s
�
�t�
s
�
�t�
s
�
�t�
s
n
�t�
sa��das
circuito
combinacional
entradas
��� S��ntese de circuitos combinacionais
O projeto de um circuito combinacional segue habitualmente os seguintes passos� que devem ser
aplicados para cada uma das sa��das do circuito�
�� Descri�c�ao do comportamento desejado para o sistema� atrav�es de uma tabela�verdade
enumerando todos os estados poss��veis para as entradas e os respectivos valores das sa��das�
�� Constru�c�ao do mapa de Karnaugh da fun�c�ao� a partir da tabela�verdade�
�� Obten�c�ao da forma m��nima para a fun�c�ao desejada� a partir dos agrupamentos de termos
no mapa de Karnaugh�
�� Constru�c�ao do circuito indicado pela express�ao m��nima da fun�c�ao� usando as portas l�ogicas
b�asicas �AND� OR� NOT�� Podem ser efetuadas manipula�c�oes sobre a express�ao para
permitir o uso de portas derivadas �XOR� ou universais �NAND� NOR��
No �nal deste cap��tulo veremos casos onde este roteiro n�ao pode ser aplicado diretamente�
devido ao grande n�umero de entradas� que torna impratic�avel a de�ni�c�ao de uma tabela�verdade
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
para o sistema inteiro �por exemplo� � entradas geram �	
 estados poss��veis�� Entretanto os
circuitos onde isso ocorre podem normalmente ser divididos em sub�sistemas� para os quais o
roteiro acima pode ser empregado�
Vejamos o uso do roteiro acima em um exemplo� vamos projetar um detector de n�umeros
primos de � bits� entre ����
�
e ����
�
�� Os n�umeros primos de � bits s�ao� �� �� �� 	� �� �� e ��� e
nosso circuito disp�oe de quatro entradas �os quatro d��gitos do n�umero bin�ario� e uma sa��da �a
indica�c�ao de que o n�umero na entrada �e primo�� o que nos leva a seguinte tabela�verdade�
n A B C D F
� � � � � �
� � � � � �
� � � � � �
� � � � � �
� � � � � �
	 � � � � �
 � � � � �
� � � � � �
� � � � � �
 � � � � �
�� � � � � �
�� � � � � �
�� � � � � �
�� � � � � �
�� � � � � �
�	 � � � � �
A partir da tabela�verdade acima podemos construir o seguinte mapa de Karnaugh para a
fun�c�ao F �
CD
AB
�� �� �� ��
��
�� � � �
�� � � �
�� �
A express�ao que pode ser obtida dos agrupamentos do mapa de Karnaugh tem a forma�
F � BCD �BCD �A BC �AD
Podemos construir o circuito indicado pela express�ao acima usando somente as portas l�ogicas
b�asicas� Cada termo �produto� da express�ao �e implementado por uma porta AND� e a soma dos
termos �e implementada por uma porta OR� o que nos d�a o seguinte circuito�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
A B C D
F
Podemos empregar os teoremas de Morgan �A�B � C � A B C� para transformar a fun�c�ao
sob a forma de uma soma de produtos em um produto de complementos� eliminando as somas
�e a porta OR��
F � BCD �BCD �A BC �AD
� BCD �BCD �A BC �AD
� BCD � BCD �A BC �AD
Desta forma a implementa�c�ao do circuito passa a empregar somente portas NAND�
A B C D
F
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
Embora implementado de outra forma� este circuito executa exatamente a mesma fun�c�ao
que o anterior� Esta forma de implementa�c�ao� empregando somente portas NAND� �e chamada
�l�ogica NAND�NAND��
��� Conversores de c�odigos
Os circuitos conversores de c�odigos se destinam �a convers�ao entre diferentes sistemas de codi��
ca�c�ao de n�umeros bin�arios� como o Gray� o BCD� o � segmentos� etc� A maioria destes circuitos
se encontra dispon��vel em circuitos integrados comerciais� Vejamos como exemplo a implemen�
ta�c�ao de um conversor de n�umeros de � bits em c�odigo Gray para bin�ario� A tabela�verdade da
fun�c�ao de convers�ao possui quatro entradas �os � d��gitos do n�umero em c�odigo Gray� e quatro
sa��das �os quatro d��gitos do c�odigo bin�ario��
n G
�
G
�
G
�
G
�
B
�
B
�
B
�
B
�
� � � � � � � � �
� � � � � � � � �
� � � � � � � � �
� � � � � � � � �
� � � � � � � � �
	 � � � � � � � �
 � � � � � � � �
� � � � � � � � �
� � � � � � � � �
 � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�	 � � � � � � � �
Com base na tabela�verdade podemos construir os mapas de Karnaugh para cada uma das
sa��das B
�
� � � B
�
� Come�cando com B
�
temos�
G
�
G
�
G
�
G
�
�� �� �� ��
�� � �
�� � �
�� � �
�� � �
O que nos leva �a express�ao B
�
� G
�
� Para B
�
teremos�
G
�
G
�
G
�
G
�
�� �� �� ��
�� � �
�� � �
�� � �
�� � �
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
O que nos leva a B
�
� G
�
G
�
�G
�
G
�
� G
�
�G
�
� Para B
�
teremos�
G
�
G
�
G
�
G
�
�� �� �� ��
�� � �
�� � �
�� � �
�� � �
B
�
� G
�
G�
G
�
�G
�
G
�
G
�
�G
�
G
�
G
�
�G
�
G
�
G
�
� G
�
�G
�
G
�
�G
�
G
�
� �G
�
�G
�
G
�
�G
�
G
�
�
� G
�
�G
�
�G
�
� �G
�
�G
�
�G
�
�
� G
�
� �G
�
�G
�
�
B
�
� G
�
�G
�
�G
�
Finalmente para B
�
teremos�
G
�
G
�
G
�
G
�
�� �� �� ��
�� � �
�� � �
�� � �
�� � �
O que nos levar�a a B
�
� G
�
�G
�
�G
�
�G
�
�este resultado pode ser encontrado de maneira
an�aloga ao obtido para B
�
�� Desta forma temos o seguinte conjunto de fun�c�oes que devem ser
implementadas�
B
�
� G
�
B
�
� G
�
�G
�
B
�
� G
�
�G
�
�G
�
� B
�
�G
�
B
�
� G
�
�G
�
�G
�
�G
�
� B
�
�G
�
A implementa�c�ao mais simples e direta destas express�oes �e dada pelo circuito abaixo�
G
�
G
�
G
�
G
�
B
�
B
�
B
�
B
�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
Veremos agora em outro exemplo a convers�ao de bin�ario para complemento �� com palavras
bin�arias de � bits �B
�
B
�
B
�
B
�
� e seus respectivos complementos �C
�
C
�
C
�
C
�
�� A tabela�verdade
assume a seguinte forma�
n B
�
B
�
B
�
B
�
C
�
C
�
C
�
C
�
� � � � � � � � �
� � � � � � � � �
� � � � � � � � �
� � � � � � � � �
� � � � � � � � �
	 � � � � � � � �
 � � � � � � � �
� � � � � � � � �
� � � � � � � � �
 � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�� � � � � � � � �
�	 � � � � � � � �
Com base na tabela�verdade podemos construir os mapas de Karnaugh e deduzir as ex�
press�oes l�ogicas para cada uma das sa��das C
�
� � � C
�
�
B
�
B
�
B
�
B
�
�� �� �� ��
�� � �
�� � �
�� � �
�� � �
B
�
B
�
B
�
B
�
�� �� �� ��
�� � �
�� � �
�� � �
�� � �
C
�
� B
�
B
�
�B
�
B
�
�B
�
B
�
�B
�
B
�
B
�
B
�
C
�
� B
�
B
�
�B
�
B
�
�B
�
B
�
B
�
B
�
B
�
B
�
B
�
�� �� �� ��
��
�� � � � �
��
�� � � � �
B
�
B
�
B
�
B
�
�� �� �� ��
��
�� � � � �
�� � � � �
��
C
�
� B
�
B
�
�B
�
B
�
C
�
� B
�
As express�oes acima nos permitem implementar o circuito como apresentado na �gura a
seguir� usando as portas b�asicas� Obviamente outras implementa�c�oes s�ao poss��veis� manipulando
adequadamente as express�oes acima�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
B
�
B
�
B
�
B
�
C
�
C
�
C
�
C
�
Al�em dos circuitos apresentados acima� podemos ter codi�cadores de bin�ario para comple�
mento � e vice�versa� de BCD para � segmentos� etc� que podem ser facilmente projetados pelo
leitor usando a t�ecnica apresentada acima�
��� Codi
cadores e decodi
cadores
Um decodi�cador �e um dispositivo com n entradas e �
n
sa��das� Para cada valor da entrada uma
�unica sa��da �e verdadeira e as demais s�ao falsas� Normalmente representamos um decodi�cador
atrav�es de um bloco� como por exemplo para o decodi�cador com � entradas e �
 sa��das�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �	
Decodi�cador �� ��
E
�
E
�
E
�
E
�
S
�
S
�
S
�
S
��
A tabela�verdade do decodi�cador �� �
 acima assume esta forma�
E
�
E
�
E
�
E
�
S
�
S
�
S
�
S
�
� � � S
��
� � � � � � � � � � � �
� � � � � � � � � � � �
� � � � � � � � � � � �
� � � � � � � � � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � � � � � � � � � � �
Por exemplo� para o decodi�cador de �� � linhas teremos a seguinte tabela�verdade�
E
�
E
�
S
�
S
�
S
�
S
�
� � � � � �
� � � � � �
� � � � � �
� � � � � �
Que pode ser facilmente implementada atrav�es do circuito abaixo �note que usamos uma
nova nota�c�ao para as entradas complementadas��
S
�
S
�
S
�
S
�
E
�
E
�
Um decodi�cador pode ser �util na implementa�c�ao de fun�c�oes l�ogicas simples� como alguns
dos circuitos vistos anteriormente� Por exemplo� eis uma implementa�c�ao do detector de n�umeros
primos de � bits usando um decodi�cador �� �
�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
E
�
E
�
E
�
E
�
F
Decodi�cador �� ��
S
�
S
��
Devido �as suas caracter��sticas construtivas� nas principais fam��lias l�ogicas uma sa��da no
estado baixo �� ou L�ow�� drena uma corrente signi�cativamente maior que uma sa��da em estado
alto �� ou H�igh��� Para uma porta TTL convencional� a corrente em uma sa��da em estado baixo
�e da ordem de ��
 mA� enquanto uma sa��da em estado alto drena apenas cerca de ��� �A� ou
seja� uma corrente � vezes menor� O comportamento esperado para um um decodi�cador com
�
n
sa��das �e ter a sa��da ativa em estado alto e as demais �
n
� � sa��das em estado baixo� sendo
por isso chamado de ativo alto� Entretanto� para diminuir o consumo de energia e a conseq�uente
dissipa�c�ao de calor nos circuitos integrados� a maioria dos decodi�cadores comerciais emprega
uma l�ogica de ativo baixo� na qual a sa��da ativa se encontra em estado baixo ��� e as demais
em estado alto ���� O decodi�cador comercial integrado TTL ������ de � � � vias� �e entao
representado por�
TTL 	��
�
E
�
E
�
E
�
S
�
S
�
S
�
S
�
EN
�
EN
�
EN
�
Al�em das entradas que de�nem a sa��da ativa� um decodi�cador pode ter uma ou mais entradas
do tipo strobe ou enable�disable� como as entradas EN
�
� EN
�
e EN
�
do decodi�cador � � �
acima� A fun�c�ao dessas entradas �e inibir a sa��da ativa do decodi�cador� na situa�c�ao acima�
enquanto EN
�
EN
�
EN
�
for falso� nenhuma sa��da ser�a ativada� n�ao importando o estado das
entradas E
i
� Considerando um decodi�cador �� � com uma entrada enable teremos a seguinte
tabela�verdade�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
EN E
�
E
�
S
�
S
�
S
�
S
�
� X X � � � �
� � � � � � �
� � � � � � �
� � � � � � �
� � � � � � �
Este comportamento pode ser facilmente implementado atrav�es do seguinte circuito�
S
�
S
�
S
�
S
�
EN
E
�
E
�
As entradas do tipo enable podem ser usadas para conectar decodi�cadores em cascata�
permitindo assim a constru�c�ao de decodi�cadores maiores� O exemplo abaixo mostra a imple�
menta�c�ao de um decodi�cador �� �
 usando 	 decodi�cadores �� ��
S
�
S
�
S
�
S
�
S
�
S
��
S
��
S
��
S
�
S
�
S
�
S
�
E
�
E
�
EN E
�
E
�
EN
S
�
S
�
S
�
S
�
E
�
E
�
EN
S
�
S
�
S
�
S
�
E
�
E
�
EN
S
�
S
�
S
�
S
�
E
�
E
�
E
�
E
�
EN EN
E
�
E
�
S
�
S
�
S
�
S
�
Ao contr�ario dos decodi�cadores� os codi�cadores convertem entre �
n
entradas e uma sa��da
com n bits� O circuito integrado ����� �e um codi�cador de � � � vias� funcionando em ativobaixo �sua entrada ativa est�a em estado ��� Sua tabela�verdade �e dada por�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
EN E
�
E
�
E
�
E
�
E
�
E
�
E
	
E
�
S
�
S
�
S
�
EO GS
� 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 x � � � � � � � � �
� x x x � � � � � � � � � �
� x x � � � � � � � � � � �
� x � � � � � � � � � � � �
� � � � � � � � � � � � � �
� � � � � � � � � � � � � �
A entrada EN habilita a sa��da� As sa��das complementadas S
�
� � � S
�
indicam o d��gito bin�ario
correspondente �a entrada ativa de n�umero mais elevado �trata�se ent�ao de um codi�cador com
prioridade� onde as entradas de n�umero mais elevado tem prioridade�� A sa��da EO �e ativada ���
quando n�ao existir entrada ativa� ou caso as sa��das estejam desabilitadas �EN � ��� A sa��da GS
�chamada group service� �e ativada caso haja alguma entrada ativa� independente da habilita�c�ao
das sa��das�
��	 Comparadores de palavras
Um circuito comparador simples permite comparar duas palavras de n bits� indicando quando
estas s�ao iguais� Esse tipo de comparador pode ser facilmente implementado atrav�es de portas
n�ao�ou�exclusivo entre os respectivos bits das palavras a comparar �A
i
�B
i
� A
i
B
i
�A
i
B
i
��
A
�
B
�
A
�
B
�
A
�
B
�
A
n
B
n
A � B
Circuitos comparadores mais complexos podem ser construidos para indicar se A � B� A � B
ou A � B� O circuito integrado TTL ���	 �e um comparador de palavras de � bits com essa
possibilidade�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero �
TTL
	���
A
�
A
�
A
�
A
�
B
�
B
�
B
�
B
�
entradas
A � B
A � B
A � B
A � B
A � B
A � B
sa��das
condi�c�ao
anterior
As entradas indicadas como condi�c�ao anterior permitem a conex�ao de comparadores em
cascata para efetuar a compara�c�ao de palavras maiores� No circuito do exemplo a seguir podem
ser comparadas palavras de � bits�
�
�
�
A
�
A
�
A
�
A
�
B
�
B
�
B
�
B
�
TTL
	���
A
�
B
�
B
�
TTL
	���
A
�
A
�
A
	
B
�
B
	
A � B
A � B
A � B
A � B
A � B
A � B
A � B
A � B
A � B
A � B
A � B
A � B
��
 Geradores e detectores de paridade
Os geradores e detectores de paridade s�ao muito �uteis em comunica�c�ao de dados� onde permitem
detectar a presen�ca de erros de transmiss�ao� A t�ecnica b�asica consiste em associar um bit de
paridade ao dado a ser transmitido� indicando se este tem um n�umero par ou ��mpar de bits
ativos� Ao ser recebido� o dado �e testado em rela�c�ao ao bit de paridade� e eventuais erros podem
ser detectados�
paridade
gerador de
paridade
detector de
dadodado
erro
paridade
bit de
Um gerador simples de bit de paridade para palavras de � bits e seu respectivo detector s�ao
apresentados no diagrama a seguir�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
D
�
D
�
D
�
D
�
bit de
paridade
erro
Um circuito �e dito de paridade par� quando o n�umero total de bits ���� incluindo o de pari�
dade� �e par� Caso contr�ario� o circuito �e dito de paridade ��mpar� O circuito acima apresentado
�e de paridade par� pois o bit de paridade vale � se o dado possuir um n�umero par de bits ativos�
e � sen�ao� em conseq�u�encia� o n�umero total de bits ativos �e sempre par�
No caso da detec�c�ao de erro em um dado� o sistema de recep�c�ao de dados pode solicitar
que este seja retransmitido� ou tomar outra atitude� Os circuitos de paridade s�ao capazes de
detectar erros quando um n�umero ��mpar de bits �e alterado durante a transmiss�ao� Existem
circuitos mais complexos de comunica�c�ao de dados capazes de detectar erros de modo mais
abrangente e mesmo corrigir erros pequenos� sem necessidade de retransmiss�ao� No entanto
esses circuitos necessitam de mais bits de controle associados a cada dado�
��� Multiplexadores e demultiplexadores
Um multiplexador �e um dispositivo com �
n
entradas de dados� uma sa��da e n entradas de sele�c�ao
que de�nem qual entrada de dados transferir para a sa��da� Um t��pico multiplexador de � vias �e
mostrado abaixo�
x�
MUX
E
�
E
�
D
�
D
�
D
�
D
�
S
�
D
�
D
�
D
�
D
�
E
�
E
�
S
A tabela�verdade do multiplexador acima �e dada por�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
E
�
E
�
S
� � D
�
� � D
�
� � D
�
� � D
�
O que nos leva a S � E
�
E
�
D
�
� E
�
E
�
D
�
� E
�
E
�
D
�
� E
�
E
�
D
�
� Esta fun�c�ao pode ser
facilmente implementada pelo circuito abaixo�
D
�
D
�
D
�
D
�
E
�
E
�
sa��da
Assim como os decodi�cadores� os multiplexadores podem ser usados na implementa�c�ao de
fun�c�oes l�ogicas� como por exemplo a detec�c�ao de n�umeros primos�
MUX ��
E
�
E
�
E
�
E
�
�
�
sa��da
D
�
D
��
Os demultiplexadores permitem distribuir um dado em sua entrada para uma entre �
n
sa��das�
escolhida de acordo com as entradas de sele�c�ao�
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
DEMUX
D
E
�
E
�
S
�
S
�
S
�
S
�
�
D
E
�
E
�
S
�
S
�
S
�
S
�
Para um demultiplexador de � vias ter��amos a seguinte tabela�verdade�
E
�
E
�
S
�
S
�
S
�
S
�
� � D � � �
� � � D � �
� � � � D �
� � � � � D
Esta tabela pode ser implementada pelo seguinte circuito�
S
�
S
�
S
�
S
�
E
�
E
�
D
Os dispositivos mux demux comerciais geralmente possuem uma ou mais entradas do tipo
enable� complementadas ou n�ao� que permitem conectar circuitos em cascata� As principais apli�
ca�c�oes desses dispositivos s�ao a sele�c�ao e encaminhamento de dados� a convers�ao s�erie�paralelo
de dados� a gera�c�ao de formas de onda e a s��ntese de fun�c�oes l�ogicas� Um exemplo de circui�
to integrado comercial �e o TTL ���	�� que possui dois multiplexadores de � vias controlados
simultaneamente �as entradas de sele�c�ao s�ao comuns a ambos��
EEL���� � Sistemas Digitais � EEL�UFSC � Prof� Carlos Maziero ��
MUX MUX
S
a
S
b
E
�
E
�
A
�
A
�
A
�
A
�
B
�
B
�
B
�
B
�
��� Somadores
Os circuitos somadores permitem efetuar opera�c�oes de soma entre duas palavras de n bits�
levando em conta o �vai�um� �excesso ou carry�� Para a soma de duas palavras A e B de � bit
teremos a seguinte tabela�verdade� para a soma S e o excesso C�
A B S C
� � � �
� � � �
� � � �
� � � �
Pode�se ent�ao concluir que S � A � B e C � A � B� O circuito de�nido por essas fun�c�oes
�e chamado �meio�somador� e sua implementa�c�ao �e trivial� usando apenas duas portas l�ogicas�
Um circuito �somador completo� deve levar em conta o excesso ��vai�um�� de um eventual ante�
cessor� para poder ser associado em cascata a outros somadores e assim implementar somadores
para palavras mais longas que � bit� A tabela�verdade para um somador completo de � bit �e
dada por�
C
i��
A
i
B
i
S
i
C
i
� � � � �
� � � � �
� � � � �
� � � � �
� � � � �
� � � � �
� � � � �
� � � � �
Atrav�es dos mapas de Karnaugh obtemos as fun�c�oes l�ogicas e sua implementa�c�ao�
S
i
� A

Continue navegando