UNIVERSIDADE ESTADUAL DE SANTA CRUZ
DEPARTAMENTO DE CIÊNCIAS EXATAS E
TECNOLÓGICAS
UMA INTRODUÇÃO À TEORIA DOS CÓDIGOS
CORRETORES DE ERROS
Liliane Xavier Neves
Ilhéus, Bahia
2003
Liliane Xavier Neves
UMA INTRODUÇÃO À TEORIA DOS CÓDIGOS
CORRETORES DE ERROS
Monografia apresentada à Disciplina Seminário em
Matemática do Departamento de Ciências Exatas
e Tecnológicas – DCET, da Universidade Estadual de Santa Cruz – UESC, como um dos prérequisitos para obtenção do grau de Bacharelado
em Matemática.
Ilhéus, Bahia
2003
Liliane Xavier Neves
UMA INTRODUÇÃO À TEORIA DOS CÓDIGOS
CORRETORES DE ERROS
Monografia apresentada, julgada e aprovada pelo Corpo Docente do
Departamento de Ciências Exatas e Tecnológicas da Universidade
Estadual de Santa Cruz como parte dos requisitos de conclusão do curso
de Bacharelado em Matemática.
Jaime Edmundo Apaza Rodriguez, Dr.
Orientador
Eurivalda Ribeiro dos Santos Santana, Msc.
José Reis Damaceno Santos, Msc.
Ilhéus, Bahia
2003
A meus pais, minhas irmãs pelo apoio e compreensão.
Agradeço de coração por todo amor, carinho e
confiança que depositaram em mim.
AGRADECIMENTOS
Agradeço a Deus, fonte que me abasteceu de fé para nunca desistir.
Agradeço também ao meu orientador e amigo Jaime Edmundo Apaza Rodrigues pelas palavras de incentivo e por me fazer descobrir uma área tão
fascinante da Matemática, área essa pela qual me apaixonei.
RESUMO
Neste trabalho apresentamos uma introdução à teoria dos Códigos Corretores de Erros, que é um campo da chamada matemática aplicada muito
usada hoje em dia, basicamente na área de transmissão de informação (em
qualquer uma de suas modalidades), e que usa fortemente conceitos e resultados abstratos da matemática pura (especialmente da álgebra abstrata).
São apresentados alguns tipos de códigos como os lineares, os de Hamming,
os de Reed-Solomon, os cı́clicos e algumas das suas propriedades.
ABSTRACT
In this monograph we are studying an introduction to error corrector
theory that is an field the mathematic applied very used today, principally
in the information transmission (in different forms) and where we are used
notions and results of pure mathematic, especially of abstract algebra. We
are studying some kinds of codes as soon linear codes, Hamming codes,
Reed-Solomon codes, ciclic codes and some properties.
Índice
1 Introdução
2
2 Códigos Corretores de Erros
5
3 Códigos Lineares
8
3.1
Códigos Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2
Matriz Geradora de um Código . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3
Códigos Duais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4
Exemplos de Códigos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5
Decodificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Códigos Cı́clicos
30
4.1
Códigos Cı́clicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2
Decodificação em códigos cı́clicos . . . . . . . . . . . . . . . . . . . . . . . 36
Bibliografia
40
2
1
Introdução
A Teoria dos Códigos Corretores de Erros foi fundada pelo matemático Claude Eloowd
Shannon, num trabalho publicado em 1948. Inicialmente, os maiores interessados nessa
teoria foram os matemáticos que a desenvolveram consideravelmente nas décadas de 50 e
60. A partir da década de 70, com as pesquisas espaciais e a grande popularização dos
computadores, essa teoria começou a interessar também aos engenheiros.
Hoje, os códigos corretores de erros participam do nosso cotidiano de inúmeras formas,
estando presentes, por exemplo, sempre que fazemos uso de informações digitalizadas,
tais como assistir a um programa de televisão, falar ao telefone, ouvir um CD de música,
assistir a um filme em DVD, mandar um recado para alguém via pager ou navegar pela
internet.
Um código corretor de erros é, em essência, um modo organizado de acrescentar algum
dado adicional a cada informação que se queira transmitir ou armazenar e, que permita,
ao recuperar a informação, detectar e corrigir erros.
Façamos dois exemplos para ilustrar os princı́pios dessa teoria.
1) Suponhamos que temos um robô que se move sobre um tabuleiro quadriculado, de
modo que, ao darmos um dos comandos (Leste, Oeste, Norte ou Sul), o robô se desloca
do centro de uma casa para o centro de uma casa contı́gua indicada pelo comando.
Os quatro comandos acima podem ser codificados como elementos do conjunto {0, 1} ×
{0, 1}, como se segue:
Leste −→ 00
N orte −→ 10
Oeste −→ 01
Sul −→ 11
O código do lado direito da tabela é chamado código da fonte. Suponhamos, agora,
que esses pares ordenados devam ser transmitidos via rádio e que o sinal no caminho sofra
interferências. Imaginemos que a mensagem 00 possa, na chegada, ser recebida como 01,
o que faria com que o robô, em vez de ir para Leste, fosse para Oeste. O que se faz, então,
é recodificar as palavras, de modo a introduzir redundâncias que permitam detectar e
3
corrigir erros. Podemos, por exemplo, modificar o nosso código como se segue:
00 −→ 00000
01 −→ 01011
10 −→ 10110
11 −→ 11101
Nessa recodificação, as duas primeiras posições reproduzem o código da fonte, enquanto
que as três posições restantes são redundâncias introduzidas. O novo código introduzido
na recodificação é chamado de código de canal. Suponhamos que se tenha introduzido
um erro ao transmitirmos, por exemplo, a palavra 10110, de modo que a mensagem recebida seja 11110. Comparando essa mensagem com as palavras do código, notamos que
não lhe pertence e, portanto, detectamos erros. A palavra do código mais próxima da
referida mensagem (a que tem menor número de componentes diferentes) é 10110, que é
precisamente a palavra transmitida.
O procedimento acima pode ser esquematizado como mostra a figura abaixo.
[fonte] −→ [codificador da fonte] −→ [codificador de canal]−→ [canal]
↓
[usuário]←−[decodificador da fonte]←−[decodificador de canal]
2) Suponhamos que queremos enviar mensagens (a, b, c) com a, b, c ∈ {0, 1} e digamos
que o nosso canal de comunicações causa um erro em cada seis dı́gitos consecutivos. Se
enviarmos a mensagem pura o receptor vai receber uma mensagem errada a cada duas
enviadas. outra tentativa é repetir cada mensagem, introduzindo redundância, o que não
vale a pena, pois se o receptor recebe, por exemplo, (a, b, c)(a´, b, c), a 6= a0 , como ele
vai saber se o primeiro dı́gito da mensagem é a ou a´? Se repetirmos a mensagem três
vezes, então certamente o receptor saberá qual é a mensagem: (a, b, c)(a´, b, c)(a, b, c).
Para isso tivemos que introduzir seis dı́gitos redundantes em cada mensagem.
O estudo da Teoria dos Códigos está intimamente ligado a uma série de tópicos da
matemática discreta, tais como exponenciais, teoria de grafos, assim como tópicos diversos
como teoria de informação, criptografia e álgebra computacional. O assunto, além de ser
intrinsecamente interessante, tem a virtude de mesclar conceitos e técnicas importantes de
Álgebra Abstrata com aplicações imediatas na vida real, o que mostra como a sofisticação
4
tecnológica torna cada vez mais difusa a fronteira entre a Matemática Pura e a Matemática
Aplicada.
5
2
Códigos Corretores de Erros
Apresento algumas definições que são importantes para o bom entendimento da Teoria
dos códigos corretores de erros:
Definição 1 O alfabeto A é um conjunto finito. Em alguns livros a notação utilizada
para o alfabeto é Fq, onde q é o número de elementos de F.
Definição 2 É uma combinação de elementos do alfabeto.
x = (x1 , x2 , · · · , xn )/xi ∈ A; 1 ≤ i ≤ n.
Definição 3 C ⊂ An /C = {x = (x1 , x2 , · · · , xn ) : xi ∈ A}, onde cada x ∈ C é uma
palavra, ou seja, é uma combinação de elementos do alfabeto e An é um espaço vetorial
com n ∈ N.
Convida-se o leitor a pensar na Lı́ngua Portuguesa como um código. Assim, o alfabeto
definido seria um conjunto, onde seus elementos são letras, e a palavra, uma combinação
delas. É claro que o código será um conjunto formado por essas palavras. Pode-se dizer que
esse é um código corretor de erros, pois, imagine que se escrevermos uma palavra, produzimos a sequência de letras “gatho”. Como este não é um elemento da lı́ngua portuguesa,
que é o nosso código, percebe-se imediatamente que houve erro; e nesse caso a correção é
possı́vel, pois a palavra do nosso código que mais se assemelha a “gatho”é “gato”. Agora
se a palavra “gato”fosse erroneamente escrita como “rato”, ou como “pato”, ou ainda
como “galo”, não detectarı́amos o erro, porque todas são palavras da Lı́ngua Portuguesa.
Então a falha deste código está na proximidade das palavras.
Um modo de medir a distância entre palavras em An é apresentado a seguir.
Definição 4 Dados dois elementos u, v ∈ An , a distância de Hamming entre u e v é
6
definida como
d(u, v) =| {i; ui 6= vi , 1 ≤ i ≤ n} |
Por exemplo, em {0, 1}3 , temos
d(001, 111) = 2
d(000, 111) = 3
d(100, 110) = 1
Como no estudo das métricas estudadas em Topologia, a métrica de Hamming possui as
seguintes propriedades:
Dados u, v, w ∈ An , temos que
i) d(u, v) ≥ 0
Prova: Se u = v, então d(u, v) = d((u1 , ..., un ), (v1 , ..., vn )) = 0, pois u1 = v1 , ..., un =
vn . Se u 6= v então d(u, v) = d((u1 , ..., un ), (v1 , ..., vn )) = | i |> 0, pois 1 ≤ i ≤ n.
ii) d(u, v) = d(v, u)
Prova: d(u, v) = d((u1 , ..., un ), (v1 , ..., vn ))=| {i; ui 6= vi , 1 ≤ i ≤ n} | = | {i; vi 6=
ui , 1 ≤ i ≤ n} |=d((v1 , ..., vn ), (u1 , ..., un ))= d(v,u).
iii) d(u, v) ≤ d(u, w) + d(w, v)
Prova: A contribuição das i-ésimas coordenadas de u e v para d(u, v) é igual a zero
se ui = vi , e igual a um se ui 6= vi . No caso em que a contribuição é zero, certamente a
contribuição das i-ésimas coordenadas a d(u, v) é menor ou igual a das i-ésimas coordenadas a d(u, w) + d(w, v)(= 0, 1 ou 2).
No outro caso, temos que ui 6= vi e, portanto, não podemos ter ui = wi e wi = vi . Conseqüentemente, a contribuição das i-ésimas coordenadas a d(u, w) + d(w, v) é maior ou
igual a 1, que é a contribuição das i-ésimas coordenadas a d(u, v).
Definição 5 Dados um elemento a ∈ An e um número real t > 0, definimos Disco e
Esfera, respectivamente, como:
D(a, t) = {u ∈ An ; d(u, a) ≤ t}
S(a, t) = {u ∈ An ; d(u, a) = t}
7
Definição 6 Seja C um código. A distância mı́nima de C é o número
d = min{d(u, v); u, v ∈ C e u 6= v}
Lema: Seja C um código com distância mı́nima d. Se c e c´são palavras distintas de C,
então:
D(c, k) ∩ D(c0 , k) = ∅
Prova: De fato, se x pertencesse a D(c, k) ∩ D(c0 , k), terı́amos d(x, c) ≤ k e d(x, c0 ) ≤ k,
e portanto, pela simetria e pela desigualdade triangular,
d(c, c0 ) ≤ d(c, x) + d(x, c0 ) ≤ 2k ≤ d − 1,
absurdo, pois d(c, c0 ) ≥ d.
Teorema 1 Seja C um código com distância mı́nima d. Então C pode corrigir até k =
[ d−1
] erros e detectar até d − 1 erros.
2
Por exemplo, no código do robô, a distância mı́nima é d = 3, então, pelo teorema acima,
é possı́vel corrigir até k = [ d−1
] = 1 erro e detectar d − 1 = 2 erros.
2
A demonstração deste teorema será feito depois da definição de “peso de um código” no
capı́tulo 3.
]. O código
Definição 7 Seja C ⊂ An um código com distância mı́nima d e seja k = [ d−1
2
C será dito perfeito se
[
D(c, k) = An
c∈C
Exemplo 1 O código do robô, tão utilizado como exemplo neste trabalho, não é perfeito.
De fato,
C = {00000, 01011, 10110, 11101}
d−1
3−1
k=[
]=[
]=1
2
2
D(c, k) = D(c, 1) = {u ∈ C/d(u, c) ≤ 1} = ∅, ∀ c, u ∈ C,
pois d = min{d(u, v); u, v ∈ C} = 3.
8
3
Códigos Lineares
A classe dos códigos lineares é a classe de códigos mais utilizada na prática. No
capı́tulo 2 vimos que um código C é um subconjunto de um espaço vetorial An , onde A
é um conjunto finito denominado alfabeto. Da mesma forma, um código linear C é um
subconjunto de um espaço vetorial, e mais do que isto, C é um subespaço de um espaço
vetorial An , onde A é um corpo finito.
3.1
Códigos Lineares
Definição 8 Sejam K um corpo finito com q elementos, n um número natural e K n um
espaço vetorial de dimensão n. Um código C ⊂ K n será chamado de código linear se for
um subespaço de K n .
Conhecendo a Álgebra Linear se pode, desde já, observar que os códigos lineares dispõem
de várias propriedades importantes da Matemática, e que serão de grande utilidade para
o desenvolvimento da Teoria dos Códigos. O código do robô citado no capı́tulo anterior,
por exemplo, é um código linear. O alfabeto A2 = {0, 1} é o corpo de Galois, bastante
conhecido pelos matemáticos, e o código utilizado nesse exemplo é subespaço vetorial de
A52 , imagem da transformação linear
T : A22 −→ A52
(x1 , x2 ) 7−→ (x1 , x2 , x1 , x1 + x2 , x2 )
Como todo código linear é um subespaço de um espaço vetorial de dimensão finita, então,
por definição, ele será um espaço vetorial de dimensão finita. Agora, suponha que a
dimensão de um código linear C seja k e que v1 , v2 , ..., vk seja uma de suas bases, portanto
pode-se escrever cada elemento de C de modo único, como uma combinação linear de
9
v1 , v2 , ..., vk . Daı́,
λ1 υ1 + ... + λk υk = υ =
k
X
λi υi
i=1
onde υ C e λi K, i=1, ..., k.
Temos também que a cardinalidade de C é dada por
M = |C| = q k
e que sua dimensão pode ser escrita da seguinte forma:
dimk C = k = logq q k = logq M
Dessa forma, se consegue uma nova forma de calcular a dimensão de um espaço vetorial
C.
Definição 9 Dado x K n , define-se o peso de x como sendo o número inteiro
ω(x) := |{i : xi 6= 0}|
Em outras palavras,
ω(x) = d(x, 0)
onde d representa a métrica de Hamming.
Definição 10 O peso de um código linear C é o inteiro
ω(C) := min{ω(x) : x C − {0}}
Neste caso o zero é excluı́do porque não faz sentido calcular a distância de um vetor a ele
mesmo, já que este cálculo daria zero.
Proposição 1 Seja C ⊂ K n um código linear com distância mı́nima d. Temos que
i) ∀x, y K n , d(x, y) = ω(x − y)
ii) d = ω(C)
Demonstração:
i) Sejam x, y K n , então d(x, y) = |{i : xi 6= yi , 1 ≤ i ≤ n}| = |{i : xi − yi 6= 0, 1 ≤ i ≤ n}|
= ω(x − y).
ii)Seja d a distância mı́nima de um código linear C, então, por definição temos.
d = min{d(x, y) : x, y C e x 6= y}
10
Considere o fato de que z = x − y ∈ C − {0} e d(x, y) = ω(x − y) = ω(z). Dessa forma,
d = min{ω(z) : z C − 0} = ω(C).
A partir dos resultados dessa proposição, nota-se que, em códigos lineares com M
elementos pode-se calcular a distância mı́nima d a partir de M - 1 cálculos de distâncias,
o que é muito trabalhoso se for considerado um código muito grande. Mesmo assim
teremos que desenvolver um outro método mais rápido e eficiente para determinar a
distância mı́nima de um código.
Pela parte (ii) da proposição 1, a distância mı́nima de um código linear C será também
chamada de peso do código C.
Agora que já foi definido o peso de um código linear C, já pode ser demonstrado o
Teorema 1 da introdução. Mas para isso será reescrito o teorema mudando a distância
mı́nima “d”pelo peso de C, ω(C), pois, como vimos na proposição acima d = ω(C).
Teorema 2 Seja C um código de peso ω(C) então C corrige [ ω(C)−1
] erros.
2
Prova: Seja ` =
d−1
2
então 2` + 1 ≤ d. Suponha que C não corrija ` erros e seja y Anq
tal que existam x1 , x2 C, x1 6= x2 com d(xi , y) ≤ `, i=1, 2. Pela propriedade (iii) de
distância de Hamming temos d(x1 , x2 ) ≤ d(x1 , y) + d(y, x2 ) ≤ 2`. Por outro lado como
x1 6= x2 , pela definição de d temos d(x1 , x2 ) ≥ d ≥ 2` + 1, contradição.
Das definições de Álgebra Linear, se pode descrever subespaços vetoriais de duas maneiras; uma como imagem e outra como núcleo de transformações lineares. Esse resultado
significa um salto muito grande na teoria dos códigos corretores, pois antes disso, a informação que se tinha tı́nhamos era a de que um código linear é um subespaço de um
espaço vetorial e essa informação não garante grandes resultados. Mas se pode escrever um código linear como imagem de uma transformação linear ou como o núcleo de
uma transformação, a partir disso, tudo fica mais concreto, pois tem-se agora como fazer
cálculos e o estudo da teoria dos códigos pode avançar muito mais.
Agora, obtêm-se a representação de um código linear C como imagem de uma transformação linear:
Escolha uma base v1 , ..., vn de C e considere a aplicação linear
T : Kk → Kn
x = (x1 , ..., xk ) 7−→ x1 v1 + ... + xk vk
11
T é uma transformação linear injetora.
De fato, sejam x, y K k , então
T (x) = T (y) =⇒ T (x1 , ..., xk ) = T (y1 , ..., yk )
=⇒ x1 v1 + ... + xk vk = y1 v1 + ... + yk vk
(x1 − y1 )v1 + ... + (xk − yk )vk = 0
=⇒ x1 − y1 = 0 =⇒ x1 = y1
..
.
xk − yk = 0 =⇒ xk = yk
Como v1 , ..., vk é base de C, logo é LI. Portanto (x1 , ..., xk ) = (y1 , ..., yk ) ⇒ x = y.
Então pode-se observar que a imagem de T é C, ou em sı́mbolos,
Im(T ) = C
Porém nessa representação é difı́cil decidir se um dado elemento v de K n pertence ou não
a C, pois, para tal é necessário resolver o sistema de n equações e k incógnitas x1 , ..., xk
abaixo
x1 v1 + ... + xk vk
A outra maneira de descrever um código C é através do núcleo de uma transformação
linear. Tome um subespaço C 0 de K n complementar de C, isto é,
C ⊕ C0 = Kn
e considere a aplicação linear
H : C ⊕ C 0 −→ K n−k
u ⊕ v 7−→ v; u Ce v C 0
Se observarmos o núcleo da aplicação H, temos:
Ker(H) = {u ⊕ v : H(u ⊕ v) = v = 0} = {u; u ∈ C}
Portanto o núcleo dessa transformação linear é precisamente C.
12
Dessa forma para determinar se um certo elemento v ∈ K n pertence ou não a C, basta
verificar se H(v) é ou não o vetor nulo de K n−k .
Exemplo 2 Considere o corpo finito com três elementos F3 = {0, 1, 2} e seja C ⊂ F34 o
código de dimensão 2 gerado pelos vetores v1 = 1011 e v2 = 0112. Esse código possui 9
(q k = 32 ) elementos. Nós podemos representar C da seguinte forma
x1 v1 + x2 v2
variando x1 e x2 em F3 ou como núcleo da transformação linear
H : F34 → F32
(x1 , ..., x4 ) 7−→ (2x1 + 2x2 + x3 , 2x1 + x2 + x4 )
Definição 11 Seja K um corpo finito. Dois códigos lineares C e C’são linearmente equivalentes se existir uma isometria linear T : K n −→ K n tal que T (C) = C 0 .
Os resultados obtidos através desta definição são usados como definição de códigos lineares
equivalentes. Um dos resultados é o que segue:
Dois códigos lineares são linearmente equivalentes se, e somente se, cada um deles
pode ser obtido do outro mediante uma sequência de operações do tipo:
(i) Multiplicação dos elementos numa dada posição fixa por um escalar não nulo em todas
as palavras.
(ii) Permutação das posições de todas as palavras do código, mediante uma permutação
fixa de {1, 2, ...,n}.
3.2
Matriz Geradora de um Código
Sejam K um corpo finito com q elementos e C ⊂ K n um código linear. Chama-se
de parâmetros do código linear C à terna de inteiros (n, k, d). Note que o número de
elementos de C é igual a q k .
Seja β = {v1 , ..., vk } uma base de C e considere a matriz G, cujas linhas são os vetores
vi = (vi1 , ..., vin ), i = 1, ..., k, isto é,
  

