$
'
Universidade Estadual de Campinas
Faculdade de Engenharia Elétrica e de Computação
Departamento de Comunicações
Uma Abordagem Algébrico-Topológica dos
Sistemas de Transmissão da Informaçãoa
Reginaldo Palazzo Jr.
a Suporte
&
Financeiro: FAPESP, CAPES e CNPq
1
%
$
'
Apresentação
I - Sistemas de Comunicação:
• Ia - Canal: Mergulho de Grafos em Superfı́cies;
• Ib - Modulação: Geração de Sinais GU em Espaços Homogêneos;
• Ic - Demodulação: Projeção em Variedades Riemannianas.
II - Sistemas de Informação Biológica:
• IIa: Motivação e Pesquisa em Codificação Genética;
• IIb: Modelos de Sistemas de Transmissão de Informação Biológica;
• IIc: Modelo de Codificação Biológica.
III - Sistemas Quânticos:
&
2
%
$
'
I - Sistemas de Comunicação
• Objetivo:
Mostrar que a estrutura topológica deve anteceder a estrutura de
espaço vetorial (métrico).
Qual deve ser a abordagem?
Identificação da geometria da superfı́cie (variedade) de cada bloco
começando com o mergulho do grafo associado ao canal DMC.
• Conseqüências:
Novos conceitos matemáticos e abordagens serão incorporados aos
já conhecidos de modo a alcançar os objetivos de melhor
desempenho e complexidade.
&
3
%
$
'
Fonte
(E1 , d1 )
(E2 , d2 )
(E3 , d3 )
Codificador
de Fonte
Codificador
de Canal
Modulador
(E0 , d0 )
Métrica Induzida
Ruído
Canal
Destinatário
(E1 , d1 )
(E2 , d2 )
(E3 , d3 )
Decodificador
de Fonte
Decodificador
de Canal
Demodulador
Figura 1: Modelo Sistema de Comunicação Digital
• Atual: projeto baseado em espaços vetoriais com métricas
apropriadas.
• Proposta: projeto deve considerar a estrutura topológica associada a
cada bloco, começando pelo bloco tracejado.
&
4
%
$
'
Canais DMC resultantes do processo de quantização (modulação BPSK)
BPSK
R1
1
R0
R11
0
1
R10
R01
Divide em 8 subintervalos
R00
0
1
0
000
00
0
0
0
0
01
001
010
011
1
1
10
1
1
11
100
101
110
111
Figura 2: Canais C2 [2], C2,4 [4], C2,8 [8]
&
5
%
'
Canais DMC resultantes do processo de quantização (modulação 4-PSK)
$
4−PSK
1
0
3
2
0
0
0
0
0
0
1
1
1
1
1
1
2
2
2
2
2
2
3
3
3
3
3
3
A
Figura 3: Canais C4 [4], C4 [3], C4,5 [4]
&
6
%
$
'
Motivação para a Proposta: Primeiro Caso
C2,8 [8, 2] ≡ K2,8
C2 [2] ≡ K2,2
֒→
←→
֒→
←→
z }| {
{S(8), T (6), 2T (4), 3T (2)}
|
{z
}
z}|{
{S(2)}
Mergulho
Km,n
Superfı́cie Compacta
Figura 4: Mergulhos
&
7
%
$
'
Motivação para a Proposta: Segundo Caso
Topological Space
Metric Space
a
M−QAM
b
b
Torus
a
Sphere
g=1
a
M−PSK
a
Plane Model
Pe(QAM) < Pe(PSK)
g=0
Space Model
Figura 5: Espaços Métrico e Topológico
&
8
%
$
'
Mergulhos em Superfı́cies Mı́nimas
C8 [3] ←→
C6 [3] ←→
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
0
0
1
1
2
2
3
3
4
4
5
5
֒→
≡ esfera com 2 fins
Catenoid
≡ esfera com 3 fins
֒→
Trinoid
Figura 6: Mergulhos
&
9
%
$
'
Realization
Abstract Approach
Existence of GU Signal Sets
in Homogeneous Spaces
DMC Channel
Riemannian
Topology
Graph
Topological
Topology
Properties
Invariants
Geometry
Geometric
Invariants
Genus
Sectional Curvature
z
}|
{
g1 > g2 → Pe (g1 ) < Pe (g2 )
z
}|
{
K1 < K2 → Pe (K1 ) < Pe (K2 )
Figura 7: Visão Geral da Proposta
&
10
%
$
'
Transformação
Conform. Homeomorfa
Superfı́cie de Riemann
↓
⇐⇒
Variedade 2-D
(geometria conforme)
(geometria Riemanniana)
m
}|
m
z
Topologia
Algébrica
{
z
}|
Geometria
Diferencial
{
Combinatorial
Caract. Euler,
χ(Ω) = 2 − 2g
g = 0 ↔ χ(Ω) > 0
g = 1 ↔ χ(Ω) = 0
z
g ≥ 2 ↔ χ(Ω) < 0
}|
{
←→
Curvatura Seccional, K
←→
K = 0,
Euclidiano
K < 0,
z
Hiperbólico
}|
{
←→
←→
Sup. Compacta, Orientada
&
K > 0,
Elı́ptico
Espaços Homogêneos
11
%
$
'
Resultados:

 K > 0, elı́ptico
• Estender o conceito de Códigos GU,
para
 K = 0, euclidiano
Códigos GU, K constante e negativo (geometria hiperbólica);
• Considerar a Análise de Desempenho de sistema de comunicação
digital em Variedades N-dimensionais;
• Mostrar que o melhor desempenho, dentre os espaços com
curvatura constante, é alcançado quando a curvatura é negativa.
&
12
%
'
Consequência Teorema Uniformização (Koebe and Poincaré)
$
Qualquer curva algébrica de g ≥ 2 é conformemente equivalente a
H2 /G, G ⊂ PSL(2, R) é um grupo Fuchsiano com a métrica hiperbólica.
Reciprocamente, qualquer superfı́cie compacta hiperbólica é isomorfa
a uma curva algébrica.
Métrica Hiperbólica
−→
Grupo Fuchsiano
Existem bons algoritmos que determinam os geradores do grupo
Fuchsiano em termos das coordenadas de Fenchel-Nielsen da superfı́cie
Grupo Fuchsiano
−→
Equações da Curva Algérica
Problema em aberto
gênero g de uma curva algébrica é um invariante
&
13



 Topológico



Corpo de Funções
%
$
'
Equação diferencial ordinária de segunda ordem é do tipo Fuchsiana
′′
′
y (z) + p(z)y (z) + q(z)y(z) = 0
se todo ponto singular no plano complexo estendido for regular, e
p(z) =
q(z) =
A1
An
+···+
(z − ε1 )
(z − εn )
B1
Bn
C1
Cn
+
·
·
·
+
+
+
(z − ε1 )2 (z − ε1 )
(z − εn )2 (z − εn )
• A1 + · · · + An = 2
• C1 + · · · +Cn = 0
• (B1 + · · · + Bn ) + (ε1C1 + · · · + εnCn ) = 0
• (2ε1 B1 + · · · + 2εn Bn ) + (ε21C1 + · · · + ε2nCn ) = 0
&
14
%
$
'
Uniformização de Curva Algébrica - w2 = z3 − 3z2 + 2z (2g + 1 = 3)
′′
′
(z3 − 3z2 + 2z)y + (4z2 − 7z + 2)y + (2z − 1)y = 0
cujas singularidades são 0, 1, 2 e ∞.
¥
0
¥
1
6
1
5
1
4
1
3
2
5
1
2
3
5
2
3
3
4
4
5
5
6
1
Figura 8: Gráfico de Farey em [0, 1]
&
15
%
'
Modelo para a Geometria Hiperbólica
$
Semi-plano Superior: H2 = {z = x + iy : y > 0, x, y ∈ R}
Disco de Poincaré: D = {|z| < 1; z ∈ C}
y
geodésicas
x
Semi-plano Superior
Disco de Poincaré
Figura 9: Modelos do Plano Hiperbólico
&
16
%
'


a b
az + b

,
⇐⇒ A =
TA (z) =
cz + d
c d
$
ad − bc = 1,
a, b, c, d ∈ R



 > 2, hiperbólica
Tr(A) = a + d
= 2, Parabólica



< 2, elı́ptica
Transformação Hiperbólica
Transformação Parabólica
Transformação Elı́ptica
Figura 10: Transformações hiperbólicas no semi-plano superior
&
17
%
$
'
Figura 11: Triângulos hiperbólicos
&
18
%
$
'
Ia - Canal: Mergulho de Grafos em Superfı́cies
(i) Gênero mı́nimo- superfı́cie orientada [Ringel]:
gm (Km,n ) = {(m − 2)(n − 2) /4}, for m, n ≥ 2,
onde {α} denota o menor inteiro maior ou igual a α.
(ii) Gênero máximo - superfı́cie orientada [Ringeisen]:
gM (Km,n ) = [(m − 1)(n − 1)/2] , for m, n ≥ 1,
onde [α] denota o maior inteiro menor ou igual a α.
(iii) Gênero mı́nimo - superfı́cie não orientada [Ringel]:
g̃ (Km,n ) = [(m − 2) (n − 2) /2] .
Teorema 1 (Ringeisen) Se um grafo G apresenta mergulhos de 2-células
em superfı́cies de gênero gm e gM , então para todo inteiro g, gm ≤ g ≤ gM ,
G apresenta um mergulho de 2-células em uma superfı́cie de gênero g.
&
19
%
'
Hipótese: Todos os mergulhos são mergulhos de 2-células de Km,n
preservando a caracterı́stica de Euler de Ω.
$
Elementos necessários:
• Um modelo Fmn ≡ Ω (α) = ∪αi=1 Ri gerado pelo mergulho mı́nimo do
grafo Km,n em uma superfı́cie compacta e orientada Ω.
• A cardinalidade do conjunto dos modelos Fmn ,
Mα = {Fmn : Km,n ֒→ Ω(α) and Fmn ≡ Ω(α)}.
é igual ao número de soluções inteiras positivas de
2mn = 4R4 + 6R6 + 8R8 + · · ·
and
∑i≥0 R4+2i = α,
onde Rk denota o número de regiões com k arestas.
O número de regiões associadas a Fmn é constante e depende de χ(Ω).
Disto e do Teorema 1, temos
&
20
%
$
'
Proposição 1 Se Ω ≡ gT (g-toro), então o número de regiões de Fmn é
|Fmn | = 2 − 2g − m − n + mn, ∀ Fmn ∈ Mα .
Definição 1 Uma classe de canal Cm,n é o conjunto consistindo de todos
os canais com m vértices em X e n vértices em Y .
(i) Classe de Canal Cm,n [P, Q] = Cm,n [{p1 , · · · , pm }, {q1 , · · · , qn }];
(ii) Classe de Canal Cm,n [p, q]. Um tipo de canal de decisão suave;
(iii) Classe de Canal Cm [p]. Um tipo de canal de decisão abrupta.
&
21
%
$
'
hΩ (α)i ≡ conjunto de superfı́cies do Cm,n [P, Q] ֒→ Ω (α), isto é,
hΩ (α)i = {Ω (α) ,Ω1 (α − 1), · · · ,Ωα−1 (1)} ,
onde Ωi ( j) denota superfı́cie Ω com j regiões e i discos removidos.
Lema 1 Se Cm [p] ֒→ gm T (α) e Cm [p] ֒→ g̃P (β) são mergulhos mı́nimos, então
o conjunto de superfı́cies para o mergulho de 2-células do canal Cm [p] é
 n
o n
o
(α−2)/2
β−1

∪ h(g̃ + j)P (β − j)i j=0 se α par
h(gm + i) T (α − 2i)ii=0



Sbm,p =

o n
o
n


 h(gm + i) T (α − 2i)i(α−1)/2 ∪ h(g̃ + j)P (β − j)iβ−1 se α ı́mpar.
i=0
j=0
onde as correspondentes superfı́cies são denotadas por T (toro) e P
(plano projetivo).
&
22
%
$
'
Algoritmo para o Mergulho de Canais DMC em Superfı́cies
P1 - Identificar o grafo completo biparticionado Km,n tendo o canal
Cm,n [P, Q] como um subgrafo;
P2 - Determinar gm e gM das superfı́cies para os mergulhos de Km,n
associados ao canal Cm,n [P, Q]. Do Teorema 1, se Km,n ֒→ Ω e Ω têm
gênero g, então gm ≤ g ≤ gM ;
P3 - Para cada g usar a Proposição 1 e identificar um modelo Fmn ֒→ Ω (α);
P4 - Para cada modelo em P3 identificar o conjunto de superfı́cies
geradas por Ω (α), hΩ (α)i, aplicar o Lema 1 para obter o conjunto de
superfı́cies Sbm,n para os mergulhos do canal Cm,n [P, Q];
P5 - identificar em P4 o conjunto das tesselações regulares com m regiões
idênticas.
&
23
%
$
'
Superfı́cies de Riemann como Espaço Quociente para os Mergulhos
• Teorema da Uniformização (Klein, Poincaré, Köbe): Toda superfı́cie
de Riemann simplesmente conexa é conformemente equivalente a
uma das três superfı́cies de Riemann (recobrimento universal):
b = C ∪ {∞} ≡ S2 , esfera de Riemann;
– C
– C ≡ R2 , plano complexo;
– H2 , semi-plano superior.
• Superfı́cie de Riemann ↔ H2 /Γ, onde Γ é um subgrupo de Aut(H2 ). Γ
satisfaz: 1) todo elemento de Γ, exceto a identidade, não tem ponto
fixo em H2 ; 2) Atua propriamente discontinuamente em H2 . Γ é
denominado grupo Fuchsiano.
&
24
%
$
'
Imagem Geométrica de H2 /Γ se dá via domı́nio fundamental para Γ.
Um conjunto aberto F de H2 é um domı́nio fundamental para Γ:
/ ∀T ∈ Γ, T 6= id
• Se T (F) ∩ F = 0,
(é propriamente discontı́nuo);
e
• Se Fe é o fecho de F em H2 , então H2 = ∪T ∈Γ T (F).
ω3
ω4
u2
v´1
v2
ω
ω2
u´1
5
0
ω
v1
u´2
ω6
v´2
u1
ω8
ω7
Figura 12: Domı́nio Fundamental do 2-toro
&
25
%
$
'
Teorema da Classificação de Superfı́cies (com bordos):
Toda superfı́cie compacta e conexa é topologicamente equivalente a
uma esfera, ou a soma conexa de toros, ou a soma conexa de planos
projetivos (com um número finito de discos removidos).
Exemplo 1 Ω = 2T → g = 2,
χ(Ω) = −2
Edges identification
a1
b4
b1
a2
a4
b2
b3
a3
Plane Model
Space Model
Figura 13: 2 Toro
&
26
%
'
Exemplos de Mergulhos e Canais DMC
$
As superfı́cies são denotadas por S (esfera), T (toro), P (plano projetivo)
ou K (garrfa de Klein).
Canal BSC
C2 [2] ≡ K2,2
&
֒→
Sb2,2 = {S (2) , S1 (1) , P (2) , P (1) , P1 (1)} .
Figura 14: Canal C2 [2]
27
%
$
'
Canais Ternários com Valência 3
C3 [3] ≡ K3,3
֒→
Sb3,3 = {hT (3)i , 2T (1) , hP (4)i , hK (3)i , h3P (2)i , 2K (1)} .
Ξ3,3 = {T [3R6 ] P1 [3R4 ] , K [3R6 ]}.
&
Figura 15: Canal C3 [3]
28
%
$
'
Superfı́cies Mı́nimas - Mergulho de Canais em N-nóides
Definição 2 Um canal α-totem é uma torre de α Cm,n [P, Q] canais, com
α ≥ 3.
Figura 16: Canal 3-totem mergulhado em um catenóide
&
Sb3-totem = {S (4) , T (2) , S1 (3) , 2N (2) , S3 (1) , T1 (1)} .
29
%
$
'
Mergulho de Canais em um Toro com 3 Fins Catenóides
A Fig. 17 mostra o mergulho do canal C6 [4] em uma superfı́cie compacta
orientada com g = 1 e com 3 fins catenóides, denotada por T3
C6 [4] ֒→ T3 = 9R4 .
Figura 17: Canal 8-totem mergulhado em T3
&
30
%
'
Ib - Modulação: Conjunto de Sinais GU em Espaços Homogêneos
$
Fato importante:
• códigos 0-tóricos (esféricos), associação de grupos de isometrias
com conjunto de sinais;
• códigos 1-tóricos (reticulados), associação de grupos de isometrias
com conjunto de sinais.
Forney em 1991, com a proposta dos códigos GU inseriu os códigos
esféricos e os códigos reticulados nesta classe.
Desde então intensificou-se a busca por conjunto de sinais associados a
grupos discretos de isometrias em espaços métricos.
Proposta:
• códigos g-tóricos, g ≥ 2, associação de grupos de isometrias com
conjunto de sinais em H2 .
&
31
%
$
'
A maioria dos canais DMC de interesse prático são mergulhados em
superfı́cies com gênero g = 0, 1, 2, 3. Isto motiva a construção
Conjunto de Sinais Casados a Grupos ↔ Conjunto de Sinais GU
• Projetar conjunto de sinais depende fortemente da existência de
tesselações regulares em espaços homogêneos.
• Espaços homogêneos são importantes dada a riqueza de
propriedades algébricas e geométricas, não devidamente
exploradas em Teoria de Comunicações e da Codificação.
• As Propriedades algébricas implicam na implementação sistemática
dos circuitos enquanto que as propriedades geométricas são
relevantes quanto à eficiência dos processos de demodulação e
decodificação.
&
32
%
$
'
• ”Geração Global” de Conjunto de Sinais Hiperbólicos
Definição 3 Tesselação regular em H2 , {p, q}, é uma partição de H2
por polı́gonos regulares com p-arestas sendo que cada vértice é
recoberto por q polı́gonos regulares com p-arestas.
– Euclidiano {p, q} existe se, e só se (p − 2)(q − 2) = 4.
Soluções: {4, 4}; {6, 3}; {3, 6}.
– Hiperbólico {p, q} existe se, e só se (p − 2)(q − 2) > 4.
Soluções: infinitas.
Associado a cada {p, q} está o grupo completo de simetrias [p, q].
Esta é uma isometria de H2 .
O grupo [p, q] é gerado por r1 , r2 e r3 nos lados do triângulo
π π π
hiperbólico com ângulos , , . A presentação de [p, q] é
2 p q
&
[p, q] = r1 , r2 , r3 : r12 = r22 = r32 = (r2 r1 ) p = (r3 r2 )q = (r1 r3 )2 = e .
33
%
$
'
• Tesselação {p, q} −→ grupo [p, q];
• Tesselação Dual {q, p} −→ grupo [q, p];
• Para [p, q] = [q, p], a tesselação é dita auto-dual.
Se p = q = 4g, g ≥ 2, então o grupo completo de simetrias [4g, 4g] de
{4g, 4g} tem um subgrupo normal,
*
+
πg =
g
a1 , ..., ag , b1 , ..., bg : ∏[ai , bi ] = e
(grupo fundamental)
i=1
A região fundamental é um polı́gono com 4g arestas, logo o grupo de
simetrias é D4g . Portanto, [4g, 4g] = πg ⋉ D4g .
&
34
%
$
'
• ”Geração Local” de Conjunto de Sinais: Abordagem Espaço
Quociente
O espaço hiperbólico é relevante pois:
– Qualquer g-toro é localmente isométrico a H2 , pode ser obtido
topologicamente por H2 /Γ, onde Γ é um grupo Fuchsiano.
– Para cada g, a ação de Γ ocorre através da identificação das
arestas de um polı́gono regular com 4g ou 4g + 2 arestas em H2 por
2g ou 2g + 1 isometrias geradoras de Γ.
Estes fatos implicam em uma maneira sistemática de gerar
localmente conjunto de sinais em H2 /Γ.
Como? Através de um subgrupo Fuchsiano G (normal) de Γ.
&
35
%
$
'
Ic - Demodulação: Projeção em Variedades Riemannianas
• Desempenho em Variedade 2-dimensional - K Constante
0
0
10
10
8−PSK K=0
16−PSK K=0
8−PSK K=−1
16−PSK K=−1
K=1
K=0
K=−1
K=−2
−1
10
−1
10
−2
10
−3
10
−2
−4
e
10
P
Pe
10
−3
10
−5
10
−6
10
−4
10
−7
10
−8
10
−6
−4
−2
0
2
4
6
8
10
−5
10
12
Figura 18: Pe × S/N para 4-PSK
com K 1, 0, -1 and -2.
&
−6
−4
−2
0
2
4
6
8
10
12
S/N (dB)
S/N (dB)
Figura 19: Pe × S/N para 8-PSK e
16-PSK com K 0 and -1.
36
%
$
'
• Para Et = (π/2)2 fixa, a Fig. 20 mostra dK /d0 versus M-PSK.
2.6
K=1
K=0
K=−1
K=−3
2.4
2.2
2
1.6
K
d /d
0
1.8
1.4
1.2
1
0.8
0.6
2
4
6
8
10
12
14
16
M−PSK
Figura 20: dK /d0 × M for Et = (π/2)2 .
Conclusão: K1 < K2
&
37
⇒
Pe (K1 ) < Pe (K2 ).
(1)
%
$
'
• Para S/N = 4dB, a Fig. 21 mostra Pe × K (4-PSK and 8-PSK).
0
10
4−PSK
8−PSK
−1
Pe
10
−2
10
−3
10
−5
−4
−3
−2
−1
0
1
Curvature (K)
Figura 21: Pe versus Curvatura Seccional
&
38
%
$
'
1
Códigos Corretores de Erros
1 - Códigos Lineares sobre Corpos Finitos
- Códigos de Bloco Lineares - Espaços Vetoriais
- Códigos Cı́clicos, Códigos Reed-Solomon e BCH
2 - Códigos Lineares sobre Anéis Comutativos com Unidade
- Códigos Cı́clicos e BCH sobre Zq
3 - Códigos Lineraes sobre Corpos de Números
- Códigos sobre Z[i]
- Códigos sobre Z[w]
&
39
%
'
2
Códigos de Bloco Lineares sobre Corpos Finitos
$
2.1 Códigos de bloco lineares oriundos de espaços vetoriais
Espaço Vetorial - (Fnq , +, ·), operação componente-a-componente.
Definição 4 O peso de Hamming, wH (v), de uma palavra-código v é
igual ao número de componentes não nulas de v. O peso mı́nimo w∗ de
um código é o menor peso de qualquer palavra-código.
Teorema 2 A distância mı́nima dmin de um código linear satisfaz
dmin = min {w(v)} =wmin .
v∈C,v6=0
Teorema 3 (Limitante de Singleton) A distância mı́nima (mı́nimo peso) de
um código linear (n, k) satisfaz
&
d ∗ ≤ n − k + 1.
40
%
$
'
Distânicia de Hamming
d(v1 , v2 ) = número de posições onde v1 e v2 diferem
Exemplo 2 A distância de Hamming entre
v1 = (1, 0, 1, 1, 1, 0, 0)
e
v2 = (1, 0, 0, 0, 1, 1, 1)
é igual a d(v1 , v2 ) = 4.
2.2 Descrição matricial
Um código linear C é um subespaço de Fnq . Qualquer conjunto de
vetores formando uma base para o subespaço pode ser usado como as
linhas da matriz G k × n, denominada matriz geradora do código.
&
41
%
$
'



