Rozprawy doktorskie na temat „Combinatorial circuits”

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1995.
Includes bibliographical references (p. 61-62).
by William John Rinderknecht.
M.S.

This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.

This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.
Thesis (Masters)
Master of Philosophy (MPhil)
School of Engineering
Science, Environment, Engineering and Technology
Full Text

The complex changes that take place in the mature Xenopus oocyte and early embryo are orchestrated in the absence of transcription. Until zygotic transcription starts, after the mid-blastula transition, cells rely on tight spatiotemporal translational regulation. Some maternal mRNAs accumulate during oocyte growth and are stored, translationally silent. Upon stimuli, stored, silenced mRNAs become cytoplasmically polyadenylated and, subsequently, engage in translation. The timing and extent of translational activation are dictated by a complex code of 3’UTR motifs recognized by RNA-binding proteins. In meiotic maturation, at least three sequential polyadenylation waves occur. First, in response to progesterone, a single Aurora kinase A phosphorylation triggers CPEB1-directed cytoplasmic polyadenylation of mRNAs that are required for Cdk1 activation and meiotic progression. Second, activated Cdk1 targets CPEB1 for degradation, triggering a second polyadenylation surge that is necessary for the MI-MII transition. Last, CPEB4, synthesized from the first wave and activated by Cdk1 and ERK2 upon meiotic progression, drives a third wave during the second meiotic division that is required for the metaphase-II arrest. Unlike the well-studied roles of CPEB1 and CPEB4, the roles of the remaining family members, CPEB2 and CPEB3, remain uncharacterized. In this thesis we have performed a systematic investigation of the CPEB-family of RBPs in meiotic maturation in order to elucidate their combinatorial contribution to gene expression regulation. We have determined that CPEB1 and the CPEB2-4 subfamily differ in their expression dynamics, concentration and regulation. Like CPEB4, CPEB2 and CPEB3 are regulated by N-terminal hyperphosphorylation that causes dissolution of the CPEB-condensates. Furthermore, we have found that all CPEBs co-localize and are proximal to mRNA repression and storage proteins, probably reflecting their inclusion within large repressive mRNPs in the oocyte. We have also found that all CPEBs bind a highly overlapping subset of mRNAs, although CPEB1 and CPEB2-4 could differentially regulate a small subset of targets. All in all, we have contributed to the understanding of how the multiple CPEBs co-exist and how their activities are coordinated in the cell to dictate complex expression patterns.
La maduración meiótica y la embriogénesis temprana de Xenopus se dan en ausencia de transcripción. Hasta la transición materno-cigótica – después de la 12ª división embrionaria - la transcripción no se re-inicia y todos los cambios en expresión génica ocurren por mecanismos post- transcripcionales, entre los cuales destaca la poliadenilación citoplasmática. Durante su crecimiento, el oocito produce grandes cantidades de mRNA que mantiene silenciados, con una cola de poly(A) corta. En la maduración y embriogénesis, ciertos mRNAs son poliadenilados y traducidos. Cuando y cuanto cada mRNA es movilizado depende de la combinación de señales presentes en su 3’UTR y de las proteínas de unión al RNA que las reconocen. En la maduración meiótica se dan, al menos, tres olas secuenciales de poliadenilación. La primera es iniciada en respuesta a progesterona. Concretamente, la fosforilación por Aurora quinasa A causa la remodelación del complejo de represión de CPEB1 a complejo de activación, permitiendo la expresión de genes necesarios para la progresión meiótica, como Cdk1. Seguidamente, Cdk1 participa en la degradación de CPEB1 generando una segunda ola que es necesaria para la interkinesis. Por último, CPEB4, producida en la primera ola de poliadenilación y activada por fosforilación por Cdk1 abandera una tercera ola que posibilita la expresión de proteínas que mantienen el arresto en metafase-II. A diferencia de sus homólogos CPEB1 y CPEB4, los papeles de CPEB2 y CPEB3 en maduración meiótica siguen sin caracterizar. Por ello y para entender como esta familia de proteínas de unión al RNA se coordina para dictar la expresión génica hemos realizado una investigación sistemática y comparativa de las CPEBs en maduración meiótica.