v1
v11 v12 . . . v1n
.  .
..
.. 
..  =  ..
G=
.
. 
  

vk
vk1 vk2 . . . vkn
13
A matriz G é chamada de matriz geradora de C associada à base β.
Considere a transformação linear definida por
T : K k −→ K n
x 7−→ xG
Se x = (x1 , ..., xk ), temos que
T (x) = xG = x1 v1 + ... + xk vk
Logo T (K k ) = C. Pode então, se considerar K k como sendo o código da fonte, C, o código
de canal e a transformação T, uma codificação. Note que a matriz G depende da escolha
da base. E lembrando que uma base de um espaço vetorial pode ser obtida de uma outra
qualquer através de sequências de operações como permutação de dois elementos da base,
multiplicação de um elemento da base por um escalar não nulo ou ainda, substituição de
um vetor da base por ele mesmo somado com um múltiplo escalar de outro vetor da base.
Observa-se, então que pode-se construir códigos a partir de matrizes geradoras G.
Para isso, basta tomar uma matriz cujas linhas são linearmente independentes e definir
um código como sendo a imagem da transformação linear
T : K k −→ K n
x 7−→ xG
Exemplo 3 Tome K = F2 e seja


1 0 1 0 1


.
G=
1
1
0
1
0


1 1 1 1 1
Considerando a transformação linear definida por
T : F23 −→ F25
x 7−→ xG
obtêm-se um código C em F25 , imagem de T. A palavra 101 do código da fonte, por
exemplo, é codificada como 01010.
Suponha agora que seja dada a palavra 10101 do código, e decodificá-la, isto é, achar a
14
palavra x de F23 da qual ela se origina por meio de T. Significa, então, resolver o sistema:
(x1 , x2 , x3 )G = (10101),
ou seja,


