21 NAND 文档 EN

有证明的下界

3 位加法的进位最少要 6 层 NAND:5 层做不出,6 层有现成电路。

结论

项值
函数A、B 是 3 位无符号数,c 是 1 位进位输入,输出 [A + B + c ≥ 8]
输入7 位,共 128 种
门两输入 NAND,个数不限,可以共用,可以接常数 0 / 1
下界深度 5 做不出
上界有一个深度 6 的电路,22 个门

只说这一个进位函数。不说完整加法器或乘法器的最小深度。

为什么 5 层做不出

  1. 列出深度 ≤ d 能做出的全部函数,记作 F_d。F_0 是 7 个输入;每加一层,把上一层任意两个函数 NAND 一下加进去。这样不漏任何电路,不管门数和共用。
  2. 实际个数:F_0 = 7,F_1 = 35,F_2 = 540,F_3 = 84,156。
  3. 深度 5 的输出 = NAND(两个 F_4 函数),每个 F_4 函数要么已在 F_3,要么是两个 F_3 函数的 NAND。
  4. 输出为 0 的那些输入上,两个操作数都必须是 1。按这个条件筛,合法的 F_3 操作数对有 1,052,195 对,得到 21,787 种不同的乘积,其中 262 种是极大的。
  5. 没有任何两个极大乘积能凑出目标函数;更浅的深度也做不出。所以深度 5 不可能。
  6. 常数没用:NAND(0, x) 恒为 1,NAND(1, x) 等于 NAND(x, x),都不会让剩下的电路更浅。

两套独立程序核过

深度 6 的电路