Projete um circuito verificador de paridade para a informação gerada pelo circuito do exercício anterior.

Passo 1

O que o enunciado pede:
  • Projetar um circuito verificador de paridade para a informação gerada pelo circuito do exercício anterior.
Informações relevantes dadas no enunciado:
  • Apenas foi dada a instrução acima (não foram enviados detalhes do circuito anterior).
Informações que faltam (necessárias para um projeto totalmente específico):
  • Quantos bits de dados são enviados (valor de n).
  • Se o bit de paridade é do tipo par (even) ou ímpar (odd).
  • Se o bit de paridade é anexado aos bits de dados como um único bit extra (caso típico) e em que posição.
  • Se o circuito precisa sinalizar “erro” (flag) ou “válido” (ack), e formatos de saída desejados.
  • Restrições tecnológicas (somente NAND/NOR disponíveis, limite de portas, requisitos de atraso).
Como esses dados não foram fornecidos, vou assumir o caso mais comum e dar um projeto genérico e parametrizável que cobre os dois tipos de paridade e qualquer número de bits n. Também dou um exemplo concreto para n=4 (caso muito frequente em exercícios).

Passo 2

Conceito básico de paridade (aula curta e prática).
  • Paridade é um bit extra P incorporado à mensagem de forma a detectar erros de transmissão simples.
  • Paridade par (even parity): o número total de bits ‘1’ na palavra de dados acrescido de P é par.
  • Paridade ímpar (odd parity): o número total de bits ‘1’ na palavra de dados acrescido de P é ímpar.
  • Operador lógico fundamental: XOR (ou exclusivo). Propriedade útil: o XOR de um conjunto de bits é 1 se o número de 1’s for ímpar; é 0 se o número de 1’s for par.
    • Se S = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1}, então S=1 <=> os dados têm um número ímpar de 1’s.
  • Assim a verificação de paridade é feita calculando o XOR de todos os bits recebidos (dados + bit de paridade) e inspecionando o resultado.

Passo 3

Definição das variáveis e do sinal de saída (explicando cada símbolo).
  • Seja D_0,D_1,\dots,D_{n-1} os bits de dados recebidos.
  • Seja P o bit de paridade recebido (gerado pelo transmissor).
  • Definir a soma XOR total
S = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1} \oplus P.
  • Interpretação de S:
    • Para paridade par: se S=0 a palavra está correta (nenhum bit com erro ímpar detectado); se S=1 foi detectado erro.
    • Para paridade ímpar: o transmissor garante que D_0\oplus\cdots\oplus D_{n-1}\oplus P = 1 quando não há erro. Logo, se S=1 então está correto; se S=0 detecta erro.
  • Portanto, sinais úteis a produzir:
    • sinal \mathrm{ERR} que indica erro detectado.
    • sinal \mathrm{OK} que indica palavra válida.
Relações lógicas:
  • Para paridade par:
\mathrm{ERR} = S = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1} \oplus P, \qquad \mathrm{OK} = \overline{\mathrm{ERR}}.
  • Para paridade ímpar:
\mathrm{OK} = S = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1} \oplus P, \qquad \mathrm{ERR} = \overline{\mathrm{OK}}.

Passo 4

Projeto lógico com portas XOR (etapas práticas para implementar na prova).
  • A implementação mais direta: construir uma “árvore XOR” que calcule S.
  • Método para construir a árvore XOR:
    1. Agrupar os bits em pares e aplicar XOR em cada par.
    2. Em seguida XOR dos resultados intermediários em etapas, até restar um único bit S.
    3. XOR final com P (ou incluir P já em uma das folhas).
  • Complexidade de portas:
    • Para n bits de dados + 1 bit P, o número de entradas a XORar é n+1.
    • Uma árvore balanceada usa aproximadamente \lceil n+1 - 1 \rceil = n portas XOR (mais precisamente, número de portas XOR = número de termos a combinar menos 1). Ex.: para 5 entradas são 4 XORs em árvore balanceada.
  • Exemplo de construção passo-a-passo para n=4 (caso concreto):
    • Calcular S_1 = D_0 \oplus D_1.
    • Calcular S_2 = D_2 \oplus D_3.
    • Calcular S = S_1 \oplus S_2 \oplus P. (pode-se fazer S_3=S_1\oplus S_2 e depois S=S_3\oplus P.)
    • Saída \mathrm{ERR} = S para paridade par, ou \mathrm{OK}=S para paridade ímpar.