x1 + x2 + x3 = 1






x2 + x3 = 0



x1 + x3 = 1





x2 + x3 = 0






x1 + x3 = 1
cuja solução é x1 = 1, x3 = 0 e x2 = 0.
O sistema de equações do exemplo, em particular, foi fácil de resolver, mas, em geral,
dada uma matriz G mais complexa, a resolução do sistema de equações associado pode
ser muito mais trabalhosa. Entretanto, efetuando operações sobre as linhas de G, pode-se
colocar G na forma


1 0 0 0 0


.
G0 = 
0
1
0
1
0


0 0 1 0 1
Note que

xG0 = x1 x2

1
0
0
0
0

  = x1 x2 x3 x2 x3
x3 
0
1
0
1
0


0 0 1 0 1
e, portanto, obtém-se o vetor x tomando apenas as três primeiras componentes do vetor
a ser decodificado. Logo, a palavra (10101) é facilmente decodificada como (101).
Definição 12 Uma matriz G geradora de um código C está na forma padrão se tivermos
G = (Idk |A)
onde Idk é a matriz identidade k × k e A, uma matriz k × (n − k).
Mas mesmo com um código C, nem sempre é possı́vel achar uma matriz geradora de
C na forma padrão. Por exemplo, o código em F25 de matriz geradora
!
0 0 1 0 1
0 0 0 1 1
15
nunca poderá ter uma matriz na forma padrão, pois não temos como colocá-la na forma
(Idk |A). No entanto, efetuando também permutações das colunas de G, podemos obter
a matriz
!
1 0 0 0 1
,
0 1 0 0 1
que é a matriz geradora na forma padrão de um código C’ equivalente a C.
De modo geral, efetuando também sequências de operações sobre a matriz geradora
G de um código linear C, como permutação de duas colunas ou multiplicação de uma
coluna por um escalar não nulo, obtemos uma matriz G’ de um código C’ equivalente a
C. Note que efetuar essas operações numa base de C implica efetuá-las em todas as palavras de C, pois todas elas são escritas como combinação linear dos elementos da base de C.
Teorema 3 Dado um código C, existe um código equivalente C’ com matriz geradora na
forma padrão.
Demonstração: Seja G uma matriz geradora de C. Mostraremos que com a seqüência de
operações listadas abaixo, podemos colocar G na forma padrão.
(i) Permutação de duas linhas.
(ii) Multiplicação de uma linha por um escalar não nulo.
(iii) Adição de um múltiplo escalar de uma linha a outra.
(iv) Permutação de duas colunas.
Suponhamos


g11 g12 . . . g1n
 .
..
.. 
.
G=
.
. 
 .
.
gk1 gk2 . . . gkn
Como a primeira linha de G não é nula, pois os vetores linhas de G são linearmente
independentes, por meio de (iv), podemos supor g11 6= 0. Agora, multiplicando a pri−1
meira linha por g11
, podemos por 1 no lugar de g11 (operação (ii)). Somando à segunda,
terceira, etc. linhas, respectivamente, a primeira linha multiplicada respectivamente por
16
(−1)g21 , (−1)g31 , etc.(operações (iii)),

1

0

.
 ..

0
obtemos uma matriz

b12 . . . b1n

b22 . . . b2n 

.
..
.. 
.
. 

bk2 . . . bkn
Agora, na segunda linha dessa matriz, temos certamente um elemento não nulo que,
por meio de uma operação(iv), pode ser colocado na segunda linha e segunda coluna.
Multiplicando a segunda linha pelo inverso desse elemento, a matriz se transforma em


1 c12 c13 . . . c1n


0 1 c

.
.
.
c
23
2n 



0 c32 c33 . . . c3n  .


 .. ..

.
.
.
.
. .

.
.


0 ck2 ck3 . . . ckn
Novamente, usando as operações (iii), obtemos a

1 0 d13 . . .

