Esta dissertação de mestrado aborda formulações computacionais e algoritmos para a busca e extração de padrões em cadeias biológicas. Em particular, o presente texto concentra-se nos dois problemas a seguir, considerando-os sob as distâncias de Hamming e Levenshtein: a) como determinar os locais nos quais um dado padrão ocorre de modo aproximado em uma cadeia fornecida; b) como extrair padrões que ocorram de modo aproximado em um número significativo de cadeias de um conjunto fornecido. O primeiro problema, para o qual já existem diversos algoritmos polinomiais, tem recebido muita atenção desde a década de 60, e ganhou novos ares com o advento da biologia computacional, nos idos dos anos 80, e com a popularização da Internet e seus mecanismos de busca: ambos os fenômenos trouxeram novos obstáculos a serem superados, em razão do grande volume de dados e das bastante justas restrições de tempo inerentes a essas aplicações. O segundo problema, de surgimento um pouco mais recente, é intrinsicamente desafiador, em razão de sua complexidade computacional, do tamanho das entradas tratadas nas aplicações mais comuns e de sua dificuldade de aproximação. Também é de chamar a atenção o seu grande potencial de aplicação. Neste trabalho são apresentadas formulações adequadas dos problemas abordados, assim como algoritmos e estruturas de dados essenciais ao seu estudo. Em especial, estudamos a extremamente versátil árvore dos sufixos, assim como uma de suas generalizações e sua estrutura irmã: o vetor dos sufixos. Grande parte do texto é dedicada aos filtros baseados em q-gramas para a busca aproximada de padrões e algumas de suas mais recentes variações. Estão cobertos os algoritmos bit-paralelos de Myers e Baeza-Yates-Gonnet para a busca de padrões; os algoritmos de Sagot para a extração de padrões; os algoritmos de filtragem de Ukkonen, Jokinen-Ukkonen, Burkhardt-Kärkkäinen, entre outros. / This thesis deals with computational formulations and algorithms for the extraction and search of patterns from biological strings. In particular, the present text focuses on the following problems, both considered under Hamming and Levenshtein distances: 1. How to find the positions where a given pattern approximatelly occurs in a given string; 2. How to extract patterns which approximatelly occurs in a certain number of strings from a given set. The first problem, for which there are many polinomial time algorithms, has been receiving a lot of attention since the 60s and entered a new era of discoveries with the advent of computational biology, in the 80s, and the widespread of the Internet and its search engines: both events brought new challenges to be faced by virtue of the large volume of data usually held by such applications and its time constraints. The second problem, much younger, is very challenging due to its computational complexity, approximation hardness and the size of the input data usually held by the most common applications. This problem is also very interesting due to its potential of application. In this work we show computational formulations, algorithms and data structures for those problems. We cover the bit-parallel algorithms of Myers, Baeza-Yates-Gonnet and the Sagots algorithms for patterns extraction. We also cover here the oustanding versatile suffix tree, its generalised version, and a similar data structure: the suffix array. A significant part of the present work focuses on q-gram based filters designed to solve the approximate pattern search problem. More precisely, we cover the filter algorithms of Ukkonen, Jokinen-Ukkonen and Burkhardt-Kärkkäinen, among others.

