Delay Optimization Of Reed-muller Logic Circuits

Circuit optimization can be dividided into power optimization, area optimization and delayoptimization, and it is the important part in CAD (Computer aided design) tool of integratedcircuits design. The previous circuit optimization is based on Boolean logic, and the correspondingautomated design technique is set up. In fact, compared with the traditional Boolean circuits, someReed-Muller circuits have more advantages in power, speed and area, e.g. computing circuits,parity check circuits, and communication circuits. Polarity is the important factor of RM expansion,and determines the complexity of expansion. Moreover, it will affect the delay, area and power inthe corresponding circuits. Therefore, RM circuit optimization is to search the best polarity ofwhich the circuit has the optimal performance in the polarity space.Fixed polarity Reed-Muller (FPRM) and mixed polarity Reed-Muller (MPRM) are twocommon expansions in RM logic. At present, most of the RM circuit optimization is for power andarea, while there is less research on delay optimization. Compared with MPRM expansion, theforms of variables in FPRM expansion are more restricted, and the polarity space is smaller.Therefore, the delay optimization on FPRM circuit is established firstly and then the optimizationscheme of FPRM circuit is extended for MPRM circuit in this thesis. The main contents aredivided into five parts, and they are as follows.1. Delay optimization for FPRM circuits: According FPRM expansion, a delay evaluation modelis set up by combining algebraic method with Huffman_like algorithm. On this basis, polarityconversion algorithm and exhaustive method are used to searchi the optimal polarity formedium-scale FPRM circuits.2. Delay and area optimization for FPRM circuits based on PSO algorithm: Based on FPRMexpansion characteristics, delay and area evaluation model is proposed. To get the delay andarea value by delay decomposition, the fitness function is designed. Then the correspondingrelation between fixed polarity and the particle is built so that the PSO algorithm is applied onthe optimal polarity of delay-are trade-off for large-scale FPRM circuits.3. Delay and area optimization for FPRM circuits based on FDDs (Functional decision diagrams):In FDDs, the logical decomposition is achieved by terminal vertices so as to get the delay andarea. Then combining searching method of variable order and tabular technique, the delay andarea optimization algorithm of medium-scale and large-scale circuits is presented.4. Conversion algorithm of MPRM expansion based on OKFDDs (Ordered kronecker functionaldecision diagrams): By studying OKFDDs and MPRM expansion, the relation of them is established. According to the operation of terminal vertices of Boolean expansion and MPRMexpansion, the terminal vertices operation is derived to realize the conversion between differentmixed polarities.5. Dealy-area trade-off on MPRM circuits based on hybrid discrete PSO (HDPSO) algorithm: Byintroducing the mutation and elitist strategy into the PSO algorithm, HDPSO is proposed.Based on this, a delay-area trade-off of MPRM circuits is presented with delay evaluationmodel.The proposed algorithms in this thesis are implemented in C++, which are tested with MCNCBenchmarks. Compared with other algorithms, the RM circuits optimized by the proposedalgorithms have superior performance on delay and area.