Conteúdo principal
Curso: Computer science theory > Unidade 3
Lição 2: Teoria da informação moderna- Taxa de símbolos
- Introdução à capacidade de canal
- Exploração do espaço de uma mensagem
- Medição de informações
- Origem das correntes de Markov
- Exploração da cadeia de Markov
- Teoria matemática da comunicação
- Exploração do texto de Markov
- Entropia da informação
- Códigos de compressão
- Correção de erro
- A busca por inteligência extraterrestre
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
Correção de erro
Como podemos nos comunicar na presença de ruído? Versão original criada por Brit Cruise.
Quer participar da conversa?
Nenhuma postagem por enquanto.
Transcrição de vídeo
RKA4JL - Alice e Bob descobriram um truque incrível. Eles estão trocando mensagens através de um fio rígido ou mole para transmitir "zeros" ou "uns". No entanto, devido às rajadas de vento, falsos "zeros" ou "uns" podem ocorrer durante a transmissão, o que resulta em erros. Mas eles já descobriram uma maneira de se comunicar livre de erros, mesmo na presença de ruído. Como puderam fazer isso? Na década de 1940, Richard Hamming
enfrentou um problema semelhante enquanto trabalhava nos laboratórios Bell. "Nos laboratórios de telefonia Bell fazíamos cerca de 10% das experiências em um computador e cerca de 90% no laboratório. Espero que com o tempo façamos
90% no computador e 10% no laboratório. Velocidade, custo e esforço favorecem o computador mais do que os métodos de laboratório". Na época, os computadores usavam informações armazenadas em cartões perfurados que representam "um" e "zero", com furo e sem furo. Esse sistema era sujeito a erros porque era comum os cartões estarem dobrados ou mal perfurados em alguns lugares. Então, os furos poderiam ser dispensados ou os sem furos poderiam ser acidentalmente perfurados, causando bits trocados. Esses erros poderiam causar
a parada de todo o sistema até que o local do erro pudesse ser
encontrado e corrigido manualmente. Hamming encarregou-se de elaborar um método que pode detectar e corrigir automaticamente erros de bits individuais, sem interromper os cálculos. Sua solução tinha raízes na ideia intuitiva de repetição, algo que todos nós fazemos
quando confrontamos a interferência ou a possibilidade de que parte
da nossa mensagem seja corrompida. Seus códigos de correção de erros foram construídos no simples conceito de um bit de paridade. Um bit de paridade é um único bit
que é adicionado ao fim de uma mensagem e indica os números de "um"
na mensagem, se ele é par ou ímpar. Se um único erro ocorre,
o destinatário poderia então detectá-lo, porque o bit de paridade já não é correspondente. No entanto, para detectar e corrigir
erros individuais corretos, Hamming precisava adicionar mais bits de paridade para identificar o local do erro. Isso leva ao seu código "Hamming 7 por 4", o que acrescenta três bits de paridade
para cada bloco de quatro bits de dados. Primeiro, vamos começar com três bits de paridade, que podem ser representados por círculos. Esses círculos se cruzam para produzir quatro regiões. Os quatro bits de dados são colocados dentro dessas regiões em uma ordem específica. E para calcular o bit de paridade,
olhamos para cada círculo, um de cada vez, cada um contendo três bits de dados. Nós determinamos o bit de paridade como antes: some os bits de dados e, se conseguirmos zero ou dois, o bit de paridade ainda é zero. E se conseguimos um ou três,
o bit de paridade é um, que é ímpar. Fazemos isso por todos os meios e acabamos com três bits de paridade para
coincidir com os quatro bits de dados. Esses são, então, colocados em
uma sequência padrão, como se segue. Perceba que o sistema pode corrigir automaticamente erros individuais com uma regra simples: Se um único erro ocorre, dois ou mais bits de paridade serão incorretos. E onde eles se cruzam é o local do erro. Esse bit de dados de intersecção, então,
foi trocado automaticamente, de modo que todos os bits de paridade
são válidos novamente. E esse é o truque de Alice e Bob. Os bits de paridade adicionais são conhecidos como bits redundantes, porque eles não carregam qualquer nova informação. Todos os códigos e correção de erros
trabalham dessa forma. Todos eles aumentam ligeiramente
o tamanho da mensagem à custa da correção automática de erros. Nós também usamos os códigos de correção de erros para armazenamento, por exemplo, em um CD. A informação é codificada usando códigos especiais para corrigir pedaços de erros causados por arranhões ou poeira que corrompem longas sequências de "zeros" e "uns" armazenados na superfície. E é exatamente por isso que você pode riscar um CD e muitas vezes ele ainda vai funcionar perfeitamente. Claude Shannon usou essa ideia de redundância para redefinir a capacidade de um canal de comunicação. Como o ruído em seu canal aumenta, então deve-se aumentar a quantidade de redundância para se comunicar livre de erros e isso deve, então, diminuir a quantidade eficaz de informação que você pode enviar por unidade de tempo.