Sistemas Digitais I - Poli - P1 2017

Prévia do material em texto

y +1/1/60+ y
PCS3115 - Sistemas Digitais I - 2017S1 Primeira Avaliação - 19/04/2017
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
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 �.
1 Gomi 2 Simplício 3 Spina 4 Bruno
Marque as caixas ao lado para formar o seu número USP, as caixas acima para
sua turma e escreva seu nome abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1) Esta prova contém 4 (quatro) questões. Verifique atentamente se todas elas estão presentes. Em caso de dúvida,
favor alertar o Professor.
2) Como primeira atividade preencha imediatamente o seu nome e o seu número USP nesta página. Provas não
identificadas não serão corrigidas e poderão ser recolhidas pelo Professor durante a sua execução.
3) Realize a prova apenas nas folhas de questão. Respostas fornecidas fora do local a elas destinadas não serão
corrigidas. O papel almaço é para ser utilizado como rascunho e não é necessário entregar.
4) A duração total da prova é de 100 minutos.
5) É proibido o uso de quaisquer equipamentos eletrônicos (calculadora, smartphone, tablets, etc).
6) A interpretação das questões faz parte da avaliação dos alunos. Caso considere alguma hipótese que não esteja
explicitada no enunciado, indique claramente na resposta, fazendo as assunções que julgar pertinentes.
7) A prova é SEM CONSULTA.
Boa Prova!
y y
y +1/2/59+ y
y y
y +1/3/58+ y
Questão 1
1 (a) [1,0 ponto] Sejam A = (204)N+1, B = (102)N , C = (41)N e D = (2)N . Sabendo-se que A−B− 4C + 4D3 =
−410, determine o valor de N , justificando sua resposta. Dica: converta os números para a base 10, em função de N ,
e então realize os cálculos para determinar N .
Para uso do professor: 0 1 2 3 4 5 6 7 8 9 10
y y
y +1/4/57+ y
1 (b) [0,7 pontos] Realize as conversões de base indicadas, considerando números inteiros positivos:
Para uso do professor: 0 1 2 3 4 5 6 7
I) CA50116, para base 2
II) 4523210, para base 16
III) 10100101, 1012, para base 10
1 (c) [0,8 pontos] Realize as seguintes operações com números inteiros positivos, nas bases indicadas:
Para uso do professor: 0 1 2 3 4 5 6 7 8
I) BEBAD016 + CA1D016 , na base 16
II) 25116 × 2716 , na base 16
III) 732018 − 340328, na base 8
IV) 3310 ÷ 610, na base 2
y y
y +1/5/56+ y
Questão 2 [2,5 pontos]
2 (a) [0,5 pontos] Escreva as representações com 6 bits em sinal e magnitude, complemento de 1 e complemento
de 2 para cada um dos números decimais apresentados.
Para uso do professor: 0 1 2 3 5
Binário (valor sem sinal) Sinal e magnitude Complemento de 1 Complemento de 2
+1
-19
+25
-13
2 (b) [0,5 pontos] Repita o exercício anterior com 8 bits.
Para uso do professor: 0 1 2 3 5
Binário (valor sem sinal) Sinal e magnitude Complemento de 1 Complemento de 2
+1
-19
+25
-13
2 (c) [1,5 pontos] Responda as questões e realize as operações sobre os números de 8 bits indicando passo a passo,
o andamento, explicitando os "vai um", "vem um", etc.
(c.1) [0,3 pontos] Qual o menor e o maior número que se pode representar, em complemento de 2, utilizando-se
8 bits?
Para uso do professor: 0 1 2 3
Complemento de 1 < N <
Complemento de 2 < N <
Para facilitar seu trabalho, sugerimos, primeiramente, escrever com 8 bits os números em complemento de 2.
Binário (valor sem sinal) Complemento de 1 Complemento de 2
+11 (−11) (−11)
+22 (−22) (−22)
+33 (−33) (−33)
+44 (−44) (−44)
+55 (−55) (−55)
y y
y +1/6/55+ y
2 (c.2) [0,3 pontos] Em complemento de 2, (+22) + (+33) =
Para uso do professor: 0 1 2 3
2 (c.3) [0,3 pontos] Em complemento de 2, (+22) + (−33) =
Para uso do professor: 0 1 2 3
2 (c.4) [0,3 pontos] Em complemento de 1, (−33)− (−11) =
Para uso do professor: 0 1 2 3
2 (c.5) [0,3 pontos] Em complemento de 1, (+44)− (+22) =
Para uso do professor: 0 1 2 3
y y
y +1/7/54+ y
Questão 3 [2,5 pontos] Na época da guerra fria os espiões usavam OTPs (One Time
Pads) para criptografar informações. Os OTPs são cadernos, onde cada folha é um punhado
de números que parecem aleatórios, mas na verdade contêm uma mensagem criptografada
com uma chave. A chave para uma determinada folha de um OTP era transmitida por
estações de rádio conhecidas como NSs (Number Stations). As NSs eram estações de rádio
de ondas curtas e longo alcance, que podiam ser captadas por um rádio simples (de ondas
curtas, obviamente). Ao sintonizar uma delas, o que se ouve é uma voz sintetizada falando
números. A rádio conhecida como Lincolnshire Poacher transmitia números de cinco dígitos
em horários pré-determinados, como por exemplo: zero-dois-cinco-cinco-oito. Ninguém sabe
ao certo se este mecanismo ainda é utilizado, mas ainda hoje pode-se sintonizar várias NSs
ao redor do mundo.
3 (a) [1 ponto] É comum as NSs transmitirem usando repetição, para garantir que o espião recebeu a chave correta.
Se uma estação com repetição 3 fosse transmitir a palavra 0110 em binário, por exemplo, na verdade transmitiria
000111111000. Assumindo que o espião receba a palavra completa, mas que potencialmente haja erros nos seus
bits, este esquema de transmissão com repetição garante que o espião receberá o código corretamente? Justifique sua
resposta.
Para uso do professor: 0 1 1 2 5 10
y y
y +1/8/53+ y
Tabela 1: Tabela ASCII para caracteres imprimíveis.
Dec Char Dec Char Dec Char Dec Char Dec Char Dec Char
32 [espaço] 48 0 64 @ 80 P 96 ‘ 112 p
33 ! 49 1 65 A 81 Q 97 a 113 q
34 " 50 2 66 B 82 R 98 b 114 r
35 # 51 3 67 C 83 S 99 c 115 s
36 $ 52 4 68 D 84 T 100 d 116 t
37 % 53 5 69 E 85 U 101 e 117 u
38 & 54 6 70 F 86 V 102 f 118 v
39 ’ 55 7 71 G 87 W 103 g 119 w
40 ( 56 8 72 H 88 X 104 h 120 x
41 ) 57 9 73 I 89 Y 105 i 121 y
42 * 58 : 74 J 90 Z 106 j 122 z
43 + 59 ; 75 K 91 [ 107 k 123 {
44 , 60 < 76 L 92 \ 108 l 124 |
45 - 61 = 77 M 93 ] 109 m 125 }
46 . 62 > 78 N 94 ^ 110 n 126 ∼
47 / 63 ? 79 O 95 _ 111 o 127 [delete]
3 (b) [1,5 ponto] No PCS, foi encontrado um OTP da estação Lincolnshire Poacher, contendo um único número:
7113894375. Este número representa uma mensagem criptografada usando a chave transmitida pela estação, de valor
02558. Para decodificá-la, basta considerar todos os números como BCD (8421) e somar a mensagem no OTP com
a chave que a estação transmitiu, repetindo-a para conter o mesmo número de dígitos, caso seja necessário (e.g. se a
mensagem criptografada no OTP fosse 1234567, deveria-se somá-la com 0255802, repetindo o 02 final para que a chave
tenha o mesmo número de dígitos da mensagem criptografada). O resultado da soma BCD deve então ser separado em
grupos de dois dígitos. Cada grupo de dois dígitos representa uma letra na tabela ASCII. Se você conseguir decifrar
a mensagem, encontrará o nome da associação à qual pertence o Vincenzo Piuri (que ministrou a aula 4, dia 15/03).
Atenção: Todo o procedimento deve ser realizado em BCD.
Para uso do professor: 0 1 1 2 5 10 15
y y
y +1/9/52+ y
Questão 4 [2,5 pontos]
4 (a) [1,0 ponto] Seja p = f(b2, b1, b0) a função “Paridade Ímpar” de uma palavra código de 3 bits, onde os
argumentos são b2 (bit mais significativo da palavra código), b1 e b0 (bit menos significativo). Construa a Tabela
Verdade da função p e apresente a sua expressão algébrica nos formatos da 1a. Forma Canônica (soma de mintermos)
e da 2a. Forma Canônica (produto de maxtermos). Explique como as expressões foram construídas.Para uso do professor: 0 1 1 2 5 10
y y
y +1/10/51+ y
4 (b) [1,0 ponto] Considere a função f(a, b, c, d) = (a + b.c + d).(a + c). Mostre algebricamente que f(a, b, c, d) =
(fD(a, b, c, d)), onde fD é a função dual de f . Justifique a sua resposta.
Para uso do professor: 0 1 1 2 5 10
4 (c) [0,5 pontos] Mostre algebricamente que f(x, y) = Πxy(0, 2, 3) = Σxy(1). Justifique a sua resposta.
Para uso do professor: 0 1 1 2 5
y y
[1.0	pontos]	Sejam	A	=	(204)N+1,			B	=	(102)N	,	C	=	(41)N	e	D	=	(2)N.	Sabendo-se	que	A	–	B	–	4C	+	4D
3	=	–4,	determine	
o	valor	de	N,	justificando	sua	resposta.	Dica:	converta	os	números	para	a	base	10,	em	função	de	N,	e	então	realize	
os	cálculos	para	determinar	N.		
	
