Computer Architecture Personal Notes

4.3 Adders

Page 4.2

First, we will need the following: x ⊕ y ⊕ z is 1 when just one or all three of x, y, z, is 1. xy + xz + yz = xy ⊕ xz ⊕ yz, and is 1 when at least two of x, y, z, is 1. Half adder: Symbol _____ |x c| | HA | |y s| |_____|

Function

Truth table

Outputs

s = arith x + y with carry out c

x 0 0 1 1

s = x ⊕ y c = xy

y 0 1 0 1

s 0 1 1 0

d 0 0 0 1

Circuit x ___ c ------*-------|AND|-------------|---*---|___| y | | ___ s | |---|XOR|------|-------|___|

Full adder: Symbol _____ |c d| | | |x | | FA | |y s| |_____|

Function

Truth table

Outputs

s = arith x + y with carry in c and carry out d

x 0 0 0 0 1 1 1 1

s = x ⊕ y ⊕ c d = xy ⊕ xc ⊕ yc

y 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

s 0 1 1 0 1 0 0 1

d 0 0 0 1 0 1 1 1

noting s = 1 when 1 or all 3 of x,y,c = 1 d = 1 when at least 2 of x,y,c = 1

Circuit x ____ xy _____ d = xy ⊕ xc ⊕ yc ----------|x c|-----------------------------------| |---------------------| HA | ____ | XOR | ----------|y s|--------|x c|---------------------|____ |

⊕

y | HA | c(x ⊕ y) = cx ⊕ cy | | ------------------------|y s|-----------------------------------------------c |____| s = x ⊕ y ⊕ c y

|____| x

There is a "handle cranking" way of getting an expression for d. _ _ _ Looking at the rows of the truth table where d = 1 we see that d = xyc+xyc+xyc+xyc. Adding Integers. To perform the sum

x2 x1 x0 + y2 y1 y0 = z2 z1 z0

with carry out c3, use the circuit

c0 = 0 _____ c1 _____ c2 _____ c3 = carry out --------|c d|-----------|c d|-----------|c d|----------------| | | | | | x0-------|x | x1--|x | x2--|x | | FA | | FA | | FA | y0-------|y s|--| y1--|y s|--| y2--|y s|--| |_____| |z0 |_____| |z1 |_____| |z2

Subtraction

______ _ For integers x, y, we use : x - y = x + y , where + and - are arithmetic. Eg 15 - 5 =

1 1 1 1 . Perform 0 0 0 0 . Invert output to get 1 0 1 0 = 10 dec - 0 1 0 1 + 0 1 0 1 = 0 1 0 1

Full Subtracter Symbol _____ |c d| | | |x | | FS | |y s| |_____|

Function arith s = x - y with carry in c and carry out d

Truth table x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

s 0 1 1 0 1 0 0 1

d 0 1 1 1 0 0 0 1

_ s 1 0 0 1 0 1 1 0

_ x 1 1 1 1 0 0 0 0

Outputs _ _ s = x ⊕ y ⊕ c _ _ d = xy ⊕ xc ⊕ yc

Circuit c ______ d ---------------|c d|--------------___ _ | | x |NOT| x | FA | ---|___|-------|x | ___ | | |NOT| s ---------------|y s|---|___|------y |_____|

_ _ _ noting s = 1 when 1 or all 3 of x,y,c = 1, and d = 1 when at least 2 of x,y,c = 1 . ____ _ _ _ Alternatively, s = x ⊕ y ⊕ c, and using a ⊕ b = a ⊕ b, we get s = x ⊕ y ⊕ c .

4.3 Sequential logic : The R-S Latch

Page 4.3

The method we have used to build an adder is an example of COMBINATORIAL logic. To build a memory store or to control the execution of events in sequence we need SEQUENTIAL logic. Sequential logic uses FEEDBACK. The OLD output from a feedback device is fed back into the input to produce a NEW output. The output is called the STATE of the device. The state depends on the current input and the previous state, and by implication on the previous input. Feedback devices go through a number of temporary TRANSITIONAL STATES before settling down into a STEADY STATE. Some feedback devices have no steady state. We deal with those that DO have a steady state. The R-S Latch. NOR circuit

