Slides 15

Prévia do material em texto

1
Matemática Discreta
Aula nº 15
Francisco Restivo
2006-04-27
2
Grupos diedral de ordem 3:
1
2 3
1
2 3
3
1 2
2
3 1
3
2 1
2
1 3
1
3 2
r0
r1
r2
m1
m2
m3
r0r1r2m1m2m3m3
r2r0r1m3m1m2m2
r1r2r0m2m3m1m1
m2m1m3r1r0r2r2
m1m3m2r0r2r1r1
m3m2m1r2r1r0r0
m3m2m1r2r1r0*
1
2 3
1
3 2
3
2 1
m1 * r2 = m2
Grupo diedral de ordem 3:
2
3
Grupo (de permutações) simétrico de ordem 3:
1234566
3126455
2315644
5462133
4651322
6543211
654321
ppppppp
ppppppp
ppppppp
ppppppp
ppppppp
ppppppp
pppppp
Estes dois grupos são isomorfos. São idênticos, excepto no que 
respeita aos nomes usados.
Um isomorfismo do grupo (G, *) para o grupo (G’, °) é uma função 
bijectiva f: G ® G’ tal que
f(g1 * g2) = f(g1) ° f(g2)
4
Um morfismo da estrutura algébrica (A, *) para a estrutura 
algébrica (B, °) é uma função f: A ® B tal que
f(a1 * a2) = f(a1) ° f(a2)
Um morfismo não tem de ser sobrejectivo: pode haver elementos 
de B que não são imagem de um elemento de A. Se o for, diz-se 
um epimorfismo.
Um morfismo também não tem de ser injectivo: pode haver 
elementos de B que são imagem de mais que um elemento de A. 
Se o for, diz-se um monomorfismo.
Um isomorfismo é um morfismo sobrejectivo e injectivo.
Exemplo:
Sejam os grupos (Z, +) e ({[0], [1]}, +2}.
A função f: Z ® {[0], [1]} tal que f(x) = [0] se x é par e f(x) = [1] se x 
é ímpar define um morfismo de (Z, +) em ({[0], [1]}, +2}.
3
5
Grupos de código:
Em comunicações, é frequente os dados serem palavras binárias, 
sendo cada dígito um bit.
Os erros de transmissão causam falhas nas comunicações. É
contudo possível desenhar códigos que reduzam a probabilidade 
de ocorrência desses erros. À custa de redundância, naturalmente.
Cenário:
- Os erros traduzem-se na conversão de 1 em 0 ou de 0 em 1, em 
um ou mais bits da palavra transmitida,
- Estes dois erros são igualmente prováveis,
- Erros são independentes,
- Erros ocorrem em qualquer bit com igual probabilidade,
- Se n < m, então a ocorrência de n erros numa transmissão é
mais provável que a ocorrência de m erros.
6
Se, por exemplo, o conjunto das palavras a transmitir for o 
conjunto B3 das palavras binárias de comprimento 3
B3 = {000, 001, 010, 011, 100, 101, 110, 111}
não há qualquer possibilidade de se detectar, e muito menos 
corrigir, a ocorrência de um erro.
Mas se restringirmos o conjunto das palavras a transmitir, por 
exemplo, às palavras com um número ímpar de 1
{001, 010, 100, 111}
um erro simples passa a ser detectado: há um número par de 1.
Se restringirmos o conjunto das palavras a transmitir a duas
{000, 111}
é possível detectar até dois erros simples e corrigir um erro 
simples. Mas não distinguimos um erro simples de dois: 010 e 
010.
4
7
Definição:
Define-se distância (ou distância de Hamming) d(x, y) entre duas 
palavras binárias x e y de comprimento n como o número de 
dígitos em que x e y diferem.
Propriedades:
1) d(x, y) ³ 0
2) d(x, y) = 0 se e só se x = y
3) d(x, y) = d(y, x)
4) d(x, z) £ d(x, y) + d(y, z)
Na prática, a detecção e correcção de erros faz-se codificando as 
palavras antes da transmissão. Vamos considerar o caso em que 
essa codificação se faz acrescentando bits de verificação aos bits 
de informação de cada palavra a transmitir. Chama-se a esta 
codificação sistemática.
8
A função de codificação é uma função E: Bm ® Bn, e os elementos 
da sua imagem são as palavras codificadas. Bn representa o 
conjunto de todas as palavras binárias de comprimento n.
A função E tem de ser injectiva.
A cada função de codificação corresponde uma função de 
descodificação D: Bn ® Bm È {‘erro’}.
Uma vez que m < n, o conjunto das palavras codificadas é um 
subconjunto próprio de Bn. Se uma palavra recebida w’ não é uma 
das palavras codificadas, e se houver uma palavra codificada w 
mais próxima de w’, pode fazer-se D(w’) = D (w) (descodificação 
pelo vizinho mais próximo).
Ao conjunto das funções E e D chama-se código em bloco (m, n).
O procedimento de codificação mais simples é o chamado bit de 
paridade: acrescenta-se um bit de tal modo que o número total de 
1 seja par. Trata-se de um código em bloco (m, m+1) sistemático.
5
9
Teoremas:
Um código detecta k erros se e só se a distância mínima (entre 
palavras codificadas) for pelo menos k + 1.
Um código corrige k erros se e só se a distância mínima for pelo 
menos 2k + 1.
Exemplo:
Quantos erros pode detectar e corrigir a função de codificação 
E: B2 ® B6 assim definida:
E(00) = 001000 E(01) = 010100
E(10) = 100010 E(11) = 110111.
Resposta: pode detectar dois erros e corrigir um erro.
Definição:
Na soma de duas palavras de código x e y de comprimento n, 
x Å y, o bit i vale xi +2 yi. Exemplo: 1011001 Å 1000111 = 0011110.
10
Definição:
O peso de uma palavra de código x, w(x), é o número de 1 que 
contem.
A distância entre duas palavras de código de n bits é dada por 
d(x, y) = w(x Å y).
Definição:
Um código para o qual o conjunto das palavras do código, com a 
operação Å, forma um grupo, é um grupo de código.
Exemplo:
O conjunto de todas as palavras binárias de comprimento n, com 
a operação Å constitui um grupo de código, embora pouco 
interessante por a sua distância mínima ser 1.
6
11
Teorema:
A distância mínima num grupo de código é o peso mínimo de 
todas as palavras codificadas não zero.
Existe uma palavra z com peso mínimo n: "x, w(x) > w(z)=n.
Se d for a distância mínima, há pelo menos duas palavras de 
código v e w tais que w(v Å w) = d.
Como v Å w é uma palavra do código, w(v Å w) ³ n, i.e., d ³ n.
Por outro lado, a palavra 0, palavra em que todos os bits são 0, 
será o elemento identidade (0 Å x = x Å 0 = x) e pertence ao grupo 
de código. Como
d(0, z) ³ d, 
e por outro lado d(0, z) = w(z) = n, donde
n ³ d.
Em conclusão, n = d.
12
Matrix geradora e matriz verificadora:
[ ] [ ] [ ]011101
110100
011010
101001
011011E
110100
011010
101001
G
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
0
0
0
Hw
100101
010110
001011
H
T (Síndrome de w)
G é a matriz particionada (I3 F) e H é a matriz particionada (FT I3).