Convertendo	para	a	base	10	
A	=	2(N+1)2	+	4		=	(2N2	+	4N	+	2)	+	4	=	2N2	+	4N	+	6	
B			 	 	 				=	1N2	+	0N	+	2	
4C	=	4(4N+1)	 	 				=										16N	+	4	
4D3		=	4(23)		 					 				=																					32	
è	A	–	B	–	4C	+	4D3	=	(2N2	–	N2)	+	(4N	–	0N	–	16N)	+	(6	–	2	–	4	+	32)	 =	–	4	
	 														=	N2	–	12N	+	36	 	 	 =	0	
	 														=	(N	–	6)2	 	 	 	 =	0	
è	N=	6		 	
	
[0.7	pontos]	Realize	as	conversões	de	base	indicadas,	considerando	números	positivos	apenas:	
	
a)	CA50116,	para	base	2.		
b)	4523210,	para	base	16	
c)	10100101,1012,	para	base	10.	
	
[0.2	pontos]	CA50116	=	(1100		1010	0101	0000	0001)2	
[0.2	pontos]	4524210	=	B0B016	
[0.3	pontos]	10100101,1012	=	165,62510	
	
	
[0.8	pontos]	Realize	as	seguintes	operações	com	números	inteiros	positivos,	nas	bases	indicadas:	
	
