The growing complexity of integrated circuits and the large variety of architectures of Field Programmable Gate Arrays (FPGAs) require sophisticated logic design tools. In the beginning of the eighties the research in logic design was concentrated on the development of fast two-level AND-OR logic minimizers like the well known ESPRESSO. However, most logic functions have a smaller and often faster circuit realization as a multi-level circuit. Thus, synthesis tools emerged for the minimization of the circuit area in a multi-level realization. Most of these synthesis tools are based on the "unate paradigm". Therefore, the synthesis methods are only advantageous for functions having a minimal circuit realization based on AND-OR gates. However, many common functions have a minmal circuit realization having a mix of AND, OR and EXOR gates like counters, adders, multipliers, and parity generators. Therefore, the design of such functions with synthesis tools based on the "unated paradigm" is very inefficient. Circuits incorporating the EXOR gate have received less attention than AND-OR circuits because the EXOR gate was perceived as slower and larger in terms of its circuit realization than the AND and the OR gate. However, the upcoming of Field Programmable Gate Arrays (FPGAs) like the Xilinx Table-Look-Up (TLU) architecture the Actel ACTâ„¢ series and the CLi 6000 series from Concurrent Logic, which allow the realization of the EXOR gate with the same speed and circuit cost as the AND and OR gate, eliminates the disadvantages of the EXOR gate over the AND and OR gate. Thus, there is a strong need for logic synthesis tools that take advantage of EXOR gates. The mapping to the new FPGAs recently obtained an increased interest. The developed synthesis algorithms for FPGAs are based on the mapping and restructuring of the Directed Acyclic Graph (DAG) representation of the logic function. Even though the new FPGAs allow the realization of the EXOR gate without any speed and circuit size penalty in comparison to the AND and OR gate, the synthesis methods have been based on the "unate paradigm". To overcome the disadvantages of the current logic synthesis tools with respect to (nearly) linear functions and FPGA synthesis, this dissertation introduces an extended theory of spectral methods for multiple-valued input, incompletely specified binary output logic. The spectral methods have not been popular in logic synthesis because of their four major drawbacks: (1) the computational complexity, especially if no Fast Transform exists, (2) the memory requirement to store the function in the necessary minterm representation, (3) they cannot take efficiently advantage of incompletely specified functions, (4) suitable only for few applications in logic synthesis. To overcome the two last stated drawbacks, this dissertation introduces the T spectrum. The T spectrum separates the information obtained for the specified and not specified parts of the underlying function. Thus, it is possible to determine directly the contribution of the specified and the not specified part of the function to a single spectral coefficient. Moreover, the T spectrum is an extension of the known spectra like Walshtype, Adding, Arithmetic, and Reed-Muller spectra to any orthogonal and nonorthogonal transform describing logic functions. Thus, transforms can be constructed that describe certain gate structures, as for example the realizable functions of a FPGA macrocell. This allows the development of special synthesis algorithms for the different types of FPGA architectures. As an exemplification of this method, a complete multi-level synthesis algorithm is introduced for the circuit realization with multiplexer modules, which form the basic macrocell of the Actel ACfâ„¢ FPGA series. Additionally, this dissertation presents the classification of the applications of spectral methods in logic synthesis into three categories: (1) The decomposition of logic functions based on the information obtained by the computation of a single spectrum. As an example the linearization procedure developed by Karpowsky is generalized to incompletely specified multi-output Boolean functions. The linearization procedure is based on the computation of the Rademacher-Walsh spectrum with a following decomposition of the underlying function based on high value spectral coefficients. (2) The circuit realization of a logic function based on the repetitive application of (1). This synthesis method is exemplified by an multi-level synthesis algorithm for multiplexer gates. (3) The realization of a logic function as an AND-EXOR circuit based on a GF 2 (Galois Field (2)) spectrum. The GF 2 transforms exhibit the property that they describe a realization of the underlying function as a two-level AND-EXOR circuit. The Multiple-Valued Input Kronecker Reed-Muller (MIKRM) form is introduced as an application of GF 2 transforms. To overcome the drawbacks of spectral methods concerning the computational complexity and high memory requirements, this dissertation presents a computation method for spectra from disjoint representations. The introduced application of the disjoint cube representation and the Ordered Decision Diagrams for the computation of spectra proves to be an ideal concept. Thus, this dissertation presents general synthesis methods based on new spectral methods that overcome the deficiencies of current logic synthesis methods with respect to the synthesis for FPGAs as well as the computational complexity and memory requirements of spectral methods.

published_or_final_version / abstract / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

by Lo Wing-yee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Includes bibliographical references (leaves vii-ix). / ABSTRACT --- p.i / LIST OF TABLES --- p.iv / LIST OF FIGURES --- p.v / Chapter 1. --- INTRODUCTION --- p.1 / Chapter 1.1 --- Traditional Design Prototyping --- p.1 / Chapter 1.2 --- In-Circuit Rapid Prototyping System --- p.2 / Chapter 1.3 --- A Summary of Prototyping Systems Available --- p.5 / Chapter 1.4 --- Universal Prototyping Board (UPB) --- p.6 / Chapter 2. --- HARDWARE DESIGNS --- p.9 / Chapter 2.1 --- Bus Interconnection --- p.9 / Chapter 2.1.1 --- Fixed buses --- p.9 / Chapter 2.1.2 --- Programmable buses --- p.12 / Chapter 2.2 --- Architectural Features --- p.15 / Chapter 2.2.1 --- Field programmable gate array --- p.15 / Chapter 2.2.2 --- Microprocessor --- p.15 / Chapter 2.2.3 --- Memory --- p.16 / Chapter 2.2.4 --- Buffers --- p.18 / Chapter 3. --- SOFTWARE TOOLS --- p.20 / Chapter 3.1 --- Critical Path Analysis --- p.20 / Chapter 3.1.1 --- Algorithm of critical path analysis --- p.21 / Chapter 3.1.2 --- Computation time --- p.21 / Chapter 3.2 --- Circuit Partitioning --- p.23 / Chapter 3.2.1 --- Partitioning algorithm --- p.24 / Chapter 3.2.2 --- Effects of partitioning --- p.36 / Chapter 3.2.3 --- Partitioning parameters --- p.38 / Chapter 3.2.4 --- Pseudo-code of partitioner --- p.39 / Chapter 3.3 --- IO Assignments --- p.40 / Chapter 3.3.1 --- Connect 4 FPGAs --- p.40 / Chapter 3.3.2 --- Connect 3 FPGAs --- p.42 / Chapter 3.3.3 --- Connect 2 FPGAs --- p.44 / Chapter 3.3.4 --- System IO (Connect 1 FPGA) --- p.47 / Chapter 3.4 --- Other Tools --- p.48 / Chapter 4. --- STRUCTURE ANALYSIS --- p.49 / Chapter 5. --- RESULTS --- p.52 / Chapter 6. --- FUTURE DIRECTION --- p.73 / Chapter 6.1 --- Other Possible Configurations --- p.73 / Chapter 6.2 --- Programmable Interconnection --- p.73 / Chapter 6.3 --- Expandability of UPB --- p.74 / Chapter 7. --- CONCLUSION --- p.75 / BIBLIOGRAPHY --- p.vii / APPENDICES --- p.x

"It is widely recognized that security issues will play a crucial role in the majority of future computer and communication systems. A central tool for achieving system security are cryptographic algorithms. For performance as well as for physical security reasons, it is often advantageous to realize cryptographic algorithms in hardware. In order to overcome the well-known drawback of reduced flexibility that is associated with traditional ASIC solutions, this contribution proposes arithmetic architectures which are optimized for modern field programmable gate arrays (FPGAs). The proposed architectures perform modular exponentiation with very long integers. This operation is at the heart of many practical public-key algorithms such as RSA and discrete logarithm schemes. We combine two versions of Montgomery modular multiplication algorithm with new systolic array designs which are well suited for FPGA realizations. The first one is based on a radix of two and is capable of processing a variable number of bits per array cell leading to a low cost design. The second design uses a radix of sixteen, resulting in a speed-up of a factor three at the cost of more used resources. The designs are flexible, allowing any choice of operand and modulus. Unlike previous approaches, we systematically implement and compare several versions of our new architecture for different bit lengths. We provide absolute area and timing measures for each architecture on Xilinx XC4000 series FPGAs. As a first practical result we show that it is possible to implement modular exponentiation at secure bit lengths on a single commercially available FPGA. Secondly we present faster processing times than previously reported. The Diffie-Hellman key exchange scheme with a modulus of 1024 bits and an exponent of 160 bits is computed in 1.9 ms. Our fastest design computes a 1024 bit RSA decryption in 3.1 ms when the Chinese remainder theorem is applied. These times are more than ten times faster than any reported software implementation. They also outperform most of the hardware-implementations presented in technical literature."