Ce travail vise la modélisation au niveau système, en langage SystemC-AMS, et la simulation d'un émetteur-récepteur au standard Bluetooth Low Energy (BLE). L'objectif est d'analyser la relation entre les performances, en termes de BER et la consommation d'énergie du transceiver. Le temps de simulation d’un tel système, à partir de cas d’étude (use case) réaliste, est un facteur clé pour le développement d’une telle plateforme. De plus, afin d’obtenir des résultats de simulation le plus précis possible, les modèles « haut niveau » doivent être raffinés à partir de modèles plus bas niveau où de mesure. L'approche dite Meet-in-the-Middle, associée à la méthode de modélisation équivalente en Bande Base (BBE, BaseBand Equivalent), a été choisie pour atteindre les deux conditions requises, à savoir temps de simulation « faible » et précision des résultats. Une simulation globale d'un système de BLE est obtenue en intégrant le modèle de l'émetteur-récepteur dans une plateforme existante développée en SystemC-TLM. La simulation est basée sur un système de communication de deux dispositifs BLE, en utilisant différents scénarios (différents cas d'utilisation de BLE). Dans un premier temps nous avons modélisé et validé chaque bloc d’un transceiver BT. Devant le temps de simulation prohibitif, les blocs RF sont réécrits en utilisant la méthodologie BB, puis raffinés afin de prendre en compte les non-linéarités qui vont impacter le couple consommation, BER. Chaque circuit (chaque modèle) est vérifié séparément, puis une première simulation système (point à point entre un émetteur et un récepteur) est effectuée / This work aims at system-level modelling a defined transceiver for Bluetooth Low energy (BLE) system using SystemC-AMS. The goal is to analyze the relationship between the transceiver performance and the accurate energy consumption. This requires the transceiver model contains system-level simulation speed and the low-level design block power consumption and other RF specifications. The Meet-in-the-Middle approach and the Baseband Equivalent method are chosen to achieve the two requirements above. A global simulation of a complete BLE system is achieved by integrating the transceiver model into a SystemC-TLM described BLE system model which contains the higher-than-PHY levels. The simulation is based on a two BLE devices communication system and is run with different BLE use cases. The transceiver Bit-Error-Rate and the energy estimation are obtained at the end of the simulation. First, we modelled and validated each block of a BT transceiver. In front of the prohibitive simulation time, the RF blocks are rewritten by using the BBE methodology, and then refined in order to take into account the non-linearities, which are going to impact the couple consumption, BER. Each circuit (each model) is separately verified, and then a first BLE system simulation (point-to-point between a transmitter and a receiver) has been executed. Finally, the BER is finally estimated. This platform fulfills our expectations, the simulation time is suitable and the results have been validated with the circuit measurement offered by Riviera Waves Company. Finally, two versions of the same transceiver architecture are modelled, simulated and compared

Depuis plus de trois décennies, l'un des aspects par lequel se manifeste la mondialisation est la mobilité internationale des firmes et des facteurs de production. L'interdépendance croissante des économies, qui résulte de l'expansion des échanges et du développement des mouvements des capitaux, est devenue incontournable. La mondialisation a donné lieu à la promotion du libéralisme économique, et au développement d'un processus mondialisé des activités, dans lesquels les IDE se font une place centrale, dans les politiques de développement des pays d'accueil. Qu'ils soient pays développés ou PED, ces derniers se livrent à une concurrence acerbe, pour l'attractivité des flux d'IDE sur leur territoire. Les FMN ont gagné une place centrale dans ce nouveau schéma. Après avoir suscité la méfiance et l'hostilité des gouvernements des PED, elles sont devenues une composante principale dans la stratégie de développement. Suivant leurs propres préoccupations (gains de productivité, sources d'approvisionnement, etc), les FMN établissent des stratégies dans une perspective internationale, et intègrent dans les activités leur responsabilité sociale et environnementale. Les IDE ont fait l'objet d'une forte controverse sur leurs potentialités à faire profiter les pays d'accueil des « spillovers ». Une inégale répartition des flux d'IDE, amène les PED à mettre en place des politiques d'attractivité ambitieuses (exonérations fiscales, subventions, etc.). L'Algérie a engagé, à l'instar d'autres PED, une série de réformes pour s'inscrire dans une nouvelle logique qui consacre les lois du marché et la libéralisation de l'économie touchant tous les secteurs d'activité. L'objectif de cette thèse est d'évaluer empiriquement les déterminants d'attractivité des IDE dans le modèle algérien, de la conduite de sa politique de promotion et de son évaluation. La qualité des institutions est bel et bien validée comme déterminant central dans la conduite de la politique d'attractivité de l'Algérie. La construction de la matrice d'attractivité a révélé que l'Algérie se place dans le cercle des « pays potentiels », qui pourraient figurer un jour dans la « short-list », à condition d'améliorer certaines composantes de leur attractivité. Des réformes cohérentes restent à faire pour une insertion effective dans l'économie internationale. / For over three decades, one aspect by which manifests globalization is the international mobility of firms and factors of production. Growing interdependence of economies resulting from the expansion of trade and development of capital movements has become unavoidable. Globalization has given rise to the promotion of economic liberalism, and development of a process of global activities in which FDI are central in the development policies of host countries. Whether developed or developing countries, these one are engaged in a bitter competition for FDI attractiveness of flux of FDI in their territory. The MNF has taken a central place in this new scheme. After arousing the suspicion and hostility of the governments of developing countries, they have become a key component in the strategy of development. Following their own concerns (productivity gains, exoneration, etc.), the MNF gone to research an international perspective, and integrate their activities in the social and environmental responsibility. The FDI has been subject of an important controversy over their potential to benefit the host countries of the "spillover". An unequal distribution of FDI, make the developing countries to take up an attractive ambitious policies (tax holidays, subsidies etc.). Algeria has committed, like other developing countries, a series of reforms to be part of a new logic that embodies the laws of the market and liberalization of the economy, affecting all sectors of activity. The objective of this thesis is to empirically assess the determinants of FDI attraction in the Algerian model, the conduct of its promotion policy and its evaluation. Quality of institutions is indeed well validated as a central determinant in the conduct of political attractiveness of Algeria. The construction of the matrix of attractiveness revealed that Algeria is located in the circle of ?potential countries", and that could one day appear in the "short list", provided certain components to improve their attractiveness. Consistent reforms are still needed for effective integration into the international economy.

