Aplicabilidade de Heur sticas na Otimiza˘c~ao de ...da otimiza˘c~ao da etapa de detec˘c~ao no receptor. Abstract Analytical approaches often do not solve problems, having to use

Universidade Estadual de Londrina

Centro de Tecnologia e Urbanismo

Departamento de Engenharia Eletrica

Aplicabilidade de Heurısticas na

Otimizacao de Problemas

Combinatorios em Telecomunicacoes

Rafael de Oliveira Ribeiro

9 de dezembro de 2009

Universidade Estadual de Londrina

Centro de Tecnologia e Urbanismo

Departamento de Engenharia Eletrica




Discente: Rafael. de Oliveira Ribeiro

Orientador: Prof. Dr. Taufik Abrao

Area de concentracao: Telecomunicacoes

Monografia orientada pelo Prof. Dr. Taufik Abrao intitulada

Aplicabilidade de Heurısticas na Otimizacao de Proble-

mas Combinatorios em Telecomunicacoes e apresentada a

Universidade Estadual de Londrina, como parte dos requi-

sitos necessarios a conclusao do Curso de Engenharia Eletrica.


Ficha Catalografica

Ribeiro, Rafael de OliveiraAplicabilidade de Heurısticas na Otimizacao de Problemas Combinatorios

em Telecomunicacoes. Londrina, 2009. 74 p.

— Universidade Estadual de Londrina. Departamento de EngenhariaEletrica.

1. DSP. 2. CDMA 3. Deteccao. 4. Algoritmos Heurısticos.

I. Universidade Estadual de Londrina. Departamento de Engenharia Eletrica.II. Aplicabilidade de Heurısticas na Otimizacao de Problemas Combinatoriosem Telecomunicacoes.

Rafael de Oliveira Ribeiro




Monografia apresentada ao curso de Engenharia Eletrica da

Universidade Estadual de Londrina, como parte dos requi-

sitos necessarios para a conclusao do curso de Engenharia

Eletrica.

Comissao Examinadora

—————————————————Prof. Dr. Taufik Abrao

Dept. de Engenharia EletricaOrientador

—————————————————Prof. MSc. Luis Carlos Kakimoto.

Dept. de Engenharia Eletrica

—————————————————Prof. Dr. Marcio Roberto Covacic

Dept. de Engenharia Eletrica

—————————————————Prof. Msc. Fernando Ciriaco Dias Neto

Faculdade Pitagoras


”A mente que se abre a uma nova ideia jamais

voltara ao seu tamanho original.” (Albert Einstein)

Agradecimentos

Agradeco aos meus pais, Francisco de Fatima Ribeiro e Angela Cristina de Oliveira

Ribeiro, pelo esforco e apoio incondicional que me ajudaram a conquistar meus objetivos.

Ao meu orientador, Prof. Dr. Taufik Abrao, pelo seu apoio, dedicacao e capacidade

de orientacao. Agradeco tambem ao meu co-orientador, Prof. MSc. Fernando Ciriaco,

pela ajuda e contribuicao para que este trabalho pudesse ser realizado.

Aos meus familiares, pelo incentivo nesta etapa da minha vida.

E aos meus colegas de curso, Alex Miyamoto Mussi e Flavio Henrique Silva, que

contribuıram para o avanco deste trabalho.

Resumo

Abordagens analıticas muitas vezes nao oferecem solucoes computacionalmente efi-cientes a problemas de elevada ordem de complexidade, sendo utilizada, alternativamente,modernas tecnicas computacionais para uma busca mais rapida de solucoes aproximadas.Portanto, a utilizacao de algoritmos heurısticos na otimizacao de problemas possibilitaa reducao da complexidade e maior agilidade na resolucao, ja que na area de telecomu-nicacoes muitos problemas sao dinamicos, de elevada ordem/dimensao e/ou mudam aolongo do tempo, fazendo com que as buscas por solucoes crescam exponencialmente como aumento das variaveis de entrada. Neste trabalho e apresentado um estudo sobre as es-trategias de implementacao da ferramenta heurıstica aplicada a sistemas de comunicacaosem fio, enfatizando o algoritmo de recozimento simulado (Simulated Annealing - SA)na deteccao multiusuario (MuD) em sistemas DS-CDMA. O desempenho da ferramentaheurıstica e comparado de acordo com sua eficiencia na solucao do problema proposto,variando-se os parametros do sistema bem como considerando sua implementacao em pro-cessadores digitais de sinais (DSP). Outra ferramenta computacional utilizada no trabalhoe o software MATLAB, o qual permite nao so a simulacao do canal e da transmissao DS-CDMA como tambem o estudo e avaliacao do algoritmo heurıstico SA−MuD na buscada otimizacao da etapa de deteccao no receptor.

Abstract

Analytical approaches often do not solve problems, having to use modern computa-tional techniques to a fast search of solutions. Therefore, the use of heuristic algorithmsfor optimization of problems enables the reduction of complexity and greater flexibilityin the resolution. In telecommunications issues, the problems are dynamic, changing overtime and the search for solutions grow exponentially with the increase of input variables.The heuristic tools applied to wireless communication systems as to the DS-CDMA mul-tiuser detection (MUD), are introduced emphasizing the main algorithms and the basicideas of each. The acting of the tool heuristic is compared with your performance in theproblem proposed, varying up the parameters of the system and also the implementationthis algorithm on digital signal processors (DSP). Another computational tool used in theproject is the MatLab software that allows the simulation of the channel and the trans-mission DS-CDMA, as well as the study of heuristic algorithms in search optimization ofthe receiver (a low error rate of bit).

Sumario

Lista de Figuras vii

Lista de Tabelas x

1 INTRODUCAO 1

1.1 Modulacao por Espalhamento Espectral . . . . . . . . . . . . . . . . . . . 2

1.2 A Tecnologia CDMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Tecnica DS-CDMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Descricao do Conteudo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.5 Publicacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 CARACTERISTICAS DO SISTEMA 7

2.1 Canal AWGN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Receptor Convencional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 Banco de Filtros Casados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4 Interferencia de Multiplo Acesso . . . . . . . . . . . . . . . . . . . . . . . . 10

3 FERRAMENTAS COMPUTACIONAIS 13

3.1 MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 Code Composer Studio - CCS . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Configurando a Comunicacao RTDX entre MATLAB e DSP . . . . . . . . 15

4 DESCRICAO DO PROBLEMA 19

5 ALGORITMOS HEURISTICOS 21

5.1 Algoritmo Simulated Annealing (SA) - Recozimento Simulado . . . . . . . 22

5.2 Adaptacao do algoritmo SA a deteccao MuD . . . . . . . . . . . . . . . . . 24

6 IMPLEMENTACAO EM DSP E RESULTADOS 26

6.1 Parametros do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

6.2 Desempenho do Algoritmo SA no problema da deteccao MuD . . . . . . . 28

6.3 Robustez do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7 Analise de Complexidade em DSP 41

7.1 Complexidade do Detector Convencional . . . . . . . . . . . . . . . . . . . 42

7.2 Complexidade para o Algoritmo Heurıstico SA . . . . . . . . . . . . . . . . 43

7.3 Complexidade para o Receptor SA-MuD Completo em Banda Base . . . . 50

7.4 Comparacao de Complexidade Computacional entre os Algotimos SA e

LS 1 opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

7.5 Calculo de Complexidade em Funcao do Numero de Operacoes . . . . . . . 54

8 CONCLUSAO 58

8.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Anexo A -- PROCESSADOR DIGITAL DE SINAIS - DSP 60

A.1 Ferramentas de suporte do DSK . . . . . . . . . . . . . . . . . . . . . . . . 61

A.1.1 DSP TMS320C6713 . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Anexo B -- SEQUENCIAS DE ESPALHAMENTO 64

B.1 Sequencias Aleatorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

B.2 Sequencias Walsh-Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . 65

B.3 Sequencias de Maximo Comprimento (SMC) . . . . . . . . . . . . . . . . 65

B.4 Sequencias Gold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

Anexo C -- Metodo de Simulacao Monte Carlo 68

Anexo D -- Principais Funcoes e Comandos Implementados 71

Referencias 73

Lista de Figuras

1.1 Transmissao e recepcao sistema DS-CDMA com filtro casado a sequencia

de espalhamento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 a) Sinal de bit transmitido no tempo b) Sequencia de espalhamento no

tempo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1 Canal com ruıdo gaussiano. . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Sistema Transmissao - Recepcao CDMA - (a) Transmissor em banda-base;

(b) Modelo de canal adotado (AWGN); (c) MFB e (d) Detector Conven-

cional Abrupto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Diagrama de blocos do sistema de transmissao/recepcao DS-CDMA imple-

mentado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 Codigo criado em linguagem C no CCS. . . . . . . . . . . . . . . . . . . . 15

3.3 Esquema de comunicacao generica do RTDX. . . . . . . . . . . . . . . . . 16

3.4 Inicializando RTDX atraves do software CCS. . . . . . . . . . . . . . . . . 17

3.5 Configuracao do numero de buffers do RTDX. . . . . . . . . . . . . . . . . 18

3.6 Processo de compilacao e carregamento do codigo automaticamente no CCS

atraves do MATLAB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1 Fluxograma dos processos adotados para implementacao do receptor SA-

MuD em DSP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.1 Classificacao das abordagens aproximativas. . . . . . . . . . . . . . . . . . 21

5.2 Sistema Transmissao-recepcao SA-MuD - (a) Transmissor em banda-base;

(b) Canal AWGN; (c) 1o estagio MFB; (d) Detector Convencional Abrupto

com ponto de derivacao das estimativas do MFB e (e) Algoritmo Heurıstico

SA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6.1 Sinal recebido observado com osciloscopio atraves da saıda Line Out do DSP. 27

6.2 Esquemas de ligacoes DSP - osciloscopio. . . . . . . . . . . . . . . . . . . . 28

6.3 Saıda Line Out do DSP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

6.4 Entrada dos parametros de simulacao do algoritmo SA. . . . . . . . . . . . 30

6.5 Parametros de entrada da 1a simulacao - SNR x BER. . . . . . . . . . . . 31

6.6 Dados e tempo estimado de todas simulacoes. . . . . . . . . . . . . . . . . 31

6.7 Resultados da 1a simulacao com baixo carregamento - SNR = 6 dB. . . . . 32

6.8 Desempenho do algoritmo SA para baixo carregamento (L = 0,333) e con-

trole total de potencia (NFR = 0). . . . . . . . . . . . . . . . . . . . . . . 33

6.9 Desempenho do algoritmo SA para alto carregamento (L = 0,8) e controle

total de potencia (NFR = 0). . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.10 Parametros de entrada da 2a simulacao - SNR x BER. . . . . . . . . . . . 35

6.11 Resultados da 2a simulacao com baixo carregamento - SNR = 6 dB. . . . . 36

6.12 Convergencia do algoritmo SA para baixo carregamento, L = 0,3333. . . . 37

6.13 Convergencia do algoritmo SA para alto carregamento, L = 0,8. . . . . . . 37

6.14 Parametros de entrada da simulacao para analise da robustez do sistema

(Indice de Carregamento x BER). . . . . . . . . . . . . . . . . . . . . . . . 38

6.15 Resultados da simulacao Indice de Carregamento x BER para L = 1. . . . 39

6.16 Analise da robustez do sistema: Indice de Carregamento (L = K/N), versus

BER). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

6.17 Analise da robustez do sistema (NFR x BER). . . . . . . . . . . . . . . . . 40

7.1 Habilitacao das funcoes para contagem de ciclos. . . . . . . . . . . . . . . . 42

7.2 Configuracao do PROFILE para contagem de ciclos. . . . . . . . . . . . . . 43

7.3 Definicao das variaveis de saıda do PROFILE. . . . . . . . . . . . . . . . . 46

7.4 Resultados do PROFILE - contagem de ciclos. . . . . . . . . . . . . . . . . 46

7.5 Grafico correspondente a complexidade em DSP do CD gerado com os

dados da tabela 7.4 com um Fitting do tipo Linear. . . . . . . . . . . . . . 47

7.6 Grafico da complexidade em DSP da Funcao Custo Inicial do SA. . . . . . 50

7.7 Grafico da complexidade em DSP de cada Iteracao do algoritmo SA gerado

com os dados da tabela 7.6. . . . . . . . . . . . . . . . . . . . . . . . . . . 51

7.8 Grafico da comparacao de ciclos entre a funcao do algoritmo SA e do re-

ceptor CD - @ N = 20. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

7.9 Grafico do incremento de complexidade do receptor. . . . . . . . . . . . . . 53

7.10 Grafico da capacidade maxima de processamento do DSP @ N = 4. . . . . 54

7.11 Grafico da capacidade maxima de processamento do DSP @ N = 8. . . . . 55

7.12 Grafico da Complexidade computacional dos algoritmos SA e LS 1 opt @

N = 15. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

7.13 Grafico do incremento de complexidade do algoritmo SA em relacao ao

LS 1 opt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

A.1 Diagrama de blocos do kit de desenvolvimento TMS320C6713 . . . . . . . 60

A.2 Placa do kit de desenvolvimento DSK6713 . . . . . . . . . . . . . . . . . . 62

B.1 Funcao de autocorrelacao de sequencias m (SMC). . . . . . . . . . . . . . . 66

C.1 Definicao da simulacao de Monte Carlo. . . . . . . . . . . . . . . . . . . . . 68

C.2 Modelo de simulacao de um sistema de comunicacao. . . . . . . . . . . . . 69

D.1 Rotinas e funcoes implementadas em DSP. . . . . . . . . . . . . . . . . . . 71

D.2 Funcao implementada para o decisor convencional com decisor abrupto. . . 72

