SEC (Single Error Correction)
Código de Hamming
Arquitetura de
Computadores
SEC (Single Error Correction)






Código de Hamming
Problema
Solução
Custos
Geração de Dados
Conclusões
Código de Hamming





Simples Correção de Erro (SEC)
Expansível : Dupla Detecção de Erro (SECDED)
Garantia maior de consistência dos dados
Verificações redundantes
Identificação única
Código de Hamming
Bits de Dados
1
1
1
1
0
Bits de verificação
(redundantes)
1
1
0
Erro
1 0
0
0
1
1
1
0
0
0
Código de Hamming
Exemplo:
Check
bit
12 1100
11 1011
10 1010
9 1001
8 1000 C8
7 0111
6 0110
5 0101
4 0100 C4
3 0011
2 0010 C2
1 0001 C1
Data
bit
M12
M11
M10
M9
M bits de dados
K bits de verificação devem ser capazes de
codificar erros em M+K posições, quando houver
erro, mais uma posição que indica que não houve
erro.
=> 2k
M7
M6
M5
M3
 M + K + 1
C1 = M3 +
+ M7 O
+ M9 +
O M5 O
O M11
C2 = M3 +
+ M7 O
+ M10 +
O M6 O
O M11
C4 = M5 +
+ M7 O
+ M12
O M6 O
C8 = M9 +
+ M11 O
+ M12
O M10 O
Problema




Implementar o código de Hamming para uma
palavra de 8 bits
Utilizar CI’s em proto-board com algum
visualizador
A princípio, portas XOR seriam utilizadas
Utilização da lógica XOR em paridade
Solução

Utilização de XOR:
–
–

Utilização de Memória:
–
–

Dificuldades: Montagem e Tamanho do Circuito
Facilidades: Implementação pronta
Dificuldades: Programação
Facilidades: Montagem e Tamanho do Circuito
Programação:
–
Utilização de um gerador (programa que gera a
programação da memória)
Custos (outra vantagem)



Xor = US$ 0,50
Mem (27C512) = US$ 1,80
Utilização:
–
–
–
–
2 mem = US$ 3,60 = 7,2 xor = 7 xor = 28 portas
Hamming = 12 portas
Comparador = 4 portas
Inversor xor = 8 portas
Custos (outra vantagem)
Total = 2 hamming (gerador e corretor) + 1
comparador + 1 inversor + codificador + ...
Total = 2 x 12 + 4 + 8 + ... = 36 + ... portas

Custo c\ memória: US$ 3,60 = R$
10,80
Fonte Futurlec:
http://www.futurlec.com/ICEPROM.shtml
http://www.futurlec.com/IC7400Series.shtml
Geração de Dados (Programação)

Identificar:
–
–
–
–

Etapas do processo
Estruturas de dados
Atividades comuns
Formas de representação
Gerar:
–
–
–
–
Arquivos de Gravação
Classes
Métodos
Atributos e saídas
Etapas do Processo

Gerar Código
–

Identificar Erro
–

A partir do dado correto¹ gerar o seu código de
Hamming
A partir do dado alterado² e o código de Hamming
identificar o bit onde houve alteração
Corrigir
–
A partir do dado alterado² e o código de Hamming
realizar a correção se existir um único erro (SEC)
1 – teoricamente imune ao erro, dado de entrada
2 – teoricamente susceptível ao erro, dado de saída
Arquivos de Gravação

Composição em 2 arquivos
–
–

Geração
–

Geração
Identificação e Correção (mesmas entradas)
ham1.txt
Identificação e Correção
–
–
ham2.txt
Etapas multiplexadas internamente
Estruturas de Dados - Classes


Estrutura que comporte a relação entre os bits de
um vetor de bits e um número inteiro
Classe Bits
–
Atributos:


–

Métodos de Conversão
Classe Gerador (programa gerador)
–

boolean[] bits – vetor de bits
int valor – valor correspondente inteiro
Métodos de Geração Estáticos¹
Classe Arquivo (auxilia gravação em arquivo)
1 – independe de um objeto, sobre uma classe
Classe Bits
import
java.util.Vector;
import
java.lang.Boolean;
public class Bits{
public int valor;
public boolean[]
bits;
public Bits(int v){
this.valor = v;
this.resolveBits();
}
public Bits(boolean[] b){
this.bits = b;
this.resolveValor();
}
...
}
Atividades Comuns – Métodos (Bits)

Gets (obter bit do vetor):
–

Mod2 (quociente e resto da divisão por 2):
–

int[] mod2(int)
Conversão (utilizado no construtor)
–

boolean getBooleanIn(int), int getIntIn(int)
resolveBits(), resolveValor()
Xor
Classe Gerador


Métodos e Atributos Estáticos
Identificar erro
–

Correção do erro
–

char corrected(int, int)
Código Hamming
–

char correctionOut(int, int), int correction(int, int)
char hamming(int)
Auxiliares
–
int adjustOut(int), int decide(int), char int2Char(int),
boolean xor (boolean, boolean)
Ex.: char hamming(int)
public static char hamming(int v){
Bits bt = new Bits(v);
boolean[] ret = new boolean[4];
ret[0] =
Gerador.xor(bt.getBooleanIn(0),
Gerador.xor(bt.getBooleanIn(1),
Gerador.xor(bt.getBooleanIn(3),
Gerador.xor(bt.getBooleanIn(4),
bt.getBooleanIn(6)))));
//C1 = M1 + M2 + M4 + M5 + M7
ret[1] =
Gerador.xor(bt.getBooleanIn(0),
Gerador.xor(bt.getBooleanIn(2),
Gerador.xor(bt.getBooleanIn(3),
Gerador.xor(bt.getBooleanIn(5),
bt.getBooleanIn(6)))));
//C2 = M1 + M3 + M4 + M6 + M7
ret[2] =
Gerador.xor(bt.getBooleanIn(1),
Gerador.xor(bt.getBooleanIn(2),
Gerador.xor(bt.getBooleanIn(3),
bt.getBooleanIn(7))));
//C4 = M2 + M3 + M4 + M8
ret[3] =
Gerador.xor(bt.getBooleanIn(4),
Gerador.xor(bt.getBooleanIn(5),
Gerador.xor(bt.getBooleanIn(6),
bt.getBooleanIn(7))));
//C8 = M5 + M6 + M7 + M8
bt = new Bits(ret);
return Gerador.int2Char(bt.valor);
}
Classe Arquivo


Classe desenvolvida pelos monitores da
disciplina de Algoritmos e Estruturas de
Dados, para auxiliar leitura e escrita de
arquivos (entradas e saídas)
Leitura: Tipo readTipo()
–

(e.g. int readInt())
Escrita: print(Tipo), println(Tipo)
–
(e.g. println(String), print(int))
Formas de Representação



Entradas (para a geração) Inteiros
Saídas (para o arquivo) Caracteres
Conversão Direta (Cast):
char c;
int i;
c = (char) 21;
i = (int) ‘b’

Problema
–
caracteres não representados: 81, 8D, 8F, 90, 9D (hex)
Conclusões



Implementações com memória
Programação Conveniente (Resultado)
Vantagens:
–
–
–

Montagem
Tamanho
Custo
Objetivo prático:
–
–
–
Análise
Implementação
Montagem
Mais Informações

www.cin.ufpe.br/~bemaf/arquivos/arq/
–
–
–
–
SEC.ppt (esta apresentação)
Bits.java
Gerador.java
Arquivo.java