Реализация 8-битного сумматора на Python

Я реализовал 8-битный сумматор на Python следующим образом:

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))

Для меня поразительно то, что "ворота" будут оценивать лениво, поэтому они не вернут 1/0, пока я не позвоню int(), и кажется, что в 8-битном сумматоре огромное количество вентилей. Например:

Допускаю ли я где-то ошибку (или избыточность) в оценке переноса / значения, или у базового 8-битного сумматора пульсаций действительно есть такое количество ворот??

Источник

2 ответа

Решение

В реальном сумматоре вентили соединены в граф, где выход логического элемента может использоваться как вход для нескольких других.

Вы пишете вывод как выражение, в котором вывод ворот можно использовать только в одном месте.

Это достигается путем копирования всего выражения для каждого вывода во все места, где оно используется. Вы делаете это на каждой итерации -carry_in используется один раз для получения значения и 3 раза для получения следующего переноса.

Размер выражения переноса умножается на 3 на каждой итерации, что приводит к экспоненциальному росту числа используемых вами операторов.

Вероятно, вы должны генерировать свой вывод в другой форме, которая может сохранить граф гейта, например статическое одиночное назначение: https://en.wikipedia.org/wiki/Static_single_assignment_form

Источник

Если реализован напрямую, полный сумматор имеет столько ворот. Рассматривали ли вы использование составных вентилей, таких как 8-битные примитивы или полусумматор? У меня нет прямого опыта, но я не думаю, что на практике полные сумматоры реализуются напрямую с примитивами, вместо этого они, вероятно, используют эти промежуточные части.

Во второй главе 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. Я все же рекомендую поместить это в отдельный вентиль, поскольку полусумматор полезен независимо.

Источник
Другие вопросы по тегам