In digital communication systems symbol timing recovery is of fundamental importance. The accuracy in estimation of symbol timing has a direct effect on received data error rates. The primary objective of this thesis is to implement a practical Digital Phase Locked Loop capable of accurate synchronisation of symbols suffering channel corruption typical of modern mobile communications. This thesis describes an all-software implementation of a Digital Phase Locked in a real-time system. A timing error detection (TED) algorithms optimally implemented into a Digital Signal Processor. A real-time transmitter and receiver system is implemented in order to measure performance when the received signal is corrupted by both Additive White Gaussian Noise and Flat Fading. The Timing Error Detection algorithm implemented is a discrete time maximum likelihood one known as FFML1, developed at Canterbury University. FFML1 along with other components of the Digital Phase Locked loop are implemented entirely in software, using Motorola 56321 assembly language.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / This work presents a new structure for an all-digital BPSK demodulator developed for space communications that performs simultaneously the sampling and down-conversion of the the intermediate frequency signal to the baseband signal. The most important aspect of this work is the design of a new interpolator to retrieve lost samples during the down conversion process, and also to simplify the demodulator implementation. This interpolator correlates the samples of the output signal in such way that it was necessary to design a optimum filter appropriate to process the samples corrupted by gaussian and colored noise. The effects of the new interpolation at the noise are analyzed as well as the way it affects the whole demodulator performance. After performing the optimum filtering, the phase and symbol offsets are estimated and corrected. For the phase, for example, it was used a DPLL (Digital Phase Locked Loop), a digital variation of the PLL, a well known structure and largely utilized in analogical electronics. The DPLL is a closed-loop structure that estimates and corrects the values for the angular which corresponds to the phase deviation caused by the offset between the transmitter and receiver oscilators. For the timing parameter estimation, it was used the Oerder&Meyer estimator that is the digital equivalent to the well known square timing recovery structure. After that, the correction is performed by an interpolation operation over the samples of the received signal, where a filter, named Farrow filter, is applied to these samples, calculating the new samples of that signal at the corrected time instants. This system is mathematically described, all the signals expressions of every stage of the demodulator are analyzed, including the noise statistics. Some computational simulation results are shown and the performance degradation is discussed. / Este trabalho apresenta um modelo de demodulador que realiza simultaneamente a conversÃo analÃgico-digital e a conversÃo em frequÃncia por amostragem em banda passante de um sinal com modulaÃÃo BPSK (Binary Phase Shift Keying) para aplicaÃÃo em enlaces espaciais. O aspecto mais importante do trabalho foi o desenvolvimento de uma nova operaÃÃo de interpolaÃÃo para recuperaÃÃo das amostras perdidas na conversÃo de frequÃncia e que simplifica a implementaÃÃo do demodulador. O interpolador correlaciona as amostras do sinal de forma que torna-se necessÃrio o projeto de um filtro Ãtimo apropriado para processar as amostras corrompidas e mitigar os efeitos do ruÃdo gaussiano e colorido. Os efeitos deste novo interpolador no ruÃdo sÃo analisados, assim como a forma em que ele afeta a performance do sistema. ApÃs a filtragem Ãtima, segue a correÃÃo dos erros de sincronismo de atraso de simbolo e de fase. Para a recuperaÃÃo do sincronismo de fase foi utilizado um DPLL (Digital Phase Locked Loop), uma variante digital de uma estrutura bastante conhecida e utilizada em eletrÃnica analÃgica. O DPLL à uma estrutura em malha fechada que estima e corrige os valores do desvio angular das amostras, o que corresponde ao devio provocado pela diferenÃa de fase entre os osciladores do transmissor e do receptor. Para a recuperaÃÃo do atraso de sÃmbolo foi utilizada, para estimaÃÃo do tempo de atraso, o estimador de Oerder&Meyer que à o equivalente digital da conhecida recuperaÃÃo de temporizaÃÃo em tempo contÃnuo com a lei quadrÃtica. ApÃs a estimaÃÃo ser realizada, à feita a correÃÃo deste atraso nas amostras do sinal recebido atravÃs de uma operaÃÃo de interpolaÃÃo, onde novos valores do sinal sÃo calculados para os instantes de tempo corrigidos. Essa operaÃÃo à realizada por um filtro interpolador, uma estrutura especial conhecida como estrutura de Farrow. O sistema proposto foi descrito matematicamente, sendo analisadas as expressÃes dos sinais nos diferentes estÃgios do conversor, bem como as estatÃsticas dos sinais de ruÃdo. Apresentam-se os resultados da simulaÃÃo computacional nos quais se avalia a perda no desempenho do demodulador, analisando suas causas.

