The present thesis analyses the proposal of CubeHash with spe- cial emphasis on the following papers: "Inside the Hypercube" [1], "Sym- metric States and Their Improved Structure" [7] and "Linearisation Frame- work for Collision Attacks" [6]. The CubeHash algorithm is presented in a concise manner together with a proof that the CubeHash round function R : ({0, 1}32 )32 → ({0, 1}32 )32 is a permutation. The results of [1] and [7] con- cerning the CubeHash symmetric states are reviewed, corrected and substan- tiated by proofs. More precisely, working with a definition of D-symmetric state, based on [7], the thesis proves both that for V = Z4 2 and its linear subspace D, there are 22 |V | |D| D-symmetric states and an internal state x is D-symmetric if and only if the state R(x) is D-symmetric. In response to [1], the thesis presents a step-by-step computation of a lower bound for the num- ber of distinct symmetric states, explains why the improved preimage attack does not work as stated and gives a mathematical background for a search for fixed points in R. The thesis further points out that the linearisation method from [6] fails to consider the equation (A ⊕ α) + β = (A + β) ⊕ α (∗), present during the CubeHash iteration phase. Necessary and sufficient conditions for A being a solution to (∗) are...

Neste trabalho inicialmente estudamos o rank da co-homologia do espaço dos pontos fixos de uma \'Z IND.p\' - ação semilivre sobre espaços X~p \' S POT. n\' x \'S POT.n\' e X~p \'S POT.n\' x \'S POT.n\' x \'S POT.n\' , com n>0. Em seguida, estudamos uma extensão para ações de p-grupos sobre espaços X~p \'S POT.n\' X \'S POT.m\', com 0< n \'< OU =\' m. Como parte do material utilizado demos uma descrição do diferencial d1 de uma seqüência espectral que converge para co-homologia equivariante de Tate, bem como uma versão da Fórmula de Künneth para a co-homologia equivariante de Tate. Na parte final, motivado pelo problemas de descrição de espaços de órbita de ações de grupos infinito, calculamos as co-homologias dos grupos virtualmente cíclicos (\'Z IND.a\' X| \' Z IND. b\' )X| Z e [\'Z POT.a\' X|(\'Z IND.b\' X \'Q IND. 2 POT.i\') ]X| Z / In this work is studied the rank of the fixed point set of a semifree action on spaces X~p \'S POT.n\' X \'S POT.n\' and X~p \'S POT.n\' X \'S POT.n\' X \'S POT.n\' , with n>0. We also consider the extension of the result for actions of p-groups on spaces X~p \'SPOT.n\' X \' S POT.m\' , with 0<n \'< OR =\' m. As result of the techniques used, we give a description of the differential d1 of a spectral sequence that converges to Tate equivariant cohomology, as well a version of the Künneth Formule to Tate equivariant cohomology. At the end, motivated by the space form problem for infinite groups we compute the cohomology of the virtually cyclic groups (\'Z IND. a\' X| \'Z IND. b\' )X| Z and [\'Z IND.a\' X|(\'Z IND. b\' X \'Q IND2 POT. i\' )] X| Z

Nas últimas três décadas os phase locked loops (PLLs) totalmente digitais têm recebido muita atenção devido, principalmente, às vantagens que eles oferecem em comparação aos PLLs analógicos. Essas vantagens incluem melhor desempenho, maior velocidade e confiabilidade, tamanho reduzido e menor custo. Os PLLs também são amplamente utilizados em sistemas de comunicações e em outras aplicações digitais. A presente dissertação é uma contribuição no campo dos PLLs digitais adaptativos e otimizados para a sua implementação em hardware. É feito uma análise de suas características dinâmicas e proposta uma nova estrutura de PLL digital capaz de melhorar a resposta da malha em termos de tempo de aquisição e largura de banda. A Malha Síncrona Digital \"Tanlock\" com Estimação de Frequência e Ganho Adaptativo para Convergência Rápida, como é chamada, foi desenvolvida a partir da malha digital \"Tanlock\", utilizando-se teoremas de ponto fixo e mapas contrativos para determinar as condições de ganho que garantam convergência rápida e melhor utilização da largura de banda. Resultados das simulações são comparados com os obtidos teoricamente para avaliar o desempenho da malha proposta. / In the last three decades, fully-digital Phase-Locked-Loops (PLLs) systems have received a lot of attention due to its advantages in comparison with analog PLLs. These advantages include improved transient response, reliability and also reduced size and cost. The PLLs are widely used in communications systems and many other digital applications. This dissertation is a contribution to the field of digital adaptive PLLs optimized to hardware implementation. Here, a new PLL structure is presented; the Frequency Sensing Adaptive TDTL is an improvement to the classic Time-Delay Tanlock structure, alowing fast convergence to the synchronous states, using fixed-point theorems and contractive maps to determine the gain conditions which ensure the rapid convergence and also providing wider bandwidth. The results of simulations are compared with those obtained theoretically in order to assess the loop performance.

