Полный многоразрядный двоичный сумматор.

Привет всем!
Прошло около двух месяцев, после того, как я напечатал предыдущую статью, ну ничего, продолжим...
Но в начале договоримся, т.к мы будем работать со системами счисления, то после чисел в двоичной системе я буду ставить букву «b», а после десятичных «d».
В прошлой статье мы рассмотрели работу двоичного полусумматора, думаю самое время рассмотреть работу полного одноразрядного сумматора!

Тоесть он будет считать числа только в пределах одного двоичного разряда:

1+1=10
1+0=1
0+1=1
0+0=0

Но тут вы можете возмутиться, и сказать,- «Ведь мы это рассматривали в предыдущей статье!»
Да, действительно рассматривали. Так вот, идея состоит в следующем, нужно придумать два одноразрядных сумматора, которые при обьединение определенным образом, давали двуразрядный сумматор, а при объединение трех таких сумматоров, давали трехразрядный.
Надеюсь все понимают что такое разрядность?

Например число 777d:

777=7*10^2+7*10^1+7*10^0
3разрядно.

Вот тоже самое число в двоичной:
1100001001b

1100001001b=1*2^9+1*2^8+0*2^7+0*2^6+0*2^7+0*2^6+1*2^5+0*2^4+0*2^3+1*2^2+1*2^1+1*2^0=
=1*2^9+1*2^8+0+0+0+0+1*2^5+0+1*2^2+1*2^1+1*2^0=512+256+8+1=777d

Число 9разрядно, тоесть получаем, Число 777d 3разрядно, а в двоичной системе 9разрядно 3*2=9 (2 — основание системы счисления)
Тоесть чтобы складывать числа в пределах десяти(10d), нам нужен четырехразрядный сумматор (число 10d 2разрядно, значит 2*2=4), что значит в пределах десяти? Значит, что сумма A+B не должна превышать число 10d, или число 1010b.

В прошлый раз мы рассмотрели такую ситуацию, для сумматора и нам удалось составить соответствующие формулы.
A_+_B___=____P_S
0_+_0___=____0_0
0_+_1___=____0_1
1_+_0___=____0_1
1_+_1___=____1_0

Рассмотрим такой случай:
10b+1b=11b
как мы это посчитали? сложили младший разряд первого числа + второе число (там 1разряд)
10b
01b
11b

Тут все просто, а теперь давайте возьмем такой случай
11b+1b=100b

011b
001b
100b

Суммируем, так берем младший разряд первого числа(1b), плюс второе число(1b) 1b+1b=10b, ноль пишем, один в уме, поднимаемся на разряд, 1b+0b=1
Получаем 1b, но у нас еще 1b в уме, 1+1=10, снова ноль пишем, один в уме, дальше разряды кончаются поэтому записываем единицу, в итоге получается:100b.

Отсюда напрашивается один простой вывод, в наши старые формулы нужно добавить еще одну переменную, которая будет хранить перенос из младшего разряда в старший (то, что мы храним в уме), причем значение этого переноса может быть либо 0b либо 1b, назовем эту переменную p0, кто не помнит, что просто P — старший разряд.

Нам нужно найти формулу при которой, будут выполняться следующее условие:

A__+_B_____p0_____P______S
0__+_0_____1______0______1
0__+_1_____1______1______0
1__+_0_____1______1______0
1__+_1_____1______1______1


Заметьте, здесь перенос всегда активен (всегда равен 1b), например складываем 1b+0b, где — то в середине числа, и перенос из младшего разряда равен 1b(в предыдущем разряде скорее всего было суммирование 1b+1b или тоже был перенос из другого, более младшего разряда)
Получается 1b+0b=1b да плюс перенос из младшего разряда 1b+1b=10b.

1__+_0_____1______1______0

Ну, что ж все вроде работает осталось найти формулу, благо все формулы уже найденны, и мы не будем заниматься нудной работой.

P=(A*B)+(A*p0)+(B*p0)

A____B_____p0____A*B_____A*p0___B*p0___(A*B)+(A*p0)_______P
0____0_____0______0________0______0__________0___________0
0____1_____0______0________0______0__________0___________0
1____0_____0______0________0______0__________0___________0
1____1_____0______1________0______0__________1___________1

___________________При_ p0=1_______________________________

0____0_____1______0________0______0__________0___________0
0____1_____1______0________0______1__________0___________1
1____0_____1______0________1______0__________1___________1
1____1_____1______1________1______1__________1___________1


S=(A+B+p0)*noP+(A*B*p0)

A____B_____p0_____P_____A+B_____A+B+p0______noP___(A+B+p0)*noP_____A*B*p0_____S
0____0_____0______0______0________0____________1__________0____________0________0
0____1_____0______0______1________1____________1__________1____________0________1
1____0_____0______0______1________1____________1__________1____________0________1
1____1_____0______1______1________1____________0__________0____________0________0

___________________________________При_ p0=1______________________________________

0____0_____1______0______0________1____________1__________1____________0________1
0____1_____1______1______1________1____________0__________0____________0________0
1____0_____1______1______1________1____________0__________0____________0________0
1____1_____1______1______1________1____________0__________0____________1________1

Еще тут есть одно условие P, должно быть вычисленно раньше чем S, так как noP (отрицание P учавствует во второй формуле), Думаю вам будет интересно взглянуть на логическую схему, логические элементы там изображены немного иначе, но там все обьяснено.

smages.com/78/39/7839c60ef43271190ad4cdc0a8560d32.jpg.htm
Вот в более хорошем качестве:
imhost.ru/show.php/17921_12.bmp.html

Как вы поняли это схема все равно будет складывать числа в пределах 1разряда двоичного разряда. Нууу… скажете вы, и все это мы читали только ради этого?

Нет, следующая схема суммирует числа в пределах 10d, 1010b, тоесть четырех разрядный сумматор.

smages.com/1b/b0/1bb0dd39ae37f3ce754c2e5f72d61142.jpg.htm

Итак, получаем следующий вывод, что любой многоразрядный сумматор можно сделать из нескольких одноразрядных, причем чем больше одноразрядных сумматоров обьединено, тем больше разрядность у сумматора.

Продолжение следует....


©Kerny
специально для hackzona.ru
22.01.09 18:41