CS 240 Lab 2: Data as Bits

Peter Mawhorter

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.

What does a transistor look like in silicon?

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?

The schematic diagram of the full CPU.

The CPU connections listed as a table:

Component	Inputs	Outputs
PC	Next Address from BEQ Logic	PC to read address of Instruction Memory PC + 2 to next address for BEQ Logic
Instruction Memory	Read Address from PC	16-bit Instruction splits into Bits 12-15 go to the Control Unit Bits 8-11 go to Read Addr 1 of Register File Bits 4-7 go to: Read Addr 2 of Register File Register File Write Addr Mux Bits 0-3 go to: Register File Write Addr Mux Sign extend to 16 bits and then: ALU 2nd Operand Mux Shift left 1 into Offset for BEQ Logic
Control Unit	Bits 12-15 of Instruction	Reg Write signal goes to Write Enable of Register File ALU Control signal goes to control inputs of ALU Branch signal goes to BEQ Logic Branch input Mem Store signal goes to Write Enable of Data Memory Mem signal goes to: Register File Write Addr Mux ALU 2nd operand Mux ALU/Memory result Mux
Register File	Read Addr 1 from bits 8-11 of Instruction Read Addr 2 from bits 4-7 of Instruction Write Addr from Register File Write Addr Mux (either bis 0-3 or 4-7 of instruction) Write Data from Final Result Mux (either ALU Result or Data Memory Read Data output) Write Enable from Reg Write output of Control Unit	Read Data 1 goes to ALU 1st Operand Read Data 2 goes to: The ALU 2nd operand Mux (along with sign-extended instruction bits) The Write Data input for Data Memory
Arithmetic Logic Unit (ALU)	1st operand from Read Data 1 of the Register File 2nd operand from the ALU 2nd operand Mux (either Read Data 2 from the Register File or bits 0-3 of the instruction after sign extension to 16 bits) ALU Control output from Control Unit	16-bit result goes to: Address input for Data Memory Final Result Mux (along with Read Data from Data Memory) Zero flag goes to Zero input to BEQ Logic
Data Memory (RAM)	Read Address from ALU result Write Data from Register file Read Data 2 output Write Enable from Control Unit Mem Store signal	Read Data result goes to Final Result Mux (along with ALU result)
BEQ Logic	Next Address from PC + 2 Offset from bits 0-3 of instruction after sign extend and shift left by 1 Branch from Control Unit Zero from ALU Zero Flag	Adds PC + 2 and Offset inputs and then selects that result or the original PC + 2 result using an AND between the Branch and Zero inputs. Takes this result as the Next Address and feeds it back to the PC.

Outline

Representing Numbers
Counting with a Circuit
Designing Circuits
Bit Puzzles

Setup status?

Has everyone successfully configured your CS account for CS 240?
- (First two sections of task 1 for the Zero assignment).
Questions about cs240 script or git?

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, $11_2 = 3_{10}$

Converting to Binary

Figure out biggest power-of-2 that’s smaller
- Hint: 1024 is $2^{10}$
This is the largest bit that’s a 1
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 −2n-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.

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.
Blue loading square: Select “save online” and then hit cancel.
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

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?

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

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

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

C Bitwise Operators

& bitwise AND

| bitwise OR

^ bitwise XOR

~ bitwise NOT

! logical NOT: anything other than 0 gives 0, 0 gives 1.

X << Y left-shift: shift bit-pattern of X left by Y bits.

X >> Y right-shift: shift bit-pattern of X right by Y bits.

Note: Left-shift adds zeros on right, right-shift adds copies of highest bit on left (or zeroes if unsigned).

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)