This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable and precise numerical results are obtained as outputs of the algorithms. However the analysis results are not reliable because of the performance analysis tools.

Dans la nature existent de nombreux exemples de systèmes dynamiques complexes: systèmes neuronaux, communautés, écosystèmes, réseaux de régulation génétiques, etc. Ces derniers, en particulier, sont de notre intérêt et sont souvent modélisés par des réseaux booléens. Un réseau booléenne peut être considérée comme un digraphe, où les sommets correspondent à des gènes ou de produits de gènes, tandis que les arcs indiquent les interactions entre eux. Une niveau d'expression des gènes est modélisé par des valeurs binaires, 0 ou 1, indiquant deux états de la transcription, soit activité, soit inactivité, respectivement, et ce niveau change dans le temps selon certains fonction locaux d'activation qui dépend des états d'un ensemble de nœuds (les gènes). L'effet conjoint des fonctions d'activation locale définit une fonction de transition globale: ainsi, le autre élément nécessaire dans la description du modèle est fonction de mise à jour, qui détermine quand chaque nœud doit être mis à jour, et donc, comme les fonctions local se combinent dans une fonction globale (en d'autres termes, il doit décrire les temps relative de les activités régulatoires). Comme un réseau booléen avec n sommets a 2 ^ n états globaux, à partir d'un état ​​de départ, et dans un nombre fini de mises à jour, le réseau atteindra un fixe point ou un cycle limite, appelée attracteurs qui sont souvent associées à des phénotypes distincts (états-cellulaire) définis par les patrons d'activité des gènes. Un réseau de régulation Booléenne (REBN) est un réseau Booléen où chaque interaction entre les éléments de la réseau correspond soit à une interaction positif ou d'une interaction négative. Ainsi, le digraphe interaction associée à une REBN est un digraphe signé où un circuit est appelé positif (négatif) si le nombre de ses arcs négative est pair (impair). Dans ce contexte, il y a diverses études sur l'importance du les circuits positif et négatifs dans le comportement dynamique de différents systèmes en Biologie. En effet le point de départ de cette thèse est basée sur un résultat en disant que le nombre maximal de points fixes d'une REBN dépend d'un ensemble de cardinalité minimale qu'intersecte tous les cycles positifs (également dénommés positive feedback vertex set) du digraphe signé associé. D'autre part, un autre aspect important de circuits est leur rôle dans la robustesse des réseaux booléens par rapport différents types de mise à jour déterministe. Dans ce contexte, un élément clé mathématique est le update digraphe qui est un digraphe étiqueté associé à la réseau dont les étiquettes sur les arcs sont définies comme suit: un arc (u,v) est dit être positif si l'état de sommet u est mis à jour en même temps ou après que celle de v, et négative sinon. Ainsi, un cycle dans le digraphe étiqueté est dite positive (négative) si tous ses arcs sont positifs (négatifs). Cela laisse en évidence que parler de "positif" et "négatif" a des significations différentes selon le contex: digraphes signé ou digraphes étiquetés. Ainsi, nous allons voir dans cette thèse, les relations entre les feedback sets et la dynamique des réseaux Booléens à travers l'étude analytique de ces deux fondamentaux objets mathématiques: le digraphe (de connexion) signé et l'update digraphe. / In the nature there exist numerous examples of complex dynamical systems: neural systems, communities, ecosystems, genetic regulatory networks, etc. These latest, in particular are of our interest and are often modeled by Boolean networks. A Boolean network can be viewed as a digraph, where the vertices correspond to genes or gene products, while the arcs denote interactions among them. A gene expression level is modeled by binary values, 0 or 1, indicating two transcriptional states, either active or inactive, respectively, and this level changes in time according to some local activation function which depends on the states of a set of nodes (genes). The joint effect of the local activation functions defines a global transition function; thus, the other element required in the description of the model is an update schedule which determines when each node has to be updated, and hence, how the local functions combine into the global one (in other words, it must describe the relative timings of the regulatory activities). Since a Boolean network with n vertices has 2^n global states, from a starting state, within a finite number of udpates, the network will reach a fixed point or a limit cycle, called attractors that are often associated to distinct phenotypes (cellular states) defined by patterns of gene activity. A regulatory Boolean network (REBN) is a Boolean network where each interaction between the elements of the network corresponds either to a positive or to a negative interaction. Thus, the interaction digraph associated to a REBN is a signed digraph where a circuit is called positive (negative) if the number of its negative arcs is even (odd). In this context, there are diverse studies about the importance of the positive and negative circuits in the dynamical behavior of different systems in Biology. Indeed the starting point of this Thesis is based on a result saying that the maximum number of fixed points of a REBN depends on a minimum cardinality vertex set whose elements intersects to all the positive cycles (also named a positive feedback vertex set) of the associated signed digraph. On the other hand, another important aspect of circuits is their role in the robustness of Boolean networks with respect to different deterministic update schedules. In this context a key mathematical element is the update digraph which is a labeled digraph associated to the network and whose labels on the arcs are defined as follows: an arc (u,v) is said to be positive if the state of vertex u is updated at the same time or after than that of v, and negative otherwise. Hence, a cycle in the labeled digraph is called positive (negative) if all its arcs are positive (negative). This leaves in evidence that talk of "positive" and "negative" has different meanings depending on the contex: signed digraphs or labeled digraphs. Thus, we will see in this thesis, relationships between feedback sets and the dynamics of Boolean networks through the analytical study of these two fundamental mathematical objects: the signed (connection) digraph and the update digraph.