With the increasing demand for faster communication systems, soon data rates in the terabit regime (100 Gbit/s and beyond) are required, which yields new challenges for the design of analog-to-digital converters (ADCs) since high bandwidths imply high sampling rates. For sampling rates larger than 300MHz, which we now achieve with 5G, the ADC power consumption per conversion step scales quadratically with the sampling rate. Thus, ADCs become a major energy consumption bottleneck. To circumvent this problem, we consider digital receivers based on 1-bit quantization and oversampling. We motivate this concept by a brief comparison of the energy efficiency of a recently proposed system employing 1-bit quantization and oversampling to the conventional approach using high resolution quantization and Nyquist rate sampling. Our numerical results show that the energy efficiency can be improved significantly by employing 1-bit quantization and oversampling at the receiver at the cost of increased bandwidth. The main part of this work is concerned with the synchronization of fully digital receivers using 1-bit quantization and oversampling. As a first step, we derive performance bounds for phase, timing, and frequency estimation in order to gain a deeper insight into the impact of 1-bit quantization and oversampling. We identify uniform phase and sample dithering as crucial to combat the non-linear behavior introduced by 1-bit quantization. This dithering can be implemented by sampling at an irrational intermediate frequency and with an oversampling factor with respect to the symbol rate that is irrational, respectively. Since oversampling results in noise correlation, a closed form expression of the likelihood function is not available. To enable an analytical treatment we thus study a system model with white noise by adapting the receive filter bandwidth to the sampling rate. Considering the aforementioned dithering, we obtain very tight closed form lower bounds on the Cramér-Rao lower bound (CRLB) in the large sample regime. We show that with uniform phase and sample dithering, all large sample properties of the CRLB of the unquantized receiver are preserved under 1-bit quantization, except for a signal-to-noise ratio (SNR) dependent performance loss that can be decreased by oversampling. For the more realistic colored noise case, we discuss a numerically computable upper bound of the CRLB and show that the properties of the CRLB for white noise still hold for colored noise except that the performance loss due to 1-bit quantization is reduced. Assuming a neglectable frequency offset, we use the least squares objective function to derive a typical digital matched filter receiver with a data-and timing-aided phase estimator and a timing estimator that is based on square time recovery. We show that both estimators are consistent under very general assumptions, e.g., arbitrary colored noise and stationary ergodic transmit symbols. Performance evaluations are done via simulations and are compared against the numerically computable upper bound of the CRLB. For low SNR the estimators perform well but for high SNR they converge to an error floor. The performance loss of the phase estimator due to decision-directed operation or estimated timing information is marginal. In summary, we have derived practical solutions for the design of fully digital receivers using 1-bit quantization and oversampling and presented a mathematical analysis of the proposed receiver structure. This is an important step towards enabling energy efficient future wireless communication systems with data rates of 100 Gbit/s and beyond.

