[pt] Este trabalho apresenta uma formulação geral da teoria de sensibilidade de filtros digitais lineares e invariantes no tempo, representados por variáveis de estado nas formas canônicas Diagonal e Jordan, com relação aos seus coeficientes quantizados devido ao tamanho finito da palavra. É estabelecida uma estrutura única que permite a análise de sensibilidade com respeito aos vários parâmetros do modelo de estado. São estudados sistemas compostos por cascatas de blocos e feita a análise de sensibilidade, considerando que há presença de elementos quantizados de blocos. É feita a análise de complexidade computacional das formulações estudadas. / [en] This work presents a general formulation on sensitivity analysis of digital linear filters modeled by state variables in canonical forms (Diagonal and Jordan), with respect to its coeficients which are aproximated due to the finite size of the word. We studied systems of cascated blocks which present quantization in its coefficients. It is established one block structure that permits the sensitivity analysis with respect to all the parameters of the state model. At last, the expressions complexity computational is calculated.

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

[pt] Os códigos de prefixo têm importância fundamental na comprenssão e transmissão de dados. Estes códigos também apresentam relações com problemas de busca. Neste tese, apresentamos novos resultados estruturais e algorítimos sobre a classe dos códigos de prefixo. Explicamos teoricamente as boas taxas de compressão observadas para alguns métodos utilizados na prática. Propomos também algoritmos eficientes para construção de códigos de prefixo ótimos e variantes. Os principais resultados aqui descritos são os seguintes: - um novo algoritmo paralelo para construção de códigos de prefixos ótimos: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo alfabéticos: - um algoritmo aproximativo e linear para construção de códigos de prefixo com restrição de comprimento: - um algoritmo aproximativo com complexidade 0(n log n) para construção de códigos de prefixo alfabéticos com restrição de comprimento: - uma nova versão de algoritmo WARM-UP com complexidade fortemente polinomial: - um algoritmo linear para reconhecer códigos de prefixo ótimos com restrição de comprimento: - uma prova afirmativa da conjectura de Vitter sobre o desempenho dos códigos de Huffmann dinâmicos construídos pelo algoritmo FGK (Faller, Gallanger e Knuth) / [en] The prefix codes play an important role in data compression and data communication. These codes also present relation with search problems. In this thesis, we present new structural and algorithmic results concerning the prefix code class. We theoretically explain results related to the high compression rates of some methods that have been used for pratical purposes. We also propose efficient algorthims for constructing optimal prefix codes and some variants. The major results are listed below: -a new parallel algorithm for constructing optimal prefix codes: -a sharp upper bound for the compression loss introduced due usage of length restricted prefix codes: -an upper bound for the compression loss introduced due the usage of length restricted alphabetic prefix codes: -an 0(n log n) time approximative algorithm for constructing lenght restricted prefix code: -a 0(n log n) time approximative algorithm for constructing lenght restricted alphabetic prefix code: -a strongly polinomial version for the WARM-UP algorithm: -a linear time algorithm for recognizing optimal length restricted prefix codes: -a proof for Vitter´s conjecture about the perfomance of the Dynamic Huffman Codes constructed by FGK (Faller, Gallager and Knuth) algorithm.

[pt] A dissertação apresenta detalhadamente o algoritmo de fatoração de Shor, tanto em termos de sua execução passo a passo como mediante sua representação em forma de circuito, abordando aspectos tanto de sua parte clássica como de sua parte quântica. Inicialmente são apresentados aspectos de teoria dos números indispensáveis para a compreensão do algoritmo e em seguida são desenvolvidos conceitos e propriedades de mecânica quântica e de informação quântica pertinentes. Em atenção ao caráter eminentemente estocástico do algoritmo realiza-se um estudo de sua fonte estocástica e demonstram-se os principais teoremas que embasam a avaliação de sua probabilidade de sucesso. Desenvolvem-se exemplos de simulação clássica do algoritmo. Finalmente, a eficiência do algoritmo de fatoração de Shor é comparada com a de algoritmos clássicos. / [en] The dissertation presents in detail Shor s factoring algorithm, including its execution step by step and its representation in the form of a circuit, addressing aspects of both its classical and its quantum parts. Aspects of number theory indispensable to understand the algorithm are presented, followed by a development of concepts and properties of quantum mechanics and quantum information. Considering the eminently stochastic character of the algorithm, a study of its stochastic source is carried out and the main theorems that support the evaluation of its probability of success are proved. Examples of classical simulation of the algorithm are developed. Finally, the efficiency of Shor s factoring algorithm is compared with that of classical algorithms.

