-
8/17/2019 00 Ooo - Aplicação Da Teoria Das Matrizes Em
Comunicações
1/4
Aplicação da Teoria das Matrizes em Comunicações
Marinaldo Felipe da Silva1
Manuel Francisco de Lima Andrade2
Raildo Sales de Andrade3
RESUMO
O presente trabalho apresenta uma aplicação das matrizes nas
comunicações. Para tal,
far-se-á um breve histórico dos códigos, dar-se-á as definições
de alfabeto, códigos e
palavras código. Mostrar-se-á a posteriori como tais
códigos estão concatenados com a
teoria das matrizes, dando alguns exemplos de códigos corretores
de erros e suas
respectivas capacidades de detecção e correção.
Palavras-chave: Matriz. Comunicações. Teoria da Codificação.
Introdução
Para fixar idéias, apresenta-se a seguir (Figura 1), um modelo
de um sistema de
comunicações.
Figura 1. Modelo de um Sistema de Comunicações
Em meados do século XX Claude Shannon afirmou (teorema de
codificação de
Shannon, 1948) que através de uma codificação adequada da
informação, erros
introduzidos pelo ruído do canal podem ser reduzidos a qualquer
nível desejado sem
sacrificar a taxa de transmissão da informação.
1 Professor do Departamento de Matemática da Universidade
Federal de Rondônia – UNIR. Doutor em
Engenharia Elétrica pela Universidade Estadual de Campinas
– UNICAMP - Brasil. E-mail:
[email protected] Acadêmico do curso de Matemática
de universidade Federal de Rondônia – UNIR.
3 Acadêmico do curso de Matemática de universidade Federal
de Rondônia – UNIR.
-
8/17/2019 00 Ooo - Aplicação Da Teoria Das Matrizes Em
Comunicações
2/4
O que é codificação? Codificar é uma forma de mapear, ou seja, é
uma conversão de
uma sequencia de símbolos ou bits (dígitos binários) em outra
sequencia de símbolos ou
bits. A Figura 2 mostra um modelo simplificado de um
codificador.
Figura 2: Modelo simplificado um Codificador
Para os propósitos deste trabalho, isto é, uma aplicação das
matrizes em comunicações,
apresentar-se-á a seguir, uma breve introdução aos Códigos
Corretores de Erros e, em
particular, os Códigos de Blocos Lineares.
DesenvolvimentoUm alfabeto é um conjunto finito. Aqui, nosso
alfabeto é o conjunto de dígitos binários
{0,1}, ou seja, todas as palavras serão compostas por letras
deste alfabeto. Um código C de comprimento n sobre {0,1} é um
subconjunto de {0,1}n. Assim, 01010101 é uma
palavra de comprimento 8. Se tal palavra pertencer a algum
código, chamar-se-á uma
palavra código.
Código de Bloco: Características
1. O codificador divide a sequência de informação em
blocos de k bits4 cada.2.
Um bloco é representado por uma k
– upla de bits u = (u0, u1, ... , uk-1)
chamadamensagem. Segue-se que existem 2k mensagens distintas.
3. O codificador transforma cada mensagem u em uma n
– upla v = (v0,v1,... , vn-1)de bits chamada
palavra – código.
4. Esse conjunto de 2k palavras-código
chamar-se-á código de bloco e será aquirepresentado por C = (n,
k).
Um código de bloco é dito ser um código de bloco linear se
e somente se suas 2k
palavras código formarem um subespaço vetorial de {0,1}n,
munido das operações soma
e produto assim definidas.
0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 e 1 + 1 = 0.0.0 = 0, 0.1 =
1, 1.0 = 1 e 1.1 = 1.
Dada uma informação u = (u0, u1, ... , uk-1) a ser
codificada, a palavra código v = (v0, v1,... , vk-1)
correspondente é obtida pela ação de uma Matriz G, como segue:
v = u.Gonde G é uma matriz k x n cujas linhas são compostas por
k palavras-código
linearmente independentes.
Tal matriz é chamada matriz geradora do código C = C(n , k).
4 Bit é a uma abreviatura para Binary digIT
-
8/17/2019 00 Ooo - Aplicação Da Teoria Das Matrizes Em
Comunicações
3/4
Um código de bloco binário é linear se a soma módulo 2 a priori
definida de duas
palavras-código for ainda uma palavra-código.
Na transmissão de informações, uma dada palavra recebida
pode conter erros. Uma
forma de identificar a palavra mais próxima (verossimilhante) de
uma palavra recebida
com erro e detectar a palavra-código transmitida é mensurar a
distância entre as
palavras de {0,1}n.
A distância de Hamming entre duas palavras-código v1 e
v2 é o número de bitsdistintos. Por exemplo: d [(0, 1, 1, 1),
(1, 1, 1, 0)] = 2 e d [(1, 1, 1), (0, 0, 0)] = 3.
A distância mínima (dmin) de um código dado C é min
{d(u,v): u,v C}. A capacidadede detectar e corrigir erros de
um código é função da distância mínima.
Se C é um código e dmin a sua distância mínima, então C
pode detectar dmin -1 erros e
corrigir até x erros, onde
x = dmin −1
2
Por exemplo, o código C = {(0, 0, 0, 0, 0), (0, 1, 0, 1, 1), (1,
0, 1, 1, 0), (1, 1, 1, 0, 1)
{0,1}5, tem dmin (C) = 3. Portanto, detecta d
– 1 = 3 – 1 = 2 erros e corriged
− 1
2 =
3 − 12
= 1 erro.
Para este estudo é de grande potencialidade transformar uma dada
matriz na forma de
Echelon, ou seja, particiona-la em duas submatrizes, a saber: G
=(I : P), onde I é uma
sub-matriz identidade e P é chamada submatriz de paridade.
Exemplo 1. O código C é gerado pela matriz =
11111111110100
01011100110100 chama-se código (7,4)
não-sistemático, cujas palavras-código são todas as combinações
lineares das linhas de
G. Note que a informação tem comprimento 4 e a palavras-código
correspondente tem
comprimento 7. Assim se u = 1111, então v = 0010001 é a
palavra-código
correspondente. Escrevendo a matriz G na forma = [ ⋮
] Obtida por combinações lineares entre as linhas de G,
tem-se;
= 1000 ⋮ 1100100 ⋮ 0110010 ⋮ 1110001 ⋮ 101
Onde I = I4x4 e P =110011111
101
. Tal matriz G desta forma gera um código (7,4) conhecidocomo
código sistemático. A vantagem de se escrever a da matriz G desta
forma é que a
mesma nos fornece uma matriz H = [Pt
⋮ n-k ] que nos diz se uma palavra recebida é uma
palavra código ou não, da seguinte forma: uma n-upla v é
uma palavra código gerada por G se e somente se H.vt =
0.
-
8/17/2019 00 Ooo - Aplicação Da Teoria Das Matrizes Em
Comunicações
4/4
Exemplo 2: Seja C = {(00000), (11101), (01011), (10110)} o
código gerado pela matriz
G=1011001011
. Daí, segue-se que, P = 110011
, portanto H= 101001101001001
.Suponha que a palavra recebida foi v = 11111. Segue-se que:
H.vt = 101001101001001
1
111
1 =
010 ≠ 0. Ou seja, a palavra recebida contém erros. Suponha
que a ocorrência de erro
tenha probabilidade p=0,1, logo 1-p = 0,9 então;
A probabilidade (v, 00000) = 0,15= 0,00001
A probabilidade (v, 11101) = 0.1 x 0,94=0,06561
A probabilidade (v, 01011) = 0.12 x 0,93 = 0,00729
A probabilidade (v, 10110) = 0.12 x 0,93 =
0,00729.
Portanto, a palavra recebida é decodificada como 11101.
Conclusão
Este trabalho apresentou uma aplicação da teoria das matrizes em
comunicações, a
saber: os códigos corretores de erros. Para tal, foram
definidos; alfabeto, códigos e sua
respectiva matriz geradora, a qual está associada a uma matriz
de paridade que tem a
potencialidade de verificar se uma mensagem recebida está
correta ou não. Foi ainda
estudada a distância de Hamming que dá uma modelagem matemática
para a detecção e
correção de erros e como tais erros podem ser corrigidos a
partir de sua probabilidade
de ocorrência.
REFERÊNCIAS
Da Silva, M.F., Codificação de Geodésicas fechadas Simples
em superfíciesHiperbólicas. Tese de Doutorado, FEE, UNICAMP,
2002.
Hefez, A. Introdução á Teoria dos Códigos. UNICAMP,
2004.
Hefez, A e Villela, M.L.T., Códigos Corretores de Erros. 2. Ed.
IMPA, Rio de Janeiro,
2008.
Lins S. and Costello Jr.D. J., Error Control Coding:
Fundamentals and applications,
Prentice-Hall, 1983.