0 1 d
23 . . .


0 0 d33 . . .

 .. .. ..
. . .

matriz

d1n

d2n 


d3n 

.. 
. 

0 0 dk3 . . . dkn
e assim sucessivamente, até encontrarmos uma matriz na forma padrão
G0 = (Idk |A).
Sejam u = (u1 , ..., un ) e v = (v1 , ..., vn ) elementos de K n , define-se o produto interno
de u e v como sendo
hu, vi = u1 v1 + ... + un vn .
Essa operação possui as propriedades usuais de um produto interno:
(i) Simétrica
hu, vi = hv, ui
(ii)Bilinear
hu + λw, vi = hu, vi + λhw, vi, ∀λK.
17
3.3
Códigos Duais
Seja C ⊂ K n um código linear. Chamamos de Código Dual do código C o conjunto
C ⊥ = {vK n : hv, ui = 0, ∀u ∈ C}.
Pela definição podemos observar que C ⊥ é ortogonal a C.
Lema 1: Se C ⊂ K n é um código linear, com matriz geradora G, então
(i) C ⊥ é um subespaço vetorial de K n ;
(ii)x ∈ C ⊥ ⇐⇒ Gxt = 0.
Prova:
(i) Sejam dados u, v ∈ C ⊥ e λ ∈ K. Temos, para todo x ∈ C, que
hu + λv, xi = hu, xi + λhv, xi = 0 + λ0 = 0
Portanto, u + λv ∈ C ⊥ e C ⊥ é um subespaço vetorial de K n ;
(ii) x ∈ C ⊥ se, e somente se x é ortogonal a u, ∀u ∈ C se, e somente se x é ortogonal a
todos os elementos de uma base de C, o que é equivalente a dizer que Gxt = 0, pois as
linhas de G são uma base de C.
Como C ⊥ é um subespaço vetorial de K n , como foi demonstrado acima, podemos
concluir que um código dual é também um código linear.
Proposição 2 Seja C ⊂ K n um código de dimensão k com matriz geradora G = (Idk |
A), na forma padrão. Então
(i) dim C ⊥ = n − k.
(ii) H = (−At | Idn−k ) é uma matriz geradora de C ⊥ .
Prova:
(i) Pelo Lema 1, x = (x1 , ..., xn ) pertence a C ⊥ se, e somente se, Gxt = 0. Como G está
na forma padrão, isso equivale a ter
 


x1
xk−1
.


 ..  = −A  ... 
 


xk
xn
Portanto, C ⊥ possui q n−k elementos, que são justamente as possı́veis escolhas arbitrárias
de xk−1 , ..., xn . Logo, C ⊥ tem dimensão n − k.
(ii) É evidente que as linhas de H são linearmente independentes(por causa do bloco
18
Idn−k ), portanto geram um subespaço vetorial de dimensão n - k. Como as linhas de H
são ortogonais às linhas de G, temos que o espaço gerado pelas linhas de H está contido
em C ⊥ ; e como esses dois subespaços têm a mesma dimensão, eles coincidem, provando
assim que H = (−At |Idn−k )é uma matriz geradora de C ⊥ .
Lema 2: Seja C um código linear em K n . Para toda permutação σ de {1, ..., n}, para
todo C ∈ K∗ e para todo j = 1, ..., n temos que
(i) (Tσ (C))⊥ = Tσ (C ⊥ )
(ii) (Tcj (C))⊥ = Tcj−1 (C ⊥ )
Prova:
(i) Seja x ∈ (Tσ (C))⊥ , então hx, ui = 0, ∀u ∈ Tσ (C). Assim, hx, vi = 0, ∀v ∈ B, sendo B
uma base do código Tσ (C). Portanto Gxt = 0, onde G é a matriz geradora de Tσ (C) e
suas linhas são uma base de Tσ (C).
(ii) Segue de (i).
Proposição 3 Sejam C e D dois códigos lineares em K n . Se C e D são linearmente
equivalentes, então C ⊥ e D⊥ são linearmente equivalentes.
Prova: Para essa demonstração precisaremos do seguinte resultado:
Sejam C e C’ dois códigos em An . Temos que C e C’ são equivalentes se, e somente
se, existem uma permutação π de {1, ..., n} e bijeções f1 , ..., fn de A tais que
C 0 = {(fπ(1) (xπ(1) ), ..., fπ(n) (xπ(n) )) : (x1 , ..., xn ) ∈ C}.
Se C e D são linearmente equivalentes existem uma permutação σ de {1, 2, ..., n} e elementos c1 , ..., cn ∈ K ∗ tais que
D = Tσ ◦ Tc11 ◦ ... ◦ Tcnn (C).
Daı́, levando em conta o lema 2, se segue o resultado, pois
D⊥ = (Tσ ◦ Tc11 ◦ ... ◦ Tcnn (C))⊥ = Tσ ◦ Tc1−1 ◦ ... ◦ Tcn−1
(C ⊥ ).
n
1
Corolário 1 Se D é um código linear em K n de dimensão k, então D⊥ é um código de
dimensão n − k.
Prova: O código D é equivalente a um código C, também de dimensão k, com matriz
geradora na forma padrão e, portanto, segue que dimC ⊥ = n − k. Pela Proposição 2,
temos que D⊥ é equivalente a C ⊥ e, portanto, também tem dimensão n − k.
19
Lema 3: Suponha que C seja um código de dimensão k em K n com matriz geradora
G. Uma matriz H de ordem (n − k) × n, com coeficientes em K e com linhas linearmente
independentes, é uma matriz geradora de C ⊥ se, e somente se,
G · H t = 0.
Prova: As linhas de H geram um subespaço vetorial de K n de dimensão n - k, portanto,
igual a dimensão de C ⊥ . Por outro lado, representando por h1 , ..., hn−k e por g1 , ..., g k ,
respectivamente, as linhas de H e de G, temos que
(G · H t )i,j = hgi , hj i.
Portanto, G · H t = 0 equivale a dizer que todos os vetores do subespaço gerado pelas
linhas de H estão em C ⊥ . Por outro lado, esse subespaço tem a mesma dimensão de C ⊥ ,
logo,
G · H t = 0 ⇐⇒ C ⊥
é gerado pelas linhas de H.
Corolário 2 (C ⊥ )⊥ = C.
Prova: Sejam G e H respectivamente matrizes geradoras de C e C ⊥ . Logo, G · H t = 0.
Tomando transpostas nessa última igualdade, temos que H · Gt = 0, logo, G é matriz
geradora de (C ⊥ )⊥ , daı́ (C ⊥ )⊥ = C.
Proposição 4 Seja C um código linear e suponhamos que H seja uma matriz geradora
de C ⊥ . Temos então que
v ∈ C ⇐⇒ Hv t = 0.
Prova: Temos, pelo corolário acima e pelo Lema 1(ii), v ∈ C se, e somente se, v ∈ (C ⊥ )⊥
se, e somente se, Hv t = 0.
A proposição 4 caracteriza os elementos de um código C por uma condição de anulamento. A matriz geradora H de C ⊥ é chamada de matriz teste de paridade de C.
Para verificar se um determinado vetor v em K n pertence ou não a um código C com matriz
geradora G, é preciso verificar se o sistema de n equações com k incógnitas x = (x1 , ..., xk ),
dado por
xG = v,
20
admite solução. Como já observamos nos resultados anteriores, essa questão requer um
custo computacional muito elevado para ser respondida. Mas, com a matriz teste de
paridade H, a solução pode ser encontrada bem mais rapidamente verificando se é nulo o
vetor Hv t . A esse vetor Hv t , chamamos de sı́ndrome de v.
Exemplo 4 Seja dado o código C sobre F2 com

1 0 0 1

G=
0 1 0 0
0 0 1 0
matriz geradora

1 1

1 1
.
1 0
Como G está na forma padrão, é fácil calcular uma matriz teste de paridade H. Então,
temos que

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



Hv t = 
0
 
0
e
 
1
 
0 t

