CS 240 Lab 3: Arithmetic Logic

Peter Mawhorter

How do Computers Work?

How do Computer Circuits Work?

  • When you press the power button, some wires in the computer are powered with +5V, based on the transistors, which implement a series of logic gates. The logic gates are organized into common units called “chips” or “integrated circuits” (ICs).

  • A clock creates cycles of high and low voltage, which creates patterns of activation over time determined by the chips. Buttons or other inputs may also create be woven into these patterns.

How do Computers Represent Things?

  • High/low voltage patterns in groups of wires represent numbers using binary. These numbers can also represent symbols via an encoding like ASCII.

  • Specialized chips create patterns of voltage from inputs to outputs which, when interpreted as binary, correspond to things like “counting” or “addition.”

But what about… ?

  • Integrated circuits put together gates to perform various functions. Which circuits are used in a CPU, and what are their functions?
  • How do the integrated circuits for basic binary operations like addition or multiplication work?
  • How are clock signals generated & managed in the computer?
  • How is memory implemented using gates?
  • How can we change what a computer does by writing a program, instead of having to re-wire it?

How does the OS Work?

  • When you boot the computer, it launches an operating system, which provides things like graphical or text interfaces for controlling the computer.
    • Most computers have graphical interfaces and either a touch screen or a mouse, possibly in addition to a keyboard.
    • Servers don’t have any direct inputs, but allow for remote connections, where input & output is via text.
    • A text interface for controlling a computer is called a “shell” or “command line.”

How does the OS Work?

  • Whatever interface you use, you will log in, and then proceed to launch individual programs to do specific stuff, like browse the web or edit a file.
    • Programs are just another kind of file, and we can create new programs using things like text editors and compilers.

But what about… ?

  • How does the “boot” process work? Where does the operating system actually start?
  • What language does the “shell” use? Why are shells still around when we have graphical interfaces?
  • How does one program launch another? How does the OS keep track of programs that are running? How do two programs run at the same time?
  • How do compliers actually work? How does our text written in a programming language turn into a program, and what does a “program” actually consist of?

Outline

  • Memes, Links, & Questions
  • Bit Puzzles (revisit)
  • Foundational circuit components:
    • Multiplexer/Demultiplexer
    • Decoder/Encoder
    • Adder
  • BREAK
  • GO

Directing Signals

Multiplexer

A multiplexer (or mux) selects one of 2n2^n inputs, using nn “select” wires whose activation pattern is interpreted as a binary number.

  • An A×BA\times B mux has AA input groups with BB wires each
  • Each input group (& the output) has BB wires
  • So an 8x2 mux has 16 inputs in 8 groups of 2, 3 select inputs, and 2 outputs.

2x1 Multiplexer

A 2x1 multiplexer circuit diagram, showing how it’s implemented. Inputs A and B each connect to a separate AND gate. The other inputs of those and gates connect to the “sel” selector input, but with a NOT gate on the way for the AND gate connected to input A. This means that switching “sel” back and forth switches which AND gate gets power from the “sel” input, but only one of them does at a time. Both AND gates connect to an OR gate whose output is the circuit output. 

8x1 Multiplexer

A diagram showing a mutiplexer as multiple wires that come in, one of which is connected to the output wire, with the select inputs controlling which connection is made. This isn’t actually how it’s implemented using transistors, but it’s a good analogy. 

We can imagine that the select inputs change which input wire (or wire group) is connected to the output.

S2 S1 S0 Q
0 0 0 D0
0 0 1 D1
0 1 0 D2
0 1 1 D3
1 0 0 D4
1 0 1 D5
1 1 1 D6
1 1 1 D7

D0-D8 are the Data inputs

Demultiplexer

A demultiplexer (or demux) is the inverse of a multiplexer: it steers an input value (or group) onto one of 2n2^n outputs based on nn select inputs.

  • The unused output lines are low/0.

1x4 Demultiplexer

The symbol for a 1x4 demux: input D comes in on the left which is the short end of a trapezoid. Select inputs S0 and S1 come in from the bottom, and outputs Q0 through Q3 go out from the right (the wide end of the trapezoid). 

S1 S0 Q3 Q2 Q1 Q0
0 0 0 0 0 D
0 1 0 0 D 0
1 0 0 D 0 0
1 1 D 0 0 0

D is the data input

Untangling Binary

Decoder

A decoder takes an nn-bit binary number on nn wires and outputs a high signal on one of 2n2^n wires with the rest low.

  • Also known as a “1-hot” encoding where “hot” refers to high-voltage.
  • Only one of the outputs is active at a time
  • Numbers M×NM\times N refer to inputs/outputs and NN is always equal to 2M2^M: you can have a 2x4 or 3x8 decoder, but a 3x5 decoder doesn’t make sense.

2x4 Decoder

A circuit diagram for the 2x4 decoder, showing inputs D0 and D1 at the top, with outputs Q0 through Q3 on the right-hand side. The inputs each split to go through a NOT gate on one side, creating wires that extend down carrying both the normal and inverse of each input signal. These normal/inverse wires feed into four AND gates (one per output) where each AND draws from the normal/inverse lines for D0 and D1 such that it will be activated when the two bits match the binary value of the output. So for example, Q0 is connected to both NOT lines, meaning that it will be high when D0 and D1 are both low. Q1 is then connected to the normal line for D0 and the NOT line for D1 so it turns on when D0 D1 is 0 1. This pattern continues for Q2 and Q3. 

3x8 Decoder Table

D2 D1 D0 Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0
0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0 0
0 1 1 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0

Encoder

An encoder is the opposite of a decoder: it takes 2n2^n inputs where only one is on at once, and has nn outputs which encode the position of the input that was on in binary.

  • Behavior is undefined if all inputs are off or more than one is on.
  • Numbers M×NM\times N refer to inputs/outputs and MM is always less than or equal to 2N2^N: you can have a 4x2 or 8x3 encoder, or even a 5x3 encoder, but you can’t have a 5x2 encoder (not enough bits of output).

4x2 Encoder

A 4x2 encoder circuit diagram. Input D0 is not connected to anything, input D1 is connected to an OR gate along with D3 to produce output Q0, and input D2 is connected to a second OR gate (also along with D3) to produce output Q1. 

Note the disconnected input: when that’s the high input, neither output is on.

Addition

Half-Adder

A half-adder adds two one-bit values to get a 1-bit result, plus a 1-bit carry-out (which is 1 when both inputs are 1).

  • Can’t use it for addition because it has no carry-in option

Full Adder

A full adder uses two half-adders to implement addition for 1 bit, with a carry-in and a carry-out.

  • With 3 inputs, the max result is 11, which only needs 2 outputs.
  • A “ripple-carry” adder for multiple bits hooks the carry-out from one adder into the carry-in of the next. This is how we add multi-bit numbers.

Adder Diagrams

Ripple-Carry