Reed-Muller逻辑函数极性优化技术研究

摘要

逻辑函数的表示既可以采用“AND/OR/NOT”形式的传统布尔（Tranditional Boolean，TB）逻辑，也可以采用“AND/XOR”形式的Reed-Muller（RM）逻辑。RM逻辑函数根据变量表示形式的不同分为固定极性表达式（FPRM）和混合极性表达式（MPRM）。由于RM逻辑函数表示形式的复杂程度与极性紧密相关，因此极性优化技术是 RM逻辑综合与优化中重要的组成部分。考虑到目前逻辑函数表达式采用传统的布尔逻辑为主，因此完整的RM逻辑函数的极性优化应该包括逻辑转换和极性搜索二部分。其中逻辑转化用来实现传统布尔逻辑向RM逻辑的转化；而极性搜索用来找到合适的变量极性，使得RM逻辑的面积或者功耗等方面实现优化。本论文主要对逻辑转换和极性搜索二部分进行了讨论。具体内容包括：
　　1)逻辑转换算法。具体包括乘积项之间的不相交锐积，乘积项的位极性运算，位相交运算和位互斥运算。其中不相交锐积运算用来将TB逻辑转换为不相交乘积项的SOP形式；然后利用其他几个乘积项运算，将由不相交项构成的SOP形式的TB逻辑直接转化到指定极性下的FPRM的表示形式。实验结果表明相应的转化算法在处理输入变量个数较大的电路时运算速度更快，并且算法对待处理电路的极性不敏感。
　　2)极性搜索方法。具体包括提出的乘积项互斥运算方法实现Boolean逻辑函数到RM逻辑函数的转换；同时利用遗传算法以及FPRM的极性之间的转化算法，实现FPRM的极性搜索。实验结果表明，由于提出乘积项互斥运算实现大电路的TB逻辑项FPRM的转化，改进的列表技术也可以实现大电路的FPRM的极性间转化，结合遗传算法的全局搜索能力，可以实现大电路的RM逻辑的极性搜索。

目录

声明

引言

1绪论

1.1课题研究背景与意义

1.2国内外研究现状

1.3研究内容安排

2与RM逻辑相关的概念

2.1基本定义与相关概念

2.2 XOR/AND函数的极性与展开式

2.3异或与同或运算的定义与性质

2.4逻辑函数的RM形式的展开

2.5 Boolean逻辑展开式与RM逻辑展开式之间的转化

2.6本章小结

3乘积项的运算方法在FPRM转换中的应用

3.1乘积项之间的操作

3.2不相交乘积项的生成过程

3.3列表技术实现FPRM的极性转换

3.4乘积项互斥运算的FPRM转换

3.5算法测试结果和比较

3.6本章小结

4 RM逻辑函数的最佳极性搜索

4.1 RM函数的极性搜索理论基础

4.2基于穷举法的RM逻辑函数极性搜索

4.3遗传算法在RM逻辑函数极性搜索中的应用

4.4算法及实验结果分析

4.5本章小结

5结论与展望

参考文献

在学研究成果

致谢