[pt] Com o desenvolvimento tecnológico no setor de telecomunicações, o espectro radioelétrico está quase totalmente ocupado com um grande número de múltiplas atribuições para os muitos serviços sem fio de aplicação comercial e, também, não comercial, tais como defesa, controle de tráfego aéreo e exploração científica. O espectro eletromagnético é um recurso natural precioso e escasso, por isso, importantes esforços estão sendo direcionados para o desenvolvimento de rádios cognitivos, com capacidade de sensoriar o uso do espectro e utilizar frequências momentaneamente disponíveis de forma oportunista. O rastreamento e a utilização de intervalos espectrais, ou white spaces, através da tecnologia de rádios cognitivos, permitirá aumentar a eficiência de uso do espectro com a introdução de novos serviços de telecomunicações a serem explorados por usuários secundários, obrigados a não interferir ou a provocar interferência muito limitada nos usuários primários. O objetivo geral deste trabalho é avaliar os principais algoritmos de detecção dos intervalos espectrais (Detector de Energia, Detecção do Valor Absoluto de Covariância, Sensoriamento de Covariância Espectral) por meio de simulações com dados experimentais obtidos em campanhas de medições e testes em laboratório. Os algoritmos foram testados para avaliar o seu desempenho em termos de probabilidade de detecção dada uma probabilidade de falso alarme requerida, complexidade computacional e robustez quanto a relações sinal-a-ruído baixas. Os dados experimentais utilizados provêm de campanhas de medidas realizadas em ambiente urbano na faixa de 3.5 GHz. / [en] With the technological development of the telecommunications industry, the radio spectrum is almost fully occupied with a large number of multiple assignments for wireless services for both commercial and non-commercial applications, such as defense, air traffic control and scientific exploration. The electromagnetic spectrum is a precious and scarce natural resource. Therefore, a considerable effort is being directed at the development of cognitive radios, capable of sensoring the spectrum and using momentarily available frequency bands in an opportunistic way. The tracking and using of these spectral intervals, or white spaces, using cognitive radio technology will enhance the efficiency of the spectrum use and allow the introduction of new telecommunications services to be exploited by secondary users, obliged not to interfere or produce very limited interference to primary users. The aim of this study is to evaluate the main algorithms for detection of spectral intervals (Energy Detector, Detection of Covariance Absolute Value, Spectral Covariance Sensing) through simulations with experimental data obtained in field measurements campaigns. The algorithms were tested to evaluate their performance in terms of detection probability given a required false alarm probability, computational complexity and robustness in low signal-to-noise conditions. The experimental data used comes from the measurements campaigns in urban environments at the 3.5 GHz band.

[pt] Este trabalho tem como finalidade analisar diferentes estratégias de detecção passíveis de aplicação em sistemas de transmissão OFDM (Orthogonal Frequency Division Multiplexing) operando em canais que variam rapidamente no tempo. Além dos métodos clássicos de detecção lineares tais como filtro casado, Zero Forcing e MMSE (Minimum Mean-Square Error), outras duas técnicas são estudadas, abrangendo também combinações entre elas. A primeira é a técnica de cancelamento paralelo de interferência (PIC - Parallel Interference Cancellation), a segunda é a detecção por busca por verossimilhança ascendente (LAS – Likelihood Ascent Search), ambas empregadas em conjunção com o filtro casado. Esse trabalho apresenta também um estudo dos efeitos de uma estimativa imperfeita do canal, no desempenho dos esquemas de detecção aqui enfocados. Os resultados dos experimentos são analisados em termos da taxa de erro de bit (BER) e custo computacional (complexidade)associado a estes esquemas. / [en] This work analyzing different detection strategies that can be applied in OFDM (Orthogonal Frequency Division Multiplexing) transmission systems over fast time-varying channels. In addition to classical linear methods of detection such as a Matched Filter, Zero Forcing and MMSE, two other techniques are studied, also encompassing combinations of them. The first is the Parallel Interference Cancellation (PIC) technique, the second is Likelihood Ascent Search (LAS), both used in conjunction with the Matched Filter. This work also presents a study of the effects of imperfect channel estimation on the performance of the detection schemes studied here. The results of the experiments are analyzed in terms of bit error rate (BER) and computational cost (complexity) associated with these schemes.

