From a7e6070ffab93d3fc80345604464f28d9ebbf724 Mon Sep 17 00:00:00 2001
From: lshprung <lshprung@yahoo.com>
Date: Fri, 16 Oct 2020 10:28:33 -0700
Subject: Post-class 10/16

---
 11.md | 145 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 145 insertions(+)
 create mode 100644 11.md

(limited to '11.md')

diff --git a/11.md b/11.md
new file mode 100644
index 0000000..c6239a8
--- /dev/null
+++ b/11.md
@@ -0,0 +1,145 @@
+[\<- Signed numbers and subtraction](10.md)
+
+# Overflow, Comparison, ALU
+
+## Overflow
+
+- Remember, signed numbers, and hardware computation units, have a fixed number of bits
+- What happens if the result of the addition/subtraction needs more than the available bits?
+- Need to detect this condition. What happens next depends on the "system" in which the circuit is implemented
+
+### Determining Overflow
+
+- Adding two numbers with the same "sign" should not yield a result with the opposite sign
+
+![diagram](11.1.png)
+
+### HW detection of overflow
+
+- As humans, we can look at the sum of two numbers and see whether there's overflow
+- A HW circuit, like a 4-bit adder, needs a way to "flag" whether the result is valid
+	- The carry-in to the sign bit position (C3) should match the carry-out (C4)
+- Overflow = C3 ^ C4 (for a 4-bit adder)
+	- C7 ^ C8 for an 8-bit adder
+	- Remember: `^` is XOR
+- Note: adding a negative and positive number can never overflow
+
+### 8-bit signed addition example
+
+- Computation of 0xDA + 0xAB
+	- Two negative 8-bit numbers
+	
+![diagram](11.2.png)
+
+- No overflow: C7 == C8
+	- Even though C3 != C4
+- It's the sign bit that we care about!
+
+---
+
+## Comparison
+
+### Comparators
+
+- Often it's usefule to detect comparisons
+	- `==`, `>`, `<`, `!=`, `>=`, `<=`
+	- "Answer" is true/false, yes/no, 1/0
+- XOR gates provide an easy means to determine if two bits are equal (`==`)
+	- Apply to each bit position and OR the results
+	- A 1 means the bits don't match => inequality
+- For unsigned `>` or `<`, start at the MSB (most significatn bit) and find the first mismatch
+	- Really only practical for small # of bits
+
+### Signed Comparison
+
+- Subtract the numbers (A-B) and check the result
+	- Three mutually exclusive possibilities
+		- A-B > 0 => A>B
+		- A-B = 0 => A=B
+		- A-B < 0 => A<B
+- We already have a sign bit for the result
+	- Can be used to determine A-B<0, but doesn't differentiate the other two possibilities
+	- Need to add a zero-detect
+
+---
+
+## Interpreting overflow when doing comparison
+
+- Since we don't need the actual result of the subtraction, we can use overflow
+	- It doesn't matter that the computed result is wrong
+- Negative overflow
+	- Adding two negatives, sign bit of result is 0
+	- Should be 1, can be interpreted as a negative
+- Positive overflow
+	- Adding two positives, sign bit of result is 1
+	- Should be 0, can be interpreted as positive
+
+---
+
+## ALU concept and example
+
+### Arithmetic Logic Unit (ALU)
+
+- Abstraction layered on top of an adder
+	- Used for any number of operations that generate a result based on two inputs
+- Operands (A and B) and a "command"
+	- We've already seen this for subtraction
+- Output is either a computation ro a comparison result
+	- For comparison type command, output is 1 for true, 0 for false (it's a yes/no question)
+
+### Example ALU
+
+- Limit ourselves to add, subtract, and comparison
+- An example 2-bit command (F1, F0)
+	- 00 means add
+	- 01 means subtract
+	- 11 means "set on less than"
+		- i.e. "true or false: A is less than B"
+- Not that we're not using the encoding 10 just yet
+	- You'll be filling this in as a homework problem
+
+### Example ALU block diagram
+
+- F1, F0 decoded to generate controls
+
+![diagram](11.3.png)
+
+---
+
+## Comparison logic
+
+- Assumes that the decode of F1 and F0 will cause Subtract to be asserted
+- Define a signal called LT (for Less Than) to tell us "yes, A is less than B"
+- Using Sum and OVF, when whould LT be true? How do we know A-B<0?
+
+|S3 OVF|LT|
+|------|--|
+|00    |0 |
+|01    |1 |
+|10    |1 |
+|11    |0 |
+
+- For this first example, where the only comparison is "less than":
+	- The "Subtract" signal is just F0
+	- The "Comparison Type" input isn't needed
+	- The "True/False" output is just LT
+- Adding another comparison command would require use of the "Comparison Type" signal to select what value to put on the "True/False" output
+
+---
+
+## Result Selection
+
+### Selecting final result
+
+- If command is specifying add or subtract, result should be output of adder
+- If command is specifying a comparison, result should be either 0001 (true) or 0000 (false)
+	- Bits 3,2,1 are 000 in either case, bit 0 is output of comparison logic
+- How to choose between these results?
+	- What circuit do we use for a choice?
+
+### Result selection circuit
+
+- RT = Result Type
+- T/F = True/False
+
+![diagram](11.4.png)
-- 
cgit