Sistemas Digitais I - Poli - P1 2015 - Segundo semestre - Turma exclusiva da Engenharia da Computação

Prévia do material em texto

Catálogo
PCS3225 2015S2 Primeira Prova 31/08/2015
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: ⌅. Não use ⇥.
Concordo em doar minhas letras manuscritas para pesquisa em OCR.
Marque as caixas ao lado para formar o seu número USP e escreva seu nome
abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Em um laboratório da Poli há o seguinte aviso colado na entrada:
Proibido comer e beber no laboratório.
Pergunta [t1a] [0.5 ponto] Como estudante assíduo de Sistemas Digitais, o Chico imediatamente entendeu comer
como a variável C e beber como a variável B de uma equação algébrica booleana, em lógica positiva. Marque a
afirmação que melhor representa a equação que o Chico visualizou nos dizeres do aviso:
B.C B.C B.C B + C B � C
Pergunta [t1b] [0.5 ponto] Considerando B e C como entradas, a equação que o Chico visualizou pode ser traduzida
graficamente em uma porta lógica onde as entradas são as variáveis B e C e a saída é verdadeira se o Chico pode
entrar no laboratório. Considerando as portas lógicas na Figura 1, marque somente a afirmação que melhor representa
a porta lógica que o Chico visualizou:
B A C D E F
(a) (b) (c) (d) (e) (f)
Figura 1: Portas lógicas.
Resolução Prof. Bruno Albertini
Esta resolução é para simples conferência e não estabelece critérios de correção.
C B.
Poderia ser C . B também, mas essa alternativa não está nas opções justamente para evitar ambiguidade.
Lembre-se do DeMorgan gráfico. Esta porta é uma NAND.
PCS3115
Mais de 2/3 aceitou doar suas letras. Agradecemos a 
colaboração e estamos estudando maneiras de incentivá-los.
Catálogo
Pergunta [t1c] [0.5 ponto] Astutamente, Chico entrou no laboratório com um salgado e uma lata de refrigerante.
Quando o técnico alertou-o sobre o aviso, Chico argumentou que é impossível para um humano comer e beber ao
mesmo tempo, ou seja, só se pode fazer uma coisa de cada vez dependendo do que você está ingerindo. O técnico teve
que permitir a entrada do Chico, mas logo em seguida mudou a placa para impedir que outros estudantes entrassem
no laboratório portando comidas ou bebidas. Marque somente a afirmação que melhor representa a equação algébrica
para a frase usada pelo técnico usou no novo aviso:
B + C B.C B.C B.C B � C
Pergunta [t2a] [1 ponto] O sistema negabinário é um sistema posicional onde a base é �2. Marque somente as
alternativas que representam a mesma quantidade que 10010�2:
1410 E16 1123 245 11102
Pergunta [t2b] [0.5 ponto] Considere a seguinte soma em BCD8421:
0101 1001 1001
+ 1001 1000 0100
Marque somente a(s) alternativa(s) que representa(m) o resultado desta soma em BCD8421:
0001 0101 1000 0011 1110 10001 1101 1111 0001 0101 0110 0010 1111
Pergunta [t2c] [1 ponto] A equação x2 � x + 29 , cujos coeficientes estão em base decimal, possui raízes exatas em
qual base?
3 2 5 8 16 nenhuma
Pergunta [t2d] [0.5 ponto] Considere operações aritméticas sobre números binários de 8 bits em complemento de 2,
onde ovf significa que o resultado é inválido (a operação resultou em overflow ou transbordo). Para a = 10110000 e
b = 10001000, marque a(s) alternativa(s) correta(s):
a+ b = ovf
b� a = 11110111
a� b = 00001001
a� b = ovf
a+ b = 01010111
Pergunta [t3a] [0.5 ponto] Marque somente a(s) alternativa(s) correta(s). Considerando n grande o suficiente, um
código cuja distância entre palavras é n pode ser usado para:
detectar até d  n� 1 erros ou corrigir até c  n�12 erros.
detectar d  n� 1� 2c erros e corrigir c  n�d�12 erros.
detectar d  n� 1 erros e corrigir c  n�d�12 erros.
detectar d  n erros ou corrigir c  n2 erros.
detectar d  n� 1 erros e corrigir c  n2 erros.
Se a idéia é não permitir a entrada com comidas OU bebidas, basta transformar a frase 
para “proibido comer ou beber”, o equivalente a uma porta NOR. Note que a informação de 
que o Chico entrou anteriormente é útil para afirmar que anteriormente a função retornava 
1 mesmo se o Chico estivesse portando comidas ou bebidas, desde que não estivesse 
comendo e bebendo ao mesmo tempo. 
= (-2)^4 + (-2)^1 = 16 + (-2) = 14
599
984
1583
+
+
=(x-1/3)(x-2/3) : Raízes 1/3 e 2/3, exatas na base 3 (0,1 e 0,2) e dízimas nas demais.
100000000
a+b=10110000
+10001000
100111000
overflow
111101110	
  
