Algumas questões de prova recentes com seus gabaritos
Q1 Uma das formas mais simples e mais usadas de detecção de erros na transmissão de dados
digitais são os códigos de paridade. Estes consistem em acrescentar um bit a uma seqüência de bits
que representam dados úteis, de forma a garantir que o total de bits transmitidos possua sempre um
número de 1´s que combine com a paridade escolhida. Por exemplo, caso se trabalhe com paridade
ímpar, o bit acrescentado a cada seqüência de dados deve ser tal que a quantidade total de bits
transmitidos (mensagem + bit de paridade) possua um número ímpar de 1´s.
Implemente um gerador de paridade ímpar em VHDL. A especificação é a seguinte: o módulo deve
receber a mensagem a transmitir de forma serial em um sinal IN de 1 bit. Um sinal de controle NEND
de 1 bit informa, quando em 0, que o valor na entrada IN é o derradeiro bit de informação útil a ser
transmitido. Uma das saídas do circuito é o sinal OUT, que apresenta, bit a bit, a mensagem a ser
transmitida, acrescida, no momento certo, do bit de paridade. Outra saída é um sinal ENDM, que
indica quando o último bit da mensagem, o bit de paridade está disponível na saída OUT.
Não se esqueça de, após receber o último bit e gerar a paridade, voltar ao estado inicial, onde se
espera nova mensagem. Comece mostrando a interface de entrada e saída do circuito sob a forma de
uma entity VHDL (0,5 pontos). A Figura abaixo mostra um comportamento válido do circuito,
supondo sensibilidade à borda de subida do relógio, sem mostrar o processo de inicialização do
circuito (diagrama começa com circuito no estado inicial, sinal de RESET não mostrado) e supondo
uma mensagem de 5 bits sendo enviada. Mostre, para sua implementação: (1) o diagrama de
transição de estados do sistema, indicando o estado inicial e a codificação de estados escolhida (1,5
pontos); (2) a implementação sob a forma de uma architecture em VHDL. Use os tipos
std_logic e std_logic_vector sempre que estes possam ser aplicados (2,5 pontos).
CK
Relógio
IN
Texto: 00110
NEND
Fim de texto
OUT
Msg c/ paridade: 001101
ENDM
Fim de mensagem
Solução (diagrama de transição sai dierto do VHDL):
--- Source code for the odd parity generator, by Ney Calazans
-library IEEE;
use IEEE.std_logic_1164.all;
entity odd_par_gen is
port (
reset: in STD_LOGIC;
clock: in STD_LOGIC;
inp: in STD_LOGIC;
nend: in STD_LOGIC;
outp: out STD_LOGIC;
endm: out STD_LOGIC);
end odd_par_gen;
architecture odd_par_gen of odd_par_gen is
type states is (par,impar,fpar,fimpar);
signal pr_st,nxt_st : states;
Entradas
signal outp_i, endm_i : std_logic; -- internal values generated
-- by the Mealy implementation
begin
process (clock,reset)
-- state register and output register
begin
if reset='1' then
pr_st <= par;
outp <= '0'; endm <= '0';
elsif clock'event and clock='1' then
pr_st <= nxt_st; outp <= outp_i; endm <= endm_i;
end if;
end process;
process (inp,nend,pr_st) -- next_state and outpur functions
variable inputs : std_logic_vector (1 downto 0);
begin
inputs := inp & nend;
case pr_st is
when par => outp_i <= inp; endm_i <= '0';
case inputs is
when "00" => nxt_st <= fpar;
when "01" => nxt_st <= par;
when "10" => nxt_st <= fimpar;
when "11" => nxt_st <= impar;
when others => null;
end case;
when impar => outp_i <= inp; endm_i <= '0';
case inputs is
when "00" => nxt_st <= fimpar;
when "01" => nxt_st <= impar;
when "10" => nxt_st <= fpar;
when "11" => nxt_st <= par;
when others => null;
end case;
when fpar => outp_i <= '1'; endm_i <= '1';
nxt_st <= par;
when fimpar => outp_i <= '0'; endm_i <= '1';
nxt_st <= par;
when others => null;
end case;
end process;
end odd_par_gen;
O testbench seria (não pedido na questão, reproduz exatamente a forma de onda da questão)
library ieee;
use ieee.std_logic_1164.all;
-- Add your library and packages declaration here ...
entity odd_par_gen_tb is
end odd_par_gen_tb;
architecture TB_ARCHITECTURE of odd_par_gen_tb is
-- Component declaration of the tested unit
component odd_par_gen
port(
reset : in std_logic;
clock : in std_logic;
inp : in std_logic;
nend : in std_logic;
outp : out std_logic;
endm : out std_logic );
end component;
-- Stimulus signals - signals mapped to the input and inout ports of tested entity
signal reset : std_logic;
signal clock : std_logic;
signal inp : std_logic;
signal nend : std_logic;
-- Observed signals - signals mapped to the output ports of tested entity
signal outp : std_logic;
signal endm : std_logic;
-- Add your code here ...
begin
-- Unit Under Test port map
UUT : odd_par_gen
port map
(reset => reset,
clock => clock,
inp => inp,
nend => nend,
outp => outp,
endm => endm );
reset <= '1', '0' after 5ns;
process
begin
clock <= '0', '1' after 10ns;
wait for 20ns;
end process;
inp <= '0', '1' after 35ns, '0' after 75ns, '1' after 95ns,
'0' after 105ns, '1' after 115ns;
nend <= '1', '0' after 85ns, '1' after 95ns;
end TB_ARCHITECTURE;
configuration TESTBENCH_FOR_odd_par_gen of odd_par_gen_tb is
for TB_ARCHITECTURE
for UUT : odd_par_gen
use entity work.odd_par_gen(odd_par_gen);
end for;
end for;
end TESTBENCH_FOR_odd_par_gen;
Q2 Implemente um programa que conte todas as ocorrências de um padrão arbitrário em
uma cadeia de caracteres. A cadeia é um vetor de caracteres ASCII armazenado a partir do
endereço de memória INS, e o término desta cadeia é identificado, como na linguagem C,
pelo caracter ASCII NULL (código 00H). O padrão é um outro vetor de caracteres, terminado
da mesma maneira que a cadeia onde se fará a pesquisa, e armazenado a partir da posição
de memória PAT. O resultado deve ser o número de vezes que PAT ocorre dentro de INS,
armazenado em uma posição de memória vezes.
Por exemplo, se INS contiver ABCDABGTHHHABTT (ou seja, 16 elementos, incluindo
o caracter NULL, não mostrado, que termina a cadeia), e se PAT for o padrão AB (com 2
elementos e terminado por NULL, também não mostrado), o resultado em vezes
(posição de memória) ao final da execução deverá ser 3. [3,5 pontos]
Pede-se:
a) Descreva o algoritmo usando palavras ou um fluxograma [1 ponto].
b) Implemente o programa na linguagem de montagem do processador Cleópatra. Não se
esqueça de mostrar, além do programa, uma área de dados válida a ser usada na
execução. [2,5 pontos].
Solução:
;
;
CONTADOR DE OCORRENCIAS EM STRINGS – resultado = 4
;
.code
LOOP:
L1:
LDA
NOT
ADD
ADD
JZ
INS,I
#01
PATTMP,I
IGUAIS,R
;
verifica se ins[i]==pat[j]
LDA PAT
STA PATTMP
;
equivalente à j=0 (resseta o ponteiro)
LDA
NOT
ADD
ADD
JZ
; verifica NOVAMENTE, pois podia estar
; em curso de comparação e interrompeu (HARD!)
INS,I
#01
PATTMP,I
IGUAIS,R
LDA INS,I
JZ FIM
LDA
ADD
STA
JMP
INS
#01
INS
LOOP,R
IGUAIS:
LDA
ADD
STA
LDA
JZ
JMP
PATTMP
#01
PATTMP
PATTMP,I
INCREM
L1,R
INCREM:
LDA VEZES
ADD #01
STA VEZES
; encontrou null na string
; incrementa indice da string principal
LDA PAT
STA PATTMP
JMP L1,R
FIM:
;
equivalente à j=0 (resseta o ponteiro)
HLT
.endcode
.data
vezes:
INS:
PAT:
PATTMP:
V1:
V2:
.enddata
db
db
db
db
db
db
db
#00
V1
V2
V2
#65h,#34h,#34h,#11h,#27h,#44h,#022h,#02h,#34h,#11h
#0FFH,#0FFH,#0FFH,#0FFH,#34h,#11h,#34h,#11h,#00
#34h,#11h,#00H
Q3 Repita a implementação do programa da Questão 1 para o processador R11. Atente para
o fato de que a memória de dados da R11 é formada de palavras de 16 bits. Para facilitar a
implementação do programa, considere que os dados de todos os vetores estão
desempacotados, isto é, que cada caracter ocupa uma palavra de memória, estando o
caracter em questão no byte inferior, a posição superior sempre contendo 00H. [2,5 pontos]
Pede-se:
a) Implemente o programa na linguagem de montagem do processador R11. Não se
esqueça de mostrar, além do programa, uma área de dados válida a ser usada na
execução.
b) Qual o tamanho do seu programa em bytes?
Solução:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ARQUITETURA R11 - detecção de strings repetidos
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.code
LOOP:
XOR
XOR
XOR
XOR
R0,
R1,
R2,
R3,
R0,
R1,
R2,
R3,
R0
R1
R2
R3
;
;
;
;
R0=0
R1 - variável i
R2 - variável j
R3 – vezes temporario
LDLI
LDHI
LDLI
LDHI
R4
R4,
R5
R5,
LD
LD
R6, R4, R1
R7, R5, R2
;
;
INS[I]
PAT[J]
COMP
STMSK
JPMI
R6, R7
#20H
#IGUAIS
;
;
z (n/n'/z/z'/c/c'/z/z')
INS[I] == PAT[J]?
XOR
R2, R2, R2
;
zera variável j
LD
COMP
STMSK
JPMI
R7, R5, R2
R6, R7
#20H
#IGUAIS
;
PAT[J]
;
segundo teste, agora com 'j' zerado
#INS
#INS
#PAT
#PAT
L1:
IGUAIS:
FIM:
COMP
STMSK
JPMI
R6, R0
#20H
#FIM
;
;
INS[I] == null ?
z (n/n'/z/z'/c/c'/z/z')
ADDI
R1,#01H
;
i++
STMSK
JPMI
#0FFH
#LOOP
ADDI
R2,#01H
;
j++
LD
COMP
STMSK
JPMI
R7, R5, R2
R7, R0
#10H
#L1
;
PAT[J]
;
;
z' (n/n'/z/z'/c/c'/z/z')
PAT[J] != null ?
ADDI
XOR
STMSK
JPMI
R3, #01H
R2, R2, R2
#0FFH
#L1
;
;
incrementa vezes
zera variável j
LDLI
LDHI
ST
HALT
R5
R5,
R5,
#VEZES
#VEZES
R3
; GRAVA VEZES
.endcode
; area de dados
.data
vezes:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
db #0000H
INS: db #AA03H, #0012H, #0012H, #0034H, #BB18H, #0012H, #0034H, #CC35H, #DD0ABH,
#EE0CDH, #FF77H, #8153H, #0012H, #0034H, #0012H, #0034H, #5645H, #0000H
PAT: db
#0012H, #0034H, #0000H
.enddata
Q4 Um determinado circuito receptor de dados contém a seguinte interface externa: os sinais
linha, init, clock e ready são fios (1 bit cada). O barramento saída contém 8 bits. A operação
do circuito ocorre conforme descrito abaixo [4 pontos]:
•
linha
Quando não há dados a serem transmitidos, a entrada linha
está com valor constante ‘1’. O circuito RX fica monitorando
linha até que ocorra uma descida para valor lógico ‘0’. Assuma que
init
linha está sincronizada com o clock, e que suas transições
ocorrem na borda de subida do mesmo.
saída
RX
ready
•
clock
Esta primeira descida de linha não é utilizada na palavra que
queremos receber. Na segunda borda de descida do clock, após a descida da linha,
armazena-se o bit 0 da palavra de saída. Procede-se assim até a nona descida do clock,
onde é armazenado o bit 7 de saída.
•
Na décima descida do clock, após a descida da linha, gera-se o sinal ready, o qual indica
existência de dado disponível.
a) Implemente a descrição do circuito em VHDL [2,5 pontos].
b) Complete o diagrama de tempos correspondente ao test_bench abaixo para 210 ns [1,5
pontos].
library ieee;
use ieee.STD_LOGIC_UNSIGNED.all;
use ieee.std_logic_1164.all;
entity serial_tb is
end serial_tb;
architecture TB_ARCHITECTURE of serial_tb is
component serial
port( clock : in std_logic;
init : in std_logic;
linha : in std_logic;
saida : out std_logic_vector(7 downto 0);
ready : out std_logic );
end component;
signal ready, clock, init, linha : std_logic;
signal saida : std_logic_vector(7 downto 0);
type mem_rom is array (0 to 4) of std_logic_vector(7 downto 0);
constant byte : mem_rom := ( x"4E", x"73", x"FF", x"C9", x"5C" );
begin
UUT : serial port map (clock => clock, init => init, linha => linha, saida => saida, ready => ready );
init <= '1', '0' after 4 ns;
process
begin clock<='1', '0' after 5ns;
wait for 10ns;
end process;
process
variable cont : integer := 0;
begin
linha <= '1';
wait for 30 ns;
linha <= '0';
wait for 10 ns;
f1: for cc in 0 to 7 loop
linha <= byte(cont)(cc);
wait for 10 ns;
end loop f1;
cont := cont + 1;
if cont=5 then cont:=0; end if;
end process;
end TB_ARCHITECTURE;
0
10
20
30
40
50
60
70
80
90
100
110
120
Init
clock
linha
saída
ready
Solução:
library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
entity serial is
port (
clock, init, linha : in std_logic;
saida: out std_logic_vector(7 downto 0);
ready: out std_logic
);
end serial;
architecture beh of serial is
130
140
150
160
170
180
190
200
210
type type_state is (S0,S1,S2,S3,S4,S5,S6,S7,S8,S9);
signal EA,PE : Type_STATE;
signal byte_rx: std_logic_vector(7 downto 0);
begin
saida <= byte_rx;
process(clock,init)
--- REGISTRADOR ÚNICO PARA ESTADO/REG SAÍDA
begin
if init='1' then
EA <= S0;
byte_rx <= (others => '0');
elsif clock'event and clock='0' then
EA <= PE;
if EA/=S0 and EA/=S9 then
byte_rx <= linha & byte_rx(7 downto 1);
end if;
end if;
end process;
process(EA, linha)
begin
case EA is
when S0 => ready <= '0';
if linha = '0' then PE <= S1; -- detect a start bit
end if;
when S1 => PE <= S2;
when S2 => PE <= S3;
when S3 => PE <= S4;
when S4 => PE <= S5;
when S5 => PE <= S6;
when S6 => PE <= S7;
when S7 => PE <= S8;
when S8 => PE <= S9;
when S9 => PE <= S0; ready <= '1';
end case;
end process;
end beh;