# Exercícios MT1 Questões de testes antigos de Fundamentos de Sistemas Computacionais, com resolução. Página: https://resumos.rgo.pt/cadeiras/fsc/exercicios-mt1/ ## Representação de dados Conversão de binário com parte fracionária Teste 1, 2023/24 O número binário $1110101{,}01_2$ está representado em que base e como? Solução Em hexadecimal, $1110101{,}01_2 = 75{,}4_{16}$. Agrupando os bits da parte inteira em nibbles, $0111,0101_2 = 75_{16}$. Na parte fracionária, $0{,}01_2 = 2^{-1}/2 = 0{,}25_{10}$, que em hexadecimal é o dígito $4$ na primeira casa ($4/16 = 0{,}25$). * **em octal por $165{,}1_8$.** A parte fracionária $0{,}01_2 = 0{,}25_{10} = 0{,}2_8$, não $0{,}1_8$. * **em octal por $165{,}4_8$.** A parte fracionária $0{,}01_2 = 0{,}2_8$, não $0{,}4_8$. * **em hexadecimal por $75{,}4_{16}$.** $1110101_2 = 75_{16}$ e $0{,}01_2 = 0{,}4_{16}$. * **em decimal por $117{,}125_{10}$.** O valor decimal é $117 + 0{,}25 = 117{,}25_{10}$. Interpretação de 8 bits em complemento para dois Teste 1, 2023/24 O número decimal representado por $10111010_2$ em 8 bits é quanto, consoante a interpretação? Solução Em complemento para dois com 8 bits, $10111010_2 = -70_{10}$. O bit mais significativo é 1, logo o número é negativo em complemento para dois. O módulo obtém-se invertendo os bits e somando 1: $01000101_2 + 1 = 01000110_2 = 64 + 4 + 2 = 70$. * **$58$, se interpretado sem sinal.** Sem sinal, $10111010_2 = 186_{10}$. * **$58$, se interpretado em sinal e grandeza.** Em sinal e grandeza, o bit de sinal é 1 e a grandeza é $0111010_2 = 58$, logo o valor é $-58$. * **$-70$, se interpretado em complemento para dois.** Complementando: $overline{10111010}_2 + 1 = 00000101_2 + 1 = 00000110_2 = 70$, com sinal negativo. * **$-186$, se interpretado em sinal e grandeza.** Em sinal e grandeza o valor é $-58$, não $-186$. Valor decimal de um número em vírgula fixa Q4.2 Teste 1, 2023/24 Considere o número binário $110101_2$ que denota um número em vírgula fixa no formato Q4.2. Qual é o valor decimal correspondente? Solução $-2{,}75$. No formato Q4.2, o número tem 6 bits no total: o bit de sinal, 3 bits inteiros e 2 bits fracionários. Como $110101_2$ em complemento para dois com 6 bits vale $53 - 64 = -11$, o valor em vírgula fixa é $-11 / 2^2 = -2{,}75$. Valor decimal de um número IEEE-754 em hexadecimal Teste 1, 2023/24 A representação hexadecimal de um número no formato IEEE-754 de precisão simples é $ exttt{C0700000}_{16}$. Qual é o valor decimal do número? Solução $-3{,}75$. Separando os campos: sinal $= 1$ (negativo), expoente $= 10000000_2 = 128$, logo expoente real $128 - 127 = 1$, e mantissa $= 1{,}111_2 = 1{,}875$. O valor é $-1{,}875 imes 2^1 = -3{,}75$. Soma em complemento para dois com 7 bits Teste 1, 2015/16 Considere os números $X = 1111001_2$ e $Y = 0100001_2$ com 7 bits. Assumindo que estão em complemento para dois, calcule $X + Y$. Solução $X + Y = 0011010_2$. Em complemento para dois, a soma faz-se como soma binária normal, ignorando o carry para fora do bit mais significativo: $1111001_2 + 0100001_2 = 1/0011010_2$, ou seja $0011010_2 = 26_{10}$. Em decimal, $X = -7$ e $Y = 33$. * **$0011010_2$.** $X = -7$ e $Y = 33$, logo $X + Y = 26 = 0011010_2$. * **$0011001_2$.** Esse valor corresponde a $25_{10}$, não a $26_{10}$. * **$10011101_2$.** A soma não produz transporte para fora do bit mais significativo que altere o sinal. * **$10011010_2$.** Esse valor seria negativo em complemento para dois, mas o resultado é positivo. Manipulação da representação IEEE-754 Teste 1, 2017/18 A representação do número $X$ no formato IEEE-754 de precisão simples, em hexadecimal, é $ exttt{427F0000}_{16}$. (a) Determine o valor de $X$ em decimal. (b) Determine a representação de $16 imes X$ por manipulação da representação binária de $X$. (c) Para o cálculo de $2^k imes X$, com $k$ inteiro maior que zero, determine o maior valor de $k$ para o qual o resultado ainda é representável em precisão simples sem overflow. Solução (a) $X = 63{,}75$. (b) $ exttt{447F0000}_{16}$. (c) $k = 122$. (a) A representação binária é $0100,0010,0111,1111,0000,0000,0000,0000$: sinal 0, expoente $10000100_2 = 132$ (real $132 - 127 = 5$) e mantissa $1{,}1111111_2$. Deslocando a vírgula 5 casas, obtém-se $111111{,}11_2 = 63{,}75$. (b) Multiplicar por $16 = 2^4$ aumenta o expoente em 4: expoente codificado $136 = 10001000_2$, ou seja $ exttt{447F0000}_{16}$. (c) O maior expoente codificado utilizável é 254 (255 é reservado), logo $k_{ ext{máx}} = 254 - 132 = 122$. Confere a tua resposta: * A resposta indica $X = 63{,}75$. * A resposta indica que $16 imes X$ se representa por $ exttt{447F0000}_{16}$. * A resposta indica que o maior valor de $k$ é 122. Soma em vírgula flutuante sem conversão para decimal Teste 1, 2020/21 Dois números $A$ e $B$ estão codificados no formato IEEE-754 de precisão simples, com representações hexadecimais $A = exttt{C3E2B000}_{16}$ e $B = exttt{C366A000}_{16}$. (a) Indique, justificando, o valor decimal de $B$. (b) Realize a operação $A + B$ sem conversão para decimal, indicando todos os passos. Solução (a) $B = -230{,}625$. (b) $A + B = exttt{C42B0000}_{16}$. (a) $B = 1,10000110,1100110101000000000000_2$: sinal 1, expoente $134$ (real $134 - 127 = 7$), mantissa $1{,}1100110101_2$. Assim, $B = -1{,}1100110101_2 imes 2^7 = -11100110{,}101_2 = -230{,}625$. (b) Ambos são negativos, logo o sinal do resultado é 1. Os expoentes reais são 8 (de $A$) e 7 (de $B$); alinhando a mantissa de $B$ uma casa para a direita e somando as mantissas de $A$ e $B$ obtém-se $10{,}1010110000_2$, que normalizado dá $1{,}0101011_2$ com expoente real 9. O resultado é $1,10001000,0101011000000000000000_2 = exttt{C42B0000}_{16}$. Confere a tua resposta: * A resposta indica $B = -230{,}625$. * A resposta indica que $A + B = exttt{C42B0000}_{16}$. Multiplicação de números binários sem sinal Teste 1, 2020/21 Sejam $A = 101{,}01_2$ e $B = 10{,}1_2$ dois números em binário sem sinal. O valor do produto $A imes B$ é: Solução $A imes B = 1101{,}001_2$. Em decimal, $A = 4 + 1 + 0{,}25 = 5{,}25$ e $B = 2 + 0{,}5 = 2{,}5$. O produto é $5{,}25 imes 2{,}5 = 13{,}125$. Convertendo: a parte inteira $13 = 1101_2$ e a parte fracionária $0{,}125 = 0{,}001_2$. * **$1100{,}001_2$.** Esse valor é $12{,}125_{10}$, não $13{,}125_{10}$. * **$1101{,}101_2$.** Esse valor é $13{,}625_{10}$, não $13{,}125_{10}$. * **$1011{,}001_2$.** Esse valor é $11{,}125_{10}$, não $13{,}125_{10}$. * **$1101{,}001_2$.** $A = 5{,}25_{10}$ e $B = 2{,}5_{10}$, logo $A imes B = 13{,}125_{10} = 1101{,}001_2$. ## Álgebra de Boole e circuitos combinatórios Conjunto de portas que não é funcionalmente completo Teste 1, 2023/24 Qual dos seguintes conjuntos de portas não pode ser usado para implementar todas as funções booleanas? Solução O conjunto ${ ext{AND2}, ext{OR2}}$ não implementa todas as funções booleanas. AND e OR são funções monótonas: trocar uma entrada de 0 para 1 nunca faz a saída passar de 1 para 0. A função NOT não é monótona, logo não pode ser realizada só com AND2 e OR2. Os restantes conjuntos incluem (direta ou derivados) uma porta de negação. * **${ ext{MUX 4:1}}$.** Um multiplexador 4:1 com as entradas adecuadas realiza qualquer função de 2 variáveis e, com constantes, também o NOT, sendo funcionalmente completo. * **${ ext{OR2}, ext{NOT}}$.** Com NOT e OR obtém-se AND por De Morgan, logo o conjunto é completo. * **${ ext{NAND2}}$.** Só com NAND2 se obtém NOT e AND, logo o conjunto é completo. * **${ ext{AND2}, ext{OR2}}$.** Sem porta de negação, nenhuma combinação de AND2 e OR2 produz a função NOT, pelo que o conjunto não é completo. Multiplexadores 2:1 necessários para um 8:1 Teste 1, 2023/24 Qual é o número mínimo de multiplexadores 2:1 necessários para construir um multiplexador 8:1? Solução 7 multiplexadores 2:1. Cada nível de multiplexadores 2:1 reduz o número de entradas a metade: são precisos 4 para passar de 8 a 4 entradas, mais 2 para passar de 4 a 2, e mais 1 na saída, num total de $4 + 2 + 1 = 7$. Função de maioria: tabela de verdade e forma canónica Teste 1, 2017/18 Um sistema crítico é composto por 3 componentes iguais do tipo C e um módulo M que apresenta na sua saída o valor obtido pela maioria das três entradas $X$, $Y$ e $Z$ (votador por maioria). (a) Apresente a tabela de verdade da função $F(X, Y, Z)$ do módulo M. (b) Indique a expressão simplificada de $F$ no formato de produto de somas, usando simplificação algébrica. (c) Mostre que a função também pode ser escrita como $F(X, Y, Z) = X cdot Y + Y cdot Z + X cdot Z$. Solução (a) $F = 1$ para $(0,1,1)$, $(1,0,1)$, $(1,1,0)$ e $(1,1,1)$, e $F = 0$ nos restantes casos. (b) $F(X, Y, Z) = (X + Y) cdot (Y + Z) cdot (X + Z)$. (c) $F(X, Y, Z) = X cdot Y + Y cdot Z + X cdot Z$. (a) A maioria de três bits é 1 quando há pelo menos dois uns. (b) A partir dos zeros da tabela, o produto de somas completo simplifica por distributividade e complemento para $(X + Y)(Y + Z)(X + Z)$. (c) A soma de produtos $X cdot Y + Y cdot Z + X cdot Z$ vale 1 quando algum par de entradas é $(1,1)$, ou seja, precisamente nos quatro casos em que há maioria de uns; as duas expressões são, portanto, equivalentes. Confere a tua resposta: * A tabela de verdade tem $F = 1$ apenas quando pelo menos duas entradas são 1. * A expressão em produto de somas simplificada é $(X + Y) cdot (Y + Z) cdot (X + Z)$. * A justificação mostra que $X cdot Y + Y cdot Z + X cdot Z$ vale 1 exatamente nos mesmos quatro casos. ## Circuitos sequenciais Registo de deslocamento que deteta o padrão 101 Teste 1, 2015/16 Considere um circuito com três flip-flops D em cascata, todos inicialmente a 0, em que a saída $Z$ é o AND lógico da entrada $X$ com as duas primeiras saídas dos flip-flops. Qual das sequências aplicadas à entrada $X$, em períodos sucessivos de relógio, faz com que a saída $Z$ fique exatamente duas vezes a 1? Solução A sequência $10101_2$. No ciclo $n$, as entradas do AND são $X_n$, $X_{n-1}$ e $X_{n-2}$, logo $Z = 1$ quando a janela de três bits é 101. Na sequência $10101$, isso acontece no 3.º e no 5.º ciclos, com saída $00101$. * **$11111_2$.** Só produz o padrão 101 uma vez (nas últimas três posições). * **$01101_2$.** Contém o padrão 101 apenas uma vez. * **$01010_2$.** Contém o padrão 101 apenas uma vez. * **$10101_2$.** Os últimos três bits são 101 nas posições 3 e 5, logo $Z = 1$ exatamente duas vezes (sequência de saída $00101$). Circuito sequencial com somador completo Teste 1, 2017/18 Considere um circuito sequencial síncrono com um somador completo (full adder) e dois flip-flops, todos inicialmente a 0. As entradas recebem um novo valor a cada ciclo: $X = 1, 0, 1, 0, 1$ e $Y = 0, 1, 1, 1, 0$ (tempo crescente). (a) Determine os valores sucessivos da saída $Z$ ao longo de cinco períodos de relógio e o valor final guardado no segundo flip-flop. (b) Explique a relação geral entre a sequência de saída e as sequências de entrada. Solução (a) $Z_0, Z_1, ldots, Z_5 = 0, 1, 1, 0, 0, 0$ e o valor final em FF2 é 1. (b) $Z_{i+1} = X_i oplus Y_i oplus C_i$, com $C_i$ o carry acumulado. O somador completo produz $S = X oplus Y oplus C_{in}$ e $C_{out}$ = maioria de $X$, $Y$, $C_{in}$; os flip-flops guardam $S$ e $C_{out}$ após cada flanco de relógio. Com $X = 1,0,1,0,1$ e $Y = 0,1,1,1,0$: ciclo 1 dá $S = 1$, $C = 0$; ciclo 2 dá $S = 1$, $C = 0$; ciclo 3 dá $S = 0$, $C = 1$; ciclo 4 dá $S = 0$, $C = 1$; ciclo 5 dá $S = 0$, $C = 1$. Logo $Z = 0,1,1,0,0,0$ e FF2 fica com o último carry, 1. Em geral, $Z_{i+1} = X_i oplus Y_i oplus C_i$, pelo que a sequência de saída é a soma lógica (bit a bit, mod 2) das sequências de entrada acumuladas. Confere a tua resposta: * A sequência de saída é $Z = 0, 1, 1, 0, 0, 0$ (incluindo o valor inicial $Z_0 = 0$). * O valor final do segundo flip-flop é 1. * A relação geral é $Z_{i+1} = X_i oplus Y_i oplus C_i$, ou seja, a saída é a soma (mod 2) das entradas acumuladas. Comparador ligado a um registo: deteção de máximos locais Teste 1, 2020/21 Um comparador de 8 bits (números sem sinal) tem a entrada $A$ ligada ao valor atual e a entrada $B$ à saída de um registo de 8 bits que guarda o valor do ciclo anterior. A saída $Z$ do comparador é 1 se $A > B$ e 0 caso contrário. O registo está inicialmente a 0. Determine o valor da saída $Z$ em cada um dos nove ciclos para a sequência de entrada $A = 12, 15, 17, 11, 6, 9, 21, 14, 25$. Solução $Z = 1, 1, 1, 0, 0, 1, 1, 0, 1$. Em cada ciclo, $B$ é o valor de $A$ no ciclo anterior (no primeiro ciclo, $B = 0$). Comparando: $12 > 0$, $15 > 12$, $17 > 15$, $11 gtr 17$, $6 gtr 11$, $9 > 6$, $21 > 9$, $14 gtr 21$, $25 > 14$. Logo a saída é $1, 1, 1, 0, 0, 1, 1, 0, 1$, ou seja, o circuito sinaliza os valores que são maiores que o antecessor. Confere a tua resposta: * A sequência de saída é $Z = 1, 1, 1, 0, 0, 1, 1, 0, 1$. * A justificação compara cada valor de $A$ com o valor anterior guardado no registo. ## Memórias e endereçamento Endereço da última posição de uma memória Teste 1, 2015/16 A primeira posição de uma memória de 1 KiB (8 bits por posição) tem o endereço $ exttt{0x0C00}$. Qual é o endereço da última posição? Solução O endereço da última posição é $ exttt{0x0FFF}$. Uma memória de 1 KiB tem $2^{10} = 1024$ posições, que ocupam 10 bits de endereço. O endereço inicial é $0000,1100,0000,0000_2$; o endereço final tem esses 10 bits menos significativos todos a 1, ou seja $0000,1111,1111,1111_2 = exttt{0x0FFF}$. * **$ exttt{0x0FFF}$.** A memória tem $2^{10}$ posições; o endereço final tem os 10 bits menos significativos a 1: $ exttt{0x0C00} + exttt{0x3FF} = exttt{0x0FFF}$. * **$ exttt{0xFC00}$.** Esse endereço não corresponde ao fim de um bloco de 1 KiB a partir de $ exttt{0x0C00}$. * **$ exttt{0xFFFF}$.** Só seria o caso se a memória começasse em $ exttt{0xFC00}$. * **$ exttt{0x0FFE}$.** Esse é o penúltimo endereço; faltam contar as 1024 posições. Capacidade de uma SRAM de 16 bits de endereço e dados Teste 1, 2020/21 Uma memória do tipo SRAM tem 16 bits de endereço e 16 bits de dados. Qual é a sua capacidade? Solução A capacidade é 128 KiB. Com 16 bits de endereço há $2^{16} = 65536$ posições. Como cada posição guarda 16 bits = 2 bytes, a capacidade total é $65536 imes 2, ext{bytes} = 131072, ext{bytes} = 128, ext{KiB}$. * **256 KiB.** Esse seria o valor com 8 bits de dados por posição. * **32 KiB.** Esse valor não corresponde a $2^{16}$ posições de 16 bits. * **64 KiB.** Esse seria o número de posições, não a capacidade em bytes. * **128 KiB.** A memória tem $2^{16}$ posições de 16 bits = 2 bytes, logo $65536 imes 2 = 131072$ bytes $= 128$ KiB. Mapa de endereços com descodificação total e parcial Teste 1, 2015/16 Um sistema de memória com 20 bits de endereço é composto por duas RAM: RAM1 usa descodificação total e o seu chip select é $CS_1 = overline{A_{19}} cdot overline{A_{18}}$; RAM2 tem 16 bits de endereço ligados a $A_{15:0}$ e o seu chip select é $CS_2 = A_{19} cdot overline{A_{17}}$. (a) Calcule a capacidade de RAM1 e a sua gama de endereços. (b) Determine as gamas de endereços a que RAM2 responde. (c) Pretende-se acrescentar um novo módulo: determine a capacidade máxima possível, a gama de endereços que deve ocupar e a expressão do seu chip select, justificando o tipo de descodificação a usar. Solução (a) RAM1: 256 KiB, de $ exttt{00000}_{16}$ a $ exttt{3FFFF}_{16}$. (b) RAM2: $ exttt{80000}_{16}$–$ exttt{9FFFF}_{16}$ e $ exttt{C0000}_{16}$–$ exttt{DFFFF}_{16}$ (quatro gamas de 64 KiB cada). (c) Máximo de 256 KiB em $ exttt{40000}_{16}$–$ exttt{7FFFF}_{16}$, com $CS = overline{A_{19}} cdot A_{18}$ e descodificação total. (a) Com descodificação total, os 18 bits $A_{17:0}$ endereçam a RAM1: $2^{18} imes 8, ext{bits} = 256$ KiB. O chip select é 1 quando $A_{19} = A_{18} = 0$, logo a gama é $ exttt{00000}_{16}$–$ exttt{3FFFF}_{16}$. (b) $CS_2 = 1$ quando $A_{19} = 1$ e $A_{17} = 0$; como $A_{18}$ e $A_{16}$ não entram no chip select, cada posição responde a 4 endereços, dando as gamas $ exttt{80000}$–$ exttt{9FFFF}$, $ exttt{A0000}$–$ exttt{BFFFF}$, $ exttt{C0000}$–$ exttt{DFFFF}$ e $ exttt{E0000}$–$ exttt{FFFF}$, cada uma de 64 KiB. (c) A maior gama livre é $ exttt{40000}_{16}$–$ exttt{7FFFF}_{16}$ (256 KiB). Para que cada posição só seja acedida por um único endereço é preciso descodificação total; com 18 bits de endereço e 2 bits de seleção, $CS = overline{A_{19}} cdot A_{18}$. Confere a tua resposta: * RAM1 tem 256 KiB e responde de $ exttt{00000}_{16}$ a $ exttt{3FFFF}_{16}$. * RAM2 responde às gamas $ exttt{80000}$–$ exttt{9FFFF}$, $ exttt{C0000}$–$ exttt{DFFFF}$ (descodificação parcial, 4 gamas de 64 KiB). * O novo módulo pode ter no máximo 256 KiB, na gama $ exttt{40000}$–$ exttt{7FFFF}$, com descodificação total e $CS = overline{A_{19}} cdot A_{18}$.