This dissertation thesis deals with new progressive channel coding methods for data transmission using satellite transponder. The design of the system for SMS transmission, in which novel turbo coding methods are applied, is discussed too. An achievement of the lowest output power and the smallest user aperture is the principal aim of the new method applications. Design of system that would be able to the error free SMS transmission by very low signal to noise ratio is analyzed in this dissertation thesis. The work is focused on energy budget, modification and implementation of new turbo code types and using unique properties, development of new bit error rate estimation methods and methods for determination of final SMS form. The main contribution is the new type of turbo code development that have optimal properties for this usage, development of new bit error rate estimation method and development of method that is able to determine final form of SMS on the basis SMS frame structure and turbo decoding theory when the bit error rate is not zero.

[pt] Sistemas de múltiplas antenas de larga escala são técnicas fundamentais para sistemas de comunicação sem fio do futuro, que deverão servir dezenas de usuários por estação rádio-base. Neste contexto, um problema chave é o aumento do consumo de energia à medida que o número de antenas cresce. Recentemente, CADs de baixa resolução têm atraído grande interesse de pesquisa. Em particular, CADs de 1 bit são adequados para sistemas de larga escala devido ao seu baixo custo e consumo de energia. Nesta tese, CADs de 1 bit são usados em três diferentes abordagens de projeto, que operam a taxa de Nyquist e a taxas superiores a taxa de Nyquist com estratégias de amostragem uniforme e dinâmica. Nos sistemas operando a taxa de Nyquist, algoritmos de estimação de canal que exploram o conhecimento da baixa resolução e um novo esquema de detecção e decodificação iterativas são propostos, em que códigos low-density paritycheck de bloco curto são considerados para evitar alta latência. Nos sistemas operando a taxas superiores a taxa de Nyquist com sobreamostragem uniforme, algoritmos eficientes de estimação de canal e de detecção com janela deslizante com exploração da baixa resolução são propostos. Além disso, são deduzidas expressões analíticas associadas aos limitantes de Cramér-Rao para os sistemas com sobreamostragem. Resultados numéricos ilustram o desempenho dos algoritmos de estimação de canal propostos e existentes e os limitantes teóricos deduzidos. Nos sistemas operando com sobreamostragem dinâmica, duas abordagens de projeto são desenvolvidas: uma técnica baseada na maximização da soma das taxas e uma técnica baseada na minimização do erro médio quadrático. Em seguida, três algoritmos de redução de dimensão são apresentados e investigados. Resultados de simulações mostram que os sistemas com sobreamostragem dinâmica têm melhor desempenho do que os sistemas com sobreamostragem uniforme em termos de soma das taxas alcançáveis e de taxa de erro de símbolos, enquanto o custo computacional das técnicas examinadas é comparável. / [en] Large-scale multiple-antenna systems are a key technique for future wireless communications, which will serve tens of users per base station (BS). In this scenario, one problem faced is the large energy consumption as the number of receive antennas scales up. Recently, low-resolution analogto-digital converters (ADCs) have attracted much attention. Specifically, 1-bit ADCs in the front-end are suitable for such systems due to their low cost and low energy consumption. In this thesis, 1-bit ADCs are applied in three different system designs, which operate at the Nyquist rate and faster than Nyquist rates along with uniform and dynamic strategies. In the Nyquist-sampling system, low-resolution-aware channel estimation algorithms and a novel iterative detection and decoding scheme are proposed, where short block length low-density parity-check codes are considered for avoiding high latency. In the faster than Nyquist rates with uniform oversampling system, lowresolution-aware channel estimation and sliding window based detection algorithms are proposed due to their low computational cost and high detection accuracy. Particularly, analytical expressions associated with the Bayesian Cramér-Rao bounds for the oversampled systems are presented. Numerical results are provided to illustrate the performance of the proposed channel estimation algorithms and the derived theoretical bounds. In the dynamic-oversampling system, two different system designs are devised, namely, sum rate and mean square error based. Three different dimension reduction algorithms are presented and thoroughly investigated. Simulation results show that the systems with the proposed dynamic oversampling outperform the uniformly oversampled system in terms of the computational cost, achievable sum rate and symbol error rate performance.