a-­‐b=10110000
+01110111
1
00101000
000011110	
  
b-­‐a=10001000
+01001111
1
11011000
carries
n=2c+d+1 Se	
  d=0,	
  c=(n-­‐1)/2
Se	
  c=0,	
  d=n-­‐1
Senão:
d=n-­‐1-­‐2c
c=(n-­‐1-­‐d)/2
0010	
  10000	
  0001
0101	
  	
  1001	
  1001
+1001	
  	
  1000	
  0100
1110	
  10001	
  1101
1101	
  	
  1111	
  0000
1110	
  10001	
  1101
0110	
  	
  0111	
  0110
1	
  0101	
  	
  1000	
  0011
carries
Catálogo
Pergunta [t3b] [1 ponto] Deseja-se transmitir 7 bits de dados úteis utilizando-se o código de Hamming. Sobre esta
transmissão, pode-se afirmar que conterá n bits no total e e que duas palavras quaisquer terão distância mínima de d.
Marque a alternativa que contém, respectivamente, n e d:
11 e 3 7 e 4 10 e 3 8 e 1 9 e 2
O	
  código	
  de	
  Hamming	
  para	
  7	
  bits	
  de	
  dados	
  será:
1	
  	
  2	
  	
  3	
  	
  4	
  	
  5	
  	
  6	
  	
  7	
  	
  8	
  	
  9	
  	
  10	
  11
p1	
  p2	
  d1	
  p3	
  d2	
  d3	
  d4	
  p4	
  d5	
  d6	
  d7
Portanto,	
  para	
  7	
  bits	
  de	
  dados	
  são	
  necessários	
  4	
  de	
  paridade,	
  totalizando	
  11.
A	
  distância	
  de	
  Hamming	
  padrão	
  é	
  sempre	
  3.
Catálogo
Pergunta [dis1] [1 ponto] Simplifique a expressão algébrica A(A + B) + (B + AA)(A + B) para conter o
menor número possível de portas lógicas (incluindo inversor), indicando o que fez em cada um dos passos.
Para uso do professor: 0 1 1 2 5 10
Pergunta [dis2] [1 ponto] Manipule a expressão ABC + AC + AB para que contenha somente AND e NOT
(complemento). Para uso do professor: 0 1 1 2 5 10
A’(A+B)+(B+AA)(A+B’)
A’A+A’B+BA+AAA+BB’+AAB’ Idempotencia	
  +	
  Complementos	
  
A’B+AB+A+AB’ Identidade	
  +	
  Distributividade
B(A’+A)+A(1+B’) Complementos	
  +	
  Elemento	
  Nulo
B+A
ABC+(AC)’+(AB)’ DeMorgan
ABC+A’+C’+A’+B’
ABC+A’+B’+C’
ABC+(ABC)’ DeMorgan
((ABC)’ABC)’
Também	
  são	
  aceitas	
  soluções	
  que	
  mostrem	
  
que	
  a	
  expressão	
  é	
  sempre	
  verdadeira.
Há	
  pelo	
  menos	
  mais	
  uma	
  solução	
  possível.
Catálogo
Pergunta [dis3] [2 pontos] Considere a palavra 1001001 recebida de um transmissor usando o código Hamming(7,4)
padrão. A partir da matriz de verificação de paridade, cacule a síndrome, indique se há erro na palavra rece-
bida e qual a palavra transmitida. Mostre todos os passos, detalhando e justificando as operações que executar.
Para uso do professor: 0 1 1 2 5 10 20
	
  	
  	
  p1	
  p2	
  d1	
  p3	
  d2	
  d3	
  d4
p1	
  X	
  	
  	
  	
  	
  X	
  	
  	
  	
  	
  X	
  	
  	
  	
  	
  X
p2	
  	
  	
  	
  X	
  	
  X	
  	
  	
  	
  	
  	
  	
  	
  X	
  	
  X
p3	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  X	
  	
  X	
  	
  X	
  	
  X
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  1
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  00
1	
  0	
  1	
  0	
  1	
  0	
  1	
  	
  	
  1	
  	
  	
  0
0	
  1	
  1	
  0	
  0	
  1	
  1	
  .	
  0	
  =	
  1	
  =	
  2
0	
  0	
  0	
  1	
  1	
  1	
  1	
  	
  	
  0	
  	
  	
  0
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  1
1101001
Palavra	
  Corrigida
Síndrome
Matriz	
  de	
  Verificação