D.3 Funcao do algoritmo Simulated Annealing implementada em DSP. . . . . . 72

Lista de Tabelas

6.1 Variacao do ındice de carregamento. . . . . . . . . . . . . . . . . . . . . . . 33

7.1 Tabela com os Ciclos do DSP resultados do Profile do CCS da funcao

MF DecisorHard (detector convencional). . . . . . . . . . . . . . . . . . . . 44

7.2 Tabela comparativa da complexidade do CD para diferentes valores de K

e N mostrando o Fator de Proporcionalidade K.N . . . . . . . . . . . . . . 44

7.3 Mapa de processamentos realizados utilizando Profile da funcao MF DecisorHard

(detector convencional); demonstram-se as posicoes onde ocorreu repeticao

do fator K.N com um asterisco. . . . . . . . . . . . . . . . . . . . . . . . . 45

7.4 Tabela da complexidade computacional, em ciclos do DSP, do CD (funcao

MF DecisorHard) em relacao ao Fator de Proporcionalidade K.N . . . . . . 45

7.5 Tabela da complexidade computacional (ciclos do DSP) da Funcao Custo

Inicial do algoritmo Simulated Annealing em relacao ao numero de usuarios

K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

7.6 Tabela da complexidade computacional (ciclos do DSP) de cada iteracao

(funcao Iteracoes) do algoritmo Simulated Annealing em relacao ao numero

de usuarios K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Lista de Siglas e Abreviaturas

1-opt LS 1 Optimum Local Search - Algoritmo de Busca Local 1 Otimo

AWGN Additive White Gaussian Noise - Ruıdo Branco Aditivo Gaussiano

BER Bit Error Rate - Taxa de erro de bit

BPSK Binary Phase Shift Keying - Modulacao por Chaveamento de Fases

CD Conventional Detector - Detector Convencional

CDMA Code Division Multiple Access - Multiplo Acesso por Divisao de Codigo

CCS Code Composer Studio

DS Direct Sequence - Espalhamento por Sequencia Direta

DS-CDMA Direct Sequence CDMA - CDMA por Sequencia Direta

DSP Digital Signal Processor - Processador Digital de Sinais

FDMA Frequency Division Multiple Access - ultiplo Acesso por Divisao de Frequencia

MAI Multiple Access Interference - Interferencia de Multiplo Acesso

MCS Monte Carlo Simulation - Metodo de Simulacao Monte Carlo

MFB Matched Filter Bank - Banco de filtros casados

ML Maximum Likehood Estimator - Estimador de Maxima Verossimilhanca

MuD Multi User Detection - Deteccao Multiusuario

NFR Near-Far Ratio - Efeito perto-longe

SA Simulated Annealing - Recozimento Simulado

SMC Sequencia de Maximo Comprimento

SNR Signal Noise Ratio - Relacao Sinal Ruıdo

SS Spread Spectrum - Espalhamento Espectral

SuB Single-User Bound - Limite de BER para usuario isolado

SuD Single-User Detection - Deteccao Uniusuario

TDMA Time Division Multiple Access - Multiplo Acesso por Divisao de Tempo

Notacoes

a, µ,A Escalar, caracter em italico

a Vetor, caracter minusculo em negrito

A Matriz, caracter maiusculo em negrito

a Valor estimado de uma dada variavel a

ai i -esimo elemento do vetor a

Ai,j Elemento da i -esima linha e j -esima coluna da matriz A

diag(a1, ..., ak) Matriz diagonal com elementos a1, ..., ak

{.}T Operador matriz transposta

{.}H Operador hermitiano

<{.} Operador parte real

={.} Operador parte imaginaria

{.} Operador melhor valor ou melhor vetor segundo um criterio

sgn [.] Operador sinal do argumento

max[.] Valor maximo assumido pelo argumento

Q(.) Funcao erro complementar gaussiano

Px (x) Funcao densidade de probabilidade da variavel x

U(x, y) Processo aleatorio com distribuicao uniforme entre as variaveis x e y

N(x, y) Processo aleatorio com distribuicao normal de media x e variancia y

∈ Pertence ao conjunto

Palavras em italico sao empregadas para identificar termos de lıngua inglesa nao

traduzidos.

Lista de Sımbolos

A Amplitude do sinal

b Bit transmitido

DSPCycles Numero de ciclos de processamento por segundo do DSP

Eb Energia de bit

Eb/N0 Relacao entre a energia de bit recebido e a densidade espectral de potencia do ruıdo

F (x) fitness value - funcao custo da variavel x

fbest Funcao custo global

gi Ganho da funcao custo de cada i-esimo vetor-candidato em relacaoa funcao custo global

h (t) Resposta impulsiva do canal

K Numero de usuarios ativos

L Indice de carregamento

M Numero de iteracoes adotado na simulacao

nerros Numero de erros por ponto na Simulacao Monte Carlo

N Ganho de processamento

N0 Densidade espectral de potencia do ruıdo

r (t) Sinal em tempo contınuo que chega ao receptor

R Matriz de correlacao entre todas as sequencias

sik i-esimo chip da sequencia de espalhamento do k-esimo usuario

t Tempo

trials Numero de repeticoes da Simulacao Monte Carlo

Tb Perıodo de bit

Tc Perıodo de chip

y Saıda amostrada de um correlacionador

V (x) Vizinhanca de x, equivalente a distancia de Hamming

η Parcela devida ao ruıdo termico de tempo discreto amostrado

η (t) Parcela devida ao ruıdo termico de tempo contınuo

ρx,y Correlacao cruzada entre as sequencia x e y

ϑ Vetor-candidato

ϑbest Melhor vetor-candidato obtido segundo a funcao custo (vetor-solucao)

σx Desvio padrao do processo x

σ2x Variancia do processo x

1

1 INTRODUCAO

Nos ultimos anos, ha um crescente interesse em sistemas de comunicacoes sem fio.

A busca por maior mobilidade aliada as caracterısticas de altas taxas de transmissao,

fizeram com que novas tecnologias de transmissao/recepcao fossem desenvolvidas visando

principalmente a otimizacao de tais sistemas.

O processo de otimizacao de algum recurso no sistema procura nao so determinar as

possıveis solucoes,como tambem procura agregar uma maior agilidade nesse procedimento,

sendo muitas vezes necessaria uma busca extensa e complexa para a determinacao das

respostas de um determinado problema, como por exemplo, a definicao de um maximo

ou mınimo em uma determinada funcao com inumeras variaveis.

Um aspecto fundamental de muitos problemas de otimizacao na area de telecomu-

nicacoes e o fato destes serem dinamicos. Isto implica que uma possıvel solucao para um

problema num determinado instante podera nao ser a melhor solucao poucos segundos

subsequentes.

Abordagens analıticas ou algoritmos simples podem ser uma maneira para resolver um

problema dinamico. Porem, muitas vezes esses problemas mudam rapidamente, fazendo-

se necessarias modernas tecnicas computacionais para uma busca mais rapida de solucoes,

ja que em muitos desses problemas o tempo ou o espaco de busca cresce exponencialmente

com o aumento das variaveis de entrada.

Algoritmos heurısticos possibilitam diminuir a complexidade em problemas aplicados

a sistemas de comunicacao sem fio e simultaneamente proporcionam uma maior veloci-

dade na obtencao de resultados quase-otimos tornando, deste modo, o uso de algoritmos

heurısticos extremamente interessante.

1.1 Modulacao por Espalhamento Espectral 2

1.1 Modulacao por Espalhamento Espectral

Desenvolvida para comunicacoes militares a fim de aumentar a seguranca das trans-

missoes e evitar possıveis interferencias intencionais ou nao intencionais, a modulacao por

espalhamento espectral (Spread Spectrum - SS) passou a ser utilizada tambem em comu-

nicacoes comerciais, nao apenas pelo fato de dificultar a interceptacao, mas tambem por

ser imune aos problemas de propagacao do sinal tendo uma utilizacao eficiente da largura

de banda, bem como da potencia.

Atraves do espalhamento espectral, descobriu-se que um determinado espectro nao

precisava ser dividido em varias faixas de frequencias, mas sim utilizado por diversos

transmissores simultaneamente com a mesma frequencia de portadora.

Segundo Haykin (HAYKIN; MOHER, 2005), pode-se definir espalhamento espectral

como:

“Espalhamento espectral e aquele em que o sinal transmitido se espalha

por uma faixa de frequencia muito mais ampla do que a largura de banda

mınima necessaria para transmitir a informacao enviada. Este tipo de sinal

pode coexistir com sinais de banda estreita, adicionando somente uma ligeira

elevacao no piso de ruıdo que os receptores de banda estreita observam”.

Existem diversas formas de espalhamento espectral, entre elas o espalhamento por

sequencia direta (DS), onde uma sequencia de dados de entrada e usada para modular

um codigo de banda larga. Esse codigo transforma a sequencia de dados de banda estreita

em um sinal de banda larga como se fosse um ruıdo.

Como afirma Lathi (LATHI, 1998), “o codigo de espalhamento e tambem chamado de

sequencia PN (pseudo−ruıdos), que e geralmente periodica e composta, ou seja, formada

por uma sequencia de 1 e 0 com determinada propriedade de autocorrelacao”.

A sequencia gerada e multiplicada pelo sinal a ser transmitido, devendo esta possuir

um intervalo de tempo menor que o sinal transmitido, sendo chamados tais intervalos de

“chips”. Como o intervalo dos chips e menor que os bits do sinal, o espectro associado a

sequencia, como citado, e do tipo banda larga.

1.2 A Tecnologia CDMA 3

1.2 A Tecnologia CDMA

A tecnologia desenvolvida de acesso multiplo por divisao de codigo - CDMA (Code

Division Multiple Access) nao utiliza apenas uma determinada faixa estreita de frequencia

para transmissao, e sim o espalhamento espectral, onde os transmissores utilizam esse

espectro simultaneamente, compartilhando em geral a mesma banda para transmissao.

Devido as tecnologias de multiplo acesso por divisao de tempo e frequencia TDMA

(Time Division Multiple Access) e FDMA (Frequency Division Multiple Access), respecti-

vamente possuırem um numero fixo de slots de tempo ou frequencia para cada transmissor,

o CDMA ao utilizar o espalhamento espectral apresenta uma vantagem com relacao as

tecnologias anteriores, proporcionando explorar uma maior capacidade de canal e con-

sequentemente possibilitar a operacao de um numero maior de sinais/usuarios em uma

mesma faixa do espectro.

Sistemas CDMA caracterizam-se pela interferencia, chamada interferencia de multiplo

acesso (MAI), que ocorre devido ao afastamento que os codigos de espalhamento tem da

ortogonalidade perfeita. Ja o outro fenomeno que ocorre e o problema do perto-longe

(NFR): sinais recebidos com potencias muito dıspares no receptor causam degradacao

excessiva no desempenho.

O sistema CDMA utiliza entao o controle de potencia na estacao radio base (ERB)

para evitar tal complicacao. Contudo, o controle de potencia e util principalmente em

sistemas de multiplo acesso para maximizar a capacidade do sistema.

Assim, a maximizacao da capacidade do sistema e obtida quando ha um estrito con-

trole de potencia em sistemas CDMA convencionais, a fim de que a relacao sinal-ruıdo

permaneca em um nıvel aceitavel, pois a elevacao da potencia recebida de alguns sinais

em detrimento dos demais aumentara a interferencia de multiplo acesso, reduzindo o

desempenho medio do sistema.

1.3 Tecnica DS-CDMA

O sistema DS-CDMA (Direct Sequence / Code Division Multiple Access) utiliza uma

sequencia distinta para cada usuario para multiplicar (no tempo) ou espalhar (no espectro)

o sinal desse mesmo usuario.

Utilizando-se uma modulacao BPSK como mostrado na figura 1.1, o sinal a ser rece-

1.4 Descricao do Conteudo 4

bido pelo receptor pode ser expresso como

r (t) =K∑

k=1

Akbkcksk (t) + η (t) (1.1)

onde K e o numero de usuarios, Ak e a amplitude do sinal transmitido do k-esimo usuario,

bk ∈ [−1,+1] e o bit transmitido, ck e o coeficiente de canal para o k-esimo usuario, sk e

a sequencia do k-esimo usuario e η(t) representa o ruıdo AWGN do canal.

Figura 1.1: Transmissao e recepcao sistema DS-CDMA com filtro casado a sequenciade espalhamento.

Os chips das sequencias de espalhamento da figura 1.2 devem ser alinhados de forma

ortogonal, contribuindo para a diminuicao da interferencia de multiplo acesso (TORRIERI,

2005).

Assim, no receptor, o sinal r (t) deve ser multiplicado pela sequencia de espalhamento

do usuario sk que deseja-se receber o sinal, sendo o sinal a saıda do banco de filtro casados

(detector convencional) determinado por (ABRAO; CIRIACO; JESZENSKY, 2004):

yk =

∫ Tb

0

r (t) sk (t) .dt = Akbkck +∑j 6=k

Ajbjcjρk,j + ηk (1.2)

onde ρK,j denota o k,j -esimo elemento da matriz de correlacao cruzada.

1.4 Descricao do Conteudo

Esta monografia contem alem da introducao, mais 6 capıtulos que podem ser assim

resumidos:

1.4 Descricao do Conteudo 5

Figura 1.2: a) Sinal de bit transmitido no tempo b) Sequencia de espalhamento notempo.

• capıtulo 2 - Neste capıtulo sao descritas as caracterısticas de um sistema DS-

CDMA, como o canal utilizado na implementacao (canal AWGN), a interferencia de

multiplo acesso (MAI) aos quais os sinais estao sujeitos bem como o funcionamento

