Exercícios MT1

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}$.

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$.

$-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$.

$-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$.

$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.

(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$.

(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}$.

$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$.

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.

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$.

(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.

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$).

(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.

$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.

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.

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.

(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}$.