English

应用科学学报 ›› 1996, Vol. 14 ›› Issue (1): 35-40.

• 论文 • 上一篇    下一篇

判定平方布尔函数的计数算法

丁左流   

  1. 上海师范大学
  • 收稿日期:1994-03-19 修回日期:1994-09-03 出版日期:1996-03-31 发布日期:1996-03-31
  • 作者简介:丁左流:副教授,上海师范大学计算机科学系,上海 200234
  • 基金资助:
    上海师范大学校科研基金资助项目

AN ALGORITHM FOR DECIDING QUADRATIC BOOLEAN FUNCTIONS BY COUNTING

DING ZUOLIU   

  1. Shanghai Teachers University
  • Received:1994-03-19 Revised:1994-09-03 Online:1996-03-31 Published:1996-03-31

PDF

74

摘要： 一个n元函数是否为平方布尔函数?如果是,如何得到其所有的平方项?文中就此判定问题提出了一个时间复杂度为O(mn3)的计数算法.与经典的Q-M算法不同,该算法基于直观的真值计数,并适合于并行实现.

关键词: 判定, 质蕴含, 平方布尔函数, Q-M算法, 极小项

Abstract: An algorithm is proposed to decide whether a function of n variables is a quadratic Boolean function.If so, how can we obtain the quadratic terms? Different from the Quine-McOluskey method, our algorithm is based on the counting of values 0, and allows a high 1evel of parallelism.

Key words: quadratic Boolean functions, decision, Q-M Algorithm, prime implicant, miniterm