do banco de filtro casado.

• capıtulo 3 - Neste capıtulo sao descritas as ferramentas computacionais utilizadas

no projeto. Realiza-se uma breve discussao sobre os softwares utilizados (Matlab e

Code Compose Studio), bem como tambem faz-se um estudo do processador digital

de sinais (DSP) mostrando suas configuracoes e caracterısticas.

• capıtulo 4 - Este capıtulo e dedicado a apresentacao do problema da deteccao

multiusuario (MuD), buscando demonstrar a viabilidade da implementacao em DSP

da tecnica heurıstica.

• capıtulo 5 - Neste capıtulo apresenta-se a definicao de algoritmos heurısticos, dando

enfase ao algoritmo SA (Simulated Annealing) utilizado no trabalho e apresentando

suas caracterısticas para aplicacao no problema da deteccao Mud.

• capıtulo 6 - Neste capıtulo sao apresentadas as principais funcoes criadas para

o projetos no DSP como tambem os resultados obtidos para o sistema DS-CDMA

implementado em DSP em comparacao com os resultados das simulacoes em Matlab.

• capıtulo 7 - Este capıtulo mostra a analise de complexidade computacional da

implementacao do algoritmo SA-MuD completo em banda base.

1.5 Publicacoes 6

• capıtulo 8 - Este capıtulo apresenta um resumo das conclusoes do trabalho e

tambem as perspectivas para novos projetos.

1.5 Publicacoes

1. Analise de Complexidade dos Algoritmos Heurısticos de Deteccao Multiusuario

CDMA Implementados em DSP (Plataforma TMS320C6713).

Autores: Ribeiro, R. O.; Mussi, A. M.; Abrao, T.; Ciriaco, F. D. N. .

2. Metodologia de projeto e implementacao em DSP (Plataforma TMS320C6713) dos

Algoritmos Heurısticos de Deteccao Multiusuario em Sistemas CDMA.

Autores: Mussi, A. M.; Ribeiro, R. O.; Abrao, T. .

7

2 CARACTERISTICAS DOSISTEMA

Para a implementacao do sistema DS-CDMA empregar-se-a um sistema em canal

AWGN sıncrono. Este capıtulo ira tratar da interferencia a qual o sinal estara sujeito

(MAI), a caracterizacao de um canal AWGN, como tambem do banco de filtros casados

(MFB) utilizado na deteccao de sinais.

Na implementacao do receptor de sinal CDMA, tanto o banco de filtro casado como

o decisor abrupto foram implementados em DSP, em conjunto com o algoritmo de reco-

zimento simulado (SA) a fim de otimizar a recepcao do sinal transmitido.

2.1 Canal AWGN

As transmissoes das comunicacoes sem fio sempre sofrem interferencia de um fenomeno

aleatorio que pode ser descrito por uma distribuicao estatıstica. Tais fenomenos podem

ser atribuıdos a muitas fontes e todos sao chamados de ruıdo (LEE; MILLER, 1998).

Existem muitas fontes que provocam esses tipos de perdas, incluindo o proprio re-

ceptor, as fontes artificiais, construıdas pelo homem e a acao de outros transmissores nas

comunicacoes.

O canal com ruıdo branco gaussiano aditivo (Additive White Gaussian Noise - AWGN)

e o modelo basico utilizado no desenvolvimento da teoria das comunicacoes, onde nesse

canal o ruıdo possui media 0 e apresenta uma distribuicao Gaussiana como propriedade

adicional. O ruıdo e presumido branco ao longo de toda a banda de interesse pois as

amostras do ruıdo no intervalo nao estao relacionadas entre si, implicando que o ruıdo

possua uma funcao de autocorrelacao dada por (N0/2) δ(t), onde δ(t) e a funcao Delta

de Dirac (HAYKIN; MOHER, 2005).

O modelo de canal AWGN e mostrado na figura 2.1.

2.2 Receptor Convencional 8

Figura 2.1: Canal com ruıdo gaussiano.

Quando tem-se um processo de ruıdo aleatorio estatıstico, tal como o ruıdo Gaussiano,

pode-se implementar receptores otimos capazes de serem aplicados em situacoes praticas,

sendo o modelo matematico do canal AWGN o mais usual (LUDERS; SCHULZE, 2005).

Seu modelo pode ser caracterizado como uma perturbacao aleatoria aditiva de um

sinal e como citado acima e uma funcao amostral de media igual a zero e densidade

espectral de potencia (CIRIACO, 2004), definido pela equacao (2.1):

σ2 =N

2Eb/N0

(2.1)

Sua funcao densidade de probabilidade e entao definida pela equacao (2.2):

Px (x) =1√

2πσ2e

(− x

2

σ2

)(2.2)

2.2 Receptor Convencional

Em canais AWGN sıncrono, o receptor convencional (CD) consiste de um banco de K

filtros casados as sequencias de espalhamento dos usuarios, onde a saıda do filtro casado

para o k -esimo usuario pode ser expressa por:

yk =

∫ Tb

0

r(t)sk(t)dt = Akbk +K∑

j 6=k

Ajbjλkj + ηk (2.3)

onde ηk o ruıdo AWGN para o k -esimo usuario e λkj o k,j -esimo elemento da matriz de

correlacao R.

Para estimar os bits dos usuarios, o detector convencional considera apenas a parte

real da saıda do banco de filtros casados seguido de um circuito de decisao abrupta:

bk = sign(<e {yk}) (2.4)

2.3 Banco de Filtros Casados 9

Este sistema tambem sera implementado em DSP, sendo comparado o seu desem-

penho com o do algoritmo SA (detector multiusuario), ja que o desempenho do detector

convencional tera reducao quando o numero de usuarios compartilhando o mesmo canal

aumentar, implicando num aumento da MAI e quando existir disparidades de potencia

entre os usuarios, um aumento do efeito near-far.

A aplicacao da estrategia de deteccao multiusuario utilizando algoritmos heurısticos,

no caso deste trabalho o SA-MuD, procura melhorar esse desempenho do CD otimizando

para um desempenho proximo ao do detector de maxima verossimilhanca.

2.3 Banco de Filtros Casados

Os sinais digitais tem um espectro amplo e o canal da transmissao apresenta ruıdo

aditivo, ou seja, afeta os dados transmitidos.

Para deteccao de tal sinal que esta imerso em ruıdo branco aditivo faz-se necessario

a utilizacao de um dispositivo de deteccao otima, que usa um filtro linear invariante no

tempo denominado filtro casado. E dado este nome ao filtro porque sua resposta ao

impulso e casada com o sinal de pulso.

Para detectar um sinal com um receptor de filtro casado, a amostra de saıda e com-

parada com um limiar e entao uma decisao e tomada pelo receptor, dependendo se o

limiar for excedido ou nao.

Apos o banco de filtros casados tem-se o detector convencional abrupto como pode

ser observado na figura 2.2.

Assim, o MFB (Matched Filter Bank) busca detectar o sinal transmitido de maneira

otima, dado o sinal recebido, procurando sempre a maximizacao do filtro e a minimizacao

dos efeitos provocados pelo ruıdo aditivo.

O sinal recebido x(t) dado pela equacao (2.5) pelo filtro consiste em um sinal de pulso

g(t) corrompido pelo ruıdo de canal aditivo η(t)

x (t) = g (t) + η (t) , 0 ≤ t ≤ T (2.5)

onde T e um intervalo arbitrario.

Logo, o receptor otimo corresponde ao processamento definido pela equacao (2.6):

y =

∫ T

0

x (t) g∗ (t) dt (2.6)

2.4 Interferencia de Multiplo Acesso 10

Figura 2.2: Sistema Transmissao - Recepcao CDMA - (a) Transmissor em banda-base;(b) Modelo de canal adotado (AWGN); (c) MFB e (d) Detector Convencional Abrupto.

Haykin e Moher (HAYKIN; MOHER, 2005) definem que como a potencia do ruıdo nao

depende do formato do sımbolo, sendo que esta e a essencia da filtragem casada, tem-

se que em um canal AWGN o desempenho da transmissao de espalhamento espectral de

sequencia direta (DS-SS) e identico aos sistemas que nao apresentam espalhamento, sendo

a relacao sinal-ruıdo dada pela equacao (2.7).

SNR =Eb

N0

(2.7)

onde Eb e a energia do bit e N0 e a densidade espectral do ruıdo.

2.4 Interferencia de Multiplo Acesso

O CDMA e uma estrategia de acesso multiplo para comunicacoes baseado no espalha-

mento espectral por sequencia direta (DS-SS), onde o espalhamento proporcionado pelo

codigo altera o espectro do sinal usado para transmitir a informacao.

Se os codigos de espalhamento forem perfeitamente ortogonais, e possıvel alcancar o

desempenho de um unico usuario no caso de multiusuarios.

Assim, existindo K usuarios CDMA compartilhando o mesmo canal, o sinal de banda


base recebido e dado por

x(t) =K∑

k=1

sk(t) + η(t) 0 ≤ t ≤ T (2.8)

onde os sinais transmitidos individualmente refletem seus respectivos dados fornecidos

por

sk(t) = bk√Ebgk(t) (2.9)

sendo bk e gk a sequencia de dados e codigos de espalhamento respectivamente e Eb a

energia por bit.

Supondo receber o sinal do primeiro usuario (k = 1), o receptor convencional de um

unico usuario aplica o correlacionador casado a sequencia de assinatura g1(t) para o sinal

recebido, obtendo-se:

y =

∫ T

0

x(t)g1(t)dt = b1√Eb + η1 +

√Eb

K∑k=2

bkR1k 0 ≤ t ≤ T (2.10)

onde os primeiros dois termos sao equivalentes ao caso de unico usuario, ou seja, termo do

sinal mais o termo do ruıdo. O ultimo termo representa a interferencia de acesso multiplo.

A amplitude media da saıda do correlacionador e dado por

E[y] = b1√Eb + E[η1] + E[

√Eb

K∑k=0

bkR1k] = b1√Eb + 0 + 0 = b1

√Eb (2.11)

A contribuicao do acesso multiplo para a variancia do ruıdo e aproximadamente dado

por (HAYKIN; MOHER, 2005)

σ2MAI ≈ Eb

K∑k=2

1

N(2.12)

onde N representa o ganho de processamento.

Admitindo-se o controle de potencia dos transmissores, tem-se que a potencia trans-

mitida de cada usuario e ajustada de forma que a potencia recebida seja constante.

Assim, a contribuicao da interferencia de acesso multiplo para o ruıdo na equacao (2.10)

pode ser resumida como

µMAI = E[y − b1

√Eb

](2.13)

e

σ2MAI =

K − 1

NEb (2.14)


Verifica-se tambem que conforme o numero de usuarios aumenta, K sendo muito

grande, a MAI se comporta como um termo de ruıdo branco aditivo Gaussiano.

Com b = ±1, a relacao sinal-interferencia-mais-ruıdo (SINR) inclui o ruıdo do receptor

e a MAI, sendo definida pela equacao (2.15).

SINR =Eb

N0

(1

1 + K−1N

EbN0

)=Eb

N0

Dg (2.15)

onde o parametro Dg da equacao (2.15) e a degradacao no desempenho de um unico

usuario devido a interferencia de multiplo acesso. Tal parametro e definido pela equacao (2.16).

Dg =

(1 +

K − 1

N

Eb

N0

)−1

(2.16)

A degradacao depende da operacao Eb/N0, do numero de usuarios K e do ganho de

processamento N. A relacao Eb/N0 e a SINR de um unico usuario na ausencia de qualquer

interferencia de acesso multiplo.

Mais usuarios implicam numa maior degradacao, porem um ganho de processamento

alto reduz o efeito da interferencia e diminui a degradacao.

13

3 FERRAMENTASCOMPUTACIONAIS

Este capıtulo apresentara os softwares utilizados no desenvolvimento do trabalho, i.e.,

os softwares MATLAB c© da Mathworks e o Code Composer Studio (CCS c©), associado

a plataforma de processamento digital de sinais (DSP). Tais ferramentas computacionais,

juntamente com a plataforma DSP (hardware) foram empregadas na solucao do problema

da deteccao MuD.

3.1 MATLAB

MATLAB e um software para simulacoes matematicas computacionais desenvolvido

pela Mathworks, sendo utilizado para o desenvolvimento de algoritmos, visualizacao,

analise de dados e, obviamente tambem, calculo numerico.

Diversas aplicacoes podem ser desenvolvidas com o uso do MATLAB, incluindo pro-

cessamento de imagens e sinais, comunicacoes, controle, teste, medicao, modelagem e

analise financeira, entre outros. Como possui diversas funcionalidades, pode-se integrar o

seu codigo com outras linguagens e aplicacoes computacionais.

O Real-Time Workshop (RTW) gera e executa codigos em C, onde o codigo resultante

pode ser utilizado em tempo real para muitas aplicacoes. Pode-se ajustar o codigo gerado

utilizando-se de recursos internos de analise e/ou executar e interagir com o codigo fora

do ambiente como foi utilizado no trabalho a troca de dados com o MATLAB.

Utilizando-se do recurso Real-Time Workshop conseguiu-se trabalhar com dois ambi-

entes de processamento ao mesmo tempo ao empregar o RTDX (Real-Time Data Transfer)

para troca de dados entre o MATLAB e o kit de processamento DSK6713 (Code Composer

Studio - CCS).

Um problema encontrado na transferencia de dados entre o kit de processamento

DSK6713 e o MatLab pode ser a limitacao de dados a serem transmitidos pela portas

3.2 Code Composer Studio - CCS 14

Figura 3.1: Diagrama de blocos do sistema de transmissao/recepcao DS-CDMAimplementado.

seriais.

