Slides 14 0607

Prévia do material em texto

Matemática Discreta
Aula nº 14
Francisco Restivo
2007-04-26
2
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.
3
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.
4
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). 
5
Teorema:
Seja G for uma matriz geradora m×n tal que G = (Im F) onde F é
uma matriz m×r e m = n – r. Seja E uma função de codificação
E: Bm→ Bn definida por E(x) = xG. Então, para qualquer palavra
codificada w ∈ Bn
HwT = 0r×1 (síndrome)
onde H = (FT Ir).
Demonstração:
1r
T
mr
TT
2
TT
T
m
r
T
TTTTT
0x0
)xF(Fx
F
I
)I(F
)x(HG)xH(GH(xG)
×× ==
+=⎟⎠
⎞⎜⎝
⎛=
==
Também se pode demonstrar a proposição conversa.
6
Teorema:
Seja E uma função de codificação E: Bm→ Bn definida por
E(x) = xG, em que G é uma matriz geradora. Então, o conjunto de 
palavras codificadas E(Bm) é um grupo com a adição módulo 2, bit 
a bit.
Demonstração:
Pode verificar-se facilmente que E é um morfismo de (Bm, ⊕) para 
(Bn, ⊕), e que a primeira estrutura é um grupo
E(x1 ⊕ x2) = (x1 ⊕ x2)G = x1G ⊕ x2G = E(x1) ⊕ E(x2)
Se o síndrome de uma palavra recebida HwT tem todos os 
elementos nulos, então é razoável concluir que não tenha havido 
erro de transmissão.
E o que acontece se o síndrome tem um ou mais valores não 
nulos? Há então uma diferença entre a palavra transmitida wt e a 
palavra recebida wr.
7
Definição:
O padrão do erro é uma palavra binária e em que o dígito i vale 0 
se os dígitos i das palavras transmitida e recebida forem os 
mesmos e vale 1 se forem diferentes. Assim
wr = wi ⊕ e
Se houver um único dígito i errado:
H de i colunaHeHeHw
)eH(we)H(wHw
TTT
t
TT
t
T
t
T
r
==⊕=
⊕=⊕=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
0
1
1
1
0
0
0
0
1
100101
010111
001011
HwT
Qual é a palavra mais provável?
110001. Porquê?
8
Não vamos estudar o capítulo sobre Álgebra de Boole:
Álgebra de Boole. 
Operações, propriedades. 
Funções booleanas. 
Mintermos e maxtermos. 
Simplificações de funções booleanas. 
Códigos de Gray e quadros de Karnaugh.
9
Técnicas de contagem:
Princípio da adição: 
Em geral
|A ∪ B| = |A| + |B| - |A ∩ B|
e no caso de os conjuntos A e B serem disjuntos
|A ∪ B| = |A| + |B|
Princípio da multiplicação:
|A × B| = |A| . |B|
Arranjos, permutações e combinações:
Na contagem dos arranjos e das permutações, a ordem é
importante, enquanto que na contagem das combinações, não.
10
Arranjos:
Escolher r objectos, sem repetição, de n objectos diferentes, 
sabendo que a ordem conta:
A(n, r) = n! / (n – r)!
Exemplo:
De quantas formas diferentes posso escolher o presidente, o vice-
presidente e o secretário de uma lista de 7 pessoas?
Trata-se de arranjos:
A(7, 3) = 7! / 4! = 210
Poder-se-ia ter usado o princípio da multiplicação: o presidente 
pode ser escolhido de um conjunto de 7 pessoas, o vice-
presidente de um conjunto de 6 e o secretário de um conjunto de 
5, havendo no total 7×6×5 = 210 possibilidades.
11
Permutações:
De quantas formas podem ser ordenados n objectos diferentes:
P(n) = A(n, n) = n! / (n – n)! = n!
Exemplo:
De quantas formas diferentes posso arrumar 7 livros numa 
estante?
Trata-se de permutações:
P(7) = 7! = 4940
Poder-se-ia também ter usado o princípio da multiplicação: o 
primeiro livro pode ser escolhido entre 7, o segundo entre 6, o 
terceiro entre 5, e assim sucessivamente até ao último: 
7×6×5×4×3×2×1 = 4940.
12
Combinações:
Escolher r objectos sem repetição de n objectos diferentes, 
sabendo que a ordem não conta:
C(n, r) = n! / (r! (n – r)!)
Exemplo:
De quantas formas diferentes posso escolher um comité de 3 
pessoas de uma lista de 7 pessoas?
Trata-se de combinações, pois agora a ordem é indiferente:
C(7, 3) = 7! / (3!×4!) = 35
Para pensar:
De um conjunto de 7 pessoas {A, B, C, D, E, F, G}, quantos 
comités de 3 pessoas posso formar sabendo que: a) B tem de 
fazer parte do comité b) D não pode fazer parte c) C e E não 
podem ser escolhidos simultaneamente. Respostas: 15, 20, 30.
	Matemática Discreta