a)	BEBAD016	+	CA1D016	,	na	base	16.		
b)	25116		*	2716	,	na	base	16.	
c)	732018	–	340328,	na	base	8.	
d)	3310	/	610	,	na	base	2.	
	
a)	CB5CA016	
c)	5A5716	
b)	371478	
d)	1000012	/	1102	=	101,12	
	
Questão 2 (Valor Total 2,0) – 
 
2.1 – (0,5) Escreva as representações com 6 bits em Sinal e magnitude, 
Complemento de 1 e Complemento de 2 para cada um dos números 
decimais apresentados: 
 
 Binário (valor sem sinal) 
Sinal e 
magnitude 
Complemento 
de 1 
Complemento 
de 2 
+1 000001 000001 000001 000001 
-19 010011 110011 101100 101101 
+25 011001 011001 011001 011001 
-13 001101 101101 110010 110011 
 
2.2 – (0,5) Repita o exercício anterior com 8 bits. 
 
 Binário (valor sem sinal) 
Sinal e 
magnitude 
Complemento 
de 1 
Complemento 
de 2 
+1 00000001 00000001 00000001 00000001 
-19 00010011 10010011 11101100 11101101 
+25 00011001 00011001 00011001 00011001 
-13 00001101 10001101 11110010 11110011 
 
2.3 – (1,5) Responda às questões e realize as operações sobre os 
números de 8 bits indicando passo a passo o andamento, explicitando os 
“vai um”, “vem um”, etc. 
2.3.1 – (0,3) Qual o menor e o maior número que se pode representar, 
utilizando-se 8 bits? 
 
Compl de 1 - 127 < N < + 127 
Compl de 2 - 128 < N < + 127 
 
Para facilitar seu trabalho, sugerimos, primeiramente, escrever com 8 bits 
os números e seus complementos. 
 
 Binário (valor sem sinal) Complemento de 1 Complemento de 2 
+11 0000 1011 (-11) 1111 0100 (-11) 1111 0101 
+22 0001 0110 (-22) 1110 1001 (-22) 1110 1010 
+33 0010 0001 (-33) 1101 1110 (-33) 1101 1111 
+44 0010 1100 (-44) 1101 0011 (-44) 1101 0100 
+55 0011 0111 (-55) 1100 1000 (-55) 1100 1001 
 