As caracterısticas do DSP e do kit de processamento DSK6713 como a quantificacao

de portas seriais, memoria e outros dispositivos sao descritas no Anexo A.

3.2 Code Composer Studio - CCS

O CCS e um programa desenvolvido pela Texas Instruments para o desenvolvimento

de programas e interface dos modelos de DSP que ela fabrica.

O CCS inclui ferramentas para a geracao de codigo (um compilador C), apresentando

tambem capacidades graficas e suporte a depuracao dos dados em tempo real.

Pode-se passar dados para o DSP utilizando o intercambio em tempo real de dados

(RTDX). O RTDX permite a troca de dados entre o computador e o kit DSK, bem como

a analise em tempo real do que esta sendo processado no DSP.

Assim, faz-se necessario um programa para compilar o algoritmo gerado, sendo esta

a funcao do CCS para o modelo de processador que foi utilizado.

O codigo criado em linguagem C como mostrado na figura 3.2 e entao convertido, para

gerar o executavel no DSP, especificando as rotinas, interrupcoes bem como os dispositivos

3.3 Configurando a Comunicacao RTDX entre MATLAB e DSP 15

e dados de entrada e saıda que o programa devera implementar a partir dos blocos de

bibliotecas utilizados na implementacao do algoritmo.

Figura 3.2: Codigo criado em linguagem C no CCS.

3.3 Configurando a Comunicacao RTDX entre MAT-

LAB e DSP

Real-Time Data Exchange (RTDX) fornece, em tempo real, a visibilidade contınua

nas operacoes realizadas numa plataforma de destino. RTDX transfere dados entre um

computador, “host”, e dispositivos de destino,“target”, sem interferir nas aplicacoes re-

alizadas no “target”, ou seja, sem interrupcao de processamento no “target”. Voce pode

analisar e visualizar os dados no computador utilizando a interface fornecida pelo COM

RTDX. Aplicativos-cliente como o Visual Basic, Visual C + +, Excel, LabView, MAT-

LAB, e outros podem facilmente usar a interface COM. Esta representacao realista de seu

funcionamento do sistema pode encurtar o tempo de desenvolvimento.

RTDX forma dois canais para caminho de dados entre um aplicativo-cliente no com-

putador e a plataforma de destino atraves de uma combinacao de componentes de hard-

ware e software, como mostrado na figura 3.3.


Figura 3.3: Esquema de comunicacao generica do RTDX.

Os dados podem ser enviados a partir do aplicativo da plataforma de destino para o

aplicativo-cliente no computador e vice-versa. Os dados podem ser inseridos nesses canais

de forma assıncrona, ou seja, a qualquer momento.

O dispositivo de destino envia dados para o computador chamando funcoes da biblio-

teca RTDX localizada na plataforma de destino, chamada “RTDX Target Library”. Estas

funcoes imediatamente armazenam os dados em um buffer de dados e entao retornam. A

“RTDX Target Library”, em seguida, transmite os dados do buffer para o computador,

sem interferir no dispositivo de destino. O computador registra estes dados ou em um

buffer de memoria ou um arquivo de log RTDX, dependendo do modo de gravacao no

computador especificado na configuracao do RTDX. Os dados gravados podem ser recu-

perados por qualquer aplicativo-cliente no computador que esteja interfaceado com o Code

Composer Studio (CCS) via RTDX. Computadores de plataforma Windows oferecem uma

interface COM que e usada entre um aplicativo-cliente e o CCS.

Do mesmo modo, um aplicativo-cliente no computador pode enviar dados para o

dispositivo de destino. A biblioteca RTDX localizada no CCS, chamada “RTDX Host

Library”, armazena no buffer todos os dados enviados para o dispositivo de destino. Se a

“RTDX Host Library”receber um pedido de dados do dispositivo de destino e os dados no

buffer do host forem suficientes para atender a solicitacao, a “RTDX Host Library”envia

os dados para o dispositivo de destino. Os dados sao gravados para o local solicitado sem

interferir com o dispositivo de destino. O host notifica o “RTDX Host Library”apos a

conclusao de operacao.

A configuracao do RTDX e realizada no software CCS atraves do menu Tools (figura 3.4),


podendo este procedimento ocorrer sem que o DSP esteja conectado.

Figura 3.4: Inicializando RTDX atraves do software CCS.

Por padrao, a configurcao inicial do RTDX apresenta 4 buffers contendo cada um 1024

bytes. Porem, como mostrado na figura 3.5, pode-se alterar estes valores e os adequar ao

projeto a ser implementado.

Apos a configuracao de todos parametros do RTDX, o projeto deve ser compilado e o

DSP conectado, podendo somente apos tais etapas habilitar o RTDX (Enable RTDX )para

realizacao da troca de dados entre o Matlab e DSP. Durante a implementacao do algoritmo

SA-MuD em DSP, foi utilizado os 4 buffers com 1024 bytes cada definidos por padrao.

Para nao ter que compilar e carregar o projeto em cada simulacao, criou-se funcoes no

MATLAB para que esses processos fossem realizados automaticamente em cada simulacao

como pode ser observado na figura 3.6. Assim, conseguiu-se realizar diversas simulacoes

consecutivamente sem ter que compilar/carregar o projeto no CCS, otimizando o tempo

gasto nas simulacoes ja que em cada uma dessas eram necessarios que novos parametros

fossem compilados e carregados no processador.


Figura 3.5: Configuracao do numero de buffers do RTDX.

Figura 3.6: Processo de compilacao e carregamento do codigo automaticamente noCCS atraves do MATLAB.

19

4 DESCRICAO DO PROBLEMA

Mesmo garantindo-se uma baixa MAI atraves do projeto cuidadoso das sequencias

de espalhamento, o ruıdo AWGN, bem como as caracterısticas do canal, interferem na

recepcao dos dados DS-CDMA. Assim, procura-se utilizar algoritmos de deteccao otima

ou quase otima dos dados recebidos sem com isto recair em uma excessiva complexidade

computacional.

Em Verdu (VERDU, 1998), foi definida a funcao de verossimilhanca (funcao custo)

que ao ser maximizada, resulta no melhor vetor de bits recebidos, i.e., garante-se que tal

informacao recebida e a mais proxima possıvel daquela transmitida, resultando assim em

uma metrica para a obtencao do detector otimo. Logo, o vetor b e definido por:

b = arg

{max

b∈{+1,−1}K2yT CHAb− bT CARACHb

}(4.1)

onde y e o vetor de saıda do 1o estagio do MFB (antes do decisor abrupto) dado pela

equacao 1.2, C e a matriz diagonal dos coeficientes do canal, A e a matriz de amplitudes

dos sinais dos usuarios e R e a matriz de correlacao. O vetor b e estimado de forma a

maximizar a equacao 4.1, dado que o sinal transmitido, equacao 1.1, foi recebido.

Verdu (VERDU, 1986) tambem definiu que o detector multiusuario otimo e composto

por um banco de filtros casados seguido por um detector de maxima verossimilhanca

(ML). O problema dessa solucao consiste no fato de ter que se testar todas as possıveis

combinacoes do vetor de dados na equacao 4.1 a cada perıodo de sımbolos de informacao,

ou seja, a complexidade do problema cresce exponencialmente com o numero de usuarios.

A figura 4.1 representa um fluxograma dos processos adotodas na implementacao do

trabalho.

Os algoritmos heurısticos aplicados a tais problemas buscam chegar a mesma solucao

encontrada pelo detector de maxima verossimilhanca ou o mais proximo a esta, realizando

apenas algumas iteracoes em um espaco de busca reduzido, apresentando assim uma

complexidade reduzida em relacao a complexidade do detector ML.

3 DESCRICAO DO PROBLEMA 20

Figura 4.1: Fluxograma dos processos adotados para implementacao do receptorSA-MuD em DSP.

Neste trabalho sera utilizado o algoritmo heurıstico baseado na tecnica de recozimento

simulado (Simulated Annealing - SA). O objetivo consiste em demonstrar a viabilidade de

implementacao em DSP da tecnica heurıstica para a deteccao MuD, bem como tambem

caracterizar o seu desempenho sob condicoes especıficas de canal e de operacao do sistema

multiusuario DS-CDMA.

21

5 ALGORITMOS HEURISTICOS

O termo heurıstica provem do grego heuriskein, com significado de descobrir ou achar.

Goldbarg (GOLDBARG; LUNA, 2000) define heurıstica como um metodo de busca de

solucoes em que nao ha qualquer garantia de que tais respostas tenham sucesso.

Contudo, esse sucesso pode ser expresso quantitativa ou qualitativamente, buscando-

se a otimizacao de um problema atraves da obtencao de uma solucao otima.

Assim, a ferramenta heurıstica pode ser definida como uma tecnica que procura a

melhor solucao utilizando-se de tecnologia computacional razoavel e conseguindo garantir

a otimizacao da solucao encontrada ou uma solucao viavel muito proximo a esta.

Os primeiros trabalhos envolvendo algoritmos heurısticos surgiram em problemas es-

pecıficos, nao sendo capazes na maioria das vezes de solucionar outros tipos de problemas.

Eram tecnicas heurısticas classicas associadas a estrategias de enumeracao incompleta,

solucao parcial ou relaxacoes, como por exemplo a heurıstica classica de roteamento.

A figura 5.1 mostra a classificacao das abordagens aproximativas (CIRIACO, 2004).

Figura 5.1: Classificacao das abordagens aproximativas.

Dentre as abordagens aproximativas apresentadas na figura 5.1, a heurıstica classica

busca a exploracao da estrutura do problema, as chamadas metaheurısticas divididas em

5.1 Algoritmo Simulated Annealing (SA) - Recozimento Simulado 22

estocasticas e analogicas. Ja as heurısticas modernas possuem um grande retorno na busca

pelo seu objetivo como tambem uma boa qualidade nas solucoes encontradas, tornando-se

ultimamente uma excelente alternativa para aplicacoes em modelos combinatorios.

Dentre os principais algoritmos heurısticos destacam-se:

• Algoritmo Genetico (GA - Genetic Algorithm).

• Busca Local.

• Busca Tabu.

• Simulated Annealing - SA.

• Particle Swarm Optimization - PSO.

• Ant Colony Optimization - ACO.

Neste trabalho optou-se pelo algoritmo de Recozimento Simulado (Simulated Annea-

ling - SA), devido a suas estrategias de escape de maximos locais, tornando-se uma exce-

lente opcao para solucionar o problema MuD, a ser implementado em DSP.

5.1 Algoritmo Simulated Annealing (SA) - Recozi-

mento Simulado

O metodo SA foi apresentado por Kirkpatrick e colaboradores em 1983, baseado em

ideias formuladas no inıcio da decada de 50.

O algoritmo SA e uma tecnica de otimizacao baseada no processo fısico de recozimento,

onde uma substancia e aquecida a uma elevada temperatura, passando em seguida a ser

resfriada progressivamente o que minimiza a sua probabilidade de distribuicao de energia

(HAUPT; HAUPT, 2004).

A otimizacao de problemas deve evitar que o algoritmo encontre apenas uma solucao

local. Assim, o SA utilizando-se de uma funcao de probabilidade de aceitacao proporcional

a temperatura, contribuem para que o algoritmo escape de regioes de maximo local e

procure por um maximo global em outras regioes.

O algoritmo SA utilizado na implementacao MuD em DSP e MATLAB e baseado no

algoritmo de busca local (1-opt LS), sendo chamado de SA-LS. Este algoritmo procura

5.1 Algoritmo Simulated Annealing (SA) - Recozimento Simulado 23

a melhor solucao em um menor espaco de busca em uma vizinhanca de distancia de

Hamming igual a 1 (KATAYAMA; NARIHISA, 2001).

Apresenta-se a seguir a descricao para o algoritmo de recozimento simulado (simulated

annealing - SA) adaptado ao problema da deteccao multiusuario (CIRIACO, 2004).

1. Utiliza-se a saıda do detector convencional como a solucao inicial.

ϑ1 = bCD = sign [y]

2. Calcula-se a energia inicial do sistema atraves da funcao custo.

ϑbest ← ϑ1

fbest ← F (ϑ1)

3. Enquanto o algoritmo melhorar fbest :

(a) Encontra-se as K possıveis solucoes na vizinhanca de ν (ϑm) cuja distancia de

Hamming e 1, onde ϑm e o melhor vetor solucao da iteracao atual.

(b) Calcula-se a energia do sistema para cada uma das solucoes possıveis atraves

da funcao custo.

(c) Se F (ϑi) > fbest :

ϑbest ← ϑi

fbest ← F (ϑi)

(d) Calcula-se a variacao de energia, associada a funcao custo.

∆e = F (ϑm)−F (ϑi)

Se ∆e < 0 :

ϑm+1 ← ϑi

f(ϑm+1)← F (ϑi)

Se ∆e ≥ 0, gera-se um numero aleatorio com distribuicao uniforme x ∈ U[0, 1]

Se x < xm:

ϑm+1 ← si

5.2 Adaptacao do algoritmo SA a deteccao MuD 24

f(ϑm+1) ← F(ϑi)

onde x(m) e o criterio de aceitacao.

4. Retorna-se a etapa 3 ate que nao ocorra mais otimizacao da funcao custo.

5. O vetor ϑbest e o vetor de saıda do algoritmo.

O criterio de probabilidade de aceitacao x(m), e baseado na termodinamica, sendo

definido por:

p (m) = exp

[− ∆E

T (m)

](5.1)

onde T (m) e a temperatura na iteracao m. Inicia-se o algoritmo com uma temperatura

inicial com valor alto ( T (0) > 0 ), sendo reduzida atraves de um processo de

resfriamento.