Made available in DSpace on 2014-06-11T19:22:35Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-05-25Bitstream added on 2014-06-13T20:49:18Z : No. of bitstreams: 1 goulartsobrinho_ef_me_ilha.pdf: 944900 bytes, checksum: 47dc5d964428b7cb8bd18e1e00e1d994 (MD5)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Neste trabalho descreve-se uma metodologia para síntese e otimização de circuitos digitais, usando a teoria de algoritmos evolutivos e como plataforma os dispositivos reconfiguráveis, denominada Hardware Evolutivo do inglês- Evolvable Hardware - EHW. O EHW, tornou-se viável com o desenvolvimento em grande escala dos dispositivos reconfiguráveis, Programmable Logic Devices (PLD s), cuja arquitetura e função podem ser determinadas por programação. Cada circuito pode ser representado como um indivíduo em um processo evolucionário, evoluindo-o através de operações genéticas para um resultado desejado. Como algoritmo evolutivo, aplicou-se o Algoritmo Genético (AG), uma das técnicas da computação evolutiva que utiliza os conceitos da genética e seleção natural. O processo de síntese aplicado neste trabalho, inicia por uma descrição do comportamento do circuito, através de uma tabela verdade para circuitos combinacionais e a tabela de estados para os circuitos seqüenciais. A técnica aplicada busca o arranjo correto e minimizado do circuito que desempenhe uma função proposta. Com base nesta metodologia, são implementados alguns exemplos em duas diferentes representações (mapas de fusíveis e matriz de portas lógicas).
In this work was described a methodology for optimization and synthesis of digital circuits, which consist of evolving circuits through evolvable algorithms using as platforms reconfigurable devices, denominated Evolvable Hardware (EHW). It was became viable with the large scale development of reconfigurable devices, whose architecture and function can be determined by programming. Each circuit can be represented as an individual within an evolutionary process, evolving through genetic operations to desire results. Genetic Algorithm (GA) was applied as evolutionary algorithm where this technique evolvable computation as concepts of genetics and natural selection. The synthesis process applied in this work starts from a description from the circuits behavior. Trust table for combinatorial circuits and state transition table for sequential circuits were used for synthesis process. This technic applied search the correct arrange and minimized circuit which response the propose function. Based on this methodology, some examples are implemented in two different representations (fuse maps and logic gate matrices).