v = uG = (u1 , u2 , · · · , uk ) 

g11
..
.
g12
..
.
···
..
.
g1n
..
.
gk1
gk2
···
gkn





k×n
onde u é uma k-upla de sı́mbolos de informação a serem codificados e
a n-upla v é a correspondente palavra-código.
Exemplo 3
v = uG =
h

1 0 0 1
i
0 1 1 
 0 1 0 0
0 0 1 1
0

 h
1 
= 0 1
1
1 1 0
i
.
(2)
Código Dual
GH T = 0
&
42
%
$
'
2.2.1 Arranjo Padrão ←→ Classes Laterais
0
v2
v3
···
vqk
0 + c1
v2 +c1
v3 +c1
···
vqk +c1
0 + c2
..
.
v2 +c2
..
.
v2 +c2
..
.
···
..
.
vqk +c2
..
.
0 + cj
v2 +c j
v3 +c j
···
vqk +c j
0 + c j+1
..
.
v2 +c j+1
..
.
v3 +c j+1
..
.
···
..
.
vqk +c j+1
..
.
0 + cp
v2 +c p
v3 +c p
···
vqk +c p
Tabela 1: Arranjo padrão
Exemplo 4 Considere o código (5, 2), capaz de corrigir um erro.
&
43
%
'

G=
&
1 0 1
1 1
0 1 1
0 1



1 1 1 0

H =
 1 0 0 1
1 1 0 0
,
2×5
Esfera 1
Esfera 2
Esfera 3
Esfera 4
00000
10111
01101
11010
00001
10110
01100
11011
00010
10101
01111
11000
00100
10011
01001
11110
01000
11111
00101
10010
10000
00111
11101
01010
00011
10100
01110
11001
00110
10001
01011
11100
0


0 

1
Tabela 2: Arranjo padrão para o código (5,2,3)
44
$
.
3×5
%
$
'
Para qualquer sequência recebida v a sı́ndrome de v é definida como
s = v.H T .
Teorema 4 Todos os elementos em uma classe lateral têm a mesma
sı́ndrome, a qual é única para aquela classe lateral.
Para o exemplo anterior, a matriz verificação de paridade é

1

H =
 1
1
1 1 0 0


0 0 1 0 

1 0 0 1
.
3×5
Tabela 2.2.1 mostra o lı́der da classe lateral e a sı́ndrome para este
código.
&
45
%
$
'
Lı́der Classe Lateral
Sı́ndrome
00000
000
00001
001
00010
010
00100
100
01000
101
10000
111
00011
011
00110
110
Note que esta tabela é mais simples que a do arranjo padrão. Assuma
que v =(1, 0, 0, 1, 0) é recebido. Então, v.H T = 101. O lı́der da classe lateral
é 01000. Portanto, a palavra-código transmitida é 10010 − 01000 = 11010, e
o bite de informação é 11.
&
46
%
$
'
2.3 Códigos de Hamming (Códigos Perfeitos)
Parametros do código :

m−1

n
=
2





k = 2m − 1 − m
dmin = 3
Exemplo 5 O código de Hamming (n, k, 3) = (7, 4, 3)

0 0

H =
 0 1
1 0
0 1 1 1 1


1 0

 0 1

G=
 0 0

0 0

1 0 0 1 1 

1 0 1 0 1
3×7
0 0
0 0
1 0
0 1
0 1 1


1 0 1 


1 1 0 

1 1 1
4×7
Lı́deres das Classes Laterais: 0000001, 0000010, ....., 1000000
&
47
%
$
'
2.4 Códigos de Reed-Muller
Defina o produto dos vetores a e b como sendo
a = (a0 , a1 , . . ., an−1 ),
e
b = (b0 , b1 , . . . , bn−1 ),
então
a.b = (a0 b0 , a1 b1 , . . . , an−1 bn−1 ).
A matriz geradora do código de Reed-Muller de r-ésima ordem e com
comprimento 2m é definida como


G
 0 


 G1 

G=
 ..  ,
 . 