O processo de resfriamento adotado no algoritmo consiste em inicializar a temperatura

T(0), mantendo esta constante por LSA(tamanho da serie - plato) iteracoes. A cada serie

de LSA iteracoes, a temperatura decai atraves de um fator ε (passo de resfriamento) ∈[0, 1].

A cada mLSA iteracoes, a temperatura e reduzida gradativamente:

T(mLSA) = εmT (0)

onde ε cosntante, 0 < ε < 1.

5.2 Adaptacao do algoritmo SA a deteccao MuD

O receptor convencional (CD) apresenta uma diminuicao no seu desempenho ao se

aumentar o numero de usuarios do sistema, provocando um aumento da MAI. A utilizacao

do algoritmo SA adaptado ao problema MuD, permite que se obtenha um desempenho

igual ou muito proximo do detector ML, sem entretanto ter que utilizar uma grande

complexidade computacional.

Assim, a estrategia adotada para solucionar tal problema na deteccao MuD atraves

do algoritmo SA, consiste na procura de uma melhor solucao segundo uma funcao custo

5.2 Adaptacao do algoritmo SA a deteccao MuD 25

(dentro de um determinado espaco de busca), sendo no contexto da deteccao MuD a

funcao dada por:

F(ϑ) = 2yT Aϑ− ϑT ARAϑ (5.2)

onde y e o vetor de saıda do banco de filtro casado (MFB), A e a matriz de amplitudes

dos sinais dos usuarios e R e a matriz de correlacao. A matriz diagonal dos coeficientes

do canal da funcao de verossimilhanca e C = 1, ja que no trabalho nao foi considerado

ruıdo multiplicativo.

O diagrama de recepcao utilizando algoritmo heurıstico SA e mostrado na figura 5.2.

O receptor constitui-se de um banco de filtros casados, seguido do algoritmo heurıstico

SA com o intuito de maximizar o desempenho da funcao da equacao (5.2).

Figura 5.2: Sistema Transmissao-recepcao SA-MuD - (a) Transmissor em banda-base;(b) Canal AWGN; (c) 1o estagio MFB; (d) Detector Convencional Abrupto com ponto

de derivacao das estimativas do MFB e (e) Algoritmo Heurıstico SA.

26

6 IMPLEMENTACAO EM DSPE RESULTADOS

Este capıtulo mostrara o desempenho do algoritmo heurıstico SA para o sistema DS-

CDMA em simulacoes no MATLAB e em DSP.

Em todas as simulacoes realizadas utilizou-se o metodo de Monte Carlo 1, sendo ado-

tado um numero mınimo de erros / ponto de 40 (nerros = 40). O numero mınimo de

erros/ponto foi adotado para garantir um tempo de processamento no DSP razoavel visto

que para alguns pontos o aumento do numero de erros tornar-se-ia inviavel o processa-

mento.

Nas simulacoes em MATLAB como no processamento em DSP foram incluıdos os

desempenhos dos detectores convencional (CD) e tambem o limite quando existe apenas

um unico usuario ativo no sistema (SuB), utilizando-se modulacao BPSK e canal AWGN

sıncrono.

Utilizou-se tambem a saıda Line Out do Kit DSK C6713 para que, atraves de um

osciloscopio, pudesse ser observado o sinal recebido pelo receptor SA-MuD implementado

em DSP, como pode ser visto na figura 6.1.

A figura 6.2 e figura 6.3 mostram os esquemas de ligacoes utilizados no trabalho para

poder observar o sinal de saıda, ou seja, o melhor vetor de bits estimados pelo receptor

SA-MuD em DSP.

6.1 Parametros do Sistema

Para entrada dos parametros das simulacoes utilizou-se do software MatLab o qual

procurou-se propiciar uma maior facilidade para o usuarios nas simulacoes sem este ter

que alterar diretamente o codigo do programa. Um exemplo da entrada dos parametros

1Para informacoes sobre o metodo de Monte Carlo ver anexo C

6.1 Parametros do Sistema 27

Figura 6.1: Sinal recebido observado com osciloscopio atraves da saıda Line Out doDSP.

do programa e mostrado na figura 6.4.

Para as simulacoes em Matlab foram utilizados os seguintes parametros: ganho do

processamento (Sequencia PN) com N = 32, distancia de Hamming = 1, temperatura

inicial do SA, T (0) = 300, constante de resfriamento ε = 0,1, tamanho da serie (Plato)

LSA= 1. Para as simulacoes em DSP do algoritmo SA utilizou-se os mesmos parametros

das simulacoes em Matlab.

Os valores adotados como parametros para o algoritmo SA foram inicialmente obtidos

da literatura (CIRIACO, 2004) e apos simulacoes adicionais cujos valores dos parametros

foram alterados, obteve-se assim os valores finais ”otimizados” (busca nao exaustiva)

mencionados acima em todas as simulacoes.

Tanto nas simulacoes em Matlab como tambem em DSP, escolheu-se sequencias

aleatorias (PN), pois como mostrado no Anexo B, as sequencias determinısticas tem boas

propriedades de correlacao e melhorariam o desempenho do sistema. Assim, utilizando-se

de sequencias aleatorias trabalhar-se-ia na pior condicao e, portanto, poder-se-ia realcar

o ganho obtido com a abordagem heurıstica.

6.2 Desempenho do Algoritmo SA no problema da deteccao MuD 28

Figura 6.2: Esquemas de ligacoes DSP - osciloscopio.

6.2 Desempenho do Algoritmo SA no problema da

deteccao MuD

Para analise inicial do desempenho do algoritmo SA no Matlab comparando com o

processamento em DSP, utilizou-se um ganho de processamento N = 32 e numero de

usuarios K = 10, resultando em um carregamento L = K/N = 10/30 = 0,3333. A entrada

dos parametros para simulacao em MATLAB bem como do processamento em DSP e

realizada atraves do MATLAB e passada atraves do RTDX para o DSP como pode ser

observado na figura 6.5 e figura 6.6.

Assim, para um baixo carregamento (L = 0,3333) foi calculado a taxa de erro de bit do

receptor SA-MuD sendo que os dados obtidos durante o processamento sao apresentados

a cada nova SNR como pode ser observado na figura 6.7.

A figura 6.8 mostra o desempenho do algoritmo SA com controle total de potencia

(NFR = 0) e baixo carregamento comparado ao detector convencional (CD) e com o limite

quando existe apenas um usuario ativo no sistema (SuB) apos todas simulacoes.

A figura 6.9 mostra o desempenho da 2a simulacao do algoritmo SA na deteccao MuD

(SNR x BER) com um alto carregamento e tambem com controle total de potencia (NFR

= 0).


Figura 6.3: Saıda Line Out do DSP.

Para essa simulacao, tanto em MATLAB como tambem no processamento em DSP,

utilizou-se um ganho de processamento N = 15 e 12 usuarios, gerando um carregamento L

= K/N = 0,8. Tais parametros de entrada da simulacao sao apresentados na figura 6.10.

Os dados obtidos durante o processamento sao apresentados a cada variacao da SNR

como mostrado na figura 6.11.

Nas duas simulacoes ( com baixo e alto carregamento), o desempenho obtido com o

algoritmo SA-MuD implementado em DSP foi muito proximo e algumas vezes ate melhor

que o desempenho em MATLAB.

Tambem foi analisado o numero de iteracoes que o receptor SA-MuD implementado

em DSP demora para convergir para o detector optimo.

Pode-se observar atraves da figura 6.12 que o algoritmo SA converge em poucas it-

eracoes para o desempenho obtido com o detector optimo (OMuD). Para essa simulacao

foi utilizado um carregamento L = 10/30 = 0,3333 e uma SNR = 6 dB.

Aumentando-se o carregamento do sistema (L = 12/15 = 0,8) e utilizando-se a mesma

SNR empregada anteriormente, observa-se que o SA consome algumas iteracoes a mais

para convergir para o melhor vetor de bits como e mostrado na figura 6.13. Porem, mesmo

com um carregamento alto, o algoritmo nas primeiras iteracoes ja consegue convergir


Figura 6.4: Entrada dos parametros de simulacao do algoritmo SA.

para melhor solucao (solucao otima) apesar de, nesta condicao de alto carregamento, ser

computacionalmente inviavel calcular a funcao de maxima verossimilhanca, eq. (4.1), a

todos os possıveis vetores candidatos, neste caso, 212 candidatos.

Pode-se perceber atraves da figura 6.13 que nao era necessario um grande numero de

iteracoes para que se conseguisse a otimizacao do sistema. Assim, foi determinado um

criterio de parada para o algoritmo SA a fim de diminuir o tempo de processamento.

O criterio de parada adotado consiste em retornar o melhor vetor de bits estimados

pelo detector Heur-MuD quando este nao otimizar mais a funcao custo em duas iteracoes

consecutivas.

A utilizacao de tal criterio de parada contribuiu para uma consideravel reducao no

tempo de processamento do algoritmo SA em DSP.

6.3 Robustez do Sistema 31

Figura 6.5: Parametros de entrada da 1a simulacao - SNR x BER.

Figura 6.6: Dados e tempo estimado de todas simulacoes.

6.3 Robustez do Sistema

Apos a analise do desempenho da BER do receptor SA-MuD atraves da variacao da

relacao sinal-ruıdo, realizou-se o estudo da robustez do sistema. Primeiramente realizou-

se um estudo do desempenho do receptor (BER) variando-se o ındice de carregamento do

sistema.

Para realizar as simulacoes foram utilizados 4 variacoes de ganho de processamento,

onde os parametros de entrada utilizados na simulacao sao mostrados na figura 6.14. A

tabela 6.1 contem os valores de ganho de processamento (N) e usuarios (K) utilizados na

simulacao para verificar a robustez do sistema.

Em cada variacao do ındice de carregamento, a saıda do algoritmo, exemplificado

atraves da figura 6.15 (L = 1) indicava os parametros de entrada, bem como os dados

obtidos no processamento.

A figura 6.16 mostra o grafico de robustez do sistema em funcao da variacao do ındice

de carregamento com uma SNR = 7 dB. Pode-se observar que o desempenho do algortimo

SA e afetado com aumento do ındice de carregamento. No entanto, o detector uniusuario


Figura 6.7: Resultados da 1a simulacao com baixo carregamento - SNR = 6 dB.

(convencional) apresenta uma degradacao muito maior com esta variacao.

Para analise da robustez do sistema com o efeito near-far (NFR 6= 0), utilizou-se

um cenario com um carregamento L = 0,67, com 3 usuarios de interesse (7 dB) e 7

usuarios interferentes com NFR variando de 1 dB ate 13 dB. A figura 6.17 mostra o

desempenho alcancado pelo algoritmo SA neste cenario, sendo avaliado o desempenho

medio dos usuarios de interesse.

Observa-se atraves do numero de iteracoes media que o algoritmo Simulated Annealing

necessita de um maior numero de iteracoes para convergir do que na condicao de controle

total de potencia (NFR = 0), indicando que a convergencia do algoritmo SA aplicado a

deteccao MuD e afetada pela presenca do efeito near-far.


Figura 6.8: Desempenho do algoritmo SA para baixo carregamento (L = 0,333) econtrole total de potencia (NFR = 0).

Tabela 6.1: Variacao do ındice de carregamento.

Usuarios (K) Ganho de Processamento (N) Indice de Carregamento (L)3 30 0,106 30 0,209 30 0,3012 30 0,4010 20 0,5012 20 0,6010 15 0,6712 15 0,8011 12 0,9212 12 1,00


Figura 6.9: Desempenho do algoritmo SA para alto carregamento (L = 0,8) e controletotal de potencia (NFR = 0).


Figura 6.10: Parametros de entrada da 2a simulacao - SNR x BER.


Figura 6.11: Resultados da 2a simulacao com baixo carregamento - SNR = 6 dB.


Figura 6.12: Convergencia do algoritmo SA para baixo carregamento, L = 0,3333.

Figura 6.13: Convergencia do algoritmo SA para alto carregamento, L = 0,8.


Figura 6.14: Parametros de entrada da simulacao para analise da robustez do sistema(Indice de Carregamento x BER).


Figura 6.15: Resultados da simulacao Indice de Carregamento x BER para L = 1.


Figura 6.16: Analise da robustez do sistema: Indice de Carregamento (L = K/N),versus BER).

Figura 6.17: Analise da robustez do sistema (NFR x BER).

41

7 Analise de Complexidade emDSP

O Code Composer Studio fornece uma ferramenta que possibilita o profile do seu

codigo em execucao, ou seja, o monitoramento de alguns parametros desejados no proces-

sador DSP durante a execucao do seu codigo ou parte dele. Os parametros que podem

ser monitorados podem ser vistos atraves da aba “Custom”do “Setup”do Profile. Muitos

parametros podem ser monitorados, sendo o mais comum “Cycles”que se refere aos ciclos

do DSP.

Para realizar e analisar a complexidade computacional do receptor Heur−MuD bem

como do algoritmo SA, utilizou-se esta ferramenta

Dentro do seu codigo, pode-se escolher funcoes, loops ou linhas de codigo que, durante

sua execucao, habilitarao o Profile. A aba “Ranges”do “Setup”do Profile ilustra que

regioes do seu codigo estao habilitadas ou nao para o Profile.

A ferramenta PROFILE permite que se obtenha o numero de ciclos realizado pelo

DSP em todo o codigo durante o processamento ou tambem individualmente em cada

funcao como pode ser visto na figura 7.1.

Primeiramente deve-se configurar o PROFILE para obter os ciclos atraves da opcao

Custom (figura 7.2) e apos o programa carregado no CCS pode-se estabelecer as variaveis

que se deseja obter atraves do profile. A figura 7.3 mostra as variaveis observadas para

