But what about… ?

• There are tens of billions of transistors in a modern computer. How are they connected?
• Transistors have 1 input & 1 output. How do we represent numbers or text?
• Logic gates just compute a single outcome from some inputs. How do computers deal with signals over time? How is memory implemented?
• How can we change what a computer does by writing a program, instead of having to re-wire it?

Setup status?

• Has everyone successfully run cs240 auth -i s24?
• Questions about cs240 script or git?

Representing Numbers

• Binary represents numbers using 0 and 1
  • In base 10, each digit represents $10^x$
    • 1, 10, 100, 1000, etc.
  • In base 2 (binary), each digit represents $2^x$
    • 1, 2, 4, 8, 16, 32, 64, 256, 512, 1024, etc.
    • We call these digits “bits”
    • These numbers show up everywhere in CS
• We use a suffix when base is unclear:
  • For example, $11_2 = 3_{10}$

Converting to Binary

1. Figure out biggest power-of-2 that’s smaller
   • Hint: 1024 is $2^{10}$
2. This is the largest bit that’s a 1
3. Repeat with the remainder after subtraction

$$\begin{align} 1037_{10} &= 1024 + 13 \\ &= 1024 + 8 + 5 \\ &= 1024 + 8 + 4 + 1 \\ &= 2^{10} + 2^3 + 2^2 + 2^0 \\ &= 10000001101_2 \end{align}$$

Hexadecimal

• Binary numbers are long and hard to read
• Decimal numbers are hard to convert to/from binary
• Hexadecimal is a compromise: base-16
  • Because the base is a power-of-2, conversion to/from binary is easy
  • Large enough to be short
  • Close enough to base-10 to be somewhat intuitive

Hexadecimal

• Uses letters A-F in addition to numbers 0-9
• Each digit is $16^x$, and converts to/from 4 bits
• A 0x prefix is often used, e.g., 0xF83A
• Two hex digits are 8 bits, which is a byte
  • Bytes are a common unit of information because one byte is enough to represent any letter of the Latin alphabet + plenty of symbols (see ASCII)
  • Max value of a byte is 255, which is FF in hex
• Converting to binary: convert each digit + concatenate

Two’s Complement

How to represent negative numbers using bits?

• Could use one bit to represent +/-, and leave other bits alone
  • 4 bits would represent -7 ($1111_2$) to +7 ($0111_2$), including +0 ($0000_2$) and -0 ($1000_2$)
  • Adding two negative numbers requires special logic
• Instead, let the first bit represent $-2^n$ and then other bits add to that to bring us closer to 0.
  • Now 4 bits can represent -8 ($1000_2$) to +7 ($0111_2$), with just one 0 ($0000_2$). -1 is represented as -8 + 7 = $1111_2$.

Advantages of Two’s Complement

• Only one zero (simplifies equality checking)
• Addition & subtraction work using a single algorithm for positive and negative numbers
  • When adding a positive number to a negative number, the overflow into the sign bit will correctly determine whether the result is positive or negative
• See this StackOverflow answer for more.

Logic Diagrams

Logic Diagrams

• The layout inside a chip is set up to minimize fabrication costs, not to make your life easy.
• When wiring things on the protoboard, ignore the logic diagram layout and just pay attention to the pin numbers.

Simulating Circuits

• Two different simulators: LogicWorks, and the Falstad simulator.
• LogicWorks has more functionality for complex logic circuits, while the Falstad simulator has a more intuitive interface.
  • Try both and then focus on the one you prefer.

LogicWorks

LogicWorks Components

• Search “binary” for Binary Switch input and Binary Probe output
• Search “5v” for “+5V” voltage source
• Search “ground” or “gnd” for ground
• Search gate name + use _2 version (e.g., ‘or_2’)
• Search IC as e.g., 74_08 or 74_93
• Search “hex” for Hex Display & Hex Keyboard

LogicWorks Issues

• Stop -> Reset Simulator -> Clear Unknowns -> Run
• If issues persist, use stick signals (yellow lighting bolt)
  • First stick all signals high, then unstick
  • Also try sticking all signals low & unsticking
• Double check connections of components by dragging
  • If it’s connected, wire will drag out
• Check for duplicate labels (they count as connections)

Falstad Simulator

Falstad Components

Found in “Draw” menu:

• Wire + resistors
• “Passive Components” has switches
• “Inputs and Sources” has voltage, ground, and clock
• “Outputs and Labels” has Labeled Node
  • Labeled nodes with the same label count as connected
• “Active Components” has NPN transistor
• “Logic Gates, Input, and Output” has logic IO + basic gates
• “Digital Chips” has lots of useful stuff

Timing Diagrams

• Combinational logic circuits can be represented by a truth table or an expression in Boolean algebra.
  • They have 1-way paths from inputs, through gates, to outputs: no loops.
  • Is the 7493 a combinational circuit? NO
• But what about memory and changes over time?
  • We’ll need more complex notation
  • Sequential circuits have internal state

Timing Diagrams

• A Timing Diagram shows the high/low state of multiple inputs/outputs as they change over time
  • Plots time on the X-axis vs. voltage on the Y-axis
  • Each input or output has its own stacked Y-axis

What combinational function is this?

Timing Diagrams

Timing Diagrams

• Sequential circuits have behavior that changes over time
  • Some elements may trigger based on a change in voltage, rather than a particular stable voltage
  • System state may depend on hidden internal variables
  • Timing diagram shows how inputs/outputs change over time, but it doesn’t show hidden variables directly
  • We’ll see more of these later

Designing Circuits

• Given a truth table, how to design a circuit for it?
  1. Use sum-of-products to build a Boolean expression
  2. Wire up gates for each operation
• Might be an inefficient circuit if you don’t simplify
• Gets messy w/ many inputs

Designing Circuits

• Can also use intuition, especially when building for many inputs
  • Often, we have 8, 16, or 32 bits (= wires) to work with
  • Just like trying integration rules in calculus, you can try out different operations over many bits mentally, and work towards a solution

Parity

• A parity bit is set so that the total number of ON bits in a message, including the parity bit, is even
• By sending a parity bit along with each row of a message, you can quickly determine if a row of the message has been corrupted (assuming only 1 bit is corrupted)
• Using row & column parity bits, you can often localize & correct errors

$1110_2$ has 3 bits set, so the parity bit would 1

$1010_2$ has 2 bits set, so the parity bit would 0

Parity with XOR

Bit Puzzle Goals

• Exercise + grow your intuition about logical operators
• Learn some tricks that may eventually come in handy
• Gain a thorough understanding of 2’s-complement representation

Bit Puzzle Tips

• Work with 4-bit or 8-bit values; double-check with 32 bits
• Write out (by hand can be good) results from applying a few operators to see if you can see a pattern

Things to try: