Embed Size (px)
Citation preview
INSTITUTO MILITAR DE ENGENHARIA
MAJ MARCUS VINÍCIUS DOS SANTOS FERNANDES
MODELAGEM DE ERROS EM SURTOS EM SISTEMAS DE
COMUNICAÇÕES
Dissertação de Mestrado apresentada ao Curso de Mestrado em Engenharia Elétrica do Instituto Militar de Engenharia, como requisito Parcial para obtenção do título de Mestre em Ciências em Engenharia Elétrica. Orientador: Prof. Ernesto Leite Pinto – D.C. Co-orientador: Marco Antônio Grivet M. Maia – Ph.D.
Rio de Janeiro
2002
2
c2002
INSTITUTO MILITAR DE ENGENHARIA
Praça General Tibúrcio, 80 – Praia Vermelha
Rio de Janeiro – RJ CEP: 22290-270
Este exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-
lo em base de dados, armazenar em computador, microfilmar ou adotar qualquer
forma de arquivamento.
É permitida a menção, reprodução parcial ou integral e a transmissão entre
bibliotecas deste trabalho, sem modificação de seu texto, em qualquer meio que
esteja ou venha a ser fixado, para pesquisa acadêmica, comentários e citações,
desde que sem finalidade comercial e que seja feita a referência bibliográfica
completa.
Os conceitos expressos neste trabalho são de responsabilidade do autor e dos
orientadores.
F363 Fernandes, Marcus Vinícius dos Santos. Modelagem de erros em surtos em sistemas de comunicações / Marcus Vinícius dos Santos Fernandes. – Rio de Janeiro : Instituto Militar de Engenharia, 2002. 88 p. : il., graf., tab. Dissertação (mestrado) – Instituto Militar de Engenharia - Rio de Janeiro, 2002. 1. Modelagem de erros em surtos. I. Instituto Militar de Engenharia. II. Título. CDD 621.3822
3
INSTITUTO MILITAR DE ENGENHARIA
MAJ MARCUS VINÍCIUS DOS SANTOS FERNANDES
MODELAGEM DE ERROS EM SURTOS EM SISTEMAS DE
COMUNICAÇÕES
Dissertação de Mestrado apresentada ao Curso de Mestrado em Engenharia Elétrica do Instituto Militar de Engenharia, como requisito parcial para a obtenção do título de Mestre em Ciências em Engenharia Elétrica.
Orientador: Prof. Ernesto Leite Pinto – D.C. Co-orientador: Marco Antonio Grivet Mattoso Maia – Ph.D.
Aprovada em 10 de maio de 2002 pela seguinte Banca Examinadora:
_______________________________________________________________ Prof. Ernesto Leite Pinto – D.C. do IME – Presidente
_______________________________________________________________ Prof. Marco Antonio Grivet Mattoso Maia – Ph.D. da PUC-Rio _______________________________________________________________ Prof. Pedro Henrique Gouvêa Coelho – Ph.D. da UERJ _______________________________________________________________ Prof. Francisco Marcos de Assis – D.C. da UFPB _______________________________________________________________ Prof. João Célio Barros Brandão – M.C. da PUC-Rio
Rio de Janeiro
2002
4
Aos meus pais Walter Fernandes e Maria Bernadete, à minha
esposa Maria Inês e à minha filha Marina Letícia.
5
AGRADECIMENTOS
Agradeço a todos que me apoiaram e incentivaram a vencer esta importante
etapa da minha carreira profissional.
À minha esposa e aos meus pais que sempre me encorajaram a superar as
dificuldades encontradas e seguir em busca do objetivo.
Aos professores e funcionários do Departamento de Engenharia Elétrica do IME
que de algum modo contribuíram para minha formação.
Em especial ao meu Professor Orientador Dr. Ernesto Leite Pinto e ao meu
Professor Co-orientador Dr. Marco Antonio Grivet Mattoso Maia, pela dedicação e
atenção que prestaram para a ampliação de meus conhecimentos e para a
realização deste trabalho.
6
SUMÁRIO
LISTA DE ILUSTRAÇÕES ................................................................................... 09
LISTA DE TABELAS ............................................................................................ 12
LISTA DE ABREVIATURAS E SÍMBOLOS ......................................................... 13
LISTA DE SIGLAS ............................................................................................... 15
1 INTRODUÇÃO ................................................................................ 18
1.1 Posicionamento do Trabalho ............................................................ 18
1.2 Finalidade do Trabalho ..................................................................... 19
1.3 Organização do Trabalho ................................................................. 20
2 CONCEITOS BÁSICOS ................................................................... 21
2.1. Erros em Surtos ................................................................................ 21
2.2 Modelos de Markov Escondido (HMM) ............................................. 22
2.2.1 Definição ........................................................................................... 22
2.2.2 Considerações .................................................................................. 23
2.2.2.1 Propriedade de Markov .................................................................... 23
2.2.2.2 Estacionariedade .............................................................................. 23
2.2.2.3 Seqüência de Observações .............................................................. 23
2.2.2.4 Independência da Saída ................................................................... 24
2.2.3 Parâmetros ....................................................................................... 24
2.2.4 Modelo de Gilbert- Elliott .................................................................. 25
2.2.5 Modelo de Fritchman ........................................................................ 27
2.2.6 Os Três Problemas Básicos Relativos a HMM ................................. 28
2.2.6.1 Cálculo da Função Verossimilhança ................................................ 29
2.2.6.1.1 Variável Progressiva ......................................................................... 29
2.2.6.1.2 Variável Regressiva .......................................................................... 30
2.2.6.2 Seqüência de Estados ...................................................................... 31
2.2.6.3 Estimação de Parâmetros ................................................................ 32
2.2.6.3.1 Critério da Máxima Verossimilhança (ML) ........................................ 32
7
2.2.6.3.2 Algoritmo de Baum-Welch ................................................................ 33
2.2.6.3.3 Problemas de Implementação .......................................................... 35
2.2.6.3.4 Ordem de Grandeza ......................................................................... 35
2.2.6.3.5 Seqüência de Observações Insuficiente .......................................... 36
2.2.6.3.6 Estimação Inicial dos Parâmetros .................................................... 37
2.2.6.3.7 Implementação ................................................................................. 37
3 MODELO DE MARKOV PROPOSTO .............................................. 41
3.1 Definições ......................................................................................... 42
3.1.1 Número de Estados .......................................................................... 43
3.1.2 Modelo Básico .................................................................................. 43
3.1.3 Tabela de Transição de Estados do Modelo Derivado ..................... 45
3.1.4 Matriz de Probabilidades de Transição ............................................ 45
3.1.5 Diagrama de Estados ....................................................................... 48
3.2
Cálculo das Distribuições de Probabilidades dos Parâmetros
Comprimento de Surto e Intervalo entre Surtos ...............................
49
3.2.1 Comprimento de surto ..................................................................... 49
3.2.2 Intervalo entre Surtos ....................................................................... 50
3.2.3 Cálculo Recursivo das Probabilidades P[C(k,l)] e P[I(k,l)] ................ 50
3.2.3.1 Probabilidade de Comprimento de Surto .......................................... 53
3.2.3.2 Probabilidade de Comprimento de Intervalo entre Surtos ................ 53
4 RESULTADOS ................................................................................. 55
4.1 Simulação ......................................................................................... 55
4.1.1 Levantamento do Parâmetro Comprimento de Surto ....................... 55
4.1.2 Levantamento do Parâmetro Intervalo entre Surtos ......................... 57
4.1.3 Densidade de Erro por surto ............................................................. 59
4.2 Modelo Derivado ............................................................................... 60
4.2.1 Distribuição Calculada dos Comprimentos de Surtos ...................... 60
4.2.1.1 Variação da Inclinação da Curva de Distribuição com L .................. 63
4.2.2 Comportamento Inicial da Distribuição dos Comprimentos .............. 64
4.2.3 Distribuição Calculada dos Intervalos entre Surtos .......................... 67
4.3 Comparação entre Simulação e Modelo Proposto ........................... 68
8
4.3.1 Comparação entre os Tempos de Processamento .......................... 71
4.4 Modelo Básico HMM de 3 Estados ................................................... 72
4.5 Modelo Básico de Fritchman-SES de 3 Estados .............................. 74
4.6 Modelagem de um Canal Simulado de HF ....................................... 79
4.6.1 Modelagem pelo Modelo de Gilbert-Elliott ........................................ 80
4.6.2 Estimação de Parâmetros pelo Modelo Derivado ............................ 82
5 CONCLUSÃO ................................................................................... 84
6 REFERÊNCIAS BIBLIOGRÁFICAS ................................................ 87
9
LISTA DE ILUSTRAÇÕES
FIG. 2.1 Modelo de Gilbert-Elliott .................................................................. 26
FIG. 2.2 Modelo de Fritchman-SES de N estados ........................................ 28
FIG. 2.3
Estimação dos parâmetros do modelo de Gilbert-Elliott pelo
algoritmo de Baum-Welch ...............................................................
39
FIG. 2.4 Efeito do tamanho da amostra na estimação de parâmetros pelo
método de Baum-Welch ..................................................................
40
FIG. 3.1 Modelo básico geral (HMM de n estados) ....................................... 44
FIG. 3.2 Célula básica de 2 estados – Gilbert Elliott ..................................... 44
FIG. 3.3 Diagrama de estados para um modelo originado de um modelo de
Gilbert-Elliott, para L=3 ....................................................................
48
FIG. 4.1 Comparação entre as distribuições do parâmetro comprimento de
surto, levantada para ‘L’s diferentes, a partir de um mesmo bloco .
56
FIG. 4.2 Comparação entre as distribuições do parâmetro intervalo entre
surtos, levantada para ‘L’s diferentes de um mesmo bloco ............
58
FIG. 4.3 Distribuição do parâmetro densidade de erro por surto média,
para L=3 ..........................................................................................
60
FIG. 4.4 Comparação entre as distribuições calculadas do parâmetro
comprimento de surto, para probabilidades de transição fixas e L
diferentes .........................................................................................
61
FIG. 4.5 Comportamento das distribuições calculadas e estimadas do
parâmetro comprimento de surto....................................................
62
1
FIG. 4.6 Comportamento da curva de distribuição dos comprimentos de
surto gerada pelo modelo de Gilbert-Elliott para PG e PB
próximos da unidade .......................................................................
63
FIG. 4.7 Curva coeficiente angular x L para a distribuição de comprimento
de surto ............................................................................................
64
FIG. 4.8 Comportamento inicial da distribuição do parâmetro comprimento
de surto e comparação entre modelo e simulação .......................
66
FIG. 4.9 Comparação entre as distribuições calculadas do parâmetro
intervalo entre surtos, para probabilidades de transição fixas e L
diferentes .........................................................................................
67
FIG. 4.10 Comparação entre simulação e modelo para L=3 .......................... 69
FIG. 4.11 Comparação entre simulação e modelo para L=4 .......................... 70
FIG. 4.12 Comparação entre simulação e modelo para L=10 ........................ 71
FIG. 4.13 Modelo básico de 3 estados ............................................................ 73
FIG. 4.14 Distribuição dos comprimentos entre surtos para um modelo
básico de 3 estados .........................................................................
73
FIG. 4.15 Distribuição dos intervalos entre surtos para um modelo básico de
3 estados .........................................................................................
74
FIG. 4.16 Modelo básico de Fritchman-SES de 3 estados ............................. 75
FIG. 4.17 Distribuições dos comprimentos de surto simuladas e calculadas,
com base no modelo de Fritchman-SES de 3 estados ...................
76
FIG. 4.18 Distribuições dos comprimentos de surto simuladas e calculadas,
com base no modelo de Fritchman-SES de 3 estados, para ‘L’s
diferentes .........................................................................................
77
1
FIG. 4.19 Distribuições dos intervalos entre surtos simuladas e calculadas,
com base no modelo de Fritchman-SES de 3 estados ...................
78
FIG. 4.20 Distribuições dos comprimentos de surtos levantadas da
simulação do canal de HF e calculadas pelo modelagem baseada
em um modelo básico de Gilbert-Elliott, cujos parâmetros foram
estimados ........................................................................................
81
FIG. 4.21 Distribuições dos intervalos entre surtos levantadas da simulação
do canal de HF e calculadas pela modelagem baseada em um
modelo básico de Gilbert-Elliott, cujos parâmetros foram
estimados ........................................................................................
82
FIG. 4.22 Ajuste da curva de distribuição dos comprimentos de surtos
pela curva obtida pelo modelo derivado ..........................................
83
1
LISTA DE TABELAS
TAB. 3.1 Tabela de transição para o modelo derivado ....................................... 45
TAB. 3.2 Tabela de transição simplificada para modelo básico de 2 estados
(η=2) .....................................................................................................
47
TAB. 4.1 Levantamentos estatísticos do parâmetro comprimento de surto do
experimento da FIG. 4.1 ....................................................................
57
TAB. 4.2 Estatística do parâmetro intervalo entre surtos .................................... 58
TAB. 4.3 Tempos de processamento .................................................................. 72
TAB. 4.4 Estatística para o parâmetro comprimento de surto, baseado no
modelo de Fritchman-SES de 3 estados .............................................
76
TAB. 4.5 Estatística para o parâmetro intervalo entre surtos, baseado no
modelo de Fritchman-SES de 3 estados .............................................
78
TAB. 4.6 Parâmetros da CCIR para simulação de condições do canal de HF ... 79
1
LISTA DE ABREVIATURAS E SÍMBOLOS
ABREVIATURAS
ARQ - Automatic Repeat reQuest
ATM - Asynchronous Transfer Mode
BER - Bit Error Rate
BLOS - Beyond Line of Sight
FEC - Forward Error Correction
HF - High Frequency
HMM - Hidden Markov Model
IID - Independentes e Identicamente Distribuidos
IP - Internet Protocol
LEO - Low Earth Orbit
ML - Maximum Likelihood
PDF - Probability Density Function
SchEMe - Skywave Channel Error Model
SES - Single Error State
UHF - Ultra High Frequency
TCP - Transport Control Protocol
SÍMBOLOS
A - Matriz de probabilidades de transição
B - Matriz das distribuições de probabilidades em cada estado
C(k,L) - Surto de comprimento k, dado L
ei - Estado i de um modelo de Markov
I - Conjunto das entradas do modelo derivado
I(k,L) - Intervalo de comprimento k, dado L
L - Critério de comprimento de surto
m - Número de símbolos do alfabeto de observações
N - Número de estados de um modelo de Markov ou do modelo derivado
1
NP - Número máximo de probabilidades distintas não nulas
ot - Observação no instante t
PB - Probabilidade de ir do estado bom para o estado ruim
pb - Probabilidade de erro do estado ruim
PG - Probabilidade de ir do estado ruim para o estado bom
pg - Probabilidade de erro do estado bom
P(O/λ) - Função Verossimilhança
P - Vetor das probabilidades dos estados do modelo derivado no estado
estacionário
qt - Estado no instante t
S - Conjunto dos estados do modelo derivado
αt(i) - Variável Progressiva
βt(i) - Variável Regressiva
η - Número de estados do modelo básico
λ - Modelo Escondido de Markov (HMM)
π - Vetor das probabilidades iniciais dos estados
1
LISTA DE SIGLAS
CCIR Comité Consultatif International de Radio
CCITT Community Colleges for Innovative Technology Transfer
IEEE Institute of Electrical and Electronic Engineers
ITU International Telecommunication Union
ITU-R ITU - Radio
1
RESUMO
A ocorrência de erros em surtos é um problema verificado principalmente nos canais “sem fio” incluindo as comunicações via satélite e os sistemas que operam na faixa de HF. A qualidade destes canais pode variar aleatoriamente devido a diversos fatores tais como: mobilidade, desvanecimento, sombreamento, interferência e ruído. A freqüência de operação e a velocidade do usuário de um sistema de comunicações influenciam no processo de desvanecimento devido ao efeito “multi-percursos”. Os códigos convolucionais e a decodificação de Viterbi, apesar de serem técnicas de correção de erros amplamente usadas para melhorar a taxa de erro de bit (BER) nos sistemas de comunicações via satélite, são também capazes de gerar erros em surtos. Neste trabalho é proposto um modelo de Markov para representar canais de comunicações sujeitos a erros em surtos, cujos estados e entradas são definidos com base em um modelo escondido de Markov clássico. Quando comparado com massas de dados simuladas, este modelo mostrou-se bastante eficiente com relação ao tratamento matemático e computacional voltados para o levantamento dos parâmetros de interesse.
1
ABSTRACT
The occurrence of burst errors is a problem mainly noted on wireless channels, including satellite communications systems and the systems that operate on HF band. The quality of that channels may fluctuates randomly due to a number of unpredictable effects such as mobility, fading, shadowing, interference, and noise. In wireless communications systems, the radio frequency and user speed affect the fading process due to the multi-path effect. Even though the convolutional codes and Viterbi decoding are error correction techniques widely used to improve the bit error rate (BER) performance over satellite communications systems, they are able to generate errors in bursts. In this work it is proposed a Markov model for modeling communications channels with busty behavior, which has its states and inputs definitions based in a classic Hidden Markov Model. When that model was compared with simulated data blocks, it was very efficient in the mathematic and computational treatments used to get the parameters of interest.
1
1 INTRODUÇÃO
1.1 POSICIONAMENTO DO TRABALHO
O fenômeno dos erros em surtos é uma característica dos canais “sem fio”,
sujeitos a todos aqueles fatores citados no resumo deste trabalho, abrangendo as
comunicações móveis, via satélite e HF, tão amplamente empregadas pelos
sistemas de comunicações atuais e em especial pelas Forças Armadas, devido suas
características de emprego. Isto ressalta a importância do estudo deste problema, e
o desenvolvimento de métodos que o minimizem, tornando mais confiáveis estes
importantes sistemas de comunicações. A seguir são citados alguns exemplos sobre
o impacto causado pelos erros em surtos sobre alguns sistemas de comunicações.
Os erros em surtos introduzidos pelo canal de um sistema de comunicações
podem acarretar impactos sobre os protocolos de comunicações. Como exemplo,
pode-se citar o protocolo TCP o qual associado ao IP é amplamente utilizado em
aplicações Internet, tendo sido inicialmente projetado para redes por cabo, onde a
taxa de erro de canal é muito baixa. Entretanto, quando associado a canais “sem
fio”, o TCP tem seu desempenho severamente afetado, devido à perda de pacotes
ocasionada pelos surtos de erros (CHOCKALINGAM, 1998). Da mesma forma nos
anos mais recentes tem havido um crescente interesse pelo ATM “sem fio”, o qual
inicialmente projetado para ambientes livres de erros, agora operando com canais
“sem fio” requer estudos sobre o impacto que recebe pelos erros em surtos (ZORZI,
Set 1998).
Os sistemas de comunicações táticas do Exército dos E.U.A. são tipicamente
amparados por sistemas de satélites a fim de prover alcance além da linha de visada
(BLOS). Estes sistemas adotam os protocolos ATM ou IP, os quais requerem canais
de alta qualidade com BER menor ou igual de 10-8. Como estes canais de satélites
apenas permitem BER da ordem de 10-5, uma solução encontrada para a melhora
de performance é a aplicação dos Códigos Convolucionais e Decodificação de
Viterbi, que por sua vez introduz erros em surtos no sistema (HEISSLER, 1999).
Em particular, o estudo do impacto causado pelos erros em surtos no
desempenho das técnicas de controle de erros assume grande importância diante
1
do exposto. Em (ZORZI, mai. 1998), é realizada uma comparação entre os
desempenhos dos métodos FEC (Forward Error Correction) e ARQ (Automatic
Repeat reQuest) de controle de erros, onde observa que num sistema de
comunicações “sem fio”, as técnicas de retransmissão para recuperar erros de canal
são soluções que em alguns casos devem ser mais eficientes do que as técnicas
FEC.
1.2 FINALIDADE DO TRABALHO
Os primeiros passos para o estudo do comportamento dos erros em surtos se
constituem na modelagem matemática deste fenômeno e no levantamento e análise
de seus parâmetros. A modelagem de um canal de comunicações tem como
finalidade a obtenção de modelos matemáticos capazes de representar com
adequada precisão o comportamento deste canal, sendo de grande importância para
o levantamento de seus parâmetros estatísticos e para o estudo de técnicas de
controle dos erros inerentes a este canal. Modelos nos quais os erros são
independentes e identicamente distribuídos (IID), são inadequados quando se
espera as condições de um canal sujeito ao fenômeno dos erros em surtos (ZORZI,
1999), pois estes possuem significante grau de correlação, não podendo, portanto
ser desprezado o efeito memória destes canais. Os modelos matemáticos mais
empregados para representar processos com memória, têm sido os modelos de
Markov, em que se supõe que a informação atual depende exclusivamente da
informação do instante de tempo imediatamente anterior sendo desnecessária a
informação de todo o passado restante (ZORZI, 2000 e HEISSLER, 1999). Dentre
eles destacam-se os modelos de Gilbert, Elliott e Fritchman, os quais serão descritos
no capítulo 2. Métodos empíricos e ajuste de curvas também são empregados para
representação de distribuições de parâmetros, como em (FRANCHI, 1993), que
procura ajustar a distribuição dos comprimentos de surtos por uma distribuição
geométrica.
Uma grande contribuição sobre o assunto tem sido dada por Michele Zorzi e
Ramesh R. Rao, por meio de suas publicações sobre erros em surtos, abordando a
sua modelagem, suas estatísticas e impacto em alguns sistemas de comunicações
como o TCP (ZORZI, 2000). Já Rabiner e Juang, apesar de trabalharem
2
direcionados para o processamento de sinais de voz, muito contribuem com
métodos para a estimação de parâmetros de um Modelo Escondido de Markov,
possuindo, além de suas publicações, um livro que aborda este assunto (RABINER,
1993).
1.3 ORGANIZAÇÃO DO TRABALHO
O presente trabalho procura encontrar um método eficiente para se obter
modelos adequados para os canais sujeitos a erros em surtos e para o levantamento
e análise dos parâmetros “comprimento de surto de erro” e “intervalo entre surtos de
erro”. O capítulo 2 aborda a definição de erro em surto do CCITT, a qual será
adotada para as análises realizadas, e a teoria sobre as Cadeias de Markov
Escondidas, base necessária ao desenvolvimento deste trabalho e das ferramentas
de simulação e análise.
O enfoque principal do trabalho, abordado pelo capítulo 3, é a proposta de uma
solução para o problema da modelagem e do levantamento dos parâmetros
“comprimento de surto de erro” e “intervalo entre surtos de erro”. Isto é realizado por
meio de um modelo de Markov gerado por uma nova definição dos estados e das
entradas. O capítulo 4, de uma maneira geral, traz os resultados, baseados no
levantamento dos referidos parâmetros de blocos de dados simulados afetados por
surtos de erro e os baseados no modelo proposto no capítulo 3, sendo realizada
comparação entre os dois métodos. Ao final deste capítulo é sugerido e
exemplificado um método para estimação de parâmetros de um HMM por meio do
modelo proposto. O capítulo 5 apresenta uma conclusão, mostrando a contribuição
do trabalho para o estudo dos erros em surtos e propostas para futuros trabalhos
relacionados à aplicação dos resultados aqui obtidos.
2
2 CONCEITOS BÁSICOS
2.1. ERROS EM SURTOS
Um surto de erro é definido pelo CCITT (CCITT “BLUE BOOK”) como: Um
grupo de bits no qual dois bits errados sucessivos estejam sempre separados por
menos do que um dado número L de bits corretos. O número L, que a partir de
agora chamaremos de critério de comprimento de surto, como é definido em
(FRANCHI, 1993), deve ser adequadamente escolhido conforme a aplicação, antes
de qualquer análise ou levantamento de parâmetros. Esta definição afeta
diretamente as distribuições de probabilidades dos parâmetros ‘comprimento de
surto de erro’ e ‘comprimento de intervalo entre surtos de erro’, os quais por
comodidade, a partir de agora chamaremos simplesmente de ‘comprimento de surto’
e ‘intervalo entre surtos’, respectivamente.
O primeiro parâmetro mencionado é o comprimento de um surto de erros,
conforme a definição do CCITT. Este parâmetro é afetado, pois quanto maior é L,
mais seqüências de bits errados, separadas de no máximo L-1 bits corretos são
unidas formando surtos mais longos. Ocorrem assim, uma diminuição das
probabilidades de ocorrência de surtos menores, ao mesmo tempo em que
aumentam as probabilidades de ocorrência de surtos maiores. O segundo parâmetro
refere-se ao número de bits corretos (maior ou igual a L), que separa dois surtos de
erro consecutivos. Este parâmetro é afetado em primeiro lugar, com relação ao
suporte da sua distribuição, pois de acordo com a definição de surto de erro do
CCITT, o menor intervalo entre dois surtos que pode ocorrer é de comprimento L.
Em segundo lugar, com o aumento de L, tem-se uma diminuição dos números de
intervalos possíveis e um conseqüente aumento das respectivas probabilidades de
ocorrência.
A. Franchi e R. A. Harris (FRANCHI, 1993) realizam experimentos baseados na
definição de surto de erro do CCITT, onde levantam a variação sofrida pelos
parâmetros comprimento de surto, comprimento médio de surto e densidade de erro
em um surto, para diferentes valores de L.
2
Todas as distribuições de probabilidades apresentadas neste trabalho são de
probabilidades condicionais, dado a ocorrência dos surtos de erros.
Os processos de Markov, apesar de serem simples aproximações, permitem-
nos representar o efeito memória dos processos com erros em surtos (ZORZI, 1999)
e ainda, a possibilidade de tratá-los analiticamente. Modelos mais precisos podem
ser encontrados, porém em muitos casos, resultando em um aumento de
complexidade matemática não compensador em termos práticos (ZORZI, 1999).
Assim, na escolha do modelo mais adequado à nossa aplicação, devemos levar em
conta os fatores precisão e complexidade, assim como o tempo de processamento.
O fator precisão significa a capacidade do modelo em representar, em termos
estatísticos o comportamento de um determinado canal de comunicações; o fator
complexidade diz respeito à representação matemática do modelo, implicando
diretamente na complexidade computacional, em termos de memória e do tempo de
processamento, que foi o último fator mencionado relacionando-se à velocidade com
que os resultados computacionais são gerados, seja em simulações ou
levantamentos de parâmetros extraídos de massas de dados.
2.2 MODELOS DE MARKOV ESCONDIDO (HMM)
2.2.1 DEFINIÇÃO
HMM (Hidden Markov Model) é um modelo composto de um conjunto finito de
estados, cada qual por sua vez associado a uma distribuição de probabilidades da
ocorrência de observações. Neste trabalho, em que o tempo é considerado discreto,
as transições entre os estados acontecem a cada unidade de tempo e são definidas
por um conjunto de probabilidades chamadas probabilidades de transição. Assim,
não só o estado, mas também a distribuição de probabilidades associada a este,
influenciará nas observações geradas. O termo “observação” é empregado porque
se refere ao símbolo que aparece para um observador externo, sendo os estados
escondidos a este, daí o nome Modelo de Markov Escondido.
2
2.2.2 CONSIDERAÇÕES
Com o objetivo de diminuir a complexidade do tratamento matemático e
computacional dos HMMs, são feitas as seguintes considerações:
2.2.2.1 PROPRIEDADE DE MARKOV
As probabilidades de transição são definidas como: ai,j = p(qt+1 = j | qt = i ), onde
qt é definido como o estado do sistema no instante t. É considerado que o próximo
estado, depende apenas do estado atual, não importando nenhum estado passado.
Com esta suposição, o modelo resultante é dito HMM de primeira ordem. Entretanto
podemos considerar que o próximo estado dependa dos ‘k’ estados passados e
assim poderemos obter um modelo chamado HMM de k-ésima ordem com as
correspondentes probabilidades de transição a seguir definidas:
Njiiiiqiqiqjqpa kkkttttjiii k≤≤===== +−−+ ,,,,1),,,,|( 2112111,21
LLL (2.1)
HMM de ordens mais altas geram maior complexidade, sendo mais empregados
os HMMs de primeira ordem, como será o nosso caso no estudo dos erros em
surtos.
2.2.2.2 ESTACIONARIEDADE
As probabilidades de transições entre estados são independentes de
deslocamentos no tempo, como está matematicamente representado a seguir:
)|()|(2211 11 iqjqpiqjqp tttt ===== ++ (2.2)
para qualquer t1 e t2.
2.2.2.3 SEQÜÊNCIA DE OBSERVAÇÕES
Considera-se como seqüência de observações, uma seqüência indicadora da
correção dos bits da seqüência de dados em questão, sendo que cada bit ‘0’ da
primeira indica que o correspondente bit da segunda chegou correto, e cada bit ‘1’
da primeira indica que o correspondente bit da segunda chegou errado.
2
2.2.2.4 INDEPENDÊNCIA DA SAÍDA
A observação atual é estatisticamente independente das observações
anteriores. Podemos representar matematicamente esta consideração definindo a
seqüência de observações:
O = o1, o2, ... oT (2.3)
considerando um HMM λ, temos:
∏=
=T
t
ttT qopqqqOp1
21 ),|(),,...,,|( λλ (2.4)
2.2.3 PARÂMETROS
Para que um HMM deste tipo seja completamente caracterizado, é necessário
estarem definidos os seguintes parâmetros:
N – Número de estados;
m – Número de símbolos do alfabeto de observações. Admite-se a partir deste
ponto que a observação assume valores em um conjunto discreto e finito. Ou seja,
que cada observação ot ∈ ν1, ν2, ... , νm , que é o conjunto alfabeto de
observações.
A – Matriz das probabilidades de transição, sendo:
A=ai,j; ai,j = p(qt+1 = j | qt = i ); 1 ≤ i, j ≤ N; (2.5)
‘qt’ representa o estado no tempo ‘t’.
As probabilidades de transição ‘aij’ devem atender as seguintes condições:
0 ≤ ai,j ≤ 1; ;11
, =∑=
N
j
jia 1 ≤ i, j ≤ N; (2.6)
B – Matriz das distribuições de probabilidades em cada estado sendo:
B = bj(k) ; onde: bj(k) = p(ot = vk | qt = j), 0 ≤ j ≤ N; 1 ≤ k ≤ m (2.7)
2
e ‘vk’ representa o K-ésimo símbolo de observação no alfabeto e ‘ot’ a observação
no tempo ‘t’.
As probabilidades ‘bj’ devem obedecer as seguintes condições:
0 ≤ bj(k) ≤ 1; ;1)( 1
=∑=
m
k
j kb 0 ≤ j ≤ N; 1 ≤ k ≤ m (2.8)
π – Vetor das probabilidades iniciais de cada estado sendo:
π = πi ; onde: πi = p(q1 = i) (2.9)
As probabilidades ‘πi’ devem obedecer as seguintes condições:
0 ≤πi ≤ 1; 1 1
=∑=
N
i
iπ ; 1 ≤ i ≤ N; (2.10)
Assim representamos um HMM com distribuição discreta de probabilidades por:
λ=(A,B,π) (2.11)
2.2.4 MODELO DE GILBERT- ELLIOTT
Especificamente para o caso da modelagem dos erros em surtos, algumas
publicações como (ZORZI, 1996, set. 1998 e 1999) informa que o modelo de Gilbert-
Elliott, que é um HMM de primeira ordem de dois estados, modela satisfatoriamente
este fenômeno e que por sua simplicidade, possibilita adequado tratamento
matemático e computacional. O alfabeto de símbolos utilizados é o binário (m=2).
Este modelo é definido da seguinte forma:
a) O estado 1 representa o estado bom (G);
b) O estado 2 representa o estado ruim (B);
c) O vetor B possui como elementos apenas quatro probabilidades: as duas
probabilidades complementares de emitir um bit errado ou um bit correto no estado 1
e as duas probabilidades análogas para estado 2 ( bi(k) );
d) O vetor π se constitui das 2 probabilidades iniciais do sistema: a
probabilidade de estar no estado 1 (P1) e a de estar no estado 2 (P2). Como
a consideração de estacionariedade é adotada, o vetor das probabilidades
de estado iniciais é o vetor das probabilidades do estado estacionário. Assim
2
o vetor π é o autovetor da matriz de transição (A), correspondente ao
autovalor 1, sendo solução do seguinte sistema (PAPOULIS, 1991, p. 639):
πA = π , e πi ≥ 0
e) O diagrama de estados correspondente a este modelo está representado na
FIG. 2.1:
Assim os parâmetros para este modelo ficam resumidos como a seguir:
=
2221
1211
aa
aaA sendo: a12 = 1- a11 e a22 = 1- a21 (2.12)
=
)1()0(
)1()0(
22
11
bb
bbB sendo: b1(0) = 1 - b1(1) e b2(0) = 1 – b2(1) (2.13)
( )21,PP=π sendo: 12 1 PP −= e 2112
211
aa
aP
+= (2.14)
O número de unidades de tempo em que o canal permanece no estado ruim é
uma variável aleatória com distribuição geométrica, portanto com média 1/a21.
Analogamente, o tempo que o canal permanece no estado bom é uma variável
aleatória com média 1/a12 (ZORZI, 1995, 1996 e 1997).
FIG. 2.1: Modelo de Gilbert-Elliott
1 1
=∑=
N
i
iπ
2
O modelo de Gilbert-Elliott é uma generalização do modelo de Gilbert, realizado
por Elliott. Inicialmente Gilbert idealizou um modelo de Markov de dois estados,
semelhante ao apresentado neste item, porém com a diferença de possuir
probabilidade de erro igual a zero no estado bom ( b1(1)=0 ). Mais tarde Elliott
considerou a possibilidade de probabilidades de erro diferentes de zero para o
estado bom (SHEN, 1999). A seguir será apresentado o modelo de Fritchman, uma
generalização do modelo de Gilbert, em relação ao número de estados.
2.2.5 MODELO DE FRITCHMAN
Para os canais cujos erros em surtos não são adequadamente representados
pelo modelo de Gilbert-Elliott, uma outra possibilidade é o modelo N-estados
particionados de Fritchman, que se constitui de uma generalização do modelo de
Gilbert, para N estados. Nele os estados são particionados em k estados de erro
(ruins) e N-k estados livres de erros (bons), em que só são permitidas transições
entre os estados bons e os estados ruins (FRITCHMAN, 1967). O que diferencia os
estados bons entre si são as respectivas probabilidades de transição entre estes e o
estado ruim. Neste modelo, a distribuição de intervalos entre surtos fica descrita pela
soma de k distribuições exponenciais enquanto a distribuição de comprimentos de
surtos pela soma de N-k exponenciais (CHU, 2002).
Uma particularização do modelo de Fritchman é o modelo Fritchman-SES
(SES – Sigle-Error-State), selecionado por (JOHNSON, 1994) para modelar o “HF
SchEMe” (Skywave Channel Error Model). Este modelo consiste no modelo de
Fritchman para k=1, ou seja, um único estado ruim para vários estados bons os
quais podem ser em número de dois, três ou mais. Na FIG. 2.2 está representado
um modelo de Fritchman-SES de N estados, onde o estado ruim está indicado por
(B) e os N-1 estados bons estão indicados por (G1), (G2) ... (GN-1), respectivamente.
Este modelo é definido pela seguinte matriz de transição, onde o estado N foi
considerado o estado ruim, deste modo os elementos nulos representam as
probabilidades de transição entre os estados bons:
2
=
−
−−
NNNNNNN
NN
N
N
N
ppppp
p
pp
pp
pp
A
1,321
1,1
333
222
111
0000
000
000
000
L
L
MMOMMM
L
L
L
Outras formas do modelo de Fritchman podem ser também utilizadas de acordo
com a aplicação. Para ilustrar a seleção de diferentes modelos para diferentes
aplicações, estudos sobre modelagem de canais de satélites de baixa órbita (LEO)
descritos em (CHU, 2002) empregam, além dos modelos de Fritchman-SES de três
e quatro estados, o modelo de Fritchman de 4 estados para k=2, ou seja dois
estados bons e dois estados ruins. O primeiro modelo mencionado acima é utilizado
em (CHU, 2002). para descrever a estatística de surtos de erros do sistema LEO-
UHF para os ângulos de elevação de 23o e 52o; o segundo para os ângulos de
elevação restantes e o terceiro para canais sujeitos a interferências.
2.2.6 OS TRÊS PROBLEMAS BÁSICOS RELATIVOS A HMM
No que diz respeito ao levantamento de parâmetros estatísticos a partir de uma
massa de dados existente, os HMMs dão origem a três problemas. A seguir, tudo de
(RABINER, 1993), serão apresentados uma rápida descrição destes problemas e
2
um posterior detalhamento do desenvolvimento teórico que será aplicado aos erros
em surtos, na implementação de ferramentas para estimação de parâmetros:
- Cálculo da função Verossimilhança: dado um HMM λ=(A,B,π) e uma
seqüência O = o1, o2, ... oT de observações, deseja-se calcular a probabilidade
das observações terem sido geradas pelo modelo λ:
P(O/λ); (2.15)
- Seqüência de Estados: dado um HMM λ=(A,B,π) e uma seqüência
O = o1, o2, ... oT de observações, deseja-se saber qual a mais provável seqüência
de estados de λ, que tenha gerado o conjunto de observações O;
- Estimação ML de Parâmetros: dada uma seqüência O = o1, o2, ... oT de
observações, deseja-se ajustar os parâmetros do modelo HMM λ=(A,B,π), de modo
a maximizar P(O/λ).
2.2.6.1 CÁLCULO DA FUNÇÃO VEROSSIMILHANÇA
Com o modelo λ=(A,B,π) e uma seqüência de observações O = o1, o2, ... oT
e devemos calcular a probabilidade da seqüência ‘O’ dado o modelo λ, P(O/λ). No
entanto, se este cálculo for feito de maneira direta, a sua alta complexidade o torna
computacionalmente inviável, mesmo para seqüências de pequeno comprimento,
pois envolve um número de operações da ordem NT, que cresce exponencialmente
com o tamanho da seqüência (T). Assim devemos buscar um método de cálculo que
reduza esta complexidade de modo a tornar o problema computacionalmente
tratável. Para tanto faremos uso de duas variáveis auxiliares: αt(i) – Variável
Progressiva e βt(i) – Variável Regressiva.
2.2.6.1.1 VARIÁVEL PROGRESSIVA
A Variável Progressiva é definida como a probabilidade de ocorrência da
seqüência parcial de observações O1t = o1, o2, ... ot, quando terminada no estado i,
isto é, ot sendo gerado pelo estado i. Está matematicamente representada a seguir:
3
)|,,...,,(),( 211 λα iqooopiO tt
t
t == (2.16)
A qual a partir daqui nos referiremos simplesmente como αt(i).
Assim podemos deduzir a seguinte relação recursiva:
∑=
++ =N
i
ijttjt aiobj1
11 )()()( αα , 1 ≤ j ≤ N , 1 ≤ t ≤ T-1 (2.17)
onde: α1(j) = πjbj(o1), 1 ≤ j ≤ N (2.18)
Através das relações acima calculamos:
αT(i) , 1 ≤ i ≤ N (2.19)
A função verossimilhança é dada por:
∑=
=N
i
T iOp1
)()|( αλ (2.20)
A complexidade deste cálculo é proporcional a N2T, que cresce linearmente com o
tamanho da seqüência T.
2.2.6.1.2 VARIÁVEL REGRESSIVA
Agora definimos a Variável Regressiva, como a probabilidade da ocorrência da
seqüência parcial de observações O1t = ot+1, ot+2, ... , oT, dado que o estado atual é
i, e está matematicamente representada a seguir:
),|,...,,(),( 211 λβ iqooopiO TTtt
t
t == ++ (2.21)
a qual a partir daqui nos referiremos simplesmente como βt(i).
Como no caso de αt(i) existe uma relação recursiva para o cálculo de βt(i):
)()()( 1
1
1 +=
+∑= t
N
j
jijtt obaji ββ , 1 ≤ i ≤ N , 1 ≤ t ≤ T-1 (2.22)
onde: βT(i)=1, 1 ≤ i ≤ N (2.23)
Das relações acima temos:
αt(i)βt(i) = p(O, qt = i | λ ), 1 ≤ i ≤ N , 1 ≤ t ≤ T (2.24)
Assim obtemos um outro modo para o cálculo de P(O/λ), usando as duas variáveis
acima definidas, como a seguir:
3
∑∑==
===N
i
tt
N
i
t iiiqOpOp11
)()(|),()|( βαλ (2.25)
2.2.6.2 SEQÜÊNCIA DE ESTADOS
Com o modelo λ=(A,B,π) e a seqüência O = o1, o2, ... oT de observações,
deseja-se encontrar a seqüência de estados mais provável do modelo que possa ter
gerado as observações. O critério mais utilizado para este fim é o que encontra uma
única seqüência de estados como solução através da maximização da probabilidade
P(q,O|λ) pelo Algoritmo de Viterbi.
Primeiramente definimos a variável δt(i), que indica a seqüência de estados mais
provável de comprimento t, relativa às t primeiras observações e que termina no
estado i:
|...,,...max)( 21121,...,, 121
λδ tttqqq
t oooiqqqqPit
== −−
(2.26)
por indução:
)(])([max)( 11 ++ = tjijti
t obaij δδ (2.27)
Assim encontramos a seqüência q1q2, ..., qT, que maximiza a EQ. 2.27 para cada t e
j. Para implementar uma rotina que calcule a seqüência de estados mais provável,
podemos seguir os passos:
a) Inicialização
( )11 )( obi iiπδ = (2.28)
0)(1 =iψ 1 ≤ j ≤ N (2.29)
b) Recursividade
)(])([max)( 11
tjijtNi
t obaij −≤≤
= δδ (2.30)
])([maxarg)( 11
ijtNi
t aij −≤≤
= δψ 2 ≤ t ≤ T e 1 ≤ j ≤ N (2.31)
c) Término
3
)]([max1
*iP T
Niδ
≤≤= (2.32)
)]([maxarg1
*iq T
NiT δ
≤≤
= (2.33)
d) Seqüência de estados
)( *
11
*
++= ttt qq ψ t=T-1, T-2, ..., 1 (2.34)
2.2.6.3 ESTIMAÇÃO DE PARÂMETROS
Neste caso o objetivo é ajustar os parâmetros de um HMM (A,B,π) para que este
represente da melhor maneira possível uma dada seqüência de observações
(seqüência de treinamento). Para a nossa aplicação utilizaremos o critério da
Máxima Verossimilhança (ML) implementando o Algoritmo de Baum-Welch.
2.2.6.3.1 CRITÉRIO DA MÁXIMA VEROSSIMILHANÇA (ML)
No Critério ML, nós procuramos maximizar a probabilidade de uma dada
seqüência de observações O = o1, o2, ... oT ter sido gerada por um dado HMM λ, por
meio do ajuste de seus parâmetros (A,B,π). Essa probabilidade é a verossimilhança
total das observações, isto é, a soma das probabilidades da observação ter sido
gerada por todas as seqüências de estados possíveis e é matematicamente
representada por:
Ltot = P(O/λ) (2.35)
Não existe nenhuma maneira conhecida de se resolver este problema
analiticamente, ou seja encontrar os parâmetros do HMM λ que maximize Ltot
(RABINER, 1993, p. 342). No entanto podemos encontrar parâmetros que maximize
localmente Ltot , através do uso do Algoritmo de Baum-Welch, o qual está descrito a
seguir:
3
2.2.6.3.2 ALGORITMO DE BAUM-WELCH
Primeiramente definimos a função auxiliar Q:
∑=q
qOpqOpQ )|,(log)'|,(),'( λλλλ (2.36)
a qual deverá ser maximizada em λ a fim de atualizar λ’ no sentido de aumentar
P(O|λ), por meio de cálculos recursivos (RABINER, 1993, p. 344-346), porque:
)'|()|()','(),'( λλλλλλ OPOPQQ ≥⇒≥ (2.37)
Uma característica muito importante deste algoritmo é a garantia da
convergência (RABINER, 1993, p. 344,348):. Define-se ainda, mais duas variáveis
auxiliares em adição as variáveis progressiva e regressiva definidas anteriormente.
A primeira delas é dada pela probabilidade de se estar no estado i em t e no estado
j em t+1 dado o modelo e a seqüência de observações, ou seja:
),|,(),( 1 λξ Ojqiqpji ttt === + (2.38)
ou ainda,
)|(
)|,,(),( 1
λ
λξ
Op
Ojqiqpji tt
t
=== +
(2.39)
em função das variáveis progressiva e Regressiva,
∑∑= =
++
++=
N
i
N
j
tjtijt
tjtijt
t
objai
objaiji
1 1
11
11
)()()(
)()()(),(
βα
βαξ
(2.40)
A segunda variável auxiliar é dada pela probabilidade de se estar no estado i em t,
dados a seqüência de observações e o modelo λ, ou seja:
),|()( λγ Oiqpi tt == (2.41)
Em função das variáveis progressiva e Regressiva,
∑=
=
N
i
tt
tt
ii
ii
t i
1
)()(
)()()(
βα
βαγ (2.42)
3
A relação entre γ(i) e ξ(i,j) é dada por:
∑=
=N
j
tt ji1
),(ξγ , 1≤i≤N, 1≤t≤M (2.43)
Agora podemos descrever as equações de reestimação dos parâmetros pelo
método de Baum-Welch. Estas equações são recursivas e a cada iteração o
parâmetro calculado é substituído na própria equação e calculado novamente
(reestimado), e assim sucessivamente até que se alcance o valor do parâmetro
procurado, segundo algum critério de parada. Os parâmetros de um HMM são
atualizados a cada iteração, no sentido de maximizar a probabilidade P(O/λ),
supondo um modelo modelo inicial λ1 =(A1 ,B1 ,π1). Inicialmente calculamos os ‘α’s
utilizando as EQ. 2.17 e 2.18, e os ‘β’s utilizando as EQ. 2.22 e 2.23. Em seguida
calculamos ξ’ e γ através das EQ. 2.32 e 2.34, respectivamente. Finalmente
atualizamos os parâmetros do HMM seguindo as equações a seguir, conhecidas
como fórmulas de reestimação:
Niii ≤≤= 1),(1γπ (2.44)
NjNi
i
ji
aT
t
t
T
t
t
ij ≤≤≤≤=
∑
∑−
=
−
= 1,1,
)(
),(
1
1
1
1
γ
ξ
(2.45)
mkNj
j
j
kbT
t
t
T
vOt
t
j
kt ≤≤≤≤=
∑
∑
=
==
1,1,
)(
)(
)(
1
1
γ
γ
(2.46)
Em função das variáveis progressiva e regressiva temos:
∑=
=N
j
T
i
j
ii
1
00
)(
)()(
α
βαπ
(2.47)
3
∑
∑
=−−
=−
=T
t
tt
T
t
ttjijt
ij
ii
jobai
a
1
11
1
1
)()(
)()()(
βα
βα
(2.48)
∑
∑
=
==T
t
tt
T
t
kttt
i
ii
voii
kb
1
1
)()(
),()()(
)(
βα
δβα
(2.49)
sendo:
≠
==
kt
kt
ktvose
vosevo
0
1),(δ
2.2.6.3.3 PROBLEMAS DE IMPLEMENTAÇÃO
Teoricamente, chegamos as fórmulas de reestimação, porém ainda existem
vários detalhes em nível de implementação que devemos observar e corrigir.
Comentaremos em seguida os mais significativos para este trabalho:
2.2.6.3.4 ORDEM DE GRANDEZA
As operações recursivas realizadas durante a estimação dos parâmetros de um
HMM fazem com que estes tendam a zero com o número de iterações. Isto acontece
devido ao fato de que as variáveis α(i) e β(i) são produzidas por um cálculo recursivo
e que cada iteração envolve produtos de probabilidades, como observado nas EQ.
2.17 e 2.22. Assim estes fatores são menores do que 1, fazendo com que α(i) e β(i)
atuais sejam sempre menores do que os anteriores, o que leva o valor destas
variáveis exponencialmente para zero com o incremento de t. Assim, mesmo que a
seqüência não seja muito grande, o limite de precisão de qualquer computador é
rapidamente atingido ao se executar este algoritmo. Para combater este problema
utilizaremos uma técnica de ponderar estas variáveis, ou seja, multiplicá-las por um
fator de escala ‘ct’ dependente do tempo, mas que não dependa de ‘i’ (RABINER,
1993, p. 365), de forma que os valores destas variáveis sejam mantidos dentro dos
3
limites de precisão do computador, quando o t varia de 1 até T. Os cálculos deste
procedimento estão descritos a seguir:
- Para t=1, calcula-se α1(i) como na EQ. 2.17;
- Cálculo do fator c1: ∑=
=N
i
i
c
1
1
1
)(
1
α e )()(ˆ111 ici αα = (2.50)
onde: )(ˆ1 iα representa o )(1 iα ponderado pelo fator c1;
- Cálculo recursivo de )(ˆ1 iα : ∑
=−=
N
j
tijitt obaji1
1 )()(ˆ)(ˆ αα ; (2.51)
Após calculado, )(ˆ itα deve ser aplicado nas EQ. 2.52, para o cálculo dos
novos valores de ct e )(ˆ itα , que deverão ser novamente aplicados na EQ. 2.51, e
assim sucessivamente.
sendo: )(ˆ)(ˆ ici ttt αα = onde: ∑=
=N
i
t
t
i
c
1
)(ˆ
1
α (2.52)
Como βt(i) possui a mesma ordem de grandeza de αt(i), utilizaremos o mesmo
fator de escala ct para ponderar estas variáveis, que também serão mantidas em
limites razoáveis para o cálculo computacional.
assim: )()(ˆ ici ttt ββ = (2.53)
2.2.6.3.5 SEQÜÊNCIA DE OBSERVAÇÕES INSUFICIENTE
Um outro problema ao nível de implementação é o efeito causado por uma
pequena seqüência de observação. No caso de bi(k), que significa a probabilidade
de ocorrer a observação vk no estado i, observa-se que o numerador de sua
equação de reestimação (EQ. 2.49) é uma soma cujos termos em que a observação
ot é diferente do símbolo vk, são nulos. Se esta probabilidade é pequena e a amostra
3
da seqüência utilizada na reestimação for também pequena, pode não ocorrer
nenhuma vez o evento ot igual a vk no estado i, assim o correspondente bi(k)
reestimado e conseqüentemente os seguintes serão nulos, levando os cálculos a
valores irreais.
Possíveis soluções seriam aumentar o comprimento da seqüência observada ou
diminuir o número de estados ou o número de símbolos do modelo utilizado,
parâmetros que geralmente não podemos alterar. Uma solução prática estipular
limiares mínimos para os parâmetros do modelo, obrigando-os durante a execução
do algoritmo a ficarem sempre acima destes limites, exemplo (RABINER, 1993, p.
371):
≥
=..,
;)(),()(
co
kbkbkb
b
bii
i δ
δ (2.54)
sendo: δb é o limiar mínimo fixado
2.2.6.3.6 ESTIMAÇÃO INICIAL DOS PARÂMETROS
As equações de reestimação produzem valores dos parâmetros de um HMM,
correspondentes a convergência para qualquer um dos máximos locais da função
verossimilhança, se houver mais de um. Portanto precisamos escolher parâmetros
iniciais, que nos conduzam ao seu máximo global. Não existe nenhuma maneira
simples e direta para resolver este problema (RABINER, 1993, p. 370), porém a
experiência tem mostrado que estimações iniciais aleatórias ou uniforme de ‘π’ e ‘A’
são adequados para a reestimação desses parâmetros. Foi observado que, para o
modelo de Gilbert-Elliott, as estimações iniciais sendo baseadas nas tendências dos
parâmetros devido a baixa probabilidade de erro do canal e dividindo-as em dois
grupos um de baixas probabilidades ( ≤ 0.25) e outro de altas probabilidades ( ≥
0.75), a convergência dos parâmetros se aproximou satisfatoriamente dos valores
esperados.
2.2.6.3.7 IMPLEMENTAÇÃO
Apesar deste assunto não ser o objeto principal deste trabalho, com o objetivo
de se obter uma ferramenta auxiliar para nossos estudos, foi implementado um
3
programa, que executa o algoritmo de Baum-Welch, recebendo como parâmetros de
entrada o bloco de dados e os valores iniciais para o processo de reestimação. A
FIG. 2.3 apresenta, como ilustração, o resultado obtido da estimação dos
parâmetros definidores de um HMM de dois estados. Observe que para este caso,
houve a convergência de todos os parâmetros com menos de dez iterações.
Observou-se para um bloco fixo de dados, que o número de iterações até a
convergência com determinada precisão, depende de dois fatores; dos parâmetros
iniciais e do tamanho da amostra. Este último influi também na precisão dos valores
finais encontrados, ou seja uma amostra pequena pode convergir em poucas
iterações, porém para valores assintóticos diferentes dos parâmetros reais.
A FIG. 2.4 ilustra a importância da dimensão da amostra utilizada para a
estimação dos parâmetros de um sistema. Observe que, apesar da convergência ter
ocorrido para todas as amostras em poucas iterações, à medida que aumentamos o
tamanho da amostra, a convergência ocorre para assíntotas correspondentes a
valores mais próximos dos parâmetros previamente conhecidos, que deram origem
a seqüência.
3
4
4
3 MODELO DE MARKOV PROPOSTO
Com o objetivo de solucionar eficientemente o problema da modelagem e da
análise de parâmetros dos erros em surtos, será proposto neste capítulo um modelo
de Markov específico para o cálculo das distribuições de probabilidades dos
parâmetros comprimento de surto e intervalo entre surtos, cuja dedução das
equações será detalhadamente apresentada. Basicamente, este modelo constitui-se
de uma Cadeia de Markov clássica originada a partir de uma Cadeia Escondida de
Markov (HMM). A partir deste ponto, a primeira cadeia mencionada acima será
referida como modelo derivado e a segunda como modelo básico. O modelo
derivado, apesar de mais complexo do que o modelo básico, é dedicado ao cálculo
dos parâmetros comprimento de surto e intervalo entre surtos, sendo a eficiência
nestes cálculos sua principal vantagem. Este modelo segue uma nova definição para
seus estados e suas entradas, onde uma entrada é definida como sendo uma
excitação originada no modelo básico necessária à transição de um estado para
outro ou para o mesmo estado do modelo derivado. Sua construção basea-se nos
quatro itens seguintes:
a) Toma-se um HMM como modelo básico e escolhe-se um valor para o critério
de comprimento de surto (L);
b) O estado atual do modelo derivado é definido por dois parâmetros, o estado
atual ei do modelo básico e o número y de bits 0 gerados após o último bit 1
gerado pelo modelo básico, sendo que se o número de bits 0 for maior ou
igual a L, define-se que y = E. Assim os estados de um modelo derivado de
um modelo básico de η estados são representadas por:
(ei, 0), (ei, 1), (ei, 2), ..., (ei, L-1), (ei, E) 1 ≤ i ≤ η;
c) A entrada do modelo derivado é definida por dois parâmetros: o próximo
estado ej do modelo básico e o bit gerado (0 ou 1) pelo estado atual do modelo
básico. Assim as entradas de um modelo derivado de um modelo básico de η
estados são representadas por:
(ej, 0) e (ej, 1) 1 ≤ j ≤ η;
4
d) Esta operação conduz a construção de uma nova matriz de transição e de
um correspondente diagrama de estados, dos quais a complexidade depende do
número de estados do modelo básico e de L.
Este modelo derivado possibilita a dedução das distribuições de probabilidades
dos parâmetros comprimento de surto e intervalo entre surtos, com muito mais
velocidade e precisão do que o levantamento destes parâmetros feitos através de
simulações.
3.1 DEFINIÇÕES
São definidos os seguintes parâmetros:
L – Critério de comprimento de surto;
N – No de estados do modelo derivado;
m – tamanho do alfabeto de símbolos dos vetores das observações:
m=2, O = 0,1 onde: '0' ≡ acerto e
'1' ≡ erro;
A – Matriz das probabilidades de transição do modelo derivado:
A= ai,j , ai,j = p(qt+1= j | qt = i ), 1 ≤ i, j ≤ N, qt = estado no tempo t;
π – Vetor das probabilidades de cada estado do modelo derivado no regime
estacionário:
π = pi , pi = p(q = i), 0 ≤ i ≤ N;
P – Vetor das probabilidades de erro dos estados
η – No de estados do modelo básico;
S = (x,y) – Estados do modelo derivado,
onde: x ∈ ei , i = 1...n (estado atual do modelo básico);
y = número (nz) de zeros após último 1 gerado, se nz < L
e
y = E, se nz ≥ L;
I = (u,v) – Entradas do modelo derivado,
onde: u ∈ ej , j = 1...η (próximo estado do modelo básico);
4
v = 0 ou 1 (bit gerado no estado atual do modelo básico);
3.1.1 NÚMERO DE ESTADOS
Observa-se de uma maneira geral, que cada estado do modelo básico define
um entre η grupos de estados do modelo derivado, onde em cada grupo, o
parâmetro y que representa o número de zeros desde o último ‘1’ gerado. Como o
parâmetro y pode assumir L+1 valores distintos, então o número N de estados do
modelo derivado é dado por:
N = η.(L+1) (3.1)
3.1.2 MODELO BÁSICO
O modelo básico constitui-se da Cadeia Escondida de Markov (HMM), a qual
originará o modelo derivado, cujo número de estados depende do número de
estados do modelo básico η e de L. Nota-se que uma mudança de estado no modelo
básico, por variar o primeiro parâmetro x do estado S do modelo derivado, implica
também em uma mudança de seu estado, o contrário não pode ser afirmado, já que
um mesmo estado do modelo básico pode originar mais de um estado do modelo
derivado, isto devido ao segundo parâmetro y de S, que representa o número de
zeros que o sistema gerou após o último ‘1’ gerado. Ainda deve ser observado que
logo que se gera um ‘1’, então y=0 e quando se gera L ou mais ‘0’ após o último ‘1’
gerado, então y=E.
Na FIG. 3.1 está representado um modelo básico genérico, isto é, um HMM
de ‘η’ estados, os quais estão todos ligados entre si por probabilidades de transição
pij nos dois sentidos e cada um deles possui uma probabilidade pi de erro (gerar ‘1’):
4
Onde:
pij = a probabilidade de transição do estado ‘i’ para o estado ‘j’;
pi = a probabilidade de erro (gerar ‘1’) do estado ‘ei’.
Inicialmente tomaremos como referência de modelo básico o modelo de Gilbert-
Elliott, o qual constitui-se de um HMM de dois estados, um deles dito estado bom
(G) e o outro estado ruim (B), onde o primeiro apresenta baixa probabilidade de erro
(pg) e o segundo alta probabilidade de erro (pb). A FIG. 3.2 apresenta o diagrama de
estados deste modelo.
Onde:
PB = Prob. de transição do estado G para o B
PG = Prob. de transição do estado B para o G
4
pb = Prob. de erro (emitir 1) do estado B
pg = Prob. de erro (emitir 1) do estado G
O item 3.1.5 apresenta o diagrama de estados do modelo derivado, para L = 3,
correspondente ao modelo básico de Gilbert-Elliot apresentado neste item.
3.1.3 TABELA DE TRANSIÇÃO DE ESTADOS DO MODELO DERIVADO
A TAB. 3.1 relaciona todos os possíveis estados atuais com todas as possíveis
entradas, apresentando os correspondentes estados futuros e cada uma das
respectivas expressões para cálculo das probabilidades de transição do modelo
derivado, as quais dependem não só das entradas, mas também dos estados atuais.
A última coluna apresenta as expressões para cálculo dos índices dos elementos da
matriz de transição do modelo derivado (descrita no item seguinte), em função dos
índices dos elementos da matriz de transição do modelo básico, esta coluna será útil
no futuro auxiliando na construção e implementação em computador da matriz de
transição.
Estado Atual Entrada Estado Futuro Prob. de Transição Elemento
(ei,x) (ej,1) (ej,0) pij.pi ai+k.η,j k=0 ... L
(ei,y) (ej,y+1) ai+k.η+s,j+(k+1).η k=0 ... L-1 s=0 para k≤L-1
(ei,L-1) (ej,0) (ej,E) pij.(1-pi)
(ei,E) (ej,E) s= η para k =L-1
(ei,y) (ej,x) (ej,z >y+1) 0 Outros casos.
TAB. 3.1: Tabela de transição para o modelo derivado.
3.1.4 MATRIZ DE PROBABILIDADES DE TRANSIÇÃO
Baseado nos parâmetros do modelo básico e na definição dos estados e das
entradas do modelo derivado representados na TAB. 3.1, podemos construir a
4
estrutura da matriz de probabilidades de transição, a qual a partir deste ponto nos
referiremos simplesmente como matriz de transição. Observa-se que só são
possíveis as transições dos estados (X,y-1) para (X,y), onde 1≤y≤L-1; (X,L-1) ou
(X,E) para (X,E) e de qualquer estado para (X,0), onde X, representa estado do
modelo básico. Os elementos da matriz correspondentes as transições restantes são
portanto, nulos.
A organização dos estados em ordem crescente do segundo parâmetro y, nas
linhas e nas colunas da matriz é uma das maneiras que permite a dedução de
expressões simples para os índices de seus elementos. A seguir é mostrado a
estrutura geral de uma matriz de transição para um critério de comprimento de surto
L, e cuja célula básica possui ‘η’ estados:
e1,0 e2,0 … eη,0 e1,1 e2,1 … eη,1 . . . e1,L-1 e2,L-1 … eη,L-1 e1,E e2,E … eη,E
e1,0 a11 a12 a1η a1,η+1 a1,η+2 a1,η+η 0 0 0 0 0 0 0 e2,0 a21 a22 a2η a2,η+1 a2,η+2 a2,η+η 0 0 0 0 0 0 0 . . . 0 0 0 0 0 0 0 eη,0 aη1 aη2 aηη aη,η+1 aη,η+2 aη,η+η 0 0 0 0 0 0 0 e1,1 a11 a12 a1η 0 0 0 0 . 0 0 0 0 e2,1 a21 a22 a2η 0 0 0 0
. 0 0 0 0
. . . 0 0 0 0 . 0 0 0 0 eη,1 aη1 aη2 aηη 0 0 0 0 . 0 0 0 0
. . . . 0 0 0 0
. . . . . 0 0 0 0
. . . . . 0 0 0 0 e1,L-1 a11 a12 a1η 0 0 0 0 0 0 0 a1,η+1 a1,η+2 a1,η+η
e2,L-1 a21 a22 a2η 0 0 0 0 0 0 0 a2,η+1 a2,η+2 a2,η+η
. . . 0 0 0 0 0 0 0 eη,L-1 aη1 aη2 aηη 0 0 0 0 … 0 0 0 aη,η+1 aη,η+2 aη,η+η
e1,E a11 a12 a1η 0 0 0 0 0 0 0 a1,η+1 a1,η+2 a1,η+η
e2,E a21 a22 a2η 0 0 0 0 0 0 0 a2,η+1 a2,η+2 a2,η+η
. . . 0 0 0 0 0 0 0 eη,E aη1 aη2 aηη 0 0 0 0 0 0 0 aη,η+1 aη,η+2 aη,η+η
Podemos observar na matriz, a repetição dos valores das probabilidades dos ηx2η
elementos correspondentes às η primeiras linhas e às 2η primeiras colunas em
outros elementos e o restante dos elementos nulos. Sendo que o número máximo de
probabilidades não nulas distintas (NP), que se repetem é o produto de η por 2η,
então:
NP = 2. η2 (3.2)
4
Agora particularizaremos a matriz de transição tomando-se como modelo básico,
o modelo de 2 estados (η=2) de Gilbert-Elliott, mantendo-a genérica quanto ao L.
Da EQ. 3.1, o número de estados desta matriz de transição é dado por
N=2(L+1), e da EQ. 3.2, o número de probabilidades distintas que podem ocorrer
para este caso é NP = 8. Assim, para este caso a matriz de transição possui a
seguinte estrutura:
Em seguida podemos deduzir cada uma destas 8 probabilidades de transição e
atribuí-las aos correspondentes elementos da matriz de transição de estados, como
descrito na TAB. 3.2.
Elemento Probabilidade de transição Elemento a (1-PB)pg a2k-1,1 onde:
k = 1, 2,…,L+1
b PB.pg a2k-1,2
c PG.pb a2k,1
d (1-PG).pb a2k,2
e (1-PB)(1-pg) a2k-1+S,3+2(k-1) onde: k = 1, 2,…,L S = 0, se k≤L S = 2, se k=L
f PB.(1-pg) a2k-1+S, 4+2(k-1)
g PG.(1-pb) a2k+S, 3+2(k-1)
h (1-PG).(1-pb) a2k+S, 4+2(k-1)
TAB. 3.2: Tabela de transição simplificada para modelo básico de 2 estados (η=2).
3.1.5 DIAGRAMA DE ESTADOS
G,0 B,0 G,1 B,1 G,2 B,2 G,E B,E
G,0 a b e f 0 0 . . . 0 0
B,0 c d g h 0 0 . . . 0 0
G,1 a b 0 0 e f . . . 0 0
B,1 c d 0 0 g h . . . 0 0
. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
G,L-1 a b 0 0 0 0 . . . e f
4
Para representar o diagrama de estados do modelo derivado, exemplifica-se
com um modelo básico de Gilbert-Elliott, para L=3. Observa-se na FIG. 3.3, que os
estados (X,0) recebem transições de todos os estados, pois de qualquer estado, o
sistema pode gerar o bit ‘1’, e assim passar a condição de ter uma quantidade nula
de ‘0’s após este ‘1’, que foi o último “1” gerado.
3.2 CÁLCULO DAS DISTRIBUIÇÕES DE PROBABILIDADES DOS PARÂMETROS
COMPRIMENTO DE SURTO E INTERVALO ENTRE SURTOS
FIG. 3.3: Diagrama de estados para um modelo originado de um modelo de Gilbert-Elliott, para L=3.
4
Apresenta-se a seguir a dedução das probabilidades de ocorrer um surto de
tamanho ‘k’ e de ocorrer um intervalo entre surtos de tamanho ‘k’, possibilitando
assim o cálculo das respectivas distribuições, fixado o valor do parâmetro L.
3.2.1 COMPRIMENTO DE SURTO
Seja Ω o conjunto de todos os N estados do modelo derivado.
Sejam os conjuntos A = (X,E) e B = (X,0), subconjuntos do conjunto Ω.
Admitindo que um surto começa no instante n, tem-se:
qn-1 ∈ A e qn ∈ B (3.3)
Este surto terá tamanho k se:
qn+i ∉ A para i = 1 até k+L-2, e (3.4)
qn+k+L-1 ∈ A (3.5)
sendo: qn o estado do modelo básico no tempo n.
Exemplo: Para L=3, seja um surto de tamanho 7 iniciando no tempo n, como
representado a seguir:
...
xn
xn+1
xn+2
.
.
.
.
.
xn+k+L-2
xn+8
xn+k+L-1
xn+9
...
... 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 ...
Fora de surto Surto de tamanho 7 L = 3 Fora de surto
sendo: xn o bit gerado no tempo n.
Portanto, dado que o surto se inicia no instante n, a probabilidade de que este surto
tenha tamanho k, é dada por:
)];(|;[)],([ 1
2
1
1 AxBxAxAxPLkCP nn
Lk
i
inLkn ∈∈∉∈= −
−+
=
+−++ I (3.6)
3.2.2 INTERVALO ENTRE SURTOS
5
Sejam os conjuntos A = (X,E), B = (X,0) e C = (X,L-1), subconjuntos do
conjunto Ω.
Admitindo que um intervalo entre surtos começa no instante n, tem-se:
qn-1 ∈ C e qn ∈ A (3.7)
Se este intervalo entre surtos tem tamanho k (k ≥ L), então:
qn+i ∈ A para i = 1 até k-L e (3.8)
qn+k-L+1 ∈ B (3.9)
Exemplo: Para L=3, seja um intervalo entre surtos de tamanho 7 iniciando no tempo
n, como representado a seguir:
...
xn
xn+1
xn+2
.
.
xn+k-L+1
xn+5
...
... 1 0 0 0 0 0 0 0 1 ...
surto L = 3
Intervalo de tamanho 7
surto
A probabilidade de ocorrer um intervalo entre surtos de tamanho ‘k’ é, portanto dada
por:
)];(|;[)],([ 1
1
1 CxAxAxBxPLkIP nn
Lk
i
inLkn ∈∈∈∈= −
−
=
++−+ I (3.10)
3.2.3 CÁLCULO RECURSIVO DAS PROBABILIDADES P[C(K,L)] E P[I(K,L)]
As probabilidades em questão são casos particulares da seguinte probabilidade
geral, a qual será desenvolvida a seguir, visando a obtenção de um algoritmo
recursivo para o seu cálculo:
)];(|;[)( 1
1
1
WxVxUxUxPM nn
M
i
inMn ∈∈∈∈= −
−
=
++ Iαλ (3.11)
Sendo: Uα , U, V e W subconjuntos fixos de Ω (conjunto de todos os estados).
Expressando λ(M) através de uma probabilidade da interseção, temos:
5
);;;();(
1)( 1
1
11
WxVxUxUxPWxVxP
M nn
M
i
inMn
nn
∈∈∈∈⋅∈∈
= −
−
=
++
−
Iαλ (3.12)
Expandindo as probabilidades do numerador e denominador da expressão acima em
somatórios nos respectivos subconjuntos:
∑ ∑∑ ∑ ∑∑∑∑ ∈ ∈ ∈ ∈ ∈ ∈
−
−
=
++
∈ ∈− −
====⋅==
=αα
αλU Uu Uu Uu Vv Ww
nni
M
i
inMn
Vv Ww
nn M
wxvxuxxPwxvxP
M1 2 1
);;;(....);(
1)( 1
1
11
I
(3.13)
usando as notações: ∑ ∑∑∈ ∈
=VW Vv Ww
e ∑ ∑ ∑∑∑∈ ∈ ∈ ∈
=αα U Uu Vv WwUVW 1
....
e aplicando a regra da cadeia nas probabilidades da EQ. 3.13 obtemos:
)()|(
);|();;|(
);;|()()|(
1)(
11
1111
2
1
11
1
1
111
wxPwxvxP
wxvxuxPwxvxuxuxP
wxvxuxxPwxPwxvxP
M
nnn
nnnnni
M
i
inMMn
UVW
nni
M
i
inMn
VW
nnn
===
⋅===⋅⋅====
⋅====⋅===
=
−−
−+−
−
=
+−−+
−
−
=
++
−−
∑∑
LI
Iαλ
(3.14)
Supondo-se este processo ser Markov de 1a ordem, obtemos a simplificação dos
fatores que compõem cada parcela da soma do numerador da EQ. 3.14:
)()|()|()|(
)|()()|(
1)(
11112211
11
11
wxPwxvxPvxuxPuxuxP
uxxPwxPwxvxP
M
nnnnnMMnMMn
UVW
MMnMn
VW
nnn
===⋅==⋅⋅==
⋅==⋅===
=
−−+−−+−−+
−−++
−−
∑∑
L
αλ
(3.15)
5
Podemos observar a EQ. 3.15 como sendo o produto de um vetor de dimensão N
contendo como elementos os estados iniciais do sistema (último fator da EQ. 3.15),
por M+1 matrizes com mesma dimensão da matriz de transição (NxN), cujos
elementos diferentes de zero são iguais aos correspondentes na matriz de transição.
No entanto, os elementos das linhas e das colunas que não correspondam aos
subconjuntos dos estados de partida (estado atual) e de chegada (próximo estado)
respectivamente, são iguais a zero. Ou seja, as matrizes em questão, equivalem a
matriz de transição afetada por uma máscara de zeros conveniente. Assim sendo,
podemos gerar a seguinte indução matemática:
1
2
1
)()(
1)( PAAAAP
PAPM u
M
uuvuwvw
wvw
⋅⋅
= −αλ (3.16)
1
3
1
)()(
1)1( PAAAAP
PAPM u
M
uuvuwvw
wvw
⋅⋅
=− −αλ (3.17)
definindo: )()(
1)( 2
1
−
⋅= M
uuvuwvw
wvw
AAAPPAP
Mλ (3.18)
chega-se à seguinte equação recursiva:
uuAMM ⋅−= )1()( λλ (3.19)
Os valores das probabilidades em função de M da EQ. 3.16 podem ser dados então
por:
1])([)( PAMM u ⋅⋅= αλλ (3.20)
Sendo:
Pw = Vetor linha de dimensão N de probabilidades dos estados iniciais do
subconjunto W. Seus elementos correspondentes a estados que não
pertençam a W são nulos;
Axy = Matriz de transição dos estados pertencentes ao subconjunto X para os
pertencentes ao subconjunto Y. As suas linhas e colunas
5
correspondentes a outros estados não pertencentes aos estados X e Y,
respectivamente, possuem elementos nulos;
P1 = Vetor coluna de dimensão N, cujos elementos são iguais a 1.
3.2.3.1 PROBABILIDADE DE COMPRIMENTO DE SURTO
Agora particularizaremos as EQ. 3.19 e 3.20 para calcularmos a expressão
recursiva da probabilidade de comprimento de surto.
Comparando as EQ. 3.6 e 3.11 e fazendo a analogia entre os subconjuntos
empregados nestas duas equações, observa-se que:
W = Uα = A = (X,E) ; V = B = (X,0) e U = (X,0),(X,1),…,(X,L-1) ≠ A (3.21)
F azendo: M=k+L-1 (3.22) definimos a equações para o cálculo daquela probabilidade:
uuAMM ⋅−= )1()( λλ (3.23)
e 1])([)( PAMM uw ⋅⋅= λλ , L ≤ M ≤ k+L-1 (3.24)
Como o menor comprimento possível de surto é 1, o menor valor de M será neste caso L. Assim, a recursão da EQ. 3.16 será i niciada por:
2
1)(
1)( −
⋅= L
uuvuwvw
wvw
AAAPPAP
Lλ (3.25)
3.2.3.2 PROBABILIDADE DE COMPRIMENTO DE INTERVALO ENTRE SURTOS
Particularizaremos a seguir as EQ. 3.19 e 3.20 para o calculo recursivo da
probabilidade de intervalo entre surtos.
5
Comparando as EQ. 3.10 e 3.11 e fazendo a analogia entre os subconjuntos
empregados nestas duas equações, observa-se que:
W = C = (X,L-1) , U = V = A = (X,E) e Uα = B = (X,0) (3.26)
F azendo: M=k-L+1 e (3.27)
voltando à EQ. 3.16, temos
1
2
1
)()(
1)( PAAAAP
PAPM u
M
uuvuwvw
wvw
⋅⋅
= −αλ (3.28)
Aplicando os subconjuntos acima observamos que Avu = Auu e Awv = Awu , logo:
1
1
1
)()(
1)( PAAAP
PAPM u
M
uuwuw
wvw
⋅⋅
= −αλ (3.29)
De forma análoga ao caso do comprimento de surto, definimos as equações para o
cálculo da probabilidade de comprimento de intervalo entre surtos:
uuAMM ⋅−= )1()( λλ (3.30)
1])([)( PAMM u ⋅⋅= αλλ , 1 ≤ M ≤ k-L+1 (3.31)
Como o menor comprimento de intervalo entre surtos possível é L, o menor valor de
M na EQ. 3.27 é igual a 1.
Assim, a recursão da EQ. 3.29 é i
niciada por:
wuw
wvw
APPAP 1)(
1)1(
⋅=λ (3.32)
5
4 RESULTADOS
4.1 SIMULAÇÃO
Foram geradas, por computador, seqüências de bits sujeitas a erros em surtos,
baseadas em um HMM de η estados, simulando o comportamento de um canal com
memória. O algoritmo gera uma seqüência de observações conforme a definição do
item 2.2.2.4.
Foram geradas diversas seqüências de observações, de comprimentos variados
e partindo-se de diferentes modelos (HMM), para posterior levantamento dos
parâmetros comprimento de surto, intervalo entre surtos e densidade de erro por
surto. Este último parâmetro é definido como a razão entre o número de bits errados
de um surto de erros e o comprimento deste surto.
4.1.1 LEVANTAMENTO DO PARÂMETRO COMPRIMENTO DE SURTO
Foi levantada a distribuição do parâmetro comprimento de surto de uma
seqüência de observações, por meio de um algoritmo que recebe como parâmetros
de entrada uma seqüência de observações e L, definido no item 1.1, retornando o
número de surtos; uma tabela com as freqüências absolutas e relativas dos
comprimentos de surto; sua média, variância, assimetria, curtose e um gráfico de
sua distribuição de probabilidades estimadas.
Foi gerado um bloco de 500 Kbytes com surtos de erro, pelo modelo de Gilbert-
Elliott definido pelos seguintes parâmetros:
PG = 0,85 pg = 0,05
PB = 0,32 pb = 0,92
para: L= 3, L= 5 e L= 7
apresentando os resultados da Fig. 4.1. Observa-se que para pequenos valores de
L, os eventos podem ser separados em múltiplos surtos pequenos, reduzindo assim
o comprimento médio dos surtos. O contrário acontece para grandes valores de L,
5
onde eventos separados são combinados em uma menor quantidade de surtos de
maior comprimento. Na TAB. 4.1 podemos observar alguns parâmetros estatísticos
dos comprimentos de surtos para os três casos, onde são apresentados o número
total de surtos, média, variância, assimetria e curtose, para cada um dos valores de
L.
Observa-se na FIG. 4.1 que o aumento de L, por acarretar a união de surtos
menores formando surtos maiores, causa uma diminuição da freqüência relativa dos
surtos menores e um aumento da freqüência relativa dos surtos maiores, causando,
portanto, uma redução em módulo da inclinação da direção geral da curva.
FIG. 4.1: Comparação entre as distribuições do parâmetro comprimento de surto, levantada para ‘L’s diferentes, a partir de um mesmo bloco.
L = 3 L = 5 L = 7
No de Surtos 430837 197667 90807
Média 4,405 13,615 35,993
Variância 19,177 199,438 1353,20
Assimetria 2,063 2,033 2,001
Curtose 9,215 9,229 9,069
5
Nota-se que apesar do aspecto mais comum das curvas de distribuição do
parâmetro comprimentos de surto ser como o apresentado nas curvas da FIG. 4.1,
este pode variar bastante com a variação dos parâmetros, como pode ser visto nas
FIG. 4.5 e 4.6.
4.1.2 LEVANTAMENTO DO PARÂMETRO INTERVALO ENTRE SURTOS
Foi levantada a distribuição do parâmetro intervalo entre surtos de uma
seqüência de observações, por meio de um algoritmo que recebe como parâmetros
de entrada uma seqüência de observações e o número L, definido no item 1.1,
retornando o número de intervalos entre surtos; uma tabela com as freqüências
absolutas e relativas dos intervalos entre surtos; sua média, variância, assimetria,
curtose e um gráfico de sua distribuição de probabilidades estimadas.
Foi gerado um bloco de 500 Kbytes com surtos de erro, pelo modelo de Gilbert-
Elliott definido pelos seguintes parâmetros:
PG = 0,85 pg = 0,05
PB = 0,32 pb = 0,92
para: L= 3, L= 5 e L= 7
apresentando os resultados da FIG. 4.2, onde pode-se observar o paralelismo das
curvas. Na TAB. 4.2 podemos observar alguns parâmetros estatísticos dos
intervalos entre surtos, onde é apresentado o número total de intervalos entre surtos,
média, variância, assimetria e curtose, para cada um dos valores de L.
5
Apesar das curvas de distribuição do parâmetro intervalo entre surtos apresentar, o
aspecto mostrado pelas curvas da FIG. 4.2, este pode variar com a variação dos
parâmetros.
4.1.3 DENSIDADE DE ERRO POR SURTO
FIG. 4.2: Comparação entre as distribuições do parâmetro intervalo entre surtos, levantada para ‘L’s diferentes de um mesmo bloco.
L = 3 L = 5 L = 7
No de Intervalos 430836 197666 90806
Média 5,102 7,107 9,114
Variância 6,559 6,586 6,606
Assimetria 2,054 2,055 2,060
Curtose 9,300 9,314 9,357
5
Foi realizado o levantamento do parâmetro densidade de erros por surto,
através de um algoritmo que recebe uma seqüência de observações e o critério de
comprimento de surto L e calcula a densidade de bits errados em cada surto de erro;
tira as médias das densidades para surtos de mesmo comprimento e então plota o
gráfico (Densidade de erro por surto) X (Comprimento de surto).
Com um bloco de 1 Mbyte, com surtos de erro, pelo modelo de Gilbert-Elliott
definido pelos seguintes parâmetros:
PG = 0,75 pg = 0,04
PB = 0,007 pb = 0,93
Foi levantada a distribuição do parâmetro densidade de erro por surto para L = 3,
que é mostrada na FIG. 4.3. A seguir são apresentados alguns parâmetros
estatísticos obtidos destes dados:
Número de surtos de erro = 605342
Comprimento médio de surto = 3.868
Taxa de erro de bits do bloco = 0.243
Densidade média de erro por surto = 0.926
Variância das densidades = 0.020
6
4.2 MODELO DERIVADO
Serão aqui apresentados alguns resultados obtidos da implementação em
computador do modelo derivado, proposto no capítulo 3. Serão apresentadas
também as distribuições de probabilidades calculadas, dos parâmetros
“comprimento de surto” e “intervalo entre surtos”, inicialmente tomando-se como
modelo básico, o modelo de Gilbert-Elliott. Em seguida, são apresentados resultados
baseados em um modelo básico de 3 estados. Por fim serão apresentadas
comparações entre os resultados levantados dos dados simulados e os calculados
pelo modelo derivado.
4.2.1 DISTRIBUIÇÃO CALCULADA DOS COMPRIMENTOS DE SURTOS
Foram geradas e comparadas três curvas de distribuição para 3 valores
diferentes de L. O modelo básico utilizado foi um HMM de Gilbert-Elliott com os
FIG. 4.3: Distribuição do parâmetro densidade de erro por surto média, para L=3.
6
mesmos parâmetros da simulação da FIG. 4.1. Observou-se, que as curvas
calculadas apresentaram o mesmo comportamento do que a simulação, como está
mostrado na FIG. 4.4.
FIG. 4.4: Comparação entre as distribuições calculadas do parâmetro comprimento de surto, para probabilidades de transição fixas e L diferentes.
Como já mencionado no item 4.1.1, a curva de distribuição pode variar bastante com
os parâmetros do HMM. A FIG. 4.5 mostra que as curvas de distribuição do
parâmetro comprimento de surto, calculada e estimada, apresentam um
comportamento semelhante a uma oscilação amortecida. Os parâmetros do HMM
deste experimento são:
PG = 0,95 pg = 0,05
PB = 0,60 pb = 0,98 e L = 2
6
Nota-se que os fatores que influenciam este comportamento oscilatório, são os
valores de ambas as probabilidades de transição para o estado bom e para o estado
ruim serem altas e ainda, a probabilidade de erro do estado bom ser baixa e a
probabilidade de erro do estado ruim ser alta. Este fato é realçado pelas curvas de
distribuição de comprimentos de surtos, calculada e simulada mostrada na FIG. 4.6,
cujo HMM que as modelaram possui parâmetros com valores extremos nas
condições descritas acima, como a seguir:
PG = 0,99 pg = 0
PB = 0,99 pb = 1 para L = 2 e
O tamanho do bloco simulado foi de 1,5 Mbytes
FIG. 4.5: Comportamento das distribuições calculadas e estimadas do parâmetro comprimento de surto.
6
FIG. 4.6: Comportamento da curva de distribuição dos comprimentos de surto gerada pelo modelo de Gilbert-Elliott para PG e PB próximos da unidade.
4.2.1.1 VARIAÇÃO DA INCLINAÇÃO DA CURVA DE DISTRIBUIÇÃO COM L
Observa-se que para valores de L grandes, a curva de distribuição dos
comprimentos de surtos se estabiliza numa exponencial, a qual numa escala
semilogarítmica (ordenadas), é representada por uma reta. Foi levantada em
computador a curva dos coeficientes angulares destas retas, versus L. Observa-se
na FIG. 4.7 que a inclinação dessas retas diminui em valor absoluto com o aumento
de L, tendendo a um valor constante para valores de L grandes. A variação de L
afeta de uma maneira complexa a distribuição deste parâmetro, pois um aumento de
L ocasiona o desaparecimento de surtos menores, que se juntam para formar surtos
maiores, ou seja, a curva de distribuição começa a pesar mais para maiores valores
de L e menos para os menores valores, daí a variação de inclinação. A matriz de
6
transição e o vetor das probabilidades de erro definidores do modelo básico utilizado
no experimento da FIG. 4.7 foram:
=
78.022.0
45.055.0A e [ ]05.092.0=P , respectivamente. (4.1)
FIG. 4.7: Curva coeficiente angular x L para a distribuição de comprimento de surto.
4.2.2 COMPORTAMENTO INICIAL DA DISTRIBUIÇÃO DOS COMPRIMENTOS
Em seguida, podemos observar nas FIG. 4.8 (a e b) para o modelo de Gilbert-
Elliott, que apesar do comportamento geral desta distribuição ser visivelmente uma
exponencial (reta na escala semilogarítmica), de uma maneira geral, os
comprimentos iniciais da distribuição fogem a esta regra. O surto de comprimento
K=1 tem uma alta probabilidade de ocorrência, estando acima da exponencial,
enquanto o de comprimento K=2 está abaixo da exponencial. A partir daí, como num
6
movimento oscilatório amortecido, a curva converge para a exponencial. Este
comportamento está representado nas FIG. 4.8 (a, b) pelas curvas de distribuições
calculadas e estimadas dos comprimentos de surtos para os primeiros valores de K.
Em cada distribuição empregou-se o mesmo HMM que gerou o bloco de
observações, para o cálculo pelo modelo derivado, visando o ajuste das curvas, o
qual foi conseguido satisfatoriamente.
Para o experimento da FIG. 4.8 (a), foi gerado um bloco de 500 Kb por um HMM
com os seguintes parâmetros:
PG = 0,91 pg = 0,01
PB = 0,57 pb = 0,89 e L = 2
Para o experimento da FIG. 4.8 (b), foi gerado um bloco de 500 Kb por um HMM
com os seguintes parâmetros:
PG = 0,85 pg = 0,05
PB = 0,32 pb = 0,92 e L = 3
6
4.2.3 DISTRIBUIÇÃO CALCULADA DOS INTERVALOS ENTRE SURTOS
a)
6
Foram geradas e comparadas três curvas de distribuição para 3 valores
diferentes de L. O modelo básico utilizado foi um HMM de Gilbert-Elliott com os
mesmos parâmetros da simulação da FIG. 4.2. Observou-se, que as curvas
calculadas apresentaram o comportamento representado na FIG. 4.9.
Com relação aos coeficientes angulares das curvas de distribuição das
probabilidades do parâmetro intervalo entre surtos, deve-se notar que estes não
variam com L, como mostra a FIG. 4.9. Este comportamento é intuitivamente
previsível, já que neste caso, o aumento de L, apenas suprime mais alguns dos
primeiros valores da distribuição, ficando inalteradas as freqüências absolutas a
partir deste valor e conseqüentemente ficando as correspondentes freqüências
relativas aumentadas por um mesmo fator, devido à diminuição do número de
intervalos possíveis. Deve ser ressaltado que os intervalos suprimidos, eram os que
FIG. 4.9: Comparação entre as distribuições calculadas do parâmetro intervalo entre surtos, para probabilidades de transição fixas e L diferentes.
6
possuíam as mais altas probabilidades, o que reforça mais ainda o deslocamento
paralelo das curvas com o aumento de L.
4.3 COMPARAÇÃO ENTRE SIMULAÇÃO E MODELO PROPOSTO
A fim de comprovar a eficiência do modelo derivado, quanto ao levantamento
das distribuições dos parâmetros comprimento de surto e intervalo entre surtos, são
realizadas comparações entre os resultados obtidos por meio de cálculos com o
modelo e os obtidos por meio de simulações.
A partir de uma seqüência simulada de observações, sujeitas a erros em surtos,
geradas por um HMM conhecido, levanta-se as curvas de distribuições dos
parâmetros comprimento de surto e intervalo entre surtos. Baseado no modelo
derivado, calcula-se as curvas correspondentes, tomando-se para modelo básico um
mesmo HMM que gerou a seqüência de observações. O objetivo deste experimento
é o de avaliar a precisão dos resultados e o tempo de processamento de cálculo do
modelo derivado, quando este é comparado com a simulação.
Pode se observar nas FIG. 4.10, 4.11, 4.12, que as curvas calculadas pelo
modelo se ajustam satisfatoriamente às curvas obtidas do levantamento desses
parâmetros do bloco de dados simulado. Nos três experimentos procurou-se variar
os parâmetros do HMM gerador da seqüência de observações, também usado como
modelo básico do modelo derivado empregado nos cálculos das distribuições.
Para o experimento relativo a FIG. 4.10, o tamanho da seqüência de
observações foi de 500 Kbytes e os parâmetros do HMM empregados nas
distribuições foram:
PG = 0,91 pg = 0,01
PB = 0,57 pb = 0,89 e L = 3
6
FIG. 4.10: Comparação entre simulação e modelo para L=3.
Observa-se, na FIG. 4.11, que mudanças nos valores dos parâmetros do HMM
e de L não alteram o ajuste da simulação pelo modelo em termos de precisão. Para
este experimento, o tamanho da seqüência de observações foi de 500 Kbytes e os
parâmetros do HMM empregados nas distribuições foram:
PG = 0,85 pg = 0,05
PB = 0,32 pb = 0,92 e L = 4
7
FIG. 4.11: Comparação entre simulação e modelo para L=4.
Observa-se na FIG. 4.12, que a redução em módulo da inclinação da curva
estimada dos comprimentos de surtos e o deslocamento paralelo da curva estimada
dos intervalos entre surtos devido ao aumento de L (em relação ao experimento
anterior), são perfeitamente acompanhados pelas curvas calculadas da modelagem
proposta. O aumento do L, provoca o surgimento de surtos maiores, aumentando
sua probabilidade, ao mesmo tempo em que diminui a probabilidade dos surtos
menores, justificando, portanto o aumento da inclinação da curva de distribuição dos
comprimentos de surtos. A maior dispersão dos pontos das curvas estimadas neste
experimento, em relação ao experimento anterior, é devida a diminuição da
seqüência de observações.
Para o experimento relativo a FIG. 4.12, o tamanho da seqüência de
observações foi de 100 Kbytes e os parâmetros do HMM empregados nas
distribuições foram:
7
PG = 0,85 pg = 0,05
PB = 0,32 pb = 0,92 e L = 10
4.3.1 COMPARAÇÃO ENTRE OS TEMPOS DE PROCESSAMENTO
Comparando-se o tempo de análise de uma seqüência de observações
simulada, afetada por erros em surtos, de tamanho 350 Kbytes, gerada por um HMM
com os seguintes parâmetros:
PG = 0,62 pg = 0,08
PB = 0,47 pb = 0,83 e L = 3,
FIG. 4.12: Comparação entre simulação e modelo para L=10.
7
com o tempo de cálculo pela modelagem proposta, observou-se que o segundo
método além de preciso é muitas vezes mais rápido do que o primeiro, como
apresentado na TAB. 4.3:
Tempos (seg.) Parâmetro Obtido
Simulação
(Ts)
Modelagem
(Tm)
Tempo relativo
(Ts/Tm)
Comprimento de surto
308,25
0,06
5138
Intervalo entre Surtos
337,08
0,06
5618
TAB. 4.3: Tempos de processamento.
Deve-se notar que nos tempos de simulação da TAB. 4.3, não foram
computados o tempo de geração da seqüência de observações, o qual dependerá
do tamanho do bloco gerado. Foram computados somente os tempos de
levantamento daqueles parâmetros, os quais aumentariam razoavelmente com a
inclusão do tempo de simulação das observações.
O computador utilizado foi um Pentium II 300 MHz.
4.4 MODELO BÁSICO HMM DE 3 ESTADOS
A representação do HMM que tomaremos como modelo básico, cujos estados
classificaremos como bom (G), médio (M) e ruim (B), está representado na FIG.
4.13, sendo que, a sua matriz de transição e o seu vetor de probabilidades de erro
dos estados são respectivamente os seguintes:
=
50.045.005.0
28.032.040.0
03.037.060.0
A e [ ]70.026.004.0=P (4.2)
7
As distribuições dos parâmetros comprimento de surto e intervalo entre surtos,
calculados pelo modelo derivado e as levantadas de um bloco simulado de 300
kbytes, todas baseadas no HMM definido pelas matrizes em 4.2, estão
representadas para L=4 nas FIG. 4.14 e 4.15, respectivamente.
A FIG. 4.14 mostra que a curva de distribuição dos comprimentos de surtos
calculada pelo modelo derivado ajustou-se precisamente a curva gerada pela
seqüência de observações estimada pelo HMM de 3 estados.
FIG. 4.14: Distribuição dos comprimentos entre surtos para um modelo básico de 3 estados.
7
A FIG. 4.15 mostra que a curva de distribuição dos intervalos de surtos
calculada pelo modelo derivado ajustou-se precisamente a curva gerada pela
seqüência de observações estimada pelo HMM de 3 estados.
4.5 MODELO BÁSICO DE FRITCHMAN-SES DE 3 ESTADOS
Agora geramos, por simulação, uma seqüência de observações de tamanho
500 KBytes, baseado no modelo de Fritchman-SES (definido no item 2.2.5) de 3
estados, comparando as distribuições de comprimento de surto e intervalo entre
surtos levantadas desta seqüência, com as calculadas pela modelagem proposta
com o correspondente modelo de Fritchman como modelo básico. A FIG. 4.16
apresenta o referido modelo básico e as FIG. 4.17 e 4.18 apresentam as curvas de
FIG. 4.15: Distribuição dos intervalos entre surtos para um modelo básico de 3 estados.
7
distribuição de probabilidades obtidas. A matriz de transição e o vetor das
probabilidades de erro dos estados estão representados a seguir:
=
6,025,015,0
10,090,00
15,0085,0
A e [ ]100=P (4.3)
Observe nas matrizes 4.3 que o vetor P das probabilidades de erro dos estados
indica probabilidade de erro zero para os dois estados bons e 1 para o estado ruim,
o que torna este modelo uma cadeia de Markov observável em relação ao estado
ruim.
A FIG. 4.17 apresenta a distribuição do parâmetro comprimento de surto
levantada a partir de um bloco de dados de 500Kb simulado e a calculada pelo
modelo derivado, ambas com base no modelo definido pelas matrizes em 4.3, para
diferentes valores de L.
A TAB. 4.4 apresenta alguns resultados estatísticos complementares deste
experimento. Observa-se que o aumento de L, por formar surtos maiores, o número
de surtos diminui, enquanto a média dos comprimentos de surto e a variância
aumentam.
Origem L No de surtos Média Variância Assimetria Curtose Tempo Comput. (seg.)
Ts Ts/Tm
7
simulação
3
282720 3,635 10,657 2,060 9,074 489,05 1286,9
modelo
______
3,637
10,693
2,080
9.274
Tm
0,38
simulação
7
172509
8,727
83,992
2,062
9,349
Ts Ts/Tm 620,10
2818,6
modelo
______
8,735
84,143
2,005
8,476
Tm
0,22 TAB. 4.4: Estatística para o parâmetro comprimento de surto, baseado no modelo de Fritchman-SES de 3 estados.
FIG. 4.17: Distribuições dos comprimentos de surto simuladas e calculadas, com base no modelo de Fritchman-SES de 3 estados.
Foi observado que para este tipo de modelo, as curvas de distribuição dos
comprimentos de surtos apresentam um ponto de quebra na abscissa
7
correspondente ao comprimento L+1, o que podemos observar com mais detalhes
na FIG. 4.18, onde são mostradas quatro curvas para L diferentes, definidas pelos
parâmetros das matrizes 4.3.
Analogamente ao caso anterior, a FIG. 4.19 apresenta a distribuição do
parâmetro intervalo entre surtos levantada do mesmo bloco e a calculada pelo
modelo derivado, ambas com base no modelo definido pelas matrizes em 4.3, para
diferentes valores de L.
A TAB. 4.5 apresenta alguns resultados estatísticos complementares deste
experimento. Observa-se que o aumento de L, por suprimir intervalos menores, o
número de intervalos diminui, enquanto a média dos comprimentos dos intervalos
entre surtos e a variância aumentam.
FIG. 4.18: Distribuições dos comprimentos de surto simuladas e calculadas, com base no modelo de Fritchman-SES de 3 estados, para ‘L’s diferentes.
7
Origem L No de Intervalos
Média Variância Assimetria Curtose Tempo Comput. (seg.)
simulação
3
282720
10,853
74,525
2,182
10,467
Ts Ts/Tm 508,83
10177 modelo
______
10,836
74,105
2,150
9,919
Tm
0,05
simulação
7
172509
15,017
76,875
2,166
10,374
Ts Ts/Tm 505,59
10112
modelo
______
15,004
76,728
2,149
10,054
Tm
0,05 TAB. 4.5: Estatística para o parâmetro intervalo entre surtos, baseado no modelo de Fritchman-SES de 3 estados.
7
4.6 MODELAGEM DE UM CANAL SIMULADO DE HF
Para tentar avaliar o comportamento da modelagem em dados que em princípio
não foram gerados por HMM, foi gerada uma seqüência de observações de
aproximadamente 1Mb, obtida da simulação de um canal de HF classificado pelo
CCIR conforme a TAB. 4.6 como “canal bom”. Desta seqüência levantou-se as
distribuições dos parâmetros comprimento de surto, intervalo entre surtos e algumas
estatísticas complementares. Para esta simulação, empregou-se o modelo de
Watterson para um sistema de comunicações em HF e portanto se constituindo
como um canal sujeito a erros em surtos. A princípio nenhuma estatística do canal é
conhecida o qual supomos poder ser representado por algum HMM. A partir daí
estimaremos seus parâmetros utilizando o algoritmo de Baum-Welch. Em seguida
tomaremos o HMM estimado como modelo básico do modelo derivado, pelo qual
FIG. 4.19: Distribuições dos intervalos entre surtos simuladas e calculadas, com base no modelo de Fritchman-SES de 3 estados.
8
calcularemos as distribuições dos parâmetros comprimento de surto e intervalo entre
surtos e compararemos com as respectivas distribuições levantadas dos dados, a
fim de observar a precisão com que aquele modelo representa o referido canal de
HF.
O CCIR estabeleceu condições para o emprego do modelo de Watterson, as
quais largamente utilizadas e procuram retratar as condições reais do canal em
questão. Estas condições consistem em dois percursos independentes de igual
amplitude representando reflexões em diferentes camadas da ionosfera, cujos
parâmetros estão detalhados na TAB. 4.6. (MELO, 2000).
Descrição do Canal
Espalhamento de retardo para 2 percursos de igual
potência (seg)
Freqüência de Deslocamento Doppler para cada percurso (Hz)
BOM
0,5 x 10-3
0,1
MODERADO
1,0 x 10-3
0,5
RUIM
2,0 x 10-3
1,0
TAB. 4.6: Parâmetros da CCIR para simulação de condições do canal de HF.
A seguir serão apresentados os resultados de modelagens com alguns HMM
diferentes, com o objetivo de encontrar aquela que melhor representa aquele canal
de HF.
4.6.1 MODELAGEM PELO MODELO DE GILBERT-ELLIOTT
Admitindo inicialmente, que as curvas de distribuição dos comprimentos de
surtos e dos intervalos entre surtos, levantadas da simulação do canal de HF
possam ser ajustados pelo modelo de Gilbert-Elliott, submeteu-se estes dados ao
algoritmo de Baum-Welch para estimação de parâmetros de HMM de dois estados,
encontrando-se a seguinte matriz de transição e vetor de probabilidades de erro dos
estados:
8
=
9675,00325,0
2325,07675,0A e [ ]0005,05208,0=P (4.4)
O que, em relação à definição particular para HMM de 2 estados, equivale à:
PG = 0,2325 pg = 0,0005
PB = 0,0321 pb = 0,5208 (4.5)
Com o modelo básico definido por 4.4, foram geradas as curvas de distribuição
dos parâmetros comprimento de surto e intervalo entre surtos e comparadas com as
simulações do canal de HF, as quais são apresentadas pelas FIG. 4.20 e 4.21,
respectivamente.
8
Observa-se que ao ser empregado para representar o canal de HF, o modelo de
Gilbert-Elliot, apesar de ter ajustado razoavelmente a distribuição de comprimentos
de surtos, deixa a desejar no que diz respeito, ao parâmetro intervalo entre surtos,
que neste caso apresentou um comportamento oscilatório das probabilidades.
FIG. 4.20: Distribuições dos comprimentos de surtos levantadas da Simulação do canal de HF e calculadas pela modelagem baseada em um modelo básico de Gilbert-Elliott, cujos parâmetros foram estimados.
8
4.6.2 ESTIMAÇÃO DE PARÂMETROS PELO MODELO DERIVADO
Aqui o modelo derivado é empregado para se tentar estimar parâmetros de
dados que em princípio não foram gerados por HMM. O método consiste em ajustar
a curva de distribuição de probabilidades calculadas do parâmetro considerado pela
correspondente curva levantada dos dados. Supondo que os dados possam ser
representados por um HMM, é realizada uma otimização dos parâmetros deste
HMM no sentido de se obter o melhor ajuste entre as curvas pelo critério dos
mínimos quadrados.
A FIG. 4.22 mostra o resultado do ajuste para a curva de distribuição de
probabilidades do parâmetro comprimento de surto levantada dos dados resultantes
da simulação do canal de HF comentada no item 4.6. O HMM empregado é o
FIG. 4.21: Distribuições dos intervalos entre surtos levantadas da simulação do canal de HF e calculadas pela modelagem baseada em um modelo básico de Gilbert-Elliott, cujos parâmetros foram estimados.
8
modelo de Gilbert-Elliott, cujos parâmetros ótimos estimados para aqueles dados
são:
PG = 0,624 pg = 0,000
PB = 0,208 pb = 0,984, para L = 2
FIG. 4.22: Ajuste da curva de distribuição dos comprimentos de surtos pela curva obtida pelo modelo derivado.
Neste experimento foi observado que, sendo o ajuste à curva de distribuição de
comprimentos de surtos a única condição imposta para otimização, mais de uma
solução é possível, o que sugere o uso de outras condições como o ajuste
simultâneo à curva de distribuição de intervalos entre surtos e a condição dos
parâmetros pertencerem a determinadas faixas de valores reconhecidamente mais
prováveis, como por exemplo: a probabilidade de erro deve ser alta no estado ruim e
baixa no estado bom, para cada caso pertencendo a uma faixa de valores mais
prováveis.
8
5 CONCLUSÃO
O presente trabalho foi direcionado ao estudo dos erros em surtos no canal
físico, gerados em canais de comunicações com memória, tais como os canais “sem
fio”, ficando transparente para nós as camadas mais altas e os protocolos dos
sistemas de comunicações.
Propôs-se um método inédito e eficiente para se obter a análise dos parâmetros
comprimento de surto de erro e intervalo entre surtos de erro, considerando-se a
definição de erro em surto do CCITT (CCITT “BLUE BOOK”). Este método
constituiu-se em um modelo de Markov gerado por uma nova definição dos estados
e das entradas, correspondente a um dado HMM clássico. Este modelo possibilita a
dedução de equações recursivas para o cálculo das distribuições de probabilidades
dos parâmetros comprimento de surto de erro e comprimento de intervalo entre
surtos de erros, relativos aos parâmetros do HMM clássico.
As principais vantagens do cálculo dos parâmetros acima citados em relação as
suas estimativas a partir de massas de dados simuladas, são a velocidade de
geração das distribuições e a precisão destes cálculos estar condicionada apenas a
precisão do processador que executa os cálculos. Os cálculos com o modelo
proposto possibilitam a implementação de algoritmos de baixa complexidade, os
quais a partir dos parâmetros do HMM que se deseja empregar como modelo
básico, produzem os resultados desejados em tempos da ordem de centésimos de
segundos, e que por serem cálculos determinísticos, possuem precisão limitada a da
máquina. Já as estimativas requerem a simulação de massas de dados a partir dos
parâmetros do HMM que se deseja empregar como modelo, para posterior
levantamento dos parâmetros comprimento de surto e intervalo entre surtos. Como
estas estimativas são baseadas em cálculos estatísticos sobre uma amostra
simulada de dados, tempos de processamento da ordem de centenas de segundos
são necessários. Além disto estes resultados possuem precisão dependente do
tamanho da massa de dados empregada.
Foram realizados diversos experimentos com HMM dos tipos Gilbert-Elliott e
Fritchman, na prática os mais utilizados na modelagem de canais sujeitos a erros em
surtos. O modelo de Gilbert-Elliott tem sido o preferido para esta finalidade, pois
8
apesar de uma simples aproximação, este possibilita a implementação de algoritmos
menos complexos do que modelos de mais estados, cuja complexidade inviabiliza
um eficiente tratamento computacional (ZORZI, 1999). Modelos de Fritchman são
freqüentemente utilizados para modelagem de canais com memória, como os canais
de satélites de baixa órbita (LEO) apresentados em (CHU, 2002) e nos canais dos
sistemas de comunicações por ondas espaciais em HF. A modelagem aqui
proposta, devido à sua eficiência, viabiliza a análise dos parâmetros destes canais e
de outros que requeiram modelos mais complexos para representá-los, pois o maior
número de estados não se torna um fator limitante em termos práticos, frente a
velocidade de seus cálculos.
Foram citados exemplos do impacto causado pelos erros em surtos em alguns
sistemas de comunicações “sem fio”. Este assunto vem sendo exaustivamente
estudado por Michele Zorzi e Ramesh R. Rao, os quais possuem grande quantidade
de artigos publicados, como (ZORZI, set, 1998 e 1999), que aborda o impacto dos
erros em surtos sobre os protocolos de redes “sem fio”, tais como o TCP e o ATM.
Observa-se que nos trabalhos de Zorzi e Rao, o modelo escolhido para se
representar os canais com memória é o de Gilbert-Elliot, o qual é considerado por
eles como um modelo simples porém suficiente para tal finalidade (ZORZI, 1999).
Um grande número de experimentos foi realizado com o modelo proposto, dos
quais apenas alguns foram apresentados neste trabalho. Inicialmente procurou-se
confirmar eficiência do modelo através de comparações dos resultados gerados por
este com os levantados de massas de dados geradas por HMM conhecidos. Estes
experimentos mostraram que o modelo proposto baseado no mesmo HMM de uma
massa de dados a representa precisamente consumindo um tempo computacional
milhares de vezes menor do que o tempo de levantamento dos parâmetros na
massa de dados. Em seguida tentou-se ajustar o modelo proposto a uma massa de
dados gerada na simulação de um canal de HF, das quais os parâmetros
desconhecidos foram estimados para HMM de 2 e 3 estados pelo algoritmo de
Baum-Welch e aplicados como modelo básico do modelo proposto, dos quais o
HMM de 3 estados ajustou-se melhor aos dados. Finalmente foi sugerido um método
para estimação de parâmetros de um HMM através do ajuste das curvas de
distribuição calculada e levantada dos dados, o qual foi exemplificado com a
estimação dos parâmetros HMM por meio do ajuste realizado para a curva de
8
distribuição dos comprimentos de surto levantadas dos dados gerados pela
simulação de um canal de HF.
Com relação a trabalhos futuros, deve ser ressaltada a importância da
modelagem dos erros em surtos, visando descrever o impacto causado nas diversas
camadas e protocolos de um sistema de comunicações, cujo canal possua memória.
Sendo este um vasto campo para novos trabalhos. Em seguida, com base nos
estudos anteriores, poderiam ser realizados estudos de métodos para controle dos
erros nas diversas camadas dos sistemas de comunicações.
O modelo proposto também pode gerar trabalhos futuros, como a pesquisa e
desenvolvimento de algoritmos para estimação de parâmetros de HMM, de uma
maneira mais eficiente do que o clássico algoritmo de Baum-Welch, baseados no
ajuste das curvas de distribuição de probabilidades dos parâmetros comprimento de
surtos e intervalo entre surtos calculados pelo modelo, em relação as
correspondentes curvas estimadas, por meio da otimização dos parâmetros do
HMM, que se deseja estimar.
Uma outra sugestão para o futuro seria o desenvolvimento de simuladores de
massas de dados afetadas por erros em surto ao nível de bits, voltados para
aplicações mais específicas em camadas mais altas de um sistema de
comunicações.
Deve ser ressaltada a importância deste estudo em aproveitamento ao Exército
Brasileiro. Em acompanhamento a evolução tecnológica dos sistemas de
comunicações digitais “sem fio”, principais alvos do problema abordado por este
trabalho, o Exército por suas características estratégicas e táticas de emprego em
que as grandes distâncias envolvidas, a mobilidade e a segurança são requisitos
básicos que devem ser atendidos pelas suas comunicações, possui dentre outros
sistemas “sem fio”, sistemas de comunicações em HF e por satélites, os quais
tendem cada vez mais, a se incorporarem às comunicações militares e guerra
eletrônica, duas áreas que do ponto de vista técnico já percebem os efeitos do
fenômeno dos erros em surtos provenientes dos canais “sem fio” sob as condições
de emprego citadas acima. Assim este trabalho vem em parte a contribuir para o
estudo de técnicas que minimizem este problema em busca de um aumento no
desempenho dos sistemas de comunicações mais empregados em ambiente militar.
8
6 REFERÊNCIAS BIBLIOGRÁFICAS
CCITT “Blue book”. Terms and definitions. Vol. 1, fasc. I.3, rec. M.60 n.34, rec.
Q.9 n.0222.
CHOCKALINGAM A., Zorzi, Michele e Rao, Ramesh R. Performance of TCP on
wireless fading links with memory. ICC’ 98. Atlanta, GA: June 7-11, 1998. CHU, V. Y. Y. e Sweeney, P. Channel modelling and error control strategies for
the LEO satellite channel. Dept. of Electrical Engineering, The University of Surrey. Disponível: http://www.ee.surrey.ac.uk/CCSR/Software/OPNET /chu-sweeney.pdf [capturado em 28 mar. 2002].
FRANCHI, A., Harris, R. A. On the error burst properties of Viterbi decoding.
IEEE International Communications Conference, 1993. pag. 1086 a 1091. FRANCHI, A., Harris, Robert A. On the error burst properties of the “standard”
K=7, rate–1/2 convolutional code with soft–decision viterbi decoding. Telecomunication Systems. May 1995. Vol. 6, no 3, pag 337 a 351.
FRITCHMAN, B. D. A binary channel characterization using partioned Markov
chains. IEEE Transactions in Information Theory, April 1967. Vol. IT-13, pp. 221 – 227.
HEISSLER, Jeffrey R., Barsoum, Yosry A. e Richard Condello. An analysis of the
Viterbi decoder error statistics for ATM and TCP/IP over satellite communication. IEEE, 1999.
JOHNSON, Eric E. HF SchEMe: a skywave channel error model. IEEE Military
Communications Conference MILCOM, 1994. MELO, Alexandre Guedes de. Equalização cega em canais WSS-US. Dissertação
de Mestrado (Mestrado em Engenharia Elétrica) - IME, jul. 2000. PAPOULIS, Athanasios. Probability, random variables, and stochastic
processes. 3. ed. Editora McGraw-Hill International Editions, 1991. PROAKIS, J. G. Digital communications. Mc Graw Hill, New York: 1995. RABINER, L. R. e Juang, B. H. Fundamental of speech recognition. Editora
Prentice Hall, 1993. RAMSEIER, Stefan e Kaltenschnee, Thomas. ATM over satellite: analysis of ATM
QOS parameters. Ascom Tech Ltd. Gewerbepark, CH-5506 Magenwill, Switzerland: 1995. pag. 1562 a 1565.
8
SHEN, Jia-Pei e Gill, John. Analysis on a hidden Markov channel model. Global Telecommunications Conference, Globecom’ 99, 1999.
TURIN, Willian e NOBELEN, Robert van. Hidden Markov modeling of flat fading
channels. IEEE Journal on selected areas in communications. dez. 1998. v. 16, n. 9.
ZORZI, Michele, Rao, Ramesh R. e Milstein, Laurence B. On the accuracy of a
first-order Markov model for data transmission on fading channels. ICUPC’95. Tokyo, Japão: nov. 1995.
ZORZI, Michele, Rao, Ramesh R. e Milstein, Laurence B. A Markov model for
block errors on fading channels. PIMRC’96. Taiwan: out.1996. ZORZI, Michele e Rao, Ramesh R. ARQ error control for delay-constrained
communications on short-range burst-error channels. VTC’ 97. Phoenix, AZ: mai. 1997.
ZORZI, Michele e Rao, Ramesh R. The effect of correlated errors on the
performance of TCP. Accepted for publication in IEEE communications letters, set. 1997.
ZORZI, Michele. Outage and error events in bursty channels. IEEE Transactions
on Communications. mar. 1998. Vol. 46, no 3, pag. 349 a 356. ZORZI, Michele. Performance of FEC and ARQ error control in bursty channels
under delay constraints. VTC’98. Ottawa, Canadá: mai. 1998. ZORZI, Michele e Rao, Ramesh R. Impact of burst errors on framing. PIMRC’ 98.
Boston: set. 1998. ZORZI, Michele e Rao, Ramesh R. Perspectives on the impact of error statistics
on protocols for wireless networks. IEEE Personal Communications Magazine. Oct. 1999.
ZORZI, Michele, Chockalingam, A. e Rao, Ramesh R. Throughput analysis of
TCP on channels with memory. IEEE Journal on Selected Areas in Communications. Jul. 2000. Vol. 18 no 7, pag. 1289 a 1300.
ZORZI, Michele e Rao, Ramesh R. On the statistics of block errors in bursty
channels. accepted for publication in the IEEE Transactions on Communications ICUPC’96. Cambridge, MA: sep.30-oct.2, 1996.
![Spontaneous coffee senna poisoning in cattle: Report onbovinos: relato de 16 surtos.] Dezesseis surtos de into-xicação por Senna occidentalis (fedegoso) em bovinos do Spontaneous](https://img.document.onl/doc/110x75/607a4a5a0732b115a7688187/spontaneous-coffee-senna-poisoning-in-cattle-report-on-bovinos-relato-de-16-surtos.jpg)