Cette thèse s'intéresse à la résolution du problème classique de décodage d'un mélange linéaire entaché d'un bruit additif gaussien. A partir d'une observation bruitée: y = Hx+b, d'un vecteur d'entiers x mélangé linéairement par une matrice H connue, b étant un vecteur de bruit, on cherche le vecteur x minimisant la distance Euclidienne entre y et le vecteur Hx. Ce problème est réputé NP-complet. Il intervient dans un grand nombre de systèmes de télécommunications (MIMO, MC-CDMA, etc. ). Nous proposons dans cette thèse un algorithme de résolution quasi optimal de ce problème et bien adapté à une implémentation matérielle. Notre démarche s'appuie sur l'utilisation des méthodes classiques de recherche opérationnelle : trouver des points initiaux répartis sur l'espace des solutions possibles et potentiellement proches de la solution optimale (diversification) et effectuer une recherche locale au voisinage des ces points (intensification). Dans ce travail, la diversification est basée sur une approche géométrique utilisant les axes dominants de concentration du bruit. Les performances en terme de taux d'erreur par bit de la méthode proposée sont proches de l'optimum tout en gardant une complexité constante et un degré de parallélisme important. Nous avons étendu cette méthode à la constellation MAQ-16 d'une part, et à la génération d'une décision souple d'autre part. Nous avons étudié l'algorithme proposé du point de vue implémentation matérielle. L'algorithme proposé présente d'une part une nouvelle alternative pour le décodage quasi optimal du mélange bruité et d'autre part un important degré de parallélisme permettant une implémentation efficace
The demand for mobile communication systems with high data rates and improved link quality for a variety of applications has dramatically increased in recent years. New concepts and methods are necessary in order to cover this huge demand, which counteract or take advantage of the impairments of the mobile communication channel and optimally exploit the limited resources such as bandwidth and power. The problem of finding the least-squares solution to a system of linear equations where the unknown vector is comprised of integers, but the matrix coefficients and given vector are comprised of real numbers, arise in many applications: communications, cryptography, MC-CDMA, MIMO, to name a few. The Maximum Likelihood (ML) decoding is equivalent to finding the closest lattice point in an n-dimensional real space. In general, this problem is known to be non deterministic NP hard. In this thesis, a polynomial-time approximation method called Geometrical Intersection and Selection Detector (GISD) is applied to the MLD problem. Moreover, the proposed approach is based on two complementary "real time" operational research methods: intensification and diversification. Our approach has three important characteristics that make it very attractive for for VLSI implementation. First, It will be shown that the performance of GISD receiver is superior as compared to other sub-optimal detection methods and it provides a good approximation to the optimal detector. Second, the inherent parallel structure of the proposed method leads to a very suitable hardware implementation. Finaly, The GISD allows a near optimal performance with constant polynomial-time, O(n3), computational complexity (unlike the sphere decoding that has exponential-time complexity for low SNR). The proposed Detector can be efficiently employed in most wireless communications systems: MIMO, MC-CDMA, MIMO-CDMA etc. .

Orientador: Suely Cunha Amaro Mantovani
Banca: José Raimundo de Oliveira
Banca: Nobuo Oki
Resumo: Neste trabalho descreve-se uma metodologia para síntese e otimização de circuitos digitais, usando a teoria de algoritmos evolutivos e como plataforma os dispositivos reconfiguráveis, denominada Hardware Evolutivo do inglês- Evolvable Hardware - EHW. O EHW, tornou-se viável com o desenvolvimento em grande escala dos dispositivos reconfiguráveis, Programmable Logic Devices (PLD’s), cuja arquitetura e função podem ser determinadas por programação. Cada circuito pode ser representado como um indivíduo em um processo evolucionário, evoluindo-o através de operações genéticas para um resultado desejado. Como algoritmo evolutivo, aplicou-se o Algoritmo Genético (AG), uma das técnicas da computação evolutiva que utiliza os conceitos da genética e seleção natural. O processo de síntese aplicado neste trabalho, inicia por uma descrição do comportamento do circuito, através de uma tabela verdade para circuitos combinacionais e a tabela de estados para os circuitos seqüenciais. A técnica aplicada busca o arranjo correto e minimizado do circuito que desempenhe uma função proposta. Com base nesta metodologia, são implementados alguns exemplos em duas diferentes representações (mapas de fusíveis e matriz de portas lógicas).
Abstract: In this work was described a methodology for optimization and synthesis of digital circuits, which consist of evolving circuits through evolvable algorithms using as platforms reconfigurable devices, denominated Evolvable Hardware (EHW). It was became viable with the large scale development of reconfigurable devices, whose architecture and function can be determined by programming. Each circuit can be represented as an individual within an evolutionary process, evolving through genetic operations to desire results. Genetic Algorithm (GA) was applied as evolutionary algorithm where this technique evolvable computation as concepts of genetics and natural selection. The synthesis process applied in this work starts from a description from the circuits behavior. Trust table for combinatorial circuits and state transition table for sequential circuits were used for synthesis process. This technic applied search the correct arrange and minimized circuit which response the propose function. Based on this methodology, some examples are implemented in two different representations (fuse maps and logic gate matrices).
Mestre

Le diagnostic automatique des erreurs de conception est un probleme important dans le domaine de la cao. Bien que des outils automatises de synthese soient employes pour generer des structures de circuits correctes-par-construction, celles-ci sont souvent modifiees manuellement pour refleter des petites modifications faites sur la specification, ou pour ameliorer certaines caracteristiques critiques de la conception. Les outils de verification peuvent reveler l'existence d'erreurs, mais ils ne donnent aucune information sur leurs emplacements ou la facon de les corriger. Ces outils generent seulement quelques contres-exemples qui mettent en evidence l'erreur. Les concepteurs utilisent ces contre-exemples pour diagnostiquer manuellement leur conception. Le diagnostic manuel est un processus tres lent et tres couteux. Le temps de diagnostic peut etre egal, voire superieur, au temps de conception. Nous presentons dans cette these de nouveaux algorithmes pour la localisation et la correction automatique des erreurs simples de conception dans les circuits logiques sous l'hypothese d'une seule erreur. Les erreurs traitees ici sont : le remplacement d'un composant dans les circuits combinatoires et sequentiels, et une erreur de connexion dans les circuits combinatoires. Le modele d'une seule erreur exige une strategie de verification frequente, dans laquelle la conception est verifiee apres chaque modification, pour que la probabilite d'insertion de plus d'une erreur ne soit pas trop elevee. Notre approche consiste a simuler et analyser automatiquement le circuit sous l'application de vecteurs de test que nous produisons specialement pour accelerer le diagnostic. Nous avons realise deux logiciels prototypes bases sur ces algorithmes. Ccds est l'outil de diagnostic pour les circuits combinatoires, et scds est l'outil de diagnostic pour les circuits sequentiels. Ces outils sont actuellement integres dans l'environnement de preuves prevail#t#m.

Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement, étant impossible d'écarter les puces défectueuses sans découper la plaque de silice, le problème de la superposition d'une puce viable avec une puce défectueuse se pose. Une pile de puces, étant considérées comme défectueuse si elle contient ne serait-ce qu'une puce défectueuse, la superposition non réfléchie des wafers entre eux mènerait à un rendement désastreux.Afin de générer un nombre minimum de piles défectueuses, une "cartographie" de chaque wafer candidat à la superposition est réalisée lors d'une phase de test, permettant de situer les puces défectueuses sur le wafer. Une fois cette cartographie réalisée, l'objectif est de sélectionner les wafers qui seront assemblés ensembles de manière à faire correspondre les défauts de chacun des wafers.Ce problème peut être modélisé à l'aide d'un problème d'affectation multidimensionnelle. Chaque wafer est représenté par un vecteur comportant autant de composantes que de puces sur le wafer qu'il représente. Une composante égale à zéro matérialise une puce défectueuse tandis qu'un un matérialise une puce viable. Chaque lot de wafers est représenté par un lot de vecteurs. Formellement, une instance d'empilement de wafers est représenté par m ensembles de n vecteurs binaires p-dimensionnels. L'objectif est alors de réaliser n m-uplets disjoints contenant exactement un vecteur par ensemble. Ces m-uplets représenteront les piles. Chaque m-uplet peut être représenté par un vecteur binaire p-dimensionnels, chaque composante étant calculée en réalisant le ET binaire des composantes correspondantes des vecteurs qui composent le m-uplet. Autrement dit, une composante du vecteur représentant le m-uplet est égale à un si et seulement si tous les vecteurs ont cette composante égale à un. Et donc une pile de puces est viables si toutes les puces qui la composent sont viables. L'objectif est alors de minimiser le nombre de zéros ou de maximiser le nombre de un.La thèse comporte deux grandes parties. Une partie théorique abordant la complexité des différentes versions du problèmes en fonction de certains paramètres tels que m, n, p ou encore le nombre maximum de zéros par vecteurs. Nous montrons entre autre que ces problèmes peuvent être utilisés pour modéliser des problèmes plus classiques tels que Maximum Clique, Minimum Vertex Cover ou encore k-Dimensional Matching, permettant de prouver un certain nombre de résultats négatifs que ce soit d'un point de vue de la complexité classique, l'approximabilité ou la complexité paramétrée. Nous fournissons également des résultats positifs pour des cas particuliers du problème.Dans un second temps, nous nous intéressons à la résolution pratique du problème en fournissant et comparant un certain nombre de formulations en Programmation Linéaire en Nombres Entiers. Mais nous nous intéressons également aux performances en pratique de certaines heuristiques à garantie de performances détaillées dans la partie théorique
In this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part

O estudo do comportamento assintótico de densidades de algumas subestruturas é uma das principais áreas de estudos em combinatória. Na Teoria das Permutações, fixadas permutações ?1 e ?2 e um inteiro n > 0, estamos interessados em estudar o comportamento das densidades de ?1 e ?2 na família de permutações de tamanho n. Assim, existem duas direções naturais que podemos seguir. Na primeira direção, estamos interessados em achar a permutação de tamanho n que maximiza a densidade das permutações ?1 e ?2 simultaneamente. Para n suficientemente grande, explicitamos a densidade máxima que uma família de permutações podem assumir dentre todas as permutações de tamanho n. Na segunda direção, estamos interessados em achar a permutação de tamanho n que minimiza a densidade de ?1 e ?2 simultaneamente. Quando ?1 é a permutação identidade com k elementos e ?2 é a permutação reversa com l elementos, Myers conjecturou que o mínimo é atingido quando tomamos o mínimo dentre as permutações que não possuem a ocorrência de ?1 ou ?2. Mostramos que se restringirmos o espaço de busca somente ao conjunto de permutações em camadas, então a Conjectura de Myers é verdadeira. Por outro lado, na Teoria dos Grafos, o problema de encontrar um circuito Hamiltoniano é um problema NP-completo clássico e está entre os 21 problemas Karp. Dessa forma, uma abordagem comum na literatura para atacar esse problema é encontrar condições que um grafo deve satisfazer e que garantem a existência de um circuito Hamiltoniano em tal grafo. O célebre resultado de Dirac afirma que se um grafo G de ordem n possui grau mínimo pelo menos n/2, então G possui um circuito Hamiltoniano. Seguindo a linha de Dirac, mostramos que, dados inteiros 1 6 l 6 k/2 e ? > 0 existe um inteiro n0 > 0 tal que, se um hipergrafo k-uniforme H de ordem n satisfaz ?k-2(H) > ((4(k - l) - 1)/(4(k - l)2) + ?) (n 2), então H possui um l-circuito Hamiltoniano.
The study of asymptotic behavior of densities of some substructures is one of the main areas in combinatorics. In Permutation Theory, fixed permutations ?1 and ?2 and an integer n > 0, we are interested in the behavior of densities of ?1 and ?2 among the permutations of size n. Thus, there are two natural directions we can follow. In the first direction, we are interested in finding the permutation of size n that maximizes the density of the permutations ?1 and ?2 simultaneously. We explicit the maximum density of a family of permutations between all the permutations of size n. In the second direction, we are interested in finding the permutation of size n that minimizes the density of ?1 and ?2 simultaneously. When ?1 is the identity permutation with l elements and ?2 is the reverse permutation with k elements, Myers conjectured that the minimum is achieved when we take the minimum among the permutations which do not have the occurrence of ?1 or ?2. We show that if we restrict the search space only to set of layered permutations and k > l, then the Myers\' Conjecture is true. On the other hand, in Graph Theory, the problem of finding a Hamiltonian cycle is a NP-complete problem and it is among the 21 Karp problems. Thus, one approach to attack this problem is to find conditions that a graph must meet to ensure the existence of a Hamiltonian cycle on it. The celebrated result of Dirac shows that a graph G of order n that has minimum degree at least n/2 has a Hamiltonian cycle. Following the line of Dirac, we show that give integers 1 6 l 6 k/2 and gamma > 0 there is an integer n0 > 0 such that if a hypergraph k-Uniform H of order n satisfies ?k-2(H) > ((4(k-l)-1)/(4(k-l)2)+?) (n 2), then H has a Hamiltonian l-cycle.

Orientador: Jose Raimundo de Oliveira
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
Made available in DSpace on 2018-08-09T13:54:55Z (GMT). No. of bitstreams: 1 Dias_MauricioAraujo_D.pdf: 794928 bytes, checksum: a328a640d35118ea7fb606ac9f4ab2b2 (MD5) Previous issue date: 2007
Resumo: Este trabalho propõe um sistema criptográfico para Criptografia baseada em Curvas Elípticas (ECC). ECC é usada alternativamente a outros sistemas criptográficos, como o algoritmo RSA (Rivest-Shamir-Adleman), por oferecer a menor chave e a maior segurança por bit. Ele realiza multiplicação de pontos (Q = kP) para curvas elípticas sobre corpos finitos binários. Trata-se de um criptosistema programável e configurável. Graças às propriedades do circuito programável (FPGA) é possível encontrar soluções otimizadas para diferentes curvas elípticas, corpos finitos e algoritmos. A característica principal deste criptosistema é o uso de um circuito combinacional para calcular duplicações e adições de pontos, por meio da aritmética sobre corpos finitos. Os resultados deste trabalho mostram que um programa de troca de chaves fica aproximadamente 20.483 vezes mais rápido com a ajuda do nosso sistema criptográfico. Para desenvolver este projeto, nós consideramos que o alto desempenho tem prioridade sobre a área ocupada pelos seus circuitos. Assim, nós recomendamos o uso deste circuito para os casos em que não sejam impostas restrições de área, mas seja exigido alto desempenho do sistema
Abstract: This work proposes a cryptosystem for Elliptic Curve Cryptography (ECC). ECC has been used as an alternative to other public-key cryptosystems such as the RSA (Rivest-Shamir-Adleman algorithm) by offering the smallest key size and the highest strength per bit. The cryptosystem performs point multiplication (Q = kP) for elliptic curves over binary polynomial fields (GF(2m)). This is a programmable and scalable cryptosystem. It uses the abilities of reconfigurable hardware (FPGA) to make possible optimized circuitry solutions for different elliptic curves, finite fields and algorithms. The main feature of this cryptosystem is the use of a combinatorial circuit to calculate point doublings and point additions, through finite field arithmetic. The results of this work show that the execution of a key-exchange program is, approximately, 20,483 times faster with the help of our cryptosystem. To develop this project we considered that high-performance has priority over area occupied by its circuit. Thus, we recommend the use of this circuit in the cases for which no area constraints are imposed but high performance systems are required.
Doutorado
Engenharia de Computação
Doutor em Engenharia Elétrica

