Universidade Federal de São Carlos
Centro de Ciências Exatas e de Tecnologia
Departamento de Matemática
Códigos Corretores de Erros
Autor: Carla Meneghesso
Orientador: Prof. Dr. Sadao Massago
Disciplina: Trabalho de Conclusão de Curso
Curso: Licenciatura em Matemática
Professores Responsáveis: Karina Schiabel Silva
Sadao Massago
Vera Lúcia Carbone
São Carlos, 6 de agosto de 2012.
i
Códigos Corretores de Erros
Autor: Carla Meneghesso
Orientador: Prof. Dr. Sadao Massago
Disciplina: Trabalho de Conclusão de Curso
Curso: Licenciatura em Matemática
Professores Responsáveis: Karina Schiabel Silva
Sadao Massago
Vera Lúcia Carbone
Instituição: Universidade Federal de São Carlos
Centro de Ciências Exatas e de Tecnologia
Departamento de Matemática
São Carlos, 6 de agosto de 2012.
Carla Meneghesso
Sadao Massago
iii
Dedicatória
Este trabalho dedico aos meus pais Onofre e Maria de Lourdes que me fizeram lutar até
o final apesar de todas as dificuldades e possibilitaram que eu realizasse o meu maior
sonho: estudar.
Agradecimentos
Agradeço aos meus pais Onofre e Maria de Lourdes e ao meu irmão Arthur por me
ajudarem nessa longa caminhada. Sem a minha famı́lia este trabalho não seria possı́vel,
pois me apoiaram e me deram forças para superar momentos difı́ceis.
Agradeço ao Prof. Dr. Sadao Massago pela imprescindı́vel ajuda e tempo dedicados,
pela orientação no desenvolvimento do meu trabalho fosse desenvolvido. Muito obrigada
pela compreensão por eu trabalhar e não pude me dedicar tanto quanto gostaria neste
trabalho.
Agradeço ao meu namorado Carlos Eduardo Domingues Nazário por toda a paciência,
carinho, compreensão e ajuda dedicada, pois sem seu companheirismo eu não teria conseguido ir até o fim da graduação. Muitı́ssimo obrigada, pois muitos foram os momentos
que você deixou de buscar seus sonhos para que o meu se realizasse. Sem o seu apoio este
trabalho não existiria.
Este trabalho simboliza a superação de um momento muito delicado da minha vida na
qual aprendi não só a importância da Matemática, mas também que podemos seguir em
frente mesmo que alguns obstáculos tenham surgido e tentado impedir que nossos sonhos
fossem concretizados. A Matemática me conquistou desde o colégio e esta monografia é
uma pequena demonstração de que esta ciência é singular em minha vida.
vi
“Procure ser um homem de valor, em vez de ser um homem de sucesso.”
(Albert Einstein)
viii
ix
Resumo
Neste trabalho serão apresentados conceitos básicos de códigos, vetores para projetar
códigos detectores de erros que podem ocorrer na transmissão de dados e os dı́gitos de
verificação. Posteriormente definimos o que é um código detector de erros, como também
a métrica de Hamming, os parâmetros de um código e equivalência de códigos. Para o
desenvolvimento do projeto foi necessário estudar anéis, corpos e anéis de polinômios para
que pudéssemos descrever os corpos finitos e sua construção. Foram estudados os Códigos
Lineares (Códigos Duais e Códigos de Reed-Muller), Códigos Cı́clicos, decodificação destes
e finalmente trabalhamos com algumas aplicações de códigos. Neste trabalho foi possı́vel
identificar a aplicação da Matemática em mercadorias e transmissão de dados, que é uma
vasta aplicação de conceitos algébricos que facilitam o dia-a-dia das pessoas.
Introdução
Historicamente, a informação por meio de códigos era utilizada com o objetivo de ocultar
uma mensagem, denominados de Criptografia. O enfoque deste projeto não é criptografia,
mas os códigos utilizados quando a informação digital deve ser transmitida com o uso de
meios analógicos tais como a luz, ondas de rádio, gravações eletromagnéticas, etc. Com a
introdução dos computadores no século XX, houve uma necessidade de transmitir grandes
quantidades de dados com rapidez e precisão. Além dos computadores, outros avanços
tecnológicos dependem de códigos, tais como: comunicação via satélite, CD, Códigos
Universais de Produtos (UPC-Universal Product Code) associados aos códigos de barras
e o Padrão Internacional de Numeração de Livros (ISBN- International Standard Book
Number).
Os vetores utilizados para o estudo de códigos não são vetores de Rn , mas vetores
em Fn onde F é um corpo finito. Assim, terão um número finito de possibilidades para
cada componente. Tais vetores dependem de um tipo diferente de aritmética - chamada
aritmética modular.
A teoria moderna de códigos originou-se com o trabalho de Claude Shannon (1916 −
2001), que teve um papel importante na criação da teoria da informação e da base teórica
para os hoje chamados códigos corretores de erros.
A teoria dos códigos vem sendo utilizada com sucesso na nossa história recente. Em
1965, a nave espacial Mariner 4 enviou 22 fotos em preto e branco de Marte com 64
tons de cinza para cada um de seus 200 × 200 pontos, que é um elemento de Z62 . A esses
vetores não acrescentavam-se informações adicionais, pois a transmissão era muito lenta,
demorando em torno de 8 horas para transmitir cada foto.
Em 1972, a nave espacial Mariner 9 transmitiu imagens de Marte com uma resolução
de 700×832 pontos. Como a velocidade da transmissão era maior, o código foi recodificado
através de uma função injetora ϕ : Z62 =⇒ Z32
para acrescentar o código de canal
2
que permite detectar e corrigir até sete erros. O dado recebido era corrigido e decodificado
através de uma transformação ϕ(−1) , obtendo-se o elemento de Z62 que representa o tom
de cinza correspondente. Esse código pertence à famı́lia de códigos chamados de Códigos
de Reed-Muller.
Em 1979, a nave espacial Voyager transmitiu imagens coloridas de Júpiter. Cada
elemento de imagem de uma cor foi representado por uma das 212 = 4096 tonalidades. O
codificador da fonte usava 12 bits binários e o codificador de canal usava 24 bits. Esse era
xii
o chamado código de Golay que permitia corrigir até três erros.
No capı́tulo 1, são apresentados conceitos algébricos que darão suporte aos demais
capı́tulos que tratam de códigos detectores e códigos corretores de erros, como anel dos
inteiros, classificação e construção de corpos finitos, espaço vetorial, etc.
O capı́tulo 2 trata dos códigos binários e como os vetores de códigos são determinados,
incluindo o processo de codificação e de decodificação de uma mensagem.
No capı́tulo 3 são estudados os códigos detectores de erros, incluindo os códigos bit
de paridade. Neste capı́tulo serão dadas aplicações dos códigos detectores de erros, como
o UPC (Universal Product Code), o EAN13 e o ISBN (International Standard Book
Number).
No capı́tulo 4 é feita um abordagem dos códigos corretores de erros, tratando da matriz
geradora do código e de teste de paridade no Matlab, Métrica de Hamming, Equivalência
de códigos, Código de Hamming, Decodificação, Algoritmo da decodificação, Distâncias
mı́nimas e Corretores de erros geométricos.
No capı́tulo 5 são estudados os Códigos lineares, a matriz geradora destes códigos,
Códigos duais, Códigos de Reed-Muller e Decodificação de Códigos de Reed-Muller.
No capı́tulo 6 é feito o estudo dos Códigos cı́clicos e sua decodificação.
xiii
Sumário
1 Conceitos Preliminares
1
2 Códigos
2.1 Códigos Binários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
7
3 Códigos Detectores de Erros
9
3.1 Código bit de paridade par (3, 2) . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Aplicações de Códigos Detectores de Erros . . . . . . . . . . . . . . . . . . 11
4 Códigos Corretores de Erros
4.1 Matriz geradora e de teste de paridade no Matlab . . . . . .
4.2 Métrica de Hamming . . . . . . . . . . . . . . . . . . . . . .
4.3 Códigos de Hamming . . . . . . . . . . . . . . . . . . . . . .
4.4 Decodificação . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Algoritmo da Decodificação . . . . . . . . . . . . . . . . . .
4.6 Distâncias Mı́nimas e Corretores de Erros Geometricamente
5 Códigos Lineares
5.1 Equivalência de Códigos . . . . . . . . .
5.2 Matriz Geradora de um Código . . . . .
5.3 Códigos Duais . . . . . . . . . . . . . . .
5.4 Códigos de Reed-Muller . . . . . . . . .
5.5 Decodificação de Códigos de Reed-Muller
Referências Bibliográficas
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
21
23
25
26
27
28
.
.
.
.
.
29
31
32
35
37
39
43
xv
Lista de Figuras
1.1
1.2
1.3
Aritmética módulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Aritmética módulo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Reta numerada enrolada em volta de um cı́rculo . . . . . . . . . . . . . . .
3.1
3.2
3.3
3.4
3.5
Palavras de código de bit de paridade par (3, 2) . . .
Exemplo de UPC . . . . . . . . . . . . . . . . . . . .
Explicação do código de barras utilizado em produtos
Exemplo do código de barras utilizado atualmente . .
ISBN . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
12
13
14
15
4.1
4.2
4.3
4.4
Procedimento para transmissão de dados . . . . . . . . . .
Representação do disco e da esfera de centro em a e raio t
Representação geométrica dos códigos corretores de erros .
Representação esférica dos códigos corretores de erros . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
24
28
28
.
.
.
.
.
.
.
.
.
.
2
2
3
1
Capı́tulo 1
Conceitos Preliminares
Para o desenvolvimento do estudo de códigos, precisamos introduzir alguns conceitos
básicos de estruturas algébricas, tais como anéis e corpos, o que permitem tratar os
conjuntos que possuem operações com propriedades similares.
Definição 1.1. Um anel comutativo é um conjunto A munido de duas operações,
+ : A×A →
A
(a, b) 7→ a + b
e
· : A×A → A
(a, b) 7→ a · b
que chamaremos respectivamente de adição e multiplicação, possuindo as seguintes propriedades:
(i) Associatividade da adição: ∀a, b, c ∈ A, (a + b) + c = a + (b + c).
(ii) Existência de elemento neutro para a adição: Existe um elemento chamado zero e
denotado por 0, tal que ∀a ∈ A, a + 0 = 0 + a = a.
(iii) Existência de elemento inverso para a adição: Dado a ∈ A, existe um único
elemento chamado simétrico de a e denotado por −a tal que
a + (−a) = −a + a = 0.
(iv) Comutatividade da adição: ∀a, b ∈ A, a + b = b + a.
(v) Associatividade da multiplicação: ∀a, b, c ∈ A, (a.b).c = a.(b.c).
(vi) Existência de elemento neutro para a multiplicação: Existe um elemento neutro
chamado unidade e denotado por 1 tal que ∀a ∈ A, a.1 = 1.a = a.
(vii) Comutatitvidade da multiplicação: ∀a, b ∈ A, a.b = b.a.
(viii) Distributividade da multiplicação com relação à adição: ∀a, b, c ∈ A, a.(b + c) =
a.b + a.c.
2
1. Conceitos Preliminares
Exemplo 1.2. O anel dos inteiros módulo m. O Zm = {0, 1, 2, . . . , m − 1, }, m ≥ 0
possui as operações + e · definidas por:
(i) a + b = a + b,
(ii) a · b = a · b
No exemplo 1.2, o conjunto Zm = {0, 1, 2, . . . , m − 1, } de inteiros módulo m corresponde ao relógio de m horas representado pela Figura 1.1 e o conjunto dos vetores m-ários
de comprimento n são denotados por Znm . Os códigos que utilizam os vetores m-ários são
chamados códigos m-ários.
Figura 1.1: Aritmética módulo m
No caso dos inteiros módulo 3, podemos representar o conjunto como um relógio de
três horas, como na Figura 1.2 .
Figura 1.2: Aritmética módulo 3
Quando calculamos 1 + 2 = 0 interpretamos do seguinte modo: duas horas após 1 hora
é 0 hora. Assim, como 24:00 e 12:00 são representados pela mesma marca em um relógio
de doze horas, 3 e 0 são equivalentes em um relógio de três horas. Todos os números
múltiplos de 3 são equivalentes a 0; os números que são iguais a 1 mais um múltiplo
de 3 é equivalente a 1; e 2 é equivalente a qualquer número que seja igual a 2 mais um
múltiplo de 3. É como se fosse uma reta numerada enrolada em volta de um cı́rculo como
na Figura 1.3.
Exemplo 1.3. Em Z53 sejam u = (2, 2, 0, 1, 2) e v = (1, 2, 2, 2, 1). Então:
1. Conceitos Preliminares
3
Figura 1.3: Reta numerada enrolada em volta de um cı́rculo
u·v =2·1+2·2+0·2+1·2+2·1 =2+1+0+2+2 =1
Os vetores de código em Z53 são chamados de vetores ternários de comprimento 5.
Definição 1.4. Um anel A será chamado de domı́nio de integridade, se possuir a seguinte
propriedade:
∀a, b ∈ A, a 6= 0 e b 6= 0 ⇒ a.b 6= 0.
Como [2] não é invertı́vel, temos que Z4 não é um corpo. Como [2] · [2] = [4] = [0],
temos que esse anel não é um domı́nio de integridade.
Definição 1.5. Um elemento a de um anel A será dito invertı́vel se existir um elemento
b ∈ A tal que a · b = 1. Nesse caso, dizemos que b é um inverso de a.
Definição 1.6. Um anel onde todo elemento não nulo é invertı́vel é chamado de corpo.
Um exemplo de corpo são os inteiros módulo 3 que consistem no conjunto Z3 =
{0, 1, 2}, com adição e multiplicação dadas como no exemplo 1.3. A tabela de operação é
como segue.
Tabela 1.1: Operações de adição e multiplicação em Z3
+
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
e
·
0
1
2
0
0
0
0
1
0
1
2
2
0
2
1
Como os elementos não nulos 1 e 2 são invertı́veis, com inversos respectivamente 1 e
2, temos que Z3 é um corpo.
Teorema 1.7. O anel Zm é um corpo se, e somente se, m é um número primo.
Exemplo 1.8. Seja b = (b1 , b2 , · · · , bn ) um vetor de Zn3 . Incluindo um dı́gito de checagem
ao vetor de código, vamos ter um código com n + 1 termos e pode ser expresso como
v = (b1 , b2 , · · · , bn , d) onde d é um dı́gito de checagem de forma que 1 · v = 0 e v é um
vetor de código em Zn+1
. O dı́gito de checagem satisfaz
3
4
1. Conceitos Preliminares
b1 + b2 + . . . + bn + d = 0 em Z3
Definição 1.9. Um conjunto não vazio V é um espaço vetorial sobre (um corpo) K se
em seus elementos, denominados vetores, estiverem definidas as seguintes operações:
(A) A cada par u, v de vetores de V corresponde um único vetor u + v ∈ V , chamado
soma de u e v, de modo que:
(A1) u + v = v + u, ∀ u, v ∈ V (propriedade comutativa).
(A2) (u + v) + w = u + (v + w), ∀ u, v, w ∈ V (propriedade associativa).
(A3) existe um vetor em V , denominado vetor nulo e denotado por 0, tal que 0 + v = v
∀ v ∈V.
(A4) a cada vetor v ∈ V , existe um vetor em V denotado por −v, tal que v + (−v) = 0.
(M) A cada par α ∈ K e v ∈ V , corresponde um vetor α · v ∈ V , denominado produto
por escalar de α por v de modo que:
(M1) (αβ) · v = α · (β · v), ∀α, β ∈ K e ∀v ∈ V (propriedade associativa).
(M2) 1 · v = v, ∀v ∈ V (onde 1 é o elemento identidade de K).
Além disso, vamos impor que as operações dadas em (A) e (M ) se distribuam, isto é, que
tenham as seguintes propriedades:
(D1) α · (u + v) = α · u + α · v, ∀α ∈ K e ∀u, v ∈ V .
(D2) (α + β) · v = α · v + β · v, ∀α, β ∈ K e ∀v ∈ V .
Definição 1.10. Seja V um espaço vetorial sobre um corpo K. Um subconjunto W de V
é um subespaço vetorial de V se a restrição das operações de V a W torna esse conjunto
um K-espaço vetorial.
Note que como Z2 é corpo, Zn2 é um espaço vetorial.
Dado um corpo F, V = Fn é um espaço vetorial com produto escalar canônico.
No exemplo 1.3, considerando o vetor u = (2, 2, 0, 1, 2), ao somarmos suas coordenadas
temos 2 + 2 + 0 + 1 + 2 = 1 e vemos que o dı́gito de checagem deve ser 2 para que a soma
das coordenadas com o dı́gito de checagem seja igual a zero módulo Z3 e então o vetor
código de checagem é v = (2, 2, 0, 1, 2, 2).
Os códigos de checagem de dı́gitos podem detectar erros simples, mas para detectar a
troca de duas coordenadas adjacentes, por exemplo, outros tipos de códigos são utilizados.
Muitos deles substituem o vetor de checagem 1 por algum outro vetor c cautelosamente
escolhido.
Como os dados no computador, os dados são codificados usando sequência de 0s e 1s
que podem ser associados ao vetor binário v ∈ Zn2 . Por esta razão, o corpo Z2 tem papel
importante na teoria de códigos.
1. Conceitos Preliminares
5
Proposição 1.11. Seja A, +, · um anel e seja I um subconjunto de A. Então, I é um
subanel de A se e somente se as seguintes condições são verificadas:
(i) 0 ∈ I (o elemento neutro de A pertence a I)
(ii) x, y ∈ I =⇒ x − y ∈ I (I é fechado para a diferença)
(iii) x, y ∈ I =⇒ x · y ∈ I (I é fechado para o produto).
Definição 1.12. Seja A um anel e seja I um subanel de A. Dizemos que I é um ideal de
A se
(i) (x + y) ∈ I, ∀x, y ∈ I
(ii) a · x ∈ I, ∀a ∈ A, ∀x ∈ I (simbolicamente A · I ⊂ I e I · A ⊂ I).
6
1. Conceitos Preliminares
7
Capı́tulo 2
Códigos
2.1
Códigos Binários
Os códigos binários consistem em vetores cujas coordenadas são iguais a 0 ou 1. Os
computadores descrevem dados em termo de 0s e 1s (que podem ser interpretados como
desligado/ligado, fechado/aberto, falso/verdadeiro ou não/sim). A aritmética é como
segue
+ 0
0 0
1 1
1
1
0
e
· 0
0 0
1 0
1
0
1
Com tais operações, nosso conjunto de escalares {0, 1} é o conjunto dos inteiros módulo
2 que denotaremos por Z2 .
Exemplo 2.1. Soma em Z2
1+1+0+1=1 e 1+1+1+1=0
Regra de Paridade, ou seja se número de 1’s for par, a soma é 0. Se for ı́mpar, a soma
será 1.
O vetor do espaço vetorial Zn2 (sobre o escalar Z2 ) é o conjunto das n-uplas de 0s e 1s.
Os vetores em Zn2 são chamados de vetores binários de comprimento n.
Exemplo 2.2. Os vetores em Z22 são (0, 0), (0, 1), (1, 0) e (1, 1)
Exemplo 2.3. Sejam u = (1, 1, 0, 1, 0) e v = (0, 1, 1, 1, 0) dois vetores binários de comprimento 5. Determine u.v
O cálculo de u.v é feito em Z2 , por isso temos
u.v = 1.0 + 1.1 + 0.1 + 1.1 + 0.0
=0+1+0+1+0
=0
8
2. Códigos
Para a transmissão de dados, começamos codificando cada “palavra”da mensagem por
um vetor binário. Ou seja, converte-se o que se quer transmitir numa sequência de bits
que compõe o vetor binário.
Definição 2.4. Um código binário é um conjunto de vetores binários (de mesmo comprimento) chamados vetores de códigos. O processo de conversão de uma mensagem em
vetores de código é chamado codificação, e o processo inverso é chamado decodificação.
9
Capı́tulo 3
Códigos Detectores de Erros
O Código detector de erros é a representação de uma mensagem que permite detectar
erros. Note que no envio de mensagens através de um canal (por exemplo uma linha de
telefone, ondas de rádio, um cabo de fibra ótica) podem ocorrer “ruı́dos”, como sinais
de interferência ou sujeira. O mesmo ocorre quando se faz a leitura de código de barras,
CD/DVD ou HD, na qual o erro pode ser introduzido. O objetivo do código é detectar
possı́veis erros na transmissão ou na leitura.
Um destes códigos detectores de erros é o bit de paridade, que permite obter um
código eficiente e relativamente simples. A seguir faremos uma abordagem do código bit
de paridade par (3, 2).
3.1
Código bit de paridade par (3, 2)
No código bit de paridade par (3, 2) adiciona-se um bit de paridade no final da mensagem.
Esse bit é a soma módulo 2 dos bits da mensagem obtendo-se assim a palavra de código
c = [c0 , c1 , c0 + c1 ]
Logo, somando-se os dı́gitos temos:
(
Soma dos dı́gitos = [número de bits ativo] ×1 =
0
1
se for par
se for ı́mpar
Logo, a soma de dı́gitos de c sempre é 0.
Vejamos na tabela 3.1, as palavras de código para cada mensagem enviada. Este
código tem d = 2 e detecta a presença de 1 e 3 bits errados, pois o valor d = 2 garante
que erros de 1 bit podem ser detectados, para qualquer código. Neste código é possı́vel
também detectar 3 bits errados. A decodificação é realizada recalculando a paridade da
mensagem recebida e fazendo a comparação da mesma com o código transmitido. Se
as palavras enviada e recebida forem iguais não serão detectados erros, caso contrário
poderão ser detectados 1 ou 3 erros na palavra recebida. A figura 3.1 mostra a posição
relativa das palavras de código, mostrando que d = 2, pois é necessário percorrer duas
arestas do cubo para ir de uma até outra palavra de código. Quando ocorrem um número
10
3. Códigos Detectores de Erros
Tabela 3.1: Mensagens e palavras de código para o código bit de paridade par (3, 2)
Mensagem Palavra de código
00
000
01
011
10
101
11
110
ı́mpar de erros sobre qualquer palavra de código, é possı́vel detectá-los, já que resulta
numa palavra que não pertence ao código.
Figura 3.1: Palavras de código de bit de paridade par (3, 2)
Vejamos como funcionam os códigos detectores de erros através de alguns exemplos.
Exemplo 3.1. Desejamos codificar e transmitir uma mensagem que consiste em uma das
palavras up, down, left, right. São quatro palavras, mas acrescentando bit de paridade no
final, teremos quatro vetores de Z32 , como na Tabela 3.2.
Tabela 3.2: Comandos codificados como elementos de Z32
Mensagem
Código
Up
(0,0,0)
Down
(0,1,1)
Left
(1,0,1)
Right
(1,1,0)
Decodificar uma mensagem é simples quando não ocorrem erros na sua transmissão.
Vamos considerar que ocorreu um erro na transmissão, resultando em alteração em
uma das coordenadas do vetor de código e o “down”que é (0, 1, 1), foi recebido como
(1, 1, 1), (0, 0, 1) ou (0, 1, 0). Como nenhum deles é um código válido (up, down, left ou
right), sabemos que ocorreu um erro na transmissão, mas ainda não temos as ferramentas
para detectar onde está o erro.
O exemplo 3.1 é um código detector de erros. Mas o avanço tecnológico permitiu não
somente detectar como também corrigir erros de transmissão. Uma forma de detectar
erros é utilizar o código de checagem de paridade, que consiste na introdução de dı́gito de
3.2. Aplicações de Códigos Detectores de Erros
11
checagem acrescentado a cada vetor para que a paridade, ou número total de 1s, seja um
número par.
Exemplo 3.2. Se a mensagem a ser enviada for o vetor binário (1, 0, 0, 1, 0, 1), que possui
um número ı́mpar de 1s, o dı́gito de checagem será 1, para que o número total de 1s no
vetor de código seja par. Logo, o vetor de código será (1, 0, 0, 1, 0, 1, 1). Se acontecer
algum erro na transmissão da mensagem ele será detectado, pois a paridade do vetor de
código será alterada de par para ı́mpar. Por exemplo, se ocorrer um erro na terceira
coordenada, o vetor de código a ser recebido é (1, 0, 0, 1, 0, 1, 1) e sua paridade é ı́mpar,
pois tem cinco 1s.
Agora veremos o dı́gito de checagem mais geral. Vamos supor a mensagem que se
quer enviar seja o vetor b = (b1 , b2 , . . . , bn ) em Znk . O vetor código de checagem de
paridade é v = (b1 , b2 , . . . , bn , d) em Zn+1
, onde o dı́gito de checagem d é escolhido de
k
maneira que
b1 + b2 + . . . + bn + d = 0 em Zk
ou
1.v = 0
onde 1 = (1, 1, . . . , 1) é um vetor com todas as coordenadas iguais a 1. O vetor 1 é
chamado vetor de checagem. Quando ocorrem erros, temos que 1 · v 6= 0 para algum v.
Nesse projeto, estamos estudando o caso que ocorre apenas um erro.
As coordenadas dos vetores de código podem ser elementos do conjunto finito Zk+1 =
{0, 1, 2, . . . , k} para k ≥ 2 que é um anel.
3.2
Aplicações de Códigos Detectores de Erros
Dentre as aplicações dos Códigos Detectores de Erros estão o UPC (Código Universal de
Produto), o EAN-13 (Código de barras) e o ISBN (Padrão Internacional de Numeração
de Livros), que são códigos que possuem o dı́gito de checagem.
UPC(Universal Product Code) - Código Universal de Produto e EAN-13
Há dois tipos de códigos de barras em uso para identificação dos itens à venda. O
UPC é o mais antigo deles, usado inicialmente apenas na América do Norte. Ele utiliza
doze dı́gitos (escrito na forma de barras) para ser lidos por uma máquina de luz refletida.
Também vem com os números abaixo das barras para ser lidos por um humano quando
necessário. Com o tempo, passou-se a usar o EAN-13 que utiliza treze dı́gitos, que permite
também distinguir o paı́s de origem do produto. Esse é o que está sendo utilizado no Brasil.
Os dois tipos de códigos são muito semelhantes, onde o UPC usa apenas um dı́gito para
12
3. Códigos Detectores de Erros
identificar o paı́s de origem, enquanto o EAN-13 utiliza dois dı́gitos e portanto possui 13
dı́gitos.
Para compreender o funcionamento dos códigos detectores de erros é preciso entender
como é atribuı́do a cada produto, um dı́gito que permite essa detecção.
Suponhamos que um produto está identificado. O UPC é um código associado aos
códigos de barras encontrados em mercadorias, na qual o leitor do código de barras escaneia as barras pretas e brancas que correspondem a um vetor 10-ário
v = (v1 , v2 , . . . , v11 , d) ∈ Z12
10
de comprimento 12. As informações sobre o fabricante e o produto são dadas pelas 11
primeiras componentes. A última componente d é o dı́gito de checagem escolhido de
maneira que c.v = 0 em Z10 , onde o vetor de checagem c é dado por
c = (3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1)
Depois de um rearranjo, temos
3(v1 + v3 + v5 + v7 + v9 + v11 ) + (v2 + v4 + v6 + v8 + v10 ) + d = 0
onde d é o dı́gito de checagem.
Os pesos dos dı́gitos das posições pares e ı́mpares são diferentes para detectar o
deslocamento de digitos devido a erros de entrada, como troca de posição de dois dı́gitos
consecutivos. O dı́gito de checagem é escolhido de maneira que o lado esquerdo da
expressão resulte num múltiplo de 10.
Exemplo 3.3. Seja o UPC como mostrado na Figura 3.3. Vamos verificar se o dı́gito de
checagem realmente é 6, considerando que os cálculos são feitos em Z10 .
Figura 3.2: Exemplo de UPC
Temos que v
=
(0, 7, 4, 9, 2, 7, 0, 2, 0, 9, 4, d)
(3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1), obtemos:
e
sabendo
que
c
=
c·v =3·0+1·7+3·4+1·9+3·2+1·7+3·0+1·2+3·0+1·0+3·4+1·d
3.2. Aplicações de Códigos Detectores de Erros
13
= 3.(0 + 4 + 2 + 0 + 0 + 4) + 1.(7 + 9 + 7 + 2 + 9 + d)
= 3.(0) + 1.(4) + d
=4+d
Como 4 + d = 0 em Z10 , então d deve ser igual a 6.
Exemplo 3.4. O UPC permite detectar erros simples (erro na coordenada) ou erros
gerados por trocas entre as coordenadas. Vamos supor que no exemplo 3.3, o UPC seja
escrito como v = (0, 7, 4, 2, 9, 7, 0, 2, 0, 9, 4, 6), ou seja, a quarta e a quinta coordenadas
tiveram suas posições invertidas. Fazendo os cálculos em Z10 obtemos:
c · v0 = 3 · 0 + 1 · 7 + 3 · 4 + 1 · 9 + 3 · 2 + 1 · 7 + 3 · 0 + 1 · 2 + 3 · 0 + 1 · 9 + 3 · 4 + 1 · 6
= 3.(0 + 4 + 9 + 0 + 0 + 4) + 1.(7 + 2 + 7 + 2 + 9 + 6)
= 3.(7) + 1.(3)
=4
Como c · v 0 = 4 6= 0 em Z10 , então concluı́mos que houve algum erro.
Agora suponhamos que um determinado produto está identificado no sistema EAN-13,
por uma dada sequência de dı́gitos v = (v1 , v2 , . . . , v12 , d).
Os primeiros doze dı́gitos identificam o paı́s de origem, o fabricante e o produto especı́fico, e são determinados a cargo de uma autoridade classificadora em cada paı́s. Veja
a figura a seguir.
Figura 3.3: Explicação do código de barras utilizado em produtos
O décimo terceiro dı́gito, chamado de dı́gito de verificação utilizado para a detecção de erros, e será denotado por d. Denotaremos essa sequência como um vetor
α = (v1 , v2 , . . . , v12 , d). O sistema EAN − 13 utiliza o vetor de checagem ou vetor de
pesos c = (1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1).
A sistemática é a mesma do UPC, mudando apenas o número de dı́gitos do vetor que
representa o artigo.
Por exemplo, no caso do código da figura que segue, os números indicam o paı́s de
origem, o fabricante e o produto são 789500026624.
14
3. Códigos Detectores de Erros
Figura 3.4: Exemplo do código de barras utilizado atualmente
Vamos determinar o dı́gito de verificação d e fazendo o produto escalar com o vetor
de pesos, temos: 7 + (3.8) + 9 + (3.5) + 0 + (3.2) + 6 + (3.6) + 2 + (3.4) + d = 99 + d
Logo, deve-se ser d = 1, pois a soma acima deve ser múltiplo de 10. Se fosse qualquer
outro número de 0 a 9, não resultaria no múltiplo de 10 e então o computador avisaria
que um erro foi cometido.
Se mais de um erro for cometido na digitação, provavelmente será detectado, mas
isso não é garantido já que eles podem compensar mutuamente e a soma poderia ainda
continuar sendo um múltiplo de 10.
Veremos a função do vetor de pesos? Se a escolha do dı́gito de verificação fosse feita
para a soma das coordenadas de (v1 , v2 , . . . , v12 , d) ser múltiplo de 10, o que equivaleria
a considerar o vetor de pesos (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1), ainda poderia detectar um
erro. Acontece que há um outro tipo de erro de digitação muito comum, que consiste em
digitar todos os números corretamente, mas trocar a ordem de dois dı́gitos consecutivos.
Nesse caso o vetor (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) não detecta o erro. Logo, o sistema de
detecção acima não tem a capacidade de detectar todo erro de transposição cometido.
A transposição de dois dı́gitos vi e vi+1 não é detectada no EAN-13, se e somente se
|vi − vi+1 | = 5 (se vi é ı́mpar, tem-se a diferença com o sinal trocado).
ISBN(Intenational Standard Book Number)- Padrão Internacional de Numeração de Livros
O ISBN é um outro código de checagem de dı́gito, utilizado universalmente para a classificação de livros. É projetado para detectar mais tipos de erros que o UPC. O vetor
de código é um vetor em Z10
11 . As primeiras 9 componentes dão paı́s, editor e informação
sobre o livro e a décima componente é o dı́gito de checagem. Para o código ISBN, o vetor
de checagem ou vetor peso é
c = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
e a condição é que c.b = 0 em Z11 , ou seja, de que o produto escalar do vetor de código
pelo vetor de checagem seja múltiplo de 11. Sendo o vetor b = (v1 , v2 , v3 , . . . , v9 , d), temos:
c.b = 10.v1 + 9.v2 + 8.v3 + 7.v4 + 6.v5 + 5.v6 + 4.v7 + 3.v8 + 2.v9 + d
onde d é o dı́gito de checagem. Ou seja, d deve ser escolhido de modo que c.b seja
múltiplo de 11. Quando o dı́gito de checagem é 10, utiliza-se o numeral romano X em seu
lugar, pois é preferı́vel que cada componente de um ISBN seja um único dı́gito.
3.2. Aplicações de Códigos Detectores de Erros
15
Exemplo 3.5. Consideramos o ISBN a seguir que tem número igual a 85−244−0169−9.
O dı́gito de verificação final é 9, pois
Figura 3.5: ISBN
(8, 5, 2, 4, 4, 0, 1, 6, 9, 9).(10, 9, 8, 7, 6, 5, 4, 3, 2, 1) =
80 + 45 + 16 + 28 + 24 + 0 + 4 + 18 + 18 + 9 = 242, que é um múltiplo de 11.
Segundo Milies [5], autores como D.F. Beckley e J. Verhoeff investigaram os erros
cometidos por operadores humanos. Os erros num único dı́gito e as transposições são os
mais frequentes, atingindo cerca de 80%. A codificação apresentada aqui foi projetada
para detectar tais erros.
17
Capı́tulo 4
Códigos Corretores de Erros
Vamos estudar neste capı́tulo códigos corretores de erros, que permitem tanto detectar
como corrigir certos tipos de erros na transmissão ou armazenamento de dados. Para
entender como funcionam, vamos utilizar como exemplo, um robô que se move sobre um
tabuleiro quadriculado e que ao darmos um dos comandos (leste, oeste, norte, sul), o robô
se desloca de uma casa para a outra.
Os quatro comandos acima podem ser codificados como elementos de Z22 , como se
segue:
Leste →
7
Oeste →
7
00
01
Norte
Sul
7→
7→
10
11
Cada código que representa um dos comandos acima (00, 01, 10, 11) é chamado de
código da fonte. Suponhamos que os pares ordenados devam ser transmitidos via rádio
que pode sofrer interferências. Suponhamos que ao enviar a mensagem como 00 (ir para
leste), o robô recebeu a mensagem 01 (ir para oeste) o que faria com que fosse para oeste.
Para evitar que a mensagem seja um dos comandos existente, é necessário introduzir redundâncias na codificação para permitir detectar e corrigir erros. Então vamos introduzir
mais dı́gitos aos códigos que representam os comandos, como segue:
00
01
10
11
7→
7→
7→
7→
00000
01011
10110
11101
Na recodificação acima, as duas primeiras posições são o código da fonte e nas três
posições restantes são redundâncias introduzidas. Este novo código recodificado é chamado de código de canal. Como exemplo, suponhamos que tenha ocorrido um erro na
transmissão do código 10110 e que foi recebido 11110. O código recebido não corresponde
a nenhum dos códigos da tabela, portanto, detectamos erros. O código mais próximo
da mensagem válida, ou seja, o código da tabela que apresenta a menor quantidade de
dı́gitos distintos do código recebido é 10110, que é a palavra transmitida.
18
4. Códigos Corretores de Erros
Figura 4.1: Procedimento para transmissão de dados
O funcionamento dos códigos corretores do exemplo do robô é esquematizado a seguir:
O esquema acima exemplifica os códigos corretores de erros. Inicialmente, transformamos os dados a serem transmitidos em um código da fonte que é convertido num código de
canal, acrescentando-se redundâncias. Ao receber, detecta e corrige os erros e em seguida,
o código de canal é decodificado em código da fonte. Neste projeto serão estudados os
códigos, denominados códigos simétricos que apresentam as seguintes propriedades:
(a) Todos os sı́mbolos (dı́gitos) transmitidos têm a mesma probabilidade de serem recebidos errados e essa probabilidade é pequena;
(b) Se um sı́mbolo é recebido errado, a probabilidade de ser qualquer um dos outros
sı́mbolos é a mesma.
Agora vamos entender matematicamente como funciona o vetor de código e o processo
de geração de um código. Seja a nossa mensagem, um vetor x em Zk2 para algum k, e
iremos codificá-lo utilizando uma transformação por meio da matriz
T : Zk2 → Zn2 para algum n > k
T (x) será um vetor de código. Um código pode ser descrito através de uma transformação envolvendo matriz.
h
i
Exemplo 4.1. Seja G = 1 1 1 e definimos T : Z2 → Z32 por T (x) = Gt x
Onde elementos de Z2 são matrizes 1 × 1.
A matriz G é chamada de Matriz geradora do código.
Para checar se um vetor recebido é um código, precisamos

fazer duas verificações de
c1


paridade. Pela G, é necessário que o vetor recebido c =  c2  satisfaça c1 = c2 = c3
c3
2
Em Z , temos
4. Códigos Corretores de Erros

c = c
1
2
c = c
1
3
19

c + c = 0
1
2
=⇒
c + c = 0
1
3
"
#
1 1 0
Se P =
, então é equivalente a P · c = 0.
1 0 1
A matriz P é chamada de matriz de verificação de paridade para o código e p · c 6= 0
implica que houve erros." #
0
Observe que P Gt =
.
0
Para entender
 como
 funciona, vamos supor que enviamos uma mensagem codificada
1
 
como (1, 1, 1) =  1 
1
Suponha que ocorreu um erro na transmissão e recebemos c0 = (1, 0, 1) Logo,
 
"
#
"
# " #
1
1 1 0
1
+
0
·
1
+
0
·
1
1
 
P · c’ =
· 0  =
=
6= 0.
1 0 1
1+0·0+1·1
0
1
Logo, c’ não
" pode
# ser um vetor de código. Mas onde estará o erro? Podemos verificar
1
que P · c’ =
que é a segunda coluna da matriz de verificação de paridade P. Isso
0
significa que o erro está na segunda coordenada de c’, o que permite corrigir o erro,
invertendo 0 para 1.
Definição 4.2. Se k < n. Um código binário (n, k) dado como T : Zk2 → Zn2 é
h
i
dito de comprimento n e dimensão k. Uma matriz G = Ik A
, onde A é uma
k×n
matriz
h k × (n =ik) sobre Z2 é dito matriz geradora padrão para o código. Uma matriz
P = B In−k é dito matriz de verificação de paridade padrão.
G e P são associados ao código T : Z2k → Z2n quando T x = Gt x e P Gt x = 0 ∀x,
ou seja, P Gt = 0.
No teorema a seguir temos a condição para G ser a matriz geradora padrão para um
código binário de correção de erros e como encontramos uma matriz de verificação de
paridade padrão associada a P .
h
i
h
i
Teorema 4.3. Sejam G = Ik A e P = B In−k . P será a matriz de verificação
de paridade associada a matriz geradora padrão G se, e somente se, At = B. Além disso,
o código binário correspondente (n, k) será um corretor de erros (em uma componente)
se, e somente se, as colunas de P forem não nulas e distintas.
Demonstração. Chamamos ati a i-ésima linha de uma matriz A e bi , o i-ésima coluna de B.
Seja G uma matriz geradora padrão e P uma matriz de verificação de paridade. Vamos
assumir que as duas matrizes correspondem ao mesmo código binário. Portanto, para
todo x em Zk2 , P G x = 0. Usando a multiplicação por blocos temos:
20
4. Códigos Corretores de Erros
P Gt x =
h
B
I
i
"
I
At
#
x = 0 para todo x em Zk2
Ou seja,
h
B
I
i
"
I
At
#
x = (BI + IAt ) x = 0
Para todo x em Zk2 , temos
Bx + At x = 0 =⇒ Bx = −At x = At x
ou
Bx=Ax
Se agora tomarmos x = ei , o i-ésimo vetor de base canônica de Zk2 , vemos que
bi = B ei = At ei = ati para todo i
Portanto, B=At .
#
I
Reciprocamente, se B = At , PGt = B I
= B + At = 0 em Z2 . Agora,
t
A
veremos que se Pi forem não nulas e distintas, então é matriz de paridade para corretor
de erros, precisamos verificar que P detecta posição de erros. Seja x, a mensagem em Zk2
e c = Gx. Então terı́amos P c = 0. Se ocorrer um erro na i-ésima posição de c, o código
recebido seria c0 = c + ei. Então temos P c0 = P c + P ei = 0 + Pi que é a i-ésima coluna de
P . Como todas as coluna sde P são distintas (e não nulas) podemos identificar a posição
do erro.
h
i
"
Exemplo 4.4. Veremos um código corretor de erros que usa três equações para verificação
de paridade, que formam as linhas de P . Então temos n−k = 3 e logo k = n−3. Os vetores
da mensagem pertencem a Zk2 , e queremos que k (portanto n) seja o maior possı́vel para
transmitir mais informações. Pelo Teorema 4.3, as colunas de P precisam ser distintas e
não nulas. O máximo ocorre quando consistem em todos os 23 − 1 = 7 vetores não nulos
de Zn−k
= Z32 . Uma destas opções é
2

1 1 0

P= 1 0 1
0 1 1
1 1
1 0
1 0
0
1
0
Isso significa que

1

A= 1
0
e dessa forma, uma matriz geradora é
1 0
0 1
1 1

1

1 
1

0

0 
1
4.1. Matriz geradora e de teste de paridade no Matlab



G=


1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
1
1
0
1
1
0
1
1
1
21






4×7
Para exemplificar como a matriz geradora funciona, vamos considerar x = (0, 1, 0, 1) e
codificar como
c = G xt = (0, 1, 0, 1, 0, 1, 0)
Se esse vetor for recebido, será considerado correto, já que P c = 0. Agora, se for
h
iT
recebido c’ = 0 1 1 1 0 1 0
, então

1

0
P c = 1
0
1 0
0 1
1 1
1 1
1 0
1 0
0
1
0

0
h

0 · 0
1
1 1
1 0
1
0
it
=
h
0
1 1
it
h
i
Como P c0 6= 0, ocorreu um erro. Como o vetor é 0 1 1 , que é a terceira coluna
da matriz P . O erro está na terceira componente de c0 . Alterando essa componente,
recuperamos o vetor de código c. Como as quatro primeiras componentes de um vetor de
código são o vetor de mensagem original,podemos decodificar c e obtemos o vetor original
h
iT
x= 0 1 0 1
.
O código do exemplo 4.4 é chamado de código de Hamming (7,4). Em geral, todos os
códigos binários construı́dos dessa forma são chamados de código de Hamming (n, k), o
que veremos mais adiante. Um código de Hamming (n, k) tem n = 2n−k − 1.
4.1
Matriz geradora e de teste de paridade no Matlab
Vamos determinar a matriz geradora padrão (G) e a matriz de verificação de paridade
(H) para um código binário (7, 4), utilizando a função hammgen no Matlab. O parâmetro
de entrada é o fator r de desenho do código, tal que (n, k) = (2r − 1, 2r − 1 − r). A
" função
#
A
hammgen retorna, além das matrizes H e G definidas neste caso como G =
e
Ik
"
#
In−k
H=
, também os valores de n e k.
AT
No Matlab executamos a primeira linha, que tem como parâmetro de entrada apenas
r = 3, e os dados de saı́da são H, G e os valores de n e k.
No Matlab também podemos obter uma palavra de código, ou seja, um vetor de código
(código da fonte) acrescido de redundâncias introduzidas, chamadas de código de canal.
Para isso, multiplicamos o vetor de código pela matriz geradora G.
22
4. Códigos Corretores de Erros
4.2. Métrica de Hamming
23
Agora vamos introduzir um erro na palavra de código, trocando o segundo bit desta
através da soma com um padrão de erro. Em seguida, calculamos a sı́ndrome e verificamos
que é a segunda linha de H T , correspondendo ao padrão de erro somado à segunda
palavra.
4.2
Métrica de Hamming
Seja A um conjunto finito que daqui em diante será chamado de alfabeto. Um código
corretor de erros é um subconjunto próprio qualquer de An . Para ter a noção de proximidade entre palavras (sequência de alfabetos), veremos um modo de medir a distância
entre palavras.
Definição 4.5. Dados dois elementos u, v ∈ An , a distância de Hamming entre u e v é
definida como
d(u, v) = |{i : ui = vi , 1 ≤ i ≤ n}|.
Proposição 4.6. Dados u, v, w ∈ An , valem as seguintes propriedades:
(i) Positividade: d(u, v) ≥ 0 e d(u, v) = 0 ⇐⇒ u = v.
(ii) Simetria: d(u, v) = d(v, u).
(iii) Desigualdade Triangular: d(u, v) ≤ d(u, w) + d(w, v).
Logo, a distância de Hamming é uma métrica, também chamados de métrica de Hamming.
Definição 4.7. Seja C um código. A distância mı́nima de C é o número
24
4. Códigos Corretores de Erros
d = min{d(u, v) : u 6= v com u, v ∈ C e u 6= v }.
No exemplo do robô dado no inı́cio deste capı́tulo, se C é o código do robô, temos que
d = 3.
Definição 4.8. Dado a ∈ An e um número real t > 0, definimos o disco e a esfera de
centro em a e raio t como sendo
D(a, t) = {u ∈ An : d(u, a) ≤ t},
S(a, t) = {u ∈ An : d(u, a) = t}.
respectivamente.
A definição 4.8 pode ser representada da seguinte forma:
Figura 4.2: Representação do disco e da esfera de centro em a e raio t
Como consequência da definição 4.8 e desigualdade triangular, temos:
Lema 4.9. Seja C um código com distância mı́nima d. Se c e c0 são palavras distintas
de C, então
D(c, κ) ∩ D(c0 , κ) = ∅.
Teorema 4.10. Seja C um código com distância mı́nima d. Então C pode corrigir até
κ = b d−1
c erros e detectar até d − 1 erros.
2
Demonstração. Se ao transmitirmos uma palavra c do código cometermos t erros com
t ≤ κ, originando a palavra r, então d(r, c) = t ≤ κ. Pelo Lema 4.9, a distância de r
a qualquer outra palavra do código é maior do que κ. Isso determina c univocamente
a partir de r, como sendo o código mais próximo. Por outro lado, dada uma palavra
do código, podemos nela introduzir até d − 1 erros sem encontrar uma outra palavra do
código, e assim, a detecção do erro será possı́vel.
A tabela 4.1 apresenta as capacidades de detecção, correção e detecção e correção
simultâneas, em função da distância mı́nima, para alguns valores.
Analisando a tabela acima, verificamos que:
4.3. Códigos de Hamming
25
Tabela 4.1: Capacidades de detecção e correção de erros em função da distância mı́nima
d Detecção (l) Correção (t) Detecção e Correção simultâneas (l, t)
1
0
0
Não tem
2
1
0
Não tem
3
2
1
Não tem
4
3
1
(2,1)
5
4
2
(3,1)
(1) Apenas para d ≥ 4 é que se torna possı́vel a detecção e a correção em simultâneo;
(2) A capacidade de detecção é sempre superior à capacidade de correção;
(3) Um código com d = 1 não tem capacidade para detectar erros; por exemplo, considerando as 8 palavras do código binário natural a 3 bit, verifica-se que qualquer
alteração de um bit numa palavra vai produzir outra palavra que pertence ao código;
este erro é indetectável (as palavras de código são excessivamente semelhantes entre
si).
As capacidades de detecção e correção são obtidos à custa da introdução de redundâncias e dependem da distância mı́nima do código. Aumentar a distância mı́nima
melhora as capacidades de detecção e correção, mas em contrapartida diminui a aficiência
do código. Os critérios para determinação dos códigos de codificação de canal são:
(1) Dado o R, onde R é a medida da eficiência do código, maximizar d;
(2) Dada a d minimizar R.
Definição 4.11. Seja C ⊂ An um código com distância mı́nima d e seja κ = b d−1
c. O
2
código C será dito perfeito se
[
D(c, κ) = An .
c∈C
Um código C sobre um alfabeto A possui três parâmetros fundamentais [n, M, d], que
são, respectivamente, o seu comprimento (o número n corresponde ao espaço ambiente
An onde C se encontra), o seu número de elementos e a sua distância mı́nima.
4.3
Códigos de Hamming
Um código de Hamming de ordem m sobre F2 = Z2 é um código com matriz teste de
paridade Hm de ordem m × n, cujas colunas são os elementos de F2 m {0} numa ordem
qualquer.
26
4. Códigos Corretores de Erros
Temos que o comprimento de um código de Hamming de ordem m é n = 2m − 1 e a
sua dimensão é κ = n − m = 2m − m − 1. Como veremos no próximo capı́tulo, podemos
converter a matriz geradora de verificação de paridade na forma padrão. Considere a
matriz


1 0 1 1 1 0 0


H3 =  1 1 0 1 0 1 0  .
0 1 1 1 0 0 1
Essa é a matriz de um código de Hamming (matriz de verificação de paridade) correspondente a m = 3.
Proposição 4.12. Todo código de Hammming é perfeito.
4.4
Decodificação
A decodificação é o procedimento de detecção e correção de erros num determinado código.
Define-se o vetor erro e como sendo a diferença entre o vetor recebido r e o vetor transmitido c, isto é,
e=r−c
Exemplo 4.13. Suponha que num código dado sobre F2 , tenhamos transmitido a palavra
(010011) e foi recebido a palavra recebida tenha sido (101011), então
e = (101011) − (010011) = (111000).
O peso do vetor erro corresponde ao número de erros cometidos durante a transmissão.
Seja H a matriz teste de paridade do código, chamamos Hv de sı́ndrome de v. Como
Hc = 0, temos que
Het = H(r − c) = Hr − Hc = Hr.
Portanto, a palavra recebida e o vetor erro têm mesma sı́ndrome.
Lema 4.14. Seja C um código linear em K n com capacidade de correção κ. Se r ∈ K n
e c ∈ C são tais que d(c, r) ≤ κ então existe um único vetor e com ω(e) ≤ κ, tal que a
sı́ndrome é igual à sı́ndrome de r. Além disso, que c = r − e.
Cada conjunto da forma v + C é chamado de classe lateral de v segundo C. Note que
v + C = C ⇐⇒ v ∈ C.
Lema 4.15. Os vetores u e v de K n têm a mesma sı́ndrome se, e somente se, u ∈ v + C.
4.5. Algoritmo da Decodificação
27
Definição 4.16. Um vetor de peso mı́nimo numa classe lateral é chamado de elemento
lı́der dessa classe.
4.5
Algoritmo da Decodificação
(1) Calcule a sı́ndrome s = Hr.
(2) Se s está na tabela de cálculo das sı́ndromes, seja l o elemento lı́der da classe
determinada por s; troque r por r − l.
(3) Se s não está na tabela de cálculo das sı́ndromes, então mensagem recebida foram
cometidos mais do que κ erros.
Exemplo 4.17. Considere o código linear (6, 3) definido sobre F2 com matriz teste de
paridade
H=


1 0 1 1 0 0


 1 1 0 0 1 0 .
0 1 1 0 0 1
Neste caso d = 3 e, portanto, κ = b d−1
c = 1.
2
Os vetores de peso ≤ 1 com suas respectivas sı́ndromes estão relacionados abaixo
Lı́der Sı́ndrome
000000
000
000001
001
000010
010
000100
100
001000
101
010000
011
100000
110
Suponhamos, agora, que a palavra recebida seja
(a) r = (100011). Logo, S = Hr = (101) e, portanto, e = (001000). Consequentemente, c = r − e = (101011).
(b) r = (111111). Logo, S = Hr = (111), que não se encontra na tabela. Sendo
assim, foi cometido mais do que 1 erro na mensagem r.
28
4.6
4. Códigos Corretores de Erros
Distâncias Mı́nimas e Corretores de Erros Geometricamente
Seja C um código de tripla repetição, temos um subconjunto de Z32 . Podemos representar
os vetores de Z32 como vértices de um cubo unitário (figura 4.3(a)). A distância de
Hamming entre quaisquer dois vetores x e y é só o caminho mais curto para ir de x até
y, passando pelas arestas. O código C corresponde a dois desses vértices, c0 = 000 e
c1 = 111. O fato de d(C) = 3 corresponde ao fato de c0 e c1 estarem a três unidades
(arestas) um do outro (figura 4.3(b)). Se um vetor recebido x estiver ao máximo de uma
unidade de algum desses vetores-códigos e soubermos que ocorreu no máximo um erro,
poderemos corretamente decodificar x como o vetor-código mais próximo. Em geral, não
podemos desenhar figuras de Zn2 .
Figura 4.3: Representação geométrica dos códigos corretores de erros
Considere um código que pode corrigir até κ erros e os vetores-código nos centros
das esferas de raio κ. Os vetores-código estão separados um dos outros por pelo menos
d unidades. Se um vetor recebido x estiver no interior de uma dessas esferas, ele será
decodificado como o vetor correspondente ao centro daquela esfera (veja a figura 4.4).
Figura 4.4: Representação esférica dos códigos corretores de erros
Esse processo é conhecido como decodificador pelo vizinho mais próximo. A figura
sugere que se um código é capaz de corrigir κ erros, então as “esferas” centradas nos
vetores-código não podem ser tocadas nem sobrepostas, tendo-se d > 2κ.
29
Capı́tulo 5
Códigos Lineares
Neste capı́tulo apresentaremos a classe de códigos denominada de Códigos Lineares.
Definição 5.1. Um código C ⊂ K n será chamado de código linear se for um subespaço
vetorial de K n .
O código do robô citado anteriormente, por exemplo, é um código linear, pois o alfabeto nesse caso é A = F2 , o código é o subespaço vetorial de F52 , que é a imagem da
transformação linear
T :
→
F52
F22
(x1 , x2 ) 7→ (x1 , x2 , x1 , x1 + x2 , x2 )
Pela definição, todo código linear é um espaço vetorial de dimensão finita. Seja κ a
dimensão do código C e seja {v1 , v2 , . . . , vκ } base C, portanto, todo elemento de C se
escreve de modo único na forma
λ1 v 1 + λ 2 v 2 + · · · + λ κ v κ
onde os λi , i = 1, . . . , κ, são elementos de K. Segue daı́ que
M = |C| = q κ
e, consequentemente,
dimK C = κ = logq q κ = logq M.
Definição 5.2. Dado x ∈ K n , define-se o peso de x como sendo o número inteiro
ω(x) := |{i : xi 6= 0} | = d(x, 0)
30
5. Códigos Lineares
onde d representa a métrica de Hamming.
Definição 5.3. O peso de um código linear C definido como inteiro
ω(C) := min{ω(x) : x ∈ C {0}.
Proposição 5.4. Seja C ⊂ K n um código linear com distância mı́nima d. Temos que
(i) ∀x, y ∈ K n , d(x, y) = ω(x − y).
(ii) d = ω(C).
Devido o item ii da Proposição 5.4, a distância mı́nima de um código linear C será
também chamada de peso do código C. Em álgebra linear, existem duas maneiras práticas
de descrever subespaços vetoriais: uma como imagem, e outra como núcleo de transformações lineares. Veremos como se obtém a representação de C como imagem. Escolhemos uma base v1 , v2 , . . . , vκ de C e considere a aplicação linear
T :
Kκ
→
Kn
x = (x1 , x2 , . . . , xκ ) 7→ (x1 v1 + x2 v2 + · · · + xκ vκ )
Então T é uma transformação linear injetora, cuja imagem é C.
Portanto, ter um código C ⊂ K n de dimensão κ é equivalente a ter uma transformação
linear injetora
T : Kκ → Kn
com C = Im(T ).
Ele é denominado de forma paramétrica, pois os elementos de C são parametrizados
pelos elementos x de K κ . Agora veremos como representar como núcleo da transformação
linear. Tome um subespaço C 0 de K n complementar de C, isto é,
C ⊕ C 0 = K n,
e considere a aplicação linear
H : C ⊕ C 0 → K n−k
u ⊕ v 7→
v
5.1. Equivalência de Códigos
31
Então o núcleo é C. Para saber se c ∈ C, basta verificar se Hv = 0, o que tem custo
computacional bem pequeno.
Exemplo 5.5. Considere o corpo finito F3 = {0, 1, 2} = Z3 com três elementos e seja
C ⊂ F43 , o código gerado pelos vetores v1 = 1011 e v2 = 0112. Esse código possui
9(= q κ = 32 ) elementos, por ter dimensão 2 sobre um corpo de 3 elementos. Uma
representação paramétrica é dada por
x1 v1 + x2 v2
O código C é o núcleo da transformação linear
H:
5.1
F43
→
F23
x = (x1 , . . . , x4 ) 7→ (2x1 + 2x2 + x3 , 2x1 + x2 + x4 )
Equivalência de Códigos
A noção de equivalência de códigos usa o conceito de isometria.
Definição 5.6. Sejam A um alfabeto e n um número natural. Diremos que uma função
F : An → An é uma isometria de An se ela preserva a distância de Hamming. Em
sı́mbolos:
d(F (x), F (y)) = d(x, y) ∀ x, y ∈ An .
Algumas propriedades conhecidas da isometria são:
Proposição 5.7.
1. Toda isometria é uma bijeção.
2. A função identidade é uma isometria.
3. Se F é uma isometria, então F −1 é uma isometria.
4. Se F e G são isometrias, então F ◦ G é uma isometria.
Dado a permutação π de {1, . . . , n}, denotemos Tπ (a1 , . . . , an ) = (aπ(1) , . . . , aπ(n) ). Se
f : A =⇒ A é bijeção, definimos Tfi (a1 , . . . , an ) = (a1 , . . . , f (ai ), . . . , an ).
Definição 5.8. Dados dois códigos C e C 0 em An , diremos que C 0 é equivalente a C se
existir uma isometria F de An tal que F (C) = C 0 .
O estudo mais aprofundado sobre a isometria costuma ser feita em livros sobre espaços
métricos.
32
5. Códigos Lineares
Teorema 5.9. Seja F : An → An uma isometria, então existem uma permutação π de
{1, . . . , n} e bijeções fi de A, i = 1, . . . , n, tais que
F = Tπ ◦ Tf11 ◦ · · · ◦ Tfnn .
Corolário 5.10. Sejam C e C 0 dois códigos em An . Temos que C e C 0 são equivalentes
se, e somente se, existem uma permutação π de {1, . . . , n} e bijeções f1 , . . . , fn de A tais
que
C 0 = {(fπ(1) (xπ(1) ), . . . , fπn (xπ(n) )) : (x1 , . . . , xn ) ∈ C}.
Definição 5.11. Seja K um corpo finito. Dois códigos lineares C e C 0 são linearmente
equivalentes se existir uma isometria linear T : K n → K n tal que T (C) = C 0 .
Pelo Teorema 5.9, segue que dois códigos lineares C e C 0 em K n são linearmente equivalentes se, e somente se, existir uma permutação π de {1, . . . , n} e elementos c1 , . . . , cn
de K\{0} tais que
C 0 = {(c1 xπ(1) , . . . , cn xπ(n) ) : (x1 , . . . , xn ) ∈ C}.
Logo, dois códigos são linearmente equivalentes se, e somente se, cada um deles pode
ser obtido do outro por uma sequência de operações do tipo:
i. Multiplicação dos elementos numa dada posição por um escalar não nulo.
ii. Permutação das posições das palavras do código, por uma permutação de
{1, 2, . . . , n} aplicado em todas as palavras do código.
5.2
Matriz Geradora de um Código
Sejam K um corpo finito com q elementos e C ⊂ K n um código linear. Denominamos
parâmetros do código linear C à terna de inteiros (n, κ, d), onde κ é a dimensão de C
sobre K, e d representa a distância mı́nima de C (que é igual ao peso ω(C)). O número
de elementos M de C é igual a q κ . Seja β = {v1 , . . . , vκ } uma base ordenada de C e
considere a matriz G, cujas linhas são os vetores vi = (vi1 , . . . , vin ), i = 1, . . . , κ, isto é,

 
v1
 .  
.  
G=
 . =
vk

v11 v12 · · · v1n
..
.. . .
.. 
.
.
.
. 

vk1 vk2 · · · vkn
A matriz G é chamada de matriz geradora de C associada à base β. Considere a transformação linear definida por
5.2. Matriz Geradora de um Código
33
T : Kκ →
Kn
x 7→ (x1 v1 + · · · + xκ vκ ),
Então T (K κ ) = C. Podemos, então, considerar K κ como sendo o código da fonte, C, o
código de canal e a transformação T , uma codificação.
Duas matrizes geradoras de um mesmo código C podem ser obtidas uma da outra por
uma sequência de operações do tipo:
(L1) Permutação de duas linhas.
(L2) Multiplicação de uma linha por um escalar não nulo.
(L3) Adição de um múltiplo escalar de uma linha a outra.
Que são as operações elementares usadas no processo de escalonamento.
Também podemos construir códigos a partir de matrizes geradoras G. Para isso, tome
uma matriz cujas linhas são linearmente independentes e defina um código como sendo a
imagem da transformação linear
T : Kκ → Kn
x 7→ Gt x
Exemplo 5.12. Tome K = F2 = Z2 e seja


1 0 1 0 1


G =  1 1 0 1 0 .
1 1 1 1 1
Considerando a transformação linear
T : F32 → F52
x 7→ Gt x
e seja C = Im(T ), o código associado, por exemplo,a palavra 101 do código da fonte
é codificada como 01010. Suponhamos agora que seja dado o código de canal 10101, e
que gostarı́amos de decodificá-la, isto é, achar x de F32 tal que 10101 = T (x). Então
precisamos resolver o sistema:


 

x1
 
T 
G  x2  = 


x3

1
0
1
0
1








34
5. Códigos Lineares
(x1 , x2 , x3 )G = (10101),
ou seja,


x1 + x2 + x3





 x2 + x3
x1 + x3



x2 + x3




x1 + x3
=
=
=
=
=
1
0
1
0
1,
Logo x1 = 1, x2 = 0 e x3 = 0.
Observe que efetuando operações sobre as linhas de G do tipo L1, L2 e L3, podemos
converter G na forma


1 0 0 0 0


G0 =  0 1 0 1 0  .
0 0 1 0 1
que é a forma padrão. Nesta forma, temos que G0T x = (x1 , x2 , x3 , x2 , x3 )
xG0 = (x1 x2 x3 x2 x3 )
Assim, o vetor x é apenas as três primeiras componentes do vetor a ser decodificado.
Logo, a palavra (10101) é facilmente decodificada como (101).
Definição 5.13. Diremos que uma matriz geradora G de um código C está na forma
padrão se tivermos
G = (Idκ |A),
onde Idκ é a matriz κ × κ e A, uma matriz κ × (n − κ).
Dado um código C, nem sempre é possı́vel obter uma matriz geradora de C na forma
padrão.
Exemplo 5.14. O código em F52 com matriz geradora
0 0 1 0 1
0 0 0 1 1
!
não poderá ter uma matriz geradora na forma padrão.
5.3. Códigos Duais
35
Mas se efetuar também as permutações nas colunas, podemos obter a matriz
1 0 0 0 1
0 1 0 0 1
!
,
que é a matriz geradora na forma padrão de novo código C 0 equivalente a C.
De modo geral, além das operações nas linhas, efetuamos também sequências de
operações sobre as colunas do tipo:
(C1) permutação de duas colunas,
(C2) multiplicação de uma coluna por um escalar não nulo,
obtemos uma matriz G0 de um código C 0 equivalente a C. Com isso, temos o seguinte
resultado:
Teorema 5.15. Dado um código C, existe um código equivalente C 0 com matriz geradora
na forma padrão.
5.3
Códigos Duais
Seja C ⊂ K n um código linear, definimos o código dual como complemento ortogonal.
C ⊥ = {v ∈ K n : hu, vi = 0, ∀u ∈ C}.
As propriedades do complemento ortogonal costuma ser tratado no texto de álgebra
linear.
Lema 5.16. Se C ⊂ K n é um código linear, com matriz geradora G, então
i) C ⊥ é um subespaço vetorial de K n ;
ii) x ∈ C ⊥ ⇐⇒ Gx = 0.
Proposição 5.17. Seja C ⊂ K n um código de dimensão κ com matriz geradora na forma
G = (Idκ |A). Então
i) dimC ⊥ = n − κ;
ii) H = (−A|Idn−κ ) é uma matriz geradora de C ⊥ .
Lema 5.18. Seja C um código linear em K n . Para toda permutação σ de {1, . . . , n},
para todo c ∈ K ∗ e para todo j = 1, . . . , n temos que
36
5. Códigos Lineares
i) (Tσ (C))⊥ = Tσ (C ⊥ )
ii) (Tcj (C))⊥ = Tcj−1 (C ⊥ )
Proposição 5.19. Sejam C e D dois códigos lineares em K n que são linearmente equivalentes, então C ⊥ e D⊥ são linearmente equivalentes.
Lema 5.20. Suponha que C seja um código de dimensão κ em K n com matriz geradora
G. Uma matriz H de ordem (n − κ) × n, com coeficientes em K e com linhas linearmente
independentes, é uma matriz geradora de C ⊥ se, e somente se,
GH t = 0.
Proposição 5.21. Seja C um código linear e suponhamos que H seja uma matriz geradora de C ⊥ . Temos então que
v ∈ C ⇐⇒ Hv = 0.
Isto significa que H é matriz teste de paridade.
Exemplo 5.22. Seja dado o código C sobre F2 com matriz geradora


