组合电路综合的逻辑编程框架

# 组合电路综合的逻辑编程框架 ## 1. 位串真值表的逻辑编程实现在组合电路综合中，位串真值表的表示和操作是基础。以下是一些关键的逻辑编程代码实现： ```prolog % Maps variable K in 0..Mask-1 to truth table % Xk packed as a bitstring-integer. var_to_bitstring_int(NbOfBits,K,Xk):- all_ones_mask(NbOfBits,Mask), NK is NbOfBits-(K+1), D is (1<<(1<<NK))+1, Xk is Mask//D. % Mask is a bitstring-integer ending with NbOfBits of the form % 11...1. It also provides an encoding of constant function 1. all_ones_mask(NbOfBits,Mask):-Mask is (1<<(1<<NbOfBits))-1. bitand(X1,X2,X3):-X3 is ’/\’(X1,X2). bitor(X1,X2,X3):-X3 is ’\/’(X1,X2). bitxor(X1,X2,X3):-X3 is ’#’(X1,X2). bitless(X1,X2,X3):-X3 is ’#’(X1,’\/’(X1,X2)). bitgt(X1,X2,X3):-X3 is ’#’(X1,’/\’(X1,X2)). bitnot(NbOfBits,X1,X3):-all_ones_mask(NbOfBits,M),X3 is ’#’(X1,M). biteq(NbOfBits,X,Y,Z):-all_ones_mask(NbOfBits,M),Z is ’#’(M,’#’(X,Y)). bitimpl(NbOfBits,X1,X2,X3):-bitnot(NbOfBits,X1,NX1),bitor(NX1,X2,X3). bitnand(NbOfBits,X1,X2,X3):-bitand(X1,X2,NX3),bitnot(NbOfBits,NX3,X3). bitnor(NbOfBits,X1,X2,X3):-bitor(X1,X2,NX3),bitnot(NbOfBits,NX3,X3). ``` 这些代码实现了变量到比特串整数的映射，以及常见的位运算操作。位串真值表的长度对于大多数涉及穷举搜索的完美综合问题是足够的，但对于超过6个变量（对应64位）的问题，可能会变得难以处理。不过，使用大多数Prolog可用的任意长度整数包可以进一步扩展该机制。在实践中，可以使用超时机制来决定是否需要退回到启发式综合方法。 ## 2. 通用布尔函数库的比较 ### 2.1 通用布尔函数库的定义如果任何布尔函数都可以写成集合F中函数的组合，则称布尔函数集合F是通用的。一个著名的通用集合是（合取，否定），即（∗, ∼），这可以通过将真值表用合取、析取和否定表示，然后使用德摩根定律消除析取来直接得出。通常通过用库中的操作表示合取和否定来证明一个库的通用性。 ### 2.2 不同库的比较以下是一些用于综合的库在表达所有16个双参数布尔操作所需的总门数方面的比较： | Library | total for 16 operators | non - redundant | | ---- | ---- | ---- | | nand | 46 | yes | | nor | 46 | yes | | nand, 1 | 33 | no | | nor, 0 | 33 | no | | ∗, nand | 32 | no | | <, nor | 31 | no | | ⇒, 0 | 28 | yes | | <, 1 | 28 | yes | | ∗, <, 1 | 26 | no | | ∗, ⊕, 1 | 25 | yes | | <, nand, 1 | 25 | no | | <, nor, 1 | 24 | no | | ∗, =, 0 | 23 | yes | | ⇒, =, 0 | 21 | no | | <, =, 1 | 21 | no | 从这个比较中可以看出，通过包含像“⊕”和“=”这样需要相对较多其他门（或高晶体管数）来表达的操作，可以最小化所需的操作符数量（和电路尺寸）。令人惊讶的是，(⇒, 0)及其对偶(<, 1)比与非门和或非门表现得更好，它们仅用28个门就能表达所有16个操作符。 ## 3. 使用严格布尔不等式进行组合电路综合 ### 3.1 严格布尔不等式的基本情况严格布尔不等式A < B与常量1组成的布尔函数对是通用的，但它被逻辑学家和电路设计师所忽视，相关文献中对它的引用很少。而它的对偶(⇒, 0)是一个众所周知的通用函数对，已被广泛研究作为经典和直觉命题逻辑的公理基础。 ### 3.2 严格布尔不等式的作用 - **对异或函数的贡献**：A⊕B可以表示为(A < B) + (B < A)，因此A < B可以提供A⊕B的一半。 - **类似合取和推理规则**：它等价于∼A ∗B，提供了一种合取形式（第一个参数取反）。同时，它也可以作为一种推理规则，从其真值可以唯一确定其两个参数的真值。 ### 3.3 严格布尔不等式作为通用布尔运算符严格布尔不等式由以下真值表定义： | A | B | A < B | |