2.3.2 - (0,3) (+22) + (+33) = +55 
 
 0 0 0 1 0 1 1 0 +22 
+ 0 0 1 0 0 0 0 1 +33 
 0 0 1 1 0 1 1 1 +55 
 
2.3.3 - (0,3) (+22) + (-33) = 
 1 1 1 1 
 0 0 0 1 0 1 1 0 +22 
+ 1 1 0 1 1 1 1 1 -33 
 1 1 1 1 0 1 0 1 -11 
 
2.3.4 - (0,3) (-33) + (-11) = 
 1 1 1 1 1 
 1 1 0 1 1 1 1 0 -33 
+ 1 1 1 1 0 1 0 0 -11 
1 1 1 0 1 0 0 1 0 
+ 1 
 1 1 0 1 0 0 1 1 -44 
 
 
2.3.5 - (0,3) (+44) + (-22) = 
 1 1 1 
 0 0 1 0 1 1 0 0 +44 
+ 1 1 1 0 1 0 0 1 -22 
1 0 0 0 1 0 1 0 1 
+ 1 
 0 0 0 1 0 1 1 0 +22 
 
 
 
y +1/7/54+ y
Questão 3 [2,5 pontos] Na época da guerra fria os espiões usavam OTPs (One Time
Pads) para criptografar informações. Os OTPs são cadernos, onde cada folha é um punhado
de números que parecem aleatórios, mas na verdade contêm uma mensagem criptografada
com uma chave. A chave para uma determinada folha de um OTP era transmitida por
estações de rádio conhecidas como NSs (Number Stations). As NSs eram estações de rádio
de ondas curtas e longo alcance, que podiam ser captadas por um rádio simples (de ondas
curtas, obviamente). Ao sintonizar uma delas, o que se ouve é uma voz sintetizada falando
números. A rádio conhecida como Lincolnshire Poacher transmitia números de cinco dígitos
em horários pré-determinados, como por exemplo: zero-dois-cinco-cinco-oito. Ninguém sabe
ao certo se este mecanismo ainda é utilizado, mas ainda hoje pode-se sintonizar várias NSs
ao redor do mundo.
3 (a) [1 ponto] É comum as NSs transmitirem usando repetição, para garantir que o espião recebeu a chave correta.
Se uma estação com repetição 3 fosse transmitir a palavra 0110 em binário, por exemplo, na verdade transmitiria
000111111000. Assumindo que o espião receba a palavra completa, mas que potencialmente haja erros nos seus
bits, este esquema de transmissão com repetição garante que o espião receberá o código corretamente? Justifique sua
resposta.
Para uso do professor: 0 1 1 2 5 10
y y
Não há código que garanta que o espião receba a palavra corretamente.
O código de repetição tem uma distância de hamming igual a repetição, por símbolo transmitido. 
Se a repetição for N, poderemos então aplicar a fórmula h=2c+d+1 com h=N.
Nesta questão, a distância (e a repetição) é 3, portanto poderia-se corrigir até um erro por 
símbolo ou detectar até dois erros por símbolo.
Critérios de correção:
[0,2] Explicar que não garante o recebimento incondicionalmente.
[0,2] Afirmar que a distância de hamming é 3.
[0,2] Afirmar que a distância aplica-se ao símbolo (e não a palavra toda).
[0,2] Afirmar que é possível corrigir até 1 erro por símbolo.
[0,2] Afirmar que é possível detectar até 2 erros por símbolo.
Observações: 
- É errado afirmar que o código tem distância 3 para a palavra transmitida, ou assumir 
capacidade de correção de 1 ou detecção de 2 para a palavra.
- É admissível chamar o símbolo de bit.
y +1/8/53+ y
Tabela 1: Tabela ASCII para caracteres imprimíveis.
Dec Char Dec Char Dec Char Dec Char Dec Char Dec Char
32 [espaço] 48 0 64 @ 80 P 96 ‘ 112 p
33 ! 49 1 65 A 81 Q 97 a 113 q
34 " 50 2 66 B 82 R 98 b 114 r
35 # 51 3 67 C 83 S 99 c 115 s
36 $ 52 4 68 D 84 T 100 d 116 t
37 % 53 5 69 E 85 U 101 e 117 u
38 & 54 6 70 F 86 V 102 f 118 v
39 ’ 55 7 71 G 87 W 103 g 119 w
40 ( 56 8 72 H 88 X 104 h 120 x
41 ) 57 9 73 I 89 Y 105 i 121 y
42 * 58 : 74 J 90 Z 106 j 122 z
43 + 59 ; 75 K 91 [ 107 k 123 {
44 , 60 < 76 L 92 \ 108 l 124 |
45 - 61 = 77 M 93 ] 109 m 125 }
46 . 62 > 78 N 94 ^ 110 n 126 ⇠
47 / 63 ? 79 O 95 _ 111 o 127 [delete]
3 (b) [1,5 ponto] No PCS, foi encontrado um OTP da estação Lincolnshire Poacher, contendo um único número:
7113894375. Este número representa uma mensagem criptografada usando a chave transmitida pela estação, de valor
02558. Para decodificá-la, basta considerar todos os números como BCD (8421) e somar a mensagem no OTP com
a chave que a estação transmitiu, repetindo-a para conter o mesmo número de dígitos, caso seja necessário (e.g. se a
mensagem criptografada no OTP fosse 1234567, deveria-se somá-la com 0255802, repetindo o 02 final para que a chave
tenha o mesmo número de dígitos da mensagem criptografada). O resultado da soma BCD deve então ser separado em
grupos de dois dígitos. Cada grupo de dois dígitos representa uma letra na tabela ASCII. Se você conseguir decifrar
a mensagem, encontrará o nome da associação à qual pertence o Vincenzo Piuri (que ministrou a aula 4, dia 15/03).
Atenção: Todo o procedimento deve ser realizado em BCD.
Para uso do professor: 0 1 1 2 5 10 15
y y
												1		1111																111		1110111	0001	0001	0011	1000	1001	0100	0011	0111	0101	+
