Detecção e Correção de Erros

•
UFABC

Douglas De Gennaro
24/11/2021
E aí, curtiu este material?
Ajude a incentivar outros estudantes a melhorar o conteúdo
Gostou desse material? Compartilhe! 🧡
Natureza da Informação

96 Materiais compartilhados
Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
Prévia do material em texto
BC-0504: Natureza da 
Informação
 
8: Detecção e correção de erros
Slides cedidos pela Profa. Mirtha Lina
Detecção e Correção de Erros
Introdução
Re-lembrando
I Dados carregam muita redundância, e.g. estima-se que a
redundância do inglês é ≈ 50%, i.e. em sequências longas ≈
metade dos śımbolos não são necessários.
Aocdcrnig to a rseecrah at Cmabrigde Uinervtisy, it
dseno’t mttaer in waht oderr the lterets in a wrod are,
the olny irpoamtnt tihng is taht the frsit and lsat ltteer
be in the rhgit pclae. The rset can be a taotl mses and
you can sitll raed it whoutit a pboerlm. Tihs is bucseae
the huamn mnid deos not raed ervey ltteer by istlef, but
the wrod as a wlohe.
https://www.cs.utexas.edu/~eberlein/cs337/errorDetection3.pdf
https://www.cs.utexas.edu/~eberlein/cs337/errorDetection3.pdf
Detecção e Correção de Erros
Introdução
Re-lembrando
I Dados carregam muita redundância, e.g. estima-se que a
redundância do inglês é ≈ 50%, i.e. em sequências longas ≈
metade dos śımbolos não são necessários.
F.rth.rm.re, .s w. .lre.dy k..w, w. .r. a.so abl. t. re.d t.is
m.s..g. ev.n tho... sev.r.l l.t..rs .r. m.s..ng!
I Técnicas de codificação e compressão diminuem a redundância
da fonte =⇒ menos bits carregam a mesma informação =⇒
certos bits têm peso ou importância muito maior
I Porém ter um pouco de redundância é bom pois evita erros
re.d =⇒ r..d =⇒ read, road?
t.is =⇒ t..s =⇒ this, thus, toss?
Detecção e Correção de Erros
Introdução
Erros?
I Canal ideal sem ruido
I Canais com ruido (ar, cabo, fibra ótica, satélite, telefone,
barramentos de computador) podem introduzir mudanças de
śımbolos
Detecção e Correção de Erros
Introdução
Erros?
I Canal ideal sem ruido
I Canais com ruido (ar, cabo, fibra ótica, satélite, telefone,
barramentos de computador) podem introduzir mudanças de
śımbolos e perdas
Detecção e Correção de Erros
Introdução
Erros
Linha de transmissão com ruido, fenômenos meteorológicos na
transmissão sem fio, quedas de energia, riscos em CD e DVD, etc
O que fazer com os erros?
I Ignorar o erro (nem sempre é posśıvel ou desejável, programas
executáveis, imagens médicas)
I Eco: transmissão à origem de reflexos dos dados recebidos
(aumenta o tráfego no canal)
I Detectar e solicitar a retransmissão (nem sempre é garantia de
recepção sem novos erros)
I Detectar e corrigir os erros de forma automática com uma
probabilidade de erro muito pequena (Shanon provou que
teoricamente é posśıvel, ótimos resultados na prática)
Detecção e Correção de Erros
Introdução
Erros
Linha de transmissão com ruido, fenômenos meteorológicos na
transmissão sem fio, quedas de energia, riscos em CD e DVD, etc
Como saber que ocorreu um erro? Acrescentar redundância
Detecção e Correção de Erros
Introdução
Detecção e Correção de Erros - Idéia
Se a maioria das sequências de bits não se corresponde com
mensagens válidas, o erro vai converter uma mensagem válida
numa sequência inválida. Se as sequências válidas estão
suficientemente separadas e cada sequência inválida se está
mais próxima de exatamente uma das mensagens válidas sv, o
decodificador pode substituir se por sv, corrigindo o erro.
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming∗
Como saber se duas sequências estão próximas?
∗ Hamming, Richard W., Error detecting and error correcting codes, Bell System Technical Journal 29 (2), 1950
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming∗
Como saber se duas sequências estão próximas?
Dadas duas sequências de bits X e Y de igual comprimento
dH(X,Y)= número de 1 em X⊕ Y
Em outras palavras, é o número de bits diferentes que há em
ambas sequências.
Exemplo: dH(01010101, 11111101) = #1(01010101⊕ 11111101)
= #1(10101000) = 3
∗ Hamming, Richard W., Error detecting and error correcting codes, Bell System Technical Journal 29 (2), 1950
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming
I O número de erros na transmissão de um bloco é a distância
de Hamming entre a palavra enviada e a recebida.
I Se um código deve detectar sd erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser sd + 1. Isto garante que qualquer erro de até sd será
detectado, erros maiores podem ser detectados ou não.
I Se um código deve corrigir sc erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser 2sc + 1.
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming
I O número de erros na transmissão de um bloco é a distância
de Hamming entre a palavra enviada e a recebida.
I Se um código deve detectar sd erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser sd + 1. Isto garante que qualquer erro de até sd será
detectado, erros maiores podem ser detectados ou não.
I Se um código deve corrigir sc erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser 2sc + 1.
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming
I O número de erros na transmissão de um bloco é a distância
de Hamming entre a palavra enviada e a recebida.
I Se um código deve detectar sd erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser sd + 1. Isto garante que qualquer erro de até sd será
detectado, erros maiores podem ser detectados ou não.
I Se um código deve corrigir sc erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser 2sc + 1.
Exemplo: Qual é a distância de Hamming ḿınima do código
{00000, 01011, 10101, 11110}
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming
I O número de erros na transmissão de um bloco é a distância
de Hamming entre a palavra enviada e a recebida.
I Se um código deve detectar sd erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser sd + 1. Isto garante que qualquer erro de até sd será
detectado, erros maiores podem ser detectados ou não.
I Se um código deve corrigir sc erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser 2sc + 1 =⇒ correção é mais dif́ıcil que detecção
I Um código de detecção/correção é escrito como C(n, k,dmin)
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming
I O número de erros na transmissão de um bloco é a distância
de Hamming entre a palavra enviada e a recebida.
I Se um código deve detectar sd erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser sd + 1. Isto garante que qualquer erro de até sd será
detectado, erros maiores podem ser detectados ou não.
I Se um código deve corrigir sc erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser 2sc + 1 =⇒ correção é mais dif́ıcil que detecção
I Um código de detecção/correção é escrito como C(n, k,dmin)
Detecção e Correção de Erros
Distância de Hamming
Distância de Hamming
I O número de erros na transmissão de um bloco é a distância
de Hamming entre a palavra enviada e a recebida.
I Se um código deve detectar sd erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser sd + 1. Isto garante que qualquer erro de até sd será
detectado, erros maiores podem ser detectados ou não.
I Se um código deve corrigir sc erros, então a distância de
Hamming ḿınima entre as palavras de códigos válidas deve
ser 2sc + 1 =⇒ correção é mais dif́ıcil que detecção
I Um código de detecção/correção é escrito como C(n, k,dmin)
Exemplo: Qual é a capacidade de detecção ou correção de
um código C(n, k,d)? Detecção d− 1 e correção bd−12 c
Detecção e Correção deErros
Técnicas básicas de Detecção e Correção de Erros
Método da Redundância
Para proteger 1 bit é preciso de mais 1 bit
para detecção ou mais 2 bits para correção
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Redundância
Dupla e Tripla redundância
I Dupla redundância: Repete cada bit 1 vez; detecta 1 erro
I Tripla redundância: Repete cada bit 2 vezes; detecta até 2
erros ou∗ corrige 1 erro.
MIT course - Digital Communication Systems
∗ O ou é exclusivo e.g. 0 7−→ 000 =⇒canal 101 7−→ 1.
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/index.htm
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Como proteger vários bits somente
com mais um bit de redundância?
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Paridade Simple - ASCII
I C(k + 1, k, 2), i.e. k bit de dados, 1 bit de redundância,
dmin = 2. O bit de redundância, chamado bit de paridade, é
escolhido para o número de bits de bloco seja par
I O bit de paridade é calculado usando o ⊕ de todos os bits de
dados (soma modulo 2)
I Permite detectar um erro (em geral um número ı́mpar de
erros); porém não pode corrigir nenhum erro.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Paridade Simple - ASCII
I C(k + 1, k, 2), i.e. k bit de dados, 1 bit de redundância,
dmin = 2. O bit de redundância, chamado bit de paridade, é
escolhido para o número de bits de bloco seja par
I O bit de paridade é calculado usando o ⊕ de todos os bits de
dados (soma modulo 2)
Exemplo: Dados a transmitir 0110010, 1100000;
I Permite detectar um erro (em geral um número ı́mpar de
erros); porém não pode corrigir nenhum erro.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Paridade Simple - ASCII
I C(k + 1, k, 2), i.e. k bit de dados, 1 bit de redundância,
dmin = 2. O bit de redundância, chamado bit de paridade, é
escolhido para o número de bits de bloco seja par
I O bit de paridade é calculado usando o ⊕ de todos os bits de
dados (soma modulo 2)
Exemplo: Dados a transmitir 0110010, 1100000;
I Permite detectar um erro (em geral um número ı́mpar de
erros); porém não pode corrigir nenhum erro.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Paridade Simple - ASCII
I C(k + 1, k, 2), i.e. k bit de dados, 1 bit de redundância,
dmin = 2. O bit de redundância, chamado bit de paridade, é
escolhido para o número de bits de bloco seja par
I O bit de paridade é calculado usando o ⊕ de todos os bits de
dados (soma modulo 2)
Exemplo: Dados a transmitir 0110010, 1100000;
I Permite detectar um erro (em geral um número ı́mpar de
erros); porém não pode corrigir nenhum erro.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Paridade Simple - ASCII
I C(k + 1, k, 2), i.e. k bit de dados, 1 bit de redundância,
dmin = 2. O bit de redundância, chamado bit de paridade, é
escolhido para o número de bits de bloco seja par
I O bit de paridade é calculado usando o ⊕ de todos os bits de
dados (soma modulo 2)
I Permite detectar um erro (em geral um número ı́mpar de
erros); porém não pode corrigir nenhum erro.
Exemplo: Dados recebidos 0110110 1 1101100 0;
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Paridade Simple - ASCII
I C(k + 1, k, 2), i.e. k bit de dados, 1 bit de redundância,
dmin = 2. O bit de redundância, chamado bit de paridade, é
escolhido para o número de bits de bloco seja par
I O bit de paridade é calculado usando o ⊕ de todos os bits de
dados (soma modulo 2)
I Permite detectar um erro (em geral um número ı́mpar de
erros); porém não pode corrigir nenhum erro.
Exemplo: Dados recebidos 0110110 1 1101100 0;
Bloco transmitido
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade Simple
Paridade Simple - ASCII
I C(k + 1, k, 2), i.e. k bit de dados, 1 bit de redundância,
dmin = 2. O bit de redundância, chamado bit de paridade, é
escolhido para o número de bits de bloco seja par
Exemplo: Bloco transmitido
I O bit de paridade é calculado usando o ⊕ de todos os bits de
dados (soma modulo 2)
I Permite detectar um erro (em geral um número ı́mpar de
erros); porém não pode corrigir nenhum erro.
I A paridade pode ser par ou ı́mpar (mas do mesmo tipo para
todo bloco) e pode estar no final ou qualquer outra posição
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Paridade de Bloco - Codificação
I m blocos de k bits são organizados numa matriz (m ∗ k)
I O bit de paridade de cada linha é calculado e anexado à linha
antes de ser transmitida. A paridade de cada coluna também
é calculada =⇒ C(m ∗ k + m + k,m ∗ k, 3)
I Além disso, pode ser acrescentado um bit de paridade de toda
a matriz =⇒ C(m ∗ k + m + k + 1,m ∗ k, 4)
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Paridade de Bloco - Codificação
I m blocos de k bits são organizados numa matriz (m ∗ k)
I O bit de paridade de cada linha é calculado e anexado à linha
antes de ser transmitida. A paridade de cada coluna também
é calculada =⇒ C(m ∗ k + m + k,m ∗ k, 3)
I Além disso, pode ser acrescentado um bit de paridade de toda
a matriz =⇒ C(m ∗ k + m + k + 1,m ∗ k, 4)
Exemplo: Blocos a serem transmitidos: 1100, 1011, 0101
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Paridade de Bloco - Codificação
I m blocos de k bits são organizados numa matriz (m ∗ k)
I O bit de paridade de cada linha é calculado e anexado à linha
antes de ser transmitida. A paridade de cada coluna também
é calculada =⇒ C(m ∗ k + m + k,m ∗ k, 3)
I Além disso, pode ser acrescentado um bit de paridade de toda
a matriz =⇒ C(m ∗ k + m + k + 1,m ∗ k, 4)
Exemplo: Blocos a serem transmitidos: 1100, 1011, 0101
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Paridade de Bloco - Decodificação
1- Se não há erro ou há num único bit paridade errado (fila ou
coluna), os dados estão ok
2- Se a paridade da fila x e a coluna y estão erradas, então o bit
na posição (x, y) está errado e é corrigido
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Paridade de Bloco - Decodificação
1- Se não há erro ou há num único bit paridade errado (fila ou
coluna), os dados estão ok
2- Se a paridade da fila x e a coluna y estão erradas, então o bit
na posição (x, y) está errado e é corrigido
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Paridade de Bloco - Decodificação
3- Outros erros de paridade são detectados mas não podem
ser corrigidos
I Não há garantia de detectar mais de 3 erros
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Paridade de Bloco - Decodificação
3- Outros erros de paridade são detectados mas não podem
ser corrigidos
I Não há garantia de detectar mais de 3 erros
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Mágica e Paridade de Bloco
http://katieirenec.blogspot.com.br/2013/03/computer-science-outreach-magic.html
http://katieirenec.blogspot.com.br/2013/03/computer-science-outreach-magic.htmlDetecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Mágica e Paridade de Bloco
http://katieirenec.blogspot.com.br/2013/03/computer-science-outreach-magic.html
http://katieirenec.blogspot.com.br/2013/03/computer-science-outreach-magic.html
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Método da Paridade de Bloco
Mágica e Paridade de Bloco
http://katieirenec.blogspot.com.br/2013/03/computer-science-outreach-magic.html
http://katieirenec.blogspot.com.br/2013/03/computer-science-outreach-magic.html
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
É posśıvel corrigir um erro somente com 3 bits?
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3)
I Corrige um erro com um número ḿınimo de bits de paridade.
Cada bit de paridade, cobre um subconjunto dos bits de dados
MIT course - Digital Communication Systems
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/index.htm
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3)
I Os bits do código são organizados convenientemente e
numerados de esquerda à direita começando em 1
MIT course - Digital Communication Systems
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/index.htm
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Codificação
I Os bits do código são organizados convenientemente e
numerados de esquerda à direita começando em 1
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Codificação
I Usualmente, as posições numeradas com potências de 2 são
reservadas para os bits de paridade
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Codificação
I Usualmente, as posições numeradas com potências de 2 são
reservadas para os bits de paridade
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Codificação
I O código a transmitir é o resultado do cálculo dos bits de
paridade para cada conjunto de bits de dados
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Decodificação
I Deve verificar a paridade de cada bit de paridade e seus bits de
dados. Se todo resultado é 0∗, assume-se que não houve erro.
∗ Assumindo paridade par. No caso de paridade ı́mpar, todas as verificações devem ser 1.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Decodificação
I Deve verificar a paridade de cada bit de paridade e seus bits de
dados. Se todo resultado é 0∗, assume-se que não houve erro.
∗ Assumindo paridade par. No caso de paridade ı́mpar, todas as verificações devem ser 1.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Decodificação
I Se houve só 1 erro ele pode ser detectado e corrigido. Os bits
de paridade, segundo seu peso, indicam a posição do erro.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Decodificação
I Se houve só 1 erro ele pode ser detectado e corrigido. Os bits
de paridade, segundo seu peso, indicam a posição do erro.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Decodificação
I 2 erros também são detectados porém, não podem ser
corrigidos.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Decodificação
I 2 erros também são detectados porém, não podem ser
corrigidos.
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Código de Hamming (7,4,3) - Decodificação
I 2 erros também são detectados porém, não podem ser
corrigidos. No há garantia de detectar mais de 2 erros
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Quantos bits precisa um Código de Hamming (n, k, 3)?
I Com k bits de dados, o código terá n− k = p bits de
paridade. Isto da para representar 2p inteiros
I Para corrigir 1 erro, os bits de paridade devem representar
1. Caso 1: No houve erro (1 possibilidade)
2. Case 2: Exatamente um dos bits do código tem um erro
(n = k + p possibilidades ou posições)
I Por isso são necessários n + 1 ≤ 2p ⇐⇒ k + p ≤ 2p − 1
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Quantos bits precisa um Código de Hamming (n, k, 3)?
I Com k bits de dados, o código terá n− k = p bits de
paridade. Isto da para representar 2p inteiros
I Para corrigir 1 erro, os bits de paridade devem representar
1. Caso 1: No houve erro (1 possibilidade)
2. Case 2: Exatamente um dos bits do código tem um erro
(n = k + p possibilidades ou posições)
I Por isso são necessários n + 1 ≤ 2p ⇐⇒ k + p ≤ 2p − 1
Exemplo: Quantos bits de paridade são necessários para corrigir 1
erro em 6 bits de dados usando código de Hamming?
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Quantos bits precisa um Código de Hamming (n, k, 3)?
I Com k bits de dados, o código terá n− k = p bits de
paridade. Isto da para representar 2p inteiros
I Para corrigir 1 erro, os bits de paridade devem representar
1. Caso 1: No houve erro (1 possibilidade)
2. Case 2: Exatamente um dos bits do código tem um erro
(n = k + p possibilidades ou posições)
I Por isso são necessários n + 1 ≤ 2p ⇐⇒ k + p ≤ 2p − 1
Exemplo: Quantos bits de paridade são necessários para corrigir 1
erro em 6 bits de dados usando código de Hamming?
k + p = 6 + 3 = 9 > 7 = 23 − 1 =⇒ Nāo
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Quantos bits precisa um Código de Hamming (n, k, 3)?
I Com k bits de dados, o código terá n− k = p bits de
paridade. Isto da para representar 2p inteiros
I Para corrigir 1 erro, os bits de paridade devem representar
1. Caso 1: No houve erro (1 possibilidade)
2. Case 2: Exatamente um dos bits do código tem um erro
(n = k + p possibilidades ou posições)
I Por isso são necessários n + 1 ≤ 2p ⇐⇒ k + p ≤ 2p − 1
Exemplo: Quantos bits de paridade são necessários para corrigir 1
erro em 6 bits de dados usando código de Hamming?
k + p = 6 + 3 = 9 > 7 = 23 − 1 =⇒ Nāo
k + p = 6 + 4 = 10 ≤ 15 = 24 − 1 =⇒ OK
Detecção e Correção de Erros
Técnicas básicas de Detecção e Correção de Erros
Código de Hamming
Códigos de Hamming Perfeitos
Detectam 2 erros ou∗ corrigem 1 erro com o número ḿınimo de
bits de paridade
I (3,1,3) ⇒ 2 bits de paridade (Tripla Redundância)
I (7,4,3) ⇒ 3 bits de paridade,
I (15,11,3) ⇒ 4 bits de paridade,
I (31,26,3) ⇒ 5 bits de paridade,
I (63,57,3) ⇒ 6 bits de paridade, ...
I (2p − 1, 2p − 1− p, 3) ⇒ p bits de paridade
Acrescentando mais um bit de paridade total, o código de
Hamming corrige um único erro e detecta até 2 erros
(http://courses.cs.vt.edu/cs2506/Spring2009/Notes/Lecture7.pdf)∗ O ou é exclusivo.
http://courses.cs.vt.edu/cs2506/Spring2009/Notes/Lecture7.pdf
Detecção e Correção de Erros
Exerćıcios
Exerćıcios
1. Se deja proteger a sequência de bits 011010 usando código
de Hamming. Que palavra de código deve ser transmitida?
Resposta: 0100110110
2. Uma sequência de oito bits na fonte foi protegida usando
código de Hamming. No receptor foi recebida a sequência
101100010010. Assumindo que o canal introduziu no
máximo um erro, determine qual foi a sequência de bits
enviada?
Resposta: 11000010
Detecção e Correção de Erros
Exerćıcios
Exerćıcios
1. Se deja proteger a sequência de bits 011010 usando código
de Hamming. Que palavra de código deve ser transmitida?
Resposta: 0100110110
2. Uma sequência de oito bits na fonte foi protegida usando
código de Hamming. No receptor foi recebida a sequência
101100010010. Assumindo que o canal introduziu no
máximo um erro, determine qual foi a sequência de bits
enviada?
Resposta: 11000010
Detecção e Correção de Erros
Exerćıcios
Exerćıcios
1. Se deja proteger a sequência de bits 011010 usando código
de Hamming. Que palavra de código deve ser transmitida?
Resposta: 0100110110
2. Uma sequência de oito bits na fonte foi protegida usando
código de Hamming. No receptor foi recebida a sequência
101100010010. Assumindo que o canal introduziu no
máximo um erro, determine qual foi a sequência de bits
enviada? Resposta: 11000010
Detecção e Correção de Erros
Exerćıcios
Exerćıcios
3. Na sáıda dum canal foi recebida a sequência binária
correspondente aos seguintes números hexadecimais. Sabendo que
foi usada paridade de bloco (tamanho do bloco de dados = 2),
sem acrescentar o bit de paridade de toda a matriz, determine se
houve ou não erro na transmissão. Pode ser obtida a informação
original? Caso afirmativo, escreva a sequência binária dela, senão
justifique de forma apropriada porque não é posśıvel.
a) A9
b) 1F
c) 28
Detecção e Correção de Erros
Exerćıcios
Exerćıcios
3. Na sáıda dum canal foi recebida a sequência binária
correspondente aos seguintes números hexadecimais. Sabendo que
foi usada paridade de bloco (tamanho do bloco de dados = 2),
sem acrescentar o bit de paridade de toda a matriz, determine se
houve ou não erro na transmissão. Pode ser obtida a informação
original? Caso afirmativo, escreva a sequência binária dela, senão
justifique de forma apropriada porque não é posśıvel.
a) A9
b) 1F
c) 28
Exerćıcios Independentes:
Floyd, pag 117, Seção 2-12, pag 124, Exerćıcios 61-64
Detecção e Correção de Erros
Exerćıcios
Exerćıcios
4. A sequência hexadecimal 5D6F deve ser transmitida em forma
binária. Se deseja protegê-la usando paridade de bloco (tamanho
do bloco de dados = 4), sem acrescentar o bit de paridade de toda
a matriz. Escreva em hexadecimal a sequência que deve ser
transmitida (assumindo a matriz é transmitida por linha)
Resposta: 56D9E1
Detecção e Correção de Erros
Exerćıcios
Exerćıcios
4. A sequência hexadecimal 5D6F deve ser transmitida em forma
binária. Se deseja protegê-la usando paridade de bloco (tamanho
do bloco de dados = 4), sem acrescentar o bit de paridade de toda
a matriz. Escreva em hexadecimal a sequência que deve ser
transmitida (assumindo a matriz é transmitida por linha)
Resposta: 56D9E1