"This thesis describes a co-processor system that has been designed to accelerate computations associated with Singular Value Array Reconciliation Tomography (SART), a method for locating a wide-band RF source which may be positioned within an indoor environment, where RF propagation characteristics make source localization very challenging. The co-processor system is based on field programmable gate array (FPGA) technology, which offers a low-cost alternative to customized integrated circuits, while still providing the high performance, low power, and small size associated with a custom integrated solution. The system has been developed in VHDL, and implemented on a Virtex-4 SX55 FPGA development platform. The system is easy to use, and may be accessed through a C program or MATLAB script. Compared to a Pentium 4 CPU running at 3 GHz, use of the co-processor system provides a speed-up of about 6 times for the current signal matrix size of 128-by-16. Greater speed-ups may be obtained by using multiple devices in parallel. The system is capable of computing the SART metric to an accuracy of about -145 dB with respect to its true value. This level of accuracy, which is shown to be better than that obtained using single precision floating point arithmetic, allows even relatively weak signals to make a meaningful contribution to the final SART solution."

Most existing computers today are built upon a subset of the arithmetic system which is based upon the foundation of set theory. All formal systems can be expressed in terms of arithmetic and logic on current arithmetic computers through an appropriate model, then work with the model using software manipulation. However, severe speed degradation is the price one must pay for using a software-based approach, making several high-level formal systems impractical. To improve the speed at which computers can implement these high-level systems, one must either design special hardware, implementing specific operations much like math and image processing coprocessors, or execute operations upon multiple processors in a parallel fashion. Due to the increase in developing applications for the manipulation of logic functions, an interest in the logic machine has arisen. Many applications such as logic optimization, simulation, pattern recognition and image processing can be better implemented with a logic machine. This thesis proposes the design, hardware realization, and testing of the iterative logic unit (ILU) of the Cube Calculus Machine II (CCM2). The CCM2 is a general purpose computer with an architecture that emphasizes a data path designed to execute operations of cube calculus, a popular algebraic model used in the minimization of Boolean functions. The ILU is an iterative logic array of cells (ITs) using internal distributed control, enabling the execution of basic cube operations, while the Control Unit (CU) handles global signals from the host computer. The ILU of the CCM2 has been realized in hardware using Xilinx Logic Cell Arrays (LCAs). FPGAs offer the logic density and versatility of gate arrays, with the off-the shelf availability and time-to-market advantages of standard user-programmable devices. These devices can be reconfigured, allowing multiple revisions and future design generations to accommodate the same device, thus saving design and production costs, an ideal solution to the resource and financial problems plaguing the University environment.

The new family of Field Programmable Gate Arrays, CLI 6000 from Concurrent Logic Inc realizes truly Cellular Logic. It has been mainly designed for the realization of data path architectures. However, the realizable logic functions provided by its macrocells and their limited connectivity call also for new general-purpose logic synthesis methods. The basic cell of CLi 6000 can be programmed to realize a two-input multiplexer ( A*B + C*B ), an AND/EXOR cell ( A*B Ea C ), or the basic 2-input AND, OR and EXOR gate. This suggests to using these cells for tree-like expansions. These "cellular logic" devices require regular connection patterns in the netlists resulting from logic synthesis. This thesis presents a synthesis tree searching program PROMPT, which generates AND/EXOR tree circuits from given Boolean functions. Such circuits have the property that the gate structures are AND/EXOR ( A *B EB C ), AND and EXOR which could be realized by the CLI6000 cells. Also, the connection. way in the circuit is that usually the output of one level gate is the input of the next level gate of the tree. This matches ideally to the architecture of the CLI6000 bussing network where the macrocells have only connections to their neighboring cells. PROMPT is based on the Davio expansions ( an equivalent of the Shannon expansions for the EXOR gates ) as its Boolean decomposition methods. The program includes three versions: exact version, heuristic version and fixed-variable version. The exact version of PROMPT generates the Permuted Reed-Muller Tree circuit which has the minimum number of gates. Such tree circuit is obtained by searching through all possible combinations of the expansion variable orders to get the one which needs the least number of gates. The heuristic version of PROMPT is designed to decrease the time complexity of the search algorithm when dealing with logic functions having many input variables. It generates a Permuted Reed-Muller Tree which may not have the minimum number of gates. However, the tree searching time in this version decreases tremendously compared to the time necessary in the exact version. The fix-variable version is developed to generate Reed-Muller Tree circuits. Such circuits will have the same expansion variables at the same tree level, so they can be easier routed after the placement to the CLI6000 chips. In short, the program PROMPT generates the PRM and RM tree circuits which are particularly well matched to both the realization of logic cell and connection structure of the CLI6000 device. Thus, the PRM and RM circuits can be easily placed and routed on the CLI6000 FPGAs.

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--University of Texas at Austin, 2000. / Vita. Includes bibliographical references (leaves 158-172). Available also in a digital version from Dissertation Abstracts.

Thesis (Ph. D.)--University of Texas at Austin, 2000. / Vita. Includes bibliographical references (leaves 111-119). Available also in a digital version from Dissertation Abstracts.