However, as
the bit number increases, the number of product terms and maximum number of literals in a product term in the expression would increase proportionally. limit the fan-in of an AND gate or an OR gate to 5. single-stage carry look-
Computer Organization
Chapter 5 The arithmetic logic unit
Chapter 5 The arithmetic logic unit
5.1 The von Neumann computer model
5.2 Parallel fast adders
Carry look-ahead（超前进位） It reduces significantly the carry creation time by generating the carry signals for all the bits at once directly from the input carry C 0
When executed, the instructions in it are retrieved from memory, one after another, and brought into the processing unit. Decodes instruction, retrieve data, perform operation, stores result in register or memory.
Carry is
transferred serially, and Fi is calculated when Ci-1 is coming. Time consumed is determined by number of bits.
A simple 4 bits serial full adder
The worst-case of
carry propagation occurs when a carry signal propagates from C0 to Cn all the way along the carry propagation circuit.
5.2 Parallel fast adders
Then C1 can be expressed ：
C1=X1Y1+(X1+Yt adders
The nature of carry propagation
C2 is
generated as long as one of the following conditions is satisfied：
5.2 Parallel fast adders
Design of a fast adder
How to improve the speed of
adder?
Change the pathway of one by one carry bits
Cn＝ XnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1 ＝(Xn+Yn) Cn-1+ XnYn
5.2 Parallel fast adders
The block carry look-ahead circuit
Theoretically speaking, expression C1~C4 can be
expanded to higher order bits up to n-1 for n>4.
Gi：when Xi and Yi are“1”，no matter whether there is low-order carry bit，the current carry bit is generated.
Pi：when either of Xi and Yi is 1，if there exist low-order carry bit, then Ci-1 is propagated to high-order carry bit
The carry of
Although n
the full adder of the Ci depends on the Ci-1
full adders work in parallel, the carry signals are generated and propagated in sequential.
The nature of carry propagation
C1 is
generated as long as one of these two conditions is meeting： (1) Both of X1，Y1 are“1”； (2) Either of X1，Y1 is“1”，and C0 is“1”。
5.2 Parallel fast adders
Design of full adder
Full
adder with the carry bit Cn-1. Fn and Cn are given as below: Fn＝XnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1 Cn＝ XnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1
An arithmetic unit (ALU) is the heart of the CPU
The ALU usually has a binary adder
The performance of the ALU is mainly determined by its adder. We need to design a fast adder to get rid of the excessive carry-propagation time of the ripplecarry adder.
5.2 Parallel fast adders
The nature of carry propagation
Put P1, G1 into C1～C4：
C1=G1+P1C0 C2=G2+P2G1+P2P1C0
（low-order bit）
C3=G3+P3G2+P3P2G1+P3P2P1C0
Control unit
Internal Bus
registers Main memory Input/ Output
CPU
ALU
External Bus
The basic organization of a stored-program computer
5.2 Parallel fast adders
half adders
add result of Xn、Yn and Cn-1 Yn Cn-1
Fn=Xn
5.2 Parallel fast adders
Design of full adder
A n
bit adder can be produced by connecting n full adders
5.2 Parallel fast adders
Design of full adder
Logic maps:
Fn＝XnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1 Cn＝ XnYnCn-1+ XnYnCn-1
+ XnYnCn-1+ XnYnCn-1
Formed by two F n :
C3=X3Y3 +(X3+Y3)X2Y2 +(X3+Y3)(X2+Y2)X1Y1 +(X3+Y3)(X2+Y2)(X1+Y1)C0 C4=X4Y4 +(X4+Y4)X3Y3 +(X4+Y4)(X3+Y3)X2Y2 +(X4+Y4)(X3+Y3)(X2+Y2)X1Y1 +(X4+Y4)(X3+Y3)(X2+Y2)(X1+Y1)C0
5.3 Analysis of the design of a commercial ALU Chip 5.4 Summary
5.1 The von Neumann computer model
The vast majority of computer systems used today are constructed on the van Neumann computer model. A computer is viewed as a stored program computer. A program is a sequence of instructions, each of which performs a basic operation. Before execution, the program is stored in memory along with data to be manipulated.
Then C2
can be expressed ：
C2=X2Y2
+(X2+Y2)X1Y1 +(X2+Y2)(X1+Y1)C0
5.2 Parallel fast adders