O Objetivo deste trabalho foi implementar um resolvedor distribuído para o problema de satisfabilidade em lógica proposicional (SAT) que pudesse ser executado em uma grade de computadores. Foi analisada a influência que o número de máquinas utilizadas pela grade para resolver diversas instâncias do SAT exerce sobre o desempenho do resolvedor implementado / O Objetivo deste trabalho foi implementar um resolvedor distribuído para o problema de satisfabilidade em lógica proposicional (SAT) que pudesse ser executado em uma grade de computadores. Foi analisada a influência que o número de máquinas utilizadas pela grade para resolver diversas instâncias do SAT exerce sobre o desempenho do resolvedor implementado

Quantified Boolean formulas (QBFs) play an important role in theoretical computer science. QBF extends propositional logic in such a way that many advanced forms of reasoning can be easily formulated and evaluated. In this dissertation we present our ZQSAT, which is an algorithm for evaluating quantified Boolean formulas. ZQSAT is based on ZBDD: Zero-Suppressed Binary Decision Diagram / which is a variant of BDD, and an adopted version of the DPLL algorithm. It has been implemented in C using the CUDD: Colorado University Decision Diagram package. <br><br> The capability of ZBDDs in storing sets of subsets efficiently enabled us to store the clauses of a QBF very compactly and let us to embed the notion of memoization to the DPLL algorithm. These points led us to implement the search algorithm in such a way that we could store and reuse the results of all previously solved subformulas with a little overheads. ZQSAT can solve some sets of standard QBF benchmark problems (known to be hard for DPLL based algorithms) faster than the best existing solvers. In addition to prenex-CNF, ZQSAT accepts prenex-NNF formulas. We show and prove how this capability can be exponentially beneficial. <br><br> / In der Dissertation stellen wir einen neuen Algorithmus vor, welcher Formeln der quantifizierten Aussagenlogik (engl. Quantified Boolean formula, kurz QBF) löst. QBFs sind eine Erweiterung der klassischen Aussagenlogik um die Quantifizierung über aussagenlogische Variablen. Die quantifizierte Aussagenlogik ist dabei eine konservative Erweiterung der Aussagenlogik, d.h. es können nicht mehr Theoreme nachgewiesen werden als in der gewöhnlichen Aussagenlogik. Der Vorteil der Verwendung von QBFs ergibt sich durch die Möglichkeit, Sachverhalte kompakter zu repräsentieren. <br><br> SAT (die Frage nach der Erfüllbarkeit einer Formel der Aussagenlogik) und QSAT (die Frage nach der Erfüllbarkeit einer QBF) sind zentrale Probleme in der Informatik mit einer Fülle von Anwendungen, wie zum Beispiel in der Graphentheorie, bei Planungsproblemen, nichtmonotonen Logiken oder bei der Verifikation. Insbesondere die Verifikation von Hard- und Software ist ein sehr aktuelles und wichtiges Forschungsgebiet in der Informatik. <br><br> Unser Algorithmus zur Lösung von QBFs basiert auf sogenannten ZBDDs (engl. Zero-suppressed Binary decision Diagrams), welche eine Variante der BDDs (engl. Binary decision Diagrams) sind. BDDs sind eine kompakte Repräsentation von Formeln der Aussagenlogik. Der Algorithmus kombiniert nun bekannte Techniken zum Lösen von QBFs mit der ZBDD-Darstellung unter Verwendung geeigneter Heuristiken und Memoization. Memoization ermöglicht dabei das einfache Wiederverwenden bereits gelöster Teilprobleme. <br><br> Der Algorithmus wurde unter Verwendung des CUDD-Paketes (Colorado University Decision Diagram) implementiert und unter dem Namen ZQSAT veröffentlicht. In Tests konnten wir nachweisen, dass ZQSAT konkurrenzfähig zu existierenden QBF-Beweisern ist, in einigen Fällen sogar bessere Resultate liefern kann.

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

