Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Matemática Discreta Aula nº 16 Francisco Restivo 2006-04-28 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. 2 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). 3 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. 4 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. 5 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| Permutações e combinações: Na contagem das permutações, a ordem é importante, enquanto que na contagem das combinações, não. 10 Permutações: Escolher r objectos sem repetição de n objectos diferentes, sabendo que a ordem conta: P(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 permutações: P(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. 6 11 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.
Compartilhar