0000	0010	0101	0101	1000	0000	0010	0101	0101	1000	(soma)
—————————————————————————————————————————————————
																																						1	1		1	1			
0111	0011	0110	1001	0000	1001	0110	1000	1100	1101	+
																				0110																0110	0110	(correção)
—————————————————————————————————————————————————
0111	0011	0110	1001	0110	1001	0110	1001	0011	0011
			7	3							6	9							6	9							6	9							3	3
73=I	69=E	33=!	Resposta:	IEEE!
Critérios de correção:
[0,3] Converter a palavra do OTP (7113894375) corretamente para BCD
[0,1] Posicionar a chave (02558) corretamente, já convertida em BCD
[0,3] Fazer a soma em BCD (incluindo vai-uns corretos)
[0,3] Fazer a correção da soma em BCD (2 dígitos menos significativos: 33)
[0,2] Fazer a correção da soma em BCD (5 dígito mais significativo: 6)
[0,3] Agrupar, converter para ASCII e responder: IEEE!
PUJt1S"" ~ 04- (~)/Pt 2\Jt:t 
~1A~ 
(8 T~ VN\~ ~ 
r 
b2- b~ h" p l 
0 0 0 ~ 1 
0 0 1 0 
0 t 0 0 
0 t ( 1 
( Q () 0 
{ 0 1 1 
.{ ~ 0 1 
1 ~ 1 0 
l 
r ~ I\~-b,b, ( o, :>, s,~) ~ 
= b~ r, b:- --t bl- b, b\) + bl-b~ b~ + b l bl b; 
2 ~ fJ}\~ ~/li\A'c.c.. 
p ":: 'll!:h b I ho ( 1, 2 I 4 I 1--) '=' 
( h,_ i- b, f 0"; ). ( b 2- + h-; + b~ ).(;;;: +b,-f h.) ( b-;: + b~ i- ~:-) 
@ t--:> (c..+ be+ d) (cA.-+ C) 
.fnco:,~,~,I) ~ 0- . (b--t'C) .J + 7 . c. 
t ( ~ 11, ' c, ~) ~ ( f v (~ ( b ! c \ J)) ~ 
~ ( 5'. ( b ~ ~) d -(- t: -c ) =-
';::' ( 0: c ~ --t [ ) .f) - ( 0:. c.) = 
= ( 0-. + ('" -t z) k <! ) . ( 0.. kc: ) -
= (o... -t b ~ -t- J.) . (tA.-+ (,) 
--~------~ 
- ----- --
@ ~ ('X-, ~) ?- '[ :>l+a ( 0 I 2.., ) I ~ 
~ c~+ tc, c ?C -~--~) c ~ i ~) = 
?- (;yr: + "- ~ + 1{_'2 + t) ~) ( ~-+ ~) ::0 
:::- W+ m-~- ~~ 1t -t ,Ycr(-t ~,-£ -t ~::: 
~ x. va + tJ u.. "':'. ..x= ~ -::: £ XlJ c t )