Passo 5

Implementação quando só há portas NAND/NOR/AND/OR (transformações práticas).
  • Fórmula básica do XOR em termos de AND/OR/NOT:
A \oplus B = (A \land \overline{B}) \lor (\overline{A} \land B).
  • Para implementar com NAND apenas, usa-se a identidade: X \land Y = \overline{\overline{X \land Y}} e De Morgan. Uma implementação comum com NANDs:
    1. t_1 = A \text{ NAND } B.
    2. t_2 = A \text{ NAND } t_1.
    3. t_3 = B \text{ NAND } t_1.
    4. A \oplus B = t_2 \text{ NAND } t_3.
  • Para mais de dois termos, aplicar XOR em árvore usando a construção acima para cada XOR de par de sinais.
  • Observação prática: usar XOR nativo (se disponível no kit/FPGA) é mais simples e tem menor atraso.

Passo 6

Atenção a sincronização e atraso (coisa de prova / projeto prático).
  • Em circuitos reais, atenção ao atraso de propagação: uma árvore XOR profunda aumenta atraso. Para grandes n, balanceie a árvore XOR (XOR de pares, depois pares dos resultados, etc.) para minimizar profundidade.
  • Se P e os dados chegam em tempos diferentes, sincronize-os (por exemplo, registe os bits num clock antes da verificação) para evitar falsos alarmes.
  • Paridade detecta apenas número ímpar de bits errados; múltiplos erros pares passam despercebidos. Se exigir detecção maior, usar CRC ou códigos Hamming.

Passo 7

Exemplos numéricos rápidos para fixar (como treinar na prova).
  • Suponha n=4, dados D_3D_2D_1D_0 = 1011.
    • Calcule XOR dos dados: D_0\oplus D_1\oplus D_2\oplus D_3 = 1\oplus1\oplus0\oplus1.
    • 1\oplus1=0; 0\oplus0=0; 0\oplus1=1. Então XOR dos dados = 1.
    • Para paridade par, transmissor deve escolher P=1 de modo que 1\oplus P = 0. Se chegar P=1 e nenhum erro, S=0\Rightarrow \mathrm{ERR}=0.
    • Se um bit for invertido em trânsito e agora S=1, \mathrm{ERR}=1 indica erro detectado.
  • Treine montando a árvore XOR no papel para palavras de 3, 4 e 8 bits para ganhar rapidez em prova.

Passo 8

Resumo operacional pronto para implementar (o projeto que entregar na prova).
  • Entrega textual do projeto:
    • Entradas: D_0,\dots,D_{n-1},P.
    • Circuito: árvore XOR que computa S = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1} \oplus P.
    • Saídas:
      • para paridade par: \mathrm{ERR}=S e \mathrm{OK}=\overline{S}.
      • para paridade ímpar: \mathrm{OK}=S e \mathrm{ERR}=\overline{S}.
    • Implementação física: usar portas XOR em árvore; se só houver NAND, usar a implementação de XOR com NAND mostrada no Passo 5; balancear árvore para reduzir atraso; registrar sinais se necessário.
  • Esse projeto é parametrizável pelo número de bits n e pelo tipo de paridade.

Resposta

Para paridade par:
\mathrm{ERR} = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1} \oplus P,\qquad \mathrm{OK} = \overline{\mathrm{ERR}}.
Para paridade ímpar:
\mathrm{OK} = D_0 \oplus D_1 \oplus \cdots \oplus D_{n-1} \oplus P,\qquad \mathrm{ERR} = \overline{\mathrm{OK}}.

Exercícios relacionados