Organização e Arquitetura de Computadores Ijoseana/OAC_NA08Adic.pdferros dependem fundamentalmente da sua distância de Hamming. Exemplo: As palavras de código 10001001 e 10110001

DSC/CEEI/UFCG

Universidade Federal de Campina Grande

Departamento de Sistemas e Computação

Curso de Bacharelado em Ciência da Computação

Circuitos Lógicos Combinacionais

(Adicional)

Profa Joseana Macêdo Fechine Régis de Araújo

[email protected]

Carga Horária: 60 horas

Organização e Arquitetura de Computadores I

DSC/CEEI/UFCGUFCG/CEEI/DSC/OACI – Joseana Macêdo Fechine Régis de Araújo 2

Tópicos

Organização Básica de Computadores

Códigos de Detecção/Correção de Erros



Problema:

Dados podem, ocasionalmente, conter erros causados por

oscilação de tensão, por exemplo.

Bits extras são acrescidos à informação, com a

finalidade de detecção de erros em caso de

ocorrência de uma ou mais inversões de bits.

Se a saída não corresponder a uma das codewords

(palavras-código), acontece uma indicação de erro.

As codewords são um subconjunto de todas as possíveis

combinações do código.




Solução:

Dados são armazenados com um código que permita a

detecção ou correção de erros.

São acrescentados bits extras nas palavras de memória

usados para verificar a exatidão da informação.

Uma palavra de código de n (=m+r) bits conterá: m bits de

dados + r bits de redundância (ou verificação).







Distância de Hamming - igual ao número de bits correspondentes que diferem em duas palavras de código quaisquer.

As propriedades de detecção de erros e de correção de erros dependem fundamentalmente da sua distância de Hamming.

Exemplo: As palavras de código 10001001 e 10110001 distam 3 unidades de Hamming.

Observação: É necessário que ocorram 3 erros (inversões) nos bits em destaque da palavra 2 para que ela se transforme na palavra 1.




Exemplo:

Detecção de d erros distância de Hamming = d+1

Correção de d erros distância de Hamming = 2d+1

(mesmo em presença de d erros, a palavra de código

original pode ser recomposta por meio dos bits

redundantes)



Código de Paridade

Código de Paridade Par: é um código formado pela adição de

um bit de controle a informação original, de forma a produzir

uma codeword com um número par de 1, ou seja:

Código de Paridade Ímpar: é um código formado pela adição

de um bit de controle a informação original, de forma a produzir

uma codeword com um número ímpar de 1, ou seja:



Código de Paridade



Código de Paridade – Código de Detecção de Erros

Exemplo Simples:

Inclusão de 1 bit de paridade (0 - par e 1 - ímpar) aos bits de dados da palavra de código.

A ocorrência de 1 único erro produz palavra de código errada (Distância de Hamming=2, são necessários 2 erros para transformar uma palavra de código válida em outra palavra de código válida).

Erro só é detectado, e não corrigido. Programa cancela o processamento para não gerar resultados errados.



Exemplo de Código de Correção de Erros

Exemplo: Código com somente quatro palavras-código válidas:

0000000000 0000011111 1111100000 1111111111

Distância de Hamming = 5 (correção de dois erros)

Exemplo de palavra de código recebida pelo receptor:

0000000111 (incorreta)

Palavra correta: 0000011111 (ocorrência de no

máximo dois erros)



Exemplo: Código de Hamming

Considere o código com 4 palavras (codewords)

A = 0000000000

B = 0000011111

C = 1111100000

D = 1111111111

d=5 => detecta todos os erros de 4 bits corrige

todos os erros de 2 bits




Corrige todos os erros de 1 bit em cada palavra

(codeword)

posições dos bits corretores: 20, 21, 22.... 2n

conteúdo dos bits corretores: soma (XOR) do peso de

cada bit da codeword que se encontrar com 1.

Exemplo de codificação:

Mensagem: 10001101 (8 bits)

Codeword: 1000x110x1xx (12 bits)

Bits com 1: 12, 7, 6, 3

Código de correção:

Codeword a transmitir: 100011101110




Transmissão: 100011101110

Recepção: 100011101110

Verificação é feita pela soma (XOR) do peso de cada

bit da codeword que se encontrar em 1:

Resultado zero: deduz que não houve erros na

transmissão.




Transmissão: 100011101110

Recepção: 100011001110

Verificação é feita pela soma (XOR) do peso de cada

bit da codeword que se encontrar em 1:

Resultado diferente de zero: indica a posição onde

ocorreu erro.



Exercício: Código de Hamming

Considere que foi recebida a palavra:

a) 100011100111

Esta palavra está correta? Em caso negativo, qual o

bit a ser corrigido?


Código de Hamming pouco eficiente para comunicações em que os erros ocorrem por

rajada.

Documents

Organização e Arquitetura de Computadores Ijoseana/OAC_NA08Adic.pdferros dependem fundamentalmente da sua distância de Hamming. Exemplo: As palavras de código 10001001 e 10110001