DEPARTAMENTO DE RÁDIO

Curso de Engenharia Electrónica e de Telecomunicações

Disciplina: Sistemas de Telecomunicações

TEMA:

Código de Hamming

DISCENTES:

 Salvador Joao Macuácua

DOCENTE:
Eng. Luis cumaio

Maputo, Maio, 2024

Índice
1. Introdução.................................................................................................................................1

2. Objectivos:................................................................................................................................2

2.1 Objectivo geral:.................................................................................................................2

2.2 Objectivo especifico:.........................................................................................................2

3. Código de Hamming................................................................................................................3

3.1 O Código de Hamming.....................................................................................................4

3.2 Desempenho dos códigos de Hamming............................................................................5

3.2.1 Calculando a distância mínima através da matriz H:.................................................6

3.2.2 Calculando a distância minima através das palavras código:....................................6

4. Capacidade de correção:...........................................................................................................6

4.1 Funcionamento do Código de Hamming:.........................................................................6

5. A aplicação do código de Hamming é vasta e essencial em diversas áreas da tecnologia:.....7

6. Código de Hamming em Matlab..............................................................................................8

7. Conclusão...............................................................................................................................10

8. Referencias bibliográficas......................................................................................................11

i
 1. Introdução
A teoria dos códigos corretores de erros surgiu da necessidade de garantir a integridade e
confiabilidade das comunicações digitais, especialmente em um contexto onde erros durante o
envio ou armazenamento de dados eram comuns. Iniciada na década de 1940 por visionários
como Richard W. Hamming e Claude E. Shannon, essa teoria ganhou destaque nos Laboratórios
Bell de Tecnologia, onde os primeiros computadores processavam programas gravados em
cartões perfurados. Naquela época, um simples erro poderia interromper o fluxo de execução de
um programa, levando Hamming a questionar se os computadores poderiam não apenas detectar,
mas também corrigir esses erros automaticamente. Essa ideia visionária lançou as bases para o
desenvolvimento dos códigos corretores de erros, uma área fundamental da teoria da informação
e da comunicação. À medida que as décadas avançaram, esses códigos se tornaram
indispensáveis, especialmente nas comunicações espaciais, onde a transmissão de dados precisa
e segura é crucial. Hoje, graças aos avanços contínuos nesta área, podemos nos comunicar com
facilidade e segurança através de uma variedade de canais, como telefone e internet. O estudo e a
aplicação dos códigos corretores de erros desempenharam um papel vital nessa evolução,
garantindo a integridade dos dados em todas as formas de comunicação digital, mas tendo
profundidade no código de Hamming.

1
1. Objectivos:

1.1 Objectivo geral:

Desenvolver uma implementação completa e funcional do código de Hamming (7,4) em
MATLAB, demonstrando sua capacidade de detectar e corrigir erros de um único bit

1.2 Objectivo especifico:

 Implementar a codificação dos dados utilizando a matriz geradora do código de
Hamming (7,4).
 Implementar a decodificação dos dados, incluindo a detecção e correção de erros
utilizando a matriz de verificação de paridade.
 Fornecer uma análise detalhada do funcionamento do código e sua aplicação prática.

2
 2. Código de Hamming
O código de Hamming é uma técnica inteligente e eficaz para detecção e correção de erros em
sistemas de comunicação digital e armazenamento de dados. Desenvolvido pelo matemático
Richard W. Hamming na década de 1940, este método revolucionário permite não apenas
detectar a ocorrência de erros, mas também corrigi-los em alguns casos, garantindo a integridade
e confiabilidade dos dados transmitidos ou armazenados. Em seu cerne, o código de Hamming
opera adicionando bits de paridade aos dados originais, criando assim uma redundância
controlada. Esses bits de paridade são calculados de acordo com uma fórmula específica e são
adicionados a posições estratégicas nos dados. Quando os dados são transmitidos ou
armazenados, esses bits de paridade permitem que o receptor verifique se houve algum erro na
transmissão ou armazenamento. Para entender melhor como funciona, imagine que você está
enviando uma mensagem composta por uma série de zeros e uns, representando informações
binárias. Antes de enviar essa mensagem, você calcula e adiciona alguns bits de paridade,
conforme determinado pelo código de Hamming. Estes bits adicionais são como "marcadores"
que ajudam a detectar erros. Durante a transmissão ou armazenamento, se ocorrer algum erro e
os dados forem recebidos de forma incorreta, o receptor pode usar os bits de paridade para
identificar exatamente onde ocorreu o erro. Em alguns casos, o código de Hamming também
permite corrigir automaticamente esses erros, garantindo que os dados sejam recuperados com
precisão.