NAND circuit ___ ____ S---|NOT|------| |------*-------Q |NAND| | |------|____| | | | |------------------|---| | | |------------------| | | ____ | |------| | | ___ |NAND| | _ R---|NOT|------|____|----------*----P = Q

___

R------------| |------*-------Q |NOR| | |-------|___| | | | |------------------|---| | | |------------------| | | ___ | |------| | | |NOR| | _ S-----------|___|-----------*---P = Q

Symbol _______ | | |R Q| | | | _| |S Q| |_______|

Truth table: (R,S) = current input, (Q, P) = current output, (Qp, Pp) = previous output R

S

Q

NO CHANGE

0

0

Qp

P __ Qp PROVIDED previous input was not (1,1)

S = SET

0

1

1

0

R = RESET

1

0

0

1

NOT PERMITTED

1

1

0 1

0 1

NOR logic NAND logic

If the input is changed from (1,1) to (0,0) there is theoretically no steady state. In fact the device will flicker & then settle down into an INDETERMINATE steady state. Thus an input of (1,1) means row 1 of the truth table ceases to hold, and moreover produces outputs which are not complements of one another, and which depend on whether NOR or NAND logic is used. An input of (1,1) must NOT be allowed to occur. Use of the R-S latch as a memory store. Suppose R = S = 0. Changing S to 1 and back to 0 STORES 1 in the latch. Changing R to 1 and back to 0 STORES 0 in the latch. Thus the latch LATCHES onto its input and stores it. The Clock. A CPU has CLOCK that controls an OSCILLATOR whose output is a SQUARE WAVE. 1 cycle _________

Signal | | 1| ____ ____ ____ | | | | | | | | | | | | | | | | | | | | | 0|____| |____| |____| |____ Time The FREQUENCY of the clock in Hertz (Hz) is the number of cycles per second. Note that the square wave is not exactly square since it is impossible to change signal from 0 to 1 in zero time, but an oscillator generated "square" wave is very nearly square

Clocked R-S Latch

Page 4.4

Circuit

___ R.Cl _____ R------------|AND|---------|R Q|-----Q |-----|___| | | | | | Cl-----* | | | ___ S.Cl | _| _ |-----|AND|---------|S Q|-----Q S------------|___| |_____|

Symbol _______ |R Q| | | |> | | _| |S Q| |_______|

Function R = S = 0 except on a clock pulse. No change to Q except on a pulse.

Cl denotes the square wave input from an oscillator controlled by a clock. > denotes an input port for this "clock" input. Edge triggered latches Clocked latches are EDGE TRIGGERED. This means they are designed internally to respond to a CHANGE in signal of the square wave they receive at their clock input port. They are LEADING edge triggered if they respond to a change in signal from 0 to 1. They are FALLING edge triggered if they respond to a change in signal from 1 to 0. This means that the input signal to a clock port can be thought of as a PULSE. On a pulse the input signal is momentarily raised from 0 to 1 and then falls back to 0. For the clocked R-S latch R=S=0 except on a pulse, so Q is unchanged Q except on a pulse. All latches in a CPU are clocked (pulsed) simultaneously. For leading or falling edge triggered latches there is 1 clock pulse per clock cycle. It is possible to design double edge triggered latches that respond to both the leading & falling edges of the square wave signal so that there are 2 clock pulses per clock cycle. AMD Athlon CPU's use double edge triggered latches and so can do more in 1 clock cycle. 4.4 Data latches and registers. D-latch Symbol _____ |D Q| | | |> | |_____|

Function

Circuit

D = input Q = stored value pulse stores input

Register Symbol ____ |S Z| | | |D | | | |> | | | |RW | |____|

_ ___ D ______ D---*---|NOT|-----|R Q| | |___| | | | |> | | D | | |-------------|S | |______|

Note that now we will never have R = S = 1.