Gr
onde G0 é um vetor de comprimento n = 2m contendo somente 1’s; G1 é
uma matriz m × 2m tendo como colunas todas as m-uplas binárias; e G2 [e
construı́da por considerar todos os produtos das linhas de G1 .
&
48
%
$
'
Considere m = 4, n = 24 = 16, e r = 3. Então,
h
G0 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

 0

G1 = 
 0

0
&
0 0 0 0 0
0 0 1 1 1
0 0 0 1 1
1 1 0 0 0
0 1 1 0 0
1 1 0 0 1
1 0 1 0 1
0 1 0 1 0
49
i
1 1
1 1 1 1 1
1×16


0 1 1 1 1 


1 0 0 1 1 

1 0 1 0 1
4×16
= [a0 ]


a1


 a 
 2 
=
.
 a3 


a4
%
$
'

Uma vez que G1 tem 4 linhas, então G2 tem 







G2 = 





&
4
2

 = 6 linhas, isto é,
0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
1
0 0 0 0 0
0 0 0 0 0
1 1 0 0 1
1
0 0 0 0 0
0 0 0 0 1
0 1 0 1 0
1
0 0 0 0 0
0 1 1 0 0
0 0 0 0 1
1
0 0 0 0 0
1 0 1 0 0
0 0 0 1 0
1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1
50














6×16






=





a1 .a2
a1 .a3
a1 .a4
a2 .a3
a2 .a4
a3 .a4







.





%
'

A matriz G3 tem 

0

 0

G3 = 
 0

0
4
3
$

 = 4 linhas,
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 1 1


0 0 1 0 1 


1 0 0 0 1 

0 0 0 0 1
4×16

a1 .a2 .a3

 a .a .a
 1 2 4
=
 a1 .a3 .a4

a2 .a3 .a4




.


Assim, a matriz geradora do código de Reed-Muller de terceira oredem
com comprimento 16 é a matriz 15 × 16 dada por


G0


 G 
 1 
G=
.
 G2 


G3
Esta matriz conduz a um código de verificação de paridade [16, 15, 2]
sobre F2 .
&
51
%
$
'
A partir desta matriz geradora é possı́vel obter um ccódigo de
Reed-Muller de segunda ordem com comprimento 16 por considerar a
matriz geradora


G0



G =  G1 
.
G2
Note que o código resultante é [16, 11, 4] e que este código é o código
de Hamming estendido [15, 11, 4] (foi acrescentado um bit de
paridade). O código de Reed-Muller de primeira ordemcom parametros
[16, 5, 8] pode ser obtido por considerar a seguinte matriz geradora


G0
.
G=
G1
&
52
%
$
'
2.5 Códigos Cı́clicos
Seja
v(x) = v0 + v1 x + · · · + vn−1 xn−1
↔
(v0 , v1 , · · · , vn−1 )
então um deslocamento cı́clico implica em
xv(x)
↔
(vn−1 , v0 , v1 , · · · , vn−2 ).
Códigos cı́clicos estão relacionados com o grupo multiplicativo de Fq ,
onde q = pk .
R∼
=
F2 [x]
n
=
{a(x)
modhx
− 1i} .
hxn − 1i
Seja I(x) um ideal em R gerado por g(x). Note que g(x) divide xn − 1.
Então,
&
Código cı́clico
53
←→
I(x)
%
$
'
Exemplo 6 Construção de um código cı́clico binário (n, k) = (7, 4).
Fatorização:
x7 + 1 = (x + 1)(x3 + x2 + 1)(x3 + x + 1) = g(x)h(x).
Se g(x) = 1 + x2 + x3 é o polinômio gerador do código, então todas as
combinações envolvendo g(x) são também palavras-código, isto é,



g(x)
1 0

 
 xg(x)   0 1

 
G=
=
 x2 g(x)   0 0

 
x3 g(x)
0 0
&
54
1
1
0
0
1
1
1
0
1
0
1
0
0
0


0 0 


1 0 

1 1
4×7
%
$
'
2.6 Códigos Reed-Solomon (RS)
(usados em todos os tipos de dispositivos)
Parâmetros código RS sobre Fq : (n, k) = (q − 1, k).
Os códigos RS são códigos cı́clicos. Assuma que o alfabeto seja F24 .
Então todos os sı́mbolos desse código pertencem ao conjunto
0, 1, α, α2 , · · · , α14 .
Note que cada sı́mbolo pode ser representado por uma 4-upla binária.
Problema 1 Determine um código Reed-Solomon sobre F24 o de
comprimento n = 15, com a maior distância de Hamming possı́vel.
A solução deste problema é equivalente a determinar os fatorers de
x15 − 1.
&
55
%
$
'
1
α, α2 , α4 , α8
α3 , α6 , α12 , α9
α5 , α10
α7 , α14 , α13 , α11
→
x+1
→
x4 + x + 1
→
x2 + x + 1
→
x4 + x3 + x2 + x + 1
→
x4 + x3 + 1
Desta tabela temos a seguinte informação
Expoentes das sequências
dH
1, 2, 3, 4, 5, 6, 7
8
2, 3, 4, 5, 6, 7, 8, 9
9
3, 4, 5, 6, 7, 8, 9
8
6, 7, 8, 9, 10, 11, 12, 13
9
O polinômio gerador é g(x) = ∏7i=1 (x − αi ).
&
56
%
$
'
2.7 Códigos BCH
(usados em Redes de Computadores e em Geração de Sequências de
DNA)
Os códigos BCH são códigos cı́clicos. Assuma que o alfabeto seja F24 .
Como no caso dos códigos RS, todos os sı́mbolos pertencem ao conjunto
0, 1, α, α2 , · · · , α14 .
Novamente, note que todo sı́mbolo em F24 pode ser representado por
uma 4-upla binária.
Problema 2 Determine um código BCH sobre F24 implica em fixar uma
distância de projeto d p , onde d p = número de potências consecutivas do
elemento primitivo α mais 1.
Exemplo 7 Considere a construção do código BCH com distância de
projeto d p = 5. Para isso, temos que α, α2 , α3 , α4 . O próximo passo é
determinar os polinômios minimais de α, α2 , α3 , α4 . Esses polinômios são
&
57
%
$
'
dados por:
α, α2 , α4 , α8
α3 , α6 , α12 , α9
→
→
M1 (x) = x4 + x + 1
M3 (x) = x4 + x3 + x2 + x + 1
O polinômio gerador do código BCH é dado por:
g(x) = mmc {M1 (x), M3 (x)} = x8 + x7 + x6 + x4 + 1
A matriz geradora é dada por:








G=






&
g(x)


 

xg(x) 
 
 

x2 g(x) 
 
 
x3 g(x)  = 
 
 
x4 g(x)  
 

5
x g(x) 
 
x6 g(x)
1
0 0
0
1
0
1 1
1
0
0
0
0
0
0
1 0
0
0
1
0 1
1
1
0
0
0
0
0
0
1
0
0
0
1 0
1
1
1
0
0
0
0
0
0
1
0
0
0 1
0
1
1
1
0
0
0
0
0
0
1
0
0 0
1
0
1
1 1
0
0
0
0
0
0
1
0 0
0
1
0
1 1
1
0
0
0
0
0
0
1 0
0
0
1
0 1
1
58
0


0 


0 


0 


0 

0 

1
7×15
%
$
'
3
Identidade de MacWilliams - Função Enumeradora
Além da distância mı́nima, um código tem uma distribuição de pesos
como um importante invariante. Um resultado interessante é que os
pesos de C são determinados unicamente através dos pesos de C ⊥ e
vice-versa.
Esta transformção se aplica aos códigos não lineares. Neste caso os
polinômios são os polinômios de Krawtchouk.
3.1 Distribuição dos Pesos do Código Dual de um Código Binário
Linear
Se C é um código linear sobre um corpo finito, então o código dual C ⊥
consiste de todos os vetores u tendo produto interno zero com toda
palavra-código de C . Se C tem parâmetros (n, k), então o código dual
tem parâmetros (n, n − k).
&
59
%
$
'
3.2 Distribuição de Pesos
O número de palavras-código com peso i em C é dado pelo polinômio
n
∑ Ai xn−i yi ,
i=0
chamado polinômio enumerador de C e denotado por WC (x, y).
Existem duas formas de escrever o polinômio enumerador:
n
WC (x, y) = ∑ Ai xn−i yi =
i=0
∑ xn−wH (u) ywH (u) .
u∈C
Note que x e y são variáveis independentes e que WC (x, y) é um
polinômio homogêneo com grau n em x e y.
′
Analogamente, Ai denota o número de palavras-código com peso i em
C ⊥ . A função enumeradora de C ⊥ é dada por
n
&
WC ⊥ (x, y) = ∑ Ai xn−i yi =
′
i=0
60
∑
u∈C ⊥
xn−wH (u) ywH (u) .
%
'
Exemplo 8 1) Seja C = {000, 011, 101, 110}. O código dual C ⊥ é
C ⊥ = {000, 111}.
As funções enumeradoras de C e C
WC (x, y) = x3 + 3xy2
⊥
$
são, respectivamente:
and
WC ⊥ (x, y) = x3 + y3 .
2) O código {00, 11} é auto-dual. Assim, WC (x, y) = WC ⊥ (x, y) e então
WC (x, y) = x2 + y2 .
3) O código de Hamming (7,4,3) tem pesos
WC (x, y) = x7 + 7x4 y3 + 7x3 y4 + y7 ,
e
WC ⊥ (x, y) = x7 + 7x3 y4 .
&
61
%
$
'
Teorema 5 (Identidades de MacWilliams para códigos binários) Se C é um
código binário linear (n, k) com código dual C ⊥ , então
WC ⊥ (x, y) =
1
|C |
WC (x + y, x − y),
(3)
onde |C | = 2k é o número de palavras-código em C . Equivalentemente,
n
∑ Ak x
′
n−k k
y =
k=0
1
n
Ai (x + y)n−i (x − y)i ,
∑
|C |
(4)
i=0
ou
∑
u∈C ⊥
&
xn−wH (u) ywH (u) =
1
∑
|C | u∈C ⊥
62
(x + y)n−wH (u) (x − y)wH (u) .
(5)
%
$
'
Exemplo 9 • Seja C = {000, 011, 101, 110} e C ⊥ = {000, 111}. Note que
esses códigos têm parâmetros (3, 2) e (3, 1), respectivamente. Assim,
WC (x, y) = x3 + 3xy2 ,
implica que
1
1
WC (x + y, x − y) = (x + y)3 + 3(x + y)(x − y)2 = x3 + y3 = WC ⊥ (x, y).
4
4
Novamente,
1
1
WC ⊥ (x + y, x − y) = (x + y)3 + (x − y)3 = x3 + 3xy2 = WC (x, y).
2
2
&
63
%
$
'
Note a simetria do teorema com respeito a C e C ⊥ .
• WC (x, y) = x2 + y2 . Então
1
1
WC (x + y, x − y) = (x + y)2 + (x − y)2 = x2 + y2 = WC ⊥ (x, y),
2
2
mostrando a auto-dualidade dos códigos.
Quando o alfabeto do código é q-ário, então a identidade de
MacWilliams é dada por:
Teorema 6 Se C é um código linear q-ário (n, k) cujo dual é C ⊥ , então
WC ⊥ (x, y) =
&
1
|C |
WC (x + (q − 1)y, x − y).
64
%
'
4
Códigos Lineares sobre Anéis Comutativos com
Unidades
$
4.1 Construção de Códigos Cı́clicos sobre GR(4, 3)
Consideraremos um exemplo da extensão de anel de Galois pelo uso do
anel GR(4, 3) dado por
GR(4, 3)[x] =
Z4 [x]
hx3 + x + 1i
= a + bx + cx2 ; a, b, c ∈ Z4 .
Considere o corpo F8 [x], uma extensão de GF(2) por um polinômio
irredutı́vel com grau 3, isto é,
F8 [x] =
&
F2 [x]
′
′
′ 2
′ ′ ′
=
{a
+
b
x
+
c
x
;
a
, b , c ∈ F2 }
hx3 + x + 1i
65
%
'
= {0, 1, x, x2 , 1 + x, 1 + x2 , x + x2 , 1 + x + x2 }
$
Seja α um elemento primitivo em F8 , equivalentemente, α é a raiz de
x3 + x + 1 = 0, isto é, α3 = α + 1. Então, os elementos de F8 são mostrados
na Tabela 3.
0→ 0 0 0
1→ 1 0 0
α→ 0 1 0
2
α → 0 0 1
3
α → 1 1 0
4
α → 0 1 1
5
α → 1 1 1
6
α → 1 0 1
Tabela 3: Elementos de F8
Seja f = (0 1 0) ∈ GR∗ (4, 3), grupo das unidades de GR(4, 3). Então,
&
66
%
$
'
f = R2 ( f ) = (0 1 0) = f gera um subgrupo cı́clico cuja ordem é
n = (2r − 1) = 7 em F8 , onde R2 ( f ) é a redução módulo 2 do elemento f .
Assim, f gera um grupo cuja ordem é nd = 7d em GR∗ (4, 3), onde d ≥ 1 ∈ Z
e f d gera o subgrupo cı́clico Gn de GR∗ (4, 3).
As operações em GR∗ (4, 3) são módulo x3 + x + 1. Então, x3 = −x − 1 = 3x + 3
(coeficientes em Z4 ). Então, considerando f = (0 1 0) = x, os elementos de
GR∗ (4, 3) são mostrados na Tabela 4.
&
67
%
'
0→
1→
f→
f2
f3
f4
f5
→
→
→
→
f6 →
0
1
0 0
0 0
0 1 0
0 0 1
3 3 0
0 3 3
1 1 3
1 2 1
f7
→
f8
→
f9
→
f 10
→
f 11
→
f 12
→
f 13
→
f 14 →
3 0
2
2 1
0
0 2
1
3 3 2
2 1 3
1 3 1
3 0 3
1 0 0
$
Tabela 4: Elementos de GR∗ (4, 3)
Portanto, nd = 14 implicando que d = 2. Assim, f gera um grupo cuja
ordem é 14 em GR∗ (4, 3) e, então f 2 = x2 = (0 0 1) gera um grupo cuja
ordem é 7 em GR∗ (4, 3). Então, β = x2 é um elemento primitivo em G7 .
Construção de um código BCH com comprimento n = 7 sobre Z4 .
Considere a distância de projeto sendo dmin ≥ 3, logo β e β2 são raı́zes.
&
68
%
$
'
Assim, g(x) = mmc (m1 (x), m2 (x)), onde mi (x) é o ´polinômio minimal de βi ,
i = 1, 2.
Os polinômios minimais de β e β2 são dados por
m1 (x) = m2 (x) = (x − β)(x − β2 )(x − β4 ) = 3 + x + 2x2 + x3 .
A correspondente matriz geradora G é dada por


