Exercise 1.48. Using the repetition code, you have a three-bit string that encodes a logical bit.
(a) If the parity of the left two bits is odd, and the parity of the right two bits is also odd, has a single-bit error occurred? If yes, which bit was flipped (the left, middle, or right bit)?
(b) If the parity of the left two bits is odd, but the parity of the right two bits is even, has a single-bit error occurred? If yes, which bit was flipped (the left, middle, or right bit)?
(c) If the probability of a single bit flipping is p=0.2, what is the probability that an uncorrectable error occurs with the 3-bit repetition code? In this case, does the 3-bit repetition code increase or decrease the probability of an uncorrectable error occurring?
(d) If the probability of a single bit flipping is p=0.7, what is the probability that an uncorrectable error occurs with the 3-bit repetition code? In this case, does the 3-bit repetition code increase or decrease the probability of an uncorrectable error occurring?

Passo 1

Vou deixar claro o que o exercício pede e quais informações temos.
  • Temos o código de repetição de 3 bits: cada bit lógico é codificado como três cópias iguais, por exemplo 000 ou 111.
  • O receptor verifica dois parities (paridades) de pares adjacentes:
    • paridade esquerda = paridade dos dois primeiros bits = bit1 \oplus bit2 (onde \oplus é XOR).
    • paridade direita = paridade dos dois últimos bits = bit2 \oplus bit3.
  • Perguntas:
    (a) Se a paridade esquerda é ímpar e a paridade direita também é ímpar, ocorreu um erro de um único bit? Se sim, qual bit (esquerdo, do meio ou direito) foi invertido?
    (b) Se a paridade esquerda é ímpar e a paridade direita é par, ocorreu um erro de um único bit? Se sim, qual bit foi invertido?
    (c) Se a probabilidade de um bit individual ser invertido é p=0,2, qual é a probabilidade de ocorrer um erro não corrigível com o código de 3 bits? Nesse caso, o código aumenta ou diminui a probabilidade de erro não corrigível?
    (d) Mesma pergunta de (c) para p=0,7.

Passo 2

Entendendo o que significa “paridade ímpar” de dois bits e como isso indica diferença entre bits.
  • Para dois bits a e b, a paridade “ímpar” (ou seja, a \oplus b = 1) significa que os dois bits são diferentes ( a\neq b). A paridade “par” ( a\oplus b = 0) significa que eles são iguais ( a=b).
  • No contexto de três bits (b_1,b_2,b_3), os dois cheques são:
    • paridade esquerda = b_1\oplus b_2.
    • paridade direita = b_2\oplus b_3.
  • Se um único bit foi invertido a partir de um código correto (ou seja, o código era 000 ou 111), o padrão dos bits será “uma diferente e duas iguais” — por exemplo 100, 010 ou 001.

Passo 3

Resolver (a): ambas paridades ímpares \Rightarrow qual bit foi invertido?
  • Se b_1\oplus b_2 = 1 e b_2\oplus b_3 = 1, então b_1\neq b_2 e b_2\neq b_3.
  • Com três bits, se b_1\neq b_2 e b_2\neq b_3, isso implica que b_1 = b_3 e que o bit do meio b_2 é diferente dos dois outros. Exemplos concretos (pegando-os de possíveis palavras recebidas):
    • 010: aqui b_1\oplus b_2 = 0\oplus1=1 e b_2\oplus b_3=1\oplus0=1.
    • 101: similarmente dá paridades ímpares.
  • Esses padrões correspondem exatamente ao caso em que o bit do meio foi invertido a partir de 000 ou 111.
  • Conclusão para (a): Sim, ocorreu um erro de um único bit e foi o bit do meio que foi invertido.

Passo 4

Resolver (b): paridade esquerda ímpar e paridade direita par \Rightarrow qual bit foi invertido?
  • Dados: b_1\oplus b_2 = 1 (logo b_1\neq b_2) e b_2\oplus b_3 = 0 (logo b_2=b_3).
  • Se b_2=b_3 e b_1\neq b_2, então b_1 é o bit diferente dos outros dois. Exemplo concreto: 100 tem b_1\oplus b_2 = 1 e b_2\oplus b_3 = 0.
  • Conclusão para (b): Sim, ocorreu um erro de um único bit e foi o bit da esquerda que foi invertido.
  • (Para referência: pelo mesmo raciocínio, se a paridade esquerda fosse par e a paridade direita ímpar, o bit invertido seria o da direita.)

