summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorlshprung <lshprung@yahoo.com>2020-10-16 10:28:33 -0700
committerlshprung <lshprung@yahoo.com>2020-10-16 10:28:33 -0700
commita7e6070ffab93d3fc80345604464f28d9ebbf724 (patch)
tree61ee0354cac1ec12ae858eee56348ee556583e7c
parent15e38ea0c10e039aa1c6cf4a20fa15116393faf1 (diff)
Post-class 10/16
-rw-r--r--10.md4
-rw-r--r--11.1.pngbin0 -> 17108 bytes
-rw-r--r--11.2.pngbin0 -> 12498 bytes
-rw-r--r--11.3.pngbin0 -> 37674 bytes
-rw-r--r--11.4.pngbin0 -> 7976 bytes
-rw-r--r--11.md145
6 files changed, 149 insertions, 0 deletions
diff --git a/10.md b/10.md
index c7bad48..3151605 100644
--- a/10.md
+++ b/10.md
@@ -181,3 +181,7 @@
- We are learning things in the context of underlying circuit implementations
- We have learned how to build an adder, not a subtractor
- When you need to show subtraction, you \*must\* negate and add
+
+---
+
+[Overflow, Comparison, ALU ->](11.md)
diff --git a/11.1.png b/11.1.png
new file mode 100644
index 0000000..06e8298
--- /dev/null
+++ b/11.1.png
Binary files differ
diff --git a/11.2.png b/11.2.png
new file mode 100644
index 0000000..7cf0884
--- /dev/null
+++ b/11.2.png
Binary files differ
diff --git a/11.3.png b/11.3.png
new file mode 100644
index 0000000..2e9921b
--- /dev/null
+++ b/11.3.png
Binary files differ
diff --git a/11.4.png b/11.4.png
new file mode 100644
index 0000000..5c63f28
--- /dev/null
+++ b/11.4.png
Binary files differ
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)