# [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展开式算法() 分享到： var jiathis_config = { data_track_clickback: true };

40

2010年第5期

932-936

2010-09-20

## 文章信息/Info

Title:
Reed-Muller expansion algorithm based on Ring-Sum-Expansion

1 东南大学计算机科学与工程学院,南京 210096; 2 河南大学计算中心,开封 475000
Author(s):
1 School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 Computer Center, Henan University, Kaifeng 475000, China

Keywords:

TP387;TN911.73
DOI:
10.3969/j.issn.1001-0505.2010.05.010

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]