No description available.

No description available.

[pt] Eficiência energética e espectral são características importantes para comunicações militares e internet das coisas (IoT). Nesta tese, métodos e sistemas de quantização de 1-bit com modulação de fase contínua (CPM) são estudados e propostos para resolver as necessidades de sistemas de comunicações modernos com baixo consumo energético. Nesse contexto, o método de superamostragem em relação a duração de um símbolo é promissor, pois a informação está contida ao longo da transição de fase de sinais CPM, que não são estritamente limitados em banda. Consequentemente, a perda de taxa alcançável causada pela quantização de 1-bit pode ser reduzida consideravelmente, até mesmo para esquemas com maior ordem de modulação. Este estudo investiga diferentes abordagens para melhorar o desempenho do modelo de sistema proposto. Um esquema de codificação de canal é projetado com mapeamento de bits adaptado ao problema de quantização grosseira, fazendo uso de um soft-in soft-out (SISO) turbo receiver. Formas de onda CPM com duração de símbolo significamente menor que o inverso da banda do sinal são propostas, nomeadas de faster-than-Nyquist CPM. Um fator maior de superamostragem é aplicado com uma estratégia de seleção de amostras em um modelo de amostragem adaptativa. Finalmente, resultados numéricos confirmam melhor desempenho em taxa de erro de bit, eficiência espectral e taxa alcançável para os métodos propostos, em comparação às técnicas recentemente utilizadas. / [en] Energy and spectral efficiency are appealing features for military communications and internet of things (IoT). On this thesis, systems and schemes with 1-bit quantization and continuous phase modulation (CPM) are studied and proposed to address the needs for modern and power efficient communications. In this context, oversampling with respect to the symbol duration is promising because the information is conveyed in the phase transitions of the CPM signals, which are not strictly bandlimited. With this, the loss in achievable rate caused by the coarse quantization can be greatly reduced, even for higher order modulation schemes. This study investigates different approaches to enhancing the performance of the proposed system model. A channel coding scheme is designed with a tailored bit mapping, by means of employing a soft-in soft-out (SISO) turbo receiver. CPM waveforms with symbol durations significantly shorter than the inverse of the signal bandwidth are proposed, termed faster-than-Nyquist CPM. Higher oversampling is applied with a sample selection strategy for a nonuniform adaptive oversampling model. Finally, numerical results confirm better performance on bit error rate, spectral efficiency and achievable rate for the proposed methods in comparison with state of the art techniques.

International Telemetering Conference Proceedings / October 20-23, 2003 / Riviera Hotel and Convention Center, Las Vegas, Nevada / Unmanned Telemetry Ground System (UTGS) was implemented in Defense System Test Center (DSTC), Agency for Defense Development (ADD). The components of UTGS are Antenna, NPS (Network Power Switch), RCB (Receiver/Combiner/Bit synchronizer) and microwave link. We have installed RCB which is composed of receiver, combiner and bit synchronizer. RCB can be controlled and monitored by RS232 serial communication and microwave network. NPS controls its power supplies. UTGS sends PCM stream to local site using E1-class HDSL and microwave link. This system is possible the signal acquisition and reduction of man power at remote site. The usability and performance of UTGS was proved in flight tests. This paper describes the hardware, software design and an implementation of UTGS.