In the study of Graph theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3 ∪ {e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings, and coverings of the complete digraph with the two 3-circuit with a pendant arc orientations.

In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization. Learning Parities under the Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al, this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables. Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even when there exists a halfspace that agrees with the unknown function on 1-ε fraction of examples. This significantly improves on a number of previous hardness results for this problem. We extend the result to ε = 2[superscript-Ω(sqrt{log n})] assuming NP is not contained in DTIME(2[superscript(log n)O(1)]). Majorities of Halfspaces: We show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. This also implies a hardness result for learning halfspaces with a high rate of adversarial noise even if the learning algorithm can output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the problem of finding the chromatic number of a graph. We show that for any constant γ > 0, there is no polynomial time algorithm that approximates these problems within factor n/2[superscript(log n)3/4+γ] in an n vertex graph, assuming NP is not contained in BPTIME(2[superscript(log n)O(1)]). This improves the hardness factor of n/2[superscript (log n)1-γ'] for some small (unspecified) constant γ' > 0 shown by Khot. Our main idea is to show an improved hardness result for the Min-3Lin-Deletion problem. An instance of Min-3Lin-Deletion is a system of linear equations modulo 2, where each equation is over three variables. The objective is to find the minimum number of equations that need to be deleted so that the remaining system of equations has a satisfying assignment. We show a hardness factor of 2[superscript sqrt{log n}] for this problem, improving upon the hardness factor of (log n)[superscriptβ] shown by Hastad, for some small (unspecified) constant β > 0. The hardness results for Max-Clique and chromatic number are then obtained using the reduction from Min-3Lin-Deletion as given by Khot. Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching: A monotone Boolean circuit is said to be multilinear if for any AND gate in the circuit, the minimal representation of the two input functions to the gate do not have any variable in common. We show that monotone multilinear Boolean circuits for computing bipartite perfect matching require exponential size. In fact we prove a stronger result by characterizing the structure of the smallest monotone multilinear Boolean circuits for the problem.

Krivelevich and Patkós conjectured in 2009 that χ(G(n, p)) ∼ χ=(G(n, p)) ∼ χ∗=(G(n, p)) for C/n < p < 1 − ε, where ε > 0. We prove this conjecture for n−1+ε1 < p < 1 − ε2 where ε1, ε2 > 0. We investigate several measures that have been proposed to indicate centrality of nodes in networks, and find examples of networks where they fail to distinguish any of the vertices nodes from one another. We develop a new method to investigate core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. Finally, we present an experiment and an analysis of empirical networks, functional human brain networks. We found that reconfiguration patterns of dynamic communities can be used to classify nodes into a stiff core, a flexible periphery, and a bulk. The separation between this stiff core and flexible periphery changes as a person learns a simple motor skill and, importantly, it is a good predictor of how successful the person is at learning the skill. This temporally defined core-periphery organisation corresponds well with the core- periphery detected by the method that we proposed earlier the static networks created by averaging over the subjects dynamic functional brain networks.

Cette thèse vise à développer des stratégies permettant d'augmenter la puissance du calcul séquentiel et des systèmes distribués, elle traite en particulier, la décomposition séquentielle des opérations ainsi que des systèmes d'édition collaboratifs décentralisés. La croissance rapide de l'utilisation des nouvelles technologies informatiques résulte de la nécessité d'avoir des performances élevées, dans tout domaine lié au calcul informatique. Une telle quête de performances a abouti à une plus grande complexité dans les architectures informatiques, conduisant à un stress non négligeable dans la technologie des compilateurs. De puissants microprocesseurs se trouvent au cœur de toute machine informatique, allant des serveurs et ordinateurs personnels, aux ordinateurs portables, jusqu'aux téléphones cellulaires " iPhone ". En effet, l'augmentation incessante des performances constitue un défi permanent dans les sciences informatiques. Par ailleurs, le développement rapide des réseaux informatiques a conduit à un progrès vers une édition collaborative en temps réel (RCE). Cette dernière permet à des groupes d'utilisateurs l'édition simultanée de documents partagés résidant dans des sites physiques dispersés, mais interconnectés par un réseau informatique. Dans de tels systèmes distribués, les conflits liés aux communications sont un défi à relever. De ce fait, la communication indexée devient une nécessité absolue. Nous introduisons, une méthode d'indexage avec précision contrôlée. Celle-ci permet la génération d'identifiants uniques utilisés dans l'indexage des communications dans les systèmes distribués, plus particulièrement dans les systèmes d'édition collaboratifs décentralisés. Ces identifiants sont des nombres réels avec un motif de précision contrôlé. Un ensemble fini d'identifiants est conservé pour permettre le calcul de cardinalités locales et globales. Cette propriété joue un rôle prépondérant dans la gestion des communications indexées. De plus, d'autres propriétés incluant la préservation de l'ordre sont observées. La méthode d'indexage a été testée et vérifiée avec succès. Ceci a permis la conception d'un système d'édition collaboratif décentralisé. Aussi, nous explorons les stratégies existantes, relatives a la décomposition séquentielle d'opérations, que nous étendons à de nouvelles stratégies. Ces stratégies mènent à une optimisation (processeur, compilateur, mémoire, code). Ces styles de décomposition portent un intérêt majeur à la communauté scientifique. Des recherches et des implémentations de plus en plus rapides résultent de la conception d'unité arithmétique.

La conception de l'appareillage électrique relève dune méthodologie généralement fort complexe. Les problèmes posés par la conception de l'appareillage électrique sont analysés et montrent l'inefficacité des méthodes mathématiques. Une approche ensembliste floue est exposée et permet de modéliser l'aspect heuristique du problème ainsi que les aspects scientifiques et industriels de la conception. Un système expert d'aide à la conception des disjoncteurs à arc tournant a été réalisé. Les résultats obtenus sont commentés et montrent l'intérêt d'une telle approche

碩士
國立中興大學
電機工程學系
93
For a quantum computer, the synthesis of quantum Boolean circuits is an essential aim. In addition, it seems that constructing a circuit with an n-bit Toffoli gatewith n 3 is neither practical nor economical. In this paper, we introduce a heuristic algorithm for synthesizing any combinational quantum Boolean circuit with a gate library containing only Not, CNot and Toffoli gates. Our algorithm mainly adopts the primary linking rule and secondary linking rule to simplify a circuit. Moreover, we propose a method for selecting a path with lower cost during the simplification process. Finally, we propose another method, which analyzes the simplified circuit and finds out common terms, to further reduce the circuit cost. In the context, we employ some examples, in company with the Karnaugh map presentation, to explain our algorithm.

碩士
國立中山大學
電機工程研究所
84
The diagnostic problem arises when the observed behavior of a system deviates from the expectation. Assuming that the design of the system is correct in the sense that it is con- sistent with its specification, a diagnosis is a hypothesis of faults within the system under the observations obtained so far which can explain the discrepancies between the expected and the actual behavior of the system. The reason to perform diag- nosis is that by replacing only the faulty components of a mal- functioning system, one can repair the system instead of re- placing it, and the former solution is usually more economical and practical. In this thesis we focus on model-based diagnosis, in par- ticular, the theory of diagnosis from first principles. We augment and clarify Hou's theory of measurement with supplementary proofs, and revise the incomplete method for minimal conflict set derivation with a complete, efficient and proved derivation approach using a CS-tree (conflict set tree) with mark set. A measurement selection strategy using the ge- netic algorithm (MSSGA) is proposed to select the best next mea- surement in a diagnostic process, and the results of a series of experiments show that this approach is promising. Finally a complete diagnostic system for combinatorial digital circuits (DSDC) is proposed and implemented. DSDC receives a circuit specification in DSDC Language (DSDCL), and automatically locates the culprits within the circuit. In addition, it is capable of improving its performance online by incorporating MSSGA as its measurement selection strategy.

We engineered several synthetic regulatory circuits to study transcriptional regulation in bacteria. We developed a new technique for DNA construction, built and characterized in vivo a library of genetic logic gates, examined the role of genetic noise transcriptional regulation using a fluorescent multi-reporter system, and characterized a synthetic circuit for the control of population density.

We used synthetic duplex DNA fragments and very short cohesive overhangs to direct ordered assemblies of diverse combinatorial libraries. Multiple DNA fragments were simultaneously ligated in a single step to produce random concatemers, without the need for amplification or product purification. We characterized the assembly process to identify optimal cohesive overhangs. We showed that the method was 97% efficient for assembling 100 base-pair concatemers from three duplex fragments.

We constructed a library of 10,000 prokaryotic promoters, containing over 1,000 unique 100 base-pair sequences. These promoters responded to up to three inputs, and contained diverse architectural arrangements of regulatory sequences. We characterized the logical input functions of 288 promoters in Escherichia coli, and analyzed the relationship between promoter function and architecture. We defined promoter function in terms of regulatory range, logic type, and input symmetry; and identified general rules for combinatorial programming of gene expression.

We built a synthetic three-color fluorescent reporter framework. This construct was non-toxic and extensible for synthetic and systems biology applications. Three spectrally distinct and genetically isolated reporter proteins allowed independent monitoring of genetic signals at the single-cell level. We showed that the simultaneous measurement of multiple genes can exploit genetic noise to sensitively detect transcriptional co-regulation.