CS 240 Lab 2: Data as Bits

Peter Mawhorter

Crisis

Teaching & Learning in Times of Crisis

  • Members of our community are being targeted right now, and more is in the works.
  • We’ll continue “as normal” for now:
    • We’re learning useful & important stuff
    • Sometimes a bit of normalcy is helpful for getting through
    • Let me know if this isn’t working for you

Teaching & Learning in Times of Crisis

  • Actions you can be taking:
    • Build community & strengthen bonds
    • Do helpful things
    • Prepare your boundaries
    • Learn from history & others
    • Plan coordinated action

How do Computers Work?

When you press the power button, electricity flows through a bunch of transistors. This feeds power to things like a keyboard & monitor, which send inputs into or receive outputs from the transistors.

The transistors are organized into logic gates, like AND and OR.

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?

Outline

Setup status?

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

Representing Numbers

Representing Numbers

  • Binary represents numbers using 0 and 1
    • In base 10, each digit represents 10x10^x
      • 1, 10, 100, 1000, etc.
    • In base 2 (binary), each digit represents 2x2^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, 112=31011_2 = 3_{10}

Converting to Binary

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

103710=1024+13=1024+8+5=1024+8+4+1=210+23+22+20=100000011012 \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 16x16^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 (111121111_2) to +7 (011120111_2), including +0 (000020000_2) and -0 (100021000_2)
    • Adding two negative numbers requires special logic
  • Instead, let the first bit represent −2n-2^n and then other bits add to that to bring us closer to 0.
    • Now 4 bits can represent -8 (100021000_2) to +7 (011120111_2), with just one 0 (000020000_2). -1 is represented as -8 + 7 = 111121111_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.

Simulating Circuits

Simulating Circuits

  • Two different simulators: CircuitVerse, and the Falstad simulator.
  • CircuitVerse has more functionality for complex logic circuits, while the Falstad simulator is easier to embed in notebooks.
    • We’ll be designing circuits using CircuitVerse but will see the Falstad simulator in some slides & notebooks for examples.

CircuitVerse

  • Cursor
    • Click to select
    • Drag green circles to draw wires
    • Delete key to remove
  • “Circuit Elements” panel click to add things.
  • Timing window.
    • Use “Debug flag” from “Misc” group.
  • Properties panel (add labels, set bit width)

Wires may be “buses:” check ‘bit width’ of components

  • Use “Splitter” under “Misc” group (a.k.a. breakout)
  • Type total bits at first prompt and then group sizes at second prompt
  • ‘8’ and then ‘2 3 3’ → break out 8 wires into 3 groups: 2 then 3 then 3
  • ‘4’ and then ‘1 1 1 1’ → break a 4-wire bus into 4 individual wires

CircuitVerse Components

  • “Input” includes power, ground, and editable inputs
  • “Output” includes LEDs and hex displays plus output bits
  • “Misc” has debug flag, splitter, and adder
  • Other groups are useful too
  • “Help” in the “Properties” panel has details

CircuitVerse Issues

  • Sometimes “Preview Circuit” is more stable.
  • Sometimes gets stuck loading in Firefox. Workaround:
    1. Open dev tools under the three-bars-menu -> “More tools” -> “Web Developer Tools”
    2. Use arrows/more button near top where it says “Inspector” to open “Performance”
    3. Click “Start recording” and it should load
    4. Click “Cancel recording” and close dev tools

Counting with a Circuit

Logic Diagrams

A logic diagram of a chip numbered 7493. The chip has inputs A, B, R1, and R2, outputs QA, QB, QC, and QD, and Vcc voltage and GND ground connections. In the diagram, input A has an unconnected wire coming in and is labeled as the input, while inputs R1 and R2 are connected to ground (along with the GND connection), and input B is connected to output QA. The Q outputs are labeled as outputs, and each have an unconnected wire coming out (with QA’s wire also connecting back across to input B as already mentioned). The inputs are drawn on the left-hand side, while the outputs are on the right-hand side; Vcc is on top and GND is on the bottom. Vcc also has an unconnected wire. Each input and output is numbered with the pin number that it is connected to on the chip. Inputs A, B, R1, and R2 are on pins 14, 1, 2, and 3. Vcc is on pin 5, and GND is on pin 10. Outputs QA, QB, QC, and QD are on pins 12, 9, 8, and 11. Indeed, this doesn’t make much sense… 

  • NOT the same as a pinout.
  • Inputs on the left
  • Outputs on the right
  • Voltage on top
  • Ground on bottom

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.

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?

A timing diagram: it shows that input A is low for a bit, then high for the same duration, then back low, etc. Meanwhile, B (shown directly below A) is low for twice as long as A, then high for the same duration, then back low, etc. Output Q (shown at the very top) is high for the same duration as input A, then low for 3x that long, with the highs of Q corresponding to the highs of A which coincide with times when B is also high. 

Timing Diagrams

A circuit with inputs A and B to an AND gate with output Q. The input A is from a clock, while input B is from a square chip that takes in the A clock and outputs another signal, which also has a connection from its second output back to its first input. 

  • Inputs are a clock and a D flip-flop:
    • Clock turns off & on (adjustable via project properties)
    • D flip-flop flips from off to on when clock falls (so creates 2x as long pulses)

The same timing diagram shown on the previous slide, where Q turns on when both A and B are on. 

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

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

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

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

Parity with XOR

  • It’s possible to design a circuit for the parity bit of a message using only XOR gates.
  • The truth table for parity P on 2 bits A and B is the same as XOR.
  • How to do this for more bits?
A B P
0 0 0
0 1 1
1 0 1
1 1 0

Bit Puzzles

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:

  • Complement the number
  • Add or subtract 1
  • Mask (& with a mask value like 0x0F)
  • !(0) = 1, but !(any other number) = 0
  • Use XOR to compare values
  • Bitwise OR a general solution with a special case
  • Shift left & then right (or vice versa)