[1]朱皖宁,陈汉武,刘志昊,等.基于Ring-Sum-Expansion范式的Reed-Muller展开式算法[J].东南大学学报(自然科学版),2010,40(5):932-936.[doi:10.3969/j.issn.1001-0505.2010.05.010]
 Zhu Wanning,Chen Hanwu,Liu Zhihao,et al.Reed-Muller expansion algorithm based on Ring-Sum-Expansion[J].Journal of Southeast University (Natural Science Edition),2010,40(5):932-936.[doi:10.3969/j.issn.1001-0505.2010.05.010]
点击复制

基于Ring-Sum-Expansion范式的Reed-Muller展开式算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
40
期数:
2010年第5期
页码:
932-936
栏目:
计算机科学与工程
出版日期:
2010-09-20

文章信息/Info

Title:
Reed-Muller expansion algorithm based on Ring-Sum-Expansion
作者:
朱皖宁1 陈汉武1 刘志昊1 王冬12
1 东南大学计算机科学与工程学院,南京 210096; 2 河南大学计算中心,开封 475000
Author(s):
Zhu Wanning1 Chen Hanwu1 Liu Zhihao1 Wang Dong12
1 School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 Computer Center, Henan University, Kaifeng 475000, China
关键词:
Ring-Sum-Expansion范式 Reed-Muller展开式 GRM递归算法 GRM矩阵算法
Keywords:
Ring-Sum-Expansion Reed-Muller expansion GRM(generalized Reed-Muller expressions)recursion algorithm GRM(generalized Reed-Muller expressions)matrix algorithm
分类号:
TP387;TN911.73
DOI:
10.3969/j.issn.1001-0505.2010.05.010
摘要:
为了改善生成Reed-Muller展开式的灵活性,提出了基于RSE范式的Reed-Muller展开式算法.根据将析取主范式转化为Ring-Sum-Expansion范式的过程,先使用真值表输入项构造预处理表,再从真值表中抽取使输出项为真的二进制码,通过预处理表直接解出每一个输出项的Reed-Muller展开式.对算法进行复杂度分析比较表明,与通常所用的GRM递归算法和GRM矩阵相乘Reed-Muller展开式算法相比,该算法在生成展开式时具有更好的灵活性,可以单独生成指定输出项的Reed-Muller展开式,不同于常用算法必须要一次生成全部输出项的Reed-Muller展开式.
Abstract:
In order to improve the agility of the Reed-Muller expansion algorithm, Reed-Muller expansion algorithm based on Ring-Sum-Expansion is presented. According to the process of transforming Disjunctive-Normal-Form into Ring-Sum-Expansion, the input of the true table is used to build pretreatment table firstly. Secondly, binary code is extracted from the input which makes the output true of the true table. Finally, Reed-Muller expansion can be solved respectively according to the binary code and the pretreatment. The complexity of the algorithm is analyzed and compared with other algorithms. The results show that compared with current GRM(generalized Reed-Muller expressions)recursion algorithm and GRM matrix algorithms, the proposed algorithm has more agility. It can create appointed output variable’s Reed-Muller expansion separately which current algorithms can not do.

参考文献/References:

[1] Bennett C.Logical reversibility of computation[J].IBM J Res Dev,1973,17(6):525-532.
[2] Maslov D,Dueck G W,Miller D M.Toffoli network synthesis with templates[J].IEEE Trans CADICS,2005,24(6):807-817.
[3] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic synthesis[C] //Proceedings of Design Automation Conference. Anaheim,CA,USA,2003:318-323.
[4] 王冬,陈汉武,安博,等.量子可逆电路综合的启发式快速匹配算法[J].东南大学学报:自然科学版,2009,39(5):900-903.
  Wang Dong,Chen Hanwu,An Bo,et al,A heuristic fast-matching algorithm for synthesis of quantum reversible logic circuits[J].Journal of Southeast University:Natural Science Edition,2009,39(5):900-903.(in Chinese)
[5] Paterson K G.Generalized Reed-Muller codes and power control in OFDM modulation[J].IEEE Transactions on Information Theory,2000,46(11):104-120.
[6] Sasao T.Easily testable realizations for generalized Reed-Muller expressions [J].IEEE Transactions on Computers,1997,46(6):709-716.
[7] Tsai C C,Marek-Sadowska M.Generalized Reed-Muller forms as a tool to detect symmetries[J],IEEE Transactions on Computers,1996,45(11):33-40.
[8] Paterson K G,Jones A E.Efficient decoding algorithms for generalized Reed-Muller codes[J].IEEE Transactions on Communications,2000,48(88):1272-1285.
[9] Yang G,Song X,Perkowski M A,et al.Four-level realization of 3-qubit reversible function[J].IET Comput Digit Tech,2007,1(4):382-388.
[10] 李志强,李文骞,陈汉武.量子可逆逻辑综合的关键技术及其算法[J].软件学报,2009,20(9):2332-2343.
  Li Zhiqiang,Li Wenqian,Chen Hanwu.Algorithm of optimizing quantum reversible logic synthesis [J].Journal of Software,2009,20(9):2332-2343.(in Chinese)
[11] 肖芳英,陈汉武,陈开忠,等.可逆电路错误检测方法的研究[J].通信学报,2007,28(8A):71-79.
  Xiao Fangying,Chen Hanwu,Chen Kaizhong,et al.Fault detection in reversible circuit[J].Journal on Communications,2007,28(8A):71-79.(in Chinese)
[12] Savage J E.Models of computation[M].Boston,MA,USA:Addison-Wesley Longman Publishing Co.,Inc.,2007.
[13] 李志强,陈汉武,徐宝文,等.量子可逆逻辑电路综合的快速算法研究[J].计算机学报,2009,32(7):1291-1303.
  Li Zhiqiang,Chen Hanwu,Xu Baowen,et al.A fast algorithm for synthesis of quantum reversible logic circuits [J].Chinese Journal of Computers,2009,32(7):1291-1303.(in Chinese)

相似文献/References:

[1]王冬,陈汉武,安博,等.量子可逆电路综合的启发式快速匹配算法[J].东南大学学报(自然科学版),2009,39(5):900.[doi:10.3969/j.issn.1001-0505.2009.05.006]
 Wang Dong,Chen Hanwu,An Bo,et al.Heuristic fast-matching algorithm for synthesis of quantum reversible logic circuits[J].Journal of Southeast University (Natural Science Edition),2009,39(5):900.[doi:10.3969/j.issn.1001-0505.2009.05.006]

备注/Memo

备注/Memo:
作者简介: 朱皖宁(1983—),男,博士生; 陈汉武(联系人),男,博士,教授,博士生导师,hw-chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60873101)、江苏省自然科学基金资助项目(BK2007104,BK2008209).
引文格式: 朱皖宁,陈汉武,刘志昊,等.基于Ring-Sum-Expansion范式的Reed-Muller展开式算法[J].东南大学学报:自然科学版,2010,40(5):932-936. [doi:10.3969/j.issn.1001-0505.2010.05.010]
更新日期/Last Update: 2010-09-20