Considere um código linear de bloco, cuja matriz geradora é dada por
G=[lllllll 1 & 0 & 0 & 0 & 1 & 1 & 0 0 & 1 & 0 & 0 & 1 & 0 & 1 0 & 0 & 1 & 0 & 0 & 1 & 1 0 & 0 & 0 & 1 & 1 & 1 & 1 ]
Para este código, determine:
(a) O tamanho dos blocos de bits de informação (mensagem) na entrada no codificador;
(b) O tamanho das palavras-código geradas e a quantidade de bits de paridade adicionados;
© As palavras-código associadas a cada mensagem e a distância mínima;
(d) O número de erros que pode ser detectados e o número de erros que pode ser corrigido;
(e) A mensagem estimada, supondo que o sinal recebido foi lllll0 & 0 & 0 & 1 & 1;
(f) A probabilidade de erro não detectado Pu(e) (isto é, probabilidade do código não detectar que houve erros durante a transmissão), supondo que as palavras-código são transmitidas através de um BSC. Calcule, então, Pu(e) para uma probabilidade de erro de 10^-2 no BSC.

Passo 1

Beleza, vamos lá. A gente tem um código linear de bloco definido pela matriz geradora
G = 1 & 0 & 0 & 0 & 1 & 1 & 0 0 & 1 & 0 & 0 & 1 & 0 & 1 0 & 0 & 1 & 0 & 0 & 1 & 1 0 & 0 & 0 & 1 & 1 & 1 & 1
Isso é matéria de códigos lineares: dados , a gente sabe que o tamanho da mensagem é número de linhas, o comprimento do código é número de colunas, e a gente vai usar operações em (soma módulo 2).

Passo 2

(a) Quantos bits entram no codificador? Como tem 4 linhas, .
(b) Quantos bits saem? tem 7 colunas, então . Os bits de paridade são .

Passo 3

© Cada palavra-código dmin = 3 sai fazendo módulo 2, onde é uma mensagem de 4 bits. Listando todas as 16 combinações:
u  | c=uG
0000 | 0000000
0001 | 0001111
0010 | 0010011
0011 | 0011100
0100 | 0100101
0101 | 0101010
0110 | 0110110
0111 | 0111001
1000 | 1000110
1001 | 1001001
1010 | 1010101
1011 | 1011010
1100 | 1100011
1101 | 1101000
1110 | 1110000
1111 | 1111111
Para achar a distância mínima , basta ver o peso (número de 1’s) da palavra-código não nula de menor peso. Dá para ver que o mínimo é 3 (por exemplo, tem três uns). Então

Passo 4

(d) Num código de distância :
  • Detecta até erros.
  • Corrige até erro.

Passo 5

(e) Para decodificar um vetor recebido H = l[-P^T mid I3r], , a gente monta a matriz de verificação de paridade
P = 1&1&01&0&10&1&11&1&1 Longrightarrow H = 1&1&0&1&1&0&0 1&0&1&1&0&1&0 0&1&1&1&0&0&1
onde s = H,r^T pmod2 . No nosso caso
Aí você calcula a síndrome
  • Se , não detectou erro.
  • Se , olha em qual coluna de ela aparece, esse índice é o bit que foi invertido. Corrige e pega os 4 primeiros bits como mensagem estimada.

Passo 6

(f) A probabilidade de erro não detectado num BSC de probabilidade Pu(e) ;=;sumw=dmin^n Aw,p^w,(1-p)^,n-w, é
A0=1,;A3=7,;A4=7,;A7=1
onde Pu(e) =7,p^3(1-p)^4;+;7,p^4(1-p)^3;+;p^7 é o número de palavras-código de peso Pu(e)approx 7cdot10^-6,(0,99)^4 +7cdot10^-8,(0,99)^3 +10^-14 approx6,8times10^-6 . No nosso (7,4,3) Hamming a distribuição é
Logo
Para :

Resposta

(a) Pu(e)=7p^3(1-p)^4+7p^4(1-p)^3+p^7, .
(b) , com 3 bits de paridade.
© Listamos as 16 palavras-código acima; .
(d) Detecta até 2 erros, corrige até 1 erro.
(e) Decodifica pela síndrome ; corrige o bit cujo índice é a coluna de que bate com ; mensagem estimada são os 4 primeiros bits do código corrigido.
(f)
para , .

Exercícios relacionados