Difference between revisions of "Binary Adders"

From Coder Merlin
(17 intermediate revisions by 2 users not shown)
Line 1: Line 1:
[[File:Half Adder.svg|thumb|link=|Half Adder]]
[[File:Gutt i matrosdress med tavle med regnestykke (9928462326).jpg|thumb|link=|Boy in sailor suit with blackboard with math]]
== Prerequisites ==
== Curriculum ==
* [[W1011 Number Systems]]
{{MerlinCurriculumData|{{ROOTPAGENAME}}}}
* [[W1012 Alternative Base Addition]]
* [[W1013 Boolean Algebra]]
* [[W1014 Logic Gates]]
* [[W1015 Bitwise Operations]]
* [[W1016 Logic Composition]]
== Introduction ==
== Introduction ==
One of the most fundamental operations performed by computers, aside from the logical operations that we've already discussed, is the arithmetic operation of addition.   
One of the most fundamental operations performed by computers, aside from the logical operations that we've already discussed, is the arithmetic operation of addition.   
Line 12: Line 7:
== Half-Adder ==
== Half-Adder ==
Let's consider what's required to add ''two'', single-bit binary integers.  We'll need one bit to represent the '''sum''' of the integers, and another to handle the '''carry'''.  Representing this in the form of a truth table yields:
Let's consider what's required to add ''two'', single-bit binary integers.  We'll need one bit to represent the '''sum''' of the integers, and another to handle the '''carry'''.  Representing this in the form of a truth table yields:
 
[[File:1-bit half-adder.svg|thumb|right|link=|Single-bit half-adder]]
   {| class="wikitable" style="text-align: center;"
   {| class="wikitable" style="text-align: center;"
   !colspan="2"| Inputs
   !colspan="2"| Inputs
Line 19: Line 14:
   ! <math>a</math>
   ! <math>a</math>
   ! <math>b</math>
   ! <math>b</math>
   ! <math>C</math>
   ! <math>C_{out}</math>
   ! <math>S</math>
   ! <math>S</math>
   |-
   |-
Line 32: Line 27:


This is formally termed a '''half-adder''', a logic circuit capable of adding two bits.
This is formally termed a '''half-adder''', a logic circuit capable of adding two bits.
<br/>
<br/>
<br/>
<br/>


{{Observe|Section 1|
{{Observe|Section 1|
Line 37: Line 36:
# What truth table do you recognize that produces the output of the '''S'''um column?
# What truth table do you recognize that produces the output of the '''S'''um column?
}}
}}


== Full-Adder ==
== Full-Adder ==
In order to add two single-bit binary integers PLUS a carry, we need an adder capable of adding ''three'' single-bit binary numbers.  Again, we'll need one bit to represent the '''sum''' of the integers, and another to handle the '''carry'''.  Representing this in the form of a truth table yields:
In order to add two single-bit binary integers PLUS a carry, we need an adder capable of adding ''three'' single-bit binary numbers.  Again, we'll need one bit to represent the '''sum''' of the integers, and another to handle the '''carry'''.  Representing this in the form of a truth table yields:


[[File:Full Adder Block.svg|thumb|right|link=|Single-bit full-adder]]
   {| class="wikitable" style="text-align: center;"
   {| class="wikitable" style="text-align: center;"
   !colspan="3"| Inputs
   !colspan="3"| Inputs
   !colspan="2"| Outputs
   !colspan="2"| Outputs
   |-
   |-
  ! <math>c_{in}</math>
   ! <math>a</math>
   ! <math>a</math>
   ! <math>b</math>
   ! <math>b</math>
   ! <math>c</math>
   ! <math>C_{out}</math>
  ! <math>C</math>
   ! <math>S</math>
   ! <math>S</math>
   |-
   |-
Line 74: Line 73:
# What do you notice about the relationship between the first-half (top four rows) of the full-adder as compared to all of the rows of the half-adder?
# What do you notice about the relationship between the first-half (top four rows) of the full-adder as compared to all of the rows of the half-adder?
# Why is this true?
# Why is this true?
}}
== Ripple Carry Adder ==
[[File:Four-bit Ripple Carry Adder.png|thumb|link=|Four-bit Ripple Carry Adder]]
We've learned that a half-adder can add two bits and full-adder can add three bits.  How can we add a multi-bit number such as a 16-bit word? By '''cascading''' four adders such that the carry ''output'' of the prior adder feeds the carry ''input'' of the subsequent adder we can add two four-bit numbers.  This concept can be easily extended to an arbitrary number of bits.
<br/>
<br/>
<br/>
<br/>
<br/>
{{Observe|Section 3|
# Why does the least significant bit position use a half-adder rather than a full-adder?
# Assume that proper inputs are applied for all bits in numbers A and B.  Will the correct output from S be available instantaneously?  If not, why not?
# Assume that we have a standard (non-scientific calculator) capable of adding two 16-bit words.  Two numbers, A and B, are added together.  After the addition, it is noted that <math>C_{15}</math> is high.  What can we infer?  What is this state commonly called?
}}
}}


== Key Concepts ==
== Key Concepts ==
{{KeyConcepts|
* A '''half-adder''' is a logic circuit capable of adding two bits and output a ''carry'' bit and a ''sum'' bit.
* A '''full-adder''' is a logic circuit capable of adding three bits and output a ''carry'' bit and a ''sum'' bit.
* A '''ripple-carry-adder''' is a logic circuit constructed of adders, cascaded in such a manner that the carry output of each adder feeds the carry input of the subsequent adder.  Using this method we are able to add an arbitrary number of bits.
}}
== Exercises ==
== Exercises ==
{{W1017-Exercises}}
{{W1017-Exercises}}


== References ==
== References ==
* [https://en.wikipedia.org/wiki/Adder_(electronics) Adder] (Wikipedia)
* Schocken, Simon and Nisan, Noam. The Elements of Computing Systems. MIT Press, 2005.
{{Experience
|experienceID=W1017
|experienceUnit=Boolean algebra
|knowledgeAndSkills=§10.331
|topicAreas=Boolean algebra
|classroomTime=30 minutes
|studyTime=1 hour
|acquiredKnowledge=understand the construction and use of binary adders
|acquiredSkill=demonstrate proficiency in constructing and using binary adders
}}

Revision as of 03:25, 22 June 2021

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder
Boy in sailor suit with blackboard with math

Curriculum[edit]

ExercisesIcon.png
 Coder Merlin™  Computer Science Curriculum Data

Unit: Boolean algebra

Experience Name: Binary Adders (W1017)

Next Experience: ()

Knowledge and skills:

  • §10.331 Demonstrate understanding and proficiency in the use of binary adders

Topic areas: Boolean algebra

Classroom time (average): 30 minutes

Study time (average): 60 minutes

Successful completion requires knowledge: understand the construction and use of binary adders

Successful completion requires skills: demonstrate proficiency in constructing and using binary adders

Introduction[edit]

One of the most fundamental operations performed by computers, aside from the logical operations that we've already discussed, is the arithmetic operation of addition.

Half-Adder[edit]

Let's consider what's required to add two, single-bit binary integers. We'll need one bit to represent the sum of the integers, and another to handle the carry. Representing this in the form of a truth table yields:

Single-bit half-adder
Inputs Outputs
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

This is formally termed a half-adder, a logic circuit capable of adding two bits.



ObserveObserveIcon.png
Observe, Ponder, and Journal: Section 1
  1. What truth table do you recognize that produces the output of the Carry column?
  2. What truth table do you recognize that produces the output of the Sum column?

Full-Adder[edit]

In order to add two single-bit binary integers PLUS a carry, we need an adder capable of adding three single-bit binary numbers. Again, we'll need one bit to represent the sum of the integers, and another to handle the carry. Representing this in the form of a truth table yields:

Single-bit full-adder
Inputs Outputs
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

This is formally termed a full-adder, a logic circuit capable of adding three bits.

ObserveObserveIcon.png
Observe, Ponder, and Journal: Section 2
  1. What do you notice about the relationship between the first-half (top four rows) of the full-adder as compared to all of the rows of the half-adder?
  2. Why is this true?

Ripple Carry Adder[edit]

Four-bit Ripple Carry Adder

We've learned that a half-adder can add two bits and full-adder can add three bits. How can we add a multi-bit number such as a 16-bit word? By cascading four adders such that the carry output of the prior adder feeds the carry input of the subsequent adder we can add two four-bit numbers. This concept can be easily extended to an arbitrary number of bits.





ObserveObserveIcon.png
Observe, Ponder, and Journal: Section 3
  1. Why does the least significant bit position use a half-adder rather than a full-adder?
  2. Assume that proper inputs are applied for all bits in numbers A and B. Will the correct output from S be available instantaneously? If not, why not?
  3. Assume that we have a standard (non-scientific calculator) capable of adding two 16-bit words. Two numbers, A and B, are added together. After the addition, it is noted that is high. What can we infer? What is this state commonly called?

Key Concepts[edit]

Key ConceptsKeyConceptsIcon.png
  • A half-adder is a logic circuit capable of adding two bits and output a carry bit and a sum bit.
  • A full-adder is a logic circuit capable of adding three bits and output a carry bit and a sum bit.
  • A ripple-carry-adder is a logic circuit constructed of adders, cascaded in such a manner that the carry output of each adder feeds the carry input of the subsequent adder. Using this method we are able to add an arbitrary number of bits.

Exercises[edit]

Template:W1017-Exercises

References[edit]

  • Adder (Wikipedia)
  • Schocken, Simon and Nisan, Noam. The Elements of Computing Systems. MIT Press, 2005.


Experience Metadata

Experience ID W1017
Next experience ID
Unit Boolean algebra
Knowledge and skills §10.331
Topic areas Boolean algebra
Classroom time 30 minutes
Study time 1 hour60 minutes <br />
Acquired knowledge understand the construction and use of binary adders
Acquired skill demonstrate proficiency in constructing and using binary adders
Additional categories