1 0 0 1 1 1


G =  0 1 0 0 1 1 .
0 0 1 0 1 0
Como G está na forma padrão, podemos usar a Proposição 5.17 (ii) e ter a matriz teste
de paridade


1 0 0 1 0 0


H =  1 1 1 0 1 0 .
1 1 0 0 0 1
Dados v = (100111) e v 0 = (010101), como


 
0
1
 
 
0
Hv =  0  e Hv =  1  =
6 0,
0
0
temos que v ∈ C e v 0 ∈
/ C.
A matriz teste de paridade de um código contém, de maneira bastante simples, informações sobre o valor do peso do código.
Teorema 5.23. Seja H a matriz teste de paridade de um código C. Então o peso de C é
igual a s se, e somente se, quaisquer s − 1 colunas de H são linearmente independentes.
5.4. Códigos de Reed-Muller
37
Corolário 5.24. (Cota de Singleton) Os parâmetros (n, κ, d) de um código linear satisfazem à desigualdade
d ≤ n − κ + 1.
Um código será chamado de MDS (Maximum Distance Separable) se valer a igualdade
d = n − κ + 1.
5.4
Códigos de Reed-Muller
Relembrando que os códigos de Reed-Muller foi usado pela sonda espacial Mariner 9 para
transmitir fotos de Marte. Para ser transmitida, cada fotografia foi dividida em elementos
pictográficos, ou pixels. Foi sobreposta à fotografia uma grade de 700 × 832 pixels, e en
seguida associou-se a cada pixel um entre 64 tons de cinza, variando de brando (0) a preto
(63). Sabendo que 64 = 26 , usamos aritmética binária para representar cada uma dessas
tonalidades, onde o branco é 000000 e o preto é 111111. Podemos, então, reescrever esses
64 números binários como vetores de Z62 e codificá-los usando um código que corrija tantos
erros quanto possı́vel. O código escolhido para ser usado no Mariner 9 pertence a uma
grande famı́lia de códigos que são mais facilmente definidos intuitivamente.
Definição 5.25. Os códigos de Reed-Muller (de primeira ordem) Rn são definidos indutivamente por:
1 Para n = 0, R0 = Z2 .
2 Para n ≥ 1, Rn é o subespaço de Z2n
2 cuja base é formada por todos os vetores da forma
"
u
u
#
"
e
0
1
#
, e 1 é o vetor formado
onde u é o vetor da base em Rn−1 , 0 é o vetor nulo de Z2n−1
2
2n−1
por 1s em Z2 .
Usando a definição acima, construiremos R1 e R2 , e verificaremos o tipo de vetores
que esses códigos contêm. Uma base para R0 = Z2 é somente {1}, portanto, uma base
para R1 é
("
1
1
# "
,
0
1
#)
que gera o código
Não há como obter mais nenhum outro vetor através da adição e por isso
38
5. Códigos Lineares
("
R1 =
0
0
# "
,
0
1
# "
,
1
0
# "
,
#)
1
1
= Z22
Realizando o mesmo procedimento obterı́amos a seguinte base para R2
     

1
0
0 











 1   1   0 

 , , 
 1   0   1 


     




 1
1
1 
e pela propriedade do
R2 são
  

0





 0 
 


R2 =   , 



 0  


 0
fechamento para a adição, é fácil ver que os 8 = 23 vetores de
0
0
1
1
 
 
 
,
 
 
0
1
0
1
 
 
 
,
 
 
0
1
1
0
 
 
 
,
 
 
1
0
1
0
 
 
 
,
 
 
1
0
0
1
 
 
 
,
 
 
1
1
0
0
 
 
 
,
 
 
1
1
1
1












Em R1 todo vetor de código tem peso 1, exceto 0 e 1;e, em R2 todo vetor de código
tem peso 2, exceto 0 e 1. Essa é uma propriedade geral dos códigos de Reed-Muller.
Observação 5.26. O complemento de um vetor x de Zn2 é o vetor de x obtido trocando-se
todos os zeros por 1s, e vice-versa.
Exemplo 5.27.



x=


1
1
0
1






 ⇐⇒ x = 




0
0
1
0






Observe que x = x + 1, onde 1 é o vetor formado inteiramente de 1s.
Teorema 5.28. Para n ≥ 1, o código de Reed-Muller Rn é um código linear (2n , n + 1)
no qual todo vetor de código, exceto o 0 e o 1, tem peso 2n−1 .
Demonstração. Para demonstrar esse teorema vamos utilizar indução em n. Para n = 1
temos que R1 = Z22 é um código linear (2, 2) = (21 , 1+1) para o qual todo vetor de código,
exceto o 0 e o 1, tem peso 1 = 21−1 . Vamos assumir que o resultado é válido para n = k,
ou seja, que Rk é um código linear (2k , k + 1) no qual todo vetor de código, exceto o 0 e
o 1, tem peso 2k−1 . Agora, consideremos Rk=k+1 .
"
#
u
Por construção, Rk+1 tem uma base formada pelos vetores da forma
, onde u é
u
"
#
0
um elemento de Rk , juntamente com o vetor
. Pela hipótese de indução, os vetores
1
5.5. Decodificação de Códigos de Reed-Muller
39
2k+1
u, 0 e 1 estão em Z2k
2 ; assim os vetores da base para Rk+1 estão em Z
"2 .# Além disso,
u
a dimensão de Rk é k + 1, pprtanto, existem k + 1 vetores da forma
e mais um,
u
"
#
0
. Segue que a dimensão de Rk+1 é k + 2.
1
Finalmente observemos que Rk+1 é um código linear (2k+1 , k + 2). Para a afirmação
final, observe que os vetores de Rk+1 são obtidos por combinação linear dos vetores da
base, e, portanto, são da forma
"
#
"
#
"
#
u1
uk+1
0
v = c1
+ . . . +ck+1
+ ck+2
u1
uk+1
1
onde {u1 , . . . , uk+1 } com ci ∈ Z2 .
Suponha que v 6= 0, 1 e seja u = c1 u1 + . . . + ck uk+1 . Dessa forma, u é um elemento
de Rk . Se ck+2 =0, então u 6= 0, 1, e, portanto, pela hipótese de indução, u tem peso 2k−1 .
Mas então v tem peso 2 · 2k−1 = 2k . Se ck+2 = 1, então v tem a forma
"
# "
# "
# "
#
u
0
u
u
v=
+
=
=
u
1
u+1
u
onde u é um elemento de Rk . Como
w(u) = 2k - w(u)
temos que
w(v) = w(u) + w (u) = 2k
como querı́amos demonstrar. Logo, o teorema é verdadeiro para todo n ≥ 1.
Sabemos da introdução desta seção que o Mariner 9 requeria um código com 64 = 26
vetores. Pelo teorema 5.28, o código de Reed-Muller R5 tem dimensão 6 sobre Z2 .
5.5
Decodificação de Códigos de Reed-Muller
Definição 5.29. Uma matriz Hn de ordem n é uma matriz n × n formada pelos valores
1 e −1, cujas linhas tomadas duas a duas são ortogonais.
Isto significa que o produto interno sobre os números reais de linhas distintas é 0.
No caso de dimensão
" ser potências
# de dois, podemos obter recursivamente por
Hn Hn
H1 = [1] e H2n =
Hn −Hn
Exemplo 5.30. Matrizes de Hadamard de ordem 1, 2 e 4 são dadas por
40
5. Códigos Lineares

"
H1 = [1]
H2 =
1 1
1 -1
#


H4 = 


1
1
1
1
1
-1
1
-1
1
1
-1
-1
1
-1
-1
1






Uma definição equivalente é Hn é uma matriz n × n com a entrada dos inteiros 1 e −1
tais que
Hn HnT = nIn
Definição 5.31. A ordenação adequada Pr de r-uplas é a ordenação definida recursivamente pelas regras
(1) P1 = [0, 1]
(2) Se Pi = [b1 , b2 , . . . , b2i ] então Pi+1 = [b1 0, b2 0, . . . , b2i 0, b1 1, b2 1, . . . , b2i 1], para 1 ≤ i ≤
r − 1.
Se inverter a ordem dos digitos, a ordenação acima é a ordem crescente dos números
binários associados.
Exemplo 5.32.
P1 = [0, 1]
P2 = [00, 10, 01, 11]
P3 = [000, 100, 010, 110, 001, 101, 011, 111]
Note que, se inverter a ordem dos dı́gitos, o P3 corresponde a
[000, 001, 010, 011, 100, 101, 110, 111] que é ordem crescente dos números binários
associados.
Agora seja n = 2r , e sejam u0 , u1 , . . . , un−1 os r-uplas binárias numa ordem correta.
Construção da matriz geradora de código
Seja Hr , a matriz de verificacao de paridade de Hamming(que não pode ser confundida
com matriz de Hadamard). Considere [Hr 0], onde 0 é uma matriz coluna nula. Br é uma
matriz ordenada de [Hr 0] segundo a ordenação
da definição 5.31. Então a matriz geradora
#
"
1
de código de Reed-Muller R(1, r) é G =
Br
ri
 Seja r o código recebido. Construı́mos o vetor R tal que Ri = (−1) =
1, se r = 0
i
−1, se r = 1
i
Agora, obtemos o vetor R̂ = HR. Seja k, a coordenada do maior valor absoluto de
R̂ e considere o vetor u da k-ésima coordenada de Br (ordenada). O código de canal é
P
c = ui vi onde vi é a i-ésima linha de Br .
5.5. Decodificação de Códigos de Reed-Muller
41
Exemplo

1 0 1

1 1 0
0 1 1
5.33. R(1, 3).
Matriz geradora do código de Hamming será H3 =



1 1 0 0
1 0 1 1 1 0 0 0



1 0 1 0 e [H3 0] = 1 1 0 1 0 1 0 0.
1 0 0 1
0 1 1 1 0 0 1 0


0 1 0 1 0 1 0 1


Reordenando, temos B3 = 0 0 1 1 0 0 1 1 e consequentemente, a matriz
0 0 0 0 1 1 1 1


1 1 1 1 1 1 1 1


0 1 0 1 0 1 0 1 


geradora do código será B3 = 

0
0
1
1
0
0
1
1


0 0 0 0 1 1 1 1
Suponha
 que foi recebido r = (01110110). Amatriz de Hadamard de ordem 8 é
1 1
1
1
1
1
1
1


1 −1 1 −1 1 −1 1 −1


1 1 −1 −1 1
1 −1 −1




1 −1 −1 1

1
−1
−1
1

H8 = 
1 1
1
1 −1 −1 −1 −1




1 −1 1 −1 −1 1 −1 1 


1 1 −1 −1 −1 −1 1
1


1 −1 −1 1 −1 1
1 −1
Se r = (01110110) então R = (1, −1, −1, −1, 1, −1, −1, 1), calculamos R̂ = HR. No
nosso exemplo, R̂ = (−2, 2, 2, 6, −2, 2, 2, −2).
Encontre a coordenada que tem o maior
valor absoluto. No exemplo, é k = 4, pois R̂4 = 6.
Considere
vetor u como a k-ésima coluna de Br . Nosso exemplo, será a quarta coluna
 o
1
 
que é u =  1 
0
P
c=
ui vi onde vi é a i-ésima linha de G.
Então c = 1v1 + 1v2 + 0v3 = [01010101] + [00110011] = [01100110] = (01100110).
Temos que o código da fonte é u ∈ Z42 com GT u = c. Logo, u = (0, 1, 1, 0).
43
Referências Bibliográficas
[1] GARCIA, A. e LEQUAIN, Y. Elementos de Álgebra. IMPA, Rio de Janeiro, 2006.
326p.
[2] GONÇALVES, A. Introdução à Álgebra. IMPA, Rio de Janeiro, 1979. 194p.
[3] HEFEZ, A.; VILLELA, M.L.T. Códigos Corretores de Erros. Série de Computação
e Matemática. Rio de janeiro: IMPA, 2002. 217p.
[4] LOURENÇO, M. L.; COELHO, F. U.Um curso de Álgebra Linear. EDUSP, São
Paulo, 2005. 261p.
[5] MILIES, C. M. A Matemática dos códigos de barras: detectando erros. RPM 65.
p.38-42.
[6] POOLE, D. Álgebra Linear. São Paulo: Pioneira Thomson Learning, 2004. 690p.
[7] VANSTONE, S. A. e OORSCHOT, P. C.van. An Introduction to Error Correcting
Codes with Applications. Kluwer Academic Publishers, 1989. 289p.