H(v ) = 
1 6= 0,
0
temos que v ∈ C e v 0 6∈ C.
Proposição 5 Seja H a matriz teste de paridade de um código C. Temos que o peso de C
é maior do que ou igual a s se, e somente se, quaisquer s - 1 colunas de H são linearmente
independentes.
Prova: Suponhamos que cada cada conjunto de s - 1 colunas de H é linearmente independente. Seja c = (c1 , ..., cn ) uma palavra não nula de C, e sejam h1 , ..., hn as colunas de H.
Como Hct = 0, temos que
0 = H · ct =
X
ci hi .
Visto que ω(c) é o número de componentes não nulas de c, segue que se ω(c) ≤ s − 1,
terı́amos, pela igualdade acima, uma combinação nula de um número t, com 1 ≤ t ≤
s − 1, de colunas de H, o que é contraditório. Logo, ω(c) ≥ s e, portanto, ω(C) ≥ s.
21
Reciprocamente, suponhamos que ω(C) ≥ s. Suponhamos também, por absurdo, que H
tenha s - 1 colunas linearmente dependentes, digamos hi1 , hi2 , ..., his−1 . Logo, existiriam
ci1 , ..., cis−1 , no corpo, nem todos nulos, tais que
ci1 hi1 + ... + cis−1 his−1 = 0.
Portanto, c = (0, ..., ci1 , 0, ..., cis−1 , 0, ..., 0) ∈ C e conseqüentemente, ω(c) ≤ s − 1 < s, o
que seria um absurdo.
Teorema 4 Seja H uma matriz teste de paridade de um código C. Temos que o peso de
C é igual a s se, e somente se, quaisquer s - 1 colunas de H são linearmente independentes
e existem s colunas de H linearmente dependentes.
Prova: Suponhamos que ω(C) = s, logo, todo conjunto de s -1 colunas de H é linearmente
independente. Por outro lado, existem s colunas de H linearmente dependentes, pois, caso
contrário, pela proposição 4, terı́amos ω(C) ≥ s + 1.
Reciprocamente, suponhamos que todo conjunto de s-1 vetores colunas de H é linearmente
independente e existem s colunas linearmente dependentes. Logo, da proposição 5, temos
que ω(C) ≥ s. Mas ω(C) não pode ser maior do que s, pois, neste caso, novamente a
proposição 5 nos diria que todo conjunto com s colunas de H é linearmnete independente,
o que é uma contradição.
Corolário 3 (Cota de Singleton) Os parâmetros (n, k, d) de um código linear satisfazem
à desigualdade
d ≤ n − k + 1.
Prova: Se H é uma matriz teste de paridade, ela tem posto n - k. Como, pelo teorema 2,
d - 1 é menor ou igual ao posto de H. Portanto, d ≤ n − k + 1.
3.4
Exemplos de Códigos
Códigos de Hamming:Um código de Hamming de ordem m sobre F2 é um código
com matriz teste de paridade Hm de ordem m × n, cujas colunas são os elementos de
F2m − {0} numa ordem qualquer.
Temos que o comprimento de um código de Hamming de ordem m é n = 2m − 1 e a
sua dimensão é k = n − m= 2m − m − 1.
22
Proposição 6 Todo código de Hamming é perfeito.
Prova: Como d=3, temos que k = [ d−1
]=[ 3−1
] = 1.
2
2
Dado c em F2n , temos que:
|D(c, 1)| =
1
X
n
!
(q − 1)i =
!
(2 − 1)0 +
n
!
(2 − 1)1 = 1 +
1
0
i
i=0
n
n!
=1+n
(n − 1)!
Portanto,
|
[
D(c, 1)| = [1 + n] · 2k = [1 + 2m − 1] · 2n−m = 2n ,
c∈C
e conseqüentemente
[
D(c, 1) = F2n .
c∈C
Proposição 7 Um código será chamado de MDS (Maximum Distance Separable) se valer
a igualdade d = n − k + 1. Verificaremos que um código de Hamming de ordem m é MDS
se, e somente se, m = 2.
Prova:(=⇒) Suponhamos que o código de Hamming C de ordem m é MDS, então d =
n − k + 1=⇒ n − k = d − 1.
Sabemos que, num código de Hamming, k = n − m e d = 3. Então,
m=n−k =d−1=3−1=2
(⇐=) Sendo m=2 temos, k = n - 2= 1, pois n = 3. Logo,d ≤ 3 − 1 + 1 = 3 =⇒ d ≤ 3.
Daı́, se d=2 temos k = [ d−1
] = 0, impossı́vel, pois k=1. Se d=1, temos k = [ d−1
] = 0, o
2
2
que não pode como vimos acima. Portanto d=3.
Códigos de Reed-Solomon: Seja K um corpo finito e considere o K-espaço vetorial
K[X]k−1 dos polinômios em K[X] de grau menor ou igual a k − 1, incluindo o polinômio
nulo, isto é,
K[X]k−1 = {P ∈ K[X] : gr(P ) ≤ k − 1} ∪ {0}.
Esse espaço vetorial tem dimensão k com uma base dada por {1, X, X 2 , ..., X k−1 }.
Sejam n um inteiro, tal que n ≥ k, e α1 , ..., αn elementos distintos de K. A função definida
por
T : K[X]k−1 −→ K n
P 7−→ (P (α1 ), ..., P (αn ))
23
é uma transformação linear.
Verificação: Sejam P1 , P2 ∈ K[X]k−1 , temos que λP2 ∈ K[X]k−1 , daı́
T (P1 + λP2 ) = (P1 + λP2 )(α1 ), ..., (P1 + λP2 )(αn ) =
= (P1 (α1 ), ..., P1 (αn )) + (λP2 (α1 ), ..., λP2 (αn )) =
= (P1 (α1 ), ..., P1 (αn )) + λ(P2 (α1 ), ..., P2 (αn )) =
= T (P1 ) + λT (P2 ).
Além disso, T é injetora. De fato,
KerT = {P ∈ K[X]k−1 : P (α1 ) = ... = P (αn ) = 0} = {0},
pois um polinômio não nulo P de grau menor do que k não pode ter n raı́zes distintas,
pois ele só pode possuir no máximo k raı́zes e definimos anteriormente que n ≥ k.
Portanto, a imagem C de T é um código linear de comprimento n e dimensão k. Podemos
considerar K[X]k−1 como código da fonte, Im(T ) = C como código de canal e, a transformação T como uma codificação. O código de Reed-Solomon é definido por α1 , ..., αn .
Uma matriz geradora do código C é dada por



1
1

T (1)



α1
α2
 T (X)  


  2
G=
α22
 =  α1
..


.
..

 
 ...
.

k−1
T (X )
k−1
k−1
α1
α1
...
1


αn 


2 
. . . αn 
.. 
. 

. . . αnk−1 .
...
Considere uma palavra não nula c de C. Então, existe P ∈ K[X]k−1 tal que
c = (P (α1 ), ..., P (αn )).
Logo,
ω(c) = |{i ∈ {1, ..., n} : P (αi ) 6= 0}| =
n − |{i ∈ {1, ..., n} : P (αi ) = 0}| ≥ n − gr(P ) ≥ n − (k − 1) = n − k + 1
Logo,
d≥n−k+1
24
Pela cota de Singleton, sabemos que
d ≤ n − k + 1.
Portanto,
d=n−k+1
Vamos agora determinar uma matriz geradora de C na forma padrão:
Considere para j = 1, ..., k os polinômios
pj (X) =
(X − α1 )...(X − αj )...(X − αk )
.
(αj − α1 )...(αj − αj−1 )(αj − αj+1 )...(αj − αk )
Logo, pj (αi )=δi,j . Temos que {p1 (X), ..., pk (X)} é uma base de K[X]k−1 , portanto, obtemos a seguinte matriz geradora G0 de C:


T (p1 )
 . 
. 
G0 = 
 .  = (Idk |A),
T (pk )
onde


A=

p1 (αk+1 ) . . . p1 (αn )


... 
.
pk (αk+1 ) . . . pk (αn )
...
Portanto, G0 é uma matriz geradora de C na forma padrão. Podemos, ainda, pelo teorema
de Interpolação de Lagrange, decidir se um dado vetor pertence ou não ao código de ReedSolomon C.
De fato, pelo teorema, existe um único polinômio P (X) ∈ K[X]k−1 tal que P (αi ) = βi , i =
1, ..., k (sendo v = (β1 , ..., βn) ∈ K n ). Portanto,
v ∈ C ⇐⇒ (β1 , ..., βn) = (P (α1 ), ..., P (αn )),
ou seja,
P (αk+j ) = βk+j , j = 1, ..., n − k.
Exemplo 5 Considere K = F7 = Z7 , k = 4, n = 6 e α1 = 30 = 1,α2 = 31 = 3,α3 =
32 = 2,α4 = 33 = 6,α5 = 34 = 4 e α6 = 35 = 5. Portanto, o código de Reed-Solomon
de comprimento 6, de dimensão 4 e definido por α1 , α2 , α3 , α4 , α5 , α6 tem uma matriz
25
geradora

1 1 1 1

30 31 32 33

G=
30 312 34 36

30
33
1
4
3
38
36 39 312


1
1
 

5
3  1
=

310 
 1
315
1
1 1 1 1
3 2 6 4
2 4 1 2
6 1 6 1

1

5


4

6
e possui distância mı́nima d = n − k + 1 = 3.
3.5
Decodificação
Decodificação é o procedimento de detecção e correção de erros num determinado
código. O método geral de decodificação para códigos lineares que desenvolveremos é um
aperfeiçoamento de um método inventado por D. Slepian do Laboratório Bell na década
de 60.
Inicialmente, define-se o vetor erro e como sendo a diferença entre o vetor recebido r e o
vetor transmitido c, isto é,
e = r − c.
Exemplo 6 Num dado código sobre F2 , tenhamos transmitido a palavra (010011) e a
palavra recebida tenha sido (101011), então
e = (101011) − (010011) = (111000).
Seja H a matriz teste de paridade do código. Como Hct = 0, temos que
Het = H(rt − ct ) = Hrt − Hct = Hrt .
Portanto, a palavra recebida e o vetor erro têm a mesma sı́ndrome.
Denotemos por hi a i-ésima coluna de H. Se e=(α1 ...αn ) então
n
X
αi hi = Het = Hrt .
i=1
Lema 4: Seja C um código linear em K n com capacidade de correção k. Se r ∈ K n e
c ∈ C são tais que d(c, r) ≤ k, então existe um único vetor e com ω(e) ≤ k cuja sı́ndrome
é igual à sı́ndrome de r e tal que c = r - e.
Demonstração: De fato, c = r - e tem a propriedade do Lema, já que ω(e) = d(c, r) ≤ k.
Para provar a unicidade, suponha que e= (α1 ...αn ) e e’= (α10 ...αn0 ) sejam tais que ω(e) ≤ k
e ω(e’) ≤ k e tenham a mesma sı́ndrome que r. Então, se H é uma matriz teste de paridade
26
de C, temos
t
0t
He = He =⇒
n
X
i
αi h =
i=1
n
X
αi0 hi ,
i=1
o que nos dá uma relação de dependência linear entre 2k(≤ d − 1) colunas de H. Como
quaisquer d-1 colunas de H são linearmente independentes, temos que αi = αi0 para todo
i, logo e = e’.
Veja, como podemos determinar esse único vetor e a partir de Hrt no exemplo seguinte.
Exemplo 7 Determinação de e quando ω(e) ≤ 1.
Suponhamos que o código C tenha distância mı́nima d ≥ 3 e que o vetor erro e,
introduzido entre a palavra transmitida c e a palavra recebida r, seja tal que ωe ≤ 1.
Isto é, o canal introduziu no máximo um erro.
Se Het = 0, então r ∈ C e se toma c = r.
Suponhamos Het 6= 0, então ωe = 1 e, portanto, e tem apenas uma coordenada não
nula. Nesse caso, consideremos que e = (0, ..., α, ..., 0) com α 6= 0 na i-ésima posição.
Logo,
Het = αhi ,
onde hi é a i-ésima coluna de H. Portanto, não conhecendo e, mas conhecendo
Het = Hrt = αhi ,
podemos determinar e como sendo o vetor com todas as componentes nulas exceto a
i-ésima componente que é α. Note que i acima é bem determinado, pois d ≥ 3.
Como ilustração, considere o código do robô C. Esse código tem matriz teste de
paridade


1 0 1 0 0



H=
1 1 0 1 0 .
0 1 0 0 1
Seja r= (10100) uma palavra recebida, logo,
 
0
 
t
t
4

He = Hr = 
1 = 1.h .
0
27
Portanto, e= (00010) e, conseqüentemente,
c = r − e = (10110).
Agora, com base no exemplo anterior, estabeleceremos o algoritmo de decodificação em
códigos corretores de um erro.
Seja H a matriz teste de paridade do código C e seja r um vetor recebido. (Suponha
d ≥ 3)
(i)Calcule Hrt .
(ii)Se Hrt = 0, aceite r como a palavra transmitida.
(iii)Se Hrt = s 6= 0 compare s com colunas de H.
(iv) Se existirem i e α tais que st = αhi , para αK, então e é a n-upla com α na posição
i e zeros nas outras posições. Corrija r pondo c = r − e.
(v) Se o contrário de (iv) ocorrer, então mais de um erro foi cometido.
Seja C ⊂ K n um código corretor de erro com matriz teste de paridade H. Sejam d
]. Recorde que e e e têm a mesma sı́ndrome e, se
a distância mı́nima de C e k = [ d−1
2
ωe = d(r, c) < k, então e é univocamente determinado por r.
Seja v ∈ K n . Defina
v + C = v + c : c ∈ C.
Lema 5: Os vetores u e v de K n têm a mesma sı́ndrome se, e somente se, u ∈ v + C.
Demonstração: Hut = Hv t ⇐⇒ H(u − v)t = 0 ⇐⇒ u − v ∈ C ⇐⇒ u ∈ v + C.
Exemplo 8 Seja C o (4,2)- código gerado sobre F2 pela matriz
!
1 0 1 1
.
0 1 0 1
Logo,
C = {0000, 1011, 0101, 1110},
e as classes laterais segundo C são
0000 + C = {0000, 1011, 0101, 1110}
1000 + C = {1000, 0011, 1101, 0110}
0100 + C = {0100, 1111, 0001, 1010}
0010 + C = {0010, 1001, 0111, 1100}.
28
O Lema acima estabelece uma correspondência 1 a 1 entre classes laterais e sı́ndromes.
Todos os elementos de uma classe lateral têm a mesma sı́ndrome, e elementos de classes
laterais distintas possuem sı́ndromes distintas.
Definição 13 Um vetor de peso mı́nimo numa classe lateral é chamado de elemento
mı́nimo dessa classe.
No exemplo acima, temos que: 0000 é lı́der de C, 1000 é lı́der de 1000 + C, 0100 e 0001
são lı́deres de 0100+C, e 0010 é lı́der de 0010 + C.
Proposição 8 Seja C um código linear em K n com distância mı́nima d. Se u ∈ K n é tal
que
d−1
] = k,
2
então u é o único elemento lı́der de sua classe.
ω(u) ≤ [
Prova: Suponhamos que u, v ∈ K n com ω(u) ≤ [ d−1
] e ω(v) ≤ [ d−1
]. Se u − v ∈ C, então
2
2
ω(u − v) ≤ ω(u) + ω(v) ≤ [
d−1
d−1
]+[
] ≤ d − 1;
2
2
Logo, u − v = 0 e, portanto, u = v.
Comentário: Para achar lı́deres de classes, tomamos os elementos u tais que ω(u) ≤
[ d−1
].
2
Cada um desses elementos é lı́der de uma e somente uma classe. Esses lı́deres são
todos aqueles de peso menor ou igual a [ d−1
], os outros lı́deres não serão considerados.
2
Vamos agora discutir um algoritmo de correção de mensagens que tenham sofrido um
].
número de erros menor ou igual à capacidade de correção do código, que é k = [ d−1
2
Preparação: Determine todos os elementos u de K n , tal que ω(u) ≤ k. Em seguida,
calcule as sı́ndromes desses elementos e coloque esses dados numa tabela. Seja r uma
palavra recebida.
O Algoritmo de Decodificação
(1) Calcule a sı́ndrome st = Hrt .
(2) Se s está na tabela, seja l o elemento lı́der da classe determinada por s; troque r por
r−l
(3) Se s não está na tabela, então na mensagem recebida foram cometidos mais do que k
erros.
29
Justificativa: Dado r, sejam c e e, respectivamente, a mensagem transmitida e o vetor
erro. Como Het = Hrt , temos que a classe lateral onde e se encontra está determinada
pela sı́ndrome de r. Se ω(e) ≤ k, temos que e é o único elemento lı́der l de sua classe
e, portanto, é conhecido e se encontra na tabela. Conseqüentemente, pelo Lema 4, c =
r − e = r − é determinado.
Exemplo 9 Considere (6,3) código linear definido sobre F2 com matriz teste de paridade


1 0 0 1 0 1


.
H=
0
1
0
1
1
0


0 0 1 0 1 1
Nesse caso d = 3 e, portanto, k = [ d−1
] = 1.
2
Os vetores de peso menor ou igual a um com as suas respectivas sı́ndromes estão relacionados na tabela abaixo
lı́der
sı́ndrome
000000
000
000001
101
000010
011
000100
110
001000
001
010000
010
100000
100
Suponhamos, agora, que a palavra recebida seja
(a) r = (100011). Logo, Hrt = (010)t e, portanto, e= (010000). Conseqüentemente,
c = r − e = (110011).
(b)r = (110011). Logo, Hrt = (111)t , que não se encontra na tabela. Sendo assim, foi
cometido mais do que um erro na mensagem r.
30
4
Códigos Cı́clicos
4.1
Códigos Cı́clicos
Essa é uma classe de códigos muito utilizada nas aplicações por possuı́rem bons algoritmos de codificação e de decodificação. No que se segue, K é um corpo finito e as
coordenadas de K n serão representadas por (x0 , ..., xn−1 ).
Definição 14 Um código linear C ⊂ K n será chamado de código cı́clico se, para c =
(c0 , ..., cn−1 ) pertence a C, o vetor (cn−1 , c0 , ..., cn−2 ) pertence a C.
Equivalentemente, o código linear C será um código cı́clico se, dada a permutação π de
{0, ..., n − 1} definida por

i − 1, se i ≥ 1
π(i) =
n − 1, se i = 0,
e sendo
Tpi (c0 , c1 , ..., cn−1 ) = (cn−1 , c0 , ..., cn−2 )
temos que Tπc ∈ C para todo c ∈ C; ou seja, Tπ C ⊂ C.
Exemplo 10 Seja v ∈ K n . O espaço vetorial
hvi = Kv + KTπ v + ... + KTπn−1 v
é claramente um código cı́clico (Tπn ) = Id. Em particular, é cı́clico o código C = h0i = {0}.
Como exemplo numérico considere K = F2 e seja v = (10011001) ∈ K 8 .Temos que
hvi = K(10011001) + K(11001100) + K(01100110) + K(00110011).
A técnica para lidar com os códigos cı́clicos consiste em enriquecer a estrutura de espaço
vetorial de K n como se segue.
31
Defina Rn como sendo o anel das classes residuais em K[X] módulo X n − 1; isto é,
Rn = K[X](X
n −1)
.
Um elemento de Rn é, portanto, um conjunto da forma
[f (X)] = {f (X) + g(X)(X n − 1) : g(X) ∈ K[X]};
e a adição e a multiplicação em Rn são respectivamente definidas por
[f1 (X)] + [f2 (X)] = [f1 (X) + f2 (X)],
e por
[f1 (X)] · [f2 (X)] = [f1 (X) · f2 (X)].
Recorde também que Rn munido da multiplicação por escalares λ ∈ K, definida por
λ[f (X)] = [λf (X)],
é um K-espaço vetorial de dimensão n com base 1, [X], ..., [X n−1 ] e como tal, é isomorfo
a K n através da transformação linear
ν : K n −→
Rn
(a0 , ..., an−1 ) 7−→ [a0 + a1 X + ... + an−1 X n−1 ].
Então, todo código linear C ⊂ K n pode ser transportado para Rn mediante o isomorfismo
ν para ser estudado. A vantagem de Rn sobre K n é que, no primeiro, temos, além da
estrutura de espaço vetorial, uma estrutura adicional de anel.
Vamos determinar matrizes geradoras e matrizes teste de paridade de códigos cı́clicos.
Para isso vamos caracterizar os códigos cı́clicos em Rn .
Primeiramente, note que a ação de Tπ em K n traduz-se, por meio de ν, na multiplicação
por [X] em Rn .
De fato, tomando c = (c0 , ..., cn−1) , temos
Tπ (c) = (cn−1 , c0 , ..., cn−2
e
ν(Tπ (c)) = [cn−1 + c0 X + ... + cn−2 X n−1 ] =
[X][c0 + c1 X + ... + cn−1 X n−1 ] = [X]ν(c).
32
Lema 1: Seja V um subespaço vetorial de Rn . Então, V é um ideal de Rn se, e
somente se, V é fechado pela multiplicação por [X].
Prova: Suponhamos que V seja um ideal de Rn .
Da definição de ideal, segue que
[X][f (X)] ∈ V para todo [f (X)] ∈ V .
Reciprocamente, suponhamos que V seja fechado pela multiplicação por [X]. É suficiente mostrar que [g(X)][f (X)] ∈ V para todo [g(X)] ∈ Rn e todo [f (X)] ∈ V .
Seja [f (X)] ∈ V . Como V é um subespaço de Rn , é claro que a[f (X)] ∈ V , para todo
a ∈ K. Como por hipótese,
[Xf (X)] = [X][f (X)] ∈ V,
então
[X 2 f (X)] = [X][Xf (X)] ∈ V.
Indutivamente, obtemos, para todo m ∈ N , que
[X m f (X)] = [X m ][f (X)] ∈ V.
Agora, escrevendo [g(X)] = [a0 + a1 X + ... + an−1 X n−1 ], temos que
[g(X)][f (X)] = [g(X)f (X)] = [(a0 + a1 X + .... + an−1 X n−1 )f (X)] =
a0 [f (X)] + a1 [X][f (X)] + .... + an−1 [X n−1 ][f (X)] ∈ V,
pois V é subespaço e cada parcela da última expressão pertence a V.
Teorema 5 Um subespaço C de K n é um código cı́clico se, e somente se, ν(C) é um ideal
de Rn .
As definições enunciadas acima, juntamente com o Lema 1, provam o resultado do Teorema 1.
Portanto, temos que um código C em K n é cı́clico se, e somente se, ν(C) = I([g(X)]),
onde g(X) ∈ K[X] é um divisor de X n − 1.
Seja p= car(K). Se n = mps com m e p primos entre si, temos que
s
X n − 1 = (X m − 1)p .
33
Como (X m − 1)0 = mX m−1 6= 0, o polinômio X m − 1 não tem fator não constante em comum com a sua derivada, portanto, não possui fator múltiplo algum. Conseqüentemente,
X m − 1 = f1 ...fr ,
onde os fi são polinômios mônicos, irredutı́veis e dois a dois distintos. Logo, a decomposição em fatores irredutı́veis de X n − 1 é
s
s
X n − 1 = f1p ...frp .
Segue, então, que o polinômio X n − 1 tem exatamente (ps + 1)r divisores mônicos. Temos
então, que Rn possui precisamente (ps + 1)r ideais. Em particular, se MDC(n,p)=1, segue
que Rn tem precisamente 2r ideais.
Note que Rn não é um domı́nio de integridade, pois temos, por exemplo,
[X − 1] · [X n−1 + X n−2 + ... + X + 1] = [X n − 1] = 0.
No que se segue, g(X)denotará sempre um divisor de X n − 1, e poremos
h(X) =
Xn − 1
.
g(X)
Teorema 6 Seja I = I([g(X)]), onde g(X) é um divisor de X n − 1 de grau s. Temos que
[g(X)], [Xg(X)], [X 2 g(X)], ..., [X n−s−1 g(X)] é uma base de I como espaço vetorial sobre
K.
Prova: Os elementos acima são linearmente independentes. De fato, suponhamos que
a0 [g(X)]a1 [Xg(X)] + ... + an−s−1 [X n−s−1 g(X)] = [0].
logo,
[g(X)][a0 + a1 X + ... + an−s−1 X n−s−1 ] = [0].
Portanto, para algum d(X) ∈ K[X], temos que
g(X)(a0 + a1 X + ... + an−s−1 X n−s−1 ) = d(X) · (X n − 1).
Daı́ segue que
(a0 + a1 X + ... + an−s−1 X n−s−1 ) = d(X · h(X)).
Como o grau de H(X)é n-s, devemos ter a0 + a1 X + ... + an−s−1 X n−s−1 = 0, e conseqüentemente, a0 = a1 = ... = an−s−1 = 0.
34
Os elementos acima geram I sobre K. De fato, se [f (X)] ∈ I, temos que
f (X) ≡ d(X) · g(X)mod(X n − 1),
Pelo algoritimo da divisão, temos que d(X) = h(X) · c(X) + r(X), com r(X)= a0 + a1 X +
... + an−s−1 X n−s−1 . Logo,
f (X) ≡ d(X) · g(X) ≡ c(X) · h(X) · g(X) + r(X) · g(X)mod(X n − 1)
e portanto,
f (X) ≡ c(X)(X n − 1) + r(X) · g(X) ≡ r(X) · g(X)mod(X n − 1).
Conseqüentemente,
[f (X)] = a0 [g(X)] + a1 [Xg(X)] + ... + an−s−1 [X n−s−1 g(X)].
Corolário 4 Dado um código cı́clico C, existe v ∈ C tal que C = hvi.
Prova: Seja I = ν(C). Logo, I é gerado como K-espaço vetorial por
[g(X)], [Xg(X)], ..., [X n−s−1 g(X)],
onde g(X)é um divisor de X n − 1. Portanto, colocando v = ν −1 ([g(X)]), temos que C é
gerado por v, Tπ v, ..., Tπn−s−1 v, e portanto, C = hvi.
Corolário 5 Seja g(X) = g0 + g1 X + ... + gs X s um divisor de X n − 1 de grau s. Se
I = I([g(X)]), então
dimk I = n − s,
e o código C = ν −1 (I) tem matriz geradora

 

−1
ν ([g(X)])
g0 g1 . . . gs 0 . . . 0

 

−1
 ν (X[g(X)])   0 g0 g1 . . . gs . . . 0 

 

G=
=.
.
.
.
.
.
.
..
..
..
..
.. 

  ..

 

−1
n−s−1
ν ([X
g(X)])
0 . . . 0 g0 . . .
gs
Dado um polinômio h(X) = h0 +h1 X +...+ht X t que divide X n −1, o polinômio recı́proco
de h(X),
h∗ (X) = X t h(1/X) = ht + ht−1 X + ... + h0 X t ,
é também um divisor de X n −1, e portanto, é o polinômio gerador de algum código cı́clico.
35
Teorema 7 Seja C = ν −1 (I) um código cı́clico, onde I = I([g(X)]), com g(X) um divisor
de X n − 1. Então C ⊥ é cı́clico e C ⊥ =ν −1 (J), onde J = I([h∗ (X)]).
Prova: Ponhamos
g(X) = g0 + g1 X + ... + gs X s e h(X) = h0 + h1 X + ... + hn−s X n−s .
Note que gr(h(X))= n-s, e portanto, hn−s 6= 0.
Sejam


g0 g1 . . . gs 0 . . . 0


 0 g0 g1 . . . gs . . . 0 


G=.

.
.
.
.
..
..
..
.. 
 ..


0 . . . 0 g0 . . .
gs
e







hn−s hn−s−1
...
h0
0
...
h0 . . .
..
.
0
..
.
hn−s
..
.
hn−s−1
..
.
0
...
0
hn−s . . .
...
0


0

.
.. 
.

h0
As linhas de H são linearmente independentes. Seja {e1 , ..., en } a base canônica de K n .
A i-ésima linha de G é
Gi = g0 ei + g1 ei + ... + gs ei+s , 1 ≤ i ≤ n − s,
e a j-ésima coluna de H t é
Hj = hn−s ej + hn−s−1 ej+1 + ... + h0 ej+n−s , 1 ≤ j ≤ s.
Suponhamos que i ≤ j. O produto interno de Gi por Hj é dado por
gj−i hn−s + gj−i+1 hn−s−1 + ... + g0 hj−i ,
onde j − i = 0, ..., s − 1. Mas a soma acima é exatamente o coeficiente de X n−s+j−i no
produto de g(X) · h(X)(= X n − 1). Como 1 ≤ n − s + j − i ≤ n − 1, temos que esse
coeficiente é igual a zero. O caso j ≤ i é análogo. Fica, então, provado que G · H t = 0, e
36
portanto, H é uma matriz geradora de C ⊥ . Agora,


ν −1 ([h∗ (X)])


 ν −1 (X[h∗ (X)]) 


H=
,
.
..




ν −1 ([X n−s−1 h∗ (X)])
portanto, temos que C ⊥ = ν −1 (J), onde J = I([h ∗ (X)]).
Corolário 6 A matriz teste de paridade de C = ν −1 (I), em que I = I([g(X)]) é dada
por

hn−s hn−s−1



H=


onde
...
h0
0
...
h0 . . .
..
.
0
..
.
hn−s
..
.
hn−s−1
..
.
0
...
0
...
hn−s . . .
0


0

,
.. 
.

h0
Xn − 1
= h0 + h1 X + ... + hn−s X n−s .
g(X)
Este corolário já foi provado no teorema imediatamente anterior.
4.2
Decodificação em códigos cı́clicos
Seja,
]
µ : K s −→ K[Xs−1 ⊂ K[X]
(a0 , ..., as−1 ) 7−→
s−1
X
ai X i
i=0
o isomorfismo de K-espaços vetoriais, onde K[X]s−1 é o espaço vetorial dos polinômios de
grau menor ou igual a s-1.
Teorema 8 Seja C ⊂ K n um código cı́clico. Suponhamos que C = ν −1 (I), onde I =
I([g(X)]), com g(X) um divisor de X n − 1. Seja R a matriz (n − s) × s cuja i-ésima linha
é
Ri = −µ−1 (ri (X)), 1 ≤ i ≤ n − s,
onde ri (X) é resto da divisão de X s−1+i por g(X). Então, (R | Idn−s ) é uma matriz geradora de C.
37
Prova: Sejam qi (X) e ri (X) o quociente e o resto da divisão de X s−1+i por g(X). Logo,
X s−1+i = g(X)qi (X) + ri (X), com Ri (X) = 0 ou degri (X) ≤ s − 1.
Portanto, [X s−1+i − ri (X)] pertence a I, e é evidente que esses vetores para i = 1, ..., n − s
são linearmente independentes sobre K. Como ν([X s−1+i − ri (X)]) = es−1+i − µ−1 (ri (X)),
temos que a matriz


1 0 ... 0


 −µ−1 (r2 (X)) 0 1 . . . 0



..
.. ..
.. 

.
. .
.


−1
−µ (rn−s (X)) 0 0 . . . 1
−µ−1 (r1 (X))
é uma matriz geradora de C.
Discutiremos, agora, o algoritmo de codificação.
Os elementos de C podem ser considerados como codificação do código da fonte K n−s .
Dado (a1 , ..., an−s ) ∈ K n−s , esse vetor pode ser codificado como elemento de C:
(a1 , ..., an−s )(R|Idn−s ) = (b0 , ..., bs−1 , a1 , ..., an−s ),
onde
(b0 , ..., bs−1 ) = −a1 µ−1 (r1 (X)) − ... − an−s µ−1 (rn−s (X)) =
n−s
X
−µ (
ai ri (X)).
−1
i=1
Exemplo 11 Considere o polinômio X 7 − 1 sobre F2 . A fatoração de X 7 − 1 é dada por
X 7 − 1 = (1 + X)(1 + X + X 3 )(1 + X 2 + X3).
Vamos considerar o código C ⊂ F27 gerado pelo polinômio g(X) = 1 + X + X 3 . A
dimensão de C é 4. Agora, determinaremos uma matriz geradora desse código na forma
padrão:
X 3 = (X 3 + X + 1) + (X + 1)
X 4 = (X 3 + X + 1)X + (X 2 + X)
X 5 = (X 3 + X + 1) + (X 2 + 1) + (X 2 + X + 1)
X 6 = (X 3 + X + 1) + (X 3 + X + 1) + (X 2 + 1).
38
Logo, temos que uma matriz geradora

1

0

G0 = 
1

1
de C é dada por
1 0 1 0 0
1 1 0 1 0
1 1 0 0 1
0 1 0 0 0

0

0

.
0

1
Suponha que seja dado o vetor (a1 , a2 , a3 , a4 ) ∈ F24 , do código da fonte, então a
codificação desse vetor é dada por
(b0 , b1 , b2 , a1 , a2 , a3 , a4 ),
onde b0 , b1 e b2 são os coeficientes do polinômio
a1 (X + 1) + a2 (X 2 + X) + a3 (X 2 + X + 1) + a4 (X 2 + 1) =
a1 + a3 + a4 + (a1 + a2 + a3 )X + (a2 + a3 + a4 )X 2 .
Portanto a codificação de (a1 , a2 , a3 , a4 ) é
(a1 + a3 + a4 , a1 + a2 + a3 , a2 + a3 + a4 , a1 , a2 , a3 , a4 ).
Teorema 9 Seja C ⊂ K n um código cı́clico gerado por um polinômio mônico g(X) com
matriz geradora na forma padrão (R | Id) e matriz teste de paridade H = (Id | −Rt ). Se
v = (υ0 , ..., υn−1 )inK n , então a sı́ndrome de v com relação à matriz H é dada por
µ−1 (r(X)),
onde r(X) é o resto da divisão de υ0 + υ1 (X) + ... + υn−1 X n−1 por g(X).
Prova:A sı́ndrome de v é o vetor
(Id| − Rt )v t =
(µ−1 (1), µ−1 (X), ..., µ−1 (X s−1 ), µ−1 (r1 (X)), ..., µ−1 (rn−s (X)))v t =
µ(−1)(υ0 + υ1 (X) + ... + υs−1 X s−1 + υs r1 (X) + ... + υn−1 rn−s (X)),
o que implica o resultado, visto que
r(X) = υ0 + υ1 (X) + ... + υs−1 X s−1 + υs r1 (X) + ... + υn−1 rn−s (X)
é o resto da divisão de υ0 + υ1 (X) + ... + υn−1 X n−1 por g(X).
Exemplo 12 Considere o código do exemplo anterior. A matriz teste de paridade asso-
39
ciada a G0 é a matriz


1 0 0 1 0 1 1


.
H=
0
1
0
1
1
1
0


0 0 1 0 1 1 1
Dado o vetor (1101001) ∈ F28 , a sua sı́ndrome relativa a H é dada por µ−1 (r(X)),
onde r(X) é o resto da divisão de 1 + X + X 3 + X 6 por g(X) = 1 + X + X 3 . Portanto,
r(X) = X 2 + 1, e conseqüentemente, a sı́ndrome é (101).
40
Bibliografia
[1] Hefez, Abramo; Códigos Corretores de Erros; Rio de Janeiro, 2002, (Coleção
Matemática Universitária).
[2] Voloch, José Felipe Códigos Corretores de Erros, Rio de Janeiro, CNPq: IMPA,
(Coleção Matemática Universitária).
[3] Blake, Ian F; An Introduction to Algebraic Combinatorial Coding Theory; Academic
Press.
[4] Pretzel, Oliver; Codes and Algebraic Curves; Oxford Lectures Series in Mathematics
and its Applications, Clarendon Press, Oxford, 1998.
[5] Shannon, Claude Eloowd; A Matematical Theory of Communication; Bell System
Tech. vol. 27 (1948) 379 - 423, 623 - 656.
[6] Goppa, V. D., Geometry and Codes, Mathematics and its Applications; vol. 24,
Kluwer, Dordricht, 1991.
[7] Hoholdt, van Lint and Pellikam; Algebraic Geometry Codes; Handbook on Coding
Theory (V.S.Pless, W.C. Huffman, Eds), Elvesier, 1998.
[8] H. Stichtenoth; Algebraic Function Fields and Codes; Springer - Verlag, 1993.
[9] Burgess, Walty; Matrices and Coding Theory - A very brief introduction; University
of Ottawa (pre-print).
[10] Lint, J. H. Van; Introduction to Coding Theory; Springs - Verlag, N. Y., 1982.
[11] Matthew E. Jachn; Introduction to Algebraic Coding Theory with emphases on
Algorithmic Decoding of the Reed - Solomon Codes; April. 2003, (paper)
[12] Boswell, Dustin; An Introduction to Coding Theory; 2001, (pre-print)
[13] Ward, Harold W; An Introduction to Algebraic Coding Theory; (pre-print)
[14] Kim, Seon Jeong; Introduction to Coding Theory and Algebraic Geometric Codes;
Proccedings of Workshops in Pure Mathematics, vol. 18, part I (1998).
[15] S.C. Coutinho; Números Inteiros e Criptografia RSA; Série de Computação e
Matemática, IMPA/SBM, 1997.