Um código de Hamming adiciona um bloco de paridade a um bloco de dados, de forma a que,

caso ocorram erros de transmissão, seja possível detectar ou corrigir erros do bloco transmitido.

De todas as possíveis palavras de código, considerar como válidas apenas algumas.

Exemplo: 000,111

3
A distância mínima entre as palavras de código é de 3 bits (distância de Hamming).
Se um bit for corrompido, o receptor detecta uma palavra de código inválida e pode recuperar o
original escolhendo a palavra de código válida mais próxima.
Álgebra Linear e Aritmética Modulo
Aritmética modulo 2:
Adição = XOR Produto = AND
Álgebra linear:

Seja A uma matriz n × m e x um vetor de dimensão m.

null(A), o espaço nulo de A, é o espaço gerado pelos vetores x que verificam Ax = 0.
rank(A) é o número de linhas/colunas linearmente independentes.
Temos que rank(null(A)) + rank(A) = m.
Exemplo:

Rank (H) = 2;
Null (H) = 000,111, rank (null (H)) = 1;
Rank (H) + rank (null (H)) = 2 + 1 = 3.

2.1 O Código de Hamming

Um código de Hamming (c, d) é formado da seguinte maneira:
Constroi-se uma matriz H cujas colunas são formadas por todos os vetores não nulos de
dimensão p = c − d. O código de Hamming consiste no espaço nulo da matriz H, i.e., as palavras
de código verificam Hc = 0.
Exemplo:
Código (3,1) -> 1 bit dados + 2 bits redundância
Espaço nulo de H é composto pelos vetores [000] e [111]

Detecção de erros

Como as palavras de código pertencem ao espaço nulo de H, é muito simples verificar se houve
erro de transmissão:

4
Basta verificar se a palavra recebida r pertence ao espaço
Nulo!
Se Hr = 0, então r pertence ao espaço nulo → OK!
Se Hr 6= 0, então r não pertence a null(H) → ERRO!
Exemplo:
Se c = 000 e r = 000, Hr = [00]′ → sem erros.
Se c = 000 e r = 001, Hr = [11]′ → erros detectados.
Se c = 000 e r = 101, Hr = [10]′ → erros detectados.
Se c = 000 e r = 111, Hr = [00]′ → sem erros.
Note que se existirem 3 erros é recebida uma palavra válida e não são detectados erros.

Detecta-se um erro quando Hr 6= 0. Como se pode saber qual o erro que ocorreu?
Suponhamos que ocorreu um erro na posição i. Usando um vector ei = [0 . . . 010 . . . 0] para
representar a posição onde ocorre o erro, temos que r = c + ei . Então, Hr = H(c + ei ) = Hc + Hei
= Hei .
Mas Hei corresponde a i-ésima coluna de H. Portanto, calculando Hr e procurando em H,
obtemos a posição i onde ocorreu o erro. Para corrigi-lo, basta invertê-lo.

2.2 Desempenho dos códigos de Hamming

Taxa de transmissão é: R =

Aumentando o tamanho das palavras de código, é possível fazer R → 1.

No entanto, a probabilidade de erro na decodificação também converge para 1:
A probabilidade de a decodificação ser correta corresponde a haver até um erro numa palavra de
comprimento c. Num canal binário simétrico com probabilidade de erro pe a probabilidade de
decodificação correta de um código (c, d), é dada por:

(1 − pe)c + cpe(1 − pe)c−1, cujo limite é zero quando c → ∞.

Distância mínima de um código de Hamming:

Pode ser determinado através da matriz H ou com uma analise das palavras código.

5
 2.2.1 Calculando a distância mínima através da matriz H:
A distância mínima do código será determinada pelo numero mínimo de colunas da matriz H que
devem ser somadas para se obter o vetor nulo.
Exemplo:

A distancia mínima para o código cuja matriz H foi dada acima é 3, porque são necessária a
soma de no mínimo 3 colunas para obtermos o vetor nulo.

2.2.2 Calculando a distância minima através das palavras código:

A distancia mínima do código será determinado pela mesma distância entre duas palavras código
lembrando que o vetor nulo sempre corresponde a uma palavra código.

Se calcularmos as distâncias entre todas as palavras código o menor valor obtido corresponde a
distância mínima para o código. Nesse exemplo

Capacidade de detecção:
o número de erros que podem ser detectados utilizando um código de Hamming dependerá da
distancia minima (dMIN) do código utilizado. e o número máximo de erros detectados será dado

por:

3. Capacidade de correção:
O número de erros que podem ser corrigidos utilizando um código de Hamming também
dependerá da distancia minima (dMIN) do código utilizado. e o número máximo de erros
corrigidos será dado por:

3.1 Funcionamento do Código de Hamming:

O código de Hamming opera adicionando bits de paridade aos dados originais, criando
redundância de informações que permitem detectar e corrigir erros. Esses bits de paridade são

6
calculados de acordo com uma fórmula específica e são adicionados a posições estratégicas nos
dados. Essas posições são selecionadas de forma que cada bit de paridade cubra um conjunto
específico de bits de dados, permitindo a detecção e, em alguns casos, a correção de erros.

Quando os dados são transmitidos ou armazenados, os bits de paridade são enviados junto com
os dados originais. No receptor, os bits de paridade são usados para verificar a integridade dos
dados. Se os dados forem recebidos corrompidos devido a erros de transmissão ou
armazenamento, os bits de paridade permitirão identificar a ocorrência desses erros e, em alguns
casos, corrigi-los automaticamente.

4. A aplicação do código de Hamming é vasta e essencial em diversas áreas da

tecnologia:
Em redes de computadores, onde a transmissão de dados é suscetível a ruídos e interferências, o
código de Hamming é usado para garantir a precisão da comunicação, minimizando o impacto de
erros. Na memória de computadores, como na RAM, onde erros de leitura podem ocorrer devido
a falhas temporárias, o código de Hamming ajuda a garantir a estabilidade do sistema, detectando
e corrigindo erros de forma eficiente. Em dispositivos de armazenamento, como discos rígidos,
CDs e DVDs, o código de Hamming é empregado para garantir a integridade dos dados, mesmo
em condições adversas, como arranhões na mídia ou degradação ao longo do tempo.

7
 5. Código de Hamming em Matlab
function hamming_code_demo()
% Solicitar entrada do usuário
data_bits = input('Digite os 4 bits de dados (como um vetor de 1 e 0):
');

if length(data_bits) ~= 4 || any(data_bits ~= 0 & data_bits ~= 1)

error('Por favor, insira exatamente 4 bits de dados (0 ou 1).');
end

% Gerar o código de Hamming (7,4)

encoded_bits = encode_hamming74(data_bits);
disp('Bits codificados (7 bits):');
disp(encoded_bits);

% Simular um erro (opcional)

encoded_bits_with_error = encoded_bits;
encoded_bits_with_error(3) = ~encoded_bits_with_error(3); % Inverter
o 3º bit
disp('Bits codificados com erro simulado:');
disp(encoded_bits_with_error);

% Decodificar e corrigir erros

[decoded_bits, error_position] =
decode_hamming74(encoded_bits_with_error);
disp('Bits decodificados (4 bits):');
disp(decoded_bits);

if error_position > 0
fprintf('Erro detectado e corrigido na posição %d.\n',
error_position);
else
disp('Nenhum erro detectado.');
end
end

function encoded = encode_hamming74(data)

% Matriz geradora G para código de Hamming (7,4)
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];

% Codificar os bits de dados

encoded = mod(data * G, 2);
end

function [decoded, error_position] = decode_hamming74(encoded)

% Matriz de verificação de paridade H para código de Hamming (7,4)
H = [1 1 0 1 1 0 0;
1 0 1 1 0 1 0;
0 1 1 1 0 0 1];

8
 % Síndrome
syndrome = mod(H * encoded', 2)';

% Tabela de correspondência de síndromes para posições de erro

error_position = bi2de(syndrome, 'left-msb');

% Se a síndrome não for zero, corrigir o erro

if error_position > 0
encoded(error_position) = ~encoded(error_position);
end

% Extrair os bits de dados (os primeiros 4 bits)

decoded = encoded(1:4);
end

% Executar a demonstração
hamming_code_demo();v

9
 6. Conclusão
O código de Hamming representa um avanço significativo na teoria da correção de erros,
oferecendo uma solução eficaz para a detecção e correção de erros de bit único. Sua
implementação simples e eficiência tornam-no uma escolha popular em diversas aplicações de
comunicação e armazenamento de dados. No entanto, em sistemas suscetíveis a múltiplos erros
de bit, métodos mais robustos podem ser necessários.

10
7. Referencias bibliográficas

 Hamming, R. W. (1950). Error detecting and error correcting codes. Bell System
Technical Journal, 29(2), 147-160.
 Peterson, W. W., & Weldon, E. J. (1972). Error-Correcting Codes. MIT Press.
 Lin, S., & Costello, D. J. (2004). Error Control Coding: Fundamentals and Applications.
Pearson.
 Huffman, W. C., & Pless, V. (2003). Fundamentals of Error-Correcting Codes.
Cambridge University Press.

11