Week 2

More Adders and Programmable Gates

COS10004 Computer Systems · Lecture 2.1 – More Adders and Programmable

Gates

Chris McCarthy

Half-adder

The XOR gate calculates the sum

Two bits (two The AND gate one-bit inputs/ calculates the variables) carry

7/8/20 2 COS10004 Computer Systems

A full adder

Made from two half-adders:

Counts how many buttons are on in binary!

0 + 1 + 1 = 10

Full adder sum only

X

Y S

Ci

The following with two XNOR gates also works: check both using the simulator. X Y S

7/8/20 4 COS10004 Computer Systems

1-BIT FULL ADDER? BUT THAT'S JUST ADDING TWO BITS

To add real numbers

together (8 bits, 16, 32...) we need to cascade full adders together. Use a half adder for the first bits, full adders for the other 7 (15, 31...)

Multi bit addition: combine 8 adders with carry to get 8-bit addition (of two 8-bit numbers).

Sn S2 S1 S0 C0 C0

Carry

full full full ½ adder adder adder adder

Y X Ci Ci Ci

n n Y2 X2 Y1 X1 Y0 X0

7/8/20 6 COS10004 Computer Systems

Output = 69 + 12 = A = 0x45 B = 0x0C Output = 0x51 = 81

Most-significant bit (27) Least-significant bit (20)

A BIT MORE ABOUT GATES

Some gates offer useful functionality that is not immediately obvious

Lets look at a couple of examples …

USING XOR AS A CONTROLLED INVERTER

A Out

C A Out

0 0 0 0 1 1 If C=0, output = A 1 0 1 If C= 1, output = A 1 1 0

It's like "to invert or not invert..." turning on C enables the inverter

9 7/8/20 COS10004 Computer Systems (Out= A)

AND AS A LOGIC-CONTROLLED SWITCH

A output

A B Out

0 0 0 0 1 0 1 0 0 1 1 1

AND AS A LOGIC-CONTROLLED SWITCH

A output

A B Out AND gate as a switch

0 0 0 0 1 0 If A=0, output always 0 1 0 0 1 1 1 If A= 1, output = B

To pass through B, or not to pass through B?

…. A is the question. It's like turning on A enables the output being B

(O = B)

Choose which circuit forms the output

(two logic controlled switches)

This block of gates can be an AND gate or an OR gate depending on Ci

7/8/20 12 COS10004 Computer Systems

WAIT A MINUTE!

… you’re saying we have the capability to Program the behaviour of a block of gates?

7/8/20 13 COS10004 Computer Systems

Ye p

7/8/20 14

YES – Programmable Gates!

We can program a gate to be an inverter or a buffer. We can program a gate to do AND or OR.

SUMMARY

Full Adders can combine to create full scale addition machines

Gates offer programmability using control bits

this can be very useful for controlling data flow

Next Lecture: Clocks for synchronised.

Dr Chris McCarthy

GATES ARE NOT INSTANTANEOUS

Changing the state of a gate takes some finite time.

X

Y S

Ci

What’s the issue here?

GATES ARE NOT INSTANTANEOUS

Changing the state of a gate takes some finite time.

Ci and the output of X XOR Y will arrive at different times!!!

X The circuit is unstable. Y S If only we could synchronise things!! Ci

What’s the issue here?

GATES ARE NOT INSTANTANEOUS

Changing the state of a gate takes some finite time.

Ci and the output of X XOR Y will arrive at different times!!!

X The circuit is unstable. Y S If only we could synchronise things!! Ci

What’s the issue here?

Clock

Could be something simple like a 555 timer (astable multivibrator using an RC timing element), a crystal oscillator, a phase-locked loop or an atomic clock. Probably just a chip.

Clock feeds into the ALU

clock

time

The clock is needed because bits need to “settle” before you can use them.

Computers often have different clocks controlling different parts.

7/8/20 6 COS10004 Computer Systems

Clock feeds into the ALU Result out carry

clock ALU Control bits

Often an ALU needs 2 clock bits out of phase:

clock1 clock2

Common symbol for ALU

7/8/20 7 COS10004 Computer Systems

Summary

Clocks ensure data flow is synchronised in a circuit:
Ensures predictability
Avoid illegal/ill-defined states
Arithmetic Logic Unit:
Where integer calculations and bit shifting operations are performed
We’ll come back to both these topics!
Next Lecture: Storing bits

Dr Chris McCarthy

WHAT IS A COMPUTER SYSTEM?

Fast memory Persistent

(RAM) memory (Disks

program and data and other non- volatile memory) Central Mother Graphics processing board unit (CPU) Keyboard Input / Output accel Channels cards Mouse

Hardware What else?

BASICS OF ELECTRONIC STORAGE – CPU REGISTERS

In a computer the output is determined by current inputs and memory (previous inputs) computed together.

Inputs Combinatorial Outputs

Logic

Memory

CPU needs some way to remember information

STORING 1 BIT