<p>This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal </p><p>processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented </p><p>to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. </p><p>Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable and precise numerical results are obtained as outputs of the algorithms. However the analysis </p><p>results are not reliable because of the performance analysis tools.</p>

<p>This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable </p><p>and precise numerical results are obtained as outputs of the algorithms. However the analysis results are not reliable because of the performance analysis tools.</p>

<p>The success of the current Internet relies to a large extent on a cooperation between the users and the network. The network signals its current state to the users by marking or dropping packets. The users then strive to maximize the sending rate without causing network congestion. To achieve this, the users implement a flow-control algorithm that controls the rate at which data packets are sent into the Internet. More specifically, the <i>Transmission Control Protocol (TCP)</i> is used by the users to adjust the sending rate in response to changing network conditions. TCP uses the observation of packet loss events and estimates of the round trip time (RTT) to adjust its sending rate. </p><p>In this thesis we investigate and propose stochastic models for TCP. The models are used to estimate network performance like throughput, link utilization, and packet loss rate. The first part of the thesis introduces the TCP protocol and contains an extensive TCP modeling survey that summarizes the most important TCP modeling work. Reviewed models are categorized as renewal theory models, fixed-point methods, fluid models, processor sharing models or control theoretic models. The merits of respective category is discussed and guidelines for which framework to use for future TCP modeling is given. </p><p>The second part of the thesis contains six papers on TCP modeling. Within the renewal theory framework we propose single source TCP-Tahoe and TCP-NewReno models. We investigate the performance of these protocols in both a DropTail and a RED queuing environment. The aspects of TCP performance that are inherently depending on the actual implementation of the flow-control algorithm are singled out from what depends on the queuing environment.</p><p>Using the fixed-point framework, we propose models that estimate packet loss rate and link utilization for a network with multiple TCP-Vegas, TCP-SACK and TCP-Reno on/off sources. The TCP-Vegas model is novel and is the first model capable of estimating the network's operating point for TCP-Vegas sources sending on/off traffic. All TCP and network models in the contributed research papers are validated via simulations with the network simulator <i>ns-2</i>. </p><p>This thesis serves both as an introduction to TCP and as an extensive orientation about state of the art stochastic TCP models.</p>

The success of the current Internet relies to a large extent on a cooperation between the users and the network. The network signals its current state to the users by marking or dropping packets. The users then strive to maximize the sending rate without causing network congestion. To achieve this, the users implement a flow-control algorithm that controls the rate at which data packets are sent into the Internet. More specifically, the Transmission Control Protocol (TCP) is used by the users to adjust the sending rate in response to changing network conditions. TCP uses the observation of packet loss events and estimates of the round trip time (RTT) to adjust its sending rate. In this thesis we investigate and propose stochastic models for TCP. The models are used to estimate network performance like throughput, link utilization, and packet loss rate. The first part of the thesis introduces the TCP protocol and contains an extensive TCP modeling survey that summarizes the most important TCP modeling work. Reviewed models are categorized as renewal theory models, fixed-point methods, fluid models, processor sharing models or control theoretic models. The merits of respective category is discussed and guidelines for which framework to use for future TCP modeling is given. The second part of the thesis contains six papers on TCP modeling. Within the renewal theory framework we propose single source TCP-Tahoe and TCP-NewReno models. We investigate the performance of these protocols in both a DropTail and a RED queuing environment. The aspects of TCP performance that are inherently depending on the actual implementation of the flow-control algorithm are singled out from what depends on the queuing environment. Using the fixed-point framework, we propose models that estimate packet loss rate and link utilization for a network with multiple TCP-Vegas, TCP-SACK and TCP-Reno on/off sources. The TCP-Vegas model is novel and is the first model capable of estimating the network's operating point for TCP-Vegas sources sending on/off traffic. All TCP and network models in the contributed research papers are validated via simulations with the network simulator ns-2. This thesis serves both as an introduction to TCP and as an extensive orientation about state of the art stochastic TCP models.