estimar os numeros de ciclos em funcao do numero de usuarios (K) e ganho de processa-

mento (Nchips).

A figura 7.4 mostra os resultados das variaveis obtidas atraves do PROFILE. Obtem-

se o numero de vezes em que cada funcao foi acessada como tambem o numero mınimo,

maximo e a media de ciclos das funcoes do receptor MF bem como do algoritmo SA.

7.1 Complexidade do Detector Convencional 42

Figura 7.1: Habilitacao das funcoes para contagem de ciclos.

7.1 Complexidade do Detector Convencional

Para determinar a complexidade do receptor (apenas MF DecisorHard), realizou-se

varios processamentos em DSP com variacao dos parametros K e N obtendo-se valores

medios entre 5 execucoes da funcao. Logo, realizou-se uma comparacao com os resultados

obtidos atraves do PROFILE, analisando o numero medio de ciclos (Cycles: Incl. Avg.)

que a funcao utilizou.

Os resultados obtidos sao apresentados na tabela 7.1, onde percebe-se que os ciclos

realizados pelo DSP durante a execucao da funcao MF DecisorHard sao proporcionais aos

valoresK eN . Assim, desenvolveu-se uma tabela de comparacao para verificar a tendencia

de o numero de ciclos ser proporcional aos parametros K e N , como e confirmado na

tabela 7.2.

Tendo um fator de proporcionalidade definido, K.N , tracou-se um mapa de proces-

samentos onde este fator repetia-se conforme a tabela 7.3, sendo que as posicoes com

asterisco indicam repeticao do fator K.N em um ou mais processamentos, onde nestas

posicoes, realizou-se a media aritmetica dos ciclos do DSP realizados com um mesmo fator

K.N .

7.2 Complexidade para o Algoritmo Heurıstico SA 43

Figura 7.2: Configuracao do PROFILE para contagem de ciclos.

Com os dados encontrados, montou-se a tabela final da complexidade computacional

do detector CD em funcao do fator de proporcionalidade K.N , tabela 7.4. A partir dos

valores da tabela 7.4, pode-se estimar uma funcao para linearizar tais dados atraves da

ferramenta “cftool”do Matlab.

Portanto, a linearizacao encontrada e dado por:

DSPCyclesCD =

1658 + (1120 ·K ·N)

Tb

[ciclos

seg

](7.1)

sendo DSPCyclesCD o numero de ciclos de processamento por segundo que o DSP executa

para detectar um bit de todos os K usuarios com ganho de processamento N , sendo que o

ciclo de processamento deve ser realizado dentro de um perıodo de informacao detectada,

Tb.

7.2 Complexidade para o Algoritmo Heurıstico SA

Com intuito de realizar a analise da complexidade computacional do algoritmo SA,

tambem foi utilizado a ferramenta Profile do CCS, onde algumas consideracoes devem ser

feitas ja que o sistema considerado no projeto consiste de um canal sıncrono AWGN. A


Tabela 7.1: Tabela com os Ciclos do DSP resultados do Profile do CCS da funcaoMF DecisorHard (detector convencional).

Usuarios Ganho de Processamento (N)(K) 10 15 20 25 30

1 11906 17196 22171 28026 318752 23347 34957 43842 54270 646733 35571 50646 68015 84206 1019414 45899 68344 89403 111390 1299665 59718 86692 114672 140041 1687506 68942 102463 136864 170928 2017107 81862 120201 158582 198355 2367028 93340 135556 178160 223265 2620389 105670 156029 205173 252390 29805510 117135 171320 229597 282789 34032711 131013 189542 248893 317631 37241312 141297 203601 274920 337755 397721

Tabela 7.2: Tabela comparativa da complexidade do CD para diferentes valores de K eN mostrando o Fator de Proporcionalidade K.N .

Usuarios Relacao entre K Relacao de Relacao Relacao de(K) (para N = 20) Ciclos do DSP de N Ciclos do DSP

1 1/12 = 8, 3% 8, 1% 20/15 = 133% 128%2 2/12 = 16, 7% 15, 9% 20/15 = 133% 125%3 3/12 = 25, 0% 24, 7% 20/15 = 133% 134%4 4/12 = 33, 3% 32, 5% 20/15 = 133% 131%5 5/12 = 41, 7% 41, 7% 20/15 = 133% 132%6 6/12 = 50, 0% 49, 8% 20/15 = 133% 134%7 7/12 = 58, 3% 57, 7% 20/15 = 133% 132%8 8/12 = 66, 7% 64, 8% 20/15 = 133% 131%9 9/12 = 75, 0% 74, 6% 20/15 = 133% 131%10 10/12 = 83, 3% 83, 5% 20/15 = 133% 134%11 11/12 = 91, 7% 90, 5% 20/15 = 133% 131%12 12/12 = 100, 0% 100, 0% 20/15 = 133% 135%


Tabela 7.3: Mapa de processamentos realizados utilizando Profile da funcaoMF DecisorHard (detector convencional); demonstram-se as posicoes onde ocorreu

repeticao do fator K.N com um asterisco.

Usuarios Ganho de Processamento (N)(K) 10 15 20 25 30

1 10 15 20* 25 30*2 20* 30* 40* 50* 60*3 30* 45 60* 75* 90*4 40* 60* 80* 100* 120*5 50* 75* 100* 125 150*6 60* 90* 120* 150* 180*7 70 105 140 175 2108 80* 120* 160 200* 240*9 90* 135 180* 225 27010 100* 150* 200* 250 300*11 110 165 220 275 33012 120* 180* 240* 300* 360

Tabela 7.4: Tabela da complexidade computacional, em ciclos do DSP, do CD (funcaoMF DecisorHard) em relacao ao Fator de Proporcionalidade K.N .

K.N Ciclos DSP K.N Ciclos DSP10 11906 135 15602915 17196 140 15858220 22759 150 17033025 28026 160 17816030 33134 165 18954240 44871 175 19835545 50646 180 20349050 56994 200 22643160 67494 210 23670270 81862 220 24889375 85449 225 25239080 91372 240 26847990 103358 250 282789100 114399 270 298055105 120201 275 317631110 131013 300 339040120 135920 330 372413125 140041 360 397721


Figura 7.3: Definicao das variaveis de saıda do PROFILE.

Figura 7.4: Resultados do PROFILE - contagem de ciclos.

funcao-custo utilizada no algoritmo heurıstico Simulated Annealing e dada pela equacao (7.2).

F (ϑ) = Re{2yT Aϑ− ϑT ARAϑ} (7.2)

onde ϑ sao os vetores-candidatos (distancia de Hamming igual a 1), y e o vetor de saıda

do 1o estagio do MFB antes do decisor abrupto, A e a matriz de amplitudes dos sinais

dos usuarios e R e a matriz de correlacao.

Observando a equacao (7.2) nota-se que os termos 2yT A e ARA serao os mesmos

para todas as iteracoes, independentemente dos vetores-candidatos. Assim, para reduzir a

complexidade computacional durante os processamentos em DSP, calculou-se estes termos

separadamente (equacao (7.3) e equacao (7.4)) fora do laco de iteracoes do algoritmo SA.


Figura 7.5: Grafico correspondente a complexidade em DSP do CD gerado com osdados da tabela 7.4 com um Fitting do tipo Linear.

F (1) = Re{2yT A} (7.3)

F (2) = Re{ARA} (7.4)

Com isso, em cada iteracao os valores de F (1) e F (2) ja estavam calculados. A

equacao (7.5) representa a Funcao Custo de cada iteracao.

F (ϑ) = F (1)ϑ− ϑTF (2)ϑ (7.5)

Utilizando-se da ferramenta Profile pode-se realizar diversos processamentos em DSP

vriando-se os parametros K e N . Para obter o numero de ciclos do algoritmo SA, dividiu-

se esta em ciclos da Funcao Custo Inicial e ciclos das Iteracoes, onde obteve-se valores

medios entre 5 execucoes da funcao.

Os ciclos da Funcao Custo Inicial foram obtidos analizando-se apenas os calculos

realizados que antecedem o laco das iteracoes, i.e., os calculos dos termos F (1) e F (2)


Tabela 7.5: Tabela da complexidade computacional (ciclos do DSP) da Funcao CustoInicial do algoritmo Simulated Annealing em relacao ao numero de usuarios K.

Usuarios Ganho de Processamento (N) Media Ciclos Desvio(K) 10 15 20 25 30 do DSP Padrao (σ)

1 4452 4505 4512 4530 4532 4506 32,422 9793 9771 9747 9752 9886 9790 56,743 18868 18874 18802 18897 18948 18878 52,804 32410 32443 32401 32427 32595 32455 79,795 52598 52556 52544 52413 52388 52500 93,266 79523 79577 79569 79688 79553 79582 62,757 115386 115331 115210 115283 115115 115265 105,888 160331 160422 160251 160208 160415 160325 95,809 217088 217114 217002 217015 216745 216993 146,4010 285134 285450 285386 285410 285399 285356 126,2811 368410 368451 368339 368497 368502 368440 67,6712 464117 463981 463991 463973 463944 464001 67,06

seguidos pelo calculo da funcao-custo utilizando o vetor a saıda do decisor abrupto.

Para o calculo dos ciclos da funcao Iteracos foram realizadas iteracoes ate que nao

ocorresse melhora na funcao-custo por duas iteracoes consecutivas.

Os resultados obtidos utilizando a ferramenta Profile da Funcao Custo Inicial sao

apresentados na tabela 7.5 e os ciclos de cada iteracao na tabela 7.6. Analisando-se as

duas tabelas percebe-se que as duas funcoes dependem apenas do numero de usuarios,

ou seja, o parametro de ganho de processamento N nao influencia o numero de ciclos

destas duas funcoes. Esta tendencia pode ser confirmada se analisarmos que o ganho de

processamento nao participa da execucao do algoritmo SA, pois, o seu vetor-inical e dado

pelo vetor a saıda do decisor abrupto que e um sinal vindo do MFB, ou seja, o sinal esta

desespalhado e com dimensao K × 1.

Logo, com os ciclos obtidos (tabela 7.5) realizou-se uma linearizacao para a Funcao

Custo Inicial atraves de um Fitting do tipo Cubic Polynomial (figura 7.6) apresentada na

equacao (7.6) . Para a funcao Iteracoes realizou-se o mesmo procedimento sendo o grafico

desta apresentado na figura 7.6 e sua linearizacao dada pela equacao (7.7).

Entretanto, a equacao (7.7) depende do numero de iteracoes (M) que o algoritmo SA

devera realizar para melhorar a funcao custo. Assim, como mostrado na figura 7.6 bem

como atraves da variavel SA it count DSP (variavel que mostra o numero de iteracoes

realizadas), o algoritmo SA converge para melhor solucao em media de K/2 iteracoes.

Portanto, como M = K/2 a equacao (7.7) pode ser simplificada para a equacao (7.8).


Tabela 7.6: Tabela da complexidade computacional (ciclos do DSP) de cada iteracao(funcao Iteracoes) do algoritmo Simulated Annealing em relacao ao numero de usuarios

K.

Usuarios Ganho de Processamento (N) Media Ciclos Desvio(K) 10 15 20 25 30 do DSP Padrao (σ)

1 2849 2849 2837 2838 2838 2842 6,222 4814 4808 4808 4808 4796 4807 6,573 7978 7974 7981 7985 8006 7985 12,524 12736 12736 12725 12744 12716 12731 10,945 19358 19379 19390 19411 19416 19390 23,766 28228 28253 28261 28287 28296 28265 27,277 39622 39643 39639 39676 39701 39656 31,788 53611 53616 53641 53630 53645 53629 14,949 71068 71092 71105 71142 71093 71100 27,0510 91976 91987 91995 92021 92006 91997 17,3311 117985 117991 118015 118010 118025 118005 16,7412 145159 145329 145395 145401 145331 145323 97,81

DSPCyclesSA−Inicial =

204, 5 ·K3 + 581 ·K2 + 2140 ·K + 1597

Tb

[ciclos

seg

](7.6)

DSPCyclesSA−Iter =

(52, 9 ·K3 + 316, 9 ·K2 + 568, 6 ·K + 1962) ·MTb

[ciclos

seg

](7.7)

DSPCyclesSA−Iter =

26, 5 ·K4 + 158, 5 ·K3 + 284, 3 ·K2 + 981 ·KTb

[ciclos

seg

](7.8)

A complexidade computacional do algoritmo SA sera dada pela soma da Funcao Custo

Inicial com a funcao Iteracoes, dada pela equacao (7.9).

DSPCyclesSA =

26, 5 ·K4 + 363 ·K3 + 865, 3 ·K2 + 3121 ·K + 1597

Tb

[ciclos

seg

](7.9)

7.3 Complexidade para o Receptor SA-MuD Completo em Banda Base 50

Figura 7.6: Grafico da complexidade em DSP da Funcao Custo Inicial do SA.

7.3 Complexidade para o Receptor SA-MuD Com-

pleto em Banda Base

A complexidade computacional para o receptor SA-MuD completo sera dada pela

soma dos ciclos do detector convencional com os ciclos do algoritmo SA, sendo esta

mostrada na equacao (7.10).

DSPCyclesSA−MuD =

1120KN + 26, 5K4 + 363K3 + 865, 3K2 + 3121K + 3255

Tb

[ciclos

seg

](7.10)

A figura 7.8 mostra o comportamento da funcao do algoritmo SA bem como do re-

ceptor CD para um ganho de processamento N = 20.

Outra analise realizada foi do incremento de complexidade, onde este e dado pela

razao do numero de ciclos do receptor SA-MuD em relacao ao detector CD, sendo este