Passo 5

Explicando como o código corrige e o que é um erro “incorrigível” (não corrigível) neste contexto.
  • O decodificador por maioria: ao receber três bits, decide o bit lógico como o valor que aparece em maioria entre b_1,b_2,b_3.
  • O código corrige todos os casos com exatamente um bit corrompido (pois a maioria ainda é o valor original).
  • Um erro não corrigível (isto é, que causa erro lógico após decodificação) acontece quando dois ou três bits são invertidos; nesses casos a maioria será o valor errado. Então devemos calcular a probabilidade de ocorrerem 2 ou 3 flips simultâneos.

Passo 6

Derivação da fórmula da probabilidade de erro não corrigível para o código de 3 bits.
  • Modelagem: cada bit é invertido independentemente com probabilidade p.
  • Probabilidade de exatamente k flips em 3 bits é \binom{3}{k} p^{k} (1-p)^{3-k}.
  • Probabilidade de erro não corrigível = probabilidade de k\ge 2:
P_{\text{incorr}} = \binom{3}{2} p^{2}(1-p) + \binom{3}{3} p^{3}.
  • Calculando os binomiais:
P_{\text{incorr}} = 3 p^{2}(1-p) + p^{3}.
  • Pode também ser simplificada:
P_{\text{incorr}} = 3p^{2} -2p^{3}.

Passo 7

Calcular (c) para p=0,2.
  • Usando a fórmula:
P_{\text{incorr}} = 3(0,2)^{2}(1-0,2) + (0,2)^{3}.
  • Calcule passo a passo:
    • (0,2)^{2} = 0,04.
    • 1-0,2 = 0,8.
    • 3\cdot 0,04 \cdot 0,8 = 3\cdot 0,032 = 0,096.
    • (0,2)^{3} = 0,008.
    • Soma: 0,096 + 0,008 = 0,104.
  • Comparação com o caso sem codificação: sem código, a probabilidade de erro lógico é simplesmente p=0,2.
  • Como 0,104 < 0,2, o código de repetição de 3 bits diminui a probabilidade de erro não corrigível quando p=0,2.

Passo 8

Calcular (d) para p=0,7.
  • Usando a fórmula:
P_{\text{incorr}} = 3(0,7)^{2}(1-0,7) + (0,7)^{3}.
  • Calcule passo a passo:
    • (0,7)^{2} = 0,49.
    • 1-0,7 = 0,3.
    • 3\cdot 0,49 \cdot 0,3 = 3\cdot 0,147 = 0,441.
    • (0,7)^{3} = 0,343.
    • Soma: 0,441 + 0,343 = 0,784.
  • Comparação com sem-código: p=0,7.
  • Como 0,784 > 0,7, o código de repetição de 3 bits aumenta a probabilidade de erro não corrigível quando p=0,7.

Passo 9

Observação geral (útil para a prova): condição de vantagem do código de 3 bits.
  • Pode-se mostrar analiticamente que o código ajuda (reduz a probabilidade de erro lógico) se, e somente se, p<0,5. Ou seja, o limiar é p=1/2.
  • Intuição: se cada bit tem mais chance de estar certo do que errado ( p<0,5), a votação por maioria melhora; se cada bit tem mais chance de estar errado ( p>0,5), a maioria tende a ser o valor errado e o código piora.

Resposta

(a) Sim — o bit do meio foi invertido.
(b) Sim — o bit da esquerda foi invertido.
(c) P_{\text{incorr}}=0,104. O código diminui a probabilidade de erro não corrigível ( 0,104<0,2).
(d) P_{\text{incorr}}=0,784. O código aumenta a probabilidade de erro não corrigível ( 0,784>0,7).

Exercícios relacionados