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

Привіт всім!
Минуло близько двох місяців, після того, як я надрукував попередню статтю, ну нічого, продовжимо…
Але на початку домовимося, тому що ми будемо працювати з системами числення, то після чисел у двійковій системі я буду ставити букву «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