【13】 Adder: how to build a circuit like Lego (Part 1)?

【 The principle of computer organization 】 Learning notes —— General catalogue

---

• This section is very simple to understand , Only summarize the key contents

---

One 、 Gate circuit 【 The most basic unit of computer hardware design 】

“” And （AND）”“ or （OR）”“NOT（ Not ）” and “ Exclusive or （XOR）”： The most basic single bit logic operation . The following gate circuit identification , You need to be very familiar with , Subsequent circuits are composed of these gate circuits .

Today we have a billion level transistor modern CPU, All of them are composed of such gate circuits one by one .

Two 、 Half adder

1、 Column vertical Calculation ：

Exclusive OR gate ： Used to calculate “ and ”
And gate ： Used to calculate “ carry ”

2、 Lead out the half adder

therefore , Calculate a bit by an exclusive OR gate , Through an and door, we can calculate whether it is carried or not , We calculated through the circuit A one digit addition . therefore , We pack two gate circuits , Give it a name , It's called Half adder （Half Adder）.

3、 ... and 、 Full adder

1、 Lead to new problems ：

Half adder can solve the problem of one bit addition , But if you put it in both of you Come up and say , Not enough . The vertical form here is a binary addition , So if you count from right to left , The second column is not ten , I call it “ both of you ”. The corresponding left , They should be Four place 、 Octet .

The reason why two bits cannot be calculated with one and a half adders is also very simple . Because apart from an addend and an addend , You also need to add carry signals from bits , A total of three numbers are needed to add , To get the result .

2、 We use it Two half adders and an OR gate , Can be combined into a full adder .

3、8 Bit adders

The only thing to notice is that , For this full adder , In a bit , We just need a half adder , Or let the carry input of the full adder always be 0. Because there is no carry from the far right . and Carry signal of the leftmost bit output , It doesn't mean to enter another position , It means whether our addition overflows .

---

doubt ： This is also an interesting point . I used to know binary addition myself , There has always been such a question , since int In this way 16 Bit integer addition , The result is also 16 digit , How do we know if the addition finally overflows ？ Because the result can only save the result of addition 16 digit . We didn't leave a third 17 position , To record whether the result of this addition overflows .

answer 【 important 】： See the circuit design of full adder , I believe you should understand , In the result of the whole adder , We actually have a circuit signal , It will identify whether the result of addition overflows . We can Put this corresponding signal , Output to other flag bits in the hardware , Let our computer know if the result of the calculation overflows . And modern computers do just that . That's why when you write a program , Be able to know whether your calculation results overflow the support obtained at the hardware level .

Four 、 Summary extension

Important ideas in software and hardware design ： layered

From simple to complex , We have built functional components with stronger capabilities layer by layer . On the upper floor , We just need to consider how to build our own functions with the components of the next layer , Other components that do not need to sink to a lower level . It's like you haven't thoroughly studied the principles of computer composition before , You can also write code directly in high-level languages , Realization function .

At the hardware level , We go through a gate circuit 、 Half adder 、 The full adder builds functional components such as adders layer by layer . We call these components used to do arithmetic and logic calculations ALU, That's the arithmetic logic unit . When further building a strong CPU when , We will no longer focus on the most fine-grained gate circuit , It's just a combination of gate circuits ALU, As a person who can complete basic calculations Black box That's all right. .

And so on , Let's talk about CPU Design and data path , We use ALU Explain the problem for a basic unit , That's enough. .

---

Supplementary reading
For performance reasons , actual CPU The adder used in it , It's a little different from the circuit we're talking about today , It will be more complicated . Real adder , It's using a method called Carry ahead adder Things that are . You can find Peking University in Coursera Opened on 《 Computer composition 》 In the course Video-306 “ Adder optimization ” section , Understand the implementation principle of carry ahead adder , And why we use it .

summary 【 Key points of personal summary 】

• Half adder ： from An XOR gate and An and gate form . Exclusive OR gate 【 Calculation “ and ”】, And gate 【 Calculation “ carry ”】
• Full adder ： from Two and a half adders and An or door form . Three inputs 【 Input 1、 Input 2、 carry 】, Two outputs 【 and 、 carry 】
• Carry of full adder overflow ： It can be used as Overflow or not The mark of a .
• Hardware and software design Stratification thought ： Layer upon layer , Just look at the next layer of the current layer , Don't pay attention to the next layer 【 At the bottom 】.

Selected questions and answers

ask ： This talk , I explained to you in detail how the adder of unsigned numbers is built through the circuit . that , If it is a signed number represented by a complement , Can this adder add a positive number to a negative number ？ If it doesn't , How should we build the corresponding circuit ？

answer ： If negative numbers are represented by complements, addition is no different from the addition of positive numbers , But if the result is negative , It's also a complement . There will be problems if overflow occurs , The highest sign may change , Additional marker bits are required .

【 The principle of computer organization 】 Learning notes —— General catalogue