Quantum computation has attracted a great deal of attention from the scientific community in recent years. By using the quantum mechanical phenomena of superposition and entanglement, a quantum computer can solve certain problems much faster than classical computers. Several quantum algorithms have been developed to demonstrate this quantum speedup. Two important examples are Shor’s algorithm for the factorization problem, and Grover’s algorithm for the search problem. Significant efforts are on to build a large scale quantum computer for implementing these quantum algorithms. This thesis deals with Grover’s search algorithm, and presents its several generalizations that perform better in specific contexts. While writing the thesis, we have assumed the familiarity of readers with the basics of quantum mechanics and computer science. For a general introduction to the subject of quantum computation, see [1]. In Chapter 1, we formally define the search problem as well as present Grover’s search algorithm [2]. This algorithm, or more generally the quantum amplitude amplification algorithm [3, 4], drives a quantum system from a prepared initial state (s) to a desired target state (t). It uses O(α-1 = | (t−|s)| -1) iterations of the operator g = IsIt on |s), where { IsIt} are selective phase inversions selective phase inversions of the corresponding states. That is a quadratic speedup over the simple scheme of O(α−2) preparations of |s) and subsequent projective measurements. Several generalizations of Grover’s algorithm exist. In Chapter 2, we study further generalizations of Grover’s algorithm. We analyse the iteration of the search operator S = DsI t on |s) where Ds is a more general transformation than Is, and I t is a selective phase rotation of |t) by angle . We find sufficient conditions for S to produce a successful quantum search algorithm. In Chapter 3, we demonstrate that our general framework encapsulates several previous generalizations of Grover’s algorithm. For example, the phase-matching condition for the search operator requires the angles and and to be almost equal for a successful quantum search. In Kato’s algorithm, the search operator is where Ks consists of only single-qubit gates, which are easier to implement physically than multi-qubit gates. The spatial search algorithms consider the search operator where is a spatially local operator and provides implementation advantages over Is. The analysis of Chapter 2 provides a simpler understanding of all these special cases. In Chapter 4, we present schemes to improve our general quantum search algorithm, by controlling the operators through an ancilla qubit. For the case of two dimensional spatial search problem, these schemes yield an algorithm with time complexity . Earlier algorithms solved this problem in time steps, and it was an open question to design a faster algorithm. The schemes can also be used to find, for a given unitary operator, an eigenstate corresponding to a specified eigenvalue. In Chapter 5, we extend the analysis of Chapter 2 to general adiabatic quantum search. It starts with the ground state |s) of an initial Hamiltonian Hs and evolves adiabatically to the target state |t) that is the ground state of the final Hamiltonian The evolution uses a time dependent Hamiltonian HT that varies linearly with time . We show that the minimum excitation gap of HT is proportional to α. Also, the ground state of HT changes significantly only within a very narrow interval of width around the transition point, where the excitation gap has its minimum. This feature can be used to reach the target state (t) using adiabatic evolution for time In Chapter 6, we present a robust quantum search algorithm that iterates the operator on |s) to successfully reach |t), whereas Grover’s algorithm fails if as per the phase-matching condition. The robust algorithm also works when is generalized to multiple target states. Moreover, the algorithm provides a new search Hamiltonian that is robust against certain systematic perturbations. In Chapter 7, we look beyond the widely studied scenario of iterative quantum search algorithms, and present a recursive quantum search algorithm that succeeds with transformations {Vs,Vt} sufficiently close to {Is,It.} Grover’s algorithm generally fails if while the recursive algorithm is nearly optimal as long as , improving the error tolerance of the transformations. The algorithms of Chapters 6-7 have applications in quantum error-correction, when systematic errors affect the transformations The algorithms are robust as long as the errors are small, reproducible and reversible. This type of errors arise often from imperfections in apparatus setup, and so the algorithms increase the flexibility in physical implementation of quantum search. In Chapter 8, we present a fixed-point quantum search algorithm. Its state evolution monotonically converges towards |t), unlike Grover’s algorithm where the evolution passes through |t) under iterations of the operator . In q steps, our algorithm monotonically reduces the failure probability, i.e. the probability of not getting |t), from . That is asymptotically optimal for monotonic convergence. Though the fixed-point algorithm is of not much use for , it is useful when and each oracle query is highly expensive. In Chapter 9, we conclude the thesis and present an overall outlook.