Ex.10. Projete um circuito que recebe um número de 6 bits e detecte (saída em nível alto) se esse número é primo. Implemente esse circuito usando o menor número possível de CIs.

Passo 1

O que o problema pede e quais informações temos.
  • Pedido: projetar um circuito combinacional que recebe um número de 6 bits e gera na saída nível alto (1) se e somente se esse número for primo.
  • Entradas: um vetor de 6 bits que representa um número inteiro no intervalo \{0,\dots,63\}. Vou chamar os bits de entrada de \,b_5,b_4,b_3,b_2,b_1,b_0\,, sendo (,b_5,$ o bit mais significativo.
  • Saída: um único bit (detector de primo), 1 quando o número representado pelas entradas for primo, 0 caso contrário.
  • Restrições/objetivo extra: usar o menor número possível de CIs (chips) para implementar a função.
Observação: nada mais foi fornecido (tipo de família lógica, disponibilidade de chips), então eu vou propor soluções práticas e explicar a que atinge o menor número de CIs.)

Passo 2

Lista exata dos números primos que interessam (primos \le 63). Vou listar explicitamente porque o circuito precisa reconhecer exatamente esses endereços.
O conjunto dos primos entre 0 e 63 é:
\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\}.
Portanto, para cada entrada que represente um desses valores a saída deve ser 1; para todos os outros valores entre 0 e 63 a saída deve ser 0. (Importante: 0 e 1 não são primos.)

Passo 3

Escolha do método — justificativa para minimizar número de CIs.
Opções óbvias:
  • Implementar por lógica pura (soma de produtos / portas) a função booleana que tem 18 minterms verdadeiros: isso gera uma expressão grande e exige muitas portas/decodificadores — portanto vários CIs.
  • Construir um circuito que testa divisibilidade por 2,3,5,7 (já que \sqrt{63}\approx7{,}9): teoricamente possível com unidades de módulo ou comparadores, mas também requer múltiplos blocos e, no fim, vários CIs.
  • Usar memória programável (ROM / PROM / EEPROM / EPROM) onde o endereço é o número de 6 bits e o dado armazenado naquele endereço é o bit “é primo?”. Essa abordagem é direta, fixa, muito simples de conectar e pode caber em apenas UM CI de memória (desde que o CI tenha pelo menos 64 palavras). Portanto é a solução com menor número de CIs na maioria dos cenários práticos.
Conclusão: a solução que minimiza CIs é usar um único CI de memória programável (ROM/PROM/EEPROM) ou um único CI programável lógico (PAL/GAL/CPLD) para implementar a tabela verdade de 64 entradas.

Passo 4

Explicando como funciona a solução com ROM (aula prática e passo-a-passo).
  1. Conceito: uma ROM (Read-Only Memory) tem linhas de endereço A_0,A_1,\dots e linhas de dados D_0,D_1,\dots. Quando se coloca um endereço nas linhas A, a ROM coloca na saída o valor previamente programado naquele endereço. Aqui queremos uma ROM com pelo menos 2^6=64 endereços. Em cada endereço n armazenamos um bit que indica primalidade: 1 se n é primo, 0 caso contrário.
  2. Necessidade de tamanho: precisa-se de 64 palavras. Pode-se usar qualquer memória com capacidade maior ou igual a 64 bytes/words. Exemplos típicos de CIs que servem (há muitos modelos; ver datasheet para detalhes): EPROM/EEROM da família 27Cxx (por exemplo 27C64), EEPROM 28Cxx, ou um pequeno CPLD/GAL. Em todos esses casos basta um só CI para esta função.
  3. Mapeamento lógico:
  • Ligações: entradas do circuito \,b_5\dots b_0 vão diretamente para os pinos de endereço \,A_5\dots A_0 da ROM (atenção à correspondência de ordem dos pinos conforme datasheet).
  • No endereço \,n (o número representado por \,b_5\dots b_0) armazena-se \,1 se n for primo e \,0 caso contrário.
  • A saída do ROM usada pode ser apenas um bit de dados (por exemplo D_0); os outros bits de dados podem ficar desprezados.
  • Sinais de controle do CI (chip enable / output enable / Vcc / GND) são conectados conforme datasheet; tipicamente CE ou /CS deve ser ativado (nível baixo para muitos chips) e OE ativado para permitir a saída. Se for EEPROM/EPROM, programar o conteúdo via gravador antes da montagem.
  • Se a família for TTL ou CMOS, pode ser necessário um resistor limitador e um buffer de saída para acionar LEDs/estágios seguintes. Mas isso não aumenta o número de CIs que contêm a lógica de detecção de primos: continua sendo um CI lógico.
  1. Tabela verdade necessária (vou escrever o valor da função P(n) para n=0 a 63, onde P(n)=1 se n é primo, caso contrário 0):
