ads:
UNIVERSIDADE FEDERAL DE GOI
´
AS
INSTITUTO DE MATEM
´
ATICA E ESTAT
´
ISTICA
C
´
ODIGOS GEOMETRICAMENTE UNIFORMES EM ESPAC¸ OS HIPERB
´
OLICOS
Por
ANA PAULA FARIA MACHADO
Orientador: Prof. Dr. M
´
ARIO JOS
´
E DE SOUZA
DISSERTAC¸
˜
AO DE MESTRADO EM MATEM
´
ATICA
GOI
ˆ
ANIA, GOI
´
AS
2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
UNIVERSIDADE FEDERAL DE GOI
´
AS
INSTITUTO DE MATEM
´
ATICA E ESTAT
´
ISTICA
COORDENAC¸
˜
AO DE P
´
OS-GRADUAC¸
˜
AO EM MATEM
´
ATICA
C´odigos Geometricamente Uniformes em Espa¸cos Hiperb´olicos
por
Ana Paula Faria Machado
´
Area de concentra¸c˜ao:
´
Algebra
Orientador: Prof. Dr. M´ario Jos´e de Souza
Disserta¸c˜ao submetida `a Banca Examinadora designada pelo Conselho Diretor do
Instituto de Matem´atica e Estat´ıstica, como parte dos requisitos necess´arios `a ob-
ten¸c˜ao do grau de Mestre em Matem´atica.
Goiˆania - Goi´as
2008
ads:
A Deus.
DEDICO
Agradecimentos
A Deus, o Senhor de todas as coisas, quem me criou e me capacitou a chegar at´e
aqui.
`
A Nossa Senhora e `a Santa Edwirges, que sempre intercederam por mim.
Ao Professor Doutor M´ario Jos´e de Souza pela grande aten¸c˜ao, paciˆencia e
dedica¸c˜ao que teve comigo durante as orienta¸c˜oes. Seu aux´ılio foi fundamental no
meu desenvolvimento. Muito obrigada!
`
A minha fam´ılia, em especial aos meus pais Maurita e Sebasti˜ao que sempre me
apoiaram incondicionalmente, me incentivando a cada dia. Eu os amo muito.
Ao meu amado Dalmo Luiz, por todo amor e compreens˜ao.
Aos professores do Corpo Docente do Mestrado em especial `aqueles com quem cursei
alguma disciplina.
Aos meus colegas que, durante o per´ıodo de aula, tanto contribu´ıram para a minha
forma¸c˜ao em bons momentos de estudo.
`
A Banca Examinadora pela disponibilidade e aten¸c˜ao dispensada ao meu trabalho.
Ao CNPq pelo apoio financeiro.
Sum´ario
Introdu¸c˜ao 1
1 Preliminares 3
1.1 Grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Classes Laterais . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Grupos Quocientes . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Homomorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.5 A¸c˜oes de grupos . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Espa¸cos M´etricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Geometria Hiperb´olica . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 C´odigos Corretores de Erros . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 C´odigos Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 C´odigos Geometricamente Uniformes 17
2.1 Isometrias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Conjuntos de Sinais Geometricamente Uniformes . . . . . . . . . . . 19
2.3 Conjuntos de Sinais Geometricamente Uniformes e a Comunica¸c˜ao
Digital . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Propriedades Sim´etricas de Conjuntos de
Sinais Geometricamente Uniformes . . . . . . . . . . . . . . . . . . . 21
2.5 Parti¸c˜oes Geometricamente Uniformes . . . . . . . . . . . . . . . . . 23
i
2.6 Rotulamentos Isom´etricos . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7 Propriedades Elementares dos Rotulamentos Isom´etricos . . . . . . . 26
2.8 Rotulamentos Bin´arios Isom´etricos . . . . . . . . . . . . . . . . . . . 27
2.9 C´odigos Geometricamente Uniformes em Espa¸cos de Sinais . . . . . . 29
2.9.1 Espa¸cos de Seq¨uˆencias . . . . . . . . . . . . . . . . . . . . . . 29
2.9.2 C´odigos em Espa¸cos de Sinais . . . . . . . . . . . . . . . . . . 30
2.9.3 Classes Laterais de C´odigos Generalizadas . . . . . . . . . . . 31
2.10 Outras No¸c˜oes de Uniformidade . . . . . . . . . . . . . . . . . . . . . 33
2.10.1 Linearidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.10.2 Subconjunto Tempo-Zero . . . . . . . . . . . . . . . . . . . . . 35
2.10.3 Rotulamentos Regulares . . . . . . . . . . . . . . . . . . . . . 36
3 C´odigos Hiperb´olicos Geometricamente Uniformes 38
3.1 Tessela¸c˜oes Hiperb´olicas . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Conjuntos de Sinais Associados a Grupos . . . . . . . . . . . . . . . . 40
3.3 Conjuntos de Sinais Geometricamente Uniformes Hiperb´olicos . . . . 41
3.4 Parti¸c˜oes Geometricamente Uniformes Hiperb´olicas . . . . . . . . . . 41
3.5 C´odigos Geometricamente Uniformes em Espa¸co de Sinais Hiperb´olicos 42
Conclus˜ao 48
Referˆencias Bibliogr´aficas 49
ii
Resumo
Nesta disserta¸c˜ao definimos c´odigos geometricamente uniformes em espa¸cos eu-
clideanos, apresentando algumas propriedades sim´etricas destes c´odigos. Constru´ı-
mos parti¸c˜oes geometricamente uniformes e a partir destas definimos classes
laterais de c´odigos generalizadas. Estendemos aos espa¸cos hiperb´olicos o conceito
de c´odigos geometricamente uniformes. Mostramos tamb´em uma caracteriza¸c˜ao de
classes laterais generalizadas atrav´es do conceito de c´odigos G − lineares.
iii
Abstract
In this dissertation we define geometrically uniform codes in Euclidean spaces, pre-
senting some symmetrical properties of these codes. Build geometrically uniforme
partitions and starting these we define generalized coset codes. We generalize the
concept of geometrically uniform codes to hyperbolic spaces. We show a character-
ization of generalized coset codes through the concept of G − linear codes.
iv
Introdu¸c˜ao
A teoria dos c´odigos corretores de erros e dos sistemas de comunica¸c˜ao digital as-
sumiu a forma atual a partir do trabalho fundamental de Shannon [10], do labo-
rat´orio de Bell, publicado em 1948. Neste trabalho foi mostrado que dado um canal
de comunica¸c˜ao digital ´e poss´ıvel, com uma codifica¸c˜ao adequada, transmitir in-
forma¸c˜oes com probabilidade de erro arbitrariamente pequena. O trabalho inicial
para aquisi¸c˜ao de bons c´odigos foi ´arduo, pois exigia um profundo conhecimento de
´algebra abstrata e teoria da probabilidade, sendo desenvolvido por um grupo restrito
composto apenas por matem´aticos nas d´ecadas de 50 e 60.
Os elementos dos c´odigos corretores de erros s˜ao seq¨uˆencias de s´ımbolos perten-
centes a um alfabeto, tomado freq¨uentemente entre os elementos de algum grupo,
por exemplo, d´ıgitos bin´arios ou vetores. Mesmo quando os s´ımbolos n˜ao tˆem uma
estrutura natural, um procedimento natural e ´util ´e produzir um rotulamento dos
s´ımbolos do alfabeto por elementos de algum grupo (ou seja, definir uma aplica¸c˜ao
injetora do alfabeto no grupo, sujeita a determinadas condi¸c˜oes).
Os conjuntos de sinais e os c´odigos corretores de erros que os tˆem como alfabeto
apresentam, em geral, algum tipo de estrutura capaz de permitir a determina¸c˜ao
de suas propriedades e tornar mais pr´atica a sua implementa¸c˜ao. As estruturas
alg´ebricas s˜ao a base de muitos c´odigos conhecidos e importantes, al´em disso, o
estabelecimento de um conceito adequado de distˆancia e o processo de avalia¸c˜ao de
distˆancias entre as palavras e as palavras-c´odigo s˜ao fundamentais no processo de
decodifica¸c˜ao.
O conceito de conjunto de sinais geometricamente uniforme foi introduzido por
1
David Forney [4] em 1991. Foram utilizados neste contexto espa¸cos e conjuntos de
sinais euclideanos.
Em 2005 Henrique Lazzari e Reginaldo Palazzo em [7] estendem os conceitos de
constela¸c˜oes, reticulados e particionamento ao plano hiperb´olico. Apesar dos grupos
de isometrias hiperb´olicos apresentarem maior complexidade quando comparados
aos grupo de isometrias euclideanos, a teoria de parti¸c˜oes geometricamente uniformes
se estende a estes.
O Cap´ıtulo 1 traz uma descri¸c˜ao das propriedades b´asicas de estruturas alg´ebricas
e m´etricas de maior importˆancia para a teoria de comunica¸c˜ao. Tamb´em traz uma
introdu¸c˜ao `a teoria de c´odigos corretores de erros. Uma grande parte das demons-
tra¸c˜oes deste cap´ıtulo foram omitidas podendo ser encontradas em [6], [9], [11] e
[5].
No Cap´ıtulo 2 s˜ao definidos conjuntos de sinais geometricamente uniformes em
espa¸cos euclideanos e verificamos algumas propriedades sim´etricas destes conjun-
tos. Apresentamos a teoria das parti¸c˜oes geometricamente uniformes, em seguida,
definimos rotulamentos isom´etricos e suas propriedades. Introduzimos o conceito
de c´odigos geometricamente uniformes em espa¸cos de sinais e encerramos o cap´ıtulo
com outras no¸c˜oes de uniformidade.
Finalizamos no Cap´ıtulo 3 definindo G − linearidade, tessela¸c˜oes regulares e
estendendo ao plano hiperb´olico a teoria das parti¸c˜oes geometricamente uniformes,
atrav´es do conceito de c´odigos G − lineares.
2
Cap´ıtulo 1
Preliminares
Neste cap´ıtulo s˜ao apresentadas no¸c˜oes gerais sobre Teoria de Grupos, Espa¸cos
M´etricos, Geometria Hiperb´olica e C´odigos. Muitas demonstra¸c˜oes s˜ao omitidas.
Para maiores detalhes em rela¸c˜ao `as no¸c˜oes acima mencionadas indicamos [5], [6],
[9] e [11].
1.1 Grupos
Uma opera¸c˜ao bin´aria num conjunto n˜ao vazio G ´e uma fun¸c˜ao
µ : G × G → G
que a cada par ordenado (a, b) de elementos de G associa um elemento µ(a, b) de G,
chamado de produto de a e b, o qual denotaremos por ab. Uma opera¸c˜ao bin´aria ´e
dita associativa se (a · b) · c = a · (b · c) para quaisquer a, b, c ∈ G.
Defini¸c˜ao 1.1. Um grupo consiste num conjunto n˜ao vazio G munido de uma
opera¸c˜ao bin´aria que satisfaz as seguintes propriedades:
G1: (a · b) · c = a · (b · c) (Associatividade)
G2: Existe e ∈ G tal que e · a = a ∀a ∈ G (Elemento neutro)
3
G3: ∀a ∈ G, existe b ∈ G tal que b · a = e (Existˆencia de inverso)
Exemplo 1.2. O grupo geral linear GL(n, R). Se G = GL(n, R) denota o conjunto
de todas as matrizes n × n invert´ıveis com entradas reais e µ ´e a multiplica¸c˜ao usual
de matrizes (A, B) → AB, ent˜ao G ´e um grupo.
Exemplo 1.3. O grupo das permuta¸c˜oes de um conjunto X. Seja G = S(X) o
conjunto de todas fun¸c˜oes bijetivas φ : X → X munido da opera¸c˜ao composi¸c˜ao de
fun¸c˜oes.
Exemplo 1.4. O conjunto G = Z com a opera¸c˜ao usual de adi¸c˜ao de n´umeros
inteiros tamb´em ´e um grupo.
Observa¸c˜ao 1.5. Seja G um grupo, se para todos x, y ∈ G temos x · y = y · x
dizemos que G ´e um grupo comutativo ou abeliano.
1.1.1 Subgrupos
Seja G um grupo e H um subconjunto de G dizemos que H ´e um subgrupo de G se
verificar as seguintes condi¸c˜oes:
S1: H n˜ao ´e vazio.
S2: Se a, b ∈ H, ent˜ao a · b ∈ H
S3: Se a ∈ H, ent˜ao a
−1
∈ H
Usaremos a nota¸c˜ao H ≤ G para indicar que H ´e um subgrupo de G.
Defini¸c˜ao 1.6. Se S ´e um subconjunto n˜ao vazio de um grupo G, definimos o grupo
gerado por S, e denotado por S, como:
S =
j
H
j
onde H
j
s˜ao os subgrupos de G que contˆem S. Assim S ´e o menor subgrupo de G
que cont´em S.
4
Defini¸c˜ao 1.7. Um subgrupo de G da forma a, para algum a ∈ G, ´e chamado
um subgrupo c´ıclico de G.
Defini¸c˜ao 1.8. Se G = g onde g ∈ G dizemos que G ´e um grupo c´ıclico.
Defini¸c˜ao 1.9. Um grupo G ´e dito um grupo finito, se como conjunto G ´e finito.
Nesse caso, o seu n´umero de elementos ´e denotado por |G|, e chamado a ordem de
G.
1.1.2 Classes Laterais
Seja H um subgrupo de um grupo G e x ∈ G o subconjunto de G
Hx = {hx; h ∈ H}
´e chamado classe lateral a direita de H em G. De maneira an´aloga se define classe
lateral a esquerda de H em G. Quando o conjunto das classes laterais (`a direita ou
`a esquerda) de H em G for um conjunto finito, dizemos que H ´e um subgrupo de
´ındice finito em G e o n´umero de classes laterais ´e chamado o ´ındice de H em G e
denotado por |G : H|.
Teorema 1.10. (Lagrange) Se G ´e um grupo finito e H ´e um subgrupo de G ent˜ao
|G| = |H||G : H|.
1.1.3 Grupos Quocientes
Sejam G um grupo e H ≤ G. Ao conjunto de todas as classes laterais `a esquerda
(`a direita) denominamos conjunto quociente e o denotamos por
G
H
.
Defini¸c˜ao 1.11. Um subgrupo H de um grupo G diz-se normal em G se ocorre
uma (e portanto todas) das condi¸c˜oes equivalentes
1. Hx = xH, para todo x ∈ G
5
2. xHx
−1
= H, para todo x ∈ G
3. xHx
−1
⊂ H, para todo x ∈ G
Escrevemos H ✂ G para dizer que H ´e um subgrupo normal de G.
Quando H ✂ G,
G
H
´e um grupo chamado de grupo quociente de G por H. No
caso de
G
H
ser um grupo finito a sua ordem ´e o ´ındice |G : H| de H em G. Se o
pr´oprio G for finito, o Teorema de Lagrange diz que
G
H
=
|G|
|H|
.
1.1.4 Homomorfismos
Defini¸c˜ao 1.12. Sejam (G, ·) e (G
, ∗) dois grupos. Uma aplica¸c˜ao f : G → G
satisfazendo
f(a · b) = f (a) ∗ f(b)
para todos a, b ∈ G, ´e dita um homomorfismo de grupos. Se f for tamb´em uma
fun¸c˜ao bijetora, dizemos que f ´e um isomorfismo entre G e G
. Se G e G
s˜ao
isomorfos escrevemos G
∼
=
G
.
Defini¸c˜ao 1.13. Se f : G → G
´e um homomorfismo de grupos, o subconjunto
ker(f) = {g ∈ G : f(g) = e
G
}
´e chamado n´ucleo de f.
Encerramos esta subse¸c˜ao, apresentando um resultado que avalia os subgrupos
de
G
H
em fun¸c˜ao dos subgrupos de G
Teorema 1.14. Seja H um subgrupo normal de um grupo G e π : G →
G
H
a
proje¸c˜ao canˆonica. Ent˜ao π induz uma correspondˆencia bijetora entre o conjunto
S
H
dos subgrupos de G que contˆem H e o conjunto S dos subgrupos de
G
H
, dada por:
V ∈ S
H
→ π(V ) =
V
H
∈ S.
Al´em disso, tem-se:
6
(a) Se V, L ∈ S
H
, ent˜ao V ⊆ L ⇔ π(V ) ⊆ π(L).
(b) Se V, L ∈ S
H
, com V ⊆ L, ent˜ao | L : V |=| π(L) : π(V ) | .
(c) Se V, L ∈ S
H
, ent˜ao V ✂ L ⇔ π(V ) ✂ π(L).
(d) Se V, L ∈ S
H
, com V ✂ L, ent˜ao
L
V
✂
π(L)
π(V )
.
1.1.5 A¸c˜oes de grupos
Uma a¸c˜ao (`a esquerda) de um grupo G num conjunto X ´e uma fun¸c˜ao
ϕ : G × X → X
satisfazendo:
(A1) ϕ(g, ϕ(h, x)) = ϕ(gh, x), ∀g, h ∈ G, ∀x ∈ X.
(A2) ϕ(e, x) = x, ∀x ∈ X (e ∈ G ´e a identidade de G).
Analogamente define-se uma a¸c˜ao `a direita de um grupo G num conjunto X.
Exemplo 1.15. G = GL(n, R) e X = R
n
. A a¸c˜ao ϕ ´e a multiplica¸c˜ao usual de uma
matriz n × n por um vetor (coluna) n × 1.
Exemplo 1.16. Seja G um grupo e X = G. A fun¸c˜ao definida por (g, x) → gxg
−1
´e uma a¸c˜ao de G em G chamada a¸c˜ao por conjuga¸c˜ao.
Defini¸c˜ao 1.17. Se um grupo G age num conjunto X e x ∈ X, o subconjunto de
X,
O(x) = {g · x : g ∈ G},
´e chamado de ´orbita de x.
Lema 1.18. Se G ´e um grupo agindo num conjunto X, ent˜ao:
(a)
X =
x∈X
O(x),
7
(b) Se x, y ∈ X, ent˜ao O(x)
O(y) = ∅, ou O(x) = O(y).
Defini¸c˜ao 1.19. Um subconjunto S de X que corta cada ´orbita da a¸c˜ao de G em X
em um ´unico ponto ´e chamado conjunto de representantes de ´orbitas. (Tal conjunto
sempre existe, pelo Axioma da Escolha).
Defini¸c˜ao 1.20. Se G age num conjunto X e x ∈ X, o subgrupo de G
G
x
= {g ∈ G : g · x = x}
´e chamado estabilizador de x ou grupo de isotropia de x.
Se para algum x
0
∈ X, G
x
0
= G, diz-se que x
0
´e um ponto fixo pela a¸c˜ao de G.
O conjunto dos pontos fixos de X ´e denotado por F ix(X).
Exemplo 1.21. G = GL(n, R) e X = R
n
.
G
X
possui dois elementos {±I} e
F ix(X) = {(0, ..., 0)}.
Defini¸c˜ao 1.22. Uma a¸c˜ao de um grupo G num conjunto X diz-se transitiva se
ocorrer uma (e portanto todas) das trˆes condi¸c˜oes equivalentes:
(i) ∃x ∈ X tal que O(x) = X
(ii) ∀x, y ∈ X, ∃g ∈ G tal que x = g.y.
(iii) ∀x ∈ X, O(x) = X.
1.2 Espa¸cos M´etricos
Defini¸c˜ao 1.23. Um conjunto E ´e dito um espa¸co m´etrico se existe uma fun¸c˜ao
d : E × E → R
denominada m´etrica ou distˆancia satisfazendo para todos x, y, z ∈ E as seguintes
propriedades:
8
E1) d(x, y) ≥ 0 e d(x, y) = 0 se, e somente se, x = y,
E2) d(x, y) = d(y, x),
E3) d(x, z) ≤ d(x, y) + d(y, z).
Geralmente o espa¸co m´etrico ´e denotado por (E, d) ou simplesmente E, quando
n˜ao houver ambiguidade.
Exemplo 1.24. Um conjunto E finito torna-se um espa¸co m´etrico munido com a
m´etrica definida por:
d(x, y) =
0, se x=y;
1, se x = y.
(1.1)
Ent˜ao d ´e denominada m´etrica discreta. Sejam E
n
um espa¸co n-dimensional e
d
H
=
n
i=1
d(x
i
, y
i
),
com d(x
i
, y
i
) a m´etrica discreta. Ent˜ao d
H
´e uma m´etrica em E
n
, chamada de
m´etrica de Hamming. Seja E = F
q
um corpo finito, onde q ´e uma potˆencia de
um n´umero primo. Definamos para um x ∈ F
n
q
o peso de Lee do elemento x por:
ω
L
(x) =
n
i=1
|x
i
|, onde
|x
i
| =
x
i
, se 0 ≤ x
i
≤
q
2
;
q − x
i
, se
q
2
≤ x
i
≤ q − 1.
(1.2)
Desse modo a distˆancia de Lee entre x, y ∈ F
n
q
´e dada por d
L
(x, y) = ω
L
(x − y).
Seja p um elemento num espa¸co m´etrico E e δ > 0 um valor real. A bola aberta
de centro p e raio δ ´e o conjunto S(p, δ) dos elementos de E cuja distˆancia ao ponto
p ´e menor do que δ, simbolicamente,
S(p, δ) = {x ∈ E : d(p, x) < δ}.
Dado um ponto p ∈ E dizemos que o mesmo ´e um ponto isolado quando ele ´e
uma bola aberta em E, isto ´e, quando existe δ > 0 tal que S(p, δ) = {p}. Um espa¸co
m´etrico ´e denominado discreto quando todos seus pontos s˜ao isolados.
9
1.3 Geometria Hiperb´olica
Existem v´arios modelos interessantes para a geometria hiperb´olica. Aqui apresen-
tamos um modelo para o plano hiperb´olico, baseado no semi-plano direito:
SP D = {z = x + iy ∈ C|Re(z) > 0}.
As retas (geod´esicas) em SP D s˜ao os seguintes subconjuntos: as semi-retas
ortogonais ao eixo imagin´ario
y = c, c ∈ R,
e os semic´ırculos ortogonais ao eixo imagin´ario dados por
x
2
+ (y − p)
2
= R
2
,
com p, R ∈ R, R > 0.
A seguir definimos uma distˆancia entre os pontos do SP D.
Seja γ : [a, b] → SPD uma curva continuamente diferenci´avel (de classe C
1
), tal
que γ(t) = (x(t), y(t)). Definimos seu comprimento por
||γ|| =
b
a
||γ
(t)||
x(t)
dt
=
b
a
(dx/dt)
2
+ (dy/dt)
2
x(t)
dt.
Pela regra da cadeia, verifica-se que este comprimento depende apenas do tra¸co
da curva, isto ´e, se φ : [a
, b
] → [a, b] for um difeomorfismo, ent˜ao ¯γ = γ ◦ φ ´e uma
curva com o mesmo tra¸co e ||γ|| = ||¯γ||. Desse modo, consideramos as curvas no
intervalo I = [0, 1].
A fun¸c˜ao d
SP D
: SP D × SP D → R
+
tal que d
SP D
(z, w) = inf ||γ||, para todo γ
de classe C
1
com γ(0) = z e γ(1) = w, ´e uma m´etrica.
Determinaremos a seguir as isometrias de (SP D, d
SP D
).
Uma matriz A =
a b
c d
∈ SL(2, R) (matrizes com determinante 1) induz
uma transforma¸c˜ao
10
T
A
: SP D → SP D
z → T
A
(z) =
a¯z+bi
−c¯zi+d
(1.3)
onde ¯z denota o complexo conjugado de z = x + iy.
Temos que
Re
a¯z + bi
−c¯zi + d
= Re
(a¯z + bi)(−c¯zi + d)
| − c¯zi + d|
2
.
De modo que
Re
a¯z + bi
−c¯zi + d
> 0 ⇔ Re((a¯z + bi)(−c¯zi + d)) > 0.
Mas
Re((a¯z + bi)(−c¯zi + d)) = Re([a(x − iy) + ib][(d − cy) + icx]) = x(ad − bc) = x,
pois ad − bc = 1, de modo que Re(z) > 0 se, e somente se, Re(T
A
(z)) > 0, ou seja,
T
A
´e uma transforma¸c˜ao do SP D.
Teorema 1.25. As transforma¸c˜oes T
A
: SP D → SP D s˜ao isometrias, ou seja,
preservam comprimento de curvas ||T
A
◦ γ|| = ||γ|| e, conseq¨uentemente, tamb´em a
distˆancia entre pontos (d(z, w) = d(T
A
(z), T
A
(w))).
Demonstra¸c˜ao: Seja γ : [a, b] → SP D diferenci´avel.
O caminho T
A
◦ γ : [a, b] → SP D ´e tal que
||T
A
◦ γ|| =
b
a
||T
A
(γ(t))γ
(t)||
ReT
A
(γ(t))
dt
=
b
a
||T
A
(γ(t))||
ReT
A
(γ(t))
||γ
(t)||dt
=
b
a
||γ
(t)||
Re(γ(t))
= ||γ(t)||.
Logo, d
SP D
(z, w) = inf ||γ||; γ(a) = z e γ(b) = w
⇒ d
SP D
(z, w) = inf ||T
A
◦ γ||; T
A
◦ γ(a) = T
A
(z) e T
A
◦ γ(b) = T
A
(w)
⇒ d
SP D
(z, w) = d
SP D
(T
A
(z), T
A
(w)) ∀z, w ∈ SP D.
Portanto, T
A
´e uma isometria de (SP D, d
SP D
).
11
1.4 C´odigos Corretores de Erros
Seja A um conjunto finito chamado de alfabeto, um c´odigo corretor de erros ´e um
subconjunto pr´oprio qualquer C de A
n
, onde n ´e um n´umero natural, e uma palavra
u ∈ A
n
ser´a representada por (u
1
, u
2
, . . . , u
n
).
Defini¸c˜ao 1.26. Dados u, v ∈ A
n
, a distˆancia de Hamming entre u e v ´e definida
como
d(u, v) := |{i : u
i
= v
i
, 1 ≤ i ≤ n}|.
E a distˆancia m´ınima de um c´odigo C ´e o n´umero
d(C) := min{d(u, v) : u, v ∈ C e u = v}.
Proposi¸c˜ao 1.27. Dados u, v, w ∈ A
n
, valem as seguintes propriedades:
i. Positividade: d(u, v) ≥ 0, valendo a igualdade se, somente se, u = v
ii. Simetria: d(u, v) = d(v, u)
iii. Desigualdade Triangular: d(u, v) ≤ d(u, w) + d(w, v)
Demonstra¸c˜ao: As propriedades i e ii s˜ao de f´acil verifica¸c˜ao, demonstraremos a
seguir a terceira propriedade.
A contribui¸c˜ao das i-´esimas coordenadas de u e v para d(u, v) ´e igual a zero se
u
i
= v
i
e igual a um se u
i
= v
i
.
No caso em que a contribui¸c˜ao ´e zero, certamente a contribui¸c˜ao das i-´esimas
coordenadas a d(u, v) ´e menor ou igual a das i-´esimas coordenadas a d(u, w)+d(w, v)
(= 0, 1 ou 2).
No outro caso, temos que u
i
= v
i
e, portanto, n˜ao podemos ter u
i
= w
i
e w
i
= v
i
.
Consequentemente, a contribui¸c˜ao das i-´esimas coordenadas a d(u, w) + d(w, u) ´e
maior ou igual a 1, que ´e a contribui¸c˜ao das i-´esimas coordenadas a d(u, v).
As propriedades contidas na Proposi¸c˜ao 1.27 mostram que a distˆancia de Ham-
ming caracteriza uma m´etrica em A
n
a chamada m´etrica de Hamming.
12
Defini¸c˜ao 1.28. Dado um c´odigo C com distˆancia m´ınima d, define-se κ =
d−1
2
onde κ representa a parte inteira de um n´umero real
d−1
2
.
Teorema 1.29. Seja C um c´odigo com distˆancia m´ınima d. Ent˜ao C pode corrigir
at´e κ erros e detectar at´e d − 1 erros.
Demonstra¸c˜ao: Se ao transmitirmos uma palavra c do c´odigo cometemos t erros
com t ≤ κ, recebendo a palavra r, ent˜ao d(c, r) = t ≤ κ; enquanto que a distˆancia
de r a qualquer outra palavra do c´odigo ´e maior do que κ. Isso determina c de modo
´unico a partir de r.
Por outro lado, dada uma palavra do c´odigo, podemos nela introduzir at´e
d − 1 erros sem encontrar outra palavra do c´odigo, e assim, a detec¸c˜ao do erro ser´a
poss´ıvel.
1.5 C´odigos Lineares
Consideremos o corpo finito K com q elementos como sendo o alfabeto. Portanto,
temos, para cada n´umero natural n, um K-espa¸co de dimens˜ao n, denotado por K
n
.
Defini¸c˜ao 1.30. Um c´odigo C ⊂ K
n
ser´a chamado de C´odigo Linear se for um
subespa¸co vetorial de K
n
. Os elementos de C s˜ao chamados de palavras-c´odigo.
Defini¸c˜ao 1.31. Dado u ∈ K
n
, define-se o peso de u como sendo o n´umero inteiro
ω(u) := d(u, o) = |{i : u
i
= 0, 1 ≤ i ≤ n}|,
onde o denota o vetor nulo. O peso de C ´e o inteiro
ω(C) := min{ω(u) : u ∈ C}.
Como d(u, v) = d(u−v, 0) = ω(u−v) e C ´e um espa¸co linear, a distˆancia m´ınima
de C ´e equivalente a
d(C) := min{w(x) : x ∈ C, x = o}.
13
A terna de inteiros [n, k, d] ´e chamada de parˆametros de c´odigo linear C, onde n
´e o comprimento das palavras de C, k ´e a dimens˜ao de C sobre K e d ´e a distˆancia
m´ınima de C. Note que o n´umero de elementos de C ´e igual a q
k
, onde q ´e o n´umero
de elementos de K.
Uma maneira de descrever subespa¸cos vetoriais de um espa¸co vetorial K
n
´e
como imagem de transforma¸c˜oes lineares. Para tal, precisamos da matriz da trans-
forma¸c˜ao, chamada matriz geradora do c´odigo.
Defini¸c˜ao 1.32. Uma matriz geradora de um c´odigo linear C com parˆametros
[n, k, d] ´e uma matriz G de ordem k × n cujas linhas formam uma base para C.
Defini¸c˜ao 1.33. Seja C ⊂ K
n
um c´odigo linear com parˆametros [n, k, d].
(i) O C´odigo Dual de C, C
⊥
, ´e o complemento ortogonal do subespa¸co C de K
n
,
C
⊥
= {v ∈ K
n
: v, u = 0, ∀u ∈ C}.
(ii) Uma matriz teste de paridade H para um c´odigo linear C ´e uma matriz
geradora para o c´odigo dual C
⊥
, cuja ordem ´e (n − k) × n.
Se tomarmos a matriz G acima descrita e nela realizarmos opera¸c˜oes do tipo
permuta¸c˜ao de duas linhas e/ou duas colunas, multiplica¸c˜ao de uma linha e/ou uma
coluna por um escalar n˜ao nulo e adi¸c˜ao de um m´ultiplo escalar de uma linha a
outra, de forma a obtermos uma matriz do tipo G
= (Id
k
| A), onde Id
k
´e a matriz
identidade k × k e A ´e uma matriz k × (n − k), temos uma matriz padr˜ao de G, ou
seja, G
= (Id
k
| A) ´e a matriz G na forma padr˜ao. Deste modo, a matriz teste de
paridade H ´e da forma H = (−A
t
| Id
n−k
).
Lema 1.34. Se C ⊂ K
n
´e um c´odigo linear, com matriz geradora G, ent˜ao
i) C
⊥
´e um subespa¸co vetorial de K
n
;
ii) x ∈ C
⊥
se, e somente se, Gx
t
= 0.
Demonstra¸c˜ao: i) Sejam dados u, v ∈ C
⊥
e λ ∈ K. Temos, para todo x ∈ C,
que
u + λv, x = u, x + λv, x = 0 + λ0 = 0.
14
Portanto, (u + λv) ∈ C
⊥
, provando que C
⊥
´e um subespa¸co vetorial de K
n
.
ii) x ∈ C
⊥
se, e somente se, x ´e ortogonal a todos os elementos de C, se, e somente
se, x ´e ortogonal a todos os elementos de uma base de C, o que ´e equivalente a dizer
que Gx
t
= 0, pois as linhas de G s˜ao uma base de C.
A proposi¸c˜ao abaixo nos d´a um m´etodo simples de determinar se uma palavra v
pertence ou n˜ao a um c´odigo C. Assim, H tem a finalidade de diminuir os c´alculos
relacionados a um c´odigo C. E o vetor Hv
t
´e chamado de s´ındrome de v.
Proposi¸c˜ao 1.35. Seja C um c´odigo linear e suponhamos que H seja uma matriz
geradora de C
⊥
. Temos, ent˜ao, que v ∈ C se, e somente se, Hv
t
= 0.
Demonstra¸c˜ao: Temos, pelo fato de que (C
⊥
)
⊥
= C e pelo Lema 1.34 item (ii),
que v ∈ C se, e somente se, v ∈ (C
⊥
)
⊥
se, e somente se, Hv
t
= 0.
Proposi¸c˜ao 1.36. Seja H a matriz teste de paridade de um c´odigo C. Temos que
o peso de C ´e maior ou igual a s se, e somente se, quaisquer s − 1 colunas de H
s˜ao linearmente independentes.
Demonstra¸c˜ao: Suponhamos, inicialmente, que cada conjunto de s − 1 colunas de
H ´e linearmente independente. Seja c = (c
1
, . . . , c
n
) uma palavra n˜ao nula de C, e
sejam h
1
, . . . , h
n
as colunas de H. Como Hc
t
= 0, temos que
0 = H · c
t
=
c
i
h
i
(1.4)
Visto que w(c) ´e o n´umero de componentes n˜ao nulas de c, segue que se w(c) ≤
s − 1, ter´ıamos por 1.4 uma combina¸c˜ao nula de um n´umero t, com 1 ≤ t ≤ s − 1,
de colunas de H, o que ´e contradit´orio. Logo, w(c) ≥ s e, portanto, w(C) ≥ s.
Reciprocamente, suponhamos que w(C) ≥ s. Suponhamos tamb´em, por ab-
surdo, que H tenha s − 1 colunas linearmente dependentes, digamos h
i
1
, . . . , h
i
s−1
.
Logo, existiriam c
i
1
, . . . , c
i
s−1
, no corpo, nem todos nulos, tais que
c
i
1
h
i
1
+ · · · + c
i
s−1
h
i
s−1
= 0.
15
Portanto, c = (0, . . . , c
i
1
, 0, . . . , c
i
s−1
, 0, . . . , 0) ∈ C e consequentemente, w(c) ≤
s − 1 < s, o que seria um absurdo.
Teorema 1.37. Seja H a matriz teste de paridade de um c´odigo C. Temos que o
peso de C ´e igual a s se, e somente se, quaisquer s−1 colunas de H s˜ao linearmente
independentes e existem s colunas de H linearmente dependentes.
Demonstra¸c˜ao: De fato, suponhamos que w(C) = s, logo, todo conjunto de s − 1
colunas de H ´e linearmente independente. Por outro lado, existem s colunas de H
linearmente dependentes, pois, caso contr´ario ter´ıamos w(C) ≥ s + 1.
Reciprocamente, suponhamos que todo conjunto de s − 1 vetores colunas de H ´e
linearmente independente e existem s colunas linearmente dependentes. Logo temos
que w(C) ≥ s. Mas w(C) n˜ao pode ser maior do que s, pois, neste caso, nos diria
que todo conjunto com s colunas de H ´e linearmente independente, o que ´e uma
contradi¸c˜ao.
16
Cap´ıtulo 2
C´odigos Geometricamente
Uniformes
Forney [4] generalizou os c´odigos de grupos de Slepian e c´odigos reticulados per-
mitindo que os elementos do grupo gerador sejam isometrias arbitr´arias do espa¸co
euclideano R
n
, ao inv´es de transforma¸c˜oes ortogonais ou transla¸c˜oes consideradas
de forma separadas. Tais c´odigos foram denominados c´odigos geometricamente uni-
formes apresentando propriedades sim´etricas altamente desej´aveis tais como: todas
as regi˜oes de Voronoi s˜ao congruentes, o perfil de distˆancias ´e o mesmo para toda
palavra-c´odigo, as palavras-c´odigo possuem a mesma probabilidade de erro e o grupo
gerador ´e isomorfo a um grupo de permuta¸c˜oes transitivas sobre as palavras-c´odigo.
2.1 Isometrias
Nesta se¸c˜ao definiremos isometrias daremos alguns exemplos de isometrias e grupos
isom´etricos, em seguida definiremos uniformidade geom´etrica.
Defini¸c˜ao 2.1. Seja M um espa¸co m´etrico com m´etrica d e T uma transforma¸c˜ao em
M, dizemos que T ´e uma isometria se T preserva a distˆancia d, ou seja,
17
∀ x, y ∈ M temos que
d(x, y) = d(T (x), T (y)).
Neste cap´ıtulo vamos considerar o R
n
, um n-espa¸co m´etrico com a m´etrica Eu-
clideana dada por:
d
2
(x, y) = ||x − y||
2
.
No R
n
importantes classes de isometrias s˜ao:
• Transla¸c˜oes: t
a
(x) = x + a para algum a ∈ R
n
.
• Transforma¸c˜oes ortogonais: r
A
(x) = Ax onde A ´e uma matriz n×n ortogonal,
ou seja, A
T
A = I onde I ´e a matriz identidade e A
T
´e a matriz transposta de
A.
Defini¸c˜ao 2.2. Uma figura geom´etrica S ´e um conjunto de pontos no R
n
. Duas
figuras S
1
e S
2
s˜ao geometricamente congruentes se existe uma isometria u de R
n
tal que u(S
1
) = S
2
.
Defini¸c˜ao 2.3. Duas figuras S
1
e S
2
s˜ao geometricamente equivalentes se existem
uma isometria u e um escalar α > 0 tal que u(αS
1
) = S
2
.
Defini¸c˜ao 2.4. Uma isometria u de R
n
S invariante (ou seja, U(S) = S) ´e denom-
inada uma simetria de S.
´
E f´acil verificar que as simetrias de um conjunto S formam um grupo com a
opera¸c˜ao composi¸c˜ao, este grupo denotaremos por Γ(S).
Defini¸c˜ao 2.5. O conjunto de todas as transla¸c˜oes sim´etricas de S formam um
subgrupo de Γ(S) denotado por T (S).O conjunto formado por todos os vetores das
transla¸c˜oes sim´etricas dado por
Λ(S) = {a; t
a
∈ T (S)}
´e um espa¸co vetorial de dimens˜ao n
≤ n chamado de reticulado de S.
18
2.2 Conjuntos de Sinais Geometricamente Uni-
formes
Para comunica¸c˜ao digital as figuras interessantes s˜ao os conjuntos de pontos discretos
S, ou seja, se s ∈ S ent˜ao existe uma vizinhan¸ca V (s) de s tal que V (s)
S = {s}.
Defini¸c˜ao 2.6. Um conjunto de sinais S ´e geometricamente uniforme se dado quais-
quer dois pontos s, s
∈ S existe uma isometria u tal que
• u(s) = s
• u(S) = S
Um conjunto finito de sinais S geometricamente uniforme ´e chamado constela¸c˜ao
uniforme e um conjunto infinito de sinais S ´e chamado de arranjo regular.
Exemplo 2.7. Consideremos o conjunto S = {(−1, −1), (−1, 1), (1, −1), (1, 1)} ⊂
R
2
, existem oito simetrias deste quadrado, estas simetrias s˜ao os elementos do grupo
diedral D
4
, o qual pode ser representado pelo seguinte grupo de matrizes ortogonais:
1 0
0 1
0 −1
1 0
−1 0
0 −1
0 1
−1 0
1 0
1 −1
0 1
1 0
−1 0
0 1
0 −1
−1 0
Podemos notar que um conjunto S ´e geometricamente uniforme se a a¸c˜ao do
grupo sim´etrico Γ(S) em S for transitiva, ou se a ´orbita de qualquer ponto s ∈ S
sobre Γ(S) ´e S.
Defini¸c˜ao 2.8. Um grupo gerador U(S) de S ´e o menor subgrupo de Γ(S) suficiente
para gerar S.
No Exemplo 2.7 podemos notar que o subgrupo formado pelas 4 primeiras ma-
trizes ´e suficiente para gerar o conjunto S dado, tal subgrupo ´e o grupo das rota¸c˜oes
puras R
4
, rota¸c˜oes por inteiros m´ultiplos de 90
o
.
19
2.3 Conjuntos de Sinais Geometricamente Uni-
formes e a Comunica¸c˜ao Digital
Os conjuntos de sinais mais utilizados em comunica¸c˜oes digitais s˜ao os conjuntos de
sinais geometricamente uniformes. A seguir alguns exemplos de tais conjuntos s˜ao
dados.
Exemplo 2.9. Seja S = {ω
j
s
0
, 0 ≤ j ≤ M} onde ω ´e uma raiz M-´esima primitiva da
unidade e s
0
´e um n´umero complexo diferente de zero, este conjunto ´e um conjunto de
sinais geometricamente uniforme o qual ´e denominado constela¸c˜ao de sinais M-PSK.
Um grupo gerador natural para S ´e o conjunto de rota¸c˜oes m´ultiplas de 360
o
/M.
Este grupo ´e isomorfo a Z
M
, o grupo dos inteiros aditivos m´odulo M.
O grupo sim´etrico de S ´e Γ(S) = V ·R
M
, onde V ´e um grupo com dois elementos
a identidade e uma reflex˜ao pelo ponto m´edio, este grupo ´e isomorfo ao grupo M-´ario
diedral D
M
.
Exemplo 2.10. Seja S = {−d, d}, onde d ∈ R. S ´e um conjunto de sinais ge-
ometricamente uniforme unidimensional onde o grupo sim´etrico de Γ(S) = V ´e
isomorfo ao Z
2
. O produto cartesiano de conjuntos geometricamente uniforme
´e um conjunto geometricamente uniforme, basta considerarmos a composi¸c˜ao de
isometrias para cada entrada separadamente, desta forma temos que o conjunto
S = {(−d, d, −d, d, ..., −d, d)} ´e uma constela¸c˜ao de sinais. Um grupo gerador natu-
ral para esta constela¸c˜ao ´e o grupo V
n
com 2
n
elementos, as n-uplas agindo em cada
coordenada individualmente. Segue que V
n
pode ser representado pelo conjunto
de matrizes ortogonais A = diag(−1, 1, −1, 1, ..., −1, 1). O grupo V
n
´e isomorfo ao
(Z
2
)
n
.
Exemplo 2.11. O conjunto de sinais do tipo reticulado, dado por S = Z
2
+
(1/2, 1/2), possui T (Z
2
) como seu grupo gerador, o conjunto de todas as transla¸c˜oes
por inteiros em cada coordenada.
20
2.4 Propriedades Sim´etricas de Conjuntos de
Sinais Geometricamente Uniformes
Um conjunto de sinais geometricamente uniforme S tem a importante propriedade
de que cada um de seus pontos tem a mesma perspectiva com rela¸c˜ao aos outros
pontos.
Defini¸c˜ao 2.12. Seja s ∈ S, o conjunto de todos os pontos de R
n
que est˜ao mais
perto de s do que qualquer outro ponto s
∈ S ´e chamado a Regi˜ao de Voronoi
associada a s. Tal conjunto ser´a denotado da seguinte forma,
R
V
(s) = {x ∈ R
n
: ||x − s||
2
= min
s
∈S
||x − s
||
2
}.
Defini¸c˜ao 2.13. Seja s ∈ S. O conjunto dado por,
DP (s) = {||s − s
||
2
; s
∈ S}
´e chamado de distˆancia perfil global.
Teorema 2.14. Se S ´e um conjunto de sinais geometricamente uniforme, ent˜ao:
a. Toda Regi˜ao de Voronoi R
V
(s) tem a mesma forma e R
V
(s
) = u
ss
[R
V
(s)],onde
u
ss
´e uma isometria que leva s em s
;
b. A distˆancia perfil global DP (s) ´e a mesma para todo s ∈ S.
Demonstra¸c˜ao: Pela defini¸c˜ao de Regi˜ao de Voronoi, x ∈ R
n
est´a em R
V
(s) se, e
somente se,
||x − s||
2
= min
s
∈S
||x − s
||
2
.
Seja s
= s outro ponto em S, ent˜ao pela defini¸c˜ao de uniformidade geom´etrica existe
uma simetria u
ss
tal que u
ss
(s) = s
. Desta forma temos que u
ss
(x) ∈ R
V
(s
) pois
21
||u
ss
(x) − s
|| = ||u
ss
(x) − u
ss
(s)|| (2.1)
= ||x − s||
= min
s
∈S
||x − s
||
= min
u
ss
(s
)∈S
||u
ss
(x) − u
ss
(s
)||
= min
y∈S
||u
ss
(x) − y||
onde podemos observar que s
varia em S, assim y = u
ss
(s
) tamb´em varia em S.
De modo an´alogo,
DP (s) = {||s − s
||
2
, s
∈ S} (2.2)
= {||u
ss
(s) − u
ss
(s
)||
2
; s
∈ S}
= {||s
− u
ss
(s
)||
2
; u
ss
(s
) ∈ S}
= {||s
− y||; y ∈ S}
= DP (s
).
Desta forma temos que a distˆancia perfil global ´e a mesma para todos os pontos.
O fato de toda regi˜ao de Voronoi de um conjunto de sinais S geometricamente
uniforme ter a mesma forma ´e uma propriedade sim´etrica muito forte porque a
forma da regi˜ao de Voronoi determina quase todas as propriedades de S que s˜ao im-
portantes no estabelecimento do sistema de comunica¸c˜ao digital. A rec´ıproca deste
teorema n˜ao ´e verdadeira. Em [2], ´e mostrado que conjunto de sinais, cujas regi˜oes
de Voronoi tenham a mesma forma n˜ao implica que o mesmo seja geometricamente
uniforme. Em [13] ´e mostrado que se um conjunto de sinais apresenta o mesmo perfil
de distˆancias, independente do ponto considerado, isto n˜ao implica que o mesmo seja
geometricamente uniforme. Podemos tomar alguma regi˜ao de Voronoi R
V
(s) como
uma t´ıpica Regi˜ao de Voronoi de um conjunto de sinais S, e cham´a-la A regi˜ao de
Voronoi de S denotada por R
V
(S).
22
Da regi˜ao de Voronoi de S podemos determinar as seguintes propriedades:
a. O volume de R
V
(S) denominado volume fundamental de S denotado por V (S)
´e finito se, e somente se o reticulado de S tem posto N inteiro.
b. A distˆancia perfil local DP
V
(S) = {||s − s
||
2
; s
∈ S
V
} onde S
V
´e um conjunto
finito de face definida de pontos s
pr´oximos a s.
c. De forma particular a distˆancia DP
V
(S) permite determinar a distˆancia m´ınima
ao quadrado d
2
min
(S) entre os pontos de S, ou o ”raio de empacotamento”.
d. A probabilidade de erro
P
r
(E) = 1 −
R
V
(s)
(2πσ
2
)
−N/2
e
(||z−s||
2
/2σ
2
)
dz,
onde s ´e o ponto transmitido sob um canal Gaussiano com variˆancia σ
2
depende
somente do quadrado da distˆancia ||z − s||
2
.
O Teorema 2.14 garante que se S ´e geometricamente uniforme ent˜ao todas estas
propriedades s˜ao as mesmas para todo ponto em S.
2.5 Parti¸c˜oes Geometricamente Uniformes
Seja S um conjunto de sinais geometricamente uniforme, U
um subgrupo normal
ao grupo gerador de S, U(S), e seja U(S)/U
o grupo quociente correspondente as
classes laterais de U
em U(S). Se S ´e a ´orbita de um ponto s
0
sob U(S), ent˜ao as
´orbitas de s
0
sob as classes laterais de U
s˜ao disjuntas e a uni˜ao delas ´e todo S.
Defini¸c˜ao 2.15. Uma parti¸c˜ao geometricamente uniforme denotada por S/S
´e
uma parti¸c˜ao do conjunto geometricamente uniforme S com grupo gerador U(S)
induzida por um subgrupo normal U
de U(S). Os elementos da parti¸c˜ao S/S
s˜ao
os subconjuntos de S que correspondem a classes laterais de U
em U(S).
23
Teorema 2.16. Seja S/S
uma parti¸c˜ao geometricamente uniforme. Ent˜ao os sub-
conjuntos de S nesta parti¸c˜ao s˜ao geometricamente uniformes mutuamente congru-
entes e tˆem U
como um grupo gerador comum.
Demonstra¸c˜ao: Se U
´e um subgrupo normal de U(S) ent˜ao as classes laterais `a
esquerda e `a direita de U
s˜ao idˆenticas. Desta forma consideremos a classe lateral `a
esquerda de U
, u
a
U
, de todas as composi¸c˜oes de alguma u
a
∈ U(S) fixa com todas
u ∈ U
. Da´ı temos que o subconjunto correspondente S
(a) ´e:
S
(a) =
u∈U
u
a
u(s
0
)
= u
a
u∈U
u(s
0
)
= u
a
(S
). (2.3)
Portanto, todo subconjunto S
(a) ´e congruente a S
.
Consideremos agora uma classe lateral `a direita de U
dada por U
u
a
, segue que
o subconjunto S
(a) correspondente ´e dado por,
S
(a) =
u∈U
u[u
a
(s
0
)].
Assim todo subgrupo S
(a) ´e a ´orbita de um ponto u
a
(s
0
) sob U
, logo S
(a) ´e
geometricamente uniforme e tem U
como grupo gerador.
Exemplo 2.17. Seja M uma potˆencia de 2 e M
um divisor de M. Um conjunto de
sinais M − P SK pode ser particionado em k conjuntos de sinais M
− P SK, onde
k = |R
M
/R
M
| = M/M
. O quociente R
M
/R
M
´e isomorfo a Z
M/M
.
Exemplo 2.18. A constela¸c˜ao hipercubo n-dimensional tem como grupo gerador
V
n
que ´e isomorfo a (Z
2
)
n
. Um c´odigo bin´ario linear (n, k) ´e um subgrupo de (Z
2
)
n
de ordem 2
k
. Pelo Teorema 2.16 este subgrupo induz uma parti¸c˜ao geometricamente
uniforme do hipercubo em 2
n−k
parti¸c˜oes geometricamente uniformes e mutuamente
congruentes.
24
2.6 Rotulamentos Isom´etricos
Defini¸c˜ao 2.19. Seja S um conjunto de sinais geometricamente uniforme com grupo
gerador U(S), U
um subgrupo normal a U(S) e consideremos A um grupo isomorfo
a U(S)/U
. Chamaremos A de grupo de r´otulos das classes de U
em U(S).
A parti¸c˜ao S/S
´e induzida por uma aplica¸c˜ao injetora entre os subconjuntos
de S e os elementos de U(S)/U
, assim como o isomorfismo entre os grupos A e
U(S)/U
.
Defini¸c˜ao 2.20. A aplica¸c˜ao m : A → S/S
que leva um r´otulo a ∈ A no subcon-
junto m(a) ∈ S induzido pela parti¸c˜ao S/S
´e denominada aplica¸c˜ao r´otulo.
Notamos que o elemento identidade de A ´e levado por m em S
e |S/S
| =
|U(S)/U
| = |A|.
Defini¸c˜ao 2.21. Seja A um grupo de r´otulos de uma parti¸c˜ao geometricamente
uniforme S/S
. Chamaremos o isomorfismo A U(S)/U
de isomorfismo rotulado.
A aplica¸c˜ao r´otulo m : A → S/S
definida pela composi¸c˜ao do isomorfismo rotulado
com a aplica¸c˜ao injetora que leva U(S)/S
em S/S
ser´a denominada rotulamento
isom´etrico.
O teorema a seguir mostra uma condi¸c˜ao necessaria e suficiente para se obter
um rotulamento isom´etrico.
Teorema 2.22. Uma aplica¸c˜ao r´otulo m : A → S/S
´e um rotulamento isom´etrico
se, e somente se, para todo a ∈ A existe uma isometria u
a
: S/S
→ S/S
tal que
para todo b ∈ A, m(ab) = u
a
(m(b)).
Demonstra¸c˜ao: Se m : A → S/S
´e um rotulamento isom´etrico, do isomorfismo
A U(S)/U
temos ab → u
ab
U
e ab → u
a
U
u
b
U
= u
ab
U
de onde obtemos,
u
ab
U
= u
a
u
b
U
= {(u
a
u
b
)u(s
0
); u ∈ U
}
= {u
a
[u
b
u(s
0
)]; u ∈ U
} = u
a
(m(b)).
(2.4)
25
Reciprocamente, se m(ab) = u
a
(m(b)) ∀a, b ∈ A ent˜ao u
ab
(S
) = u
a
u
b
(S
), isto
implica que m(ab) = m(a)m(b), portanto m ´e um homomorfismo, desta forma o
rotulamento ´e isom´etrico.
2.7 Propriedades Elementares dos Rotulamentos
Isom´etricos
Dado um rotulamento isom´etrico m : A → S/S
existem v´arias transforma¸c˜oes de
rotulamentos simples que resultam em rotulamentos isom´etricos. A seguir apre-
sentaremos alguns resultados elementares dos rotulamentos isom´etricos.
Proposi¸c˜ao 2.23. Se m : A → S/S
´e um rotulamento isom´etrico e T : A → A ´e
um automorfismo, ent˜ao o rotulamento mT : A → S/S
definido por a → m[T (a)]
´e tamb´em um rotulamento isom´etrico.
Demonstra¸c˜ao: Como T ´e um automorfismo de A temos que T leva todos elemen-
tos de A em elementos de A, logo como m ´e um rotulamento isom´etrico temos que
mT tamb´em ´e um rotulamento isom´etrico.
Proposi¸c˜ao 2.24. Se m : A → S/S
´e um rotulamento isom´etrico ent˜ao o rotula-
mento mt
b
: A → S/S
definido por a → m(ab) para algum b ∈ A ´e tamb´em um
rotulamento isom´etrico.
Demonstra¸c˜ao: Como m ´e um rotulamento isom´etrico temos pelo Teorema 2.22
que existe uma isometria u
a
: S/S
→ S/S
tal que m(ab) = u
a
(m(b)), ∀a, b ∈ A.
Logo temos que mt
b
´e um rotulamento isom´etrico.
As duas proposi¸c˜oes acima implicam que se a parti¸c˜ao S/S
admite um rotula-
mento isom´etrico com grupo de r´otulos A, ent˜ao alguma transforma¸c˜ao afim definida
26
por a → T (a) + b onde a, b ∈ A, tamb´em produz um rotulamento isom´etrico.
´
E in-
teressante notar que em um espa¸co onde a m´etrica natural ´e a m´etrica de Hamming
uma transforma¸c˜ao ´e uma isometria.
Proposi¸c˜ao 2.25. Se m : A → S/S
´e um rotulamento isom´etrico, e u ´e uma
simetria em U(S), ent˜ao o rotulamento u · m : A → S/S
definido por a → u[m(a)]
´e um rotulamento isom´etrico.
Demonstra¸c˜ao: A demonstra¸c˜ao desta proposi¸c˜ao decorre diretamente do Teorema
2.22.
2.8 Rotulamentos Bin´arios Isom´etricos
Nesta se¸c˜ao estamos interessados em parti¸c˜oes S/S
que admitem rotulamentos
isom´etricos por alfabetos n − bit bin´arios, ou seja, alfabetos da forma A = (Z
2
)
n
. A
seguir definiremos um Rotulamento Bin´ario de Ungerboeck.
Defini¸c˜ao 2.26. Consideremos uma parti¸c˜ao S/S
geometricamente uniforme 2
n
-
caminhos. Se existe um refinamento desta parti¸c˜ao em n parti¸c˜oes 2-caminhos, S =
S
0
/S
1
/.../S
n
= S
tal que os r´otulos dos 2
n
subconjuntos s˜ao escolhidos em (Z
2
)
n
de
modo que os r´otulos de todos os subconjuntos do j-´esimo n´ıvel que pertencem a um
mesmo subconjunto tenham as ´ultimas coordenadas iguais, ent˜ao este rotulamento
´e chamado de Ungerboeck.
A distˆancia m´ınima quadrada entre dois pontos com r´otulos a e a
´e maior ou
igual a d
2
min
(S
j
) onde j ´e o n´umero de zeros na soma mod2 de a ⊕ a
. Esta distˆancia
recebe o nome de distˆancia limite de Ungerboeck.
Teorema 2.27. Se S/S
´e uma parti¸c˜ao geometricamente uniforme que admite
um rotulamento bin´ario isom´etrico, e S = S
0
/S
1
/.../S
n
= S
´e uma cadeia de
parti¸c˜oes 2-caminhos geometricamente uniformes, ent˜ao S/S
admite um rotula-
mento isom´etrico de Ungerboeck consistente com esta cadeia.
27
Demonstra¸c˜ao: Se S/S
admite um rotulamento bin´ario isom´etrico ent˜ao existem
grupos geradores U(S) e U(S
) tais que U(S)/U(S
) (Z
2
)
n
= A, e se
S = S
0
/S
1
/.../S
n
= S
´e uma cadeia de parti¸c˜oes geometricamente uniformes, ent˜ao existe uma cadeia
correspondente de grupos geradores
U(S) = U(S
0
)/U(S
1
)/.../U(S
n
) = U(S
).
Seja A
j
a posi¸c˜ao do conjunto de r´otulos inclu´ıdo no subconjunto S
j
de S. A cadeia
correspondente
A = A
0
/A
1
/.../A
n
= {0}
´e uma cadeia de espa¸cos vetoriais bin´arios, onde a dimens˜ao de A
j
´e igual a n − j.
Consideremos a respectiva classe n˜ao nula na parti¸c˜ao A
j
/A
j+1
, 0 ≤ j ≤ n − 1
tomada como algum r´otulo (x)
n−j−1
(10)
j
onde x, (10) ∈ (Z
2
)
2
. Ent˜ao temos que
A
j
/A
n
= A
j
o espa¸co vetorial bin´ario (n − j) dimensional consistindo de todos os
r´otulos x
n−j
(10)
j
e os subconjuntos no j-´esimo n´ıvel consistem da uni˜ao de todos
n-´esimos subconjuntos que tˆem um j − bit em comum em seu r´otulo. Temos assim
um rotulamento de Ungerboeck.
Os bits conduzidos no rotulamento de Ungerboeck s˜ao chamados bits mais sig-
nificantes e os bits restantes s˜ao chamados bits menos significantes.
Corol´ario 2.28. Uma parti¸c˜ao tipo reticulado S = Λ + τ em classes laterais de um
subreticulado Λ
admite um rotulamento de Ungerboeck se Z
n
/Λ/Λ
/4Z
n
forma uma
cadeia de parti¸c˜oes reticulada.
Demonstra¸c˜ao: Existe um rotulamento isom´etrico de Ungerboeck 2n − bits de
Z
n
/4Z
n
, se |Z
n
/Λ| = 2
j
e |Λ
/4Z
n
| = 2
2n−j
, ent˜ao um rotulamento de Ungerboeck
de Λ/Λ
pode ser obtido se desconsiderarmos os (2n − j
) − bits mais significantes e
os j − bits menos significantes do rotulamento de Z
n
/4Z
n
.
28
Os reticulados de Z
n
que tˆem como um subreticulado o 4Z
n
s˜ao chamados de
reticulados bin´arios mod4 e as parti¸c˜oes Λ/Λ
tal que Z
n
/Λ/Λ
/4Z
n
´e uma cadeia
de parti¸c˜oes reticulada, s˜ao chamadas de parti¸c˜oes de profundidade µ ≤ 4. Assim
todas as parti¸c˜oes de profundidade µ ≤ 4 admitem rotulamentos isom´etricos de
Ungerboeck.
2.9 C´odigos Geometricamente Uniformes em Es-
pa¸cos de Sinais
Dado uma parti¸c˜ao geometricamente uniforme S/S
e um rotulamento isom´etrico
com um grupo de r´otulos A, a especifica¸c˜ao de um c´odigo em espa¸co de sinais C ´e
completa se for especificado um c´odigo r´otulo C cujos elementos s˜ao seq¨uˆencias de
r´otulos que selecionam uma seq¨uˆencia de subconjuntos de S atrav´es do rotulamento
isom´etrico. Devemos notar que C ´e um grupo c´odigo sobre o grupo r´otulo A.
2.9.1 Espa¸cos de Seq¨uˆencias
Seja S/S
uma parti¸c˜ao geometricamente uniforme e A um grupo de r´otulos associ-
ado a esta parti¸c˜ao, temos que um espa¸co de A
I
´e o conjunto de todas as seq¨uˆencias
a = {a
k
; k ∈ I} onde os elementos a
k
pertencem ao grupo de r´otulos A e o conjunto
de ´ındices I ´e um subconjunto dos inteiros I ⊂ Z. Se I ´e finito, ou seja, I = {k; 1 ≤
k ≤ n} ent˜ao A
I
´e o produto n cartesiano de A. Se I ´e infinito temos que A
I
´e o
produto cartesiano infinito de A . Se A ´e um grupo com a opera¸c˜ao bin´aria ∗ ent˜ao
o espa¸co de seq¨uˆencias A
I
tamb´em ´e um grupo sob ∗ usando a estens˜ao usual, isto ´e,
∀a, b ∈ A
I
, a ∗ b = {a
k
∗ b
k
; k ∈ I}. A seguir definiremos um c´odigo sobre o alfabeto
A.
Defini¸c˜ao 2.29. Um c´odigo C sobre o grupo de r´otulos A ´e um conjunto de
seq¨uˆencias de elementos de A. Tal c´odigo ´e um subconjunto do espa¸co de seq¨uˆencias
A
I
.
29
2.9.2 C´odigos em Espa¸cos de Sinais
Um c´odigo r´otulo C sobre um grupo de r´otulos A define um c´odigo em um espa¸co
de sinais como segue:
Defini¸c˜ao 2.30. Sejam S/S
uma parti¸c˜ao geometricamente uniforme, C um c´odigo
r´otulo sobre o alfabeto A, I o conjunto de ´ındices e m : A → S/S
uma aplica¸c˜ao
r´otulo. Um c´odigo em um espa¸co de sinais ´e a uni˜ao disjunta
C(S/S
; C) =
c∈C
m(c)
das seq¨uˆencias de subconjuntos m(c) = {m(c
k
); k ∈ I}.
Uma seq¨uˆencia de sinais s ´e uma seq¨uˆencia de c´odigos em C(S/S
; C) se s ∈ m(c)
para algum c ∈ C, isto ´e, se s = {s
k
∈ m(c
k
); k ∈ I}. Desta forma temos que um
c´odigo em espa¸co de sinais C(S/S
; C) ´e um subconjunto do espa¸co de seq¨uˆencias
S
I
, o conjunto de todas as seq¨uˆencias de elementos do conjunto de sinais S.
Exemplo 2.31. Se S ´e um subconjunto de R
n
, ent˜ao S
I
e C(S/S
; C) s˜ao subcon-
juntos do espa¸co de seq¨uˆencias (R
n
)
I
, o conjunto de todas as seq¨uˆencias reais de
n− uplas. O produto cartesiano (R
n
)
I
´e ainda um espa¸co Euclideano com a m´etrica
usual do espa¸co Euclideano.
Uma codifica¸c˜ao para um c´odigo r´otulo C gera uma seq¨uˆencia de c´odigos r´otulos
c = {c
k
} que permanecem em C. A seq¨uˆencia particular c ´e determinada por uma
seq¨uˆencia apropriada de entrada de dados.
A seq¨uˆencia r´otulo c ´e ent˜ao aplicada a uma seq¨uˆencia de subconjuntos
m(c) = {m(c
k
); k ∈ I} atrav´es da aplica¸c˜ao r´otulo m. Uma segunda opera¸c˜ao
ent˜ao seleciona uma espec´ıfica seq¨uˆencia de sinal s ∈ m(c) para transmiss˜ao sobre
o canal, de acordo com uma segunda seq¨uˆencia de entrada de dados. A segunda
opera¸c˜ao ´e de importˆancia secund´aria uma vez que as propriedades do c´odigo ge-
rador para tal codifica¸c˜ao s˜ao determinadas primeiramente pelas propriedades do
c´odigo em espa¸co de sinais C(S/S
; C) que s˜ao determinadas no primeiro n´ıvel.
30
2.9.3 Classes Laterais de C´odigos Generalizadas
Sejam S/S
uma parti¸c˜ao geometricamente uniforme gerada pelo grupo gerador da
parti¸c˜ao U(S)/U(S
), A um grupo r´otulo isomorfo a U(S)/U(S
) abeliano,
m : A → S/S
um rotulamento isom´etrico e C um grupo c´odigo sobre o espa¸co
de seq¨uˆencias A
I
. Como A ´e um grupo abeliano temos que A
I
´e tamb´em um grupo
abeliano e qualquer subgrupo C de A
I
´e um subgrupo normal. A seguir definiremos
uma classe lateral de c´odigo generalizada .
Defini¸c˜ao 2.32. Uma classe lateral de c´odigo generalizada C(S/S
; C) ´e o conjunto
de todas as seq¨uˆencias de sinais s ∈ m(c); c ∈ C.
Podemos notar que o rotulamento m : A → S/S
pode ser estendido para
m : A
I
→ (S/S
)
I
sem perder as suas propriedades e que a parti¸c˜ao (S/S
)
I
= S
I
/S
I
´e tamb´em uma parti¸c˜ao geometricamente uniforme. Se o grupo gerador de S ´e U(S)
temos que o grupo gerador do conjunto de sinais S
I
´e o grupo [U(S)]
I
pois cada ele-
mento s = {s
k
} ∈ S
I
pode ser levado em algum outro elemento de S
I
por composi¸c˜ao
de isometrias em U(S) agindo em cada componente s
k
de s individualmente. Al´em
disso, se U(S
) ´e um subgrupo normal de U(S) ent˜ao [U(S
)]
I
´e um subgrupo normal
de [U(S)]
I
logo o grupo quociente [U(S
)]
I
/[U(S)]
I
induz a parti¸c˜ao geometricamen-
te uniforme S
I
/S
I
de S
I
. O espa¸co r´otulo A
I
´e isomorfo a [U(S
)]
I
/[U(S)]
I
, desta
forma temos que a aplica¸c˜ao r´otulo estendida m : A
I
→ (S/S
)
I
´e um rotulamento
isom´etrico.
Se C ´e um subgrupo de A
I
ent˜ao C(S/S
; C) ´e um subgrupo de S
I
, e o quociente
S
I
/C ´e isomorfo a A
I
/C, sobre a estrutura de grupo induzida a S
I
por [U (S)]
I
.
Al´em disso, S
I
´e um subgrupo de C e a cadeia S
I
/C/S
I
´e isomorfa a A
I
/C/{0}
I
.
A seguir definiremos um r´otulo transladado a partir de uma classe lateral de C.
Defini¸c˜ao 2.33. As classes laterais de C podem ser escritas como C ⊕ a, onde
a ∈ A
I
. Para cada classe lateral o rotulamento m : A
I
→ (S/S
)
I
define subconjun-
31
tos de S
I
chamados de r´otulos transladados de C dados por
C(S/S
; C ⊕ a) =
c∈C
m(c ⊕ a).
Os r´otulos transladados de C s˜ao as classes laterais de C em S
I
sobre a estrutura
de grupo induzida.
Teorema 2.34. Se C(S/S
; C) ´e uma classe lateral generalizada de c´odigos, ent˜ao
S
I
/C/S
I
´e uma cadeia de parti¸c˜oes geometricamente uniformes, e os r´otulos trans-
ladados C(S/S
; C ⊕ a) de C s˜ao geometricamente uniformes, mutuamente congru-
entes e tem U(C) como grupo gerador em comum.
Demonstra¸c˜ao: Seja S
I
/C/S
I
estabelecida como uma cadeia de parti¸c˜oes geome-
tricamente uniforme com a estrutura de grupo induzida sobre S
I
por [U(S)]
I
como
observamos acima. Desta forma temos que o Teorema 2.34 ´e um simples corol´ario
do Teorema 2.16.
O teorema acima nos garante que qualquer classe lateral generalizada de c´odigo
C ´e geometricamente uniforme. Al´em disso, ele afirma que o conjunto S
I
de todas
as seq¨uˆencias de sinais em S tem uma parti¸c˜ao no r´otulo transladado de C que ´e
congruente a C. Segue ent˜ao de forma direta o seguinte corol´ario.
Corol´ario 2.35. Se C ´e uma classe lateral de c´odigo generalizada , ent˜ao:
a. A regi˜ao de Voronoi associada a quaisquer duas seq¨uˆencias de c´odigos s, s
∈ C
s˜ao congruentes.
b. A distˆancia perfil DP (s) = {||s − s
||
2
; s
∈ C} de uma seq¨uˆencia s ∈ C para toda
seq¨uˆencia s
∈ C independe da seq¨uˆencia s.
Muitos c´odigos em espa¸cos Euclideanos s˜ao baseados nos c´odigos bin´arios lineares
C sobre o corpo bin´ario F = Z
2
.
Exemplo 2.36. O produto n-cartesiano do rotulamento bin´ario usual m : {0, 1} →
{−1, +1} do conjunto de sinais bin´ario ´e um rotulamento bin´ario isom´etrico do
hipercubo N-dimensional usando o alfabeto r´otulo F
n
.
32
Qualquer subgrupo aditivo de F
n
´e tamb´em um espa¸co vetorial de alguma di-
mens˜ao k sobre F , isto ´e, um (n, k) bloco bin´ario linear do c´odigo C. Conseq¨uente-
mente os c´odigos de espa¸cos bin´arios C correspondentes a qualquer bloco bin´ario de
c´odigo C s˜ao geometricamente uniformes. As classes de C aplicadas em conjuntos
de sinais geometricamente uniformes s˜ao todas congruentes a C, e C e suas classes
laterais formam assim uma parti¸c˜ao do hipercubo.
2.10 Outras No¸c˜oes de Uniformidade
Nesta se¸c˜ao compararemos as no¸c˜oes de uniformidade usadas at´e agora com outros
tipos de simetrias que ser˜ao previamente introduzidos.
2.10.1 Linearidade
Para parti¸c˜oes Λ/Λ
de um reticulado Λ em classes laterais de um subreticulado Λ
de Λ, ´e poss´ıvel ter um rotulamento que ´e linear no seguinte sentido.
Defini¸c˜ao 2.37. Um rotulamento m : A → Λ/Λ
definido por m(a) = Λ
+ t(a),
onde t(a) ∈ R
n
, de uma parti¸c˜ao reticulada ´e linear se:
m(a ⊕ b) = Λ
+ t(a ⊕ b)
= Λ
+ t(a) + t(b)
= m(b) + t(a)
onde + ´e a adi¸c˜ao em R
n
.
Pelo Teorema 2.22 um rotulamento linear ´e um rotulamento isom´etrico com a
isometria u
a
dada pela transla¸c˜ao t(a). Isto implica que t(0) deve ser um elemento
de Λ
pois m(0) = Λ
+ t(0) = Λ
.
Se C(Λ/Λ
; C) ´e um c´odigo em espa¸co de sinais baseado numa parti¸c˜ao reticulada
Λ/Λ
e em um rotulamento linear, ent˜ao C ´e linear no sentido de que C ´e um
grupo aditivo sob uma seq¨uˆencia aditiva no espa¸co de seq¨uˆencias (R
n
)
I
. Sejam s
33
e s
quaisquer duas seq¨uˆencias de c´odigos em C, pertencentes `as classes laterais de
seq¨uˆencias (Λ
)
I
+ t(c) e (Λ
)
I
+ t(c
), respectivamente. Ent˜ao a seq¨uˆencia s + s
pertence a classe lateral (Λ
)
I
+ t(c) + t(c
) = (Λ
)
I
+ t(c ⊕ c
) e est´a em C, assim
como c ⊕ c
est´a no c´odigo C.
Uma classe lateral de um c´odigo tipo reticulado ´e um c´odigo em espa¸co de sinais
C[(Λ + τ)/Λ
; C] baseada na parti¸c˜ao do translado Λ + τ de Λ em classes laterais de
Λ
. Temos que
C[(Λ + τ)/Λ
; C] = C(Λ/Λ
; C) + τ
I
assim tal c´odigo ´e meramente um translado de um c´odigo C(Λ/Λ
; C) baseado na
parti¸c˜ao do pr´oprio Λ. Ele n˜ao ´e rigorosamente linear, mas pode ser considerado efe-
tivamente linear. Alternativamente ele pode ser considerado como uma classe lateral
generalizada de c´odigos com um rotulamento isom´etrico onde todas as isometrias
s˜ao transla¸c˜oes.
Lema 2.38. Um grupo G ´e isomorfo a (Z
2
)
n
para algum inteiro positivo n se, e
somente se, G ´e um grupo finito tal que todo elemento g ∈ G satisfaz g
2
= e onde e
´e o elemento neutro de G.
Demonstra¸c˜ao: Se G (Z
2
)
n
, ent˜ao G ´e finito e abeliano e qualquer g satisfaz
g
2
= e. Reciprocamente, se todo elemento de G ´e seu pr´oprio inverso, ent˜ao para
quaisquer a, b ∈ G temos que (ab)
2
= e que implica que ab = b
−1
a
−1
= ba, assim G ´e
abeliano. Denotaremos a identidade de G por 0 e a opera¸c˜ao de G por +. Como G
´e abeliano e todo elemento de G ´e seu pr´oprio inverso temos que g + g = 0, a soma
envolvendo m´ultiplos de algum g ∈ G depende somente se o n´umero de ocorrˆencias
´e par ou ´ımpar. Agora se G = {0}, escolha algum g
1
∈ G n˜ao nulo, o grupo gerado
por g
1
´e portanto um grupo de dois elementos G
1
= {0, g
1
}. Se G = G
1
a afirmativa
´e verdadeira. Se G = G
1
escolha g
2
n˜ao nulo tal que g
2
n˜ao perten¸ca a G
1
, o grupo
gerado por {g
1
, g
2
} ´e o grupo G
2
= {
1≤j≤2
a
j
g
j
; a
j
∈ {0, 1}}. Se G = G
2
continue
34
este processo que ´e finito pois G ´e finito. A correspondˆencia
1≤j≤n
a
j
g
j
↔ a ∈ (Z
2
)
n
´e ent˜ao um isomorfismo entre G e (Z
2
)
n
.
Portanto Λ/Λ
´e isomorfo a (Z
2
)
n
se, e somente se, cada classe n˜ao nula de Λ
em Λ ´e sua pr´opria inversa sobre a adi¸c˜ao m´odulo Λ
.
Teorema 2.39. Se Λ
´e um subreticulado de Λ e Λ/Λ
´e finito ent˜ao existe um
rotulamento bin´ario linear de Λ/Λ
se, e somente se, 2Λ ´e um subreticulado de Λ
.
Demonstra¸c˜ao: Seja Λ
+ t, t ∈ Λ, alguma classe lateral de Λ
em Λ. Ent˜ao
(Λ
+ t) + (Λ
+ t) = Λ
+ 2t ´e igual a classe lateral do zero se, e somente se, 2t ∈ Λ
.
Segue que, toda classe lateral de Λ
em Λ ´e inversa dela mesma se, e somente se,
2t ∈ Λ
∀t ∈ Λ, isto ´e, se, e somente se, 2Λ ´e um subreticulado de Λ
.
Muitas classes laterais generalizadas de c´odigos C(Λ/Λ
; C) que utilizam c´odigos
bin´arios C s˜ao baseadas em parti¸c˜oes reticuladas Λ/Λ
que n˜ao admitem rotulamen-
tos bin´arios lineares isom´etricos.
Exemplo 2.40. N˜ao existe rotulamento bin´ario linear da parti¸c˜ao 4-caminhos Z/4Z
por A = (Z
2
)
2
, visto que se a ´e o r´otulo para a classe lateral 4Z+1, ent˜ao a⊕a = (00)
precisa aplicar-se a 4Z, n˜ao a 4Z + 2, assim a linearidade n˜ao pode ser obtida.
2.10.2 Subconjunto Tempo-Zero
Nesta subse¸c˜ao definiremos subconjunto Tempo-Zero utilizando c´odigos bin´arios
lineares convolucionais. A seguir daremos a defini¸c˜ao de c´odigos convolucionais.
Defini¸c˜ao 2.41. Um c´odigo convolucional ´e um tipo de c´odigo corretor de erro em
que cada conjunto de m sinais ´e transformado em um conjunto de n sinais, onde
n ≥ m.
35
Seja C(S/S
; C) um c´odigo em um espa¸co de sinais reticulado, com C um c´odigo
bin´ario linear convolucional de ´ındice k/n. Ent˜ao quando a codifica¸c˜ao est´a no
estado ”zero” a pr´oxima codifica¸c˜ao pode produzir 2
k
valores a ∈ F
n
. Se C ´e linear
estes valores formam um grupo aditivo ou um subespa¸co de F
n
. Este subespa¸co
denotado por C
0
´e denominado c´odigo Tempo-Zero.
Defini¸c˜ao 2.42. Seja
m(C
0
) = {m(a); a ∈ C
0
}
a imagem do c´odigo tempo-zero. Este conjunto recebe o nome de subconjunto de
tempo-zero do conjunto de sinais S.
Se C ´e uma classe lateral generalizada de c´odigos, ent˜ao o Teorema 2.16 aplica-se
de forma direta ao Teorema 2.43 enunciado abaixo.
Teorema 2.43. Se S/S
´e uma parti¸c˜ao geometricamente uniforme com um rotu-
lamento isom´etrico bin´ario m : A → S/S
, onde A = (Z
2
)
n
, ent˜ao:
i. O subconjunto Tempo-zero m(C
0
) ´e geometricamente uniforme.
ii. Os r´otulos transladados m(C
0
⊕ b) s˜ao todos congruentes a m(C
0
)
iii. A parti¸c˜ao 2
n−k
-caminhos de S no r´otulo transladado mC
0
⊕ b ´e uma parti¸c˜ao
geometricamente uniforme.
A maior parte dos c´odigos reticulados utilizam c´odigos convolucionais bin´arios
C de taxa k/(k + 1). Neste caso existem apenas dois r´otulos transladados, o sub-
conjunto tempo-zero m(C
0
) e seu complemento.
2.10.3 Rotulamentos Regulares
Definiremos abaixo duas no¸c˜oes de regularidades, primeiramente uma no¸c˜ao fraca e
em seguida uma no¸c˜ao forte de regularidade.
36
Defini¸c˜ao 2.44. Uma aplica¸c˜ao r´otulo m : A → Λ/Λ
definida por m(a) = Λ
+t(a)
´e regular no sentido fraco se a distˆancia m´ınima ao quadrado entre os elementos de
duas classes laterais depende somente da diferen¸ca dos r´otulos:
d
2
min
[m(a), m(a
)] = d
2
min
[Λ
+ t(a), Λ
+ t(a
)] = N
2
(−a ⊕ a
)
Defini¸c˜ao 2.45. Uma aplica¸c˜ao r´otulo m : A → Λ/Λ
definida por m(a) = Λ
+t(a)
´e regular no sentido forte se o conjunto das distˆancias entre qualquer elemento da
classe lateral Λ
+ t(a) e todos os elementos de outra classe lateral Λ
+ t(a
) depen-
dem somente da diferen¸ca dos r´otulos, isto ´e, se o peso perfil de qualquer diferen¸ca
Λ
− t(a) + t(a
) ´e igual ao peso perfil da classe lateral Λ
− t(0) + t(−a ⊕ a
).
Segue ent˜ao que regularidade no sentido forte implica em regularidade no sentido
fraco.
Proposi¸c˜ao 2.46. Um rotulamento isom´etrico de uma parti¸c˜ao reticulada ´e regular
no sentido forte.
Demonstra¸c˜ao: Se m(a) = Λ
+ t(a) ´e um rotulamento isom´etrico, ent˜ao pelo
Teorema 2.22 existe uma isometria u
−a
tal que:
m(−a ⊕ a
) = Λ
+ t(−a ⊕ a
) = u
−a
[Λ
+ t(a)];
m(−a ⊕ a) = m(0) = Λ
+ t(0) = u
−a
[Λ
+ t(a)].
Como u
−a
´e uma isometria, o conjunto das distˆancias de qualquer elemento de
Λ
+ t(a) a todos os elementos de Λ
+ t(a
) ´e o mesmo conjunto de distˆancias de
qualquer elemento de Λ
+ t(0) a todos elementos de Λ
+ t(−a ⊕ a
), que tem o
mesmo peso perfil da classe lateral Λ
− t(0) + t(−a ⊕ a
), que depende somente da
diferen¸ca entre r´otulo −a ⊕ a
.
Assim mostramos que existe um rotulamento bin´ario isom´etrico e portanto regu-
lar no sentido forte para qualquer parti¸c˜ao Λ/Λ
tal que Z
n
/Λ/Λ
/4Z
n
´e uma parti¸c˜ao
reticulada.
37
Cap´ıtulo 3
C´odigos Hiperb´olicos
Geometricamente Uniformes
Neste cap´ıtulo generalizaremos o conceito de c´odigos geometricamente uniformes,
primeiramente explorados em espa¸cos Euclideanos, aos espa¸cos Hiperb´olicos. Tam-
b´em mostraremos uma caracteriza¸c˜ao de classes laterais generalizadas de c´odigos
atrav´es do conceito de c´odigos G-lineares.
Um dos principais objetivos de c´odigos geometricamente uniformes ´e a constru¸c˜ao
de parti¸c˜oes geometricamente uniformes e em particular classes laterais generaliza-
das.
Estenderemos os conceitos de conjuntos de sinais, reticulados e conjuntos parti-
cionados para o plano hiperb´olico, marcando assim o uso das tessela¸c˜oes hiperb´olicas
regulares associadas aos seus correspondentes grupos de simetrias.
Embora os grupos de isometrias hiperb´olicos tenham maior complexidade que
os grupos de isometrias Euclideanos os procedimentos e os conceitos para parti¸c˜oes
geometricamente uniformes podem ser considerados os mesmos.
Em [3] ´e mostrado que a probabilidade de erro associada a uma constela¸c˜ao
de sinais depende da curvatura k, tendo melhor performance quando consideradas
superf´ıcies com curvatura constante negativa.
38
3.1 Tessela¸c˜oes Hiperb´olicas
Para a Teoria da Comunica¸c˜ao uma das estruturas alg´ebricas mais importantes ´e
o espa¸co vetorial, que ´e um espa¸co cuja a m´etrica ´e compat´ıvel com a norma, por
exemplo os espa¸cos Euclideanos. O uso desta estrutura possibilita modelar e a-
nalisar novos sistemas de comunica¸c˜ao, novos esquemas de modula¸c˜ao, t´ecnicas de
processamento de sinais entre outras. A seguir definiremos uma tessela¸c˜ao regular
no plano hiperb´olico SP D.
Defini¸c˜ao 3.1. Uma tessela¸c˜ao regular do plano hiperb´olico SP D ´e uma parti¸c˜ao de
SP D por pol´ıgonos regulares com o mesmo n´umero de lados os quais se interceptam
inteiramente ou apenas nos v´ertices. Uma tessela¸c˜ao regular na qual q pol´ıgonos
regulares se encontram em cada v´ertice ´e denotada por {p, q}.
Associado com cada tessela¸c˜ao {p, q} existe um grupo chamado grupo sim´etrico
de {p, q} e denota-se por [p, q]. Este grupo ´e o grupo de isometrias de SP D, gerado
por reflex˜oes em retas hiperb´olicas em que as tessela¸c˜oes {p, q} auto refletem. O
grupo [p, q] ´e gerado pelas reflex˜oes r
1
, r
2
e r
3
no bordo do triˆangulo hiperb´olico
com ˆangulos
π
2
,
π
p
,
π
q
.
A apresenta¸c˜ao do grupo [p, q] associado com a tessela¸c˜ao {p, q} ´e dada por,
r
1
, r
2
, r
3
: r
2
1
= r
2
2
= r
2
3
= (r
2
r
1
)
p
= (r
3
r
2
)
q
= (r
1
r
3
)
2
= e
Dado uma tessela¸c˜ao {p, q} com grupo sim´etrico [p, q] a tessela¸c˜ao dual desta ´e
{q, p} com grupo sim´etrico [q, p]. Os grupos [p, q] e [q, p] s˜ao isomorfos, entretanto
as tessela¸c˜oes {p, q} e {q, p} coincidem se, e somente se, p = q. O caso p = q ´e
chamado de dual pr´oprio.
Se p = q = 4g, onde g ´e um inteiro maior ou igual a 2, a tessela¸c˜ao {4g, 4g}
produz uma cobertura universal para SPD. O grupo fundamental desta superf´ıcie
de gˆenero g dado por
π
g
= a
1
, ..., a
g
, b
1
, ..., b
g
:
g
i=1
[a
i
, b
i
] = 1
39
´e um subgrupo normal de [4g, 4g]. Desta forma segue que o grupo [4g, 4g] pode ser
escrito como o produto semidireto
[4g, 4g] = π
g
D
4g
,
onde D
4g
denota o grupo diedral com 8g elementos. Para maiores informa¸c˜oes sobre
tessela¸c˜oes ver [7].
3.2 Conjuntos de Sinais Associados a Grupos
Assim como no espa¸co Euclideano um conjunto de sinais em um espa¸co hiperb´olico
´e um subconjunto discreto de SP D.
Defini¸c˜ao 3.2. Um conjunto de sinais S em SP D se corresponde com um grupo G,
se existe uma aplica¸c˜ao sobrejetiva m : G → S tal que ∀g, g
∈ G d(m(g), m(g
)) =
d(m(g
−1
g
), m(e)). Tal aplica¸c˜ao m ´e denominada aplica¸c˜ao correspondˆencia. Se m
´e injetiva, ent˜ao m
−1
´e um rotulamento de correspondˆencia.
Se m : G → S ´e uma aplica¸c˜ao correspondˆencia ent˜ao H = m
−1
(m(e)) ´e um
subgrupo de G e g ≡ g
modH se, e somente se, m(g) = m(g
). Assim para cada
aplica¸c˜ao correspondˆencia m podemos estabelecer uma correspondˆencia bijetiva en-
tre as classes laterais gH e os elementos m(g) de S. Imediatamente seque que se
H ☎ G, ent˜ao a aplica¸c˜ao m :
G
H
→ S ´e um rotulamento de correspondˆencia.
Dizemos que um rotulamento m : G → S ´e um rotulamento efetivo se H n˜ao
cont´em nenhum subgrupo normal n˜ao trivial de G. Neste caso, dizemos que S ´e
efetivamente correspondido `a G.
Exemplo 3.3. Seja A um espa¸co m´etrico com uma m´etrica invariante d
A
e G um
grupo com uma m´etrica de grupo d
G
tal que existe uma aplica¸c˜ao m : G → A que
´e uma isometria. Ent˜ao para quaisquer g, h ∈ G temos
d
A
(m(g), m(h)) = d
G
(g, h) = d
G
(gh
−1
, e) = d
A
(m(gh
−1
), m(e))
resultando que m ´e um rotulamento de correspondˆencia.
40
A seguir definiremos um c´odigo G-linear onde G ´e um grupo.
Defini¸c˜ao 3.4. Um c´odigo C ⊆ S
I
´e G-linear se existe uma isometria µ : G → S,
um grupo c´odigo D ≤ G
I
e uma permuta¸c˜ao σ ∈ S
I
tal que σ(C) = µ(D), µ tamb´em
denota a extens˜ao µ : G
I
→ S
I
.
3.3 Conjuntos de Sinais Geometricamente Uni-
formes Hiperb´olicos
Conforme Defini¸c˜ao 2.6 dada no Cap´ıtulo 2 um conjunto de sinais S ´e chamado
geometricamente uniforme se a a¸c˜ao do grupo de simetrias Γ(S) em S ´e transitiva.
Exemplo 3.5. Considere a tessela¸c˜ao {8, 8} no plano hiperb´olico. Ent˜ao o conjunto
S consistindo de centro de massa dos oct´ogonos da tessela¸c˜ao (ou equivalentemente
os v´ertices dos oct´agonos da tessela¸c˜ao dual ) ´e geometricamente uniforme, para
cada x ∈ S fixo, temos que S = {T (x) : T ∈ [8, 8]}.
Slepian, [12] nos fornece um exemplo de um conjunto de sinais S com 10 sinais em
R
5
que n˜ao ´e ´orbita de qualquer subgrupo de simetrias de R
5
. Portanto nem todos
os subconjuntos de sinais, mesmo os euclideanos, s˜ao geometricamente uniformes.
Como j´a vimos no Cap´ıtulo 2 um subgrupo U(S) de Γ(S) ´e um gerador de S, se
S = {u(s
0
); u ∈ U(S)}.
3.4 Parti¸c˜oes Geometricamente Uniformes Hiper-
b´olicas
O conceito de parti¸c˜oes geometricamente uniformes mostrado no Cap´ıtulo 2 foi in-
troduzido por Forney em [4], no contexto de conjuntos de sinais Euclideanos. Como
mencionado anteriormente embora os grupos de isometria hiperb´olicos
41
tenham uma maior complexidade quando comparados aos grupos de isometrias eu-
clideanos, ´e poss´ıvel estender o conceito de parti¸c˜oes geometricamente uniformes,
como exemplificaremos nesta se¸c˜ao.
Exemplo 3.6. As parti¸c˜oes de Ungerboeck [15] s˜ao parti¸c˜oes bin´arias geometrica-
mente uniformes associadas com um conjunto de sinais M − PSK com M = 2
k
e
os subgrupos da forma 2
j
− P SK (n˜ao necessariamente normais) determinam uma
seq¨uˆencia de parti¸c˜oes. Os pol´ıgonos S associados `as tessela¸c˜oes hiperb´olicas (p
pol´ıgonos regulares ) tˆem D
p
como seu grupo de simetrias. Assim os pol´ıgonos S
s˜ao constela¸c˜oes geradas por p − P SK.
Exemplo 3.7. No caso Euclideano, se Λ ´e um reticulado e Λ
´e um subreticulado
de Λ de ´ındice finito, ent˜ao o conjunto de sinais S = Λ + a ´e particionado em |Λ/Λ
|
subconjuntos geometricamente uniformes.
No caso hiperb´olico temos alguns pontos a considerar. Como a tessela¸c˜ao dual ´e
gerada por transla¸c˜oes ent˜ao uma condi¸c˜ao equivalente a T (Λ) = Λ, onde T denota
transla¸c˜ao, ´e exatamente o fato de a tessela¸c˜ao ser auto-dual, do tipo {p, p}.
3.5 C´odigos Geometricamente Uniformes em Es-
pa¸co de Sinais Hiperb´olicos
Seja S/S
uma parti¸c˜ao geometricamente uniforme no espa¸co hiperb´olico induzida
pelo grupo U(S)/U(S
). Seja A U(S)/U(S
), os conceitos de isomorfismo r´otulo
e rotulamento isom´etrico dados no Cap´ıtulo 2 se aplicam tamb´em a essa parti¸c˜ao.
Defini¸c˜ao 3.8. Seja S/S
uma parti¸c˜ao geometricamente uniforme com grupo r´otulo
A e D ✂ A
I
ent˜ao uma classe lateral generalizada de c´odigos ´e o subconjunto
C(S/S
; D) = {m(c) : c ∈ D} ⊆ S
I
.
O pr´oximo teorema promove uma conex˜ao entre G-linearidade e as classes laterais
generalizadas de c´odigos.
42
Teorema 3.9. Sobre as hip´oteses da Defini¸c˜ao 3.8 uma classe lateral generalizada
de c´odigos ´e um c´odigo U(S) − linear.
Demonstra¸c˜ao: Seja
µ : U(S) → S
u → u(s
0
)
(3.1)
um rotulamento de correspondˆencia para algum ponto fixo s
0
∈ S.
Tomemos
A = U(S)/U(S
) = {uU(S
); u ∈ U(S)}
e o rotulamento
m : A → S/S
uU(S
) → u(S
).
(3.2)
Temos que se uU(S
) = vU(S
) ent˜ao u
−1
v ∈ U(S
) onde u
−1
v(S
) = S
, portanto
u(S
) = v(S
).
Seja H = {u ∈ U(S); uU(S
) ∈ D}. Assim se u, v ∈ H, uU(S
), vU(S
) ∈ D,
como D ≤ A segue que uv
−1
U(S
) ∈ D e uv
−1
∈ H. Desta forma, como e ∈ H
temos que H ≤ U(S). Em outras palavras, como
µ(H) = {u(s
0
) : u ∈ H} =
uU(S
)∈D
u(S
) =
m(c) = C(S/S
; D),
isso mostra que C(S/S
; D) ´e U(S) − linear.
No contexto hiperb´olico, uma generaliza¸c˜ao da defini¸c˜ao euclideana dada no
Cap´ıtulo 2 de classes laterais generalizadas de c´odigos nos obriga a condi¸c˜ao que o
c´odigo D seja um subgrupo normal de A
I
.
O pr´oximo teorema nos assegura a validade da seguinte vers˜ao do Teorema 2.34
nas classes laterais generalizadas de c´odigos em espa¸cos de sinais hiperb´olicos.
Defini¸c˜ao 3.10. As classes laterais de D podem ser escritas como Da, onde a ∈ A
I
.
Para cada classe lateral o rotulamento m : A
I
→ (S/S
)
I
define subconjuntos de S
I
chamados de r´otulos transladados de C dados por
C(S/S
; Da) =
c∈D
m(ca).
43
Teorema 3.11. Se C(S/S
; D) ´e uma classe lateral generalizada de c´odigos, ent˜ao
S
I
/C(S/S
; D)/(S
)
I
´e uma cadeia de parti¸c˜oes geometricamente uniformes e os
r´otulos transladados C(S/S
; Da) de C(S/S
; D) s˜ao geometricamente uniformes,
mutuamente congruentes e tˆem o grupo de simetrias U(C(S/S
; D)) = V em comum.
A demonstra¸c˜ao deste teorema decorre dos trˆes lemas demonstrados a seguir.
Lema 3.12. Se C(S/S
; D) ´e uma classe lateral generalizada de c´odigos, ent˜ao
(S
I
/(S
)
I
) (S/S
)
´e uma parti¸c˜ao geometricamente uniforme e m : A
I
→ (S/S
)
I
´e um rotulamento
isom´etrico para esta parti¸c˜ao.
Demonstra¸c˜ao: Primeiramente vamos mostrar que U(S
I
) = U(S)
I
. De fato, temos
U(S
I
) ⊆ U(S)
I
. Agora se H ≤ U(S)
I
ent˜ao H =
k∈I
H
k
onde H
k
≤ U(S) ∀k ∈ I,
e se U(S
I
) = H U(S)
I
temos que H
k
U(S) para qualquer k ∈ I, mas ent˜ao S =
Hs
0
contrariando a minimalidade de U(S). Portanto U(S
I
) = U(S)
I
. Temos ainda
que U(S
)
I
✂ U(S)
I
pois U(S
) ✂ U(S). Assim m : A
I
→ (S/S
) ´e uma isometria,
onde U(S)
I
/U(S
)
I
produz uma parti¸c˜ao geometricamente uniforme S
I
/(S
)
I
com
espa¸co r´otulo A
I
U(S)
I
/U(S
)
I
.
Lema 3.13. Se D ✂ A
I
ent˜ao com a estrutura induzida, (S
) ≤ C(S/S
; D) ≤ S
I
,
temos os isomorfismos:
S
I
/C(S/S
; D) A/D; C(S/S
; D)/(S
)
I
D/e
A
I
D; S
I
/(S
)
I
A
I
/e
A
I
A
I
,
que ´e a cadeia de parti¸c˜oes dos grupos S
I
/C(S/S
; D)/(S
)
I
e A
I
/D/e
A
I
s˜ao iso-
morfas.
Demonstra¸c˜ao: Consideremos o caso |I| = 1. Para o caso geral basta estender as
44
considera¸c˜oes a cada coordenada.
U(S) →
f
S
| |
V → C(S/S
; D)
| |
U(S
) → S
(a) Primeiramente vamos mostrar que C(S/S
; D) ≤ S. Se φ, ψ ∈ C(S/S
; D) ent˜ao
existe c
1
, c
2
∈ D tal que φ ∈ m(c
1
) e ψ ∈ m(c
2
). Se f : U(S) → S ´e uma bije¸c˜ao
que induz a estrutura de grupo em S, ent˜ao existe v, w ∈ U(S) tal que f(v) = φ
e f(w) = ψ. Ent˜ao vw ∈ u
c
1
U(S
).u
c
2
U(S
) = u
c
1
u
c
2
U(S
) = u
c
1
c
2
U(S
),
e f(vw) = φψ ∈ m(c
1
c
2
). Portanto, φψ ∈ C(S/S
; D). Como vU(S
) =
u
c
1
U(S
) temos que (vU(S
))
−1
= (u
c
1
U(S
))
−1
ou v
−1
U(S
) = u
−1
c
1
U(S
) =
u
c
−1
1
U(S
). Portanto, φ
−1
∈ m(c
−1
1
) ∈ C(S/S
; D) e C(S/S
; D) ≤ S.
(b) Agora mostraremos que S
≤ C(S/S
; D). Como C(S/S
; D) =
c∈D
m(c),
definimos V = f
−1
(C(S/S
; D)). Isto implica que V ≤ U(S) e
V = f
−1
(C(S/S
; D))
= f
−1
c∈D
m(c)
=
c∈D
f
−1
(m(c)) =
c∈D
u
c
U(S
).
Em particular, m(1) = U(S
) ⊆ V , segue que S
⊆ C(S/S
; D) ou S
≤
C(S/S
; D).
(c) A/D S/C(S/S
; D). Como V = f
−1
(C(S/S
; D)) temos que
U(S)/V S/C(S/S
; D).
Considerando
φ : A → U(S)/V
a → u
a
V
45
φ ´e bem definida e o Kerφ = D. Portanto,
A/D U(S)/V S/C(S/S
; D).
(d) D C(S/S
; D)/S
. Considerando,
g : A → U(S)/U(S
)
e o isomorfismo r´otulo como g(c) = u
c
U(S
), temos
g(D) = V /U(S
).
( De fato, se u
c
U(S
) ∈ g(D), por defini¸c˜ao u
c
U(S
) ⊆ V , e assim u
c
U(S
) ∈
V/U(S
) ent˜ao uU(S
) = wU(S
) se
w ∈
c∈D
u
c
U(S
) ou w = u
c
u
1
para c ∈ D e u
1
∈ U(S
).
Assim g(D) = V /U(S
) ). Segue que
D V/U(S
). (3.3)
Da´ı, temos que V/U(S
) ´e a imagem de C(S/S
; D) pelo isomorfismo r´otulo,
ou equivalentemente,
V =
u∈g(D)
uU(S
) =
g(D).
Seja f|V temos,
V/U(S
) C(S/S
; D)/S
, (3.4)
de (3.3) e (3.4) temos que D C(S/S
; D)/S
.
Por fim A S/S
decorre diretamente do isomorfismo r´otulo.
Lema 3.14. Os r´otulos transladados de C(S/S
; D) s˜ao as classes laterais `a direita
de C(S/S
; D) em S
I
sobre a estrutura de grupo induzida.
46
Demonstra¸c˜ao: Consideremos o caso |I| = 1. Para o caso geral basta estender as
considera¸c˜oes a cada coordenada. Seja
f
−1
(C(S/S
; Da)) = f
−1
c∈D
m(c.a)
=
c∈D
f
−1
(m(c.a)) =
c∈D
u
c.a
U(S
)
=
c∈D
u
c
u
a
U(S
) =
c∈D
u
c
U(S
)
u
a
=
c∈D
f
−1
m(c)
f
−1
(f(u
a
))
=
f
−1
(
c∈D
m(c))
f
−1
(f(u
a
)) = f
−1
c∈D
m(c)
f(u
a
)
= f
−1
[[C(S/S
; D.a)]f(u
a
)]
Segue que C(S/S
; D.a) = C(S/S
; D).f(u
a
)
47
Conclus˜ao
O presente trabalho teve como finalidade estender ao plano hiperb´olico as defini¸c˜oes
de conjuntos de sinais, parti¸c˜oes geometricamente uniformes e classes laterais de
c´odigos generalizadas. Al´em de estabelecer uma rela¸c˜ao entre os c´odigos e a defini¸c˜ao
de G-linearidade. Para isso estruturamos o texto como a seguir.
No Cap´ıtulo 1 apresentamos alguns requisitos para o bom entendimento da dis-
serta¸c˜ao. Descrevemos propriedades b´asicas de estruturas alg´ebricas e m´etricas de
maior importˆancia para a teoria de comunica¸c˜ao. Introduzimos tamb´em a teoria de
c´odigos corretores de erros.
J´a no Cap´ıtulo 2 foram definidos conjuntos de sinais geometricamente uniformes
em espa¸cos euclideanos e verificamos algumas propriedades destes conjuntos. Exi-
bimos a teoria das parti¸c˜oes geometricamente uniformes e definimos rotulamentos
isom´etricos. Em seguida, introduzimos o conceito de c´odigos geometricamente uni-
formes em espa¸cos de sinais, concluindo este cap´ıtulo com outras no¸c˜oes de uni-
formidade.
No ´ultimo cap´ıtulo, Cap´ıtulo 3, definimos G − linearidade, tessela¸c˜oes regulares
e estendemos ao plano hiperb´olico a teoria das parti¸c˜oes geometricamente uniformes.
48
Referˆencias Bibliogr´aficas
[1] Agustini, E., Constela¸c˜oes de Sinais em Espa¸cos Hiperb´olicos, Tese de
Doutorado, IMECC-UNICAMP, Brasil, (2002).
[2] Biglieri, E. and Elia, M., The Isometry Group of Geometrically Uniform Spheri-
cal Signal Sets, in IEEE Internetional Symposium on Information Theory, agosto
1991.
[3] Cavalcante, R.G. , Performance Analysis of Signal Constellations in Riemannian
Varieties, MS Thesis, FEEC-UNICAMP, Brasil, (2002)(portuguese)
[4] Forney, G.D. Jr., Geometrically uniform codes, IEEE Trans. Inform. Theory, vol.
IT37 no. 5, pp. 1241-1260, Sep.(1991).
[5] Hefez, A., e Villela, M. L. T., C´odigos Corretores de Erros, Rio de Janeiro,
IMPA, 2002.
[6] Lima, E.L., Espa¸cos M´etricos, Rio de Janeiro, IMPA, 1977.
[7] Lazari, H., Palazzo Jr, R., Geometrically Uniform Hyperbolic Codes, Computa-
tional e Applied Mathematics, SBMAC, vol.24 no.2pp. 173-192, 2005.
[8] Lazari, H., Uma Contribui¸c˜ao `a Teoria dos C´odigos Geometricamente Uniformes
Hiperb´olicos, Tese de Doutorado, FEEC-UNICAMP, Brasil, (2000).
[9] Rotman, J. J., The Theory of Groups, An Introdution, Boston, Allyn and Bacon,
Inc. 1973.
49
[10] Shannom, C. E.,A Mathematical Theory of Communication, Bell Syst. Tech.
J., vol.27, pp. 379-423 e 623-656, julho/outubro 1948.
[11] Shokranian, S., Geometria Hiperb´olica e Teoria do N´umeros, Bras´ılia, UNB,
2004.
[12] Slepian, D. , Group codes for the gaissian channel, Bell Sys. Tech. Journal, vol.
37 (1968), p. 575-602.
[13] Slepian, D., On Neighbor distance and symmetry in group codes, IEEE Trans.
Inform. Theory, vol.IT-17, pp. 630-632, sept. 1971.
[14] Souza, M. J., Realiza¸c˜oes de Constela¸c˜oes de Sinais Hiperb´olicos Densos Asso-
ciadas a Sistemas Lineares Atrav´es das Fun¸c˜oes Automorfas, Tese de Doutorado,
FEEC-UNICAMP, Brasil, (2005).
[15] Ungerboeck, G., Channel coding with multilevel/phase signals, IEEE Trans.
Inform. Theory, vol. IT 28 no. 1 pp. 55-67, Jan.(1982)
50
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