3 1 2 1 0 0 0


 0 3 1 2 1 0 0 


G=

 0 0 3 1 2 1 0 


0 0 0 3 1 2 1
4×7
&
69
%
$
'
5
Códigos Lineares sobre Corpos de Números
5.1 Códigos sobre Z[i] e Códigos sobre Z[w]
√
Considere o anel dos inteiros Z(ρ) de Q( d). O interesse é para os valores
de d que implicam em Domı́nios Euclidianos (DE), isto é,

√

d = −1, −2

 ρ= d
DE =

√


ρ = (1 + d)/2 d = −3, −7, −11
Em todos esses casos o domı́nio euclidiano Z(ρ) é também um domı́nio
de ideal principal (PID), onde os ideais primos são dados por
p = hπi = πZ(ρ) = {πα; α ∈ Z(ρ)},
onde π = a + bρ ∈ Z(ρ) é um primo, e a, b ∈ Z.
&
70
%
$
'
A função N(·) : Z(ρ) → Z, é chamada norma e é definida por

 a2 − da2
if d = −1, −2
1
2
N(z) = zσ(z) = zz̄ =
 a2 + a1 a2 + 1−d a2 if d = −3, −7, −11.
1
Seja p ∈ Z um primo ı́mpar tal que


1







 1, 3
p≡
1




1, 2, 4




 1, 3, 4, 5, 9
4
(mod 4)
(mod 8)
(mod 6)
(mod 7)
(6)
2
if d = −1;
if d = −2;
if d = −3;
(7)
if d = −7;
(mod 11) if d = −11.
Então, se p = π · π̄, temos N(π) = p, e o ideal primo pZ de Z se ramifica
completamente em Z(ρ), i.e., pZ[ρ] = p · p̄, onde p = hπi e p̄ = hπ̄i são ideais
primos distinos. Como p de Z(ρ) são maximais, o quociente Z(ρ)/p é um
corpo com ordem p, denotado por A p [ρ].
&
71
%
$
'
Os elementos 0, 1, . . ., p − 1 formam um conjunto completo de
representativos de p vistos como subgrupos aditivos de Z(ρ). Como
ρ ∈ Z(ρ), segue que ρ pertence a alguma classe lateral s ∈ Z(ρ)/p, onde
0 ≤ s ≤ p − 1. Assim, x + yρ = x + y ρ = x + y s = x + ys = ℓ, ℓ ∈ {0, 1, . . ., p − 1}.
Agora, x + ys = ℓ ⇔ x + ys − ℓ ∈ p ∩ Z = pZ, como x, y, s, ℓ ∈ Z. Portanto,
x + yρ ≡ ℓ (mod p)
⇔
x + ys ≡ ℓ
(mod p),
(8)
Procedimento para Rotular os elementos de A p [ρ] pelos elementos de F p
1. Dado um primo p que ramifica completamente sobre Z(ρ)], seja
π = a + bρ uma solução de N(π) = p;
2. Seja s ∈ Z a única solução (em r) da equação a + br ≡ 0
(mod p), onde 0 ≤ r ≤ p − 1;
3. O elemento ℓ ∈ F p é o rótulo do ponto α = x + yρ ∈ Z(ρ) se x + sy ≡ ℓ
(mod p) e N(α) é mı́nimo.
&
72
%
$
'
Exemplo 10 Considere o caso onde d = −1 e p = 37 ≡ 1 (mod 4).
1. Uma solução de N(α) = a2 + b2 = 37 é (a, b) = (6, 1). Considere π = 6 + i;
2. A única solução de 6 + r ≡ 0 (mod 37), onde 0 ≤ r ≤ 36 é r = 31;
3. O elemento ℓ é o rótulo do ponto α = x + yi ∈ Z[i] se x + 31y ≡ ℓ (mod 37)
e N(α) é mı́nimo.
A representação geométrica do conjunto A37 [i] é mostrada na Fig. 22.
&
73
%
$
'
&
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Figura 22: O conjunto A37 [i] rotulado por F37 , d = −1.
74
%
$
'
Exemplo 11 Considere o caso onde d = −3 e p = 37 ≡ 1 (mod 6).
1. Uma solução de N(α) = a2 + ab + b2 = 37 é (a, b) = (3, 4). Assim,
consideramos π = 3 + 4ω;
2. A única solução da equação 3 + 4r ≡ 0 (mod 37), onde 0 ≤ r ≤ 36 é
r = 27;
3. O elemento ℓ é o rótulo do ponto α = x + yω ∈ Z[ω] se x + 27y ≡ ℓ
(mod 37) e N(α) é mı́nimo.
A representação geométrica do conjunto A37 [ω] é mostrada na Fig. 23.
&
75
%
$
'
4
14
24
34
15
25
35
8
26
9
7
17
27
0
10
20
30
6
16
36
19
&
5
28
1
11
21
31
18
2
12
22
32
29
3
13
23
33
Figura 23: The set A37 [ω] labeled by F37 , d = −3.
76
%
$
'
II - Sistemas de Transmissão de Informação Genética
Problema: Modelagem do Sistema de Informação Biológica
Matriz G
u=sinalizador
Organelas
Núcleo
DNA / mRNA
Ribossomos
mRNA
Retículo
endoplasmático
Sequência de
direcionamento
mRNA
Mitocôndria
.v=mRNA
Sequência de
direcionamento
Proteína
Cloroplasto
Sinais internos
da proteína
.Pv’=proteína
&
Figura 24: Célula eucariótica
77
Citosol
%
$
'
Apresentação
1- Motivação:
• Relevância cientı́fica e tecnológica;
• Aplicações em Biotecnologia (Recombinação de DNA).
– Melhoramento animal;
– Fármacos;
– Agronegócio, etc
2- Pesquisa em Codificação Genômica:
• Utilização de Conceitos de Teoria da Informação e Estatı́stica na
determinação de regiões codantes e não-codantes;
• Caracterização de estruturas topológicas (Teoria dos Nós e Laços) na
recombinação de DNA;
• Caracterização de estruturas algébricas e geométricas de códigos
corretores de erros em seqüências de DNA;
• Modelagem de Sistemas de Transmissão de Informação Biológica como
Network Information Theory and Coding.
&
78
%
$
'
3- Objetivo: Propor um modelo para o sistema de informação biológico
e mostrar que seqüências de DNA são identificadas como
palavras-código de códigos corretores de erros cı́clicos;
4- Dogma Central da Biologia Molecular e da Teoria de Comunicações;
6- Modelos de Sistemas de Transmissão de Informação Biológica;
7- Modelo de Codificação Biológica: Extensão Galoisiana do Anel Z4 ,
GR(4k , r); Rótulos A, B e C;
8- Algoritmo de Identificação de Seqüências de DNA;
9- Resultados: Identificação de seqüências de DNA tais como: exons,
introns, promoter, DNA repetitivo, seqüências de sinalização interna,
seqüências de direcionamento, proteı́nas, genes e genoma
plasmidial.
&
79
%
$
'
CONCEITO
TEORIA DA
INFORMAÇAO
INFORMAÇAO
BIOLOGIA
CODIFICAÇAO
MOLECULAR
COMUNICAÇAO
TRANSMISSOR
CANAL
RECEPTOR
RNA
DNA
TRANSCRIÇAO
PROTEINA
TRADUÇAO
QUAO CONFIAVEL E A INFORMAÇAO CLASSICA ?
QUAO CONFIAVEL E A INFORMAÇAO GENETICA ?
&
80
%
'
Teorema Codificação de Canal (Shannon):
Pe ≤ αe−N(C−R) ,
$
C≥R
onde R = (log M)/N fixo, ∃ código com N → ∞ tal que Pe → 0.
• C - Capacidade de Canal;
• R - Taxa de Transmissão;
• N - Comprimento palavra-código;
• α - constante.
Deste Teorema resulta dois fatos importantes:
• Mensagens longas implicam em aumento da dimensão do espaço e as
esferas têm superfı́cies bem definidas, e isto permite que aconteçam poucos
erros;
• Se essas esferas são empacotadas convenientemente, a taxa de transmissão
pode aumentar até o valor da capacidade de canal, C. Este arranjo de
esferas é chamado Código surgindo então a ”Teoria da Codificação” cujo
objetivo é prover comunicação confiável em canais não confiáveis.
&
81
%
$
'
Teoria da Informação:
• Modelagem Probabilı́stica e Estatı́stica;
• Medidas: entropias (Shannon, Renyi, Tsalis), informação mútua média, etc;
• Limitantes.
Teoria da Codificação:
• Modelagem Algébrica;
• Modelagem Geométrica;
• Modelagem Topológica.
Teoria de Comunicação:
• Modelagem probabilı́stica, estatı́stica, algébrica, geométrica e topológica.
Objetivo:
• da Teoria da Informação fornecer o referencial comparativo;
• da Teoria da Codificação fornecer a estratégia de construção do código
ótimo;
• da Teoria de Comunicação está na realização fı́sica do sistema de
transmissão de informação.
&
82
%
$
'
Áreas de Pesquisa:
• Teoria da Informação em Biologia, em particular, no Mapeamento
Genético;
• Existência de correção de erros no processamento da informação
biológica;
• Teoria da Codificação em Computação Biomolecular;
• Teoria da Codificação em Biologia Molecular Computacional e
Bioinformática.
&
83
%
'
Sob o ponto de vista da Teoria da Codificação:
•
$
L.S. Liebovitch, Y. Tao, A.T. Todorov, and L. Levine, “Is there an error correcting code in the base sequence in DNA?,” Biophysical Journal, vol.
71, pp. 1539-1544, 1996.
•
G.L. Rosen, “Examining coding structure and redundancy in DNA,”IEEE Engineering in Medicine and Biology, vol. 25, pp. 62-68, 2006.
•
D.R. Forsdyke, “Are introns in-series error-detecting sequences?,”J. Theoretical Biol., vol. 93, pp. 861-866, 1981.
•
J. Rzeszowska-Wolny, “Is genetic code error-correcting?,”J. Theoretical Biol., vol. 104, pp. 701-702, 1983.
•
E. May, M. Vouk, D. Bitzer and D. Rosnick, “An error-correcting code framework for genetic sequence analysis,” Journal of the Franklin
Institute, vol. 34, pp. 89-109, 2004.
•
G. Battail, “Information Theory and error correcting codes in genetics and biological evolution,” Introduction to Biosemiotics. Springer: New
York, USA, 2006.
Perguntas:
• Existe um sistema de correção de erros no processamento da
informação biológica?
• Existe uma estrutura matemática nas seqüências de DNA?
&
84
%
$
'
Processo de Geração - Códigos de Bloco (Espaço Vetorial)
• Informação a ser transmitida: u = (u1 , u2 , · · · , uk )
• Matriz Geradora:

