Difference between revisions of "NAND2GO Chapter 2. Boolean Arithmetic"
test>Xlp |
m (1 revision imported) |
(No difference)
| |
Latest revision as of 10:23, 1 August 2019
| 1. Context |
Have mastered and implemented the Or function, the And function, the Not function, the Xor function, the multiplexor (including multi-bit). Have a basic command of HDL. Have understood the notions of bit and bit operations (like negation). | ||
| 2. Goal |
Understand the notions of number and arithmetic in the computer. Understand how a computers perform arithmetic operations (this chapter only talks about addition and subtraction). Master the functions of adders and the Arithmetic Logic Unit (ALU) . Learn the efficient and elegant design of coding and the ALU. | ||
| 3. Measurable Effects |
Implement adder chips (including half-adder, full-adder, 16-bit adder, 16-bit Inc) and the ALU, and get the hardware simulator test to pass. | ||
| 4. Outputs | 5. Process | 6. Inputs | |
|
The HDL programs of adder chips (including half-adder, full-adder, 16-bit adder, 16-bit Inc) and the ALU. |
Read this chapter, watch the video of "Nand to Tetris", and then get down to the chips (including half-adder, full-adder, 16-bit adder, 16-bit Inc and the ALU). |
Backgrounds of binary numbers, binary addition and 2’s complement. The functions and the implementation guidelines of half-adder, full-adder, 16-bit adder, 16-bit Inc and the ALU. | |
| 7. External Factors | |||
General Description
One the basis of the set of logic gates built in chapter 1, we build logic designs that represent numbers and perform arithmetic operations in this chapter. There are only two states in the computer, high level and low level. We use binary codes to represent the two states. And then we use binary codes to represent numbers. Now that we have binary numbers, we can introduce arithmetic operations, including addition, subtraction multiplication, division and so on. We only talk about addition and subtraction. They are analogous to elementary arithmetic in the decimal system which we are familiar with. To compute 2 + 8 in the computer, the operands will first be converted to binary numbers, and then the result will be converted into a decimal number, which is the final answer. Multiplication is actually doing additions repeatedly. Subtracting a number is equivalent to plus its opposite number, so in fact subtraction is the addition of signed numbers. The introduction of 2's complement will make it easy to represent signed numbers. Because addition is simple but runs deep, our primary task is to implement adder chips. They set the stage for the ALU, which encapsulates all arithmetic and logic operations in a single chip, enabling many arithmetic and logic operations.
Background
Binary Numbers
We are familiar with decimal numbers. They are founded on base 10, that is to say, decimal numbers have 10 numerical codes,0, 1, 2, 3, 4, 5, 6, 7, 8, 9, which are all less than 10. Analogously, binary numbers are founded on base 2. They have 2 numerical codes 0, 1, which are both less than 2. For example, 10111 can be regarded as binary numbers, while 10200 cannot because 2 is not the numerical codes of binary numbers, it is greater than 1.
Conversion to and from Decimal system
To convert from a base-10 integer to its base-2 (binary) equivalent, the number is divided by two. The remainder is the least significant bit. The quotient is again divided by two; its remainder becomes the next least significant bit. This process repeats until a quotient of one is reached. The sequence of remainders (including the final quotient of one) forms the binary value, as each remainder must be either zero or one when dividing by two. For example, (00)10 is expressed as (1100100)2.
10_to_its_binary_equivalent.png){kind=link}
Fig2.1 Convert (100)10 to its binary equivalent
Conversion from base-2 to base-10 simply inverts the preceding algorithm. Let x = xnxn-1…x0 be string of digits. The value of x in base b, denoted (x)b, is defined as follows:
As for binary numbers, b = 2. For example, to convert (10011)2 to decimal:
Binary Addition
Like decimal addition, a pair of binary numbers can be added digit by digit from right to left. First, we add the two right-most digits, also called the least significant bits (LSB). Next, we add the resulting carry bit (which is either 0 or 1) to the sum of the next pair of bits up the significance ladder. We continue the process until the two most significant bits (MSB) are added. If the last bit-wise addition generates a carry of 1, we can report overflow. The MSB 1 will be discarded, which is important because 2’s complement makes use of this property. Otherwise, the addition completes successfully.
2’s Complement
The next problem is how to implement binary subtraction. (a – b) is defined as a + (-b), that is, subtracting a number is equivalent to adding its opposite number. So the problem that how to represent the subtraction is the problem how to represent signed numbers. This requires the introduction of 2’s complement. In a binary system with n digits, the 2’s complement of the number x is defined as follows:
For example, in a 5-bit binary system, the 2’s complement of -2 is (25 )10 - (2)10 = (30)10 = (11110)2.
Why it is reasonable?
(-x)+ x = 2n (x ≠ 0). In an n-bit binary system, the binary equivalent of (2n)10 is 10…0. An n-bit binary system can only hold the last n digits, the first one will be discarded. So (-x) + x = 0. This is exactly the definition of the opposite number.
Fig2.2 2’s complement representation of signed numbers in a 4-bit binary system
To obtain the code of –x from the code of x, first flip all the bits, and add 1 to the result. For example, in 4-bit system, (5)10 = (0101)2, after the first step we figure it out to be (1010)2, after the second step we obtain the result (1011)2. This is consistent with the table.
Another problem is how to figure out the decimal equivalent of a negative binary number if we know its 2’s complement. Flip all the bits, convert it to a decimal number, and then add 1 to the result. For example, 1011 -> 0100 -> 4 -> 5 -> -5. So the negative number is -5.
It is easy to prove the following properties of 2’s complement.
The codes of all positive numbers begin with 0.
The codes of all negative numbers begin with 1.
The system can code a total of 2 n signed numbers. The maximal is 2n-1 – 1(011…1), while the minimal is -2n-1(111…1).
With 2’s complement, we can unify addition and subtraction. In this way, hardware complexity is kept to a minimum. The design is concise and efficient.
Specificatio
Half-Adderfigure
Fig 2.3 Inputs and out puts for Half Adder
Function
Compute the addition of two 1-bit binary numbers.
Details
As shown below, there are two input pins and two output pins. a and b represent two 1-bit binary numbers, sum represent the least significant bit (LSB) while carry represent the least significant bit (MSB). If there is a carry (as for half-adder, only if both operands are 1), carry = 1, otherwise carry = 0. For example, 1 + 1 = 10, so carry = 1, sum = 0. 1 + 0 = 01, so carry = 0, sum = 1. It should be emphasized that half-adder is one-bit addition, it cannot figure out 10 + 11. There are only 4 cases as follows.
Hint: There are only four cases, so we can simply consider from the truth table. The truth table for sum happens to be consistent with the Xor function. The truth table for carry is exactly the truth table for the And function.
Full-Adder
Function
Compute the addition of three 1-bit binary numbers.
Details
As shown, there are three input pins, representing three one-bit binary numbers. The maximum is 1 + 1 + 1 = 11, which is a double-digit number. sum represents LSB, while carry represents MSB. For example, 1 + 1 + 0 = 10, sum = LSB = 0, carry = MSB = 1. If we obtain carry and sum, we can easily obtain the result of the addition.
Hint: Use half-adder twice
16-bit adder
Fig2.5 Inputs and outputs of 16-bit adder
Function
Compute the addition of two 16-bit binary numbers.
Details
As shown, there are two input pins, representing two 16-bit binary numbers. Differing from half-adder and full-adder, there is only one output, which is the result of the addition. Otherwise, we may need 16 outputs. We cannot give the truth table, because there are 232 cases.
Hint: A pair of binary numbers can be added digit by digit from right to left. The first addition only involves two one-bit number, we choose a half-adder chip. After the first addition, involving two one-bit number and carry from the last addition, we choose a full-adder chip. The method of 32-bit or n-bit adder is just the same.
16-bit Incrementer
Function
Compute the addition of one 16-bit binary number and 1.
Details
There is one input pin representing a 16-bit binary number and one output pin which is the result of the addition.
Hint: Now that we have a 16-bit adder chip, it is very easy.
The Arithmetic Logic Unit (ALU)
Function
The ALU is the centerpiece chip that executes all the arithmetic and logical functions performed by the computer.
Details
As shown below, x and y are the chip’s two 16-bit inputs, out is the chip’s 16-bit output, and f(x) is an arithmetic or logical function selected from a fi xed repertoire of eighteen functions. We instruct the ALU which function to compute by setting six input bits, called control bits, to selected binary values. Each one of the six control bits instructs the ALU to carry out a certain elementary operation. Taken together, the combined effects of these operations cause the ALU to compute a variety of useful functions. Since the overall operation is driven by six controls, the ALU can potentially compute 26 = 64 different functions. Another two outputs zr, ng respectively signifi es whether the result is 0 and whether the result is negative. The functions of six control bits and two output bits are as follows.
Fig2.6 Inputs and outputs of the ALU
zx: Set x to 0.
nx: Negate the x input.
zy: Set y to 0.
Ny: Negate the y input.
f: Choose two different operations. 1 for Add, 0
for And.
no: Negate the out output.
zr: zr = 1 if out = 0.
ng : ng = 1 if out < 0.
Fig2.7 Part of the truth table for the ALU
Hint: The idea is to implement control bits one by one, which requires repeatedly using Mux. For example, to implement nx, we can first use the 16-bit Not function, and then use Mux to choose. As for ng, according to the knowledge about 2’s complement, if MSB is 1, the output is negative. We can use 16-bit Or to complement zr.
Perspective
Binary addition is a simple operation. However, most of the operations performed by digit computers can be reduced to elementary additions of binary numbers. Therefore, constructive understanding of binary addition holds the key to the implementation of numerous computer operations that depend on it, one way or another.
Our suggested adder implement is rather efficient due to the long delays incurred while the carry bit propagates from the least significant bit pair to the most significant bit pair.
There are 64 functions in total because of 6 control bits. If there are 10 control bits, the ALU can potentially compute 210 = 1024 functions. The exponential function grows fast, so the number of the ALU’s functions grows fast with the number of control bits increasing. As a result, our ALU architecture achieves a great deal of functionality using a minimal set of internal parts. In that respect, it provides a good example of an efficient and elegant logic design.
It should be pointed out that this ALU is a simple one. There are all kinds of ALUs, some of them can be extremely sophisticated. But the fact is that simple ALUs can also perform the functions of a sophisticated ALU at a slower speed requiring more simple ALUs. That is to say, the simple ALU is fully functional.
In any given computer, the overall functionality the hardware/software plat- form is delivered jointly by the ALU and the operating system that runs on top of it. Thus when designing a new computer system, the question of how much functionality the ALU should deliver is essentially a cost/performance issue. The general rule is that hardware Implementations of arithmetic and logical operations are usually most costly, but achieve better performance. The design trade-off that we have chosen in this book is to specify an ALU hardware with a limited functionality and then implement as many operations as possible in software. For example, our ALU features neither multiplication nor division nor floating point arithmetic. We will implement some of these operations (as well as more mathematical functions) at the operating system level.
Project
Implement all the chips presented in this chapter. The only building blocks that you can use are the chips that you will gradually build and the chips described in the previous chapter. Make sure that you get all the hardware simulator tests to pass.
Glossary
Binary number
2’s complement
the least significant bit (LSB)
the most significant bit (MSB)
half-adder
full-adder
16-bit adder
16-bit Incrementer
the Arithmetic Logic Unit (ALU)
References
Description: References are divided into books, journal articles, audio recordings, videos, web pages, research reports, etc. Please select the appropriate template for reference according to your needs.
- Noam Nisan & Shimon Schocken,《The elements of computing systems. Massachusetts》, 1st edition, MIT Press, 2008, ISBN:0262640686, ,
- Binary number, https://en.wikipedia.org/wiki/Binary_number, Retrieved from December31,2017
Additional Reading Material
- Noam Nisan & Shimon Schocken,《The elements of computing systems. Massachusetts》, 1st edition, MIT Press, 2008, ISBN:0262640686, ,
- John L. Hennessy & David A. Patterson,《Computer Architecture》, 5th edition, Morgan Kaufmann Press, 2011, ISBN:012383872X(10);978-8178672663(13), ,
- Thomas L. Floyd,《Digital Fundamentals》, 11th edition, Pearson Press, 2014, ISBN:9332584605(10);978-9332584600(13), ,
- Jr. Charles H. Roth & Larry L Kinney,《Fundamentals of Logic Design》, 7th edition, CL Engineering Press, 2013, ISBN:1133628478, ,