\begin{aligned} P(0)&=0,\; P(1)=0,\; P(2)=1,\; P(3)=1,\\\ P(4)&=0,\; P(5)=1,\; P(6)=0,\; P(7)=1,\\\ P(8)&=0,\; P(9)=0,\; P(10)=0,\; P(11)=1,\\\ P(12)&=0,\; P(13)=1,\; P(14)=0,\; P(15)=0,\\\ P(16)&=0,\; P(17)=1,\; P(18)=0,\; P(19)=1,\\\ P(20)&=0,\; P(21)=0,\; P(22)=0,\; P(23)=1,\\\ P(24)&=0,\; P(25)=0,\; P(26)=0,\; P(27)=0,\\\ P(28)&=0,\; P(29)=1,\; P(30)=0,\; P(31)=1,\\\ P(32)&=0,\; P(33)=0,\; P(34)=0,\; P(35)=0,\\\ P(36)&=0,\; P(37)=1,\; P(38)=0,\; P(39)=0,\\\ P(40)&=0,\; P(41)=1,\; P(42)=0,\; P(43)=1,\\\ P(44)&=0,\; P(45)=0,\; P(46)=0,\; P(47)=1,\\\ P(48)&=0,\; P(49)=0,\; P(50)=0,\; P(51)=0,\\\ P(52)&=0,\; P(53)=1,\; P(54)=0,\; P(55)=0,\\\ P(56)&=0,\; P(57)=0,\; P(58)=0,\; P(59)=1,\\\ P(60)&=0,\; P(61)=1,\; P(62)=0,\; P(63)=0. \end{aligned}
(Verificação rápida: os valores 1 ocorrem exatamente nos índices da lista de primos dada no Passo 2.)

Passo 5

Como programar/conectar na prática (detalhes de implementação física, passo-a-passo).
  1. Escolha do CI:
  • Pode ser qualquer memória programável com capacidade \ge 64 palavras. Exemplos práticos: um EPROM/EEPROM da família 27 C (ex.: 27C64 — que tem muito mais espaço que o necessário). Ou um dispositivo programável como GAL/CPLD (por exemplo um pequeno CPLD com uma única macro que implementa a tabela).
  • Em qualquer caso, só será necessário 1 CI para a lógica de decisão “é primo?”.
  1. Programação:
  • Para cada endereço n entre 0 e 63 grave o bit P(n) conforme a tabela do Passo 4.
  • Se o CI escolhido for byte-wide (por exemplo 8 bits por endereço), grave o bit de interesse em uma das posições de dados (por exemplo D_0) e deixe os outros bits a 0 (ou sem uso).
  1. Ligações:
  • Ligue \,b_0 ao pino A_0, …, \,b_5 ao pino A_5 (confirmar correspondência exata dos pinos no datasheet).
  • Ligue D_0 (ou outro bit de dados escolhido) à saída do seu circuito (por exemplo a entrada de um LED por resistor, ou a entrada de outro estágio lógico).
  • Conecte Vcc, GND e os sinais de enable (OE/CE) conforme datasheet. Se o chip usa /CE ativo baixo, assegure que esteja habilitado conforme o modo de operação (normalmente /CE=0 e /OE=0 para leitura).
  1. Teste:
  • Aplique combinações de b_5\dots b_0 correspondendo a cada número e verifique que a saída está alta exatamente nos números primos listados.

Passo 6

Alternativas e observações finais comparativas (para a prova — entenda por que escolhemos ROM).
  • Minimalidade: com a família adequada, a abordagem por ROM usa apenas 1 CI. É difícil (praticamente impossível, sem usar um CI programável) fazer a mesma função com menos de 1 CI porque precisa-se de algum circuito físico que realize a tabela (logo pelo menos um CI).
  • PAL/GAL/CPLD: também é uma opção de 1 CI — pode-se implementar a mesma tabela de verdade com uma única GAL16V8/GAL22V10 ou um pequeno CPLD. Vantagem: reprogramável e mais simples de gravar em laboratório; desvantagem: exige ferramental diferente.
  • Solução por portas/decodificadores: aumenta o número de CIs (muitos 74xx), portanto não é mínima.
  • Rápida dica para a prova: se o enunciado pede “menor número possível de CIs” sem restringir tipo, responda “um único CI (memória programada ou dispositivo lógico programável) implementando a tabela de verdade de 64 entradas” e explique o mapeamento endereço → flag primo (como fiz acima). Isso demonstra entendimento e é simples de justificar.

Resposta

Um CI: uma memória programável (ROM/EPROM/EEPROM) ou um CI programável (GAL/CPLD) único, por exemplo um EPROM tipo 27C64, com as 64 palavras programadas para produzir nível alto exatamente nos endereços \{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\}.

Exercícios relacionados