Memory is built up of 1-bit storage units.
We need a circuit that holds one bit.
We set what it is to remember and it retains this until we actively change it (unless the power goes off!).
The simplest is the RS Flip-Flop

4 COS10004 Computer Systems 4

RS FLIP-FLOP – OPERATIONS

At start assume QA=0 (QB=1)

This is a stable state: a change in the Reset value from 1 to 0 will not change either output. Here, “Set” means pull the Set 1 0 Set pin to ground (0) to A QA activate it (i.e, QA = 1) 1 RESET state

0 B Q

5 COS10004 Computer Systems 5

RS FLIP-FLOP – OPERATIONS

If Set is made low (0) for a moment, the output of A (QA) goes high (1).

Set 1 A 0 Q turning the output of B (QB) to low (0). A

1 0 SET state

further change. B QB

Making Set active (low) has set QA output high.

6 COS10004 Computer Systems 6

RS FLIP-FLOP – OPERATIONS

Confused?

It's a toggle switch using push- Set 1 A 1 Q buttons. 0 A SET state Pull Set low for a moment and QA 1 B turns on. Reset 1 0 QB

turns on. A Q

A QA and QB can never be on or off at RESET state the same time 0 B QB

7 COS10004 Computer Systems 7

Exercise: complete the timing diagram below

Set 1 A 0 Q (aka Q) A 1 RESET state

0 B Q (aka Q) B 0 only when Reset 1 1 Reset pressed.

SET

Reset

Q

8 COS10004 Computer Systems 8

Exercise: complete the timing diagram below

SET

Reset

Q RESET state

SET state Q

9 COS10004 Computer Systems 9

ACTIVE LOW INPUT RS FLIP-FLOP – TRUTH TABLE

SET RESET Q Q

0 0 indeterminant dangerous!!!

0 1 1 0 1 0 0 1

1 1 no change NB Both inputs must not be active (pulled low) at the same time The flip flop outputs may change whenever an input changes. If we want synchronized changes we need to build more complex Flip-Flops!

10 COS10004 Computer Systems 10

A N RS FLIP FLOP WITH ACTIVE HIGH INPUTS

Q

An RS flip flop made out of cross coupled NOR gates has active high inputs. The stable states are as shown. Q Q. 1 Taking Reset momentarily high will set Q i.e. reset Q. Q

0 Q

11 COS10004 Computer Systems 11

NOR-BASED (ACTIVE HIGH) INPUT RS FLIP-FLOP –

TRUTH TABLE

SET RESET Q Q

0 0 no change

0 1 1 0 1 0 0 1

1 1 indeterminate NB Both inputs must not be active at the same time The flip flop outputs may change whenever an input changes. If we want synchronized changes we need to build more complex Flip-Flops

12 COS10004 Computer Systems 12

SUMMARY

CPUs need storage to keep track of state and store computation outputs
Flip Flops:
Store single bits of data
RS Flip Flop:
Set / Reset
Asynchronous therefore problematic
We can do better! (next lecture we’ll see!)

Dr Chris McCarthy

BASICS OF ELECTRONIC STORAGE – CPU REGISTERS

In a computer the output is determined by current inputs and memory (previous inputs) computed together.

Inputs Combinatorial Outputs

Logic

Memory

CPU needs some way to remember information

FLIP-FLOPS WITH CLOCKED INPUTS

The two most common clocked Flip-Flops are the D and the JK

Q J Q

D Q K Q

. Clock Clock

3 COS10004 Computer Systems 3

D FLIP FLOP

Q

D Q

Clock

The D flip-flop has only one input, Q is updated to be the same as D when the clock goes active

J-K FLIP FLOP

J Q

K Q

Clock

The JK flip-flop has two inputs.

It is updated when the clock goes active but how it is updated depends on both the J and K inputs.

D FLIP-FLOP

The external D input (Data) internally generate both an R and an S input. These are complements so never get both being active at once. Hence the true table for D and Q after each clock change to active is DN Q N+1 (N means at the clock, N+1 means after the clock) 0 0 D-FFs are used in computer registers and memories and in counters and 1 1 shift registers

6 COS10004 Computer Systems 6

Exercise

From the description given in the last slide, convert the NOR-gate RS FF into a D-type FF. Use the rising edge of the Clock for “active”.
Hint: add a couple of AND gates controlled (oppositely) by D
Clock the AND gates …

RS Fl

Set

Reset

7 COS10004 Computer Systems 7

Exercise – Solution

Step 1, Add a couple of AND gates to permit updates of state when the clock ticks over.
Step 2, Replace R and S with one input (D) and use an inverter to ensure that R is always the opposite of S.

Set

Reset

Exercise: complete the timing diagram below

Data is read Data is read here and here here and here

Clock

Data

Q RESET state Data pulse too SET state short-no change Q of state

9 COS10004 Computer Systems 9

J K FLIP-FLOP

J K FF’s are more flexible and can be used for a number of operations. The JK truth table (remember that N+1 means after the clock) J K Q N+1 A sort of 0 0 Q (No Change) programmable N gate 0 1 0 (Reset) 1 0 1 (Set) 1 1 Q N (Toggle) Note the change

