基于Ring-Sum-Expansion范式的Reed-Muller展开式算法

摘要：

为了改善生成Reed-Muller展开式的灵活性,提出了基于RSE范式的Reed-Muller展开式算法.根据将析取主范式转化为Ring-Sum-Expansion范式的过程,先使用真值表输入项构造预处理表,再从真值表中抽取使输出项为真的二进制码,通过预处理表直接解出每一个输出项的Reed-Muller展开式.对算法进行复杂度分析比较表明,与通常所用的GRM递归算法和GRM矩阵相乘Reed-Muller展开式算法相比,该算法在生成展开式时具有更好的灵活性,可以单独生成指定输出项的Reed-Muller展开式,不同于常用算法必须要一次生成全部输出项的Reed-Muller展开式.

关键词：Ring-Sum-Expansion范式、Reed-Muller展开式、GRM递归算法、GRM矩阵算法

所属期刊栏目：40

分类号：TP387;TN911.73(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目60873101;江苏省自然科学基金资助项目BK2007104,BK2008209

在线出版日期：2010-12-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：932-936