apresentado na equacao (7.11).

Inc. Complex. % =DSPCycles

SA−MuD

DSPCyclesCD

· 100% (7.11)

7.3 Complexidade para o Receptor SA-MuD Completo em Banda Base 51

Figura 7.7: Grafico da complexidade em DSP de cada Iteracao do algoritmo SAgerado com os dados da tabela 7.6.

A figura 7.9 mostra o incremento de complexidade ( em % ) do receptor SA-MuD

para ganhos de processamento de: N = 10, N = 15, N = 20, N = 25 e N = 30.

Ao se obter a complexidade computacional para o receptor SA-MuD completo em

banda base, realizou-se uma analise para verificar a capacidade maxima de processamento

do DSP, em termos de numeros maximos de usuarios e ganho de processamento.

Para esta analise foi considerado apenas usuarios de voz, com taxa de transferencia

padrao de um VOCODER1 de 8 Kbits/s.

A figura 7.10 mostra a comparacao do numero de ciclos necessarios para deteccao dos

bits com um ganho de processamento N = 4. Pode-se observar que o numero de usuarios

a qual o DSP consegue garantir a taxa de 8 Kbits/s para o ganho de processamento

estipulado e de 2 usuarios, enquanto o detector convencional consegue 5 usuarios.

Aumentando-se o ganho de processamento (N = 8), observa-se que esse numero de

usuarios e reduzido como pode ser observador na figura 7.11.

1voice + encoder - codificadores de voz do tipo ”Toll Quality”voice coders, tais como o ITU G.729,com taxa de dados final de 8 kbps.

7.4 Comparacao de Complexidade Computacional entre os Algotimos SA e LS 1 opt 52

Figura 7.8: Grafico da comparacao de ciclos entre a funcao do algoritmo SA e doreceptor CD - @ N = 20.

7.4 Comparacao de Complexidade Computacional en-

tre os Algotimos SA e LS 1 opt

Esta secao busca mostrar a comparacao da complexidade computacional entre os

algoritmos heurısticos SA e LS 1 opt em funcao do numero de ciclos que cada um realiza.

Como apresentado na secao anterior, a complexidade computacional para o recep-

tor SA-MuD e dado pela equacao (7.10). Em (MUSSI, 2009), defini-se a complexidade

computacional em DSP (numero de ciclos) para o algoritmo heurıstico de busca local

(LS 1 opt) como:

DSPCyclesSA−MuD =

26, 5K4 + 364, 2K3 + 854, 5K2 + 2381, 6K + 1120KN + 3202

Tb

[ciclos

seg

](7.12)

A figura 7.12 mostra a comparacao da complexidade computacional dos dois algo-

ritmos pra um ganho de processamento N = 15. Observa-se que estes apresentam uma

complexidade computacional muito proxima.

7.4 Comparacao de Complexidade Computacional entre os Algotimos SA e LS 1 opt 53

Figura 7.9: Grafico do incremento de complexidade do receptor.

Porem, para uma melhor analise e comparacao, realizou-se o estudo do incremento de

complexidade, dado por:

Inc. Complex.SAvs.LS % =DSPCycles

SA−MuD

DSPCyclesLS−MuD

· 100% (7.13)

A figura 7.13 mostra o incremento de complexidade ( em % ) do receptor SA-MuD

em relacao ao receptor LS-MuD para ganhos de processamento de: N = 10, N = 15, N =

20, N = 25 e N = 30.

Assim, pode-se observar araves da figura 7.13 que o algoritmo SA-MuD apresenta um

pequeno incremento na complexidade computacional quando comparado com o algoritmo

LS-MuD.

7.5 Calculo de Complexidade em Funcao do Numero de Operacoes 54

Figura 7.10: Grafico da capacidade maxima de processamento do DSP @ N = 4.

7.5 Calculo de Complexidade em Funcao do Numero

de Operacoes

Outro metodo utilizado para realizar a complexidade computacional do receptor SA-

MuD consistiu em analizar as operacoes de somas e multiplicacoes realizadas.

Como na analise de ciclos, tambem dividiu-se o programa em tres partes, sendo Re-

ceptor Convencional (MF + decisor abrupto), Funcao Custo Inicial e Iteracoes. Em cada

uma delas foi determinado o numero de somas e multiplicacoes realizadas em funcao do

numero de usuarios (K) e ganho de processamento (N).

A equacao (7.14) e a equacao (7.15) mostram, respectivamente, o numero de somas e

multiplicacoes realizadas pelo receptor convencional.

DSP SomasCD = 36 ·K ·N + 4 ·K (7.14)

DSPMult.CD = 28 ·K ·N + 2 ·K (7.15)


Figura 7.11: Grafico da capacidade maxima de processamento do DSP @ N = 8.

Para o calculo da Funcao Custo Inicial, o numero de operacoes realizadas sao:

DSP SomasSA−F.inicial = 20 ·K3 + 27 ·K2 + 50 ·K + 11 (7.16)

DSPMult.SA−F.inicial = 18 ·K3 + 19 ·K2 + 31 ·K (7.17)

Ja para parte Iteracoes, adotou-se um numero de iteracoes M = K/2 para convergencia

do algoritmo, como anteriormente ja adotado no calculo do numero de ciclos (Profile).

Assim, para cada iteracao, o numero de somas e multiplicacoes pode ser dado respectiva-

mente por:

DSP SomasSA−F.inicial =

[4 ·K3 + 18 ·K2 + 32 ·K + 21

]·M (7.18)

DSPMult.SA−F.inicial =

[3 ·K3 + 11 ·K2 + 16 ·K + 20

]·M (7.19)

O numero de somas da parte Iteracoes para o algoritmo SA e dado pela equacao (7.20)


Figura 7.12: Grafico da Complexidade computacional dos algoritmos SA e LS 1 opt @N = 15.

e multiplicacoes pela equacao (7.21).

DSP SomasSA−F.inicial = 2 ·K4 + 9 ·K3 + 16 ·K2 + 10, 5 ·K (7.20)

DSPMult.SA−F.inicial = 1, 5 ·K4 + 5, 5 ·K3 + 8 ·K2 + 10 ·K (7.21)


Figura 7.13: Grafico do incremento de complexidade do algoritmo SA em relacao aoLS 1 opt.

58

8 CONCLUSAO

Inicialmente encontrou-se grandes dificuldades na implementacao do trabalho em DSP,

principalmente com relacao a alocacao de memoria. O estudo de algumas literaturas sobre

DSP contribuiu para auxiliar a solucionar este problema de alocacao de memoria.

A implementacao do algoritmo heurıstico de recozimento simulado (Simulated Annea-

ling - SA) ao problema de deteccao MuD em canal AWGN sıncrono em plataforma DSP

resultou em um desempenho muito proximo ao obtido com o detector ML, porem com

uma reduzida complexidade computacional proporcionado pelo espaco de busca reduzido

inerente ao algoritmo heurıstico.

A utilizacao do algoritmo SA com sequencias de espalhamento aleatorias (pior caso)

mostrou que o sistema mesmo assim atinge otimo desempenho, mesmo em condicoes de

sistema com alto carregamento.

Pode-se observar que o algoritmo SA mostrou-se robusto ao aumento do carrega-

mento e a presenca do efeito near-far, porem apresentou uma reducao na velocidade de

convergencia quando houve tais variacoes nos parametros do sistema.

Assim, a implementacao em DSP de um detector Heur-MuD utilizando o algoritmo

SA mostrou-se possıvel em banda base, nao somente a parte heurıstica como tambem

o decisor abrupto e filtro casado, resultando excepcional melhoria de desempenho com

acrescimo marginal de complexidade em relacao ao detector convencional.

A analise atraves do tempo computacional (numero de ciclos do DSP) bem como o

numero de operacoes realizadas foi um fator importante na analise da complexidade com-

putacional para implementacao do detector SA-MuD. Conseguiu-se realizar a deteccao,

porem esta ficou limitada a um baixo ganho de processamento como tambem a poucos

usuarios ja que o processador do DSP utilizado no trabalho apresentava um clock de 225

MHz.

Portanto, para conseguir a deteccao de um maior numero de usuarios e garantir a

8.1 Trabalhos Futuros 59

taxa basica de transmissao de 8 Kbits/s, deve-se trabalhar com um processador mais

veloz, afim deste ser capaz de realizar todas as operacoes de estimativa e deteccao do

receptor SA-MuD. Algumas otimizacoes ainda podem ser realizadas no codigo para ajudar

na diminuicao da complexidade do receptor, entretanto o numero de ciclos necessarios

para implementacao do receptor ainda sera grande, exigindo um processador com alta

capacidade de processamento.

8.1 Trabalhos Futuros

Como trabalhos futuros, sao propostos:

• Implementacao e analise em DSP de outros algoritmos heurısticos para canais

AWGN sıncrono.

• Utilizacao de canais mais realistas, como canais assıncronos e/ou com desvaneci-

mento multipercurso.

• Estudo da complexidade computacional da implementacao de outras heurısticas em

processadores digitais de sinais.

60

Anexo A -- PROCESSADOR DIGITAL DE

SINAIS - DSP

A utilizacao de software para simulacoes computacionais como o MATLAB nao impoe

um determinado tempo para que tal simulacao ocorra. Porem, ao se trabalhar com

aplicacoes em tempo real, faz-se necessario a utilizacao de um processador digital de sinais,

conhecido como DSP (Digital Signal Processor) que implementara tais processamentos

de uma determinada amostra, antes que novos dados cheguem para serem processados

(ABRAO et al., 2007).

Os DSP’s podem ser empregados em diversas areas como tambem para processamentos

especıficos, onde deseja-se encontrar solucoes adaptativas para um determinado problema.

A simulacao em tempo real e uma area que tem sido bastante estudada ao longo dos

anos, existindo diversos trabalhos de programacao para controle de processos.

Assim, a questao da limitacao de tempo tornou-se um problema a ser solucionado,

pois garantir uma resposta certa em tempo real em alto nıvel torna-se complexo, especial-

mente para DSP’s onde sistemas com determinada taxas de dados devem ser analisados

(MARWEDEL, 1995).

A figura A.1 mostra o diagrama de blocos do kit DSK6713 da Spectrum Digital Inc.

Figura A.1: Diagrama de blocos do kit de desenvolvimento TMS320C6713

A.1 Ferramentas de suporte do DSK 61

A famılia de processadores digitais de sinal TMS320 e utilizada em uma ampla gama

de aplicacoes, como em comunicacoes, controles de processamento de voz, e assim por

diante. Tambem sao utilizados em telefones celulares, cameras digitais, televisao de alta

definicao (HDTV), radio, transmissao de fax, modems e outros dispositivos.

Estes dispositivos tambem podem ser utilizados em projetos experimentais, pois fornecem

uma maneira economica de apresentar em tempo real o processamento de sinais.

O DSP procura trabalhar principalmente com o processamento de sinal em tempo

real (real-time).

Sistemas analogicos com componentes eletronicos, como resistores, podem ser mais

sensıveis a mudancas de temperatura por exemplo, ja sistemas baseados em DSP sao

menos afetados pelas condicoes ambientais. Eles tambem tem uma vantagem de utilizar

microprocessadores, sendo de facil utilizacao, flexıveis e economicos.

A famılia de processadores TMS320C6x (C6x) sao microprocessadores com uma alta

velocidade de processamento contendo um tipo especializado de arquitetura e um conjunto

de instrucoes adequadas para o processamento de sinais.

A notacao C6x e utilizada para designar a famılia de DSP da Texas Instruments (TI

famılia TMS320C6000), onde a arquitetura deste processador digital de sinal esta adap-

tada para calculos numericos intensivos baseado na arquitetura VLIW, senso considerado

um dos melhores processadores da TI.

A famılia C6x da TI pode realizar diferentes tarefas, uma vez que permite a repro-

gramacao facilmente para diversas aplicacoes, tendo tido muito sucesso devido ao desen-

volvimento de baixo custo do software e hardware.

Processadores da famılia C6x incluem tanto dispositivos de ponto fixo (por exemplo,

C62x, C64x) e de ponto flutuante (por exemplo, C67x). O processador utilizado no

trabalho foi o C6713 de ponto flutuante muito util em aplicacoes que requerem calculos

intensivos.

A.1 Ferramentas de suporte do DSK

Desenvolvido pela Spectrum Digital Inc., o kit DSK6713 consiste em uma plataforma

de integracao entre o DSP TMS320C6713 e diversos componentes.

Para realizar a implementacao de programas no DSK6713 e necessaria a comunicacao

do kit com um computador atraves de uma porta USB, possibilitando a implementacao


de diversas aplicacoes no processador.

Para realizacao do projeto foram utilizadas as seguintes ferramentas:

• Kit da TI - DSP (DSK). O pacote inclui o Code Composer Studio (CCS), que fornece

o software necessario e ferramentas de apoio com um ambiente de desenvolvimento

integrado (IDE), que reune um compilador C, assembler, linker e debugger.

• A placa, mostrada na figura A.2, contem o processador TMS320C6713 (C6713) de

ponto flutuante, bem como um codec estereo de 32-bits para entrada e saıda de

dados.

Figura A.2: Placa do kit de desenvolvimento DSK6713

• A conexao da placa do kit DSK se conecta a porta USB do PC atraves de um cabo.

O pacote DSK inclui tambem conversores AD e DA, 16MB de memoria SDRAM e

256KB de memoria flash. Quatro conectores de entrada e saıda de dados: MIC IN para

entrada de microfone, LINE IN, LINE OUT para saıda de linha e uma entrada para fone

de ouvido(multiplexado com saıda de linha). O processador opera com uma frequencia

de 225MHz.