• Código Dual:
&



G=



g1
g2
..
.
gk


g
  11
 
  g21
=
  ..
  .
 
gk1
g12
···
g1n
g22
..
.
···
..
.
g2n
..
.
gk2
···
gkn








k×n
GH T = 0
85
%
$
'
Arranjo Padrão - Processo de Decodificação
código
00000
01101
10110
11011
00001
01100
10111
11010
00010
01111
10100
11001
00100
01001
10010
11111
01000
00101
11110
10011
10000
11101
00110
01011
00011
01110
10101
11000
10001
11100
00111
01010
↑
↑
↑
↑
Lı́deres Classes Nuvem
Nuvem
Nuvem
Laterais
&
86
%
'
$
Estrutura dos Ácidos Nucléicos
• RNA - Ácido Ribonucléico
• DNA - Ácido Desoxirribonucléico
BASE
NITROGENADA
FOSFATO
AÇUCAR
HOCH2
OH
H
H
HOCH2
OH
H
H
H
H
H
H
OH
OH
OH
RIBOSE
&
O
AÇUCARES
O
H
DESOXIRRIBOSE
87
%
'
• Estrutura Primária do DNA e RNA: consiste de polı́meros na forma linear
composto por monômeros chamados nucleotı́deos;
$
• Alfabeto DNA= {A,C, T, G}, A,G: purinas; C,T: pirimidinas;
• Alfabeto RNA= {A,C,U, G}, A,G: purinas; C,U: pirimidinas;
• As bases (nucleotı́deos) nos ácidos nucléicos interagem da seguinte forma:
A-T ou A-U e C-G;
BASES PURICAS
NH2
O
C
H
N
C
N
N
C
N
C
C
H
C
H
C
C
H
C
NH2
N
N
N
N
H
GUANINA − G
ADENINA − A
H
BASES PIRIMIDICAS
NH2
O
O
C
C
C
H
N
C H
C
C H
O
&
H
N
C
CH3
C
C
H
O
C
N
C
C
H
O
N
N
N
H
H
H
CITOSINA − C
TIMINA − T
88
H
URACILA − U
%
'
• Transcrição do DNA: resulta em vários tipos de ácidos ribonucléicos:
$
– RNA mensageiro;
– RNA transportador;
– RNA ribossômico,
empregados na sı́ntese de proteı́nas.
ESTRUTURA PRIMARIA
3’
5’
SEQUENCIA DE NUCLEOTIDEOS
ESTRUTURA SECUNDARIA
5’
AMINOACIDO
3’
RNA TRANSPORTADOR
&
RIBOSSOMO
ANTICODON
89
%
'
• Códon: consiste de triplas de nucleotı́deos;
$
• Código Genético: consiste de 64 códons correspondendo a 20 amino
ácidos. Logo, um código degenerado.
&
Amino ácido
Códon
Leu
UUA, UUG, CUU, CUC, CUA, CUG
Arg
CGU, CGC, CGA, CGG, AGA, AGG
Ser
UCU, UCC, UCA, UCG, AGU, AGC
Amino ácido
Códon
Pro
CCU, CCC, CCA, CCG
Ala
GCU, GCC, GCA, GCG
Gly
GGU, GGC, GGA, GGG
Thy
ACU, ACC, ACA, ACG
Val
GUU, GUC, GUA, GUG
90
%
$
'
&
Amino ácido
Códon
lle
AUU, AUC, AUA
Amino ácido
Códon
Phe
UUU, UUC
Tyr
UAU, UAC
Cys
UGU, UGC
His
CAU, CAC
Gln
CAA, CAG
Asn
AAU, AAC
Lys
AAA, AAG
Glu
GAA, GAG
Asp
GAU, GAC
91
%
$
'
&
Amino ácido
Códon
Met
AUG
Trp
UGG
Amino ácido
Códon
Stop
UAA, UAG, UGA
92
%
$
'
Central Dogma of Genetics = Genetic Information Transmission
A
Encode
Channel
Decode
B
&
93
%
$
'
Estágios na Transcrição
• Inı́cio da Transcrição:
– RNA polimerase reconhece e se associa ao local especı́fico
denominado promoter na fita dupla do DNA (3’-5’);
– Polimerase dissolve a fita dupla próxima ao ponto de partida
formando uma bolha de transcrição;
– Polimerase cataliza o processo inicial de transcrição gerando a
fita 5’-3’;
• Elongação: Polimerase avança na direção 3’-5’ dissolvendo a fita
dupla de DNA e adicionando ribonucleotı́deos à fita de RNA;
• Término: ao atingir o ponto stop, polimerase libera o RNA
completado e se dissocia do DNA.
&
94
%
'
&
Tradução
95
$
%
$
'
Tipos de Proteı́nas
Exemplos
Onde são encontrados
Estrutural
Colágeno
ossos, tendões, cartilagens
de defesa
anticorpos
corrente sanguı́nea vertebrados
transportadoras
hemoglobina
corrente sanguı́nea vertebrados
reguladora
hormônio
sangue
de contração
actina
músculos lisos
de armazenamento
ovoalbumina
clara do ovo
Enzimas
ptialina
saliva
&
96
%
$
'
ALA
GLY
LEU
VAL
LYS
ESTRUTURA SECUNDARIA
LYS
ESPIRAL DOBRADA
ESTRUTURA TERCIARIA
GLY
FORMAS GLOBOSAS
HIS
ESTRUTURA PRIMARIA
ESTRUTURA QUATERNARIA
CADEIA POLIPEPTIDICA
&
CADEIA POLIPEPTIDICA
97
%
$
'
Erros Transcrição
DNA normal
DNA normal
ser
trp
arg
ser
leu
DNA normal
trp
arg
leu
ser
trp
arg
leu
TCC
GAG T
AGA
ACC TCC
GAG
T
AGA
ACC
TCC
GAG
T
AGA
ACC
TCT
TGG AGG
CTC
A
TCT
TGG
AGG
CTC
A
TCT
TGG AGG CTC
AGA
GCC
TCC
GAG
T
AGA
CCT
CCG
AGT
C
AGA
GAC
CTC CGA
G
TCT
CGG AGG
CTC
A
TCT
GGA
GGC
TCA
G
TCT
CTG GAG GCT
C
ser
arg
gly
ser
arg
leu
ser
gly
ser
asp
leu
arg
DNA mutante
DNA mutante
DNA mutante
SUBSTITUIÇAO
DELEÇAO DE
INSERÇAO DE
PAR DE BASES
PAR DE BASES
PAR DE BASES
&
98
A
%
$
'
Erros Tradução (”wobble position”)
&
Amino ácido
Códon
Leu
UUA, UUG, CUU, CUC, CUA, CUG
Arg
CGU, CGC, CGA, CGG, AGA, AGG
Ser
UCU, UCC, UCA, UCG, AGU, AGC
Amino ácido
Códon
Pro
CCU, CCC, CCA, CCG
Ala
GCU, GCC, GCA, GCG
Gly
GGU, GGC, GGA, GGG
Thy
ACU, ACC, ACA, ACG
Val
GUU, GUC, GUA, GUG
99
%
$
'
• Modelos de Sistemas de Comunicações para Sı́ntese Protéica:
– Modelo Proposto por Gatlin, 1972
– Modelo Proposto por Yockey, 1992
– Modelo Proposto por May e colaboradores, 2004
– Modelo Proposto, 2008
– Interpretação do Modelo Proposto, 2009
&
100
%
$
'
Modelo Proposto por Gatlin, 1972
Channel
Source
Encoder
Amino Acid
DNA
Transcription
Translation
Sequences
• Erros Transcrição - Substituição, deleção e inserção de nucleotı́deos;
• Erros Tradução - RNA de transferência diferindo na terceira posição
(wobble position).
&
101
%
$
'
Modelo Proposto por Yockey, 1992
Encoder
Genetic
Message
DNA
mRNA
DNA Code
To
mRNA Code
DNA
Transcription
Mutation
Channel
Other Interferences
Translation
Protein Sequence
Encoded Genetic
Message
mRNA
mRNA code
To
Protein Code
Protein
RNA Ribosome
tRNA
&
102
%
$
'
Modelo Proposto por May e Colaboradores, 2004
DNA duplication
DNA
Genetic
Genetic
Genetic
Encoder
Channel
Information
Genetic Decoder
mRNA
Protein
Ending Action
Starting Action
Ribosome
Ribosome
Sequence
Prokaryontes
Shine−Dalgarno Sequence
&
103
%
$
'
Modelo Proposto, 2008
Codigo
Genetico
N={A, C, G, T}
Z4 = {0, 1, 2, 3}
RNAt
Codificador
N
Fonte
Z4
Rotulo
Z4
Codigo
BCH
Z4
N
Sequencia
Rotulo
Ribossomo
Amino acido
Codigo G−Linear
Modulador
&
104
%
$
'
Mapeamento Z4
A C G T A C G T A C G T A C G T A C G T A C G T
0 1 3 2 2 1 3 0 0 1 2 3 2 1 0 3 0 2 1 3 2 0 1 3
A C G T A C G T A C G T A C G T A C G T A C G T
0 3 1 2 2 3 1 0 0 3 2 1 2 3 0 1 0 2 3 1 2 0 3 1
A C G T A C G T A C G T A C G T A C G T A C G T
1 0 2 3 3 0 2 1 1 0 3 2 3 0 1 2 1 3 0 2 3 1 0 2
A C G T A C G T A C G T A C G T A C G T A C G T
1 2 0 3 3 2 0 1 1 2 3 0 3 2 1 0 1 3 2 0 3 1 2 0
}
Rotulamento A
Rotulamento B
A C G T
0 1 3 2
A C G T
2 1 3 0
A C G T
0 1 2 3
A C G T
2 1 0 3
A C G T
0 2 1 3
A C G T
2 0 1 3
A C G T
0 3 1 2
A C G T
2 3 1 0
A C G T
0 3 2 1
A C G T
2 3 0 1
A C G T
0 2 3 1
A C G T
2 0 3 1
A C G T
1 0 2 3
A C G T
3 0 2 1
A C G T
1 0 3 2
A C G T
3 0 1 2
A C G T
1 3 0 2
A C G T
3 1 0 2
A C G T
1 2 0 3
A C G T
3 2 0 1
A C G T
1 2 3 0
A C G T
3 2 1 0
A C G T
1 3 2 0
A C G T
3 1 2 0
Forma Geométrica
Forma Geométrica
1=C
T=2
Forma Geométrica
1=C
0=A
3=G
&
Rotulamento C
Z4
G=2
1=G
0=A
3=T
105
Z2 x Z2
C=2
0=A
3=T
Klein
%
$
'
Descrição do Processo de Transcrição e Tradução via Códigos
Targeting Sequence | I.batatas - Mitochondrial - F1-ATPase delta subunit – GI number 217937
5’–ATG TTC AGG CAC TCT TCT CGA CTC CTA GCT CGC GCC ACC ACA ATG GGG TGG CGT CGC CCC TTC-3’
||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| ||| |||
3’-TAC AAG TCC GTG AGA AGA GCT GAG GAT CGA GCG CGG TGG TGT TAC CCC ACC GCA GCG GGG AAG-5’
Sequence generated by the code:
p(x)= x6+x5+x3+x2+1 – g(x)= x6+3x5+x3+x2+2x+1
032
5’–ATG
|||
3’-TAC
301
331
TTC
|||
AAG
002
331
TTC
|||
AAG
002
022
AGG
|||
TCC
311
101
CAC
|||
GTG
232
313
TCT
|||
AGA
020
313
TCT
|||
AGA
020
120
CGA
|||
GCT
213
130
CTA
|||
GAT
203
213
GCT
|||
CGA
120
121
CGC
|||
GCG
212
211
GCC
|||
CGG
122
011
ACC
|||
TGG
322
010
ACA
|||
TGT
323
032
ATG
|||
TAC
301
222
GGG
|||
CCC
111
322
TGG
|||
ACC
011
123
CGT
|||
GCA
210
121
CGC
|||
GCG
212
111
CCC
|||
GGG
222
331
TTC-3’
|||
AAG-5’
002
Transcription
6
5
3
2
6
5
3
2
mRNA: p05 (x)= x +x +x +x +1 – g05 (x)= x +3x +x +x +2x+1 – Labelling A: (0,1,2,3) – (A,C,G,U)
5’–AUG UUC AGG CAC UCU UCU CGA UUC CUA GCU CGC GCC ACC ACA AUG GGG UGG CGU CGC CCC UUC-3’
032 331 022 101 313 313 120 331 130 213 121 211 011 010 032 222 322 123 121 111 331
Translation (mateched mapping – tRNA e rRNA)
Protein:
M
&
F
R
H
S
S
R
F
L
A
R
106
A
T
T
M
G
W
R
R
P
F
%
$
'
Seqüências de DNA
Organismo
p(x)=polinômio primitivo
Número GI
Célula
g(x)=polinômio gerador
TS
Bn
p(x) = x6 + x5 + x3 + x2 + 1
899225
(EC)
TS
At
186509758
(EC)
TS
Nt
632733
(EC)
g(x) = x6 + 3x5 + x3 + x2 + 2x + 1
TS
Mm
p(x) = x6 + x5 + x4 + x + 1
16740522
(EC)
g(x) = x6 + x5 + x4 + 2x2 + 3x + 1
TS
Pd
51093376
(EC)
P
Ad
45368559
(EC)
P
Ah
207258119
(PC)
P
Ap
32455378
(PC)
g(x) = x6 + 3x5 + x3 + x2 + 2x + 1
p(x) = x6 + x5 + x3 + x2 + 1
g(x) = x6 + 3x5 + x3 + x2 + 2x + 1
p(x) = x6 + x5 + x3 + x2 + 1
p(x) = x6 + x5 + 1
g(x) = x6 + 3x5 + 2x3 + 1
p(x) = x8 + x7 + x5 + x3 + 1
g(x) = x8 + 3x7 + 2x6 + x5 + 3x3 + 1
p(x) = x8 + x6 + x5 + x2 + 1
g(x) = x8 + 2x7 + x6 + x5 + 2x3 + x2 + 2x + 1
p(x) = x10 + x6 + x5 + x3 + x2 + x + 1
g(x) = x10 + 2x8 + 3x6 + x5 + 3x3 + 3x2 + x + 1
Tabela 5: Seqüências de DNA
&
107
%
$
'
Algoritmo de Identificação de Seqüências de DNA
Dados de entrada: 1) seq = seqüência original de DNA em nucleotı́deos (NCBI);
2) n = 2r − 1; e 3) dH = 2t + 1.
• Passo 1 - Gere todos os polinômios primitivos (PP) com grau r para serem
usados nas extensões do anel de Galois e do corpo algébrico de Galois;
• Passo 2 - Selecione um PP de cada vez do Passo 1, e determine o grupo das
unidades de GR(4, r), denotado por GR∗ (4, r);
• Passo 3 - Determine os polinômios gerador e verificação de paridade do
código BCH conhecidos a distância mı́nima e o elemento primitivo derivado
no Passo 2. Como conseqüência, as matrizes geradora e verificação de
paridade bem como suas transpostas são determinadas;
• Passo 4 - Do mapeamento N → Z4 , converter a seq com os elementos de N
na correspondente seqüência com elementos de Z4 ;
&
108
%
$
'
• Passo 5 - Verificar através da sı́ndrome s se cada uma das seqüências de
DNA convertidas é uma palavra-código:
– Se s = 0, então armazene a seqüência;
– Se s 6= 0 implica na existência de até t diferentes nucleotı́deos. Considerar
todas as possibilidades de nucleotı́deos nessas posições. Verificar se cada
uma dessas combinações é uma palavra-código: se for, armazene-a;
caso contrário desconsidere-a;
• Passo 6 - Do mapeamento Z4 → N converter cada seqüência armazenada
no Passo 5 com os elementos de Z4 nas correspondentes seqüências com
elementos de N. Compare cada uma dessas seqüências com a seq e
mostre a posição onde ocorreram as diferenças de nucleotı́deos;
• Passo 7 - Vá ao Passo 1. Selecione um outro PP e verifique se todo PP já foi
utilizado:Se não, repita os Passos de 2 a 5 para cada PP do Passo 1; caso
contrário, vá ao Passo 8;
• Passo 8 - Fim.
&
109
%
$
'
SD01 - B . n ap u s -
Mitochondrial -
Malate dehydrogenase* -
p(x)= x6+x5+x3+x2+1
Fita codante:
-
GI: 899225
g(x)= x6+3x5+x3+x2+2x+1
Rotulamento A: (0,1,3,2) - (A,C,G,T)
Oaa: F
R
S
A
L
V
R
S
S
A
S
A
K
Q
S
L
L
R
R
S
F
Ont: TTC AGA TCC GCG CTT GTC CGA TCC TCC GCC TCG GCG AAG CAG TCG CTT CTC CGC CGC AGC TTC
Olb: 221 030 211 313 122 321 130 211 211 311 213 313 003 103 213 122 121 131 131 031 221
Glb: 221 030 211 313 122 321 130 211 211 311 213 313 003 103 213 122 121 131 131 031 222
Gnt: TTC AGA TCC GCG CTT GTC CGA TCC TCC GCC TCG GCG AAG CAG TCG CTT CTC CGC CGC AGC TTT
Gaa: F
R
S
A
L
V
R
S
S
A
S
A
K
Q
S
L
L
R
R
S
F
Fita complementar:
p(x)’= x6+x4+x3+x+1
-
g(x)’= x6+2x5+x4+x3+3x+1
Rotulamento A: (0,1,3,2) - (A,C,G,T)
Ont: GAA GCT GCG GCG GAG AAG CGA CTG CTT CGC CGA GGC GGA GGA TCG GAC AAG CGC GGA TCT GAA
Olb: 300 312 313 313 303 003 130 123 122 131 130 331 330 330 213 301 003 131 330 212 300
Glb: 000 312 313 313 303 003 130 123 122 131 130 331 330 330 213 301 003 131 330 212 300
Gnt: AAA GCT GCG GCG GAG AAG CGA CTG CTT CGC CGA GGC GGA GGA TCG GAC AAG CGC GGA TCT GAA
&
110
%
$
'
SD02 - I. b atatas – Mitochondrial - F1-ATPase delta subunit – GI: 217937
p(x)= x6+x5+x3+x2+1
Fita codante:
-
g(x)= x6+3x5+x3+x2+2x+1
Rotulamento B: (0,1,2,3) - (A,C,G,T)
Oaa: M
F
R
H
S
S
R
L
L
A
R
A
T
T
M
G
W
R
R
P
F
Ont: ATG TTC AGG CAC TCT TCT CGA CTC CTA GCT CGC GCC ACC ACA ATG GGG TGG CGT CGC CCC TTC
Olb: 032 331 022 101 313 313 120 131 130 213 121 211 011 010 032 222 322 123 121 111 331
Glb: 032 331 022 101 313 313 120 331 130 213 121 211 011 010 032 222 322 123 121 111 331
Gnt: ATG TTC AGG CAC TCT TCT CGA TTC CTA GCT CGC GCC ACC ACA ATG GGG TGG CGT CGC CCC TTC
Gaa: M
F
R
H
S
S
R
F
L
A
R
A
T
T
M
G
W
R
R
P
F
Fita complementar:
p(x)’= x6+x4+x3+x+1
-
g(x)’= x6+2x5+x4+x3+3x+1
Rotulamento B: (0,1,2,3) - (A,C,G,T)
Ont: GAA GGG GCG ACG CCA CCC CAT TGT GGT GGC GCG AGC TAG GAG TCG AGA AGA GTG CCT GAA CAT
Olb: 200 222 212 012 110 111 103 323 223 221 212 021 302 202 312 020 020 232 113 200 103
Glb: 200 222 212 012 110 111 103 323 223 221 212 021 302 200 312 020 020 232 113 200 103
Gnt: GAA GGG GCG ACG CCA CCC CAT TGT GGT GGC GCG AGC TAG GAA TCG AGA AGA GTG CCT GAA CAT
&
111
%
'
Fita Codante
p(x) = x8 + x6 + x5 + x2 + 1
−
g(x) = x8 + 2x7 + x6 + x5 + 2x3 + x2 + 2x + 1 Rótulo A:
(0, 1, 3, 2) = (A,C, G, T )
$
A.hospitalis - plasmid pAH1 – complete sequence – GI number 207258119
&
Oaa:
Ont:
Olb:
Glb:
Gnt:
Gaa:
M
ATG
023
023
ATG
M
S
AGC
031
031
AGC
S
L
TTA
220
220
TTA
L
V
GTT
322
322
GTT
V
Q
CAA
100
100
CAA
Q
L
CTC
121
121
CTC
L
V
GTT
322
322
GTT
V
E
GAA
300
300
GAA
E
K
AAA
000
000
AAA
K
V
GTT
322
322
GTT
V
A
GCG
313
313
GCG
A
K
AAG
003
003
AAG
K
K
AAG
003
003
AAG
K
Y
TAT
202
202
TAT
Y
N
AAT
002
002
AAT
N
I
ATC
021
021
ATC
I
K
AAA
000
000
AAA
K
V
GTA
320
320
GTA
V
N
AAT
002
002
AAT
N
S
TCT
212
212
TCT
S
L
CTC
121
121
CTC
L
Oaa:
Ont:
Olb:
Glb:
Gnt:
Gaa:
P
CCT
112
112
CCT
P
N
AAT
002
002
AAT
N
G
GGT
332
332
GGT
G
V
GTG
323
323
GTG
V
I
ATA
020
020
ATA
I
I
ATT
022
022
ATT
I
L
CTT
122
122
CTT
L
V
GTA
320
320
GTA
V
K
AAA
000
000
AAA
K
N
AAT
002
002
AAT
N
D
GAC
301
301
GAC
D
I
ATA
020
020
ATA
I
G
GGC
331
331
GGC
G
Y
TAT
202
202
TAT
Y
V
GTG
323
323
GTG
V
Q
CAA
100
100
CAA
Q
I
ATA
020
020
ATA
I
A
GCT
312
312
GCT
A
A
GCA
310
310
GCA
A
V
GTT
322
322
GTT
V
R
AGA
030
030
AGA
R
Oaa:
Ont:
Olb:
Glb:
Gnt:
Gaa:
N
AAT
002
002
AAT
N
V
GTT
322
322
GTT
V
Y
TAC
201
201
TAC
Y
Y
TAT
202
202
TAT
Y
V
GTC
321
321
GTC
V
R
AGA
030
030
AGA
R
Y
TAC
201
201
TAC
Y
L
TTA
220
220
TTA
L
T
ACG
013
013
ACG
T
K
AAA
000
000
AAA
K
N
AAT
002
002
AAT
N
E
GAG
303
303
GAG
E
A
GCA
310
310
GCA
A
Y
TAT
202
202
TAT
Y
I
ATT
022
022
ATT
I
I
ATA
020
020
ATA
I
H
CAT
102
102
CAT
H
K
AAA
000
000
AAA
K
L
CTT
122
122
CTT
L
N
AAC
001
001
AAC
N
E
GAA
300
300
GAA
E
Oaa:
Ont:
Olb:
Glb:
Gnt:
Gaa:
E
GAG
303
303
GAG
E
V
GTC
321
321
GTC
V
I
ATA
020
020
ATA
I
E
GAA
300
300
GAA
E
W
TGG
233
233
TGG
W
I
ATT
022
122
CTT
L
L
TTA
220
220
TTA
L
E
GAA
300
300
GAA
E
E
GAA
300
300
GAA
E
K
AAG
003
003
AAG
K
L
TTA
220
220
TTA
L
D
GAT
302
302
GAT
D
E
GAA
300
300
GAA
E
T
ACT
012
012
ACT
T
K
AAA
000
000
AAA
K
A
GCC
311
311
GCC
A
L
CTC
121
121
CTC
L
K
AAA
000
000
AAA
K
I
ATC
021
021
ATC
I
P
CCT
112
112
CCT
P
D
GAT
302
302
GAT
D
Figura 25: Reprodução de Proteı́na
112
V
GTT
322
322
GTT
V
%
$
'
BCH Code over Ring
GR*(4,9) - Labeling 2
GR*(4,11) - Labeling 1
11
10
7
p(x)= x9+x8+x5+x4+1
g(x)=x9 +3x8 +2x7 +2x6 +x5 +x4+2x2 +3
2
p(x)=x +x + x +x +1
g(x)=x11 +3x10 +2x9+x7 +2x6 +2x5 +3x2 +2x+3
L 9 = (113nt)
L 8 = (612nt)
.gene repB
L1 = (715nt)
Lactococcus lactis
plasmid pcl 2.1
Genomic
2047nt
L 7 = (76nt)
RNA
L 2 = (168nt)
Exon - 52nt
.single-stranded
replication origin
Exon - 285nt
511nt
L 3 = (104nt)
L 6 = (138nt)
.gene copG
L 5 = (12nt)
L 4 = (129nt)
.double-stranded
replication origin
Trav7 predicted gene
Plasmidial DNA
&
Intron - 147nt
113
%
$
'
III - Sistemas Quânticos
Information
Theory
Maxwell´s Demon
Cryptography
Statistical
Mechanics
Shannon´s
Computer
(Turing)
Theorems
Complexity
Theory
Data Compression
Error Correcting
Codes
Quantum
Algorithms
Quantum
Error Correction
Quantum
Computer
Entanglement
Quantum
Key Distribution
Bell EPR Pairs
Measurement
Multiple Particle
Decoherence
Interference
Hilbert Space
Schrodinger Equations
Quantum
Mechanics
Figura 26: Teoria da Informação e Mecânica Quântica
&
114
%