Le raisonnement assisté par ordinateur joue un rôle crucial en informatique et en logique mathématique, de la programmation logique à la déduction automatique, en passant par les assistants à la démonstration. Le but de cette thèse est la conception d'un cadre général où différentes techniques de raisonnement assisté par ordinateur peuvent être implémentées, pour que ces dernières puissent collaborer, être généralisées, et être implémentées de manière plus sûre. Le cadre que je propose est un calcul des séquents appelé LKp(T), qui généralise un système de la littérature à la présence d'une théorie pour laquelle nous avons une procédure de décision, comme l'arithmétique linéaire. Cette thèse développe la méta-théorie de LKp(T), avec par exemple la propriété de complétude logique. Nous montrons ensuite comment le système spécifie une procédure de recherche de preuve qui émule une technique connue du domaine de la Satisfiabilité-modulo-théories appelée DPLL(T). Enfin, les tableaux de clauses et les tableaux de connexions sont d'autres techniques populaires en déduction automatique, d'une nature relativement différente de DPLL. Cette thèse décrit donc également comment ces techniques de tableaux peuvent être décrites en termes de recherche de preuve dans LKp(T). La simulation est donnée à la fois pour la logique propositionnelle et la logique du premier ordre, ce qui ouvre de nouvelles perspectives de généralisation et de collaboration entre les techniques de tableaux et DPLL, même en présence d'une théorie.

First, a frequency synthesizer for IEEE 802.15.4 / ZigBee transceiver applications that employs dynamic True Single Phase Clocking (TSPC) circuits in its frequency dividers is presented and through the analysis and measurement results of this synthesizer, the need for low power circuit techniques in frequency dividers is discussed. Next, Differential Cascode Voltage-Switch-Logic (DCVSL) based delay cells are explored for implementing radio-frequency (RF) frequency dividers of low power frequency synthesizers. DCVSL ip- ops offer small input and clock capacitance which makes the power consumption of these circuits and their driving stages, very low. We perform a delay analysis of DCVSL circuits and propose a closed-form delay model that predicts the speed of DCVSL circuits with 8 percent worst case accuracy. The proposed delay model also demonstrates that DCVSL circuits suffer from a large low-to-high propagation delay ( PLH) which limits their speed and results in asymmetrical output waveforms. Our proposed enhanced DCVSL, which we call DCVSL-R, solves this delay bottleneck, reducing PLH and achieving faster operation. We implement two ring-oscillator-based voltage controlled oscillators (VCOs) in 0.13 mu m technology with DCVSL and DCVSL-R delay cells. In measurements, for the same oscillation frequency (2.4GHz) and same phase noise (-113dBc/Hz at 10MHz), DCVSL-R VCO consumes 30 percent less power than the DCVSL VCO. We also use the proposed DCVSL-R circuit to implement the 2.4GHz dual-modulus prescaler of a low power frequency synthesizer in 0.18 mu m technology. In measurements, the synthesizer exhibits -135dBc/Hz phase noise at 10MHz offset and 58 mu m settling time with 8.3mW power consumption, only 1.07mWof which is consumed by the dual modulus prescaler and the buffer that drives it. When compared to other dual modulus prescalers with similar division ratios and operating frequencies in literature, DCVSL-R dual modulus prescaler demonstrates the lowest power consumption. An all digital phase locked loop (ADPLL) that operates for a wide range of frequencies to serve as a multi-protocol compatible PLL for microprocessor and serial link applications, is presented. The proposed ADPLL is truly digital and is implemented in a standard complementary metal-oxide-semiconductor (CMOS) technology without any analog/RF or non-scalable components. It addresses the challenges that come along with continuous wide range of operation such as stability and phase frequency detection for a large frequency error range. A proposed multi-bit bidirectional smart shifter serves as the digitally controlled oscillator (DCO) control and tunes the DCO frequency by turning on/off inverter units in a large row/column matrix that constitute the ring oscillator. The smart shifter block is completely digital, consisting of standard cell logic gates, and is capable of tracking the row/column unit availability of the DCO and shifting multiple bits per single update cycle. This enables fast frequency acquisition times without necessitating dual loop fi lter or gear shifting mechanisms. The proposed ADPLL loop architecture does not employ costly, cumbersome DACs or binary to thermometer converters and minimizes loop filter and DCO control complexity. The wide range ADPLL is implemented in 90nm digital CMOS technology and has a 9-bit TDC, the output of which is processed by a 10-bit digital loop filter and a 5-bit smart shifter. In measurements, the synthesizer achieves 2.5GHz-7.3GHz operation while consuming 10mW/GHz power, with an active area of 0.23 mm2.