Existem na placa do kit reguladores de tensao que fornecem uma tensao de 1,26 V

para o C6713 e 3,3 V para a sua memoria e perifericos.

A.1.1 DSP TMS320C6713

O TMS320C6713 (C6713) e baseado na arquitetura VLIW, que esta muito bem adap-

tado para algoritmos numericamente intensivos. A memoria de programa interno esta


estruturada de modo que um total de oito instrucoes podem ser buscadas a cada ciclo.

Outra caracterıstica do DSP C6713 e sua memoria interna de 264 kB (8kb como L1P

e L1D e 256kB de memoria cache L2 compartilhado entre o programa e os dados), seis

unidades de logica aritmetica (ULA) e duas unidades de multiplicadores, um barramento

de 32 bits de endereco de 4 GB e dois conjuntos de registradores de 32 bits.

64

Anexo B -- SEQUENCIAS DE

ESPALHAMENTO

A divisao por sequencias, cada uma sendo um codigo para um determinado usuario,

mostra-se uma boa estrategia de acesso multiplo ja que melhora o desempenho com relacao

a interferencia (HAYKIN; MOHER, 2005). No sistema CDMA tem-se uma ortogonalidade

nos codigos dos usuarios. Para garantir tal ortogonalidade, cada sequencia atribuıda a

um usuario [sk(q)] deve ter uma funcao de modelamento de sımbolo diferente.

gk =N∑

q=1

skgc (t− qTc) 0 ≤ t ≤ T (B.1)

Assim, a ortogonalidade aproximada entre o k-esimo e o j-esimo usuario para diferentes

deslocamentos de tempo t pode ser expresso como na equacao (B.2):

Rjk (τ) =

∫ ∞−∞

gj (t+ τ) g∗k (t) dt ≈ 0 para j 6= k (B.2)

Com a equacao (B.2), assumindo-se que o receptor esta usando um filtro casado

(MFB), a correlacao cruzada de dois sımbolos diferentes e aproximadamente zero para

todos os deslocamentos de tempo τ . Outro requisito de ortogonalidade que minimiza

varios canais e efeitos no receptor e mostrado em equacao (B.3):

Rkk (τ) ≈ 0 para τ > 0 (B.3)

Portanto, a escolha das sequencia de espalhamento ira determinar se as equacoes

acima serao satisfeitas.

B.1 Sequencias Aleatorias 65

B.1 Sequencias Aleatorias

Como o proprio nome indica, tais sequencias sao geradas aleatoriamente, onde pode-se

definir a correlacao cruzada entre duas sequencias aleatorias x e y pela equacao (B.4):

Rxy (k) = E

[1

N

N∑n=1

xnyn+k

](B.4)

Ja a funcao de autocorrelacao da sequencia aleatoria e dada pela equacao (B.5):

Rxx (k) = E

[1

N

N∑n=1

xnyn+k

]=

{0 para k 6= 0

1 para k = 0(B.5)

Portanto, ao se considerar que a autocorrelacao e normalizada tal que Rxx = 1, a

correlacao cruzada media de duas sequencias aleatorias e definida na equacao (B.6).

E[|Rxy|2

]= E

( 1

N

N∑n=1

xnyn

)2 =

1

N(B.6)

Atraves da equacao (B.6) observa-se que a interferencia entre duas sequencias aleatorias

e inversamente proporcional ao comprimento da sequencia.

B.2 Sequencias Walsh-Hadamard

Considerando que as sequencias estao sincronizadas no tempo, ou seja, τ = 0, as

relacoes de ortogonalidades podem ser satisfeitas e os codigos resultantes sao chamados de

Sequencias Walsh-Hadamard. A implementacao de tais sequencias permite-se construir 2n

sequencias ortogonais de comprimento 2n, tendo os codigos uma pequena autocorrelacao

e correlacao cruzada em deslocamento de tempo diferentes de zero.

B.3 Sequencias de Maximo Comprimento (SMC)

Os codigos de Walsh-Hadamard nao possuem boas propriedades de ortogonalidade

quando eles nao se alinham no tempo. Para aplicacoes em comunicacoes, precisa-se de

sequencias com propriedades semelhantes as das sequencias aleatorias, devendo ser gerada

de forma simples no transmissor e receptor. Uma classe de sequencias que garante tais

B.4 Sequencias Gold 66

condicoes e a Sequencia de Maximo Comprimento ou Sequencias m. As sequencias m tem

um comprimento de N = 2m - 1 chips, constituıdos por 2m−1 valores logicos 1 e 2m−1 - 1

valores logicos 0 (GOULD; STEELE, 2001). A funcao de auto correlacao e periodica em N,

com um pico de N para zero e -1 para outros valores como e mostrado na figura B.1.

Figura B.1: Funcao de autocorrelacao de sequencias m (SMC).

Sao geradas a partir de um registrador de deslocamento binario com realimentacao.

Como a funcao de autocorrelacao circular para uma sequencia pode ser expresso por

Rjj (k) =1

N

N∑q=1

s (q) s ((q + k)mod (N)) (B.7)

onde N = 2m - 1, pode-se determinar a autocorrelacao normalizada para a sequencia

de comprimento maximo na equacao (B.8):

Rjj (k) =

{1 para k = 0−1N

para k 6= 0(B.8)

Quanto maior for o ganho de processamento N (numero de chips), melhores serao as

propriedades de autocorrelacao das sequencias de comprimento maximo.

B.4 Sequencias Gold

A sequencia Gold propoe que seja somado duas sequencias de maximo comprimento

tendo estas o mesmo tamanho, porem usando geradores diferentes. Os codigos gerados

da soma das saıdas de dois geradores de sequencias m, dao origem a uma nova sequencia

B.4 Sequencias Gold 67

de espalhamento (sequencia Gold). A correlacao cruzada das sequencias Gold e aproxi-

madamente

|Rjk (τ)| =≤ 1

N+

2√N

j 6= k (B.9)

onde N = 2m -1.

68

Anexo C -- Metodo de Simulacao Monte

Carlo

Para realizacoes das simulacoes foi utilizado o metodo Monte Carlo. Geradores

mecanicos de numeros aleatorios foram usados primeiramente para simular jogos de azar,

dando origem ao nome de Metodo de Monte Carlo, referindo-se a cidade de Monte Carlo,

cidade dos mais famosos bingos do mundo. Esse metodo de simulacao procura atraves

das propriedades estatısticas dos numeros aleatorios e em utilizar tecnicas de calculo

probabilısticos para a garantia de um resultado correto (CIRIACO, 2004).

Embora existam muitas variacoes da tecnica de Monte Carlo, esse metodo envolve

basicamente a simulacao de um experimento aleatorio usando meios artificiais.

Assim, para estimar a taxa de erro de bits em um sistema de comunicacao, pode-se

definir a simulacao de Monte Carlo como um modelo de sistema de comunicacao mostrado

na figura C.1 com os sinais de entrada U (t), V (t) e W (t), sendo esses processos aleatorios.

O objetivo e encontrar as propriedades estatısticas de Y (t) ou o valor esperado de alguma

funcao g (Y (t)) de Y (t) (JERUCHIM; BALABAN; SHANMUGAN, 2002).

Figura C.1: Definicao da simulacao de Monte Carlo.

A simulacao de Monte Carlo mostrada na figura C.2 para estimar a taxa de erro de

bits em um sistema de comunicacao digital envolve as seguintes etapas.

1. Gerar valores de amostra da sequencia de bits de entrada A(k), k = 1, 2, ..., N, e

as amostras de ruıdo N (j), j = 1, 2, ..., Mn (a taxa de amostragem e m amostras

por bit).


2. Processar estas amostras atraves dos modelos dos blocos funcionais e gerar uma

sequencia de saıda Y(k).

3. Estimar E (g (Y (k)) como

Pe =1

N

N∑k=1

g (Y (k)) (C.1)

Figura C.2: Modelo de simulacao de um sistema de comunicacao.

A precisao das estimativas obtidas atraves de simulacao de Monte Carlo dependera

da estimativa dos procedimentos utilizados, do tamanho das amostras N, a capacidade

de reproduzir valores amostrados da entrada, e os pressupostos de modelagem e aprox-

imacoes.

Em geral, a precisao sera proporcional a 1/√N , o que significa que um numero grande

de amostras devera ser simuladas a fim de obter estimativas precisas atraves de simulacoes

de Monte Carlo (CIRIACO, 2004).

No algoritmo implementado, o metodo de Monte Carlo e utilizado para a definir o

desempenho do sistema, levando-se em conta a taxa de erro de bit. Para cada ponto da

SNR foi utilizado um valor determinado de nerros que assim definia o numero de trials

utilizados nas iteracoes.

A BER estimada e calculada da forma:

Pe =nerros

trials(C.2)

Se o numero de trials for elevado, a probabilidade de erro Pe ira ser a menor possıvel,

mas implementar computacionalmente um numero elevado de trials torna-se um processo


inviavel. Assim, trabalha-se com um numero tal de trials ou nerros que propicie um

resultado confiavel.

71

Anexo D -- Principais Funcoes e Comandos

Implementados

A seguir, estao descritos as funcoes e comandos implementados para o processamento

do canal DS-CDMA com deteccao multiusuario em DSP.

A figura D.1 mostra a inicializacao da comunicacao RTDX, habilitando os canais de

entrada e saıda de dados do DSP para comunicacao com o MATLAB. Mostra tambem

a recepcao da sequencia de espalhamento e a amplitude dos sinais dos usuarios enviadas

pelo MATLAB.

A funcao correlacao calcula no DSP a correlacao (R) atraves dos paramentros passa-

dos a ela (sequencia de espalhamento, numero de usuarios e ganho de processamento).

Figura D.1: Rotinas e funcoes implementadas em DSP.

A funcao mostrada na figura D.2 diz respeito ao decisor convencional com decisor

abrupto implementado em DSP. Esta funcao retorna o vetor de bits estimado (b) para

um canal AWGN sıncrono.

A terceira rotina (figura D.3) diz respeito ao algoritmo SA-Mud implementando em

Anexo D -- Principais Funcoes e Comandos Implementados 72

Figura D.2: Funcao implementada para o decisor convencional com decisor abrupto.

DSP atraves da descricao apresentada no capıtulo 5. O algoritmo retorna o melhor ve-

tor de bits estimado (vbest), onde este e enviado atraves da comunicacao RTDX para o

MATLAB para geracao das figuras de merito.

Figura D.3: Funcao do algoritmo Simulated Annealing implementada em DSP.

As rotinas e funcoes acima sao as principais implementadas1 para construcao deste

trabalho.

1outras rotinas eram chamadas internamente

73

Referencias

ABRAO, T.; CAMARGO, V. L. A.; PEREIRA, R. V.; TAKAYAMA, D. K.Desenvolvimento e implementacao rapida de filtros adaptativos para processadoresdigitais de sinais tms320c6713 utilizando o simulink. In: . Londrina: Brasil, 2007. p. 13.

ABRAO, T.; CIRIACO, F. D. N.; JESZENSKY, P. J. E. Deteccao multiusuarioutilizando algoritmos heurısticos evolucionarios e de busca local. In: Semina - CienciasExatas e Tecnologicas. Londrina: Brasil, 2004. (Semina).

CIRIACO, F. D. N. Algoritmos Heurısticos Aplicados a Deteccao MultiusuarioDS-CDMA. Londrina - PR: Universidade Estadual de Londrina - UEL, 2004. 120 p.

GOLDBARG, M. C.; LUNA, H. P. L. Otimizacao Combinatoria e Programacao Linear.Rio de Janeiro: Campus, 2000. 649 p.

GOULD, C. L. P.; STEELE, R. GSM, cdmaOne and 3G Systems. [S.l.]: John WileySons, 2001.

HAUPT, R. L.; HAUPT, S. E. Practical Genetic Algorithms. Hoboken: John WileySons, Ltd, 2004.

HAYKIN, S.; MOHER, M. Modern Wireless Communications. [S.l.]: Pearson Education,2005.

JERUCHIM, M. C.; BALABAN, P.; SHANMUGAN, K. S. Simulation of CommunicationSystems. New York: Kluwer Academic Publishers, 2002.

KATAYAMA, K.; NARIHISA, H. Performance of simulated annealing-based heuristicfor unconstrained binary quadratic programming problem. [S.l.]: European Journal ofOperational Research, 2001. 103-119 p.

LATHI, B. P. Modern Digital and Analog Communication Systems. [S.l.]: OxfordUniversity Press, Inc., 1998.

LEE, J. S.; MILLER, L. E. CDMA Systems Engineering Handbook. [S.l.]: Artech HousePublishers, 1998.

LUDERS, C.; SCHULZE, H. Theory and application of OFDM and CDMA. [S.l.]: JohnWiley Sons, Ltd, 2005.

MARWEDEL, P. Code Generation for Embedded Processors. [S.l.]: Hardcover, 1995.

MUSSI, A. M. Implementacao de Subsistemas DS/CDMA Utilizando Plataforma DSPcom Abordagem Heurıstica. Londrina - PR: Universidade Estadual de Londrina - UEL,2009. 102 p.

Referencias 74

TORRIERI, D. Principles of Spread-Spectrum Communication Systems. [S.l.]: SpringerScience + Business Media, Inc., 2005.

VERDU, S. Optimum multiuser asymptotic efficiency. IEEE Transactions onCommunications, p. 890–897, September 1986.

VERDU, S. Multiuser Detection. USA: Cambridge University Press, 1998. ISBN0-521-59373-5.

Documents

Aplicabilidade de Heur sticas na Otimiza˘c~ao de ...da otimiza˘c~ao da etapa de detec˘c~ao no receptor. Abstract Analytical approaches often do not solve problems, having to use