Thesis (Ph.D.)--Victoria University of Wellington, 2009. / Includes bibliographical references and index.

In the thesis a new way of checking whether a function is CCZ-equivalent to a permutation is given. The results for known families of almost perfect nonlinear (APN) functions are presented for functions defined over GF(2n ), for even n ≤ 12. The ways how to reduce the number of polynomials from each family are studied. For functions of the form x3 + a-1 tr1(a3 x9 ) it is shown, that they cannot be CCZ-equivalent to a permutation on fields GF(24n ) for n ∈ ℕ .

Orientador: Reginaldo Palazzo Júnior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-19T17:49:58Z (GMT). No. of bitstreams: 1 Oliveira_AndersonJosede_M.pdf: 1619063 bytes, checksum: 79a49301084eecde745f0e73cddfc1fa (MD5) Previous issue date: 2012 / Resumo: Uma área de pesquisa em franca expansão é a modelagem matemática do código genético, por meio da qual pode-se identificar as características e propriedades do mesmo. Neste trabalho apresentamos alguns modelos matemáticos aplicados à biologia, especificamente relacionado ao código genético. Os objetivos deste trabalho são: a) caracterização da hidropaticidade dos aminoácidos através da construção de reticulados booleanos e diagramas de Hasse associados a cada rotulamento do código genético, b) proposta de um algoritmo soma com transporte para efetuar a soma entre códons, ferramenta importante em análises mutacionais, c) representação polinomial dos códons do código genético, d) comparação dos resultados dos rotulamentos A, B e C em cada uma das modelagens construídas, e) análise do comportamento dos aminoácidos em cada um dos rotulamentos do código genético. Os resultados encontrados permitem a utilização de tais ferramentas em diversas áreas do conhecimento como bioinformática, biomatemática, engenharia genética, etc, devido a interdisciplinaridade do trabalho, onde elementos de biologia, matemática e engenharia foram utilizados / Abstract: A research area in frank expansion is the mathematical modeling of the genetic code, through can identify the characteristics and properties of them. In this paper we present some mathematical models applied to biology, specifically related to the genetic code. The aims of this work are: a) a characterization of the hydropathy of the amino acids through the construction of boolean lattices and Hasse diagrams associated with each labeling of the genetic code, b) the proposal of a sum algorithm of transportation to make the sum of codons, important tool in mutational analysis, c) a polynomial representation of the codons of the genetic code, d) a comparing of the results of the A, B and C labels in each of the built modeling, e) an analysis of the behavior of the amino acids in each of the labels of the genetic code. The results allow the use of such tools in a lot of areas like bio informatics, biomathematics, genetic engineering, etc., due to the interdisciplinary of the paper, where elements of biology, mathematics and engineering were used / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Optimisation heuristics rely on implicit or explicit assumptions about the structure of the black-box fitness function they optimise. A review of the literature shows that understanding of structure and linkage is helpful to the design and analysis of heuristics. The aim of this thesis is to investigate the role that problem structure plays in heuristic optimisation. Many heuristics use ordinal operators; which are those that are invariant under monotonic transformations of the fitness function. In this thesis we develop a classification of pseudo-Boolean functions based on rank-invariance. This approach classifies functions which are monotonic transformations of one another as equivalent, and so partitions an infinite set of functions into a finite set of classes. Reasoning about heuristics composed of ordinal operators is, by construction, invariant over these classes. We perform a complete analysis of 2-bit and 3-bit pseudo-Boolean functions. We use Walsh analysis to define concepts of necessary, unnecessary, and conditionally necessary interactions, and of Walsh families. This helps to make precise some existing ideas in the literature such as benign interactions. Many algorithms are invariant under the classes we define, which allows us to examine the difficulty of pseudo-Boolean functions in terms of function classes. We analyse a range of ordinal selection operators for an EDA. Using a concept of directed ordinal linkage, we define precedence networks and precedence profiles to represent key algorithmic steps and their interdependency in terms of problem structure. The precedence profiles provide a measure of problem difficulty. This corresponds to problem difficulty and algorithmic steps for optimisation. This work develops insight into the relationship between function structure and problem difficulty for optimisation, which may be used to direct the development of novel algorithms. Concepts of structure are also used to construct easy and hard problems for a hill-climber.

We study two classes of problems within sublinear algorithms: data structures for approximate nearest neighbor search, and property testing of Boolean functions. We develop algorithmic and analytical tools for proving upper and lower bounds on the complexity of these problems, and obtain the following results: * We give data structures for approximate nearest neighbor search achieving state-of-the-art approximations for various high-dimensional normed spaces. For example, our data structure for 𝘢𝘳𝘣𝘪𝘵𝘳𝘢𝘳𝘺 normed spaces over R𝘥 answers queries in sublinear time while using nearly linear space and achieves approximation which is sub-polynomial in the dimension. * We prove query complexity lower bounds for property testing of three fundamental properties: 𝘬-juntas, monotonicity, and unateness. Our lower bounds for non-adaptive junta testing and adaptive unateness testing are nearly optimal, and the lower bound for adaptive monotonicity testing is the best that is currently known. * We give an algorithm for testing unateness with nearly optimal query complexity. The algorithm is crucially adaptive and based on a novel analysis of binary search over long paths of the hypercube.

Spectral techniques in digital logic design have been known for more than thirty years. They have been used for Boolean function classification, disjoint decomposition, parallel and serial linear decomposition, spectral translation synthesis (extraction of linear pre- and post-filters), multiplexer synthesis, prime implicant extraction by spectral summation, threshold logic synthesis, estimation of logic complexity, testing, and state assignment. This dissertation resolves many important issues concerning the efficient application of spectral methods used in the computer-aided design of digital circuits. The main obstacles in these applications were, up to now, memory requirements for computer systems and lack of the possibility of calculating spectra directly from Boolean equations. By using the algorithms presented here these obstacles have been overcome. Moreover, the methods presented in this dissertation can be regarded as representatives of a whole family of methods and the approach presented can be easily adapted to other orthogonal transforms used in digital logic design. Algorithms are shown for Adding, Arithmetic, and Reed-Muller transforms. However, the main focus of this dissertation is on the efficient computer calculation of Rademacher-Walsh spectra of Boolean functions, since this particular ordering of Walsh transforms is most frequently used in digital logic design. A theory has been developed to calculate the Rademacher-Walsh transform from a cube array specification of incompletely specified Boolean functions. The importance of representing Boolean functions as arrays of disjoint ON- and DC- cubes has been pointed out, and an efficient new algorithm to generate disjoint cubes from non-disjoint ones has been designed. The transform algorithm makes use of the properties of an array of disjoint cubes and allows the determination of the spectral coefficients in an independent way. By such an approach each spectral coefficient can be calculated separately or all the coefficients can be calculated in parallel. These advantages are absent in the existing methods. The possibility of calculating only some coefficients is very important since there are many spectral methods in digital logic design for which the values of only a few selected coefficients are needed. Most of the current methods used in the spectral domain deal only with completely specified Boolean functions. On the other hand, all of the algorithms introduced here are valid, not only for completely specified Boolean functions, but for functions with don't cares. Don't care minterms are simply represented in the form of disjoint cubes. The links between spectral and classical methods used for designing digital circuits are described. The real meaning of spectral coefficients from Walsh and other orthogonal spectra in classical logic terms is shown. The relations presented here can be used for the calculation of different transforms. The methods are based on direct manipulations on Karnaugh maps. The conversion start with Karnaugh maps and generate the spectral coefficients. The spectral representation of multiple-valued input binary functions is proposed here for the first time. Such a representation is composed of a vector of Walsh transforms each vector is defined for one pair of the input variables of the function. The new representation has the advantage of being real-valued, thus having an easy interpretation. Since two types of codings of values of binary functions are used, two different spectra are introduced. The meaning of each spectral coefficient in classical logic terms is discussed. The mathematical relationships between the number of true, false, and don't care minterms and spectral coefficients are stated. These relationships can be used to calculate the spectral coefficients directly from the graphical representations of binary functions. Similarly to the spectral methods in classical logic design, the new spectral representation of binary functions can find applications in many problems of analysis, synthesis, and testing of circuits described by such functions. A new algorithm is shown that converts the disjoint cube representation of Boolean functions into fixed-polarity Generalized Reed-Muller Expansions (GRME). Since the known fast algorithm that generates the GRME, based on the factorization of the Reed-Muller transform matrix, always starts from the truth table (minterms) of a Boolean function, then the described method has advantages due to a smaller required computer memory. Moreover, for Boolean functions, described by only a few disjoint cubes, the method is much more efficient than the fast algorithm. By investigating a family of elementary second order matrices, new transforms of real vectors are introduced. When used for Boolean function transformations, these transforms are one-to-one mappings in a binary or ternary vector space. The concept of different polarities of the Arithmetic and Adding transforms has been introduced. New operations on matrices: horizontal, vertical, and vertical-horizontal joints (concatenations) are introduced. All previously known transforms, and those introduced in this dissertation can be characterized by two features: "ordering" and "polarity". When a transform exists for all possible polarities then it is said to be "generalized". For all of the transforms discussed, procedures are given for generalizing and defining for different orderings. The meaning of each spectral coefficient for a given transform is also presented in terms of standard logic gates. There exist six commonly used orderings of Walsh transforms: Hadamard, Rademacher, Kaczmarz, Paley, Cal-Sal, and X. By investigating the ways in which these known orderings are generated the author noticed that the same operations can be used to create some new orderings. The generation of two new Walsh transforms in Gray code orderings, from the straight binary code is shown. A recursive algorithm for the Gray code ordered Walsh transform is based on the new operator introduced in this presentation under the name of the "bi-symmetrical pseudo Kronecker product". The recursive algorithm is the basis for the flow diagram of a constant geometry fast Walsh transform in Gray code ordering. The algorithm is fast (N 10g2N additions/subtractions), computer efficient, and is implemented

No description available.

The memory cells used in modern field programmable gate arrays (FPGAs) are highly susceptible to single event upsets (SEUs). The typical mitigation strategy in the industry is some form of hardware redundancy in the form of duplication with comparison (DWC) or triple modular redundancy (TMR). While this strategy is highly effective in masking out the effect of faults, it incurs a large hardware cost. In this thesis, we explore a different approach to hardware redundancy. The core idea of our approach is to exploit the conflict-driven clause learning (CDCL) mechanism in modern Boolean satisfiability (SAT) solvers to provide us with invariants which can be realized as hardware checkers. Furthermore, we develop the algorithms required to select a subset of these invariants to be included as part of a checker circuit. This checker circuit then augments the original FPGA design. We find which look-up table (LUT) memory cells are sensitive to bitflips, then we automatically generate a checker circuit consisting of hardware invariants targeted towards those faults. We aim to reach 100% coverage of sensitizable faults. After extensive experimentation, we conclude that this approach is not competitive with DWC with respect to hardware area. However, we demonstrate that many bitflips will have reduced a detection latency compared to DWC. / Thesis / Master of Applied Science (MASc)

In this episode, we take a break from proving identities of Boolean algebra and start applying them. Why? Well, so we can build our Boolean logic circuits with fewer gates. That means they’ll be cheaper, smaller, and faster. That’s why.

Truth tables and circuit diagrams fall short in many ways including their abilities to evaluate and manipulate combinational logic. By using algebraic methods to represent logic expressions, we can apply properties and identities to improve performance.