Circuit _____ Z S ------*---------------------------------------------| |----------------| ______ | | D ------|----------- ----| D Q|---------------------| AND | | ____ | | | | |-----| | | | |--|_____| |AND | | | | Cl -----------| |-----|> | | | | |______| | |-----|____| ___ | | |NOT| | RW ------*----------------------------|___|----------

Function S D RW Q Z

= = = = =

SELECT DATA INPUT READ/WRITE STORED VALUE OUTPUT

S = 1 : RW = 1 (Write) : Z = 0, Pulse sets Q = D RW = 0 (Read) : Z = Q, Pulse leaves Q unchanged S = 0 : Z = 0, Pulse leaves Q unchanged

4.5 J-K latch, Toggle latch, Sequencer. J-K Symbol _____ |J Q| | | |> | | _| |K Q| |_____|

Truth table J 0 1 0

K 0 0 1

1

1

Q Qp 1 0 __ Qp

Circuit No change Set Reset Toggle

|-----------------------| | ___ ____ | |----|AND|-----|S Q|---*---Q J-------------|___| | | ___ |> | K-------------|AND| | _| _ |----|___|-----|R Q|---*---Q | | |-----------------------|

J, K, Q are current input/output, Qp is previous output.

Like an R-S with J as S, K as R If J = K = 1 then a pulse TOGGLES the stored value.

T-Latch. Toggle with clear. Symbol _____ |T Q| | | |> | |_____| |CLR|

Page 4.5

Function

Circuit

T = input Q = stored value CLR = 0 : J = K = T T = 1 : Pulse toggles Q T = 0 : Pulse leaves Q unchanged CLR = 1 : J = 0 K = 1 Pulse forces Q = 0

___ ___ _______ |-----|NOT|-----| |----|J Q|------Q | |___| |AND| | | | | | | | | |------------| | | | T | | |___| |> | -------|--* | | | | ___ | | | |------------| |----|K | CLR | |OR | | | -------*---------------|___| |_______|

3-bit sequencer SC Symbol _____ |E B| | | |> SC | |_____| |CLR|

Circuit

^ b0 ^ b1 ^ b2 | | | E _____ | ___ E b0 _____ | ___ E b0 b1 _____ | >-*--|T Q |---*---| |---*--|T Q|---*---| |---------|T Q|----| | | | |AND| | | | |AND| | | | |> | |----|___| | |> | |---|___| |> | | |_____| | | |_____| | |_____| | |CLR| | | |CLR| | |CLR| | | | | |-----------| |------------|

Function B = (b2 b1 b0) = OUTPUT E = ENABLE. CLR = CLEAR

If E = 1, a pulse increases b by 1 mod 8. If E = 0, a pulse leaves b unchanged. If CLR = 0 a pulse forces b to zero.

Note that a pulse outputs a new b, but the feed forward feeds the old b into the T-latches. An n-bit sequencer implements the following rule for increasing bn-1...b2 b1 b0 mod 2n b0 is always complemented. bi is complemented if bi-1 = bi-2 = ... = b2 = b1 = b0 = 1, i > 0. 4.6 Decoder and Multiplexer (Combinatorial circuits) Decoder: 2 bit b0 ______ ------| |----A0 | 2 bit|----A1 b1 | dec |----A2 ------|______|----A3 __ __ __ A0 = b1 b0 A1 = b1 b0

n bit _______

Ai = 1 if (b1,b0) = i

__ A2 = b1 b0

b | |-------A0 -------| n bit | --n bit | dec | --|_______|-------A2n

Ai = 1 if b = i -

1

A3 = b1 b0

Multiplexer: 2bit D0 D1 D2 D3 | | | | data b0 _|__|__|__|__ ----------| | A = Di if (b1,b0) = i Select | 2 bit MUX |-------------------------------|_____________| b1 __ __ __ __ A = D0 b1 b0 + D1 b1 b0 + D2 b1 b0 + D3 b1 b0

n bit D0 |

D2n-1 | data _|________|__ b | | A = Di if b = i -------| n bit mux |-----------------n bit |_____________| select

: