在python中实现8位加法器

Question

我已经在python中实现了8位加法器，如下所示：

from gates import AND, OR, XOR
from utils import number_to_binary, binary_to_number

def EightBitAdder(s1='110101', s2='00010', carry_in=0):
    # Limit to 8 bits
    s1 = s1[-8:].zfill(8)
    s2 = s2[-8:].zfill(8)
    s_out = ''
    carry_out = None
    for i in range(8):
        bit_1 = int(s1[8-1-i])
        bit_2 = int(s2[8-1-i])
        carry_in = carry_out if (carry_out is not None) else carry_in
        value_out = XOR(carry_in, XOR(bit_1, bit_2))
        carry_out = OR(AND(bit_1, bit_2), AND(bit_1, carry_in), AND(bit_2, carry_in))
        s_out = str(int(value_out)) + s_out
    print ("  %s (%s) \n+ %s (%s) \n= %s (%s)  -- Carry %s" % (s1, binary_to_number(s1), s2, binary_to_number(s2), s_out, binary_to_number(s_out), int(carry_in)))
    return (s_out, int(carry_out))

对我来说，最引人注目的是“门”的求值是延迟的，因此除非我调用int()，否则它不会返回1/0，而且8位加法器中似乎有大量的门。例如：

我是在进位/值输出评估中的某个地方犯了错误（还是冗余），还是基本的8位纹波加法器确实包含这么多的门？

Answer 1

如果直接实现，一个完整的加法器中确实有那么多门。您是否考虑过使用复合门（例如8位基元）或使用half adder？我没有直接的经验，但是我不认为完整的加法器实际上是直接用原语实现的，相反，他们可能使用了这些中间部分。

nand2tetris的第二章介绍了半加法器方法，如果您将其应用到代码中，则可以略作简化：

        carry_in = carry_out if (carry_out is not None) else carry_in
        value_out = XOR(carry_in, XOR(bit_1, bit_2))
        carry_out = OR(AND(bit_1, bit_2), AND(bit_1, carry_in), AND(bit_2, carry_in))

可以改写为：

        carry_in = carry_out if (carry_out is not None) else carry_in
        half_sum = XOR(bit_1, bit_2)
        half_carry = AND(bit_1, bit_2)
        full_sum = XOR(carry_in, half_sum)
        full_carry = AND(half_sum, carry_in)
        value_out = full_sum
        carry_out = OR(half_carry, full_carry)

这会将每次迭代的门数从6减少到5，因此应将输出减少1/6。我仍然建议将其放在单独的门中，因为半加器是独立有用的。

Answer 2

在真正的加法器中，门连接成一个图，其中门的输出可用作其他几个输入的输入。

您正在将输出写为表达式，其中门的输出只能在一个地方使用。

这是通过将每个输出的整个表达式复制到使用它的所有位置来完成的。您可以在每次迭代中执行此操作-carry_in一次用于产生值，而3次用于产生下一个进位。

进位表达式的大小在每次迭代中均乘以3，导致使用的运算符数量呈指数级增长。