The state when both inputs are active has been turned from a problem state (as it was for an RS flip flop) into something very useful (more on this later).

10 COS10004 Computer Systems 10

Uses tri-input NAND gates.
Has a defined state (toggle) when both J and K (equivalent to S and R) are high.
Waits for the clock before it changes state – can’t be made unstable.

Q ’ is another notation for Q

T FLIP-FLOPS

The T input just toggles the output.

Note the ‘ notation. Q’ means the same as Q

For inputs, CLR’ == CLR which means:

“pull CLR down to activate”

Making a T from an R S Flip-Flop

Add a couple of NAND gates controlled by D
Clock the NAND gates inversely…

Set

What goes

Here? Reset

13 COS10004 Computer Systems 13

Making a T from an R S Flip-Flop

Add a couple of NAND gates controlled by D
Clock the NAND gates inversely… We invert the Clock to one NAND gate instead of inverting the Data

Set

Reset

14 COS10004 Computer Systems 14

D-FLIP-FLOPS AS A REGISTER OR LATCH

A register (many bits) or latch (usually one bit) can be made Input before the clock Information 1 0 1 1 up from a series of D-Flip-Flops latched driven by a common clock. now D D D D

The transfer from the D side to the Clock Q Q Q Q Q side for all D flip flops occurs 1 0 1 1 simultaneously as this clock Output after the clock changes. This arrangement is found in CPU registers http://www.electronics-tutorials.ws/sequential/seq_4.html

16 COS10004 Computer Systems 16

SHIFT REGISTERS

Here is how a high A B C travels through a 3 bit Q Q Q Output shift register. For this Input D D D example we assume Q Q Q that each of the shift register bits is cleared at Clock Clock Clock the start.

Clock

Input

FF A

Q outputs FF B

FF C

17 COS10004 Computer Systems 17

SHIFT REGISTERS

A shift register takes input from one end, and at each clock change this value is moved to the next D-Flip-Flop. This is used in serial data transfer when a byte (say) of data sent on a cable one bit after another can be collected in a series of D Flip-Flops to rebuild the whole data byte. This is called serial-to-parallel conversion. Parallel output

Q Q Q Serial Output Input D D D Q Q Q

Clock Clock Clock

18 COS10004 Computer Systems 18

PARALLEL LOAD SHIFT REGISTERS

Some shift registers have the ability for you to load all their flip- flops at once, i.e. in parallel. Q1 Q2 Q3 Qn

Serial in Serial out

FF1 FF2 FF3 \dots\dots.. FFn

Serial clock

Parallel load clock

// in 1 // in 2 // in 3 // in n

Doing this then allows you to “clock out” each bit in turn (starting with bit n) using the serial clock. This gives parallel-to-serial conversion. (// is a common abbreviation for "parallel“)

19 COS10004 Computer Systems 19

SHIFT LEFT SHIFT REGISTERS

The shift registers shown so far shift data to the right. A simple rewiring gives a shift register that can move data left. Of course these may also have the ability to parallel load. Q1 Q2 Q3 Serial in

D in D in D in

FF1 FF2 FF3

Serial clock

Parallel clock // in // in // in

1 2 3

20 COS10004 Computer Systems 20

SHIFT REGISTERS AND MATHS

As well as serialising and de-serialising data (parallel to serial, serial to parallel), shift registers have other purposes.
Shifting a binary number left one place multiplies it by 2.
Shifting a +ve binary number right one place divides it by 2.
Shifting left, shifting right, in addition to adding and complementing, allow us the perform the basic arithmetic operations – addition, subtraction, multiplication and division.
Multiplication is performed as a series of shifts-left and adds.
Division is performed as a series of shifts-right and subtractions.

21 COS10004 Computer Systems 21

"LEFT" VS "RIGHT"

What do we mean by a “shift-left register”?
No matter which way we draw them, "left" should mean "from least significant bit position to most significant".
Redrawing: Q7 Q6 Q5 Q0 Serial out Serial in

FF7 FF6 FF5 …….. FF0

Serial clock

Parallel load clock

// in // in // in // in

bit7 bit6 bit5 bit0

Here the serial transfer convention is “big end first”.

22 COS10004 Computer Systems 22

THE COMPLETE SHIFT REGISTER.

To perform all these actions a shift register may need to be able to shift left, shift right and parallel load. It may have three different clock inputs to perform these actions as shown.

Q3 Q2 Q1 Q0

Serial in SR Serial in SL

Serial out SL FF3 FF2 FF1 FF0 Serial out SR

SR clock (to all ff) SL clock (to all ff)

//-Load clock (to all ff) //-Load data inputs

The main register in an UART (universal asynchronous receiver/transmitter) is a shift register like this (except more than 4 bits long)

23 COS10004 Computer Systems 23

WHERE ARE WE?

Fast memory (RAM) Persistent

program and data memory (Disks)