No description available.

With the increased complexity of Very Large Scale Integrated (VLSI) circuits, Computer Aided Design (CAD) plays an even more important role. Top-down design methodology and layout of VLSI are reviewed. Moreover, previously published algorithms in CAD of VLSI design are outlined. In certain applications, Reed-Muller (RM) forms when implemented with AND/XOR or OR/XNOR logic have shown some attractive advantages over the standard Boolean logic based on AND/OR logic. The RM forms implemented with OR/XNOR logic, known as Dual Forms of Reed-Muller (DFRM), is the Dual form of traditional RM implemented with AND /XOR. Map folding and transformation techniques are presented for the conversion between standard Boolean and DFRM expansions of any polarity. Bidirectional multi-segment computer based conversion algorithms are also proposed for large functions based on the concept of Boolean polarity for canonical product-of-sums Boolean functions. Furthermore, another two tabular based conversion algorithms, serial and parallel tabular techniques, are presented for the conversion of large functions between standard Boolean and DFRM expansions of any polarity. The algorithms were tested for examples of up to 25 variables using the MCNC and IWLS'93 benchmarks. Any n-variable Boolean function can be expressed by a Fixed Polarity Reed-Muller (FPRM) form. In order to have a compact Multi-level MPRM (MMPRM) expansion, a method called on-set table method is developed. The method derives MMPRM expansions directly from FPRM expansions. If searching all polarities of FPRM expansions, the MMPRM expansions with the least number of literals can be obtained. As a result, it is possible to find the best polarity expansion among 2n FPRM expansions instead of searching 2n2n - 1 MPRM expansions within reasonable time for large functions. Furthermore, it uses on-set coefficients only and hence reduces the usage of memory dramatically. Currently, XOR and XNOR gates can be implemented into Look-Up Tables (LUT) of Field Programmable Gate Arrays (FPGAs). However, FPGA placement is categorised to be NP-complete. Efficient placement algorithms are very important to CAD design tools. Two algorithms based on Genetic Algorithm (GA) and GA with Simulated Annealing (SA) are presented for the placement of symmetrical FPGA. Both of algorithms could achieve comparable results to those obtained by Versatile Placement and Routing (VPR) tools in terms of the number of routing channel tracks.

Finding an optimal solution for the logic circuit design problem is challenging and time-consuming especially for complex logic circuits. As the number of logic gates increases the task of designing optimal logic circuits extends beyond human capability. A number of evolutionary algorithms have been invented to tackle a range of optimisation problems, including logic circuit design. This dissertation explores two of these evolutionary algorithms i.e. Gene Expression Programming (GEP) and Multi Expression Programming (MEP) with the aim of integrating their strengths into a new Genetic Programming (GP) algorithm. GEP was invented by Candida Ferreira in 1999 and published in 2001 [8]. The GEP algorithm inherits the advantages of the Genetic Algorithm (GA) and GP, and it uses a simple encoding method to solve complex problems [6, 32]. While GEP emerged as powerful due to its simplicity in implementation and exibility in genetic operations, it is not without weaknesses. Some of these inherent weaknesses are discussed in [1, 6, 21]. Like GEP, MEP is a GP-variant that uses linear chromosomes of xed length [23]. A unique feature of MEP is its ability to store multiple solutions of a problem in a single chromosome. MEP also has an ability to implement code-reuse which is achieved through its representation which allow multiple references to a single sub-structure. This dissertation proposes a new GP algorithm, Improved Gene Expression Programming (IGEP) which im- proves the performance of the traditional GEP by combining the code-reuse capability and simplicity of gene encoding method from MEP and GEP, respectively. The results obtained using the IGEP and the traditional GEP show that the two algorithms are comparable in terms of the success rate when applied on simple problems such as basic logic functions. However, for complex problems such as one-bit Full Adder (FA) and AND-OR Arithmetic Logic Unit (ALU) the IGEP performs better than the traditional GEP due to the code-reuse in IGEP / Mathematical Sciences / M. Sc. (Applied Mathematics)