Research On Designing Methods Of Combinational Logic Circuits And Polymorphic Logic Circuits

Evolvable Hardware (EHW) is a kind of hardware which can adapt itself to the new environment by reorganizing its structure automatically. With features of self-organizing, self-adapting, self-repairing and fault-tolerance, the EHW technique could make the system work correctly with a higher reliability and have a better chance to survive in an extreme and unknown environment. The EHW technique also provides a new way for designing circuits. With the ability of exploring the whole solution space, the EHW technique could find some novel hardware structures which possess the features of low-power, fault-tolerance and area-efficency. The EHW technique has already generate some small circuits successfully. However, the EHW faces the scaling problem, i.e. it is hard to generate large scale circuits, which limits its use in the real applications.Up to now, the target circuits of the EHW technique are mainly traditional combinational digital logic circuits, sequential logic circuits or analog circuits. However, nowadays, with the adventure of polymorphic electronics, polymorphic circuits have opened a new way for the EHW. Different from the traditional electronics, polymorphic components possess intrinsically build-in multiple functions. In different circumstances, a polymorphic component would behave differently. With the characteristics of build-in multi-functions and sensitiveness to the environment signal, the combination of polymorphic circuits and the EHW technique could build new self-adaptive circuits and systems.The purpose of the dissertation is to study the evolutionary methods for designing combinational logic circuits, the approach for designing large scale polymorphic logic circuits and the completeness theory of the polymorphic circuits. The main research work consists of the following four parts.(1) A Step Dimension Reduction approach (SDR) is proposed for designing combinational digital logic circuits. The SDR divides the whole circuit into several layers. As for a circuit with one output, the number of input combinations is expected to be reduced layer-by-layer. The current layer's outputs are the next layer's inputs. All layers are evolved separately one after another, and assembled to form a final solution. However, as for some complex circuits (such as 5x5 multiplier), some layers in the SDR are difficult to be evolved. Therefore, the eXtended Stepwise Dimension Reduction (XSDR) is proposed. The XSDR improves the SDR by decomposing the original truth table of a layer to two truth tables. The new truth tables after decomposing are easy to be evolved. The XSDR extensively improves the performance of the SDR in terms of the number of fitness evaluations and the computational time. And larger circuits could be evolved by the XSDR.(2) Based on the Bi-Decomposition approach, methods for designing polymorphic logic circuits is proposed. In the Bi-Decomposition method, a traditional digital logic gate (AND, OR or XOR) is adopted to decompose the original truth table to two new truth tables which are easier to be implemented. Through repeating the decomposing operation, a combinational logic circuit is obtained from the top to the bottom. Based on the Bi-Decomposition approach, the Poly-Bi-Decompositon method is proposed for designing polymorphic circuits. In the Poly-Bi-Decompositon method, a polymorphic gate is adopted to decompose the original polymorphic truth table to two simpler polymorphic truth tables. Through repeating the Poly-Bi-Decompositon, a polymorphic circuit is obtained. In addition, a polymorphic circuit designing method based on the Bi-Decomposition method and logic gates transformation rules is proposed.(3) The completeness of the polymorphic logic gate set is discussed. Firstly, the impact of the Logic-0 and Logic-1 for the completeness of a polymorphic gate set is studied. The definition of the weak and strong complete polymorphic gate set is given. Secondly, two determine algorithms are proposed to judge the completeness of a polymorphic gate set with two modes. Finally, the theory and algorithm for polymorphic gate sets with more than two modes are given.(4) A straightforward method is proposed to judge the completeness of a polymorphic gate set. If several crucial circuits can be built by the straightforward method, the polymorphic gate set is complete. Otherwise, it is not complete. The proposed method is easy to understand, and it is suitable for manually judging the completeness of polymorphic gate sets with two or three modes.This dissertation focuses on the scaling problem in the evolutionary design of combinational logic circuits, the theory and design methods of the polymorphic circuit. In one hand, effective methods for evolving relatively large combinational logic circuits are proposed. In the other hand, firstly, the method for designing relatively large scale polymorphic logic circuits is proposed. Secondly, algorithms for judging the completeness of polymorphic gate set are given.