[pt] Este trabalho tem como finalidade o estudo das possibilidade do sistema GFDM (Generalized Frequency Division Multiplexing). Para o estudo feito foi apresentado um modelo matricial para representar os sinais gerados no sistema GFDM, a semelhança do modelo de sinal do sistema OFDM (Orthogonal Frequency Division Multiplexing). Tal modelo permitiu a obtenção de expressões analíticas para a Densidade Espectral de Potência (DEP, Spectral Power Density) dos sinais e sua comparação com a DEP dos sinais transmitidos em sistemas OFDM. A partir do modelo matricial apresentado são estudados o desempenho de diferentes tipos de equalizadores/detectores lineares clássicos passíveis de utilização neste sistema de comunicações digitais, tais como Zero Forcing, Minimum Mean Square Error e Matched Filter. Além disso o trabalho propõe e analisa o desempenho resultante da aplicação de técnicas de supressão de interferência PIC (Parallel Interference Cancellation) em conjunto com os detectores lineares mencionados e dos detectores LAS (Likelihood Ascent Search) precedidos por equalizadores Matched Filter (MF-LAS). O número de estágios PIC realizados em cada detecção é controlado por uma estratégia de parada baseada na métrica de distância. Diferentes esquemas de detecção MF-LAS em conjunto com PIC são também propostos e examinadas. Finalmente, partindo do modelo matricial desenvolvido neste trabalho é realizada a estimação de canal empregando a estratégia de símbolos pilotos ortogonais. As diferentes estratégias de detecção examinadas para o sistemas GFDM são comparadas em termos de desempenho BER (Bit Error Rate) e da complexidade computacional associada aos respectivos detectores. Comparações entre os sistemas GFDM e OFDM com destaque na complexidade na geração de sinais, eficiência espectral e desempenho estão também incluídos nesta dissertação. / [en] The main goal of the presented work is to study the possibilities of the GFDM system (Generalized Frequency Division Multiplexing). For achieving this purpose, a matrix model is presented which represents the signals generated in the GFDM system, similar to the signal model of the OFDM (Orthogonal Frequency Division Multiplexing) system. This model allows the obtainment analytical expressions for the Spectral Power Density (DEP) of the signals and their comparison with the DEP of the signals transmitted in OFDM systems. Furthermore, we study the performance of different types of classical linear equalizers/detectors that can be used in the digital communications systems, such as Zero Forcing, Minimum Mean Square Error and Matched Filter. In addition, we propose and analyze the performance resulting from the application of PIC (Parallel Interference Cancellation) interference suppression techniques together with the linear detectors mentioned and LAS (Likelihood Ascent Search) detectors preceded by Matched Filter (MF-LAS) equalizers. The number of PIC stages performed at each detection is controlled by a stop strategy based on the distance metric. Different MF-LAS detection schemes together with PIC are also proposed and examined. Finally, the channel estimation is performing based on the matrix model developed in this work and using orthogonal pilots symbols. The differents strategies of detection examined for GFDM systems are compared in terms of BER performance (Bit Error Rate) and the computational complexity associated with the respective detectors. Comparisons between GFDM and OFDM systems based on criterions as the complexity of the signal generation, spectral efficiency and performance are also included in this dissertation.