COMP8830 System Architecture Lecture 3: Instructions, numbers & logic Part II

Lecture Objectives

• Binary numbers.
• Half- and full-adders.
• Logic gates.
• Switches.
• Truth table.
• Gate delay.
• AND, OR, NOT, NAND & NOR.
• Two's complement.

References

• H&P: chapter 1 for background, then 3.1–3.3 for arithmetic, gates etc.
• Scott: (no numbers; roughly, first ~8 stories then skip forward to “The Other Half of the Computer”

Computer Components

• Processor.
• Memory.
• Memory bus (wires).
• Input/output controller(s).
• I/O bus (more wires).
• Display device, network interface, disk controller.
• Keyboard, mouse, audio device, printer (many I/O devices possible; examples…).
• Execution unit, Control unit, Register file, ALU.

From Binary to Decimal

*Quiz:
101 = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 5
*Convert hexadecimal number (25){16} to its decimal form. (25){16} = 2 \times 16^1 + 5 \times 16^0 = 2 \times 16 + 5 \times 1 = 32 + 5 = 37
*Therefore, (25){16} = (37){10}.

Half Adder

• The lowest digit is the easiest one-digit adder.
• x0 + y0 = s0 and c0 where
  • 0 + 0 = 0
  • 1 + 0 = 1
  • 0 + 1 = 1
  • 1 + 1 becomes “0 carry 1”.
• A B "Sum" "Carry".
• We have turned arithmetic into logic.

Expressing Arithmetic as Logic

• We’ve just taken arithmetic (complicated!).
• … and expressed it as logic (simpler).
• i.e. formulae that evaluate to true or false.
• Logic is simple enough to translate into digital electrical circuits.
• We often call circuits “logic”, hence ALU
  • Unit containing Logic for doing Arithmetic.

Half Adder Details

• A B Sum Carry
• XOR gate AND gate
• It’s “half” because it can’t handle a carry in
• A half adder uses only one gate between the input bit and the carry.

Full Adder

• Dealing with carry-in means adding three digits, not two … and we carry out in two cases: “0 carry 1” or “1 carry 1”
• Although the longest path in a full adder is 3 gates, we only need two gates between the carry in and carry out.

Gate Delay

• What limits the speed of logic? Gate delay!
• When the input of a logic gate is changed, the output does not change immediately!
• 1 \rightarrow (delay…) 0
• It takes a short time, called “gate delay”
• As we chain gates together, the delay adds up
• What’s the fewest gate delays possible?
  • 0 \rightarrow 1
  • 1 \rightarrow 0

Gate Delay Example

• For 4-bit numbers, three full adders and a half-adder in the lowest bit are used.
• How many gate delays are there on the longest path between the least significant bit's input and the top bit's carry output?
• Answer: 2 gate delays/full adder x 3 bits + 1 gate delay/half adder x 1 bit = 7 gate delays

ALU (Arithmetic Logic Unit)

• We've started to build an ALU (arithmetic logic unit)!

Real Adders

• Real adders also allow carry-in to the lowest digit.

Why Binary?

• A transistor is either on or off.
• The voltage in a wire is either high or low.
• A binary digit (bit) is either 0 or 1.
• Computers naturally use binary numbers.

Recap of Electrical Circuits

• Electrical circuits are made from some conductors (wires) and components
• Conductors permit charge carriers (e.g. electrons) to travel through them
• Components act (somehow) on the energy held by those charge carriers
  • e.g. turning some of it into light
• Voltage (or potential difference) is a measure of how much energy the charge carriers have at a particular point in the circuit (with apologies to physics graduates in the room)

Voltage

• Voltage (or potential difference) is a measure of how much energy the charge carriers have at a particular point in the circuit
  • “difference” -- it’s relative to some reference point
  • a bit like energy you have from being at the top of a hill
  • a bit like water pressure
  • pressure exists even when the tap is off

Electrical Circuits in Computers

• Unlike circuits you may have seen, in computers we don’t want to spend energy. We are using electricity to perform signalling, not work.
  • what should the output signal be…
  • given our input signals?
  • contrast: lighting up an LED is work!
• In the water/pipes metaphor, we designing a network of pipes that transmits pressure (voltage) but ideally no water would flow (current)
  • can’t do with zero current, but minimise

Role of Switches

• Switches, like valves, let us transfer voltage (“pressure”) to different places
• When the switch is open (i.e. switched off), we say its resistance is very high
• For components in series, volts are dropped in proportion to components’ resistance
• When we close the switch, its resistance drops. Proportionally its share of the resistance becomes much less
• The wire between the LED and the switch now has lower voltage
  • side effect 1: total resistance is much lower -> more current flows -> LED does work

Switches and Voltage

• If we put some kind of probe on the circuit where the arrow is, we would see a higher or lower voltage
  • depending on the state of the switch!
  • i.e. the switch lets us control whether the signal is 0 (low) or 1 (high)

Potential Divider

• This kind of circuit is called a “potential divider”.
• By changing the resistances, we can change how we “split the voltage”
  • a switch is just a variable resistor with only two different resistances
  • very high, very low
• V_0 = \frac{r}{r+r} \cdot 5V = 2.5V

Diagram Conventions for Digital Logic

• In the context of digital logic, we normally draw circuit diagrams a bit differently
  • use the old-fashioned resistor symbol (wiggly line)
  • abstract away the “power supply”
    • just show “input voltage” (“+”, “V in ”, “V cc ”) and “earth”
    • not all power connections shown
• V_0 = \frac{r}{r+r} \cdot 5V = 2.5V

Building Logic with Switches

• How do we set the switches to get a high (5V) value at our probe point?
• What about a low value?
• Bonus question: why do we have an extra (small-ish) resistor at the top?
• Logic gates (here NAND) are building blocks for circuits
• Ohm’s law: \Delta V = I \times r = 0 \times r = 0
• I = 0
• V0 = V{cc} - \Delta V = 5V – 0V = 5V

NAND Gates

• Logic gates (here NAND) are building blocks for circuits
• Any Boolean function can be made out of only NAND gates, or only NOR gates

Logic Gates

• AND, OR, NOR, NAND, XOR, NOT

Logic Gate Truth Tables

• AND
  • A B A∧B
  • 0 0 0
  • 0 1 0
  • 1 0 0
  • 1 1 1
• OR
  • A B A∨B
  • 0 0 0
  • 0 1 1
  • 1 0 1
  • 1 1 1
• NOT
  • A ¬A
  • 0 1
  • 1 0
• Out of these, we can build any combinational circuit
  • each combination of inputs has a fixed output
  • the circuit has no “memory”

Inventor of the Modern Adder

• Charles Babbage

Combinational Circuits

• Combinational circuits are “Boolean functions”
  • “Function”: a thing that takes some input(s) and gives an output – the same input always gives the same output
  • “Boolean”: taking only the value true or false