|
|
Line 1: |
Line 1: |
| [[File:Gutt i matrosdress med tavle med regnestykke (9928462326).jpg|thumb|link=|Boy in sailor suit with blackboard with math]]
| | efadsffdf |
| == Curriculum ==
| |
| {{MerlinCurriculumData|{{ROOTPAGENAME}}}}
| |
| == 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.
| |
| | |
| == 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:
| |
| [[File:1-bit half-adder.svg|thumb|right|link=|Single-bit half-adder]]
| |
| {| class="wikitable" style="text-align: center;"
| |
| !colspan="2"| Inputs
| |
| !colspan="2"| Outputs
| |
| |-
| |
| ! <math>a</math>
| |
| ! <math>b</math>
| |
| ! <math>C_{out}</math>
| |
| ! <math>S</math>
| |
| |-
| |
| | 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.
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| <br/>
| |
| | |
| {{Observe|Section 1|
| |
| # What truth table do you recognize that produces the output of the '''C'''arry column?
| |
| # What truth table do you recognize that produces the output of the '''S'''um column?
| |
| }}
| |
| | |
| == 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:
| |
| | |
| [[File:Full Adder Block.svg|thumb|right|link=|Single-bit full-adder]]
| |
| {| class="wikitable" style="text-align: center;"
| |
| !colspan="3"| Inputs
| |
| !colspan="2"| Outputs
| |
| |-
| |
| ! <math>c_{in}</math>
| |
| ! <math>a</math>
| |
| ! <math>b</math>
| |
| ! <math>C_{out}</math>
| |
| ! <math>S</math>
| |
| |-
| |
| | 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.
| |
| | |
| {{Observe|Section 2|
| |
| # 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?
| |
| }}
| |
| | |
| == 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 ==
| |
| {{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|
| |
| {{JournalExercise|J1017}}
| |
| ----
| |
| * Construct your work using <span style{{Equal}}"background:white">[https://www.falstad.com/circuit/circuitjs.html?cct{{Equal}}$+1+0.000005+10.20027730826997+50+5+50%0A Falstad's Editor]</span>
| |
| * All circuits must be on a single page
| |
| * Label the page (using Text) with:
| |
| ** Your name
| |
| ** The date
| |
| * Begin each circuit with a Blank Circuit
| |
| * Label each circuit diagram (using Text) with:
| |
| ** The name of the logic gate (e.g. "NOT")
| |
| ** Each output (e.g. "sum", "carry out")
| |
| * Save the document using the <code>Save As...</code> option from the File submenu and then click on the link presented
| |
| * The file contains your work for the exercise. Create a new subdirectory, J1017, in your Journals directory. Upload the file to the J1017 directory via SFTP. Be sure to push the files to your GitHub repository.
| |
| * You may use any of the following logic gates in your implementation: AND, OR, NOT, XOR, NAND, and NOR
| |
| ----
| |
| # Construct a half-adder
| |
| # Construct a full-adder
| |
| ----
| |
| * {{MMMAssignment|M1017-31}}
| |
| }}
| |
| | |
| == References ==
| |
| * [https://en.wikipedia.org/wiki/Adder_(electronics) Adder] (Wikipedia)
| |
| * Schocken, Simon and Nisan, Noam. The Elements of Computing Systems. MIT Press, 2005.
| |
| {{Experience | | {{Experience |
| |experienceID=W1017 | | |experienceID=W1017 |
| |experienceUnit=Boolean algebra | | |experienceUnit=Boolean algebra |
| |knowledgeAndSkills=§10.331 | | |knowledgeAndSkills=Knowledge and skills |
| |topicAreas=Boolean algebra | | |topicAreas=Boolean algebra |
| |classroomTime=30 minutes | | |classroomTime=30 minutes |