Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2014, Vol. 15 Issue (12): 1174-1182    DOI: 10.1631/jzus.C1400093
    
或-符合代数系统中的对称变量检测算法
Xiao-hua Li, Ji-zhong Shen
Campus Information Center, Zhejiang University, Hangzhou 310027, China; Department of Information Science & Electronic Engineering, Zhejiang University, Hangzhou 310027, China
An algorithm for identifying symmetric variables in the canonical OR-coincidence algebra system
Xiao-hua Li, Ji-zhong Shen
Campus Information Center, Zhejiang University, Hangzhou 310027, China; Department of Information Science & Electronic Engineering, Zhejiang University, Hangzhou 310027, China
 全文: PDF 
摘要： 逻辑变量对称性在逻辑综合、OBDD化简、故障检测、电路分析及密码学函数构造等领域具有广泛的应用。为简化或-符合代数系统中12类对称变量的检测过程，提出一种新的检测算法。提出新的基于或-符合展开系数对称性检测算法。该算法可实现12类对称变量的完备性检测，同样适用于与-或-非代数系统和与-异或代数系统。首先，分析基于或-符合展开布尔函数的子函数系数矩阵和有序子系数矩阵之间的关系（公式5），提出基于有序子系数矩阵的12类对称形式的约束条件（表3）。根据该约束条件，通过判别图的有序特征格值，提出逻辑变量12类对称形式的快速检测算法（图4）。与其他方法相比（表7），该方法有效避免或-符合展开系数和与-异或展开系数及与-或-非展开系数之间的转换，同时解决了图方法中的完备性问题。算法用C语言实现并用MCNC91 benchmarks（表6）进行测试。提出或-符合代数系统中12类对称变量的检测算法。与其他方法相比，该算法在适用的检测变量数、检测类型、检测过程的复杂度方面最优。
关键词： 对称变量;  图;  或-符合代数系统;  布尔函数    
Abstract: To simplify the process for identifying 12 types of symmetric variables in the canonical OR-coincidence (COC) algebra system, we propose a new symmetry detection algorithm based on OR-NXOR expansion. By analyzing the relationships between the coefficient matrices of sub-functions and the order coefficient subset matrices based on OR-NXOR expansion around two arbitrary logical variables, the constraint conditions of the order coefficient subset matrices are revealed for 12 types of symmetric variables. Based on the proposed constraints, the algorithm is realized by judging the order characteristic square value matrices. The proposed method avoids the transformation process from OR-NXOR expansion to AND-OR-NOT expansion, or to AND-XOR expansion, and solves the problem of completeness in the dj-map method. The application results show that, compared with traditional methods, the new algorithm is an optimal detection method in terms of applicability of the number of logical variables, detection type, and complexity of the identification process. The algorithm has been implemented in C language and tested on MCNC91 benchmarks. Experimental results show that the proposed algorithm is convenient and efficient.
Key words: Symmetric variable    dj-map    Canonical OR-coincidence algebra system    Boolean function
收稿日期: 2014-03-16 出版日期: 2014-12-05
CLC:  TN431  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Xiao-hua Li
Ji-zhong Shen

引用本文:

Xiao-hua Li, Ji-zhong Shen. An algorithm for identifying symmetric variables in the canonical OR-coincidence algebra system. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1174-1182.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C1400093    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2014/V15/I12/1174

[1] Hamid Reza Boveiri. 基于渐进式蚁群优化的多处理器任务分配[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 498-510.
[2] Jian-ru Xue, Di Wang, Shao-yi Du, Di-xiao Cui, Yong Huang, Nan-ning Zheng. 无人车自主定位和障碍物感知的视觉主导多传感器融合方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 122-138.
[3] Shahab Pourtalebi, Imre Horváth. 用于定义系统表现特征的基因型与表型仓库数据库的信息图式构造方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(9): 862-884.
[4] Jia-yin Song, Wen-long Song, Jian-ping Huang, Liang-kuan Zhu. 基于边界分析的森林冠层半球图像中心点定位与分割[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(8): 741-749.
[5] Reza Sookhtsaraei, Javad Artin, Ali Ghorbani, Ahmad Faraahi, Hadi Adineh. 基于位置的数据云复制管理器[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(12): 1275-1286.
[6] Aftab Ahmed Chandio, Nikos Tziritas, Fan Zhang, Ling Yin, Cheng-Zhong Xu. 基于云计算的自适应可调节GPS轨迹地图匹配策略[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(12): 1305-1319.
[7] Jing-li Gao, Cheng-lin Wen, Zhe-jing Bao, Mei-qin Liu. 基于时域滤波和关联策略的红外慢速目标检测[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(11): 1176-1185.
[8] De-xuan Zou, Gai-ge Wang, Gai Pan, Hong-wei Qi. 基于修正模拟退火算法及溢出面积模型的固定边界布图规划[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(11): 1228-1244.
[9] Yong Ding, Nan Li, Yang Zhao, Kai Huang. 基于核空间非线性特征提取的图像质量评价方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(10): 1008-1017.
[10] Yong-xing Liu, Ken-li Li, Zhuo Tang, Ke-qin Li. 面向异构系统的节能调度算法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(7): 519-531.
[11] Qian-shan Li, Rong Xiong, Shoudong Huang, Yi-ming Huang. 一种利用半稠密点云及RGB图像构建稠密表面模型地图的方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(7): 594-606.
[12] Zhi-min Han, Zhi-yun Lin, Min-yue Fu, Zhi-yong Chen. 图拉普拉斯视角下的多智能体系统分布式协调控制[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(6): 429-448.
[13] Xun Liu, Yin Zhang, San-yuan Zhang, Ying Wang, Zhong-yan Liang, Xiu-zi Ye. 基于高清监控图像的工程车辆检测算法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(5): 346-357.
[14] Yang Chen, Zheng Qin. 基于梯度的压缩感知图像融合[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(3): 227-237.
[15] László Lengyel, Hassan Charaf. 测试驱动的模式转换检验/认证[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 85-97.